Roslyin Compiler Support for Type Classes

This documentation describes potential implementation of Type Classes and Shapes features in Roslyn compiler.

Goals:

Provide a solution without extra modification of .NET CLR
Stay backward compatible so previous versions of C# programming language can use generic types constrained with type classes
Stay CLS compliant
Provide interoperability between different .NET languages

Non-Goals:

Syntax for Type Classes or Shapes
Higher Kinded Types (HKT) is not covered in this document but it doesn't mean that HKT cannot be implemented using the techniques described below

Limitations:

Fields cannot be a part of concept definition

Introduction

Implementation of Type Classes can be based on the following existing features of .NET BLC and CLR:

Reflection
beforefieldinit behavior
Function pointers
calli IL instruction

For better explanation, the current document explains translation of the following concept definition:

concept Number<A> {
  static A Add(A a, A b);
  static A Mult(A a, A b);
  static A Neg(A a);
  string ToString(string format);
}

public class TestClass<T>
  where T: Number<T>
{
}

Stage 1: Translation of concept declaration

Concept declaration can be translated into static class with the same number of generic parameters as original declaration has.

public static class Number<A>
{
}

Such static class should not be marked with beforefieldinit to cause earlier initialization of static members through calling of static constructor. It is needed because all members of concept types are represented as static fields. Such transformation will be described below.

Generated static class should be marked with several attributes to inform the compiler that this class is a concept declaration:

CompilerGeneratedAttribute. This attribute prevents from using this class and call its members explicitly from source code.
ConceptTypeAttribute which is applicable only to classes. This attribute indicates that the static class is a declaration of concept.

Obviously, that concept type definition may include existing generic parameter constraints such as required interfaces, parameterless constructor or struct/class specialization.

Stage 2: Translation of concept members

Concept member has enough information to discover such member using Reflection:

Name of the member
Its signature: list of formal parameters and return type

With help of reflection it is possible to obtain instance of MethodInfo. After that, just store method handle as a private static field. Initialization of these fields are placed into static constructor:

public static class Number<A>
{
  private static readonly RuntimeMethodHandle addMethod;
  private static readonly RuntimeMethodHandle multMethod;
  private static readonly RuntimeMethodHandle negMethod;
  private static readonly RuntimeMethodHandle toString1;
  
  static Number()
  {
    addMethod = typeof(A).GetMethod("Add", BindingFlags.Static | BindingFlags.FlattenHierarchy, new[] { typeof(A), typeof(A) })?.MethodHandle ?? throw new GenericConstraintViolationException();
    multMethod = typeof(A).GetMethod("Mult", BindingFlags.Static | BindingFlags.FlattenHierarchy, new[] { typeof(A), typeof(A) })?.MethodHandle ?? throw new GenericConstraintViolationException();
    negMethod = typeof(A).GetMethod("Mult", BindingFlags.Static | BindingFlags.FlattenHierarchy, new[] { typeof(A) })?.MethodHandle ?? throw new GenericConstraintViolationException();
    toString1 = typeof(A).GetMethod("ToString", BindingFlags.Instance | BindingFlags.FlattenHierarchy, new[] { typeof(string) })?.MethodHandle ?? throw new GenericConstraintViolationException();
  }
}

GenericConstraintViolationException indicating that the required member is not presented by actual generic argument. The sections below describe how to translate different programmatic elements and control the application of concept type by compiler.

Translation of methods

Method handle provides access to the method pointer. The method can be called using such pointer using calli IL instruction. This behavior is placed into public static method. Instance method requires to pass this argument. The appropriate parameter is declared explicitly. If constrained type T is struct then this argument should be passed by reference (ref keyword); otherwise, by value. If T is not constrained to value type or reference type then this argument should be passed by-ref. In our example, A is not constrained, therefore, guard condition should be inserted inside of the wrapper method.

public static class Number<A>
{
  private static readonly RuntimeMethodHandle addMethod;
  private static readonly RuntimeMethodHandle toString1;
  
  static Number()
  {
    //...
  }
  
  [MethodImpl(MethodImplOptions.AggressiveInlining)]
  [ConceptMember(IsStatic = true)]
  public static A Add(A a, A b)
  {
    //MSIL code
    ldsfld RuntimeMethodHandle toString1
    call instance native int RuntimeMethodHandle::GetFunctionPointer();
    ldarg.0
    ldarg.1
    calli A(A)
    ret
  }
  
  [ConceptMember(IsStatic = false)]
  [MethodImpl(MethodImplOptions.AggressiveInlining)]
  public static string ToString(ref A @this, string format)
  {
    if(typeof(A).IsValueType)
    {
      //MSIL code
      ldsfld RuntimeMethodHandle Number<!!T>::toString1
      call instance native int RuntimeMethodHandle::GetFunctionPointer()
      ldarg.0
      ldarg.1
      calli A(A&)
      ret
    }
    else
    {
      ldsfld RuntimeMethodHandle Number<!!T>::toString1
      call instance native int RuntimeMethodHandle::GetFunctionPointer()
      ldarg.0
      ldobj A
      ldarg.1
      calli A(A)
      ret
    }
  }
}

Guard condition if(typeof(A).IsValueType) can be optimized by CLR for each actual generic argument.

Each public static method should be marked as aggressiveinlining to inline indirect method call.

ConceptMemberAttribute is a special attribute indicating that marked member is concept member implementation. This information can be used by compiler to provide necessary control at source code level.

Translation of properties

The concept property is identified by its type, name and getter/setter. Instance property will be translated into public indexer property which accepts this argument as its first argument. Static property can be translated as-is because this argument is not required.

public static class Number<A> where A: class
{
  private static readonly RuntimeMethodHandle getterMethod;
  
  static Number()
  {
    //...
  }
  
  [ConceptMember(IsStatic = false)]
  public static int Length[ref A @this]
  {
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    get
    {
      ldsfld RuntimeMethodHandle Number<!!T>::getterMethod
      call instance native int RuntimeMethodHandle::GetFunctionPointer()
      ldarg.0
      calli int(A)
      ret
    }
  }
}

Translation of events

Translation of events has the same algorithm as for properties.

Stage 3: Applying concept to the generic parameters

Generic parameter with concept constraint can be translated without introduction of new IL metadata instructions. In our example, TestClass<T> will be translated as follows:

public class TestClass<[Concept(typeof(Number<>))] T>
{
  static TestClass()
  {
    //MSIL code
    call static void Number<!!T>::.cctor()
  }
}

ConceptAttribute necessary to associate generic parameter with concept definition. Additionally, this attribute can be used by compiler to verify the actual generic argument at compile time.

Explicit call of concept static constructor is required to follow fail fast approach.

If concept is applied to the method generic parameter then fail fast is guaranteed because static class Number is not marked as beforefieldinit.

Stage 4: Calling concept members

Calling of concept member is translated into appropriate static method call from static class representing concept definition.

public static void ToStr<T>(T value) where T: Number<T> => value.ToString("X");

translated into

public static void ToStr<T>(T value) where T: Number<T> => Number<T>.ToString(ref value, "X");

Performance

Calling of concept members has the cost equal to invocation of the method by pointer. CLR can performs inline caching to reduce this cost.

Proof of Concept

.NEXT library (I am the author) provides support of concepts including ability to declare required fields, operators and constructors in the concept. The library offers ready-to-use concept types:

Number concept which represents any numeric type with operators, static and instance methods
Disposable concept which covers any disposable type even if doesn't implement IDisposable interface.
Awaitable concept type which allows to capture the type providing GetAwaiter method with corrent signature to be compatible with await operator.

Delegate instances in this library are used instead of function pointers because there is not way to use calli IL instruction in C# explicitly. This behavior is replaced by Invoke special method provided by any delegate type.

Benchmarks demonstrating that the proposed implementation of Type Concepts doesn't cause performance issues are here and here.

sakno/roslyn-tc-proposal.md