xref: /third_party/boost/libs/mp11/doc/mp11/examples.adoc

////
Copyright 2017 Peter Dimov

Distributed under the Boost Software License, Version 1.0.

See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt
////

[#examples]
# Examples
:toc:
:toc-title:
:idprefix:

## Generating Test Cases

Let's suppose that we have written a metafunction `result<T, U>`:

```
template<class T> using promote = typename std::common_type<T, int>::type;

template<class T, class U> using result =
    typename std::common_type<promote<T>, promote<U>>::type;
```

that ought to represent the result of an arithmetic operation on the integer types `T` and `U`,
for example `t + u`. We want to test whether `result<T, U>` gives correct results for various combinations
of `T` and `U`, so we write the function
```
template<class T1, class T2> void test_result()
{
    using T3 = decltype( T1() + T2() );
    using T4 = result<T1, T2>;

    std::cout << ( std::is_same<T3, T4>::value? "[PASS]": "[FAIL]" ) << std::endl;
}
```
and then need to call it a substantial number of times:

    int main()
    {
        test_result<char, char>();
        test_result<char, short>();
        test_result<char, int>();
        test_result<char, unsigned>();
        // ...
    }

Writing all those type combinations by hand is unwieldy, error prone, and worst of all, boring. This is
how we can leverage Mp11 to automate the task:
```
#include <boost/mp11.hpp>
#include <boost/core/demangle.hpp>
#include <type_traits>
#include <iostream>
#include <typeinfo>

using namespace boost::mp11;

template<class T> std::string name()
{
    return boost::core::demangle( typeid(T).name() );
}

template<class T> using promote = typename std::common_type<T, int>::type;

template<class T, class U> using result =
    typename std::common_type<promote<T>, promote<U>>::type;

template<class T1, class T2> void test_result( mp_list<T1, T2> const& )
{
    using T3 = decltype( T1() + T2() );
    using T4 = result<T1, T2>;

    std::cout << ( std::is_same<T3, T4>::value? "[PASS] ": "[FAIL] " )
        << name<T1>() << " + " << name<T2>() << " -> " << name<T3>()
        << ", result: " << name<T4>() << std::endl;
}

int main()
{
    using L = std::tuple<char, short, int, unsigned, long, unsigned long>;
    tuple_for_each( mp_product<mp_list, L, L>(), [](auto&& x){ test_result(x); } );
}
```
How does it work?

`mp_product<F, L1, L2>` calls `F<T1, T2>` where `T1` varies over the elements of `L1` and `T2` varies over
the elements of `L2`, as if by executing two nested loops. It then returns a list of these results, of the same
type as `L1`.

In our case, both lists are the same `std::tuple`, and `F` is `mp_list`, so `mp_product<mp_list, L, L>` will get us
`std::tuple<mp_list<char, char>, mp_list<char, short>, mp_list<char, int>, ..., mp_list<unsigned long, long>, mp_list<unsigned long, unsigned long>>`.

We then default-construct this tuple and pass it to `tuple_for_each`. `tuple_for_each(tp, f)` calls `f` for every
tuple element; we use a (C++14) lambda that calls `test_result`.

In pure C++11, we can't use a lambda with an `auto&&` parameter, so we'll have to make `test_result` a function object with
a templated `operator()` and pass that to `tuple_for_each` directly:
```
struct test_result
{
    template<class T1, class T2> void operator()( mp_list<T1, T2> const& ) const
    {
        using T3 = decltype( T1() + T2() );
        using T4 = result<T1, T2>;

        std::cout << ( std::is_same<T3, T4>::value? "[PASS] ": "[FAIL] " )
            << name<T1>() << " + " << name<T2>() << " -> " << name<T3>()
            << ", result: " << name<T4>() << std::endl;
    }
};

int main()
{
    using L = std::tuple<char, short, int, unsigned, long, unsigned long>;
    tuple_for_each( mp_product<mp_list, L, L>(), test_result() );
}
```
## Writing common_type Specializations

The standard trait `std::common_type`, used to obtain a type to which all of its arguments can convert without
unnecessary loss of precision, can be user-specialized when its default implementation (based on the ternary `?:`
operator) is unsuitable.

Let's write a `common_type` specialization for two `std::tuple` arguments. For that, we need a metafunction that
applies `std::common_type` to each pair of elements and gathers the results into a tuple:
```
template<class... T> using common_type_t =
    typename std::common_type<T...>::type; // standard in C++14

template<class Tp1, class Tp2> using common_tuple =
    mp_transform<common_type_t, Tp1, Tp2>;
```
then specialize `common_type` to use it:
```
namespace std
{

    template<class... T1, class... T2>
    struct common_type<std::tuple<T1...>, std::tuple<T2...>>:
        mp_defer<common_tuple, std::tuple<T1...>, std::tuple<T2...>>
    {
    };

} // std
```
(There is no need to specialize `std::common_type` for more than two arguments - it takes care of synthesizing the appropriate semantics from
the binary case.)

The subtlety here is the use of `mp_defer`. We could have defined a nested `type` to `common_tuple<std::tuple<T1...>, std::tuple<T2...>>`,
and it would still have worked in all valid cases. By letting `mp_defer` define `type`, though, we make our specialization _SFINAE-friendly_.

That is, when our `common_tuple` causes a substitution failure instead of a hard error, `mp_defer` will not define a nested `type`,
and `common_type_t`, which is defined as `typename common_type<...>::type`, will also cause a substitution failure.

As another example, consider the hypothetical type `expected<T, E...>` that represents either a successful return with a value of `T`,
or an unsuccessful return with an error code of some type in the list `E...`. The common type of `expected<T1, E1, E2, E3>` and
`expected<T2, E1, E4, E5>` is `expected<common_type_t<T1, T2>, E1, E2, E3, E4, E5>`. That is, the possible return values are
combined into their common type, and we take the union of the set of error types.

Therefore,
```
template<class T1, class E1, class T2, class E2> using common_expected =
    mp_rename<mp_push_front<mp_unique<mp_append<E1, E2>>, common_type_t<T1, T2>>,
        expected>;

namespace std
{

    template<class T1, class... E1, class T2, class... E2>
    struct common_type<expected<T1, E1...>, expected<T2, E2...>>:
        mp_defer<common_expected, T1, mp_list<E1...>, T2, mp_list<E2...>>
    {
    };

} // std
```
Here we've taken a different tack; instead of passing the `expected` types to `common_expected`, we're passing the `T` types and lists of
the `E` types. This makes our job easier. `mp_unique<mp_append<E1, E2>>` gives us the concatenation of `E1` and `E2` with the duplicates
removed; we then add `common_type_t<T1, T2>` to the front via `mp_push_front`; and finally, we `mp_rename` the resultant `mp_list`
to `expected`.

## Fixing tuple_cat

The article http://pdimov.com/cpp2/simple_cxx11_metaprogramming.html#[Simple C++11 metaprogramming] builds an
implementation of the standard function `tuple_cat`, with the end result given below:

```
template<class L> using F = mp_iota<mp_size<L>>;

template<class R, class...Is, class... Ks, class Tp>
R tuple_cat_( mp_list<Is...>, mp_list<Ks...>, Tp tp )
{
    return R{ std::get<Ks::value>(std::get<Is::value>(tp))... };
}

template<class... Tp,
    class R = mp_append<std::tuple<>, typename std::remove_reference<Tp>::type...>>
    R tuple_cat( Tp &&... tp )
{
    std::size_t const N = sizeof...(Tp);

    // inner

    using list1 = mp_list<
        mp_rename<typename std::remove_reference<Tp>::type, mp_list>...>;

    using list2 = mp_iota_c<N>;

    using list3 = mp_transform<mp_fill, list1, list2>;

    using inner = mp_apply<mp_append, list3>;

    // outer

    using list4 = mp_transform<F, list1>;

    using outer = mp_apply<mp_append, list4>;

    //

    return tuple_cat_<R>( inner(), outer(),
        std::forward_as_tuple( std::forward<Tp>(tp)... ) );
}
```

This function, however, is not entirely correct, in that it doesn't handle some cases properly. For example,
trying to concatenate tuples containing move-only elements such as `unique_ptr` fails:

```
std::tuple<std::unique_ptr<int>> t1;
std::tuple<std::unique_ptr<float>> t2;

auto result = ::tuple_cat( std::move( t1 ), std::move( t2 ) );
```
Trying to concatenate `const` tuples fails:
```
std::tuple<int> const t1;
std::tuple<float> const t2;

auto result = ::tuple_cat( t1, t2 );
```
And finally, the standard `tuple_cat` is specified to work on arbitrary tuple-like types (that is, all types
that support `tuple_size`, `tuple_element`, and `get`), while our implementation only works with `tuple` and
`pair`. `std::array`, for example, fails:
```
std::array<int, 2> t1{ 1, 2 };
std::array<float, 3> t2{ 3.0f, 4.0f, 5.0f };

auto result = ::tuple_cat( t1, t2 );
```
Let's fix these one by one. Support for move-only types is easy, if one knows where to look. The problem is
that `Tp` that we're passing to the helper `tuple_cat_` is (correctly) `tuple<unique_ptr<int>&&, unique_ptr<float>&&>`,
but `std::get<0>(tp)` still returns `unique_ptr<int>&`, because `tp` is an lvalue. This behavior is a bit
surprising, but is intended to prevent inadvertent double moves.

Long story short, we need `std::move(tp)` in `tuple_cat_` to make `tp` an rvalue:

    template<class R, class...Is, class... Ks, class Tp>
    R tuple_cat_( mp_list<Is...>, mp_list<Ks...>, Tp tp )
    {
        return R{ std::get<Ks::value>(std::get<Is::value>(std::move(tp)))... };
    }

Next, `const`-qualified tuples. The issue here is that we're stripping references from the input tuples, but not
`const`. As a result, we're trying to manipulate types such as `tuple<int> const` with Mp11 algorithms, and these
types do not fit the list concept. We just need to strip qualifiers as well, by defining the useful `remove_cv_ref`
primitive that is inexplicably missing from the standard library:

    template<class T> using remove_cv_ref = typename std::remove_cv<
        typename std::remove_reference<T>::type>::type;

and then by using `remove_cv_ref<Tp>` in place of `typename std::remove_reference<Tp>::type`:

```
template<class... Tp,
    class R = mp_append<std::tuple<>, remove_cv_ref<Tp>...>>
    R tuple_cat( Tp &&... tp )
{
    std::size_t const N = sizeof...(Tp);

    // inner

    using list1 = mp_list<mp_rename<remove_cv_ref<Tp>, mp_list>...>;

    // ...
```

Finally, tuple-like types. We've so far exploited the fact that `std::pair` and `std::tuple` are valid Mp11 lists,
but in general, arbitrary tuple-like types aren't, so we need to convert them into such. For that, we'll need to
define a metafunction `from_tuple_like` that will take an arbitrary tuple-like type and will return, in our case,
the corresponding `mp_list`.

Technically, a more principled approach would've been to return `std::tuple`, but here `mp_list` will prove more
convenient.

What we need is, given a tuple-like type `Tp`, to obtain `mp_list<std::tuple_element<0, Tp>::type, std::tuple_element<1, Tp>::type,
..., std::tuple_element<N-1, Tp>::type>`, where `N` is `tuple_size<Tp>::value`. Here's one way to do it:

```
template<class T, class I> using tuple_element =
    typename std::tuple_element<I::value, T>::type;

template<class T> using from_tuple_like =
    mp_product<tuple_element, mp_list<T>, mp_iota<std::tuple_size<T>>>;
```

(`mp_iota<N>` is an algorithm that returns an `mp_list` with elements `mp_size_t<0>`, `mp_size_t<1>`, ..., `mp_size_t<N-1>`.)

Remember that `mp_product<F, L1, L2>` performs the equivalent of two nested loops over the elements of `L1` and `L2`,
applying `F` to the two variables and gathering the result. In our case `L1` consists of the single element `T`, so
only the second loop (over `mp_iota<N>`, where `N` is `tuple_size<T>`), remains, and we get a list of the same type
as `L1` (an `mp_list`) with contents `tuple_element<T, mp_size_t<0>>`, `tuple_element<T, mp_size_t<1>>`, ...,
`tuple_element<T, mp_size_t<N-1>>`.

For completeness's sake, here's another, more traditional way to achieve the same result:

    template<class T> using from_tuple_like =
        mp_transform_q<mp_bind_front<tuple_element, T>, mp_iota<std::tuple_size<T>>>;

With all these fixes applied, our fully operational `tuple_cat` now looks like this:

```
template<class L> using F = mp_iota<mp_size<L>>;

template<class R, class...Is, class... Ks, class Tp>
R tuple_cat_( mp_list<Is...>, mp_list<Ks...>, Tp tp )
{
    return R{ std::get<Ks::value>(std::get<Is::value>(std::move(tp)))... };
}

template<class T> using remove_cv_ref = typename std::remove_cv<
    typename std::remove_reference<T>::type>::type;

template<class T, class I> using tuple_element =
    typename std::tuple_element<I::value, T>::type;

template<class T> using from_tuple_like =
    mp_product<tuple_element, mp_list<T>, mp_iota<std::tuple_size<T>>>;

template<class... Tp,
    class R = mp_append<std::tuple<>, from_tuple_like<remove_cv_ref<Tp>>...>>
    R tuple_cat( Tp &&... tp )
{
    std::size_t const N = sizeof...(Tp);

    // inner

    using list1 = mp_list<from_tuple_like<remove_cv_ref<Tp>>...>;
    using list2 = mp_iota_c<N>;

    using list3 = mp_transform<mp_fill, list1, list2>;

    using inner = mp_apply<mp_append, list3>;

    // outer

    using list4 = mp_transform<F, list1>;

    using outer = mp_apply<mp_append, list4>;

    //

    return tuple_cat_<R>( inner(), outer(),
        std::forward_as_tuple( std::forward<Tp>(tp)... ) );
}
```

## Computing Return Types

{cpp}17 has a standard variant type, called `std::variant`. It also defines a function template
`std::visit` that can be used to apply a function to the contained value of one or more variants.
So for instance, if the variant `v1` contains `1`, and the variant `v2` contains `2.0f`,
`std::visit(f, v1, v2)` will call `f(1, 2.0f)`.

However, `std::visit` has one limitation: it cannot return a result unless all
possible applications of the function have the same return type. If, for instance, `v1` and `v2`
are both of type `std::variant<short, int, float>`,

    std::visit( []( auto const& x, auto const& y ){ return x + y; }, v1, v2 );

will fail to compile because the result of `x + y` can be either `int` or `float` depending on
what `v1` and `v2` hold.

A type that can hold either `int` or `float` already exists, called, surprisingly enough, `std::variant<int, float>`.
Let's write our own function template `rvisit` that is the same as `visit` but returns a `variant`:

```
template<class F, class... V> auto rvisit( F&& f, V&&... v )
{
    using R = /*...*/;

    return std::visit( [&]( auto&&... x )
        { return R( std::forward<F>(f)( std::forward<decltype(x)>(x)... ) ); },
        std::forward<V>( v )... );
}
```

What this does is basically calls `std::visit` to do the work, but instead of passing it `f`, we pass a lambda that does the same as `f` except
it converts the result to a common type `R`. `R` is supposed to be `std::variant<...>` where the ellipsis denotes the return types of
calling `f` with all possible combinations of variant values.

We'll first define a helper quoted metafunction `Qret<F>` that returns the result of the application of `F` to arguments of type `T...`:

    template<class F> struct Qret
    {
        template<class... T> using fn =
            decltype( std::declval<F>()( std::declval<T>()... ) );
    };

It turns out that {cpp}17 already contains a metafunction that returns the result of the application of a function `F` to arguments
of type `T...`: `std::invoke_result_t<F, T...>`. We can make use of it to simplify our `Qret` to

    template<class F> struct Qret
    {
        template<class... T> using fn = std::invoke_result_t<F, T...>;
    };

which in Mp11 can be expressed more concisely as

    using Qret = mp_bind_front<std::invoke_result_t, F>;

With `Qret` in hand, a `variant` of the possible return types is just a matter of applying it over the possible combinations of the variant values:

    using R = mp_product_q<Qret, remove_cv_ref<V>...>;

Why does this work? `mp_product<F, L1<T1...>, L2<T2...>, ..., Ln<Tn...>>` returns `L1<F<U1, U2, ..., Un>, ...>`, where `Ui` traverse all
possible combinations of list values. Since in our case all `Li` are `std::variant`, the result will also be `std::variant`. (`mp_product_q` is
the same as `mp_product`, but for quoted metafunctions such as our `Qret`.)

One more step remains. Suppose that, as above, we're passing two variants of type `std::variant<short, int, float>` and `F` is
`[]( auto const& x, auto const& y ){ return x + y; }`. This will generate `R` of length 9, one per each combination, but many of those
elements will be the same, either `int` or `float`, and we need to filter out the duplicates. So, we pass the result to `mp_unique`:

    using R = mp_unique<mp_product_q<Qret, remove_cv_ref<V>...>>;

and we're done:

```
#include <boost/mp11.hpp>
#include <boost/core/demangle.hpp>
#include <variant>
#include <type_traits>
#include <typeinfo>
#include <iostream>

using namespace boost::mp11;

template<class T> using remove_cv_ref = typename std::remove_cv<
    typename std::remove_reference<T>::type>::type;

template<class F, class... V> auto rvisit( F&& f, V&&... v )
{
    using Qret = mp_bind_front<std::invoke_result_t, F>;

    using R = mp_unique<mp_product_q<Qret, remove_cv_ref<V>...>>;

    return std::visit( [&]( auto&&... x )
        { return R( std::forward<F>(f)( std::forward<decltype(x)>(x)... ) ); },
        std::forward<V>( v )... );
}

template<class T> std::string name()
{
    return boost::core::demangle( typeid(T).name() );
}

template<class V> void print_variant( char const * n, V const& v )
{
    std::cout << "(" << name<decltype(v)>() << ")" << n << ": ";

    std::visit( []( auto const& x )
        { std::cout << "(" << name<decltype(x)>() << ")" << x << std::endl; }, v );
}

int main()
{
    std::variant<char, int, float> v1( 1 );

    print_variant( "v1", v1 );

    std::variant<short, int, double> const v2( 3.14 );

    print_variant( "v2", v2 );

    auto v3 = rvisit( []( auto const& x, auto const& y ){ return x + y; }, v1, v2 );

    print_variant( "v3", v3 );
}
```