L'Argument-Dependent Lookup (ADL)

Il existe en C++ une règle un peu particulière et quelque peu méconnue qu'on nomme l'Argument-Dependent Lookup, ou ADL (on le nommera parfois le Koenig Lookup, du nom de son auteur présumé, Andrew Koenig, mais il semble que lui-même ne puisse s'en attribuer la paternité : http://www.drdobbs.com/cpp/a-personal-note-about-argument-dependent/232901443). Cet ensemble de règles guide le compilateur lorsqu'il cherche les fonctions auxquelles nous faisons référence en programmant, et est en général suffisamment naturel pour qu'on ne lui porte pas attention et que tout fonctionne normalement...

Évidemment, dans des cas plus subtils, comme ceux impliquant plusieurs espaces nommés ou de la programmation générique, l'application naïve de ces règles de base peut surprendre ou donner des résultats qui rendent perplexes.

Le présent article se veut un survol d'ADL, pour aider à comprendre à la fois ce que c'est, pourqui cela fonctionne en général, et quoi faire pour survivre quand on sort des cas typiques et qu'il faut comprendre un peu mieux ce qui se passe.

La base – pourquoi ADL, et comment cela fonctionne-t-il?

Imaginons un programme simple comme celui-ci :

#include <iostream>
#include <string>
int main() {
   std::string s = "J'aime mon prof!";
   std::cout << s << std::endl; 
}

Il semble évident que ce programme fonctionne, et qu'il devrait fonctionner. Toutefois, cette apparente simplicité masque une réalité, c'est à dire qu'en pratique, le recours à l'opérateur << pour projeter un const std::string& comme s sur la sortie standard sollicite l'opérateur suivant :

std::ostream& operator<<(std::ostream&,const string&);

... mais comment le compilateur trouve-t-il la fonction operator<<() dans ce cas? Nous n'avons pas inséré d'instructing using pour la rendre disponible, après tout? Vous ne serez pas étonné(e), dans le contexte du présent article, de savoir que l'identification implicite de cette fonction par le compilateur est le fruit de l'application des règles d'ADL.

Les fonctions accessibles par voie d'ADL pour un type donné font, techniquement, partie de l'interface publique de ce type.

De maniere plus générale, supposons cet extrait de code :

namespace demo_adl {
   // une classe string maison; son nom complet est demo_adl::string
   class string {
      // ...
   public:
      string(const char*);
      // ...
   };
   void f(string); // fonction f acceptant un demo_adl::string en paramètre
}
int main() {
   demo_adl::string s = "J'aime mon prof!";
   f(s); // on espere demo_adl::f(demo_adl::string), n'est-ce pas?
}

Ici, bien que demo_adl::f() ne soit pas rendue accessible directement par une instruction using, ADL nous y donnera implictement accès en reconnaissant que le f() le mieux placé pour prendre en charge un paramètre de type demo_adl::string est demo_adl::f().

De la même manière, l'exemple suivant utilisera implicitement std::getline() pour gérer la lecture sur une std::string, sans que nous ne devions expliciter l'appartenance de getline() à l'espace nommé std :

#include <iostream>
#include <string>
#include <algorithm>
int main() {
   std::string s;
   if (getline(std::cin, s))
      std::cout << s << std::endl;
}

Évidemment, il faut gérer ces situations avec prudence. Par exemple, le programme ci-dessous ne compile pas dû à un appel ambigu à f() dans main() :

#include <iostream>
namespace demo_adl {
   class string {
      // ...
   public:
      string(const char*) {}
      // ...
   };
   void f(string)
      { std::cout << "demo_adl::f(demo_adl::string)" << std::endl; }
}
void f(demo_adl::string)
   { std::cout << "::f(demo_adl::string)" << std::endl; }
int main() {
   demo_adl::string s = "J'aime mon prof!";
   f(s); // ambigu!
}

Citons Herb Sutter dans son introduction de http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2103.pdf, qui résume bien ADL, son rôle avec C++ et son absence dans certains autres langages connus :

ADL is a result of having a language that supports both namespaces and nonmember functions, especially when some functions that clearly are part of a type's public interface (e.g., operator<<) are required to be nonmembers.

Specifically, ADL exists to treat nonmember and member name lookup more uniformly. The principle behind ADL is that if you call member functions they naturally "come along" with an object for name lookup:

o.f(); // look into the scope of o's type, no using needed

and nonmember functions can be equally part of the interface and should be treated the same way:

f(o); // look into the namespace containing o's type, no using needed

because some functions on a type must be nonmembers (notably operators << and >>) and clearly ought to be first-class members of the type's interface. Languages like C# and Java don't have this problem only because there are no nonmember methods. ADL exists because people realized that the nonmember function parts of a type's interface ought to "come along for the ride" and be naturally usable just as the member functions already come along for free (because of the .mf() and ->mf() syntax which implies the scope of the object's type).

