[clangd] Add textDocument/ast extension method to dump the AST

[sammccall]

Summary

This is a mass-market version of the "dump AST" tweak we have behind
-hidden-features.
I think in this friendlier form it'll be useful for people outside clang
developers, which would justify making it a real feature.
It could be useful as a step towards lightweight clang-AST tooling in clangd
itself (like matcher-based search).

Advantages over the tweak:

• simplified information makes it more accessible, likely somewhat useful without learning too much clang internals
• can be shown in a tree view
• structured information gives some options for presentation (e.g. icon + two text colors + tooltip in vscode)
• clickable nodes jump to the corresponding code

Disadvantages:

• a bunch of code to handle different node types
• likely missing some important info vs dump-ast due to brevity/oversight
• may end up chasing/maintaining support for the long tail of nodes

Demo with VSCode support: https://imgur.com/a/6gKfyIV

[sammccall]

Oops, forgot newly added files :-\

[sammccall]

(for real this time)

[adamcz]

clang-tools-extra/clangd/ClangdServer.cpp

795

Please rename O to anything else. *O below looks very much like *0 and it had me really confused.

clang-tools-extra/clangd/ClangdServer.h

323

Any reason not to name arguments here?

clang-tools-extra/clangd/DumpAST.cpp

242

Maybe instead of "" the fallback should be to just return the code in the getSourceRange() range?

394

Lots of lint warnings here about "const". Please fix.

clang-tools-extra/clangd/Protocol.h

1672

We should really disable readability-identifier-naming check on this file, it's complaining on every single identifier.

clang-tools-extra/clangd/unittests/DumpASTTests.cpp

105

Can you add a test case for class with overloaded operator(s)? They tend to cause issues here and there.

[sammccall]

clang-tools-extra/clangd/ClangdServer.h

323

I generally prefer not to name them in the declaration when it doesn't communicate anything beyond the type.

Done here as most of the other functions name them.

(I'm curious, do you think there are useful names here, or is the irregularity between named/unnamed bothersome?)

clang-tools-extra/clangd/DumpAST.cpp

242

This goes against a couple of related goals I have here:

• the detail should be short enough to quickly scan, roughly it should be one name (a class name is OK, but an arbitrary function signature isn't)
• the detail should relate to this *node*, not the whole subtree

clang-tools-extra/clangd/Protocol.h

1672

Agree - but I don't actually know how to do this without turning it off for the whole directory. (We could do that...)

clang-tools-extra/clangd/unittests/DumpASTTests.cpp

105

Added one with use of an overloaded operator (LMK if you wanted to dump the declaration instead)

[sammccall]

Address comments

[adamcz]

clang-tools-extra/clangd/ClangdServer.cpp

799

Also here please ;)

clang-tools-extra/clangd/ClangdServer.h

323

Unnamed argument makes me think that it's ignored by this function. It's in-line with Google style guide, maybe doesn't necessary apply here.

clang-tools-extra/clangd/DumpAST.cpp

210

lint says this can be const

clang-tools-extra/clangd/unittests/DumpASTTests.cpp

13

include order lint warning here

105

Thanks, that's exactly what I wanted.

[sammccall]

clang-tools-extra/clangd/unittests/DumpASTTests.cpp

13

Not sure what's going on here, this does seem to be the order that current clang-format wants. Maybe this clang-tidy is an older version?

[kadircet]

clang-tools-extra/clangd/unittests/DumpASTTests.cpp

13

Has been fixed with https://github.com/llvm/llvm-project/commit/5a9f3867046c4e1c97760e22a505f4d1d788417e

clang-tools-extra/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   CompileCommands.cpp
   Compiler.cpp
   Config.cpp
   ConfigCompile.cpp
   ConfigProvider.cpp
   ConfigYAML.cpp
   Diagnostics.cpp
   DraftStore.cpp
+  DumpAST.cpp
   ExpectedTypes.cpp
   FindSymbols.cpp
   FindTarget.cpp
   FileDistance.cpp
   Format.cpp
   FS.cpp
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp

clang-tools-extra/clangd/ClangdLSPServer.h

private:
   void onInitialize(const InitializeParams &, Callback<llvm::json::Value>);
   void onInitialized(const InitializedParams &);
   void onShutdown(const ShutdownParams &, Callback<std::nullptr_t>);
   void onSync(const NoParams &, Callback<std::nullptr_t>);
   void onDocumentDidOpen(const DidOpenTextDocumentParams &);
   void onDocumentDidChange(const DidChangeTextDocumentParams &);
   void onDocumentDidClose(const DidCloseTextDocumentParams &);
   void onDocumentDidSave(const DidSaveTextDocumentParams &);
+  void onAST(const ASTParams &, Callback<llvm::Optional<ASTNode>>);
   void onDocumentOnTypeFormatting(const DocumentOnTypeFormattingParams &,
                                   Callback<std::vector<TextEdit>>);
   void onDocumentRangeFormatting(const DocumentRangeFormattingParams &,
                                  Callback<std::vector<TextEdit>>);
   void onDocumentFormatting(const DocumentFormattingParams &,
                             Callback<std::vector<TextEdit>>);
   // The results are serialized 'vector<DocumentSymbol>' if
   // SupportsHierarchicalDocumentSymbol is true and 'vector<SymbolInformation>'

clang-tools-extra/clangd/ClangdLSPServer.cpp

 //===--- ClangdLSPServer.cpp - LSP server ------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "ClangdLSPServer.h"
 #include "ClangdServer.h"
 #include "CodeComplete.h"
 #include "Diagnostics.h"
 #include "DraftStore.h"
+#include "DumpAST.h"
 #include "GlobalCompilationDatabase.h"
 #include "Protocol.h"
 #include "SemanticHighlighting.h"
 #include "SourceCode.h"
 #include "TUScheduler.h"
 #include "URI.h"
 #include "refactor/Tweak.h"
 #include "support/Context.h"
 #include "support/MemoryTree.h"
 #include "support/Trace.h"
+#include "clang/AST/ASTContext.h"
 #include "clang/Basic/Version.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Allocator.h"
llvm::json::Object Result{
                  {"resolveProvider", false},
              }},
             {"hoverProvider", true},
             {"renameProvider", std::move(RenameProvider)},
             {"selectionRangeProvider", true},
             {"documentSymbolProvider", true},
             {"workspaceSymbolProvider", true},
             {"referencesProvider", true},
