C3线性化

在计算机科学中，C3算法主要用在多重继承中，确定子类应该继承哪一个父类的方法。换句话说，C3超类线性化的输出是确定性的方法解析顺序（MRO：Method Resolution Order）。

C3算法得名于它实现了一致性于三种重要特性：

• 一致性扩展的优先图，
• 局部优先原则（比如A继承B和C，C继承B，那么A读取父类方法，应该优先使用C的方法而不是B的方法），
• 单调性原则（即子类不改变父类的方法搜索顺序）。

在1996年的OOPSLA会议上，发表的论文《Dylan的单调超类线性化》，首次提出了C3超类线性化。Python 2.3、Raku、Parrot、Solidity和PGF/TikZ的面向对象语言模块等，将它选作方法解析的默认算法。Perl 5语言从版本5.10.0起将它作为可选的、非默认的MRO。早期版本Perl 5有称为Class::C3一个扩展实现曾发布于CPAN。

Python创始人Guido van Rossum这样总结C3超类线性化：

基本上，在C3背后的想法是，如果你写下在复杂的类层级中继承关系所施加的所有次序规则，这个算法将确定出满足所有这些规则的这些类的一个单调次序。如果不能确定出这样的次序，这个算法会失败。

描述

一个类的C3超类线性化，是这个类加上它的这些父类的线性化和这些父类自身的列表的唯一性归并的总和。这些父类的列表作为给这个归并过程的最后实际参数，保持了这些直接父类的局部优先次序。

完成父类的线性化和父类列表的归并，选择这些列表的头部中第一个符合条件者，它不出现在任何这些列表的尾部（一个列表的除了第一个元素的所有元素）之中。注意一个良好头部，可以同时出现为多个列表的第一个元素，但是禁止它出现在任何其他地方。将选择的元素从以它作为头部的所有列表中移除，并将它填加到输出列表。重复选择并移除良好头部并扩展输出列表的过程，直到所有余下的列表被竭尽。如果在某一点上，因为所有余下列表的头部都出现在某个列表的尾部中，而没有良好头部可选，那么由于在继承层级中依赖的不一致次序，归并过程不能计算下去，故而最初类的线性化不存在。

计算一个类的线性化的一种朴素分治法，可以采用递归算法来为归并子例程找到父类的线性化。但是，这将在出现环状类层级时导致无限循环递归。为了检测这种环并打破无限递归，并重新利用前面计算的结果作为一种优化，递归调用应当通过缓存或记忆化的方式屏蔽重入以前的实际参数。

这个算法类似于找到拓扑次序。

例子

给定

一个C3线性化的依赖图例子

 class O
 class A extends O
 class B extends O
 class C extends O
 class D extends O
 class E extends O
 class K1 extends A, B, C
 class K2 extends D, B, E
 class K3 extends D, A
 class Z extends K1, K2, K3

