[clangd] Implementation of textDocument/documentSymbol

[malaperle]

Summary

An AST-based approach is used to retrieve the document symbols rather than an
in-memory index query. The index is not an ideal fit to achieve this because of
the file-centric query being done here whereas the index is suited for
project-wide queries. Document symbols also includes more symbols and need to
keep the order as seen in the file.

Signed-off-by: Marc-Andre Laperle <[e-mail]>

[malaperle]

unittests/clangd/FindSymbolsTests.cpp

40

I updated the other tests to use this in https://reviews.llvm.org/D47847

[malaperle]

Rebased.

[malaperle]

I found some issues while testing, I will investigate before review.

[sammccall]

This looks great! Would like to get your thoughts on reusing/not reusing SymbolCollector.

clangd/FindSymbols.cpp

181

I guess the alternative here is to use SymbolCollector and then convert Symbol->SymbolInformation (which we should already have for workspace/symbol).

I also guess there's some divergence in behavior, which is why you went this route :-)
Mostly in filtering? (I'd think that for e.g. printing, we'd want to be consistent)

Do you think it's worth adding enough customization to SymbolCollector to make it usable here? Even if it was making shouldFilterDecl a std::function, there'd be some value in unifying the rest. WDYT?

clangd/SourceCode.cpp

194

the common case when tryGetRealPathName() is empty seems to be when it's a file that was part of the preamble we're reusing.
Does this fallback tend to give the same answer in that case? (If so, great! I know some other places we should reuse this function!)

unittests/clangd/FindSymbolsTests.cpp

447

in a perfect world, I think the template definitions might be printed Tmpl<T>, Tmpl<int>. Not sure about Tmpl::x vs Tmpl<T>::x though. WDYT?

(Not necessarily worth doing this patch, keep it simple)

[sammccall]

clangd/SourceCode.cpp

194

Sorry, I just noticed this is only being moved. Please disregard (and thangs for moving it somewhere common).
Note that D48687 modifies this function, let's make sure not to lose anything in the merge.

[malaperle]

clangd/FindSymbols.cpp

181

I put a bit of the justification in the summary, perhaps you missed it or maybe did you think it was not enough of a justification?

An AST-based approach is used to retrieve the document symbols rather than an
in-memory index query. The index is not an ideal fit to achieve this because of
the file-centric query being done here whereas the index is suited for
project-wide queries. Document symbols also includes more symbols and need to
keep the order as seen in the file.

It's not a clear cut decision but I felt that there was more diverging parts than common and that it would be detrimental to SymbolCollector in terms of added complexity.
Differences:

• We need a different way to filter (as you suggested)
• Don't need anything about completion
• Don't need to distinguish declaration vs definition or canonical declaration
• Don't need a map<USR, Symbol>, we just need them in same order as they appear and SymbolCollector should be free to store them in whichever order for purposes of proving a project-wide collection of symbols
• Don't want to track references
• DocumentSymbols needs symbols in main files

Common things:

• Both need to generate Position/Uri from a SourceLocation. But they can both call sourceLocToPosition.
• Both need to generate a symbol name from Decl&. But they can both call AST.h's printQualifiedName (I fixed this in a new version).
• Both use/extend a IndexDataConsumer. Not worth sharing the same code path just to not have to create a class definition IMO.

Let me know if that makes sense to you, otherwise I can try to make another version that uses SymbolCollector.

unittests/clangd/FindSymbolsTests.cpp

447

I'm thinking Tmpl<class T>, Tmpl<int>, so that we can more easily distinguish between a primary and specialization, especially in partial specializations and when the generic type might not be just a single letter. And Tmpl<class T>::x. Maybe this is too much :)

[malaperle]

Fix handling of externs, definition vs declaration and call more common code.

[malaperle]

Rebased.

[sammccall]

Sorry, I thought I'd accepted this already!

clangd/ClangdServer.cpp

471

hover -> documentSymbols

clangd/FindSymbols.cpp

188

OS is unused

203

nit: rename to shouldIncludeSymbol or something? "filter" is slightly ambiguous, and a negation. (We've made this change in SymbolCollector recently)

229

nit: isWrittenInMainFile(NameLoc)

234

remove

256

nit: for readability, could we declare a local SymbolInformation above, fill in the fields by name, and then move it into Symbols?

a) it's easier to see that the right values go into the right slots, b), it's easier to search (find references!) for how fields are populated.

268

applying the filter is fine, but note that SystemSymbolFilter only applies to included symbols in -isystem headers (I only just noticed that myself). So the comment is a little misleading, I would drop it.

[sammccall]

(Reasoning for not using SymbolCollector totally makes sense, thanks for the breakdown!)

[malaperle]

Address comments.

[malaperle]

Thanks a lot for the great comments (as always)!

clangd/ClangdLSPServer.h

private:
   void onDocumentDidOpen(DidOpenTextDocumentParams &Params) override;
   void onDocumentDidChange(DidChangeTextDocumentParams &Params) override;
   void onDocumentDidClose(DidCloseTextDocumentParams &Params) override;
   void
   onDocumentOnTypeFormatting(DocumentOnTypeFormattingParams &Params) override;
   void
   onDocumentRangeFormatting(DocumentRangeFormattingParams &Params) override;
   void onDocumentFormatting(DocumentFormattingParams &Params) override;
+  void onDocumentSymbol(DocumentSymbolParams &Params) override;
   void onCodeAction(CodeActionParams &Params) override;
   void onCompletion(TextDocumentPositionParams &Params) override;
   void onSignatureHelp(TextDocumentPositionParams &Params) override;
   void onGoToDefinition(TextDocumentPositionParams &Params) override;
   void onSwitchSourceHeader(TextDocumentIdentifier &Params) override;
   void onDocumentHighlight(TextDocumentPositionParams &Params) override;
   void onFileEvent(DidChangeWatchedFilesParams &Params) override;
   void onCommand(ExecuteCommandParams &Params) override;

clangd/ClangdLSPServer.cpp

reply(json::obj{
             {"signatureHelpProvider",
              json::obj{
                  {"triggerCharacters", {"(", ","}},
              }},
             {"definitionProvider", true},
             {"documentHighlightProvider", true},
             {"hoverProvider", true},
             {"renameProvider", true},
+            {"documentSymbolProvider", true},
             {"workspaceSymbolProvider", true},
             {"executeCommandProvider",
              json::obj{
                  {"commands", {ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND}},
              }},
         }}}});
 }
 
void ClangdLSPServer::onDocumentFormatting(DocumentFormattingParams &Params) {
   auto ReplacementsOrError = Server.formatFile(*Code, File);
   if (ReplacementsOrError)
     reply(json::ary(replacementsToEdits(*Code, ReplacementsOrError.get())));
   else
     replyError(ErrorCode::UnknownErrorCode,
                llvm::toString(ReplacementsOrError.takeError()));
 }
 
+void ClangdLSPServer::onDocumentSymbol(DocumentSymbolParams &Params) {
+  Server.documentSymbols(
+      Params.textDocument.uri.file(),
+      [this](llvm::Expected<std::vector<SymbolInformation>> Items) {
+        if (!Items)
+          return replyError(ErrorCode::InvalidParams,
+                            llvm::toString(Items.takeError()));
+        for (auto &Sym : *Items)
+          Sym.kind = adjustKindToCapability(Sym.kind, SupportedSymbolKinds);
+        reply(json::ary(*Items));
+      });
+}
+
 void ClangdLSPServer::onCodeAction(CodeActionParams &Params) {
   // We provide a code action for each diagnostic at the requested location
   // which has FixIts available.
   auto Code = DraftMgr.getDraft(Params.textDocument.uri.file());
   if (!Code)
     return replyError(ErrorCode::InvalidParams,
                       "onCodeAction called for non-added file");
 

clangd/ClangdServer.h

public:
   /// Get code hover for a given position.
   void findHover(PathRef File, Position Pos,
                  Callback<llvm::Optional<Hover>> CB);
 
   /// Retrieve the top symbols from the workspace matching a query.
   void workspaceSymbols(StringRef Query, int Limit,
                         Callback<std::vector<SymbolInformation>> CB);
 
+  /// Retrieve the symbols within the specified file.
+  void documentSymbols(StringRef File,
+                       Callback<std::vector<SymbolInformation>> CB);
+
   /// Run formatting for \p Rng inside \p File with content \p Code.
   llvm::Expected<tooling::Replacements> formatRange(StringRef Code,
                                                     PathRef File, Range Rng);
 
   /// Run formatting for the whole \p File with content \p Code.
   llvm::Expected<tooling::Replacements> formatFile(StringRef Code,
                                                    PathRef File);
 

clangd/ClangdServer.cpp

 }
 
 void ClangdServer::workspaceSymbols(
     StringRef Query, int Limit, Callback<std::vector<SymbolInformation>> CB) {
   CB(clangd::getWorkspaceSymbols(Query, Limit, Index,
                                  RootPath ? *RootPath : ""));
 }
 
+void ClangdServer::documentSymbols(
+    StringRef File, Callback<std::vector<SymbolInformation>> CB) {
+  auto Action = [](Callback<std::vector<SymbolInformation>> CB,
+                   llvm::Expected<InputsAndAST> InpAST) {
+    if (!InpAST)
+      return CB(InpAST.takeError());
+    CB(clangd::getDocumentSymbols(InpAST->AST));
+  };
+  WorkScheduler.runWithAST("Hover", File, Bind(Action, std::move(CB)));
+}
+
 std::vector<std::pair<Path, std::size_t>>
 ClangdServer::getUsedBytesPerFile() const {
   return WorkScheduler.getUsedBytesPerFile();
 }
 
 LLVM_NODISCARD bool
 ClangdServer::blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds) {
   return WorkScheduler.blockUntilIdle(timeoutSeconds(TimeoutSeconds));
 }

