Added calculateRangesAfterReplaments() to calculate affacted ranges in the new code.

[ioeric]

Summary

Added calculateRangesAfterReplaments() to calculate original ranges as well as
newly affacted ranges in the new code.

[ioeric]

• fixed commenting.

[djasper]

include/clang/Tooling/Core/Replacement.h

73

Can we keep these private for now?

238

Should we make the latter optional?

241

s/Replacemments/Replacements/

246

I'd call this getShiftedRanges().

247

const vector&?

lib/Tooling/Core/Replacement.cpp

39

No need for parentheses.

330

Remove " a"

331

Just return the new vector and use a const parameter.

354

Couldn't we implement this using mergeReplacements?

Fundamentally:

• Turn Ranges into Replacements at (offset, length) with an empty (unimportant) replacement text of length "length".
• Merge these into Replaces
• Convert the resulting Replacements into Ranges, each with the Replacement's (offset, replacement_text.size()) and shifting subsequent ones forward.

[ioeric]

• Use mergeReplacements to calculate the new affected ranges.

[ioeric]

include/clang/Tooling/Core/Replacement.h

238

Why would why want to exclude the newly affected ranges? But if replaces overlap with original ranges, do we consider sub-ranges in original ranges being replaced as parts of the shifted ranges in the new code?

246

getShiftedRanges sounds like it's excluding affected ranges of Replaces. I think often time we want both?

lib/Tooling/Core/Replacement.cpp

331

Shall we pass Ranges by value instead since it's gonna be sorted anyway?

Also, does it make sense to have calculateChangedRanges() call this?

354

That actually works very well! Thanks!

[djasper]

Nice :)

include/clang/Tooling/Core/Replacement.h

62

Can we just add a lambda that does this to the std::sort operation? I am not sure that this is actually a natural order for all Replacements.

69

Why is this required?

lib/Tooling/Core/Replacement.cpp

287

maybe:

std::vector<Range> Result;
for (const auto &R: Ranges) {
  if (Result.empty() || !Result.back().overlapsWith(R)) {
    Result.push_back(R);
  } else {
    unsigned NewEnd = std::max(Result.back.getOffset() + Result.back.getLength(), R.getOffset() + R.getLength());
    Result[Result.size() - 1] = Range(Result.back.getOffset(), NewEnd - Result.back.getOffset());
  }
}

320

I'd probably leave these early exits out. I don't think anyone will ever notice the performance difference.

322

I think you need to do:

Ranges = mergeAndSortRanges(Ranges);

here

[ioeric]

• Addressed reviewer's comments.

include/clang/Tooling/Core/Replacement.h

69

It is used in unit test to test the equality between two ranges.

lib/Tooling/Core/Replacement.cpp

287

Thanks! Just one minor point: we also want to merge ranges R1 and R2 if

R1.getOffset() + R1.getLength() == R2.getOffset()

For example, if we have R1(1, 1) and R2(2, 1), then we can merge them into R3(1, 2).

[djasper]

A couple of small comments, otherwise looks good.

lib/Tooling/Core/Replacement.cpp

284

I don't think you need "-> bool".

285

or std::tie(LHS.getOffset(), LHS.getLength()) < std::tie(RHS.getOffset(), RHS.getLength())?

292

Maybe pull out:

unsigned CurrentEnd = Result.back().getOffset() + Result.back().getLength();

Will probably save a line or two :)

[ioeric]

• removed redundant return type in lambda function.

lib/Tooling/Core/Replacement.cpp

285

I tried std::tie(args...), but it takes references of args...and return values are temp values.

292

But there is Result.empty()...?

include/clang/Tooling/Core/Replacement.h

bool overlapsWith(Range RHS) const {
     return Offset + Length > RHS.Offset && Offset < RHS.Offset + RHS.Length;
   }
 
   /// \brief Whether this range contains \p RHS or not.
   bool contains(Range RHS) const {
     return RHS.Offset >= Offset &&
            (RHS.Offset + RHS.Length) <= (Offset + Length);
   }
