Merge conflicting replacements when they are order-independent.

[ioeric]

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

[ioeric]

• Provide order-independent replacements examples in comments.

[ioeric]

Friendly ping :)

[klimek]

include/clang/Tooling/Core/Replacement.h

177–178 ↗

(On Diff #72045)

This seems incorrect. What am I missing?

[ioeric]

include/clang/Tooling/Core/Replacement.h

177–178 ↗

(On Diff #72045)

Here is the discussion about this: https://reviews.llvm.org/D24717

[klimek]

include/clang/Tooling/Core/Replacement.h

177–178 ↗

(On Diff #72045)

I misunderstood :) Perhaps change to:
, i.e. if X + Y == Y + X when inserting X and Y respectively.

242 ↗

(On Diff #72045)

typo: otheriwse

lib/Tooling/Core/Replacement.cpp

162 ↗

(On Diff #72045)

I'd not use auto for simple integer types.

166 ↗

(On Diff #72045)

Add comment why we can assert this.

179–181 ↗

(On Diff #72045)

These names are confusing me...

184 ↗

(On Diff #72045)

This comes from a single replacement - why do we need to call merge?

[ioeric]

• Addressed review comments.

lib/Tooling/Core/Replacement.cpp

179–181 ↗

(On Diff #72045)

Trying to make names less confusing... any better now?

184 ↗

(On Diff #72045)

Because it refers to code after Replaces are applied?

[klimek]

lib/Tooling/Core/Replacement.cpp

179–181 ↗

(On Diff #72642)

I think this is a bit subtle and needs a lot more comments to guide me along what is happening and why ...

[ioeric]

• Addressed review comments.

lib/Tooling/Core/Replacement.cpp

179–181 ↗

(On Diff #72642)

Ahh, right! Should've done that...

Comments added.

[klimek]

lg

lib/Tooling/Core/Replacement.cpp

179–181 ↗

(On Diff #72666)

Much better. Thanks.

[alexander-shaposhnikov]

cfe/trunk/lib/Tooling/Core/Replacement.cpp

182

sorry, probably i am late to the party,
however i'd like to ask how this method is supposed to be used by the customers of this code.
If i'm not mistaken we have some concrete examples in clang-extra-tools: for instance @omtcyfz referred to this diff on https://reviews.llvm.org/D24914.
Basically after this diff the class Replacements contains several methods (add, mergeIfOrderIndependent etc), but mergeIfOrderIndependent potentially will copy a lot of replacements (i don't know if the perf is a real issue here, but at least it looks a bit strange to me).
Another question - how are the customers of this code supposed to use the method add ? still suppress the error (like what was happening on https://reviews.llvm.org/D24914) ?
Am i missing smth ?
cc: @klimek, @djasper.

[ioeric]

cfe/trunk/lib/Tooling/Core/Replacement.cpp

182

First of all, this diff doesn't introduce new interfaces - they are just private helper functions, which are mostly called on conflicting replacements set with relatively small size.

Secondly, add now supports merging order-independent replacements, so it handles deduplication to some extend, i.e. identical non-insertion replacements can be deduplicated, which happens to solve the issue with clang-rename as mentioned in D24914.

[alexander-shaposhnikov]

cfe/trunk/lib/Tooling/Core/Replacement.cpp

182

i see, thank you for the explanation.

cfe/trunk/include/clang/Tooling/Core/Replacement.h

public:
   /// Returns `success` if the replacement is successfully inserted; otherwise,
   /// it returns an llvm::Error, i.e. there is a conflict between R and the
   /// existing replacements (i.e. they are order-dependent) or R's file path is
   /// different from the filepath of existing replacements. Callers must
   /// explicitly check the Error returned. This prevents users from adding
   /// 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.
   llvm::Error add(const Replacement &R);
 
   /// \brief Merges \p Replaces into the current replacements. \p Replaces
   /// refers to code after applying the current replacements.
   Replacements merge(const Replacements &Replaces) const;

 
 
 private:
   Replacements(const_iterator Begin, const_iterator End)
       : Replaces(Begin, End) {}
 
   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<Replacements>
+  mergeIfOrderIndependent(const Replacement &R) const;
+
   ReplacementsImpl Replaces;
 };
 
 /// \brief Apply all replacements in \p Replaces to the Rewriter \p Rewrite.
 ///
 /// Replacement applications happen independently of the success of
 /// other applications.
 ///

cfe/trunk/lib/Tooling/Core/Replacement.cpp

void Replacement::setFromSourceRange(const SourceManager &Sources,
                                      const CharSourceRange &Range,
                                      StringRef ReplacementText,
                                      const LangOptions &LangOpts) {
   setFromSourceLocation(Sources, Sources.getSpellingLoc(Range.getBegin()),
                         getRangeSize(Sources, Range, LangOpts),
                         ReplacementText);
 }
 
-llvm::Error makeConflictReplacementsError(const Replacement &New,
+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();
+    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>
+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())
     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());
llvm::Error Replacements::add(const Replacement &R) {
   // Find the first entry that starts after or at the end of R. Note that
   // entries that start at the end can still be conflicting if R is an
   // insertion.
   auto I = Replaces.lower_bound(AtEnd);
   // If `I` starts at the same offset as `R`, `R` must be an insertion.
   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)
+    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
     // either end before `R` or end at `R` but has length > 0 (if the
     // replacement before `I` is an insertion at `R`, it would have been `I`
     // since it is a lower bound of `AtEnd` and ordered before the current `I`
     // in the set).
     Replaces.insert(R);
     return llvm::Error::success();
   }
 
   // `I` is the smallest iterator (after `R`) whose entry cannot overlap.
   // If that is begin(), there are no overlaps.
   if (I == Replaces.begin()) {
     Replaces.insert(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
     //   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 {
 
 // Represents a merged replacement, i.e. a replacement consisting of multiple
 // overlapping replacements from 'First' and 'Second' in mergeReplacements.
 //
 // Position projection:

cfe/trunk/unittests/Tooling/RefactoringTest.cpp

TEST_F(ReplacementTest, ReturnsInvalidPath) {
   EXPECT_TRUE(Replace1.getFilePath().empty());
 
   Replacement Replace2;
   EXPECT_TRUE(Replace2.getFilePath().empty());
 }
 
 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) {
   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(!Err);
   llvm::consumeError(std::move(Err));
   EXPECT_EQ(Replaces.size(), 2u);
 
   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(!Err);
   llvm::consumeError(std::move(Err));
   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
   // 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);
+  EXPECT_TRUE(!Err);
   llvm::consumeError(std::move(Err));
 }
 
 TEST_F(ReplacementTest, InsertAtOffsetOfReplacement) {
   Replacements Replaces;
   auto Err = Replaces.add(Replacement("x.cc", 10, 2, ""));
   EXPECT_TRUE(!Err);
   llvm::consumeError(std::move(Err));
   Err = Replaces.add(Replacement("x.cc", 10, 0, ""));
   EXPECT_TRUE(!Err);
   llvm::consumeError(std::move(Err));
   EXPECT_EQ(Replaces.size(), 2u);
 
   Replaces.clear();
   Err = Replaces.add(Replacement("x.cc", 10, 0, ""));
   EXPECT_TRUE(!Err);
   llvm::consumeError(std::move(Err));
   Err = Replaces.add(Replacement("x.cc", 10, 2, ""));
   EXPECT_TRUE(!Err);
   llvm::consumeError(std::move(Err));
   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);
   llvm::consumeError(std::move(Err));
   Err = Replaces.add(Replacement("x.cc", 10, 0, "b"));
   EXPECT_TRUE((bool)Err);
   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, ""));
   EXPECT_TRUE(!Err);
   llvm::consumeError(std::move(Err));
   Err = Replaces.add(Replacement("x.cc", 10, 3, ""));
   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) {
   Replacements Replaces;
   auto Err = Replaces.add(Replacement("x.cc", 10, 5, "a"));
   EXPECT_TRUE(!Err);
   llvm::consumeError(std::move(Err));
   Err = Replaces.add(Replacement("x.cc", 8, 2, "a"));
FileID ID = Context.createInMemoryFile("input.cpp",
                                          "ab");
   Replacements Replaces = toReplacements(
       {Replacement(Context.Sources, Context.getLocation(ID, 1, 1), 1, "x"),
        Replacement(Context.Sources, Context.getLocation(ID, 1, 2), 1, "y")});
   EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite));
   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")});
 
   EXPECT_FALSE(applyAllReplacements(Replaces, Context.Rewrite));
 }
 
 TEST_F(ReplacementTest, MultipleFilesReplaceAndFormat) {