A contravariance conundrum - Muhammad Rizwan

Suppose we have my usual hierarchy of types, Animal, Giraffe, etc, with the obvious type relationships. An IEqualityComparer<T> is contravariant in its type parameter; if we have a device which can compare two Animals for equality then it can compare two Giraffes for equality as well. So why does this code fail to compile?

IEqualityComparer<Animal> animalComparer = whatever;
IEnumerable<Giraffe> giraffes = whatever;
IEnumerable<Giraffe> distinct = giraffes.Distinct(animalComparer);

This illustrates a subtle and slightly unfortunate design choice in the method type inference algorithm, which of course was designed long before covariance and contravariance were added to the language.

Let's take a look at the signature of the Distinct extension method that was used above:

public static IEnumerable<T> Distinct<T>(
  this IEnumerable<T> source,
  IEqualityComparer<T> comparer)

Type inference computes a set of bounds on what T can be based on an analysis of each argument and its corresponding formal parameter type. For the first argument, since IEnumerable<T> is a covariant interface, the type inference algorithm computes that T must be Giraffe or any larger type.¹ The specification expresses this notion by saying that Giraffe is a "lower bound" -- whatever is finally chosen has to be a type that is not smaller than Giraffe.
For the second argument, since IEqualityComparer<T> is a contravariant interface, the type inference algorithm concludes that T must be Animal or any smaller type. This is an "upper bound" -- T has to be a type that is not larger than Animal.
Given these two bounds, what type should actually be inferred for T? One of the design rules of C# that I have mentioned many times on this blog is that when given a set of types to choose from, C# always chooses one of those types rather than making up a type that is not in the set. So we know that we are going to choose either Animal or Giraffe and not some third type which satisfies the constraints, like Mammal. But which? Both types satisfy the bounds! Both Animal and Giraffe are not smaller than Giraffe, and both are not larger than Animal.
When faced with this situation the type inference algorithm chooses the larger of the types, so T is inferred to be Animal. Thus we have:

public static IEnumerable<Animal> Distinct<Animal>( 
  this IEnumerable<Animal> source, 
  IEqualityComparer<Animal> comparer)

and since the method returns IEnumerable<Animal>, it cannot be assigned to a variable of type IEnumerable<Giraffe>.
You would be forgiven for expecting Giraffe to be chosen because that's what the spec says:

If among the remaining candidate types U_j there is a unique type V from which there is an implicit conversion to all the other candidate types, then X_i is fixed to V.

That's a long-standing typo that has never been fixed in the spec; the intended wording was "to which", not "from which".
It might seem strange to choose the larger type here; why not choose the more specific type if you can? We designed the type inference algorithm for C# 3, which did not have covariance or contravariance² and so it was a bit of a moot point; the spec said that in the unlikely event of a conflict, choose the larger type. When C# 4 came along and added contravariance I made the case that we ought to choose the more specific type, because now there were scenarios where it actually might work, but we ultimately decided to stick with the existing algorithm. We then promptly wrote that algorithm down wrong in the spec. Whoops.
In any event, this is a small problem. If it hurts when you do that then simply change the type of the comparer:

IEqualityComparer<Animal> animalComparer = whatever;
// Legal thanks to contravariance:
IEqualityComparer<Giraffe> giraffeComparer = animalComparer; 
IEnumerable<Giraffe> giraffes = whatever;
IEnumerable<Giraffe> distinct = giraffes.Distinct(giraffeComparer);

And now there is no conflict; the bounds inferred are an upper bound of Giraffe and a lower bound of Giraffe, so there's only one to choose from.

Recall that when I say that one type is larger than another, I mean that there is an implicit conversion from the smaller type to the larger type. Animal is a larger type than Giraffe because all Giraffes are Animals, but some Animals are not Giraffes. There are more Animals than Giraffes, so Animal is the larger type.
Except for array type covariance.