[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)

[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 &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);
   }
 };
@@ -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)

[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)

[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 &Other) 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 &Other) 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* t

[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 &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);
   }
 };
@@ -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)

[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] D99181: [analyzer] Fix crash on spaceship operator (PR47511)

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

loic-joly-sonarsource added inline comments.



Comment at: clang/test/Analysis/PR47511.cpp:5
+
+#include "Inputs/std-compare.h"
+

For such a simple test, there is no need to use the full-fledged header, the 
following would suffice:
```
namespace std { 
struct strong_ordering {
  int n;
  constexpr operator int() const { return n; }
  static const strong_ordering equal, greater, less;
};
constexpr strong_ordering strong_ordering::equal = { 0 };
constexpr strong_ordering strong_ordering::greater = { 1 };
constexpr strong_ordering strong_ordering::less = { -1 };
} // namespace std
```


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D99181

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