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