patchwork

// Package diff compares two versions of a document at two levels: blocks
// (paragraphs, list items, code) and, inside a changed block, words.
package diff

// EditKind is the type of one run in an edit script.
type EditKind int

const (
	Eq EditKind = iota
	Del
	Ins
)

// Edit is a run of the edit script: a[A0:A1] deleted, b[B0:B1] inserted, or
// a[A0:A1] == b[B0:B1] kept.
type Edit struct {
	Kind           EditKind
	A0, A1, B0, B1 int
}

// maxD bounds the search. Two versions that differ in more than maxD
// elements get one big replacement instead of an expensive minimal script;
// nobody reads a minimal diff of a rewritten page anyway.
const maxD = 4000

// Myers returns a shortest edit script from a to b (Myers 1986, the greedy
// O(ND) forward search with trace back), as runs in order.
func Myers[T comparable](a, b []T) []Edit {
	pre := 0
	for pre < len(a) && pre < len(b) && a[pre] == b[pre] {
		pre++
	}
	suf := 0
	for suf < len(a)-pre && suf < len(b)-pre && a[len(a)-1-suf] == b[len(b)-1-suf] {
		suf++
	}
	mid := middle(a[pre:len(a)-suf], b[pre:len(b)-suf])

	var out []Edit
	add := func(e Edit) {
		if e.A0 == e.A1 && e.B0 == e.B1 {
			return
		}
		if n := len(out); n > 0 && out[n-1].Kind == e.Kind && out[n-1].A1 == e.A0 && out[n-1].B1 == e.B0 {
			out[n-1].A1, out[n-1].B1 = e.A1, e.B1
			return
		}
		out = append(out, e)
	}
	add(Edit{Eq, 0, pre, 0, pre})
	for _, e := range mid {
		add(Edit{e.Kind, e.A0 + pre, e.A1 + pre, e.B0 + pre, e.B1 + pre})
	}
	add(Edit{Eq, len(a) - suf, len(a), len(b) - suf, len(b)})
	return out
}

func middle[T comparable](a, b []T) []Edit {
	n, m := len(a), len(b)
	if n == 0 && m == 0 {
		return nil
	}
	if n == 0 || m == 0 {
		return replaceAll(n, m)
	}
	max := n + m
	if max > maxD {
		max = maxD
	}
	offset := max + 1
	v := make([]int, 2*max+3)
	var trace [][]int
	for d := 0; d <= max; d++ {
		trace = append(trace, append([]int(nil), v...))
		for k := -d; k <= d; k += 2 {
			var x int
			if k == -d || (k != d && v[offset+k-1] < v[offset+k+1]) {
				x = v[offset+k+1]
			} else {
				x = v[offset+k-1] + 1
			}
			y := x - k
			for x < n && y < m && a[x] == b[y] {
				x++
				y++
			}
			v[offset+k] = x
			if x >= n && y >= m {
				return backtrack(trace, offset, n, m)
			}
		}
	}
	return replaceAll(n, m)
}

func backtrack(trace [][]int, offset, n, m int) []Edit {
	var rev []Edit
	x, y := n, m
	for d := len(trace) - 1; d > 0; d-- {
		v := trace[d]
		k := x - y
		var prevK int
		if k == -d || (k != d && v[offset+k-1] < v[offset+k+1]) {
			prevK = k + 1
		} else {
			prevK = k - 1
		}
		prevX := v[offset+prevK]
		prevY := prevX - prevK
		for x > prevX && y > prevY {
			rev = append(rev, Edit{Eq, x - 1, x, y - 1, y})
			x--
			y--
		}
		if x == prevX {
			rev = append(rev, Edit{Ins, x, x, y - 1, y})
		} else {
			rev = append(rev, Edit{Del, x - 1, x, y, y})
		}
		x, y = prevX, prevY
	}
	for x > 0 && y > 0 {
		rev = append(rev, Edit{Eq, x - 1, x, y - 1, y})
		x--
		y--
	}
	out := make([]Edit, 0, len(rev))
	for i := len(rev) - 1; i >= 0; i-- {
		e := rev[i]
		if n := len(out); n > 0 && out[n-1].Kind == e.Kind && out[n-1].A1 == e.A0 && out[n-1].B1 == e.B0 {
			out[n-1].A1, out[n-1].B1 = e.A1, e.B1
			continue
		}
		out = append(out, e)
	}
	return out
}

func replaceAll(n, m int) []Edit {
	var out []Edit
	if n > 0 {
		out = append(out, Edit{Del, 0, n, 0, 0})
	}
	if m > 0 {
		out = append(out, Edit{Ins, n, n, 0, m})
	}
	return out
}