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