[cfe-dev] Limits on AST depth and stack usage?

Sam McCall via cfe-dev cfe-dev at lists.llvm.org
Mon Aug 31 08:22:11 PDT 2020

This program creates an AST of depth 10000:

template <class T, T...V> struct seq {
  constexpr bool zero() { return (true && ... && (V == 0)); };
constexpr unsigned N = 10000;
auto x = __make_integer_seq<seq, int, N>{};
static_assert(!x.zero(), "");

On my machine, clang-10 parses this successfully (slowly!) but crashes if I
increase to 100000.
I suppose -ftemplate-depth doesn't apply as there's no actual recursion
here (just fold-expressions), but I feel like some implementation limit
*should* apply: clang relies heavily on being able to traverse the AST
recursively, and will inevitably crash if the tree is too tall.

Should there be a limit here? It seems tempting to say one of:
 -ftemplate-depth should constrain either the number of arguments a pack
can represent
 -ftemplate-depth should constrain the size of pack that can be unfolded
 -some limit should constrain the overall AST height


The immediate problem we're dealing with is that
https://reviews.llvm.org/D85621 increased the size of DynTypedNode from
32->56 and we're seeing clang-tidy crashes due to stack overflow in the
recursive traversal MatchASTVisitor::memoizedMatchesAncestorOfRecursively.

However this is on a unit test very similar to the above (with N=2000) so
before trying to squeeze stack usage I'd like to understand what we should
be aiming to support.

(Tangentially related: Richard, if you think there are good ways to squeeze
TemplateArgumentLoc, that'd be interesting to know. Currently it's by-value
and holds TemplateArgument and TemplateArgumentLocInfo which are 24 bytes
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20200831/34b6d369/attachment.html>

More information about the cfe-dev mailing list