Why does Python use C3 linearization instead of naive depth-first attribute lookup?
answer
- Depth-first loses something in a diamond
- An override shadowed by its own base
- Two guarantees, not one
- Base order preserved; ancestors last
- Parents' relative order survives in children
basics
~10 sDepth-first, left-to-right lookup reaches a shared base before the second branch, so a class's override of an inherited method can be silently skipped. C3 guarantees local precedence order and monotonicity, which makes that impossible.
solid answer
~40 sA depth-first walk of `D(B, C)` where both derive from A visits `D, B, A` and only then C — so if C overrides a method it inherited from A, D gets A's version and C's override is invisible. C3 linearization forbids that by construction with two guarantees: **local precedence order**, the direct bases keep the order written in the class statement, and **monotonicity**, the class's order is consistent with each base's own order, so a class always precedes its ancestors. The result is `D, B, C, A, object`. It is also a *total* order computed once, which is what makes a cooperative hand-off chain well defined across a whole hierarchy. When the constraints cannot all hold, C3 refuses rather than picking an order, which is why an inconsistent hierarchy fails at class creation.
code
python · 14 linesclass Cost:
def score(self): return "Cost"
class Fast(Cost):
pass
class Cheap(Cost):
def score(self): return "Cheap"
class Plan(Fast, Cheap):
pass
print(Plan().score())
print([c.__name__ for c in Plan.__mro__])go deeper
You are not expected to name the algorithm. Know that Python flattens the hierarchy into one order and that a plain left-branch-to-the-root search would give a different, wrong answer.
Be able to show the failure concretely: put an override on the right branch of a diamond and explain why depth-first would return the shared base's version instead.
Name and apply both guarantees, hand-trace a small merge, and explain that an unsatisfiable set of constraints is refused rather than resolved arbitrarily.
Own the tradeoff: the algorithm buys predictable, stable behaviour under extension, but a hierarchy that needs its order printed to be understood is a signal to flatten it or compose instead of inherit.
### The failure C3 was adopted to remove Take the classic diamond, but put the override on the *right* branch: ```python class Cost: def score(self): return "Cost" class Fast(Cost): pass class Cheap(Cost): def score(self): return "Cheap" class Plan(Fast, Cheap): pass ``` A naive depth-first, left-to-right search asks Plan, then descends the whole left branch: Fast, then Cost. `Cost.score` exists, so lookup stops there and returns `"Cost"` — Cheap is never reached, and Cheap's deliberate override of the very method it inherited from Cost is silently discarded. Worse, the outcome depends on which subclass you look from, so a class can lose an override merely by being combined with a sibling. Under C3 the order is `Plan, Fast, Cheap, Cost, object` and the call returns `"Cheap"`, which is the answer anyone reading the class definitions expects. ### The two guarantees **Local precedence order.** The direct bases appear in the linearization in the order written in the class statement. Base order is therefore meaningful and honoured, rather than being a hint that a deeper walk may override. **Monotonicity.** If class P precedes class Q in some class's order, P precedes Q in the order of every subclass of it too. Equivalently: a class's order is consistent with each of its bases' orders, and no class ever appears before one of its own subclasses. This is the property that keeps ancestors behind all of their descendants, and it is what makes a hierarchy's behaviour stable as you extend it — adding a subclass cannot reshuffle the relative order its parents already agreed on. ### The merge, briefly C3 computes the order of a class C with bases B1..Bn as C followed by a merge of the bases' orders plus the base list itself. The merge repeatedly takes the head of the first remaining sequence that does not appear in the *tail* (anything but the head) of any other sequence, and appends it. "Not in anyone's tail" is the check that stops a class being emitted while something that must precede it is still pending. Hand-tracing `Plan`: ```text L[Fast] = Fast, Cost, object L[Cheap] = Cheap, Cost, object merge(L[Fast], L[Cheap], [Fast, Cheap]) Fast -> head, in no tail -> take Cost -> head, but in Cheap's tail -> skip this sequence Cheap -> head of next, in no tail -> take Cost -> now in no tail -> take object -> take L[Plan] = Plan, Fast, Cheap, Cost, object ``` If every remaining sequence's head appears in some other sequence's tail, the merge is stuck — that is exactly the situation reported as a `TypeError` at class creation. C3 never invents an order; it either satisfies both guarantees or fails. ### Why totality matters as much as correctness Because the result is a single linear order over the whole ancestor set, "the next class after this one" is always well defined, and it is defined with respect to the *instance's* class rather than the class the code lives in. That is what makes a cooperative chain traverse every branch of a diamond exactly once — under a tree walk there is no coherent notion of "next", so each class would have to name its successor and a diamond's shared base would run twice or not at all. And it is cheap: the order is computed once at class creation and cached, so lookup is a scan over a tuple, backed by a per-type method cache. The algorithm's cost lands entirely at class-definition time. ### Where the tradeoff actually bites C3 buys predictability, not simplicity. The order it produces is correct but not always *obvious* — reordering two bases can move a shared ancestor several positions, and a deep hierarchy may need printing to be understood. That is a real cost, and the senior read is that a hierarchy you cannot predict without printing its order is a hierarchy that should be flatter or composed rather than inherited. The algorithm's job is to make multiple inheritance analysable; it is not a licence to make the graph arbitrarily deep. Historically this is settled ground: depth-first lookup belonged to Python 2's classic classes, C3 arrived with new-style classes in Python 2.3, and Python 3 — through 3.14 — has only ever used C3.
- State monotonicity precisely enough to check it against an example.If P comes before Q in some class's linearization, then P comes before Q in the linearization of every subclass of that class. The practical consequence is that a subclass can insert classes into the order but never reverse an ordering its parents already established — so extending a hierarchy cannot silently reshuffle inherited behaviour.
- Why is a total order, rather than just a correct one, important?Because it makes "the next class after this one" well defined for the whole hierarchy, relative to the instance's class rather than the class the code sits in. A cooperative hand-off chain therefore visits each ancestor of a diamond exactly once; with a tree walk, a shared base would run twice or be skipped entirely.
- What is the cost of C3 at runtime?Essentially none. The linearization runs once per class, at class creation, and is cached as a tuple; attribute lookup is a scan over that tuple backed by a per-type method cache. The expense is paid at definition time, and the real cost is cognitive — deep hierarchies whose order needs printing to be understood.
Depth-first reads one branch of the family tree to the root before glancing at the other; C3 interviews every relative once, in an order that never lets a grandparent answer before a parent.
saying these in an interview costs you the question
- Describes the MRO as depth-first, left-to-right
- Names only base order and misses monotonicity
- Thinks C3 picks some order when constraints conflict
- Claims the linearization is recomputed per lookup
- Says duplicates are allowed and simply skipped