This weekend, I finally decided to step into the 21st century and began the process of migrating RSS Bandit to v2.0 of the .NET Framework. In addition, we've also moved our source code repository from CVS to Subversion and so far it's already been a marked improvement. Since the .NET Framework is currently on v3.0 and v3.5 is in beta 1, I'm fairly out of date when it comes to the pet peeves in my favorite programming tools. At least one of my pet peeves was fixed, in Visual Studio 2005 I finally have an IDE where "Find References to this Method" actually works. On the flip side, the introduction of generics has added a lot more frustrating moments than I expected. By now most .NET developers have seen the dreaded

Cannot convert from 'System.Collections.Generic.List<subtype of T> to 'System.Collections.Generic.List<T>'

For those of you who aren't familiar with C# 2.0, here are examples of code that works and code that doesn't work. The difference is often subtle enough to be quite irritating when you first encounter it.

WORKS! - Array[subtype of T]  implicitly casted to Array[T]

using System;
using Cybertron.Transformers;

public class TransformersTest{

  public
static void GetReadyForBattle(Transformer[] robots){
    foreach(Transformer bot in robots){
        if(!bot.InRobotMode)
            bot.Transform();
    }
  }

  public static void Main(string[] args){

    Autobot OptimusPrime = new Autobot();
    Autobot[] autobots = new Autobot[1];
    autobots[0] = OptimusPrime;

    Decepticon Megatron = new Decepticon();
    Decepticon[] decepticons = new Decepticon[1];
    decepticons[0] = Megatron;

    GetReadyForBattle(decepticons);
    GetReadyForBattle(autobots);

  }
}

DOESN'T WORK - List<subtype of T> implicitly casted to List<T>

using System;
using Cybertron.Transformers;

public class TransformersTest{

  public static void GetReadyForBattle(List<Transformer> robots){
    foreach(Transformer bot in robots){
    if(!bot.InRobotMode)
        bot.Transform();
    }
  }

  public static void Main(string[] args){

    Autobot OptimusPrime = new Autobot();
    List<Autobot> autobots = new List<Autobot>(1);
    autobots.Add(OptimusPrime);

    Decepticon Megatron = new Decepticon();
    List<Decepticon> decepticons = new List<Decepticon>(1);
    decepticons.Add(Megatron);

    GetReadyForBattle(decepticons);
    GetReadyForBattle(autobots);

  }
}

The reason this doesn't work has been explained ad nauseum by various members of the CLR and C# teams such as Rick Byer's post Generic type parameter variance in the CLR where he argues

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.

Even if I buy that the there is no good way to prevent the error scenario in the above code snippet without making generic types invariant, it seems that there were a couple of ways out of the problem that were shut out by the C# language team. One approach that I was so sure would work was to create a subtype of System.Collections.Generics.List and define implict and explict cast operators for it. It didn't

WORKS! - MyList<T> implicitly casted to ArrayList via user-defined cast operator

using System;
using Cybertron.Transformers;


public class MyList<T>: List<T>{

  public static implicit operator MyList<T>(ArrayList target){
    MyList<T> newList = new MyList<T>();

    foreach(T item in target){
        newList.Add(item);
    }
    return newList;
  }
}

public class Test{

  public static void GetReadyForBattle(MyList<Transformer> robots){
    foreach(Transformer bot in robots){
        if(!bot.InRobotMode){
                bot.Transform();
            }
        }   
  }

  public static void Main(string[] args){

    Autobot OptimusPrime = new Autobot();
    ArrayList autobots = new ArrayList(1);
    autobots.Add(OptimusPrime);

    Decepticon Megatron = new Decepticon();
    ArrayList decepticons = new ArrayList(1);
    decepticons.Add(Megatron);

    GetReadyForBattle(decepticons);
    GetReadyForBattle(autobots);
  }
}

DOESN'T WORK - MyList<subtype of T> implicitly casted to MyList<T> via user-defined cast

using System;
using Cybertron.Transformers;


public class MyList<T>: List<T>{

  public static implicit operator MyList<T>(MyList<U> target) where U:T{
    MyList<T> newList = new MyList<T>();

    foreach(T item in target){
        newList.Add(item);
    }
    return newList;
  }

}

public class Test{

  public static void GetReadyForBattle(MyList<Transformer> robots){
    foreach(Transformer bot in robots){
        if(!bot.InRobotMode)
            bot.Transform();
    }
  }

  public static void Main(string[] args){

   
Autobot OptimusPrime = new Autobot();
    MyList<Autobot> autobots = new MyList<Autobot>(1);
    autobots.Add(OptimusPrime);

    Decepticon Megatron = new Decepticon();
    MyList<Decepticon> decepticons = new MyList<Decepticon>(1);
    decepticons[0] = Megatron;

    GetReadyForBattle(decepticons);
    GetReadyForBattle(autobots);

  }
}

