internal/lsp: invert the diff dependencies so myers depends on diff
This makes it so the diff package is depended on by all implementations, rather
than the diff package having to depend on the default myers implementation.
Change-Id: I04b9caee6ff1017fa8e5476a7434e4b0e17753c3
Reviewed-on: https://go-review.googlesource.com/c/tools/+/198379
Reviewed-by: Rebecca Stambler <rstambler@golang.org>
diff --git a/internal/lsp/diff/hooks.go b/internal/lsp/diff/diff.go
similarity index 67%
rename from internal/lsp/diff/hooks.go
rename to internal/lsp/diff/diff.go
index 033789b..2c4a0fa 100644
--- a/internal/lsp/diff/hooks.go
+++ b/internal/lsp/diff/diff.go
@@ -24,6 +24,30 @@
ToUnified func(from, to string, before string, edits []TextEdit) string
)
+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")
+ }
+}
+
+// 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 {
diff --git a/internal/lsp/diff/diff_test.go b/internal/lsp/diff/diff_test.go
deleted file mode 100644
index 1b532f5..0000000
--- a/internal/lsp/diff/diff_test.go
+++ /dev/null
@@ -1,16 +0,0 @@
-// 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_test
-
-import (
- "testing"
-
- "golang.org/x/tools/internal/lsp/diff"
- "golang.org/x/tools/internal/lsp/diff/difftest"
-)
-
-func TestDiff(t *testing.T) {
- difftest.DiffTest(t, diff.MyersComputeEdits)
-}
diff --git a/internal/lsp/diff/myers.go b/internal/lsp/diff/myers.go
deleted file mode 100644
index d0d9ef3..0000000
--- a/internal/lsp/diff/myers.go
+++ /dev/null
@@ -1,73 +0,0 @@
-// 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 (
- "fmt"
- "strings"
-
- "golang.org/x/tools/internal/lsp/diff/myers"
- "golang.org/x/tools/internal/span"
-)
-
-func init() {
- ToUnified = myersToUnified
-}
-
-func MyersComputeEdits(uri span.URI, before, after string) []TextEdit {
- u := myers.SplitLines(before)
- f := myers.SplitLines(after)
- return myersDiffToEdits(uri, myers.Operations(u, f))
-}
-
-func myersToUnified(from, to string, before string, edits []TextEdit) string {
- u := myers.SplitLines(before)
- ops := myersEditsToDiff(edits)
- return fmt.Sprint(myers.ToUnified(from, to, u, ops))
-}
-
-func myersDiffToEdits(uri span.URI, ops []*myers.Op) []TextEdit {
- edits := make([]TextEdit, 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))
- switch op.Kind {
- case myers.Delete:
- // Delete: unformatted[i1:i2] is deleted.
- edits = append(edits, TextEdit{Span: s})
- case myers.Insert:
- // Insert: formatted[j1:j2] is inserted at unformatted[i1:i1].
- if content := strings.Join(op.Content, ""); content != "" {
- edits = append(edits, TextEdit{Span: s, NewText: content})
- }
- }
- }
- return edits
-}
-
-func myersEditsToDiff(edits []TextEdit) []*myers.Op {
- iToJ := 0
- ops := make([]*myers.Op, len(edits))
- for i, edit := range edits {
- i1 := edit.Span.Start().Line() - 1
- i2 := edit.Span.End().Line() - 1
- kind := myers.Insert
- if edit.NewText == "" {
- kind = myers.Delete
- }
- ops[i] = &myers.Op{
- Kind: kind,
- Content: myers.SplitLines(edit.NewText),
- I1: i1,
- I2: i2,
- J1: i1 + iToJ,
- }
- if kind == myers.Insert {
- iToJ += len(ops[i].Content)
- } else {
- iToJ -= i2 - i1
- }
- }
- return ops
-}
diff --git a/internal/lsp/diff/myers/diff.go b/internal/lsp/diff/myers/diff.go
index 4bbe3dd..e6e6e21 100644
--- a/internal/lsp/diff/myers/diff.go
+++ b/internal/lsp/diff/myers/diff.go
@@ -5,40 +5,23 @@
// Package myers implements the Myers diff algorithm.
package myers
-import "strings"
+import (
+ "strings"
+
+ "golang.org/x/tools/internal/lsp/diff"
+)
// 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
type Op struct {
- Kind OpKind
+ Kind diff.OpKind
Content []string // content from b
I1, I2 int // indices of the line in a
J1 int // indices of the line in b, J2 implied by len(Content)
}
-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
@@ -50,7 +33,7 @@
}
}
switch op.Kind {
- case Equal, Insert:
+ case diff.Equal, diff.Insert:
b = append(b, op.Content...)
}
prevI2 = op.I2
@@ -84,7 +67,7 @@
return
}
op.I2 = i2
- if op.Kind == Insert {
+ if op.Kind == diff.Insert {
op.Content = b[op.J1:j2]
}
solution[i] = op
@@ -100,7 +83,7 @@
for snake[0]-snake[1] > x-y {
if op == nil {
op = &Op{
- Kind: Delete,
+ Kind: diff.Delete,
I1: x,
J1: y,
}
@@ -116,7 +99,7 @@
for snake[0]-snake[1] < x-y {
if op == nil {
op = &Op{
- Kind: Insert,
+ Kind: diff.Insert,
I1: x,
J1: y,
}
diff --git a/internal/lsp/diff/myers/diff_test.go b/internal/lsp/diff/myers/diff_test.go
index f60f73b..9e6d7e7 100644
--- a/internal/lsp/diff/myers/diff_test.go
+++ b/internal/lsp/diff/myers/diff_test.go
@@ -14,6 +14,8 @@
"strings"
"testing"
+ "golang.org/x/tools/internal/lsp/diff"
+ "golang.org/x/tools/internal/lsp/diff/difftest"
"golang.org/x/tools/internal/lsp/diff/myers"
)
@@ -26,6 +28,10 @@
var verifyDiff = flag.Bool("verify-diff", false, "Check that the unified diff output matches `diff -u`")
func TestDiff(t *testing.T) {
+ difftest.DiffTest(t, myers.ComputeEdits)
+}
+
+func TestMyersDiff(t *testing.T) {
for _, test := range []struct {
a, b string
lines []*myers.Op
@@ -42,8 +48,8 @@
a: "A\n",
b: "B\n",
operations: []*myers.Op{
- &myers.Op{Kind: myers.Delete, I1: 0, I2: 1, J1: 0},
- &myers.Op{Kind: myers.Insert, Content: []string{"B\n"}, I1: 1, I2: 1, J1: 0},
+ &myers.Op{Kind: diff.Delete, I1: 0, I2: 1, J1: 0},
+ &myers.Op{Kind: diff.Insert, Content: []string{"B\n"}, I1: 1, I2: 1, J1: 0},
},
unified: `
@@ -1 +1 @@
@@ -53,8 +59,8 @@
a: "A",
b: "B",
operations: []*myers.Op{
- &myers.Op{Kind: myers.Delete, I1: 0, I2: 1, J1: 0},
- &myers.Op{Kind: myers.Insert, Content: []string{"B"}, I1: 1, I2: 1, J1: 0},
+ &myers.Op{Kind: diff.Delete, I1: 0, I2: 1, J1: 0},
+ &myers.Op{Kind: diff.Insert, Content: []string{"B"}, I1: 1, I2: 1, J1: 0},
},
unified: `
@@ -1 +1 @@
@@ -66,11 +72,11 @@
a: "A\nB\nC\nA\nB\nB\nA\n",
b: "C\nB\nA\nB\nA\nC\n",
operations: []*myers.Op{
- &myers.Op{Kind: myers.Delete, I1: 0, I2: 1, J1: 0},
- &myers.Op{Kind: myers.Delete, I1: 1, I2: 2, J1: 0},
- &myers.Op{Kind: myers.Insert, Content: []string{"B\n"}, I1: 3, I2: 3, J1: 1},
- &myers.Op{Kind: myers.Delete, I1: 5, I2: 6, J1: 4},
- &myers.Op{Kind: myers.Insert, Content: []string{"C\n"}, I1: 7, I2: 7, J1: 5},
+ &myers.Op{Kind: diff.Delete, I1: 0, I2: 1, J1: 0},
+ &myers.Op{Kind: diff.Delete, I1: 1, I2: 2, J1: 0},
+ &myers.Op{Kind: diff.Insert, Content: []string{"B\n"}, I1: 3, I2: 3, J1: 1},
+ &myers.Op{Kind: diff.Delete, I1: 5, I2: 6, J1: 4},
+ &myers.Op{Kind: diff.Insert, Content: []string{"C\n"}, I1: 7, I2: 7, J1: 5},
},
unified: `
@@ -1,7 +1,6 @@
@@ -90,9 +96,9 @@
a: "A\nB\n",
b: "A\nC\n\n",
operations: []*myers.Op{
- &myers.Op{Kind: myers.Delete, I1: 1, I2: 2, J1: 1},
- &myers.Op{Kind: myers.Insert, Content: []string{"C\n"}, I1: 2, I2: 2, J1: 1},
- &myers.Op{Kind: myers.Insert, Content: []string{"\n"}, I1: 2, I2: 2, J1: 2},
+ &myers.Op{Kind: diff.Delete, I1: 1, I2: 2, J1: 1},
+ &myers.Op{Kind: diff.Insert, Content: []string{"C\n"}, I1: 2, I2: 2, J1: 1},
+ &myers.Op{Kind: diff.Insert, Content: []string{"\n"}, I1: 2, I2: 2, J1: 2},
},
unified: `
@@ -1,2 +1,3 @@
diff --git a/internal/lsp/diff/myers/myers.go b/internal/lsp/diff/myers/myers.go
new file mode 100644
index 0000000..4b7da07
--- /dev/null
+++ b/internal/lsp/diff/myers/myers.go
@@ -0,0 +1,73 @@
+// 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 myers
+
+import (
+ "fmt"
+ "strings"
+
+ "golang.org/x/tools/internal/lsp/diff"
+ "golang.org/x/tools/internal/span"
+)
+
+func init() {
+ diff.ToUnified = myersToUnified
+}
+
+func ComputeEdits(uri span.URI, before, after string) []diff.TextEdit {
+ u := SplitLines(before)
+ f := SplitLines(after)
+ return myersDiffToEdits(uri, Operations(u, f))
+}
+
+func myersToUnified(from, to string, before string, edits []diff.TextEdit) string {
+ u := SplitLines(before)
+ ops := myersEditsToDiff(edits)
+ return fmt.Sprint(ToUnified(from, to, u, ops))
+}
+
+func myersDiffToEdits(uri span.URI, ops []*Op) []diff.TextEdit {
+ edits := make([]diff.TextEdit, 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))
+ switch op.Kind {
+ case diff.Delete:
+ // Delete: unformatted[i1:i2] is deleted.
+ edits = append(edits, diff.TextEdit{Span: s})
+ case diff.Insert:
+ // Insert: formatted[j1:j2] is inserted at unformatted[i1:i1].
+ if content := strings.Join(op.Content, ""); content != "" {
+ edits = append(edits, diff.TextEdit{Span: s, NewText: content})
+ }
+ }
+ }
+ return edits
+}
+
+func myersEditsToDiff(edits []diff.TextEdit) []*Op {
+ iToJ := 0
+ ops := make([]*Op, len(edits))
+ for i, edit := range edits {
+ i1 := edit.Span.Start().Line() - 1
+ i2 := edit.Span.End().Line() - 1
+ kind := diff.Insert
+ if edit.NewText == "" {
+ kind = diff.Delete
+ }
+ ops[i] = &Op{
+ Kind: kind,
+ Content: SplitLines(edit.NewText),
+ I1: i1,
+ I2: i2,
+ J1: i1 + iToJ,
+ }
+ if kind == diff.Insert {
+ iToJ += len(ops[i].Content)
+ } else {
+ iToJ -= i2 - i1
+ }
+ }
+ return ops
+}
diff --git a/internal/lsp/diff/myers/unified.go b/internal/lsp/diff/myers/unified.go
index 9d73dff..dae023f 100644
--- a/internal/lsp/diff/myers/unified.go
+++ b/internal/lsp/diff/myers/unified.go
@@ -7,6 +7,8 @@
import (
"fmt"
"strings"
+
+ "golang.org/x/tools/internal/lsp/diff"
)
type Unified struct {
@@ -21,7 +23,7 @@
}
type Line struct {
- Kind OpKind
+ Kind diff.OpKind
Content string
}
@@ -67,14 +69,14 @@
}
last = op.I1
switch op.Kind {
- case Delete:
+ case diff.Delete:
for i := op.I1; i < op.I2; i++ {
- h.Lines = append(h.Lines, Line{Kind: Delete, Content: lines[i]})
+ h.Lines = append(h.Lines, Line{Kind: diff.Delete, Content: lines[i]})
last++
}
- case Insert:
+ case diff.Insert:
for _, c := range op.Content {
- h.Lines = append(h.Lines, Line{Kind: Insert, Content: c})
+ h.Lines = append(h.Lines, Line{Kind: diff.Insert, Content: c})
}
default:
// all other op types ignored
@@ -97,7 +99,7 @@
if i >= len(lines) {
return delta
}
- h.Lines = append(h.Lines, Line{Kind: Equal, Content: lines[i]})
+ h.Lines = append(h.Lines, Line{Kind: diff.Equal, Content: lines[i]})
delta++
}
return delta
@@ -113,9 +115,9 @@
fromCount, toCount := 0, 0
for _, l := range hunk.Lines {
switch l.Kind {
- case Delete:
+ case diff.Delete:
fromCount++
- case Insert:
+ case diff.Insert:
toCount++
default:
fromCount++
@@ -136,9 +138,9 @@
fmt.Fprint(f, " @@\n")
for _, l := range hunk.Lines {
switch l.Kind {
- case Delete:
+ case diff.Delete:
fmt.Fprintf(f, "-%s", l.Content)
- case Insert:
+ case diff.Insert:
fmt.Fprintf(f, "+%s", l.Content)
default:
fmt.Fprintf(f, " %s", l.Content)
diff --git a/internal/lsp/source/options.go b/internal/lsp/source/options.go
index 7e3df1d..c89967d 100644
--- a/internal/lsp/source/options.go
+++ b/internal/lsp/source/options.go
@@ -10,6 +10,7 @@
"time"
"golang.org/x/tools/internal/lsp/diff"
+ "golang.org/x/tools/internal/lsp/diff/myers"
"golang.org/x/tools/internal/lsp/protocol"
"golang.org/x/tools/internal/telemetry/tag"
errors "golang.org/x/xerrors"
@@ -41,7 +42,7 @@
FuzzyMatching: true,
Budget: 100 * time.Millisecond,
},
- ComputeEdits: diff.MyersComputeEdits,
+ ComputeEdits: myers.ComputeEdits,
}
)
