List.Contains and T[].Contains behaving differently

Question

Say I have this class:

public class Animal : IEquatable<Animal>
{
    public string Name { get; set; }

    public bool Equals(Animal other)
    {
        return Name.Equals(other.Name);
    }
    public override bool Equals(object obj)
    {
        return Equals((Animal)obj);
    }
    public override int GetHashCode()
    {
        return Name == null ? 0 : Name.GetHashCode();
    }
}

This is the test:

var animals = new[] { new Animal { Name = "Fred" } };

Now, when I do:

animals.ToList().Contains(new Animal { Name = "Fred" }); 

it calls the right generic Equals overload. The problem is with array types. Suppose I do:

animals.Contains(new Animal { Name = "Fred" });

it calls non generic Equals method. Actually T[] doesn't expose ICollection<T>.Contains method. In the above case IEnumerable<Animal>.Contains extension overload is called which in turn calls the ICollection<T>.Contains. Here is how IEnumerable<T>.Containsis implemented:

public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value)
{
    ICollection<TSource> collection = source as ICollection<TSource>;
    if (collection != null)
    {
        return collection.Contains(value); //this is where it gets done for arrays
    }
    return source.Contains(value, null);
}

So my questions are:

1. Why should List<T>.Contains and T[].Contains behave differently? In other words, why is former calling the generic Equals and the latter non-generic Equals even though both the collections are generic?
2. Is there a way I can see T[].Contains implementation?

Edit: Why does it matter or why am I asking this:

1. It trips one up in case she forgets to override non generic Equals when implementing IEquatable<T> in which case calls like T[].Contains does a referential equality check. Especially when she expects all generic collections to operate on generic Equals.

2. You lose all the benefits of implementing IEquatable<T> (even though it isn't a disaster for reference types).

3. As noted in comments, just interested in knowing the internal details and design choices. There is no other generic situation I can think of where the non generic Equals will be preferred, be it any List<T> or set based (Dictionary<K,V> etc) operations. Even worse, had Animal been a struct, Animal[].Contains calls the generic Equals, all which makes T[] implementation kinda strange, something developers ought to know.

Note: The generic version of Equals is called only when the class implements IEquatable<T>. If the class doesn't implement IEquatable<T>, non-generic overload of Equals is called irrespective of whether it is called by List<T>.Contains or T[].Contains.

Answer 1

Arrays do not implement IList<T> because they can be multidimensional and non-zero based.

However at runtime single-dimensional arrays that have a lower bound of zero automatically implement IList<T> and some other generic interfaces. The purpose of this runtime hack is elaborated below in 2 quotes.

Here http://msdn.microsoft.com/en-us/library/vstudio/ms228502.aspx it says:

In C# 2.0 and later, single-dimensional arrays that have a lower bound of zero automatically implement IList<T>. This enables you to create generic methods that can use the same code to iterate through arrays and other collection types. This technique is primarily useful for reading data in collections. The IList<T> interface cannot be used to add or remove elements from an array. An exception will be thrown if you try to call an IList<T> method such as RemoveAt on an array in this context.

Jeffrey Richter in his book says:

The CLR team didn’t want System.Array to implement IEnumerable<T>, ICollection<T>, and IList<T>, though, because of issues related to multi-dimensional arrays and non-zero–based arrays. Defining these interfaces on System.Array would have enabled these interfaces for all array types. Instead, the CLR performs a little trick: when a single-dimensional, zero–lower bound array type is created, the CLR automatically makes the array type implement IEnumerable<T>, ICollection<T>, and IList<T> (where T is the array’s element type) and also implements the three interfaces for all of the array type’s base types as long as they are reference types.

Digging deeper, SZArrayHelper is the class that provides this "hacky" IList implementations for Single dimention Zero based arrays.

Here is the Class description:

//----------------------------------------------------------------------------------------
// ! READ THIS BEFORE YOU WORK ON THIS CLASS.
// 
// The methods on this class must be written VERY carefully to avoid introducing security holes.
// That's because they are invoked with special "this"! The "this" object
// for all of these methods are not SZArrayHelper objects. Rather, they are of type U[]
// where U[] is castable to T[]. No actual SZArrayHelper object is ever instantiated. Thus, you will
// see a lot of expressions that cast "this" "T[]". 
//
// This class is needed to allow an SZ array of type T[] to expose IList<T>,
// IList<T.BaseType>, etc., etc. all the way up to IList<Object>. When the following call is
// made:
//
//   ((IList<T>) (new U[n])).SomeIListMethod()
//
// the interface stub dispatcher treats this as a special case, loads up SZArrayHelper,
// finds the corresponding generic method (matched simply by method name), instantiates
// it for type <T> and executes it. 
//
// The "T" will reflect the interface used to invoke the method. The actual runtime "this" will be
// array that is castable to "T[]" (i.e. for primitivs and valuetypes, it will be exactly
// "T[]" - for orefs, it may be a "U[]" where U derives from T.)
//----------------------------------------------------------------------------------------

And Contains implementation:

    bool Contains<T>(T value) {
        //! Warning: "this" is an array, not an SZArrayHelper. See comments above
        //! or you may introduce a security hole!
        T[] _this = this as T[];
        BCLDebug.Assert(_this!= null, "this should be a T[]");
        return Array.IndexOf(_this, value) != -1;
    }

So we call following method

public static int IndexOf<T>(T[] array, T value, int startIndex, int count) {
    ...
    return EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count);
}

So far so good. But now we get to the most curious/buggy part.

Consider following example (based on your follow up question)

public struct DummyStruct : IEquatable<DummyStruct>
{
    public string Name { get; set; }

