¿Por qué las clases se ordenan de esta manera en el MRO?

Tengo un problema con el MRO de Python para este código:

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__) 

Obtengo esta salida:

(, , , , , , , , )

¿Por qué recibo antes de ?

Pensé que sería:

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

y así

En resumen, porque C depende de E como se puede ver en el gráfico de dependencias (O es object ) :

introduzca la descripción de la imagen aquí

El orden de resolución de métodos (MRO) de Python funciona con la restricción de que si una clase a es una dependencia de una clase b , se coloca más adelante en la cola que b .

Ahora más a la teoría:

En Python, el MRO funciona con la siguiente regla de linealización :

L [ C(B1 ... Bn) ] = C + fusionar (L [ B1 ] … L [ Bn ], B1Bn ) ; y

L [ object ] = object

(fuente)

Y la fusión se define como:

tomar el encabezado de la primera lista, es decir, L [ B1 ] [0] ; Si este encabezado no está en la cola de ninguna de las otras listas, entonces agréguelo a la linealización de C y elimínelo de las listas en la combinación. De lo contrario, mire el encabezado de la siguiente lista y tómelo, si es un buena cabeza. Luego repita la operación hasta que se eliminen todas las clases o sea imposible encontrar buenos jefes. En este caso, es imposible construir la combinación, Python 2.3 se negará a crear la clase C y generará una excepción.

(fuente)

Entonces, para tu caso, el primer paso es:

L [ A ] = A + fusionar (L [ D ], L [ B ], L [ E ])

Primero resolvamos las llamadas recursivas:

L [ D ] = D + fusionar (L [ E ], L [ F ]) ;
L [ B ] = B + fusionar (L [ C ], L [ H ]) ; y
L [ E ] = E + fusionar (L [ G ], L [ H ]) .

Y más recursión (solo hacemos H una vez y no rehacemos E ):

L [ F ] = F + fusionar (L [ O ]) ;
L [ C ] = C + fusionar (L [ E ], L [ G ]) ;
L [ G ] = G + fusionar (L [ O ]) ; y
L [ H ] = H + fusionar (L [ O ]) .

Como L [ O ] es O y fusiona (a) (para un objeto es a ), por lo tanto, ya hemos obtenido la secuencia para H , G y F :

L [ H ] = ( H , O ) .
L [ G ] = ( G , O ) .
L [ F ] = ( F , O ) .

Ahora podemos calcular L [ E ] :

L [ E ] = E + fusionar (( G , O ), ( H , O )) .

Dado que O es para ambos en la cola, se coloca en último lugar:

L [ E ] = ( E , G , H , O ) .

Ahora podemos calcular L [ C ] :

L [ C ] = C + fusionar (( E , G , H , O ), ( G , O )) ;
L [ C ] = ( C , E ) + combinación (( G , H , O ), ( G , O )) ;
L [ C ] = ( C , E , G ) + combinación (( H , O ), ( O )) ;
L [ C ] = ( C , E , G , H ) + combinación (( O ), ( O )) ;
* L [ C ] = ( C , E , G , H , O ).

Y L [ D ] :

L [ D ] = D + fusionar (( E , G , H , O ), ( F , O )) ;
..;
L [ D ] = ( D , E , G , H , F , O ) .

Siguiente L [ B ] se puede resolver completamente:

L [ B ] = B + fusionar (( C , E , G , H , O ), ( H , O )) ;
..;
L [ B ] = ( B , C , E , G , H , O ) .

Y ahora podemos resolver finalmente:

L [ A ] = A + fusionar (( D , E , G , H , F , O ), ( B , C , E , G , H , O ), ( E , G , H , O )) ;
L [ A ] = ( A , D ) + combinación (( E , G , H , F , O ), ( B , C , E , G , H , O ), ( E , G , H , O )) ;
L [ A ] = ( A , D , B ) + combinación (( E , G , H , F , O ), ( C , E , G , H , O ), ( E , G , H , O )) ;
L [ A ] = ( A , D , B , C ) + combinación (( E , G , H , F , O ), ( E , G , H , O ), ( E , G , H , O )) ;
L [ A ] = ( A , D , B , C , E ) + combinación (( G , H , F , O ), ( G , H , O ), ( G , H , O )) ;
L [ A ] = ( A , D , B , C , E , G ) + fusión (( H , F , O ), ( H , O ), ( H , O )) ;
L [ A ] = ( A , D , B , C , E , G , H ) + combinación (( F , O ), ( O ), ( O )) ;
L [ A ] = ( A , D , B , C , E , G , H , F ) + combinación (( O ), ( O ), ( O )) ;
L [ A ] = ( A , D , B , C , E , G , H , F , O ) .

Cual es el comportamiento esperado.

Una función de fusión no eficiente que he hecho se puede usar para fines educativos, definitivamente no está optimizada para la producción:

 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 

Y cuando lo llamas, se genera:

 >>> 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']