Z的线性化计算：
 L(O)  := [O]                       // O的线性化就是平凡的单例列表[O]，因为O没有父类
 
 L(A)  := [A] + merge(L(O), [O])    // A的线性化是A加上它的父类的线性化与父类列表的归并
        = [A] + merge([O], [O])
        = [A, O]                    // 其结果是简单的将A前置于它的单一父类的线性化
 
 L(B)  := [B, O]                    // B、C、D和E的线性化的计算类似于A
 L(C)  := [C, O]
 L(D)  := [D, O]
 L(E)  := [E, O]
 
 L(K1) := [K1] + merge(L(A), L(B), L(C), [A, B, C])          // 首先找到K1的父类的线性化L(A)、L(B)和L(C)，接着将它们归并于父类列表[A, B, C]
        = [K1] + merge([A, O], [B, O], [C, O], [A, B, C])    // 类A是第一个归并步骤的良好候选者，因为它只出现为第一个和最后一个列表的头部元素。
        = [K1, A] + merge([O], [B, O], [C, O], [B, C])       // 类O不是第二个归并步骤的良好候选者，因为它还出现在列表2和列表3的尾部中；但是类B是良好候选者
        = [K1, A, B] + merge([O], [O], [C, O], [C])          // 类C是良好候选者；类O仍出现在列表3的尾部中
        = [K1, A, B, C] + merge([O], [O], [O])               // 最后，类O是有效候选者，这还竭尽了所有余下的列表
        = [K1, A, B, C, O]
 
 L(K2) := [K2] + merge(L(D), L(B), L(E), [D, B, E])
        = [K2] + merge([D, O], [B, O], [E, O], [D, B, E])    // 选择D
        = [K2, D] + merge([O], [B, O], [E, O], [B, E])       // 不选O，选择B
        = [K2, D, B] + merge([O], [O], [E, O], [E])          // 不选O，选择E
        = [K2, D, B, E] + merge([O], [O], [O])               // 选择O
        = [K2, D, B, E, O]
 
 L(K3) := [K3] + merge(L(D), L(A), [D, A])
        = [K3] + merge([D, O], [A, O], [D, A])               // 选择D
        = [K3, D] + merge([O], [A, O], [A])                  // 不选O，选择A
        = [K3, D, A] + merge([O], [O])                       // 选择O
        = [K3, D, A, O]
 
 L(Z)  := [Z] + merge(L(K1), L(K2), L(K3), [K1, K2, K3])
        = [Z] + merge([K1, A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K1, K2, K3])    // 选择K1
        = [Z, K1] + merge([A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K2, K3])        // 不选A，选择K2
        = [Z, K1, K2] + merge([A, B, C, O], [D, B, E, O], [K3, D, A, O], [K3])            // 不选A，不选D，选择K3
        = [Z, K1, K2, K3] + merge([A, B, C, O], [D, B, E, O], [D, A, O])                  // 不选A，选择D
        = [Z, K1, K2, K3, D] + merge([A, B, C, O], [B, E, O], [A, O])                     // 选择A
        = [Z, K1, K2, K3, D, A] + merge([B, C, O], [B, E, O], [O])                        // 选择B
        = [Z, K1, K2, K3, D, A, B] + merge([C, O], [E, O], [O])                           // 选择C
        = [Z, K1, K2, K3, D, A, B, C] + merge([O], [E, O], [O])                           // 不选O，选择E
        = [Z, K1, K2, K3, D, A, B, C, E] + merge([O], [O], [O])                           // 选择O
        = [Z, K1, K2, K3, D, A, B, C, E, O]                                               // 完成

例子的 Python 实现

以下为 C3 算法 Python 实现的一个例子：

def c3_mro(cls):
    if cls is object:
        # 讨论假设顶层基类为 object ，递归终止
        return [object]
 
    # 构造 C3-MRO 算法的总式，递归开始
    merge_list = [c3_mro(base_cls) for base_cls in cls.__bases__]
    merge_list.append(list(cls.__bases__))
    mro = [cls] + merge(merge_list)
    return mro
 
 
def merge(in_lists):
    if not in_lists:
        # 若合并的内容为空，返回空 list
        # 配合下文的排除空 list 操作，递归终止
        return []
 
    # 遍历要合并的 MRO
    for mro_list in in_lists:
        # 取头
        head = mro_list[0]
        # 遍历要合并的 MRO（与外一层相同），检查尾中是否有头
        for cmp_list in in_lists:
            if cmp_list is mro_list:
                continue
            
            if head in cmp_list[1:]:
                break
        else:
            # 筛选出好头
            next_list = []
            for merge_item in in_lists:
                if head in merge_item:
                    merge_item.remove(head)
                
                if merge_item:
                    # 排除空 list
                    next_list.append(merge_item)
            # 递归开始
            return [head] + merge(next_list)
    else:
        # 无好头，引发类型错误
        raise TypeError

首先，metaclass 允许对象通过名字简明表示而不用 <class '__main__.A'>:

class Type(type):
    def __repr__(cls):
        return cls.__name__
A = Type('A', (object,), {})

类 A 表示自身通过名字：

>>> A
A

由于 Python 3 的metaclass语法改变了，为使例子兼任版本2与3，用metaclass创建对象，如同用type。

A = Type('A', (object,), {})
B = Type('B', (object,), {})
C = Type('C', (object,), {})
D = Type('D', (object,), {})
E = Type('E', (object,), {})
K1 = Type('K1', (A, B, C), {})
K2 = Type('K2', (D, B, E), {})
K3 = Type('K3', (D, A), {})
Z = Type('Z', (K1, K2, K3), {})

等价的Python 2 的类定义是：

class Z(K1, K2, K3):
    __metaclass__ = Type

对于Python 3是

class Z(K1, K2, K3, metaclass=Type):
    pass

最后有：

>>> Z.mro()
[Z, K1, K2, K3, D, A, B, C, E, <type 'object'>]