Support iterative fixes in the LSP "Fix All" command

[DanTup]

The dart fix can apply multiple rounds of fixes, but the equiv LSP command (which is wired up to "Auto Fix" in VS Code, which some users like to run on-save) does not.

The dart fix command works by building overlays from the first set of changes and then running the fixes again. This will be more complicated inside the server run by the IDE as we can't modify the overlays without potentially introducing issues (even if they are applied and reverted, because the fixes are async, there's no guarantee the editor won't be sending requests that will have "misunderstood" offsets during that time).

It may be possible to lay another OverlayResourceProvider over the existing one to do this, but will need some testing - see discussion at #47886 (comment).

[DanTup]

@bwilkerson this was the issue mentioned earlier. Based on the text above, it seems like the issue was that dart fix was modifying the overlays (which is fine for it because they're not also being used by an editor). Your linked comments suggest we may be able to wrap another temporary overlay provider over that one, though I haven't tested that yet. I'll make a note to do so soon, as this might actually be a fairly simple fix if that works (or can be made to).

[bwilkerson]

@pq for visibility

[DanTup]

@bwilkerson I started taking a look at this, but hit a snag. The way this currently works in dart fix is:

• compute some edits
• apply edits to overlay
• reanalyze / compute more edits

If we collect all of the edits here, we don't end up with a single change that makes the necessary changes, but rather a set of changes that need applying sequentially to arrive at the expected output. For example in the case of prefer_final_locals and prefer_const_declarations and code var a = 'test'; we end up with:

1. A change that says "replace var with final"
2. A change that says "replace final with const"

These changes conflict, and can only be applied sequentially. In order to apply them in a single operation in VS Code (such that undo buffer works as expected), we need a single set of atomic edits (at least, that's how it seems.. though I'll see if there's a way around this.. I don't see why in theory VS Code couldn't apply some edits sequentially within a single undo record).

I think some of the issues (that is, edits from second round of edits offsets are wrong because they assumed the previous round of edits have already been made) might be fixable by using a shared ChangeBuilder, however I don't think conflicting edits (as occur in the example above) would work. (edit: I don't think this is the right route, because a ChangeBuilder is based from a single document and we're producing edits based on amended documents for each iteration)... In theory I think we should be able to merge the changes, but I'm not sure if that would be a simple task.

[bwilkerson]

I think that merging the edits would be fairly difficult and hence error prone, but I haven't tried, so it might be more doable than I'm thinking it would be.

The only solution that comes to mind is to make all the edits as per dart fix, then return an edit to replace the entire content of the initial version with the entire content of the final version. We could potentially write a diff algorithm that would narrow it down, but I'm not convinced that it would be worth it.

[bwilkerson]

I also have some concerns around performance. If we're iterating then we're re-analyzing the file on each iteration, which might take longer than we want to spend before returning an edit that might or might not be applied. (Unless I'm misremembering and 'Fix All' is actually a command rather than a fix.)

[DanTup]

I think of those options, a full edit and diff is probably better Not doing the diff could be a problem though (which is why we do something similar for formatting - although it's not a real diff because we know only whitespace changes and can just walk two token streams together). A diff seems like the sort of thing there should be well-tested algorithms for we might be able to easily implement in Dart (if there isn't one already in the SDK somewhere 😄).

I also have some concerns around performance.

I was curious about perf too (I noticed the dart fix command on the CLI wasn't terribly fast when testing some of the fixes above on flutter_gallery), but didn't get as far as being able to measure it.

It is a command though, so we're not paying any cost until the user invokes it (we just return a static CodeAction referencing the command from the /codeActions request):

sdk/pkg/analysis_server/lib/src/lsp/handlers/code_actions/dart.dart

Lines 302 to 307 in 15c8dad

	if (shouldIncludeKind(DartCodeActionKind.FixAll))
	createCommand(
	DartCodeActionKind.FixAll,
	'Fix All',
	Commands.fixAll,
	),

We can show progress notifications while it's running though (as we do for refactorings because the first invokcation of them can sometimes be a bit slow).

[bwilkerson]

... if there isn't one already in the SDK somewhere ...

There might be one, but I wasn't able to find it when we were implementing dart fix. We considered having a flag to display a diff of the files rather than just a "we fixed 3 things in this file" message, but it looked like it would be too much work. If you find a diff algorithm, we might reconsider.

It is a command though ...

If it's a command, then I'm not concerned about the performance (the user will know what's happening).

[DanTup]

I also couldn't find one in the SDK, although I did find this:

https://github.com/google/diff-match-patch/tree/master/dart

The repo hasn't been updated in a few years, but with some tweaks for null-safety the code (and tests) work in current Dart:

https://github.com/DanTup/diff-match-patch/tree/dart-null-safe

Although it doesn't seem like the project is maintained any more, so if we used this (it's Apache licence and Google-created, so I presume that would be possible) and there are any issues we'd have to fix them. Reducing it to only the useful diff-producing code gives ~1k lines:

https://gist.github.com/DanTup/a212ed0f02376322b1486af72f2fc52f

This is larger than I was expecting a diff to be, although it seems to describe some reasonable-sounding optimisations (I don't know if this is a common algorithm or something developed by that project though). Any thoughts?

[bwilkerson]

I'm not going to address the question of whether we can use the code. My guess is yes, but I'd want someone else to make that call.

But if we can use some or all of that code, then it probably isn't going to be any bigger than the code we'd end up writing ourselves. Meyer's algorithm is definitely one of the best. The most recent committer is still working here, so we can also reach out if we have any additional questions.

[DanTup]

@bwilkerson if we can get confirmation that it can be used, do you think that's the most sensible path forward? (further up you said you're not sure it's worth it, though I don't know if there are other options besides not supporting this - which might not be a problem, I guess it depends on the number of fixes may require multiple iterations.. I only know of the one given as an example above).

There may be some other benefits to having something like this - --dry-run could be updated to support a diff as you noted above, and we could also perhaps remove the custom handling for the formatter that does this by re-parsing both sets of code (although we might want to compare performance - I suspect since it's much simpler it may also be quicker).