Make lsp-ui-imenu hierarchical

[MaskRay]

lsp--imenu-create-index from lsp-imenu.el (in lsp-mode) does not take hierarchy into consideration. I think it might be useful if it can be used to visualize arbitrary symbol hierarchy, where the most common ones are:

• member hierarchy: members of a type (e.g. members of a class/struct; enumeration constants in an enum; members in a module/namespace) are recursively expanded

struct B { B* x; int b; };
struct A { B b;  int c; };

may expand to

A
  B b
    int b
    B* x    // pointer types can optionally be expanded
      int b
      B* x   // but the client needs to explicitly trigger the expansion to avoid infinite recursion
        int b
        B* x
  int c

• caller tree of a callable (e.g. function,method,...). (may be generalized to reference tree)

void foo() { bar(); quz(); foo(); }
void bar() { quz(); }

is visualized as:

quz
  foo
    foo   // explicit expansion to avoid infinite recursion
  bar
    foo
      foo

• inheritance hierarchy (e.g. all derived classes of a C++ base class, or overriden virtual functions of a base function; Rust trait/impl; Java interface...)

struct B : A {};
struct C : B {};
struct D : B {};

is visualized as:

A
  B
    C
    D

LSP spec

interface SymbolInformation {
	name: string;
        // id is missing; name may be insufficient to identify a symbol
	kind: number;
	location: Location;
	containerName?: string;  // containerName is a string. If it was an identifier, it could be used to describe a parent pointer tree
}

When the point is at a reference of a symbol, textDocument/documentHighlight or other mechanism can be employed to highlight the imenu entry and there can be some keys to trigger these different kinds of hierarchies.

• $cquery/typeHierarchyTree is a kind of inheritance hierarchy
• $cquery/memberHierarchy is a kind of member hierarchy.
• $cquery/callerTreeInitial is a kind of call hierarchy.

I'd like to know if such extensions have been implemented in other servers. We should unify these server API interfaces and even standardize it.

[MaskRay]

rls: @Xanewok
cquery: @jacobdufault
pyls: @gatesn

[sebastiencs]

I agree that something should be done to have symbols hierarchy.

I think that containerName can just be rename to parentId:

interface SymbolInformation {
	name: string; // Name display to the user
	kind: number;
	location: Location;
    id: string // A unique identifier
    parentId?: string // An optional pointer to its parent. Could be a string[] ?
}

The RLS doesn't provide yet such hierarchy, but it shouldn't be difficult to implement. @Xanewok ?

Related discussions:
microsoft/language-server-protocol#136
facebookarchive/atom-ide-ui#121

[bizzyman]

Some issues for consideration re hierarchies.

1. Distinction between defined symbols and called symbols. This is important because it seems lsp methods such as 'textDocument/documentSymbol' only return symbols that are defined in the document, they do not return symbols that are called. It seems like 'lsp--imenu-create-index' does this too. I think therefore implementations of a call-tree/hierarchy should either wait for an explicit separate lsp method for call trees or use additional ad-hoc hacks to find called symbols.

2. LSP currently discourages inferring hierarchical information from the methods that are currently defined. For example, 'containerName':

/**
	 * The name of the symbol containing this symbol. This information is for
	 * user interface purposes (e.g. to render a qualifier in the user interface
	 * if necessary). **It can't be used to re-infer a hierarchy for the document
	 * symbols.**
	 */
	containerName?: string;

And 'location'

	/**
	 * The location of this symbol. The location's range is used by a tool
	 * to reveal the location in the editor. If the symbol is selected in the
	 * tool the range's start information is used to position the cursor. So
	 * the range usually spawns more then the actual symbol's name and does
	 * normally include thinks like visibility modifiers.
	 *
	 * The range doesn't have to denote a node range in the sense of a abstract
	 * syntax tree. **It can therefore not be used to re-construct a hierarchy of
	 * the symbols**.
	 */
	location: Location;

(from https://microsoft.github.io/language-server-protocol/specification)

Further discussion of symbol hierarchy is here microsoft/language-server-protocol#327 , here microsoft/vscode#34968 and here microsoft/language-server-protocol#136 . It seems from these issues that creating a separate method for getting symbol hierarchies is in the works ?

My own experience is that getting proper hierarchies is a big pain and may require an AST if we choose to just adopt ad-hoc hacks.

[MaskRay]

May I loop @beacoder in as he has recently published https://github.com/beacoder/call-graph which provide similar features.

[beacoder]

@MaskRay ,thanks for loop me in.
May I share a little thought about my call-graph:
I know that it's especially difficult to find the correct function calling relationship in languages like cplusplus.
Even with the help of building systems like Clang.
Of cause with Clang, it can help you rule out lots of false matches which tags systems could not, but still if one interface has two or more implementations, for one specific function invocation, it fails to tell you which implementation is one that used here.
So my thought is at the end of the day, we the programmer knows what's going on here, we know what this invocation is about.
So my only expectations for tools like call-graph is that it could give me all the possible calling-relations.
Then with my knowledge about the code base, I could help the tool (call-graph) to tell the right from wrong, and to take it a little further, maybe find some way to persist this right calling-relationship, so that we don't have to do this repeatedly.

Some explanation in Chinese(due to poor english):
这有点儿像中文拼音输入法，你输入几个拼音后，可能代表很多种中文意思
最后取决于我们来选择我们要的到底是哪一种，并且，根据我们使用的频率
输入法下次会将我们使用频繁的意思排到前排。

hope this is of some help to you guys, thanks.

[topisani]

emacs-cquery now has hierarchial trees for
Inheritance
Callers/callees
Members

This uses yet another custom tree implementation, which i would be perfectly willing to hand over to lsp-ui for this.

[MaskRay]

Thanks! I have done some minor work based on yours. On the cquery server side, these hierarchies have been unified (in terms of the interface),

$cquery/{call,member,inheritance}Hierarchy

In lsp-ui-imenu and cquery-tree-mode, it may be useful to have a follow mode: the current entry is visited automatically and the focus is kept in the tree view.

[sebastiencs]

@MaskRay @topisani That's nice ! If the code is generic enough for all LSP clients/languages it would be great to have it in lsp-ui

[MaskRay]

@topisani I think a big issue is that your code is licensed under MIT but most Emacs packages are under GPL 3. I am not a big fan of GPL 3 but I think it is better to keep the convention. Without switching to GPL 3 it is very difficult for anyone to pick it up.

And also the copyright notice in https://github.com/emacs-lsp/lsp-ui/blob/master/lsp-ui.el

[topisani]

@MaskRay makes sense, feel free to relicense any of my emacs-cquery code to GPL3. Also all of lsp-ui should cite @sebastiencs as the author

[MaskRay]

@topisani can you make the relicense change?..

I cannot do it for you as otherwise I would make a similar mistake as that (presumably) made by esr
https://invisible-island.net/ncurses/ncurses-license.html

[MaskRay]

Fixed by #179