[API Proposal]: Add structural equality and order comparison for common collections

[eiriktsarpalis]

Background and motivation

This proposal attempts to consolidate a number of issues requesting IEqualityComparer<T> and IComparer<T> combinators acting on common collection types, e.g. #33873, #44796, #77183 (comment) and #19644. Defining structural equality/order comparison on collection types is a common requirement, for example when working with incremental source generators.

API Proposal

namespace System.Collections.Generic;

public static class EqualityComparer
{
    // Equality comparison using sequence equality
    public static IEqualityComparer<IEnumerable<T>> CreateEnumerableComparer<T>(IEqualityComparer<T> elementComparer = null);
    public static IEqualityComparer<ReadOnlyMemory<T>> CreateMemoryComparer<T>(IEqualityComparer<T> elementComparer = null);
    public static IEqualityComparer<IReadOnlyList<T>> CreateListComparer<T>(IEqualityComparer<T> elementComparer = null);

    // Equality comparison à la HashSetEqualityComparer
    // cf. https://github.com/dotnet/runtime/blob/5ef4c68b08b5f55df91ce62cca86babfdb321162/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/HashSetEqualityComparer.cs
    public static IEqualityComparer<IReadOnlySet<T>> CreateSetComparer<T>(IEqualityComparer<T> elementComparer = null);
    public static IEqualityComparer<IReadOnlyDictionary<TKey, TValue>> CreateDictionaryComparer<TKey, TValue>(IEqualityComparer<TKey> keyComparer= null, IEqualityComparer<TValue> valueComparer = null);
}

public static class Comparer
{
    // Comparison using lexicographic ordering
    public static IComparer<IEnumerable<T>> CreateEnumerableComparer<T>(IComparer<T> elementComparer = null);
    public static IComparer<ReadOnlyMemory<T>> CreateMemoryComparer<T>(IComparer<T> elementComparer = null);
    public static IComparer<IReadOnlyList<T>> CreateListComparer<T>(IComparer<T> elementComparer = null);
}

API Usage

IEqualityComparer<string[]> stringArrayComparer = EqualityComparer.CreateEnumerableComparer(StringComparer.InvariantCultureIgnoreCase);
var dictionary = new Dictionary<string[], object>(stringArrayComparer);

dictionary.Add(new string[] { "key" }, null);
dictionary.ContainsKey(new string[] { "KEY" }); // true

IComparer<string[]> stringArrayComparer = Comparer.CreateEnumerableComparer(StringComparer.InvariantCultureIgnoreCase);
var dictionary = new SortedDictionary<string[], object>(stringArrayComparer);

dictionary.Add(new string[] { "key" }, null);
dictionary.ContainsKey(new string[] { "KEY" }); // true

Alternative Designs

Making the combinators generic on the collection type would allow construction-time specialization and help with devirtualization, e.g.

public static IEqualityComparer<TEnumerable> CreateEnumerableComparer<TEnumerable, TElement>(IEqualityComparer<TElement> elementComparer = null)
     where TEnumerable : IEnumerable<TElement>
{
     elementComparer ??= EqualityComparer<T>.Default;

     if (typeof(IReadOnlyList<TElement>).IsAssignableFrom(typeof(TEnumerable)))
     {
          return new ListSequenceComparer<TEnumerable, TElement>(elementComparer));
     }

     return new EnumerableSequenceComparer<TEnumerable, TElement>(elementComparer);
}

But obviously that would make calling the combinators more complicated:

IEqualityComparer<int[]> arrayComparer = EqualityComparer.CreateEnumerableComparer<int[], int>();

Full alternative proposal:

namespace System.Collections.Generic;

public static class EqualityComparer
{
    // Equality comparison using sequence equality
    public static IEqualityComparer<TEnumerable> CreateEnumerableComparer<TEnumerable, T>(IEqualityComparer<T> elementComparer = null) 
        where TEnumerable : IEnumerable<T> { }

    public static IEqualityComparer<ReadOnlyMemory<T>> CreateMemoryComparer<T>(IEqualityComparer<T> elementComparer = null) { }

    // Equality comparison à la HashSetEqualityComparer
    // cf. https://github.com/dotnet/runtime/blob/5ef4c68b08b5f55df91ce62cca86babfdb321162/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/HashSetEqualityComparer.cs
    public static IEqualityComparer<TSet> CreateSetComparer<TSet, T>(IEqualityComparer<T> elementComparer = null) 
        where TSet : IReadOnly<T> { }

    public static IEqualityComparer<TDictionary> CreateDictionaryComparer<TDictionary, TKey, TValue>(IEqualityComparer<TKey> keyComparer= null, IEqualityComparer<TValue> valueComparer = null) 
        where TDictionary : IDictionary<TKey, TValue> { }
}

