Hacking Limbo

Reading / Coding / Hacking

Method Resolution Order in Python

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 计算的结果。