Python的MRO算法(The Python 2.3 Method Resolution Order-翻译)

由Michele Simionato撰写, 原文

摘要

本文是为了那些想要理解Python 2.3的MRO算法——C3算法的程序员们准备的。尽管不是为了新人准备的，但通过几个例子，本文还是具有教学意义的。我不清楚是否已有和本文相同主题的公开文档，因而，本文应该是有用的。

声明

基于Python2.3的授权许可，我将本文贡献给了Python软件基金会(Python Software Foundation).按照惯例，我会告知读者，接下来的内容应该是正确的，但我不会担保。使用本文，自担风险。

致谢

（感谢)在Python邮件列表中给与我支持的所有人;(感谢)指出我多处不准确之处并让我增加局部优先排序的Paul Foley;(感谢)David Goodger在reStructuredText格式排版上的帮助;(感谢) David Mertz在编辑方面的帮助；(感谢)Joan G. Stark在绘制pythonic图片方面的帮助;最后，感谢热情将本文添加到Python 2.3官方主页的 Guido van Rossum.

开篇(The beginning)

那幸运之人，发现事物的起因 (Felix qui potuit rerum cognoscere causas) -- 维吉尔(Virgilius)

事情要从Samuele Pedroni发给Python开发邮件列表的一封邮件开始[1]。在他的邮件中，Samuele证明了Python 2.2的方法解析顺序(MRO)不是单调的，并建议替换成C3。Guido 认可了他的观点，所以现在Python 2.3使用C3方法解析顺序.C3方式本身和Python不搭嘎，因为它是由从事Dylan的人发明的，并在一篇面向lisp开发者的论文中被阐述过[2]。希望该论文给那些想要理解这个MRO变化的Python使用者(Pythonistas)一次热烈讨论。

首先， 我要声明，我接下来要说的仅适用于Python 2.2引入的新式类，而旧式类维持原有的方法解析顺序:深度优先、从左到右。所以，并没有破坏使用旧式类的老的代码；尽管在原则上可能会破坏Python 2.2的新式类，但实践中，C3解析顺序不同于Python 2.2解析顺序的地方是很少的，所以并不会像猜测的那样破坏代码。

所以，别害怕

此外， 除非你重度使用了多继承并且使用了复杂的层次体系，否则，你不需要理解C3算法，可以直接跳过本文。另一方面，如果你想了解多继承是如何工作的，本文就满足你的需要。本文要说的内容并不像你想象的那么复杂。

本文从下述定义开始：

1. 在一个复杂的多继承体系中，给定类C，很难确定哪些方法被重写了，例如：确定类C的祖先顺序。
2. 类C的祖先列表，包含类C本身，从最近的祖先开始，一直到最远的祖先；成为类C的类优先序列(class precedence list)或者线性化(linearization)。
3. 方法解析顺序(MRO)是一系列用于构建线性化序列的规则；在Python中，术语"the MRO of C和类C的线性化一个意思。
4. 例如，在单继承的层次中，如果C是C1的子类、C1是C2的子类，那么C的线性化就是[C, C1, C2];然而，在多继承层次中，构建类的线性化列表就很麻烦，因为构建一个满足局部优先顺序(local precedence ordering)和单调性(monotonicity)的现象化会更困难。
5. 我会在后文讨论局部优先顺序，但要在这先说下单调性。当满足"如果在C的线性化中，C1在C2之前，那么在C的任意子类的线性化中，C1都在C2之前"时, 一个MRO就是单调性的。
6. 不是所有的类都会有线性化。在复杂的层次中，存在着一些不可能从一个类派生出一个新的子类使得该子类的序列化满足要求情况。
   

这里，我给出这种情形的一个例子，考虑下面的层次：

>>> O = object
>>> class X(O): pass
>>> class Y(O): pass
>>> class A(X,Y): pass
>>> class B(Y,X): pass

用继承图表示，如下图(其中O表示object类，而object是所有新式类继承层次的起点)：

 — — — — — —
|           |
|    O      |
|  /   \    |
 - X    Y  /
   |  / | /
   | /  |/
   A    B
   \   /
     ?

在这种场景下，不可能从A、B中派生出一个新的类C，因为：在A的线性化中，X在Y前面；而在B的线性化中，Y在X前面。那么C的方法查找顺序中，就会模棱两可义。

在这种情形下，Python 2.3会抛出一个异常(TypeError: MRO conflict among bases Y, X)，阻止拿衣服(naive)的Python程序员创建模棱两可的继承层次。Python 2.2不会抛出异常，而是选择了一种特定的方法解析顺序(CABXYO).

.   _                   .-=-.          .-==-.
   { }      __        .' O o '.       /  -<' )
   { }    .' O'.     / o .-. O \     /  .--v`
   { }   / .-. o\   /O  /   \  o\   /O /
    \ `-` /   \ O`-'o  /     \  O`-`o /
jgs  `-.-`     '.____.'       `.____.'

C3方法解析顺序(The C3 Method Resolution Order)

我先引入几个简单的符号以方便后续的讨论。我将使用：C1 C2 ... CN

来代表类列表：[C1, C2, ..., C3

该列表的head是它的第一个元素

head = C1

而列表的tail就是列表的余下部分：

tail = C2 ... CN.

使用表达式

C + (C1 C2 ... CN) = C C1 C2 ... CN

来表示多个列表的和： [C] + [C1, C2, ... ,CN]

现在，我可以解释下Python 2.3中MRO是如何工作的了。

假设在多继承层次中，类C继承自B1，B2，..., BN。 我们想计算类C的线性化L|C|，规则如下：C的线性化，是类C、C的各个父类线性化的合并、C的父类三个部分的求和(the linearization of C is the sum of C plus the merge of the linearizations of the parents and the list of the parents)

符号化表示：

L[C(B1 ... BN)] = C + merge(L[B1] ... L[BN], B1 ... BN)

特殊情况下， 如果C是object类，线性化就简单：

[object] = object.

通常情况下，需要按照下述方法来进行序列化列表的合并：

take the head of the first list, i.e L[B1][0]; 

取出第一个列表的head， 比如 L[B1][0]；

if this head is not in the tail of any of the other lists, 

如果这个head不在其它列表的tail中

then add it to the linearization of C and remove it from the lists in the merge, 

那就把这个head添加到C的线性化中并从所有的列表中删除它，

otherwise look at the head of the next list and take it, if it is a good head. 

否则，就查看下一个列表的head， 如果满足上面的条件的h话，就取它。

Then repeat the operation until all the class are removed or it is impossible to find good heads.

接着重复操作，直到所有的列表中的所有的类被删除完毕或者不可能再找到一个符合规则的head。

In this case, it is impossible to construct the merge,

在这种情况下，不可能构建合并。

Python 2.3 will refuse to create the class C and will raise an exception.

Python 2.3会拒绝创建类C并会抛出一个异常。

该方法保证：如果顺序能够被保留，合并操作会保留顺序。反过来说，如果顺序不能被保留，合并操作就不能进行。

如果类C只有一个父类，很容易合并：

L[C(B)] = C + merge(L[B],B) = C + L[B]

然而，在多继承层次中，处理起来会更复杂。我也不指望你在没几个例子的情况下，能够理解上面的规则。

.         .-'-.
        /'     `\
      /' _.-.-._ `\
     |  (|)   (|)  |
     |   \__"__/   |
     \    |v.v|    /
      \   | | |   /
       `\ |=^-| /'
         `|=-=|'
          | - |
          |=  |
          |-=-|
    _.-=-=|= -|=-=-._
   (      |___|      )
  ( `-=-=-=-=-=-=-=-` )
  (`-=-=-=-=-=-=-=-=-`)
  (`-=-=-=-=-=-=-=-=-`)
   (`-=-=-=-=-=-=-=-`)
    (`-=-=-=-=-=-=-`)
jgs  `-=-=-=-=-=-=-`

例子(Examples)

第一个例子，考虑下面的继承层次：

>>> 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

继承图如下：

.                        6
                         ---
Level 3                 | O |                  (more general)
                      /  ---  \
                     /    |    \                      |
                    /     |     \                     |
                   /      |      \                    |
                  ---    ---    ---                   |
Level 2        3 | D | 4| E |  | F | 5                |
                  ---    ---    ---                   |
                   \  \ _ /       |                   |
                    \    / \ _    |                   |
                     \  /      \  |                   |
                      ---      ---                    |
