Pages

lundi 26 octobre 2015

[C++] Filtrage par type

Exécuter du code dépendant du type des entrées est le principe même de la surcharge. La procédure est plutôt simple pour les types concrets, mais devient rapidement compliquée quand des templates interviennent avec des priorités de concept.

Pour exemple, une fonction foo() spécialisée dans l'ordre pour les types flottants, signés et non-signés requière 3 prototypes de la forme:

enable_if_t<   is_floating_point_v<T> > foo(T);
enable_if_t< ! is_floating_point_v<T> &&   is_signed_v<T> > foo(T);
enable_if_t< ! is_floating_point_v<T> && ! is_signed_v<T> > foo(T);

Comme is_signed inclut également les nombres flottants, il faut les exclure pour empêcher tout appel ambigü, ce qui tend le prototype à grandir inexorablement.

Une première approche consiste à la création d'une hiérarchie de fonctions.

- is_floating_point foo()
- ! is_floating_point foo()
  \- is_signed foo_with_integral()
  \- ! is_signed foo_with_integral()

Ce qui accroît le nombre de fonctions et n'est pas vraiment plus lisible.

Les autres solutions passent par les tags, la spécialisation de template et d'autres que j'oublie peut-être. Au final, la problématique est très proche de l'article précédent concernant static_if.

La solution aussi :D.

Le plus simple consiste en un pattern chaîne de responsabilité appliqué aux protypes de fonction.
Pour rappel, ce pattern permet d'exécuter la première fonction qui répond à une demande. Ici, notre demande sera: cette fonction peut-elle être appelée avec tel type de variable ?

// foo(T xxx)
select(
  xxx,
  if_<std::is_floating_point>([](auto & x) { ... }),
  if_<std::is_unsigned>([](auto & x) { ... }),
  if_<std::is_signed>([](auto & x) { ... }),
  // et plus
  [](std::string const & x) { ... },
  [](auto & x) -> decltype(x.foo()) { ... },
  // ...
  [](auto & x) { static_assert(decltype(void(x),1){},
    "Oups, il n'y a pas de correspondance :/"
  ); }
);


// Implémentation (présentation de la méthode: ici)

template<template<class> class Tpl, class F>
struct case_tpl
{
  F f;

  template<class T>
  auto operator()(T && x, std::enable_if_t<Tpl<std::decay_t<T>>{}>* = 0) const
  { return f(std::forward<T>(x)); }
};

template<template<class> class Tpl, class F>
case_tpl<Tpl, F> if_(F && f) {
  return {f};
}

template<class T>
void select_impl(int, T &) {}

template<class T, class Fn, class... Fns>
auto select_impl(int, T & x, Fn & fn, Fns & ...)
-> decltype(fn(x)) {
  return fn(x);
}

template<class T, class Fn, class... Fns>
auto select_impl(unsigned, T & x, Fn &, Fns & ... fns) {
  return select_impl(1, x, fns...);
}

template<class T, class... Fns>
auto select(T && x, Fns && ... fns) {
  return select_impl(1, x, fns...);
}

On peut même faire une implémentation qui utilise la surcharge et ainsi avoir une garantie forte que seule une fonction existe pour un type donné.

Avec les inconvénients concernant les appels ambigüs ;).

template<class T, class Fn>
auto match(T & x, Fn f) {
  return f(x);
}

template<class T, class Fn1, class Fn2, class... Fns>
auto match(T & x, Fn1 && fn1, Fn2 && fn2, Fns && ... fns) {
  struct F : Fn1, Fn2 {
    using Fn1::operator();
    using Fn2::operator();
    F(Fn1 f1, Fn2 f2) : Fn1(f1), Fn2(f2) {}
  };
  return match(F{fn1,fn2}, fns...)
}

lundi 21 septembre 2015

[c++] static_if

Le but de `static_if` est de ne pas vérifier la validité d'un code dans la phase de compilation. Le code doit être syntaxiquement valide, mais n'a pas l'obligation de pouvoir être compilé.

Plutôt étrange n'est-ce pas ? Cette propriété se révèle pourtant fort pratique dans les fonctions templates. Prenons comme exemple relativement bidon une fonction `foo(T & array)` qui vérifie si `array.size()` est au moins à 4 et, dans le cas contraire, agrandit le container avec `array.resize(4)`.

// pour T[N]
if (std::is_array<T>{})) {
  static_assert(std::extent<T>{} >= 4, "");
}
// pour std::vector
else { 
 array.resize(4);
}

