[ASTMatchers] Ensure that we can match inside lambdas

[steveire]

Summary

Because we don't know in ASTMatchFinder whether we're matching in AsIs
or IgnoreUnlessSpelledInSource mode, we need to traverse the lambda
twice, but store whether we're matching in nodes spelled in source or
not.

[steveire]

Update

[aaron.ballman]

clang/lib/ASTMatchers/ASTMatchFinder.cpp

478–487

512–513

516

526

Do we also need to traverse attributes of the lambda?

clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp

3069

Do we have other test coverage for the rest of lambda matching, or should you add coverage for things like parameters, trailing requires clauses, etc?

[steveire]

Update

[steveire]

Update

[steveire]

clang/lib/ASTMatchers/ASTMatchFinder.cpp

526

At least RAV doesn't do so. It would be a new feature which is orthogonal to this MR/patch.

clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp

3069

Yep, there's other lambda-related tests higher up in this test function.

[aaron.ballman]

LGTM

clang/lib/ASTMatchers/ASTMatchFinder.cpp

526

Okay, SGTM

[alexfh]

This patch causes practically infinite traversal times on code that contains deeply nested lambdas. I'll try to get a suitable repro, but could you maybe revert this in the meantime?

[alexfh]

In D93688#2525947, @alexfh wrote:

This patch causes practically infinite traversal times on code that contains deeply nested lambdas. I'll try to get a suitable repro, but could you maybe revert this in the meantime?

Actually, there's a very simple test case:

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

It looks like each lambda traversal triggers multiple traversals of the same AST fragment causing exponential growth of the traversal time.

clang/include/clang/ASTMatchers/ASTMatchersInternal.h

bool matchesAncestorOf(const T &Node, const DynTypedMatcher &Matcher,
     return matchesAncestorOf(DynTypedNode::create(Node), getASTContext(),
                              Matcher, Builder, MatchMode);
   }
 
   virtual ASTContext &getASTContext() const = 0;
 
   virtual bool IsMatchingInASTNodeNotSpelledInSource() const = 0;
 
+  virtual bool IsMatchingInASTNodeNotAsIs() const = 0;
+
   bool isTraversalIgnoringImplicitNodes() const;
 
 protected:
   virtual bool matchesChildOf(const DynTypedNode &Node, ASTContext &Ctx,
                               const DynTypedMatcher &Matcher,
                               BoundNodesTreeBuilder *Builder,
                               BindKind Bind) = 0;
 

clang/lib/ASTMatchers/ASTMatchFinder.cpp

if (auto *RF = dyn_cast<CXXForRangeStmt>(S)) {
             SubStmt == RF->getRangeInit() || SubStmt == RF->getBody()) {
           TraverseStmt(SubStmt, Queue);
         } else {
           ASTNodeNotSpelledInSourceScope RAII(this, true);
           TraverseStmt(SubStmt, Queue);
         }
       }
       return true;
+    } else if (auto *LE = dyn_cast<LambdaExpr>(S)) {
+      for (auto I : llvm::zip(LE->captures(), LE->capture_inits())) {
+        auto C = std::get<0>(I);
+        ASTNodeNotSpelledInSourceScope RAII(
+            this, TraversingASTNodeNotSpelledInSource || !C.isExplicit());
+        TraverseLambdaCapture(LE, &C, std::get<1>(I));
+      }
+
+      {
+        ASTNodeNotSpelledInSourceScope RAII(this, true);
+        TraverseDecl(LE->getLambdaClass());
+      }
+      {
+        ASTNodeNotAsIsSourceScope RAII(this, true);
+
+        // We need to poke around to find the bits that might be explicitly
+        // written.
+        TypeLoc TL = LE->getCallOperator()->getTypeSourceInfo()->getTypeLoc();
+        FunctionProtoTypeLoc Proto = TL.getAsAdjusted<FunctionProtoTypeLoc>();
+
+        if (auto *TPL = LE->getTemplateParameterList()) {
+          for (NamedDecl *D : *TPL) {
+            TraverseDecl(D);
+          }
+          if (Expr *RequiresClause = TPL->getRequiresClause()) {
+            TraverseStmt(RequiresClause);
+          }
+        }
+
+        if (LE->hasExplicitParameters()) {
+          // Visit parameters.
+          for (ParmVarDecl *Param : Proto.getParams())
+            TraverseDecl(Param);
+        }
+
+        const auto *T = Proto.getTypePtr();
+        for (const auto &E : T->exceptions())
+          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,
                                   BoundNodesTreeBuilder *Builder, int MaxDepth,
public:
   ASTContext &getASTContext() const override { return *ActiveASTContext; }
 
   bool shouldVisitTemplateInstantiations() const { return true; }
   bool shouldVisitImplicitCode() const { return true; }
 
   bool IsMatchingInASTNodeNotSpelledInSource() const override {
     return TraversingASTNodeNotSpelledInSource;
   }
+  bool IsMatchingInASTNodeNotAsIs() const override {
+    return TraversingASTNodeNotAsIs;
+  }
 
   bool TraverseTemplateInstantiations(ClassTemplateDecl *D) {
     ASTNodeNotSpelledInSourceScope RAII(this, true);
     return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
         D);
   }
 
   bool TraverseTemplateInstantiations(VarTemplateDecl *D) {
     ASTNodeNotSpelledInSourceScope RAII(this, true);
     return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
         D);
   }
 
   bool TraverseTemplateInstantiations(FunctionTemplateDecl *D) {
     ASTNodeNotSpelledInSourceScope RAII(this, true);
     return RecursiveASTVisitor<MatchASTVisitor>::TraverseTemplateInstantiations(
         D);
   }
 
 private:
   bool TraversingASTNodeNotSpelledInSource = false;
