Index: include/clang/Tooling/Core/Replacement.h =================================================================== --- include/clang/Tooling/Core/Replacement.h +++ include/clang/Tooling/Core/Replacement.h @@ -64,6 +64,12 @@ unsigned Length; }; +/// \brief Less-than operator between two Ranges. +bool operator<(const Range &LHS, const Range &RHS); + +/// \brief Equal-to operator between two Ranges. +bool operator==(const Range &LHS, const Range &RHS); + /// \brief A text replacement. /// /// Represents a SourceManager independent replacement of a range of text in a @@ -227,6 +233,18 @@ /// \pre Replacements must be for the same file. std::vector calculateChangedRanges(const Replacements &Replaces); +/// \brief Calculates the new ranges after \p Replaces are applied. These +/// include both the original \p Ranges and the affected ranges of \p Replaces +/// in the new code. +/// +/// \pre Replacemments must be for the same file. +/// +/// \return The new ranges after \p Replaces are applied. The new ranges will be +/// sorted and non-overlapping. +std::vector +calculateRangesAfterReplacements(const Replacements &Replaces, + std::vector Ranges); + /// \brief Groups a random set of replacements by file path. Replacements /// related to the same file entry are put into the same vector. std::map Index: lib/Tooling/Core/Replacement.cpp =================================================================== --- lib/Tooling/Core/Replacement.cpp +++ lib/Tooling/Core/Replacement.cpp @@ -29,6 +29,17 @@ static const char * const InvalidLocation = ""; +bool operator<(const Range &LHS, const Range &RHS) { + if (LHS.getOffset() != RHS.getOffset()) + return LHS.getOffset() < RHS.getOffset(); + return LHS.getLength() < LHS.getLength(); +} + +bool operator==(const Range &LHS, const Range &RHS) { + return (LHS.getOffset() == RHS.getOffset()) && + (LHS.getLength() == RHS.getLength()); +} + Replacement::Replacement() : FilePath(InvalidLocation) {} @@ -290,6 +301,96 @@ return ChangedRanges; } +// Merge and sort overlapping and adjacent ranges in \p Ranges. +static void mergeAndSortRanges(std::vector &Ranges) { + if (Ranges.empty()) + return; + std::vector Result; + std::sort(Ranges.begin(), Ranges.end()); + auto I = Ranges.begin(); + unsigned CurBegin = I->getOffset(); + unsigned CurEnd = CurBegin + I->getLength(); + ++I; + for (auto E = Ranges.end(); I != E; ++I) { + if (CurEnd < I->getOffset()) { + Result.emplace_back(CurBegin, CurEnd - CurBegin); + CurBegin = I->getOffset(); + CurEnd = CurBegin + I->getLength(); + continue; + } + CurEnd = std::max(CurEnd, I->getOffset() + I->getLength()); + } + Result.emplace_back(CurBegin, CurEnd - CurBegin); + Ranges = Result; +} + +std::vector +calculateRangesAfterReplacements(const Replacements &Replaces, + std::vector Ranges) { + if (Ranges.empty()) { + Ranges = calculateChangedRanges(Replaces); + mergeAndSortRanges(Ranges); + return Ranges; + } + + // Merge and sort adjacent ranges so that we can assume that ranges are sorted + // and non-overlapping in the future processing. + mergeAndSortRanges(Ranges); + if (Replaces.empty()) + return Ranges; + std::stack RangeStack; + for (auto I = Ranges.rbegin(), E = Ranges.rend(); I != E; ++I) + RangeStack.push(*I); + int Offset = 0; + std::vector Result; + for (const auto &R : Replaces) { + Result.emplace_back(R.getOffset() + Offset, R.getReplacementText().size()); + unsigned RBegin = R.getOffset(); + // Handle only ranges before or intercepted with the affected range of R. + while (!RangeStack.empty() && + RangeStack.top().getOffset() < RBegin + R.getLength()) { + auto CurrentRange = RangeStack.top(); + RangeStack.pop(); + unsigned CurBegin = CurrentRange.getOffset(); + unsigned CurEnd = CurBegin + CurrentRange.getLength(); + if (CurEnd < RBegin) { + Result.emplace_back(CurBegin + Offset, CurrentRange.getLength()); + continue; + } + // CurEnd >= RBegin starting from here. + if (CurBegin <= RBegin) { + // Truncate the part before R if the part is longer than 0. + Result.emplace_back(CurBegin + Offset, RBegin - CurBegin); + // If the current range also ends after R, push the part after R back to + // the stack and skip this replacement since there is no more range + // before or overlapped with it. + if (CurEnd > RBegin + R.getLength()) { + RangeStack.emplace(RBegin + R.getLength(), + CurEnd - RBegin - R.getLength()); + break; + } + continue; + } + // CurBegin > RBegin and CurBegin < RBegin + R.Length() starting from + // here. + // Truncate the part of CurrentRange after R and make it a separate range. + if (CurEnd > RBegin + R.getLength()) + RangeStack.emplace(RBegin + R.getLength(), + CurEnd - RBegin - R.getLength()); + } + Offset += R.getReplacementText().size() - R.getLength(); + } + + while (!RangeStack.empty()) { + Result.emplace_back(RangeStack.top().getOffset() + Offset, + RangeStack.top().getLength()); + RangeStack.pop(); + } + + mergeAndSortRanges(Result); + return Result; +} + namespace { // Represents a merged replacement, i.e. a replacement consisting of multiple // overlapping replacements from 'First' and 'Second' in mergeReplacements. @@ -434,4 +535,3 @@ } // end namespace tooling } // end namespace clang - Index: unittests/Tooling/RefactoringTest.cpp =================================================================== --- unittests/Tooling/RefactoringTest.cpp +++ unittests/Tooling/RefactoringTest.cpp @@ -471,6 +471,91 @@ EXPECT_TRUE(Ranges[2].getLength() == 16); } +TEST(Range, RangesAfterReplacements) { + std::vector Ranges = {Range(5, 2), Range(10, 5)}; + Replacements Replaces = {Replacement("foo", 0, 2, "1234")}; + std::vector Expected = {Range(0, 4), Range(7, 2), Range(12, 5)}; + EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges)); +} + +TEST(Range, RangesBeforeReplacements) { + std::vector Ranges = {Range(5, 2), Range(10, 5)}; + Replacements Replaces = {Replacement("foo", 20, 2, "1234")}; + std::vector Expected = {Range(5, 2), Range(10, 5), Range(20, 4)}; + EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges)); +} + +TEST(Range, NotAffectedByReplacements) { + std::vector Ranges = {Range(0, 2), Range(5, 2), Range(10, 5)}; + Replacements Replaces = {Replacement("foo", 3, 2, "12"), + Replacement("foo", 12, 2, "12"), + Replacement("foo", 20, 5, "")}; + std::vector Expected = {Range(0, 2), Range(3, 4), Range(10, 5), + Range(20, 0)}; + EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges)); +} + +TEST(Range, RangesWithNonOverlappingReplacements) { + std::vector Ranges = {Range(0, 2), Range(5, 2), Range(10, 5)}; + Replacements Replaces = {Replacement("foo", 3, 1, ""), + Replacement("foo", 6, 1, "123"), + Replacement("foo", 20, 2, "12345")}; + std::vector Expected = {Range(0, 2), Range(3, 0), Range(4, 4), + Range(11, 5), Range(21, 5)}; + EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges)); +} + +TEST(Range, RangesWithOverlappingReplacements) { + std::vector Ranges = {Range(0, 2), Range(5, 2), Range(15, 5), + Range(30, 5)}; + Replacements Replaces = { + Replacement("foo", 1, 3, ""), Replacement("foo", 6, 1, "123"), + Replacement("foo", 13, 3, "1"), Replacement("foo", 25, 15, "")}; + std::vector Expected = {Range(0, 1), Range(2, 4), Range(12, 5), + Range(22, 0)}; + EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges)); +} + +TEST(Range, MergeIntoOneRange) { + std::vector Ranges = {Range(0, 2), Range(5, 2), Range(15, 5)}; + Replacements Replaces = {Replacement("foo", 1, 15, "1234567890")}; + std::vector Expected = {Range(0, 15)}; + EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges)); +} + +TEST(Range, ReplacementsStartingAtRangeOffsets) { + std::vector Ranges = {Range(0, 2), Range(5, 5), Range(15, 5)}; + Replacements Replaces = { + Replacement("foo", 0, 2, "12"), Replacement("foo", 5, 1, "123"), + Replacement("foo", 7, 4, "12345"), Replacement("foo", 15, 10, "12")}; + std::vector Expected = {Range(0, 2), Range(5, 9), Range(18, 2)}; + EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges)); +} + +TEST(Range, ReplacementsEndingAtRangeEnds) { + std::vector Ranges = {Range(0, 2), Range(5, 2), Range(15, 5)}; + Replacements Replaces = {Replacement("foo", 6, 1, "123"), + Replacement("foo", 17, 3, "12")}; + std::vector Expected = {Range(0, 2), Range(5, 4), Range(17, 4)}; + EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges)); +} + +TEST(Range, AjacentReplacements) { + std::vector Ranges = {Range(0, 0), Range(15, 5)}; + Replacements Replaces = {Replacement("foo", 1, 2, "123"), + Replacement("foo", 12, 3, "1234")}; + std::vector Expected = {Range(0, 0), Range(1, 3), Range(13, 9)}; + EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges)); +} + +TEST(Range, MergeRangesAfterReplacements) { + std::vector Ranges = {Range(8, 0), Range(5, 2), Range(9, 0), Range(0, 1)}; + Replacements Replaces = {Replacement("foo", 1, 3, ""), + Replacement("foo", 7, 0, "12"), Replacement("foo", 9, 2, "")}; + std::vector Expected = {Range(0, 1), Range(2, 4), Range(7, 0), Range(8, 0)}; + EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges)); +} + TEST(DeduplicateTest, removesDuplicates) { std::vector Input; Input.push_back(Replacement("fileA", 50, 0, " foo "));