Feature request: "document/extendSelection" for semantic selection

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.

Dirk Bäumer (@dbaeumer)

Dirk Bäumer (@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.

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 .

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.

Alex Kladov (@matklad)

Alex Kladov (@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.

Johannes Rieken (@jrieken)

Awesome Johannes Rieken (@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 Ivan Yonchovski (@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.

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.

👍 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.

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.

Johannes Rieken (@jrieken)

Johannes Rieken (@jrieken) thanks for jumping in here.

Alex Kladov (@matklad) most of the stuff Johannes Rieken (@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 Johannes Rieken (@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

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.

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).

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) :)

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

Alex Kladov (@matklad)

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

Alex Kladov (@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?

Johannes Rieken (@jrieken)

Johannes Rieken (@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 :-)

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

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.

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...

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.

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.

Denis Kasak (@dkasak)

Denis Kasak (@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.

Denis Kasak (@dkasak)

Denis Kasak (@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?

Johannes Rieken (@jrieken)

Johannes Rieken (@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.

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:

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

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

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();
}

Ivan Yonchovski (@yyoncho)

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

Avi Dessauer (@Avi-D-coder)

Avi Dessauer (@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).

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

Navigation Menu

Repository navigation

Feature request: "document/extendSelection" for semantic selection #613

23 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Feature request: "document/extendSelection" for semantic selection #613

Description

Activity

matklad commented on Dec 8, 2018

yyoncho commented on Dec 9, 2018

matklad commented on Dec 9, 2018

jrieken commented on Dec 10, 2018

matklad commented on Dec 10, 2018

matklad commented on Dec 10, 2018

jrieken commented on Dec 10, 2018

matklad commented on Dec 10, 2018

dbaeumer commented on Dec 11, 2018

matklad commented on Dec 11, 2018

jrieken commented on Dec 11, 2018

matklad commented on Dec 11, 2018

dbaeumer commented on Dec 11, 2018

jrieken commented on Dec 12, 2018

matklad commented on Dec 12, 2018

23 remaining items

dbaeumer commented on Aug 13, 2019

sam-mccall commented on Aug 28, 2019

jrieken commented on Aug 29, 2019

Avi-D-coder commented on Aug 29, 2019

dkasak commented on Aug 29, 2019

Avi-D-coder commented on Aug 29, 2019

jrieken commented on Aug 29, 2019

Avi-D-coder commented on Aug 29, 2019

yyoncho commented on Aug 29, 2019

Avi-D-coder commented on Aug 29, 2019

yyoncho commented on Aug 30, 2019

dbaeumer commented on Sep 20, 2019

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions