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/go/analysis/analysistest/analysistest.go b/go/analysis/analysistest/analysistest.go
index e65a695..bc25b9f 100644
--- a/go/analysis/analysistest/analysistest.go
+++ b/go/analysis/analysistest/analysistest.go
@@ -25,7 +25,6 @@
"golang.org/x/tools/go/analysis/internal/checker"
"golang.org/x/tools/go/packages"
"golang.org/x/tools/internal/diff"
- "golang.org/x/tools/internal/span"
"golang.org/x/tools/internal/testenv"
"golang.org/x/tools/txtar"
)
@@ -113,7 +112,7 @@
// should match up.
for _, act := range r {
// file -> message -> edits
- fileEdits := make(map[*token.File]map[string][]diff.TextEdit)
+ fileEdits := make(map[*token.File]map[string][]diff.Edit)
fileContents := make(map[*token.File][]byte)
// Validate edits, prepare the fileEdits map and read the file contents.
@@ -141,17 +140,13 @@
}
fileContents[file] = contents
}
- spn, err := span.NewRange(file, edit.Pos, edit.End).Span()
- if err != nil {
- t.Errorf("error converting edit to span %s: %v", file.Name(), err)
- }
-
if _, ok := fileEdits[file]; !ok {
- fileEdits[file] = make(map[string][]diff.TextEdit)
+ fileEdits[file] = make(map[string][]diff.Edit)
}
- fileEdits[file][sf.Message] = append(fileEdits[file][sf.Message], diff.TextEdit{
- Span: spn,
- NewText: string(edit.NewText),
+ fileEdits[file][sf.Message] = append(fileEdits[file][sf.Message], diff.Edit{
+ Start: file.Offset(edit.Pos),
+ End: file.Offset(edit.End),
+ New: string(edit.NewText),
})
}
}
@@ -188,7 +183,7 @@
for _, vf := range ar.Files {
if vf.Name == sf {
found = true
- out := diff.ApplyEdits(string(orig), edits)
+ out := diff.Apply(string(orig), edits)
// the file may contain multiple trailing
// newlines if the user places empty lines
// between files in the archive. normalize
@@ -200,7 +195,7 @@
continue
}
if want != string(formatted) {
- edits := diff.Strings("", want, string(formatted))
+ edits := diff.Strings(want, string(formatted))
t.Errorf("suggested fixes failed for %s:\n%s", file.Name(), diff.Unified(fmt.Sprintf("%s.golden [%s]", file.Name(), sf), "actual", want, edits))
}
break
@@ -213,12 +208,12 @@
} else {
// all suggested fixes are represented by a single file
- var catchallEdits []diff.TextEdit
+ var catchallEdits []diff.Edit
for _, edits := range fixes {
catchallEdits = append(catchallEdits, edits...)
}
- out := diff.ApplyEdits(string(orig), catchallEdits)
+ out := diff.Apply(string(orig), catchallEdits)
want := string(ar.Comment)
formatted, err := format.Source([]byte(out))
@@ -227,7 +222,7 @@
continue
}
if want != string(formatted) {
- edits := diff.Strings("", want, string(formatted))
+ edits := diff.Strings(want, string(formatted))
t.Errorf("suggested fixes failed for %s:\n%s", file.Name(), diff.Unified(file.Name()+".golden", "actual", want, edits))
}
}
diff --git a/gopls/api-diff/api_diff.go b/gopls/api-diff/api_diff.go
index 8aa333e..0fabae1 100644
--- a/gopls/api-diff/api_diff.go
+++ b/gopls/api-diff/api_diff.go
@@ -262,6 +262,6 @@
}
before += "\n"
after += "\n"
- edits := diffpkg.Strings("irrelevant", before, after)
+ edits := diffpkg.Strings(before, after)
return fmt.Sprintf("%q", diffpkg.Unified("previous", "current", before, edits))
}
diff --git a/gopls/internal/hooks/diff.go b/gopls/internal/hooks/diff.go
index 25b1d95..3aa1f0b 100644
--- a/gopls/internal/hooks/diff.go
+++ b/gopls/internal/hooks/diff.go
@@ -8,7 +8,6 @@
"crypto/rand"
"encoding/json"
"fmt"
- "go/token"
"io"
"log"
"math/big"
@@ -23,7 +22,6 @@
"github.com/sergi/go-diff/diffmatchpatch"
"golang.org/x/tools/internal/bug"
"golang.org/x/tools/internal/diff"
- "golang.org/x/tools/internal/span"
)
// structure for saving information about diffs
@@ -144,14 +142,14 @@
// BothDiffs edits calls both the new and old diffs, checks that the new diffs
// change before into after, and attempts to preserve some statistics.
-func BothDiffs(uri span.URI, before, after string) (edits []diff.TextEdit) {
+func BothDiffs(before, after string) (edits []diff.Edit) {
// The new diff code contains a lot of internal checks that panic when they
// fail. This code catches the panics, or other failures, tries to save
// the failing example (and ut wiykd ask the user to send it back to us, and
// changes options.newDiff to 'old', if only we could figure out how.)
stat := diffstat{Before: len(before), After: len(after)}
now := time.Now()
- oldedits := ComputeEdits(uri, before, after)
+ oldedits := ComputeEdits(before, after)
stat.Oldedits = len(oldedits)
stat.Oldtime = time.Since(now)
defer func() {
@@ -161,10 +159,10 @@
}
}()
now = time.Now()
- newedits := diff.Strings(uri, before, after)
+ newedits := diff.Strings(before, after)
stat.Newedits = len(newedits)
stat.Newtime = time.Now().Sub(now)
- got := diff.ApplyEdits(before, newedits)
+ got := diff.Apply(before, newedits)
if got != after {
stat.Msg += "FAIL"
disaster(before, after)
@@ -176,50 +174,34 @@
}
// ComputeEdits computes a diff using the github.com/sergi/go-diff implementation.
-func ComputeEdits(uri span.URI, before, after string) (edits []diff.TextEdit) {
+func ComputeEdits(before, after string) (edits []diff.Edit) {
// The go-diff library has an unresolved panic (see golang/go#278774).
// TODO(rstambler): Remove the recover once the issue has been fixed
// upstream.
defer func() {
if r := recover(); r != nil {
- bug.Reportf("unable to compute edits for %s: %s", uri.Filename(), r)
-
+ bug.Reportf("unable to compute edits: %s", r)
// Report one big edit for the whole file.
-
- // Reuse the machinery of go/token to convert (content, offset)
- // to (line, column).
- tf := token.NewFileSet().AddFile(uri.Filename(), -1, len(before))
- tf.SetLinesForContent([]byte(before))
- offsetToPoint := func(offset int) span.Point {
- // Re-use span.ToPosition since it contains more than
- // just token.File operations (bug workarounds).
- // But it can only fail if the diff was ill-formed.
- line, col, err := span.ToPosition(tf, offset)
- if err != nil {
- log.Fatalf("invalid offset: %v", err)
- }
- return span.NewPoint(line, col, offset)
- }
- all := span.New(uri, offsetToPoint(0), offsetToPoint(len(before)))
- edits = []diff.TextEdit{{
- Span: all,
- NewText: after,
+ edits = []diff.Edit{{
+ Start: 0,
+ End: len(before),
+ New: after,
}}
}
}()
diffs := diffmatchpatch.New().DiffMain(before, after, true)
- edits = make([]diff.TextEdit, 0, len(diffs))
+ edits = make([]diff.Edit, 0, len(diffs))
offset := 0
for _, d := range diffs {
- start := span.NewPoint(0, 0, offset)
+ start := offset
switch d.Type {
case diffmatchpatch.DiffDelete:
offset += len(d.Text)
- edits = append(edits, diff.TextEdit{Span: span.New(uri, start, span.NewPoint(0, 0, offset))})
+ edits = append(edits, diff.Edit{Start: start, End: offset})
case diffmatchpatch.DiffEqual:
offset += len(d.Text)
case diffmatchpatch.DiffInsert:
- edits = append(edits, diff.TextEdit{Span: span.New(uri, start, span.Point{}), NewText: d.Text})
+ edits = append(edits, diff.Edit{Start: start, End: start, New: d.Text})
}
}
return edits
diff --git a/gopls/internal/lsp/cache/mod_tidy.go b/gopls/internal/lsp/cache/mod_tidy.go
index 5570417..e471a9b 100644
--- a/gopls/internal/lsp/cache/mod_tidy.go
+++ b/gopls/internal/lsp/cache/mod_tidy.go
@@ -419,7 +419,7 @@
return nil, err
}
// Calculate the edits to be made due to the change.
- edits := computeEdits(m.URI, string(m.Content), string(newContent))
+ edits := computeEdits(string(m.Content), string(newContent))
return source.ToProtocolEdits(m, edits)
}
diff --git a/gopls/internal/lsp/cache/parse.go b/gopls/internal/lsp/cache/parse.go
index 5c084fa..ec3e563 100644
--- a/gopls/internal/lsp/cache/parse.go
+++ b/gopls/internal/lsp/cache/parse.go
@@ -157,7 +157,7 @@
// it is likely we got stuck in a loop somehow. Log out a diff
// of the last changes we made to aid in debugging.
if i == 9 {
- edits := diff.Strings(fh.URI(), string(src), string(newSrc))
+ edits := diff.Strings(string(src), string(newSrc))
unified := diff.Unified("before", "after", string(src), edits)
event.Log(ctx, fmt.Sprintf("fixSrc loop - last diff:\n%v", unified), tag.File.Of(tok.Name()))
}
diff --git a/gopls/internal/lsp/cmd/format.go b/gopls/internal/lsp/cmd/format.go
index b2f2afa..17e3e6a 100644
--- a/gopls/internal/lsp/cmd/format.go
+++ b/gopls/internal/lsp/cmd/format.go
@@ -80,7 +80,7 @@
if err != nil {
return fmt.Errorf("%v: %v", spn, err)
}
- formatted := diff.ApplyEdits(string(file.mapper.Content), sedits)
+ formatted := diff.Apply(string(file.mapper.Content), sedits)
printIt := true
if c.List {
printIt = false
diff --git a/gopls/internal/lsp/cmd/imports.go b/gopls/internal/lsp/cmd/imports.go
index eb564ee..7fd5483 100644
--- a/gopls/internal/lsp/cmd/imports.go
+++ b/gopls/internal/lsp/cmd/imports.go
@@ -85,7 +85,7 @@
if err != nil {
return fmt.Errorf("%v: %v", edits, err)
}
- newContent := diff.ApplyEdits(string(file.mapper.Content), sedits)
+ newContent := diff.Apply(string(file.mapper.Content), sedits)
filename := file.uri.Filename()
switch {
diff --git a/gopls/internal/lsp/cmd/rename.go b/gopls/internal/lsp/cmd/rename.go
index a330bae..e0ffa66 100644
--- a/gopls/internal/lsp/cmd/rename.go
+++ b/gopls/internal/lsp/cmd/rename.go
@@ -100,7 +100,7 @@
if err != nil {
return fmt.Errorf("%v: %v", edits, err)
}
- newContent := diff.ApplyEdits(string(cmdFile.mapper.Content), renameEdits)
+ newContent := diff.Apply(string(cmdFile.mapper.Content), renameEdits)
switch {
case r.Write:
diff --git a/gopls/internal/lsp/cmd/suggested_fix.go b/gopls/internal/lsp/cmd/suggested_fix.go
index faf681f..b6022a7 100644
--- a/gopls/internal/lsp/cmd/suggested_fix.go
+++ b/gopls/internal/lsp/cmd/suggested_fix.go
@@ -146,7 +146,7 @@
if err != nil {
return fmt.Errorf("%v: %v", edits, err)
}
- newContent := diff.ApplyEdits(string(file.mapper.Content), sedits)
+ newContent := diff.Apply(string(file.mapper.Content), sedits)
filename := file.uri.Filename()
switch {
diff --git a/gopls/internal/lsp/cmd/test/imports.go b/gopls/internal/lsp/cmd/test/imports.go
index 67826a4..eab4668 100644
--- a/gopls/internal/lsp/cmd/test/imports.go
+++ b/gopls/internal/lsp/cmd/test/imports.go
@@ -19,7 +19,7 @@
return []byte(got), nil
}))
if want != got {
- edits := diff.Strings(uri, want, got)
+ edits := diff.Strings(want, got)
t.Errorf("imports failed for %s, expected:\n%s", filename, diff.Unified("want", "got", want, edits))
}
}
diff --git a/gopls/internal/lsp/command.go b/gopls/internal/lsp/command.go
index e9483b6..cb4c698 100644
--- a/gopls/internal/lsp/command.go
+++ b/gopls/internal/lsp/command.go
@@ -390,7 +390,7 @@
return nil, err
}
// Calculate the edits to be made due to the change.
- diff := snapshot.View().Options().ComputeEdits(pm.URI, string(pm.Mapper.Content), string(newContent))
+ diff := snapshot.View().Options().ComputeEdits(string(pm.Mapper.Content), string(newContent))
return source.ToProtocolEdits(pm.Mapper, diff)
}
@@ -612,7 +612,7 @@
}
m := protocol.NewColumnMapper(fh.URI(), oldContent)
- diff := snapshot.View().Options().ComputeEdits(uri, string(oldContent), string(newContent))
+ diff := snapshot.View().Options().ComputeEdits(string(oldContent), string(newContent))
edits, err := source.ToProtocolEdits(m, diff)
if err != nil {
return nil, err
diff --git a/gopls/internal/lsp/fake/edit.go b/gopls/internal/lsp/fake/edit.go
index 7c83338..bb5fb80 100644
--- a/gopls/internal/lsp/fake/edit.go
+++ b/gopls/internal/lsp/fake/edit.go
@@ -110,7 +110,7 @@
// invalid for the current content.
//
// TODO(rfindley): this function does not handle non-ascii text correctly.
-// TODO(rfindley): replace this with diff.ApplyEdits: we should not be
+// TODO(rfindley): replace this with diff.Apply: we should not be
// maintaining an additional representation of edits.
func editContent(content []string, edits []Edit) ([]string, error) {
newEdits := make([]Edit, len(edits))
diff --git a/gopls/internal/lsp/lsp_test.go b/gopls/internal/lsp/lsp_test.go
index a61f683..78032f0 100644
--- a/gopls/internal/lsp/lsp_test.go
+++ b/gopls/internal/lsp/lsp_test.go
@@ -413,7 +413,7 @@
if err != nil {
t.Error(err)
}
- got := diff.ApplyEdits(string(m.Content), sedits)
+ got := diff.Apply(string(m.Content), sedits)
if diff := compare.Text(gofmted, got); diff != "" {
t.Errorf("format failed for %s (-want +got):\n%s", filename, diff)
}
@@ -979,7 +979,7 @@
if err != nil {
t.Error(err)
}
- got := diff.ApplyEdits(string(m.Content), sedits)
+ got := diff.Apply(string(m.Content), sedits)
withinlayHints := string(r.data.Golden(t, "inlayHint", filename, func() ([]byte, error) {
return []byte(got), nil
@@ -1126,17 +1126,14 @@
return res, nil
}
-func applyEdits(contents string, edits []diff.TextEdit) string {
+func applyEdits(contents string, edits []diff.Edit) string {
res := contents
// Apply the edits from the end of the file forward
// to preserve the offsets
for i := len(edits) - 1; i >= 0; i-- {
edit := edits[i]
- start := edit.Span.Start().Offset()
- end := edit.Span.End().Offset()
- tmp := res[0:start] + edit.NewText
- res = tmp + res[end:]
+ res = res[:edit.Start] + edit.New + res[edit.End:]
}
return res
}
diff --git a/gopls/internal/lsp/mod/format.go b/gopls/internal/lsp/mod/format.go
index 010d2ac..9c3942e 100644
--- a/gopls/internal/lsp/mod/format.go
+++ b/gopls/internal/lsp/mod/format.go
@@ -25,6 +25,6 @@
return nil, err
}
// Calculate the edits to be made due to the change.
- diffs := snapshot.View().Options().ComputeEdits(fh.URI(), string(pm.Mapper.Content), string(formatted))
+ diffs := snapshot.View().Options().ComputeEdits(string(pm.Mapper.Content), string(formatted))
return source.ToProtocolEdits(pm.Mapper, diffs)
}
diff --git a/gopls/internal/lsp/protocol/span.go b/gopls/internal/lsp/protocol/span.go
index 58601a6..f24a28e 100644
--- a/gopls/internal/lsp/protocol/span.go
+++ b/gopls/internal/lsp/protocol/span.go
@@ -70,6 +70,35 @@
return Range{Start: start, End: end}, nil
}
+// OffsetRange returns a Range for the byte-offset interval Content[start:end],
+func (m *ColumnMapper) OffsetRange(start, end int) (Range, error) {
+ // TODO(adonovan): this can surely be simplified by expressing
+ // it terms of more primitive operations.
+
+ // We use span.ToPosition for its "line+1 at EOF" workaround.
+ startLine, startCol, err := span.ToPosition(m.TokFile, start)
+ if err != nil {
+ return Range{}, fmt.Errorf("start line/col: %v", err)
+ }
+ startPoint := span.NewPoint(startLine, startCol, start)
+ startPosition, err := m.Position(startPoint)
+ if err != nil {
+ return Range{}, fmt.Errorf("start position: %v", err)
+ }
+
+ endLine, endCol, err := span.ToPosition(m.TokFile, end)
+ if err != nil {
+ return Range{}, fmt.Errorf("end line/col: %v", err)
+ }
+ endPoint := span.NewPoint(endLine, endCol, end)
+ endPosition, err := m.Position(endPoint)
+ if err != nil {
+ return Range{}, fmt.Errorf("end position: %v", err)
+ }
+
+ return Range{Start: startPosition, End: endPosition}, nil
+}
+
func (m *ColumnMapper) Position(p span.Point) (Position, error) {
chr, err := span.ToUTF16Column(p, m.Content)
if err != nil {
diff --git a/gopls/internal/lsp/source/completion/util.go b/gopls/internal/lsp/source/completion/util.go
index f40c0b3..72877a3 100644
--- a/gopls/internal/lsp/source/completion/util.go
+++ b/gopls/internal/lsp/source/completion/util.go
@@ -10,9 +10,10 @@
"go/types"
"golang.org/x/tools/go/types/typeutil"
- "golang.org/x/tools/internal/diff"
"golang.org/x/tools/gopls/internal/lsp/protocol"
+ "golang.org/x/tools/gopls/internal/lsp/safetoken"
"golang.org/x/tools/gopls/internal/lsp/source"
+ "golang.org/x/tools/internal/diff"
"golang.org/x/tools/internal/typeparams"
)
@@ -311,14 +312,18 @@
}
func (c *completer) editText(from, to token.Pos, newText string) ([]protocol.TextEdit, error) {
- rng := source.NewMappedRange(c.tokFile, c.mapper, from, to)
- spn, err := rng.Span()
+ start, err := safetoken.Offset(c.tokFile, from)
if err != nil {
- return nil, err
+ return nil, err // can't happen: from came from c
}
- return source.ToProtocolEdits(c.mapper, []diff.TextEdit{{
- Span: spn,
- NewText: newText,
+ end, err := safetoken.Offset(c.tokFile, to)
+ if err != nil {
+ return nil, err // can't happen: to came from c
+ }
+ return source.ToProtocolEdits(c.mapper, []diff.Edit{{
+ Start: start,
+ End: end,
+ New: newText,
}})
}
diff --git a/gopls/internal/lsp/source/format.go b/gopls/internal/lsp/source/format.go
index 9080595..dc7445a 100644
--- a/gopls/internal/lsp/source/format.go
+++ b/gopls/internal/lsp/source/format.go
@@ -199,8 +199,8 @@
if fixedData == nil || fixedData[len(fixedData)-1] != '\n' {
fixedData = append(fixedData, '\n') // ApplyFixes may miss the newline, go figure.
}
- edits := snapshot.View().Options().ComputeEdits(pgf.URI, left, string(fixedData))
- return ProtocolEditsFromSource([]byte(left), edits, pgf.Mapper.TokFile)
+ edits := snapshot.View().Options().ComputeEdits(left, string(fixedData))
+ return protocolEditsFromSource([]byte(left), edits, pgf.Mapper.TokFile)
}
// importPrefix returns the prefix of the given file content through the final
@@ -309,69 +309,63 @@
_, done := event.Start(ctx, "source.computeTextEdits")
defer done()
- edits := snapshot.View().Options().ComputeEdits(pgf.URI, string(pgf.Src), formatted)
+ edits := snapshot.View().Options().ComputeEdits(string(pgf.Src), formatted)
return ToProtocolEdits(pgf.Mapper, edits)
}
-// ProtocolEditsFromSource converts text edits to LSP edits using the original
+// protocolEditsFromSource converts text edits to LSP edits using the original
// source.
-func ProtocolEditsFromSource(src []byte, edits []diff.TextEdit, tf *token.File) ([]protocol.TextEdit, error) {
+func protocolEditsFromSource(src []byte, edits []diff.Edit, tf *token.File) ([]protocol.TextEdit, error) {
m := lsppos.NewMapper(src)
var result []protocol.TextEdit
for _, edit := range edits {
- spn, err := edit.Span.WithOffset(tf)
- if err != nil {
- return nil, fmt.Errorf("computing offsets: %v", err)
- }
- rng, err := m.Range(spn.Start().Offset(), spn.End().Offset())
+ rng, err := m.Range(edit.Start, edit.End)
if err != nil {
return nil, err
}
- if rng.Start == rng.End && edit.NewText == "" {
+ if rng.Start == rng.End && edit.New == "" {
// Degenerate case, which may result from a diff tool wanting to delete
// '\r' in line endings. Filter it out.
continue
}
result = append(result, protocol.TextEdit{
Range: rng,
- NewText: edit.NewText,
+ NewText: edit.New,
})
}
return result, nil
}
-func ToProtocolEdits(m *protocol.ColumnMapper, edits []diff.TextEdit) ([]protocol.TextEdit, error) {
- if edits == nil {
- return nil, nil
- }
+func ToProtocolEdits(m *protocol.ColumnMapper, edits []diff.Edit) ([]protocol.TextEdit, error) {
result := make([]protocol.TextEdit, len(edits))
for i, edit := range edits {
- rng, err := m.Range(edit.Span)
+ rng, err := m.OffsetRange(edit.Start, edit.End)
if err != nil {
return nil, err
}
result[i] = protocol.TextEdit{
Range: rng,
- NewText: edit.NewText,
+ NewText: edit.New,
}
}
return result, nil
}
-func FromProtocolEdits(m *protocol.ColumnMapper, edits []protocol.TextEdit) ([]diff.TextEdit, error) {
+func FromProtocolEdits(m *protocol.ColumnMapper, edits []protocol.TextEdit) ([]diff.Edit, error) {
if edits == nil {
return nil, nil
}
- result := make([]diff.TextEdit, len(edits))
+ result := make([]diff.Edit, len(edits))
for i, edit := range edits {
spn, err := m.RangeSpan(edit.Range)
if err != nil {
return nil, err
}
- result[i] = diff.TextEdit{
- Span: spn,
- NewText: edit.NewText,
+ result[i] = diff.Edit{
+ Start: spn.Start().Offset(),
+ End: spn.End().Offset(),
+ New: edit.NewText,
}
}
return result, nil
diff --git a/gopls/internal/lsp/source/options.go b/gopls/internal/lsp/source/options.go
index 8159221..04a614c 100644
--- a/gopls/internal/lsp/source/options.go
+++ b/gopls/internal/lsp/source/options.go
@@ -67,7 +67,6 @@
"golang.org/x/tools/gopls/internal/lsp/protocol"
"golang.org/x/tools/internal/diff"
"golang.org/x/tools/internal/diff/myers"
- "golang.org/x/tools/internal/span"
)
var (
@@ -501,7 +500,7 @@
// DiffFunction is the type for a function that produces a set of edits that
// convert from the before content to the after content.
-type DiffFunction func(uri span.URI, before, after string) []diff.TextEdit
+type DiffFunction func(before, after string) []diff.Edit
// Hooks contains configuration that is provided to the Gopls command by the
// main package.
diff --git a/gopls/internal/lsp/source/rename.go b/gopls/internal/lsp/source/rename.go
index 93ded0f..842b1a9 100644
--- a/gopls/internal/lsp/source/rename.go
+++ b/gopls/internal/lsp/source/rename.go
@@ -19,6 +19,7 @@
"golang.org/x/tools/go/types/typeutil"
"golang.org/x/tools/gopls/internal/lsp/protocol"
+ "golang.org/x/tools/gopls/internal/lsp/safetoken"
"golang.org/x/tools/internal/diff"
"golang.org/x/tools/internal/event"
"golang.org/x/tools/internal/span"
@@ -445,8 +446,7 @@
return nil, err
}
m := protocol.NewColumnMapper(uri, data)
- // Sort the edits first.
- diff.SortTextEdits(edits)
+ diff.SortEdits(edits)
protocolEdits, err := ToProtocolEdits(m, edits)
if err != nil {
return nil, err
@@ -457,8 +457,8 @@
}
// Rename all references to the identifier.
-func (r *renamer) update() (map[span.URI][]diff.TextEdit, error) {
- result := make(map[span.URI][]diff.TextEdit)
+func (r *renamer) update() (map[span.URI][]diff.Edit, error) {
+ result := make(map[span.URI][]diff.Edit)
seen := make(map[span.Span]bool)
docRegexp, err := regexp.Compile(`\b` + r.from + `\b`)
@@ -487,9 +487,10 @@
}
// Replace the identifier with r.to.
- edit := diff.TextEdit{
- Span: refSpan,
- NewText: r.to,
+ edit := diff.Edit{
+ Start: refSpan.Start().Offset(),
+ End: refSpan.End().Offset(),
+ New: r.to,
}
result[refSpan.URI()] = append(result[refSpan.URI()], edit)
@@ -510,23 +511,26 @@
if isDirective(comment.Text) {
continue
}
+ // TODO(adonovan): why are we looping over lines?
+ // Just run the loop body once over the entire multiline comment.
lines := strings.Split(comment.Text, "\n")
tokFile := r.fset.File(comment.Pos())
commentLine := tokFile.Line(comment.Pos())
+ uri := span.URIFromPath(tokFile.Name())
for i, line := range lines {
lineStart := comment.Pos()
if i > 0 {
lineStart = tokFile.LineStart(commentLine + i)
}
for _, locs := range docRegexp.FindAllIndex([]byte(line), -1) {
- rng := span.NewRange(tokFile, lineStart+token.Pos(locs[0]), lineStart+token.Pos(locs[1]))
- spn, err := rng.Span()
- if err != nil {
- return nil, err
- }
- result[spn.URI()] = append(result[spn.URI()], diff.TextEdit{
- Span: spn,
- NewText: r.to,
+ // The File.Offset static check complains
+ // even though these uses are manifestly safe.
+ start, _ := safetoken.Offset(tokFile, lineStart+token.Pos(locs[0]))
+ end, _ := safetoken.Offset(tokFile, lineStart+token.Pos(locs[1]))
+ result[uri] = append(result[uri], diff.Edit{
+ Start: start,
+ End: end,
+ New: r.to,
})
}
}
@@ -588,7 +592,7 @@
// updatePkgName returns the updates to rename a pkgName in the import spec by
// only modifying the package name portion of the import declaration.
-func (r *renamer) updatePkgName(pkgName *types.PkgName) (*diff.TextEdit, error) {
+func (r *renamer) updatePkgName(pkgName *types.PkgName) (*diff.Edit, error) {
// Modify ImportSpec syntax to add or remove the Name as needed.
pkg := r.packages[pkgName.Pkg()]
_, tokFile, path, _ := pathEnclosingInterval(r.fset, pkg, pkgName.Pos(), pkgName.Pos())
@@ -614,8 +618,9 @@
return nil, err
}
- return &diff.TextEdit{
- Span: spn,
- NewText: newText,
+ return &diff.Edit{
+ Start: spn.Start().Offset(),
+ End: spn.End().Offset(),
+ New: newText,
}, nil
}
diff --git a/gopls/internal/lsp/source/source_test.go b/gopls/internal/lsp/source/source_test.go
index d899f4f..0a4e70c 100644
--- a/gopls/internal/lsp/source/source_test.go
+++ b/gopls/internal/lsp/source/source_test.go
@@ -489,7 +489,7 @@
if err != nil {
t.Error(err)
}
- got := diff.ApplyEdits(string(data), diffEdits)
+ got := diff.Apply(string(data), diffEdits)
if gofmted != got {
t.Errorf("format failed for %s, expected:\n%v\ngot:\n%v", spn.URI().Filename(), gofmted, got)
}
@@ -520,7 +520,7 @@
if err != nil {
t.Error(err)
}
- got := diff.ApplyEdits(string(data), diffEdits)
+ got := diff.Apply(string(data), diffEdits)
want := string(r.data.Golden(t, "goimports", spn.URI().Filename(), func() ([]byte, error) {
return []byte(got), nil
}))
@@ -821,17 +821,14 @@
}
}
-func applyEdits(contents string, edits []diff.TextEdit) string {
+func applyEdits(contents string, edits []diff.Edit) string {
res := contents
// Apply the edits from the end of the file forward
// to preserve the offsets
for i := len(edits) - 1; i >= 0; i-- {
edit := edits[i]
- start := edit.Span.Start().Offset()
- end := edit.Span.End().Offset()
- tmp := res[0:start] + edit.NewText
- res = tmp + res[end:]
+ res = res[:edit.Start] + edit.New + res[edit.End:]
}
return res
}
diff --git a/gopls/internal/lsp/source/stub.go b/gopls/internal/lsp/source/stub.go
index d0dff4f..3aab0b4 100644
--- a/gopls/internal/lsp/source/stub.go
+++ b/gopls/internal/lsp/source/stub.go
@@ -80,17 +80,14 @@
if err != nil {
return nil, fmt.Errorf("format.Node: %w", err)
}
- diffs := snapshot.View().Options().ComputeEdits(parsedConcreteFile.URI, string(parsedConcreteFile.Src), source.String())
+ diffs := snapshot.View().Options().ComputeEdits(string(parsedConcreteFile.Src), source.String())
+ tf := parsedConcreteFile.Mapper.TokFile
var edits []analysis.TextEdit
for _, edit := range diffs {
- rng, err := edit.Span.Range(parsedConcreteFile.Mapper.TokFile)
- if err != nil {
- return nil, err
- }
edits = append(edits, analysis.TextEdit{
- Pos: rng.Start,
- End: rng.End,
- NewText: []byte(edit.NewText),
+ Pos: tf.Pos(edit.Start),
+ End: tf.Pos(edit.End),
+ NewText: []byte(edit.New),
})
}
return &analysis.SuggestedFix{
diff --git a/gopls/internal/lsp/tests/compare/text.go b/gopls/internal/lsp/tests/compare/text.go
index 66d2e62..0563fcd 100644
--- a/gopls/internal/lsp/tests/compare/text.go
+++ b/gopls/internal/lsp/tests/compare/text.go
@@ -22,7 +22,7 @@
want += "\n"
got += "\n"
- edits := diff.Strings("irrelevant", want, got)
+ edits := diff.Strings(want, got)
diff := diff.Unified("want", "got", want, edits)
// Defensively assert that we get an actual diff, so that we guarantee the
diff --git a/gopls/internal/lsp/tests/util.go b/gopls/internal/lsp/tests/util.go
index d463ba0..ce5ab5b 100644
--- a/gopls/internal/lsp/tests/util.go
+++ b/gopls/internal/lsp/tests/util.go
@@ -230,7 +230,7 @@
w := want.Signatures[0]
if NormalizeAny(w.Label) != NormalizeAny(g.Label) {
wLabel := w.Label + "\n"
- edits := diff.Strings("", wLabel, g.Label+"\n")
+ edits := diff.Strings(wLabel, g.Label+"\n")
return decorate("mismatched labels:\n%q", diff.Unified("want", "got", wLabel, edits)), nil
}
var paramParts []string
diff --git a/gopls/internal/lsp/work/format.go b/gopls/internal/lsp/work/format.go
index bc84464..e852eb4 100644
--- a/gopls/internal/lsp/work/format.go
+++ b/gopls/internal/lsp/work/format.go
@@ -23,6 +23,6 @@
}
formatted := modfile.Format(pw.File.Syntax)
// Calculate the edits to be made due to the change.
- diffs := snapshot.View().Options().ComputeEdits(fh.URI(), string(pw.Mapper.Content), string(formatted))
+ diffs := snapshot.View().Options().ComputeEdits(string(pw.Mapper.Content), string(formatted))
return source.ToProtocolEdits(pw.Mapper, diffs)
}
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++
}
diff --git a/internal/span/span.go b/internal/span/span.go
index 502145b..a714cca 100644
--- a/internal/span/span.go
+++ b/internal/span/span.go
@@ -42,7 +42,7 @@
var invalidPoint = Point{v: point{Line: 0, Column: 0, Offset: -1}}
-func New(uri URI, start Point, end Point) Span {
+func New(uri URI, start, end Point) Span {
s := Span{v: span{URI: uri, Start: start.v, End: end.v}}
s.v.clean()
return s
diff --git a/internal/span/token.go b/internal/span/token.go
index d3827eb..da4dc22 100644
--- a/internal/span/token.go
+++ b/internal/span/token.go
@@ -141,7 +141,7 @@
func positionFromOffset(tf *token.File, offset int) (string, int, int, error) {
if offset > tf.Size() {
- return "", 0, 0, fmt.Errorf("offset %v is past the end of the file %v", offset, tf.Size())
+ return "", 0, 0, fmt.Errorf("offset %d is beyond EOF (%d) in file %s", offset, tf.Size(), tf.Name())
}
pos := tf.Pos(offset)
p := tf.Position(pos)
