Mostly Software

January 29, 2008

Other Types

Filed under: Software — Tags: , , — schani @ 6:43 pm

In my last longer post on generics sharing in Mono I talked about the three different interesting ways an open type that’s used in a method of a generic class (to create an array, for example) can be related to that generic class: The used type can be one of the class’s type arguments, it can be the class itself or one of its superclasses, or it can be more or less unrelated to the class (where we treat all degrees of more or less the same). I talked about the “run-time generic context”, which is a data structure that stores various pieces of type information in connection to a closed generic class, so that shared code can execute efficiently and doesn’t need to do complicated look-up maneuvers to get to those pieces of data. I also explained that the third category of relatedness, namely “other”, is different from the first two in that we cannot know which, or even how many of those other types there will be when we load the class or compile one of its methods, and that we therefore need an extensible data structure to store them. This post is about that data structure.

To use an example from the post alluded to above, let’s say we have a class GenA<T> which has a method newSomeClassArr() that we are in the process of compiling:

public SomeClass<T>[] newSomeClassArr () {
  return new SomeClass<T> [3];
}

We encounter a NEWARR instruction telling us to create an array with element type SomeClass<T>. To create an array we need the internal meta-data of the element type, so SomeClass<T> must be in the run-time generic context. Since it is unrelated to GenA<T>, i.e. it is not a type argument nor a subclass of the latter, we have to put it in the extensible part of the run-time generic context.

To make things easy let’s assume that the run-time generic context contains an extensible array, so we can just append elements without having to worry about memory management or complex data structures. What exactly does it mean to put that class into the run-time generic context? I have already explained that every closed generic class, i.e. every instantiation of an open generic class, has its own run-time generic context, so there might already be several run-time generic contexts of some instantiations of GenA<T> in the wild where we need to put that information in. Furthermore, we have to make sure that for every new instantiation that we might create later on, that information is put in there, too. To that latter end we keep track of all the type information stored in the run-time generic contexts of the instantiations of an open generic class in another structure we call the “run-time generic context template”.

Things get a bit more complicated, however. Not only do we have to make sure that all instantiations of GenA<T> contain the meta-data information of SomeClass<T>, we must do the same for all subclasses of GenA<T> as well, since they might also execute the newSomeClassArr() method. This has two interesting consequences: First, we sometimes have to create run-time generic contexts for non-generic classes, and second, we cannot just pick any unused slot in the extensible array for a new type.

Non-generic classes can be subclasses of generic classes, and since we have to create run-time generic contexts for all subclasses of a generic class, it follows that some non-generic classes, namely those which are direct or indirect subclasses of generic ones, need one too.

The second point has to do with the downward propagation, in the inheritance tree, of entries in the run-time generic context. If we put a type into a specific slot for some class, then we have to put the corresponding type into the same slot of all subclasses of that class. That means that we have to pick a slot that is not already occupied by some other type in one or more of the subclasses. We solve this problem by not only propagating entries downward but also by marking the slot we selected as occupied in all the parent classes (to be precise: in their run-time generic context templates).

The last remaining mystery is the question how the slots are actually represented in the run-time generic context. For now we have decided to put a fixed number of slots directly into the run-time generic context and use an indirect slot for the rest. That indirect slot points to an array of slots that can be reallocated if more space is needed. Other approaches are possible and have been discussed, but we’re taking our chances with this simple solution and see how it works out.

About these ads

2 Comments

  1. [...] are Lazy Filed under: Software — by schani @ 2:13 pm Tags: generics, mono, types In my last post about my work on generics sharing in Mono I expanded on the runtime generic context and its extensible part. Today I want to talk about when [...]

    Pingback by Generic Types are Lazy « Juggling, Photography, Software, and Atheism — February 25, 2008 @ 2:13 pm

  2. [...] first stab at implementing a fast virtual generic call mechanism involved the runtime generic context data structure I implemented for generic code sharing. The idea was to use the RGCTX as an extensible virtual [...]

    Pingback by Fast Virtual Generic Calls « Juggling, Photography, Software, and Atheism — October 12, 2008 @ 5:03 pm


RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

The Shocking Blue Green Theme Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: