diff.go

// 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.
package diff

// Operation represents an operation in the edit script.
type Operation int

// The list of possible operations.
//
// None is never used by the package. It can be used as a sentinel
// operation for Edit.Op; the value is reserved. See the simple diff
// output example for an illustration of usage.
const (
	None Operation = iota
	Delete
	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.
type Edit struct {
	Index  int // index where the operation should occur
	Op     Operation
	Bindex int // only valid for Insert
}

// 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 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
}

// 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 Diff(data Data) []Edit {
	n, m := data.Lens()

	// Some shortest edit script leaves a common prefix and a common
	// suffix alone, so the search only has to cover what lies between
	// them.
	// Trimming them before the vectors are sized is what makes
	// identical, and nearly identical, inputs cheap;
	// identical ones do not allocate at all.
	var pre int
	for pre < n && pre < m && data.Equal(pre, pre) {
		pre++
	}
	for n > pre && m > pre && data.Equal(n-1, m-1) {
		n, m = n-1, m-1
	}
	n, m = n-pre, m-pre
	if n == 0 && m == 0 {
		return nil
	}

	// Every subproblem is a rectangle within the trimmed one, so one
	// pair of vectors shared by all recursion levels is enough, sized
	// for the widest search that rectangle can require. The forward
	// search spans the diagonals [-half, half] and the reverse one
	// those [delta-half, delta+half], where delta lies in [-m, n]; off
	// shifts a diagonal to a vector index, and both ends leave room
	// for the neighbour just past the last diagonal.
	half := (n + m + 1) / 2
	off := half + m + 1
	size := off + half + n + 2
	v := make([]int, 2*size)
	p := &differ{data: data, vf: v[:size], vr: v[size:], off: off}
	p.diff(pre, pre, n, m)
	return p.eds
}

type differ struct {
	data Data
	// vf and vr hold the furthest-reaching path on each diagonal for
	// the forward and the reverse search of the current subproblem.
	vf, vr []int
	off    int // index of diagonal 0 within vf and vr
	eds    []Edit
}

// diff appends to p.eds the edit script converting the elements
// [x0, x0+n) of A into the elements [y0, y0+m) of B.
func (p *differ) diff(x0, y0, n, m int) {
	if n == 0 {
		for j := range m {
			p.eds = append(p.eds, Edit{x0, Insert, y0 + j})
		}
		return
	}
	if m == 0 {
		for i := range n {
			p.eds = append(p.eds, Edit{x0 + i, Delete, 0})
		}
		return
	}

	xs, ys, xe, ye, d := p.middleSnake(x0, y0, n, m)
	if d > 1 {
		// Each half has a strictly shorter edit script than d,
		// which is what makes the recursion terminate.
		// Descending into the left half first keeps p.eds ordered
		// by index.
		p.diff(x0, y0, xs, ys)
		p.diff(x0+xe, y0+ye, n-xe, m-ye)
		return
	}

	// A d of 0 means the rectangle is a single diagonal
	// and there is nothing to report.
	// A d of 1 means one insert or delete,
	// which the shortest script places right after the common prefix.
	if n == m {
		return
	}
	i := 0
	for i < n && i < m && p.data.Equal(x0+i, y0+i) {
		i++
	}
	if n < m {
		p.eds = append(p.eds, Edit{x0 + i, Insert, y0 + i})
	} else {
		p.eds = append(p.eds, Edit{x0 + i, Delete, 0})
	}
}

