10 nov. 2006

Etude du C++ Technical Report 1 - reference_wrapper

Cette série d'article étudie le C++ Technical Report 1 (TR1) d'une part du point de vue de son utilisation, et d'autre part tente de faire la lumière sur la manière dont sont implémentées les fonctionnalités qu'il offre. Ce billet étudie <reference_wrapper>.

Il doit être noté qu'à l'heure actuelle, il est difficile de tester les fonctionnalités du TR1 - pour la bonne raison que certains compilateurs ne supportent pas cette extension. Il est toutefois possible d'acheter une license de cette librairie chez Dinkumware Ltd., ou tout simplement d'utiliser boost (qui propose une certain nombre de classes du TR1, mais qui ne l'implémente pas complètement). Les dernières versions de GCC implémentent une partie du TR1. Visual C++ (même la version .NET 2005) ne propose les nouvelles interfaces définies. Quant aux compilateurs Borland (en particulier les versions Turbo Explorer gratuites), elles sont accompagnées de la suite Dinkumware[1].

Ah oui, dernière chose : inutile d'essayer de compiler ce code avec Visual C++ 6. Lorsque je parle de compilateurs, je parle bien évidemment de compilateurs C++, et VC6 n'en est pas un.


L'interface reference_wrapper

Lorsque j'ai commencé ce billet, j'avais une vague idée de là où je voulais aller. Mais bien qu'en apparence simple, le sujet a en fait des ramifications inattendues. C'est ce qui explique le fait qu'il soit si long - et le fait qu'il soit si long a eu bien évidemment une influence sur la durée de sa rédaction (vous l'avez compris : je suis en retard. J'aurais du poster ce billet jeudi dernier, et le voilà seulement...). Pour tout vous dire, j'ai du implémenter moi même les différents cas - sur la base de "on n'explique bien que ce que l'on comprend bien". Le résultat est à la hauteur de mes attentes : plus de 200 lignes de code relativement difficile à déchiffrer pour implémenter une classe proposant 5 méthodes en comptant les 2 constructeurs...[2]

Motivation

Avez vous déjà essayer de créer un vecteur de références ? Si ce n'est pas le cas, n'essayez même pas : le code ne compilera pas. Prenez par exemple la méthode push_back(), qui est définie comme prenant une référence constante sur le type paramète du template:

void push_back(const T& value);

Remplacez T par type&, et on obtient:

void push_back(const type&& value);

Une double référence - une entité qui ne peut pas exister en C++.

Sans compter les problèmes de compilation, la sémantique du vecteur créé serait de toute façon différente de celle d'un vecteur normal, rendant l'utilisation d'un tel vecteur pour le moins hasardeuse : que signifierais v[i] = j; ? Est-ce qu'on devrait modifier la valeur référencée par v[i] ou est-ce qu'on devrait remplacer la référence v[i] par la référence j ? Dans un vecteur normal, c'est la valeur qui est remplacée (donc, la référence dans ce cas). Mais le fonctionnement particulier des références ferait que dans ce cas, la référence ne serait pas remplacée, mais la valeur serait changée.

Le but de tr1::reference_wrapper[3] est de circonvenir à ces deux problèmes aux mieux. En encapsulant la référence dans une classe répondant à la sémantique Assignable, on résout ces deux problèmes en faisant d'une pierre deux coups.

Présentation

tr1::reference_wrapper est disponible via le fichier d'entête <functional> (dans les implémentation qui supportent le TR1 ; GCC implémente cette classe dans <tr1/functional>).

En elle même, l'interface de la classe tr1::reference_wrapper<T> est simple puisque seul un petit nombre de méthodes sont exposées :

  • deux constructeurs : un constructeur explicite qui prends en paramètre un T&, et un constructeur par copie qui prend en paramètre un const tr1::reference_wrapper<T>&. L'objet obéît à la sémantique CopyConstructible.
  • operator=(), qui fait de cette classe une classe Assignable, c'est à dire une classe qui utilise une sémantique de copie lors de l'assignation.
  • operator T&() const, qui autorise un transtypage automatique de tr1::reference_wrapper<T> vers T&
  • T& get() const, qui permet de récupérer une référence sur l'entité sous-jacente.

Outre ces méthodes, quatre fonctions hors classes ont été ajoutées afin de simplifier la création de tr1::reference_wrapper :

  • deux fonctions ref(T&) qui créent des objets tr1::reference_wrapper<T>
  • deux fonctions cref(const T&) qui créent des objets tr1::reference_wrapper<const T>

Ces quatre fonctions utilisent le type du paramètre pour déduire T automatiquement.

On notera que la classe ne possède pas de constructeur par défaut - tout comme il est impossible de construire une référence à partir de rien.

Enfin, la classe définit le type type comme étant le type de la référence (T). Si ce type est un pointeur sur une fonction (fonction seule avec un paramètre ou fonction membre avec aucun paramètre) ou si le type dérive de std::unary_function et/ou std::binary_function, alors tr1::reference_wrapper dérivera de std::unary_function et/ou std::binary_function et définira entre autre les types result_type, ainsi que les types des arguments. Dans le cas contraire, result_type est exposé uniquement si la classe paramètre expose aussi ce type - nous décrirons dans la partie traitant de l'implémentation comment on peut traiter ces cas particuliers.

Utilisation

Cette nouvelle classe peut être utilisée dans de nombreux cas. Le cas du vecteur de référence auquel j'ai fait allusion plus haut en est un exemple. Je peux écrire :

std::vector<std::tr1::reference_wrapper<some_class> > ref_vector;

Puisque le paramètre template n'est pas une référence, le vecteur résultant peut être compilé. Et puisque la classe tr1::reference_wrapper respecte la sémantique Assignable, ce vecteur peut être utilisé comme n'importe quel vecteur. Enfin, pas tout à fait : il existe une limitation de taille. Puisque la classe ne possède pas de constructeur par défaut, il est impossible de modifier la taille du vecteur en utilisant la fonction resize(size_t) - celle ci nécessitant que la classe paramètre possède un constructeur par défaut. On peut toutefois utiliser la version resize(size_t,const T&) et lui passer un paramètre qui sera par la suite inutilisé (par exemple: ref_vector.resize(10, std::tr1::ref(dummy_value));).

Il existe bien évidemment d'autres utilisations de cette classe. Partout là ou une référence ne peut être utilisée en tant que paramètre template, la classe tr1::reference_wrapper peut être utilisée. Nous verrons dans les billets ultérieurs de cette série que cette classe est régulèrement utilisée dans l'implementation du TR1.

L'autre utilisation privilégiée correspond au cas ou l'on souhaite modifier une référence pour non pas lui donner une nouvelle valeur mais pour la faire pointer vers une autre valeur. C'est possible avec un pointeur, mais impossible avec une référence. En d'autre terme, c'est le cas ou l'on souhaite travailler sur une référence qui répond à la sémantique Assignable. Avec tr1::reference_wrapper, rien n'est plus simple :

int a = 5, b = 10;
std::tr1::reference_wrapper<int> refw(a);
refw++; std::cout << refw.get() << std::endl;
refw = std::tr1::ref(b); refw++; std::cout << refw.get() << std::endl; std::cout << a << " - " << b << std::endl;

Informations sur l'implémentation

Notons tout d'abord que la "référence" sous-jacente est implémentée non pas grâce à une référence (ce qui aurait pour effet d'interdire la sémantique Assignable de la classe) mais grâce à un pointeur. La copie de la valeur du pointeur permet ainsi de créer plusieurs objets tr1::reference_wrapper qui référence la même entité.

