[clangd] Support for standard type hierarchy

[kadircet]

Summary

This is mostly a mechanical change to adapt standard type hierarchy
support proposed in LSP 3.17 on top of clangd's existing extension support.

This does mainly two things:

• Incorporate symbolids for all the parents inside resolution parameters, so that they can be retrieved from index later on. This is a new code path, as extension always resolved them eagerly.
• Propogate parent information when resolving children, so that at least one branch of parents is always preserved. This is to address a shortcoming in the extension.

This doesn't drop support for the extension, but it's deprecated from now on and
will be deleted in upcoming releases. Currently we use the same struct
internally but don't serialize extra fields.

[nridge]

Related issue: https://github.com/clangd/clangd/issues/826

[usaxena95]

clang-tools-extra/clangd/Protocol.cpp

1228

Nit: Allow RVO.

clang-tools-extra/clangd/Protocol.h

1415

nit.

clang-tools-extra/clangd/XRefs.cpp

1953–1962

Can you revert the formatting changes in l:1894-1964

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

781

It would be clearer if we use getSymbolID(&findDecl(AST, "Parent1")) here and in SuperTypes.

[kadircet]

clang-tools-extra/clangd/Protocol.cpp

1228

there's an issue with one of the compilers used by a build-bot which can't find the relevant constructor if we don't have std::move here (hence we've the same pattern across others). we should definitely check at some point to see if that compiler is gone, but i'd rather not do that in the scope of this patch.

clang-tools-extra/clangd/XRefs.cpp

1953–1962

oops, thanks for noticing.

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

781

not sure what you mean by also doing it in SuperTypes

[kadircet]

• Address comments

[usaxena95]

LG. Thanks!

clang-tools-extra/clangd/Protocol.cpp

1228

Interesting. Makes sense to get to it later.

clang-tools-extra/clangd/XRefs.cpp

1713

nit: std::move.

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

781

Nvm. I was referring to SuperTypes test but it does not check for the symbol id.

[kadircet]

clang-tools-extra/clangd/XRefs.cpp

1713

the copy here is actually intentional. as we need to preserve data both in current element and also in its parent.

clang-tools-extra/clangd/ClangdLSPServer.h

 #include "support/MemoryTree.h"
 #include "support/Path.h"
 #include "support/Threading.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/Support/JSON.h"
 #include <chrono>
 #include <cstddef>
 #include <memory>
+#include <vector>
 
 namespace clang {
 namespace clangd {
 
 /// This class exposes ClangdServer's capabilities via Language Server Protocol.
 ///
 /// MessageHandler binds the implemented LSP methods (e.g. onInitialize) to
 /// corresponding JSON-RPC methods ("initialize").
private:
   void onFileEvent(const DidChangeWatchedFilesParams &);
   void onWorkspaceSymbol(const WorkspaceSymbolParams &,
                          Callback<std::vector<SymbolInformation>>);
   void onPrepareRename(const TextDocumentPositionParams &,
                        Callback<llvm::Optional<Range>>);
   void onRename(const RenameParams &, Callback<WorkspaceEdit>);
   void onHover(const TextDocumentPositionParams &,
                Callback<llvm::Optional<Hover>>);
-  void onTypeHierarchy(const TypeHierarchyParams &,
-                       Callback<llvm::Optional<TypeHierarchyItem>>);
+  void onPrepareTypeHierarchy(const TypeHierarchyPrepareParams &,
+                              Callback<std::vector<TypeHierarchyItem>>);
+  void onSuperTypes(const ResolveTypeHierarchyItemParams &,
+                    Callback<llvm::Optional<std::vector<TypeHierarchyItem>>>);
+  void onSubTypes(const ResolveTypeHierarchyItemParams &,
+                  Callback<std::vector<TypeHierarchyItem>>);
+  void onTypeHierarchy(const TypeHierarchyPrepareParams &,
+                       Callback<llvm::json::Value>);
   void onResolveTypeHierarchy(const ResolveTypeHierarchyItemParams &,
-                              Callback<llvm::Optional<TypeHierarchyItem>>);
+                              Callback<llvm::json::Value>);
   void onPrepareCallHierarchy(const CallHierarchyPrepareParams &,
                               Callback<std::vector<CallHierarchyItem>>);
   void onCallHierarchyIncomingCalls(
       const CallHierarchyIncomingCallsParams &,
       Callback<std::vector<CallHierarchyIncomingCall>>);
   void onCallHierarchyOutgoingCalls(
       const CallHierarchyOutgoingCallsParams &,
       Callback<std::vector<CallHierarchyOutgoingCall>>);

clang-tools-extra/clangd/ClangdLSPServer.cpp

 #include "URI.h"
 #include "refactor/Tweak.h"
 #include "support/Cancellation.h"
 #include "support/Context.h"
 #include "support/MemoryTree.h"
 #include "support/Trace.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/FunctionExtras.h"
+#include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/JSON.h"
llvm::json::Object ServerCaps{
        }},
       {"hoverProvider", true},
       {"selectionRangeProvider", true},
       {"documentSymbolProvider", true},
       {"workspaceSymbolProvider", true},
       {"referencesProvider", true},
       {"astProvider", true}, // clangd extension
       {"typeHierarchyProvider", true},
-      {"memoryUsageProvider", true}, // clangd extension
-      {"compilationDatabase",        // clangd extension
+      // Unfortunately our extension made use of the same capability name as the
+      // standard. Advertise this capability to tell clients that implement our
+      // extension we really have support for the standardized one as well.
+      {"standardTypeHierarchyProvider", true}, // clangd extension
+      {"memoryUsageProvider", true},           // clangd extension
+      {"compilationDatabase",                  // clangd extension
        llvm::json::Object{{"automaticReload", true}}},
       {"callHierarchyProvider", true},
       {"clangdInlayHintsProvider", true},
       {"inlayHintProvider", true},
   };
 
   {
     LSPBinder Binder(Handlers, *this);
Server->findHover(Params.textDocument.uri.file(), Params.position,
                       case MarkupKind::Markdown:
                         R.contents.value = (*H)->present().asMarkdown();
                         return Reply(std::move(R));
                       };
                       llvm_unreachable("unhandled MarkupKind");
                     });
 }
 
-void ClangdLSPServer::onTypeHierarchy(
-    const TypeHierarchyParams &Params,
-    Callback<Optional<TypeHierarchyItem>> Reply) {
+// Our extension has a different representation on the wire than the standard.
+// https://clangd.llvm.org/extensions#type-hierarchy
+llvm::json::Value serializeTHIForExtension(TypeHierarchyItem THI) {
+  llvm::json::Object Result{{
+      {"name", std::move(THI.name)},
+      {"kind", static_cast<int>(THI.kind)},
+      {"uri", std::move(THI.uri)},
+      {"range", THI.range},
+      {"selectionRange", THI.selectionRange},
+      {"data", std::move(THI.data)},
+  }};
+  if (THI.deprecated)
+    Result["deprecated"] = THI.deprecated;
+  if (THI.detail)
+    Result["detail"] = std::move(*THI.detail);
+
+  if (THI.parents) {
+    llvm::json::Array Parents;
+    for (auto &Parent : *THI.parents)
+      Parents.emplace_back(serializeTHIForExtension(std::move(Parent)));
+    Result["parents"] = std::move(Parents);
+  }
+
+  if (THI.children) {
+    llvm::json::Array Children;
+    for (auto &child : *THI.children)
+      Children.emplace_back(serializeTHIForExtension(std::move(child)));
+    Result["children"] = std::move(Children);
+  }
+  return Result;
+}
+
+void ClangdLSPServer::onTypeHierarchy(const TypeHierarchyPrepareParams &Params,
+                                      Callback<llvm::json::Value> Reply) {
+  auto Serialize =
+      [Reply = std::move(Reply)](
+          llvm::Expected<std::vector<TypeHierarchyItem>> Resp) mutable {
+        if (!Resp) {
+          Reply(Resp.takeError());
+          return;
+        }
+        if (Resp->empty()) {
+          Reply(nullptr);
+          return;
+        }
+        Reply(serializeTHIForExtension(std::move(Resp->front())));
+      };
   Server->typeHierarchy(Params.textDocument.uri.file(), Params.position,
-                        Params.resolve, Params.direction, std::move(Reply));
+                        Params.resolve, Params.direction, std::move(Serialize));
 }
 
 void ClangdLSPServer::onResolveTypeHierarchy(
     const ResolveTypeHierarchyItemParams &Params,
-    Callback<Optional<TypeHierarchyItem>> Reply) {
+    Callback<llvm::json::Value> Reply) {
+  auto Serialize =
+      [Reply = std::move(Reply)](
+          llvm::Expected<llvm::Optional<TypeHierarchyItem>> Resp) mutable {
+        if (!Resp) {
+          Reply(Resp.takeError());
+          return;
+        }
+        if (!*Resp) {
+          Reply(std::move(*Resp));
+          return;
+        }
+        Reply(serializeTHIForExtension(std::move(**Resp)));
+      };
   Server->resolveTypeHierarchy(Params.item, Params.resolve, Params.direction,
-                               std::move(Reply));
+                               std::move(Serialize));
+}
+
+void ClangdLSPServer::onPrepareTypeHierarchy(
+    const TypeHierarchyPrepareParams &Params,
+    Callback<std::vector<TypeHierarchyItem>> Reply) {
+  Server->typeHierarchy(Params.textDocument.uri.file(), Params.position,
+                        Params.resolve, Params.direction, std::move(Reply));
+}
+
+void ClangdLSPServer::onSuperTypes(
+    const ResolveTypeHierarchyItemParams &Params,
+    Callback<llvm::Optional<std::vector<TypeHierarchyItem>>> Reply) {
+  Server->superTypes(Params.item, std::move(Reply));
+}
+
+void ClangdLSPServer::onSubTypes(
+    const ResolveTypeHierarchyItemParams &Params,
+    Callback<std::vector<TypeHierarchyItem>> Reply) {
+  Server->subTypes(Params.item, std::move(Reply));
 }
 
 void ClangdLSPServer::onPrepareCallHierarchy(
     const CallHierarchyPrepareParams &Params,
     Callback<std::vector<CallHierarchyItem>> Reply) {
   Server->prepareCallHierarchy(Params.textDocument.uri.file(), Params.position,
                                std::move(Reply));
 }
