Python 2.3 方法解析順序

備註

這是一份歷史文件，作為正式文件的附錄提供。此處討論的方法解析順序 (Method Resolution Order) 是在 Python 2.3 中 引入 的，但仍在後續版本中使用，包括 Python 3。

作者：Michele Simionato。

摘要:

此文件適用於想要了解 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 演算法，可以輕鬆跳過本文。另一方面，如果你真的想知道多重繼承如何運作，那麼本文就是為你準備的。好消息是，事情並不像你想像的那樣複雜。

讓我從一些基本定義開始。

  1. 給定複雜多重繼承階層中的類別 C，要指定方法被覆寫（override）的順序並非易事，也就是要指定 C 的祖先順序。

  2. 類別 C 的祖先串列（包含類別本身），從最近的祖先到最遠的祖先排序，稱為類別優先串列（class precedence list）或 C 的線性化（linearization）。

  3. 方法解析順序 (Method Resolution Order, MRO) 是建構線性化的一組規則。在 Python 文獻中，習慣用語「C 的 MRO」也是 C 類別線性化的同義詞。

  4. 例如，在單一繼承階層的情況下，如果 C 是 C1 的子類別，而 C1 是 C2 的子類別，那麼 C 的線性化就是串列 [C, C1, C2]。然而，在多重繼承階層中，線性化的建構更加複雜，因為要建構一個遵守區域優先順序（local precedence ordering） 和單調性（monotonicity） 的線性化更加困難。

  5. 我將在稍後討論區域優先順序，但可以在此給出單調性的定義。當以下條件為真時，MRO 具有單調性：如果 C1 在 C 的線性化中先於 C2，那麼 C1 在 C 的任何子類別的線性化中也先於 C2。否則，衍生新類別這個看似無害的操作可能會改變方法的解析順序，進而引入非常微妙的錯誤。稍後將展示發生這種情況的範例。

  6. 並非所有類別都能進行線性化。在複雜的階層結構中，有些情況下無法衍生出一個類別，使其線性化遵守所有所需的屬性。

以下是這種情況的範例。考慮以下階層結構

>>> 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.

然而，一般來說必須根據以下規則來計算合併：

取第一個串列的頭部，即 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 |                  （更廣泛）
                      /  ---  \
                     /    |    \                      |
                    /     |     \                     |
                   /      |      \                    |
                  ---    ---    ---                   |
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

在此範例中，線性化是根據繼承層級以相當不錯的方式排序的，因為較低層級（即更專精的類別）具有更高的優先級（請參見繼承圖）。但是這不是一般情況。

第二個範例的線性化之計算我留給讀者當作練習：