L'un des points particulier de tr1::reference_wrapper réside dans sa définition. En effet, dans les cas suivants :

  • si le type sous-jacent dérive de std::unary_function ou std::binary_function,
  • si le type sous-jacent est un type pointeur sur fonction qui prend un ou deux arguments,
  • si le type sous-jacent est un type pointeur sur fonction membre qui prends un ou deux arguments,

Alors tr1::reference_wrapper doit dériver de std::unary_function et/ou std::binary_function.

Détection statique de l'héritage

Comment implémenter ces cas ? Considérons le premier point (T dérive de std::unary_function ou std::binary_function). Nous avons donc besoin de vérifier le lien d'héritage entre T et ces deux classes. Notre problème est que nous devons réaliser cette opération au moment de la compilation, car c'est à ce moment que nous avons de cette information. A ce moment, le compilateur ne peut évaluer que des expressions constantes et notre héritage supposé est une information qui ne nous est pas directement accessible. Fort heureusement, elle l'est de manière indirecte. Considérons le code suivant :

class B : public A { /* ... */ };
void f (A *); void f(int);

La fonction surchargée f() peut être appelée en lui passant un objet de type B. Quand est-ce que le choix de la fonction à appeler est-il effectué ? Vous l'avez deviné : au moment de la compilation. Bien évidement, cette seule remarque ne suffit pas, car nous ne somme pas capable à première vue de différencier les deux fonctions : de plus, si le choix de l'appel est effectué au moment de la compilation, le résultat de la fonction ne peut être connu qu'au moment de l'exécution - ce qui ne nous aide pas vraiment. Mais allons plus loin : quelles sont les différences qui peuvent exister lorsqu'on compare deux fonctions qui prennent chacun un unique argument et qui ont le même nom ? la première est triviale, et c'est celle qui permet au compilateur de faire son choix - il s'agit bien évidemment du type de l'argument. Il existe une autre différence, plus subtile : le type de retour de la fonction. Reprenons notre code :

