IndexOf with IEquatable

Published on Friday, July 14, 2017

This topic started from question on StackOverflow: different collections (Array and List) have different implementation of IList.IndexOf method.

Example

using System;
using System.Collections;
using System.Collections.Generic;

namespace IndexOf
{
    class Program
    {
        public static void Main()
        {
            var item = new Item { Id = 1 };

            IList list = new List<Item> { item };
            IList array = new[] { item };

            var newItem = new Item { Id = 1 };

            var lIndex = list.IndexOf(newItem);
            var aIndex = array.IndexOf(newItem);

            Console.WriteLine(lIndex); //0
            Console.WriteLine(aIndex); //-1
        }

        public class Item : IEquatable<Item>
        {
            public int Id { get; set; }

            public bool Equals(Item other) => other != null && other.Id == Id;

        }
    }
}

As we see Item impelments generic interface IEquatable<T> with generic method Equals(T other). Both collections are declared as IList that has non-generic method IndexOf(object value). But, why results are different? We can find item in list, but not in array.

Let's look at List<T> implementation of the method:

int IList.IndexOf(object item)
{
    if (List<T>.IsCompatibleObject(item))
        return this.IndexOf((T) item);
    return -1;
}

It calls generic implementation IndexOf(T item):

public int IndexOf(T item)
{
    return Array.IndexOf<T>(this._items, item, 0, this._size);
}

And static generic method IndexOf of Array class:

public static int IndexOf<T>(T[] array, T value, int startIndex, int count)
{
    if (array == null)
        throw new ArgumentNullException("array");
    if (startIndex < 0 || startIndex > array.Length)
        throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));
    if (count < 0 || count > array.Length - startIndex)
        throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count"));
    return EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count);
}

The main part is EqualityComparer<T>.Default. Here .net creates comparer for out class Item. As our class impelments IEquatable<> interface, GenericEqualityComparer will be created. Check with:

Console.WriteLine(EqualityComparer<Item>.Default.GetType());

GenericEqualityComparer uses IEquatable<T>.Equals(T other) method to compare objects:

internal class GenericEqualityComparer<T> : EqualityComparer<T> where T : IEquatable<T>
{
    public override bool Equals(T x, T y)
    {
        if ((object) x != null)
        {
            if ((object) y != null)
                return x.Equals(y);
            return false;
        }
        return (object) y == null;
    }
    //...
}

So, method IndexOf implemented in List always uses IEquatable<T>.Equals(T other). What about arrays?

Array implementation:

int IList.IndexOf(object value)
{
    return Array.IndexOf(this, value);
}

There is not calls to generic implementation, it operates with object:

public static int IndexOf(Array array, object value)
{
    if (array == null)
        throw new ArgumentNullException("array");
    int lowerBound = array.GetLowerBound(0);
    return Array.IndexOf(array, value, lowerBound, array.Length);
}

And again calls non-generic methods. Final method has this code:

for (int index = startIndex; index < num; ++index)
{
    object obj = objArray[index];
    if (obj != null && obj.Equals(value))
        return index;
}

Where obj.Equals(value) is Equals(object obj) method of Object class.

So, Array and List has different behavior, when we search index of item. It also the same for Contains method:

    Console.WriteLine(list.Contains(newItem)); //true
    Console.WriteLine(array.Contains(newItem)); //false

Ok, but we worked with non-generic interface IList and it looks not so strange. Let's change example to use generic IList<T>:

using System;
using System.Collections;
using System.Collections.Generic;

namespace IndexOf
{
    class Program
    {
        public static void Main()
        {
            var item = new Item { Id = 1 };

            IList<Item> list = new List<Item> { item };
            IList<Item> array = new[] { item };

            var newItem = new Item { Id = 1 };

            var lIndex = list.IndexOf(newItem);
            var aIndex = array.IndexOf(newItem);

            Console.WriteLine(lIndex); //0
            Console.WriteLine(aIndex); //-1

            Console.WriteLine(list.Contains(newItem)); //true
            Console.WriteLine(array.Contains(newItem)); //false

        }

        public class Item : IEquatable<Item>
        {
            public int Id { get; set; }

            public bool Equals(Item other) => other != null && other.Id == Id;
        }
    }
}

But result is the same! We can find item in list, but not in array.

List uses generic method that we saw before:

public int IndexOf(T item)
{
    return Array.IndexOf<T>(this._items, item, 0, this._size);
}

But array... has no generic implementation of IndexOf<T> method! Here magic begins. CLR uses special wrapper for array - SZArrayHelper and it's method IndexOf<T>:

int IndexOf<T>(T value) {
    //! Warning: "this" is an array, not an SZArrayHelper. See comments above
    //! or you may introduce a security hole!
    T[] _this = JitHelpers.UnsafeCast<T[]>(this);
    return Array.IndexOf(_this, value);
}

It look like we work with generic method and objects and should lead to GenericEqualityComparer<T>:

public static int IndexOf<T>(T[] array, T value) {
    if (array==null) {
        throw new ArgumentNullException("array");
    }
    Contract.Ensures((Contract.Result<int>() < 0) ||
        (Contract.Result<int>() >= 0 && Contract.Result<int>() < array.Length && EqualityComparer<T>.Default.Equals(value, array[Contract.Result<int>()])));
    Contract.EndContractBlock();
 
    return IndexOf(array, value, 0, array.Length);
}

But the problem is, how CLR calls this method:

SZArrayHelper

Despite the fact that we use generic IList<Item> and pass Item, CLR cast it to object type and use ObjectEqualityComparer<T> instead of GenericEqualityComparer<T>. Funny, that ObjectEqualityComparer<T> is generic too but compares values as objects:

internal class ObjectEqualityComparer<T> : EqualityComparer<T>
{
    public override bool Equals(T x, T y)
    {
        if ((object) x != null)
        {
            if ((object) y != null)
                return x.Equals((object) y);
            return false;
        }
        return (object) y == null;
    }
    //...
}

And we returned to Item that has only generic Equals, not base one.

So, don't forget to override Equals(object obj):

public class Item : IEquatable<Item>
{
    public int Id { get; set; }

    public bool Equals(Item other) => other != null && other.Id == Id;
    public override bool Equals(object obj) => Equals(obj as Item);
}