Debian Codegraph @

llvm-project/clang-tools-extra/clangd/XRefs.cpp

raw
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 "FindSymbols.h"
11 #include "FindTarget.h"
12 #include "HeuristicResolver.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/SymbolCollector.h"
23 #include "index/SymbolID.h"
24 #include "index/SymbolLocation.h"
25 #include "support/Logger.h"
26 #include "clang/AST/ASTContext.h"
27 #include "clang/AST/ASTTypeTraits.h"
28 #include "clang/AST/Attr.h"
29 #include "clang/AST/Attrs.inc"
30 #include "clang/AST/Decl.h"
31 #include "clang/AST/DeclCXX.h"
32 #include "clang/AST/DeclObjC.h"
33 #include "clang/AST/DeclTemplate.h"
34 #include "clang/AST/DeclVisitor.h"
35 #include "clang/AST/ExprCXX.h"
36 #include "clang/AST/RecursiveASTVisitor.h"
37 #include "clang/AST/Stmt.h"
38 #include "clang/AST/StmtCXX.h"
39 #include "clang/AST/StmtVisitor.h"
40 #include "clang/AST/Type.h"
41 #include "clang/Basic/LLVM.h"
42 #include "clang/Basic/LangOptions.h"
43 #include "clang/Basic/SourceLocation.h"
44 #include "clang/Basic/SourceManager.h"
45 #include "clang/Basic/TokenKinds.h"
46 #include "clang/Index/IndexDataConsumer.h"
47 #include "clang/Index/IndexSymbol.h"
48 #include "clang/Index/IndexingAction.h"
49 #include "clang/Index/IndexingOptions.h"
50 #include "clang/Index/USRGeneration.h"
51 #include "clang/Tooling/Syntax/Tokens.h"
52 #include "llvm/ADT/ArrayRef.h"
53 #include "llvm/ADT/DenseMap.h"
54 #include "llvm/ADT/STLExtras.h"
55 #include "llvm/ADT/ScopeExit.h"
56 #include "llvm/ADT/SmallSet.h"
57 #include "llvm/ADT/SmallVector.h"
58 #include "llvm/ADT/StringRef.h"
59 #include "llvm/Support/Casting.h"
60 #include "llvm/Support/Error.h"
61 #include "llvm/Support/Path.h"
62 #include "llvm/Support/raw_ostream.h"
63 #include <optional>
64 #include <vector>
65
66 namespace clang {
67 namespace clangd {
68 namespace {
69
70 // Returns the single definition of the entity declared by D, if visible.
71 // In particular:
72 // - for non-redeclarable kinds (e.g. local vars), return D
73 // - for kinds that allow multiple definitions (e.g. namespaces), return nullptr
74 // Kinds of nodes that always return nullptr here will not have definitions
75 // reported by locateSymbolAt().
76 const NamedDecl *getDefinition(const NamedDecl *D) {
77 assert(D);
78 // Decl has one definition that we can find.
79 if (const auto *TD = dyn_cast<TagDecl>(D))
80 return TD->getDefinition();
81 if (const auto *VD = dyn_cast<VarDecl>(D))
82 return VD->getDefinition();
83 if (const auto *FD = dyn_cast<FunctionDecl>(D))
84 return FD->getDefinition();
85 if (const auto *CTD = dyn_cast<ClassTemplateDecl>(D))
86 if (const auto *RD = CTD->getTemplatedDecl())
87 return RD->getDefinition();
88 if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) {
89 if (MD->isThisDeclarationADefinition())
90 return MD;
91 // Look for the method definition inside the implementation decl.
92 auto *DeclCtx = cast<Decl>(MD->getDeclContext());
93 if (DeclCtx->isInvalidDecl())
94 return nullptr;
95
96 if (const auto *CD = dyn_cast<ObjCContainerDecl>(DeclCtx))
97 if (const auto *Impl = getCorrespondingObjCImpl(CD))
98 return Impl->getMethod(MD->getSelector(), MD->isInstanceMethod());
99 }
100 if (const auto *CD = dyn_cast<ObjCContainerDecl>(D))
101 return getCorrespondingObjCImpl(CD);
102 // Only a single declaration is allowed.
103 if (isa<ValueDecl>(D) || isa<TemplateTypeParmDecl>(D) ||
104 isa<TemplateTemplateParmDecl>(D)) // except cases above
105 return D;
106 // Multiple definitions are allowed.
107 return nullptr; // except cases above
108 }
109
110 void logIfOverflow(const SymbolLocation &Loc) {
111 if (Loc.Start.hasOverflow() || Loc.End.hasOverflow())
112 log("Possible overflow in symbol location: {0}", Loc);
113 }
114
115 // Convert a SymbolLocation to LSP's Location.
116 // TUPath is used to resolve the path of URI.
117 // FIXME: figure out a good home for it, and share the implementation with
118 // FindSymbols.
119 std::optional<Location> toLSPLocation(const SymbolLocation &Loc,
120 llvm::StringRef TUPath) {
121 if (!Loc)
122 return std::nullopt;
123 auto Uri = URI::parse(Loc.FileURI);
124 if (!Uri) {
125 elog("Could not parse URI {0}: {1}", Loc.FileURI, Uri.takeError());
126 return std::nullopt;
127 }
128 auto U = URIForFile::fromURI(*Uri, TUPath);
129 if (!U) {
130 elog("Could not resolve URI {0}: {1}", Loc.FileURI, U.takeError());
131 return std::nullopt;
132 }
133
134 Location LSPLoc;
135 LSPLoc.uri = std::move(*U);
136 LSPLoc.range.start.line = Loc.Start.line();
137 LSPLoc.range.start.character = Loc.Start.column();
138 LSPLoc.range.end.line = Loc.End.line();
139 LSPLoc.range.end.character = Loc.End.column();
140 logIfOverflow(Loc);
141 return LSPLoc;
142 }
143
144 SymbolLocation toIndexLocation(const Location &Loc, std::string &URIStorage) {
145 SymbolLocation SymLoc;
146 URIStorage = Loc.uri.uri();
147 SymLoc.FileURI = URIStorage.c_str();
148 SymLoc.Start.setLine(Loc.range.start.line);
149 SymLoc.Start.setColumn(Loc.range.start.character);
150 SymLoc.End.setLine(Loc.range.end.line);
151 SymLoc.End.setColumn(Loc.range.end.character);
152 return SymLoc;
153 }
154
155 // Returns the preferred location between an AST location and an index location.
156 SymbolLocation getPreferredLocation(const Location &ASTLoc,
157 const SymbolLocation &IdxLoc,
158 std::string &Scratch) {
159 // Also use a mock symbol for the index location so that other fields (e.g.
160 // definition) are not factored into the preference.
161 Symbol ASTSym, IdxSym;
162 ASTSym.ID = IdxSym.ID = SymbolID("mock_symbol_id");
163 ASTSym.CanonicalDeclaration = toIndexLocation(ASTLoc, Scratch);
164 IdxSym.CanonicalDeclaration = IdxLoc;
165 auto Merged = mergeSymbol(ASTSym, IdxSym);
166 return Merged.CanonicalDeclaration;
167 }
168
169 std::vector<std::pair<const NamedDecl *, DeclRelationSet>>
170 getDeclAtPositionWithRelations(ParsedAST &AST, SourceLocation Pos,
171 DeclRelationSet Relations,
172 ASTNodeKind *NodeKind = nullptr) {
173 unsigned Offset = AST.getSourceManager().getDecomposedSpellingLoc(Pos).second;
174 std::vector<std::pair<const NamedDecl *, DeclRelationSet>> Result;
175 auto ResultFromTree = [&](SelectionTree ST) {
176 if (const SelectionTree::Node *N = ST.commonAncestor()) {
177 if (NodeKind)
178 *NodeKind = N->ASTNode.getNodeKind();
179 // Attributes don't target decls, look at the
180 // thing it's attached to.
181 // We still report the original NodeKind!
182 // This makes the `override` hack work.
183 if (N->ASTNode.get<Attr>() && N->Parent)
184 N = N->Parent;
185 llvm::copy_if(allTargetDecls(N->ASTNode, AST.getHeuristicResolver()),
186 std::back_inserter(Result),
187 [&](auto &Entry) { return !(Entry.second & ~Relations); });
188 }
189 return !Result.empty();
190 };
191 SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset,
192 Offset, ResultFromTree);
193 return Result;
194 }
195
196 std::vector<const NamedDecl *>
197 getDeclAtPosition(ParsedAST &AST, SourceLocation Pos, DeclRelationSet Relations,
198 ASTNodeKind *NodeKind = nullptr) {
199 std::vector<const NamedDecl *> Result;
200 for (auto &Entry :
201 getDeclAtPositionWithRelations(AST, Pos, Relations, NodeKind))
202 Result.push_back(Entry.first);
203 return Result;
204 }
205
206 // Expects Loc to be a SpellingLocation, will bail out otherwise as it can't
207 // figure out a filename.
208 std::optional<Location> makeLocation(const ASTContext &AST, SourceLocation Loc,
209 llvm::StringRef TUPath) {
210 const auto &SM = AST.getSourceManager();
211 const FileEntry *F = SM.getFileEntryForID(SM.getFileID(Loc));
212 if (!F)
213 return std::nullopt;
214 auto FilePath = getCanonicalPath(F, SM);
215 if (!FilePath) {
216 log("failed to get path!");
217 return std::nullopt;
218 }
219 Location L;
220 L.uri = URIForFile::canonicalize(*FilePath, TUPath);
221 // We call MeasureTokenLength here as TokenBuffer doesn't store spelled tokens
222 // outside the main file.
223 auto TokLen = Lexer::MeasureTokenLength(Loc, SM, AST.getLangOpts());
224 L.range = halfOpenToRange(
225 SM, CharSourceRange::getCharRange(Loc, Loc.getLocWithOffset(TokLen)));
226 return L;
227 }
228
229 // Treat #included files as symbols, to enable go-to-definition on them.
230 std::optional<LocatedSymbol> locateFileReferent(const Position &Pos,
231 ParsedAST &AST,
232 llvm::StringRef MainFilePath) {
233 for (auto &Inc : AST.getIncludeStructure().MainFileIncludes) {
234 if (!Inc.Resolved.empty() && Inc.HashLine == Pos.line) {
235 LocatedSymbol File;
236 File.Name = std::string(llvm::sys::path::filename(Inc.Resolved));
237 File.PreferredDeclaration = {
238 URIForFile::canonicalize(Inc.Resolved, MainFilePath), Range{}};
239 File.Definition = File.PreferredDeclaration;
240 // We're not going to find any further symbols on #include lines.
241 return File;
242 }
243 }
244 return std::nullopt;
245 }
246
247 // Macros are simple: there's no declaration/definition distinction.
248 // As a consequence, there's no need to look them up in the index either.
249 std::optional<LocatedSymbol>
250 locateMacroReferent(const syntax::Token &TouchedIdentifier, ParsedAST &AST,
251 llvm::StringRef MainFilePath) {
252 if (auto M = locateMacroAt(TouchedIdentifier, AST.getPreprocessor())) {
253 if (auto Loc =
254 makeLocation(AST.getASTContext(), M->NameLoc, MainFilePath)) {
255 LocatedSymbol Macro;
256 Macro.Name = std::string(M->Name);
257 Macro.PreferredDeclaration = *Loc;
258 Macro.Definition = Loc;
259 Macro.ID = getSymbolID(M->Name, M->Info, AST.getSourceManager());
260 return Macro;
261 }
262 }
263 return std::nullopt;
264 }
265
266 // A wrapper around `Decl::getCanonicalDecl` to support cases where Clang's
267 // definition of a canonical declaration doesn't match up to what a programmer
268 // would expect. For example, Objective-C classes can have three types of
269 // declarations:
270 //
271 // - forward declaration(s): @class MyClass;
272 // - true declaration (interface definition): @interface MyClass ... @end
273 // - true definition (implementation): @implementation MyClass ... @end
274 //
275 // Clang will consider the forward declaration to be the canonical declaration
276 // because it is first. We actually want the class definition if it is
277 // available since that is what a programmer would consider the primary
278 // declaration to be.
279 const NamedDecl *getPreferredDecl(const NamedDecl *D) {
280 // FIXME: Canonical declarations of some symbols might refer to built-in
281 // decls with possibly-invalid source locations (e.g. global new operator).
282 // In such cases we should pick up a redecl with valid source location
283 // instead of failing.
284 D = llvm::cast<NamedDecl>(D->getCanonicalDecl());
285
286 // Prefer Objective-C class/protocol definitions over the forward declaration.
287 if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(D))
288 if (const auto *DefinitionID = ID->getDefinition())
289 return DefinitionID;
290 if (const auto *PD = dyn_cast<ObjCProtocolDecl>(D))
291 if (const auto *DefinitionID = PD->getDefinition())
292 return DefinitionID;
293
294 return D;
295 }
296
297 std::vector<LocatedSymbol> findImplementors(llvm::DenseSet<SymbolID> IDs,
298 RelationKind Predicate,
299 const SymbolIndex *Index,
300 llvm::StringRef MainFilePath) {
301 if (IDs.empty() || !Index)
302 return {};
303 static constexpr trace::Metric FindImplementorsMetric(
304 "find_implementors", trace::Metric::Counter, "case");
305 switch (Predicate) {
306 case RelationKind::BaseOf:
307 FindImplementorsMetric.record(1, "find-base");
308 break;
309 case RelationKind::OverriddenBy:
310 FindImplementorsMetric.record(1, "find-override");
311 break;
312 }
313
314 RelationsRequest Req;
315 Req.Predicate = Predicate;
316 Req.Subjects = std::move(IDs);
317 std::vector<LocatedSymbol> Results;
318 Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
319 auto DeclLoc =
320 indexToLSPLocation(Object.CanonicalDeclaration, MainFilePath);
321 if (!DeclLoc) {
322 elog("Find overrides: {0}", DeclLoc.takeError());
323 return;
324 }
325 Results.emplace_back();
326 Results.back().Name = Object.Name.str();
327 Results.back().PreferredDeclaration = *DeclLoc;
328 auto DefLoc = indexToLSPLocation(Object.Definition, MainFilePath);
329 if (!DefLoc) {
330 elog("Failed to convert location: {0}", DefLoc.takeError());
331 return;
332 }
333 Results.back().Definition = *DefLoc;
334 });
335 return Results;
336 }
337
338 // Decls are more complicated.
339 // The AST contains at least a declaration, maybe a definition.
340 // These are up-to-date, and so generally preferred over index results.
341 // We perform a single batch index lookup to find additional definitions.
342 std::vector<LocatedSymbol>
343 locateASTReferent(SourceLocation CurLoc, const syntax::Token *TouchedIdentifier,
344 ParsedAST &AST, llvm::StringRef MainFilePath,
345 const SymbolIndex *Index, ASTNodeKind &NodeKind) {
346 const SourceManager &SM = AST.getSourceManager();
347 // Results follow the order of Symbols.Decls.
348 std::vector<LocatedSymbol> Result;
349 // Keep track of SymbolID -> index mapping, to fill in index data later.
350 llvm::DenseMap<SymbolID, size_t> ResultIndex;
351
352 static constexpr trace::Metric LocateASTReferentMetric(
353 "locate_ast_referent", trace::Metric::Counter, "case");
354 auto AddResultDecl = [&](const NamedDecl *D) {
355 D = getPreferredDecl(D);
356 auto Loc =
357 makeLocation(AST.getASTContext(), nameLocation(*D, SM), MainFilePath);
358 if (!Loc)
359 return;
360
361 Result.emplace_back();
362 Result.back().Name = printName(AST.getASTContext(), *D);
363 Result.back().PreferredDeclaration = *Loc;
364 Result.back().ID = getSymbolID(D);
365 if (const NamedDecl *Def = getDefinition(D))
366 Result.back().Definition = makeLocation(
367 AST.getASTContext(), nameLocation(*Def, SM), MainFilePath);
368
369 // Record SymbolID for index lookup later.
370 if (auto ID = getSymbolID(D))
371 ResultIndex[ID] = Result.size() - 1;
372 };
373
374 // Emit all symbol locations (declaration or definition) from AST.
375 DeclRelationSet Relations =
376 DeclRelation::TemplatePattern | DeclRelation::Alias;
377 auto Candidates =
378 getDeclAtPositionWithRelations(AST, CurLoc, Relations, &NodeKind);
379 llvm::DenseSet<SymbolID> VirtualMethods;
380 for (const auto &E : Candidates) {
381 const NamedDecl *D = E.first;
382 if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(D)) {
383 // Special case: virtual void ^method() = 0: jump to all overrides.
384 // FIXME: extend it to ^virtual, unfortunately, virtual location is not
385 // saved in the AST.
386 if (CMD->isPure()) {
387 if (TouchedIdentifier && SM.getSpellingLoc(CMD->getLocation()) ==
388 TouchedIdentifier->location()) {
389 VirtualMethods.insert(getSymbolID(CMD));
390 LocateASTReferentMetric.record(1, "method-to-override");
391 }
392 }
393 // Special case: void foo() ^override: jump to the overridden method.
394 if (NodeKind.isSame(ASTNodeKind::getFromNodeKind<OverrideAttr>()) ||
395 NodeKind.isSame(ASTNodeKind::getFromNodeKind<FinalAttr>())) {
396 // We may be overridding multiple methods - offer them all.
397 for (const NamedDecl *ND : CMD->overridden_methods())
398 AddResultDecl(ND);
399 continue;
400 }
401 }
402
403 // Special case: the cursor is on an alias, prefer other results.
404 // This targets "using ns::^Foo", where the target is more interesting.
405 // This does not trigger on renaming aliases:
406 // `using Foo = ^Bar` already targets Bar via a TypeLoc
407 // `using ^Foo = Bar` has no other results, as Underlying is filtered.
408 if (E.second & DeclRelation::Alias && Candidates.size() > 1 &&
409 // beginLoc/endLoc are a token range, so rewind the identifier we're in.
410 SM.isPointWithin(TouchedIdentifier ? TouchedIdentifier->location()
411 : CurLoc,
412 D->getBeginLoc(), D->getEndLoc()))
413 continue;
414
415 // Special case: the point of declaration of a template specialization,
416 // it's more useful to navigate to the template declaration.
417 if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(D)) {
418 if (TouchedIdentifier &&
419 D->getLocation() == TouchedIdentifier->location()) {
420 LocateASTReferentMetric.record(1, "template-specialization-to-primary");
421 AddResultDecl(CTSD->getSpecializedTemplate());
422 continue;
423 }
424 }
425
426 // Special case: if the class name is selected, also map Objective-C
427 // categories and category implementations back to their class interface.
428 //
429 // Since `TouchedIdentifier` might refer to the `ObjCCategoryImplDecl`
430 // instead of the `ObjCCategoryDecl` we intentionally check the contents
431 // of the locs when checking for class name equivalence.
432 if (const auto *CD = dyn_cast<ObjCCategoryDecl>(D))
433 if (const auto *ID = CD->getClassInterface())
434 if (TouchedIdentifier &&
435 (CD->getLocation() == TouchedIdentifier->location() ||
436 ID->getName() == TouchedIdentifier->text(SM))) {
437 LocateASTReferentMetric.record(1, "objc-category-to-class");
438 AddResultDecl(ID);
439 }
440
441 LocateASTReferentMetric.record(1, "regular");
442 // Otherwise the target declaration is the right one.
443 AddResultDecl(D);
444 }
445
446 // Now query the index for all Symbol IDs we found in the AST.
447 if (Index && !ResultIndex.empty()) {
448 LookupRequest QueryRequest;
449 for (auto It : ResultIndex)
450 QueryRequest.IDs.insert(It.first);
451 std::string Scratch;
452 Index->lookup(QueryRequest, [&](const Symbol &Sym) {
453 auto &R = Result[ResultIndex.lookup(Sym.ID)];
454
455 if (R.Definition) { // from AST
456 // Special case: if the AST yielded a definition, then it may not be
457 // the right *declaration*. Prefer the one from the index.
458 if (auto Loc = toLSPLocation(Sym.CanonicalDeclaration, MainFilePath))
459 R.PreferredDeclaration = *Loc;
460
461 // We might still prefer the definition from the index, e.g. for
462 // generated symbols.
463 if (auto Loc = toLSPLocation(
464 getPreferredLocation(*R.Definition, Sym.Definition, Scratch),
465 MainFilePath))
466 R.Definition = *Loc;
467 } else {
468 R.Definition = toLSPLocation(Sym.Definition, MainFilePath);
469
470 // Use merge logic to choose AST or index declaration.
471 if (auto Loc = toLSPLocation(
472 getPreferredLocation(R.PreferredDeclaration,
473 Sym.CanonicalDeclaration, Scratch),
474 MainFilePath))
475 R.PreferredDeclaration = *Loc;
476 }
477 });
478 }
479
480 auto Overrides = findImplementors(VirtualMethods, RelationKind::OverriddenBy,
481 Index, MainFilePath);
482 Result.insert(Result.end(), Overrides.begin(), Overrides.end());
483 return Result;
484 }
485
486 std::vector<LocatedSymbol> locateSymbolForType(const ParsedAST &AST,
487 const QualType &Type) {
488 const auto &SM = AST.getSourceManager();
489 auto MainFilePath = AST.tuPath();
490
491 // FIXME: this sends unique_ptr<Foo> to unique_ptr<T>.
492 // Likely it would be better to send it to Foo (heuristically) or to both.
493 auto Decls = targetDecl(DynTypedNode::create(Type.getNonReferenceType()),
494 DeclRelation::TemplatePattern | DeclRelation::Alias,
495 AST.getHeuristicResolver());
496 if (Decls.empty())
497 return {};
498
499 std::vector<LocatedSymbol> Results;
500 const auto &ASTContext = AST.getASTContext();
501
502 for (const NamedDecl *D : Decls) {
503 D = getPreferredDecl(D);
504
505 auto Loc = makeLocation(ASTContext, nameLocation(*D, SM), MainFilePath);
506 if (!Loc)
507 continue;
508
509 Results.emplace_back();
510 Results.back().Name = printName(ASTContext, *D);
511 Results.back().PreferredDeclaration = *Loc;
512 Results.back().ID = getSymbolID(D);
513 if (const NamedDecl *Def = getDefinition(D))
514 Results.back().Definition =
515 makeLocation(ASTContext, nameLocation(*Def, SM), MainFilePath);
516 }
517
518 return Results;
519 }
520
521 bool tokenSpelledAt(SourceLocation SpellingLoc, const syntax::TokenBuffer &TB) {
522 auto ExpandedTokens = TB.expandedTokens(
523 TB.sourceManager().getMacroArgExpandedLocation(SpellingLoc));
524 return !ExpandedTokens.empty();
525 }
526
527 llvm::StringRef sourcePrefix(SourceLocation Loc, const SourceManager &SM) {
528 auto D = SM.getDecomposedLoc(Loc);
529 bool Invalid = false;
530 llvm::StringRef Buf = SM.getBufferData(D.first, &Invalid);
531 if (Invalid || D.second > Buf.size())
532 return "";
533 return Buf.substr(0, D.second);
534 }
535
536 bool isDependentName(ASTNodeKind NodeKind) {
537 return NodeKind.isSame(ASTNodeKind::getFromNodeKind<OverloadExpr>()) ||
538 NodeKind.isSame(
539 ASTNodeKind::getFromNodeKind<CXXDependentScopeMemberExpr>()) ||
540 NodeKind.isSame(
541 ASTNodeKind::getFromNodeKind<DependentScopeDeclRefExpr>());
542 }
543
544 } // namespace
545
546 std::vector<LocatedSymbol> locateSymbolTextually(const SpelledWord &Word,
547 ParsedAST &AST,
548 const SymbolIndex *Index,
549 llvm::StringRef MainFilePath,
550 ASTNodeKind NodeKind) {
551 // Don't use heuristics if this is a real identifier, or not an
552 // identifier.
553 // Exception: dependent names, because those may have useful textual
554 // matches that AST-based heuristics cannot find.
555 if ((Word.ExpandedToken && !isDependentName(NodeKind)) ||
556 !Word.LikelyIdentifier || !Index)
557 return {};
558 // We don't want to handle words in string literals. (It'd be nice to list
559 // *allowed* token kinds explicitly, but comment Tokens aren't retained).
560 if (Word.PartOfSpelledToken &&
561 isStringLiteral(Word.PartOfSpelledToken->kind()))
562 return {};
563
564 const auto &SM = AST.getSourceManager();
565 // Look up the selected word in the index.
566 FuzzyFindRequest Req;
567 Req.Query = Word.Text.str();
568 Req.ProximityPaths = {MainFilePath.str()};
569 // Find the namespaces to query by lexing the file.
570 Req.Scopes =
571 visibleNamespaces(sourcePrefix(Word.Location, SM), AST.getLangOpts());
572 // FIXME: For extra strictness, consider AnyScope=false.
573 Req.AnyScope = true;
574 // We limit the results to 3 further below. This limit is to avoid fetching
575 // too much data, while still likely having enough for 3 results to remain
576 // after additional filtering.
577 Req.Limit = 10;
578 bool TooMany = false;
579 using ScoredLocatedSymbol = std::pair<float, LocatedSymbol>;
580 std::vector<ScoredLocatedSymbol> ScoredResults;
581 Index->fuzzyFind(Req, [&](const Symbol &Sym) {
582 // Only consider exact name matches, including case.
583 // This is to avoid too many false positives.
584 // We could relax this in the future (e.g. to allow for typos) if we make
585 // the query more accurate by other means.
586 if (Sym.Name != Word.Text)
587 return;
588
589 // Exclude constructor results. They have the same name as the class,
590 // but we don't have enough context to prefer them over the class.
591 if (Sym.SymInfo.Kind == index::SymbolKind::Constructor)
592 return;
593
594 auto MaybeDeclLoc =
595 indexToLSPLocation(Sym.CanonicalDeclaration, MainFilePath);
596 if (!MaybeDeclLoc) {
597 log("locateSymbolNamedTextuallyAt: {0}", MaybeDeclLoc.takeError());
598 return;
599 }
600 LocatedSymbol Located;
601 Located.PreferredDeclaration = *MaybeDeclLoc;
602 Located.Name = (Sym.Name + Sym.TemplateSpecializationArgs).str();
603 Located.ID = Sym.ID;
604 if (Sym.Definition) {
605 auto MaybeDefLoc = indexToLSPLocation(Sym.Definition, MainFilePath);
606 if (!MaybeDefLoc) {
607 log("locateSymbolNamedTextuallyAt: {0}", MaybeDefLoc.takeError());
608 return;
609 }
610 Located.PreferredDeclaration = *MaybeDefLoc;
611 Located.Definition = *MaybeDefLoc;
612 }
613
614 if (ScoredResults.size() >= 5) {
615 // If we have more than 5 results, don't return anything,
616 // as confidence is too low.
617 // FIXME: Alternatively, try a stricter query?
618 TooMany = true;
619 return;
620 }
621
622 SymbolQualitySignals Quality;
623 Quality.merge(Sym);
624 SymbolRelevanceSignals Relevance;
625 Relevance.Name = Sym.Name;
626 Relevance.Query = SymbolRelevanceSignals::Generic;
627 Relevance.merge(Sym);
628 auto Score = evaluateSymbolAndRelevance(Quality.evaluateHeuristics(),
629 Relevance.evaluateHeuristics());
630 dlog("locateSymbolNamedTextuallyAt: {0}{1} = {2}\n{3}{4}\n", Sym.Scope,
631 Sym.Name, Score, Quality, Relevance);
632
633 ScoredResults.push_back({Score, std::move(Located)});
634 });
635
636 if (TooMany) {
637 vlog("Heuristic index lookup for {0} returned too many candidates, ignored",
638 Word.Text);
639 return {};
640 }
641
642 llvm::sort(ScoredResults,
643 [](const ScoredLocatedSymbol &A, const ScoredLocatedSymbol &B) {
644 return A.first > B.first;
645 });
646 std::vector<LocatedSymbol> Results;
647 for (auto &Res : std::move(ScoredResults))
648 Results.push_back(std::move(Res.second));
649 if (Results.empty())
650 vlog("No heuristic index definition for {0}", Word.Text);
651 else
652 log("Found definition heuristically in index for {0}", Word.Text);
653 return Results;
654 }
655
656 const syntax::Token *findNearbyIdentifier(const SpelledWord &Word,
657 const syntax::TokenBuffer &TB) {
658 // Don't use heuristics if this is a real identifier.
659 // Unlikely identifiers are OK if they were used as identifiers nearby.
660 if (Word.ExpandedToken)
661 return nullptr;
662 // We don't want to handle words in string literals. (It'd be nice to list
663 // *allowed* token kinds explicitly, but comment Tokens aren't retained).
664 if (Word.PartOfSpelledToken &&
665 isStringLiteral(Word.PartOfSpelledToken->kind()))
666 return {};
667
668 const SourceManager &SM = TB.sourceManager();
669 // We prefer the closest possible token, line-wise. Backwards is penalized.
670 // Ties are implicitly broken by traversal order (first-one-wins).
671 auto File = SM.getFileID(Word.Location);
672 unsigned WordLine = SM.getSpellingLineNumber(Word.Location);
673 auto Cost = [&](SourceLocation Loc) -> unsigned {
674 assert(SM.getFileID(Loc) == File && "spelled token in wrong file?");
675 unsigned Line = SM.getSpellingLineNumber(Loc);
676 return Line >= WordLine ? Line - WordLine : 2 * (WordLine - Line);
677 };
678 const syntax::Token *BestTok = nullptr;
679 unsigned BestCost = -1;
680 // Search bounds are based on word length:
681 // - forward: 2^N lines
682 // - backward: 2^(N-1) lines.
683 unsigned MaxDistance =
684 1U << std::min<unsigned>(Word.Text.size(),
685 std::numeric_limits<unsigned>::digits - 1);
686 // Line number for SM.translateLineCol() should be one-based, also
687 // SM.translateLineCol() can handle line number greater than
688 // number of lines in the file.
689 // - LineMin = max(1, WordLine + 1 - 2^(N-1))
690 // - LineMax = WordLine + 1 + 2^N
691 unsigned LineMin =
692 WordLine + 1 <= MaxDistance / 2 ? 1 : WordLine + 1 - MaxDistance / 2;
693 unsigned LineMax = WordLine + 1 + MaxDistance;
694 SourceLocation LocMin = SM.translateLineCol(File, LineMin, 1);
695 assert(LocMin.isValid());
696 SourceLocation LocMax = SM.translateLineCol(File, LineMax, 1);
697 assert(LocMax.isValid());
698
699 // Updates BestTok and BestCost if Tok is a good candidate.
700 // May return true if the cost is too high for this token.
701 auto Consider = [&](const syntax::Token &Tok) {
702 if (Tok.location() < LocMin || Tok.location() > LocMax)
703 return true; // we are too far from the word, break the outer loop.
704 if (!(Tok.kind() == tok::identifier && Tok.text(SM) == Word.Text))
705 return false;
706 // No point guessing the same location we started with.
707 if (Tok.location() == Word.Location)
708 return false;
709 // We've done cheap checks, compute cost so we can break the caller's loop.
710 unsigned TokCost = Cost(Tok.location());
711 if (TokCost >= BestCost)
712 return true; // causes the outer loop to break.
713 // Allow locations that might be part of the AST, and macros (even if empty)
714 // but not things like disabled preprocessor sections.
715 if (!(tokenSpelledAt(Tok.location(), TB) || TB.expansionStartingAt(&Tok)))
716 return false;
717 // We already verified this token is an improvement.
718 BestCost = TokCost;
719 BestTok = &Tok;
720 return false;
721 };
722 auto SpelledTokens = TB.spelledTokens(File);
723 // Find where the word occurred in the token stream, to search forward & back.
724 auto *I = llvm::partition_point(SpelledTokens, [&](const syntax::Token &T) {
725 assert(SM.getFileID(T.location()) == SM.getFileID(Word.Location));
726 return T.location() < Word.Location; // Comparison OK: same file.
727 });
728 // Search for matches after the cursor.
729 for (const syntax::Token &Tok : llvm::ArrayRef(I, SpelledTokens.end()))
730 if (Consider(Tok))
731 break; // costs of later tokens are greater...
732 // Search for matches before the cursor.
733 for (const syntax::Token &Tok :
734 llvm::reverse(llvm::ArrayRef(SpelledTokens.begin(), I)))
735 if (Consider(Tok))
736 break;
737
738 if (BestTok)
739 vlog(
740 "Word {0} under cursor {1} isn't a token (after PP), trying nearby {2}",
741 Word.Text, Word.Location.printToString(SM),
742 BestTok->location().printToString(SM));
743
744 return BestTok;
745 }
746
747 std::vector<LocatedSymbol> locateSymbolAt(ParsedAST &AST, Position Pos,
748 const SymbolIndex *Index) {
749 const auto &SM = AST.getSourceManager();
750 auto MainFilePath = AST.tuPath();
751
752 if (auto File = locateFileReferent(Pos, AST, MainFilePath))
753 return {std::move(*File)};
754
755 auto CurLoc = sourceLocationInMainFile(SM, Pos);
756 if (!CurLoc) {
757 elog("locateSymbolAt failed to convert position to source location: {0}",
758 CurLoc.takeError());
759 return {};
760 }
761
762 const syntax::Token *TouchedIdentifier = nullptr;
763 auto TokensTouchingCursor =
764 syntax::spelledTokensTouching(*CurLoc, AST.getTokens());
765 for (const syntax::Token &Tok : TokensTouchingCursor) {
766 if (Tok.kind() == tok::identifier) {
767 if (auto Macro = locateMacroReferent(Tok, AST, MainFilePath))
768 // Don't look at the AST or index if we have a macro result.
769 // (We'd just return declarations referenced from the macro's
770 // expansion.)
771 return {*std::move(Macro)};
772
773 TouchedIdentifier = &Tok;
774 break;
775 }
776
777 if (Tok.kind() == tok::kw_auto || Tok.kind() == tok::kw_decltype) {
778 // go-to-definition on auto should find the definition of the deduced
779 // type, if possible
780 if (auto Deduced = getDeducedType(AST.getASTContext(), Tok.location())) {
781 auto LocSym = locateSymbolForType(AST, *Deduced);
782 if (!LocSym.empty())
783 return LocSym;
784 }
785 }
786 }
787
788 ASTNodeKind NodeKind;
789 auto ASTResults = locateASTReferent(*CurLoc, TouchedIdentifier, AST,
790 MainFilePath, Index, NodeKind);
791 if (!ASTResults.empty())
792 return ASTResults;
793
794 // If the cursor can't be resolved directly, try fallback strategies.
795 auto Word =
796 SpelledWord::touching(*CurLoc, AST.getTokens(), AST.getLangOpts());
797 if (Word) {
798 // Is the same word nearby a real identifier that might refer to something?
799 if (const syntax::Token *NearbyIdent =
800 findNearbyIdentifier(*Word, AST.getTokens())) {
801 if (auto Macro = locateMacroReferent(*NearbyIdent, AST, MainFilePath)) {
802 log("Found macro definition heuristically using nearby identifier {0}",
803 Word->Text);
804 return {*std::move(Macro)};
805 }
806 ASTResults = locateASTReferent(NearbyIdent->location(), NearbyIdent, AST,
807 MainFilePath, Index, NodeKind);
808 if (!ASTResults.empty()) {
809 log("Found definition heuristically using nearby identifier {0}",
810 NearbyIdent->text(SM));
811 return ASTResults;
812 }
813 vlog("No definition found using nearby identifier {0} at {1}", Word->Text,
814 Word->Location.printToString(SM));
815 }
816 // No nearby word, or it didn't refer to anything either. Try the index.
817 auto TextualResults =
818 locateSymbolTextually(*Word, AST, Index, MainFilePath, NodeKind);
819 if (!TextualResults.empty())
820 return TextualResults;
821 }
822
823 return {};
824 }
825
826 std::vector<DocumentLink> getDocumentLinks(ParsedAST &AST) {
827 const auto &SM = AST.getSourceManager();
828
829 std::vector<DocumentLink> Result;
830 for (auto &Inc : AST.getIncludeStructure().MainFileIncludes) {
831 if (Inc.Resolved.empty())
832 continue;
833 auto HashLoc = SM.getComposedLoc(SM.getMainFileID(), Inc.HashOffset);
834 const auto *HashTok = AST.getTokens().spelledTokenAt(HashLoc);
835 assert(HashTok && "got inclusion at wrong offset");
836 const auto *IncludeTok = std::next(HashTok);
837 const auto *FileTok = std::next(IncludeTok);
838 // FileTok->range is not sufficient here, as raw lexing wouldn't yield
839 // correct tokens for angled filenames. Hence we explicitly use
840 // Inc.Written's length.
841 auto FileRange =
842 syntax::FileRange(SM, FileTok->location(), Inc.Written.length())
843 .toCharRange(SM);
844
845 Result.push_back(
846 DocumentLink({halfOpenToRange(SM, FileRange),
847 URIForFile::canonicalize(Inc.Resolved, AST.tuPath())}));
848 }
849
850 return Result;
851 }
852
853 namespace {
854
855 /// Collects references to symbols within the main file.
856 class ReferenceFinder : public index::IndexDataConsumer {
857 public:
858 struct Reference {
859 syntax::Token SpelledTok;
860 index::SymbolRoleSet Role;
861 const Decl *Container;
862
863 Range range(const SourceManager &SM) const {
864 return halfOpenToRange(SM, SpelledTok.range(SM).toCharRange(SM));
865 }
866 };
867
868 ReferenceFinder(const ParsedAST &AST,
869 const llvm::ArrayRef<const NamedDecl *> Targets,
870 bool PerToken)
871 : PerToken(PerToken), AST(AST) {
872 for (const NamedDecl *ND : Targets)
873 TargetDecls.insert(ND->getCanonicalDecl());
874 }
875
876 std::vector<Reference> take() && {
877 llvm::sort(References, [](const Reference &L, const Reference &R) {
878 auto LTok = L.SpelledTok.location();
879 auto RTok = R.SpelledTok.location();
880 return std::tie(LTok, L.Role) < std::tie(RTok, R.Role);
881 });
882 // We sometimes see duplicates when parts of the AST get traversed twice.
883 References.erase(std::unique(References.begin(), References.end(),
884 [](const Reference &L, const Reference &R) {
885 auto LTok = L.SpelledTok.location();
886 auto RTok = R.SpelledTok.location();
887 return std::tie(LTok, L.Role) ==
888 std::tie(RTok, R.Role);
889 }),
890 References.end());
891 return std::move(References);
892 }
893
894 bool
895 handleDeclOccurrence(const Decl *D, index::SymbolRoleSet Roles,
896 llvm::ArrayRef<index::SymbolRelation> Relations,
897 SourceLocation Loc,
898 index::IndexDataConsumer::ASTNodeInfo ASTNode) override {
899 if (!TargetDecls.contains(D->getCanonicalDecl()))
900 return true;
901 const SourceManager &SM = AST.getSourceManager();
902 if (!isInsideMainFile(Loc, SM))
903 return true;
904 const auto &TB = AST.getTokens();
905
906 llvm::SmallVector<SourceLocation, 1> Locs;
907 if (PerToken) {
908 // Check whether this is one of the few constructs where the reference
909 // can be split over several tokens.
910 if (auto *OME = llvm::dyn_cast_or_null<ObjCMessageExpr>(ASTNode.OrigE)) {
911 OME->getSelectorLocs(Locs);
912 } else if (auto *OMD =
913 llvm::dyn_cast_or_null<ObjCMethodDecl>(ASTNode.OrigD)) {
914 OMD->getSelectorLocs(Locs);
915 }
916 // Sanity check: we expect the *first* token to match the reported loc.
917 // Otherwise, maybe it was e.g. some other kind of reference to a Decl.
918 if (!Locs.empty() && Locs.front() != Loc)
919 Locs.clear(); // First token doesn't match, assume our guess was wrong.
920 }
921 if (Locs.empty())
922 Locs.push_back(Loc);
923
924 SymbolCollector::Options CollectorOpts;
925 CollectorOpts.CollectMainFileSymbols = true;
926 for (SourceLocation L : Locs) {
927 L = SM.getFileLoc(L);
928 if (const auto *Tok = TB.spelledTokenAt(L))
929 References.push_back(
930 {*Tok, Roles,
931 SymbolCollector::getRefContainer(ASTNode.Parent, CollectorOpts)});
932 }
933 return true;
934 }
935
936 private:
937 bool PerToken; // If true, report 3 references for split ObjC selector names.
938 std::vector<Reference> References;
939 const ParsedAST &AST;
940 llvm::DenseSet<const Decl *> TargetDecls;
941 };
942
943 std::vector<ReferenceFinder::Reference>
944 findRefs(const llvm::ArrayRef<const NamedDecl *> TargetDecls, ParsedAST &AST,
945 bool PerToken) {
946 ReferenceFinder RefFinder(AST, TargetDecls, PerToken);
947 index::IndexingOptions IndexOpts;
948 IndexOpts.SystemSymbolFilter =
949 index::IndexingOptions::SystemSymbolFilterKind::All;
950 IndexOpts.IndexFunctionLocals = true;
951 IndexOpts.IndexParametersInDeclarations = true;
952 IndexOpts.IndexTemplateParameters = true;
953 indexTopLevelDecls(AST.getASTContext(), AST.getPreprocessor(),
954 AST.getLocalTopLevelDecls(), RefFinder, IndexOpts);
955 return std::move(RefFinder).take();
956 }
957
958 const Stmt *getFunctionBody(DynTypedNode N) {
959 if (const auto *FD = N.get<FunctionDecl>())
960 return FD->getBody();
961 if (const auto *FD = N.get<BlockDecl>())
962 return FD->getBody();
963 if (const auto *FD = N.get<LambdaExpr>())
964 return FD->getBody();
965 if (const auto *FD = N.get<ObjCMethodDecl>())
966 return FD->getBody();
967 return nullptr;
968 }
969
970 const Stmt *getLoopBody(DynTypedNode N) {
971 if (const auto *LS = N.get<ForStmt>())
972 return LS->getBody();
973 if (const auto *LS = N.get<CXXForRangeStmt>())
974 return LS->getBody();
975 if (const auto *LS = N.get<WhileStmt>())
976 return LS->getBody();
977 if (const auto *LS = N.get<DoStmt>())
978 return LS->getBody();
979 return nullptr;
980 }
981
982 // AST traversal to highlight control flow statements under some root.
983 // Once we hit further control flow we prune the tree (or at least restrict
984 // what we highlight) so we capture e.g. breaks from the outer loop only.
985 class FindControlFlow : public RecursiveASTVisitor<FindControlFlow> {
986 // Types of control-flow statements we might highlight.
987 enum Target {
988 Break = 1,
989 Continue = 2,
990 Return = 4,
991 Case = 8,
992 Throw = 16,
993 Goto = 32,
994 All = Break | Continue | Return | Case | Throw | Goto,
995 };
996 int Ignore = 0; // bitmask of Target - what are we *not* highlighting?
997 SourceRange Bounds; // Half-open, restricts reported targets.
998 std::vector<SourceLocation> &Result;
999 const SourceManager &SM;
1000
1001 // Masks out targets for a traversal into D.
1002 // Traverses the subtree using Delegate() if any targets remain.
1003 template <typename Func>
1004 bool filterAndTraverse(DynTypedNode D, const Func &Delegate) {
1005 auto RestoreIgnore = llvm::make_scope_exit(
1006 [OldIgnore(Ignore), this] { Ignore = OldIgnore; });
1007 if (getFunctionBody(D))
1008 Ignore = All;
1009 else if (getLoopBody(D))
1010 Ignore |= Continue | Break;
1011 else if (D.get<SwitchStmt>())
1012 Ignore |= Break | Case;
1013 // Prune tree if we're not looking for anything.
1014 return (Ignore == All) ? true : Delegate();
1015 }
1016
1017 void found(Target T, SourceLocation Loc) {
1018 if (T & Ignore)
1019 return;
1020 if (SM.isBeforeInTranslationUnit(Loc, Bounds.getBegin()) ||
1021 SM.isBeforeInTranslationUnit(Bounds.getEnd(), Loc))
1022 return;
1023 Result.push_back(Loc);
1024 }
1025
1026 public:
1027 FindControlFlow(SourceRange Bounds, std::vector<SourceLocation> &Result,
1028 const SourceManager &SM)
1029 : Bounds(Bounds), Result(Result), SM(SM) {}
1030
1031 // When traversing function or loops, limit targets to those that still
1032 // refer to the original root.
1033 bool TraverseDecl(Decl *D) {
1034 return !D || filterAndTraverse(DynTypedNode::create(*D), [&] {
1035 return RecursiveASTVisitor::TraverseDecl(D);
1036 });
1037 }
1038 bool TraverseStmt(Stmt *S) {
1039 return !S || filterAndTraverse(DynTypedNode::create(*S), [&] {
1040 return RecursiveASTVisitor::TraverseStmt(S);
1041 });
1042 }
1043
1044 // Add leaves that we found and want.
1045 bool VisitReturnStmt(ReturnStmt *R) {
1046 found(Return, R->getReturnLoc());
1047 return true;
1048 }
1049 bool VisitBreakStmt(BreakStmt *B) {
1050 found(Break, B->getBreakLoc());
1051 return true;
1052 }
1053 bool VisitContinueStmt(ContinueStmt *C) {
1054 found(Continue, C->getContinueLoc());
1055 return true;
1056 }
1057 bool VisitSwitchCase(SwitchCase *C) {
1058 found(Case, C->getKeywordLoc());
1059 return true;
1060 }
1061 bool VisitCXXThrowExpr(CXXThrowExpr *T) {
1062 found(Throw, T->getThrowLoc());
1063 return true;
1064 }
1065 bool VisitGotoStmt(GotoStmt *G) {
1066 // Goto is interesting if its target is outside the root.
1067 if (const auto *LD = G->getLabel()) {
1068 if (SM.isBeforeInTranslationUnit(LD->getLocation(), Bounds.getBegin()) ||
1069 SM.isBeforeInTranslationUnit(Bounds.getEnd(), LD->getLocation()))
1070 found(Goto, G->getGotoLoc());
1071 }
1072 return true;
1073 }
1074 };
1075
1076 // Given a location within a switch statement, return the half-open range that
1077 // covers the case it's contained in.
1078 // We treat `case X: case Y: ...` as one case, and assume no other fallthrough.
1079 SourceRange findCaseBounds(const SwitchStmt &Switch, SourceLocation Loc,
1080 const SourceManager &SM) {
1081 // Cases are not stored in order, sort them first.
1082 // (In fact they seem to be stored in reverse order, don't rely on this)
1083 std::vector<const SwitchCase *> Cases;
1084 for (const SwitchCase *Case = Switch.getSwitchCaseList(); Case;
1085 Case = Case->getNextSwitchCase())
1086 Cases.push_back(Case);
1087 llvm::sort(Cases, [&](const SwitchCase *L, const SwitchCase *R) {
1088 return SM.isBeforeInTranslationUnit(L->getKeywordLoc(), R->getKeywordLoc());
1089 });
1090
1091 // Find the first case after the target location, the end of our range.
1092 auto CaseAfter = llvm::partition_point(Cases, [&](const SwitchCase *C) {
1093 return !SM.isBeforeInTranslationUnit(Loc, C->getKeywordLoc());
1094 });
1095 SourceLocation End = CaseAfter == Cases.end() ? Switch.getEndLoc()
1096 : (*CaseAfter)->getKeywordLoc();
1097
1098 // Our target can be before the first case - cases are optional!
1099 if (CaseAfter == Cases.begin())
1100 return SourceRange(Switch.getBeginLoc(), End);
1101 // The start of our range is usually the previous case, but...
1102 auto CaseBefore = std::prev(CaseAfter);
1103 // ... rewind CaseBefore to the first in a `case A: case B: ...` sequence.
1104 while (CaseBefore != Cases.begin() &&
1105 (*std::prev(CaseBefore))->getSubStmt() == *CaseBefore)
1106 --CaseBefore;
1107 return SourceRange((*CaseBefore)->getKeywordLoc(), End);
1108 }
1109
1110 // Returns the locations of control flow statements related to N. e.g.:
1111 // for => branches: break/continue/return/throw
1112 // break => controlling loop (forwhile/do), and its related control flow
1113 // return => all returns/throws from the same function
1114 // When an inner block is selected, we include branches bound to outer blocks
1115 // as these are exits from the inner block. e.g. return in a for loop.
1116 // FIXME: We don't analyze catch blocks, throw is treated the same as return.
1117 std::vector<SourceLocation> relatedControlFlow(const SelectionTree::Node &N) {
1118 const SourceManager &SM =
1119 N.getDeclContext().getParentASTContext().getSourceManager();
1120 std::vector<SourceLocation> Result;
1121
1122 // First, check if we're at a node that can resolve to a root.
1123 enum class Cur { None, Break, Continue, Return, Case, Throw } Cursor;
1124 if (N.ASTNode.get<BreakStmt>()) {
1125 Cursor = Cur::Break;
1126 } else if (N.ASTNode.get<ContinueStmt>()) {
1127 Cursor = Cur::Continue;
1128 } else if (N.ASTNode.get<ReturnStmt>()) {
1129 Cursor = Cur::Return;
1130 } else if (N.ASTNode.get<CXXThrowExpr>()) {
1131 Cursor = Cur::Throw;
1132 } else if (N.ASTNode.get<SwitchCase>()) {
1133 Cursor = Cur::Case;
1134 } else if (const GotoStmt *GS = N.ASTNode.get<GotoStmt>()) {
1135 // We don't know what root to associate with, but highlight the goto/label.
1136 Result.push_back(GS->getGotoLoc());
1137 if (const auto *LD = GS->getLabel())
1138 Result.push_back(LD->getLocation());
1139 Cursor = Cur::None;
1140 } else {
1141 Cursor = Cur::None;
1142 }
1143
1144 const Stmt *Root = nullptr; // Loop or function body to traverse.
1145 SourceRange Bounds;
1146 // Look up the tree for a root (or just at this node if we didn't find a leaf)
1147 for (const auto *P = &N; P; P = P->Parent) {
1148 // return associates with enclosing function
1149 if (const Stmt *FunctionBody = getFunctionBody(P->ASTNode)) {
1150 if (Cursor == Cur::Return || Cursor == Cur::Throw) {
1151 Root = FunctionBody;
1152 }
1153 break; // other leaves don't cross functions.
1154 }
1155 // break/continue associate with enclosing loop.
1156 if (const Stmt *LoopBody = getLoopBody(P->ASTNode)) {
1157 if (Cursor == Cur::None || Cursor == Cur::Break ||
1158 Cursor == Cur::Continue) {
1159 Root = LoopBody;
1160 // Highlight the loop keyword itself.
1161 // FIXME: for do-while, this only covers the `do`..
1162 Result.push_back(P->ASTNode.getSourceRange().getBegin());
1163 break;
1164 }
1165 }
1166 // For switches, users think of case statements as control flow blocks.
1167 // We highlight only occurrences surrounded by the same case.
1168 // We don't detect fallthrough (other than 'case X, case Y').
1169 if (const auto *SS = P->ASTNode.get<SwitchStmt>()) {
1170 if (Cursor == Cur::Break || Cursor == Cur::Case) {
1171 Result.push_back(SS->getSwitchLoc()); // Highlight the switch.
1172 Root = SS->getBody();
1173 // Limit to enclosing case, if there is one.
1174 Bounds = findCaseBounds(*SS, N.ASTNode.getSourceRange().getBegin(), SM);
1175 break;
1176 }
1177 }
1178 // If we didn't start at some interesting node, we're done.
1179 if (Cursor == Cur::None)
1180 break;
1181 }
1182 if (Root) {
1183 if (!Bounds.isValid())
1184 Bounds = Root->getSourceRange();
1185 FindControlFlow(Bounds, Result, SM).TraverseStmt(const_cast<Stmt *>(Root));
1186 }
1187 return Result;
1188 }
1189
1190 DocumentHighlight toHighlight(const ReferenceFinder::Reference &Ref,
1191 const SourceManager &SM) {
1192 DocumentHighlight DH;
1193 DH.range = Ref.range(SM);
1194 if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Write))
1195 DH.kind = DocumentHighlightKind::Write;
1196 else if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Read))
1197 DH.kind = DocumentHighlightKind::Read;
1198 else
1199 DH.kind = DocumentHighlightKind::Text;
1200 return DH;
1201 }
1202
1203 std::optional<DocumentHighlight> toHighlight(SourceLocation Loc,
1204 const syntax::TokenBuffer &TB) {
1205 Loc = TB.sourceManager().getFileLoc(Loc);
1206 if (const auto *Tok = TB.spelledTokenAt(Loc)) {
1207 DocumentHighlight Result;
1208 Result.range = halfOpenToRange(
1209 TB.sourceManager(),
1210 CharSourceRange::getCharRange(Tok->location(), Tok->endLocation()));
1211 return Result;
1212 }
1213 return std::nullopt;
1214 }
1215
1216 } // namespace
1217
1218 std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,
1219 Position Pos) {
1220 const SourceManager &SM = AST.getSourceManager();
1221 // FIXME: show references to macro within file?
1222 auto CurLoc = sourceLocationInMainFile(SM, Pos);
1223 if (!CurLoc) {
1224 llvm::consumeError(CurLoc.takeError());
1225 return {};
1226 }
1227 std::vector<DocumentHighlight> Result;
1228 auto TryTree = [&](SelectionTree ST) {
1229 if (const SelectionTree::Node *N = ST.commonAncestor()) {
1230 DeclRelationSet Relations =
1231 DeclRelation::TemplatePattern | DeclRelation::Alias;
1232 auto TargetDecls =
1233 targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver());
1234 if (!TargetDecls.empty()) {
1235 // FIXME: we may get multiple DocumentHighlights with the same location
1236 // and different kinds, deduplicate them.
1237 for (const auto &Ref : findRefs(TargetDecls, AST, /*PerToken=*/true))
1238 Result.push_back(toHighlight(Ref, SM));
1239 return true;
1240 }
1241 auto ControlFlow = relatedControlFlow(*N);
1242 if (!ControlFlow.empty()) {
1243 for (SourceLocation Loc : ControlFlow)
1244 if (auto Highlight = toHighlight(Loc, AST.getTokens()))
1245 Result.push_back(std::move(*Highlight));
1246 return true;
1247 }
1248 }
1249 return false;
1250 };
1251
1252 unsigned Offset =
1253 AST.getSourceManager().getDecomposedSpellingLoc(*CurLoc).second;
1254 SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset,
1255 Offset, TryTree);
1256 return Result;
1257 }
1258
1259 std::vector<LocatedSymbol> findImplementations(ParsedAST &AST, Position Pos,
1260 const SymbolIndex *Index) {
1261 // We rely on index to find the implementations in subclasses.
1262 // FIXME: Index can be stale, so we may loose some latest results from the
1263 // main file.
1264 if (!Index)
1265 return {};
1266 const SourceManager &SM = AST.getSourceManager();
1267 auto CurLoc = sourceLocationInMainFile(SM, Pos);
1268 if (!CurLoc) {
1269 elog("Failed to convert position to source location: {0}",
1270 CurLoc.takeError());
1271 return {};
1272 }
1273 DeclRelationSet Relations =
1274 DeclRelation::TemplatePattern | DeclRelation::Alias;
1275 llvm::DenseSet<SymbolID> IDs;
1276 RelationKind QueryKind = RelationKind::OverriddenBy;
1277 for (const NamedDecl *ND : getDeclAtPosition(AST, *CurLoc, Relations)) {
1278 if (const auto *CXXMD = llvm::dyn_cast<CXXMethodDecl>(ND)) {
1279 if (CXXMD->isVirtual()) {
1280 IDs.insert(getSymbolID(ND));
1281 QueryKind = RelationKind::OverriddenBy;
1282 }
1283 } else if (const auto *RD = dyn_cast<CXXRecordDecl>(ND)) {
1284 IDs.insert(getSymbolID(RD));
1285 QueryKind = RelationKind::BaseOf;
1286 }
1287 }
1288 return findImplementors(std::move(IDs), QueryKind, Index, AST.tuPath());
1289 }
1290
1291 namespace {
1292 // Recursively finds all the overridden methods of `CMD` in complete type
1293 // hierarchy.
1294 void getOverriddenMethods(const CXXMethodDecl *CMD,
1295 llvm::DenseSet<SymbolID> &OverriddenMethods) {
1296 if (!CMD)
1297 return;
1298 for (const CXXMethodDecl *Base : CMD->overridden_methods()) {
1299 if (auto ID = getSymbolID(Base))
1300 OverriddenMethods.insert(ID);
1301 getOverriddenMethods(Base, OverriddenMethods);
1302 }
1303 }
1304
1305 std::optional<std::string>
1306 stringifyContainerForMainFileRef(const Decl *Container) {
1307 // FIXME We might also want to display the signature here
1308 // When doing so, remember to also add the Signature to index results!
1309 if (auto *ND = llvm::dyn_cast_if_present<NamedDecl>(Container))
1310 return printQualifiedName(*ND);
1311 return {};
1312 }
1313 } // namespace
1314
1315 ReferencesResult findReferences(ParsedAST &AST, Position Pos, uint32_t Limit,
1316 const SymbolIndex *Index, bool AddContext) {
1317 ReferencesResult Results;
1318 const SourceManager &SM = AST.getSourceManager();
1319 auto MainFilePath = AST.tuPath();
1320 auto URIMainFile = URIForFile::canonicalize(MainFilePath, MainFilePath);
1321 auto CurLoc = sourceLocationInMainFile(SM, Pos);
1322 if (!CurLoc) {
1323 llvm::consumeError(CurLoc.takeError());
1324 return {};
1325 }
1326
1327 llvm::DenseSet<SymbolID> IDsToQuery, OverriddenMethods;
1328
1329 const auto *IdentifierAtCursor =
1330 syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens());
1331 std::optional<DefinedMacro> Macro;
1332 if (IdentifierAtCursor)
1333 Macro = locateMacroAt(*IdentifierAtCursor, AST.getPreprocessor());
1334 if (Macro) {
1335 // Handle references to macro.
1336 if (auto MacroSID = getSymbolID(Macro->Name, Macro->Info, SM)) {
1337 // Collect macro references from main file.
1338 const auto &IDToRefs = AST.getMacros().MacroRefs;
1339 auto Refs = IDToRefs.find(MacroSID);
1340 if (Refs != IDToRefs.end()) {
1341 for (const auto &Ref : Refs->second) {
1342 ReferencesResult::Reference Result;
1343 Result.Loc.range = Ref.Rng;
1344 Result.Loc.uri = URIMainFile;
1345 if (Ref.IsDefinition) {
1346 Result.Attributes |= ReferencesResult::Declaration;
1347 Result.Attributes |= ReferencesResult::Definition;
1348 }
1349 Results.References.push_back(std::move(Result));
1350 }
1351 }
1352 IDsToQuery.insert(MacroSID);
1353 }
1354 } else {
1355 // Handle references to Decls.
1356
1357 DeclRelationSet Relations =
1358 DeclRelation::TemplatePattern | DeclRelation::Alias;
1359 std::vector<const NamedDecl *> Decls =
1360 getDeclAtPosition(AST, *CurLoc, Relations);
1361 llvm::SmallVector<const NamedDecl *> TargetsInMainFile;
1362 for (const NamedDecl *D : Decls) {
1363 auto ID = getSymbolID(D);
1364 if (!ID)
1365 continue;
1366 TargetsInMainFile.push_back(D);
1367 // Not all symbols can be referenced from outside (e.g. function-locals).
1368 // TODO: we could skip TU-scoped symbols here (e.g. static functions) if
1369 // we know this file isn't a header. The details might be tricky.
1370 if (D->getParentFunctionOrMethod())
1371 continue;
1372 IDsToQuery.insert(ID);
1373 }
1374
1375 RelationsRequest OverriddenBy;
1376 if (Index) {
1377 OverriddenBy.Predicate = RelationKind::OverriddenBy;
1378 for (const NamedDecl *ND : Decls) {
1379 // Special case: For virtual methods, report decl/def of overrides and
1380 // references to all overridden methods in complete type hierarchy.
1381 if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(ND)) {
1382 if (CMD->isVirtual()) {
1383 if (auto ID = getSymbolID(CMD))
1384 OverriddenBy.Subjects.insert(ID);
1385 getOverriddenMethods(CMD, OverriddenMethods);
1386 }
1387 }
1388 }
1389 }
1390
1391 // We traverse the AST to find references in the main file.
1392 auto MainFileRefs = findRefs(TargetsInMainFile, AST, /*PerToken=*/false);
1393 // We may get multiple refs with the same location and different Roles, as
1394 // cross-reference is only interested in locations, we deduplicate them
1395 // by the location to avoid emitting duplicated locations.
1396 MainFileRefs.erase(std::unique(MainFileRefs.begin(), MainFileRefs.end(),
1397 [](const ReferenceFinder::Reference &L,
1398 const ReferenceFinder::Reference &R) {
1399 return L.SpelledTok.location() ==
1400 R.SpelledTok.location();
1401 }),
1402 MainFileRefs.end());
1403 for (const auto &Ref : MainFileRefs) {
1404 ReferencesResult::Reference Result;
1405 Result.Loc.range = Ref.range(SM);
1406 Result.Loc.uri = URIMainFile;
1407 if (AddContext)
1408 Result.Loc.containerName =
1409 stringifyContainerForMainFileRef(Ref.Container);
1410 if (Ref.Role & static_cast<unsigned>(index::SymbolRole::Declaration))
1411 Result.Attributes |= ReferencesResult::Declaration;
1412 // clang-index doesn't report definitions as declarations, but they are.
1413 if (Ref.Role & static_cast<unsigned>(index::SymbolRole::Definition))
1414 Result.Attributes |=
1415 ReferencesResult::Definition | ReferencesResult::Declaration;
1416 Results.References.push_back(std::move(Result));
1417 }
1418 // Add decl/def of overridding methods.
1419 if (Index && !OverriddenBy.Subjects.empty()) {
1420 LookupRequest ContainerLookup;
1421 // Different overrides will always be contained in different classes, so
1422 // we have a one-to-one mapping between SymbolID and index here, thus we
1423 // don't need to use std::vector as the map's value type.
1424 llvm::DenseMap<SymbolID, size_t> RefIndexForContainer;
1425 Index->relations(OverriddenBy, [&](const SymbolID &Subject,
1426 const Symbol &Object) {
1427 if (Limit && Results.References.size() >= Limit) {
1428 Results.HasMore = true;
1429 return;
1430 }
1431 const auto LSPLocDecl =
1432 toLSPLocation(Object.CanonicalDeclaration, MainFilePath);
1433 const auto LSPLocDef = toLSPLocation(Object.Definition, MainFilePath);
1434 if (LSPLocDecl && LSPLocDecl != LSPLocDef) {
1435 ReferencesResult::Reference Result;
1436 Result.Loc = {std::move(*LSPLocDecl), std::nullopt};
1437 Result.Attributes =
1438 ReferencesResult::Declaration | ReferencesResult::Override;
1439 RefIndexForContainer.insert({Object.ID, Results.References.size()});
1440 ContainerLookup.IDs.insert(Object.ID);
1441 Results.References.push_back(std::move(Result));
1442 }
1443 if (LSPLocDef) {
1444 ReferencesResult::Reference Result;
1445 Result.Loc = {std::move(*LSPLocDef), std::nullopt};
1446 Result.Attributes = ReferencesResult::Declaration |
1447 ReferencesResult::Definition |
1448 ReferencesResult::Override;
1449 RefIndexForContainer.insert({Object.ID, Results.References.size()});
1450 ContainerLookup.IDs.insert(Object.ID);
1451 Results.References.push_back(std::move(Result));
1452 }
1453 });
1454
1455 if (!ContainerLookup.IDs.empty() && AddContext)
1456 Index->lookup(ContainerLookup, [&](const Symbol &Container) {
1457 auto Ref = RefIndexForContainer.find(Container.ID);
1458 assert(Ref != RefIndexForContainer.end());
1459 Results.References[Ref->getSecond()].Loc.containerName =
1460 Container.Scope.str() + Container.Name.str();
1461 });
1462 }
1463 }
1464 // Now query the index for references from other files.
1465 auto QueryIndex = [&](llvm::DenseSet<SymbolID> IDs, bool AllowAttributes,
1466 bool AllowMainFileSymbols) {
1467 if (IDs.empty() || !Index || Results.HasMore)
1468 return;
1469 RefsRequest Req;
1470 Req.IDs = std::move(IDs);
1471 if (Limit) {
1472 if (Limit < Results.References.size()) {
1473 // We've already filled our quota, still check the index to correctly
1474 // return the `HasMore` info.
1475 Req.Limit = 0;
1476 } else {
1477 // Query index only for the remaining size.
1478 Req.Limit = Limit - Results.References.size();
1479 }
1480 }
1481 LookupRequest ContainerLookup;
1482 llvm::DenseMap<SymbolID, std::vector<size_t>> RefIndicesForContainer;
1483 Results.HasMore |= Index->refs(Req, [&](const Ref &R) {
1484 auto LSPLoc = toLSPLocation(R.Location, MainFilePath);
1485 // Avoid indexed results for the main file - the AST is authoritative.
1486 if (!LSPLoc ||
1487 (!AllowMainFileSymbols && LSPLoc->uri.file() == MainFilePath))
1488 return;
1489 ReferencesResult::Reference Result;
1490 Result.Loc = {std::move(*LSPLoc), std::nullopt};
1491 if (AllowAttributes) {
1492 if ((R.Kind & RefKind::Declaration) == RefKind::Declaration)
1493 Result.Attributes |= ReferencesResult::Declaration;
1494 // FIXME: our index should definitely store def | decl separately!
1495 if ((R.Kind & RefKind::Definition) == RefKind::Definition)
1496 Result.Attributes |=
1497 ReferencesResult::Declaration | ReferencesResult::Definition;
1498 }
1499 if (AddContext) {
1500 SymbolID Container = R.Container;
1501 ContainerLookup.IDs.insert(Container);
1502 RefIndicesForContainer[Container].push_back(Results.References.size());
1503 }
1504 Results.References.push_back(std::move(Result));
1505 });
1506
1507 if (!ContainerLookup.IDs.empty() && AddContext)
1508 Index->lookup(ContainerLookup, [&](const Symbol &Container) {
1509 auto Ref = RefIndicesForContainer.find(Container.ID);
1510 assert(Ref != RefIndicesForContainer.end());
1511 auto ContainerName = Container.Scope.str() + Container.Name.str();
1512 for (auto I : Ref->getSecond()) {
1513 Results.References[I].Loc.containerName = ContainerName;
1514 }
1515 });
1516 };
1517 QueryIndex(std::move(IDsToQuery), /*AllowAttributes=*/true,
1518 /*AllowMainFileSymbols=*/false);
1519 // For a virtual method: Occurrences of BaseMethod should be treated as refs
1520 // and not as decl/def. Allow symbols from main file since AST does not report
1521 // these.
1522 QueryIndex(std::move(OverriddenMethods), /*AllowAttributes=*/false,
1523 /*AllowMainFileSymbols=*/true);
1524 return Results;
1525 }
1526
1527 std::vector<SymbolDetails> getSymbolInfo(ParsedAST &AST, Position Pos) {
1528 const SourceManager &SM = AST.getSourceManager();
1529 auto CurLoc = sourceLocationInMainFile(SM, Pos);
1530 if (!CurLoc) {
1531 llvm::consumeError(CurLoc.takeError());
1532 return {};
1533 }
1534 auto MainFilePath = AST.tuPath();
1535 std::vector<SymbolDetails> Results;
1536
1537 // We also want the targets of using-decls, so we include
1538 // DeclRelation::Underlying.
1539 DeclRelationSet Relations = DeclRelation::TemplatePattern |
1540 DeclRelation::Alias | DeclRelation::Underlying;
1541 for (const NamedDecl *D : getDeclAtPosition(AST, *CurLoc, Relations)) {
1542 D = getPreferredDecl(D);
1543
1544 SymbolDetails NewSymbol;
1545 std::string QName = printQualifiedName(*D);
1546 auto SplitQName = splitQualifiedName(QName);
1547 NewSymbol.containerName = std::string(SplitQName.first);
1548 NewSymbol.name = std::string(SplitQName.second);
1549
1550 if (NewSymbol.containerName.empty()) {
1551 if (const auto *ParentND =
1552 dyn_cast_or_null<NamedDecl>(D->getDeclContext()))
1553 NewSymbol.containerName = printQualifiedName(*ParentND);
1554 }
1555 llvm::SmallString<32> USR;
1556 if (!index::generateUSRForDecl(D, USR)) {
1557 NewSymbol.USR = std::string(USR.str());
1558 NewSymbol.ID = SymbolID(NewSymbol.USR);
1559 }
1560 if (const NamedDecl *Def = getDefinition(D))
1561 NewSymbol.definitionRange = makeLocation(
1562 AST.getASTContext(), nameLocation(*Def, SM), MainFilePath);
1563 NewSymbol.declarationRange =
1564 makeLocation(AST.getASTContext(), nameLocation(*D, SM), MainFilePath);
1565
1566 Results.push_back(std::move(NewSymbol));
1567 }
1568
1569 const auto *IdentifierAtCursor =
1570 syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens());
1571 if (!IdentifierAtCursor)
1572 return Results;
1573
1574 if (auto M = locateMacroAt(*IdentifierAtCursor, AST.getPreprocessor())) {
1575 SymbolDetails NewMacro;
1576 NewMacro.name = std::string(M->Name);
1577 llvm::SmallString<32> USR;
1578 if (!index::generateUSRForMacro(NewMacro.name, M->Info->getDefinitionLoc(),
1579 SM, USR)) {
1580 NewMacro.USR = std::string(USR.str());
1581 NewMacro.ID = SymbolID(NewMacro.USR);
1582 }
1583 Results.push_back(std::move(NewMacro));
1584 }
1585
1586 return Results;
1587 }
1588
1589 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const LocatedSymbol &S) {
1590 OS << S.Name << ": " << S.PreferredDeclaration;
1591 if (S.Definition)
1592 OS << " def=" << *S.Definition;
1593 return OS;
1594 }
1595
1596 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
1597 const ReferencesResult::Reference &R) {
1598 OS << R.Loc;
1599 if (R.Attributes & ReferencesResult::Declaration)
1600 OS << " [decl]";
1601 if (R.Attributes & ReferencesResult::Definition)
1602 OS << " [def]";
1603 if (R.Attributes & ReferencesResult::Override)
1604 OS << " [override]";
1605 return OS;
1606 }
1607
1608 template <typename HierarchyItem>
1609 static std::optional<HierarchyItem>
1610 declToHierarchyItem(const NamedDecl &ND, llvm::StringRef TUPath) {
1611 ASTContext &Ctx = ND.getASTContext();
1612 auto &SM = Ctx.getSourceManager();
1613 SourceLocation NameLoc = nameLocation(ND, Ctx.getSourceManager());
1614 SourceLocation BeginLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getBeginLoc()));
1615 SourceLocation EndLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getEndLoc()));
1616 const auto DeclRange =
1617 toHalfOpenFileRange(SM, Ctx.getLangOpts(), {BeginLoc, EndLoc});
1618 if (!DeclRange)
1619 return std::nullopt;
1620 auto FilePath =
1621 getCanonicalPath(SM.getFileEntryForID(SM.getFileID(NameLoc)), SM);
1622 if (!FilePath)
1623 return std::nullopt; // Not useful without a uri.
1624
1625 Position NameBegin = sourceLocToPosition(SM, NameLoc);
1626 Position NameEnd = sourceLocToPosition(
1627 SM, Lexer::getLocForEndOfToken(NameLoc, 0, SM, Ctx.getLangOpts()));
1628
1629 index::SymbolInfo SymInfo = index::getSymbolInfo(&ND);
1630 // FIXME: This is not classifying constructors, destructors and operators
1631 // correctly.
1632 SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind);
1633
1634 HierarchyItem HI;
1635 HI.name = printName(Ctx, ND);
1636 HI.kind = SK;
1637 HI.range = Range{sourceLocToPosition(SM, DeclRange->getBegin()),
1638 sourceLocToPosition(SM, DeclRange->getEnd())};
1639 HI.selectionRange = Range{NameBegin, NameEnd};
1640 if (!HI.range.contains(HI.selectionRange)) {
1641 // 'selectionRange' must be contained in 'range', so in cases where clang
1642 // reports unrelated ranges we need to reconcile somehow.
1643 HI.range = HI.selectionRange;
1644 }
1645
1646 HI.uri = URIForFile::canonicalize(*FilePath, TUPath);
1647
1648 return HI;
1649 }
1650
1651 static std::optional<TypeHierarchyItem>
1652 declToTypeHierarchyItem(const NamedDecl &ND, llvm::StringRef TUPath) {
1653 auto Result = declToHierarchyItem<TypeHierarchyItem>(ND, TUPath);
1654 if (Result) {
1655 Result->deprecated = ND.isDeprecated();
1656 // Compute the SymbolID and store it in the 'data' field.
1657 // This allows typeHierarchy/resolve to be used to
1658 // resolve children of items returned in a previous request
1659 // for parents.
1660 Result->data.symbolID = getSymbolID(&ND);
1661 }
1662 return Result;
1663 }
1664
1665 static std::optional<CallHierarchyItem>
1666 declToCallHierarchyItem(const NamedDecl &ND, llvm::StringRef TUPath) {
1667 auto Result = declToHierarchyItem<CallHierarchyItem>(ND, TUPath);
1668 if (!Result)
1669 return Result;
1670 if (ND.isDeprecated())
1671 Result->tags.push_back(SymbolTag::Deprecated);
1672 if (auto ID = getSymbolID(&ND))
1673 Result->data = ID.str();
1674 return Result;
1675 }
1676
1677 template <typename HierarchyItem>
1678 static std::optional<HierarchyItem> symbolToHierarchyItem(const Symbol &S,
1679 PathRef TUPath) {
1680 auto Loc = symbolToLocation(S, TUPath);
1681 if (!Loc) {
1682 elog("Failed to convert symbol to hierarchy item: {0}", Loc.takeError());
1683 return std::nullopt;
1684 }
1685 HierarchyItem HI;
1686 HI.name = std::string(S.Name);
1687 HI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind);
1688 HI.selectionRange = Loc->range;
1689 // FIXME: Populate 'range' correctly
1690 // (https://github.com/clangd/clangd/issues/59).
1691 HI.range = HI.selectionRange;
1692 HI.uri = Loc->uri;
1693
1694 return HI;
1695 }
1696
1697 static std::optional<TypeHierarchyItem>
1698 symbolToTypeHierarchyItem(const Symbol &S, PathRef TUPath) {
1699 auto Result = symbolToHierarchyItem<TypeHierarchyItem>(S, TUPath);
1700 if (Result) {
1701 Result->deprecated = (S.Flags & Symbol::Deprecated);
1702 Result->data.symbolID = S.ID;
1703 }
1704 return Result;
1705 }
1706
1707 static std::optional<CallHierarchyItem>
1708 symbolToCallHierarchyItem(const Symbol &S, PathRef TUPath) {
1709 auto Result = symbolToHierarchyItem<CallHierarchyItem>(S, TUPath);
1710 if (!Result)
1711 return Result;
1712 Result->data = S.ID.str();
1713 if (S.Flags & Symbol::Deprecated)
1714 Result->tags.push_back(SymbolTag::Deprecated);
1715 return Result;
1716 }
1717
1718 static void fillSubTypes(const SymbolID &ID,
1719 std::vector<TypeHierarchyItem> &SubTypes,
1720 const SymbolIndex *Index, int Levels, PathRef TUPath) {
1721 RelationsRequest Req;
1722 Req.Subjects.insert(ID);
1723 Req.Predicate = RelationKind::BaseOf;
1724 Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
1725 if (std::optional<TypeHierarchyItem> ChildSym =
1726 symbolToTypeHierarchyItem(Object, TUPath)) {
1727 if (Levels > 1) {
1728 ChildSym->children.emplace();
1729 fillSubTypes(Object.ID, *ChildSym->children, Index, Levels - 1, TUPath);
1730 }
1731 SubTypes.emplace_back(std::move(*ChildSym));
1732 }
1733 });
1734 }
1735
1736 using RecursionProtectionSet = llvm::SmallSet<const CXXRecordDecl *, 4>;
1737
1738 // Extracts parents from AST and populates the type hierarchy item.
1739 static void fillSuperTypes(const CXXRecordDecl &CXXRD, llvm::StringRef TUPath,
1740 TypeHierarchyItem &Item,
1741 RecursionProtectionSet &RPSet) {
1742 Item.parents.emplace();
1743 Item.data.parents.emplace();
1744 // typeParents() will replace dependent template specializations
1745 // with their class template, so to avoid infinite recursion for
1746 // certain types of hierarchies, keep the templates encountered
1747 // along the parent chain in a set, and stop the recursion if one
1748 // starts to repeat.
1749 auto *Pattern = CXXRD.getDescribedTemplate() ? &CXXRD : nullptr;
1750 if (Pattern) {
1751 if (!RPSet.insert(Pattern).second) {
1752 return;
1753 }
1754 }
1755
1756 for (const CXXRecordDecl *ParentDecl : typeParents(&CXXRD)) {
1757 if (std::optional<TypeHierarchyItem> ParentSym =
1758 declToTypeHierarchyItem(*ParentDecl, TUPath)) {
1759 fillSuperTypes(*ParentDecl, TUPath, *ParentSym, RPSet);
1760 Item.data.parents->emplace_back(ParentSym->data);
1761 Item.parents->emplace_back(std::move(*ParentSym));
1762 }
1763 }
1764
1765 if (Pattern) {
1766 RPSet.erase(Pattern);
1767 }
1768 }
1769
1770 std::vector<const CXXRecordDecl *> findRecordTypeAt(ParsedAST &AST,
1771 Position Pos) {
1772 auto RecordFromNode = [&AST](const SelectionTree::Node *N) {
1773 std::vector<const CXXRecordDecl *> Records;
1774 if (!N)
1775 return Records;
1776
1777 // Note: explicitReferenceTargets() will search for both template
1778 // instantiations and template patterns, and prefer the former if available
1779 // (generally, one will be available for non-dependent specializations of a
1780 // class template).
1781 auto Decls = explicitReferenceTargets(N->ASTNode, DeclRelation::Underlying,
1782 AST.getHeuristicResolver());
1783 for (const NamedDecl *D : Decls) {
1784
1785 if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
1786 // If this is a variable, use the type of the variable.
1787 Records.push_back(VD->getType().getTypePtr()->getAsCXXRecordDecl());
1788 continue;
1789 }
1790
1791 if (const CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(D)) {
1792 // If this is a method, use the type of the class.
1793 Records.push_back(Method->getParent());
1794 continue;
1795 }
1796
1797 // We don't handle FieldDecl because it's not clear what behaviour
1798 // the user would expect: the enclosing class type (as with a
1799 // method), or the field's type (as with a variable).
1800
1801 if (auto *RD = dyn_cast<CXXRecordDecl>(D))
1802 Records.push_back(RD);
1803 }
1804 return Records;
1805 };
1806
1807 const SourceManager &SM = AST.getSourceManager();
1808 std::vector<const CXXRecordDecl *> Result;
1809 auto Offset = positionToOffset(SM.getBufferData(SM.getMainFileID()), Pos);
1810 if (!Offset) {
1811 llvm::consumeError(Offset.takeError());
1812 return Result;
1813 }
1814 SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), *Offset,
1815 *Offset, [&](SelectionTree ST) {
1816 Result = RecordFromNode(ST.commonAncestor());
1817 return !Result.empty();
1818 });
1819 return Result;
1820 }
1821
1822 // Return the type most associated with an AST node.
1823 // This isn't precisely defined: we want "go to type" to do something useful.
1824 static QualType typeForNode(const SelectionTree::Node *N) {
1825 // If we're looking at a namespace qualifier, walk up to what it's qualifying.
1826 // (If we're pointing at a *class* inside a NNS, N will be a TypeLoc).
1827 while (N && N->ASTNode.get<NestedNameSpecifierLoc>())
1828 N = N->Parent;
1829 if (!N)
1830 return QualType();
1831
1832 // If we're pointing at a type => return it.
1833 if (const TypeLoc *TL = N->ASTNode.get<TypeLoc>()) {
1834 if (llvm::isa<DeducedType>(TL->getTypePtr()))
1835 if (auto Deduced = getDeducedType(
1836 N->getDeclContext().getParentASTContext(), TL->getBeginLoc()))
1837 return *Deduced;
1838 // Exception: an alias => underlying type.
1839 if (llvm::isa<TypedefType>(TL->getTypePtr()))
1840 return TL->getTypePtr()->getLocallyUnqualifiedSingleStepDesugaredType();
1841 return TL->getType();
1842 }
1843
1844 // Constructor initializers => the type of thing being initialized.
1845 if (const auto *CCI = N->ASTNode.get<CXXCtorInitializer>()) {
1846 if (const FieldDecl *FD = CCI->getAnyMember())
1847 return FD->getType();
1848 if (const Type *Base = CCI->getBaseClass())
1849 return QualType(Base, 0);
1850 }
1851
1852 // Base specifier => the base type.
1853 if (const auto *CBS = N->ASTNode.get<CXXBaseSpecifier>())
1854 return CBS->getType();
1855
1856 if (const Decl *D = N->ASTNode.get<Decl>()) {
1857 struct Visitor : ConstDeclVisitor<Visitor, QualType> {
1858 QualType VisitValueDecl(const ValueDecl *D) { return D->getType(); }
1859 // Declaration of a type => that type.
1860 QualType VisitTypeDecl(const TypeDecl *D) {
1861 return QualType(D->getTypeForDecl(), 0);
1862 }
1863 // Exception: alias declaration => the underlying type, not the alias.
1864 QualType VisitTypedefNameDecl(const TypedefNameDecl *D) {
1865 return D->getUnderlyingType();
1866 }
1867 // Look inside templates.
1868 QualType VisitTemplateDecl(const TemplateDecl *D) {
1869 return Visit(D->getTemplatedDecl());
1870 }
1871 } V;
1872 return V.Visit(D);
1873 }
1874
1875 if (const Stmt *S = N->ASTNode.get<Stmt>()) {
1876 struct Visitor : ConstStmtVisitor<Visitor, QualType> {
1877 // Null-safe version of visit simplifies recursive calls below.
1878 QualType type(const Stmt *S) { return S ? Visit(S) : QualType(); }
1879
1880 // In general, expressions => type of expression.
1881 QualType VisitExpr(const Expr *S) {
1882 return S->IgnoreImplicitAsWritten()->getType();
1883 }
1884 QualType VisitMemberExpr(const MemberExpr *S) {
1885 // The `foo` in `s.foo()` pretends not to have a real type!
1886 if (S->getType()->isSpecificBuiltinType(BuiltinType::BoundMember))
1887 return Expr::findBoundMemberType(S);
1888 return VisitExpr(S);
1889 }
1890 // Exceptions for void expressions that operate on a type in some way.
1891 QualType VisitCXXDeleteExpr(const CXXDeleteExpr *S) {
1892 return S->getDestroyedType();
1893 }
1894 QualType VisitCXXPseudoDestructorExpr(const CXXPseudoDestructorExpr *S) {
1895 return S->getDestroyedType();
1896 }
1897 QualType VisitCXXThrowExpr(const CXXThrowExpr *S) {
1898 return S->getSubExpr()->getType();
1899 }
1900 QualType VisitCoyieldExpr(const CoyieldExpr *S) {
1901 return type(S->getOperand());
1902 }
1903 // Treat a designated initializer like a reference to the field.
1904 QualType VisitDesignatedInitExpr(const DesignatedInitExpr *S) {
1905 // In .foo.bar we want to jump to bar's type, so find *last* field.
1906 for (auto &D : llvm::reverse(S->designators()))
1907 if (D.isFieldDesignator())
1908 if (const auto *FD = D.getField())
1909 return FD->getType();
1910 return QualType();
1911 }
1912
1913 // Control flow statements that operate on data: use the data type.
1914 QualType VisitSwitchStmt(const SwitchStmt *S) {
1915 return type(S->getCond());
1916 }
1917 QualType VisitWhileStmt(const WhileStmt *S) { return type(S->getCond()); }
1918 QualType VisitDoStmt(const DoStmt *S) { return type(S->getCond()); }
1919 QualType VisitIfStmt(const IfStmt *S) { return type(S->getCond()); }
1920 QualType VisitCaseStmt(const CaseStmt *S) { return type(S->getLHS()); }
1921 QualType VisitCXXForRangeStmt(const CXXForRangeStmt *S) {
1922 return S->getLoopVariable()->getType();
1923 }
1924 QualType VisitReturnStmt(const ReturnStmt *S) {
1925 return type(S->getRetValue());
1926 }
1927 QualType VisitCoreturnStmt(const CoreturnStmt *S) {
1928 return type(S->getOperand());
1929 }
1930 QualType VisitCXXCatchStmt(const CXXCatchStmt *S) {
1931 return S->getCaughtType();
1932 }
1933 QualType VisitObjCAtThrowStmt(const ObjCAtThrowStmt *S) {
1934 return type(S->getThrowExpr());
1935 }
1936 QualType VisitObjCAtCatchStmt(const ObjCAtCatchStmt *S) {
1937 return S->getCatchParamDecl() ? S->getCatchParamDecl()->getType()
1938 : QualType();
1939 }
1940 } V;
1941 return V.Visit(S);
1942 }
1943
1944 return QualType();
1945 }
1946
1947 // Given a type targeted by the cursor, return one or more types that are more interesting
1948 // to target.
1949 static void unwrapFindType(
1950 QualType T, const HeuristicResolver* H, llvm::SmallVector<QualType>& Out) {
1951 if (T.isNull())
1952 return;
1953
1954 // If there's a specific type alias, point at that rather than unwrapping.
1955 if (const auto* TDT = T->getAs<TypedefType>())
1956 return Out.push_back(QualType(TDT, 0));
1957
1958 // Pointers etc => pointee type.
1959 if (const auto *PT = T->getAs<PointerType>())
1960 return unwrapFindType(PT->getPointeeType(), H, Out);
1961 if (const auto *RT = T->getAs<ReferenceType>())
1962 return unwrapFindType(RT->getPointeeType(), H, Out);
1963 if (const auto *AT = T->getAsArrayTypeUnsafe())
1964 return unwrapFindType(AT->getElementType(), H, Out);
1965
1966 // Function type => return type.
1967 if (auto *FT = T->getAs<FunctionType>())
1968 return unwrapFindType(FT->getReturnType(), H, Out);
1969 if (auto *CRD = T->getAsCXXRecordDecl()) {
1970 if (CRD->isLambda())
1971 return unwrapFindType(CRD->getLambdaCallOperator()->getReturnType(), H, Out);
1972 // FIXME: more cases we'd prefer the return type of the call operator?
1973 // std::function etc?
1974 }
1975
1976 // For smart pointer types, add the underlying type
1977 if (H)
1978 if (const auto* PointeeType = H->getPointeeType(T.getNonReferenceType().getTypePtr())) {
1979 unwrapFindType(QualType(PointeeType, 0), H, Out);
1980 return Out.push_back(T);
1981 }
1982
1983 return Out.push_back(T);
1984 }
1985
1986 // Convenience overload, to allow calling this without the out-parameter
1987 static llvm::SmallVector<QualType> unwrapFindType(
1988 QualType T, const HeuristicResolver* H) {
1989 llvm::SmallVector<QualType> Result;
1990 unwrapFindType(T, H, Result);
1991 return Result;
1992 }
1993
1994
1995 std::vector<LocatedSymbol> findType(ParsedAST &AST, Position Pos) {
1996 const SourceManager &SM = AST.getSourceManager();
1997 auto Offset = positionToOffset(SM.getBufferData(SM.getMainFileID()), Pos);
1998 std::vector<LocatedSymbol> Result;
1999 if (!Offset) {
2000 elog("failed to convert position {0} for findTypes: {1}", Pos,
2001 Offset.takeError());
2002 return Result;
2003 }
2004 // The general scheme is: position -> AST node -> type -> declaration.
2005 auto SymbolsFromNode =
2006 [&AST](const SelectionTree::Node *N) -> std::vector<LocatedSymbol> {
2007 std::vector<LocatedSymbol> LocatedSymbols;
2008
2009 // NOTE: unwrapFindType might return duplicates for something like
2010 // unique_ptr<unique_ptr<T>>. Let's *not* remove them, because it gives you some
2011 // information about the type you may have not known before
2012 // (since unique_ptr<unique_ptr<T>> != unique_ptr<T>).
2013 for (const QualType& Type : unwrapFindType(typeForNode(N), AST.getHeuristicResolver()))
2014 llvm::copy(locateSymbolForType(AST, Type), std::back_inserter(LocatedSymbols));
2015
2016 return LocatedSymbols;
2017 };
2018 SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), *Offset,
2019 *Offset, [&](SelectionTree ST) {
2020 Result = SymbolsFromNode(ST.commonAncestor());
2021 return !Result.empty();
2022 });
2023 return Result;
2024 }
2025
2026 std::vector<const CXXRecordDecl *> typeParents(const CXXRecordDecl *CXXRD) {
2027 std::vector<const CXXRecordDecl *> Result;
2028
2029 // If this is an invalid instantiation, instantiation of the bases
2030 // may not have succeeded, so fall back to the template pattern.
2031 if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD)) {
2032 if (CTSD->isInvalidDecl())
2033 CXXRD = CTSD->getSpecializedTemplate()->getTemplatedDecl();
2034 }
2035
2036 // Can't query bases without a definition.
2037 if (!CXXRD->hasDefinition())
2038 return Result;
2039
2040 for (auto Base : CXXRD->bases()) {
2041 const CXXRecordDecl *ParentDecl = nullptr;
2042
2043 const Type *Type = Base.getType().getTypePtr();
2044 if (const RecordType *RT = Type->getAs<RecordType>()) {
2045 ParentDecl = RT->getAsCXXRecordDecl();
2046 }
2047
2048 if (!ParentDecl) {
2049 // Handle a dependent base such as "Base<T>" by using the primary
2050 // template.
2051 if (const TemplateSpecializationType *TS =
2052 Type->getAs<TemplateSpecializationType>()) {
2053 TemplateName TN = TS->getTemplateName();
2054 if (TemplateDecl *TD = TN.getAsTemplateDecl()) {
2055 ParentDecl = dyn_cast<CXXRecordDecl>(TD->getTemplatedDecl());
2056 }
2057 }
2058 }
2059
2060 if (ParentDecl)
2061 Result.push_back(ParentDecl);
2062 }
2063
2064 return Result;
2065 }
2066
2067 std::vector<TypeHierarchyItem>
2068 getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
2069 TypeHierarchyDirection Direction, const SymbolIndex *Index,
2070 PathRef TUPath) {
2071 std::vector<TypeHierarchyItem> Results;
2072 for (const auto *CXXRD : findRecordTypeAt(AST, Pos)) {
2073
2074 bool WantChildren = Direction == TypeHierarchyDirection::Children ||
2075 Direction == TypeHierarchyDirection::Both;
2076
2077 // If we're looking for children, we're doing the lookup in the index.
2078 // The index does not store relationships between implicit
2079 // specializations, so if we have one, use the template pattern instead.
2080 // Note that this needs to be done before the declToTypeHierarchyItem(),
2081 // otherwise the type hierarchy item would misleadingly contain the
2082 // specialization parameters, while the children would involve classes
2083 // that derive from other specializations of the template.
2084 if (WantChildren) {
2085 if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD))
2086 CXXRD = CTSD->getTemplateInstantiationPattern();
2087 }
2088
2089 std::optional<TypeHierarchyItem> Result =
2090 declToTypeHierarchyItem(*CXXRD, AST.tuPath());
2091 if (!Result)
2092 continue;
2093
2094 RecursionProtectionSet RPSet;
2095 fillSuperTypes(*CXXRD, AST.tuPath(), *Result, RPSet);
2096
2097 if (WantChildren && ResolveLevels > 0) {
2098 Result->children.emplace();
2099
2100 if (Index) {
2101 if (auto ID = getSymbolID(CXXRD))
2102 fillSubTypes(ID, *Result->children, Index, ResolveLevels, TUPath);
2103 }
2104 }
2105 Results.emplace_back(std::move(*Result));
2106 }
2107
2108 return Results;
2109 }
2110
2111 std::optional<std::vector<TypeHierarchyItem>>
2112 superTypes(const TypeHierarchyItem &Item, const SymbolIndex *Index) {
2113 std::vector<TypeHierarchyItem> Results;
2114 if (!Item.data.parents)
2115 return std::nullopt;
2116 if (Item.data.parents->empty())
2117 return Results;
2118 LookupRequest Req;
2119 llvm::DenseMap<SymbolID, const TypeHierarchyItem::ResolveParams *> IDToData;
2120 for (const auto &Parent : *Item.data.parents) {
2121 Req.IDs.insert(Parent.symbolID);
2122 IDToData[Parent.symbolID] = &Parent;
2123 }
2124 Index->lookup(Req, [&Item, &Results, &IDToData](const Symbol &S) {
2125 if (auto THI = symbolToTypeHierarchyItem(S, Item.uri.file())) {
2126 THI->data = *IDToData.lookup(S.ID);
2127 Results.emplace_back(std::move(*THI));
2128 }
2129 });
2130 return Results;
2131 }
2132
2133 std::vector<TypeHierarchyItem> subTypes(const TypeHierarchyItem &Item,
2134 const SymbolIndex *Index) {
2135 std::vector<TypeHierarchyItem> Results;
2136 fillSubTypes(Item.data.symbolID, Results, Index, 1, Item.uri.file());
2137 for (auto &ChildSym : Results)
2138 ChildSym.data.parents = {Item.data};
2139 return Results;
2140 }
2141
2142 void resolveTypeHierarchy(TypeHierarchyItem &Item, int ResolveLevels,
2143 TypeHierarchyDirection Direction,
2144 const SymbolIndex *Index) {
2145 // We only support typeHierarchy/resolve for children, because for parents
2146 // we ignore ResolveLevels and return all levels of parents eagerly.
2147 if (!Index || Direction == TypeHierarchyDirection::Parents ||
2148 ResolveLevels == 0)
2149 return;
2150
2151 Item.children.emplace();
2152 fillSubTypes(Item.data.symbolID, *Item.children, Index, ResolveLevels,
2153 Item.uri.file());
2154 }
2155
2156 std::vector<CallHierarchyItem>
2157 prepareCallHierarchy(ParsedAST &AST, Position Pos, PathRef TUPath) {
2158 std::vector<CallHierarchyItem> Result;
2159 const auto &SM = AST.getSourceManager();
2160 auto Loc = sourceLocationInMainFile(SM, Pos);
2161 if (!Loc) {
2162 elog("prepareCallHierarchy failed to convert position to source location: "
2163 "{0}",
2164 Loc.takeError());
2165 return Result;
2166 }
2167 for (const NamedDecl *Decl : getDeclAtPosition(AST, *Loc, {})) {
2168 if (!(isa<DeclContext>(Decl) &&
2169 cast<DeclContext>(Decl)->isFunctionOrMethod()) &&
2170 Decl->getKind() != Decl::Kind::FunctionTemplate)
2171 continue;
2172 if (auto CHI = declToCallHierarchyItem(*Decl, AST.tuPath()))
2173 Result.emplace_back(std::move(*CHI));
2174 }
2175 return Result;
2176 }
2177
2178 std::vector<CallHierarchyIncomingCall>
2179 incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) {
2180 std::vector<CallHierarchyIncomingCall> Results;
2181 if (!Index || Item.data.empty())
2182 return Results;
2183 auto ID = SymbolID::fromStr(Item.data);
2184 if (!ID) {
2185 elog("incomingCalls failed to find symbol: {0}", ID.takeError());
2186 return Results;
2187 }
2188 // In this function, we find incoming calls based on the index only.
2189 // In principle, the AST could have more up-to-date information about
2190 // occurrences within the current file. However, going from a SymbolID
2191 // to an AST node isn't cheap, particularly when the declaration isn't
2192 // in the main file.
2193 // FIXME: Consider also using AST information when feasible.
2194 RefsRequest Request;
2195 Request.IDs.insert(*ID);
2196 Request.WantContainer = true;
2197 // We could restrict more specifically to calls by introducing a new RefKind,
2198 // but non-call references (such as address-of-function) can still be
2199 // interesting as they can indicate indirect calls.
2200 Request.Filter = RefKind::Reference;
2201 // Initially store the ranges in a map keyed by SymbolID of the caller.
2202 // This allows us to group different calls with the same caller
2203 // into the same CallHierarchyIncomingCall.
2204 llvm::DenseMap<SymbolID, std::vector<Range>> CallsIn;
2205 // We can populate the ranges based on a refs request only. As we do so, we
2206 // also accumulate the container IDs into a lookup request.
2207 LookupRequest ContainerLookup;
2208 Index->refs(Request, [&](const Ref &R) {
2209 auto Loc = indexToLSPLocation(R.Location, Item.uri.file());
2210 if (!Loc) {
2211 elog("incomingCalls failed to convert location: {0}", Loc.takeError());
2212 return;
2213 }
2214 auto It = CallsIn.try_emplace(R.Container, std::vector<Range>{}).first;
2215 It->second.push_back(Loc->range);
2216
2217 ContainerLookup.IDs.insert(R.Container);
2218 });
2219 // Perform the lookup request and combine its results with CallsIn to
2220 // get complete CallHierarchyIncomingCall objects.
2221 Index->lookup(ContainerLookup, [&](const Symbol &Caller) {
2222 auto It = CallsIn.find(Caller.ID);
2223 assert(It != CallsIn.end());
2224 if (auto CHI = symbolToCallHierarchyItem(Caller, Item.uri.file()))
2225 Results.push_back(
2226 CallHierarchyIncomingCall{std::move(*CHI), std::move(It->second)});
2227 });
2228 // Sort results by name of container.
2229 llvm::sort(Results, [](const CallHierarchyIncomingCall &A,
2230 const CallHierarchyIncomingCall &B) {
2231 return A.from.name < B.from.name;
2232 });
2233 return Results;
2234 }
2235
2236 llvm::DenseSet<const Decl *> getNonLocalDeclRefs(ParsedAST &AST,
2237 const FunctionDecl *FD) {
2238 if (!FD->hasBody())
2239 return {};
2240 llvm::DenseSet<const Decl *> DeclRefs;
2241 findExplicitReferences(
2242 FD,
2243 [&](ReferenceLoc Ref) {
2244 for (const Decl *D : Ref.Targets) {
2245 if (!index::isFunctionLocalSymbol(D) && !D->isTemplateParameter() &&
2246 !Ref.IsDecl)
2247 DeclRefs.insert(D);
2248 }
2249 },
2250 AST.getHeuristicResolver());
2251 return DeclRefs;
2252 }
2253
2254 } // namespace clangd
2255 } // namespace clang