python2.3方法解析顺序(译)
——详解多继承的C3算法(C3 Method Resolution Order)

不少语言支持多继承,比如python。多继承?似乎很简单嘛!但仔细想想,真的是这样吗?创建一个类时,如果继承的层级比较深,继承图中的每个节点都可能有一个或多个直接父类,那么这个新创建的类该从按照什么顺序继承父类和祖先类的属性和方法?这个问题远没有想象的简单。最近研究dojo源码,发现dojo模拟了多继承,其方法解析顺序参照了python中的C3算法。谷歌了好久,发现这方面的中文参考资料很少,绝望之下,索性翻译了这篇来自python官方的文档。该文档深入介绍了多继承时的C3方法解析顺序,解释了“局部优先级”和“单调性”两条重要原则,并且有丰富的例子。希望各位看官喜欢。

摘要

这份文档是为想要理解python2.3中的C3方法解析顺序(C3 Method Resolution Order)的程序员们准备的。虽然本文不是针对初学者的,但它提供了很多范例,方便学习。我并不知晓其他公开发表并与本文主题一致的文档,因此本文应该是有用的。

免责声明

我把本文档捐赠给了python软件基金会,基于python2.3的授权许可。按照这种情境的惯例,我提醒读者,本文的内容应当是正确无误的,但我不会给出任何担保。使用本文请自负风险!

鸣谢

感谢通过邮件给与我支持的所有朋友。感谢Paul Foley指出了本文多处不严谨的地方,并且让我添加了关于局部优先级的有关内容。感谢David Goodge帮我重新编排本文时制定了格式。感谢David Mertz对本文的编辑。感谢Joan G. Stark制作的蟒蛇图案(译者注:原文中配有各种奇葩的像蛇一样图案,不知道作者配这些图案是发了哪门子神经,这些图案影响文章的可读性,去掉也无关宏旨,所以本译文统统将其省去了。好奇心重的读者可以自行查看原文)。最后,感谢Guido van Rossum热情地将本文添加到了python2.3的官方首页。

开场白

幸福就是人能够了解万物的起因——维吉尔

一切缘起于Samuele Pedroni在python开发邮件列表中发表的一个帖子。在该贴子中,Asmuele指出python2.2的方法解析顺序不符合单调性原则,他提议用C3方法解析顺序作为替代方案。Guido同意了他的观点,所以现在的python2.3使用的是C3。C3方法本身与python风马牛不相及,因为它是由致力于dylan(译者注:一种是由Apple公司发布的一个类似Scheme的面向对象语言,以Dylan Thomas命名)的人们发明的,在一篇针对lisp编程者的论文(译者注:该论文的链接已经失效,译者google了N久,没找到这篇论文,读者如果有该论文的原件,还请不吝分享)中被详加解释。本论文提供了一份颇具可读性的关于C3算法的探讨(我希望如此),以期给希望理解这种变化的python程序员提供帮助。

首先我要指出,我即将论述的内容仅仅针对python2.2中引入的新式类:经典类通过广度优先、从左到右的方式来确定方法解析顺序。因此,老代码中的经典类并不会被破坏;并且即便从原则上说,python2.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是单调的,可以表述为:C的线性化中,假如C1优先于C2,那么在C的任何子类的线性化中,C1优先于C2。在不满足单调性的情况下,创建一个子类这种很寻常的操作,都会改变方法的解析顺序,潜在地引入诡异的bug。发生这种情况的例子将在下文呈现。
  6. 不是所有的类都能实现线性化。在某些情况下,复杂的层级架构无法派生一个其线性化能满足所有要求的子类。

这里我给出一个这种情形的例子。考虑下面的层级:

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

可以用下面的继承图来表示上述层级,图中我用O来表示object类,它位于任何用来派生新类的层级结构的顶端。

着这种情境下,从A和B中派生新的类C是不可能的,因为在A中X优先于Y,但在B中Y优先于A,因此C的方法解析顺序是模棱两可的。

python2.3在这种情况下会报错(TypeError:MRO conflict among bases Y,X)阻止稚嫩的程序员来创建模棱两可的继承结构。而python2.2则不会报错,而是选择了一种特别的顺序(这个例子中是CABXYO)。

C3方法解析顺序

我会引入一些对后面讨论很有用的简单的记号。我将使用简写记号:

C1C2C3…CN

来表征类列表[C1, C2, C3…, CN]。

