martong created this revision.
martong added a reviewer: a_sidorin.
Herald added subscribers: cfe-commits, gamesh411, Szelethus, dkrupp, rnkovacs.
Herald added a reviewer: a.sidorin.
Herald added a reviewer: shafik.
Herald added a project: clang.
During import of a specific Decl D, it may happen that some AST nodes
had already been created before we recognize an error. In this case we
signal back the error to the caller, but the "to" context remains
polluted with those nodes which had been created. Ideally, those nodes
should not had been created, but that time we did not know about the
error, the error happened later. Since the AST is immutable (most of
the cases we can't remove existing nodes) we choose to mark these nodes
as erroneous.
Here are the steps of the algorithm:
1. We keep track of the nodes which we visit during the import of D: See
ImportPathTy.
2. If a Decl is already imported and it is already on the import path
(we have a cycle) then we copy/store the relevant part of the import
path. We store these cycles for each Decl.
3. When we recognize an error during the import of D then we set up this
error to all Decls in the stored cycles for D and we clear the stored
cycles.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D62375
Files:
clang/include/clang/AST/ASTImporter.h
clang/lib/AST/ASTImporter.cpp
clang/unittests/AST/ASTImporterTest.cpp
Index: clang/unittests/AST/ASTImporterTest.cpp
===================================================================
--- clang/unittests/AST/ASTImporterTest.cpp
+++ clang/unittests/AST/ASTImporterTest.cpp
@@ -358,6 +358,106 @@
EXPECT_EQ(0U, count);
}
+struct ImportPath : ASTImporterOptionSpecificTestBase {
+ Decl *FromTU;
+ FunctionDecl *D0, *D1, *D2;
+ ImportPath() {
+ FromTU = getTuDecl("void f(); void f(); void f();", Lang_CXX);
+ auto Pattern = functionDecl(hasName("f"));
+ D0 = FirstDeclMatcher<FunctionDecl>().match(FromTU, Pattern);
+ D2 = LastDeclMatcher<FunctionDecl>().match(FromTU, Pattern);
+ D1 = D2->getPreviousDecl();
+ }
+};
+
+TEST_P(ImportPath, Push) {
+ ASTImporter::ImportPathTy path;
+ path.push(D0);
+ EXPECT_FALSE(path.hasCycleAtBack());
+}
+
+TEST_P(ImportPath, SmallCycle) {
+ ASTImporter::ImportPathTy path;
+ path.push(D0);
+ path.push(D0);
+ EXPECT_TRUE(path.hasCycleAtBack());
+ path.pop();
+ EXPECT_FALSE(path.hasCycleAtBack());
+ path.push(D0);
+ EXPECT_TRUE(path.hasCycleAtBack());
+}
+
+TEST_P(ImportPath, GetSmallCycle) {
+ ASTImporter::ImportPathTy path;
+ path.push(D0);
+ path.push(D0);
+ EXPECT_TRUE(path.hasCycleAtBack());
+ std::array<Decl* ,2> Res;
+ int i = 0;
+ for (Decl *Di : path.getCycleAtBack()) {
+ Res[i++] = Di;
+ }
+ ASSERT_EQ(i, 2);
+ EXPECT_EQ(Res[0], D0);
+ EXPECT_EQ(Res[1], D0);
+}
+
+TEST_P(ImportPath, GetCycle) {
+ ASTImporter::ImportPathTy path;
+ path.push(D0);
+ path.push(D1);
+ path.push(D2);
+ path.push(D0);
+ EXPECT_TRUE(path.hasCycleAtBack());
+ std::array<Decl* ,4> Res;
+ int i = 0;
+ for (Decl *Di : path.getCycleAtBack()) {
+ Res[i++] = Di;
+ }
+ ASSERT_EQ(i, 4);
+ EXPECT_EQ(Res[0], D0);
+ EXPECT_EQ(Res[1], D2);
+ EXPECT_EQ(Res[2], D1);
+ EXPECT_EQ(Res[3], D0);
+}
+
+TEST_P(ImportPath, CycleAfterCycle) {
+ ASTImporter::ImportPathTy path;
+ path.push(D0);
+ path.push(D1);
+ path.push(D0);
+ path.push(D1);
+ path.push(D2);
+ path.push(D0);
+ EXPECT_TRUE(path.hasCycleAtBack());
+ std::array<Decl* ,4> Res;
+ int i = 0;
+ for (Decl *Di : path.getCycleAtBack()) {
+ Res[i++] = Di;
+ }
+ ASSERT_EQ(i, 4);
+ EXPECT_EQ(Res[0], D0);
+ EXPECT_EQ(Res[1], D2);
+ EXPECT_EQ(Res[2], D1);
+ EXPECT_EQ(Res[3], D0);
+
+ path.pop();
+ path.pop();
+ path.pop();
+ EXPECT_TRUE(path.hasCycleAtBack());
+ i = 0;
+ for (Decl *Di : path.getCycleAtBack()) {
+ Res[i++] = Di;
+ }
+ ASSERT_EQ(i, 3);
+ EXPECT_EQ(Res[0], D0);
+ EXPECT_EQ(Res[1], D1);
+ EXPECT_EQ(Res[2], D0);
+
+ path.pop();
+ EXPECT_FALSE(path.hasCycleAtBack());
+}
+
TEST_P(ImportExpr, ImportStringLiteral) {
MatchVerifier<Decl> Verifier;
testImport(
@@ -4501,12 +4601,6 @@
EXPECT_EQ(*Res.begin(), A);
}
-INSTANTIATE_TEST_CASE_P(ParameterizedTests, DeclContextTest,
- ::testing::Values(ArgVector()), );
-
-INSTANTIATE_TEST_CASE_P(
- ParameterizedTests, CanonicalRedeclChain,
- ::testing::Values(ArgVector()),);
// FIXME This test is disabled currently, upcoming patches will make it
// possible to enable.
@@ -4574,9 +4668,18 @@
EXPECT_EQ(Imported->getPreviousDecl(), Friend);
}
+INSTANTIATE_TEST_CASE_P(ParameterizedTests, DeclContextTest,
+ ::testing::Values(ArgVector()), );
+
+INSTANTIATE_TEST_CASE_P(ParameterizedTests, CanonicalRedeclChain,
+ ::testing::Values(ArgVector()), );
+
INSTANTIATE_TEST_CASE_P(ParameterizedTests, ASTImporterLookupTableTest,
DefaultTestValuesForRunOptions, );
+INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportPath,
+ ::testing::Values(ArgVector()), );
+
INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportExpr,
DefaultTestValuesForRunOptions, );
Index: clang/lib/AST/ASTImporter.cpp
===================================================================
--- clang/lib/AST/ASTImporter.cpp
+++ clang/lib/AST/ASTImporter.cpp
@@ -7796,10 +7796,23 @@
return FromDPos->second->getTranslationUnitDecl();
}
+// RAII class to maintain the import path.
+class ImportPathBuilder {
+ ASTImporter::ImportPathTy &Path;
+
+public:
+ ImportPathBuilder(ASTImporter::ImportPathTy &Path, Decl *FromD) : Path(Path) {
+ Path.push(FromD);
+ };
+ ~ImportPathBuilder() { Path.pop(); }
+};
+
Expected<Decl *> ASTImporter::Import(Decl *FromD) {
if (!FromD)
return nullptr;
+ // Push FromD to the stack, and remove that when we return.
+ ImportPathBuilder PathRAII(ImportPath, FromD);
// Check whether there was a previous failed import.
// If yes return the existing error.
@@ -7811,6 +7824,10 @@
if (ToD) {
// If FromD has some updated flags after last import, apply it
updateFlags(FromD, ToD);
+ // If we encounter a cycle during an import then we save the relevant part
+ // of the import path associated to the Decl.
+ if (ImportPath.hasCycleAtBack())
+ SavedImportPaths[FromD].push_back(ImportPath.copyCycleAtBack());
return ToD;
}
@@ -7855,6 +7872,14 @@
handleAllErrors(ToDOrErr.takeError(),
[&ErrOut](const ImportError &E) { ErrOut = E; });
setImportDeclError(FromD, ErrOut);
+
+ // Set the error for all nodes which have been created before we
+ // recognized the error.
+ for (const auto &Path : SavedImportPaths[FromD])
+ for (Decl *Di : Path)
+ setImportDeclError(Di, ErrOut);
+ SavedImportPaths[FromD].clear();
+
// Do not return ToDOrErr, error was taken out of it.
return make_error<ImportError>(ErrOut);
}
@@ -7879,6 +7904,7 @@
Imported(FromD, ToD);
updateFlags(FromD, ToD);
+ SavedImportPaths[FromD].clear();
return ToDOrErr;
}
@@ -8599,8 +8625,6 @@
}
void ASTImporter::setImportDeclError(Decl *From, ImportError Error) {
- assert(ImportDeclErrors.find(From) == ImportDeclErrors.end() &&
- "Setting import error allowed only once for a Decl.");
ImportDeclErrors[From] = Error;
}
@@ -8622,3 +8646,38 @@
Complain);
return Ctx.IsEquivalent(From, To);
}
+
+void ASTImporter::ImportPathTy::push(Decl *D) {
+ Nodes.push_back(D);
+ ++Aux[D];
+}
+
+void ASTImporter::ImportPathTy::pop() {
+ if (Nodes.empty())
+ return;
+ --Aux[Nodes.back()];
+ Nodes.pop_back();
+}
+
+Decl *ASTImporter::ImportPathTy::top() const {
+ if (!Nodes.empty())
+ return Nodes.back();
+ return nullptr;
+}
+
+bool ASTImporter::ImportPathTy::hasCycleAtBack() {
+ return Aux[Nodes.back()] > 1;
+}
+
+ASTImporter::ImportPathTy::Cycle
+ASTImporter::ImportPathTy::getCycleAtBack() const {
+ assert(Nodes.size() >= 2);
+ return Cycle(Nodes.rbegin(),
+ std::find(Nodes.rbegin() + 1, Nodes.rend(), Nodes.back()) + 1);
+}
+
+ASTImporter::ImportPathTy::VecTy
+ASTImporter::ImportPathTy::copyCycleAtBack() const {
+ auto R = getCycleAtBack();
+ return VecTy(R.begin(), R.end());
+}
Index: clang/include/clang/AST/ASTImporter.h
===================================================================
--- clang/include/clang/AST/ASTImporter.h
+++ clang/include/clang/AST/ASTImporter.h
@@ -26,6 +26,7 @@
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Support/Error.h"
#include <utility>
@@ -87,6 +88,30 @@
using ImportedCXXBaseSpecifierMap =
llvm::DenseMap<const CXXBaseSpecifier *, CXXBaseSpecifier *>;
+ class ImportPathTy {
+ public:
+ using VecTy = llvm::SmallVector<Decl *, 32>;
+
+ void push(Decl *D);
+ void pop();
+ Decl *top() const;
+
+ /// Returns true if the last element can be found earlier in the path.
+ bool hasCycleAtBack();
+ using Cycle = llvm::iterator_range<VecTy::const_reverse_iterator>;
+ Cycle getCycleAtBack() const;
+ /// Returns the copy of the cycle.
+ VecTy copyCycleAtBack() const;
+
+ private:
+ // All the nodes of the path.
+ VecTy Nodes;
+ // Auxiliary container to be able to answer "Do we have a cycle ending
+ // at last element?" as fast as possible.
+ // We count each Decl's occurrence over the path.
+ llvm::SmallDenseMap<Decl *, int, 32> Aux;
+ };
+
private:
/// Pointer to the import specific lookup table, which may be shared
@@ -96,6 +121,17 @@
/// If not set then the original C/C++ lookup is used.
ASTImporterLookupTable *LookupTable = nullptr;
+ /// The path which we go through during the import of a given AST node.
+ ImportPathTy ImportPath;
+ /// Sometimes we have to save some part of an import path, so later we can
+ /// set up properties to the saved nodes.
+ /// We may have several of these import paths associated to one Decl.
+ using SavedImportPathsForOneDecl =
+ llvm::SmallVector<ImportPathTy::VecTy, 32>;
+ using SavedImportPathsTy =
+ llvm::SmallDenseMap<Decl *, SavedImportPathsForOneDecl, 32>;
+ SavedImportPathsTy SavedImportPaths;
+
/// The contexts we're importing to and from.
ASTContext &ToContext, &FromContext;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
