[cfe-dev] recursive template instantiation exceeded maximum depth of 1024

[John McCall via cfe-dev]

> On Jul 16, 2018, at 5:08 AM, degski via cfe-dev <cfe-dev at lists.llvm.org> wrote:
> 
> On 16 July 2018 at 11:06, Csaba Raduly <rcsaba at gmail.com <mailto:rcsaba at gmail.com>> wrote:
> 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).

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20180718/d5236ab8/attachment.html>