Adapting C3 Linearization for Java

By: on June 23, 2006

One of the interesting issues in
implementing dynamic dispatch for
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

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.


Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>