C++ : la priorisation par contraintes

L'idée de sélectionner le plus contraint de deux (ou plusieurs) templates de fonctions provient de la STL, où nous pouvons avoir deux versions de l'algorithme std::advance : l'une s'applique à tout type d'itérateur (elle est donc déjà contrainte par le concept InputIterator), et l'autre s'applique uniquement à des types qui modélisent RandomAccessIterator, en offrant de meilleures performances. En C++ 89, cette idée d'algorithme plus spécialisé fut appliquée grâce à des techniques telles que le « tag dispatching »(1). En C++ 17, nous disposons de if constexpr, qui élimine souvent le besoin de fournir une surcharge, dans les cas où l'ensemble des spécialisations disponibles est fini et connu dès le départ. Pour les autres cas, C++ 20 offre une solution consacrée : la priorisation de templates par contraintes.

La mise en œuvre des concepts, telle qu'elle était prévue pour C++ 11, incluait une notion de « raffinement de concept » : le concept RandomAccessIterator pouvait explicitement déclarer qu'il était un raffinement du concept BidirectionalIterator et, de ce fait, le compilateur savait quelle surcharge choisir, si l'une était contrainte par RandomAccessIterator et l'autre par BidirectionalIterator. Par contraste avec cela, l'extension « Concepts Lite » de C++ 20 a adopté une autre démarche : deux déclarations de templates contraints peuvent être priorisées en fonction de leurs contraintes. Par exemple, en se basant sur le concept suivant :

template <typename T>
concept Trivial = std::is_trivial_v<T>;

et les deux surcharges de la fonction fon, ci-dessous :

template <typename T, typename U>
  requires Trivial<T>
void fon(T t, U u) { std::cout << "général"; }

template <typename T, typename U>
  requires Trivial<T> && Trivial<U>
void fon(T t, U u) { std::cout << "spécial"; }

Si je tente d'invoquer fon avec deux arguments triviaux :

fon(1, 2);

C'est la seconde surcharge qui est choisie, car elle est plus contrainte. Comme vous l'avez vu dans le précédent billet, l'unité lexicale && à l'intérieur de la clause requires n'est pas un opérateur « et logique », mais une conjonction de contraintes. La conjonction d'une contrainte P avec une autre contrainte rend la déclaration plus contrainte (c.-à-d. plus spécialisée) qu'une déclaration avec une unique contrainte P.

Mais si nous substituons le trait de type std::is_trivial_v au concept, dans nos deux déclarations :

template <typename T, typename U>
  requires std::is_trivial_v<T>
void fon(T t, U u) { std::cout << "général"; }
 
template <typename T, typename U>
  requires std::is_trivial_v<T> && std::is_trivial_v<U>
void fon(T t, U u) { std::cout << "spécial"; }

Le même appel :

fon(1, 2);

devient alors ambigu et déclenche une erreur de compilation. Ceci paraît surprenant et, pour l'expliquer, nous devons comprendre ce qui arrive lorsque deux séquences de caractères du code source représentent la même contrainte. Car c'est là le cœur du problème : dans le premier exemple, Trivial<T> à la ligne 2 et Trivial<T> à la ligne 6 représentent la même contrainte ; pourtant, dans le second exemple, std::is_trivial_v<T> à la ligne 2 et std::is_trivial_v<T> à la ligne 6 représentent deux contraintes différentes, bien qu'elles résultent en la même valeur.

Ce mécanisme fonctionne de la façon suivante. L'intégralité de la contrainte associée à une fonction donnée se décompose en conjonctions et disjonctions de « contraintes atomiques ». Une contrainte atomique est une expression (qui peut être évaluée à la compilation) de type bool qui ne peut plus être décomposée. Une telle décomposition fonctionne comme suit :

1. P && Q se décompose en la conjonction des contraintes P et Q.
2. P || Q se décompose en la disjonction des contraintes P et Q.
3. La présence du nom du concept avec des arguments de patron spécifiés, comme dans Trivial<T>, est remplacée par la définition du concept.