    public bool Equals(DummyStruct other) //<- he is the man
    {
        return Name == other.Name;
    }
    public override bool Equals(object obj)
    {
        throw new InvalidOperationException("Shouldn't be called, since we use Generic Equality Comparer");
    }
    public override int GetHashCode()
    {
        return Name == null ? 0 : Name.GetHashCode();
    }
}

public class DummyClass : IEquatable<DummyClass>
{
    public string Name { get; set; }

    public bool Equals(DummyClass other)
    {
        return Name == other.Name;
    }
    public override bool Equals(object obj) 
    {
        throw new InvalidOperationException("Shouldn't be called, since we use Generic Equality Comparer");
    }
    public override int GetHashCode()
    {
        return Name == null ? 0 : Name.GetHashCode();
    }
}

I have planted exception throws in both non IEquatable<T>.Equals() implementations.

The surprise is:

    DummyStruct[] structs = new[] { new DummyStruct { Name = "Fred" } };
    DummyClass[] classes = new[] { new DummyClass { Name = "Fred" } };

    Array.IndexOf(structs, new DummyStruct { Name = "Fred" });
    Array.IndexOf(classes, new DummyClass { Name = "Fred" });

This code doesn't throw any exceptions. We get directly to the IEquatable Equals implementation!

But when we try the following code:

    structs.Contains(new DummyStruct {Name = "Fred"});
    classes.Contains(new DummyClass { Name = "Fred" }); //<-throws exception, since it calls object.Equals method

Second line throws exception, with following stacktrace:

DummyClass.Equals(Object obj) at System.Collections.Generic.ObjectEqualityComparer`1.IndexOf(T[] array, T value, Int32 startIndex, Int32 count) at System.Array.IndexOf(T[] array, T value) at System.SZArrayHelper.Contains(T value)

Now the bug? or Big Question here is how we got to ObjectEqualityComparer from our DummyClass which does implement IEquatable<T>?

Because the following code:

var t = EqualityComparer<DummyStruct>.Default;
            Console.WriteLine(t.GetType());
            var t2 = EqualityComparer<DummyClass>.Default;
            Console.WriteLine(t2.GetType());

Produces

System.Collections.Generic.GenericEqualityComparer1[DummyStruct] System.Collections.Generic.GenericEqualityComparer1[DummyClass]

Both use GenericEqualityComparer, which calls IEquatable method. In fact Default comparer calls following CreateComparer method:

private static EqualityComparer<T> CreateComparer()
{
    RuntimeType c = (RuntimeType) typeof(T);
    if (c == typeof(byte))
    {
        return (EqualityComparer<T>) new ByteEqualityComparer();
    }
    if (typeof(IEquatable<T>).IsAssignableFrom(c))
    {
        return (EqualityComparer<T>) RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType) typeof(GenericEqualityComparer<int>), c);
    } // RELEVANT PART
    if (c.IsGenericType && (c.GetGenericTypeDefinition() == typeof(Nullable<>)))
    {
        RuntimeType type2 = (RuntimeType) c.GetGenericArguments()[0];
        if (typeof(IEquatable<>).MakeGenericType(new Type[] { type2 }).IsAssignableFrom(type2))
        {
            return (EqualityComparer<T>) RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType) typeof(NullableEqualityComparer<int>), type2);
        }
    }
    if (c.IsEnum && (Enum.GetUnderlyingType(c) == typeof(int)))
    {
        return (EqualityComparer<T>) RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType) typeof(EnumEqualityComparer<int>), c);
    }
    return new ObjectEqualityComparer<T>(); // CURIOUS PART
}

The curious parts are bolded. Evidently for DummyClass with Contains we got to last line, and didn't pass

typeof(IEquatable).IsAssignableFrom(c)

check!

Why not? well I guess its either a bug or implementation detail, which differs for structs because of the following line in SZArrayHelper description class:

The "T" will reflect the interface used to invoke the method. The actual runtime "this" will be array that is castable to "T[]" (i.e. for primitivs and valuetypes, it will be >>exactly "T[]" - for orefs, it may be a "U[]" where U derives from T.)

So we know almost everything now. The only question, which is left, is how comes U doesn't pass typeof(IEquatable<T>).IsAssignableFrom(c) check?

PS: to be more accurate, SZArrayHelper Contains implementation code is from SSCLI20. It seems that currently implementation has changed, cause reflector shows the following for this method:

private bool Contains<T>(T value)
{
    return (Array.IndexOf<T>(JitHelpers.UnsafeCast<T[]>(this), value) != -1);
}

JitHelpers.UnsafeCast shows following code from dotnetframework.org

   static internal T UnsafeCast<t>(Object o) where T : class
    {
        // The body of this function will be replaced by the EE with unsafe code that just returns o!!!
        // See getILIntrinsicImplementation for how this happens.
        return o as T;
    }

Now I wonder about three exclamation marks and how exactly it happens in that mysterious getILIntrinsicImplementation.

Answer 2

Arrays does implement the generic Interfaces IList<T>, ICollection<T> and IEnumerable<T> but the implemeneation is provided at runtime and therefore are not visible to the documentation build tools (That is why you don't see ICollection<T>.Contains in the msdn documentation of Array).

I suspect that the runtime implementation just calls the non generic IList.Contains(object) that the array already has.
And therefor the non generic Equals method in your class is called.

Answer 3

Array has no method with name of contains, this is an extension method from Enumerable class.

Enumerable.Contains method, which you are using that in your array,

is using default equality comparer.

The default equality comparer, needs override of Object.Equality method.

This is because of backward compatibility.

Lists have their own specific implementations, but Enumerable should be compatible with any Enumerable, from .NET 1 to .NET 4.5

Good luck