Comportement dynamique

Introduction

Cet article va s’appuyer sur un problème concret pour montrer la mise en place d’une sélection dynamique de comportement. Un autre objectif sera d’illustrer l’assemblage de divers composants, principalement issus de boost, pour répondre à un problème plus complexe.

Les bibliothèques de boost utilisées sont : container, functional, mpl, phoenix et variant. Chacune de ces bibliothèques répond à un problème bien précis, si bien que l’essentiel du travail sera de les assembler sans se soucier des problématiques techniques inhérentes au langage.

Le problème que j’ai choisi est assez classique, comment gérer de manière homogène plusieurs formes géométriques et déterminer les collisions avec divers algorithmes ? Ce problème est surtout un prétexte, je ne vais ni soutenir qu’il est utile dans une situation quelconque, ni qu’il est le plus efficace possible.

Contexte

Je vais directement introduire du code pour exposer le contexte :

#include<string>

#include<boost/container/flat_map.hpp>
#include<boost/container/vector.hpp>

namespace container = boost::container;

//Deux types représentant des formes
struct Rectangle {};
struct Ellipsis {};
//Comment écrire les algorithmes de collisions ?

using Shape = /* * */;
//On va avoir besoin d'un type pour
//manipuler nos formes ensemble,
//lequel ?

//Comme notre système est dynamique, l'on
//va avoir besoin d'un type de clé
using KeyType = std::string;

//On va avoir besoin d'un objet associant
//à des clés de quoi créer des formes
using Factories =
    container::flat_map<KeyType,/* ** */>;
//Il s'agit d'un conteneur associatif,
//à quoi associer les clés ?

//On crée ce conteneur :
//c'est nos "factories"
Factories factories;
//Comment le remplir ?

//On crée un conteneur de forme et on le remplit un peu
container::vector<Shape> container;
container.push_back(factories["Rectangle"]/**/);
container.push_back(factories["Rectangle"]/**/);
container.push_back(factories["Ellipsis" ]/**/);
container.push_back(factories["Ellipsis" ]/**/);
//Le remplissage dépend de nos factories

//Comment tester des collisions ?

On voit les différentes interrogations auxquelles l’on va devoir répondre. Notons dès maintenant la volonté de garder le système le plus générique possible, l’on doit pouvoir changer très facilement un élément du système. Par exemple :

  • changer de type de clé doit se limiter à changer le KeyType et les valeurs associées aux différentes formes.
  • changer le type de conteneur pour les factories ou le conteneur de formes doit se limiter à changer une ligne.
  • ajouter un nouveau genre de forme à l’ensemble des formes possibles doit se limiter à changer un using, ajouter un élément aux factories et (nécessairement) fournir les algorithmes de collision nécessaires.

Type-Erasure et Multi-Dispatch

Le premier élément est l’utilisation d’un type-erasure, c’est-à-dire d’un type regroupant plusieurs types supprimant ainsi les informations propres à chaque type : on perd de l’information. Une première forme de type-erasure est l’héritage offert par le C++.

Une fois que l’on dispose de ce type-erasure, la question est de savoir comment avoir des services avec un comportement lié au type réel. Dans le cas où le service ne porte que sur un seul objet (avec un type-erasure) et qu’on utilise l’héritage pour le réaliser, le C++ propose la redéfinition de fonction. Dans le cas où il y a plusieurs objets, la problématique est celle du multi-dispatch : c’est notre cas, la collision utilise deux type-erasure.

On va utiliser le type-erasure de boost : boost.variant. Notre code devient :

#include<boost/variant/variant.hpp>

using Shape =
    boost::variant<Rectangle,Ellipsis>;

Ainsi notre type Shape peut représenter aussi bien un objet de type Rectangle que de type Ellipsis. Maintenant il faut écrire et utiliser notre service collide qui utilise deux type-erasure :

#include<iostream>
#include<utility>

#include<boost/variant/apply_visitor.hpp>
#include<boost/variant/static_visitor.hpp>

//Visiteur utilisant boost::variant
//On définit ici les différents algorithmes de collision
//en surchargeant l'opérateur ()
//La dernière surcharge permet de prendre en compte la symétrie
//Notre service est donc cet objet collide d'un type non nommé
//Le std::string dans le type hérité indique le type de retour
//le choix de std::string n'est ici que pour l'exemple

struct : boost::static_visitor<std::string>
{
    result_type operator()(Rectangle&, Rectangle&) const
    { return "Rectangle vs Rectangle"; }
    result_type operator()(Ellipsis&, Ellipsis&) const
    { return "Ellipsis  vs Ellipsis" ; }
    result_type operator()(Rectangle&, Ellipsis&) const
    { return "Rectangle vs Ellipsis" ; }
    template<class T, class U>
    result_type operator()(T&& lhs, U&& rhs) const
    {
        return (*this)(
            std::forward<U>(rhs),
            std::forward<T>(lhs)
        );
    }
} collide;

//On peut alors tester des collisions,
//l'utilisation du service collide est
//plus verbeuse que pour une simple fonction
std::cout
    << "Test                     ResultnRectangle vs Rectangle : "
    << boost::apply_visitor(collide,container[0],container[1])
    << "nEllipsis  vs Ellipsis  : "
    << boost::apply_visitor(collide,container[2],container[3])
    << "nRectangle vs Ellipsis  : "
    << boost::apply_visitor(collide,container[0],container[2])
    << "nEllipsis  vs Rectangle : "
    << boost::apply_visitor(collide,container[3],container[1])
    << std::endl;

A ce stade vous pouvez tester le code si vous remplissez manuellement (ie sans utiliser les factories) le conteneur de forme. Notons qu’il y a une problématique technique très forte pour réaliser un système de multi-dispatch, elle est ici totalement effacée par l’utilisation de boost.

