How to resolve generic typenames in compiler?

Question

Let's say I have such code (and its meaning is like in C#):

class Foo<T>
{
   public T my_field;
}

and later in code I have:

var foo = new Foo<int>(); 
foo.my_field = 5;

My problem starts with the Foo<int>. What I currently do is I take type Foo<T> and mapping T -> int and clone the surface of that type. Surface because I skip init expressions, method/property bodies, but nevertheless I create something like this on the fly:

class Foo<int>
{
   public int my_field;
}

and then continue as it would be the usual type. The good thing is it works but the bad thing is it works slowly -- profiler does not hestitate to point out it is the bottleneck.

The other idea I have is using something like a "view" which would consist of reference to generic type (here Foo<T>) and mapping (here T -> int) and then using it each time I reference instance of generic type. In case of foo, I would go through such view to a field, I would get its type T, and "filter" it back through the view to get finally the result: int. I would like to avoid trial&error approach so...

My question is how instances of generic type are handled in compiler (not in runtime)? I mean for real :-).

Answer 1

What I've done (in a compiler that targets CIL) is have a series of objects that represent the various elements in the type system:

• GenericParameter - represents T in the code above - specifically the T owned by Foo. It has a name, and a constraint.
• GenericArgumentReferenceType - represents T as used in the field above. It's not a declaration of a generic type, it's a reference to another.
• BoundGenericType - represents Foo<int> when int is bound to T. This binding is useful since you can see what the source generic type is, as well as what the concrete type is, and models the .NET TypeBuilderInstantiation stuff and MakeGenericType constructs. It's a simple pair with some logic to return the "effective" type.

So Foo<T> is a type with one GenericParameter, which has one field with a GenericArgumentReference. Foo<int> then constructs a new BoundGenericType tying Foo<T> and int. For me the bound generic type has no fields - it is just a pair tying the two together. I need to do it in order to prevent scope explosion, but that might be particular to my language.

I also have separate objects to represent inference points for function generics. And there are separate expressions that access the generic parameters in functions. These are perhaps outside of the scope of your question.

Regardless, generics tend to get tricky. Remember to work out:

• What happens when you have Bar<T>, and it has a Foo<T> member?
• What happens when you have a function in Foo<T> that has a generic parameter T?
• What happens when you have a List<T> in Foo<T>?
• What happens when you're inferring T for a Foo<T> in a function?