Принцип работы C3 хорошо задокументирован здесь . Но мы можем проработать его для вашего конкретного примера, чтобы понять, почему вы получаете результат, который вы делаете.
Алгоритм линеаризации не слишком сложен для понимания. Он состоит из двух рекурсивных частей. Открытый интерфейс, который я назову mro (в приведенном выше документе используется L[x] вместо mro(x), но я буду придерживаться синтаксиса Python-ish). Другая часть - вспомогательная функция с именем merge.
Функция mro очень проста для понимания. Он возвращает [object] в базовом случае, когда он вызывается для типа object, или сначала возвращает список с аргументом, за которым следуют значения, возвращаемые merge, вызываемые для mro всех Основы его аргументации. Вот быстрая и грязная реализация в Python:
def mro(cls):
if cls is object:
return [object]
return [cls] + merge([mro(base) for base in cls.__bases__])
Слияние немного сложнее. Его аргументом является список списков, каждый из которых является mro базового класса. Если есть только один список, результат merge действительно прост (это тот же список). Это единственный случай наследования. Но для такого поведения не требуется никакого специального кода, который возникнет из алгоритма. Алгоритм говорит сканировать списки, которые вы передали, чтобы найти первое действительное значение, которое нужно вставить в результат mro. Допустимое значение - это значение, которое появляется только в начале списка аргументов, в котором оно находится, и никогда не углубляется в список. Когда у вас есть действительное значение, вы ставите его во главу списка результатов, а затем повторяете все остальные списки (исключая только что извлеченное значение).
Вот реализация этого на Python:
def merge(mros):
if not any(mros): # all lists are empty
return [] # base case
for candidate, *_ in mros:
if all(candidate not in tail for _, *tail in mros):
return [candidate] + merge([tail if head is candidate else [head, *tail]
for head, *tail in mros])
else:
raise TypeError("No legal mro")
Понимание списка для создания аргумента списка списков для merge немного сложно. Он просто удаляет ссылки на candidate, которые появляются в начале списков, и удаляет все списки, которые впоследствии оказываются пустыми (чтобы мы могли знать, когда прекратить повторение).
В любом случае, давайте посмотрим, как эти функции обрабатывают вашу иерархию классов, когда вы вызываете mro(H).
Первый вызов mro(H), который запускает общий случай кода функции mro. Это приводит к трем рекурсивным вызовам, чтобы получить mro с E, F и G. Надеюсь, это вас не смущает, так как я не хочу в них углубляться (поскольку часть алгоритма, вызывающая странность, о которой вы спрашиваете, появится позже). Поэтому после разрешения этих рекурсивных вызовов mro мы вызываем merge для получения результатов. Это как наш стек вызовов:
mro(H)->
return [H] + merge([[E, B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
Код merge теперь выполняется. Первый проверяемый кандидат - E, и он действителен, поскольку E не появляется нигде, кроме как в начале списка. Таким образом, он удаляет E и рекурсивно. Новый стек вызовов:
mro(H)->
[H] + merge([[E, B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[E, ...], [F, ...], [G, ...]]) ->
[E] + merge([[B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
При следующем запуске он сначала пытается B в качестве кандидата, но это не очень хорошо, так как он появляется вторым во втором списке. Итак, он пытается F, который действителен:
mro(H)->
[H] + merge([[E, B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[E, ...], [F, ...], [G, ...]]) ->
[E] + merge([[B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[B, ...], [F, ...], [G, ...]]) ->
[F] + merge([[B, C, A, object], [B, D, A, object], [G, C, D, A, object]])
Этот следующий звонок интересен для вашего вопроса. Первый кандидат, который будет проверен в коде merge, - B, поскольку он является главой первого списка. На этот раз он действителен, поскольку он также является главой второго списка (а не хвостом, как в прошлый раз) и вообще не входит в третий список. Так что это результат, который был удален до рекурсии, а не G (как вы, вероятно, ожидали).
mro(H)->
[H] + merge([[E, B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[E, ...], [F, ...], [G, ...]]) ->
[E] + merge([[B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[B, ...], [F, ...], [G, ...]]) ->
[F] + merge([[B, C, A, object], [B, D, A, object], [G, C, D, A, object]])
merge([[B, ...], [B, ...], [G, ...]]) ->
[B] + merge([[C, A, object], [D, A, object], [G, C, D, A, object]])
Отсюда все довольно просто, так как значения в третьем списке будут в конечном итоге удалены один за другим (с теми, которые в более ранних списках, также будут происходить одновременно). Я просто покажу стек вызовов, а не буду комментировать каждый из них:
mro(H)->
[H] + merge([[E, B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[E, ...], [F, ...], [G, ...]]) ->
[E] + merge([[B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[B, ...], [F, ...], [G, ...]]) ->
[F] + merge([[B, C, A, object], [B, D, A, object], [G, C, D, A, object]])
merge([[B, ...], [B, ...], [G, ...]]) ->
[B] + merge([[C, A, object], [D, A, object], [G, C, D, A, object]])
merge([[C, ...], [D, ...], [G, ...]]) ->
[G] + merge([[C, A, object], [D, A, object], [C, D, A, object]])
merge([[C, ...], [D, ...], [C, ...]]) ->
[C] + merge([[A, object], [D, A, object], [D, A, object]])
merge([[A, ...], [D, ...], [D, ...]]) ->
[D] + merge([[A, object], [A, object], [A, object]])
merge([[A, object], [A, object], [A, object]]) ->
[A] + merge([[object], [object], [object]])
merge([[object], [object], [object]]) ->
[object] + merge([])
merge([]) ->
[] # base case