Apprendre à implémenter un autre type de polymorphisme

Nous commençons par observer le polymorphisme classique basé sur des fonctions virtuelles.

L'objectif de tout polymorphisme est de faire en sorte qu'une routine donnée (une fonction ou une fonction template) s'exécute et fasse les choses correctement, même si nous ignorons quels types de variables nous allons utiliser effectivement. Autrement dit, il s'agit de mettre en œuvre une forme de type erasure, une sorte de ligne de démarcation derrière laquelle il pourrait y avoir différents sous-programmes en cours d'exécution à des moments différents, mais devant elle nous avons toujours le même algorithme.

Il y a plusieurs façons d'obtenir cet effet. Le polymorphisme basé sur la table de fonctions virtuelles possède quelques caractéristiques particulières :

1. Nombre fixe de fonctions. Vous choisissez d'abord une interface complète et fixe : des fonctions membres virtuelles, et décidez d'interagir avec des objets de différents types uniquement à travers cette interface. Techniquement, vous pouvez surmonter cette contrainte en utilisant un dynamic_cast, mais cela est contraire à l'idée de polymorphisme basé sur la vtable, et en fait va à l'encontre du but d'utiliser en premier lieu ce type de polymorphisme, alors nous n'en discuterons pas davantage ici.
2. Nombre illimité de types. Une fois que vous avez choisi l'interface, n'importe qui peut définir à tout moment un nouveau type qui peut être utilisé à travers l'interface, tant que ce type est conforme. Les fonctions qui opèrent sur l'interface n'ont pas besoin de savoir combien de types différents il y aura.
3. Sécurité de type. Si l'interface possède des fonctions virtuelles pures et j'oublie de mettre en œuvre l'une d'elles dans mes types, je reçois une erreur de compilation.

Cela est très utile dans certains cas. Nous pouvons par exemple utiliser le polymorphisme basé sur la vtable pour mettre en œuvre des plug-ins d'application : lorsque nous écrivons le programme principal, nous ne savons pas combien de plug-ins différents lui seront ajoutés et lesquels. Mais nous n'avons pas à nous en préoccuper, tant que nous fournissons une bonne interface.

Parfois, nous avons besoin de quelque chose de différent. Lorsque ma structure de données modélise une situation de la vie réelle, il m'arrive souvent de me dire que dans un « endroit » donné j'aurais besoin de choisir parmi deux ou trois options bien définies.

Laissez-moi vous donner un exemple. Supposons que nous voulons représenter une séquence de conteneurs physiques (boîtes) qui seront chargés dans une cale. Chaque boîte pourrait être :

1. Un conteneur régulier — vous pouvez y mettre une certaine quantité de cargaison qui tient à l'intérieur d'un volume donné.
2. Un conteneur multiple — il se compose d'une séquence de conteneurs plus petits : chacun d'entre eux peut être chargé comme un conteneur régulier, mais ensemble ils constituent une boîte qui sera placée dans un endroit de la cale. (Ces récipients plus petits ne peuvent pas être subdivisés.)
3. Du lest — vu de l'extérieur, cela ressemble à un conteneur, et peut être situé dans la cale comme un conteneur régulier, mais rien ne peut être chargé à l'intérieur, et son utilité est légèrement différente.

Je peux représenter chacun de ces récipients par un type distinct, chacun contenant un ensemble différent de données :

struct Conteneur
{
  Volume allocation_volume;
  Poids allocation_poids;
  bool est_climatise;
  Id id;
  // plus de code ...
};
 
struct ConteneurMultiple
{
  vector<Conteneur> conteneurs;
  Id id;
  // plus de code ...
};
 
struct Lest
{
  LestType type;
  Poids poids;
  // plus de code ...
};

La question est de savoir comment je devrais dire que, à un endroit donné, j'attends l'un de ces trois types de données. Ceci est bien sûr réalisable avec un polymorphisme basé sur la vtable : je dois définir une classe d'interface, puis forcer mes types à se conformer à l'interface. Si je ne peux pas les forcer (parce que je ne contrôle pas leurs définitions), je dois définir des types d'enveloppes, qui contiendront le type d'origine et se conformeront à l'interface. Mais cela pose deux problèmes :

1. Cela n'exprime pas mon idée d'avoir uniquement l'un des trois types, sans aucune autre implémentation d'interface attendue ou permise.
2. Les trois types n'ont vraiment rien en commun (sauf le fait que je les veux au même endroit). Quelles fonctions dois-je mettre dans l'interface ?

