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/ASTContext.h" |
19 | #include "clang/AST/ASTTypeTraits.h" |
20 | #include "clang/AST/Decl.h" |
21 | #include "clang/AST/DeclBase.h" |
22 | #include "clang/AST/DeclCXX.h" |
23 | #include "clang/AST/DeclObjC.h" |
24 | #include "clang/AST/DeclTemplate.h" |
25 | #include "clang/AST/DeclarationName.h" |
26 | #include "clang/AST/ParentMapContext.h" |
27 | #include "clang/AST/Stmt.h" |
28 | #include "clang/Basic/CharInfo.h" |
29 | #include "clang/Basic/LLVM.h" |
30 | #include "clang/Basic/SourceLocation.h" |
31 | #include "clang/Tooling/Syntax/Tokens.h" |
32 | #include "llvm/ADT/STLExtras.h" |
33 | #include "llvm/ADT/StringExtras.h" |
34 | #include "llvm/Support/Casting.h" |
35 | #include "llvm/Support/Error.h" |
36 | #include "llvm/Support/FormatVariadic.h" |
37 | #include "llvm/Support/JSON.h" |
38 | #include <algorithm> |
39 | #include <optional> |
40 | |
41 | namespace clang { |
42 | namespace clangd { |
43 | namespace { |
44 | |
45 | std::optional<std::string> filePath(const SymbolLocation &Loc, |
46 | llvm::StringRef HintFilePath) { |
47 | if (!Loc) |
48 | return std::nullopt; |
49 | auto Path = URI::resolve(FileURI: Loc.FileURI, HintPath: HintFilePath); |
50 | if (!Path) { |
51 | elog(Fmt: "Could not resolve URI {0}: {1}" , Vals: Loc.FileURI, Vals: Path.takeError()); |
52 | return std::nullopt; |
53 | } |
54 | |
55 | return *Path; |
56 | } |
57 | |
58 | // Returns true if the given location is expanded from any macro body. |
59 | bool isInMacroBody(const SourceManager &SM, SourceLocation Loc) { |
60 | while (Loc.isMacroID()) { |
61 | if (SM.isMacroBodyExpansion(Loc)) |
62 | return true; |
63 | Loc = SM.getImmediateMacroCallerLoc(Loc); |
64 | } |
65 | |
66 | return false; |
67 | } |
68 | |
69 | // Canonical declarations help simplify the process of renaming. Examples: |
70 | // - Template's canonical decl is the templated declaration (i.e. |
71 | // ClassTemplateDecl is canonicalized to its child CXXRecordDecl, |
72 | // FunctionTemplateDecl - to child FunctionDecl) |
73 | // - Given a constructor/destructor, canonical declaration is the parent |
74 | // CXXRecordDecl because we want to rename both type name and its ctor/dtor. |
75 | // - All specializations are canonicalized to the primary template. For example: |
76 | // |
77 | // template <typename T, int U> |
78 | // bool Foo = true; (1) |
79 | // |
80 | // template <typename T> |
81 | // bool Foo<T, 0> = true; (2) |
82 | // |
83 | // template <> |
84 | // bool Foo<int, 0> = true; (3) |
85 | // |
86 | // Here, both partial (2) and full (3) specializations are canonicalized to (1) |
87 | // which ensures all three of them are renamed. |
88 | const NamedDecl *canonicalRenameDecl(const NamedDecl *D) { |
89 | if (const auto *VarTemplate = dyn_cast<VarTemplateSpecializationDecl>(Val: D)) |
90 | return canonicalRenameDecl( |
91 | VarTemplate->getSpecializedTemplate()->getTemplatedDecl()); |
92 | if (const auto *Template = dyn_cast<TemplateDecl>(Val: D)) |
93 | if (const NamedDecl *TemplatedDecl = Template->getTemplatedDecl()) |
94 | return canonicalRenameDecl(D: TemplatedDecl); |
95 | if (const auto *ClassTemplateSpecialization = |
96 | dyn_cast<ClassTemplateSpecializationDecl>(Val: D)) |
97 | return canonicalRenameDecl( |
98 | ClassTemplateSpecialization->getSpecializedTemplate() |
99 | ->getTemplatedDecl()); |
100 | if (const auto *Method = dyn_cast<CXXMethodDecl>(Val: D)) { |
101 | if (Method->getDeclKind() == Decl::Kind::CXXConstructor || |
102 | Method->getDeclKind() == Decl::Kind::CXXDestructor) |
103 | return canonicalRenameDecl(Method->getParent()); |
104 | if (const FunctionDecl *InstantiatedMethod = |
105 | Method->getInstantiatedFromMemberFunction()) |
106 | return canonicalRenameDecl(InstantiatedMethod); |
107 | // FIXME(kirillbobyrev): For virtual methods with |
108 | // size_overridden_methods() > 1, this will not rename all functions it |
109 | // overrides, because this code assumes there is a single canonical |
110 | // declaration. |
111 | if (Method->isVirtual() && Method->size_overridden_methods()) |
112 | return canonicalRenameDecl(*Method->overridden_methods().begin()); |
113 | } |
114 | if (const auto *Function = dyn_cast<FunctionDecl>(Val: D)) |
115 | if (const FunctionTemplateDecl *Template = Function->getPrimaryTemplate()) |
116 | return canonicalRenameDecl(Template); |
117 | if (const auto *Field = dyn_cast<FieldDecl>(Val: D)) { |
118 | // This is a hacky way to do something like |
119 | // CXXMethodDecl::getInstantiatedFromMemberFunction for the field because |
120 | // Clang AST does not store relevant information about the field that is |
121 | // instantiated. |
122 | const auto *FieldParent = |
123 | dyn_cast_or_null<CXXRecordDecl>(Val: Field->getParent()); |
124 | if (!FieldParent) |
125 | return Field->getCanonicalDecl(); |
126 | FieldParent = FieldParent->getTemplateInstantiationPattern(); |
127 | // Field is not instantiation. |
128 | if (!FieldParent || Field->getParent() == FieldParent) |
129 | return Field->getCanonicalDecl(); |
130 | for (const FieldDecl *Candidate : FieldParent->fields()) |
131 | if (Field->getDeclName() == Candidate->getDeclName()) |
132 | return Candidate->getCanonicalDecl(); |
133 | elog(Fmt: "FieldParent should have field with the same name as Field." ); |
134 | } |
135 | if (const auto *VD = dyn_cast<VarDecl>(Val: D)) { |
136 | if (const VarDecl *OriginalVD = VD->getInstantiatedFromStaticDataMember()) |
137 | return canonicalRenameDecl(OriginalVD); |
138 | } |
139 | if (const auto *UD = dyn_cast<UsingShadowDecl>(Val: D)) { |
140 | if (const auto *TargetDecl = UD->getTargetDecl()) |
141 | return canonicalRenameDecl(D: TargetDecl); |
142 | } |
143 | return dyn_cast<NamedDecl>(D->getCanonicalDecl()); |
144 | } |
145 | |
146 | // Some AST nodes can reference multiple declarations. We try to pick the |
147 | // relevant one to rename here. |
148 | const NamedDecl *pickInterestingTarget(const NamedDecl *D) { |
149 | // We only support renaming the class name, not the category name. This has |
150 | // to be done outside of canonicalization since we don't want a category name |
151 | // reference to be canonicalized to the class. |
152 | if (const auto *CD = dyn_cast<ObjCCategoryDecl>(Val: D)) |
153 | if (const auto CI = CD->getClassInterface()) |
154 | return CI; |
155 | return D; |
156 | } |
157 | |
158 | llvm::DenseSet<const NamedDecl *> locateDeclAt(ParsedAST &AST, |
159 | SourceLocation TokenStartLoc) { |
160 | unsigned Offset = |
161 | AST.getSourceManager().getDecomposedSpellingLoc(Loc: TokenStartLoc).second; |
162 | |
163 | SelectionTree Selection = SelectionTree::createRight( |
164 | AST&: AST.getASTContext(), Tokens: AST.getTokens(), Begin: Offset, End: Offset); |
165 | const SelectionTree::Node *SelectedNode = Selection.commonAncestor(); |
166 | if (!SelectedNode) |
167 | return {}; |
168 | |
169 | llvm::DenseSet<const NamedDecl *> Result; |
170 | for (const NamedDecl *D : |
171 | targetDecl(SelectedNode->ASTNode, |
172 | DeclRelation::Alias | DeclRelation::TemplatePattern, |
173 | AST.getHeuristicResolver())) { |
174 | D = pickInterestingTarget(D); |
175 | Result.insert(canonicalRenameDecl(D)); |
176 | } |
177 | return Result; |
178 | } |
179 | |
180 | void filterRenameTargets(llvm::DenseSet<const NamedDecl *> &Decls) { |
181 | // For something like |
182 | // namespace ns { void foo(); } |
183 | // void bar() { using ns::f^oo; foo(); } |
184 | // locateDeclAt() will return a UsingDecl and foo's actual declaration. |
185 | // For renaming, we're only interested in foo's declaration, so drop the other |
186 | // one. There should never be more than one UsingDecl here, otherwise the |
187 | // rename would be ambiguos anyway. |
188 | auto UD = llvm::find_if( |
189 | Range&: Decls, P: [](const NamedDecl *D) { return llvm::isa<UsingDecl>(Val: D); }); |
190 | if (UD != Decls.end()) { |
191 | Decls.erase(I: UD); |
192 | } |
193 | } |
194 | |
195 | // By default, we exclude symbols from system headers and protobuf symbols as |
196 | // renaming these symbols would change system/generated files which are unlikely |
197 | // to be good candidates for modification. |
198 | bool isExcluded(const NamedDecl &RenameDecl) { |
199 | const auto &SM = RenameDecl.getASTContext().getSourceManager(); |
200 | return SM.isInSystemHeader(RenameDecl.getLocation()) || |
201 | isProtoFile(RenameDecl.getLocation(), SM); |
202 | } |
203 | |
204 | enum class ReasonToReject { |
205 | NoSymbolFound, |
206 | NoIndexProvided, |
207 | NonIndexable, |
208 | UnsupportedSymbol, |
209 | AmbiguousSymbol, |
210 | |
211 | // name validation. FIXME: reconcile with InvalidName |
212 | SameName, |
213 | }; |
214 | |
215 | std::optional<ReasonToReject> renameable(const NamedDecl &RenameDecl, |
216 | StringRef MainFilePath, |
217 | const SymbolIndex *Index, |
218 | const RenameOptions &Opts) { |
219 | trace::Span Tracer("Renameable" ); |
220 | if (!Opts.RenameVirtual) { |
221 | if (const auto *S = llvm::dyn_cast<CXXMethodDecl>(Val: &RenameDecl)) { |
222 | if (S->isVirtual()) |
223 | return ReasonToReject::UnsupportedSymbol; |
224 | } |
225 | } |
226 | // We allow renaming ObjC methods although they don't have a simple |
227 | // identifier. |
228 | const auto *ID = RenameDecl.getIdentifier(); |
229 | if (!ID && !isa<ObjCMethodDecl>(Val: &RenameDecl)) |
230 | return ReasonToReject::UnsupportedSymbol; |
231 | // Filter out symbols that are unsupported in both rename modes. |
232 | if (llvm::isa<NamespaceDecl>(Val: &RenameDecl)) |
233 | return ReasonToReject::UnsupportedSymbol; |
234 | if (const auto *FD = llvm::dyn_cast<FunctionDecl>(Val: &RenameDecl)) { |
235 | if (FD->isOverloadedOperator()) |
236 | return ReasonToReject::UnsupportedSymbol; |
237 | } |
238 | // function-local symbols is safe to rename. |
239 | if (RenameDecl.getParentFunctionOrMethod()) |
240 | return std::nullopt; |
241 | |
242 | if (isExcluded(RenameDecl)) |
243 | return ReasonToReject::UnsupportedSymbol; |
244 | |
245 | // Check whether the symbol being rename is indexable. |
246 | auto &ASTCtx = RenameDecl.getASTContext(); |
247 | bool MainFileIsHeader = isHeaderFile(MainFilePath, ASTCtx.getLangOpts()); |
248 | bool DeclaredInMainFile = |
249 | isInsideMainFile(RenameDecl.getBeginLoc(), ASTCtx.getSourceManager()); |
250 | bool IsMainFileOnly = true; |
251 | if (MainFileIsHeader) |
252 | // main file is a header, the symbol can't be main file only. |
253 | IsMainFileOnly = false; |
254 | else if (!DeclaredInMainFile) |
255 | IsMainFileOnly = false; |
256 | // If the symbol is not indexable, we disallow rename. |
257 | if (!SymbolCollector::shouldCollectSymbol( |
258 | ND: RenameDecl, ASTCtx: RenameDecl.getASTContext(), Opts: SymbolCollector::Options(), |
259 | IsMainFileSymbol: IsMainFileOnly)) |
260 | return ReasonToReject::NonIndexable; |
261 | |
262 | return std::nullopt; |
263 | } |
264 | |
265 | llvm::Error makeError(ReasonToReject Reason) { |
266 | auto Message = [](ReasonToReject Reason) { |
267 | switch (Reason) { |
268 | case ReasonToReject::NoSymbolFound: |
269 | return "there is no symbol at the given location" ; |
270 | case ReasonToReject::NoIndexProvided: |
271 | return "no index provided" ; |
272 | case ReasonToReject::NonIndexable: |
273 | return "symbol may be used in other files (not eligible for indexing)" ; |
274 | case ReasonToReject::UnsupportedSymbol: |
275 | return "symbol is not a supported kind (e.g. namespace, macro)" ; |
276 | case ReasonToReject::AmbiguousSymbol: |
277 | return "there are multiple symbols at the given location" ; |
278 | case ReasonToReject::SameName: |
279 | return "new name is the same as the old name" ; |
280 | } |
281 | llvm_unreachable("unhandled reason kind" ); |
282 | }; |
283 | return error(Fmt: "Cannot rename symbol: {0}" , Vals: Message(Reason)); |
284 | } |
285 | |
286 | // Return all rename occurrences in the main file. |
287 | std::vector<SourceLocation> findOccurrencesWithinFile(ParsedAST &AST, |
288 | const NamedDecl &ND) { |
289 | trace::Span Tracer("FindOccurrencesWithinFile" ); |
290 | assert(canonicalRenameDecl(&ND) == &ND && |
291 | "ND should be already canonicalized." ); |
292 | |
293 | std::vector<SourceLocation> Results; |
294 | for (Decl *TopLevelDecl : AST.getLocalTopLevelDecls()) { |
295 | findExplicitReferences( |
296 | D: TopLevelDecl, |
297 | Out: [&](ReferenceLoc Ref) { |
298 | if (Ref.Targets.empty()) |
299 | return; |
300 | for (const auto *Target : Ref.Targets) { |
301 | if (canonicalRenameDecl(D: Target) == &ND) { |
302 | Results.push_back(x: Ref.NameLoc); |
303 | return; |
304 | } |
305 | } |
306 | }, |
307 | Resolver: AST.getHeuristicResolver()); |
308 | } |
309 | |
310 | return Results; |
311 | } |
312 | |
313 | // Detect name conflict with othter DeclStmts in the same enclosing scope. |
314 | const NamedDecl *lookupSiblingWithinEnclosingScope(ASTContext &Ctx, |
315 | const NamedDecl &RenamedDecl, |
316 | StringRef NewName) { |
317 | // Store Parents list outside of GetSingleParent, so that returned pointer is |
318 | // not invalidated. |
319 | DynTypedNodeList Storage(DynTypedNode::create(Node: RenamedDecl)); |
320 | auto GetSingleParent = [&](const DynTypedNode &Node) -> const DynTypedNode * { |
321 | Storage = Ctx.getParents(Node); |
322 | return (Storage.size() == 1) ? Storage.begin() : nullptr; |
323 | }; |
324 | |
325 | // We need to get to the enclosing scope: NamedDecl's parent is typically |
326 | // DeclStmt (or FunctionProtoTypeLoc in case of function arguments), so |
327 | // enclosing scope would be the second order parent. |
328 | const auto *Parent = GetSingleParent(DynTypedNode::create(Node: RenamedDecl)); |
329 | if (!Parent || !(Parent->get<DeclStmt>() || Parent->get<TypeLoc>())) |
330 | return nullptr; |
331 | Parent = GetSingleParent(*Parent); |
332 | |
333 | // The following helpers check corresponding AST nodes for variable |
334 | // declarations with the name collision. |
335 | auto CheckDeclStmt = [&](const DeclStmt *DS, |
336 | StringRef Name) -> const NamedDecl * { |
337 | if (!DS) |
338 | return nullptr; |
339 | for (const auto &Child : DS->getDeclGroup()) |
340 | if (const auto *ND = dyn_cast<NamedDecl>(Val: Child)) |
341 | if (ND != &RenamedDecl && ND->getDeclName().isIdentifier() && |
342 | ND->getName() == Name && |
343 | ND->getIdentifierNamespace() & RenamedDecl.getIdentifierNamespace()) |
344 | return ND; |
345 | return nullptr; |
346 | }; |
347 | auto CheckCompoundStmt = [&](const Stmt *S, |
348 | StringRef Name) -> const NamedDecl * { |
349 | if (const auto *CS = dyn_cast_or_null<CompoundStmt>(Val: S)) |
350 | for (const auto *Node : CS->children()) |
351 | if (const auto *Result = CheckDeclStmt(dyn_cast<DeclStmt>(Val: Node), Name)) |
352 | return Result; |
353 | return nullptr; |
354 | }; |
355 | auto CheckConditionVariable = [&](const auto *Scope, |
356 | StringRef Name) -> const NamedDecl * { |
357 | if (!Scope) |
358 | return nullptr; |
359 | return CheckDeclStmt(Scope->getConditionVariableDeclStmt(), Name); |
360 | }; |
361 | |
362 | // CompoundStmt is the most common enclosing scope for function-local symbols |
363 | // In the simplest case we just iterate through sibling DeclStmts and check |
364 | // for collisions. |
365 | if (const auto *EnclosingCS = Parent->get<CompoundStmt>()) { |
366 | if (const auto *Result = CheckCompoundStmt(EnclosingCS, NewName)) |
367 | return Result; |
368 | const auto *ScopeParent = GetSingleParent(*Parent); |
369 | // CompoundStmt may be found within if/while/for. In these cases, rename can |
370 | // collide with the init-statement variable decalaration, they should be |
371 | // checked. |
372 | if (const auto *Result = |
373 | CheckConditionVariable(ScopeParent->get<IfStmt>(), NewName)) |
374 | return Result; |
375 | if (const auto *Result = |
376 | CheckConditionVariable(ScopeParent->get<WhileStmt>(), NewName)) |
377 | return Result; |
378 | if (const auto *For = ScopeParent->get<ForStmt>()) |
379 | if (const auto *Result = CheckDeclStmt( |
380 | dyn_cast_or_null<DeclStmt>(Val: For->getInit()), NewName)) |
381 | return Result; |
382 | // Also check if there is a name collision with function arguments. |
383 | if (const auto *Function = ScopeParent->get<FunctionDecl>()) |
384 | for (const auto *Parameter : Function->parameters()) |
385 | if (Parameter->getName() == NewName && |
386 | Parameter->getIdentifierNamespace() & |
387 | RenamedDecl.getIdentifierNamespace()) |
388 | return Parameter; |
389 | return nullptr; |
390 | } |
391 | |
392 | // When renaming a variable within init-statement within if/while/for |
393 | // condition, also check the CompoundStmt in the body. |
394 | if (const auto *EnclosingIf = Parent->get<IfStmt>()) { |
395 | if (const auto *Result = CheckCompoundStmt(EnclosingIf->getElse(), NewName)) |
396 | return Result; |
397 | return CheckCompoundStmt(EnclosingIf->getThen(), NewName); |
398 | } |
399 | if (const auto *EnclosingWhile = Parent->get<WhileStmt>()) |
400 | return CheckCompoundStmt(EnclosingWhile->getBody(), NewName); |
401 | if (const auto *EnclosingFor = Parent->get<ForStmt>()) { |
402 | // Check for conflicts with other declarations within initialization |
403 | // statement. |
404 | if (const auto *Result = CheckDeclStmt( |
405 | dyn_cast_or_null<DeclStmt>(Val: EnclosingFor->getInit()), NewName)) |
406 | return Result; |
407 | return CheckCompoundStmt(EnclosingFor->getBody(), NewName); |
408 | } |
409 | if (const auto *EnclosingFunction = Parent->get<FunctionDecl>()) { |
410 | // Check for conflicts with other arguments. |
411 | for (const auto *Parameter : EnclosingFunction->parameters()) |
412 | if (Parameter != &RenamedDecl && Parameter->getName() == NewName && |
413 | Parameter->getIdentifierNamespace() & |
414 | RenamedDecl.getIdentifierNamespace()) |
415 | return Parameter; |
416 | // FIXME: We don't modify all references to function parameters when |
417 | // renaming from forward declaration now, so using a name colliding with |
418 | // something in the definition's body is a valid transformation. |
419 | if (!EnclosingFunction->doesThisDeclarationHaveABody()) |
420 | return nullptr; |
421 | return CheckCompoundStmt(EnclosingFunction->getBody(), NewName); |
422 | } |
423 | |
424 | return nullptr; |
425 | } |
426 | |
427 | // Lookup the declarations (if any) with the given Name in the context of |
428 | // RenameDecl. |
429 | const NamedDecl *lookupSiblingsWithinContext(ASTContext &Ctx, |
430 | const NamedDecl &RenamedDecl, |
431 | llvm::StringRef NewName) { |
432 | const auto &II = Ctx.Idents.get(Name: NewName); |
433 | DeclarationName LookupName(&II); |
434 | DeclContextLookupResult LookupResult; |
435 | const auto *DC = RenamedDecl.getDeclContext(); |
436 | while (DC->isTransparentContext()) |
437 | DC = DC->getParent(); |
438 | switch (DC->getDeclKind()) { |
439 | // The enclosing DeclContext may not be the enclosing scope, it might have |
440 | // false positives and negatives, so we only choose "confident" DeclContexts |
441 | // that don't have any subscopes that are neither DeclContexts nor |
442 | // transparent. |
443 | // |
444 | // Notably, FunctionDecl is excluded -- because local variables are not scoped |
445 | // to the function, but rather to the CompoundStmt that is its body. Lookup |
446 | // will not find function-local variables. |
447 | case Decl::TranslationUnit: |
448 | case Decl::Namespace: |
449 | case Decl::Record: |
450 | case Decl::Enum: |
451 | case Decl::CXXRecord: |
452 | LookupResult = DC->lookup(LookupName); |
453 | break; |
454 | default: |
455 | break; |
456 | } |
457 | // Lookup may contain the RenameDecl itself, exclude it. |
458 | for (const auto *D : LookupResult) |
459 | if (D->getCanonicalDecl() != RenamedDecl.getCanonicalDecl() && |
460 | D->getIdentifierNamespace() & RenamedDecl.getIdentifierNamespace()) |
461 | return D; |
462 | return nullptr; |
463 | } |
464 | |
465 | const NamedDecl *lookupSiblingWithName(ASTContext &Ctx, |
466 | const NamedDecl &RenamedDecl, |
467 | llvm::StringRef NewName) { |
468 | trace::Span Tracer("LookupSiblingWithName" ); |
469 | if (const auto *Result = |
470 | lookupSiblingsWithinContext(Ctx, RenamedDecl, NewName)) |
471 | return Result; |
472 | return lookupSiblingWithinEnclosingScope(Ctx, RenamedDecl, NewName); |
473 | } |
474 | |
475 | struct InvalidName { |
476 | enum Kind { |
477 | Keywords, |
478 | Conflict, |
479 | BadIdentifier, |
480 | }; |
481 | Kind K; |
482 | std::string Details; |
483 | }; |
484 | std::string toString(InvalidName::Kind K) { |
485 | switch (K) { |
486 | case InvalidName::Keywords: |
487 | return "Keywords" ; |
488 | case InvalidName::Conflict: |
489 | return "Conflict" ; |
490 | case InvalidName::BadIdentifier: |
491 | return "BadIdentifier" ; |
492 | } |
493 | llvm_unreachable("unhandled InvalidName kind" ); |
494 | } |
495 | |
496 | llvm::Error makeError(InvalidName Reason) { |
497 | auto Message = [](const InvalidName &Reason) { |
498 | switch (Reason.K) { |
499 | case InvalidName::Keywords: |
500 | return llvm::formatv(Fmt: "the chosen name \"{0}\" is a keyword" , |
501 | Vals: Reason.Details); |
502 | case InvalidName::Conflict: |
503 | return llvm::formatv(Fmt: "conflict with the symbol in {0}" , Vals: Reason.Details); |
504 | case InvalidName::BadIdentifier: |
505 | return llvm::formatv(Fmt: "the chosen name \"{0}\" is not a valid identifier" , |
506 | Vals: Reason.Details); |
507 | } |
508 | llvm_unreachable("unhandled InvalidName kind" ); |
509 | }; |
510 | return error(Fmt: "invalid name: {0}" , Vals: Message(Reason)); |
511 | } |
512 | |
513 | static bool mayBeValidIdentifier(llvm::StringRef Ident, bool AllowColon) { |
514 | assert(llvm::json::isUTF8(Ident)); |
515 | if (Ident.empty()) |
516 | return false; |
517 | // We don't check all the rules for non-ascii characters (most are allowed). |
518 | bool AllowDollar = true; // lenient |
519 | if (llvm::isASCII(C: Ident.front()) && |
520 | !isAsciiIdentifierStart(c: Ident.front(), AllowDollar)) |
521 | return false; |
522 | for (char C : Ident) { |
523 | if (AllowColon && C == ':') |
524 | continue; |
525 | if (llvm::isASCII(C) && !isAsciiIdentifierContinue(c: C, AllowDollar)) |
526 | return false; |
527 | } |
528 | return true; |
529 | } |
530 | |
531 | std::string getName(const NamedDecl &RenameDecl) { |
532 | if (const auto *MD = dyn_cast<ObjCMethodDecl>(Val: &RenameDecl)) |
533 | return MD->getSelector().getAsString(); |
534 | if (const auto *ID = RenameDecl.getIdentifier()) |
535 | return ID->getName().str(); |
536 | return "" ; |
537 | } |
538 | |
539 | // Check if we can rename the given RenameDecl into NewName. |
540 | // Return details if the rename would produce a conflict. |
541 | llvm::Error checkName(const NamedDecl &RenameDecl, llvm::StringRef NewName, |
542 | llvm::StringRef OldName) { |
543 | trace::Span Tracer("CheckName" ); |
544 | static constexpr trace::Metric InvalidNameMetric( |
545 | "rename_name_invalid" , trace::Metric::Counter, "invalid_kind" ); |
546 | |
547 | if (OldName == NewName) |
548 | return makeError(Reason: ReasonToReject::SameName); |
549 | |
550 | if (const auto *MD = dyn_cast<ObjCMethodDecl>(Val: &RenameDecl)) { |
551 | const auto Sel = MD->getSelector(); |
552 | if (Sel.getNumArgs() != NewName.count(C: ':') && |
553 | NewName != "__clangd_rename_placeholder" ) |
554 | return makeError(Reason: InvalidName{.K: InvalidName::BadIdentifier, .Details: NewName.str()}); |
555 | } |
556 | |
557 | auto &ASTCtx = RenameDecl.getASTContext(); |
558 | std::optional<InvalidName> Result; |
559 | if (isKeyword(NewName, ASTCtx.getLangOpts())) |
560 | Result = InvalidName{.K: InvalidName::Keywords, .Details: NewName.str()}; |
561 | else if (!mayBeValidIdentifier(Ident: NewName, AllowColon: isa<ObjCMethodDecl>(Val: &RenameDecl))) |
562 | Result = InvalidName{.K: InvalidName::BadIdentifier, .Details: NewName.str()}; |
563 | else { |
564 | // Name conflict detection. |
565 | // Function conflicts are subtle (overloading), so ignore them. |
566 | if (RenameDecl.getKind() != Decl::Function && |
567 | RenameDecl.getKind() != Decl::CXXMethod) { |
568 | if (auto *Conflict = lookupSiblingWithName(ASTCtx, RenameDecl, NewName)) |
569 | Result = InvalidName{ |
570 | InvalidName::Conflict, |
571 | Conflict->getLocation().printToString(ASTCtx.getSourceManager())}; |
572 | } |
573 | } |
574 | if (Result) { |
575 | InvalidNameMetric.record(Value: 1, Label: toString(K: Result->K)); |
576 | return makeError(Reason: *Result); |
577 | } |
578 | return llvm::Error::success(); |
579 | } |
580 | |
581 | bool isSelectorLike(const syntax::Token &Cur, const syntax::Token &Next) { |
582 | return Cur.kind() == tok::identifier && Next.kind() == tok::colon && |
583 | // We require the selector name and : to be contiguous. |
584 | // e.g. support `foo:` but not `foo :`. |
585 | Cur.endLocation() == Next.location(); |
586 | } |
587 | |
588 | bool isMatchingSelectorName(const syntax::Token &Cur, const syntax::Token &Next, |
589 | const SourceManager &SM, |
590 | llvm::StringRef SelectorName) { |
591 | if (SelectorName.empty()) |
592 | return Cur.kind() == tok::colon; |
593 | return isSelectorLike(Cur, Next) && Cur.text(SM) == SelectorName; |
594 | } |
595 | |
596 | // Scan through Tokens to find ranges for each selector fragment in Sel assuming |
597 | // its first segment is located at Tokens.front(). |
598 | // The search will terminate upon seeing Terminator or a ; at the top level. |
599 | std::optional<SymbolRange> |
600 | findAllSelectorPieces(llvm::ArrayRef<syntax::Token> Tokens, |
601 | const SourceManager &SM, const RenameSymbolName &Name, |
602 | tok::TokenKind Terminator) { |
603 | assert(!Tokens.empty()); |
604 | |
605 | ArrayRef<std::string> NamePieces = Name.getNamePieces(); |
606 | unsigned NumArgs = NamePieces.size(); |
607 | llvm::SmallVector<tok::TokenKind, 8> Closes; |
608 | std::vector<Range> SelectorPieces; |
609 | for (unsigned Index = 0, Last = Tokens.size(); Index < Last - 1; ++Index) { |
610 | const auto &Tok = Tokens[Index]; |
611 | |
612 | if (Closes.empty()) { |
613 | auto PieceCount = SelectorPieces.size(); |
614 | if (PieceCount < NumArgs && |
615 | isMatchingSelectorName(Cur: Tok, Next: Tokens[Index + 1], SM, |
616 | SelectorName: NamePieces[PieceCount])) { |
617 | // If 'foo:' instead of ':' (empty selector), we need to skip the ':' |
618 | // token after the name. We don't currently properly support empty |
619 | // selectors since we may lex them improperly due to ternary statements |
620 | // as well as don't properly support storing their ranges for edits. |
621 | if (!NamePieces[PieceCount].empty()) |
622 | ++Index; |
623 | SelectorPieces.push_back( |
624 | x: halfOpenToRange(SM, R: Tok.range(SM).toCharRange(SM))); |
625 | continue; |
626 | } |
627 | // If we've found all pieces but the current token looks like another |
628 | // selector piece, it means the method being renamed is a strict prefix of |
629 | // the selector we've found - should be skipped. |
630 | if (SelectorPieces.size() >= NumArgs && |
631 | isSelectorLike(Cur: Tok, Next: Tokens[Index + 1])) |
632 | return std::nullopt; |
633 | } |
634 | |
635 | if (Closes.empty() && Tok.kind() == Terminator) |
636 | return SelectorPieces.size() == NumArgs |
637 | ? std::optional(SymbolRange(SelectorPieces)) |
638 | : std::nullopt; |
639 | |
640 | switch (Tok.kind()) { |
641 | case tok::l_square: |
642 | Closes.push_back(Elt: tok::r_square); |
643 | break; |
644 | case tok::l_paren: |
645 | Closes.push_back(Elt: tok::r_paren); |
646 | break; |
647 | case tok::l_brace: |
648 | Closes.push_back(Elt: tok::r_brace); |
649 | break; |
650 | case tok::r_square: |
651 | case tok::r_paren: |
652 | case tok::r_brace: |
653 | if (Closes.empty() || Closes.back() != Tok.kind()) |
654 | return std::nullopt; |
655 | Closes.pop_back(); |
656 | break; |
657 | case tok::semi: |
658 | // top level ; terminates all statements. |
659 | if (Closes.empty()) |
660 | return SelectorPieces.size() == NumArgs |
661 | ? std::optional(SymbolRange(SelectorPieces)) |
662 | : std::nullopt; |
663 | break; |
664 | default: |
665 | break; |
666 | } |
667 | } |
668 | return std::nullopt; |
669 | } |
670 | |
671 | /// Collects all ranges of the given identifier/selector in the source code. |
672 | /// |
673 | /// If `Name` is an Objective-C symbol name, this does a full lex of the given |
674 | /// source code in order to identify all selector fragments (e.g. in method |
675 | /// exprs/decls) since they are non-contiguous. |
676 | std::vector<SymbolRange> |
677 | collectRenameIdentifierRanges(const RenameSymbolName &Name, |
678 | llvm::StringRef Content, |
679 | const LangOptions &LangOpts) { |
680 | std::vector<SymbolRange> Ranges; |
681 | if (auto SinglePiece = Name.getSinglePiece()) { |
682 | auto IdentifierRanges = |
683 | collectIdentifierRanges(Identifier: *SinglePiece, Content, LangOpts); |
684 | for (const auto &R : IdentifierRanges) |
685 | Ranges.emplace_back(args: R); |
686 | return Ranges; |
687 | } |
688 | // FIXME: InMemoryFileAdapter crashes unless the buffer is null terminated! |
689 | std::string NullTerminatedCode = Content.str(); |
690 | SourceManagerForFile FileSM("mock_file_name.cpp" , NullTerminatedCode); |
691 | auto &SM = FileSM.get(); |
692 | |
693 | // We track parens and brackets to ensure that we don't accidentally try |
694 | // parsing a method declaration or definition which isn't at the top level or |
695 | // similar looking expressions (e.g. an @selector() expression). |
696 | llvm::SmallVector<tok::TokenKind, 8> Closes; |
697 | llvm::StringRef FirstSelPiece = Name.getNamePieces()[0]; |
698 | |
699 | auto Tokens = syntax::tokenize(FID: SM.getMainFileID(), SM, LO: LangOpts); |
700 | unsigned Last = Tokens.size() - 1; |
701 | for (unsigned Index = 0; Index < Last; ++Index) { |
702 | const auto &Tok = Tokens[Index]; |
703 | |
704 | // Search for the first selector piece to begin a match, but make sure we're |
705 | // not in () to avoid the @selector(foo:bar:) case. |
706 | if ((Closes.empty() || Closes.back() == tok::r_square) && |
707 | isMatchingSelectorName(Cur: Tok, Next: Tokens[Index + 1], SM, SelectorName: FirstSelPiece)) { |
708 | // We found a candidate for our match, this might be a method call, |
709 | // declaration, or unrelated identifier eg: |
710 | // - [obj ^sel0: X sel1: Y ... ] |
711 | // |
712 | // or |
713 | // |
714 | // @interface Foo |
715 | // - (int)^sel0:(int)x sel1:(int)y; |
716 | // @end |
717 | // |
718 | // or |
719 | // |
720 | // @implementation Foo |
721 | // - (int)^sel0:(int)x sel1:(int)y {} |
722 | // @end |
723 | // |
724 | // but not @selector(sel0:sel1:) |
725 | // |
726 | // Check if we can find all the relevant selector peices starting from |
727 | // this token |
728 | auto SelectorRanges = |
729 | findAllSelectorPieces(Tokens: ArrayRef(Tokens).slice(N: Index), SM, Name, |
730 | Terminator: Closes.empty() ? tok::l_brace : Closes.back()); |
731 | if (SelectorRanges) |
732 | Ranges.emplace_back(args: std::move(*SelectorRanges)); |
733 | } |
734 | |
735 | switch (Tok.kind()) { |
736 | case tok::l_square: |
737 | Closes.push_back(Elt: tok::r_square); |
738 | break; |
739 | case tok::l_paren: |
740 | Closes.push_back(Elt: tok::r_paren); |
741 | break; |
742 | case tok::r_square: |
743 | case tok::r_paren: |
744 | if (Closes.empty()) // Invalid code, give up on the rename. |
745 | return std::vector<SymbolRange>(); |
746 | |
747 | if (Closes.back() == Tok.kind()) |
748 | Closes.pop_back(); |
749 | break; |
750 | default: |
751 | break; |
752 | } |
753 | } |
754 | return Ranges; |
755 | } |
756 | |
757 | clangd::Range tokenRangeForLoc(ParsedAST &AST, SourceLocation TokLoc, |
758 | const SourceManager &SM, |
759 | const LangOptions &LangOpts) { |
760 | const auto *Token = AST.getTokens().spelledTokenContaining(Loc: TokLoc); |
761 | assert(Token && "rename expects spelled tokens" ); |
762 | clangd::Range Result; |
763 | Result.start = sourceLocToPosition(SM, Loc: Token->location()); |
764 | Result.end = sourceLocToPosition(SM, Loc: Token->endLocation()); |
765 | return Result; |
766 | } |
767 | |
768 | // AST-based ObjC method rename, it renames all occurrences in the main file |
769 | // even for selectors which may have multiple tokens. |
770 | llvm::Expected<tooling::Replacements> |
771 | renameObjCMethodWithinFile(ParsedAST &AST, const ObjCMethodDecl *MD, |
772 | llvm::StringRef NewName, |
773 | std::vector<SourceLocation> SelectorOccurences) { |
774 | const SourceManager &SM = AST.getSourceManager(); |
775 | auto Code = SM.getBufferData(FID: SM.getMainFileID()); |
776 | llvm::SmallVector<llvm::StringRef, 8> NewNames; |
777 | NewName.split(A&: NewNames, Separator: ":" ); |
778 | |
779 | std::vector<Range> Ranges; |
780 | const auto &LangOpts = MD->getASTContext().getLangOpts(); |
781 | for (const auto &Loc : SelectorOccurences) |
782 | Ranges.push_back(tokenRangeForLoc(AST, Loc, SM, LangOpts)); |
783 | auto FilePath = AST.tuPath(); |
784 | auto RenameRanges = collectRenameIdentifierRanges( |
785 | RenameSymbolName(MD->getDeclName()), Code, LangOpts); |
786 | auto RenameEdit = buildRenameEdit(FilePath, Code, RenameRanges, NewNames); |
787 | if (!RenameEdit) |
788 | return error("failed to rename in file {0}: {1}" , FilePath, |
789 | RenameEdit.takeError()); |
790 | return RenameEdit->Replacements; |
791 | } |
792 | |
793 | // AST-based rename, it renames all occurrences in the main file. |
794 | llvm::Expected<tooling::Replacements> |
795 | renameWithinFile(ParsedAST &AST, const NamedDecl &RenameDecl, |
796 | llvm::StringRef NewName) { |
797 | trace::Span Tracer("RenameWithinFile" ); |
798 | const SourceManager &SM = AST.getSourceManager(); |
799 | |
800 | tooling::Replacements FilteredChanges; |
801 | std::vector<SourceLocation> Locs; |
802 | for (SourceLocation Loc : findOccurrencesWithinFile(AST, ND: RenameDecl)) { |
803 | SourceLocation RenameLoc = Loc; |
804 | // We don't rename in any macro bodies, but we allow rename the symbol |
805 | // spelled in a top-level macro argument in the main file. |
806 | if (RenameLoc.isMacroID()) { |
807 | if (isInMacroBody(SM, Loc: RenameLoc)) |
808 | continue; |
809 | RenameLoc = SM.getSpellingLoc(Loc); |
810 | } |
811 | // Filter out locations not from main file. |
812 | // We traverse only main file decls, but locations could come from an |
813 | // non-preamble #include file e.g. |
814 | // void test() { |
815 | // int f^oo; |
816 | // #include "use_foo.inc" |
817 | // } |
818 | if (!isInsideMainFile(Loc: RenameLoc, SM)) |
819 | continue; |
820 | Locs.push_back(x: RenameLoc); |
821 | } |
822 | if (const auto *MD = dyn_cast<ObjCMethodDecl>(Val: &RenameDecl)) { |
823 | // The custom ObjC selector logic doesn't handle the zero arg selector |
824 | // case, as it relies on parsing selectors via the trailing `:`. |
825 | // We also choose to use regular rename logic for the single-arg selectors |
826 | // as the AST/Index has the right locations in that case. |
827 | if (MD->getSelector().getNumArgs() > 1) |
828 | return renameObjCMethodWithinFile(AST, MD, NewName, SelectorOccurences: std::move(Locs)); |
829 | |
830 | // Eat trailing : for single argument methods since they're actually |
831 | // considered a separate token during rename. |
832 | NewName.consume_back(Suffix: ":" ); |
833 | } |
834 | for (const auto &Loc : Locs) { |
835 | if (auto Err = FilteredChanges.add(R: tooling::Replacement( |
836 | SM, CharSourceRange::getTokenRange(R: Loc), NewName))) |
837 | return std::move(Err); |
838 | } |
839 | return FilteredChanges; |
840 | } |
841 | |
842 | Range toRange(const SymbolLocation &L) { |
843 | Range R; |
844 | R.start.line = L.Start.line(); |
845 | R.start.character = L.Start.column(); |
846 | R.end.line = L.End.line(); |
847 | R.end.character = L.End.column(); |
848 | return R; |
849 | } |
850 | |
851 | // Walk down from a virtual method to overriding methods, we rename them as a |
852 | // group. Note that canonicalRenameDecl() ensures we're starting from the base |
853 | // method. |
854 | void insertTransitiveOverrides(SymbolID Base, llvm::DenseSet<SymbolID> &IDs, |
855 | const SymbolIndex &Index) { |
856 | RelationsRequest Req; |
857 | Req.Predicate = RelationKind::OverriddenBy; |
858 | |
859 | llvm::DenseSet<SymbolID> Pending = {Base}; |
860 | while (!Pending.empty()) { |
861 | Req.Subjects = std::move(Pending); |
862 | Pending.clear(); |
863 | |
864 | Index.relations(Req, Callback: [&](const SymbolID &, const Symbol &Override) { |
865 | if (IDs.insert(V: Override.ID).second) |
866 | Pending.insert(V: Override.ID); |
867 | }); |
868 | } |
869 | } |
870 | |
871 | // Return all rename occurrences (using the index) outside of the main file, |
872 | // grouped by the absolute file path. |
873 | llvm::Expected<llvm::StringMap<std::vector<Range>>> |
874 | findOccurrencesOutsideFile(const NamedDecl &RenameDecl, |
875 | llvm::StringRef MainFile, const SymbolIndex &Index, |
876 | size_t MaxLimitFiles) { |
877 | trace::Span Tracer("FindOccurrencesOutsideFile" ); |
878 | RefsRequest RQuest; |
879 | RQuest.IDs.insert(V: getSymbolID(&RenameDecl)); |
880 | |
881 | if (const auto *MethodDecl = llvm::dyn_cast<CXXMethodDecl>(Val: &RenameDecl)) |
882 | if (MethodDecl->isVirtual()) |
883 | insertTransitiveOverrides(Base: *RQuest.IDs.begin(), IDs&: RQuest.IDs, Index); |
884 | |
885 | // Absolute file path => rename occurrences in that file. |
886 | llvm::StringMap<std::vector<Range>> AffectedFiles; |
887 | bool HasMore = Index.refs(Req: RQuest, Callback: [&](const Ref &R) { |
888 | if (AffectedFiles.size() >= MaxLimitFiles) |
889 | return; |
890 | if ((R.Kind & RefKind::Spelled) == RefKind::Unknown) |
891 | return; |
892 | if (auto RefFilePath = filePath(Loc: R.Location, /*HintFilePath=*/MainFile)) { |
893 | if (!pathEqual(*RefFilePath, MainFile)) |
894 | AffectedFiles[*RefFilePath].push_back(x: toRange(L: R.Location)); |
895 | } |
896 | }); |
897 | |
898 | if (AffectedFiles.size() >= MaxLimitFiles) |
899 | return error(Fmt: "The number of affected files exceeds the max limit {0}" , |
900 | Vals&: MaxLimitFiles); |
901 | if (HasMore) |
902 | return error(Fmt: "The symbol {0} has too many occurrences" , |
903 | Vals: RenameDecl.getQualifiedNameAsString()); |
904 | // Sort and deduplicate the results, in case that index returns duplications. |
905 | for (auto &FileAndOccurrences : AffectedFiles) { |
906 | auto &Ranges = FileAndOccurrences.getValue(); |
907 | llvm::sort(C&: Ranges); |
908 | Ranges.erase(first: llvm::unique(R&: Ranges), last: Ranges.end()); |
909 | |
910 | SPAN_ATTACH(Tracer, FileAndOccurrences.first(), |
911 | static_cast<int64_t>(Ranges.size())); |
912 | } |
913 | return AffectedFiles; |
914 | } |
915 | |
916 | // Index-based rename, it renames all occurrences outside of the main file. |
917 | // |
918 | // The cross-file rename is purely based on the index, as we don't want to |
919 | // build all ASTs for affected files, which may cause a performance hit. |
920 | // We choose to trade off some correctness for performance and scalability. |
921 | // |
922 | // Clangd builds a dynamic index for all opened files on top of the static |
923 | // index of the whole codebase. Dynamic index is up-to-date (respects dirty |
924 | // buffers) as long as clangd finishes processing opened files, while static |
925 | // index (background index) is relatively stale. We choose the dirty buffers |
926 | // as the file content we rename on, and fallback to file content on disk if |
927 | // there is no dirty buffer. |
928 | llvm::Expected<FileEdits> |
929 | renameOutsideFile(const NamedDecl &RenameDecl, llvm::StringRef MainFilePath, |
930 | llvm::StringRef NewName, const SymbolIndex &Index, |
931 | size_t MaxLimitFiles, llvm::vfs::FileSystem &FS) { |
932 | trace::Span Tracer("RenameOutsideFile" ); |
933 | auto AffectedFiles = findOccurrencesOutsideFile(RenameDecl, MainFile: MainFilePath, |
934 | Index, MaxLimitFiles); |
935 | if (!AffectedFiles) |
936 | return AffectedFiles.takeError(); |
937 | FileEdits Results; |
938 | for (auto &FileAndOccurrences : *AffectedFiles) { |
939 | llvm::StringRef FilePath = FileAndOccurrences.first(); |
940 | |
941 | auto ExpBuffer = FS.getBufferForFile(Name: FilePath); |
942 | if (!ExpBuffer) { |
943 | elog(Fmt: "Fail to read file content: Fail to open file {0}: {1}" , Vals&: FilePath, |
944 | Vals: ExpBuffer.getError().message()); |
945 | continue; |
946 | } |
947 | RenameSymbolName RenameName(RenameDecl.getDeclName()); |
948 | llvm::SmallVector<llvm::StringRef, 8> NewNames; |
949 | NewName.split(A&: NewNames, Separator: ":" ); |
950 | |
951 | auto AffectedFileCode = (*ExpBuffer)->getBuffer(); |
952 | auto RenameRanges = adjustRenameRanges( |
953 | AffectedFileCode, RenameName, std::move(FileAndOccurrences.second), |
954 | RenameDecl.getASTContext().getLangOpts()); |
955 | if (!RenameRanges) { |
956 | // Our heuristics fails to adjust rename ranges to the current state of |
957 | // the file, it is most likely the index is stale, so we give up the |
958 | // entire rename. |
959 | return error(Fmt: "Index results don't match the content of file {0} " |
960 | "(the index may be stale)" , |
961 | Vals&: FilePath); |
962 | } |
963 | auto RenameEdit = |
964 | buildRenameEdit(FilePath, AffectedFileCode, *RenameRanges, NewNames); |
965 | if (!RenameEdit) |
966 | return error("failed to rename in file {0}: {1}" , FilePath, |
967 | RenameEdit.takeError()); |
968 | if (!RenameEdit->Replacements.empty()) |
969 | Results.insert({FilePath, std::move(*RenameEdit)}); |
970 | } |
971 | return Results; |
972 | } |
973 | |
974 | // A simple edit is either changing line or column, but not both. |
975 | bool impliesSimpleEdit(const Position &LHS, const Position &RHS) { |
976 | return LHS.line == RHS.line || LHS.character == RHS.character; |
977 | } |
978 | |
979 | // Performs a DFS to enumerate all possible near-miss matches. |
980 | // It finds the locations where the indexed occurrences are now spelled in |
981 | // Lexed occurrences, a near miss is defined as: |
982 | // - a near miss maps all of the **name** occurrences from the index onto a |
983 | // *subset* of lexed occurrences (we allow a single name refers to more |
984 | // than one symbol) |
985 | // - all indexed occurrences must be mapped, and Result must be distinct and |
986 | // preserve order (only support detecting simple edits to ensure a |
987 | // robust mapping) |
988 | // - each indexed -> lexed occurrences mapping correspondence may change the |
989 | // *line* or *column*, but not both (increases chance of a robust mapping) |
990 | void findNearMiss( |
991 | std::vector<size_t> &PartialMatch, ArrayRef<Range> IndexedRest, |
992 | ArrayRef<SymbolRange> LexedRest, int LexedIndex, int &Fuel, |
993 | llvm::function_ref<void(const std::vector<size_t> &)> MatchedCB) { |
994 | if (--Fuel < 0) |
995 | return; |
996 | if (IndexedRest.size() > LexedRest.size()) |
997 | return; |
998 | if (IndexedRest.empty()) { |
999 | MatchedCB(PartialMatch); |
1000 | return; |
1001 | } |
1002 | if (impliesSimpleEdit(LHS: IndexedRest.front().start, |
1003 | RHS: LexedRest.front().range().start)) { |
1004 | PartialMatch.push_back(x: LexedIndex); |
1005 | findNearMiss(PartialMatch, IndexedRest: IndexedRest.drop_front(), LexedRest: LexedRest.drop_front(), |
1006 | LexedIndex: LexedIndex + 1, Fuel, MatchedCB); |
1007 | PartialMatch.pop_back(); |
1008 | } |
1009 | findNearMiss(PartialMatch, IndexedRest, LexedRest: LexedRest.drop_front(), |
1010 | LexedIndex: LexedIndex + 1, Fuel, MatchedCB); |
1011 | } |
1012 | |
1013 | } // namespace |
1014 | |
1015 | RenameSymbolName::RenameSymbolName() : NamePieces({}) {} |
1016 | |
1017 | namespace { |
1018 | std::vector<std::string> (const DeclarationName &DeclName) { |
1019 | if (DeclName.getNameKind() == |
1020 | DeclarationName::NameKind::ObjCMultiArgSelector || |
1021 | DeclName.getNameKind() == DeclarationName::NameKind::ObjCOneArgSelector) { |
1022 | const Selector &Sel = DeclName.getObjCSelector(); |
1023 | std::vector<std::string> Result; |
1024 | for (unsigned Slot = 0; Slot < Sel.getNumArgs(); ++Slot) { |
1025 | Result.push_back(x: Sel.getNameForSlot(argIndex: Slot).str()); |
1026 | } |
1027 | return Result; |
1028 | } |
1029 | return {DeclName.getAsString()}; |
1030 | } |
1031 | } // namespace |
1032 | |
1033 | RenameSymbolName::RenameSymbolName(const DeclarationName &DeclName) |
1034 | : RenameSymbolName(extractNamePieces(DeclName)) {} |
1035 | |
1036 | RenameSymbolName::RenameSymbolName(ArrayRef<std::string> NamePieces) { |
1037 | for (const auto &Piece : NamePieces) |
1038 | this->NamePieces.push_back(Elt: Piece); |
1039 | } |
1040 | |
1041 | std::optional<std::string> RenameSymbolName::getSinglePiece() const { |
1042 | if (getNamePieces().size() == 1) { |
1043 | return NamePieces.front(); |
1044 | } |
1045 | return std::nullopt; |
1046 | } |
1047 | |
1048 | std::string RenameSymbolName::getAsString() const { |
1049 | std::string Result; |
1050 | llvm::raw_string_ostream OS(Result); |
1051 | this->print(OS); |
1052 | return Result; |
1053 | } |
1054 | |
1055 | void RenameSymbolName::print(raw_ostream &OS) const { |
1056 | llvm::interleave(c: NamePieces, os&: OS, separator: ":" ); |
1057 | } |
1058 | |
1059 | SymbolRange::SymbolRange(Range R) : Ranges({R}) {} |
1060 | |
1061 | SymbolRange::SymbolRange(std::vector<Range> Ranges) |
1062 | : Ranges(std::move(Ranges)) {} |
1063 | |
1064 | Range SymbolRange::range() const { return Ranges.front(); } |
1065 | |
1066 | bool operator==(const SymbolRange &LHS, const SymbolRange &RHS) { |
1067 | return LHS.Ranges == RHS.Ranges; |
1068 | } |
1069 | bool operator!=(const SymbolRange &LHS, const SymbolRange &RHS) { |
1070 | return !(LHS == RHS); |
1071 | } |
1072 | bool operator<(const SymbolRange &LHS, const SymbolRange &RHS) { |
1073 | return LHS.range() < RHS.range(); |
1074 | } |
1075 | |
1076 | llvm::Expected<RenameResult> rename(const RenameInputs &RInputs) { |
1077 | assert(!RInputs.Index == !RInputs.FS && |
1078 | "Index and FS must either both be specified or both null." ); |
1079 | trace::Span Tracer("Rename flow" ); |
1080 | const auto &Opts = RInputs.Opts; |
1081 | ParsedAST &AST = RInputs.AST; |
1082 | const SourceManager &SM = AST.getSourceManager(); |
1083 | llvm::StringRef MainFileCode = SM.getBufferData(FID: SM.getMainFileID()); |
1084 | // Try to find the tokens adjacent to the cursor position. |
1085 | auto Loc = sourceLocationInMainFile(SM, P: RInputs.Pos); |
1086 | if (!Loc) |
1087 | return Loc.takeError(); |
1088 | const syntax::Token *IdentifierToken = |
1089 | spelledIdentifierTouching(Loc: *Loc, Tokens: AST.getTokens()); |
1090 | |
1091 | // Renames should only triggered on identifiers. |
1092 | if (!IdentifierToken) |
1093 | return makeError(Reason: ReasonToReject::NoSymbolFound); |
1094 | Range CurrentIdentifier = halfOpenToRange( |
1095 | SM, R: CharSourceRange::getCharRange(B: IdentifierToken->location(), |
1096 | E: IdentifierToken->endLocation())); |
1097 | // FIXME: Renaming macros is not supported yet, the macro-handling code should |
1098 | // be moved to rename tooling library. |
1099 | if (locateMacroAt(SpelledTok: *IdentifierToken, PP&: AST.getPreprocessor())) |
1100 | return makeError(Reason: ReasonToReject::UnsupportedSymbol); |
1101 | |
1102 | auto DeclsUnderCursor = locateDeclAt(AST, TokenStartLoc: IdentifierToken->location()); |
1103 | filterRenameTargets(Decls&: DeclsUnderCursor); |
1104 | if (DeclsUnderCursor.empty()) |
1105 | return makeError(Reason: ReasonToReject::NoSymbolFound); |
1106 | if (DeclsUnderCursor.size() > 1) |
1107 | return makeError(Reason: ReasonToReject::AmbiguousSymbol); |
1108 | |
1109 | const auto &RenameDecl = **DeclsUnderCursor.begin(); |
1110 | static constexpr trace::Metric RenameTriggerCounter( |
1111 | "rename_trigger_count" , trace::Metric::Counter, "decl_kind" ); |
1112 | RenameTriggerCounter.record(Value: 1, Label: RenameDecl.getDeclKindName()); |
1113 | |
1114 | std::string Placeholder = getName(RenameDecl); |
1115 | auto Invalid = checkName(RenameDecl, NewName: RInputs.NewName, OldName: Placeholder); |
1116 | if (Invalid) |
1117 | return std::move(Invalid); |
1118 | |
1119 | auto Reject = |
1120 | renameable(RenameDecl, MainFilePath: RInputs.MainFilePath, Index: RInputs.Index, Opts); |
1121 | if (Reject) |
1122 | return makeError(Reason: *Reject); |
1123 | |
1124 | // We have two implementations of the rename: |
1125 | // - AST-based rename: used for renaming local symbols, e.g. variables |
1126 | // defined in a function body; |
1127 | // - index-based rename: used for renaming non-local symbols, and not |
1128 | // feasible for local symbols (as by design our index don't index these |
1129 | // symbols by design; |
1130 | // To make cross-file rename work for local symbol, we use a hybrid solution: |
1131 | // - run AST-based rename on the main file; |
1132 | // - run index-based rename on other affected files; |
1133 | auto MainFileRenameEdit = renameWithinFile(AST, RenameDecl, NewName: RInputs.NewName); |
1134 | if (!MainFileRenameEdit) |
1135 | return MainFileRenameEdit.takeError(); |
1136 | |
1137 | llvm::DenseSet<Range> RenamedRanges; |
1138 | if (!isa<ObjCMethodDecl>(Val: RenameDecl)) { |
1139 | // TODO: Insert the ranges from the ObjCMethodDecl/ObjCMessageExpr selector |
1140 | // pieces which are being renamed. This will require us to make changes to |
1141 | // locateDeclAt to preserve this AST node. |
1142 | RenamedRanges.insert(V: CurrentIdentifier); |
1143 | } |
1144 | |
1145 | // Check the rename-triggering location is actually being renamed. |
1146 | // This is a robustness check to avoid surprising rename results -- if the |
1147 | // the triggering location is not actually the name of the node we identified |
1148 | // (e.g. for broken code), then rename is likely not what users expect, so we |
1149 | // reject this kind of rename. |
1150 | for (const auto &Range : RenamedRanges) { |
1151 | auto StartOffset = positionToOffset(Code: MainFileCode, P: Range.start); |
1152 | auto EndOffset = positionToOffset(Code: MainFileCode, P: Range.end); |
1153 | if (!StartOffset) |
1154 | return StartOffset.takeError(); |
1155 | if (!EndOffset) |
1156 | return EndOffset.takeError(); |
1157 | if (llvm::none_of( |
1158 | Range&: *MainFileRenameEdit, |
1159 | P: [&StartOffset, &EndOffset](const clang::tooling::Replacement &R) { |
1160 | return R.getOffset() == *StartOffset && |
1161 | R.getLength() == *EndOffset - *StartOffset; |
1162 | })) { |
1163 | return makeError(Reason: ReasonToReject::NoSymbolFound); |
1164 | } |
1165 | } |
1166 | RenameResult Result; |
1167 | Result.Target = CurrentIdentifier; |
1168 | Result.Placeholder = Placeholder; |
1169 | Edit MainFileEdits = Edit(MainFileCode, std::move(*MainFileRenameEdit)); |
1170 | for (const TextEdit &TE : MainFileEdits.asTextEdits()) |
1171 | Result.LocalChanges.push_back(x: TE.range); |
1172 | |
1173 | // return the main file edit if this is a within-file rename or the symbol |
1174 | // being renamed is function local. |
1175 | if (RenameDecl.getParentFunctionOrMethod()) { |
1176 | Result.GlobalChanges = FileEdits( |
1177 | {std::make_pair(x: RInputs.MainFilePath, y: std::move(MainFileEdits))}); |
1178 | return Result; |
1179 | } |
1180 | |
1181 | // If the index is nullptr, we don't know the completeness of the result, so |
1182 | // we don't populate the field GlobalChanges. |
1183 | if (!RInputs.Index) { |
1184 | assert(Result.GlobalChanges.empty()); |
1185 | return Result; |
1186 | } |
1187 | |
1188 | auto OtherFilesEdits = renameOutsideFile( |
1189 | RenameDecl, MainFilePath: RInputs.MainFilePath, NewName: RInputs.NewName, Index: *RInputs.Index, |
1190 | MaxLimitFiles: Opts.LimitFiles == 0 ? std::numeric_limits<size_t>::max() |
1191 | : Opts.LimitFiles, |
1192 | FS&: *RInputs.FS); |
1193 | if (!OtherFilesEdits) |
1194 | return OtherFilesEdits.takeError(); |
1195 | Result.GlobalChanges = *OtherFilesEdits; |
1196 | // Attach the rename edits for the main file. |
1197 | Result.GlobalChanges.try_emplace(Key: RInputs.MainFilePath, |
1198 | Args: std::move(MainFileEdits)); |
1199 | return Result; |
1200 | } |
1201 | |
1202 | llvm::Expected<Edit> buildRenameEdit(llvm::StringRef AbsFilePath, |
1203 | llvm::StringRef InitialCode, |
1204 | std::vector<SymbolRange> Occurrences, |
1205 | llvm::ArrayRef<llvm::StringRef> NewNames) { |
1206 | trace::Span Tracer("BuildRenameEdit" ); |
1207 | SPAN_ATTACH(Tracer, "file_path" , AbsFilePath); |
1208 | SPAN_ATTACH(Tracer, "rename_occurrences" , |
1209 | static_cast<int64_t>(Occurrences.size())); |
1210 | |
1211 | assert(llvm::is_sorted(Occurrences)); |
1212 | assert(llvm::unique(Occurrences) == Occurrences.end() && |
1213 | "Occurrences must be unique" ); |
1214 | |
1215 | // These two always correspond to the same position. |
1216 | Position LastPos{.line: 0, .character: 0}; |
1217 | size_t LastOffset = 0; |
1218 | |
1219 | auto Offset = [&](const Position &P) -> llvm::Expected<size_t> { |
1220 | assert(LastPos <= P && "malformed input" ); |
1221 | Position Shifted = { |
1222 | .line: P.line - LastPos.line, |
1223 | .character: P.line > LastPos.line ? P.character : P.character - LastPos.character}; |
1224 | auto ShiftedOffset = |
1225 | positionToOffset(Code: InitialCode.substr(Start: LastOffset), P: Shifted); |
1226 | if (!ShiftedOffset) |
1227 | return error(Fmt: "fail to convert the position {0} to offset ({1})" , Vals: P, |
1228 | Vals: ShiftedOffset.takeError()); |
1229 | LastPos = P; |
1230 | LastOffset += *ShiftedOffset; |
1231 | return LastOffset; |
1232 | }; |
1233 | |
1234 | struct OccurrenceOffset { |
1235 | size_t Start; |
1236 | size_t End; |
1237 | llvm::StringRef NewName; |
1238 | |
1239 | OccurrenceOffset(size_t Start, size_t End, llvm::StringRef NewName) |
1240 | : Start(Start), End(End), NewName(NewName) {} |
1241 | }; |
1242 | |
1243 | std::vector<OccurrenceOffset> OccurrencesOffsets; |
1244 | for (const auto &SR : Occurrences) { |
1245 | for (auto [Range, NewName] : llvm::zip(t: SR.Ranges, u&: NewNames)) { |
1246 | auto StartOffset = Offset(Range.start); |
1247 | if (!StartOffset) |
1248 | return StartOffset.takeError(); |
1249 | auto EndOffset = Offset(Range.end); |
1250 | if (!EndOffset) |
1251 | return EndOffset.takeError(); |
1252 | // Nothing to do if the token/name hasn't changed. |
1253 | auto CurName = |
1254 | InitialCode.substr(Start: *StartOffset, N: *EndOffset - *StartOffset); |
1255 | if (CurName == NewName) |
1256 | continue; |
1257 | OccurrencesOffsets.emplace_back(args&: *StartOffset, args&: *EndOffset, args: NewName); |
1258 | } |
1259 | } |
1260 | |
1261 | tooling::Replacements RenameEdit; |
1262 | for (const auto &R : OccurrencesOffsets) { |
1263 | auto ByteLength = R.End - R.Start; |
1264 | if (auto Err = RenameEdit.add( |
1265 | R: tooling::Replacement(AbsFilePath, R.Start, ByteLength, R.NewName))) |
1266 | return std::move(Err); |
1267 | } |
1268 | return Edit(InitialCode, std::move(RenameEdit)); |
1269 | } |
1270 | |
1271 | // Details: |
1272 | // - lex the draft code to get all rename candidates, this yields a superset |
1273 | // of candidates. |
1274 | // - apply range patching heuristics to generate "authoritative" occurrences, |
1275 | // cases we consider: |
1276 | // (a) index returns a subset of candidates, we use the indexed results. |
1277 | // - fully equal, we are sure the index is up-to-date |
1278 | // - proper subset, index is correct in most cases? there may be false |
1279 | // positives (e.g. candidates got appended), but rename is still safe |
1280 | // (b) index returns non-candidate results, we attempt to map the indexed |
1281 | // ranges onto candidates in a plausible way (e.g. guess that lines |
1282 | // were inserted). If such a "near miss" is found, the rename is still |
1283 | // possible |
1284 | std::optional<std::vector<SymbolRange>> |
1285 | adjustRenameRanges(llvm::StringRef DraftCode, const RenameSymbolName &Name, |
1286 | std::vector<Range> Indexed, const LangOptions &LangOpts) { |
1287 | trace::Span Tracer("AdjustRenameRanges" ); |
1288 | assert(!Indexed.empty()); |
1289 | assert(llvm::is_sorted(Indexed)); |
1290 | std::vector<SymbolRange> Lexed = |
1291 | collectRenameIdentifierRanges(Name, Content: DraftCode, LangOpts); |
1292 | llvm::sort(C&: Lexed); |
1293 | return getMappedRanges(Indexed, Lexed); |
1294 | } |
1295 | |
1296 | std::optional<std::vector<SymbolRange>> |
1297 | getMappedRanges(ArrayRef<Range> Indexed, ArrayRef<SymbolRange> Lexed) { |
1298 | trace::Span Tracer("GetMappedRanges" ); |
1299 | assert(!Indexed.empty()); |
1300 | assert(llvm::is_sorted(Indexed)); |
1301 | assert(llvm::is_sorted(Lexed)); |
1302 | |
1303 | if (Indexed.size() > Lexed.size()) { |
1304 | vlog(Fmt: "The number of lexed occurrences is less than indexed occurrences" ); |
1305 | SPAN_ATTACH( |
1306 | Tracer, "error" , |
1307 | "The number of lexed occurrences is less than indexed occurrences" ); |
1308 | return std::nullopt; |
1309 | } |
1310 | // Fast check for the special subset case. |
1311 | if (std::includes(first1: Indexed.begin(), last1: Indexed.end(), first2: Lexed.begin(), last2: Lexed.end())) |
1312 | return Lexed.vec(); |
1313 | |
1314 | std::vector<size_t> Best; |
1315 | size_t BestCost = std::numeric_limits<size_t>::max(); |
1316 | bool HasMultiple = false; |
1317 | std::vector<size_t> ResultStorage; |
1318 | int Fuel = 10000; |
1319 | findNearMiss(PartialMatch&: ResultStorage, IndexedRest: Indexed, LexedRest: Lexed, LexedIndex: 0, Fuel, |
1320 | MatchedCB: [&](const std::vector<size_t> &Matched) { |
1321 | size_t MCost = |
1322 | renameRangeAdjustmentCost(Indexed, Lexed, MappedIndex: Matched); |
1323 | if (MCost < BestCost) { |
1324 | BestCost = MCost; |
1325 | Best = std::move(Matched); |
1326 | HasMultiple = false; // reset |
1327 | return; |
1328 | } |
1329 | if (MCost == BestCost) |
1330 | HasMultiple = true; |
1331 | }); |
1332 | if (HasMultiple) { |
1333 | vlog(Fmt: "The best near miss is not unique." ); |
1334 | SPAN_ATTACH(Tracer, "error" , "The best near miss is not unique" ); |
1335 | return std::nullopt; |
1336 | } |
1337 | if (Best.empty()) { |
1338 | vlog(Fmt: "Didn't find a near miss." ); |
1339 | SPAN_ATTACH(Tracer, "error" , "Didn't find a near miss" ); |
1340 | return std::nullopt; |
1341 | } |
1342 | std::vector<SymbolRange> Mapped; |
1343 | for (auto I : Best) |
1344 | Mapped.push_back(x: Lexed[I]); |
1345 | SPAN_ATTACH(Tracer, "mapped_ranges" , static_cast<int64_t>(Mapped.size())); |
1346 | return Mapped; |
1347 | } |
1348 | |
1349 | // The cost is the sum of the implied edit sizes between successive diffs, only |
1350 | // simple edits are considered: |
1351 | // - insert/remove a line (change line offset) |
1352 | // - insert/remove a character on an existing line (change column offset) |
1353 | // |
1354 | // Example I, total result is 1 + 1 = 2. |
1355 | // diff[0]: line + 1 <- insert a line before edit 0. |
1356 | // diff[1]: line + 1 |
1357 | // diff[2]: line + 1 |
1358 | // diff[3]: line + 2 <- insert a line before edits 2 and 3. |
1359 | // |
1360 | // Example II, total result is 1 + 1 + 1 = 3. |
1361 | // diff[0]: line + 1 <- insert a line before edit 0. |
1362 | // diff[1]: column + 1 <- remove a line between edits 0 and 1, and insert a |
1363 | // character on edit 1. |
1364 | size_t renameRangeAdjustmentCost(ArrayRef<Range> Indexed, |
1365 | ArrayRef<SymbolRange> Lexed, |
1366 | ArrayRef<size_t> MappedIndex) { |
1367 | assert(Indexed.size() == MappedIndex.size()); |
1368 | assert(llvm::is_sorted(Indexed)); |
1369 | assert(llvm::is_sorted(Lexed)); |
1370 | |
1371 | int LastLine = -1; |
1372 | int LastDLine = 0, LastDColumn = 0; |
1373 | int Cost = 0; |
1374 | for (size_t I = 0; I < Indexed.size(); ++I) { |
1375 | int DLine = |
1376 | Indexed[I].start.line - Lexed[MappedIndex[I]].range().start.line; |
1377 | int DColumn = Indexed[I].start.character - |
1378 | Lexed[MappedIndex[I]].range().start.character; |
1379 | int Line = Indexed[I].start.line; |
1380 | if (Line != LastLine) |
1381 | LastDColumn = 0; // column offsets don't carry cross lines. |
1382 | Cost += abs(x: DLine - LastDLine) + abs(x: DColumn - LastDColumn); |
1383 | std::tie(args&: LastLine, args&: LastDLine, args&: LastDColumn) = std::tie(args&: Line, args&: DLine, args&: DColumn); |
1384 | } |
1385 | return Cost; |
1386 | } |
1387 | |
1388 | } // namespace clangd |
1389 | } // namespace clang |
1390 | |