[ASTMatcher] Correct memoization bug ignoring direction (descendants or ancestors)

[loic-joly-sonarsource]

Summary

In ASTMatcher, when we have has(...) and hasParent(...) called with the same internal matcher on the same node, the memoization process will mix-up the two calls because the direction of the traversal is not part of the memoization key.

This patch adds this information.

[njames93]

This needs rebasing against trunk

[klimek]

clang/lib/ASTMatchers/ASTMatchFinder.cpp

46–49

Nice find! Why don't we need more states though?

1. wouldn't hasParent() followed by a hasAncestor() also trigger the memoization? (if so, we'd need transitive / non-transitive)
2. can we trigger a directional match and a non-directional (non-traversal, for example, explicit) match in the same memoization scope?

[loic-joly-sonarsource]

Take into account transitive/non transitive request
Clarify unit tests

[loic-joly-sonarsource]

In D80025#2041247, @njames93 wrote:

This needs rebasing against trunk

I'm doing it

clang/lib/ASTMatchers/ASTMatchFinder.cpp

46–49

1. Yes, I'm going to add it
2. Sorry, I did not understand what you mean...

[klimek]

clang/lib/ASTMatchers/ASTMatchFinder.cpp

46–49

Re 2: nevermind, we don't memoize non-transitive matches (other than hasParent / hasChild), right?
In that case, I'm wondering whether the simpler solution is to just not memoize hasParent / hasChild - wouldn't that be more in line with the rest of the memoization?

[loic-joly-sonarsource]

clang/lib/ASTMatchers/ASTMatchFinder.cpp

46–49

If I correctly understand what you mean, you think that memoizing recursive searches (ancestors/descendants) might not be worth it, and that just memoizing direct searches (parent, child) would be enough.

I really don't know if it's true or not, and I believe that getting this kind of data requires a significant benchmarking effort (which code base, which matchers...). And there might also be other performance-related concerns (for instance, the value of MaxMemoizationEntries, the choice of std::map to store the cache...),

In other words, I think this would go far beyond what this PR is trying to achieve, which is only correcting a bug.

[klimek]

clang/lib/ASTMatchers/ASTMatchFinder.cpp

46–49

What I'm trying to say is:
Currently the only non-transitive matchers we memoize are hasChild and hasParent, which ... seems weird - my operating hypothesis is that back in the day I didn't realize that or I'd have changed it :)

Thus, it seems like a simpler patch is to not memoize if it's not a transitive match.

Sam also had a good idea, which is to change the ASTMatchFinder API to instead of the current:
matchesChildOf
matchesDescendantOf
matchesAncestorOf(..., MatchMode)

create different atoms:
matchesChildOf
matchesDescendantOfOrSelf
matchesParentOf
matchesAncestorOfOrSelf

then hasDescendant(m) would be implemented as hasChild(hasDescendantOrSelf(m)) and the direction would be part of the matcher already.
That as an aside, which I'd propose to not do in the current patch though :)

My proposal for the current patch is to not memoize if we're only matching a single child or parent.

[loic-joly-sonarsource]

Removing memoization for non recursive matches

[loic-joly-sonarsource]

clang/lib/ASTMatchers/ASTMatchFinder.cpp

46–49

I've applied the change you suggested

[klimek]

LG. Thanks!

[loic-joly-sonarsource]

Can someone with write access merge this please?
Thank you!

clang/lib/ASTMatchers/ASTMatchFinder.cpp

 // of performance vs. memory consumption by running matcher
 // that match on every statement over a very large codebase.
 //
 // FIXME: Do some performance optimization in general and
 // revisit this number; also, put up micro-benchmarks that we can
 // optimize this on.
 static const unsigned MaxMemoizationEntries = 10000;
 
