Python 2.3 方法解析順序¶
備註
這是一份歷史文件，作為正式文件的附錄提供。此處討論的方法解析順序 (Method Resolution Order) 是在 Python 2.3 中 引入 的，但仍在後續版本中使用，包括 Python 3。
- 摘要:
此文件適用於想要了解 Python 2.3 中使用的 C3 方法解析順序的 Python 程式設計師。雖然它不是為初學者準備的，但透過許多實際範例進行教學。我沒找到其他具有相同範圍的公開文件，因此這應該很有用。
免責聲明：
我根據 Python 2.3 授權條款將此文件捐贈給 Python 軟體基金會。如同往常，我警告讀者，以下內容 *應該 是正確的，但我不提供任何保證。使用時風險自負！*
致謝：
感謝 Python 郵件列表中所有給予我支持的人。Paul Foley 指出了各種不精確之處，並促使我加入了區域優先順序（local precedence ordering）的部分。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 的方法解析順序不具單調性（monotonic），並提議以 C3 方法解析順序來取代。Guido 同意他的論點，因此 Python 2.3 現在使用 C3。C3 方法本身與 Python 無關，因為它是由研究 Dylan 語言的人所發明，並在一篇針對 Lisp 程式設計師的論文 [2] 中描述。本文為想要了解此變更原因的 Python 程式設計師提供了 C3 演算法（希望是）易讀的討論。
首先讓我指出，我要說的僅適用於 Python 2.2 中引入的 新式類別（new style classes）：經典類別（classic classes） 維持其舊有的方法解析順序，即深度優先然後由左至右。因此，經典類別的舊程式碼不會受到影響；即使原則上 Python 2.2 新式類別的程式碼可能會受影響，但實際上 C3 解析順序與 Python 2.2 方法解析順序不同的情況極為罕見，因此預期不會真正破壞程式碼。因此：
別怕！
此外，除非你大量使用多重繼承且有複雜的類別階層，否則你無需了解 C3 演算法，可以輕鬆跳過本文。另一方面，如果你真的想知道多重繼承如何運作，那麼本文就是為你準備的。好消息是，事情並不像你想像的那樣複雜。
讓我從一些基本定義開始。
給定複雜多重繼承階層中的類別 C，要指定方法被覆寫（override）的順序並非易事，也就是要指定 C 的祖先順序。
類別 C 的祖先串列（包含類別本身），從最近的祖先到最遠的祖先排序，稱為類別優先串列（class precedence list）或 C 的線性化（linearization）。
方法解析順序 (Method Resolution Order, MRO) 是建構線性化的一組規則。在 Python 文獻中，習慣用語「C 的 MRO」也是 C 類別線性化的同義詞。
例如，在單一繼承階層的情況下，如果 C 是 C1 的子類別，而 C1 是 C2 的子類別，那麼 C 的線性化就是串列 [C, C1, C2]。然而，在多重繼承階層中，線性化的建構更加複雜，因為要建構一個遵守區域優先順序（local precedence ordering） 和單調性（monotonicity） 的線性化更加困難。
我將在稍後討論區域優先順序，但可以在此給出單調性的定義。當以下條件為真時，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（頭部）是其第一個元素：
head = C1
而 tail（尾部）是串列的其餘部分：
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.
然而，一般來說必須根據以下規則來計算合併：
take the head of the first list, i.e L[B1][0]; if this head is not in the tail of any of the other lists, then add it to the linearization of C and remove it from the lists in the merge, otherwise look at the head of the next list and take it, if it is a good head. Then repeat the operation until all the classes are removed or it is impossible to find good heads. In this case, it is impossible to construct the merge, Python 2.3 will refuse to create the class C and will raise an exception.
此規則確保合併操作保留順序（如果順序可以被保留）。另一方面，如果無法保留順序（如上面討論的嚴重順序分歧的範例），則無法計算合併。
如果 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 | （更廣泛） / --- \ / | \ | / | \ | / | \ | --- --- --- | Level 2 3 | D | 4| E | | F | 5 | --- --- --- | \ \ _ / | | \ / \ _ | | \ / \ | | --- --- | Level 1 1 | B | | C | 2 | --- --- | \ / | \ / \ / --- Level 0 0 | A | （更專精） ---
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 打破諸如區域優先順序和單調性之類的基本屬性時，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 *跟隨* 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；在這種情況下，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 也決定了屬性的解析順序；
Pythonistas 的預設食物是 spam！（但是你已經知道 ;-)
在討論了區域優先順序的問題之後，現在讓我考慮單調性問題。我的目標是表明經典類別的 MRO 或 Python 2.2 新式類別都不是單調的。
為了證明經典類別的 MRO 是非單調的，查看鑽石圖就足夠了：
C / \ / \ A B \ / \ / D
可以很容易地辨別出這種不一致：
L[B,P21] = B C # B 優先於 C：B 的方法勝出
L[D,P21] = D A C B C # B 跟隨 C：C 的方法勝出！
另一方面，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>
"""Samuele Pedroni 撰寫的 C3 演算法（由我改善了可讀性）。"""
class __metaclass__(type):
"所有類別都會被神奇地修改以便美觀地列印"
__repr__ = lambda cls: cls.__name__
class ex_2:
"嚴重的順序分歧" # 來自 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 # 在 Python 2.2 中會建立 Z(A,B)
except TypeError:
pass # 在 Python 2.3 中無法建立 Z(A,B)
class ex_5:
"我的第一個範例"
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:
"我的第二個範例"
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:
"Python 2.2 MRO 與 C3 的差異" # 來自 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: # 在序列頭部中尋找合併候選者
cand = seq[0]; print ' ',cand,
nothead=[s for s in nonemptyseqs if cand in s[1:]]
if nothead: cand=None # 拒絕候選者
else: break
if not cand: raise "不一致的階層結構"
res.append(cand)
for seq in nonemptyseqs: # 移除候選者
if seq[0] == cand: del seq[0]
def mro(C):
"根據 C3 計算類別優先串列 (mro)"
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>
就這樣，各位，
祝使用愉快！