[clang] Limit the maximum level of fold-expr expansion.

[hokein]

Summary

Introduce a new diagnostic, and respect the bracket-depth (256) by default.

[sammccall]

clang/include/clang/Basic/DiagnosticSemaKinds.td

5095

I think this should be NoSFINAE, similar to err_template_recursion_depth_exceeded.

Maybe DefaultFatal too?

5096

The diagnostic test could be clearer: what's a "fold expression expansion level"?

what about "instantiating fold expression with %0 arguments exceeds expression nesting limit of %1"?

clang/lib/Sema/TreeTransform.h

13196

The brackets here are not obvious. Also we're not actually tracking bracket *depth*! So this definitely needs a comment.

Something like:

// Formally a fold expression expands to nested parenthesized expressions.
// Enforce this limit to avoid creating trees so deep we can't safely traverse them

13197

you might also want to emit note_bracket_depth (I don't think you need to clone it if we get the wording right)

clang/test/SemaCXX/fold_expr_expansion_limit.cpp

9

this diagnostic is bogus :-(
default-fatal would fix this, I guess.

[hokein]

address review comments.

clang/lib/Sema/TreeTransform.h

13197

note_bracket_depth is from parse diagnostic, introducing it in Sema feels like a slight layer violation, but the compile should be fine, because all diagnostic headers in the support library.

clang/test/SemaCXX/fold_expr_expansion_limit.cpp

9

oh, yeah, if a fatal error is emitted, all subsequent diagnostics will be silenced.

[sammccall]

clang/include/clang/Basic/DiagnosticSemaKinds.td

5096

arguements -> arguments

[hokein]

fix a typo.

[erichkeane]

Why did we select the 'bracket-depth' for this? The documentation on that doesn't seem to be anything close to what this should be based on:

Sets the limit for nested parentheses, brackets, and braces to N in blocks, declarators, expressions, and struct or union declarations.

The 256 default limit is REALLY small for a fold expression, particularly since the instantiation depth limit is 1024 by default. I think this patch needs to be changed to use the InstantiationDepth instead. @rjmccall, thoughts?

[erichkeane]

In D86936#2338664, @erichkeane wrote:

Why did we select the 'bracket-depth' for this? The documentation on that doesn't seem to be anything close to what this should be based on:

Sets the limit for nested parentheses, brackets, and braces to N in blocks, declarators, expressions, and struct or union declarations.

The 256 default limit is REALLY small for a fold expression, particularly since the instantiation depth limit is 1024 by default. I think this patch needs to be changed to use the InstantiationDepth instead. @rjmccall, thoughts?

Even that limit (1024) seems like it is perhaps a little conservative. Apparently, this comes up in Boost Numerics, where they use a pack of size 1089 at one point that they use a '+' fold expression that this causes us to no longer be able to build.

[sammccall]

In D86936#2338664, @erichkeane wrote:

Why did we select the 'bracket-depth' for this? The documentation on that doesn't seem to be anything close to what this should be based on:

Based on a discussion with @rsmith - the formal definition of pack expansion is that it expands to nested parenthesized expressions expressions.

Sets the limit for nested parentheses, brackets, and braces to N in blocks, declarators, expressions, and struct or union declarations.

The 256 default limit is REALLY small for a fold expression, particularly since the instantiation depth limit is 1024 by default. I think this patch needs to be changed to use the InstantiationDepth instead. @rjmccall, thoughts?

One motivation here is to limit exposure of tools to stack overflows. A modest increase in the stack size of DynTypedNode triggered stack overflows in various traversals on real code.
While it's possible in principle to write traversals that use only data recursion (and I've also fixed the ones in clang itself that I can find), in practice a lot of code and tools rely on recursive traversals, so trivially creating arbitrarily deep ASTs without any limit is certain to break things with unclear responsibility. (Whereas this change places responsibility with boost numerics).

FWIW, somewhere between 1024 and 2048 was the critical depth on the systems we looked at, so 1024 seems... plausible, but large.

clang/include/clang/Basic/DiagnosticSemaKinds.td

 
 def err_fold_expression_packs_both_sides : Error<
   "binary fold expression has unexpanded parameter packs in both operands">;
 def err_fold_expression_empty : Error<
   "unary fold expression has empty expansion for operator '%0' "
   "with no fallback value">;
 def err_fold_expression_bad_operand : Error<
   "expression not permitted as operand of fold expression">;
+def err_fold_expression_limit_exceeded: Error<
+  "instantiating fold expression with %0 arguments exceeded expression nesting "
+  "limit of %1">, DefaultFatal, NoSFINAE;
 
 def err_unexpected_typedef : Error<
   "unexpected type name %0: expected expression">;
 def err_unexpected_namespace : Error<
   "unexpected namespace name %0: expected expression">;
 def err_undeclared_var_use : Error<"use of undeclared identifier %0">;
 def ext_undeclared_unqual_id_with_dependent_base : ExtWarn<
   "use of undeclared identifier %0; "

clang/lib/Sema/TreeTransform.h

 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/ExprObjC.h"
 #include "clang/AST/ExprOpenMP.h"
 #include "clang/AST/OpenMPClause.h"
 #include "clang/AST/Stmt.h"
 #include "clang/AST/StmtCXX.h"
 #include "clang/AST/StmtObjC.h"
 #include "clang/AST/StmtOpenMP.h"
+#include "clang/Basic/DiagnosticParse.h"
 #include "clang/Basic/OpenMPKinds.h"
 #include "clang/Sema/Designator.h"
 #include "clang/Sema/Lookup.h"
 #include "clang/Sema/Ownership.h"
 #include "clang/Sema/ParsedTemplate.h"
 #include "clang/Sema/ScopeInfo.h"
 #include "clang/Sema/SemaDiagnostic.h"
 #include "clang/Sema/SemaInternal.h"
if (!Expand) {
     if (!getDerived().AlwaysRebuild() &&
         LHS.get() == E->getLHS() && RHS.get() == E->getRHS())
       return E;
 
     return getDerived().RebuildCXXFoldExpr(
         Callee, E->getBeginLoc(), LHS.get(), E->getOperator(),
         E->getEllipsisLoc(), RHS.get(), E->getEndLoc(), NumExpansions);
   }
 
+  // Formally a fold expression expands to nested parenthesized expressions.
+  // Enforce this limit to avoid creating trees so deep we can't safely traverse
+  // them.
+  if (NumExpansions && SemaRef.getLangOpts().BracketDepth < NumExpansions) {
+    SemaRef.Diag(E->getEllipsisLoc(),
+                 clang::diag::err_fold_expression_limit_exceeded)
+        << *NumExpansions << SemaRef.getLangOpts().BracketDepth
+        << E->getSourceRange();
+    SemaRef.Diag(E->getEllipsisLoc(), diag::note_bracket_depth);
+    return ExprError();
+  }
+
   // The transform has determined that we should perform an elementwise
   // expansion of the pattern. Do so.
   ExprResult Result = getDerived().TransformExpr(E->getInit());
   if (Result.isInvalid())
     return true;
   bool LeftFold = E->isLeftFold();
 
   // If we're retaining an expansion for a right fold, it is the innermost

clang/test/SemaCXX/fold_expr_expansion_limit.cpp

+// RUN: %clang_cc1 -fsyntax-only -fbracket-depth 2 -verify -std=c++17 %s
+
+template <class T, T... V> struct seq {
+  constexpr bool zero() { return (true && ... && (V == 0)); }; // expected-error {{instantiating fold expression with 3 arguments exceeded expression nesting limit of 2}} \
+                                                                  expected-note {{use -fbracket-depth}}
+};
+constexpr unsigned N = 3;
+auto x = __make_integer_seq<seq, int, N>{};
+static_assert(!x.zero(), ""); // expected-note {{in instantiation of member function}}