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。

Python創始人吉多·范羅蘇姆這樣總結C3超類線性化：「基本上，在C3背後的想法是，如果你寫下在複雜的類層級中繼承關系所施加的所有次序規則，這個演算法將確定出滿足所有這些規則的這些類的一個單調次序。如果不能確定出這樣的次序，這個演算法以失敗告終。」

## 演算法

一個類的C3超類線性化列表，是這個類的單例列表，串接上從並發的諸基類的線性化列表以及諸基類自身列表歸併而成的唯一性序列化列表。這個演算法要確定的單調次序類似於拓撲次序，諸基類自身列表作為給這個歸併過程的最後實際參數，保持了這些直接基類的局部優先次序。

完成諸基類的線性化列表和諸基類列表的歸併，就是選擇這些列表的頭部中第一個符合條件者，它可以同時出現為多個列表的第一個元素，但是禁止它出現在任何其他非頭部位置。將選擇的元素從以它作為頭部的所有列表中移除，並將它填加到輸出列表。重複選擇並移除符合條件頭部並擴展輸出列表的過程，直到竭盡所有餘下的列表。在這個處理過程中，如果由於所有餘下列表的頭部都出現在其他某個列表的非頭部中，而沒有選出符合條件的頭部，則歸併過程失敗；在繼承層級中的這種不一致性的依賴次序，導致這個類的線性化不存在。

計算一個類的線性化可以採用下文例子中演示的演算法，在繼承層級中找到這個類的所有基類，從根基類開始逐步進行歸併處理。計算一個類的線性化還可以採用樸素分治演算法，為求解這個類而遞歸的為歸併子例程找到基類的線性化，但是它在用於存在環的類層級之時會導致無限循環遞歸，故而遞歸調用應當結合緩存或記憶化的優化方式。

## 例子

給定一個類`Z`的如下類層級：

<image>

```java
 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`的線性化計算過程：

```pascal
 L(O)  := [O]                       // O没有基类
 
 L(A)  := [A] + merge(L(O), [O]) 
        = [A] + merge([O], [O])
        = [A, O]                    // A只有单一基类
 
 L(B)  := [B, O]
 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] + merge([A, O], [B, O], [C, O], [A, B, C])    // 选择A
        = [K1, A] + merge([O], [B, O], [C, O], [B, C])       // 不选O，选择B
        = [K1, A, B] + merge([O], [O], [C, O], [C])          // 不选O，选择C
        = [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

首先，定義一個元類來允許對象通過名字簡明表示：

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

class O(object, metaclass=Type): pass 
```

根基類`O`通過名字`O`表示自身，而不採用默認表示形式`<class '__main__.O'>`。

下面定義一些基類，並接著構造這個繼承樹：

```python
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
```

查看結果：

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

### Raku

Raku默認的對類使用C3線性化：

```perl6
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對象從其繼承的類型。