gasm-sdk/cmd/gasm/unidiff.go

// Copyright (c) 2026 Petr Balvín <opensource@petrbalvin.org> (https://petrbalvin.org)
// SPDX-License-Identifier: BSD-3-Clause

package main

import (
	"fmt"
	"slices"
	"strings"
)

// unifiedDiff renders a unified diff with three lines of context between the
// two line slices, in the form `gofmt -d` prints.  An empty result means the
// inputs are identical.
func unifiedDiff(name string, a, b []string) string {
	if slices.Equal(a, b) {
		return ""
	}
	var out strings.Builder
	fmt.Fprintf(&out, "--- %s\n+++ %s\n", name, name)

	// Longest common subsequence over the lines (assembly files are small
	// enough for the quadratic table).
	n, m := len(a), len(b)
	lcs := make([][]int, n+1)
	for i := range lcs {
		lcs[i] = make([]int, m+1)
	}
	for i := n - 1; i >= 0; i-- {
		for j := m - 1; j >= 0; j-- {
			if a[i] == b[j] {
				lcs[i][j] = lcs[i+1][j+1] + 1
			} else if lcs[i+1][j] >= lcs[i][j+1] {
				lcs[i][j] = lcs[i+1][j]
			} else {
				lcs[i][j] = lcs[i][j+1]
			}
		}
	}

	// Walk the LCS once, assigning every op its absolute position in both
	// files (1-based, the position an insertion sits before).
	type op struct {
		kind         byte // ' ', '-' or '+'
		aLine, bLine int
		text         string
	}
	var ops []op
	aPos, bPos := 0, 0
	emit := func(kind byte, text string) {
		ops = append(ops, op{kind: kind, aLine: aPos + 1, bLine: bPos + 1, text: text})
		switch kind {
		case ' ':
			aPos++
			bPos++
		case '-':
			aPos++
		case '+':
			bPos++
		}
	}
	i, j := 0, 0
	for i < n && j < m {
		switch {
		case a[i] == b[j]:
			emit(' ', a[i])
			i++
			j++
		case lcs[i+1][j] >= lcs[i][j+1]:
			emit('-', a[i])
			i++
		default:
			emit('+', b[j])
			j++
		}
	}
	for ; i < n; i++ {
		emit('-', a[i])
	}
	for ; j < m; j++ {
		emit('+', b[j])
	}

	// Group the edits into hunks: consecutive changes separated by more than
	// twice the context lines start a new hunk.
	const context = 3
	var changes []int
	for k, o := range ops {
		if o.kind != ' ' {
			changes = append(changes, k)
		}
	}
	for g := 0; g < len(changes); {
		last := g
		for last+1 < len(changes) && changes[last+1]-changes[last]-1 <= 2*context {
			last++
		}
		lo := max(0, changes[g]-context)
		hi := min(len(ops), changes[last]+1+context)
		// The header numbers are the first line of each side actually shown:
		// the first context, deletion or insertion line.  A hunk that shows
		// no old lines is a pure insertion and reports the position it sits
		// before (0 at the top of the file); the mirror rule holds for a
		// pure deletion.
		aStart := ops[lo].aLine - 1
		bStart := ops[lo].bLine - 1
		countA, countB := 0, 0
		for _, o := range ops[lo:hi] {
			switch o.kind {
			case ' ':
				countA++
				countB++
			case '-':
				countA++
			case '+':
				countB++
			}
		}
		for _, o := range ops[lo:hi] {
			if o.kind != '+' {
				aStart = o.aLine
				break
			}
		}
		for _, o := range ops[lo:hi] {
			if o.kind != '-' {
				bStart = o.bLine
				break
			}
		}
		fmt.Fprintf(&out, "@@ -%d,%d +%d,%d @@\n", aStart, countA, bStart, countB)
		for _, o := range ops[lo:hi] {
			out.WriteByte(o.kind)
			out.WriteString(o.text)
			out.WriteByte('\n')
		}
		g = last + 1
	}
	return out.String()
}