+            {"astProvider", true},
             {"executeCommandProvider",
              llvm::json::Object{
                  {"commands",
                   {ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND,
                    ExecuteCommandParams::CLANGD_APPLY_TWEAK}},
              }},
             {"typeHierarchyProvider", true},
             {"memoryUsageProvider", true}, // clangd extension.

 void ClangdLSPServer::onMemoryUsage(const NoParams &,
                                     Callback<MemoryTree> Reply) {
   llvm::BumpPtrAllocator DetailAlloc;
   MemoryTree MT(&DetailAlloc);
   profile(MT);
   Reply(std::move(MT));
 }
 
+void ClangdLSPServer::onAST(const ASTParams &Params,
+                            Callback<llvm::Optional<ASTNode>> CB) {
+  Server->getAST(Params.textDocument.uri.file(), Params.range, std::move(CB));
+}
+
 ClangdLSPServer::ClangdLSPServer(class Transport &Transp,
                                  const ThreadsafeFS &TFS,
                                  const ClangdLSPServer::Options &Opts)
     : BackgroundContext(Context::current().clone()), Transp(Transp),
       MsgHandler(new MessageHandler(*this)), TFS(TFS),
       SupportedSymbolKinds(defaultSymbolKinds()),
       SupportedCompletionItemKinds(defaultCompletionItemKinds()), Opts(Opts) {
   // clang-format off
ClangdLSPServer::ClangdLSPServer(class Transport &Transp,
   MsgHandler->bind("textDocument/switchSourceHeader", &ClangdLSPServer::onSwitchSourceHeader);
   MsgHandler->bind("textDocument/prepareRename", &ClangdLSPServer::onPrepareRename);
   MsgHandler->bind("textDocument/rename", &ClangdLSPServer::onRename);
   MsgHandler->bind("textDocument/hover", &ClangdLSPServer::onHover);
   MsgHandler->bind("textDocument/documentSymbol", &ClangdLSPServer::onDocumentSymbol);
   MsgHandler->bind("workspace/executeCommand", &ClangdLSPServer::onCommand);
   MsgHandler->bind("textDocument/documentHighlight", &ClangdLSPServer::onDocumentHighlight);
   MsgHandler->bind("workspace/symbol", &ClangdLSPServer::onWorkspaceSymbol);
+  MsgHandler->bind("textDocument/ast", &ClangdLSPServer::onAST);
   MsgHandler->bind("textDocument/didOpen", &ClangdLSPServer::onDocumentDidOpen);
   MsgHandler->bind("textDocument/didClose", &ClangdLSPServer::onDocumentDidClose);
   MsgHandler->bind("textDocument/didChange", &ClangdLSPServer::onDocumentDidChange);
   MsgHandler->bind("textDocument/didSave", &ClangdLSPServer::onDocumentDidSave);
   MsgHandler->bind("workspace/didChangeWatchedFiles", &ClangdLSPServer::onFileEvent);
   MsgHandler->bind("workspace/didChangeConfiguration", &ClangdLSPServer::onChangeConfiguration);
   MsgHandler->bind("textDocument/symbolInfo", &ClangdLSPServer::onSymbolInfo);
   MsgHandler->bind("textDocument/typeHierarchy", &ClangdLSPServer::onTypeHierarchy);

clang-tools-extra/clangd/ClangdServer.h

void semanticRanges(PathRef File, const std::vector<Position> &Pos,
                       Callback<std::vector<SelectionRange>> CB);
 
   /// Get all document links in a file.
   void documentLinks(PathRef File, Callback<std::vector<DocumentLink>> CB);
 
   void semanticHighlights(PathRef File,
                           Callback<std::vector<HighlightingToken>>);
 
+  /// Describe the AST subtree for a piece of code.
+  void getAST(PathRef File, Range R, Callback<llvm::Optional<ASTNode>> CB);
+
   /// Runs an arbitrary action that has access to the AST of the specified file.
   /// The action will execute on one of ClangdServer's internal threads.
   /// The AST is only valid for the duration of the callback.
   /// As with other actions, the file must have been opened.
   void customAction(PathRef File, llvm::StringRef Name,
                     Callback<InputsAndAST> Action);
 
   /// Returns estimated memory usage and other statistics for each of the

clang-tools-extra/clangd/ClangdServer.cpp

 //===--- ClangdServer.cpp - Main clangd server code --------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===-------------------------------------------------------------------===//
 
 #include "ClangdServer.h"
 #include "CodeComplete.h"
 #include "Config.h"
+#include "DumpAST.h"
 #include "FindSymbols.h"
 #include "Format.h"
 #include "HeaderSourceSwitch.h"
 #include "Headers.h"
 #include "ParsedAST.h"
 #include "Preamble.h"
 #include "Protocol.h"
 #include "SemanticHighlighting.h"
auto Action =
         if (!InpAST)
           return CB(InpAST.takeError());
         CB(clangd::getSemanticHighlightings(InpAST->AST));
       };
   WorkScheduler.runWithAST("SemanticHighlights", File, std::move(Action),
                            TUScheduler::InvalidateOnUpdate);
 }
 
