Type pack metaprogramming

I did advertise once to my c++ students that my feelings tell me that variadic templates are going to be key in implementing type lists in c++ template metaprogramming soon, and showed them a half-baked sketch. But they were not happy with that, “So, you have that class that depends on the type pack, very nice, now, how do you write a method whose signature is calculated out of your type pack?” they asked immediately. Such students’ questions brighten your teacher’s day, even if all you have to say at that point is “I’ll tell you next week”. So I will try in this post to work on the answer step by step.

C++11 introduced variadic templates and type packs. Suppose you need a class that depends on a variable number of type parameters. You can define it this way:

    template<class... Args>
class R
  {
  };

The class R depends on a list of types of arbitrary length (including zero-length), and this is expressed with the syntax class... Args in the template declaration. Args is a type pack. The type pack is a construct that is very different from individual types. It is available only in the scope of the template that depends on it, and the two most reasonable ways it can be used are instantiations of other variadic templates and declarations of parameters of functions. In particular, type packs cannot be typedef-ed. Let us provide our class with some sort of contents:

#include <tuple>

    template<class... Args>
class R
  {
    std::tuple<Args...> data_;
  public:
    R(Args... args)
      : data_(args...)
      {}
  };

int main(void)
  {
  R<int,double> r(1,3.14);
  return 0;
  }

In the code above I used the std::tuple, a C++11 library class that represents a vector of values of arbitrary types defined at compile time. The syntax Args... is called a type pack expansion, and it is roughly equivalent here to inserting a comma-separated list of types contained in the type pack it expands. The other use of the expansion Args... is in the constructor’s definition, where it defines the parameter pack args, and causes the arguments’ list of the function to be made up of types contained in the type pack Args. The parameter pack can be expanded in turn, which in its simplest form is, again, roughly equivalent to inserting a comma-separated list of values contained in the pack (but it does not work in some legal comma-separated contexts of C++, notably not with operator comma). This can be seen in the constructor call of the attribute data_.

We now have a variadic template class R, so let me try to equip it with overloaded methods whose signatures be dependent on the types in the Args type pack with wich the template class is instantiated. The two examples I will work on are a) repeating the first type and b) repeating each type. Of course these examples have some special cases. Repeating the first type makes no sense for empty Args, and for Args with length one the resulting type lists are the same, leading to ambiguity. We would expect the compiler to flag a reasonable error in both cases.

The problem that has to be faced when writing any of these methods is that we only have the original pack Args, but we need another, a transformed one, in the arguments’ list of the method, we cannot hard-code the signature of the method, because it has to depend on arbitrary-length Args. And type packs are not first-rate types, they cannot be typedefed. The only way out of this dilemma is to try to program the method as a template method depending on its own type pack:

#include <tuple>

    template<class... Args>
class R
  {
    std::tuple<Args...> data_;
  public:
    R(Args... args)
      : data_(args...)
      {}

        template<class... FooArgs>
        auto 
    foo(FooArgs... fooargs) 
        -> void;
  };

But this is not yet what we wanted, this is a method template that will gladly accept any arguments whatsoever, not just those corresponding to case a) or b), although this is the only way of having methods with type pack arguments other than the template class parameter Args. What we need to make it work as expected is a feature of function overload resolution called SFINAE (Substitution Failure Is Not An Error). When the compiler tries to find a best matching function for a call, it tries to generate arguments’ lists in corresponding function templates and on the set of all matching functions (template or not), called candidate functions, creates a partial order where functions with more specialized arguments’ lists are better than less specialized, and non-template functions are better than template with the same arguments’ lists. If a unique best is found, overload resolution succeeds. If during the generation of the arguments’ list of a particular function template an error occurs, by SFINAE this does not trigger a compilation error, but simply takes this template function out of the overload resolution set. Moreover, although non-template functions can be overloaded on arguments’ lists but not the return type, this is not the case for templates, template functions with same arguments but different return types are distinct candidates for the overload resolution set. The conclusion of this lengthy paragraph is that we need to modify the above declaration of foo so that it fails if the types in FooArgs do not satisfy the suitable constraint with respect to the types in Args.

