• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- Rename.cpp - Symbol-rename refactorings -----------------*- C++-*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "refactor/Rename.h"
10 #include "AST.h"
11 #include "FindTarget.h"
12 #include "ParsedAST.h"
13 #include "Selection.h"
14 #include "SourceCode.h"
15 #include "index/SymbolCollector.h"
16 #include "support/Logger.h"
17 #include "support/Trace.h"
18 #include "clang/AST/DeclCXX.h"
19 #include "clang/AST/DeclTemplate.h"
20 #include "clang/Basic/SourceLocation.h"
21 #include "clang/Tooling/Syntax/Tokens.h"
22 #include "llvm/ADT/None.h"
23 #include "llvm/ADT/STLExtras.h"
24 #include "llvm/Support/Casting.h"
25 #include "llvm/Support/Error.h"
26 #include "llvm/Support/FormatVariadic.h"
27 #include <algorithm>
28 
29 namespace clang {
30 namespace clangd {
31 namespace {
32 
filePath(const SymbolLocation & Loc,llvm::StringRef HintFilePath)33 llvm::Optional<std::string> filePath(const SymbolLocation &Loc,
34                                      llvm::StringRef HintFilePath) {
35   if (!Loc)
36     return None;
37   auto Path = URI::resolve(Loc.FileURI, HintFilePath);
38   if (!Path) {
39     elog("Could not resolve URI {0}: {1}", Loc.FileURI, Path.takeError());
40     return None;
41   }
42 
43   return *Path;
44 }
45 
46 // Returns true if the given location is expanded from any macro body.
isInMacroBody(const SourceManager & SM,SourceLocation Loc)47 bool isInMacroBody(const SourceManager &SM, SourceLocation Loc) {
48   while (Loc.isMacroID()) {
49     if (SM.isMacroBodyExpansion(Loc))
50       return true;
51     Loc = SM.getImmediateMacroCallerLoc(Loc);
52   }
53 
54   return false;
55 }
56 
57 // Query the index to find some other files where the Decl is referenced.
getOtherRefFile(const Decl & D,StringRef MainFile,const SymbolIndex & Index)58 llvm::Optional<std::string> getOtherRefFile(const Decl &D, StringRef MainFile,
59                                             const SymbolIndex &Index) {
60   RefsRequest Req;
61   // We limit the number of results, this is a correctness/performance
62   // tradeoff. We expect the number of symbol references in the current file
63   // is smaller than the limit.
64   Req.Limit = 100;
65   Req.IDs.insert(getSymbolID(&D));
66   llvm::Optional<std::string> OtherFile;
67   Index.refs(Req, [&](const Ref &R) {
68     if (OtherFile)
69       return;
70     if (auto RefFilePath = filePath(R.Location, /*HintFilePath=*/MainFile)) {
71       if (*RefFilePath != MainFile)
72         OtherFile = *RefFilePath;
73     }
74   });
75   return OtherFile;
76 }
77 
78 // Canonical declarations help simplify the process of renaming. Examples:
79 // - Template's canonical decl is the templated declaration (i.e.
80 //   ClassTemplateDecl is canonicalized to its child CXXRecordDecl,
81 //   FunctionTemplateDecl - to child FunctionDecl)
82 // - Given a constructor/destructor, canonical declaration is the parent
83 //   CXXRecordDecl because we want to rename both type name and its ctor/dtor.
84 // - All specializations are canonicalized to the primary template. For example:
85 //
86 //    template <typename T, int U>
87 //    bool Foo = true; (1)
88 //
89 //    template <typename T>
90 //    bool Foo<T, 0> = true; (2)
91 //
92 //    template <>
93 //    bool Foo<int, 0> = true; (3)
94 //
95 // Here, both partial (2) and full (3) specializations are canonicalized to (1)
96 // which ensures all three of them are renamed.
canonicalRenameDecl(const NamedDecl * D)97 const NamedDecl *canonicalRenameDecl(const NamedDecl *D) {
98   if (const auto *VarTemplate = dyn_cast<VarTemplateSpecializationDecl>(D))
99     return canonicalRenameDecl(
100         VarTemplate->getSpecializedTemplate()->getTemplatedDecl());
101   if (const auto *Template = dyn_cast<TemplateDecl>(D))
102     if (const NamedDecl *TemplatedDecl = Template->getTemplatedDecl())
103       return canonicalRenameDecl(TemplatedDecl);
104   if (const auto *ClassTemplateSpecialization =
105           dyn_cast<ClassTemplateSpecializationDecl>(D))
106     return canonicalRenameDecl(
107         ClassTemplateSpecialization->getSpecializedTemplate()
108             ->getTemplatedDecl());
109   if (const auto *Method = dyn_cast<CXXMethodDecl>(D)) {
110     if (Method->getDeclKind() == Decl::Kind::CXXConstructor ||
111         Method->getDeclKind() == Decl::Kind::CXXDestructor)
112       return canonicalRenameDecl(Method->getParent());
113     if (const FunctionDecl *InstantiatedMethod =
114             Method->getInstantiatedFromMemberFunction())
115       Method = cast<CXXMethodDecl>(InstantiatedMethod);
116     // FIXME(kirillbobyrev): For virtual methods with
117     // size_overridden_methods() > 1, this will not rename all functions it
118     // overrides, because this code assumes there is a single canonical
119     // declaration.
120     while (Method->isVirtual() && Method->size_overridden_methods())
121       Method = *Method->overridden_methods().begin();
122     return dyn_cast<NamedDecl>(Method->getCanonicalDecl());
123   }
124   if (const auto *Function = dyn_cast<FunctionDecl>(D))
125     if (const FunctionTemplateDecl *Template = Function->getPrimaryTemplate())
126       return canonicalRenameDecl(Template);
127   if (const auto *Field = dyn_cast<FieldDecl>(D)) {
128     // This is a hacky way to do something like
129     // CXXMethodDecl::getInstantiatedFromMemberFunction for the field because
130     // Clang AST does not store relevant information about the field that is
131     // instantiated.
132     const auto *FieldParent =
133         dyn_cast_or_null<CXXRecordDecl>(Field->getParent());
134     if (!FieldParent)
135       return Field->getCanonicalDecl();
136     FieldParent = FieldParent->getTemplateInstantiationPattern();
137     // Field is not instantiation.
138     if (!FieldParent || Field->getParent() == FieldParent)
139       return Field->getCanonicalDecl();
140     for (const FieldDecl *Candidate : FieldParent->fields())
141       if (Field->getDeclName() == Candidate->getDeclName())
142         return Candidate->getCanonicalDecl();
143     elog("FieldParent should have field with the same name as Field.");
144   }
145   if (const auto *VD = dyn_cast<VarDecl>(D)) {
146     if (const VarDecl *OriginalVD = VD->getInstantiatedFromStaticDataMember())
147       VD = OriginalVD;
148     return VD->getCanonicalDecl();
149   }
150   return dyn_cast<NamedDecl>(D->getCanonicalDecl());
151 }
152 
locateDeclAt(ParsedAST & AST,SourceLocation TokenStartLoc)153 llvm::DenseSet<const NamedDecl *> locateDeclAt(ParsedAST &AST,
154                                                SourceLocation TokenStartLoc) {
155   unsigned Offset =
156       AST.getSourceManager().getDecomposedSpellingLoc(TokenStartLoc).second;
157 
158   SelectionTree Selection = SelectionTree::createRight(
159       AST.getASTContext(), AST.getTokens(), Offset, Offset);
160   const SelectionTree::Node *SelectedNode = Selection.commonAncestor();
161   if (!SelectedNode)
162     return {};
163 
164   llvm::DenseSet<const NamedDecl *> Result;
165   for (const NamedDecl *D :
166        targetDecl(SelectedNode->ASTNode,
167                   DeclRelation::Alias | DeclRelation::TemplatePattern)) {
168     Result.insert(canonicalRenameDecl(D));
169   }
170   return Result;
171 }
172 
173 // By default, we exclude C++ standard symbols and protobuf symbols as rename
174 // these symbols would change system/generated files which are unlikely to be
175 // modified.
isExcluded(const NamedDecl & RenameDecl)176 bool isExcluded(const NamedDecl &RenameDecl) {
177   if (isProtoFile(RenameDecl.getLocation(),
178                   RenameDecl.getASTContext().getSourceManager()))
179     return true;
180   static const auto *StdSymbols = new llvm::DenseSet<llvm::StringRef>({
181 #define SYMBOL(Name, NameSpace, Header) {#NameSpace #Name},
182 #include "StdSymbolMap.inc"
183 #undef SYMBOL
184   });
185   return StdSymbols->count(printQualifiedName(RenameDecl));
186 }
187 
188 enum class ReasonToReject {
189   NoSymbolFound,
190   NoIndexProvided,
191   NonIndexable,
192   UsedOutsideFile, // for within-file rename only.
193   UnsupportedSymbol,
194   AmbiguousSymbol,
195 
196   // name validation.
197   RenameToKeywords,
198   SameName,
199 };
200 
renameable(const NamedDecl & RenameDecl,StringRef MainFilePath,const SymbolIndex * Index,bool CrossFile)201 llvm::Optional<ReasonToReject> renameable(const NamedDecl &RenameDecl,
202                                           StringRef MainFilePath,
203                                           const SymbolIndex *Index,
204                                           bool CrossFile) {
205   trace::Span Tracer("Renameable");
206   // Filter out symbols that are unsupported in both rename modes.
207   if (llvm::isa<NamespaceDecl>(&RenameDecl))
208     return ReasonToReject::UnsupportedSymbol;
209   if (const auto *FD = llvm::dyn_cast<FunctionDecl>(&RenameDecl)) {
210     if (FD->isOverloadedOperator())
211       return ReasonToReject::UnsupportedSymbol;
212   }
213   // function-local symbols is safe to rename.
214   if (RenameDecl.getParentFunctionOrMethod())
215     return None;
216 
217   if (isExcluded(RenameDecl))
218     return ReasonToReject::UnsupportedSymbol;
219 
220   // Check whether the symbol being rename is indexable.
221   auto &ASTCtx = RenameDecl.getASTContext();
222   bool MainFileIsHeader = isHeaderFile(MainFilePath, ASTCtx.getLangOpts());
223   bool DeclaredInMainFile =
224       isInsideMainFile(RenameDecl.getBeginLoc(), ASTCtx.getSourceManager());
225   bool IsMainFileOnly = true;
226   if (MainFileIsHeader)
227     // main file is a header, the symbol can't be main file only.
228     IsMainFileOnly = false;
229   else if (!DeclaredInMainFile)
230     IsMainFileOnly = false;
231   // If the symbol is not indexable, we disallow rename.
232   if (!SymbolCollector::shouldCollectSymbol(
233           RenameDecl, RenameDecl.getASTContext(), SymbolCollector::Options(),
234           IsMainFileOnly))
235     return ReasonToReject::NonIndexable;
236 
237   if (!CrossFile) {
238     if (!DeclaredInMainFile)
239       // We are sure the symbol is used externally, bail out early.
240       return ReasonToReject::UsedOutsideFile;
241 
242     // If the symbol is declared in the main file (which is not a header), we
243     // rename it.
244     if (!MainFileIsHeader)
245       return None;
246 
247     if (!Index)
248       return ReasonToReject::NoIndexProvided;
249 
250     auto OtherFile = getOtherRefFile(RenameDecl, MainFilePath, *Index);
251     // If the symbol is indexable and has no refs from other files in the index,
252     // we rename it.
253     if (!OtherFile)
254       return None;
255     // If the symbol is indexable and has refs from other files in the index,
256     // we disallow rename.
257     return ReasonToReject::UsedOutsideFile;
258   }
259 
260   assert(CrossFile);
261 
262   // FIXME: Renaming virtual methods requires to rename all overridens in
263   // subclasses, our index doesn't have this information.
264   // Note: Within-file rename does support this through the AST.
265   if (const auto *S = llvm::dyn_cast<CXXMethodDecl>(&RenameDecl)) {
266     if (S->isVirtual())
267       return ReasonToReject::UnsupportedSymbol;
268   }
269   return None;
270 }
271 
makeError(ReasonToReject Reason)272 llvm::Error makeError(ReasonToReject Reason) {
273   auto Message = [](ReasonToReject Reason) {
274     switch (Reason) {
275     case ReasonToReject::NoSymbolFound:
276       return "there is no symbol at the given location";
277     case ReasonToReject::NoIndexProvided:
278       return "no index provided";
279     case ReasonToReject::UsedOutsideFile:
280       return "the symbol is used outside main file";
281     case ReasonToReject::NonIndexable:
282       return "symbol may be used in other files (not eligible for indexing)";
283     case ReasonToReject::UnsupportedSymbol:
284       return "symbol is not a supported kind (e.g. namespace, macro)";
285     case ReasonToReject::AmbiguousSymbol:
286       return "there are multiple symbols at the given location";
287     case ReasonToReject::RenameToKeywords:
288       return "the chosen name is a keyword";
289     case ReasonToReject::SameName:
290       return "new name is the same as the old name";
291     }
292     llvm_unreachable("unhandled reason kind");
293   };
294   return error("Cannot rename symbol: {0}", Message(Reason));
295 }
296 
297 // Return all rename occurrences in the main file.
findOccurrencesWithinFile(ParsedAST & AST,const NamedDecl & ND)298 std::vector<SourceLocation> findOccurrencesWithinFile(ParsedAST &AST,
299                                                       const NamedDecl &ND) {
300   trace::Span Tracer("FindOccurrencesWithinFile");
301   assert(canonicalRenameDecl(&ND) == &ND &&
302          "ND should be already canonicalized.");
303 
304   std::vector<SourceLocation> Results;
305   for (Decl *TopLevelDecl : AST.getLocalTopLevelDecls()) {
306     findExplicitReferences(TopLevelDecl, [&](ReferenceLoc Ref) {
307       if (Ref.Targets.empty())
308         return;
309       for (const auto *Target : Ref.Targets) {
310         if (canonicalRenameDecl(Target) == &ND) {
311           Results.push_back(Ref.NameLoc);
312           return;
313         }
314       }
315     });
316   }
317 
318   return Results;
319 }
320 
321 // Lookup the declarations (if any) with the given Name in the context of
322 // RenameDecl.
lookupSiblingWithName(const ASTContext & Ctx,const NamedDecl & RenamedDecl,llvm::StringRef Name)323 const NamedDecl *lookupSiblingWithName(const ASTContext &Ctx,
324                                        const NamedDecl &RenamedDecl,
325                                        llvm::StringRef Name) {
326   trace::Span Tracer("LookupSiblingWithName");
327   const auto &II = Ctx.Idents.get(Name);
328   DeclarationName LookupName(&II);
329   DeclContextLookupResult LookupResult;
330   const auto *DC = RenamedDecl.getDeclContext();
331   while (DC && DC->isTransparentContext())
332     DC = DC->getParent();
333   switch (DC->getDeclKind()) {
334   // The enclosing DeclContext may not be the enclosing scope, it might have
335   // false positives and negatives, so we only choose "confident" DeclContexts
336   // that don't have any subscopes that are neither DeclContexts nor
337   // transparent.
338   //
339   // Notably, FunctionDecl is excluded -- because local variables are not scoped
340   // to the function, but rather to the CompoundStmt that is its body. Lookup
341   // will not find function-local variables.
342   case Decl::TranslationUnit:
343   case Decl::Namespace:
344   case Decl::Record:
345   case Decl::Enum:
346   case Decl::CXXRecord:
347     LookupResult = DC->lookup(LookupName);
348     break;
349   default:
350     break;
351   }
352   // Lookup may contain the RenameDecl itself, exclude it.
353   for (const auto *D : LookupResult)
354     if (D->getCanonicalDecl() != RenamedDecl.getCanonicalDecl())
355       return D;
356   return nullptr;
357 }
358 
359 struct InvalidName {
360   enum Kind {
361     Keywords,
362     Conflict,
363   };
364   Kind K;
365   std::string Details;
366 };
toString(InvalidName::Kind K)367 std::string toString(InvalidName::Kind K) {
368   switch (K) {
369   case InvalidName::Keywords:
370     return "Keywords";
371   case InvalidName::Conflict:
372     return "Conflict";
373   }
374   llvm_unreachable("unhandled InvalidName kind");
375 }
376 
makeError(InvalidName Reason)377 llvm::Error makeError(InvalidName Reason) {
378   auto Message = [](InvalidName Reason) {
379     switch (Reason.K) {
380     case InvalidName::Keywords:
381       return llvm::formatv("the chosen name \"{0}\" is a keyword",
382                            Reason.Details);
383     case InvalidName::Conflict:
384       return llvm::formatv("conflict with the symbol in {0}", Reason.Details);
385     }
386     llvm_unreachable("unhandled InvalidName kind");
387   };
388   return error("invalid name: {0}", Message(Reason));
389 }
390 
391 // Check if we can rename the given RenameDecl into NewName.
392 // Return details if the rename would produce a conflict.
checkName(const NamedDecl & RenameDecl,llvm::StringRef NewName)393 llvm::Optional<InvalidName> checkName(const NamedDecl &RenameDecl,
394                                       llvm::StringRef NewName) {
395   trace::Span Tracer("CheckName");
396   static constexpr trace::Metric InvalidNameMetric(
397       "rename_name_invalid", trace::Metric::Counter, "invalid_kind");
398   auto &ASTCtx = RenameDecl.getASTContext();
399   llvm::Optional<InvalidName> Result;
400   if (isKeyword(NewName, ASTCtx.getLangOpts()))
401     Result = InvalidName{InvalidName::Keywords, NewName.str()};
402   else {
403     // Name conflict detection.
404     // Function conflicts are subtle (overloading), so ignore them.
405     if (RenameDecl.getKind() != Decl::Function) {
406       if (auto *Conflict = lookupSiblingWithName(ASTCtx, RenameDecl, NewName))
407         Result = InvalidName{
408             InvalidName::Conflict,
409             Conflict->getLocation().printToString(ASTCtx.getSourceManager())};
410     }
411   }
412   if (Result)
413     InvalidNameMetric.record(1, toString(Result->K));
414   return Result;
415 }
416 
417 // AST-based rename, it renames all occurrences in the main file.
418 llvm::Expected<tooling::Replacements>
renameWithinFile(ParsedAST & AST,const NamedDecl & RenameDecl,llvm::StringRef NewName)419 renameWithinFile(ParsedAST &AST, const NamedDecl &RenameDecl,
420                  llvm::StringRef NewName) {
421   trace::Span Tracer("RenameWithinFile");
422   const SourceManager &SM = AST.getSourceManager();
423 
424   tooling::Replacements FilteredChanges;
425   for (SourceLocation Loc : findOccurrencesWithinFile(AST, RenameDecl)) {
426     SourceLocation RenameLoc = Loc;
427     // We don't rename in any macro bodies, but we allow rename the symbol
428     // spelled in a top-level macro argument in the main file.
429     if (RenameLoc.isMacroID()) {
430       if (isInMacroBody(SM, RenameLoc))
431         continue;
432       RenameLoc = SM.getSpellingLoc(Loc);
433     }
434     // Filter out locations not from main file.
435     // We traverse only main file decls, but locations could come from an
436     // non-preamble #include file e.g.
437     //   void test() {
438     //     int f^oo;
439     //     #include "use_foo.inc"
440     //   }
441     if (!isInsideMainFile(RenameLoc, SM))
442       continue;
443     if (auto Err = FilteredChanges.add(tooling::Replacement(
444             SM, CharSourceRange::getTokenRange(RenameLoc), NewName)))
445       return std::move(Err);
446   }
447   return FilteredChanges;
448 }
449 
toRange(const SymbolLocation & L)450 Range toRange(const SymbolLocation &L) {
451   Range R;
452   R.start.line = L.Start.line();
453   R.start.character = L.Start.column();
454   R.end.line = L.End.line();
455   R.end.character = L.End.column();
456   return R;
457 }
458 
459 // Return all rename occurrences (using the index) outside of the main file,
460 // grouped by the absolute file path.
461 llvm::Expected<llvm::StringMap<std::vector<Range>>>
findOccurrencesOutsideFile(const NamedDecl & RenameDecl,llvm::StringRef MainFile,const SymbolIndex & Index,size_t MaxLimitFiles)462 findOccurrencesOutsideFile(const NamedDecl &RenameDecl,
463                            llvm::StringRef MainFile, const SymbolIndex &Index,
464                            size_t MaxLimitFiles) {
465   trace::Span Tracer("FindOccurrencesOutsideFile");
466   RefsRequest RQuest;
467   RQuest.IDs.insert(getSymbolID(&RenameDecl));
468 
469   // Absolute file path => rename occurrences in that file.
470   llvm::StringMap<std::vector<Range>> AffectedFiles;
471   bool HasMore = Index.refs(RQuest, [&](const Ref &R) {
472     if (AffectedFiles.size() >= MaxLimitFiles)
473       return;
474     if ((R.Kind & RefKind::Spelled) == RefKind::Unknown)
475       return;
476     if (auto RefFilePath = filePath(R.Location, /*HintFilePath=*/MainFile)) {
477       if (*RefFilePath != MainFile)
478         AffectedFiles[*RefFilePath].push_back(toRange(R.Location));
479     }
480   });
481 
482   if (AffectedFiles.size() >= MaxLimitFiles)
483     return error("The number of affected files exceeds the max limit {0}",
484                  MaxLimitFiles);
485   if (HasMore)
486     return error("The symbol {0} has too many occurrences",
487                  RenameDecl.getQualifiedNameAsString());
488   // Sort and deduplicate the results, in case that index returns duplications.
489   for (auto &FileAndOccurrences : AffectedFiles) {
490     auto &Ranges = FileAndOccurrences.getValue();
491     llvm::sort(Ranges);
492     Ranges.erase(std::unique(Ranges.begin(), Ranges.end()), Ranges.end());
493 
494     SPAN_ATTACH(Tracer, FileAndOccurrences.first(),
495                 static_cast<int64_t>(Ranges.size()));
496   }
497   return AffectedFiles;
498 }
499 
500 // Index-based rename, it renames all occurrences outside of the main file.
501 //
502 // The cross-file rename is purely based on the index, as we don't want to
503 // build all ASTs for affected files, which may cause a performance hit.
504 // We choose to trade off some correctness for performance and scalability.
505 //
506 // Clangd builds a dynamic index for all opened files on top of the static
507 // index of the whole codebase. Dynamic index is up-to-date (respects dirty
508 // buffers) as long as clangd finishes processing opened files, while static
509 // index (background index) is relatively stale. We choose the dirty buffers
510 // as the file content we rename on, and fallback to file content on disk if
511 // there is no dirty buffer.
renameOutsideFile(const NamedDecl & RenameDecl,llvm::StringRef MainFilePath,llvm::StringRef NewName,const SymbolIndex & Index,size_t MaxLimitFiles,llvm::function_ref<llvm::Expected<std::string> (PathRef)> GetFileContent)512 llvm::Expected<FileEdits> renameOutsideFile(
513     const NamedDecl &RenameDecl, llvm::StringRef MainFilePath,
514     llvm::StringRef NewName, const SymbolIndex &Index, size_t MaxLimitFiles,
515     llvm::function_ref<llvm::Expected<std::string>(PathRef)> GetFileContent) {
516   trace::Span Tracer("RenameOutsideFile");
517   auto AffectedFiles = findOccurrencesOutsideFile(RenameDecl, MainFilePath,
518                                                   Index, MaxLimitFiles);
519   if (!AffectedFiles)
520     return AffectedFiles.takeError();
521   FileEdits Results;
522   for (auto &FileAndOccurrences : *AffectedFiles) {
523     llvm::StringRef FilePath = FileAndOccurrences.first();
524 
525     auto AffectedFileCode = GetFileContent(FilePath);
526     if (!AffectedFileCode) {
527       elog("Fail to read file content: {0}", AffectedFileCode.takeError());
528       continue;
529     }
530     auto RenameRanges =
531         adjustRenameRanges(*AffectedFileCode, RenameDecl.getNameAsString(),
532                            std::move(FileAndOccurrences.second),
533                            RenameDecl.getASTContext().getLangOpts());
534     if (!RenameRanges) {
535       // Our heuristics fails to adjust rename ranges to the current state of
536       // the file, it is most likely the index is stale, so we give up the
537       // entire rename.
538       return error("Index results don't match the content of file {0} "
539                    "(the index may be stale)",
540                    FilePath);
541     }
542     auto RenameEdit =
543         buildRenameEdit(FilePath, *AffectedFileCode, *RenameRanges, NewName);
544     if (!RenameEdit)
545       return error("failed to rename in file {0}: {1}", FilePath,
546                    RenameEdit.takeError());
547     if (!RenameEdit->Replacements.empty())
548       Results.insert({FilePath, std::move(*RenameEdit)});
549   }
550   return Results;
551 }
552 
553 // A simple edit is either changing line or column, but not both.
impliesSimpleEdit(const Position & LHS,const Position & RHS)554 bool impliesSimpleEdit(const Position &LHS, const Position &RHS) {
555   return LHS.line == RHS.line || LHS.character == RHS.character;
556 }
557 
558 // Performs a DFS to enumerate all possible near-miss matches.
559 // It finds the locations where the indexed occurrences are now spelled in
560 // Lexed occurrences, a near miss is defined as:
561 //   - a near miss maps all of the **name** occurrences from the index onto a
562 //     *subset* of lexed occurrences (we allow a single name refers to more
563 //     than one symbol)
564 //   - all indexed occurrences must be mapped, and Result must be distinct and
565 //     preserve order (only support detecting simple edits to ensure a
566 //     robust mapping)
567 //   - each indexed -> lexed occurrences mapping correspondence may change the
568 //     *line* or *column*, but not both (increases chance of a robust mapping)
findNearMiss(std::vector<size_t> & PartialMatch,ArrayRef<Range> IndexedRest,ArrayRef<Range> LexedRest,int LexedIndex,int & Fuel,llvm::function_ref<void (const std::vector<size_t> &)> MatchedCB)569 void findNearMiss(
570     std::vector<size_t> &PartialMatch, ArrayRef<Range> IndexedRest,
571     ArrayRef<Range> LexedRest, int LexedIndex, int &Fuel,
572     llvm::function_ref<void(const std::vector<size_t> &)> MatchedCB) {
573   if (--Fuel < 0)
574     return;
575   if (IndexedRest.size() > LexedRest.size())
576     return;
577   if (IndexedRest.empty()) {
578     MatchedCB(PartialMatch);
579     return;
580   }
581   if (impliesSimpleEdit(IndexedRest.front().start, LexedRest.front().start)) {
582     PartialMatch.push_back(LexedIndex);
583     findNearMiss(PartialMatch, IndexedRest.drop_front(), LexedRest.drop_front(),
584                  LexedIndex + 1, Fuel, MatchedCB);
585     PartialMatch.pop_back();
586   }
587   findNearMiss(PartialMatch, IndexedRest, LexedRest.drop_front(),
588                LexedIndex + 1, Fuel, MatchedCB);
589 }
590 
591 } // namespace
592 
rename(const RenameInputs & RInputs)593 llvm::Expected<RenameResult> rename(const RenameInputs &RInputs) {
594   trace::Span Tracer("Rename flow");
595   const auto &Opts = RInputs.Opts;
596   ParsedAST &AST = RInputs.AST;
597   const SourceManager &SM = AST.getSourceManager();
598   llvm::StringRef MainFileCode = SM.getBufferData(SM.getMainFileID());
599   auto GetFileContent = [&RInputs,
600                          &SM](PathRef AbsPath) -> llvm::Expected<std::string> {
601     llvm::Optional<std::string> DirtyBuffer;
602     if (RInputs.GetDirtyBuffer &&
603         (DirtyBuffer = RInputs.GetDirtyBuffer(AbsPath)))
604       return std::move(*DirtyBuffer);
605 
606     auto Content =
607         SM.getFileManager().getVirtualFileSystem().getBufferForFile(AbsPath);
608     if (!Content)
609       return error("Fail to open file {0}: {1}", AbsPath,
610                    Content.getError().message());
611     if (!*Content)
612       return error("Got no buffer for file {0}", AbsPath);
613 
614     return (*Content)->getBuffer().str();
615   };
616   // Try to find the tokens adjacent to the cursor position.
617   auto Loc = sourceLocationInMainFile(SM, RInputs.Pos);
618   if (!Loc)
619     return Loc.takeError();
620   const syntax::Token *IdentifierToken =
621       spelledIdentifierTouching(*Loc, AST.getTokens());
622 
623   // Renames should only triggered on identifiers.
624   if (!IdentifierToken)
625     return makeError(ReasonToReject::NoSymbolFound);
626   Range CurrentIdentifier = halfOpenToRange(
627       SM, CharSourceRange::getCharRange(IdentifierToken->location(),
628                                         IdentifierToken->endLocation()));
629   // FIXME: Renaming macros is not supported yet, the macro-handling code should
630   // be moved to rename tooling library.
631   if (locateMacroAt(*IdentifierToken, AST.getPreprocessor()))
632     return makeError(ReasonToReject::UnsupportedSymbol);
633 
634   auto DeclsUnderCursor = locateDeclAt(AST, IdentifierToken->location());
635   if (DeclsUnderCursor.empty())
636     return makeError(ReasonToReject::NoSymbolFound);
637   if (DeclsUnderCursor.size() > 1)
638     return makeError(ReasonToReject::AmbiguousSymbol);
639   const auto &RenameDecl = **DeclsUnderCursor.begin();
640   const auto *ID = RenameDecl.getIdentifier();
641   if (!ID)
642     return makeError(ReasonToReject::UnsupportedSymbol);
643   if (ID->getName() == RInputs.NewName)
644     return makeError(ReasonToReject::SameName);
645   auto Invalid = checkName(RenameDecl, RInputs.NewName);
646   if (Invalid)
647     return makeError(*Invalid);
648 
649   auto Reject = renameable(RenameDecl, RInputs.MainFilePath, RInputs.Index,
650                            Opts.AllowCrossFile);
651   if (Reject)
652     return makeError(*Reject);
653 
654   // We have two implementations of the rename:
655   //   - AST-based rename: used for renaming local symbols, e.g. variables
656   //     defined in a function body;
657   //   - index-based rename: used for renaming non-local symbols, and not
658   //     feasible for local symbols (as by design our index don't index these
659   //     symbols by design;
660   // To make cross-file rename work for local symbol, we use a hybrid solution:
661   //   - run AST-based rename on the main file;
662   //   - run index-based rename on other affected files;
663   auto MainFileRenameEdit = renameWithinFile(AST, RenameDecl, RInputs.NewName);
664   if (!MainFileRenameEdit)
665     return MainFileRenameEdit.takeError();
666   RenameResult Result;
667   Result.Target = CurrentIdentifier;
668   Edit MainFileEdits = Edit(MainFileCode, std::move(*MainFileRenameEdit));
669   llvm::for_each(MainFileEdits.asTextEdits(), [&Result](const TextEdit &TE) {
670     Result.LocalChanges.push_back(TE.range);
671   });
672 
673   // return the main file edit if this is a within-file rename or the symbol
674   // being renamed is function local.
675   if (!Opts.AllowCrossFile || RenameDecl.getParentFunctionOrMethod()) {
676     Result.GlobalChanges = FileEdits(
677         {std::make_pair(RInputs.MainFilePath, std::move(MainFileEdits))});
678     return Result;
679   }
680 
681   // If the index is nullptr, we don't know the completeness of the result, so
682   // we don't populate the field GlobalChanges.
683   if (!RInputs.Index) {
684     assert(Result.GlobalChanges.empty() && Opts.AllowCrossFile);
685     return Result;
686   }
687 
688   auto OtherFilesEdits = renameOutsideFile(
689       RenameDecl, RInputs.MainFilePath, RInputs.NewName, *RInputs.Index,
690       Opts.LimitFiles == 0 ? std::numeric_limits<size_t>::max()
691                            : Opts.LimitFiles,
692       GetFileContent);
693   if (!OtherFilesEdits)
694     return OtherFilesEdits.takeError();
695   Result.GlobalChanges = *OtherFilesEdits;
696   // Attach the rename edits for the main file.
697   Result.GlobalChanges.try_emplace(RInputs.MainFilePath,
698                                    std::move(MainFileEdits));
699   return Result;
700 }
701 
buildRenameEdit(llvm::StringRef AbsFilePath,llvm::StringRef InitialCode,std::vector<Range> Occurrences,llvm::StringRef NewName)702 llvm::Expected<Edit> buildRenameEdit(llvm::StringRef AbsFilePath,
703                                      llvm::StringRef InitialCode,
704                                      std::vector<Range> Occurrences,
705                                      llvm::StringRef NewName) {
706   trace::Span Tracer("BuildRenameEdit");
707   SPAN_ATTACH(Tracer, "file_path", AbsFilePath);
708   SPAN_ATTACH(Tracer, "rename_occurrences",
709               static_cast<int64_t>(Occurrences.size()));
710 
711   assert(std::is_sorted(Occurrences.begin(), Occurrences.end()));
712   assert(std::unique(Occurrences.begin(), Occurrences.end()) ==
713              Occurrences.end() &&
714          "Occurrences must be unique");
715 
716   // These two always correspond to the same position.
717   Position LastPos{0, 0};
718   size_t LastOffset = 0;
719 
720   auto Offset = [&](const Position &P) -> llvm::Expected<size_t> {
721     assert(LastPos <= P && "malformed input");
722     Position Shifted = {
723         P.line - LastPos.line,
724         P.line > LastPos.line ? P.character : P.character - LastPos.character};
725     auto ShiftedOffset =
726         positionToOffset(InitialCode.substr(LastOffset), Shifted);
727     if (!ShiftedOffset)
728       return error("fail to convert the position {0} to offset ({1})", P,
729                    ShiftedOffset.takeError());
730     LastPos = P;
731     LastOffset += *ShiftedOffset;
732     return LastOffset;
733   };
734 
735   std::vector<std::pair</*start*/ size_t, /*end*/ size_t>> OccurrencesOffsets;
736   for (const auto &R : Occurrences) {
737     auto StartOffset = Offset(R.start);
738     if (!StartOffset)
739       return StartOffset.takeError();
740     auto EndOffset = Offset(R.end);
741     if (!EndOffset)
742       return EndOffset.takeError();
743     OccurrencesOffsets.push_back({*StartOffset, *EndOffset});
744   }
745 
746   tooling::Replacements RenameEdit;
747   for (const auto &R : OccurrencesOffsets) {
748     auto ByteLength = R.second - R.first;
749     if (auto Err = RenameEdit.add(
750             tooling::Replacement(AbsFilePath, R.first, ByteLength, NewName)))
751       return std::move(Err);
752   }
753   return Edit(InitialCode, std::move(RenameEdit));
754 }
755 
756 // Details:
757 //  - lex the draft code to get all rename candidates, this yields a superset
758 //    of candidates.
759 //  - apply range patching heuristics to generate "authoritative" occurrences,
760 //    cases we consider:
761 //      (a) index returns a subset of candidates, we use the indexed results.
762 //        - fully equal, we are sure the index is up-to-date
763 //        - proper subset, index is correct in most cases? there may be false
764 //          positives (e.g. candidates got appended), but rename is still safe
765 //      (b) index returns non-candidate results, we attempt to map the indexed
766 //          ranges onto candidates in a plausible way (e.g. guess that lines
767 //          were inserted). If such a "near miss" is found, the rename is still
768 //          possible
769 llvm::Optional<std::vector<Range>>
adjustRenameRanges(llvm::StringRef DraftCode,llvm::StringRef Identifier,std::vector<Range> Indexed,const LangOptions & LangOpts)770 adjustRenameRanges(llvm::StringRef DraftCode, llvm::StringRef Identifier,
771                    std::vector<Range> Indexed, const LangOptions &LangOpts) {
772   trace::Span Tracer("AdjustRenameRanges");
773   assert(!Indexed.empty());
774   assert(std::is_sorted(Indexed.begin(), Indexed.end()));
775   std::vector<Range> Lexed =
776       collectIdentifierRanges(Identifier, DraftCode, LangOpts);
777   llvm::sort(Lexed);
778   return getMappedRanges(Indexed, Lexed);
779 }
780 
getMappedRanges(ArrayRef<Range> Indexed,ArrayRef<Range> Lexed)781 llvm::Optional<std::vector<Range>> getMappedRanges(ArrayRef<Range> Indexed,
782                                                    ArrayRef<Range> Lexed) {
783   trace::Span Tracer("GetMappedRanges");
784   assert(!Indexed.empty());
785   assert(std::is_sorted(Indexed.begin(), Indexed.end()));
786   assert(std::is_sorted(Lexed.begin(), Lexed.end()));
787 
788   if (Indexed.size() > Lexed.size()) {
789     vlog("The number of lexed occurrences is less than indexed occurrences");
790     SPAN_ATTACH(
791         Tracer, "error",
792         "The number of lexed occurrences is less than indexed occurrences");
793     return llvm::None;
794   }
795   // Fast check for the special subset case.
796   if (std::includes(Indexed.begin(), Indexed.end(), Lexed.begin(), Lexed.end()))
797     return Indexed.vec();
798 
799   std::vector<size_t> Best;
800   size_t BestCost = std::numeric_limits<size_t>::max();
801   bool HasMultiple = 0;
802   std::vector<size_t> ResultStorage;
803   int Fuel = 10000;
804   findNearMiss(ResultStorage, Indexed, Lexed, 0, Fuel,
805                [&](const std::vector<size_t> &Matched) {
806                  size_t MCost =
807                      renameRangeAdjustmentCost(Indexed, Lexed, Matched);
808                  if (MCost < BestCost) {
809                    BestCost = MCost;
810                    Best = std::move(Matched);
811                    HasMultiple = false; // reset
812                    return;
813                  }
814                  if (MCost == BestCost)
815                    HasMultiple = true;
816                });
817   if (HasMultiple) {
818     vlog("The best near miss is not unique.");
819     SPAN_ATTACH(Tracer, "error", "The best near miss is not unique");
820     return llvm::None;
821   }
822   if (Best.empty()) {
823     vlog("Didn't find a near miss.");
824     SPAN_ATTACH(Tracer, "error", "Didn't find a near miss");
825     return llvm::None;
826   }
827   std::vector<Range> Mapped;
828   for (auto I : Best)
829     Mapped.push_back(Lexed[I]);
830   SPAN_ATTACH(Tracer, "mapped_ranges", static_cast<int64_t>(Mapped.size()));
831   return Mapped;
832 }
833 
834 // The cost is the sum of the implied edit sizes between successive diffs, only
835 // simple edits are considered:
836 //   - insert/remove a line (change line offset)
837 //   - insert/remove a character on an existing line (change column offset)
838 //
839 // Example I, total result is 1 + 1 = 2.
840 //   diff[0]: line + 1 <- insert a line before edit 0.
841 //   diff[1]: line + 1
842 //   diff[2]: line + 1
843 //   diff[3]: line + 2 <- insert a line before edits 2 and 3.
844 //
845 // Example II, total result is 1 + 1 + 1 = 3.
846 //   diff[0]: line + 1  <- insert a line before edit 0.
847 //   diff[1]: column + 1 <- remove a line between edits 0 and 1, and insert a
848 //   character on edit 1.
renameRangeAdjustmentCost(ArrayRef<Range> Indexed,ArrayRef<Range> Lexed,ArrayRef<size_t> MappedIndex)849 size_t renameRangeAdjustmentCost(ArrayRef<Range> Indexed, ArrayRef<Range> Lexed,
850                                  ArrayRef<size_t> MappedIndex) {
851   assert(Indexed.size() == MappedIndex.size());
852   assert(std::is_sorted(Indexed.begin(), Indexed.end()));
853   assert(std::is_sorted(Lexed.begin(), Lexed.end()));
854 
855   int LastLine = -1;
856   int LastDLine = 0, LastDColumn = 0;
857   int Cost = 0;
858   for (size_t I = 0; I < Indexed.size(); ++I) {
859     int DLine = Indexed[I].start.line - Lexed[MappedIndex[I]].start.line;
860     int DColumn =
861         Indexed[I].start.character - Lexed[MappedIndex[I]].start.character;
862     int Line = Indexed[I].start.line;
863     if (Line != LastLine)
864       LastDColumn = 0; // column offsets don't carry cross lines.
865     Cost += abs(DLine - LastDLine) + abs(DColumn - LastDColumn);
866     std::tie(LastLine, LastDLine, LastDColumn) = std::tie(Line, DLine, DColumn);
867   }
868   return Cost;
869 }
870 
871 } // namespace clangd
872 } // namespace clang
873