/**
 * Recovers stale section tags by proving that every anchored line still maps
 * to one unchanged, contiguous region in the current file, then replaying the
 * edit against that live content.
 *
 * Recovery fails closed when the target changed or became ambiguous. The
 * patcher then returns a mismatch with fresh context instead of guessing.
 *
 * Note: upstream (omp) computes the line diff via the native
 * `@oh-my-pi/pi-natives` bindings; this fork inlines a pure-TS LCS diff so
 * the package loads on any runtime (pi loads extensions under node).
 */
import { applyEdits } from "./apply";
import { RECOVERY_EXTERNAL_WARNING, RECOVERY_LINE_REMAP_WARNING, RECOVERY_SESSION_CHAIN_WARNING } from "./messages";
import type { SnapshotStore } from "./snapshots";
import type { Anchor, ApplyResult, Clipboard, Edit } from "./types";

export interface RecoveryArgs {
	path: string;
	currentText: string;
	fileHash: string;
	edits: readonly Edit[];
	/** Shared clipboard register for `cut`/`paste` edits, threaded into the replay apply. */
	clipboard?: Clipboard;
}

/** 行级 diff 的一个 run：`equal` 时 added/removed 均为 false。 */
export interface LineDiffRun {
	count: number;
	added: boolean;
	removed: boolean;
}

/**
 * 行级 diff（LCS 动态规划 + 回溯），替代上游的 native `diffLineRuns`。
 *
 * 输出与 native 版本同构：相邻 run 类型交替，equal run 合并计数，
 * added / removed run 即使相邻也不合并。文本按 `\n` 切行后比较。
 */
export function diffLineRuns(previousText: string, currentText: string): LineDiffRun[] {
	const a = previousText.length === 0 ? [] : previousText.split("\n");
	const b = currentText.length === 0 ? [] : currentText.split("\n");
	const n = a.length;
	const m = b.length;

	// 行数过大时退化：仅剥离公共前缀/后缀，中间视为整体替换。
	// 恢复场景文件通常远小于此阈值（>4MB 的文件根本不发 tag）。
	if (n * m > 4_000_000) {
		return diffLineRunsDegenerate(a, b);
	}

	// 行内容先编号，DP 比较整数（省内存、快）。
	const lineIds = new Map<string, number>();
	const idOf = (line: string): number => {
		let id = lineIds.get(line);
		if (id === undefined) {
			id = lineIds.size + 1;
			lineIds.set(line, id);
		}
		return id;
	};
	const ai = new Int32Array(n);
	const bi = new Int32Array(m);
	for (let i = 0; i < n; i++) ai[i] = idOf(a[i]);
	for (let j = 0; j < m; j++) bi[j] = idOf(b[j]);

	// LCS 长度表：dp[i][j] = a[0..i) 与 b[0..j) 的最长公共子序列长度。
	const dp: Int32Array[] = new Array(n + 1);
	dp[0] = new Int32Array(m + 1);
	for (let i = 1; i <= n; i++) {
		const row = new Int32Array(m + 1);
		const prev = dp[i - 1];
		const aiPrev = ai[i - 1];
		for (let j = 1; j <= m; j++) {
			row[j] = aiPrev === bi[j - 1] ? prev[j - 1] + 1 : Math.max(prev[j], row[j - 1]);
		}
		dp[i] = row;
	}

	// 回溯生成 runs（逆序，最后统一反转）。
	const runs: LineDiffRun[] = [];
	let i = n;
	let j = m;
	while (i > 0 || j > 0) {
		if (i > 0 && j > 0 && ai[i - 1] === bi[j - 1]) {
			pushRun(runs, { count: 1, added: false, removed: false });
			i--;
			j--;
		} else if (j > 0 && (i === 0 || dp[i][j - 1] >= dp[i - 1][j])) {
			pushRun(runs, { count: 1, added: true, removed: false });
			j--;
		} else {
			pushRun(runs, { count: 1, added: false, removed: true });
			i--;
		}
	}
	runs.reverse();
	return runs;
}

/** 追加一个 run，与尾部同类型则合并计数。 */
function pushRun(runs: LineDiffRun[], run: LineDiffRun): void {
	const last = runs[runs.length - 1];
	if (last && last.added === run.added && last.removed === run.removed) {
		last.count += run.count;
	} else {
		runs.push(run);
	}
}

/** 退化实现：剥离公共前后缀，中间为整段替换。 */
function diffLineRunsDegenerate(a: string[], b: string[]): LineDiffRun[] {
	let start = 0;
	while (start < a.length && start < b.length && a[start] === b[start]) start++;
	let endA = a.length;
	let endB = b.length;
	while (endA > start && endB > start && a[endA - 1] === b[endB - 1]) {
		endA--;
		endB--;
	}
	const runs: LineDiffRun[] = [];
	if (start > 0) runs.push({ count: start, added: false, removed: false });
	if (endA > start) runs.push({ count: endA - start, added: false, removed: true });
	if (endB > start) runs.push({ count: endB - start, added: true, removed: false });
	if (endA < a.length) runs.push({ count: a.length - endA, added: false, removed: false });
	return runs;
}

export interface RecoveryResult {
	/** Post-recovery text. */
	text: string;
	/** First changed line (1-indexed) relative to the live `currentText`, or `undefined`. */
	firstChangedLine: number | undefined;
	/** Warnings collected during recovery, including the user-facing recovery banner. */
	warnings: string[];
}

function collectAnchorLines(edits: readonly Edit[]): number[] {
	const lines: number[] = [];
	for (const edit of edits) {
		for (const anchor of getEditAnchors(edit)) lines.push(anchor.line);
	}
	return lines;
}

function getEditAnchors(edit: Edit): Anchor[] {
	if (edit.kind === "delete") return [edit.anchor];
	// Recovery only ever receives already-resolved edits (no `block`); this arm
	// exists for type-exhaustiveness over the full `Edit` union.
	if (edit.kind === "block") return [edit.anchor];
	if (edit.kind === "cut") {
		// Every captured line is an anchor: changed interior content is unsafe.
		const anchors: Anchor[] = [];
		for (let line = edit.range.start.line; line <= edit.range.end.line; line++) anchors.push({ line });
		return anchors;
	}
	if (edit.kind === "paste") {
		if (edit.at.kind === "span") {
			const anchors: Anchor[] = [];
			for (let line = edit.at.range.start.line; line <= edit.at.range.end.line; line++) anchors.push({ line });
			return anchors;
		}
		const cursor = edit.at.cursor;
		return cursor.kind === "before_anchor" || cursor.kind === "after_anchor" ? [cursor.anchor] : [];
	}
	return edit.cursor.kind === "before_anchor" || edit.cursor.kind === "after_anchor" ? [edit.cursor.anchor] : [];
}

function buildLineMap(previousText: string, currentText: string): Map<number, number> {
	const changes = diffLineRuns(previousText, currentText);
	const map = new Map<number, number>();
	let previousLine = 1;
	let currentLine = 1;

	for (const change of changes) {
		const count = change.count;
		if (change.added) {
			currentLine += count;
			continue;
		}
		if (change.removed) {
			previousLine += count;
			continue;
		}
		for (let offset = 0; offset < count; offset++) {
			map.set(previousLine + offset, currentLine + offset);
		}
		previousLine += count;
		currentLine += count;
	}

	return map;
}

/** Values appearing two or more times in `lines`, for O(1) duplicate checks. */
function collectDuplicatedValues(lines: readonly string[]): Set<string> {
	const seen = new Set<string>();
	const duplicated = new Set<string>();
	for (const value of lines) {
		if (seen.has(value)) duplicated.add(value);
		else seen.add(value);
	}
	return duplicated;
}

interface AnchorNeighbors {
	/** Nearest non-anchor line below the anchor's run, or `undefined` at the file edge. */
	before: number | undefined;
	/** Nearest non-anchor line above the anchor's run, or `undefined` at the file edge. */
	after: number | undefined;
}

/**
 * Nearest non-anchor context line on each side of every anchor, computed in
 * one sweep over the sorted anchor set. Anchors in one contiguous run share
 * both neighbors (the lines just outside the run), so this replaces the
 * per-anchor directional walk across anchored ranges — O(anchors²) on a
 * large block replacement — with one O(anchors log anchors) pass.
 */
function computeAnchorNeighbors(anchorLines: ReadonlySet<number>, lineCount: number): Map<number, AnchorNeighbors> {
	const sorted = [...anchorLines].sort((a, b) => a - b);
	const neighbors = new Map<number, AnchorNeighbors>();
	for (let i = 0; i < sorted.length; ) {
		let j = i;
		while (j + 1 < sorted.length && sorted[j + 1] === sorted[j] + 1) j++;
		const start = sorted[i];
		const end = sorted[j];
		const before = start - 1 >= 1 && start - 1 <= lineCount ? start - 1 : undefined;
		const after = end + 1 <= lineCount ? end + 1 : undefined;
		for (let k = i; k <= j; k++) neighbors.set(sorted[k], { before, after });
		i = j + 1;
	}
	return neighbors;
}

function validateDuplicateAnchorContext(
	line: number,
	mapped: number,
	neighbors: AnchorNeighbors,
	lineMap: ReadonlyMap<number, number>,
): boolean {
	let checked = false;
	const { before, after } = neighbors;
	if (before !== undefined) {
		checked = true;
		if (lineMap.get(before) !== mapped - (line - before)) return false;
	}
	if (after !== undefined) {
		checked = true;
		if (lineMap.get(after) !== mapped + (after - line)) return false;
	}
	return checked;
}

function validateUniqueAnchorContext(
	line: number,
	mapped: number,
	neighbors: AnchorNeighbors,
	lineMap: ReadonlyMap<number, number>,
): boolean {
	const offset = mapped - line;
	const { before, after } = neighbors;
	if (after !== undefined && lineMap.get(after) === after + offset) return true;
	return before !== undefined && lineMap.get(before) === before + offset;
}

function validateRemappedAnchorContext(
	previousText: string,
	currentText: string,
	lineMap: ReadonlyMap<number, number>,
	edits: readonly Edit[],
): boolean {
	const previousLines = previousText.split("\n");
	const currentLines = currentText.split("\n");
	const anchorLines = new Set(collectAnchorLines(edits));
	// Precompute once per validation pass: which line values are duplicated,
	// and each anchor's nearest non-anchor context. The per-anchor forms —
	// indexOf/lastIndexOf full-file scans plus directional walks across
	// anchored ranges — are O(anchors×lines) + O(anchors²) and blow up on
	// large block replacements.
	const duplicatedPrevious = collectDuplicatedValues(previousLines);
	const duplicatedCurrent = collectDuplicatedValues(currentLines);
	const anchorNeighbors = computeAnchorNeighbors(anchorLines, previousLines.length);

	for (const [line, neighbors] of anchorNeighbors) {
		const mapped = lineMap.get(line);
		if (mapped === undefined) return false;
		if (!duplicatedPrevious.has(previousLines[line - 1]) && !duplicatedCurrent.has(currentLines[mapped - 1])) {
			if (!validateUniqueAnchorContext(line, mapped, neighbors, lineMap)) {
				return false;
			}
			continue;
		}
		if (!validateDuplicateAnchorContext(line, mapped, neighbors, lineMap)) {
			return false;
		}
	}

	return true;
}

interface RemappedEdits {
	edits: Edit[];
	offset: number;
}

