Наследование, MRO, C3 linearization

«У D есть B и C как родители, у обоих A как родитель. Какой порядок поиска атрибутов в D?» Это diamond problem — классическая ловушка multiple inheritance, в которой большинство языков прорывались хирургически (C++: virtual base, Java: запрет multiple inheritance классов). Python в 2003 году принял C3 linearization — алгоритм из академической работы Barrett et al. OOPSLA 1996, который гарантирует monotonicity и local precedence. С тех пор __mro__ Python — детерминированный кортеж, вычисляемый по строгому правилу.

В этом уроке мы откроем функцию mro_implementation() в Objects/typeobject.c, пройдём C3 merge step-by-step для diamond D(B, C), разберём три constraint’а (local precedence, monotonicity, EPG consistency), увидим реальный пример TypeError при невозможной linearization, и поймём, как super() использует tp_mro для proxy chain.

Single → multiple inheritance, diamond problem

В single inheritance (один родитель) MRO тривиален: цепочка вверх по __bases__[0]:

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

print(C.__mro__)  # (<class 'C'>, <class 'B'>, <class 'A'>, <class 'object'>)

Lookup c.attr при c = C():

1. c.__dict__ (instance attrs) — пусто.
2. C.__dict__ — нет.
3. B.__dict__ — нет.
4. A.__dict__ — нет.
5. object.__dict__ — может быть default (__repr__, __class__).

Прямолинейно. Но что, если у класса два родителя?

class A: pass
class B(A):
    def hello(self): return "B.hello"
class C(A):
    def hello(self): return "C.hello"
class D(B, C): pass         # multiple inheritance

d = D()
print(d.hello())            # ???

Какой hello() вызовется? «B.hello» (depth-first слева)? «C.hello» (breadth-first)? Это diamond problem — у нас четыре класса в форме ромба:

       A
      / \
     B   C
      \ /
       D

И вопрос принципиальный: какой порядок поиска?

MRO как монотонная linearization

MRO (Method Resolution Order) — это упорядоченный список классов, по которому CPython идёт при attribute lookup. Хранится в type.__mro__ (это tuple), в C — tp_mro (см. M04 урок 01).

Для diamond выше CPython даёт:

print(D.__mro__)
# (<class 'D'>, <class 'B'>, <class 'C'>, <class 'A'>, <class 'object'>)

print(d.hello())  # 'B.hello' - первый попавшийся в MRO

Важно: ни depth-first, ни breadth-first. Это специфичный порядок, удовлетворяющий трём требованиям одновременно (см. Python 2.3 MRO doc):

1. Local precedence: если D(B, C), то в D.__mro__ B идёт раньше C. Direct base-классы упорядочены так, как объявлены.
2. Monotonicity: если B идёт раньше C в B.__mro__ (или в любом subclass), то B должен идти раньше C и в D.__mro__. Порядок «не переворачивается» при добавлении дочерних классов.
3. EPG consistency: согласованность с __bases__ — каждый родитель идёт раньше своих собственных родителей.

Алгоритм, удовлетворяющий все три — C3 linearization (Barrett et al., OOPSLA 1996, оригинально для Dylan, потом перенят Python в 2.3).

C3 algorithm (Barrett et al. OOPSLA 1996)

Формальное определение через рекурсивный merge:

L[C] = C + merge(L[B1], L[B2], ..., L[Bn], [B1, B2, ..., Bn])

где merge(...) выбирает на каждом шаге первый "good head":
  - "head" = первый элемент любого из списков
  - "good head" = head, который НЕ появляется в "tail" (т.е. не первый и не последний элемент) ни одного из списков

Финальный кортеж L[C] — это tp_mro для класса C. Если на каком-то шаге ни один head не good — linearization невозможна, raises TypeError: Cannot create a consistent MRO.

Cite: Barrett, Cassel, Haahr, Moon, Playford, Withington — “A Monotonic Superclass Linearization for Dylan”, OOPSLA 1996; Objects/typeobject.c — mro_implementation() функция (~150 lines).

Step-by-step C3 merge: diamond D(B, C) with B(A), C(A)

Раcсмотрим:

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

Сначала вычисляем MRO для базовых:

L[object] = [object]
L[A] = [A, object]
L[B] = B + merge(L[A], [A]) = B + merge([A, object], [A]) = [B, A, object]
L[C] = C + merge(L[A], [A]) = C + merge([A, object], [A]) = [C, A, object]