En ce qui concerne le premier problème, vous pouvez le rejeter en disant : « Et alors ? Nous allons accepter tout simplement que quelqu'un puisse ajouter une autre implémentation de l'interface ». Cela ne correspond plus à notre intention, et nous pourrions rater des opportunités d'optimisation ; mais cela pourrait encore représenter une solution acceptable.

Le second problème est plus sérieux. Les trois types ne disposent pas d'une interface commune. Certes, à un moment donné dans le programme j'aurai besoin de les traiter de manière uniforme. Mais au moment de la conception de mes structures de données, je ne sais pas à l'avance combien d'opérations différentes je devrai effectuer sur les types. Je suppose que je pourrais vouloir :

• obtenir le poids total alloué ;
• obtenir le volume total alloué ;
• vérifier si une partie d'un conteneur est climatisée ;
• vérifier si tout le conteneur est climatisé ;
• vérifier si le chargement est possible ;
• vérifier si c'est du lest ;
• vérifier si le conteneur est divisé en sous-conteneurs ;
• vérifier si le conteneur correspond à un volume donné ;
• vérifier si le conteneur a un identifiant ;
• obtenir l'identifiant ;
• obtenir la liste des identifiants ;
• que sais-je encore…

C'est exactement le contraire de ce qu'une interface est censée être. Une interface doit être constituée d'un petit nombre de fonctions faciles à comprendre et reflétant la nature commune des objets avec lesquels nous travaillons. Mon interface, en revanche, en plus d'être énorme va continuer de croître chaque fois où j'écris une nouvelle fonction parce que je trouve l'ensemble actuel des fonctions insuffisant.

Au lieu de cela, je pourrais ajouter une interface triviale avec une seule fonction virtuelle — le destructeur — et utiliser la conversion dynamique de type (dynamic_cast) partout où je veux utiliser les types.

Cela, bien sûr, plombe complètement l'idée d'utiliser une interface basée sur la vtable. Nous allons contourner en permanence l'interface. Même si c'est laid, cela fera l'affaire, mais il y a un problème de sécurité. Lorsqu'un jour il sera nécessaire d'ajouter un quatrième type de cargaison, que je ne peux pas connaître à l'avance, les dynamic_cast existants ne le prendront pas en compte par défaut ; et si j'oublie de modifier le code dans tous les endroits où cela est nécessaire, j'obtiendrai un bogue dans la logique de mon programme : certaines parties du programme ne seront pas préparées à gérer ce nouveau type de données, même si elles compileront.

Ce qui précède est un genre de problème que Boost.Variant est destiné à résoudre. Avec Boost.Variant, vous déclarez votre type « l'un des trois » comme :

using Cargaison =
  boost::variant<Lest, Conteneur, ConteneurMultiple>;

Maintenant, le type Cargaison est soit un Lest, soit un Conteneur, soit un ConteneurMultiple, et rien d'autre.

Cargaison est un type régulier : il est constructible par défaut (si Lest l'est), il est copiable et mobile (à condition que les trois types le soient). Il est même comparable en termes d'égalité (à condition que les trois types le soient).

Cargaison a tous ses sous-types codés dans son type. Cela laisse la place à un certain nombre de calculs utiles réalisés à la compilation. Par exemple, le compilateur peut calculer le sizeof requis par Cargaison : c'est la taille du plus grand des trois sous-types + un byte pour le discriminant — qui indique le sous-type exact auquel appartient un objet donné. De cette façon, nous ne demandons pas à allouer de la mémoire sur le tas.

(Bon, parfois l'affirmation ci-dessus concernant sizeof et l'allocation sur le tas n'est pas vraie, comme nous le verrons plus loin.)

Boost.Variant garantit que les objets de type Cargaison contiennent toujours une instance valide de l'un des trois sous-types : ils ne sont jamais « vides ». Cela est appelé une garantie du jamais vide.

La représentation d'un « choix » de types est la partie facile. La question intéressante est de savoir comment utiliser une telle chose. Boost.Variant vous permet de demander quel type est couramment/actuellement stocké dans l'objet, mais nous ne voulons pas le faire. Ce dont nous avons besoin est un mécanisme de plus haut niveau de manipulation polymorphique du variant.

En quelque sorte, nous voulons traiter de façon uniforme n'importe quel sous-type de notre Cargaison. Nous voulons quelque chose qui ressemble à un appel de fonction virtuelle : nous lui passons une référence à Cargaison et elle devrait savoir que faire avec chacun de ses sous-types.

C'est ici que nous pouvons voir toute la puissance de Boost.Variant. Le code suivant montre comment nous pouvons utiliser le concept d'un visiteur statique pour calculer le poids alloué à n'importe quel Conteneur, ConteneurMultiple ou Lest.

struct Allocation_poids : boost::static_visitor<Poids>
{
  Poids operator()(const Conteneur& conteneur) const
  {
    return conteneur.allocation_poids;
  }
      
  Poids operator()(const ConteneurMultiple& multi) const
  {
    Poids poids (0);
    for (const Conteneur& conteneur : multi.conteneurs)
      poids += conteneur.allocation_poids ;
    return poids;
  }
      
  Poids operator()(const Lest&) const
  {
    return Poids(0);
  }
};

Le fait de dériver de boost::static_visitor<Poids> indique que cet objet fonction peut être utilisé pour « déballer » un variant. Son type de retour est Poids. Ensuite, nous donnons des indications pour calculer le poids de chaque sous-type possible.

Nous invoquons cette « fonction polymorphe » comme ceci :

Cargaison c = /* ... */;
Poids p = boost::apply_visitor(Allocation_poids(), b);

La fonction supplémentaire apply_visitor inspecte l'état actuel du type variant et appelle la routine correspondante. En outre, elle effectue un calcul à la compilation pour vérifier si tous les cas de sous-types du variant ont été envisagés : si nous en avons omis un, nous obtenons une erreur de compilation. Cela est particulièrement utile lorsqu'à un moment donné vous avez besoin d'ajouter un nouveau sous-type au variant. Les erreurs de compilation (si laides qu'elles soient) vous indiquent immédiatement tous les endroits dans le code qui doivent être reconsidérés.

Vous pouvez voir ici un exemple complet d'utilisation de Boost.Variant avec des visiteurs statiques.

Si vous regardez la structure de la définition du visiteur (Allocation_poids ci-dessus), elle ressemble dans un sens à une instruction switch. Dans un langage différent, nous pourrions l'exprimer ainsi :

// PAS EN C++
Poids Allocation_poids(const Cargaison& c)
{
  type switch (b)
  {
  case (const Conteneur& cont):
    return cont.allocation_poids;
 
  case (const ConteneurMultiple& multi):
    Poids poids (0);
    for (const Conteneur& cont : multi.conteneurs)
      poids += cont.allocation_poids;
    return poids;
 
  case (const Lest&):
    return Poids(0);
  }
}

Pour poursuivre l'analogie avec l'instruction switch, vous pouvez utiliser un équivalent de l'étiquette default lors de la définition d'un visiteur. Prenons l'exemple suivant :

struct Is_lest : boost::static_visitor<bool>
{
  bool operator()(const Lest&) const { return true; }
     
  template <typename T>
  bool operator()(const T&) const { return false; }
};

Cela signifie « pour Lest retourne vrai, pour toute autre chose retourne faux ». Cependant, je ne vous conseillerais pas de le faire. Vous ne savez pas ce que « toute autre chose » pourrait être à l'avenir, quand un nouveau sous-type sera ajouté au type variant. Ou vous pourriez invoquer par erreur le visiteur sur un autre variant, comme variant<int, long, float>, car un visiteur n'est pas lié à un type précis de variant. En utilisant un cas inspecte-tout, vous perdez la fonctionnalité de sécurité statique.

La véritable puissance du visiteur statique devient visible lorsque vous devez traiter simultanément deux types de variants.

Supposons que nous ayons une liste de contenus que nous voulons distribuer dans des conteneurs. Chaque contenu peut être soit un seul paquet, soit un ensemble de paquets, qui pour certaines raisons sont traités comme un seul paquet, mais pour les besoins du transport peuvent être séparés et répartis dans un certain nombre de conteneurs. Ceci est représenté par les types suivants :

struct Paquet
{
  Poids poids;
  Volume volume;
  Id id;
  bool necessite_air_conditionne;
  // plus de code ...
};
 
struct MultiPaquet
{
  Id paquet_id;
  vector<Paquet> sous_paquets;
  // plus de code ...
};
 
using UniteCharge = boost::variant<Paquet, MultiPaquet>;

Maintenant, nous voulons écrire une fonction binaire qui inspecte si une UniteCharge donnée peut être incluse dans une Cargaison donnée. Voilà comment nous le faisons avec Boost.Variant :

struct Tient : boost::static_visitor<bool>
{
  bool operator()(const Conteneur& c, const Paquet& p) const
  {
    return c.allocation_poids >= p.poids
        && c.allocation_volume >= p.volume;
  }
     
  bool operator()(const Conteneur& c,
                  const ConteneurMultiple& cm) const
  {
    return bool("la totalité des paquets tient dans c");
  }
     
  bool operator()(const ConteneurMultiple& cm,
                  const Paquet& p) const
  {
    for (const Conteneur& c : cm.conteneurs)
      if (Tient{}(c, p)) // auto-appel
        return true;
    return false;
  }
     
  bool operator()(const ConteneurMultiple& cm,
                  const PaquetMultiple& pm) const
  {
    return bool("la totalité des paquets tient dans l'ensemble de sous-conteneurs");
  }
      
  template <typename T>
  bool operator()(const Lest&, const T&) const
  {
    return false;
  }
};

Je n'ai pas de place pour mettre en œuvre décemment tous les cas de figure, mais vous pouvez saisir l'idée. Je peux spécifier une procédure pour chaque paire de sous-types en deux variantes.

À noter également le dernier cas : il est interprété, « si nous avons Lest du côté gauche et toute autre chose du côté droit ».

J'ai vérifié comment le même problème d'appliquer une « fonction polymorphe » à un variant peut être résolu avec la bibliothèque Mach7. Mach7 est une bibliothèque expérimentale pour la correspondance de motifs, et notre problème de correspondance des sous-types du variant rentre dans son champ d'application. Mach7 ne nous demande aucune inversion de contrôle. Avec un certain nombre de macros astucieuses, elle nous permet d'écrire une instruction de type switch. Notre exemple ci-dessus avec la vérification de l'allocation de poids dans un conteneur donné ressemble à ceci :

Poids allocation_poids(const Cargaison& cargaison)
{
  Match (cargaison)
  {
  Case (C<Conteneur>())
    return match0.allocation_poids ;
  
  Case (C<ConteneurMultiple>())
    Poids poids(0);
    for (const Conteneur& cont : match0.conteneurs)
      poids += cont.allocation_poids;
    return poids;
  
  Case (C<Lest>())
    return Poids(0);
  }
  EndMatch
}

Nous pouvons voir que cela se rapproche vraiment d'une fonctionnalité intégrée dans le langage. En fait, Mach7 est une expérience qui a l'intention d'ouvrir la voie à une future extension du langage C++.

Une chose à observer est que nous ne choisissons pas le nom de la référence à Conteneur ou ConteneurMultiple. Le nom est choisi par la bibliothèque : match0. Il représente une correspondance à la variable à l'indice 0. On peut obtenir plus d'un indice si nous faisons un dispatch multiple, comme dans le cas de notre fonction qui vérifie si une charge donnée tient dans un conteneur donné. En Mach7, cette fonction ressemble à ceci :

bool tient(const Cargaison& cargaison, const UniteCharge& charge)
{
  Match (cargaison, charge)
  {
  Case (C<Conteneur>(), C<Paquet>())
    return match0.allocation_poids >= match1.poids
        && match0.allocation_volume >= match1.volume;
  
  Case (C<Conteneur>(), C<PaquetMultiple>())
    return bool("la totalité des paquets tient dans c");
  
  Case (C<ConteneurMultiple>(), C<Paquet>())
    for (const Conteneur& c : match0.conteneurs)
      if (tient(c, match1)) // appel recursif
        return true;
    return false;
  
  Case (C<ConteneurMultiple>(), C<PaquetMultiple>())
    return bool("la totalité des paquets tient dans l'ensemble de sous-conteneurs");
  
  Case (C<Lest>(), C<Paquet>())
    return false;
  
  Case (C<Lest>(), C<PaquetMultiple>())
    return false;
  }
  EndMatch
}

Ici, match0 représente une référence à un sous-type du variant Cargaison et match1 représente une référence à un sous-type du variant UniteCharge.

Une chose à retenir est que la construction de l'instruction switch étant extensible par sa nature, elle ne vérifie pas si nous avons couvert toutes les possibilités dans les branches de case, alors il pourrait être nécessaire d'y ajouter l'équivalent du cas par défaut pour couvrir un cas futur, lorsque nous ajouterons un nouveau sous-type à Cargaison. Dans Mach7, cela est orthographié Otherwise (« Sinon ») et notre premier exemple pourrait être réécrit ainsi :

Poids allocation_poids(const Cargaison& cargaison)
{
  Match (cargaison)
  {
  Case (C<Conteneur>())
    return match0.allocation_poids;
  
  Case (C<ConteneurMultiple>())
    return Poids(("calculer la réponse correcte...", 1));
  
  Case (C<Lest>())
    return Poids(0);
 
  Otherwise()       // lorsque rien d'autre ne correspond
    assert(false);  // ou selon le besoin
  }
  EndMatch
}

Vous pouvez voir ici un exemple complet d'utilisation de Boost.Variant avec Mach7.

J'ai exécuté un petit benchmark pour comparer la vitesse de Mach7 par rapport à celle des visiteurs Boost.Variant. Vous pouvez trouver le code d'essai ici. Les résultats montrent que le visiteur statique Boost.Variant est plus rapide que Mach7 : 1,65 fois sur GCC 4.9.2, et 2,93 fois sur MSVC 14.0. (Les deux tests ont été effectués sur Windows, avec les optimisations maximales activées).

Garantir que variant<A, B> stocke toujours un objet de type A ou B, en présence des exceptions, est plus difficile que l'on pourrait s'y attendre. Imaginez comment vous pourriez mettre en œuvre une affectation « mixte » comme ceci :

variant<A, B> va = A{};
variant<A, B> vb = B{};
va = vb;

Que signifie attribuer un B à un A ? Et comment mettre ça en œuvre s'il est possible qu'un constructeur de B lance une exception ? Pour une discussion détaillée à ce sujet, consultez la section « Vue d'ensemble de la conception » de la documentation de Boost.Variant. En bref, dans certains cas, l'affectation par copie du variant effectue une allocation sur le tas.

Une conception alternative du variant, proposée pour normalisation, n'alloue pas de la mémoire sur le tas au risque de compromettre dans une certaine mesure la garantie du jamais vide. Pour plus de détails, voir ici et ici. En bref, bien que vous ne puissiez pas créer un variant qui ne contienne ni un A, ni un B, vous pouvez vous retrouver dans un tel état si, lors d'une copie « mixte », une exception a été lancée. Une tentative de « visite » d'un tel variant aura pour résultat une exception.

Le point clé de cette introduction est que Boost.Variant, avec son concept de visiteur statique, offre un autre type de polymorphisme qui fait des compromis différents et vise des cas d'utilisation différents par rapport aux solutions basées sur la vtable (comme l'héritage de classe ou le type erasure à sémantique de valeur). Le tableau suivant résume les différences.