void ClangdLSPServer::bindMethods(LSPBinder &Bind,
   Bind.notification("textDocument/didClose", this, &ClangdLSPServer::onDocumentDidClose);
   Bind.notification("textDocument/didChange", this, &ClangdLSPServer::onDocumentDidChange);
   Bind.notification("textDocument/didSave", this, &ClangdLSPServer::onDocumentDidSave);
   Bind.notification("workspace/didChangeWatchedFiles", this, &ClangdLSPServer::onFileEvent);
   Bind.notification("workspace/didChangeConfiguration", this, &ClangdLSPServer::onChangeConfiguration);
   Bind.method("textDocument/symbolInfo", this, &ClangdLSPServer::onSymbolInfo);
   Bind.method("textDocument/typeHierarchy", this, &ClangdLSPServer::onTypeHierarchy);
   Bind.method("typeHierarchy/resolve", this, &ClangdLSPServer::onResolveTypeHierarchy);
+  Bind.method("textDocument/prepareTypeHierarchy", this, &ClangdLSPServer::onPrepareTypeHierarchy);
+  Bind.method("typeHierarchy/supertypes", this, &ClangdLSPServer::onSuperTypes);
+  Bind.method("typeHierarchy/subtypes", this, &ClangdLSPServer::onSubTypes);
   Bind.method("textDocument/prepareCallHierarchy", this, &ClangdLSPServer::onPrepareCallHierarchy);
   Bind.method("callHierarchy/incomingCalls", this, &ClangdLSPServer::onCallHierarchyIncomingCalls);
   Bind.method("textDocument/selectionRange", this, &ClangdLSPServer::onSelectionRange);
   Bind.method("textDocument/documentLink", this, &ClangdLSPServer::onDocumentLink);
   Bind.method("textDocument/semanticTokens/full", this, &ClangdLSPServer::onSemanticTokens);
   Bind.method("textDocument/semanticTokens/full/delta", this, &ClangdLSPServer::onSemanticTokensDelta);
   Bind.method("clangd/inlayHints", this, &ClangdLSPServer::onClangdInlayHints);
   Bind.method("textDocument/inlayHint", this, &ClangdLSPServer::onInlayHint);

clang-tools-extra/clangd/ClangdServer.h

public:
 
   /// Get code hover for a given position.
   void findHover(PathRef File, Position Pos,
                  Callback<llvm::Optional<HoverInfo>> CB);
 
   /// Get information about type hierarchy for a given position.
   void typeHierarchy(PathRef File, Position Pos, int Resolve,
                      TypeHierarchyDirection Direction,
-                     Callback<llvm::Optional<TypeHierarchyItem>> CB);
+                     Callback<std::vector<TypeHierarchyItem>> CB);
+  /// Get direct parents of a type hierarchy item.
+  void superTypes(const TypeHierarchyItem &Item,
+                  Callback<llvm::Optional<std::vector<TypeHierarchyItem>>> CB);
+  /// Get direct children of a type hierarchy item.
+  void subTypes(const TypeHierarchyItem &Item,
+                Callback<std::vector<TypeHierarchyItem>> CB);
 
   /// Resolve type hierarchy item in the given direction.
   void resolveTypeHierarchy(TypeHierarchyItem Item, int Resolve,
                             TypeHierarchyDirection Direction,
                             Callback<llvm::Optional<TypeHierarchyItem>> CB);
 
   /// Get information about call hierarchy for a given position.
   void prepareCallHierarchy(PathRef File, Position Pos,

clang-tools-extra/clangd/ClangdServer.cpp

auto Action = [File = File.str(), Pos, CB = std::move(CB),
     CB(clangd::getHover(InpAST->AST, Pos, std::move(Style), Index));
   };
 
   WorkScheduler->runWithAST("Hover", File, std::move(Action), Transient);
 }
 
 void ClangdServer::typeHierarchy(PathRef File, Position Pos, int Resolve,
                                  TypeHierarchyDirection Direction,
-                                 Callback<Optional<TypeHierarchyItem>> CB) {
+                                 Callback<std::vector<TypeHierarchyItem>> CB) {
   auto Action = [File = File.str(), Pos, Resolve, Direction, CB = std::move(CB),
                  this](Expected<InputsAndAST> InpAST) mutable {
     if (!InpAST)
       return CB(InpAST.takeError());
     CB(clangd::getTypeHierarchy(InpAST->AST, Pos, Resolve, Direction, Index,
                                 File));
   };
 
   WorkScheduler->runWithAST("TypeHierarchy", File, std::move(Action));
 }
 
+void ClangdServer::superTypes(
+    const TypeHierarchyItem &Item,
+    Callback<llvm::Optional<std::vector<TypeHierarchyItem>>> CB) {
+  WorkScheduler->run("typeHierarchy/superTypes", /*Path=*/"",
+                     [=, CB = std::move(CB)]() mutable {
+                       CB(clangd::superTypes(Item, Index));
+                     });
+}
+
+void ClangdServer::subTypes(const TypeHierarchyItem &Item,
+                            Callback<std::vector<TypeHierarchyItem>> CB) {
+  WorkScheduler->run(
+      "typeHierarchy/subTypes", /*Path=*/"",
+      [=, CB = std::move(CB)]() mutable { CB(clangd::subTypes(Item, Index)); });
+}
+
 void ClangdServer::resolveTypeHierarchy(
     TypeHierarchyItem Item, int Resolve, TypeHierarchyDirection Direction,
     Callback<llvm::Optional<TypeHierarchyItem>> CB) {
   WorkScheduler->run(
       "Resolve Type Hierarchy", "", [=, CB = std::move(CB)]() mutable {
         clangd::resolveTypeHierarchy(Item, Resolve, Direction, Index);
         CB(Item);
       });

clang-tools-extra/clangd/Protocol.h

public:
   void log(llvm::raw_ostream &OS) const override {
     OS << int(Code) << ": " << Message;
   }
   std::error_code convertToErrorCode() const override {
     return llvm::inconvertibleErrorCode();
   }
 };
 