+void ClangdServer::getAST(PathRef File, Range R,
+                          Callback<llvm::Optional<ASTNode>> CB) {
+  auto Action =
+      [R, CB(std::move(CB))](llvm::Expected<InputsAndAST> Inputs) mutable {
+        if (!Inputs)
+          return CB(Inputs.takeError());
+        unsigned Start, End;
+        if (auto Offset = positionToOffset(Inputs->Inputs.Contents, R.start))
+          Start = *Offset;
+        else
+          return CB(Offset.takeError());
+        if (auto Offset = positionToOffset(Inputs->Inputs.Contents, R.end))
+          End = *Offset;
+        else
+          return CB(Offset.takeError());
+
+        bool Success = SelectionTree::createEach(
+            Inputs->AST.getASTContext(), Inputs->AST.getTokens(), Start, End,
+            [&](SelectionTree T) {
+              if (const SelectionTree::Node *N = T.commonAncestor()) {
+                CB(dumpAST(N->ASTNode, Inputs->AST.getTokens(),
+                           Inputs->AST.getASTContext()));
+                return true;
+              }
+              return false;
+            });
+        if (!Success)
+          CB(llvm::None);
+      };
+  WorkScheduler.runWithAST("GetAST", File, std::move(Action));
+}
+
 void ClangdServer::customAction(PathRef File, llvm::StringRef Name,
                                 Callback<InputsAndAST> Action) {
   WorkScheduler.runWithAST(Name, File, std::move(Action));
 }
 
 llvm::StringMap<TUScheduler::FileStats> ClangdServer::fileStats() const {
   return WorkScheduler.fileStats();
 }

clang-tools-extra/clangd/DumpAST.h

+//===--- DumpAST.h - Serialize clang AST to LSP -----------------*- C++-*--===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Exposing clang's AST can give insight into the precise meaning of code.
+// (C++ is a complicated language, and very few people know all its rules).
+// Despite the name, clang's AST describes *semantics* and so includes nodes
+// for implicit behavior like conversions.
+//
+// It's also useful to developers who work with the clang AST specifically,
+// and want to know how certain constructs are represented.
+//
+// The main representation is not based on the familiar -ast-dump output,
+// which is heavy on internal details.
+// It also does not use the -ast-dump=json output, which captures the same
+// detail in a machine-friendly way, but requires client-side logic to present.
+// Instead, the key information is bundled into a few fields (role/kind/detail)
+// with weakly-defined semantics, optimized for easy presentation.
+// The -ast-dump output is preserved in the 'arcana' field, and may be shown
+// e.g. as a tooltip.
+//
+// The textDocument/ast method implemented here is a clangd extension.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_DUMPAST_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_DUMPAST_H
+
+#include "Protocol.h"
+#include "clang/AST/ASTContext.h"
+
+namespace clang {
+namespace syntax {
+class TokenBuffer;
+} // namespace syntax
+namespace clangd {
+
+ASTNode dumpAST(const DynTypedNode &, const syntax::TokenBuffer &Tokens,
+                const ASTContext &);
+
+} // namespace clangd
+} // namespace clang
+
+#endif

clang-tools-extra/clangd/DumpAST.cpp

