Many Questions: Generics Variance

One of the main benefits of the addition of generics to C# is the ability to easily create strongly typed collections using types in the System.Collections.Generics namespace. For example, you can create a variable of type List<int>, and the compiler will check all accesses to the variable – ensuring that only ints are added to the collection. This is a big usability improvement over the untyped collections available in version 1 of C#.

 

Unfortunately, strongly typed collections have drawbacks of their own. For example, suppose you have a strongly typed List<object> and you want to append all the elements from a List<int> to your List<object>. You would like to be able to write code like this:

 

            List<int> ints = new List<int>();

            ints.Add(1);

            ints.Add(10);

            ints.Add(42);

            List<object> objects = new List<object>();

            // doesn’t compile ‘ints’ is not a IEnumerable<object>

            objects.AddRange(ints);

 

In this case, you would like to treat a List<int> which is also an IEnumerable<int>, as an IEnumerable<object>. This seems like a reasonable thing to do – as int is convertible to object. It is very similar to being able to treat a string[] as an object[] as you can do today. If you find yourself in this situation, the feature you are looking for is called generics variance – treating an instantiation of a generic type (in this case IEnumerable<int>) as a different instantiation of that same type(in this case IEnumerable<object>).

 

C# doesn’t support variance for generic types, so when encountering cases like this you will need to find a workaround in your code. If you do encounter this kind of problem, there are a couple of techniques you can use to workaround the problem. For the simplest cases, like the case of a single method like AddRange in the example above, you can declare a simple helper method to do the conversion for you. For example, you could write this method:

 

    // Simple workaround for single method

    // Variance in one direction only

    public static void Add<S, D>(List<S> source, List<D> destination)

        where S : D

    {

        foreach (S sourceElement in source)

            destination.Add(sourceElement);

    }

    ...

    // does compile

    Add<int, object>(ints, objects);

 

This example shows the some characteristics of a simple variance workaround. The helper method takes 2 type parameters, for the source and destination, and the source type parameter S has a constraint which is the destination type parameter D. This means that the List<> being read from must contain elements which are convertible to the element type of the List<> being inserted into. This allows the compiler to enforce that int is convertible to object. Constraining a type parameter to derive from another type parameter is called a ‘naked type parameter constraint’.

 

Defining a single method to workaround variance problems is not too bad. Unfortunately variance issues can become quite complex quite quickly. The next level of complexity is when you want to treat an interface of one instantiation as an interface of another instantiation. For example, you have an IEnumerable<int>, and you want to pass it to a method which only takes an IEnumerable<object>. Again, this makes some sense because you can think of an IEnumerable<object> as a sequence of objects, and an IEnumerable<int> is a sequence of ints. Since ints are objects, a sequence of ints should be treatable as a sequence of objects. For example:

 

        static void PrintObjects(IEnumerable<object> objects)

        {

            foreach (object o in objects)

                Console.WriteLine(o);

        }

        ...

        List<int> ints = new List<int>();

        // would like to do this, but can’t ...

        // ... ints is not an IEnumerable<object>

        PrintObjects(ints);

 

The workaround for the interface case, is to create a wrapper object which does the conversions for each member of the interface. This would look something like this:

 

    // Workaround for interface

    // Variance in one direction only so type expressinos are natural

    public static IEnumerable<D> Convert<S, D>(IEnumerable<S> source)

        where S : D

    {

        return new EnumerableWrapper<S, D>(source);

    }

    private class EnumerableWrapper<S, D> : IEnumerable<D>

        where S : D

    {

        ...

    }

    ...

    List<int> ints = new List<int>();

    // would like to do this, but can’t ...

    // ... ints is not an IEnumerable<object>

    PrintObjects(Convert<int, object>(ints));

 

Again, notice the ‘naked type parameter constraint’ on the wrapper class and helper method. This machinery is getting pretty complicated, but the code in the wrapper class is pretty straightforward – it just delegates to the members of the wrapped interface doing nothing more than straightforward type conversions along the way. Why not have the compiler allow the conversion from IEnumerable<int> to IEnumerable<object> directly?

 

Although variance is type safe in the case where you are looking at read only views of your collections, variance is not type safe in the case where both read and write operations are involved. For example, the IList<> interface could not be dealt with in this automatic way. You can still write a helper which will wrap all read operations on an IList<> in a type safe manner, but wrapping of write operations cannot be done so simply.

 

Here’s part of a wrapper for dealing with variance on the IList<T> interface which shows the problems that arise with variance in both the read and write directions:

 

    private class ListWrapper<S, D> : CollectionWrapper<S, D>, IList<D>

        where S : D

    {

        public ListWrapper(IList<S> source) : base(source)

        {

            this.source = source;

        }

        public void Insert(int index, D item)

        {

            if (item is S)

                this.source.Insert(index, (S)item);

            else

                throw new Exception("Invalid type exception");

        }

       

        public int IndexOf(D item)

        {

  if (item is S)

                return this.source.IndexOf((S) item);

            else

                return -1;

        }

 

The Insert method on the wrapper has a problem – it takes as an argument a D, but it must insert it into an IList<S>. Since D is a base type of S, not all D’s are S’s, so the Insert operation may fail. This example has an analogue with variance with arrays. When inserting an object into an object[], a dynamic type check is performed because the object[] may in fact be a string[] at runtime. For example:

 

            object[] objects = new string[10];

            // no problem, adding a string to a string[]

            objects[0] = "hello";

            // runtime exception, adding an object to a string[]

            objects[1] = new object();

 

Back to our IList<> example, the wrapper for the Insert method can simply throw when the actual type doesn’t match the desired type at runtime. So again, you could imagine that the compiler would automatically generate the wrapper for the programmer. There are cases where this policy isn’t the right thing to do however. The IndexOf method searches the collection for the item provided, and returns the index in the collection if the item is found. However, if the item is not found, the IndexOf method simply returns -1, it doesn’t throw. This kind of wrapping cannot be provided by an automatically generated wrapper.

 

So far we’ve seen the two simplest workarounds for generic variance issues. However, variance issues can get arbitrarily complex – for example treating a List<IEnumerable<int>> as a List<IEnumerable<object>>, or treating a List<IEnumerable<IEnumerable<int>>> as a List<IEnumerable<IEnumerable<object>>>.

 

Generating these wrappers to work around variance problems in your code can introduce a significant overhead in your code. Also, it can introduce referential identity issues, as each wrapper does not have the same identity as the original collection which can lead to subtle bugs. When using generics, you should choose your type instantiation to reduce mismatches between components which are tightly coupled. This may require some compromises in the design of your code. As always, design involves tradeoffs between conflicting requirements, and the constraints of the types system in the language should be considered in your design process.

 

There are type systems which include generic variance as a first class part of the language. Eiffel is the prime example of this. However, including generics variance as a first class part of the type system would dramatically increase the complexity of the type system of C#, even in relatively straightforward scenarios which don’t involve variance. As a result, the C# designers felt that not including variance was the right choice for C#.

 

Here’s the full source code for the examples discussed above.

 

 

using System;

using System.Collections.Generic;

using System.Text;

using System.Collections;

static class VarianceWorkaround

{

    // Simple workaround for single method

    // Variance in one direction only

    public static void Add<S, D>(List<S> source, List<D> destination)

        where S : D

    {

        foreach (S sourceElement in source)

            destination.Add(sourceElement);

    }

    // Workaround for interface

    // Variance in one direction only so type expressinos are natural

    public static IEnumerable<D> Convert<S, D>(IEnumerable<S> source)

        where S : D

    {

        return new EnumerableWrapper<S, D>(source);

    }

    private class EnumerableWrapper<S, D> : IEnumerable<D>

        where S : D

    {

        public EnumerableWrapper(IEnumerable<S> source)

        {

            this.source = source;

        }

        public IEnumerator<D> GetEnumerator()

        {

            return new EnumeratorWrapper(this.source.GetEnumerator());

        }

        IEnumerator System.Collections.IEnumerable.GetEnumerator()

        {

            return this.GetEnumerator();

        }

        private class EnumeratorWrapper : IEnumerator<D>

        {

            public EnumeratorWrapper(IEnumerator<S> source)

            {

                this.source = source;

            }

            private IEnumerator<S> source;

            public D Current

            {

                get { return this.source.Current; }

            }

            public void Dispose()

            {

                this.source.Dispose();

            }

            object IEnumerator.Current

            {

                get { return this.source.Current; }

            }

            public bool MoveNext()

            {

                return this.source.MoveNext();

            }

            public void Reset()

            {

                this.source.Reset();

            }

        }

        private IEnumerable<S> source;

    }

    // Workaround for interface

    // Variance in both directions, causes issues

    // similar to existing array variance

    public static ICollection<D> Convert<S, D>(ICollection<S> source)

        where S : D

    {

        return new CollectionWrapper<S, D>(source);

    }

    private class CollectionWrapper<S, D>

        : EnumerableWrapper<S, D>, ICollection<D>

        where S : D

    {

        public CollectionWrapper(ICollection<S> source)

            : base(source)

        {

        }

        // variance going the wrong way ...

    // ... can yield exceptions at runtime

        public void Add(D item)

        {

            if (item is S)

                this.source.Add((S)item);

            else

                throw new Exception(@"Type mismatch exception, due to type hole introduced by variance.");

        }

        public void Clear()

        {

            this.source.Clear();

        }

        // variance going the wrong way ...

        // ... but the semantics of the method yields reasonable

        // semantics

        public bool Contains(D item)

        {

            if (item is S)

                return this.source.Contains((S)item);

            else

                return false;

        }

        // variance going the right way ...

        public void CopyTo(D[] array, int arrayIndex)

        {

            foreach (S src in this.source)

                array[arrayIndex++] = src;

        }

        public int Count

        {

            get { return this.source.Count; }

        }

        public bool IsReadOnly

       {

            get { return this.source.IsReadOnly; }

        }

        // variance going the wrong way ...

        // ... but the semantics of the method yields reasonable

        // semantics

        public bool Remove(D item)

        {

            if (item is S)

                return this.source.Remove((S)item);

            else

                return false;

        }

       

        private ICollection<S> source;

    }

    // Workaround for interface

    // Variance in both directions, causes issues

    // similar to existing array variance

    public static IList<D> Convert<S, D>(IList<S> source)

        where S : D

    {

        return new ListWrapper<S, D>(source);

    }

    private class ListWrapper<S, D> : CollectionWrapper<S, D>, IList<D>

   where S : D

    {

        public ListWrapper(IList<S> source) : base(source)

        {

            this.source = source;

        }

       

        public int IndexOf(D item)

        {

            if (item is S)

                return this.source.IndexOf((S) item);

            else

                return -1;

        }

        // variance the wrong way ...

        // ... can throw exceptions at runtime

        public void Insert(int index, D item)

        {

            if (item is S)

                this.source.Insert(index, (S)item);

            else

                throw new Exception("Invalid type exception");

        }

        public void RemoveAt(int index)

        {

            this.source.RemoveAt(index);

        }

        public D this[int index]

        {

            get

            {

                return this.source[index];

            }

            set

            {

                if (value is S)

                    this.source[index] = (S)value;

                else

                    throw new Exception("Invalid type exception.");

            }

        }

       

        private IList<S> source;

    }

}

namespace GenericVariance

{

    class Program

    {

        static void PrintObjects(IEnumerable<object> objects)

        {

          foreach (object o in objects)

                Console.WriteLine(o);

        }

       

        static void AddToObjects(IList<object> objects)

        {

            // this will fail if the collection provided is a

            // wrapped collection

    objects.Add(new object());

        }

        static void Main(string[] args)

        {

            List<int> ints = new List<int>();

            ints.Add(1);

            ints.Add(10);

            ints.Add(42);

            List<object> objects = new List<object>();

            VarianceWorkaround.Add<int, object>(ints, objects);

            PrintObjects(VarianceWorkaround

                .Convert<int, object>(ints));

            AddToObjects(objects); // this works fine

            AddToObjects(VarianceWorkaround

                .Convert<int, object>(ints));

        }

        static void ArrayExample()

        {

            object[] objects = new string[10];

            // no problem, adding a string to a string[]

            objects[0] = "hello";

   // runtime exception, adding an object to a string[]

            objects[1] = new object();

        }

    }

}

Comments

• Anonymous
  July 29, 2005
  Why would generic variance add too much complexity to C#, when IL already supports it.
• Anonymous
  July 29, 2005
  It's a Microsoft fault !!
  
  You was able to add additional methods something like this:
  
  class List<TItem> {
  void AddRange<TOther>(List<TOther> list) where TOther: TItem {
  }
  }
  
• Anonymous
  July 30, 2005
  In my opinion C# team should keep C# as the static/ type safe language and avoid adding too much difficult to understand new concepts or ones that would cause even more run-time surprises. However I would like to see these more advanced features in C# like language also. My suggestion is that you allow developers to use advanced C# features only in files that have, for example, extension .csa or .cs3 etc. So if developer needed these features that might cause more dynamic behaviour for example, they could use them in C# project but if a second person (maintenance programmer?) came to take over the project, he would notice from the extension immediately that there may be advanced concepts used in the code that you need to learn first.
• Anonymous
  July 31, 2005
  Blog link of the week 30
• Anonymous
  August 08, 2005
  Your argument type validation code "item is S" is flawed.
  It return False for null-reference values - but this is legal for interface contracts you are defining !
• Anonymous
  August 10, 2005
  Good catch TAG, you are correct. The checks for item is S, should also permit null.
  
  Peter
• Anonymous
  April 21, 2009
  PingBack from http://tour-eiffel.linkedz.info/2005/07/29/many-questions-generics-variance/