Merge deletions that are contained in a larger deletion.

[ioeric]

Summary

If a new deletion replacement is contained in an existing deletion or contains one or more existing replacements, then all deletions are merged into the largest deletion.

[djasper]

Thinking about this some more, starting to merge deletions now, but only some of them is a bit suspect. I think we either want to allow even more or continue to be restrictive for now.

I think fundamentally, there are two questions that we need to answer:

1. Is this something that the user/tool author would likely want to do?
2. Is add the replacement order-dependent in any way?

I have no clue about #1, I'd have to see use cases. E.g. what use case are you trying to solve here?

But lets look at #2: I think I have come up with an easy definition of what makes something order-dependent. Lets assume we have two replacements A and B that both refer to the same original code (I am using A and B as single replacements or as sets of a single replacement for simplicity). The question is whether A.add(B) is order-dependent. I think we should define this as (assuming we have a function that shifts a replacement by another replacement like your getReplacementInChangedCode from https://reviews.llvm.org/D24383):

A.add(B) is order-dependent (and thus should conflict, if A.merge(getReplacementInChangedCode(B)) != B.merge(getReplacementInChangedCode(A)).

I think, this enables exactly the kinds of additions that we have so far enabled, which seems good. It also enables overlapping deletions, e.g. deleting range [0-2] and [1-3] will result in deleting [0-3], not matter in which order.

[ioeric]

In D24717#546096, @djasper wrote:

Thinking about this some more, starting to merge deletions now, but only some of them is a bit suspect. I think we either want to allow even more or continue to be restrictive for now.

I think fundamentally, there are two questions that we need to answer:

1. Is this something that the user/tool author would likely want to do?
2. Is add the replacement order-dependent in any way?

I have no clue about #1, I'd have to see use cases. E.g. what use case are you trying to solve here?

Cong has this problem with dead code deletion where one dead code block is contained in another dead code block. Removing both dead entities will cause conflict now, so I figure maybe this is something we can also support because they are also order-independent and safe to deduplicate.

But lets look at #2: I think I have come up with an easy definition of what makes something order-dependent. Lets assume we have two replacements A and B that both refer to the same original code (I am using A and B as single replacements or as sets of a single replacement for simplicity). The question is whether A.add(B) is order-dependent. I think we should define this as (assuming we have a function that shifts a replacement by another replacement like your getReplacementInChangedCode from https://reviews.llvm.org/D24383):

A.add(B) is order-dependent (and thus should conflict, if A.merge(getReplacementInChangedCode(B)) != B.merge(getReplacementInChangedCode(A)).

I think, this enables exactly the kinds of additions that we have so far enabled, which seems good. It also enables overlapping deletions, e.g. deleting range [0-2] and [1-3] will result in deleting [0-3], not matter in which order.

This seems to be a nice definition for order-dependent. Just one caveat: with this condition, A=(0,0,"a") and B=(0,0,"a") are now also order-independent. Although the result for applying A and B in either order would be the same, I feel this is somehow less safe than merging deletions. And I guess the question here is whether users want to deduplicate. But for deletions, duplication doesn't matter.

[djasper]

I actually think this is a good example. So lets assume we'd write a tool to fully quote binary expressions, e.g. that turns

if (a * b + c * d == 10) ...

into

if (((a * b) + (c * d)) == 10) ...

So, here, we would be inserting two "(" and two ")" at the same locations. And, as you correctly mention, the order doesn't matter because we are inserting the same string twice. I think this is actually good behavior.

Deduplication is an interesting concern, but I think we probably want to handle that at a different layer. E.g. in the use case above, deduplicating would be quite fatal :).

[ioeric]

In D24717#546279, @djasper wrote:

I actually think this is a good example. So lets assume we'd write a tool to fully quote binary expressions, e.g. that turns

if (a * b + c * d == 10) ...

into

if (((a * b) + (c * d)) == 10) ...

So, here, we would be inserting two "(" and two ")" at the same locations. And, as you correctly mention, the order doesn't matter because we are inserting the same string twice. I think this is actually good behavior.

I agree that this is good behavior.

Deduplication is an interesting concern, but I think we probably want to handle that at a different layer. E.g. in the use case above, deduplicating would be quite fatal :).

Okay, it does make more sense to handle deduplication in a different layer.

