CODEWITHSUNDEEP
c++templatesrecursionc++11variadic-templates
djfm
djfm

Reputation: 2458

Infinite recursion in variadic template instantiation trying to build arbitrary depth tree-like structure

I'm doing some experimentation with variadics and I've stumbled into an issue I can't figure out the solution of - basically I'm trying to build a tree with components of arbitrary data types - here is some code:

template <class A, class B>
struct SeqExpression
{
    const A & first;
    const B & then;
};

template <class A, class B>
SeqExpression<A,B>
make_seq(const A & a, const B & b)
{
    return {a,b};
}

template <class A, class B, class ...T>
auto
make_seq(const A & first, const B & second, T ...rest) -> decltype(make_seq(make_seq(first,second),rest...))
{

    return make_seq(make_seq(first,second),rest...);
}

Then I try:

auto x = make_seq("X","Y",'z');

But GCC(4.7) tells me:

error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) substituting ‘template<class A, class B, class ... T> decltype (make_seq(make_seq(first, second), rest ...)) make_seq(const A&, const B&, T ...) [with A = SeqExpression<char [2], char [2]>; B = char; T = {}]’
recursively required by substitution of ‘template<class A, class B, class ... T> decltype (make_seq(make_seq(first, second), rest ...)) make_seq(const A&, const B&, T ...) [with A = SeqExpression<char [2], char [2]>; B = char; T = {}]’
required by substitution of ‘template<class A, class B, class ... T> decltype (make_seq(make_seq(first, second), rest ...)) make_seq(const A&, const B&, T ...) [with A = char [2]; B = char [2]; T = {char}]’

It seems to me though that it should be solvable !

make_seq("X","Y") has type SeqExpression< char[2],char[2] > so make_seq(make_seq("X","Y"),'z') has type SeqExpression< SeqExpression< char[2],char[2] >,char >

and it seems relatively non-loopy to me.

Any thoughts?

Upvotes: 5

Views: 992

Answers (1)

ecatmur
ecatmur

Reputation: 157344

The problem is that your variadic template is being selected when you have two arguments (over the two-argument template). You need to ensure that it is only selected when you have at least three arguments; the easiest way is to add another argument:

template <class A, class B, class C, class ...T>
auto
make_seq(const A & first, const B & second, const C &third, T ...rest)
 -> decltype(make_seq(make_seq(first,second), third, rest...))
{

    return make_seq(make_seq(first,second), third, rest...);
}

Variadic argument packs can and will match zero arguments; it might seem surprising but it's better than the alternative.

Note that apparently the above exploits a non-standard g++ extension for the return type. The following type program should be able to compute the type corresponding to a parameter sequence:

template <int n, class ...T> struct mst_helper;
template <class A, class B>
struct mst_helper<2, A, B> { typedef SeqExpression<A, B> type; };
template <int n, class A, class B, class ...T>
struct mst_helper<n, A, B, T...> {
    typedef typename mst_helper<n - 1, SeqExpression<A, B>, T...>::type type; };
template <class ...T>
struct make_seq_type { typedef typename mst_helper<sizeof...(T), T...>::type type; };

template <class A, class B, class C, class ...T>
typename make_seq_type<A, B, C, T...>::type
make_seq(const A & first, const B & second, const C &third, T ...rest)
{
    return make_seq(make_seq(first,second), third, rest...);
}

g++-4.7.1 seems to have a bug with template aliases, so I had to use struct instead of using.

Upvotes: 3

Related Questions