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 &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 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 *&EquivToD1 = 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 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; } } Index: cfe/trunk/unittests/AST/StructuralEquivalenceTest.cpp =================================================================== --- cfe/trunk/unittests/AST/StructuralEquivalenceTest.cpp +++ cfe/trunk/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