Lorsque votre cas d'utilisation correspond au « profil » de Boost.Variant, il vaut le coup de choisir cette bibliothèque à la place du polymorphisme classique basé sur la vtable. Elle est optimisée pour ce cas d'utilisation et plus performante que les autres solutions possibles ; elle est un peu plus facile à utiliser. Mais le plus important : elle reflète ce que vous modélisez.

Je suis reconnaissant à Yuriy Solodkyy pour m'aider à comprendre la mécanique et l'utilisation de la bibliothèque Mach7.

1. Eric Friedman, Itay Maman, La bibliothèque Boost.Variant.
2. David Sankel, “C++ Language Support for Pattern Matching and Variants”.
3. David Sankel, “A variant for the everyday Joe”.
4. Anthony Williams, “Standardizing Variant: Difficult Decisions”.
5. Axel Naumann, “Variant: a type-safe union (v4)”.
6. Yuriy Solodkyy, La bibliothèque Mach7.
7. Yuriy Solodkyy, Gabriel Dos Reis, Bjarne Stroustrup, “Open and Efficient Type Switch for C++”.
8. Vicente J. Botet Escriba, “C++ generic match function”.

Toute l'équipe de Developpez.com remercie sincèrement Andrzej Krzemieński qui nous a aimablement permis de traduire et de publier son tutoriel sur notre site. Nous tenons également à remercier Mishulyna pour la traduction, Luc Hermitte pour la relecture technique et f-leb pour la relecture orthographique.