| 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/IndexSymbol.h" |
| 19 |
#include "llvm/ADT/ArrayRef.h" |
| 20 |
#include "llvm/ADT/STLExtras.h" |
| 21 |
#include "llvm/ADT/SmallVector.h" |
| 22 |
#include "llvm/ADT/StringRef.h" |
| 23 |
#include <limits> |
| 24 |
#include <optional> |
| 25 |
#include <tuple> |
| 26 |
|
| 27 |
#define DEBUG_TYPE "FindSymbols" |
| 28 |
|
| 29 |
namespace clang { |
| 30 |
namespace clangd { |
| 31 |
|
| 32 |
namespace { |
| 33 |
using ScoredSymbolInfo = std::pair<float, SymbolInformation>; |
| 34 |
struct ScoredSymbolGreater { |
| 35 |
bool operator()(const ScoredSymbolInfo &L, const ScoredSymbolInfo &R) { |
| 36 |
if (L.first != R.first) |
| 37 |
return L.first > R.first; |
| 38 |
return L.second.name < R.second.name; // Earlier name is better. |
| 39 |
} |
| 40 |
}; |
| 41 |
|
| 42 |
// Returns true if \p Query can be found as a sub-sequence inside \p Scope. |
| 43 |
bool approximateScopeMatch(llvm::StringRef Scope, llvm::StringRef Query) { |
| 44 |
assert(Scope.empty() || Scope.endswith("::")); |
| 45 |
assert(Query.empty() || Query.endswith("::")); |
| 46 |
while (!Scope.empty() && !Query.empty()) { |
| 47 |
auto Colons = Scope.find("::"); |
| 48 |
assert(Colons != llvm::StringRef::npos); |
| 49 |
|
| 50 |
llvm::StringRef LeadingSpecifier = Scope.slice(0, Colons + 2); |
| 51 |
Scope = Scope.slice(Colons + 2, llvm::StringRef::npos); |
| 52 |
Query.consume_front(LeadingSpecifier); |
| 53 |
} |
| 54 |
return Query.empty(); |
| 55 |
} |
| 56 |
|
| 57 |
} // namespace |
| 58 |
|
| 59 |
llvm::Expected<Location> indexToLSPLocation(const SymbolLocation &Loc, |
| 60 |
llvm::StringRef TUPath) { |
| 61 |
auto Path = URI::resolve(Loc.FileURI, TUPath); |
| 62 |
if (!Path) |
| 63 |
return error("Could not resolve path for file '{0}': {1}", Loc.FileURI, |
| 64 |
Path.takeError()); |
| 65 |
Location L; |
| 66 |
L.uri = URIForFile::canonicalize(*Path, TUPath); |
| 67 |
Position Start, End; |
| 68 |
Start.line = Loc.Start.line(); |
| 69 |
Start.character = Loc.Start.column(); |
| 70 |
End.line = Loc.End.line(); |
| 71 |
End.character = Loc.End.column(); |
| 72 |
L.range = {Start, End}; |
| 73 |
return L; |
| 74 |
} |
| 75 |
|
| 76 |
llvm::Expected<Location> symbolToLocation(const Symbol &Sym, |
| 77 |
llvm::StringRef TUPath) { |
| 78 |
// Prefer the definition over e.g. a function declaration in a header |
| 79 |
return indexToLSPLocation( |
| 80 |
Sym.Definition ? Sym.Definition : Sym.CanonicalDeclaration, TUPath); |
| 81 |
} |
| 82 |
|
| 83 |
llvm::Expected<std::vector<SymbolInformation>> |
| 84 |
getWorkspaceSymbols(llvm::StringRef Query, int Limit, |
| 85 |
const SymbolIndex *const Index, llvm::StringRef HintPath) { |
| 86 |
std::vector<SymbolInformation> Result; |
| 87 |
if (!Index) |
| 88 |
return Result; |
| 89 |
|
| 90 |
// Lookup for qualified names are performed as: |
| 91 |
// - Exact namespaces are boosted by the index. |
| 92 |
// - Approximate matches are (sub-scope match) included via AnyScope logic. |
| 93 |
// - Non-matching namespaces (no sub-scope match) are post-filtered. |
| 94 |
auto Names = splitQualifiedName(Query); |
| 95 |
|
| 96 |
FuzzyFindRequest Req; |
| 97 |
Req.Query = std::string(Names.second); |
| 98 |
|
| 99 |
// FuzzyFind doesn't want leading :: qualifier. |
| 100 |
auto HasLeadingColons = Names.first.consume_front("::"); |
| 101 |
// Limit the query to specific namespace if it is fully-qualified. |
| 102 |
Req.AnyScope = !HasLeadingColons; |
| 103 |
// Boost symbols from desired namespace. |
| 104 |
if (HasLeadingColons || !Names.first.empty()) |
| 105 |
Req.Scopes = {std::string(Names.first)}; |
| 106 |
if (Limit) { |
| 107 |
Req.Limit = Limit; |
| 108 |
// If we are boosting a specific scope allow more results to be retrieved, |
| 109 |
// since some symbols from preferred namespaces might not make the cut. |
| 110 |
if (Req.AnyScope && !Req.Scopes.empty()) |
| 111 |
*Req.Limit *= 5; |
| 112 |
} |
| 113 |
TopN<ScoredSymbolInfo, ScoredSymbolGreater> Top( |
| 114 |
Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max()); |
| 115 |
FuzzyMatcher Filter(Req.Query); |
| 116 |
|
| 117 |
Index->fuzzyFind(Req, [HintPath, &Top, &Filter, AnyScope = Req.AnyScope, |
| 118 |
ReqScope = Names.first](const Symbol &Sym) { |
| 119 |
llvm::StringRef Scope = Sym.Scope; |
| 120 |
// Fuzzyfind might return symbols from irrelevant namespaces if query was |
| 121 |
// not fully-qualified, drop those. |
| 122 |
if (AnyScope && !approximateScopeMatch(Scope, ReqScope)) |
| 123 |
return; |
| 124 |
|
| 125 |
auto Loc = symbolToLocation(Sym, HintPath); |
| 126 |
if (!Loc) { |
| 127 |
log("Workspace symbols: {0}", Loc.takeError()); |
| 128 |
return; |
| 129 |
} |
| 130 |
|
| 131 |
SymbolQualitySignals Quality; |
| 132 |
Quality.merge(Sym); |
| 133 |
SymbolRelevanceSignals Relevance; |
| 134 |
Relevance.Name = Sym.Name; |
| 135 |
Relevance.Query = SymbolRelevanceSignals::Generic; |
| 136 |
// If symbol and request scopes do not match exactly, apply a penalty. |
| 137 |
Relevance.InBaseClass = AnyScope && Scope != ReqScope; |
| 138 |
if (auto NameMatch = Filter.match(Sym.Name)) |
| 139 |
Relevance.NameMatch = *NameMatch; |
| 140 |
else { |
| 141 |
log("Workspace symbol: {0} didn't match query {1}", Sym.Name, |
| 142 |
Filter.pattern()); |
| 143 |
return; |
| 144 |
} |
| 145 |
Relevance.merge(Sym); |
| 146 |
auto QualScore = Quality.evaluateHeuristics(); |
| 147 |
auto RelScore = Relevance.evaluateHeuristics(); |
| 148 |
auto Score = evaluateSymbolAndRelevance(QualScore, RelScore); |
| 149 |
dlog("FindSymbols: {0}{1} = {2}\n{3}{4}\n", Sym.Scope, Sym.Name, Score, |
| 150 |
Quality, Relevance); |
| 151 |
|
| 152 |
SymbolInformation Info; |
| 153 |
Info.name = (Sym.Name + Sym.TemplateSpecializationArgs).str(); |
| 154 |
Info.kind = indexSymbolKindToSymbolKind(Sym.SymInfo.Kind); |
| 155 |
Info.location = *Loc; |
| 156 |
Scope.consume_back("::"); |
| 157 |
Info.containerName = Scope.str(); |
| 158 |
|
| 159 |
// Exposed score excludes fuzzy-match component, for client-side re-ranking. |
| 160 |
Info.score = Relevance.NameMatch > std::numeric_limits<float>::epsilon() |
| 161 |
? Score / Relevance.NameMatch |
| 162 |
: QualScore; |
| 163 |
Top.push({Score, std::move(Info)}); |
| 164 |
}); |
| 165 |
for (auto &R : std::move(Top).items()) |
| 166 |
Result.push_back(std::move(R.second)); |
| 167 |
return Result; |
| 168 |
} |
| 169 |
|
| 170 |
namespace { |
| 171 |
std::string getSymbolName(ASTContext &Ctx, const NamedDecl &ND) { |
| 172 |
// Print `MyClass(Category)` instead of `Category` and `MyClass()` instead |
| 173 |
// of `anonymous`. |
| 174 |
if (const auto *Container = dyn_cast<ObjCContainerDecl>(&ND)) |
| 175 |
return printObjCContainer(*Container); |
| 176 |
// Differentiate between class and instance methods: print `-foo` instead of |
| 177 |
// `foo` and `+sharedInstance` instead of `sharedInstance`. |
| 178 |
if (const auto *Method = dyn_cast<ObjCMethodDecl>(&ND)) { |
| 179 |
std::string Name; |
| 180 |
llvm::raw_string_ostream OS(Name); |
| 181 |
|
| 182 |
OS << (Method->isInstanceMethod() ? '-' : '+'); |
| 183 |
Method->getSelector().print(OS); |
| 184 |
|
| 185 |
OS.flush(); |
| 186 |
return Name; |
| 187 |
} |
| 188 |
return printName(Ctx, ND); |
| 189 |
} |
| 190 |
|
| 191 |
std::string getSymbolDetail(ASTContext &Ctx, const NamedDecl &ND) { |
| 192 |
PrintingPolicy P(Ctx.getPrintingPolicy()); |
| 193 |
P.SuppressScope = true; |
| 194 |
P.SuppressUnwrittenScope = true; |
| 195 |
P.AnonymousTagLocations = false; |
| 196 |
P.PolishForDeclaration = true; |
| 197 |
std::string Detail; |
| 198 |
llvm::raw_string_ostream OS(Detail); |
| 199 |
if (ND.getDescribedTemplateParams()) { |
| 200 |
OS << "template "; |
| 201 |
} |
| 202 |
if (const auto *VD = dyn_cast<ValueDecl>(&ND)) { |
| 203 |
// FIXME: better printing for dependent type |
| 204 |
if (isa<CXXConstructorDecl>(VD)) { |
| 205 |
std::string ConstructorType = VD->getType().getAsString(P); |
| 206 |
// Print constructor type as "(int)" instead of "void (int)". |
| 207 |
llvm::StringRef WithoutVoid = ConstructorType; |
| 208 |
WithoutVoid.consume_front("void "); |
| 209 |
OS << WithoutVoid; |
| 210 |
} else if (!isa<CXXDestructorDecl>(VD)) { |
| 211 |
VD->getType().print(OS, P); |
| 212 |
} |
| 213 |
} else if (const auto *TD = dyn_cast<TagDecl>(&ND)) { |
| 214 |
OS << TD->getKindName(); |
| 215 |
} else if (isa<TypedefNameDecl>(&ND)) { |
| 216 |
OS << "type alias"; |
| 217 |
} else if (isa<ConceptDecl>(&ND)) { |
| 218 |
OS << "concept"; |
| 219 |
} |
| 220 |
return std::move(OS.str()); |
| 221 |
} |
| 222 |
|
| 223 |
std::optional<DocumentSymbol> declToSym(ASTContext &Ctx, const NamedDecl &ND) { |
| 224 |
auto &SM = Ctx.getSourceManager(); |
| 225 |
|
| 226 |
SourceLocation BeginLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getBeginLoc())); |
| 227 |
SourceLocation EndLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getEndLoc())); |
| 228 |
const auto SymbolRange = |
| 229 |
toHalfOpenFileRange(SM, Ctx.getLangOpts(), {BeginLoc, EndLoc}); |
| 230 |
if (!SymbolRange) |
| 231 |
return std::nullopt; |
| 232 |
|
| 233 |
index::SymbolInfo SymInfo = index::getSymbolInfo(&ND); |
| 234 |
// FIXME: This is not classifying constructors, destructors and operators |
| 235 |
// correctly. |
| 236 |
SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind); |
| 237 |
|
| 238 |
DocumentSymbol SI; |
| 239 |
SI.name = getSymbolName(Ctx, ND); |
| 240 |
SI.kind = SK; |
| 241 |
SI.deprecated = ND.isDeprecated(); |
| 242 |
SI.range = Range{sourceLocToPosition(SM, SymbolRange->getBegin()), |
| 243 |
sourceLocToPosition(SM, SymbolRange->getEnd())}; |
| 244 |
SI.detail = getSymbolDetail(Ctx, ND); |
| 245 |
|
| 246 |
SourceLocation NameLoc = ND.getLocation(); |
| 247 |
SourceLocation FallbackNameLoc; |
| 248 |
if (NameLoc.isMacroID()) { |
| 249 |
if (isSpelledInSource(NameLoc, SM)) { |
| 250 |
// Prefer the spelling loc, but save the expansion loc as a fallback. |
| 251 |
FallbackNameLoc = SM.getExpansionLoc(NameLoc); |
| 252 |
NameLoc = SM.getSpellingLoc(NameLoc); |
| 253 |
} else { |
| 254 |
NameLoc = SM.getExpansionLoc(NameLoc); |
| 255 |
} |
| 256 |
} |
| 257 |
auto ComputeSelectionRange = [&](SourceLocation L) -> Range { |
| 258 |
Position NameBegin = sourceLocToPosition(SM, L); |
| 259 |
Position NameEnd = sourceLocToPosition( |
| 260 |
SM, Lexer::getLocForEndOfToken(L, 0, SM, Ctx.getLangOpts())); |
| 261 |
return Range{NameBegin, NameEnd}; |
| 262 |
}; |
| 263 |
|
| 264 |
SI.selectionRange = ComputeSelectionRange(NameLoc); |
| 265 |
if (!SI.range.contains(SI.selectionRange) && FallbackNameLoc.isValid()) { |
| 266 |
// 'selectionRange' must be contained in 'range'. In cases where clang |
| 267 |
// reports unrelated ranges, we first try falling back to the expansion |
| 268 |
// loc for the selection range. |
| 269 |
SI.selectionRange = ComputeSelectionRange(FallbackNameLoc); |
| 270 |
} |
| 271 |
if (!SI.range.contains(SI.selectionRange)) { |
| 272 |
// If the containment relationship still doesn't hold, throw away |
| 273 |
// 'range' and use 'selectionRange' for both. |
| 274 |
SI.range = SI.selectionRange; |
| 275 |
} |
| 276 |
return SI; |
| 277 |
} |
| 278 |
|
| 279 |
/// A helper class to build an outline for the parse AST. It traverses the AST |
| 280 |
/// directly instead of using RecursiveASTVisitor (RAV) for three main reasons: |
| 281 |
/// - there is no way to keep RAV from traversing subtrees we are not |
| 282 |
/// interested in. E.g. not traversing function locals or implicit template |
| 283 |
/// instantiations. |
| 284 |
/// - it's easier to combine results of recursive passes, |
| 285 |
/// - visiting decls is actually simple, so we don't hit the complicated |
| 286 |
/// cases that RAV mostly helps with (types, expressions, etc.) |
| 287 |
class DocumentOutline { |
| 288 |
// A DocumentSymbol we're constructing. |
| 289 |
// We use this instead of DocumentSymbol directly so that we can keep track |
| 290 |
// of the nodes we insert for macros. |
| 291 |
class SymBuilder { |
| 292 |
std::vector<SymBuilder> Children; |
| 293 |
DocumentSymbol Symbol; // Symbol.children is empty, use Children instead. |
| 294 |
// Macro expansions that this node or its parents are associated with. |
| 295 |
// (Thus we will never create further children for these expansions). |
| 296 |
llvm::SmallVector<SourceLocation> EnclosingMacroLoc; |
| 297 |
|
| 298 |
public: |
| 299 |
DocumentSymbol build() && { |
| 300 |
for (SymBuilder &C : Children) { |
| 301 |
Symbol.children.push_back(std::move(C).build()); |
| 302 |
// Expand range to ensure children nest properly, which editors expect. |
| 303 |
// This can fix some edge-cases in the AST, but is vital for macros. |
| 304 |
// A macro expansion "contains" AST node if it covers the node's primary |
| 305 |
// location, but it may not span the node's whole range. |
| 306 |
Symbol.range.start = |
| 307 |
std::min(Symbol.range.start, Symbol.children.back().range.start); |
| 308 |
Symbol.range.end = |
| 309 |
std::max(Symbol.range.end, Symbol.children.back().range.end); |
| 310 |
} |
| 311 |
return std::move(Symbol); |
| 312 |
} |
| 313 |
|
| 314 |
// Add a symbol as a child of the current one. |
| 315 |
SymBuilder &addChild(DocumentSymbol S) { |
| 316 |
Children.emplace_back(); |
| 317 |
Children.back().EnclosingMacroLoc = EnclosingMacroLoc; |
| 318 |
Children.back().Symbol = std::move(S); |
| 319 |
return Children.back(); |
| 320 |
} |
| 321 |
|
| 322 |
// Get an appropriate container for children of this symbol that were |
| 323 |
// expanded from a macro (whose spelled name is Tok). |
| 324 |
// |
| 325 |
// This may return: |
| 326 |
// - a macro symbol child of this (either new or previously created) |
| 327 |
// - this scope itself, if it *is* the macro symbol or is nested within it |
| 328 |
SymBuilder &inMacro(const syntax::Token &Tok, const SourceManager &SM, |
| 329 |
std::optional<syntax::TokenBuffer::Expansion> Exp) { |
| 330 |
if (llvm::is_contained(EnclosingMacroLoc, Tok.location())) |
| 331 |
return *this; |
| 332 |
// If there's an existing child for this macro, we expect it to be last. |
| 333 |
if (!Children.empty() && !Children.back().EnclosingMacroLoc.empty() && |
| 334 |
Children.back().EnclosingMacroLoc.back() == Tok.location()) |
| 335 |
return Children.back(); |
| 336 |
|
| 337 |
DocumentSymbol Sym; |
| 338 |
Sym.name = Tok.text(SM).str(); |
| 339 |
Sym.kind = SymbolKind::Null; // There's no suitable kind! |
| 340 |
Sym.range = Sym.selectionRange = |
| 341 |
halfOpenToRange(SM, Tok.range(SM).toCharRange(SM)); |
| 342 |
|
| 343 |
// FIXME: Exp is currently unavailable for nested expansions. |
| 344 |
if (Exp) { |
| 345 |
// Full range covers the macro args. |
| 346 |
Sym.range = halfOpenToRange(SM, CharSourceRange::getCharRange( |
| 347 |
Exp->Spelled.front().location(), |
| 348 |
Exp->Spelled.back().endLocation())); |
| 349 |
// Show macro args as detail. |
| 350 |
llvm::raw_string_ostream OS(Sym.detail); |
| 351 |
const syntax::Token *Prev = nullptr; |
| 352 |
for (const auto &Tok : Exp->Spelled.drop_front()) { |
| 353 |
// Don't dump arbitrarily long macro args. |
| 354 |
if (OS.tell() > 80) { |
| 355 |
OS << " ...)"; |
| 356 |
break; |
| 357 |
} |
| 358 |
if (Prev && Prev->endLocation() != Tok.location()) |
| 359 |
OS << ' '; |
| 360 |
OS << Tok.text(SM); |
| 361 |
Prev = &Tok; |
| 362 |
} |
| 363 |
} |
| 364 |
SymBuilder &Child = addChild(std::move(Sym)); |
| 365 |
Child.EnclosingMacroLoc.push_back(Tok.location()); |
| 366 |
return Child; |
| 367 |
} |
| 368 |
}; |
| 369 |
|
| 370 |
public: |
| 371 |
DocumentOutline(ParsedAST &AST) : AST(AST) {} |
| 372 |
|
| 373 |
/// Builds the document outline for the generated AST. |
| 374 |
std::vector<DocumentSymbol> build() { |
| 375 |
SymBuilder Root; |
| 376 |
for (auto &TopLevel : AST.getLocalTopLevelDecls()) |
| 377 |
traverseDecl(TopLevel, Root); |
| 378 |
return std::move(std::move(Root).build().children); |
| 379 |
} |
| 380 |
|
| 381 |
private: |
| 382 |
enum class VisitKind { No, OnlyDecl, OnlyChildren, DeclAndChildren }; |
| 383 |
|
| 384 |
void traverseDecl(Decl *D, SymBuilder &Parent) { |
| 385 |
// Skip symbols which do not originate from the main file. |
| 386 |
if (!isInsideMainFile(D->getLocation(), AST.getSourceManager())) |
| 387 |
return; |
| 388 |
|
| 389 |
if (auto *Templ = llvm::dyn_cast<TemplateDecl>(D)) { |
| 390 |
// TemplatedDecl might be null, e.g. concepts. |
| 391 |
if (auto *TD = Templ->getTemplatedDecl()) |
| 392 |
D = TD; |
| 393 |
} |
| 394 |
|
| 395 |
VisitKind Visit = shouldVisit(D); |
| 396 |
if (Visit == VisitKind::No) |
| 397 |
return; |
| 398 |
|
| 399 |
if (Visit == VisitKind::OnlyChildren) |
| 400 |
return traverseChildren(D, Parent); |
| 401 |
|
| 402 |
auto *ND = llvm::cast<NamedDecl>(D); |
| 403 |
auto Sym = declToSym(AST.getASTContext(), *ND); |
| 404 |
if (!Sym) |
| 405 |
return; |
| 406 |
SymBuilder &MacroParent = possibleMacroContainer(D->getLocation(), Parent); |
| 407 |
SymBuilder &Child = MacroParent.addChild(std::move(*Sym)); |
| 408 |
|
| 409 |
if (Visit == VisitKind::OnlyDecl) |
| 410 |
return; |
| 411 |
|
| 412 |
assert(Visit == VisitKind::DeclAndChildren && "Unexpected VisitKind"); |
| 413 |
traverseChildren(ND, Child); |
| 414 |
} |
| 415 |
|
| 416 |
// Determines where a decl should appear in the DocumentSymbol hierarchy. |
| 417 |
// |
| 418 |
// This is usually a direct child of the relevant AST parent. |
| 419 |
// But we may also insert nodes for macros. Given: |
| 420 |
// #define DECLARE_INT(V) int v; |
| 421 |
// namespace a { DECLARE_INT(x) } |
| 422 |
// We produce: |
| 423 |
// Namespace a |
| 424 |
// Macro DECLARE_INT(x) |
| 425 |
// Variable x |
| 426 |
// |
| 427 |
// In the absence of macros, this method simply returns Parent. |
| 428 |
// Otherwise it may return a macro expansion node instead. |
| 429 |
// Each macro only has at most one node in the hierarchy, even if it expands |
| 430 |
// to multiple decls. |
| 431 |
SymBuilder &possibleMacroContainer(SourceLocation TargetLoc, |
| 432 |
SymBuilder &Parent) { |
| 433 |
const auto &SM = AST.getSourceManager(); |
| 434 |
// Look at the path of macro-callers from the token to the main file. |
| 435 |
// Note that along these paths we see the "outer" macro calls first. |
| 436 |
SymBuilder *CurParent = &Parent; |
| 437 |
for (SourceLocation Loc = TargetLoc; Loc.isMacroID(); |
| 438 |
Loc = SM.getImmediateMacroCallerLoc(Loc)) { |
| 439 |
// Find the virtual macro body that our token is being substituted into. |
| 440 |
FileID MacroBody; |
| 441 |
if (SM.isMacroArgExpansion(Loc)) { |
| 442 |
// Loc is part of a macro arg being substituted into a macro body. |
| 443 |
MacroBody = SM.getFileID(SM.getImmediateExpansionRange(Loc).getBegin()); |
| 444 |
} else { |
| 445 |
// Loc is already in the macro body. |
| 446 |
MacroBody = SM.getFileID(Loc); |
| 447 |
} |
| 448 |
// The macro body is being substituted for a macro expansion, whose |
| 449 |
// first token is the name of the macro. |
| 450 |
SourceLocation MacroName = |
| 451 |
SM.getSLocEntry(MacroBody).getExpansion().getExpansionLocStart(); |
| 452 |
// Only include the macro expansion in the outline if it was written |
| 453 |
// directly in the main file, rather than expanded from another macro. |
| 454 |
if (!MacroName.isValid() || !MacroName.isFileID()) |
| 455 |
continue; |
| 456 |
// All conditions satisfied, add the macro. |
| 457 |
if (auto *Tok = AST.getTokens().spelledTokenAt(MacroName)) |
| 458 |
CurParent = &CurParent->inMacro( |
| 459 |
*Tok, SM, AST.getTokens().expansionStartingAt(Tok)); |
| 460 |
} |
| 461 |
return *CurParent; |
| 462 |
} |
| 463 |
|
| 464 |
void traverseChildren(Decl *D, SymBuilder &Builder) { |
| 465 |
auto *Scope = llvm::dyn_cast<DeclContext>(D); |
| 466 |
if (!Scope) |
| 467 |
return; |
| 468 |
for (auto *C : Scope->decls()) |
| 469 |
traverseDecl(C, Builder); |
| 470 |
} |
| 471 |
|
| 472 |
VisitKind shouldVisit(Decl *D) { |
| 473 |
if (D->isImplicit()) |
| 474 |
return VisitKind::No; |
| 475 |
|
| 476 |
if (llvm::isa<LinkageSpecDecl>(D) || llvm::isa<ExportDecl>(D)) |
| 477 |
return VisitKind::OnlyChildren; |
| 478 |
|
| 479 |
if (!llvm::isa<NamedDecl>(D)) |
| 480 |
return VisitKind::No; |
| 481 |
|
| 482 |
if (auto *Func = llvm::dyn_cast<FunctionDecl>(D)) { |
| 483 |
// Some functions are implicit template instantiations, those should be |
| 484 |
// ignored. |
| 485 |
if (auto *Info = Func->getTemplateSpecializationInfo()) { |
| 486 |
if (!Info->isExplicitInstantiationOrSpecialization()) |
| 487 |
return VisitKind::No; |
| 488 |
} |
| 489 |
// Only visit the function itself, do not visit the children (i.e. |
| 490 |
// function parameters, etc.) |
| 491 |
return VisitKind::OnlyDecl; |
| 492 |
} |
| 493 |
// Handle template instantiations. We have three cases to consider: |
| 494 |
// - explicit instantiations, e.g. 'template class std::vector<int>;' |
| 495 |
// Visit the decl itself (it's present in the code), but not the |
| 496 |
// children. |
| 497 |
// - implicit instantiations, i.e. not written by the user. |
| 498 |
// Do not visit at all, they are not present in the code. |
| 499 |
// - explicit specialization, e.g. 'template <> class vector<bool> {};' |
| 500 |
// Visit both the decl and its children, both are written in the code. |
| 501 |
if (auto *TemplSpec = llvm::dyn_cast<ClassTemplateSpecializationDecl>(D)) { |
| 502 |
if (TemplSpec->isExplicitInstantiationOrSpecialization()) |
| 503 |
return TemplSpec->isExplicitSpecialization() |
| 504 |
? VisitKind::DeclAndChildren |
| 505 |
: VisitKind::OnlyDecl; |
| 506 |
return VisitKind::No; |
| 507 |
} |
| 508 |
if (auto *TemplSpec = llvm::dyn_cast<VarTemplateSpecializationDecl>(D)) { |
| 509 |
if (TemplSpec->isExplicitInstantiationOrSpecialization()) |
| 510 |
return TemplSpec->isExplicitSpecialization() |
| 511 |
? VisitKind::DeclAndChildren |
| 512 |
: VisitKind::OnlyDecl; |
| 513 |
return VisitKind::No; |
| 514 |
} |
| 515 |
// For all other cases, visit both the children and the decl. |
| 516 |
return VisitKind::DeclAndChildren; |
| 517 |
} |
| 518 |
|
| 519 |
ParsedAST &AST; |
| 520 |
}; |
| 521 |
|
| 522 |
struct PragmaMarkSymbol { |
| 523 |
DocumentSymbol DocSym; |
| 524 |
bool IsGroup; |
| 525 |
}; |
| 526 |
|
| 527 |
/// Merge in `PragmaMarkSymbols`, sorted ascending by range, into the given |
| 528 |
/// `DocumentSymbol` tree. |
| 529 |
void mergePragmas(DocumentSymbol &Root, ArrayRef<PragmaMarkSymbol> Pragmas) { |
| 530 |
while (!Pragmas.empty()) { |
| 531 |
// We'll figure out where the Pragmas.front() should go. |
| 532 |
PragmaMarkSymbol P = std::move(Pragmas.front()); |
| 533 |
Pragmas = Pragmas.drop_front(); |
| 534 |
DocumentSymbol *Cur = &Root; |
| 535 |
while (Cur->range.contains(P.DocSym.range)) { |
| 536 |
bool Swapped = false; |
| 537 |
for (auto &C : Cur->children) { |
| 538 |
// We assume at most 1 child can contain the pragma (as pragmas are on |
| 539 |
// a single line, and children have disjoint ranges). |
| 540 |
if (C.range.contains(P.DocSym.range)) { |
| 541 |
Cur = &C; |
| 542 |
Swapped = true; |
| 543 |
break; |
| 544 |
} |
| 545 |
} |
| 546 |
// Cur is the parent of P since none of the children contain P. |
| 547 |
if (!Swapped) |
| 548 |
break; |
| 549 |
} |
| 550 |
// Pragma isn't a group so we can just insert it and we are done. |
| 551 |
if (!P.IsGroup) { |
| 552 |
Cur->children.emplace_back(std::move(P.DocSym)); |
| 553 |
continue; |
| 554 |
} |
| 555 |
// Pragma is a group, so we need to figure out where it terminates: |
| 556 |
// - If the next Pragma is not contained in Cur, P owns all of its |
| 557 |
// parent's children which occur after P. |
| 558 |
// - If the next pragma is contained in Cur but actually belongs to one |
| 559 |
// of the parent's children, we temporarily skip over it and look at |
| 560 |
// the next pragma to decide where we end. |
| 561 |
// - Otherwise nest all of its parent's children which occur after P but |
| 562 |
// before the next pragma. |
| 563 |
bool TerminatedByNextPragma = false; |
| 564 |
for (auto &NextPragma : Pragmas) { |
| 565 |
// If we hit a pragma outside of Cur, the rest will be outside as well. |
| 566 |
if (!Cur->range.contains(NextPragma.DocSym.range)) |
| 567 |
break; |
| 568 |
|
| 569 |
// NextPragma cannot terminate P if it is nested inside a child, look for |
| 570 |
// the next one. |
| 571 |
if (llvm::any_of(Cur->children, [&NextPragma](const auto &Child) { |
| 572 |
return Child.range.contains(NextPragma.DocSym.range); |
| 573 |
})) |
| 574 |
continue; |
| 575 |
|
| 576 |
// Pragma owns all the children between P and NextPragma |
| 577 |
auto It = llvm::partition(Cur->children, |
| 578 |
[&P, &NextPragma](const auto &S) -> bool { |
| 579 |
return !(P.DocSym.range < S.range && |
| 580 |
S.range < NextPragma.DocSym.range); |
| 581 |
}); |
| 582 |
P.DocSym.children.assign(make_move_iterator(It), |
| 583 |
make_move_iterator(Cur->children.end())); |
| 584 |
Cur->children.erase(It, Cur->children.end()); |
| 585 |
TerminatedByNextPragma = true; |
| 586 |
break; |
| 587 |
} |
| 588 |
if (!TerminatedByNextPragma) { |
| 589 |
// P is terminated by the end of current symbol, hence it owns all the |
| 590 |
// children after P. |
| 591 |
auto It = llvm::partition(Cur->children, [&P](const auto &S) -> bool { |
| 592 |
return !(P.DocSym.range < S.range); |
| 593 |
}); |
| 594 |
P.DocSym.children.assign(make_move_iterator(It), |
| 595 |
make_move_iterator(Cur->children.end())); |
| 596 |
Cur->children.erase(It, Cur->children.end()); |
| 597 |
} |
| 598 |
// Update the range for P to cover children and append to Cur. |
| 599 |
for (DocumentSymbol &Sym : P.DocSym.children) |
| 600 |
unionRanges(P.DocSym.range, Sym.range); |
| 601 |
Cur->children.emplace_back(std::move(P.DocSym)); |
| 602 |
} |
| 603 |
} |
| 604 |
|
| 605 |
PragmaMarkSymbol markToSymbol(const PragmaMark &P) { |
| 606 |
StringRef Name = StringRef(P.Trivia).trim(); |
| 607 |
bool IsGroup = false; |
| 608 |
// "-\s+<group name>" or "<name>" after an initial trim. The former is |
| 609 |
// considered a group, the latter just a mark. Like Xcode, we don't consider |
| 610 |
// `-Foo` to be a group (space(s) after the `-` is required). |
| 611 |
// |
| 612 |
// We need to include a name here, otherwise editors won't properly render the |
| 613 |
// symbol. |
| 614 |
StringRef MaybeGroupName = Name; |
| 615 |
if (MaybeGroupName.consume_front("-") && |
| 616 |
(MaybeGroupName.ltrim() != MaybeGroupName || MaybeGroupName.empty())) { |
| 617 |
Name = MaybeGroupName.empty() ? "(unnamed group)" : MaybeGroupName.ltrim(); |
| 618 |
IsGroup = true; |
| 619 |
} else if (Name.empty()) { |
| 620 |
Name = "(unnamed mark)"; |
| 621 |
} |
| 622 |
DocumentSymbol Sym; |
| 623 |
Sym.name = Name.str(); |
| 624 |
Sym.kind = SymbolKind::File; |
| 625 |
Sym.range = P.Rng; |
| 626 |
Sym.selectionRange = P.Rng; |
| 627 |
return {Sym, IsGroup}; |
| 628 |
} |
| 629 |
|
| 630 |
std::vector<DocumentSymbol> collectDocSymbols(ParsedAST &AST) { |
| 631 |
std::vector<DocumentSymbol> Syms = DocumentOutline(AST).build(); |
| 632 |
|
| 633 |
const auto &PragmaMarks = AST.getMarks(); |
| 634 |
if (PragmaMarks.empty()) |
| 635 |
return Syms; |
| 636 |
|
| 637 |
std::vector<PragmaMarkSymbol> Pragmas; |
| 638 |
Pragmas.reserve(PragmaMarks.size()); |
| 639 |
for (const auto &P : PragmaMarks) |
| 640 |
Pragmas.push_back(markToSymbol(P)); |
| 641 |
Range EntireFile = { |
| 642 |
{0, 0}, |
| 643 |
{std::numeric_limits<int>::max(), std::numeric_limits<int>::max()}}; |
| 644 |
DocumentSymbol Root; |
| 645 |
Root.children = std::move(Syms); |
| 646 |
Root.range = EntireFile; |
| 647 |
mergePragmas(Root, llvm::ArrayRef(Pragmas)); |
| 648 |
return Root.children; |
| 649 |
} |
| 650 |
|
| 651 |
} // namespace |
| 652 |
|
| 653 |
llvm::Expected<std::vector<DocumentSymbol>> getDocumentSymbols(ParsedAST &AST) { |
| 654 |
return collectDocSymbols(AST); |
| 655 |
} |
| 656 |
|
| 657 |
} // namespace clangd |
| 658 |
} // namespace clang |