Level 1            1 | B |    | C | 2                 |
                      ---      ---                    |
                        \      /                      |
                         \    /                      \ /
                           ---
Level 0                 0 | A |                (more specialized)
                           ---

O、D、E、F的线性化很简单：

L[O] = O
L[D] = D O
L[E] = E O
L[F] = F O

B的线性化可以如下计算：

L[B] = B + merge(DO, EO, DE)

可以看到，D是个满足规则的head，所以将它取出，就简化为计算merge(O,EO,E).现在O不符合规则，因为它在EO的tail中。这种情况下，按照规则，我们要跳到下一个序列。接着我们看到，E符合规则；我们采用它， 并简化为计算merge(O,O)，所以：

L[B] = B D E O

即：

L[C] = C + merge(DO,FO,DF)
     = C + D + merge(O,FO,F)
     = C + D + F + merge(O,O)
     = C D F O

现在，我们可以计算：

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)
     = A + B + C + D + E + merge(O,FO)
     = A + B + C + D + E + F + merge(O,O)
     = A B C D E F O

在本例中，按照继承层次，线性化比较好地排序了， 有种“底层的父类具有较高的优先级”。但这只是个特例，而非一般情况。

我将下面的例子留给读者作为练习。

>>> O = object
>>> class F(O): pass
>>> class E(O): pass
>>> class D(O): pass
>>> class C(D,F): pass
>>> class B(E,D): pass
>>> class A(B,C): pass

这个例子和前一个例子的唯一区别是B(D,E) --> B(E,D)。但就是这一点小修改会完全改变整个层次的排序。

.                          6
                          ---
Level 3                  | O |
                       /  ---  \
                      /    |    \
                     /     |     \
                    /      |      \
                  ---     ---    ---
Level 2        2 | E | 4 | D |  | F | 5
                  ---     ---    ---
                   \      / \     /
                    \    /   \   /
                     \  /     \ /
                      ---     ---
Level 1            1 | B |   | C | 3
                      ---     ---
                       \       /
                        \     /
                          ---
Level 0                0 | A |
                          ---

要注意：(在线性化列表中)在level 2上的类E，在类C(尽管在Level 1)的前面。

偷懒的程序员可以直接从Python 2.2中获得MRO，因为这个例子中，Python 2.2的线性化和Python 2.3的线性化一致。调用类A的.mro()方法就够了：

>>> A.mro()
(<class '__main__.A'>, <class '__main__.B'>, <class '__main__.E'>,
<class '__main__.C'>, <class '__main__.D'>, <class '__main__.F'>,
<type 'object'>)

最后，再来考虑一下第一部分的例子，带来了严重的顺序不一致问题。这个例子中，能够直接得到O, X, Y, A， B的线性化：

L[O] = 0
L[X] = X O
L[Y] = Y O
L[A] = A X Y O
L[B] = B Y X O

但是却不可能计算C(A，B)的线性化，

L[C] = C + merge(AXYO, BYXO, AB)
     = C + A + merge(XYO, BYXO, B)
     = C + A + B + merge(XYO, YXO)