clangd/FindSymbols.h

 //===----------------------------------------------------------------------===//
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_FINDSYMBOLS_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_FINDSYMBOLS_H
 
 #include "Protocol.h"
 #include "llvm/ADT/StringRef.h"
 
 namespace clang {
+class ParsedAST;
 namespace clangd {
 class SymbolIndex;
 
 /// Searches for the symbols matching \p Query. The syntax of \p Query can be
 /// the non-qualified name or fully qualified of a symbol. For example, "vector"
 /// will match the symbol std::vector and "std::vector" would also match it.
 /// Direct children of scopes (namepaces, etc) can be listed with a trailing
 /// "::". For example, "std::" will list all children of the std namespace and
 /// "::" alone will list all children of the global namespace.
 /// \p Limit limits the number of results returned (0 means no limit).
 /// \p HintPath This is used when resolving URIs. If empty, URI resolution can
 /// fail if a hint path is required for the scheme of a specific URI.
 llvm::Expected<std::vector<SymbolInformation>>
 getWorkspaceSymbols(llvm::StringRef Query, int Limit,
                     const SymbolIndex *const Index, llvm::StringRef HintPath);
 
+/// Retrieves the symbols contained in the "main file" section of an AST in the
+/// same order that they appear.
+llvm::Expected<std::vector<SymbolInformation>>
+getDocumentSymbols(ParsedAST &AST);
+
 } // namespace clangd
 } // namespace clang
 
 #endif

clangd/FindSymbols.cpp

 //===--- FindSymbols.cpp ------------------------------------*- C++-*------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 #include "FindSymbols.h"
 
-#include "Logger.h"
+#include "AST.h"
+#include "ClangdUnit.h"
 #include "FuzzyMatch.h"
-#include "SourceCode.h"
+#include "Logger.h"
 #include "Quality.h"
+#include "SourceCode.h"
 #include "index/Index.h"
+#include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexSymbol.h"
+#include "clang/Index/IndexingAction.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 
 #define DEBUG_TYPE "FindSymbols"
 
 namespace clang {
 namespace clangd {
 
Index->fuzzyFind(Req, [HintPath, &Top, &Filter](const Symbol &Sym) {
 
     Top.push({Score, std::move(Info)});
   });
   for (auto &R : std::move(Top).items())
     Result.push_back(std::move(R.second));
   return Result;
 }
 
+namespace {
+/// Finds document symbols in the main file of the AST.
+class DocumentSymbolsConsumer : public index::IndexDataConsumer {
+  ASTContext *
+  std::vector<SymbolInformation> Symbols;
+  // We are always list document for the same file, so cache the value.
+  llvm::Optional<URIForFile> MainFileUri;
+
+public:
+  DocumentSymbolsConsumer(raw_ostream &OS, ASTContext &AST) : AST(AST) {}
+  std::vector<SymbolInformation> takeSymbols() { return std::move(Symbols); }
+
+  void initialize(ASTContext &Ctx) override {
+    // Compute the absolute path of the main file which we will use for all
+    // results.
+    const SourceManager &SM = AST.getSourceManager();
+    const FileEntry *F = SM.getFileEntryForID(SM.getMainFileID());
+    if (!F)
+      return;
+    auto FilePath = getAbsoluteFilePath(F, SM);
+    if (FilePath)
+      MainFileUri = URIForFile(*FilePath);
+  }
+
+  bool shouldFilterDecl(const NamedDecl *ND) {
+    if (!ND || ND->isImplicit())
+      return true;
+    // Skip anonymous declarations, e.g (anonymous enum/class/struct).
+    if (ND->getDeclName().isEmpty())
+      return true;
+    return false;
+  }
+
+  bool
+  handleDeclOccurence(const Decl *, index::SymbolRoleSet Roles,
+                      ArrayRef<index::SymbolRelation> Relations,
+                      SourceLocation Loc,
+                      index::IndexDataConsumer::ASTNodeInfo ASTNode) override {
+    assert(ASTNode.OrigD);
+    // No point in continuing the index consumer if we could not get the
+    // absolute path of the main file.
+    if (!MainFileUri)
+      return false;
+    // We only want declarations and definitions, i.e. no references.
+    if (!(Roles & static_cast<unsigned>(index::SymbolRole::Declaration) ||
+          Roles & static_cast<unsigned>(index::SymbolRole::Definition)))
+      return true;
+    SourceLocation NameLoc = findNameLoc(ASTNode.OrigD);
+    const SourceManager &SourceMgr = AST.getSourceManager();
+    // We should be only be looking at "local" decls in the main file.
+    if (SourceMgr.getMainFileID() != SourceMgr.getFileID(NameLoc)) {
+      // Even thought we are visiting only local (non-preamble) decls,
+      // we can get here when in the presense of "extern" decls.
+      return true;
+    }
+    // assert(SourceMgr.getMainFileID() == SourceMgr.getFileID(NameLoc));
+    const NamedDecl *ND = llvm::dyn_cast<NamedDecl>(ASTNode.OrigD);
+    if (shouldFilterDecl(ND))
+      return true;
+
+    SourceLocation EndLoc =
+        Lexer::getLocForEndOfToken(NameLoc, 0, SourceMgr, AST.getLangOpts());
+    Position Begin = sourceLocToPosition(SourceMgr, NameLoc);
+    Position End = sourceLocToPosition(SourceMgr, EndLoc);
+    Range R = {Begin, End};
+    Location L;
+    L.uri = *MainFileUri;
+    L.range = R;
+
+    std::string QName = printQualifiedName(*ND);
+    StringRef Scope, Name;
+    std::tie(Scope, Name) = splitQualifiedName(QName);
+    Scope.consume_back("::");
+
+    index::SymbolInfo SymInfo = index::getSymbolInfo(ND);
+    SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind);
+
+    Symbols.push_back({Name, SK, L, Scope});
+    return true;
+  }
+};
+} // namespace
+
+llvm::Expected<std::vector<SymbolInformation>>
+getDocumentSymbols(ParsedAST &AST) {
+  DocumentSymbolsConsumer DocumentSymbolsCons(llvm::errs(),
+                                              AST.getASTContext());
+
+  index::IndexingOptions IndexOpts;
+  // We don't need references, only declarations so that is makes a nice
+  // outline of the document.
+  IndexOpts.SystemSymbolFilter =
+      index::IndexingOptions::SystemSymbolFilterKind::DeclarationsOnly;
+  IndexOpts.IndexFunctionLocals = false;
+  indexTopLevelDecls(AST.getASTContext(), AST.getLocalTopLevelDecls(),
+                     DocumentSymbolsCons, IndexOpts);
+
+  return DocumentSymbolsCons.takeSymbols();
+}
+
 } // namespace clangd
 } // namespace clang

clangd/Protocol.h

struct DocumentFormattingParams {
   /// The document to format.
   TextDocumentIdentifier textDocument;
 
   /// The format options
   FormattingOptions options;
 };
 bool fromJSON(const json::Expr &, DocumentFormattingParams &);
 
+struct DocumentSymbolParams {
+  // The text document to find symbols in.
+  TextDocumentIdentifier textDocument;
+};
+bool fromJSON(const json::Expr &, DocumentSymbolParams &);
+
 struct Diagnostic {
   /// The range at which the message applies.
   Range range;
 
   /// The diagnostic's severity. Can be omitted. If omitted it is up to the
   /// client to interpret diagnostics as error, warning, info or hint.
   int severity = 0;
 

clangd/Protocol.cpp

 }
 
 bool fromJSON(const json::Expr &Params, DocumentFormattingParams &R) {
   json::ObjectMapper O(Params);
   return O && O.map("textDocument", R.textDocument) &&
          O.map("options", R.options);
 }
 
+bool fromJSON(const json::Expr &Params, DocumentSymbolParams &R) {
+  json::ObjectMapper O(Params);
+  return O && O.map("textDocument", R.textDocument);
+}
+
 bool fromJSON(const json::Expr &Params, Diagnostic &R) {
   json::ObjectMapper O(Params);
   if (!O || !O.map("range", R.range) || !O.map("message", R.message))
     return false;
   O.map("severity", R.severity);
   return true;
 }
 

clangd/ProtocolHandlers.h

public:
 
   virtual void onInitialize(InitializeParams &Params) = 0;
   virtual void onShutdown(ShutdownParams &Params) = 0;
   virtual void onExit(ExitParams &Params) = 0;
   virtual void onDocumentDidOpen(DidOpenTextDocumentParams &Params) = 0;
   virtual void onDocumentDidChange(DidChangeTextDocumentParams &Params) = 0;
   virtual void onDocumentDidClose(DidCloseTextDocumentParams &Params) = 0;
   virtual void onDocumentFormatting(DocumentFormattingParams &Params) = 0;
+  virtual void onDocumentSymbol(DocumentSymbolParams &Params) = 0;
   virtual void
   onDocumentOnTypeFormatting(DocumentOnTypeFormattingParams &Params) = 0;
   virtual void
   onDocumentRangeFormatting(DocumentRangeFormattingParams &Params) = 0;
   virtual void onCodeAction(CodeActionParams &Params) = 0;
   virtual void onCompletion(TextDocumentPositionParams &Params) = 0;
   virtual void onSignatureHelp(TextDocumentPositionParams &Params) = 0;
   virtual void onGoToDefinition(TextDocumentPositionParams &Params) = 0;

clangd/ProtocolHandlers.cpp

void clangd::registerCallbackHandlers(JSONRPCDispatcher &Dispatcher,
   Register("textDocument/codeAction", &ProtocolCallbacks::onCodeAction);
   Register("textDocument/completion", &ProtocolCallbacks::onCompletion);
   Register("textDocument/signatureHelp", &ProtocolCallbacks::onSignatureHelp);
   Register("textDocument/definition", &ProtocolCallbacks::onGoToDefinition);
   Register("textDocument/switchSourceHeader",
            &ProtocolCallbacks::onSwitchSourceHeader);
   Register("textDocument/rename", &ProtocolCallbacks::onRename);
   Register("textDocument/hover", &ProtocolCallbacks::onHover);
+  Register("textDocument/documentSymbol", &ProtocolCallbacks::onDocumentSymbol);
   Register("workspace/didChangeWatchedFiles", &ProtocolCallbacks::onFileEvent);
   Register("workspace/executeCommand", &ProtocolCallbacks::onCommand);
   Register("textDocument/documentHighlight",
            &ProtocolCallbacks::onDocumentHighlight);
   Register("workspace/didChangeConfiguration",
            &ProtocolCallbacks::onChangeConfiguration);
   Register("workspace/symbol", &ProtocolCallbacks::onWorkspaceSymbol);
 }

clangd/SourceCode.h

 std::pair<llvm::StringRef, llvm::StringRef>
 splitQualifiedName(llvm::StringRef QName);
 
 TextEdit replacementToEdit(StringRef Code, const tooling::Replacement &R);
 
 std::vector<TextEdit> replacementsToEdits(StringRef Code,
                                           const tooling::Replacements &Repls);
 
+/// Get the absolute file path of a given file entry.
+llvm::Optional<std::string> getAbsoluteFilePath(const FileEntry *F,
+                                                const SourceManager &SourceMgr);
 } // namespace clangd
 } // namespace clang
 #endif

clangd/SourceCode.cpp

 //===--- SourceCode.h - Manipulating source code as strings -----*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 #include "SourceCode.h"
 
+#include "Logger.h"
+#include "clang/AST/ASTContext.h"
 #include "clang/Basic/SourceManager.h"
+#include "clang/Lex/Lexer.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
+#include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 
 // Here be dragons. LSP positions use columns measured in *UTF-16 code units*!
 // Clangd uses UTF-8 and byte-offsets internally, so conversion is nontrivial.
 

 std::vector<TextEdit> replacementsToEdits(StringRef Code,
                                           const tooling::Replacements &Repls) {
   std::vector<TextEdit> Edits;
   for (const auto &R : Repls)
     Edits.push_back(replacementToEdit(Code, R));
   return Edits;
 }
 
+llvm::Optional<std::string>
+getAbsoluteFilePath(const FileEntry *F, const SourceManager &SourceMgr) {
+  SmallString<64> FilePath = F->tryGetRealPathName();
+  if (FilePath.empty())
+    FilePath = F->getName();
+  if (!llvm::sys::path::is_absolute(FilePath)) {
+    if (!SourceMgr.getFileManager().makeAbsolutePath(FilePath)) {
+      log("Could not turn relative path to absolute: " + FilePath);
+      return llvm::None;
+    }
+  }
+  return FilePath.str().str();
+}
+
 } // namespace clangd
 } // namespace clang

clangd/XRefs.cpp

IndexOpts.SystemSymbolFilter =
       index::IndexingOptions::SystemSymbolFilterKind::All;
   IndexOpts.IndexFunctionLocals = true;
   indexTopLevelDecls(AST.getASTContext(), AST.getLocalTopLevelDecls(),
                      DeclMacrosFinder, IndexOpts);
 
   return {DeclMacrosFinder.takeDecls(), DeclMacrosFinder.takeMacroInfos()};
 }
 
