[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

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

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

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

901

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

17

it seems like there is no change in file requiring this

226

can you revert this one as well ?

clang-tools-extra/clangd/Protocol.cpp

801

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

1012

why not just use an int then ?

1032

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

clang-tools-extra/clangd/XRefs.cpp

876

again reduce nesting

891

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

llvm::None

925

what about member fields ?

932

reduce nesting

935

Is this mentioned in proposal?

939

llvm::None

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

1355

can you format the code?

1387

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

1012

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

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

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

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

483

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

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

483

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

483

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

483

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

483

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

857

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

857

(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

1550

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

465

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

clang-tools-extra/clangd/Protocol.cpp

814

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

815

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

816

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.

844

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

1011

= 0

clang-tools-extra/clangd/XRefs.cpp

868

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.

964

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.

clang-tools-extra/clangd/XRefs.h

50

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

57

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

814

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

868

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

324–325

Can you revert this change?

clang-tools-extra/clangd/FindSymbols.h

17

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

21

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

clang-tools-extra/clangd/Protocol.cpp

855

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

clang-tools-extra/clangd/XRefs.cpp

868

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?

911

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

917

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

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

1419

Can you put a TODO?

1666

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

868

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

324–325

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

868

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

1419

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

868

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

[kadircet]

clang-tools-extra/clangd/ClangdServer.cpp

324–325

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

324–325

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

324–325

it is not that important, nvm.

[kadircet]

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

1353

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.

1691

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

31

This could probably live in Protocol.h.

clang-tools-extra/clangd/XRefs.cpp

945

nit: s/TODO/FIXME(owner)/

same elsewhere.

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

150

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

176

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

clang-tools-extra/clangd/XRefs.h

47

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

47

@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

150

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

47

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/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 onSuperTypes(const TextDocumentPositionParams &,
+                    Callback<llvm::Optional<DocumentSymbol>>);
   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/clangd/ClangdLSPServer.cpp

Reply(llvm::json::Object{
             {"renameProvider", true},
             {"documentSymbolProvider", true},
             {"workspaceSymbolProvider", true},
             {"referencesProvider", true},
             {"executeCommandProvider",
              llvm::json::Object{
                  {"commands", {ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND}},
              }},
+            {"typeHierarchy", 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::onSuperTypes(const TextDocumentPositionParams &Params,
+                                   Callback<Optional<DocumentSymbol>> Reply) {
+  Server->findSuperTypes(Params.textDocument.uri.file(), Params.position,
+                         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/superTypes", &ClangdLSPServer::onSuperTypes);
   // clang-format on
 }
 
 ClangdLSPServer::~ClangdLSPServer() = default;
 
 bool ClangdLSPServer::run() {
   // Run the Language Server loop.
   bool CleanExit = true;

clang-tools-extra/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 super types for a given position.
+  void findSuperTypes(PathRef File, Position Pos,
+                      Callback<llvm::Optional<DocumentSymbol>> 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/clangd/ClangdServer.cpp

for (const tooling::AtomicChange &Change : ResultCollector.Result->get()) {
       }
     }
     return CB(std::move(Replacements));
   };
 
   WorkScheduler.runWithAST(
       "Rename", File, Bind(Action, File.str(), NewName.str(), std::move(CB)));
 }
 
 void ClangdServer::dumpAST(PathRef File,
                            llvm::unique_function<void(std::string)> Callback) {
   auto Action = [](decltype(Callback) Callback,
                    llvm::Expected<InputsAndAST> InpAST) {
     if (!InpAST) {
       llvm::consumeError(InpAST.takeError());
       return Callback("<no-ast>");
     }
     std::string Result;
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::findSuperTypes(PathRef File, Position Pos,
+                                  Callback<Optional<DocumentSymbol>> CB) {
+  auto Action = [Pos](Callback<Optional<DocumentSymbol>> CB,
+                      Expected<InputsAndAST> InpAST) {
+    if (!InpAST)
+      return CB(InpAST.takeError());
+    CB(clangd::getSuperTypes(InpAST->AST, Pos));
+  };
+
+  WorkScheduler.runWithAST("Super Types", 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);
 
   // Inject the resource dir.
   // FIXME: Don't overwrite it if it's already there.
   C->CommandLine.push_back("-resource-dir=" + ResourceDir);
   return std::move(*C);
 }
 
 void ClangdServer::onFileEvent(const DidChangeWatchedFilesParams &Params) {
   // FIXME: Do nothing for now. This will be used for indexing and potentially
   // invalidating other caches.
 }
 
 void ClangdServer::workspaceSymbols(
     llvm::StringRef Query, int Limit,
     Callback<std::vector<SymbolInformation>> CB) {

clang-tools-extra/clangd/FindSymbols.h

 //===--- FindSymbols.h --------------------------------------*- C++-*------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // 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 "llvm/ADT/StringRef.h"
 
 namespace clang {
+class ASTContext;
+class NamedDecl;
+
 namespace clangd {
 class ParsedAST;
 class SymbolIndex;
 
+/// Collect information about a symbol named by \p ND and return it in the form
+/// of a DocumentSymbol object. If \p IncludeURI is false, the declaration is
+/// required to be written in the main file, and the 'uri' field of the result
+/// will be empty. If \p IncludeURI is true, the declaration may be in a
+/// different file, and the 'uri' field will be populated to indicate the file.
+llvm::Optional<DocumentSymbol> declToSym(ASTContext &Ctx, const NamedDecl &ND,
+                                         bool IncludeURI = false);
+
 /// 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).
 /// \p HintPath This is used when resolving URIs. If empty, URI resolution can

clang-tools-extra/clangd/FindSymbols.cpp

 //===--- FindSymbols.cpp ------------------------------------*- C++-*------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 #include "FindSymbols.h"
 
 #include "AST.h"
 #include "ClangdUnit.h"
 #include "FuzzyMatch.h"
 #include "Logger.h"
 #include "Quality.h"
 #include "SourceCode.h"
+#include "XRefs.h"
 #include "index/Index.h"
+#include "index/SymbolCollector.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Index/IndexingAction.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/ScopedPrinter.h"
 
Index->fuzzyFind(Req, [HintPath, &Top, &Filter](const Symbol &Sym) {
 
     Top.push({Score, std::move(Info)});
   });
   for (auto &R : std::move(Top).items())
     Result.push_back(std::move(R.second));
   return Result;
 }
 
-namespace {
-llvm::Optional<DocumentSymbol> declToSym(ASTContext &Ctx, const NamedDecl &ND) {
+llvm::Optional<DocumentSymbol> declToSym(ASTContext &Ctx, const NamedDecl &ND,
+                                         bool IncludeURI) {
   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;
 
+  if (!IncludeURI) {
     if (!SM.isWrittenInMainFile(NameLoc) || !SM.isWrittenInMainFile(BeginLoc) ||
         !SM.isWrittenInMainFile(EndLoc))
       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);
 
   DocumentSymbol SI;
   SI.name = printName(Ctx, ND);
   SI.kind = SK;
   SI.deprecated = ND.isDeprecated();
   SI.range =
       Range{sourceLocToPosition(SM, BeginLoc), sourceLocToPosition(SM, EndLoc)};
   SI.selectionRange = Range{NameBegin, NameEnd};
   if (!SI.range.contains(SI.selectionRange)) {
     // 'selectionRange' must be contained in 'range', so in cases where clang
     // reports unrelated ranges we need to reconcile somehow.
     SI.range = SI.selectionRange;
   }
+
+  if (IncludeURI) {
+    StringRef Filename = SM.getFilename(BeginLoc);
+    std::string FileURI = toURI(SM, Filename, {});
+    std::string TUPath;
+    const FileEntry *FE =
+        SM.getFileEntryForID(SM.getMainFileID());
+    if (auto Path = getCanonicalPath(FE, SM))
+      TUPath = *Path;
+    if (auto U = getURIForFile(FileURI, TUPath)) {
+      SI.uri = std::move(*U);
+    } else {
+      return llvm::None;  // Not useful without a uri.
+    }
+  }
+
   return SI;
 }
 
+namespace {
 /// A helper class to build an outline for the parse AST. It traverse the AST
 /// directly instead of using RecursiveASTVisitor (RAV) for three main reasons:
 ///    - there is no way to keep RAV from traversing subtrees we're not
 ///      interested in. E.g. not traversing function locals or implicit template
 ///      instantiations.
 ///    - it's easier to combine results of recursive passes, e.g.
 ///    - visiting decls is actually simple, so we don't hit the complicated
 ///      cases that RAV mostly helps with (types and expressions, etc.)

clang-tools-extra/clangd/Protocol.h

struct DocumentSymbol {
   Range range;
 
   /// The range that should be selected and revealed when this symbol is being
   /// picked, e.g the name of a function. Must be contained by the `range`.
   Range selectionRange;
 
   /// Children of this symbol, e.g. properties of a class.
   std::vector<DocumentSymbol> children;
+
+  /// File in which the symbol is contained.
+  /// Used for queries where the result may not be in the main file.
+  llvm::Optional<URIForFile> uri;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &O, const DocumentSymbol &S);
 llvm::json::Value toJSON(const DocumentSymbol &S);
 
 /// Represents information about programming constructs like variables, classes,
 /// interfaces etc.
 struct SymbolInformation {
   /// The name of this symbol.

 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 {
   /// The text document's URI.
   URIForFile uri;
   /// The human-readable string presents the current state of the file, can be
   /// shown in the UI (e.g. status bar).
   std::string state;
   // FIXME: add detail messages.
 };
 llvm::json::Value toJSON(const FileStatus &FStatus);
 
 } // namespace clangd
 } // namespace clang
 
 namespace llvm {
 template <> struct format_provider<clang::clangd::Position> {
   static void format(const clang::clangd::Position &Pos, raw_ostream &OS,
                      StringRef Style) {
     assert(Style.empty() && "style modifiers for this type are not supported");
     OS << Pos;
   }
 };
 } // namespace llvm
 
 #endif

clang-tools-extra/clangd/Protocol.cpp

llvm::json::Object Result{{"name", S.name},
                             {"selectionRange", S.selectionRange}};
 
   if (!S.detail.empty())
     Result["detail"] = S.detail;
   if (!S.children.empty())
     Result["children"] = S.children;
   if (S.deprecated)
     Result["deprecated"] = true;
+  if (S.uri)
+    Result["uri"] = *S.uri;
   // Older gcc cannot compile 'return Result', even though it is legal.
   return llvm::json::Value(std::move(Result));
 }
 
 llvm::json::Value toJSON(const WorkspaceEdit &WE) {
   if (!WE.changes)
     return llvm::json::Object{};
   llvm::json::Object FileChanges;
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 &Params, ReferenceParams &R) {
   TextDocumentPositionParams &Base = R;
   return fromJSON(Params, Base);
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/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);
 
+/// Get the super types information at \p Pos.
+llvm::Optional<DocumentSymbol> getSuperTypes(ParsedAST &AST, Position Pos);
+
+/// Convert a a URI (such as that returned by toURI()) into a form suitable
+/// for use in protocol replies (e.g. Location.uri, DocumentSymbol.uri).
+/// TUPath is used to resolve the path of URI.
+Optional<URIForFile> getURIForFile(StringRef FileURI, StringRef TUPath);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_XREFS_H

clang-tools-extra/clangd/XRefs.cpp

 //===--- XRefs.cpp -----------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 #include "XRefs.h"
 #include "AST.h"
+#include "FindSymbols.h"
 #include "Logger.h"
 #include "SourceCode.h"
 #include "URI.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Index/USRGeneration.h"
 #include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {
+
+Optional<URIForFile> getURIForFile(StringRef FileURI,
+                                   StringRef TUPath) {
+  auto Uri = URI::parse(FileURI);
+  if (!Uri) {
+    elog("Could not parse URI {0}: {1}", FileURI, Uri.takeError());
+    return None;
+  }
+  auto U = URIForFile::fromURI(*Uri, TUPath);
+  if (!U) {
+    elog("Could not resolve URI {0}: {1}", FileURI, U.takeError());
+    return None;
+  }
+
+  return *U;
+}
+
 namespace {
 
 // Get the definition from a given declaration `D`.
 // Return nullptr if no definition is found, or the declaration type of `D` is
 // not supported.
 const Decl *getDefinition(const Decl *D) {
   assert(D);
   if (const auto *TD = dyn_cast<TagDecl>(D))

 // Convert a SymbolLocation to LSP's Location.
 // TUPath is used to resolve the path of URI.
 // FIXME: figure out a good home for it, and share the implementation with
 // FindSymbols.
 llvm::Optional<Location> toLSPLocation(const SymbolLocation &Loc,
                                        llvm::StringRef TUPath) {
   if (!Loc)
     return None;
-  auto Uri = URI::parse(Loc.FileURI);
-  if (!Uri) {
-    elog("Could not parse URI {0}: {1}", Loc.FileURI, Uri.takeError());
-    return None;
-  }
-  auto U = URIForFile::fromURI(*Uri, TUPath);
-  if (!U) {
-    elog("Could not resolve URI {0}: {1}", Loc.FileURI, U.takeError());
+
+  auto U = getURIForFile(Loc.FileURI, TUPath);
+  if (!U)
     return None;
-  }
 
   Location LSPLoc;
   LSPLoc.uri = std::move(*U);
   LSPLoc.range.start.line = Loc.Start.line();
   LSPLoc.range.start.character = Loc.Start.column();
   LSPLoc.range.end.line = Loc.End.line();
   LSPLoc.range.end.character = Loc.End.column();
   logIfOverflow(Loc);
if (!index::generateUSRForMacro(NewMacro.name, Loc, SM, USR)) {
       NewMacro.ID = SymbolID(NewMacro.USR);
     }
     Results.push_back(std::move(NewMacro));
   }
 
   return Results;
 }
 
+static Optional<DocumentSymbol> getSuperTypes(const CXXRecordDecl &CXXRD,
+                                              ASTContext &ASTCtx) {
+  Optional<DocumentSymbol> Result = declToSym(ASTCtx, CXXRD, /* IncludeURI = */ true);
+  if (Result) {
+    for (auto It = CXXRD.bases_begin(); It != CXXRD.bases_end(); It++) {
+      const RecordType *ParentType =
+          It->getType().getTypePtr()->getAs<RecordType>();
+      if (!ParentType)
+        continue;
+
+      const CXXRecordDecl *ParentDecl = ParentType->getAsCXXRecordDecl();
+      if (!ParentDecl)
+        continue;
+
+      if (Optional<DocumentSymbol> ParentSym = 
+          getSuperTypes(*ParentDecl, ASTCtx)) {
+        Result->children.emplace_back(std::move(*ParentSym));
+      }
+    }
+  }
+  return Result;
+}
+
+Optional<DocumentSymbol> getSuperTypes(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 {};
+
+  const Decl *D = Symbols.Decls[0].D;
+  const CXXRecordDecl *CXXRD;
+
+  if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
+    // If this is a variable, use the type of the variable.
+    CXXRD = VD->getType().getTypePtr()->getAsCXXRecordDecl();
+  } else if (const CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(D)) {
+    // If this is a method, use the type of the class.
+    CXXRD = Method->getParent();
+  } else {
+    CXXRD = dyn_cast<CXXRecordDecl>(D);
+  }
+
+  if (CXXRD)
+    return getSuperTypes(*CXXRD, ASTCtx);
+
+  return {};
+}
+
 } // namespace clangd
 } // namespace clang

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

private:
   // provided by clang. For example, friend declaration might be considered
   // canonical by clang but should not be considered canonical in the index
   // unless it's a definition.
   llvm::DenseMap<const Decl *, const Decl *> CanonicalDecls;
   // Cache whether to index a file or not.
   llvm::DenseMap<FileID, bool> FilesToIndexCache;
 };
 
+// Returns a URI of \p Path. Firstly, this makes the \p Path absolute using the
+// current working directory of the given SourceManager if the Path is not an
+// absolute path. If failed, this resolves relative paths against \p FallbackDir
+// to get an absolute path. Then, this tries creating an URI for the absolute
+// path with schemes specified in \p Opts. This returns an URI with the first
+// working scheme, if there is any; otherwise, this returns None.
+//
+// The Path can be a path relative to the build directory, or retrieved from
+// the SourceManager.
+std::string toURI(const SourceManager &SM, llvm::StringRef Path,
+                  llvm::StringRef FallbackDir);
+
 } // namespace clangd
 } // namespace clang
 #endif

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

 #include "clang/Index/USRGeneration.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {
-namespace {
-
-/// If \p ND is a template specialization, returns the described template.
-/// Otherwise, returns \p ND.
-const NamedDecl &getTemplateOrThis(const NamedDecl &ND) {
-  if (auto T = ND.getDescribedTemplate())
-    return *T;
-  return ND;
-}
 
-// Returns a URI of \p Path. Firstly, this makes the \p Path absolute using the
-// current working directory of the given SourceManager if the Path is not an
-// absolute path. If failed, this resolves relative paths against \p FallbackDir
-// to get an absolute path. Then, this tries creating an URI for the absolute
-// path with schemes specified in \p Opts. This returns an URI with the first
-// working scheme, if there is any; otherwise, this returns None.
-//
-// The Path can be a path relative to the build directory, or retrieved from
-// the SourceManager.
 std::string toURI(const SourceManager &SM, llvm::StringRef Path,
-                  const SymbolCollector::Options &Opts) {
+                  llvm::StringRef FallbackDir) {
   llvm::SmallString<128> AbsolutePath(Path);
   if (auto CanonPath =
           getCanonicalPath(SM.getFileManager().getFile(Path), SM)) {
     AbsolutePath = *CanonPath;
   }
   // We don't perform is_absolute check in an else branch because makeAbsolute
   // might return a relative path on some InMemoryFileSystems.
-  if (!llvm::sys::path::is_absolute(AbsolutePath) && !Opts.FallbackDir.empty())
-    llvm::sys::fs::make_absolute(Opts.FallbackDir, AbsolutePath);
+  if (!llvm::sys::path::is_absolute(AbsolutePath) && !FallbackDir.empty())
+    llvm::sys::fs::make_absolute(FallbackDir, AbsolutePath);
   llvm::sys::path::remove_dots(AbsolutePath, /*remove_dot_dot=*/true);
   return URI::create(AbsolutePath).toString();
 }
 
+namespace {
+
+/// If \p ND is a template specialization, returns the described template.
+/// Otherwise, returns \p ND.
+const NamedDecl &getTemplateOrThis(const NamedDecl &ND) {
+  if (auto T = ND.getDescribedTemplate())
+    return *T;
+  return ND;
+}
+
 // All proto generated headers should start with this line.
 static const char *PROTO_HEADER_COMMENT =
     "// Generated by the protocol buffer compiler.  DO NOT EDIT!";
 
 // Checks whether the decl is a private symbol in a header generated by
 // protobuf compiler.
 // To identify whether a proto header is actually generated by proto compiler,
 // we check whether it starts with PROTO_HEADER_COMMENT.
getIncludeHeader(llvm::StringRef QName, const SourceManager &SM,
   if (Headers.empty())
     return None;
   llvm::StringRef Header = Headers[0];
   if (Opts.Includes) {
     Header = Opts.Includes->mapHeader(Headers, QName);
     if (Header.startswith("<") || Header.startswith("\""))
       return Header.str();
   }
-  return toURI(SM, Header, Opts);
+  return toURI(SM, Header, Opts.FallbackDir);
 }
 
 // Return the symbol range of the token at \p TokLoc.
 std::pair<SymbolLocation::Position, SymbolLocation::Position>
 getTokenRange(SourceLocation TokLoc, const SourceManager &SM,
               const LangOptions &LangOpts) {
   auto CreatePosition = [&SM](SourceLocation Loc) {
     auto LSPLoc = sourceLocToPosition(SM, Loc);

 llvm::Optional<SymbolLocation>
 getTokenLocation(SourceLocation TokLoc, const SourceManager &SM,
                  const SymbolCollector::Options &Opts,
                  const clang::LangOptions &LangOpts,
                  std::string &FileURIStorage) {
   auto Path = SM.getFilename(TokLoc);
   if (Path.empty())
     return None;
-  FileURIStorage = toURI(SM, Path, Opts);
+  FileURIStorage = toURI(SM, Path, Opts.FallbackDir);
   SymbolLocation Result;
   Result.FileURI = FileURIStorage.c_str();
   auto Range = getTokenRange(TokLoc, SM, LangOpts);
   Result.Start = Range.first;
   Result.End = Range.second;
 
   return Result;
 }
void SymbolCollector::finish() {
   }
 
   const auto &SM = ASTCtx->getSourceManager();
   llvm::DenseMap<FileID, std::string> URICache;
   auto GetURI = [&](FileID FID) -> llvm::Optional<std::string> {
     auto Found = URICache.find(FID);
     if (Found == URICache.end()) {
       if (auto *FileEntry = SM.getFileEntryForID(FID)) {
-        auto FileURI = toURI(SM, FileEntry->getName(), Opts);
+        auto FileURI = toURI(SM, FileEntry->getName(), Opts.FallbackDir);
         Found = URICache.insert({FID, FileURI}).first;
       } else {
         // Ignore cases where we can not find a corresponding file entry
         // for the loc, thoses are not interesting, e.g. symbols formed
         // via macro concatenation.
         return None;
       }
     }

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

 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
 using testing::ElementsAre;
+using testing::Eq;
 using testing::Field;
 using testing::IsEmpty;
 using testing::Matcher;
 using testing::UnorderedElementsAreArray;
 
 class IgnoreDiagnostics : public DiagnosticsConsumer {
   void onDiagnosticsReady(PathRef File,
                           std::vector<Diag> Diagnostics) override {}
 };
 
 MATCHER_P2(FileRange, File, Range, "") {
   return Location{URIForFile::canonicalize(File, testRoot()), Range} == arg;
 }
 
+// GMock helpers for matching DocumentSymbol.
+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... ChildMatchers>
+testing::Matcher<DocumentSymbol> Children(ChildMatchers... ChildrenM) {
+  return Field(&DocumentSymbol::children, ElementsAre(ChildrenM...));
+}
+
 // Extracts ranges from an annotated example, and constructs a matcher for a
 // highlight set. Ranges should be named $read/$write as appropriate.
 Matcher<const std::vector<DocumentHighlight> &>
 HighlightsFrom(const Annotations &Test) {
   std::vector<DocumentHighlight> Expected;
   auto Add = [&](const Range &R, DocumentHighlightKind K) {
     Expected.emplace_back();
     Expected.back().range = R;
for (Test T : Tests) {
     findReferences(AST, File.point(), 0, &Rec);
     if (T.WantQuery)
       EXPECT_NE(Rec.RefIDs, None) << T.AnnotatedCode;
     else
       EXPECT_EQ(Rec.RefIDs, None) << T.AnnotatedCode;
   }
 }
 
+TEST(SuperTypes, SimpleInheritanceOnTypeOrVariable) {
+  Annotations Source(R"cpp(
+struct $ParentDef[[Parent]]
+{
+  int a;
+};
+
+struct $Child1Def[[Child1]] : Parent
+{
+  int b;
+};
+
+struct Ch$p1^ild2 : Child1
+{
+  int c;
+};
+
+struct Child3 : Child2
+{
+  int d;
+};
+
+int main()
+{
+  Ch$p2^ild2 ch$p3^ild2;
+
+  parent.a = 1;
+  ch$p4^ild2.c = 1;
+}
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+
+  for (auto Pt : {"p1", "p2", "p3", "p4"}) {
+    llvm::Optional<DocumentSymbol> Result = getSuperTypes(AST, Source.point(Pt));
+    ASSERT_TRUE(bool(Result));
+    EXPECT_THAT(*Result,
+                AllOf(WithName("Child2"), WithKind(SymbolKind::Struct),
+                      Children(AllOf(WithName("Child1"),
+                                     WithKind(SymbolKind::Struct),
+                                     SelectionRangeIs(Source.range("Child1Def")),
+                                     Children(AllOf(WithName("Parent"),
+                                                    WithKind(SymbolKind::Struct),
+                                                    SelectionRangeIs(Source.range("ParentDef")),
+                                                    Children()))))));
+  }
+}
+
+TEST(SuperTypes, MultipleInheritanceOnTypeOrVariable) {
+  Annotations Source(R"cpp(
+struct $Parent1Def[[Parent1]]
+{
+  int a;
+};
+
+struct $Parent2Def[[Parent2]]
+{
+  int b;
+};
+
+struct $Parent3Def[[Parent3]] : Parent2
+{
+  int c;
+};
+
+struct Ch$c1^ild : Parent1, Parent3
+{
+  int d;
+};
+
+int main()
+{
+  Ch$c2^ild  ch$c3^ild;
+
+  ch$c4^ild.a = 1;
+}
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+
+  for (auto Pt : {"c1", "c2", "c3", "c4"}) {
+    llvm::Optional<DocumentSymbol> Result = getSuperTypes(AST, Source.point(Pt));
+    ASSERT_TRUE(bool(Result));
+    EXPECT_THAT(*Result,
+                AllOf(WithName("Child"), WithKind(SymbolKind::Struct),
+                      Children(AllOf(WithName("Parent1"),
+                                     WithKind(SymbolKind::Struct),
+                                     SelectionRangeIs(Source.range("Parent1Def")),
+                                     Children()), 
+                               AllOf(WithName("Parent3"),
+                                     WithKind(SymbolKind::Struct),
+                                     SelectionRangeIs(Source.range("Parent3Def")),
+                                     Children(AllOf(WithName("Parent2"),
+                                                    WithKind(SymbolKind::Struct),
+                                                    SelectionRangeIs(Source.range("Parent2Def")),
+                                                    Children()))))));
+  }
+}
+
+TEST(SuperTypes, OnMethod) {
+  Annotations Source(R"cpp(
+struct $ParentDef[[Parent]]
+{
+  void method ();
+  void method () const;
+  void method (int x);
+  void method (char x);
+};
+
+struct $Child1Def[[Child1]] : Parent
+{
+  void method ();
+  void method (char x);
+};
+
+struct Child2 : Child1
+{
+  void met$p1^hod ();
+  void met$p2^hod (int x);
+};
+
+struct Child3 : Child2
+{
+  void method (int x);
+};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  for (auto Pt : {"p1", "p2"}) {
+    llvm::Optional<DocumentSymbol> Result = getSuperTypes(AST, Source.point(Pt));
+    ASSERT_TRUE(bool(Result));
+    EXPECT_THAT(*Result,
+                AllOf(WithName("Child2"), WithKind(SymbolKind::Struct),
+                      Children(AllOf(WithName("Child1"),
+                                     WithKind(SymbolKind::Struct),
+                                     SelectionRangeIs(Source.range("Child1Def")),
+                                     Children(AllOf(WithName("Parent"),
+                                                    WithKind(SymbolKind::Struct),
+                                                    SelectionRangeIs(Source.range("ParentDef")),
+                                                    Children()))))));
+  }
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang