clang-tools-extra/clangd/FindSymbols.cpp

   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 <tuple>
  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 // Returns true if \p Query can be found as a sub-sequence inside \p Scope.
  42 bool approximateScopeMatch(llvm::StringRef Scope, llvm::StringRef Query) {
  43   assert(Scope.empty() || Scope.endswith("::"));
  44   assert(Query.empty() || Query.endswith("::"));
  45   while (!Scope.empty() && !Query.empty()) {
  46     auto Colons = Scope.find("::");
  47     assert(Colons != llvm::StringRef::npos);
  48
  49     llvm::StringRef LeadingSpecifier = Scope.slice(0, Colons + 2);
  50     Scope = Scope.slice(Colons + 2, llvm::StringRef::npos);
  51     Query.consume_front(LeadingSpecifier);
  52   }
  53   return Query.empty();
  54 }
  55
  56 } // namespace
  57
  58 llvm::Expected<Location> indexToLSPLocation(const SymbolLocation &Loc,
  59                                             llvm::StringRef TUPath) {
  60   auto Path = URI::resolve(Loc.FileURI, TUPath);
  61   if (!Path)
  62     return error("Could not resolve path for file '{0}': {1}", Loc.FileURI,
  63                  Path.takeError());
  64   Location L;
  65   L.uri = URIForFile::canonicalize(*Path, TUPath);
  66   Position Start, End;
  67   Start.line = Loc.Start.line();
  68   Start.character = Loc.Start.column();
  69   End.line = Loc.End.line();
  70   End.character = Loc.End.column();
  71   L.range = {Start, End};
  72   return L;
  73 }
  74
  75 llvm::Expected<Location> symbolToLocation(const Symbol &Sym,
  76                                           llvm::StringRef TUPath) {
  77   // Prefer the definition over e.g. a function declaration in a header
  78   return indexToLSPLocation(
  79       Sym.Definition ? Sym.Definition : Sym.CanonicalDeclaration, TUPath);
  80 }
  81
  82 llvm::Expected<std::vector<SymbolInformation>>
  83 getWorkspaceSymbols(llvm::StringRef Query, int Limit,
  84                     const SymbolIndex *const Index, llvm::StringRef HintPath) {
  85   std::vector<SymbolInformation> Result;
  86   if (!Index)
  87     return Result;
  88
  89   // Lookup for qualified names are performed as:
  90   // - Exact namespaces are boosted by the index.
  91   // - Approximate matches are (sub-scope match) included via AnyScope logic.
  92   // - Non-matching namespaces (no sub-scope match) are post-filtered.
  93   auto Names = splitQualifiedName(Query);
  94
  95   FuzzyFindRequest Req;
  96   Req.Query = std::string(Names.second);
  97
  98   // FuzzyFind doesn't want leading :: qualifier.
  99   auto HasLeadingColons = Names.first.consume_front("::");
 100   // Limit the query to specific namespace if it is fully-qualified.
 101   Req.AnyScope = !HasLeadingColons;
 102   // Boost symbols from desired namespace.
 103   if (HasLeadingColons || !Names.first.empty())
 104     Req.Scopes = {std::string(Names.first)};
 105   if (Limit) {
 106     Req.Limit = Limit;
 107     // If we are boosting a specific scope allow more results to be retrieved,
 108     // since some symbols from preferred namespaces might not make the cut.
 109     if (Req.AnyScope && !Req.Scopes.empty())
 110       *Req.Limit *= 5;
 111   }
 112   TopN<ScoredSymbolInfo, ScoredSymbolGreater> Top(
 113       Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max());
 114   FuzzyMatcher Filter(Req.Query);
 115
 116   Index->fuzzyFind(Req, [HintPath, &Top, &Filter, AnyScope = Req.AnyScope,
 117                          ReqScope = Names.first](const Symbol &Sym) {
 118     llvm::StringRef Scope = Sym.Scope;
 119     // Fuzzyfind might return symbols from irrelevant namespaces if query was
 120     // not fully-qualified, drop those.
 121     if (AnyScope && !approximateScopeMatch(Scope, ReqScope))
 122       return;
 123
 124     auto Loc = symbolToLocation(Sym, HintPath);
 125     if (!Loc) {
 126       log("Workspace symbols: {0}", Loc.takeError());
 127       return;
 128     }
 129
 130     SymbolQualitySignals Quality;
 131     Quality.merge(Sym);
 132     SymbolRelevanceSignals Relevance;
 133     Relevance.Name = Sym.Name;
 134     Relevance.Query = SymbolRelevanceSignals::Generic;
 135     // If symbol and request scopes do not match exactly, apply a penalty.
 136     Relevance.InBaseClass = AnyScope && Scope != ReqScope;
 137     if (auto NameMatch = Filter.match(Sym.Name))
 138       Relevance.NameMatch = *NameMatch;
 139     else {
 140       log("Workspace symbol: {0} didn't match query {1}", Sym.Name,
 141           Filter.pattern());
 142       return;
 143     }
 144     Relevance.merge(Sym);
 145     auto QualScore = Quality.evaluateHeuristics();
 146     auto RelScore = Relevance.evaluateHeuristics();
 147     auto Score = evaluateSymbolAndRelevance(QualScore, RelScore);
 148     dlog("FindSymbols: {0}{1} = {2}\n{3}{4}\n", Sym.Scope, Sym.Name, Score,
 149          Quality, Relevance);
 150
 151     SymbolInformation Info;
 152     Info.name = (Sym.Name + Sym.TemplateSpecializationArgs).str();
 153     Info.kind = indexSymbolKindToSymbolKind(Sym.SymInfo.Kind);
 154     Info.location = *Loc;
 155     Scope.consume_back("::");
 156     Info.containerName = Scope.str();
 157
 158     // Exposed score excludes fuzzy-match component, for client-side re-ranking.
 159     Info.score = Relevance.NameMatch > std::numeric_limits<float>::epsilon()
 160                      ? Score / Relevance.NameMatch
 161                      : QualScore;
 162     Top.push({Score, std::move(Info)});
 163   });
 164   for (auto &R : std::move(Top).items())
 165     Result.push_back(std::move(R.second));
 166   return Result;
 167 }
 168
 169 namespace {
 170 std::string getSymbolName(ASTContext &Ctx, const NamedDecl &ND) {
 171   // Print `MyClass(Category)` instead of `Category` and `MyClass()` instead
 172   // of `anonymous`.
 173   if (const auto *Container = dyn_cast<ObjCContainerDecl>(&ND))
 174     return printObjCContainer(*Container);
 175   // Differentiate between class and instance methods: print `-foo` instead of
 176   // `foo` and `+sharedInstance` instead of `sharedInstance`.
 177   if (const auto *Method = dyn_cast<ObjCMethodDecl>(&ND)) {
 178     std::string Name;
 179     llvm::raw_string_ostream OS(Name);
 180
 181     OS << (Method->isInstanceMethod() ? '-' : '+');
 182     Method->getSelector().print(OS);
 183
 184     OS.flush();
 185     return Name;
 186   }
 187   return printName(Ctx, ND);
 188 }
 189
 190 std::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>(&ND)) {
 202     // FIXME: better printing for dependent type
 203     if (isa<CXXConstructorDecl>(VD)) {
 204       std::string ConstructorType = VD->getType().getAsString(P);
 205       // Print constructor type as "(int)" instead of "void (int)".
 206       llvm::StringRef WithoutVoid = ConstructorType;
 207       WithoutVoid.consume_front("void ");
 208       OS << WithoutVoid;
 209     } else if (!isa<CXXDestructorDecl>(VD)) {
 210       VD->getType().print(OS, P);
 211     }
 212   } else if (const auto *TD = dyn_cast<TagDecl>(&ND)) {
 213     OS << TD->getKindName();
 214   } else if (isa<TypedefNameDecl>(&ND)) {
 215     OS << "type alias";
 216   } else if (isa<ConceptDecl>(&ND)) {
 217     OS << "concept";
 218   }
 219   return std::move(OS.str());
 220 }
 221
 222 llvm::Optional<DocumentSymbol> declToSym(ASTContext &Ctx, const NamedDecl &ND) {
 223   auto &SM = Ctx.getSourceManager();
 224
 225   SourceLocation BeginLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getBeginLoc()));
 226   SourceLocation EndLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getEndLoc()));
 227   const auto SymbolRange =
 228       toHalfOpenFileRange(SM, Ctx.getLangOpts(), {BeginLoc, EndLoc});
 229   if (!SymbolRange)
 230     return llvm::None;
 231
 232   index::SymbolInfo SymInfo = index::getSymbolInfo(&ND);
 233   // FIXME: This is not classifying constructors, destructors and operators
 234   // correctly.
 235   SymbolKind SK = indexSymbolKindToSymbolKind(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(NameLoc, SM)) {
 249       // Prefer the spelling loc, but save the expansion loc as a fallback.
 250       FallbackNameLoc = SM.getExpansionLoc(NameLoc);
 251       NameLoc = SM.getSpellingLoc(NameLoc);
 252     } else {
 253       NameLoc = SM.getExpansionLoc(NameLoc);
 254     }
 255   }
 256   auto ComputeSelectionRange = [&](SourceLocation L) -> Range {
 257     Position NameBegin = sourceLocToPosition(SM, L);
 258     Position NameEnd = sourceLocToPosition(
 259         SM, Lexer::getLocForEndOfToken(L, 0, SM, Ctx.getLangOpts()));
 260     return Range{NameBegin, NameEnd};
 261   };
 262
 263   SI.selectionRange = ComputeSelectionRange(NameLoc);
 264   if (!SI.range.contains(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(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.)
 286 class 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(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(Symbol.range.start, Symbol.children.back().range.start);
 307         Symbol.range.end =
 308             std::max(Symbol.range.end, 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                         llvm::Optional<syntax::TokenBuffer::Expansion> Exp) {
 329       if (llvm::is_contained(EnclosingMacroLoc, 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, 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, CharSourceRange::getCharRange(
 346                                             Exp->Spelled.front().location(),
 347                                             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(std::move(Sym));
 364       Child.EnclosingMacroLoc.push_back(Tok.location());
 365       return Child;
 366     }
 367   };
 368
 369 public:
 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(TopLevel, Root);
 377     return std::move(std::move(Root).build().children);
 378   }
 379
 380 private:
 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(D->getLocation(), AST.getSourceManager()))
 386       return;
 387
 388     if (auto *Templ = llvm::dyn_cast<TemplateDecl>(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, Parent);
 400
 401     auto *ND = llvm::cast<NamedDecl>(D);
 402     auto Sym = declToSym(AST.getASTContext(), *ND);
 403     if (!Sym)
 404       return;
 405     SymBuilder &MacroParent = possibleMacroContainer(D->getLocation(), Parent);
 406     SymBuilder &Child = MacroParent.addChild(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(SM.getImmediateExpansionRange(Loc).getBegin());
 443       } else {
 444         // Loc is already in the macro body.
 445         MacroBody = SM.getFileID(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(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().spelledTokenAt(MacroName))
 457         CurParent = &CurParent->inMacro(
 458             *Tok, SM, AST.getTokens().expansionStartingAt(Tok));
 459     }
 460     return *CurParent;
 461   }
 462
 463   void traverseChildren(Decl *D, SymBuilder &Builder) {
 464     auto *Scope = llvm::dyn_cast<DeclContext>(D);
 465     if (!Scope)
 466       return;
 467     for (auto *C : Scope->decls())
 468       traverseDecl(C, Builder);
 469   }
 470
 471   VisitKind shouldVisit(Decl *D) {
 472     if (D->isImplicit())
 473       return VisitKind::No;
 474
 475     if (llvm::isa<LinkageSpecDecl>(D) || llvm::isa<ExportDecl>(D))
 476       return VisitKind::OnlyChildren;
 477
 478     if (!llvm::isa<NamedDecl>(D))
 479       return VisitKind::No;
 480
 481     if (auto *Func = llvm::dyn_cast<FunctionDecl>(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>(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>(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
 521 struct PragmaMarkSymbol {
 522   DocumentSymbol DocSym;
 523   bool IsGroup;
 524 };
 525
 526 /// Merge in `PragmaMarkSymbols`, sorted ascending by range, into the given
 527 /// `DocumentSymbol` tree.
 528 void 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(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(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(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(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(Cur->children, [&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(Cur->children,
 577                                 [&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(make_move_iterator(It),
 582                                make_move_iterator(Cur->children.end()));
 583       Cur->children.erase(It, 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(Cur->children, [&P](const auto &S) -> bool {
 591         return !(P.DocSym.range < S.range);
 592       });
 593       P.DocSym.children.assign(make_move_iterator(It),
 594                                make_move_iterator(Cur->children.end()));
 595       Cur->children.erase(It, 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(P.DocSym.range, Sym.range);
 600     Cur->children.emplace_back(std::move(P.DocSym));
 601   }
 602 }
 603
 604 PragmaMarkSymbol 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("-") &&
 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 {Sym, IsGroup};
 627 }
 628
 629 std::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(PragmaMarks.size());
 638   for (const auto &P : PragmaMarks)
 639     Pragmas.push_back(markToSymbol(P));
 640   Range EntireFile = {
 641       {0, 0},
 642       {std::numeric_limits<int>::max(), std::numeric_limits<int>::max()}};
 643   DocumentSymbol Root;
 644   Root.children = std::move(Syms);
 645   Root.range = EntireFile;
 646   mergePragmas(Root, llvm::makeArrayRef(Pragmas));
 647   return Root.children;
 648 }
 649
 650 } // namespace
 651
 652 llvm::Expected<std::vector<DocumentSymbol>> getDocumentSymbols(ParsedAST &AST) {
 653   return collectDocSymbols(AST);
 654 }
 655
 656 } // namespace clangd
 657 } // namespace clang