<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">RecursiveASTVisitor::TraverseStmt has a `DataRecursionQueue *Queue` in its signature to prevent stack overflow by default (as Richard once helpfully explained to me). ASTMatchers uses the DataRecursionQueue, so that searching for matches in Stmt children should never overflow the stack, I believe (though it does confuse users who expect a more orderly traversal…but that’s another matter).<div class=""><br class=""></div><div class="">But `memoizedMatchesAncestorOfRecursively` does *not* use data recursion, as you’ve noted. So in other words it is using data recursion when traversing descendants of deeply nested Exprs, but not when traversing the ancestors of those at the bottom. </div><div class=""><br class=""></div><div class="">So, I think it could just be a limited problem with a simple solution: there should be a non-recursive, loop-based version of memoizedMatchesAncestorOfRecursively specific to traversing the ancestors of Stmts/Exprs, mirroring what RecursiveASTVisitor::TraverseStmt does.</div><div class=""><br class=""></div><div class="">Whether there are more general issues with e.g. evaluating extremely deep ASTs, is beyond my own depth, though...</div><div class=""><br class=""></div><div class="">Dave<br class=""></div><div class=""><br class=""></div><div><br class=""><blockquote type="cite" class=""><div class="">On Aug 31, 2020, at 11:33 AM, Sam McCall via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org" class="">cfe-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">(doh, obviously that first "constexpr" shouldn't be there)</div><br class=""><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Aug 31, 2020 at 5:22 PM Sam McCall <<a href="mailto:sammccall@google.com" class="">sammccall@google.com</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr" class="">This program creates an AST of depth 10000:<div class=""><br class=""></div><div class="">constexpr </div><div class="">template <class T, T...V> struct seq {<br class=""></div><div class=""> constexpr bool zero() { return (true && ... && (V == 0)); };<br class=""></div><div class="">};</div><div class="">constexpr unsigned N = 10000;</div><div class="">auto x = __make_integer_seq<seq, int, N>{};<br class=""></div><div class="">static_assert(!x.zero(), "");<br class=""></div><div class=""><br class=""></div><div class="">On my machine, clang-10 parses this successfully (slowly!) but crashes if I increase to 100000.</div><div class="">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.</div><div class=""><br class=""></div><div class="">Should there be a limit here? It seems tempting to say one of:</div><div class=""> -ftemplate-depth should constrain either the number of arguments a pack can represent</div><div class=""> -ftemplate-depth should constrain the size of pack that can be unfolded</div><div class=""> -some limit should constrain the overall AST height</div><div class=""><br class=""></div><div class="">---</div><div class=""><br class=""></div><div class="">The immediate problem we're dealing with is that <a href="https://reviews.llvm.org/D85621" target="_blank" class="">https://reviews.llvm.org/D85621</a> 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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">(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 each)</div></div>
</blockquote></div>
_______________________________________________<br class="">cfe-dev mailing list<br class=""><a href="mailto:cfe-dev@lists.llvm.org" class="">cfe-dev@lists.llvm.org</a><br class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev<br class=""></div></blockquote></div><br class=""></body></html>