[API Proposal]: Add `allows ref struct` to `TComparer` in BinarySearch

[agocke]

EDITED on 6/17/2024 by @stephentoub to add a few more overloads

Background and motivation

There are a number of instances where a user might like to perform a binary search using a ref struct. For example, a table of strings could be searched with a ReadOnlySpan<char>, potentially avoiding additional string allocations.

API Proposal

namespace System;

public static partial class MemoryExtensions
{
    public static int BinarySearch<T, TComparable>(this Span<T> span, TComparable comparable)
        where TComparable : IComparable<T>
+       , allows ref struct
    public static int BinarySearch<T, TComparer>(this ReadOnlySpan<T> span, T value, TComparer comparer)
+       where T : allows ref struct
        where TComparer: IComparer<T>
+       , allows ref struct
    public static int BinarySearch<T, TComparable>(this Span<T> span, TComparable comparable)
        where TComparable : IComparable<T>
+       , allows ref struct
    public static int BinarySearch<T, TComparer>(this ReadOnlySpan<T> span, T value, TComparer comparer)
+       where T : allows ref struct
        where TComparer: IComparer<T>
+       , allows ref struct
}

API Usage

var a = new string[] {
   "a",
   "b",
   "c",
};
// Sort
...

int index = a.BinarySearch(new RosComparable("b"));

ref struct RosComparable(ReadOnlySpan<char> span) : IComparable<string>
{
    private readonly ReadOnlySpan<char> _span;
    public int CompareTo(string s) => _span.SequenceCompareTo(s.AsSpan());
}

Alternative Designs

There's another overload for BinarySearch that takes two values. We could mark the T in that one as allows ref struct and rely on the comparer to handle it. That seems like a fine addition, but not a replacement. If there's already a dedicated "key" struct being used for lookup, this would mean creating a new comparer for no reason.

Risks

These are static methods, so none. The only actual changes required to implement this API change is adding allows ref struct in a few more places.

[dotnet-policy-service]

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