Linéarisation C3

En programmation informatique, et plus précisément en programmation objet, la linéarisation de la superclasse C3 est un algorithme utilisé principalement pour obtenir l'ordre dans lequel les méthodes doivent être héritées en présence d'un héritage multiple. En d'autres termes, la sortie de la linéarisation de la superclasse C3 est un ordre de résolution de méthode (MRO pour Method Resolution Order en anglais) déterministe.

Explication de la terminologie

La linéarisation de la superclasse C3 est appelée C3 car elle « est cohérente avec trois propriétés » :

un graphe de précédence étendue cohérent^[Quoi ?],
la préservation de l'ordre de préséance local^[Quoi ?], et
appliquant un critère de monotonie^[Lequel ?].

Histoire

Publication en 1996

La linéarisation de la superclasse C3 a été publié pour la première fois lors de la conférence OOPSLA de 1996, dans un article intitulé A Monotonic Superclass Linearization for Dylan, où Dylan est un langage de programmation qui permet la programmation objet. Dans cet article, il est écrit :

« Dans les systèmes orientés objet avec héritage multiple, un mécanisme doit être utilisé pour résoudre les conflits lors de l'héritage de différentes définitions de la même propriété à partir de plusieurs superclasses. »

Adoption dans différents langages

Il a été adapté à l'implémentation d'Open Dylan en janvier 2012 à la suite d'une proposition d'amélioration. Il a été choisi comme algorithme par défaut pour la résolution de méthode dans Python 2.3 (et versions ultérieures)^,, Raku, Parrot, Solidity et le module de programmation orientée objet de PGF/TikZ . Il est également disponible en tant que MRO alternatif, non par défaut, dans le cœur de Perl 5 à partir de la version 5.10.0. Une implémentation d'extension pour les versions antérieures de Perl 5 nommée Class::C3 existe sur CPAN .

Guido van Rossum de Python résume ainsi la linéarisation de la superclasse C3 :

« Fondamentalement, l'idée derrière C3 est que si vous écrivez toutes les règles d'ordonnancement imposées par les relations d'héritage dans une hiérarchie de classes complexe, l'algorithme déterminera un ordonnancement monotone des classes qui les satisfait toutes. Si un tel ordre ne peut être déterminé, l'algorithme échouera. »

Description

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 dans un graphe orienté acyclique^{[réf. nécessaire]}.

Exemple

Dans cette section, nous allons considérer le graphe de dépendance dans la figure de droite. Les sommets Z, K1, K2, K3, A, B, C, D, E, O sont des classes. Dans la figure, il y a une flèche, lorsqu'une classe hérite d'une autre. Par exemple, la flèche Z → K1 indique que la classe Z hérite de K1. Il y a de l'héritage multiple : par exemple Z hérite de K1, K2 et K3.