README
¶
diff
Package diff implements methods for comparing objects and producing edit scripts. The motivation for creating the package was to be able to use the diff output format in tests where the output of go-cmp wasn’t suitable. Comparing sequences of lengths N and M whose shortest edit script has D operations takes O((N+M)D) time and O(N+M) space. See the package documentation for more information.
Installation
$ go get mibk.dev/diff
Migrating from v0.1.0
v0.1.0 shipped without a go.mod
and was imported as github.com/mibk/diff.
The module is now mibk.dev/diff, so go get -u refuses the upgrade
and restores v0.1.0, reporting a path mismatch.
To move over:
-
Move the imports over, from the root of your module:
$ go run mibk.dev/mvimport@latest github.com/mibk/diff mibk.dev/diffThat rewrites every import in the module, swaps the
requirefor the new path at its latest version, prunes the oldgo.sumlines, and gofmts what it touched, so there is nothing left forgo mod tidyto do. It needs Go 1.25 or newer. -
Run
go fix ./..., which rewrites calls to the deprecatedIntSlices,Float64SlicesandStringSlicesinto calls toSlices. This step needs Go 1.26 or newer.
To take the new version without touching the import paths yet, map the old path onto the new module instead:
replace github.com/mibk/diff => mibk.dev/diff v0.2.0
Where a pair of sequences has several shortest edit scripts, v0.2.0 may report a different one than v0.1.0 did. Both are equally minimal, but tests pinned to the exact output can need updating.
Documentation
¶
Overview ¶
Package diff implements methods for comparing objects and producing edit scripts.
The implementation is based on the algorithm described in the paper "An O(ND) Difference Algorithm and Its Variations" by Eugene W. Myers, Algorithmica Vol. 1 No. 2, 1986, p. 251, including the linear space refinement of its section 4b. Comparing sequences of lengths N and M whose shortest edit script has D operations takes O((N+M)D) time and O(N+M) space.
Where several edit scripts of that shortest length exist, which one Diff reports is not part of the API.
Example (CustomType) ¶
package main
import (
"fmt"
"mibk.dev/diff"
)
// columns presents two grids of ASCII characters to Diff
// as their sequences of columns.
// A column is not a slice of its own,
// which is what the Data interface is for:
// it describes a sequence by index,
// leaving it to exist however it already does.
type columns struct {
a, b []string
}
func (c columns) Lens() (n, m int) { return len(c.a[0]), len(c.b[0]) }
func (c columns) Equal(i, j int) bool {
for r := range c.a {
if c.a[r][i] != c.b[r][j] {
return false
}
}
return true
}
func main() {
a := []string{
"abcd",
"1234",
}
b := []string{
"abxd",
"12y4",
}
for _, ed := range diff.Diff(columns{a, b}) {
switch ed.Op {
case diff.Delete:
fmt.Println("-", column(a, ed.Index))
case diff.Insert:
fmt.Println("+", column(b, ed.Bindex))
}
}
}
func column(rows []string, i int) string {
col := make([]byte, len(rows))
for r, row := range rows {
col[r] = row[i]
}
return string(col)
}
Output: - c3 + xy
Example (IgnoreCase) ¶
package main
import (
"fmt"
"strings"
"mibk.dev/diff"
)
// missingIgnoreCase returns elements that are moved or deleted from a
// compared to b.
func missingIgnoreCase(a, b []string) []string {
eds := diff.SlicesFunc(a, b, strings.EqualFold)
var miss []string
for _, ed := range eds {
if ed.Op == diff.Insert {
miss = append(miss, b[ed.Bindex])
}
}
return miss
}
func main() {
a := []string{"black", "#31ad1d", "#8923dd", "#baddad", "yellow"}
b := []string{"#31AD1D", "#8924dd", "#BadDad", "black", "YELLOW"}
for _, m := range missingIgnoreCase(a, b) {
fmt.Println("-", m)
}
}
Output: - #8924dd - black
Example (SimpleDiffOutput) ¶
package main
import (
"fmt"
"mibk.dev/diff"
)
func main() {
a := []string{"Alice", "Bob", "Cyril", "Alice", "Bob", "Bob", "Alice", "Daniel"}
b := []string{"Cyril", "Bob", "Alice", "Bob", "Alice", "Cyril", "Daniel"}
eds := diff.Slices(a, b)
eds = append(eds, diff.Edit{Index: len(a), Op: diff.None})
var i int
for _, ed := range eds {
for ; i < ed.Index; i++ {
fmt.Printf(" %s\n", a[i])
}
switch ed.Op {
case diff.Delete:
fmt.Printf("-%s\n", a[i])
i++
case diff.Insert:
fmt.Printf("+%s\n", b[ed.Bindex])
}
}
}
Output: -Alice -Bob Cyril -Alice Bob +Alice Bob Alice +Cyril Daniel
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Data ¶
type Data interface {
// Lens returns the lengths of the underlying sequences.
Lens() (n, m int)
// Equal reports whether the elements from the two sequences
// with indexes i and j are equal.
Equal(i, j int) bool
}
Data is the interface that is used by the Diff function to produce an edit script. A type that satisfies the Data interface is typically a wrapper around two collections. The interface requires that the elements of the sequences be enumerated by integer indexes.
type Edit ¶
type Edit struct {
Index int // index where the operation should occur
Op Operation
Bindex int // only valid for Insert
}
An Edit represents an element in the edit script, produced by the Diff function. The edit script represents a set of operations describing how to convert the sequence A into the sequence B.
Each Edit has an operation Op (either Insert or Delete) that should occur at Index in A in order to convert it into B. If Op is Insert, Bindex represents the index of the element in B that should be inserted into A at Index.
func Diff ¶
Diff creates an edit script for data. The edit script represents a set of operations describing how to convert the sequence A into the sequence B.
func Float64Slices
deprecated
func Slices ¶ added in v0.2.0
func Slices[E comparable](a, b []E) []Edit
Slices creates an edit script for two slices. Elements are compared with ==, so a NaN differs from every element, including itself.
func SlicesFunc ¶ added in v0.2.0
SlicesFunc is like Slices, but compares the elements with eq. The two slices need not hold the same type.
Source Files