recursive template instantiation exceeded maximum depth of 1024

Consider:

template<std::size_t N>
struct foobar : foobar<N - 1> { };

// some other condition for which this might get std::true_type.

template<>
struct foobar<0> : std::false_type { };

int main ( ) {

std::cout << foobar<5000>::value << ‘\n’;
}

This fails, unsurprisingly to anyone on this mailing list, with:

1>------ Build started: Project: project, Configuration: Debug x64 ------
1>main.cpp(334): fatal error : recursive template instantiation exceeded maximum depth of 1024
1>main.cpp(334): note: in instantiation of template class ‘foobar<3976>’ requested here
1>main.cpp(334): note: in instantiation of template class ‘foobar<3977>’ requested here
1>main.cpp(334): note: in instantiation of template class ‘foobar<3978>’ requested here
1>main.cpp(334): note: in instantiation of template class ‘foobar<3979>’ requested here
1>main.cpp(334): note: in instantiation of template class ‘foobar<3980>’ requested here
1>main.cpp(334): note: (skipping 1015 contexts in backtrace; use -ftemplate-backtrace-limit=0 to see all)
1>main.cpp(334): note: in instantiation of template class ‘foobar<4996>’ requested here
1>main.cpp(334): note: in instantiation of template class ‘foobar<4997>’ requested here
1>main.cpp(334): note: in instantiation of template class ‘foobar<4998>’ requested here
1>main.cpp(334): note: in instantiation of template class ‘foobar<4999>’ requested here
1>main.cpp(343): note: in instantiation of template class ‘foobar<5000>’ requested here
1>main.cpp(334): note: use -ftemplate-depth=N to increase recursive template instantiation depth
1>Done building project “project.vcxproj” – FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

This state of affairs seems poor to me. I have a background in the prolog programming language, in which recursive calls are ubiquitous, you cannot live without, recursion all the way. In prolog, a similar bit of code would be subject to tail-call optimization, which is a nice word for stating that iff the last call of a predicate (a prolog procedure of sorts) is the recursive one, that call will not be put on the stack (call frame re-use), as there is nothing more to do, i.e. won’t run out of stack-space (unless there is no stop condition of course, then you have an endless loop).

Can this be implemented?

Have a nice day,

degski

Hi degski,

You seem to be confusing run-time with compile-time. These errors are
issued by the compiler while analyzing the source. There is no call
stack yet.

If you want to compile this program, you can pass the
-ftemplate-depth=6000 option to the compiler.

You seem to be confusing run-time with compile-time. These errors are
issued by the compiler while analyzing the source.

I understand, that it is at compile-time (otherwise it wouldn't be a
problem). My point is, why is there in the case of recursive templates (as
like in the example) a depth-limit at all. I mean at each recursive
instantiation, there should be no need to increase the depth on each
instantiation, as one can "forget" about the ones already instantiated,
"they did not match".

There is no call stack yet.

Well, obviously I know nothing about how it works under the hood (and the
issue is not particular to clang, this is how all c++compilers work), but I
interpreted the fact that there is a depth at all, that there must be some
kind of stack-like mechanism.

Referring to prolog, the compiler/interpreter would translate such a
*tail-recursive
call* (which would fill the prolog-call-stack, if taken at face-value) into
iteration (by re-using the same stack-frame), which allows the "depth" to
be arbitrarily deep (as there is non).

Possibly, I'm expressing myself poorly, my apologies.

degski

The depth limit exists to ensure that template instantiation terminates.

Joerg

We all know what tail-recursion is. Template instantiation is not naturally tail-recursive from the perspective of the compiler implementation because, while you might think of your template as a function which computes the constant initializer of the value member, class template instantiation is in fact a complex process which produces (and memoizes) an entire instantiated class, and (w.r.t your example) the recursive instantiation of the base clause is merely one step in that process. In other words, the product of instantiation is a class, not a value, and the production of the value is not in tail position in the instantiation function.

The compiler must provide a template-instantiation engine which produces actual classes in order to satisfy the main purpose of class template instantiation, which is to produce types that are normally usable in the language. To naturally tail-recurse as you would like would require the compiler to include a recognizer of such templates and their uses which instead triggers a second, separate instantiation engine for the sole purpose of evaluating constant initializers in metaprograms; this would be a source of great redundancy, complexity, and bugs, and I suspect it would provide marginal value to most C++ compilations, even metaprogramming-heavy ones.

Alternatively, within the compiler implementation we avoid using direct recursion when recursively instantiating class templates and instead apply generic recursion-to-iteration techniques, such as iterating on a worklist and resuming previous instantiations from a stored continuation point when they become unblocked. However, that would require an extremely invasive restructuring of the compiler implementation, because it turns out that a rather shockingly long list of things in C++ can trigger class template instantiation, from name lookup to essentially every aspect of type-checking, and they would all need to be restructured to be paused and resumed. So instead we use direct recursion like pretty much every other C++ implementation, meaning we cannot recursively instantiate templates to an infinite depth without blowing out the stack.

John.

Thanks for such an in-depth and informative answer to my question.

Have a nice day,

degski