Proposal: Pattern match via generic constraint

[benaadams]

Pattern match via generic constraint

from dotnet/roslyn#22092 (comment) and https://github.com/dotnet/coreclr/issues/12877#issuecomment-329247453

Summary

To allow non-boxing binding for value types in generic types/methods that themselves don't have the constraint applied (bind to original argument rather than cast/converted result)

Proposal

Pattern to match generic constraint's where against the generic type identifier and change : for is

Note: Using typeof would be a Type variable, so not be same

If pattern

Change : for is

Binding change

class MyClass<TKey> // No generic constraint
{
    public static bool Equals(TKey key0, TKey key1)
    {
        if (TKey is IEquatable<TKey>){
            // key0 is now known to be constrained via IEquatable<TKey>
            // so this can be a constrained callvirt to `IEquatable<TKey>.Equals`
            return key0.Equals(key1);
        }
    }

    // not constrained so callvirt to `Object.Equals`
    return key0.Equals(key1);
}

Allowed call change/expanded methods

interface IMyInterface1
{
    void DoSomething();
}

interface IMyInterface2
{
    void DoSomethingElse();
}

class MyClass<T> where T : IMyInterface1
{
    public static void Do(T value)
    {
        if (T is IMyInterface2)
        {
            // value is now known to be constrained via IMyInterface2
            // so can call DoSomethingElse on it
            value.DoSomethingElse();
        }

        // constrained via class so valid
        value.DoSomething();
        // not constrained so compile error
        // value.DoSomethingElse();
    }
}

Switch pattern

Switch on generic type identifier and change : for is

public static bool Equals(TKey key0, TKey key1)
{
    bool result;
    switch (TKey)
    {
        case is struct, IEquatable<TKey>:
            result = key0.Equals(key1);
            break;
        case is IEquatable<TKey>:
            result = key0?.Equals(key1) ?? key1 == null;
            break;
        default:
            result = s_defaultComparer.Equals(key0, key1);
            break;
    }
    return result;
}

Current workarounds for constraint

Interface constraint

Runtime test

public int KeyHashCode(TKey key)
{
    if (typeof(IEquatable<>).MakeGenericType(typeof(TKey)).IsAssignableFrom(typeof(TKey)))
    {
        // Not currently valid
        // Bind to IEquatable<TKey>.GetHashCode()
        //   rather than Object.GetHashCode()
        return key.GetHashCode();
    }
    else
    {
        // Binds to Object.GetHashCode()
        return key.GetHashCode();
    }
}

Compile-time

public int KeyHashCode<TKey>(TKey key) where TKey : IEquatable<TKey>
{
    return key.GetHashCode();
}

public int KeyHashCode(object key)
{
    return key.GetHashCode();
}

Have to go via a convoluted runtime construction to get it to work as is done by Dictionary; to create EqualityComparer; however then becomes non-inlinable virtual calls. (see RavenDB: Fast Dictionary and struct generic arguments)

Struct constraint

Runtime (ex. nullables)

if (default(T) != null)

Generic constraint

 where TKey : struct

Class constraint

Runtime (inc. nullables)

if (default(T) == null)

Generic constraint

 where TKey : class

Other constraint

Is also : new() constraint

Notes

Runtime checks for struct and class with default(T) are recognised and the alternate path is elided.

Proposed Use

System.Collections.Generic.Dictionary

