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

[degski via cfe-dev]

On 18 July 2018 at 10:03, John McCall <rjmccall at apple.com> wrote:

> 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.
>

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

Have a nice day,

degski
-- 
*"If something cannot go on forever, it will stop" - Herbert Stein*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20180718/763e1c02/attachment.html>