Python 2.3 方法解析顺序

注意

这是一份历史文档,作为官方文档的附录提供。这里讨论的方法解析顺序是在 Python 2.3 中引入的,但它在后来的版本中仍然使用 - 包括 Python 3。

作者:Michele Simionato.

摘要:

本文档面向希望了解 Python 2.3 中使用的 C3 方法解析顺序的 Python 程序员。虽然它不适合新手,但它非常具有教学意义,并包含许多实例。据我所知,没有其他公开的文档具有相同的范围,因此它应该很有用。

免责声明

我将这份文档捐赠给 Python 软件基金会,根据 Python 2.3 许可证。在这些情况下,我通常会提醒读者,以下内容应该是正确的,但我不会提供任何保证。使用它需要您自担风险!

致谢

感谢所有在 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]。本文档对 Pythonistas 来说是一份(希望)易于理解的 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 不会抛出异常,而是选择一个 *特定* 的排序(在本例中为 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] 的总和。

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

考虑一个类 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,即 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 违反诸如局部优先级排序和单调性等基本属性时,它就是错误的。在本节中,我将展示 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.remember2buyF.rembermer2buy 继承,而不是由 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)

无法计算时,C3 算法失败,因为 F 位于 EFO 的尾部,而 E 位于 FE 的尾部。

真正的解决方案是设计一个非歧义的层次结构,即从 E 和 F(更具体的优先)而不是从 F 和 E 派生 G;在这种情况下,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. Pythonistas 的默认食物是垃圾邮件!(但你已经知道了 ;-)

讨论了局部优先级排序问题后,现在让我考虑一下单调性问题。我的目标是证明经典类的 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>

就这样吧,

享受!

资源