+//===--- DumpAST.cpp - Serialize clang AST to LSP -------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "DumpAST.h"
+#include "Protocol.h"
+#include "SourceCode.h"
+#include "support/Logger.h"
+#include "clang/AST/ASTTypeTraits.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/ExprCXX.h"
+#include "clang/AST/ExternalASTSource.h"
+#include "clang/AST/NestedNameSpecifier.h"
+#include "clang/AST/PrettyPrinter.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/TextNodeDumper.h"
+#include "clang/AST/Type.h"
+#include "clang/AST/TypeLoc.h"
+#include "clang/Basic/Specifiers.h"
+#include "clang/Tooling/Syntax/Tokens.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+using llvm::raw_ostream;
+template <typename Print> std::string toString(const Print &C) {
+  std::string Result;
+  llvm::raw_string_ostream OS(Result);
+  C(OS);
+  return std::move(OS.str());
+}
+
+bool isInjectedClassName(Decl *D) {
+  if (const auto *CRD = llvm::dyn_cast<CXXRecordDecl>(D))
+    return CRD->isInjectedClassName();
+  return false;
+}
+
+class DumpVisitor : public RecursiveASTVisitor<DumpVisitor> {
+  using Base = RecursiveASTVisitor<DumpVisitor>;
+
+  const syntax::TokenBuffer &Tokens;
+  const ASTContext &Ctx;
+
+  // Pointers are into 'children' vector.
+  // They remain valid because while a node is on the stack we only add
+  // descendants, not siblings.
+  std::vector<ASTNode *> Stack;
+
+  // Generic logic used to handle traversal of all node kinds.
+
+  template <typename T>
+  bool traverseNodePre(llvm::StringRef Role, const T &Node) {
+    if (Stack.empty()) {
+      assert(Root.role.empty());
+      Stack.push_back(&Root);
+    } else {
+      Stack.back()->children.emplace_back();
+      Stack.push_back(&Stack.back()->children.back());
+    }
+    auto &N = *Stack.back();
+    N.role = Role.str();
+    N.kind = getKind(Node);
+    N.detail = getDetail(Node);
+    N.range = getRange(Node);
+    N.arcana = getArcana(Node);
+    return true;
+  }
+  bool traverseNodePost() {
+    assert(!Stack.empty());
+    Stack.pop_back();
+    return true;
+  }
+  template <typename T, typename Callable>
+  bool traverseNode(llvm::StringRef Role, const T &Node, const Callable &Body) {
+    traverseNodePre(Role, Node);
+    Body();
+    return traverseNodePost();
+  }
+
+  // Range: most nodes have getSourceRange(), with a couple of exceptions.
+  // We only return it if it's valid at both ends and there are no macros.
+
+  template <typename T> llvm::Optional<Range> getRange(const T &Node) {
+    SourceRange SR = getSourceRange(Node);
+    auto Spelled = Tokens.spelledForExpanded(Tokens.expandedTokens(SR));
+    if (!Spelled)
+      return llvm::None;
+    return halfOpenToRange(
+        Tokens.sourceManager(),
+        CharSourceRange::getCharRange(Spelled->front().location(),
+                                      Spelled->back().endLocation()));
+  }
+  template <typename T, typename = decltype(std::declval<T>().getSourceRange())>
+  SourceRange getSourceRange(const T &Node) {
+    return Node.getSourceRange();
+  }
+  template <typename T,
+            typename = decltype(std::declval<T *>()->getSourceRange())>
+  SourceRange getSourceRange(const T *Node) {
+    return Node->getSourceRange();
+  }
+  // TemplateName doesn't have a real Loc node type.
+  SourceRange getSourceRange(const TemplateName &Node) { return SourceRange(); }
+  // Attr just uses a weird method name. Maybe we should fix it instead?
+  SourceRange getSourceRange(const Attr *Node) { return Node->getRange(); }
+
+  // Kind is usualy the class name, without the suffix ("Type" etc).
+  // Where there's a set of variants instead, we use the 'Kind' enum values.
+
+  std::string getKind(const Decl *D) { return D->getDeclKindName(); }
+  std::string getKind(const Stmt *S) {
+    std::string Result = S->getStmtClassName();
+    if (llvm::StringRef(Result).endswith("Stmt") ||
+        llvm::StringRef(Result).endswith("Expr"))
+      Result.resize(Result.size() - 4);
+    return Result;
+  }
+  std::string getKind(const TypeLoc &TL) {
+    std::string Result;
+    if (TL.getTypeLocClass() == TypeLoc::Qualified)
+      return "Qualified";
+    return TL.getType()->getTypeClassName();
+  }
+  std::string getKind(const TemplateArgumentLoc &TAL) {
+    switch (TAL.getArgument().getKind()) {
+#define TEMPLATE_ARGUMENT_KIND(X)                                              \
+  case TemplateArgument::X:                                                    \
+    return #X
+      TEMPLATE_ARGUMENT_KIND(Null);
+      TEMPLATE_ARGUMENT_KIND(NullPtr);
+      TEMPLATE_ARGUMENT_KIND(Expression);
+      TEMPLATE_ARGUMENT_KIND(Integral);
+      TEMPLATE_ARGUMENT_KIND(Pack);
+      TEMPLATE_ARGUMENT_KIND(Type);
+      TEMPLATE_ARGUMENT_KIND(Declaration);
+      TEMPLATE_ARGUMENT_KIND(Template);
+      TEMPLATE_ARGUMENT_KIND(TemplateExpansion);
+#undef TEMPLATE_ARGUMENT_KIND
+    }
+  }
+  std::string getKind(const NestedNameSpecifierLoc &NNSL) {
+    assert(NNSL.getNestedNameSpecifier());
+    switch (NNSL.getNestedNameSpecifier()->getKind()) {
+#define NNS_KIND(X)                                                            \
+  case NestedNameSpecifier::X:                                                 \
+    return #X
+      NNS_KIND(Identifier);
+      NNS_KIND(Namespace);
+      NNS_KIND(TypeSpec);
+      NNS_KIND(TypeSpecWithTemplate);
+      NNS_KIND(Global);
+      NNS_KIND(Super);
+      NNS_KIND(NamespaceAlias);
+#undef NNS_KIND
+    }
+  }
+  std::string getKind(const CXXCtorInitializer *CCI) {
+    if (CCI->isBaseInitializer())
+      return "BaseInitializer";
+    if (CCI->isDelegatingInitializer())
+      return "DelegatingInitializer";
+    if (CCI->isAnyMemberInitializer())
+      return "MemberInitializer";
+    llvm_unreachable("Unhandled CXXCtorInitializer type");
+  }
+  std::string getKind(const TemplateName &TN) {
+    switch (TN.getKind()) {
+#define TEMPLATE_KIND(X)                                                       \
+  case TemplateName::X:                                                        \
+    return #X;
+      TEMPLATE_KIND(Template);
+      TEMPLATE_KIND(OverloadedTemplate);
+      TEMPLATE_KIND(AssumedTemplate);
+      TEMPLATE_KIND(QualifiedTemplate);
+      TEMPLATE_KIND(DependentTemplate);
+      TEMPLATE_KIND(SubstTemplateTemplateParm);
+      TEMPLATE_KIND(SubstTemplateTemplateParmPack);
+#undef TEMPLATE_KIND
+    }
+  }
+  std::string getKind(const Attr *A) {
+    switch (A->getKind()) {
+#define ATTR(X)                                                                \
+  case attr::X:                                                                \
+    return #X;
+#include "clang/Basic/AttrList.inc"
+#undef ATTR
+    }
+  }
+  std::string getKind(const CXXBaseSpecifier &CBS) {
+    // There aren't really any variants of CXXBaseSpecifier.
+    // To avoid special cases in the API/UI, use public/private as the kind.
+    return getAccessSpelling(CBS.getAccessSpecifier()).str();
+  }
+
+  // Detail is the single most important fact about the node.
+  // Often this is the name, sometimes a "kind" enum like operators or casts.
+  // We should avoid unbounded text, like dumping parameter lists.
+
+  std::string getDetail(const Decl *D) {
+    const auto *ND = dyn_cast<NamedDecl>(D);
+    if (!ND || llvm::isa_and_nonnull<CXXConstructorDecl>(ND->getAsFunction()) ||
+        isa<CXXDestructorDecl>(ND))
+      return "";
+    std::string Name = toString([&](raw_ostream &OS) { ND->printName(OS); });
+    if (Name.empty())
+      return "(anonymous)";
+    return Name;
+  }
+  std::string getDetail(const Stmt *S) {
+    if (const auto *DRE = dyn_cast<DeclRefExpr>(S))
+      return DRE->getNameInfo().getAsString();
+    if (const auto *DSDRE = dyn_cast<DependentScopeDeclRefExpr>(S))
+      return DSDRE->getNameInfo().getAsString();
+    if (const auto *ME = dyn_cast<MemberExpr>(S))
+      return ME->getMemberNameInfo().getAsString();
+    if (const auto *CE = dyn_cast<CastExpr>(S))
+      return CE->getCastKindName();
+    if (const auto *BO = dyn_cast<BinaryOperator>(S))
+      return BO->getOpcodeStr().str();
+    if (const auto *UO = dyn_cast<UnaryOperator>(S))
+      return UnaryOperator::getOpcodeStr(UO->getOpcode()).str();
+    if (const auto *CCO = dyn_cast<CXXConstructExpr>(S))
+      return CCO->getConstructor()->getNameAsString();
+    if (isa<IntegerLiteral>(S) || isa<FloatingLiteral>(S) ||
+        isa<FixedPointLiteral>(S) || isa<CharacterLiteral>(S) ||
+        isa<ImaginaryLiteral>(S) || isa<CXXBoolLiteralExpr>(S))
+      return toString([&](raw_ostream &OS) {
+        S->printPretty(OS, nullptr, Ctx.getPrintingPolicy());
+      });
+    if (const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(S))
+      return MTE->isBoundToLvalueReference() ? "lvalue" : "rvalue";
+    return "";
+  }
+  std::string getDetail(const TypeLoc &TL) {
+    if (TL.getType().hasLocalQualifiers())
+      return TL.getType().getLocalQualifiers().getAsString(
+          Ctx.getPrintingPolicy());
+    if (const auto *TT = dyn_cast<TagType>(TL.getTypePtr()))
+      return getDetail(TT->getDecl());
+    if (const auto *DT = dyn_cast<DeducedType>(TL.getTypePtr()))
+      if (DT->isDeduced())
+        return DT->getDeducedType().getAsString(Ctx.getPrintingPolicy());
+    if (const auto *BT = dyn_cast<BuiltinType>(TL.getTypePtr()))
+      return BT->getName(Ctx.getPrintingPolicy()).str();
+    if (const auto *TTPT = dyn_cast<TemplateTypeParmType>(TL.getTypePtr()))
+      return getDetail(TTPT->getDecl());
+    if (const auto *TT = dyn_cast<TypedefType>(TL.getTypePtr()))
+      return getDetail(TT->getDecl());
+    return "";
+  }
+  std::string getDetail(const NestedNameSpecifierLoc &NNSL) {
+    const auto &NNS = *NNSL.getNestedNameSpecifier();
+    switch (NNS.getKind()) {
+    case NestedNameSpecifier::Identifier:
+      return NNS.getAsIdentifier()->getName().str() + "::";
+    case NestedNameSpecifier::Namespace:
+      return NNS.getAsNamespace()->getNameAsString() + "::";
+    case NestedNameSpecifier::NamespaceAlias:
+      return NNS.getAsNamespaceAlias()->getNameAsString() + "::";
+    default:
+      return "";
+    }
+  }
+  std::string getDetail(const CXXCtorInitializer *CCI) {
+    if (FieldDecl *FD = CCI->getAnyMember())
+      return getDetail(FD);
+    if (TypeLoc TL = CCI->getBaseClassLoc())
+      return getDetail(TL);
+    return "";
+  }
+  std::string getDetail(const TemplateArgumentLoc &TAL) {
+    if (TAL.getArgument().getKind() == TemplateArgument::Integral)
+      return TAL.getArgument().getAsIntegral().toString(10);
+    return "";
+  }
+  std::string getDetail(const TemplateName &TN) {
+    return toString([&](raw_ostream &OS) {
+      TN.print(OS, Ctx.getPrintingPolicy(), /*SuppressNNS=*/true);
+    });
+  }
+  std::string getDetail(const Attr *A) {
+    return A->getAttrName() ? A->getNormalizedFullName() : A->getSpelling();
+  }
+  std::string getDetail(const CXXBaseSpecifier &CBS) {
+    return CBS.isVirtual() ? "virtual" : "";
+  }
+
+  /// Arcana is produced by TextNodeDumper, for the types it supports.
+
+  template <typename Dump> std::string dump(const Dump &D) {
+    return toString([&](raw_ostream &OS) {
+      TextNodeDumper Dumper(OS, Ctx, /*ShowColors=*/false);
+      D(Dumper);
+    });
+  }
+  template <typename T> std::string getArcana(const T &N) {
+    return dump([&](TextNodeDumper &D) { D.Visit(N); });
+  }
+  std::string getArcana(const NestedNameSpecifierLoc &NNS) { return ""; }
+  std::string getArcana(const TemplateName &NNS) { return ""; }
+  std::string getArcana(const CXXBaseSpecifier &CBS) { return ""; }
+  std::string getArcana(const TemplateArgumentLoc &TAL) {
+    return dump([&](TextNodeDumper &D) {
+      D.Visit(TAL.getArgument(), TAL.getSourceRange());
+    });
+  }
+  std::string getArcana(const TypeLoc &TL) {
+    return dump([&](TextNodeDumper &D) { D.Visit(TL.getType()); });
+  }
+
+public:
+  ASTNode Root;
+  DumpVisitor(const syntax::TokenBuffer &Tokens, const ASTContext &Ctx)
+      : Tokens(Tokens), Ctx(Ctx) {}
+
+  // Override traversal to record the nodes we care about.
+  // Generally, these are nodes with position information (TypeLoc, not Type).
+  bool TraverseDecl(Decl *D) {
+    return !D || isInjectedClassName(D) ||
+           traverseNode("declaration", D, [&] { Base::TraverseDecl(D); });
+  }
+  bool TraverseTypeLoc(TypeLoc TL) {
+    return !TL || traverseNode("type", TL, [&] { Base::TraverseTypeLoc(TL); });
+  }
+  bool TraverseTemplateName(const TemplateName &TN) {
+    return traverseNode("template name", TN,
+                        [&] { Base::TraverseTemplateName(TN); });
+  }
+  bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &TAL) {
+    return traverseNode("template argument", TAL,
+                        [&] { Base::TraverseTemplateArgumentLoc(TAL); });
+  }
+  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSL) {
+    return !NNSL || traverseNode("specifier", NNSL, [&] {
+      Base::TraverseNestedNameSpecifierLoc(NNSL);
+    });
+  }
+  bool TraverseConstructorInitializer(CXXCtorInitializer *CCI) {
+    return !CCI || traverseNode("constructor initializer", CCI, [&] {
+      Base::TraverseConstructorInitializer(CCI);
+    });
+  }
+  bool TraverseAttr(Attr *A) {
+    return !A || traverseNode("attribute", A, [&] { Base::TraverseAttr(A); });
+  }
+  bool TraverseCXXBaseSpecifier(const CXXBaseSpecifier &CBS) {
+    return traverseNode("base", CBS,
+                        [&] { Base::TraverseCXXBaseSpecifier(CBS); });
+  }
+  // Stmt is the same, but this form allows the data recursion optimization.
+  bool dataTraverseStmtPre(Stmt *S) {
+    return S && traverseNodePre(isa<Expr>(S) ? "expression" : "statement", S);
+  }
+  bool dataTraverseStmtPost(Stmt *X) { return traverseNodePost(); }
+
+  // QualifiedTypeLoc is handled strangely in RecursiveASTVisitor: the derived
+  // TraverseTypeLoc is not called for the inner UnqualTypeLoc.
+  // This means we'd never see 'int' in 'const int'! Work around that here.
+  // (The reason for the behavior is to avoid traversing the nested Type twice,
+  // but we ignore TraverseType anyway).
+  bool TraverseQualifiedTypeLoc(QualifiedTypeLoc QTL) {
+    return TraverseTypeLoc(QTL.getUnqualifiedLoc());
+  }
+  // Uninteresting parts of the AST that don't have locations within them.
+  bool TraverseNestedNameSpecifier(NestedNameSpecifier *) { return true; }
+  bool TraverseType(QualType) { return true; }
+
+  // OpaqueValueExpr blocks traversal, we must explicitly traverse it.
+  bool TraverseOpaqueValueExpr(OpaqueValueExpr *E) {
+    return TraverseStmt(E->getSourceExpr());
+  }
+  // We only want to traverse the *syntactic form* to understand the selection.
+  bool TraversePseudoObjectExpr(PseudoObjectExpr *E) {
+    return TraverseStmt(E->getSyntacticForm());
+  }
+};
+
+} // namespace
+
+ASTNode dumpAST(const DynTypedNode &N, const syntax::TokenBuffer &Tokens,
+                const ASTContext &Ctx) {
+  DumpVisitor V(Tokens, Ctx);
+  // DynTypedNode only works with const, RecursiveASTVisitor only non-const :-(
+  if (const auto *D = N.get<Decl>())
+    V.TraverseDecl(const_cast<Decl *>(D));
+  else if (const auto *S = N.get<Stmt>())
+    V.TraverseStmt(const_cast<Stmt *>(S));
+  else if (const auto *NNSL = N.get<NestedNameSpecifierLoc>())
+    V.TraverseNestedNameSpecifierLoc(
+        *const_cast<NestedNameSpecifierLoc *>(NNSL));
+  else if (const auto *NNS = N.get<NestedNameSpecifier>())
+    V.TraverseNestedNameSpecifier(const_cast<NestedNameSpecifier *>(NNS));
+  else if (const auto *TL = N.get<TypeLoc>())
+    V.TraverseTypeLoc(*const_cast<TypeLoc *>(TL));
+  else if (const auto *QT = N.get<QualType>())
+    V.TraverseType(*const_cast<QualType *>(QT));
+  else if (const auto *CCI = N.get<CXXCtorInitializer>())
+    V.TraverseConstructorInitializer(const_cast<CXXCtorInitializer *>(CCI));
+  else if (const auto *TAL = N.get<TemplateArgumentLoc>())
+    V.TraverseTemplateArgumentLoc(*const_cast<TemplateArgumentLoc *>(TAL));
+  else if (const auto *CBS = N.get<CXXBaseSpecifier>())
+    V.TraverseCXXBaseSpecifier(*const_cast<CXXBaseSpecifier *>(CBS));
+  else
+    elog("dumpAST: unhandled DynTypedNode kind {0}",
+         N.getNodeKind().asStringRef());
+  return std::move(V.Root);
+}
+
+} // namespace clangd
+} // namespace clang

clang-tools-extra/clangd/Protocol.h

struct FoldingRange {
   llvm::Optional<std::string> kind;
 };
 llvm::json::Value toJSON(const FoldingRange &Range);
 
 /// Keys starting with an underscore(_) represent leaves, e.g. _total or _self
 /// for memory usage of whole subtree or only that specific node in bytes. All
 /// other keys represents children. An example:
 ///   {
 ///     "_self": 0,
 ///     "_total": 8,
 ///     "child1": {
 ///       "_self": 4,
 ///       "_total": 4,
 ///     }
 ///     "child2": {
 ///       "_self": 2,
 ///       "_total": 4,
 ///       "child_deep": {
 ///         "_self": 2,
 ///         "_total": 2,
 ///       }
 ///     }
 ///   }
 llvm::json::Value toJSON(const MemoryTree &MT);
 
+/// Payload for textDocument/ast request.
+/// This request is a clangd extension.
+struct ASTParams {
+  /// The text document.
+  TextDocumentIdentifier textDocument;
+
+  /// The position of the node to be dumped.
+  /// The highest-level node that entirely contains the range will be returned.
+  Range range;
+};
+bool fromJSON(const llvm::json::Value &, ASTParams &, llvm::json::Path);
+
+/// Simplified description of a clang AST node.
+/// This is clangd's internal representation of C++ code.
+struct ASTNode {
+  /// The general kind of node, such as "expression"
+  /// Corresponds to the base AST node type such as Expr.
+  std::string role;
+  /// The specific kind of node this is, such as "BinaryOperator".
+  /// This is usually a concrete node class (with Expr etc suffix dropped).
+  /// When there's no hierarchy (e.g. TemplateName), the variant (NameKind).
+  std::string kind;
+  /// Brief additional information, such as "||" for the particular operator.
+  /// The information included depends on the node kind, and may be empty.
+  std::string detail;
+  /// A one-line dump of detailed information about the node.
+  /// This includes role/kind/description information, but is rather cryptic.
+  /// It is similar to the output from `clang -Xclang -ast-dump`.
+  /// May be empty for certain types of nodes.
+  std::string arcana;
+  /// The range of the original source file covered by this node.
+  /// May be missing for implicit nodes, or those created by macro expansion.
+  llvm::Optional<Range> range;
+  /// Nodes nested within this one, such as the operands of a BinaryOperator.
+  std::vector<ASTNode> children;
+};
+llvm::json::Value toJSON(const ASTNode &);
+llvm::raw_ostream &operator<<(llvm::raw_ostream &, const ASTNode &);
+
 } // namespace clangd
 } // namespace clang
 
 namespace llvm {
 template <> struct format_provider<clang::clangd::Position> {
   static void format(const clang::clangd::Position &Pos, raw_ostream &OS,
                      StringRef Style) {
     assert(Style.empty() && "style modifiers for this type are not supported");
     OS << Pos;
   }
 };
 } // namespace llvm
 
 #endif