// middleSnake runs the forward and the reverse search of the greedy
// algorithm in lockstep until they overlap,
// which happens halfway along a shortest path.
// It reports the diagonal run at the meeting point, from (xs, ys) to
// (xe, ye) in coordinates relative to (x0, y0),
// and the length d of the shortest edit script for the rectangle
// [x0, x0+n) x [y0, y0+m).
//
// Splitting the rectangle at the two ends of that run is what keeps
// the space linear:
// the two halves are solved one after the other, so they can share vf
// and vr instead of the algorithm having to retain a search vector
// per step.
func (p *differ) middleSnake(x0, y0, n, m int) (xs, ys, xe, ye, d int) {
	// The reverse search starts at (n, m), which lies on diagonal delta.
	// Its parity decides which of the two searches
	// can be the one to detect the overlap.
	delta := n - m
	odd := delta%2 != 0

	p.vf[p.off+1] = 0
	p.vr[p.off+delta+1] = n + 1

	// The two searches are bound to overlap once their steps add up
	// to the length of a shortest path, so half of them suffice.
	half := (n + m + 1) / 2

	// Both searches walk their diagonals from the highest down,
	// so that when several of them overlap at the same step
	// the meeting point picked is the one furthest along A.
	// That is what makes an all-different rectangle come out as its
	// deletes followed by its inserts rather than the other way round.
	for step := 0; step <= half; step++ {
		for k := step; k >= -step; k -= 2 {
			var x int
			if k == -step || k != step && p.vf[p.off+k-1] < p.vf[p.off+k+1] {
				x = p.vf[p.off+k+1]
			} else {
				x = p.vf[p.off+k-1] + 1
			}
			y := x - k

			xs, ys = x, y
			for x < n && y < m && p.data.Equal(x0+x, y0+y) {
				x, y = x+1, y+1
			}
			p.vf[p.off+k] = x

			// The reverse search has run step-1 steps so far,
			// so only the diagonals it has reached can overlap.
			if odd && k-delta >= 1-step && k-delta <= step-1 && x >= p.vr[p.off+k] {
				return xs, ys, x, y, 2*step - 1
			}
		}

		for k := delta + step; k >= delta-step; k -= 2 {
			var x int
			if k == delta-step || k != delta+step && p.vr[p.off+k+1]-1 < p.vr[p.off+k-1] {
				x = p.vr[p.off+k+1] - 1
			} else {
				x = p.vr[p.off+k-1]
			}
			y := x - k

			xe, ye = x, y
			for x > 0 && y > 0 && p.data.Equal(x0+x-1, y0+y-1) {
				x, y = x-1, y-1
			}
			p.vr[p.off+k] = x

			if !odd && k >= -step && k <= step && p.vf[p.off+k] >= x {
				return x, y, xe, ye, 2 * step
			}
		}
	}
	panic("unreachable")
}

// Slices creates an edit script for two slices.
// Elements are compared with ==,
// so a NaN differs from every element,
// including itself.
func Slices[E comparable](a, b []E) []Edit { return Diff(&sliceData[E]{a, b}) }

// SlicesFunc is like Slices, but compares the elements with eq.
// The two slices need not hold the same type.
func SlicesFunc[E1, E2 any](a []E1, b []E2, eq func(x E1, y E2) bool) []Edit {
	return Diff(&sliceFuncData[E1, E2]{a, b, eq})
}

// IntSlices creates an edit script for two slices of ints.
//
// Deprecated: Use [Slices] instead.
//
//go:fix inline
func IntSlices(a, b []int) []Edit { return Slices(a, b) }

// Float64Slices creates an edit script for two slices of float64s.
//
// Deprecated: Use [Slices] instead.
//
//go:fix inline
func Float64Slices(a, b []float64) []Edit { return Slices(a, b) }

// StringSlices creates an edit script for two slices of strings.
//
// Deprecated: Use [Slices] instead.
//
//go:fix inline
func StringSlices(a, b []string) []Edit { return Slices(a, b) }

// sliceData presents a pair of slices to Diff.
type sliceData[E comparable] struct {
	a, b []E
}

func (p *sliceData[E]) Lens() (n, m int)    { return len(p.a), len(p.b) }
func (p *sliceData[E]) Equal(i, j int) bool { return p.a[i] == p.b[j] }

// sliceFuncData is sliceData for elements
// that == cannot compare, or should not.
// It keeps eq out of sliceData
// so that the common case stays a direct comparison
// rather than a call through a function value.
type sliceFuncData[E1, E2 any] struct {
	a  []E1
	b  []E2
	eq func(x E1, y E2) bool
}

func (p *sliceFuncData[E1, E2]) Lens() (n, m int)    { return len(p.a), len(p.b) }
func (p *sliceFuncData[E1, E2]) Equal(i, j int) bool { return p.eq(p.a[i], p.b[j]) }