Le problème ici: `static_assert` est toujours exécuté et `resize()` toujours évalué. Résultat, le code ne compile jamais, car `resize()` n'existe pas pour les tableaux et `size()` n'est pas `constexpr` pour `std::vector`.

Évidemment, `static_if` résout le problème. Dit comme cela, on pourrait croire que c'est un nouveau mot clef du langage, mais non. (Il eut une proposition dans ce sens, mais celle-ci fut rejetée.) Alors comment faire ?

Alternatives au static_if

En réalité, il existe plusieurs alternatives utilisées, et ce, bien avant C++11.

Trait et tag

Parmi celles qui font le sujet d'un de mes articles: les 'tags', souvent associés à un type_trait pour l'extraction.

Sur le principe, un type catégorie est extrait d'un paramètre et propagé à des fonctions surchargées sur la catégorie désirée. Malheureusement, cette approche disperse le code et rend la lecture difficile pour des besoins spécifiques et ponctuels. L'autre inconvénient est la transmission du scope de variable qui s'avère délicat (c'est une union (dans le sens mathématique) de toutes les variables utilisées par l'ensemble des surcharges).

Spécialisation de template

Sans plus m'étendre sur cette technique, le principe est exactement le même que pour les tags, sauf que l'on remplace la surcharge de fonction par de la spécialisation de template.

Classes internes sélectionnées avec std::conditional

La classe interne (comme utilisée dans l'article précédent) permet un code monolithique, mais n'a pas de conséquence sur le scope de variable, il faut toujours le propager. Sa lourdeur d'écriture est aussi un peu rédhibitoire.

Lambda

Les lambdas permettent de capturer le scope et se définissent n'importe où. Mais un problème survient, comment empêcher l'évaluation de la lambda si la condition n'est pas respectée ?

Depuis C++14, il existe les lambdas polymorphes. Celles-ci permettent l'usage de template à travers un type `auto`. Comme les templates ne sont évaluées qu'à leur appel, on peut faire du branchement conditionnel à la compilation en utilisant de la surcharge sur `std::true_type` et `std::false_type`. Au final, static_if devient un appel de fonction.

#include <type_traits>

class dummy { dummy(){} void operator()() const {} };

template<class TrueFn, class FalseFn = dummy>
auto static_if(std::true_type, TrueFn yes_fn, FalseFn const & = FalseFn{}) {
  return yes_fn(std::true_type{});
}

template<class TrueFn, class FalseFn>
auto static_if(std::false_type, TrueFn const &, FalseFn no_fn) {
  return no_fn(std::false_type{});
}


template<class T>
void foo(T & array) {
  static_if(std::is_array<T>{}, [&](auto){
    static_assert(std::extent<T>{} >= 4, "");
  },
  /*else*/[&](auto){
    array.resize(4);
  });
}


#include <vector>

int main()
{
  {
    std::vector<int> a;
    foo(a); // ok
  }
  {
    int a[5];
    foo(a); // ok
  }
  {
    int a[2];
    foo(a); // static_assert
  }
}

J'ai mis une valeur arbitraire pour le paramètre envoyé aux lambdas, on pourrait aussi le rendre optionnel en utilisant la méthode présentée dans cet article.

L'implémentation de static_if ne se prête pas très bien à l'imbrication. Une autre manière de faire, passe par une classe et du chaînage `static_if(...).else_if(...)`. C'est un peu plus compliqué si on veut un type de retour et on ne pourra pas utiliser de AAA sans appeler explicitement une fonction `eval()`.

auto xxx = static_if(..., []{ return 1; }).else_([]{ return 2; });
// decltype(xxx) != int (définit par l'implémentation de static_if)
auto xxx = static_if(..., []{ return 1; }).else_([]{ return 2; }).eval();
// decltype(xxx) = int

Je pense qu'il vaut alors mieux se tourner vers une forme proche du switch.

static_switch(xxx
, case_<std::is_array>() = [&](auto){ static_assert(std::extent<T>{} >= 4, ""); }
, case_<yyy>() | case_<zzz>() = [&]{ ... }
, default_ = []{ ... }
);

Que je laisse à la discrétion de chacun ;)

mardi 28 juillet 2015

Paramètres de fonction nommés en C++

Cet article est la démonstration de l'article précédent. La problématique présentée est la suivante: "Comment, dans une fonction avec plusieurs paramètres optionnels, initialiser un paramètre précis sans indiquer les valeurs optionnels qui précèdent ?"

La fonction de référence sera la suivante:

