Recommit r281457 "Supports adding insertion around non-insertion replacements".

[ioeric]

Summary

Diff to r281457:

• added a test case CalculateRangesOfInsertionAroundReplacement.

[ioeric]

• Update comment in getAffectedRanges.

[ioeric]

• Supports adding insertion around non-insertion replacements. Recommit r281457.
• Also add a test case for calculating ranges for replacements with the same offset.

[ioeric]

This patch now only recommits D24515 with an additional test case CalculateRangesOfInsertionAroundReplacement.

[djasper]

Looks good.

include/clang/Tooling/Core/Replacement.h

public:
   typedef ReplacementsImpl::const_iterator const_iterator;
 
   Replacements() = default;
 
   explicit Replacements(const Replacement &R) { Replaces.insert(R); }
 
   /// \brief Adds a new replacement \p R to the current set of replacements.
   /// \p R must have the same file path as all existing replacements.
-  /// Returns true if the replacement is successfully inserted; otherwise,
+  /// 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 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.
+  /// 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:
+  ///   - don't overlap (being directly adjacent is fine) and
+  ///   - aren't both inserts at the same code location (would be
+  ///     order-dependent).
   /// 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;

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,
+                                          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 (!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) {
   // Thus, we know that all replacements that start after the end of the current
   // replacement cannot overlap.
   Replacement AtEnd(R.getFilePath(), R.getOffset() + R.getLength(), 0, "");
 
   // 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 it starts at the same offset as R (can only happen if R is an
-  // insertion), we have a conflict.  In that case, increase I to fall through
-  // to the conflict check.
-  if (I != Replaces.end() && R.getOffset() == I->getOffset())
-    ++I;
+  // 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)
+      return makeConflictReplacementsError(R, *I);
+    // 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 whose entry cannot overlap.
   // If that is begin(), there are no overlaps.
   if (I == Replaces.begin()) {
     Replaces.insert(R);
     return llvm::Error::success();
   }
   --I;
   // If the previous entry does not overlap, we know that entries before it
   // can also not overlap.
-  if (R.getOffset() != I->getOffset() &&
-      !Range(R.getOffset(), R.getLength())
+  if (!Range(R.getOffset(), R.getLength())
            .overlapsWith(Range(I->getOffset(), I->getLength()))) {
+    // 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 it has length 0.
+    //   - 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();
   }
-  return llvm::make_error<llvm::StringError>(
-      "New replacement:\n" + R.toString() +
-          "\nconflicts with existing replacement:\n" + I->toString(),
-      llvm::inconvertibleErrorCode());
+  return makeConflictReplacementsError(R, *I);
 }
 
 namespace {
 
 // Represents a merged replacement, i.e. a replacement consisting of multiple
 // overlapping replacements from 'First' and 'Second' in mergeReplacements.
 //
 // Position projection:
for (const auto &R : MergedRanges) {
     (void)Err;
   }
   return FakeReplaces.merge(Replaces).getAffectedRanges();
 }
 
 std::vector<Range> Replacements::getAffectedRanges() const {
   std::vector<Range> ChangedRanges;
   int Shift = 0;
-  for (const Replacement &R : Replaces) {
-    unsigned Offset = R.getOffset() + Shift;
-    unsigned Length = R.getReplacementText().size();
-    Shift += Length - R.getLength();
+  for (auto I = Replaces.begin(), Prev = Replaces.end(), E = Replaces.end();
+       I != E; Prev = I, ++I) {
+    unsigned Offset = I->getOffset() + Shift;
+    // An insertion (`I`) and a non-insertion replacement (`Prev`) may have the
+    // same offset. In this case, `Prev` will be ordered before `I` in the set,
+    // but the offset of `I` should not be shifted by `Prev`, so we deduce the
+    // shift of `Prev` from the new offset of `I`.
+    if (Prev != E && Prev->getOffset() == I->getOffset()) {
+      llvm::errs() << "Last: " << Prev->toString() << "\n"
+                   << "R: " << I->toString() << "\n";
+      assert(Prev->getLength() > 0 && I->getLength() == 0 &&
+             "Two replacements with the same offset must consist of one "
+             "non-insertion replacement and one insertion.");
+      Offset -= Prev->getReplacementText().size() - Prev->getLength();
+    }
+    unsigned Length = I->getReplacementText().size();
+    Shift += Length - I->getLength();
     ChangedRanges.push_back(Range(Offset, Length));
   }
   return combineAndSortRanges(ChangedRanges);
 }
 
 unsigned Replacements::getShiftedCodePosition(unsigned Position) const {
   unsigned Offset = 0;
   for (const auto& R : Replaces) {

unittests/Tooling/RefactoringTest.cpp

TEST_F(ReplacementTest, FailAddReplacements) {
   Err = Replaces.add(Replacement("x.cc", 2, 2, ""));
   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));
 }
 
-TEST_F(ReplacementTest, FailAddOverlappingInsertions) {
+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((bool)Err);
+  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((bool)Err);
+  EXPECT_TRUE(!Err);
   llvm::consumeError(std::move(Err));
+  EXPECT_EQ(Replaces.size(), 2u);
 }
 
 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);
   llvm::consumeError(std::move(Err));
 }
 
