[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Balázs Kéri via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rL370639: [AST] AST structural equivalence to work internally 
with pairs. (authored by balazske, committed by ).
Herald added a project: LLVM.
Herald added a subscriber: llvm-commits.

Changed prior to commit:
  https://reviews.llvm.org/D66538?vs=217105=218327#toc

Repository:
  rL LLVM

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

https://reviews.llvm.org/D66538

Files:
  cfe/trunk/include/clang/AST/ASTStructuralEquivalence.h
  cfe/trunk/lib/AST/ASTStructuralEquivalence.cpp
  cfe/trunk/unittests/AST/StructuralEquivalenceTest.cpp

Index: cfe/trunk/include/clang/AST/ASTStructuralEquivalence.h
===
--- cfe/trunk/include/clang/AST/ASTStructuralEquivalence.h
+++ cfe/trunk/include/clang/AST/ASTStructuralEquivalence.h
@@ -18,7 +18,7 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Optional.h"
-#include 
+#include 
 #include 
 
 namespace clang {
@@ -42,14 +42,13 @@
   /// AST contexts for which we are checking structural equivalence.
   ASTContext , 
 
-  /// The set of "tentative" equivalences between two canonical
-  /// declarations, mapping from a declaration in the first context to the
-  /// declaration in the second context that we believe to be equivalent.
-  llvm::DenseMap TentativeEquivalences;
-
-  /// Queue of declarations in the first context whose equivalence
-  /// with a declaration in the second context still needs to be verified.
-  std::deque DeclsToCheck;
+  // Queue of from-to Decl pairs that are to be checked to determine the final
+  // result of equivalence of a starting Decl pair.
+  std::queue> DeclsToCheck;
+
+  // Set of from-to Decl pairs that are already visited during the check
+  // (are in or were once in \c DeclsToCheck) of a starting Decl pair.
+  llvm::DenseSet> VisitedDecls;
 
   /// Declaration (from, to) pairs that are known not to be equivalent
   /// (which we have already complained about).
@@ -88,14 +87,14 @@
   /// Implementation functions (all static functions in
   /// ASTStructuralEquivalence.cpp) must never call this function because that
   /// will wreak havoc the internal state (\c DeclsToCheck and
-  /// \c TentativeEquivalences members) and can cause faulty equivalent results.
+  /// \c VisitedDecls members) and can cause faulty equivalent results.
   bool IsEquivalent(Decl *D1, Decl *D2);
 
   /// Determine whether the two types are structurally equivalent.
   /// Implementation functions (all static functions in
   /// ASTStructuralEquivalence.cpp) must never call this function because that
   /// will wreak havoc the internal state (\c DeclsToCheck and
-  /// \c TentativeEquivalences members) and can cause faulty equivalent results.
+  /// \c VisitedDecls members) and can cause faulty equivalent results.
   bool IsEquivalent(QualType T1, QualType T2);
 
   /// Find the index of the given anonymous struct/union within its
Index: cfe/trunk/lib/AST/ASTStructuralEquivalence.cpp
===
--- cfe/trunk/lib/AST/ASTStructuralEquivalence.cpp
+++ cfe/trunk/lib/AST/ASTStructuralEquivalence.cpp
@@ -1574,20 +1574,24 @@
  Decl *D1, Decl *D2) {
   // FIXME: Check for known structural equivalences via a callback of some sort.
 
+  D1 = D1->getCanonicalDecl();
+  D2 = D2->getCanonicalDecl();
+  std::pair P{D1, D2};
+
   // Check whether we already know that these two declarations are not
   // structurally equivalent.
-  if (Context.NonEquivalentDecls.count(
-  std::make_pair(D1->getCanonicalDecl(), D2->getCanonicalDecl(
+  if (Context.NonEquivalentDecls.count(P))
 return false;
 
-  // Determine whether we've already produced a tentative equivalence for D1.
-  Decl * = Context.TentativeEquivalences[D1->getCanonicalDecl()];
-  if (EquivToD1)
-return EquivToD1 == D2->getCanonicalDecl();
-
-  // Produce a tentative equivalence D1 <-> D2, which will be checked later.
-  EquivToD1 = D2->getCanonicalDecl();
-  Context.DeclsToCheck.push_back(D1->getCanonicalDecl());
+  // Check if a check for these declarations is already pending.
+  // If yes D1 and D2 will be checked later (from DeclsToCheck),
+  // or these are already checked (and equivalent).
+  bool Inserted = Context.VisitedDecls.insert(P).second;
+  if (!Inserted)
+return true;
+
+  Context.DeclsToCheck.push(P);
+
   return true;
 }
 
@@ -1703,11 +1707,13 @@
   // Ensure that the implementation functions (all static functions in this TU)
   // never call the public ASTStructuralEquivalence::IsEquivalent() functions,
   // because that will wreak havoc the internal state (DeclsToCheck and
-  // TentativeEquivalences members) and can cause faulty behaviour. For
-  // instance, some leaf declarations can be stated and cached as inequivalent
-  // as a side effect of one inequivalent element in the 

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Aleksei Sidorin via Phabricator via cfe-commits]

a_sidorin accepted this revision.
a_sidorin added a comment.

Looks good, thank you for addressing the comments!


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Gabor Marton via Phabricator via cfe-commits]

martong added a comment.

@a_sidorin Ping


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Gabor Marton via Phabricator via cfe-commits]

martong added a comment.

In D66538#1642999 , @balazske wrote:

> In D66538#1642883 , @martong wrote:
>
> > There is a third test which could be useful to test whether there is no 
> > faulty cache entries there:
> >
> >   +TEST_F(StructuralEquivalenceCacheTest, DISABLED_NonEq) {
> >   ...
> >   +}
> >
>
>
> This is somewhat the same check that is done in the current tests when the 
> `NonEquivalentDecls` is checked to not contain any pairs of equivalent Decls. 
> (Specially this line:
>
>   EXPECT_FALSE(isInNonEqCache(
> findDeclPair(TU, functionDecl(hasName("x");
>
>
> )


Ok, that looks good.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Balázs Kéri via Phabricator via cfe-commits]

balazske updated this revision to Diff 217105.
balazske added a comment.

- Small update to newer C++ syntax, use std::pair in test.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538

Files:
  clang/include/clang/AST/ASTStructuralEquivalence.h
  clang/lib/AST/ASTStructuralEquivalence.cpp
  clang/unittests/AST/StructuralEquivalenceTest.cpp

Index: clang/unittests/AST/StructuralEquivalenceTest.cpp
===
--- clang/unittests/AST/StructuralEquivalenceTest.cpp
+++ clang/unittests/AST/StructuralEquivalenceTest.cpp
@@ -1273,6 +1273,128 @@
   classTemplateSpecializationDecl(hasName("Primary")));
   EXPECT_FALSE(testStructuralMatch(t));
 }
+struct StructuralEquivalenceCacheTest : public StructuralEquivalenceTest {
+  llvm::DenseSet> NonEquivalentDecls;
+
+  template 
+  std::pair
+  findDeclPair(std::tuple TU,
+   MatcherType M) {
+NodeType *D0 = FirstDeclMatcher().match(get<0>(TU), M);
+NodeType *D1 = FirstDeclMatcher().match(get<1>(TU), M);
+return {D0, D1};
+  }
+
+  template 
+  bool isInNonEqCache(std::pair D) {
+return NonEquivalentDecls.count(D) > 0;
+  }
+};
+
+TEST_F(StructuralEquivalenceCacheTest, SimpleNonEq) {
+  auto TU = makeTuDecls(
+  R"(
+  class A {};
+  class B {};
+  void x(A, A);
+  )",
+  R"(
+  class A {};
+  class B {};
+  void x(A, B);
+  )",
+  Lang_CXX);
+
+  StructuralEquivalenceContext Ctx(
+  get<0>(TU)->getASTContext(), get<1>(TU)->getASTContext(),
+  NonEquivalentDecls, StructuralEquivalenceKind::Default, false, false);
+
+  auto X = findDeclPair(TU, functionDecl(hasName("x")));
+  EXPECT_FALSE(Ctx.IsEquivalent(X.first, X.second));
+
+  EXPECT_FALSE(isInNonEqCache(findDeclPair(
+  TU, cxxRecordDecl(hasName("A"), unless(isImplicit());
+  EXPECT_FALSE(isInNonEqCache(findDeclPair(
+  TU, cxxRecordDecl(hasName("B"), unless(isImplicit());
+}
+
+TEST_F(StructuralEquivalenceCacheTest, SpecialNonEq) {
+  auto TU = makeTuDecls(
+  R"(
+  class A {};
+  class B { int i; };
+  void x(A *);
+  void y(A *);
+  class C {
+friend void x(A *);
+friend void y(A *);
+  };
+  )",
+  R"(
+  class A {};
+  class B { int i; };
+  void x(A *);
+  void y(B *);
+  class C {
+friend void x(A *);
+friend void y(B *);
+  };
+  )",
+  Lang_CXX);
+
+  StructuralEquivalenceContext Ctx(
+  get<0>(TU)->getASTContext(), get<1>(TU)->getASTContext(),
+  NonEquivalentDecls, StructuralEquivalenceKind::Default, false, false);
+
+  auto C = findDeclPair(
+  TU, cxxRecordDecl(hasName("C"), unless(isImplicit(;
+  EXPECT_FALSE(Ctx.IsEquivalent(C.first, C.second));
+
+  EXPECT_FALSE(isInNonEqCache(C));
+  EXPECT_FALSE(isInNonEqCache(findDeclPair(
+  TU, cxxRecordDecl(hasName("A"), unless(isImplicit());
+  EXPECT_FALSE(isInNonEqCache(findDeclPair(
+  TU, cxxRecordDecl(hasName("B"), unless(isImplicit());
+  EXPECT_FALSE(isInNonEqCache(
+  findDeclPair(TU, functionDecl(hasName("x");
+  EXPECT_FALSE(isInNonEqCache(
+  findDeclPair(TU, functionDecl(hasName("y");
+}
+
+TEST_F(StructuralEquivalenceCacheTest, Cycle) {
+  auto TU = makeTuDecls(
+  R"(
+  class C;
+  class A { C *c; };
+  void x(A *);
+  class C {
+friend void x(A *);
+  };
+  )",
+  R"(
+  class C;
+  class A { C *c; };
+  void x(A *);
+  class C {
+friend void x(A *);
+  };
+  )",
+  Lang_CXX);
+
+  StructuralEquivalenceContext Ctx(
+  get<0>(TU)->getASTContext(), get<1>(TU)->getASTContext(),
+  NonEquivalentDecls, StructuralEquivalenceKind::Default, false, false);
+
+  auto C = findDeclPair(
+  TU, cxxRecordDecl(hasName("C"), unless(isImplicit(;
+  EXPECT_TRUE(Ctx.IsEquivalent(C.first, C.second));
+
+  EXPECT_FALSE(isInNonEqCache(C));
+  EXPECT_FALSE(isInNonEqCache(findDeclPair(
+  TU, cxxRecordDecl(hasName("A"), unless(isImplicit());
+  EXPECT_FALSE(isInNonEqCache(
+  findDeclPair(TU, functionDecl(hasName("x");
+}
 
 } // end namespace ast_matchers
 } // end namespace clang
Index: clang/lib/AST/ASTStructuralEquivalence.cpp
===
--- clang/lib/AST/ASTStructuralEquivalence.cpp
+++ clang/lib/AST/ASTStructuralEquivalence.cpp
@@ -1574,20 +1574,24 @@
  Decl *D1, Decl *D2) {
   // FIXME: Check for known structural equivalences via a callback of some sort.
 
+  D1 = D1->getCanonicalDecl();
+  D2 = D2->getCanonicalDecl();
+  std::pair P{D1, D2};
+
   // Check whether we already know that these two declarations are not
   // structurally equivalent.
-  if (Context.NonEquivalentDecls.count(
-  std::make_pair(D1->getCanonicalDecl(), D2->getCanonicalDecl(
+  if 

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Balázs Kéri via Phabricator via cfe-commits]

balazske marked 2 inline comments as done.
balazske added a comment.

I remember that we had "problems" with nonsense ODR warnings where both 
declarations are the same. Probably the reason for it was this cache problem. 
Still the `NonEquivalentDecls` as cache is useful to filter out the 
non-equivalences that were already encountered to not produce repeated warnings 
for them.




Comment at: clang/unittests/AST/StructuralEquivalenceTest.cpp:1357
+
+  EXPECT_FALSE(isInNonEqCache(C));
+  EXPECT_FALSE(isInNonEqCache(findDeclPair(

a_sidorin wrote:
> The declarations of C are not equivalent, but they are not placed into the 
> non-equivalence cache. This looks strange to me, could you please explain 
> this behavior?
We can not know which declarations go into the `NonEquivalentDecls` (at least I 
do not expect it from this "interface"). It is only meaningful to test that 
there are no wrong (equivalent) values in it. I think users of this function 
should not rely on what exactly is put into the `NonEquivalentDecls`  because 
it is "implementation dependent". Currently the first encountered 
non-equivalence (during the internal checks) is put into it only, that is here 
the `A` and `B`. It can be a future work to put every encountered 
non-equivalent declaration into the cache but even that code will find these 
only until the first non-equivalence is encountered.



Comment at: clang/unittests/AST/StructuralEquivalenceTest.cpp:1399
+  TU, cxxRecordDecl(hasName("A"), unless(isImplicit());
+  EXPECT_FALSE(isInNonEqCache(
+  findDeclPair(TU, functionDecl(hasName("x");

a_sidorin wrote:
> We don't have any tests where isInNonEqCache() can return true. Is it 
> expected?
Yes, the specification for `IsEquivalent` should say that it returns if the 
declaratiopns are equivalent and puts something into the `NonEquivalentDecls` 
that is not equivalent. (This "something" is the first encountered 
non-equivalence and for this the warning message may be produced.)


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Aleksei Sidorin via Phabricator via cfe-commits]

a_sidorin added a comment.

Hello Balasz,
I have some comments inline.




Comment at: clang/lib/AST/ASTStructuralEquivalence.cpp:1579
+  D2 = D2->getCanonicalDecl();
+  std::pair P = std::make_pair(D1, D2);
+

`std::pair P{D1, D2}`?



Comment at: clang/lib/AST/ASTStructuralEquivalence.cpp:1888
 
-Decl *D2 = TentativeEquivalences[D1];
-assert(D2 && "Unrecorded tentative equivalence?");
+Decl *D1 = P.first;
+Decl *D2 = P.second;

I would prefer std::tie instead: `std::tie(D1, D2) = P;`. But it is a matter of 
taste.



Comment at: clang/unittests/AST/StructuralEquivalenceTest.cpp:1290
+  bool isInNonEqCache(std::tuple D) {
+return NonEquivalentDecls.find(std::make_pair(get<0>(D), get<1>(D))) !=
+   NonEquivalentDecls.end();

Can we use std::pair instead of std::tuple in this class? The size of tuple is 
known to be 2 and it will help to avoid such conversions.



Comment at: clang/unittests/AST/StructuralEquivalenceTest.cpp:1291
+return NonEquivalentDecls.find(std::make_pair(get<0>(D), get<1>(D))) !=
+   NonEquivalentDecls.end();
+  }

`return NonEquivalentDecls.count({get<0>(D), get<1>(D)});`?



Comment at: clang/unittests/AST/StructuralEquivalenceTest.cpp:1314
+  bool Eq = Ctx.IsEquivalent(get<0>(X), get<1>(X));
+  EXPECT_FALSE(Eq);
+

It seems to me that the assertion will become a bit easier to read without an 
intermediate variable. What do you think?



Comment at: clang/unittests/AST/StructuralEquivalenceTest.cpp:1357
+
+  EXPECT_FALSE(isInNonEqCache(C));
+  EXPECT_FALSE(isInNonEqCache(findDeclPair(

The declarations of C are not equivalent, but they are not placed into the 
non-equivalence cache. This looks strange to me, could you please explain this 
behavior?



Comment at: clang/unittests/AST/StructuralEquivalenceTest.cpp:1399
+  TU, cxxRecordDecl(hasName("A"), unless(isImplicit());
+  EXPECT_FALSE(isInNonEqCache(
+  findDeclPair(TU, functionDecl(hasName("x");

We don't have any tests where isInNonEqCache() can return true. Is it expected?


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Balázs Kéri via Phabricator via cfe-commits]

balazske added a comment.

In D66538#1642883 , @martong wrote:

> There is a third test which could be useful to test whether there is no 
> faulty cache entries there:
>
>   +TEST_F(StructuralEquivalenceCacheTest, DISABLED_NonEq) {
>   ...
>   +}
>


This is somewhat the same check that is done in the current tests when the 
`NonEquivalentDecls` is checked to not contain any pairs of equivalent Decls. 
(Specially this line:

  EXPECT_FALSE(isInNonEqCache(
findDeclPair(TU, functionDecl(hasName("x");

)


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Balázs Kéri via Phabricator via cfe-commits]

balazske updated this revision to Diff 216851.
balazske added a comment.

- Updated tests.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538

Files:
  clang/include/clang/AST/ASTStructuralEquivalence.h
  clang/lib/AST/ASTStructuralEquivalence.cpp
  clang/unittests/AST/StructuralEquivalenceTest.cpp

Index: clang/unittests/AST/StructuralEquivalenceTest.cpp
===
--- clang/unittests/AST/StructuralEquivalenceTest.cpp
+++ clang/unittests/AST/StructuralEquivalenceTest.cpp
@@ -1273,6 +1273,132 @@
   classTemplateSpecializationDecl(hasName("Primary")));
   EXPECT_FALSE(testStructuralMatch(t));
 }
+struct StructuralEquivalenceCacheTest : public StructuralEquivalenceTest {
+  llvm::DenseSet> NonEquivalentDecls;
+
+  template 
+  std::tuple
+  findDeclPair(std::tuple TU,
+   MatcherType M) {
+NodeType *D0 = FirstDeclMatcher().match(get<0>(TU), M);
+NodeType *D1 = FirstDeclMatcher().match(get<1>(TU), M);
+return std::make_tuple(D0, D1);
+  }
+
+  template 
+  bool isInNonEqCache(std::tuple D) {
+return NonEquivalentDecls.find(std::make_pair(get<0>(D), get<1>(D))) !=
+   NonEquivalentDecls.end();
+  }
+};
+
+TEST_F(StructuralEquivalenceCacheTest, SimpleNonEq) {
+  auto TU = makeTuDecls(
+  R"(
+  class A {};
+  class B {};
+  void x(A, A);
+  )",
+  R"(
+  class A {};
+  class B {};
+  void x(A, B);
+  )",
+  Lang_CXX);
+
+  StructuralEquivalenceContext Ctx(
+  get<0>(TU)->getASTContext(), get<1>(TU)->getASTContext(),
+  NonEquivalentDecls, StructuralEquivalenceKind::Default, false, false);
+  auto X = findDeclPair(TU, functionDecl(hasName("x")));
+  bool Eq = Ctx.IsEquivalent(get<0>(X), get<1>(X));
+  EXPECT_FALSE(Eq);
+
+  EXPECT_FALSE(isInNonEqCache(findDeclPair(
+  TU, cxxRecordDecl(hasName("A"), unless(isImplicit());
+  EXPECT_FALSE(isInNonEqCache(findDeclPair(
+  TU, cxxRecordDecl(hasName("B"), unless(isImplicit());
+}
+
+TEST_F(StructuralEquivalenceCacheTest, SpecialNonEq) {
+  auto TU = makeTuDecls(
+  R"(
+  class A {};
+  class B { int i; };
+  void x(A *);
+  void y(A *);
+  class C {
+friend void x(A *);
+friend void y(A *);
+  };
+  )",
+  R"(
+  class A {};
+  class B { int i; };
+  void x(A *);
+  void y(B *);
+  class C {
+friend void x(A *);
+friend void y(B *);
+  };
+  )",
+  Lang_CXX);
+
+  TranslationUnitDecl *TU0 = get<0>(TU);
+  TranslationUnitDecl *TU1 = get<1>(TU);
+
+  StructuralEquivalenceContext Ctx(
+  TU0->getASTContext(), TU1->getASTContext(), NonEquivalentDecls,
+  StructuralEquivalenceKind::Default, false, false);
+  auto C = findDeclPair(
+  TU, cxxRecordDecl(hasName("C"), unless(isImplicit(;
+  bool Eq = Ctx.IsEquivalent(get<0>(C), get<1>(C));
+  EXPECT_FALSE(Eq);
+
+  EXPECT_FALSE(isInNonEqCache(C));
+  EXPECT_FALSE(isInNonEqCache(findDeclPair(
+  TU, cxxRecordDecl(hasName("A"), unless(isImplicit());
+  EXPECT_FALSE(isInNonEqCache(findDeclPair(
+  TU, cxxRecordDecl(hasName("B"), unless(isImplicit());
+  EXPECT_FALSE(isInNonEqCache(
+  findDeclPair(TU, functionDecl(hasName("x");
+  EXPECT_FALSE(isInNonEqCache(
+  findDeclPair(TU, functionDecl(hasName("y");
+}
+
+TEST_F(StructuralEquivalenceCacheTest, Cycle) {
+  auto TU = makeTuDecls(
+  R"(
+  class C;
+  class A { C *c; };
+  void x(A *);
+  class C {
+friend void x(A *);
+  };
+  )",
+  R"(
+  class C;
+  class A { C *c; };
+  void x(A *);
+  class C {
+friend void x(A *);
+  };
+  )",
+  Lang_CXX);
+
+  StructuralEquivalenceContext Ctx(
+  get<0>(TU)->getASTContext(), get<1>(TU)->getASTContext(),
+  NonEquivalentDecls, StructuralEquivalenceKind::Default, false, false);
+  auto C = findDeclPair(
+  TU, cxxRecordDecl(hasName("C"), unless(isImplicit(;
+  bool Eq = Ctx.IsEquivalent(get<0>(C), get<1>(C));
+  EXPECT_TRUE(Eq);
+
+  EXPECT_FALSE(isInNonEqCache(C));
+  EXPECT_FALSE(isInNonEqCache(findDeclPair(
+  TU, cxxRecordDecl(hasName("A"), unless(isImplicit());
+  EXPECT_FALSE(isInNonEqCache(
+  findDeclPair(TU, functionDecl(hasName("x");
+}
 
 } // end namespace ast_matchers
 } // end namespace clang
Index: clang/lib/AST/ASTStructuralEquivalence.cpp
===
--- clang/lib/AST/ASTStructuralEquivalence.cpp
+++ clang/lib/AST/ASTStructuralEquivalence.cpp
@@ -1574,20 +1574,24 @@
  Decl *D1, Decl *D2) {
   // FIXME: Check for known structural equivalences via a callback of some sort.
 
+  D1 = D1->getCanonicalDecl();
+  D2 = D2->getCanonicalDecl();
+  std::pair P = std::make_pair(D1, D2);
+
   // Check whether we already know that these two 

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Gabor Marton via Phabricator via cfe-commits]

martong added a comment.

There is a third test which could be useful to test whether there is no faulty 
cache entries there:

  +TEST_F(StructuralEquivalenceCacheTest, DISABLED_NonEq) {
  +  auto Decls =
  +  makeTuDecls(
  +  R"(
  +class A {};
  +class B {
  +  int i;
  +};
  +void x(A *);
  +void y(A *);
  +class C {
  +  friend void x(A *);
  +  friend void y(A *);
  +};
  +  )",
  +  R"(
  +class A {};
  +class B {
  +  int i;
  +};
  +void x(A *);
  +void y(B *);
  +class C {
  +  friend void x(A *);
  +  friend void y(B *);
  +};
  +  )", Lang_CXX);
  +
  +  TranslationUnitDecl *TU1 = get<0>(Decls);
  +  TranslationUnitDecl *TU2 = get<1>(Decls);
  +  auto *C1 = LastDeclMatcher().match(
  +  TU1, cxxRecordDecl(hasName("C"), unless(isImplicit(;
  +  auto *C2 = LastDeclMatcher().match(
  +  TU2, cxxRecordDecl(hasName("C"), unless(isImplicit(;
  +  auto *x1 =
  +  FirstDeclMatcher().match(TU1, 
functionDecl(hasName("x")));
  +  auto *x2 =
  +  FirstDeclMatcher().match(TU2, 
functionDecl(hasName("x")));
  +
  +  llvm::DenseSet> NonEquivalentDecls;
  +  {
  +StructuralEquivalenceContext Ctx(
  +C1->getASTContext(), C2->getASTContext(), NonEquivalentDecls,
  +StructuralEquivalenceKind::Default, false, false);
  +EXPECT_FALSE(Ctx.IsEquivalent(C1, C2));
  +  }
  +
  +  // Reuse the cache.
  +  {
  +StructuralEquivalenceContext Ctx(
  +C1->getASTContext(), C2->getASTContext(), NonEquivalentDecls,
  +StructuralEquivalenceKind::Default, false, false);
  +EXPECT_TRUE(Ctx.IsEquivalent(x1, x2));
  +  }
  +}


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Gabor Marton via Phabricator via cfe-commits]

martong added a comment.

Ok.

I like this patch because it eliminates the need for checking the redeclaration 
chains.

Seems like it handles cycles and the simple `f(A,B)` vs `f(A,A)` cases properly 
too. (Not talking about caching now, probably we must remove the 
`NonEquivalentDecls` cache.)
I've added two new test cases, could you please add them to the patch (maybe 
with modifications if you find something)?

  TEST_F(StructuralEquivalenceCacheTest, Cycle) {
auto Decls =
makeTuDecls(
R"(
  class C;
  class A { C *c; };
  class B {
int i;
  };
  void x(A *);
  void y(A *);
  class C {
friend void x(A *);
friend void y(A *);
  };
)",
R"(
  class C;
  class A { C *c; };
  class B {
int i;
  };
  void x(A *);
  void y(A *);
  class C {
friend void x(A *);
friend void y(A *);
  };
)", Lang_CXX);
  
TranslationUnitDecl *TU1 = get<0>(Decls);
TranslationUnitDecl *TU2 = get<1>(Decls);
auto *C1 = LastDeclMatcher().match(
TU1, cxxRecordDecl(hasName("C"), unless(isImplicit(;
auto *C2 = LastDeclMatcher().match(
TU2, cxxRecordDecl(hasName("C"), unless(isImplicit(;
  
llvm::DenseSet> NonEquivalentDecls;
StructuralEquivalenceContext Ctx(
C1->getASTContext(), C2->getASTContext(), NonEquivalentDecls,
StructuralEquivalenceKind::Default, false, false);
bool Eq = Ctx.IsEquivalent(C1, C2);
  
EXPECT_TRUE(Eq);
  }
  
  TEST_F(StructuralEquivalenceCacheTest, SimpleNonEq) {
auto Decls =
makeTuDecls(
R"(
  class A {};
  class B {};
  void x(A, A);
)",
R"(
  class A {};
  class B {};
  void x(A, B);
)", Lang_CXX);
  
TranslationUnitDecl *TU1 = get<0>(Decls);
TranslationUnitDecl *TU2 = get<1>(Decls);
auto *x1 =
FirstDeclMatcher().match(TU1, functionDecl(hasName("x")));
auto *x2 =
FirstDeclMatcher().match(TU2, functionDecl(hasName("x")));
  
llvm::DenseSet> NonEquivalentDecls;
StructuralEquivalenceContext Ctx(
x1->getASTContext(), x2->getASTContext(), NonEquivalentDecls,
StructuralEquivalenceKind::Default, false, false);
bool Eq = Ctx.IsEquivalent(x1, x2);
  
EXPECT_FALSE(Eq);
  }


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Balázs Kéri via Phabricator via cfe-commits]

balazske added a comment.

The structural equivalency check works (with this patch) the following way: To 
check a `(A1,A2)` pair we collect further `(X1,X2)` pairs that should be 
checked and put these in `DeclsToCheck` (if not already there). The check 
succeeds if every pair is equivalent. The pairs `(A1,X2)` and `(A1,Y2)` are 
checked independently. A `true` return value from any of the 
`IsStructurallyEquivalent` functions means that we did not found 
non-equivalence in the internal node data but the pairs in `DeclsToCheck` 
should be checked too. Return value of `false` means a non-equivalence in the 
internal data only is found with the `(X1,X2)` pair that is currently checked, 
therefore we found non-equivalence for the original pair and for `(X1,X2)` too. 
Again, with the new code the test `CheckCommonEquivalence(D1, D2) && 
CheckKindSpecificEquivalence(D1, D2)` fails only if we found difference in the 
internal node data and we can be sure that `D1` and `D2` are non-equivalent. 
The old code does not have this property.

With the old code (that uses `TentativeEquivalences`) return value `false` for 
`IsStructurallyEquivalent` for `(X1,X2)` pair to check can mean that we found a 
`(X1,Y2)` to check and `X2!=Y2` (decl chain different). But we can not say that 
`(X1,X2)` are non-equivalent because it may be that `(X1,Y2)` are 
non-equivalent and `(X1,X2)` are equivalent. (But it is sure that the original 
pair `(A1,A2)` is non-equivalent.)


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Gabor Marton via Phabricator via cfe-commits]

martong added a comment.

The link for the diff went off, sorry about that.
Here is the new link which is going to work:
https://github.com/martong/clang/compare/NonEqDecls_cache_in_an_upper_level_0...martong:NonEqDecls_cache_in_an_upper_level?expand=1


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Balázs Kéri via Phabricator via cfe-commits]

balazske added a comment.

In D66538#1641310 , @martong wrote:

> > It looks like that the original code is correct in the decision of 
> > structural equivalence of the original pair. If we have an (A,B) and (A,C) 
> > to compare, B and C are in different decl chain, then (A,B) or (A,C) will 
> > be non-equivalent (unless B and C are equivalent, but what to do in this 
> > case?). The problem was that the code assumed that in this case always A 
> > and B (or A and C) are non-equivalent. If NonEquivalentDecls is not filled 
> > in this case (or not used at all) the problem does not exist.
>
> I think we must not update the NonEquivalentDecls cache at that level, 
> because as we've seen (during the discussion of 
> https://reviews.llvm.org/D62131) it may store the wrong pairs.
>  However, it is still okay to cache the inequivalent decls in one level 
> upper, right after the `Finish` returns.
>  See this diff 
> https://github.com/martong/clang/compare/NonEqDecls_cache_in_an_upper_level~...martong:NonEqDecls_cache_in_an_upper_level?expand=1
>  Right now I started a build on our CI to see if it causes any slowdown.


This is correct, `NonEquivalentDecls` can be filled after `Finish` (in 
`IsEquivalent`?) (still we can have similar cache for equivalence too, maybe 
this is not of so much use). With the new code there is the possibility to get 
more information about non-equivalence, the `NonEquivalentDecls` can be filled 
in `Finish` too like it is done now, and with not much effort (I think) we can 
add some dependency relation (a tree structure) to decide which (already 
visited) Decls become non-equivalent if one non-equivalence is found. If there 
is a `void f(A *, B *)` to check the `f` can be a "parent" of `A` and `B`, if 
`A` or `B` is found to be non-equivalent we can set this for `f` too.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Gabor Marton via Phabricator via cfe-commits]

martong added a comment.

> It looks like that the original code is correct in the decision of structural 
> equivalence of the original pair. If we have an (A,B) and (A,C) to compare, B 
> and C are in different decl chain, then (A,B) or (A,C) will be non-equivalent 
> (unless B and C are equivalent, but what to do in this case?). The problem 
> was that the code assumed that in this case always A and B (or A and C) are 
> non-equivalent. If NonEquivalentDecls is not filled in this case (or not used 
> at all) the problem does not exist.

I think we must not update the NonEquivalentDecls cache at that level, because 
as we've seen (during the discussion of https://reviews.llvm.org/D62131) it may 
store the wrong pairs.
However, it is still okay to cache the inequivalent decls in one level upper, 
right after the `Finish` returns.
See this diff 
https://github.com/martong/clang/compare/NonEqDecls_cache_in_an_upper_level~...martong:NonEqDecls_cache_in_an_upper_level?expand=1
Right now I started a build on our CI to see if it causes any slowdown.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Balázs Kéri via Phabricator via cfe-commits]

balazske marked an inline comment as done.
balazske added inline comments.



Comment at: clang/unittests/AST/StructuralEquivalenceTest.cpp:1323
+NonEquivalentDecls.end());
+  EXPECT_EQ(NonEquivalentDecls.find(std::make_pair(y1, y2)),
+NonEquivalentDecls.end());

martong wrote:
> This should be `EXPECT_NE` ! Because `void y(A*)` is not eq to `void y(B*)`
We have no guarantee that every non-equivalent Decl will be collected in 
`NonEquivalentDecls`, in this concrete case only the `(A1,B2)` pair is inserted 
(this is why the test passes). This line is to be removed, probably the last 
line too (it is an implementation detail that `(A1,B2)` is inserted but not 
even `(C1,C2)`).


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Gabor Marton via Phabricator via cfe-commits]

martong added inline comments.



Comment at: clang/unittests/AST/StructuralEquivalenceTest.cpp:1323
+NonEquivalentDecls.end());
+  EXPECT_EQ(NonEquivalentDecls.find(std::make_pair(y1, y2)),
+NonEquivalentDecls.end());

This should be `EXPECT_NE` ! Because `void y(A*)` is not eq to `void y(B*)`


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Gabor Marton via Phabricator via cfe-commits]

martong added inline comments.



Comment at: clang/lib/AST/ASTStructuralEquivalence.cpp:1586
-  if (EquivToD1)
-return EquivToD1 == D2->getCanonicalDecl();
 

balazske wrote:
> It looks like that the original code is correct in the decision of structural 
> equivalence of the original pair. If we have an (A,B) and (A,C) to compare, B 
> and C are in different decl chain, then (A,B) or (A,C) will be non-equivalent 
> (unless B and C are equivalent, but what to do in this case?). The problem 
> was that the code assumed that in this case always A and B (or A and C) are 
> non-equivalent. If `NonEquivalentDecls` is not filled in this case (or not 
> used at all) the problem does not exist.
I have a déjá vu feeling. We already had tried to get rid of the redecl chain 
comparison:
https://github.com/Ericsson/clang/pull/382/files


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Balázs Kéri via Phabricator via cfe-commits]

balazske marked an inline comment as done.
balazske added inline comments.



Comment at: clang/lib/AST/ASTStructuralEquivalence.cpp:1586
-  if (EquivToD1)
-return EquivToD1 == D2->getCanonicalDecl();
 

It looks like that the original code is correct in the decision of structural 
equivalence of the original pair. If we have an (A,B) and (A,C) to compare, B 
and C are in different decl chain, then (A,B) or (A,C) will be non-equivalent 
(unless B and C are equivalent, but what to do in this case?). The problem was 
that the code assumed that in this case always A and B (or A and C) are 
non-equivalent. If `NonEquivalentDecls` is not filled in this case (or not used 
at all) the problem does not exist.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D66538



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

[PATCH] D66538: [AST] AST structural equivalence to work internally with pairs.

[Balázs Kéri via Phabricator via cfe-commits]

balazske created this revision.
Herald added subscribers: cfe-commits, gamesh411, Szelethus, dkrupp.
Herald added a reviewer: martong.
Herald added a project: clang.

The structural equivalence check stores now pairs of nodes in the
'from' and 'to' context instead of only the node in 'from' context
and a corresponding one in 'to' context. This is needed to handle
cases when a Decl in the 'from' context is to be compared with
multiple Decls in the 'to' context.


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D66538

Files:
  clang/include/clang/AST/ASTStructuralEquivalence.h
  clang/lib/AST/ASTStructuralEquivalence.cpp
  clang/unittests/AST/StructuralEquivalenceTest.cpp

Index: clang/unittests/AST/StructuralEquivalenceTest.cpp
===
--- clang/unittests/AST/StructuralEquivalenceTest.cpp
+++ clang/unittests/AST/StructuralEquivalenceTest.cpp
@@ -1273,6 +1273,59 @@
   classTemplateSpecializationDecl(hasName("Primary")));
   EXPECT_FALSE(testStructuralMatch(t));
 }
+struct StructuralEquivalenceCacheTest : StructuralEquivalenceTest {};
+
+TEST_F(StructuralEquivalenceCacheTest, NonEquivalentDecls) {
+  auto Decls =
+  makeTuDecls("class A{}; class B{int i;}; void x(A*); void y(A*); class "
+  "C{friend void x(A*); friend void y(A*); };",
+  "class A{}; class B{int i;}; void x(A*); void y(B*); class "
+  "C{friend void x(A*); friend void y(B*); };",
+  Lang_CXX);
+
+  TranslationUnitDecl *TU1 = get<0>(Decls);
+  TranslationUnitDecl *TU2 = get<1>(Decls);
+  auto *C1 = LastDeclMatcher().match(
+  TU1, cxxRecordDecl(hasName("C"), unless(isImplicit(;
+  auto *C2 = LastDeclMatcher().match(
+  TU2, cxxRecordDecl(hasName("C"), unless(isImplicit(;
+  auto *A1 = FirstDeclMatcher().match(
+  TU1, cxxRecordDecl(hasName("A"), unless(isImplicit(;
+  auto *A2 = FirstDeclMatcher().match(
+  TU2, cxxRecordDecl(hasName("A"), unless(isImplicit(;
+  auto *B1 = FirstDeclMatcher().match(
+  TU1, cxxRecordDecl(hasName("B"), unless(isImplicit(;
+  auto *B2 = FirstDeclMatcher().match(
+  TU2, cxxRecordDecl(hasName("B"), unless(isImplicit(;
+  auto *x1 =
+  FirstDeclMatcher().match(TU1, functionDecl(hasName("x")));
+  auto *x2 =
+  FirstDeclMatcher().match(TU2, functionDecl(hasName("x")));
+  auto *y1 =
+  FirstDeclMatcher().match(TU1, functionDecl(hasName("y")));
+  auto *y2 =
+  FirstDeclMatcher().match(TU2, functionDecl(hasName("y")));
+
+  llvm::DenseSet> NonEquivalentDecls;
+  StructuralEquivalenceContext Ctx(
+  C1->getASTContext(), C2->getASTContext(), NonEquivalentDecls,
+  StructuralEquivalenceKind::Default, false, false);
+  bool Eq = Ctx.IsEquivalent(C1, C2);
+
+  EXPECT_FALSE(Eq);
+
+  EXPECT_EQ(NonEquivalentDecls.find(std::make_pair(A1, A2)),
+NonEquivalentDecls.end());
+  EXPECT_EQ(NonEquivalentDecls.find(std::make_pair(B1, B2)),
+NonEquivalentDecls.end());
+  EXPECT_EQ(NonEquivalentDecls.find(std::make_pair(x1, x2)),
+NonEquivalentDecls.end());
+  EXPECT_EQ(NonEquivalentDecls.find(std::make_pair(y1, y2)),
+NonEquivalentDecls.end());
+
+  EXPECT_NE(NonEquivalentDecls.find(std::make_pair(A1, B2)),
+NonEquivalentDecls.end());
+}
 
 } // end namespace ast_matchers
 } // end namespace clang
Index: clang/lib/AST/ASTStructuralEquivalence.cpp
===
--- clang/lib/AST/ASTStructuralEquivalence.cpp
+++ clang/lib/AST/ASTStructuralEquivalence.cpp
@@ -1574,20 +1574,24 @@
  Decl *D1, Decl *D2) {
   // FIXME: Check for known structural equivalences via a callback of some sort.
 
+  D1 = D1->getCanonicalDecl();
+  D2 = D2->getCanonicalDecl();
+  std::pair P = std::make_pair(D1, D2);
+
   // Check whether we already know that these two declarations are not
   // structurally equivalent.
-  if (Context.NonEquivalentDecls.count(
-  std::make_pair(D1->getCanonicalDecl(), D2->getCanonicalDecl(
+  if (Context.NonEquivalentDecls.count(P))
 return false;
 
-  // Determine whether we've already produced a tentative equivalence for D1.
-  Decl * = Context.TentativeEquivalences[D1->getCanonicalDecl()];
-  if (EquivToD1)
-return EquivToD1 == D2->getCanonicalDecl();
+  // Check if a check for these declarations is already pending.
+  // If yes D1 and D2 will be checked later (from DeclsToCheck),
+  // or these are already checked (and equivalent).
+  bool Inserted = Context.VisitedDecls.insert(P).second;
+  if (!Inserted)
+return true;
+
+  Context.DeclsToCheck.push(P);
 
-  // Produce a tentative equivalence D1 <-> D2, which will be checked later.
-  EquivToD1 = D2->getCanonicalDecl();
-  Context.DeclsToCheck.push_back(D1->getCanonicalDecl());
   return true;
 }
 
@@ -1703,11 +1707,13 @@
   // Ensure that the implementation functions (all static functions