How do C#/.Net generics know their parameter types?

Question

In C# a generic function or class is aware of the types of its generic parameters. This means that dynamic type information, like is or as is available (in contrast to Java where it is not).

I'm curious, how does the compiler provides this type information to the generic methods? For classes I can image the instances can simply have a pointer to the type, but for generic functions I'm not sure, perhaps just a hidden parameter?

If the generics are preserved into the IL level, which I believe they are, then I'd like to know how this is done at that level.

Answer 1

Since you've edited your question to extend it beyond the C# compiler to the JIT compiler, here's an overview of the process, taking List<T> as our example.

As we've established, there is only one IL representation of the List<T> class. This representation has a type parameter corresponding to the T type parameter seen in C# code. As Holger Thiemann says in his comment, when you use the List<> class with a given type argument, the JIT compiler creates a native-code representation of the class for that type argument.

However, for reference types, it compiles the native code only once and reuses it for all other reference types. This is possible because, in the virtual execution system (VES, commonly called the "runtime"), there is only one reference type, called O in the spec (see paragraph I.12.1, table I.6, in the standard: http://www.ecma-international.org/publications/standards/Ecma-335.htm). This type is defined as a "native size object reference to managed memory."

In other words, all objects in the (virtual) evaluation stack of the VES are represented by an "object reference" (effectively a pointer), which, taken by itself, is essentially typeless. How then does the VES ensure that we don't use members of an incompatible type? What stops us from calling the string.Length property on an instance of System.Random?

To enforce type safety, the VES uses metadata that describes the static type of each object reference, comparing the type of a method call's receiver to the type identified by the method's metadata token (this applies to access of other member types as well).

For example, to call a method of the object's class, the reference to the object must be on the top of the virtual evaluation stack. The static type of this reference is known thanks to the method's metadata and analysis of the "stack transition" -- the changes in the state of the stack caused by each IL instruction. The call or callvirt instruction then indicates the method to be called by including a metadata token representing the method, which of course indicates the type on which the method is defined.

The VES "verifies" the code before compiling it, comparing the reference's type to that of the method. If the types are not compatible, verification fails, and the program crashes.

This works just as well for generic type parameters as it does for non-generic types. To achieve this, the VES limits the methods that can be called on an reference whose type is an unconstrained generic type parameter. The only allowed methods are those defined on System.Object, because all objects are instances of that type.

For a constrained parameter type, the references of that type can receive calls for methods defined by the types of the constraint. For example, if you write a method where you have constrained type T to be derived from ICollection, you can call the ICollection.Count getter on a reference of type T. The VES knows that it is safe to call this getter because it ensures that any reference being stored to that position in the stack will be an instance of some type that implements the ICollection interface. No matter what the actual type of the object is, the JIT compiler can therefore use the same native code.

Consider also fields that depend on the generic type parameter. In the case of List<T>, there is an array of type T[] that holds the elements in the list. Remember that the actual in-memory array will be an array of O object references. The native code to construct that array, or to read or write its elements, looks just the same regardless of whether the array is a member of a List<string> or of a List<FileInfo>.

So, within the scope of an unconstrained generic type such as List<T>, the T references are just as good as System.Object references. The advantage of generics, though, is that the VES substitutes the type argument for the type parameter in the caller's scope. In other words, even though List<string> and List<FileInfo> treat their elements the same internally, the callers see that the Find method of the one returns a string, while that of the other returns a FileInfo.

Finally, because all of this is achieved by metadata in the IL, and because the VES uses the metadata when it loads and JIT-compiles the types, the information can be extracted at run time through reflection.

Answer 2

You asked how casts (including is and as) can work on variables of a generic type parameter. Since all objects store metadata about their own type all casts work the same way as if you had used the variable type object. The object is interrogated about its type and a runtime decision is being made.

Of course this technique is only valid for reference types. For value types the JIT compiles one specialized native method for each value type that is used to instantiate the generic type parameters. In that specialized method the type of T is exactly known. No further "magic" is needed. Value type parameters are therefore a "boring" case. To the JIT it looks like there are no generic type parameters at all.

How can typeof(T) work? This value is passed as a hidden parameter to generic methods. This is also how someObj as T is able to work. I'm quite sure it's being compiled as a call to a runtime helper (e.g. RuntimeCastHelper(someObj, typeof(T))).

Answer 3

The clr runtime compiles each method separately just in time when it is first executed. You can see this, if you use a type somewhere in a method with multiple lines and the dll the type is defined in is missing. Set a breakpoint in the first line of the method. On calling the method, a type load exception is thrown. The breakpoint is not hit by the debugger. Now separate the method in three submethods. The middle one should contain the lines with the missing type. Now you can step in the method with the debugger and also into the first of the new methods, but when calling the second one, the exception is thrown. This is due to the fact that the method is compiled when it is first called and only then the compiler/linker stumbles over the missing type.

To answer your question: As pointed out by others, the generics are supported in the IL. On execution time, when you create a List for the first time, the constructor code is compiled (with the subsitution of int for the type parameter). If you then create a List for the first time, the code is compiled again with string as the type parameter. You can see it as if the concrete classes with concrete types are generated at runtime on the fly.

Answer 4

how does the compiler provides this type information to the generic methods?

tl;dr It provides the type information by effectively duplicating the method for every unique type that it is used with.

Now, for those of you who want to read more... ;) The answer is actually quite simple once you get a little example to go with it.

Let's start with this:

public static class NonGenericStaticClass
{
    public static string GenericMethod<T>(T value)
    {
        if(value is Foo)
        {
            return "Foo";
        }
        else if(value is Bar)
        {
            return "Bar";
        }
        else
        {
            return string.Format("It's a {0}!", typeof(T).Name);
        }
    }
}

// ...

static void Main()
{
    // Prints "It's a Int32!"
    Console.WriteLine(NonGenericStaticClass.GenericMethod<int>(100));

    // Prints "Foo"
    Console.WriteLine(NonGenericStaticClass.GenericMethod<Foo>(new Foo()))

    // Prints "It's a Int32!"
    Console.WriteLine(NonGenericStaticClass.GenericMethod<int>(20));
}

Now, as other people have already stated, IL supports generics natively, so the C# compiler doesn't actually do much with this example. However, when the Just-In-Time compiler comes along to turn the IL into Machine Code, it has to convert the generic code into something that is not generic. To do this, the .Net Just-In-Time compiler effectively duplicates the method for each of the different types that are used with it.

If the resulting code were in C# it would probably look something like this:

public static class NonGenericStaticClass
{
    // The JIT Compiler might rename these methods after their
    // representative types to avoid any weird overload issues, but I'm not sure
    public static string GenericMethod(Int32 value)
    {
        // Note that the JIT Compiler might optimize much of this away
        // since the first 2 "if" statements are always going to be false
        if(value is Foo)
        {
            return "Foo";
        }
        else if(value is Bar)
        {
            return "Bar";
        }
        else
        {
            return string.Format("It's a {0}!", typeof(Int32).Name);
        }
    }

    public static string GenericMethod(Foo value)
    {
        if(value is Foo)
        {
            return "Foo";
        }
        else if(value is Bar)
        {
            return "Bar";
        }
        else
        {
            return string.Format("It's a {0}!", typeof(Foo).Name);
        }
    }
}

// ...

static void Main()
{
    // Notice how we don't need to specify the type parameters any more.
    // (of course you could've used generic inference, but that's beside the point),
    // That is because they are essentially, but not necessarily, overloads of each other

    // Prints "It's a Int32!"
    Console.WriteLine(NonGenericStaticClass.GenericMethod(100));

    // Prints "Foo"
    Console.WriteLine(NonGenericStaticClass.GenericMethod(new Foo()))

    // Prints "It's a Int32!"
    Console.WriteLine(NonGenericStaticClass.GenericMethod(20));
}

Once you've generated the non-generic methods, then you know exactly what type you are dealing with through the wonderful use of static dispatch.

Now, there are obviously going to be differences between how I represent the transformation and how it is actually done, but that is the gist of it. Also, the same sort of process is done for generic types as well.

For some contrast, the Java compiler "cheats" generics. Instead of generating new types and methods like .Net does, Java inserts casts where you expect the value to be of a certain type. As such, our typeof(T) would not be possible in the Java world, instead we would have to use the getClass() method.