public static class Comparer
{
    // Comparison using lexicographic ordering
    public static IComparer<TEnumerable> CreateEnumerableComparer<TEnumerable, T>(IComparer<T> elementComparer = null) 
        where TEnumerable : IEnumerable<T> { }

    public static IComparer<ReadOnlyMemory<T>> CreateMemoryComparer<T>(IComparer<T> elementComparer = null) { }
}

Risks

No response

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and motivation

This proposal attempts to consolidate a number of issues requesting IEqualityComparer<T> and IComparer<T> combinators acting on common collection types, e.g. #33873, #44796 and #19644. Defining structural equality/order comparison on collection types is a common requirement, for example when working with incremental source generators.

API Proposal

namespace System.Collections.Generic;

public static class EqualityComparer
{
    // Equality comparison using sequence equality
    public static IEqualityComparer<IEnumerable<T>> CreateEnumerableComparer<T>(IEqualityComparer<T> elementComparer = null);
    public static IEqualityComparer<ReadOnlyMemory<T>> CreateMemoryComparer<T>(IEqualityComparer<T> elementComparer = null);
    public static IEqualityComparer<IReadOnlyList<T>> CreateListComparer<T>(IEqualityComparer<T> elementComparer = null);

    // Equality comparison à la HashSetEqualityComparer
    // cf. https://github.com/dotnet/runtime/blob/5ef4c68b08b5f55df91ce62cca86babfdb321162/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/HashSetEqualityComparer.cs
    public static IEqualityComparer<IReadOnlySet<T>> CreateSetComparer<T>(IEqualityComparer<T> elementComparer = null);
    public static IEqualityComparer<IReadOnlyDictionary<TKey, TValue>> CreateDictionaryComparer<TKey, TValue>(IEqualityComparer<TKey> keyComparer= null, IEqualityComparer<TValue> valueComparer = null);
}

public static class Comparer
{
    // Comparison using Lexicographic ordering
    public static IComparer<IEnumerable<T>> CreateEnumerableComparer<T>(IComparer<T> elementComparer = null);
    public static IComparer<ReadOnlyMemory<T>> CreateMemoryComparer<T>(IComparer<T> elementComparer = null);
    public static IComparer<IReadOnlyList<T>> CreateListComparer<T>(IComparer<T> elementComparer = null);

    // Optional additions -- cheap (O(n) time, O(1) space) when specialized to SortedSet/SortedDictionary and friends,
    //                                    expensive (O(n log n) time, O(n) space) for hashtable implementations.
    public static IComparer<IReadOnlySet<T>> CreateSetComparer<T>(IComparer<T> elementComparer = null);
    public static IComparer<IReadOnlyDictionary<TKey, TValue>> CreateDictionaryComparer<TKey, TValue>(IComparer<TKey> keyComparer= null, IComparer<TValue> valueComparer = null);
}

API Usage

IEqualityComparer<string[]> stringArrayComparer = EqualityComparer.CreateEnumerableComparer<string>(StringComparer.InvariantCultureIgnoreCase);
var dictionary = new Dictionary<string[], object>(stringArrayComparer);

dictionary.Add(new string[] { "key" }, null);
dictionary.ContainsKey(new string[] { "KEY" }); // true

IComparer<string[]> stringArrayComparer = Comparer.CreateEnumerableComparer<string>(StringComparer.InvariantCultureIgnoreCase);
var dictionary = new SortedDictionary<string[], object>(stringArrayComparer);

dictionary.Add(new string[] { "key" }, null);
dictionary.ContainsKey(new string[] { "KEY" }); // true

Alternative Designs

Making the combinators generic on the collection type would allow construction-time specialization, e.g.

public static IEqualityComparer<TEnumerable> CreateEnumerableComparer<TEnumerable, TElement>(IEqualityComparer<TElement> elementComparer = null)
     where TEnumerable : IEnumerable<TElement>
{
     elementComparer ??= EqualityComparer<T>.Default;

     if (typeof(TEnumerable) = typeof(TElement[]))
     {
          return (IEqualityComparer<TEnumerable>)(object)(new ArraySequenceComparer<TElement>(elementComparer));
     }

     if (typeof(TEnumerable) = typeof(List<TElement>))
     {
          return (IEqualityComparer<TEnumerable>)(object)(new ListSequenceComparer<TElement>(elementComparer));
     }

     return new EnumerableSequenceComparer<TElement>(elementComparer);
}

But obviously that would make calling the combinators more complicated:

IEqualityComparer<int[]> arrayComparer = EqualityComparer.CreateEnumerableComparer<int[], int>();

Risks

No response

Author:	eiriktsarpalis
Assignees:	-
Labels:	api-suggestion, area-System.Collections
Milestone:	-

[eiriktsarpalis]

