27.2 Method Resolution Order (MRO) and the C3 Algorithm

The Method Resolution Order (MRO) is the sequence in which Python searches the class hierarchy to find the correct method or attribute to execute when it is requested on an object. In single inheritance, this is a simple, linear path up the inheritance chain. However, with multiple inheritance, the hierarchy becomes a directed acyclic graph (DAG), and the search order becomes critically important to avoid ambiguity and ensure predictable behavior. The C3 linearization algorithm is the deterministic algorithm Python uses, since version 2.3, to create this MRO. It was introduced to replace the previous depth-first, left-to-right approach, which was prone to creating inconsistencies and non-monotonic behavior.

The Core Principles of the C3 Algorithm

The C3 algorithm is designed to satisfy three key properties, making the resulting MRO more predictable and robust:

Consistency with the Inheritance Graph: The MRO must respect the order of base classes as declared in a class definition. If class D(B, C) is defined, the MRO for D should visit B before C, all else being equal.
Consistency with Local Precedence Order: The order of base classes in a class declaration provides a local ordering constraint that must be preserved globally.
Monotonicity: If class A comes before class B in the MRO of a class C, then A should always come before B in the MRO of any subclass of C. This prevents a method from being overridden by one of its own subclasses, a problem that plagued the old MRO style.

The algorithm works by merging the MROs of the parent classes while adhering to the local precedence order. The formal “merge” operation follows the rule: take the head of the first list if it is not in the tail of any other list; otherwise, move to the next list and try again.

Visualizing MRO with `mro` and `mro()`

Every class in Python has a __mro__ attribute, which is a tuple of the classes in the order they are searched. You can also call the mro() method on the class to get the same result as a list. This is the primary tool for inspecting and debugging the inheritance hierarchy.

class A:
    pass

class B(A):
    pass

class C(A):
    pass

class D(B, C):
    pass

# Inspecting the MRO
print(D.__mro__)
# Output: (<class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.A'>, <class 'object'>)

print(D.mro())
# Output: [<class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.A'>, <class 'object'>]

This output demonstrates the classic “diamond” inheritance pattern. The MRO is D -> B -> C -> A -> object. It satisfies the local precedence: B comes before C as declared in class D(B, C). It also satisfies monotonicity: the MRO of B is (B, A, object) and the MRO of C is (C, A, object), and in D’s MRO, B comes before C, and A comes after both.

A Deeper Example: The C3 Merge in Action

Let’s trace a more complex example to understand the merge process. The algorithm’s steps are often more illustrative than the formal definition.

class O:
    pass

class A(O):
    pass

class B(O):
    pass

class C(O):
    pass

class D(A, B):
    pass

class E(B, C):
    pass

class F(D, E):
    pass

print(F.mro())
# Output: [F, D, A, E, B, C, O, object]

To compute F’s MRO, we need to merge the sequences of its parents and its own declaration:

The linearization of F is L[F] = [F] + merge(L[D], L[E], [D, E])
L[D] = [D, A, B, O, object]
L[E] = [E, B, C, O, object]
So, L[F] = [F] + merge([D, A, B, O, object], [E, B, C, O, object], [D, E])

The merge process is as follows:

Step 1: Look at the first element of the first list, D. Is D in the tail of any other list? The tails are [A, B, O, object], [E, B, C, O, object], and [E]. D is not in any of these tails. So, take D. Now the lists are [A, B, O, object], [E, B, C, O, object], [E].
Step 2: Look at the first element of the new first list, A. Is A in any other tail? No. Take A. Lists now: [B, O, object], [E, B, C, O, object], [E].
Step 3: Look at B (first list). B is in the tail of the second list ([B, C, O, object]). So, skip to the next list. Look at E (second list). Is E in the tail of any other list? The tail of the first list is [B, O, object] – E is not there. The tail of the third list is [] – it’s empty. So, take E. Lists now: [B, O, object], [B, C, O, object], [].
Step 4: The third list is empty, so we ignore it. Look at B from the first list. B is not in the tail of the second list ([C, O, object]). So, take B. Lists now: [O, object], [C, O, object].
Step 5: Look at O. O is in the tail of the second list ([O, object]). So, skip to the next list. Look at C. C is not in the tail of the first list ([O, object]). So, take C. Lists now: [O, object], [O, object].
Step 6: Take O (it’s at the head of both lists and not in any tail). Then take object.

The final merged list is [D, A, E, B, C, O, object]. Prepend [F] to get the final MRO: [F, D, A, E, B, C, O, object].

Common Pitfalls and Best Practices

Inconsistent Method Resolution Order: The most common error is creating a class hierarchy that C3 cannot linearize, resulting in a TypeError. This happens when the base class declarations create conflicting constraints that cannot be resolved monotonically.

class A:
    pass
class B(A):
    pass
# This will cause a TypeError because the constraints are inconsistent.
# The local precedence from C requires A before B.
# The local precedence from D requires B before A.
# C3 cannot satisfy both.
class C(A, B):
    pass
# Output: TypeError: Cannot create a consistent method resolution order (MRO) for bases A, B

Misunderstanding super(): The super() function does not simply call the parent class. It delegates to the next class in the MRO. This is a crucial distinction in multiple inheritance. Each call to super() cooperates to navigate the entire inheritance graph.
```
class A:
    def run(self):
        print("A")
        super().run()  # This does not error; it calls the next in MRO!

class B:
    def run(self):
        print("B")

class C(A, B):
    def run(self):
        print("C")
        super().run()

c = C()
c.run()
# Output:
# C
# A
# B
```
Here, C’s MRO is (C, A, B, object). When A.run() calls super().run(), the next class in the MRO is B, so B.run() is executed. This cooperative design is essential for well-behaved multiple inheritance.
Best Practice: Use Mixins: Favor using “mixins” – small, focused classes designed for multiple inheritance. They should typically not define their own __init__ and should use super() to call into the next method in the MRO, ensuring the chain of calls is never broken. Always document the expected method resolution order for your mixins.

The Core Principles of the C3 Algorithm

Visualizing MRO with __mro__ and mro()

A Deeper Example: The C3 Merge in Action

Common Pitfalls and Best Practices

Visualizing MRO with `mro` and `mro()`