volumen/internal/diff/diff.go

// Copyright (c) 2026 Petr Balvín <opensource@petrbalvin.org> (https://petrbalvin.org)
// SPDX-License-Identifier: PolyForm-Noncommercial-1.0.0

// Package diff renders a line-based difference between two texts. The
// classic longest-common-subsequence dynamic program is enough here:
// post-sized inputs are small, and inputs beyond the cell budget fall
// back to an honest full replacement rather than a slow or hungry walk.
package diff

import "strings"

// Op classifies one line of the result.
type Op uint8

const (
	// Equal marks a line both texts share.
	Equal Op = iota
	// Removed marks a line only the old text carries.
	Removed
	// Added marks a line only the new text carries.
	Added
	// Skipped marks equal lines the context collapse hid.
	Skipped
)

// Is reports whether the operation matches the name a template asks
// for: "equal", "removed", "added" or "skipped".
func (o Op) Is(name string) bool {
	switch name {
	case "equal":
		return o == Equal
	case "removed":
		return o == Removed
	case "added":
		return o == Added
	case "skipped":
		return o == Skipped
	}
	return false
}

// Chunk is a run of consecutive lines with one operation.
type Chunk struct {
	Op      Op
	Lines   []string
	Skipped int // Skipped only: how many equal lines the collapse hid
}

// maxCells bounds the dynamic-programming table. Past it, the diff
// degrades to a whole-text replacement: rare, and never wrong.
const maxCells = 4_000_000

// Chunks diffs the old text against the new one line by line and
// collapses long equal runs to context lines around each change. The
// texts are split on newlines; a trailing newline does not create an
// empty final line.
func Chunks(oldText, newText string, context int) []Chunk {
	oldLines := split(oldText)
	newLines := split(newText)

	ops := make([]Op, 0, len(oldLines)+len(newLines))
	if len(oldLines)*len(newLines) > maxCells {
		ops = appendAll(ops, Removed, oldLines)
		ops = appendAll(ops, Added, newLines)
	} else {
		ops = lcs(oldLines, newLines)
	}
	return collapse(ops, oldLines, newLines, context)
}

// split breaks a text into lines without a phantom empty line for the
// trailing newline.
func split(text string) []string {
	text = strings.TrimSuffix(text, "\n")
	if text == "" {
		return nil
	}
	return strings.Split(text, "\n")
}

func appendAll(ops []Op, op Op, lines []string) []Op {
	for range lines {
		ops = append(ops, op)
	}
	return ops
}

// lcs walks the dynamic-programming table backwards and yields the
// per-line operations.
func lcs(a, b []string) []Op {
	n, m := len(a), len(b)
	// table[i][j] holds the LCS length of a[i:] and b[j:].
	table := make([]int32, (n+1)*(m+1))
	at := func(i, j int) *int32 { return &table[i*(m+1)+j] }
	for i := n - 1; i >= 0; i-- {
		for j := m - 1; j >= 0; j-- {
			if a[i] == b[j] {
				*at(i, j) = *at(i+1, j+1) + 1
			} else {
				down, right := *at(i+1, j), *at(i, j+1)
				*at(i, j) = max(down, right)
			}
		}
	}
	ops := make([]Op, 0, n+m)
	i, j := 0, 0
	for i < n && j < m {
		switch {
		case a[i] == b[j]:
			ops = append(ops, Equal)
			i++
			j++
		case *at(i+1, j) >= *at(i, j+1):
			ops = append(ops, Removed)
			i++
		default:
			ops = append(ops, Added)
			j++
		}
	}
	ops = appendAll(ops, Removed, a[i:])
	ops = appendAll(ops, Added, b[j:])
	return ops
}

// collapse groups the operations into chunks and trims equal runs to
// context lines around the changes.
func collapse(ops []Op, a, b []string, context int) []Chunk {
	// Position each operation over its source line.
	type line struct {
		op   Op
		text string
	}
	out := make([]line, 0, len(ops))
	ai, bi := 0, 0
	for _, op := range ops {
		switch op {
		case Removed:
			out = append(out, line{Removed, a[ai]})
			ai++
		case Added:
			out = append(out, line{Added, b[bi]})
			bi++
		default:
			out = append(out, line{Equal, a[ai]})
			ai++
			bi++
		}
	}

	var chunks []Chunk
	for start := 0; start < len(out); {
		op := out[start].op
		end := start
		for end < len(out) && out[end].op == op {
			end++
		}
		lines := make([]string, 0, end-start)
		for _, l := range out[start:end] {
			lines = append(lines, l.text)
		}
		chunks = append(chunks, Chunk{Op: op, Lines: lines})
		start = end
	}

	// Collapse an equal chunk only when another change follows it; the
	// leading context of the first change stays whole.
	if context < 0 {
		context = 0
	}
	final := make([]Chunk, 0, len(chunks))
	for _, chunk := range chunks {
		final = append(final, chunk)
	}
	for i := 0; i < len(final)-1; i++ {
		c := &final[i]
		if c.Op != Equal || len(c.Lines) <= 2*context+4 {
			continue
		}
		hidden := len(c.Lines) - 2*context
		collapsed := Chunk{Op: Skipped, Skipped: hidden}
		with := make([]Chunk, 0, len(final)+1)
		with = append(with, final[:i]...)
		with = append(with, Chunk{Op: Equal, Lines: c.Lines[:context]})
		with = append(with, collapsed)
		with = append(with, Chunk{Op: Equal, Lines: c.Lines[len(c.Lines)-context:]})
		with = append(with, final[i+1:]...)
		final = with
		i++
	}
	return final
}