lib/Tooling/Core/Replacement.cpp - third_party/swift-clang - Git at Google

 //===--- Replacement.cpp - Framework for clang refactoring tools ----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //  Implements classes to support/store refactorings.
 //
 //===----------------------------------------------------------------------===//

 #include "clang/Tooling/Core/Replacement.h"

 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticIDs.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Rewrite/Core/Rewriter.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/raw_os_ostream.h"

 namespace clang {
 namespace tooling {

 static const char * const InvalidLocation = "";

 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,
                          const LangOptions &LangOpts) {
   setFromSourceRange(Sources, Range, ReplacementText, LangOpts);
 }

 bool Replacement::isApplicable() const {
   return FilePath != InvalidLocation;
 }

 bool Replacement::apply(Rewriter &Rewrite) const {
   SourceManager &SM = Rewrite.getSourceMgr();
   const FileEntry *Entry = SM.getFileManager().getFile(FilePath);
   if (!Entry)
     return false;

   FileID ID = SM.getOrCreateFileID(Entry, SrcMgr::C_User);
   const SourceLocation Start =
     SM.getLocForStartOfFile(ID).
     getLocWithOffset(ReplacementRange.getOffset());
   // ReplaceText returns false on success.
   // ReplaceText only fails if the source location is not a file location, in
   // which case we already returned false earlier.
   bool RewriteSucceeded = !Rewrite.ReplaceText(
       Start, ReplacementRange.getLength(), ReplacementText);
   assert(RewriteSucceeded);
   return RewriteSucceeded;
 }

 std::string Replacement::toString() const {
   std::string Result;
   llvm::raw_string_ostream Stream(Result);
   Stream << FilePath << ": " << ReplacementRange.getOffset() << ":+"
          << ReplacementRange.getLength() << ":\"" << ReplacementText << "\"";
   return Stream.str();
 }

 bool operator<(const Replacement &LHS, const Replacement &RHS) {
   if (LHS.getOffset() != RHS.getOffset())
     return LHS.getOffset() < RHS.getOffset();

   // Apply longer replacements first, specifically so that deletions are
   // executed before insertions. It is (hopefully) never the intention to
   // delete parts of newly inserted code.
   if (LHS.getLength() != RHS.getLength())
     return LHS.getLength() > RHS.getLength();

   if (LHS.getFilePath() != RHS.getFilePath())
     return LHS.getFilePath() < RHS.getFilePath();
   return LHS.getReplacementText() < RHS.getReplacementText();
 }

 bool operator==(const Replacement &LHS, const Replacement &RHS) {
   return LHS.getOffset() == RHS.getOffset() &&
          LHS.getLength() == RHS.getLength() &&
          LHS.getFilePath() == RHS.getFilePath() &&
          LHS.getReplacementText() == RHS.getReplacementText();
 }

 void Replacement::setFromSourceLocation(const SourceManager &Sources,
                                         SourceLocation Start, unsigned Length,
                                         StringRef ReplacementText) {
   const std::pair<FileID, unsigned> DecomposedLocation =
       Sources.getDecomposedLoc(Start);
   const FileEntry *Entry = Sources.getFileEntryForID(DecomposedLocation.first);
   this->FilePath = Entry ? Entry->getName() : InvalidLocation;
   this->ReplacementRange = Range(DecomposedLocation.second, Length);
   this->ReplacementText = ReplacementText;
 }

 // FIXME: This should go into the Lexer, but we need to figure out how
 // to handle ranges for refactoring in general first - there is no obvious
 // good way how to integrate this into the Lexer yet.
 static int getRangeSize(const SourceManager &Sources,
                         const CharSourceRange &Range,
                         const LangOptions &LangOpts) {
   SourceLocation SpellingBegin = Sources.getSpellingLoc(Range.getBegin());
   SourceLocation SpellingEnd = Sources.getSpellingLoc(Range.getEnd());
   std::pair<FileID, unsigned> Start = Sources.getDecomposedLoc(SpellingBegin);
   std::pair<FileID, unsigned> End = Sources.getDecomposedLoc(SpellingEnd);
   if (Start.first != End.first) return -1;
   if (Range.isTokenRange())
     End.second += Lexer::MeasureTokenLength(SpellingEnd, Sources, LangOpts);
   return End.second - Start.second;
 }

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

   // Special-case header insertions.
   if (R.getOffset() == UINT_MAX) {
     Replaces.insert(R);
     return llvm::Error::success();
   }

   // This replacement cannot conflict with replacements that end before
   // this replacement starts or start after this replacement ends.
   // We also know that there currently are no overlapping replacements.
   // 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;

   // 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())
            .overlapsWith(Range(I->getOffset(), I->getLength()))) {
     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());
 }

 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
   // set the next element is coming from.
   void merge(const Replacement &R) {
     if (MergeSecond) {
       unsigned REnd = R.getOffset() + Delta + R.getLength();
       unsigned End = Offset + Text.size();
       if (REnd > End) {
         Length += REnd - End;
         MergeSecond = false;
       }
       StringRef TextRef = Text;
       StringRef Head = TextRef.substr(0, R.getOffset() + Delta - Offset);
       StringRef Tail = TextRef.substr(REnd - Offset);
       Text = (Head + R.getReplacementText() + Tail).str();
       Delta += R.getReplacementText().size() - R.getLength();
     } else {
       unsigned End = Offset + Length;
       StringRef RText = R.getReplacementText();
       StringRef Tail = RText.substr(End - R.getOffset());
       Text = (Text + Tail).str();
       if (R.getOffset() + RText.size() > End) {
         Length = R.getOffset() + R.getLength() - Offset;
         MergeSecond = true;
       } else {
         Length += R.getLength() - RText.size();
       }
       DeltaFirst += RText.size() - R.getLength();
     }
   }

   // Returns 'true' if 'R' starts strictly after the MergedReplacement and thus
   // doesn't need to be merged.
   bool endsBefore(const Replacement &R) const {
     if (MergeSecond)
       return Offset + Text.size() < R.getOffset() + Delta;
     return Offset + Length < R.getOffset();
   }

   // Returns 'true' if an element from the second set should be merged next.
   bool mergeSecond() const { return MergeSecond; }
   int deltaFirst() const { return DeltaFirst; }
   Replacement asReplacement() const { return {FilePath, Offset, Length, Text}; }

 private:
   bool MergeSecond;

   // Amount of characters that elements from 'Second' need to be shifted by in
   // order to refer to the original text.
   int Delta;

   // Sum of all deltas (text-length - length) of elements from 'First' merged
   // into this element. This is used to update 'Delta' once the
   // MergedReplacement is completed.
   int DeltaFirst;

   // Data of the actually merged replacement. FilePath and Offset aren't changed
   // as the element is only extended to the right.
   const StringRef FilePath;
   const unsigned Offset;
   unsigned Length;
   std::string Text;
 };

 } // namespace

 Replacements Replacements::merge(const Replacements &ReplacesToMerge) const {
   if (empty() || ReplacesToMerge.empty())
     return empty() ? ReplacesToMerge : *this;

   auto &First = Replaces;
   auto &Second = ReplacesToMerge.Replaces;
   // Delta is the amount of characters that replacements from 'Second' need to
   // be shifted so that their offsets refer to the original text.
   int Delta = 0;
   ReplacementsImpl Result;

   // Iterate over both sets and always add the next element (smallest total
   // Offset) from either 'First' or 'Second'. Merge that element with
   // subsequent replacements as long as they overlap. See more details in the
   // comment on MergedReplacement.
   for (auto FirstI = First.begin(), SecondI = Second.begin();
        FirstI != First.end() || SecondI != Second.end();) {
     bool NextIsFirst = SecondI == Second.end() ||
                        (FirstI != First.end() &&
                         FirstI->getOffset() < SecondI->getOffset() + Delta);
     MergedReplacement Merged(NextIsFirst ? *FirstI : *SecondI, NextIsFirst,
                              Delta);
     ++(NextIsFirst ? FirstI : SecondI);

     while ((Merged.mergeSecond() && SecondI != Second.end()) ||
            (!Merged.mergeSecond() && FirstI != First.end())) {
       auto &I = Merged.mergeSecond() ? SecondI : FirstI;
       if (Merged.endsBefore(*I))
         break;
       Merged.merge(*I);
       ++I;
     }
     Delta -= Merged.deltaFirst();
     Result.insert(Merged.asReplacement());
   }
   return Replacements(Result.begin(), Result.end());
 }

 // Combines overlapping ranges in \p Ranges and sorts the combined ranges.
 // Returns a set of non-overlapping and sorted ranges that is equivalent to
 // \p Ranges.
 static std::vector<Range> combineAndSortRanges(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>
 calculateRangesAfterReplacements(const Replacements &Replaces,
                                  const std::vector<Range> &Ranges) {
   // To calculate the new ranges,
   //   - Turn \p Ranges into Replacements at (offset, length) with an empty
   //     (unimportant) replacement text of length "length".
   //   - Merge with \p Replaces.
   //   - The new ranges will be the affected ranges of the merged replacements.
   auto MergedRanges = combineAndSortRanges(Ranges);
   if (Replaces.empty())
     return MergedRanges;
   tooling::Replacements FakeReplaces;
   for (const auto &R : MergedRanges) {
     auto Err = FakeReplaces.add(Replacement(Replaces.begin()->getFilePath(),
                                             R.getOffset(), R.getLength(),
                                             std::string(R.getLength(), ' ')));
     assert(!Err &&
            "Replacements must not conflict since ranges have been merged.");
     (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();
     ChangedRanges.push_back(Range(Offset, Length));
   }
   return combineAndSortRanges(ChangedRanges);
 }

 unsigned Replacements::getShiftedCodePosition(unsigned Position) const {
   unsigned Offset = 0;
   for (const auto& R : Replaces) {
     if (R.getOffset() + R.getLength() <= Position) {
       Offset += R.getReplacementText().size() - R.getLength();
       continue;
     }
     if (R.getOffset() < Position &&
         R.getOffset() + R.getReplacementText().size() <= Position) {
       Position = R.getOffset() + R.getReplacementText().size();
       if (R.getReplacementText().size() > 0)
         Position--;
     }
     break;
   }
   return Position + Offset;
 }

 bool applyAllReplacements(const Replacements &Replaces, Rewriter &Rewrite) {
   bool Result = true;
   for (Replacements::const_iterator I = Replaces.begin(),
                                     E = Replaces.end();
        I != E; ++I) {
     if (I->isApplicable()) {
       Result = I->apply(Rewrite) && Result;
     } else {
       Result = false;
     }
   }
   return Result;
 }

 llvm::Expected<std::string> applyAllReplacements(StringRef Code,
                                                 const Replacements &Replaces) {
   if (Replaces.empty())
     return Code.str();

   IntrusiveRefCntPtr<vfs::InMemoryFileSystem> InMemoryFileSystem(
       new vfs::InMemoryFileSystem);
   FileManager Files(FileSystemOptions(), InMemoryFileSystem);
   DiagnosticsEngine Diagnostics(
       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
       new DiagnosticOptions);
   SourceManager SourceMgr(Diagnostics, Files);
   Rewriter Rewrite(SourceMgr, LangOptions());
   InMemoryFileSystem->addFile(
       "<stdin>", 0, llvm::MemoryBuffer::getMemBuffer(Code, "<stdin>"));
   FileID ID = SourceMgr.createFileID(Files.getFile("<stdin>"), SourceLocation(),
                                      clang::SrcMgr::C_User);
   for (Replacements::const_iterator I = Replaces.begin(), E = Replaces.end();
        I != E; ++I) {
     Replacement Replace("<stdin>", I->getOffset(), I->getLength(),
                         I->getReplacementText());
     if (!Replace.apply(Rewrite))
       return llvm::make_error<llvm::StringError>(
           "Failed to apply replacement: " + Replace.toString(),
           llvm::inconvertibleErrorCode());
   }
   std::string Result;
   llvm::raw_string_ostream OS(Result);
   Rewrite.getEditBuffer(ID).write(OS);
   OS.flush();
   return Result;
 }

 std::map<std::string, Replacements>
 groupReplacementsByFile(const Replacements &Replaces) {
   std::map<std::string, Replacements> FileToReplaces;
   for (const auto &Replace : Replaces)
     // We can ignore the Error here since \p Replaces is already conflict-free.
     FileToReplaces[Replace.getFilePath()].add(Replace);
   return FileToReplaces;
 }

 } // end namespace tooling
 } // end namespace clang
	//===--- Replacement.cpp - Framework for clang refactoring tools ----------===//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//
	//
	// Implements classes to support/store refactorings.
	//
	//===----------------------------------------------------------------------===//

	#include "clang/Tooling/Core/Replacement.h"

	#include "clang/Basic/Diagnostic.h"
	#include "clang/Basic/DiagnosticIDs.h"
	#include "clang/Basic/DiagnosticOptions.h"
	#include "clang/Basic/FileManager.h"
	#include "clang/Basic/SourceManager.h"
	#include "clang/Lex/Lexer.h"
	#include "clang/Rewrite/Core/Rewriter.h"
	#include "llvm/Support/FileSystem.h"
	#include "llvm/Support/raw_os_ostream.h"

	namespace clang {
	namespace tooling {

	static const char * const InvalidLocation = "";

	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,
	const LangOptions &LangOpts) {
	setFromSourceRange(Sources, Range, ReplacementText, LangOpts);
	}

	bool Replacement::isApplicable() const {
	return FilePath != InvalidLocation;
	}

	bool Replacement::apply(Rewriter &Rewrite) const {
	SourceManager &SM = Rewrite.getSourceMgr();
	const FileEntry *Entry = SM.getFileManager().getFile(FilePath);
	if (!Entry)
	return false;

	FileID ID = SM.getOrCreateFileID(Entry, SrcMgr::C_User);
	const SourceLocation Start =
	SM.getLocForStartOfFile(ID).
	getLocWithOffset(ReplacementRange.getOffset());
	// ReplaceText returns false on success.
	// ReplaceText only fails if the source location is not a file location, in
	// which case we already returned false earlier.
	bool RewriteSucceeded = !Rewrite.ReplaceText(
	Start, ReplacementRange.getLength(), ReplacementText);
	assert(RewriteSucceeded);
	return RewriteSucceeded;
	}

	std::string Replacement::toString() const {
	std::string Result;
	llvm::raw_string_ostream Stream(Result);
	Stream << FilePath << ": " << ReplacementRange.getOffset() << ":+"
	<< ReplacementRange.getLength() << ":\"" << ReplacementText << "\"";
	return Stream.str();
	}

	bool operator<(const Replacement &LHS, const Replacement &RHS) {
	if (LHS.getOffset() != RHS.getOffset())
	return LHS.getOffset() < RHS.getOffset();

	// Apply longer replacements first, specifically so that deletions are
	// executed before insertions. It is (hopefully) never the intention to
	// delete parts of newly inserted code.
	if (LHS.getLength() != RHS.getLength())
	return LHS.getLength() > RHS.getLength();

	if (LHS.getFilePath() != RHS.getFilePath())
	return LHS.getFilePath() < RHS.getFilePath();
	return LHS.getReplacementText() < RHS.getReplacementText();
	}

	bool operator==(const Replacement &LHS, const Replacement &RHS) {
	return LHS.getOffset() == RHS.getOffset() &&
	LHS.getLength() == RHS.getLength() &&
	LHS.getFilePath() == RHS.getFilePath() &&
	LHS.getReplacementText() == RHS.getReplacementText();
	}

	void Replacement::setFromSourceLocation(const SourceManager &Sources,
	SourceLocation Start, unsigned Length,
	StringRef ReplacementText) {
	const std::pair<FileID, unsigned> DecomposedLocation =
	Sources.getDecomposedLoc(Start);
	const FileEntry *Entry = Sources.getFileEntryForID(DecomposedLocation.first);
	this->FilePath = Entry ? Entry->getName() : InvalidLocation;
	this->ReplacementRange = Range(DecomposedLocation.second, Length);
	this->ReplacementText = ReplacementText;
	}

	// FIXME: This should go into the Lexer, but we need to figure out how
	// to handle ranges for refactoring in general first - there is no obvious
	// good way how to integrate this into the Lexer yet.
	static int getRangeSize(const SourceManager &Sources,
	const CharSourceRange &Range,
	const LangOptions &LangOpts) {
	SourceLocation SpellingBegin = Sources.getSpellingLoc(Range.getBegin());
	SourceLocation SpellingEnd = Sources.getSpellingLoc(Range.getEnd());
	std::pair<FileID, unsigned> Start = Sources.getDecomposedLoc(SpellingBegin);
	std::pair<FileID, unsigned> End = Sources.getDecomposedLoc(SpellingEnd);
	if (Start.first != End.first) return -1;
	if (Range.isTokenRange())
	End.second += Lexer::MeasureTokenLength(SpellingEnd, Sources, LangOpts);
	return End.second - Start.second;
	}

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

	// Special-case header insertions.
	if (R.getOffset() == UINT_MAX) {
	Replaces.insert(R);
	return llvm::Error::success();
	}

	// This replacement cannot conflict with replacements that end before
	// this replacement starts or start after this replacement ends.
	// We also know that there currently are no overlapping replacements.
	// 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;

	// 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())
	.overlapsWith(Range(I->getOffset(), I->getLength()))) {
	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());
	}

	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
	// set the next element is coming from.
	void merge(const Replacement &R) {
	if (MergeSecond) {
	unsigned REnd = R.getOffset() + Delta + R.getLength();
	unsigned End = Offset + Text.size();
	if (REnd > End) {
	Length += REnd - End;
	MergeSecond = false;
	}
	StringRef TextRef = Text;
	StringRef Head = TextRef.substr(0, R.getOffset() + Delta - Offset);
	StringRef Tail = TextRef.substr(REnd - Offset);
	Text = (Head + R.getReplacementText() + Tail).str();
	Delta += R.getReplacementText().size() - R.getLength();
	} else {
	unsigned End = Offset + Length;
	StringRef RText = R.getReplacementText();
	StringRef Tail = RText.substr(End - R.getOffset());
	Text = (Text + Tail).str();
	if (R.getOffset() + RText.size() > End) {
	Length = R.getOffset() + R.getLength() - Offset;
	MergeSecond = true;
	} else {
	Length += R.getLength() - RText.size();
	}
	DeltaFirst += RText.size() - R.getLength();
	}
	}

	// Returns 'true' if 'R' starts strictly after the MergedReplacement and thus
	// doesn't need to be merged.
	bool endsBefore(const Replacement &R) const {
	if (MergeSecond)
	return Offset + Text.size() < R.getOffset() + Delta;
	return Offset + Length < R.getOffset();
	}

	// Returns 'true' if an element from the second set should be merged next.
	bool mergeSecond() const { return MergeSecond; }
	int deltaFirst() const { return DeltaFirst; }
	Replacement asReplacement() const { return {FilePath, Offset, Length, Text}; }

	private:
	bool MergeSecond;

	// Amount of characters that elements from 'Second' need to be shifted by in
	// order to refer to the original text.
	int Delta;

	// Sum of all deltas (text-length - length) of elements from 'First' merged
	// into this element. This is used to update 'Delta' once the
	// MergedReplacement is completed.
	int DeltaFirst;

	// Data of the actually merged replacement. FilePath and Offset aren't changed
	// as the element is only extended to the right.
	const StringRef FilePath;
	const unsigned Offset;
	unsigned Length;
	std::string Text;
	};

	} // namespace

	Replacements Replacements::merge(const Replacements &ReplacesToMerge) const {
	if (empty() \|\| ReplacesToMerge.empty())
	return empty() ? ReplacesToMerge : *this;

	auto &First = Replaces;
	auto &Second = ReplacesToMerge.Replaces;
	// Delta is the amount of characters that replacements from 'Second' need to
	// be shifted so that their offsets refer to the original text.
	int Delta = 0;
	ReplacementsImpl Result;

	// Iterate over both sets and always add the next element (smallest total
	// Offset) from either 'First' or 'Second'. Merge that element with
	// subsequent replacements as long as they overlap. See more details in the
	// comment on MergedReplacement.
	for (auto FirstI = First.begin(), SecondI = Second.begin();
	FirstI != First.end() \|\| SecondI != Second.end();) {
	bool NextIsFirst = SecondI == Second.end() \|\|
	(FirstI != First.end() &&
	FirstI->getOffset() < SecondI->getOffset() + Delta);
	MergedReplacement Merged(NextIsFirst ? FirstI : SecondI, NextIsFirst,
	Delta);
	++(NextIsFirst ? FirstI : SecondI);

	while ((Merged.mergeSecond() && SecondI != Second.end()) \|\|
	(!Merged.mergeSecond() && FirstI != First.end())) {
	auto &I = Merged.mergeSecond() ? SecondI : FirstI;
	if (Merged.endsBefore(*I))
	break;
	Merged.merge(*I);
	++I;
	}
	Delta -= Merged.deltaFirst();
	Result.insert(Merged.asReplacement());
	}
	return Replacements(Result.begin(), Result.end());
	}

	// Combines overlapping ranges in \p Ranges and sorts the combined ranges.
	// Returns a set of non-overlapping and sorted ranges that is equivalent to
	// \p Ranges.
	static std::vector<Range> combineAndSortRanges(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>
	calculateRangesAfterReplacements(const Replacements &Replaces,
	const std::vector<Range> &Ranges) {
	// To calculate the new ranges,
	// - Turn \p Ranges into Replacements at (offset, length) with an empty
	// (unimportant) replacement text of length "length".
	// - Merge with \p Replaces.
	// - The new ranges will be the affected ranges of the merged replacements.
	auto MergedRanges = combineAndSortRanges(Ranges);
	if (Replaces.empty())
	return MergedRanges;
	tooling::Replacements FakeReplaces;
	for (const auto &R : MergedRanges) {
	auto Err = FakeReplaces.add(Replacement(Replaces.begin()->getFilePath(),
	R.getOffset(), R.getLength(),
	std::string(R.getLength(), ' ')));
	assert(!Err &&
	"Replacements must not conflict since ranges have been merged.");
	(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();
	ChangedRanges.push_back(Range(Offset, Length));
	}
	return combineAndSortRanges(ChangedRanges);
	}

	unsigned Replacements::getShiftedCodePosition(unsigned Position) const {
	unsigned Offset = 0;
	for (const auto& R : Replaces) {
	if (R.getOffset() + R.getLength() <= Position) {
	Offset += R.getReplacementText().size() - R.getLength();
	continue;
	}
	if (R.getOffset() < Position &&
	R.getOffset() + R.getReplacementText().size() <= Position) {
	Position = R.getOffset() + R.getReplacementText().size();
	if (R.getReplacementText().size() > 0)
	Position--;
	}
	break;
	}
	return Position + Offset;
	}

	bool applyAllReplacements(const Replacements &Replaces, Rewriter &Rewrite) {
	bool Result = true;
	for (Replacements::const_iterator I = Replaces.begin(),
	E = Replaces.end();
	I != E; ++I) {
	if (I->isApplicable()) {
	Result = I->apply(Rewrite) && Result;
	} else {
	Result = false;
	}
	}
	return Result;
	}

	llvm::Expected<std::string> applyAllReplacements(StringRef Code,
	const Replacements &Replaces) {
	if (Replaces.empty())
	return Code.str();

	IntrusiveRefCntPtr<vfs::InMemoryFileSystem> InMemoryFileSystem(
	new vfs::InMemoryFileSystem);
	FileManager Files(FileSystemOptions(), InMemoryFileSystem);
	DiagnosticsEngine Diagnostics(
	IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
	new DiagnosticOptions);
	SourceManager SourceMgr(Diagnostics, Files);
	Rewriter Rewrite(SourceMgr, LangOptions());
	InMemoryFileSystem->addFile(
	"<stdin>", 0, llvm::MemoryBuffer::getMemBuffer(Code, "<stdin>"));
	FileID ID = SourceMgr.createFileID(Files.getFile("<stdin>"), SourceLocation(),
	clang::SrcMgr::C_User);
	for (Replacements::const_iterator I = Replaces.begin(), E = Replaces.end();
	I != E; ++I) {
	Replacement Replace("<stdin>", I->getOffset(), I->getLength(),
	I->getReplacementText());
	if (!Replace.apply(Rewrite))
	return llvm::make_error<llvm::StringError>(
	"Failed to apply replacement: " + Replace.toString(),
	llvm::inconvertibleErrorCode());
	}
	std::string Result;
	llvm::raw_string_ostream OS(Result);
	Rewrite.getEditBuffer(ID).write(OS);
	OS.flush();
	return Result;
	}

	std::map<std::string, Replacements>
	groupReplacementsByFile(const Replacements &Replaces) {
	std::map<std::string, Replacements> FileToReplaces;
	for (const auto &Replace : Replaces)
	// We can ignore the Error here since \p Replaces is already conflict-free.
	FileToReplaces[Replace.getFilePath()].add(Replace);
	return FileToReplaces;
	}

	} // end namespace tooling
	} // end namespace clang