Python Method Resolution Order

2017-03-21

定义

首先需要定义下几个相关概念: linearizationMethod Resolution OrderMonotonicity

  1. The list of the ancestors of a class C, including the class itself, ordered from the nearest ancestor to the furthest, is called the class precedence list or the linearization of C.
  2. The Method Resolution Order (MRO) is the set of rules that construct the linearization. In the Python literature, the idiom “the MRO of C” is also used as a synonymous for the linearization of the class C.
  3. A MRO is monotonic when the following is true: if C1 precedes C2 in the linearization of C, then C1 precedes C2 in the linearization of any subclass of C.

在 Python2 中,存在两种类:经典类和新式类,因此存在两种不同的 MRO 方法。

经典类

对于经典类,MRO 方法很简单:使用深度优先,从左到右的方法搜寻基类。一个例子如下:

class A: pass

class B(A): pass

class C(A): pass

class D(B, C): pass

这样就有了一个菱形继承,对于 D 来说,其线性化(linearization)结果计算如下: 先从左边开始深度遍历,于是得到 D-B-A,然后对右边深度遍历得到 C-A。最终结果为:D-B-A-C-A。

稍后我们会看到对于新式类,这样的菱形继承关系将产生的不同的结果。

新式类

首先介绍几个有用的符号:

使用

来指明一串类的列表 [C1, C2, … CN]。

列表头为第一个元素:

而列表尾则是剩下的元素:

另外,使用:

来表示列表和 [C] + [C1, C2, …, CN]。

Python 的新式类基于 C3 Linearization 算法,考虑一个类 C 继承自基于 B1, B2, …, BN,那么类 C 的线性化结果 L[C] 计算如下:

the linearization of C is the sum of C plus the merge of the linearization of the parents and the list of the parents.

用符号表示的话,就是:

如果 C 是 object 类,那么它就没有父类,其线性化表示为:

但是通常情况下需要根据下面的规则计算 merge:

take the head of the first list, i.e L[B1][0]; the head is a good head if it is not in the tail of any other lists, then add it to the linearization of C and remove it from all of the lists in the merge, otherwise look at the head of the next list and take it, if it is a good head. Repeat the operation until all the class are removed ot it is impossible to find a good head. In later case, it it impossible to construct the merge, Python will refuse to create the class C and will raise an exception.

上面的描述,其思想有点类似于广度优先遍历类 C 的父节点,使得 merge 这个操作能保持父节点的顺序(monotonicity),即在复杂的多继承下,子类一定会在父类前面。

当 C 只有一个父类时,其线性化计算如下:

下面就考虑多继承:

例一


O = object

class F(O): pass

class E(O): pass

class D(O): pass

class C(D, F): pass

class B(D, E): pass

class A(B, C): pass

O,D,E 和 F 的线性化计算都比较简单:

那么 B 的线性化计算如下:

可以看到,D 是一个好头(good head),于是将其加入 B 的线性化列表中,并将 merge 中所有的 D 移除。而下面一步中,因为 O 出现 EO 的尾部中,所以跳过 O 转而考虑下一个列表的头,即 E。将 E 加入到 B 的线性列表中,移除所有的 E。最后将 O 加入列表。

类似地,可以计算 C 的线性化结果:

最后,可以计算:

可以看到 A 的线性化结果类似于对 A 的父类做一次广度优先扫描(只是类似)得到的结果,这样就可以保证单调性,即子类在线性化列表中比父类前。

例二

再来看看上述经典类的例子,将 Object 用 A 表示,我们有:

A = Object

class B(A): pass

class C(A): pass

class D(B, C): pass

那么 D 的线性化计算结果为:

不同于经典类的线性化结果!

例三

最后展示一个会导致类线性化结果冲突的例子:

O = object

class X(O): pass

class Y(O): pass

class A(X, Y): pass

class B(Y, X): pass

class C(A, B): pass

可以计算得到:

但是在计算 L[C] 时则会出错:

这是,Python 就会抛出异常:

TypeError: Cannot create a consistent method resolution
order (MRO) for bases X, Y

参考:

  1. The Python 2.3 Method Resolution Order