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 "CodeCompletionStrings.h"
11 #include "FindSymbols.h"
12 #include "FindTarget.h"
13 #include "ParsedAST.h"
14 #include "Protocol.h"
15 #include "Quality.h"
16 #include "Selection.h"
17 #include "SourceCode.h"
18 #include "URI.h"
19 #include "index/Index.h"
20 #include "index/Merge.h"
21 #include "index/Relation.h"
22 #include "index/SymbolLocation.h"
23 #include "support/Logger.h"
24 #include "clang/AST/ASTContext.h"
25 #include "clang/AST/ASTTypeTraits.h"
26 #include "clang/AST/Attr.h"
27 #include "clang/AST/Attrs.inc"
28 #include "clang/AST/Decl.h"
29 #include "clang/AST/DeclCXX.h"
30 #include "clang/AST/DeclObjC.h"
31 #include "clang/AST/DeclTemplate.h"
32 #include "clang/AST/ExprCXX.h"
33 #include "clang/AST/RecursiveASTVisitor.h"
34 #include "clang/AST/Stmt.h"
35 #include "clang/AST/StmtCXX.h"
36 #include "clang/AST/Type.h"
37 #include "clang/Basic/CharInfo.h"
38 #include "clang/Basic/LLVM.h"
39 #include "clang/Basic/LangOptions.h"
40 #include "clang/Basic/SourceLocation.h"
41 #include "clang/Basic/SourceManager.h"
42 #include "clang/Basic/TokenKinds.h"
43 #include "clang/Index/IndexDataConsumer.h"
44 #include "clang/Index/IndexSymbol.h"
45 #include "clang/Index/IndexingAction.h"
46 #include "clang/Index/IndexingOptions.h"
47 #include "clang/Index/USRGeneration.h"
48 #include "clang/Tooling/Syntax/Tokens.h"
49 #include "llvm/ADT/ArrayRef.h"
50 #include "llvm/ADT/MapVector.h"
51 #include "llvm/ADT/None.h"
52 #include "llvm/ADT/STLExtras.h"
53 #include "llvm/ADT/ScopeExit.h"
54 #include "llvm/ADT/SmallSet.h"
55 #include "llvm/ADT/StringExtras.h"
56 #include "llvm/ADT/StringRef.h"
57 #include "llvm/Support/Casting.h"
58 #include "llvm/Support/Error.h"
59 #include "llvm/Support/MathExtras.h"
60 #include "llvm/Support/Path.h"
61 #include "llvm/Support/raw_ostream.h"
62
63 namespace clang {
64 namespace clangd {
65 namespace {
66
67 // Returns the single definition of the entity declared by D, if visible.
68 // In particular:
69 // - for non-redeclarable kinds (e.g. local vars), return D
70 // - for kinds that allow multiple definitions (e.g. namespaces), return nullptr
71 // Kinds of nodes that always return nullptr here will not have definitions
72 // reported by locateSymbolAt().
getDefinition(const NamedDecl * D)73 const NamedDecl *getDefinition(const NamedDecl *D) {
74 assert(D);
75 // Decl has one definition that we can find.
76 if (const auto *TD = dyn_cast<TagDecl>(D))
77 return TD->getDefinition();
78 if (const auto *VD = dyn_cast<VarDecl>(D))
79 return VD->getDefinition();
80 if (const auto *FD = dyn_cast<FunctionDecl>(D))
81 return FD->getDefinition();
82 // Objective-C classes can have three types of declarations:
83 //
84 // - forward declaration: @class MyClass;
85 // - true declaration (interface definition): @interface MyClass ... @end
86 // - true definition (implementation): @implementation MyClass ... @end
87 //
88 // Objective-C categories are extensions are on classes:
89 //
90 // - declaration: @interface MyClass (Ext) ... @end
91 // - definition: @implementation MyClass (Ext) ... @end
92 //
93 // With one special case, a class extension, which is normally used to keep
94 // some declarations internal to a file without exposing them in a header.
95 //
96 // - class extension declaration: @interface MyClass () ... @end
97 // - which really links to class definition: @implementation MyClass ... @end
98 if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(D))
99 return ID->getImplementation();
100 if (const auto *CD = dyn_cast<ObjCCategoryDecl>(D)) {
101 if (CD->IsClassExtension()) {
102 if (const auto *ID = CD->getClassInterface())
103 return ID->getImplementation();
104 return nullptr;
105 }
106 return CD->getImplementation();
107 }
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
logIfOverflow(const SymbolLocation & Loc)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.
toLSPLocation(const SymbolLocation & Loc,llvm::StringRef TUPath)125 llvm::Optional<Location> toLSPLocation(const SymbolLocation &Loc,
126 llvm::StringRef TUPath) {
127 if (!Loc)
128 return None;
129 auto Uri = URI::parse(Loc.FileURI);
130 if (!Uri) {
131 elog("Could not parse URI {0}: {1}", Loc.FileURI, Uri.takeError());
132 return None;
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 None;
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
toIndexLocation(const Location & Loc,std::string & URIStorage)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.
getPreferredLocation(const Location & ASTLoc,const SymbolLocation & IdxLoc,std::string & Scratch)162 SymbolLocation getPreferredLocation(const Location &ASTLoc,
163 const SymbolLocation &IdxLoc,
164 std::string &Scratch) {
165 // Also use a dummy 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("dummy_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>>
getDeclAtPositionWithRelations(ParsedAST & AST,SourceLocation Pos,DeclRelationSet Relations,ASTNodeKind * NodeKind=nullptr)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 llvm::copy_if(allTargetDecls(N->ASTNode), std::back_inserter(Result),
186 [&](auto &Entry) { return !(Entry.second & ~Relations); });
187 }
188 return !Result.empty();
189 };
190 SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset,
191 Offset, ResultFromTree);
192 return Result;
193 }
194
195 std::vector<const NamedDecl *>
getDeclAtPosition(ParsedAST & AST,SourceLocation Pos,DeclRelationSet Relations,ASTNodeKind * NodeKind=nullptr)196 getDeclAtPosition(ParsedAST &AST, SourceLocation Pos, DeclRelationSet Relations,
197 ASTNodeKind *NodeKind = nullptr) {
198 std::vector<const NamedDecl *> Result;
199 for (auto &Entry :
200 getDeclAtPositionWithRelations(AST, Pos, Relations, NodeKind))
201 Result.push_back(Entry.first);
202 return Result;
203 }
204
205 // Expects Loc to be a SpellingLocation, will bail out otherwise as it can't
206 // figure out a filename.
makeLocation(const ASTContext & AST,SourceLocation Loc,llvm::StringRef TUPath)207 llvm::Optional<Location> makeLocation(const ASTContext &AST, SourceLocation Loc,
208 llvm::StringRef TUPath) {
209 const auto &SM = AST.getSourceManager();
210 const FileEntry *F = SM.getFileEntryForID(SM.getFileID(Loc));
211 if (!F)
212 return None;
213 auto FilePath = getCanonicalPath(F, SM);
214 if (!FilePath) {
215 log("failed to get path!");
216 return None;
217 }
218 Location L;
219 L.uri = URIForFile::canonicalize(*FilePath, TUPath);
220 // We call MeasureTokenLength here as TokenBuffer doesn't store spelled tokens
221 // outside the main file.
222 auto TokLen = Lexer::MeasureTokenLength(Loc, SM, AST.getLangOpts());
223 L.range = halfOpenToRange(
224 SM, CharSourceRange::getCharRange(Loc, Loc.getLocWithOffset(TokLen)));
225 return L;
226 }
227
228 // Treat #included files as symbols, to enable go-to-definition on them.
locateFileReferent(const Position & Pos,ParsedAST & AST,llvm::StringRef MainFilePath)229 llvm::Optional<LocatedSymbol> locateFileReferent(const Position &Pos,
230 ParsedAST &AST,
231 llvm::StringRef MainFilePath) {
232 for (auto &Inc : AST.getIncludeStructure().MainFileIncludes) {
233 if (!Inc.Resolved.empty() && Inc.HashLine == Pos.line) {
234 LocatedSymbol File;
235 File.Name = std::string(llvm::sys::path::filename(Inc.Resolved));
236 File.PreferredDeclaration = {
237 URIForFile::canonicalize(Inc.Resolved, MainFilePath), Range{}};
238 File.Definition = File.PreferredDeclaration;
239 // We're not going to find any further symbols on #include lines.
240 return File;
241 }
242 }
243 return llvm::None;
244 }
245
246 // Macros are simple: there's no declaration/definition distinction.
247 // As a consequence, there's no need to look them up in the index either.
248 llvm::Optional<LocatedSymbol>
locateMacroReferent(const syntax::Token & TouchedIdentifier,ParsedAST & AST,llvm::StringRef MainFilePath)249 locateMacroReferent(const syntax::Token &TouchedIdentifier, ParsedAST &AST,
250 llvm::StringRef MainFilePath) {
251 if (auto M = locateMacroAt(TouchedIdentifier, AST.getPreprocessor())) {
252 if (auto Loc =
253 makeLocation(AST.getASTContext(), M->NameLoc, MainFilePath)) {
254 LocatedSymbol Macro;
255 Macro.Name = std::string(M->Name);
256 Macro.PreferredDeclaration = *Loc;
257 Macro.Definition = Loc;
258 return Macro;
259 }
260 }
261 return llvm::None;
262 }
263
264 // A wrapper around `Decl::getCanonicalDecl` to support cases where Clang's
265 // definition of a canonical declaration doesn't match up to what a programmer
266 // would expect. For example, Objective-C classes can have three types of
267 // declarations:
268 //
269 // - forward declaration(s): @class MyClass;
270 // - true declaration (interface definition): @interface MyClass ... @end
271 // - true definition (implementation): @implementation MyClass ... @end
272 //
273 // Clang will consider the forward declaration to be the canonical declaration
274 // because it is first. We actually want the class definition if it is
275 // available since that is what a programmer would consider the primary
276 // declaration to be.
getPreferredDecl(const NamedDecl * D)277 const NamedDecl *getPreferredDecl(const NamedDecl *D) {
278 // FIXME: Canonical declarations of some symbols might refer to built-in
279 // decls with possibly-invalid source locations (e.g. global new operator).
280 // In such cases we should pick up a redecl with valid source location
281 // instead of failing.
282 D = llvm::cast<NamedDecl>(D->getCanonicalDecl());
283
284 // Prefer Objective-C class/protocol definitions over the forward declaration.
285 if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(D))
286 if (const auto *DefinitionID = ID->getDefinition())
287 return DefinitionID;
288 if (const auto *PD = dyn_cast<ObjCProtocolDecl>(D))
289 if (const auto *DefinitionID = PD->getDefinition())
290 return DefinitionID;
291
292 return D;
293 }
294
295 // Decls are more complicated.
296 // The AST contains at least a declaration, maybe a definition.
297 // These are up-to-date, and so generally preferred over index results.
298 // We perform a single batch index lookup to find additional definitions.
299 std::vector<LocatedSymbol>
locateASTReferent(SourceLocation CurLoc,const syntax::Token * TouchedIdentifier,ParsedAST & AST,llvm::StringRef MainFilePath,const SymbolIndex * Index,ASTNodeKind * NodeKind)300 locateASTReferent(SourceLocation CurLoc, const syntax::Token *TouchedIdentifier,
301 ParsedAST &AST, llvm::StringRef MainFilePath,
302 const SymbolIndex *Index, ASTNodeKind *NodeKind) {
303 const SourceManager &SM = AST.getSourceManager();
304 // Results follow the order of Symbols.Decls.
305 std::vector<LocatedSymbol> Result;
306 // Keep track of SymbolID -> index mapping, to fill in index data later.
307 llvm::DenseMap<SymbolID, size_t> ResultIndex;
308
309 auto AddResultDecl = [&](const NamedDecl *D) {
310 D = getPreferredDecl(D);
311 auto Loc =
312 makeLocation(AST.getASTContext(), nameLocation(*D, SM), MainFilePath);
313 if (!Loc)
314 return;
315
316 Result.emplace_back();
317 Result.back().Name = printName(AST.getASTContext(), *D);
318 Result.back().PreferredDeclaration = *Loc;
319 if (const NamedDecl *Def = getDefinition(D))
320 Result.back().Definition = makeLocation(
321 AST.getASTContext(), nameLocation(*Def, SM), MainFilePath);
322
323 // Record SymbolID for index lookup later.
324 if (auto ID = getSymbolID(D))
325 ResultIndex[ID] = Result.size() - 1;
326 };
327
328 // Emit all symbol locations (declaration or definition) from AST.
329 DeclRelationSet Relations =
330 DeclRelation::TemplatePattern | DeclRelation::Alias;
331 auto Candidates =
332 getDeclAtPositionWithRelations(AST, CurLoc, Relations, NodeKind);
333 for (const auto &E : Candidates) {
334 const NamedDecl *D = E.first;
335 // Special case: void foo() ^override: jump to the overridden method.
336 if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(D)) {
337 const InheritableAttr *Attr = D->getAttr<OverrideAttr>();
338 if (!Attr)
339 Attr = D->getAttr<FinalAttr>();
340 if (Attr && TouchedIdentifier &&
341 SM.getSpellingLoc(Attr->getLocation()) ==
342 TouchedIdentifier->location()) {
343 // We may be overridding multiple methods - offer them all.
344 for (const NamedDecl *ND : CMD->overridden_methods())
345 AddResultDecl(ND);
346 continue;
347 }
348 }
349
350 // Special case: the cursor is on an alias, prefer other results.
351 // This targets "using ns::^Foo", where the target is more interesting.
352 // This does not trigger on renaming aliases:
353 // `using Foo = ^Bar` already targets Bar via a TypeLoc
354 // `using ^Foo = Bar` has no other results, as Underlying is filtered.
355 if (E.second & DeclRelation::Alias && Candidates.size() > 1 &&
356 // beginLoc/endLoc are a token range, so rewind the identifier we're in.
357 SM.isPointWithin(TouchedIdentifier ? TouchedIdentifier->location()
358 : CurLoc,
359 D->getBeginLoc(), D->getEndLoc()))
360 continue;
361
362 // Special case: the point of declaration of a template specialization,
363 // it's more useful to navigate to the template declaration.
364 if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(D)) {
365 if (TouchedIdentifier &&
366 D->getLocation() == TouchedIdentifier->location()) {
367 AddResultDecl(CTSD->getSpecializedTemplate());
368 continue;
369 }
370 }
371
372 // Special case: if the class name is selected, also map Objective-C
373 // categories and category implementations back to their class interface.
374 //
375 // Since `TouchedIdentifier` might refer to the `ObjCCategoryImplDecl`
376 // instead of the `ObjCCategoryDecl` we intentionally check the contents
377 // of the locs when checking for class name equivalence.
378 if (const auto *CD = dyn_cast<ObjCCategoryDecl>(D))
379 if (const auto *ID = CD->getClassInterface())
380 if (TouchedIdentifier &&
381 (CD->getLocation() == TouchedIdentifier->location() ||
382 ID->getName() == TouchedIdentifier->text(SM)))
383 AddResultDecl(ID);
384
385 // Otherwise the target declaration is the right one.
386 AddResultDecl(D);
387 }
388
389 // Now query the index for all Symbol IDs we found in the AST.
390 if (Index && !ResultIndex.empty()) {
391 LookupRequest QueryRequest;
392 for (auto It : ResultIndex)
393 QueryRequest.IDs.insert(It.first);
394 std::string Scratch;
395 Index->lookup(QueryRequest, [&](const Symbol &Sym) {
396 auto &R = Result[ResultIndex.lookup(Sym.ID)];
397
398 if (R.Definition) { // from AST
399 // Special case: if the AST yielded a definition, then it may not be
400 // the right *declaration*. Prefer the one from the index.
401 if (auto Loc = toLSPLocation(Sym.CanonicalDeclaration, MainFilePath))
402 R.PreferredDeclaration = *Loc;
403
404 // We might still prefer the definition from the index, e.g. for
405 // generated symbols.
406 if (auto Loc = toLSPLocation(
407 getPreferredLocation(*R.Definition, Sym.Definition, Scratch),
408 MainFilePath))
409 R.Definition = *Loc;
410 } else {
411 R.Definition = toLSPLocation(Sym.Definition, MainFilePath);
412
413 // Use merge logic to choose AST or index declaration.
414 if (auto Loc = toLSPLocation(
415 getPreferredLocation(R.PreferredDeclaration,
416 Sym.CanonicalDeclaration, Scratch),
417 MainFilePath))
418 R.PreferredDeclaration = *Loc;
419 }
420 });
421 }
422
423 return Result;
424 }
425
tokenSpelledAt(SourceLocation SpellingLoc,const syntax::TokenBuffer & TB)426 bool tokenSpelledAt(SourceLocation SpellingLoc, const syntax::TokenBuffer &TB) {
427 auto ExpandedTokens = TB.expandedTokens(
428 TB.sourceManager().getMacroArgExpandedLocation(SpellingLoc));
429 return !ExpandedTokens.empty();
430 }
431
sourcePrefix(SourceLocation Loc,const SourceManager & SM)432 llvm::StringRef sourcePrefix(SourceLocation Loc, const SourceManager &SM) {
433 auto D = SM.getDecomposedLoc(Loc);
434 bool Invalid = false;
435 llvm::StringRef Buf = SM.getBufferData(D.first, &Invalid);
436 if (Invalid || D.second > Buf.size())
437 return "";
438 return Buf.substr(0, D.second);
439 }
440
isDependentName(ASTNodeKind NodeKind)441 bool isDependentName(ASTNodeKind NodeKind) {
442 return NodeKind.isSame(ASTNodeKind::getFromNodeKind<OverloadExpr>()) ||
443 NodeKind.isSame(
444 ASTNodeKind::getFromNodeKind<CXXDependentScopeMemberExpr>()) ||
445 NodeKind.isSame(
446 ASTNodeKind::getFromNodeKind<DependentScopeDeclRefExpr>());
447 }
448
449 } // namespace
450
451 std::vector<LocatedSymbol>
locateSymbolTextually(const SpelledWord & Word,ParsedAST & AST,const SymbolIndex * Index,const std::string & MainFilePath,ASTNodeKind NodeKind)452 locateSymbolTextually(const SpelledWord &Word, ParsedAST &AST,
453 const SymbolIndex *Index, const std::string &MainFilePath,
454 ASTNodeKind NodeKind) {
455 // Don't use heuristics if this is a real identifier, or not an
456 // identifier.
457 // Exception: dependent names, because those may have useful textual
458 // matches that AST-based heuristics cannot find.
459 if ((Word.ExpandedToken && !isDependentName(NodeKind)) ||
460 !Word.LikelyIdentifier || !Index)
461 return {};
462 // We don't want to handle words in string literals. (It'd be nice to list
463 // *allowed* token kinds explicitly, but comment Tokens aren't retained).
464 if (Word.PartOfSpelledToken &&
465 isStringLiteral(Word.PartOfSpelledToken->kind()))
466 return {};
467
468 const auto &SM = AST.getSourceManager();
469 // Look up the selected word in the index.
470 FuzzyFindRequest Req;
471 Req.Query = Word.Text.str();
472 Req.ProximityPaths = {MainFilePath};
473 // Find the namespaces to query by lexing the file.
474 Req.Scopes =
475 visibleNamespaces(sourcePrefix(Word.Location, SM), AST.getLangOpts());
476 // FIXME: For extra strictness, consider AnyScope=false.
477 Req.AnyScope = true;
478 // We limit the results to 3 further below. This limit is to avoid fetching
479 // too much data, while still likely having enough for 3 results to remain
480 // after additional filtering.
481 Req.Limit = 10;
482 bool TooMany = false;
483 using ScoredLocatedSymbol = std::pair<float, LocatedSymbol>;
484 std::vector<ScoredLocatedSymbol> ScoredResults;
485 Index->fuzzyFind(Req, [&](const Symbol &Sym) {
486 // Only consider exact name matches, including case.
487 // This is to avoid too many false positives.
488 // We could relax this in the future (e.g. to allow for typos) if we make
489 // the query more accurate by other means.
490 if (Sym.Name != Word.Text)
491 return;
492
493 // Exclude constructor results. They have the same name as the class,
494 // but we don't have enough context to prefer them over the class.
495 if (Sym.SymInfo.Kind == index::SymbolKind::Constructor)
496 return;
497
498 auto MaybeDeclLoc =
499 indexToLSPLocation(Sym.CanonicalDeclaration, MainFilePath);
500 if (!MaybeDeclLoc) {
501 log("locateSymbolNamedTextuallyAt: {0}", MaybeDeclLoc.takeError());
502 return;
503 }
504 LocatedSymbol Located;
505 Located.PreferredDeclaration = *MaybeDeclLoc;
506 Located.Name = (Sym.Name + Sym.TemplateSpecializationArgs).str();
507 if (Sym.Definition) {
508 auto MaybeDefLoc = indexToLSPLocation(Sym.Definition, MainFilePath);
509 if (!MaybeDefLoc) {
510 log("locateSymbolNamedTextuallyAt: {0}", MaybeDefLoc.takeError());
511 return;
512 }
513 Located.PreferredDeclaration = *MaybeDefLoc;
514 Located.Definition = *MaybeDefLoc;
515 }
516
517 if (ScoredResults.size() >= 5) {
518 // If we have more than 5 results, don't return anything,
519 // as confidence is too low.
520 // FIXME: Alternatively, try a stricter query?
521 TooMany = true;
522 return;
523 }
524
525 SymbolQualitySignals Quality;
526 Quality.merge(Sym);
527 SymbolRelevanceSignals Relevance;
528 Relevance.Name = Sym.Name;
529 Relevance.Query = SymbolRelevanceSignals::Generic;
530 Relevance.merge(Sym);
531 auto Score = evaluateSymbolAndRelevance(Quality.evaluateHeuristics(),
532 Relevance.evaluateHeuristics());
533 dlog("locateSymbolNamedTextuallyAt: {0}{1} = {2}\n{3}{4}\n", Sym.Scope,
534 Sym.Name, Score, Quality, Relevance);
535
536 ScoredResults.push_back({Score, std::move(Located)});
537 });
538
539 if (TooMany) {
540 vlog("Heuristic index lookup for {0} returned too many candidates, ignored",
541 Word.Text);
542 return {};
543 }
544
545 llvm::sort(ScoredResults,
546 [](const ScoredLocatedSymbol &A, const ScoredLocatedSymbol &B) {
547 return A.first > B.first;
548 });
549 std::vector<LocatedSymbol> Results;
550 for (auto &Res : std::move(ScoredResults))
551 Results.push_back(std::move(Res.second));
552 if (Results.empty())
553 vlog("No heuristic index definition for {0}", Word.Text);
554 else
555 log("Found definition heuristically in index for {0}", Word.Text);
556 return Results;
557 }
558
findNearbyIdentifier(const SpelledWord & Word,const syntax::TokenBuffer & TB)559 const syntax::Token *findNearbyIdentifier(const SpelledWord &Word,
560 const syntax::TokenBuffer &TB) {
561 // Don't use heuristics if this is a real identifier.
562 // Unlikely identifiers are OK if they were used as identifiers nearby.
563 if (Word.ExpandedToken)
564 return nullptr;
565 // We don't want to handle words in string literals. (It'd be nice to list
566 // *allowed* token kinds explicitly, but comment Tokens aren't retained).
567 if (Word.PartOfSpelledToken &&
568 isStringLiteral(Word.PartOfSpelledToken->kind()))
569 return {};
570
571 const SourceManager &SM = TB.sourceManager();
572 // We prefer the closest possible token, line-wise. Backwards is penalized.
573 // Ties are implicitly broken by traversal order (first-one-wins).
574 auto File = SM.getFileID(Word.Location);
575 unsigned WordLine = SM.getSpellingLineNumber(Word.Location);
576 auto Cost = [&](SourceLocation Loc) -> unsigned {
577 assert(SM.getFileID(Loc) == File && "spelled token in wrong file?");
578 unsigned Line = SM.getSpellingLineNumber(Loc);
579 return Line >= WordLine ? Line - WordLine : 2 * (WordLine - Line);
580 };
581 const syntax::Token *BestTok = nullptr;
582 unsigned BestCost = -1;
583 // Search bounds are based on word length:
584 // - forward: 2^N lines
585 // - backward: 2^(N-1) lines.
586 unsigned MaxDistance =
587 1U << std::min<unsigned>(Word.Text.size(),
588 std::numeric_limits<unsigned>::digits - 1);
589 // Line number for SM.translateLineCol() should be one-based, also
590 // SM.translateLineCol() can handle line number greater than
591 // number of lines in the file.
592 // - LineMin = max(1, WordLine + 1 - 2^(N-1))
593 // - LineMax = WordLine + 1 + 2^N
594 unsigned LineMin =
595 WordLine + 1 <= MaxDistance / 2 ? 1 : WordLine + 1 - MaxDistance / 2;
596 unsigned LineMax = WordLine + 1 + MaxDistance;
597 SourceLocation LocMin = SM.translateLineCol(File, LineMin, 1);
598 assert(LocMin.isValid());
599 SourceLocation LocMax = SM.translateLineCol(File, LineMax, 1);
600 assert(LocMax.isValid());
601
602 // Updates BestTok and BestCost if Tok is a good candidate.
603 // May return true if the cost is too high for this token.
604 auto Consider = [&](const syntax::Token &Tok) {
605 if (Tok.location() < LocMin || Tok.location() > LocMax)
606 return true; // we are too far from the word, break the outer loop.
607 if (!(Tok.kind() == tok::identifier && Tok.text(SM) == Word.Text))
608 return false;
609 // No point guessing the same location we started with.
610 if (Tok.location() == Word.Location)
611 return false;
612 // We've done cheap checks, compute cost so we can break the caller's loop.
613 unsigned TokCost = Cost(Tok.location());
614 if (TokCost >= BestCost)
615 return true; // causes the outer loop to break.
616 // Allow locations that might be part of the AST, and macros (even if empty)
617 // but not things like disabled preprocessor sections.
618 if (!(tokenSpelledAt(Tok.location(), TB) || TB.expansionStartingAt(&Tok)))
619 return false;
620 // We already verified this token is an improvement.
621 BestCost = TokCost;
622 BestTok = &Tok;
623 return false;
624 };
625 auto SpelledTokens = TB.spelledTokens(File);
626 // Find where the word occurred in the token stream, to search forward & back.
627 auto *I = llvm::partition_point(SpelledTokens, [&](const syntax::Token &T) {
628 assert(SM.getFileID(T.location()) == SM.getFileID(Word.Location));
629 return T.location() < Word.Location; // Comparison OK: same file.
630 });
631 // Search for matches after the cursor.
632 for (const syntax::Token &Tok : llvm::makeArrayRef(I, SpelledTokens.end()))
633 if (Consider(Tok))
634 break; // costs of later tokens are greater...
635 // Search for matches before the cursor.
636 for (const syntax::Token &Tok :
637 llvm::reverse(llvm::makeArrayRef(SpelledTokens.begin(), I)))
638 if (Consider(Tok))
639 break;
640
641 if (BestTok)
642 vlog(
643 "Word {0} under cursor {1} isn't a token (after PP), trying nearby {2}",
644 Word.Text, Word.Location.printToString(SM),
645 BestTok->location().printToString(SM));
646
647 return BestTok;
648 }
649
locateSymbolAt(ParsedAST & AST,Position Pos,const SymbolIndex * Index)650 std::vector<LocatedSymbol> locateSymbolAt(ParsedAST &AST, Position Pos,
651 const SymbolIndex *Index) {
652 const auto &SM = AST.getSourceManager();
653 auto MainFilePath =
654 getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
655 if (!MainFilePath) {
656 elog("Failed to get a path for the main file, so no references");
657 return {};
658 }
659
660 if (auto File = locateFileReferent(Pos, AST, *MainFilePath))
661 return {std::move(*File)};
662
663 auto CurLoc = sourceLocationInMainFile(SM, Pos);
664 if (!CurLoc) {
665 elog("locateSymbolAt failed to convert position to source location: {0}",
666 CurLoc.takeError());
667 return {};
668 }
669
670 const syntax::Token *TouchedIdentifier =
671 syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens());
672 if (TouchedIdentifier)
673 if (auto Macro =
674 locateMacroReferent(*TouchedIdentifier, AST, *MainFilePath))
675 // Don't look at the AST or index if we have a macro result.
676 // (We'd just return declarations referenced from the macro's
677 // expansion.)
678 return {*std::move(Macro)};
679
680 ASTNodeKind NodeKind;
681 auto ASTResults = locateASTReferent(*CurLoc, TouchedIdentifier, AST,
682 *MainFilePath, Index, &NodeKind);
683 if (!ASTResults.empty())
684 return ASTResults;
685
686 // If the cursor can't be resolved directly, try fallback strategies.
687 auto Word =
688 SpelledWord::touching(*CurLoc, AST.getTokens(), AST.getLangOpts());
689 if (Word) {
690 // Is the same word nearby a real identifier that might refer to something?
691 if (const syntax::Token *NearbyIdent =
692 findNearbyIdentifier(*Word, AST.getTokens())) {
693 if (auto Macro = locateMacroReferent(*NearbyIdent, AST, *MainFilePath)) {
694 log("Found macro definition heuristically using nearby identifier {0}",
695 Word->Text);
696 return {*std::move(Macro)};
697 }
698 ASTResults =
699 locateASTReferent(NearbyIdent->location(), NearbyIdent, AST,
700 *MainFilePath, Index, /*NodeKind=*/nullptr);
701 if (!ASTResults.empty()) {
702 log("Found definition heuristically using nearby identifier {0}",
703 NearbyIdent->text(SM));
704 return ASTResults;
705 } else {
706 vlog("No definition found using nearby identifier {0} at {1}",
707 Word->Text, Word->Location.printToString(SM));
708 }
709 }
710 // No nearby word, or it didn't refer to anything either. Try the index.
711 auto TextualResults =
712 locateSymbolTextually(*Word, AST, Index, *MainFilePath, NodeKind);
713 if (!TextualResults.empty())
714 return TextualResults;
715 }
716
717 return {};
718 }
719
getDocumentLinks(ParsedAST & AST)720 std::vector<DocumentLink> getDocumentLinks(ParsedAST &AST) {
721 const auto &SM = AST.getSourceManager();
722 auto MainFilePath =
723 getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
724 if (!MainFilePath) {
725 elog("Failed to get a path for the main file, so no links");
726 return {};
727 }
728
729 std::vector<DocumentLink> Result;
730 for (auto &Inc : AST.getIncludeStructure().MainFileIncludes) {
731 if (Inc.Resolved.empty())
732 continue;
733 auto HashLoc = SM.getComposedLoc(SM.getMainFileID(), Inc.HashOffset);
734 const auto *HashTok = AST.getTokens().spelledTokenAt(HashLoc);
735 assert(HashTok && "got inclusion at wrong offset");
736 const auto *IncludeTok = std::next(HashTok);
737 const auto *FileTok = std::next(IncludeTok);
738 // FileTok->range is not sufficient here, as raw lexing wouldn't yield
739 // correct tokens for angled filenames. Hence we explicitly use
740 // Inc.Written's length.
741 auto FileRange =
742 syntax::FileRange(SM, FileTok->location(), Inc.Written.length())
743 .toCharRange(SM);
744
745 Result.push_back(
746 DocumentLink({halfOpenToRange(SM, FileRange),
747 URIForFile::canonicalize(Inc.Resolved, *MainFilePath)}));
748 }
749
750 return Result;
751 }
752
753 namespace {
754
755 /// Collects references to symbols within the main file.
756 class ReferenceFinder : public index::IndexDataConsumer {
757 public:
758 struct Reference {
759 syntax::Token SpelledTok;
760 index::SymbolRoleSet Role;
761
rangeclang::clangd::__anon7033247a0b11::ReferenceFinder::Reference762 Range range(const SourceManager &SM) const {
763 return halfOpenToRange(SM, SpelledTok.range(SM).toCharRange(SM));
764 }
765 };
766
ReferenceFinder(const ParsedAST & AST,const std::vector<const NamedDecl * > & TargetDecls)767 ReferenceFinder(const ParsedAST &AST,
768 const std::vector<const NamedDecl *> &TargetDecls)
769 : AST(AST) {
770 for (const NamedDecl *D : TargetDecls)
771 CanonicalTargets.insert(D->getCanonicalDecl());
772 }
773
take()774 std::vector<Reference> take() && {
775 llvm::sort(References, [](const Reference &L, const Reference &R) {
776 auto LTok = L.SpelledTok.location();
777 auto RTok = R.SpelledTok.location();
778 return std::tie(LTok, L.Role) < std::tie(RTok, R.Role);
779 });
780 // We sometimes see duplicates when parts of the AST get traversed twice.
781 References.erase(std::unique(References.begin(), References.end(),
782 [](const Reference &L, const Reference &R) {
783 auto LTok = L.SpelledTok.location();
784 auto RTok = R.SpelledTok.location();
785 return std::tie(LTok, L.Role) ==
786 std::tie(RTok, R.Role);
787 }),
788 References.end());
789 return std::move(References);
790 }
791
792 bool
handleDeclOccurrence(const Decl * D,index::SymbolRoleSet Roles,llvm::ArrayRef<index::SymbolRelation> Relations,SourceLocation Loc,index::IndexDataConsumer::ASTNodeInfo ASTNode)793 handleDeclOccurrence(const Decl *D, index::SymbolRoleSet Roles,
794 llvm::ArrayRef<index::SymbolRelation> Relations,
795 SourceLocation Loc,
796 index::IndexDataConsumer::ASTNodeInfo ASTNode) override {
797 assert(D->isCanonicalDecl() && "expect D to be a canonical declaration");
798 const SourceManager &SM = AST.getSourceManager();
799 if (!CanonicalTargets.count(D) || !isInsideMainFile(Loc, SM))
800 return true;
801 const auto &TB = AST.getTokens();
802 Loc = SM.getFileLoc(Loc);
803 if (const auto *Tok = TB.spelledTokenAt(Loc))
804 References.push_back({*Tok, Roles});
805 return true;
806 }
807
808 private:
809 llvm::SmallSet<const Decl *, 4> CanonicalTargets;
810 std::vector<Reference> References;
811 const ParsedAST &AST;
812 };
813
814 std::vector<ReferenceFinder::Reference>
findRefs(const std::vector<const NamedDecl * > & Decls,ParsedAST & AST)815 findRefs(const std::vector<const NamedDecl *> &Decls, ParsedAST &AST) {
816 ReferenceFinder RefFinder(AST, Decls);
817 index::IndexingOptions IndexOpts;
818 IndexOpts.SystemSymbolFilter =
819 index::IndexingOptions::SystemSymbolFilterKind::All;
820 IndexOpts.IndexFunctionLocals = true;
821 IndexOpts.IndexParametersInDeclarations = true;
822 IndexOpts.IndexTemplateParameters = true;
823 indexTopLevelDecls(AST.getASTContext(), AST.getPreprocessor(),
824 AST.getLocalTopLevelDecls(), RefFinder, IndexOpts);
825 return std::move(RefFinder).take();
826 }
827
getFunctionBody(DynTypedNode N)828 const Stmt *getFunctionBody(DynTypedNode N) {
829 if (const auto *FD = N.get<FunctionDecl>())
830 return FD->getBody();
831 if (const auto *FD = N.get<BlockDecl>())
832 return FD->getBody();
833 if (const auto *FD = N.get<LambdaExpr>())
834 return FD->getBody();
835 if (const auto *FD = N.get<ObjCMethodDecl>())
836 return FD->getBody();
837 return nullptr;
838 }
839
getLoopBody(DynTypedNode N)840 const Stmt *getLoopBody(DynTypedNode N) {
841 if (const auto *LS = N.get<ForStmt>())
842 return LS->getBody();
843 if (const auto *LS = N.get<CXXForRangeStmt>())
844 return LS->getBody();
845 if (const auto *LS = N.get<WhileStmt>())
846 return LS->getBody();
847 if (const auto *LS = N.get<DoStmt>())
848 return LS->getBody();
849 return nullptr;
850 }
851
852 // AST traversal to highlight control flow statements under some root.
853 // Once we hit further control flow we prune the tree (or at least restrict
854 // what we highlight) so we capture e.g. breaks from the outer loop only.
855 class FindControlFlow : public RecursiveASTVisitor<FindControlFlow> {
856 // Types of control-flow statements we might highlight.
857 enum Target {
858 Break = 1,
859 Continue = 2,
860 Return = 4,
861 Case = 8,
862 Throw = 16,
863 Goto = 32,
864 All = Break | Continue | Return | Case | Throw | Goto,
865 };
866 int Ignore = 0; // bitmask of Target - what are we *not* highlighting?
867 SourceRange Bounds; // Half-open, restricts reported targets.
868 std::vector<SourceLocation> &Result;
869 const SourceManager &SM;
870
871 // Masks out targets for a traversal into D.
872 // Traverses the subtree using Delegate() if any targets remain.
873 template <typename Func>
filterAndTraverse(DynTypedNode D,const Func & Delegate)874 bool filterAndTraverse(DynTypedNode D, const Func &Delegate) {
875 auto RestoreIgnore = llvm::make_scope_exit(
876 [OldIgnore(Ignore), this] { Ignore = OldIgnore; });
877 if (getFunctionBody(D))
878 Ignore = All;
879 else if (getLoopBody(D))
880 Ignore |= Continue | Break;
881 else if (D.get<SwitchStmt>())
882 Ignore |= Break | Case;
883 // Prune tree if we're not looking for anything.
884 return (Ignore == All) ? true : Delegate();
885 }
886
found(Target T,SourceLocation Loc)887 void found(Target T, SourceLocation Loc) {
888 if (T & Ignore)
889 return;
890 if (SM.isBeforeInTranslationUnit(Loc, Bounds.getBegin()) ||
891 SM.isBeforeInTranslationUnit(Bounds.getEnd(), Loc))
892 return;
893 Result.push_back(Loc);
894 }
895
896 public:
FindControlFlow(SourceRange Bounds,std::vector<SourceLocation> & Result,const SourceManager & SM)897 FindControlFlow(SourceRange Bounds, std::vector<SourceLocation> &Result,
898 const SourceManager &SM)
899 : Bounds(Bounds), Result(Result), SM(SM) {}
900
901 // When traversing function or loops, limit targets to those that still
902 // refer to the original root.
TraverseDecl(Decl * D)903 bool TraverseDecl(Decl *D) {
904 return !D || filterAndTraverse(DynTypedNode::create(*D), [&] {
905 return RecursiveASTVisitor::TraverseDecl(D);
906 });
907 }
TraverseStmt(Stmt * S)908 bool TraverseStmt(Stmt *S) {
909 return !S || filterAndTraverse(DynTypedNode::create(*S), [&] {
910 return RecursiveASTVisitor::TraverseStmt(S);
911 });
912 }
913
914 // Add leaves that we found and want.
VisitReturnStmt(ReturnStmt * R)915 bool VisitReturnStmt(ReturnStmt *R) {
916 found(Return, R->getReturnLoc());
917 return true;
918 }
VisitBreakStmt(BreakStmt * B)919 bool VisitBreakStmt(BreakStmt *B) {
920 found(Break, B->getBreakLoc());
921 return true;
922 }
VisitContinueStmt(ContinueStmt * C)923 bool VisitContinueStmt(ContinueStmt *C) {
924 found(Continue, C->getContinueLoc());
925 return true;
926 }
VisitSwitchCase(SwitchCase * C)927 bool VisitSwitchCase(SwitchCase *C) {
928 found(Case, C->getKeywordLoc());
929 return true;
930 }
VisitCXXThrowExpr(CXXThrowExpr * T)931 bool VisitCXXThrowExpr(CXXThrowExpr *T) {
932 found(Throw, T->getThrowLoc());
933 return true;
934 }
VisitGotoStmt(GotoStmt * G)935 bool VisitGotoStmt(GotoStmt *G) {
936 // Goto is interesting if its target is outside the root.
937 if (const auto *LD = G->getLabel()) {
938 if (SM.isBeforeInTranslationUnit(LD->getLocation(), Bounds.getBegin()) ||
939 SM.isBeforeInTranslationUnit(Bounds.getEnd(), LD->getLocation()))
940 found(Goto, G->getGotoLoc());
941 }
942 return true;
943 }
944 };
945
946 // Given a location within a switch statement, return the half-open range that
947 // covers the case it's contained in.
948 // We treat `case X: case Y: ...` as one case, and assume no other fallthrough.
findCaseBounds(const SwitchStmt & Switch,SourceLocation Loc,const SourceManager & SM)949 SourceRange findCaseBounds(const SwitchStmt &Switch, SourceLocation Loc,
950 const SourceManager &SM) {
951 // Cases are not stored in order, sort them first.
952 // (In fact they seem to be stored in reverse order, don't rely on this)
953 std::vector<const SwitchCase *> Cases;
954 for (const SwitchCase *Case = Switch.getSwitchCaseList(); Case;
955 Case = Case->getNextSwitchCase())
956 Cases.push_back(Case);
957 llvm::sort(Cases, [&](const SwitchCase *L, const SwitchCase *R) {
958 return SM.isBeforeInTranslationUnit(L->getKeywordLoc(), R->getKeywordLoc());
959 });
960
961 // Find the first case after the target location, the end of our range.
962 auto CaseAfter = llvm::partition_point(Cases, [&](const SwitchCase *C) {
963 return !SM.isBeforeInTranslationUnit(Loc, C->getKeywordLoc());
964 });
965 SourceLocation End = CaseAfter == Cases.end() ? Switch.getEndLoc()
966 : (*CaseAfter)->getKeywordLoc();
967
968 // Our target can be before the first case - cases are optional!
969 if (CaseAfter == Cases.begin())
970 return SourceRange(Switch.getBeginLoc(), End);
971 // The start of our range is usually the previous case, but...
972 auto CaseBefore = std::prev(CaseAfter);
973 // ... rewind CaseBefore to the first in a `case A: case B: ...` sequence.
974 while (CaseBefore != Cases.begin() &&
975 (*std::prev(CaseBefore))->getSubStmt() == *CaseBefore)
976 --CaseBefore;
977 return SourceRange((*CaseBefore)->getKeywordLoc(), End);
978 }
979
980 // Returns the locations of control flow statements related to N. e.g.:
981 // for => branches: break/continue/return/throw
982 // break => controlling loop (forwhile/do), and its related control flow
983 // return => all returns/throws from the same function
984 // When an inner block is selected, we include branches bound to outer blocks
985 // as these are exits from the inner block. e.g. return in a for loop.
986 // FIXME: We don't analyze catch blocks, throw is treated the same as return.
relatedControlFlow(const SelectionTree::Node & N)987 std::vector<SourceLocation> relatedControlFlow(const SelectionTree::Node &N) {
988 const SourceManager &SM =
989 N.getDeclContext().getParentASTContext().getSourceManager();
990 std::vector<SourceLocation> Result;
991
992 // First, check if we're at a node that can resolve to a root.
993 enum class Cur { None, Break, Continue, Return, Case, Throw } Cursor;
994 if (N.ASTNode.get<BreakStmt>()) {
995 Cursor = Cur::Break;
996 } else if (N.ASTNode.get<ContinueStmt>()) {
997 Cursor = Cur::Continue;
998 } else if (N.ASTNode.get<ReturnStmt>()) {
999 Cursor = Cur::Return;
1000 } else if (N.ASTNode.get<CXXThrowExpr>()) {
1001 Cursor = Cur::Throw;
1002 } else if (N.ASTNode.get<SwitchCase>()) {
1003 Cursor = Cur::Case;
1004 } else if (const GotoStmt *GS = N.ASTNode.get<GotoStmt>()) {
1005 // We don't know what root to associate with, but highlight the goto/label.
1006 Result.push_back(GS->getGotoLoc());
1007 if (const auto *LD = GS->getLabel())
1008 Result.push_back(LD->getLocation());
1009 Cursor = Cur::None;
1010 } else {
1011 Cursor = Cur::None;
1012 }
1013
1014 const Stmt *Root = nullptr; // Loop or function body to traverse.
1015 SourceRange Bounds;
1016 // Look up the tree for a root (or just at this node if we didn't find a leaf)
1017 for (const auto *P = &N; P; P = P->Parent) {
1018 // return associates with enclosing function
1019 if (const Stmt *FunctionBody = getFunctionBody(P->ASTNode)) {
1020 if (Cursor == Cur::Return || Cursor == Cur::Throw) {
1021 Root = FunctionBody;
1022 }
1023 break; // other leaves don't cross functions.
1024 }
1025 // break/continue associate with enclosing loop.
1026 if (const Stmt *LoopBody = getLoopBody(P->ASTNode)) {
1027 if (Cursor == Cur::None || Cursor == Cur::Break ||
1028 Cursor == Cur::Continue) {
1029 Root = LoopBody;
1030 // Highlight the loop keyword itself.
1031 // FIXME: for do-while, this only covers the `do`..
1032 Result.push_back(P->ASTNode.getSourceRange().getBegin());
1033 break;
1034 }
1035 }
1036 // For switches, users think of case statements as control flow blocks.
1037 // We highlight only occurrences surrounded by the same case.
1038 // We don't detect fallthrough (other than 'case X, case Y').
1039 if (const auto *SS = P->ASTNode.get<SwitchStmt>()) {
1040 if (Cursor == Cur::Break || Cursor == Cur::Case) {
1041 Result.push_back(SS->getSwitchLoc()); // Highlight the switch.
1042 Root = SS->getBody();
1043 // Limit to enclosing case, if there is one.
1044 Bounds = findCaseBounds(*SS, N.ASTNode.getSourceRange().getBegin(), SM);
1045 break;
1046 }
1047 }
1048 // If we didn't start at some interesting node, we're done.
1049 if (Cursor == Cur::None)
1050 break;
1051 }
1052 if (Root) {
1053 if (!Bounds.isValid())
1054 Bounds = Root->getSourceRange();
1055 FindControlFlow(Bounds, Result, SM).TraverseStmt(const_cast<Stmt *>(Root));
1056 }
1057 return Result;
1058 }
1059
toHighlight(const ReferenceFinder::Reference & Ref,const SourceManager & SM)1060 DocumentHighlight toHighlight(const ReferenceFinder::Reference &Ref,
1061 const SourceManager &SM) {
1062 DocumentHighlight DH;
1063 DH.range = Ref.range(SM);
1064 if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Write))
1065 DH.kind = DocumentHighlightKind::Write;
1066 else if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Read))
1067 DH.kind = DocumentHighlightKind::Read;
1068 else
1069 DH.kind = DocumentHighlightKind::Text;
1070 return DH;
1071 }
1072
toHighlight(SourceLocation Loc,const syntax::TokenBuffer & TB)1073 llvm::Optional<DocumentHighlight> toHighlight(SourceLocation Loc,
1074 const syntax::TokenBuffer &TB) {
1075 Loc = TB.sourceManager().getFileLoc(Loc);
1076 if (const auto *Tok = TB.spelledTokenAt(Loc)) {
1077 DocumentHighlight Result;
1078 Result.range = halfOpenToRange(
1079 TB.sourceManager(),
1080 CharSourceRange::getCharRange(Tok->location(), Tok->endLocation()));
1081 return Result;
1082 }
1083 return llvm::None;
1084 }
1085
1086 } // namespace
1087
findDocumentHighlights(ParsedAST & AST,Position Pos)1088 std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,
1089 Position Pos) {
1090 const SourceManager &SM = AST.getSourceManager();
1091 // FIXME: show references to macro within file?
1092 auto CurLoc = sourceLocationInMainFile(SM, Pos);
1093 if (!CurLoc) {
1094 llvm::consumeError(CurLoc.takeError());
1095 return {};
1096 }
1097 std::vector<DocumentHighlight> Result;
1098 auto TryTree = [&](SelectionTree ST) {
1099 if (const SelectionTree::Node *N = ST.commonAncestor()) {
1100 DeclRelationSet Relations =
1101 DeclRelation::TemplatePattern | DeclRelation::Alias;
1102 auto Decls = targetDecl(N->ASTNode, Relations);
1103 if (!Decls.empty()) {
1104 // FIXME: we may get multiple DocumentHighlights with the same location
1105 // and different kinds, deduplicate them.
1106 for (const auto &Ref : findRefs({Decls.begin(), Decls.end()}, AST))
1107 Result.push_back(toHighlight(Ref, SM));
1108 return true;
1109 }
1110 auto ControlFlow = relatedControlFlow(*N);
1111 if (!ControlFlow.empty()) {
1112 for (SourceLocation Loc : ControlFlow)
1113 if (auto Highlight = toHighlight(Loc, AST.getTokens()))
1114 Result.push_back(std::move(*Highlight));
1115 return true;
1116 }
1117 }
1118 return false;
1119 };
1120
1121 unsigned Offset =
1122 AST.getSourceManager().getDecomposedSpellingLoc(*CurLoc).second;
1123 SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset,
1124 Offset, TryTree);
1125 return Result;
1126 }
1127
findImplementations(ParsedAST & AST,Position Pos,const SymbolIndex * Index)1128 std::vector<LocatedSymbol> findImplementations(ParsedAST &AST, Position Pos,
1129 const SymbolIndex *Index) {
1130 // We rely on index to find the implementations in subclasses.
1131 // FIXME: Index can be stale, so we may loose some latest results from the
1132 // main file.
1133 if (!Index)
1134 return {};
1135 const SourceManager &SM = AST.getSourceManager();
1136 auto MainFilePath =
1137 getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
1138 if (!MainFilePath) {
1139 elog("Failed to get a path for the main file, so no implementations.");
1140 return {};
1141 }
1142 auto CurLoc = sourceLocationInMainFile(SM, Pos);
1143 if (!CurLoc) {
1144 elog("Failed to convert position to source location: {0}",
1145 CurLoc.takeError());
1146 return {};
1147 }
1148 std::vector<LocatedSymbol> Results;
1149 DeclRelationSet Relations =
1150 DeclRelation::TemplatePattern | DeclRelation::Alias;
1151 RelationsRequest Req;
1152 Req.Predicate = RelationKind::OverriddenBy;
1153 for (const NamedDecl *ND : getDeclAtPosition(AST, *CurLoc, Relations))
1154 if (const CXXMethodDecl *CXXMD = llvm::dyn_cast<CXXMethodDecl>(ND))
1155 if (CXXMD->isVirtual())
1156 Req.Subjects.insert(getSymbolID(ND));
1157
1158 if (Req.Subjects.empty())
1159 return Results;
1160 Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
1161 auto DeclLoc =
1162 indexToLSPLocation(Object.CanonicalDeclaration, *MainFilePath);
1163 if (!DeclLoc) {
1164 elog("Find implementation: {0}", DeclLoc.takeError());
1165 return;
1166 }
1167 LocatedSymbol Loc;
1168 Loc.Name = Object.Name.str();
1169 Loc.PreferredDeclaration = *DeclLoc;
1170 auto DefLoc = indexToLSPLocation(Object.Definition, *MainFilePath);
1171 if (DefLoc)
1172 Loc.Definition = *DefLoc;
1173 else
1174 llvm::consumeError(DefLoc.takeError());
1175 Results.push_back(Loc);
1176 });
1177 return Results;
1178 }
1179
findReferences(ParsedAST & AST,Position Pos,uint32_t Limit,const SymbolIndex * Index)1180 ReferencesResult findReferences(ParsedAST &AST, Position Pos, uint32_t Limit,
1181 const SymbolIndex *Index) {
1182 if (!Limit)
1183 Limit = std::numeric_limits<uint32_t>::max();
1184 ReferencesResult Results;
1185 const SourceManager &SM = AST.getSourceManager();
1186 auto MainFilePath =
1187 getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
1188 if (!MainFilePath) {
1189 elog("Failed to get a path for the main file, so no references");
1190 return Results;
1191 }
1192 auto URIMainFile = URIForFile::canonicalize(*MainFilePath, *MainFilePath);
1193 auto CurLoc = sourceLocationInMainFile(SM, Pos);
1194 if (!CurLoc) {
1195 llvm::consumeError(CurLoc.takeError());
1196 return {};
1197 }
1198 llvm::Optional<DefinedMacro> Macro;
1199 if (const auto *IdentifierAtCursor =
1200 syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens())) {
1201 Macro = locateMacroAt(*IdentifierAtCursor, AST.getPreprocessor());
1202 }
1203
1204 RefsRequest Req;
1205 if (Macro) {
1206 // Handle references to macro.
1207 if (auto MacroSID = getSymbolID(Macro->Name, Macro->Info, SM)) {
1208 // Collect macro references from main file.
1209 const auto &IDToRefs = AST.getMacros().MacroRefs;
1210 auto Refs = IDToRefs.find(MacroSID);
1211 if (Refs != IDToRefs.end()) {
1212 for (const auto &Ref : Refs->second) {
1213 Location Result;
1214 Result.range = Ref;
1215 Result.uri = URIMainFile;
1216 Results.References.push_back(std::move(Result));
1217 }
1218 }
1219 Req.IDs.insert(MacroSID);
1220 }
1221 } else {
1222 // Handle references to Decls.
1223
1224 DeclRelationSet Relations =
1225 DeclRelation::TemplatePattern | DeclRelation::Alias;
1226 std::vector<const NamedDecl *> Decls =
1227 getDeclAtPosition(AST, *CurLoc, Relations);
1228
1229 // We traverse the AST to find references in the main file.
1230 auto MainFileRefs = findRefs(Decls, AST);
1231 // We may get multiple refs with the same location and different Roles, as
1232 // cross-reference is only interested in locations, we deduplicate them
1233 // by the location to avoid emitting duplicated locations.
1234 MainFileRefs.erase(std::unique(MainFileRefs.begin(), MainFileRefs.end(),
1235 [](const ReferenceFinder::Reference &L,
1236 const ReferenceFinder::Reference &R) {
1237 return L.SpelledTok.location() ==
1238 R.SpelledTok.location();
1239 }),
1240 MainFileRefs.end());
1241 for (const auto &Ref : MainFileRefs) {
1242 Location Result;
1243 Result.range = Ref.range(SM);
1244 Result.uri = URIMainFile;
1245 Results.References.push_back(std::move(Result));
1246 }
1247 if (Index && Results.References.size() <= Limit) {
1248 for (const Decl *D : Decls) {
1249 // Not all symbols can be referenced from outside (e.g.
1250 // function-locals).
1251 // TODO: we could skip TU-scoped symbols here (e.g. static functions) if
1252 // we know this file isn't a header. The details might be tricky.
1253 if (D->getParentFunctionOrMethod())
1254 continue;
1255 if (auto ID = getSymbolID(D))
1256 Req.IDs.insert(ID);
1257 }
1258 }
1259 }
1260 // Now query the index for references from other files.
1261 if (!Req.IDs.empty() && Index && Results.References.size() <= Limit) {
1262 Req.Limit = Limit;
1263 Results.HasMore |= Index->refs(Req, [&](const Ref &R) {
1264 // No need to continue process if we reach the limit.
1265 if (Results.References.size() > Limit)
1266 return;
1267 auto LSPLoc = toLSPLocation(R.Location, *MainFilePath);
1268 // Avoid indexed results for the main file - the AST is authoritative.
1269 if (!LSPLoc || LSPLoc->uri.file() == *MainFilePath)
1270 return;
1271
1272 Results.References.push_back(std::move(*LSPLoc));
1273 });
1274 }
1275 if (Results.References.size() > Limit) {
1276 Results.HasMore = true;
1277 Results.References.resize(Limit);
1278 }
1279 return Results;
1280 }
1281
getSymbolInfo(ParsedAST & AST,Position Pos)1282 std::vector<SymbolDetails> getSymbolInfo(ParsedAST &AST, Position Pos) {
1283 const SourceManager &SM = AST.getSourceManager();
1284 auto CurLoc = sourceLocationInMainFile(SM, Pos);
1285 if (!CurLoc) {
1286 llvm::consumeError(CurLoc.takeError());
1287 return {};
1288 }
1289
1290 std::vector<SymbolDetails> Results;
1291
1292 // We also want the targets of using-decls, so we include
1293 // DeclRelation::Underlying.
1294 DeclRelationSet Relations = DeclRelation::TemplatePattern |
1295 DeclRelation::Alias | DeclRelation::Underlying;
1296 for (const NamedDecl *D : getDeclAtPosition(AST, *CurLoc, Relations)) {
1297 SymbolDetails NewSymbol;
1298 std::string QName = printQualifiedName(*D);
1299 auto SplitQName = splitQualifiedName(QName);
1300 NewSymbol.containerName = std::string(SplitQName.first);
1301 NewSymbol.name = std::string(SplitQName.second);
1302
1303 if (NewSymbol.containerName.empty()) {
1304 if (const auto *ParentND =
1305 dyn_cast_or_null<NamedDecl>(D->getDeclContext()))
1306 NewSymbol.containerName = printQualifiedName(*ParentND);
1307 }
1308 llvm::SmallString<32> USR;
1309 if (!index::generateUSRForDecl(D, USR)) {
1310 NewSymbol.USR = std::string(USR.str());
1311 NewSymbol.ID = SymbolID(NewSymbol.USR);
1312 }
1313 Results.push_back(std::move(NewSymbol));
1314 }
1315
1316 const auto *IdentifierAtCursor =
1317 syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens());
1318 if (!IdentifierAtCursor)
1319 return Results;
1320
1321 if (auto M = locateMacroAt(*IdentifierAtCursor, AST.getPreprocessor())) {
1322 SymbolDetails NewMacro;
1323 NewMacro.name = std::string(M->Name);
1324 llvm::SmallString<32> USR;
1325 if (!index::generateUSRForMacro(NewMacro.name, M->Info->getDefinitionLoc(),
1326 SM, USR)) {
1327 NewMacro.USR = std::string(USR.str());
1328 NewMacro.ID = SymbolID(NewMacro.USR);
1329 }
1330 Results.push_back(std::move(NewMacro));
1331 }
1332
1333 return Results;
1334 }
1335
operator <<(llvm::raw_ostream & OS,const LocatedSymbol & S)1336 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const LocatedSymbol &S) {
1337 OS << S.Name << ": " << S.PreferredDeclaration;
1338 if (S.Definition)
1339 OS << " def=" << *S.Definition;
1340 return OS;
1341 }
1342
1343 template <typename HierarchyItem>
declToHierarchyItem(const NamedDecl & ND)1344 static llvm::Optional<HierarchyItem> declToHierarchyItem(const NamedDecl &ND) {
1345 ASTContext &Ctx = ND.getASTContext();
1346 auto &SM = Ctx.getSourceManager();
1347 SourceLocation NameLoc = nameLocation(ND, Ctx.getSourceManager());
1348 SourceLocation BeginLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getBeginLoc()));
1349 SourceLocation EndLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getEndLoc()));
1350 const auto DeclRange =
1351 toHalfOpenFileRange(SM, Ctx.getLangOpts(), {BeginLoc, EndLoc});
1352 if (!DeclRange)
1353 return llvm::None;
1354 auto FilePath =
1355 getCanonicalPath(SM.getFileEntryForID(SM.getFileID(NameLoc)), SM);
1356 auto TUPath = getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
1357 if (!FilePath || !TUPath)
1358 return llvm::None; // Not useful without a uri.
1359
1360 Position NameBegin = sourceLocToPosition(SM, NameLoc);
1361 Position NameEnd = sourceLocToPosition(
1362 SM, Lexer::getLocForEndOfToken(NameLoc, 0, SM, Ctx.getLangOpts()));
1363
1364 index::SymbolInfo SymInfo = index::getSymbolInfo(&ND);
1365 // FIXME: This is not classifying constructors, destructors and operators
1366 // correctly.
1367 SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind);
1368
1369 HierarchyItem HI;
1370 HI.name = printName(Ctx, ND);
1371 HI.kind = SK;
1372 HI.range = Range{sourceLocToPosition(SM, DeclRange->getBegin()),
1373 sourceLocToPosition(SM, DeclRange->getEnd())};
1374 HI.selectionRange = Range{NameBegin, NameEnd};
1375 if (!HI.range.contains(HI.selectionRange)) {
1376 // 'selectionRange' must be contained in 'range', so in cases where clang
1377 // reports unrelated ranges we need to reconcile somehow.
1378 HI.range = HI.selectionRange;
1379 }
1380
1381 HI.uri = URIForFile::canonicalize(*FilePath, *TUPath);
1382
1383 // Compute the SymbolID and store it in the 'data' field.
1384 // This allows typeHierarchy/resolve to be used to
1385 // resolve children of items returned in a previous request
1386 // for parents.
1387 if (auto ID = getSymbolID(&ND))
1388 HI.data = ID.str();
1389
1390 return HI;
1391 }
1392
1393 static llvm::Optional<TypeHierarchyItem>
declToTypeHierarchyItem(const NamedDecl & ND)1394 declToTypeHierarchyItem(const NamedDecl &ND) {
1395 auto Result = declToHierarchyItem<TypeHierarchyItem>(ND);
1396 if (Result)
1397 Result->deprecated = ND.isDeprecated();
1398 return Result;
1399 }
1400
1401 static llvm::Optional<CallHierarchyItem>
declToCallHierarchyItem(const NamedDecl & ND)1402 declToCallHierarchyItem(const NamedDecl &ND) {
1403 auto Result = declToHierarchyItem<CallHierarchyItem>(ND);
1404 if (Result && ND.isDeprecated())
1405 Result->tags.push_back(SymbolTag::Deprecated);
1406 return Result;
1407 }
1408
1409 template <typename HierarchyItem>
symbolToHierarchyItem(const Symbol & S,PathRef TUPath)1410 static llvm::Optional<HierarchyItem> symbolToHierarchyItem(const Symbol &S,
1411 PathRef TUPath) {
1412 auto Loc = symbolToLocation(S, TUPath);
1413 if (!Loc) {
1414 elog("Failed to convert symbol to hierarchy item: {0}", Loc.takeError());
1415 return llvm::None;
1416 }
1417 HierarchyItem HI;
1418 HI.name = std::string(S.Name);
1419 HI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind);
1420 HI.selectionRange = Loc->range;
1421 // FIXME: Populate 'range' correctly
1422 // (https://github.com/clangd/clangd/issues/59).
1423 HI.range = HI.selectionRange;
1424 HI.uri = Loc->uri;
1425 // Store the SymbolID in the 'data' field. The client will
1426 // send this back in requests to resolve additional levels
1427 // of the hierarchy.
1428 HI.data = S.ID.str();
1429
1430 return HI;
1431 }
1432
1433 static llvm::Optional<TypeHierarchyItem>
symbolToTypeHierarchyItem(const Symbol & S,PathRef TUPath)1434 symbolToTypeHierarchyItem(const Symbol &S, PathRef TUPath) {
1435 auto Result = symbolToHierarchyItem<TypeHierarchyItem>(S, TUPath);
1436 if (Result)
1437 Result->deprecated = (S.Flags & Symbol::Deprecated);
1438 return Result;
1439 }
1440
1441 static llvm::Optional<CallHierarchyItem>
symbolToCallHierarchyItem(const Symbol & S,PathRef TUPath)1442 symbolToCallHierarchyItem(const Symbol &S, PathRef TUPath) {
1443 auto Result = symbolToHierarchyItem<CallHierarchyItem>(S, TUPath);
1444 if (Result && (S.Flags & Symbol::Deprecated))
1445 Result->tags.push_back(SymbolTag::Deprecated);
1446 return Result;
1447 }
1448
fillSubTypes(const SymbolID & ID,std::vector<TypeHierarchyItem> & SubTypes,const SymbolIndex * Index,int Levels,PathRef TUPath)1449 static void fillSubTypes(const SymbolID &ID,
1450 std::vector<TypeHierarchyItem> &SubTypes,
1451 const SymbolIndex *Index, int Levels, PathRef TUPath) {
1452 RelationsRequest Req;
1453 Req.Subjects.insert(ID);
1454 Req.Predicate = RelationKind::BaseOf;
1455 Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
1456 if (Optional<TypeHierarchyItem> ChildSym =
1457 symbolToTypeHierarchyItem(Object, TUPath)) {
1458 if (Levels > 1) {
1459 ChildSym->children.emplace();
1460 fillSubTypes(Object.ID, *ChildSym->children, Index, Levels - 1, TUPath);
1461 }
1462 SubTypes.emplace_back(std::move(*ChildSym));
1463 }
1464 });
1465 }
1466
1467 using RecursionProtectionSet = llvm::SmallSet<const CXXRecordDecl *, 4>;
1468
fillSuperTypes(const CXXRecordDecl & CXXRD,ASTContext & ASTCtx,std::vector<TypeHierarchyItem> & SuperTypes,RecursionProtectionSet & RPSet)1469 static void fillSuperTypes(const CXXRecordDecl &CXXRD, ASTContext &ASTCtx,
1470 std::vector<TypeHierarchyItem> &SuperTypes,
1471 RecursionProtectionSet &RPSet) {
1472 // typeParents() will replace dependent template specializations
1473 // with their class template, so to avoid infinite recursion for
1474 // certain types of hierarchies, keep the templates encountered
1475 // along the parent chain in a set, and stop the recursion if one
1476 // starts to repeat.
1477 auto *Pattern = CXXRD.getDescribedTemplate() ? &CXXRD : nullptr;
1478 if (Pattern) {
1479 if (!RPSet.insert(Pattern).second) {
1480 return;
1481 }
1482 }
1483
1484 for (const CXXRecordDecl *ParentDecl : typeParents(&CXXRD)) {
1485 if (Optional<TypeHierarchyItem> ParentSym =
1486 declToTypeHierarchyItem(*ParentDecl)) {
1487 ParentSym->parents.emplace();
1488 fillSuperTypes(*ParentDecl, ASTCtx, *ParentSym->parents, RPSet);
1489 SuperTypes.emplace_back(std::move(*ParentSym));
1490 }
1491 }
1492
1493 if (Pattern) {
1494 RPSet.erase(Pattern);
1495 }
1496 }
1497
findRecordTypeAt(ParsedAST & AST,Position Pos)1498 const CXXRecordDecl *findRecordTypeAt(ParsedAST &AST, Position Pos) {
1499 auto RecordFromNode =
1500 [](const SelectionTree::Node *N) -> const CXXRecordDecl * {
1501 if (!N)
1502 return nullptr;
1503
1504 // Note: explicitReferenceTargets() will search for both template
1505 // instantiations and template patterns, and prefer the former if available
1506 // (generally, one will be available for non-dependent specializations of a
1507 // class template).
1508 auto Decls = explicitReferenceTargets(N->ASTNode, DeclRelation::Underlying);
1509 if (Decls.empty())
1510 return nullptr;
1511
1512 const NamedDecl *D = Decls[0];
1513
1514 if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
1515 // If this is a variable, use the type of the variable.
1516 return VD->getType().getTypePtr()->getAsCXXRecordDecl();
1517 }
1518
1519 if (const CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(D)) {
1520 // If this is a method, use the type of the class.
1521 return Method->getParent();
1522 }
1523
1524 // We don't handle FieldDecl because it's not clear what behaviour
1525 // the user would expect: the enclosing class type (as with a
1526 // method), or the field's type (as with a variable).
1527
1528 return dyn_cast<CXXRecordDecl>(D);
1529 };
1530
1531 const SourceManager &SM = AST.getSourceManager();
1532 const CXXRecordDecl *Result = nullptr;
1533 auto Offset = positionToOffset(SM.getBufferData(SM.getMainFileID()), Pos);
1534 if (!Offset) {
1535 llvm::consumeError(Offset.takeError());
1536 return Result;
1537 }
1538 SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), *Offset,
1539 *Offset, [&](SelectionTree ST) {
1540 Result = RecordFromNode(ST.commonAncestor());
1541 return Result != nullptr;
1542 });
1543 return Result;
1544 }
1545
typeParents(const CXXRecordDecl * CXXRD)1546 std::vector<const CXXRecordDecl *> typeParents(const CXXRecordDecl *CXXRD) {
1547 std::vector<const CXXRecordDecl *> Result;
1548
1549 // If this is an invalid instantiation, instantiation of the bases
1550 // may not have succeeded, so fall back to the template pattern.
1551 if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD)) {
1552 if (CTSD->isInvalidDecl())
1553 CXXRD = CTSD->getSpecializedTemplate()->getTemplatedDecl();
1554 }
1555
1556 // Can't query bases without a definition.
1557 if (!CXXRD->hasDefinition())
1558 return Result;
1559
1560 for (auto Base : CXXRD->bases()) {
1561 const CXXRecordDecl *ParentDecl = nullptr;
1562
1563 const Type *Type = Base.getType().getTypePtr();
1564 if (const RecordType *RT = Type->getAs<RecordType>()) {
1565 ParentDecl = RT->getAsCXXRecordDecl();
1566 }
1567
1568 if (!ParentDecl) {
1569 // Handle a dependent base such as "Base<T>" by using the primary
1570 // template.
1571 if (const TemplateSpecializationType *TS =
1572 Type->getAs<TemplateSpecializationType>()) {
1573 TemplateName TN = TS->getTemplateName();
1574 if (TemplateDecl *TD = TN.getAsTemplateDecl()) {
1575 ParentDecl = dyn_cast<CXXRecordDecl>(TD->getTemplatedDecl());
1576 }
1577 }
1578 }
1579
1580 if (ParentDecl)
1581 Result.push_back(ParentDecl);
1582 }
1583
1584 return Result;
1585 }
1586
1587 llvm::Optional<TypeHierarchyItem>
getTypeHierarchy(ParsedAST & AST,Position Pos,int ResolveLevels,TypeHierarchyDirection Direction,const SymbolIndex * Index,PathRef TUPath)1588 getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
1589 TypeHierarchyDirection Direction, const SymbolIndex *Index,
1590 PathRef TUPath) {
1591 const CXXRecordDecl *CXXRD = findRecordTypeAt(AST, Pos);
1592 if (!CXXRD)
1593 return llvm::None;
1594
1595 bool WantParents = Direction == TypeHierarchyDirection::Parents ||
1596 Direction == TypeHierarchyDirection::Both;
1597 bool WantChildren = Direction == TypeHierarchyDirection::Children ||
1598 Direction == TypeHierarchyDirection::Both;
1599
1600 // If we're looking for children, we're doing the lookup in the index.
1601 // The index does not store relationships between implicit
1602 // specializations, so if we have one, use the template pattern instead.
1603 // Note that this needs to be done before the declToTypeHierarchyItem(),
1604 // otherwise the type hierarchy item would misleadingly contain the
1605 // specialization parameters, while the children would involve classes
1606 // that derive from other specializations of the template.
1607 if (WantChildren) {
1608 if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD))
1609 CXXRD = CTSD->getTemplateInstantiationPattern();
1610 }
1611
1612 Optional<TypeHierarchyItem> Result = declToTypeHierarchyItem(*CXXRD);
1613 if (!Result)
1614 return Result;
1615
1616 if (WantParents) {
1617 Result->parents.emplace();
1618
1619 RecursionProtectionSet RPSet;
1620 fillSuperTypes(*CXXRD, AST.getASTContext(), *Result->parents, RPSet);
1621 }
1622
1623 if (WantChildren && ResolveLevels > 0) {
1624 Result->children.emplace();
1625
1626 if (Index) {
1627 if (auto ID = getSymbolID(CXXRD))
1628 fillSubTypes(ID, *Result->children, Index, ResolveLevels, TUPath);
1629 }
1630 }
1631
1632 return Result;
1633 }
1634
resolveTypeHierarchy(TypeHierarchyItem & Item,int ResolveLevels,TypeHierarchyDirection Direction,const SymbolIndex * Index)1635 void resolveTypeHierarchy(TypeHierarchyItem &Item, int ResolveLevels,
1636 TypeHierarchyDirection Direction,
1637 const SymbolIndex *Index) {
1638 // We only support typeHierarchy/resolve for children, because for parents
1639 // we ignore ResolveLevels and return all levels of parents eagerly.
1640 if (Direction == TypeHierarchyDirection::Parents || ResolveLevels == 0)
1641 return;
1642
1643 Item.children.emplace();
1644
1645 if (Index && Item.data) {
1646 // We store the item's SymbolID in the 'data' field, and the client
1647 // passes it back to us in typeHierarchy/resolve.
1648 if (Expected<SymbolID> ID = SymbolID::fromStr(*Item.data)) {
1649 fillSubTypes(*ID, *Item.children, Index, ResolveLevels, Item.uri.file());
1650 }
1651 }
1652 }
1653
1654 std::vector<CallHierarchyItem>
prepareCallHierarchy(ParsedAST & AST,Position Pos,PathRef TUPath)1655 prepareCallHierarchy(ParsedAST &AST, Position Pos, PathRef TUPath) {
1656 std::vector<CallHierarchyItem> Result;
1657 const auto &SM = AST.getSourceManager();
1658 auto Loc = sourceLocationInMainFile(SM, Pos);
1659 if (!Loc) {
1660 elog("prepareCallHierarchy failed to convert position to source location: "
1661 "{0}",
1662 Loc.takeError());
1663 return Result;
1664 }
1665 for (const NamedDecl *Decl : getDeclAtPosition(AST, *Loc, {})) {
1666 if (!Decl->isFunctionOrFunctionTemplate())
1667 continue;
1668 if (auto CHI = declToCallHierarchyItem(*Decl))
1669 Result.emplace_back(std::move(*CHI));
1670 }
1671 return Result;
1672 }
1673
1674 std::vector<CallHierarchyIncomingCall>
incomingCalls(const CallHierarchyItem & Item,const SymbolIndex * Index)1675 incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) {
1676 std::vector<CallHierarchyIncomingCall> Results;
1677 if (!Index || Item.data.empty())
1678 return Results;
1679 auto ID = SymbolID::fromStr(Item.data);
1680 if (!ID) {
1681 elog("incomingCalls failed to find symbol: {0}", ID.takeError());
1682 return Results;
1683 }
1684 // In this function, we find incoming calls based on the index only.
1685 // In principle, the AST could have more up-to-date information about
1686 // occurrences within the current file. However, going from a SymbolID
1687 // to an AST node isn't cheap, particularly when the declaration isn't
1688 // in the main file.
1689 // FIXME: Consider also using AST information when feasible.
1690 RefsRequest Request;
1691 Request.IDs.insert(*ID);
1692 // We could restrict more specifically to calls by introducing a new RefKind,
1693 // but non-call references (such as address-of-function) can still be
1694 // interesting as they can indicate indirect calls.
1695 Request.Filter = RefKind::Reference;
1696 // Initially store the ranges in a map keyed by SymbolID of the caller.
1697 // This allows us to group different calls with the same caller
1698 // into the same CallHierarchyIncomingCall.
1699 llvm::DenseMap<SymbolID, std::vector<Range>> CallsIn;
1700 // We can populate the ranges based on a refs request only. As we do so, we
1701 // also accumulate the container IDs into a lookup request.
1702 LookupRequest ContainerLookup;
1703 Index->refs(Request, [&](const Ref &R) {
1704 auto Loc = indexToLSPLocation(R.Location, Item.uri.file());
1705 if (!Loc) {
1706 elog("incomingCalls failed to convert location: {0}", Loc.takeError());
1707 return;
1708 }
1709 auto It = CallsIn.try_emplace(R.Container, std::vector<Range>{}).first;
1710 It->second.push_back(Loc->range);
1711
1712 ContainerLookup.IDs.insert(R.Container);
1713 });
1714 // Perform the lookup request and combine its results with CallsIn to
1715 // get complete CallHierarchyIncomingCall objects.
1716 Index->lookup(ContainerLookup, [&](const Symbol &Caller) {
1717 auto It = CallsIn.find(Caller.ID);
1718 assert(It != CallsIn.end());
1719 if (auto CHI = symbolToCallHierarchyItem(Caller, Item.uri.file()))
1720 Results.push_back(
1721 CallHierarchyIncomingCall{std::move(*CHI), std::move(It->second)});
1722 });
1723 // Sort results by name of container.
1724 llvm::sort(Results, [](const CallHierarchyIncomingCall &A,
1725 const CallHierarchyIncomingCall &B) {
1726 return A.from.name < B.from.name;
1727 });
1728 return Results;
1729 }
1730
getNonLocalDeclRefs(ParsedAST & AST,const FunctionDecl * FD)1731 llvm::DenseSet<const Decl *> getNonLocalDeclRefs(ParsedAST &AST,
1732 const FunctionDecl *FD) {
1733 if (!FD->hasBody())
1734 return {};
1735 llvm::DenseSet<const Decl *> DeclRefs;
1736 findExplicitReferences(FD, [&](ReferenceLoc Ref) {
1737 for (const Decl *D : Ref.Targets) {
1738 if (!index::isFunctionLocalSymbol(D) && !D->isTemplateParameter() &&
1739 !Ref.IsDecl)
1740 DeclRefs.insert(D);
1741 }
1742 });
1743 return DeclRefs;
1744 }
1745 } // namespace clangd
1746 } // namespace clang
1747