void draw_rect(
  unsigned w, unsigned h
, char border_top = '-', char border_bottom = '-'
, char border_left = '<', char border_right = '>'
, char fill = '#'
) {
  std::cout << std::setfill(border_top) << std::setw(w+2) << "" << "\n";
  while (h--) {
    std::cout << border_left << std::setfill(fill) << std::setw(w) << "" << border_right << "\n";
  }
  std::cout << std::setfill(border_bottom) << std::setw(w+2) << "" << "\n";
}

Comment faire un appel proche de `draw_rect(4,3, fill='@')` ?

Création d'un paramètre nommé.

La première étape consiste à créer un type par paramètre optionnel. Comme je n'ai pas envie de me compliquer la vie, la syntaxe `fill='@'` qui demande plus de code sera remplacer par un simple appel de constructeur `fill{'@'}`.

La définition des types devient alors véritablement simpliste:

struct border_top { char value; };
struct border_bottom { char value; };
struct border_left { char value; };  
struct border_right { char value; };
struct fill { char value; };

Adapter draw_rect.

Au lieu d'adapter draw_rect, je vais passer par une surcharge, ceci n'impactera pas le résultat.

La nouvelle fonction doit pouvoir prendre les nouveaux types, mais pas forcement tous et de préférence dans un ordre indéfini.

On pourrait faire toutes les surcharges possibles, il n'y a "que" plus d'une centaine de possibilités après tous... Solution rejetée, évidemment ;).

Une variadique template fera l'affaire.

template<class... Ts>
void draw_rect(unsigned w, unsigned h, Ts... params);

Il reste maintenant à associer chaque type de `params` avec le paramètre de notre premier prototype de draw_rect.

Distribution des paramètres.

C'est là qu'intervient le magasin de type de l'article précédant (toujours pas trouvé de meilleur nom).

Le principe est simple, toutes les valeurs de params sont regroupées sous une même enseigne appelé ici 'pack'. On vérifie si le pack est convertible en un type voulu et dans le cas contraire, on utilise une valeur par défaut.

Notre pack ressemble à ça:

struct Pack : Ts... {
  Pack(Ts... args) : Ts(args)... {}
} pack{params...};

Et la distribution des paramètres se fait ainsi:

draw_rect(w, h
, getval<border_top>(pack, '-')   
, getval<border_bottom>(pack, '-')
, getval<border_left>(pack, '<')  
, getval<border_right>(pack, '>')
, getval<fill>(pack, '#')  
);

Pour les plus attentifs (il m'a fallu 2 jours pour le réaliser xD), rien n'empêche d'envoyer des paramètres inutiles, on peut l'empêcher grâce à un static_assert avec une condition style `std::is_convertible_t<border_top>() + std::is_convertible<border_bottom>() + /*etc*/ == sizeof...(Ts)`.

Dans l'histoire, bien que largement surmontable, getval est la fonction la plus compliquée. Si Pack est convertible en T alors Get::get() est utilisé, sinon Default::get().

template<class T, class Pack>
char getval(Pack & pack, char default_) {
  struct Get     { static char get(T item, char         ) { return item.value; } };
  struct Default { static char get(Pack &, char default_) { return default_;   } };
  return std::conditional<std::is_convertible<Pack, T>::value, Get, Default>::type
  ::get(pack, default_);
}

Conclusion

Je trouve la technique du 'pack' très adapté pour les paramètres optionnel. Contrairement à l'alternative hyper lourdingue via fonctions récursives et 2 tuples (un des paramètres reçus + un des paramètres triés), getval() est plutôt limpide. Aspect suffisamment rare dans le domaine de la méta-programmation pour être souligné ^^.

Les choses se compliquent quand on veut récupérer un type partiel d'un pack. Un std::vector<T> par exemple. Actuellement, je n'ai pas de solution aussi simple qu'utiliser is_convertible. J'espère dans les prochains jours trouver une solution et l'ajouter à Falcon.Store.

Pour aller plus loin dans la voie des paramètres nommés, il existe Boost.Parameters.

jeudi 2 juillet 2015

Implémentation d'un magasin de type

Ce que j'appelle ici un magasin de type n'est autre qu'un std::tuple où les types ne sont présents qu'une seule fois. Une espèce de set version tuple en somme.

Je me suis servi de ce type de structure à 2 reprises.

Une fois pour manipuler de façon similaire des types hétérogènes sans la lourdeur de std::tuple. Il faut dire aussi que j'étais en C++11 et que dans cette norme std::get<Type>() n'existe pas.

L'autre fois dans une fonction variadique qui distribue les valeurs vers différentes fonctions. Le but étant de ne pas se soucier de l'ordre des paramètres, certains étant optionnels.

std::tuple fait plutôt bien le boulot, mais possède plusieurs inconvénients pour ce cas de figure.

  • Aucune erreur de compilation si un type est présent 2 fois (et c'est normal pour un tuple).
  • Prend beaucoup de mémoire et de temps de compilation (osef !)

Je pourrais faire l'apologie de RapidTuple histoire de me faire mousser (le projet contient un tuple_set), mais en fait non, on peut faire encore plus simple en 10 lignes de code :).
Bon ok, 3 lignes.
Mais 10 pour rendre pratique ;).

Planter la compilation quand un type est en doublon.

Le C++ dispose déjà d'un mécanisme interne qui vérifie et hurle au scandale si un type doublon existe. J'ai nommé l'héritage.

Seulement, un héritage direct n'est pas possible avec les types scalaires, il faut un intermédiaire.

template<class T> struct item { T x;  }; 

template<class... Ts>
struct store : item<Ts>... {}; 

Avec cette implémentation, des petits malins pourraient faire de la pseudo-duplication de type en y ajoutant des qualificatifs, store<int, int const> par exemple.

On peut être tolérant ou devenir un tyran sans pitié en empêchant cela.

template<class... Ts>
struct tyrannical_store_impl : store<std::remove_cv_t<Ts>...> {
  using type = store<Ts...>; 
}; 

template<class... Ts>
using tyrannical_store = typename tyrannical_store_impl<Ts...>::type; 

Le store tyrannique est construit en 2 étapes, car un alias direct sur un store épuré ne permet pas de garder les qualificatifs.

Piocher dans le magasin.

Piquer un élément du magasin est une affaire de cast. Un simple static_cast.

store<int, char> my_store; 

static_cast<item<int>&>(my_store).x; 

En mettant des opérateurs de cast dans la classe item, plus besoin de préciser cette dernière avec le static_cast.

template<class T> struct item {
  explicit operator T & () noexcept { return x_;  }
  explicit operator T const & () const noexcept { return x_;  }
private:
  T x_; 
}; 
store<int, char> my_store; 

static_cast<int&>(my_store); 

Petit bémol toutefois, cela ne permet pas d'enlever l'ambiguïté pour un type qui diffère uniquement par son qualificatif.

store<int, int volatile> my_store; 

static_cast<int volatile&>(my_store);  // 'store<int, volatile int>' to 'volatile int&' is ambiguous

Ce qu'il manque

  • Les constructeurs, évidemment.
  • Une fonction get<Type>() pour un parallèle avec la STL.
  • Une fonction pour boucler sur chaque item (apply_from_store ?).
  • Et sûrement d'autres.

J'ai mis tout ça dans un repo au nom provisoire (falcon.store).

samedi 16 mai 2015

Délégation d'appel de fonctions utilitaires.

Cet article fait suite à l'utilisation de swap et des fonctions utilitaires en général.

L'article précédemment cité montre pourquoi il faut exporter avec using la fonction utilitaire généraliste avant de l'utiliser. La nécessité de "déplacer" les fonctions dans le scope est lourd et facile à oublier.

L'idéal serait la présence d'une unique fonction en charge d'appeler la bonne surcharge. Heureusement, une solution existe. Elle consiste en la création d'un namespace dans lequel la fonction générale est exportée et où une fonction intermédiaire l'appelle. Comme la règle d'adl s'applique, la fonction surchargée sera appelée si existante.

#include <algorithm>

namespace fn {
  namespace {
    using std::swap;

    template<class T>
    void swap_impl(T & a, T & b)
    { swap(a,b); }
  }

  template<class T>
  void swap(T & x, T & y)
  { ::fn::swap_impl(x,y); }
}

Cependant, cette solution souffre de l'effet inverse: la fonction ne peut pas être déplacée dans le même scope qu'une fonction généraliste. Il y aurait 2 prototypes identiques, le compilateur ne pourrait pas lever l’ambiguïté. Comme il est très courant de voir `using namespace std;`, un `using fn::swap` dans le même scope rentrerait en conflit avec std::swap lors de l'appel (aucun problème si dans un sous-scope).

#include <iostream>

namespace my {
  struct A{};
  void swap(A&, A&)
  { std::cout << "ok\n"; }
}

int main()
{
  {
    my::A a, b;
    fn::swap(a,b); // affiche ok
  }
  {
    int a, b;
    fn::swap(a,b); // compile
  }

  {
    using fn::swap;
    using std::swap;
    int a, b;
    swap(a,b); // ambiguïté
  }

  {
    using std::swap;
    {
      using fn::swap;
      my::A a, b;
      fn::swap(a,b); // affiche ok
    }
  }
}