Fix quadratic runtime when adding items to tooling::Replacements.
Previously, we would search through all replacements when inserting a
new one to check for overlaps. Instead, make use of the fact that we
already have a set of replacments without overlaps to find the potential
overlap with lower_bound.
Differential Revision: https://reviews.llvm.org/D23119
llvm-svn: 277597
diff --git a/clang/unittests/Tooling/RefactoringTest.cpp b/clang/unittests/Tooling/RefactoringTest.cpp
index 6fbb328..b06123e 100644
--- a/clang/unittests/Tooling/RefactoringTest.cpp
+++ b/clang/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");