MemoryExtensions.*(..., IEqualityComparer) overloads

[stephentoub]

EDITED 11/5/2024 by @stephentoub with updated proposal:

namespace System;

public static class MemoryExtensions
{
+   public static bool Contains<T>(this ReadOnlySpan<T> span, T value, IEqualityComparer<T>? comparer = null);
+   public static bool ContainsAny<T>(this ReadOnlySpan<T> span, T value0, T value1, IEqualityComparer<T>? comparer = null);
+   public static bool ContainsAny<T>(this ReadOnlySpan<T> span, T value0, T value1, T value2, IEqualityComparer<T>? comparer = null);
+   public static bool ContainsAny<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> values, IEqualityComparer<T>? comparer = null);

+   public static bool ContainsAnyExcept<T>(this ReadOnlySpan<T> span, T value, IEqualityComparer<T>? comparer = null);
+   public static bool ContainsAnyExcept<T>(this ReadOnlySpan<T> span, T value0, T value1, IEqualityComparer<T>? comparer = null);
+   public static bool ContainsAnyExcept<T>(this ReadOnlySpan<T> span, T value0, T value1, T value2, IEqualityComparer<T>? comparer = null);
+   public static bool ContainsAnyExcept<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> values, IEqualityComparer<T>? comparer = null);

+   public static int Count<T>(this ReadOnlySpan<T> span, T value, IEqualityComparer<T>? comparer = null);
+   public static int Count<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> value, IEqualityComparer<T>? comparer = null);

+   public static bool EndsWith<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> value, IEqualityComparer<T>? comparer = null);
+   public static bool EndsWith<T>(this ReadOnlySpan<T> span, T value, IEqualityComparer<T>? comparer = null);

+   public static bool StartsWith<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> value, IEqualityComparer<T>? comparer = null);
+   public static bool StartsWith<T>(this ReadOnlySpan<T> span, T value, IEqualityComparer<T>? comparer = null);

+   public static int IndexOf<T>(this ReadOnlySpan<T> span, T value, IEqualityComparer<T>? comparer = null);
+   public static int IndexOfAny<T>(this ReadOnlySpan<T> span, T value0, T value1, IEqualityComparer<T>? comparer = null);
+   public static int IndexOfAny<T>(this ReadOnlySpan<T> span, T value0, T value1, T value2, IEqualityComparer<T>? comparer = null);
+   public static int IndexOfAny<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> values, IEqualityComparer<T>? comparer = null);

+   public static int IndexOf<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> value, IEqualityComparer<T>? comparer = null);

+   public static int IndexOfAnyExcept<T>(this ReadOnlySpan<T> span, T value, IEqualityComparer<T>? comparer = null);
+   public static int IndexOfAnyExcept<T>(this ReadOnlySpan<T> span, T value0, T value1, IEqualityComparer<T>? comparer = null);
+   public static int IndexOfAnyExcept<T>(this ReadOnlySpan<T> span, T value0, T value1, T value2, IEqualityComparer<T>? comparer = null);
+   public static int IndexOfAnyExcept<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> value, IEqualityComparer<T>? comparer = null);

+   public static int LastIndexOf<T>(this ReadOnlySpan<T> span, T value, IEqualityComparer<T>? comparer = null);
+   public static int LastIndexOfAny<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> values, IEqualityComparer<T>? comparer = null);
+   public static int LastIndexOfAny<T>(this ReadOnlySpan<T> span, T value0, T value1, IEqualityComparer<T>? comparer = null);
+   public static int LastIndexOfAny<T>(this ReadOnlySpan<T> span, T value0, T value1, T value2, IEqualityComparer<T>? comparer = null);

+   public static int LastIndexOf<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> value, IEqualityComparer<T>? comparer = null);

+   public static int LastIndexOfAnyExcept<T>(this ReadOnlySpan<T> span, T value, IEqualityComparer<T>? comparer = null);
+   public static int LastIndexOfAnyExcept<T>(this ReadOnlySpan<T> span, T value0, T value1, IEqualityComparer<T>? comparer = null);
+   public static int LastIndexOfAnyExcept<T>(this ReadOnlySpan<T> span, T value0, T value1, T value2, IEqualityComparer<T>? comparer = null);
+   public static int LastIndexOfAnyExcept<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> values, IEqualityComparer<T>? comparer = null);

+   public static void Replace<T>(this ReadOnlySpan<T> source, Span<T> destination, T oldValue, T newValue, IEqualityComparer<T>? comparer = null);

+   public static int SequenceCompareTo<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> other, IComparer<T>? comparer = null);
}

Notes:

• The above systematically adds IEqualityComparer<T>? comparer = null overloads for existing overloads without the comparer but constraining where T : IEquatable<T>?. Exceptions to this:
• 1. Overloads for Trim/TrimStart/TrimEnd and Split/SplitAny as there are a lot of them, and I've not yet seen a need. The return type also complicates things, e.g. Split returns a SpanSplitEnumerable<T> that constrains the T.
• 2. Overloads for this Span. Per [API Proposal]: Apply [OverloadResolutionPriority] to Span-based overloads #109549, they're no longer needed.
• The IEquatable<T> overloads will continue to bind when no comparer is provided and the T is IEquatable. The new overloads will be used when either a comparer is provided or when T isn't IEquatable, so the signatures just naturally become usable in more places.

---

Old proposal:

https://github.com/dotnet/corefx/issues/27526 was reviewed and API-approved to add four overloads:

public static class MemoryExtensions
{
    bool Contains<T>(this Span<T> span, T value);
    bool Contains<T>(this ReadOnlySpan<T> span, T value);
    bool Contains<T>(this Span<T> span, T value, IEqualityComparer<T> comparer);
    bool Contains<T>(this ReadOnlySpan<T> span, T value, IEqualityComparer<T> comparer);
}

However, only the first two got implemented. The latter two were flagged as being inconsistent:
https://github.com/dotnet/corefx/issues/27526#issuecomment-422467532

The other 2 APIs are inconsistent with the rest of System.Memory public surface (none of the several hundreds other System.Memory APIs take IEqualityComparer). I assume that this was oversight during API review. We should have a new issue opened to discuss the IEqualityComparer overloads. We should either add the overloads that take IEqualityComparer everywhere in System.Memory (ie add ~30 new APIs), or nowhere. It does not make sense to add them to a random subset.

Opening this issue to track those.

cc: @GrabYourPitchforks, @ahsonkhan

[GrabYourPitchforks]

Thanks for bringing this up! One of the things that has been confounding me a bit is the fact that String's methods have different default comparisons if no explicit comparison is specified. For example, String.Contains(string) defaults to StringComparison.Ordinal, but String.IndexOf(string) defaults to StringComparison.CurrentCulture. The end result is that foo.Contains(bar) and foo.IndexOf(bar) >= 0 don't necessarily always have the same value, which is problematic.

Given that we want our developer audience to use ROS<char> as a drop-in replacement for string slices, I wonder if we need to audit our ROS<char> extension methods to bring them into agreement with what String does. For example, should myString.IndexOf(otherString) and myString.AsSpan().IndexOf(otherString) be guaranteed to produce the same result? (Currently there is no such guarantee, since a different implied default StringComparison is used for each operation.)

[benaadams]

For example, should myString.IndexOf(otherString) and myString.AsSpan().IndexOf(otherString) be guaranteed to produce the same result?

Isn't the equivalent of Spans Array comparison? (Though array doesn't have an api to do this)

I wonder if we need to audit our ROS extension methods to bring them into agreement with what String does.

What string does for IndexOf confuses people https://github.com/dotnet/corefx/issues/32519, https://github.com/dotnet/corefx/issues/32285, https://github.com/dotnet/corefx/issues/31103, https://github.com/dotnet/corefx/issues/26293, https://github.com/dotnet/coreclr/issues/6087, https://github.com/dotnet/corefx/issues/9202, https://github.com/dotnet/corefx/issues/3973, https://github.com/dotnet/corefx/issues/1983, dotnet/core#1273,

[benaadams]

Of course its made weirder because string.Equals defaults to Ordinal as does string.IndexOf(char); so string.IndexOf(string) being CurrentCulture is an outlier?

[NinoFloris]

In 9.0 we're getting ROSpan params, we can easily make ROSpan locals through collection expressions for some time now (some nicely becoming RVA data, some still having room for improvement via InlineArray IMO), and when possible spans are generally preferred over arrays in new api surface.

However, after all these years we still can't use Spans of any type for searching due to the IEquatable constraint (which is not present on e.g. Array.IndexOf/Contains). Even common BCL types like Type (#31171), Uri (#97940, fixed in 9.0), IPAddress (#86589) don't implement IEquatable so this can quickly be a blocker for improving Array based code.

It's always jarring to run into a hard limitation on a core type and I hope to see the IEqualityComparer overloads added in .NET 10. Alternatively a variant taking an equality delegate would often be more convenient and strictly more general here.

EDIT: referencing #75639 as well, good to see the issue is on people's mind.