类表的头(head是它的第一个元素:

head = C1

而其尾(tail则是列表的剩余部分:

tail = C2C3…CN

我还会使用如下标记:

C + (C1C2C3…CN) = CC1C2C3…CN

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

现在我能够解释MRO在python2.3中是如何工作的了。

考虑一个复杂继承层级中的类C,C继承自基类B1, B2, B3, … , BN。我们想要计算C的线性化L(C)。规则如下:

C的线性化是C加上其父类线性化的合并(merge)以及其父类列表的和。

用符号表示如下:

L[C(B1B2…BN)] = C + merge(L(B1)L(B2)…L(BN), B1B2…BN)

特别地,如果C是object类,该类没有任何父类,则其线性化很简单:

L(object) = object

然而,一般情况下,必须根据下面的规则实施合并(merge)操作:

取出第一个列表的头,也就是L[B1][0];如果该头不在其他列表的尾中,那么将该头添加到C的线性化中,并将其从merge操作的所有列表中删除,否则查看下一个列表的头并操作它,加入它符合要求。然后,重复该操作直到所有的类都被删掉或者无法再找到符合要求的头。在这种情况下,合并操作(merge)无法进行下去,python2.3将会拒绝创建类C并抛出一个错误。

这个规则确保了合并操作(merge)能够保存特定顺序,当然前提是该顺序是可被保存的。(译者注:这句话理解起来比较烧脑,读者可以好好思考一下“保存”二字,或者参看译者的理解)。另一方面,如果该顺序不能被保存(就像在前面讨论过的严重顺序分歧一样),合并操作(merge)不能被计算完成。

如果C只有一个父类(单继承情况),合并操作(merge)的计算十分简单;这个例子中

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

这个例子的继承图可以画为:

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(0, EO, E)。现在O这个头不合乎要求,因为它在序列EO的尾中。这种情况下,规则要求我们跳转到下一个序列。然后我们发现E是一个合乎条件的头;我们取出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 + merge(O, FO)

= A + B + C + D + 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);然而即便是如此微小的修改,也彻底改变了层级的顺序。

注意一下类E,它处于继承的第二级上,优先于处于继承第一级的C,也就是说,E比C更加特化,尽管它处于更高的级别。

爱偷懒的程序员,可以直接从python2.2中获取MRO,因为这种境况下它与python2.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和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算法终止了。python2.3抛出了一个错误,拒绝创建类C。

糟糕的方法解析顺序

如果一个MRO破坏了局部优先级单调性这样的基本特性,那么它就是糟糕的。在这一小节中,我将会说明,在不管是传统类,还是python2.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!

图示如下:

我们看到类G继承了F和E,F更靠前:所以我们期望G.remember2buy从F.remenber2buy中而不是从E.remember2buy继承而来。然而python2.2中会得到:

>>> G.remember2buy
'eggs'

这样就打破了局部优先级,因为局部优先列表,也就是G的父类列表,在python2.2中G的线性化中没有被保存:

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

有人可能会争论,python2.2的线性化中,F位于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还是反过来才好。python2.3通过在创建类G的时候抛出错误,来解决这种模棱两可的困境,这样可以有效地阻止程序员写出模糊不清的层级结构来。之所以会这样的原因,在于C3算法会在执行如下合并操作的时候失败:

merge(FO, EFO, FE)

无法计算的原因是F在EFO的尾中,而E在FE的尾中。

真正的解决办法是避免创建模棱两可的层级机构,也就是从E和F中派生G(更具体的类靠前),而不是从F和E中派生;这样一来MRO就是GEF,没有半点争议。

python2.3强制程序员书写良好的继承结构(或者至少是不容易出错的写法)。

我还要指出一个相关的注意事项,那就是python2.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

python2.2中(不论是老式类还是新类),在这种情况下不会报任何错误。

最后,我将要指出我们从这个例子中学到的两点:

1、虽然名称易招致误解,但MRO决定的是所有属性的解析顺序,不仅仅是方法;

2、对python编码人员,默认的食物是猪肉罐头!(但你已经知道啦;-))

讨论完了局部优先级的问题,接着考虑单调性的问题。我的目标是说明无论老式类,还是python2.2中的新式类,都不是单调的。

证明老式类的MRO是非单调的很容易,只要看看下面的菱形问题就是足够了:

你可以很容易地发现其中的不一致:

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!

另一方面,python2.2和2.3的MRO中没有问题,它们都返回:

L[D] = A A B C

Guido在他的随笔中指出,老式类的MRO在实践中并不是非常糟糕,因为大家一般可以在老式类中避免菱形问题。但是所有的新式类都继承自object,因此菱形问题不可避免,在每个多继承中都会出现这种冲突。

python2.2的MRO使得打破单调性变得困难了,但并非不可能。下面的例子最初是由Asmuele Pedroni提供的,显示了python2.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

这里是根据C3MRO(读者当做一个练习,来应该验证这些线性化,并且画出继承图;-))

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

python2.2对于A, B, C, D, E, K1, K2 和 K给出了一致的线性化结果,但对于Z则有所不同:

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

很明显这个结果是错误的,因为在A跑到了D的前面,但是在K3的线性化中A却是在D的后面。换句话说,在K3中,从D继承来的方法覆盖了从A继承来的,但在Z中,虽然Z还是K3的子类,但A继承来的方法覆盖了从D继承来的!这是对单调性原则的违犯。而且,python2.2中Z的线性化也与局部优先级不一致,因为类Z的局部优先顺序列表是[K1, K2, K3](K2优先于K3),而在Z的线性化中,K2跑到了K3的后面。这些问题解释了为什么2.2中的规则被摒弃而选择了C3规则。

结语

这一小节是针对不耐烦的读者的,他们跳过了前面的所有小节直接来到了结尾。这个小节也是为懒惰的程序员准备的,他们不想活动他/她的大脑。最后,本小节也适用于有点傲慢的程序员,否则他/她也不会阅读一篇关于多继承层级结构中C3方法解析顺序的的论文;-)。这三种节操凑到一起(而不是单独地),值得一个奖励:奖励就是一段简短的python2.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>

就这样结束了,伙计们!

希望大家喜欢!

本文原英文地址:https://www.python.org/download/releases/2.3/mro/