如何理解 Python 的 MRO 算法：深度优先与 C3 线性化本质区别

Python 作为一种支持多重继承的面向对象语言，必须有一个清晰的规则来确定当子类调用一个方法时，应该在哪个父类中查找该方法。这个规则就是方法解析顺序（Method Resolution Order, MRO）。

在 Python 2.3 之后，所有新式类都采用了一种名为 C3 线性化（C3 Linearization）的算法来计算 MRO，它取代了早期复杂多重继承中容易出错的深度优先搜索（DFS）规则。

深度优先搜索（DFS） MRO 的缺陷

传统的简单深度优先 MRO 遵循的原则是：从当前类开始，深度优先遍历第一个父类的继承链，直到根类，然后才回溯到第二个父类。

这种简单策略在处理“菱形继承”（Diamond Problem）时会导致混乱，更重要的是，它无法保证父类的相对顺序，从而破坏了程序员在定义类时所期望的局部优先级。

假设我们有以下继承结构：

class X:
    def speak(self): return "X"
class Y(X):
    def speak(self): return "Y"
class A(Y):
    def speak(self): return "A"
class B(X):
    def speak(self): return "B"
class C(A, B):
    # 如果使用简单的DFS，MRO可能是 C -> A -> Y -> X -> B -> X -> object
    # 但这违反了B必须在X之前被检查的规则。
    pass

在更复杂的场景中，DFS 可能会导致一个父类在其所有子类被检查之前就被访问，这通常是不可接受的。

Python 解决方案：C3 线性化算法

C3 线性化算法的设计目标是确保两个核心属性得到满足：

1. 局部优先级（Local Precedence Order）： 子类优先于父类，并且在类定义中列出的父类（左边）优先于后面列出的父类（右边）。例如 class C(A, B) 必须保证 A 在 B 之前被检查。
2. 单调性（Monotonicity）： 如果一个类 X 在类 Y 的 MRO 中出现，那么在任何继承自 X 和 Y 的子类中，X 也必须出现在 Y 之前。简而言之，祖先必须保持其相对顺序。

C3 算法通过递归地将当前类的所有父类列表进行合并（Merge）来计算 MRO。合并过程遵循严格的“Head-of-List”规则：

只有当一个类是其 MRO 列表的“头部”（即列表中的第一个元素），并且它不在任何其他待合并列表的“尾部”时，才能将其取出并添加到最终的 MRO 列表中。

C3 算法实战演示

我们可以使用 .__mro__ 属性或 help() 函数来查看 Python 实际计算出的 MRO。

考虑经典的“Z”字形继承结构：

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

1. C 的 MRO 计算：

C 的父类列表是 [A, B, object]。C3 保证了 A 在 B 之前。

print(C.__mro__)
# (<class '__main__.C'>, <class '__main__.A'>, <class '__main__.B'>, <class '__main__.O'>, <class 'object'>)

2. D 的 MRO 计算：

D 的父类列表是 [B, A, object]。C3 保证了 B 在 A 之前，同时仍满足单调性，O 在 A 和 B 之后。

print(D.__mro__)
# (<class '__main__.D'>, <class '__main__.B'>, <class '__main__.A'>, <class '__main__.O'>, <class 'object'>)

演示 C3 保持单调性的优势

我们尝试一个会使简单 DFS 失败的结构，但 C3 能够成功解析，并保持 A 的继承顺序：

class Root:
    def who(self): print("Root")
class P1(Root):
    def who(self): print("P1")
class P2(Root):
    def who(self): print("P2")
class C1(P1, P2):
    pass
class C2(P2, P1):
    pass

# C1 优先 P1，然后 P2
print("C1 MRO:", [cls.__name__ for cls in C1.__mro__])
# C1 MRO: ['C1', 'P1', 'P2', 'Root', 'object']

# C2 优先 P2，然后 P1
print("C2 MRO:", [cls.__name__ for cls in C2.__mro__])
# C2 MRO: ['C2', 'P2', 'P1', 'Root', 'object']

在这两个例子中，Root 始终排在 P1 和 P2 之后，即使 P1 和 P2 的相对顺序发生了变化。这就是 C3 算法的核心优势：它提供了一个可预测、一致且局部优先级正确的方法解析顺序，极大地提高了 Python 多重继承的健壮性。