+enum class MatchType {
+  Ancestors,
+  Descendants
+};
+
 // We use memoization to avoid running the same matcher on the same
 // AST node twice.  This struct is the key for looking up match
 // result.  It consists of an ID of the MatcherInterface (for
 // identifying the matcher), a pointer to the AST node and the
 // bound nodes before the matcher was executed.
 //
 // We currently only memoize on nodes whose pointers identify the
 // nodes (\c Stmt and \c Decl, but not \c QualType or \c TypeLoc).
 // For \c QualType and \c TypeLoc it is possible to implement
 // generation of keys for each type.
 // FIXME: Benchmark whether memoization of non-pointer typed nodes
 // provides enough benefit for the additional amount of code.
 struct MatchKey {
   DynTypedMatcher::MatcherIDType MatcherID;
   DynTypedNode Node;
   BoundNodesTreeBuilder BoundNodes;
   TraversalKind Traversal = TK_AsIs;
+  MatchType Type;
 
   bool operator<(const MatchKey &Other) const {
-    return std::tie(Traversal, MatcherID, Node, BoundNodes) <
-           std::tie(Other.Traversal, Other.MatcherID, Other.Node,
+    return std::tie(Traversal, Type, MatcherID, Node, BoundNodes) <
+           std::tie(Other.Traversal, Other.Type, Other.MatcherID, Other.Node,
                     Other.BoundNodes);
   }
 };
 
 // Used to store the result of a match and possibly bound nodes.
 struct MemoizedMatchResult {
   bool ResultOfMatch;
   BoundNodesTreeBuilder Nodes;
public:
   bool TraverseConstructorInitializer(CXXCtorInitializer *CtorInit);
 
   // Matches children or descendants of 'Node' with 'BaseMatcher'.
   bool memoizedMatchesRecursively(const DynTypedNode &Node, ASTContext &Ctx,
                                   const DynTypedMatcher &Matcher,
                                   BoundNodesTreeBuilder *Builder, int MaxDepth,
                                   TraversalKind Traversal, BindKind Bind) {
     // For AST-nodes that don't have an identity, we can't memoize.
-    if (!Node.getMemoizationData() || !Builder->isComparable())
+    // When doing a single-level match, we don't need to memoize
+    if (!Node.getMemoizationData() || !Builder->isComparable() || MaxDepth == 1)
       return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
                                 Bind);
 
     MatchKey Key;
     Key.MatcherID = Matcher.getID();
     Key.Node = Node;
     // Note that we key on the bindings *before* the match.
     Key.BoundNodes = *Builder;
     Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
-
+    Key.Type = MatchType::Descendants;
     MemoizationMap::iterator I = ResultCache.find(Key);
     if (I != ResultCache.end()) {
       *Builder = I->second.Nodes;
       return I->second.ResultOfMatch;
     }
 
     MemoizedMatchResult Result;
     Result.Nodes = *Builder;
private:
   // allow simple memoization on the ancestors. Thus, we only memoize as long
   // as there is a single parent.
   bool memoizedMatchesAncestorOfRecursively(const DynTypedNode &Node,
                                             ASTContext &Ctx,
                                             const DynTypedMatcher &Matcher,
                                             BoundNodesTreeBuilder *Builder,
                                             AncestorMatchMode MatchMode) {
     // For AST-nodes that don't have an identity, we can't memoize.
-    if (!Builder->isComparable())
+    // When doing a single-level match, we don't need to memoize
+    if (!Builder->isComparable() || MatchMode == AncestorMatchMode::AMM_ParentOnly)
       return matchesAncestorOfRecursively(Node, Ctx, Matcher, Builder,
                                           MatchMode);
 
     MatchKey Key;
     Key.MatcherID = Matcher.getID();
     Key.Node = Node;
     Key.BoundNodes = *Builder;
     Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
+    Key.Type = MatchType::Ancestors;
 
     // 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;
     }

clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp

TEST(HasParent, MatchesOnlyParent) {
   EXPECT_TRUE(notMatches(
     "void f() { for (;;) { int x = 42; } }",
     compoundStmt(hasParent(ifStmt()))));
   EXPECT_TRUE(notMatches(
     "void f() { if (true) for (;;) { int x = 42; } }",
     compoundStmt(hasParent(ifStmt()))));
 }
 
+TEST(MatcherMemoize, HasParentDiffersFromHas) {
+  // Test introduced after detecting a bug in memoization
+  constexpr auto code = "void f() { throw 1; }";
+  EXPECT_TRUE(notMatches(
+    code,
+    cxxThrowExpr(hasParent(expr()))));
+  EXPECT_TRUE(matches(
+    code,
+    cxxThrowExpr(has(expr()))));
+  EXPECT_TRUE(matches(
+    code,
+    cxxThrowExpr(anyOf(hasParent(expr()), has(expr())))));
+}
+
+TEST(MatcherMemoize, HasDiffersFromHasDescendant) {
+  // Test introduced after detecting a bug in memoization
+  constexpr auto code = "void f() { throw 1+1; }";
+  EXPECT_TRUE(notMatches(
+    code,
+    cxxThrowExpr(has(integerLiteral()))));
+  EXPECT_TRUE(matches(
+    code,
+    cxxThrowExpr(hasDescendant(integerLiteral()))));
+  EXPECT_TRUE(notMatches(code, 
+    cxxThrowExpr(allOf(
+      hasDescendant(integerLiteral()),
+      has(integerLiteral())))));
+}
 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(cxxRecordDecl(isTemplateInstantiation())),