class B : public A { /* ... */ };
int f (A *); short f(int);

Si nous sommes maintenant capable de distinguer le type de retour de la fonction, alors nous devrions être capable de savoir quelle fonction a été appelée. Mais comment faire pour déterminer le type au moment de la compilation ? La réponse à cette question est difficile, mais heureusement il ne nous est pas nécessaire de la connaitre. En effet, plutôt que de déterminer le type de retour, nous pouvons parfaitement utiliser une caractéristique intrinsèque de celui-ci : sa taille, via l'opérateur sizeof(). Là, nous avons une chance incroyable puisque sizeof() est évalué au moment de la compilation, et se base non pas sur la valeur qui est testée mais sur le type statique de celle ci. Or le type statique résultant de l'appel d'une fonction est le type de retour de la fonction. Ainsi, le code

B b;
std::cout << sizeof(f(&b));

Affichera la taille du type de retour de la fonction appelée - qui est dans notre cas int f(A*). Nous avons donc résolu notre plus gros problème.

Il nous reste toutefois deux petits problèmes à surmonter. Premièrement, je dois pouvoir être sur de la taille du type de retour. Le cas que j'ai choisi (int contre short) est ambigu car rien ne dit dans la norme que la taille d'un int doit être supérieure à celle d'un short (c'est même le contraire : sizeof(int) >= sizeof(short), donc un vendeur particulier peut parfaitement implémenter des types de même taille). En fait, la seule taille dont nous soyons sure est celle du type char - la norme C++ nous dictant que sizeof(char) == 1. On peut donc surmonter notre premier problème en écrivant :

typedef char size_1[1];
typedef char size_2[2];
size_1& f(A*);
size_2& f(int);

