Since you asked about more general issues:
In general terms, it would be nice if we could accept arbitrarily-deep ASTs. We make some effort to do so, with three major efforts (in addition to expecting 8MB of stack space in each thread that might run Clang):
- Data recursion. RecursiveASTVisitor does this by default, and the constant evaluator does it when evaluating integer-valued expressions. But this is limited: you only get it where you apply it, and RAV’s automatic data recursion turns itself off when it thinks the difference might be observable in subclasses.
- Minimizing stack space during recursion. For example, during “regular” function template instantiation at the end of the translation unit, we try to keep the size of the recursive frame as small as possible.
- The “runWithSufficientStackSpace” mechanism that tries to check that “enough” stack space is available and pops out a diagnostic (and as a slow-but-correct fallback, allocates a new stack) if we’re getting close to running out.
Applying these techniques (largely in the above order) should be encouraged, and if we can make memoizedMatchesAncestorOfRecursively do so, that seems like a good directed approach for the local problem. But it’s unlikely that we’ll ever cover enough ground here to consistently prevent ever running out of stack in all cases – not unless we fully move away from recursion as an implementation technique, which seems implausible, or add “runWithSufficientStackSpace” calls to every call graph SCC, which seems expensive. So this is currently done pragmatically: we fix stack usage issues as we see them become a problem. And in the remaining cases, we crash
Not the end of the world for a compiler, but not great for more or less any other user of Clang as a library.
For standards-conformance, our backstop here are so-called “implementation limits” – we’re permitted to bail out if things get too complex, and we largely get to define what that means. C has some minimal requirements here – for example, that we can support at least one program with 63 levels of nested parentheses; C++ has only suggestions and no hard requirements. But in either case, if our limits are violated, there are no constraints on our behavior; we’re allowed to crash or whatever. So that puts us in quality-of-implementation land.
Now, we do have some defined implementation limits (and there has been some work done towards improving and formalizing them: https://reviews.llvm.org/D72053). In the specific case of expanding a fold-expression, the relevant implementation limit is LangOptions::BracketDepth, which limits the total number of parentheses, braces, or square brackets that can be open at once, but that limit is currently only applied when parsing, not during template instantiation. So in this specific case, as a bare minimum, I think we’re missing a check for that language option during fold-expression expansion (each level of a fold-expression introduces a set of parentheses, so even a pedantic interpretation of the rules has us covered reusing the same limit here).
As for limiting the size of packs in general: I think it might make sense to impose a limit – not to avoid excessive recursion; we should have other mechanisms to deal with that – but to avoid huge memory usage during compilation due to forming overly-large packs. Eg, passing a very large integer to the __make_integer_seq builtin can easily cause Clang to fall into a hole from which it will never escape, assuming you don’t run out of address space and just crash.
Setting an implementation limit on the overall depth of the AST could be interesting, if there’s a way we can practically do it. This seems like a hard problem – there are just too many different places and ways in which AST nodes are created, many of them aren’t equipped to cope with the operation failing in some kind of gracefully-recoverable way, and just keeping track of the AST depth without paying a code complexity and memory usage cost seems like a challenge – and we’d need to be sure the cost of solving it is worth the benefit.