internal/diff: simplify API, break span dependency
diff.TextEdit (now called simply Edit) no longer has a Span,
and no longer depends on the span package, which is really
part of gopls. Instead, it records only start/end byte
offsets within an (implied) file.
The diff algorithms have been simplified to avoid the need to
map offsets to line/column numbers (e.g. using a token.File).
All the conditions actually needed by the logic can be derived
by local string operations on the source text.
This change will allow us to move the span package into the
gopls module.
I was expecting that gopls would want to define its own
Span-augmented TextEdit type but, surprisingly, diff.Edit
is quite convenient to use throughout the entire repo:
in all places in gopls that manipulate Edits, the implied
file is obvious. In most cases, less conversion boilerplate
is required than before.
API Notes:
- diff.TextEdit -> Edit (it needn't be text)
- diff.ApplyEdits -> Apply
- source.protocolEditsFromSource is now private
Change-Id: I4d7cef078dfbd189b4aef477f845db320af6c5f6
Reviewed-on: https://go-review.googlesource.com/c/tools/+/436781
Run-TryBot: Alan Donovan <adonovan@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
gopls-CI: kokoro <noreply+kokoro@google.com>
Reviewed-by: Robert Findley <rfindley@google.com>
Auto-Submit: Alan Donovan <adonovan@google.com>
diff --git a/internal/diff/diff.go b/internal/diff/diff.go
index b00ffbc..e7f8469 100644
--- a/internal/diff/diff.go
+++ b/internal/diff/diff.go
@@ -2,170 +2,130 @@
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
-// Package diff supports a pluggable diff algorithm.
+// Package diff computes differences between files or strings.
package diff
import (
"sort"
"strings"
-
- "golang.org/x/tools/internal/span"
)
-// TODO(adonovan): simplify this package to just:
-//
-// package diff
-// type Edit struct { Start, End int; New string }
-// func Strings(old, new string) []Edit
-// func Unified(oldLabel, newLabel string, old string, edits []Edit) string
-// func Apply(old string, edits []Edit) (string, error)
-//
-// and move everything else into gopls, including the concepts of filenames and spans.
-// Observe that TextEdit.URI is irrelevant to Unified.
+// TODO(adonovan): switch to []byte throughout.
+// But make clear that the operation is defined on runes, not bytes.
+// Also:
// - delete LineEdits? (used only by Unified and test)
// - delete Lines (unused except by its test)
-// TextEdit represents a change to a section of a document.
-// The text within the specified span should be replaced by the supplied new text.
-type TextEdit struct {
- Span span.Span
- NewText string
+// An Edit describes the replacement of a portion of a file.
+type Edit struct {
+ Start, End int // byte offsets of the region to replace
+ New string // the replacement
}
-// SortTextEdits attempts to order all edits by their starting points.
-// The sort is stable so that edits with the same starting point will not
-// be reordered.
-func SortTextEdits(d []TextEdit) {
- // Use a stable sort to maintain the order of edits inserted at the same position.
- sort.SliceStable(d, func(i int, j int) bool {
- return span.Compare(d[i].Span, d[j].Span) < 0
+// SortEdits orders edits by their start offset. The sort is stable
+// so that edits with the same start offset will not be reordered.
+func SortEdits(edits []Edit) {
+ sort.SliceStable(edits, func(i int, j int) bool {
+ return edits[i].Start < edits[j].Start
})
}
-// ApplyEdits applies the set of edits to the before and returns the resulting
-// content.
-// It may panic or produce garbage if the edits are not valid for the provided
-// before content.
-// TODO(adonovan): this function must not panic! Make it either cope
-// or report an error. We should not trust that (e.g.) patches supplied
-// as RPC inputs to gopls are consistent.
-func ApplyEdits(before string, edits []TextEdit) string {
- // Preconditions:
- // - all of the edits apply to before
- // - and all the spans for each TextEdit have the same URI
- if len(edits) == 0 {
- return before
- }
- edits, _ = prepareEdits(before, edits)
- after := strings.Builder{}
+// Apply applies a sequence of edits to the src buffer and
+// returns the result. It may panic or produce garbage if the edits
+// are overlapping, out of bounds of src, or out of order.
+//
+// TODO(adonovan): this function must not panic if the edits aren't
+// consistent with src, or with each other---especially when fed
+// information from an untrusted source. It should probably be
+// defensive against bad input and report an error in any of the above
+// situations.
+func Apply(src string, edits []Edit) string {
+ SortEdits(edits) // TODO(adonovan): move to caller? What's the contract? Don't mutate arguments.
+
+ var out strings.Builder
+ // TODO(adonovan): opt: preallocate correct final size
+ // by scanning the list of edits. (This can be done
+ // in the same pass as detecting inconsistent edits.)
last := 0
for _, edit := range edits {
- start := edit.Span.Start().Offset()
+ start := edit.Start
if start > last {
- after.WriteString(before[last:start])
+ out.WriteString(src[last:start])
last = start
}
- after.WriteString(edit.NewText)
- last = edit.Span.End().Offset()
+ out.WriteString(edit.New)
+ last = edit.End
}
- if last < len(before) {
- after.WriteString(before[last:])
+ if last < len(src) {
+ out.WriteString(src[last:])
}
- return after.String()
+ return out.String()
}
-// LineEdits takes a set of edits and expands and merges them as necessary
-// to ensure that there are only full line edits left when it is done.
-func LineEdits(before string, edits []TextEdit) []TextEdit {
- if len(edits) == 0 {
- return nil
- }
- edits, partial := prepareEdits(before, edits)
- if partial {
- edits = lineEdits(before, edits)
- }
- return edits
-}
+// LineEdits expands and merges a sequence of edits so that each
+// resulting edit replaces one or more complete lines.
+//
+// It may panic or produce garbage if the edits
+// are overlapping, out of bounds of src, or out of order.
+// TODO(adonovan): see consistency note at Apply.
+// We could hide this from the API so that we can enforce
+// the precondition... but it seems like a reasonable feature.
+func LineEdits(src string, edits []Edit) []Edit {
+ SortEdits(edits) // TODO(adonovan): is this necessary? Move burden to caller?
-// prepareEdits returns a sorted copy of the edits
-func prepareEdits(before string, edits []TextEdit) ([]TextEdit, bool) {
- partial := false
- tf := span.NewTokenFile("", []byte(before))
- copied := make([]TextEdit, len(edits))
- for i, edit := range edits {
- edit.Span, _ = edit.Span.WithAll(tf)
- copied[i] = edit
- partial = partial ||
- edit.Span.Start().Offset() >= len(before) ||
- edit.Span.Start().Column() > 1 || edit.Span.End().Column() > 1
- }
- SortTextEdits(copied)
- return copied, partial
-}
-
-// lineEdits rewrites the edits to always be full line edits
-func lineEdits(before string, edits []TextEdit) []TextEdit {
- adjusted := make([]TextEdit, 0, len(edits))
- current := TextEdit{Span: span.Invalid}
+ // Do all edits begin and end at the start of a line?
+ // TODO(adonovan): opt: is this fast path necessary?
+ // (Also, it complicates the result ownership.)
for _, edit := range edits {
- if current.Span.IsValid() && edit.Span.Start().Line() <= current.Span.End().Line() {
- // overlaps with the current edit, need to combine
- // first get the gap from the previous edit
- gap := before[current.Span.End().Offset():edit.Span.Start().Offset()]
- // now add the text of this edit
- current.NewText += gap + edit.NewText
- // and then adjust the end position
- current.Span = span.New(current.Span.URI(), current.Span.Start(), edit.Span.End())
- } else {
- // does not overlap, add previous run (if there is one)
- adjusted = addEdit(before, adjusted, current)
- // and then remember this edit as the start of the next run
- current = edit
+ 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
}
}
- // add the current pending run if there is one
- return addEdit(before, adjusted, current)
+ return edits // 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
+ }
+ }
+ return append(expanded, expandEdit(prev, src)) // flush final edit
}
-func addEdit(before string, edits []TextEdit, edit TextEdit) []TextEdit {
- if !edit.Span.IsValid() {
- return edits
+// 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
}
- // if edit is partial, expand it to full line now
- start := edit.Span.Start()
- end := edit.Span.End()
- if start.Column() > 1 {
- // prepend the text and adjust to start of line
- delta := start.Column() - 1
- start = span.NewPoint(start.Line(), 1, start.Offset()-delta)
- edit.Span = span.New(edit.Span.URI(), start, end)
- edit.NewText = before[start.Offset():start.Offset()+delta] + edit.NewText
- }
- if start.Offset() >= len(before) && start.Line() > 1 && before[len(before)-1] != '\n' {
- // after end of file that does not end in eol, so join to last line of file
- // to do this we need to know where the start of the last line was
- eol := strings.LastIndex(before, "\n")
- if eol < 0 {
- // file is one non terminated line
- eol = 0
- }
- delta := len(before) - eol
- start = span.NewPoint(start.Line()-1, 1, start.Offset()-delta)
- edit.Span = span.New(edit.Span.URI(), start, end)
- edit.NewText = before[start.Offset():start.Offset()+delta] + edit.NewText
- }
- if end.Column() > 1 {
- remains := before[end.Offset():]
- eol := strings.IndexRune(remains, '\n')
- if eol < 0 {
- eol = len(remains)
+
+ // Expand end right to end of line.
+ // (endCol is the zero-based column number of end.)
+ end := edit.End
+ if endCol := end - 1 - strings.LastIndex(src[:end], "\n"); endCol > 0 {
+ if nl := strings.IndexByte(src[end:], '\n'); nl < 0 {
+ edit.End = len(src) // extend to EOF
} else {
- eol++
+ edit.End = end + nl + 1 // extend beyond \n
}
- end = span.NewPoint(end.Line()+1, 1, end.Offset()+eol)
- edit.Span = span.New(edit.Span.URI(), start, end)
- edit.NewText = edit.NewText + remains[:eol]
+ edit.New += src[end:edit.End]
}
- edits = append(edits, edit)
- return edits
+
+ return edit
}
diff --git a/internal/diff/diff_test.go b/internal/diff/diff_test.go
index 11930de..8b8b648 100644
--- a/internal/diff/diff_test.go
+++ b/internal/diff/diff_test.go
@@ -5,25 +5,25 @@
package diff_test
import (
- "fmt"
"math/rand"
+ "reflect"
"strings"
"testing"
+ "unicode/utf8"
"golang.org/x/tools/internal/diff"
"golang.org/x/tools/internal/diff/difftest"
- "golang.org/x/tools/internal/span"
)
-func TestApplyEdits(t *testing.T) {
+func TestApply(t *testing.T) {
for _, tc := range difftest.TestCases {
t.Run(tc.Name, func(t *testing.T) {
- if got := diff.ApplyEdits(tc.In, tc.Edits); got != tc.Out {
- t.Errorf("ApplyEdits(Edits): got %q, want %q", got, tc.Out)
+ if got := diff.Apply(tc.In, tc.Edits); got != tc.Out {
+ t.Errorf("Apply(Edits): got %q, want %q", got, tc.Out)
}
if tc.LineEdits != nil {
- if got := diff.ApplyEdits(tc.In, tc.LineEdits); got != tc.Out {
- t.Errorf("ApplyEdits(LineEdits): got %q, want %q", got, tc.Out)
+ if got := diff.Apply(tc.In, tc.LineEdits); got != tc.Out {
+ t.Errorf("Apply(LineEdits): got %q, want %q", got, tc.Out)
}
}
})
@@ -31,10 +31,9 @@
}
func TestNEdits(t *testing.T) {
- for i, tc := range difftest.TestCases {
- sp := fmt.Sprintf("file://%s.%d", tc.Name, i)
- edits := diff.Strings(span.URI(sp), tc.In, tc.Out)
- got := diff.ApplyEdits(tc.In, edits)
+ for _, tc := range difftest.TestCases {
+ edits := diff.Strings(tc.In, tc.Out)
+ got := diff.Apply(tc.In, edits)
if got != tc.Out {
t.Fatalf("%s: got %q wanted %q", tc.Name, got, tc.Out)
}
@@ -47,21 +46,33 @@
func TestNRandom(t *testing.T) {
rand.Seed(1)
for i := 0; i < 1000; i++ {
- fname := fmt.Sprintf("file://%x", i)
a := randstr("abω", 16)
b := randstr("abωc", 16)
- edits := diff.Strings(span.URI(fname), a, b)
- got := diff.ApplyEdits(a, edits)
+ edits := diff.Strings(a, b)
+ got := diff.Apply(a, edits)
if got != b {
t.Fatalf("%d: got %q, wanted %q, starting with %q", i, got, b, a)
}
}
}
+// $ go test -fuzz=FuzzRoundTrip ./internal/diff
+func FuzzRoundTrip(f *testing.F) {
+ f.Fuzz(func(t *testing.T, a, b string) {
+ if !utf8.ValidString(a) || !utf8.ValidString(b) {
+ return // inputs must be text
+ }
+ edits := diff.Strings(a, b)
+ got := diff.Apply(a, edits)
+ if got != b {
+ t.Fatalf("applying diff(%q, %q) gives %q; edits=%v", a, b, got, edits)
+ }
+ })
+}
+
func TestNLinesRandom(t *testing.T) {
rand.Seed(2)
for i := 0; i < 1000; i++ {
- fname := fmt.Sprintf("file://%x", i)
x := randlines("abω", 4) // avg line length is 6, want a change every 3rd line or so
v := []rune(x)
for i := 0; i < len(v); i++ {
@@ -78,8 +89,8 @@
y = y[:len(y)-1]
}
a, b := strings.SplitAfter(x, "\n"), strings.SplitAfter(y, "\n")
- edits := diff.Lines(span.URI(fname), a, b)
- got := diff.ApplyEdits(x, edits)
+ edits := diff.Lines(a, b)
+ got := diff.Apply(x, edits)
if got != y {
t.Fatalf("%d: got\n%q, wanted\n%q, starting with %q", i, got, y, a)
}
@@ -122,8 +133,8 @@
a := "// Copyright 2019 The Go Authors. All rights reserved.\n// Use of this source code is governed by a BSD-style\n// license that can be found in the LICENSE file.\n\npackage diff_test\n\nimport (\n\t\"fmt\"\n\t\"math/rand\"\n\t\"strings\"\n\t\"testing\"\n\n\t\"golang.org/x/tools/gopls/internal/lsp/diff\"\n\t\"golang.org/x/tools/internal/diff/difftest\"\n\t\"golang.org/x/tools/internal/span\"\n)\n"
b := "// Copyright 2019 The Go Authors. All rights reserved.\n// Use of this source code is governed by a BSD-style\n// license that can be found in the LICENSE file.\n\npackage diff_test\n\nimport (\n\t\"fmt\"\n\t\"math/rand\"\n\t\"strings\"\n\t\"testing\"\n\n\t\"github.com/google/safehtml/template\"\n\t\"golang.org/x/tools/gopls/internal/lsp/diff\"\n\t\"golang.org/x/tools/internal/diff/difftest\"\n\t\"golang.org/x/tools/internal/span\"\n)\n"
- diffs := diff.Strings(span.URI("file://one"), a, b)
- got := diff.ApplyEdits(a, diffs)
+ diffs := diff.Strings(a, b)
+ got := diff.Apply(a, diffs)
if got != b {
i := 0
for ; i < len(a) && i < len(b) && got[i] == b[i]; i++ {
@@ -136,8 +147,8 @@
func TestRegressionOld002(t *testing.T) {
a := "n\"\n)\n"
b := "n\"\n\t\"golang.org/x//nnal/stack\"\n)\n"
- diffs := diff.Strings(span.URI("file://two"), a, b)
- got := diff.ApplyEdits(a, diffs)
+ diffs := diff.Strings(a, b)
+ got := diff.Apply(a, diffs)
if got != b {
i := 0
for ; i < len(a) && i < len(b) && got[i] == b[i]; i++ {
@@ -147,20 +158,8 @@
}
}
-func diffEdits(got, want []diff.TextEdit) bool {
- if len(got) != len(want) {
- return true
- }
- for i, w := range want {
- g := got[i]
- if span.Compare(w.Span, g.Span) != 0 {
- return true
- }
- if w.NewText != g.NewText {
- return true
- }
- }
- return false
+func diffEdits(got, want []diff.Edit) bool {
+ return !reflect.DeepEqual(got, want)
}
// return a random string of length n made of characters from s
diff --git a/internal/diff/difftest/difftest.go b/internal/diff/difftest/difftest.go
index c9808a5..998a90f 100644
--- a/internal/diff/difftest/difftest.go
+++ b/internal/diff/difftest/difftest.go
@@ -11,7 +11,6 @@
"testing"
"golang.org/x/tools/internal/diff"
- "golang.org/x/tools/internal/span"
)
const (
@@ -22,7 +21,7 @@
var TestCases = []struct {
Name, In, Out, Unified string
- Edits, LineEdits []diff.TextEdit
+ Edits, LineEdits []diff.Edit
NoDiff bool
}{{
Name: "empty",
@@ -41,8 +40,8 @@
-fruit
+cheese
`[1:],
- Edits: []diff.TextEdit{{Span: newSpan(0, 5), NewText: "cheese"}},
- LineEdits: []diff.TextEdit{{Span: newSpan(0, 6), NewText: "cheese\n"}},
+ Edits: []diff.Edit{{Start: 0, End: 5, New: "cheese"}},
+ LineEdits: []diff.Edit{{Start: 0, End: 6, New: "cheese\n"}},
}, {
Name: "insert_rune",
In: "gord\n",
@@ -52,8 +51,8 @@
-gord
+gourd
`[1:],
- Edits: []diff.TextEdit{{Span: newSpan(2, 2), NewText: "u"}},
- LineEdits: []diff.TextEdit{{Span: newSpan(0, 5), NewText: "gourd\n"}},
+ Edits: []diff.Edit{{Start: 2, End: 2, New: "u"}},
+ LineEdits: []diff.Edit{{Start: 0, End: 5, New: "gourd\n"}},
}, {
Name: "delete_rune",
In: "groat\n",
@@ -63,8 +62,8 @@
-groat
+goat
`[1:],
- Edits: []diff.TextEdit{{Span: newSpan(1, 2), NewText: ""}},
- LineEdits: []diff.TextEdit{{Span: newSpan(0, 6), NewText: "goat\n"}},
+ Edits: []diff.Edit{{Start: 1, End: 2, New: ""}},
+ LineEdits: []diff.Edit{{Start: 0, End: 6, New: "goat\n"}},
}, {
Name: "replace_rune",
In: "loud\n",
@@ -74,8 +73,8 @@
-loud
+lord
`[1:],
- Edits: []diff.TextEdit{{Span: newSpan(2, 3), NewText: "r"}},
- LineEdits: []diff.TextEdit{{Span: newSpan(0, 5), NewText: "lord\n"}},
+ Edits: []diff.Edit{{Start: 2, End: 3, New: "r"}},
+ LineEdits: []diff.Edit{{Start: 0, End: 5, New: "lord\n"}},
}, {
Name: "replace_partials",
In: "blanket\n",
@@ -85,11 +84,11 @@
-blanket
+bunker
`[1:],
- Edits: []diff.TextEdit{
- {Span: newSpan(1, 3), NewText: "u"},
- {Span: newSpan(6, 7), NewText: "r"},
+ Edits: []diff.Edit{
+ {Start: 1, End: 3, New: "u"},
+ {Start: 6, End: 7, New: "r"},
},
- LineEdits: []diff.TextEdit{{Span: newSpan(0, 8), NewText: "bunker\n"}},
+ LineEdits: []diff.Edit{{Start: 0, End: 8, New: "bunker\n"}},
}, {
Name: "insert_line",
In: "1: one\n3: three\n",
@@ -100,7 +99,7 @@
+2: two
3: three
`[1:],
- Edits: []diff.TextEdit{{Span: newSpan(7, 7), NewText: "2: two\n"}},
+ Edits: []diff.Edit{{Start: 7, End: 7, New: "2: two\n"}},
}, {
Name: "replace_no_newline",
In: "A",
@@ -112,7 +111,7 @@
+B
\ No newline at end of file
`[1:],
- Edits: []diff.TextEdit{{Span: newSpan(0, 1), NewText: "B"}},
+ Edits: []diff.Edit{{Start: 0, End: 1, New: "B"}},
}, {
Name: "append_empty",
In: "", // GNU diff -u special case: -0,0
@@ -123,8 +122,8 @@
+C
\ No newline at end of file
`[1:],
- Edits: []diff.TextEdit{{Span: newSpan(0, 0), NewText: "AB\nC"}},
- LineEdits: []diff.TextEdit{{Span: newSpan(0, 0), NewText: "AB\nC"}},
+ Edits: []diff.Edit{{Start: 0, End: 0, New: "AB\nC"}},
+ LineEdits: []diff.Edit{{Start: 0, End: 0, New: "AB\nC"}},
},
// TODO(adonovan): fix this test: GNU diff -u prints "+1,2", Unifies prints "+1,3".
// {
@@ -153,8 +152,20 @@
+AB
\ No newline at end of file
`[1:],
- Edits: []diff.TextEdit{{Span: newSpan(1, 1), NewText: "B"}},
- LineEdits: []diff.TextEdit{{Span: newSpan(0, 1), NewText: "AB"}},
+ Edits: []diff.Edit{{Start: 1, End: 1, New: "B"}},
+ LineEdits: []diff.Edit{{Start: 0, End: 1, New: "AB"}},
+ }, {
+ Name: "add_empty",
+ In: "",
+ Out: "AB\nC",
+ Unified: UnifiedPrefix + `
+@@ -0,0 +1,2 @@
++AB
++C
+\ No newline at end of file
+`[1:],
+ Edits: []diff.Edit{{Start: 0, End: 0, New: "AB\nC"}},
+ LineEdits: []diff.Edit{{Start: 0, End: 0, New: "AB\nC"}},
}, {
Name: "add_newline",
In: "A",
@@ -165,8 +176,8 @@
\ No newline at end of file
+A
`[1:],
- Edits: []diff.TextEdit{{Span: newSpan(1, 1), NewText: "\n"}},
- LineEdits: []diff.TextEdit{{Span: newSpan(0, 1), NewText: "A\n"}},
+ Edits: []diff.Edit{{Start: 1, End: 1, New: "\n"}},
+ LineEdits: []diff.Edit{{Start: 0, End: 1, New: "A\n"}},
}, {
Name: "delete_front",
In: "A\nB\nC\nA\nB\nB\nA\n",
@@ -183,15 +194,14 @@
A
+C
`[1:],
- Edits: []diff.TextEdit{
- {Span: newSpan(0, 4), NewText: ""},
- {Span: newSpan(6, 6), NewText: "B\n"},
- {Span: newSpan(10, 12), NewText: ""},
- {Span: newSpan(14, 14), NewText: "C\n"},
+ NoDiff: true, // unified diff is different but valid
+ Edits: []diff.Edit{
+ {Start: 0, End: 4, New: ""},
+ {Start: 6, End: 6, New: "B\n"},
+ {Start: 10, End: 12, New: ""},
+ {Start: 14, End: 14, New: "C\n"},
},
- NoDiff: true, // diff algorithm produces different delete/insert pattern
- },
- {
+ }, {
Name: "replace_last_line",
In: "A\nB\n",
Out: "A\nC\n\n",
@@ -202,8 +212,8 @@
+C
+
`[1:],
- Edits: []diff.TextEdit{{Span: newSpan(2, 3), NewText: "C\n"}},
- LineEdits: []diff.TextEdit{{Span: newSpan(2, 4), NewText: "C\n\n"}},
+ Edits: []diff.Edit{{Start: 2, End: 3, New: "C\n"}},
+ LineEdits: []diff.Edit{{Start: 2, End: 4, New: "C\n\n"}},
},
{
Name: "multiple_replace",
@@ -223,33 +233,19 @@
-G
+K
`[1:],
- Edits: []diff.TextEdit{
- {Span: newSpan(2, 8), NewText: "H\nI\nJ\n"},
- {Span: newSpan(12, 14), NewText: "K\n"},
+ Edits: []diff.Edit{
+ {Start: 2, End: 8, New: "H\nI\nJ\n"},
+ {Start: 12, End: 14, New: "K\n"},
},
NoDiff: true, // diff algorithm produces different delete/insert pattern
},
}
-func init() {
- // expand all the spans to full versions
- // we need them all to have their line number and column
- for _, tc := range TestCases {
- tf := span.NewTokenFile("", []byte(tc.In))
- for i := range tc.Edits {
- tc.Edits[i].Span, _ = tc.Edits[i].Span.WithAll(tf)
- }
- for i := range tc.LineEdits {
- tc.LineEdits[i].Span, _ = tc.LineEdits[i].Span.WithAll(tf)
- }
- }
-}
-
-func DiffTest(t *testing.T, compute func(uri span.URI, before, after string) []diff.TextEdit) {
+func DiffTest(t *testing.T, compute func(before, after string) []diff.Edit) {
for _, test := range TestCases {
t.Run(test.Name, func(t *testing.T) {
- edits := compute(span.URIFromPath("/"+test.Name), test.In, test.Out)
- got := diff.ApplyEdits(test.In, edits)
+ edits := compute(test.In, test.Out)
+ got := diff.Apply(test.In, edits)
unified := diff.Unified(FileA, FileB, test.In, edits)
if got != test.Out {
t.Errorf("Apply: got patched:\n%v\nfrom diff:\n%v\nexpected:\n%v", got, unified, test.Out)
@@ -260,7 +256,3 @@
})
}
}
-
-func newSpan(start, end int) span.Span {
- return span.New("", span.NewPoint(0, 0, start), span.NewPoint(0, 0, end))
-}
diff --git a/internal/diff/difftest/difftest_test.go b/internal/diff/difftest/difftest_test.go
index c761432..a990e52 100644
--- a/internal/diff/difftest/difftest_test.go
+++ b/internal/diff/difftest/difftest_test.go
@@ -34,7 +34,7 @@
diff = difftest.UnifiedPrefix + diff
}
if diff != test.Unified {
- t.Errorf("unified:\n%q\ndiff -u:\n%q", test.Unified, diff)
+ t.Errorf("unified:\n%s\ndiff -u:\n%s", test.Unified, diff)
}
})
}
diff --git a/internal/diff/myers/diff.go b/internal/diff/myers/diff.go
index 2188c0d..7c2d435 100644
--- a/internal/diff/myers/diff.go
+++ b/internal/diff/myers/diff.go
@@ -9,26 +9,36 @@
"strings"
"golang.org/x/tools/internal/diff"
- "golang.org/x/tools/internal/span"
)
// Sources:
// https://blog.jcoglan.com/2017/02/17/the-myers-diff-algorithm-part-3/
// https://www.codeproject.com/Articles/42279/%2FArticles%2F42279%2FInvestigating-Myers-diff-algorithm-Part-1-of-2
-func ComputeEdits(uri span.URI, before, after string) []diff.TextEdit {
- ops := operations(splitLines(before), splitLines(after))
- edits := make([]diff.TextEdit, 0, len(ops))
+func ComputeEdits(before, after string) []diff.Edit {
+ beforeLines := splitLines(before)
+ ops := operations(beforeLines, splitLines(after))
+
+ // Build a table mapping line number to offset.
+ lineOffsets := make([]int, 0, len(beforeLines)+1)
+ total := 0
+ for i := range beforeLines {
+ lineOffsets = append(lineOffsets, total)
+ total += len(beforeLines[i])
+ }
+ lineOffsets = append(lineOffsets, total) // EOF
+
+ edits := make([]diff.Edit, 0, len(ops))
for _, op := range ops {
- s := span.New(uri, span.NewPoint(op.I1+1, 1, 0), span.NewPoint(op.I2+1, 1, 0))
+ start, end := lineOffsets[op.I1], lineOffsets[op.I2]
switch op.Kind {
case diff.Delete:
- // Delete: unformatted[i1:i2] is deleted.
- edits = append(edits, diff.TextEdit{Span: s})
+ // Delete: before[I1:I2] is deleted.
+ edits = append(edits, diff.Edit{Start: start, End: end})
case diff.Insert:
- // Insert: formatted[j1:j2] is inserted at unformatted[i1:i1].
+ // Insert: after[J1:J2] is inserted at before[I1:I1].
if content := strings.Join(op.Content, ""); content != "" {
- edits = append(edits, diff.TextEdit{Span: s, NewText: content})
+ edits = append(edits, diff.Edit{Start: start, End: end, New: content})
}
}
}
diff --git a/internal/diff/ndiff.go b/internal/diff/ndiff.go
index e369f46..e76d2db 100644
--- a/internal/diff/ndiff.go
+++ b/internal/diff/ndiff.go
@@ -5,13 +5,10 @@
package diff
import (
- "go/token"
- "log"
"strings"
"unicode/utf8"
"golang.org/x/tools/internal/diff/lcs"
- "golang.org/x/tools/internal/span"
)
// maxDiffs is a limit on how deeply the lcs algorithm should search
@@ -23,59 +20,39 @@
// is why the arguments are strings, not []bytes.)
// TODO(adonovan): opt: consider switching everything to []bytes, if
// that's the more common type in practice. Or provide both flavors?
-func Strings(uri span.URI, before, after string) []TextEdit {
+func Strings(before, after string) []Edit {
if before == after {
// very frequently true
return nil
}
- // the diffs returned by the lcs package use indexes into whatever slice
- // was passed in. TextEdits need a span.Span which is computed with
- // byte offsets, so rune or line offsets need to be converted.
+ // The diffs returned by the lcs package use indexes into
+ // whatever slice was passed in. Edits use byte offsets, so
+ // rune or line offsets need to be converted.
// TODO(adonovan): opt: eliminate all the unnecessary allocations.
- if needrunes(before) || needrunes(after) {
- diffs, _ := lcs.Compute([]rune(before), []rune(after), maxDiffs/2)
+ var diffs []lcs.Diff
+ if !isASCII(before) || !isASCII(after) {
+ diffs, _ = lcs.Compute([]rune(before), []rune(after), maxDiffs/2)
diffs = runeOffsets(diffs, []rune(before))
- return convertDiffs(uri, diffs, []byte(before))
} else {
- diffs, _ := lcs.Compute([]byte(before), []byte(after), maxDiffs/2)
- return convertDiffs(uri, diffs, []byte(before))
+ // Common case: pure ASCII. Avoid expansion to []rune slice.
+ diffs, _ = lcs.Compute([]byte(before), []byte(after), maxDiffs/2)
}
+ return convertDiffs(diffs)
}
// Lines computes the differences between two list of lines.
// TODO(adonovan): unused except by its test. Do we actually need it?
-func Lines(uri span.URI, before, after []string) []TextEdit {
+func Lines(before, after []string) []Edit {
diffs, _ := lcs.Compute(before, after, maxDiffs/2)
diffs = lineOffsets(diffs, before)
- return convertDiffs(uri, diffs, []byte(strJoin(before)))
+ return convertDiffs(diffs)
// the code is not coping with possible missing \ns at the ends
}
-// convert diffs with byte offsets into diffs with line and column
-func convertDiffs(uri span.URI, diffs []lcs.Diff, src []byte) []TextEdit {
- ans := make([]TextEdit, len(diffs))
-
- // Reuse the machinery of go/token to convert (content, offset) to (line, column).
- tf := token.NewFileSet().AddFile("", -1, len(src))
- tf.SetLinesForContent(src)
-
- offsetToPoint := func(offset int) span.Point {
- // Re-use span.ToPosition's EOF workaround.
- // It is infallible if the diffs are consistent with src.
- line, col, err := span.ToPosition(tf, offset)
- if err != nil {
- log.Fatalf("invalid offset: %v", err)
- }
- return span.NewPoint(line, col, offset)
- }
-
+func convertDiffs(diffs []lcs.Diff) []Edit {
+ ans := make([]Edit, len(diffs))
for i, d := range diffs {
- start := offsetToPoint(d.Start)
- end := start
- if d.End != d.Start {
- end = offsetToPoint(d.End)
- }
- ans[i] = TextEdit{span.New(uri, start, end), d.Text}
+ ans[i] = Edit{d.Start, d.End, d.Text}
}
return ans
}
@@ -131,13 +108,12 @@
return b.String()
}
-// need runes is true if the string needs to be converted to []rune
-// for random access
-func needrunes(s string) bool {
+// isASCII reports whether s contains only ASCII.
+func isASCII(s string) bool {
for i := 0; i < len(s); i++ {
if s[i] >= utf8.RuneSelf {
- return true
+ return false
}
}
- return false
+ return true
}
diff --git a/internal/diff/unified.go b/internal/diff/unified.go
index 13ef677..f861832 100644
--- a/internal/diff/unified.go
+++ b/internal/diff/unified.go
@@ -9,10 +9,12 @@
"strings"
)
-// Unified applies the edits to oldContent and presents a unified diff.
-// The two labels are the names of the old and new files.
-func Unified(oldLabel, newLabel string, oldContent string, edits []TextEdit) string {
- return toUnified(oldLabel, newLabel, oldContent, edits).String()
+// TODO(adonovan): API: hide all but func Unified.
+
+// Unified applies the edits to content and presents a unified diff.
+// The old and new labels are the names of the content and result files.
+func Unified(oldLabel, newLabel string, content string, edits []Edit) string {
+ return toUnified(oldLabel, newLabel, content, edits).String()
}
// unified represents a set of edits as a unified diff.
@@ -82,7 +84,7 @@
// toUnified takes a file contents and a sequence of edits, and calculates
// a unified diff that represents those edits.
-func toUnified(fromName, toName string, content string, edits []TextEdit) unified {
+func toUnified(fromName, toName string, content string, edits []Edit) unified {
u := unified{
From: fromName,
To: toName,
@@ -90,17 +92,20 @@
if len(edits) == 0 {
return u
}
- edits, partial := prepareEdits(content, edits)
- if partial {
- edits = lineEdits(content, edits)
- }
+ edits = LineEdits(content, edits) // expand to whole lines
lines := splitLines(content)
var h *hunk
last := 0
toLine := 0
for _, edit := range edits {
- start := edit.Span.Start().Line() - 1
- end := edit.Span.End().Line() - 1
+ // Compute the zero-based line numbers of the edit start and end.
+ // TODO(adonovan): opt: compute incrementally, avoid O(n^2).
+ start := strings.Count(content[:edit.Start], "\n")
+ end := strings.Count(content[:edit.End], "\n")
+ if edit.End == len(content) && len(content) > 0 && content[len(content)-1] != '\n' {
+ end++ // EOF counts as an implicit newline
+ }
+
switch {
case h != nil && start == last:
//direct extension
@@ -129,8 +134,8 @@
h.Lines = append(h.Lines, line{Kind: Delete, Content: lines[i]})
last++
}
- if edit.NewText != "" {
- for _, content := range splitLines(edit.NewText) {
+ if edit.New != "" {
+ for _, content := range splitLines(edit.New) {
h.Lines = append(h.Lines, line{Kind: Insert, Content: content})
toLine++
}
