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
40using namespace clang;
41using namespace tooling;
42
43static const char * const InvalidLocation = "";
44
45Replacement::Replacement() : FilePath(InvalidLocation) {}
46
47Replacement::Replacement(StringRef FilePath, unsigned Offset, unsigned Length,
48                         StringRef ReplacementText)
49    : FilePath(FilePath), ReplacementRange(Offset, Length),
50      ReplacementText(ReplacementText) {}
51
52Replacement::Replacement(const SourceManager &Sources, SourceLocation Start,
53                         unsigned Length, StringRef ReplacementText) {
54  setFromSourceLocation(Sources, Start, Length, ReplacementText);
55}
56
57Replacement::Replacement(const SourceManager &Sources,
58                         const CharSourceRange &Range,
59                         StringRef ReplacementText,
60                         const LangOptions &LangOpts) {
61  setFromSourceRange(Sources, Range, ReplacementText, LangOpts);
62}
63
64bool Replacement::isApplicable() const {
65  return FilePath != InvalidLocation;
66}
67
68bool Replacement::apply(Rewriter &Rewrite) const {
69  SourceManager &SM = Rewrite.getSourceMgr();
70  auto 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
87std::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
95namespace clang {
96namespace tooling {
97
98bool 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
110bool 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
120void 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.
134static 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
147void 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
156Replacement
157Replacements::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
164static 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
180std::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
189char ReplacementError::ID = 0;
190
191Replacements 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.
219llvm::Expected<Replacements>
220Replacements::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
245llvm::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
344namespace {
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.
366class MergedReplacement {
367public:
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
421private:
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
443Replacements 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.
484static 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
506namespace clang {
507namespace tooling {
508
509std::vector<Range>
510calculateRangesAfterReplacements(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
534std::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
546unsigned 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
564namespace clang {
565namespace tooling {
566
567bool 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
579llvm::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>"),
595                                     SourceLocation(),
596                                     clang::SrcMgr::C_User);
597  for (auto I = Replaces.rbegin(), E = Replaces.rend(); I != E; ++I) {
598    Replacement Replace("<stdin>", I->getOffset(), I->getLength(),
599                        I->getReplacementText());
600    if (!Replace.apply(Rewrite))
601      return llvm::make_error<ReplacementError>(
602          replacement_error::fail_to_apply, Replace);
603  }
604  std::string Result;
605  llvm::raw_string_ostream OS(Result);
606  Rewrite.getEditBuffer(ID).write(OS);
607  OS.flush();
608  return Result;
609}
610
611std::map<std::string, Replacements> groupReplacementsByFile(
612    FileManager &FileMgr,
613    const std::map<std::string, Replacements> &FileToReplaces) {
614  std::map<std::string, Replacements> Result;
615  llvm::SmallPtrSet<const FileEntry *, 16> ProcessedFileEntries;
616  for (const auto &Entry : FileToReplaces) {
617    auto FE = FileMgr.getFile(Entry.first);
618    if (!FE)
619      llvm::errs() << "File path " << Entry.first << " is invalid.\n";
620    else if (ProcessedFileEntries.insert(*FE).second)
621      Result[Entry.first] = std::move(Entry.second);
622  }
623  return Result;
624}
625
626} // namespace tooling
627} // namespace clang
628