Changes between Initial Version and Version 1 of C3 linearization

02/10/10 07:29:13 (12 years ago)

Created while trying to comprehend C3 code.


  • C3 linearization

    v1 v1  
     1= C3 Linearization = 
     3A 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: 
     5== Class MRO lists == 
     7An ''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. 
     9In 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." 
     11For single-inheritance languages like Java, the MRO is simply the class inheritance hierarchy in reverse - [ Child, Parent, Grandparent, ... ] 
     13For 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? 
     15This is the point of an MRO, and C3 is one of many algorithms used to compute an MRO. 
     17== C3 Avoidance == 
     19In most cases, C3 can be avoided. 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. 
     22class Root;             # [ Root ] 
     24class Leaf is Root;     # [ Leaf, Root ] 
     27== Computation == 
     29Given 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. 
     31The `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. 
     33Each 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. 
     35Finally, the list of immediate parents is added to the merge list (of lists).  Thus, our DogTree example would have a merge list like: 
     37    $merge_list = [ 
     38        [ class Dog mro list, starting with 'Dog' ], 
     39        [ class Tree mro list, starting with 'Tree' ], 
     40        [ class DogTree parents list:  'Dog', 'Tree' ], 
     41    ] 
     44`Parrot_ComputeMRO_C3` sets up the merge_list and passes it to a recursive helper function called `C3_merge`. 
     46=== C3_merge === 
     48`C3_merge` 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. 
     50==== Find a candidate class ==== 
     52C3_merge processes each list (mro list, or parents list) in the master merge list. 
     54If the list is empty, it is skipped. 
     56The next candidate class is the first entry in the list. 
     58All 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. 
     60(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.) 
     62==== No lists means empty result ==== 
     64If the merge list is empty (or composed of empty lists) then an empty RPA is returned. 
     66==== "Could not build C3 linearization: ambiguous hierarchy" ==== 
     68If the search for the next candidate fails to produce one, the dreaded "ambiguous hierarchy" exception is thrown. 
     70==== Remove the candidate from all the lists ==== 
     72A valid candidate causes the code to search all the lists for that candidate. (N-squared search.) Any reference to the candidate is removed.  
     74(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.) 
     76==== Recurse ==== 
     78The 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. 
     80=== C3_merge example === 
     81This example comes from the Dylan paper. 
     83class pane; 
     84class scroll-mixin; 
     85class scrollable-pane is scroll-mixin, pane;    # NB: scroll-mixin is more important 
     87class edit-mixin; 
     88class editable-pane is edit-mixin, pane; 
     90class combo-pane is scrollable-pane, editable-pane; 
     93The call to C3_merge for combo-pane would have a list-of-lists like: 
     96    [ scrollable-pane, scroll-mixin, pane ],   # scrollable-pane MRO 
     97    [ editable-pane, edit-mixin, pane ],       # editable-pane MRO 
     98    [ scrollable-pane, editable-pane ],        # immediate parents of combo-pane 
     102`C3_merge` would identify candidates: 
     106| **Candidate**   |           **Merge Lists**                 | **Comments**                  | 
     108| scrollable-pane | | **scrollable-pane,** scroll-mixin, pane | Remove from MRO, parents      | 
     109|                 | | editable-pane, edit-mixin, pane         |                               | 
     110|                 | | **scrollable-pane,** editable-pane      |                               | 
     112| scroll-mixin    | | **scroll-mixin,** pane                  | Remove from MRO               | 
     113|                 | | editable-pane, edit-mixin, pane         |                               | 
     114|                 | | editable-pane                           |                               | 
     116| editable-pane   | | pane                                    | **pane** appears in tail of   | 
     117|                 | | **editable-pane,** edit-mixin, pane     | editable MRO, so try          | 
     118|                 | | **editable-pane**                       | editable-pane instead. Remove | 
     119|                 |                                           | from MRO, parents.            | 
     121| edit-mixin      | | pane                                    | Removed from MRO              | 
     122|                 | | **edit-mixin,** pane                    |                               | 
     123|                 | | *( )*                                   |                               | 
     125| pane            | | **pane**                                | Removed from MRO, other MRO.  | 
     126|                 | | **pane**                                |                               | 
     127|                 | | *( )*                                   |                               | 
     130The returned list is the candidates in order: 
     132[ scrollable-pane, scroll-mixin, editable-pane, edit-mixin, pane ]