LShift Ltd.

Adapting C3 Linearization for Java

June 23rd, 2006 david

One of the interesting issues in implementing dynamic dispatch for Java is that the basic C3 linearization algorithm isn’t a very good fit for the complexities of Java’s subtyping. (Note: the following paragraphs rely on the reader having a basic understanding of the details of C3 linearization.)

Java lists a class’s implemented interfaces separately from its superclass. C3 requires, for each class, a list of direct superclasses as input - so to adapt it for use with Java, we have to choose how to combine each class’s superclass with its implemented interface list: for instance, the superclass could be placed at the beginning or at the end of the interface list.

In Java any interface is assignable to Object. So for C3 to make sense, all interfaces which have no super-types have Object as a super-type. If Object is in the super-type list of a type, it must be the last thing - otherwise linearization will always be impossible. So the most obvious thing to do is to include the super-class last in the list of super-types.

This mostly works, but for the way collections from java.util are implemented: The various abstract collections implement their corresponding interface, but the actual implementations don’t directly implement the corresponding interface, so for example AbstractSet implements Set, and HashSet extends AbstractSet, but does not implement Set directly. This is a common pattern.

If, then, you always choose to put the super-class at the end of the list of super-types while performing linearization for C3, this results in an inconsistent linearization for all of Java’s built in collections.

So I ended up doing the following by default: For any super-class other than Object, the super-class goes first in the list of super-types. If the super-class is Object, it gets pushed to the end. This works in an intuitive way in lots of cases, and the implementation supports pluggable ordering, should you need to do something different.

Entry Filed under: Technology, Programming