Help TS team to assume ownership of semantic highlighting in TS tooling

[aeschli]

We've been working on our semantic coloring support. This is currently powered by a TS Server plugin but we’d like to merge this work back into TS Server.

The plugin's readme descibed it's purpose and a list of the implemented features.

Also see the Tests for more details: https://github.com/aeschli/typescript-vscode-sh-plugin/blob/master/src/test/semanticTokens.test.ts

Along with the adoption goes the request to improve the encodedSemanticClassifications-full command to also support deltas. See #92963 (comment)

[DanielRosenwasser]

In #92963 (comment), @alexdima mentioned something about a delta strategy.

I can't find any place where this delta strategy is documented. Can you please elaborate on that?

[alexdima]

@DanielRosenwasser Here is the relevant documentation. A DocumentSemanticTokensProvider can optionally implement a method provideDocumentSemanticTokensEdits. This method will be called by the editor after a while and the provider has a chance to give edits relative to the previous result. You can think of them like updates to the previous semantic tokens, flowing from the provider to the editor. The JS Doc explains it in greater detail.

[DanielRosenwasser]

One of the things we brought up when this was first discussed is that TypeScript doesn't have a model where we can correlate the current semantic state of the world with that of the last semantic state. I don't think that that's accounted for in this model.

In Visual Studio we've had APIs to provide semantic classifications which are handled by Roslyn and we simply haven't had to worry about any issues there. This has worked for years, and given the constraints that I've mentioned above, along with the fact with this API each language server has to figure out how to achieve this, I think we need to rethink the approach here.

[CyrusNajmabadi]

In Visual Studio we've had APIs to provide semantic classifications which are handled by Roslyn and we simply haven't had to worry about any issues there. This has worked for years, and given the constraints that I've mentioned above, along with the fact with this API each language server has to figure out how to achieve this, I think we need to rethink the approach here.

I would agree with this. It doesn't make sense to me for languages to have to figure it out. It's non-trivial and would involve a lot of work per-language. In Roslyn we allow the languages to just be 'dumb'. They compute their syntactic or semantic classifications however they see fit, and we just update our host intelligently with the minimal change that's appropriate.

Note that this is what we do with all our taggers. classification, outlining, line separators, reference highlighting, etc. etc. etc. All of these sit on systems where the language is just asked to compute simply, and the host (i.e. Roslyn) intelligently manages those and ensures minimal updating to actual clients.

Having this complex logic centralized has been a boon for all roslyn languages to be able to focus on the language tasks and not on complexities of semantic changes and diffs. I don't think it's reasonable or appropriate to now push that back out onto all the languages again.

[RyanCavanaugh]

Sending deltas is only solving a small part of the problem. We also have to consider that the language side is going to end up spending a lot of time computing semantic information for highlights that are off-screen and remain off-screen - a user editing a large file might only ever scroll a tiny portion of it into view. For TypeScript, a question like "Is this JS identifier actually a class or a function" involves a surprisingly large amount of work, e.g. looking for prototype assignments, looking for this. bindings, and other heuristics; these not individually expensive, but in total can represent a lot of work if done repeatedly over thousands of occurrences.

Worse, edits near the top of the file are going to invalidate a lot of semantic highlights as the file goes in and out of a syntactically valid state, so even under a delta-based scheme we're going to have to send back a bunch of (nontrivially computed) diffs for off-screen tokens.

Even considering none of that, we're looking at 5+ seconds of extra startup responsiveness delay for a large file as VS Code processes the initial highlighting data, which deltas will not fix any of,

I'd like to revisit #92963 to address the underlying concern here and ship a performant feature - VS Code has already invested a lot in making the experience shine in large files and I think we need to continue to keep these scenarios in mind.

[alexdima]

