[API Proposal]: Employ allows ref struct in comparer interfaces

[hamarb123]

EDITED on 6/17/2024 by @stephentoub to add more interfaces

Background and motivation

Similar to #102671.
Similar to #103270.
I discovered this gap as I attempted to pre-emptively implement .NET 9 allows ref struct on some of my own APIs behind a #if to see which APIs missing it would cause me problems.
We have done the same thing for IEnumerable<T> and IEnumerator<T> already.

API Proposal

namespace System.Collections.Generic;

public interface IComparable<T>
+   where T : allows ref struct
{
    ...
}

public interface IComparer<in T>
+   where T : allows ref struct
{
    ...
}

public interface IEquatable<T>
+   where T : allows ref struct
{
    ...
}

public interface IEqualityComparer<in T>
+    where T : allows ref struct
{
    ...
}

public interface IAlternateEqualityComparer<in TAlternate, T>
    where TAlternate : allows ref struct
+   where T : allows ref struct
{
    ...
}

API Usage

struct SpanSequenceComparer<T> : IEqualityComparer<ReadOnlySpan<T>>, IEqualityComparer<Span<T>>
{
    public readonly bool Equals(ReadOnlySpan<T> x, ReadOnlySpan<T> y)
    {
        if (x.Length != y.Length) return false;
        for (int i = 0; i < x.Length; i++)
        {
            if (!EqualityComparer<T>.Default.Equals(x[i], y[i])) return false;
        }
        return true;
    }

    public readonly bool Equals(Span<T> x, Span<T> y) => Equals((ReadOnlySpan<T>)x, (ReadOnlySpan<T>)y);

    public readonly int GetHashCode(ReadOnlySpan<T> obj)
    {
        HashCode hc = new();
        hc.Add(obj.Length);
        for (int i = 0; i < obj.Length; i++) hc.Add(EqualityComparer<T>.Default.GetHashCode(obj[i]));
        return hc.ToHashCode();
    }

    public readonly int GetHashCode(Span<T> obj) => GetHashCode((ReadOnlySpan<T>)obj);
}

Alternative Designs

Also implement on readonly collection types:

public interface IReadOnlyCollection<out T>
+    where T : allows ref struct
{
    ...
}

public interface IReadOnlyList<out T>
+    where T : allows ref struct
{
    ...
}

public interface IReadOnlySet<T>
+    where T : allows ref struct
{
    ...
}

Risks

These are interfaces, so none really.

[dotnet-policy-service]

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

[eiriktsarpalis]

Having written ISpanEqualityComparer<T> interfaces before, I can see the value in doing this to the comparison types. I would probably add it to some of the helper methods as well, such as EqualityComparer<T>.Create, Comparison<T> and Comparer<T>.Create.

Not sure if there's huge value in propagating this to all collection interfaces though, we did this with IEnumerable<T> and the use cases are limited, to say the least. Wouldn't hurt adding them either.

@stephentoub thoughts?

[stephentoub]

Constraining the T in IEqualityComparer<T> and IComparer<T> seems fine.

Comparison<T> is already annotated.

We can't do Comparer<T>.Create, at least not without changing other code in its implementation, because that generic parameter is on the type level and the T is already used in unsupported ways.

I'm skeptical of other interfaces like ICollection<T>, where you need to implement methods like Add(T). In fact looking at the interface, I don't think that's even possible, since it uses T[] in its APIs and that can't be done with a ref struct.

[eiriktsarpalis]

@hamarb123 would it be possible to update the API proposal to reflect feedback?

[hamarb123]

I'm skeptical of other interfaces like ICollection<T>, where you need to implement methods like Add(T). In fact looking at the interface, I don't think that's even possible, since it uses T[] in its APIs and that can't be done with a ref struct.

My understanding is that implementing ICollection<T> and IList<T>, even when mutating is not possible, and even when resizing makes no sense, is very, very common. For example, ImmutableArray<T> implements all the collection interfaces (other than the set ones obviously).

We can't do Comparer<T>.Create, at least not without changing other code in its implementation, because that generic parameter is on the type level and the T is already used in unsupported ways.

I don't really see what the issue is here - are you talking about the non-generic API overloads? Boxing is pretty easy to work around by using RuntimeHelpers.Box (I've already implemented my own helper API for boxing with allows ref struct). Edit - I just realised it's unboxing lol, I don't know how to implement that one yet lol, nevermind.

[stephentoub]

My understanding is that implementing ICollection and IList

It is simply not possible to mark the T in these interfaces as allows ref struct. ICollection<T>.CopyTo accepts a T[].

I don't really see what the issue is here

I wrote "at least not without changing other code in its implementation". If you try to mark the T in Comparer<T> as allows ref struct, it will not compile without doing surgery on the code.

[hamarb123]

Ok, I have updated it - I missed the CopyTo method when looking at them 😄

[eiriktsarpalis]

Even if technically feasible, I still question the value of allowing ref structs in the other collection interfaces, ref types seem fundamentally irreconcilable with these abstractions. IEnumerable is different in that respect since it can be used to implement streaming.

Which reminds me -- we should add IAsyncEnumerable<T>/IAsyncEnumerator<T> to that list.

[stephentoub]

Which reminds me -- we should add IAsyncEnumerable/IAsyncEnumerator to that list.

Those are already annotated.

[eiriktsarpalis]

Oh, ok. I thought they had missed the first round.

[hamarb123]

Even if technically feasible, I still question the value of allowing ref structs in the other collection interfaces, ref types seem fundamentally irreconcilable with these abstractions.

I don't think it's fundamentally irreconcilable at all - I think it makes perfect sense to have a readonly list where you're able to lookup a span at any index for example.

[eiriktsarpalis]

I think it makes perfect sense to have a readonly list where you're able to lookup a span at any index for example.

I saw the example that you shared earlier, but I struggle to see how this could be considered a valid collection implementation or where it could be used meaningfully. Perhaps sharing the full implementation + a consuming application might illuminate things a bit more.

[stephentoub]

I don't think we should do this for any of the readonly collection ones, either. From my perspective, it's a mistake of history that IReadOnlyCollection doesn't include members like CopyTo, and I'd like to reserve the ability to add those later as DIMs, plus possibly methods like ToArray. Making T here allows ref struct ptevents us from ever doing so. I don't believe the reward outweighs the risk.

[hamarb123]

I don't think we should do this for any of the readonly collection ones, either. From my perspective, it's a mistake of history that IReadOnlyCollection doesn't include members like CopyTo, and I'd like to reserve the ability to add those later as DIMs, plus possibly methods like ToArray. Making T here allows ref struct ptevents us from ever doing so. I don't believe the reward outweighs the risk.

Yeah, okay, makes enough sense, I will remove them.

I saw the example that you shared earlier, but I struggle to see how this could be considered a valid collection implementation or where it could be used meaningfully. Perhaps sharing the full implementation + a consuming application might illuminate things a bit more.

Sorry, I didn't get a chance to reply to this :)