// Package comparer реализует построчно-словесное сравнение двух текстов
// (аналог вкладки Comparer в Burp) на основе классического LCS-алгоритма.
package comparer

import "regexp"

// tokenPattern разбивает текст на чередующиеся куски пробелов и
// непробельных последовательностей — так diff получается на уровне
// "слов" (примерно как режим "Words" в Burp Comparer), но при этом
// исходный текст полностью восстанавливается конкатенацией токенов,
// включая переносы строк и пробелы между ними.
var tokenPattern = regexp.MustCompile(`\s+|\S+`)

func tokenize(s string) []string {
	return tokenPattern.FindAllString(s, -1)
}

// Op — тип операции над токеном при переходе от a к b.
type Op int

const (
	OpEqual Op = iota
	OpDelete
	OpInsert
)

// Chunk — последовательность токенов с одной и той же операцией,
// склеенных в одну строку для компактного вывода.
type Chunk struct {
	Op   Op
	Text string
}

// Diff сравнивает a и b на уровне токенов (слов и пробельных
// промежутков) через LCS и возвращает последовательность чанков:
// OpEqual — совпадающие куски, OpDelete — есть только в a,
// OpInsert — есть только в b.
//
// Сложность O(n·m) по числу токенов в a и b — для вставки HTTP-запросов
// (сотни-тысячи токенов) это доли миллисекунды; для вставки многомегабайтных
// текстов такой алгоритм не годится, но это осознанно не наш случай.
func Diff(a, b string) []Chunk {
	ta := tokenize(a)
	tb := tokenize(b)

	lcs := lcsTable(ta, tb)
	ops := backtrack(lcs, ta, tb, len(ta), len(tb))

	return mergeChunks(ops)
}

type tokenOp struct {
	op   Op
	text string
}

// lcsTable строит стандартную DP-таблицу длин наибольшей общей
// подпоследовательности для токенов ta и tb.
func lcsTable(ta, tb []string) [][]int {
	n, m := len(ta), len(tb)
	table := make([][]int, n+1)
	for i := range table {
		table[i] = make([]int, m+1)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if ta[i-1] == tb[j-1] {
				table[i][j] = table[i-1][j-1] + 1
			} else if table[i-1][j] >= table[i][j-1] {
				table[i][j] = table[i-1][j]
			} else {
				table[i][j] = table[i][j-1]
			}
		}
	}
	return table
}

// backtrack восстанавливает последовательность операций из DP-таблицы,
// двигаясь от (n, m) к (0, 0), и разворачивает её в порядок a→b.
func backtrack(table [][]int, ta, tb []string, i, j int) []tokenOp {
	var reversed []tokenOp
	for i > 0 || j > 0 {
		switch {
		case i > 0 && j > 0 && ta[i-1] == tb[j-1]:
			reversed = append(reversed, tokenOp{OpEqual, ta[i-1]})
			i--
			j--
		case j > 0 && (i == 0 || table[i][j-1] >= table[i-1][j]):
			reversed = append(reversed, tokenOp{OpInsert, tb[j-1]})
			j--
		default:
			reversed = append(reversed, tokenOp{OpDelete, ta[i-1]})
			i--
		}
	}

	ops := make([]tokenOp, len(reversed))
	for k, v := range reversed {
		ops[len(reversed)-1-k] = v
	}
	return ops
}

// mergeChunks склеивает подряд идущие токены с одинаковой операцией
// в один Chunk — иначе на каждое слово приходился бы отдельный чанк,
// что нечитаемо в выводе.
func mergeChunks(ops []tokenOp) []Chunk {
	var chunks []Chunk
	for _, o := range ops {
		if len(chunks) > 0 && chunks[len(chunks)-1].Op == o.op {
			chunks[len(chunks)-1].Text += o.text
			continue
		}
		chunks = append(chunks, Chunk{Op: o.op, Text: o.text})
	}
	return chunks
}