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

[Sam McCall via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rGcba56e026c7b: [ASTMatcher] Correct memoization bug ignoring 
direction (descendants or… (authored by loic-joly-sonarsource, committed by 
sammccall).

Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80025/new/

https://reviews.llvm.org/D80025

Files:
  clang/lib/ASTMatchers/ASTMatchFinder.cpp
  clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp

Index: clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
===
--- clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
+++ clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
@@ -2864,6 +2864,34 @@
 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  struct C { static void f() { 42; } };"
Index: clang/lib/ASTMatchers/ASTMatchFinder.cpp
===
--- clang/lib/ASTMatchers/ASTMatchFinder.cpp
+++ clang/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -43,6 +43,11 @@
 // optimize this on.
 static const unsigned MaxMemoizationEntries = 1;
 
+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
@@ -60,10 +65,11 @@
   DynTypedNode Node;
   BoundNodesTreeBuilder BoundNodes;
   TraversalKind Traversal = TK_AsIs;
+  MatchType Type;
 
   bool operator<(const MatchKey ) 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);
   }
 };
@@ -446,7 +452,8 @@
   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);
 
@@ -456,7 +463,7 @@
 // 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;
@@ -693,7 +700,8 @@
 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);
 
@@ -702,6 +710,7 @@
 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.
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Loïc Joly via Phabricator via cfe-commits]

loic-joly-sonarsource added a comment.

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


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80025/new/

https://reviews.llvm.org/D80025



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Manuel Klimek via Phabricator via cfe-commits]

klimek accepted this revision.
klimek added a comment.
This revision is now accepted and ready to land.

LG. Thanks!


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80025/new/

https://reviews.llvm.org/D80025



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Loïc Joly via Phabricator via cfe-commits]

loic-joly-sonarsource updated this revision to Diff 270893.
loic-joly-sonarsource added a comment.

Removing memoization for non recursive matches


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80025/new/

https://reviews.llvm.org/D80025

Files:
  clang/lib/ASTMatchers/ASTMatchFinder.cpp
  clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp

Index: clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
===
--- clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
+++ clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
@@ -2864,6 +2864,34 @@
 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  struct C { static void f() { 42; } };"
Index: clang/lib/ASTMatchers/ASTMatchFinder.cpp
===
--- clang/lib/ASTMatchers/ASTMatchFinder.cpp
+++ clang/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -43,6 +43,11 @@
 // optimize this on.
 static const unsigned MaxMemoizationEntries = 1;
 
+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
@@ -60,10 +65,11 @@
   DynTypedNode Node;
   BoundNodesTreeBuilder BoundNodes;
   TraversalKind Traversal = TK_AsIs;
+  MatchType Type;
 
   bool operator<(const MatchKey ) 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);
   }
 };
@@ -446,7 +452,8 @@
   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);
 
@@ -456,7 +463,7 @@
 // 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;
@@ -693,7 +700,8 @@
 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);
 
@@ -702,6 +710,7 @@
 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.
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Loïc Joly via Phabricator via cfe-commits]

loic-joly-sonarsource marked an inline comment as done.
loic-joly-sonarsource added inline comments.



Comment at: clang/lib/ASTMatchers/ASTMatchFinder.cpp:46-49
+enum class MatchDirection {
+  Ancestors,
+  Descendants
+};

klimek wrote:
> loic-joly-sonarsource wrote:
> > klimek wrote:
> > > loic-joly-sonarsource wrote:
> > > > klimek wrote:
> > > > > 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?
> > > > 1. Yes, I'm going to add it
> > > > 2. Sorry, I did not understand what you mean...
> > > > 
> > > 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?
> > 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.
> 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.
> 
> 
I've applied the change you suggested


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80025/new/

https://reviews.llvm.org/D80025



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Manuel Klimek via Phabricator via cfe-commits]

klimek added inline comments.



Comment at: clang/lib/ASTMatchers/ASTMatchFinder.cpp:46-49
+enum class MatchDirection {
+  Ancestors,
+  Descendants
+};

loic-joly-sonarsource wrote:
> klimek wrote:
> > loic-joly-sonarsource wrote:
> > > klimek wrote:
> > > > 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?
> > > 1. Yes, I'm going to add it
> > > 2. Sorry, I did not understand what you mean...
> > > 
> > 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?
> 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.
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.




CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80025/new/