+
+  /// \brief Whether this range equals to \p RHS or not.
+  bool operator==(const Range &RHS) const {
+    return Offset == RHS.getOffset() && Length == RHS.getLength();
+  }
   /// @}
 
 private:
   unsigned Offset;
   unsigned Length;
 };
 
 /// \brief A text replacement.
 ///
 /// Represents a SourceManager independent replacement of a range of text in a
 /// specific file.
 class Replacement {
 public:
   /// \brief Creates an invalid (not applicable) replacement.
   Replacement();
 
   /// \brief Creates a replacement of the range [Offset, Offset+Length) in

 
 /// \brief Applies all replacements in \p Replaces to \p Code.
 ///
 /// This completely ignores the path stored in each replacement. If one or more
 /// replacements cannot be applied, this returns an empty \c string.
 std::string applyAllReplacements(StringRef Code, const Replacements &Replaces);
 
 /// \brief Calculates the ranges in a single file that are affected by the
-/// Replacements.
+/// Replacements. Overlapping ranges will be merged.
 ///
 /// \pre Replacements must be for the same file.
+///
+/// \returns a non-overlapping and sorted ranges.
 std::vector<Range> calculateChangedRanges(const Replacements &Replaces);
 
+/// \brief Calculates the new ranges after \p Replaces are applied. These
+/// include both the original \p Ranges and the affected ranges of \p Replaces
+/// in the new code.
+///
+/// \pre Replacements must be for the same file.
+///
+/// \return The new ranges after \p Replaces are applied. The new ranges will be
+/// sorted and non-overlapping.
+std::vector<Range>
+calculateRangesAfterReplacements(const Replacements &Replaces,
+                                 const std::vector<Range> &Ranges);
+
 /// \brief Groups a random set of replacements by file path. Replacements
 /// related to the same file entry are put into the same vector.
 std::map<std::string, Replacements>
 groupReplacementsByFile(const Replacements &Replaces);
 
 /// \brief Merges two sets of replacements with the second set referring to the
 /// code after applying the first set. Within both 'First' and 'Second',
 /// replacements must not overlap.

lib/Tooling/Core/Replacement.cpp

 
 Replacement::Replacement()
   : FilePath(InvalidLocation) {}
 
 Replacement::Replacement(StringRef FilePath, unsigned Offset, unsigned Length,
                          StringRef ReplacementText)
     : FilePath(FilePath), ReplacementRange(Offset, Length),
       ReplacementText(ReplacementText) {}
 
 Replacement::Replacement(const SourceManager &Sources, SourceLocation Start,
                          unsigned Length, StringRef ReplacementText) {
   setFromSourceLocation(Sources, Start, Length, ReplacementText);
 }
 
 Replacement::Replacement(const SourceManager &Sources,
                          const CharSourceRange &Range,
                          StringRef ReplacementText,
std::string applyAllReplacements(StringRef Code, const Replacements &Replaces) {
   }
   std::string Result;
   llvm::raw_string_ostream OS(Result);
   Rewrite.getEditBuffer(ID).write(OS);
   OS.flush();
   return Result;
 }
 
+// Merge and sort overlapping ranges in \p Ranges.
+static std::vector<Range> mergeAndSortRanges(std::vector<Range> Ranges) {
+  std::sort(Ranges.begin(), Ranges.end(),
+            [](const Range &LHS, const Range &RHS) -> bool {
+              if (LHS.getOffset() != RHS.getOffset())
+                return LHS.getOffset() < RHS.getOffset();
+              return LHS.getLength() < RHS.getLength();
+            });
+  std::vector<Range> Result;
+  for (const auto &R : Ranges) {
+    if (Result.empty() ||
+        Result.back().getOffset() + Result.back().getLength() < R.getOffset()) {
+      Result.push_back(R);
+    } else {
+      unsigned NewEnd =
+          std::max(Result.back().getOffset() + Result.back().getLength(),
+                   R.getOffset() + R.getLength());
+      Result[Result.size() - 1] =
+          Range(Result.back().getOffset(), NewEnd - Result.back().getOffset());
+    }
+  }
+  return Result;
+}
+
 std::vector<Range> calculateChangedRanges(const Replacements &Replaces) {
   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();
     ChangedRanges.push_back(Range(Offset, Length));
   }
-  return ChangedRanges;
+  return mergeAndSortRanges(ChangedRanges);
+}
+
+std::vector<Range>
+calculateRangesAfterReplacements(const Replacements &Replaces,
+                                 const std::vector<Range> &Ranges) {
+  auto MergedRanges = mergeAndSortRanges(Ranges);
+  tooling::Replacements FakeReplaces;
+  for (const auto &R : MergedRanges)
+    FakeReplaces.insert(Replacement(Replaces.begin()->getFilePath(),
+                                    R.getOffset(), R.getLength(),
+                                    std::string(" ", R.getLength())));
+  tooling::Replacements NewReplaces = mergeReplacements(FakeReplaces, Replaces);
+  return calculateChangedRanges(NewReplaces);
 }
 
 namespace {
 // Represents a merged replacement, i.e. a replacement consisting of multiple
 // overlapping replacements from 'First' and 'Second' in mergeReplacements.
 //
 // Position projection:
 // Offsets and lengths of the replacements can generally refer to two different
 // coordinate spaces. Replacements from 'First' refer to the original text
 // whereas replacements from 'Second' refer to the text after applying 'First'.
 //
 // MergedReplacement always operates in the coordinate space of the original
 // text, i.e. transforms elements from 'Second' to take into account what was
 // changed based on the elements from 'First'.
 //
 // We can correctly calculate this projection as we look at the replacements in
 // order of strictly increasing offsets.
 //
 // Invariants:
 // * We always merge elements from 'First' into elements from 'Second' and vice
 //   versa. Within each set, the replacements are non-overlapping.
 // * We only extend to the right, i.e. merge elements with strictly increasing
 //   offsets.
 class MergedReplacement {
 public:
   MergedReplacement(const Replacement &R, bool MergeSecond, int D)
       : MergeSecond(MergeSecond), Delta(D), FilePath(R.getFilePath()),
         Offset(R.getOffset() + (MergeSecond ? 0 : Delta)), Length(R.getLength()),
         Text(R.getReplacementText()) {
     Delta += MergeSecond ? 0 : Text.size() - Length;
     DeltaFirst = MergeSecond ? Text.size() - Length : 0;
   }
 
   // Merges the next element 'R' into this merged element. As we always merge
   // from 'First' into 'Second' or vice versa, the MergedReplacement knows what
for (auto FirstI = First.begin(), SecondI = Second.begin();
     Delta -= Merged.deltaFirst();
     Result.insert(Merged.asReplacement());
   }
   return Result;
 }
 
 } // end namespace tooling
 } // end namespace clang
