C3线性化算法

在介绍算法之前，我们首先约定需要使用的符号。我们用
C₁ C₂ ....... C_n表示包含 N 个类的列表，并令
head(C₁C₂⋯C_N)=C₁
tail(C₁C₂⋯C_N)=C₁C₂⋯C_N

为了方便做列表连接操作，我们记：

C₁+(C₂C₃⋯C_N)=C₁C₂⋯C_N

假设类 C继承自父类 B₁,⋯,B_N，那么根据 C3 线性化，类 C的方法解析列表通过如下公式确定：

L[C(B₁B_N)]=C+merge(L[B₁],⋯,L[B_N],B₁⋯B_N)

这个公式表明 C 的解析列表是通过对其所有父类的解析列表及其父类一起做 merge 操作所得到。
接下来我们介绍 C3 线性化中最重要的操作 merge ，该操作可以分为以下几个步骤：
1.选取 me rge 中的第一个列表记为当前列表 K 。
2.令 h = head( K )，如果 h 没有出现在其他任何列表的 tail 当中，那么将其加入到类 C 的线性化列表中，并将其从 merge 中所有列表中移除，之后重复步骤 2。
3.否则，设置 K 为 merge 中的下一个列表，并重复 2 中的操作。
4.如果 merge 中所有的类都被移除，则输出类创建成功；如果不能找到下一个 h ，则输出拒绝创建类 C 并抛出异常。

上面的过程看起来好像很复杂，我们用一个例子来具体执行一下，你就会觉得其实还是挺简单的。假设我们有如下的一个类继承关系：

class X():
    def who_am_i(self):
        print("I am a X")
        
class Y():
    def who_am_i(self):
        print("I am a Y")
        
class A(X, Y):
    def who_am_i(self):
        print("I am a A")
        
class B(Y, X):
     def who_am_i(self):
         print("I am a B")
         
class F(A, B):
    def who_am_i(self):
        print("I am a F")

首先我们有 L [ X ] = X ， L [ Y ] = Y ，然后立即可以得到:
L[A]=A+merge[L[X],L[Y],X,Y]=[A,X,Y]
L[B]=B+merge[L[Y],L[X],Y,X]=[B,Y,X]
根据公式：
L[F]=F+merge[L[A],L[B],A,B]=F+merge[[A,X,Y],[B,Y,X],A,B]
我们首先选取 h = h e a d ( L [ A ] ) = A ，发现 A 可以加入到类 C 的解析列表中（同时将 A 从其他列表中删去），所以得到：
L[F]=[F,A]+merge[[X,Y],[B,Y,X],B]

之后选取 h = h e a d ( L [ A ] ) = X ，发现 X 不能满足要求（因为 X 在 L [ B ] 的 t a i l 中出现），所以根据步骤 3 选取下一个列表并令 h = h e a d ( L [ B ] ) = B ，然后将 B 加入到类 C 的解析列表中得到：
L[F]=[F,A,B]+merge[[X,Y],[Y,X]]

接下来按照算法流程应该选取 h = h e a d ( L [ B ] ) = Y ，很显然 Y 并不能满足要求，此时由于 m e r g e 中没有下一个列表了，所以不能继续选择 h ，所以根据步骤 4 算法输出类 F 创建失败并抛出异常。如果你用 new-style class 的方式执行一下上面的代码，你就会发现 Python 解释器将不允许你创建类 F:

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

自己写一遍：

class A:
    def myc(self):
        print("mya")

class B(A):
    def myc(self):
        print("myb")

class C(A):

    def myc(self):
        print("myc")


class D(B,C):

    def myd(self):
        print("myd")


print(D.__mro__)

# L|C(B1....BN) = C + merge([L|B1]....[L|Bn],B1....BN)

L(B) = B + merge(L(A),[A]) = [B,A]

L(C) = C + merge(L(A),[A]) = [C,A]


L(D) = D + merge(L(B),L(C),(B,C))
这时候我们把L(B) =[B,A], L(C) =[C,A] 替换L(D) 的里面去就得到如下:

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

这时候我们看B 有没有在其他列表尾部，
没有，先把D和B组合成一个列表，
然后把B 在的[B,A]列表和(B,C)去掉所以得到如下

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

这时候我们看A 有没有在其他列表尾部，
有，A 在[A] 和[C,A] 都在尾部，所以进行不下去了，
我们看[CA]这个列表，C 不在其他列表尾部，所以得到如下

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

L[D] = [D,B,C,A]