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

source code of clang-tools-extra/clangd/XRefs.cpp