Tutoriel architectural sur le patron de conception visiteur par injection (ou Visitor Injector)

Comment contourner le caractère statique du patron Visiteur du Gang of Four

L'inconvénient du design pattern Visitor est qu'il fige la structure des classes à visiter. En effet, comme le visiteur implémente une méthode spécifique à chaque classe à visiter (chaque type), si une classe devait être ajoutée à posteriori, la classe Visitor devrait être surclassée, engendrant des tests de types et des transtypages. Je vous propose le design pattern Visitor Injector qui a pour but de résoudre cet aspect par injection de dépendances (disons plutôt par une approche fonctionnelle/comportementale du problème). Cette modification du patron original peut être utilisée chaque fois qu'un patron visiteur est utile et prend tout son sens dans le développement de librairies flexibles. Suivez le guide, et n'hésitez pas à me faire vos remarques. 2 commentaires Donner une note à l'article (5) cet article sur dvp.

Article lu   fois.

L'auteur

Profil Pro

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Intention

Comme défini au travers du patron de conception Visitor par le Gang Of Four (retrouvez le libre ici), Visitor Injector permet de découpler un comportement d'une structure de données (généralement sous la forme d'un Composite).

Le visiteur permet de définir un nouveau comportement sans que la classe de l'objet qui agit ne soit altérée. Le patron Visitor Injector permet qu'un nouvel objet soit défini sans que la classe visitor ne soit à son tour modifiée.

Les injections de visiteurs définissent un comportement de façon dynamique. Ils sont associés par le type de l'objet ou sur tout autre critère.

Retrouvez les sources du projet d'exemple netbeans iciSources.

II. Motivation

Le but de ce pattern est d'étendre le pattern Visitor original en gardant à l'esprit la flexibilité de la librairie le contenant.

Considérons un compilateur représentant un programme sous la forme d'un Abstract Syntax Tree. Le patron Visitor original permet de définir le comportement des différents objets constituant l'AST de façon externe.

Si un objet est ajouté à la structure de l'AST, la classe du visiteur doit être modifiée en y ajoutant la nouvelle méthode associée à la nouvelle classe. Dans le cas où l'objet doit être ajouté dans une couche logicielle supérieure (en dehors de la librairie), le visiteur initial devra être surclassé. Un nouveau type héritant du visiteur sera défini dans lequel la nouvelle méthode sera implémentée. Comme la nouvelle méthode accept (voir le pattern Visitor original) est définie dans une sous-classe, son paramètre référençant le visiteur ne pourra pas avoir comme type la sous-classe, mais la super-classe. Cela implique que pour récupérer l'instance de la sous-classe, il sera nécessaire de transtyper le paramètre.

Visitor Injector contourne ce problème de transtypage par inversion de contrôle (ou plus précisément par une approche fonctionnelle du problème).

III. Applications

Le pattern Visitor Injector doit être employé partout où un visiteur est nécessaire et où la flexibilité est un aspect important.

En d'autres termes, là ou le principe d'ouverture / fermeture (OCP) doit être observé de façon à garantir le caractère extensible du programme.

En aparté, l'OCP est défini comme suit dans son texte original :  « OCP states that modules should be open for extension and closed for modification. New functionality should be implemented by adding new classes, attributes and methods, instead of changing the current ones. »

En outre, le patron Visitor Injector tient une place de choix dans les architectures en couches où le découplage est nécessaire.

IV. Structure

Le patron Visitor Injector est une extension du patron Visitor.

Image non disponible

Le diagramme de classes montre les modifications apportées au visitor original : une seule méthode « visite » est définie par visiteur et un objet VisitorInjector qui est en charge de déterminer quel visiteur associer à l'élément de la structure.

V. Participants

  • « MethodVisitor » : interface des visiteurs à injecter. Elle décrit le comportement que devraient avoir les éléments lors du second parcours.
  • « ConcretVisitor » : réalisation des visiteurs. Chaque visiteur est affecté à un « ConcretElement » par le « VisitorIntector ».
  • « VisitorInjector » est responsable de l'association entre un élément concret et son visiteur.