+  bool TraversingASTNodeNotAsIs = false;
   bool TraversingASTChildrenNotSpelledInSource = false;
 
   struct ASTNodeNotSpelledInSourceScope {
     ASTNodeNotSpelledInSourceScope(MatchASTVisitor *V, bool B)
         : MV(V), MB(V->TraversingASTNodeNotSpelledInSource) {
       V->TraversingASTNodeNotSpelledInSource = B;
     }
     ~ASTNodeNotSpelledInSourceScope() {
       MV->TraversingASTNodeNotSpelledInSource = MB;
     }
 
   private:
     MatchASTVisitor *MV;
     bool MB;
   };
 
+  struct ASTNodeNotAsIsSourceScope {
+    ASTNodeNotAsIsSourceScope(MatchASTVisitor *V, bool B)
+        : MV(V), MB(V->TraversingASTNodeNotAsIs) {
+      V->TraversingASTNodeNotAsIs = B;
+    }
+    ~ASTNodeNotAsIsSourceScope() { MV->TraversingASTNodeNotAsIs = MB; }
+
+  private:
+    MatchASTVisitor *MV;
+    bool MB;
+  };
+
   struct ASTChildrenNotSpelledInSource {
     ASTChildrenNotSpelledInSource(MatchASTVisitor *V, bool B)
         : MV(V), MB(V->TraversingASTChildrenNotSpelledInSource) {
       V->TraversingASTChildrenNotSpelledInSource = B;
     }
     ~ASTChildrenNotSpelledInSource() {
       MV->TraversingASTChildrenNotSpelledInSource = MB;
     }

clang/lib/ASTMatchers/ASTMatchersInternal.cpp

bool DynTypedMatcher::matches(const DynTypedNode &DynNode,
                               BoundNodesTreeBuilder *Builder) const {
   TraversalKindScope RAII(Finder->getASTContext(),
                           Implementation->TraversalKind());
 
   if (Finder->isTraversalIgnoringImplicitNodes() &&
       Finder->IsMatchingInASTNodeNotSpelledInSource())
     return false;
 
+  if (!Finder->isTraversalIgnoringImplicitNodes() &&
+      Finder->IsMatchingInASTNodeNotAsIs())
+    return false;
+
   auto N =
       Finder->getASTContext().getParentMapContext().traverseIgnored(DynNode);
 
   if (RestrictKind.isBaseOf(N.getNodeKind()) &&
       Implementation->dynMatches(N, Finder, Builder)) {
     return true;
   }
   // Delete all bindings when a matcher does not match.
   // This prevents unexpected exposure of bound nodes in unmatches
   // branches of the match tree.
   Builder->removeBindings([](const BoundNodesMap &) { return true; });
   return false;
 }
 
 bool DynTypedMatcher::matchesNoKindCheck(const DynTypedNode &DynNode,
                                          ASTMatchFinder *Finder,
                                          BoundNodesTreeBuilder *Builder) const {
   TraversalKindScope raii(Finder->getASTContext(),
                           Implementation->TraversalKind());
 
   if (Finder->isTraversalIgnoringImplicitNodes() &&
       Finder->IsMatchingInASTNodeNotSpelledInSource())
     return false;
 
+  if (!Finder->isTraversalIgnoringImplicitNodes() &&
+      Finder->IsMatchingInASTNodeNotAsIs())
+    return false;
+
   auto N =
       Finder->getASTContext().getParentMapContext().traverseIgnored(DynNode);
 
   assert(RestrictKind.isBaseOf(N.getNodeKind()));
   if (Implementation->dynMatches(N, Finder, Builder)) {
     return true;
   }
   // Delete all bindings when a matcher does not match.

clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp

EXPECT_TRUE(matches(
                           has(templateTypeParmDecl(hasName("TemplateType"))))),
       langCxx20OrLater()));
 
   EXPECT_TRUE(matches(
       Code,
       traverse(TK_IgnoreUnlessSpelledInSource,
                functionDecl(hasName("func14"), hasDescendant(floatLiteral()))),
       langCxx20OrLater()));
+
+  Code = R"cpp(
+void foo() {
+    int explicit_captured = 0;
+    int implicit_captured = 0;
+    auto l = [&, explicit_captured](int i) {
+        if (i || explicit_captured || implicit_captured) return;
+    };
+}
+)cpp";
+
+  EXPECT_TRUE(matches(Code, traverse(TK_AsIs, ifStmt())));
+  EXPECT_TRUE(
+      matches(Code, traverse(TK_IgnoreUnlessSpelledInSource, ifStmt())));
+
+  auto lambdaExplicitCapture = declRefExpr(
+      to(varDecl(hasName("explicit_captured"))), unless(hasAncestor(ifStmt())));
+  auto lambdaImplicitCapture = declRefExpr(
+      to(varDecl(hasName("implicit_captured"))), unless(hasAncestor(ifStmt())));
+
+  EXPECT_TRUE(matches(Code, traverse(TK_AsIs, lambdaExplicitCapture)));
+  EXPECT_TRUE(matches(
+      Code, traverse(TK_IgnoreUnlessSpelledInSource, lambdaExplicitCapture)));
+
+  EXPECT_TRUE(matches(Code, traverse(TK_AsIs, lambdaImplicitCapture)));
+  EXPECT_FALSE(matches(
+      Code, traverse(TK_IgnoreUnlessSpelledInSource, lambdaImplicitCapture)));
 }
 
 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(