-

unittests/Tooling/RefactoringTest.cpp

TEST(Range, CalculateRangesOfReplacements) {
   // After : bbbbbbzzzzzzoooooooooooooooo
   Replacements Replaces;
   Replaces.insert(Replacement("foo", 0, 4, ""));
   Replaces.insert(Replacement("foo", 10, 1, "zzzzzz"));
   Replaces.insert(Replacement("foo", 11, 0, "oooooooooooooooo"));
 
   std::vector<Range> Ranges = calculateChangedRanges(Replaces);
 
-  EXPECT_EQ(3ul, Ranges.size());
+  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() == 6);
-  EXPECT_TRUE(Ranges[2].getOffset() == 12);
-  EXPECT_TRUE(Ranges[2].getLength() == 16);
+  EXPECT_TRUE(Ranges[1].getLength() == 22);
+}
+
+TEST(Range, RangesAfterReplacements) {
+  std::vector<Range> Ranges = {Range(5, 2), Range(10, 5)};
+  Replacements Replaces = {Replacement("foo", 0, 2, "1234")};
+  std::vector<Range> Expected = {Range(0, 4), Range(7, 2), Range(12, 5)};
+  EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
+}
+
+TEST(Range, RangesBeforeReplacements) {
+  std::vector<Range> Ranges = {Range(5, 2), Range(10, 5)};
+  Replacements Replaces = {Replacement("foo", 20, 2, "1234")};
+  std::vector<Range> Expected = {Range(5, 2), Range(10, 5), Range(20, 4)};
+  EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
+}
+
+TEST(Range, NotAffectedByReplacements) {
+  std::vector<Range> Ranges = {Range(0, 2), Range(5, 2), Range(10, 5)};
+  Replacements Replaces = {Replacement("foo", 3, 2, "12"),
+                           Replacement("foo", 12, 2, "12"),
+                           Replacement("foo", 20, 5, "")};
+  std::vector<Range> Expected = {Range(0, 2), Range(3, 4), Range(10, 5),
+                                 Range(20, 0)};
+  EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
+}
+
+TEST(Range, RangesWithNonOverlappingReplacements) {
+  std::vector<Range> Ranges = {Range(0, 2), Range(5, 2), Range(10, 5)};
+  Replacements Replaces = {Replacement("foo", 3, 1, ""),
+                           Replacement("foo", 6, 1, "123"),
+                           Replacement("foo", 20, 2, "12345")};
+  std::vector<Range> Expected = {Range(0, 2), Range(3, 0), Range(4, 4),
+                                 Range(11, 5), Range(21, 5)};
+  EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
+}
+
+TEST(Range, RangesWithOverlappingReplacements) {
+  std::vector<Range> Ranges = {Range(0, 2), Range(5, 2), Range(15, 5),
+                               Range(30, 5)};
+  Replacements Replaces = {
+      Replacement("foo", 1, 3, ""), Replacement("foo", 6, 1, "123"),
+      Replacement("foo", 13, 3, "1"), Replacement("foo", 25, 15, "")};
+  std::vector<Range> Expected = {Range(0, 1), Range(2, 4), Range(12, 5),
+                                 Range(22, 0)};
+  EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
+}
+
+TEST(Range, MergeIntoOneRange) {
+  std::vector<Range> Ranges = {Range(0, 2), Range(5, 2), Range(15, 5)};
+  Replacements Replaces = {Replacement("foo", 1, 15, "1234567890")};
+  std::vector<Range> Expected = {Range(0, 15)};
+  EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
+}
+
+TEST(Range, ReplacementsStartingAtRangeOffsets) {
+  std::vector<Range> Ranges = {Range(0, 2), Range(5, 5), Range(15, 5)};
+  Replacements Replaces = {
+      Replacement("foo", 0, 2, "12"), Replacement("foo", 5, 1, "123"),
+      Replacement("foo", 7, 4, "12345"), Replacement("foo", 15, 10, "12")};
+  std::vector<Range> Expected = {Range(0, 2), Range(5, 9), Range(18, 2)};
+  EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
+}
+
+TEST(Range, ReplacementsEndingAtRangeEnds) {
+  std::vector<Range> Ranges = {Range(0, 2), Range(5, 2), Range(15, 5)};
+  Replacements Replaces = {Replacement("foo", 6, 1, "123"),
+                           Replacement("foo", 17, 3, "12")};
+  std::vector<Range> Expected = {Range(0, 2), Range(5, 4), Range(17, 4)};
+  EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
+}
+
+TEST(Range, AjacentReplacements) {
+  std::vector<Range> Ranges = {Range(0, 0), Range(15, 5)};
+  Replacements Replaces = {Replacement("foo", 1, 2, "123"),
+                           Replacement("foo", 12, 3, "1234")};
+  std::vector<Range> Expected = {Range(0, 0), Range(1, 3), Range(13, 9)};
+  EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
+}
+
+TEST(Range, MergeRangesAfterReplacements) {
+  std::vector<Range> Ranges = {Range(8, 0), Range(5, 2), Range(9, 0), Range(0, 1)};
+  Replacements Replaces = {Replacement("foo", 1, 3, ""),
+                           Replacement("foo", 7, 0, "12"), Replacement("foo", 9, 2, "")};
+  std::vector<Range> Expected = {Range(0, 1), Range(2, 4), Range(7, 0), Range(8, 0)};
+  EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
 }
 
 TEST(DeduplicateTest, removesDuplicates) {
   std::vector<Replacement> Input;
   Input.push_back(Replacement("fileA", 50, 0, " foo "));
   Input.push_back(Replacement("fileA", 10, 3, " bar "));
   Input.push_back(Replacement("fileA", 10, 2, " bar ")); // Length differs
   Input.push_back(Replacement("fileA", 9,  3, " bar ")); // Offset differs