https://reviews.llvm.org/D80025



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Loïc Joly via Phabricator via cfe-commits]

loic-joly-sonarsource added inline comments.



Comment at: clang/lib/ASTMatchers/ASTMatchFinder.cpp:46-49
+enum class MatchDirection {
+  Ancestors,
+  Descendants
+};

klimek wrote:
> loic-joly-sonarsource wrote:
> > klimek wrote:
> > > 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?
> > 1. Yes, I'm going to add it
> > 2. Sorry, I did not understand what you mean...
> > 
> 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?
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.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80025/new/

https://reviews.llvm.org/D80025



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Manuel Klimek via Phabricator via cfe-commits]

klimek added inline comments.



Comment at: clang/lib/ASTMatchers/ASTMatchFinder.cpp:46-49
+enum class MatchDirection {
+  Ancestors,
+  Descendants
+};

loic-joly-sonarsource wrote:
> klimek wrote:
> > 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?
> 1. Yes, I'm going to add it
> 2. Sorry, I did not understand what you mean...
> 
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?


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80025/new/

https://reviews.llvm.org/D80025



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Loïc Joly via Phabricator via cfe-commits]

loic-joly-sonarsource added a comment.

In D80025#2041247 , @njames93 wrote:

> This needs rebasing against trunk


I'm doing it




Comment at: clang/lib/ASTMatchers/ASTMatchFinder.cpp:46-49
+enum class MatchDirection {
+  Ancestors,
+  Descendants
+};

klimek wrote:
> 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?
1. Yes, I'm going to add it
2. Sorry, I did not understand what you mean...



CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80025/new/

https://reviews.llvm.org/D80025



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Loïc Joly via Phabricator via cfe-commits]

loic-joly-sonarsource updated this revision to Diff 264709.
loic-joly-sonarsource added a comment.

Take into account transitive/non transitive request
Clarify unit tests


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80025/new/

https://reviews.llvm.org/D80025

Files:
  clang/lib/ASTMatchers/ASTMatchFinder.cpp
  clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp


Index: clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
===
--- clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
+++ clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
@@ -2689,6 +2689,34 @@
 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  struct C { static void f() { 42; } };"
Index: clang/lib/ASTMatchers/ASTMatchFinder.cpp
===
--- clang/lib/ASTMatchers/ASTMatchFinder.cpp
+++ clang/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -43,6 +43,13 @@
 // optimize this on.
 static const unsigned MaxMemoizationEntries = 1;
 
+enum class MatchType {
+  Ancestors,
+  Descendants,
+  Parent,
+  Child
+};
+
 // 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
@@ -60,10 +67,11 @@
   DynTypedNode Node;
   BoundNodesTreeBuilder BoundNodes;
   TraversalKind Traversal = TK_AsIs;
+  MatchType Type;
 
   bool operator<(const MatchKey ) 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);
   }
 };
@@ -456,7 +464,7 @@
 // Note that we key on the bindings *before* the match.
 Key.BoundNodes = *Builder;
 Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
-
+Key.Type = MaxDepth == 1 ? MatchType::Child : MatchType::Descendants;
 MemoizationMap::iterator I = ResultCache.find(Key);
 if (I != ResultCache.end()) {
   *Builder = I->second.Nodes;
@@ -702,6 +710,8 @@
 Key.Node = Node;
 Key.BoundNodes = *Builder;
 Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
+Key.Type = MatchMode == AncestorMatchMode::AMM_ParentOnly ? 
+  MatchType::Parent : MatchType::Ancestors;
 
 // Note that we cannot use insert and reuse the iterator, as recursive
 // calls to match might invalidate the result cache iterators.


Index: clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
===
--- clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
+++ clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
@@ -2689,6 +2689,34 @@
 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  struct C { static void f() { 42; } };"
Index: clang/lib/ASTMatchers/ASTMatchFinder.cpp

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

[Manuel Klimek via Phabricator via cfe-commits]

klimek added inline comments.



Comment at: clang/lib/ASTMatchers/ASTMatchFinder.cpp:46-49
+enum class MatchDirection {
+  Ancestors,
+  Descendants
+};

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?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80025/new/

https://reviews.llvm.org/D80025



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Nathan James via Phabricator via cfe-commits]

njames93 added a comment.

This needs rebasing against trunk


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D80025/new/

