text: //===--- 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);
    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
  