Multiple Inheritance & C3 Linearization

Python natively supports multiple inheritance: a class can inherit from two or more parent classes simultaneously.

However, multiple inheritance introduces serious theoretical challenges, most notably the Diamond Inheritance Problem, where multiple inheritance paths diverge and rejoin at a common base class.

To resolve method calls deterministically without duplicate executions or ambiguous dispatch, Python uses the C3 Linearization Algorithm to construct a single, ordered list known as the Method Resolution Order (MRO).

1. The Diamond Inheritance Dilemma#

Consider a classic diamond hierarchy:

If class D calls a method defined in A and overridden in B and C, which version should execute? In what order should cooperative initializers run?

Legacy Python 2.2 used a naive Depth-First Search (DFS) order (D -> B -> A -> C -> A -> object), which violated fundamental object-oriented principles: it evaluated grandparent A before sibling parent C!

2. The Formal C3 Linearization Algorithm#

Python resolves inheritance graphs using C3 Linearization. The algorithm defines the linearization $L(C)$ of class $C$ inheriting from parent classes $B_1, B_2, \dots, B_n$ through a recursive merge operation:

The Merge Selection Rule#

The merge operator evaluates the list candidates:

1. Examine the head (first element) of the first list in the merge set.
2. Check if this head appears in the tail (all elements after the first) of any other list in the merge set.
3. If it does not appear in any tail:

• Append that head class to the output MRO list.
• Remove that class from every list in the merge set.

1. If it appears in a tail:

• Skip to the head of the next list in the merge set and repeat the check.

1. If all heads appear in tails, C3 aborts, raising TypeError: Cannot create a consistent method resolution order (MRO).

Invariants Guaranteed by C3#

1. Extended Child Precedence: Subclasses always precede parent classes ($D$ appears before $B$ and $C$).
2. Local Precedence Order: Parent order declared in class definition headers is preserved ($B$ appears before $C$).
3. Monotonicity: If class $X$ precedes class $Y$ in $L(C)$, then $X$ strictly precedes $Y$ in the MRO of any subclass of $C$.

3. Step-by-Step Mathematical Derivation#

Let us calculate the MRO for the diamond hierarchy where $B(A)$, $C(A)$, and $D(B, C)$:

Now compute $L(D)$:

• Round 1: Head of list 1 is $B$. Is $B$ in any tail?
• Tails: (A, object), (A, object), (C). $B$ is not in any tail!
• Pick $B$. Output: (D, B).
• Remaining: merge((A, object), (C, A, object), (C))

• Round 2: Head of list 1 is $A$. Is $A$ in any tail?
• Tails: (object), (A, object) $\implies A$ is in the tail of list 2! Blocked!
• Move to list 2 head: $C$. Is $C$ in any tail?
• Tails: (object), (A, object), () $\implies C$ is not in any tail!
• Pick $C$. Output: (D, B, C).
• Remaining: merge((A, object), (A, object))

• Round 3: Head is $A$. $A$ is not in any tail. Pick $A$. Output: (D, B, C, A).
• Round 4: Pick object.

4. Demystifying super() in Cooperative Hierarchies#

A widespread misconception is that super() calls the immediate parent class. In Python, super() does not call the parent; it calls the NEXT class in the instance's MRO!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Base:
    def action(self):
        print("Base action")

class Left(Base):
    def action(self):
        print("Left action start")
        super().action()
        print("Left action end")

class Right(Base):
    def action(self):
        print("Right action start")
        super().action()
        print("Right action end")

class Diamond(Left, Right):
    def action(self):
        print("Diamond action start")
        super().action()
        print("Diamond action end")

d = Diamond()
print(f"MRO Order: {[cls.__name__ for cls in Diamond.__mro__]}")
print("\n=== Executing d.action() ===")
d.action()

Notice that inside Left.action(), calling super().action() dispatched directly to Right.action(), even though Left does not inherit from Right! This cooperative dispatch allows every class in the diamond to execute exactly once.

5. Concept Verification#

Test your understanding of multiple inheritance and C3 linearization: