• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- XRefs.cpp -----------------------------------------------*- 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 #include "XRefs.h"
9 #include "AST.h"
10 #include "CodeCompletionStrings.h"
11 #include "FindSymbols.h"
12 #include "FindTarget.h"
13 #include "ParsedAST.h"
14 #include "Protocol.h"
15 #include "Quality.h"
16 #include "Selection.h"
17 #include "SourceCode.h"
18 #include "URI.h"
19 #include "index/Index.h"
20 #include "index/Merge.h"
21 #include "index/Relation.h"
22 #include "index/SymbolLocation.h"
23 #include "support/Logger.h"
24 #include "clang/AST/ASTContext.h"
25 #include "clang/AST/ASTTypeTraits.h"
26 #include "clang/AST/Attr.h"
27 #include "clang/AST/Attrs.inc"
28 #include "clang/AST/Decl.h"
29 #include "clang/AST/DeclCXX.h"
30 #include "clang/AST/DeclObjC.h"
31 #include "clang/AST/DeclTemplate.h"
32 #include "clang/AST/ExprCXX.h"
33 #include "clang/AST/RecursiveASTVisitor.h"
34 #include "clang/AST/Stmt.h"
35 #include "clang/AST/StmtCXX.h"
36 #include "clang/AST/Type.h"
37 #include "clang/Basic/CharInfo.h"
38 #include "clang/Basic/LLVM.h"
39 #include "clang/Basic/LangOptions.h"
40 #include "clang/Basic/SourceLocation.h"
41 #include "clang/Basic/SourceManager.h"
42 #include "clang/Basic/TokenKinds.h"
43 #include "clang/Index/IndexDataConsumer.h"
44 #include "clang/Index/IndexSymbol.h"
45 #include "clang/Index/IndexingAction.h"
46 #include "clang/Index/IndexingOptions.h"
47 #include "clang/Index/USRGeneration.h"
48 #include "clang/Tooling/Syntax/Tokens.h"
49 #include "llvm/ADT/ArrayRef.h"
50 #include "llvm/ADT/MapVector.h"
51 #include "llvm/ADT/None.h"
52 #include "llvm/ADT/STLExtras.h"
53 #include "llvm/ADT/ScopeExit.h"
54 #include "llvm/ADT/SmallSet.h"
55 #include "llvm/ADT/StringExtras.h"
56 #include "llvm/ADT/StringRef.h"
57 #include "llvm/Support/Casting.h"
58 #include "llvm/Support/Error.h"
59 #include "llvm/Support/MathExtras.h"
60 #include "llvm/Support/Path.h"
61 #include "llvm/Support/raw_ostream.h"
62 
63 namespace clang {
64 namespace clangd {
65 namespace {
66 
67 // Returns the single definition of the entity declared by D, if visible.
68 // In particular:
69 // - for non-redeclarable kinds (e.g. local vars), return D
70 // - for kinds that allow multiple definitions (e.g. namespaces), return nullptr
71 // Kinds of nodes that always return nullptr here will not have definitions
72 // reported by locateSymbolAt().
getDefinition(const NamedDecl * D)73 const NamedDecl *getDefinition(const NamedDecl *D) {
74   assert(D);
75   // Decl has one definition that we can find.
76   if (const auto *TD = dyn_cast<TagDecl>(D))
77     return TD->getDefinition();
78   if (const auto *VD = dyn_cast<VarDecl>(D))
79     return VD->getDefinition();
80   if (const auto *FD = dyn_cast<FunctionDecl>(D))
81     return FD->getDefinition();
82   // Objective-C classes can have three types of declarations:
83   //
84   // - forward declaration: @class MyClass;
85   // - true declaration (interface definition): @interface MyClass ... @end
86   // - true definition (implementation): @implementation MyClass ... @end
87   //
88   // Objective-C categories are extensions are on classes:
89   //
90   // - declaration: @interface MyClass (Ext) ... @end
91   // - definition: @implementation MyClass (Ext) ... @end
92   //
93   // With one special case, a class extension, which is normally used to keep
94   // some declarations internal to a file without exposing them in a header.
95   //
96   // - class extension declaration: @interface MyClass () ... @end
97   // - which really links to class definition: @implementation MyClass ... @end
98   if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(D))
99     return ID->getImplementation();
100   if (const auto *CD = dyn_cast<ObjCCategoryDecl>(D)) {
101     if (CD->IsClassExtension()) {
102       if (const auto *ID = CD->getClassInterface())
103         return ID->getImplementation();
104       return nullptr;
105     }
106     return CD->getImplementation();
107   }
108   // Only a single declaration is allowed.
109   if (isa<ValueDecl>(D) || isa<TemplateTypeParmDecl>(D) ||
110       isa<TemplateTemplateParmDecl>(D)) // except cases above
111     return D;
112   // Multiple definitions are allowed.
113   return nullptr; // except cases above
114 }
115 
logIfOverflow(const SymbolLocation & Loc)116 void logIfOverflow(const SymbolLocation &Loc) {
117   if (Loc.Start.hasOverflow() || Loc.End.hasOverflow())
118     log("Possible overflow in symbol location: {0}", Loc);
119 }
120 
121 // Convert a SymbolLocation to LSP's Location.
122 // TUPath is used to resolve the path of URI.
123 // FIXME: figure out a good home for it, and share the implementation with
124 // FindSymbols.
toLSPLocation(const SymbolLocation & Loc,llvm::StringRef TUPath)125 llvm::Optional<Location> toLSPLocation(const SymbolLocation &Loc,
126                                        llvm::StringRef TUPath) {
127   if (!Loc)
128     return None;
129   auto Uri = URI::parse(Loc.FileURI);
130   if (!Uri) {
131     elog("Could not parse URI {0}: {1}", Loc.FileURI, Uri.takeError());
132     return None;
133   }
134   auto U = URIForFile::fromURI(*Uri, TUPath);
135   if (!U) {
136     elog("Could not resolve URI {0}: {1}", Loc.FileURI, U.takeError());
137     return None;
138   }
139 
140   Location LSPLoc;
141   LSPLoc.uri = std::move(*U);
142   LSPLoc.range.start.line = Loc.Start.line();
143   LSPLoc.range.start.character = Loc.Start.column();
144   LSPLoc.range.end.line = Loc.End.line();
145   LSPLoc.range.end.character = Loc.End.column();
146   logIfOverflow(Loc);
147   return LSPLoc;
148 }
149 
toIndexLocation(const Location & Loc,std::string & URIStorage)150 SymbolLocation toIndexLocation(const Location &Loc, std::string &URIStorage) {
151   SymbolLocation SymLoc;
152   URIStorage = Loc.uri.uri();
153   SymLoc.FileURI = URIStorage.c_str();
154   SymLoc.Start.setLine(Loc.range.start.line);
155   SymLoc.Start.setColumn(Loc.range.start.character);
156   SymLoc.End.setLine(Loc.range.end.line);
157   SymLoc.End.setColumn(Loc.range.end.character);
158   return SymLoc;
159 }
160 
161 // Returns the preferred location between an AST location and an index location.
getPreferredLocation(const Location & ASTLoc,const SymbolLocation & IdxLoc,std::string & Scratch)162 SymbolLocation getPreferredLocation(const Location &ASTLoc,
163                                     const SymbolLocation &IdxLoc,
164                                     std::string &Scratch) {
165   // Also use a dummy symbol for the index location so that other fields (e.g.
166   // definition) are not factored into the preference.
167   Symbol ASTSym, IdxSym;
168   ASTSym.ID = IdxSym.ID = SymbolID("dummy_id");
169   ASTSym.CanonicalDeclaration = toIndexLocation(ASTLoc, Scratch);
170   IdxSym.CanonicalDeclaration = IdxLoc;
171   auto Merged = mergeSymbol(ASTSym, IdxSym);
172   return Merged.CanonicalDeclaration;
173 }
174 
175 std::vector<std::pair<const NamedDecl *, DeclRelationSet>>
getDeclAtPositionWithRelations(ParsedAST & AST,SourceLocation Pos,DeclRelationSet Relations,ASTNodeKind * NodeKind=nullptr)176 getDeclAtPositionWithRelations(ParsedAST &AST, SourceLocation Pos,
177                                DeclRelationSet Relations,
178                                ASTNodeKind *NodeKind = nullptr) {
179   unsigned Offset = AST.getSourceManager().getDecomposedSpellingLoc(Pos).second;
180   std::vector<std::pair<const NamedDecl *, DeclRelationSet>> Result;
181   auto ResultFromTree = [&](SelectionTree ST) {
182     if (const SelectionTree::Node *N = ST.commonAncestor()) {
183       if (NodeKind)
184         *NodeKind = N->ASTNode.getNodeKind();
185       llvm::copy_if(allTargetDecls(N->ASTNode), std::back_inserter(Result),
186                     [&](auto &Entry) { return !(Entry.second & ~Relations); });
187     }
188     return !Result.empty();
189   };
190   SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset,
191                             Offset, ResultFromTree);
192   return Result;
193 }
194 
195 std::vector<const NamedDecl *>
getDeclAtPosition(ParsedAST & AST,SourceLocation Pos,DeclRelationSet Relations,ASTNodeKind * NodeKind=nullptr)196 getDeclAtPosition(ParsedAST &AST, SourceLocation Pos, DeclRelationSet Relations,
197                   ASTNodeKind *NodeKind = nullptr) {
198   std::vector<const NamedDecl *> Result;
199   for (auto &Entry :
200        getDeclAtPositionWithRelations(AST, Pos, Relations, NodeKind))
201     Result.push_back(Entry.first);
202   return Result;
203 }
204 
205 // Expects Loc to be a SpellingLocation, will bail out otherwise as it can't
206 // figure out a filename.
makeLocation(const ASTContext & AST,SourceLocation Loc,llvm::StringRef TUPath)207 llvm::Optional<Location> makeLocation(const ASTContext &AST, SourceLocation Loc,
208                                       llvm::StringRef TUPath) {
209   const auto &SM = AST.getSourceManager();
210   const FileEntry *F = SM.getFileEntryForID(SM.getFileID(Loc));
211   if (!F)
212     return None;
213   auto FilePath = getCanonicalPath(F, SM);
214   if (!FilePath) {
215     log("failed to get path!");
216     return None;
217   }
218   Location L;
219   L.uri = URIForFile::canonicalize(*FilePath, TUPath);
220   // We call MeasureTokenLength here as TokenBuffer doesn't store spelled tokens
221   // outside the main file.
222   auto TokLen = Lexer::MeasureTokenLength(Loc, SM, AST.getLangOpts());
223   L.range = halfOpenToRange(
224       SM, CharSourceRange::getCharRange(Loc, Loc.getLocWithOffset(TokLen)));
225   return L;
226 }
227 
228 // Treat #included files as symbols, to enable go-to-definition on them.
locateFileReferent(const Position & Pos,ParsedAST & AST,llvm::StringRef MainFilePath)229 llvm::Optional<LocatedSymbol> locateFileReferent(const Position &Pos,
230                                                  ParsedAST &AST,
231                                                  llvm::StringRef MainFilePath) {
232   for (auto &Inc : AST.getIncludeStructure().MainFileIncludes) {
233     if (!Inc.Resolved.empty() && Inc.HashLine == Pos.line) {
234       LocatedSymbol File;
235       File.Name = std::string(llvm::sys::path::filename(Inc.Resolved));
236       File.PreferredDeclaration = {
237           URIForFile::canonicalize(Inc.Resolved, MainFilePath), Range{}};
238       File.Definition = File.PreferredDeclaration;
239       // We're not going to find any further symbols on #include lines.
240       return File;
241     }
242   }
243   return llvm::None;
244 }
245 
246 // Macros are simple: there's no declaration/definition distinction.
247 // As a consequence, there's no need to look them up in the index either.
248 llvm::Optional<LocatedSymbol>
locateMacroReferent(const syntax::Token & TouchedIdentifier,ParsedAST & AST,llvm::StringRef MainFilePath)249 locateMacroReferent(const syntax::Token &TouchedIdentifier, ParsedAST &AST,
250                     llvm::StringRef MainFilePath) {
251   if (auto M = locateMacroAt(TouchedIdentifier, AST.getPreprocessor())) {
252     if (auto Loc =
253             makeLocation(AST.getASTContext(), M->NameLoc, MainFilePath)) {
254       LocatedSymbol Macro;
255       Macro.Name = std::string(M->Name);
256       Macro.PreferredDeclaration = *Loc;
257       Macro.Definition = Loc;
258       return Macro;
259     }
260   }
261   return llvm::None;
262 }
263 
264 // A wrapper around `Decl::getCanonicalDecl` to support cases where Clang's
265 // definition of a canonical declaration doesn't match up to what a programmer
266 // would expect. For example, Objective-C classes can have three types of
267 // declarations:
268 //
269 // - forward declaration(s): @class MyClass;
270 // - true declaration (interface definition): @interface MyClass ... @end
271 // - true definition (implementation): @implementation MyClass ... @end
272 //
273 // Clang will consider the forward declaration to be the canonical declaration
274 // because it is first. We actually want the class definition if it is
275 // available since that is what a programmer would consider the primary
276 // declaration to be.
getPreferredDecl(const NamedDecl * D)277 const NamedDecl *getPreferredDecl(const NamedDecl *D) {
278   // FIXME: Canonical declarations of some symbols might refer to built-in
279   // decls with possibly-invalid source locations (e.g. global new operator).
280   // In such cases we should pick up a redecl with valid source location
281   // instead of failing.
282   D = llvm::cast<NamedDecl>(D->getCanonicalDecl());
283 
284   // Prefer Objective-C class/protocol definitions over the forward declaration.
285   if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(D))
286     if (const auto *DefinitionID = ID->getDefinition())
287       return DefinitionID;
288   if (const auto *PD = dyn_cast<ObjCProtocolDecl>(D))
289     if (const auto *DefinitionID = PD->getDefinition())
290       return DefinitionID;
291 
292   return D;
293 }
294 
295 // Decls are more complicated.
296 // The AST contains at least a declaration, maybe a definition.
297 // These are up-to-date, and so generally preferred over index results.
298 // We perform a single batch index lookup to find additional definitions.
299 std::vector<LocatedSymbol>
locateASTReferent(SourceLocation CurLoc,const syntax::Token * TouchedIdentifier,ParsedAST & AST,llvm::StringRef MainFilePath,const SymbolIndex * Index,ASTNodeKind * NodeKind)300 locateASTReferent(SourceLocation CurLoc, const syntax::Token *TouchedIdentifier,
301                   ParsedAST &AST, llvm::StringRef MainFilePath,
302                   const SymbolIndex *Index, ASTNodeKind *NodeKind) {
303   const SourceManager &SM = AST.getSourceManager();
304   // Results follow the order of Symbols.Decls.
305   std::vector<LocatedSymbol> Result;
306   // Keep track of SymbolID -> index mapping, to fill in index data later.
307   llvm::DenseMap<SymbolID, size_t> ResultIndex;
308 
309   auto AddResultDecl = [&](const NamedDecl *D) {
310     D = getPreferredDecl(D);
311     auto Loc =
312         makeLocation(AST.getASTContext(), nameLocation(*D, SM), MainFilePath);
313     if (!Loc)
314       return;
315 
316     Result.emplace_back();
317     Result.back().Name = printName(AST.getASTContext(), *D);
318     Result.back().PreferredDeclaration = *Loc;
319     if (const NamedDecl *Def = getDefinition(D))
320       Result.back().Definition = makeLocation(
321           AST.getASTContext(), nameLocation(*Def, SM), MainFilePath);
322 
323     // Record SymbolID for index lookup later.
324     if (auto ID = getSymbolID(D))
325       ResultIndex[ID] = Result.size() - 1;
326   };
327 
328   // Emit all symbol locations (declaration or definition) from AST.
329   DeclRelationSet Relations =
330       DeclRelation::TemplatePattern | DeclRelation::Alias;
331   auto Candidates =
332       getDeclAtPositionWithRelations(AST, CurLoc, Relations, NodeKind);
333   for (const auto &E : Candidates) {
334     const NamedDecl *D = E.first;
335     // Special case: void foo() ^override: jump to the overridden method.
336     if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(D)) {
337       const InheritableAttr *Attr = D->getAttr<OverrideAttr>();
338       if (!Attr)
339         Attr = D->getAttr<FinalAttr>();
340       if (Attr && TouchedIdentifier &&
341           SM.getSpellingLoc(Attr->getLocation()) ==
342               TouchedIdentifier->location()) {
343         // We may be overridding multiple methods - offer them all.
344         for (const NamedDecl *ND : CMD->overridden_methods())
345           AddResultDecl(ND);
346         continue;
347       }
348     }
349 
350     // Special case: the cursor is on an alias, prefer other results.
351     // This targets "using ns::^Foo", where the target is more interesting.
352     // This does not trigger on renaming aliases:
353     //   `using Foo = ^Bar` already targets Bar via a TypeLoc
354     //   `using ^Foo = Bar` has no other results, as Underlying is filtered.
355     if (E.second & DeclRelation::Alias && Candidates.size() > 1 &&
356         // beginLoc/endLoc are a token range, so rewind the identifier we're in.
357         SM.isPointWithin(TouchedIdentifier ? TouchedIdentifier->location()
358                                            : CurLoc,
359                          D->getBeginLoc(), D->getEndLoc()))
360       continue;
361 
362     // Special case: the point of declaration of a template specialization,
363     // it's more useful to navigate to the template declaration.
364     if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(D)) {
365       if (TouchedIdentifier &&
366           D->getLocation() == TouchedIdentifier->location()) {
367         AddResultDecl(CTSD->getSpecializedTemplate());
368         continue;
369       }
370     }
371 
372     // Special case: if the class name is selected, also map Objective-C
373     // categories and category implementations back to their class interface.
374     //
375     // Since `TouchedIdentifier` might refer to the `ObjCCategoryImplDecl`
376     // instead of the `ObjCCategoryDecl` we intentionally check the contents
377     // of the locs when checking for class name equivalence.
378     if (const auto *CD = dyn_cast<ObjCCategoryDecl>(D))
379       if (const auto *ID = CD->getClassInterface())
380         if (TouchedIdentifier &&
381             (CD->getLocation() == TouchedIdentifier->location() ||
382              ID->getName() == TouchedIdentifier->text(SM)))
383           AddResultDecl(ID);
384 
385     // Otherwise the target declaration is the right one.
386     AddResultDecl(D);
387   }
388 
389   // Now query the index for all Symbol IDs we found in the AST.
390   if (Index && !ResultIndex.empty()) {
391     LookupRequest QueryRequest;
392     for (auto It : ResultIndex)
393       QueryRequest.IDs.insert(It.first);
394     std::string Scratch;
395     Index->lookup(QueryRequest, [&](const Symbol &Sym) {
396       auto &R = Result[ResultIndex.lookup(Sym.ID)];
397 
398       if (R.Definition) { // from AST
399         // Special case: if the AST yielded a definition, then it may not be
400         // the right *declaration*. Prefer the one from the index.
401         if (auto Loc = toLSPLocation(Sym.CanonicalDeclaration, MainFilePath))
402           R.PreferredDeclaration = *Loc;
403 
404         // We might still prefer the definition from the index, e.g. for
405         // generated symbols.
406         if (auto Loc = toLSPLocation(
407                 getPreferredLocation(*R.Definition, Sym.Definition, Scratch),
408                 MainFilePath))
409           R.Definition = *Loc;
410       } else {
411         R.Definition = toLSPLocation(Sym.Definition, MainFilePath);
412 
413         // Use merge logic to choose AST or index declaration.
414         if (auto Loc = toLSPLocation(
415                 getPreferredLocation(R.PreferredDeclaration,
416                                      Sym.CanonicalDeclaration, Scratch),
417                 MainFilePath))
418           R.PreferredDeclaration = *Loc;
419       }
420     });
421   }
422 
423   return Result;
424 }
425 
tokenSpelledAt(SourceLocation SpellingLoc,const syntax::TokenBuffer & TB)426 bool tokenSpelledAt(SourceLocation SpellingLoc, const syntax::TokenBuffer &TB) {
427   auto ExpandedTokens = TB.expandedTokens(
428       TB.sourceManager().getMacroArgExpandedLocation(SpellingLoc));
429   return !ExpandedTokens.empty();
430 }
431 
sourcePrefix(SourceLocation Loc,const SourceManager & SM)432 llvm::StringRef sourcePrefix(SourceLocation Loc, const SourceManager &SM) {
433   auto D = SM.getDecomposedLoc(Loc);
434   bool Invalid = false;
435   llvm::StringRef Buf = SM.getBufferData(D.first, &Invalid);
436   if (Invalid || D.second > Buf.size())
437     return "";
438   return Buf.substr(0, D.second);
439 }
440 
isDependentName(ASTNodeKind NodeKind)441 bool isDependentName(ASTNodeKind NodeKind) {
442   return NodeKind.isSame(ASTNodeKind::getFromNodeKind<OverloadExpr>()) ||
443          NodeKind.isSame(
444              ASTNodeKind::getFromNodeKind<CXXDependentScopeMemberExpr>()) ||
445          NodeKind.isSame(
446              ASTNodeKind::getFromNodeKind<DependentScopeDeclRefExpr>());
447 }
448 
449 } // namespace
450 
451 std::vector<LocatedSymbol>
locateSymbolTextually(const SpelledWord & Word,ParsedAST & AST,const SymbolIndex * Index,const std::string & MainFilePath,ASTNodeKind NodeKind)452 locateSymbolTextually(const SpelledWord &Word, ParsedAST &AST,
453                       const SymbolIndex *Index, const std::string &MainFilePath,
454                       ASTNodeKind NodeKind) {
455   // Don't use heuristics if this is a real identifier, or not an
456   // identifier.
457   // Exception: dependent names, because those may have useful textual
458   // matches that AST-based heuristics cannot find.
459   if ((Word.ExpandedToken && !isDependentName(NodeKind)) ||
460       !Word.LikelyIdentifier || !Index)
461     return {};
462   // We don't want to handle words in string literals. (It'd be nice to list
463   // *allowed* token kinds explicitly, but comment Tokens aren't retained).
464   if (Word.PartOfSpelledToken &&
465       isStringLiteral(Word.PartOfSpelledToken->kind()))
466     return {};
467 
468   const auto &SM = AST.getSourceManager();
469   // Look up the selected word in the index.
470   FuzzyFindRequest Req;
471   Req.Query = Word.Text.str();
472   Req.ProximityPaths = {MainFilePath};
473   // Find the namespaces to query by lexing the file.
474   Req.Scopes =
475       visibleNamespaces(sourcePrefix(Word.Location, SM), AST.getLangOpts());
476   // FIXME: For extra strictness, consider AnyScope=false.
477   Req.AnyScope = true;
478   // We limit the results to 3 further below. This limit is to avoid fetching
479   // too much data, while still likely having enough for 3 results to remain
480   // after additional filtering.
481   Req.Limit = 10;
482   bool TooMany = false;
483   using ScoredLocatedSymbol = std::pair<float, LocatedSymbol>;
484   std::vector<ScoredLocatedSymbol> ScoredResults;
485   Index->fuzzyFind(Req, [&](const Symbol &Sym) {
486     // Only consider exact name matches, including case.
487     // This is to avoid too many false positives.
488     // We could relax this in the future (e.g. to allow for typos) if we make
489     // the query more accurate by other means.
490     if (Sym.Name != Word.Text)
491       return;
492 
493     // Exclude constructor results. They have the same name as the class,
494     // but we don't have enough context to prefer them over the class.
495     if (Sym.SymInfo.Kind == index::SymbolKind::Constructor)
496       return;
497 
498     auto MaybeDeclLoc =
499         indexToLSPLocation(Sym.CanonicalDeclaration, MainFilePath);
500     if (!MaybeDeclLoc) {
501       log("locateSymbolNamedTextuallyAt: {0}", MaybeDeclLoc.takeError());
502       return;
503     }
504     LocatedSymbol Located;
505     Located.PreferredDeclaration = *MaybeDeclLoc;
506     Located.Name = (Sym.Name + Sym.TemplateSpecializationArgs).str();
507     if (Sym.Definition) {
508       auto MaybeDefLoc = indexToLSPLocation(Sym.Definition, MainFilePath);
509       if (!MaybeDefLoc) {
510         log("locateSymbolNamedTextuallyAt: {0}", MaybeDefLoc.takeError());
511         return;
512       }
513       Located.PreferredDeclaration = *MaybeDefLoc;
514       Located.Definition = *MaybeDefLoc;
515     }
516 
517     if (ScoredResults.size() >= 5) {
518       // If we have more than 5 results, don't return anything,
519       // as confidence is too low.
520       // FIXME: Alternatively, try a stricter query?
521       TooMany = true;
522       return;
523     }
524 
525     SymbolQualitySignals Quality;
526     Quality.merge(Sym);
527     SymbolRelevanceSignals Relevance;
528     Relevance.Name = Sym.Name;
529     Relevance.Query = SymbolRelevanceSignals::Generic;
530     Relevance.merge(Sym);
531     auto Score = evaluateSymbolAndRelevance(Quality.evaluateHeuristics(),
532                                             Relevance.evaluateHeuristics());
533     dlog("locateSymbolNamedTextuallyAt: {0}{1} = {2}\n{3}{4}\n", Sym.Scope,
534          Sym.Name, Score, Quality, Relevance);
535 
536     ScoredResults.push_back({Score, std::move(Located)});
537   });
538 
539   if (TooMany) {
540     vlog("Heuristic index lookup for {0} returned too many candidates, ignored",
541          Word.Text);
542     return {};
543   }
544 
545   llvm::sort(ScoredResults,
546              [](const ScoredLocatedSymbol &A, const ScoredLocatedSymbol &B) {
547                return A.first > B.first;
548              });
549   std::vector<LocatedSymbol> Results;
550   for (auto &Res : std::move(ScoredResults))
551     Results.push_back(std::move(Res.second));
552   if (Results.empty())
553     vlog("No heuristic index definition for {0}", Word.Text);
554   else
555     log("Found definition heuristically in index for {0}", Word.Text);
556   return Results;
557 }
558 
findNearbyIdentifier(const SpelledWord & Word,const syntax::TokenBuffer & TB)559 const syntax::Token *findNearbyIdentifier(const SpelledWord &Word,
560                                           const syntax::TokenBuffer &TB) {
561   // Don't use heuristics if this is a real identifier.
562   // Unlikely identifiers are OK if they were used as identifiers nearby.
563   if (Word.ExpandedToken)
564     return nullptr;
565   // We don't want to handle words in string literals. (It'd be nice to list
566   // *allowed* token kinds explicitly, but comment Tokens aren't retained).
567   if (Word.PartOfSpelledToken &&
568       isStringLiteral(Word.PartOfSpelledToken->kind()))
569     return {};
570 
571   const SourceManager &SM = TB.sourceManager();
572   // We prefer the closest possible token, line-wise. Backwards is penalized.
573   // Ties are implicitly broken by traversal order (first-one-wins).
574   auto File = SM.getFileID(Word.Location);
575   unsigned WordLine = SM.getSpellingLineNumber(Word.Location);
576   auto Cost = [&](SourceLocation Loc) -> unsigned {
577     assert(SM.getFileID(Loc) == File && "spelled token in wrong file?");
578     unsigned Line = SM.getSpellingLineNumber(Loc);
579     return Line >= WordLine ? Line - WordLine : 2 * (WordLine - Line);
580   };
581   const syntax::Token *BestTok = nullptr;
582   unsigned BestCost = -1;
583   // Search bounds are based on word length:
584   // - forward: 2^N lines
585   // - backward: 2^(N-1) lines.
586   unsigned MaxDistance =
587       1U << std::min<unsigned>(Word.Text.size(),
588                                std::numeric_limits<unsigned>::digits - 1);
589   // Line number for SM.translateLineCol() should be one-based, also
590   // SM.translateLineCol() can handle line number greater than
591   // number of lines in the file.
592   // - LineMin = max(1, WordLine + 1 - 2^(N-1))
593   // - LineMax = WordLine + 1 + 2^N
594   unsigned LineMin =
595       WordLine + 1 <= MaxDistance / 2 ? 1 : WordLine + 1 - MaxDistance / 2;
596   unsigned LineMax = WordLine + 1 + MaxDistance;
597   SourceLocation LocMin = SM.translateLineCol(File, LineMin, 1);
598   assert(LocMin.isValid());
599   SourceLocation LocMax = SM.translateLineCol(File, LineMax, 1);
600   assert(LocMax.isValid());
601 
602   // Updates BestTok and BestCost if Tok is a good candidate.
603   // May return true if the cost is too high for this token.
604   auto Consider = [&](const syntax::Token &Tok) {
605     if (Tok.location() < LocMin || Tok.location() > LocMax)
606       return true; // we are too far from the word, break the outer loop.
607     if (!(Tok.kind() == tok::identifier && Tok.text(SM) == Word.Text))
608       return false;
609     // No point guessing the same location we started with.
610     if (Tok.location() == Word.Location)
611       return false;
612     // We've done cheap checks, compute cost so we can break the caller's loop.
613     unsigned TokCost = Cost(Tok.location());
614     if (TokCost >= BestCost)
615       return true; // causes the outer loop to break.
616     // Allow locations that might be part of the AST, and macros (even if empty)
617     // but not things like disabled preprocessor sections.
618     if (!(tokenSpelledAt(Tok.location(), TB) || TB.expansionStartingAt(&Tok)))
619       return false;
620     // We already verified this token is an improvement.
621     BestCost = TokCost;
622     BestTok = &Tok;
623     return false;
624   };
625   auto SpelledTokens = TB.spelledTokens(File);
626   // Find where the word occurred in the token stream, to search forward & back.
627   auto *I = llvm::partition_point(SpelledTokens, [&](const syntax::Token &T) {
628     assert(SM.getFileID(T.location()) == SM.getFileID(Word.Location));
629     return T.location() < Word.Location; // Comparison OK: same file.
630   });
631   // Search for matches after the cursor.
632   for (const syntax::Token &Tok : llvm::makeArrayRef(I, SpelledTokens.end()))
633     if (Consider(Tok))
634       break; // costs of later tokens are greater...
635   // Search for matches before the cursor.
636   for (const syntax::Token &Tok :
637        llvm::reverse(llvm::makeArrayRef(SpelledTokens.begin(), I)))
638     if (Consider(Tok))
639       break;
640 
641   if (BestTok)
642     vlog(
643         "Word {0} under cursor {1} isn't a token (after PP), trying nearby {2}",
644         Word.Text, Word.Location.printToString(SM),
645         BestTok->location().printToString(SM));
646 
647   return BestTok;
648 }
649 
locateSymbolAt(ParsedAST & AST,Position Pos,const SymbolIndex * Index)650 std::vector<LocatedSymbol> locateSymbolAt(ParsedAST &AST, Position Pos,
651                                           const SymbolIndex *Index) {
652   const auto &SM = AST.getSourceManager();
653   auto MainFilePath =
654       getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
655   if (!MainFilePath) {
656     elog("Failed to get a path for the main file, so no references");
657     return {};
658   }
659 
660   if (auto File = locateFileReferent(Pos, AST, *MainFilePath))
661     return {std::move(*File)};
662 
663   auto CurLoc = sourceLocationInMainFile(SM, Pos);
664   if (!CurLoc) {
665     elog("locateSymbolAt failed to convert position to source location: {0}",
666          CurLoc.takeError());
667     return {};
668   }
669 
670   const syntax::Token *TouchedIdentifier =
671       syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens());
672   if (TouchedIdentifier)
673     if (auto Macro =
674             locateMacroReferent(*TouchedIdentifier, AST, *MainFilePath))
675       // Don't look at the AST or index if we have a macro result.
676       // (We'd just return declarations referenced from the macro's
677       // expansion.)
678       return {*std::move(Macro)};
679 
680   ASTNodeKind NodeKind;
681   auto ASTResults = locateASTReferent(*CurLoc, TouchedIdentifier, AST,
682                                       *MainFilePath, Index, &NodeKind);
683   if (!ASTResults.empty())
684     return ASTResults;
685 
686   // If the cursor can't be resolved directly, try fallback strategies.
687   auto Word =
688       SpelledWord::touching(*CurLoc, AST.getTokens(), AST.getLangOpts());
689   if (Word) {
690     // Is the same word nearby a real identifier that might refer to something?
691     if (const syntax::Token *NearbyIdent =
692             findNearbyIdentifier(*Word, AST.getTokens())) {
693       if (auto Macro = locateMacroReferent(*NearbyIdent, AST, *MainFilePath)) {
694         log("Found macro definition heuristically using nearby identifier {0}",
695             Word->Text);
696         return {*std::move(Macro)};
697       }
698       ASTResults =
699           locateASTReferent(NearbyIdent->location(), NearbyIdent, AST,
700                             *MainFilePath, Index, /*NodeKind=*/nullptr);
701       if (!ASTResults.empty()) {
702         log("Found definition heuristically using nearby identifier {0}",
703             NearbyIdent->text(SM));
704         return ASTResults;
705       } else {
706         vlog("No definition found using nearby identifier {0} at {1}",
707              Word->Text, Word->Location.printToString(SM));
708       }
709     }
710     // No nearby word, or it didn't refer to anything either. Try the index.
711     auto TextualResults =
712         locateSymbolTextually(*Word, AST, Index, *MainFilePath, NodeKind);
713     if (!TextualResults.empty())
714       return TextualResults;
715   }
716 
717   return {};
718 }
719 
getDocumentLinks(ParsedAST & AST)720 std::vector<DocumentLink> getDocumentLinks(ParsedAST &AST) {
721   const auto &SM = AST.getSourceManager();
722   auto MainFilePath =
723       getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
724   if (!MainFilePath) {
725     elog("Failed to get a path for the main file, so no links");
726     return {};
727   }
728 
729   std::vector<DocumentLink> Result;
730   for (auto &Inc : AST.getIncludeStructure().MainFileIncludes) {
731     if (Inc.Resolved.empty())
732       continue;
733     auto HashLoc = SM.getComposedLoc(SM.getMainFileID(), Inc.HashOffset);
734     const auto *HashTok = AST.getTokens().spelledTokenAt(HashLoc);
735     assert(HashTok && "got inclusion at wrong offset");
736     const auto *IncludeTok = std::next(HashTok);
737     const auto *FileTok = std::next(IncludeTok);
738     // FileTok->range is not sufficient here, as raw lexing wouldn't yield
739     // correct tokens for angled filenames. Hence we explicitly use
740     // Inc.Written's length.
741     auto FileRange =
742         syntax::FileRange(SM, FileTok->location(), Inc.Written.length())
743             .toCharRange(SM);
744 
745     Result.push_back(
746         DocumentLink({halfOpenToRange(SM, FileRange),
747                       URIForFile::canonicalize(Inc.Resolved, *MainFilePath)}));
748   }
749 
750   return Result;
751 }
752 
753 namespace {
754 
755 /// Collects references to symbols within the main file.
756 class ReferenceFinder : public index::IndexDataConsumer {
757 public:
758   struct Reference {
759     syntax::Token SpelledTok;
760     index::SymbolRoleSet Role;
761 
rangeclang::clangd::__anon7033247a0b11::ReferenceFinder::Reference762     Range range(const SourceManager &SM) const {
763       return halfOpenToRange(SM, SpelledTok.range(SM).toCharRange(SM));
764     }
765   };
766 
ReferenceFinder(const ParsedAST & AST,const std::vector<const NamedDecl * > & TargetDecls)767   ReferenceFinder(const ParsedAST &AST,
768                   const std::vector<const NamedDecl *> &TargetDecls)
769       : AST(AST) {
770     for (const NamedDecl *D : TargetDecls)
771       CanonicalTargets.insert(D->getCanonicalDecl());
772   }
773 
take()774   std::vector<Reference> take() && {
775     llvm::sort(References, [](const Reference &L, const Reference &R) {
776       auto LTok = L.SpelledTok.location();
777       auto RTok = R.SpelledTok.location();
778       return std::tie(LTok, L.Role) < std::tie(RTok, R.Role);
779     });
780     // We sometimes see duplicates when parts of the AST get traversed twice.
781     References.erase(std::unique(References.begin(), References.end(),
782                                  [](const Reference &L, const Reference &R) {
783                                    auto LTok = L.SpelledTok.location();
784                                    auto RTok = R.SpelledTok.location();
785                                    return std::tie(LTok, L.Role) ==
786                                           std::tie(RTok, R.Role);
787                                  }),
788                      References.end());
789     return std::move(References);
790   }
791 
792   bool
handleDeclOccurrence(const Decl * D,index::SymbolRoleSet Roles,llvm::ArrayRef<index::SymbolRelation> Relations,SourceLocation Loc,index::IndexDataConsumer::ASTNodeInfo ASTNode)793   handleDeclOccurrence(const Decl *D, index::SymbolRoleSet Roles,
794                        llvm::ArrayRef<index::SymbolRelation> Relations,
795                        SourceLocation Loc,
796                        index::IndexDataConsumer::ASTNodeInfo ASTNode) override {
797     assert(D->isCanonicalDecl() && "expect D to be a canonical declaration");
798     const SourceManager &SM = AST.getSourceManager();
799     if (!CanonicalTargets.count(D) || !isInsideMainFile(Loc, SM))
800       return true;
801     const auto &TB = AST.getTokens();
802     Loc = SM.getFileLoc(Loc);
803     if (const auto *Tok = TB.spelledTokenAt(Loc))
804       References.push_back({*Tok, Roles});
805     return true;
806   }
807 
808 private:
809   llvm::SmallSet<const Decl *, 4> CanonicalTargets;
810   std::vector<Reference> References;
811   const ParsedAST &AST;
812 };
813 
814 std::vector<ReferenceFinder::Reference>
findRefs(const std::vector<const NamedDecl * > & Decls,ParsedAST & AST)815 findRefs(const std::vector<const NamedDecl *> &Decls, ParsedAST &AST) {
816   ReferenceFinder RefFinder(AST, Decls);
817   index::IndexingOptions IndexOpts;
818   IndexOpts.SystemSymbolFilter =
819       index::IndexingOptions::SystemSymbolFilterKind::All;
820   IndexOpts.IndexFunctionLocals = true;
821   IndexOpts.IndexParametersInDeclarations = true;
822   IndexOpts.IndexTemplateParameters = true;
823   indexTopLevelDecls(AST.getASTContext(), AST.getPreprocessor(),
824                      AST.getLocalTopLevelDecls(), RefFinder, IndexOpts);
825   return std::move(RefFinder).take();
826 }
827 
getFunctionBody(DynTypedNode N)828 const Stmt *getFunctionBody(DynTypedNode N) {
829   if (const auto *FD = N.get<FunctionDecl>())
830     return FD->getBody();
831   if (const auto *FD = N.get<BlockDecl>())
832     return FD->getBody();
833   if (const auto *FD = N.get<LambdaExpr>())
834     return FD->getBody();
835   if (const auto *FD = N.get<ObjCMethodDecl>())
836     return FD->getBody();
837   return nullptr;
838 }
839 
getLoopBody(DynTypedNode N)840 const Stmt *getLoopBody(DynTypedNode N) {
841   if (const auto *LS = N.get<ForStmt>())
842     return LS->getBody();
843   if (const auto *LS = N.get<CXXForRangeStmt>())
844     return LS->getBody();
845   if (const auto *LS = N.get<WhileStmt>())
846     return LS->getBody();
847   if (const auto *LS = N.get<DoStmt>())
848     return LS->getBody();
849   return nullptr;
850 }
851 
852 // AST traversal to highlight control flow statements under some root.
853 // Once we hit further control flow we prune the tree (or at least restrict
854 // what we highlight) so we capture e.g. breaks from the outer loop only.
855 class FindControlFlow : public RecursiveASTVisitor<FindControlFlow> {
856   // Types of control-flow statements we might highlight.
857   enum Target {
858     Break = 1,
859     Continue = 2,
860     Return = 4,
861     Case = 8,
862     Throw = 16,
863     Goto = 32,
864     All = Break | Continue | Return | Case | Throw | Goto,
865   };
866   int Ignore = 0;     // bitmask of Target - what are we *not* highlighting?
867   SourceRange Bounds; // Half-open, restricts reported targets.
868   std::vector<SourceLocation> &Result;
869   const SourceManager &SM;
870 
871   // Masks out targets for a traversal into D.
872   // Traverses the subtree using Delegate() if any targets remain.
873   template <typename Func>
filterAndTraverse(DynTypedNode D,const Func & Delegate)874   bool filterAndTraverse(DynTypedNode D, const Func &Delegate) {
875     auto RestoreIgnore = llvm::make_scope_exit(
876         [OldIgnore(Ignore), this] { Ignore = OldIgnore; });
877     if (getFunctionBody(D))
878       Ignore = All;
879     else if (getLoopBody(D))
880       Ignore |= Continue | Break;
881     else if (D.get<SwitchStmt>())
882       Ignore |= Break | Case;
883     // Prune tree if we're not looking for anything.
884     return (Ignore == All) ? true : Delegate();
885   }
886 
found(Target T,SourceLocation Loc)887   void found(Target T, SourceLocation Loc) {
888     if (T & Ignore)
889       return;
890     if (SM.isBeforeInTranslationUnit(Loc, Bounds.getBegin()) ||
891         SM.isBeforeInTranslationUnit(Bounds.getEnd(), Loc))
892       return;
893     Result.push_back(Loc);
894   }
895 
896 public:
FindControlFlow(SourceRange Bounds,std::vector<SourceLocation> & Result,const SourceManager & SM)897   FindControlFlow(SourceRange Bounds, std::vector<SourceLocation> &Result,
898                   const SourceManager &SM)
899       : Bounds(Bounds), Result(Result), SM(SM) {}
900 
901   // When traversing function or loops, limit targets to those that still
902   // refer to the original root.
TraverseDecl(Decl * D)903   bool TraverseDecl(Decl *D) {
904     return !D || filterAndTraverse(DynTypedNode::create(*D), [&] {
905       return RecursiveASTVisitor::TraverseDecl(D);
906     });
907   }
TraverseStmt(Stmt * S)908   bool TraverseStmt(Stmt *S) {
909     return !S || filterAndTraverse(DynTypedNode::create(*S), [&] {
910       return RecursiveASTVisitor::TraverseStmt(S);
911     });
912   }
913 
914   // Add leaves that we found and want.
VisitReturnStmt(ReturnStmt * R)915   bool VisitReturnStmt(ReturnStmt *R) {
916     found(Return, R->getReturnLoc());
917     return true;
918   }
VisitBreakStmt(BreakStmt * B)919   bool VisitBreakStmt(BreakStmt *B) {
920     found(Break, B->getBreakLoc());
921     return true;
922   }
VisitContinueStmt(ContinueStmt * C)923   bool VisitContinueStmt(ContinueStmt *C) {
924     found(Continue, C->getContinueLoc());
925     return true;
926   }
VisitSwitchCase(SwitchCase * C)927   bool VisitSwitchCase(SwitchCase *C) {
928     found(Case, C->getKeywordLoc());
929     return true;
930   }
VisitCXXThrowExpr(CXXThrowExpr * T)931   bool VisitCXXThrowExpr(CXXThrowExpr *T) {
932     found(Throw, T->getThrowLoc());
933     return true;
934   }
VisitGotoStmt(GotoStmt * G)935   bool VisitGotoStmt(GotoStmt *G) {
936     // Goto is interesting if its target is outside the root.
937     if (const auto *LD = G->getLabel()) {
938       if (SM.isBeforeInTranslationUnit(LD->getLocation(), Bounds.getBegin()) ||
939           SM.isBeforeInTranslationUnit(Bounds.getEnd(), LD->getLocation()))
940         found(Goto, G->getGotoLoc());
941     }
942     return true;
943   }
944 };
945 
946 // Given a location within a switch statement, return the half-open range that
947 // covers the case it's contained in.
948 // We treat `case X: case Y: ...` as one case, and assume no other fallthrough.
findCaseBounds(const SwitchStmt & Switch,SourceLocation Loc,const SourceManager & SM)949 SourceRange findCaseBounds(const SwitchStmt &Switch, SourceLocation Loc,
950                            const SourceManager &SM) {
951   // Cases are not stored in order, sort them first.
952   // (In fact they seem to be stored in reverse order, don't rely on this)
953   std::vector<const SwitchCase *> Cases;
954   for (const SwitchCase *Case = Switch.getSwitchCaseList(); Case;
955        Case = Case->getNextSwitchCase())
956     Cases.push_back(Case);
957   llvm::sort(Cases, [&](const SwitchCase *L, const SwitchCase *R) {
958     return SM.isBeforeInTranslationUnit(L->getKeywordLoc(), R->getKeywordLoc());
959   });
960 
961   // Find the first case after the target location, the end of our range.
962   auto CaseAfter = llvm::partition_point(Cases, [&](const SwitchCase *C) {
963     return !SM.isBeforeInTranslationUnit(Loc, C->getKeywordLoc());
964   });
965   SourceLocation End = CaseAfter == Cases.end() ? Switch.getEndLoc()
966                                                 : (*CaseAfter)->getKeywordLoc();
967 
968   // Our target can be before the first case - cases are optional!
969   if (CaseAfter == Cases.begin())
970     return SourceRange(Switch.getBeginLoc(), End);
971   // The start of our range is usually the previous case, but...
972   auto CaseBefore = std::prev(CaseAfter);
973   // ... rewind CaseBefore to the first in a `case A: case B: ...` sequence.
974   while (CaseBefore != Cases.begin() &&
975          (*std::prev(CaseBefore))->getSubStmt() == *CaseBefore)
976     --CaseBefore;
977   return SourceRange((*CaseBefore)->getKeywordLoc(), End);
978 }
979 
980 // Returns the locations of control flow statements related to N. e.g.:
981 //   for    => branches: break/continue/return/throw
982 //   break  => controlling loop (forwhile/do), and its related control flow
983 //   return => all returns/throws from the same function
984 // When an inner block is selected, we include branches bound to outer blocks
985 // as these are exits from the inner block. e.g. return in a for loop.
986 // FIXME: We don't analyze catch blocks, throw is treated the same as return.
relatedControlFlow(const SelectionTree::Node & N)987 std::vector<SourceLocation> relatedControlFlow(const SelectionTree::Node &N) {
988   const SourceManager &SM =
989       N.getDeclContext().getParentASTContext().getSourceManager();
990   std::vector<SourceLocation> Result;
991 
992   // First, check if we're at a node that can resolve to a root.
993   enum class Cur { None, Break, Continue, Return, Case, Throw } Cursor;
994   if (N.ASTNode.get<BreakStmt>()) {
995     Cursor = Cur::Break;
996   } else if (N.ASTNode.get<ContinueStmt>()) {
997     Cursor = Cur::Continue;
998   } else if (N.ASTNode.get<ReturnStmt>()) {
999     Cursor = Cur::Return;
1000   } else if (N.ASTNode.get<CXXThrowExpr>()) {
1001     Cursor = Cur::Throw;
1002   } else if (N.ASTNode.get<SwitchCase>()) {
1003     Cursor = Cur::Case;
1004   } else if (const GotoStmt *GS = N.ASTNode.get<GotoStmt>()) {
1005     // We don't know what root to associate with, but highlight the goto/label.
1006     Result.push_back(GS->getGotoLoc());
1007     if (const auto *LD = GS->getLabel())
1008       Result.push_back(LD->getLocation());
1009     Cursor = Cur::None;
1010   } else {
1011     Cursor = Cur::None;
1012   }
1013 
1014   const Stmt *Root = nullptr; // Loop or function body to traverse.
1015   SourceRange Bounds;
1016   // Look up the tree for a root (or just at this node if we didn't find a leaf)
1017   for (const auto *P = &N; P; P = P->Parent) {
1018     // return associates with enclosing function
1019     if (const Stmt *FunctionBody = getFunctionBody(P->ASTNode)) {
1020       if (Cursor == Cur::Return || Cursor == Cur::Throw) {
1021         Root = FunctionBody;
1022       }
1023       break; // other leaves don't cross functions.
1024     }
1025     // break/continue associate with enclosing loop.
1026     if (const Stmt *LoopBody = getLoopBody(P->ASTNode)) {
1027       if (Cursor == Cur::None || Cursor == Cur::Break ||
1028           Cursor == Cur::Continue) {
1029         Root = LoopBody;
1030         // Highlight the loop keyword itself.
1031         // FIXME: for do-while, this only covers the `do`..
1032         Result.push_back(P->ASTNode.getSourceRange().getBegin());
1033         break;
1034       }
1035     }
1036     // For switches, users think of case statements as control flow blocks.
1037     // We highlight only occurrences surrounded by the same case.
1038     // We don't detect fallthrough (other than 'case X, case Y').
1039     if (const auto *SS = P->ASTNode.get<SwitchStmt>()) {
1040       if (Cursor == Cur::Break || Cursor == Cur::Case) {
1041         Result.push_back(SS->getSwitchLoc()); // Highlight the switch.
1042         Root = SS->getBody();
1043         // Limit to enclosing case, if there is one.
1044         Bounds = findCaseBounds(*SS, N.ASTNode.getSourceRange().getBegin(), SM);
1045         break;
1046       }
1047     }
1048     // If we didn't start at some interesting node, we're done.
1049     if (Cursor == Cur::None)
1050       break;
1051   }
1052   if (Root) {
1053     if (!Bounds.isValid())
1054       Bounds = Root->getSourceRange();
1055     FindControlFlow(Bounds, Result, SM).TraverseStmt(const_cast<Stmt *>(Root));
1056   }
1057   return Result;
1058 }
1059 
toHighlight(const ReferenceFinder::Reference & Ref,const SourceManager & SM)1060 DocumentHighlight toHighlight(const ReferenceFinder::Reference &Ref,
1061                               const SourceManager &SM) {
1062   DocumentHighlight DH;
1063   DH.range = Ref.range(SM);
1064   if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Write))
1065     DH.kind = DocumentHighlightKind::Write;
1066   else if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Read))
1067     DH.kind = DocumentHighlightKind::Read;
1068   else
1069     DH.kind = DocumentHighlightKind::Text;
1070   return DH;
1071 }
1072 
toHighlight(SourceLocation Loc,const syntax::TokenBuffer & TB)1073 llvm::Optional<DocumentHighlight> toHighlight(SourceLocation Loc,
1074                                               const syntax::TokenBuffer &TB) {
1075   Loc = TB.sourceManager().getFileLoc(Loc);
1076   if (const auto *Tok = TB.spelledTokenAt(Loc)) {
1077     DocumentHighlight Result;
1078     Result.range = halfOpenToRange(
1079         TB.sourceManager(),
1080         CharSourceRange::getCharRange(Tok->location(), Tok->endLocation()));
1081     return Result;
1082   }
1083   return llvm::None;
1084 }
1085 
1086 } // namespace
1087 
findDocumentHighlights(ParsedAST & AST,Position Pos)1088 std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,
1089                                                       Position Pos) {
1090   const SourceManager &SM = AST.getSourceManager();
1091   // FIXME: show references to macro within file?
1092   auto CurLoc = sourceLocationInMainFile(SM, Pos);
1093   if (!CurLoc) {
1094     llvm::consumeError(CurLoc.takeError());
1095     return {};
1096   }
1097   std::vector<DocumentHighlight> Result;
1098   auto TryTree = [&](SelectionTree ST) {
1099     if (const SelectionTree::Node *N = ST.commonAncestor()) {
1100       DeclRelationSet Relations =
1101           DeclRelation::TemplatePattern | DeclRelation::Alias;
1102       auto Decls = targetDecl(N->ASTNode, Relations);
1103       if (!Decls.empty()) {
1104         // FIXME: we may get multiple DocumentHighlights with the same location
1105         // and different kinds, deduplicate them.
1106         for (const auto &Ref : findRefs({Decls.begin(), Decls.end()}, AST))
1107           Result.push_back(toHighlight(Ref, SM));
1108         return true;
1109       }
1110       auto ControlFlow = relatedControlFlow(*N);
1111       if (!ControlFlow.empty()) {
1112         for (SourceLocation Loc : ControlFlow)
1113           if (auto Highlight = toHighlight(Loc, AST.getTokens()))
1114             Result.push_back(std::move(*Highlight));
1115         return true;
1116       }
1117     }
1118     return false;
1119   };
1120 
1121   unsigned Offset =
1122       AST.getSourceManager().getDecomposedSpellingLoc(*CurLoc).second;
1123   SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset,
1124                             Offset, TryTree);
1125   return Result;
1126 }
1127 
findImplementations(ParsedAST & AST,Position Pos,const SymbolIndex * Index)1128 std::vector<LocatedSymbol> findImplementations(ParsedAST &AST, Position Pos,
1129                                                const SymbolIndex *Index) {
1130   // We rely on index to find the implementations in subclasses.
1131   // FIXME: Index can be stale, so we may loose some latest results from the
1132   // main file.
1133   if (!Index)
1134     return {};
1135   const SourceManager &SM = AST.getSourceManager();
1136   auto MainFilePath =
1137       getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
1138   if (!MainFilePath) {
1139     elog("Failed to get a path for the main file, so no implementations.");
1140     return {};
1141   }
1142   auto CurLoc = sourceLocationInMainFile(SM, Pos);
1143   if (!CurLoc) {
1144     elog("Failed to convert position to source location: {0}",
1145          CurLoc.takeError());
1146     return {};
1147   }
1148   std::vector<LocatedSymbol> Results;
1149   DeclRelationSet Relations =
1150       DeclRelation::TemplatePattern | DeclRelation::Alias;
1151   RelationsRequest Req;
1152   Req.Predicate = RelationKind::OverriddenBy;
1153   for (const NamedDecl *ND : getDeclAtPosition(AST, *CurLoc, Relations))
1154     if (const CXXMethodDecl *CXXMD = llvm::dyn_cast<CXXMethodDecl>(ND))
1155       if (CXXMD->isVirtual())
1156         Req.Subjects.insert(getSymbolID(ND));
1157 
1158   if (Req.Subjects.empty())
1159     return Results;
1160   Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
1161     auto DeclLoc =
1162         indexToLSPLocation(Object.CanonicalDeclaration, *MainFilePath);
1163     if (!DeclLoc) {
1164       elog("Find implementation: {0}", DeclLoc.takeError());
1165       return;
1166     }
1167     LocatedSymbol Loc;
1168     Loc.Name = Object.Name.str();
1169     Loc.PreferredDeclaration = *DeclLoc;
1170     auto DefLoc = indexToLSPLocation(Object.Definition, *MainFilePath);
1171     if (DefLoc)
1172       Loc.Definition = *DefLoc;
1173     else
1174       llvm::consumeError(DefLoc.takeError());
1175     Results.push_back(Loc);
1176   });
1177   return Results;
1178 }
1179 
findReferences(ParsedAST & AST,Position Pos,uint32_t Limit,const SymbolIndex * Index)1180 ReferencesResult findReferences(ParsedAST &AST, Position Pos, uint32_t Limit,
1181                                 const SymbolIndex *Index) {
1182   if (!Limit)
1183     Limit = std::numeric_limits<uint32_t>::max();
1184   ReferencesResult Results;
1185   const SourceManager &SM = AST.getSourceManager();
1186   auto MainFilePath =
1187       getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
1188   if (!MainFilePath) {
1189     elog("Failed to get a path for the main file, so no references");
1190     return Results;
1191   }
1192   auto URIMainFile = URIForFile::canonicalize(*MainFilePath, *MainFilePath);
1193   auto CurLoc = sourceLocationInMainFile(SM, Pos);
1194   if (!CurLoc) {
1195     llvm::consumeError(CurLoc.takeError());
1196     return {};
1197   }
1198   llvm::Optional<DefinedMacro> Macro;
1199   if (const auto *IdentifierAtCursor =
1200           syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens())) {
1201     Macro = locateMacroAt(*IdentifierAtCursor, AST.getPreprocessor());
1202   }
1203 
1204   RefsRequest Req;
1205   if (Macro) {
1206     // Handle references to macro.
1207     if (auto MacroSID = getSymbolID(Macro->Name, Macro->Info, SM)) {
1208       // Collect macro references from main file.
1209       const auto &IDToRefs = AST.getMacros().MacroRefs;
1210       auto Refs = IDToRefs.find(MacroSID);
1211       if (Refs != IDToRefs.end()) {
1212         for (const auto &Ref : Refs->second) {
1213           Location Result;
1214           Result.range = Ref;
1215           Result.uri = URIMainFile;
1216           Results.References.push_back(std::move(Result));
1217         }
1218       }
1219       Req.IDs.insert(MacroSID);
1220     }
1221   } else {
1222     // Handle references to Decls.
1223 
1224     DeclRelationSet Relations =
1225         DeclRelation::TemplatePattern | DeclRelation::Alias;
1226     std::vector<const NamedDecl *> Decls =
1227         getDeclAtPosition(AST, *CurLoc, Relations);
1228 
1229     // We traverse the AST to find references in the main file.
1230     auto MainFileRefs = findRefs(Decls, AST);
1231     // We may get multiple refs with the same location and different Roles, as
1232     // cross-reference is only interested in locations, we deduplicate them
1233     // by the location to avoid emitting duplicated locations.
1234     MainFileRefs.erase(std::unique(MainFileRefs.begin(), MainFileRefs.end(),
1235                                    [](const ReferenceFinder::Reference &L,
1236                                       const ReferenceFinder::Reference &R) {
1237                                      return L.SpelledTok.location() ==
1238                                             R.SpelledTok.location();
1239                                    }),
1240                        MainFileRefs.end());
1241     for (const auto &Ref : MainFileRefs) {
1242       Location Result;
1243       Result.range = Ref.range(SM);
1244       Result.uri = URIMainFile;
1245       Results.References.push_back(std::move(Result));
1246     }
1247     if (Index && Results.References.size() <= Limit) {
1248       for (const Decl *D : Decls) {
1249         // Not all symbols can be referenced from outside (e.g.
1250         // function-locals).
1251         // TODO: we could skip TU-scoped symbols here (e.g. static functions) if
1252         // we know this file isn't a header. The details might be tricky.
1253         if (D->getParentFunctionOrMethod())
1254           continue;
1255         if (auto ID = getSymbolID(D))
1256           Req.IDs.insert(ID);
1257       }
1258     }
1259   }
1260   // Now query the index for references from other files.
1261   if (!Req.IDs.empty() && Index && Results.References.size() <= Limit) {
1262     Req.Limit = Limit;
1263     Results.HasMore |= Index->refs(Req, [&](const Ref &R) {
1264       // No need to continue process if we reach the limit.
1265       if (Results.References.size() > Limit)
1266         return;
1267       auto LSPLoc = toLSPLocation(R.Location, *MainFilePath);
1268       // Avoid indexed results for the main file - the AST is authoritative.
1269       if (!LSPLoc || LSPLoc->uri.file() == *MainFilePath)
1270         return;
1271 
1272       Results.References.push_back(std::move(*LSPLoc));
1273     });
1274   }
1275   if (Results.References.size() > Limit) {
1276     Results.HasMore = true;
1277     Results.References.resize(Limit);
1278   }
1279   return Results;
1280 }
1281 
getSymbolInfo(ParsedAST & AST,Position Pos)1282 std::vector<SymbolDetails> getSymbolInfo(ParsedAST &AST, Position Pos) {
1283   const SourceManager &SM = AST.getSourceManager();
1284   auto CurLoc = sourceLocationInMainFile(SM, Pos);
1285   if (!CurLoc) {
1286     llvm::consumeError(CurLoc.takeError());
1287     return {};
1288   }
1289 
1290   std::vector<SymbolDetails> Results;
1291 
1292   // We also want the targets of using-decls, so we include
1293   // DeclRelation::Underlying.
1294   DeclRelationSet Relations = DeclRelation::TemplatePattern |
1295                               DeclRelation::Alias | DeclRelation::Underlying;
1296   for (const NamedDecl *D : getDeclAtPosition(AST, *CurLoc, Relations)) {
1297     SymbolDetails NewSymbol;
1298     std::string QName = printQualifiedName(*D);
1299     auto SplitQName = splitQualifiedName(QName);
1300     NewSymbol.containerName = std::string(SplitQName.first);
1301     NewSymbol.name = std::string(SplitQName.second);
1302 
1303     if (NewSymbol.containerName.empty()) {
1304       if (const auto *ParentND =
1305               dyn_cast_or_null<NamedDecl>(D->getDeclContext()))
1306         NewSymbol.containerName = printQualifiedName(*ParentND);
1307     }
1308     llvm::SmallString<32> USR;
1309     if (!index::generateUSRForDecl(D, USR)) {
1310       NewSymbol.USR = std::string(USR.str());
1311       NewSymbol.ID = SymbolID(NewSymbol.USR);
1312     }
1313     Results.push_back(std::move(NewSymbol));
1314   }
1315 
1316   const auto *IdentifierAtCursor =
1317       syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens());
1318   if (!IdentifierAtCursor)
1319     return Results;
1320 
1321   if (auto M = locateMacroAt(*IdentifierAtCursor, AST.getPreprocessor())) {
1322     SymbolDetails NewMacro;
1323     NewMacro.name = std::string(M->Name);
1324     llvm::SmallString<32> USR;
1325     if (!index::generateUSRForMacro(NewMacro.name, M->Info->getDefinitionLoc(),
1326                                     SM, USR)) {
1327       NewMacro.USR = std::string(USR.str());
1328       NewMacro.ID = SymbolID(NewMacro.USR);
1329     }
1330     Results.push_back(std::move(NewMacro));
1331   }
1332 
1333   return Results;
1334 }
1335 
operator <<(llvm::raw_ostream & OS,const LocatedSymbol & S)1336 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const LocatedSymbol &S) {
1337   OS << S.Name << ": " << S.PreferredDeclaration;
1338   if (S.Definition)
1339     OS << " def=" << *S.Definition;
1340   return OS;
1341 }
1342 
1343 template <typename HierarchyItem>
declToHierarchyItem(const NamedDecl & ND)1344 static llvm::Optional<HierarchyItem> declToHierarchyItem(const NamedDecl &ND) {
1345   ASTContext &Ctx = ND.getASTContext();
1346   auto &SM = Ctx.getSourceManager();
1347   SourceLocation NameLoc = nameLocation(ND, Ctx.getSourceManager());
1348   SourceLocation BeginLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getBeginLoc()));
1349   SourceLocation EndLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getEndLoc()));
1350   const auto DeclRange =
1351       toHalfOpenFileRange(SM, Ctx.getLangOpts(), {BeginLoc, EndLoc});
1352   if (!DeclRange)
1353     return llvm::None;
1354   auto FilePath =
1355       getCanonicalPath(SM.getFileEntryForID(SM.getFileID(NameLoc)), SM);
1356   auto TUPath = getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
1357   if (!FilePath || !TUPath)
1358     return llvm::None; // Not useful without a uri.
1359 
1360   Position NameBegin = sourceLocToPosition(SM, NameLoc);
1361   Position NameEnd = sourceLocToPosition(
1362       SM, Lexer::getLocForEndOfToken(NameLoc, 0, SM, Ctx.getLangOpts()));
1363 
1364   index::SymbolInfo SymInfo = index::getSymbolInfo(&ND);
1365   // FIXME: This is not classifying constructors, destructors and operators
1366   // correctly.
1367   SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind);
1368 
1369   HierarchyItem HI;
1370   HI.name = printName(Ctx, ND);
1371   HI.kind = SK;
1372   HI.range = Range{sourceLocToPosition(SM, DeclRange->getBegin()),
1373                    sourceLocToPosition(SM, DeclRange->getEnd())};
1374   HI.selectionRange = Range{NameBegin, NameEnd};
1375   if (!HI.range.contains(HI.selectionRange)) {
1376     // 'selectionRange' must be contained in 'range', so in cases where clang
1377     // reports unrelated ranges we need to reconcile somehow.
1378     HI.range = HI.selectionRange;
1379   }
1380 
1381   HI.uri = URIForFile::canonicalize(*FilePath, *TUPath);
1382 
1383   // Compute the SymbolID and store it in the 'data' field.
1384   // This allows typeHierarchy/resolve to be used to
1385   // resolve children of items returned in a previous request
1386   // for parents.
1387   if (auto ID = getSymbolID(&ND))
1388     HI.data = ID.str();
1389 
1390   return HI;
1391 }
1392 
1393 static llvm::Optional<TypeHierarchyItem>
declToTypeHierarchyItem(const NamedDecl & ND)1394 declToTypeHierarchyItem(const NamedDecl &ND) {
1395   auto Result = declToHierarchyItem<TypeHierarchyItem>(ND);
1396   if (Result)
1397     Result->deprecated = ND.isDeprecated();
1398   return Result;
1399 }
1400 
1401 static llvm::Optional<CallHierarchyItem>
declToCallHierarchyItem(const NamedDecl & ND)1402 declToCallHierarchyItem(const NamedDecl &ND) {
1403   auto Result = declToHierarchyItem<CallHierarchyItem>(ND);
1404   if (Result && ND.isDeprecated())
1405     Result->tags.push_back(SymbolTag::Deprecated);
1406   return Result;
1407 }
1408 
1409 template <typename HierarchyItem>
symbolToHierarchyItem(const Symbol & S,PathRef TUPath)1410 static llvm::Optional<HierarchyItem> symbolToHierarchyItem(const Symbol &S,
1411                                                            PathRef TUPath) {
1412   auto Loc = symbolToLocation(S, TUPath);
1413   if (!Loc) {
1414     elog("Failed to convert symbol to hierarchy item: {0}", Loc.takeError());
1415     return llvm::None;
1416   }
1417   HierarchyItem HI;
1418   HI.name = std::string(S.Name);
1419   HI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind);
1420   HI.selectionRange = Loc->range;
1421   // FIXME: Populate 'range' correctly
1422   // (https://github.com/clangd/clangd/issues/59).
1423   HI.range = HI.selectionRange;
1424   HI.uri = Loc->uri;
1425   // Store the SymbolID in the 'data' field. The client will
1426   // send this back in requests to resolve additional levels
1427   // of the hierarchy.
1428   HI.data = S.ID.str();
1429 
1430   return HI;
1431 }
1432 
1433 static llvm::Optional<TypeHierarchyItem>
symbolToTypeHierarchyItem(const Symbol & S,PathRef TUPath)1434 symbolToTypeHierarchyItem(const Symbol &S, PathRef TUPath) {
1435   auto Result = symbolToHierarchyItem<TypeHierarchyItem>(S, TUPath);
1436   if (Result)
1437     Result->deprecated = (S.Flags & Symbol::Deprecated);
1438   return Result;
1439 }
1440 
1441 static llvm::Optional<CallHierarchyItem>
symbolToCallHierarchyItem(const Symbol & S,PathRef TUPath)1442 symbolToCallHierarchyItem(const Symbol &S, PathRef TUPath) {
1443   auto Result = symbolToHierarchyItem<CallHierarchyItem>(S, TUPath);
1444   if (Result && (S.Flags & Symbol::Deprecated))
1445     Result->tags.push_back(SymbolTag::Deprecated);
1446   return Result;
1447 }
1448 
fillSubTypes(const SymbolID & ID,std::vector<TypeHierarchyItem> & SubTypes,const SymbolIndex * Index,int Levels,PathRef TUPath)1449 static void fillSubTypes(const SymbolID &ID,
1450                          std::vector<TypeHierarchyItem> &SubTypes,
1451                          const SymbolIndex *Index, int Levels, PathRef TUPath) {
1452   RelationsRequest Req;
1453   Req.Subjects.insert(ID);
1454   Req.Predicate = RelationKind::BaseOf;
1455   Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
1456     if (Optional<TypeHierarchyItem> ChildSym =
1457             symbolToTypeHierarchyItem(Object, TUPath)) {
1458       if (Levels > 1) {
1459         ChildSym->children.emplace();
1460         fillSubTypes(Object.ID, *ChildSym->children, Index, Levels - 1, TUPath);
1461       }
1462       SubTypes.emplace_back(std::move(*ChildSym));
1463     }
1464   });
1465 }
1466 
1467 using RecursionProtectionSet = llvm::SmallSet<const CXXRecordDecl *, 4>;
1468 
fillSuperTypes(const CXXRecordDecl & CXXRD,ASTContext & ASTCtx,std::vector<TypeHierarchyItem> & SuperTypes,RecursionProtectionSet & RPSet)1469 static void fillSuperTypes(const CXXRecordDecl &CXXRD, ASTContext &ASTCtx,
1470                            std::vector<TypeHierarchyItem> &SuperTypes,
1471                            RecursionProtectionSet &RPSet) {
1472   // typeParents() will replace dependent template specializations
1473   // with their class template, so to avoid infinite recursion for
1474   // certain types of hierarchies, keep the templates encountered
1475   // along the parent chain in a set, and stop the recursion if one
1476   // starts to repeat.
1477   auto *Pattern = CXXRD.getDescribedTemplate() ? &CXXRD : nullptr;
1478   if (Pattern) {
1479     if (!RPSet.insert(Pattern).second) {
1480       return;
1481     }
1482   }
1483 
1484   for (const CXXRecordDecl *ParentDecl : typeParents(&CXXRD)) {
1485     if (Optional<TypeHierarchyItem> ParentSym =
1486             declToTypeHierarchyItem(*ParentDecl)) {
1487       ParentSym->parents.emplace();
1488       fillSuperTypes(*ParentDecl, ASTCtx, *ParentSym->parents, RPSet);
1489       SuperTypes.emplace_back(std::move(*ParentSym));
1490     }
1491   }
1492 
1493   if (Pattern) {
1494     RPSet.erase(Pattern);
1495   }
1496 }
1497 
findRecordTypeAt(ParsedAST & AST,Position Pos)1498 const CXXRecordDecl *findRecordTypeAt(ParsedAST &AST, Position Pos) {
1499   auto RecordFromNode =
1500       [](const SelectionTree::Node *N) -> const CXXRecordDecl * {
1501     if (!N)
1502       return nullptr;
1503 
1504     // Note: explicitReferenceTargets() will search for both template
1505     // instantiations and template patterns, and prefer the former if available
1506     // (generally, one will be available for non-dependent specializations of a
1507     // class template).
1508     auto Decls = explicitReferenceTargets(N->ASTNode, DeclRelation::Underlying);
1509     if (Decls.empty())
1510       return nullptr;
1511 
1512     const NamedDecl *D = Decls[0];
1513 
1514     if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
1515       // If this is a variable, use the type of the variable.
1516       return VD->getType().getTypePtr()->getAsCXXRecordDecl();
1517     }
1518 
1519     if (const CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(D)) {
1520       // If this is a method, use the type of the class.
1521       return Method->getParent();
1522     }
1523 
1524     // We don't handle FieldDecl because it's not clear what behaviour
1525     // the user would expect: the enclosing class type (as with a
1526     // method), or the field's type (as with a variable).
1527 
1528     return dyn_cast<CXXRecordDecl>(D);
1529   };
1530 
1531   const SourceManager &SM = AST.getSourceManager();
1532   const CXXRecordDecl *Result = nullptr;
1533   auto Offset = positionToOffset(SM.getBufferData(SM.getMainFileID()), Pos);
1534   if (!Offset) {
1535     llvm::consumeError(Offset.takeError());
1536     return Result;
1537   }
1538   SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), *Offset,
1539                             *Offset, [&](SelectionTree ST) {
1540                               Result = RecordFromNode(ST.commonAncestor());
1541                               return Result != nullptr;
1542                             });
1543   return Result;
1544 }
1545 
typeParents(const CXXRecordDecl * CXXRD)1546 std::vector<const CXXRecordDecl *> typeParents(const CXXRecordDecl *CXXRD) {
1547   std::vector<const CXXRecordDecl *> Result;
1548 
1549   // If this is an invalid instantiation, instantiation of the bases
1550   // may not have succeeded, so fall back to the template pattern.
1551   if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD)) {
1552     if (CTSD->isInvalidDecl())
1553       CXXRD = CTSD->getSpecializedTemplate()->getTemplatedDecl();
1554   }
1555 
1556   // Can't query bases without a definition.
1557   if (!CXXRD->hasDefinition())
1558     return Result;
1559 
1560   for (auto Base : CXXRD->bases()) {
1561     const CXXRecordDecl *ParentDecl = nullptr;
1562 
1563     const Type *Type = Base.getType().getTypePtr();
1564     if (const RecordType *RT = Type->getAs<RecordType>()) {
1565       ParentDecl = RT->getAsCXXRecordDecl();
1566     }
1567 
1568     if (!ParentDecl) {
1569       // Handle a dependent base such as "Base<T>" by using the primary
1570       // template.
1571       if (const TemplateSpecializationType *TS =
1572               Type->getAs<TemplateSpecializationType>()) {
1573         TemplateName TN = TS->getTemplateName();
1574         if (TemplateDecl *TD = TN.getAsTemplateDecl()) {
1575           ParentDecl = dyn_cast<CXXRecordDecl>(TD->getTemplatedDecl());
1576         }
1577       }
1578     }
1579 
1580     if (ParentDecl)
1581       Result.push_back(ParentDecl);
1582   }
1583 
1584   return Result;
1585 }
1586 
1587 llvm::Optional<TypeHierarchyItem>
getTypeHierarchy(ParsedAST & AST,Position Pos,int ResolveLevels,TypeHierarchyDirection Direction,const SymbolIndex * Index,PathRef TUPath)1588 getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
1589                  TypeHierarchyDirection Direction, const SymbolIndex *Index,
1590                  PathRef TUPath) {
1591   const CXXRecordDecl *CXXRD = findRecordTypeAt(AST, Pos);
1592   if (!CXXRD)
1593     return llvm::None;
1594 
1595   bool WantParents = Direction == TypeHierarchyDirection::Parents ||
1596                      Direction == TypeHierarchyDirection::Both;
1597   bool WantChildren = Direction == TypeHierarchyDirection::Children ||
1598                       Direction == TypeHierarchyDirection::Both;
1599 
1600   // If we're looking for children, we're doing the lookup in the index.
1601   // The index does not store relationships between implicit
1602   // specializations, so if we have one, use the template pattern instead.
1603   // Note that this needs to be done before the declToTypeHierarchyItem(),
1604   // otherwise the type hierarchy item would misleadingly contain the
1605   // specialization parameters, while the children would involve classes
1606   // that derive from other specializations of the template.
1607   if (WantChildren) {
1608     if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD))
1609       CXXRD = CTSD->getTemplateInstantiationPattern();
1610   }
1611 
1612   Optional<TypeHierarchyItem> Result = declToTypeHierarchyItem(*CXXRD);
1613   if (!Result)
1614     return Result;
1615 
1616   if (WantParents) {
1617     Result->parents.emplace();
1618 
1619     RecursionProtectionSet RPSet;
1620     fillSuperTypes(*CXXRD, AST.getASTContext(), *Result->parents, RPSet);
1621   }
1622 
1623   if (WantChildren && ResolveLevels > 0) {
1624     Result->children.emplace();
1625 
1626     if (Index) {
1627       if (auto ID = getSymbolID(CXXRD))
1628         fillSubTypes(ID, *Result->children, Index, ResolveLevels, TUPath);
1629     }
1630   }
1631 
1632   return Result;
1633 }
1634 
resolveTypeHierarchy(TypeHierarchyItem & Item,int ResolveLevels,TypeHierarchyDirection Direction,const SymbolIndex * Index)1635 void resolveTypeHierarchy(TypeHierarchyItem &Item, int ResolveLevels,
1636                           TypeHierarchyDirection Direction,
1637                           const SymbolIndex *Index) {
1638   // We only support typeHierarchy/resolve for children, because for parents
1639   // we ignore ResolveLevels and return all levels of parents eagerly.
1640   if (Direction == TypeHierarchyDirection::Parents || ResolveLevels == 0)
1641     return;
1642 
1643   Item.children.emplace();
1644 
1645   if (Index && Item.data) {
1646     // We store the item's SymbolID in the 'data' field, and the client
1647     // passes it back to us in typeHierarchy/resolve.
1648     if (Expected<SymbolID> ID = SymbolID::fromStr(*Item.data)) {
1649       fillSubTypes(*ID, *Item.children, Index, ResolveLevels, Item.uri.file());
1650     }
1651   }
1652 }
1653 
1654 std::vector<CallHierarchyItem>
prepareCallHierarchy(ParsedAST & AST,Position Pos,PathRef TUPath)1655 prepareCallHierarchy(ParsedAST &AST, Position Pos, PathRef TUPath) {
1656   std::vector<CallHierarchyItem> Result;
1657   const auto &SM = AST.getSourceManager();
1658   auto Loc = sourceLocationInMainFile(SM, Pos);
1659   if (!Loc) {
1660     elog("prepareCallHierarchy failed to convert position to source location: "
1661          "{0}",
1662          Loc.takeError());
1663     return Result;
1664   }
1665   for (const NamedDecl *Decl : getDeclAtPosition(AST, *Loc, {})) {
1666     if (!Decl->isFunctionOrFunctionTemplate())
1667       continue;
1668     if (auto CHI = declToCallHierarchyItem(*Decl))
1669       Result.emplace_back(std::move(*CHI));
1670   }
1671   return Result;
1672 }
1673 
1674 std::vector<CallHierarchyIncomingCall>
incomingCalls(const CallHierarchyItem & Item,const SymbolIndex * Index)1675 incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) {
1676   std::vector<CallHierarchyIncomingCall> Results;
1677   if (!Index || Item.data.empty())
1678     return Results;
1679   auto ID = SymbolID::fromStr(Item.data);
1680   if (!ID) {
1681     elog("incomingCalls failed to find symbol: {0}", ID.takeError());
1682     return Results;
1683   }
1684   // In this function, we find incoming calls based on the index only.
1685   // In principle, the AST could have more up-to-date information about
1686   // occurrences within the current file. However, going from a SymbolID
1687   // to an AST node isn't cheap, particularly when the declaration isn't
1688   // in the main file.
1689   // FIXME: Consider also using AST information when feasible.
1690   RefsRequest Request;
1691   Request.IDs.insert(*ID);
1692   // We could restrict more specifically to calls by introducing a new RefKind,
1693   // but non-call references (such as address-of-function) can still be
1694   // interesting as they can indicate indirect calls.
1695   Request.Filter = RefKind::Reference;
1696   // Initially store the ranges in a map keyed by SymbolID of the caller.
1697   // This allows us to group different calls with the same caller
1698   // into the same CallHierarchyIncomingCall.
1699   llvm::DenseMap<SymbolID, std::vector<Range>> CallsIn;
1700   // We can populate the ranges based on a refs request only. As we do so, we
1701   // also accumulate the container IDs into a lookup request.
1702   LookupRequest ContainerLookup;
1703   Index->refs(Request, [&](const Ref &R) {
1704     auto Loc = indexToLSPLocation(R.Location, Item.uri.file());
1705     if (!Loc) {
1706       elog("incomingCalls failed to convert location: {0}", Loc.takeError());
1707       return;
1708     }
1709     auto It = CallsIn.try_emplace(R.Container, std::vector<Range>{}).first;
1710     It->second.push_back(Loc->range);
1711 
1712     ContainerLookup.IDs.insert(R.Container);
1713   });
1714   // Perform the lookup request and combine its results with CallsIn to
1715   // get complete CallHierarchyIncomingCall objects.
1716   Index->lookup(ContainerLookup, [&](const Symbol &Caller) {
1717     auto It = CallsIn.find(Caller.ID);
1718     assert(It != CallsIn.end());
1719     if (auto CHI = symbolToCallHierarchyItem(Caller, Item.uri.file()))
1720       Results.push_back(
1721           CallHierarchyIncomingCall{std::move(*CHI), std::move(It->second)});
1722   });
1723   // Sort results by name of container.
1724   llvm::sort(Results, [](const CallHierarchyIncomingCall &A,
1725                          const CallHierarchyIncomingCall &B) {
1726     return A.from.name < B.from.name;
1727   });
1728   return Results;
1729 }
1730 
getNonLocalDeclRefs(ParsedAST & AST,const FunctionDecl * FD)1731 llvm::DenseSet<const Decl *> getNonLocalDeclRefs(ParsedAST &AST,
1732                                                  const FunctionDecl *FD) {
1733   if (!FD->hasBody())
1734     return {};
1735   llvm::DenseSet<const Decl *> DeclRefs;
1736   findExplicitReferences(FD, [&](ReferenceLoc Ref) {
1737     for (const Decl *D : Ref.Targets) {
1738       if (!index::isFunctionLocalSymbol(D) && !D->isTemplateParameter() &&
1739           !Ref.IsDecl)
1740         DeclRefs.insert(D);
1741     }
1742   });
1743   return DeclRefs;
1744 }
1745 } // namespace clangd
1746 } // namespace clang
1747