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