Make it clearer the responsibilities/gurantees for orders of multiple text edits

[DanTup]

This was discussed a little in #279, including this comment from @dbaeumer:

The burden of doing the right thing is basically pushed to the too (e.g. client)

the changes should be applied in the order in which they are sent

So there is no need to order the edits

My understanding of these three is that the client must send these edits in offset-descending order (despite the fact that semantically the order should not matter, because the offsets are based on the original document). However I don't think this is clear from the spec:

 	/**
	 * The actual content changes. The content changes describe single state changes
	 * to the document. So if there are two content changes c1 and c2 for a document
	 * in state S then c1 move the document to S' and c2 to S''.
	 */

It's possible this says the same thing, but it's not very clear to me (so it might not be to some other devs). I think it should be very explicit whether it is required for the client to send the edits in reverse-offset order (or if they're not, that a server should handle them in the wrong order).

VS Code had a bug around this (microsoft/vscode#88570) where some extensions were mutating the edits and they arrived to other extensions in the wrong order (I would presume that the Node LSP client was also effected unless it's manually sorting the edits before sending) and it's still not clear where the responsibilities lie (I asked for clarification, but the issue was just closed). I think the less ambiguity in the specs, the less likely bugs like this will crop up.

[dbaeumer]

Actually no. For content changes the order is important and it is not in offset-descending order. I clarifies this in the comment now:

	/**
	 * The actual content changes. The content changes describe single state changes
	 * to the document. So if there are two content changes c1 (at array index 0) and
	 * c2 (at array index 1) for a document in state S then c1 moves the document from
	 * S to S' and c2 from S' to S''. So c1 is computed on the state S and c2 is computed
	 * on the state S'.
	 */

[DanTup]

Oh sorry, I misunderstood. My understanding was that in VS Code the changes all use offsets from the original state, and it doesn't look like the LSP client changes them in any way. Does this mean VS Code is also intended to guarantee edits can be applied sequentially? (If so, it doesn't seem to be documented, and microsoft/vscode#11487 (comment) suggests it's not guaranteed).

[dbaeumer]

IMO this is clearly stated with:

The contract is that if you begin following independently a certain document and consistently apply the content change events (in the order you received them) you will end up with a document in the same state (same text) as our document.

[DanTup]

I read that as the separate events, rather than the items within the array of a single event. However, even so, it does not state guarantees around the ordering or semantics of the offsets. If the items in the array do come through in offset-descending order (as they seem to, and the bug fix above prevents other extensions messing with) then applying them in-order is unambigious. If they come through in offset-ascending order (I see nothing to say that they cannot) then it is ambigious (can they be applied sequentially, or do all offsets refer to the original state?).

Right now I've added code to sort the edits in offset-descending order before applying sequentially because it's not clear (I appreciate this isn't an LSP question, it's VS Code API, though my requests for clarification there keep going unanswered and this seems kinda important to clarify).

[DanTup]

I just found microsoft/vscode#23173 (comment), which seems to state that they can be applied sequentially. This seems different to what I was told in the past :-(

I don't know why this isn't explicit in the docs though. New implementors don't read through all GH issues, they just look at the API docs.

[dbaeumer]

There is no need to sort something since every event and every change in the text document content changes move the document exactly one state forward. Sorting is only necessary if an event or edit has n edits and moves the state of a document exactly one state forward (although n edits are applied).

I always thought that this is clear describing it as state changes but I can add a sentence as well that the event should be applied in the order they are received.

[DanTup]

@dbaeumer I'm just a bit confused because I've previously had responses that seem to differ in VS Code, so it's not clear what the rules are where. For example:

microsoft/vscode#49114

This came from an edit coming the other way - the language server provided edits to be applied sequentially (and each offset took into account the previous edit), but VS Code interpreted all offsets as being from the initial state.

The responses there made me believe that VS Code worked with non-sequential edits, for ex:

Yeah, you can fire sequential edits (which isn't proper)

I am not very keen on adding this because I don't want to confuse folks. Today, things are easy. You are in state A, apply n edits, end you end in state B.

This led me to believe that VS Code may also send me back edits using this assumption (and therefore it's not safe to just apply sequentially) but now I'm still not sure.

[dbaeumer]

The reason for this is to keep the API simple for clients. In both cases (events and edits) clients don't need to sort anything. For events clients simply need to apply the changes in the order they appear, for edits the client / tools takes care of doing the right ordering. The provider of a text edits (e.g the extension or server) can provide them in any order. To achieve this a single event change therefore describes the document transformation from S' to S''. In contrast for edits n edits describe the transformation from S' to S''.

[DanTup]

@dbaeumer I'm still confused. What's written in the issue I linked above doesn't seem to match what you're saying. I think what you're saying makes sense, but the edits I have to send to VS Code are not such that they could be applied in-sequence. VS Code requires the builder of the edits to provide offsets based on the initial state, not the state before each change.

const changes = new vs.WorkspaceEdit();
changes.replace(document.uri, new vs.Range(new vs.Position(0, 0), new vs.Position(0, 0)), "LINE 1\n");
changes.replace(document.uri, new vs.Range(new vs.Position(1, 0), new vs.Position(1, 0)), "LINE 2\n");
// This code does *not* insert at line 3, it inserts at line 5 because of the two newlines inserted above.
changes.replace(document.uri, new vs.Range(new vs.Position(2, 0), new vs.Position(2, 0)), "LINE 3\n");
await vs.workspace.applyEdit(changes);

This seems different to what you're describing here. Sure, this is a different part of the API and it's ok for it to behave differently - but that's where the confusion comes from if the specs are not explicit.

[dbaeumer]

Actually the LSP and the VS Code API have the same constraints when it comes to events and text edits. And what you are seeing is expected. The thing is that you could even added the changes in reverse order and the outcome would still be the same.

As you are mentioning that doesn't mean that your edit at position p is in the final document at position p.

Consider you have a line 0123456789 and you add the following two edits

• insert A at position 7
• replace [1,2] with CCC

then you end up with 0CCC3456A789 So all edits are described position wise on state S and applying them produce S'. But as said the final position don't have to be the once provided in the edit.

Side note: in Eclipse (which uses the same model) you can track edit positions if you want to know at which positions in state S' the edit ended up. But VS Code doesn't have this support.

[DanTup]

@dbaeumer I'm getting more confused :-)

So all edits are described position wise on state S and applying them produce S'. But as said the final position don't have to be the once provided in the edit.

Isn't this different to what's described above? These edits are not the same as if they are applied sequentially, in-order (if they were, then LINE3 would be inserted at line 3, not line 5).

Side note: in Eclipse (which uses the same model) you can track edit positions if you want to know at which positions in state S' the edit ended up.

This sounds a bit like something I requested at microsoft/vscode#54147. Right now I have my own implementation of it (which subscribes to edits and translates the tracked positions).

[dbaeumer]

The sequence in which you provide the edits is irrelevant. They are all described on state S.

const changes = new vs.WorkspaceEdit();
changes.replace(document.uri, new vs.Range(new vs.Position(0, 0), new vs.Position(0, 0)), "LINE 1\n");
changes.replace(document.uri, new vs.Range(new vs.Position(1, 0), new vs.Position(1, 0)), "LINE 2\n");
// This code does *not* insert at line 3, it inserts at line 5 because of the two newlines inserted above.
changes.replace(document.uri, new vs.Range(new vs.Position(2, 0), new vs.Position(2, 0)), "LINE 3\n");
await vs.workspace.applyEdit(changes);

and this

const changes = new vs.WorkspaceEdit();
changes.replace(document.uri, new vs.Range(new vs.Position(2, 0), new vs.Position(2, 0)), "LINE 3\n");
changes.replace(document.uri, new vs.Range(new vs.Position(1, 0), new vs.Position(1, 0)), "LINE 2\n");
changes.replace(document.uri, new vs.Range(new vs.Position(0, 0), new vs.Position(0, 0)), "LINE 1\n");
await vs.workspace.applyEdit(changes);

produce the same result.

This is done since these edits are usually generated traversing tree (sometime even to independent walkers) and require that they sequence things will make this very complicated.

The only exception to this rule is insertion at the same position. Here the first in the array wins.

But as said and you experienced inserting something at line two might not end on line two if you manipulate text before line two. Same for thing on a specific line.

[DanTup]

The sequence in which you provide the edits is irrelevant

Right - that's my point. For the WorkspaceEdit given to VS Code, ordering is imported. But above, in relation to text document changes, you said:

For content changes the order is important

My point is that it's confusing that these are different - they are both descriptions of edits to a document but for one the offsets are all based on the original state and the other they're based on the state after applying the previous edits. The docs do not make it very clear where order is/is not important. When two very similar things behave differently, I think it's important for the specs to be absolutely clear.

[dbaeumer]

The reason for the difference is to make live easy for clients.

• for events (content changes) simply take them in the order you receive them and apply them without thinking (e.g sorting).
• for edits simply create them in the order you want for a given document content without thinking

I tried to make this clear by describing the state changes that happen. But I will add a sentence on how to apply the changes.

[DanTup]

The reason for the difference is to make live easy for clients.

Right - I'm not questioning the reason - just explaining why I think it's confusing and the docs should be explicit. People building extensions will likely just read the API docs (and not all GH issues), so they may have the same confusion I have (or worse, just implement things wrong and then have puzzling bug reports from users in the future). I just think the specs should be as explicit as possible, including calling out anything that might be incorrectly assumed. Tracking down bugs in these sorts of things can be time consuming.

[jvican]

I was kind of struggling with the interpretation of text edits as well before reading this thread.

I think the spec could better motivate the differences between workspace edits and content change edits, or encode the rule you've just mentioned @dbaeumer in your last comment. I think it's a good decision to model this in such a way that it makes life easier for clients.

One thing that remains unclear to me is why clients have a better time sending the content changes events with offsets referring to the original document. Is it because several changes might fire up within some timeframe and then be batched and sent to the language server? Otherwise, I would expect clients to process user changes sequentially and with offsets depending on the last applied changes within the same event.

[DanTup]

One thing that remains unclear to me is why clients have a better time sending the content changes events with offsets referring to the original document

My guess is that this usually occurs with multi-cursor-edits, so if the user has three cursors and types "a" it's trivial to make three edits that are at those three offsets that insert "a".

Always sending the edits in reverse-descending order would mean it doesn't matter so it's easier on everyone - and that's what I think VS Code intends to do (based on the fix for microsoft/vscode#88310), but since it doesn't documented I'm not sure we should be relying on it.

I don't know why both the VS Code API and the LSP specs don't describe this in explicit detail, it's a frustrating sort of bug to track down, and when you do track it down, it's not very clear where the bug lies.

[jvican]

@DanTup That explanation makes sense, though I've just re-read the whole thing again and realized that my question is wrong: content changes don't contain offsets referring to the original document, it's only text edits coming from WorkspaceEdits that do contain references to the original offsets. This matches my expectation of "what's easy to do on the client-side".

[DanTup]

it's only text edits coming from WorkspaceEdits that do contain references to the original offsets

Yep, though those edits may have been generated with data from a server. In the Dart extension even today we still have to check edits from the server to see if they're in reverse order. If they're not (which occurs for a few types of edits) we apply them sequentially with separate edits, which means the undo buffer becomes multi-step. I only discovered this after much troubleshooting - which is exactly why I think the specs should be more explicit and helpful, to avoid others having similar hard-to-track-down bugs in future (spec updates are way cheaper than diagnosing intermiddent bugs like this).

[dbaeumer]

For text edits the spec already contains:

A TextDocumentEdit describes all changes on a version Si and after they are applied move the document to version Si+1. So the creator of a TextDocumentEdit doesn't need to sort the array of edits or do any kind of ordering. However the edits must be non overlapping.

I added the following for content changes:

	 * To mirror the content of a document using change events use the following approach:
	 * - start with the same initial content
	 * - apply the 'textDocument/didChange' notifications in the order you recevie them.
	 * - apply the `TextDocumentContentChangeEvent`s in a single notification in the order
	 *   you receive them.

I want to point out one additional thing: the spec intentionally leaves it open how a client applies text edits since this highly depends on the internal data structure used by the client. One easy approach is of course to reverse sort them and then apply them.

[DanTup]

For text edits the spec already contains:

"A TextDocumentEdit describes all changes on a version Si and after they are applied move the document to version Si+1. So the creator of a TextDocumentEdit doesn't need to sort the array of edits or do any kind of ordering."

I still think this should be explicit in pointing out that offsets for all edits are relative to the original document, such as:

"A TextDocumentEdit describes all changes on a version Si and after they are applied move the document to version Si+1 such that all offsets are based on Si and the order of edits is not important. Edits must be non overlapping."

FWIW, I was mostly complaining about the VS Code API docs here:

https://code.visualstudio.com/api/references/vscode-api#TextDocumentChangeEvent

It has no such text, and even now I am still unclear what the rules around its edits are. Is ordering important? If not, why was the recent fix made to stop extensions reversing the order?

I added the following for content changes:

Similarly, I think this text should also appear on the contentChanges field here?

"apply the TextDocumentContentChangeEvents in a single notification in the order you receive them."

Also, since this differs from the above and the offsets are not based from the original state (and thus, order is important) I think it should also be explicitly called out, for ex:

"apply the TextDocumentContentChangeEvents in a single notification in the order interpreting offsets based on the document after previous edits in the notification have been applied."