https://reviews.llvm.org/D80025



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Loïc Joly via Phabricator via cfe-commits]

loic-joly-sonarsource created this revision.
loic-joly-sonarsource added a reviewer: klimek.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.

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.


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D80025

Files:
  clang/lib/ASTMatchers/ASTMatchFinder.cpp
  clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp


Index: clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
===
--- clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
+++ clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
@@ -2591,6 +2591,14 @@
 compoundStmt(hasParent(ifStmt();
 }
 
+TEST(MatcherMemoize, HasParentDiffersFromHas) {
+  // Test introduced after detecting a bug in memoization
+EXPECT_TRUE(matches(
+  "void f() { throw 1; }",
+  expr(eachOf(cxxThrowExpr(hasParent(expr())),
+  cxxThrowExpr(has(expr()));
+}
+
 TEST(HasAncestor, MatchesAllAncestors) {
   EXPECT_TRUE(matches(
 "template  struct C { static void f() { 42; } };"
Index: clang/lib/ASTMatchers/ASTMatchFinder.cpp
===
--- clang/lib/ASTMatchers/ASTMatchFinder.cpp
+++ clang/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -43,6 +43,11 @@
 // optimize this on.
 static const unsigned MaxMemoizationEntries = 1;
 
+enum class MatchDirection {
+  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
@@ -60,11 +65,12 @@
   ast_type_traits::DynTypedNode Node;
   BoundNodesTreeBuilder BoundNodes;
   ast_type_traits::TraversalKind Traversal = ast_type_traits::TK_AsIs;
+  MatchDirection Direction;
 
   bool operator<(const MatchKey ) const {
-return std::tie(MatcherID, Node, BoundNodes, Traversal) <
+return std::tie(MatcherID, Node, BoundNodes, Traversal, Direction) <
std::tie(Other.MatcherID, Other.Node, Other.BoundNodes,
-Other.Traversal);
+Other.Traversal, Other.Direction);
   }
 };
 
@@ -457,6 +463,7 @@
 // Note that we key on the bindings *before* the match.
 Key.BoundNodes = *Builder;
 Key.Traversal = Ctx.getTraversalKind();
+Key.Direction = MatchDirection::Descendants;
 
 MemoizationMap::iterator I = ResultCache.find(Key);
 if (I != ResultCache.end()) {
@@ -706,6 +713,7 @@
 Key.Node = Node;
 Key.BoundNodes = *Builder;
 Key.Traversal = Ctx.getTraversalKind();
+Key.Direction = MatchDirection::Ancestors;
 
 // Note that we cannot use insert and reuse the iterator, as recursive
 // calls to match might invalidate the result cache iterators.


Index: clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
===
--- clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
+++ clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
@@ -2591,6 +2591,14 @@
 compoundStmt(hasParent(ifStmt();
 }
 
+TEST(MatcherMemoize, HasParentDiffersFromHas) {
+  // Test introduced after detecting a bug in memoization
+EXPECT_TRUE(matches(
+  "void f() { throw 1; }",
+  expr(eachOf(cxxThrowExpr(hasParent(expr())),
+  cxxThrowExpr(has(expr()));
+}
+
 TEST(HasAncestor, MatchesAllAncestors) {
   EXPECT_TRUE(matches(
 "template  struct C { static void f() { 42; } };"
Index: clang/lib/ASTMatchers/ASTMatchFinder.cpp
===
--- clang/lib/ASTMatchers/ASTMatchFinder.cpp
+++ clang/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -43,6 +43,11 @@
 // optimize this on.
 static const unsigned MaxMemoizationEntries = 1;
 
+enum class MatchDirection {
+  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
@@ -60,11 +65,12 @@
   ast_type_traits::DynTypedNode Node;
   BoundNodesTreeBuilder BoundNodes;
   ast_type_traits::TraversalKind Traversal = ast_type_traits::TK_AsIs;
+  MatchDirection Direction;
 
   bool operator<(const MatchKey ) const {
-return std::tie(MatcherID, Node, BoundNodes, Traversal) <
+return std::tie(MatcherID, Node, BoundNodes, Traversal, Direction) <
std::tie(Other.MatcherID, Other.Node, Other.BoundNodes,
-Other.Traversal);
+Other.Traversal, Other.Direction);
   }
 };
 
@@ -457,6 +463,7 @@
 // Note that we key on the bindings *before* the match.