Si vous êtes intéressés par la réalisation d’un tel système, les différentes possibilités sont traitées dans Modern C++ Design d’Andrei Alexandrescu. Il existe des techniques qui peuvent s’avérer plus rapide.Cependant, quelle que soit la solution technique, il est possible d’avoir une interface proche de celle proposée par boost.

Factories

Une factory n’est rien d’autre qu’un élément permettant de construire un objet désiré : c’est donc un simple service, pour le stocker on retrouve la notion de type-erasure.  Nos factories deviennent :

#include<functional>

using Factories =
    container::flat_map<KeyType,std::function<Shape()>>;

Pour l’exemple, les factories utilisées seront simples, il n’y a donc pas de paramètres (ce qui est entre les ()). Dans le cas contraire il faudrait adapter cette partie du code et la partie qui créée des formes qui dans ce cas simple est :

//On crée un conteneur de forme et on le remplit un peu
container::vector<Shape> container;
container.push_back(factories["Rectangle"]());
container.push_back(factories["Rectangle"]());
container.push_back(factories["Ellipsis" ]());
container.push_back(factories["Ellipsis" ]());

On va aborder le remplissage de ces factories, pour ce faire introduire plus de généricité nous offrira un gain. On va introduire une séquence de type, adaptons immédiatement la création du type utilisée pour représenter une forme avec cette nouvelle séquence :

#include<boost/mpl/vector.hpp>

namespace mpl       = boost::mpl;

using SeqShape =
    mpl::vector<Rectangle,Ellipsis>;
using Shape =
    boost::make_variant_over<SeqShape>::type;

Venons en au remplissage, il dépend bien entendu de cette séquence de types (une factory par type de forme), du conteneur associatif qu’on veut remplir et du type des clés. On va utiliser l’algorithme for_each de mpl :

#include<boost/mpl/for_each.hpp>

mpl::for_each<SeqShape,/* méta-foncteur */>
    (/* foncteur */);
  • Il itère sur la séquence de types en y appliquant un méta-foncteur pour obtenir un autre type. Le méta-foncteur dépend du type de clé.
  • Pour chacun de ces types, il instancie un objet sur lequel il applique un foncteur. Le foncteur dépend du conteneur associatif.

Il nous faut donc créer une classe pour chaque type de la séquence que l’on puisse instancier et qui fournira la clé à insérer dans le conteneur associatif. Une macro nous permet de rapidement créer ces classes, on peut donc compléter le premier foncteur du for_each :

#include<boost/mpl/placeholders.hpp>

template<class,class>
struct Id;

#define MACRO_ID(TYPE_ID,TYPE_OBJ,ID_OBJ) 
    template<> 
    struct Id<TYPE_ID,TYPE_OBJ> 
    { TYPE_ID const id = ID_OBJ; }

//Par exemple, on associe au type Rectangle l'identifiant
//"Rectangle" de type std::string

MACRO_ID(std::string,Rectangle,"Rectangle");
MACRO_ID(std::string,Ellipsis ,"Ellipsis" );

using mpl::placeholders::_;

mpl::for_each<SeqShape,Id<KeyType,_>>
    (/* foncteur */);

Il nous reste à écrire le foncteur, son rôle est d’utiliser les clés fournies par les itérations successives du méta-foncteur sur la séquence de type pour insérer les bonnes factories dans le conteneur de factories, on a donc besoin d’un foncteur polymorphique, on va utiliser phoenix :

#include<boost/functional/value_factory.hpp>

#include<boost/phoenix/core.hpp>
#include<boost/phoenix/function.hpp>

namespace phoenix   = boost::phoenix;

struct PopulateType
{
    template<class...>
    struct result
    { typedef void type; };

    template<class Factories, class T>
    void operator()(
        Factories& factories,
        const Id<typename Factories::key_type,T>& i) const
    { factories[i.id]=boost::value_factory<T>(); }
};

phoenix::function<PopulateType> const populate;

using phoenix::placeholders::arg1;

mpl::for_each<SeqShape,Id<KeyType,_>>
    (populate(phoenix::ref(factories),arg1));

Le code est maintenant complet, si vous avez assemblé l’ensemble des morceaux de code correctement, il devrait être parfaitement fonctionnel. La prochaine partie, qui fera office de conclusion, sera là pour vérifier que les objectifs énumérés dans la première partie sont bel et bien atteint.

Conclusion

Vérifions d’abord la situation la plus classique, comment ajouter un type de forme ? Avec notre code il faut :

  • Une classe représentant cette forme, c’est un besoin incompressible.
  • Ajouter les algorithmes de collision propre à ce type, c’est aussi incompressible.
  • Modifier la séquence de type et l’utilisation de la macro MAKE_ID, ce sont deux éléments très localisés du code : on a donc une grande flexibilité.

La seconde modification la plus courante et le changement de type de clé :

  • Changer un using
  • Autant d’utilisation de MAKE_ID que de type de forme : c’est à nouveau très localisé.

Les autres modifications sont moins courantes et beaucoup plus spécifiques à la situation, elles concernent principalement le foncteur et ce qu’il insère dans le conteneur. Dans l’exemple il s’agit de simple boost::value_factory&&, mais ceci pourrait être plus complexe : allocation dynamique, utilisation de paramètre pour la construction, …

Pour conclure, je tiens à souligner encore une fois que la problématique choisie et la résolution proposée sont surtout un prétexte pour montrer comment divers éléments peuvent travailler ensemble. La résolution n’est probablement pas optimale et la problématique n’est pas forcément probante.

Publicités

2 réflexions au sujet de « Comportement dynamique »

  1. Ping : Lambda polymorphique du C++14 | C++ | Boost — Développement

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s