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