[clangd] Type hierarchy subtypes

[nridge]

Summary

This builds on the relations support added in D59407, D62459, D62471, and D62839 to implement type hierarchy subtypes.

[nridge]

Rebased onto updated D56370

[nridge]

Removing Sam as reviewer as he's on parental leave.

Kadir, if you have other reviewers to suggest to provide feedback on the API changes here, please feel free to add them. Thanks!

[kadircet]

For starters, what about just introducing a new field Bases into the Symbol. Which can store symbol IDs for the parents of the mentioned symbol, then during index build we can simply add same relations from base to this symbol. This should help us get rid of RelationSlab logic.
If there wasn't a specific reason that I missed for introducing RelationSlab logic.

[kadircet]

Sorry I didn't notice the mailing thread beforehand, looks like Sam had a good point regarding performing operations on types rather than symbols(http://lists.llvm.org/pipermail/clangd-dev/2019-January/000241.html).
Does current implementation take this into account by either pointing at template specializations and/or base template declarations?

[nridge]

Add tests involving templates and template specializations

[nridge]

In D58880#1416754, @kadircet wrote:

Sorry I didn't notice the mailing thread beforehand, looks like Sam had a good point regarding performing operations on types rather than symbols(http://lists.llvm.org/pipermail/clangd-dev/2019-January/000241.html).
Does current implementation take this into account by either pointing at template specializations and/or base template declarations?

I thought about this, and I believe that having the relationship be between symbols is sufficient.

The main utility in a type hierarchy view is to allow the user to navigate to base/derived classes. If a base or derived class is an implicit specialization, the desired navigation is to the corresponding template definition; if it's an explicit specialization, the desired navigation is to the explicit specialization's definition.

A class template will obviously have its own symbol, so that part's fine. Explicit specializations are not currently stored in the index, but I think it would make sense for them to be, for other reasons as well (e.g. a user may want to navigate to an explicit specialization definition via "workspace/symbol"), in which case they too will get their own symbols. So, in either case, the desired type hierarchy item can be obtained from a symbol.

The updated patch has tests covering these scenarios, specifically Subtypes.ClassTemplate and Subtypes.DependentBase. Two additional tests, Subtypes.TemplateSpec1 and Subtypes.TemplateSpec2 are disabled until we start storing explicit specializations in the index.

[hokein]

Haven't looked at the patch. I think we can extend the existing Ref to support it, so that most of the stuff could be reused, rather than implementing a new slab:

• introduce a new RefKind, like BaseOf
• add a new field SymbolID in Ref

and clangIndex library has already implemented relationship functionality (we could use handleDeclOccurence to store the symbols relationships).

[nridge]

In D58880#1418195, @hokein wrote:

I think we can extend the existing Ref to support it, so that most of the stuff could be reused, rather than implementing a new slab:

• introduce a new RefKind, like BaseOf
• add a new field SymbolID in Ref

I had considered this approach as well, but figured that it would be wasteful in terms of storage space.

My understanding is that the storage space taken up for Refs is currently 8 bytes per Ref (4 each for the start and end positions), plus filename strings which are deduplicated across all refs. If we add a SymbolID, that adds an additional 8 bytes to each Ref. Given that Refs are numerous, and most of them won't use the SymbolID, that seems wasteful.

That said, I do appreciate that this is a simpler approach in terms of complexity, so if folks feel the right tradeoff is to take the Refs approach, I am open to doing that.

[gribozavr]

My understanding is that the storage space taken up for Refs is currently 8 bytes per Ref (4 each for the start and end positions), plus filename strings which are deduplicated across all refs. If we add a SymbolID, that adds an additional 8 bytes to each Ref. Given that Refs are numerous, and most of them won't use the SymbolID, that seems wasteful.

I see. This is a very good observation, we didn't consider increase in memory usage when we discussed your patch. Sorry about that! We discussed your patch again and we agree with the approach of adding a RelationsSlab.

