Python 2.3 方法解析顺序
| 摘要 | 本文档面向想要理解 Python 2.3 中使用的 C3 方法解析顺序 (MRO) 的 Python 程序员。尽管它并非为新手编写，但其中包含许多示例，具有很强的教学性。我没有发现其他公开的范围相同的文档，因此它应该会有用。 |
|---|
免责声明
我根据 Python 2.3 许可证将本文档捐赠给 Python 软件基金会。像在这种情况下通常一样，我提醒读者，以下内容“应该”是正确的，但我对此不作任何保证。使用风险自负！
致谢
感谢 Python 邮件列表中所有支持我的人。Paul Foley 指出了各种不准确之处，并让我添加了关于局部优先级排序的部分。感谢 David Goodger 帮助我用 reStructuredText 格式化。感谢 David Mertz 帮助编辑。感谢 Joan G. Stark 提供了 Pythonic 图片。最后，感谢 Guido van Rossum 热情地将本文档添加到 Python 2.3 官方主页。
.-=-. .--.
__ .' '. / " )
_ .' '. / .-. \ / .-'\
( \ / .-. \ / / \ \ / / ^
\ `-` / \ `-' / \ `-` /
jgs`-.-` '.____.' `.____.'
开端
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 算法，并且可以轻松跳过本文。另一方面，如果您真的想知道多重继承是如何工作的，那么本文适合您。好消息是事情并不像您想象的那么复杂。
让我从一些基本定义开始。
- 给定一个复杂多重继承层次结构中的类 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 表示对象类，它是新式类的任何层次结构的起点
-----------
| |
| 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）。
_ .-=-. .-==-.
{ } __ .' O o '. / -<' )
{ } .' O'. / o .-. O \ / .--v`
{ } / .-. o\ /O / \ o\ /O /
\ `-` / \ O`-'o / \ O`-`o /
jgs `-.-` '.____.' `.____.'
C3 方法解析顺序
让我介绍一些简单的符号，它们对后续讨论很有用。我将使用快捷符号
C1 C2 ... CN
表示类列表 [C1, C2, ... , CN]。
列表的“头”是它的第一个元素
头 = C1
而“尾”是列表的其余部分
尾 = 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 是对象类，它没有父类，线性化是简单的
L[object] = object。
然而，通常需要根据以下规定计算合并：
取第一个列表的头，即 L[B1][0]；如果此头不在任何其他列表的尾部，则将其添加到 C 的线性化中，并从合并中的列表中移除它，否则查看下一个列表的头，如果它是一个好的头，则取它。然后重复操作，直到所有类都被移除，或者无法找到好的头。在这种情况下，无法构建合并，Python 2.3 将拒绝创建类 C 并引发异常。
此规定确保合并操作“保留”排序，如果排序可以保留的话。另一方面，如果无法保留排序（如上述讨论的严重排序分歧示例），则无法计算合并。
如果 C 只有一个父类（单继承），合并的计算是简单的；在这种情况下
L[C(B)] = C + merge(L[B],B) = C + L[B]
然而，在多重继承的情况下，事情就更繁琐了，我期望您没有几个例子就无法理解规则 ;-)
.-'-.
/' `\
/' _.-.-._ `\
| (|) (|) |
| \__"__/ |
\ |v.v| /
\ | | | /
`\ |=^-| /'
`|=-=|'
| - |
|= |
|-=-|
_.-=-=|= -|=-=-._
( |___| )
( `-=-=-=-=-=-=-=-` )
(`-=-=-=-=-=-=-=-=-`)
(`-=-=-=-=-=-=-=-=-`)
(`-=-=-=-=-=-=-=-`)
(`-=-=-=-=-=-=-`)
jgs `-=-=-=-=-=-=-`
示例
第一个例子。考虑以下层次结构
>>> 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 是一个好的头部，因此我们选择它，然后我们只需要计算合并 (O, EO, E). 现在 O 不是一个好的头部，因为它在序列 EO 的尾部。在这种情况下，规则规定我们必须跳到下一个序列。然后我们看到 E 是一个好的头部；我们选择它，然后我们只需要计算合并 (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 '__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
然而，对于继承自 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。
__
(\ .-. .-. /_")
\\_//^\\_//^\\_//
jgs `"` `"` `"`
错误的方法解析顺序
当 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.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 时引发异常来解决这种歧义，从而有效地阻止程序员生成模糊的层次结构。原因是 C3 算法在合并时失败
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（经典类和新式类）在这种情况下都不会引发任何异常。
最后，我想指出我们从这个例子中学到的两点教训
- 尽管有名称，但 MRO 决定的是属性的解析顺序，而不仅仅是方法的解析顺序；
- Python 程序员的默认食物是 spam！（但你已经知道了 ;-)
__
(\ .-. .-. /_")
\\_//^\\_//^\\_//
jgs `"` `"` `"`
讨论了局部优先级排序问题之后，现在让我考虑单调性问题。我的目标是证明经典类的 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 在实践中并没有那么糟糕，因为对于经典类，通常可以避免菱形结构。但是所有新式类都继承自对象，因此菱形是不可避免的，不一致性会出现在每个多重继承图中。
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 规则取代。
__
(\ .-. .-. .-. .-. .-. .-. .-. .-. /_")
\\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//
jgs `"` `"` `"` `"` `"` `"` `"` `"` `"`
结束
本节面向不耐烦的读者，他们跳过了所有前面的章节，直接跳到末尾。本节也面向懒惰的程序员，他们不想锻炼大脑。最后，它也面向有些傲慢的程序员，否则他/她就不会阅读关于多重继承层次结构中 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>
就这些，各位，
尽情享受吧！
__
("_\ .-. .-. .-. .-. .-. .-. .-. .-. /)
\\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//
jgs `"` `"` `"` `"` `"` `"` `"` `"` `"`
资源
| [1] | Samuele Pedroni 在 python-dev 上发起的帖子：http://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://pythonlang.cn/2.2.2/descrintro.html |