ioeric updated this revision to Diff 72045.
ioeric added a comment.

- Provide order-independent replacements examples in comments.


https://reviews.llvm.org/D24800

Files:
  include/clang/Tooling/Core/Replacement.h
  lib/Tooling/Core/Replacement.cpp
  unittests/Tooling/RefactoringTest.cpp

Index: unittests/Tooling/RefactoringTest.cpp
===================================================================
--- unittests/Tooling/RefactoringTest.cpp
+++ unittests/Tooling/RefactoringTest.cpp
@@ -101,18 +101,56 @@
 
 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 @@
   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 @@
   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 @@
   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 @@
   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 @@
   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,26 +409,41 @@
   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(
       Context.Sources, Context.getLocation(ID, 2, 1), 5, "replaced")});
 
   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")});
Index: lib/Tooling/Core/Replacement.cpp
===================================================================
--- lib/Tooling/Core/Replacement.cpp
+++ lib/Tooling/Core/Replacement.cpp
@@ -134,14 +134,63 @@
                         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<llvm::StringError>(
       "New replacement:\n" + New.toString() +
           "\nconflicts with existing replacement:\n" + Existing.toString(),
       llvm::inconvertibleErrorCode());
 }
 
+Replacements Replacements::getCanonicalReplacements() const {
+  std::vector<Replacement> NewReplaces;
+  // Merge adjacent replacements.
+  for (const auto &R : Replaces) {
+    if (NewReplaces.empty()) {
+      NewReplaces.push_back(R);
+      continue;
+    }
+    auto &Prev = NewReplaces.back();
+    auto PrevEnd = Prev.getOffset() + Prev.getLength();
+    if (PrevEnd < R.getOffset()) {
+      NewReplaces.push_back(R);
+    } else {
+      assert(PrevEnd == R.getOffset());
+      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());
+}
+
+llvm::Expected<Replacements>
+Replacements::mergeIfOrderIndependent(const Replacement &R) const {
+  Replacements Rs(R);
+  Replacements ShiftedRs(getReplacementInChangedCode(R));
+  Replacements ShiftedReplaces;
+  for (const auto &Replace : Replaces)
+    ShiftedReplaces.Replaces.insert(Rs.getReplacementInChangedCode(Replace));
+  auto MergeRs = merge(ShiftedRs);
+  auto MergeReplaces = Rs.merge(ShiftedReplaces);
+  // Since empty or segmented replacements around existing replacements might be
+  // produced above, we need to compare replacements in canonical forms.
+  if (MergeRs.getCanonicalReplacements() ==
+      MergeReplaces.getCanonicalReplacements())
+    return MergeRs;
+  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 +221,21 @@
   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,21 +254,38 @@
     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
     //   have come after `AtEnd`.
     //   - If `R` is not an insertion, `I` must be an insertion; otherwise, `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<Replacements> 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 {
Index: include/clang/Tooling/Core/Replacement.h
===================================================================
--- include/clang/Tooling/Core/Replacement.h
+++ include/clang/Tooling/Core/Replacement.h
@@ -167,10 +167,25 @@
   /// 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 if one inserts text X and the
+  ///     other inserts text Y.
+  /// 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 @@
 
   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; otheriwse, returns an
+  // error.
+  llvm::Expected<Replacements>
+  mergeIfOrderIndependent(const Replacement &R) const;
+
   ReplacementsImpl Replaces;
 };
 
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

Reply via email to