cc @jnm2 @GSPP @JonHanna @Sergio0694

[Sergio0694]

Looks great! A couple quick notes:

• I wonder if we'd want to have a specialization for ImmutableArray<T> like a lot of the built-in extension for that type do, so that the allocation due to going through IEnumerable<T> can be skipped. As in, so that you'd just have a "more specific" type when you're just interested in getting an equality comparer for ImmutableArray<T> instances. I found this to be sometimes useful in source generators as well (as immutable arrays are used quite extensively and you might want to compare them).
• This unfortunately does not really solve the issue of "falling off a cliff" with record types. I guess a solution for that is outside of the scope of this proposal (and this proposal is still very useful, absolutely), but I'm just wondering if something could be done about that, and if so, what a solution for that could look like.

Essentially, the issue for the second point is:

record MyModel(int X, string Y, SomeEquatableType Z, ImmutableArray<AnotherEquatableType> W);

Records like these are extremely common in incremental generation steps, and they will silently break incrementality because the codegen for records will just compare those arrays by reference equality for the underlying array, which of course will not work. Right now the only solution is to manually implement full equality for the type, which defeats the whole point of using a record. I'm not sure I know how a solution for this could look like though, as this might just be considered a limitation with Roslyn's codegen for records. @RikkiGibson any thoughts here? I'd be happy to help opening a proposal for csharplang if needed, but I guess my question here is more about, I'm not actually sure what (if anything) could be done to improve the situation here 🤔

[eiriktsarpalis]

I wonder if we'd want to have a specialization for ImmutableArray<T>

I'm hoping that having a generic specialization for a TList : IReadOnlyList<T> comparer would be good enough as it would avoid enumeration and help with devirtualization.

This unfortunately does not really solve the issue of "falling off a cliff" with record types.

It is unfortunate, but this it's beyond the scope of this proposal. We might continue this conversation either in #77183 or csharplang if necessary.

[GSPP]

Awesome to see this happening.

What about IList<T>? This interface does not derive from IReadOnlyList<T>. It is quite conceivable that someone might use a collection type that implements IList<T> but not IReadOnlyList<T>. IReadOnlyList<T> is a fairly new interface.

https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.ireadonlylist-1?view=net-6.0
https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.ilist-1?view=net-6.0

The sets of derived types have quite a few unique items on both sides. As an example, JSON types caught my eye.

[eiriktsarpalis]

What about IList?

I wanted to avoid exposing combinators for overtly mutable types, since using these with hash tables can be dangerous. I do get that read-only does not imply immutable, and that mutable types implement read-only collection interfaces, but I suspect there's self-documentation value in constraining the APIs to read-only types. It's the same reason why I didn't add a Memory<T> overload.

Assuming we use the API variant in "Alternative Designs", it might be possible that we specialize IList<T> in the enumerable combinator.

The sets of derived types have quite a few unique items on both sides.

As of .NET 7 it is possible to wrap an IList<T> inside a IReadOnlyList<T> using the AsReadOnly extension method.

[GSPP]

I see your reasoning.

The IEnumerable<T> overload could also runtime cast and specialize for common use cases such as arrays and lists. It can happen easily to have such an instance typed statically as IEnumerable<T>.

Changing this in later releases could be a compatibility problem. Maybe the documentation should say:

The implementation might specialize comparison behavior for runtime types other than the type denoted statically by the generic parameter. This might, for example, result in IList<T> methods being called on a comparer argument statically typed as IEnumerable<T>.

That way, there is documented leeway to optimize this.

[GSPP]

Casting-based specialization adds constant overhead for all cases but that might be better than falling off a performance cliff when people compare byte arrays and such through IEnumerable<T>.

A complication with this is that hash codes must be the same even if different IEnumerable<T>-derived types are mixed. As an example, the following two expressions must result in the same hashcode:

myComparer.GetHashCode(new byte[] { 1, 2, 3, 4 }) //Potentially optimizable array
myComparer.GetHashCode(new byte[] { 1, 2, 3, 4 }.Select(x => x)) //Opaque enumerable

This effectively forces per-element hashing and hashcode aggregation, which implies certain inefficiencies.

The CreateEnumerableComparer<TEnumerable, TElement> design is an interesting idea but it would not help with this particular usability issue.

[eiriktsarpalis]

The CreateEnumerableComparer<TEnumerable, TElement> design is an interesting idea but it would not help with this particular usability issue.

Note that the return type is IEqualityComparer<TEnumerable> rather than IEqualityComparer<IEnumerable<T>>, so the implementation would change based on the static type parameter rather than the runtime type of the supplied parameters.

Obviously this means that different hashcodes would be returned depending on what type TEnumerable is, but I suspect this is fine as long we have consistency for the particular equality comparer instance .