Notre second problème concerne le type de l'objet passé en paramètre. Nous souhaitons faire la différence entre un objet qui dérive de A et... et quoi au fait ? Certainement pas un int - le choix serait bien trop restrictif. Le fait est que nous ne connaissons pas le type de l'objet passé en paramètre - rappelez vous, nous souhaitons en découvrir ses caractéristiques. Cela peut donc être n'importe quoi. Quel doit être le type du paramètre de la seconde version de f() pour être capable de recevoir n'importe quel type d'objet (type scalaire, pointeur, etc) ? La réponse n'est pas void* (parce qu'il n'y a pas de transtypage implicite d'un type scalaire vers un type pointeur). La réponse, héritée du C, est... qu'il faut utiliser la forme variadique de la fonction - c'est à dire que la fonction va prendre un nombre quelconque d'arguments dont le type n'est pas spécifié.

size_1& f(A *); // catch objects that inherit A
size_2& f(...);   // catch all !

On peut maintenant mettre en forme nos classes de vérification, à la manière des classes d'identification de type utilisées en métaprogrammation.

template <class T> class inherit_unary_function
{
  typedef char size_1[1];
  typedef char size_2[2];
template <class A, class R> static size_1& test(const std::unary_function<A,R> *); static size_2& test(...);
public: static const bool value = (sizeof(test((T*)0)) == 1); }

Notez que je n'ai pas besoin de définir le corps des fonctions déclarées - la fonction n'est en fait jamais appelée puisque tout est réalisé au moment de la compilation. Bien évidemment, la même méthode peut être utilisée pour découvrir le lien d'héritage avec std::binary_function. Nous pouvons alors utiliser d'autres techniques de métaprogrammation pour décider de faire dériver une classe proxy reference_wrapper_base<> de std::unary_function et/ou std::binary_function, en se servant de la constante inherit_unary_function<>::value pour nous aider. Remarquez aussi que puisque value est statique, j'ai du aussi définir les fonctions test() comme étant statiques elles aussi.

Cette technique porte un nom : SFINAE, qui est l'acronyme de ''Subsitution Failure Is Not An Error". Vous pouvez en apprendre plus sur SFINAE et d'autres techniques de métaprogrammation sur ce site de cours.

Gestion des pointeurs sur fonction et pointeurs sur fonction membre

Les deux autres points, bien que non triviaux (puisqu'ils font aussi appels à des techniques de métaprogrammation) sont quand à eux beaucoup plus simples à implémenter - en fait, le principe consiste à spécialiser une classe particulière de manière plus pointue en utilisant des spécialisations de templates :

template <class __type> class base { };

Je peux ensuite spécialiser base pour extraire le type de retour et l'argument d'un pointeur sur fonction - ce qui me permet de faire dériver base de std::unary_function.

template <class A, class R> class base<R(*)(A)> :
  public std::unary_function<A,R> { };

En créant tous les cas nécessaires, je peux aisément décider dans quel cas je vais dériver de std::unary_function ou std::binary_function, et dans quel cas je ne vais dériver de rien.

Le problème de result_type

Pour finir, SFINAE est aussi utilisé pour déterminer si la classe paramètre expose un type nommé return_type ou non. Puisque qu'il s'agit de vérifier l'existence d'un type, nous devons affiner la technique précédemment décrite. En effet, je ne peux pas écrire

template <class T> class has_result_type
{
   static size_1& test(typename T::result_type*);  // (1)
   static size_2& test(...);
public:
   static const bool value = (sizeof(test((T*)0)) == 1);
};

Premièrement, ça n'a pas de sens. Deuxièmement, la ligne (1) va générer une erreur si T::result_type n'existe pas - ce qui n'est pas notre but. Heureusement, il est possible de passer outre ce problème en utilisant une indirection supplémentaire.

template <class T> class has_result_type
{
   template <class wrapped> class wrapper { };
   template <class u> static size_1& 
     test(wrapper<typename u::result_type>*); // (1)
   template <class u> static size_2& test(...); // (2)
public:
   static const bool value = (sizeof(test<T>(0)) == 1);
};

Comment cela peut-il fonctionner et ne pas générer d'erreur ? Tout simplement parce que la méthode test étant une méthode template, le compilateur cherche la méthode qui correspond le mieux à l'appel de fonction qui est fait et il n'instanciera quelle celle-là. Lorsque T::result_type existe, (1) est choisi car même si (2) est valide, le fait d'utiliser la construction variadique fait qu'au niveau du compilateur, elle est de priorité inférieure à toute autre fonction pouvant correspondre. Lorsque T::result_type n'existe pas, (1) ne peut pas être un choix valide. La méthode n'est donc pas instanciée (c'est la raison pour laquelle elle ne génère pas d'erreur de compilation), et (2) convient et est choisie.

Conclusion

Vous devez commencer à le sentir, ce sont des techniques de métaprogrammation poussées qui ont permis le développement de la librairie TR1. Ces techniques, bien que non triviales, n'en restent pas moins relativement aisées à comprendre, une fois que les clefs de décodage sont en notre possession. Pour avoir un plus large aperçu du code de cette classe, je vous conseille de télécharger la dernière version de la libstdc++ de GCC - elle contient un répertoire tr1 dans lequel vous trouverez le code de cette classe.

Vous pouvez aussi télécharger mon implémentation (qui reste quand même proche de celle de GCC) ici.

Notes

[1] honnêtement, j'en suis encore à télécharger Turbo C++ Explorer au moment ou j'écris ces lignes - je ne sais donc pas si cette version de la librairie Dinkumware contient leur implémentation du TR1

[2] plus exactement : 226 lignes.

[3] cette classe est basée sur la classe éponyme de boost, bien que certaines méthodes en ait été supprimée dans le processus d'étude.

Commentaires

1. Le vendredi, novembre 17 2006, 00:42 par Emmanuel Deloget

Il était évident que mon implémentation de std::tr1::reference_wrapper<> allait être truffé d'erreurs et d'omissions. Fort heureusement, je m'en suis rendu compte trop tard, et je vous ait donc livré un code comportant un certain nombre de défauts, dont voici la liste :

  • les fonctions std::tr1::ref() et std::tr1::cref() ne sont pas définies. Cette erreur est simple à corriger.
  • plus ennuyeux, reference_wrapper<>::result_type n'est pas traité correctement. En effet, result_type devrait être défini à partir du moment où le type encapsulé est un pointeur sur fonction ou un pointeur sur une fonction membre. Hors, dès lors que l'on définit un reference_wrapper<> autour d'une de ces deux entités de manière à ne pas tomber dans les cas "normaux" (une ou deux paramètres avec un type de retour), result_type n'est pas défini.
  • encore plus ennuyeux, lorsque le type encapsulé dérive à la fois de std::unary_function<> et std::binary_function<> et que les result_type de ces deux classes sont différents, reference_wrapper<>::result_type n'est pas défini correctement. Cela se complique notamment lorsqu'il faut prendre en compte le fait que la classe encapsulée peut très bien redéfinir result_type - dans ce cas, c'est cette définition qu'il faut utiliser. Hors à l'heure actuelle, je ne vois pas encore de moyen de détecter ce cas...
  • et pour finit, terriblement ennuyeux : l'invocation des fonctions encapsulées (soit par le biais d'un pointeur de fonction, d'un pointeur sur une fonction membre où d'un functor) n'est pas implémenté du tout.

Comme vous le voyez, la liste des défauts est loin d'être minime.

J'espère toutefois vous fournir une version partiellement (voire totalement corrigée) rapidement - hélas, je n'ai pas la possibilité de vous indiquer dès maintenant une date fixe. Certain de ces défauts ne sont en effet pas des plus simples à corriger (en particulier le problème de l'invocation).

Ajouter un commentaire

Les commentaires peuvent être formatés en utilisant une syntaxe wiki simplifiée.

Fil des commentaires de ce billet