这时，我们不能合并列表XYO和列表YXO，因为X在YXO的tail中，而Y在XYO的tail中：因此，没有了符合规则的head，C3算法停止。 Python 2.3抛出异常、拒绝创建类C。

 .                    __
    (\   .-.   .-.   /_")
     \\_//^\\_//^\\_//
jgs   `"`   `"`   `"`

不好的方法解析顺序(Bad Method Resolution Orders)

当一个MRO不满足局部有限顺序、单调性之类的基本条件时，就认为是bad(翻译成'不好'挺怪)。在本节，我将举例证明旧式类的MRO、Python 2.2新式类的MRO是bad。

简单起见，先从局部优先顺序开始。看下面的这个例子：

>>> F=type('Food',(),{'remember2buy':'spam'})
>>> E=type('Eggs',(F,),{'remember2buy':'eggs'})
>>> G=type('GoodFood',(F,E),{}) # under Python 2.3 this is an error!

对应的继承图是：

.            O
             |
(buy spam)   F
             | \
             | E   (buy eggs)
             | /
             G

      (buy eggs or spam ?)

我们可以看到，G继承了F和E、F在E的前面；我们也期望G.remember2buy继承自F.rembermer2buy，而不是E.remember2buy，然而，Python 2.2给出的是：

>>> G.remember2buy
'eggs'

这就破坏了局部优先顺序，因为：局部优先列表的顺序，以G的继承链为例，并没有在Python 2.2的G的线性化中得到保留：

L[G,P22]= G E F object   # F *follows* E

有人会质疑说：在Python 2.2的线性化中，F之所以在E的后面，是因为F是E的父类，所以不像E那么具体。然后，破坏了局部优先顺序，是非常不直观、有错误倾向的做法。由于不同于旧式类，这种做法就尤其正确：

>>> class F: remember2buy='spam'
>>> class E(F): remember2buy='eggs'
>>> class G(F,E): pass
>>> G.remember2buy
'spam'

在这个例子中，MRO是GFEF, 局部优先顺序得到了保留。

一般来说，应该避免使用像前面例子的继承层次，因为它没有清晰表达是否重写了E。Python 2.3在创建类G的过程中，通过抛出异常解决了这种二义性，有效地阻止了程序员创建这种模棱两可的层次。之所以能抛出异常，是因为C3算法无法合并：

merge(FO,EFO,FE)

因为F在EFO的tai中、E又在FE的tail中。

真正的解决方案是创建一个无歧义的继承层次，比如让G继承E、F而不是F、E，此时， MRO无疑是GEF，

.          O
           |
           F (spam)
         / |
(eggs)   E |
         \ |
           G
             (eggs, no doubt)

Pytho 2.3强迫程序员书写正确的继承层次(至少没有错误倾向的层次)。

同样， 我要指出：Python 2.3的C3算法能够智能地识别出多种错误，如，父类列表中存在重复，

>>> class A(object): pass
>>> class C(A,A): pass # error
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
TypeError: duplicate base class A

(然而)在Python 2.2(无论是旧式类还是新式类)都不会抛出任何异常。

最后，我要总结下从这个例子中学到的两点：

1. 尽管名称是``method``， MRO还决定了属性的解析顺序，不仅仅是方法
2. Python开发者默认的食物就是spam(尽管你已经知道了).

.                     __
    (\   .-.   .-.   /_")
     \\_//^\\_//^\\_//
jgs   `"`   `"`   `"`

已经讨论过局部优先顺序了，接下来介绍一下单调性。我要说的是：无论是旧式类的MRO，还是Python2.2新式类的MRO，都不是单调的。

很容易证明，旧式类的MRO不是单调的，看下面的菱形图就知道：

.  C
  / \
 /   \
A     B
 \   /
  \ /
   D

很容易就看出不一致的地方：

L[B,P21] = B C        # B precedes C : B's methods win
L[D,P21] = D A C B C  # B follows C  : C's methods win!

而Python 2.2和Python 2.3给出了相同的答案：

L[D] = D A B C

Guido指出在他自己的文章[3]中，旧式类的MRO在实践中没那么糟糕，因为开发者可以避免这种菱形的继承；但是所有的新式类都继承自object，所以在多继承层次图中，菱形是不可避免的。

在Python 2.2中，虽然MRO很难破坏单调性，但不是不可能的。下面的例子就是由Samuele Pedroni提供的， 表明Python 2.2的MRO不是单调的，

>>> class A(object): pass
>>> class B(object): pass
>>> class C(object): pass
>>> class D(object): pass
>>> class E(object): pass
>>> class K1(A,B,C): pass
>>> class K2(D,B,E): pass
>>> class K3(D,A):   pass
>>> class Z(K1,K2,K3): pass

按照C3的MRO如下（读者应该自行验证一下线性化、画一画继承图）：

L[A] = A O
L[B] = B O
L[C] = C O
L[D] = D O
L[E] = E O
L[K1]= K1 A B C O
L[K2]= K2 D B E O
L[K3]= K3 D A O
L[Z] = Z K1 K2 K3 D A B C E O

Python 2.2能够准确给出A, B, C, D, E, K1, K2, K3这些类的线性化， 但是Z的就不对了：

L[Z,P22] = Z K1 K3 A K2 D B C E O

显然，这个线性化是错误的，因为A排在了D前面，但是在K3的线性化中，A是在D后面的。换言之，K3从D继承的方法会覆盖掉A的方法，但是在作为K3子类的类Z中，继承自A的方法覆盖了D的方法；这就违反了单调性。此外，Python2.2中，Z的线性化还违背了局部优先顺序，因为Z的局部优先列表是[K1, K2, K3] (K2在K3前)，但是Z的线性化中，K2在K3后面了。这些问题，解释了为啥2.2的规则违反了C3的规则。

.                                                        __
   (\   .-.   .-.   .-.   .-.   .-.   .-.   .-.   .-.   /_")
    \\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//
jgs  `"`   `"`   `"`   `"`   `"`   `"`   `"`   `"`   `"`

结束语(The end)

本节是给那些没有耐心、跳过前几节、直接来到本节的的读者准备的。本节也是给那些不想锻炼一下脑子、偷懒的程序员准备的。最后，本节是给那些傲慢的程序员准备的，不然， 他也不应该正在阅读一篇关于C3 MRO 的文章了;-)。集齐这三个美德可以召唤一个奖品了：一个简短的Python 2.2脚本，帮你计算Python 2.3的MRO，而不用费脑子；只要更改最后一行，就可以好好测试一下我在本文中提到的几个例子

#<mro.py>

"""C3 algorithm by Samuele Pedroni (with readability enhanced by me)."""

class __metaclass__(type):
    "All classes are metamagically modified to be nicely printed"
    __repr__ = lambda cls: cls.__name__

class ex_2:
    "Serious order disagreement" #From Guido
    class O: pass
    class X(O): pass
    class Y(O): pass
    class A(X,Y): pass
    class B(Y,X): pass
    try:
        class Z(A,B): pass #creates Z(A,B) in Python 2.2
    except TypeError:
        pass # Z(A,B) cannot be created in Python 2.3

class ex_5:
    "My first example"
    class O: pass
    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

class ex_6:
    "My second example"
    class O: pass
    class F(O): pass
    class E(O): pass
    class D(O): pass
    class C(D,F): pass
    class B(E,D): pass
    class A(B,C): pass

class ex_9:
    "Difference between Python 2.2 MRO and C3" #From Samuele
    class O: pass
    class A(O): pass
    class B(O): pass
    class C(O): pass
    class D(O): pass
    class E(O): pass
    class K1(A,B,C): pass
    class K2(D,B,E): pass
    class K3(D,A): pass
    class Z(K1,K2,K3): pass

def merge(seqs):
    print '\n\nCPL[%s]=%s' % (seqs[0][0],seqs),
    res = []; i=0
    while 1:
      nonemptyseqs=[seq for seq in seqs if seq]
      if not nonemptyseqs: return res
      i+=1; print '\n',i,'round: candidates...',
      for seq in nonemptyseqs: # find merge candidates among seq heads
          cand = seq[0]; print ' ',cand,
          nothead=[s for s in nonemptyseqs if cand in s[1:]]
          if nothead: cand=None #reject candidate
          else: break
      if not cand: raise "Inconsistent hierarchy"
      res.append(cand)
      for seq in nonemptyseqs: # remove cand
          if seq[0] == cand: del seq[0]

def mro(C):
    "Compute the class precedence list (mro) according to C3"
    return merge([[C]]+map(mro,C.__bases__)+[list(C.__bases__)])

def print_mro(C):
    print '\nMRO[%s]=%s' % (C,mro(C))
    print '\nP22 MRO[%s]=%s' % (C,C.mro())

print_mro(ex_9.Z)

#</mro.py>

.   __
   ("_\   .-.   .-.   .-.   .-.   .-.   .-.   .-.   .-.   /)
      \\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//
jgs    `"`   `"`   `"`   `"`   `"`   `"`   `"`   `"`   `"`

资源(Resources)

[1] The thread on python-dev started by Samuele Pedroni: http://mail.python.org/pipermail/python-dev/2002-October/029035.html

[2] The paper A Monotonic Superclass Linearization for Dylan: http://www.webcom.com/haahr/dylan/linearization-oopsla96.html

[3] Guido van Rossum's essay, Unifying types and classes in Python 2.2: http://www.python.org/2.2.2/descrintro.html

本文来自网易实践者社区，经作者王一兵权发布。