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