T[].Contains for struct and class behaving differe

Question

This is a followup question to this: List<T>.Contains and T[].Contains behaving differently

T[].Contains is behaving differently when T is class and struct. Suppose I have this struct:

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

    public bool Equals(Animal other) //<- he is the man
    {
        return Name == other.Name;
    }
    public override bool Equals(object obj)
    {
        return Equals((Animal)obj);
    }
    public override int GetHashCode()
    {
        return Name == null ? 0 : Name.GetHashCode();
    }
}

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

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

Here, generic Equals is rightly called as I expected.

But in case of a class:

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

    public bool Equals(Animal other)
    {
        return Name == other.Name;
    }
    public override bool Equals(object obj) //<- he is the man
    {
        return Equals((Animal)obj);
    }
    public override int GetHashCode()
    {
        return Name == null ? 0 : Name.GetHashCode();
    }
}

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

animals.Contains(new Animal { Name = "Fred" }); // calls Equals(object)

The non generic Equals is called, taking away the benefit of implementing `IEquatable.

Why is array calling Equals differently for struct[] and class[], even though both the collections seem to look generic?

The array weirdness is so frustrating that I'm thinking of avoiding it totally...

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

Answer 1

It appears that it's not actually Array.IndexOf() that ends up getting called. Looking at the source for that, I would have expected the Equals(object) to get called in both cases if that were the case. By looking at the stack trace at the point where the Equals gets called, it makes it more clear why you're getting the behavior you're seeing (value type gets Equals(Animal), but reference type gets Equals(object).

Here is the stack trace for the value type (struct Animal)

at Animal.Equals(Animal other)
at System.Collections.Generic.GenericEqualityComparer`1.IndexOf(T[] array, T value, Int32 startIndex, Int32 count)
at System.Array.IndexOf[T](T[] array, T value, Int32 startIndex, Int32 count)
at System.Array.IndexOf[T](T[] array, T value)
at System.SZArrayHelper.Contains[T](T value)
at System.Linq.Enumerable.Contains[TSource](IEnumerable`1 source, TSource value) 

Here is the stack trace for the reference type (object Animal)

at Animal.Equals(Object obj)
at System.Collections.Generic.ObjectEqualityComparer`1.IndexOf(T[] array, T value, Int32 startIndex, Int32 count)
at System.Array.IndexOf[T](T[] array, T value, Int32 startIndex, Int32 count)
at System.Array.IndexOf[T](T[] array, T value)
at System.SZArrayHelper.Contains[T](T value)
at System.Linq.Enumerable.Contains[TSource](IEnumerable`1 source, TSource value)

From this you can see that it's not Array.IndexOf that's getting called - it's Array.IndexOf[T]. That method does end up using Equality comparers. In the case of the reference type, it uses ObjectEqualityComparer which call Equals(object). In the case of the value type, it uses GenericEqualityComparer which calls Equals(Animal), presumably to avoid an expensive boxing.

If you look at the source code for IEnumerable at http://www.dotnetframework.org it has this interesting bit at the top:

// Note that T[] : IList<t>, and we want to ensure that if you use
// IList<yourvaluetype>, we ensure a YourValueType[] can be used
// without jitting.  Hence the TypeDependencyAttribute on SZArrayHelper.
// This is a special hack internally though - see VM\compile.cpp.
// The same attribute is on IList<t> and ICollection<t>.
[TypeDependencyAttribute("System.SZArrayHelper")]

I'm not familiar with TypeDependencyAttribute, but from the comment, I'm wondering if there is some magic going on that's special for Array. This may explain how IndexOf[T] ends up getting called instead of IndexOf via Array's IList.Contains.

Answer 2

The primary purpose of IEquatable<T> is to allow reasonably-efficient equality comparisons with generic structure types. It is intended that IEquatable<T>.Equals((T)x) should behave exactly like Equals((object)(T)x); except that if T is a value type the former will avoid a heap allocation which will be required for the latter. Although IEquatable<T> does not constrain T to be a struct type, and sealed classes may in some cases receive a slight performance benefit from using it, class types cannot receive nearly as much benefit from that interface as do struct types. A properly-written class may perform slightly faster if outside code uses IEquatable<T>.Equals(T) instead of Equals(Object), but should otherwise not care which comparison method is used. Because the performance advantage of using IEquatable<T> with classes is never very large, code which knows it's using a class type might decide that the time required to check whether the type happens to implement IEquatable<T> would likely not be recouped by any performance gain the interface could plausibly offer.

Incidentally, it's worth noting that if X and Y are "normal" classes, X.Equals(Y) may legitimately be true if either X or Y derives from the other. Further, a variable of an unsealed class type may legitimately compare equal to one of any interface type whether or not the class implements that interface. By comparison, a structure can only compare equal to a variable of its own type, Object, ValueType, or an interface which the structure itself implements. The fact that class-type instances may be "equal" to a much wider range of variable types means that the IEquatable<T> isn't as applicable with them as with structure types.

PS--There's another reason arrays are special: they support a style of covariance which classes cannot. Given

Dog Fido = new Dog();
Cat Felix = new Cat();
Animal[] meows = new Cat[]{Felix};

it is perfectly legal to test meows.Contains(Fido). If meows were replaced with an instance of Animal[] or Dog[], the new array might indeed contain Fido; even if it weren't, one might legitimately have a variable of some unknown type of Animal and want to know if it's contained within meows. Even if Cat implements IEquatable<Cat>, trying to use the IEquatable<Cat>.Equals(Cat) method to test whether an element of meows is equal to Fido would fail because Fido cannot be converted into a Cat. There might be ways for the system to use IEquatable<Cat> when it's workable and Equals(Object) when it isn't, but it would add a lot of complexity, and it would be hard to do without a performance cost which would exceed that of simply using Equals(Object).

Answer 3

I think its because they are both using their own base implementation of Equals

Classes inherit Object.Equals which implements identity equality, Structs inherit ValueType.Equals which implements value equality.