C3线性化

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

描述

C3算法得名于它的实现符合三种重要性质：一致性扩展优先图（EPG）、保留局部优先次序和适合单调性准则。

在1996年的OOPSLA会议上，发表的论文《Dylan的单调超类线性化》，首次提出了C3超类线性化。它在2012年1月被适配到了Open Dylan实现，跟从了一个增进的提议。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]                                               // 完成

用Python3展示例子

首先，定义一个元类来允许对象通过名字简明表示：

class Type(type):
    def __repr__(cls):
        return cls.__name__

class O(object, metaclass=Type): pass

类O通过名字表示自身，而不采用默认表示形式：

>>> O
O
>>> class X: pass
... 
>>> X
<class '__main__.X'>

下面定义一些基础类：

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

然后就可看到结果：

>>> Z.__mro__
[Z, K1, K2, K3, D, A, B, C, E, O, <class 'object'>]

用Raku展示例子

Raku默认的对类使用C3线性化：

class A {}
class B {}
class C {}
class D {}
class E {}
class K1 is A is B is C {}
class K2 is D is B is E {}
class K3 is D is A {}
class Z is K1 is K2 is K3 {}
say Z.^mro; # OUTPUT: ((Z) (K1) (K2) (K3) (D) (A) (B) (C) (E) (Any) (Mu))

Any和Mu是所有Raku对象从其继承的类型。