internal/diff: abolish errors
Computing the difference between two strings is logically an
infallible operation. This change makes the code reflect that. The
actual failures were unreachable given consistent inputs, but that was
hard to see from the complexity of the logic surrounding span.Span.
(The problem only occurs when converting offsets beyond the end of the
file to Spans, but the code preserves the integrity of offsets.)
gopls' "old" hooks.ComputeEdits impl (based on sergi/go-diff) now
reports a bug and returns a single diff for the entire file if it
panics.
Also, first steps towards simpler API and a
reusable diff package in x/tools:
- add TODO for new API. In particular, the diff package shouldn't care
about filenames, spans, and URIs. These are gopls concerns.
- diff.String is the main diff function.
- diff.Unified prints edits in unified form;
all its internals are now hidden.
- the ComputeEdits func type is moved to gopls (source.DiffFunction)
- remove all non-critical uses of myers.ComputeEdits. The only
remaining one is in gopls' defaults, but perhaps that gets
overridden by the default GoDiff setting in hooks, to BothDiffs
(sergi + pjw impls), so maybe it's now actually unused in practice?
Change-Id: I6ceb5c670897abbf285b243530a7372dfa41edf6
Reviewed-on: https://go-review.googlesource.com/c/tools/+/436778
Run-TryBot: Alan Donovan <adonovan@google.com>
Reviewed-by: Robert Findley <rfindley@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
gopls-CI: kokoro <noreply+kokoro@google.com>
diff --git a/internal/diff/ndiff.go b/internal/diff/ndiff.go
index e537b72..e369f46 100644
--- a/internal/diff/ndiff.go
+++ b/internal/diff/ndiff.go
@@ -5,6 +5,8 @@
package diff
import (
+ "go/token"
+ "log"
"strings"
"unicode/utf8"
@@ -16,51 +18,66 @@
// the value is just a guess
const maxDiffs = 30
-// NComputeEdits computes TextEdits for strings
-// (both it and the diff in the myers package have type ComputeEdits, which
+// Strings computes the differences between two strings.
+// (Both it and the diff in the myers package have type ComputeEdits, which
// is why the arguments are strings, not []bytes.)
-func NComputeEdits(uri span.URI, before, after string) ([]TextEdit, error) {
+// 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 {
if before == after {
// very frequently true
- return nil, nil
+ 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
+ // was passed in. TextEdits need a span.Span which is computed with
// 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)
diffs = runeOffsets(diffs, []rune(before))
- ans, err := convertDiffs(uri, diffs, []byte(before))
- return ans, err
+ return convertDiffs(uri, diffs, []byte(before))
} else {
diffs, _ := lcs.Compute([]byte(before), []byte(after), maxDiffs/2)
- ans, err := convertDiffs(uri, diffs, []byte(before))
- return ans, err
+ return convertDiffs(uri, diffs, []byte(before))
}
}
-// NComputeLineEdits computes TextEdits for []strings
-func NComputeLineEdits(uri span.URI, before, after []string) ([]TextEdit, error) {
+// 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 {
diffs, _ := lcs.Compute(before, after, maxDiffs/2)
diffs = lineOffsets(diffs, before)
- ans, err := convertDiffs(uri, diffs, []byte(strJoin(before)))
+ return convertDiffs(uri, diffs, []byte(strJoin(before)))
// the code is not coping with possible missing \ns at the ends
- return ans, err
}
// convert diffs with byte offsets into diffs with line and column
-func convertDiffs(uri span.URI, diffs []lcs.Diff, src []byte) ([]TextEdit, error) {
+func convertDiffs(uri span.URI, diffs []lcs.Diff, src []byte) []TextEdit {
ans := make([]TextEdit, len(diffs))
- tf := span.NewTokenFile(uri.Filename(), src)
- for i, d := range diffs {
- s := newSpan(uri, d.Start, d.End)
- s, err := s.WithPosition(tf)
+
+ // 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 {
- return nil, err
+ log.Fatalf("invalid offset: %v", err)
}
- ans[i] = TextEdit{s, d.Text}
+ return span.NewPoint(line, col, offset)
}
- return ans, nil
+
+ 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}
+ }
+ return ans
}
// convert diffs with rune offsets into diffs with byte offsets
@@ -114,10 +131,6 @@
return b.String()
}
-func newSpan(uri span.URI, left, right int) span.Span {
- return span.New(uri, span.NewPoint(0, 0, left), span.NewPoint(0, 0, right))
-}
-
// need runes is true if the string needs to be converted to []rune
// for random access
func needrunes(s string) bool {
