Linéarisation C3

La linéarisation de la superclasse C3 d'une classe est la somme de la classe plus une fusion unique des linéarisations de ses parents et une liste des parents elle-même. La liste des parents comme dernier argument du processus de fusion préserve l'ordre de priorité local des classes parentes directes.

La fusion des linéarisations des parents et de la liste des parents se fait en sélectionnant la première tête des listes qui n'apparaît pas dans la queue (tous les éléments d'une liste sauf le premier) d'aucune des listes. Notez qu'une bonne tête peut apparaître comme premier élément dans plusieurs listes en même temps, mais il est interdit d'apparaître ailleurs. L'élément sélectionné est supprimé de toutes les listes où il apparaît en tant qu'en-tête et ajouté à la liste de sortie. Le processus de sélection et de suppression d'une bonne tête pour étendre la liste de sortie est répété jusqu'à ce que toutes les listes restantes soient épuisées. Si, à un moment donné, aucune bonne tête ne peut être sélectionnée, car les têtes de toutes les listes restantes apparaissent dans n'importe quelle queue des listes, la fusion est alors impossible à calculer en raison d'ordres incohérents de dépendances dans la hiérarchie d'héritage et de l'absence de linéarisation de l'original. classe existe.

Une approche naïve de division pour régner pour calculer la linéarisation d'une classe peut invoquer l'algorithme de manière récursive pour trouver les linéarisations des classes parentes pour le sous-programme de fusion. Cependant, cela se traduira par une récursivité en boucle infinie en présence d'une hiérarchie de classes cyclique. Pour détecter un tel cycle et casser la récursivité infinie (et réutiliser les résultats des calculs précédents comme optimisation), l'invocation récursive doit être protégée contre la ré-entrée d'un argument précédent au moyen d'un cache ou d'une mémorisation .

Cet algorithme est similaire à la recherche d'un ordre topologique .

Exemple

Donné

Un graphique de dépendance pour l'exemple de linéarisation C3.

Modèle:SxhlModèle:Sxhlla linéarisation de Z est calculée commeModèle:SxhlModèle:Sxhl

class Type(type):
    def __repr__(cls):
        return cls.__name__
class O(object, metaclass=Type): pass

class A(O): pass
class B(O): pass
class C(O): pass
class D(O): pass
class E(O): pass
class K1(C, A, B): pass
class K3(A, D): pass
class K2(B, D, E): pass
class Z(K1, K3, K2): pass

>>> Z.mro()
[Z, K1, C, K3, A, K2, B, D, E, O, <class 'object'>]

class A {}
class B {}
class C {}
class D {}
class E {}
class K1 is C is A is B {}
class K3 is A is D {}
class K2 is B is D is E {}
class Z is K1 is K3 is K2 {}
say Z.^mro; # OUTPUT: ((Z) (K1) (C) (K3) (A) (K2) (B) (D) (E) (Any) (Mu))