Generics and the Covariance Problem

Since some version of this question keeps showing up on StackOverflow, and the answer’s always basically the same, I figured I may as well write up a post on here that people can link to.  Here’s the question, in simplified form:

“Why can’t I pass a TList<TMyDerivedObject> to a function that’s expecting a TList<TMyBaseObject>?  You can pass a TMyDerivedObject to a parameter expecting TMyBaseObject, so why doesn’t it work for lists?”

It really looks like it ought to be that simple, but unfortunately it’s not.  Trying to do this gets into a tricky issue in type theory known as covariance and contravariance, which is a formal way of describing the relationship between different types when one inherits from another.

It’s important to remember that object types don’t really exist at the binary level.  They’re an abstraction that makes it easier for us to work with them, but when you get down to it, all that’s there is a sequence of bytes.  As a strongly-typed language, it’s up to the Delphi compiler to make sure that, when you have a TMyDerivedObject, it doesn’t get replaced with a TMyIncompatibleObject that will cause things to crash or corrupt your data when you try to use it.  This is why you’re not allowed to pass descendant classes to a var parameter, for example:  because in the function using the var parameter, you’re allowed to replace the object with something else, and if the compiler can’t guarantee that the replacement will be of a compatible type, it prevents you from passing it in order to preserve type safety.

This is basically the same problem you get when dealing with generic lists.  Let’s say you have a TList<TMyDerivedObject> and you pass it to a function that expects a TList<TMyBaseObject>.  As long as all it does is reads the items in the list, you’re just fine.  But if this function calls .Add on the list and adds a TMyIncompatibleObject, (which also descends from TMyBaseObject, and so is perfectly legal in this context,) then you’ve violated type safety.  You have a list that’s supposed to only contain one type of object, and now there’s something incompatible inside.  And since this is done by calling a method on the list object and not by directly assigning one variable to another, the compiler can’t check to make sure you’re not doing something dangerous like this, so it forbids the entire concept in order to preserve type safety.

There’s a solution to this problem.  You can extend the language syntax a little so that the compiler does have a way to check this.  You have to mark the methods on the list so that the compiler knows that it’s safe for them to receive an object that descends from, or is an ancestor of, the specified generic type.  For example, you could mark TList<T>.Add with a hint that it’s OK to add descendants of the T type, but not ancestors.  Then the compiler uses this to determine more relaxed type safety rules that allow you to pass around different generic types without the danger of mixing incompatible types together.

The latest version of Prism supports this, but the Delphi team hasn’t implemented it yet.  I haven’t heard anything to indicate that they’re working on it for Delphi 2011 either.  Hopefully it they’ll find some way to implement it for Delphi 2012.

7 Comments

  1. Stefan says:

    If you are really sure that the function you call just reads and doesnt cause the things you mentioned you can just cast your TList<TMyDerivedObject> to TList<TMyBaseObject> and pass it.

  2. Ken Knopfli says:

    “It’s important to remember that object types don’t really exist at the binary level.”

    Is that what they mean when they speak of “Syntactic Sugar”?

  3. Warren says:

    I had never heard of the term “Covariance” and “Contravariance” until I read about it in the context of C# 3.0. The explanation there was not nearly as clear as your explanation.
    Kudos for making sense of something I read several articles about, all the while understanding none of it. Now I think I get it.

    W

  4. François says:

    Nice job explaining it. I think the “var” analogy is great to make it easier to grasp.

  5. Mason Wheeler says:

    Stefan: Fixed the angle brackets for you.

    Ken: Not really. Syntactic sugar is when you have something in the syntax of the language that doesn’t add anything new, but makes it easier to do something that you could do in a different way. For example, any for loop could be written as a while loop instead, but it would take more lines to do the same thing, so for loops are syntactic sugar.

    Warren, François: Thanks! I tried to make this a clear explanation. Glad to hear that it worked for you guys.

  6. Ken Bourassa says:

    My favorite “syntactic sugar” is certainly the new EXIT syntax.

    if SomeCondition then
    EXIT(SomeValue)

    Instead of

    if SomeContion then
    begin
    Result := SomeValue;
    EXIT;
    end;

  7. Lars Fosdal says:

    One way to implement “typesafe” lists which I frequently use, is to have a class function in the list class that returns the default baseclass of the objects that can be added/inserted. In most cases, this will ensure that the ancestor list object can add/insert new objects without breaking the dependencies of the descendant list. One limitation is that the basetype must be able to tolerate not having any new properties set (ie properties that are not known to the ancestor list). By implementing Assign/Copy methods for the list item object class, you can also do safe duplication in the ancestor list object.