Skip to content
quarry Artifact [6acc63d1b7]
Login

Artifact [6acc63d1b7]

Check-ins Using Download Hex

Artifact 6acc63d1b797eb1adeeef727e608f746698c4a8c33aa6926def94ea25ca2442f:

// 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"`
	// Added and Deleted are the WHOLE file's changed-line counts,
	// tallied while parsing. Counting the rendered hunks instead would
	// report the window rather than the file, so a long diff read page
	// by page would show a different total on every page.
	Added   int `json:"added,omitempty"`
	Deleted int `json:"deleted,omitempty"`
	// Window bookkeeping: Before counts this file's lines that fall
	// before the window (the file continues from an earlier chunk),
	// Omitted those after it (more chunks follow). Hunks is the window.
	Before  int `json:"before,omitempty"`
	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:]}}})
			if cur != nil {
				cur.Added++
			}
			newN++
			remNew--
		case inHunk && strings.HasPrefix(line, "-"):
			hunk.Lines = append(hunk.Lines, Line{Kind: "deletion", OldNum: oldN,
				Tokens: []Token{{Text: line[1:]}}})
			if cur != nil {
				cur.Deleted++
			}
			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)
				}
			}
		}
	}
}

// Window keeps the diff lines in [offset, offset+maxLines) — whole
// hunks, in order, so a chunk never splits one — and drops the rest.
// A 600-file merge is not something a reader scrolls in one go, and
// enriching and rendering all of it took twenty seconds; the page
// shows one window and fetches the next as the reader reaches it.
// Lines cut before and after the window are counted per file (Before,
// Omitted). A hunk longer than maxLines is kept whole when it opens
// the window, so progress is always made. maxLines <= 0 keeps
// everything from offset on. Returns where the window actually starts
// — offset snapped back to the boundary of the hunk containing it, so
// an arbitrary offset still yields whole hunks and honest counts —
// the lines kept, and the lines remaining after the window.
func Window(files []FileDiff, offset, maxLines int) (start, kept, after int) {
	pos, full, started := 0, false, false
	for fi := range files {
		f := &files[fi]
		var win []Hunk
		for _, h := range f.Hunks {
			n := len(h.Lines)
			switch {
			case pos+n <= offset:
				f.Before += n
			case full || (maxLines > 0 && kept > 0 && kept+n > maxLines):
				// Once the window is full every later hunk is after
				// it, however small: a window is a contiguous run, so
				// "next" continues exactly where this one stopped.
				full = true
				f.Omitted += n
				after += n
			default:
				if !started {
					start, started = pos, true
				}
				win = append(win, h)
				kept += n
			}
			pos += n
		}
		f.Hunks = win
	}
	if !started {
		start = pos
	}
	return start, kept, after
}

// LastWindow is the offset at which the final window of the greedy
// chunking from 0 begins — the same chain a reader following "next"
// walks, so "last" lands where "next" eventually would. Call it before
// Window, which trims the hunks it counts.
func LastWindow(files []FileDiff, maxLines int) int {
	if maxLines <= 0 {
		return 0
	}
	start, kept, pos := 0, 0, 0
	for _, f := range files {
		for _, h := range f.Hunks {
			n := len(h.Lines)
			if kept > 0 && kept+n > maxLines {
				start, kept = pos, 0
			}
			kept += n
			pos += n
		}
	}
	return start
}

// 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
}