Python 2.3 方法解析順序¶
備註
這是一份歷史文件，作為官方文件的附錄提供。這裡討論的方法解析順序是 Python 2.3 中“引入”的，但它仍在更高版本中使用——包括 Python 3。
- 摘要:
本文件旨在幫助希望理解 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 演算法，並且可以輕鬆跳過本文。另一方面，如果您真的想知道多重繼承是如何工作的，那麼本文適合您。好訊息是，事情並沒有您想象的那麼複雜。
讓我從一些基本定義開始。
給定一個複雜的多重繼承層次結構中的類 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 則不會引發異常，而是選擇一種“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（無論是經典類還是新式類）在這種情況下都不會引發任何異常。
最後，我想指出我們從這個例子中學到的兩點教訓
儘管名稱如此，MRO 決定了屬性（不僅僅是方法）的解析順序；
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>
各位，就這些了，
祝您愉快！