1 //===--- Rename.cpp - Symbol-rename refactorings -----------------*- C++-*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "refactor/Rename.h"
10 #include "AST.h"
11 #include "FindTarget.h"
12 #include "Logger.h"
13 #include "ParsedAST.h"
14 #include "Selection.h"
15 #include "SourceCode.h"
16 #include "index/SymbolCollector.h"
17 #include "clang/AST/DeclCXX.h"
18 #include "clang/AST/DeclTemplate.h"
19 #include "clang/Basic/SourceLocation.h"
20 #include "clang/Tooling/Refactoring/Rename/USRFindingAction.h"
21 #include "clang/Tooling/Syntax/Tokens.h"
22 #include "llvm/ADT/None.h"
23 #include "llvm/ADT/STLExtras.h"
24 #include "llvm/Support/Casting.h"
25 #include "llvm/Support/Error.h"
26 #include "llvm/Support/FormatVariadic.h"
27 #include <algorithm>
28
29 namespace clang {
30 namespace clangd {
31 namespace {
32
filePath(const SymbolLocation & Loc,llvm::StringRef HintFilePath)33 llvm::Optional<std::string> filePath(const SymbolLocation &Loc,
34 llvm::StringRef HintFilePath) {
35 if (!Loc)
36 return None;
37 auto Path = URI::resolve(Loc.FileURI, HintFilePath);
38 if (!Path) {
39 elog("Could not resolve URI {0}: {1}", Loc.FileURI, Path.takeError());
40 return None;
41 }
42
43 return *Path;
44 }
45
46 // Returns true if the given location is expanded from any macro body.
isInMacroBody(const SourceManager & SM,SourceLocation Loc)47 bool isInMacroBody(const SourceManager &SM, SourceLocation Loc) {
48 while (Loc.isMacroID()) {
49 if (SM.isMacroBodyExpansion(Loc))
50 return true;
51 Loc = SM.getImmediateMacroCallerLoc(Loc);
52 }
53
54 return false;
55 }
56
57 // Query the index to find some other files where the Decl is referenced.
getOtherRefFile(const Decl & D,StringRef MainFile,const SymbolIndex & Index)58 llvm::Optional<std::string> getOtherRefFile(const Decl &D, StringRef MainFile,
59 const SymbolIndex &Index) {
60 RefsRequest Req;
61 // We limit the number of results, this is a correctness/performance
62 // tradeoff. We expect the number of symbol references in the current file
63 // is smaller than the limit.
64 Req.Limit = 100;
65 Req.IDs.insert(*getSymbolID(&D));
66 llvm::Optional<std::string> OtherFile;
67 Index.refs(Req, [&](const Ref &R) {
68 if (OtherFile)
69 return;
70 if (auto RefFilePath = filePath(R.Location, /*HintFilePath=*/MainFile)) {
71 if (*RefFilePath != MainFile)
72 OtherFile = *RefFilePath;
73 }
74 });
75 return OtherFile;
76 }
77
locateDeclAt(ParsedAST & AST,SourceLocation TokenStartLoc)78 llvm::DenseSet<const Decl *> locateDeclAt(ParsedAST &AST,
79 SourceLocation TokenStartLoc) {
80 unsigned Offset =
81 AST.getSourceManager().getDecomposedSpellingLoc(TokenStartLoc).second;
82
83 SelectionTree Selection(AST.getASTContext(), AST.getTokens(), Offset);
84 const SelectionTree::Node *SelectedNode = Selection.commonAncestor();
85 if (!SelectedNode)
86 return {};
87
88 llvm::DenseSet<const Decl *> Result;
89 for (const NamedDecl *D :
90 targetDecl(SelectedNode->ASTNode,
91 DeclRelation::Alias | DeclRelation::TemplatePattern)) {
92 // Get to CXXRecordDecl from constructor or destructor.
93 D = tooling::getCanonicalSymbolDeclaration(D);
94 Result.insert(D);
95 }
96 return Result;
97 }
98
99 enum ReasonToReject {
100 NoSymbolFound,
101 NoIndexProvided,
102 NonIndexable,
103 UsedOutsideFile, // for within-file rename only.
104 UnsupportedSymbol,
105 AmbiguousSymbol,
106 };
107
renameable(const Decl & RenameDecl,StringRef MainFilePath,const SymbolIndex * Index,bool CrossFile)108 llvm::Optional<ReasonToReject> renameable(const Decl &RenameDecl,
109 StringRef MainFilePath,
110 const SymbolIndex *Index,
111 bool CrossFile) {
112 // Filter out symbols that are unsupported in both rename modes.
113 if (llvm::isa<NamespaceDecl>(&RenameDecl))
114 return ReasonToReject::UnsupportedSymbol;
115 if (const auto *FD = llvm::dyn_cast<FunctionDecl>(&RenameDecl)) {
116 if (FD->isOverloadedOperator())
117 return ReasonToReject::UnsupportedSymbol;
118 }
119 // function-local symbols is safe to rename.
120 if (RenameDecl.getParentFunctionOrMethod())
121 return None;
122
123 // Check whether the symbol being rename is indexable.
124 auto &ASTCtx = RenameDecl.getASTContext();
125 bool MainFileIsHeader = isHeaderFile(MainFilePath, ASTCtx.getLangOpts());
126 bool DeclaredInMainFile =
127 isInsideMainFile(RenameDecl.getBeginLoc(), ASTCtx.getSourceManager());
128 bool IsMainFileOnly = true;
129 if (MainFileIsHeader)
130 // main file is a header, the symbol can't be main file only.
131 IsMainFileOnly = false;
132 else if (!DeclaredInMainFile)
133 IsMainFileOnly = false;
134 bool IsIndexable =
135 isa<NamedDecl>(RenameDecl) &&
136 SymbolCollector::shouldCollectSymbol(
137 cast<NamedDecl>(RenameDecl), RenameDecl.getASTContext(),
138 SymbolCollector::Options(), IsMainFileOnly);
139 if (!IsIndexable) // If the symbol is not indexable, we disallow rename.
140 return ReasonToReject::NonIndexable;
141
142 if (!CrossFile) {
143 if (!DeclaredInMainFile)
144 // We are sure the symbol is used externally, bail out early.
145 return ReasonToReject::UsedOutsideFile;
146
147 // If the symbol is declared in the main file (which is not a header), we
148 // rename it.
149 if (!MainFileIsHeader)
150 return None;
151
152 if (!Index)
153 return ReasonToReject::NoIndexProvided;
154
155 auto OtherFile = getOtherRefFile(RenameDecl, MainFilePath, *Index);
156 // If the symbol is indexable and has no refs from other files in the index,
157 // we rename it.
158 if (!OtherFile)
159 return None;
160 // If the symbol is indexable and has refs from other files in the index,
161 // we disallow rename.
162 return ReasonToReject::UsedOutsideFile;
163 }
164
165 assert(CrossFile);
166 if (!Index)
167 return ReasonToReject::NoIndexProvided;
168
169 // Blacklist symbols that are not supported yet in cross-file mode due to the
170 // limitations of our index.
171 // FIXME: Renaming templates requires to rename all related specializations,
172 // our index doesn't have this information.
173 if (RenameDecl.getDescribedTemplate())
174 return ReasonToReject::UnsupportedSymbol;
175
176 // FIXME: Renaming virtual methods requires to rename all overridens in
177 // subclasses, our index doesn't have this information.
178 // Note: Within-file rename does support this through the AST.
179 if (const auto *S = llvm::dyn_cast<CXXMethodDecl>(&RenameDecl)) {
180 if (S->isVirtual())
181 return ReasonToReject::UnsupportedSymbol;
182 }
183 return None;
184 }
185
makeError(ReasonToReject Reason)186 llvm::Error makeError(ReasonToReject Reason) {
187 auto Message = [](ReasonToReject Reason) {
188 switch (Reason) {
189 case ReasonToReject::NoSymbolFound:
190 return "there is no symbol at the given location";
191 case ReasonToReject::NoIndexProvided:
192 return "no index provided";
193 case ReasonToReject::UsedOutsideFile:
194 return "the symbol is used outside main file";
195 case ReasonToReject::NonIndexable:
196 return "symbol may be used in other files (not eligible for indexing)";
197 case ReasonToReject::UnsupportedSymbol:
198 return "symbol is not a supported kind (e.g. namespace, macro)";
199 case AmbiguousSymbol:
200 return "there are multiple symbols at the given location";
201 }
202 llvm_unreachable("unhandled reason kind");
203 };
204 return llvm::make_error<llvm::StringError>(
205 llvm::formatv("Cannot rename symbol: {0}", Message(Reason)),
206 llvm::inconvertibleErrorCode());
207 }
208
209 // Return all rename occurrences in the main file.
findOccurrencesWithinFile(ParsedAST & AST,const NamedDecl & ND)210 std::vector<SourceLocation> findOccurrencesWithinFile(ParsedAST &AST,
211 const NamedDecl &ND) {
212 // If the cursor is at the underlying CXXRecordDecl of the
213 // ClassTemplateDecl, ND will be the CXXRecordDecl. In this case, we need to
214 // get the primary template maunally.
215 // getUSRsForDeclaration will find other related symbols, e.g. virtual and its
216 // overriddens, primary template and all explicit specializations.
217 // FIXME: Get rid of the remaining tooling APIs.
218 const auto RenameDecl =
219 ND.getDescribedTemplate() ? ND.getDescribedTemplate() : &ND;
220 std::vector<std::string> RenameUSRs =
221 tooling::getUSRsForDeclaration(RenameDecl, AST.getASTContext());
222 llvm::DenseSet<SymbolID> TargetIDs;
223 for (auto &USR : RenameUSRs)
224 TargetIDs.insert(SymbolID(USR));
225
226 std::vector<SourceLocation> Results;
227 for (Decl *TopLevelDecl : AST.getLocalTopLevelDecls()) {
228 findExplicitReferences(TopLevelDecl, [&](ReferenceLoc Ref) {
229 if (Ref.Targets.empty())
230 return;
231 for (const auto *Target : Ref.Targets) {
232 auto ID = getSymbolID(Target);
233 if (!ID || TargetIDs.find(*ID) == TargetIDs.end())
234 return;
235 }
236 Results.push_back(Ref.NameLoc);
237 });
238 }
239
240 return Results;
241 }
242
243 // AST-based rename, it renames all occurrences in the main file.
244 llvm::Expected<tooling::Replacements>
renameWithinFile(ParsedAST & AST,const NamedDecl & RenameDecl,llvm::StringRef NewName)245 renameWithinFile(ParsedAST &AST, const NamedDecl &RenameDecl,
246 llvm::StringRef NewName) {
247 const SourceManager &SM = AST.getSourceManager();
248
249 tooling::Replacements FilteredChanges;
250 for (SourceLocation Loc : findOccurrencesWithinFile(AST, RenameDecl)) {
251 SourceLocation RenameLoc = Loc;
252 // We don't rename in any macro bodies, but we allow rename the symbol
253 // spelled in a top-level macro argument in the main file.
254 if (RenameLoc.isMacroID()) {
255 if (isInMacroBody(SM, RenameLoc))
256 continue;
257 RenameLoc = SM.getSpellingLoc(Loc);
258 }
259 // Filter out locations not from main file.
260 // We traverse only main file decls, but locations could come from an
261 // non-preamble #include file e.g.
262 // void test() {
263 // int f^oo;
264 // #include "use_foo.inc"
265 // }
266 if (!isInsideMainFile(RenameLoc, SM))
267 continue;
268 if (auto Err = FilteredChanges.add(tooling::Replacement(
269 SM, CharSourceRange::getTokenRange(RenameLoc), NewName)))
270 return std::move(Err);
271 }
272 return FilteredChanges;
273 }
274
toRange(const SymbolLocation & L)275 Range toRange(const SymbolLocation &L) {
276 Range R;
277 R.start.line = L.Start.line();
278 R.start.character = L.Start.column();
279 R.end.line = L.End.line();
280 R.end.character = L.End.column();
281 return R;
282 }
283
284 // Return all rename occurrences (using the index) outside of the main file,
285 // grouped by the absolute file path.
286 llvm::Expected<llvm::StringMap<std::vector<Range>>>
findOccurrencesOutsideFile(const NamedDecl & RenameDecl,llvm::StringRef MainFile,const SymbolIndex & Index)287 findOccurrencesOutsideFile(const NamedDecl &RenameDecl,
288 llvm::StringRef MainFile, const SymbolIndex &Index) {
289 RefsRequest RQuest;
290 RQuest.IDs.insert(*getSymbolID(&RenameDecl));
291
292 // Absolute file path => rename occurrences in that file.
293 llvm::StringMap<std::vector<Range>> AffectedFiles;
294 // FIXME: Make the limit customizable.
295 static constexpr size_t MaxLimitFiles = 50;
296 bool HasMore = Index.refs(RQuest, [&](const Ref &R) {
297 if (AffectedFiles.size() > MaxLimitFiles)
298 return;
299 if (auto RefFilePath = filePath(R.Location, /*HintFilePath=*/MainFile)) {
300 if (*RefFilePath != MainFile)
301 AffectedFiles[*RefFilePath].push_back(toRange(R.Location));
302 }
303 });
304
305 if (AffectedFiles.size() > MaxLimitFiles)
306 return llvm::make_error<llvm::StringError>(
307 llvm::formatv("The number of affected files exceeds the max limit {0}",
308 MaxLimitFiles),
309 llvm::inconvertibleErrorCode());
310 if (HasMore) {
311 return llvm::make_error<llvm::StringError>(
312 llvm::formatv("The symbol {0} has too many occurrences",
313 RenameDecl.getQualifiedNameAsString()),
314 llvm::inconvertibleErrorCode());
315 }
316 // Sort and deduplicate the results, in case that index returns duplications.
317 for (auto &FileAndOccurrences : AffectedFiles) {
318 auto &Ranges = FileAndOccurrences.getValue();
319 llvm::sort(Ranges);
320 Ranges.erase(std::unique(Ranges.begin(), Ranges.end()), Ranges.end());
321 }
322 return AffectedFiles;
323 }
324
325 // Index-based rename, it renames all occurrences outside of the main file.
326 //
327 // The cross-file rename is purely based on the index, as we don't want to
328 // build all ASTs for affected files, which may cause a performance hit.
329 // We choose to trade off some correctness for performance and scalability.
330 //
331 // Clangd builds a dynamic index for all opened files on top of the static
332 // index of the whole codebase. Dynamic index is up-to-date (respects dirty
333 // buffers) as long as clangd finishes processing opened files, while static
334 // index (background index) is relatively stale. We choose the dirty buffers
335 // as the file content we rename on, and fallback to file content on disk if
336 // there is no dirty buffer.
337 //
338 // FIXME: Add range patching heuristics to detect staleness of the index, and
339 // report to users.
340 // FIXME: Our index may return implicit references, which are not eligible for
341 // rename, we should filter out these references.
renameOutsideFile(const NamedDecl & RenameDecl,llvm::StringRef MainFilePath,llvm::StringRef NewName,const SymbolIndex & Index,llvm::function_ref<llvm::Expected<std::string> (PathRef)> GetFileContent)342 llvm::Expected<FileEdits> renameOutsideFile(
343 const NamedDecl &RenameDecl, llvm::StringRef MainFilePath,
344 llvm::StringRef NewName, const SymbolIndex &Index,
345 llvm::function_ref<llvm::Expected<std::string>(PathRef)> GetFileContent) {
346 auto AffectedFiles =
347 findOccurrencesOutsideFile(RenameDecl, MainFilePath, Index);
348 if (!AffectedFiles)
349 return AffectedFiles.takeError();
350 FileEdits Results;
351 for (auto &FileAndOccurrences : *AffectedFiles) {
352 llvm::StringRef FilePath = FileAndOccurrences.first();
353
354 auto AffectedFileCode = GetFileContent(FilePath);
355 if (!AffectedFileCode) {
356 elog("Fail to read file content: {0}", AffectedFileCode.takeError());
357 continue;
358 }
359 auto RenameRanges =
360 adjustRenameRanges(*AffectedFileCode, RenameDecl.getNameAsString(),
361 std::move(FileAndOccurrences.second),
362 RenameDecl.getASTContext().getLangOpts());
363 if (!RenameRanges) {
364 // Our heuristics fails to adjust rename ranges to the current state of
365 // the file, it is most likely the index is stale, so we give up the
366 // entire rename.
367 return llvm::make_error<llvm::StringError>(
368 llvm::formatv("Index results don't match the content of file {0} "
369 "(the index may be stale)",
370 FilePath),
371 llvm::inconvertibleErrorCode());
372 }
373 auto RenameEdit =
374 buildRenameEdit(FilePath, *AffectedFileCode, *RenameRanges, NewName);
375 if (!RenameEdit) {
376 return llvm::make_error<llvm::StringError>(
377 llvm::formatv("fail to build rename edit for file {0}: {1}", FilePath,
378 llvm::toString(RenameEdit.takeError())),
379 llvm::inconvertibleErrorCode());
380 }
381 if (!RenameEdit->Replacements.empty())
382 Results.insert({FilePath, std::move(*RenameEdit)});
383 }
384 return Results;
385 }
386
387 // A simple edit is either changing line or column, but not both.
impliesSimpleEdit(const Position & LHS,const Position & RHS)388 bool impliesSimpleEdit(const Position &LHS, const Position &RHS) {
389 return LHS.line == RHS.line || LHS.character == RHS.character;
390 }
391
392 // Performs a DFS to enumerate all possible near-miss matches.
393 // It finds the locations where the indexed occurrences are now spelled in
394 // Lexed occurrences, a near miss is defined as:
395 // - a near miss maps all of the **name** occurrences from the index onto a
396 // *subset* of lexed occurrences (we allow a single name refers to more
397 // than one symbol)
398 // - all indexed occurrences must be mapped, and Result must be distinct and
399 // preseve order (only support detecting simple edits to ensure a
400 // robust mapping)
401 // - each indexed -> lexed occurrences mapping correspondence may change the
402 // *line* or *column*, but not both (increases chance of a robust mapping)
findNearMiss(std::vector<size_t> & PartialMatch,ArrayRef<Range> IndexedRest,ArrayRef<Range> LexedRest,int LexedIndex,int & Fuel,llvm::function_ref<void (const std::vector<size_t> &)> MatchedCB)403 void findNearMiss(
404 std::vector<size_t> &PartialMatch, ArrayRef<Range> IndexedRest,
405 ArrayRef<Range> LexedRest, int LexedIndex, int &Fuel,
406 llvm::function_ref<void(const std::vector<size_t> &)> MatchedCB) {
407 if (--Fuel < 0)
408 return;
409 if (IndexedRest.size() > LexedRest.size())
410 return;
411 if (IndexedRest.empty()) {
412 MatchedCB(PartialMatch);
413 return;
414 }
415 if (impliesSimpleEdit(IndexedRest.front().start, LexedRest.front().start)) {
416 PartialMatch.push_back(LexedIndex);
417 findNearMiss(PartialMatch, IndexedRest.drop_front(), LexedRest.drop_front(),
418 LexedIndex + 1, Fuel, MatchedCB);
419 PartialMatch.pop_back();
420 }
421 findNearMiss(PartialMatch, IndexedRest, LexedRest.drop_front(),
422 LexedIndex + 1, Fuel, MatchedCB);
423 }
424
425 } // namespace
426
rename(const RenameInputs & RInputs)427 llvm::Expected<FileEdits> rename(const RenameInputs &RInputs) {
428 ParsedAST &AST = RInputs.AST;
429 const SourceManager &SM = AST.getSourceManager();
430 llvm::StringRef MainFileCode = SM.getBufferData(SM.getMainFileID());
431 auto GetFileContent = [&RInputs,
432 &SM](PathRef AbsPath) -> llvm::Expected<std::string> {
433 llvm::Optional<std::string> DirtyBuffer;
434 if (RInputs.GetDirtyBuffer &&
435 (DirtyBuffer = RInputs.GetDirtyBuffer(AbsPath)))
436 return std::move(*DirtyBuffer);
437
438 auto Content =
439 SM.getFileManager().getVirtualFileSystem().getBufferForFile(AbsPath);
440 if (!Content)
441 return llvm::createStringError(
442 llvm::inconvertibleErrorCode(),
443 llvm::formatv("Fail to open file {0}: {1}", AbsPath,
444 Content.getError().message()));
445 if (!*Content)
446 return llvm::createStringError(
447 llvm::inconvertibleErrorCode(),
448 llvm::formatv("Got no buffer for file {0}", AbsPath));
449
450 return (*Content)->getBuffer().str();
451 };
452 // Try to find the tokens adjacent to the cursor position.
453 auto Loc = sourceLocationInMainFile(SM, RInputs.Pos);
454 if (!Loc)
455 return Loc.takeError();
456 const syntax::Token *IdentifierToken =
457 spelledIdentifierTouching(*Loc, AST.getTokens());
458 // Renames should only triggered on identifiers.
459 if (!IdentifierToken)
460 return makeError(ReasonToReject::NoSymbolFound);
461 // FIXME: Renaming macros is not supported yet, the macro-handling code should
462 // be moved to rename tooling library.
463 if (locateMacroAt(IdentifierToken->location(), AST.getPreprocessor()))
464 return makeError(ReasonToReject::UnsupportedSymbol);
465
466 auto DeclsUnderCursor = locateDeclAt(AST, IdentifierToken->location());
467 if (DeclsUnderCursor.empty())
468 return makeError(ReasonToReject::NoSymbolFound);
469 if (DeclsUnderCursor.size() > 1)
470 return makeError(ReasonToReject::AmbiguousSymbol);
471
472 const auto *RenameDecl = llvm::dyn_cast<NamedDecl>(*DeclsUnderCursor.begin());
473 if (!RenameDecl)
474 return makeError(ReasonToReject::UnsupportedSymbol);
475
476 auto Reject =
477 renameable(*RenameDecl->getCanonicalDecl(), RInputs.MainFilePath,
478 RInputs.Index, RInputs.AllowCrossFile);
479 if (Reject)
480 return makeError(*Reject);
481
482 // We have two implementations of the rename:
483 // - AST-based rename: used for renaming local symbols, e.g. variables
484 // defined in a function body;
485 // - index-based rename: used for renaming non-local symbols, and not
486 // feasible for local symbols (as by design our index don't index these
487 // symbols by design;
488 // To make cross-file rename work for local symbol, we use a hybrid solution:
489 // - run AST-based rename on the main file;
490 // - run index-based rename on other affected files;
491 auto MainFileRenameEdit = renameWithinFile(AST, *RenameDecl, RInputs.NewName);
492 if (!MainFileRenameEdit)
493 return MainFileRenameEdit.takeError();
494
495 if (!RInputs.AllowCrossFile) {
496 // Within-file rename: just return the main file results.
497 return FileEdits(
498 {std::make_pair(RInputs.MainFilePath,
499 Edit{MainFileCode, std::move(*MainFileRenameEdit)})});
500 }
501
502 FileEdits Results;
503 // Renameable safely guards us that at this point we are renaming a local
504 // symbol if we don't have index.
505 if (RInputs.Index) {
506 auto OtherFilesEdits =
507 renameOutsideFile(*RenameDecl, RInputs.MainFilePath, RInputs.NewName,
508 *RInputs.Index, GetFileContent);
509 if (!OtherFilesEdits)
510 return OtherFilesEdits.takeError();
511 Results = std::move(*OtherFilesEdits);
512 }
513 // Attach the rename edits for the main file.
514 Results.try_emplace(RInputs.MainFilePath, MainFileCode,
515 std::move(*MainFileRenameEdit));
516 return Results;
517 }
518
buildRenameEdit(llvm::StringRef AbsFilePath,llvm::StringRef InitialCode,std::vector<Range> Occurrences,llvm::StringRef NewName)519 llvm::Expected<Edit> buildRenameEdit(llvm::StringRef AbsFilePath,
520 llvm::StringRef InitialCode,
521 std::vector<Range> Occurrences,
522 llvm::StringRef NewName) {
523 assert(std::is_sorted(Occurrences.begin(), Occurrences.end()));
524 assert(std::unique(Occurrences.begin(), Occurrences.end()) ==
525 Occurrences.end() &&
526 "Occurrences must be unique");
527
528 // These two always correspond to the same position.
529 Position LastPos{0, 0};
530 size_t LastOffset = 0;
531
532 auto Offset = [&](const Position &P) -> llvm::Expected<size_t> {
533 assert(LastPos <= P && "malformed input");
534 Position Shifted = {
535 P.line - LastPos.line,
536 P.line > LastPos.line ? P.character : P.character - LastPos.character};
537 auto ShiftedOffset =
538 positionToOffset(InitialCode.substr(LastOffset), Shifted);
539 if (!ShiftedOffset)
540 return llvm::make_error<llvm::StringError>(
541 llvm::formatv("fail to convert the position {0} to offset ({1})", P,
542 llvm::toString(ShiftedOffset.takeError())),
543 llvm::inconvertibleErrorCode());
544 LastPos = P;
545 LastOffset += *ShiftedOffset;
546 return LastOffset;
547 };
548
549 std::vector<std::pair</*start*/ size_t, /*end*/ size_t>> OccurrencesOffsets;
550 for (const auto &R : Occurrences) {
551 auto StartOffset = Offset(R.start);
552 if (!StartOffset)
553 return StartOffset.takeError();
554 auto EndOffset = Offset(R.end);
555 if (!EndOffset)
556 return EndOffset.takeError();
557 OccurrencesOffsets.push_back({*StartOffset, *EndOffset});
558 }
559
560 tooling::Replacements RenameEdit;
561 for (const auto &R : OccurrencesOffsets) {
562 auto ByteLength = R.second - R.first;
563 if (auto Err = RenameEdit.add(
564 tooling::Replacement(AbsFilePath, R.first, ByteLength, NewName)))
565 return std::move(Err);
566 }
567 return Edit(InitialCode, std::move(RenameEdit));
568 }
569
570 // Details:
571 // - lex the draft code to get all rename candidates, this yields a superset
572 // of candidates.
573 // - apply range patching heuristics to generate "authoritative" occurrences,
574 // cases we consider:
575 // (a) index returns a subset of candidates, we use the indexed results.
576 // - fully equal, we are sure the index is up-to-date
577 // - proper subset, index is correct in most cases? there may be false
578 // positives (e.g. candidates got appended), but rename is still safe
579 // (b) index returns non-candidate results, we attempt to map the indexed
580 // ranges onto candidates in a plausible way (e.g. guess that lines
581 // were inserted). If such a "near miss" is found, the rename is still
582 // possible
583 llvm::Optional<std::vector<Range>>
adjustRenameRanges(llvm::StringRef DraftCode,llvm::StringRef Identifier,std::vector<Range> Indexed,const LangOptions & LangOpts)584 adjustRenameRanges(llvm::StringRef DraftCode, llvm::StringRef Identifier,
585 std::vector<Range> Indexed, const LangOptions &LangOpts) {
586 assert(!Indexed.empty());
587 assert(std::is_sorted(Indexed.begin(), Indexed.end()));
588 std::vector<Range> Lexed =
589 collectIdentifierRanges(Identifier, DraftCode, LangOpts);
590 llvm::sort(Lexed);
591 return getMappedRanges(Indexed, Lexed);
592 }
593
getMappedRanges(ArrayRef<Range> Indexed,ArrayRef<Range> Lexed)594 llvm::Optional<std::vector<Range>> getMappedRanges(ArrayRef<Range> Indexed,
595 ArrayRef<Range> Lexed) {
596 assert(!Indexed.empty());
597 assert(std::is_sorted(Indexed.begin(), Indexed.end()));
598 assert(std::is_sorted(Lexed.begin(), Lexed.end()));
599
600 if (Indexed.size() > Lexed.size()) {
601 vlog("The number of lexed occurrences is less than indexed occurrences");
602 return llvm::None;
603 }
604 // Fast check for the special subset case.
605 if (std::includes(Indexed.begin(), Indexed.end(), Lexed.begin(), Lexed.end()))
606 return Indexed.vec();
607
608 std::vector<size_t> Best;
609 size_t BestCost = std::numeric_limits<size_t>::max();
610 bool HasMultiple = 0;
611 std::vector<size_t> ResultStorage;
612 int Fuel = 10000;
613 findNearMiss(ResultStorage, Indexed, Lexed, 0, Fuel,
614 [&](const std::vector<size_t> &Matched) {
615 size_t MCost =
616 renameRangeAdjustmentCost(Indexed, Lexed, Matched);
617 if (MCost < BestCost) {
618 BestCost = MCost;
619 Best = std::move(Matched);
620 HasMultiple = false; // reset
621 return;
622 }
623 if (MCost == BestCost)
624 HasMultiple = true;
625 });
626 if (HasMultiple) {
627 vlog("The best near miss is not unique.");
628 return llvm::None;
629 }
630 if (Best.empty()) {
631 vlog("Didn't find a near miss.");
632 return llvm::None;
633 }
634 std::vector<Range> Mapped;
635 for (auto I : Best)
636 Mapped.push_back(Lexed[I]);
637 return Mapped;
638 }
639
640 // The cost is the sum of the implied edit sizes between successive diffs, only
641 // simple edits are considered:
642 // - insert/remove a line (change line offset)
643 // - insert/remove a character on an existing line (change column offset)
644 //
645 // Example I, total result is 1 + 1 = 2.
646 // diff[0]: line + 1 <- insert a line before edit 0.
647 // diff[1]: line + 1
648 // diff[2]: line + 1
649 // diff[3]: line + 2 <- insert a line before edits 2 and 3.
650 //
651 // Example II, total result is 1 + 1 + 1 = 3.
652 // diff[0]: line + 1 <- insert a line before edit 0.
653 // diff[1]: column + 1 <- remove a line between edits 0 and 1, and insert a
654 // character on edit 1.
renameRangeAdjustmentCost(ArrayRef<Range> Indexed,ArrayRef<Range> Lexed,ArrayRef<size_t> MappedIndex)655 size_t renameRangeAdjustmentCost(ArrayRef<Range> Indexed, ArrayRef<Range> Lexed,
656 ArrayRef<size_t> MappedIndex) {
657 assert(Indexed.size() == MappedIndex.size());
658 assert(std::is_sorted(Indexed.begin(), Indexed.end()));
659 assert(std::is_sorted(Lexed.begin(), Lexed.end()));
660
661 int LastLine = -1;
662 int LastDLine = 0, LastDColumn = 0;
663 int Cost = 0;
664 for (size_t I = 0; I < Indexed.size(); ++I) {
665 int DLine = Indexed[I].start.line - Lexed[MappedIndex[I]].start.line;
666 int DColumn =
667 Indexed[I].start.character - Lexed[MappedIndex[I]].start.character;
668 int Line = Indexed[I].start.line;
669 if (Line != LastLine)
670 LastDColumn = 0; // column offsets don't carry cross lines.
671 Cost += abs(DLine - LastDLine) + abs(DColumn - LastDColumn);
672 std::tie(LastLine, LastDLine, LastDColumn) = std::tie(Line, DLine, DColumn);
673 }
674 return Cost;
675 }
676
677 } // namespace clangd
678 } // namespace clang
679