I really wanted that last bit of code to work because it would have been quite a non-intrusive fix for the problem (ignoring the fact that I have to use my own subclasses of the .NET Framework's collection classes). At the end of the day I ended up creating a TypeConverter utility class which contains some of the dumbest code I've had to write to trick a compiler into doing the right thing, here's what it ended up looking like

WORKS - Create a TypeConverter class that encapsulates calls to List.ConvertAll

using System;
using Cybertron.Transformers;


public class TypeConverter{

  public static List<Transformer> ToTransformerList<T>(List<T> target) where T: Transformer{
    return target.ConvertAll(new Converter<T,Transformer>(MakeTransformer));
  }

  public static Transformer
MakeTransformer<T>(T target) where T:Transformer{
    return target;
/* greatest conversion code ever!!!! */
  }

}

public class Test{

public static void GetReadyForBattle(List<Transformer> robots){
    foreach(Transformer bot in robots){
        if(!bot.InRobotMode)
            bot.Transform();
        }
    }
 }

 public static void Main(string[] args){

    Autobot OptimusPrime = new Autobot();
    List<Autobot> autobots = new List<Autobot>(1);
    autobots.Add(OptimusPrime);

    Decepticon Megatron = new Decepticon();
    List<Decepticon> decepticons = new List<Decepticon>(1);
    decepticons.Add(Megatron);

    GetReadyForBattle(TypeConverter.ToTransformerList(decepticons));
    GetReadyForBattle(TypeConverter.ToTransformerList(autobots));

 }

}

This works but it's ugly as sin. Anybody got any better ideas?

UPDATE: Lot's of great suggestions in the comments. Since I don't want to go ahead and modify a huge chunk of methods across our code base, I suspect I'll continue with the TypeConverter model. However John Spurlock pointed out that it is much smarter to implement the TypeConverter using generics for both input and output parameters instead of way I hacked it together last night. So our code will look more like

using System;
using Cybertron.Transformers;


public class TypeConverter{

 	/// <summary>
/// Returns a delegate that can be used to cast a subtype back to its base type.
/// </summary>
/// <typeparam name="T">The derived type</typeparam>
/// <typeparam name="U">The base type</typeparam>
/// <returns>Delegate that can be used to cast a subtype back to its base type. </returns>
public static Converter<T, U> UpCast<T, U>() where T : U {
return delegate(T item) { return (U)item; };
}

}


public class Test{

public static void GetReadyForBattle(List<Transformer> robots){
    foreach(Transformer bot in robots){
        if(!bot.InRobotMode)
            bot.Transform();
        }
    }
 }

 public static void Main(string[] args){

    Autobot OptimusPrime = new Autobot();
    List<Autobot> autobots = new List<Autobot>(1);
    autobots.Add(OptimusPrime);

    Decepticon Megatron = new Decepticon();
    List<Decepticon> decepticons = new List<Decepticon>(1);
    decepticons.Add(Megatron);

    GetReadyForBattle(decepticons
.ConvertAll(TypeConverter.UpCast<Decepticon, Transformer>()));
    GetReadyForBattle(autobots.ConvertAll(TypeConverter.UpCast<Autobot, Transformer>()));

 }

}


 

Thursday, August 09, 2007 12:25:21 PM (GMT Daylight Time, UTC+01:00)
Another alternative is to define your own list class in terms of a base IList<>. Then you could create a strongly typed list while still maintaining the ability to use the base interface.

The downside is that you have to specify up-front which base classes you might be casting to.

I emailed you the code for the class as this form won't let me post it here.
Oren Novotny
Thursday, August 09, 2007 12:38:22 PM (GMT Daylight Time, UTC+01:00)
Another possibility is to make the receiver method a generic method:

public static void GetReadyForBattle{T}(List{T} robots)
where T: Transformer

( {} = angle brackets )

Thursday, August 09, 2007 12:46:11 PM (GMT Daylight Time, UTC+01:00)
There ya go, you have to be quick to be helpful. I'm can only second John's comment. If I'm not completely wrong C# 2.0's compiler should be able to infer the type of T when you call the generic method, such that the actual code calling the method doesn't even look different.
Thursday, August 09, 2007 2:11:59 PM (GMT Daylight Time, UTC+01:00)
IronPython.

I'm going through the same growing pains in Java, having just jumped the shark to move to Java 1.5. What a pain. I find myself just not even bothering to use the generics at all. The occasional cast is easier to deal with.
Thursday, August 09, 2007 2:41:20 PM (GMT Daylight Time, UTC+01:00)
Oren,
I have two issues with your solution. (i) At the time of declaring the list of objects, I have to know that I will need to cast its contents and what subtypes I plan to cast its contents (ii) it breaks if I have more than one step in my derivation tree (e.g. in RssBandit we have SearchHitNewsItem which is a subtype of NewsItem which is a subtype of RelationBase)

