Solidity C3 线性化

Question

C3 算法最早被提出是用于 Lisp 的，应用在 Python 中是为了解决原来基于深度优先搜索算法不满足本地优先级，和单调性的问题。 本地优先级：指声明时父类的顺序，比如 C(A,B)，如果访问 C 类对象属性时，应该根据声明顺序，优先查找 A 类，然后再查找 B 类。 单调性：如果在 C 的解析顺序中，A 排在 B 的前面，那么在 C 的所有子类里，也必须满足这个顺序。C3 算法将多重继承的树状结构继承关系实现线性化，生成一个线性序列，确定了子类查找父类方法的优先顺序。

MRO

MRO 全称方法解析顺序（Method Resolution Order），它 决定基类中的函数到底应该以什么样的顺序调用父类中的函数。

大体顺序如下：

for(遍历执行 merge 操作的序列){
    if(一个序列的第一个元素在其他序列中也是第一个元素 || 不在其他序列出现){
        从所有执行 merge 操作序列中删除这个元素
        合并到当前的 mro 中
    }

    if(merge 操作的序列为空){
        done;
    }

    if(最后一次 merge 操作完成 && merge 操作的序列无法为空){
        throw;
        该继承不合法
    }

}

示例：

class A(O)
class B(O)
class C(O)
class E(A,B)
class F(B,C)
class G(E,F)

意思是：A 继承 O，B 继承 O，C 继承 O；E 继承 A 和 B，F 继承 B 和 C，G 继承 E 和 F。

分析 E：

[E] = [E] + merge([A], [B], [A,B])
= [E] + merge([A,O], [B,O], [A,B])

因为 A 是序列[A,O]中的第一个元素，而且在序列[B,O]中不出现，而且在序列[A,B]中也是第一个元素，所以删除 A、合并到 E，得：

[E] = [E,A] + merge([O], [B,O], [B])

继续分析：

• O 是序列[O]中的第一个元素，但 O 在序列[B,O]中出现并且不是其中第一个元素，因此不能合并
• B 是[B,O]的第一个元素，所以删除 B，合并到 E，得：
• [E] = [E,A,B] + merge([O], [O])

两个[O] 可以直接合并了，因此最终结果是 ： [E,A,B,O]

推导 F 也是一样的道理，在这里建议读者不妨先自己推理一遍，然后再对照答案。

(F) = [F] + merge([B], [C], [B,C])
= [F] + merge([B,O], [C,O], [B,C])
= [F,B] + merge([O], [C,O], [C])
= [F,B,C] + merge([O], [O])
= [F,B,C,O]