Feature request: "document/extendSelection" for semantic selection

[matklad]

Hi!

A very useful feature of a syntax-aware code editor is semantic selection: editor.action.smartSelect which is based on the real syntax tree and not on the lexical grammar approximation.

I've implemented it as a custom extension to LSP for a couple of my language servers, and I'd like to suggest adding this feature to the LSP proper, with the following interface:

// `document/extendSelection` is sent from client to server
interface ExtendSelectionParams {
    textDocument: TextDocumentIdentifier;
    selections: Range[];
}

interface ExtendSelectionResult {
    selections: Range[];
}

Q&A:

Q: Why do we send an array of ranges?
A: This is to support multiple cursors. An argument could be made that this should be supported by the protocol-level batching of requests, but that seems much more complicated and potentially slow (server will have to resolve URL to document several times, etc)

Q: How about the opposition action, "shrinkSelection"?
A: Shrink selection is "ambiguous": given syntax node has many children, and selection could be shrunk to any child. The natural handling of "shrinkSelection" should be a client-side selection undo list.

Q: Why a range-based interface? Shouldn't the server just tell the client the syntax tree structure, and let the client implement "extendSelection"?
A: Using ranges is more general. There are cases when you want to do extend selection on a granularity smaller then a syntax node. For example, you might want to select an escape sequence in a string literal, or a word in a comment, or an expression in the code snippet in the comment. By providing a low-level range-based interface, we give servers maximum flexibility.

Q: Is there an example implementation?
A: Yep! Here's the bits then implement this feature in rust-analyzer server 1, 2, 3. Here's the client side implementation.

[matklad]

@dbaeumer friendly ping :)

Does this looks reasonable? If it does, I can proceed with drafting up protocol PR / reference impl.

It's OK if there are some obvious problems, or if it doesn't fit the current roadmap for LSP, but it would be useful to know.

[yyoncho]

I am curios whether this could be replaced with lightweight AST(like [element, range] where element is if/function definition/for and so on.) so the client could do more complex operations like - delete surrounding if .

[matklad]

That’s Q №3 :-)

I think that having such lightweight syntax tree might be useful In addition to this low-level API: it indeed would fit vim’s text object concept neatly. On the other hand, I expect that a lot of stuff which you might want to use such API for is actually better served by language specific code actions: stuff like invert if condition, replace if with early return, add else branch etc.

[jrieken]

@matklad Great timing! For the 1.30 release will have proposed API for this (microsoft/vscode#63935). https://github.com/Microsoft/vscode/blob/ff538190de79f06b9849e5e047fb367cd451a442/src/vs/vscode.proposed.d.ts#L21-L35

The proposed extension API is very similar to your proposal but we don't honour multiple cursors. In none of the APIs we have exposed the fact that the editor has multiple cursors and IMO esp. for the LSP that make sense - not all editor have the notion of multiple cursors.

In this specific case I would propose that an editor that supports multiple cursors and that wants to support smart select for them simply makes a request per cursor.

What's different in our proposal is that a provider must return all ranges enclosing the current position. With that we only ask once per "session" and can grow/shrink selections along them.

[matklad]

Awesome @jrieken!

Couple of comments:

re multiple cursors, I still think it probably makes sense to support it natively:

• users will be using extend selection + multiple cursor heavily, because this is an extremely powerful combinations
• most editors support multiple cursors, either natively or via plugin.
• if editor does not support multiple cursors, it would be trivial to send a list with one element
• (this one is important I think): request per position, if implemented naively, could lead to latency proportional to the number of cursors, which seems bad for such "UI-synchronous" feature.

To sum up, adding support for queering several regions seems pretty trivial, both on the client and on the server side, while implementing "request per cursor" needs more engineering and could have perf problems. Though, both versions seems OK. IIRC, VS code does not support "Expand selection" with multiple cursors at the moment, so it might be a good idea to add multiple cursors support to VS code first to see how much of a pain "request per cursor" is in practice.

What's different in our proposal is that a provider must return all ranges enclosing the current position. With that we only ask once per "session" and can grow/shrink selections along them.

👍 I don't think performance is too important here: first query must be fast (shorter than human-perceptible delay) anyway, and if the first query is fast, other queries will be fast as well. What is important is flexibility: with this API, we can add additional metadata to ranges to provide features beyond extend selection (that's what @yyoncho was talking about). For example, you can add kind: ?ElementKind = "expression" | "statemet" | "method" | "class" field to ranges, and then have shortcuts like "select method" (vim users will love them I suppose). Another thing we can do here is to add presentation: ?string field and use that to power breadcrumbs, instead of outline: I want to see if's and whiles (with conditions, if they are short) in breadcrumbs, but I definitely don't want to see them in outline. With this in mind, it might make sense to future-proof here, and name the method contextAtPosition, and use interface ContextElement { range: Range } instead of plain Range.

[matklad]

first query must be fast

That's actually false: the client can optimistically issue this request after each cursor movement, so, when the user invokes "extend selection", the results are already on the client.

[jrieken]

👍 I don't think performance is too important here: first query must be fast (shorter than human-perceptible delay) anyway, and if the first query is fast, other queries will be fast as well.

The thinking goes that when you implement this API you will likely use a syntax tree to do so. Given that it will be easy and super cheap to return all containing ranges. That safes IPC roundtrips and helps with implementations that don't keep/cache syntax trees.

For example, you can add kind: ?ElementKind = "expression" | "statemet" | "method" | "class" field to ranges, and then have shortcuts like "select method" (vim users will love them I suppose).

I like that

Another thing we can do here is to add presentation: ?string field and use that to power breadcrumbs, instead of outline: I want to see if's and whiles (with conditions, if they are short) in breadcrumbs, but

This is not going to happen. We following the one provider, one UI piece idea. Using the outline data provider for the breadcrumbs might have pushed it a little but if we are changing anything than it'll be a special breadcrumbs data provider.

[matklad]

This is not going to happen. We following the one provider, one UI piece idea.

👍 I've actually missed the fact that the thing you proposed is a VS Code provider, and not a protocol extension. It definitely makes sense to keep providers as granular as possible in the editor. In the protocol, it could make sense to query the data once and distribute it across several providers.

This actually makes the question about multiple selections more interesting: if I were designing editor extension API, then I would deferentially prefer to expose API which operates on one range and not on the collection of ranges. However, to make that work with n selections without incurring a total delay of O(n) client-server roundtrips, a lot of stars have to align:

• first, the editor must to await Promise.all(selections.map(s => provider.provide(s))) instead of for s in selections { await provider.provide(s) }
• second, the LSP client library must issue all requests concurrently. If, for example, it has some flow-control logic like "at most three requests in flight at any time", you'll have to wait several round trips
• third, either the LSP server should be capable of processing several requests concurrently or the underlying transport should have buffers large enough to fit all requests.

[dbaeumer]

@jrieken thanks for jumping in here.

@matklad most of the stuff @jrieken explained does apply for the LSP as well. The LSP for example doesn't talk about multiple cursors as well and I tried to avoid this so far. In general I even avoid talking about a cursor. The only place where it sneaked in is with snippets to denote the final cursor position.

I would like that we try to keep it that way even if it gets a little hard for clients to implement this.

Your point:

third, either the LSP server should be capable of processing several requests concurrently ...

This is currently allowed in the LSP. But it is up to the server to do so. We don't force this.

The JSON-RPC allows batching https://www.jsonrpc.org/specification#batch which we didn't add so far. But I am open to add this to make these thinks easier to implement. But it would need to be a capability since not all servers are supporting it.

Based on the API that @jrieken proposed would you be willing to add the protocol and implementation as described here: https://github.com/Microsoft/language-server-protocol/blob/master/contributing.md

[matklad]

But it is up to the server to do so. We don't force this.

Yeah: this is the point where we can get O(N) round-trips even if the client side is implemented properly.

The JSON-RPC allows batching

Thanks, I didn't realized that! This mostly clears my performance concerns with multiple cursors: RPC-level batching should work ok, though my gut feeling is that request-level batching would be much less complex. We also won't be able to employ batching with current VS Code interface (we won't be able to assemble requests in the batch), but it's always possible to add provideSelectionRangesBatch(document: TextDocument, positions: Position[], token: CancellationToken): ProviderResult<Range[][]> later when/if we actually need this.

would you be willing to add the protocol and implementation as described here: https://github.com/Microsoft/language-server-protocol/blob/master/contributing.md

Sure! I hope to find time to do that this or the next week.

[jrieken]

this is the point where we can get O(N) round-trips even

I think we understand that but how big will N get? I'd say it's rarely above 10. Then, assuming you ask for N cursors, how do you handle overlap? In the snippet below (| is one cursor), there are two cursors both will expand to true. Should the response be two ranges or one, merged range? What if you return an array of ranges per cursor (all containing ranges as proposed) and ranges overlap only at a later point?

while(tr|ue|) {}

All these complications make us not talk about multiple cursors in the API and hence LSP. Often the editor itself can be pragmatic, e.g not supporting multiple cursor for a feature, or asking N times, or automatically adopting a result to multiple cursors. E.g. for this feature multiple cursors could be supported when selecting the same text (that's like the use case for smart select and multi-cursor anyways).

[matklad]

I think we understand that but how big will N get? I'd say it's rarely above 10

That's true, yeah. I've measured the roundtrip time for extend selection, and it is about 2ms so, ten times that gives us 20ms which feels comfortable. Note, however that this is for a server that caches parse trees. For servers which do parsing on every request, I think you can get tens of milliseconds for a single requests, so the total time would be in low hundreds, which is not as comfortable, but hey, in this case it's probably the slow server's problem.

All these complications

I think this is an exaggeration of the problem: a simple semantics "for every input, compute the output independently" would work. Note that this is not at all about multiple cursors on the protocol level, its purely about multiplexing the request. If client is likely to issue several requests in a row, it's just an optimization to allow the client to send a single request with the array of the parameters, and this does not affect the semantics and meaning of the protocol.

To be clear, I am not arguing that the current proposal is wrong or that it'll lead to significantly worse user experience, I am just explaining why I went with request-level multiplexing: to avoid worst-case O(N) (and worst-case is definitely not a common case here) :)

[dbaeumer]

I personally would try to address this with JSON-RPC batching since it will allow us to batch requests of different types as well.

[jrieken]

ElementKind = "expression" | "statemet" | "method" | "class" field to ranges

@matklad wrt to classification of selection ranges. Did you already think of a reasonable set of types? I think it shouldn't be soo many (as we want user-facing command for them) and it should be generic enough to work for multiple languages. I think your list above is already a good starting ground - do you know more them vim-users et al?

[matklad]

@jrieken that's a hard question, b/c there's a tension between being language-specific, and being language-agnostic.

Can we perhaps just add future-proofing to be able to support this later? I think supporting this would be cool, and could unlock some awesome use-cases, but at the same time I don't know any specific use-case (that is, I won't be using ElementKind myself, I don't use Vim actually).

With vim-style interface I imagine you'd want a fine-grained set of types here, like if, while, etc. That probably means we need an open-ended set of tags, like string[] with some well-known ones (expression, statement, function, type) exposed via user-visible commands and an API for plugin writers which takes tag as a string.

All this design space is the reason why I want just to future-proof for now :-)

[matklad]

impl: microsoft/vscode-languageserver-node#441

[matklad]

@jrieken found an interesting edge-case due to the fact that the API uses only start position of the selection for the request.

Consider the case, when the caret is between two tokens:

    |while (true) {    }

Here, the caret is between whitespace and while keyword. I think the correct behavior from the users's POV is to select the more significant token of the two: pick identifier over whitespace or operator tokens.

Now, consider what happens in this situation:

    while| |   (true) {}

Here, we ideally want to select the whitespace node. However, the client will send an offset for the start of the selection, so server will pick while over whitespace and return ranges ['while', 'while (true) {}'], and the client will then pick the second range.

In theory, we can fix it by passing a range to the server, but in practice I don't think it makes sense to make API more complicated because of this rather obscure edge case.

[jrieken]

edge-case due to the fact that the API uses only start position of the selection for the request.

I think it just calls the API with a bad position - instead of the start it should use the active position of the selection, e.g. where the cursor blinks

[jrieken]

@jrieken that's a hard question, b/c there's a tension between being language-specific, and being language-agnostic.

This is my current proposal:

https://github.com/Microsoft/vscode/blob/78963e9090b187a58c49d6f0238dd1a56beea5a2/src/vs/vscode.proposed.d.ts#L21-L50

So, instead of just an array of ranges it's not an array of SelectionRange-objects. Each can have kind which is concat-string, like block or block.if etc. Those need refinement but it will allow to be generic and also flexible (code action use something very similar)

[matklad]

LGMT!

We probably don't need block: depending on the language, it's a kind of expression or statement.

We probably do need "declaration" (extendable to "declaration.method", "declaration.class")

[MaskRay]

Have you renamed extendSelection to selectionRange? My conjecture is that the rename reflects a future generalization to make it possible to do semantic navigation (one implementation is here at https://github.com/MaskRay/ccls/wiki/lsp-mode#ccls-navigate): one can select next/previous object as well as container or the first child.

[matklad]

@jrieken I've noticed that FoldingRange and SelectionRange have a very similar share, however they differ in the order of parameters to constructors. SelectionRange is constructor(kind: SelectionRangeKind, range: Range);, and FoldingRange is new FoldingRange(start: number, end: number, kind?: FoldingRangeKind). I think it makes sense to unify them (purely for consistency) and make the kind argument of SelectionRange come last and be nullable.

[matklad]

My conjecture is that the rename reflects a future generalization to make it possible to do semantic navigation

@MaskRay I very much support the "We following the one provider, one UI piece idea." pattern. It would be better to introduce a separate API for navigation specifically. Granted, folding ranges, selection ranges and navigation ranges will necessary have very similar shape (subset of the syntax tree mostly), however, by keeping them separately, we'll give servers the ability to fine-tune each one specifically. For example, I expect selections to be more fine-grained then folding ranges, and folding to be more fine-grained then navigation.

[matklad]

@octref it's up to the server to send or no send kinds, and its up to the client how to interpret kinds. FunctionArgument would be something like declaration.value_parameter.

[matklad]

@dbaeumer VS Code now uses API with multiple input positions, how we should proceede on the protocol side?

We can:

1. Keep the current proposal with single-position request, and emit several requests in the vscode-lsp-client library

2. Change the protocol to speak about multiple input positions as well.

I personally would mildely prefer approach 2: it is less general than protocol-level request multiplexing, but it's trivial to implement. I don't have a strong opinion however, so can go with 1 as well.

[matklad]

Status update: the relevant API is stable in VS Code, and is provisional in the language-server-node library.

I guess, we should wait wile a copule of other servers/clients implement the API and then move it to stable?

[rcjsuen]

@matklad I’ll do some hacking today and see how it feels.

[rcjsuen]

Technically blocked because of microsoft/vscode-languageserver-node#460 but I guess I'll just change my dependencies for the time being...

[dbaeumer]

@rcjsuen I can move the types to the types package when they become stable. The types package has no proposed support :-)

[dkasak]

I'd like to reiterate @octref's comment from above. As a vim user, the kind is the most interesting aspect of this feature. Is there going to be a recommended set of kinds that servers might support so that the kind names do not diverge between servers?

Out of those proposed by @jrieken above, I feel that the most obvious missing one is a kind for function/method definition. In fact, this is what led me here since I was searching for a vim plugin that implements function text objects and realized that it makes most sense if this was implemented in LSP servers.

Also, I'm unsure where the current proposal is located? I found https://github.com/Microsoft/vscode-languageserver-node/blob/master/protocol/src/protocol.selectionRange.proposed.ts, but there seems to be no mention of kinds there.

[dbaeumer]

@dkasak a first proposed implementation is indeed in the vscode-languageserver-node. We usually update the specification when it stabilizes there. Regarding the kind: we decided to leave it out in a first implementation due to:

• hard to agree and the kinds
• no client right now that make use of it.

That doesn't mean that we can add such a kind later on.

[matklad]

This is now implemented in Emacs, and, with two clients, I think maybe we should stabilize this?

[dbaeumer]

Agree. It is on my list to move it out of proposed for 3.15.

[sam-mccall]

FWIW We're working on this for clangd (C++).
The protocol looks good, though the multi-cursor support feels a bit inconsistent with other features.
We'd be interested in exposing both a Kind, and next/previous sibling at each level, if clients would find that useful.

I'm not sure how to make kind both as useful as possible and language-agnostic. expression/statement/declaration/other is probably easy, but may not be rich enough for some cases. Subclassing like "expression.operator.binary.plus" is richer but may be a can of worms.

[jrieken]

I'm not sure how to make kind both as useful as possible and language-agnostic.

Our initial proposal had the kind property but we had trouble on defining a "common language" for them and ultimately discarded the idea. It would be useful for configurable commands like "expand till declaration" but then you need to agree on what a declaration is...

[Avi-D-coder]

Any conservative set of kinds that can be added onto is better than nothing.
As a vim user I am not going to make keybindings for more than ~5 kinds, after that I will need a UI to discover/select kinds. I would imagine non modal editors will need a UI much sooner.

As minimal future compatible set of kinds is [Expression, Statement, Declaration, Argument]
At any point subclassing, other primitive kinds, custom primitive kinds or any combination of features could be added to the spec.

What matters right now is some tiny list of kinds is included.

On a different note: Subclassing is a great idea. If all custom kinds are subclass of a primitive kind then language agnostic keybindings are easy.

[dkasak]

Again, I feel like the function/procedure/method definition kind is missing from the above. Which languages do not have some way of defining a procedure? I'm not sure which of the above I would put it under. Perhaps it could be shoehorned under Declaration.

[Avi-D-coder]

@dkasak It would depend on the language but in general the name and body of a function/procedure/method is a Declaration, the body is a Expression or in rare cases a Statement. The point of a small list is to force shoehorning.

If subclassing is added a method could be Declaration.function.method or whatever you liked. When adding classes you should always keep in mind that users are only going to have so many keybindings, so while I may have a Declaration binding, I am less likely to have a Declaration.function, and I probably don't have a Declaration.method or Declaration.function.method. As a general rule the lower a subclass is in a common hierarchy the more likely a binding for a supper class will exist.

For this reason I would argue the LSP docs should also contain an unofficial taxonomy that LS authors can add common custom tags to.

[jrieken]

@dkasak It would depend on the language but in general the name and body of a function/procedure/method is a Declaration,

I think the tricky question is if a function argument is a declaration or not and what should happen when triggering 'expand to declaration' while being on an argument?

[Avi-D-coder]

@jrieken If arguments are declarations: expand to declaration on bazz will select bazz 1 and then $ bazz 1 before finally hitting foo = bar $ bazz 1. In other words function composition is O(n) where n is the level of nested functions. Expression based languages can't have that.

foo = bar $ bazz 1

PS: If kinds were added to the spec, I would add immediately add support for them in CoC and Haskell IDE engine.

[yyoncho]

IMHO for the purpose of creating a modal editing interface in the spirit of vim/evil-mode/etc. it will be better and more powerful to return a lightweight AST (e. g. all the ranges in the document). For example:

1. I would like to know that I am in for statement and address it(e. g. delete surrounding for).
2. I would like to address function args definition block (e. g. add action jump/change to params block).
3. I am in if block and I would like to delete the then block.
4. I want to transpose statements, e. g if I have this code and I want to

if (foo) {
  bar();
}
| // cursor here
if (foo1) {
 bar1();
}

5. I would like to implement a function delete it, but keep it ballanced, e. g. if the cursor is before if and I issue a command kill-balanced I would like the whole code block to be killed since the { block is part of the if statement.

if (foo) 
{
  bar();
}

[Avi-D-coder]

@yyoncho It's unclear what implementation your arguing for or against? Does subclassing not address your described use case?

[yyoncho]

@Avi-D-coder my main point is about introducing a new method (e. g. textDocument/ast) instead of adding kind to textDocument/extendSelection. For me personally doesn't matter whether kind will use subclassing or other technique as long as the response contains detailed information(e. g. what is the type of the statement, etc).

[dbaeumer]

Closing. Spec got updated in dbaeumer/3.15 to contain textDocument.selectionRange request.