How are generics implemented?

Question

This is the question from compiler internals perspective.

I am interested in generics, not templates (C++), so I marked the question with C#. Not Java, because AFAIK the generics in both languages differ in implementations.

When I look at languages w/o generics it is pretty straightforward, you can validate the class definition, add it to hierarchy and that's it.

But what to do with generic class, and more importantly how handle references to it? How to make sure that static fields are singular per instantiations (i.e. each time generic parameters are resolved).

Let's say I see a call:

var x = new Foo<Bar>();

Do I add new Foo_Bar class to hierarchy?

---

Update: So far I found only 2 relevant posts, however even they don't go into much details in sense "how to do it by yourself":

• http://www.jprl.com/Blog/archive/development/2007/Aug-31.html
• http://www.artima.com/intv/generics2.html

Answer 1

How to make sure that static fields are singular per instantiations (i.e. each time generic parameters are resolved).

Each generic instantiation has its own copy of the (confusingly named) MethodTable, which is where static fields are stored.

Let's say I see a call:

var x = new Foo<Bar>();

Do I add new Foo_Bar class to hierarchy?

I'm not sure it's useful to think of the class hierarchy as some structure that actually exists at runtime, it's more of a logical construct.

But if you consider MethodTables, each with an indirect pointer to its base class, to form this hierarchy, then yeah, this adds new class to the hierarchy.

Answer 2

I see two actual concrete questions in there. You're probably want to ask additional related questions (as separate question with a link back to this one) to get a full understanding.

How are static fields given separate instances per generic instance?

Well, for static members which are not related to the generic type parameters, this is pretty easy (use a dictionary mapped from the generic parameters to the value).

Members (static or not) which are related to the type parameters can be handled via type erasure. Just use whatever the strongest constraint is (often System.Object). Because the type information is erased after compiler type checks, it means that runtime type checks won't be needed (although interface casts may still exist at runtime).

Does each generic instance appear separately in the type hierarchy?

Not in .NET generics. The decision was made to exclude inheritance from type parameters, so it turns out that all instances of a generic occupy the same spot in the type hierarchy.

This was probably a good decision, because failure to look up names from a base class would be incredibly surprising.

Answer 3

But what to do with generic class, and more importantly how handle references to it?

The general way in the front end of the compiler is to have two sorts of type instances, the generic type (List<T>) and a bound generic type (List<Foo>). The generic type defines what functions exist, what fields, and has generic type references wherever T is used. The bound generic type contains a reference to the generic type, and a set of type arguments. That has enough information for you to then generate a concrete type, replacing the generic type references with Foo or whatever the type arguments are. This sort of distinction is important when you're doing type inference and need to infer List<T> versus List<Foo>.

Instead of thinking of generics like templates (which build out various implementations directly), it may be helpful to instead think of them like functional language type constructors (where the generic arguments are like arguments into a function that gives you a type).

As for the back end, I don't really know. All of my work with generics has targeted CIL as the backend, so I could compile them into the supported generics there.