clang-tools-extra/clangd/Protocol.cpp

llvm::json::Value toJSON(const MemoryTree &MT) {
   for (const auto &Entry : MT.children()) {
     auto Child = toJSON(Entry.getSecond());
     Total += *Child.getAsObject()->getInteger("_total");
     Out[Entry.first] = std::move(Child);
   }
   Out["_total"] = Total;
   return Out;
 }
+
+bool fromJSON(const llvm::json::Value &Params, ASTParams &R,
+              llvm::json::Path P) {
+  llvm::json::ObjectMapper O(Params, P);
+  return O && O.map("textDocument", R.textDocument) && O.map("range", R.range);
+}
+
+llvm::json::Value toJSON(const ASTNode &N) {
+  llvm::json::Object Result{
+      {"role", N.role},
+      {"kind", N.kind},
+  };
+  if (!N.children.empty())
+    Result["children"] = N.children;
+  if (!N.detail.empty())
+    Result["detail"] = N.detail;
+  if (!N.arcana.empty())
+    Result["arcana"] = N.arcana;
+  if (N.range)
+    Result["range"] = *N.range;
+  return Result;
+}
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const ASTNode &Root) {
+  std::function<void(const ASTNode &, unsigned)> Print = [&](const ASTNode &N,
+                                                             unsigned Level) {
+    OS.indent(2 * Level) << N.role << ": " << N.kind;
+    if (!N.detail.empty())
+      OS << " - " << N.detail;
+    OS << "\n";
+    for (const ASTNode &C : N.children)
+      Print(C, Level + 1);
+  };
+  Print(Root, 0);
+  return OS;
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/test/ast.test

+# RUN: clangd -lit-test < %s | FileCheck %s
+{"jsonrpc":"2.0","id":0,"method":"initialize","params":{"processId":123,"rootPath":"clangd","capabilities":{},"trace":"off"}}
+---
+{"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"test:///simple.cpp","languageId":"cpp","version":1,"text":"int x;"}}}
+---
+{"jsonrpc":"2.0","id":1,"method":"textDocument/ast","params":{
+  "textDocument":{"uri":"test:///simple.cpp"},
+  "range": {"start": {"line":0, "character":0}, "end": {"line":0, "character":5}}
+}}
+#      CHECK:  "id": 1,
+# CHECK-NEXT:  "jsonrpc": "2.0",
+# CHECK-NEXT:  "result": {
+# CHECK-NEXT:    "arcana": "VarDecl {{.*}} x 'int'",
+# CHECK-NEXT:    "children": [
+# CHECK-NEXT:      {
+# CHECK-NEXT:        "arcana": "QualType {{.*}} 'int' ",
+# CHECK-NEXT:        "detail": "int",
+# CHECK-NEXT:        "kind": "Builtin",
+# CHECK-NEXT:        "range": {
+# CHECK-NEXT:          "end": {
+# CHECK-NEXT:            "character": 3,
+# CHECK-NEXT:            "line": 0
+# CHECK-NEXT:          },
+# CHECK-NEXT:          "start": {
+# CHECK-NEXT:            "character": 0,
+# CHECK-NEXT:            "line": 0
+# CHECK-NEXT:          }
+# CHECK-NEXT:        },
+# CHECK-NEXT:        "role": "type"
+# CHECK-NEXT:      }
+# CHECK-NEXT:    ],
+# CHECK-NEXT:    "detail": "x",
+# CHECK-NEXT:    "kind": "Var",
+# CHECK-NEXT:    "range": {
+# CHECK-NEXT:      "end": {
+# CHECK-NEXT:        "character": 5,
+# CHECK-NEXT:        "line": 0
+# CHECK-NEXT:      },
+# CHECK-NEXT:      "start": {
+# CHECK-NEXT:        "character": 0,
+# CHECK-NEXT:        "line": 0
+# CHECK-NEXT:      }
+# CHECK-NEXT:    },
+# CHECK-NEXT:    "role": "declaration"
+# CHECK-NEXT:  }
+---
+{"jsonrpc":"2.0","id":2,"method":"shutdown"}
+---
+{"jsonrpc":"2.0","method":"exit"}

clang-tools-extra/clangd/test/initialize-params.test

 # RUN: clangd -lit-test < %s | FileCheck -strict-whitespace %s
 # Test initialize request parameters with rootUri
 {"jsonrpc":"2.0","id":0,"method":"initialize","params":{"processId":123,"rootUri":"test:///workspace","capabilities":{},"trace":"off"}}
 #      CHECK:  "id": 0,
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "capabilities": {
+# CHECK-NEXT:      "astProvider": true,
 # CHECK-NEXT:      "codeActionProvider": true,
 # CHECK-NEXT:      "completionProvider": {
 # CHECK-NEXT:        "allCommitCharacters": [
 # CHECK-NEXT:          " ",
 # CHECK-NEXT:          "\t",
 # CHECK-NEXT:          "(",
 # CHECK-NEXT:          ")",
 # CHECK-NEXT:          "[",

clang-tools-extra/clangd/unittests/CMakeLists.txt

add_unittest(ClangdUnitTests ClangdTests
   CompilerTests.cpp
   ConfigCompileTests.cpp
   ConfigProviderTests.cpp
   ConfigYAMLTests.cpp
   DecisionForestTests.cpp
   DexTests.cpp
   DiagnosticsTests.cpp
   DraftStoreTests.cpp
+  DumpASTTests.cpp
   ExpectedTypeTest.cpp
   FileDistanceTests.cpp
   FileIndexTests.cpp
   FindSymbolsTests.cpp
   FindTargetTests.cpp
   FormatTests.cpp
   FSTests.cpp
   FuzzyMatchTests.cpp

clang-tools-extra/clangd/unittests/DumpASTTests.cpp

+//===-- DumpASTTests.cpp --------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Annotations.h"
+#include "DumpAST.h"
+#include "TestTU.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+using testing::SizeIs;
+
+TEST(DumpASTTests, BasicInfo) {
+  std::pair</*Code=*/std::string, /*Expected=*/std::string> Cases[] = {
+      {R"cpp(
+float root(int *x) {
+  return *x + 1;
+}
+      )cpp",
+       R"(
+declaration: Function - root
+  type: FunctionProto
+    type: Builtin - float
+    declaration: ParmVar - x
+      type: Pointer
+        type: Builtin - int
+  statement: Compound
+    statement: Return
+      expression: ImplicitCast - IntegralToFloating
+        expression: BinaryOperator - +
+          expression: ImplicitCast - LValueToRValue
+            expression: UnaryOperator - *
+              expression: ImplicitCast - LValueToRValue
+                expression: DeclRef - x
+          expression: IntegerLiteral - 1
+      )"},
+      {R"cpp(
+namespace root {
+struct S { static const int x = 0; };
+int y = S::x + root::S().x;
+}
+      )cpp",
+       R"(
+declaration: Namespace - root
+  declaration: CXXRecord - S
+    declaration: Var - x
+      type: Qualified - const
+        type: Builtin - int
+      expression: IntegerLiteral - 0
+    declaration: CXXConstructor
+    declaration: CXXConstructor
+    declaration: CXXConstructor
+    declaration: CXXDestructor
+  declaration: Var - y
+    type: Builtin - int
+    expression: ExprWithCleanups
+      expression: BinaryOperator - +
+        expression: ImplicitCast - LValueToRValue
+          expression: DeclRef - x
+            specifier: TypeSpec
+              type: Record - S
+        expression: ImplicitCast - LValueToRValue
+          expression: Member - x
+            expression: MaterializeTemporary - rvalue
+              expression: CXXTemporaryObject - S
+                type: Elaborated
+                  specifier: Namespace - root::
+                  type: Record - S
+      )"},
+      {R"cpp(
+template <typename T> int root() {
+  (void)root<unsigned>();
+  return T::value;
+}
+      )cpp",
+       R"(
+declaration: FunctionTemplate - root
+  declaration: TemplateTypeParm - T
+  declaration: Function - root
+    type: FunctionProto
+      type: Builtin - int
+    statement: Compound
+      expression: CStyleCast - ToVoid
+        type: Builtin - void
+        expression: Call
+          expression: ImplicitCast - FunctionToPointerDecay
+            expression: DeclRef - root
+              template argument: Type
+                type: Builtin - unsigned int
+      statement: Return
+        expression: DependentScopeDeclRef - value
+          specifier: TypeSpec
+            type: TemplateTypeParm - T
+      )"},
+      {R"cpp(
+struct Foo { char operator+(int); };
+char root = Foo() + 42;
+      )cpp",
+       R"(
+declaration: Var - root
+  type: Builtin - char
+  expression: ExprWithCleanups
+    expression: CXXOperatorCall
+      expression: ImplicitCast - FunctionToPointerDecay
+        expression: DeclRef - operator+
+      expression: MaterializeTemporary - lvalue
+        expression: CXXTemporaryObject - Foo
+          type: Record - Foo
+      expression: IntegerLiteral - 42
+      )"},
+  };
+  for (const auto &Case : Cases) {
+    ParsedAST AST = TestTU::withCode(Case.first).build();
+    auto Node = dumpAST(DynTypedNode::create(findDecl(AST, "root")),
+                        AST.getTokens(), AST.getASTContext());
+    EXPECT_EQ(llvm::StringRef(Case.second).trim(),
+              llvm::StringRef(llvm::to_string(Node)).trim());
+  }
+}
+
+TEST(DumpASTTests, Range) {
+  Annotations Case("$var[[$type[[int]] x]];");
+  ParsedAST AST = TestTU::withCode(Case.code()).build();
+  auto Node = dumpAST(DynTypedNode::create(findDecl(AST, "x")), AST.getTokens(),
+                      AST.getASTContext());
+  EXPECT_EQ(Node.range, Case.range("var"));
+  ASSERT_THAT(Node.children, SizeIs(1)) << "Expected one child typeloc";
+  EXPECT_EQ(Node.children.front().range, Case.range("type"));
+}
+
+TEST(DumpASTTests, Arcana) {
+  ParsedAST AST = TestTU::withCode("int x;").build();
+  auto Node = dumpAST(DynTypedNode::create(findDecl(AST, "x")), AST.getTokens(),
+                      AST.getASTContext());
+  EXPECT_THAT(Node.arcana, testing::StartsWith("VarDecl "));
+  EXPECT_THAT(Node.arcana, testing::EndsWith(" 'int'"));
+  ASSERT_THAT(Node.children, SizeIs(1)) << "Expected one child typeloc";
+  EXPECT_THAT(Node.children.front().arcana, testing::StartsWith("QualType "));
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang