From dcb910b1cfbb9839e67b94d67da6c9b7ab3a63ff Mon Sep 17 00:00:00 2001 From: Manuel Klimek Date: Wed, 3 Aug 2016 14:12:17 +0000 Subject: [PATCH] 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 --- clang/lib/Tooling/Core/Replacement.cpp | 66 +++++++++++++++++++++-------- clang/unittests/Tooling/RefactoringTest.cpp | 42 ++++++++++++++++++ 2 files changed, 90 insertions(+), 18 deletions(-) diff --git a/clang/lib/Tooling/Core/Replacement.cpp b/clang/lib/Tooling/Core/Replacement.cpp index 5e22f57..b990ed2 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( - "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 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( + "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 6fbb328..b06123e 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"); -- 2.7.4