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?

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.