-llvm::Optional<std::string>
-getAbsoluteFilePath(const FileEntry *F, const SourceManager &SourceMgr) {
-  SmallString<64> FilePath = F->tryGetRealPathName();
-  if (FilePath.empty())
-    FilePath = F->getName();
-  if (!llvm::sys::path::is_absolute(FilePath)) {
-    if (!SourceMgr.getFileManager().makeAbsolutePath(FilePath)) {
-      log("Could not turn relative path to absolute: " + FilePath);
-      return llvm::None;
-    }
-  }
-  return FilePath.str().str();
-}
-
 llvm::Optional<Location>
 makeLocation(ParsedAST &AST, const SourceRange &ValSourceRange) {
   const SourceManager &SourceMgr = AST.getASTContext().getSourceManager();
   const LangOptions &LangOpts = AST.getASTContext().getLangOpts();
   SourceLocation LocStart = ValSourceRange.getBegin();
 
   const FileEntry *F =
       SourceMgr.getFileEntryForID(SourceMgr.getFileID(LocStart));

test/clangd/initialize-params-invalid.test

 # CHECK-NEXT:      "definitionProvider": true,
 # CHECK-NEXT:      "documentFormattingProvider": true,
 # CHECK-NEXT:      "documentHighlightProvider": true,
 # CHECK-NEXT:      "documentOnTypeFormattingProvider": {
 # CHECK-NEXT:        "firstTriggerCharacter": "}",
 # CHECK-NEXT:        "moreTriggerCharacter": []
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "documentRangeFormattingProvider": true,
+# CHECK-NEXT:      "documentSymbolProvider": true,
 # CHECK-NEXT:      "executeCommandProvider": {
 # CHECK-NEXT:        "commands": [
 # CHECK-NEXT:          "clangd.applyFix"
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "hoverProvider": true,
 # CHECK-NEXT:      "renameProvider": true,
 # CHECK-NEXT:      "signatureHelpProvider": {

test/clangd/initialize-params.test

 # CHECK-NEXT:      "definitionProvider": true,
 # CHECK-NEXT:      "documentFormattingProvider": true,
 # CHECK-NEXT:      "documentHighlightProvider": true,
 # CHECK-NEXT:      "documentOnTypeFormattingProvider": {
 # CHECK-NEXT:        "firstTriggerCharacter": "}",
 # CHECK-NEXT:        "moreTriggerCharacter": []
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "documentRangeFormattingProvider": true,
+# CHECK-NEXT:      "documentSymbolProvider": true,
 # CHECK-NEXT:      "executeCommandProvider": {
 # CHECK-NEXT:        "commands": [
 # CHECK-NEXT:          "clangd.applyFix"
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "hoverProvider": true,
 # CHECK-NEXT:      "renameProvider": true,
 # CHECK-NEXT:      "signatureHelpProvider": {

test/clangd/symbols.test

 # CHECK-NEXT:          },
 # CHECK-NEXT:          "uri": "file://{{.*}}/sstream.h"
 # CHECK-NEXT:        },
 # CHECK-NEXT:        "name": "basic_ostringstream"
 # CHECK-NEXT:      }
 # CHECK-NEXT:    ]
 # CHECK-NEXT:}
 ---
+{"jsonrpc":"2.0","id":2,"method":"textDocument/documentSymbol","params":{"textDocument":{"uri":"test:///main.cpp"}}}
+#      CHECK:  "id": 2,
+# CHECK-NEXT:  "jsonrpc": "2.0",
+# CHECK-NEXT:    "result": [
+# CHECK-NEXT:      {
+# CHECK-NEXT:        "containerName": "",
+# CHECK-NEXT:        "kind": 12,
+# CHECK-NEXT:        "location": {
+# CHECK-NEXT:          "range": {
+# CHECK-NEXT:            "end": {
+# CHECK-NEXT:              "character": {{.*}},
+# CHECK-NEXT:              "line": {{.*}}
+# CHECK-NEXT:            },
+# CHECK-NEXT:            "start": {
+# CHECK-NEXT:              "character": {{.*}},
+# CHECK-NEXT:              "line": {{.*}}
+# CHECK-NEXT:            }
+# CHECK-NEXT:          },
+# CHECK-NEXT:          "uri": "file://{{.*}}/main.cpp"
+# CHECK-NEXT:        },
+# CHECK-NEXT:        "name": "foo"
+# CHECK-NEXT:      }
+# CHECK-NEXT:      {
+# CHECK-NEXT:        "containerName": "",
+# CHECK-NEXT:        "kind": 12,
+# CHECK-NEXT:        "location": {
+# CHECK-NEXT:          "range": {
+# CHECK-NEXT:            "end": {
+# CHECK-NEXT:              "character": {{.*}},
+# CHECK-NEXT:              "line": {{.*}}
+# CHECK-NEXT:            },
+# CHECK-NEXT:            "start": {
+# CHECK-NEXT:              "character": {{.*}},
+# CHECK-NEXT:              "line": {{.*}}
+# CHECK-NEXT:            }
+# CHECK-NEXT:          },
+# CHECK-NEXT:          "uri": "file://{{.*}}/main.cpp"
+# CHECK-NEXT:        },
+# CHECK-NEXT:        "name": "main"
+# CHECK-NEXT:      }
+# CHECK-NEXT:    ]
+# CHECK-NEXT:}
+---
+{"jsonrpc":"2.0","id":3,"method":"textDocument/documentSymbol","params":{"textDocument":{"uri":"test:///foo.cpp"}}}
+#      CHECK:  "error": {
+# CHECK-NEXT:    "code": -32602,
+# CHECK-NEXT:    "message": "trying to get AST for non-added document"
+# CHECK-NEXT:  },
+# CHECK-NEXT:  "id": 3,
+# CHECK-NEXT:  "jsonrpc": "2.0"
+---
 {"jsonrpc":"2.0","id":3,"method":"shutdown"}
 ---
 {"jsonrpc":"2.0","method":"exit"}

unittests/clangd/FindSymbolsTests.cpp

 namespace clang {
 namespace clangd {
 
 namespace {
 
 using ::testing::AllOf;
 using ::testing::AnyOf;
 using ::testing::ElementsAre;
+using ::testing::ElementsAreArray;
 using ::testing::IsEmpty;
 using ::testing::UnorderedElementsAre;
 
 class IgnoreDiagnostics : public DiagnosticsConsumer {
   void onDiagnosticsReady(PathRef File,
                           std::vector<Diag> Diagnostics) override {}
 };
 
 // GMock helpers for matching SymbolInfos items.
 MATCHER_P(QName, Name, "") {
   if (arg.containerName.empty())
     return arg.name == Name;
   return (arg.containerName + "::" + arg.name) == Name;
 }
 MATCHER_P(WithKind, Kind, "") { return arg.kind == Kind; }
+MATCHER_P(SymRange, Range, "") { return arg.location.range == Range; }
 
 ClangdServer::Options optsForTests() {
   auto ServerOpts = ClangdServer::optsForTest();
   ServerOpts.BuildDynamicSymbolIndex = true;
   ServerOpts.URISchemes = {"unittest", "file"};
   return ServerOpts;
 }
 
EXPECT_THAT(getSymbols("foo"),
               UnorderedElementsAre(
                   AllOf(QName("foo"), WithKind(SymbolKind::Variable)),
                   AllOf(QName("foo2"), WithKind(SymbolKind::Variable))));
 
   Limit = 1;
   EXPECT_THAT(getSymbols("foo"), ElementsAre(QName("foo")));
 }
 
+namespace {
+class DocumentSymbolsTest : public ::testing::Test {
+public:
+  DocumentSymbolsTest()
+      : Server(CDB, FSProvider, DiagConsumer, optsForTests()) {}
+
+protected:
+  MockFSProvider FSProvider;
+  MockCompilationDatabase CDB;
+  IgnoreDiagnostics DiagConsumer;
+  ClangdServer Server;
+
+  std::vector<SymbolInformation> getSymbols(PathRef File) {
+    EXPECT_TRUE(Server.blockUntilIdleForTest()) << "Waiting for preamble";
+    auto SymbolInfos = runDocumentSymbols(Server, File);
+    EXPECT_TRUE(bool(SymbolInfos)) << "documentSymbols returned an error";
+    return *SymbolInfos;
+  }
+
+  void addFile(StringRef FilePath, StringRef Contents) {
+    FSProvider.Files[FilePath] = Contents;
+    Server.addDocument(FilePath, Contents);
+  }
+};
+} // namespace
+
+TEST_F(DocumentSymbolsTest, BasicSymbols) {
+  std::string FilePath = testPath("foo.cpp");
+  Annotations Main(R"(
+      class Foo;
+      class Foo {
+        Foo() {}
+        Foo(int a) {}
+        void $decl[[f]]();
+        friend void f1();
+        friend class Friend;
+        Foo& operator=(const Foo&);
+        ~Foo();
+        class Nested {
+        void f();
+        };
+      };
+      class Friend {
+      };
+
+      void f1();
+      inline void f2() {}
+      static const int KInt = 2;
+      const char* kStr = "123";
+
+      void f1() {}
+
+      namespace foo {
+      // Type alias
+      typedef int int32;
+      using int32_t = int32;
+
+      // Variable
+      int v1;
+
+      // Namespace
+      namespace bar {
+      int v2;
+      }
+      // Namespace alias
+      namespace baz = bar;
+
+      // FIXME: using declaration is not supported as the IndexAction will ignore
+      // implicit declarations (the implicit using shadow declaration) by default,
+      // and there is no way to customize this behavior at the moment.
+      using bar::v2;
+      } // namespace foo
+    )");
+
+  addFile(FilePath, Main.code());
+  EXPECT_THAT(getSymbols(FilePath),
+              ElementsAreArray(
+                  {AllOf(QName("Foo"), WithKind(SymbolKind::Class)),
+                   AllOf(QName("Foo"), WithKind(SymbolKind::Class)),
+                   AllOf(QName("Foo::Foo"), WithKind(SymbolKind::Method)),
+                   AllOf(QName("Foo::Foo"), WithKind(SymbolKind::Method)),
+                   AllOf(QName("Foo::f"), WithKind(SymbolKind::Method)),
+                   AllOf(QName("f1"), WithKind(SymbolKind::Function)),
+                   AllOf(QName("Foo::operator="), WithKind(SymbolKind::Method)),
+                   AllOf(QName("Foo::~Foo"), WithKind(SymbolKind::Method)),
+                   AllOf(QName("Foo::Nested"), WithKind(SymbolKind::Class)),
+                   AllOf(QName("Foo::Nested::f"), WithKind(SymbolKind::Method)),
+                   AllOf(QName("Friend"), WithKind(SymbolKind::Class)),
+                   AllOf(QName("f1"), WithKind(SymbolKind::Function)),
+                   AllOf(QName("f2"), WithKind(SymbolKind::Function)),
+                   AllOf(QName("KInt"), WithKind(SymbolKind::Variable)),
+                   AllOf(QName("kStr"), WithKind(SymbolKind::Variable)),
+                   AllOf(QName("f1"), WithKind(SymbolKind::Function)),
+                   AllOf(QName("foo"), WithKind(SymbolKind::Namespace)),
+                   AllOf(QName("foo::int32"), WithKind(SymbolKind::Class)),
+                   AllOf(QName("foo::int32_t"), WithKind(SymbolKind::Class)),
+                   AllOf(QName("foo::v1"), WithKind(SymbolKind::Variable)),
+                   AllOf(QName("foo::bar"), WithKind(SymbolKind::Namespace)),
+                   AllOf(QName("foo::bar::v2"), WithKind(SymbolKind::Variable)),
+                   AllOf(QName("foo::baz"), WithKind(SymbolKind::Namespace))}));
+}
+
+TEST_F(DocumentSymbolsTest, DeclarationDefinition) {
+  std::string FilePath = testPath("foo.cpp");
+  Annotations Main(R"(
+      class Foo {
+        void $decl[[f]]();
+      };
+      void Foo::$def[[f]]() {
+      }
+    )");
+
+  addFile(FilePath, Main.code());
+  EXPECT_THAT(getSymbols(FilePath),
+              ElementsAre(AllOf(QName("Foo"), WithKind(SymbolKind::Class)),
+                          AllOf(QName("Foo::f"), WithKind(SymbolKind::Method),
+                                SymRange(Main.range("decl"))),
+                          AllOf(QName("Foo::f"), WithKind(SymbolKind::Method),
+                                SymRange(Main.range("def")))));
+}
+
+TEST_F(DocumentSymbolsTest, ExternSymbol) {
+  std::string FilePath = testPath("foo.cpp");
+  addFile(testPath("foo.h"), R"cpp(
+      extern int var = 2;
+      )cpp");
+  addFile(FilePath, R"cpp(
+      #include "foo.h"
+      )cpp");
+
+  EXPECT_THAT(getSymbols(FilePath), IsEmpty());
+}
+
+TEST_F(DocumentSymbolsTest, NoLocals) {
+  std::string FilePath = testPath("foo.cpp");
+  addFile(FilePath,
+          R"cpp(
+      void test(int FirstParam, int SecondParam) {
+        struct LocalClass {};
+        int local_var;
+      })cpp");
+  EXPECT_THAT(getSymbols(FilePath), ElementsAre(QName("test")));
+}
+
+TEST_F(DocumentSymbolsTest, Unnamed) {
+  std::string FilePath = testPath("foo.h");
+  addFile(FilePath,
+          R"cpp(
+      struct {
+        int InUnnamed;
+      } UnnamedStruct;
+      )cpp");
+  EXPECT_THAT(
+      getSymbols(FilePath),
+      ElementsAre(AllOf(QName("UnnamedStruct"), WithKind(SymbolKind::Variable)),
+                  AllOf(QName("(anonymous struct)::InUnnamed"),
+                        WithKind(SymbolKind::Field))));
+}
+
+TEST_F(DocumentSymbolsTest, InHeaderFile) {
+  addFile("bar.h", R"cpp(
+      int foo() {
+      }
+      )cpp");
+  std::string FilePath = testPath("foo.h");
+  addFile(FilePath, R"cpp(
+      #include "bar.h"
+      int test() {
+      }
+      )cpp");
+  addFile("foo.cpp", R"cpp(
+      #include "foo.h"
+      )cpp");
+  EXPECT_THAT(getSymbols(FilePath), ElementsAre(QName("test")));
+}
+
+TEST_F(DocumentSymbolsTest, Template) {
+  std::string FilePath = testPath("foo.cpp");
+  addFile(FilePath, R"(
+    // Primary templates and specializations are included but instantiations
+    // are not.
+    template <class T> struct Tmpl {T x = 0;};
+    template <> struct Tmpl<int> {};
+    extern template struct Tmpl<float>;
+    template struct Tmpl<double>;
+  )");
+  EXPECT_THAT(getSymbols(FilePath),
+              ElementsAre(AllOf(QName("Tmpl"), WithKind(SymbolKind::Struct)),
+                          AllOf(QName("Tmpl::x"), WithKind(SymbolKind::Field)),
+                          AllOf(QName("Tmpl"), WithKind(SymbolKind::Struct))));
+}
+
+TEST_F(DocumentSymbolsTest, Namespaces) {
+  std::string FilePath = testPath("foo.cpp");
+  addFile(FilePath, R"cpp(
+      namespace ans1 {
+        int ai1;
+      namespace ans2 {
+        int ai2;
+      }
+      }
+      namespace {
+      void test() {}
+      }
+
+      namespace na {
+      inline namespace nb {
+      class Foo {};
+      }
+      }
+      namespace na {
+      // This is still inlined.
+      namespace nb {
+      class Bar {};
+      }
+      }
+      )cpp");
+  EXPECT_THAT(
+      getSymbols(FilePath),
+      ElementsAreArray({QName("ans1"), QName("ans1::ai1"), QName("ans1::ans2"),
+                        QName("ans1::ans2::ai2"), QName("test"), QName("na"),
+                        QName("na::nb"), QName("na::Foo"), QName("na"),
+                        QName("na::nb"), QName("na::Bar")}));
+}
+
+TEST_F(DocumentSymbolsTest, Enums) {
+  std::string FilePath = testPath("foo.cpp");
+  addFile(FilePath, R"(
+      enum {
+        Red
+      };
+      enum Color {
+        Green
+      };
+      enum class Color2 {
+        Yellow
+      };
+      namespace ns {
+      enum {
+        Black
+      };
+      }
+    )");
+  EXPECT_THAT(getSymbols(FilePath),
+              ElementsAre(QName("Red"), QName("Color"), QName("Green"),
+                          QName("Color2"), QName("Color2::Yellow"), QName("ns"),
+                          QName("ns::Black")));
+}
+
+TEST_F(DocumentSymbolsTest, FromMacro) {
+  std::string FilePath = testPath("foo.cpp");
+  Annotations Main(R"(
+    #define FF(name) \
+      class name##_Test {};
+
+    $expansion[[FF]](abc);
+
+    #define FF2() \
+      class $spelling[[Test]] {};
+
+    FF2();
+  )");
+  addFile(FilePath, Main.code());
+  EXPECT_THAT(
+      getSymbols(FilePath),
+      ElementsAre(AllOf(QName("abc_Test"), SymRange(Main.range("expansion"))),
+                  AllOf(QName("Test"), SymRange(Main.range("spelling")))));
+}
+
 } // namespace clangd
 } // namespace clang

unittests/clangd/SyncAPI.h

 llvm::Expected<std::vector<tooling::Replacement>>
 runRename(ClangdServer &Server, PathRef File, Position Pos, StringRef NewName);
 
 std::string runDumpAST(ClangdServer &Server, PathRef File);
 
 llvm::Expected<std::vector<SymbolInformation>>
 runWorkspaceSymbols(ClangdServer &Server, StringRef Query, int Limit);
 
+llvm::Expected<std::vector<SymbolInformation>>
+runDocumentSymbols(ClangdServer &Server, PathRef File);
+
 } // namespace clangd
 } // namespace clang
 
 #endif

unittests/clangd/SyncAPI.cpp

 
 llvm::Expected<std::vector<SymbolInformation>>
 runWorkspaceSymbols(ClangdServer &Server, StringRef Query, int Limit) {
   llvm::Optional<llvm::Expected<std::vector<SymbolInformation>>> Result;
   Server.workspaceSymbols(Query, Limit, capture(Result));
   return std::move(*Result);
 }
 
+llvm::Expected<std::vector<SymbolInformation>>
+runDocumentSymbols(ClangdServer &Server, PathRef File) {
+  llvm::Optional<llvm::Expected<std::vector<SymbolInformation>>> Result;
+  Server.documentSymbols(File, capture(Result));
+  return std::move(*Result);
+}
+
 } // namespace clangd
 } // namespace clang