Теперь главная задача — L[D]:

L[D] = D + merge(L[B], L[C], [B, C])
     = D + merge([B, A, object], [C, A, object], [B, C])

Будем выбирать good heads пошагово:

Шаг 1: списки = [B, A, object], [C, A, object], [B, C].

• Heads: B, C, B.
• B — head первого списка. В tails других списков? Tail второго = [A, object] — B нет. Tail третьего = [C] — B нет. ✓ B good → принимаем.
• Удаляем B из всех списков.

Списки после шага 1: [A, object], [C, A, object], [C].

Шаг 2: heads = A, C, C.

• A — head первого списка. В tails? Tail второго = [A, object] — да, A в tail второго списка! ✗ Не good, пропускаем.
• C — head второго списка. В tails? Tail первого = [object] — C нет. Tail третьего = [] — пусто. ✓ C good → принимаем.
• Удаляем C из всех списков.

Списки после шага 2: [A, object], [A, object], [].

Шаг 3: heads = A, A.

• A — head первого списка. В tails? Tail первого = [object] — нет. Tail второго = [object] — нет. ✓ A good → принимаем.

Списки после шага 3: [object], [object], [].

Шаг 4: heads = object.

• object — head, нет tail-конфликтов. ✓ принимаем.

Финальный merge = [B, C, A, object].

Итого: L[D] = D + [B, C, A, object] = [D, B, C, A, object].

Проверка:

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

print(D.__mro__)
# (<class 'D'>, <class 'B'>, <class 'C'>, <class 'A'>, <class 'object'>)

Cite: Objects/typeobject.c — функция pmerge() реализует merge step-by-step, mro_implementation() оборачивает recursive call.

Three constraints — local precedence, monotonicity, EPG consistency

Давайте проверим, что [D, B, C, A, object] удовлетворяет все три constraints:

Local precedence: D(B, C) — direct bases в порядке B, C. В MRO B идёт перед C. ✓

Monotonicity: B идёт раньше A в B.__mro__ = [B, A, object]. В D.__mro__ = [D, B, C, A, object] B тоже раньше A. ✓ (То же для C раньше A.)

EPG consistency: каждый родитель идёт раньше своих собственных родителей.

• D (потомок) раньше B, C — ✓.
• B раньше A — ✓.
• C раньше A — ✓.
• A раньше object — ✓.

Все три выполнены. [D, B, C, A, object] — единственный порядок, удовлетворяющий все одновременно.

Big-O analysis: complexity of C3 merge

Merge перебирает на каждом шаге головы всех списков. Если C3 строится для класса с n базовыми и каждый список длиной m, то:

• На каждом шаге проверка одной head’ы: O(n·m) (проверить, что head не в tail каждого списка).
• Шагов всего: O(n·m) (каждый шаг удаляет один элемент).
• Total: O(n²·m²).

Для diamond с 4 классами это ничтожно (constants), но для больших иерархий (Django ORM, SQLAlchemy declarative — иногда ~50 базовых классов) — measurable. CPython делает caching tp_mro один раз при создании класса; lookup obj.attr потом — это просто tuple iteration, O(depth) где depth = длина MRO.

Per D-07 (Phase 64 carrying decision): квадратичная сложность C3 merge — implementation detail, irrelevant для production (один раз, на class definition). Atribute lookup — линейный по MRO.

TypeError: невозможная linearization (real example)

Не каждая комбинация классов имеет valid C3 linearization. Если local precedence двух родителей противоречит друг другу, merge не может выбрать good head на каком-то шаге → TypeError:

class X: pass
class Y: pass

# Z имеет X раньше Y, W имеет Y раньше X — конфликт:
class Z(X, Y): pass
class W(Y, X): pass

# Попытка унаследовать оба:
class Bad(Z, W): pass

TypeError: Cannot create a consistent method resolution order (MRO) for bases X, Y

Что произошло? Merge вычисляет:

L[Bad] = Bad + merge(L[Z], L[W], [Z, W])
       = Bad + merge([Z, X, Y, object], [W, Y, X, object], [Z, W])

После выбора Z и W:

merge([X, Y, object], [Y, X, object], [])

• Head X — в tail второго [Y, X, object]. Не good.
• Head Y — в tail первого [X, Y, object]. Не good.
• Никакой head не good → TypeError.

Это нарушение monotonicity: Z требует X раньше Y, W требует Y раньше X — несовместимо. Python отказывается строить arbitrary порядок и явно сигнализирует о проектной ошибке в иерархии.

