[ASTImporter] Fix poisonous structural equivalence cache

[martong]

Summary

Implementation functions call into the member functions of
ASTStructuralEquivalence, thus they can falsely alter the DeclsToCheck state
(they add decls). This results that some leaf declarations can be stated as
inequivalent as a side effect of one inequivalent element in the DeclsToCheck
list. And since we store the non-equivalencies, any (otherwise independent)
decls will be rendered as non-equivalent. Solution: I tried to clearly
separate the implementation functions (the static ones) and the public
interface. From now on, the implementation functions do not call any public
member functions, only other implementation functions.

[a_sidorin]

Hi Gabor,
Could you provide some tests for the issue?

[martong]

Hi Aleksei,

Unfortunately, it seems that it is very to hard synthesize a lit or unit test for this fix.
I have found this flaw during the CTU analysis of Bitcoin, where the AST was immense.

Because of the lack of tests, now I am trying to persuade you based on some theory.
Let's consider this simple BFS algorithm from the s source:

void bfs(Graph G, int s)
{
  Queue<Integer> queue = new Queue<Integer>();
  marked[s] = true; // Mark the source
  queue.enqueue(s); // and put it on the queue.
  while (!q.isEmpty()) {
    int v = queue.dequeue(); // Remove next vertex from the queue.
    for (int w : G.adj(v))
      if (!marked[w]) // For every unmarked adjacent vertex,
      {
        marked[w] = true;
        queue.enqueue(w);
      }
  }
}

I believe , the structural equivalence check could be implemented as a parallel BFS on a pair of graphs.
And, I think that must have been the original approach at the beginning.
Indeed, it has it's queue, which holds pairs of nodes, one from each graph, this is the DeclsToCheck and it's pair is in TentativeEquivalences.
TentativeEquivalences also plays the role of the marking (marked) functionality above, we use it to check whether we've already seen a pair of nodes.

We put in the elements into the queue only in the toplevel decl check function:

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     Decl *D1, Decl *D2);

The while loop where we iterate over the children is implemented in Finish().
And Finish is called only from the two member functions which check the equivalency of two Decls or two Types. ASTImporter (and other clients) call only these functions.

The static implementation functions are called from Finish, these push the children nodes to the queue via static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, Decl *D1, Decl *D2).
So far so good, this is almost like the BFS.
However, if we let a static implementation function to call Finish via another member function that means we end up with two nested while loops each of them working on the same queue. This is wrong and nobody can reason about it's doing. (This time it had an effect of poisoning the non-equivalencies cache.)

So, now TentativeEquivalences plays two roles. It is used to store the second half of the decls which we want to compare, plus it plays a role in closing the recursion. On a long term, I think, (after this change) we could refactor structural equivalency to be more alike to the traditional BFS.

[a_sidorin]

Hi Gabor,

Thank you for this explanation, it sounds reasonable. Ithink it should be placed into the commit message or into the comment somewhere.

[martong]

@a_sidorin

Ok, thanks Aleksei for the review. I added the explanation as file comments into StructuralEquivalence.cpp.

[martong]

• Add comment about structural eq and BFS

include/clang/AST/ASTStructuralEquivalence.h

StructuralEquivalenceContext(
         EqKind(EqKind), StrictTypeSpelling(StrictTypeSpelling),
         ErrorOnTagTypeMismatch(ErrorOnTagTypeMismatch), Complain(Complain) {}
 
   DiagnosticBuilder Diag1(SourceLocation Loc, unsigned DiagID);
   DiagnosticBuilder Diag2(SourceLocation Loc, unsigned DiagID);
 
   /// Determine whether the two declarations are structurally
   /// equivalent.
-  bool IsStructurallyEquivalent(Decl *D1, Decl *D2);
+  /// 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.
+  bool IsEquivalent(Decl *D1, Decl *D2);
 
   /// Determine whether the two types are structurally equivalent.
-  bool IsStructurallyEquivalent(QualType T1, QualType T2);
+  /// 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.
+  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
   /// struct/union is at namespace or block scope.

lib/AST/ASTImporter.cpp

public:
     using TemplateArgsTy = SmallVector<TemplateArgument, 8>;
     using OptionalTemplateArgsTy = Optional<TemplateArgsTy>;
     std::tuple<FunctionTemplateDecl *, OptionalTemplateArgsTy>
     ImportFunctionTemplateWithTemplateArgsFromSpecialization(
         FunctionDecl *FromFD);
 
     bool ImportTemplateInformation(FunctionDecl *FromFD, FunctionDecl *ToFD);
 
+    bool IsStructuralMatch(Decl *From, Decl *To, bool Complain);
     bool IsStructuralMatch(RecordDecl *FromRecord, RecordDecl *ToRecord,
                            bool Complain = true);
     bool IsStructuralMatch(VarDecl *FromVar, VarDecl *ToVar,
                            bool Complain = true);
     bool IsStructuralMatch(EnumDecl *FromEnum, EnumDecl *ToRecord);
     bool IsStructuralMatch(EnumConstantDecl *FromEC, EnumConstantDecl *ToEC);
     bool IsStructuralMatch(FunctionTemplateDecl *From,
                            FunctionTemplateDecl *To);

 }
 
 static StructuralEquivalenceKind
 getStructuralEquivalenceKind(const ASTImporter &Importer) {
   return Importer.isMinimalImport() ? StructuralEquivalenceKind::Minimal
                                     : StructuralEquivalenceKind::Default;
 }
 
-bool ASTNodeImporter::IsStructuralMatch(RecordDecl *FromRecord, 
+bool ASTNodeImporter::IsStructuralMatch(Decl *From, Decl *To, bool Complain) {
+  StructuralEquivalenceContext Ctx(
+      Importer.getFromContext(), Importer.getToContext(),
+      Importer.getNonEquivalentDecls(), getStructuralEquivalenceKind(Importer),
+      false, Complain);
+  return Ctx.IsEquivalent(From, To);
+}
+
+bool ASTNodeImporter::IsStructuralMatch(RecordDecl *FromRecord,
                                         RecordDecl *ToRecord, bool Complain) {
   // Eliminate a potential failure point where we attempt to re-import
   // something we're trying to import while completing ToRecord.
   Decl *ToOrigin = Importer.GetOriginalDecl(ToRecord);
   if (ToOrigin) {
     auto *ToOriginRecord = dyn_cast<RecordDecl>(ToOrigin);
     if (ToOriginRecord)
       ToRecord = ToOriginRecord;
   }
 
   StructuralEquivalenceContext Ctx(Importer.getFromContext(),
                                    ToRecord->getASTContext(),
                                    Importer.getNonEquivalentDecls(),
                                    getStructuralEquivalenceKind(Importer),
                                    false, Complain);
-  return Ctx.IsStructurallyEquivalent(FromRecord, ToRecord);
+  return Ctx.IsEquivalent(FromRecord, ToRecord);
 }
 
 bool ASTNodeImporter::IsStructuralMatch(VarDecl *FromVar, VarDecl *ToVar,
                                         bool Complain) {
   StructuralEquivalenceContext Ctx(
       Importer.getFromContext(), Importer.getToContext(),
       Importer.getNonEquivalentDecls(), getStructuralEquivalenceKind(Importer),
       false, Complain);
-  return Ctx.IsStructurallyEquivalent(FromVar, ToVar);
+  return Ctx.IsEquivalent(FromVar, ToVar);
 }
 
 bool ASTNodeImporter::IsStructuralMatch(EnumDecl *FromEnum, EnumDecl *ToEnum) {
   StructuralEquivalenceContext Ctx(
       Importer.getFromContext(), Importer.getToContext(),
       Importer.getNonEquivalentDecls(), getStructuralEquivalenceKind(Importer));
-  return Ctx.IsStructurallyEquivalent(FromEnum, ToEnum);
+  return Ctx.IsEquivalent(FromEnum, ToEnum);
 }
 
 bool ASTNodeImporter::IsStructuralMatch(FunctionTemplateDecl *From,
                                         FunctionTemplateDecl *To) {
   StructuralEquivalenceContext Ctx(
       Importer.getFromContext(), Importer.getToContext(),
       Importer.getNonEquivalentDecls(), getStructuralEquivalenceKind(Importer),
       false, false);
-  return Ctx.IsStructurallyEquivalent(From, To);
+  return Ctx.IsEquivalent(From, To);
 }
 
 bool ASTNodeImporter::IsStructuralMatch(FunctionDecl *From, FunctionDecl *To) {
   StructuralEquivalenceContext Ctx(
       Importer.getFromContext(), Importer.getToContext(),
       Importer.getNonEquivalentDecls(), getStructuralEquivalenceKind(Importer),
       false, false);
-  return Ctx.IsStructurallyEquivalent(From, To);
+  return Ctx.IsEquivalent(From, To);
 }
 
 bool ASTNodeImporter::IsStructuralMatch(EnumConstantDecl *FromEC,
                                         EnumConstantDecl *ToEC) {
   const llvm::APSInt &FromVal = FromEC->getInitVal();
   const llvm::APSInt &ToVal = ToEC->getInitVal();
 
   return FromVal.isSigned() == ToVal.isSigned() &&
          FromVal.getBitWidth() == ToVal.getBitWidth() &&
          FromVal == ToVal;
 }
 
 bool ASTNodeImporter::IsStructuralMatch(ClassTemplateDecl *From,
                                         ClassTemplateDecl *To) {
   StructuralEquivalenceContext Ctx(Importer.getFromContext(),
                                    Importer.getToContext(),
                                    Importer.getNonEquivalentDecls(),
                                    getStructuralEquivalenceKind(Importer));
-  return Ctx.IsStructurallyEquivalent(From, To);
+  return Ctx.IsEquivalent(From, To);
 }
 
 bool ASTNodeImporter::IsStructuralMatch(VarTemplateDecl *From,
                                         VarTemplateDecl *To) {
   StructuralEquivalenceContext Ctx(Importer.getFromContext(),
                                    Importer.getToContext(),
                                    Importer.getNonEquivalentDecls(),
                                    getStructuralEquivalenceKind(Importer));
-  return Ctx.IsStructurallyEquivalent(From, To);
+  return Ctx.IsEquivalent(From, To);
 }
 
 Decl *ASTNodeImporter::VisitDecl(Decl *D) {
   Importer.FromDiag(D->getLocation(), diag::err_unsupported_ast_node)
     << D->getDeclKindName();
   return nullptr;
 }
 
DeclContext *LexicalDC = D->getDeclContext() == D->getLexicalDeclContext()
       ? DC : Importer.ImportContext(D->getLexicalDeclContext());
   if (!DC || !LexicalDC)
     return nullptr;
 
   // Determine whether we've already imported this decl.
   // FriendDecl is not a NamedDecl so we cannot use localUncachedLookup.
   auto *RD = cast<CXXRecordDecl>(DC);
   FriendDecl *ImportedFriend = RD->getFirstFriend();
-  StructuralEquivalenceContext Context(
-      Importer.getFromContext(), Importer.getToContext(),
-      Importer.getNonEquivalentDecls(), getStructuralEquivalenceKind(Importer),
-      false, false);
 
   while (ImportedFriend) {
     if (D->getFriendDecl() && ImportedFriend->getFriendDecl()) {
-      if (Context.IsStructurallyEquivalent(D->getFriendDecl(),
-                                           ImportedFriend->getFriendDecl()))
+      if (IsStructuralMatch(D->getFriendDecl(), ImportedFriend->getFriendDecl(),
+                            /*Complain=*/false))
         return Importer.MapImported(D, ImportedFriend);
 
     } else if (D->getFriendType() && ImportedFriend->getFriendType()) {
       if (Importer.IsStructurallyEquivalent(
             D->getFriendType()->getType(),
             ImportedFriend->getFriendType()->getType(), true))
         return Importer.MapImported(D, ImportedFriend);
     }
bool ASTImporter::IsStructurallyEquivalent(QualType From, QualType To,
   llvm::DenseMap<const Type *, const Type *>::iterator Pos
    = ImportedTypes.find(From.getTypePtr());
   if (Pos != ImportedTypes.end() && ToContext.hasSameType(Import(From), To))
     return true;
 
   StructuralEquivalenceContext Ctx(FromContext, ToContext, NonEquivalentDecls,
                                    getStructuralEquivalenceKind(*this), false,
                                    Complain);
-  return Ctx.IsStructurallyEquivalent(From, To);
+  return Ctx.IsEquivalent(From, To);
 }

lib/AST/ASTStructuralEquivalence.cpp

 //===- ASTStructuralEquivalence.cpp ---------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file implement StructuralEquivalenceContext class and helper functions
 //  for layout matching.
 //
+// The structural equivalence check could have been implemented as a parallel
+// BFS on a pair of graphs.  That must have been the original approach at the
+// beginning.
+// Let's consider this simple BFS algorithm from the `s` source:
+// ```
+// void bfs(Graph G, int s)
+// {
+//   Queue<Integer> queue = new Queue<Integer>();
+//   marked[s] = true; // Mark the source
+//   queue.enqueue(s); // and put it on the queue.
+//   while (!q.isEmpty()) {
+//     int v = queue.dequeue(); // Remove next vertex from the queue.
+//     for (int w : G.adj(v))
+//       if (!marked[w]) // For every unmarked adjacent vertex,
+//       {
+//         marked[w] = true;
+//         queue.enqueue(w);
+//       }
+//   }
+// }
+// ```
+// Indeed, it has it's queue, which holds pairs of nodes, one from each graph,
+// this is the `DeclsToCheck` and it's pair is in `TentativeEquivalences`.
+// `TentativeEquivalences` also plays the role of the marking (`marked`)
+// functionality above, we use it to check whether we've already seen a pair of
+// nodes.
+//
+// We put in the elements into the queue only in the toplevel decl check
+// function:
+// ```
+// static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
+//                                      Decl *D1, Decl *D2);
+// ```
+// The `while` loop where we iterate over the children is implemented in
+// `Finish()`.  And `Finish` is called only from the two **member** functions
+// which check the equivalency of two Decls or two Types. ASTImporter (and
+// other clients) call only these functions.
+//
+// The `static` implementation functions are called from `Finish`, these push
+// the children nodes to the queue via `static bool
+// IsStructurallyEquivalent(StructuralEquivalenceContext &Context, Decl *D1,
+// Decl *D2)`.  So far so good, this is almost like the BFS.  However, if we
+// let a static implementation function to call `Finish` via another **member**
+// function that means we end up with two nested while loops each of them
+// working on the same queue. This is wrong and nobody can reason about it's
+// doing. Thus, static implementation functions must not call the **member**
+// functions.
+//
+// So, now `TentativeEquivalences` plays two roles. It is used to store the
+// second half of the decls which we want to compare, plus it plays a role in
+// closing the recursion. On a long term, we could refactor structural
+// equivalency to be more alike to the traditional BFS.
+//
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/ASTStructuralEquivalence.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTDiagnostic.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclCXX.h"
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
   if (Arg1.getKind() != Arg2.getKind())
     return false;
 
   switch (Arg1.getKind()) {
   case TemplateArgument::Null:
     return true;
 
   case TemplateArgument::Type:
-    return Context.IsStructurallyEquivalent(Arg1.getAsType(), Arg2.getAsType());
+    return IsStructurallyEquivalent(Context, Arg1.getAsType(), Arg2.getAsType());
 
   case TemplateArgument::Integral:
-    if (!Context.IsStructurallyEquivalent(Arg1.getIntegralType(),
+    if (!IsStructurallyEquivalent(Context, Arg1.getIntegralType(),
                                           Arg2.getIntegralType()))
       return false;
 
     return llvm::APSInt::isSameValue(Arg1.getAsIntegral(),
                                      Arg2.getAsIntegral());
 
   case TemplateArgument::Declaration:
-    return Context.IsStructurallyEquivalent(Arg1.getAsDecl(), Arg2.getAsDecl());
+    return IsStructurallyEquivalent(Context, Arg1.getAsDecl(), Arg2.getAsDecl());
 
   case TemplateArgument::NullPtr:
     return true; // FIXME: Is this correct?
 
   case TemplateArgument::Template:
     return IsStructurallyEquivalent(Context, Arg1.getAsTemplate(),
                                     Arg2.getAsTemplate());
 
if (Params1->getParam(I)->getKind() != Params2->getParam(I)->getKind()) {
         Context.Diag2(Params2->getParam(I)->getLocation(),
                       diag::err_odr_different_template_parameter_kind);
         Context.Diag1(Params1->getParam(I)->getLocation(),
                       diag::note_odr_template_parameter_here);
       }
       return false;
     }
 
-    if (!Context.IsStructurallyEquivalent(Params1->getParam(I),
-                                          Params2->getParam(I)))
+    if (!IsStructurallyEquivalent(Context, Params1->getParam(I),
       return false;
   }
 
   return true;
 }
 
 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                      TemplateTypeParmDecl *D1,
if (Context.Complain) {
           << D2->isParameterPack();
       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
           << D1->isParameterPack();
     }
     return false;
   }
 
   // Check types.
-  if (!Context.IsStructurallyEquivalent(D1->getType(), D2->getType())) {
+  if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType())) {
     if (Context.Complain) {
       Context.Diag2(D2->getLocation(),
                     diag::err_odr_non_type_parameter_type_inconsistent)
           << D2->getType() << D1->getType();
       Context.Diag1(D1->getLocation(), diag::note_odr_value_here)
           << D1->getType();
     }
     return false;

 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                      ClassTemplateDecl *D1,
                                      ClassTemplateDecl *D2) {
   // Check template parameters.
   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
     return false;
 
   // Check the templated declaration.
-  return Context.IsStructurallyEquivalent(D1->getTemplatedDecl(),
-                                          D2->getTemplatedDecl());
+  return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),
 }
 
 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                      FunctionTemplateDecl *D1,
                                      FunctionTemplateDecl *D2) {
   // Check template parameters.
   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
     return false;
 
   // Check the templated declaration.
-  return Context.IsStructurallyEquivalent(D1->getTemplatedDecl()->getType(),
-                                          D2->getTemplatedDecl()->getType());
+  return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(),
 }
 
 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                      FriendDecl *D1, FriendDecl *D2) {
   if ((D1->getFriendType() && D2->getFriendDecl()) ||
       (D1->getFriendDecl() && D2->getFriendType())) {
       return false;
   }
if (const auto *RecType = dyn_cast<RecordType>(FieldType)) {
         continue;
       }
     }
   }
 
   return Index;
 }
 
-bool StructuralEquivalenceContext::IsStructurallyEquivalent(Decl *D1,
-                                                            Decl *D2) {
+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.
+  assert(DeclsToCheck.empty());
+  assert(TentativeEquivalences.empty());
+
   if (!::IsStructurallyEquivalent(*this, D1, D2))
     return false;
 
   return !Finish();
 }
 
-bool StructuralEquivalenceContext::IsStructurallyEquivalent(QualType T1,
-                                                            QualType T2) {
+bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {
+  assert(DeclsToCheck.empty());
+  assert(TentativeEquivalences.empty());
   if (!::IsStructurallyEquivalent(*this, T1, T2))
     return false;
 
   return !Finish();
 }
 
 bool StructuralEquivalenceContext::Finish() {
   while (!DeclsToCheck.empty()) {

lib/Sema/SemaType.cpp

bool Sema::hasStructuralCompatLayout(Decl *D, Decl *Suggested) {
 
   // FIXME: Add a specific mode for C11 6.2.7/1 in StructuralEquivalenceContext
   // and isolate from other C++ specific checks.
   StructuralEquivalenceContext Ctx(
       D->getASTContext(), Suggested->getASTContext(), NonEquivalentDecls,
       StructuralEquivalenceKind::Default,
       false /*StrictTypeSpelling*/, true /*Complain*/,
       true /*ErrorOnTagTypeMismatch*/);
-  return Ctx.IsStructurallyEquivalent(D, Suggested);
+  return Ctx.IsEquivalent(D, Suggested);
 }
 
 /// Determine whether there is any declaration of \p D that was ever a
 ///        definition (perhaps before module merging) and is currently visible.
 /// \param D The definition of the entity.
 /// \param Suggested Filled in with the declaration that should be made visible
 ///        in order to provide a definition of this entity.
 /// \param OnlyNeedComplete If \c true, we only need the type to be complete,

unittests/AST/StructuralEquivalenceTest.cpp

std::tuple<NamedDecl *, NamedDecl *> makeNamedDecls(
     return makeDecls<NamedDecl>(SrcCode0, SrcCode1, Lang, Matcher);
   }
 
   bool testStructuralMatch(Decl *D0, Decl *D1) {
     llvm::DenseSet<std::pair<Decl *, Decl *>> NonEquivalentDecls;
     StructuralEquivalenceContext Ctx(
         D0->getASTContext(), D1->getASTContext(), NonEquivalentDecls,
         StructuralEquivalenceKind::Default, false, false);
-    return Ctx.IsStructurallyEquivalent(D0, D1);
+    return Ctx.IsEquivalent(D0, D1);
   }
 
   bool testStructuralMatch(std::tuple<Decl *, Decl *> t) {
     return testStructuralMatch(get<0>(t), get<1>(t));
   }
 };
 
 TEST_F(StructuralEquivalenceTest, Int) {