How do I tell the compiler that a type supports a specific interface?

[AlexRadch]

I want to write the IndexOf method for Span and type T without limits: public static int IndexOfEquals<T>(this Span<T> span, T value).

You can notice that if the type T implements the interface IEquatable<T> then for such T corresponding method is already exists and we just need to call it, but the compiler will not allow us to do that.

Next code have incorrect casting (T: IEquatable<T>)value. How to make it correct?

        public static int IndexOfEquals<T>(this Span<T> span, T value)
        {
            if (typeof(IEquatable<T>).IsAssignableFrom(typeof(T)))
                return System.MemoryExtensions.IndexOf(span, (T: IEquatable<T>)value);
            // something else
        }

How can I call System.MemoryExtensions.IndexOf method in case if T type supports IEquatable<T> interface?

[theunrepentantgeek]

What's wrong with this?

public static int IndexOfEquals<T>(this TimeSpan<T> span, T value)
{
    if (value is IEquatable<T> e)
    {
        return System.MemoryExtensions.IndexOf(span, e);
    }

    return 42;
}

[AlexRadch]

@theunrepentantgeek it is wrong because we have Span<T> span but not Span<IEquatable<T>> span. It was first that I tried.

[jnm2]

@AlexRadch I don't understand; the second parameter to MemoryExtensions.IndexOf must be T or ReadOnlySpan<T>, not IEquatable<T>. What's the larger purpose of your IndexOfEquals?

[svick]

@jnm2 The second parameter (of the overload of interest here) must be T where T : IEquatable<T>. As I understand it, the question here is: How can I call that method if I have unconstrained T (after somehow dynamically checking that T implements IEquatable<T>)?

[jnm2]

Ah, similar to #1315?

[svick]

@jnm2 Possibly, though that seems to be geared towards specializing for a list of specific types, not for all types that satisfy a constraint.

[svick]

@AlexRadch I think the usual answer to questions of the form "The C# type system doesn't let me do this, what do I do?" is "Bypass it by using reflection". The issue is that you can't use reflection with Span<T>, but you can also work around that. Though the work around I came up with is quite convoluted:

// Note: ignore the class names, couldn't think of better ones
abstract class ClosureBase<T>
{
    public static ClosureBase<T> Instance = (ClosureBase<T>)Activator.CreateInstance(
        typeof(Closure<>).MakeGenericType(typeof(T)));

    public abstract int IndexOf(ReadOnlySpan<T> span, T value);
}

sealed class Closure<T> : ClosureBase<T> where T : IEquatable<T>
{
    public override int IndexOf(ReadOnlySpan<T> span, T value) =>
    	MemoryExtensions.IndexOf(span, value);
}    
    
public static int IndexOfEquals<T>(this Span<T> span, T value)
{
    if (typeof(IEquatable<T>).IsAssignableFrom(typeof(T)))
    {
        return ClosureBase<T>.Instance.IndexOf(span, value);
    }
    return 42;
}

[jnm2]

If there was a way to reinterpret the Span<T> as a Span<EqualityWrapper<T>>, you could move the equality logic into EqualityWrapper<T>.Equals(T).

I'm new to the APIs and I can't figure out how to reinterpret the span memory this way, though. It should be safe since the size and layout of the wrapper struct should be identical to the bits in the T span.

[jnm2]

Wait, think I got it. This is passing my tests:

public static unsafe int IndexOfEquals<T>(this Span<T> span, T value)
{
    fixed (void* pointer = &Unsafe.As<T, byte>(ref span.GetPinnableReference()))
    {
        return System.MemoryExtensions.IndexOf(
            MemoryMarshal.CreateSpan(ref Unsafe.AsRef<EqualityWrapper<T>>(pointer), span.Length),
            new EqualityWrapper<T>(value));
    }
}

private readonly struct EqualityWrapper<T> : IEquatable<EqualityWrapper<T>>
{
    private readonly T value;

    public EqualityWrapper(T value)
    {
        this.value = value;
    }

    public bool Equals(EqualityWrapper<T> other)
    {
        // Whatever you want here—this is what I’d probably go for.
        return EqualityComparer<T>.Default.Equals(value, other.value);
    }

    public override bool Equals(object obj)
    {
        return obj is EqualityWrapper<T> other && Equals(other);
    }

    public override int GetHashCode()
    {
        return value == null ? 0 : value.GetHashCode();
    }
}

