C3 linearization

Определение

C3-линеаризация — это алгоритм, который Python использует для построения MRO (Method Resolution Order). Он определяет строгую последовательность обхода родительских классов при поиске методов и атрибутов.

Зачем нужна

C3 linearization была введена в Python 2.3, чтобы решить проблемы старого поиска в глубину (DFS), который некорректно работал в сложных иерархиях. Она успешно справляется с «проблемой ромба» (diamond problem), когда один и тот же базовый класс встречается в дереве наследования несколько раз.
Главная цель алгоритма — гарантировать монотонность: если класс A стоит перед B в списке родителей, то и во всей итоговой цепочке поиска он должен стоять раньше.

Как работает алгоритм

Линеаризация класса L[C] вычисляется как сам класс плюс результат слияния (merge) линеаризаций его родителей и списка самих родителей.

L[C]=[C] + merge(L[P1],L[P2],…,L[Pn],[P1,P2,…,Pn])

Правила слияния (merge):

• Берётся голова первого списка (первый элемент).

• Если этот элемент не является «хвостом» (любым элементом, кроме первого) в других списках, он добавляется в итоговый MRO.

• Этот элемент удаляется из всех списков, и процесс повторяется.

• Если элемент найден в хвосте другого списка, переходим к голове следующего списка.

Пример «Ромб»

    class O: pass
    class A(O): pass
    class B(O): pass
    class C(A, B): pass

    # Порядок поиска методов (MRO) для класса C:
    print(C.mro())
    # [C, A, B, O, object]

Здесь алгоритм гарантирует, что общий предок O будет проверен только после того, как будут просмотрены оба его потомка (A и B).

Ключевые мысли

• Алгоритм обеспечивает соблюдение локального приоритета (порядок перечисления родителей при объявлении класса сохраняется).

• C3-линеаризация делает поведение super() предсказуемым в сложных схемах множественного наследования.

• Если иерархия классов нарушает правила линеаризации (например, создаёт циклическое противоречие), Python выдаст ошибку TypeError: Cannot create a consistent MRO.