C3-линеаризация

C3-линеаризация суперкласса (англ. C3 superclass linearization) — алгоритм, используемый преимущественно для получения устойчивой линеаризации иерархии множественного наследования в объектно-ориентированном программировании. Данная линеаризация используется для определения порядка, в котором должны наследоваться методы, что часто в англоязычной литературе обозначается как «MRO» (сокращение от «Method Resolution Order», то есть «порядок разрешения метода»). C3 в названии указывает на три главные особенности итоговой линеаризации: устойчивый и расширяющийся (по старшинству) граф, сохранение локального порядка старшинства, а также монотонность. Данная теория впервые была представлена в 1996 году в рамках конференции OOPSLA, в документе, озаглавленном «Монотонная линеаризация суперкласса для языка Dylan»^[1]. Впоследствии данный алгоритм был выбран как алгоритм по умолчанию для разрешения методов в языке программирования Python 2.3 (и последующих версиях), Perl 6 и виртуальной машине Parrot. Он также доступен в виде альтернативы (не являясь MRO по умолчанию) в ядре Perl 5, начиная с версии 5.10.0. Расширенная реализация для более ранних версий Perl 5 носит название Class::C3 и существует в CPAN.

Для

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]

L(B)  := [B, O]                                             // линеаризация B, C, D и E
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 подходит для первого шага merge, потому что он появляется только в начале всех списков
       = [K1, A] + merge([O], [B, O], [C, O], [B, C])       // класс O не подходит, так как он содержится в хвостах списков 2 и 3, но...
       = [K1, A, B] + merge([O], [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])
       = [K3, D] + merge([O], [A, O], [A])
       = [K3, D, A] + merge([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]                                               // ответ

Обозначения:

L(Class) - линеаризация класса Class
[A,B,C]  - список из трех элементов, где голова это A, а хвост [B,C]
merge    - слияние списков

Функция merge осуществляет слияние списков таким образом, чтобы каждый элемент встречался в результате ровно один раз, этим она похожа на слияние множеств, но тут важен порядок следования элементов в списке. Функция merge работает следующим образом - она перебирает списки-аргументы по порядку упоминания (слева направо), выбирая первый элемент, который может быть первым в нескольких списках, но нигде не упоминается вторым и далее, и перемещает его в список-результат, исключая из списков-аргументов, повторяя эту процедуру несколько раз, пока все элементы не переместятся из списков-аргументов в список-результат. Если на каком-то этапе возникает ситуация, что нельзя выбрать элемент-кандидат, удовлетворяющий указанному условию, т.е. если во всех списках-аргументах первые элементы встречаются в других списках-аргументах не первыми, итоговый список не создаётся.