Exemples de saine utilisation

Imaginons le cas d'une classe pour laquelle il existe une version spécialisée de l'important algorithme swap(). Puisque cette opération joue un rôle clé dans un vaste éventail d'algorithmes (par exemple les tris) et dans plusieurs implémentations de l'opérateur d'affectation, il est probable que l'on souhaite recourir en tout temps à la meilleure version possible de swap() pour un type donné – et il est raisonnable de supposer que l'implémentation faite sur mesure pour ce type soit celle à privilégier pour lui.

Sachant cela, l'appel suivant dans main() est une forme de pessimisation :

namespace demo_adl {
   class string {
      // ...
   public:
      string(const char*);
      // ...
   };
   void swap(string&, string&); // swap() sur deux demo_adl::string&
}
#include <algorithm>
int main() {
   demo_adl::string s0 = "J'aime mon prof",
                    s1 = "Moi aussi";
   std::swap(s0, s1); // vilain
}

En effet, en forçant le passage par le std::swap() générique, la version sur mesure ne sera pas considérée (par choix explicite du code client). Une meilleure utilisation de swap() serait la suivante :

namespace demo_adl {
   class string {
      // ...
   public:
      string(const char*);
      // ...
   };
   void swap(string&, string&); // swap() sur deux demo_adl::string&
}
#include <algorithm>
int main() {
   using std::swap; // rendre std::swap disponible, de manière optionnelle
   demo_adl::string s0 = "J'aime mon prof",
                    s1 = "Moi aussi";
   swap(s0, s1); // prendra demo_adl::swap() s'il existe, std::swap() sinon
}

Ici, le using std::swap() n'est pas nécessaire car nous savons que la version spécialisée de swap() pour une demo_adl::string est implicitement accessible par ADL. Toutefois, examinons une version générique du même problème :

namespace demo_adl {
   class string {
      // ...
   public:
      string(const char*);
      // ...
   };
   void swap(string&, string&); // swap() sur deux demo_adl::string&
}
#include <algorithm>
template <class T>
   void permuter(T &a, T &b) {
      using std::swap; // le rendre disponible juste au cas
      swap(a, b); // utilisera la version sur mesure si elle existe, et std::swap sinon
   }
int main() {
   demo_adl::string ds0 = "J'aime mon prof",
                    ds1 = "Moi aussi";
   permuter(ds0, ds1); // prendra demo_adl::swap()
   std::string s0 = "J'aime mon prof",
               s1 = "Moi aussi";
   permuter(s0, s1); // prendra std::swap()
}

Quelques cas irritants

ADL est un mécanisme gourmand, parfois trop, et pour lequel les gens responsables d'écrire et de tenir à jour les compilateurs ont dû interpréter des passages... perfectibles du standard C++. Le texte http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2103.pdf met de l'avant un certain nombre de cas dégénérés pour lesquels il est traditionnellement ardu d'écrire du code portable.

Dans une présentation de 2013, http://meetingcpp.com/tl_files/2013/talks/Keynote-cxx11-library-design-ericniebler.pdf, Eric Niebler relate quelques cas patents où ADL interfère avec ce qu'on pourrait considérer comme le comportement « normal » ou attendu d'un compilateur cherchant les bonnes versions de diverses fonctions, et met de l'avant quelques techniques pour contourner ces irritants.

Lectures complémentaires

Cet article n'est qu'un survol. Pour en savoir plus sur le sujet, quelques suggestions de lecture :


Valid XHTML 1.0 Transitional

CSS Valide !