+bool fromJSON(const llvm::json::Value &, SymbolID &, llvm::json::Path);
+llvm::json::Value toJSON(const SymbolID &);
+
 // URI in "file" scheme for a file.
 struct URIForFile {
   URIForFile() = default;
 
   /// Canonicalizes \p AbsPath via URI.
   ///
   /// File paths in URIForFile can come from index or local AST. Path from
   /// index goes through URI transformation, and the final path is resolved by

 
 enum class TypeHierarchyDirection { Children = 0, Parents = 1, Both = 2 };
 bool fromJSON(const llvm::json::Value &E, TypeHierarchyDirection &Out,
               llvm::json::Path);
 
 /// The type hierarchy params is an extension of the
 /// `TextDocumentPositionsParams` with optional properties which can be used to
 /// eagerly resolve the item when requesting from the server.
-struct TypeHierarchyParams : public TextDocumentPositionParams {
+struct TypeHierarchyPrepareParams : public TextDocumentPositionParams {
   /// The hierarchy levels to resolve. `0` indicates no level.
+  /// This is a clangd extension.
   int resolve = 0;
 
   /// The direction of the hierarchy levels to resolve.
+  /// This is a clangd extension.
   TypeHierarchyDirection direction = TypeHierarchyDirection::Parents;
 };
-bool fromJSON(const llvm::json::Value &, TypeHierarchyParams &,
+bool fromJSON(const llvm::json::Value &, TypeHierarchyPrepareParams &,
               llvm::json::Path);
 
 struct TypeHierarchyItem {
-  /// The human readable name of the hierarchy item.
+  /// The name of this item.
   std::string name;
 
-  /// Optional detail for the hierarchy item. It can be, for instance, the
-  /// signature of a function or method.
-  llvm::Optional<std::string> detail;
-
-  /// The kind of the hierarchy item. For instance, class or interface.
+  /// The kind of this item.
   SymbolKind kind;
 
-  /// `true` if the hierarchy item is deprecated. Otherwise, `false`.
-  bool deprecated = false;
+  /// More detail for this item, e.g. the signature of a function.
+  llvm::Optional<std::string> detail;
 
-  /// The URI of the text document where this type hierarchy item belongs to.
+  /// The resource identifier of this item.
   URIForFile uri;
 
-  /// The range enclosing this type hierarchy item not including
-  /// leading/trailing whitespace but everything else like comments. This
-  /// information is typically used to determine if the client's cursor is
-  /// inside the type hierarch item to reveal in the symbol in the UI.
+  /// The range enclosing this symbol not including leading/trailing whitespace
+  /// but everything else, e.g. comments and code.
   Range range;
 
-  /// The range that should be selected and revealed when this type hierarchy
-  /// item is being picked, e.g. the name of a function. Must be contained by
-  /// the `range`.
+  /// The range that should be selected and revealed when this symbol is being
+  /// picked, e.g. the name of a function. Must be contained by the `range`.
   Range selectionRange;
 
-  /// If this type hierarchy item is resolved, it contains the direct parents.
-  /// Could be empty if the item does not have direct parents. If not defined,
-  /// the parents have not been resolved yet.
+  /// Used to resolve a client provided item back.
+  struct ResolveParams {
+    SymbolID symbolID;
+    /// None means parents aren't resolved and empty is no parents.
+    llvm::Optional<std::vector<ResolveParams>> parents;
+  };
+  /// A data entry field that is preserved between a type hierarchy prepare and
+  /// supertypes or subtypes requests. It could also be used to identify the
+  /// type hierarchy in the server, helping improve the performance on resolving
+  /// supertypes and subtypes.
+  ResolveParams data;
+
+  /// `true` if the hierarchy item is deprecated. Otherwise, `false`.
+  /// This is a clangd exntesion.
+  bool deprecated = false;
+
+  /// This is a clangd exntesion.
   llvm::Optional<std::vector<TypeHierarchyItem>> parents;
 
   /// If this type hierarchy item is resolved, it contains the direct children
   /// of the current item. Could be empty if the item does not have any
   /// descendants. If not defined, the children have not been resolved.
+  /// This is a clangd exntesion.
   llvm::Optional<std::vector<TypeHierarchyItem>> children;
-
-  /// An optional 'data' field, which can be used to identify a type hierarchy
-  /// item in a resolve request.
-  llvm::Optional<std::string> data;
 };
+llvm::json::Value toJSON(const TypeHierarchyItem::ResolveParams &);
+bool fromJSON(const TypeHierarchyItem::ResolveParams &);
 llvm::json::Value toJSON(const TypeHierarchyItem &);
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const TypeHierarchyItem &);
 bool fromJSON(const llvm::json::Value &, TypeHierarchyItem &, llvm::json::Path);
 
 /// Parameters for the `typeHierarchy/resolve` request.
 struct ResolveTypeHierarchyItemParams {
   /// The item to resolve.
   TypeHierarchyItem item;

clang-tools-extra/clangd/Protocol.cpp

if (!T)
     return false;
   if (*T < static_cast<int>(TypeHierarchyDirection::Children) ||
       *T > static_cast<int>(TypeHierarchyDirection::Both))
     return false;
   Out = static_cast<TypeHierarchyDirection>(*T);
   return true;
 }
 
-bool fromJSON(const llvm::json::Value &Params, TypeHierarchyParams &R,
+bool fromJSON(const llvm::json::Value &Params, TypeHierarchyPrepareParams &R,
               llvm::json::Path P) {
   llvm::json::ObjectMapper O(Params, P);
   return O && O.map("textDocument", R.textDocument) &&
-         O.map("position", R.position) && O.map("resolve", R.resolve) &&
-         O.map("direction", R.direction);
+         O.map("position", R.position) &&
+         mapOptOrNull(Params, "resolve", R.resolve, P) &&
+         mapOptOrNull(Params, "direction", R.direction, P);
 }
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &O,
                               const TypeHierarchyItem &I) {
   return O << I.name << " - " << toJSON(I);
 }
 
+llvm::json::Value toJSON(const TypeHierarchyItem::ResolveParams &RP) {
+  llvm::json::Object Result{{"symbolID", RP.symbolID}};
+  if (RP.parents)
+    Result["parents"] = RP.parents;
+  return std::move(Result);
+}
+bool fromJSON(const llvm::json::Value &Params,
+              TypeHierarchyItem::ResolveParams &RP, llvm::json::Path P) {
+  llvm::json::ObjectMapper O(Params, P);
+  return O && O.map("symbolID", RP.symbolID) &&
+         mapOptOrNull(Params, "parents", RP.parents, P);
+}
+
 llvm::json::Value toJSON(const TypeHierarchyItem &I) {
-  llvm::json::Object Result{{"name", I.name},
-                            {"kind", static_cast<int>(I.kind)},
-                            {"range", I.range},
-                            {"selectionRange", I.selectionRange},
-                            {"uri", I.uri}};
+  llvm::json::Object Result{
+      {"name", I.name},   {"kind", static_cast<int>(I.kind)},
+      {"range", I.range}, {"selectionRange", I.selectionRange},
+      {"uri", I.uri},     {"data", I.data},
+  };
 
   if (I.detail)
     Result["detail"] = I.detail;
-  if (I.deprecated)
-    Result["deprecated"] = I.deprecated;
-  if (I.parents)
-    Result["parents"] = I.parents;
-  if (I.children)
-    Result["children"] = I.children;
-  if (I.data)
-    Result["data"] = I.data;
   return std::move(Result);
 }
 
 bool fromJSON(const llvm::json::Value &Params, TypeHierarchyItem &I,
               llvm::json::Path P) {
   llvm::json::ObjectMapper O(Params, P);
 
   // Required fields.
   return O && O.map("name", I.name) && O.map("kind", I.kind) &&
          O.map("uri", I.uri) && O.map("range", I.range) &&
          O.map("selectionRange", I.selectionRange) &&
          mapOptOrNull(Params, "detail", I.detail, P) &&
          mapOptOrNull(Params, "deprecated", I.deprecated, P) &&
          mapOptOrNull(Params, "parents", I.parents, P) &&
          mapOptOrNull(Params, "children", I.children, P) &&
          mapOptOrNull(Params, "data", I.data, P);
 }
 
 bool fromJSON(const llvm::json::Value &Params,
               ResolveTypeHierarchyItemParams &R, llvm::json::Path P) {
   llvm::json::ObjectMapper O(Params, P);
-  return O && O.map("item", R.item) && O.map("resolve", R.resolve) &&
-         O.map("direction", R.direction);
+  return O && O.map("item", R.item) &&
+         mapOptOrNull(Params, "resolve", R.resolve, P) &&
+         mapOptOrNull(Params, "direction", R.direction, P);
 }
 
 bool fromJSON(const llvm::json::Value &Params, ReferenceContext &R,
               llvm::json::Path P) {
   llvm::json::ObjectMapper O(Params, P);
   return O && O.mapOptional("includeDeclaration", R.includeDeclaration);
 }
 
std::function<void(const ASTNode &, unsigned)> Print = [&](const ASTNode &N,
     OS << "\n";
     for (const ASTNode &C : N.children)
       Print(C, Level + 1);
   };
   Print(Root, 0);
   return OS;
 }
 
+bool fromJSON(const llvm::json::Value &E, SymbolID &S, llvm::json::Path P) {
+  auto Str = E.getAsString();
+  if (!Str) {
+    P.report("expected a string");
+    return false;
+  }
+  auto ID = SymbolID::fromStr(*Str);
+  if (!ID) {
+    elog("Malformed symbolid: {0}", ID.takeError());
+    P.report("malformed symbolid");
+    return false;
+  }
+  S = *ID;
+  return true;
+}
+llvm::json::Value toJSON(const SymbolID &S) { return S.str(); }
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/XRefs.h

 /// Returns references of the symbol at a specified \p Pos.
 /// \p Limit limits the number of results returned (0 means no limit).
 ReferencesResult findReferences(ParsedAST &AST, Position Pos, uint32_t Limit,
                                 const SymbolIndex *Index = nullptr);
 
 /// Get info about symbols at \p Pos.
 std::vector<SymbolDetails> getSymbolInfo(ParsedAST &AST, Position Pos);
 
-/// Find the record type references at \p Pos.
-const CXXRecordDecl *findRecordTypeAt(ParsedAST &AST, Position Pos);
+/// Find the record types referenced at \p Pos.
+std::vector<const CXXRecordDecl *> findRecordTypeAt(ParsedAST &AST,
+                                                    Position Pos);
 
 /// Given a record type declaration, find its base (parent) types.
 std::vector<const CXXRecordDecl *> typeParents(const CXXRecordDecl *CXXRD);
 
 /// Get type hierarchy information at \p Pos.
-llvm::Optional<TypeHierarchyItem> getTypeHierarchy(
+std::vector<TypeHierarchyItem> getTypeHierarchy(
     ParsedAST &AST, Position Pos, int Resolve, TypeHierarchyDirection Direction,
     const SymbolIndex *Index = nullptr, PathRef TUPath = PathRef{});
 
+/// Returns direct parents of a TypeHierarchyItem using SymbolIDs stored inside
+/// the item.
+llvm::Optional<std::vector<TypeHierarchyItem>>
+superTypes(const TypeHierarchyItem &Item, const SymbolIndex *Index);
+/// Returns direct children of a TypeHierarchyItem.
+std::vector<TypeHierarchyItem> subTypes(const TypeHierarchyItem &Item,
+                                        const SymbolIndex *Index);
+
 void resolveTypeHierarchy(TypeHierarchyItem &Item, int ResolveLevels,
                           TypeHierarchyDirection Direction,
                           const SymbolIndex *Index);
 
 /// Get call hierarchy information at \p Pos.
 std::vector<CallHierarchyItem>
 prepareCallHierarchy(ParsedAST &AST, Position Pos, PathRef TUPath);
 

clang-tools-extra/clangd/XRefs.cpp

 #include "clang/Index/IndexSymbol.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Index/IndexingOptions.h"
 #include "clang/Index/USRGeneration.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/raw_ostream.h"
+#include <vector>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 // Returns the single definition of the entity declared by D, if visible.
 // In particular:
 // - for non-redeclarable kinds (e.g. local vars), return D
struct Reference {
     SymbolID Target;
 
     Range range(const SourceManager &SM) const {
       return halfOpenToRange(SM, SpelledTok.range(SM).toCharRange(SM));
     }
   };
 
   ReferenceFinder(const ParsedAST &AST,
-                  const llvm::ArrayRef<const NamedDecl *> Targets, bool PerToken)
+                  const llvm::ArrayRef<const NamedDecl *> Targets,
+                  bool PerToken)
       : PerToken(PerToken), AST(AST) {
     for (const NamedDecl *ND : Targets) {
       const Decl *CD = ND->getCanonicalDecl();
       TargetDeclToID[CD] = getSymbolID(CD);
     }
   }
 
   std::vector<Reference> take() && {

 private:
   bool PerToken; // If true, report 3 references for split ObjC selector names.
   std::vector<Reference> References;
   const ParsedAST &AST;
   llvm::DenseMap<const Decl *, SymbolID> TargetDeclToID;
 };
 
 std::vector<ReferenceFinder::Reference>
-findRefs(const llvm::ArrayRef<const NamedDecl*> TargetDecls, ParsedAST &AST,
+findRefs(const llvm::ArrayRef<const NamedDecl *> TargetDecls, ParsedAST &AST,
          bool PerToken) {
   ReferenceFinder RefFinder(AST, TargetDecls, PerToken);
   index::IndexingOptions IndexOpts;
   IndexOpts.SystemSymbolFilter =
       index::IndexingOptions::SystemSymbolFilterKind::All;
   IndexOpts.IndexFunctionLocals = true;
   IndexOpts.IndexParametersInDeclarations = true;
   IndexOpts.IndexTemplateParameters = true;
if (!CurLoc) {
     llvm::consumeError(CurLoc.takeError());
     return {};
   }
   std::vector<DocumentHighlight> Result;
   auto TryTree = [&](SelectionTree ST) {
     if (const SelectionTree::Node *N = ST.commonAncestor()) {
       DeclRelationSet Relations =
           DeclRelation::TemplatePattern | DeclRelation::Alias;
-      auto TargetDecls=
-           targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver());
+      auto TargetDecls =
       if (!TargetDecls.empty()) {
         // FIXME: we may get multiple DocumentHighlights with the same location
         // and different kinds, deduplicate them.
         for (const auto &Ref : findRefs(TargetDecls, AST, /*PerToken=*/true))
           Result.push_back(toHighlight(Ref, SM));
         return true;
       }
       auto ControlFlow = relatedControlFlow(*N);
declToHierarchyItem(const NamedDecl &ND, llvm::StringRef TUPath) {
   if (!HI.range.contains(HI.selectionRange)) {
     // 'selectionRange' must be contained in 'range', so in cases where clang
     // reports unrelated ranges we need to reconcile somehow.
     HI.range = HI.selectionRange;
   }
 
   HI.uri = URIForFile::canonicalize(*FilePath, TUPath);
 
-  // Compute the SymbolID and store it in the 'data' field.
-  // This allows typeHierarchy/resolve to be used to
-  // resolve children of items returned in a previous request
-  // for parents.
-  if (auto ID = getSymbolID(&ND))
-    HI.data = ID.str();
-
   return HI;
 }
 
 static llvm::Optional<TypeHierarchyItem>
 declToTypeHierarchyItem(const NamedDecl &ND, llvm::StringRef TUPath) {
   auto Result = declToHierarchyItem<TypeHierarchyItem>(ND, TUPath);
-  if (Result)
+  if (Result) {
     Result->deprecated = ND.isDeprecated();
+    // Compute the SymbolID and store it in the 'data' field.
+    // This allows typeHierarchy/resolve to be used to
+    // resolve children of items returned in a previous request
+    // for parents.
+    Result->data.symbolID = getSymbolID(&ND);
+  }
   return Result;
 }
 
 static llvm::Optional<CallHierarchyItem>
 declToCallHierarchyItem(const NamedDecl &ND, llvm::StringRef TUPath) {
   auto Result = declToHierarchyItem<CallHierarchyItem>(ND, TUPath);
-  if (Result && ND.isDeprecated())
+  if (!Result)
+    return Result;
+  if (ND.isDeprecated())
     Result->tags.push_back(SymbolTag::Deprecated);
+  if (auto ID = getSymbolID(&ND))
+    Result->data = ID.str();
   return Result;
 }
 
 template <typename HierarchyItem>
 static llvm::Optional<HierarchyItem> symbolToHierarchyItem(const Symbol &S,
                                                            PathRef TUPath) {
   auto Loc = symbolToLocation(S, TUPath);
   if (!Loc) {
     elog("Failed to convert symbol to hierarchy item: {0}", Loc.takeError());
     return llvm::None;
   }
   HierarchyItem HI;
   HI.name = std::string(S.Name);
   HI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind);
   HI.selectionRange = Loc->range;
   // FIXME: Populate 'range' correctly
   // (https://github.com/clangd/clangd/issues/59).
   HI.range = HI.selectionRange;
   HI.uri = Loc->uri;
-  // Store the SymbolID in the 'data' field. The client will
-  // send this back in requests to resolve additional levels
-  // of the hierarchy.
-  HI.data = S.ID.str();
 
   return HI;
 }
 
 static llvm::Optional<TypeHierarchyItem>
 symbolToTypeHierarchyItem(const Symbol &S, PathRef TUPath) {
   auto Result = symbolToHierarchyItem<TypeHierarchyItem>(S, TUPath);
-  if (Result)
+  if (Result) {
     Result->deprecated = (S.Flags & Symbol::Deprecated);
+    Result->data.symbolID = S.ID;
+  }
   return Result;
 }
 
 static llvm::Optional<CallHierarchyItem>
 symbolToCallHierarchyItem(const Symbol &S, PathRef TUPath) {
   auto Result = symbolToHierarchyItem<CallHierarchyItem>(S, TUPath);
-  if (Result && (S.Flags & Symbol::Deprecated))
+  if (!Result)
+    return Result;
+  Result->data = S.ID.str();
+  if (S.Flags & Symbol::Deprecated)
     Result->tags.push_back(SymbolTag::Deprecated);
   return Result;
 }
 
 static void fillSubTypes(const SymbolID &ID,
                          std::vector<TypeHierarchyItem> &SubTypes,
                          const SymbolIndex *Index, int Levels, PathRef TUPath) {
   RelationsRequest Req;
   Req.Subjects.insert(ID);
   Req.Predicate = RelationKind::BaseOf;
   Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
     if (Optional<TypeHierarchyItem> ChildSym =
             symbolToTypeHierarchyItem(Object, TUPath)) {
       if (Levels > 1) {
         ChildSym->children.emplace();
         fillSubTypes(Object.ID, *ChildSym->children, Index, Levels - 1, TUPath);
       }
       SubTypes.emplace_back(std::move(*ChildSym));
     }
   });
 }
 
 using RecursionProtectionSet = llvm::SmallSet<const CXXRecordDecl *, 4>;
 
+// Extracts parents from AST and populates the type hierarchy item.
 static void fillSuperTypes(const CXXRecordDecl &CXXRD, llvm::StringRef TUPath,
-                           std::vector<TypeHierarchyItem> &SuperTypes,
+                           TypeHierarchyItem &Item,
                            RecursionProtectionSet &RPSet) {
+  Item.parents.emplace();
+  Item.data.parents.emplace();
   // typeParents() will replace dependent template specializations
   // with their class template, so to avoid infinite recursion for
   // certain types of hierarchies, keep the templates encountered
   // along the parent chain in a set, and stop the recursion if one
   // starts to repeat.
   auto *Pattern = CXXRD.getDescribedTemplate() ? &CXXRD : nullptr;
   if (Pattern) {
     if (!RPSet.insert(Pattern).second) {
       return;
     }
   }
 
   for (const CXXRecordDecl *ParentDecl : typeParents(&CXXRD)) {
     if (Optional<TypeHierarchyItem> ParentSym =
             declToTypeHierarchyItem(*ParentDecl, TUPath)) {
-      ParentSym->parents.emplace();
-      fillSuperTypes(*ParentDecl, TUPath, *ParentSym->parents, RPSet);
-      SuperTypes.emplace_back(std::move(*ParentSym));
+      fillSuperTypes(*ParentDecl, TUPath, *ParentSym, RPSet);
+      Item.data.parents->emplace_back(ParentSym->data);
+      Item.parents->emplace_back(std::move(*ParentSym));
     }
   }
 
   if (Pattern) {
     RPSet.erase(Pattern);
   }
 }
 
-const CXXRecordDecl *findRecordTypeAt(ParsedAST &AST, Position Pos) {
-  auto RecordFromNode =
-      [&AST](const SelectionTree::Node *N) -> const CXXRecordDecl * {
+std::vector<const CXXRecordDecl *> findRecordTypeAt(ParsedAST &AST,
+                                                    Position Pos) {
+  auto RecordFromNode = [&AST](const SelectionTree::Node *N) {
+    std::vector<const CXXRecordDecl *> Records;
     if (!N)
-      return nullptr;
+      return Records;
 
     // Note: explicitReferenceTargets() will search for both template
     // instantiations and template patterns, and prefer the former if available
     // (generally, one will be available for non-dependent specializations of a
     // class template).
     auto Decls = explicitReferenceTargets(N->ASTNode, DeclRelation::Underlying,
                                           AST.getHeuristicResolver());
-    if (Decls.empty())
-      return nullptr;
-
-    const NamedDecl *D = Decls[0];
+    for (const NamedDecl *D : Decls) {
 
       if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
         // If this is a variable, use the type of the variable.
-      return VD->getType().getTypePtr()->getAsCXXRecordDecl();
+        Records.push_back(VD->getType().getTypePtr()->getAsCXXRecordDecl());
+        continue;
       }
 
       if (const CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(D)) {
         // If this is a method, use the type of the class.
-      return Method->getParent();
+        Records.push_back(Method->getParent());
+        continue;
       }
 
       // We don't handle FieldDecl because it's not clear what behaviour
       // the user would expect: the enclosing class type (as with a
       // method), or the field's type (as with a variable).
 
-    return dyn_cast<CXXRecordDecl>(D);
+      if (auto *RD = dyn_cast<CXXRecordDecl>(D))
+        Records.push_back(RD);
+    }
+    return Records;
   };
 
   const SourceManager &SM = AST.getSourceManager();
-  const CXXRecordDecl *Result = nullptr;
+  std::vector<const CXXRecordDecl *> Result;
   auto Offset = positionToOffset(SM.getBufferData(SM.getMainFileID()), Pos);
   if (!Offset) {
     llvm::consumeError(Offset.takeError());
     return Result;
   }
   SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), *Offset,
                             *Offset, [&](SelectionTree ST) {
                               Result = RecordFromNode(ST.commonAncestor());
-                              return Result != nullptr;
+                              return !Result.empty();
                             });
   return Result;
 }
 
 // Return the type most associated with an AST node.
 // This isn't precisely defined: we want "go to type" to do something useful.
 static QualType typeForNode(const SelectionTree::Node *N) {
   // If we're looking at a namespace qualifier, walk up to what it's qualifying.
std::vector<LocatedSymbol> findType(ParsedAST &AST, Position Pos) {
   std::vector<LocatedSymbol> Result;
   if (!Offset) {
     elog("failed to convert position {0} for findTypes: {1}", Pos,
          Offset.takeError());
     return Result;
   }
   // The general scheme is: position -> AST node -> type -> declaration.
   auto SymbolsFromNode =
       [&AST](const SelectionTree::Node *N) -> std::vector<LocatedSymbol> {
     std::vector<LocatedSymbol> LocatedSymbols;
 
     // NOTE: unwrapFindType might return duplicates for something like
     // unique_ptr<unique_ptr<T>>. Let's *not* remove them, because it gives you some
     // information about the type you may have not known before
     // (since unique_ptr<unique_ptr<T>> != unique_ptr<T>).
     for (const QualType& Type : unwrapFindType(typeForNode(N), AST.getHeuristicResolver()))
         llvm::copy(locateSymbolForType(AST, Type), std::back_inserter(LocatedSymbols));
 
     return LocatedSymbols;
   };
   SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), *Offset,
                             *Offset, [&](SelectionTree ST) {
                               Result = SymbolsFromNode(ST.commonAncestor());
                               return !Result.empty();
                             });
   return Result;
