Author: klimek Date: Wed Aug 3 09:12:17 2016 New Revision: 277597 URL: http://llvm.org/viewvc/llvm-project?rev=277597&view=rev Log: 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 Modified: cfe/trunk/lib/Tooling/Core/Replacement.cpp cfe/trunk/unittests/Tooling/RefactoringTest.cpp Modified: cfe/trunk/lib/Tooling/Core/Replacement.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Tooling/Core/Replacement.cpp?rev=277597&r1=277596&r2=277597&view=diff ============================================================================== --- cfe/trunk/lib/Tooling/Core/Replacement.cpp (original) +++ cfe/trunk/lib/Tooling/Core/Replacement.cpp Wed Aug 3 09:12:17 2016 @@ -138,25 +138,55 @@ void Replacement::setFromSourceRange(con } 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()); - Replaces.insert(R); - return llvm::Error::success(); + // 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 { Modified: cfe/trunk/unittests/Tooling/RefactoringTest.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/unittests/Tooling/RefactoringTest.cpp?rev=277597&r1=277596&r2=277597&view=diff ============================================================================== --- cfe/trunk/unittests/Tooling/RefactoringTest.cpp (original) +++ cfe/trunk/unittests/Tooling/RefactoringTest.cpp Wed Aug 3 09:12:17 2016 @@ -115,6 +115,48 @@ TEST_F(ReplacementTest, FailAddReplaceme 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"); _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