[jnm2]

The above also handles searches for null properly, whereas System.MemoryExtensions.IndexOf throws!

[AlexRadch]

@jnm2 Thanks for your very cool code!

[AlexRadch]

@svick Thanks for your very cool code! I think it is more tricky code than @jnm2 code but more fast.
@jnm2 code will remove optimizations for standard types like string or int.

[jnm2]

@jkotas Could you please check that my code is safe, interpreting contiguous T bits as contiguous WrapperStruct<T> bits?

[jnm2]

@AlexRadch

@jnm2 code will remove optimizations for standard types like string or int.

I don't think this is the case. EqualityComparer<T>.Default.Equals is a JIT instrinsic and compiles to the same code as comparing ints with == when T is int.

Compare: generic versus handwritten specialized int; the asm is the same.

[AlexRadch]

@jnm2 I think that for some standard types like char or byte method IndexOf<T> does not use IEquatable<T> interface at all for speed. But it will use this interface for EqualityWrapper<char> type.

[jkotas]

@jkotas Could you please check that my code is safe

Yes, it should work fine, but I think it is unnecessary ceremony. You can just have a simple loop (maybe unrolled) to achieve the same effect. You are not gaining much by bending backwards to call System.MemoryExtensions.IndexOf.

some standard types like char or byte method IndexOf does not use IEquatable interface

Correct. These optimizations won't kick in for the above.

[jnm2]

@AlexRadch Ah, yes I see.

@jkotas Thank you! Good to know that.

[mikedn]

Seem like the "reinterpret" acrobatics can be reduced using MemoryMarshal.Cast

Span<Foo> s = new Foo[42];
Span<EqualityWrapper<Foo>> e = MemoryMarshal.Cast<Foo, EqualityWrapper<Foo>>(s);

[jnm2]

@mikedn We need to use it with unconstrained generics. That fails at both compile time (TTo is where TTo : struct) and runtime:

        public static Span<TTo> Cast<TFrom, TTo>(Span<TFrom> span)
            where TFrom : struct
            where TTo : struct
        {
            if (RuntimeHelpers.IsReferenceOrContainsReferences<TFrom>())
                ThrowHelper.ThrowInvalidTypeWithPointersNotSupported(typeof(TFrom));
            if (RuntimeHelpers.IsReferenceOrContainsReferences<TTo>())
                ThrowHelper.ThrowInvalidTypeWithPointersNotSupported(typeof(TTo));

[jnm2]

@jkotas

Correct. These optimizations won't kick in for the above.

Actually, what is preventing the EqualityWrapper<int>.Equals call from being inlined?

[mikedn]

We need to use it with unconstrained generics. That fails at both compile time (TTo is where TTo : struct) and runtime

Ah, right, that's unfortunate. One can anyway achieve the same thing without using Cast so the restriction seems a bit pointless.

[tannergooding]

There should probably just be a MemoryExtensions.IndexOf(Span<T>, T, IEqualityComparer<T>) overload, to cover the case where T doesn't implement IEquatable<T>

[jkotas]

Actually, what is preventing the EqualityWrapper.Equals call from being inlined?

Nothing fundamental. Inlining is not the optimization dropped here. The optimization dropped here is the manual vectorization for byte, etc.

[jnm2]

These are solutions to @AlexRadch's specific problem, but the general problem could be solved with #399. Each interface check could cause the code inside the succeeding branch to intersect the type (T & IEnumerable<T> etc). Pretty harrowing to implement without CLR support, though, since the compiler would have to do the same reflection workaround for generic constraints that @svick posted at the top.

@jkotas It would be pretty cool if it could be both inlined and vectorized.

[AlexRadch]

I created proposal to add pattern matching for types #1839. Also my proposal mostly is duplicate of #631 proposal.
So I think pattern matching for types should be added to c# in future.