for (auto Base : CXXRD->bases()) {
 
     if (ParentDecl)
       Result.push_back(ParentDecl);
   }
 
   return Result;
 }
 
-llvm::Optional<TypeHierarchyItem>
+std::vector<TypeHierarchyItem>
 getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
                  TypeHierarchyDirection Direction, const SymbolIndex *Index,
                  PathRef TUPath) {
-  const CXXRecordDecl *CXXRD = findRecordTypeAt(AST, Pos);
-  if (!CXXRD)
-    return llvm::None;
+  std::vector<TypeHierarchyItem> Results;
+  for (const auto *CXXRD : findRecordTypeAt(AST, Pos)) {
 
-  bool WantParents = Direction == TypeHierarchyDirection::Parents ||
-                     Direction == TypeHierarchyDirection::Both;
     bool WantChildren = Direction == TypeHierarchyDirection::Children ||
                         Direction == TypeHierarchyDirection::Both;
 
     // If we're looking for children, we're doing the lookup in the index.
     // The index does not store relationships between implicit
     // specializations, so if we have one, use the template pattern instead.
     // Note that this needs to be done before the declToTypeHierarchyItem(),
     // otherwise the type hierarchy item would misleadingly contain the
     // specialization parameters, while the children would involve classes
     // that derive from other specializations of the template.
     if (WantChildren) {
       if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD))
         CXXRD = CTSD->getTemplateInstantiationPattern();
     }
 
     Optional<TypeHierarchyItem> Result =
         declToTypeHierarchyItem(*CXXRD, AST.tuPath());
     if (!Result)
-    return Result;
-
-  if (WantParents) {
-    Result->parents.emplace();
+      continue;
 
     RecursionProtectionSet RPSet;
-    fillSuperTypes(*CXXRD, AST.tuPath(), *Result->parents, RPSet);
-  }
+    fillSuperTypes(*CXXRD, AST.tuPath(), *Result, RPSet);
 
     if (WantChildren && ResolveLevels > 0) {
       Result->children.emplace();
 
       if (Index) {
         if (auto ID = getSymbolID(CXXRD))
           fillSubTypes(ID, *Result->children, Index, ResolveLevels, TUPath);
       }
     }
+    Results.emplace_back(std::move(*Result));
+  }
 
