This revision was automatically updated to reflect the committed changes.
Closed by commit rL277597: Fix quadratic runtime when adding items to
tooling::Replacements. (authored by klimek).
Changed prior to commit:
https://reviews.llvm.org/D23119?vs=66661&id=66663#toc
Repository:
rL LLVM
https://reviews.llvm.org/D23119
Files:
cfe/trunk/lib/Tooling/Core/Replacement.cpp
cfe/trunk/unittests/Tooling/RefactoringTest.cpp
Index: cfe/trunk/lib/Tooling/Core/Replacement.cpp
===================================================================
--- cfe/trunk/lib/Tooling/Core/Replacement.cpp
+++ cfe/trunk/lib/Tooling/Core/Replacement.cpp
@@ -138,25 +138,55 @@
}
llvm::Error Replacements::add(const Replacement &R) {
- if (R.getOffset() != UINT_MAX)
- for (auto Replace : Replaces) {
- if (R.getFilePath() != Replace.getFilePath())
- return llvm::make_error<llvm::StringError>(
- "All replacements must have the same file path. New replacement: " +
- R.getFilePath() + ", existing replacements: " +
- Replace.getFilePath() + "\n",
- llvm::inconvertibleErrorCode());
- if (R.getOffset() == Replace.getOffset() ||
- Range(R.getOffset(), R.getLength())
- .overlapsWith(Range(Replace.getOffset(), Replace.getLength())))
- return llvm::make_error<llvm::StringError>(
- "New replacement:\n" + R.toString() +
- "\nconflicts with existing replacement:\n" + Replace.toString(),
- llvm::inconvertibleErrorCode());
- }
+ // Check the file path.
+ if (!Replaces.empty() && R.getFilePath() != Replaces.begin()->getFilePath())
+ return llvm::make_error<llvm::StringError>(
+ "All replacements must have the same file path. New replacement: " +
+ R.getFilePath() + ", existing replacements: " +
+ Replaces.begin()->getFilePath() + "\n",
+ llvm::inconvertibleErrorCode());
+
+ // Special-case header insertions.
+ if (R.getOffset() == UINT_MAX) {
+ Replaces.insert(R);
+ return llvm::Error::success();
+ }
- Replaces.insert(R);
- return llvm::Error::success();
+ // This replacement cannot conflict with replacements that end before
+ // this replacement starts or start after this replacement ends.
+ // We also know that there currently are no overlapping replacements.
+ // Thus, we know that all replacements that start after the end of the current
+ // replacement cannot overlap.
+ Replacement AtEnd(R.getFilePath(), R.getOffset() + R.getLength(), 0, "");
+
+ // Find the first entry that starts after the end of R.
+ // We cannot use upper_bound for that, as there might be an element equal to
+ // AtEnd in Replaces, and AtEnd does not overlap.
+ // Instead, we use lower_bound and special-case finding AtEnd below.
+ auto I = Replaces.lower_bound(AtEnd);
+ // If *I == R (which can only happen if R == AtEnd) the first entry that
+ // starts after R is (I+1).
+ if (I != Replaces.end() && *I == R)
+ ++I;
+ // I is the smallest iterator whose entry cannot overlap.
+ // If that is begin(), there are no overlaps.
+ if (I == Replaces.begin()) {
+ Replaces.insert(R);
+ return llvm::Error::success();
+ }
+ --I;
+ // If the previous entry does not overlap, we know that entries before it
+ // can also not overlap.
+ if (R.getOffset() != I->getOffset() &&
+ !Range(R.getOffset(), R.getLength())
+ .overlapsWith(Range(I->getOffset(), I->getLength()))) {
+ Replaces.insert(R);
+ return llvm::Error::success();
+ }
+ return llvm::make_error<llvm::StringError>(
+ "New replacement:\n" + R.toString() +
+ "\nconflicts with existing replacement:\n" + I->toString(),
+ llvm::inconvertibleErrorCode());
}
namespace {
Index: cfe/trunk/unittests/Tooling/RefactoringTest.cpp
===================================================================
--- cfe/trunk/unittests/Tooling/RefactoringTest.cpp
+++ cfe/trunk/unittests/Tooling/RefactoringTest.cpp
@@ -115,6 +115,48 @@
llvm::consumeError(std::move(Err));
}
+TEST_F(ReplacementTest, FailAddOverlappingInsertions) {
+ Replacements Replaces;
+ // Test adding an insertion at the offset of an existing replacement.
+ auto Err = Replaces.add(Replacement("x.cc", 10, 3, "replace"));
+ EXPECT_TRUE(!Err);
+ llvm::consumeError(std::move(Err));
+ Err = Replaces.add(Replacement("x.cc", 10, 0, "insert"));
+ EXPECT_TRUE((bool)Err);
+ llvm::consumeError(std::move(Err));
+
+ Replaces.clear();
+ // Test overlap with an existing insertion.
+ Err = Replaces.add(Replacement("x.cc", 10, 0, "insert"));
+ EXPECT_TRUE(!Err);
+ llvm::consumeError(std::move(Err));
+ Err = Replaces.add(Replacement("x.cc", 10, 3, "replace"));
+ EXPECT_TRUE((bool)Err);
+ llvm::consumeError(std::move(Err));
+}
+
+TEST_F(ReplacementTest, FailAddRegression) {
+ Replacements Replaces;
+ // Create two replacements, where the second one is an insertion of the empty
+ // string exactly at the end of the first one.
+ auto Err = Replaces.add(Replacement("x.cc", 0, 10, "1"));
+ EXPECT_TRUE(!Err);
+ llvm::consumeError(std::move(Err));
+ Err = Replaces.add(Replacement("x.cc", 10, 0, ""));
+ EXPECT_TRUE(!Err);
+ llvm::consumeError(std::move(Err));
+
+ // Make sure we find the overlap with the first entry when inserting a
+ // replacement that ends exactly at the seam of the existing replacements.
+ Err = Replaces.add(Replacement("x.cc", 5, 5, "fail"));
+ EXPECT_TRUE((bool)Err);
+ llvm::consumeError(std::move(Err));
+
+ Err = Replaces.add(Replacement("x.cc", 10, 0, ""));
+ EXPECT_TRUE((bool)Err);
+ llvm::consumeError(std::move(Err));
+}
+
TEST_F(ReplacementTest, CanApplyReplacements) {
FileID ID = Context.createInMemoryFile("input.cpp",
"line1\nline2\nline3\nline4");
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
