x/tools/internal/diff: suboptimal line edits for a common prefix #64023
Comments
findleyr
added
gopls
|
Change https://go.dev/cl/540715 mentions this issue: |
|
@pjweinb, since the problem is in the core of the diff algorithm, on which you are the expert (and not in the ToUnified presentation logic), could you take a look at it? Thanks. |
The new diff.Strings algorithm produces suboptimal line edits, as described in golang/go#64023, which lead to confusing test data. Switch our test diff output to the older myers package (ideally temporarily). Change-Id: I2327f5551db795dac47c6c8f2a936a5ce49ab8e0 Reviewed-on: https://go-review.googlesource.com/c/tools/+/540715 Auto-Submit: Robert Findley <rfindley@google.com> Reviewed-by: Alan Donovan <adonovan@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
|
This is a case where a longest common subsequence doesn't include the
common prefix, and unfortunately the algorithm finds it. I think that it's
not hard to fix.
…On Thu, Nov 9, 2023 at 11:27 AM Alan Donovan ***@***.***> wrote:
Assigned #64023 <#64023> to @pjweinb
<https://github.com/pjweinb>.
—
Reply to this email directly, view it on GitHub
<#64023 (comment)>, or
unsubscribe
<https://github.com/notifications/unsubscribe-auth/ABJIAI4PVQ3U5TAGKKNCYYDYDT75PAVCNFSM6AAAAAA7DV2PRKVHI2DSMVQWIX3LMV45UABCJFZXG5LFIV3GK3TUJZXXI2LGNFRWC5DJN5XDWMJQHEYTKNBSGE4TSOA>
.
You are receiving this because you were assigned.Message ID:
***@***.***>
|
Understood. I think this is why many diff algorithms do a line-based diff first before narrowing to sub-line diffs: when "a\n" is considered as a single unit, the trailing '\n' can't be considered part of a sequence. Perhaps the simplest fix is to do the same: start by diffing lines, and then do a second sub-line pass on each hunk. This may also lead to better performance. |
|
Change https://go.dev/cl/541382 mentions this issue: |
|
This is perhaps unfortunate, but it is not a bug. The same visibly unfortunate thing can happen without a common prefix: diff(xyAA, yyAABA) has the same problem of not returning a minimal diff and being small enough to be dissatisfying to a human observer. |
Noticed in https://go.dev/cl/539656. The x/tools/internal/diff package produces suboptimal line diffs, in that it generates edits inside of common prefixes.
Here is a minimal example: https://go.dev/play/p/kS7ykVOJzbm
While the edits are valid, I think it's a bug that an edit is inserted inside a common prefix. Pragmatically, it causes the unified diff to be rather confusing. It may also cause non-nonsensical movement of the cursor in gopls, but I've yet to demonstrate this in practice.
At the very least, I think this warrants investigation.
CC @pjweinb @adonovan
The text was updated successfully, but these errors were encountered: