Code actions use lots of text edits for small changes

[krobelus]

Example reproducer:

1. Clone https://github.com/kak-lsp/kak-lsp (I'm using 1ffcd26021fb2f5818353254e9e15042852bbedb)
2. Open src/main.rs in your editor
3. Goto line 46, the one with use std::path::Path;
4. Hover over std::path::Path and run the code action "Merge Imports".

To apply "Merge Imports", rust-analyzer sends a sequence of 274 text edits, some extending to unrelated lines like 315. This feels a bit weird because their sum is just this:

diff --git a/src/main.rs b/src/main.rs
index 11b623c..53ac623 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -45,4 +45,3 @@ use std::os::unix::net::UnixStream;
 use std::panic;
-use std::path::Path;
-use std::process::{Command, Stdio};
+use std::{path::Path, process::{Command, Stdio}};

perhaps we can make this more minimal?

Of course this difference is not user-visible in most clients. However, the LSP client kak-lsp leaks this noise to the user in some scenarios: it applies each text edit directly inside the Kakoune editor (kind of as if the user had made the edit). Now when the user undoes the code action, Kakoune will use a heuristic to select the ranges that were touched by the text edits. In this case it selects much more than just the two affected lines, which is unfortunate.

I guess various clients have their own ways of squashing sequences of text edits. Undo works properly in VSCode, but it's probably based on a diff of the old/new buffer contents. Computing this diff seems unnecessary if we already have the text edits; we should just make them simpler.

(FWIW kak-lsp currently has a bug on the reproducer: it modifies unrelated lines, probably because it doesn't interpret text edits correctly)

rust-analyzer version: rust-analyzer 2022-01-17

rustc version: rustc 1.56.1 (59eed8a2a 2021-11-01

[Veykril]

This might be due to our diffing algorithm, it is very simplistic and adjusted for some specific behaviour. Ideally we would replace this with a rowan specific implementation of a proper algorithm, like the one used by roslyn.

Current implementation is the following: https://github.com/rust-analyzer/rust-analyzer/blob/be9e7f9aaf742217532f20a80d4cbc15fd185ecf/crates/syntax/src/algo.rs#L151-L252

[krobelus]

Here is a recent compilation of tree diff algorithms.

• GumTree is a good algorithm that combines exact top-down matching followed by bottom-up matching based on similarity heuristics.
• I've briefly looked into the "Concise, Type-Safe, and Efficient Structural Diffing"paper but unless I misread they only match subtrees that have structurally equivalent. This means that the edit script that goes fromA(B, C)toA2(B, C, D)` contains the entire RHS. That's not ideal; we don't want our text edits to touch B and C. I probably misunderstood something but I also couldn't figure out how to run their Scala implementation.

The above two are nice for detecting moves, but I don't think we care about moves (we merely want to produce LSP text edits). I think we should try running a plain old LCS algorithm on leaf nodes, like diffsitter does. Of course this assumes that non-leaf nodes contain no text themselves.