[ASTMatchers] Avoid pathological traversal over nested lambdas

[alexfh]

This fixes the issue with exponential traversal times for deeply nested lambdas. Please add a test though. For example, this one:

void f() {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  [] {
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
  }();
}

[alexfh]

Thanks for the prompt fix, btw!

clang/include/clang/AST/RecursiveASTVisitor.h

2064

Please specify the type explicitly here.

[rsmith]

clang/include/clang/AST/RecursiveASTVisitor.h

2063–2065

This is incorrectly skipping the bodies of all other lambda member functions (default ctor, copy ctor, destructor, implicit conversion to function pointer type), not only the "body" of the lambda itself (the definition of the operator()).

[steveire]

clang/include/clang/AST/RecursiveASTVisitor.h

2063–2065

Please see https://reviews.llvm.org/D95644.

[sammccall]

Since the 12 branch has been cut, I've added a blocking bug to get this fixed in some form: https://bugs.llvm.org/show_bug.cgi?id=48935

@rsmith I've assigned it to you to make a call about whether to cherrypick this patch, this patch+followup, or revert the original change on the branch.
(@steveire is a revert really an option here, or is there already more stuff relying on this?)

clang/include/clang/AST/RecursiveASTVisitor.h

public:
   /// Return whether this visitor should recurse into the types of
   /// TypeLocs.
   bool shouldWalkTypesOfTypeLocs() const { return true; }
 
   /// Return whether this visitor should recurse into implicit
   /// code, e.g., implicit constructors and destructors.
   bool shouldVisitImplicitCode() const { return false; }
 
+  /// Return whether this visitor should recurse into lambda body
+  bool shouldVisitLambdaBody() const { return true; }
+
   /// Return whether this visitor should traverse post-order.
   bool shouldTraversePostOrder() const { return false; }
 
   /// Recursively visits an entire AST, starting from the top-level Decls
   /// in the AST traversal scope (by default, the TranslationUnitDecl).
   /// \returns false if visitation was terminated early.
   bool TraverseAST(ASTContext &AST) {
     for (Decl *D : AST.getTraversalScope())
bool RecursiveASTVisitor<Derived>::TraverseFunctionHelper(FunctionDecl *D) {
   }
 
   bool VisitBody =
       D->isThisDeclarationADefinition() &&
       // Don't visit the function body if the function definition is generated
       // by clang.
       (!D->isDefaulted() || getDerived().shouldVisitImplicitCode());
 
+  if (const auto *MD = dyn_cast<CXXMethodDecl>(D)) {
+    if (const CXXRecordDecl *RD = MD->getParent()) {
+      if (RD->isLambda()) {
+        VisitBody = VisitBody && getDerived().shouldVisitLambdaBody();
+      }
+    }
+  }
+
   if (VisitBody) {
     TRY_TO(TraverseStmt(D->getBody())); // Function body.
   }
   return true;
 }
 
 DEF_TRAVERSE_DECL(FunctionDecl, {
   // We skip decls_begin/decls_end, which are already covered by

clang/lib/ASTMatchers/ASTMatchFinder.cpp

if (auto *RF = dyn_cast<CXXForRangeStmt>(S)) {
           TraverseType(E);
 
         if (Expr *NE = T->getNoexceptExpr())
           TraverseStmt(NE, Queue);
 
         if (LE->hasExplicitResultType())
           TraverseTypeLoc(Proto.getReturnLoc());
         TraverseStmt(LE->getTrailingRequiresClause());
+      }
 
-        TraverseStmt(LE->getBody());
-      }
       return true;
     }
     return RecursiveASTVisitor<MatchASTVisitor>::dataTraverseNode(S, Queue);
   }
 
   // Matches children or descendants of 'Node' with 'BaseMatcher'.
   bool memoizedMatchesRecursively(const DynTypedNode &Node, ASTContext &Ctx,
                                   const DynTypedMatcher &Matcher,
public:
   }
 
   // Implements ASTMatchFinder::getASTContext.
   ASTContext &getASTContext() const override { return *ActiveASTContext; }
 
   bool shouldVisitTemplateInstantiations() const { return true; }
   bool shouldVisitImplicitCode() const { return true; }
 
+  // We visit the lambda body explicitly, so instruct the RAV
+  // to not visit it on our behalf too.
+  bool shouldVisitLambdaBody() const { return false; }
+
   bool IsMatchingInASTNodeNotSpelledInSource() const override {
     return TraversingASTNodeNotSpelledInSource;
   }
   bool isMatchingChildrenNotSpelledInSource() const override {
     return TraversingASTChildrenNotSpelledInSource;
   }
   void setMatchingChildrenNotSpelledInSource(bool Set) override {
     TraversingASTChildrenNotSpelledInSource = Set;

clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp

EXPECT_TRUE(matchesConditionally(
             TK_IgnoreUnlessSpelledInSource,
             binaryOperation(hasOperatorName("=="),
                             hasLHS(declRefExpr(to(varDecl(hasName("F1"))))),
                             hasRHS(declRefExpr(to(varDecl(hasName("F2"))))))),
         true, {"-std=c++20"}));
   }
 }
 
+TEST(IgnoringImpCasts, PathologicalLambda) {
+
+  // Test that deeply nested lambdas are not a performance penalty
+  StringRef Code = R"cpp(
+void f() {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+  [] {
+    int i = 42;
+    (void)i;
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+  }();
+}
+  )cpp";
+
+  EXPECT_TRUE(matches(Code, integerLiteral(equals(42))));
+  EXPECT_TRUE(matches(Code, functionDecl(hasDescendant(integerLiteral(equals(42))))));
+}
+
 TEST(IgnoringImpCasts, MatchesImpCasts) {
   // This test checks that ignoringImpCasts matches when implicit casts are
   // present and its inner matcher alone does not match.
   // Note that this test creates an implicit const cast.
   EXPECT_TRUE(matches("int x = 0; const int y = x;",
                       varDecl(hasInitializer(ignoringImpCasts(
                         declRefExpr(to(varDecl(hasName("x")))))))));
   // This test creates an implict cast from int to char.