Multiple inheritance — Python's C3 linearization algorithm

WHY do we even need C3?

WHAT goes wrong without a good algorithm:

Old Python (pre-2.3) used depth-first, left-to-right: D → B → A → C. Disaster — it checked A before C, even though C is "more derived" than A.
We want: a child always precedes its parents, and the original parent order is preserved.

C3 fixes both. The three properties it guarantees:

Consistency with local precedence — order of parents in the class statement is kept.
Monotonicity — if X comes before Y in some parent's MRO, that order is never reversed in any subclass.
A child always appears before all its parents.

HOW the algorithm works — derived from scratch

HOW merge works (this is the heart):

Worked Example 1 — the Diamond

Classes: class A, class B(A), class C(A), class D(B, C).

Step — linearize the simple ones first. Why this step? C3 is recursive; we need $L[B]$ and $L[C]$ before $L[D]$ .

$L[A] = [A, \text{object}]$ $L[B] = B + \text{merge}(L[A], [A]) = B + \text{merge}([A,O],[A]) = [B, A, O]$ $L[C] = [C, A, O]$

Step — linearize D. Why this step? Now apply the master formula with both parents.

$L[D] = D + \text{merge}([B,A,O],\,[C,A,O],\,[B,C])$

Now run merge:

Iter	Lists	Candidate head	Good?	Why
1	`[B,A,O] [C,A,O] [B,C]`	`B`	✅	`B` not in any tail
2	`[A,O] [C,A,O] [C]`	`A`	❌	`A` is in tail of list 2 → skip; try `C` (head of list2) ✅
3	`[A,O] [A,O] []`	`A`	✅	no longer in any tail
4	`[O] [O] []`	`O`	✅

Result: $L[D] = [D, B, C, A, \text{object}]$ .

Worked example Verify in real Python

class A: pass
class B(A): pass
class C(A): pass
class D(B, C): pass
print(D.__mro__)
# (<class 'D'>, <class 'B'>, <class 'C'>, <class 'A'>, <class 'object'>)

Notice: A (the shared grandparent) appears once, and after both B and C.

Figure — Multiple inheritance — Python's C3 linearization algorithm

Worked Example 2 — an inconsistent hierarchy

class X, class Y, class A(X, Y), class B(Y, X), class C(A, B).

Why look at this? It shows when C3 fails and Python refuses the class.

$L[A] = [A, X, Y, O]$ , $L[B] = [B, Y, X, O]$ .

$L[C] = C + \text{merge}([A,X,Y,O],\,[B,Y,X,O],\,[A,B])$

Emit A ✅ → lists: [X,Y,O] [B,Y,X,O] [B]
Try X: it's in the tail of list 2 (...,Y,X,O) → skip.
Try B (head of list 2): is B in any tail? No → emit B ✅ → [X,Y,O] [Y,X,O] []
Try X: in tail of list 2 (Y,X,O) → skip. Try Y (head of list2): in tail of list 1 (X,Y,O) → skip. No good head!

→ TypeError: Cannot create a consistent method resolution order (MRO). The reason: A wants X before Y, B wants Y before X. Contradiction → no valid linear order exists.

Flashcards

What does MRO stand for and what is it?

Method Resolution Order — the single linear order in which Python searches classes for an attribute/method.

What formula defines C3 linearization of class C?

L[C] = C + \text{merge}(L[P_1],\dots,L[P_n],[P_1,\dots,P_n])

In the C3 merge, when is a head a "good head"?

When it does NOT appear in the tail (any position after the head) of any remaining list.

What happens to a head that is found in some list's tail?

It is skipped; you move on to test the head of the next list.

What is the MRO of D(B,C) where B(A), C(A)?

[D, B, C, A, object].

Why must a shared base appear only once and last among its descendants in the MRO?

A child must always be searched before its parents; merging places the base after every class that derives from it, with no duplicates.

What error does Python raise when C3 can't build a consistent MRO?

TypeError: Cannot create a consistent method resolution order (MRO).

Does super() call the literal parent class?

No — it calls the next class in the MRO, which may be a sibling, not the written parent.

What is the base case of C3?

L[\text{object}] = [\text{object}]

Name the three guarantees of C3.

Local precedence order preserved, monotonicity, and child-before-parent.

Recall Feynman: explain to a 12-year-old

Imagine you ask your family a question, and there's a rule about who you ask first. You ask yourself, then your mom, then your dad (in the order they're listed), and only after both of them do you ask grandma — because grandma is everyone's parent, so she has to wait until all her kids have been asked. C3 is just the careful rule that builds this "who-to-ask-first" line so nobody's parent ever gets asked before them, and grandma only stands in line once.

Connections

Method Resolution Order
super() and cooperative inheritance
The Diamond Problem
Single inheritance
Mixins
Composition vs Inheritance
Topological sort (C3 is a constrained topological ordering)

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, jab ek class ek se zyada parents se inherit karti hai (multiple inheritance), tab Python ko decide karna padta hai ki method ya attribute kis order mein dhoondhna hai. Ye order hi MRO (Method Resolution Order) kehlata hai, aur ise banane wala algorithm hai C3 linearization. Sabse classic case hai "diamond problem": B aur C dono A se aate hain, aur D dono B aur C se. Ab d.method() call karoge to kaunsa version chalega? C3 isko cleanly solve karta hai.

C3 ka formula simple hai: $L[C] = C + \text{merge}(\text{parents ke MRO}, \text{parents ki list})$ . Aur merge ka rule yaad rakho — ek class ko queue ke aage tabhi laao jab wo kisi bhi list ke tail mein na ho. Iska matlab: us class ke koi child abhi line mein wait nahi kar raha. Agar head tail mein mil jaye to use skip karke agli list ka head test karo. Diamond ke liye answer aata hai [D, B, C, A, object] — notice karo A (grandparent) sirf ek baar aata hai, aur dono children ke baad.

Ye matter kyun karta hai? Kyunki real code mein, especially frameworks aur mixins mein, multiple inheritance bahut use hota hai. Agar order galat ho to parent ka method child ke method se pehle chal jaye — bug! C3 guarantee karta hai ki child hamesha parent se pehle search ho, aur jo order tumne class D(B, C) mein likha wo respect ho. Aur sabse important: super() literal parent ko nahi, balki MRO ka agla class ko call karta hai — isi wajah se cooperative multiple inheritance kaam karta hai. Agar ek bhi hierarchy inconsistent ho (jaise A(X,Y) aur B(Y,X) dono ko mila do), to Python TypeError de dega kyunki koi valid linear order possible hi nahi.

Multiple inheritance — Python's C3 linearization algorithm

WHY do we even need C3?

HOW the algorithm works — derived from scratch

Worked Example 1 — the Diamond

Worked Example 2 — an inconsistent hierarchy

Common mistakes

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — OOP Fundamentals

Connections