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