Method Resolution Order in Multiple Inheritance

Single inheritance has one obvious lookup order: the class, then its base, then the base’s base. Multiple inheritance has no such order, because a class graph is a partial order and method lookup needs a total order. Different languages answer differently, and the differences are not cosmetic — they change which override wins in a diamond and whether a program’s meaning can change when an unrelated class is added elsewhere in the hierarchy.

Why depth-first, left-to-right fails

The intuitive rule is to visit direct bases in declaration order, recursing into each one’s ancestors before moving to the next base. C++ uses something close to this for its lookup, with the added rule that a name found in two unrelated bases makes the reference ambiguous and the program ill-formed unless qualified. That works because C++ resolves at compile time and can reject ambiguity.

A dynamically dispatched language cannot reject ambiguity per call without making the class graph brittle: whether an ambiguity exists would depend on which classes happen to define the name, and adding a method to a class could break unrelated code. So such languages must define a total order over the ancestors and let the first definition in that order win.

Consider the classic diamond:

    A
   / \
  B   C
   \ /
    D

Depth-first, left-to-right from D gives D, B, A, C. That order has a defect: A appears before C, even though C is a direct base of D and A is not. If C overrides a method defined in A, and B does not, the order picks A’s version and silently ignores C’s override — even though C is more specific with respect to D than A is. Intuitively, a direct base should be consulted before a base’s base.

The obvious repair is to concatenate the linearisations of the direct bases, in declaration order, and drop duplicates. It fails as soon as two bases share ancestors in a different order. Let B derive from D then E, and C derive from D then F, all four deriving from a common root O; let A derive from B then C. The base linearisations are B, D, E, O and C, D, F, O. Concatenating them under A gives A, B, D, E, O, C, F, which places D before C even though C is a direct base of A and C’s own order requires C before D. The rule has emitted D while walking B, before it had a chance to see that C constrains it. A local rule cannot fix this, because the constraint arrives from a base that has not been visited yet.

The merge rule and what it preserves

C3 linearisation, introduced for Dylan and later adopted by Python, defines the linearisation of a class as the merge of three kinds of sequence:

1. The linearisations of each direct base, in declaration order.
2. The list of the direct bases themselves, again in declaration order.
3. The list holding the class alone, which in practice is treated as the head of the remaining merge; the effect is that the class itself precedes all of its ancestors.

Merging means repeatedly taking the head of the first sequence that does not appear in the tail of any other sequence and appending it to the output. A candidate that appears in some other sequence’s tail is blocked: taking it would place it before something that must precede it.

The merge preserves two properties that the local rules do not:

Local precedence order. If a class lists bases B1, B2 in that order, B1 precedes B2 in the linearisation. This makes the declaration order meaningful and is why reordering bases is a semantic change.

Monotonicity. If a class X precedes Y in the linearisation of a class, then X precedes Y in the linearisation of every subclass of that class. Adding a new class to a hierarchy therefore cannot reverse an existing precedence, which means a program’s method resolution cannot change because of a class defined elsewhere. This is the property the earlier rules lacked, and it is the one that makes the order safe to reason about across module boundaries.

class A: pass
class B(A): pass
class C(A): pass
class D(B, C): pass

# D.__mro__ == (D, B, C, A, object)
# merge([B,A,object], [C,A,object], [B,C]) with the object links elided:
#   B is head of the first, not in any tail -> take B
#   A is head of [A], but in tail of [C,A] -> blocked, skip
#   C is head of [C,A], not in any tail    -> take C
#   then A, then object

The blocked step is the whole mechanism. A depth-first walk would have taken A at that point; C3 refuses because C must precede A, and C has not been emitted yet. The refusal is what turns the partial order into a consistent total order.

When linearisation fails

Not every class graph has a C3 linearisation. A cycle is the trivial case and is rejected at class creation. The interesting case is an inconsistent hierarchy: one where the local precedence orders of different classes contradict each other. If X declares bases (A, B) and Y declares bases (B, A), and a class Z inherits from both, the merge has no valid head — A is blocked by Y’s order and B is blocked by X’s — and the class definition fails.

The failure is a feature. Without it, the language would have to either pick an order that violates one of the declared orders or defer the error to a method call, where it would be harder to diagnose and might depend on which methods exist. Rejecting the definition makes the inconsistency a property of the hierarchy rather than of the program’s behaviour. The cost is that a library cannot be extended in a way that combines two unrelated hierarchies whose base orders conflict, even when no method is actually ambiguous in the resulting class. This is a real limitation of the approach and the main argument for preferring composition or interfaces over multiple implementation inheritance.

Comparison with other orders

C++ resolves names rather than linearising. A name lookup in a class with multiple bases searches each base subobject; if the name is found in more than one base and those bases are not related by inheritance, the reference is ambiguous and must be qualified with the base’s name. The rule is applied per name, so a hierarchy can be ambiguous for one member and unambiguous for another, which C3 cannot express. The cost is that adding a member to a base class can make an existing unqualified reference ambiguous, breaking client code — the compile-time analogue of the fragility described in the fragile base class problem.

The Common Lisp Object System takes a different route: it computes a class precedence list by a topological sort of the local precedence orders — the order in which each class lists its direct superclasses — and, among the classes that are candidates at each step, chooses the one that appears earliest in the local precedence order of the most recently selected class, breaking remaining ties by starting from the class itself and walking the orders in sequence. CLOS lets a program redefine the order through the metaobject protocol, which is more flexible than a fixed linearisation and correspondingly harder to predict.

Java and C# avoid the problem for state by allowing only one superclass and any number of interfaces. Interfaces carry no fields and, in the common case, no implementation, so a class that implements two interfaces with the same method signature has one implementation that satisfies both. Where interfaces do provide default implementations, the conflict rules are explicit: the class must override the method, or the compiler rejects it. The design decision is that ambiguity should be resolved by the programmer, not by a linearisation algorithm.

Traits and mixins occupy a middle position. A trait provides method implementations that are flattened into the class, with explicit disambiguation required when two traits define the same method. Flattening means the composed class has a single, ordinary method table; the composition happens at class definition time, so there is no run-time lookup order at all. The expressive cost is that a trait cannot easily call “the next implementation” in a chain, which the linearised orders can.

What the order means for super calls

In a linearised language, a call to the next method in the order is well defined even with multiple inheritance: it means the implementation that follows the current one in the receiver’s linearisation, skipping classes that do not define the method. That gives cooperative multiple inheritance, where each class in a chain performs its part and delegates upward. It also means a class must be written to tolerate being placed at any position in a chain it did not anticipate, which is a stronger requirement than single inheritance imposes and the reason cooperative hierarchies are usually built from a small set of documented mixins. The alternative arrangement, where the compiler fixes a slot per method and the object carries a table per polymorphic base, is the one described in vtable layout and the cost of a virtual call.

The order is computed once per class, at class creation, and cached. Lookup at run time is then a scan of the linearisation for the first class that defines the selector, or, in optimised implementations, a per-class method table built from the linearisation so the scan becomes a single probe. The cost of the algorithm is paid at class definition, not at call time; the cost at call time is the same as any other dynamic dispatch, and the number of classes in the linearisation only affects how the table was built.