// 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 (
"strconv"
"strings"
"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"`
}
// 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
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]
switch {
case strings.HasPrefix(line, "--- "):
flush()
if cur != nil {
files = append(files, *cur)
}
cur = &FileDiff{Change: Change, PrevPath: cleanPath(line[4:])}
case 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 strings.HasPrefix(line, "@@"):
flush()
h := Hunk{}
h.OldStart, h.NewStart, h.Header = parseHunkHeader(line)
oldN, newN = h.OldStart, h.NewStart
hunk = &h
case hunk != nil && strings.HasPrefix(line, "+"):
hunk.Lines = append(hunk.Lines, Line{Kind: "addition", NewNum: newN,
Tokens: []Token{{Text: line[1:]}}})
newN++
case hunk != nil && strings.HasPrefix(line, "-"):
hunk.Lines = append(hunk.Lines, Line{Kind: "deletion", OldNum: oldN,
Tokens: []Token{{Text: line[1:]}}})
oldN++
case hunk != nil && strings.HasPrefix(line, " "):
hunk.Lines = append(hunk.Lines, Line{Kind: "context", OldNum: oldN, NewNum: newN,
Tokens: []Token{{Text: line[1:]}}})
oldN++
newN++
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, newStart int, header string) {
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, "-+")
if c := strings.IndexByte(n, ','); c >= 0 {
n = n[:c]
}
v, _ := strconv.Atoi(n)
if strings.HasPrefix(f, "-") {
oldStart = v
} else if strings.HasPrefix(f, "+") {
newStart = v
}
}
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 {
lexer := lexers.Match(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)
}
}
}
}
}
// 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 := chroma.Coalesce(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
}