[AST] AST structural equivalence to work internally with pairs.

[balazske]

Summary

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.

[balazske]

clang/lib/AST/ASTStructuralEquivalence.cpp

1586 ↗

(On Diff #216403)

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.

[martong]

clang/lib/AST/ASTStructuralEquivalence.cpp

1586 ↗

(On Diff #216403)

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

[martong]

clang/unittests/AST/StructuralEquivalenceTest.cpp

1323 ↗

(On Diff #216403)

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

[balazske]

clang/unittests/AST/StructuralEquivalenceTest.cpp

1323 ↗

(On Diff #216403)

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

[martong]

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.

[balazske]

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.

[martong]

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

[balazske]

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

[martong]

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<CXXRecordDecl>().match(
      TU1, cxxRecordDecl(hasName("C"), unless(isImplicit())));
  auto *C2 = LastDeclMatcher<CXXRecordDecl>().match(
      TU2, cxxRecordDecl(hasName("C"), unless(isImplicit())));

  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_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<FunctionDecl>().match(TU1, functionDecl(hasName("x")));
  auto *x2 =
      FirstDeclMatcher<FunctionDecl>().match(TU2, functionDecl(hasName("x")));

  llvm::DenseSet<std::pair<Decl *, Decl *>> NonEquivalentDecls;
  StructuralEquivalenceContext Ctx(
      x1->getASTContext(), x2->getASTContext(), NonEquivalentDecls,
      StructuralEquivalenceKind::Default, false, false);
  bool Eq = Ctx.IsEquivalent(x1, x2);

  EXPECT_FALSE(Eq);
}

[martong]

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<CXXRecordDecl>().match(
+      TU1, cxxRecordDecl(hasName("C"), unless(isImplicit())));
+  auto *C2 = LastDeclMatcher<CXXRecordDecl>().match(
+      TU2, cxxRecordDecl(hasName("C"), unless(isImplicit())));
+  auto *x1 =
+      FirstDeclMatcher<FunctionDecl>().match(TU1, functionDecl(hasName("x")));
+  auto *x2 =
+      FirstDeclMatcher<FunctionDecl>().match(TU2, functionDecl(hasName("x")));
+
+  llvm::DenseSet<std::pair<Decl *, Decl *>> 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));
+  }
+}

[balazske]

• Updated tests.

[balazske]

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<FunctionDecl>(TU, functionDecl(hasName("x")))));

)

[a_sidorin]

Hello Balasz,
I have some comments inline.

clang/lib/AST/ASTStructuralEquivalence.cpp

1579 ↗

(On Diff #216851)

std::pair<Decl *, Decl *> P{D1, D2}?

1888 ↗

(On Diff #216851)

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

clang/unittests/AST/StructuralEquivalenceTest.cpp

1290 ↗

(On Diff #216851)

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.

1291 ↗

(On Diff #216851)

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

1314 ↗

(On Diff #216851)

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

1357 ↗

(On Diff #216851)

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?

1399 ↗

(On Diff #216851)

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

[balazske]

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.

clang/unittests/AST/StructuralEquivalenceTest.cpp

1357 ↗

(On Diff #216851)

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.

1399 ↗

(On Diff #216851)

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

[balazske]

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

[martong]

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<FunctionDecl>(TU, functionDecl(hasName("x")))));

)

Ok, that looks good.

[martong]

@a_sidorin Ping

[a_sidorin]

Looks good, thank you for addressing the comments!

cfe/trunk/include/clang/AST/ASTStructuralEquivalence.h

 
 #ifndef LLVM_CLANG_AST_ASTSTRUCTURALEQUIVALENCE_H
 #define LLVM_CLANG_AST_ASTSTRUCTURALEQUIVALENCE_H
 
 #include "clang/AST/DeclBase.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Optional.h"
-#include <deque>
+#include <queue>
 #include <utility>
 
 namespace clang {
 
 class ASTContext;
 class Decl;
 class DiagnosticBuilder;
 class QualType;
 class RecordDecl;
 class SourceLocation;
 
 /// \brief Whether to perform a normal or minimal equivalence check.
 /// In case of `Minimal`, we do not perform a recursive check of decls with
 /// external storage.
 enum class StructuralEquivalenceKind {
   Default,
   Minimal,
 };
 
 struct StructuralEquivalenceContext {
   /// 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 declarations in the first context whose equivalence
-  /// with a declaration in the second context still needs to be verified.
-  std::deque<Decl *> 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<std::pair<Decl *, 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).
   llvm::DenseSet<std::pair<Decl *, Decl *>> &NonEquivalentDecls;
 
   StructuralEquivalenceKind EqKind;
 
   /// Whether we're being strict about the spelling of types when
struct StructuralEquivalenceContext {
   DiagnosticBuilder Diag1(SourceLocation Loc, unsigned DiagID);
   DiagnosticBuilder Diag2(SourceLocation Loc, unsigned DiagID);
 
   /// Determine whether the two declarations 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(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
   /// context.
   ///
   /// \returns Returns the index of this anonymous struct/union in its context,
   /// including the next assigned index (if none of them match). Returns an
   /// empty option if the context is not a record, i.e.. if the anonymous

cfe/trunk/lib/AST/ASTStructuralEquivalence.cpp

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
   return true;
 }
 
 /// Determine structural equivalence of two declarations.
 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                      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{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;
 }
 
 DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,
                                                       unsigned DiagID) {
   assert(Complain && "Not allowed to complain");
   if (LastDiagFromC2)
     FromCtx.getDiagnostics().notePriorDiagnosticFrom(ToCtx.getDiagnostics());
unsigned StructuralEquivalenceContext::getApplicableDiagnostic(
   llvm_unreachable("Diagnostic kind not handled in preceding switch");
 }
 
 bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) {
 
   // 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;
 
   return !Finish();
 }
 
 bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {
   assert(DeclsToCheck.empty());
-  assert(TentativeEquivalences.empty());
+  assert(VisitedDecls.empty());
   if (!::IsStructurallyEquivalent(*this, T1, T2))
     return false;
 
   return !Finish();
 }
 
 bool StructuralEquivalenceContext::CheckCommonEquivalence(Decl *D1, Decl *D2) {
   // Check for equivalent described template.
bool StructuralEquivalenceContext::CheckKindSpecificEquivalence(
   }
 
   return true;
 }
 
 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);
 
     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;
     }
   }
 
   return false;
 }

cfe/trunk/unittests/AST/StructuralEquivalenceTest.cpp

auto t = makeDecls<ClassTemplateSpecializationDecl>(
         // Explicit instantiation with N::Arg which shadows ::Arg
         template struct Primary<Arg>;
       }
       )",
       Lang_CXX,
       classTemplateSpecializationDecl(hasName("Primary")));
   EXPECT_FALSE(testStructuralMatch(t));
 }
+struct StructuralEquivalenceCacheTest : public StructuralEquivalenceTest {
+  llvm::DenseSet<std::pair<Decl *, Decl *>> NonEquivalentDecls;
+
+  template <typename NodeType, typename MatcherType>
+  std::pair<NodeType *, NodeType *>
+  findDeclPair(std::tuple<TranslationUnitDecl *, TranslationUnitDecl *> TU,
+               MatcherType M) {
+    NodeType *D0 = FirstDeclMatcher<NodeType>().match(get<0>(TU), M);
+    NodeType *D1 = FirstDeclMatcher<NodeType>().match(get<1>(TU), M);
+    return {D0, D1};
+  }
+
+  template <typename NodeType>
+  bool isInNonEqCache(std::pair<NodeType *, NodeType *> 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<FunctionDecl>(TU, functionDecl(hasName("x")));
+  EXPECT_FALSE(Ctx.IsEquivalent(X.first, X.second));
+
+  EXPECT_FALSE(isInNonEqCache(findDeclPair<CXXRecordDecl>(
+      TU, cxxRecordDecl(hasName("A"), unless(isImplicit())))));
+  EXPECT_FALSE(isInNonEqCache(findDeclPair<CXXRecordDecl>(
+      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<CXXRecordDecl>(
+      TU, cxxRecordDecl(hasName("C"), unless(isImplicit())));
+  EXPECT_FALSE(Ctx.IsEquivalent(C.first, C.second));
+
+  EXPECT_FALSE(isInNonEqCache(C));
+  EXPECT_FALSE(isInNonEqCache(findDeclPair<CXXRecordDecl>(
+      TU, cxxRecordDecl(hasName("A"), unless(isImplicit())))));
+  EXPECT_FALSE(isInNonEqCache(findDeclPair<CXXRecordDecl>(
+      TU, cxxRecordDecl(hasName("B"), unless(isImplicit())))));
+  EXPECT_FALSE(isInNonEqCache(
+      findDeclPair<FunctionDecl>(TU, functionDecl(hasName("x")))));
+  EXPECT_FALSE(isInNonEqCache(
+      findDeclPair<FunctionDecl>(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<CXXRecordDecl>(
+      TU, cxxRecordDecl(hasName("C"), unless(isImplicit())));
+  EXPECT_TRUE(Ctx.IsEquivalent(C.first, C.second));
+
+  EXPECT_FALSE(isInNonEqCache(C));
+  EXPECT_FALSE(isInNonEqCache(findDeclPair<CXXRecordDecl>(
+      TU, cxxRecordDecl(hasName("A"), unless(isImplicit())))));
+  EXPECT_FALSE(isInNonEqCache(
+      findDeclPair<FunctionDecl>(TU, functionDecl(hasName("x")))));
+}
 
 } // end namespace ast_matchers
 } // end namespace clang