[tools] internal/diff: fix lineEdits
4 views
Skip to first unread message
Peter Weinberger (Gerrit)
May 28, 2023, 8:40:12 AM5/28/23
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Peter Weinberger has uploaded this change for review.
internal/diff: fix lineEdits
The code for computing unified diffs, used only in tests,
was broken because the code to turn computed diffs into
whole-line diffs was buggy. The code has been rewritten,
and tests have been adjusted to match.
Fixes: golang/go#60379
Change-Id: I01f81d9c1f1f48287e03fe5a6d15b1a5c068be7f
---
M internal/diff/diff.go
M internal/diff/diff_test.go
M internal/diff/difftest/difftest.go
3 files changed, 103 insertions(+), 58 deletions(-)
diff --git a/internal/diff/diff.go b/internal/diff/diff.go
index 602f1e7..858f4c7 100644
--- a/internal/diff/diff.go
+++ b/internal/diff/diff.go
@@ -8,7 +8,6 @@
import (
"fmt"
"sort"
- "strings"
)
// An Edit describes the replacement of a portion of a text file.
@@ -18,7 +17,7 @@
}
func (e Edit) String() string {
- return fmt.Sprintf("{Start:%d,End:%d,New:%s}", e.Start, e.End, e.New)
+ return fmt.Sprintf("{Start:%d,End:%d,New:%q}", e.Start, e.End, e.New)
}
// Apply applies a sequence of edits to the src buffer and returns the
@@ -109,61 +108,81 @@
// resulting edit replaces one or more complete lines.
// See ApplyEdits for preconditions.
func lineEdits(src string, edits []Edit) ([]Edit, error) {
+ // make sure they are sorted and non-overlapping
edits, _, err := validate(src, edits)
if err != nil {
return nil, err
}
-
- // Do all edits begin and end at the start of a line?
- // TODO(adonovan, pjw): why does omitting this 'optimization'
- // cause tests to fail? (TestDiff/insert-line,extra_newline)
- for _, edit := range edits {
- if edit.Start >= len(src) || // insertion at EOF
- edit.Start > 0 && src[edit.Start-1] != '\n' || // not at line start
- edit.End > 0 && src[edit.End-1] != '\n' { // not at line start
- goto expand
+ tmp := make([]Edit, 0, len(edits))
+ // extend each edit to the left, until it starts at 0, or just after
+ // \n, or touches the previous edit
+loop:
+ for n := range edits {
+ e := edits[n]
+ // if it doesn't start at 0 or just after a \n,
+ // backwards until it touches the previous, starts just after a \n, or hits 0.
+ var i int
+ for i = e.Start; i > 0 && src[i-1] != '\n'; i-- {
+ if len(tmp) > 0 && i == tmp[len(tmp)-1].End {
+ // merge with previous, and don't use e
+ e.New = src[i:e.Start] + e.New
+ e.Start = i
+ tmp[len(tmp)-1].End = e.End
+ tmp[len(tmp)-1].New += e.New
+ continue loop
+ }
}
- }
- return edits, nil // aligned
-
-expand:
- expanded := make([]Edit, 0, len(edits)) // a guess
- prev := edits[0]
- // TODO(adonovan): opt: start from the first misaligned edit.
- // TODO(adonovan): opt: avoid quadratic cost of string += string.
- for _, edit := range edits[1:] {
- between := src[prev.End:edit.Start]
- if !strings.Contains(between, "\n") {
- // overlapping lines: combine with previous edit.
- prev.New += between + edit.New
- prev.End = edit.End
- } else {
- // non-overlapping lines: flush previous edit.
- expanded = append(expanded, expandEdit(prev, src))
- prev = edit
+ if i < e.Start {
+ e.New = src[i:e.Start] + e.New
+ e.Start = i
}
+ tmp = append(tmp, e)
}
- return append(expanded, expandEdit(prev, src)), nil // flush final edit
+ // by construction, each edit in tmp starts at 0 or just after a \n,
+ // and they don't overlap.
+ // extend each edit to the right until it ends at eof or with a \n
+ ans := make([]Edit, 0, len(tmp))
+ for n := range tmp {
+ e := tmp[n]
+ if wholeLine(src, e) {
+ // it must replace a whole line too
+ j := e.End
+ for ; j < len(src) && src[j-1] != '\n'; j++ {
+ }
+ if j > e.End {
+ e.New += src[e.End:j]
+ e.End = j
+ }
+ ans = append(ans, e)
+ continue
+ }
+ j := e.End
+ if e.Start == e.End && e.End < len(src) {
+ // avoid trouble with an insertion at the beginning of a line
+ j++
+ }
+ for ; j < len(src) && src[j-1] != '\n'; j++ {
+ }
+ if j > e.End {
+ e.New += src[e.End:j]
+ e.End = j
+ }
+ ans = append(ans, e)
+ }
+ return ans, nil
}
-
-// expandEdit returns edit expanded to complete whole lines.
-func expandEdit(edit Edit, src string) Edit {
- // Expand start left to start of line.
- // (delta is the zero-based column number of of start.)
- start := edit.Start
- if delta := start - 1 - strings.LastIndex(src[:start], "\n"); delta > 0 {
- edit.Start -= delta
- edit.New = src[start-delta:start] + edit.New
+func wholeLine(src string, e Edit) bool {
+ // Needs to start at either 0 or just after \n
+ if e.Start != 0 && src[e.Start-1] != '\n' {
+ return false
}
-
- // Expand end right to end of line.
- end := edit.End
- if nl := strings.IndexByte(src[end:], '\n'); nl < 0 {
- edit.End = len(src) // extend to EOF
- } else {
- edit.End = end + nl + 1 // extend beyond \n
+ // If it is an insertion or replacement, that must end in \n
+ if len(e.New) > 0 && e.New[len(e.New)-1] == '\n' {
+ return true
}
- edit.New += src[end:edit.End]
-
- return edit
+ // or go to the end of the src
+ if e.End == len(src) {
+ return true
+ }
+ return false
}
diff --git a/internal/diff/diff_test.go b/internal/diff/diff_test.go
index b6881c1..9d01449 100644
--- a/internal/diff/diff_test.go
+++ b/internal/diff/diff_test.go
@@ -107,6 +107,14 @@
if !reflect.DeepEqual(got, edits) {
t.Errorf("LineEdits got\n%q, want\n%q\n%#v", got, edits, tc)
}
+ // make sure that applying the edits gives the expected result
+ fixed, err := diff.Apply(tc.In, got)
+ if err != nil {
+ t.Error(err)
+ }
+ if fixed != tc.Out {
+ t.Errorf("Apply(LineEdits): got %q, want %q", fixed, tc.Out)
+ }
})
}
}
diff --git a/internal/diff/difftest/difftest.go b/internal/diff/difftest/difftest.go
index 9b00590..47229a2 100644
--- a/internal/diff/difftest/difftest.go
+++ b/internal/diff/difftest/difftest.go
@@ -31,13 +31,15 @@
Edits, LineEdits []diff.Edit
NoDiff bool
}{{
- Name: "empty",
- In: "",
- Out: "",
+ Name: "empty",
+ In: "",
+ Out: "",
+ LineEdits: []diff.Edit{},
}, {
- Name: "no_diff",
- In: "gargantuan\n",
- Out: "gargantuan\n",
+ Name: "no_diff",
+ In: "gargantuan\n",
+ Out: "gargantuan\n",
+ LineEdits: []diff.Edit{},
}, {
Name: "replace_all",
In: "fruit\n",
@@ -220,9 +222,9 @@
{Start: 14, End: 14, New: "C\n"},
},
LineEdits: []diff.Edit{
- {Start: 0, End: 6, New: "C\n"},
- {Start: 6, End: 8, New: "B\nA\n"},
- {Start: 10, End: 14, New: "A\n"},
+ {Start: 0, End: 4, New: ""},
+ {Start: 6, End: 6, New: "B\n"},
+ {Start: 10, End: 12, New: ""},
{Start: 14, End: 14, New: "C\n"},
},
}, {
@@ -279,6 +281,22 @@
Edits: []diff.Edit{{Start: 3, End: 3, New: "\nbbb"}},
LineEdits: []diff.Edit{{Start: 0, End: 4, New: "aaa\nbbb\n"}},
Unified: UnifiedPrefix + "@@ -1,2 +1,3 @@\n aaa\n+bbb\n ccc\n",
+ }, {
+ Name: "60379",
+ In: `package a
+
+type S struct {
+s fmt.Stringer
+}
+`,
+ Out: `package a
+
+type S struct {
+ s fmt.Stringer
+}
+`,
+ Edits: []diff.Edit{{Start: 27, End: 27, New: "\t"}},
+ LineEdits: []diff.Edit{{Start: 27, End: 42, New: "\ts fmt.Stringer\n"}},
},
}
To view, visit change 498975. To unsubscribe, or for help writing mail filters, visit settings.
kokoro (Gerrit)
May 28, 2023, 8:49:27 AM5/28/23
to Peter Weinberger, goph...@pubsubhelper.golang.org, Gopher Robot, golang-co...@googlegroups.com
Attention is currently required from: Peter Weinberger.
Kokoro presubmit build finished with status: FAILURE
Logs at: https://source.cloud.google.com/results/invocations/c2807c5f-18f8-4afc-aa25-29edaf2e4670
Patch set 1:gopls-CI -1
Peter Weinberger (Gerrit)
May 28, 2023, 8:59:13 AM5/28/23
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention is currently required from: Peter Weinberger.
Peter Weinberger uploaded patch set #2 to this change.
The following approvals got outdated and were removed: Run-TryBot+1 by Peter Weinberger, TryBot-Result-1 by Gopher Robot, gopls-CI-1 by kokoro
internal/diff: fix lineEdits
The code for computing unified diffs, used only in tests,
was broken because the code to turn computed diffs into
whole-line diffs was buggy. The code has been rewritten,
and tests have been adjusted to match.
Fixes: golang/go#60379
Change-Id: I01f81d9c1f1f48287e03fe5a6d15b1a5c068be7f
---
M internal/diff/diff.go
M internal/diff/diff_test.go
M internal/diff/difftest/difftest.go
3 files changed, 104 insertions(+), 58 deletions(-)
To view, visit change 498975. To unsubscribe, or for help writing mail filters, visit settings.
kokoro (Gerrit)
May 28, 2023, 9:10:07 AM5/28/23
to Peter Weinberger, goph...@pubsubhelper.golang.org, Gopher Robot, golang-co...@googlegroups.com
Attention is currently required from: Peter Weinberger.
Kokoro presubmit build finished with status: SUCCESS
Logs at: https://source.cloud.google.com/results/invocations/72e0b3c2-02e0-4069-ade8-d74595f065a1
Patch set 2:gopls-CI +1
Alan Donovan (Gerrit)
May 30, 2023, 11:19:08 PM5/30/23
to Peter Weinberger, goph...@pubsubhelper.golang.org, kokoro, Gopher Robot, golang-co...@googlegroups.com
Attention is currently required from: Peter Weinberger.
1 comment:
Patchset:
Thanks Peter. I spent quite a while studying this CL today and it helped me understand what was wrong with the original one-copy (or zero-copy in the fast-path case) implementation. I've mailed you two CLs, the first to fix a bug in the fast path, which resolves the primary issue #60379, and a second to fix the same bug in the slow path, which means we can remove the recent workaround for #59232 we added to the Unified formatter, which was the wrong place for the fix.
Perhaps the need for the two CLs is an argument against having a fast path, but at least we now understand it completely.
To view, visit change 498975. To unsubscribe, or for help writing mail filters, visit settings.
Peter Weinberger (Gerrit)
Jun 1, 2023, 2:34:01 PM6/1/23
to goph...@pubsubhelper.golang.org, Alan Donovan, kokoro, Gopher Robot, golang-co...@googlegroups.com
Reply all
Reply to author
Forward
0 new messages