Fix quadratic runtime when adding items to tooling::Replacements.

[klimek]

Remove re-implementation of overlaps check.

[klimek]

Fix bugs around marker replacements that neither insert nor delete anything.

[akuegel]

lg

lib/Tooling/Core/Replacement.cpp

163 ↗

(On Diff #66661)

nit: "as there might an" -> "as there might be an".

[ioeric]

cfe/trunk/lib/Tooling/Core/Replacement.cpp

169

I think we should ignore replacement text when checking equality between *I and R here.

[klimek]

cfe/trunk/lib/Tooling/Core/Replacement.cpp

169

lower_bound already compares the replacement text, so as the comment says, unless I'm mistaken, this can only happen if R == AtEnd, which means that R has an empty replacement text.
Can you come up with a test that would break?

cfe/trunk/lib/Tooling/Core/Replacement.cpp

void Replacement::setFromSourceRange(const SourceManager &Sources,
                                      StringRef ReplacementText,
                                      const LangOptions &LangOpts) {
   setFromSourceLocation(Sources, Sources.getSpellingLoc(Range.getBegin()),
                         getRangeSize(Sources, Range, LangOpts),
                         ReplacementText);
 }
 
 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())
+            Replaces.begin()->getFilePath() + "\n",
+
+  // Special-case header insertions.
+  if (R.getOffset() == UINT_MAX) {
+    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 {
 
 // Represents a merged replacement, i.e. a replacement consisting of multiple
 // overlapping replacements from 'First' and 'Second' in mergeReplacements.
 //
 // Position projection:
 // Offsets and lengths of the replacements can generally refer to two different

cfe/trunk/unittests/Tooling/RefactoringTest.cpp

TEST_F(ReplacementTest, FailAddReplacements) {
   Err = Replaces.add(Replacement("x.cc", 2, 2, ""));
   EXPECT_TRUE((bool)Err);
   llvm::consumeError(std::move(Err));
   Err = Replaces.add(Replacement("y.cc", 20, 2, ""));
   EXPECT_TRUE((bool)Err);
   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");
   Replacements Replaces =
       toReplacements({Replacement(Context.Sources,
                                   Context.getLocation(ID, 2, 1), 5, "replaced"),
                       Replacement(Context.Sources,
                                   Context.getLocation(ID, 3, 1), 5, "other")});