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

2 files changed, 90 insertions, 18 deletions

diff --git a/clang/lib/Tooling/Core/Replacement.cpp b/clang/lib/Tooling/Core/Replacement.cpp
index 5e22f57347a..b990ed2083a 100644
--- a/clang/lib/Tooling/Core/Replacement.cpp
+++ b/clang/lib/Tooling/Core/Replacement.cpp
@@ -138,25 +138,55 @@ void Replacement::setFromSourceRange(const SourceManager &Sources,
 }
 
 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 {
diff --git a/clang/unittests/Tooling/RefactoringTest.cpp b/clang/unittests/Tooling/RefactoringTest.cpp
index 6fbb328732d..b06123ed62d 100644
--- a/clang/unittests/Tooling/RefactoringTest.cpp
+++ b/clang/unittests/Tooling/RefactoringTest.cpp
@@ -115,6 +115,48 @@ TEST_F(ReplacementTest, FailAddReplacements) {
   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");