Multiple inheritance — Python's C3 linearization algorithm: Question bank

Some terms before we start, so nothing here is used unearned:

Every trap below is really a test of ONE small procedure — the merge. So let's pin it down here, on this page, before we start hunting traps.

The single picture below shows both the diamond tree and one merge step in action — glance at it whenever a question feels abstract.

Figure — Multiple inheritance — Python's C3 linearization algorithm

True or false — justify

Python searches classes depth-first, left-to-right, up the inheritance tree.

False. That was the pre-2.3 rule and it could place a grandparent before a sibling; C3 replaced it precisely because depth-first violates child-before-parent (see The Diamond Problem).

In D(B, C) where B(A) and C(A), the base class A is searched twice — once through B, once through C.

False. C3 produces a list with no duplicates; A appears exactly once, at the latest position consistent with all constraints: [D, B, C, A, object].

The order you write the parents in — class D(B, C) vs class D(C, B) — changes the resulting MRO.

True. Local precedence is one of C3's three guarantees; swapping to D(C, B) gives [D, C, B, A, object], so parent write-order genuinely matters.

super() always calls the class you literally wrote as the parent.

False. super() walks to the next class in the MRO, which in D(B, C) can send a call inside B onward to its sibling C, not up to A (see super() and cooperative inheritance).

Every set of classes has some valid MRO if you try hard enough.

False. When two parents demand contradictory orders (one wants X before Y, another Y before X), no linear order satisfies both and Python raises TypeError.

C3 is essentially a Topological sort of the inheritance graph.

True, but constrained. It respects the partial order "child before parent" plus the extra local-precedence and monotonicity constraints, so it's a specific topological order, not just any one.

For a class using only single inheritance, the MRO is simply the chain from the class up to object.

True. With one parent per class there are no competing paths, so C3 degenerates to the obvious straight-line order (see Single inheritance).

Adding a new subclass at the bottom of a hierarchy can reorder the MRO of a class higher up.

False. Monotonicity guarantees existing relative orders are preserved; a new leaf never reshuffles the ancestors it inherits.

The last argument to merge, the literal list of parents [P_1, ..., P_n], is optional decoration.

False. That list is what enforces local precedence — without it, C3 could emit parents in an order different from how you wrote them.

Spot the error

"merge(L[B], L[C], [B, C]) — I'll take head B, it's a good head, so I remove B only from the first list."

Error: when you emit a good head you must remove it from every list it appears in — including the [B, C] parent list — otherwise it can never leave and the merge stalls.

"Head A is in the tail of list 2, so the merge fails and Python raises TypeError."

Error: one head being in a tail just means skip it and try the next list's head. Failure only happens when no list has a good head at all.

"A head is 'good' if it isn't the tail of its own list."

Error: the test is whether it appears in the tail of any remaining list, not just its own. A class can be a perfectly fine head of one list while blocking as a tail element of another.

"L[C] = merge(L[P_1], ..., [P_1,...,P_n])."

Error: the formula is L[C] = C + merge(...). You must prepend C itself — a class is always the first entry of its own MRO.

"After emitting a good head I restart merge from the first list every time."

✅ TRICK — this one is correct. You always re-scan from the first non-empty list; the misconception would be thinking you continue from where you skipped. You begin the scan afresh.

"D(B, C) with B(A), C(A) gives MRO [D, B, A, C, object] because I finish B's whole chain first."

Error: finishing B's chain first is depth-first thinking. A is in the tail of both parent lists, so it's blocked until C is emitted, giving [D, B, C, A, object].

Why questions

Why must a head be absent from every tail before it's safe to emit?

If X sits in some list's tail, something ahead of it there is a subclass of X not yet placed; emitting X now would put a parent before its child.

Why does the shared base end up last among its descendants rather than somewhere in the middle?

Every descendant lists the base in its tail, so the base stays blocked until all of them are emitted — pushing it to the latest valid position.

Why can't we just deduplicate a naive depth-first list to get the MRO?

Deduplication fixes duplicates but not order; depth-first may already have parents before siblings, and simply removing repeats keeps that wrong ordering intact.

Why does C3 refuse the A(X,Y) / B(Y,X) / C(A,B) hierarchy?

A demands X before Y while B demands Y before X; these are contradictory, so no single order satisfies both and merge runs out of good heads.

Why is monotonicity valuable to programmers, not just theorists?

It means understanding a class's MRO never gets silently rearranged when someone subclasses it later — behaviour you reasoned about stays stable.

Why does super() need the MRO instead of just remembering the parent?

Cooperative multiple inheritance (Mixins) relies on each class passing control to its MRO successor, which may be a sibling; only the MRO knows that successor.

Why is composition sometimes recommended over wrestling with C3?

Deep multiple-inheritance diamonds make MRO reasoning fragile; composition sidesteps the whole ordering problem by holding objects instead of inheriting them.

Edge cases

What is the MRO of a class with no explicit parents, like class A: pass?

[A, object]. Every class implicitly inherits object, so even a "parentless" class has a two-element linearization.

What is L[object], the base case of the whole recursion?

[object] — a single-element list. It has no further parents, so the recursion bottoms out here.

If two direct parents share no common ancestor beyond object, is there any diamond to worry about?

No true diamond, but C3 still runs; it simply lays the two independent chains one after the other, then merges their shared object at the end.

Can a class legally appear at position 1 (as a head) in one list and simultaneously be blocked in another during the same scan?

Yes, and that's the normal case — being a head somewhere doesn't help; if it's in any other tail it's skipped until unblocked.

What happens to MRO when the same parent is listed twice, e.g. class D(B, B)?

Python rejects it outright with TypeError: duplicate base class — this fails before C3 even runs, at class-creation time.

If parent lists are all empty except the final [P_1,...,P_n], what does merge return?

It emits the parents in their written order and finishes — this is exactly how local precedence is honoured when nothing else constrains them.

Recall One-line self-test

Cover everything above. Can you state, without peeking, why a good head must be absent from all tails, and why super() follows the MRO rather than the literal parent? Answer ::: A tail-appearance means an unplaced subclass still owes precedence, so emitting early breaks child-before-parent; and super() uses the MRO so cooperative chains can reach sibling classes.

Connections

Method Resolution Order
super() and cooperative inheritance
The Diamond Problem
Single inheritance
Mixins
Composition vs Inheritance
Topological sort