Do not store duplicate parents when memoization data is available.

[sbenza]

Summary

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

[sbenza]

Minor style change.

[klimek]

lg

lib/AST/ASTContext.cpp

8183

Please fix my "bug benign" typo :D

8209–8212

Any reason not to use std::find?

[sbenza]

Use std::find() instead of std::any_of()

[sbenza]

lib/AST/ASTContext.cpp

8183

Done.

8209–8212

I was afraid that operator== will break for non-memo types, but as long as one of the arguments has memo, then it gives a correct result. Changed.

[sbenza]

Closed by commit rL210902 (authored by @sbenza).

lib/AST/ASTContext.cpp

bool shouldUseDataRecursionFor(clang::Stmt *S) const {
       return false;
     }
 
     template <typename T>
     bool TraverseNode(T *Node, bool(VisitorBase:: *traverse) (T *)) {
       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
         // do not have pointer identity.
         auto &NodeOrVector = (*Parents)[Node];
         if (NodeOrVector.isNull()) {
           NodeOrVector = new ast_type_traits::DynTypedNode(ParentStack.back());
-        } else if (NodeOrVector
-                       .template is<ast_type_traits::DynTypedNode *>()) {
+        } 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 {
+          }
           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));
       bool Result = (this ->* traverse) (Node);
       ParentStack.pop_back();
       return Result;
     }
 

unittests/ASTMatchers/ASTMatchersTest.cpp

EXPECT_TRUE(matches(
                          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(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")));
 }
 
 TEST(TypeMatching, MatchesArrayTypes) {
   EXPECT_TRUE(matches("int a[] = {2,3};", arrayType()));
   EXPECT_TRUE(matches("int a[42];", arrayType()));
   EXPECT_TRUE(matches("void f(int b) { int a[b]; }", arrayType()));