À noter que pour rendre configurable cette étape en Java, l'objet visitorInjector contient un dictionnaire ayant pour clé la classe de l'élément et pour valeur le visiteur lui correspondant (Map<Class, MethodVisitor>). Lors de l'identification du visiteur, le visiteur est renvoyé par le dictionnaire selon le type d'élément parcouru.

  • « Element » : super-classe des éléments de la structure arborescente. Dans le cas de JASI, c'est la super-classe AST.
  • « ConcreteElement » : élément concret de la structure ; dans le cas de JASI ils peuvent être des nombres, des opérateurs, des fonctions, etc.

VI. Collaboration

Un premier parcours en profondeur dans l'arbre est effectué. C'est la méthode inject (dans les classes éléments) qui en est responsable. Elle reçoit en paramètre un objet de type VisitorInjector qui est en charge de déterminer quel visiteur correspond à quel élément parcouru. Une fois le visiteur identifié, sa référence est stockée dans l'élément lui-même (sous forme d'un attribut privé nommé ici visitor).

Une fois cette étape d'injection effectuée, le second parcours en profondeur, celui de l'exécution, peut être exécuté. Lors de ce second parcours, la méthode visite de l'élément appelle la méthode de visite par la référence qui lui a été assignée : visitor.visite (this).

Image non disponible

VII. Conséquences

  • Séparation des responsabilités : comme le pattern visitor original, visitor injector permet de séparer la structure de l'arbre des éléments de leur implémentation.
  • L'ajout d'un nouvel élément à la structure déjà existante est simplifié et transparent. Le nouvel élément doit hériter de la super-classe Element, un nouveau visiteur réalisant l'interface MethodVisitor doit être ajouté et enregistré auprès d'objet VisitorInjector.

    Attention toutefois, la souplesse obtenue par ce nouveau modèle ne garantit plus que tous les visiteurs nécessaires à la structure de donnée ont bien été créés. Pour contourner ce problème il est nécessaire d'écrire un test unitaire qui s'assurera que chaque type (classe) de notre structure possède un visiteur associé.

  • Pas de perte de performance lors de l'exécution de la structure puisque l'injection s'effectue dans une phase préliminaire. Aucun test supplémentaire n'est nécessaire lors de l'exécution.
  • La décoration de visiteurs est simplifiée par cette architecture. En effet, dans le patron classique, il est nécessaire de décorer chaque méthode visitée, dans le cas présent on utilisera un décorateur fonctionnel (une peu comme les function decorators en Python). À cet effet, il faut définir un decorator au niveau de la classe MethodVisitor. C'est cette faculté qui a été utilisée lors de la création du débogueur et du mode d'exécution pas-à-pas d'Algoid.
  • L'architecture en couches est également simplifiée puisque de nouveaux visiteurs peuvent être définis indépendamment de la structure initiale. Une couche peut contenir une partie des éléments de la structure ainsi que les visiteurs associés et une autre peut contenir le reste des éléments et des visiteurs. Par exemple, lorsque j'ai développé le parseur et le langage, des AST génériques étaient définis dans la couche parseur (expression, binaryOperation, etc.) et des AST plus spécifiques (comme if, function, object, array, etc.) dans la couche du langage.
  • L'injection des visiteurs peut être effectuée sur d'autres critères que le type des éléments rencontrés. Dans le cadre du langage AL, une extension de ce pattern a été mise en place en ce sens.

Lors de la phase d'injection du langage AL, l'injection des opérations binaires et unaires se fait sur deux critères. D'abord effectuée sur la classe de ceux-ci, ici BinaryOperation ou UnaryOperation, puis effectuée sur le lexème opérateur (plus, moins, multiplié, divisé, modulo, etc.). De cette façon, seul l'AST BinaryOperation est défini, seuls les visiteurs correspondant à l'addition, la soustraction, etc. diffèrent. Cela permet de réduire la forte population de classes de l'AST. Une des problématiques identifiées dans le livre de Terence Parr sur la création d'analyseurs.

