package fileedit

import (
	"fmt"
	"strings"
)

// op is what happened to a line. The values are the characters of the unified
// format, which saves a conversion table.
type op byte

const (
	keep op = ' '
	del  op = '-'
	add  op = '+'
)

// line is one line of the diff. oldNo and newNo are 1-based, 0 when the line
// does not exist on that side.
type line struct {
	op    op
	text  string
	oldNo int
	newNo int
}

// comparison is a diff ready to render: the lines, and what splitting into
// lines cannot say — whether each side ended with a newline. Two files that
// differ only there are two different files, and `git apply` refuses a patch
// that ignores it.
type comparison struct {
	lines        []line
	oldNL, newNL bool
}

// compare splits, compares, and returns what is needed to display and to patch.
func compare(old, new string) comparison {
	oldLines, oldNL := splitLines(old)
	newLines, newNL := splitLines(new)
	r := comparison{lines: diffLines(oldLines, newLines), oldNL: oldNL, newNL: newNL}

	// Edge case: identical line by line, only the final newline moved. Nothing
	// is marked changed and the patch would be empty while the file changes.
	// The last line is replayed — deleted then added — which is exactly what
	// `git diff` prints.
	if oldNL != newNL && !changed(r.lines) && len(r.lines) > 0 {
		last := r.lines[len(r.lines)-1]
		r.lines = append(r.lines[:len(r.lines)-1],
			line{del, last.text, last.oldNo, 0},
			line{add, last.text, 0, last.newNo},
		)
	}
	return r
}

func (r comparison) changed() bool { return changed(r.lines) }

// firstChanged is the number, in the NEW version, of the first touched line —
// 0 when nothing changed. Enough to open the file at the right place, or to
// say "it starts at line 42" rather than "done".
func (r comparison) firstChanged() int {
	for _, l := range r.lines {
		switch l.op {
		case add:
			return l.newNo
		case del:
			// A deletion has no line in the new version: point at where it
			// happened.
			return max(1, newNoBefore(r.lines, l))
		}
	}
	return 0
}

func (r comparison) stat() (added, deleted int) {
	for _, l := range r.lines {
		switch l.op {
		case add:
			added++
		case del:
			deleted++
		}
	}
	return added, deleted
}

// splitLines splits a body into lines and says whether it ended with a
// newline. Both matter: a file without a final newline is a different file,
// and the unified patch has to say so.
func splitLines(body string) (lines []string, finalNewline bool) {
	if body == "" {
		return nil, true
	}
	finalNewline = strings.HasSuffix(body, "\n")
	if finalNewline {
		body = body[:len(body)-1]
	}
	return strings.Split(body, "\n"), finalNewline
}

// maxCells caps the LCS table. Past it, a line-by-line comparison would cost
// hundreds of megabytes for a diff nobody will read: the middle block is then
// rendered as a block (all deleted, all added), still exact — only coarser.
const maxCells = 4 << 20

// diffLines compares two sequences of lines.
//
// Common prefix and suffix are removed BEFORE the LCS: a targeted edit touches
// a few lines in the middle of a file, and without that cut the table would be
// the size of the file squared.
func diffLines(old, new []string) []line {
	var out []line

	head := 0
	for head < len(old) && head < len(new) && old[head] == new[head] {
		out = append(out, line{keep, old[head], head + 1, head + 1})
		head++
	}
	tail := 0
	for tail < len(old)-head && tail < len(new)-head &&
		old[len(old)-1-tail] == new[len(new)-1-tail] {
		tail++
	}

	midOld, midNew := old[head:len(old)-tail], new[head:len(new)-tail]
	out = append(out, middle(midOld, midNew, head)...)

	for i := len(old) - tail; i < len(old); i++ {
		out = append(out, line{keep, old[i], i + 1, i + 1 - len(old) + len(new)})
	}
	return out
}

// middle compares what remains after trimming the edges. `off` is the number
// of lines already consumed, to number correctly.
func middle(old, new []string, off int) []line {
	if len(old) == 0 && len(new) == 0 {
		return nil
	}
	if len(old)*len(new) > maxCells {
		out := make([]line, 0, len(old)+len(new))
		for i, l := range old {
			out = append(out, line{del, l, off + i + 1, 0})
		}
		for j, l := range new {
			out = append(out, line{add, l, 0, off + j + 1})
		}
		return out
	}

	// Classic LCS: length table, then walk. Files edited by an agent fit in it
	// comfortably.
	lcs := make([][]int, len(old)+1)
	for i := range lcs {
		lcs[i] = make([]int, len(new)+1)
	}
	for i := len(old) - 1; i >= 0; i-- {
		for j := len(new) - 1; j >= 0; j-- {
			if old[i] == new[j] {
				lcs[i][j] = lcs[i+1][j+1] + 1
			} else {
				lcs[i][j] = max(lcs[i+1][j], lcs[i][j+1])
			}
		}
	}

	var out []line
	i, j := 0, 0
	for i < len(old) && j < len(new) {
		switch {
		case old[i] == new[j]:
			out = append(out, line{keep, old[i], off + i + 1, off + j + 1})
			i, j = i+1, j+1
		case lcs[i+1][j] >= lcs[i][j+1]:
			// Deletion first on a tie: a replacement then reads "- old" then
			// "+ new", the order one expects.
			out = append(out, line{del, old[i], off + i + 1, 0})
			i++
		default:
			out = append(out, line{add, new[j], 0, off + j + 1})
			j++
		}
	}
	for ; i < len(old); i++ {
		out = append(out, line{del, old[i], off + i + 1, 0})
	}
	for ; j < len(new); j++ {
		out = append(out, line{add, new[j], 0, off + j + 1})
	}
	return out
}

