10b57cec5SDimitry Andric //===- Replacement.cpp - Framework for clang refactoring tools ------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // Implements classes to support/store refactorings.
100b57cec5SDimitry Andric //
110b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
120b57cec5SDimitry Andric
130b57cec5SDimitry Andric #include "clang/Tooling/Core/Replacement.h"
140b57cec5SDimitry Andric #include "clang/Basic/Diagnostic.h"
150b57cec5SDimitry Andric #include "clang/Basic/DiagnosticIDs.h"
160b57cec5SDimitry Andric #include "clang/Basic/DiagnosticOptions.h"
170b57cec5SDimitry Andric #include "clang/Basic/FileManager.h"
180b57cec5SDimitry Andric #include "clang/Basic/FileSystemOptions.h"
190b57cec5SDimitry Andric #include "clang/Basic/SourceLocation.h"
200b57cec5SDimitry Andric #include "clang/Basic/SourceManager.h"
210b57cec5SDimitry Andric #include "clang/Lex/Lexer.h"
220b57cec5SDimitry Andric #include "clang/Rewrite/Core/RewriteBuffer.h"
230b57cec5SDimitry Andric #include "clang/Rewrite/Core/Rewriter.h"
240b57cec5SDimitry Andric #include "llvm/ADT/IntrusiveRefCntPtr.h"
250b57cec5SDimitry Andric #include "llvm/ADT/SmallPtrSet.h"
260b57cec5SDimitry Andric #include "llvm/ADT/StringRef.h"
270b57cec5SDimitry Andric #include "llvm/Support/Error.h"
280b57cec5SDimitry Andric #include "llvm/Support/ErrorHandling.h"
290b57cec5SDimitry Andric #include "llvm/Support/MemoryBuffer.h"
300b57cec5SDimitry Andric #include "llvm/Support/VirtualFileSystem.h"
310b57cec5SDimitry Andric #include "llvm/Support/raw_ostream.h"
320b57cec5SDimitry Andric #include <algorithm>
330b57cec5SDimitry Andric #include <cassert>
340b57cec5SDimitry Andric #include <limits>
350b57cec5SDimitry Andric #include <map>
360b57cec5SDimitry Andric #include <string>
370b57cec5SDimitry Andric #include <utility>
380b57cec5SDimitry Andric #include <vector>
390b57cec5SDimitry Andric
400b57cec5SDimitry Andric using namespace clang;
410b57cec5SDimitry Andric using namespace tooling;
420b57cec5SDimitry Andric
430b57cec5SDimitry Andric static const char * const InvalidLocation = "";
440b57cec5SDimitry Andric
Replacement()450b57cec5SDimitry Andric Replacement::Replacement() : FilePath(InvalidLocation) {}
460b57cec5SDimitry Andric
Replacement(StringRef FilePath,unsigned Offset,unsigned Length,StringRef ReplacementText)470b57cec5SDimitry Andric Replacement::Replacement(StringRef FilePath, unsigned Offset, unsigned Length,
480b57cec5SDimitry Andric StringRef ReplacementText)
495ffd83dbSDimitry Andric : FilePath(std::string(FilePath)), ReplacementRange(Offset, Length),
505ffd83dbSDimitry Andric ReplacementText(std::string(ReplacementText)) {}
510b57cec5SDimitry Andric
Replacement(const SourceManager & Sources,SourceLocation Start,unsigned Length,StringRef ReplacementText)520b57cec5SDimitry Andric Replacement::Replacement(const SourceManager &Sources, SourceLocation Start,
530b57cec5SDimitry Andric unsigned Length, StringRef ReplacementText) {
540b57cec5SDimitry Andric setFromSourceLocation(Sources, Start, Length, ReplacementText);
550b57cec5SDimitry Andric }
560b57cec5SDimitry Andric
Replacement(const SourceManager & Sources,const CharSourceRange & Range,StringRef ReplacementText,const LangOptions & LangOpts)570b57cec5SDimitry Andric Replacement::Replacement(const SourceManager &Sources,
580b57cec5SDimitry Andric const CharSourceRange &Range,
590b57cec5SDimitry Andric StringRef ReplacementText,
600b57cec5SDimitry Andric const LangOptions &LangOpts) {
610b57cec5SDimitry Andric setFromSourceRange(Sources, Range, ReplacementText, LangOpts);
620b57cec5SDimitry Andric }
630b57cec5SDimitry Andric
isApplicable() const640b57cec5SDimitry Andric bool Replacement::isApplicable() const {
650b57cec5SDimitry Andric return FilePath != InvalidLocation;
660b57cec5SDimitry Andric }
670b57cec5SDimitry Andric
apply(Rewriter & Rewrite) const680b57cec5SDimitry Andric bool Replacement::apply(Rewriter &Rewrite) const {
690b57cec5SDimitry Andric SourceManager &SM = Rewrite.getSourceMgr();
705f757f3fSDimitry Andric auto Entry = SM.getFileManager().getOptionalFileRef(FilePath);
710b57cec5SDimitry Andric if (!Entry)
720b57cec5SDimitry Andric return false;
730b57cec5SDimitry Andric
74a7dea167SDimitry Andric FileID ID = SM.getOrCreateFileID(*Entry, SrcMgr::C_User);
750b57cec5SDimitry Andric const SourceLocation Start =
760b57cec5SDimitry Andric SM.getLocForStartOfFile(ID).
770b57cec5SDimitry Andric getLocWithOffset(ReplacementRange.getOffset());
780b57cec5SDimitry Andric // ReplaceText returns false on success.
790b57cec5SDimitry Andric // ReplaceText only fails if the source location is not a file location, in
800b57cec5SDimitry Andric // which case we already returned false earlier.
810b57cec5SDimitry Andric bool RewriteSucceeded = !Rewrite.ReplaceText(
820b57cec5SDimitry Andric Start, ReplacementRange.getLength(), ReplacementText);
830b57cec5SDimitry Andric assert(RewriteSucceeded);
840b57cec5SDimitry Andric return RewriteSucceeded;
850b57cec5SDimitry Andric }
860b57cec5SDimitry Andric
toString() const870b57cec5SDimitry Andric std::string Replacement::toString() const {
880b57cec5SDimitry Andric std::string Result;
890b57cec5SDimitry Andric llvm::raw_string_ostream Stream(Result);
900b57cec5SDimitry Andric Stream << FilePath << ": " << ReplacementRange.getOffset() << ":+"
910b57cec5SDimitry Andric << ReplacementRange.getLength() << ":\"" << ReplacementText << "\"";
920b57cec5SDimitry Andric return Stream.str();
930b57cec5SDimitry Andric }
940b57cec5SDimitry Andric
950b57cec5SDimitry Andric namespace clang {
960b57cec5SDimitry Andric namespace tooling {
970b57cec5SDimitry Andric
operator <(const Replacement & LHS,const Replacement & RHS)980b57cec5SDimitry Andric bool operator<(const Replacement &LHS, const Replacement &RHS) {
990b57cec5SDimitry Andric if (LHS.getOffset() != RHS.getOffset())
1000b57cec5SDimitry Andric return LHS.getOffset() < RHS.getOffset();
1010b57cec5SDimitry Andric
1020b57cec5SDimitry Andric if (LHS.getLength() != RHS.getLength())
1030b57cec5SDimitry Andric return LHS.getLength() < RHS.getLength();
1040b57cec5SDimitry Andric
1050b57cec5SDimitry Andric if (LHS.getFilePath() != RHS.getFilePath())
1060b57cec5SDimitry Andric return LHS.getFilePath() < RHS.getFilePath();
1070b57cec5SDimitry Andric return LHS.getReplacementText() < RHS.getReplacementText();
1080b57cec5SDimitry Andric }
1090b57cec5SDimitry Andric
operator ==(const Replacement & LHS,const Replacement & RHS)1100b57cec5SDimitry Andric bool operator==(const Replacement &LHS, const Replacement &RHS) {
1110b57cec5SDimitry Andric return LHS.getOffset() == RHS.getOffset() &&
1120b57cec5SDimitry Andric LHS.getLength() == RHS.getLength() &&
1130b57cec5SDimitry Andric LHS.getFilePath() == RHS.getFilePath() &&
1140b57cec5SDimitry Andric LHS.getReplacementText() == RHS.getReplacementText();
1150b57cec5SDimitry Andric }
1160b57cec5SDimitry Andric
1170b57cec5SDimitry Andric } // namespace tooling
1180b57cec5SDimitry Andric } // namespace clang
1190b57cec5SDimitry Andric
setFromSourceLocation(const SourceManager & Sources,SourceLocation Start,unsigned Length,StringRef ReplacementText)1200b57cec5SDimitry Andric void Replacement::setFromSourceLocation(const SourceManager &Sources,
1210b57cec5SDimitry Andric SourceLocation Start, unsigned Length,
1220b57cec5SDimitry Andric StringRef ReplacementText) {
1230b57cec5SDimitry Andric const std::pair<FileID, unsigned> DecomposedLocation =
1240b57cec5SDimitry Andric Sources.getDecomposedLoc(Start);
1255f757f3fSDimitry Andric OptionalFileEntryRef Entry =
1265f757f3fSDimitry Andric Sources.getFileEntryRefForID(DecomposedLocation.first);
1275ffd83dbSDimitry Andric this->FilePath = std::string(Entry ? Entry->getName() : InvalidLocation);
1280b57cec5SDimitry Andric this->ReplacementRange = Range(DecomposedLocation.second, Length);
1295ffd83dbSDimitry Andric this->ReplacementText = std::string(ReplacementText);
1300b57cec5SDimitry Andric }
1310b57cec5SDimitry Andric
1320b57cec5SDimitry Andric // FIXME: This should go into the Lexer, but we need to figure out how
1330b57cec5SDimitry Andric // to handle ranges for refactoring in general first - there is no obvious
1340b57cec5SDimitry Andric // good way how to integrate this into the Lexer yet.
getRangeSize(const SourceManager & Sources,const CharSourceRange & Range,const LangOptions & LangOpts)1350b57cec5SDimitry Andric static int getRangeSize(const SourceManager &Sources,
1360b57cec5SDimitry Andric const CharSourceRange &Range,
1370b57cec5SDimitry Andric const LangOptions &LangOpts) {
1380b57cec5SDimitry Andric SourceLocation SpellingBegin = Sources.getSpellingLoc(Range.getBegin());
1390b57cec5SDimitry Andric SourceLocation SpellingEnd = Sources.getSpellingLoc(Range.getEnd());
1400b57cec5SDimitry Andric std::pair<FileID, unsigned> Start = Sources.getDecomposedLoc(SpellingBegin);
1410b57cec5SDimitry Andric std::pair<FileID, unsigned> End = Sources.getDecomposedLoc(SpellingEnd);
1420b57cec5SDimitry Andric if (Start.first != End.first) return -1;
1430b57cec5SDimitry Andric if (Range.isTokenRange())
1440b57cec5SDimitry Andric End.second += Lexer::MeasureTokenLength(SpellingEnd, Sources, LangOpts);
1450b57cec5SDimitry Andric return End.second - Start.second;
1460b57cec5SDimitry Andric }
1470b57cec5SDimitry Andric
setFromSourceRange(const SourceManager & Sources,const CharSourceRange & Range,StringRef ReplacementText,const LangOptions & LangOpts)1480b57cec5SDimitry Andric void Replacement::setFromSourceRange(const SourceManager &Sources,
1490b57cec5SDimitry Andric const CharSourceRange &Range,
1500b57cec5SDimitry Andric StringRef ReplacementText,
1510b57cec5SDimitry Andric const LangOptions &LangOpts) {
1520b57cec5SDimitry Andric setFromSourceLocation(Sources, Sources.getSpellingLoc(Range.getBegin()),
1530b57cec5SDimitry Andric getRangeSize(Sources, Range, LangOpts),
1540b57cec5SDimitry Andric ReplacementText);
1550b57cec5SDimitry Andric }
1560b57cec5SDimitry Andric
1570b57cec5SDimitry Andric Replacement
getReplacementInChangedCode(const Replacement & R) const1580b57cec5SDimitry Andric Replacements::getReplacementInChangedCode(const Replacement &R) const {
1590b57cec5SDimitry Andric unsigned NewStart = getShiftedCodePosition(R.getOffset());
1600b57cec5SDimitry Andric unsigned NewEnd = getShiftedCodePosition(R.getOffset() + R.getLength());
1610b57cec5SDimitry Andric return Replacement(R.getFilePath(), NewStart, NewEnd - NewStart,
1620b57cec5SDimitry Andric R.getReplacementText());
1630b57cec5SDimitry Andric }
1640b57cec5SDimitry Andric
getReplacementErrString(replacement_error Err)1650b57cec5SDimitry Andric static std::string getReplacementErrString(replacement_error Err) {
1660b57cec5SDimitry Andric switch (Err) {
1670b57cec5SDimitry Andric case replacement_error::fail_to_apply:
1680b57cec5SDimitry Andric return "Failed to apply a replacement.";
1690b57cec5SDimitry Andric case replacement_error::wrong_file_path:
1700b57cec5SDimitry Andric return "The new replacement's file path is different from the file path of "
1710b57cec5SDimitry Andric "existing replacements";
1720b57cec5SDimitry Andric case replacement_error::overlap_conflict:
1730b57cec5SDimitry Andric return "The new replacement overlaps with an existing replacement.";
1740b57cec5SDimitry Andric case replacement_error::insert_conflict:
1750b57cec5SDimitry Andric return "The new insertion has the same insert location as an existing "
1760b57cec5SDimitry Andric "replacement.";
1770b57cec5SDimitry Andric }
1780b57cec5SDimitry Andric llvm_unreachable("A value of replacement_error has no message.");
1790b57cec5SDimitry Andric }
1800b57cec5SDimitry Andric
message() const1810b57cec5SDimitry Andric std::string ReplacementError::message() const {
1820b57cec5SDimitry Andric std::string Message = getReplacementErrString(Err);
18381ad6265SDimitry Andric if (NewReplacement)
1840b57cec5SDimitry Andric Message += "\nNew replacement: " + NewReplacement->toString();
18581ad6265SDimitry Andric if (ExistingReplacement)
1860b57cec5SDimitry Andric Message += "\nExisting replacement: " + ExistingReplacement->toString();
1870b57cec5SDimitry Andric return Message;
1880b57cec5SDimitry Andric }
1890b57cec5SDimitry Andric
1900b57cec5SDimitry Andric char ReplacementError::ID = 0;
1910b57cec5SDimitry Andric
getCanonicalReplacements() const1920b57cec5SDimitry Andric Replacements Replacements::getCanonicalReplacements() const {
1930b57cec5SDimitry Andric std::vector<Replacement> NewReplaces;
1940b57cec5SDimitry Andric // Merge adjacent replacements.
1950b57cec5SDimitry Andric for (const auto &R : Replaces) {
1960b57cec5SDimitry Andric if (NewReplaces.empty()) {
1970b57cec5SDimitry Andric NewReplaces.push_back(R);
1980b57cec5SDimitry Andric continue;
1990b57cec5SDimitry Andric }
2000b57cec5SDimitry Andric auto &Prev = NewReplaces.back();
2010b57cec5SDimitry Andric unsigned PrevEnd = Prev.getOffset() + Prev.getLength();
2020b57cec5SDimitry Andric if (PrevEnd < R.getOffset()) {
2030b57cec5SDimitry Andric NewReplaces.push_back(R);
2040b57cec5SDimitry Andric } else {
2050b57cec5SDimitry Andric assert(PrevEnd == R.getOffset() &&
2060b57cec5SDimitry Andric "Existing replacements must not overlap.");
2070b57cec5SDimitry Andric Replacement NewR(
2080b57cec5SDimitry Andric R.getFilePath(), Prev.getOffset(), Prev.getLength() + R.getLength(),
2090b57cec5SDimitry Andric (Prev.getReplacementText() + R.getReplacementText()).str());
2100b57cec5SDimitry Andric Prev = NewR;
2110b57cec5SDimitry Andric }
2120b57cec5SDimitry Andric }
2130b57cec5SDimitry Andric ReplacementsImpl NewReplacesImpl(NewReplaces.begin(), NewReplaces.end());
2140b57cec5SDimitry Andric return Replacements(NewReplacesImpl.begin(), NewReplacesImpl.end());
2150b57cec5SDimitry Andric }
2160b57cec5SDimitry Andric
2170b57cec5SDimitry Andric // `R` and `Replaces` are order-independent if applying them in either order
2180b57cec5SDimitry Andric // has the same effect, so we need to compare replacements associated to
2190b57cec5SDimitry Andric // applying them in either order.
2200b57cec5SDimitry Andric llvm::Expected<Replacements>
mergeIfOrderIndependent(const Replacement & R) const2210b57cec5SDimitry Andric Replacements::mergeIfOrderIndependent(const Replacement &R) const {
2220b57cec5SDimitry Andric Replacements Rs(R);
2230b57cec5SDimitry Andric // A Replacements set containing a single replacement that is `R` referring to
2240b57cec5SDimitry Andric // the code after the existing replacements `Replaces` are applied.
2250b57cec5SDimitry Andric Replacements RsShiftedByReplaces(getReplacementInChangedCode(R));
2260b57cec5SDimitry Andric // A Replacements set that is `Replaces` referring to the code after `R` is
2270b57cec5SDimitry Andric // applied.
2280b57cec5SDimitry Andric Replacements ReplacesShiftedByRs;
2290b57cec5SDimitry Andric for (const auto &Replace : Replaces)
2300b57cec5SDimitry Andric ReplacesShiftedByRs.Replaces.insert(
2310b57cec5SDimitry Andric Rs.getReplacementInChangedCode(Replace));
2320b57cec5SDimitry Andric // This is equivalent to applying `Replaces` first and then `R`.
2330b57cec5SDimitry Andric auto MergeShiftedRs = merge(RsShiftedByReplaces);
2340b57cec5SDimitry Andric // This is equivalent to applying `R` first and then `Replaces`.
2350b57cec5SDimitry Andric auto MergeShiftedReplaces = Rs.merge(ReplacesShiftedByRs);
2360b57cec5SDimitry Andric
2370b57cec5SDimitry Andric // Since empty or segmented replacements around existing replacements might be
2380b57cec5SDimitry Andric // produced above, we need to compare replacements in canonical forms.
2390b57cec5SDimitry Andric if (MergeShiftedRs.getCanonicalReplacements() ==
2400b57cec5SDimitry Andric MergeShiftedReplaces.getCanonicalReplacements())
2410b57cec5SDimitry Andric return MergeShiftedRs;
2420b57cec5SDimitry Andric return llvm::make_error<ReplacementError>(replacement_error::overlap_conflict,
2430b57cec5SDimitry Andric R, *Replaces.begin());
2440b57cec5SDimitry Andric }
2450b57cec5SDimitry Andric
add(const Replacement & R)2460b57cec5SDimitry Andric llvm::Error Replacements::add(const Replacement &R) {
2470b57cec5SDimitry Andric // Check the file path.
2480b57cec5SDimitry Andric if (!Replaces.empty() && R.getFilePath() != Replaces.begin()->getFilePath())
2490b57cec5SDimitry Andric return llvm::make_error<ReplacementError>(
2500b57cec5SDimitry Andric replacement_error::wrong_file_path, R, *Replaces.begin());
2510b57cec5SDimitry Andric
2520b57cec5SDimitry Andric // Special-case header insertions.
2530b57cec5SDimitry Andric if (R.getOffset() == std::numeric_limits<unsigned>::max()) {
2540b57cec5SDimitry Andric Replaces.insert(R);
2550b57cec5SDimitry Andric return llvm::Error::success();
2560b57cec5SDimitry Andric }
2570b57cec5SDimitry Andric
2580b57cec5SDimitry Andric // This replacement cannot conflict with replacements that end before
2590b57cec5SDimitry Andric // this replacement starts or start after this replacement ends.
2600b57cec5SDimitry Andric // We also know that there currently are no overlapping replacements.
2610b57cec5SDimitry Andric // Thus, we know that all replacements that start after the end of the current
2620b57cec5SDimitry Andric // replacement cannot overlap.
2630b57cec5SDimitry Andric Replacement AtEnd(R.getFilePath(), R.getOffset() + R.getLength(), 0, "");
2640b57cec5SDimitry Andric
2650b57cec5SDimitry Andric // Find the first entry that starts after or at the end of R. Note that
2660b57cec5SDimitry Andric // entries that start at the end can still be conflicting if R is an
2670b57cec5SDimitry Andric // insertion.
2680b57cec5SDimitry Andric auto I = Replaces.lower_bound(AtEnd);
2690b57cec5SDimitry Andric // If `I` starts at the same offset as `R`, `R` must be an insertion.
2700b57cec5SDimitry Andric if (I != Replaces.end() && R.getOffset() == I->getOffset()) {
2710b57cec5SDimitry Andric assert(R.getLength() == 0);
2720b57cec5SDimitry Andric // `I` is also an insertion, `R` and `I` conflict.
2730b57cec5SDimitry Andric if (I->getLength() == 0) {
274bdd1243dSDimitry Andric // Check if two insertions are order-independent: if inserting them in
2750b57cec5SDimitry Andric // either order produces the same text, they are order-independent.
2760b57cec5SDimitry Andric if ((R.getReplacementText() + I->getReplacementText()).str() !=
2770b57cec5SDimitry Andric (I->getReplacementText() + R.getReplacementText()).str())
2780b57cec5SDimitry Andric return llvm::make_error<ReplacementError>(
2790b57cec5SDimitry Andric replacement_error::insert_conflict, R, *I);
2800b57cec5SDimitry Andric // If insertions are order-independent, we can merge them.
2810b57cec5SDimitry Andric Replacement NewR(
2820b57cec5SDimitry Andric R.getFilePath(), R.getOffset(), 0,
2830b57cec5SDimitry Andric (R.getReplacementText() + I->getReplacementText()).str());
2840b57cec5SDimitry Andric Replaces.erase(I);
2850b57cec5SDimitry Andric Replaces.insert(std::move(NewR));
2860b57cec5SDimitry Andric return llvm::Error::success();
2870b57cec5SDimitry Andric }
2880b57cec5SDimitry Andric // Insertion `R` is adjacent to a non-insertion replacement `I`, so they
2890b57cec5SDimitry Andric // are order-independent. It is safe to assume that `R` will not conflict
2900b57cec5SDimitry Andric // with any replacement before `I` since all replacements before `I` must
2910b57cec5SDimitry Andric // either end before `R` or end at `R` but has length > 0 (if the
2920b57cec5SDimitry Andric // replacement before `I` is an insertion at `R`, it would have been `I`
2930b57cec5SDimitry Andric // since it is a lower bound of `AtEnd` and ordered before the current `I`
2940b57cec5SDimitry Andric // in the set).
2950b57cec5SDimitry Andric Replaces.insert(R);
2960b57cec5SDimitry Andric return llvm::Error::success();
2970b57cec5SDimitry Andric }
2980b57cec5SDimitry Andric
2990b57cec5SDimitry Andric // `I` is the smallest iterator (after `R`) whose entry cannot overlap.
3000b57cec5SDimitry Andric // If that is begin(), there are no overlaps.
3010b57cec5SDimitry Andric if (I == Replaces.begin()) {
3020b57cec5SDimitry Andric Replaces.insert(R);
3030b57cec5SDimitry Andric return llvm::Error::success();
3040b57cec5SDimitry Andric }
3050b57cec5SDimitry Andric --I;
3060b57cec5SDimitry Andric auto Overlap = [](const Replacement &R1, const Replacement &R2) -> bool {
3070b57cec5SDimitry Andric return Range(R1.getOffset(), R1.getLength())
3080b57cec5SDimitry Andric .overlapsWith(Range(R2.getOffset(), R2.getLength()));
3090b57cec5SDimitry Andric };
3100b57cec5SDimitry Andric // If the previous entry does not overlap, we know that entries before it
3110b57cec5SDimitry Andric // can also not overlap.
3120b57cec5SDimitry Andric if (!Overlap(R, *I)) {
3130b57cec5SDimitry Andric // If `R` and `I` do not have the same offset, it is safe to add `R` since
3140b57cec5SDimitry Andric // it must come after `I`. Otherwise:
3150b57cec5SDimitry Andric // - If `R` is an insertion, `I` must not be an insertion since it would
3160b57cec5SDimitry Andric // have come after `AtEnd`.
3170b57cec5SDimitry Andric // - If `R` is not an insertion, `I` must be an insertion; otherwise, `R`
3180b57cec5SDimitry Andric // and `I` would have overlapped.
3190b57cec5SDimitry Andric // In either case, we can safely insert `R`.
3200b57cec5SDimitry Andric Replaces.insert(R);
3210b57cec5SDimitry Andric } else {
3220b57cec5SDimitry Andric // `I` overlaps with `R`. We need to check `R` against all overlapping
323bdd1243dSDimitry Andric // replacements to see if they are order-independent. If they are, merge `R`
3240b57cec5SDimitry Andric // with them and replace them with the merged replacements.
3250b57cec5SDimitry Andric auto MergeBegin = I;
3260b57cec5SDimitry Andric auto MergeEnd = std::next(I);
3270b57cec5SDimitry Andric while (I != Replaces.begin()) {
3280b57cec5SDimitry Andric --I;
3290b57cec5SDimitry Andric // If `I` doesn't overlap with `R`, don't merge it.
3300b57cec5SDimitry Andric if (!Overlap(R, *I))
3310b57cec5SDimitry Andric break;
3320b57cec5SDimitry Andric MergeBegin = I;
3330b57cec5SDimitry Andric }
3340b57cec5SDimitry Andric Replacements OverlapReplaces(MergeBegin, MergeEnd);
3350b57cec5SDimitry Andric llvm::Expected<Replacements> Merged =
3360b57cec5SDimitry Andric OverlapReplaces.mergeIfOrderIndependent(R);
3370b57cec5SDimitry Andric if (!Merged)
3380b57cec5SDimitry Andric return Merged.takeError();
3390b57cec5SDimitry Andric Replaces.erase(MergeBegin, MergeEnd);
3400b57cec5SDimitry Andric Replaces.insert(Merged->begin(), Merged->end());
3410b57cec5SDimitry Andric }
3420b57cec5SDimitry Andric return llvm::Error::success();
3430b57cec5SDimitry Andric }
3440b57cec5SDimitry Andric
3450b57cec5SDimitry Andric namespace {
3460b57cec5SDimitry Andric
3470b57cec5SDimitry Andric // Represents a merged replacement, i.e. a replacement consisting of multiple
3480b57cec5SDimitry Andric // overlapping replacements from 'First' and 'Second' in mergeReplacements.
3490b57cec5SDimitry Andric //
3500b57cec5SDimitry Andric // Position projection:
3510b57cec5SDimitry Andric // Offsets and lengths of the replacements can generally refer to two different
3520b57cec5SDimitry Andric // coordinate spaces. Replacements from 'First' refer to the original text
3530b57cec5SDimitry Andric // whereas replacements from 'Second' refer to the text after applying 'First'.
3540b57cec5SDimitry Andric //
3550b57cec5SDimitry Andric // MergedReplacement always operates in the coordinate space of the original
3560b57cec5SDimitry Andric // text, i.e. transforms elements from 'Second' to take into account what was
3570b57cec5SDimitry Andric // changed based on the elements from 'First'.
3580b57cec5SDimitry Andric //
3590b57cec5SDimitry Andric // We can correctly calculate this projection as we look at the replacements in
3600b57cec5SDimitry Andric // order of strictly increasing offsets.
3610b57cec5SDimitry Andric //
3620b57cec5SDimitry Andric // Invariants:
3630b57cec5SDimitry Andric // * We always merge elements from 'First' into elements from 'Second' and vice
3640b57cec5SDimitry Andric // versa. Within each set, the replacements are non-overlapping.
3650b57cec5SDimitry Andric // * We only extend to the right, i.e. merge elements with strictly increasing
3660b57cec5SDimitry Andric // offsets.
3670b57cec5SDimitry Andric class MergedReplacement {
3680b57cec5SDimitry Andric public:
MergedReplacement(const Replacement & R,bool MergeSecond,int D)3690b57cec5SDimitry Andric MergedReplacement(const Replacement &R, bool MergeSecond, int D)
3700b57cec5SDimitry Andric : MergeSecond(MergeSecond), Delta(D), FilePath(R.getFilePath()),
3715ffd83dbSDimitry Andric Offset(R.getOffset() + (MergeSecond ? 0 : Delta)),
3725ffd83dbSDimitry Andric Length(R.getLength()), Text(std::string(R.getReplacementText())) {
3730b57cec5SDimitry Andric Delta += MergeSecond ? 0 : Text.size() - Length;
3740b57cec5SDimitry Andric DeltaFirst = MergeSecond ? Text.size() - Length : 0;
3750b57cec5SDimitry Andric }
3760b57cec5SDimitry Andric
3770b57cec5SDimitry Andric // Merges the next element 'R' into this merged element. As we always merge
3780b57cec5SDimitry Andric // from 'First' into 'Second' or vice versa, the MergedReplacement knows what
3790b57cec5SDimitry Andric // set the next element is coming from.
merge(const Replacement & R)3800b57cec5SDimitry Andric void merge(const Replacement &R) {
3810b57cec5SDimitry Andric if (MergeSecond) {
3820b57cec5SDimitry Andric unsigned REnd = R.getOffset() + Delta + R.getLength();
3830b57cec5SDimitry Andric unsigned End = Offset + Text.size();
3840b57cec5SDimitry Andric if (REnd > End) {
3850b57cec5SDimitry Andric Length += REnd - End;
3860b57cec5SDimitry Andric MergeSecond = false;
3870b57cec5SDimitry Andric }
3880b57cec5SDimitry Andric StringRef TextRef = Text;
3890b57cec5SDimitry Andric StringRef Head = TextRef.substr(0, R.getOffset() + Delta - Offset);
3900b57cec5SDimitry Andric StringRef Tail = TextRef.substr(REnd - Offset);
3910b57cec5SDimitry Andric Text = (Head + R.getReplacementText() + Tail).str();
3920b57cec5SDimitry Andric Delta += R.getReplacementText().size() - R.getLength();
3930b57cec5SDimitry Andric } else {
3940b57cec5SDimitry Andric unsigned End = Offset + Length;
3950b57cec5SDimitry Andric StringRef RText = R.getReplacementText();
3960b57cec5SDimitry Andric StringRef Tail = RText.substr(End - R.getOffset());
3970b57cec5SDimitry Andric Text = (Text + Tail).str();
3980b57cec5SDimitry Andric if (R.getOffset() + RText.size() > End) {
3990b57cec5SDimitry Andric Length = R.getOffset() + R.getLength() - Offset;
4000b57cec5SDimitry Andric MergeSecond = true;
4010b57cec5SDimitry Andric } else {
4020b57cec5SDimitry Andric Length += R.getLength() - RText.size();
4030b57cec5SDimitry Andric }
4040b57cec5SDimitry Andric DeltaFirst += RText.size() - R.getLength();
4050b57cec5SDimitry Andric }
4060b57cec5SDimitry Andric }
4070b57cec5SDimitry Andric
4080b57cec5SDimitry Andric // Returns 'true' if 'R' starts strictly after the MergedReplacement and thus
4090b57cec5SDimitry Andric // doesn't need to be merged.
endsBefore(const Replacement & R) const4100b57cec5SDimitry Andric bool endsBefore(const Replacement &R) const {
4110b57cec5SDimitry Andric if (MergeSecond)
4120b57cec5SDimitry Andric return Offset + Text.size() < R.getOffset() + Delta;
4130b57cec5SDimitry Andric return Offset + Length < R.getOffset();
4140b57cec5SDimitry Andric }
4150b57cec5SDimitry Andric
4160b57cec5SDimitry Andric // Returns 'true' if an element from the second set should be merged next.
mergeSecond() const4170b57cec5SDimitry Andric bool mergeSecond() const { return MergeSecond; }
4180b57cec5SDimitry Andric
deltaFirst() const4190b57cec5SDimitry Andric int deltaFirst() const { return DeltaFirst; }
asReplacement() const4200b57cec5SDimitry Andric Replacement asReplacement() const { return {FilePath, Offset, Length, Text}; }
4210b57cec5SDimitry Andric
4220b57cec5SDimitry Andric private:
4230b57cec5SDimitry Andric bool MergeSecond;
4240b57cec5SDimitry Andric
4250b57cec5SDimitry Andric // Amount of characters that elements from 'Second' need to be shifted by in
4260b57cec5SDimitry Andric // order to refer to the original text.
4270b57cec5SDimitry Andric int Delta;
4280b57cec5SDimitry Andric
4290b57cec5SDimitry Andric // Sum of all deltas (text-length - length) of elements from 'First' merged
4300b57cec5SDimitry Andric // into this element. This is used to update 'Delta' once the
4310b57cec5SDimitry Andric // MergedReplacement is completed.
4320b57cec5SDimitry Andric int DeltaFirst;
4330b57cec5SDimitry Andric
4340b57cec5SDimitry Andric // Data of the actually merged replacement. FilePath and Offset aren't changed
4350b57cec5SDimitry Andric // as the element is only extended to the right.
4360b57cec5SDimitry Andric const StringRef FilePath;
4370b57cec5SDimitry Andric const unsigned Offset;
4380b57cec5SDimitry Andric unsigned Length;
4390b57cec5SDimitry Andric std::string Text;
4400b57cec5SDimitry Andric };
4410b57cec5SDimitry Andric
4420b57cec5SDimitry Andric } // namespace
4430b57cec5SDimitry Andric
merge(const Replacements & ReplacesToMerge) const4440b57cec5SDimitry Andric Replacements Replacements::merge(const Replacements &ReplacesToMerge) const {
4450b57cec5SDimitry Andric if (empty() || ReplacesToMerge.empty())
4460b57cec5SDimitry Andric return empty() ? ReplacesToMerge : *this;
4470b57cec5SDimitry Andric
4480b57cec5SDimitry Andric auto &First = Replaces;
4490b57cec5SDimitry Andric auto &Second = ReplacesToMerge.Replaces;
4500b57cec5SDimitry Andric // Delta is the amount of characters that replacements from 'Second' need to
4510b57cec5SDimitry Andric // be shifted so that their offsets refer to the original text.
4520b57cec5SDimitry Andric int Delta = 0;
4530b57cec5SDimitry Andric ReplacementsImpl Result;
4540b57cec5SDimitry Andric
4550b57cec5SDimitry Andric // Iterate over both sets and always add the next element (smallest total
4560b57cec5SDimitry Andric // Offset) from either 'First' or 'Second'. Merge that element with
4570b57cec5SDimitry Andric // subsequent replacements as long as they overlap. See more details in the
4580b57cec5SDimitry Andric // comment on MergedReplacement.
4590b57cec5SDimitry Andric for (auto FirstI = First.begin(), SecondI = Second.begin();
4600b57cec5SDimitry Andric FirstI != First.end() || SecondI != Second.end();) {
4610b57cec5SDimitry Andric bool NextIsFirst = SecondI == Second.end() ||
4620b57cec5SDimitry Andric (FirstI != First.end() &&
4630b57cec5SDimitry Andric FirstI->getOffset() < SecondI->getOffset() + Delta);
4640b57cec5SDimitry Andric MergedReplacement Merged(NextIsFirst ? *FirstI : *SecondI, NextIsFirst,
4650b57cec5SDimitry Andric Delta);
4660b57cec5SDimitry Andric ++(NextIsFirst ? FirstI : SecondI);
4670b57cec5SDimitry Andric
4680b57cec5SDimitry Andric while ((Merged.mergeSecond() && SecondI != Second.end()) ||
4690b57cec5SDimitry Andric (!Merged.mergeSecond() && FirstI != First.end())) {
4700b57cec5SDimitry Andric auto &I = Merged.mergeSecond() ? SecondI : FirstI;
4710b57cec5SDimitry Andric if (Merged.endsBefore(*I))
4720b57cec5SDimitry Andric break;
4730b57cec5SDimitry Andric Merged.merge(*I);
4740b57cec5SDimitry Andric ++I;
4750b57cec5SDimitry Andric }
4760b57cec5SDimitry Andric Delta -= Merged.deltaFirst();
4770b57cec5SDimitry Andric Result.insert(Merged.asReplacement());
4780b57cec5SDimitry Andric }
4790b57cec5SDimitry Andric return Replacements(Result.begin(), Result.end());
4800b57cec5SDimitry Andric }
4810b57cec5SDimitry Andric
4820b57cec5SDimitry Andric // Combines overlapping ranges in \p Ranges and sorts the combined ranges.
4830b57cec5SDimitry Andric // Returns a set of non-overlapping and sorted ranges that is equivalent to
4840b57cec5SDimitry Andric // \p Ranges.
combineAndSortRanges(std::vector<Range> Ranges)4850b57cec5SDimitry Andric static std::vector<Range> combineAndSortRanges(std::vector<Range> Ranges) {
4860b57cec5SDimitry Andric llvm::sort(Ranges, [](const Range &LHS, const Range &RHS) {
4870b57cec5SDimitry Andric if (LHS.getOffset() != RHS.getOffset())
4880b57cec5SDimitry Andric return LHS.getOffset() < RHS.getOffset();
4890b57cec5SDimitry Andric return LHS.getLength() < RHS.getLength();
4900b57cec5SDimitry Andric });
4910b57cec5SDimitry Andric std::vector<Range> Result;
4920b57cec5SDimitry Andric for (const auto &R : Ranges) {
4930b57cec5SDimitry Andric if (Result.empty() ||
4940b57cec5SDimitry Andric Result.back().getOffset() + Result.back().getLength() < R.getOffset()) {
4950b57cec5SDimitry Andric Result.push_back(R);
4960b57cec5SDimitry Andric } else {
4970b57cec5SDimitry Andric unsigned NewEnd =
4980b57cec5SDimitry Andric std::max(Result.back().getOffset() + Result.back().getLength(),
4990b57cec5SDimitry Andric R.getOffset() + R.getLength());
5000b57cec5SDimitry Andric Result[Result.size() - 1] =
5010b57cec5SDimitry Andric Range(Result.back().getOffset(), NewEnd - Result.back().getOffset());
5020b57cec5SDimitry Andric }
5030b57cec5SDimitry Andric }
5040b57cec5SDimitry Andric return Result;
5050b57cec5SDimitry Andric }
5060b57cec5SDimitry Andric
5070b57cec5SDimitry Andric namespace clang {
5080b57cec5SDimitry Andric namespace tooling {
5090b57cec5SDimitry Andric
5100b57cec5SDimitry Andric std::vector<Range>
calculateRangesAfterReplacements(const Replacements & Replaces,const std::vector<Range> & Ranges)5110b57cec5SDimitry Andric calculateRangesAfterReplacements(const Replacements &Replaces,
5120b57cec5SDimitry Andric const std::vector<Range> &Ranges) {
5130b57cec5SDimitry Andric // To calculate the new ranges,
5140b57cec5SDimitry Andric // - Turn \p Ranges into Replacements at (offset, length) with an empty
5150b57cec5SDimitry Andric // (unimportant) replacement text of length "length".
5160b57cec5SDimitry Andric // - Merge with \p Replaces.
5170b57cec5SDimitry Andric // - The new ranges will be the affected ranges of the merged replacements.
5180b57cec5SDimitry Andric auto MergedRanges = combineAndSortRanges(Ranges);
5190b57cec5SDimitry Andric if (Replaces.empty())
5200b57cec5SDimitry Andric return MergedRanges;
5210b57cec5SDimitry Andric tooling::Replacements FakeReplaces;
5220b57cec5SDimitry Andric for (const auto &R : MergedRanges) {
5230b57cec5SDimitry Andric llvm::cantFail(
5240b57cec5SDimitry Andric FakeReplaces.add(Replacement(Replaces.begin()->getFilePath(),
5250b57cec5SDimitry Andric R.getOffset(), R.getLength(),
5260b57cec5SDimitry Andric std::string(R.getLength(), ' '))),
5270b57cec5SDimitry Andric "Replacements must not conflict since ranges have been merged.");
5280b57cec5SDimitry Andric }
5290b57cec5SDimitry Andric return FakeReplaces.merge(Replaces).getAffectedRanges();
5300b57cec5SDimitry Andric }
5310b57cec5SDimitry Andric
5320b57cec5SDimitry Andric } // namespace tooling
5330b57cec5SDimitry Andric } // namespace clang
5340b57cec5SDimitry Andric
getAffectedRanges() const5350b57cec5SDimitry Andric std::vector<Range> Replacements::getAffectedRanges() const {
5360b57cec5SDimitry Andric std::vector<Range> ChangedRanges;
5370b57cec5SDimitry Andric int Shift = 0;
5380b57cec5SDimitry Andric for (const auto &R : Replaces) {
5390b57cec5SDimitry Andric unsigned Offset = R.getOffset() + Shift;
5400b57cec5SDimitry Andric unsigned Length = R.getReplacementText().size();
5410b57cec5SDimitry Andric Shift += Length - R.getLength();
5420b57cec5SDimitry Andric ChangedRanges.push_back(Range(Offset, Length));
5430b57cec5SDimitry Andric }
5440b57cec5SDimitry Andric return combineAndSortRanges(ChangedRanges);
5450b57cec5SDimitry Andric }
5460b57cec5SDimitry Andric
getShiftedCodePosition(unsigned Position) const5470b57cec5SDimitry Andric unsigned Replacements::getShiftedCodePosition(unsigned Position) const {
5480b57cec5SDimitry Andric unsigned Offset = 0;
5490b57cec5SDimitry Andric for (const auto &R : Replaces) {
5500b57cec5SDimitry Andric if (R.getOffset() + R.getLength() <= Position) {
5510b57cec5SDimitry Andric Offset += R.getReplacementText().size() - R.getLength();
5520b57cec5SDimitry Andric continue;
5530b57cec5SDimitry Andric }
5540b57cec5SDimitry Andric if (R.getOffset() < Position &&
5550b57cec5SDimitry Andric R.getOffset() + R.getReplacementText().size() <= Position) {
5560b57cec5SDimitry Andric Position = R.getOffset() + R.getReplacementText().size();
5570b57cec5SDimitry Andric if (!R.getReplacementText().empty())
5580b57cec5SDimitry Andric Position--;
5590b57cec5SDimitry Andric }
5600b57cec5SDimitry Andric break;
5610b57cec5SDimitry Andric }
5620b57cec5SDimitry Andric return Position + Offset;
5630b57cec5SDimitry Andric }
5640b57cec5SDimitry Andric
5650b57cec5SDimitry Andric namespace clang {
5660b57cec5SDimitry Andric namespace tooling {
5670b57cec5SDimitry Andric
applyAllReplacements(const Replacements & Replaces,Rewriter & Rewrite)5680b57cec5SDimitry Andric bool applyAllReplacements(const Replacements &Replaces, Rewriter &Rewrite) {
5690b57cec5SDimitry Andric bool Result = true;
5700b57cec5SDimitry Andric for (auto I = Replaces.rbegin(), E = Replaces.rend(); I != E; ++I) {
5710b57cec5SDimitry Andric if (I->isApplicable()) {
5720b57cec5SDimitry Andric Result = I->apply(Rewrite) && Result;
5730b57cec5SDimitry Andric } else {
5740b57cec5SDimitry Andric Result = false;
5750b57cec5SDimitry Andric }
5760b57cec5SDimitry Andric }
5770b57cec5SDimitry Andric return Result;
5780b57cec5SDimitry Andric }
5790b57cec5SDimitry Andric
applyAllReplacements(StringRef Code,const Replacements & Replaces)5800b57cec5SDimitry Andric llvm::Expected<std::string> applyAllReplacements(StringRef Code,
5810b57cec5SDimitry Andric const Replacements &Replaces) {
5820b57cec5SDimitry Andric if (Replaces.empty())
5830b57cec5SDimitry Andric return Code.str();
5840b57cec5SDimitry Andric
5850b57cec5SDimitry Andric IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> InMemoryFileSystem(
5860b57cec5SDimitry Andric new llvm::vfs::InMemoryFileSystem);
5870b57cec5SDimitry Andric FileManager Files(FileSystemOptions(), InMemoryFileSystem);
5880b57cec5SDimitry Andric DiagnosticsEngine Diagnostics(
5890b57cec5SDimitry Andric IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
5900b57cec5SDimitry Andric new DiagnosticOptions);
5910b57cec5SDimitry Andric SourceManager SourceMgr(Diagnostics, Files);
5920b57cec5SDimitry Andric Rewriter Rewrite(SourceMgr, LangOptions());
5930b57cec5SDimitry Andric InMemoryFileSystem->addFile(
5940b57cec5SDimitry Andric "<stdin>", 0, llvm::MemoryBuffer::getMemBuffer(Code, "<stdin>"));
595e8d8bef9SDimitry Andric FileID ID = SourceMgr.createFileID(*Files.getOptionalFileRef("<stdin>"),
596a7dea167SDimitry Andric SourceLocation(),
5970b57cec5SDimitry Andric clang::SrcMgr::C_User);
5980b57cec5SDimitry Andric for (auto I = Replaces.rbegin(), E = Replaces.rend(); I != E; ++I) {
5990b57cec5SDimitry Andric Replacement Replace("<stdin>", I->getOffset(), I->getLength(),
6000b57cec5SDimitry Andric I->getReplacementText());
6010b57cec5SDimitry Andric if (!Replace.apply(Rewrite))
6020b57cec5SDimitry Andric return llvm::make_error<ReplacementError>(
6030b57cec5SDimitry Andric replacement_error::fail_to_apply, Replace);
6040b57cec5SDimitry Andric }
6050b57cec5SDimitry Andric std::string Result;
6060b57cec5SDimitry Andric llvm::raw_string_ostream OS(Result);
6070b57cec5SDimitry Andric Rewrite.getEditBuffer(ID).write(OS);
6080b57cec5SDimitry Andric OS.flush();
6090b57cec5SDimitry Andric return Result;
6100b57cec5SDimitry Andric }
6110b57cec5SDimitry Andric
groupReplacementsByFile(FileManager & FileMgr,const std::map<std::string,Replacements> & FileToReplaces)6120b57cec5SDimitry Andric std::map<std::string, Replacements> groupReplacementsByFile(
6130b57cec5SDimitry Andric FileManager &FileMgr,
6140b57cec5SDimitry Andric const std::map<std::string, Replacements> &FileToReplaces) {
6150b57cec5SDimitry Andric std::map<std::string, Replacements> Result;
6160b57cec5SDimitry Andric llvm::SmallPtrSet<const FileEntry *, 16> ProcessedFileEntries;
6170b57cec5SDimitry Andric for (const auto &Entry : FileToReplaces) {
618a7dea167SDimitry Andric auto FE = FileMgr.getFile(Entry.first);
6190b57cec5SDimitry Andric if (!FE)
6200b57cec5SDimitry Andric llvm::errs() << "File path " << Entry.first << " is invalid.\n";
621a7dea167SDimitry Andric else if (ProcessedFileEntries.insert(*FE).second)
6220b57cec5SDimitry Andric Result[Entry.first] = std::move(Entry.second);
6230b57cec5SDimitry Andric }
6240b57cec5SDimitry Andric return Result;
6250b57cec5SDimitry Andric }
6260b57cec5SDimitry Andric
6270b57cec5SDimitry Andric } // namespace tooling
6280b57cec5SDimitry Andric } // namespace clang
629