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

68 ↗

(On Diff #61337)

Can we keep these private for now?

237 ↗

(On Diff #61337)

Should we make the latter optional?

240 ↗

(On Diff #61337)

s/Replacemments/Replacements/

245 ↗

(On Diff #61337)

I'd call this getShiftedRanges().

246 ↗

(On Diff #61337)

const vector&?

lib/Tooling/Core/Replacement.cpp

39 ↗

(On Diff #61337)

No need for parentheses.

304 ↗

(On Diff #61337)

Remove " a"

305 ↗

(On Diff #61337)

Just return the new vector and use a const parameter.

328 ↗

(On Diff #61337)

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

253 ↗

(On Diff #61359)

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

237 ↗

(On Diff #61340)

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?

lib/Tooling/Core/Replacement.cpp

305 ↗

(On Diff #61340)

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

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

328 ↗

(On Diff #61340)

That actually works very well! Thanks!

[djasper]

Nice :)

include/clang/Tooling/Core/Replacement.h

62 ↗

(On Diff #61359)

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 ↗

(On Diff #61359)

Why is this required?

lib/Tooling/Core/Replacement.cpp

287 ↗

(On Diff #61359)

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());
  }
}

319 ↗

(On Diff #61359)

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

321 ↗

(On Diff #61359)

I think you need to do:

Ranges = mergeAndSortRanges(Ranges);

here

[ioeric]

• Addressed reviewer's comments.

include/clang/Tooling/Core/Replacement.h

69 ↗

(On Diff #61359)

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

lib/Tooling/Core/Replacement.cpp

287 ↗

(On Diff #61359)

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 ↗

(On Diff #61375)

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

285 ↗

(On Diff #61375)

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

292 ↗

(On Diff #61375)

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 ↗

(On Diff #61375)

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

292 ↗

(On Diff #61375)

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

cfe/trunk/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.

 
 /// \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.

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

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) {
+              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
for (auto FirstI = First.begin(), SecondI = Second.begin();
     Delta -= Merged.deltaFirst();
     Result.insert(Merged.asReplacement());
   }
   return Result;
 }
 
 } // end namespace tooling
 } // end namespace clang
-

cfe/trunk/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