Ark: Incremental and cancellable computations with salsa

[lionel-]

Salsa is an incremental computation framework built for the rust-analyzer LSP. It makes it easy to cache the result of expensive computations on a given set of inputs. These results can then be used for other expensive computations and so on. Salsa tracks the graphs of intermediate results, memoises them, and when some inputs are invalidated after an update it will only recompute - on demand - the relevant parts of the graph.

https://salsa-rs.github.io/salsa/about_salsa.html
https://rustc-dev-guide.rust-lang.org/salsa.html
https://medium.com/@eliah.lakhin/salsa-algorithm-explained-c5d6df1dd291

Salsa inputs and outputs can be cheaply shared across threads. The interesting part is that invalidation of inputs (e.g. after a DidChange notification from the LSP client) can be used to drive cancellation of background tasks running on other threads. If a task queries an invalidated input, it is cancelled via a special panic that is captured at the task join site. This can then be used to reply to the client with a ContentModified error. The nice thing about this approach is that querying for an expensive computation is exactly the point at which you'd want to cancel your task if it were invalidated.

An alternative cancellation approach in an async setup is to use await as cancellation points. This has the advantage of interacting well with client-iniated cancellation, which causes tower-lsp to drop the request handler's future, which effectively cancels the task at the next await point. This approach is compatible with cancellation driven by cache invalidation.

In order to use salsa, expensive queries must be calculated with pure functions from inputs to outputs and all inputs to expensive queries should be centralised in a data store managed by Salsa. In particular functions implementing these queries should not peek into side state, e.g. from the R session. For this reason this approach aligns well with the goals of decoupling the LSP from the Jupyter kernel (#3180).

Right now we haven't faced any performance issues, but these might arise in the future as we build up the capabilities of our LSP. The immediate advantages of using salsa are:

• Get in the habit of writing our analysis functions in a way that lend itself to be managed by salsa queries.
• A nice cancellation approach for longer running tasks such as diagnostics.

An obvious first candidate for an experiment with salsa would be the computation of DiagnosticContext from (a) console scopes and (b) indexed symbols.

Another candidate is the caching of symbols indexed from a document AST, only rebuilding symbols on the parts that have actually changed.