So, with this assumption, the implementation should be much easier now: when there is conflict found in add, check this condition. If A and B are order-dependent as defined above, we then merge(getReplacementInChangedCode(B)) into the set.

[ioeric]

Abandon in favor of D24800

include/clang/Tooling/Core/Replacement.h

 
 
 private:
   Replacements(const_iterator Begin, const_iterator End)
       : Replaces(Begin, End) {}
 
   Replacements mergeReplacements(const ReplacementsImpl &Second) const;
 
+  /// \brief Tries adding a conflicting deletion `R` into the current set of
+  /// replacements by merging it with existing replacemnts that are contained in
+  /// `R` or replacement that containing `R`. `LastOverlap` is the last
+  /// replacement in the set that overlaps with `R`.
+  /// On success, all overlapping deletions are replaced with the largest
+  /// deletion, and the function returns true; otherwise, the set of
+  /// replacements is not changed, and the function returns false.
+  bool tryMergeDeletions(const Replacement &R,
+                         ReplacementsImpl::iterator LastOverlap);
+
   ReplacementsImpl Replaces;
 };
 
 /// \brief Apply all replacements in \p Replaces to the Rewriter \p Rewrite.
 ///
 /// Replacement applications happen independently of the success of
 /// other applications.
 ///

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,
+static bool isDeletion(const Replacement &R) {
+  return R.getLength() > 0 && R.getReplacementText().empty();
+}
+
+bool Replacements::tryMergeDeletions(const Replacement &R,
+                                     ReplacementsImpl::iterator LastOverlap) {
+  assert(isDeletion(R) && "R must be a deletion replacement.");
+  if (!isDeletion(*LastOverlap))
+    return false;
+  auto contains = [](const Replacement &R1, const Replacement &R2) -> bool {
+    return Range(R1.getOffset(), R1.getLength())
+        .contains(Range(R2.getOffset(), R2.getLength()));
+  };
+  if (contains(*LastOverlap, R))
+    return true;
+  // Now `LastOverlap` doesn't contain `R`. If `R` doesn't contain
+  // `LastOverlap` either, they are really conflicting.
+  if (!contains(R, *LastOverlap))
+    return false;
+  llvm::SmallVector<ReplacementsImpl::iterator, 1> MergedDeletions = {
+      LastOverlap};
+  auto MergedBegin = LastOverlap;
+  auto MergedEnd = LastOverlap;
+  // If all existing replacements overlapping with `R` are deletions that are
+  // contained in `R`, delete all deletions that are contained in `R` and insert
+  // `R`.
+  while (LastOverlap-- != Replaces.begin()) {
+    // Stop checking if `LastOverLap` does not overlap with `R` anymore.
+    if (LastOverlap->getOffset() + LastOverlap->getLength() <= R.getOffset())
+      break;
+    // Only merge `LastOverlap` into `R` if it is a deletion contained in `R`.
+    if (!isDeletion(*LastOverlap) || !contains(R, *LastOverlap))
+      return false;
+    MergedBegin = LastOverlap;
+  }
+  do {
+    Replaces.erase(MergedBegin);
+  } while (MergedBegin++ != MergedEnd);
+  Replaces.insert(R);
+  return true;
+}
+
+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());
 }
 
 llvm::Error Replacements::add(const Replacement &R) {
   // Check the file path.
if (!Range(R.getOffset(), R.getLength())
     // 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 if (isDeletion(R) && tryMergeDeletions(R, I)) {
+    // Special case: if `R` is contained in an existing deletion or contains
+    // one or more existing replacements, then all deletions can be merged into
+    // the largest deletion.
+    return llvm::Error::success();
   }
   return makeConflictReplacementsError(R, *I);
 }
 
 namespace {
 
 // Represents a merged replacement, i.e. a replacement consisting of multiple
 // overlapping replacements from 'First' and 'Second' in mergeReplacements.

unittests/Tooling/RefactoringTest.cpp

TEST_F(ReplacementTest, AddAdjacentInsertionAndReplacement) {
   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, MergeExistingDeletions) {
+  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, 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((bool)Err);
+  llvm::consumeError(std::move(Err));
+
+  EXPECT_EQ(2u, Replaces.size());
+  EXPECT_EQ(*Replaces.begin(), First);
+  EXPECT_EQ(*(++Replaces.begin()), Second);
+}
+
 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, ""));