Python 2.3 方法解析顺序¶
注意
这是一份历史文档，作为官方文档的附录提供。这里讨论的方法解析顺序是在 Python 2.3 中引入的，但它仍然在更高版本中使用——包括 Python 3。
- 摘要:
本文档面向希望理解 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 – Virgilius
一切都始于 Samuele Pedroni 在 Python 开发邮件列表中发布的一篇文章 [1]。在他的帖子中，Samuele 表明 Python 2.2 方法解析顺序不是单调的，他建议用 C3 方法解析顺序代替它。Guido 同意他的观点，因此现在 Python 2.3 使用 C3。C3 方法本身与 Python 无关，因为它是由研究 Dylan 的人发明的，并且在为 lispers 准备的论文中进行了描述 [2]。本文为希望了解更改原因的 Pythonistas 提供了 C3 算法（希望）可读的讨论。
首先，请允许我指出，我接下来要说的仅适用于 Python 2.2 中引入的新式类：经典类保持其旧的方法解析顺序，深度优先然后从左到右。因此，对于经典类，不会破坏旧代码；即使原则上可能会破坏 Python 2.2 新式类的代码，但在实践中，C3 解析顺序与 Python 2.2 方法解析顺序不同的情况非常罕见，因此预计不会真正破坏代码。所以
不要害怕！
此外，除非你大量使用多重继承并且具有非平凡的层次结构，否则你不需要理解 C3 算法，你可以轻松跳过本文。另一方面，如果你真的想了解多重继承的工作原理，那么本文适合你。好消息是，事情并不像你想象的那么复杂。
让我从一些基本定义开始。
给定一个复杂的多重继承层次结构中的类 C，指定重写方法的顺序，即指定 C 的祖先的顺序，是一项非平凡的任务。
类 C 的祖先列表，包括类本身，从最近的祖先到最远的祖先排序，称为类优先级列表或 C 的线性化。
方法解析顺序 (MRO) 是一组构建线性化的规则。在 Python 文献中，习惯用法“C 的 MRO”也用作类 C 的线性化的同义词。
例如，在单继承层次结构的情况下，如果 C 是 C1 的子类，而 C1 是 C2 的子类，则 C 的线性化就是列表 [C, C1, C2]。然而，对于多重继承层次结构，线性化的构建更加繁琐，因为它更难以构建尊重局部优先级排序和单调性的线性化。
我将在稍后讨论局部优先级排序，但我可以在这里给出单调性的定义。当以下情况为真时，MRO 是单调的：如果 C1 在 C 的线性化中先于 C2，则 C1 在 C 的任何子类的线性化中先于 C2。否则，派生新类的无害操作可能会更改方法的解析顺序，从而可能引入非常细微的错误。稍后将显示发生这种情况的示例。
并非所有类都允许线性化。在复杂的层次结构中，在某些情况下，无法派生一个类，使其线性化尊重所有期望的属性。
在这里，我给出一个这种情况的例子。考虑层次结构
>>> 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。
错误的 Method Resolution Order（方法解析顺序）¶
当 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.rembermer2buy 继承，而不是被 E.remember2buy 继承：然而 Python 2.2 给出了
>>> G.remember2buy
'eggs'
这是对局部优先级排序的破坏，因为局部优先级列表（即 G 的父类列表）中的顺序没有在 G 的 Python 2.2 线性化中保留。
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 时引发异常来解决歧义，有效地阻止程序员生成有歧义的层次结构。原因是 C3 算法在合并时失败
merge(FO,EFO,FE)
无法计算，因为 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（对于经典类和新式类）不会引发任何异常。
最后，我想指出我们从这个例子中吸取的两个教训
尽管名称如此，MRO 决定了属性的解析顺序，而不仅仅是方法；
Python 爱好者的默认食物是 spam！ （但你已经知道了 ;-)
在讨论了局部优先级排序的问题之后，现在让我考虑单调性的问题。我的目标是证明经典类的 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 派生的方法！这违反了单调性。此外，Z 的 Python 2.2 线性化也与局部优先级排序不一致，因为类 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>
就这些了，伙计们，
尽情享受！