Implements memoization for ancestor matching.

This yields a log(#ast_nodes) worst-case improvement with matchers like
stmt(unless(hasAncestor(...))).

Also made the order of visitation for ancestor matches BFS, as the most
common use cases (for example finding the closest enclosing function
definition) rely on that.

llvm-svn: 177081

1 files changed, 22 insertions, 2 deletions

diff --git a/clang/unittests/ASTMatchers/ASTMatchersTest.cpp b/clang/unittests/ASTMatchers/ASTMatchersTest.cpp
index 32f846d925f..2e2a824f8fe 100644
--- a/clang/unittests/ASTMatchers/ASTMatchersTest.cpp
+++ b/clang/unittests/ASTMatchers/ASTMatchersTest.cpp
@@ -632,8 +632,10 @@ public:
   // Create an object that checks that a node of type \c T was bound to \c Id.
   // Checks that there was exactly one match with the name \c ExpectedName.
   // Note that \c T must be a NamedDecl for this to work.
-  VerifyIdIsBoundTo(llvm::StringRef Id, llvm::StringRef ExpectedName)
-    : Id(Id), ExpectedCount(1), Count(0), ExpectedName(ExpectedName) {}
+  VerifyIdIsBoundTo(llvm::StringRef Id, llvm::StringRef ExpectedName,
+                    int ExpectedCount = 1)
+      : Id(Id), ExpectedCount(ExpectedCount), Count(0),
+        ExpectedName(ExpectedName) {}
 
   ~VerifyIdIsBoundTo() {
     if (ExpectedCount != -1)
@@ -3192,6 +3194,20 @@ TEST(HasAncestor, BindsCombinationsWithHasDescendant) {
       new VerifyIdIsBoundTo<CXXRecordDecl>("d", "E")));
 }
 
+TEST(HasAncestor, MatchesClosestAncestor) {
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "template <typename T> struct C {"
+      "  void f(int) {"
+      "    struct I { void g(T) { int x; } } i; i.g(42);"
+      "  }"
+      "};"
+      "template struct C<int>;",
+      varDecl(hasName("x"),
+              hasAncestor(functionDecl(hasParameter(
+                  0, varDecl(hasType(asString("int"))))).bind("f"))).bind("v"),
+      new VerifyIdIsBoundTo<FunctionDecl>("f", "g", 2)));
+}
+
 TEST(HasAncestor, MatchesInTemplateInstantiations) {
   EXPECT_TRUE(matches(
       "template <typename T> struct A { struct B { struct C { T t; }; }; }; "
@@ -3254,6 +3270,10 @@ TEST(HasParent, MatchesAllParents) {
                              hasParent(recordDecl(isTemplateInstantiation())))),
                          hasParent(functionDecl(hasParent(recordDecl(
                              unless(isTemplateInstantiation())))))))))));
+  EXPECT_TRUE(
+      notMatches("template <typename T> struct C { static void f() {} };"
+                 "void t() { C<int>::f(); }",
+                 compoundStmt(hasParent(recordDecl()))));
 }
 
 TEST(TypeMatching, MatchesTypes) {