Do not store duplicate parents when memoization data is available.

Summary:
Do not store duplicate parents when memoization data is available.
This does not solve the duplication problem, but ameliorates it.

Reviewers: klimek

Subscribers: klimek, cfe-commits

Differential Revision: http://reviews.llvm.org/D4124

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

2 files changed, 46 insertions, 14 deletions

diff --git a/lib/AST/ASTContext.cpp b/lib/AST/ASTContext.cpp
index ddde907522..4250850467 100644
--- a/lib/AST/ASTContext.cpp
+++ b/lib/AST/ASTContext.cpp
@@ -8159,10 +8159,12 @@ namespace {
       if (!Node)
         return true;
       if (ParentStack.size() > 0) {
-        // 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.
+        // FIXME: Currently we add the same parent multiple times, but only
+        // when no memoization data is available for the type.
+        // For example when we visit all subexpressions of template
+        // instantiations; this is suboptimal, but 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
@@ -8170,18 +8172,27 @@ namespace {
         auto &NodeOrVector = (*Parents)[Node];
         if (NodeOrVector.isNull()) {
           NodeOrVector = new ast_type_traits::DynTypedNode(ParentStack.back());
-        } else if (NodeOrVector
-                       .template is<ast_type_traits::DynTypedNode *>()) {
-          auto *Node =
-              NodeOrVector.template get<ast_type_traits::DynTypedNode *>();
-          auto *Vector = new ASTContext::ParentVector(1, *Node);
-          Vector->push_back(ParentStack.back());
-          NodeOrVector = Vector;
-          delete Node;
         } else {
+          if (NodeOrVector.template is<ast_type_traits::DynTypedNode *>()) {
+            auto *Node =
+                NodeOrVector.template get<ast_type_traits::DynTypedNode *>();
+            auto *Vector = new ASTContext::ParentVector(1, *Node);
+            NodeOrVector = Vector;
+            delete Node;
+          }
           assert(NodeOrVector.template is<ASTContext::ParentVector *>());
-          NodeOrVector.template get<ASTContext::ParentVector *>()->push_back(
-              ParentStack.back());
+
+          auto *Vector =
+              NodeOrVector.template get<ASTContext::ParentVector *>();
+          // Skip duplicates for types that have memoization data.
+          // We must check that the type has memoization data before calling
+          // std::find() because DynTypedNode::operator== can't compare all
+          // types.
+          bool Found = ParentStack.back().getMemoizationData() &&
+                       std::find(Vector->begin(), Vector->end(),
+                                 ParentStack.back()) != Vector->end();
+          if (!Found)
+            Vector->push_back(ParentStack.back());
         }
       }
       ParentStack.push_back(ast_type_traits::DynTypedNode::create(*Node));
diff --git a/unittests/ASTMatchers/ASTMatchersTest.cpp b/unittests/ASTMatchers/ASTMatchersTest.cpp
index 03acfe3060..d247fac29f 100644
--- a/unittests/ASTMatchers/ASTMatchersTest.cpp
+++ b/unittests/ASTMatchers/ASTMatchersTest.cpp
@@ -3623,6 +3623,27 @@ TEST(HasParent, MatchesAllParents) {
                  compoundStmt(hasParent(recordDecl()))));
 }
 
+TEST(HasParent, NoDuplicateParents) {
+  class HasDuplicateParents : public BoundNodesCallback {
+  public:
+    bool run(const BoundNodes *Nodes) override { return false; }
+    bool run(const BoundNodes *Nodes, ASTContext *Context) override {
+      const Stmt *Node = Nodes->getNodeAs<Stmt>("node");
+      std::set<const void *> Parents;
+      for (const auto &Parent : Context->getParents(*Node)) {
+        if (!Parents.insert(Parent.getMemoizationData()).second) {
+          return true;
+        }
+      }
+      return false;
+    }
+  };
+  EXPECT_FALSE(matchAndVerifyResultTrue(
+      "template <typename T> int Foo() { return 1 + 2; }\n"
+      "int x = Foo<int>() + Foo<unsigned>();",
+      stmt().bind("node"), new HasDuplicateParents()));
+}
+
 TEST(TypeMatching, MatchesTypes) {
   EXPECT_TRUE(matches("struct S {};", qualType().bind("loc")));
 }