-  return Result;
+  return Results;
+}
+
+llvm::Optional<std::vector<TypeHierarchyItem>>
+superTypes(const TypeHierarchyItem &Item, const SymbolIndex *Index) {
+  std::vector<TypeHierarchyItem> Results;
+  if (!Item.data.parents)
+    return llvm::None;
+  if (Item.data.parents->empty())
+    return Results;
+  LookupRequest Req;
+  llvm::DenseMap<SymbolID, const TypeHierarchyItem::ResolveParams *> IDToData;
+  for (const auto &Parent : *Item.data.parents) {
+    Req.IDs.insert(Parent.symbolID);
+    IDToData[Parent.symbolID] = &Parent;
+  }
+  Index->lookup(Req, [&Item, &Results, &IDToData](const Symbol &S) {
+    if (auto THI = symbolToTypeHierarchyItem(S, Item.uri.file())) {
+      THI->data = *IDToData.lookup(S.ID);
+      Results.emplace_back(std::move(*THI));
+    }
+  });
+  return Results;
+}
+
+std::vector<TypeHierarchyItem> subTypes(const TypeHierarchyItem &Item,
+                                        const SymbolIndex *Index) {
+  std::vector<TypeHierarchyItem> Results;
+  fillSubTypes(Item.data.symbolID, Results, Index, 1, Item.uri.file());
+  for (auto &ChildSym : Results)
+    ChildSym.data.parents = {Item.data};
+  return Results;
 }
 
 void resolveTypeHierarchy(TypeHierarchyItem &Item, int ResolveLevels,
                           TypeHierarchyDirection Direction,
                           const SymbolIndex *Index) {
   // We only support typeHierarchy/resolve for children, because for parents
   // we ignore ResolveLevels and return all levels of parents eagerly.
-  if (Direction == TypeHierarchyDirection::Parents || ResolveLevels == 0)
+  if (!Index || Direction == TypeHierarchyDirection::Parents ||
+      ResolveLevels == 0)
     return;
 
   Item.children.emplace();
-
-  if (Index && Item.data) {
-    // We store the item's SymbolID in the 'data' field, and the client
-    // passes it back to us in typeHierarchy/resolve.
-    if (Expected<SymbolID> ID = SymbolID::fromStr(*Item.data)) {
-      fillSubTypes(*ID, *Item.children, Index, ResolveLevels, Item.uri.file());
-    }
-  }
+  fillSubTypes(Item.data.symbolID, *Item.children, Index, ResolveLevels,
+               Item.uri.file());
 }
 
 std::vector<CallHierarchyItem>
 prepareCallHierarchy(ParsedAST &AST, Position Pos, PathRef TUPath) {
   std::vector<CallHierarchyItem> Result;
   const auto &SM = AST.getSourceManager();
   auto Loc = sourceLocationInMainFile(SM, Pos);
   if (!Loc) {

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

 # CHECK-NEXT:          ")",
 # CHECK-NEXT:          "{",
 # CHECK-NEXT:          "}",
 # CHECK-NEXT:          "<",
 # CHECK-NEXT:          ">"
 # CHECK-NEXT:          ","
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
+# CHECK-NEXT:      "standardTypeHierarchyProvider": true,
 # CHECK-NEXT:      "textDocumentSync": {
 # CHECK-NEXT:        "change": 2,
 # CHECK-NEXT:        "openClose": true,
 # CHECK-NEXT:        "save": true
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "typeDefinitionProvider": true,
 # CHECK-NEXT:      "typeHierarchyProvider": true
 # CHECK-NEXT:      "workspaceSymbolProvider": true

clang-tools-extra/clangd/test/type-hierarchy-ext.test

 # RUN: clangd -lit-test < %s | FileCheck -strict-whitespace %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:///main.cpp","languageId":"cpp","version":1,"text":"struct Parent {};\nstruct Child1 : Parent {};\nstruct Child2 : Child1 {};\nstruct Child3 : Child2 {};\nstruct Child4 : Child3 {};"}}}
 ---
 {"jsonrpc":"2.0","id":1,"method":"textDocument/typeHierarchy","params":{"textDocument":{"uri":"test:///main.cpp"},"position":{"line":2,"character":11},"direction":2,"resolve":1}}
 #      CHECK:  "id": 1
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "children": [
 # CHECK-NEXT:      {
-# CHECK-NEXT:        "data": "A6576FE083F2949A",
+# CHECK-NEXT:        "data": {
+# CHECK-NEXT:           "symbolID": "A6576FE083F2949A"
+# CHECK-NEXT:        },
 # CHECK-NEXT:        "kind": 23,
 # CHECK-NEXT:        "name": "Child3",
 # CHECK-NEXT:        "range": {
 # CHECK-NEXT:          "end": {
 # CHECK-NEXT:            "character": 13,
 # CHECK-NEXT:            "line": 3
 # CHECK-NEXT:          },
 # CHECK-NEXT:          "start": {

 # CHECK-NEXT:          "start": {
 # CHECK-NEXT:            "character": 7,
 # CHECK-NEXT:            "line": 3
 # CHECK-NEXT:          }
 # CHECK-NEXT:        },
 # CHECK-NEXT:        "uri": "file://{{.*}}/clangd-test/main.cpp"
 # CHECK-NEXT:      }
 # CHECK-NEXT:    ],
-# CHECK-NEXT:    "data": "8A991335E4E67D08",
+# CHECK-NEXT:    "data": {
+# CHECK-NEXT:        "parents": [
+# CHECK-NEXT:         {
+# CHECK-NEXT:          "parents": [
+# CHECK-NEXT:            {
+# CHECK-NEXT:             "parents": [],
+# CHECK-NEXT:             "symbolID": "FE546E7B648D69A7"
+# CHECK-NEXT:            }
+# CHECK-NEXT:          ],
+# CHECK-NEXT:          "symbolID": "ECDC0C46D75120F4"
+# CHECK-NEXT:         }
+# CHECK-NEXT:        ],
+# CHECK-NEXT:        "symbolID": "8A991335E4E67D08"
+# CHECK-NEXT:    },
 # CHECK-NEXT:    "kind": 23,
 # CHECK-NEXT:    "name": "Child2",
 # CHECK-NEXT:    "parents": [
 # CHECK-NEXT:      {
-# CHECK-NEXT:        "data": "ECDC0C46D75120F4",
+# CHECK-NEXT:        "data": {
+# CHECK-NEXT:          "parents": [
+# CHECK-NEXT:            {
+# CHECK-NEXT:             "parents": [],
+# CHECK-NEXT:             "symbolID": "FE546E7B648D69A7"
+# CHECK-NEXT:            }
+# CHECK-NEXT:          ],
+# CHECK-NEXT:          "symbolID": "ECDC0C46D75120F4"
+# CHECK-NEXT:        },
 # CHECK-NEXT:        "kind": 23,
 # CHECK-NEXT:        "name": "Child1",
 # CHECK-NEXT:        "parents": [
 # CHECK-NEXT:          {
-# CHECK-NEXT:            "data": "FE546E7B648D69A7",
+# CHECK-NEXT:            "data": {
+# CHECK-NEXT:             "parents": [],
+# CHECK-NEXT:             "symbolID": "FE546E7B648D69A7"
+# CHECK-NEXT:            },
 # CHECK-NEXT:            "kind": 23,
 # CHECK-NEXT:            "name": "Parent",
 # CHECK-NEXT:            "parents": [],
 # CHECK-NEXT:            "range": {
 # CHECK-NEXT:              "end": {
 # CHECK-NEXT:                "character": 16,
 # CHECK-NEXT:                "line": 0
 # CHECK-NEXT:              },

 # CHECK-NEXT:      "start": {
 # CHECK-NEXT:        "character": 7,
 # CHECK-NEXT:        "line": 2
 # CHECK-NEXT:      }
 # CHECK-NEXT:    },
 # CHECK-NEXT:    "uri": "file://{{.*}}/clangd-test/main.cpp"
 # CHECK-NEXT:  }
 ---
-{"jsonrpc":"2.0","id":2,"method":"typeHierarchy/resolve","params":{"item":{"uri":"test:///main.cpp","data":"A6576FE083F2949A","name":"Child3","kind":23,"range":{"end":{"character":13,"line":3},"start":{"character":7,"line":3}},"selectionRange":{"end":{"character":13,"line":3},"start":{"character":7,"line":3}}},"direction":0,"resolve":1}}
+{"jsonrpc":"2.0","id":2,"method":"typeHierarchy/resolve","params":{"item":{"uri":"test:///main.cpp","data":{"symbolID":"A6576FE083F2949A"},"name":"Child3","kind":23,"range":{"end":{"character":13,"line":3},"start":{"character":7,"line":3}},"selectionRange":{"end":{"character":13,"line":3},"start":{"character":7,"line":3}}},"direction":0,"resolve":1}}
 #      CHECK:  "id": 2
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "children": [
 # CHECK-NEXT:      {
-# CHECK-NEXT:        "data": "5705B382DFC77CBC",
+# CHECK-NEXT:        "data": {
+# CHECK-NEXT:          "symbolID": "5705B382DFC77CBC"
+# CHECK-NEXT:        },
 # CHECK-NEXT:        "kind": 23,
 # CHECK-NEXT:        "name": "Child4",
 # CHECK-NEXT:        "range": {
 # CHECK-NEXT:          "end": {
 # CHECK-NEXT:            "character": 13,
 # CHECK-NEXT:            "line": 4
 # CHECK-NEXT:          },
 # CHECK-NEXT:          "start": {

 # CHECK-NEXT:          "start": {
 # CHECK-NEXT:            "character": 7,
 # CHECK-NEXT:            "line": 4
 # CHECK-NEXT:          }
 # CHECK-NEXT:        },
 # CHECK-NEXT:        "uri": "file://{{.*}}/clangd-test/main.cpp"
 # CHECK-NEXT:      }
 # CHECK-NEXT:    ],
-# CHECK-NEXT:    "data": "A6576FE083F2949A",
+# CHECK-NEXT:    "data": {
+# CHECK-NEXT:      "symbolID": "A6576FE083F2949A"
+# CHECK-NEXT:    },
 # CHECK-NEXT:    "kind": 23,
 # CHECK-NEXT:    "name": "Child3",
 # CHECK-NEXT:    "range": {
 # CHECK-NEXT:      "end": {
 # CHECK-NEXT:        "character": 13,
 # CHECK-NEXT:        "line": 3
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "start": {

clang-tools-extra/clangd/test/type-hierarchy.test

 # RUN: clangd -lit-test < %s | FileCheck -strict-whitespace %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:///main.cpp","languageId":"cpp","version":1,"text":"struct Parent {};\nstruct Child1 : Parent {};\nstruct Child2 : Child1 {};\nstruct Child3 : Child2 {};\nstruct Child4 : Child3 {};"}}}
 ---
-{"jsonrpc":"2.0","id":1,"method":"textDocument/typeHierarchy","params":{"textDocument":{"uri":"test:///main.cpp"},"position":{"line":2,"character":11},"direction":2,"resolve":1}}
+{"jsonrpc":"2.0","id":1,"method":"textDocument/prepareTypeHierarchy","params":{"textDocument":{"uri":"test:///main.cpp"},"position":{"line":2,"character":11},"direction":2,"resolve":1}}
 #      CHECK:  "id": 1
 # CHECK-NEXT:  "jsonrpc": "2.0",
-# CHECK-NEXT:  "result": {
-# CHECK-NEXT:    "children": [
-# CHECK-NEXT:      {
-# CHECK-NEXT:        "data": "A6576FE083F2949A",
-# CHECK-NEXT:        "kind": 23,
-# CHECK-NEXT:        "name": "Child3",
-# CHECK-NEXT:        "range": {
-# CHECK-NEXT:          "end": {
-# CHECK-NEXT:            "character": 13,
-# CHECK-NEXT:            "line": 3
-# CHECK-NEXT:          },
-# CHECK-NEXT:          "start": {
-# CHECK-NEXT:            "character": 7,
-# CHECK-NEXT:            "line": 3
-# CHECK-NEXT:          }
-# CHECK-NEXT:        },
-# CHECK-NEXT:        "selectionRange": {
-# CHECK-NEXT:          "end": {
-# CHECK-NEXT:            "character": 13,
-# CHECK-NEXT:            "line": 3
-# CHECK-NEXT:          },
-# CHECK-NEXT:          "start": {
-# CHECK-NEXT:            "character": 7,
-# CHECK-NEXT:            "line": 3
-# CHECK-NEXT:          }
-# CHECK-NEXT:        },
-# CHECK-NEXT:        "uri": "file://{{.*}}/clangd-test/main.cpp"
-# CHECK-NEXT:      }
-# CHECK-NEXT:    ],
-# CHECK-NEXT:    "data": "8A991335E4E67D08",
-# CHECK-NEXT:    "kind": 23,
-# CHECK-NEXT:    "name": "Child2",
-# CHECK-NEXT:    "parents": [
-# CHECK-NEXT:      {
-# CHECK-NEXT:        "data": "ECDC0C46D75120F4",
-# CHECK-NEXT:        "kind": 23,
-# CHECK-NEXT:        "name": "Child1",
-# CHECK-NEXT:        "parents": [
-# CHECK-NEXT:          {
-# CHECK-NEXT:            "data": "FE546E7B648D69A7",
-# CHECK-NEXT:            "kind": 23,
-# CHECK-NEXT:            "name": "Parent",
-# CHECK-NEXT:            "parents": [],
-# CHECK-NEXT:            "range": {
-# CHECK-NEXT:              "end": {
-# CHECK-NEXT:                "character": 16,
-# CHECK-NEXT:                "line": 0
-# CHECK-NEXT:              },
-# CHECK-NEXT:              "start": {
-# CHECK-NEXT:                "character": 0,
-# CHECK-NEXT:                "line": 0
-# CHECK-NEXT:              }
-# CHECK-NEXT:            },
-# CHECK-NEXT:            "selectionRange": {
-# CHECK-NEXT:              "end": {
-# CHECK-NEXT:                "character": 13,
-# CHECK-NEXT:                "line": 0
-# CHECK-NEXT:              },
-# CHECK-NEXT:              "start": {
-# CHECK-NEXT:                "character": 7,
-# CHECK-NEXT:                "line": 0
-# CHECK-NEXT:              }
-# CHECK-NEXT:            },
-# CHECK-NEXT:            "uri": "file://{{.*}}/clangd-test/main.cpp"
-# CHECK-NEXT:          }
-# CHECK-NEXT:        ],
-# CHECK-NEXT:        "range": {
-# CHECK-NEXT:          "end": {
-# CHECK-NEXT:            "character": 25,
-# CHECK-NEXT:            "line": 1
-# CHECK-NEXT:          },
-# CHECK-NEXT:          "start": {
-# CHECK-NEXT:            "character": 0,
-# CHECK-NEXT:            "line": 1
-# CHECK-NEXT:          }
-# CHECK-NEXT:        },
-# CHECK-NEXT:        "selectionRange": {
-# CHECK-NEXT:          "end": {
-# CHECK-NEXT:            "character": 13,
-# CHECK-NEXT:            "line": 1
-# CHECK-NEXT:          },
-# CHECK-NEXT:          "start": {
-# CHECK-NEXT:            "character": 7,
-# CHECK-NEXT:            "line": 1
-# CHECK-NEXT:          }
-# CHECK-NEXT:        },
-# CHECK-NEXT:        "uri": "file://{{.*}}/clangd-test/main.cpp"
-# CHECK-NEXT:      }
-# CHECK-NEXT:    ],
-# CHECK-NEXT:    "range": {
-# CHECK-NEXT:      "end": {
-# CHECK-NEXT:        "character": 25,
-# CHECK-NEXT:        "line": 2
-# CHECK-NEXT:      },
-# CHECK-NEXT:      "start": {
-# CHECK-NEXT:        "character": 0,
-# CHECK-NEXT:        "line": 2
-# CHECK-NEXT:      }
-# CHECK-NEXT:    },
-# CHECK-NEXT:    "selectionRange": {
-# CHECK-NEXT:      "end": {
-# CHECK-NEXT:        "character": 13,
-# CHECK-NEXT:        "line": 2
-# CHECK-NEXT:      },
-# CHECK-NEXT:      "start": {
-# CHECK-NEXT:        "character": 7,
-# CHECK-NEXT:        "line": 2
-# CHECK-NEXT:      }
-# CHECK-NEXT:    },
-# CHECK-NEXT:    "uri": "file://{{.*}}/clangd-test/main.cpp"
-# CHECK-NEXT:  }
+# CHECK-NEXT:  "result": [
+# CHECK-NEXT:     {
+# CHECK-NEXT:       "data": {
+# CHECK-NEXT:         "parents": [
+# CHECK-NEXT:          {
+# CHECK-NEXT:           "parents": [
+# CHECK-NEXT:             {
+# CHECK-NEXT:              "parents": [],
+# CHECK-NEXT:              "symbolID": "FE546E7B648D69A7"
+# CHECK-NEXT:             }
+# CHECK-NEXT:           ],
+# CHECK-NEXT:           "symbolID": "ECDC0C46D75120F4"
+# CHECK-NEXT:          }
+# CHECK-NEXT:        ],
+# CHECK-NEXT:        "symbolID": "8A991335E4E67D08"
+# CHECK-NEXT:       },
+# CHECK-NEXT:       "kind": 23,
+# CHECK-NEXT:       "name": "Child2",
+# CHECK-NEXT:       "range": {
+# CHECK-NEXT:         "end": {
+# CHECK-NEXT:           "character": 25,
+# CHECK-NEXT:           "line": 2
+# CHECK-NEXT:         },
+# CHECK-NEXT:         "start": {
+# CHECK-NEXT:           "character": 0,
+# CHECK-NEXT:           "line": 2
+# CHECK-NEXT:         }
+# CHECK-NEXT:       },
+# CHECK-NEXT:       "selectionRange": {
+# CHECK-NEXT:         "end": {
+# CHECK-NEXT:           "character": 13,
+# CHECK-NEXT:           "line": 2
+# CHECK-NEXT:         },
+# CHECK-NEXT:         "start": {
+# CHECK-NEXT:           "character": 7,
+# CHECK-NEXT:           "line": 2
+# CHECK-NEXT:         }
+# CHECK-NEXT:       },
+# CHECK-NEXT:       "uri": "file://{{.*}}/clangd-test/main.cpp"
+# CHECK-NEXT:     }
+# CHECK-NEXT:   ]
 ---
-{"jsonrpc":"2.0","id":2,"method":"typeHierarchy/resolve","params":{"item":{"uri":"test:///main.cpp","data":"A6576FE083F2949A","name":"Child3","kind":23,"range":{"end":{"character":13,"line":3},"start":{"character":7,"line":3}},"selectionRange":{"end":{"character":13,"line":3},"start":{"character":7,"line":3}}},"direction":0,"resolve":1}}
+{"jsonrpc":"2.0","id":2,"method":"typeHierarchy/supertypes","params":{"item":{"uri":"test:///main.cpp","data":{"parents":[{"parents":[{"parents":[],"symbolID":"FE546E7B648D69A7"}],"symbolID":"ECDC0C46D75120F4"}],"symbolID":"8A991335E4E67D08"},"name":"Child2","kind":23,"range":{"end":{"character":13,"line":3},"start":{"character":7,"line":3}},"selectionRange":{"end":{"character":13,"line":3},"start":{"character":7,"line":3}}}}}
 #      CHECK:  "id": 2
 # CHECK-NEXT:  "jsonrpc": "2.0",
-# CHECK-NEXT:  "result": {
-# CHECK-NEXT:    "children": [
-# CHECK-NEXT:      {
-# CHECK-NEXT:        "data": "5705B382DFC77CBC",
-# CHECK-NEXT:        "kind": 23,
-# CHECK-NEXT:        "name": "Child4",
-# CHECK-NEXT:        "range": {
-# CHECK-NEXT:          "end": {
-# CHECK-NEXT:            "character": 13,
-# CHECK-NEXT:            "line": 4
-# CHECK-NEXT:          },
-# CHECK-NEXT:          "start": {
-# CHECK-NEXT:            "character": 7,
-# CHECK-NEXT:            "line": 4
-# CHECK-NEXT:          }
-# CHECK-NEXT:        },
-# CHECK-NEXT:        "selectionRange": {
-# CHECK-NEXT:          "end": {
-# CHECK-NEXT:            "character": 13,
-# CHECK-NEXT:            "line": 4
-# CHECK-NEXT:          },
-# CHECK-NEXT:          "start": {
-# CHECK-NEXT:            "character": 7,
-# CHECK-NEXT:            "line": 4
-# CHECK-NEXT:          }
-# CHECK-NEXT:        },
-# CHECK-NEXT:        "uri": "file://{{.*}}/clangd-test/main.cpp"
-# CHECK-NEXT:      }
-# CHECK-NEXT:    ],
-# CHECK-NEXT:    "data": "A6576FE083F2949A",
-# CHECK-NEXT:    "kind": 23,
-# CHECK-NEXT:    "name": "Child3",
-# CHECK-NEXT:    "range": {
-# CHECK-NEXT:      "end": {
-# CHECK-NEXT:        "character": 13,
-# CHECK-NEXT:        "line": 3
-# CHECK-NEXT:      },
-# CHECK-NEXT:      "start": {
-# CHECK-NEXT:        "character": 7,
-# CHECK-NEXT:        "line": 3
-# CHECK-NEXT:      }
-# CHECK-NEXT:    },
-# CHECK-NEXT:    "selectionRange": {
-# CHECK-NEXT:      "end": {
-# CHECK-NEXT:        "character": 13,
-# CHECK-NEXT:        "line": 3
-# CHECK-NEXT:      },
-# CHECK-NEXT:      "start": {
-# CHECK-NEXT:        "character": 7,
-# CHECK-NEXT:        "line": 3
-# CHECK-NEXT:      }
-# CHECK-NEXT:    },
-# CHECK-NEXT:    "uri": "file://{{.*}}/clangd-test/main.cpp"
-# CHECK-NEXT:  }
+# CHECK-NEXT:  "result": [
+# CHECK-NEXT:     {
+# CHECK-NEXT:       "data": {
+# CHECK-NEXT:         "parents": [
+# CHECK-NEXT:           {
+# CHECK-NEXT:            "parents": [],
+# CHECK-NEXT:            "symbolID": "FE546E7B648D69A7"
+# CHECK-NEXT:           }
+# CHECK-NEXT:         ],
+# CHECK-NEXT:         "symbolID": "ECDC0C46D75120F4"
+# CHECK-NEXT:       },
+# CHECK-NEXT:       "kind": 23,
+# CHECK-NEXT:       "name": "Child1",
+# CHECK-NEXT:       "range": {
+# CHECK-NEXT:         "end": {
+# CHECK-NEXT:           "character": 13,
+# CHECK-NEXT:           "line": 1
+# CHECK-NEXT:         },
+# CHECK-NEXT:         "start": {
+# CHECK-NEXT:           "character": 7,
+# CHECK-NEXT:           "line": 1
+# CHECK-NEXT:         }
+# CHECK-NEXT:       },
+# CHECK-NEXT:       "selectionRange": {
+# CHECK-NEXT:         "end": {
+# CHECK-NEXT:           "character": 13,
+# CHECK-NEXT:           "line": 1
+# CHECK-NEXT:         },
+# CHECK-NEXT:         "start": {
+# CHECK-NEXT:           "character": 7,
+# CHECK-NEXT:           "line": 1
+# CHECK-NEXT:         }
+# CHECK-NEXT:       },
+# CHECK-NEXT:       "uri": "file://{{.*}}/clangd-test/main.cpp"
+# CHECK-NEXT:     }
+# CHECK-NEXT:  ]
+---
+{"jsonrpc":"2.0","id":2,"method":"typeHierarchy/subtypes","params":{"item":{"uri":"test:///main.cpp","data":{"parents":[{"parents":[{"parents":[],"symbolID":"FE546E7B648D69A7"}],"symbolID":"ECDC0C46D75120F4"}],"symbolID":"8A991335E4E67D08"},"name":"Child2","kind":23,"range":{"end":{"character":13,"line":3},"start":{"character":7,"line":3}},"selectionRange":{"end":{"character":13,"line":3},"start":{"character":7,"line":3}}}}}
+#      CHECK:  "id": 2
+# CHECK-NEXT:  "jsonrpc": "2.0",
+# CHECK-NEXT:  "result": [
+# CHECK-NEXT:     {
+# CHECK-NEXT:       "data": {
+# CHECK-NEXT:         "parents": [
+# CHECK-NEXT:          {
+# CHECK-NEXT:           "parents": [
+# CHECK-NEXT:            {
+# CHECK-NEXT:             "parents": [
+# CHECK-NEXT:               {
+# CHECK-NEXT:                "parents": [],
+# CHECK-NEXT:                "symbolID": "FE546E7B648D69A7"
+# CHECK-NEXT:               }
+# CHECK-NEXT:             ],
+# CHECK-NEXT:             "symbolID": "ECDC0C46D75120F4"
+# CHECK-NEXT:            }
+# CHECK-NEXT:           ],
+# CHECK-NEXT:           "symbolID": "8A991335E4E67D08"
+# CHECK-NEXT:         }
+# CHECK-NEXT:        ],
+# CHECK-NEXT:        "symbolID": "A6576FE083F2949A"
+# CHECK-NEXT:       },
+# CHECK-NEXT:       "kind": 23,
+# CHECK-NEXT:       "name": "Child3",
+# CHECK-NEXT:       "range": {
+# CHECK-NEXT:         "end": {
+# CHECK-NEXT:           "character": 13,
+# CHECK-NEXT:           "line": 3
+# CHECK-NEXT:         },
+# CHECK-NEXT:         "start": {
+# CHECK-NEXT:           "character": 7,
+# CHECK-NEXT:           "line": 3
+# CHECK-NEXT:         }
+# CHECK-NEXT:       },
+# CHECK-NEXT:       "selectionRange": {
+# CHECK-NEXT:         "end": {
+# CHECK-NEXT:           "character": 13,
+# CHECK-NEXT:           "line": 3
+# CHECK-NEXT:         },
+# CHECK-NEXT:         "start": {
+# CHECK-NEXT:           "character": 7,
+# CHECK-NEXT:           "line": 3
+# CHECK-NEXT:         }
+# CHECK-NEXT:       },
+# CHECK-NEXT:       "uri": "file://{{.*}}/clangd-test/main.cpp"
+# CHECK-NEXT:     }
+# CHECK-NEXT:  ]
 ---
 {"jsonrpc":"2.0","id":3,"method":"shutdown"}
 ---
 {"jsonrpc":"2.0","method":"exit"}

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

 //===-- TypeHierarchyTests.cpp  ---------------------------*- 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 "AST.h"
 #include "Annotations.h"
 #include "Matchers.h"
 #include "ParsedAST.h"
 #include "TestFS.h"
 #include "TestTU.h"
 #include "XRefs.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclTemplate.h"
 #include "llvm/Support/Path.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include <vector>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 using ::testing::AllOf;
 using ::testing::ElementsAre;
 using ::testing::Field;
 using ::testing::IsEmpty;
 using ::testing::Matcher;
+using ::testing::SizeIs;
 using ::testing::UnorderedElementsAre;
 
 // GMock helpers for matching TypeHierarchyItem.
 MATCHER_P(withName, N, "") { return arg.name == N; }
 MATCHER_P(withKind, Kind, "") { return arg.kind == Kind; }
 MATCHER_P(selectionRangeIs, R, "") { return arg.selectionRange == R; }
 template <class... ParentMatchers>
 ::testing::Matcher<TypeHierarchyItem> parents(ParentMatchers... ParentsM) {
   return Field(&TypeHierarchyItem::parents,
                HasValue(UnorderedElementsAre(ParentsM...)));
 }
 template <class... ChildMatchers>
 ::testing::Matcher<TypeHierarchyItem> children(ChildMatchers... ChildrenM) {
   return Field(&TypeHierarchyItem::children,
                HasValue(UnorderedElementsAre(ChildrenM...)));
 }
 // Note: "not resolved" is different from "resolved but empty"!
 MATCHER(parentsNotResolved, "") { return !arg.parents; }
 MATCHER(childrenNotResolved, "") { return !arg.children; }
+MATCHER_P(withResolveID, SID, "") { return arg.symbolID.str() == SID; }
+MATCHER_P(withResolveParents, M, "") {
+  return testing::ExplainMatchResult(M, arg.data.parents, result_listener);
+}
 
 TEST(FindRecordTypeAt, TypeOrVariable) {
   Annotations Source(R"cpp(
 struct Ch^ild2 {
   int c;
 };
 
 using A^lias = Child2;
 
 int main() {
   Ch^ild2 ch^ild2;
   ch^ild2.c = 1;
 }
 )cpp");
 
   TestTU TU = TestTU::withCode(Source.code());
   auto AST = TU.build();
 
   for (Position Pt : Source.points()) {
-    const CXXRecordDecl *RD = findRecordTypeAt(AST, Pt);
-    EXPECT_EQ(&findDecl(AST, "Child2"), static_cast<const NamedDecl *>(RD));
+    auto Records = findRecordTypeAt(AST, Pt);
+    ASSERT_THAT(Records, SizeIs(1));
+    EXPECT_EQ(&findDecl(AST, "Child2"),
+              static_cast<const NamedDecl *>(Records.front()));
   }
 }
 
 TEST(FindRecordTypeAt, Method) {
   Annotations Source(R"cpp(
 struct Child2 {
   void met^hod ();
   void met^hod (int x);
 };
 
 int main() {
   Child2 child2;
   child2.met^hod(5);
 }
 )cpp");
 
   TestTU TU = TestTU::withCode(Source.code());
   auto AST = TU.build();
 
   for (Position Pt : Source.points()) {
-    const CXXRecordDecl *RD = findRecordTypeAt(AST, Pt);
-    EXPECT_EQ(&findDecl(AST, "Child2"), static_cast<const NamedDecl *>(RD));
+    auto Records = findRecordTypeAt(AST, Pt);
+    ASSERT_THAT(Records, SizeIs(1));
+    EXPECT_EQ(&findDecl(AST, "Child2"),
+              static_cast<const NamedDecl *>(Records.front()));
   }
 }
 
 TEST(FindRecordTypeAt, Field) {
   Annotations Source(R"cpp(
 struct Child2 {
   int fi^eld;
 };
 
 int main() {
   Child2 child2;
   child2.fi^eld = 5;
 }
 )cpp");
 
   TestTU TU = TestTU::withCode(Source.code());
   auto AST = TU.build();
 
   for (Position Pt : Source.points()) {
-    const CXXRecordDecl *RD = findRecordTypeAt(AST, Pt);
     // A field does not unambiguously specify a record type
     // (possible associated reocrd types could be the field's type,
     // or the type of the record that the field is a member of).
-    EXPECT_EQ(nullptr, RD);
+    EXPECT_THAT(findRecordTypeAt(AST, Pt), SizeIs(0));
   }
 }
 
 TEST(TypeParents, SimpleInheritance) {
   Annotations Source(R"cpp(
 struct Parent {
   int a;
 };

 )cpp");
 
   TestTU TU = TestTU::withCode(Source.code());
   auto AST = TU.build();
 
   for (Position Pt : Source.points()) {
     // Set ResolveLevels to 0 because it's only used for Children;
     // for Parents, getTypeHierarchy() always returns all levels.
-    llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
-        AST, Pt, /*ResolveLevels=*/0, TypeHierarchyDirection::Parents);
-    ASSERT_TRUE(bool(Result));
+    auto Result = getTypeHierarchy(AST, Pt, /*ResolveLevels=*/0,
+                                   TypeHierarchyDirection::Parents);
+    ASSERT_THAT(Result, SizeIs(1));
     EXPECT_THAT(
-        *Result,
+        Result.front(),
         AllOf(
             withName("Child"), withKind(SymbolKind::Struct),
             parents(AllOf(withName("Parent1"), withKind(SymbolKind::Struct),
                           selectionRangeIs(Source.range("Parent1Def")),
                           parents()),
                     AllOf(withName("Parent3"), withKind(SymbolKind::Struct),
                           selectionRangeIs(Source.range("Parent3Def")),
                           parents(AllOf(
TEST(TypeHierarchy, RecursiveHierarchyUnbounded) {
   // The compiler should produce a diagnostic for hitting the
   // template instantiation depth.
   ASSERT_TRUE(!AST.getDiagnostics()->empty());
 
   // Make sure getTypeHierarchy() doesn't get into an infinite recursion.
   // The parent is reported as "S" because "S<0>" is an invalid instantiation.
   // We then iterate once more and find "S" again before detecting the
   // recursion.
-  llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
-      AST, Source.points()[0], 0, TypeHierarchyDirection::Parents);
-  ASSERT_TRUE(bool(Result));
+  auto Result = getTypeHierarchy(AST, Source.points()[0], 0,
+                                 TypeHierarchyDirection::Parents);
+  ASSERT_THAT(Result, SizeIs(1));
   EXPECT_THAT(
-      *Result,
+      Result.front(),
       AllOf(withName("S<0>"), withKind(SymbolKind::Struct),
             parents(
                 AllOf(withName("S"), withKind(SymbolKind::Struct),
                       selectionRangeIs(Source.range("SDef")),
                       parents(AllOf(withName("S"), withKind(SymbolKind::Struct),
                                     selectionRangeIs(Source.range("SDef")),
                                     parents()))))));
 }
struct Foo {
     S$SRefDependent^<N> s;
   };)cpp");
 
   TestTU TU = TestTU::withCode(Source.code());
   auto AST = TU.build();
 
   // Make sure getTypeHierarchy() doesn't get into an infinite recursion
   // for either a concrete starting point or a dependent starting point.
-  llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
-      AST, Source.point("SRefConcrete"), 0, TypeHierarchyDirection::Parents);
-  ASSERT_TRUE(bool(Result));
+  auto Result = getTypeHierarchy(AST, Source.point("SRefConcrete"), 0,
+                                 TypeHierarchyDirection::Parents);
+  ASSERT_THAT(Result, SizeIs(1));
   EXPECT_THAT(
-      *Result,
+      Result.front(),
       AllOf(withName("S<2>"), withKind(SymbolKind::Struct),
             parents(AllOf(
                 withName("S<1>"), withKind(SymbolKind::Struct),
                 selectionRangeIs(Source.range("SDef")),
                 parents(AllOf(withName("S<0>"), withKind(SymbolKind::Struct),
                               parents()))))));
   Result = getTypeHierarchy(AST, Source.point("SRefDependent"), 0,
                             TypeHierarchyDirection::Parents);
-  ASSERT_TRUE(bool(Result));
+  ASSERT_THAT(Result, SizeIs(1));
   EXPECT_THAT(
-      *Result,
+      Result.front(),
       AllOf(withName("S"), withKind(SymbolKind::Struct),
             parents(AllOf(withName("S"), withKind(SymbolKind::Struct),
                           selectionRangeIs(Source.range("SDef")), parents()))));
 }
 
 TEST(TypeHierarchy, DeriveFromImplicitSpec) {
   Annotations Source(R"cpp(
   template <typename T>
   struct Parent {};
 
   struct Child1 : Parent<int> {};
 
   struct Child2 : Parent<char> {};
 
   Parent<int> Fo^o;
   )cpp");
 
   TestTU TU = TestTU::withCode(Source.code());
   auto AST = TU.build();
   auto Index = TU.index();
 
-  llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
-      AST, Source.points()[0], 2, TypeHierarchyDirection::Children, Index.get(),
+  auto Result = getTypeHierarchy(AST, Source.points()[0], 2,
+                                 TypeHierarchyDirection::Children, Index.get(),
                                  testPath(TU.Filename));
-  ASSERT_TRUE(bool(Result));
-  EXPECT_THAT(*Result,
+  ASSERT_THAT(Result, SizeIs(1));
+  EXPECT_THAT(Result.front(),
               AllOf(withName("Parent"), withKind(SymbolKind::Struct),
                     children(AllOf(withName("Child1"),
                                    withKind(SymbolKind::Struct), children()),
                              AllOf(withName("Child2"),
                                    withKind(SymbolKind::Struct), children()))));
 }
 
 TEST(TypeHierarchy, DeriveFromPartialSpec) {
   Annotations Source(R"cpp(
   template <typename T> struct Parent {};
   template <typename T> struct Parent<T*> {};
 
   struct Child : Parent<int*> {};
 
   Parent<int> Fo^o;
   )cpp");
 
   TestTU TU = TestTU::withCode(Source.code());
   auto AST = TU.build();
   auto Index = TU.index();
 
-  llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
-      AST, Source.points()[0], 2, TypeHierarchyDirection::Children, Index.get(),
+  auto Result = getTypeHierarchy(AST, Source.points()[0], 2,
+                                 TypeHierarchyDirection::Children, Index.get(),
                                  testPath(TU.Filename));
-  ASSERT_TRUE(bool(Result));
-  EXPECT_THAT(*Result, AllOf(withName("Parent"), withKind(SymbolKind::Struct),
-                             children()));
+  ASSERT_THAT(Result, SizeIs(1));
+  EXPECT_THAT(Result.front(), AllOf(withName("Parent"),
+                                    withKind(SymbolKind::Struct), children()));
 }
 
 TEST(TypeHierarchy, DeriveFromTemplate) {
   Annotations Source(R"cpp(
   template <typename T>
   struct Parent {};
 
   template <typename T>
   struct Child : Parent<T> {};
 
   Parent<int> Fo^o;
   )cpp");
 
   TestTU TU = TestTU::withCode(Source.code());
   auto AST = TU.build();
   auto Index = TU.index();
 
   // FIXME: We'd like this to show the implicit specializations Parent<int>
   //        and Child<int>, but currently libIndex does not expose relationships
   //        between implicit specializations.
-  llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
-      AST, Source.points()[0], 2, TypeHierarchyDirection::Children, Index.get(),
+  auto Result = getTypeHierarchy(AST, Source.points()[0], 2,
+                                 TypeHierarchyDirection::Children, Index.get(),
                                  testPath(TU.Filename));
-  ASSERT_TRUE(bool(Result));
-  EXPECT_THAT(*Result,
+  ASSERT_THAT(Result, SizeIs(1));
+  EXPECT_THAT(Result.front(),
               AllOf(withName("Parent"), withKind(SymbolKind::Struct),
                     children(AllOf(withName("Child"),
                                    withKind(SymbolKind::Struct), children()))));
 }
 
 TEST(TypeHierarchy, Preamble) {
   Annotations SourceAnnotations(R"cpp(
 struct Ch^ild : Parent {
   int b;
 };)cpp");
 
   Annotations HeaderInPreambleAnnotations(R"cpp(
 struct [[Parent]] {
   int a;
 };)cpp");
 
   TestTU TU = TestTU::withCode(SourceAnnotations.code());
   TU.HeaderCode = HeaderInPreambleAnnotations.code().str();
   auto AST = TU.build();
 
-  llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
+  std::vector<TypeHierarchyItem> Result = getTypeHierarchy(
       AST, SourceAnnotations.point(), 1, TypeHierarchyDirection::Parents);
 
-  ASSERT_TRUE(Result);
+  ASSERT_THAT(Result, SizeIs(1));
   EXPECT_THAT(
-      *Result,
+      Result.front(),
       AllOf(withName("Child"),
             parents(AllOf(withName("Parent"),
                           selectionRangeIs(HeaderInPreambleAnnotations.range()),
                           parents()))));
 }
 
 SymbolID findSymbolIDByName(SymbolIndex *Index, llvm::StringRef Name,
                             llvm::StringRef TemplateArgs = "") {

 struct Child2a : Child1 {};
 struct Child2b : Child1 {};
 )cpp");
 
   TestTU TU = TestTU::withCode(Source.code());
   auto AST = TU.build();
   auto Index = TU.index();
 
-  llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
-      AST, Source.point(), /*ResolveLevels=*/1,
-      TypeHierarchyDirection::Children, Index.get(), testPath(TU.Filename));
-  ASSERT_TRUE(bool(Result));
+  auto Result = getTypeHierarchy(AST, Source.point(), /*ResolveLevels=*/1,
+                                 TypeHierarchyDirection::Children, Index.get(),
+                                 testPath(TU.Filename));
+  ASSERT_THAT(Result, SizeIs(1));
   EXPECT_THAT(
-      *Result,
-      AllOf(withName("Parent"), withKind(SymbolKind::Struct),
-            parentsNotResolved(),
+      Result.front(),
+      AllOf(withName("Parent"), withKind(SymbolKind::Struct), parents(),
             children(AllOf(withName("Child1"), withKind(SymbolKind::Struct),
                            parentsNotResolved(), childrenNotResolved()))));
 
-  resolveTypeHierarchy((*Result->children)[0], /*ResolveLevels=*/1,
+  resolveTypeHierarchy((*Result.front().children)[0], /*ResolveLevels=*/1,
                        TypeHierarchyDirection::Children, Index.get());
 
   EXPECT_THAT(
-      (*Result->children)[0],
+      (*Result.front().children)[0],
       AllOf(withName("Child1"), withKind(SymbolKind::Struct),
             parentsNotResolved(),
             children(AllOf(withName("Child2a"), withKind(SymbolKind::Struct),
                            parentsNotResolved(), childrenNotResolved()),
                      AllOf(withName("Child2b"), withKind(SymbolKind::Struct),
                            parentsNotResolved(), childrenNotResolved()))));
 }
 
+TEST(Standard, SubTypes) {
+  Annotations Source(R"cpp(
+struct Pare^nt1 {};
+struct Parent2 {};
+struct Child : Parent1, Parent2 {};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+  auto Index = TU.index();
+
+  auto Result = getTypeHierarchy(AST, Source.point(), /*ResolveLevels=*/1,
+                                 TypeHierarchyDirection::Children, Index.get(),
+                                 testPath(TU.Filename));
+  ASSERT_THAT(Result, SizeIs(1));
+  auto Children = subTypes(Result.front(), Index.get());
+
+  // Make sure parents are populated when getting children.
+  // FIXME: This is partial.
+  EXPECT_THAT(
+      Children,
+      UnorderedElementsAre(
+          AllOf(withName("Child"),
+                withResolveParents(HasValue(UnorderedElementsAre(withResolveID(
+                    getSymbolID(&findDecl(AST, "Parent1")).str())))))));
+}
+
+TEST(Standard, SuperTypes) {
+  Annotations Source(R"cpp(
+struct Parent {};
+struct Chil^d : Parent {};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+  auto Index = TU.index();
+
+  auto Result = getTypeHierarchy(AST, Source.point(), /*ResolveLevels=*/1,
+                                 TypeHierarchyDirection::Children, Index.get(),
+                                 testPath(TU.Filename));
+  ASSERT_THAT(Result, SizeIs(1));
+  auto Parents = superTypes(Result.front(), Index.get());
+
+  EXPECT_THAT(Parents, HasValue(UnorderedElementsAre(
+                           AllOf(withName("Parent"),
+                                 withResolveParents(HasValue(IsEmpty()))))));
+}
 } // namespace
 } // namespace clangd
 } // namespace clang