Index: lib/Tooling/Core/Replacement.cpp =================================================================== --- lib/Tooling/Core/Replacement.cpp +++ 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( - "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( - "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( + "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 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( + "New replacement:\n" + R.toString() + + "\nconflicts with existing replacement:\n" + I->toString(), + llvm::inconvertibleErrorCode()); } namespace { Index: unittests/Tooling/RefactoringTest.cpp =================================================================== --- unittests/Tooling/RefactoringTest.cpp +++ 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");