Python 2.3 方法解析顺序

备注

这是一份历史文档，作为官方文档的附录提供。这里讨论的方法解析顺序是 Python 2.3 中“引入”的，但它仍在更高版本中使用——包括 Python 3。

作者：Michele Simionato。

摘要:

本文档旨在帮助希望理解 Python 2.3 中使用的 C3 方法解析顺序的 Python 程序员。尽管它不适合新手，但它具有很强的教学性，包含许多已解决的示例。我不知道有其他公开可用的具有相同范围的文档，因此它应该会有用。

免责声明

我根据 Python 2.3 许可证将本文档捐赠给 Python 软件基金会。像在这种情况下一样，我提醒读者，以下内容应该是正确的，但我不做任何保证。使用风险自负！

致谢

所有在 Python 邮件列表中向我提供支持的人。Paul Foley 指出了各种不准确之处，并促使我添加了关于局部优先顺序的部分。David Goodger 帮助我进行了 reStructuredText 格式化。David Mertz 帮助我进行了编辑。最后，Guido van Rossum 热情地将本文档添加到了官方 Python 2.3 主页。

开篇

Felix qui potuit rerum cognoscere causas – 维吉尔

一切都始于 Samuele Pedroni 在 Python 开发邮件列表上的帖子[1]。在他的帖子中，Samuele 表明 Python 2.2 方法解析顺序不是单调的，他建议用 C3 方法解析顺序替换它。Guido 同意他的论点，因此现在 Python 2.3 使用 C3。C3 方法本身与 Python 无关，因为它是由开发 Dylan 的人发明的，并且在一篇为 Lisp 程序员准备的论文中有所描述[2]。本文为希望理解此更改原因的 Python 程序员提供了对 C3 算法的（希望是）易懂的讨论。

首先，让我指出，我将要说的只适用于 Python 2.2 中引入的“新式类”：“经典类”保留了它们旧的方法解析顺序，即深度优先，然后从左到右。因此，对于经典类，没有旧代码的中断；即使原则上 Python 2.2 新式类的代码可能会中断，但在实践中，C3 解析顺序与 Python 2.2 方法解析顺序不同的情况非常罕见，因此预计不会有实际的代码中断。因此

不要害怕！

此外，除非您大量使用多重继承并且拥有非平凡的层次结构，否则您不需要理解 C3 算法，并且可以轻松跳过本文。另一方面，如果您真的想知道多重继承是如何工作的，那么本文适合您。好消息是，事情并没有您想象的那么复杂。

让我从一些基本定义开始。

1. 给定一个复杂的多重继承层次结构中的类 C，指定方法被覆盖的顺序，即指定 C 的祖先的顺序，是一项非平凡的任务。

2. 一个类 C 的祖先列表，包括类本身，从最近的祖先到最远的祖先排序，称为类优先列表或 C 的“线性化”。

3. “方法解析顺序”（MRO）是构建线性化的规则集合。在 Python 文献中，“C 的 MRO”的说法也用作类 C 的线性化的同义词。

4. 例如，在单继承层次结构中，如果 C 是 C1 的子类，C1 是 C2 的子类，那么 C 的线性化就是简单的列表 [C, C1, C2]。然而，在多重继承层次结构中，线性化的构建更为繁琐，因为更难构建一个尊重“局部优先顺序”和“单调性”的线性化。

5. 我稍后将讨论局部优先顺序，但我可以在这里给出单调性的定义。当以下情况为真时，MRO 是单调的：如果 C1 在 C 的线性化中先于 C2，那么 C1 在 C 的任何子类的线性化中都先于 C2。否则，派生新类的无害操作可能会改变方法的解析顺序，从而可能引入非常微妙的错误。稍后将展示发生这种情况的示例。

6. 并非所有类都允许线性化。在复杂的层次结构中，存在无法派生一个类，使其线性化尊重所有所需属性的情况。

我在这里给出这种情况的一个例子。考虑层次结构

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

这可以用以下继承图表示，其中我用 O 表示 object 类，它是任何新式类层次结构的起点

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

在这种情况下，无法从 A 和 B 派生新类 C，因为 X 在 A 中先于 Y，但 Y 在 B 中先于 X，因此 C 中的方法解析顺序将是模糊的。

Python 2.3 在这种情况下会引发异常（TypeError: MRO conflict among bases Y, X），阻止新手程序员创建模糊的层次结构。而 Python 2.2 则不会引发异常，而是选择一种“ad hoc”顺序（本例中为 CABXYO）。

C3 方法解析顺序

让我介绍一些简单的符号，它们对下面的讨论会很有用。我将使用以下简写符号

C1 C2 ... CN

表示类列表 [C1, C2, … , CN]。

列表的“头部”是它的第一个元素

head = C1

而“尾部”是列表的其余部分

tail = C2 ... CN.

我还会使用以下符号

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

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

现在我可以解释 Python 2.3 中 MRO 的工作原理了。

考虑一个多重继承层次结构中的类 C，其中 C 继承自基类 B1, B2, …, BN。我们想计算类 C 的线性化 L[C]。规则如下

C 的线性化是 C 加上父类线性化和父类列表的合并。

用符号表示为

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

特别地，如果 C 是 object 类，它没有父类，那么线性化是微不足道的

L[object] = object.

然而，通常需要根据以下规定计算合并

取第一个列表的头部，即 L[B1][0]；如果这个头部不在任何其他列表的尾部中，则将其添加到 C 的线性化中，并从合并中的列表中删除它，否则查看下一个列表的头部，如果它是一个好的头部，则取它。然后重复操作，直到所有类都被删除或者无法找到好的头部。在这种情况下，无法构建合并，Python 2.3 将拒绝创建类 C 并引发异常。

如果可以保留排序，此规定确保合并操作“保留”排序。另一方面，如果无法保留排序（如上文讨论的严重排序分歧示例），则无法计算合并。

如果 C 只有一个父类（单继承），合并计算是微不足道的；在这种情况下

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

然而，在多重继承的情况下，事情更加繁琐，我预计没有几个例子您无法理解这条规则 ;-)

示例

第一个例子。考虑以下层次结构

>>> 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 是一个好的头部，因此我们取它，我们被简化为计算 merge(O,EO,E)。现在 O 不是一个好的头部，因为它在序列 EO 的尾部。在这种情况下，规则规定我们必须跳到下一个序列。然后我们看到 E 是一个好的头部；我们取它，我们被简化为计算 merge(O,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 |
                          ---

请注意，类 E 位于层次结构的第二层，它优先于类 C，而类 C 位于层次结构的第一层，即 E 比 C 更专业，即使它位于更高的层级。

一个懒惰的程序员可以直接从 Python 2.2 获得 MRO，因为在这种情况下，它与 Python 2.3 的线性化一致。只需调用类 A 的 mro() 方法即可

>>> A.mro()
[<class 'A'>, <class 'B'>, <class 'E'>,
<class 'C'>, <class 'D'>, <class 'F'>,
<class '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

然而，对于继承自 A 和 B 的类 C，无法计算其线性化

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

此时，我们无法合并列表 XYO 和 YXO，因为 X 在 YXO 的尾部，而 Y 在 XYO 的尾部：因此没有好的头部，C3 算法停止。Python 2.3 会引发错误并拒绝创建类 C。

糟糕的方法解析顺序

当 MRO 破坏了局部优先顺序和单调性等基本属性时，它就是“糟糕”的。在本节中，我将展示经典类的 MRO 和 Python 2.2 新式类的 MRO 都是糟糕的。

从局部优先顺序开始更容易。考虑以下示例

>>> 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.remember2buy 而不是 E.remember2buy：然而 Python 2.2 给出

>>> G.remember2buy
'eggs'

这是对局部优先顺序的破坏，因为局部优先列表（即 G 的父类列表）中的顺序在 Python 2.2 的 G 的线性化中没有得到保留

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

有人可能会争辩说，F 在 Python 2.2 线性化中排在 E 之后的原因是 F 比 E 不那么专业，因为 F 是 E 的超类；然而，局部优先顺序的破坏非常不直观且容易出错。这尤其真实，因为它与旧式类不同

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

在这种情况下，MRO 是 GFEF，并且局部优先顺序得到保留。

一般来说，应避免像前面那样的层次结构，因为 F 应该覆盖 E 还是反之亦然，这是不清楚的。Python 2.3 通过在创建类 G 时引发异常来解决歧义，从而有效地阻止程序员生成歧义层次结构。原因是当合并操作

merge(FO,EFO,FE)

无法计算时，因为 F 在 EFO 的尾部，而 E 在 FE 的尾部。

真正的解决方案是设计一个非歧义的层次结构，即从 E 和 F 派生 G（更具体的在前），而不是从 F 和 E 派生；在这种情况下，MRO 毫无疑问是 GEF。

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

Python 2.3 强制程序员编写好的（或者至少是更不容易出错的）层次结构。

值得一提的是，Python 2.3 算法足够智能，可以识别明显的错误，例如在父类列表中重复的类

>>> 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. 尽管名称如此，MRO 决定了属性（不仅仅是方法）的解析顺序；

2. Python 程序员的默认食物是垃圾邮件！(但你已经知道了 ;-)

讨论了局部优先顺序的问题后，现在让我考虑单调性问题。我的目标是证明经典类的 MRO 和 Python 2.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 和 2.3 的 MRO 没有问题，它们都给出

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 派生的方法，但在 Z 中（它仍然是 K3 的子类），A 派生的方法覆盖 D 派生的方法！这违反了单调性。此外，Python 2.2 的 Z 线性化也与局部优先顺序不一致，因为类 Z 的局部优先列表是 [K1, K2, K3] (K2 在 K3 之前)，而在 Z 的线性化中 K2“跟随”K3。这些问题解释了为什么 2.2 规则被 C3 规则取代。

结尾

本节适用于不耐烦的读者，他们跳过了前面所有章节，直接跳到了结尾。本节也适用于懒惰的程序员，他们不想锻炼自己的大脑。最后，它适用于有点傲慢的程序员，否则他/她就不会阅读一篇关于多重继承层次结构中 C3 方法解析顺序的论文了 ;-) 这三种美德合在一起（而不是单独）值得一个奖品：这个奖品是一个简短的 Python 2.2 脚本，它允许您在不损伤大脑的情况下计算 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>

各位，就这些了，

祝您愉快！

资源

[1]

Samuele Pedroni 在 python-dev 上开启的讨论串：https://mail.python.org/pipermail/python-dev/2002-October/029035.html

[2]

论文 A Monotonic Superclass Linearization for Dylan：https://doi.org/10.1145/236337.236343

[3]

Guido van Rossum 的文章，Unifying types and classes in Python 2.2：https://web.archive.org/web/20140210194412/https://pythonlang.cn/download/releases/2.2.2/descrintro