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