VIII. Implémentation

La super-classe Element (la super-classe de tous les objets de la structure à visiter) :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
public abstract class Element {
    /**
     * La référence de la méthode de visite correspondante
     */
    private MethodVisitor visitor;

    /**
     * Délègue le choix de la méthode de visite à l'injecteur
     * @param injector l'objet responsable du choix de la méthode de visite
     */
    public void injectVisitor(VisitorInjector injector) {
        visitor = injector.getVisitor(this);
    }

    public void visit() {
        this.visitor.visit(this);
    }
}

Les éléments terminaux concrets qui implémentent la classe Element :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
public class ConcreteElementA extends Element {

    @Override
    public void injectVisitor(VisitorInjector injector) {
        this.visitor = injector.getVisitor(this);
    }
}
public class ConcreteElementB extends Element {

    @Override
    public void injectVisitor(VisitorInjector injector) {
        this.visitor = injector.getVisitor(this);
    }
}

L'interface MethodVisitor :

 
Sélectionnez
1.
2.
3.
public interface MethodVisitor<E extends Element> {
    void visit(E e);
}

L'interface Injector :

 
Sélectionnez
1.
2.
3.
public interface VisitorInjector {
    public MethodVisitor getVisitor(Element e);
}

La classe réalisant l‘interface Injector. Une liste associative (Map dans le langage Java) a été préférée à un branchement impératif :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
public class VisitorInjectorClassMap implements VisitorInjector {

    private final Map<Class<? extends Element>, MethodVisitor> map;

    public VisitorInjectorClassMap() {
        map = new HashMap<Class<? extends Element>, MethodVisitor>();
    }

    /**
     * Indique quel visiteur correspond à quel type de class
     */
    public <E extends Element> void addMatch(final Class<E> clazz, final MethodVisitor<E> v) {
        map.put(clazz, v);
    }

    @Override
    public MethodVisitor getVisitor(Element e) {
        // cherche dans le dictionnaire
        MethodVisitor v = map.get(e.getClass());

        // si un visiteur n?existe pas
        if (v == null) throw new RuntimeException(
            "Undefined visitor for type " + e.getClass().getName());

        return v;
    }
}

Exemple d'utilisation

L'exemple suivant montre comment utiliser ce patron au travers d'une hiérarchie simple.

Voici la création de la hiérarchie visée :

 
Sélectionnez
1.
2.
3.
4.
5.
// Création des éléments du système
Element a1 = new ConcreteElementA("Element A.1");
Element a2 = new ConcreteElementA("Element A.2");
Element b1 = new ConcreteElementA("Element B.1");
Element b2 = new ConcreteElementA("Element B.2");

La création de l'injecteur :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
VisitorInjectorClassMap injector = new VisitorInjectorClassMap();
injector.addMatch(ConcreteElementA.class, new MethodVisitor<ConcreteElementA>() {

    @Override
    public void visit(ConcreteElementA e) {
        System.out.println("Je visite un élément de type A qui se nomme : " + e.getName());
    }
});

injector.addMatch(ConcreteElementB.class, new MethodVisitor<ConcreteElementB>() {

    @Override
    public void visit(ConcreteElementB e) {
        System.out.println("Et maintenant un élément de type B : " + e.getName());
    }
});

Et les séquences d'injection et d'exécution de la structure :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
// phase d'injection des visiteurs
a1.injectVisitor(injector);
a2.injectVisitor(injector);
b1.injectVisitor(injector);
b2.injectVisitor(injector);

// visite
a1.visit();
a2.visit();
b1.visit();
b2.visit();

IX. Patrons associés

J'ai imaginé ce patron à l'occasion de la réalisation de la librairie JASI (l'analyseur syntaxique) et du langage Algoid Language. Il permet de définir les primitives du langage et son API au travers des différentes couches logicielles. De plus il a permis, par l'adjonction d'un patron decorator de créer un débogueur et un mode d'exécution pas à pas.

IX-A. Composite

Les éléments peuvent faire partie d'un patron composite [GAMMA p.163]. Voir variante 1 en annexe.

L'injecteur peut être architecturé autour d'un Cela permet d'effectuer une injection sur plusieurs critères. Par exemple, un premier nœud d'injection se charge de déterminer les visiteurs par classe de la structure, et dans certains cas, un second se charge de déterminer les visiteurs par lexème. C'est le cas dans le langage AL que j'ai développé où les opérateurs binaires (plus, moins, multiplié et divisé) sont en réalité tous représentés par un AST de type BinaryOperation. L'injecteur se charge d'assigner le visiteur correspondant à l'opération réelle selon le mot clé utilisé dans le script. Voir variante 2 en annexe.

IX-B. Decorator

Le patron de conception decorator [GAMMA p.175] peut être utilisé pour décorer les visiteurs et en altérer le comportement. C'est ce qui a été mis en place pour le débogueur et le mode d'exécution pas à pas d'Algoid.

Ce patron simplifie l'utilisation du décorateur, puisque celui-ci ne devra surcharger qu'une méthode (visite()) de l'objet VisitorMethod. Dans le cas d'un visiteur classique ce sont toutes les méthodes visite correspondantes aux différents éléments concrets qui devront être surchargées.

IX-C. Interpreter

Dans le cas d'un AST, les éléments sont architecturés autour du design pattern Interpreter [GAMMA p.243].

IX-D. Flyweight

Lors de l'injection, afin d'éviter d'instancier de nouveaux visiteurs à chaque fois, il est possible d'utiliser un patron flyweight qui sera en charge du mapping.

X. Histoire du patron

J'ai personnellement découvert et utilisé ce patron lorsque j'ai écrit mon analyseur syntaxique nommé JASI (lequel a été utilisé pour réaliser le langage AL présenté à ma soutenance d'ingénieur).

JASI - signifie Java Abstract Syntax Interpreter - est un analyseur de type Packrat dont la particularité est issue de son architecture. Son principe réside, en quelques mots, dans la construction d'un « Parse Tree » directement dans le langage hôte (en l'occurrence Java) qui en fait un « Domain Specific Embeded Language » au même titre que JParsec. À ceci près que son architecture est orientée objet plutôt que fonctionnelle (arbre n-aire plutôt que binaire). L'idée fondamentale de ce nouveau parseur étant de permettre de déclarer (déclaratif vs impératif) une grammaire en manipulant des composites comportementaux (Patron Interpréteur du GoF) et des décorateurs.

La seconde idée était de rendre flexible la génération de l'AST et l'implémentation de celui-ci, c'est là qu'intervient le patron Visitor Injector.

JASI fera bientôt l'objet d'une mise à disposition en open source. Son modèle de construction AST étant à revoir au préalable.

XI. Annexes

XI-A. Variante 1 : Éléments composites

Le bloc architectural des éléments du modèle peut être remodelé de façon à créer un composite. Le patron VisitorInjector se prête très bien au parcours en profondeur d'un arbre ainsi obtenu :

Voici les différents éléments du composite :

 
Sélectionnez
public abstract class Component extends Element {

    private final String name;

    public Component(String name) {
        this.name = name;
    }

    public final String getName() {
        return name;
    }

}

public class Leaf extends Component {

    public Leaf(String name) {
        super(name);
    }

}

public class Composite extends Component implements Iterable<Component> {
    private final List<Component> children;

    public Composite(String name) {
        super(name);
        children = new ArrayList<Component>();
    }

    public final boolean addChild(Component e) {
        return children.add(e);
    }

    @Override
    public final Iterator<Component> iterator() {
        return children.iterator();
    }

    @Override
    public void injectVisitor(VisitorInjector injector) {
        super.injectVisitor(injector);

        /* Dans le cas d'un composite il est nécessaire de surcharger l'injection et de déléguer celle-ci à tous les enfants lors d'un parcours en profondeur !
        */
        for (Element c : children) {
            c.injectVisitor(injector);
        }
    }
}

Et leur utilisation :

 
Sélectionnez
VisitorInjectorClassMap injector = new VisitorInjectorClassMap();

injector.addMatch(Composite.class, new MethodVisitor<Composite>() {

    @Override
    public void visit(Composite e) {
        System.out.println("Je visite un noeud qui se nomme : " + e.getName());
        System.out.println("Et ses enfants : ");

        // merci le patron iterator
        for (Component c : e) {
            c.visit();
        }
    }
});

injector.addMatch(Leaf.class, new MethodVisitor<Leaf>() {

    @Override
    public void visit(Leaf e) {
        System.out.println("Je visite une feuille qui se nomme : " + e.getName());
    }
});


// crée le composite
Composite root = new Composite("root");
Leaf cmp10 = new Leaf("Leaf 1");
root.addChild(cmp10);

Composite cmp20 = new Composite("Node 2");
root.addChild(cmp20);
Leaf cmp21 = new Leaf("Leaf 2.1");
Leaf cmp22 = new Leaf("Leaf 2.2");
cmp20.addChild(cmp21);
cmp20.addChild(cmp22);

/**
 * Arbre :
 * root
 *   + Leaf 1
 *   + Node 2
 *       + Leaf 2.1
 *       + Leaf 2.2
 */

root.injectVisitor(injector);
root.visit();

En voici le schéma UML modifié avec le composite au niveau des éléments :

Image non disponible

XI-B. Variant 2 : Injecteurs composites

De la même façon, la partie du diagramme de classes décrivant la partie injection du patron peut être architecturée sous la forme d'un composite.

Pour ce faire, voici les nouveaux éléments (appelés expression pour l'occasion puisqu'il s'agit de parcourir une expression arithmétique à travers son AST) :

 
Sélectionnez
// l'interface
public interface VisitorInjector<E extends Expression> {
    MethodVisitor getVisitor(E e);
}

// l'injecteur simple
public class LeafVisitorInjector<E extends Expression> implements VisitorInjector<E> {

    private final MethodVisitor<E> visitor;

    public LeafVisitorInjector(MethodVisitor<E> visitor) {
        this.visitor = visitor;
    }

    @Override
    public MethodVisitor<E> getVisitor(E e) {
        return visitor;
    }
}

// le composite qui associe les classes à un visiteur
public class ClassMapVisitorInjector implements VisitorInjector {

    private final Map<Class<? extends Expression>, VisitorInjector> injectors;

    public ClassMapVisitorInjector() {
        this.injectors = new HashMap<>();
    }

    public <E extends Expression> void addInjector(Class<E> clazz, VisitorInjector<E> injector) {
        injectors.put(clazz, injector);
    }

    @Override
    public MethodVisitor getVisitor(Expression e) {
        // chaîne de responçabilité
        return injectors.get(e.getClass()).getVisitor(e);
    }

}

// Et celui qui associe le signe d'une opération à une méthode (par exemple plus, moins, multiplie, divise, etc.)
public class SignVisitorInjector<E extends Expression & Signed> implements VisitorInjector<E> {

    private final Map<Character, VisitorInjector<E>> injectors;

    public SignVisitorInjector() {
        this.injectors = new HashMap<>();
    }

    public void addInjector(Character sign, VisitorInjector<E> injector) {
        injectors.put(sign, injector);
    }

    @Override
    public MethodVisitor getVisitor(E e) {
        // chaîne de responsabilité
        return injectors.get(e.getSign()).getVisitor(e);
    }

}

// Et l'interface signed qui est utile à l'injecteur précédent (e.getSign() de la méthode getVisitor)
public interface Signed {
    char getSign();
}

Remarquez la signature particulière du générique E : <E extends Expression & Signed> qui signifie que l'expression doit implémenter l'interface Signed.

Voici notre AST, tout ce qu'il y a de plus classique :

 
Sélectionnez
// La super classe expression
public abstract class Expression {
    private MethodVisitor visitor;

    public void injectVisitor(VisitorInjector injector) {
        visitor = injector.getVisitor(this);
    }

    public void visit() {
        this.visitor.visit(this);
    }
}

// Un nombre littéral
public class Number extends Expression {
    private final int value;

    public Number(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

}

// Une expression binaire (+, -, *, /, %)
public class BinaryExpression extends Expression implements Signed {
    private final Expression left;
    private final Expression right;
    private final char sign;

    public BinaryExpression(Expression left, char sign, Expression right) {
        this.left = left;
        this.sign = sign;
        this.right = right;
    }

    public Expression getLeft() {
        return left;
    }

    @Override
    public char getSign() {
        return sign;
    }

    public Expression getRight() {
        return right;
    }

    @Override
    public void injectVisitor(VisitorInjector injector) {
        super.injectVisitor(injector);
        left.injectVisitor(injector);
        right.injectVisitor(injector);
    }

}

Et l'utilisation de tout ceci :

 
Sélectionnez
// Injecteur pour les expressions binaires
SignVisitorInjector<BinaryExpression> binaryExpressionInjector = new SignVisitorInjector<>();
binaryExpressionInjector.addInjector('+', new LeafVisitorInjector<>(new MethodVisitor<BinaryExpression>() {

    @Override
    public void visit(BinaryExpression e) {
        System.out.print("(");
        e.getLeft().visit();
        System.out.print(" + ");
        e.getRight().visit();
        System.out.print(")");
    }
}));
binaryExpressionInjector.addInjector('-', new LeafVisitorInjector<>(new MethodVisitor<BinaryExpression>() {

    @Override
    public void visit(BinaryExpression e) {
        System.out.print("(");
        e.getLeft().visit();
        System.out.print(" - ");
        e.getRight().visit();
        System.out.print(")");
    }
}));

// Injecteur principal
ClassMapVisitorInjector injector = new ClassMapVisitorInjector();

injector.addInjector(BinaryExpression.class, binaryExpressionInjector);
injector.addInjector(Number.class, new LeafVisitorInjector<>(new MethodVisitor<Number>() {

    @Override
    public void visit(Number e) {
        System.out.print(e.getValue());
    }
}));

// exemple d'expression arithmetique
// 8 + 2 - 7
Expression expr = new BinaryExpression(new Number(8), '+', new BinaryExpression(new Number(2), '-', new Number(7)));

expr.injectVisitor(injector);
expr.visit();
System.out.println("");
// resultat : (8 + (2 - 7))

Attention toutefois, le code est simplifié à l'extrême. Dans un cas réel il est utile d'utiliser un contexte pour passer des paramètres (résultats intermédiaires, etc.) lors de la visite.

Voici le schéma UML correspondant, avec les injecteurs architecturés selon un patron composite :

Image non disponible

XII. Remerciements

Je tiens à remercier toute ma petite famille qui ferme les yeux sur ma geek attitude et me pardonne mon manque de présence… Du moins parfois.

Merci également à toute l'équipe du forum developpez.com pour leurs lectures patientes, leurs corrections (plus que patientes) et leurs encouragements très appréciés. Tout particulièrement regis1512 et Thierry Leriche Dessirier pour leur relecture technique avisée et f-leb pour ses promptes corrections orthographiques.

Vos retours nous aident à améliorer nos publications. N'hésitez donc pas à commenter cet article sur le forum : Commentez cet article.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

En complément sur Developpez.com

  

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2014 Yann Caron. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.