Python 的类支持多继承，假如一个类 C 继承自 A 和 B，那么在调用它的实例方法时的
查找路径（Method Resolution Order，即 MRO）是怎样的呢？以前用 Python 的时候没有
思考过这个问题，因为当时几乎没有用过多继承，一直到在 Ruby 里大量使用 mixin 的
时候才对这个有所了解（Ruby 的 module mixin 可以看做是另一种形式的多继承）。
我在 Python 官网找到了 The Python 2.3 Method Resolution Order
这篇文章，作者很详尽地讲解了从 Python 2.3 开始使用的 C3 Method Resolution Order
方法（这个算法来自一篇叫 A Monotonic Superclass Linearization for Dylan 的论文）。
需要注意的是这个 C3 MRO 只对 new-style class 有效，classic class 的 MRO 仍然
保持从左至右（指的是声明类时指定的父类的顺序）的深度优先的查找方法。new-style
class 的 MRO 之所以比 classic class 复杂，是因为在多继承的基础上所有的 new-style
class 都派生自同一个父类 object，必须用稍微复杂一点的算法来确定一个线性的
继承路径。以下提到的类都属于 new-style class.
对于一个继承自 B1, B2, B3, ... BN 的类 C，它的线性继承关系 L(C) 是这样计算的：
L(C) = C + merge(L(B1), L(B2), L(B3), ... L(BN), [B1, B2, ... BN])
merge 方法的伪代码如下：
def merge(*args):
results = []
for current in args:
for cls in current:
if cls in tail_of_other_classes(args, current):
break outer_loop
else:
results.append(cls)
tail_of_other_classes(args, current).delete(cls)
:outer_loop:
def tail_of_other_classes(all, current):
return flatten(map(lambda xs: xs[1:], filter(lambda x: x != current, all)))
以下面这两个继承关系的 MRO 计算结果为例：
## example 1
O = object # L(O): O
class F(O): pass # L(F) = FO
class E(O): pass # L(E) = EO
class D(O): pass # L(D) = DO
# L(C) = C + merge(DO, FO, DF)
# = C + D + merge(O, FO, F)
# = C + D + F + merge(O, O)
# = CDFO
class C(D, F): pass
# L(B) = B + merge(DO, EO, DE)
= BDEO
class B(D, E): pass
# L(A) = A + merge(BDEO, CDFO, BC)
# = A + B + merge(DEO, CDFO, C)
# = A + B + C + merge(DEO, DFO)
# = A + B + C + D + merge(EO, FO)
# = ABCDEFO
class A(B, C): pass
## example 2
O = object
class F(O): pass
class E(O): pass
class D(O): pass
class C(D,F): pass
# L(B) = B + merge(EO, DO, ED)
# = B + E + merge(O, DO, D)
# = BEDO
class B(E,D): pass
# L(A) = A + merge(BEDO, CDFO, BC)
# = A + B + merge(EDO, CDFO, C)
# = A + B + E + merge(DO, CDFO, C)
# = A + B + E + C + merge(DO, DFO)
# = A + B + E + C + D + merge(O, FO)
# = ABECDFO
class A(B,C): pass
这里还有一种例外情况：
O = object
class X(O): pass
class Y(O): pass
class A(X, Y): pass
class B(Y, X): pass
# the following declaration will raise error for Python >= 2.3
# TypeError: Error when calling the metaclass bases
# Cannot create a consistent method resolution order (MRO) for bases object, X, Y
class C(A, B): pass
上面这个继承关系会触发异常，因为根据 C3 MRO 算法：
L(C) = C + merge(AXYO, BYXO, AB)
= C + A + B + merge(XYO, YXO)
merge(XYO, YXO) 存在一个“死锁”，无法继续运算下去。
Updated on Sep. 3: 还有另外一种死锁的情况：
O = object
class B(O): pass
class C(B): pass
# the following declaration will raise error for Python >= 2.3
# TypeError: Error when calling the metaclass bases
Cannot create a consistent method resolution order (MRO) for bases object, C, B
# L(N) = N + merge(BO, CBO, BC)
# both B and C block the calculation
class N(B, C): pass
# this works because:
# L(N) = N + merge(CBO, BO, CB)
# = N + C + merge(BO, BO, B)
# = NCBO
class N(C, B): pass
BTW: new-style class 有一个类方法 mro()，返回的就是 C3 MRO 计算的结果。