class Dictionary<TKey, TValue>
{
    private static readonly EqualityComparer<TKey> s_defaultComparer;
    private readonly IEqualityComparer<TKey> _customComparer;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public bool KeyEquals(TKey key0, TKey key1)
    {
        bool result;
        if (_customComparer == null)
        {
            if (TKey is struct && TKey is IEquatable<TKey>)
            {
                result = key0.Equals(key1);
            }
            else if (TKey is IEquatable<TKey>)
            {
                result =  key0?.Equals(key1) ?? key1 == null;;
            }
            else
            {
                result = s_defaultComparer.Equals(key0, key1);
            }
        }
        else
        {
            result = _customComparer.Equals(key0, key1);
        }

        return result;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public int KeyHashCode(TKey key)
    {
        int result;
        if (_customComparer == null)
        {
            if (TKey is struct && TKey is IEquatable<TKey>)
            {
                result = key.GetHashCode();
            }
            else if (TKey is IEquatable<TKey>)
            {
                result = key?.GetHashCode() ?? 0;
            }
            else
            {
                result = s_defaultComparer.GetHashCode(key);
            }
        }
        else
        {
            result = _customComparer.GetHashCode(key);
        }

        return result & 0x7FFFFFFF;
    }
}

/cc @AndyAyersMS @gafter @stephentoub

[redknightlois]

A Love emoji would not be enough to say what this would mean. This would be a game changer for the kind of performance work we do, we could throw away lots of workaround code and also open lots of venues to expand the abilities of the type of generic metaprogramming we are doing exploiting struct JIT optimization behavior.

[benaadams]

Switch example

For a strongly typed type collection; you have to test using typeof then cast via object back to T as there is no relation between the if and the return

TFeature FastFeatureGet<TFeature>()
{
    if (typeof(TFeature) == typeof(IHttpRequestFeature))
    {
        return (TFeature)(object)_currentIHttpRequestFeature;
    }
    if (typeof(TFeature) == typeof(IHttpResponseFeature))
    {
        return (TFeature)(object)_currentIHttpResponseFeature;
    }
    if (typeof(TFeature) == typeof(IHttpRequestIdentifierFeature))
    {
        return (TFeature)(object)_currentIHttpRequestIdentifierFeature;
    }
    if (typeof(TFeature) == typeof(IServiceProvidersFeature))
    {
        return (TFeature)(object)_currentIServiceProvidersFeature;
    }
    if (typeof(TFeature) == typeof(IHttpRequestLifetimeFeature))
    {
        return (TFeature)(object)_currentIHttpRequestLifetimeFeature;
    }
    if (typeof(TFeature) == typeof(IHttpConnectionFeature))
    {
        return (TFeature)(object)_currentIHttpConnectionFeature;
    }
    if (typeof(TFeature) == typeof(IHttpAuthenticationFeature))
    {
        return (TFeature)(object)_currentIHttpAuthenticationFeature;
    }
    if (typeof(TFeature) == typeof(IQueryFeature))
    {
        return (TFeature)(object)_currentIQueryFeature;
    }
    if (typeof(TFeature) == typeof(IFormFeature))
    {
        return (TFeature)(object)_currentIFormFeature;
    }
    if (typeof(TFeature) == typeof(IHttpUpgradeFeature))
    {
        return (TFeature)(object)_currentIHttpUpgradeFeature;
    }
    if (typeof(TFeature) == typeof(IResponseCookiesFeature))
    {
        return (TFeature)(object)_currentIResponseCookiesFeature;
    }
    if (typeof(TFeature) == typeof(IItemsFeature))
    {
        return (TFeature)(object)_currentIItemsFeature;
    }
    if (typeof(TFeature) == typeof(ITlsConnectionFeature))
    {
        return (TFeature)(object)_currentITlsConnectionFeature;
    }
    if (typeof(TFeature) == typeof(IHttpWebSocketFeature))
    {
        return (TFeature)(object)_currentIHttpWebSocketFeature;
    }
    if (typeof(TFeature) == typeof(ISessionFeature))
    {
        return (TFeature)(object)_currentISessionFeature;
    }
    if (typeof(TFeature) == typeof(IHttpMaxRequestBodySizeFeature))
    {
        return (TFeature)(object)_currentIHttpMaxRequestBodySizeFeature;
    }
    if (typeof(TFeature) == typeof(IHttpMinRequestBodyDataRateFeature))
    {
        return (TFeature)(object)_currentIHttpMinRequestBodyDataRateFeature;
    }
    if (typeof(TFeature) == typeof(IHttpMinResponseDataRateFeature))
    {
        return (TFeature)(object)_currentIHttpMinResponseDataRateFeature;
    }
    if (typeof(TFeature) == typeof(IHttpBodyControlFeature))
    {
        return (TFeature)(object)_currentIHttpBodyControlFeature;
    }
    if (typeof(TFeature) == typeof(IHttpSendFileFeature))
    {
        return (TFeature)(object)_currentIHttpSendFileFeature;
    }
    return (TFeature)ExtraFeatureGet(typeof(TFeature));
}

With the switch T has been constrained so there is no cast via object required and it becomes more compact and understandable

TFeature FastFeatureGet<TFeature>()
{
    switch (TFeature)
    {
        case is IHttpRequestFeature:
            return _currentIHttpRequestFeature;
        case is IHttpResponseFeature:
            return _currentIHttpResponseFeature;
        case is IHttpRequestIdentifierFeature:
            return _currentIHttpRequestIdentifierFeature;
        case is IServiceProvidersFeature:
            return _currentIServiceProvidersFeature;
        case is IHttpRequestLifetimeFeature:
            return _currentIHttpRequestLifetimeFeature;
        case is IHttpConnectionFeature:
            return _currentIHttpConnectionFeature;
        case is IHttpAuthenticationFeature:
            return _currentIHttpAuthenticationFeature;
        case is IQueryFeature:
            return _currentIQueryFeature;
        case is IFormFeature:
            return _currentIFormFeature;
        case is IHttpUpgradeFeature:
            return _currentIHttpUpgradeFeature;
        case is IResponseCookiesFeature:
            return _currentIResponseCookiesFeature;
        case is IItemsFeature:
            return _currentIItemsFeature;
        case is ITlsConnectionFeature:
            return _currentITlsConnectionFeature;
        case is IHttpWebSocketFeature:
            return _currentIHttpWebSocketFeature;
        case is ISessionFeature:
            return _currentISessionFeature;
        case is IHttpMaxRequestBodySizeFeature:
            return _currentIHttpMaxRequestBodySizeFeature;
        case is IHttpMinRequestBodyDataRateFeature:
            return _currentIHttpMinRequestBodyDataRateFeature;
        case is IHttpMinResponseDataRateFeature:
            return _currentIHttpMinResponseDataRateFeature;
        case is IHttpBodyControlFeature:
            return _currentIHttpBodyControlFeature;
        case is IHttpSendFileFeature:
            return _currentIHttpSendFileFeature;
    }
    return (TFeature)ExtraFeatureGet(typeof(TFeature));
}

[benaadams]

System.Numerics.Vector.ScalarAdd would change from

private static T ScalarAdd(T left, T right)
{
    if (typeof(T) == typeof(Byte))
    {
        return (T)(object)unchecked((Byte)((Byte)(object)left + (Byte)(object)right));
    }
    else if (typeof(T) == typeof(SByte))
    {
        return (T)(object)unchecked((SByte)((SByte)(object)left + (SByte)(object)right));
    }
    else if (typeof(T) == typeof(UInt16))
    {
        return (T)(object)unchecked((UInt16)((UInt16)(object)left + (UInt16)(object)right));
    }
    else if (typeof(T) == typeof(Int16))
    {
        return (T)(object)unchecked((Int16)((Int16)(object)left + (Int16)(object)right));
    }
    else if (typeof(T) == typeof(UInt32))
    {
        return (T)(object)unchecked((UInt32)((UInt32)(object)left + (UInt32)(object)right));
    }
    else if (typeof(T) == typeof(Int32))
    {
        return (T)(object)unchecked((Int32)((Int32)(object)left + (Int32)(object)right));
    }
    else if (typeof(T) == typeof(UInt64))
    {
        return (T)(object)unchecked((UInt64)((UInt64)(object)left + (UInt64)(object)right));
    }
    else if (typeof(T) == typeof(Int64))
    {
        return (T)(object)unchecked((Int64)((Int64)(object)left + (Int64)(object)right));
    }
    else if (typeof(T) == typeof(Single))
    {
        return (T)(object)unchecked((Single)((Single)(object)left + (Single)(object)right));
    }
    else if (typeof(T) == typeof(Double))
    {
        return (T)(object)unchecked((Double)((Double)(object)left + (Double)(object)right));
    }
    else
    {
        throw new NotSupportedException(SR.Arg_TypeNotSupported);
    }
}

To the much more svelte code below

private static T ScalarAdd(T left, T right)
{
    switch (T)
    {
        case is Byte:
            return unchecked((Byte)(left + right));
        case is SByte:
            return unchecked((SByte)(left + right));
        case is UInt16:
            return unchecked((UInt16)(left + right));
        case is Int16:
            return unchecked((Int16)(left + right));
        case is UInt32:
            return unchecked(left + right);
        case is Int32:
            return unchecked(left + right);
        case is UInt64:
            return unchecked(left + right);
        case is Int64:
            return unchecked(left + right);
        case is Single:
            return unchecked(left + right);
        case is Double:
            return unchecked(left + right);
        default:
            throw new NotSupportedException(SR.Arg_TypeNotSupported);
    }
}

[HaloFour]

@benaadams

What IL do you envision that compiling down to? How can the compiler avoid the "crazy" while retaining a verifiable assembly? I assume that this change will be accompanied by a number of CLR changes.

[benaadams]

@HaloFour removed the bit about boxing as apparently the verifier requires

IL_002B:  box         System.Numerics+Vector<>.T
IL_0030:  unbox.any   System.Byte

IL_0037:  box         System.Byte
IL_003C:  unbox.any   System.Numerics+Vector<>.T

To be happy...

So the IL for the two switch examples would likely be the same

[HaloFour]

@benaadams

If we're going to go down this route I think it's worthwhile to coordinate with the CLR/JIT so that the compiler can emit "better" IL and/or the JIT can be smarter about how it can generate code optimized for the given specialization.

[benaadams]

Updated c# equivalent and il

Syntactic C#

public partial class Dictionary<TKey, TValue> 
{
    private static readonly EqualityComparer<TKey> s_defaultComparer;
    private readonly IEqualityComparer<TKey> _customComparer;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public bool KeyEquals(TKey key0, TKey key1)
    {
        bool result;
        if (_customComparer == null)
        {
            if (TKey is struct && TKey is IEquatable<TKey>)
            {
                result = key0.Equals(key1);
            }
            else if (TKey is IEquatable<TKey>)
            {
                result =  key0?.Equals(key1) ?? key1 == null;;
            }
            else
            {
                result = s_defaultComparer.Equals(key0, key1);
            }
        }
        else
        {
            result = _customComparer.Equals(key0, key1);
        }

        return result;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public int KeyHashCode(TKey key)
    {
        int result;
        if (_customComparer == null)
        {
            if (TKey is struct && TKey is IEquatable<TKey>)
            {
                result = key.GetHashCode();
            }
            else if (TKey is IEquatable<TKey>)
            {
                result = key?.GetHashCode() ?? 0;
            }
            else
            {
                result = s_defaultComparer.GetHashCode(key);
            }
        }
        else
        {
            result = _customComparer.GetHashCode(key);
        }

        return result & 0x7FFFFFFF;
    }
}

Equivalent C#

public partial class Dictionary<TKey, TValue> where TKey : IEquatable<TKey>
{
    private static readonly EqualityComparer<TKey> s_defaultComparer;
    private readonly IEqualityComparer<TKey> _customComparer;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public bool KeyEquals(TKey key0, TKey key1)
    {
        bool result;
        if (_customComparer == null)
        {
            if (default(TKey) != null && typeof(IEquatable<TKey>).IsAssignableFrom(typeof(TKey)))
            {
                result = key0.Equals(key1);
            }
            else if (typeof(IEquatable<TKey>).IsAssignableFrom(typeof(TKey)))
            {
                result = key0?.Equals(key1) ?? key1 == null;
            }
            else
            {
                result = s_defaultComparer.Equals(key0, key1);
            }
        }
        else
        {
            result = _customComparer.Equals(key0, key1);
        }
        
        return result;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public int KeyHashCode(TKey key)
    {
        int result;
        if (_customComparer == null)
        {
            if (default(TKey) != null && typeof(IEquatable<TKey>).IsAssignableFrom(typeof(TKey)))
            {
                result = key.GetHashCode();
            }
            else if (typeof(IEquatable<TKey>).IsAssignableFrom(typeof(TKey)))
            {
                result = key?.GetHashCode() ?? 0;
            }
            else
            {
                result = s_defaultComparer.GetHashCode(key);
            }
        }
        else
        {
            result = _customComparer.GetHashCode(key);
        }

        return result & 0x7FFFFFFF;
    }
}

generated il

.method public hidebysig instance bool  KeyEquals(!TKey key0,
                                                  !TKey key1) cil managed aggressiveinlining
{
  // Code size       165 (0xa5)
  .maxstack  3
  .locals init (bool V_0,
           !TKey V_1)
  IL_0000:  ldarg.0
  IL_0001:  ldfld      class [System.Runtime]System.Collections.Generic.IEqualityComparer`1<!0> class System.Collections.Generic.Dictionary`2<!TKey,!TValue>::_customComparer
  IL_0006:  brtrue     IL_0095
  IL_000b:  ldloca.s   V_1
  IL_000d:  initobj    !TKey
  IL_0013:  ldloc.1
  IL_0014:  box        !TKey
  IL_0019:  brfalse.s  IL_0047
  IL_001b:  ldtoken    class [System.Runtime]System.IEquatable`1<!TKey>
  IL_0020:  call       class [System.Runtime]System.Type [System.Runtime]System.Type::GetTypeFromHandle(valuetype [System.Runtime]System.RuntimeTypeHandle)
  IL_0025:  ldtoken    !TKey
  IL_002a:  call       class [System.Runtime]System.Type [System.Runtime]System.Type::GetTypeFromHandle(valuetype [System.Runtime]System.RuntimeTypeHandle)
  IL_002f:  callvirt   instance bool [System.Runtime]System.Type::IsAssignableFrom(class [System.Runtime]System.Type)
  IL_0034:  brfalse.s  IL_0047
  IL_0036:  ldarga.s   key0
  IL_0038:  ldarg.2
  IL_0039:  constrained. !TKey
  IL_003f:  callvirt   instance bool class [System.Runtime]System.IEquatable`1<!TKey>::Equals(!0)
  IL_0044:  stloc.0
  IL_0045:  br.s       IL_00a3
  IL_0047:  ldtoken    class [System.Runtime]System.IEquatable`1<!TKey>
  IL_004c:  call       class [System.Runtime]System.Type [System.Runtime]System.Type::GetTypeFromHandle(valuetype [System.Runtime]System.RuntimeTypeHandle)
  IL_0051:  ldtoken    !TKey
  IL_0056:  call       class [System.Runtime]System.Type [System.Runtime]System.Type::GetTypeFromHandle(valuetype [System.Runtime]System.RuntimeTypeHandle)
  IL_005b:  callvirt   instance bool [System.Runtime]System.Type::IsAssignableFrom(class [System.Runtime]System.Type)
  IL_0060:  brfalse.s  IL_0086
  IL_0062:  ldarg.1
  IL_0063:  box        !TKey
  IL_0068:  brtrue.s   IL_0075
  IL_006a:  ldarg.2
  IL_006b:  box        !TKey
  IL_0070:  ldnull
  IL_0071:  ceq
  IL_0073:  br.s       IL_0083
  IL_0075:  ldarga.s   key0
  IL_0077:  ldarg.2
  IL_0078:  constrained. !TKey
  IL_007e:  callvirt   instance bool class [System.Runtime]System.IEquatable`1<!TKey>::Equals(!0)
  IL_0083:  stloc.0
  IL_0084:  br.s       IL_00a3
  IL_0086:  ldsfld     class [System.Collections]System.Collections.Generic.EqualityComparer`1<!0> class System.Collections.Generic.Dictionary`2<!TKey,!TValue>::s_defaultComparer
  IL_008b:  ldarg.1
  IL_008c:  ldarg.2
  IL_008d:  callvirt   instance bool class [System.Collections]System.Collections.Generic.EqualityComparer`1<!TKey>::Equals(!0,
                                                                                                                            !0)
  IL_0092:  stloc.0
  IL_0093:  br.s       IL_00a3
  IL_0095:  ldarg.0
  IL_0096:  ldfld      class [System.Runtime]System.Collections.Generic.IEqualityComparer`1<!0> class System.Collections.Generic.Dictionary`2<!TKey,!TValue>::_customComparer
  IL_009b:  ldarg.1
  IL_009c:  ldarg.2
  IL_009d:  callvirt   instance bool class [System.Runtime]System.Collections.Generic.IEqualityComparer`1<!TKey>::Equals(!0,
                                                                                                                         !0)
  IL_00a2:  stloc.0
  IL_00a3:  ldloc.0
  IL_00a4:  ret
} // end of method Dictionary`2::KeyEquals

.method public hidebysig instance int32  KeyHashCode(!TKey key) cil managed aggressiveinlining
{
  // Code size       156 (0x9c)
  .maxstack  2
  .locals init (int32 V_0,
           !TKey V_1)
  IL_0000:  ldarg.0
  IL_0001:  ldfld      class [System.Runtime]System.Collections.Generic.IEqualityComparer`1<!0> class System.Collections.Generic.Dictionary`2<!TKey,!TValue>::_customComparer
  IL_0006:  brtrue.s   IL_0087
  IL_0008:  ldloca.s   V_1
  IL_000a:  initobj    !TKey
  IL_0010:  ldloc.1
  IL_0011:  box        !TKey
  IL_0016:  brfalse.s  IL_0043
  IL_0018:  ldtoken    class [System.Runtime]System.IEquatable`1<!TKey>
  IL_001d:  call       class [System.Runtime]System.Type [System.Runtime]System.Type::GetTypeFromHandle(valuetype [System.Runtime]System.RuntimeTypeHandle)
  IL_0022:  ldtoken    !TKey
  IL_0027:  call       class [System.Runtime]System.Type [System.Runtime]System.Type::GetTypeFromHandle(valuetype [System.Runtime]System.RuntimeTypeHandle)
  IL_002c:  callvirt   instance bool [System.Runtime]System.Type::IsAssignableFrom(class [System.Runtime]System.Type)
  IL_0031:  brfalse.s  IL_0043
  IL_0033:  ldarga.s   key
  IL_0035:  constrained. !TKey
  IL_003b:  callvirt   instance int32 [System.Runtime]System.Object::GetHashCode()
  IL_0040:  stloc.0
  IL_0041:  br.s       IL_0094
  IL_0043:  ldtoken    class [System.Runtime]System.IEquatable`1<!TKey>
  IL_0048:  call       class [System.Runtime]System.Type [System.Runtime]System.Type::GetTypeFromHandle(valuetype [System.Runtime]System.RuntimeTypeHandle)
  IL_004d:  ldtoken    !TKey
  IL_0052:  call       class [System.Runtime]System.Type [System.Runtime]System.Type::GetTypeFromHandle(valuetype [System.Runtime]System.RuntimeTypeHandle)
  IL_0057:  callvirt   instance bool [System.Runtime]System.Type::IsAssignableFrom(class [System.Runtime]System.Type)
  IL_005c:  brfalse.s  IL_0079
  IL_005e:  ldarg.1
  IL_005f:  box        !TKey
  IL_0064:  brtrue.s   IL_0069
  IL_0066:  ldc.i4.0
  IL_0067:  br.s       IL_0076
  IL_0069:  ldarga.s   key
  IL_006b:  constrained. !TKey
  IL_0071:  callvirt   instance int32 [System.Runtime]System.Object::GetHashCode()
  IL_0076:  stloc.0
  IL_0077:  br.s       IL_0094
  IL_0079:  ldsfld     class [System.Collections]System.Collections.Generic.EqualityComparer`1<!0> class System.Collections.Generic.Dictionary`2<!TKey,!TValue>::s_defaultComparer
  IL_007e:  ldarg.1
  IL_007f:  callvirt   instance int32 class [System.Collections]System.Collections.Generic.EqualityComparer`1<!TKey>::GetHashCode(!0)
  IL_0084:  stloc.0
  IL_0085:  br.s       IL_0094
  IL_0087:  ldarg.0
  IL_0088:  ldfld      class [System.Runtime]System.Collections.Generic.IEqualityComparer`1<!0> class System.Collections.Generic.Dictionary`2<!TKey,!TValue>::_customComparer
  IL_008d:  ldarg.1
  IL_008e:  callvirt   instance int32 class [System.Runtime]System.Collections.Generic.IEqualityComparer`1<!TKey>::GetHashCode(!0)
  IL_0093:  stloc.0
  IL_0094:  ldloc.0
  IL_0095:  ldc.i4     0x7fffffff
  IL_009a:  and
  IL_009b:  ret
} // end of method Dictionary`2::KeyHashCode

[bondsbw]

Is there really a need for the where? Could

if (T is IMyInterface2) 
...

work just as well?

[benaadams]

So rather than

if (where TKey is struct, IEquatable<TKey>)

Go for

if (TKey is struct && TKey is IEquatable<TKey>)

Which is equivalent to

if (default(TKey) != null && typeof(IEquatable<TKey>).IsAssignableFrom(typeof(TKey))

An opens up non-boxing constrained calls on the types; within scope of the test?

Could work :)

[redknightlois]

The pattern is pretty clear and repetitive; perfect case for a JIT enabled optimization. Probably @AndyAyersMS or @CarolEidt could shed some light into the viability of such an approach from the JIT point of view.

[benaadams]

Dropped the where from the samples; does look better.

@redknightlois I think for structs it should be able to be elided as they each have their own version of the generic. For classes; with their shared generic the check would remain I think? So would be cost vs opening up of api.

However you can always put a struct wrapper on a class to get the elided struct version

public struct KeyWrapper<TKey> : IEquatable<KeyWrapper<TKey>> where TKey : IEquatable<TKey>
{
    private TKey _key;

    public static implicit operator KeyWrapper<TKey>(TKey key) => new KeyWrapper<TKey> { _key = key };
    public static implicit operator TKey(KeyWrapper<TKey> key) => key._key;
    public bool Equals(KeyWrapper<TKey> other) => _key?.Equals(other._key) ?? other._key == null;
    public int GetHashCode(KeyWrapper<TKey> obj) => _key?.GetHashCode() ?? 0;
}

And even use custom Equals and GetHashCode in the wrapper, rather than going via an interface IEqualityComparer

[redknightlois]

Yes, but if you know the type some devirtualization could happen and in very specific cases the inliner will kick-in AFAIK. I presume if C# is going to write an specific pattern, there could exist some optimizations that would ensure in say 90% of the cases that the devirtualization may happen.

[benaadams]

Added struct wrapper code above would should make it transparent other than at Dictionary declaration and new.

Also you could put custom equality in the wrapper if you didn't want to defer directly to the classes equality; and with the change it wouldn't use the Interface based IEqualityComparer (or virtual EqualityComparer)

[CarolEidt]

The pattern is pretty clear and repetitive; perfect case for a JIT enabled optimization. Probably @AndyAyersMS or @CarolEidt could shed some light into the viability of such an approach from the JIT point of view.

@AndyAyersMS has been working on type-related optimizations, so he's probably in the best position to judge.

Regarding the "is XX" syntax, this seems reasonable for structs and classes, but I would think a different "operator" would be needed for interfaces, since you couldn't really use case is IFoo in a switch statement since that could result in ambiguities. Or maybe interface types would simply not be allowed in a case is context?

[AndyAyersMS]

I'll have to look fairly closely at the details before I can comment. May be a day or two.

[benaadams]

since you couldn't really use case is IFoo in a switch statement since that could result in ambiguities.

This is currently the case with pattern matching and switch currently; the order is important, so it resolves from top to bottom (unlike switch with constants).

So currently in C#7.0 you can switch on the variable and do:

T shape;

switch (shape)
{
    case ISquare s when s.Side == 0:
    case ICircle c when c.Radius == 0:
    case ITriangle t when t.Base == 0 || t.Height == 0:
    case IRectangle r when r.Length == 0 || r.Height == 0:
        return 0;
    case ISquare s:
        return s.Side * s.Side;
    case ICircle c:
        return c.Radius * c.Radius * Math.PI;
    case ITriangle t:
        return t.Base * t.Height * 2;
    case IRectangle r:
        return r.Length * r.Height;
    default:
        throw new ArgumentException(
            message: "shape is not a recognized shape",
            paramName: nameof(shape));
}

The issue with the current pattern matching is its an as cast to another variable; at which point it allocates to a box for that type and the methods are executed on the box via interface dispatch on that second variable.

I originally thought this behavior was a bug with pattern matching dotnet/roslyn#22092; however there are a much wider range of cases where the switching on a variable is valid (from pattern-matching with generics)

Certain combinations of static type of the left-hand-side and the given type are considered incompatible and result in compile-time error. A value of static type E is said to be pattern compatible with the type T if there exists an identity conversion, an implicit reference conversion, a boxing conversion, an explicit reference conversion, or an unboxing conversion from E to T, or if either E or T is an open type. It is a compile-time error if an expression of type E is not pattern compatible with the type in a type pattern that it is matched with.

So the suggestion is adding a new type of switch; which is on the generic type rather than the variable and then operating on the original variable rather than a converted one.

T shape;

switch (T)
{
    case is ISquare when shape.Side == 0:
    case is ICircle when shape.Radius == 0:
    case is ITriangle when shape.Base == 0 || shape.Height == 0:
    case is IRectangle when shape.Length == 0 || shape.Height == 0:
        return 0;
    case is ISquare:
        return shape.Side * shape.Side;
    case is ICircle:
        return shape.Radius * shape.Radius * Math.PI;
    case is ITriangle:
        return shape.Base * shape.Height * 2;
    case is IRectangle:
        return shape.Length * shape.Height;
    default:
        throw new ArgumentException(
            message: "shape is not a recognized shape",
            paramName: nameof(shape));
}

Then for structs there is no-boxing and the calls are direct rather than via interface dispatch.

[benaadams]

All the examples generally on pattern matching are off object rather than T so structs would be pre-boxed 😿

[gafter]

The code that this issue proposes to be generated is illegal IL. That is because the constrained call requires that the receiver type be statically derived from the constrained type. That is not the case in the code in these examples. This proposal requires a set of changes to valid IL, and it requires those changes to be implemented before (or at the same time as) the proposed language changes. There is currently no proposal to make that change to the CLR.

As for switching on a value of type System.Type, have you looked at #356 ?

[gafter]

Also, in

class MyClass<TKey> // No generic constraint
{
    public static bool Equals(TKey key0, TKey key1)
    {
        if (TKey is IEquatable<TKey>){
            // key0 is now known to be constrained via IEquatable<TKey>
            // so this can be a constrained callvirt to `IEquatable<TKey>.Equals`
            return key0.Equals(key1);
        }
    }

    // not constrained so callvirt to `Object.Equals`
    return key0.Equals(key1);
}

• No matter what kind of call you want, the C# compiler resolves an invocation expression like key0.Equals(key1) by looking for methods named Equals in the type of key0. Since key0's type is an unconstrained type parameter, the only Equals instance method found by name lookup is the one in Object. So you are proposing some kind of name lookup magic as well to find something in an interface that is not part of key0's static type.

• The constrained call is designed to be used with a type parameter as its constraint, not an interface type, as its purpose is to avoid boxing when the type of the constraint is a value type. But if you are using an interface type as the constraint type, then it is not a value type, and so boxing is required. Even if constrained were safe to use as you suggested, you would not avoid the boxing.

[benaadams]

I'm suggesting for the pattern the TKey is IEquatable<TKey> is the constraint; not a cast to interface; because if typeof(IEquatable<TKey>).IsAssignableFrom(typeof(TKey)) then you know the constraint is valid, whether TKey is actually a struct, class or interface?

So expressing it in terms of an inner function it would be

class MyClass<TKey> // No generic constraint
{
    public static bool Equals(TKey key0, TKey key1)
    {
        if (TKey is IEquatable<TKey>)
        {
            return ConstrainedEquals(key0, key1);
        }

        // not constrained so callvirt to `Object.Equals`
        return key0.Equals(key1);

        bool ConstrainedEquals(TKey cKey0, TKey cKey1) where TKey : IEquatable<TKey>
        {
            return cKey0.Equals(cKey1);
        }
    }
}

[gafter]

@benaadams One does not execute constraints as part of the control-flow of statements. Constraints are expanded at compile-time based on the static (not dynamic) type of type parameters. Treating a constraint as executable code is essentially asking to do away with the static type system and compilation.

[benaadams]

Which is why I'm suggesting a language addition...

So

if (TKey is struct && TKey is IEquatable<TKey>)

Are static type system constraints (which works in function)

default(TKey) != null && typeof(IEquatable<TKey>).IsAssignableFrom(typeof(TKey))

Is an implementation detail to give a runtime guarantee. For a struct, to the Jit they are constants; so it can remove the test and either remove the block; or remove the else.

Could put it in a readonly static if the Jit didn't recognize it immediately as a const; to get it to still elide e.g.

readonly static bool IsEquatable = typeof(IEquatable<TKey>).IsAssignableFrom(typeof(TKey));

public staic bool KeyEquals(TKey key0, TKey key1)
{
    bool result;
    if (_customComparer == null)
    {
        if (default(TKey) != null && IsEquatable)
        {
            result = key0.Equals(key1);
        }
        else if (IsEquatable)
        {
            result = key0?.Equals(key1) ?? key1 == null;
        }
        else
        {
            result = s_defaultComparer.Equals(key0, key1);
        }
    }
    else
    {
        result = _customComparer.Equals(key0, key1);
    }
    
    return result;
}

The output il whether having the constraint or not is not wildly different

.method public hidebysig newslot virtual 
        instance bool  Equals(!TKey key0,
                              !TKey key1) cil managed
{
  // Code size       20 (0x14)
  .maxstack  8
  IL_0000:  ldarga.s   key0
  IL_0002:  ldarg.2
  IL_0003:  box        !TKey
  IL_0008:  constrained. !TKey
  IL_000e:  callvirt   instance bool [System.Runtime]System.Object::Equals(object)
  IL_0013:  ret
} // end of method EqualityComparer`1::Equals

.method public hidebysig virtual instance bool 
        Equals(!TKey key0,
               !TKey key1) cil managed
{
  // Code size       15 (0xf)
  .maxstack  8
  IL_0000:  ldarga.s   key0
  IL_0002:  ldarg.2
  IL_0003:  constrained. !TKey
  IL_0009:  callvirt   instance bool class [System.Runtime]System.IEquatable`1<!TKey>::Equals(!0)
  IL_000e:  ret
} // end of method GenericEqualityComparer`1::Equals

The constraint drops box !TKey, and changes

callvirt   instance bool [System.Runtime]System.Object::Equals(object)

to

callvirt   instance bool class [System.Runtime]System.IEquatable`1<!TKey>::Equals(!0)

Currently the workaround to apply the constraint to a non-constrained class is something like

public class EqualityComparer<TKey>
{
    public virtual bool Equals(TKey key0, TKey key1) => key0.Equals(key1);
}

public class GenericEqualityComparer<TKey> : EqualityComparer<TKey> where TKey : IEquatable<TKey>
{
    public override bool Equals(TKey key0, TKey key1) => key0.Equals(key1);
}

public partial class Dictionary<TKey, TValue>
{
    private static readonly EqualityComparer<TKey> s_comparer = CreateComparer();

    public static bool KeyEquals(TKey key0, TKey key1)
    {
        // Equality is constrained
        return s_comparer.Equals(key0, key1);
    }

    private static EqualityComparer<TKey> CreateComparer()
    {
        if (typeof(IEquatable<TKey>).IsAssignableFrom(typeof(TKey)))
        {
            Type type = typeof(GenericEqualityComparer<>).MakeGenericType(typeof(TKey));
            return (EqualityComparer<TKey>)Activator.CreateInstance(type);
        }
        else
        {
            return new EqualityComparer<TKey>();
        }
    }
}

Which avoids the boxing; but then involves non-inlinable virtual calls, so looses on performance (and is a bit horrible).

The coreclr Dictionary even does something similar to this as it cannot currently be expressed in C# in a more sensible way.

I'm suggesting within scope of the test e.g

if (TKey is struct && TKey is IEquatable<TKey>)
{
    // here
}

Types of TKey are known to have the types implemented; so they should then be available to be called; and done so without boxing; and also it should be a language level feature.

[benaadams]

The other current way to do it; but only for a set of known types, is to cast the generic through object and then to type; and get the Jit to sort out the boxing (As used in Vectors). So:

[MethodImpl(MethodImplOptions.AggressiveInlining)]
private bool KeyEquals(TKey key0, TKey key1)
{
    IEqualityComparer<TKey> customComparer = _customComparer;
    if (customComparer == null)
    {
        if (default(TKey) == null)
        {
            EqualityComparer<TKey> defaultComparer = _defaultComparer;
            return defaultComparer.Equals(key0, key1);
        }
        else
        {
            if (typeof(TKey) == typeof(byte))
            {
                return (byte)(object)key0 == (byte)(object)key1;
            }
            else if (typeof(TKey) == typeof(sbyte))
            {
                return (sbyte)(object)key0 == (sbyte)(object)key1;
            }
            else if (typeof(TKey) == typeof(ushort))
            {
                return (ushort)(object)key0 == (ushort)(object)key1;
            }
            else if (typeof(TKey) == typeof(short))
            {
                return (short)(object)key0 == (short)(object)key1;
            }
            else if (typeof(TKey) == typeof(char))
            {
                return (char)(object)key0 == (char)(object)key1;
            }
            else if (typeof(TKey) == typeof(uint))
            {
                return (uint)(object)key0 == (uint)(object)key1;
            }
            else if (typeof(TKey) == typeof(int))
            {
                return (int)(object)key0 == (int)(object)key1;
            }
            else if (typeof(TKey) == typeof(ulong))
            {
                return (ulong)(object)key0 == (ulong)(object)key1;
            }
            else if (typeof(TKey) == typeof(long))
            {
                return (long)(object)key0 == (long)(object)key1;
            }
            else if (typeof(TKey) == typeof(IntPtr))
            {
                return (IntPtr)(object)key0 == (IntPtr)(object)key1;
            }
            else if (typeof(TKey) == typeof(UIntPtr))
            {
                return (UIntPtr)(object)key0 == (UIntPtr)(object)key1;
            }
            else if (typeof(TKey) == typeof(Guid))
            {
                return (Guid)(object)key0 == (Guid)(object)key1;
            }
            else
            {
                EqualityComparer<TKey> defaultComparer = _defaultComparer;
                return defaultComparer.Equals(key0, key1);
            }
        }
    }
    else
    {
        return customComparer.Equals(key0, key1);
    }
}

This approach more heavily violates the static type system and compilation:

• Its more error prone as the type check and type cast have to manually match
• Its more repetitive and verbose
• Its more brittle only working for the types explicitly specified
• Its essentially bypassing the C# compiler and placing a greater load on the Jit to clean up

However, it does produce the desired asm.

What I'd like is a way to do this in C#; that is less error prone, less repetitive, less brittle and compile time checked - hence the suggestion (however, it may not be the best approach to achieve this?)

[redknightlois]

In support of @benaadams, we use a ton of those things. Our codebase is cluttered with that stuff and with new support of intrinsics at the JIT level we plan to use more and more of that. A less error prone, typed and less cluttered approach would be pretty useful for managing our codebase performance targets.

We are even hijacking JIT behavior around structs to write limited generic metaprogramming structures using this kind of construction.

[Drawaes]

We also have plenty of these around in coming "message types" and networking. We need to process the messages very quickly and end up trying to trick the jit to reduce the branches for us but this leaves a bunch of ugly code.

All logic says that the user code should by all rights be the place this is fixed rather than lower so as to reduce the mess and allow of a performance "pit of sucess" rather than a few who know the tricks being able gain advantage.

[JosephTremoulet]

The other current way to do it; but only for a set of known types, is to cast the generic through object and then to type

This only works if the method you want to call doesn't modify its this parameter, right? Otherwise the MSIL you're emitting here says to make a box and invoke the method on that; the JIT couldn't very well "optimize" that to instead do its side-effects on the original (without more cleverness like proving that the original is dead at that point...).

I wonder if a coordinated language/jit/runtime change could do this without requiring a change to MSIL itself. Modifying one of the examples above slightly, supposing you could write this:

class MyClass<TKey> // No generic constraint
{
    public static bool Equals(TKey key0, TKey key1)
    {
        if (key0 is IEquatable<TKey> constrainedKey with constraint) {
            // constrainedKey  statically known to be constrained via IEquatable<TKey>
            // so this can be a constrained callvirt
            return constrainedKey.Equals(key1);
        }

        // not constrained so callvirt to `Object.Equals`
        return key0.Equals(key1);
    }
}

(pardon the ugly strawman syntax of adding with constraint after the type clause of an is-style pattern match... it's just there because I'm thinking what I'm suggesting here would need some sort of syntax indicator to distinguish it from regular pattern-matching)

Perhaps that could "desugar" to something like @benaadams's example with the nested function:

class MyClass<TKey> // No generic constraint
{
    public static bool Equals(TKey key0, TKey key1)
    {
       {
            bool _<>_injectedMethod<TConstrained>(TConstrained constriainedKey) where TConstrained : IEquatable<TKey> {
                // constrainedKey  statically known to be constrained via IEquatable<TKey>
                // so this can be a constrained callvirt
                return constrainedKey.Equals(key1);
            }
           bool _<>_injectedLocal = false;
           if (System.Runtime.CompilerServices.TryConstrain(methodof(_<>_injectedMethod), key0, ref _<>_injectedLocal)) {
              return _<>_injectedLocal;
           }

        // not constrained so callvirt to `Object.Equals`
        return key0.Equals(key1);
    }
}

(I'm intentionally glossing over methodof, assuming there'd be some way to pass an appropriate MethodInfo or something that the C# compiler could generate)
(I'm also intentionally glossing over how this "desugaring" deals with control flow out of the pattern-match scope; this is a nontrivial problem, so maybe ultimately it would be better to have something that looks less like a pattern-match and more like a local function definition... but I'll go on, assuming those sorts of questions could have answers)

This depends on some new method bool System.Runtime.CompilerServices.TryConstrain<T, TResult>(MethodInfo method, T arg, ref TResult result), which would have to be a jit instrinsic, and would require that the specified method be immediately apparent from the IL (not e.g. fetched from some local of type MethodInfo) and have signature TResult method<T>(T arg) where T : ConstrainedInterfaceType. Its semantics for ref types T would be to expand to

    if (arg is <constraint interface type>) {
      result = <call to the given method>((ConstraintInterfaceType) arg);
      "return" true;
   } else {
      "return" false;
   }

I'm assuming that the constraint interface type could be inferred by looking at the signature of the method passed as an argument to TryConstrain. So here we insert a run-time test and if that succeeds cast and call the constrained nested method.

For struct types T, the JIT would check if T implements the constraint interface; if not, the call to TryConstrain would simply be replaced with false, but if so, it would insert a direct call to the target method -- since this is happening at JIT time and the exact type of T is known, I believe that internally it would be able to use the handling it uses for constrained calls to effect this. (at least, I've verified that if I manually create unverifiable IL with a not-statically-guaranteed constrained callvirt, but then invoke it with a struct type that would satisfy the constraint, the JIT ends up handling it fine).

[JosephTremoulet]

On second thought, the T-typed parameter to the nested method and to System.Runtime.CompilerServices.TryConstrain would have to have type ref T, rather than (by-value) T, or else this still has the problem of the interface method applying modifications to the wrong instance. But with ref T, the expansion above for the reference type case doesn't work, since (ConstraintInterfaceType) arg isn't an l-value / can't have its address taken. Maybe the JIT IR could include some sort of unsafe cast on the byref types?

Also, maybe readonly ref T would be more appropriate than plan ref T. Looks like with pattern-matching if (x is S s), a copy is introduced from x to s? Hmm...

[benaadams]

I think there are 3 was to do it currently; but they all mostly violate the type system

if (typeof(TKey) == typeof(int))
{
    return (int)(object)key0 == (int)(object)key1;
}
if (typeof(TKey) == typeof(int))
{
    return __refvalue(__makeref(key0), int) == __refvalue(__makeref(key1), int);
}
if (typeof(TKey) == typeof(int))
{
    return Unsafe.As<TKey, int>(ref key0) == Unsafe.As<TKey, int>(ref key1);
}

[ericsampson]

@benaadams are you still interested in this? Being able to switch/pattern match on generics would be awesome.

[benaadams]

Later proposal from @tannergooding #6308

[benaadams]

@benaadams are you still interested in this?

Yes, I would like to be able to opt back into constraints via checks, with flow control similar to how nullable references works; to then be able to call more specific constrained methods from a less specific constrained type.

e.g. call an unmanaged constrained method from a struct constrained method in a branch that has verified T is unmanaged in some way.