// Package diff turns a unified diff into a structured, renderable
// model: files, hunks, numbered lines, positional syntax tokens, and
// intra-line changed ranges. The factoring is adapted from
// @pierre/diffs' public types (Apache-2.0) — a model that survived two
// wildly different renderers there, which is the evidence it is
// separable from any one markup.
//
// The one idea worth taking above all others: a token is POSITIONAL —
// (column, class, text) — never nested markup. Syntax highlighting and
// intra-line marking both want spans over the same text and do not
// nest; keeping both positional lets the renderer splice them.
package diff
import (
"path/filepath"
"strconv"
"strings"
"sync"
"github.com/alecthomas/chroma/v2"
"github.com/alecthomas/chroma/v2/lexers"
)
type ChangeKind string
const (
Change ChangeKind = "change"
Added ChangeKind = "new"
Deleted ChangeKind = "deleted"
)
// FileDiff is one file's change.
type FileDiff struct {
Path string `json:"path"`
PrevPath string `json:"prevPath,omitempty"`
Change ChangeKind `json:"change"`
Hunks []Hunk `json:"hunks,omitempty"`
// Omitted counts lines Budget cut from this file. Hunks holds what
// was kept; a reader follows up with a single-file diff.
Omitted int `json:"omitted,omitempty"`
}
// Hunk is one @@ region.
type Hunk struct {
OldStart int `json:"oldStart"`
NewStart int `json:"newStart"`
Header string `json:"header,omitempty"` // text after the second @@
Lines []Line `json:"lines"`
}
// Line is one row of a hunk. A side with no number carries 0.
type Line struct {
Kind string `json:"kind"` // context | addition | deletion
OldNum int `json:"oldNum,omitempty"`
NewNum int `json:"newNum,omitempty"`
Tokens []Token `json:"tokens"`
}
// Token is one positional run of text: one syntax class, one change
// state. Mark is true inside an intra-line changed range.
type Token struct {
Class string `json:"class,omitempty"` // chroma short class ("k", "s", …), "" for plain
Text string `json:"text"`
Mark bool `json:"mark,omitempty"`
}
// Parse structures a unified diff. filename chooses the chroma lexer
// (per file header when the diff carries them); an unknown language
// still gets structure, numbers and marks — just plain tokens.
func Parse(unified string) []FileDiff {
var files []FileDiff
var cur *FileDiff
var hunk *Hunk
var oldN, newN int
// remOld/remNew count the hunk lines its @@ header promised. While
// either is positive, +/-/space lines are hunk CONTENT even when
// they look like file headers — a deleted line whose text begins
// "-- " prints as "---…" in unified, and prefix-matching alone
// misread it as the next file (found by the corpus sweep on sqlite,
// where SQL comment lines begin exactly that way).
var remOld, remNew int
flush := func() {
if cur != nil && hunk != nil {
cur.Hunks = append(cur.Hunks, *hunk)
hunk = nil
}
}
lines := strings.Split(strings.TrimSuffix(unified, "\n"), "\n")
for i := 0; i < len(lines); i++ {
line := lines[i]
inHunk := hunk != nil && (remOld > 0 || remNew > 0)
switch {
case !inHunk && strings.HasPrefix(line, "--- "):
flush()
if cur != nil {
files = append(files, *cur)
}
cur = &FileDiff{Change: Change, PrevPath: cleanPath(line[4:])}
case !inHunk && strings.HasPrefix(line, "+++ "):
if cur == nil {
cur = &FileDiff{Change: Change}
}
cur.Path = cleanPath(line[4:])
switch {
case cur.PrevPath == "/dev/null":
cur.Change, cur.PrevPath = Added, ""
case cur.Path == "/dev/null":
cur.Change, cur.Path, cur.PrevPath = Deleted, cur.PrevPath, ""
case cur.PrevPath == cur.Path:
cur.PrevPath = ""
}
case !inHunk && strings.HasPrefix(line, "@@"):
flush()
h := Hunk{}
var oc, nc int
h.OldStart, oc, h.NewStart, nc, h.Header = parseHunkHeader(line)
oldN, newN = h.OldStart, h.NewStart
remOld, remNew = oc, nc
hunk = &h
case inHunk && strings.HasPrefix(line, "+"):
hunk.Lines = append(hunk.Lines, Line{Kind: "addition", NewNum: newN,
Tokens: []Token{{Text: line[1:]}}})
newN++
remNew--
case inHunk && strings.HasPrefix(line, "-"):
hunk.Lines = append(hunk.Lines, Line{Kind: "deletion", OldNum: oldN,
Tokens: []Token{{Text: line[1:]}}})
oldN++
remOld--
case inHunk && strings.HasPrefix(line, " "):
hunk.Lines = append(hunk.Lines, Line{Kind: "context", OldNum: oldN, NewNum: newN,
Tokens: []Token{{Text: line[1:]}}})
oldN++
newN++
remOld--
remNew--
case hunk != nil && line == `\ No newline at end of file`:
// metadata; drop — the absence is not a change a reader acts on
default:
// Index:/=== chrome between files; ignore.
}
}
flush()
if cur != nil {
files = append(files, *cur)
}
return files
}
func cleanPath(s string) string {
s = strings.TrimSpace(s)
if i := strings.IndexByte(s, '\t'); i >= 0 {
s = s[:i] // strip the timestamp some diffs carry
}
s = strings.TrimPrefix(s, "a/")
s = strings.TrimPrefix(s, "b/")
return s
}
func parseHunkHeader(line string) (oldStart, oldCount, newStart, newCount int, header string) {
oldCount, newCount = 1, 1 // a bare "-N" means one line
rest := strings.TrimPrefix(line, "@@")
if i := strings.Index(rest, "@@"); i >= 0 {
header = strings.TrimSpace(rest[i+2:])
rest = rest[:i]
}
for _, f := range strings.Fields(rest) {
n := strings.TrimLeft(f, "-+")
count := -1
if c := strings.IndexByte(n, ','); c >= 0 {
count, _ = strconv.Atoi(n[c+1:])
n = n[:c]
}
v, _ := strconv.Atoi(n)
if strings.HasPrefix(f, "-") {
oldStart = v
if count >= 0 {
oldCount = count
}
} else if strings.HasPrefix(f, "+") {
newStart = v
if count >= 0 {
newCount = count
}
}
}
return
}
// Enrich adds intra-line marks and syntax tokens in place. filename
// picks the lexer; empty or unknown leaves tokens plain.
func Enrich(files []FileDiff) {
for fi := range files {
if len(files[fi].Hunks) == 0 {
continue // nothing to mark, and a lexer lookup is ~2ms
}
lexer := lexerFor(files[fi].Path)
for hi := range files[fi].Hunks {
markHunk(&files[fi].Hunks[hi])
if lexer != nil {
for li := range files[fi].Hunks[hi].Lines {
tokenize(&files[fi].Hunks[hi].Lines[li], lexer)
}
}
}
}
}
// Budget keeps at most maxLines diff lines across files, in order, and
// drops the rest: a 600-file merge is not something a reader scrolls,
// and enriching and rendering it took twenty seconds. Dropped hunks
// are counted in each file's Omitted so the page can say so and link
// to the single-file view. maxLines <= 0 keeps everything. Returns the
// number of lines omitted in total.
func Budget(files []FileDiff, maxLines int) (omitted int) {
if maxLines <= 0 {
return 0
}
left := maxLines
for fi := range files {
f := &files[fi]
keep := 0
for _, h := range f.Hunks {
if left < len(h.Lines) {
break
}
left -= len(h.Lines)
keep++
}
for _, h := range f.Hunks[keep:] {
f.Omitted += len(h.Lines)
}
f.Hunks = f.Hunks[:keep]
omitted += f.Omitted
}
return omitted
}
// lexerFor memoises lexers.Match by base name: chroma tests the name
// against every registered lexer's globs, which was a second of a
// 600-file diff on its own. Coalesce is folded in for the same reason
// — it was rebuilt per line.
func lexerFor(path string) chroma.Lexer {
base := filepath.Base(path)
lexerMu.Lock()
defer lexerMu.Unlock()
if l, ok := lexerCache[base]; ok {
return l
}
var l chroma.Lexer
if m := lexers.Match(base); m != nil {
l = chroma.Coalesce(m)
}
lexerCache[base] = l
return l
}
var (
lexerMu sync.Mutex
lexerCache = map[string]chroma.Lexer{}
)
// markHunk pairs each deletion run with the addition run that follows
// it (index-aligned) and marks the changed ranges word-diff-wise.
func markHunk(h *Hunk) {
i := 0
for i < len(h.Lines) {
if h.Lines[i].Kind != "deletion" {
i++
continue
}
ds := i
for i < len(h.Lines) && h.Lines[i].Kind == "deletion" {
i++
}
as := i
for i < len(h.Lines) && h.Lines[i].Kind == "addition" {
i++
}
n := min(i-as, as-ds)
for k := 0; k < n; k++ {
d, a := &h.Lines[ds+k], &h.Lines[as+k]
dr, ar := wordDiff(d.Tokens[0].Text, a.Tokens[0].Text)
d.Tokens = applyMarks(d.Tokens[0].Text, dr)
a.Tokens = applyMarks(a.Tokens[0].Text, ar)
}
}
}
// span is a half-open byte range.
type span struct{ from, to int }
// wordDiff computes the changed byte ranges of two lines by an LCS
// over word tokens. Lines are short; O(n²) here beats a dependency.
// When the lines share almost nothing, mark NOTHING rather than
// everything: a fully-marked pair says less than plain colour.
func wordDiff(a, b string) (aSpans, bSpans []span) {
aw, bw := words(a), words(b)
la, lb := len(aw), len(bw)
if la == 0 || lb == 0 || la*lb > 10000 {
return nil, nil
}
dp := make([][]int, la+1)
for i := range dp {
dp[i] = make([]int, lb+1)
}
for i := la - 1; i >= 0; i-- {
for j := lb - 1; j >= 0; j-- {
if aw[i].text == bw[j].text {
dp[i][j] = dp[i+1][j+1] + 1
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j+1])
}
}
}
common := dp[0][0]
// Shared-little guard: if under a third of the shorter side
// survives, the lines are rewrites, not edits.
if common*3 < min(la, lb) {
return nil, nil
}
i, j := 0, 0
for i < la && j < lb {
switch {
case aw[i].text == bw[j].text:
i++
j++
case dp[i+1][j] >= dp[i][j+1]:
aSpans = appendSpan(aSpans, aw[i].from, aw[i].to)
i++
default:
bSpans = appendSpan(bSpans, bw[j].from, bw[j].to)
j++
}
}
for ; i < la; i++ {
aSpans = appendSpan(aSpans, aw[i].from, aw[i].to)
}
for ; j < lb; j++ {
bSpans = appendSpan(bSpans, bw[j].from, bw[j].to)
}
return
}
type word struct {
text string
from, to int
}
// words splits into runs of letters/digits and runs of everything
// else, so punctuation edits mark punctuation, not the word beside it.
func words(s string) []word {
var out []word
start := 0
kind := -1
classify := func(r byte) int {
switch {
case r == ' ' || r == '\t':
return 0
case (r >= 'a' && r <= 'z') || (r >= 'A' && r <= 'Z') || (r >= '0' && r <= '9') || r == '_' || r >= 0x80:
return 1
default:
return 2
}
}
for i := 0; i < len(s); i++ {
k := classify(s[i])
if k != kind {
if kind > 0 {
out = append(out, word{s[start:i], start, i})
}
start, kind = i, k
}
}
if kind > 0 {
out = append(out, word{s[start:], start, len(s)})
}
return out
}
func appendSpan(spans []span, from, to int) []span {
if n := len(spans); n > 0 && spans[n-1].to >= from-1 {
spans[n-1].to = to // merge adjacent/overlapping
return spans
}
return append(spans, span{from, to})
}
// applyMarks rebuilds a line's tokens as plain text split at mark
// boundaries.
func applyMarks(text string, spans []span) []Token {
if len(spans) == 0 {
return []Token{{Text: text}}
}
var out []Token
pos := 0
for _, sp := range spans {
if sp.from > pos {
out = append(out, Token{Text: text[pos:sp.from]})
}
out = append(out, Token{Text: text[sp.from:sp.to], Mark: true})
pos = sp.to
}
if pos < len(text) {
out = append(out, Token{Text: text[pos:]})
}
return out
}
// tokenize splits a line's tokens further by chroma class, preserving
// marks: every emitted token carries exactly one syntax class and one
// change state. Chroma sees the line alone, which loses multi-line
// constructs (a string spanning lines); that is the price of not
// having the whole file, and it degrades to plain, never to wrong
// text.
func tokenize(l *Line, lexer chroma.Lexer) {
var full strings.Builder
for _, t := range l.Tokens {
full.WriteString(t.Text)
}
it, err := lexer.Tokenise(nil, full.String())
if err != nil {
return
}
// Positional class map over the line.
type classRun struct {
from, to int
class string
}
var runs []classRun
pos := 0
for _, ct := range it.Tokens() {
n := len(ct.Value)
class := chroma.StandardTypes[ct.Type]
// Per-line tokenization cannot see multi-line constructs: a raw
// string spanning lines leaves an unclosed quote on every line
// inside it, and chroma answers with Error tokens — which the
// stylesheet paints as red warning boxes over perfectly healthy
// code. An error TOKEN is a lexer's shrug, not a defect in the
// file; it renders plain.
if ct.Type.InCategory(chroma.Error) || class == "err" {
class = ""
}
runs = append(runs, classRun{pos, pos + n, class})
pos += n
}
// Splice: walk the mark tokens and the class runs together.
var out []Token
pos = 0
ri := 0
for _, t := range l.Tokens {
end := pos + len(t.Text)
for pos < end {
for ri < len(runs) && runs[ri].to <= pos {
ri++
}
to := end
class := ""
if ri < len(runs) {
class = runs[ri].class
if runs[ri].to < to {
to = runs[ri].to
}
}
full := full.String()
out = append(out, Token{Class: class, Text: full[pos:to], Mark: t.Mark})
pos = to
}
}
l.Tokens = out
}