Почему классы заказываются таким образом в MRO?

Question

У меня проблема с Python MRO Для этого кода:

class F: pass 
class G: pass 
class H: pass
class E(G,H): pass
class D(E,F): pass 
class C(E,G): pass
class B(C,H): pass
class A(D,B,E): pass

print(A.__mro__)

Я получаю этот вывод:

(<class '__main__.A'>, <class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.E'>, <class '__main__.G'>, <class '__main__.H'>, <class '__main__.F'>, <class 'object'>)

Почему я получаю <class '__main__.C'> до <class '__main__.E'>?

Я думал, что это будет:

1. A
2. D,B,E
3. E,F | C,H | G,H

и так далее

Answer 1

Короче потому что C зависит от E как вы можете видеть на графике зависимостей (O object ):

Порядок разрешения методов Python (MRO) работает с ограничением на то, что если класс a является зависимостью класса b, он помещается в очередь позже, чем b.

Теперь подробнее к теории:

В Python MRO работает со следующим правилом линеаризации:

L [ C(B1 ... Bn) ] = C + объединить (L [ B1 ]... L [ Bn ], B1 ... Bn ); а также

L [ object ] = object

(источник)

И объединение определяется как:

возглавить первый список, то есть L [ B1 ] [0]; если этот заголовок не находится в хвосте любого из других списков, то добавьте его к линеаризации C и удалите его из списков в слиянии, в противном случае посмотрите на заголовок следующего списка и возьмите его, если это хорошая голова Затем повторяйте операцию, пока все классы не будут удалены или невозможно найти хорошие головы. В этом случае невозможно построить слияние, Python 2.3 откажется от создания класса C и вызовет исключение.

(источник)

Итак, для вашего случая это первый шаг:

L [ A знак равно A + объединить (L [ D ], L [ B ], L [ E ])

Давайте сначала разрешим рекурсивные вызовы:

L [ D знак равно D + объединить (L [ E ], L [ F ]);
L [ B знак равно B + объединить (L [ C ], L [ H ]); а также
L [ E знак равно E + объединить (L [ G ], L [ H ]).

И больше рекурсии (мы делаем только H один раз и не повторяй E):

L [ F знак равно F + объединить (L [ O ]);
L [ C знак равно C + объединить (L [ E ], L [ G ]);
L [ G знак равно G + объединить (L [ O ]); а также
L [ H знак равно H + объединить (L [ O ]).

Поскольку L [ O ] является O и слить (а) (для одного объекта является) мы, таким образом, уже получили последовательность для H, G а также F:

L [ H знак равно H , O )
L [ G знак равно G , O )
L [ F знак равно F , O )

Теперь мы можем вычислить L [ E ]:

L [ E знак равно E + объединить (( G , O ), ( H , O )).

поскольку O для обоих в хвосте, он ставится последним:

L [ E знак равно E , G , H , O )

Теперь мы можем вычислить L [ C ]:

L [ C знак равно C + объединить (( E , G , H , O ), ( G , O ));
L [ C знак равно C , E ) + объединить (( G , H , O ), ( G , O ));
L [ C знак равно C , E , G ) + объединить (( H , O ), ( O ));
L [ C знак равно C , E , G , H ) + объединить (( O ), ( O ));
* L [ C знак равно C, E, G, H, O).

И L [ D ]:

L [ D знак равно D + объединить (( E , G , H , O ), ( F , O ));
..;
L [ D знак равно D , E , G , H , F , O )

Следующая L [ B ] может быть полностью решена:

L [ B знак равно B + объединить (( C , E , G , H , O ), ( H , O ));
..;
L [ B знак равно B , C , E , G , H , O )

И теперь мы можем наконец решить:

L [ A знак равно A + объединить (( D , E , G , H , F , O ), ( B , C , E , G , H , O ), ( E , G , H , O ));
L [ A знак равно A , D ) + объединить (( E , G , H , F , O ), ( B , C , E , G , H , O ), ( E , G , H , O ));
L [ A знак равно A , D , B ) + объединить (( E , G , H , F , O ), ( C, E, G, H, O), (E, G, H, O));
L [ A знак равно A , D , B , C ) + объединить (( E , G , H , F , O ), ( E , G , H , O ), ( E , G , H , O ));
L [ A знак равно A , D , B , C , E ) + объединить (( G , H , F , O ), ( G , H , O ), ( G , H , O ));
L [ A знак равно A , D , B , C , E , G ) + объединить (( H , F , O ), ( H , O ), ( H , O ));
L [ A знак равно A , D , B , C , E , G , H ) + объединить (( F , O ), ( O ), ( O ));
L [ A знак равно A , D , B , C , E , G , H , F ) + объединить (( O ), ( O ), ( O ));
L [ A знак равно A , D , B , C , E , G , H , F , O )

Что является ожидаемым поведением.

Неэффективная функция слияния, которую я сделал, может использоваться в образовательных целях, она определенно не оптимизирована для производства:

def mro_merge(*args):
    for i,arg in enumerate(args):
        if len(arg) > 0:
            head = arg[0]
            for argb in args:
                if head in argb[1:]:
                    break
            else:
                newargs = tuple(argb if len(argb) > 0 and argb[0] != head else argb[1:] for argb in args)
                print('mro_merge(%s) = %s + mro_merge(%s)'%(args,head,newargs))
                yield head
                for x in mro_merge(*newargs):
                    yield x
                break

И когда вы называете это, он генерирует:

>>> list(mro_merge(('G','O'),('H','O')))
mro_merge((('G', 'O'), ('H', 'O'))) = G + mro_merge((('O',), ('H', 'O')))
mro_merge((('O',), ('H', 'O'))) = H + mro_merge((('O',), ('O',)))
mro_merge((('O',), ('O',))) = O + mro_merge(((), ()))
['G', 'H', 'O']
>>> list(mro_merge( ('D','E','G','H','F','O') , ('B','C','E','G','H','O') , ('E','G','H','O') ))
mro_merge((('D', 'E', 'G', 'H', 'F', 'O'), ('B', 'C', 'E', 'G', 'H', 'O'), ('E', 'G', 'H', 'O'))) = D + mro_merge((('E', 'G', 'H', 'F', 'O'), ('B', 'C', 'E', 'G', 'H', 'O'), ('E', 'G', 'H', 'O')))
mro_merge((('E', 'G', 'H', 'F', 'O'), ('B', 'C', 'E', 'G', 'H', 'O'), ('E', 'G', 'H', 'O'))) = B + mro_merge((('E', 'G', 'H', 'F', 'O'), ('C', 'E', 'G', 'H', 'O'), ('E', 'G', 'H', 'O')))
mro_merge((('E', 'G', 'H', 'F', 'O'), ('C', 'E', 'G', 'H', 'O'), ('E', 'G', 'H', 'O'))) = C + mro_merge((('E', 'G', 'H', 'F', 'O'), ('E', 'G', 'H', 'O'), ('E', 'G', 'H', 'O')))
mro_merge((('E', 'G', 'H', 'F', 'O'), ('E', 'G', 'H', 'O'), ('E', 'G', 'H', 'O'))) = E + mro_merge((('G', 'H', 'F', 'O'), ('G', 'H', 'O'), ('G', 'H', 'O')))
mro_merge((('G', 'H', 'F', 'O'), ('G', 'H', 'O'), ('G', 'H', 'O'))) = G + mro_merge((('H', 'F', 'O'), ('H', 'O'), ('H', 'O')))
mro_merge((('H', 'F', 'O'), ('H', 'O'), ('H', 'O'))) = H + mro_merge((('F', 'O'), ('O',), ('O',)))
mro_merge((('F', 'O'), ('O',), ('O',))) = F + mro_merge((('O',), ('O',), ('O',)))
mro_merge((('O',), ('O',), ('O',))) = O + mro_merge(((), (), ()))
['D', 'B', 'C', 'E', 'G', 'H', 'F', 'O']