[clangd] Add support for type hierarchy (super types only for now)

[nridge]

Summary

This is an LSP extension proposed here:
https://github.com/Microsoft/vscode-languageserver-node/pull/426

An example client implementation can be found here:
https://github.com/theia-ide/theia/pull/3802

[nridge]

This comment was removed by nridge.

[nridge]

Cleaned up patch, ready for review

[nridge]

Please see also the clangd-dev discussion about this feature.

A particular question that I could use some feedback on from reviewers: the patch takes several functions that were previously file-local, such as declToSym() in FindSymbols.cpp and toURI() in SymbolCollector.cpp, and promotes them to functions declared in the corresponding header, so that they can be used from elsewhere (e.g. declToSym() from XRefs.cpp). Should these functions be moved to a dedicated file for utilities used for converting from internal representations (e.g. AST nodes) to protocol structures?

[jkorous]

Hi Nate, thanks for the patch!

I am just wondering which data structure fits the best here. Do you have any thoughts on support for virtual inheritance? In other words - should we use a tree or a DAG?

clang-tools-extra/clangd/XRefs.cpp

836 ↗

(On Diff #182686)

This looks a bit confusing naming-wise. Maybe renaming the property to something like graphChildren would be better? WDYT?

[nridge]

In D56370#1370021, @jkorous wrote:

I am just wondering which data structure fits the best here. Do you have any thoughts on support for virtual inheritance? In other words - should we use a tree or a DAG?

All the editors I know of that support a type hierarchy view, use a tree view of some sort to display it, so I think having a tree data structure at the protocol level makes sense. We could potentially annotate virtual bases with a flag (perhaps visualized as an icon / decoration) to draw attention to them.

clang-tools-extra/clangd/XRefs.cpp

836 ↗

(On Diff #182686)

The property name here comes from the fact that the formulation of the protocol that I implemented is reusing the existing DocumentSymbol type.

However, the proposal has been updated just a few days ago to use a dedicated new type instead of reusing DocumentSymbol. The new type, TypeHierarchyItem, has separate fields named parents and children.

It probably makes sense for me to update this implementation to reflect the updated proposal, before it is reviewed further, so I will mark it as "Changes Planned" for now.

[nridge]

Implement revised specification (WIP)

[nridge]

Remove unrelated file

[nridge]

This is a partial implementation of the revised spec for type hierarchy. Things that still need to be done:

• Handle the resolve and direction parameters in TypeHierarchyRequest
• Implement typeHierarchy/resolve
• (Later, in a separate patch: subtypes. Will requre index changes.)

[nridge]

This completes the implementation of the revised spec (for supertypes only)

[nridge]

remove unrelated file

[nridge]

clang-tools-extra/clangd/XRefs.cpp

820 ↗

(On Diff #184985)

I am open to feedback on whether we want to reduce the duplication between these functions, and if so, suggestions for how.

901 ↗

(On Diff #184985)

I am deliberately leaving this part for a follow-up patch, as it will require index changes.

clang-tools-extra/unittests/clangd/Matchers.h

130 ↗

(On Diff #184985)

Should I split this out into a separate patch? It's used by the tests being added for this functionality.

[kadircet]

Implementation LG, but I am not sure about adding a functionality on a proposal that might change. WDYT @sammccall ?

clang-tools-extra/clangd/FindSymbols.cpp

16 ↗

(On Diff #184985)

it seems like there is no change in file requiring this

218 ↗

(On Diff #184985)

can you revert this one as well ?

clang-tools-extra/clangd/Protocol.cpp

817 ↗

(On Diff #184985)

nit: get rid of nesting by

auto T = E.getas..;
if(!T)
  return false;
if(*T not in rage)
  return false;
Out = cast(*T);
return true;

clang-tools-extra/clangd/Protocol.h

1026 ↗

(On Diff #184985)

why not just use an int then ?

1046 ↗

(On Diff #184985)

again we can just store a bool, and only serialize if it is true

clang-tools-extra/clangd/XRefs.cpp

876 ↗

(On Diff #184985)

again reduce nesting

891 ↗

(On Diff #184985)

A problem that might occur when you add children traversal:
do we really want to include current decl in children of parent when we have BOTH as direction? If so, maybe we should rather cache the results? Maybe leave a todo/fixme ?

917 ↗

(On Diff #184985)

llvm::None

925 ↗

(On Diff #184985)

what about member fields ?

932 ↗

(On Diff #184985)

reduce nesting

935 ↗

(On Diff #184985)

Is this mentioned in proposal?

939 ↗

(On Diff #184985)

llvm::None

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

1355 ↗

(On Diff #184985)

can you format the code?

1387 ↗

(On Diff #184985)

You can use Source.points() and use Pt directly instead of doing Source.point(pt). Same for other tests.

[sammccall]

In D56370#1390283, @kadircet wrote:

Implementation LG, but I am not sure about adding a functionality on a proposal that might change. WDYT @sammccall ?

We discussed this a bit on the thread, I think we should follow the proposed spec, but with some useful hedges:

• only implement enough bits to be useful
• I'm not sure the internal APIs/implementation should follow the "shape" of the spec so deeply.

So on a concrete but still high-level:

• I don't think we should implement the resolve operation, or resolution bounds, at this point - this patch doesn't do anything slow. Returning complete ancestors and never returning any children seems simplest.
• in 'XRefs.h', I think the API to introduce is findTypeAt(Position) -> Decl* + typeAncestors(Decl*) and later typeDescendants(Decl*), rather than a single more complex typeHierarchy call. These two operations have little in common implementation-wise, and it's easy to imagine editors preferring to expose them separately. In clangdserver of course we need to expose a single operation because of transactionality. The stitching together could go in clangdserver, or a higher-level function exposed by xrefs - but I think the separate functions are what we should be unit-testing.

clang-tools-extra/unittests/clangd/Matchers.h

130 ↗

(On Diff #184985)

This is nice! I think it should probably go in llvm/Testing/Support/..., but it's OK here.

[sammccall]

Updated reviewers line to reflect (I think) current reality so this doesn't get lost, but feel free to reassign as you'd prefer.

[nridge]

Add tests for scenarios involving class template specializations

Also improve support for dependent bases

[nridge]

In D56370#1391904, @nridge wrote:

Add tests for scenarios involving class template specializations

Also improve support for dependent bases

(This update is unrelated to the review comments, it's just improvements I had in the queue already. Another update to address review comments will come next.)

[nridge]

Thank you for the reviews!

clang-tools-extra/clangd/Protocol.h

1026 ↗

(On Diff #184985)

I was making the data structure correspond closely to the protocol, where the field is optional. But we can handle this in the serialization logic, yes.

clang-tools-extra/clangd/XRefs.cpp

891 ↗

(On Diff #184985)

Actually, this is a bug: if the top-level call uses Both, the recursive calls should still just use Parents and Children (i.e. we never want children of parents or parents of children). Thanks for spotting that!

925 ↗

(On Diff #184985)

It's not clear what the desired semantics would be for a member field: get the type hierarchy of the enclosing class type, or the type hierarchy of the field's type?

935 ↗

(On Diff #184985)

It's not specified; I left a comment on the proposal asking about it.

clang-tools-extra/unittests/clangd/Matchers.h

130 ↗

(On Diff #184985)

I'll leave it here for now. We can move it in a follow-up patch.

[nridge]

Address Kadir's review comments

[nridge]

In D56370#1390359, @sammccall wrote:

So on a concrete but still high-level:

• I don't think we should implement the resolve operation, or resolution bounds, at this point - this patch doesn't do anything slow. Returning complete ancestors and never returning any children seems simplest.

A hypothetical client could always ask for one level at a time, and ignore any levels it didn't ask for; such a client would break if we did this.

I think the implementation of resolve is straightforward enough that we might as well keep it.

• in 'XRefs.h', I think the API to introduce is findTypeAt(Position) -> Decl* + typeAncestors(Decl*) and later typeDescendants(Decl*), rather than a single more complex typeHierarchy call. These two operations have little in common implementation-wise, and it's easy to imagine editors preferring to expose them separately. In clangdserver of course we need to expose a single operation because of transactionality. The stitching together could go in clangdserver, or a higher-level function exposed by xrefs - but I think the separate functions are what we should be unit-testing.

This sounds nice and clean, thanks for the suggestion! I will give it a try.

[nridge]

Introduce and use findRecordTypeAt() and typeAncestors() helpers

[nridge]

In D56370#1390359, @sammccall wrote:

• in 'XRefs.h', I think the API to introduce is findTypeAt(Position) -> Decl* + typeAncestors(Decl*) and later typeDescendants(Decl*), rather than a single more complex typeHierarchy call. These two operations have little in common implementation-wise, and it's easy to imagine editors preferring to expose them separately. In clangdserver of course we need to expose a single operation because of transactionality. The stitching together could go in clangdserver, or a higher-level function exposed by xrefs - but I think the separate functions are what we should be unit-testing.

In the latest update I introduced these helpers. I made the first one findRecordTypeAt() instead of findTypeAt(), since findTypeAt() suggests it also works for built-in types like int, but I don't think we can get a Decl* for int.

As far as reworking the tests to use these functions, I've thought about that a bit:

• These functions return AST nodes. It's not clear to me how I would come up with "expected" AST nodes to test the return values against.
• Even if we find a way to get "expected" AST nodes, we would be losing test coverage of functions like declToTypeHierarchyItem() (though I suppose we could write separate tests for that).
• We could instead test against the properties of the AST nodes, such as their names and source ranges, but then the test code to query those properties would basically be duplicating code in declToTypeHierarchyItem(). It would seem to make more sense to just test the resulting TypeHierarchyItem instead (as the tests are doing now).

[sammccall]

In D56370#1391924, @nridge wrote:

As far as reworking the tests to use these functions, I've thought about that a bit:

• These functions return AST nodes. It's not clear to me how I would come up with "expected" AST nodes to test the return values against.

See findDecl in ASTUnit.h

• Even if we find a way to get "expected" AST nodes, we would be losing test coverage of functions like declToTypeHierarchyItem() (though I suppose we could write separate tests for that).

Yes, please do.

clang-tools-extra/clangd/ClangdServer.cpp

543 ↗

(On Diff #186139)

relying on the item range to resolve the actual symbol isn't reliable:

• the source code may have changed
• the range may not be within the TU, and might be e.g. in an indexed header we don't have a compile command for.

[kadircet]

clang-tools-extra/clangd/XRefs.cpp

925 ↗

(On Diff #184985)

I think it is sensible to go for enclosing type. But up to you, in any case could you add a comment stating how FieldDecl are handled?

[nridge]

clang-tools-extra/clangd/ClangdServer.cpp

543 ↗

(On Diff #186139)

Good point. I appreciate a bit better now why you suggested trying to avoid resolve for now :)

What do you think of the following implementation approach:

• Use the data field of TypeHierarchyItem (which the client will send back to the server for resolve queries) to send the SymbolID of the item to the client.
• When the client sends back the SymbolID in the resolve request, look up the symbol in the index, and use the source range from the symbol.

(Later, when we start storing base <--> derived relationships in the index for subtype support, we could just answer the entire resolve query using the index.)

[sammccall]

clang-tools-extra/clangd/ClangdServer.cpp

543 ↗

(On Diff #186139)

Thanks for exploring all the options here!

Generally we've tried to avoid relying on the index unless it's needed, using the AST where possible. There are failure modes here:

• the base type is in the current file, which is actively edited. The ranges in the index may be off due to staleness.
• the base type is not indexed, because it is e.g. a member class inside a class template
• there's no index (-index=0, though I'm not sure why we still support this) or the index is stale and the type is missing (we're working on making index updates more async)
• the base type is not encodable.

There are just more moving pieces here, I think. Is there a clear reason to support resolve for parents?

[nridge]

clang-tools-extra/clangd/ClangdServer.cpp

543 ↗

(On Diff #186139)

Is there a clear reason to support resolve for parents?

Just what I said earlier about a hypothetical client that relies on it.

However, given the complications involved in implementing it, I'm happy with only being concerned with actual clients, not hypothetical ones. The only client implementation I currently know of is Theia, and I checked that it works fine without resolve, so I'm happy with deferring work on resolve for now.

If another client comes along that relies on resolve, we can revisit this.

[sammccall]

clang-tools-extra/clangd/ClangdServer.cpp

543 ↗

(On Diff #186139)

Just what I said earlier about a hypothetical client that relies on it.

I'll try to get the spec clarified such that eager resolution is always fine.
But if we ever do need to deal with such clients, @ioeric had a neat idea: we can just stash the rest of the response in the data field, and then "resolution" can just pull it out. This should be easy to bolt on.

clang-tools-extra/clangd/XRefs.cpp

842 ↗

(On Diff #186139)

This is more conversions than necessary.
I think we just need:

auto FilePath = getCanonicalPath(SM.getFileEntryForID(SM.getFileID(BeginLoc)), SM);
auto TUPath = getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()));
if (!FilePath || !TUPath)
  return;
THI.uri = URIForFile::Canonicalize(*FilePath, *TUPath);

(This is still more lines than I'd like, maybe we should have some helper for going from (File ID, SourceManager) --> URI)

[sammccall]

clang-tools-extra/clangd/XRefs.cpp

842 ↗

(On Diff #186139)

(I looked at adding such a helper, and I don't think it's a good idea - the few existing callsites that could use it currently benefit significantly from hoisting the getCanonicalPath from the TUPath outside of a loop. It may or may not be worth doing that here)

[nridge]

• Rework tests to test the lower-level functions like typeAncestors()
• Remove support for typeHierarchy/resolve

[nridge]

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

1604 ↗

(On Diff #186944)

Any suggestions for how we can make findDecl() support template-ids?

[nridge]

Fix a test failure

[nridge]

I think this is ready to continue to be reviewed :)

[nridge]

Rebased.

[sammccall]

Hi Nathan,
Really sorry about the delay here.
I'm actually out on leave at the moment, and didn't get things wrapped up before I went.
(I'm 1 week into 4 week parental leave, and got sick the week I was supposed to be handing things off).

@kadircet, can you finish the review here so we can get this landed?
My main concern is I think this can be further simplified by always fetching all ancestors, and treating "fill descendants" as basically a separate operation.
If it's not clear how to proceed there, we can land this and I can work on simplifying when I get back.
Cheers, Sam

clang-tools-extra/clangd/ClangdServer.cpp

530 ↗

(On Diff #186947)

nit: decltype(CB) CB is I think a little more readable (once you're used to the idiom)

clang-tools-extra/clangd/Protocol.cpp

830 ↗

(On Diff #189065)

use ObjectMapper here? It's more idiomatic and avoids the issues below.

831 ↗

(On Diff #189065)

this seems confused - if there is a "resolve" field, but it's not a valid integer, then we should return false (fail to decode)

832 ↗

(On Diff #189065)

prefer to initialize it inline in the struct, rather than manually initializing in failure cases.
As written, if the "resolve" field isn't present at all, the field will be uninitialized.

860 ↗

(On Diff #189065)

nit: this happens in lots of places, and we don't usually add a comment in each.
return std::move(Result); should be enough.

(technically I think this *isn't* legal in C++11, as DR1579 was only addressed in 14. But most compilers backport it...)

clang-tools-extra/clangd/Protocol.h

1025 ↗

(On Diff #189065)

= 0

clang-tools-extra/clangd/XRefs.cpp

990 ↗

(On Diff #186947)

this kind of interpreting of request messages should be a few layers up: probably TypeHierarchyRequest should just have a TypeHierarchyDirection direction = Parents and replace it if present while parsing.

885 ↗

(On Diff #189065)

The scope and complexity of this function seems unneccesarily large:

• it's (in future?) capable of resolving in both directions
• it calls itself recursively, modifying TypeHierarchyDirection to control the search
• it handles levels, even though this optimization is only important for derived types

Can we restrict this to retrieving (all) recursive base types?
i.e. Optional<TypeHierarchyItem> getTypeAncestors(const CXXRecordDecl &CXXRD, ASTContext &Ctx)
Then later, subtype resolution can be the job of another function: resolveTypeDescendants(TypeHierarchyItem& Item, int depth)

That way the recursion of getTypeAncestors is simpler to understand, as it has much smaller scope. And code sharing between the two LSP calls is clearer: fetching type hierarchy is a call to getTypeAncestors and a call to resolveTypeDescendants (if direction is children or both, and resolve is > 0), and resolving a hierarchy is a call to resolveTypeDescendants.

clang-tools-extra/clangd/XRefs.h

65 ↗

(On Diff #189065)

the name says "ancestors" (i.e. recursive) but the implementation is parents (non-recursive). I guess the name should change?

72 ↗

(On Diff #189065)

XRefs.h isn't a suitable place to expose such a function.
It seems to be called only in one place in XRefs.cpp now, which doesn't need to be changed in this patch, can we revert the change?

If you do need to keep the function, I think it can be private.

[nridge]

clang-tools-extra/clangd/Protocol.cpp

830 ↗

(On Diff #189065)

The reason I didn't use ObjectMapper is that I didn't know how to use it while also reusing the fromJSON() method for the base class, TextDocumentPositionParams.

I suppose I could just not reuse it (i.e. mention the fields of TextDocumentPositionParams in this function directly).

clang-tools-extra/clangd/XRefs.cpp

885 ↗

(On Diff #189065)

If we remove "levels" here, should we introduce some kind of guard for infinite recursion, in case the user writes something like:

template <int N>
struct S : S<N + 1> {};

S<0> s;

[nridge]

Address latest review comments

[nridge]

Address a couple of outstanding TODOs

[kadircet]

clang-tools-extra/clangd/ClangdServer.cpp

365 ↗

(On Diff #189114)

Can you revert this change?

clang-tools-extra/clangd/FindSymbols.h

16 ↗

(On Diff #189114)

this should rather be clang/Index/IndexSymbol.h. index::SymbolKind resides in that header.

21 ↗

(On Diff #189114)

I don't think these two are necessary inside header file.

clang-tools-extra/clangd/Protocol.cpp

871 ↗

(On Diff #189114)

Shouldn't we fail if some of the above fields(like name) fails to decode ?

clang-tools-extra/clangd/XRefs.cpp

885 ↗

(On Diff #189065)

clang should be limiting recursive template instantiations. Also since we are just traversing the AST produced by clang, it should never be infinite, but still a nice test case can you add one?

918 ↗

(On Diff #189114)

Nit: Get rid of CXXRD and return inside if/else branches.

924 ↗

(On Diff #189114)

why not use a for-range loop ? (CXXRD->bases())

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

1562 ↗

(On Diff #189114)

Can you put a TODO?

1809 ↗

(On Diff #189114)

I suppose parent resolving should not depend on level, so what about setting it to 0 instead of 10 so that test is consistent even after "child resolution" implementation?

[sammccall]

Thanks for picking this up... just wanted to leave one last comment as I'd been thinking about the recursive template case too.

clang-tools-extra/clangd/XRefs.cpp

885 ↗

(On Diff #189065)

I think there is a point here...

Consider our S template with the direction reversed and a base case specialized:

template <int N>
struct S : S<N - 1> {};
template<>
struct S<0>{};

S<2> instance;

Now the hierarchy of S<2> is well defined and finite: S<2> : S<1> : S<0>.
However IIUC the CXXRecordDecl for S<2> is the instantiation of the primary template, whose base is S<N - 1>, which is dependent[1], so the base's CXXRecordDecl is the primary template, whose base is S<N - 1>... and we never reach the base case.

Actually I'm not sure whether this happens if the base is dependent merely where it's spelled, or still dependent after instantiation? Even in the latter case one can construct examples where we'll infloop:

template <int N>
struct Foo {
  S<N> instance;
}

Trying to get the hierarchy on S<N> could infloop. (I agree these should both be test cases)

What's the Right Thing?

• not sure about a recursion limit, as showing 10 S<N-1>s in the hierarchy is silly.
• not sure about bailing out on dependent types either, as knowing that e.g. my SmallSet<T> inherits from SmallMap<T, bool> is meaningful or useful.
• maybe we should bail out once we see instantiations of the same template decl twice in a parent chain. I.e. keep the seen non-null CXXRecordDecl->getTemplateInstantiationPattern()s in a set and stop recursing if insertion fails.

However for this patch I'd suggest just bailing out on dependent types with a TODO as the simplest, this is an edge case that can be fixed later.

[nridge]

Address most of the latest review comments.

The infinite recursion issue remains to be fixed.

[nridge]

clang-tools-extra/clangd/ClangdServer.cpp

365 ↗

(On Diff #189114)

I tried, but clang-format automatically makes the change again.

Is there some particular clang-format configuration I should apply, so it produces the same results? I don't currently have any configuration, i.e. I think it's just reading the .clang-format file in the monorepo root.

clang-tools-extra/clangd/XRefs.cpp

885 ↗

(On Diff #189065)

The current patch does actually recurse infinitely on this test case, likely for the reasons Sam outlined (our handling of dependent types), and eventually runs into the segfault.

I will update the patch to address this.

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

1562 ↗

(On Diff #189114)

I added a comment to clarify that a field does not unambiguously specify a record type. i don't think there's anything further "to do" here.

[nridge]

clang-tools-extra/clangd/XRefs.cpp

885 ↗

(On Diff #189065)

I meant to say "eventually runs into a stack overflow".

[kadircet]

clang-tools-extra/clangd/ClangdServer.cpp

365 ↗

(On Diff #189114)

That's what we use as well(and your formatted version is correct), but unfortunately sometimes people send out changes with wrong formatting and they are hard to notice during review. Generally we try not to touch those lines in irrelevant patches to keep blame clean.

If you are running clang-format directly you can instead try clang-format-diff to format only changed lines. But not that crucial.

[nridge]

Address the infinite recursion issue

[nridge]

The updated patch addresses the infinite recursion issue by bailing on dependent bases for now, as Sam suggested. I will implement the more comprehensive suggested fix ("bail out once we see instantiations of the same template decl twice in a parent chain") in a follow-up patch. I did add all three testcases that have come up during discussion.

I believe all review comments to date are addressed now.

clang-tools-extra/clangd/ClangdServer.cpp

365 ↗

(On Diff #189114)

I'm not running clang-format directly, VSCode's clang-format extension is doing so automatically upon every file-save. I have not found an option to configure it to format only changed lines.

Would it help if I moved the formatting corrections to their own patch (and made this patch depend on that)?

[nridge]

Fix a (somewhat amusing) typo where I wrote '0' instead of 'O' in a fromJSON() implementation

(Does the fact that this didn't cause any test failures suggest that the fromJSON() functions aren't exercised by any tests?)

[nridge]

Unfortunately, there is a further problem: the Theia client-side implementation of type hierarchy has recently merged, and their code has changed so that they do require typeHierarchy/resolve to be supported. They ask for 1 level in the initial request, ignore any extra levels the server might send, and ask for extra levels using typeHierarchy/resolve instead.

What should we do here -- seek to change Theia, or implement typeHierachy/resolve for supertypes after all?

[kadircet]

In D56370#1424177, @nridge wrote:

Fix a (somewhat amusing) typo where I wrote '0' instead of 'O' in a fromJSON() implementation

(Does the fact that this didn't cause any test failures suggest that the fromJSON() functions aren't exercised by any tests?)

Unfortunately we usually test LSP layer with lit tests, and since we don't have any lit tests for this use-case it wasn't caught. Could you add a lit test for overall use case? You can see examples inside clang-tools-extra/test/clangd/ folder.

In D56370#1424180, @nridge wrote:

Unfortunately, there is a further problem: the Theia client-side implementation of type hierarchy has recently merged, and their code has changed so that they do require typeHierarchy/resolve to be supported. They ask for 1 level in the initial request, ignore any extra levels the server might send, and ask for extra levels using typeHierarchy/resolve instead.

What should we do here -- seek to change Theia, or implement typeHierachy/resolve for supertypes after all?

Looking at https://github.com/theia-ide/theia/pull/3802#issuecomment-455992523 inside theia's implementation of this feature, I believe these are all subject to change.
So let's leave it as it is, even if it would mean you will be able to get only one level of parents knowledge in theia for now. I believe it should be addressed in theia's implementation and proposal itself(which is acutally addressed by sam, https://github.com/Microsoft/vscode-languageserver-node/pull/426/files#r255416980)
And if the conclusion happens to be in favor of theia's current implementation we can always change current implementation to respond to those queries as well.

clang-tools-extra/clangd/ClangdServer.cpp

365 ↗

(On Diff #189114)

it is not that important, nvm.

[kadircet]

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

1496 ↗

(On Diff #190041)

Sorry for not pointing this out before, but it would be great if you could move related tests into a new file, XRefsTests is getting out of hand.

Feel free to ignore if you don't feel like it.

1834 ↗

(On Diff #190041)

Could you also check for the response, since parent traversal for these cases are also disabled currently(due to dependent types issue).
So that we won't forget to fix any issues regarding these cases.
I suppose, a check with only current symbol and empty parents and children should be enough. Same for other two cases.

[nridge]

In D56370#1424180, @nridge wrote:

Unfortunately, there is a further problem: the Theia client-side implementation of type hierarchy has recently merged, and their code has changed so that they do require typeHierarchy/resolve to be supported. They ask for 1 level in the initial request, ignore any extra levels the server might send, and ask for extra levels using typeHierarchy/resolve instead.

What should we do here -- seek to change Theia, or implement typeHierachy/resolve for supertypes after all?

Looking at https://github.com/theia-ide/theia/pull/3802#issuecomment-455992523 inside theia's implementation of this feature, I believe these are all subject to change.

Note, that is a fairly old comment, and as mentioned the PR in question has recently merged.

So let's leave it as it is, even if it would mean you will be able to get only one level of parents knowledge in theia for now. I believe it should be addressed in theia's implementation and proposal itself(which is acutally addressed by sam, https://github.com/Microsoft/vscode-languageserver-node/pull/426/files#r255416980)
And if the conclusion happens to be in favor of theia's current implementation we can always change current implementation to respond to those queries as well.

Ok, I filed a Theia issue about it for now.

[nridge]

In D56370#1426234, @kadircet wrote:

Unfortunately we usually test LSP layer with lit tests, and since we don't have any lit tests for this use-case it wasn't caught. Could you add a lit test for overall use case? You can see examples inside clang-tools-extra/test/clangd/ folder.

Are these tests written manually, or with the help or some kind of tool?

[nridge]

Address remaining review comments

(I figure out how to write a lit test)

[kadircet]

In D56370#1427075, @nridge wrote:

Ok, I filed a Theia issue about it for now.

Thanks!

In D56370#1427076, @nridge wrote:

Are these tests written manually, or with the help or some kind of tool?

Yes unfortunately :(

Thanks for moving the tests!

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

1 ↗

(On Diff #190375)

why strict-whitespace?

[ioeric]

just a few drive-by comments ;)

clang-tools-extra/clangd/FindSymbols.h

28 ↗

(On Diff #190375)

This could probably live in Protocol.h.

clang-tools-extra/clangd/XRefs.cpp

957 ↗

(On Diff #190375)

nit: s/TODO/FIXME(owner)/

same elsewhere.

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

154 ↗

(On Diff #190375)

why are we pulling this into the header? This still seems to be only used in SymbolCollector.cpp.

[ilya-biryukov]

A few small NITs

clang-tools-extra/clangd/ClangdServer.h

188 ↗

(On Diff #190375)

Could you rename it to typeHierarchy?
We try to keep these method names aligned with the LSP methods.

clang-tools-extra/clangd/XRefs.h

62 ↗

(On Diff #190375)

This method looks like an implementation detail and does not align with other methods in XRefs.h which are high-level methods that implement LSP functionality.

It would be more appropriate to move it to AST.h or directly into the XRefs.cpp. WDYT?

[nridge]

clang-tools-extra/clangd/XRefs.h

62 ↗

(On Diff #190375)

@sammccall asked for this method to be exposed in the header and some of the tests written in terms of it.

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

154 ↗

(On Diff #190375)

You're right. This is a leftover from an earlier version of the patch.

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

1 ↗

(On Diff #190375)

That's what the other lit tests seem to do, I just copied it :)

[nridge]

Address latest review comments

[ilya-biryukov]

clang-tools-extra/clangd/XRefs.h

62 ↗

(On Diff #190375)

LG, thanks for the clarification. I haven't been following the review closely.
Having methods that return pointers in XRefs.h seems like the wrong layering to me, but in any case it's a minor detail.

[kadircet]

LGTM, thanks Nathan!

[nridge]

Great, thanks for the reviews!

Could you commit the patch as well?

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

void onDocumentHighlight(const TextDocumentPositionParams &,
                            Callback<std::vector<DocumentHighlight>>);
   void onFileEvent(const DidChangeWatchedFilesParams &);
   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 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

Reply(llvm::json::Object{
             {"workspaceSymbolProvider", true},
             {"referencesProvider", true},
             {"executeCommandProvider",
              llvm::json::Object{
                  {"commands",
                   {ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND,
                    ExecuteCommandParams::CLANGD_APPLY_TWEAK}},
              }},
+            {"typeHierarchyProvider", true},
         }}}});
 }
 
 void ClangdLSPServer::onShutdown(const ShutdownParams &Params,
                                  Callback<std::nullptr_t> Reply) {
   // Do essentially nothing, just say we're ready to exit.
   ShutdownRequestReceived = true;
   Reply(nullptr);

 }
 
 void ClangdLSPServer::onHover(const TextDocumentPositionParams &Params,
                               Callback<llvm::Optional<Hover>> Reply) {
   Server->findHover(Params.textDocument.uri.file(), Params.position,
                     std::move(Reply));
 }
 
+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::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(class Transport &Transp,
   MsgHandler->bind("textDocument/documentHighlight", &ClangdLSPServer::onDocumentHighlight);
   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);
   // clang-format on
 }
 
 ClangdLSPServer::~ClangdLSPServer() = default;
 
 bool ClangdLSPServer::run() {
   // Run the Language Server loop.
   bool CleanExit = true;

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

public:
   /// Get document highlights for a given position.
   void findDocumentHighlights(PathRef File, Position Pos,
                               Callback<std::vector<DocumentHighlight>> CB);
 
   /// Get code hover for a given position.
   void findHover(PathRef File, Position Pos,
                  Callback<llvm::Optional<Hover>> 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);
+
   /// 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);
 

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

void ClangdServer::enumerateTweaks(PathRef File, Range Sel,
   };
 
   WorkScheduler.runWithAST("EnumerateTweaks", File,
                            Bind(Action, std::move(CB), File.str()));
 }
 
 void ClangdServer::applyTweak(PathRef File, Range Sel, StringRef TweakID,
                               Callback<tooling::Replacements> CB) {
-  auto Action = [Sel](decltype(CB) CB, std::string File,
-                            std::string TweakID,
-                            Expected<InputsAndAST> InpAST) {
+  auto Action = [Sel](decltype(CB) CB, std::string File, std::string TweakID,
     if (!InpAST)
       return CB(InpAST.takeError());
     auto Selection = tweakSelection(Sel, *InpAST);
     if (!Selection)
       return CB(Selection.takeError());
     auto A = prepareTweak(TweakID, *Selection);
     if (!A)
       return CB(A.takeError());
auto Action = [Pos](Callback<llvm::Optional<Hover>> CB,
     if (!InpAST)
       return CB(InpAST.takeError());
     CB(clangd::getHover(InpAST->AST, Pos));
   };
 
   WorkScheduler.runWithAST("Hover", File, Bind(Action, std::move(CB)));
 }
 
+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) {
+    if (!InpAST)
+      return CB(InpAST.takeError());
+    CB(clangd::getTypeHierarchy(InpAST->AST, Pos, Resolve, Direction));
+  };
+
+  WorkScheduler.runWithAST("Type Hierarchy", File, Bind(Action, std::move(CB)));
+}
+
 tooling::CompileCommand ClangdServer::getCompileCommand(PathRef File) {
   trace::Span Span("GetCompileCommand");
   llvm::Optional<tooling::CompileCommand> C = CDB.getCompileCommand(File);
   if (!C) // FIXME: Suppress diagnostics? Let the user know?
     C = CDB.getFallbackCommand(File);
   return std::move(*C);
 }
 

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

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

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

 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/ScopedPrinter.h"
 
 #define DEBUG_TYPE "FindSymbols"
 
 namespace clang {
 namespace clangd {
-namespace {
-
-// Convert a index::SymbolKind to clangd::SymbolKind (LSP)
-// Note, some are not perfect matches and should be improved when this LSP
-// issue is addressed:
-// https://github.com/Microsoft/language-server-protocol/issues/344
-SymbolKind indexSymbolKindToSymbolKind(index::SymbolKind Kind) {
-  switch (Kind) {
-  case index::SymbolKind::Unknown:
-    return SymbolKind::Variable;
-  case index::SymbolKind::Module:
-    return SymbolKind::Module;
-  case index::SymbolKind::Namespace:
-    return SymbolKind::Namespace;
-  case index::SymbolKind::NamespaceAlias:
-    return SymbolKind::Namespace;
-  case index::SymbolKind::Macro:
-    return SymbolKind::String;
-  case index::SymbolKind::Enum:
-    return SymbolKind::Enum;
-  case index::SymbolKind::Struct:
-    return SymbolKind::Struct;
-  case index::SymbolKind::Class:
-    return SymbolKind::Class;
-  case index::SymbolKind::Protocol:
-    return SymbolKind::Interface;
-  case index::SymbolKind::Extension:
-    return SymbolKind::Interface;
-  case index::SymbolKind::Union:
-    return SymbolKind::Class;
-  case index::SymbolKind::TypeAlias:
-    return SymbolKind::Class;
-  case index::SymbolKind::Function:
-    return SymbolKind::Function;
-  case index::SymbolKind::Variable:
-    return SymbolKind::Variable;
-  case index::SymbolKind::Field:
-    return SymbolKind::Field;
-  case index::SymbolKind::EnumConstant:
-    return SymbolKind::EnumMember;
-  case index::SymbolKind::InstanceMethod:
-  case index::SymbolKind::ClassMethod:
-  case index::SymbolKind::StaticMethod:
-    return SymbolKind::Method;
-  case index::SymbolKind::InstanceProperty:
-  case index::SymbolKind::ClassProperty:
-  case index::SymbolKind::StaticProperty:
-    return SymbolKind::Property;
-  case index::SymbolKind::Constructor:
-  case index::SymbolKind::Destructor:
-    return SymbolKind::Method;
-  case index::SymbolKind::ConversionFunction:
-    return SymbolKind::Function;
-  case index::SymbolKind::Parameter:
-    return SymbolKind::Variable;
-  case index::SymbolKind::Using:
-    return SymbolKind::Namespace;
-  }
-  llvm_unreachable("invalid symbol kind");
-}
 
+namespace {
 using ScoredSymbolInfo = std::pair<float, SymbolInformation>;
 struct ScoredSymbolGreater {
   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.
   }
 };

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

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_PROTOCOL_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_PROTOCOL_H
 
 #include "URI.h"
 #include "index/SymbolID.h"
+#include "clang/Index/IndexSymbol.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/Support/JSON.h"
 #include <bitset>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {

 bool fromJSON(const llvm::json::Value &, SymbolKind &);
 constexpr auto SymbolKindMin = static_cast<size_t>(SymbolKind::File);
 constexpr auto SymbolKindMax = static_cast<size_t>(SymbolKind::TypeParameter);
 using SymbolKindBitset = std::bitset<SymbolKindMax + 1>;
 bool fromJSON(const llvm::json::Value &, SymbolKindBitset &);
 SymbolKind adjustKindToCapability(SymbolKind Kind,
                                   SymbolKindBitset &supportedSymbolKinds);
 
+// Convert a index::SymbolKind to clangd::SymbolKind (LSP)
+// Note, some are not perfect matches and should be improved when this LSP
+// issue is addressed:
+// https://github.com/Microsoft/language-server-protocol/issues/344
+SymbolKind indexSymbolKindToSymbolKind(index::SymbolKind Kind);
+
 // This struct doesn't mirror LSP!
 // The protocol defines deeply nested structures for client capabilities.
 // Instead of mapping them all, this just parses out the bits we care about.
 struct ClientCapabilities {
   /// The supported set of SymbolKinds for workspace/symbol.
   /// workspace.symbol.symbolKind.valueSet
   llvm::Optional<SymbolKindBitset> WorkspaceSymbolKinds;
 
struct DocumentHighlight {
   friend bool operator==(const DocumentHighlight &LHS,
                          const DocumentHighlight &RHS) {
     return LHS.kind == RHS.kind && LHS.range == RHS.range;
   }
 };
 llvm::json::Value toJSON(const DocumentHighlight &DH);
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const DocumentHighlight &);
 
+enum class TypeHierarchyDirection { Children = 0, Parents = 1, Both = 2 };
+bool fromJSON(const llvm::json::Value &E, TypeHierarchyDirection &Out);
+
+/// 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 {
+  /// The hierarchy levels to resolve. `0` indicates no level.
+  int resolve = 0;
+
+  /// The direction of the hierarchy levels to resolve.
+  TypeHierarchyDirection direction = TypeHierarchyDirection::Parents;
+};
+bool fromJSON(const llvm::json::Value &, TypeHierarchyParams &);
+
+struct TypeHierarchyItem {
+  /// The human readable name of the hierarchy 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.
+  SymbolKind kind;
+
+  /// `true` if the hierarchy item is deprecated. Otherwise, `false`.
+  bool deprecated;
+
+  /// 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.
+  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`.
+  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.
+  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.
+};
+llvm::json::Value toJSON(const TypeHierarchyItem &);
+llvm::raw_ostream &operator<<(llvm::raw_ostream &, const TypeHierarchyItem &);
+
 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.
 struct FileStatus {

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

case SymbolKind::Struct:
     return SymbolKind::Class;
   case SymbolKind::EnumMember:
     return SymbolKind::Enum;
   default:
     return SymbolKind::String;
   }
 }
 
+SymbolKind indexSymbolKindToSymbolKind(index::SymbolKind Kind) {
+  switch (Kind) {
+  case index::SymbolKind::Unknown:
+    return SymbolKind::Variable;
+  case index::SymbolKind::Module:
+    return SymbolKind::Module;
+  case index::SymbolKind::Namespace:
+    return SymbolKind::Namespace;
+  case index::SymbolKind::NamespaceAlias:
+    return SymbolKind::Namespace;
+  case index::SymbolKind::Macro:
+    return SymbolKind::String;
+  case index::SymbolKind::Enum:
+    return SymbolKind::Enum;
+  case index::SymbolKind::Struct:
+    return SymbolKind::Struct;
+  case index::SymbolKind::Class:
+    return SymbolKind::Class;
+  case index::SymbolKind::Protocol:
+    return SymbolKind::Interface;
+  case index::SymbolKind::Extension:
+    return SymbolKind::Interface;
+  case index::SymbolKind::Union:
+    return SymbolKind::Class;
+  case index::SymbolKind::TypeAlias:
+    return SymbolKind::Class;
+  case index::SymbolKind::Function:
+    return SymbolKind::Function;
+  case index::SymbolKind::Variable:
+    return SymbolKind::Variable;
+  case index::SymbolKind::Field:
+    return SymbolKind::Field;
+  case index::SymbolKind::EnumConstant:
+    return SymbolKind::EnumMember;
+  case index::SymbolKind::InstanceMethod:
+  case index::SymbolKind::ClassMethod:
+  case index::SymbolKind::StaticMethod:
+    return SymbolKind::Method;
+  case index::SymbolKind::InstanceProperty:
+  case index::SymbolKind::ClassProperty:
+  case index::SymbolKind::StaticProperty:
+    return SymbolKind::Property;
+  case index::SymbolKind::Constructor:
+  case index::SymbolKind::Destructor:
+    return SymbolKind::Method;
+  case index::SymbolKind::ConversionFunction:
+    return SymbolKind::Function;
+  case index::SymbolKind::Parameter:
+    return SymbolKind::Variable;
+  case index::SymbolKind::Using:
+    return SymbolKind::Namespace;
+  }
+  llvm_unreachable("invalid symbol kind");
+}
+
 bool fromJSON(const llvm::json::Value &Params, ClientCapabilities &R) {
   const llvm::json::Object *O = Params.getAsObject();
   if (!O)
     return false;
   if (auto *TextDocument = O->getObject("textDocument")) {
     if (auto *Diagnostics = TextDocument->getObject("publishDiagnostics")) {
       if (auto CategorySupport = Diagnostics->getBoolean("categorySupport"))
         R.DiagnosticCategory = *CategorySupport;
bool fromJSON(const llvm::json::Value &Params, InitializationOptions &Opts) {
 
   fromJSON(Params, Opts.ConfigSettings);
   O.map("compilationDatabasePath", Opts.compilationDatabasePath);
   O.map("fallbackFlags", Opts.fallbackFlags);
   O.map("clangdFileStatus", Opts.FileStatus);
   return true;
 }
 
+bool fromJSON(const llvm::json::Value &E, TypeHierarchyDirection &Out) {
+  auto T = E.getAsInteger();
+  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) {
+  llvm::json::ObjectMapper O(Params);
+  return O && O.map("textDocument", R.textDocument) &&
+         O.map("position", R.position) && O.map("resolve", R.resolve) &&
+         O.map("direction", R.direction);
+}
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &O,
+                              const TypeHierarchyItem &I) {
+  return O << I.name << " - " << toJSON(I);
+}
+
+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}};
+
+  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;
+  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);
+
+  return true;
+}
+
 bool fromJSON(const llvm::json::Value &Params, ReferenceParams &R) {
   TextDocumentPositionParams &Base = R;
   return fromJSON(Params, Base);
 }
 
 } // namespace clangd
 } // namespace clang

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

 /// \p Limit limits the number of results returned (0 means no limit).
 std::vector<Location> 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);
+
+/// 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);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_XREFS_H

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

 //===--- XRefs.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 "XRefs.h"
 #include "AST.h"
+#include "FindSymbols.h"
 #include "Logger.h"
 #include "SourceCode.h"
 #include "URI.h"
 #include "index/Merge.h"
+#include "index/SymbolCollector.h"
 #include "index/SymbolLocation.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/Type.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Index/USRGeneration.h"
 #include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {

 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const LocatedSymbol &S) {
   OS << S.Name << ": " << S.PreferredDeclaration;
   if (S.Definition)
     OS << " def=" << *S.Definition;
   return OS;
 }
 
+// FIXME(nridge): Reduce duplication between this function and declToSym().
+static llvm::Optional<TypeHierarchyItem>
+declToTypeHierarchyItem(ASTContext &Ctx, const NamedDecl &ND) {
+  auto &SM = Ctx.getSourceManager();
+
+  SourceLocation NameLoc = findNameLoc(&ND);
+  // getFileLoc is a good choice for us, but we also need to make sure
+  // sourceLocToPosition won't switch files, so we call getSpellingLoc on top of
+  // that to make sure it does not switch files.
+  // FIXME: sourceLocToPosition should not switch files!
+  SourceLocation BeginLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getBeginLoc()));
+  SourceLocation EndLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getEndLoc()));
+  if (NameLoc.isInvalid() || BeginLoc.isInvalid() || EndLoc.isInvalid())
+    return llvm::None;
+
+  Position NameBegin = sourceLocToPosition(SM, NameLoc);
+  Position NameEnd = sourceLocToPosition(
+      SM, Lexer::getLocForEndOfToken(NameLoc, 0, SM, Ctx.getLangOpts()));
+
+  index::SymbolInfo SymInfo = index::getSymbolInfo(&ND);
+  // FIXME: this is not classifying constructors, destructors and operators
+  //        correctly (they're all "methods").
+  SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind);
+
+  TypeHierarchyItem THI;
+  THI.name = printName(Ctx, ND);
+  THI.kind = SK;
+  THI.deprecated = ND.isDeprecated();
+  THI.range =
+      Range{sourceLocToPosition(SM, BeginLoc), sourceLocToPosition(SM, EndLoc)};
+  THI.selectionRange = Range{NameBegin, NameEnd};
+  if (!THI.range.contains(THI.selectionRange)) {
+    // 'selectionRange' must be contained in 'range', so in cases where clang
+    // reports unrelated ranges we need to reconcile somehow.
+    THI.range = THI.selectionRange;
+  }
+
+  auto FilePath =
+      getCanonicalPath(SM.getFileEntryForID(SM.getFileID(BeginLoc)), SM);
+  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> getTypeAncestors(const CXXRecordDecl &CXXRD,
+                                                    ASTContext &ASTCtx) {
+  Optional<TypeHierarchyItem> Result = declToTypeHierarchyItem(ASTCtx, CXXRD);
+  if (!Result)
+    return Result;
+
+  Result->parents.emplace();
+
+  for (const CXXRecordDecl *ParentDecl : typeParents(&CXXRD)) {
+    if (Optional<TypeHierarchyItem> ParentSym =
+            getTypeAncestors(*ParentDecl, ASTCtx)) {
+      Result->parents->emplace_back(std::move(*ParentSym));
+    }
+  }
+
+  return Result;
+}
+
+const CXXRecordDecl *findRecordTypeAt(ParsedAST &AST, Position Pos) {
+  ASTContext &ASTCtx = AST.getASTContext();
+  const SourceManager &SourceMgr = ASTCtx.getSourceManager();
+  SourceLocation SourceLocationBeg =
+      getBeginningOfIdentifier(AST, Pos, SourceMgr.getMainFileID());
+  IdentifiedSymbol Symbols = getSymbolAtPosition(AST, SourceLocationBeg);
+  if (Symbols.Decls.empty())
+    return nullptr;
+
+  const Decl *D = Symbols.Decls[0];
+
+  if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
+    // If this is a variable, use the type of the variable.
+    return VD->getType().getTypePtr()->getAsCXXRecordDecl();
+  }
+
+  if (const CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(D)) {
+    // If this is a method, use the type of the class.
+    return Method->getParent();
+  }
+
+  // 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);
+}
+
+std::vector<const CXXRecordDecl *> typeParents(const CXXRecordDecl *CXXRD) {
+  std::vector<const CXXRecordDecl *> Result;
+
+  for (auto Base : CXXRD->bases()) {
+    const CXXRecordDecl *ParentDecl = nullptr;
+
+    const Type *Type = Base.getType().getTypePtr();
+    if (const RecordType *RT = Type->getAs<RecordType>()) {
+      ParentDecl = RT->getAsCXXRecordDecl();
+    }
+
+    // For now, do not handle dependent bases such as "Base<T>".
+    // We would like to handle them by heuristically choosing the
+    // primary template declaration, but we need to take care to
+    // avoid infinite recursion.
+
+    if (ParentDecl)
+      Result.push_back(ParentDecl);
+  }
+
+  return Result;
+}
+
+llvm::Optional<TypeHierarchyItem>
+getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
+                 TypeHierarchyDirection Direction) {
+  const CXXRecordDecl *CXXRD = findRecordTypeAt(AST, Pos);
+  if (!CXXRD)
+    return llvm::None;
+
+  Optional<TypeHierarchyItem> Result =
+      getTypeAncestors(*CXXRD, AST.getASTContext());
+  // FIXME(nridge): Resolve type descendants if direction is Children or Both,
+  // and ResolveLevels > 0.
+  return Result;
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/index/SymbolCollector.h

bool handleMacroOccurence(const IdentifierInfo *Name, const MacroInfo *MI,
                             SourceLocation Loc) override;
 
   SymbolSlab takeSymbols() { return std::move(Symbols).build(); }
   RefSlab takeRefs() { return std::move(Refs).build(); }
 
   void finish() override;
 
 private:
-  const Symbol *addDeclaration(const NamedDecl &, SymbolID, bool IsMainFileSymbol);
+  const Symbol *addDeclaration(const NamedDecl &, SymbolID,
+                               bool IsMainFileSymbol);
   void addDefinition(const NamedDecl &, const Symbol &DeclSymbol);
 
   // All Symbols collected from the AST.
   SymbolSlab::Builder Symbols;
   // All refs collected from the AST.
   // Only symbols declared in preamble (from #include) and referenced from the
   // main file will be included.
   RefSlab::Builder Refs;

clang-tools-extra/trunk/clangd/index/SymbolCollector.cpp

bool IsOnlyRef =
       !(Roles & (static_cast<unsigned>(index::SymbolRole::Declaration) |
                  static_cast<unsigned>(index::SymbolRole::Definition)));
 
   if (IsOnlyRef && !CollectRef)
     return true;
 
   // ND is the canonical (i.e. first) declaration. If it's in the main file,
   // then no public declaration was visible, so assume it's main-file only.
-  bool IsMainFileOnly = SM.isWrittenInMainFile(SM.getExpansionLoc(
-    ND->getBeginLoc()));
+  bool IsMainFileOnly =
+      SM.isWrittenInMainFile(SM.getExpansionLoc(ND->getBeginLoc()));
   if (!shouldCollectSymbol(*ND, *ASTCtx, Opts, IsMainFileOnly))
     return true;
   // Do not store references to main-file symbols.
   if (CollectRef && !IsMainFileOnly && !isa<NamespaceDecl>(ND) &&
       (Opts.RefsInHeaders || SM.getFileID(SpellingLoc) == SM.getMainFileID()))
     DeclRefs[ND].emplace_back(SpellingLoc, Roles);
   // Don't continue indexing if this is a mere reference.
   if (IsOnlyRef)
void SymbolCollector::finish() {
   }
 
   ReferencedDecls.clear();
   ReferencedMacros.clear();
   DeclRefs.clear();
   FilesToIndexCache.clear();
 }
 
-const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND,
-                                              SymbolID ID,
+const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND, SymbolID ID,
                                               bool IsMainFileOnly) {
   auto &Ctx = ND.getASTContext();
   auto &SM = Ctx.getSourceManager();
 
   Symbol S;
   S.ID = std::move(ID);
   std::string QName = printQualifiedName(ND);
   std::tie(S.Scope, S.Name) = splitQualifiedName(QName);

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

 # CHECK-NEXT:      "renameProvider": true,
 # CHECK-NEXT:      "signatureHelpProvider": {
 # CHECK-NEXT:        "triggerCharacters": [
 # CHECK-NEXT:          "(",
 # CHECK-NEXT:          ","
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "textDocumentSync": 2,
+# CHECK-NEXT:      "typeHierarchyProvider": true
 # CHECK-NEXT:      "workspaceSymbolProvider": true
 # CHECK-NEXT:    }
 # CHECK-NEXT:  }
 ---
 {"jsonrpc":"2.0","id":3,"method":"shutdown"}
 #      CHECK:  "id": 3,
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": null
 ---
 {"jsonrpc":"2.0","method":"exit"}

clang-tools-extra/trunk/test/clangd/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","id":1,"method":"textDocument/typeHierarchy","params":{"textDocument":{"uri":"test:///main.cpp"},"position":{"line":2,"character":11},"direction":1,"resolve":1}}
+#      CHECK:  "id": 1
+# CHECK-NEXT:  "jsonrpc": "2.0",
+# CHECK-NEXT:  "result": {
+# 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:          {
+# CHECK-NEXT:            "kind": 23,
+# CHECK-NEXT:            "name": "Parent",
+# CHECK-NEXT:            "parents": [],
+# CHECK-NEXT:            "range": {
+# CHECK-NEXT:              "end": {
+# CHECK-NEXT:                "character": 15,
+# 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": 24,
+# 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": 24,
+# 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:  }
+---
+{"jsonrpc":"2.0","id":2,"method":"shutdown"}
+---
+{"jsonrpc":"2.0","method":"exit"}

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

add_extra_unittest(ClangdTests
   SymbolInfoTests.cpp
   SyncAPI.cpp
   TUSchedulerTests.cpp
   TestFS.cpp
   TestIndex.cpp
   TestTU.cpp
   ThreadingTests.cpp
   TraceTests.cpp
+  TypeHierarchyTests.cpp
   TweakTests.cpp
   URITests.cpp
   XRefsTests.cpp
 
   $<TARGET_OBJECTS:obj.clangDaemonTweaks>
   )
 
 target_link_libraries(ClangdTests

clang-tools-extra/trunk/unittests/clangd/Matchers.h

if (ComputedValue) {                                                       \
       ADD_FAILURE() << "expected an error from " << #expectedValue             \
                     << " but got "                                             \
                     << ::testing::PrintToString(*ComputedValue);               \
       break;                                                                   \
     }                                                                          \
     llvm::consumeError(ComputedValue.takeError());                             \
   } while (false)
 
+// Implements the HasValue(m) matcher for matching an Optional whose
+// value matches matcher m.
+template <typename InnerMatcher> class OptionalMatcher {
+public:
+  explicit OptionalMatcher(const InnerMatcher &matcher) : matcher_(matcher) {}
+
+  // This type conversion operator template allows Optional(m) to be
+  // used as a matcher for any Optional type whose value type is
+  // compatible with the inner matcher.
+  //
+  // The reason we do this instead of relying on
+  // MakePolymorphicMatcher() is that the latter is not flexible
+  // enough for implementing the DescribeTo() method of Optional().
+  template <typename Optional> operator Matcher<Optional>() const {
+    return MakeMatcher(new Impl<Optional>(matcher_));
+  }
+
+private:
+  // The monomorphic implementation that works for a particular optional type.
+  template <typename Optional>
+  class Impl : public ::testing::MatcherInterface<Optional> {
+  public:
+    using Value = typename std::remove_const<
+        typename std::remove_reference<Optional>::type>::type::value_type;
+
+    explicit Impl(const InnerMatcher &matcher)
+        : matcher_(::testing::MatcherCast<const Value &>(matcher)) {}
+
+    virtual void DescribeTo(::std::ostream *os) const {
+      *os << "has a value that ";
+      matcher_.DescribeTo(os);
+    }
+
+    virtual void DescribeNegationTo(::std::ostream *os) const {
+      *os << "does not have a value that ";
+      matcher_.DescribeTo(os);
+    }
+
+    virtual bool
+    MatchAndExplain(Optional optional,
+                    ::testing::MatchResultListener *listener) const {
+      if (!optional.hasValue())
+        return false;
+
+      *listener << "which has a value ";
+      return MatchPrintAndExplain(*optional, matcher_, listener);
+    }
+
+  private:
+    const Matcher<const Value &> matcher_;
+
+    GTEST_DISALLOW_ASSIGN_(Impl);
+  };
+
+  const InnerMatcher matcher_;
+
+  GTEST_DISALLOW_ASSIGN_(OptionalMatcher);
+};
+
+// Creates a matcher that matches an Optional that has a value
+// that matches inner_matcher.
+template <typename InnerMatcher>
+inline OptionalMatcher<InnerMatcher>
+HasValue(const InnerMatcher &inner_matcher) {
+  return OptionalMatcher<InnerMatcher>(inner_matcher);
+}
+
 } // namespace clangd
 } // namespace clang
 #endif

clang-tools-extra/trunk/unittests/clangd/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 "Annotations.h"
+#include "ClangdUnit.h"
+#include "Compiler.h"
+#include "Matchers.h"
+#include "SyncAPI.h"
+#include "TestFS.h"
+#include "TestTU.h"
+#include "XRefs.h"
+#include "index/FileIndex.h"
+#include "index/SymbolCollector.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/DeclTemplate.h"
+#include "clang/Index/IndexingAction.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+using testing::AllOf;
+using testing::ElementsAre;
+using testing::Eq;
+using testing::Field;
+using testing::IsEmpty;
+using testing::Matcher;
+using testing::Pointee;
+using testing::UnorderedElementsAreArray;
+
+// 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(FindRecordTypeAt, TypeOrVariable) {
+  Annotations Source(R"cpp(
+struct Ch^ild2 {
+  int c;
+};
+
+int main() {
+  Ch^ild2 ch^ild2;
+  ch^ild2.c = 1;
+}
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  for (Position Pt : Source.points()) {
+    const CXXRecordDecl *RD = findRecordTypeAt(AST, Pt);
+    EXPECT_EQ(&findDecl(AST, "Child2"), static_cast<const NamedDecl *>(RD));
+  }
+}
+
+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();
+
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  for (Position Pt : Source.points()) {
+    const CXXRecordDecl *RD = findRecordTypeAt(AST, Pt);
+    EXPECT_EQ(&findDecl(AST, "Child2"), static_cast<const NamedDecl *>(RD));
+  }
+}
+
+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();
+
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  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);
+  }
+}
+
+TEST(TypeParents, SimpleInheritance) {
+  Annotations Source(R"cpp(
+struct Parent {
+  int a;
+};
+
+struct Child1 : Parent {
+  int b;
+};
+
+struct Child2 : Child1 {
+  int c;
+};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  const CXXRecordDecl *Parent =
+      dyn_cast<CXXRecordDecl>(&findDecl(AST, "Parent"));
+  const CXXRecordDecl *Child1 =
+      dyn_cast<CXXRecordDecl>(&findDecl(AST, "Child1"));
+  const CXXRecordDecl *Child2 =
+      dyn_cast<CXXRecordDecl>(&findDecl(AST, "Child2"));
+
+  EXPECT_THAT(typeParents(Parent), ElementsAre());
+  EXPECT_THAT(typeParents(Child1), ElementsAre(Parent));
+  EXPECT_THAT(typeParents(Child2), ElementsAre(Child1));
+}
+
+TEST(TypeParents, MultipleInheritance) {
+  Annotations Source(R"cpp(
+struct Parent1 {
+  int a;
+};
+
+struct Parent2 {
+  int b;
+};
+
+struct Parent3 : Parent2 {
+  int c;
+};
+
+struct Child : Parent1, Parent3 {
+  int d;
+};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  const CXXRecordDecl *Parent1 =
+      dyn_cast<CXXRecordDecl>(&findDecl(AST, "Parent1"));
+  const CXXRecordDecl *Parent2 =
+      dyn_cast<CXXRecordDecl>(&findDecl(AST, "Parent2"));
+  const CXXRecordDecl *Parent3 =
+      dyn_cast<CXXRecordDecl>(&findDecl(AST, "Parent3"));
+  const CXXRecordDecl *Child = dyn_cast<CXXRecordDecl>(&findDecl(AST, "Child"));
+
+  EXPECT_THAT(typeParents(Parent1), ElementsAre());
+  EXPECT_THAT(typeParents(Parent2), ElementsAre());
+  EXPECT_THAT(typeParents(Parent3), ElementsAre(Parent2));
+  EXPECT_THAT(typeParents(Child), ElementsAre(Parent1, Parent3));
+}
+
+TEST(TypeParents, ClassTemplate) {
+  Annotations Source(R"cpp(
+struct Parent {};
+
+template <typename T>
+struct Child : Parent {};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  const CXXRecordDecl *Parent =
+      dyn_cast<CXXRecordDecl>(&findDecl(AST, "Parent"));
+  const CXXRecordDecl *Child =
+      dyn_cast<ClassTemplateDecl>(&findDecl(AST, "Child"))->getTemplatedDecl();
+
+  EXPECT_THAT(typeParents(Child), ElementsAre(Parent));
+}
+
+MATCHER_P(ImplicitSpecOf, ClassTemplate, "") {
+  const ClassTemplateSpecializationDecl *CTS =
+      dyn_cast<ClassTemplateSpecializationDecl>(arg);
+  return CTS &&
+         CTS->getSpecializedTemplate()->getTemplatedDecl() == ClassTemplate &&
+         CTS->getSpecializationKind() == TSK_ImplicitInstantiation;
+}
+
+// This is similar to findDecl(AST, QName), but supports using
+// a template-id as a query.
+const NamedDecl &findDeclWithTemplateArgs(ParsedAST &AST,
+                                          llvm::StringRef Query) {
+  return findDecl(AST, [&Query](const NamedDecl &ND) {
+    std::string QName;
+    llvm::raw_string_ostream OS(QName);
+    PrintingPolicy Policy(ND.getASTContext().getLangOpts());
+    // Use getNameForDiagnostic() which includes the template
+    // arguments in the printed name.
+    ND.getNameForDiagnostic(OS, Policy, /*Qualified=*/true);
+    OS.flush();
+    return QName == Query;
+  });
+}
+
+TEST(TypeParents, 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 AST = TU.build();
+
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  const CXXRecordDecl *Parent =
+      dyn_cast<ClassTemplateDecl>(&findDecl(AST, "Parent"))->getTemplatedDecl();
+  const CXXRecordDecl *ParentSpec =
+      dyn_cast<CXXRecordDecl>(&findDeclWithTemplateArgs(AST, "Parent<int>"));
+  const CXXRecordDecl *Child1 =
+      dyn_cast<CXXRecordDecl>(&findDecl(AST, "Child1"));
+  const CXXRecordDecl *Child2 =
+      dyn_cast<CXXRecordDecl>(&findDecl(AST, "Child2"));
+
+  EXPECT_THAT(typeParents(Child1), ElementsAre(ImplicitSpecOf(Parent)));
+  EXPECT_THAT(typeParents(Child2), ElementsAre(ParentSpec));
+}
+
+TEST(TypeParents, 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 AST = TU.build();
+
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  const CXXRecordDecl *Parent =
+      dyn_cast<CXXRecordDecl>(&findDecl(AST, "Parent"));
+  const CXXRecordDecl *Child =
+      dyn_cast<ClassTemplateDecl>(&findDecl(AST, "Child"))->getTemplatedDecl();
+  const CXXRecordDecl *ChildSpec =
+      dyn_cast<CXXRecordDecl>(&findDeclWithTemplateArgs(AST, "Child<int>"));
+
+  EXPECT_THAT(typeParents(Child), ElementsAre());
+  EXPECT_THAT(typeParents(ChildSpec), ElementsAre(Parent));
+}
+
+// This is disabled for now, because support for dependent bases
+// requires additional measures to avoid infinite recursion.
+TEST(DISABLED_TypeParents, DependentBase) {
+  Annotations Source(R"cpp(
+template <typename T>
+struct Parent {};
+
+template <typename T>
+struct Child1 : Parent<T> {};
+
+template <typename T>
+struct Child2 : Parent<T>::Type {};
+
+template <typename T>
+struct Child3 : T {};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  const CXXRecordDecl *Parent =
+      dyn_cast<ClassTemplateDecl>(&findDecl(AST, "Parent"))->getTemplatedDecl();
+  const CXXRecordDecl *Child1 =
+      dyn_cast<ClassTemplateDecl>(&findDecl(AST, "Child1"))->getTemplatedDecl();
+  const CXXRecordDecl *Child2 =
+      dyn_cast<ClassTemplateDecl>(&findDecl(AST, "Child2"))->getTemplatedDecl();
+  const CXXRecordDecl *Child3 =
+      dyn_cast<ClassTemplateDecl>(&findDecl(AST, "Child3"))->getTemplatedDecl();
+
+  // For "Parent<T>", use the primary template as a best-effort guess.
+  EXPECT_THAT(typeParents(Child1), ElementsAre(Parent));
+  // For "Parent<T>::Type", there is nothing we can do.
+  EXPECT_THAT(typeParents(Child2), ElementsAre());
+  // Likewise for "T".
+  EXPECT_THAT(typeParents(Child3), ElementsAre());
+}
+
+// Parts of getTypeHierarchy() are tested in more detail by the
+// FindRecordTypeAt.* and TypeParents.* tests above. This test exercises the
+// entire operation.
+TEST(TypeHierarchy, Parents) {
+  Annotations Source(R"cpp(
+struct $Parent1Def[[Parent1]] {
+  int a;
+};
+
+struct $Parent2Def[[Parent2]] {
+  int b;
+};
+
+struct $Parent3Def[[Parent3]] : Parent2 {
+  int c;
+};
+
+struct Ch^ild : Parent1, Parent3 {
+  int d;
+};
+
+int main() {
+  Ch^ild  ch^ild;
+
+  ch^ild.a = 1;
+}
+)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));
+    EXPECT_THAT(
+        *Result,
+        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(
+                              WithName("Parent2"), WithKind(SymbolKind::Struct),
+                              SelectionRangeIs(Source.range("Parent2Def")),
+                              Parents()))))));
+  }
+}
+
+TEST(TypeHierarchy, RecursiveHierarchy1) {
+  Annotations Source(R"cpp(
+  template <int N>
+  struct S : S<N + 1> {};
+
+  S^<0> s;
+  )cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+
+  // 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.
+  llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
+      AST, Source.points()[0], 0, TypeHierarchyDirection::Parents);
+  ASSERT_TRUE(bool(Result));
+  EXPECT_THAT(*Result,
+              AllOf(WithName("S"), WithKind(SymbolKind::Struct), Parents()));
+}
+
+TEST(TypeHierarchy, RecursiveHierarchy2) {
+  Annotations Source(R"cpp(
+  template <int N>
+  struct S : S<N - 1> {};
+
+  template <>
+  struct S<0>{};
+
+  S^<2> s;
+  )cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  // Make sure getTypeHierarchy() doesn't get into an infinite recursion.
+  llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
+      AST, Source.points()[0], 0, TypeHierarchyDirection::Parents);
+  ASSERT_TRUE(bool(Result));
+  EXPECT_THAT(*Result,
+              AllOf(WithName("S"), WithKind(SymbolKind::Struct), Parents()));
+}
+
+TEST(TypeHierarchy, RecursiveHierarchy3) {
+  Annotations Source(R"cpp(
+  template <int N>
+  struct S : S<N - 1> {};
+
+  template <>
+  struct S<0>{};
+
+  template <int N>
+  struct Foo {
+    S^<N> s;
+  };
+  )cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  // Make sure getTypeHierarchy() doesn't get into an infinite recursion.
+  llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
+      AST, Source.points()[0], 0, TypeHierarchyDirection::Parents);
+  ASSERT_TRUE(bool(Result));
+  EXPECT_THAT(*Result,
+              AllOf(WithName("S"), WithKind(SymbolKind::Struct), Parents()));
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang