16

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":

  • Upvoting because I think a complete answer would be interesting. I have some ideas about how it works but not enough to answer accurately. I don't think that generics in C# compile out to specialized classes for each generic type. They seem to be resolved at runtime (there can be a noticeable speed hit from using generics). Maybe we can get Eric Lippert to chime in? – KChaloux Oct 28 '13 at 16:34
  • 2
    @KChaloux: At the MSIL level, there's one description of the generic. When the JIT runs, it creates separate machine code for each value type used as a generic parameters, and one more set of machine code that covers all the reference types. Preserving the generic description in MSIL is really nice because it allows you to create new instances at runtime. – Ben Voigt Oct 28 '13 at 16:40
  • @Ben That's why I didn't attempt to actually answer the question :p – KChaloux Oct 28 '13 at 17:21
  • I'm not sure if you're still around, but what language are you compiling to. That will have a lot of influence on how you implement generics. I can provide information about how I've usually approached it on the front end, but the back end can vary wildly. – Telastyn Jul 2 '15 at 12:57
  • @Telastyn, for those topics sure I am :-) I am looking for something really close to C#, in my case I am compiling to PHP (no joke). I will be grateful if you share your knowledge. – greenoldman Jul 3 '15 at 5:48
4

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.

  • Thank you, that is interesting piece. So the static fields are solved similarly to virtual table, right? There is a reference to "global" dictionary which holds entries per each type? So I could have 2 assemblies not knowing of each other using Foo<string> and they won't produce two instances of static field from Foo. – greenoldman Oct 28 '13 at 17:37
  • 1
    @greenoldman Well, not similarly to virtual table, exactly the same. The MethodTable holds both static fields and references to methods of the type, used in virtual dispatch (that's why it's called MethodTable). And yeah, the CLR has to have some table that it can use to access all MethodTables. – svick Oct 28 '13 at 17:43
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.

  • My problem is that I cannot get away from thinking in terms of template. For example -- unlike template generic class is fully compiled. This means that in other assembly using this class what happens? The already compiled method is called with internal casting? I doubt the generics can rely on constraint -- rather on argument, otherwise Foo<int> and Foo<string> would hit the same data with Foo w/o constraints. – greenoldman Oct 28 '13 at 16:54
  • 1
    @greenoldman: Can we avoid value types for a minute, because they actually are handled specially? If you have List<string> and List<Form>, then since List<T> internally has a member of type T[] and there are no constraints on T, then what you'll actually get is machine code that manipulates an object[]. However, since only T instances are put into the array, everything coming out can be returned as a T without an additional type check. On the other hand, if you had ControlCollection<T> where T : Control, then the internal array T[] would become Control[]. – Ben Voigt Oct 28 '13 at 16:58
  • Do I understand correctly, that the constraint is taken and used as internal typename, but when class is actually used the casting is used? OK, I understand that model, but I was under the impression Java uses it, not C#. – greenoldman Oct 28 '13 at 17:07
  • 3
    @greenoldman: Java performs type erasure in the source->bytecode translation step. Which makes it impossible for the verifier to verify generic code. C# does it in the bytecode->machine code step. – Ben Voigt Oct 28 '13 at 17:14
  • @BenVoigt Some information is retained in Java about the generic types, as otherwise you couldn't compile against a generic-using class without its source. It's just not kept in the bytecode sequence itself AIUI, but rather in class metadata. – Donal Fellows Oct 29 '13 at 10:07
1

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.

  • Thank you very much (pity I cannot accept multiply answers). It is great to hear that I did pretty much that step correctly -- in my case List<T> holds real type (its definition), while List<Foo> (thank you for the terminology piece as well) with my approach hold the declarations of List<T> (of course now bound to Foo instead of T). – greenoldman Jul 3 '15 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.