How can I constrain template parameter pack arguments to a "chain" sequence?

Question

Suppose I have two classes:

template <typename X, typename Y>
class Functor {};

template <typename Start, typename End, typename ...Functors>
class Template {};

Template has the constraints:

• All Functors must be type Functor

• All Functor must be in a chain sequence, such that

  • the first Functor must have Start as its first argument
  • the last Functor must have End as its second argument
  • each Functor's first argument is the second argument of the Functor preceding it

  E.g. Functor<A,B>, Functor<B, C>, Functor<C, D>, ... etc.

Example:

Starting with: char

Ending with: long

Template<char, long, Functor<char, A>, Functor<A, B>, Functor<B, C>, Functor<C, long>> t;

                1         2         3         4
           ├─────────┼─────────┼─────────┼─────────┤
argument: char       A         B         C        long
Functor #
  = 1      Functor<char, A>,
    2                Functor<A, B>,
    3                           Functor<B, C>,
    4                                    Functor<C, long>

Code

namespace ns
{
    template <typename X, typename Y = X>
    class Functor
    {
    public:
        using first  = X;
        using second = Y;
        Functor(X lVal) : x(lVal) {}
    private:
        X x;
    };

    template <typename Start, typename End, typename ...Functors>
        requires(std::is_convertible_v<Functors, Functor> && ...)    //error
    class Template
    {
        // How does one use `std::is_convertible_v` on
        // an un-specialized template class?
    };

    template <typename Start, typename End>
    class Template<Start, End, Functor<Start, End>>
    {};
}

Questions:

1. What is the best approach?
   • Can this be done with fold expression(s)?
   • Or concepts?
2. How does one use std::is_convertible (or any of the other metaprogramming traits) on an un-specialized template class?

Stiver

Answer 1

As a single requires-expression:

    requires requires(Functors... f) {
        []<typename... X, typename... Y>(Functor<X, Y>&...)
            requires std::same_as<void(Start, Y...), void(X..., End)> {
        }(f...);
    }

First, we deduce the X and Y of each Functor; this step will fail if any of the Functors are not an instantiation of Functor. (Strictly speaking, it will also allow types derived from Functor<X, Y>; to prevent this, you could use std::type_identity.) Then, we check that the chain of types Start, Y... is the same as the chain X..., End (note: not Start, X...!); this will hold precisely if the <X, Y>... form a chain from Start to End.

Note that it will also hold for <Start, End, Functor<Start, End>>, which you've listed as a separate case, and for <Start, Start>, i.e. if Start and End are the same type, it will allow the chain to be empty; if you want to disallow this you can add sizeof...(Functors) != 0u as an extra constraint.

I'm using function types for a typelist, which is concise but does have the potential drawback of decaying the types; you could equally use e.g. std::tuple, and that would allow relaxing the constraint to e.g. std::convertible_to (std::tuple<T...> is convertible to std::tuple<U...> iff each T is convertible to its respective U).

If an invalid chain is passed, gcc will output an error ending with something like:

note: the expression 'is_same_v<_Tp, _Up> [with _Tp = void(char, A, C, C, int); _Up = void(char, A, B, C, long int)]' evaluated to 'false'

Demo.

A slightly more verbose but perhaps clearer way to write the constraint is:

    requires requires(std::tuple<Functors...> f) {
        []<typename... X, typename... Y>(std::tuple<Functor<X, Y>...>)
            requires requires(std::tuple<Start, Y...> c, std::tuple<X..., End> d) {
                []<typename... C, typename... D>(std::tuple<C...>, std::tuple<D...>)
                    requires (std::same_as<C, D> and...) {}(c, d);
            } {}(f); }

Here we're using type deduction to form the typelists C := {Start, Y...} and D := {X..., End}, then performing a conjunction fold over the elementwise type comparison, giving an error on invalid chain along the lines of:

note: the expression '(same_as<C, D> && ...) [with C = {char, A, C, C, int}; D = {char, A, B, C, long int}]' evaluated to 'false'

Demo.

Improbable

std::same_as<void(Start, Y...), void(X..., End)> ... is one of the nicest things I've seen in a long time. Brilliant! – Zorazorah

Agreed, very innovative! – Stiver

Unfortunately, std::same_as<void(int [69]), void(int [420])>. – Need

@Need true, but an array type can't be a return type so that wouldn't be an issue here. – Improbable

What return type? – Need

@Need the problem context is that of chaining unary functions in composition: f ∘ g ∘ h where the argument and return types of adjacent functions must be the same. – Improbable

What functions? – Need

@Need ah, I must have been thinking of a similar problem - it's kinda implied by the term Functor though. – Improbable

Answer 2

With (ab)use of operator overloading, you might do

// Used std::type_identity as wrapper
// Operator+, but no implementation needed
template <typename A, typename B, typename C>
std::type_identity<Functor<A, C>>
operator +(std::type_identity<Functor<A, B>>, std::type_identity<Functor<B, C>>);

And then just check the operation is "valid".

template <typename Start, typename End, typename... Functors>
requires(std::is_same_v<std::type_identity<Functor<Start, End>>,
                        decltype((std::type_identity<Functors>{} + ...))>)
class Template {
    //...
};

Demo

Shaving

I'd suggest either putting that operator+ in a namespace or using a separate wrapper instead of type_identity to make it even less likely it would accidentally be used or conflict with some other similar abuse. – Symonds

Answer 3

You could start by adding a type trait for checking that a template parameter is of Functor type:

template <typename X, typename Y>
class Functor {
   public:
    using first_type = X;
    using second_type = Y;
};

// type trait to check if a type is a Functor
template <class...>
struct is_Functor : std::false_type {};

template <class X, class Y>
struct is_Functor<Functor<X, Y>> : std::true_type {};

