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