Tuesday, April 13, 2010

C# 4.0: Covariance And Contravariance In Generics

by Paulo Morgado via Paulo Morgado : C# on 4/13/2010 1:25:58 AM

C# 4.0 (and .NET 4.0) introduced covariance and contravariance to generic interfaces and delegates. But what is this variance thing?

According to Wikipedia, in multilinear algebra and tensor analysis, covariance and contravariance describe how the quantitative description of certain geometrical or physical entities changes when passing from one coordinate system to another.^(*)

But what does this have to do with C# or .NET?

In type theory, a the type T is greater (>) than type S if S is a subtype (derives from) T, which means that there is a quantitative description for types in a type hierarchy.

So, how does covariance and contravariance apply to C# (and .NET) generic types?

In C# (and .NET), variance is a relation between a generic type definition and a particular generic type parameter.

Given two types Base and Derived, such that:

• There is a reference (or identity) conversion between Base and Derived
• Base = Derived

A generic type definition Generic<T> is:

• covariant in T if the ordering of the constructed types follows the ordering of the generic type parameters: Generic<Base> = Generic<Derived>.
• contravariant in T if the ordering of the constructed types is reversed from the ordering of the generic type parameters: Generic<Base> = Generic<Derived>.
• invariant in T if neither of the above apply.

If this definition is applied to arrays, we can see that arrays have always been covariant in relation to the type of the elements because this is valid code:

object[] objectArray = new string[] { "string 1", "string 2" };
objectArray[0] = "string 3";
objectArray[1] = new object();

However, when we try to run this code, the second assignment will throw an ArrayTypeMismatchException. Although the compiler was fooled into thinking this was valid code because an object is being assigned to an element of an array of object, at run time, there is always a type check to guarantee that the runtime type of the definition of the elements of the array is greater or equal to the instance being assigned to the element. In the above example, because the runtime type of the array is array of string, the first assignment of array elements is valid because string = string and the second is invalid because string = object.

This leads to the conclusion that, although arrays have always been covariant in relation to the type of the elements, they are not safely covariant – code that compiles is not guaranteed to run without errors.

In C#, variance is enforced in the declaration of the type and not determined by the usage of each the generic type parameter.

Covariance in relation to a particular generic type parameter is enforced, is using the out generic modifier:

public interface IEnumerable<out T>
{
    IEnumerator<T> GetEnumerator();
}

public interface IEnumerator<out T>
{
    T Current { get; }
    bool MoveNext();
}

Notice the convenient use the pre-existing out keyword. Besides the benefit of not having to remember a new hypothetic covariant keyword, out is easier to remember because it defines that the generic type parameter can only appear in output positions — read-only properties and method return values.

In a similar way, the way contravariance is enforced in relation a particular generic type parameter, is using the in generic modifier:

public interface IComparer<in T>
{
    int Compare(T x, T y);
}

Once again, the use of the pre-existing in keyword makes it easier to remember that the generic type parameter can only be used in input positions — write-only properties and method non ref and non out parameters.

A generic type parameter that is not marked covariant (out) or contravariant (in) is invariant.

Because covariance and contravariance applies to the relation between a generic type definition and a particular generic type parameter, a generic type definition can be both covariant, contravariant and invariant depending on the generic type parameter.

public delegate TResult Func<in T, out TResult>(T arg);

In the above delegate definition, Func<T, TResult> is contravariant in T and convariant in TResult.

All the types in the .NET Framework where variance could be applied to its generic type parameters have been modified to take advantage of this new feature.

In summary, the rules for variance in C# (and .NET) are:

• Variance in relation to generic type parameters is restricted to generic interface and generic delegate type definitions.
• A generic interface or generic delegate type definition can be covariant, contravariant or invariant in relation to different generic type parameters.
• Variance applies only to reference types: a IEnumerable<int> is not an IEnumerable<object>.
• Variance does not apply to delegate combination. That is, given two delegates of types Action<Derived> and Action<Base>, you cannot combine the second delegate with the first although the result would be type safe. Variance allows the second delegate to be assigned to a variable of type Action<Derived>, but delegates can combine only if their types match exactly.

If you want to learn more about variance in C# (and .NET), you can always read:

• Covariance and Contravariance in Generics — MSDN Library
• Exact rules for variance validity — Eric Lippert
• Events get a little overhaul in C# 4, Afterward: Effective Events — Chris Burrows

Note: Because variance is a feature of .NET 4.0 and not only of C# 4.0, all this also applies to Visual Basic 10.