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<CXXRecordDecl>().match(
+ TU1, cxxRecordDecl(hasName("C"), unless(isImplicit())));
+ auto *C2 = LastDeclMatcher<CXXRecordDecl>().match(
+ TU2, cxxRecordDecl(hasName("C"), unless(isImplicit())));
+ auto *A1 = FirstDeclMatcher<CXXRecordDecl>().match(
+ TU1, cxxRecordDecl(hasName("A"), unless(isImplicit())));
+ auto *A2 = FirstDeclMatcher<CXXRecordDecl>().match(
+ TU2, cxxRecordDecl(hasName("A"), unless(isImplicit())));
+ auto *B1 = FirstDeclMatcher<CXXRecordDecl>().match(
+ TU1, cxxRecordDecl(hasName("B"), unless(isImplicit())));
+ auto *B2 = FirstDeclMatcher<CXXRecordDecl>().match(
+ TU2, cxxRecordDecl(hasName("B"), unless(isImplicit())));
+ auto *x1 =
+ FirstDeclMatcher<FunctionDecl>().match(TU1, functionDecl(hasName("x")));
+ auto *x2 =
+ FirstDeclMatcher<FunctionDecl>().match(TU2, functionDecl(hasName("x")));
+ auto *y1 =
+ FirstDeclMatcher<FunctionDecl>().match(TU1, functionDecl(hasName("y")));
+ auto *y2 =
+ FirstDeclMatcher<FunctionDecl>().match(TU2, functionDecl(hasName("y")));
+
+ llvm::DenseSet<std::pair<Decl *, Decl *>> 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<Decl *, Decl *> 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 *&EquivToD1 = 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 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 DeclsToCheck list.
+ // VisitedDecls members) and can cause faulty behaviour.
+ // In other words: Do not start a graph search from a new node with the
+ // internal data of another search in progress.
+ // FIXME: Better encapsulation and separation of internal and public
+ // functionality.
assert(DeclsToCheck.empty());
- assert(TentativeEquivalences.empty());
+ assert(VisitedDecls.empty());
if (!::IsStructurallyEquivalent(*this, D1, D2))
return false;
@@ -1717,7 +1723,7 @@
bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {
assert(DeclsToCheck.empty());
- assert(TentativeEquivalences.empty());
+ assert(VisitedDecls.empty());
if (!::IsStructurallyEquivalent(*this, T1, T2))
return false;
@@ -1876,11 +1882,11 @@
bool StructuralEquivalenceContext::Finish() {
while (!DeclsToCheck.empty()) {
// Check the next declaration.
- Decl *D1 = DeclsToCheck.front();
- DeclsToCheck.pop_front();
+ std::pair<Decl *, Decl *> P = DeclsToCheck.front();
+ DeclsToCheck.pop();
- Decl *D2 = TentativeEquivalences[D1];
- assert(D2 && "Unrecorded tentative equivalence?");
+ Decl *D1 = P.first;
+ Decl *D2 = P.second;
bool Equivalent =
CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2);
@@ -1888,8 +1894,8 @@
if (!Equivalent) {
// Note that these two declarations are not equivalent (and we already
// know about it).
- NonEquivalentDecls.insert(
- std::make_pair(D1->getCanonicalDecl(), D2->getCanonicalDecl()));
+ NonEquivalentDecls.insert(P);
+
return true;
}
}
Index: clang/include/clang/AST/ASTStructuralEquivalence.h
===================================================================
--- clang/include/clang/AST/ASTStructuralEquivalence.h
+++ clang/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 <deque>
+#include <queue>
#include <utility>
namespace clang {
@@ -42,14 +42,13 @@
/// AST contexts for which we are checking structural equivalence.
ASTContext &FromCtx, &ToCtx;
- /// 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<Decl *, Decl *> TentativeEquivalences;
+ // 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<std::pair<Decl *, Decl *>> DeclsToCheck;
- /// Queue of declarations in the first context whose equivalence
- /// with a declaration in the second context still needs to be verified.
- std::deque<Decl *> 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<std::pair<Decl *, Decl *>> 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
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