Here are the options we considered, and the trade-offs we identified.

Option 1: Add SymbolID to Ref. Advantage: simpler API, fewer types in the API. Disadvantage: increased memory usage, as you noted.

Option 2: Add Relation struct, but store them in RefSlab, using a compact representation that skips storing SymbolID where it is not present. Advantages: we avoid adding a type that's almost an exact duplicate of RefSlab, we don't unnecessarily increase memory usage. Disadvantages: tricky code to avoid storing SymbolID, and RefSlab now stores both Refs and Relations, which is confusing from the API point of view.

Option 3 (what your patch implements): Add Relation struct and RelationSlab. Advantage: API matches the data model, we don't unnecessarily increase memory usage. Disadvantage: have to plumb the new slab everywhere in the code.

Option 4: Add a Relation struct. Change RefSlab to a template so that it can store either Refs, or Relations. Advantage: API matches the data model, we don't unnecessarily increase memory usage, we avoid duplicating RefSlab type. Disadvantage: possibly complex template in a in important clangd API, we avoided duplicating at most 100 lines, but we still have to plumb the new slab everywhere in the code.

clang-tools-extra/clangd/index/FileIndex.h

125 ↗

(On Diff #189275)

AllSlabs? And even better, a struct?

[nridge]

Thanks for the detailed analysis!

For completeness, I think another advantage of option 3 is that it allows us to make the key for relation lookups be a (SymbolID, RelationKind) pair rather than just a SymbolID.

It sounds like I should continue implementing the current approach. Marking the revision as "changes planned" accordingly.

[kadircet]

Hi Nathan,

I would also suggest splitting up current changes so that we can start reviewing them, which might result in other changes in your planned changes and help reduce duplicate work both on our and your side.
Also please have a look at D59083, and make sure it helps implement what you have in might and let me know if there's anything missing.

As for splitting changes I would suggest something like:

• RelationSlab
• Serialization/Deserialization of the RelationSlab
• Integrating RelationSlab with SymbolCollector
• Adding queries to index structures(memindex, dex, mergedindex etc.)
• Surfacing those queries through typehierarchy request

[nridge]

In D58880#1422494, @kadircet wrote:

Hi Nathan,

I would also suggest splitting up current changes so that we can start reviewing them, which might result in other changes in your planned changes and help reduce duplicate work both on our and your side.
[...]

As for splitting changes I would suggest something like:

• RelationSlab
• Serialization/Deserialization of the RelationSlab
• Integrating RelationSlab with SymbolCollector
• Adding queries to index structures(memindex, dex, mergedindex etc.)
• Surfacing those queries through typehierarchy request

Thanks. The proposed split looks good to me. I've posted the first patch here: https://reviews.llvm.org/D59407

[nridge]

In D58880#1422494, @kadircet wrote:

Also please have a look at D59083, and make sure it helps implement what you have in might and let me know if there's anything missing.

I verified that with D59083 + D59354, I'm able to get my template specialization tests passing. Thanks for working on those!

[nridge]

Rebased onto D62839 and predecessors

[nridge]

Rebase, add lit test, and post for review

[nridge]

Get disabled tests passing

[kadircet]

mostly LG, thanks!

clang-tools-extra/clangd/XRefs.cpp

1057 ↗

(On Diff #204208)

nit: could we directly use THI.range.start.line (same for the following 3 lines)

1061 ↗

(On Diff #204208)

a few different approaches that comes to my mind:

• store the full range in index.
• check AST cache to see if we have AST for CD.FileURI, and use that decl.
• build AST for CD.FileURI
• heuristically parse CD.FileURI

Could you create a bug report in https://github.com/clangd/clangd/issues ?

1064 ↗

(On Diff #204208)

yeah it would be great to have a Location symbolToLocation(const Symbol& S);

1071 ↗

(On Diff #204208)

you do not need WorkspaceRoot, you can pass the translationunit getTypeHierarchy was triggered on. Which is available in File parameter.

Also it always exists whereas WorkspaceRoot might be missing depending on the editor.

1212 ↗

(On Diff #204208)

nit: braces(just the inner one, keep the outer one)

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

459 ↗

(On Diff #204208)

bool GotResult = false;

462 ↗

(On Diff #204208)

EXPECT_FALSE(GotResult);
GotResult = true;

466 ↗

(On Diff #204208)

EXPECT_TRUE(GotResult);

470 ↗

(On Diff #204208)

Maybe call it Subject instead of Type ?

478 ↗

(On Diff #204208)

could you add another child that derives Parent to check multiple children case?

479 ↗

(On Diff #204208)

could you get rid of member fields and put definitions into single lines to make test smaller?

505 ↗

(On Diff #204208)

same suggestion for member fields and single line definitions

[nridge]

Address review comments

[nridge]

clang-tools-extra/clangd/XRefs.cpp

1061 ↗

(On Diff #204208)

Filed https://github.com/clangd/clangd/issues/59.

[kadircet]

LGTM with a few small comments.

Thanks for implementing this awesome feature!

clang-tools-extra/clangd/FindSymbols.cpp

42 ↗

(On Diff #204696)

let's rather return an llvm::Expected<Location> and propagate the error messages in the error then log in the caller site

clang-tools-extra/clangd/FindSymbols.h

21 ↗

(On Diff #204696)

let's rather #include "Symbol.h"

clang-tools-extra/clangd/XRefs.cpp

1052 ↗

(On Diff #204696)

this part looks a little messed up ?

I suppose you wanted to propagate TUPath to symbolToLocation right?

clang-tools-extra/clangd/XRefs.h

139 ↗

(On Diff #204696)

I believe TUPath is not used if Index is nullptr, maybe replace those two?

[nridge]

Address remaining review comments

clang-tools-extra/clangd/XRefs.cpp

1052 ↗

(On Diff #204696)

Good catch! Fixed.

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

if (!A)
       return CB(A.takeError());
     auto Raw = (*A)->apply(*Selection);
     if (!Raw)
       return CB(Raw.takeError());
     // FIXME: this function has I/O operations (find .clang-format file), figure
     // out a way to cache the format style.
     auto Style = getFormatStyleForFile(File, InpAST->Inputs.Contents,
                                        InpAST->Inputs.FS.get());
-    auto Formatted =
-        cleanupAndFormat(InpAST->Inputs.Contents, *Raw, Style);
+    auto Formatted = cleanupAndFormat(InpAST->Inputs.Contents, *Raw, Style);
     if (!Formatted)
       return CB(Formatted.takeError());
     return CB(replacementsToEdits(InpAST->Inputs.Contents, *Formatted));
   };
   WorkScheduler.runWithAST(
       "ApplyTweak", File,
       Bind(Action, std::move(CB), File.str(), TweakID.str()));
 }
void ClangdServer::findHover(PathRef File, Position Pos,
 
   WorkScheduler.runWithAST("Hover", File,
                            Bind(Action, std::move(CB), File.str()));
 }
 
 void ClangdServer::typeHierarchy(PathRef File, Position Pos, int Resolve,
                                  TypeHierarchyDirection Direction,
                                  Callback<Optional<TypeHierarchyItem>> CB) {
-  auto Action = [Pos, Resolve, Direction](decltype(CB) CB,
-                                          Expected<InputsAndAST> InpAST) {
+  std::string FileCopy = File; // copy will be captured by the lambda
+  auto Action = [FileCopy, Pos, Resolve, Direction,
+                 this](decltype(CB) CB, Expected<InputsAndAST> InpAST) {
     if (!InpAST)
       return CB(InpAST.takeError());
-    CB(clangd::getTypeHierarchy(InpAST->AST, Pos, Resolve, Direction));
+    CB(clangd::getTypeHierarchy(InpAST->AST, Pos, Resolve, Direction, Index,
+                                FileCopy));
   };
 
   WorkScheduler.runWithAST("Type Hierarchy", File, Bind(Action, std::move(CB)));
 }
 
 void ClangdServer::onFileEvent(const DidChangeWatchedFilesParams &Params) {
   // FIXME: Do nothing for now. This will be used for indexing and potentially
   // invalidating other caches.

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

 //===--- FindSymbols.h --------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 //
 // Queries that provide a list of symbols matching a string.
 //
 //===----------------------------------------------------------------------===//
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_FINDSYMBOLS_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_FINDSYMBOLS_H
 
 #include "Protocol.h"
+#include "index/Symbol.h"
 #include "llvm/ADT/StringRef.h"
 
 namespace clang {
 namespace clangd {
 class ParsedAST;
 class SymbolIndex;
 
+/// Helper function for deriving an LSP Location for a Symbol.
+llvm::Expected<Location> symbolToLocation(const Symbol &Sym,
+                                          llvm::StringRef HintPath);
+
 /// Searches for the symbols matching \p Query. The syntax of \p Query can be
 /// the non-qualified name or fully qualified of a symbol. For example,
 /// "vector" will match the symbol std::vector and "std::vector" would also
 /// match it. Direct children of scopes (namepaces, etc) can be listed with a
 /// trailing
 /// "::". For example, "std::" will list all children of the std namespace and
 /// "::" alone will list all children of the global namespace.
 /// \p Limit limits the number of results returned (0 means no limit).

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

bool operator()(const ScoredSymbolInfo &L, const ScoredSymbolInfo &R) {
     if (L.first != R.first)
       return L.first > R.first;
     return L.second.name < R.second.name; // Earlier name is better.
   }
 };
 
 } // namespace
 
+llvm::Expected<Location> symbolToLocation(const Symbol &Sym,
+                                          llvm::StringRef HintPath) {
+  // Prefer the definition over e.g. a function declaration in a header
+  auto &CD = Sym.Definition ? Sym.Definition : Sym.CanonicalDeclaration;
+  auto Uri = URI::parse(CD.FileURI);
+  if (!Uri) {
+    return llvm::make_error<llvm::StringError>(
+        formatv("Could not parse URI '{0}' for symbol '{1}'.", CD.FileURI,
+                Sym.Name),
+        llvm::inconvertibleErrorCode());
+  }
+  auto Path = URI::resolve(*Uri, HintPath);
+  if (!Path) {
+    return llvm::make_error<llvm::StringError>(
+        formatv("Could not resolve path for URI '{0}' for symbol '{1}'.",
+                Uri->toString(), Sym.Name),
+        llvm::inconvertibleErrorCode());
+  }
+  Location L;
+  // Use HintPath as TUPath since there is no TU associated with this
+  // request.
+  L.uri = URIForFile::canonicalize(*Path, HintPath);
+  Position Start, End;
+  Start.line = CD.Start.line();
+  Start.character = CD.Start.column();
+  End.line = CD.End.line();
+  End.character = CD.End.column();
+  L.range = {Start, End};
+  return L;
+}
+
 llvm::Expected<std::vector<SymbolInformation>>
 getWorkspaceSymbols(llvm::StringRef Query, int Limit,
                     const SymbolIndex *const Index, llvm::StringRef HintPath) {
   std::vector<SymbolInformation> Result;
   if (Query.empty() || !Index)
     return Result;
 
   auto Names = splitQualifiedName(Query);
getWorkspaceSymbols(llvm::StringRef Query, int Limit,
   else
     Req.AnyScope = true;
   if (Limit)
     Req.Limit = Limit;
   TopN<ScoredSymbolInfo, ScoredSymbolGreater> Top(
       Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max());
   FuzzyMatcher Filter(Req.Query);
   Index->fuzzyFind(Req, [HintPath, &Top, &Filter](const Symbol &Sym) {
-    // Prefer the definition over e.g. a function declaration in a header
-    auto &CD = Sym.Definition ? Sym.Definition : Sym.CanonicalDeclaration;
-    auto Uri = URI::parse(CD.FileURI);
-    if (!Uri) {
-      log("Workspace symbol: Could not parse URI '{0}' for symbol '{1}'.",
-          CD.FileURI, Sym.Name);
-      return;
-    }
-    auto Path = URI::resolve(*Uri, HintPath);
-    if (!Path) {
-      log("Workspace symbol: Could not resolve path for URI '{0}' for symbol "
-          "'{1}'.",
-          Uri->toString(), Sym.Name);
+    auto Loc = symbolToLocation(Sym, HintPath);
+    if (!Loc) {
+      log("Workspace symbols: {0}", Loc.takeError());
       return;
     }
-    Location L;
-    // Use HintPath as TUPath since there is no TU associated with this
-    // request.
-    L.uri = URIForFile::canonicalize(*Path, HintPath);
-    Position Start, End;
-    Start.line = CD.Start.line();
-    Start.character = CD.Start.column();
-    End.line = CD.End.line();
-    End.character = CD.End.column();
-    L.range = {Start, End};
+
     SymbolKind SK = indexSymbolKindToSymbolKind(Sym.SymInfo.Kind);
     std::string Scope = Sym.Scope;
     llvm::StringRef ScopeRef = Scope;
     ScopeRef.consume_back("::");
     SymbolInformation Info = {(Sym.Name + Sym.TemplateSpecializationArgs).str(),
-                              SK, L, ScopeRef};
+                              SK, *Loc, ScopeRef};
 
     SymbolQualitySignals Quality;
     Quality.merge(Sym);
     SymbolRelevanceSignals Relevance;
     Relevance.Name = Sym.Name;
     Relevance.Query = SymbolRelevanceSignals::Generic;
     if (auto NameMatch = Filter.match(Sym.Name))
       Relevance.NameMatch = *NameMatch;

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

 
 /// Find the record type references at \p Pos.
 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(ParsedAST &AST, Position Pos, int Resolve,
-                 TypeHierarchyDirection Direction);
+llvm::Optional<TypeHierarchyItem> getTypeHierarchy(
+    ParsedAST &AST, Position Pos, int Resolve, TypeHierarchyDirection Direction,
+    const SymbolIndex *Index = nullptr, PathRef TUPath = PathRef{});
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_XREFS_H

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

declToTypeHierarchyItem(ASTContext &Ctx, const NamedDecl &ND) {
   auto TUPath = getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
   if (!FilePath || !TUPath)
     return llvm::None; // Not useful without a uri.
   THI.uri = URIForFile::canonicalize(*FilePath, *TUPath);
 
   return THI;
 }
 
+static Optional<TypeHierarchyItem>
+symbolToTypeHierarchyItem(const Symbol &S, const SymbolIndex *Index,
+                          PathRef TUPath) {
+  auto Loc = symbolToLocation(S, TUPath);
+  if (!Loc) {
+    log("Type hierarchy: {0}", Loc.takeError());
+    return llvm::None;
+  }
+  TypeHierarchyItem THI;
+  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;
+
+  return std::move(THI);
+}
+
+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 = index::SymbolRole::RelationBaseOf;
+  Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
+    if (Optional<TypeHierarchyItem> ChildSym =
+            symbolToTypeHierarchyItem(Object, Index, 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>;
 
 static Optional<TypeHierarchyItem>
 getTypeAncestors(const CXXRecordDecl &CXXRD, ASTContext &ASTCtx,
                  RecursionProtectionSet &RPSet) {
   Optional<TypeHierarchyItem> Result = declToTypeHierarchyItem(ASTCtx, CXXRD);
   if (!Result)
     return Result;
if (ParentDecl)
       Result.push_back(ParentDecl);
   }
 
   return Result;
 }
 
 llvm::Optional<TypeHierarchyItem>
 getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
-                 TypeHierarchyDirection Direction) {
+                 TypeHierarchyDirection Direction, const SymbolIndex *Index,
+                 PathRef TUPath) {
   const CXXRecordDecl *CXXRD = findRecordTypeAt(AST, Pos);
   if (!CXXRD)
     return llvm::None;
 
   RecursionProtectionSet RPSet;
   Optional<TypeHierarchyItem> Result =
       getTypeAncestors(*CXXRD, AST.getASTContext(), RPSet);
 
-  // FIXME(nridge): Resolve type descendants if direction is Children or Both,
-  // and ResolveLevels > 0.
+  if ((Direction == TypeHierarchyDirection::Children ||
+       Direction == TypeHierarchyDirection::Both) &&
+      ResolveLevels > 0) {
+    Result->children.emplace();
+
+    if (Index) {
+      if (Optional<SymbolID> ID = getSymbolID(CXXRD))
+        fillSubTypes(*ID, *Result->children, Index, ResolveLevels, TUPath);
+    }
+  }
 
   return Result;
 }
 
 FormattedString HoverInfo::present() const {
   FormattedString Output;
   if (NamespaceScope) {
     Output.appendText("Declared in");

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 {};"}}}
+{"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","id":1,"method":"textDocument/typeHierarchy","params":{"textDocument":{"uri":"test:///main.cpp"},"position":{"line":2,"character":11},"direction":1,"resolve":1}}
+{"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:        "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:    "kind": 23,
 # CHECK-NEXT:    "name": "Child2",
 # CHECK-NEXT:    "parents": [
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "kind": 23,
 # CHECK-NEXT:        "name": "Child1",
 # CHECK-NEXT:        "parents": [
 # CHECK-NEXT:          {

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

 
 using ::testing::AllOf;
 using ::testing::ElementsAre;
 using ::testing::Eq;
 using ::testing::Field;
 using ::testing::IsEmpty;
 using ::testing::Matcher;
 using ::testing::Pointee;
-using ::testing::UnorderedElementsAreArray;
+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...)));
TEST(TypeHierarchy, RecursiveHierarchyBounded) {
   ASSERT_TRUE(bool(Result));
   EXPECT_THAT(
       *Result,
       AllOf(WithName("S"), WithKind(SymbolKind::Struct),
             Parents(AllOf(WithName("S"), WithKind(SymbolKind::Struct),
                           SelectionRangeIs(Source.range("SDef")), Parents()))));
 }
 
+SymbolID findSymbolIDByName(SymbolIndex *Index, llvm::StringRef Name,
+                            llvm::StringRef TemplateArgs = "") {
+  SymbolID Result;
+  FuzzyFindRequest Request;
+  Request.Query = Name;
+  Request.AnyScope = true;
+  bool GotResult = false;
+  Index->fuzzyFind(Request, [&](const Symbol &S) {
+    if (TemplateArgs == S.TemplateSpecializationArgs) {
+      EXPECT_FALSE(GotResult);
+      Result = S.ID;
+      GotResult = true;
+    }
+  });
+  EXPECT_TRUE(GotResult);
+  return Result;
+}
+
+std::vector<SymbolID> collectSubtypes(SymbolID Subject, SymbolIndex *Index) {
+  std::vector<SymbolID> Result;
+  RelationsRequest Req;
+  Req.Subjects.insert(Subject);
+  Req.Predicate = index::SymbolRole::RelationBaseOf;
+  Index->relations(Req,
+                   [&Result](const SymbolID &Subject, const Symbol &Object) {
+                     Result.push_back(Object.ID);
+                   });
+  return Result;
+}
+
+TEST(Subtypes, SimpleInheritance) {
+  Annotations Source(R"cpp(
+struct Parent {};
+struct Child1a : Parent {};
+struct Child1b : Parent {};
+struct Child2 : Child1a {};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto Index = TU.index();
+
+  SymbolID Parent = findSymbolIDByName(Index.get(), "Parent");
+  SymbolID Child1a = findSymbolIDByName(Index.get(), "Child1a");
+  SymbolID Child1b = findSymbolIDByName(Index.get(), "Child1b");
+  SymbolID Child2 = findSymbolIDByName(Index.get(), "Child2");
+
+  EXPECT_THAT(collectSubtypes(Parent, Index.get()),
+              UnorderedElementsAre(Child1a, Child1b));
+  EXPECT_THAT(collectSubtypes(Child1a, Index.get()), ElementsAre(Child2));
+}
+
+TEST(Subtypes, MultipleInheritance) {
+  Annotations Source(R"cpp(
+struct Parent1 {};
+struct Parent2 {};
+struct Parent3 : Parent2 {};
+struct Child : Parent1, Parent3 {};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto Index = TU.index();
+
+  SymbolID Parent1 = findSymbolIDByName(Index.get(), "Parent1");
+  SymbolID Parent2 = findSymbolIDByName(Index.get(), "Parent2");
+  SymbolID Parent3 = findSymbolIDByName(Index.get(), "Parent3");
+  SymbolID Child = findSymbolIDByName(Index.get(), "Child");
+
+  EXPECT_THAT(collectSubtypes(Parent1, Index.get()), ElementsAre(Child));
+  EXPECT_THAT(collectSubtypes(Parent2, Index.get()), ElementsAre(Parent3));
+  EXPECT_THAT(collectSubtypes(Parent3, Index.get()), ElementsAre(Child));
+}
+
+TEST(Subtypes, ClassTemplate) {
+  Annotations Source(R"cpp(
+struct Parent {};
+
+template <typename T>
+struct Child : Parent {};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  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, TemplateSpec1) {
+  Annotations Source(R"cpp(
+template <typename T>
+struct Parent {};
+
+template <>
+struct Parent<int> {};
+
+struct Child1 : Parent<float> {};
+
+struct Child2 : Parent<int> {};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto Index = TU.index();
+
+  SymbolID Parent = findSymbolIDByName(Index.get(), "Parent");
+  SymbolID ParentSpec = findSymbolIDByName(Index.get(), "Parent", "<int>");
+  SymbolID Child1 = findSymbolIDByName(Index.get(), "Child1");
+  SymbolID Child2 = findSymbolIDByName(Index.get(), "Child2");
+
+  EXPECT_THAT(collectSubtypes(Parent, Index.get()), ElementsAre(Child1));
+  EXPECT_THAT(collectSubtypes(ParentSpec, Index.get()), ElementsAre(Child2));
+}
+
+TEST(Subtypes, TemplateSpec2) {
+  Annotations Source(R"cpp(
+struct Parent {};
+
+template <typename T>
+struct Child {};
+
+template <>
+struct Child<int> : Parent {};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto Index = TU.index();
+
+  SymbolID Parent = findSymbolIDByName(Index.get(), "Parent");
+  SymbolID ChildSpec = findSymbolIDByName(Index.get(), "Child", "<int>");
+
+  EXPECT_THAT(collectSubtypes(Parent, Index.get()), ElementsAre(ChildSpec));
+}
+
+TEST(Subtypes, DependentBase) {
+  Annotations Source(R"cpp(
+template <typename T>
+struct Parent {};
+
+template <typename T>
+struct Child : Parent<T> {};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto Index = TU.index();
+
+  SymbolID Parent = findSymbolIDByName(Index.get(), "Parent");
+  SymbolID Child = findSymbolIDByName(Index.get(), "Child");
+
+  EXPECT_THAT(collectSubtypes(Parent, Index.get()), ElementsAre(Child));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang