Prototyping a "type hierarchy" request

Hi all,

There is no request to obtain the type hierarchy starting from a particular type in the LSP specification yet, but there are some proposals [1] and some other language servers have their own extension to the protocol to support that. I thought I would start prototyping the feature in clangd to see how we can retrieve this information, so that once the specification is modified to include such a request, we are not too far from supporting it. It can also help steer the proposed changes to the specification to make sure it supports what we need for the C++ language.

The scope of my prototype is: given a type or variable, recursively find the base classes of that type (or the type of that variable). I am not considering derived classes right now, because it would require dealing with the index. Here is my work so far:

https://reviews.llvm.org/D51311

One extra feature I would really like to have is to be able to use the "type hierarchy" request on a method (definition, declaration or call). The result would tell you which nodes of the type hierarchy have an implementation of this method (possibly with some more details, is it virtual, is it pure, etc). It would allow implementing UIs such as the one in this screenshot, which I find very useful:

https://github.com/Microsoft/vscode-languageserver-node/pull/346#issuecomment-416256239

I'm a bit stuck at this point: given a CXXMethodDecl representing the method the user targeted, how can I tell if some base class (a CXXRecordDecl) has a method matching this one. I saw CXXMethodDecl::overridden_methods, but it only concerns virtual methods, whereas for type hierarchy we would also want non-virtual overrides.

Does anybody have any pointers on how I could do this?

Simon

[1] https://github.com/Microsoft/vscode-languageserver-node/pull/346

Hi all,

There is no request to obtain the type hierarchy starting from a
particular type in the LSP specification yet, but there are some
proposals [1] and some other language servers have their own extension
to the protocol to support that. I thought I would start prototyping
the feature in clangd to see how we can retrieve this information, so
that once the specification is modified to include such a request, we
are not too far from supporting it. It can also help steer the proposed
changes to the specification to make sure it supports what we need for
the C++ language.

The scope of my prototype is: given a type or variable, recursively find
the base classes of that type (or the type of that variable). I am not
considering derived classes right now, because it would require dealing
with the index. Here is my work so far:

https://reviews.llvm.org/D51311

Haven’t looked at the patch yet, but this sounds awesome and you’re right about the index needing work to support this.
One approach would be to use the XRefs APIs that are landing, make “overrides” a role, and allow the payload to be a symbol ID rather than a location.

One extra feature I would really like to have is to be able to use the
“type hierarchy” request on a method (definition, declaration or call).
The result would tell you which nodes of the type hierarchy have an
implementation of this method (possibly with some more details, is it
virtual, is it pure, etc). It would allow implementing UIs such as the
one in this screenshot, which I find very useful:

https://github.com/Microsoft/vscode-languageserver-node/pull/346#issuecomment-416256239

I’m a bit stuck at this point: given a CXXMethodDecl representing the
method the user targeted, how can I tell if some base class (a
CXXRecordDecl) has a method matching this one. I saw
CXXMethodDecl::overridden_methods, but it only concerns virtual methods,
whereas for type hierarchy we would also want non-virtual overrides.

Dumb question, what are non-virtual overrides? I’m thinking CRTP, but I’m probably overthinking this :slight_smile:

Not sure I understand you question. But simply, if you have this:

struct A
{
   void method ();
};

struct B : A
{};

struct C : B
{
   void me^thod ();
};

I think that doing a type hierarchy request at the caret should still tell you that a definition of the method you are targeting is present in A and not in B, even if they are not marked virtual.

Simon

I'll take a look, but I am not sure how this solves the problem of extracting the required information from the AST.

Simon

whereas for type hierarchy we would also want non-virtual overrides.

Dumb question, what are non-virtual overrides? I’m thinking CRTP, but
I’m
probably overthinking this :slight_smile:

Not sure I understand you question. But simply, if you have this:

struct A
{
void method ();
};

struct B : A
{};

struct C : B
{
void me^thod ();
};

I think that doing a type hierarchy request at the caret should still
tell you that a definition of the method you are targeting is present in
A and not in B, even if they are not marked virtual.

Ah, right. I don’t think this is usually considered overriding.
I’d be surprised to see this in a type hierarchy, as I’d usually consider them unrelated functions.
(And the compiler mostly does too, so you’ll probably have to iterate over all the base’s members).

There are cases where this hiding is used for overriding-like effect with compile-time polymorphism, like when a CRTP base class B provides a default implementation of foo(), and invokes it as Derived::foo(). But this is probably the exception rather than the rule, it seems OK to leave it out in the first cut at least.

One approach would be to use the XRefs APIs that are landing, make
“overrides” a role, and allow the payload to be a symbol ID rather than
a
location.
I’ll take a look, but I am not sure how this solves the problem of
extracting the required information from the AST.

Sorry, it doesn’t - I was speculating about how to (later) tie this to the index to get the derived types.