The purpose of DocumentSemanticTokensProvider is to provide semantic tokens for the entire document, in such a way that after those semantic tokens have been provided, scrolling in the editor can render synchronously all the text without flickering, even if there is latency to the language server, like when using VS Code Remote SSH, where the UI and the language server are separated by the internet. This solution is designed for an asynchronous world, where the editor cannot make a synchronous call to the languager server and ask it for tokens in the viewport when painting. I will focus my examples on the DocumentSemanticTokensProvider, but if you find this one too difficult to implement (I'm not sure why that would be the case), there is also a DocumentRangeSemanticTokensProvider, which fetches semantic tokens only for the viewport, but which flickers because they must be fetched asynchronously.

I'm going to try to explain the idea behind provideDocumentSemanticTokensEdits and going to suggest a simple implementation. provideDocumentSemanticTokensEdits is first and foremost about reducing data on the wire. It can also be about computing less, but that is really up to how the language server itself is implemented.

I find it best to reason about an example. So, suppose you open checker.ts. The language server receives an event that the document was opened in the editor and that from now the "truth" lies with the editor and that changes will be pushed to the language server. On some version of TypeScript I have checked out, that file contains 81,047 semantic tokens. With the encoding of 5 x 32 bit integers per token, that is 405,235 x 32 bit integers, or about 1.6MB "on the wire". The encoding can definitely be reduced to 3 integers per token, and that is doable, but that is not so important to this reasoning.

Let's suppose the 1.6MB semantic tokens have made it to the editor, they are now rendered and all is good. But suppose a single edit is done: a new line is inserted at the top of cheker.ts. The editor will adjust the semantic tokens on the UI thread, and they will "stick with the text", so all the tokens will move down, but now the editor must consider that these tokens are potentially invalid. As far as the editor is concerned, the editor cannot understand that in this programming language \n does not carry semantic meaning. So, as far as the editor is concerned, it behaves very similarly when you insert /* and when you insert \n, even though they cary different semantic meaning in TS.

The simple small edit is communicated to the language service with a single text delta event that is small: it will just say that at (1;1) a \n got inserted. So just a few bytes, an event proportional in size to the size of the change. But eventually the editor needs to validate those semantic tokens (think to cover the case of typing /*, it cannot just assume that sticking the tokens with the text is correct). So the editor needs eventually to ask the DocumentSemanticTokensProvider for semantic tokens again. That means that in the \n case, 1.6 MB worth of data needs to be sent again "on the wire" to the editor. All the tokens will be very similar to the previous tokens, but they will have their line number increased by one (or their offset will be increased by 1), depending on the chosen tokens encoding (line,col or offset).

So that is where the provideDocumentSemanticTokensEdits comes in. Instead of sending 1.6MB worth of tokens again on the wire, it is possible to send one or more edits to the previous result which describe the new result, instead of sending the new result in full.

Now, for the simple implementation I have promised. On the language server side, when a provideDocumentSemanticTokens request comes in, compute all the semantic tokens in the file by walking the entire AST. Let's call this result X0 and let's store it in a map associated with the document. Only keep a single semantic tokens result per document. If there is any other previous semantic tokens result stored, delete it. If the document gets closed (the editor will let you know with an event), you can delete the result X0 from the map of open documents.

For a subsequent call to provideDocumentSemanticTokensEdits, X0 (an identifier that you chose before) will be passed in the request. If you find X0 in the result map, proceed, otherwise throw an error. Compute all the semantic tokens in the file by walking the entire AST and generate the result X1. Now you have N0 integers from X0 and N1 integers from X1.

You need to compute one or more edits which brings X0 to X1, let's call that diff(X0,X1). The best way is to implement a LCS algorithm (one that is typically implemented in a diff algorithm, like Myers's), but that might be slow. A simpler way is to check the prefix and the suffix for equality and strip them, and then consider the entire range in the middle as an edit (e.g. axc => ayc, where a, x, y and c are sequences of integers can be expressed as replace x with y). Delete X0 from the stored state and store X1 in full. Return the diff(X0, X1) that you computed before.

If you don't want to do this, then that is ok, simply don't implement provideDocumentSemanticTokensEdits. But if you implement that, 1.6MB are saved almost on each keystroke.