clang-tools  12.0.0git
FindSymbols.cpp
Go to the documentation of this file.
1 //===--- FindSymbols.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 "FindSymbols.h"
9 
10 #include "AST.h"
11 #include "FuzzyMatch.h"
12 #include "ParsedAST.h"
13 #include "Quality.h"
14 #include "SourceCode.h"
15 #include "index/Index.h"
16 #include "support/Logger.h"
17 #include "clang/AST/DeclTemplate.h"
18 #include "clang/Index/IndexDataConsumer.h"
19 #include "clang/Index/IndexSymbol.h"
20 #include "clang/Index/IndexingAction.h"
21 #include "llvm/ADT/StringRef.h"
22 #include "llvm/Support/FormatVariadic.h"
23 #include "llvm/Support/Path.h"
24 #include "llvm/Support/ScopedPrinter.h"
25 
26 #define DEBUG_TYPE "FindSymbols"
27 
28 namespace clang {
29 namespace clangd {
30 
31 namespace {
32 using ScoredSymbolInfo = std::pair<float, SymbolInformation>;
33 struct ScoredSymbolGreater {
34  bool operator()(const ScoredSymbolInfo &L, const ScoredSymbolInfo &R) {
35  if (L.first != R.first)
36  return L.first > R.first;
37  return L.second.name < R.second.name; // Earlier name is better.
38  }
39 };
40 
41 } // namespace
42 
43 llvm::Expected<Location> indexToLSPLocation(const SymbolLocation &Loc,
44  llvm::StringRef TUPath) {
45  auto Path = URI::resolve(Loc.FileURI, TUPath);
46  if (!Path) {
47  return llvm::make_error<llvm::StringError>(
48  llvm::formatv("Could not resolve path for file '{0}': {1}", Loc.FileURI,
49  llvm::toString(Path.takeError())),
50  llvm::inconvertibleErrorCode());
51  }
52  Location L;
53  L.uri = URIForFile::canonicalize(*Path, TUPath);
54  Position Start, End;
55  Start.line = Loc.Start.line();
56  Start.character = Loc.Start.column();
57  End.line = Loc.End.line();
58  End.character = Loc.End.column();
59  L.range = {Start, End};
60  return L;
61 }
62 
63 llvm::Expected<Location> symbolToLocation(const Symbol &Sym,
64  llvm::StringRef TUPath) {
65  // Prefer the definition over e.g. a function declaration in a header
66  return indexToLSPLocation(
67  Sym.Definition ? Sym.Definition : Sym.CanonicalDeclaration, TUPath);
68 }
69 
70 llvm::Expected<std::vector<SymbolInformation>>
71 getWorkspaceSymbols(llvm::StringRef Query, int Limit,
72  const SymbolIndex *const Index, llvm::StringRef HintPath) {
73  std::vector<SymbolInformation> Result;
74  if (Query.empty() || !Index)
75  return Result;
76 
77  auto Names = splitQualifiedName(Query);
78 
79  FuzzyFindRequest Req;
80  Req.Query = std::string(Names.second);
81 
82  // FuzzyFind doesn't want leading :: qualifier
83  bool IsGlobalQuery = Names.first.consume_front("::");
84  // Restrict results to the scope in the query string if present (global or
85  // not).
86  if (IsGlobalQuery || !Names.first.empty())
87  Req.Scopes = {std::string(Names.first)};
88  else
89  Req.AnyScope = true;
90  if (Limit)
91  Req.Limit = Limit;
93  Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max());
94  FuzzyMatcher Filter(Req.Query);
95  Index->fuzzyFind(Req, [HintPath, &Top, &Filter](const Symbol &Sym) {
96  auto Loc = symbolToLocation(Sym, HintPath);
97  if (!Loc) {
98  log("Workspace symbols: {0}", Loc.takeError());
99  return;
100  }
101 
103  std::string Scope = std::string(Sym.Scope);
104  llvm::StringRef ScopeRef = Scope;
105  ScopeRef.consume_back("::");
107  SK, *Loc, std::string(ScopeRef)};
108 
110  Quality.merge(Sym);
111  SymbolRelevanceSignals Relevance;
112  Relevance.Name = Sym.Name;
114  if (auto NameMatch = Filter.match(Sym.Name))
115  Relevance.NameMatch = *NameMatch;
116  else {
117  log("Workspace symbol: {0} didn't match query {1}", Sym.Name,
118  Filter.pattern());
119  return;
120  }
121  Relevance.merge(Sym);
122  auto Score =
123  evaluateSymbolAndRelevance(Quality.evaluate(), Relevance.evaluate());
124  dlog("FindSymbols: {0}{1} = {2}\n{3}{4}\n", Sym.Scope, Sym.Name, Score,
125  Quality, Relevance);
126 
127  Top.push({Score, std::move(Info)});
128  });
129  for (auto &R : std::move(Top).items())
130  Result.push_back(std::move(R.second));
131  return Result;
132 }
133 
134 namespace {
135 llvm::Optional<DocumentSymbol> declToSym(ASTContext &Ctx, const NamedDecl &ND) {
136  auto &SM = Ctx.getSourceManager();
137 
138  SourceLocation NameLoc = nameLocation(ND, SM);
139  SourceLocation BeginLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getBeginLoc()));
140  SourceLocation EndLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getEndLoc()));
141  const auto SymbolRange =
142  toHalfOpenFileRange(SM, Ctx.getLangOpts(), {BeginLoc, EndLoc});
143  if (!SymbolRange)
144  return llvm::None;
145 
146  Position NameBegin = sourceLocToPosition(SM, NameLoc);
147  Position NameEnd = sourceLocToPosition(
148  SM, Lexer::getLocForEndOfToken(NameLoc, 0, SM, Ctx.getLangOpts()));
149 
151  // FIXME: this is not classifying constructors, destructors and operators
152  // correctly (they're all "methods").
153  SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind);
154 
155  DocumentSymbol SI;
156  SI.name = printName(Ctx, ND);
157  SI.kind = SK;
158  SI.deprecated = ND.isDeprecated();
159  SI.range = Range{sourceLocToPosition(SM, SymbolRange->getBegin()),
160  sourceLocToPosition(SM, SymbolRange->getEnd())};
161  SI.selectionRange = Range{NameBegin, NameEnd};
162  if (!SI.range.contains(SI.selectionRange)) {
163  // 'selectionRange' must be contained in 'range', so in cases where clang
164  // reports unrelated ranges we need to reconcile somehow.
165  SI.range = SI.selectionRange;
166  }
167  return SI;
168 }
169 
170 /// A helper class to build an outline for the parse AST. It traverses the AST
171 /// directly instead of using RecursiveASTVisitor (RAV) for three main reasons:
172 /// - there is no way to keep RAV from traversing subtrees we are not
173 /// interested in. E.g. not traversing function locals or implicit template
174 /// instantiations.
175 /// - it's easier to combine results of recursive passes,
176 /// - visiting decls is actually simple, so we don't hit the complicated
177 /// cases that RAV mostly helps with (types, expressions, etc.)
178 class DocumentOutline {
179 public:
180  DocumentOutline(ParsedAST &AST) : AST(AST) {}
181 
182  /// Builds the document outline for the generated AST.
183  std::vector<DocumentSymbol> build() {
184  std::vector<DocumentSymbol> Results;
185  for (auto &TopLevel : AST.getLocalTopLevelDecls())
186  traverseDecl(TopLevel, Results);
187  return Results;
188  }
189 
190 private:
191  enum class VisitKind { No, OnlyDecl, DeclAndChildren };
192 
193  void traverseDecl(Decl *D, std::vector<DocumentSymbol> &Results) {
194  if (auto *Templ = llvm::dyn_cast<TemplateDecl>(D)) {
195  // TemplatedDecl might be null, e.g. concepts.
196  if (auto *TD = Templ->getTemplatedDecl())
197  D = TD;
198  }
199  auto *ND = llvm::dyn_cast<NamedDecl>(D);
200  if (!ND)
201  return;
202  VisitKind Visit = shouldVisit(ND);
203  if (Visit == VisitKind::No)
204  return;
205  llvm::Optional<DocumentSymbol> Sym = declToSym(AST.getASTContext(), *ND);
206  if (!Sym)
207  return;
208  if (Visit == VisitKind::DeclAndChildren)
209  traverseChildren(D, Sym->children);
210  Results.push_back(std::move(*Sym));
211  }
212 
213  void traverseChildren(Decl *D, std::vector<DocumentSymbol> &Results) {
214  auto *Scope = llvm::dyn_cast<DeclContext>(D);
215  if (!Scope)
216  return;
217  for (auto *C : Scope->decls())
218  traverseDecl(C, Results);
219  }
220 
221  VisitKind shouldVisit(NamedDecl *D) {
222  if (D->isImplicit())
223  return VisitKind::No;
224 
225  if (auto Func = llvm::dyn_cast<FunctionDecl>(D)) {
226  // Some functions are implicit template instantiations, those should be
227  // ignored.
228  if (auto *Info = Func->getTemplateSpecializationInfo()) {
229  if (!Info->isExplicitInstantiationOrSpecialization())
230  return VisitKind::No;
231  }
232  // Only visit the function itself, do not visit the children (i.e.
233  // function parameters, etc.)
234  return VisitKind::OnlyDecl;
235  }
236  // Handle template instantiations. We have three cases to consider:
237  // - explicit instantiations, e.g. 'template class std::vector<int>;'
238  // Visit the decl itself (it's present in the code), but not the
239  // children.
240  // - implicit instantiations, i.e. not written by the user.
241  // Do not visit at all, they are not present in the code.
242  // - explicit specialization, e.g. 'template <> class vector<bool> {};'
243  // Visit both the decl and its children, both are written in the code.
244  if (auto *TemplSpec = llvm::dyn_cast<ClassTemplateSpecializationDecl>(D)) {
245  if (TemplSpec->isExplicitInstantiationOrSpecialization())
246  return TemplSpec->isExplicitSpecialization()
247  ? VisitKind::DeclAndChildren
248  : VisitKind::OnlyDecl;
249  return VisitKind::No;
250  }
251  if (auto *TemplSpec = llvm::dyn_cast<VarTemplateSpecializationDecl>(D)) {
252  if (TemplSpec->isExplicitInstantiationOrSpecialization())
253  return TemplSpec->isExplicitSpecialization()
254  ? VisitKind::DeclAndChildren
255  : VisitKind::OnlyDecl;
256  return VisitKind::No;
257  }
258  // For all other cases, visit both the children and the decl.
259  return VisitKind::DeclAndChildren;
260  }
261 
262  ParsedAST &AST;
263 };
264 
265 std::vector<DocumentSymbol> collectDocSymbols(ParsedAST &AST) {
266  return DocumentOutline(AST).build();
267 }
268 } // namespace
269 
270 llvm::Expected<std::vector<DocumentSymbol>> getDocumentSymbols(ParsedAST &AST) {
271  return collectDocSymbols(AST);
272 }
273 
274 } // namespace clangd
275 } // namespace clang
SourceLocation Loc
&#39;#&#39; location in the include directive
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:207
const FunctionDecl * Decl
SignatureQualitySignals Quality
void merge(const CodeCompletionResult &SemaCCResult)
Definition: Quality.cpp:183
llvm::Expected< std::vector< SymbolInformation > > getWorkspaceSymbols(llvm::StringRef Query, int Limit, const SymbolIndex *const Index, llvm::StringRef HintPath)
Searches for the symbols matching Query.
Definition: FindSymbols.cpp:71
SourceLocation nameLocation(const clang::Decl &D, const SourceManager &SM)
Find the source location of the identifier for D.
Definition: AST.cpp:161
Diagnostics must be generated for this snapshot.
Interface for symbol indexes that can be used for searching or matching symbols among a set of symbol...
Definition: Index.h:85
std::pair< StringRef, StringRef > splitQualifiedName(StringRef QName)
Definition: SourceCode.cpp:489
SymbolKind indexSymbolKindToSymbolKind(index::SymbolKind Kind)
Definition: Protocol.cpp:230
llvm::Expected< Location > indexToLSPLocation(const SymbolLocation &Loc, llvm::StringRef TUPath)
Helper function for deriving an LSP Location from an index SymbolLocation.
Definition: FindSymbols.cpp:43
URIForFile uri
The text document&#39;s URI.
Definition: Protocol.h:201
static llvm::StringRef toString(SpecialMemberFunctionsCheck::SpecialMemberFunctionKind K)
Range selectionRange
The range that should be selected and revealed when this symbol is being picked, e.g the name of a function.
Definition: Protocol.h:966
std::vector< CodeCompletionResult > Results
llvm::Expected< Location > symbolToLocation(const Symbol &Sym, llvm::StringRef TUPath)
Helper function for deriving an LSP Location for a Symbol.
Definition: FindSymbols.cpp:63
llvm::StringRef Scope
The containing namespace. e.g. "" (global), "ns::" (top-level namespace).
Definition: Symbol.h:44
ArrayRef< Decl * > getLocalTopLevelDecls()
This function returns top-level decls present in the main file of the AST.
Definition: ParsedAST.cpp:487
Documents should not be synced at all.
Attributes of a symbol that affect how much we like it.
Definition: Quality.h:57
Range range
The range enclosing this symbol not including leading/trailing whitespace but everything else like co...
Definition: Protocol.h:962
llvm::StringRef Name
The name of the symbol (for ContextWords). Must be explicitly assigned.
Definition: Quality.h:89
Represents programming constructs like variables, classes, interfaces etc.
Definition: Protocol.h:945
ASTContext & getASTContext()
Note that the returned ast will not contain decls from the preamble that were not deserialized during...
Definition: ParsedAST.cpp:471
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:36
index::SymbolInfo SymInfo
The symbol information, like symbol kind.
Definition: Symbol.h:40
llvm::Optional< float > Score
SymbolLocation Definition
The location of the symbol&#39;s definition, if one was found.
Definition: Symbol.h:47
Context Ctx
std::vector< SymbolDetails > getSymbolInfo(ParsedAST &AST, Position Pos)
Get info about symbols at Pos.
Definition: XRefs.cpp:1123
enum clang::clangd::SymbolRelevanceSignals::QueryType Query
clang::find_all_symbols::SymbolInfo SymbolInfo
void log(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:62
std::string Path
A typedef to represent a file path.
Definition: Path.h:20
std::string Query
A query string for the fuzzy find.
Definition: Index.h:29
#define dlog(...)
Definition: Logger.h:72
llvm::Optional< float > match(llvm::StringRef Word)
Definition: FuzzyMatch.cpp:92
static URIForFile canonicalize(llvm::StringRef AbsPath, llvm::StringRef TUPath)
Canonicalizes AbsPath via URI.
Definition: Protocol.cpp:33
SymbolLocation CanonicalDeclaration
The location of the preferred declaration of the symbol.
Definition: Symbol.h:56
bool push(value_type &&V)
Definition: Quality.h:160
std::string name
The name of this symbol.
Definition: Protocol.h:947
Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc)
Turn a SourceLocation into a [line, column] pair.
Definition: SourceCode.cpp:220
An information message.
Stores and provides access to parsed AST.
Definition: ParsedAST.h:48
float evaluateSymbolAndRelevance(float SymbolQuality, float SymbolRelevance)
Combine symbol quality and relevance into a single score.
Definition: Quality.cpp:467
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:428
int line
Line position in a document (zero-based).
Definition: Protocol.h:146
int character
Character offset on a line in a document (zero-based).
Definition: Protocol.h:151
bool contains(Position Pos) const
Definition: Protocol.h:190
The class presents a C++ symbol, e.g.
Definition: Symbol.h:36
SymbolKind kind
The kind of this symbol.
Definition: Protocol.h:953
Position Start
The symbol range, using half-open range [Start, End).
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
SymbolKind
A symbol kind.
Definition: Protocol.h:321
llvm::StringRef Name
The unqualified name of the symbol, e.g. "bar" (for ns::bar).
Definition: Symbol.h:42
llvm::Expected< std::vector< DocumentSymbol > > getDocumentSymbols(ParsedAST &AST)
Retrieves the symbols contained in the "main file" section of an AST in the same order that they appe...
bool deprecated
Indicates if this symbol is deprecated.
Definition: Protocol.h:956
static llvm::Expected< std::string > resolve(const URI &U, llvm::StringRef HintPath="")
Resolves the absolute path of U.
Definition: URI.cpp:232
float NameMatch
0-1+ fuzzy-match score for unqualified name. Must be explicitly assigned.
Definition: Quality.h:91
llvm::StringRef pattern() const
Definition: FuzzyMatch.h:82
llvm::StringRef TemplateSpecializationArgs
Argument list in human-readable format, will be displayed to help disambiguate between different spec...
Definition: Symbol.h:69
Attributes of a symbol-query pair that affect how much we like it.
Definition: Quality.h:87
TopN<T> is a lossy container that preserves only the "best" N elements.
Definition: Quality.h:152
const SymbolIndex * Index
Definition: Dexp.cpp:95
Represents information about programming constructs like variables, classes, interfaces etc...
Definition: Protocol.h:976