Page MenuHomePhabricator

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

Authored by nridge on Jan 6 2019, 4:32 PM.

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
nridge marked an inline comment as done.Feb 14 2019, 4:30 PM
nridge added inline comments.
clang-tools-extra/unittests/clangd/XRefsTests.cpp
1604 ↗(On Diff #186944)

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

nridge updated this revision to Diff 186947.Feb 14 2019, 4:49 PM

Fix a test failure

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

nridge updated this revision to Diff 189065.Sat, Mar 2, 5:17 PM

Rebased.

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 marked 19 inline comments as done.Sun, Mar 3, 11:27 AM
nridge added inline comments.
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 updated this revision to Diff 189092.Sun, Mar 3, 11:30 AM
nridge marked 2 inline comments as done.

Address latest review comments

nridge updated this revision to Diff 189114.Sun, Mar 3, 8:55 PM

Address a couple of outstanding TODOs

kadircet added inline comments.Mon, Mar 4, 2:02 AM
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
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())

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?

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?

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 updated this revision to Diff 189444.Tue, Mar 5, 7:55 PM
nridge marked 10 inline comments as done.

Address most of the latest review comments.

The infinite recursion issue remains to be fixed.

nridge added inline comments.Tue, Mar 5, 7:55 PM
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 marked an inline comment as done.Tue, Mar 5, 7:56 PM
nridge added inline comments.
clang-tools-extra/clangd/XRefs.cpp
885 ↗(On Diff #189065)

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

kadircet added inline comments.Wed, Mar 6, 12:48 AM
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 updated this revision to Diff 190040.Sun, Mar 10, 7:42 PM

Address the infinite recursion issue

nridge marked an inline comment as done.Sun, Mar 10, 7:47 PM

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 updated this revision to Diff 190041.Sun, Mar 10, 8:20 PM

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 added a comment.EditedSun, Mar 10, 8:24 PM

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 marked an inline comment as done.EditedTue, Mar 12, 8:31 AM

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.

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 added inline comments.Tue, Mar 12, 8:50 AM
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.

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.

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 updated this revision to Diff 190375.Tue, Mar 12, 10:23 PM

Address remaining review comments

(I figure out how to write a lit test)

nridge marked 2 inline comments as done.Tue, Mar 12, 10:24 PM

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

Thanks!

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?

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.

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 marked 7 inline comments as done.Thu, Mar 14, 4:55 PM
nridge added inline comments.
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 updated this revision to Diff 190755.Thu, Mar 14, 4:57 PM
nridge marked an inline comment as done.

Address latest review comments

ilya-biryukov added inline comments.Fri, Mar 15, 2:47 AM
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 accepted this revision.Fri, Mar 15, 2:53 AM

LGTM, thanks Nathan!

This revision is now accepted and ready to land.Fri, Mar 15, 2:53 AM

Great, thanks for the reviews!

Could you commit the patch as well?

This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptTue, Mar 19, 2:28 AM