Implements multiple parents in the parent map.

Previously we would match the last visited parent, which in the
case of template instantiations was the last instantiated template.

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

2 files changed, 84 insertions, 23 deletions

diff --git a/lib/ASTMatchers/ASTMatchFinder.cpp b/lib/ASTMatchers/ASTMatchFinder.cpp
index 7f89550573..0b1d1b6f25 100644
--- a/lib/ASTMatchers/ASTMatchFinder.cpp
+++ b/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -39,8 +39,11 @@ typedef MatchFinder::MatchCallback MatchCallback;
 /// FIXME: Currently only builds up the map using \c Stmt and \c Decl nodes.
 class ParentMapASTVisitor : public RecursiveASTVisitor<ParentMapASTVisitor> {
 public:
-  /// \brief Maps from a node to its parent.
-  typedef llvm::DenseMap<const void*, ast_type_traits::DynTypedNode> ParentMap;
+  /// \brief Contains parents of a node.
+  typedef llvm::SmallVector<ast_type_traits::DynTypedNode, 1> ParentVector;
+
+  /// \brief Maps from a node to its parents.
+  typedef llvm::DenseMap<const void *, ParentVector> ParentMap;
 
   /// \brief Builds and returns the translation unit's parent map.
   ///
@@ -67,7 +70,15 @@ private:
     if (Node == NULL)
       return true;
     if (ParentStack.size() > 0)
-      (*Parents)[Node] = ParentStack.back();
+      // FIXME: Currently we add the same parent multiple times, for example
+      // when we visit all subexpressions of template instantiations; this is
+      // suboptimal, bug benign: the only way to visit those is with
+      // hasAncestor / hasParent, and those do not create new matches.
+      // The plan is to enable DynTypedNode to be storable in a map or hash
+      // map. The main problem there is to implement hash functions /
+      // comparison operators for all types that DynTypedNode supports that
+      // do not have pointer identity.
+      (*Parents)[Node].push_back(ParentStack.back());
     ParentStack.push_back(ast_type_traits::DynTypedNode::create(*Node));
     bool Result = (this->*traverse)(Node);
     ParentStack.pop_back();
@@ -453,26 +464,7 @@ public:
       Parents.reset(ParentMapASTVisitor::buildMap(
         *ActiveASTContext->getTranslationUnitDecl()));
     }
-    ast_type_traits::DynTypedNode Ancestor = Node;
-    while (Ancestor.get<TranslationUnitDecl>() !=
-           ActiveASTContext->getTranslationUnitDecl()) {
-      assert(Ancestor.getMemoizationData() &&
-             "Invariant broken: only nodes that support memoization may be "
-             "used in the parent map.");
-      ParentMapASTVisitor::ParentMap::const_iterator I =
-        Parents->find(Ancestor.getMemoizationData());
-      if (I == Parents->end()) {
-        assert(false &&
-               "Found node that is not in the parent map.");
-        return false;
-      }
-      Ancestor = I->second;
-      if (Matcher.matches(Ancestor, this, Builder))
-        return true;
-      if (MatchMode == ASTMatchFinder::AMM_ParentOnly)
-        return false;
-    }
-    return false;
+    return matchesAncestorOfRecursively(Node, Matcher, Builder, MatchMode);
   }
 
   // Implements ASTMatchFinder::getASTContext.
@@ -485,6 +477,39 @@ public:
   bool shouldUseDataRecursionFor(clang::Stmt *S) const { return false; }
 
 private:
+  bool matchesAncestorOfRecursively(
+      const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher,
+      BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
+    if (Node.get<TranslationUnitDecl>() ==
+        ActiveASTContext->getTranslationUnitDecl())
+      return false;
+    assert(Node.getMemoizationData() &&
+           "Invariant broken: only nodes that support memoization may be "
+           "used in the parent map.");
+    ParentMapASTVisitor::ParentMap::const_iterator I =
+        Parents->find(Node.getMemoizationData());
+    if (I == Parents->end()) {
+      assert(false && "Found node that is not in the parent map.");
+      return false;
+    }
+    for (ParentMapASTVisitor::ParentVector::const_iterator AncestorI =
+             I->second.begin(), AncestorE = I->second.end();
+         AncestorI != AncestorE; ++AncestorI) {
+      if (Matcher.matches(*AncestorI, this, Builder))
+        return true;
+    }
+    if (MatchMode == ASTMatchFinder::AMM_ParentOnly)
+      return false;
+    for (ParentMapASTVisitor::ParentVector::const_iterator AncestorI =
+             I->second.begin(), AncestorE = I->second.end();
+         AncestorI != AncestorE; ++AncestorI) {
+      if (matchesAncestorOfRecursively(*AncestorI, Matcher, Builder, MatchMode))
+        return true;
+    }
+    return false;
+  }
+
+
   // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
   // the aggregated bound nodes for each match.
   class MatchVisitor : public BoundNodesTree::Visitor {
diff --git a/unittests/ASTMatchers/ASTMatchersTest.cpp b/unittests/ASTMatchers/ASTMatchersTest.cpp
index 32b1496252..8beff0f98a 100644
--- a/unittests/ASTMatchers/ASTMatchersTest.cpp
+++ b/unittests/ASTMatchers/ASTMatchersTest.cpp
@@ -3044,6 +3044,42 @@ TEST(HasParent, MatchesOnlyParent) {
       compoundStmt(hasParent(ifStmt()))));
 }
 
+TEST(HasAncestor, MatchesAllAncestors) {
+  EXPECT_TRUE(matches(
+      "template <typename T> struct C { static void f() { 42; } };"
+      "void t() { C<int>::f(); }",
+      integerLiteral(
+          equals(42),
+          allOf(hasAncestor(recordDecl(isTemplateInstantiation())),
+                hasAncestor(recordDecl(unless(isTemplateInstantiation())))))));
+}
+
+TEST(HasParent, MatchesAllParents) {
+  EXPECT_TRUE(matches(
+      "template <typename T> struct C { static void f() { 42; } };"
+      "void t() { C<int>::f(); }",
+      integerLiteral(
+          equals(42),
+          hasParent(compoundStmt(hasParent(functionDecl(
+              hasParent(recordDecl(isTemplateInstantiation())))))))));
+  EXPECT_TRUE(matches(
+      "template <typename T> struct C { static void f() { 42; } };"
+      "void t() { C<int>::f(); }",
+      integerLiteral(
+          equals(42),
+          hasParent(compoundStmt(hasParent(functionDecl(
+              hasParent(recordDecl(unless(isTemplateInstantiation()))))))))));
+  EXPECT_TRUE(matches(
+      "template <typename T> struct C { static void f() { 42; } };"
+      "void t() { C<int>::f(); }",
+      integerLiteral(equals(42),
+                     hasParent(compoundStmt(allOf(
+                         hasParent(functionDecl(
+                             hasParent(recordDecl(isTemplateInstantiation())))),
+                         hasParent(functionDecl(hasParent(recordDecl(
+                             unless(isTemplateInstantiation())))))))))));
+}
+
 TEST(TypeMatching, MatchesTypes) {
   EXPECT_TRUE(matches("struct S {};", qualType().bind("loc")));
 }