-TEST_F(ReplacementTest, FailAddInsertAtOffsetOfReplacement) {
+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((bool)Err);
+  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) {
   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, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 10, 0, ""));
+  EXPECT_TRUE((bool)Err);
+  llvm::consumeError(std::move(Err));
+
+  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);
+  llvm::consumeError(std::move(Err));
+}
+
+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"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 10, 0, "b"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
 }
 
 TEST_F(ReplacementTest, CanApplyReplacements) {
   FileID ID = Context.createInMemoryFile("input.cpp",
                                          "line1\nline2\nline3\nline4");
   Replacements Replaces =
       toReplacements({Replacement(Context.Sources,
                                   Context.getLocation(ID, 2, 1), 5, "replaced"),
                       Replacement(Context.Sources,
                                   Context.getLocation(ID, 3, 1), 5, "other")});
   EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite));
   EXPECT_EQ("line1\nreplaced\nother\nline4", Context.getRewrittenText(ID));
 }
 
+// Verifies that replacement/deletion is applied before insertion at the same
+// offset.
+TEST_F(ReplacementTest, InsertAndDelete) {
+  FileID ID = Context.createInMemoryFile("input.cpp",
+                                         "line1\nline2\nline3\nline4");
+  Replacements Replaces = toReplacements(
+      {Replacement(Context.Sources, Context.getLocation(ID, 2, 1), 6, ""),
+       Replacement(Context.Sources, Context.getLocation(ID, 2, 1), 0,
+                   "other\n")});
+  EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite));
+  EXPECT_EQ("line1\nother\nline3\nline4", Context.getRewrittenText(ID));
+}
+
+TEST_F(ReplacementTest, AdjacentReplacements) {
+  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) {
   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"));
TEST(Range, CalculateRangesOfReplacements) {
 
   EXPECT_EQ(2ul, Ranges.size());
   EXPECT_TRUE(Ranges[0].getOffset() == 0);
   EXPECT_TRUE(Ranges[0].getLength() == 0);
   EXPECT_TRUE(Ranges[1].getOffset() == 6);
   EXPECT_TRUE(Ranges[1].getLength() == 22);
 }
 
+TEST(Range, CalculateRangesOfInsertionAroundReplacement) {
+  Replacements Replaces = toReplacements(
+      {Replacement("foo", 0, 2, ""), Replacement("foo", 0, 0, "ba")});
+
+  std::vector<Range> Ranges = Replaces.getAffectedRanges();
+
+  EXPECT_EQ(1ul, Ranges.size());
+  EXPECT_EQ(0u, Ranges[0].getOffset());
+  EXPECT_EQ(2u, Ranges[0].getLength());
+}
+
 TEST(Range, RangesAfterEmptyReplacements) {
   std::vector<Range> Ranges = {Range(5, 6), Range(10, 5)};
   Replacements Replaces;
   std::vector<Range> Expected = {Range(5, 10)};
   EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
 }
 
 TEST(Range, RangesAfterReplacements) {