C3 Linearization

A function called Parrot_ComputeMRO_C3(PARROT_INTERP, PMC *_class) computes the C3 linearization for a given class. C3 is an algorithm to compute the method resolution order (MRO) of a class that is inheriting from multiple parent classes (multiple inheritance). C3 was first described by Barrett et al at:  http://192.220.96.201/dylan/linearization-oopsla96.html

Class MRO lists

An MRO list is a method-resolution-order list of all the classes searched, in search order, when trying to look up a given method for a class.

In most OO languages, the rule is something like "the method name is sought in the invocant object's class; if no matching method exists in the class, then the immediate parent class is searched; this continues until the first matching method is found, or until the search reaches the farthest ancestor class, in which case the call fails and an exception is thrown."

For single-inheritance languages like Java, the MRO is simply the class inheritance hierarchy in reverse - [ Child, Parent, Grandparent, ... ]

For multiple-inheritance languages some kind of rule must be specified for determining MRO. If class DogTree is a child of both class Dog and class Tree, then what code is run when a method called "bark" is invoked?

This is the point of an MRO, and C3 is one of many algorithms used to compute an MRO.

C3 Avoidance

In most cases, C3 can be avoided. (See source:/trunk/src/pmc/class.pmc#L430) If a class has no parent (very infrequent) or if a class has only one parent (very common - this is single inheritance) then the MRO computation is trivial. The MRO of a root class is a list of the class itself. The MRO of a class with one parent is the parent's MRO with the child class added.

class Root;             # [ Root ]

class Leaf is Root;     # [ Leaf, Root ]

Computation

Given a target class, C3 returns a list of classes. The first class in the list will be the target class -- methods are sought first in the target class.

The Parrot_ComputeMRO_C3 function prepares a master "merge list" consisting of the MRO lists of each immediate parent class of the target class. No parents means a single-element list. Each immediate parent class' MRO list is added to the merge list in order. The ordering is important, since this order is used to determine search order.

Finally, the list of immediate parents is added to the merge list (of lists). Thus, our DogTree example would have a merge list like:

    $merge_list = [
        [ class Dog mro list, starting with 'Dog' ],
        [ class Tree mro list, starting with 'Tree' ],
        [ class DogTree parents list:  'Dog', 'Tree' ],
    ]

Parrot_ComputeMRO_C3 sets up the merge_list and passes it to a recursive helper function called C3_merge.

C3_merge

C3_merge (see source:/trunk/src/oo.c#L1109) identifies a valid candidate class, searching in a particular order. The first valid candidate is considered the "next" entry in the MRO. All references to that candidate are removed from the search arena, and the function calls itself recursively.

Find a candidate class

C3_merge processes each list (mro list, or parents list) in the master merge list.

If the list is empty, it is skipped.

The next candidate class is the first entry in the list.

All of the other lists in the master merge list are checked. If the candidate class is part of the tail of any of those lists, the candidate is rejected.

(In the first pass of our DogTree example, Dog will appear as the first entry in the "class Dog mro" list, and will appear as the first entry in the "DogTree parents" list, but will not appear in the tail of any list. So Dog is not rejected.)

No lists means empty result

If the merge list is empty (or composed of empty lists) then an empty RPA is returned.

"Could not build C3 linearization: ambiguous hierarchy"

If the search for the next candidate fails to produce one, the dreaded "ambiguous hierarchy" exception is thrown.

Remove the candidate from all the lists

A valid candidate causes the code to search all the lists for that candidate. (N-squared search.) Any reference to the candidate is removed.

(Note: Since the candidate was found as index 0, and since a scan was done to make sure the candidate is not in the tail of any other list, the only place it might appear is at index 0. I think this code could get simpler.)

Recurse

The set of lists has shrunk by one candidate removed from at least one list. Recursively compute the C3_merge of this smaller set, and then prepend the current candidate to the front of the recursive result. Return that.

C3_merge example

This example comes from the Dylan paper.

class pane;
class scroll-mixin;
class scrollable-pane is scroll-mixin, pane;    # NB: scroll-mixin is more important

class edit-mixin;
class editable-pane is edit-mixin, pane;

class combo-pane is scrollable-pane, editable-pane;

The call to C3_merge for combo-pane would have a list-of-lists like:

[
    [ scrollable-pane, scroll-mixin, pane ],   # scrollable-pane MRO
    [ editable-pane, edit-mixin, pane ],       # editable-pane MRO
    [ scrollable-pane, editable-pane ],        # immediate parents of combo-pane
]

C3_merge would identify candidates:

Candidate Merge Lists Comments
scrollable-pane
scrollable-pane, scroll-mixin, pane
editable-pane, edit-mixin, pane
scrollable-pane, editable-pane
Remove from MRO, parents
scroll-mixin
scroll-mixin, pane
editable-pane, edit-mixin, pane
editable-pane
Remove from MRO
editable-pane
pane
editable-pane, edit-mixin, pane
editable-pane
pane appears in tail of editable MRO, so try editable-pane instead. Remove from MRO, parents.
edit-mixin
pane
edit-mixin, pane
( )
Removed from MRO
pane
pane
pane
( )
Removed from MRO, other MRO.

The returned list is the candidates in order:

[ scrollable-pane, scroll-mixin, editable-pane, edit-mixin, pane ]