Python MRO: How C3 Linearization Works

This article provides an overview of how Python determines the sequence of classes searched when looking up attributes and methods in complex inheritance hierarchies. You will learn the core principles of Python's Method Resolution Order (MRO), the mathematical formula behind the C3 linearization algorithm introduced in Python 2.3, and a step-by-step walkthrough demonstrating how Python computes the lookup sequence.

What Is Method Resolution Order (MRO)?

Method Resolution Order (MRO) is the ordered list of classes Python traverses to find an attribute or method on an instance. In single inheritance, this order is trivial: an instance checks its own class, then its parent, and continues up to object.

In multiple inheritance, determining the correct order is more complex. Python uses the C3 linearization algorithm to guarantee three fundamental properties:

1. Children precede parents: A subclass is always checked before its base classes.
2. Local Precedence Order: The order of base classes declared in a class definition (left to right) is preserved.
3. Monotonicity: If class \(A\) precedes class \(B\) in the MRO of one class, \(A\) must precede \(B\) in the MRO of any subclass.

If an inheritance graph violates these rules, Python rejects the class definition and raises a TypeError.

The C3 Linearization Algorithm

The linearization of a class \(C\)—denoted as \(L[C]\)—is defined recursively. It is the class \(C\) itself prepended to the result of merging the linearizations of its direct base classes along with the list of direct base classes themselves.

The Linearization Formula

For a class \(C\) that inherits from base classes \(B_1, B_2, \dots, B_n\):

\[L[C] = [C] + \operatorname{merge}(L[B_1], L[B_2], \dots, L[B_n], [B_1, B_2, \dots, B_n])\]

The base case is the root class: \[L[\text{object}] = [\text{object}]\]

The Merge Step

The merge operation evaluates a series of lists using the following rules:

1. Look at the head (the first element) of the first list in the merge collection.
2. Check if this head appears in the tail (all elements after the first element) of any other list in the collection.
3. If it does not appear in any tail, it is considered a "good head":
   • Append this class to the output MRO.
   • Remove this class from all lists in the merge collection.
4. If it does appear in a tail, reject it for now. Move to the head of the next list in the collection and test if that class is a valid head.
5. Repeat steps 1–4 until all lists are empty (successful linearization).
6. If the algorithm scans through all heads without finding a valid candidate, the hierarchy cannot be linearized, and Python raises a TypeError.

Step-by-Step Calculation Example

Consider the classic diamond problem with the following hierarchy:

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

1. Compute Base Linearizations

• \(L[O] = [O]\)
• \(L[A] = [A] + \operatorname{merge}(L[O], [O]) = [A, O]\)
• \(L[B] = [B] + \operatorname{merge}(L[A], [A]) = [B, A, O]\)
• \(L[C] = [C] + \operatorname{merge}(L[A], [A]) = [C, A, O]\)

2. Compute \(L[D]\)

Using the formula: \[L[D] = [D] + \operatorname{merge}(L[B], L[C], [B, C])\] \[L[D] = [D] + \operatorname{merge}([B, A, O], [C, A, O], [B, C])\]

Merge Steps:

• Step 1: Consider the head of the first list, B.

  • Is B in the tail of [C, A, O]? No.
  • Is B in the tail of [B, C]? No (B is the head, not in the tail [C]).
  • B is a valid head. Output: [D, B].
  • Remaining lists: \(\operatorname{merge}([A, O], [C, A, O], [C])\)

• Step 2: Consider the head of the first list, A.

  • Is A in the tail of [C, A, O]? Yes (the tail is [A, O]).
  • A is invalid. Skip to the next list's head: C.
  • Is C in the tail of [A, O]? No.
  • Is C in the tail of [C]? No.
  • C is a valid head. Output: [D, B, C].
  • Remaining lists: \(\operatorname{merge}([A, O], [A, O])\)

• Step 3: Consider the head of the first list, A.

  • Is A in the tail of [A, O]? No.
  • A is a valid head. Output: [D, B, C, A].
  • Remaining lists: \(\operatorname{merge}([O], [O])\)

• Step 4: Consider the head of the first list, O.

  • Is O in the tail of [O]? No.
  • O is a valid head. Output: [D, B, C, A, O].
  • Remaining lists are all empty.

Result

The final MRO for class D is: [D, B, C, A, O]

You can verify this directly in Python using the mro() method:

print([cls.__name__ for cls in D.mro()])
# Output: ['D', 'B', 'C', 'A', 'O']