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