clang-tools  10.0.0svn
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 "Logger.h"
13 #include "ParsedAST.h"
14 #include "Quality.h"
15 #include "SourceCode.h"
16 #include "index/Index.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/Support/FormatVariadic.h"
22 #include "llvm/Support/Path.h"
23 #include "llvm/Support/ScopedPrinter.h"
24 
25 #define DEBUG_TYPE "FindSymbols"
26 
27 namespace clang {
28 namespace clangd {
29 
30 namespace {
31 using ScoredSymbolInfo = std::pair<float, SymbolInformation>;
32 struct ScoredSymbolGreater {
33  bool operator()(const ScoredSymbolInfo &L, const ScoredSymbolInfo &R) {
34  if (L.first != R.first)
35  return L.first > R.first;
36  return L.second.name < R.second.name; // Earlier name is better.
37  }
38 };
39 
40 } // namespace
41 
42 llvm::Expected<Location> symbolToLocation(const Symbol &Sym,
43  llvm::StringRef HintPath) {
44  // Prefer the definition over e.g. a function declaration in a header
45  auto &CD = Sym.Definition ? Sym.Definition : Sym.CanonicalDeclaration;
46  auto Path = URI::resolve(CD.FileURI, HintPath);
47  if (!Path) {
48  return llvm::make_error<llvm::StringError>(
49  formatv("Could not resolve path for symbol '{0}': {1}",
50  Sym.Name, llvm::toString(Path.takeError())),
51  llvm::inconvertibleErrorCode());
52  }
53  Location L;
54  // Use HintPath as TUPath since there is no TU associated with this
55  // request.
56  L.uri = URIForFile::canonicalize(*Path, HintPath);
57  Position Start, End;
58  Start.line = CD.Start.line();
59  Start.character = CD.Start.column();
60  End.line = CD.End.line();
61  End.character = CD.End.column();
62  L.range = {Start, End};
63  return L;
64 }
65 
66 llvm::Expected<std::vector<SymbolInformation>>
67 getWorkspaceSymbols(llvm::StringRef Query, int Limit,
68  const SymbolIndex *const Index, llvm::StringRef HintPath) {
69  std::vector<SymbolInformation> Result;
70  if (Query.empty() || !Index)
71  return Result;
72 
73  auto Names = splitQualifiedName(Query);
74 
75  FuzzyFindRequest Req;
76  Req.Query = Names.second;
77 
78  // FuzzyFind doesn't want leading :: qualifier
79  bool IsGlobalQuery = Names.first.consume_front("::");
80  // Restrict results to the scope in the query string if present (global or
81  // not).
82  if (IsGlobalQuery || !Names.first.empty())
83  Req.Scopes = {Names.first};
84  else
85  Req.AnyScope = true;
86  if (Limit)
87  Req.Limit = Limit;
88  TopN<ScoredSymbolInfo, ScoredSymbolGreater> Top(
89  Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max());
90  FuzzyMatcher Filter(Req.Query);
91  Index->fuzzyFind(Req, [HintPath, &Top, &Filter](const Symbol &Sym) {
92  auto Loc = symbolToLocation(Sym, HintPath);
93  if (!Loc) {
94  log("Workspace symbols: {0}", Loc.takeError());
95  return;
96  }
97 
98  SymbolKind SK = indexSymbolKindToSymbolKind(Sym.SymInfo.Kind);
99  std::string Scope = Sym.Scope;
100  llvm::StringRef ScopeRef = Scope;
101  ScopeRef.consume_back("::");
102  SymbolInformation Info = {(Sym.Name + Sym.TemplateSpecializationArgs).str(),
103  SK, *Loc, ScopeRef};
104 
105  SymbolQualitySignals Quality;
106  Quality.merge(Sym);
107  SymbolRelevanceSignals Relevance;
108  Relevance.Name = Sym.Name;
109  Relevance.Query = SymbolRelevanceSignals::Generic;
110  if (auto NameMatch = Filter.match(Sym.Name))
111  Relevance.NameMatch = *NameMatch;
112  else {
113  log("Workspace symbol: {0} didn't match query {1}", Sym.Name,
114  Filter.pattern());
115  return;
116  }
117  Relevance.merge(Sym);
118  auto Score =
119  evaluateSymbolAndRelevance(Quality.evaluate(), Relevance.evaluate());
120  dlog("FindSymbols: {0}{1} = {2}\n{3}{4}\n", Sym.Scope, Sym.Name, Score,
121  Quality, Relevance);
122 
123  Top.push({Score, std::move(Info)});
124  });
125  for (auto &R : std::move(Top).items())
126  Result.push_back(std::move(R.second));
127  return Result;
128 }
129 
130 namespace {
131 llvm::Optional<DocumentSymbol> declToSym(ASTContext &Ctx, const NamedDecl &ND) {
132  auto &SM = Ctx.getSourceManager();
133 
134  SourceLocation NameLoc = spellingLocIfSpelled(findName(&ND), SM);
135  // getFileLoc is a good choice for us, but we also need to make sure
136  // sourceLocToPosition won't switch files, so we call getSpellingLoc on top of
137  // that to make sure it does not switch files.
138  // FIXME: sourceLocToPosition should not switch files!
139  SourceLocation BeginLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getBeginLoc()));
140  SourceLocation EndLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getEndLoc()));
141  if (NameLoc.isInvalid() || BeginLoc.isInvalid() || EndLoc.isInvalid())
142  return llvm::None;
143 
144  if (!SM.isWrittenInMainFile(NameLoc) || !SM.isWrittenInMainFile(BeginLoc) ||
145  !SM.isWrittenInMainFile(EndLoc))
146  return llvm::None;
147 
148  Position NameBegin = sourceLocToPosition(SM, NameLoc);
149  Position NameEnd = sourceLocToPosition(
150  SM, Lexer::getLocForEndOfToken(NameLoc, 0, SM, Ctx.getLangOpts()));
151 
153  // FIXME: this is not classifying constructors, destructors and operators
154  // correctly (they're all "methods").
155  SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind);
156 
157  DocumentSymbol SI;
158  SI.name = printName(Ctx, ND);
159  SI.kind = SK;
160  SI.deprecated = ND.isDeprecated();
161  SI.range =
162  Range{sourceLocToPosition(SM, BeginLoc), sourceLocToPosition(SM, EndLoc)};
163  SI.selectionRange = Range{NameBegin, NameEnd};
164  if (!SI.range.contains(SI.selectionRange)) {
165  // 'selectionRange' must be contained in 'range', so in cases where clang
166  // reports unrelated ranges we need to reconcile somehow.
167  SI.range = SI.selectionRange;
168  }
169  return SI;
170 }
171 
172 /// A helper class to build an outline for the parse AST. It traverses the AST
173 /// directly instead of using RecursiveASTVisitor (RAV) for three main reasons:
174 /// - there is no way to keep RAV from traversing subtrees we are not
175 /// interested in. E.g. not traversing function locals or implicit template
176 /// instantiations.
177 /// - it's easier to combine results of recursive passes,
178 /// - visiting decls is actually simple, so we don't hit the complicated
179 /// cases that RAV mostly helps with (types, expressions, etc.)
180 class DocumentOutline {
181 public:
182  DocumentOutline(ParsedAST &AST) : AST(AST) {}
183 
184  /// Builds the document outline for the generated AST.
185  std::vector<DocumentSymbol> build() {
186  std::vector<DocumentSymbol> Results;
187  for (auto &TopLevel : AST.getLocalTopLevelDecls())
188  traverseDecl(TopLevel, Results);
189  return Results;
190  }
191 
192 private:
193  enum class VisitKind { No, OnlyDecl, DeclAndChildren };
194 
195  void traverseDecl(Decl *D, std::vector<DocumentSymbol> &Results) {
196  if (auto *Templ = llvm::dyn_cast<TemplateDecl>(D))
197  D = Templ->getTemplatedDecl();
198  auto *ND = llvm::dyn_cast<NamedDecl>(D);
199  if (!ND)
200  return;
201  VisitKind Visit = shouldVisit(ND);
202  if (Visit == VisitKind::No)
203  return;
204  llvm::Optional<DocumentSymbol> Sym = declToSym(AST.getASTContext(), *ND);
205  if (!Sym)
206  return;
207  if (Visit == VisitKind::DeclAndChildren)
208  traverseChildren(D, Sym->children);
209  Results.push_back(std::move(*Sym));
210  }
211 
212  void traverseChildren(Decl *D, std::vector<DocumentSymbol> &Results) {
213  auto *Scope = llvm::dyn_cast<DeclContext>(D);
214  if (!Scope)
215  return;
216  for (auto *C : Scope->decls())
217  traverseDecl(C, Results);
218  }
219 
220  VisitKind shouldVisit(NamedDecl *D) {
221  if (D->isImplicit())
222  return VisitKind::No;
223 
224  if (auto Func = llvm::dyn_cast<FunctionDecl>(D)) {
225  // Some functions are implicit template instantiations, those should be
226  // ignored.
227  if (auto *Info = Func->getTemplateSpecializationInfo()) {
228  if (!Info->isExplicitInstantiationOrSpecialization())
229  return VisitKind::No;
230  }
231  // Only visit the function itself, do not visit the children (i.e.
232  // function parameters, etc.)
233  return VisitKind::OnlyDecl;
234  }
235  // Handle template instantiations. We have three cases to consider:
236  // - explicit instantiations, e.g. 'template class std::vector<int>;'
237  // Visit the decl itself (it's present in the code), but not the
238  // children.
239  // - implicit instantiations, i.e. not written by the user.
240  // Do not visit at all, they are not present in the code.
241  // - explicit specialization, e.g. 'template <> class vector<bool> {};'
242  // Visit both the decl and its children, both are written in the code.
243  if (auto *TemplSpec = llvm::dyn_cast<ClassTemplateSpecializationDecl>(D)) {
244  if (TemplSpec->isExplicitInstantiationOrSpecialization())
245  return TemplSpec->isExplicitSpecialization()
246  ? VisitKind::DeclAndChildren
247  : VisitKind::OnlyDecl;
248  return VisitKind::No;
249  }
250  if (auto *TemplSpec = llvm::dyn_cast<VarTemplateSpecializationDecl>(D)) {
251  if (TemplSpec->isExplicitInstantiationOrSpecialization())
252  return TemplSpec->isExplicitSpecialization()
253  ? VisitKind::DeclAndChildren
254  : VisitKind::OnlyDecl;
255  return VisitKind::No;
256  }
257  // For all other cases, visit both the children and the decl.
258  return VisitKind::DeclAndChildren;
259  }
260 
261  ParsedAST &AST;
262 };
263 
264 std::vector<DocumentSymbol> collectDocSymbols(ParsedAST &AST) {
265  return DocumentOutline(AST).build();
266 }
267 } // namespace
268 
269 llvm::Expected<std::vector<DocumentSymbol>> getDocumentSymbols(ParsedAST &AST) {
270  return collectDocSymbols(AST);
271 }
272 
273 } // namespace clangd
274 } // namespace clang
SourceLocation Loc
&#39;#&#39; location in the include directive
int Limit
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:126
SourceLocation findName(const clang::Decl *D)
Find the identifier source location of the given D.
Definition: AST.cpp:83
SignatureQualitySignals Quality
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:67
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:602
SymbolKind indexSymbolKindToSymbolKind(index::SymbolKind Kind)
Definition: Protocol.cpp:216
URIForFile uri
The text document&#39;s URI.
Definition: Protocol.h:184
static llvm::StringRef toString(SpecialMemberFunctionsCheck::SpecialMemberFunctionKind K)
std::vector< CodeCompletionResult > Results
Documents should not be synced at all.
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
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:983
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
static URIForFile canonicalize(llvm::StringRef AbsPath, llvm::StringRef TUPath)
Canonicalizes AbsPath via URI.
Definition: Protocol.cpp:32
SymbolKind
The SymbolInfo Type.
Definition: SymbolInfo.h:30
SymbolLocation CanonicalDeclaration
The location of the preferred declaration of the symbol.
Definition: Symbol.h:56
const Decl * D
Definition: XRefs.cpp:849
llvm::Expected< Location > symbolToLocation(const Symbol &Sym, llvm::StringRef HintPath)
Helper function for deriving an LSP Location for a Symbol.
Definition: FindSymbols.cpp:42
Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc)
Turn a SourceLocation into a [line, column] pair.
Definition: SourceCode.cpp:194
An information message.
Stores and provides access to parsed AST.
Definition: ParsedAST.h:46
float evaluateSymbolAndRelevance(float SymbolQuality, float SymbolRelevance)
Combine symbol quality and relevance into a single score.
Definition: Quality.cpp:463
int line
Line position in a document (zero-based).
Definition: Protocol.h:129
int character
Character offset on a line in a document (zero-based).
Definition: Protocol.h:134
The class presents a C++ symbol, e.g.
Definition: Symbol.h:36
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
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...
CharSourceRange Range
SourceRange for the file name.
SourceLocation spellingLocIfSpelled(SourceLocation Loc, const SourceManager &SM)
Returns the spelling location of the token at Loc if isSpelledInSource, otherwise its expansion locat...
Definition: SourceCode.cpp:221
static llvm::Expected< std::string > resolve(const URI &U, llvm::StringRef HintPath="")
Resolves the absolute path of U.
Definition: URI.cpp:233
const SymbolIndex * Index
Definition: Dexp.cpp:84