[ASTMatchers] Do not try to memoize nodes we can't compare.

[sbenza]

Summary

Prevent hasAncestor from comparing nodes that are not supported.
hasDescendant was fixed some time ago to avoid this problem.
I'm applying the same fix to hasAncestor: if any object in the Builder map is
not comparable, skip the cache.

[alexfh]

Looks good. Thanks!

cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp

private:
   // as there is a single parent.
   bool memoizedMatchesAncestorOfRecursively(
       const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher,
       BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
     if (Node.get<TranslationUnitDecl>() ==
         ActiveASTContext->getTranslationUnitDecl())
       return false;
 
+    // For AST-nodes that don't have an identity, we can't memoize.
+    if (!Builder->isComparable())
+      return matchesAncestorOfRecursively(Node, Matcher, Builder, MatchMode);
+
     MatchKey Key;
     Key.MatcherID = Matcher.getID();
     Key.Node = Node;
     Key.BoundNodes = *Builder;
 
     // Note that we cannot use insert and reuse the iterator, as recursive
     // calls to match might invalidate the result cache iterators.
     MemoizationMap::iterator I = ResultCache.find(Key);
     if (I != ResultCache.end()) {
       *Builder = I->second.Nodes;
       return I->second.ResultOfMatch;
     }
 
     MemoizedMatchResult Result;
-    Result.ResultOfMatch = false;
     Result.Nodes = *Builder;
+    Result.ResultOfMatch =
+        matchesAncestorOfRecursively(Node, Matcher, &Result.Nodes, MatchMode);
 
+    MemoizedMatchResult &CachedResult = ResultCache[Key];
+    CachedResult = std::move(Result);
+
+    *Builder = CachedResult.Nodes;
+    return CachedResult.ResultOfMatch;
+  }
+
+  bool matchesAncestorOfRecursively(const ast_type_traits::DynTypedNode &Node,
+                                    const DynTypedMatcher &Matcher,
+                                    BoundNodesTreeBuilder *Builder,
+                                    AncestorMatchMode MatchMode) {
     const auto &Parents = ActiveASTContext->getParents(Node);
     assert(!Parents.empty() && "Found node that is not in the parent map.");
     if (Parents.size() == 1) {
       // Only one parent - do recursive memoization.
       const ast_type_traits::DynTypedNode Parent = Parents[0];
-      if (Matcher.matches(Parent, this, &Result.Nodes)) {
-        Result.ResultOfMatch = true;
-      } else if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
-        // Reset the results to not include the bound nodes from the failed
-        // match above.
-        Result.Nodes = *Builder;
-        Result.ResultOfMatch = memoizedMatchesAncestorOfRecursively(
-            Parent, Matcher, &Result.Nodes, MatchMode);
+      BoundNodesTreeBuilder BuilderCopy = *Builder;
+      if (Matcher.matches(Parent, this, &BuilderCopy)) {
+        *Builder = std::move(BuilderCopy);
+        return true;
+      }
+      if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
+        return memoizedMatchesAncestorOfRecursively(Parent, Matcher, Builder,
+                                                    MatchMode);
         // Once we get back from the recursive call, the result will be the
         // same as the parent's result.
       }
     } else {
       // Multiple parents - BFS over the rest of the nodes.
       llvm::DenseSet<const void *> Visited;
       std::deque<ast_type_traits::DynTypedNode> Queue(Parents.begin(),
                                                       Parents.end());
       while (!Queue.empty()) {
-        Result.Nodes = *Builder;
-        if (Matcher.matches(Queue.front(), this, &Result.Nodes)) {
-          Result.ResultOfMatch = true;
-          break;
+        BoundNodesTreeBuilder BuilderCopy = *Builder;
+        if (Matcher.matches(Queue.front(), this, &BuilderCopy)) {
+          *Builder = std::move(BuilderCopy);
+          return true;
         }
         if (MatchMode != ASTMatchFinder::AMM_ParentOnly) {
           for (const auto &Parent :
                ActiveASTContext->getParents(Queue.front())) {
             // Make sure we do not visit the same node twice.
             // Otherwise, we'll visit the common ancestors as often as there
             // are splits on the way down.
             if (Visited.insert(Parent.getMemoizationData()).second)
               Queue.push_back(Parent);
           }
         }
         Queue.pop_front();
       }
     }
-
-    MemoizedMatchResult &CachedResult = ResultCache[Key];
-    CachedResult = std::move(Result);
-
-    *Builder = CachedResult.Nodes;
-    return CachedResult.ResultOfMatch;
+    return false;
   }
 
   // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
   // the aggregated bound nodes for each match.
   class MatchVisitor : public BoundNodesTreeBuilder::Visitor {
   public:
     MatchVisitor(ASTContext* Context,
                  MatchFinder::MatchCallback* Callback)

cfe/trunk/unittests/ASTMatchers/ASTMatchersTest.cpp

EXPECT_TRUE(notMatches("void f() { int i; }",
                          decl(hasDescendant(VD), hasDescendant(RD))));
   EXPECT_TRUE(notMatches("void f() { int i; }",
                          decl(hasDescendant(RD), hasDescendant(VD))));
   // Not matching RD first should not make a cache hit for VD either.
   EXPECT_TRUE(matches("void f() { int i; }",
                       decl(anyOf(hasDescendant(RD), hasDescendant(VD)))));
 }
 
+TEST(DeclarationMatcher, HasAncestorMemoization) {
+  // This triggers an hasAncestor with a TemplateArgument in the bound nodes.
+  // That node can't be memoized so we have to check for it before trying to put
+  // it on the cache.
+  DeclarationMatcher CannotMemoize = classTemplateSpecializationDecl(
+      hasAnyTemplateArgument(templateArgument().bind("targ")),
+      forEach(fieldDecl(hasAncestor(forStmt()))));
+
+  EXPECT_TRUE(notMatches("template <typename T> struct S;"
+                         "template <> struct S<int>{ int i; int j; };",
+                         CannotMemoize));
+}
+
 TEST(DeclarationMatcher, HasAttr) {
   EXPECT_TRUE(matches("struct __attribute__((warn_unused)) X {};",
                       decl(hasAttr(clang::attr::WarnUnused))));
   EXPECT_FALSE(matches("struct X {};",
                        decl(hasAttr(clang::attr::WarnUnused))));
 }
 
 TEST(DeclarationMatcher, MatchCudaDecl) {