URL: https://linuxfr.org/users/rewind/journaux/visiteurs-en-c Title: Visiteurs en C++ Authors: rewind Date: 2013年04月24日T04:19:54+02:00 License: CC By-SA Tags: c et génie_logiciel Score: 27 Le [design pattern du Visiteur](http://fr.wikipedia.org/wiki/Visiteur) est un des plus connu. Il permet, selon Wikipédia, de «séparer un algorithme d'une structure de données». Je ne rappelle pas l'intérêt de ce design pattern, j'en viens directement au fond de cet article : quelle est la meilleure façon de faire un Visiteur en C++ ? Il y a essentiellement deux manières, et une variante sur la deuxième, avec chacune leurs avantages et inconvénients. # Le Visiteur polymorphe C'est la manière la plus simple et celle qu'on rencontre partout (comme sur l'article Wikipédia). Voilà comment ça se présente sur un petit exemple. ```c++ class Visitor; class Base { public: virtual void accept(Visitor& vis) { vis.visitBase(*this); } }; class Derived : public Base { public: virtual void accept(Visitor& vis) override { vis.visitDerived(*this); } }; class Visitor { virtual void visitBase(Base& b) { } virtual void visitDerived(Derived& d) { } }; ``` Du classique. Ensuite, quand on veut utiliser un Visiteur, on dérive de `Visitor` et hop, ça marche. Je ne détaille pas les avantages/inconvénients tout de suite. # Le Visiteur template Pour ceux qui n'aiment pas le polymorphisme (qui est quand même l'essence de l'OO), C++ permet de faire un Visiteur avec des templates. Ce code est inspiré de [LLVM (qui utilise la variante présentée ensuite)](http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/InstVisitor.h?view=markup) qui utilise des Visiteurs pour quasiment tout. ## Le Visiteur template à base de RTTI L'idée est simple : remplacer le dispatch du `accept` par une suite de condition vérifiant le type de l'objet dynamiquement. Pour cela, on va utiliser l'opérateur [`typeid`](http://en.cppreference.com/w/cpp/language/typeid) qui permet de récupérer un objet de type `type_info` qu'on peut comparer à un autre objet de type `type_info`. Quand les objets sont simples (sans méthode virtuelle), le `type_info` peut être calculé à la compilation. Dès que l'objet possède une méthode virtuelle (le destructeur par exemple), le `type_info` est déterminé à l'exécution. ```c++ class Base { public: virtual ~Base() { } // on met une fonction virtuelle pour rendre typeid dynamique void accept(Visitor& vis) { if (typeid(*this) == typeid(Derived)) { vis.visitDerived(static_cast(*this)); return; } vis.visitBase(*this); } }; class Derived : public Base { // pas besoin de code dans les classes filles }; ``` Reste un problème : en l'état actuel, le Visiteur doit encore être déclaré comme précédemment, avec du polymorphisme. C'est là qu'intervient le template. Il est impossible en C++ de déclarer une méthode virtuelle avec un template (heureusement !), mais ici, notre méthode `accept` n'est plus virtuelle, donc on peut lui coller un template. ```c++ template void accept(Visitor& vis) { if (typeid(*this) == typeid(Derived)) { vis.visitDerived(static_cast(*this)); return; } vis.visitBase(*this); } ``` Cette fois, c'est gagné, on peut déclarer n'importe quel visiteur sans devoir hériter d'un visiteur père. ```c++ class FooVisitor { void visitBase(Base& b) { } void visitDerived(Derived& d) { } }; ``` On doit cependant déclarer toutes les méthodes requises. Inutile de créer un Visiteur père avec des implémentations par défaut, ça ne marchera pas. Au moment de l'instanciation, le compilateur n'ira pas chercher dans la classe mère. Pour pallier ce problème, on peut modifier un peu notre Base et notre Visiteur et placer la logique de dispatch dans le Visiteur. ```c++ class Base { public: virtual ~Base() { } template void accept(Visitor& vis) { vis.visit(*this); } }; class Derived : public Base { }; template class Visitor { public: void visit(Base& base) { if (typeid(base) == typeid(Derived)) { static_cast(this)->visitDerived(static_cast(base)); // Ouch ! return; } static_cast(this)->visitBase(base); } // les implémentations par défaut void visitBase(Base& b) { } void visitDerived(Derived& d) { } }; ``` Un peu d'explication sur la ligne Ouch. Déjà, on a un argument template pour ce visiteur. Quand on implémentera un visiteur, il faudra dériver de celui-ci de la manière suivante : ```c++ class FooVisitor : public Visitor { // ... }; ``` Ça permet de prévenir `Visitor` de sa classe fille et donc de faire appel aux méthodes de la classe fille en castant `this` en `Subclass`. Comme on appelle `visit` depuis l'objet, on peut faire le dispatch dans le visiteur et appeler les méthodes utiles du Visiteur à ce moment-là. Ensuite, dans les Visiteurs (comme `FooVisitor`), on implémente uniquement les méthodes nécessaires et pas toutes les méthodes. ## Avantages et inconvénients Évidemment, tout est histoire de compromis. Passons donc en revue les avantages et inconvénients de chaque technique. Du côté des avantages pour les templates, on peut citer le découplage entre le Visiteur et la structure, dans le sens où on n'a plus de cycle de dépendance entre `Visitor` et `Base`. Autre avantage, si on ajoute une classe dans la hiérarchie et qu'on n'a pas mis de méthode par défaut, on tombera dans le cas de `Base`. Ce cas ne sera sans doute pas pertinent, mais ça compilera. Avec le Visiteur polymorphe, il faudra ajouter la méthode adéquate dans le visiteur sinon, ça ne compilera pas. Du côté des inconvénients, un petit test rapide montre que le Visiteur avec template est environ 3 fois plus lent que le Visiteur polymorphe. C'est là qu'intervient la variante pour améliorer ce manque de performance. ## Le Visiteur template sans RTTI Ce qui prend du temps, c'est le RTTI, c'est-à-dire tous les appels à `typeid`. Il est possible de mimer un genre de typeid en ajoutant un membre à `Base` qui sera initialisé dans les constructeurs. ```c++ enum Kind { BASE, DERIVED } class Base { public: const Kind kind; Base(Kind k) : kind(k) { } // pour les classes filles Base() : kind(BASE) { } // pour la classe Base // ... }; class Derived : public Base { public: Derived() : Base(DERIVED) { } }; ``` Ça alourdit un peu le code mais ça permet de se passer du RTTI. Du côté du Visiteur, on peut faire un simple `switch`: ```c++ template class Visitor { public: void visit(Base& base) { switch (base.kind) { case DERIVED: static_cast(this)->visitDerived(static_cast(base)); // Ouch ! return; case BASE: static_cast(this)->visitBase(base); } } // ... }; ``` Avec cette astuce, on n'arrive pas tout à fait à la performance du Visiteur polymorphe mais on s'en approche à moins de 10%, ce qui est tout à fait convenable. ## Les petits plus LLVM, en plus de cette technique, introduit deux petits plus dont le premier n'est pas reproductible dans le cas du Visiteur polymorphe. Il s'agit de faire varier le type de retour du Visiteur. Actuellement, on a mis `void`. Mais on peut faire mieux et mettre le type de retour dans le template du visiteur. ```c++ class Base { public: // ... template typename Visitor::return_type accept(Visitor& vis) { return vis.visit(*this); } }; template class Visitor { public: typedef RetTy return_type; return_type visit(Base& base) { switch (base.kind) { case DERIVED: return static_cast(this)->visitDerived(static_cast(base)); // Ouch ! case BASE: return static_cast(this)->visitBase(base); } } return_type visitBase(Base& b) { return return_type(); } return_type visitDerived(Derived& d) { return return_type(); } }; ``` On peut maintenant faire des visiteurs qui renvoie des entier ou tout autre type. Dans le cas du Visiteur polymorphe, on peut passer par un membre mais c'est moins joli. Autre petit plus inspiré de LLVM et qui là, peut tout à fait s'appliquer au Visiteur polymorphe. Généralement, on ne visite que les feuilles de l'arbre des classes et pas les classes abstraites. LLVM permet de visiter également une classe abstraite et, dans les implémentations par défaut, le visiteur appelle la méthode pour sa classe mère (éventuellement abstraite). Cette astuce permet de mutualiser certains traitements à toute une hiérarchie. ```c++ template class Visitor { public: typedef RetTy return_type; // ... return_type visitBase(Base& b) { return return_type(); } return_type visitDerived(Derived& d) { return visitBase(d); } }; ``` # Conclusion Voilà, le voyage dans le fabuleux monde des visiteurs C++ est fini. En conclusion, on peut dire qu'il n'y a pas un vainqueur net, mais qu'il faut adapter le type de Visiteur au projet.

AltStyle によって変換されたページ (->オリジナル) /