[PATCH] D49300: [ASTImporter] Fix poisonous structural equivalence cache
This revision was automatically updated to reflect the committed changes.
Closed by commit rC337275: [ASTImporter] Fix poisonous structural equivalence
cache (authored by martong, committed by ).
Changed prior to commit:
https://reviews.llvm.org/D49300?vs=155858=155863#toc
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: 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(DC);
FriendDecl *ImportedFriend = RD->getFirstFriend();
- StructuralEquivalenceContext Context(
- Importer.getFromContext(), Importer.getToContext(),
-
[PATCH] D49300: [ASTImporter] Fix poisonous structural equivalence cache
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 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 queue = new Queue();
+// 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 ,
+// 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 , 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
[PATCH] D49300: [ASTImporter] Fix poisonous structural equivalence cache
martong added a comment. @a_sidorin Ok, thanks Aleksei for the review. I added the explanation as file comments into `StructuralEquivalence.cpp`. Repository: rC Clang https://reviews.llvm.org/D49300 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D49300: [ASTImporter] Fix poisonous structural equivalence cache
a_sidorin accepted this revision. a_sidorin added a comment. This revision is now accepted and ready to land. Hi Gabor, Thank you for this explanation, it sounds reasonable. Ithink it should be placed into the commit message or into the comment somewhere. Repository: rC Clang https://reviews.llvm.org/D49300 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D49300: [ASTImporter] Fix poisonous structural equivalence cache
martong added a comment.
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 queue = new Queue();
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 ,
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.
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.
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.
Repository:
rC Clang
https://reviews.llvm.org/D49300
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D49300: [ASTImporter] Fix poisonous structural equivalence cache
a_sidorin added a comment. Hi Gabor, Could you provide some tests for the issue? Repository: rC Clang https://reviews.llvm.org/D49300 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D49300: [ASTImporter] Fix poisonous structural equivalence cache
martong created this revision.
martong added reviewers: a.sidorin, a_sidorin, r.stahl.
Herald added subscribers: cfe-commits, dkrupp, rnkovacs.
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.
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
@@ -67,7 +67,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 t) {
Index: lib/Sema/SemaType.cpp
===
--- lib/Sema/SemaType.cpp
+++ lib/Sema/SemaType.cpp
@@ -7540,7 +7540,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
@@ -184,18 +184,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?
@@ -1191,8 +1191,8 @@
return false;
}
-if (!Context.IsStructurallyEquivalent(Params1->getParam(I),
- Params2->getParam(I)))
+if (!IsStructurallyEquivalent(Context, Params1->getParam(I),
+ Params2->getParam(I)))
return false;
}
@@ -1229,7 +1229,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)
@@ -1280,8 +1280,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 ,
@@ -1292,8 +1292,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 ,
@@ -1404,16 +1404,26 @@
return Index;
}
-bool StructuralEquivalenceContext::IsStructurallyEquivalent(Decl *D1,
-Decl *D2) {
+bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) {
+
+ //
