[clangd] Implement typeHierarchy/resolve for subtypes

[nridge]

Summary

This allows the client to resolve subtypes one level at a time.

For supertypes, this is not necessary, because we eagerly compute
supertypes and return all levels.

[nridge]

This was an oversight on my part: I forgot that, when we didn't implement typeHierarchy/resolve, it was only supertypes that didn't need it; subtypes do.

[sammccall]

Thanks, I forgot we hadn't hooked this part up!

clang-tools-extra/clangd/XRefs.cpp

1222 ↗

(On Diff #208318)

I think this should just return Item.
We're supposed to return null if the item is no longer valid, but AFAICT not if it's valid but already fully resolved.

Since we don't actually detect invalidity (e.g. when the location is no longer valid), I'd suggest just making all the functions here return TypeHierarchyItem rather than Optional (or take a mutable reference for this one, which is synchronous)

clang-tools-extra/clangd/XRefs.h

144 ↗

(On Diff #208318)

const TypeHierarchyItem &Item

(or mutable ref as suggested in the other comment, and return void)

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

1 ↗

(On Diff #208318)

Please add a unit test to TypeHierarchyTests.

I'm on the fence about having a lit test: it's a new LSP method, though the binding is pretty simple.
But features that are only covered by lit tests are too painful to maintain.

[nridge]

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

1 ↗

(On Diff #208318)

As I've already written the lit test, I think there's little harm in keeping it.

[nridge]

This was backed out due to a Windows test failure. Seems to be related to the hint path having a different format on Windows. I guess I should not hard-code it, but get it from the TestTU.

[sammccall]

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

629

yes, this should be testPath(TU.Filename)

(TU.Filename is always unix-style relative path, testPath() makes it an OS-style absolute path)

[sammccall]

(Thanks for writing the test, and sorry for the hassle it caused!)

[nridge]

Fix Windows test failure

clang-tools-extra/trunk/clangd/ClangdLSPServer.h

private:
   void onCommand(const ExecuteCommandParams &, Callback<llvm::json::Value>);
   void onWorkspaceSymbol(const WorkspaceSymbolParams &,
                          Callback<std::vector<SymbolInformation>>);
   void onRename(const RenameParams &, Callback<WorkspaceEdit>);
   void onHover(const TextDocumentPositionParams &,
                Callback<llvm::Optional<Hover>>);
   void onTypeHierarchy(const TypeHierarchyParams &,
                        Callback<llvm::Optional<TypeHierarchyItem>>);
+  void onResolveTypeHierarchy(const ResolveTypeHierarchyItemParams &,
+                              Callback<llvm::Optional<TypeHierarchyItem>>);
   void onChangeConfiguration(const DidChangeConfigurationParams &);
   void onSymbolInfo(const TextDocumentPositionParams &,
                     Callback<std::vector<SymbolDetails>>);
 
   std::vector<Fix> getFixes(StringRef File, const clangd::Diagnostic &D);
 
   /// Checks if completion request should be ignored. We need this due to the
   /// limitation of the LSP. Per LSP, a client sends requests for all "trigger

clang-tools-extra/trunk/clangd/ClangdLSPServer.cpp

 
 void ClangdLSPServer::onTypeHierarchy(
     const TypeHierarchyParams &Params,
     Callback<Optional<TypeHierarchyItem>> Reply) {
   Server->typeHierarchy(Params.textDocument.uri.file(), Params.position,
                         Params.resolve, Params.direction, std::move(Reply));
 }
 
+void ClangdLSPServer::onResolveTypeHierarchy(
+    const ResolveTypeHierarchyItemParams &Params,
+    Callback<Optional<TypeHierarchyItem>> Reply) {
+  Server->resolveTypeHierarchy(Params.item, Params.resolve, Params.direction,
+                               std::move(Reply));
+}
+
 void ClangdLSPServer::applyConfiguration(
     const ConfigurationSettings &Settings) {
   // Per-file update to the compilation database.
   bool ShouldReparseOpenFiles = false;
   for (auto &Entry : Settings.compilationDatabaseChanges) {
     /// The opened files need to be reparsed only when some existing
     /// entries are changed.
     PathRef File = Entry.first;
ClangdLSPServer::ClangdLSPServer(
   MsgHandler->bind("workspace/symbol", &ClangdLSPServer::onWorkspaceSymbol);
   MsgHandler->bind("textDocument/didOpen", &ClangdLSPServer::onDocumentDidOpen);
   MsgHandler->bind("textDocument/didClose", &ClangdLSPServer::onDocumentDidClose);
   MsgHandler->bind("textDocument/didChange", &ClangdLSPServer::onDocumentDidChange);
   MsgHandler->bind("workspace/didChangeWatchedFiles", &ClangdLSPServer::onFileEvent);
   MsgHandler->bind("workspace/didChangeConfiguration", &ClangdLSPServer::onChangeConfiguration);
   MsgHandler->bind("textDocument/symbolInfo", &ClangdLSPServer::onSymbolInfo);
   MsgHandler->bind("textDocument/typeHierarchy", &ClangdLSPServer::onTypeHierarchy);
+  MsgHandler->bind("typeHierarchy/resolve", &ClangdLSPServer::onResolveTypeHierarchy);
   // clang-format on
 }
 
 ClangdLSPServer::~ClangdLSPServer() = default;
 
 bool ClangdLSPServer::run() {
   // Run the Language Server loop.
   bool CleanExit = true;

clang-tools-extra/trunk/clangd/ClangdServer.h

struct Options {
     /// Clangd will execute compiler drivers matching one of these globs to
     /// fetch system include path.
     std::vector<std::string> QueryDriverGlobs;
 
     /// Enable semantic highlighting features.
     bool SemanticHighlighting = false;
 
     /// Returns true if the StringRef is a tweak that should be enabled
-    std::function<bool(llvm::StringRef)> TweakFilter = [](llvm::StringRef TweakToSearch) {return true;};
+    std::function<bool(llvm::StringRef)> TweakFilter =
+        [](llvm::StringRef TweakToSearch) { return true; };
   };
   // Sensible default options for use in tests.
   // Features like indexing must be enabled if desired.
   static Options optsForTest();
 
   /// Creates a new ClangdServer instance.
   ///
   /// ClangdServer uses \p CDB to obtain compilation arguments for parsing. Note
public:
   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);
 
+  /// Resolve type hierarchy item in the given direction.
+  void resolveTypeHierarchy(TypeHierarchyItem Item, int Resolve,
+                            TypeHierarchyDirection Direction,
+                            Callback<llvm::Optional<TypeHierarchyItem>> CB);
+
   /// Retrieve the top symbols from the workspace matching a query.
   void workspaceSymbols(StringRef Query, int Limit,
                         Callback<std::vector<SymbolInformation>> CB);
 
   /// Retrieve the symbols within the specified file.
   void documentSymbols(StringRef File,
                        Callback<std::vector<DocumentSymbol>> CB);
 
private:
 
   // When set, provides clang-tidy options for a specific file.
   ClangTidyOptionsBuilder GetClangTidyOptions;
 
   // If this is true, suggest include insertion fixes for diagnostic errors that
   // can be caused by missing includes (e.g. member access in incomplete type).
   bool SuggestMissingIncludes = false;
   bool EnableHiddenFeatures = false;
-   
   std::function<bool(llvm::StringRef)> TweakFilter;
 
   // GUARDED_BY(CachedCompletionFuzzyFindRequestMutex)
   llvm::StringMap<llvm::Optional<FuzzyFindRequest>>
       CachedCompletionFuzzyFindRequestByFile;
   mutable std::mutex CachedCompletionFuzzyFindRequestMutex;
 
   llvm::Optional<std::string> WorkspaceRoot;

clang-tools-extra/trunk/clangd/ClangdServer.cpp

ClangdServer::ClangdServer(const GlobalCompilationDatabase &CDB,
                            DiagnosticsConsumer &DiagConsumer,
                            const Options &Opts)
     : FSProvider(FSProvider),
       DynamicIdx(Opts.BuildDynamicSymbolIndex
                      ? new FileIndex(Opts.HeavyweightDynamicSymbolIndex)
                      : nullptr),
       GetClangTidyOptions(Opts.GetClangTidyOptions),
       SuggestMissingIncludes(Opts.SuggestMissingIncludes),
-      EnableHiddenFeatures(Opts.HiddenFeatures),
-      TweakFilter(Opts.TweakFilter),
+      EnableHiddenFeatures(Opts.HiddenFeatures), TweakFilter(Opts.TweakFilter),
       WorkspaceRoot(Opts.WorkspaceRoot),
       // Pass a callback into `WorkScheduler` to extract symbols from a newly
       // parsed file and rebuild the file index synchronously each time an AST
       // is parsed.
       // FIXME(ioeric): this can be slow and we may be able to index on less
       // critical paths.
       WorkScheduler(
           CDB, Opts.AsyncThreadsCount, Opts.StorePreamblesInMemory,
if (!InpAST)
       return CB(InpAST.takeError());
     CB(clangd::getTypeHierarchy(InpAST->AST, Pos, Resolve, Direction, Index,
                                 FileCopy));
   };
 
   WorkScheduler.runWithAST("Type Hierarchy", File, Bind(Action, std::move(CB)));
 }
 
+void ClangdServer::resolveTypeHierarchy(
+    TypeHierarchyItem Item, int Resolve, TypeHierarchyDirection Direction,
+    Callback<llvm::Optional<TypeHierarchyItem>> CB) {
+  clangd::resolveTypeHierarchy(Item, Resolve, Direction, Index);
+  CB(Item);
+}
+
 void ClangdServer::onFileEvent(const DidChangeWatchedFilesParams &Params) {
   // FIXME: Do nothing for now. This will be used for indexing and potentially
   // invalidating other caches.
 }
 
 void ClangdServer::workspaceSymbols(
     llvm::StringRef Query, int Limit,
     Callback<std::vector<SymbolInformation>> CB) {

clang-tools-extra/trunk/clangd/Protocol.h

struct TypeHierarchyItem {
   /// 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.
   SymbolKind kind;
 
   /// `true` if the hierarchy item is deprecated. Otherwise, `false`.
-  bool deprecated;
+  bool deprecated = false;
 
   /// The URI of the text document where this type hierarchy item belongs to.
   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.
struct TypeHierarchyItem {
   /// the parents have not been resolved yet.
   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.
   llvm::Optional<std::vector<TypeHierarchyItem>> children;
 
-  /// The protocol has a slot here for an optional 'data' filed, which can
-  /// be used to identify a type hierarchy item in a resolve request. We don't
-  /// need this (the item itself is sufficient to identify what to resolve)
-  /// so don't declare it.
+  /// An optional 'data' filed, 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 &);
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const TypeHierarchyItem &);
+bool fromJSON(const llvm::json::Value &, TypeHierarchyItem &);
+
+/// Parameters for the `typeHierarchy/resolve` request.
+struct ResolveTypeHierarchyItemParams {
+  /// The item to resolve.
+  TypeHierarchyItem item;
+
+  /// The hierarchy levels to resolve. `0` indicates no level.
+  int resolve;
+
+  /// The direction of the hierarchy levels to resolve.
+  TypeHierarchyDirection direction;
+};
+bool fromJSON(const llvm::json::Value &, ResolveTypeHierarchyItemParams &);
 
 struct ReferenceParams : public TextDocumentPositionParams {
   // For now, no options like context.includeDeclaration are supported.
 };
 bool fromJSON(const llvm::json::Value &, ReferenceParams &);
 
 /// Clangd extension: indicates the current state of the file in clangd,
 /// sent from server via the `textDocument/clangd.fileStatus` notification.

clang-tools-extra/trunk/clangd/Protocol.cpp

bool fromJSON(const llvm::json::Value &Params,
   llvm::json::ObjectMapper O(Params);
   return O && O.map("range", R.range) && O.map("rangeLength", R.rangeLength) &&
          O.map("text", R.text);
 }
 
 bool fromJSON(const llvm::json::Value &Params,
               DocumentRangeFormattingParams &R) {
   llvm::json::ObjectMapper O(Params);
-  return O && O.map("textDocument", R.textDocument) &&
-         O.map("range", R.range);
+  return O && O.map("textDocument", R.textDocument) && O.map("range", R.range);
 }
 
 bool fromJSON(const llvm::json::Value &Params,
               DocumentOnTypeFormattingParams &R) {
   llvm::json::ObjectMapper O(Params);
   return O && O.map("textDocument", R.textDocument) &&
          O.map("position", R.position) && O.map("ch", R.ch);
 }
 
 bool fromJSON(const llvm::json::Value &Params, DocumentFormattingParams &R) {
   llvm::json::ObjectMapper O(Params);
   return O && O.map("textDocument", R.textDocument);
 }
 
 bool fromJSON(const llvm::json::Value &Params, DocumentSymbolParams &R) {
   llvm::json::ObjectMapper O(Params);
   return O && O.map("textDocument", R.textDocument);
 }
 
 llvm::json::Value toJSON(const DiagnosticRelatedInformation &DRI) {
   return llvm::json::Object{
       {"location", DRI.location},
       {"message", DRI.message},
   };
 }
 
 llvm::json::Value toJSON(const Diagnostic &D) {
   llvm::json::Object Diag{
       {"range", D.range},
       {"severity", D.severity},
       {"message", D.message},
llvm::json::Value toJSON(const TypeHierarchyItem &I) {
   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::ObjectMapper O(Params);
 
   // Required fields.
   if (!(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))) {
     return false;
   }
 
   // Optional fields.
   O.map("detail", I.detail);
   O.map("deprecated", I.deprecated);
   O.map("parents", I.parents);
   O.map("children", I.children);
+  O.map("data", I.data);
 
   return true;
 }
 
+bool fromJSON(const llvm::json::Value &Params,
+              ResolveTypeHierarchyItemParams &P) {
+  llvm::json::ObjectMapper O(Params);
+  return O && O.map("item", P.item) && O.map("resolve", P.resolve) &&
+         O.map("direction", P.direction);
+}
+
 bool fromJSON(const llvm::json::Value &Params, ReferenceParams &R) {
   TextDocumentPositionParams &Base = R;
   return fromJSON(Params, Base);
 }
 
 static const char *toString(OffsetEncoding OE) {
   switch (OE) {
   case OffsetEncoding::UTF8:

clang-tools-extra/trunk/clangd/XRefs.h

 /// 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(
     ParsedAST &AST, Position Pos, int Resolve, TypeHierarchyDirection Direction,
     const SymbolIndex *Index = nullptr, PathRef TUPath = PathRef{});
 
+void resolveTypeHierarchy(TypeHierarchyItem &Item, int ResolveLevels,
+                          TypeHierarchyDirection Direction,
+                          const SymbolIndex *Index);
+
 /// Retrieves the deduced type at a given location (auto, decltype).
 /// Retuns None unless SourceLocationBeg starts an auto/decltype token.
 /// It will return the underlying type.
 llvm::Optional<QualType> getDeducedType(ParsedAST &AST,
                                         SourceLocation SourceLocationBeg);
 
 /// Check if there is a deduced type at a given location (auto, decltype).
 /// SourceLocationBeg must point to the first character of the token
 bool hasDeducedType(ParsedAST &AST, SourceLocation SourceLocationBeg);
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_XREFS_H

clang-tools-extra/trunk/clangd/XRefs.cpp

llvm::Optional<QualType> getDeducedType(ParsedAST &AST,
 
   DeducedTypeVisitor V(SourceLocationBeg);
   V.TraverseAST(AST.getASTContext());
   return V.DeducedType;
 }
 
 /// Retrieves the deduced type at a given location (auto, decltype).
 bool hasDeducedType(ParsedAST &AST, SourceLocation SourceLocationBeg) {
-  return (bool) getDeducedType(AST, SourceLocationBeg);
+  return (bool)getDeducedType(AST, SourceLocationBeg);
 }
 
 llvm::Optional<HoverInfo> getHover(ParsedAST &AST, Position Pos,
                                    format::FormatStyle Style,
                                    const SymbolIndex *Index) {
   llvm::Optional<HoverInfo> HI;
   SourceLocation SourceLocationBeg = getBeginningOfIdentifier(
       AST, Pos, AST.getSourceManager().getMainFileID());
symbolToTypeHierarchyItem(const Symbol &S, const SymbolIndex *Index,
   THI.name = S.Name;
   THI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind);
   THI.deprecated = (S.Flags & Symbol::Deprecated);
   THI.selectionRange = Loc->range;
   // FIXME: Populate 'range' correctly
   // (https://github.com/clangd/clangd/issues/59).
   THI.range = THI.selectionRange;
   THI.uri = Loc->uri;
+  // Store the SymbolID in the 'data' field. The client will
+  // send this back in typeHierarchy/resolve, allowing us to
+  // continue resolving additional levels of the type hierarchy.
+  THI.data = S.ID.str();
 
   return std::move(THI);
 }
 
 static void fillSubTypes(const SymbolID &ID,
                          std::vector<TypeHierarchyItem> &SubTypes,
                          const SymbolIndex *Index, int Levels, PathRef TUPath) {
   RelationsRequest Req;
if (Index) {
       if (Optional<SymbolID> ID = getSymbolID(CXXRD))
         fillSubTypes(*ID, *Result->children, Index, ResolveLevels, TUPath);
     }
   }
 
   return Result;
 }
 
+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)
+    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());
+    }
+  }
+}
+
 FormattedString HoverInfo::present() const {
   FormattedString Output;
   if (NamespaceScope) {
     Output.appendText("Declared in");
     // Drop trailing "::".
     if (!LocalScope.empty())
       Output.appendInlineCode(llvm::StringRef(LocalScope).drop_back(2));
     else if (NamespaceScope->empty())

clang-tools-extra/trunk/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 {};"}}}
+{"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:        "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": 2
 # CHECK-NEXT:      }
 # CHECK-NEXT:    },
 # CHECK-NEXT:    "uri": "file:///clangd-test/main.cpp"
 # CHECK-NEXT:  }
 ---
-{"jsonrpc":"2.0","id":2,"method":"shutdown"}
+{"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}}
+#      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:  }
+---
+{"jsonrpc":"2.0","id":3,"method":"shutdown"}
 ---
 {"jsonrpc":"2.0","method":"exit"}

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

 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(ElementsAre(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 differnt from "resolved but empty"!
+MATCHER(ParentsNotResolved, "") { return !arg.parents; }
+MATCHER(ChildrenNotResolved, "") { return !arg.children; }
 
 TEST(FindRecordTypeAt, TypeOrVariable) {
   Annotations Source(R"cpp(
 struct Ch^ild2 {
   int c;
 };
 
 int main() {
)cpp");
   auto Index = TU.index();
 
   SymbolID Parent = findSymbolIDByName(Index.get(), "Parent");
   SymbolID Child = findSymbolIDByName(Index.get(), "Child");
 
   EXPECT_THAT(collectSubtypes(Parent, Index.get()), ElementsAre(Child));
 }
 
+TEST(Subtypes, LazyResolution) {
+  Annotations Source(R"cpp(
+struct P^arent {};
+struct Child1 : Parent {};
+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(), "/clangd-test/TestTU.cpp");
+  ASSERT_TRUE(bool(Result));
+  EXPECT_THAT(
+      *Result,
+      AllOf(WithName("Parent"), WithKind(SymbolKind::Struct), Parents(),
+            Children(AllOf(WithName("Child1"), WithKind(SymbolKind::Struct),
+                           ParentsNotResolved(), ChildrenNotResolved()))));
+
+  resolveTypeHierarchy((*Result->children)[0], /*ResolveLevels=*/1,
+                       TypeHierarchyDirection::Children, Index.get());
+
+  EXPECT_THAT(
+      (*Result->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()))));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang