julian m bucknall >> C# generics and covariance, part one

C# generics and covariance, part one

published: Tue, 28-Jun-2005 | updated: Thu, 27-Oct-2005

Time to blow your mind. You've downloaded Visual C# Express or maybe you're using the full Visual Studio 2005 beta 2. You've seen that C# 2.0 now includes generics, or a way of writing classes that accept type parameters. You've played around with List<T> and seen that it's pretty good. You're feeling comfortable with generics, right?

Perhaps you've even written this method

public static T Max<T>(T[] array) where T : IComparable {...}

and sweat broke out a little when you wrote that constraint. "Let's see: I'm writing a Max() function that works on an array of Ts to return the maximum one. To do that I need to compare two Ts. I can't assume that the less than operator is defined for T, so I have to tell the compiler that I can only use Ts that implement IComparable. Cool! Er, or is it IComparable<T>? Ulp."

Believe me, that's a pretty simple case (the correct answer and discussion is below). Let's sweat a little more before we get there.

I hope we're all familiar with this fact: since String derives from Object, C# guarantees that String[] derives from Object[]. That is, to use the proper terminology, in C# arrays are covariant with their base types. Oh, and this only works with reference types.

What does this mean in our code? Well, let's play around with a test:

class Base {
  }

class Derived : Base {
  }

class Test {
  void F() {
    // create new array of Base
    Base[] baseArray = new Base[20];          

    // create new array of Derived
    Derived[] derivedArray = new Derived[20]; 

    // can assign array of Derived to array of Base
    Base[] baseArray2 = derivedArray;         

    // CANNOT assign array of Base to array of Derived
    Derived[] derivedArray2 = baseArray;   // compiler error here
  }
}

All this is fairly uncontroversial, and it mimics what happens (and what you'd expect) for plain instances of Base and Derived (that is, you can assign an instance of Derived to a variable of type Base, but you can't do it the other way round.

OK. So we've seen that C# assumes that arrays are covariant with their element type. (By the way, there's a little more to this topic that I won't go into right now.)

Right. Let's see if this works with List<T>. That's pretty much an array, right?

class Base {
  }

class Derived : Base {
  }

class Test {
  void F() {
    // create new List<Base>
    List<Base> baseArray = new List<Base>();

    // create new List<Derived>
    List<Derived> derivedArray = new List<Derived>(); 

    // CANNOT assign List<Derived> to List<Base>
    List<Base> baseArray2 = derivedArray;      // compiler error here

    // CANNOT assign List<Base> to List<Derived>
    List<Derived> derivedArray2 = baseArray;   // compiler error here
  }
}

Er, what's going on? The compiler won't let us assign a List<Derived> to a List<Base> like in the old array case. I can see the second one still failing -- it's a similar case to the one before after all -- but the first one? What's with that? Looks like it should work.

Let's imagine that it could work. Think about what the compiler and the Jitter are colluding to do. The compiler compiles the generic List<T> class into a type template rather than a real type. The Jitter will then compile the type template into a proper type when it first encounters a List<whatever> declaration (this is called constructing the type). Internally, the Jitter will give the compiled type a unique name, but for simplicity let's imagine that it just removes the angle brackets. So our code will look like this at *runtime* (note this code is only to help us visualize what's going on, the Jitter doesn't actually write this code and compile it):

class ListBase : object, someinterfaces {
  public void Add(Base item) {...}
  ..etc..
}

class ListDerived : object, someinterfaces {
  public void Add(Derived item) {...}
  ..etc..
}

class Test {
  void F() {
    ListBase baseArray = new ListBase();
    ListDerived derivedArray = new ListDerived(); 

    ListBase baseArray2 = derivedArray;      
  }
}

Well it looks a lot more obvious that it won't work this time. The only common superclass ListBase and ListDerived have is System.Object. They certainly don't derive from one another. To convert (that is, assign) a ListDerived to a ListBase, we'd have to write some code; there is no possible implicit conversion.

Hence although string derives from object, it is not true that the class Foo<string> derives from Foo<object>. We say that generic classes are not covariant with respect to their type parameters.

Phew. More on this subject later on, but for now I return to the original Max<T>() method: which should it be? IComparable or IComparable<T>? And why?

First thing to notice is that it compiles just dandily both ways. And if you wrote some code to test it, it would work just dandily both ways. So, what's the difference?

We return to one of the really groovy things about generics compared with writing code that used objects (say the difference between List<T> versus ArrayList). For value types the jitter will construct the type from the template to use instances of the value type, and will not use boxing. For value types, the generic class will be faster than the non-generic version using objects, because it won't have to box instances of the value type. (Or, to use a concrete example, using a List<int> is much faster than an ArrayList into which you stuff int values. The latter case requires the compiler to issue boxing calls to get the ints into the ArrayList, and unboxing calls to get them out.)

The difference between IComparable and IComparable<T> is that the former will cause boxing and the latter won't. So the best constraint to use is IComparable<T>, just in case you later construct the generic Max<T>() method with a value type.

Update 23-Jun-2005

Somehow I knew this post would cause problems. Not with my human readers mind you, but with my non-human readers. The issues are due to the angle-brackets with which you adorn type parameters. The web page displays fine, but currently my RSS feed looks wierd when rendered, at least in FeedDemon (which is what I use as aggregator). I've posted a query into FeedDemon's tech support forums; I'll let you know what transpires.

Update 1-Jul-2005

Nick Bradbury confirmed that the problem with this post was due to FeedDemon, or rather to this situation: "When I first created FeedDemon, a lot of feeds were double-escaping HTML, which caused them to be displayed incorrectly in FeedDemon (and many other RSS readers). So, I added a hack which corrected for this problem - which in your case, is having the exact opposite effect." He says it'll be fixed in version 1.6.

BTW, congratulations to Nick on merging with NewsGator: I'm really looking forward to the new things he and the NewsGator team are working on.