PgTidy/cmd/pgtidy/diff.go

package main

import (
	"fmt"
	"strings"
)

const diffContext = 3

// unifiedDiff returns a unified diff between original and formatted. The path
// argument is used in the diff header. Returns "" when the strings are equal.
func unifiedDiff(original, formatted, path string) string {
	a := splitAfterNewline(original)
	b := splitAfterNewline(formatted)

	ops := editScript(a, b)
	if len(ops) == 0 {
		return ""
	}

	// Locate hunk ranges: groups of changed lines expanded by diffContext.
	type hunk struct{ lo, hi int }
	var hunks []hunk
	for k, op := range ops {
		if op == ' ' {
			continue
		}
		lo := k - diffContext
		if lo < 0 {
			lo = 0
		}
		hi := k + diffContext + 1
		if hi > len(ops) {
			hi = len(ops)
		}
		if len(hunks) > 0 && lo <= hunks[len(hunks)-1].hi {
			if hi > hunks[len(hunks)-1].hi {
				hunks[len(hunks)-1].hi = hi
			}
		} else {
			hunks = append(hunks, hunk{lo, hi})
		}
	}

	if len(hunks) == 0 {
		return ""
	}

	// Reconstitute lines for each op: '+' takes from b, '-' from a, ' ' from a.
	aIdx, bIdx := 0, 0
	type opLine struct {
		op   byte
		text string
	}
	lines := make([]opLine, len(ops))
	for k, op := range ops {
		switch op {
		case '+':
			lines[k] = opLine{'+', b[bIdx]}
			bIdx++
		case '-':
			lines[k] = opLine{'-', a[aIdx]}
			aIdx++
		default:
			lines[k] = opLine{' ', a[aIdx]}
			aIdx++
			bIdx++
		}
	}

	var sb strings.Builder
	fmt.Fprintf(&sb, "--- a/%s\n+++ b/%s\n", path, path)

	for _, h := range hunks {
		// Count original and formatted line numbers.
		aStart, bStart := 1, 1
		for k := 0; k < h.lo; k++ {
			if lines[k].op != '+' {
				aStart++
			}
			if lines[k].op != '-' {
				bStart++
			}
		}
		aCount, bCount := 0, 0
		for k := h.lo; k < h.hi; k++ {
			if lines[k].op != '+' {
				aCount++
			}
			if lines[k].op != '-' {
				bCount++
			}
		}
		fmt.Fprintf(&sb, "@@ -%d,%d +%d,%d @@\n", aStart, aCount, bStart, bCount)
		for k := h.lo; k < h.hi; k++ {
			sb.WriteByte(lines[k].op)
			sb.WriteString(lines[k].text)
			if !strings.HasSuffix(lines[k].text, "\n") {
				sb.WriteString("\n\\ No newline at end of file\n")
			}
		}
	}

	return sb.String()
}

// editScript computes the shortest edit script between a and b as a sequence
// of ops: ' ' (keep), '+' (insert from b), '-' (delete from a).
// Uses an O(m*n) LCS-based approach — suitable for typical SQL file sizes.
func editScript(a, b []string) []byte {
	m, n := len(a), len(b)
	// dp[i][j] = LCS length of a[i:] and b[j:]
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if a[i] == b[j] {
				dp[i][j] = dp[i+1][j+1] + 1
			} else if dp[i+1][j] >= dp[i][j+1] {
				dp[i][j] = dp[i+1][j]
			} else {
				dp[i][j] = dp[i][j+1]
			}
		}
	}

	var ops []byte
	i, j := 0, 0
	for i < m || j < n {
		switch {
		case i < m && j < n && a[i] == b[j]:
			ops = append(ops, ' ')
			i++
			j++
		case j < n && (i >= m || dp[i][j+1] >= dp[i+1][j]):
			ops = append(ops, '+')
			j++
		default:
			ops = append(ops, '-')
			i++
		}
	}
	return ops
}

// splitAfterNewline splits s into lines keeping the trailing newline on each
// line, so that joining the result reconstructs the original string exactly.
func splitAfterNewline(s string) []string {
	return strings.SplitAfter(s, "\n")
}