// newNoBefore finds the number of the kept line that precedes `target`.
func newNoBefore(lines []line, target line) int {
	last := 0
	for _, l := range lines {
		if l == target {
			break
		}
		if l.newNo > 0 {
			last = l.newNo
		}
	}
	return last + 1
}

func changed(lines []line) bool {
	for _, l := range lines {
		if l.op != keep {
			return true
		}
	}
	return false
}

// noNewline is the line the unified format requires when a file does not end
// with a newline. `git apply` reads it; without it, it adds a newline nobody
// asked for.
const noNewline = `\ No newline at end of file`

// contextLines is how many unchanged lines are kept around each change. Three
// is the value of `diff -u` and of git.
const contextLines = 3

// unified renders a unified patch, applicable as-is by `patch -p1` or
// `git apply`. Paths are prefixed a/ and b/ like git does.
func (r comparison) unified(path string) string {
	if !changed(r.lines) {
		return ""
	}
	var b strings.Builder
	fmt.Fprintf(&b, "--- a/%s\n+++ b/%s\n", path, path)

	lastOld, lastNew := 0, 0
	for _, l := range r.lines {
		lastOld, lastNew = max(lastOld, l.oldNo), max(lastNew, l.newNo)
	}
	for _, h := range hunks(r.lines) {
		oldStart, oldCount, newStart, newCount := h.ranges()
		fmt.Fprintf(&b, "@@ -%d,%d +%d,%d @@\n", oldStart, oldCount, newStart, newCount)
		for _, l := range h {
			b.WriteByte(byte(l.op))
			b.WriteString(l.text)
			b.WriteByte('\n')
			// The marker follows the LAST line of each version, and a kept
			// line belongs to both: it may carry it for both at once.
			if (!r.oldNL && l.oldNo == lastOld && l.op != add) ||
				(!r.newNL && l.newNo == lastNew && l.op != del) {
				b.WriteString(noNewline + "\n")
			}
		}
	}
	return b.String()
}

// hunk is a group of contiguous lines shown together.
type hunk []line

// hunks cuts the diff into pieces: each change plus `contextLines` on both
// sides. Touching pieces are merged — otherwise two neighbouring changes would
// produce overlapping @@ headers, and the patch would be refused.
func hunks(lines []line) []hunk {
	var out []hunk
	i := 0
	for i < len(lines) {
		if lines[i].op == keep {
			i++
			continue
		}
		start := max(0, i-contextLines)
		if n := len(out); n > 0 {
			if prevEnd := indexAfter(lines, out[n-1]); prevEnd >= start {
				out[n-1] = append(out[n-1], lines[prevEnd:hunkEnd(lines, i)]...)
				i = hunkEnd(lines, i)
				continue
			}
		}
		out = append(out, append(hunk(nil), lines[start:hunkEnd(lines, i)]...))
		i = hunkEnd(lines, i)
	}
	return out
}

// hunkEnd finds the end of the piece opened at `i`: advance while a change
// occurs within `contextLines` lines, then keep the trailing context.
func hunkEnd(lines []line, i int) int {
	last := i
	for j := i; j < len(lines); j++ {
		if lines[j].op != keep {
			last = j
			continue
		}
		if j-last > contextLines {
			break
		}
	}
	return min(len(lines), last+contextLines+1)
}

// indexAfter returns the position, in `lines`, of the line following the last
// element of `h`.
func indexAfter(lines []line, h hunk) int {
	if len(h) == 0 {
		return 0
	}
	target := h[len(h)-1]
	for i, l := range lines {
		if l == target {
			return i + 1
		}
	}
	return 0
}

// ranges computes the @@ header of the piece.
func (h hunk) ranges() (oldStart, oldCount, newStart, newCount int) {
	for _, l := range h {
		if l.op != add {
			if oldStart == 0 {
				oldStart = l.oldNo
			}
			oldCount++
		}
		if l.op != del {
			if newStart == 0 {
				newStart = l.newNo
			}
			newCount++
		}
	}
	if oldCount == 0 {
		oldStart = 0
	}
	if newCount == 0 {
		newStart = 0
	}
	return oldStart, oldCount, newStart, newCount
}

// render formats the diff for the screen and for the model: a line number, a
// sign, the text. No colours here at all — the same text goes back to the
// model, and ANSI codes in a tool result only get in its way; the screen gets
// its grey from the caller's preview mechanism.
//
// The number shown is ALWAYS the new version's: the one to look at after the
// edit. A deleted line no longer exists there, so it gets the number of the
// place where it vanished — a replacement shows "-" and "+" on the SAME number
// and the column never goes backwards.
func (r comparison) render() string {
	if !changed(r.lines) {
		return ""
	}
	var b strings.Builder
	for _, h := range hunks(r.lines) {
		current := 0
		for _, l := range h {
			no := l.newNo
			if no > 0 {
				current = no
			} else {
				no = current + 1
			}
			fmt.Fprintf(&b, "%4d %c %s\n", no, l.op, l.text)
		}
	}
	return b.String()
}