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