John,
I prefer your solution to Oren's but it means that I pretty much need to change the signature of every method we have or will ever have which manipulates a list of objects in case we one day add a subtype to that object. This also seems like a cognitive price to pay. Then there's the aesthetic gripe that all our method calls are now longer and uglier in every case not just when we have to do a cast.
Thursday, August 09, 2007 3:08:24 PM (GMT Daylight Time, UTC+01:00)
John,
That said. Your approach is a lot cleaner and more flexible than my TypeConverter hack. Thanks for suggesting it.
Thursday, August 09, 2007 3:34:26 PM (GMT Daylight Time, UTC+01:00)
A pedantic point: v3.5 of the .NET Framework is at Beta 2 now. It was released on 26-July.
Thursday, August 09, 2007 3:51:46 PM (GMT Daylight Time, UTC+01:00)
"This also seems like a cognitive price to pay."

Obviously you have not worked with the LINQ api :)

(To be fair, the java 1.5 generic collections api is also plagued with such type-constraint headaches)

I agree though, you want to keep these generic astronautics limited to internal apis, and use simple types for any exposed surface area.

Back to your example, if you are already willing to create a new list, you can use a "converter-creator" fn (not dissimilar to your type-converter approach):

private static Converter{TInput, TOutput} Cast{TInput, TOutput}()
where TInput : TOutput
{
return delegate(TInput item)
{
return (TOutput)item;
};
}
GetReadyForBattle(autobots.ConvertAll(Cast{Autobot,Transformer}()));
GetReadyForBattle(decepticons.ConvertAll(Cast{Decepticon,Transformer}()));


The caller incurs significant cognitive cost either way. The price we pay for static typing...
Thursday, August 09, 2007 4:36:34 PM (GMT Daylight Time, UTC+01:00)
"Then there's the aesthetic gripe that all our method calls are now longer and uglier in every case not just when we have to do a cast."

Not necessarily. The C# 2.0 compiler can infer the generic parameter of a method from its arguments. If you had a method (assume angle brackets in place of curly brackets):

public static void GetReadyForBattle{T}(List{T} robots)
where T: Transformer

The following is valid:

List{Autobot} aList = new List{Autobot}();
GetReadyForBattle(aList);

List{Decepticon} dList = new List{Decepticon}();
GetReadyForBattle(dList);

You do not have to incur the aesthetic overhead of including the generic type parameter on every call to GetReadyForBattle.
Timothy Fries
Thursday, August 09, 2007 5:23:51 PM (GMT Daylight Time, UTC+01:00)
Timothy's spot-on with this. If the GetReadyForBattle method picks up a little generic parametricity itself, then the problem pretty much disappears (the type inference works in Mono, too!).

I think this is a great example of the effort required to work generics into one's coding practices. A half-way effort (such as just using the generic collection classes) can sometimes end up more limiting than the bad old days. What remains frustrating is that, from the programmer's point of view, the generic version of a function like GetReadyForBattle is achieving the exact same thing as the old covariant method, just with more code and a less-direct type annotation (the expected type, Transformer, of the parameter is now off in a where clause).
Wednesday, August 15, 2007 10:58:57 PM (GMT Daylight Time, UTC+01:00)
The proper type relationship from type theory would be:

List&lt;X&gt; is-a ReadOnlyList&lt;X&gt; and also is-a WriteOnlyList&lt;X&gt;

If B extends A, then List&lt;B&gt; is NOT compatible with List&lt;A&gt; (and array[B] shouldn't be compatible with array[A] either!), and the example you gave explains why. However, ReadOnlyList&lt;B&gt; is-a ReadOnlyList&lt;A&gt;.

Since getReadyForBattle doesn't modify the list, it would take ReadOnlyList&lt;Transformer&gt;. Passing in List&lt;Autobot&gt; or List&lt;Decepticon&gt; would be fine.

The interesting bit is WriteOnlyList. If you only add to a list, then WriteOnlyList&lt;A&gt; is-a WriteOnlyList&lt;B&gt;. Note that this is backwards from what you might expect, but it works out: if you have a List&lt;Decepticon&gt; then you can pass it to a function that takes WriteOnlyList&lt;Autobot&gt;, and that function can add autobots to the list without causing any type errors.

Since List has both read and write methods, it needs to work in both directions: List&lt;B&gt; is-a List&lt;A&gt; if B is-a A (for reading) and A is-a B (for writing). This only happens when A and B are the same thing, which is why you can't pass lists around like you'd like. But I think you'll find that in all the cases you want to do this, you only want to read from the list. Having a write-only list interface is probably silly but having a read-only interface in C# (or Java) would solve the type problem.
Wednesday, August 15, 2007 11:00:55 PM (GMT Daylight Time, UTC+01:00)
Ugh, sorry, my comment is formatted badly because I couldn't figure out how to insert angle brackets properly. :( If I put them in directly then the web site complains that I'm writing HTML; if I put in entities then they show up raw.
Comments are closed.