clang-tools  11.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"
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/Refactoring/Rename/USRFindingAction.h"
22 #include "clang/Tooling/Syntax/Tokens.h"
23 #include "llvm/ADT/None.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include "llvm/Support/Casting.h"
26 #include "llvm/Support/Error.h"
27 #include "llvm/Support/FormatVariadic.h"
28 #include <algorithm>
29 
30 namespace clang {
31 namespace clangd {
32 namespace {
33 
34 llvm::Optional<std::string> filePath(const SymbolLocation &Loc,
35  llvm::StringRef HintFilePath) {
36  if (!Loc)
37  return None;
38  auto Path = URI::resolve(Loc.FileURI, HintFilePath);
39  if (!Path) {
40  elog("Could not resolve URI {0}: {1}", Loc.FileURI, Path.takeError());
41  return None;
42  }
43 
44  return *Path;
45 }
46 
47 // Returns true if the given location is expanded from any macro body.
48 bool isInMacroBody(const SourceManager &SM, SourceLocation Loc) {
49  while (Loc.isMacroID()) {
50  if (SM.isMacroBodyExpansion(Loc))
51  return true;
52  Loc = SM.getImmediateMacroCallerLoc(Loc);
53  }
54 
55  return false;
56 }
57 
58 // Query the index to find some other files where the Decl is referenced.
59 llvm::Optional<std::string> getOtherRefFile(const Decl &D, StringRef MainFile,
60  const SymbolIndex &Index) {
61  RefsRequest Req;
62  // We limit the number of results, this is a correctness/performance
63  // tradeoff. We expect the number of symbol references in the current file
64  // is smaller than the limit.
65  Req.Limit = 100;
66  Req.IDs.insert(*getSymbolID(&D));
67  llvm::Optional<std::string> OtherFile;
68  Index.refs(Req, [&](const Ref &R) {
69  if (OtherFile)
70  return;
71  if (auto RefFilePath = filePath(R.Location, /*HintFilePath=*/MainFile)) {
72  if (*RefFilePath != MainFile)
73  OtherFile = *RefFilePath;
74  }
75  });
76  return OtherFile;
77 }
78 
79 llvm::DenseSet<const NamedDecl *> locateDeclAt(ParsedAST &AST,
80  SourceLocation TokenStartLoc) {
81  unsigned Offset =
82  AST.getSourceManager().getDecomposedSpellingLoc(TokenStartLoc).second;
83 
84  SelectionTree Selection = SelectionTree::createRight(
85  AST.getASTContext(), AST.getTokens(), Offset, Offset);
86  const SelectionTree::Node *SelectedNode = Selection.commonAncestor();
87  if (!SelectedNode)
88  return {};
89 
90  llvm::DenseSet<const NamedDecl *> Result;
91  for (const NamedDecl *D :
92  targetDecl(SelectedNode->ASTNode,
94  // Get to CXXRecordDecl from constructor or destructor.
95  D = tooling::getCanonicalSymbolDeclaration(D);
96  Result.insert(D);
97  }
98  return Result;
99 }
100 
101 // By default, we exclude C++ standard symbols and protobuf symbols as rename
102 // these symbols would change system/generated files which are unlikely to be
103 // modified.
104 bool isExcluded(const NamedDecl &RenameDecl) {
105  if (isProtoFile(RenameDecl.getLocation(),
106  RenameDecl.getASTContext().getSourceManager()))
107  return true;
108  static const auto *StdSymbols = new llvm::DenseSet<llvm::StringRef>({
109 #define SYMBOL(Name, NameSpace, Header) {#NameSpace #Name},
110 #include "StdSymbolMap.inc"
111 #undef SYMBOL
112  });
113  return StdSymbols->count(printQualifiedName(RenameDecl));
114 }
115 
117  NoSymbolFound,
118  NoIndexProvided,
119  NonIndexable,
120  UsedOutsideFile, // for within-file rename only.
121  UnsupportedSymbol,
122  AmbiguousSymbol,
123 };
124 
125 llvm::Optional<ReasonToReject> renameable(const NamedDecl &RenameDecl,
126  StringRef MainFilePath,
127  const SymbolIndex *Index,
128  bool CrossFile) {
129  trace::Span Tracer("Renameable");
130  // Filter out symbols that are unsupported in both rename modes.
131  if (llvm::isa<NamespaceDecl>(&RenameDecl))
132  return ReasonToReject::UnsupportedSymbol;
133  if (const auto *FD = llvm::dyn_cast<FunctionDecl>(&RenameDecl)) {
134  if (FD->isOverloadedOperator())
135  return ReasonToReject::UnsupportedSymbol;
136  }
137  // function-local symbols is safe to rename.
138  if (RenameDecl.getParentFunctionOrMethod())
139  return None;
140 
141  if (isExcluded(RenameDecl))
142  return ReasonToReject::UnsupportedSymbol;
143 
144  // Check whether the symbol being rename is indexable.
145  auto &ASTCtx = RenameDecl.getASTContext();
146  bool MainFileIsHeader = isHeaderFile(MainFilePath, ASTCtx.getLangOpts());
147  bool DeclaredInMainFile =
148  isInsideMainFile(RenameDecl.getBeginLoc(), ASTCtx.getSourceManager());
149  bool IsMainFileOnly = true;
150  if (MainFileIsHeader)
151  // main file is a header, the symbol can't be main file only.
152  IsMainFileOnly = false;
153  else if (!DeclaredInMainFile)
154  IsMainFileOnly = false;
155  // If the symbol is not indexable, we disallow rename.
157  RenameDecl, RenameDecl.getASTContext(), SymbolCollector::Options(),
158  IsMainFileOnly))
159  return ReasonToReject::NonIndexable;
160 
161  if (!CrossFile) {
162  if (!DeclaredInMainFile)
163  // We are sure the symbol is used externally, bail out early.
164  return ReasonToReject::UsedOutsideFile;
165 
166  // If the symbol is declared in the main file (which is not a header), we
167  // rename it.
168  if (!MainFileIsHeader)
169  return None;
170 
171  if (!Index)
172  return ReasonToReject::NoIndexProvided;
173 
174  auto OtherFile = getOtherRefFile(RenameDecl, MainFilePath, *Index);
175  // If the symbol is indexable and has no refs from other files in the index,
176  // we rename it.
177  if (!OtherFile)
178  return None;
179  // If the symbol is indexable and has refs from other files in the index,
180  // we disallow rename.
181  return ReasonToReject::UsedOutsideFile;
182  }
183 
184  assert(CrossFile);
185  if (!Index)
186  return ReasonToReject::NoIndexProvided;
187 
188  // FIXME: Renaming virtual methods requires to rename all overridens in
189  // subclasses, our index doesn't have this information.
190  // Note: Within-file rename does support this through the AST.
191  if (const auto *S = llvm::dyn_cast<CXXMethodDecl>(&RenameDecl)) {
192  if (S->isVirtual())
193  return ReasonToReject::UnsupportedSymbol;
194  }
195  return None;
196 }
197 
199  auto Message = [](ReasonToReject Reason) {
200  switch (Reason) {
201  case ReasonToReject::NoSymbolFound:
202  return "there is no symbol at the given location";
203  case ReasonToReject::NoIndexProvided:
204  return "no index provided";
205  case ReasonToReject::UsedOutsideFile:
206  return "the symbol is used outside main file";
207  case ReasonToReject::NonIndexable:
208  return "symbol may be used in other files (not eligible for indexing)";
209  case ReasonToReject::UnsupportedSymbol:
210  return "symbol is not a supported kind (e.g. namespace, macro)";
211  case AmbiguousSymbol:
212  return "there are multiple symbols at the given location";
213  }
214  llvm_unreachable("unhandled reason kind");
215  };
216  return llvm::make_error<llvm::StringError>(
217  llvm::formatv("Cannot rename symbol: {0}", Message(Reason)),
218  llvm::inconvertibleErrorCode());
219 }
220 
221 // Return all rename occurrences in the main file.
222 std::vector<SourceLocation> findOccurrencesWithinFile(ParsedAST &AST,
223  const NamedDecl &ND) {
224  trace::Span Tracer("FindOccurrenceeWithinFile");
225  // If the cursor is at the underlying CXXRecordDecl of the
226  // ClassTemplateDecl, ND will be the CXXRecordDecl. In this case, we need to
227  // get the primary template manually.
228  // getUSRsForDeclaration will find other related symbols, e.g. virtual and its
229  // overriddens, primary template and all explicit specializations.
230  // FIXME: Get rid of the remaining tooling APIs.
231  const auto *RenameDecl =
232  ND.getDescribedTemplate() ? ND.getDescribedTemplate() : &ND;
233  std::vector<std::string> RenameUSRs =
234  tooling::getUSRsForDeclaration(RenameDecl, AST.getASTContext());
235  llvm::DenseSet<SymbolID> TargetIDs;
236  for (auto &USR : RenameUSRs)
237  TargetIDs.insert(SymbolID(USR));
238 
239  std::vector<SourceLocation> Results;
240  for (Decl *TopLevelDecl : AST.getLocalTopLevelDecls()) {
241  findExplicitReferences(TopLevelDecl, [&](ReferenceLoc Ref) {
242  if (Ref.Targets.empty())
243  return;
244  for (const auto *Target : Ref.Targets) {
245  auto ID = getSymbolID(Target);
246  if (!ID || TargetIDs.find(*ID) == TargetIDs.end())
247  return;
248  }
249  Results.push_back(Ref.NameLoc);
250  });
251  }
252 
253  return Results;
254 }
255 
256 // AST-based rename, it renames all occurrences in the main file.
257 llvm::Expected<tooling::Replacements>
258 renameWithinFile(ParsedAST &AST, const NamedDecl &RenameDecl,
259  llvm::StringRef NewName) {
260  trace::Span Tracer("RenameWithinFile");
261  const SourceManager &SM = AST.getSourceManager();
262 
263  tooling::Replacements FilteredChanges;
264  for (SourceLocation Loc : findOccurrencesWithinFile(AST, RenameDecl)) {
265  SourceLocation RenameLoc = Loc;
266  // We don't rename in any macro bodies, but we allow rename the symbol
267  // spelled in a top-level macro argument in the main file.
268  if (RenameLoc.isMacroID()) {
269  if (isInMacroBody(SM, RenameLoc))
270  continue;
271  RenameLoc = SM.getSpellingLoc(Loc);
272  }
273  // Filter out locations not from main file.
274  // We traverse only main file decls, but locations could come from an
275  // non-preamble #include file e.g.
276  // void test() {
277  // int f^oo;
278  // #include "use_foo.inc"
279  // }
280  if (!isInsideMainFile(RenameLoc, SM))
281  continue;
282  if (auto Err = FilteredChanges.add(tooling::Replacement(
283  SM, CharSourceRange::getTokenRange(RenameLoc), NewName)))
284  return std::move(Err);
285  }
286  return FilteredChanges;
287 }
288 
289 Range toRange(const SymbolLocation &L) {
290  Range R;
291  R.start.line = L.Start.line();
292  R.start.character = L.Start.column();
293  R.end.line = L.End.line();
294  R.end.character = L.End.column();
295  return R;
296 }
297 
298 // Return all rename occurrences (using the index) outside of the main file,
299 // grouped by the absolute file path.
300 llvm::Expected<llvm::StringMap<std::vector<Range>>>
301 findOccurrencesOutsideFile(const NamedDecl &RenameDecl,
302  llvm::StringRef MainFile, const SymbolIndex &Index,
303  size_t MaxLimitFiles) {
304  trace::Span Tracer("FindOccurrencesOutsideFile");
305  RefsRequest RQuest;
306  RQuest.IDs.insert(*getSymbolID(&RenameDecl));
307 
308  // Absolute file path => rename occurrences in that file.
309  llvm::StringMap<std::vector<Range>> AffectedFiles;
310  bool HasMore = Index.refs(RQuest, [&](const Ref &R) {
311  if (AffectedFiles.size() >= MaxLimitFiles)
312  return;
314  return;
315  if (auto RefFilePath = filePath(R.Location, /*HintFilePath=*/MainFile)) {
316  if (*RefFilePath != MainFile)
317  AffectedFiles[*RefFilePath].push_back(toRange(R.Location));
318  }
319  });
320 
321  if (AffectedFiles.size() >= MaxLimitFiles)
322  return llvm::make_error<llvm::StringError>(
323  llvm::formatv("The number of affected files exceeds the max limit {0}",
324  MaxLimitFiles),
325  llvm::inconvertibleErrorCode());
326  if (HasMore) {
327  return llvm::make_error<llvm::StringError>(
328  llvm::formatv("The symbol {0} has too many occurrences",
329  RenameDecl.getQualifiedNameAsString()),
330  llvm::inconvertibleErrorCode());
331  }
332  // Sort and deduplicate the results, in case that index returns duplications.
333  for (auto &FileAndOccurrences : AffectedFiles) {
334  auto &Ranges = FileAndOccurrences.getValue();
335  llvm::sort(Ranges);
336  Ranges.erase(std::unique(Ranges.begin(), Ranges.end()), Ranges.end());
337 
338  SPAN_ATTACH(Tracer, FileAndOccurrences.first(),
339  static_cast<int64_t>(Ranges.size()));
340  }
341  return AffectedFiles;
342 }
343 
344 // Index-based rename, it renames all occurrences outside of the main file.
345 //
346 // The cross-file rename is purely based on the index, as we don't want to
347 // build all ASTs for affected files, which may cause a performance hit.
348 // We choose to trade off some correctness for performance and scalability.
349 //
350 // Clangd builds a dynamic index for all opened files on top of the static
351 // index of the whole codebase. Dynamic index is up-to-date (respects dirty
352 // buffers) as long as clangd finishes processing opened files, while static
353 // index (background index) is relatively stale. We choose the dirty buffers
354 // as the file content we rename on, and fallback to file content on disk if
355 // there is no dirty buffer.
356 llvm::Expected<FileEdits> renameOutsideFile(
357  const NamedDecl &RenameDecl, llvm::StringRef MainFilePath,
358  llvm::StringRef NewName, const SymbolIndex &Index, size_t MaxLimitFiles,
359  llvm::function_ref<llvm::Expected<std::string>(PathRef)> GetFileContent) {
360  trace::Span Tracer("RenameOutsideFile");
361  auto AffectedFiles = findOccurrencesOutsideFile(RenameDecl, MainFilePath,
362  Index, MaxLimitFiles);
363  if (!AffectedFiles)
364  return AffectedFiles.takeError();
366  for (auto &FileAndOccurrences : *AffectedFiles) {
367  llvm::StringRef FilePath = FileAndOccurrences.first();
368 
369  auto AffectedFileCode = GetFileContent(FilePath);
370  if (!AffectedFileCode) {
371  elog("Fail to read file content: {0}", AffectedFileCode.takeError());
372  continue;
373  }
374  auto RenameRanges =
375  adjustRenameRanges(*AffectedFileCode, RenameDecl.getNameAsString(),
376  std::move(FileAndOccurrences.second),
377  RenameDecl.getASTContext().getLangOpts());
378  if (!RenameRanges) {
379  // Our heuristics fails to adjust rename ranges to the current state of
380  // the file, it is most likely the index is stale, so we give up the
381  // entire rename.
382  return llvm::make_error<llvm::StringError>(
383  llvm::formatv("Index results don't match the content of file {0} "
384  "(the index may be stale)",
385  FilePath),
386  llvm::inconvertibleErrorCode());
387  }
388  auto RenameEdit =
389  buildRenameEdit(FilePath, *AffectedFileCode, *RenameRanges, NewName);
390  if (!RenameEdit) {
391  return llvm::make_error<llvm::StringError>(
392  llvm::formatv("fail to build rename edit for file {0}: {1}", FilePath,
393  llvm::toString(RenameEdit.takeError())),
394  llvm::inconvertibleErrorCode());
395  }
396  if (!RenameEdit->Replacements.empty())
397  Results.insert({FilePath, std::move(*RenameEdit)});
398  }
399  return Results;
400 }
401 
402 // A simple edit is either changing line or column, but not both.
403 bool impliesSimpleEdit(const Position &LHS, const Position &RHS) {
404  return LHS.line == RHS.line || LHS.character == RHS.character;
405 }
406 
407 // Performs a DFS to enumerate all possible near-miss matches.
408 // It finds the locations where the indexed occurrences are now spelled in
409 // Lexed occurrences, a near miss is defined as:
410 // - a near miss maps all of the **name** occurrences from the index onto a
411 // *subset* of lexed occurrences (we allow a single name refers to more
412 // than one symbol)
413 // - all indexed occurrences must be mapped, and Result must be distinct and
414 // preserve order (only support detecting simple edits to ensure a
415 // robust mapping)
416 // - each indexed -> lexed occurrences mapping correspondence may change the
417 // *line* or *column*, but not both (increases chance of a robust mapping)
418 void findNearMiss(
419  std::vector<size_t> &PartialMatch, ArrayRef<Range> IndexedRest,
420  ArrayRef<Range> LexedRest, int LexedIndex, int &Fuel,
421  llvm::function_ref<void(const std::vector<size_t> &)> MatchedCB) {
422  if (--Fuel < 0)
423  return;
424  if (IndexedRest.size() > LexedRest.size())
425  return;
426  if (IndexedRest.empty()) {
427  MatchedCB(PartialMatch);
428  return;
429  }
430  if (impliesSimpleEdit(IndexedRest.front().start, LexedRest.front().start)) {
431  PartialMatch.push_back(LexedIndex);
432  findNearMiss(PartialMatch, IndexedRest.drop_front(), LexedRest.drop_front(),
433  LexedIndex + 1, Fuel, MatchedCB);
434  PartialMatch.pop_back();
435  }
436  findNearMiss(PartialMatch, IndexedRest, LexedRest.drop_front(),
437  LexedIndex + 1, Fuel, MatchedCB);
438 }
439 
440 } // namespace
441 
442 llvm::Expected<FileEdits> rename(const RenameInputs &RInputs) {
443  trace::Span Tracer("Rename flow");
444  const auto &Opts = RInputs.Opts;
445  ParsedAST &AST = RInputs.AST;
446  const SourceManager &SM = AST.getSourceManager();
447  llvm::StringRef MainFileCode = SM.getBufferData(SM.getMainFileID());
448  auto GetFileContent = [&RInputs,
449  &SM](PathRef AbsPath) -> llvm::Expected<std::string> {
450  llvm::Optional<std::string> DirtyBuffer;
451  if (RInputs.GetDirtyBuffer &&
452  (DirtyBuffer = RInputs.GetDirtyBuffer(AbsPath)))
453  return std::move(*DirtyBuffer);
454 
455  auto Content =
456  SM.getFileManager().getVirtualFileSystem().getBufferForFile(AbsPath);
457  if (!Content)
458  return llvm::createStringError(
459  llvm::inconvertibleErrorCode(),
460  llvm::formatv("Fail to open file {0}: {1}", AbsPath,
461  Content.getError().message()));
462  if (!*Content)
463  return llvm::createStringError(
464  llvm::inconvertibleErrorCode(),
465  llvm::formatv("Got no buffer for file {0}", AbsPath));
466 
467  return (*Content)->getBuffer().str();
468  };
469  // Try to find the tokens adjacent to the cursor position.
470  auto Loc = sourceLocationInMainFile(SM, RInputs.Pos);
471  if (!Loc)
472  return Loc.takeError();
473  const syntax::Token *IdentifierToken =
474  spelledIdentifierTouching(*Loc, AST.getTokens());
475  // Renames should only triggered on identifiers.
476  if (!IdentifierToken)
477  return makeError(ReasonToReject::NoSymbolFound);
478  // FIXME: Renaming macros is not supported yet, the macro-handling code should
479  // be moved to rename tooling library.
480  if (locateMacroAt(*IdentifierToken, AST.getPreprocessor()))
481  return makeError(ReasonToReject::UnsupportedSymbol);
482 
483  auto DeclsUnderCursor = locateDeclAt(AST, IdentifierToken->location());
484  if (DeclsUnderCursor.empty())
485  return makeError(ReasonToReject::NoSymbolFound);
486  if (DeclsUnderCursor.size() > 1)
487  return makeError(ReasonToReject::AmbiguousSymbol);
488 
489  const auto &RenameDecl =
490  llvm::cast<NamedDecl>(*(*DeclsUnderCursor.begin())->getCanonicalDecl());
491  auto Reject = renameable(RenameDecl, RInputs.MainFilePath, RInputs.Index,
492  Opts.AllowCrossFile);
493  if (Reject)
494  return makeError(*Reject);
495 
496  // We have two implementations of the rename:
497  // - AST-based rename: used for renaming local symbols, e.g. variables
498  // defined in a function body;
499  // - index-based rename: used for renaming non-local symbols, and not
500  // feasible for local symbols (as by design our index don't index these
501  // symbols by design;
502  // To make cross-file rename work for local symbol, we use a hybrid solution:
503  // - run AST-based rename on the main file;
504  // - run index-based rename on other affected files;
505  auto MainFileRenameEdit = renameWithinFile(AST, RenameDecl, RInputs.NewName);
506  if (!MainFileRenameEdit)
507  return MainFileRenameEdit.takeError();
508 
509  // return the main file edit if this is a within-file rename or the symbol
510  // being renamed is function local.
511  if (!Opts.AllowCrossFile || RenameDecl.getParentFunctionOrMethod()) {
512  return FileEdits(
513  {std::make_pair(RInputs.MainFilePath,
514  Edit{MainFileCode, std::move(*MainFileRenameEdit)})});
515  }
516 
518  // Renameable safely guards us that at this point we are renaming a local
519  // symbol if we don't have index.
520  if (RInputs.Index) {
521  auto OtherFilesEdits = renameOutsideFile(
522  RenameDecl, RInputs.MainFilePath, RInputs.NewName, *RInputs.Index,
523  Opts.LimitFiles == 0 ? std::numeric_limits<size_t>::max()
524  : Opts.LimitFiles,
525  GetFileContent);
526  if (!OtherFilesEdits)
527  return OtherFilesEdits.takeError();
528  Results = std::move(*OtherFilesEdits);
529  }
530  // Attach the rename edits for the main file.
531  Results.try_emplace(RInputs.MainFilePath, MainFileCode,
532  std::move(*MainFileRenameEdit));
533  return Results;
534 }
535 
536 llvm::Expected<Edit> buildRenameEdit(llvm::StringRef AbsFilePath,
537  llvm::StringRef InitialCode,
538  std::vector<Range> Occurrences,
539  llvm::StringRef NewName) {
540  trace::Span Tracer("BuildRenameEdit");
541  SPAN_ATTACH(Tracer, "file_path", AbsFilePath);
542  SPAN_ATTACH(Tracer, "rename_occurrences",
543  static_cast<int64_t>(Occurrences.size()));
544 
545  assert(std::is_sorted(Occurrences.begin(), Occurrences.end()));
546  assert(std::unique(Occurrences.begin(), Occurrences.end()) ==
547  Occurrences.end() &&
548  "Occurrences must be unique");
549 
550  // These two always correspond to the same position.
551  Position LastPos{0, 0};
552  size_t LastOffset = 0;
553 
554  auto Offset = [&](const Position &P) -> llvm::Expected<size_t> {
555  assert(LastPos <= P && "malformed input");
556  Position Shifted = {
557  P.line - LastPos.line,
558  P.line > LastPos.line ? P.character : P.character - LastPos.character};
559  auto ShiftedOffset =
560  positionToOffset(InitialCode.substr(LastOffset), Shifted);
561  if (!ShiftedOffset)
562  return llvm::make_error<llvm::StringError>(
563  llvm::formatv("fail to convert the position {0} to offset ({1})", P,
564  llvm::toString(ShiftedOffset.takeError())),
565  llvm::inconvertibleErrorCode());
566  LastPos = P;
567  LastOffset += *ShiftedOffset;
568  return LastOffset;
569  };
570 
571  std::vector<std::pair</*start*/ size_t, /*end*/ size_t>> OccurrencesOffsets;
572  for (const auto &R : Occurrences) {
573  auto StartOffset = Offset(R.start);
574  if (!StartOffset)
575  return StartOffset.takeError();
576  auto EndOffset = Offset(R.end);
577  if (!EndOffset)
578  return EndOffset.takeError();
579  OccurrencesOffsets.push_back({*StartOffset, *EndOffset});
580  }
581 
582  tooling::Replacements RenameEdit;
583  for (const auto &R : OccurrencesOffsets) {
584  auto ByteLength = R.second - R.first;
585  if (auto Err = RenameEdit.add(
586  tooling::Replacement(AbsFilePath, R.first, ByteLength, NewName)))
587  return std::move(Err);
588  }
589  return Edit(InitialCode, std::move(RenameEdit));
590 }
591 
592 // Details:
593 // - lex the draft code to get all rename candidates, this yields a superset
594 // of candidates.
595 // - apply range patching heuristics to generate "authoritative" occurrences,
596 // cases we consider:
597 // (a) index returns a subset of candidates, we use the indexed results.
598 // - fully equal, we are sure the index is up-to-date
599 // - proper subset, index is correct in most cases? there may be false
600 // positives (e.g. candidates got appended), but rename is still safe
601 // (b) index returns non-candidate results, we attempt to map the indexed
602 // ranges onto candidates in a plausible way (e.g. guess that lines
603 // were inserted). If such a "near miss" is found, the rename is still
604 // possible
605 llvm::Optional<std::vector<Range>>
606 adjustRenameRanges(llvm::StringRef DraftCode, llvm::StringRef Identifier,
607  std::vector<Range> Indexed, const LangOptions &LangOpts) {
608  trace::Span Tracer("AdjustRenameRanges");
609  assert(!Indexed.empty());
610  assert(std::is_sorted(Indexed.begin(), Indexed.end()));
611  std::vector<Range> Lexed =
612  collectIdentifierRanges(Identifier, DraftCode, LangOpts);
613  llvm::sort(Lexed);
614  return getMappedRanges(Indexed, Lexed);
615 }
616 
617 llvm::Optional<std::vector<Range>> getMappedRanges(ArrayRef<Range> Indexed,
618  ArrayRef<Range> Lexed) {
619  trace::Span Tracer("GetMappedRanges");
620  assert(!Indexed.empty());
621  assert(std::is_sorted(Indexed.begin(), Indexed.end()));
622  assert(std::is_sorted(Lexed.begin(), Lexed.end()));
623 
624  if (Indexed.size() > Lexed.size()) {
625  vlog("The number of lexed occurrences is less than indexed occurrences");
626  SPAN_ATTACH(
627  Tracer, "error",
628  "The number of lexed occurrences is less than indexed occurrences");
629  return llvm::None;
630  }
631  // Fast check for the special subset case.
632  if (std::includes(Indexed.begin(), Indexed.end(), Lexed.begin(), Lexed.end()))
633  return Indexed.vec();
634 
635  std::vector<size_t> Best;
636  size_t BestCost = std::numeric_limits<size_t>::max();
637  bool HasMultiple = 0;
638  std::vector<size_t> ResultStorage;
639  int Fuel = 10000;
640  findNearMiss(ResultStorage, Indexed, Lexed, 0, Fuel,
641  [&](const std::vector<size_t> &Matched) {
642  size_t MCost =
643  renameRangeAdjustmentCost(Indexed, Lexed, Matched);
644  if (MCost < BestCost) {
645  BestCost = MCost;
646  Best = std::move(Matched);
647  HasMultiple = false; // reset
648  return;
649  }
650  if (MCost == BestCost)
651  HasMultiple = true;
652  });
653  if (HasMultiple) {
654  vlog("The best near miss is not unique.");
655  SPAN_ATTACH(Tracer, "error", "The best near miss is not unique");
656  return llvm::None;
657  }
658  if (Best.empty()) {
659  vlog("Didn't find a near miss.");
660  SPAN_ATTACH(Tracer, "error", "Didn't find a near miss");
661  return llvm::None;
662  }
663  std::vector<Range> Mapped;
664  for (auto I : Best)
665  Mapped.push_back(Lexed[I]);
666  SPAN_ATTACH(Tracer, "mapped_ranges", static_cast<int64_t>(Mapped.size()));
667  return Mapped;
668 }
669 
670 // The cost is the sum of the implied edit sizes between successive diffs, only
671 // simple edits are considered:
672 // - insert/remove a line (change line offset)
673 // - insert/remove a character on an existing line (change column offset)
674 //
675 // Example I, total result is 1 + 1 = 2.
676 // diff[0]: line + 1 <- insert a line before edit 0.
677 // diff[1]: line + 1
678 // diff[2]: line + 1
679 // diff[3]: line + 2 <- insert a line before edits 2 and 3.
680 //
681 // Example II, total result is 1 + 1 + 1 = 3.
682 // diff[0]: line + 1 <- insert a line before edit 0.
683 // diff[1]: column + 1 <- remove a line between edits 0 and 1, and insert a
684 // character on edit 1.
685 size_t renameRangeAdjustmentCost(ArrayRef<Range> Indexed, ArrayRef<Range> Lexed,
686  ArrayRef<size_t> MappedIndex) {
687  assert(Indexed.size() == MappedIndex.size());
688  assert(std::is_sorted(Indexed.begin(), Indexed.end()));
689  assert(std::is_sorted(Lexed.begin(), Lexed.end()));
690 
691  int LastLine = -1;
692  int LastDLine = 0, LastDColumn = 0;
693  int Cost = 0;
694  for (size_t I = 0; I < Indexed.size(); ++I) {
695  int DLine = Indexed[I].start.line - Lexed[MappedIndex[I]].start.line;
696  int DColumn =
697  Indexed[I].start.character - Lexed[MappedIndex[I]].start.character;
698  int Line = Indexed[I].start.line;
699  if (Line != LastLine)
700  LastDColumn = 0; // column offsets don't carry cross lines.
701  Cost += abs(DLine - LastDLine) + abs(DColumn - LastDColumn);
702  std::tie(LastLine, LastDLine, LastDColumn) = std::tie(Line, DLine, DColumn);
703  }
704  return Cost;
705 }
706 
707 } // namespace clangd
708 } // namespace clang
SourceLocation Loc
&#39;#&#39; location in the include directive
bool isProtoFile(SourceLocation Loc, const SourceManager &SM)
Returns true if the given location is in a generated protobuf file.
const FunctionDecl * Decl
llvm::DenseSet< SymbolID > IDs
Definition: Index.h:68
std::string printQualifiedName(const NamedDecl &ND)
Returns the qualified name of ND.
Definition: AST.cpp:168
Position start
The range&#39;s start position.
Definition: Protocol.h:175
llvm::Optional< SymbolID > getSymbolID(const Decl *D)
Gets the symbol ID for a declaration, if possible.
Definition: AST.cpp:285
static llvm::Error makeError(const char *Msg)
Definition: RIFF.cpp:16
Preprocessor & getPreprocessor()
Definition: ParsedAST.cpp:477
llvm::Optional< std::vector< Range > > getMappedRanges(ArrayRef< Range > Indexed, ArrayRef< Range > Lexed)
Calculates the lexed occurrences that the given indexed occurrences map to.
Definition: Rename.cpp:617
const SymbolIndex * Index
Definition: Rename.h:48
Information about a reference written in the source code, independent of the actual AST node that thi...
Definition: FindTarget.h:119
DirtyBufferGetter GetDirtyBuffer
Definition: Rename.h:55
This is the pattern the template specialization was instantiated from.
Interface for symbol indexes that can be used for searching or matching symbols among a set of symbol...
Definition: Index.h:85
bool isInsideMainFile(SourceLocation Loc, const SourceManager &SM)
Returns true iff Loc is inside the main file.
Definition: SourceCode.cpp:421
Represents a symbol occurrence in the source file.
Definition: Ref.h:87
llvm::StringRef PathRef
A typedef to represent a ref to file path.
Definition: Path.h:23
static llvm::StringRef toString(SpecialMemberFunctionsCheck::SpecialMemberFunctionKind K)
std::vector< CodeCompletionResult > Results
llvm::StringRef MainFilePath
Definition: Rename.h:46
ArrayRef< Decl * > getLocalTopLevelDecls()
This function returns top-level decls present in the main file of the AST.
Definition: ParsedAST.cpp:487
Documents should not be synced at all.
RenameOptions Opts
Definition: Rename.h:50
void vlog(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:67
void elog(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:56
llvm::Expected< SourceLocation > sourceLocationInMainFile(const SourceManager &SM, Position P)
Return the file location, corresponding to P.
Definition: SourceCode.cpp:461
This declaration is an alias that was referred to.
llvm::StringRef NewName
Definition: Rename.h:43
const syntax::TokenBuffer & getTokens() const
Tokens recorded while parsing the main file.
Definition: ParsedAST.h:103
ASTContext & getASTContext()
Note that the returned ast will not contain decls from the preamble that were not deserialized during...
Definition: ParsedAST.cpp:471
std::string MainFile
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:175
SourceLocation NameLoc
Start location of the last name part, i.e. &#39;foo&#39; in &#39;ns::foo<int>&#39;.
Definition: FindTarget.h:123
SymbolLocation Location
The source location where the symbol is named.
Definition: Ref.h:89
std::string Path
A typedef to represent a file path.
Definition: Path.h:20
virtual bool refs(const RefsRequest &Req, llvm::function_ref< void(const Ref &)> Callback) const =0
Finds all occurrences (e.g.
static SelectionTree createRight(ASTContext &AST, const syntax::TokenBuffer &Tokens, unsigned Begin, unsigned End)
Definition: Selection.cpp:784
llvm::SmallVector< const NamedDecl *, 1 > Targets
A list of targets referenced by this name.
Definition: FindTarget.h:131
llvm::SmallVector< const NamedDecl *, 1 > targetDecl(const ast_type_traits::DynTypedNode &N, DeclRelationSet Mask)
targetDecl() finds the declaration referred to by an AST node.
Definition: FindTarget.cpp:545
Stores and provides access to parsed AST.
Definition: ParsedAST.h:48
llvm::StringMap< Edit > FileEdits
A mapping from absolute file path (the one used for accessing the underlying VFS) to edits...
Definition: SourceCode.h:198
llvm::Optional< DefinedMacro > locateMacroAt(const syntax::Token &SpelledTok, Preprocessor &PP)
Gets the macro referenced by SpelledTok.
Definition: SourceCode.cpp:968
Range toRange(llvm::SMRange R, const llvm::SourceMgr &SM)
Definition: ConfigTesting.h:69
SourceManager & getSourceManager()
Definition: ParsedAST.h:74
int line
Line position in a document (zero-based).
Definition: Protocol.h:146
size_t Offset
int character
Character offset on a line in a document (zero-based).
Definition: Protocol.h:151
static bool shouldCollectSymbol(const NamedDecl &ND, const ASTContext &ASTCtx, const Options &Opts, bool IsMainFileSymbol)
Returns true is ND should be collected.
Position Start
The symbol range, using half-open range [Start, End).
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
void findExplicitReferences(const Stmt *S, llvm::function_ref< void(ReferenceLoc)> Out)
Recursively traverse S and report all references explicitly written in the code.
Definition: FindTarget.cpp:994
size_t renameRangeAdjustmentCost(ArrayRef< Range > Indexed, ArrayRef< Range > Lexed, ArrayRef< size_t > MappedIndex)
Evaluates how good the mapped result is.
Definition: Rename.cpp:685
std::unique_ptr< trace::EventTracer > Tracer
Definition: TraceTests.cpp:163
bool isHeaderFile(llvm::StringRef FileName, llvm::Optional< LangOptions > LangOpts)
Infers whether this is a header from the FileName and LangOpts (if presents).
static llvm::Expected< std::string > resolve(const URI &U, llvm::StringRef HintPath="")
Resolves the absolute path of U.
Definition: URI.cpp:232
const Node * commonAncestor() const
Definition: Selection.cpp:814
llvm::Optional< std::vector< Range > > adjustRenameRanges(llvm::StringRef DraftCode, llvm::StringRef Identifier, std::vector< Range > Indexed, const LangOptions &LangOpts)
Adjusts indexed occurrences to match the current state of the file.
Definition: Rename.cpp:606
llvm::Expected< FileEdits > rename(const RenameInputs &RInputs)
Renames all occurrences of the symbol.
Definition: Rename.cpp:442
Position end
The range&#39;s end position.
Definition: Protocol.h:178
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:627
Records an event whose duration is the lifetime of the Span object.
Definition: Trace.h:135
std::array< uint8_t, 20 > SymbolID
#define SPAN_ATTACH(S, Name, Expr)
Attach a key-value pair to a Span event.
Definition: Trace.h:154
A set of edits generated for a single file.
Definition: SourceCode.h:180
llvm::Expected< Edit > buildRenameEdit(llvm::StringRef AbsFilePath, llvm::StringRef InitialCode, std::vector< Range > Occurrences, llvm::StringRef NewName)
Generates rename edits that replaces all given occurrences with the NewName.
Definition: Rename.cpp:536
RefKind Kind
Definition: Ref.h:90
const SymbolIndex * Index
Definition: Dexp.cpp:92