c++ variadic template instantiation depth exceeds maximum of 900

user_8486247 0
Viewed 1787

I am using c++11 variadic template, however the compiler complains template instantiation depth excedds maximun of 900, the code looks like: 

template<typename F1, typename F2>
composed<F1, F2> compose(F1 f1, F2 f2) {
    return composed<F1, F2>(f1, f2);
}
template<typename F1, typename F2, typename... Fs>
auto compose(F1 f1, F2 f2, Fs... fs) ->decltype(compose(compose(f1, f2), fs...)) {
    return compose(compose(f1, f2), fs...);
}

I am using this template like:

auto composed_func = compose(f1, f2, f3, f4);

But if I change the variadic template defination to:

template<typename F1, typename F2, typename F3, typename... Fs>
auto compose(F1 f1, F2 f2, F3 f3, Fs... fs) ->decltype(compose(compose(f1, f2), f3, fs...)) {
    return compose(compose(f1, f2), f3, fs...);
}

It will work OK. I am not clear why this happened. It seems to me that the upper usage also looks valid since it still recursively reduce the args to call compose.

trailing-return-type variadic-templates c++11 c++
2 Answers

You have infinite recursion in your second function: it does not call the first function, as you may have thought, but calls itself instead:

template<typename F1, typename F2, typename... Fs>
auto compose(F1 f1, F2 f2, Fs... fs) ->decltype(compose(compose(f1, f2), fs...)) {
    return compose(compose(f1, f2), fs...);
}

Let's say you call:

compose(f, g, h);

This invokes the function with F1 = decltype(f), F2 = decltype(g), and Fs = {decltype(h)}. The function then goes on and invokes:

compose(f1, f2)

which is actually:

compose(f, g);

This invokes the same function with F1 = decltype(f), F2 = decltype(g), and an empty Fs = {}. Basically executing:

compose(compose(f, g));

Which again calls itself with F1 = decltype(f), F2 = decltype(g), and an empty Fs = {}. And this goes on to infinity, or until the limit of 900 is reached.

What you need is to make sure that the second function is relevant only when there is something after f2:

template<typename F1, typename F2, typename F3, typename... Fs>
auto compose(F1 f1, F2 f2, F3 f3, Fs... fs) ->decltype(compose(compose(f1, f2), f3, fs...)) {
    return compose(compose(f1, f2), f3, fs...);
}
user_49554980

You might fix it with:

template<typename F1, typename F2>
composed<F1, F2> compose(F1 f1, F2 f2) {
    return composed<F1, F2>(f1, f2);
}

template<typename F1, typename F2, typename... Fs>
auto compose(F1 f1, F2 f2, Fs... fs)
->decltype(compose(::compose(f1, f2), fs...))
{
    return compose(compose(f1, f2), fs...);
}

Demo

Unqualified names can be found by ADL and name is search at the point of instantiation.

so, with unqualified look up, we first generated the candidates (even if they won't be the better match)

compose(f, g) can be:

  • template<typename F1, typename F2> compose
  • or template<typename F1, typename F2, typename...Fs> compose. (with FS empty pack)

for the later case, we have decltype(compose(compose(f, g))) to resolve, and so compose(f, g) again -> infinite recursion.

On the other part, qualified names is search immediately, and only fully declared functions can be found (so not itself, as the trailing-return-type is part of the declaration). so ::compose avoid to consider itself as candidate of overloads.

user_26845390
Related