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
41namespace clang {
42namespace clangd {
43namespace {
44
45std::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.
59bool 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.
88const 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.
148const 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
158llvm::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
180void 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.
198bool isExcluded(const NamedDecl &RenameDecl) {
199 const auto &SM = RenameDecl.getASTContext().getSourceManager();
200 return SM.isInSystemHeader(RenameDecl.getLocation()) ||
201 isProtoFile(RenameDecl.getLocation(), SM);
202}
203
204enum class ReasonToReject {
205 NoSymbolFound,
206 NoIndexProvided,
207 NonIndexable,
208 UnsupportedSymbol,
209 AmbiguousSymbol,
210
211 // name validation. FIXME: reconcile with InvalidName
212 SameName,
213};
214
215std::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
265llvm::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.
287std::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.
314const 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.
429const 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
465const 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
475struct InvalidName {
476 enum Kind {
477 Keywords,
478 Conflict,
479 BadIdentifier,
480 };
481 Kind K;
482 std::string Details;
483};
484std::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
496llvm::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
513static 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
531std::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.
541llvm::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
581bool 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
588bool 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.
599std::optional<SymbolRange>
600findAllSelectorPieces(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.
676std::vector<SymbolRange>
677collectRenameIdentifierRanges(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
757clangd::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.
770llvm::Expected<tooling::Replacements>
771renameObjCMethodWithinFile(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.
794llvm::Expected<tooling::Replacements>
795renameWithinFile(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
842Range 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.
854void 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.
873llvm::Expected<llvm::StringMap<std::vector<Range>>>
874findOccurrencesOutsideFile(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.
928llvm::Expected<FileEdits>
929renameOutsideFile(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.
975bool 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)
990void 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
1015RenameSymbolName::RenameSymbolName() : NamePieces({}) {}
1016
1017namespace {
1018std::vector<std::string> extractNamePieces(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
1033RenameSymbolName::RenameSymbolName(const DeclarationName &DeclName)
1034 : RenameSymbolName(extractNamePieces(DeclName)) {}
1035
1036RenameSymbolName::RenameSymbolName(ArrayRef<std::string> NamePieces) {
1037 for (const auto &Piece : NamePieces)
1038 this->NamePieces.push_back(Elt: Piece);
1039}
1040
1041std::optional<std::string> RenameSymbolName::getSinglePiece() const {
1042 if (getNamePieces().size() == 1) {
1043 return NamePieces.front();
1044 }
1045 return std::nullopt;
1046}
1047
1048std::string RenameSymbolName::getAsString() const {
1049 std::string Result;
1050 llvm::raw_string_ostream OS(Result);
1051 this->print(OS);
1052 return Result;
1053}
1054
1055void RenameSymbolName::print(raw_ostream &OS) const {
1056 llvm::interleave(c: NamePieces, os&: OS, separator: ":");
1057}
1058
1059SymbolRange::SymbolRange(Range R) : Ranges({R}) {}
1060
1061SymbolRange::SymbolRange(std::vector<Range> Ranges)
1062 : Ranges(std::move(Ranges)) {}
1063
1064Range SymbolRange::range() const { return Ranges.front(); }
1065
1066bool operator==(const SymbolRange &LHS, const SymbolRange &RHS) {
1067 return LHS.Ranges == RHS.Ranges;
1068}
1069bool operator!=(const SymbolRange &LHS, const SymbolRange &RHS) {
1070 return !(LHS == RHS);
1071}
1072bool operator<(const SymbolRange &LHS, const SymbolRange &RHS) {
1073 return LHS.range() < RHS.range();
1074}
1075
1076llvm::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
1202llvm::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
1284std::optional<std::vector<SymbolRange>>
1285adjustRenameRanges(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
1296std::optional<std::vector<SymbolRange>>
1297getMappedRanges(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.
1364size_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

source code of clang-tools-extra/clangd/refactor/Rename.cpp