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算法的流程。