template <class T>
inline constexpr bool is_Functor_v = is_Functor<T>::value;

Then require that all of them are in fact of Functor type using a requires clause with a fold expression:

// Require Functors
template <typename Start, typename End, typename... Functors>
    requires(is_Functor_v<Functors> && ...)
class Template {

Then assert that the first Functor has Start as first parameter and that the last Functor has End as the second parameter:

    // helper type to get a Functor (type) at a specific index:
    template <std::size_t I>
    using funcat = typename std::tuple_element_t<I, std::tuple<Functors...>>;

    static_assert(std::is_same_v<
                  Start, typename funcat<0>::first_type>);

    static_assert(std::is_same_v<
                  End, typename funcat<sizeof...(Functors) - 1>::second_type>);

Then checking that the second parameter of each Functor is the same type as the first parameter of the next Functor using a lambda and fold expression:

    static_assert([]<std::size_t... I>(std::index_sequence<I...>) {
        return (... && std::is_same_v<typename funcat<I>::second_type,
                                      typename funcat<I + 1>::first_type>);
    }(std::make_index_sequence<sizeof...(Functors) - 1>()));

---

You could also make a concept out of the is_Functor type trait if you prefer this declaration:

template <class T>
concept functor = is_Functor_v<T>;

template <typename Start, typename End, functor... Functors>
class Template {
   //
};

Demo

---

As for the second question, "How does one use std::is_convertible (or any of the other metaprogramming traits) on an un-specialized template class?", you could again create a type trait or concept that checks if a Functor can be instantiated by the supplied type without having to explicitly supply any template parameters.

Example concept:

template <class F, template <class...> class T>
concept deducible = requires(F&& f) {
    T(std::forward<F>(f));
};

And the class template would then need to use the Functor type each actual template parameter would be converted to:

template <typename Start, typename End, deducible<Functor>... Functors>
class Template {
    template <std::size_t I>
    using funcat =
        std::tuple_element_t<I,
            std::tuple<decltype(Functor(std::declval<Functors>()))...>>;
    // converted to Functor     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^            

    static_assert(std::is_same_v<
                  Start, typename funcat<0>::first_type>,
                  "First Functor::first_type != Start");

    static_assert(std::is_same_v<
                  End, typename funcat<sizeof...(Functors) - 1>::second_type>,
                  "Last Functor::second_type != End");

    static_assert([]<std::size_t... I>(std::index_sequence<I...>) {
        return (... && std::is_same_v<typename funcat<I>::second_type,
                                      typename funcat<I + 1>::first_type>);
    }(std::make_index_sequence<sizeof...(Functors) - 1>()),
                  "Functor_n<..., T> != Functor_n+1<T, ...>");
};

Demo where a std::pair<X, Y> is convertible into a Functor<X, Y> (odd conversion, but it's just an example).

Zorazorah

Answer 4

This answers the main question. The following seems to work. This gives the basic checking of proper sequence of Functors, and turning this into a concept, or adding a type traits-style using wrapper, etc..., can be left as a homework assignment:

class Start;
class End;

template <typename X, typename Y> class Functor {};

template<typename required, typename NextFunctor,
     typename ...RemainingFunctors> struct FunctorValidate;

template<typename required>
struct FunctorValidate<required, Functor<required, End>> {

    typedef void type_t;
};

template<typename required, typename NextFunctorType,
    typename FirstRemainingFunctor, typename ...RemainingFunctors>
struct FunctorValidate<required, Functor<required, NextFunctorType>,
    FirstRemainingFunctor, RemainingFunctors...>
    : FunctorValidate<NextFunctorType, FirstRemainingFunctor,
              RemainingFunctors...>
{
};

template<typename ...AllFunctors> struct FunctorChain
    : FunctorValidate<Start, AllFunctors...>
{
};

class A;
class B;
class C;

typedef FunctorChain<Functor<Start, A>,
             Functor<A, B>,
             Functor<B, C>,
             Functor<C, End>>::type_t ok1;

typedef FunctorChain<Functor<Start, End>>::type_t ok2;

#if 0
typedef FunctorChain<Functor<A, B>,
             Functor<B, C>,
             Functor<C, End>>::type_t error1;

typedef FunctorChain<Functor<Start, A>,
             Functor<A, B>,
             Functor<B, C>>::type_t error2;

typedef FunctorChain<Functor<Start, A>,
             Functor<B, C>,
             Functor<C, End>>::type_t error3;

#endif

Biaxial

Answer 5

You can use template specialization as a type-level pattern-matching engine to create a class template that not only validates a chain of Functors, but also extracts its “domain” and “codomain” types.

#include <type_traits>

template <typename T, typename U>
struct Functor { /* […] */ };

template <typename ...Fs>
struct chain_types;

template <typename T, typename U>
struct chain_types<Functor<T, U>>
{
    using from_t = T;
    using into_t = U;
};

template <typename T, typename U, typename ...Fs>
    requires (std::is_same_v<U, typename chain_types<Fs...>::from_t>)
struct chain_types<Functor<T, U>, Fs...>
{
    using from_t = T;
    using into_t = chain_types<Fs...>::into_t;
};

template <typename T, typename U, typename ...Fs>
    requires (
        std::is_same_v<T, typename chain_types<Fs...>::from_t> &&
        std::is_same_v<U, typename chain_types<Fs...>::into_t>
    )
class Template { /* […] */ };

Test case:

class A;
class B;
class C;

static_assert(
    std::is_same_v<A, chain_types<Functor<A, B>, Functor<B, C>>::from_t>);
static_assert(
    std::is_same_v<C, chain_types<Functor<A, B>, Functor<B, C>>::into_t>);
static_assert(
    requires { typename Template<A, C, Functor<A, B>, Functor<B, C>>; });

Need