martong updated this revision to Diff 155858.
martong added a comment.
- Add comment about structural eq and BFS
Repository:
rC Clang
https://reviews.llvm.org/D49300
Files:
include/clang/AST/ASTStructuralEquivalence.h
lib/AST/ASTImporter.cpp
lib/AST/ASTStructuralEquivalence.cpp
lib/Sema/SemaType.cpp
unittests/AST/StructuralEquivalenceTest.cpp
Index: unittests/AST/StructuralEquivalenceTest.cpp
===================================================================
--- unittests/AST/StructuralEquivalenceTest.cpp
+++ unittests/AST/StructuralEquivalenceTest.cpp
@@ -82,7 +82,7 @@
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) {
Index: lib/Sema/SemaType.cpp
===================================================================
--- lib/Sema/SemaType.cpp
+++ lib/Sema/SemaType.cpp
@@ -7498,7 +7498,7 @@
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
Index: lib/AST/ASTStructuralEquivalence.cpp
===================================================================
--- lib/AST/ASTStructuralEquivalence.cpp
+++ lib/AST/ASTStructuralEquivalence.cpp
@@ -10,6 +10,59 @@
// 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"
@@ -184,18 +237,18 @@
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?
@@ -1205,8 +1258,8 @@
return false;
}
- if (!Context.IsStructurallyEquivalent(Params1->getParam(I),
- Params2->getParam(I)))
+ if (!IsStructurallyEquivalent(Context, Params1->getParam(I),
+ Params2->getParam(I)))
return false;
}
@@ -1243,7 +1296,7 @@
}
// 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)
@@ -1294,8 +1347,8 @@
return false;
// Check the templated declaration.
- return Context.IsStructurallyEquivalent(D1->getTemplatedDecl(),
- D2->getTemplatedDecl());
+ return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),
+ D2->getTemplatedDecl());
}
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
@@ -1306,8 +1359,8 @@
return false;
// Check the templated declaration.
- return Context.IsStructurallyEquivalent(D1->getTemplatedDecl()->getType(),
- D2->getTemplatedDecl()->getType());
+ return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(),
+ D2->getTemplatedDecl()->getType());
}
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
@@ -1418,16 +1471,26 @@
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;
Index: lib/AST/ASTImporter.cpp
===================================================================
--- lib/AST/ASTImporter.cpp
+++ lib/AST/ASTImporter.cpp
@@ -295,6 +295,7 @@
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,
@@ -1592,7 +1593,15 @@
: 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.
@@ -1608,40 +1617,40 @@
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,
@@ -1660,16 +1669,16 @@
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) {
@@ -2978,15 +2987,11 @@
// 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()) {
@@ -7621,5 +7626,5 @@
StructuralEquivalenceContext Ctx(FromContext, ToContext, NonEquivalentDecls,
getStructuralEquivalenceKind(*this), false,
Complain);
- return Ctx.IsStructurallyEquivalent(From, To);
+ return Ctx.IsEquivalent(From, To);
}
Index: include/clang/AST/ASTStructuralEquivalence.h
===================================================================
--- include/clang/AST/ASTStructuralEquivalence.h
+++ include/clang/AST/ASTStructuralEquivalence.h
@@ -85,10 +85,18 @@
/// 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.
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
