API Proposal: MemoryExtensions.SequenceEqual with IComparer<T>

[stephentoub]

Background and Motivation

We currently have MemoryExtensions.SequenceEqual overloads that work with spans, but they constrain T : IEquatable<T>:

public static bool SequenceEqual<T>(this System.ReadOnlySpan<T> span, System.ReadOnlySpan<T> other) where T : System.IEquatable<T> { throw null; }
public static bool SequenceEqual<T>(this System.Span<T> span, System.ReadOnlySpan<T> other) where T : System.IEquatable<T> { throw null; }

This means there's no built-in support for using IEqualityComparer<T>. It also means APIs like Enumerable.SequenceEqual that are unconstrained aren't able to delegate to this in general when provided with array inputs.

Proposed API

public static class MemoryExtensions
{
    public static bool SequenceEqual<T>(this System.ReadOnlySpan<T> span, System.ReadOnlySpan<T> other, IEqualityComparer<T>? comparer);
    public static bool SequenceEqual<T>(this System.Span<T> span, System.ReadOnlySpan<T> other, IEqualityComparer<T>? comparer);
    ...
}

We could also consider doing the same thing for SequenceCompareTo, taking the existing overloads and adding new ones that remove the constraint and accept a nullable IComparer<T>.

The implementations would delegate to the existing implementations if comparer is null and T is found to be IEquatable<T> (maybe just for value types). Otherwise, they'd loop through the spans comparing each element.

Usage Examples

For example, we would change Enumerable.SequenceEqual to do:

if (first is TSource[] firstArray && second is TSource[] secondArray)
{
    return ((ReadOnlySequence<TSource>)firstArray).SequenceEqual(secondArray, comparer);
}

Tagging subscribers to this area: @GrabYourPitchforks
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and Motivation

We currently have MemoryExtensions.SequenceEqual overloads that work with spans, but they constrain T : IEquatable<T>:

        public static bool SequenceEqual<T>(this System.ReadOnlySpan<T> span, System.ReadOnlySpan<T> other) where T : System.IEquatable<T> { throw null; }
        public static bool SequenceEqual<T>(this System.Span<T> span, System.ReadOnlySpan<T> other) where T : System.IEquatable<T> { throw null; }

This means there's no built-in support for using IEqualityComparer<T>. It also means APIs like Enumerable.SequenceEqual that are unconstrained aren't able to delegate to this in general when provided with array inputs.

Proposed API

public static class MemoryExtensions
{
    public static bool SequenceEqual<T>(this System.ReadOnlySpan<T> span, System.ReadOnlySpan<T> other, IEqualityComparer<T>? comparer);
    public static bool SequenceEqual<T>(this System.Span<T> span, System.ReadOnlySpan<T> other, IEqualityComparer<T>? comparer);
    ...
}

We could also consider doing the same thing for SequenceCompareTo, taking the existing overloads and adding new ones that remove the constraint and accept a nullable IComparer<T>.

Usage Examples

For example, we would change Enumerable.SequenceEqual to do:

if (first is TSource[] firstArray && second is TSource[] secondArray)
{
    return ((ReadOnlySequence<TSource>)firstArray).SequenceEqual(secondArray, comparer);
}

<table>
  <tr>
    <th align="left">Author:</th>
    <td>stephentoub</td>
  </tr>
  <tr>
    <th align="left">Assignees:</th>
    <td>-</td>
  </tr>
  <tr>
    <th align="left">Labels:</th>
    <td>

`api-ready-for-review`, `area-System.Memory`, `untriaged`

</td>
  </tr>
  <tr>
    <th align="left">Milestone:</th>
    <td>6.0.0</td>
  </tr>
</table>
</details>

[benaadams]

Would it need a IEqualityComparer<T>? comparer = null optional param to be used as your example? (which doesn't specify the comparer)

[stephentoub]

to be used as your example? (which doesn't specify the comparer)

My example does pass a comparer... ?

[benaadams]

My example does pass a comparer... ?

😅 So it does

[terrajobst]

Video

• Makes sense
• We could drop the constraint on the existing APIs and do the right thing internally, but we can do that later
  • Or we could default the comparer to null, which means the caller will either use the existing one when it is equatable and use the new one when it's not.

namespace System
{
    public static class MemoryExtensions
    {
        // Existing
        // public static bool SequenceEqual<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> other) where T : IEquatable<T>;
        // public static bool SequenceEqual<T>(this Span<T> span, ReadOnlySpan<T> other) where T : System.IEquatable<T>;
        public static bool SequenceEqual<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> other, IEqualityComparer<T>? comparer = null);
        public static bool SequenceEqual<T>(this Span<T> span, ReadOnlySpan<T> other, IEqualityComparer<T>? comparer = null);
    }
}