iasysadmin/internal/patch/diff.go

package patch

import (
	"errors"
	"fmt"
	"strings"
)

// Límites de la generación de diffs: por encima, usar "diff -u" del sistema.
const (
	maxDiffLines = 50000
	maxEditDist  = 5000
)

// ErrTooDifferent indica que los archivos difieren demasiado para calcular
// el diff con memoria acotada.
var ErrTooDifferent = errors.New("files are too different to diff efficiently; use exec diff -u")

type opKind byte

const (
	opEqual  opKind = ' '
	opDelete opKind = '-'
	opInsert opKind = '+'
)

type edit struct {
	kind opKind
	text string
	a, b int // índices en old/new (0-based) para calcular cabeceras
}

// Unified genera un diff unificado entre old y new con context líneas de
// contexto. Devuelve "" si son iguales. Sirve para documentar exactamente
// los cambios realizados (§40, §88) y para crear parches propios.
func Unified(oldName, newName, old, new string, context int) (string, error) {
	if old == new {
		return "", nil
	}
	// Las líneas conservan su "\n": así una última línea sin salto final se
	// distingue de la misma línea con salto, y el diff lo refleja.
	a, b := splitKeep(old), splitKeep(new)
	if len(a) > maxDiffLines || len(b) > maxDiffLines {
		return "", ErrTooDifferent
	}
	edits, err := myers(a, b)
	if err != nil {
		return "", err
	}

	var sb strings.Builder
	fmt.Fprintf(&sb, "--- %s\n+++ %s\n", oldName, newName)
	// Agrupar cambios en hunks con contexto.
	for i := 0; i < len(edits); {
		// Buscar el siguiente cambio.
		for i < len(edits) && edits[i].kind == opEqual {
			i++
		}
		if i >= len(edits) {
			break
		}
		start := max(i-context, 0)
		end := i
		// Extender mientras los cambios estén separados por <= 2*context iguales.
		for end < len(edits) {
			if edits[end].kind != opEqual {
				end++
				continue
			}
			run := end
			for run < len(edits) && edits[run].kind == opEqual {
				run++
			}
			if run >= len(edits) || run-end > 2*context {
				end = min(end+context, len(edits))
				break
			}
			end = run
		}
		writeHunk(&sb, edits[start:end])
		i = end
	}
	return sb.String(), nil
}

func writeHunk(sb *strings.Builder, es []edit) {
	oldStart, newStart := -1, -1
	oldN, newN := 0, 0
	for _, e := range es {
		if e.kind != opInsert {
			if oldStart < 0 {
				oldStart = e.a
			}
			oldN++
		}
		if e.kind != opDelete {
			if newStart < 0 {
				newStart = e.b
			}
			newN++
		}
	}
	// Para lados vacíos, la convención es la línea anterior (o 0).
	if oldStart < 0 {
		oldStart = es[0].a - 1
	}
	if newStart < 0 {
		newStart = es[0].b - 1
	}
	fmt.Fprintf(sb, "@@ -%s +%s @@\n", rangeStr(oldStart, oldN), rangeStr(newStart, newN))
	for _, e := range es {
		sb.WriteByte(byte(e.kind))
		sb.WriteString(strings.TrimSuffix(e.text, "\n"))
		sb.WriteByte('\n')
		if !strings.HasSuffix(e.text, "\n") {
			sb.WriteString("\\ No newline at end of file\n")
		}
	}
}

// splitKeep divide en líneas conservando el "\n" de cada una.
func splitKeep(s string) []string {
	if s == "" {
		return nil
	}
	lines := strings.SplitAfter(s, "\n")
	if lines[len(lines)-1] == "" {
		lines = lines[:len(lines)-1]
	}
	return lines
}

func rangeStr(start, n int) string {
	if n == 1 {
		return fmt.Sprint(start + 1)
	}
	if n == 0 {
		return fmt.Sprintf("%d,0", start+1)
	}
	return fmt.Sprintf("%d,%d", start+1, n)
}

// myers calcula el script de edición mínimo (algoritmo de Myers, O((N+M)D)).
// Guarda solo la franja [-d, d] de cada iteración, así la memoria es O(D²).
func myers(a, b []string) ([]edit, error) {
	n, m := len(a), len(b)
	var trace [][]int
	v := map[int]int{1: 0}
	var dFinal int
	found := false
	for d := 0; d <= n+m; d++ {
		if d > maxEditDist {
			return nil, ErrTooDifferent
		}
		snap := make([]int, 2*d+3)
		for k := -d; k <= d; k += 2 {
			var x int
			if k == -d || (k != d && v[k-1] < v[k+1]) {
				x = v[k+1]
			} else {
				x = v[k-1] + 1
			}
			y := x - k
			for x < n && y < m && a[x] == b[y] {
				x++
				y++
			}
			v[k] = x
			if x >= n && y >= m {
				found = true
			}
		}
		for k := -d - 1; k <= d+1; k++ {
			snap[k+d+1] = v[k]
		}
		trace = append(trace, snap)
		if found {
			dFinal = d
			break
		}
	}

	get := func(d, k int) int {
		s := trace[d]
		idx := k + d + 1
		if idx < 0 || idx >= len(s) {
			return 0
		}
		return s[idx]
	}
	var rev []edit
	x, y := n, m
	for d := dFinal; d > 0; d-- {
		k := x - y
		var prevK int
		if k == -d || (k != d && get(d-1, k-1) < get(d-1, k+1)) {
			prevK = k + 1
		} else {
			prevK = k - 1
		}
		prevX := get(d-1, prevK)
		prevY := prevX - prevK
		for x > prevX && y > prevY {
			x--
			y--
			rev = append(rev, edit{kind: opEqual, text: a[x], a: x, b: y})
		}
		if x == prevX {
			y--
			rev = append(rev, edit{kind: opInsert, text: b[y], a: x, b: y})
		} else {
			x--
			rev = append(rev, edit{kind: opDelete, text: a[x], a: x, b: y})
		}
	}
	for x > 0 && y > 0 {
		x--
		y--
		rev = append(rev, edit{kind: opEqual, text: a[x], a: x, b: y})
	}
	out := make([]edit, len(rev))
	for i := range rev {
		out[i] = rev[len(rev)-1-i]
	}
	return out, nil
}