// Package diff compares texts line by line, renders unified diffs, and
// applies them.
package diff

import (
	"fmt"
	"strings"
)

// Kind says what a line of a diff does.
type Kind byte

const (
	Same Kind = ' '
	Del  Kind = '-'
	Add  Kind = '+'
)

// Line is one line of a diff, without its newline.
type Line struct {
	Kind Kind
	Text string
}

// SplitLines splits text into lines without their newlines. A final newline
// does not start another line.
func SplitLines(s string) []string {
	if s == "" {
		return nil
	}
	return strings.Split(strings.TrimSuffix(s, "\n"), "\n")
}

// maxCells bounds the work of the line-matching table; bigger changes are
// shown as replacing everything between the common start and end.
const maxCells = 8_000_000

// Lines diffs a against b.
func Lines(a, b []string) []Line {
	var out []Line
	// The common start and end need no table.
	pre := 0
	for pre < len(a) && pre < len(b) && a[pre] == b[pre] {
		pre++
	}
	suf := 0
	for suf < len(a)-pre && suf < len(b)-pre && a[len(a)-1-suf] == b[len(b)-1-suf] {
		suf++
	}
	for _, l := range a[:pre] {
		out = append(out, Line{Same, l})
	}
	ma, mb := a[pre:len(a)-suf], b[pre:len(b)-suf]
	n, m := len(ma), len(mb)
	if n*m > maxCells {
		for _, l := range ma {
			out = append(out, Line{Del, l})
		}
		for _, l := range mb {
			out = append(out, Line{Add, l})
		}
	} else {
		// lcs[i][j] is the longest common subsequence of ma[i:] and mb[j:].
		lcs := make([][]int32, n+1)
		for i := range lcs {
			lcs[i] = make([]int32, m+1)
		}
		for i := n - 1; i >= 0; i-- {
			for j := m - 1; j >= 0; j-- {
				if ma[i] == mb[j] {
					lcs[i][j] = lcs[i+1][j+1] + 1
				} else {
					lcs[i][j] = max(lcs[i+1][j], lcs[i][j+1])
				}
			}
		}
		i, j := 0, 0
		for i < n || j < m {
			switch {
			case i < n && j < m && ma[i] == mb[j]:
				out = append(out, Line{Same, ma[i]})
				i, j = i+1, j+1
			case i < n && (j == m || lcs[i+1][j] >= lcs[i][j+1]):
				out = append(out, Line{Del, ma[i]})
				i++
			default:
				out = append(out, Line{Add, mb[j]})
				j++
			}
		}
	}
	for _, l := range a[len(a)-suf:] {
		out = append(out, Line{Same, l})
	}
	return out
}

// Hunk is a run of changes with context around it.
type Hunk struct {
	OldStart, NewStart int // 1-based
	Lines              []Line
}

// Hunks groups a diff into hunks with up to context unchanged lines around
// each change; changes closer than that share a hunk.
func Hunks(lines []Line, context int) []Hunk {
	// Mark the lines within context of a change, then cut runs of marked
	// lines into hunks.
	keep := make([]bool, len(lines))
	for i, l := range lines {
		if l.Kind == Same {
			continue
		}
		for k := max(i-context, 0); k <= min(i+context, len(lines)-1); k++ {
			keep[k] = true
		}
	}
	var hunks []Hunk
	oldLine, newLine := 1, 1
	var cur *Hunk
	for i, l := range lines {
		if keep[i] {
			if cur == nil {
				cur = &Hunk{OldStart: oldLine, NewStart: newLine}
			}
			cur.Lines = append(cur.Lines, l)
		} else if cur != nil {
			hunks = append(hunks, *cur)
			cur = nil
		}
		switch l.Kind {
		case Same:
			oldLine++
			newLine++
		case Del:
			oldLine++
		case Add:
			newLine++
		}
	}
	if cur != nil {
		hunks = append(hunks, *cur)
	}
	return hunks
}

// Count returns the lines a hunk covers in the old and new text.
func (h Hunk) Count() (old, new int) {
	for _, l := range h.Lines {
		if l.Kind != Add {
			old++
		}
		if l.Kind != Del {
			new++
		}
	}
	return old, new
}

// splitKeep splits text into lines, each keeping its newline, so a last
// line without one differs from the same line with one.
func splitKeep(s string) []string {
	lines := strings.SplitAfter(s, "\n")
	if lines[len(lines)-1] == "" {
		lines = lines[:len(lines)-1]
	}
	return lines
}

// noNewline marks a line that ends its text without a newline.
const noNewline = "\\ No newline at end of file"

// Unified renders the diff between two texts in unified format, with
// headers naming path; "" if they are the same. A change to the final
// newline shows, as in diff(1).
func Unified(path, a, b string, context int) string {
	hunks := Hunks(Lines(splitKeep(a), splitKeep(b)), context)
	if len(hunks) == 0 {
		return ""
	}
	var sb strings.Builder
	fmt.Fprintf(&sb, "--- %s\n+++ %s\n", path, path)
	for _, h := range hunks {
		o, n := h.Count()
		fmt.Fprintf(&sb, "@@ -%d,%d +%d,%d @@\n", h.OldStart, o, h.NewStart, n)
		for _, l := range h.Lines {
			sb.WriteByte(byte(l.Kind))
			text, nl := strings.CutSuffix(l.Text, "\n")
			sb.WriteString(text)
			sb.WriteByte('\n')
			if !nl {
				sb.WriteString(noNewline + "\n")
			}
		}
	}
	return sb.String()
}

// Stat counts the lines added and removed between two texts.
func Stat(a, b string) (added, removed int) {
	for _, l := range Lines(splitKeep(a), splitKeep(b)) {
		switch l.Kind {
		case Add:
			added++
		case Del:
			removed++
		}
	}
	return added, removed
}