Cite: Objects/typeobject.c — set_mro_error() raise’ит TypeError при невозможной linearization.

super() proxy chain через class cell + tp_mro traversal

super() — не просто «обращение к родителю». Это proxy объект, который продолжает MRO traversal после текущего класса. В diamond это критично:

class A:
    def hello(self): return "A.hello"

class B(A):
    def hello(self): return super().hello() + " + B.hello"

class C(B):
    def hello(self): return super().hello() + " + C.hello"

c = C()
print(c.hello())
# "A.hello + B.hello + C.hello"

Что делает super() без аргументов в B.hello:

1. Через __class__ cell (см. M03 урок про closures) находит containing class — B.
2. Через Py_TYPE(self).__mro__ находит position of B в MRO c-объекта.
3. Возвращает proxy, который при attribute lookup пропускает B и идёт дальше по MRO.

# Эквивалентно (старый Python 2 стиль):
class B(A):
    def hello(self):
        return super(B, self).hello() + " + B.hello"
        # super(B, self) - explicit form: skip B in self's MRO, return next class

В Python 3.0+ компилятор автоматически добавляет __class__ cell в любой метод, использующий super() без аргументов (см. PEP 3135). Это та самая cell, что хранит ссылку на enclosing class — closure over the class itself.

Cite: Objects/typeobject.c — super_init_without_args(); Python/compile.c — компиляция __class__ cell; PEP 3135.

super() в diamond — какой parent?

Critical: в diamond D(B, C), super() из B.hello не вызывает A.hello напрямую, а вызывает next в MRO — а это C.hello!

class A:
    def hello(self): return "A"

class B(A):
    def hello(self): return super().hello() + " + B"

class C(A):
    def hello(self): return super().hello() + " + C"

class D(B, C): pass

print(D.__mro__)
# (D, B, C, A, object)

d = D()
print(d.hello())
# "A + C + B"  (НЕ "A + B + A + C", как было бы при naive double-inheritance)

super() в B.hello (когда self — instance D) идёт по MRO D: после B следующий — C. Поэтому B.hello → C.hello → A.hello → “A + C + B” reading bottom-up. Это cooperative multiple inheritance — каждый класс в diamond вызывает super(), и MRO гарантирует, что A.hello будет вызван ровно один раз, а не два.

Cross-course context

Cross-course → Spark: 02/03 optimization-rules — C3 linearization строит детерминированный порядок resolution из графа inheritance; Catalyst optimizer аналогично применяет rules в детерминированном порядке (Batch’и + fixed-point iteration). Те же три constraint’а действуют по разному: MRO гарантирует local precedence + monotonicity для attribute lookup; Catalyst — что rule application converges к canonical plan. Оба — graph linearization для resolution, не tree-traversal.

Ключевые выводы

1. MRO — детерминированный кортеж в cls.__mro__ / tp_mro. Вычисляется один раз при создании класса через C3 linearization (Barrett et al., OOPSLA 1996), кэшируется в tp_mro.
2. C3 algorithm: рекурсивный merge с правилом good head — head, не появляющийся в tail других списков. Если никакой head не good → невозможная linearization → TypeError.
3. Три constraints: local precedence (порядок baseses сохраняется), monotonicity (порядок не переворачивается в subclass), EPG consistency (родитель раньше своих родителей). Все три выполнены C3 одновременно.
4. Diamond D(B, C) с B(A), C(A): D.__mro__ = (D, B, C, A, object). Step-by-step merge: B → C → A → object. См. диаграмму — четыре итерации с tail-conflict checking.
5. TypeError MRO — не bug, а defense: Python отказывается строить arbitrary порядок при противоречии local precedence (например, class Z(X,Y) + class W(Y,X) + class Bad(Z,W)).
6. super() proxy через __class__ cell + tp_mro traversal: continues MRO после текущего класса. В diamond super() из B может вызвать C (не A!), потому что C — next в MRO. Это cooperative multiple inheritance.
7. Big-O: C3 merge — O(n²·m²), irrelevant for production (один раз при class creation). Attribute lookup потом — O(depth_MRO), обычно ≤ 5-7.

В уроке M04-04 разберём дескрипторы: что под капотом у @property, @classmethod, @staticmethod, и почему data descriptor > instance __dict__ > non-data descriptor — fundamental правило lookup precedence.