function remapEditsToCurrent(previousText: string, currentText: string, edits: readonly Edit[]): RemappedEdits | null {
	const lineMap = buildLineMap(previousText, currentText);
	if (!validateRemappedAnchorContext(previousText, currentText, lineMap, edits)) return null;
	const offsets: number[] = [];

	const mapLine = (line: number): number | null => {
		const mapped = lineMap.get(line);
		if (mapped === undefined) return null;
		offsets.push(mapped - line);
		return mapped;
	};

	const mapAnchor = (anchor: Anchor): Anchor | null => {
		const line = mapLine(anchor.line);
		return line === null ? null : { line };
	};

	const remapped: Edit[] = [];
	for (const edit of edits) {
		if (edit.kind === "delete") {
			const anchor = mapAnchor(edit.anchor);
			if (anchor === null) return null;
			remapped.push({ ...edit, anchor });
			continue;
		}
		if (edit.kind === "block") {
			const anchor = mapAnchor(edit.anchor);
			if (anchor === null) return null;
			remapped.push({ ...edit, anchor });
			continue;
		}
		if (edit.kind === "cut") {
			// Map every captured line; an unmapped interior line means the
			// content drifted and cannot be moved safely. Uniform offsets keep
			// the mapped range contiguous.
			const start = mapLine(edit.range.start.line);
			if (start === null) return null;
			let end = start;
			for (let line = edit.range.start.line + 1; line <= edit.range.end.line; line++) {
				const mapped = mapLine(line);
				if (mapped === null) return null;
				end = mapped;
			}
			remapped.push({ ...edit, range: { start: { line: start }, end: { line: end } } });
			continue;
		}
		if (edit.kind === "paste") {
			let blockStart = edit.blockStart;
			if (blockStart !== undefined) {
				const mappedBlockStart = mapLine(blockStart);
				if (mappedBlockStart === null) return null;
				blockStart = mappedBlockStart;
			}
			if (edit.at.kind === "span") {
				const start = mapLine(edit.at.range.start.line);
				if (start === null) return null;
				let end = start;
				for (let line = edit.at.range.start.line + 1; line <= edit.at.range.end.line; line++) {
					const mapped = mapLine(line);
					if (mapped === null) return null;
					end = mapped;
				}
				remapped.push({
					...edit,
					at: { kind: "span", range: { start: { line: start }, end: { line: end } } },
					blockStart,
				});
				continue;
			}
			const cursor = edit.at.cursor;
			if (cursor.kind !== "before_anchor" && cursor.kind !== "after_anchor") {
				remapped.push(blockStart === edit.blockStart ? edit : { ...edit, blockStart });
				continue;
			}
			const anchor = mapAnchor(cursor.anchor);
			if (anchor === null) return null;
			remapped.push({ ...edit, at: { kind: "gap", cursor: { kind: cursor.kind, anchor } }, blockStart });
			continue;
		}
		if (edit.kind === "insert") {
			let blockStart = edit.blockStart;
			if (blockStart !== undefined) {
				const mappedBlockStart = mapLine(blockStart);
				if (mappedBlockStart === null) return null;
				blockStart = mappedBlockStart;
			}
			const cursor = edit.cursor;
			if (cursor.kind !== "before_anchor" && cursor.kind !== "after_anchor") {
				remapped.push(blockStart === edit.blockStart ? edit : { ...edit, blockStart });
				continue;
			}
			const anchor = mapAnchor(cursor.anchor);
			if (anchor === null) return null;
			remapped.push({ ...edit, cursor: { kind: cursor.kind, anchor }, blockStart });
		}
	}

	if (offsets.length === 0) return null;
	const firstOffset = offsets[0];
	if (!offsets.every(offset => offset === firstOffset)) return null;
	return { edits: remapped, offset: firstOffset };
}

function replayRemappedAnchorsOnCurrent(
	previousText: string,
	currentText: string,
	edits: readonly Edit[],
	recoveryWarning: string,
	clipboard: Clipboard | undefined,
): RecoveryResult | null {
	const remapped = remapEditsToCurrent(previousText, currentText, edits);
	if (remapped === null) return null;
	let applied: ApplyResult;
	try {
		applied = applyEdits(currentText, remapped.edits, clipboard === undefined ? {} : { clipboard });
	} catch {
		return null;
	}
	if (applied.text === currentText) return null;
	return {
		text: applied.text,
		firstChangedLine: applied.firstChangedLine,
		warnings: [remapped.offset === 0 ? recoveryWarning : RECOVERY_LINE_REMAP_WARNING, ...(applied.warnings ?? [])],
	};
}
/**
 * Stateless recovery driver over a {@link SnapshotStore}. Construct once and
 * call {@link Recovery.tryRecover} per stale-tag incident.
 *
 * Recovery maps every stale anchor through unchanged lines from the tagged
 * snapshot to the live text, validates surrounding context, and replays the
 * edit directly on live content. All anchors must move by one consistent
 * offset. A changed, deleted, split, or ambiguous target is rejected so the
 * caller can surface a {@link MismatchError} with current context.
 */
export class Recovery {
	constructor(readonly store: SnapshotStore) {}
	/**
	 * Attempt recovery. Returns `null` when no path forward is found — the
	 * caller should then surface a {@link MismatchError}.
	 */
	tryRecover(args: RecoveryArgs): RecoveryResult | null {
		const { path, currentText, fileHash, edits, clipboard } = args;
		// When retained texts collide on the 16-bit tag, use the latest one.
		// Recovery still requires its anchors and context to map unambiguously.
		const snapshot = this.store.byHash(path, fileHash);
		if (!snapshot) return null;
		const recoveryWarning =
			this.store.head(path) === snapshot ? RECOVERY_EXTERNAL_WARNING : RECOVERY_SESSION_CHAIN_WARNING;
		return replayRemappedAnchorsOnCurrent(snapshot.text, currentText, edits, recoveryWarning, clipboard);
	}
}