[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

[ghost]

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 .

[bartonjs]

• The group preferred the arity-2 versions of the comparers
• We had a distraction around ReadOnlyMemory and IEnumerable, and decided to omit CreateMemoryComparer for now. We should discuss if we should just make ReadOnlyMemory : IEnumerable for .NET 8 (and, if no, we can discuss bringing this back).

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<TSet> CreateSetComparer<TSet, T>(IEqualityComparer<T>? elementComparer = null) 
        where TSet : IReadOnlySet<T> { }

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

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

[eiriktsarpalis]

We had a distraction around ReadOnlyMemory and IEnumerable, and decided to omit CreateMemoryComparer for now. We should discuss if we should just make ReadOnlyMemory : IEnumerable for .NET 8 (and, if no, we can discuss bringing this back).

Relevant issue: #23950. I'm marking that as ready-for-review so we can revisit in light of this discussion.

[Timovzl]

// Equality comparison à la HashSetEqualityComparer
// cf. https://github.com/dotnet/runtime/blob/5ef4c68b08b5f55df91ce62cca86babfdb321162/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/HashSetEqualityComparer.cs

I love the optimizations that implementation does, but falling back to O(N^2) comparisons seems suboptimal. Wouldn't a 2*N approach like this be just as correct?

Its premise is: if (and only if) each set considers the other to satisfy each of its own elements, then the sets must be equal. With constant-time lookups, that can be evaluated in linear time.

In fact, the latter implementation offers another advantage over HashSetEqualityComparer's O(N^2) portion: avoiding the default comparer is more consistent and arguably more correct. After all, if the comparers are identical, then HashSetEqualityComparer delegates to IsSubsetOfHashSetWithSameComparer, which performs the comparisons on the set, i.e. using their comparer. But if their comparers differ, it ignores them altogether and switches to the default comparer! That's different behavior.

[Timovzl]

This is an exciting proposal.

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

Is this still the plan? I don't see an overload for it in the last update, but hopefully...

it might be possible that we specialize IList in the enumerable combinator

...applies here?

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

I believe this one might be worth optimizing for as well. Specifically, I give you Lookup.Grouping<TKey, TElement>. This sneaky little bugger is used to implement the IGrouping<TKey, TElement> used in LINQ's lookups. That interface and those lookups are read-only to the caller. Yet this grouping neglects to implement IReadOnlyList<T>. 😠

It would not surprise me if some other internal collection implementations similarly restrict themselves to IList<T>.

I realize that we have to select our special cases carefully. But since such IList<T> implementations lacking IReadOnlyList<T> appear in commonly occurring types (and are out of the caller's control), I think they warrant optimization.

(In my own implementation, I chose to runtime-special-case List<T>, T[], and ImmutableArray<T> by using spans, and IList<T> by using indexers. The rare IReadOnlyList<T> not implementing IList<T> I let slip, to reduce the number of special cases.)

[Timovzl]

Speaking of ILookup<TKey, TElement>: should it be included? Including dictionaries and sets but skipping lookups strikes me as incomplete. Together, they cover the spectrum of 1:0 (set), 1:1 (dictionary), and 1:N (lookup).

Also, I believe that my earlier comment on set equality applies to lookups as well. (Here is an example implementation.)

[manandre]

Be careful, the Comparer class already exists in the System.Collections namespace.
Adding a Comparer class also in the System.Collections.Generic namespace will lead to references conflict in (common) situations where both namespaces are used.

error CS0104: 'Comparer' is an ambiguous reference between 'System.Collections.Comparer' and 'System.Collections.Generic.Comparer'

[stephentoub]

Yeah, we should not be adding new non-generic EqualityComparer and Comparer types to System.Collections.Generic. This needs to be revisited.

[eiriktsarpalis]

I think we could just cut the Comparer combinator for now and ship the equality comparer ones as approved. Or are you suggesting a new design/class name that encapsulates both kinds of combinators?

[stephentoub]

We should not add System.Collections.Generic.EqualityComparer when there's already System.Collections.EqualityComparer.

We already have System.Collections.Generic.EqualityComparer<T> with Create methods... we should add to that class with a revised design, given the T.

[eiriktsarpalis]

We should not add System.Collections.Generic.EqualityComparer when there's already System.Collections.EqualityComparer.

I don't think there is a System.Collections.EqualityComparer type, the issue is with System.Collections.Comparer.

We already have System.Collections.Generic.EqualityComparer with Create methods... we should add to that class with a revised design, given the T.

I don't think that would work well for the dictionary combinator, which requires at least two type parameters bound by generic constraints. It certainly wouldn't work with the current design of using an added generic parameter for the collection type.

[stephentoub]

I don't think there is a System.Collections.EqualityComparer type, the issue is with System.Collections.Comparer.

You're right. But even so, as there is a non-generic Comparer in System.Collections, it's strange to add a non-generic EqualityComparer to System.Collections.Generic which already has a generic one. I'd much rather see Create overloads or CreateXx methods on the existing type. It's where devs now look for this kind of functionality; they shouldn't need to look to EqualityComparer<T> for some Create methods and EqualityComparer for others.

If others on fdc think it's fine, fine. But we need to re-review it.

[eiriktsarpalis]

But even so, as there is a non-generic Comparer in System.Collections, it's strange to add a non-generic EqualityComparer to System.Collections.Generic which already has a generic one.

Using non-generic static classes to host factory methods for generic types is standard practice as far I can tell (the static classes in System.Collections.Immutable jump to mind).

I'd much rather see Create overloads or CreateXx methods on the existing type.

Retrofitting the existing generic class with combinators creates problems when type constraints come into play, for example the following is not valid C#:

public partial class EqualityComparer<T>
{
    public static EqualityComparer<T> CreateEnumerableComparer<TElement>(IEqualityComparer<TElement>? elementComparer = null) 
        where T : IEnumerable<TElement> { }
}

We could just ignore the class-level type parameter:

public partial class EqualityComparer<T>
{
    public static EqualityComparer<TEnumerable> CreateEnumerableComparer<TEnumerable, TElement>(IEqualityComparer<TElement>? elementComparer = null) 
        where TEnumerable : IEnumerable<TElement> { }
}

but this would be too awkward to use.

It's where devs now look for this kind of functionality;

I'd be inclined to think of EqualityComparer<T> as the class defining the default equality comparison for a given type. Even though users can derive from that type, I'm not aware of any locations in System.Collections that use the type for non-default equality comparison.

[stephentoub]

Using non-generic static classes to host factory methods for generic types is standard practice as far I can tell (the static classes in System.Collections.Immutable jump to mind

Yes, but it's not standard to have have both a non-generic and generic of the same name both with factory methods.

[stephentoub]

I'd be inclined to think of EqualityComparer<T> as the class defining the default equality comparison for a given type

It provides a Create method that lets you fully customize it. That is not default equality.

[stephentoub]

Retrofitting the existing generic class with combinators creates problems when type constraints come into play,

Hence why this needs work. The 99% case here is needing the APIs on the generic class, and this proposal suggests creating a non-generic right next to it with very niche support. So a dev comes along, types EqualityComparer, dots of it, and is now in a pit of failure for the 99% case. Essentially this niche proposal makes using the existing golden path functionality harder to discover.

[eiriktsarpalis]

I'd be inclined to think of EqualityComparer<T> as the class defining the default equality comparison for a given type

It provides a Create method that lets you fully customize it. That is not default equality.

This was added recently. It might be possible to reconsider its location so that all factories are located consistently in the non-generic class:

public class EqualityComparer<T>
{
-    public EqualityComparer<T> Create(Func<T?, T?, bool> equals, Func<T, int>? getHashCode = null);
}

+public static class EqualityComparer
+{
+    public EqualityComparer<T> Create<T>(Func<T?, T?, bool> equals, Func<T, int>? getHashCode = null);
+
+    public static EqualityComparer<TEnumerable> CreateEnumerableComparer<TEnumerable, T>(IEqualityComparer<T>? elementComparer = null) 
+        where TEnumerable : IEnumerable<T> { }
+
+    public static EqualityComparer<TSet> CreateSetComparer<TSet, T>(IEqualityComparer<T>? elementComparer = null) 
+        where TSet : IReadOnlySet<T> { }
+
+    public static EqualityComparer<TDictionary> CreateDictionaryComparer<TDictionary, TKey, TValue>(IEqualityComparer<TKey>? keyComparer = null, IEqualityComparer<TValue>? valueComparer = null) 
+        where TDictionary : IReadOnlyDictionary<TKey, TValue> { }
+}

[eiriktsarpalis]

Essentially this niche proposal

Keying on buffers using sequence equality is fairly common, we currently don't have a built-in implementation for it.

[stephentoub]

Keying on buffers using sequence equality

It's way, way less common than just needing a simple comparer for a T, and if it were just about sequence equality, it could be added to the existing type.

[eiriktsarpalis]

if it were just about sequence equality, it could be added to the existing type.

You could, but it would necessarily forsake the TEnumerable specializations.

So a dev comes along, types EqualityComparer, dots of it, and is now in a pit of failure for the 99% case.

I'm not sure how existence of similarly named types constitutes a pit of failure. It is fairly common for a particular named component to distribute functionality across a generic/nongeneric, class/interface matrix.