How does the c# language prevent generics from being covarient unless they contain no methods that require T as an input?

Question

I have been reading up on the changes that .NET4.5 will bring, and on this blog post I stumbled upon something I neither knew nor understood.

When talking about the implementation of readonly collections, Immo Landwerth says:

Unfortunately, our type system doesn’t allow making types of T covariant unless it has no methods that take T as an input. Therefore, we can’t add an IndexOf method to IReadOnlyList. We believe this is a small sacrifice compared to not having support for covariance.

From my obviously limited understanding, it seems like he is saying that in order to enable us to call a method that requires an IReadOnlyList<Shape> by passing in a IReadOnlyList<Circle>, we can't have a IReadOnlyList<T>.IndexOf(T someShape) method.

I don't see how the type system would prevent that. Can someone explain?

Answer 1

Suppose Circle implements IEquatable<Circle>. That would naturally be used by IReadOnlyList<Circle>.IndexOf if it were available. Now if you could write this:

IReadOnlyList<Circle> circles = ...;
IReadOnlyList<Shape> shapes = circles;
int index = shapes.IndexOf(new Square(10));

that would end up trying to pass a Square to Circle.Equals(Circle) which would clearly be a bad idea.

The rules which enforce the "no values of T in input positions" are in section 13.1.3 of the C# 4 spec. You should also read Eric Lippert's blog series on generic variance for a lot more details.

Answer 2

Since IReadOnlyList<T> is covariant, you can cast it to any supertype of T and all methods should still work according to the contract. The most super supertype of T is Object, so if IndexOf were part of the interface, it should have accepted Object.

As Jon Skeet states, in a list of Circle objects, you can then ask: what is the index of a particular Square in this list? The only correct response would be "it is not here," and IndexOf should return -1 and not throw an exception.

So, I don't agree with Jon Skeet. Given the limitations of covariant generic parameters, and similar to ArrayList.indexOf in Java, the BCL team should have included a method IndexOf with the following signature:

int IndexOf(object item);

Exactly the same argument applies to Contains in IReadOnlyCollection: when you pass in an object of an incompatible type, the collection obviously doesn't contain it and the method should just return false.

The only downside would be boxing of value types, but actual implementation can still hide the IReadOnlyList.IndexOf method and provide their own generic overload, making this argument moot.

So, you are correct in expecting IndexOf to return -1 when passed an incompatible object, if it were on the interface.

---

I implemented this principle in my M42.Collections library to show how this would work in practice. You can download it here:

M42 Collections - Portable .NET library for working with collections properly.

Answer 3

Note that it would be correct, in theory (not sure if that is implemented in .NET yet), to define IndexOf for all subtypes of T:

class ReadOnlyList<+T> = { ...
  Int IndexOf<U>(U elem) where T : U { ... }
}

It is interesting to see why IndexOf(T elem) would not obviously be covariant, while this one is: if you have T2 : T1, a method IndexOf(T1 elem) may not be compatible with the signature IndexOf(T2 elem). On the contrary, if you have IndexOf<U>(U elem) where T1 : U, you know that T2 : T1 and T1 : U, so you also have T2 : U for all such U: this type is a subtyping of IndexOf<U>(U elem) with T2 : U.

This remark is made, for example, in the 2006 article Variance and Generalized Constraints for C# Generics by Emir, Kennedy, Russo and Yu: they present a type system that would accept this definition.