pve-confsync/internal/nodesync/diff.go

package nodesync

import (
	"strconv"
	"strings"
)

// Line is one line of a unified diff: Op is ' ' (context), '-' (target only)
// or '+' (written by the replication). A hunk starts with Op '@' and Text
// "@@ -a,b +c,d @@".
type Line struct {
	Op   string `json:"op"`
	Text string `json:"text"`
}

const diffContext = 3

// maxCells bounds the LCS table; beyond, the diff shows every line replaced.
const maxCells = 4_000_000

// Diff compares the current content of a file with the content to write.
func Diff(oldText, newText []byte) []Line {
	a, b := lines(oldText), lines(newText)
	ops := editScript(a, b)
	// group the changes into hunks with their context
	var out []Line
	n := len(ops)
	i := 0
	for i < n {
		if ops[i].Op == " " {
			i++
			continue
		}
		start := i - diffContext
		if start < 0 {
			start = 0
		}
		end := i
		for end < n {
			if ops[end].Op != " " {
				end++
				continue
			}
			// a run of context: the hunk ends when it is longer than 2*context
			j := end
			for j < n && ops[j].Op == " " {
				j++
			}
			if j == n || j-end > 2*diffContext {
				end += diffContext
				if end > n {
					end = n
				}
				break
			}
			end = j
		}
		oa, ob := ops[start].A, ops[start].B
		ca, cb := 0, 0
		for _, o := range ops[start:end] {
			if o.Op != "+" {
				ca++
			}
			if o.Op != "-" {
				cb++
			}
		}
		out = append(out, Line{Op: "@", Text: hunkHeader(oa, ca, ob, cb)})
		for _, o := range ops[start:end] {
			out = append(out, Line{Op: o.Op, Text: o.Text})
		}
		i = end
	}
	return out
}

type editOp struct {
	Op   string
	Text string
	A, B int // line numbers (1-based) where this op starts in a and b
}

func editScript(a, b []string) []editOp {
	var ops []editOp
	if len(a)*len(b) > maxCells {
		for i, l := range a {
			ops = append(ops, editOp{"-", l, i + 1, 1})
		}
		for i, l := range b {
			ops = append(ops, editOp{"+", l, len(a) + 1, i + 1})
		}
		return ops
	}
	// lcs[i][j]: length of the LCS of a[i:] and b[j:]
	lcs := make([][]int, len(a)+1)
	for i := range lcs {
		lcs[i] = make([]int, len(b)+1)
	}
	for i := len(a) - 1; i >= 0; i-- {
		for j := len(b) - 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]
			}
		}
	}
	i, j := 0, 0
	for i < len(a) || j < len(b) {
		switch {
		case i < len(a) && j < len(b) && a[i] == b[j]:
			ops = append(ops, editOp{" ", a[i], i + 1, j + 1})
			i++
			j++
		case j < len(b) && (i == len(a) || lcs[i][j+1] > lcs[i+1][j]):
			ops = append(ops, editOp{"+", b[j], i + 1, j + 1})
			j++
		default:
			ops = append(ops, editOp{"-", a[i], i + 1, j + 1})
			i++
		}
	}
	return ops
}

func lines(b []byte) []string {
	s := string(b)
	if s == "" {
		return nil
	}
	s = strings.TrimSuffix(s, "\n")
	return strings.Split(s, "\n")
}

func hunkHeader(a, ca, b, cb int) string {
	r := func(start, n int) string {
		if n == 0 {
			start--
		}
		if n == 1 {
			return strconv.Itoa(start)
		}
		return strconv.Itoa(start) + "," + strconv.Itoa(n)
	}
	return "@@ -" + r(a, ca) + " +" + r(b, cb) + " @@"
}