diff --git a/clang/include/clang/AST/ASTStructuralEquivalence.h b/clang/include/clang/AST/ASTStructuralEquivalence.h --- a/clang/include/clang/AST/ASTStructuralEquivalence.h +++ b/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 +#include #include 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 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> DeclsToCheck; - /// Queue of declarations in the first context whose equivalence - /// with a declaration in the second context still needs to be verified. - std::deque 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 diff --git a/clang/lib/AST/ASTStructuralEquivalence.cpp b/clang/lib/AST/ASTStructuralEquivalence.cpp --- a/clang/lib/AST/ASTStructuralEquivalence.cpp +++ b/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 *&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 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; } } diff --git a/clang/unittests/AST/StructuralEquivalenceTest.cpp b/clang/unittests/AST/StructuralEquivalenceTest.cpp --- a/clang/unittests/AST/StructuralEquivalenceTest.cpp +++ b/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