internal/lsp: implement diff for computing text edits
Rather than replacing the whole file on gofmt or goimports, use the Myers
diff algorithm to compute diffs for a file. We send those back as text
edits.
Change-Id: I4f8cce5b27d51eae1911049ea002558a84cdf1bf
Reviewed-on: https://go-review.googlesource.com/c/158579
Reviewed-by: Ian Cottrell <iancottrell@google.com>
diff --git a/cmd/gopls/forward/main.go b/cmd/gopls/forward/main.go
index 145bd46..c437679 100644
--- a/cmd/gopls/forward/main.go
+++ b/cmd/gopls/forward/main.go
@@ -24,7 +24,7 @@
func (*app) Name() string { return "forward" }
func (*app) Usage() string { return "[-port=<value>]" }
-func (*app) ShortHelp() string { return "An intermediary between an editor and GoLSP." }
+func (*app) ShortHelp() string { return "An intermediary between an editor and gopls." }
func (*app) DetailedHelp(*flag.FlagSet) {}
func (a *app) Run(ctx context.Context, args ...string) error {
diff --git a/internal/lsp/diff/diff.go b/internal/lsp/diff/diff.go
new file mode 100644
index 0000000..3c09483
--- /dev/null
+++ b/internal/lsp/diff/diff.go
@@ -0,0 +1,263 @@
+// Copyright 2019 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package diff implements the Myers diff algorithm.
+package diff
+
+import "strings"
+
+// Sources:
+// https://blog.jcoglan.com/2017/02/15/the-myers-diff-algorithm-part-3/
+// https://www.codeproject.com/Articles/42279/%2FArticles%2F42279%2FInvestigating-Myers-diff-algorithm-Part-1-of-2
+
+type Op struct {
+ Kind OpKind
+ Content string
+ I1, I2 int // indices of the line in a
+ J1, J2 int // indices of the line in b
+}
+
+type OpKind int
+
+const (
+ Delete OpKind = iota
+ Insert
+ Equal
+)
+
+func (k OpKind) String() string {
+ switch k {
+ case Delete:
+ return "delete"
+ case Insert:
+ return "insert"
+ case Equal:
+ return "equal"
+ default:
+ panic("unknown operation kind")
+ }
+}
+
+func ApplyEdits(a []string, operations []*Op) []string {
+ var b []string
+ var prevI2 int
+ for _, op := range operations {
+ // catch up to latest indices
+ if op.I1-prevI2 > 0 {
+ for _, c := range a[prevI2:op.I1] {
+ b = append(b, c)
+ }
+ }
+ switch op.Kind {
+ case Equal, Insert:
+ b = append(b, op.Content)
+ }
+ prevI2 = op.I2
+ }
+ // final catch up
+ if len(a)-prevI2 > 0 {
+ for _, c := range a[prevI2:len(a)] {
+ b = append(b, c)
+ }
+ }
+ return b
+}
+
+// Operations returns the list of operations to convert a into b, consolidating
+// operations for multiple lines and not including equal lines.
+func Operations(a, b []string) []*Op {
+ trace, offset := shortestEditSequence(a, b)
+ snakes := backtrack(trace, len(a), len(b), offset)
+
+ var i int
+ solution := make([]*Op, len(a)+len(b))
+
+ add := func(op *Op, i2, j2 int) {
+ if op == nil {
+ return
+ }
+ op.I2 = i2
+ op.J2 = j2
+ if op.Kind == Insert {
+ op.Content = strings.Join(b[op.J1:op.J2], "")
+ }
+ solution[i] = op
+ i++
+ }
+ x, y := 0, 0
+ for _, snake := range snakes {
+ if len(snake) < 2 {
+ continue
+ }
+ var op *Op
+ // delete (horizontal)
+ for snake[0]-snake[1] > x-y {
+ if op == nil {
+ op = &Op{
+ Kind: Delete,
+ I1: x,
+ J1: y,
+ }
+ }
+ x++
+ if x == len(a) {
+ break
+ }
+ }
+ add(op, x, y)
+ op = nil
+ // insert (vertical)
+ for snake[0]-snake[1] < x-y {
+ if op == nil {
+ op = &Op{
+ Kind: Insert,
+ I1: x,
+ J1: y,
+ }
+ }
+ y++
+ }
+ add(op, x, y)
+ op = nil
+ // equal (diagonal)
+ for x < snake[0] {
+ x++
+ y++
+ }
+ if x >= len(a) && y >= len(b) {
+ break
+ }
+ }
+ return solution[:i]
+}
+
+// Lines returns a list of per-line operations to convert a into b.
+func Lines(a, b []string) []*Op {
+ trace, offset := shortestEditSequence(a, b)
+ snakes := backtrack(trace, len(a), len(b), offset)
+
+ var i int
+ solution := make([]*Op, len(a)+len(b))
+
+ x, y := 0, 0
+ for _, snake := range snakes {
+ if len(snake) < 2 {
+ continue
+ }
+ // horizontal
+ for snake[0]-snake[1] > x-y {
+ solution[i] = &Op{
+ Kind: Delete,
+ Content: a[x],
+ }
+ i++
+ x++
+ if x == len(a) {
+ break
+ }
+ }
+ // vertical
+ for snake[0]-snake[1] < x-y {
+ solution[i] = &Op{
+ Kind: Insert,
+ Content: b[y],
+ }
+ i++
+ y++
+ }
+ // diagonal
+ for x < snake[0] {
+ solution[i] = &Op{
+ Kind: Equal,
+ Content: a[x],
+ }
+ i++
+ x++
+ y++
+ }
+ if x >= len(a) && y >= len(b) {
+ break
+ }
+ }
+ return solution[:i]
+}
+
+// backtrack uses the trace for the edit sequence computation and returns the
+// "snakes" that make up the solution. A "snake" is a single deletion or
+// insertion followed by zero or diagnonals.
+func backtrack(trace [][]int, x, y, offset int) [][]int {
+ snakes := make([][]int, len(trace))
+ d := len(trace) - 1
+ for ; x > 0 && y > 0 && d > 0; d-- {
+ V := trace[d]
+ if len(V) == 0 {
+ continue
+ }
+ snakes[d] = []int{x, y}
+
+ k := x - y
+
+ var kPrev int
+ if k == -d || (k != d && V[k-1+offset] < V[k+1+offset]) {
+ kPrev = k + 1
+ } else {
+ kPrev = k - 1
+ }
+
+ x = V[kPrev+offset]
+ y = x - kPrev
+ }
+ // this feels questionable
+ if x < 0 || y < 0 {
+ return snakes
+ }
+ snakes[d] = []int{x, y}
+ return snakes
+}
+
+// shortestEditSequence returns the shortest edit sequence that converts a into b.
+func shortestEditSequence(a, b []string) ([][]int, int) {
+ M, N := len(a), len(b)
+ V := make([]int, 2*(N+M)+1)
+ offset := N + M
+ trace := make([][]int, N+M+1)
+
+ // Iterate through the maximum possible length of the SES (N+M).
+ for d := 0; d <= N+M; d++ {
+ // k lines are represented by the equation y = x - k. We move in
+ // increments of 2 because end points for even d are on even k lines.
+ for k := -d; k <= d; k += 2 {
+ // At each point, we either go down or to the right. We go down if
+ // k == -d, and we go to the right if k == d. We also prioritize
+ // the maximum x value, because we prefer deletions to insertions.
+ var x int
+ if k == -d || (k != d && V[k-1+offset] < V[k+1+offset]) {
+ x = V[k+1+offset] // down
+ } else {
+ x = V[k-1+offset] + 1 // right
+ }
+
+ y := x - k
+
+ // Diagonal moves while we have equal contents.
+ for x < M && y < N && a[x] == b[y] {
+ x++
+ y++
+ }
+
+ V[k+offset] = x
+
+ // Save the state of the array.
+ copyV := make([]int, len(V))
+ copy(copyV, V)
+ trace[d] = copyV
+
+ // Return if we've exceeded the maximum values.
+ if x >= M-1 && y >= N-1 {
+ return trace, offset
+ }
+ }
+ }
+ return nil, 0
+}
diff --git a/internal/lsp/diff/diff_test.go b/internal/lsp/diff/diff_test.go
new file mode 100644
index 0000000..1c53328
--- /dev/null
+++ b/internal/lsp/diff/diff_test.go
@@ -0,0 +1,68 @@
+// Copyright 2019 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package diff
+
+import (
+ "reflect"
+ "testing"
+)
+
+func TestDiff(t *testing.T) {
+ for _, tt := range []struct {
+ a, b []string
+ lines []*Op
+ operations []*Op
+ }{
+ {
+ a: []string{"A", "B", "C", "A", "B", "B", "A"},
+ b: []string{"C", "B", "A", "B", "A", "C"},
+ lines: []*Op{
+ &Op{Kind: Delete, Content: "A"},
+ &Op{Kind: Delete, Content: "B"},
+ &Op{Kind: Equal, Content: "C"},
+ &Op{Kind: Insert, Content: "B"},
+ &Op{Kind: Equal, Content: "A"},
+ &Op{Kind: Equal, Content: "B"},
+ &Op{Kind: Delete, Content: "B"},
+ &Op{Kind: Equal, Content: "A"},
+ &Op{Kind: Insert, Content: "C"},
+ },
+ operations: []*Op{
+ &Op{Kind: Delete, I1: 0, I2: 1, J1: 0, J2: 0},
+ &Op{Kind: Delete, I1: 1, I2: 2, J1: 0, J2: 0},
+ &Op{Kind: Insert, Content: "B", I1: 3, I2: 3, J1: 1, J2: 2},
+ &Op{Kind: Delete, I1: 5, I2: 6, J1: 4, J2: 4},
+ &Op{Kind: Insert, Content: "C", I1: 7, I2: 7, J1: 5, J2: 6},
+ },
+ },
+ } {
+ for i, got := range Lines(tt.a, tt.b) {
+ want := tt.lines[i]
+ if !reflect.DeepEqual(want, got) {
+ t.Errorf("expected %v, got %v", want, got)
+ }
+ }
+ b := ApplyEdits(tt.a, tt.lines)
+ for i, want := range tt.b {
+ got := b[i]
+ if got != want {
+ t.Errorf("expected %v got %v", want, got)
+ }
+ }
+ for i, got := range Operations(tt.a, tt.b) {
+ want := tt.operations[i]
+ if !reflect.DeepEqual(want, got) {
+ t.Errorf("expected %v, got %v", want, got)
+ }
+ }
+ b = ApplyEdits(tt.a, tt.operations)
+ for i, want := range tt.b {
+ got := b[i]
+ if got != want {
+ t.Errorf("expected %v got %v", want, got)
+ }
+ }
+ }
+}
diff --git a/internal/lsp/imports.go b/internal/lsp/imports.go
index e3b9818..32f3e1c 100644
--- a/internal/lsp/imports.go
+++ b/internal/lsp/imports.go
@@ -28,7 +28,7 @@
if err != nil {
return nil, err
}
- edits, err := source.Imports(ctx, tok.Name(), content, r)
+ edits, err := source.Imports(ctx, tok, content, r)
if err != nil {
return nil, err
}
diff --git a/internal/lsp/lsp_test.go b/internal/lsp/lsp_test.go
index 28a2c22..4a7ecc5 100644
--- a/internal/lsp/lsp_test.go
+++ b/internal/lsp/lsp_test.go
@@ -17,6 +17,7 @@
"golang.org/x/tools/go/packages"
"golang.org/x/tools/go/packages/packagestest"
"golang.org/x/tools/internal/lsp/cache"
+ "golang.org/x/tools/internal/lsp/diff"
"golang.org/x/tools/internal/lsp/protocol"
"golang.org/x/tools/internal/lsp/source"
)
@@ -262,7 +263,7 @@
if err != nil {
t.Fatalf("completion failed for %s:%v:%v: %v", filepath.Base(src.Filename), src.Line, src.Column, err)
}
- if diff := diffCompletionItems(src, want, got); diff != "" {
+ if diff := diffCompletionItems(t, src, want, got); diff != "" {
t.Errorf(diff)
}
}
@@ -322,7 +323,7 @@
// diffCompletionItems prints the diff between expected and actual completion
// test results.
-func diffCompletionItems(pos token.Position, want, got []protocol.CompletionItem) string {
+func diffCompletionItems(t *testing.T, pos token.Position, want, got []protocol.CompletionItem) string {
if len(got) != len(want) {
goto Failed
}
@@ -359,15 +360,41 @@
URI: protocol.DocumentURI(source.ToURI(filename)),
},
})
- if err != nil || len(edits) == 0 {
+ if err != nil {
if gofmted != "" {
t.Error(err)
}
continue
}
- edit := edits[0]
- if edit.NewText != gofmted {
- t.Errorf("formatting failed: (got: %s), (expected: %s)", edit.NewText, gofmted)
+ f, err := s.view.GetFile(context.Background(), source.ToURI(filename))
+ if err != nil {
+ t.Error(err)
+ }
+ original, err := f.Read()
+ if err != nil {
+ t.Error(err)
+ }
+ var ops []*diff.Op
+ for _, edit := range edits {
+ if edit.NewText == "" { // deletion
+ ops = append(ops, &diff.Op{
+ Kind: diff.Delete,
+ I1: int(edit.Range.Start.Line),
+ I2: int(edit.Range.End.Line),
+ })
+ } else if edit.Range.Start == edit.Range.End { // insertion
+ ops = append(ops, &diff.Op{
+ Kind: diff.Insert,
+ Content: edit.NewText,
+ I1: int(edit.Range.Start.Line),
+ I2: int(edit.Range.End.Line),
+ })
+ }
+ }
+ split := strings.SplitAfter(string(original), "\n")
+ got := strings.Join(diff.ApplyEdits(split, ops), "")
+ if gofmted != got {
+ t.Errorf("format failed for %s: expected %v, got %v", filename, gofmted, got)
}
}
}
diff --git a/internal/lsp/position.go b/internal/lsp/position.go
index 2f9b4ae..454eb31 100644
--- a/internal/lsp/position.go
+++ b/internal/lsp/position.go
@@ -106,7 +106,7 @@
func lineStart(f *token.File, line int) token.Pos {
// Use binary search to find the start offset of this line.
//
- // TODO(adonovan): eventually replace this function with the
+ // TODO(rstambler): eventually replace this function with the
// simpler and more efficient (*go/token.File).LineStart, added
// in go1.12.
diff --git a/internal/lsp/source/definition.go b/internal/lsp/source/definition.go
index 8024d63..9d9ea17 100644
--- a/internal/lsp/source/definition.go
+++ b/internal/lsp/source/definition.go
@@ -180,7 +180,7 @@
func lineStart(f *token.File, line int) token.Pos {
// Use binary search to find the start offset of this line.
//
- // TODO(adonovan): eventually replace this function with the
+ // TODO(rstambler): eventually replace this function with the
// simpler and more efficient (*go/token.File).LineStart, added
// in go1.12.
diff --git a/internal/lsp/source/format.go b/internal/lsp/source/format.go
index 0ac932a..5d1177a 100644
--- a/internal/lsp/source/format.go
+++ b/internal/lsp/source/format.go
@@ -11,9 +11,12 @@
"fmt"
"go/ast"
"go/format"
+ "go/token"
+ "strings"
"golang.org/x/tools/go/ast/astutil"
"golang.org/x/tools/imports"
+ "golang.org/x/tools/internal/lsp/diff"
)
// Format formats a file with a given range.
@@ -55,24 +58,49 @@
if err := format.Node(buf, fset, node); err != nil {
return nil, err
}
- return computeTextEdits(rng, buf.String()), nil
-}
-
-// Imports formats a file using the goimports tool.
-func Imports(ctx context.Context, filename string, content []byte, rng Range) ([]TextEdit, error) {
- content, err := imports.Process(filename, content, nil)
+ content, err := f.Read()
if err != nil {
return nil, err
}
- return computeTextEdits(rng, string(content)), nil
+ tok, err := f.GetToken()
+ if err != nil {
+ return nil, err
+ }
+ return computeTextEdits(rng, tok, string(content), buf.String()), nil
}
-// TODO(rstambler): Compute text edits instead of replacing whole file.
-func computeTextEdits(rng Range, content string) []TextEdit {
- return []TextEdit{
- {
- Range: rng,
- NewText: content,
- },
+// Imports formats a file using the goimports tool.
+func Imports(ctx context.Context, tok *token.File, content []byte, rng Range) ([]TextEdit, error) {
+ formatted, err := imports.Process(tok.Name(), content, nil)
+ if err != nil {
+ return nil, err
}
+ return computeTextEdits(rng, tok, string(content), string(formatted)), nil
+}
+
+func computeTextEdits(rng Range, tok *token.File, unformatted, formatted string) (edits []TextEdit) {
+ u := strings.SplitAfter(unformatted, "\n")
+ f := strings.SplitAfter(formatted, "\n")
+ for _, op := range diff.Operations(u, f) {
+ switch op.Kind {
+ case diff.Delete:
+ // Delete: unformatted[i1:i2] is deleted.
+ edits = append(edits, TextEdit{
+ Range: Range{
+ Start: lineStart(tok, op.I1+1),
+ End: lineStart(tok, op.I2+1),
+ },
+ })
+ case diff.Insert:
+ // Insert: formatted[j1:j2] is inserted at unformatted[i1:i1].
+ edits = append(edits, TextEdit{
+ Range: Range{
+ Start: lineStart(tok, op.I1+1),
+ End: lineStart(tok, op.I1+1),
+ },
+ NewText: op.Content,
+ })
+ }
+ }
+ return edits
}
diff --git a/internal/lsp/testdata/format/bad_format.go b/internal/lsp/testdata/format/bad_format.go.in
similarity index 99%
rename from internal/lsp/testdata/format/bad_format.go
rename to internal/lsp/testdata/format/bad_format.go.in
index 77f0861..94187d2 100644
--- a/internal/lsp/testdata/format/bad_format.go
+++ b/internal/lsp/testdata/format/bad_format.go.in
@@ -1,19 +1,20 @@
package format //@format("package")
import (
- "fmt"
"runtime"
-
+ "fmt"
"log"
)
func hello() {
+
+
+
var x int //@diag("x", "x declared but not used")
}
func hi() {
-
runtime.GOROOT()
fmt.Printf("")