I could put the conditional failure expression in the template arguments, in the arguments’ list or in the return type, the latter of which leading to the simplest solution, so that will be my pick. And due to the possibility of overloading function templates on their return type, this will work for both our functions. I will use a standard wrapper for that expression, std::enable_if, which is a two-argument class template. Its first template argument is a compile-time boolean value, the second is an arbitrary type. If the value is false, an error is triggered, if it is true, the type is typedefed inside the struct as type. So our piece of code will become

#include <tuple>
#include <type_traits>

    template<class... Args>
class R
  {
    std::tuple<Args...> data_;
  public:
    R(Args... args)
      : data_(args...)
      {}

        template<class... FooArgs>
        auto 
    foo(FooArgs... fooargs) 
        -> typename std::enable_if</*expression*/,void>::type;
  };

For a more thorough discussion on enable_if see for instance the post Remastered enable_if by R. Martinho Fernandes. The commented-out word “expression” is a placeholder where we should really do our compile-time calculation. In that scope we see two type packs, Args and FooArgs. As said before, the only reasonable use of a type pack is instantiation of type-pack dependent templates, so one might be tempted to try to use them in a plain way in an expression like TestArgs<Args,FooArgs>::is_good, but this is impossible without further work. The reason for this impossibility is that to define TestArgs we would have to write

    template<class... Args1, class... Args2>
class TestArgs;

and the compiler, at instantiation of TestArgs with several types, would not know where Args1 ends and Args2 starts. There is, however, a way to deal with this problem. Above, I tried to define the primary template of TestArgs. The primary template is a declaration that defines the number and kinds of template arguments, possibly variadic, but the variadic pack must be unique and at the end of the template parameters’ list. When the primary template is not just declared, but also defined, that definition is the catch-all version used if no template specialization fits better. So the idea is this: write the class TestArgs as a two-arguments template, and define a partial specialization that will get the type packs wrapped as template parameters of another template class:

    template<class... Args>
class TypeList {};

    template<class T, class U>
class TestArgs;

    template<class... Args1, class... Args2>
class TestArgs<TypeList<Args1...>,TypeList<Args2...>>
  {
  /* definition here */
  };

Now, if TestArgs is instantiated with types with structure different from TypeList<...>, the compiler will flag an error, because the catch-all template version is not defined. The idea of wrapping the type packs has yet another consequence: while it is not possible to typedef a pack, it is indeed possible to typedef the wrapper instantiated with a pack. This will allow me to split the task of checking the types in the packs Args and FooArgs into two operations, one that will compute the desired type list out of Args, and the other one that will check if the calculated type list is the same as the one produced by wrapping FooArgs. This approach produces elements of a reusable type list toolkit, since testing for equality of type lists should be a frequent operation. So, let me gather all the code:

#include <tuple>
#include <type_traits>

    template<class... Args>
class TypeList {};

    template<class T, class U>
struct Equal;

    template<class... Args1>
struct Equal<TypeList<Args1...>,TypeList<Args1...>>
  {
  static const bool is_same=true;
  };

    template<class... Args1, class... Args2>
struct Equal<TypeList<Args1...>,TypeList<Args2...>>
  {
  static const bool is_same=false;
  };

    template<class... Args>
class R
  {
    std::tuple<Args...> data_;
  public:
    R(Args... args)
      : data_(args...)
      {}

        template<class... FooArgs>
        auto 
    foo(FooArgs... fooargs) 
        -> typename std::enable_if
             <Equal
                <typename RepeatFirst<TypeList<Args...>>::type_list
                ,TypeList<FooArgs...>
                >::is_same
             ,void
             >::type;
  };

The piece still missing is the metafunction RepeatFirst that is supposed to produce a type list with first type appearing twice. To code it I will use another programming pattern related to variadic templates, that allows to single out a fixed number of initial types from a pack:

    template<class T>
struct RepeatFirst;

    template<class Head, class... Tail>
struct RepeatFirst<TypeList<Head, Tail...>>
  {
  typedef TypeList<Head,Head,Tail...> type_list;
  };

The above template, when instantiated with a type list with at least one type, lets you deal separately with the first type and the type pack corresponding to the tail of the list. Additionally, if it is instantiated with an empty type list, the compiler will complain about not finding Head.

It should be now clear what to do to overload foo with version b). We just need to define a metafunction RepeatEach and produce a second copy of foo that will check if RepeatEach applied to Args gives the same list as FooArgs. How do we repeat each entry in a list? The most obvious answer: write a loop, that is iterate, is wrong, since looping involves modification of some state, while during compilation, once an item is declared or defined, it remains immutable. That observation indicates that c++ metaprogramming is closely related to functional programming (for more on that see for instance What Does Haskell Have to Do with C++? by Bartosz Milewski), and experience from that domain gives the right answer: use recurrence. Repeating each type in an empty list should produce an empty list, that will be our terminating case. Repeating each type in a list containing at least one type should produce a list with that first type repeated, concatenated with the result of the same operation on the tail of the list. (On a marginal note, I wonder whether compilers recognize the tail recursion that allows important speedups on suitably reformulated recursion calculations, will have to check that some day). Anyway, to solve our problem we need to be able to concatenate type lists, but that is not very difficult:

    template<class T, class U>
struct Concat;

    template<class... Arg1, class... Arg2>
struct Concat<TypeList<Arg1...>,TypeList<Arg2...>>
  {
  typedef TypeList<Arg1...,Arg2...> type_list;
  };

And now we are able to write an implementation of the recursive algorithm described above:

    template<class U>
struct RepeatEach;

    template<>
struct RepeatEach<TypeList<>>
  {
  typedef TypeList<> type_list;
  };

    template<class Head, class... Tail>
struct RepeatEach<TypeList<Head,Tail...>>
  {
  typedef typename Concat<TypeList<Head,Head>
                         ,typename RepeatEach<TypeList<Tail...>>::type_list
                         >::type_list type_list;
  };

Putting all the code together we get the final solution:

#include <tuple>
#include <type_traits>

    template<class... Args>
class TypeList {};

    template<class T, class U>
struct Equal;

    template<class... Args1>
struct Equal<TypeList<Args1...>,TypeList<Args1...>>
  {
  static const bool is_same=true;
  };

    template<class... Args1, class... Args2>
struct Equal<TypeList<Args1...>,TypeList<Args2...>>
  {
  static const bool is_same=false;
  };

    template<class T, class U>
struct Concat;

    template<class... Arg1, class... Arg2>
struct Concat<TypeList<Arg1...>,TypeList<Arg2...>>
  {
  typedef TypeList<Arg1...,Arg2...> type_list;
  };

    template<class T>
struct RepeatFirst;

    template<class Head, class... Tail>
struct RepeatFirst<TypeList<Head, Tail...>>
  {
  typedef TypeList<Head,Head,Tail...> type_list;
  };

    template<class U>
struct RepeatEach;

    template<>
struct RepeatEach<TypeList<>>
  {
  typedef TypeList<> type_list;
  };

    template<class Head, class... Tail>
struct RepeatEach<TypeList<Head,Tail...>>
  {
  typedef typename Concat<TypeList<Head,Head>
                         ,typename RepeatEach<TypeList<Tail...>>::type_list
                         >::type_list type_list;
  };

    template<class... Args>
class R
  {
    std::tuple<Args...> data_;
  public:
    R(Args... args)
      : data_(args...)
      {}

        template<class... FooArgs>
        auto 
    foo(FooArgs... fooargs) 
        -> typename std::enable_if
             <Equal
                <typename RepeatFirst<TypeList<Args...>>::type_list
                ,TypeList<FooArgs...>
                >::is_same
             ,void
             >::type;

        template<class... FooArgs>
        auto 
    foo(FooArgs... fooargs) 
        -> typename std::enable_if
             <Equal
                <typename RepeatEach<TypeList<Args...>>::type_list
                ,TypeList<FooArgs...>
                >::is_same
             ,void
             >::type;
  };

The above is an answer to the original question. It uses C++11 features, as far as I can say, it would not be possible to produce the same effect using C++98/03 with type lists implemented as empty lists or pairs of type and tail list. It is not without its own set of problems: the enabling/disabling clauses may lead to ambiguity with no compiler support to detect it in general, there is a message only when a particular instantiation leads to it. And trying to port this idea to constructors is even more tricky, not only because the enabling clauses would have to be placed elsewhere as constructors have no return value, but also because of interference with default/copy/move constructors, for more on that see Scott Meyers’ post Copying Constructors in C++11.

Advertisements

One Response to Type pack metaprogramming

  1. Pingback: Generating set partitions – replacing virtual functions with protected inheritance | Programming blog of Łukasz Wojakowski

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: