"Fossies" - the Fresh Open Source Software Archive

Member "cfe-9.0.0.src/lib/Tooling/Core/Replacement.cpp" (6 Feb 2019, 24555 Bytes) of package /linux/misc/cfe-9.0.0.src.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. See also the latest Fossies "Diffs" side-by-side code changes report for "Replacement.cpp": 8.0.1_vs_9.0.0.

    1 //===- Replacement.cpp - Framework for clang refactoring tools ------------===//
    2 //
    3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
    4 // See https://llvm.org/LICENSE.txt for license information.
    5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
    6 //
    7 //===----------------------------------------------------------------------===//
    8 //
    9 //  Implements classes to support/store refactorings.
   10 //
   11 //===----------------------------------------------------------------------===//
   12 
   13 #include "clang/Tooling/Core/Replacement.h"
   14 #include "clang/Basic/Diagnostic.h"
   15 #include "clang/Basic/DiagnosticIDs.h"
   16 #include "clang/Basic/DiagnosticOptions.h"
   17 #include "clang/Basic/FileManager.h"
   18 #include "clang/Basic/FileSystemOptions.h"
   19 #include "clang/Basic/SourceLocation.h"
   20 #include "clang/Basic/SourceManager.h"
   21 #include "clang/Lex/Lexer.h"
   22 #include "clang/Rewrite/Core/RewriteBuffer.h"
   23 #include "clang/Rewrite/Core/Rewriter.h"
   24 #include "llvm/ADT/IntrusiveRefCntPtr.h"
   25 #include "llvm/ADT/SmallPtrSet.h"
   26 #include "llvm/ADT/StringRef.h"
   27 #include "llvm/Support/Error.h"
   28 #include "llvm/Support/ErrorHandling.h"
   29 #include "llvm/Support/MemoryBuffer.h"
   30 #include "llvm/Support/VirtualFileSystem.h"
   31 #include "llvm/Support/raw_ostream.h"
   32 #include <algorithm>
   33 #include <cassert>
   34 #include <limits>
   35 #include <map>
   36 #include <string>
   37 #include <utility>
   38 #include <vector>
   39 
   40 using namespace clang;
   41 using namespace tooling;
   42 
   43 static const char * const InvalidLocation = "";
   44 
   45 Replacement::Replacement() : FilePath(InvalidLocation) {}
   46 
   47 Replacement::Replacement(StringRef FilePath, unsigned Offset, unsigned Length,
   48                          StringRef ReplacementText)
   49     : FilePath(FilePath), ReplacementRange(Offset, Length),
   50       ReplacementText(ReplacementText) {}
   51 
   52 Replacement::Replacement(const SourceManager &Sources, SourceLocation Start,
   53                          unsigned Length, StringRef ReplacementText) {
   54   setFromSourceLocation(Sources, Start, Length, ReplacementText);
   55 }
   56 
   57 Replacement::Replacement(const SourceManager &Sources,
   58                          const CharSourceRange &Range,
   59                          StringRef ReplacementText,
   60                          const LangOptions &LangOpts) {
   61   setFromSourceRange(Sources, Range, ReplacementText, LangOpts);
   62 }
   63 
   64 bool Replacement::isApplicable() const {
   65   return FilePath != InvalidLocation;
   66 }
   67 
   68 bool Replacement::apply(Rewriter &Rewrite) const {
   69   SourceManager &SM = Rewrite.getSourceMgr();
   70   const FileEntry *Entry = SM.getFileManager().getFile(FilePath);
   71   if (!Entry)
   72     return false;
   73 
   74   FileID ID = SM.getOrCreateFileID(Entry, SrcMgr::C_User);
   75   const SourceLocation Start =
   76     SM.getLocForStartOfFile(ID).
   77     getLocWithOffset(ReplacementRange.getOffset());
   78   // ReplaceText returns false on success.
   79   // ReplaceText only fails if the source location is not a file location, in
   80   // which case we already returned false earlier.
   81   bool RewriteSucceeded = !Rewrite.ReplaceText(
   82       Start, ReplacementRange.getLength(), ReplacementText);
   83   assert(RewriteSucceeded);
   84   return RewriteSucceeded;
   85 }
   86 
   87 std::string Replacement::toString() const {
   88   std::string Result;
   89   llvm::raw_string_ostream Stream(Result);
   90   Stream << FilePath << ": " << ReplacementRange.getOffset() << ":+"
   91          << ReplacementRange.getLength() << ":\"" << ReplacementText << "\"";
   92   return Stream.str();
   93 }
   94 
   95 namespace clang {
   96 namespace tooling {
   97 
   98 bool operator<(const Replacement &LHS, const Replacement &RHS) {
   99   if (LHS.getOffset() != RHS.getOffset())
  100     return LHS.getOffset() < RHS.getOffset();
  101 
  102   if (LHS.getLength() != RHS.getLength())
  103     return LHS.getLength() < RHS.getLength();
  104 
  105   if (LHS.getFilePath() != RHS.getFilePath())
  106     return LHS.getFilePath() < RHS.getFilePath();
  107   return LHS.getReplacementText() < RHS.getReplacementText();
  108 }
  109 
  110 bool operator==(const Replacement &LHS, const Replacement &RHS) {
  111   return LHS.getOffset() == RHS.getOffset() &&
  112          LHS.getLength() == RHS.getLength() &&
  113          LHS.getFilePath() == RHS.getFilePath() &&
  114          LHS.getReplacementText() == RHS.getReplacementText();
  115 }
  116 
  117 } // namespace tooling
  118 } // namespace clang
  119 
  120 void Replacement::setFromSourceLocation(const SourceManager &Sources,
  121                                         SourceLocation Start, unsigned Length,
  122                                         StringRef ReplacementText) {
  123   const std::pair<FileID, unsigned> DecomposedLocation =
  124       Sources.getDecomposedLoc(Start);
  125   const FileEntry *Entry = Sources.getFileEntryForID(DecomposedLocation.first);
  126   this->FilePath = Entry ? Entry->getName() : InvalidLocation;
  127   this->ReplacementRange = Range(DecomposedLocation.second, Length);
  128   this->ReplacementText = ReplacementText;
  129 }
  130 
  131 // FIXME: This should go into the Lexer, but we need to figure out how
  132 // to handle ranges for refactoring in general first - there is no obvious
  133 // good way how to integrate this into the Lexer yet.
  134 static int getRangeSize(const SourceManager &Sources,
  135                         const CharSourceRange &Range,
  136                         const LangOptions &LangOpts) {
  137   SourceLocation SpellingBegin = Sources.getSpellingLoc(Range.getBegin());
  138   SourceLocation SpellingEnd = Sources.getSpellingLoc(Range.getEnd());
  139   std::pair<FileID, unsigned> Start = Sources.getDecomposedLoc(SpellingBegin);
  140   std::pair<FileID, unsigned> End = Sources.getDecomposedLoc(SpellingEnd);
  141   if (Start.first != End.first) return -1;
  142   if (Range.isTokenRange())
  143     End.second += Lexer::MeasureTokenLength(SpellingEnd, Sources, LangOpts);
  144   return End.second - Start.second;
  145 }
  146 
  147 void Replacement::setFromSourceRange(const SourceManager &Sources,
  148                                      const CharSourceRange &Range,
  149                                      StringRef ReplacementText,
  150                                      const LangOptions &LangOpts) {
  151   setFromSourceLocation(Sources, Sources.getSpellingLoc(Range.getBegin()),
  152                         getRangeSize(Sources, Range, LangOpts),
  153                         ReplacementText);
  154 }
  155 
  156 Replacement
  157 Replacements::getReplacementInChangedCode(const Replacement &R) const {
  158   unsigned NewStart = getShiftedCodePosition(R.getOffset());
  159   unsigned NewEnd = getShiftedCodePosition(R.getOffset() + R.getLength());
  160   return Replacement(R.getFilePath(), NewStart, NewEnd - NewStart,
  161                      R.getReplacementText());
  162 }
  163 
  164 static std::string getReplacementErrString(replacement_error Err) {
  165   switch (Err) {
  166   case replacement_error::fail_to_apply:
  167     return "Failed to apply a replacement.";
  168   case replacement_error::wrong_file_path:
  169     return "The new replacement's file path is different from the file path of "
  170            "existing replacements";
  171   case replacement_error::overlap_conflict:
  172     return "The new replacement overlaps with an existing replacement.";
  173   case replacement_error::insert_conflict:
  174     return "The new insertion has the same insert location as an existing "
  175            "replacement.";
  176   }
  177   llvm_unreachable("A value of replacement_error has no message.");
  178 }
  179 
  180 std::string ReplacementError::message() const {
  181   std::string Message = getReplacementErrString(Err);
  182   if (NewReplacement.hasValue())
  183     Message += "\nNew replacement: " + NewReplacement->toString();
  184   if (ExistingReplacement.hasValue())
  185     Message += "\nExisting replacement: " + ExistingReplacement->toString();
  186   return Message;
  187 }
  188 
  189 char ReplacementError::ID = 0;
  190 
  191 Replacements Replacements::getCanonicalReplacements() const {
  192   std::vector<Replacement> NewReplaces;
  193   // Merge adjacent replacements.
  194   for (const auto &R : Replaces) {
  195     if (NewReplaces.empty()) {
  196       NewReplaces.push_back(R);
  197       continue;
  198     }
  199     auto &Prev = NewReplaces.back();
  200     unsigned PrevEnd = Prev.getOffset() + Prev.getLength();
  201     if (PrevEnd < R.getOffset()) {
  202       NewReplaces.push_back(R);
  203     } else {
  204       assert(PrevEnd == R.getOffset() &&
  205              "Existing replacements must not overlap.");
  206       Replacement NewR(
  207           R.getFilePath(), Prev.getOffset(), Prev.getLength() + R.getLength(),
  208           (Prev.getReplacementText() + R.getReplacementText()).str());
  209       Prev = NewR;
  210     }
  211   }
  212   ReplacementsImpl NewReplacesImpl(NewReplaces.begin(), NewReplaces.end());
  213   return Replacements(NewReplacesImpl.begin(), NewReplacesImpl.end());
  214 }
  215 
  216 // `R` and `Replaces` are order-independent if applying them in either order
  217 // has the same effect, so we need to compare replacements associated to
  218 // applying them in either order.
  219 llvm::Expected<Replacements>
  220 Replacements::mergeIfOrderIndependent(const Replacement &R) const {
  221   Replacements Rs(R);
  222   // A Replacements set containing a single replacement that is `R` referring to
  223   // the code after the existing replacements `Replaces` are applied.
  224   Replacements RsShiftedByReplaces(getReplacementInChangedCode(R));
  225   // A Replacements set that is `Replaces` referring to the code after `R` is
  226   // applied.
  227   Replacements ReplacesShiftedByRs;
  228   for (const auto &Replace : Replaces)
  229     ReplacesShiftedByRs.Replaces.insert(
  230         Rs.getReplacementInChangedCode(Replace));
  231   // This is equivalent to applying `Replaces` first and then `R`.
  232   auto MergeShiftedRs = merge(RsShiftedByReplaces);
  233   // This is equivalent to applying `R` first and then `Replaces`.
  234   auto MergeShiftedReplaces = Rs.merge(ReplacesShiftedByRs);
  235 
  236   // Since empty or segmented replacements around existing replacements might be
  237   // produced above, we need to compare replacements in canonical forms.
  238   if (MergeShiftedRs.getCanonicalReplacements() ==
  239       MergeShiftedReplaces.getCanonicalReplacements())
  240     return MergeShiftedRs;
  241   return llvm::make_error<ReplacementError>(replacement_error::overlap_conflict,
  242                                             R, *Replaces.begin());
  243 }
  244 
  245 llvm::Error Replacements::add(const Replacement &R) {
  246   // Check the file path.
  247   if (!Replaces.empty() && R.getFilePath() != Replaces.begin()->getFilePath())
  248     return llvm::make_error<ReplacementError>(
  249         replacement_error::wrong_file_path, R, *Replaces.begin());
  250 
  251   // Special-case header insertions.
  252   if (R.getOffset() == std::numeric_limits<unsigned>::max()) {
  253     Replaces.insert(R);
  254     return llvm::Error::success();
  255   }
  256 
  257   // This replacement cannot conflict with replacements that end before
  258   // this replacement starts or start after this replacement ends.
  259   // We also know that there currently are no overlapping replacements.
  260   // Thus, we know that all replacements that start after the end of the current
  261   // replacement cannot overlap.
  262   Replacement AtEnd(R.getFilePath(), R.getOffset() + R.getLength(), 0, "");
  263 
  264   // Find the first entry that starts after or at the end of R. Note that
  265   // entries that start at the end can still be conflicting if R is an
  266   // insertion.
  267   auto I = Replaces.lower_bound(AtEnd);
  268   // If `I` starts at the same offset as `R`, `R` must be an insertion.
  269   if (I != Replaces.end() && R.getOffset() == I->getOffset()) {
  270     assert(R.getLength() == 0);
  271     // `I` is also an insertion, `R` and `I` conflict.
  272     if (I->getLength() == 0) {
  273       // Check if two insertions are order-indepedent: if inserting them in
  274       // either order produces the same text, they are order-independent.
  275       if ((R.getReplacementText() + I->getReplacementText()).str() !=
  276           (I->getReplacementText() + R.getReplacementText()).str())
  277         return llvm::make_error<ReplacementError>(
  278             replacement_error::insert_conflict, R, *I);
  279       // If insertions are order-independent, we can merge them.
  280       Replacement NewR(
  281           R.getFilePath(), R.getOffset(), 0,
  282           (R.getReplacementText() + I->getReplacementText()).str());
  283       Replaces.erase(I);
  284       Replaces.insert(std::move(NewR));
  285       return llvm::Error::success();
  286     }
  287     // Insertion `R` is adjacent to a non-insertion replacement `I`, so they
  288     // are order-independent. It is safe to assume that `R` will not conflict
  289     // with any replacement before `I` since all replacements before `I` must
  290     // either end before `R` or end at `R` but has length > 0 (if the
  291     // replacement before `I` is an insertion at `R`, it would have been `I`
  292     // since it is a lower bound of `AtEnd` and ordered before the current `I`
  293     // in the set).
  294     Replaces.insert(R);
  295     return llvm::Error::success();
  296   }
  297 
  298   // `I` is the smallest iterator (after `R`) whose entry cannot overlap.
  299   // If that is begin(), there are no overlaps.
  300   if (I == Replaces.begin()) {
  301     Replaces.insert(R);
  302     return llvm::Error::success();
  303   }
  304   --I;
  305   auto Overlap = [](const Replacement &R1, const Replacement &R2) -> bool {
  306     return Range(R1.getOffset(), R1.getLength())
  307         .overlapsWith(Range(R2.getOffset(), R2.getLength()));
  308   };
  309   // If the previous entry does not overlap, we know that entries before it
  310   // can also not overlap.
  311   if (!Overlap(R, *I)) {
  312     // If `R` and `I` do not have the same offset, it is safe to add `R` since
  313     // it must come after `I`. Otherwise:
  314     //   - If `R` is an insertion, `I` must not be an insertion since it would
  315     //   have come after `AtEnd`.
  316     //   - If `R` is not an insertion, `I` must be an insertion; otherwise, `R`
  317     //   and `I` would have overlapped.
  318     // In either case, we can safely insert `R`.
  319     Replaces.insert(R);
  320   } else {
  321     // `I` overlaps with `R`. We need to check `R` against all overlapping
  322     // replacements to see if they are order-indepedent. If they are, merge `R`
  323     // with them and replace them with the merged replacements.
  324     auto MergeBegin = I;
  325     auto MergeEnd = std::next(I);
  326     while (I != Replaces.begin()) {
  327       --I;
  328       // If `I` doesn't overlap with `R`, don't merge it.
  329       if (!Overlap(R, *I))
  330         break;
  331       MergeBegin = I;
  332     }
  333     Replacements OverlapReplaces(MergeBegin, MergeEnd);
  334     llvm::Expected<Replacements> Merged =
  335         OverlapReplaces.mergeIfOrderIndependent(R);
  336     if (!Merged)
  337       return Merged.takeError();
  338     Replaces.erase(MergeBegin, MergeEnd);
  339     Replaces.insert(Merged->begin(), Merged->end());
  340   }
  341   return llvm::Error::success();
  342 }
  343 
  344 namespace {
  345 
  346 // Represents a merged replacement, i.e. a replacement consisting of multiple
  347 // overlapping replacements from 'First' and 'Second' in mergeReplacements.
  348 //
  349 // Position projection:
  350 // Offsets and lengths of the replacements can generally refer to two different
  351 // coordinate spaces. Replacements from 'First' refer to the original text
  352 // whereas replacements from 'Second' refer to the text after applying 'First'.
  353 //
  354 // MergedReplacement always operates in the coordinate space of the original
  355 // text, i.e. transforms elements from 'Second' to take into account what was
  356 // changed based on the elements from 'First'.
  357 //
  358 // We can correctly calculate this projection as we look at the replacements in
  359 // order of strictly increasing offsets.
  360 //
  361 // Invariants:
  362 // * We always merge elements from 'First' into elements from 'Second' and vice
  363 //   versa. Within each set, the replacements are non-overlapping.
  364 // * We only extend to the right, i.e. merge elements with strictly increasing
  365 //   offsets.
  366 class MergedReplacement {
  367 public:
  368   MergedReplacement(const Replacement &R, bool MergeSecond, int D)
  369       : MergeSecond(MergeSecond), Delta(D), FilePath(R.getFilePath()),
  370         Offset(R.getOffset() + (MergeSecond ? 0 : Delta)), Length(R.getLength()),
  371         Text(R.getReplacementText()) {
  372     Delta += MergeSecond ? 0 : Text.size() - Length;
  373     DeltaFirst = MergeSecond ? Text.size() - Length : 0;
  374   }
  375 
  376   // Merges the next element 'R' into this merged element. As we always merge
  377   // from 'First' into 'Second' or vice versa, the MergedReplacement knows what
  378   // set the next element is coming from.
  379   void merge(const Replacement &R) {
  380     if (MergeSecond) {
  381       unsigned REnd = R.getOffset() + Delta + R.getLength();
  382       unsigned End = Offset + Text.size();
  383       if (REnd > End) {
  384         Length += REnd - End;
  385         MergeSecond = false;
  386       }
  387       StringRef TextRef = Text;
  388       StringRef Head = TextRef.substr(0, R.getOffset() + Delta - Offset);
  389       StringRef Tail = TextRef.substr(REnd - Offset);
  390       Text = (Head + R.getReplacementText() + Tail).str();
  391       Delta += R.getReplacementText().size() - R.getLength();
  392     } else {
  393       unsigned End = Offset + Length;
  394       StringRef RText = R.getReplacementText();
  395       StringRef Tail = RText.substr(End - R.getOffset());
  396       Text = (Text + Tail).str();
  397       if (R.getOffset() + RText.size() > End) {
  398         Length = R.getOffset() + R.getLength() - Offset;
  399         MergeSecond = true;
  400       } else {
  401         Length += R.getLength() - RText.size();
  402       }
  403       DeltaFirst += RText.size() - R.getLength();
  404     }
  405   }
  406 
  407   // Returns 'true' if 'R' starts strictly after the MergedReplacement and thus
  408   // doesn't need to be merged.
  409   bool endsBefore(const Replacement &R) const {
  410     if (MergeSecond)
  411       return Offset + Text.size() < R.getOffset() + Delta;
  412     return Offset + Length < R.getOffset();
  413   }
  414 
  415   // Returns 'true' if an element from the second set should be merged next.
  416   bool mergeSecond() const { return MergeSecond; }
  417 
  418   int deltaFirst() const { return DeltaFirst; }
  419   Replacement asReplacement() const { return {FilePath, Offset, Length, Text}; }
  420 
  421 private:
  422   bool MergeSecond;
  423 
  424   // Amount of characters that elements from 'Second' need to be shifted by in
  425   // order to refer to the original text.
  426   int Delta;
  427 
  428   // Sum of all deltas (text-length - length) of elements from 'First' merged
  429   // into this element. This is used to update 'Delta' once the
  430   // MergedReplacement is completed.
  431   int DeltaFirst;
  432 
  433   // Data of the actually merged replacement. FilePath and Offset aren't changed
  434   // as the element is only extended to the right.
  435   const StringRef FilePath;
  436   const unsigned Offset;
  437   unsigned Length;
  438   std::string Text;
  439 };
  440 
  441 } // namespace
  442 
  443 Replacements Replacements::merge(const Replacements &ReplacesToMerge) const {
  444   if (empty() || ReplacesToMerge.empty())
  445     return empty() ? ReplacesToMerge : *this;
  446 
  447   auto &First = Replaces;
  448   auto &Second = ReplacesToMerge.Replaces;
  449   // Delta is the amount of characters that replacements from 'Second' need to
  450   // be shifted so that their offsets refer to the original text.
  451   int Delta = 0;
  452   ReplacementsImpl Result;
  453 
  454   // Iterate over both sets and always add the next element (smallest total
  455   // Offset) from either 'First' or 'Second'. Merge that element with
  456   // subsequent replacements as long as they overlap. See more details in the
  457   // comment on MergedReplacement.
  458   for (auto FirstI = First.begin(), SecondI = Second.begin();
  459        FirstI != First.end() || SecondI != Second.end();) {
  460     bool NextIsFirst = SecondI == Second.end() ||
  461                        (FirstI != First.end() &&
  462                         FirstI->getOffset() < SecondI->getOffset() + Delta);
  463     MergedReplacement Merged(NextIsFirst ? *FirstI : *SecondI, NextIsFirst,
  464                              Delta);
  465     ++(NextIsFirst ? FirstI : SecondI);
  466 
  467     while ((Merged.mergeSecond() && SecondI != Second.end()) ||
  468            (!Merged.mergeSecond() && FirstI != First.end())) {
  469       auto &I = Merged.mergeSecond() ? SecondI : FirstI;
  470       if (Merged.endsBefore(*I))
  471         break;
  472       Merged.merge(*I);
  473       ++I;
  474     }
  475     Delta -= Merged.deltaFirst();
  476     Result.insert(Merged.asReplacement());
  477   }
  478   return Replacements(Result.begin(), Result.end());
  479 }
  480 
  481 // Combines overlapping ranges in \p Ranges and sorts the combined ranges.
  482 // Returns a set of non-overlapping and sorted ranges that is equivalent to
  483 // \p Ranges.
  484 static std::vector<Range> combineAndSortRanges(std::vector<Range> Ranges) {
  485   llvm::sort(Ranges, [](const Range &LHS, const Range &RHS) {
  486     if (LHS.getOffset() != RHS.getOffset())
  487       return LHS.getOffset() < RHS.getOffset();
  488     return LHS.getLength() < RHS.getLength();
  489   });
  490   std::vector<Range> Result;
  491   for (const auto &R : Ranges) {
  492     if (Result.empty() ||
  493         Result.back().getOffset() + Result.back().getLength() < R.getOffset()) {
  494       Result.push_back(R);
  495     } else {
  496       unsigned NewEnd =
  497           std::max(Result.back().getOffset() + Result.back().getLength(),
  498                    R.getOffset() + R.getLength());
  499       Result[Result.size() - 1] =
  500           Range(Result.back().getOffset(), NewEnd - Result.back().getOffset());
  501     }
  502   }
  503   return Result;
  504 }
  505 
  506 namespace clang {
  507 namespace tooling {
  508 
  509 std::vector<Range>
  510 calculateRangesAfterReplacements(const Replacements &Replaces,
  511                                  const std::vector<Range> &Ranges) {
  512   // To calculate the new ranges,
  513   //   - Turn \p Ranges into Replacements at (offset, length) with an empty
  514   //     (unimportant) replacement text of length "length".
  515   //   - Merge with \p Replaces.
  516   //   - The new ranges will be the affected ranges of the merged replacements.
  517   auto MergedRanges = combineAndSortRanges(Ranges);
  518   if (Replaces.empty())
  519     return MergedRanges;
  520   tooling::Replacements FakeReplaces;
  521   for (const auto &R : MergedRanges) {
  522     llvm::cantFail(
  523         FakeReplaces.add(Replacement(Replaces.begin()->getFilePath(),
  524                                      R.getOffset(), R.getLength(),
  525                                      std::string(R.getLength(), ' '))),
  526         "Replacements must not conflict since ranges have been merged.");
  527   }
  528   return FakeReplaces.merge(Replaces).getAffectedRanges();
  529 }
  530 
  531 } // namespace tooling
  532 } // namespace clang
  533 
  534 std::vector<Range> Replacements::getAffectedRanges() const {
  535   std::vector<Range> ChangedRanges;
  536   int Shift = 0;
  537   for (const auto &R : Replaces) {
  538     unsigned Offset = R.getOffset() + Shift;
  539     unsigned Length = R.getReplacementText().size();
  540     Shift += Length - R.getLength();
  541     ChangedRanges.push_back(Range(Offset, Length));
  542   }
  543   return combineAndSortRanges(ChangedRanges);
  544 }
  545 
  546 unsigned Replacements::getShiftedCodePosition(unsigned Position) const {
  547   unsigned Offset = 0;
  548   for (const auto &R : Replaces) {
  549     if (R.getOffset() + R.getLength() <= Position) {
  550       Offset += R.getReplacementText().size() - R.getLength();
  551       continue;
  552     }
  553     if (R.getOffset() < Position &&
  554         R.getOffset() + R.getReplacementText().size() <= Position) {
  555       Position = R.getOffset() + R.getReplacementText().size();
  556       if (!R.getReplacementText().empty())
  557         Position--;
  558     }
  559     break;
  560   }
  561   return Position + Offset;
  562 }
  563 
  564 namespace clang {
  565 namespace tooling {
  566 
  567 bool applyAllReplacements(const Replacements &Replaces, Rewriter &Rewrite) {
  568   bool Result = true;
  569   for (auto I = Replaces.rbegin(), E = Replaces.rend(); I != E; ++I) {
  570     if (I->isApplicable()) {
  571       Result = I->apply(Rewrite) && Result;
  572     } else {
  573       Result = false;
  574     }
  575   }
  576   return Result;
  577 }
  578 
  579 llvm::Expected<std::string> applyAllReplacements(StringRef Code,
  580                                                 const Replacements &Replaces) {
  581   if (Replaces.empty())
  582     return Code.str();
  583 
  584   IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> InMemoryFileSystem(
  585       new llvm::vfs::InMemoryFileSystem);
  586   FileManager Files(FileSystemOptions(), InMemoryFileSystem);
  587   DiagnosticsEngine Diagnostics(
  588       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
  589       new DiagnosticOptions);
  590   SourceManager SourceMgr(Diagnostics, Files);
  591   Rewriter Rewrite(SourceMgr, LangOptions());
  592   InMemoryFileSystem->addFile(
  593       "<stdin>", 0, llvm::MemoryBuffer::getMemBuffer(Code, "<stdin>"));
  594   FileID ID = SourceMgr.createFileID(Files.getFile("<stdin>"), SourceLocation(),
  595                                      clang::SrcMgr::C_User);
  596   for (auto I = Replaces.rbegin(), E = Replaces.rend(); I != E; ++I) {
  597     Replacement Replace("<stdin>", I->getOffset(), I->getLength(),
  598                         I->getReplacementText());
  599     if (!Replace.apply(Rewrite))
  600       return llvm::make_error<ReplacementError>(
  601           replacement_error::fail_to_apply, Replace);
  602   }
  603   std::string Result;
  604   llvm::raw_string_ostream OS(Result);
  605   Rewrite.getEditBuffer(ID).write(OS);
  606   OS.flush();
  607   return Result;
  608 }
  609 
  610 std::map<std::string, Replacements> groupReplacementsByFile(
  611     FileManager &FileMgr,
  612     const std::map<std::string, Replacements> &FileToReplaces) {
  613   std::map<std::string, Replacements> Result;
  614   llvm::SmallPtrSet<const FileEntry *, 16> ProcessedFileEntries;
  615   for (const auto &Entry : FileToReplaces) {
  616     const FileEntry *FE = FileMgr.getFile(Entry.first);
  617     if (!FE)
  618       llvm::errs() << "File path " << Entry.first << " is invalid.\n";
  619     else if (ProcessedFileEntries.insert(FE).second)
  620       Result[Entry.first] = std::move(Entry.second);
  621   }
  622   return Result;
  623 }
  624 
  625 } // namespace tooling
  626 } // namespace clang