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.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177081 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 22 insertions, 2 deletions

diff --git a/unittests/ASTMatchers/ASTMatchersTest.cpp b/unittests/ASTMatchers/ASTMatchersTest.cpp
index 32f846d925..2e2a824f8f 100644
--- a/unittests/ASTMatchers/ASTMatchersTest.cpp
+++ b/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) {