Generic type parameter variance in the CLR


When people start using C# generics for the first time, they are sometimes surprised that they can’t convert between related generic instances.  For example, since you can convert a string to an object, shouldn’t you also be able to convert a List<string> to a List<object>?  After all, you can convert a string[] to an object[], why should List<T> be any different?


 


More formally, in C# v2.0 if T is a subtype of U, then T[] is a subtype of U[], but G<T> is not a subtype of G<U> (where G is any generic type).  In type-theory terminology, we describe this behavior by saying that C# array types are “covariant” and generic types are “invariant”. 


 


There is actually a reason why you might consider generic type invariance to be a good thing.  Consider the following code:


 


List<string> ls = new List<string>();


      ls.Add(“test”);


      List<object> lo = ls;   // Can’t do this in C#


      object o1 = lo[0];      // ok – converting string to object


      lo[0] = new object();   // ERROR – can’t convert object to string


 


If this were allowed, the last line would have to result in a run-time type-check (to preserve type safety), which could throw an exception (eg. InvalidCastException).  This wouldn’t be the end of the world, but it would be unfortunate.  Part of the benefit of generic types is that it helps to avoid the run-time checking and error handling overhead involved in converting back and forth from a base type (object in C#).  It simplifies things greatly (both from a developer and run-time perspective) to be able to say that a variable of type List<object> can for sure hold any object.


 


So what about arrays, don’t we have the exact problem there?  Yep.  This was a hotly debated aspect to C#/CLR design.  Java also has covariant array types, and whether or not this is a language flaw has been debated for ages. Jim Miller has an interesting annotation in his CLI book (pg 59) where he says “The decision to support covariant arrays was primarily to allow Java to run on the VES.  The covariant design is not thought to be the best design in general, but it was chosen in the interest of broad reach”.  [Update: I’ve heard that Bill Joy, one of the original Java designers, has since said that he tried to remove array covariance in 1995 but wasn’t able to do it in time, and has regretted having it in Java ever since]


 


Let’s get back to our original question.  What if you really did want covariant generic types in a .NET language?  Does the CLR really prevent that?  Well, you may recall that I alluded to the fact that Eiffel makes use of additional features in the CLR generic support, that C# and VB do not.  In Eiffel, generic types are always covariant (and so have the same sort of run-time checks as arrays).  If you were to look at the draft v2 ECMA specification, you would see the following:


 


In addition, CLI supports covariant and contravariant generic parameters, with the following characteristics:


·         It is type-safe (based on purely static checking)


·         Simplicity: in particular, variance is only permitted on generic interfaces and generic delegates (not classes or value-types)


·         Languages not wishing to support variance can ignore the feature, and treat all generic types as non-variant.


·        Enable implementation of more complex covariance scheme as used in some languages, e.g. Eiffel.


 


Contravariance is the opposite of covariance – it means that the subtype relationship of the generic type varies inversely with the relationship of the type parameter.  Or formally, G<T> is a subtype of G<U> if and only if U is a subtype of T.  This is a pretty cool approach in my opinion.  It allows a compiler to mark generic type parameters on an interface as being nonvariant, covariant or contravariant, and then enforces that those types are used only in places where they are safe (i.e. don’t require a run-time type check).  Specifically, it’s always safe to use a covariant type as an output (return type or out parameter), and a contravariant type as an input.  In IL, covariant type parameters are indicated by a ‘+’, and contravariant type parameters are indicated by a ‘-‘ (non-variant type parameters are the default, and can be used anywhere).  Consider this simple example (using a theoretical extension of C#) from the draft ECMA spec [Update: switched to the newly announced C# 4.0 syntax]:


 


// Covariant parameters can be used as result types


interface IEnumerator<out T> {


      T Current { get; }


      bool MoveNext();


}


// Covariant parameters can be used in covariant result types


interface IEnumerable<out T> {


      IEnumerator<T> GetEnumerator();


}


// Contravariant parameters can be used as argument types


interface IComparer<in T> {


      bool Compare(T x, T y);


}


 


This would mean we could write code like the following:


 


      IEnumerable<string> stringCollection = …;


      IEnumerable<object> objectCollection = stringCollection;


      foreach( object o in objectCollection ) { … }


 


      IComparer<object> objectComparer = …;


      IComparer<string> stringComparer = objectComparer;


      bool b = stringComparer.Compare( “x”, “y” );


 


But we couldn’t do the opposite – try and convert an IEnumerable<object> to an IEnumerable<string>, or try and convert an IComparer<string> to an IComparer<object>.  In those cases, we’d get a compile time error telling us such a conversion wouldn’t be type-safe.  Of course, languages (like Eiffel) are free to build their own run-time type checking on top of the strict CLR support to relax the rules where they see fit.


 


In my opinion this sort of language feature would occasionally be very useful (although the real scenarios would, of course, be much more involved than the above simplistic examples).  There have been a couple of times when writing real-world C# code when I knew I could write simpler code if the CLR generic variance support was exposed in C#.  Generic variance support in C# has been discussed on the MSDN product feedback center, and I don’t think the C# team has ruled it out for a future addition to the language (but of course I don’t know their plans any better than you do).  Although I think this is a cool feature, I don’t think I’m going to start writing any applications in IL just so I can take advantage of it.  However, it would probably be a fun project to write or extend and existing free C# compiler (like Mike Stall’s Blue) with support for generic variance.  If you’re interested in more details (including a thorough description of assignment compatibility in the face of generic variance) see the draft v2 ECMA specification.


 


[Update: Added details about covariant arrays from Jim Miller’s CLI book, and pointer to the draft v2 ECMA spec above.]


[Update: See my post “More on generic variance” for more details and discussion]


[Update: Here’s an MSDN article that discusses this as well: http://msdn2.microsoft.com/en-us/library/ms228359(vs.80).aspx]


[Update: Anders has finally announced that C# 4.0 and the BCL will support generic variance with “in” and “out” keywords.  This has been in the works for awhile, and of course I’m super excited about it.]

Comments (19)

  1. Paul Tessier says:

    After using generics for that last month, I know I can never go back again. Right now through, I’d kill for exactly what you have in your "theoretical extension of C#".

    I’ve writen:

    class A<T>

    {

    void F<T2>(A<T2> val) where T2 : T

    }

    I’m going crazy.

  2. MSDNArchive says:

    Hi Rick. Today a tester walked into my office and complained to me that he can’t convert a List of derived classes to a List of the base class. When I explained that that would violate type safety because List objects are not read-only, he asked if he could just wrap it in some kind of read-only adapter which would then be covariant. He should be able to, but the sad answer is no – it would be great to have this simple kind of OO type support in C# generics. Definitely something to push for in C# 3.0.

  3. rmbyers says:

    Yep, that’s exactly what you’d want to be able to do.  In fact, IEnumerable<T> is that "read-only wrapper".  I’ve spoken with the C# team about this.  In fact, Mads Torgersen is the key person that got this support added to Java (in the form of wildcard types), and I was impressed to see that he now works on our C# team.  Not surprisingly, he’d like very much to be able to add this to C#, but there are additional complications in C# that make that very difficult (in Java, wildcard types were added at the same time as generics – in C# we’ve got a significant compatability problem, plus in Java generics exist only in the compiler, not in the run-time type system like in the CLR).  So, unfortunately, I wouldn’t hold your breath waiting for this in C# 3.0.

  4. Lately, I’ve been fielding questions as related to conversion between related generic types in C# 2.0….

  5. Rick Byers says:

    In my entry on generic variance in the CLR, I said that you can’t convert a List&amp;lt;String&amp;gt; to a List&amp;lt;Object&amp;gt;,…

  6. This post is aresult of an expensive lesson I learned. The situation: A MVP style architecture, Presentation

  7. If generic casting to base generic classes is not possible, is there a way we can work around this without writting hundreds of lines of code?

    I’ve got in the simplest terms a lockmanager which manages locks on rows in a table. This lock manager is inherited by a lot of managers of specific tables and features.

    A generic form of mine takes editor controls and manages all the lock/save operations. If i want to provide a "business manager" to it as much as a "department manager" it won’t let me do it.

    If i can’t convert back to a generic lock manager to handle various types of object how can i work around that still keeping it secure and allowing only business objects or contact objects to their respective managers?

  8. Very many thanks for a good work. Nice and useful. Like it!

  9. rmbyers says:

    TheInsaneCoder,

    Sorry for the delay – I’ve been out of the office for the past few weeks (just had my first child!).  

    Casting (and even implicit conversions) to base generic classes IS possible.  Eg., if Bar<T> derives from Foo<T> then you can convert a Foo<int> to a Bar<int>.  

    What we’re talking about here is converting between different generic instantiations (eg. List<Foo> to List<Bar>).  In general this is not safe, and if you find yourself wanting to do this a lot it often means there is a flaw in your generic type design (eg. you don’t really want the strong typing generics provide).

    To mix between the strong-typing and weak-typing world, you often want to have generic classes implement non-generics interfaces.  This allows you to throw away the extra type information embodied by the generic type parameters when its appropriate to do so.

    Eg., List<T> implements the non-generic IList and IEnumerable interfaces for exactly this reason.

    Its hard to say for sure without a more detailed description (and/or code) of what you’re trying to do.  But it sounds to me like you perhaps want your generic lock managers to implement a non-generic lock manager interface.

  10. cherridge says:

    My real confusion (and i’m sure this is what your describing) is why this doesn’t work…

    I’m only casting the generic type with it’s T parameter going back to an interface that T derives from…

    Am i missing something here or is it just impossible in c#2?

    interface IAmAString

       {

           string Text {get;}

       }

       class MyStringClass : IAmAString

       {

           string _Text;

           public string Text

           {

               get

               {

                   return (_Text);

               }

           }

       }

       class GenericClassA<T> where T : IAmAString

       {

       }

       class Program

       {

           static void Main(string[] args)

           {

               object o = new GenericClassA<MyStringClass>();

               GenericClassA<IAmAString> newo = (GenericClassA<IAmAString>)o;

               //I’ve just thrown a casting exception

           }

       }

  11. rmbyers says:

    Cherridge,

    Yes that is exactly what I’m describing.  It’s intentionally not possible (if it were, you’d lose a lot of the benefits of generics).

    Specifically, if you could do that, then what would a program like this do?:

    interface IAmAString

    {

       string Text { get;}

    }

    class MyStringClass : IAmAString

    {

       string _Text;

       public string Text

       {

           get

           {

               return (_Text);

           }

       }

    }

    class OtherStringClass : IAmAString

    {

       int _num;

       public string Text

       {

           get

           {

               return _num.ToString();

           }

       }

    }

    class GenericClassA<T> where T : IAmAString

    {

       GenericClassA(T init)

       {

           _field = init;

       }

       

       public T _field;

    }

    class Program

    {

       static void Main(string[] args)

       {

           GenericClassA<MyStringClass> o = new GenericClassA<MyStringClass>(new MyStringClass());

           GenericClassA<IAmAString> newo = (GenericClassA<IAmAString>)o;

           // If that worked, I could now do this:

           IAmAString newString = new OtherStringClass();

           newo._field = newString;

           // Now what type should this be?  Generics are supposed to allow this to work without a type-check

           // or possibility if InvalidCastException.  But we’ve got a OtherStringClass stored where we expect

           // to have a MyStringClass!

           MyStringClass s = o._field;

       }

    }

    Perhaps really what you want to write is something more like this (similar to how List<T> implements the non-generic IList interface):

    interface IAmAString

    {

       string Text { get;}

    }

    class MyStringClass : IAmAString

    {

       string _Text;

       public string Text

       {

           get

           {

               return (_Text);

           }

       }

    }

    interface IStringClass

    {

       IAmAString SomeFunc();

    }

    class GenericClassA<T> : IStringClass where T : IAmAString

    {

       public T SomeFunc()

       {

           …

       }

       // This function lets us decide explicitly what happens when a T is converted to a IAmAString.

       // In this case we can just do an implicit conversion.  In other scenarios you may want a runtime-checked

       // cast.

       IAmAString IStringClass.SomeFunc()

       {

           return SomeFunc();

       }

    }

    class Program

    {

       static void Main(string[] args)

       {

           // Here we can use things knowing their exact type

           GenericClassA<MyStringClass> o = new GenericClassA<MyStringClass>();

           MyStringClass s1 = o.SomeFunc();

           // But if we want to erase some of that type information, we still can:

           IStringClass newo = o;

           IAmAString s = newo.SomeFunc();

       }

    }

  12. I&#39;ve posted about this before , largely covariance is possible in C# delegates but not featured in

  13. cisjokey says:

    Hello dear

    I’hope i can post something usefull. I’had the same problem as you all. And (in some cases) its easy to come around;

    I make a sample with a “Searcher” class;

    class Searcher

    {

       public ICollection<ISearchItem> Search(IList<ISearchItem> listToSearch)

    { //searches through the items }

    }

    }

    Now if you have a list with items of a type that implements this ISearchItem interface, you get the compiler-errors as you described above.

    e.g List<SearchItem>

    what you could do is the following thing;

    class Searcher

    {

       public ICollection<T> Search<T>(IList<T> listToSearch) where T:ISearchItem

    { //searches through the items }

    }

    }

    And now, you can use your Interface without writing hundreds of lines of code. You do not see which type is expected with intellisense when using this Searchmethod, but the method is at least “typesave”.

    If this post is useless or misplaced/misinterpreted, just delete it (im not that programming geek and do not know if this is a suiteable solution).

    Greetings

    Cis

  14. rmbyers says:

    Cis,

    Yes – that’s exactly right, in some cases you can use a generic method with a base class constraint to overcome this limitation.  I talked about this option in detail in my follow-up post here: http://blogs.msdn.com/rmbyers/archive/2006/06/01/613690.aspx

  15. richardcollins says:

    I would certainly like to see this kind of extension made to C#, but I would prefer the syntax to be, e.g.:

    interface IEnumerable<out T> { … }

    interface IComparer<in T> { … }

    as this describes the constraints more clearly.

    -Richard.