From 7fc60d9e117f4e7f3767089067d3e947f76801ae Mon Sep 17 00:00:00 2001 From: Eric Liu Date: Wed, 28 Sep 2016 11:02:16 +0000 Subject: [PATCH] Merge conflicting replacements when they are order-independent. Summary: Now two replacements are considered order-independent if applying them in either order produces the same result. These include (but not restricted to) replacements that: - don't overlap (being directly adjacent is fine) and - are overlapping deletions. - are insertions at the same offset and applying them in either order has the same effect, i.e. X + Y = Y + X if one inserts text X and the other inserts text Y. Discussion about this design can be found in D24717 Reviewers: djasper, klimek Subscribers: omtcyfz, cfe-commits Differential Revision: https://reviews.llvm.org/D24800 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@282577 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/Tooling/Core/Replacement.h | 37 ++++- lib/Tooling/Core/Replacement.cpp | 107 ++++++++++++- unittests/Tooling/RefactoringTest.cpp | 192 +++++++++++++++++++++-- 3 files changed, 313 insertions(+), 23 deletions(-) diff --git a/include/clang/Tooling/Core/Replacement.h b/include/clang/Tooling/Core/Replacement.h index f7c32193c4..82f1716e60 100644 --- a/include/clang/Tooling/Core/Replacement.h +++ b/include/clang/Tooling/Core/Replacement.h @@ -167,10 +167,25 @@ class Replacements { /// order-dependent replacements. To control the order in which /// order-dependent replacements are applied, use merge({R}) with R referring /// to the changed code after applying all existing replacements. - /// Two replacements are considered order-independent if they: + /// Two replacements A and B are considered order-independent if applying them + /// in either order produces the same result. Note that the range of the + /// replacement that is applied later still refers to the original code. + /// These include (but not restricted to) replacements that: /// - don't overlap (being directly adjacent is fine) and - /// - aren't both inserts at the same code location (would be - /// order-dependent). + /// - are overlapping deletions. + /// - are insertions at the same offset and applying them in either order + /// has the same effect, i.e. X + Y = Y + X when inserting X and Y + /// respectively. + /// Examples: + /// 1. Replacement A(0, 0, "a") and B(0, 0, "aa") are order-independent since + /// applying them in either order gives replacement (0, 0, "aaa"). + /// However, A(0, 0, "a") and B(0, 0, "b") are order-dependent since + /// applying A first gives (0, 0, "ab") while applying B first gives (B, A, + /// "ba"). + /// 2. Replacement A(0, 2, "123") and B(0, 2, "123") are order-independent + /// since applying them in either order gives (0, 2, "123"). + /// 3. Replacement A(0, 3, "123") and B(2, 3, "321") are order-independent + /// since either order gives (0, 5, "12321"). /// Replacements with offset UINT_MAX are special - we do not detect conflicts /// for such replacements since users may add them intentionally as a special /// category of replacements. @@ -213,6 +228,22 @@ private: Replacements mergeReplacements(const ReplacementsImpl &Second) const; + // Returns `R` with new range that refers to code after `Replaces` being + // applied. + Replacement getReplacementInChangedCode(const Replacement &R) const; + + // Returns a set of replacements that is equivalent to the current + // replacements by merging all adjacent replacements. Two sets of replacements + // are considered equivalent if they have the same effect when they are + // applied. + Replacements getCanonicalReplacements() const; + + // If `R` and all existing replacements are order-indepedent, then merge it + // with `Replaces` and returns the merged replacements; otherwise, returns an + // error. + llvm::Expected + mergeIfOrderIndependent(const Replacement &R) const; + ReplacementsImpl Replaces; }; diff --git a/lib/Tooling/Core/Replacement.cpp b/lib/Tooling/Core/Replacement.cpp index db5eea413d..918488310c 100644 --- a/lib/Tooling/Core/Replacement.cpp +++ b/lib/Tooling/Core/Replacement.cpp @@ -134,14 +134,75 @@ void Replacement::setFromSourceRange(const SourceManager &Sources, ReplacementText); } -llvm::Error makeConflictReplacementsError(const Replacement &New, - const Replacement &Existing) { +Replacement +Replacements::getReplacementInChangedCode(const Replacement &R) const { + unsigned NewStart = getShiftedCodePosition(R.getOffset()); + unsigned NewEnd = getShiftedCodePosition(R.getOffset() + R.getLength()); + return Replacement(R.getFilePath(), NewStart, NewEnd - NewStart, + R.getReplacementText()); +} + +static llvm::Error makeConflictReplacementsError(const Replacement &New, + const Replacement &Existing) { return llvm::make_error( "New replacement:\n" + New.toString() + "\nconflicts with existing replacement:\n" + Existing.toString(), llvm::inconvertibleErrorCode()); } +Replacements Replacements::getCanonicalReplacements() const { + std::vector NewReplaces; + // Merge adjacent replacements. + for (const auto &R : Replaces) { + if (NewReplaces.empty()) { + NewReplaces.push_back(R); + continue; + } + auto &Prev = NewReplaces.back(); + unsigned PrevEnd = Prev.getOffset() + Prev.getLength(); + if (PrevEnd < R.getOffset()) { + NewReplaces.push_back(R); + } else { + assert(PrevEnd == R.getOffset() && + "Existing replacements must not overlap."); + Replacement NewR( + R.getFilePath(), Prev.getOffset(), Prev.getLength() + R.getLength(), + (Prev.getReplacementText() + R.getReplacementText()).str()); + Prev = NewR; + } + } + ReplacementsImpl NewReplacesImpl(NewReplaces.begin(), NewReplaces.end()); + return Replacements(NewReplacesImpl.begin(), NewReplacesImpl.end()); +} + +// `R` and `Replaces` are order-independent if applying them in either order +// has the same effect, so we need to compare replacements associated to +// applying them in either order. +llvm::Expected +Replacements::mergeIfOrderIndependent(const Replacement &R) const { + Replacements Rs(R); + // A Replacements set containg a single replacement that is `R` referring to + // the code after the existing replacements `Replaces` are applied. + Replacements RsShiftedByReplaces(getReplacementInChangedCode(R)); + // A Replacements set that is `Replaces` referring to the code after `R` is + // applied. + Replacements ReplacesShiftedByRs; + for (const auto &Replace : Replaces) + ReplacesShiftedByRs.Replaces.insert( + Rs.getReplacementInChangedCode(Replace)); + // This is equivalent to applying `Replaces` first and then `R`. + auto MergeShiftedRs = merge(RsShiftedByReplaces); + // This is equivalent to applying `R` first and then `Replaces`. + auto MergeShiftedReplaces = Rs.merge(ReplacesShiftedByRs); + + // Since empty or segmented replacements around existing replacements might be + // produced above, we need to compare replacements in canonical forms. + if (MergeShiftedRs.getCanonicalReplacements() == + MergeShiftedReplaces.getCanonicalReplacements()) + return MergeShiftedRs; + return makeConflictReplacementsError(R, *Replaces.begin()); +} + llvm::Error Replacements::add(const Replacement &R) { // Check the file path. if (!Replaces.empty() && R.getFilePath() != Replaces.begin()->getFilePath()) @@ -172,8 +233,21 @@ llvm::Error Replacements::add(const Replacement &R) { if (I != Replaces.end() && R.getOffset() == I->getOffset()) { assert(R.getLength() == 0); // `I` is also an insertion, `R` and `I` conflict. - if (I->getLength() == 0) - return makeConflictReplacementsError(R, *I); + if (I->getLength() == 0) { + // Check if two insertions are order-indepedent: if inserting them in + // either order produces the same text, they are order-independent. + if ((R.getReplacementText() + I->getReplacementText()).str() != + (I->getReplacementText() + R.getReplacementText()).str()) { + return makeConflictReplacementsError(R, *I); + } + // If insertions are order-independent, we can merge them. + Replacement NewR( + R.getFilePath(), R.getOffset(), 0, + (R.getReplacementText() + I->getReplacementText()).str()); + Replaces.erase(I); + Replaces.insert(NewR); + return llvm::Error::success(); + } // Insertion `R` is adjacent to a non-insertion replacement `I`, so they // are order-independent. It is safe to assume that `R` will not conflict // with any replacement before `I` since all replacements before `I` must @@ -192,10 +266,13 @@ llvm::Error Replacements::add(const Replacement &R) { return llvm::Error::success(); } --I; + auto Overlap = [](const Replacement &R1, const Replacement &R2) -> bool { + return Range(R1.getOffset(), R1.getLength()) + .overlapsWith(Range(R2.getOffset(), R2.getLength())); + }; // If the previous entry does not overlap, we know that entries before it // can also not overlap. - if (!Range(R.getOffset(), R.getLength()) - .overlapsWith(Range(I->getOffset(), I->getLength()))) { + if (!Overlap(R, *I)) { // If `R` and `I` do not have the same offset, it is safe to add `R` since // it must come after `I`. Otherwise: // - If `R` is an insertion, `I` must not be an insertion since it would @@ -204,9 +281,23 @@ llvm::Error Replacements::add(const Replacement &R) { // and `I` would have overlapped. // In either case, we can safely insert `R`. Replaces.insert(R); - return llvm::Error::success(); + } else { + // `I` overlaps with `R`. We need to check `R` against all overlapping + // replacements to see if they are order-indepedent. If they are, merge `R` + // with them and replace them with the merged replacements. + auto MergeBegin = I; + auto MergeEnd = std::next(I); + while (I-- != Replaces.begin() && Overlap(R, *I)) + MergeBegin = I; + Replacements OverlapReplaces(MergeBegin, MergeEnd); + llvm::Expected Merged = + OverlapReplaces.mergeIfOrderIndependent(R); + if (!Merged) + return Merged.takeError(); + Replaces.erase(MergeBegin, MergeEnd); + Replaces.insert(Merged->begin(), Merged->end()); } - return makeConflictReplacementsError(R, *I); + return llvm::Error::success(); } namespace { diff --git a/unittests/Tooling/RefactoringTest.cpp b/unittests/Tooling/RefactoringTest.cpp index b4c269d1f1..0a70a112aa 100644 --- a/unittests/Tooling/RefactoringTest.cpp +++ b/unittests/Tooling/RefactoringTest.cpp @@ -101,18 +101,56 @@ TEST_F(ReplacementTest, ReturnsInvalidPath) { TEST_F(ReplacementTest, FailAddReplacements) { Replacements Replaces; - auto Err = Replaces.add(Replacement("x.cc", 0, 10, "3")); + Replacement Deletion("x.cc", 0, 10, "3"); + auto Err = Replaces.add(Deletion); EXPECT_TRUE(!Err); llvm::consumeError(std::move(Err)); - Err = Replaces.add(Replacement("x.cc", 0, 2, "")); + Err = Replaces.add(Replacement("x.cc", 0, 2, "a")); EXPECT_TRUE((bool)Err); llvm::consumeError(std::move(Err)); - Err = Replaces.add(Replacement("x.cc", 2, 2, "")); + Err = Replaces.add(Replacement("x.cc", 2, 2, "a")); 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)); + EXPECT_EQ(1u, Replaces.size()); + EXPECT_EQ(Deletion, *Replaces.begin()); +} + +TEST_F(ReplacementTest, DeletionInReplacements) { + Replacements Replaces; + Replacement R("x.cc", 0, 10, "3"); + auto Err = Replaces.add(R); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + Err = Replaces.add(Replacement("x.cc", 0, 2, "")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + Err = Replaces.add(Replacement("x.cc", 2, 2, "")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + EXPECT_EQ(1u, Replaces.size()); + EXPECT_EQ(R, *Replaces.begin()); +} + +TEST_F(ReplacementTest, OverlappingReplacements) { + Replacements Replaces; + auto Err = Replaces.add(Replacement("x.cc", 0, 3, "345")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + Err = Replaces.add(Replacement("x.cc", 2, 3, "543")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + EXPECT_EQ(1u, Replaces.size()); + EXPECT_EQ(Replacement("x.cc", 0, 5, "34543"), *Replaces.begin()); + + Err = Replaces.add(Replacement("x.cc", 2, 1, "5")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + EXPECT_EQ(1u, Replaces.size()); + EXPECT_EQ(Replacement("x.cc", 0, 5, "34543"), *Replaces.begin()); } TEST_F(ReplacementTest, AddAdjacentInsertionAndReplacement) { @@ -137,6 +175,116 @@ TEST_F(ReplacementTest, AddAdjacentInsertionAndReplacement) { EXPECT_EQ(Replaces.size(), 2u); } +TEST_F(ReplacementTest, MergeNewDeletions) { + Replacements Replaces; + Replacement ContainingReplacement("x.cc", 0, 10, ""); + auto Err = Replaces.add(ContainingReplacement); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + Err = Replaces.add(Replacement("x.cc", 5, 3, "")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + Err = Replaces.add(Replacement("x.cc", 0, 10, "")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + Err = Replaces.add(Replacement("x.cc", 5, 5, "")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + EXPECT_EQ(1u, Replaces.size()); + EXPECT_EQ(*Replaces.begin(), ContainingReplacement); +} + +TEST_F(ReplacementTest, MergeOverlappingButNotAdjacentReplacement) { + Replacements Replaces; + auto Err = Replaces.add(Replacement("x.cc", 0, 2, "")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + Err = Replaces.add(Replacement("x.cc", 5, 5, "")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + Replacement After = Replacement("x.cc", 10, 5, ""); + Err = Replaces.add(After); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + Replacement ContainingReplacement("x.cc", 0, 10, ""); + Err = Replaces.add(ContainingReplacement); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + EXPECT_EQ(2u, Replaces.size()); + EXPECT_EQ(*Replaces.begin(), ContainingReplacement); + EXPECT_EQ(*(++Replaces.begin()), After); +} + +TEST_F(ReplacementTest, InsertionBeforeMergedDeletions) { + Replacements Replaces; + + Replacement Insertion("x.cc", 0, 0, "123"); + auto Err = Replaces.add(Insertion); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + Err = Replaces.add(Replacement("x.cc", 5, 5, "")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + Replacement Deletion("x.cc", 0, 10, ""); + Err = Replaces.add(Deletion); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + EXPECT_EQ(2u, Replaces.size()); + EXPECT_EQ(*Replaces.begin(), Insertion); + EXPECT_EQ(*(++Replaces.begin()), Deletion); +} + +TEST_F(ReplacementTest, MergeOverlappingDeletions) { + Replacements Replaces; + auto Err = Replaces.add(Replacement("x.cc", 0, 2, "")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + Err = Replaces.add(Replacement("x.cc", 0, 5, "")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + EXPECT_EQ(1u, Replaces.size()); + EXPECT_EQ(Replacement("x.cc", 0, 5, ""), *Replaces.begin()); + + Err = Replaces.add(Replacement("x.cc", 1, 5, "")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + EXPECT_EQ(1u, Replaces.size()); + EXPECT_EQ(Replacement("x.cc", 0, 6, ""), *Replaces.begin()); +} + +TEST_F(ReplacementTest, FailedMergeExistingDeletions) { + Replacements Replaces; + Replacement First("x.cc", 0, 2, ""); + auto Err = Replaces.add(First); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + Replacement Second("x.cc", 5, 5, ""); + Err = Replaces.add(Second); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + Err = Replaces.add(Replacement("x.cc", 1, 10, "")); + EXPECT_TRUE(!Err); + llvm::consumeError(std::move(Err)); + + EXPECT_EQ(1u, Replaces.size()); + EXPECT_EQ(Replacement("x.cc", 0, 11, ""), *Replaces.begin()); +} + TEST_F(ReplacementTest, FailAddRegression) { Replacements Replaces; // Create two replacements, where the second one is an insertion of the empty @@ -155,7 +303,7 @@ TEST_F(ReplacementTest, FailAddRegression) { llvm::consumeError(std::move(Err)); Err = Replaces.add(Replacement("x.cc", 10, 0, "")); - EXPECT_TRUE((bool)Err); + EXPECT_TRUE(!Err); llvm::consumeError(std::move(Err)); } @@ -179,7 +327,7 @@ TEST_F(ReplacementTest, InsertAtOffsetOfReplacement) { EXPECT_EQ(Replaces.size(), 2u); } -TEST_F(ReplacementTest, FailAddInsertAtOtherInsert) { +TEST_F(ReplacementTest, AddInsertAtOtherInsertWhenOderIndependent) { Replacements Replaces; auto Err = Replaces.add(Replacement("x.cc", 10, 0, "a")); EXPECT_TRUE(!Err); @@ -189,12 +337,14 @@ TEST_F(ReplacementTest, FailAddInsertAtOtherInsert) { llvm::consumeError(std::move(Err)); Replaces.clear(); - Err = Replaces.add(Replacement("x.cc", 10, 0, "")); + Err = Replaces.add(Replacement("x.cc", 10, 0, "a")); EXPECT_TRUE(!Err); llvm::consumeError(std::move(Err)); - Err = Replaces.add(Replacement("x.cc", 10, 0, "")); - EXPECT_TRUE((bool)Err); + Err = Replaces.add(Replacement("x.cc", 10, 0, "aa")); + EXPECT_TRUE(!Err); llvm::consumeError(std::move(Err)); + EXPECT_EQ(1u, Replaces.size()); + EXPECT_EQ(Replacement("x.cc", 10, 0, "aaa"), *Replaces.begin()); Replaces.clear(); Err = Replaces.add(Replacement("x.cc", 10, 0, "")); @@ -204,8 +354,11 @@ TEST_F(ReplacementTest, FailAddInsertAtOtherInsert) { EXPECT_TRUE(!Err); llvm::consumeError(std::move(Err)); Err = Replaces.add(Replacement("x.cc", 10, 0, "")); - EXPECT_TRUE((bool)Err); + EXPECT_TRUE(!Err); llvm::consumeError(std::move(Err)); + EXPECT_EQ(2u, Replaces.size()); + EXPECT_EQ(Replacement("x.cc", 10, 0, ""), *Replaces.begin()); + EXPECT_EQ(Replacement("x.cc", 10, 3, ""), *std::next(Replaces.begin())); } TEST_F(ReplacementTest, InsertBetweenAdjacentReplacements) { @@ -256,7 +409,7 @@ TEST_F(ReplacementTest, AdjacentReplacements) { EXPECT_EQ("xy", Context.getRewrittenText(ID)); } -TEST_F(ReplacementTest, SkipsDuplicateReplacements) { +TEST_F(ReplacementTest, AddDuplicateReplacements) { FileID ID = Context.createInMemoryFile("input.cpp", "line1\nline2\nline3\nline4"); auto Replaces = toReplacements({Replacement( @@ -264,18 +417,33 @@ TEST_F(ReplacementTest, SkipsDuplicateReplacements) { auto Err = Replaces.add(Replacement( Context.Sources, Context.getLocation(ID, 2, 1), 5, "replaced")); - EXPECT_TRUE((bool)Err); + EXPECT_TRUE(!Err); llvm::consumeError(std::move(Err)); Err = Replaces.add(Replacement(Context.Sources, Context.getLocation(ID, 2, 1), 5, "replaced")); - EXPECT_TRUE((bool)Err); + EXPECT_TRUE(!Err); llvm::consumeError(std::move(Err)); EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite)); EXPECT_EQ("line1\nreplaced\nline3\nline4", Context.getRewrittenText(ID)); } +TEST_F(ReplacementTest, FailOrderDependentReplacements) { + FileID ID = Context.createInMemoryFile("input.cpp", + "line1\nline2\nline3\nline4"); + auto Replaces = toReplacements({Replacement( + Context.Sources, Context.getLocation(ID, 2, 1), 5, "other")}); + + auto Err = Replaces.add(Replacement( + Context.Sources, Context.getLocation(ID, 2, 1), 5, "rehto")); + EXPECT_TRUE((bool)Err); + llvm::consumeError(std::move(Err)); + + EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite)); + EXPECT_EQ("line1\nother\nline3\nline4", Context.getRewrittenText(ID)); +} + TEST_F(ReplacementTest, InvalidSourceLocationFailsApplyAll) { Replacements Replaces = toReplacements({Replacement(Context.Sources, SourceLocation(), 5, "2")}); -- 2.40.0