Python 2.3 方法解析順序
| 摘要 | 本文件適用於希望瞭解 Python 2.3 中使用的 C3 方法解析順序的 Python 程式設計師。 雖然本文件並非面向新手，但它具有很強的教學性，幷包含許多已解決的示例。我沒有找到其他公開可用的具有相同範圍的文件，因此本文件應該很有用。 |
|---|
免責宣告
我將本文件捐贈給 Python 軟體基金會，遵循 Python 2.3 許可證。 與往常一樣，我提醒讀者，以下內容應該是正確的，但我不做任何保證。 使用本文件的風險自負！
鳴謝
感謝 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]。本文給出了對 C3 演算法的（希望）易讀的討論，以供希望瞭解更改原因的 Python 愛好者參考。
首先，我想指出，我接下來要說的僅適用於 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：基類 Y 和 X 之間存在 MRO 衝突），從而阻止幼稚的程式設計師建立模糊的層次結構。 Python 2.2 則不會引發異常，而是選擇一個臨時的排序（在本例中為 CABXYO）。
_ .-=-. .-==-.
{ } __ .' O o '. / -<' )
{ } .' O'. / o .-. O \ / .--v`
{ } / .-. o\ /O / \ o\ /O /
\ `-` / \ O`-'o / \ O`-`o /
jgs `-.-` '.____.' `.____.'
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]
但是，在多重繼承的情況下，事情更加麻煩，我不希望您在沒有幾個示例的情況下就能理解該規則 ;-)
.-'-.
/' `\
/' _.-.-._ `\
| (|) (|) |
| \__"__/ |
\ |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 是一個好的頭部，因此我們取它，並且我們簡化為計算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 '__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 時引發異常來解決歧義，有效地阻止程式設計師生成有歧義的層次結構。原因是當合並
merge(FO,EFO,FE)
無法計算時，C3 演算法會失敗，因為 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 決定的是屬性的解析順序，而不僅僅是方法的解析順序；
- Pythonistas 的預設食物是 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 在實踐中並不那麼糟糕，因為人們通常可以避免經典類的鑽石繼承。但是所有新式類都繼承自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 規則。
__
(\ .-. .-. .-. .-. .-. .-. .-. .-. /_")
\\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//^\\_//
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] | 論文《Dylan 的單調超類線性化》：https://doi.org/10.1145/236337.236343 |
| [3] | Guido van Rossum 的文章《統一 Python 2.2 中的型別和類》：https://python.club.tw/2.2.2/descrintro.html |