C3线性化（C3 Linearization）
学习Solidity语言的时候，通过多重继承接触到了C3线性化的概念，整理一篇文章记录下相关知识点。
背景
在支持多重继承的语言中，比如python、solidity等，如果出现了一个类有多重继承的情况，如下Python代码：
#!/usr/bin/python
class O(object):
def echo(self):
print "I am class_O"
class A(O):
pass
class B(O):
pass
class C(O):
pass
class K1(B,A):
def echo(self):
print "I am class_K1"
class K2(C,A):
pass
class Z(K2,K1):
pass
就会出现一个问题，如果我调用Z中的某个父类方法时，该去调用哪个父类呢？子类往上寻找父类方法的顺序是什么？
什么是C3
C3线性化，也叫方法解析顺序（Method Resolution Order，MRO）,是一种用于在多继承时确定继承的方法的调用顺序的算法。 至于为什么叫C3，主要是因为最终线性化的三种重要特性：
- 一致扩展前趋图
- 本地前趋序的保持
- 适于单调标准
也就是说通过C3算法将多重继承的树状结构继承关系实现线性化，生成一个线性序列，确定了子类查找父类方法的优先顺序。
C3算法规则解释
关于C3算法的规则，我们先看分别引用三个地方不同的解释：
引用维基百科-C3线性化
一个类的C3超类线性化是这个类，再加上它的各个父类的线性化与各个父类形成列表的唯一合并的结果。 父类列表作为合并过程的最后实参，保持了直接父类的本地前趋序。 各个父类的线性化与各个父类形成列表的合并算法，首先选择不出现在各个列表的尾部（指除了第一个元素外的其他元素）的第一个元素，该元素可能同时出现在多个列表的头部。被选中元素从各个列表中删除并追加到输出列表中。这个选择再删除、追加元素的过程迭代下去直到各个列表被耗尽。如果在某个时候无法选出元素，说明这个类继承体系的依赖序是不一致的，因而无法线性化。引用《Python高级编程》
引用网络文章-python多重继承新算法C3
如果继承至一个基类: class B(A) 这时B的mro序列为[B,A] 如果继承至多个基类 class B(A1,A2,A3 ...) 这时B的mro序列 mro(B) = [B] + merge(mro(A1), mro(A2), mro(A3) ..., [A1,A2,A3]) merge操作就是C3算法的核心。 遍历执行merge操作的序列，如果一个序列的第一个元素，是其他序列中的第一个元素，或不在其他序列出现，则从所有执行merge操作序列中删除这个元素，合并到当前的mro中。 merge操作后的序列，继续执行merge操作，直到merge操作的序列为空。 如果merge操作的序列无法为空，则说明不合法。
C3算法实践过程
再回到最开始的Python代码中的多继承关系，梳理如下:
O
A -> O
B -> O
C -> O
K1 -> B, A
K2 -> C, A
Z -> K2, K1
我们的目标是确定Z的父类方法调用顺序
开始按照C3算法计算，核心点在于从Merge的序列中取出合适的元素，放入到当前的Mro序列中，直到Merge序列为空为止。
L(O) := [O]
L(A) := [A] + merge(L(O), [O])
= [A] + merge([O], [O])
= [A, O]
L(B) := [B, O]//计算过程类似L(A)
L(C) := [C, O]//计算过程类似L(A)
L(K1) := [K1] + merge(L(B), L(A), [B, A])
= [K1] + merge([B, O], [A, O], [B, A])
//取一个序列的第一个元素，是其他序列中的第一个元素，或不在其他序列出现，符合条件是B
= [K1, B] + merge([O], [A, O], [A])
= [K1, B, A] + merge([O], [O])
= [K1, B, A, O]
L(K2) := [K2, C, A, O]//计算过程类似L(K1)
L(Z) := [Z] + merge(L(K2), L(K1), [K2, K1])
= [Z] + merge([K2, C, A, O], [K1, B, A, O], [K2, K1])
= [Z, K2] + merge([C, A, O], [K1, B, A, O], [K1])
= [Z, K2, C] + merge([A, O], [K1, B, A, O], [K1])
= [Z, K2, C, K1] + merge([A, O], [B, A, O])
= [Z, K2, C, K1, B] + merge([A, O], [A, O])
= [Z, K2, C, K1, B, A] + merge([O], [O])
= [Z, K2, C, K1, B, A, O]
那么结论就是Z类的父类方法调用顺序为Z, K2, C, K1, B, A, O
验证结果
在Python中，使用mro属性来存储当前类的方法解析顺序，我们可以在最初的Python代码最后面加入一行
print Z.__mro__
然后执行这段Python即可看到结果：
本作品由TedXiong采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。