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
73namespace clang {
74namespace clangd {
75namespace {
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().
83const 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
117void 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.
124std::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
137SymbolLocation 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.
149SymbolLocation 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
162std::vector<std::pair<const NamedDecl *, DeclRelationSet>>
163getDeclAtPositionWithRelations(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
189std::vector<const NamedDecl *>
190getDeclAtPosition(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.
201std::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.
223std::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.
242std::optional<LocatedSymbol>
243locateMacroReferent(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.
272const 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
290std::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.
333void 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
375bool 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.
388std::vector<LocatedSymbol>
389locateASTReferent(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
513std::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
550bool 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
556llvm::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
565bool 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
575std::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
685const 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
776std::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
855std::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
882namespace {
883
884/// Collects references to symbols within the main file.
885class ReferenceFinder : public index::IndexDataConsumer {
886public:
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
965private:
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
972std::vector<ReferenceFinder::Reference>
973findRefs(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
987const 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
999const 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.
1014class 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
1055public:
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.
1108SourceRange 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.
1146std::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
1219DocumentHighlight 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
1232std::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
1247std::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
1288std::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
1326namespace {
1327// Recursively finds all the overridden methods of `CMD` in complete type
1328// hierarchy.
1329void 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.
1342void 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
1355std::optional<std::string>
1356stringifyContainerForMainFileRef(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
1364std::optional<ReferencesResult>
1365maybeFindIncludeReferences(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
1413ReferencesResult 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
1636std::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
1698llvm::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
1705llvm::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
1717template <typename HierarchyItem>
1718static std::optional<HierarchyItem>
1719declToHierarchyItem(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
1763static std::optional<TypeHierarchyItem>
1764declToTypeHierarchyItem(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
1777static std::optional<CallHierarchyItem>
1778declToCallHierarchyItem(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
1789template <typename HierarchyItem>
1790static 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
1810static std::optional<TypeHierarchyItem>
1811symbolToTypeHierarchyItem(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
1820static std::optional<CallHierarchyItem>
1821symbolToCallHierarchyItem(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
1831static 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
1849using RecursionProtectionSet = llvm::SmallSet<const CXXRecordDecl *, 4>;
1850
1851// Extracts parents from AST and populates the type hierarchy item.
1852static 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
1883std::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.
1938static 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.
2063static 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
2103static 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
2110std::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
2143std::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
2184std::vector<TypeHierarchyItem>
2185getTypeHierarchy(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
2228std::optional<std::vector<TypeHierarchyItem>>
2229superTypes(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
2250std::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
2259void 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
2273std::vector<CallHierarchyItem>
2274prepareCallHierarchy(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
2298std::vector<CallHierarchyIncomingCall>
2299incomingCalls(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
2367std::vector<CallHierarchyOutgoingCall>
2368outgoingCalls(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
2439llvm::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

Provided by KDAB

Privacy Policy
Update your C++ knowledge – Modern C++11/14/17 Training
Find out more

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