MRO - Method Resolution Order

Linearizzazione del DAG delle superclassi

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

flowchart LR
	A --> D
	B --> E
	C --> A 
	C --> D 
	C --> B
	E --> object
	D --> object

Usando la funzione mro() su una di queste sottoclassi, come ad esempio C, viene restituita un array come il seguente:

[<class '__main__.C'>, <class '__main__.A'>, <class '__main__.D'>, <class '__main__.B'>, <class '__main__.E'>, <class 'object'>]

Quindi per la ricerca degli attributi, il grafo è stato linearizzato come segue: [C, A, D, B, E, object].

ATTENZIONE

Non tutti i DAG possono essere linearizzati!

class B: pass
class A(object, B): pass

Genera errore, in quanto entrambe le classi, A e B puntano a object, e si verrebbe a creare un grafo del genere:

flowchart LR
	B --> object
	A --> object
	A --> B

Linearizzazione

In generale viene usato un metodo depth-first/left-to-right del DAG per risolverla.

Monotonicità

Se $C_{1}$ precede $C_{2}$ nella linearizzazione di C, allora questo avverrà per la linearizzazione di tutte le sottoclassi di C.

Precedenza locale

L’ordine delle classi base della definizione di una classe, è preservato nella linearizzazione delle sottoclassi.

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

Le classi qui sopra si possono visualizzare meglio con un grafico:

graph BT
    A --> B
    A --> E
    A --> H
    B --> C
    C --> D
    E --> F
    F --> G
    H --> I
    I --> J
    D --> object
    G --> object
    J --> object

Algoritmo di linearizzazione

Terminologia:

$G_{S}$ grafo costituito da tutti e soli i vertici raggiungibili da S
$L (S)$ linearizzazione di $G_{S}$ , rappresentata come una lista
$L (H) = S B_{1} B_{2} ... B_{k}$ linearizzazione di un generico $G_{h}$ , con $H$ testa e $B_{1} B_{2} ... B_{k}$ coda della linearizzazione

Se $S = o bj ec t$ la linearizzazione è composta da object. $L (o bj ec t) = o bj ec t$ passo base della ricorsione. S è la classe sulla quale si linearizza, e $B_{1} B_{2} ... B_{k}$ sono le classi base di S.
Si suppone che ricorsivamente siano già stati linearizzati i grafi delle classi base e le liste si indicano con $L_{1} L_{2} ... L_{k}$ .
Oltre a quelle liste si considera sempre un’altra lista delle classi base della classe che stiamo considerando, $B_{1} B_{2} ... B_{k}$
Una volta che si hanno tutte le liste, si fa il merge di queste $k + 1$ liste.
1. Si inizializza la lista $L (S) = S$
2. Le liste vengono analizzate da sinistra a destra un elemento alla volta. Per ogni elemento si possono eseguire due azioni:
  1. $x$ viene inserito in fondo alla lista $L (S)$ .
    - Se non compare nella coda di nessuna lista $L_{j}$ con $l > i$ , $x$ , viene rimosso da tutte le liste, con indice maggiore della lista $L_{i}$ che stiamo valutando ( $L_{j}, j > i$ ), che lo contengono.
    - Si ricomincia il processo con la testa della prima lista non vuota tra quelle rimaste.
    - Se sono tutte vuote l’algoritmo termina con successo.
  2. $x$ viene temporaneamente scartato.
    - Se $x$ compare nella coda di una lista $L_{j}$ con $j > i$ , viene scartato perchè viola la regola di monotonicità, dal momento che dovrebbe essere dopo $L_{j} [0]$ . Per la stessa ragione non si possono inserire tutti i restanti elementi di $L_{i}$ .
    - Si cerca quindi la testa della prima lista non vuota di indice $j > i$ che non sia un elemento scartato. Se si arriva in fondo alle liste senza trovare un elemento inseribile la linearizzazione fallisce.

Esempio

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

$A \neq = o bj ec t$
$L_{1} = B D EO, L_{2} = C D FO$
$B_{1} = BC$
1. $L (A) = A$
2. Si esegue il merge
  - B non compare in nessun’altra lista, quindi $L (A) = A B$ , $L_{1} = D EO$ e $B_{1} = C$
  - D compare nella coda di $L_{2}$ , quindi bisogna passare a valutare la testa di $L_{2}$
  - C non compare in nessun’altra lista, quindi $L (A) = A BC$ , $L_{2} = D FO$ e $B_{1} = []$
  - Ripartendo dalla prima lista, si ha D, che è in testa a tutte le liste, e quindi $L (A) = A BC D$ , $L_{1} = EO$ e $L_{2} = FO$
  - E compare solo in $L_{1}$ , quindi $L (A) = A BC D E$ e $L_{1} = O$
  - O compare anche in $L_{2}$ , quindi si inserisce F e si ha $L (A) = A BC D EF$ , $L_{1} = O$ e $L_{2} = O$
  - Si finisce con $L (A) = A BC D EFO$ e tutte le altre listevuote.

title: Attenzione
La lista $B_i$ serve a evitare violazioni della regola di precedenza locale.
 
`class C: pass`
`class B(C): pass`
`class A(C, B): pass`
 
Avendo liste $CO$, $BCO$ e $CB$, si ha che il grafo non è linearizzabile.

python_book3

🧬 Gianipero

Explorer

MRO