[clang-tools-extra] NFC: Fix trivial typo in documents and comments
[lldb.git] / clang-tools-extra / clangd / refactor / Rename.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-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "refactor/Rename.h"
10 #include "AST.h"
11 #include "FindTarget.h"
12 #include "Logger.h"
13 #include "ParsedAST.h"
14 #include "Selection.h"
15 #include "SourceCode.h"
16 #include "Trace.h"
17 #include "index/SymbolCollector.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,
93                   DeclRelation::Alias | DeclRelation::TemplatePattern)) {
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 blacklist 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 isBlacklisted(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
116 enum ReasonToReject {
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 (isBlacklisted(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.
156   if (!SymbolCollector::shouldCollectSymbol(
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
198 llvm::Error makeError(ReasonToReject Reason) {
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;
313     if ((R.Kind & RefKind::Spelled) == RefKind::Unknown)
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();
365   FileEdits Results;
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
517   FileEdits Results;
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