Suite à cette décomposition, deux contraintes atomiques sont considérées comme identiques si elles sont représentées exactement par la même expression exactement au même emplacement dans le code source. Ainsi, si nous reprenons l'exemple avec les traits de type :

template <typename T, typename U>
  requires std::is_trivial_v<T>
void fon(T t, U u) { std::cout << "général"; }
 
template <typename T, typename U>
  requires std::is_trivial_v<T> && std::is_trivial_v<U>
void fon(T t, U u) { std::cout << "spécial"; }

La première surcharge a une contrainte atomique P représentée par l'expression std::is_trivial_v<T> à la ligne 2. La seconde a deux contraintes atomiques : la première, Q, est représentée par l'expression std::is_trivial_v<T> de la ligne 6. Bien qu'elles soient représentées par la même séquence de caractères, ces expressions sont définies à des emplacements différents – l'un se trouve à la ligne 2, l'autre à la ligne 6 – et c'est seulement pour cela qu'elles sont considérées comme des contraintes atomiques différentes. Par conséquent, la contrainte de la première surcharge est P, la contrainte de la seconde surcharge est Q ∧ R, sans lien entre les trois contraintes atomiques. De ce fait, nous ne pouvons pas déterminer laquelle de ces contraintes est la plus stricte.

Analysons à présent l'exemple avec les concepts :

template <typename T>
concept Trivial = std::is_trivial_v<T>;

template <typename T, typename U>
  requires Trivial<T>
void fon(T t, U u) { std::cout << "général"; }

template <typename T, typename U>
  requires Trivial<T> && Trivial<U>
void fon(T t, U u) { std::cout << "spécial"; }

La première surcharge est contrainte par un seul concept. Un identifiant de concept (c.-à-d. un concept associé à des arguments), tel que Trivial<T>, n'est pas traité en tant qu'expression. Afin de déterminer les contraintes atomiques, il nous faut regarder à l'intérieur. Là, nous trouvons une contrainte atomique P représentée par l'expression std::is_trivial_v<T> de la ligne 2. Si nous analysons la contrainte de la seconde surcharge, nous obtenons une conjonction de contraintes, constituée de deux identifiants de concepts. En regardant à l'intérieur de la première, nous obtenons une contrainte atomique Q représentée par l'expression std::is_trivial_v<T> de la ligne 2. Ainsi, P et Q sont représentées par la même expression (séquence de caractères) exactement au même emplacement (ligne 2) et sont par conséquent considérées comme identiques. Ainsi, la contrainte de la première surcharge est P, et celle de la seconde surcharge est P ∧ R. Nous pouvons ainsi conclure que la seconde contrainte est plus forte.

Ce qui précède illustre la première propriété spéciale des concepts. Un identifiant de concept – c'est-à-dire un concept avec tous ses paramètres spécifiés, comme dans Trivial<T> – n'est pas une expression : c'est un alias pour une expression définie ailleurs : nommément, c'est la définition du concept. C'est assez analogue aux alias de template, qui sont des alias de types. Les alias de template, au même titre que les concepts, sont des templates qui ne sont jamais instanciés. Ce qui signifie cela :

1. Leur instanciation ne peut jamais échouer (mais l'instanciation de ce dont ils sont l'alias peut néanmoins échouer) ;
2. Ils ne peuvent pas être spécialisés.

Répétons-le, std::is_trivial_v<T> est une expression de type bool. Trivial<T> est un alias pour une expression de type bool.

À présent, réécrivons nos surcharges contraintes par des concepts, mais sous une notation plus succincte :

template <typename T>
concept Trivial = std::is_trivial_v<T>;
template <Trivial T, typename U>
void fon(T t, U u) { std::cout << "général"; }
template <Trivial T, Trivial U>
void fon(T t, U u) { std::cout << "spécial"; }

Cette fois, le concept apparaît entre chevrons, et on ne lui passe pas d'arguments. Fonctionnellement, c'est équivalent au précédent exemple : un appel à fon(1, 2) sélectionnera aussi la seconde surcharge, mais la différence réside uniquement dans la notation. Ceci illustre deux choses. Premièrement, c'est une autre propriété particulière des concepts qui est présentée ici : ils peuvent être utilisés pour adjoindre des contraintes à des templates, sans recourir à la clause requires.

