Python多繼承解析順序的C3線性演算法流程解析

Python多繼承MRO

在Python2.1中，採用了經典類，使用深度優先演算法解析。
Python2.2中，引入了新式類，使用深度優先演算法和廣度優先演算法。
在Python2.3以後的版本中，經典類和新式類共存，使用了DFS演算法和C3演算法。
Python2中的經典類

class A(object):
    pass

Python3的新式類

class A:
    pass

C3演算法

In computing, the C3 superclass linearization is an algorithm used primarily to obtain the order in which methods should be inherited (the "linearization") in the presence of multiple inheritance, and is often termed Method Resolution Order (MRO).
這是維基百科中的定義，下麵這張圖是一張多繼承的關係圖：

那麼這裡的mro解析順序是如何的呢？單純看圖很難得出答案。
C3線性演算法的推導過程如下：
假設類C繼承自父類B1，...Bn,類C的解析列表公式如下：

這個公式表明C的解析列表是通過對其所有父類的解析列表及其父類一起merge得到的。
merge操作分為如下幾個步驟：

1. 選取merge中的第一個列表記為當前列表K。
2. 令h = head(K), 如果h沒有出現在其他任何列表的tail（列表中除了第一個元素，其餘的稱之為tail）當中，那麼將其加入類C的線性化列表中，並將其從merge中的所有列表移除，之後重覆步驟2.
3. 否則，設置K為merge的下一個列表，重覆2中的操作
4. 如果merge的所有類都被移除，則輸出類創建成功；如果不能找到下一個h，則輸出C類拋出異常。

推導過程

我們用上面的那張圖試一下推導出mro的解析順序。
上面那張圖轉換為python代碼如下：
轉換成Python代碼

O = object
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

print(Z.mro())

推導

L(K1) = K1 + merge(L[A],L[B],L[C],(A,B,C))
      = K1 + merge(L[A,O],L[B,O],L[C,O],(A,B,C))
      = [K1,A] + merge(L[O],L[B,O],L[C,O],(B,C))
      = [K1,A,B] + merge(L[O],L[O],L[C,O],(C))
      = [K1,A,B,C] + merge(L[O],L[O],L[O])
      = [K1,A,B,C,O]

L(K2) = [K2,D,B,E,O]
L(K3) = [K3,D,A,O]

以上是K1,K2,K3的解析順序

下麵是Z的推導過程

L(Z) = Z + merge(L(K1)+L(K2)+L[K3],(K1,K2,K3))
     = Z + merge(L[K1,A,B,C,O]+L(K2,D,B,E,O)+L(K3,D,A,O),(K1,K2,K3))
     = [Z,K1] + merge(L[A,B,C,O]+L(K2,D,B,E,O)+L(K3,D,A,O),(K2,K3))
     = [Z,K1,K2] + merge(L[A,B,C,O]+L(D,B,E,O)+L(K3,D,A,O),(K3))
     = [Z,K1,K2,K3] + merge(L[A,B,C,O]+L(D,B,E,O)+L(D,A,O))
     = [Z,K1,K2,K3,D] + merge(L[A,B,C,O]+L(B,E,O)+L(A,O))
     = [Z,K1,K2,K3,D,A] + merge(L[B,C,O]+L(B,E,O)+L(O))
     = [Z,K1,K2,K3,D,A,B] + merge(L[C,O]+L(E,O)+L(O))
     = [Z,K1,K2,K3,D,A,B,C] + merge(L[O]+L(E,O)+L(O))
     = [Z,K1,K2,K3,D,A,B,C,E,O]

我們得出的最終答案為：Z的解析順序：Z->K1->K2->K3->D->A->B->C->E->O
為了驗證答案，我們在python中運行

print(Z.mro())

結果如下

[<class '__main__.Z'>, <class '__main__.K1'>, <class '__main__.K2'>, <class '__main__.K3'>, <class '__main__.D'>, <class '__main__.A'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.E'>, <class 'object'>]

和我們推導的結果相同，這就是C3演算法的流程。