View source for Draft:C3 linearization

{{AFC submission|d|npov|u=2804:7F0:B2C0:A3D6:B6C:7F14:E9A6:20E4|ns=118|decliner=Aydoh8|declinets=20250525235710|ts=20250525235604}} <!-- Do not remove this line! -->

{{Short description|Computer algorithm}}
{{Draft topics|computing}}
{{AfC topic|other}}

{{draft article|nomove=yes}}
 
'''C3 superclass linearization''' is an [[algorithm]] used primarily to obtain the order in which [[method (computing)|methods]] should be inherited in the presence of [[multiple inheritance]]. In other words, the ''output'' of C3 superclass linearization is a deterministic '''Method Resolution Order''' ('''MRO''').  

{{quote|In [[object-oriented]] systems with multiple inheritance, some mechanism must be used for resolving conflicts when inheriting different definitions of the same property from multiple superclasses.<ref name=C3_96/>}}

C3 superclass linearization is called C3 because it "is consistent with three properties":<ref name=C3_96/> 
* a consistent extended [[precedence graph]], 
* preservation of local precedence order, and 
* fitting a monotonicity criterion.

It was first published at the 1996 [[OOPSLA]] conference, in a paper entitled "A Monotonic Superclass Linearization for [[Dylan (programming language)|Dylan]]".<ref name=C3_96>{{cite conference
| date = 1996-06-28
| title = A Monotonic Superclass Linearization for Dylan
| book-title = OOPSLA '96 Conference Proceedings
| author = Kim Barrett, Bob Cassels, Paul Haahr, David A. Moon, Keith Playford, P. Tucker Withington
| pages = 69–82
| publisher = [[ACM Press]]
| doi = 10.1145/236337.236343
| isbn = 0-89791-788-X
| citeseerx = 10.1.1.19.3910
}}</ref>  It was adapted to the Open Dylan implementation in January 2012<ref>[http://opendylan.org/news/2012/01/25/c3.html News item on opendylan.org]</ref> following an enhancement proposal.<ref>{{Cite web |url=http://opendylan.org/proposals/dep-0003.html |title=Dylan Enhancement Proposal 3: C3 superclass linearization |access-date=2013-02-17 |archive-date=2017-07-03 |archive-url=https://web.archive.org/web/20170703005630/https://opendylan.org/proposals/dep-0003.html |url-status=dead }}</ref> It has been chosen as the default algorithm for method resolution in [[Python (programming language)|Python]] 2.3 (and newer),<ref>[https://www.python.org/download/releases/2.3/mro/ Python 2.3's use of C3 MRO]</ref><ref>[http://rhettinger.wordpress.com/2011/05/26/super-considered-super/ Tutorial for practical applications of C3 linearization using Python]</ref> [[Raku (programming language)|Raku]],<ref>[http://doc.perl6.org/type/Metamodel::C3MRO Perl 6's use of the C3 MRO]</ref> [[Parrot virtual machine|Parrot]],<ref>{{Cite web |url=http://aspn.activestate.com/ASPN/Mail/Message/perl6-internals/2746631 |title=Parrot uses C3 MRO |access-date=2006-12-06 |archive-url=https://web.archive.org/web/20070208165958/http://aspn.activestate.com/ASPN/Mail/Message/perl6-internals/2746631 |archive-date=2007-02-08 |url-status=dead }}</ref> [[Solidity]], and [[PGF/TikZ]]'s Object-Oriented Programming module.<ref>{{cite book|last1=Tantau|first1=Till|title=The TikZ & PGF Manual|date=August 29, 2015|page=1062|edition=3.1.9a|url=http://ftp.ntua.gr/mirror/ctan/graphics/pgf/base/doc/pgfmanual.pdf|access-date=2021-05-15}}</ref> It is also available as an alternative, non-default MRO in the core of [[Perl|Perl 5]] starting with version 5.10.0.<ref>[https://metacpan.org/module/mro C3 MRO available in Perl 5.10 and newer]</ref> An extension implementation for earlier versions of Perl 5 named <code>Class::C3</code> exists on [[CPAN]].<ref>[https://metacpan.org/module/Class::C3 Perl 5 extension for C3 MRO on CPAN]</ref>

Python's [[Guido van Rossum]] summarizes C3 superclass linearization thus:<ref>{{cite web|last1=van Rossum|first1=Guido|title=Method Resolution Order|url=http://python-history.blogspot.co.uk/2010/06/method-resolution-order.html|website=The History of Python|access-date=18 January 2018|date=23 June 2010}}</ref>

{{quote|Basically, the idea behind C3 is that if you write down all of the ordering rules imposed by inheritance relationships in a complex class hierarchy, the algorithm will determine a monotonic ordering of the classes that satisfies all of them. If such an ordering can not be determined, the algorithm will fail.}}

== Description ==
{{Confusing|date=April 2018}}

The C3 superclass linearization of a class is the sum of the class plus a unique merge of the linearizations of its parents and a list of the parents itself. The list of parents as the last argument to the merge process preserves the local precedence order of direct parent classes.

The merge of parents' linearizations and parents list is done by selecting the first head of the lists which does not appear in the tail (all elements of a list except the first) of any of the lists. Note, that a good head may appear as the first element in multiple lists at the same time, but it is forbidden to appear anywhere else. The selected element is removed from all the lists where it appears as a head and appended to the output list. The process of selecting and removing a good head to extend the output list is repeated until all remaining lists are exhausted. If at some point no good head can be selected, because the heads of all remaining lists appear in any one tail of the lists, then the merge is impossible to compute due to inconsistent orderings of dependencies in the inheritance hierarchy and no linearization of the original class exists.

A naive [[divide-and-conquer algorithm|divide-and-conquer]] approach to computing the linearization of a class may invoke the algorithm recursively to find the linearizations of parent classes for the merge-subroutine. However, this will result in an infinitely looping recursion in the presence of a cyclic class hierarchy. To detect such a cycle and to break the infinite recursion (and to reuse the results of previous computations as an optimization), the recursive invocation should be shielded against [[reentrancy (computing)|re-entrance]] of a previous argument by means of a cache or [[memoization]].

This algorithm is similar to finding a [[topological sorting|topological ordering]].

=== Example ===
Given
[[File:C3_linearization_example.svg|right|300px|thumb|A dependency graph for the C3 linearization example.]]
{{sxhl|2=java|1=<nowiki/>
 class O
 class A extends O
 class B extends O
 class C extends O
 class D extends O
 class E extends O
 class K1 extends C, A, B
 class K3 extends A, D
 class K2 extends B, D, E
 class Z extends K1, K3, K2
}}
the linearization of Z is computed as
{{sxhl|2=pascal|1=<nowiki/>
 L(O)  := [O]                                                // the linearization of O is trivially the singleton list [O], because O has no parents
 
 L(A)  := [A] + merge(L(O), [O])                             // the linearization of A is A plus the merge of its parents' linearizations with the list of parents...
        = [A] + merge([O], [O])
        = [A, O]                                             // ...which simply prepends A to its single parent's linearization
 
 L(B)  := [B, O]                                             // linearizations of B, C, D and E are computed similar to that of A
 L(C)  := [C, O]
 L(D)  := [D, O]
 L(E)  := [E, O]
 
 L(K1) := [K1] + merge(L(C), L(B), L(A), [C, A, B])          // first, find the linearization of K1's parents, L(C), L(B), and L(A), and merge them with the parent list [C, A, B]
        = [K1] + merge([C, O], [B, O], [A, O], [C, A, B])    // class C is a good candidate for the first merge step, because it only appears as the head of the first and last lists
        = [K1, C] + merge([O], [B, O], [A, O], [A, B])       // class O is not a good candidate for the next merge step, because it also appears in the tails of list 2 and 3, class B is also not good; but class A is a good candidate
        = [K1, C, A] + merge([O], [B, O], [O], [B])          // class B is a good candidate; class O still appears in the tail of list 2
        = [K1, C, A, B] + merge([O], [O], [O])               // finally, class O is a valid candidate, which also exhausts all remaining lists
        = [K1, C, A, B, O]
 
 L(K3) := [K3] + merge(L(A), L(D), [A, D])
        = [K3] + merge([A, O], [D, O], [A, D])               // select A
        = [K3, A] + merge([O], [D, O], [D])                  // fail O, select D
        = [K3, A, D] + merge([O], [O])                       // select O
        = [K3, A, D, O]
 
 L(K2) := [K2] + merge(L(B), L(D), L(E), [B, D, E])
        = [K2] + merge([B, O], [D, O], [E, O], [B, D, E])    // select B
        = [K2, B] + merge([O], [D, O], [E, O], [D, E])       // fail O, select D
        = [K2, B, D] + merge([O], [O], [E, O], [E])          // fail O, select E
        = [K2, B, D, E] + merge([O], [O], [O])               // select O
        = [K2, B, D, E, O]
 
 L(Z)  := [Z] + merge(L(K1), L(K3), L(K2), [K1, K3, K2])
        = [Z] + merge([K1, C, A, B, O], [K3, A, D, O], [K2, B, D, E, O], [K1, K3, K2])    // select K1
        = [Z, K1] + merge([C, A, B, O], [K3, A, D, O], [K2, B, D, E, O], [K3, K2])        // select C
        = [Z, K1, C] + merge([A, B, O], [K3, A, D, O], [K2, B, D, E, O], [K3, K2])        // fail A, select K3
        = [Z, K1, C, K3] + merge([A, B, O], [A, D, O], [K2, B, D, E, O], [K2])            // select A
        = [Z, K1, C, K3, A] + merge([B, O], [D, O], [K2, B, D, E, O], [K2])               // fail B, fail D, select K2
        = [Z, K1, C, K3, A, K2] + merge([B, O], [D, O], [B, D, E, O])                     // select B
        = [Z, K1, C, K3, A, K2, B] + merge([O], [D, O], [D, E, O])                        // fail O, select D
        = [Z, K1, C, K3, A, K2, B, D] + merge([O], [O], [E, O])                           // fail O, select E
        = [Z, K1, C, K3, A, K2, B, D, E] + merge([O], [O], [O])                           // select O
        = [Z, K1, C, K3, A, K2, B, D, E, O]                                               // done.
}}

=== Example demonstrated in Python 3 ===
First, a metaclass to enable a short representation of the objects by name instead of the default class REPR value:

<syntaxhighlight lang="python3">
class Type(type):
    def __repr__(cls):
        # Will make it so that repr(O) is "O" instead of "<__main__.O>",
        # and the same for any subclasses of O.
        return cls.__name__

class O(object, metaclass=Type): pass 
</syntaxhighlight>

Next, we define our base classes:

<syntaxhighlight lang="python">
class A(O): pass

class B(O): pass

class C(O): pass

class D(O): pass

class E(O): pass
</syntaxhighlight>

Then we construct the inheritance tree:

<syntaxhighlight lang="python">
class K1(C, A, B): pass

class K3(A, D): pass

class K2(B, D, E): pass

class Z(K1, K3, K2): pass
</syntaxhighlight>

And now:
<syntaxhighlight lang="pycon">
>>> Z.mro()
[Z, K1, C, K3, A, K2, B, D, E, O, <class 'object'>]
</syntaxhighlight>

=== Example demonstrated in Raku ===

[[Raku (programming language)|Raku]] uses C3 linearization for classes by default:
<syntaxhighlight lang="perl6">
class A {}
class B {}
class C {}
class D {}
class E {}
class K1 is C is A is B {}
class K3 is A is D {}
class K2 is B is D is E {}
class Z is K1 is K3 is K2 {}
say Z.^mro; # OUTPUT: ((Z) (K1) (C) (K3) (A) (K2) (B) (D) (E) (Any) (Mu))
</syntaxhighlight>

(the <code>Any</code> and <code>Mu</code> are the types all Raku objects inherit from, so <code>Any</code> stands in place of O)

== References ==
{{reflist}}

{{draft categories|
[[:Category:Object-oriented programming]]
[[:Category:Programming language implementation]]
[[:Category:Articles with example Python (programming language) code]]
}}
{{Drafts moved from mainspace|date=May 2025}}