Deuxièmement, bien qu'il n'y ait pas de && en vue, nous avons tout de même une conjonction de deux contraintes atomiques. Donc, bien qu'une disjonction de contraintes ne puisse être énoncée que par l'opérateur ||, la conjonction de contraintes, elle, peut être énoncée de deux manières : soit par l'opérateur &&, soit en plaçant les contraintes à plus d'un endroit dans la déclaration du template. Le code suivant pourrait aussi remplacer la seconde surcharge, avec le même effet :

template <Trivial T, typename U>
    requires Trivial<U>
void fon(T t, U u) { std::cout << "spécial"; }

En fait, nous pouvons utiliser une notation plus succincte pour déclarer des patrons contraints par des concepts :

void fon(Trivial auto t, auto u)
{ std::cout << "général"; }
void fon(Trivial auto t, Trivial auto u)
{ std::cout << "spécial"; }

Ceci nous permet de nous débarrasser des noms de types T et U. Le fait d'utiliser auto dans la liste de paramètres indique que nous déclarons un template. De plus, placer un nom de concept avant auto ajoute une contrainte pour le type du paramètre.

Nous avons vu que P ∧ Q était plus contraignant que P. De façon similaire, P est plus contraignant que P ∨ Q. À présent, en guise d'exercice, nous allons nous intéresser à la forme la plus générique de cette relation entre contraintes. Le Standard, pour définir ceci, introduit la notion d'inclusion de contrainte. La définition complète se trouve ici, elle est reproduite ci-dessous pour des raisons pratiques. Nous l'illustrerons ensuite par un exemple.

Pour illustrer ce mécanisme, prenons le modèle de concepts ci-dessous, pour une hypothétique bibliothèque de calculs mathématiques.

template <typename T>
concept Scalar = std::is_scalar_v<T>;

Le concept Scalar représente tous les types natifs pouvant subir des opérations arithmétiques de base telles que l'addition, la multiplication et autres. En plus des types natifs, cette bibliothèque peut apprendre des « types mathématiques » définis par l'utilisateur. Afin de commander à la bibliothèque de reconnaître mon type (appelons-le big_int, par exemple), je dois spécialiser un template :

// fourni par la bibliothèque :
template <typename T>
struct mathematical_traits
{
    constexpr static bool customized = false;
};
 
// personnalisé par l'utilisateur :
template <>
struct mathematical_traits<big_int>
{
    constexpr static bool customized = true;
};

Cette personnalisation est reconnue par un autre concept de la bibliothèque :

template <typename T>
concept CustomMath = mathematical_traits<T>::customized;

Enfin, nous avons un concept (probablement le plus utile) qui reconnaît tout type mathématique, natif ou défini par l'utilisateur :

template <typename T>
concept Mathematical = Scalar<T> || CustomMath<T>;

Les fonctions de la bibliothèque utilisent ces concepts comme des contraintes :

template <Mathematical T, Mathematical U>
void fon(T const&, U const&) { std::cout << "Q"; }

La fonction fon peut être appliquée à toute paire de types arithmétiques, différents ou non. Toutefois, une implémentation plus rapide peut être développée si les deux types T et U représentent un type mathématique de la même manière, c'est-à-dire qu'ils sont soit tous deux des types scalaires, soit tous deux des types personnalisés grâce à mathematical_traits. La déclaration de cette surcharge optimisée se présente comme suit :

template <typename T, typename U>
  requires (Scalar<T> && Scalar<U>) 
        || (CustomMath<T> && CustomMath<U>)
void fon(T const&, U const& ) { std::cout << "P"; }

Désormais, lorsque l'utilisateur invoque la fonction fon(1, 1), et que les deux surcharges sont des candidates valables, le compilateur doit déterminer si l'une d'elles, au travers des contraintes, est plus spécialisée que l'autre (elle sera alors sélectionnée) ou s'il y a ambiguïté. Nous allons effectuer ce processus manuellement.

Tout d'abord, nous allons déterminer si la contrainte de la seconde surcharge (celle qui affiche « P ») inclut celle de la première. Nous appellerons Q la contrainte de la première surcharge, et P celle de la seconde. Pour cela, nous devons représenter P sous sa forme disjonctive (des « ET » liés par l'opérateur « OU »), et Q sous sa forme conjonctive (des « OU » liés par l'opérateur « ET ») :

P = P1 ∨ P2
P1 = Scalar<T> ∧ Scalar<U>
P2 = CustomMath<T> ∧ CustomMath<U>

Q = Q1 ∧ Q2
Q1 = Scalar<T> ∨ CustomMath<T>
Q2 = Scalar<U> ∨ CustomMath<U>

Nous devons à présent démontrer que les propositions suivantes sont toutes vérifiées :

• P1 inclut Q1 ;
• P2 inclut Q1 ;
• P1 inclut Q2 ;
• P2 inclut Q2.

Pour démontrer que Pi inclut Qj, nous devons trouver une clause conjonctive Pia dans Pi et une clause disjonctive Qjb dans Qj telles que Pia soit identique à Qj. Et, en effet, nous avons :

• pour P1 et Q1 : Scalar<T> ;
• pour P2 et Q1 : CustomMath<T> ;
• pour P1 et Q2 : Scalar<U> ;
• pour P2 et Q2 : CustomMath<U>.

Par conséquent, la contrainte P inclut la contrainte Q. Mais pour empêcher toute ambiguïté lors de la résolution de la surcharge, nous devons aussi démontrer que Q n'inclut pas P. Tentons de représenter Q sous sa forme disjonctive, et P sous sa forme conjonctive. C'est possible, mais plus long et, dans le cas de P, assez peu intuitif :

Q = Q1 ∨ Q2 ∨ Q3 ∨ Q4
Q1 = Scalar<T> ∧ Scalar<U>
Q2 = Scalar<T> ∧ CustomMath<U>
Q3 = CustomMath<T> ∧ Scalar<U>
Q4 = CustomMath<T> ∧ CustomMath<U>

P = P1 ∧ P2 ∧ P3 ∧ P4
P1 = Scalar<T> ∨ CustomMath<T>
P2 = Scalar<U> ∨ CustomMath<T>
P3 = Scalar<T> ∨ CustomMath<U>
P4 = Scalar<U> ∨ CustomMath<U>

Ici, nous pouvons trouver des couples de Qi et Pj qui n'ont pas de contrainte atomique en commun : par exemple, Q2 et P2. Q n'inclut donc pas P. De ce fait, l'inclusion dans notre cas ne fonctionne que dans un sens, ce qui signifie que la surcharge qui affiche « P » correspond mieux, et sera donc sélectionnée.

Ceci illustre le nombre de calculs qu'un compilateur doit effectuer durant la résolution de surcharge (ou de spécialisations partielles de patrons de classes correspondants) lorsque nous posons des contraintes trop compliquées, basées sur des conjonctions et disjonctions. Les conjonctions sont généralement inévitables : nous avons vu avec quelle facilité elles étaient créées même lorsque nous ne mettions l'unité lexicale && nulle part. Il est par conséquent judicieux d'éviter les disjonctions de contraintes lorsque c'est possible, pour ne pas accroître les temps de compilation.

Pour conclure, étant donné ce que nous avons vu, tentons d'expliquer pourquoi le concept std::same_as est défini d'une manière étrange, présentée ci-dessous :

namespace std
{
  template <typename X, typename Y>
  concept __same_as = is_same_v<X, Y>;

  template <typename X, typename Y>
  concept same_as = __same_as<X, Y> && __same_as<Y, X>;
}

Le nom __same_as est un détail interne et, en réalité, peut être différent. Toutefois, l'existence du concept intermédiaire et l'usage de la conjonction sont garantis par le Standard C++. On pourrait se demander si la définition suivante ne serait pas suffisante, sachant que le trait de type std::is_same_v est symétrique :

template <typename X, typename Y>
concept Same = std::is_same_v<X, Y>;

Afin de comprendre pourquoi ceci n'est pas suffisant, voyez ci-dessous les deux surcharges de patrons de fonctions, qui sont basées sur notre concept :

template <typename T>
using value_type = typename T::value_type;
template <typename T, typename U>
  requires Same<value_type<T>, value_type<U>>
void fon(T&, U&) {}
template <typename T, typename U>
  requires Same<value_type<U>, value_type<T>>
        && std::regular<value_type<U>>
void fon(T&, U&) {}

Elles requièrent toutes deux que T et U aient un type imbriqué value_type et que les deux typedef nomment le même type. En outre, la seconde surcharge requiert également que ce type soit usuel (c.-à-d. qu'on puisse le copier, et vérifier son égalité avec un autre type). L'objectif n'est pas nécessairement d'offrir plus de rapidité, mais peut-être de permettre d'appliquer des contrôles de précaution supplémentaires, tels que copier la valeur au début et la comparer à la fin. L'ordre de T et U est différent dans la seconde surcharge à l'intérieur de Same, mais nous nous attendons à ce que la surcharge soit symétrique, n'est-ce pas ?

Mais si nous invoquons cette fonction surchargée comme suit :

std::optional<int> oi;
fon(oi, oi);

Nous obtenons un résultat ambigu de la résolution de surcharge, car, après normalisation, la contrainte de la première surcharge est :

std::is_same_v<value_type<T>, value_type<U>>

et la contrainte de la seconde est :

std::is_same_v<value_type<U>, value_type<T>> ∧ …

Ceci est une expression atomique différente. L'une des deux contraintes n'inclura donc jamais l'autre. La définition suivante ne fera pas l'affaire non plus :

template <typename X, typename Y>
concept Same = std::is_same_v<X, Y> && std::is_same_v<Y, X>;

La raison est que les deux contraintes, après substitution et normalisation, sont :

std::is_same_v<value_type<T>, value_type<U>> ∧
std::is_same_v<value_type<U>, value_type<T>>

et :

std::is_same_v<value_type<U>, value_type<T>> ∧
std::is_same_v<value_type<T>, value_type<U>> ∧ …

Elles ont la même apparence, en termes d'unités lexicales, mais sont générées depuis des emplacements différents (ces deux emplacements sont bien situés sur la même ligne de code, mais pas du même côté de l'unité lexicale &&). Ce n'est qu'en codant Same avec un concept intermédiaire, comme suit :

template <typename X, typename Y>
concept Same_ = std::is_same_v<X, Y>;
 
template <typename X, typename Y>
concept Same = Same_<X, Y> && Same_<Y, X>;

que nous obtenons les contraintes normalisées :

std::is_same_v<value_type<T>, value_type<U>> ∧
std::is_same_v<value_type<U>, value_type<T>>

et :

std::is_same_v<value_type<U>, value_type<T>> ∧
std::is_same_v<value_type<T>, value_type<U>> ∧ …

Mais alors, toutes les expressions atomiques viennent très exactement du même emplacement et se soumettent donc à l'inclusion.

L'autre point que nous pouvons observer, sans entrer dans les détails, est qu'il est possible de coder le concept Same différemment, avec une expressionrequires :

template <typename X, typename Y>
concept Same_ = std::is_same_v<X, Y>;
template <typename X, typename Y>
concept Same = requires {
    requires Same_<X, Y>;
    requires Same_<Y, X>;
};

Mais ceci fera également échouer notre résolution de surcharge, parce que l'expression requires est traitée comme une seule contrainte atomique.

Et c'est tout pour aujourd'hui. Tout cela peut sembler difficile, mais c'est parce que je me suis concentré sur les aspects les plus compliqués. En pratique, l'utilisation des concepts est bien plus simple.

Nous remercions Andrzej Krzemieński de nous avoir autorisés à publier ce tutoriel .

Nous tenons également à remercier kurtcpp pour la traduction et escartefigue pour la relecture orthographique