clang-tools 20.0.0git
Rename.cpp
Go to the documentation of this file.
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"
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(Loc.FileURI, HintFilePath);
48 if (!Path) {
49 elog("Could not resolve URI {0}: {1}", Loc.FileURI, 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>(D))
88 return canonicalRenameDecl(
89 VarTemplate->getSpecializedTemplate()->getTemplatedDecl());
90 if (const auto *Template = dyn_cast<TemplateDecl>(D))
91 if (const NamedDecl *TemplatedDecl = Template->getTemplatedDecl())
92 return canonicalRenameDecl(TemplatedDecl);
93 if (const auto *ClassTemplateSpecialization =
94 dyn_cast<ClassTemplateSpecializationDecl>(D))
95 return canonicalRenameDecl(
96 ClassTemplateSpecialization->getSpecializedTemplate()
97 ->getTemplatedDecl());
98 if (const auto *Method = dyn_cast<CXXMethodDecl>(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>(D))
113 if (const FunctionTemplateDecl *Template = Function->getPrimaryTemplate())
114 return canonicalRenameDecl(Template);
115 if (const auto *Field = dyn_cast<FieldDecl>(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>(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("FieldParent should have field with the same name as Field.");
132 }
133 if (const auto *VD = dyn_cast<VarDecl>(D)) {
134 if (const VarDecl *OriginalVD = VD->getInstantiatedFromStaticDataMember())
135 return canonicalRenameDecl(OriginalVD);
136 }
137 if (const auto *UD = dyn_cast<UsingShadowDecl>(D)) {
138 if (const auto *TargetDecl = UD->getTargetDecl())
139 return canonicalRenameDecl(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>(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(TokenStartLoc).second;
160
161 SelectionTree Selection = SelectionTree::createRight(
162 AST.getASTContext(), AST.getTokens(), Offset, 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,
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(Decls.begin(), Decls.end(), [](const NamedDecl *D) {
187 return llvm::isa<UsingDecl>(D);
188 });
189 if (UD != Decls.end()) {
190 Decls.erase(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>(&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>(&RenameDecl))
229 return ReasonToReject::UnsupportedSymbol;
230 // Filter out symbols that are unsupported in both rename modes.
231 if (llvm::isa<NamespaceDecl>(&RenameDecl))
232 return ReasonToReject::UnsupportedSymbol;
233 if (const auto *FD = llvm::dyn_cast<FunctionDecl>(&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.
257 RenameDecl, RenameDecl.getASTContext(), SymbolCollector::Options(),
258 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("Cannot rename symbol: {0}", 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()) {
295 TopLevelDecl,
296 [&](ReferenceLoc Ref) {
297 if (Ref.Targets.empty())
298 return;
299 for (const auto *Target : Ref.Targets) {
300 if (canonicalRenameDecl(Target) == &ND) {
301 Results.push_back(Ref.NameLoc);
302 return;
303 }
304 }
305 },
306 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(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(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>(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>(S))
348 for (const auto *Node : CS->children())
349 if (const auto *Result = CheckDeclStmt(dyn_cast<DeclStmt>(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>(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>(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(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 };
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("the chosen name \"{0}\" is a keyword",
494 Reason.Details);
495 case InvalidName::Conflict:
496 return llvm::formatv("conflict with the symbol in {0}", Reason.Details);
497 case InvalidName::BadIdentifier:
498 return llvm::formatv("the chosen name \"{0}\" is not a valid identifier",
499 Reason.Details);
500 }
501 llvm_unreachable("unhandled InvalidName kind");
502 };
503 return error("invalid name: {0}", 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(Ident.front()) &&
513 !isAsciiIdentifierStart(Ident.front(), AllowDollar))
514 return false;
515 for (char C : Ident) {
516 if (AllowColon && C == ':')
517 continue;
518 if (llvm::isASCII(C) && !isAsciiIdentifierContinue(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>(&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(ReasonToReject::SameName);
542
543 if (const auto *MD = dyn_cast<ObjCMethodDecl>(&RenameDecl)) {
544 const auto Sel = MD->getSelector();
545 if (Sel.getNumArgs() != NewName.count(':') &&
546 NewName != "__clangd_rename_placeholder")
547 return makeError(InvalidName{InvalidName::BadIdentifier, NewName.str()});
548 }
549
550 auto &ASTCtx = RenameDecl.getASTContext();
551 std::optional<InvalidName> Result;
552 if (isKeyword(NewName, ASTCtx.getLangOpts()))
553 Result = InvalidName{InvalidName::Keywords, NewName.str()};
554 else if (!mayBeValidIdentifier(NewName, isa<ObjCMethodDecl>(&RenameDecl)))
555 Result = InvalidName{InvalidName::BadIdentifier, 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(1, toString(Result->K));
569 return makeError(*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(Tok, Tokens[Index + 1], SM,
608 Sel.getNameForSlot(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(PieceCount).empty())
614 ++Index;
615 SelectorPieces.push_back(
616 halfOpenToRange(SM, 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(Tok, 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(tok::r_square);
635 break;
636 case tok::l_paren:
637 Closes.push_back(tok::r_paren);
638 break;
639 case tok::l_brace:
640 Closes.push_back(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(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(SM.getMainFileID(), SM, 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(Tok, Tokens[Index + 1], SM, 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(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(tok::r_square);
729 break;
730 case tok::l_paren:
731 Closes.push_back(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().spelledTokenContaining(TokLoc);
752 assert(Token && "rename expects spelled tokens");
753 clangd::Range Result;
754 Result.start = sourceLocToPosition(SM, Token->location());
755 Result.end = sourceLocToPosition(SM, 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(SM.getMainFileID());
767 auto RenameIdentifier = MD->getSelector().getNameForSlot(0).str();
768 llvm::SmallVector<llvm::StringRef, 8> NewNames;
769 NewName.split(NewNames, ":");
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, 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, 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(RenameLoc, SM))
811 continue;
812 Locs.push_back(RenameLoc);
813 }
814 if (const auto *MD = dyn_cast<ObjCMethodDecl>(&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, 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(":");
825 }
826 for (const auto &Loc : Locs) {
827 if (auto Err = FilteredChanges.add(tooling::Replacement(
828 SM, CharSourceRange::getTokenRange(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, [&](const SymbolID &, const Symbol &Override) {
857 if (IDs.insert(Override.ID).second)
858 Pending.insert(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(getSymbolID(&RenameDecl));
872
873 if (const auto *MethodDecl = llvm::dyn_cast<CXXMethodDecl>(&RenameDecl))
874 if (MethodDecl->isVirtual())
875 insertTransitiveOverrides(*RQuest.IDs.begin(), 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(RQuest, [&](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(R.Location, /*HintFilePath=*/MainFile)) {
885 if (!pathEqual(*RefFilePath, MainFile))
886 AffectedFiles[*RefFilePath].push_back(toRange(R.Location));
887 }
888 });
889
890 if (AffectedFiles.size() >= MaxLimitFiles)
891 return error("The number of affected files exceeds the max limit {0}",
892 MaxLimitFiles);
893 if (HasMore)
894 return error("The symbol {0} has too many occurrences",
895 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(Ranges);
900 Ranges.erase(std::unique(Ranges.begin(), Ranges.end()), 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, MainFilePath,
926 Index, MaxLimitFiles);
927 if (!AffectedFiles)
928 return AffectedFiles.takeError();
930 for (auto &FileAndOccurrences : *AffectedFiles) {
931 llvm::StringRef FilePath = FileAndOccurrences.first();
932
933 auto ExpBuffer = FS.getBufferForFile(FilePath);
934 if (!ExpBuffer) {
935 elog("Fail to read file content: Fail to open file {0}: {1}", FilePath,
936 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>(&RenameDecl)) {
943 RenameIdentifier = MD->getSelector().getNameForSlot(0).str();
944 if (MD->getSelector().getNumArgs() > 1)
945 Selector = MD->getSelector();
946 }
947 NewName.split(NewNames, ":");
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("Index results don't match the content of file {0} "
959 "(the index may be stale)",
960 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(IndexedRest.front().start,
1002 LexedRest.front().range().start)) {
1003 PartialMatch.push_back(LexedIndex);
1004 findNearMiss(PartialMatch, IndexedRest.drop_front(), LexedRest.drop_front(),
1005 LexedIndex + 1, Fuel, MatchedCB);
1006 PartialMatch.pop_back();
1007 }
1008 findNearMiss(PartialMatch, IndexedRest, LexedRest.drop_front(),
1009 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(SM.getMainFileID());
1039 // Try to find the tokens adjacent to the cursor position.
1040 auto Loc = sourceLocationInMainFile(SM, RInputs.Pos);
1041 if (!Loc)
1042 return Loc.takeError();
1043 const syntax::Token *IdentifierToken =
1044 spelledIdentifierTouching(*Loc, AST.getTokens());
1045
1046 // Renames should only triggered on identifiers.
1047 if (!IdentifierToken)
1048 return makeError(ReasonToReject::NoSymbolFound);
1049 Range CurrentIdentifier = halfOpenToRange(
1050 SM, CharSourceRange::getCharRange(IdentifierToken->location(),
1051 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(*IdentifierToken, AST.getPreprocessor()))
1055 return makeError(ReasonToReject::UnsupportedSymbol);
1056
1057 auto DeclsUnderCursor = locateDeclAt(AST, IdentifierToken->location());
1058 filterRenameTargets(DeclsUnderCursor);
1059 if (DeclsUnderCursor.empty())
1060 return makeError(ReasonToReject::NoSymbolFound);
1061 if (DeclsUnderCursor.size() > 1)
1062 return makeError(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(1, RenameDecl.getDeclKindName());
1068
1069 std::string Placeholder = getName(RenameDecl);
1070 auto Invalid = checkName(RenameDecl, RInputs.NewName, Placeholder);
1071 if (Invalid)
1072 return std::move(Invalid);
1073
1074 auto Reject =
1075 renameable(RenameDecl, RInputs.MainFilePath, RInputs.Index, Opts);
1076 if (Reject)
1077 return makeError(*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, RInputs.NewName);
1089 if (!MainFileRenameEdit)
1090 return MainFileRenameEdit.takeError();
1091
1092 llvm::DenseSet<Range> RenamedRanges;
1093 if (!isa<ObjCMethodDecl>(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 RenamedRanges.insert(CurrentIdentifier);
1098 }
1099
1100 // Check the rename-triggering location is actually being renamed.
1101 // This is a robustness check to avoid surprising rename results -- if the
1102 // the triggering location is not actually the name of the node we identified
1103 // (e.g. for broken code), then rename is likely not what users expect, so we
1104 // reject this kind of rename.
1105 for (const auto &Range : RenamedRanges) {
1106 auto StartOffset = positionToOffset(MainFileCode, Range.start);
1107 auto EndOffset = positionToOffset(MainFileCode, Range.end);
1108 if (!StartOffset)
1109 return StartOffset.takeError();
1110 if (!EndOffset)
1111 return EndOffset.takeError();
1112 if (llvm::none_of(
1113 *MainFileRenameEdit,
1114 [&StartOffset, &EndOffset](const clang::tooling::Replacement &R) {
1115 return R.getOffset() == *StartOffset &&
1116 R.getLength() == *EndOffset - *StartOffset;
1117 })) {
1118 return makeError(ReasonToReject::NoSymbolFound);
1119 }
1120 }
1121 RenameResult Result;
1122 Result.Target = CurrentIdentifier;
1123 Result.Placeholder = Placeholder;
1124 Edit MainFileEdits = Edit(MainFileCode, std::move(*MainFileRenameEdit));
1125 for (const TextEdit &TE : MainFileEdits.asTextEdits())
1126 Result.LocalChanges.push_back(TE.range);
1127
1128 // return the main file edit if this is a within-file rename or the symbol
1129 // being renamed is function local.
1130 if (RenameDecl.getParentFunctionOrMethod()) {
1131 Result.GlobalChanges = FileEdits(
1132 {std::make_pair(RInputs.MainFilePath, std::move(MainFileEdits))});
1133 return Result;
1134 }
1135
1136 // If the index is nullptr, we don't know the completeness of the result, so
1137 // we don't populate the field GlobalChanges.
1138 if (!RInputs.Index) {
1139 assert(Result.GlobalChanges.empty());
1140 return Result;
1141 }
1142
1143 auto OtherFilesEdits = renameOutsideFile(
1144 RenameDecl, RInputs.MainFilePath, RInputs.NewName, *RInputs.Index,
1145 Opts.LimitFiles == 0 ? std::numeric_limits<size_t>::max()
1146 : Opts.LimitFiles,
1147 *RInputs.FS);
1148 if (!OtherFilesEdits)
1149 return OtherFilesEdits.takeError();
1150 Result.GlobalChanges = *OtherFilesEdits;
1151 // Attach the rename edits for the main file.
1152 Result.GlobalChanges.try_emplace(RInputs.MainFilePath,
1153 std::move(MainFileEdits));
1154 return Result;
1155}
1156
1157llvm::Expected<Edit> buildRenameEdit(llvm::StringRef AbsFilePath,
1158 llvm::StringRef InitialCode,
1159 std::vector<SymbolRange> Occurrences,
1160 llvm::ArrayRef<llvm::StringRef> NewNames) {
1161 trace::Span Tracer("BuildRenameEdit");
1162 SPAN_ATTACH(Tracer, "file_path", AbsFilePath);
1163 SPAN_ATTACH(Tracer, "rename_occurrences",
1164 static_cast<int64_t>(Occurrences.size()));
1165
1166 assert(llvm::is_sorted(Occurrences));
1167 assert(std::unique(Occurrences.begin(), Occurrences.end()) ==
1168 Occurrences.end() &&
1169 "Occurrences must be unique");
1170
1171 // These two always correspond to the same position.
1172 Position LastPos{0, 0};
1173 size_t LastOffset = 0;
1174
1175 auto Offset = [&](const Position &P) -> llvm::Expected<size_t> {
1176 assert(LastPos <= P && "malformed input");
1177 Position Shifted = {
1178 P.line - LastPos.line,
1179 P.line > LastPos.line ? P.character : P.character - LastPos.character};
1180 auto ShiftedOffset =
1181 positionToOffset(InitialCode.substr(LastOffset), Shifted);
1182 if (!ShiftedOffset)
1183 return error("fail to convert the position {0} to offset ({1})", P,
1184 ShiftedOffset.takeError());
1185 LastPos = P;
1186 LastOffset += *ShiftedOffset;
1187 return LastOffset;
1188 };
1189
1190 struct OccurrenceOffset {
1191 size_t Start;
1192 size_t End;
1193 llvm::StringRef NewName;
1194
1195 OccurrenceOffset(size_t Start, size_t End, llvm::StringRef NewName)
1196 : Start(Start), End(End), NewName(NewName) {}
1197 };
1198
1199 std::vector<OccurrenceOffset> OccurrencesOffsets;
1200 for (const auto &SR : Occurrences) {
1201 for (auto [Range, NewName] : llvm::zip(SR.Ranges, NewNames)) {
1202 auto StartOffset = Offset(Range.start);
1203 if (!StartOffset)
1204 return StartOffset.takeError();
1205 auto EndOffset = Offset(Range.end);
1206 if (!EndOffset)
1207 return EndOffset.takeError();
1208 // Nothing to do if the token/name hasn't changed.
1209 auto CurName =
1210 InitialCode.substr(*StartOffset, *EndOffset - *StartOffset);
1211 if (CurName == NewName)
1212 continue;
1213 OccurrencesOffsets.emplace_back(*StartOffset, *EndOffset, NewName);
1214 }
1215 }
1216
1217 tooling::Replacements RenameEdit;
1218 for (const auto &R : OccurrencesOffsets) {
1219 auto ByteLength = R.End - R.Start;
1220 if (auto Err = RenameEdit.add(
1221 tooling::Replacement(AbsFilePath, R.Start, ByteLength, R.NewName)))
1222 return std::move(Err);
1223 }
1224 return Edit(InitialCode, std::move(RenameEdit));
1225}
1226
1227// Details:
1228// - lex the draft code to get all rename candidates, this yields a superset
1229// of candidates.
1230// - apply range patching heuristics to generate "authoritative" occurrences,
1231// cases we consider:
1232// (a) index returns a subset of candidates, we use the indexed results.
1233// - fully equal, we are sure the index is up-to-date
1234// - proper subset, index is correct in most cases? there may be false
1235// positives (e.g. candidates got appended), but rename is still safe
1236// (b) index returns non-candidate results, we attempt to map the indexed
1237// ranges onto candidates in a plausible way (e.g. guess that lines
1238// were inserted). If such a "near miss" is found, the rename is still
1239// possible
1240std::optional<std::vector<SymbolRange>>
1241adjustRenameRanges(llvm::StringRef DraftCode, llvm::StringRef Identifier,
1242 std::vector<Range> Indexed, const LangOptions &LangOpts,
1243 std::optional<Selector> Selector) {
1244 trace::Span Tracer("AdjustRenameRanges");
1245 assert(!Indexed.empty());
1246 assert(llvm::is_sorted(Indexed));
1247 std::vector<SymbolRange> Lexed =
1248 collectRenameIdentifierRanges(Identifier, DraftCode, LangOpts, Selector);
1249 llvm::sort(Lexed);
1250 return getMappedRanges(Indexed, Lexed);
1251}
1252
1253std::optional<std::vector<SymbolRange>>
1254getMappedRanges(ArrayRef<Range> Indexed, ArrayRef<SymbolRange> Lexed) {
1255 trace::Span Tracer("GetMappedRanges");
1256 assert(!Indexed.empty());
1257 assert(llvm::is_sorted(Indexed));
1258 assert(llvm::is_sorted(Lexed));
1259
1260 if (Indexed.size() > Lexed.size()) {
1261 vlog("The number of lexed occurrences is less than indexed occurrences");
1263 Tracer, "error",
1264 "The number of lexed occurrences is less than indexed occurrences");
1265 return std::nullopt;
1266 }
1267 // Fast check for the special subset case.
1268 if (std::includes(Indexed.begin(), Indexed.end(), Lexed.begin(), Lexed.end()))
1269 return Lexed.vec();
1270
1271 std::vector<size_t> Best;
1272 size_t BestCost = std::numeric_limits<size_t>::max();
1273 bool HasMultiple = false;
1274 std::vector<size_t> ResultStorage;
1275 int Fuel = 10000;
1276 findNearMiss(ResultStorage, Indexed, Lexed, 0, Fuel,
1277 [&](const std::vector<size_t> &Matched) {
1278 size_t MCost =
1279 renameRangeAdjustmentCost(Indexed, Lexed, Matched);
1280 if (MCost < BestCost) {
1281 BestCost = MCost;
1282 Best = std::move(Matched);
1283 HasMultiple = false; // reset
1284 return;
1285 }
1286 if (MCost == BestCost)
1287 HasMultiple = true;
1288 });
1289 if (HasMultiple) {
1290 vlog("The best near miss is not unique.");
1291 SPAN_ATTACH(Tracer, "error", "The best near miss is not unique");
1292 return std::nullopt;
1293 }
1294 if (Best.empty()) {
1295 vlog("Didn't find a near miss.");
1296 SPAN_ATTACH(Tracer, "error", "Didn't find a near miss");
1297 return std::nullopt;
1298 }
1299 std::vector<SymbolRange> Mapped;
1300 for (auto I : Best)
1301 Mapped.push_back(Lexed[I]);
1302 SPAN_ATTACH(Tracer, "mapped_ranges", static_cast<int64_t>(Mapped.size()));
1303 return Mapped;
1304}
1305
1306// The cost is the sum of the implied edit sizes between successive diffs, only
1307// simple edits are considered:
1308// - insert/remove a line (change line offset)
1309// - insert/remove a character on an existing line (change column offset)
1310//
1311// Example I, total result is 1 + 1 = 2.
1312// diff[0]: line + 1 <- insert a line before edit 0.
1313// diff[1]: line + 1
1314// diff[2]: line + 1
1315// diff[3]: line + 2 <- insert a line before edits 2 and 3.
1316//
1317// Example II, total result is 1 + 1 + 1 = 3.
1318// diff[0]: line + 1 <- insert a line before edit 0.
1319// diff[1]: column + 1 <- remove a line between edits 0 and 1, and insert a
1320// character on edit 1.
1321size_t renameRangeAdjustmentCost(ArrayRef<Range> Indexed,
1322 ArrayRef<SymbolRange> Lexed,
1323 ArrayRef<size_t> MappedIndex) {
1324 assert(Indexed.size() == MappedIndex.size());
1325 assert(llvm::is_sorted(Indexed));
1326 assert(llvm::is_sorted(Lexed));
1327
1328 int LastLine = -1;
1329 int LastDLine = 0, LastDColumn = 0;
1330 int Cost = 0;
1331 for (size_t I = 0; I < Indexed.size(); ++I) {
1332 int DLine =
1333 Indexed[I].start.line - Lexed[MappedIndex[I]].range().start.line;
1334 int DColumn = Indexed[I].start.character -
1335 Lexed[MappedIndex[I]].range().start.character;
1336 int Line = Indexed[I].start.line;
1337 if (Line != LastLine)
1338 LastDColumn = 0; // column offsets don't carry cross lines.
1339 Cost += abs(DLine - LastDLine) + abs(DColumn - LastDColumn);
1340 std::tie(LastLine, LastDLine, LastDColumn) = std::tie(Line, DLine, DColumn);
1341 }
1342 return Cost;
1343}
1344
1345} // namespace clangd
1346} // namespace clang
const FunctionDecl * Decl
BindArgumentKind Kind
llvm::SmallString< 256U > Name
size_t Offset
std::vector< CodeCompletionResult > Results
const FunctionDecl * EnclosingFunction
const Node * Parent
std::string Code
const Criteria C
SmallVector< Detail, DefaultLimit > Details
ExpectedMatch Candidate
std::string MainFile
CharSourceRange Range
SourceRange for the file name.
SourceLocation Loc
unsigned int LastLine
::clang::DynTypedNode Node
Kind K
Definition: Rename.cpp:474
std::unique_ptr< CompilerInvocation > CI
#define SPAN_ATTACH(S, Name, Expr)
Attach a key-value pair to a Span event.
Definition: Trace.h:164
Stores and provides access to parsed AST.
Definition: ParsedAST.h:46
static SelectionTree createRight(ASTContext &AST, const syntax::TokenBuffer &Tokens, unsigned Begin, unsigned End)
Definition: Selection.cpp:1067
static bool shouldCollectSymbol(const NamedDecl &ND, const ASTContext &ASTCtx, const Options &Opts, bool IsMainFileSymbol)
Returns true is ND should be collected.
static llvm::Expected< std::string > resolve(const URI &U, llvm::StringRef HintPath="")
Resolves the absolute path of U.
Definition: URI.cpp:244
Records an event whose duration is the lifetime of the Span object.
Definition: Trace.h:143
Range toRange(llvm::SMRange R, const llvm::SourceMgr &SM)
Definition: ConfigTesting.h:82
SymbolID getSymbolID(const Decl *D)
Gets the symbol ID for a declaration. Returned SymbolID might be null.
Definition: AST.cpp:331
Range halfOpenToRange(const SourceManager &SM, CharSourceRange R)
Definition: SourceCode.cpp:472
std::string Path
A typedef to represent a file path.
Definition: Path.h:26
bool isInsideMainFile(SourceLocation Loc, const SourceManager &SM)
Returns true iff Loc is inside the main file.
Definition: SourceCode.cpp:423
llvm::StringMap< Edit > FileEdits
A mapping from absolute file path (the one used for accessing the underlying VFS) to edits.
Definition: SourceCode.h:209
llvm::Expected< Edit > buildRenameEdit(llvm::StringRef AbsFilePath, llvm::StringRef InitialCode, std::vector< SymbolRange > Occurrences, llvm::ArrayRef< llvm::StringRef > NewNames)
Generates rename edits that replaces all given occurrences with the NewName.
Definition: Rename.cpp:1157
void vlog(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:72
static const char * toString(OffsetEncoding OE)
Definition: Protocol.cpp:1553
llvm::Expected< RenameResult > rename(const RenameInputs &RInputs)
Renames all occurrences of the symbol.
Definition: Rename.cpp:1031
void findExplicitReferences(const Stmt *S, llvm::function_ref< void(ReferenceLoc)> Out, const HeuristicResolver *Resolver)
Recursively traverse S and report all references explicitly written in the code.
llvm::Error error(std::error_code EC, const char *Fmt, Ts &&... Vals)
Definition: Logger.h:79
bool operator==(const Inclusion &LHS, const Inclusion &RHS)
Definition: Headers.cpp:331
llvm::SmallVector< const NamedDecl *, 1 > targetDecl(const DynTypedNode &N, DeclRelationSet Mask, const HeuristicResolver *Resolver)
targetDecl() finds the declaration referred to by an AST node.
Definition: FindTarget.cpp:582
Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc)
Turn a SourceLocation into a [line, column] pair.
Definition: SourceCode.cpp:214
std::optional< DefinedMacro > locateMacroAt(const syntax::Token &SpelledTok, Preprocessor &PP)
Gets the macro referenced by SpelledTok.
Definition: SourceCode.cpp:999
bool operator!=(const SymbolRange &LHS, const SymbolRange &RHS)
Definition: Rename.cpp:1024
std::optional< std::vector< SymbolRange > > adjustRenameRanges(llvm::StringRef DraftCode, llvm::StringRef Identifier, std::vector< Range > Indexed, const LangOptions &LangOpts, std::optional< Selector > Selector)
Adjusts indexed occurrences to match the current state of the file.
Definition: Rename.cpp:1241
llvm::Expected< size_t > positionToOffset(llvm::StringRef Code, Position P, bool AllowColumnsBeyondLineLength)
Turn a [line, column] pair into an offset in Code.
Definition: SourceCode.cpp:173
bool operator<(const Ref &L, const Ref &R)
Definition: Ref.h:95
std::vector< Range > collectIdentifierRanges(llvm::StringRef Identifier, llvm::StringRef Content, const LangOptions &LangOpts)
Collects all ranges of the given identifier in the source code.
Definition: SourceCode.cpp:646
size_t renameRangeAdjustmentCost(ArrayRef< Range > Indexed, ArrayRef< SymbolRange > Lexed, ArrayRef< size_t > MappedIndex)
Evaluates how good the mapped result is.
Definition: Rename.cpp:1321
llvm::Expected< SourceLocation > sourceLocationInMainFile(const SourceManager &SM, Position P)
Return the file location, corresponding to P.
Definition: SourceCode.cpp:462
@ Parameter
An inlay hint that is for a parameter.
bool isKeyword(llvm::StringRef NewName, const LangOptions &LangOpts)
Return true if the TokenName is in the list of reversed keywords of the language.
Definition: SourceCode.cpp:659
void elog(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:61
bool isProtoFile(SourceLocation Loc, const SourceManager &SM)
Returns true if the given location is in a generated protobuf file.
@ TemplatePattern
This is the pattern the template specialization was instantiated from.
@ Alias
This declaration is an alias that was referred to.
bool isHeaderFile(llvm::StringRef FileName, std::optional< LangOptions > LangOpts)
Infers whether this is a header from the FileName and LangOpts (if presents).
std::optional< std::vector< SymbolRange > > getMappedRanges(ArrayRef< Range > Indexed, ArrayRef< SymbolRange > Lexed)
Calculates the lexed occurrences that the given indexed occurrences map to.
Definition: Rename.cpp:1254
constexpr llvm::StringLiteral Message
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
A set of edits generated for a single file.
Definition: SourceCode.h:189
std::vector< TextEdit > asTextEdits() const
Represents Replacements as TextEdits that are available for use in LSP.
int line
Line position in a document (zero-based).
Definition: Protocol.h:158
Position start
The range's start position.
Definition: Protocol.h:187
Position end
The range's end position.
Definition: Protocol.h:190
llvm::StringRef NewName
Definition: Rename.h:40
const SymbolIndex * Index
Definition: Rename.h:50
llvm::StringRef MainFilePath
Definition: Rename.h:43
llvm::IntrusiveRefCntPtr< llvm::vfs::FileSystem > FS
Definition: Rename.h:48
RenameOptions Opts
Definition: Rename.h:52
Represents a symbol range where the symbol can potentially have multiple tokens.
Definition: Rename.h:69
std::vector< Range > Ranges
Ranges for the tokens that make up the symbol's name.
Definition: Rename.h:73
Range range() const
Returns the first range.
Definition: Rename.cpp:1019
Represents measurements of clangd events, e.g.
Definition: Trace.h:38
@ Counter
An aggregate number whose rate of change over time is meaningful.
Definition: Trace.h:46
void record(double Value, llvm::StringRef Label="") const
Records a measurement for this metric to active tracer.
Definition: Trace.cpp:329