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

source code of clang-tools-extra/clangd/FindSymbols.cpp