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

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