Support sequential request processing or selective request ordering

[radeksimko]

Asynchronous processing of requests is useful from performance perspective. Unfortunately there are scenarios in LSP where ordering matters.

One example is when the client sends a number of partial text edits which need to be applied in that particular order.

As per LSP it is necessary to process any textDocument/didChange requests in the same order they were received:

https://microsoft.github.io/language-server-protocol/specifications/specification-current/#textDocument_didChange

        /*
	 * 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 receive them.
	 * - apply the `TextDocumentContentChangeEvent`s in a single notification in the order
	 *   you receive them.
	 */

In theory the incoming requests could be ordered by IDs, but:

1. IDs are not even guaranteed to be numbers in LSP and even when they are the numbers may not have any meaning
2. Even though clients seem to be sending IDs in textDocument/didChange requests, the LSP technically documents this as a notification method - i.e. request should not contain ID and should not be responded to

In some cases it may be possible to order requests by version ID, but the sequence may not be complete, so there is no point in queuing the requests and waiting if a particular version arrives.

https://microsoft.github.io/language-server-protocol/specifications/specification-current/#versionedTextDocumentIdentifier

The version number of a document will increase after each change, including
undo/redo. The number doesn't need to be consecutive.

---

gopls (Go language server) seems to be implementing purely sequential server, which I don't is strictly necessary, but it probably reduces the complexity quite a bit which may be preferable. i.e. It is IMO sensible to temporarily compromise the performance in favour of getting the overall implementation right.

Lastly the LSP spec says the following about ordering:

Request, Notification and Response ordering

Responses to requests should be sent in roughly the same order as the requests appear on the server or client side. So for example if a server receives a textDocument/completion request and then a textDocument/signatureHelp request it will usually first return the response for the textDocument/completion and then the response for textDocument/signatureHelp.

However, the server may decide to use a parallel execution strategy and may wish to return responses in a different order than the requests were received. The server may do so as long as this reordering doesn’t affect the correctness of the responses. For example, reordering the result of textDocument/completion and textDocument/signatureHelp is allowed, as these each of these requests usually won’t affect the output of the other. On the other hand, the server most likely should not reorder textDocument/definition and textDocument/rename requests, since the executing the latter may affect the result of the former.

[creachadair]

I believe it should already be possible to achieve sequential processing by setting Concurrency: 1 in the server options. The server processes incoming request batches in order of arrival and limits the number of handlers that can be concurrently active to that value. I think the only corner case is that order of resolution within a batch is not constrained; however, the entire batch is resolved before any results are reported, so it shouldn't matter.

Does that suffice for your purposes, or is there a case that still doesn't cover?

[radeksimko]

That is actually something I already tried 😄 and it does significantly reduce the chance of this occurring, but it appears there are still some edge cases users are hitting. See hashicorp/terraform-ls#161 or more specifically request/response log: https://gist.github.com/amasover/f7d8c8e7091b316079853da6bff80907

I can try to come up with a test case that would fail under go test -race

[creachadair]

That is actually something I already tried 😄 and it does significantly reduce the chance of this occurring, but it appears there are still some edge cases users are hitting.

Thank you for the additional context.

Even with concurrency 1 it won't be perfect—it's still possible for two consecutive requests that arrive nearby in time to be issued (i.e., passed to their handlers) out of order. I thought about that case, but didn't consider it to be problematic: If (I reasoned) the API updates a state machine, the client can guarantee the desired order of requests by sequencing calls.

Here, I see, the problem is specific to notifications—for which the client cannot sequence issue by definition. The LSP (implicitly) expects notifications to behave like sequential atomic operations—specifically that if notification B is received after notification A, that B will not issue until A is complete. I suspect this was accidental rather than a design choice (Hyrum's Law at work).

One practical approach might be to introduce a specific barrier for notifications, so that at most one notification handler can be in-flight at a time. I think that would address the difficulty described in this issue.

[creachadair]

After further consideration, I realized the barrier I described isn’t sufficient in itself: Even if only one notification can be processed at a time, the order of issue is what governs this case. We would also need to ensure that issue order (at least for notifications) follows arrival order strictly.

[creachadair]

So I think I found a decent way to handle this. @radeksimko can you please try patching #21 and see if that solves the problem reported above?

[creachadair]

Note that there is still a bug in #21 around the order of operations at server shutdown, but I will update the PR with the fix when I have sorted it out.

Edit: The bug is fixed.

[radeksimko]

Thank you for the PR, I will take some time this week to review the code more closely and see if it solves the problem, but it looks good at first sight!

I also published custom build of our language server and posted links in the relevant issue, so hopefully @amasover (and anyone else experiencing the same bug) can also help verifying the patch: hashicorp/terraform-ls#161 (comment)

[amasover]

I replied on the other issue as well, but basically...I'm not seeing any errors after running with the custom build. I was never able to reproduce the issue reliably in the first place, so we can't be 100% sure, but seems likely to me that it is fixed.