技術文章 » Python MRO方法解析順序詳解

Python MRO方法解析順序詳解

2020-07-16 10:05:01
我們知道，Python 類是支援（多）繼承的，一個類的方法和屬性可能定義在當前類，也可能定義在基礎類別。針對這種情況，當呼叫類方法或類屬性時，就需要對當前類以及它的基礎類別進行搜尋，以確定方法或屬性的位置，而搜尋的順序就稱為方法解析順序。

方法解析順序（Method Resolution Order），簡稱 MRO。對於只支援單繼承的程式語言來說，MRO 很簡單，就是從當前類開始，逐個搜尋它的父類別；而對於 Python，它支援多繼承，MRO 相對會複雜一些。

實際上，Python 發展至今，經歷了以下 3 種 MRO 演算法，分別是：
  1. 從左往右，採用深度優先搜尋（DFS）的演算法，稱為舊式類的 MRO；
  2. 自 Python 2.2 版本開始，新式類在採用深度優先搜尋演算法的基礎上，對其做了優化；
  3. 自 Python 2.3 版本，對新式類採用了 C3 演算法。由於 Python 3.x 僅支援新式類，所以該版本只使用 C3 演算法。

有關舊式類和新式類的講解，可閱讀《Python super()使用注意事項》一文。

有讀者可能會好奇，為什麼 MRO 棄用了前兩種演算法，而選擇最終的 C3 演算法呢？原因很簡單，前 2 種演算法都存在一定的問題。

舊式類MRO演算法

在使用舊式類的 MRO 演算法時，以下面程式碼為例（程式一）: 
class A:
    def method(self):
      print("CommonA")
class B(A):
    pass
class C(A):
    def method(self):
      print("CommonC")
class D(B, C):
    pass
print(D().method())
通過分析可以想到，此程式中的 4 個類是一個“菱形”繼承的關係，當使用 D 類物件存取 method() 方法時，根據深度優先演算法，搜尋順序為 D->B->A->C->A。

舊式類的 MRO 可通過使用 inspect 模組中的 getmro(類名) 函數直接獲取。例如 inspect.getmro(D) 表示獲取 D 類的 MRO。

因此，使用舊式類的 MRO 演算法最先搜尋得到的是基礎類別 A 中的 method() 方法，即在 Python 2.x 版本中，此程式的執行結果為：

CommonA

但是，這個結果顯然不是想要的，我們希望搜尋到的是 C 類中的 method() 方法。

新式類MRO演算法

為解決舊式類 MRO 演算法存在的問題，Python 2.2 版本推出了新的計算新式類 MRO 的方法，它仍然採用從左至右的深度優先遍歷，但是如果遍歷中出現重複的類，只保留最後一個。

仍以上面程式為例，通過深度優先遍歷，其搜尋順序為 D->B->A->C->A，由於此順序中有 2 個 A，因此僅保留後一個，簡化後得到最終的搜尋順序為 D->B->C->A。

新式類可以直接通過 類名.__mro__ 的方式獲取類的 MRO，也可以通過 類名.mro() 的形式，舊式類是沒有 __mro__ 屬性和 mro() 方法的。

可以看到，這種 MRO 方式已經能夠解決“菱形”繼承的問題，但是可能會違反單調性原則。所謂單調性原則，是指在類存在多繼承時，子類不能改變基礎類別的 MRO 搜尋順序，否則會導致程式發生異常。

例如，分析如下程式（程式二）： 
class X(object):
  pass
class Y(object):
  pass
class A(X,Y):
  pass
class B(Y,X):
  pass
class C(A, B):
  pass
通過進行深度遍歷，得到搜尋順序為 C->A->X->object->Y->object->B->Y->object->X->object，再進行簡化（相同取後者），得到 C->A->B->Y->X->object。

下面來分析這樣的搜尋順序是否合理，我們來看下各個類中的 MRO：
  • 對於 A，其搜尋順序為 A->X->Y->object；
  • 對於 B，其搜尋順序為 B->Y->X->object；
  • 對於 C，其搜尋順序為 C->A->B->X->Y->object。
可以看到，B 和 C 中，X、Y 的搜尋順序是相反的，也就是說，當 B 被繼承時，它本身的搜尋順序發生了改變，這違反了單調性原則。

MRO C3

為解決 Python 2.2 中 MRO 所存在的問題，Python 2.3 採用了 C3 方法來確定方法解析順序。多數情況下，如果某人提到 Python 中的 MRO，指的都是 C3 演算法。

在 Python 2.3 及後續版本中，執行程式一，得到如下結果：

CommonC


執行程式二，會產生如下異常：

Traceback (most recent call last):
  File "C:UsersmengmaDesktopdemo.py", line 9, in <module>
    class C(A, B):
TypeError: Cannot create a consistent method resolution
order (MRO) for bases X, Y

由此可見，C3 可以有效解決前面 2 種演算法的問題。那麼，C3 演算法是怎樣實現的呢？

以程式一為主，C3 把各個類的 MRO 記為如下等式：
  • 類 A：L[A] = merge(A , object)
  • 類 B：L[B] = [B] + merge(L[A] , [A])
  • 類 C：L[C] = [C] + merge(L[A] , [A])
  • 類 D：L[D] = [D] + merge(L[A] , L[B] , [A] , [B])

注意，以類 A 等式為例，其中 merge 包含的 A 稱為 L[A] 的頭，剩餘元素（這裡僅有一個 object）稱為尾。

這裡的關鍵在於 merge，它的運算方式如下：
  1. 檢查第一個列表的頭元素（如 L[A] 的頭），記作 H。
  2. 若 H 未出現在 merge 中其它列表的尾部，則將其輸出，並將其從所有列表中刪除，然後回到步驟 1；否則，取出下一個列表的頭部記作 H，繼續該步驟。
重複上述步驟，直至列表為空或者不能再找出可以輸出的元素。如果是前一種情況，則演算法結束；如果是後一種情況，Python 會丟擲異常。

由此，可以計算出類 B 的 MRO，其計算過程為： 
L[B] = [B] + merge(L[A],[A])
     = [B] + merge([A,object],[A])
     = [B,A] + merge([object])
     = [B,A,object]
同理，其他類的 MRO 也可以輕鬆計算得出。這裡不再贅述，有興趣的讀者可自行推算。