import { join, resolve } from "node:path";
import { writeJsonAtomic } from "./atomic-fs.ts";

import type {
	ExtensionAPI,
	ExtensionCommandContext,
	ExtensionContext,
} from "@earendil-works/pi-coding-agent";

import {
	UndoControllerImpl,
	type ControllerDependencies,
	type ControllerInitialState,
} from "./controller.ts";
import { finalizeDurablePack, hasDurablePack, loadDurablePack } from "./durable-pack.ts";
import { assertCursor, canonicalJson, checksum, sameWorkspaceSnapshot } from "./encoding.ts";
import { JournalStore, finalizeCursorMarker, inspectCursorMarkers } from "./journal.ts";
import type { CheckpointRecord, ManifestId, SessionFileIdentity, SnapshotManifest } from "./model.ts";
import {
	cleanupPackedMutations,
	materializePackedMutationJournal,
	recoverPackedMutations,
} from "./packed-recovery.ts";
import { JournalRecovery } from "./recovery.ts";
import { QuarantineManager } from "./quarantine.ts";
import { RestoreEngine } from "./restore-engine.ts";
import { RootDiscovery } from "./root-discovery.ts";
import { DurableCursorWriter, SessionState, type SessionEntrySource } from "./session-state.ts";
import { SnapshotStore } from "./snapshot-store.ts";
import { StatusReporter } from "./status-reporter.ts";
import { WorkspaceLock } from "./workspace-lock.ts";
import { allCompleted, checkOperation, configuredTimeout, currentOperationContext, isUnconfirmedExit, operationHasUnconfirmedExit, runWithOperationContext, withRecoveryBudget, type ProcessDiagnostic } from "./operation-context.ts";

type ReadonlySessionManager = ExtensionContext["sessionManager"];

export function createPiUndoRuntime(context: ExtensionContext, pi: ExtensionAPI) {
	return withRecoveryBudget(() => initializePiUndoRuntime(context, pi));
}

async function initializePiUndoRuntime(context: ExtensionContext, pi: ExtensionAPI) {
	const manager = context.sessionManager;
	const reporter = new StatusReporter(context);
	const sessionState = sessionStateFor(manager);
	const sessionIdentity = await sessionState.getSessionIdentity() ?? volatileSessionIdentity(manager, context.cwd);
	const privateRoot = join(manager.getSessionDir(), ".pi-undo");
	const discovery = new RootDiscovery();
	const initialTopology = await discovery.discover(context.cwd);
	const store = new SnapshotStore({ storeRoot: privateRoot, discovery });
	const restore = new RestoreEngine({ workspaceRoot: context.cwd, store, discovery });
	const journal = new JournalStore({ transactionsRoot: join(privateRoot, "transactions") });
	const cursorWriter = new DurableCursorWriter();
	const workspaceLock = new WorkspaceLock();
	let commandContext: ExtensionCommandContext | undefined;
	let internalNavigation = false;
	const capture = async (scopePaths?: readonly string[]) => {
		const topology = await discovery.discover(context.cwd);
		if (topology.workspaceIdentity !== initialTopology.workspaceIdentity) {
			throw new Error("workspace identity 已变化");
		}
		return store.capture(topology, scopePaths, { topologyAlreadyValidated: true });
	};
	const captureBaseline = async (baseline: SnapshotManifest) => {
		const topology = await discovery.discover(context.cwd);
		if (topology.workspaceIdentity !== initialTopology.workspaceIdentity) {
			throw new Error("workspace identity 已变化");
		}
		return store.captureBaseline(topology, baseline, undefined, { topologyAlreadyValidated: true });
	};
	const recovery = new JournalRecovery({
		sessionIdentity,
		workspaceIdentity: initialTopology.workspaceIdentity,
		getLogicalLeafId: () => sessionStateFor(manager).getLogicalLeafId(),
		loadPending: () => journal.loadPending(),
		assessForeignTransaction: (pending) => journal.isInertForeignPrepared(pending),
		assessCompensatedTransaction: (pending) => journal.isFullyCompensated(pending),
		inspectCursor: (pending) => inspectCursorMarkers(pending.descriptor.sessionIdentity.path, pending.descriptor,
			pending.descriptor.action === "tree" && pending.state.observedLogicalLeaf !== undefined
				? pending.state.observedLogicalLeaf : pending.descriptor.toLogicalLeaf),
		finalizeCursor: (pending, inspection) => finalizeCursorMarker(
			pending.descriptor.sessionIdentity.path,
			pending.descriptor,
			inspection,
			pending.descriptor.action === "tree" && pending.state.observedLogicalLeaf !== undefined
				? pending.state.observedLogicalLeaf : pending.descriptor.toLogicalLeaf,
		),
		recoverMutations: async (pending, decision) => {
			const mutationJournal = journal.mutationJournal(pending.descriptor.opId);
			if (await hasDurablePack(mutationJournal)) {
				const result = await recoverPackedMutations({
					workspaceRoot: context.cwd,
					journal: mutationJournal,
					planDigest: pending.descriptor.planDigest,
					decision,
					retainArtifacts: decision === "roll_forward",
				});
				if (result.kind === "clean" && decision === "roll_forward") {
					await finalizeDurablePack(mutationJournal, context.cwd);
					await cleanupPackedMutations({
						workspaceRoot: context.cwd,
						journal: mutationJournal,
						planDigest: pending.descriptor.planDigest,
					});
				}
				return result;
			}
			const quarantine = new QuarantineManager({ workspaceRoot: context.cwd, journal: mutationJournal });
			try {
				const loaded = await mutationJournal.load();
				const scopePaths = pending.descriptor.scopePaths;
				if (loaded.some((record) => !scopePaths.some((scope) =>
					scope === "." || record.path === scope || record.path.startsWith(`${scope}/`)
				))) {
					throw new Error("mutation journal path 超出 descriptor scope");
				}
				const records = loaded.filter((record) => record.state !== "CLEANED");
				if (decision === "rollback") records.reverse();
				for (const record of records) {
					if (decision === "rollback") {
						await quarantine.restoreMutation(record);
						continue;
					}
					await quarantine.rollForwardMutation(record);
					const latest = await mutationJournal.loadOrdinal(record.ordinal);
					if (latest === undefined) throw new Error("mutation ordinal 在恢复期间丢失");
					await quarantine.cleanupMutation(latest);
				}
				await mutationJournal.assertCleaned();
				return { kind: "clean" } as const;
			} catch {
				const active = await mutationJournal.load().catch(() => []);
				return {
					kind: "conflict" as const,
					paths: Math.max(1, active.filter((record) => record.state !== "CLEANED").length),
				};
			}
		},
		capture,
		loadManifest: (manifestId) => store.loadManifest(manifestId),
		planRestore: (current, target, scopePaths) => restore.plan(current, target, scopePaths),
		applyRestore: (plan, target, operation) => restore.apply(plan, target, {
			opId: operation.opId,
			mutationJournal: journal.mutationJournal(operation.opId),
			forceTargetArtifactSync: true,
		}),
		settle: (opId, phase) => journal.settleRecovery(opId, phase),
	});

	let finalizationQueue: Promise<void> = Promise.resolve();
	let finalizationFailure: unknown;
	const waitForFinalization = async (): Promise<void> => {
		await finalizationQueue;
		if (finalizationFailure !== undefined) throw finalizationFailure;
	};
	const scheduleFinalization = (opId: string): void => {
		finalizationQueue = runWithOperationContext(undefined, () => finalizationQueue.then(() => withRecoveryBudget(async () => {
			const lease = await workspaceLock.acquire(initialTopology.workspaceIdentity);
			try {
				const mutationJournal = journal.mutationJournal(opId);
				const pack = await loadDurablePack(mutationJournal, undefined, true);
				const [materialized, finalized] = await Promise.allSettled([
					materializePackedMutationJournal(mutationJournal, pack),
					finalizeDurablePack(mutationJournal, context.cwd, {
						allowCleanedOwnershipWithoutMarker: false,
					}),
				]);
				if (materialized.status === "rejected") throw materialized.reason;
				if (finalized.status === "rejected") throw finalized.reason;
				await cleanupPackedMutations({
					workspaceRoot: context.cwd,
					journal: mutationJournal,
					planDigest: pack.planDigest,
				});
				await journal.markCommitted(opId);
			} finally {
				if (!operationHasUnconfirmedExit()) await lease.release();
			}
		}))).catch((error: unknown) => {
			finalizationFailure = error;
		});
	};
	const transactionJournal: ControllerDependencies["journal"] = {
		prepare: (descriptor, plan) => journal.prepare(descriptor, plan),
		setPhase: (opId, phase, options) => journal.setPhase(opId, phase, options),
		setPhases: (opId, transitions) => journal.setPhases(opId, transitions),
		markCommitted: async (opId) => {
			const mutationJournal = journal.mutationJournal(opId);
			if (!await hasDurablePack(mutationJournal)) {
				await journal.markCommitted(opId);
				return;
			}
			await journal.assertLogicalCommitReady(opId, true);
			scheduleFinalization(opId);
		},
		loadPending: () => journal.loadPending(),
	};

	const diagnostics: ProcessDiagnostic[] = [];
	const phases: Array<{ phase: string; elapsedMs: number }> = [];
	let operationStarted = 0;
	const dependencies: ControllerDependencies = {
		workspaceIdentity: initialTopology.workspaceIdentity,
		sessionIdentity,
		isAgentIdle: () => context.isIdle(),
		abortAgent: async () => { context.abort(); },
		waitForIdle: async (deadlineMs) => waitForIdle(commandContext, deadlineMs),
		getLogicalLeafId: () => sessionStateFor(manager).getLogicalLeafId(),
		acquireWorkspaceLock: async () => {
			await waitForFinalization();
			return workspaceLock.acquire(initialTopology.workspaceIdentity);
		},
		findUserEntryAfter: (startEntryId) => findUserEntryAfter(manager, startEntryId),
		resolveSessionTarget: (action, checkpoint) => action === "undo"
			? logicalLeafAt(manager, entryParent(manager, checkpoint.userEntryId))
			: checkpoint.endLeafId,
		navigateSession: async (action, checkpoint) => {
			if (commandContext === undefined) throw new Error("command context 不可用");
			const targetId = action === "undo" ? checkpoint.userEntryId : checkpoint.endLeafId;
			internalNavigation = true;
			try {
				const result = await commandContext.navigateTree(targetId, { summarize: false });
				return { cancelled: result.cancelled, logicalLeafId: sessionStateFor(manager).getLogicalLeafId() };
			} finally {
				internalNavigation = false;
			}
		},
		restoreSessionLeaf: async (logicalLeafId) => {
			if (commandContext === undefined) return false;
			const targetId = sessionNavigationEntry(manager, logicalLeafId);
			if (targetId === undefined) return false;
			internalNavigation = true;
			try {
				const result = await commandContext.navigateTree(targetId, { summarize: false });
				return !result.cancelled && sessionStateFor(manager).getLogicalLeafId() === logicalLeafId;
			} finally {
				internalNavigation = false;
			}
		},
		resolveTreeTarget: async (targetEntryId) => resolveTreeTarget(manager, sessionIdentity, targetEntryId),
		appendControl: async (customType, data) => appendControlEntry(pi, manager, customType, data),
		appendCursor: async (cursor) => cursorWriter.appendCursor(cursor, pi, sourceFor(manager)),
		capture,
		captureBaseline,
		captureSafety: async (referenceManifestId, targetManifestId, scopePaths) => {
			const [reference, target] = await allCompleted([
				store.loadManifest(referenceManifestId),
				store.loadManifest(targetManifestId),
			]);
			if (await restore.canReuseDurableSource(reference, target, scopePaths)) return reference;
			return capture(scopePaths);
		},
		changedPaths: async (before, after) => {
			// 完全相同的 workspace snapshot 只撤回 session 分支；无需再次展开所有 root tree。
			if (sameWorkspaceSnapshot(before, after)) return [];
			const plan = await restore.plan(before, after);
			return [...new Set([...plan.deletePaths, ...plan.writePaths])].sort();
		},
		loadManifest: (manifestId) => store.loadManifest(manifestId),
		planRestore: (current, target, scopePaths) => restore.plan(current, target, scopePaths),
		prepareDurableRestore: (current, target, scopePaths) =>
			restore.prepareDurableRestore(current, target, scopePaths),
		applyRestore: (plan, target, operation) => restore.apply(plan, target, {
			opId: operation.opId,
			mutationJournal: journal.mutationJournal(operation.opId),
			deferDurability: true,
		}),
		recoverPending: async () => {
			await waitForFinalization();
			return workspaceLock.withLock(initialTopology.workspaceIdentity, () => recovery.recover());
		},
		journal: transactionJournal,
		clock: Date.now,
		operationTimeoutMs: configuredTimeout("PI_UNDO_OPERATION_TIMEOUT_MS", 300_000),
		onOperationStart: (opId) => {
			operationStarted = performance.now();
			diagnostics.length = 0;
			phases.length = 0;
			reporter.startOperation(opId);
		},
		onProgress: (phase) => {
			reporter.setOperationPhase(phase);
			if (phases.at(-1)?.phase === phase) return;
			if (phases.length === 128) phases.shift();
			phases.push({ phase, elapsedMs: Math.round(performance.now() - operationStarted) });
		},
		onProcess: (diagnostic) => {
			if (diagnostics.length === 128) diagnostics.shift();
			diagnostics.push(diagnostic);
		},
		onOperationEnd: async (opId, result) => {
			const totalMs = Math.round(performance.now() - operationStarted);
			if (totalMs < 1_000 && (result.code === "ok" || result.code === "noop")) return;
			await writeJsonAtomic(join(privateRoot, "diagnostics", `${manager.getSessionId()}-latest.json`), {
				schemaVersion: 1, opId, code: result.code, totalMs, phases, processes: diagnostics,
			});
		},
	};
	const startupRecovery = await workspaceLock.withLock(
		initialTopology.workspaceIdentity,
		() => recovery.recover(),
	);
	const controller = new UndoControllerImpl(dependencies, {
		...rebuildControllerState(manager, sessionIdentity),
		locked: startupRecovery.kind === "locked",
		recoveryReason: startupRecovery.kind === "locked" ? startupRecovery.reason : undefined,
		recoveryCompleted: true,
	});
	return {
		controller,
		reporter,
		diffSource: store,
		recovery: startupRecovery.kind === "locked"
			? { reason: startupRecovery.reason, files: startupRecovery.files, opId: startupRecovery.opId }
			: undefined,
		async dispose(): Promise<void> {
			await controller.dispose();
			await finalizationQueue;
			if (isUnconfirmedExit(finalizationFailure)) throw finalizationFailure;
			reporter.endOperation();
		},
		setCommandContext(next: ExtensionCommandContext | undefined): void {
			commandContext = next;
		},
		isInternalNavigation(): boolean {
			return internalNavigation;
		},
		normalizeTreeEvent(event: { newLeafId: string | null; summaryEntry?: { parentId: string | null } }) {
			return {
				newLeafId: logicalLeafAt(manager, event.newLeafId),
				navigationTargetLeafId: logicalLeafAt(manager,
					event.summaryEntry === undefined ? event.newLeafId : event.summaryEntry.parentId),
			};
		},
	};
}

function rebuildControllerState(
	manager: ReadonlySessionManager,
	identity: SessionFileIdentity,
): ControllerInitialState {
	const state = sessionStateFor(manager);
	const branch = physicalBranch(manager, manager.getLeafId());
	const checkpoints = checkpointFrontierAfterDetachedRun(
		manager,
		identity,
		branch,
		state.getCheckpoints(identity),
	);
	const cursor = state.getCursor(identity);
	let undoStack = [...checkpoints];
	if (cursor !== null) {
		if (cursor.undoHead === null) {
			undoStack = [];
		} else {
			undoStack = checkpointFrontierById(manager, identity, cursor.undoHead);
		}
	}
	const redoStack = cursor === null ? [] : cursor.redoStack.map((checkpointId, index) => {
		const checkpoint = findCheckpointById(manager, identity, checkpointId);
		if (checkpoint === undefined) throw new Error("cursor redo checkpoint 不可信");
		const prefix = cursor.redoStack.slice(0, index + 1);
		const sourceCursor = validCursors(manager, identity)
			.filter((candidate) => candidate.action === "undo" && sameStrings(candidate.redoStack, prefix))
			.at(-1);
		if (sourceCursor === undefined) throw new Error("cursor redo safety manifest 缺失");
		return { checkpoint, targetManifestId: sourceCursor.rollbackManifestId };
	});
	const lastBarrier = findLastIndex(branch, (entry) => entry.type === "custom" && entry.customType === "pi-undo:barrier");
	const lastCheckpoint = findLastIndex(branch, (entry) => entry.type === "custom" && entry.customType === "pi-undo:checkpoint");
	return { undoStack, redoStack, historyPaused: lastBarrier > lastCheckpoint };
}

/**
 * redo 或树导航后的新 run 会挂在 cursor 后面，使前一个 checkpoint 脱离当前物理 branch。
 * start entry 保存了 run 前的逻辑叶，利用它恢复可信的 checkpoint frontier，再接上当前 branch。
 */
function checkpointFrontierAfterDetachedRun(
	manager: ReadonlySessionManager,
	identity: SessionFileIdentity,
	branch: readonly Record<string, unknown>[],
	current: readonly CheckpointRecord[],
): CheckpointRecord[] {
	const start = [...branch].reverse().find((entry) => entry.type === "custom" && entry.customType === "pi-undo:start");
	if (start === undefined || !isRecord(start.data)) return [...current];
	const sourceLogicalLeaf = start.data.sourceLogicalLeaf;
	if (typeof sourceLogicalLeaf !== "string") return [...current];
	const sourceCheckpoint = findCheckpointByEndLeaf(manager, identity, sourceLogicalLeaf);
	if (sourceCheckpoint === undefined) return [...current];
	const inherited = checkpointFrontierById(manager, identity, sourceCheckpoint.checkpointId);
	return [
		...inherited,
		...current.filter((checkpoint) => !inherited.some((candidate) => candidate.checkpointId === checkpoint.checkpointId)),
	].filter((checkpoint, index, all) => all.findIndex((candidate) => candidate.checkpointId === checkpoint.checkpointId) === index);
}

function checkpointFrontierById(
	manager: ReadonlySessionManager,
	identity: SessionFileIdentity,
	checkpointId: string,
): CheckpointRecord[] {
	for (const entry of manager.getEntries() as unknown[]) {
		if (!isRecord(entry) || entry.type !== "custom" || entry.customType !== "pi-undo:checkpoint" || typeof entry.id !== "string") continue;
		const frontier = sessionStateFor(manager, entry.id).getCheckpoints(identity);
		const index = frontier.findIndex((checkpoint) => checkpoint.checkpointId === checkpointId);
		if (index >= 0) return frontier.slice(0, index + 1);
	}
	throw new Error("cursor undoHead 不在可信 checkpoint branch");
}

async function appendControlEntry(
	pi: ExtensionAPI,
	manager: ReadonlySessionManager,
	customType: string,
	data?: unknown,
): Promise<string | null> {
	pi.appendEntry(customType, data);
	const leafId = manager.getLeafId();
	if (leafId === null) return null;
	const entry = manager.getEntry(leafId) as unknown;
	if (!isRecord(entry) || entry.type !== "custom" || entry.customType !== customType) return null;
	if (canonicalJson(entry.data) !== canonicalJson(data ?? null) && entry.data !== data) return null;
	return leafId;
}

function sessionStateFor(manager: ReadonlySessionManager, leafId = manager.getLeafId()): SessionState {
	return new SessionState(sourceFor(manager, leafId));
}

function sourceFor(manager: ReadonlySessionManager, leafId?: string | null): SessionEntrySource {
	return {
		getEntries: () => manager.getEntries(),
		getLeafId: () => leafId === undefined ? manager.getLeafId() : leafId,
		getSessionFile: () => manager.getSessionFile(),
	};
}

function findUserEntryAfter(manager: ReadonlySessionManager, startEntryId: string): string | null {
	const entries = manager.getEntries() as unknown[];
	for (const value of entries) {
		if (!isRecord(value) || value.parentId !== startEntryId || value.type !== "message" || !isRecord(value.message)) continue;
		if (value.message.role === "user" && typeof value.id === "string") return value.id;
	}
	return null;
}

function entryParent(manager: ReadonlySessionManager, entryId: string): string | null {
	const entry = manager.getEntry(entryId) as unknown;
	if (!isRecord(entry) || (entry.parentId !== null && typeof entry.parentId !== "string")) {
		throw new Error("session target entry 无效");
	}
	return entry.parentId;
}

function logicalLeafAt(manager: ReadonlySessionManager, leafId: string | null): string | null {
	return sessionStateFor(manager, leafId).getLogicalLeafId();
}

function sessionNavigationEntry(manager: ReadonlySessionManager, logicalLeafId: string | null): string | undefined {
	if (logicalLeafId !== null) {
		const entry = manager.getEntry(logicalLeafId) as unknown;
		if (isRecord(entry) && entry.type !== "custom_message" &&
			!(entry.type === "message" && isRecord(entry.message) && entry.message.role === "user")) return logicalLeafId;
	}
	// Pi 的公开导航 API 不接受 null；选择 parent 对应逻辑位置的用户消息。
	for (const entry of manager.getEntries() as unknown[]) {
		if (!isRecord(entry) || typeof entry.id !== "string" || entry.type !== "message" ||
			!isRecord(entry.message) || entry.message.role !== "user") continue;
		if (logicalLeafAt(manager, entryParent(manager, entry.id)) === logicalLeafId) return entry.id;
	}
	return undefined;
}

async function resolveTreeTarget(
	manager: ReadonlySessionManager,
	identity: SessionFileIdentity,
	targetEntryId: string | null,
): Promise<{ logicalLeafId: string | null; targetManifestId: ManifestId; undoStack: readonly CheckpointRecord[] }> {
	if (targetEntryId === null) throw new Error("tree target 缺失");
	const target = manager.getEntry(targetEntryId) as unknown;
	if (!isRecord(target)) throw new Error("tree target 不存在");
	const isUser = target.type === "message" && isRecord(target.message) && target.message.role === "user";
	const physicalLeaf = isUser || target.type === "custom_message" ? entryParent(manager, targetEntryId) : targetEntryId;
	const logicalLeafId = logicalLeafAt(manager, physicalLeaf);
	if (isUser) {
		const checkpoint = findCheckpointByUserEntry(manager, identity, targetEntryId);
		if (checkpoint === undefined) throw new Error("tree target 缺少 before checkpoint");
		return {
			logicalLeafId,
			targetManifestId: checkpoint.beforeManifestId,
			undoStack: sessionStateFor(manager, physicalLeaf).getCheckpoints(identity),
		};
	}
	const exact = findCheckpointByEndLeaf(manager, identity, logicalLeafId);
	if (exact !== undefined) {
		return {
			logicalLeafId,
			targetManifestId: exact.afterManifestId,
			undoStack: checkpointFrontierById(manager, identity, exact.checkpointId),
		};
	}
	// cursor 可以证明 summary/撤回后逻辑边界对应的文件状态；不能退回任意旧栈顶。
	const cursor = sessionStateFor(manager, physicalLeaf).getCursor(identity);
	if (cursor !== null && cursor.toLogicalLeaf === logicalLeafId) {
		return {
			logicalLeafId,
			targetManifestId: cursor.targetManifestId,
			undoStack: cursor.undoHead === null ? [] : checkpointFrontierById(manager, identity, cursor.undoHead),
		};
	}
	// 用户输入前的控制条目/根叶可由可信 before checkpoint 证明。
	const boundaries = new Map<string, { checkpoint: CheckpointRecord; physicalLeaf: string | null }>();
	for (const value of manager.getEntries() as unknown[]) {
		if (!isRecord(value) || value.type !== "custom" || value.customType !== "pi-undo:checkpoint" || typeof value.id !== "string") continue;
		for (const checkpoint of sessionStateFor(manager, value.id).getCheckpoints(identity)) {
			const beforeLeaf = entryParent(manager, checkpoint.userEntryId);
			if (logicalLeafAt(manager, beforeLeaf) === logicalLeafId) boundaries.set(checkpoint.checkpointId, { checkpoint, physicalLeaf: beforeLeaf });
		}
	}
	const beforeStates = [...boundaries.values()];
	if (beforeStates.length > 0 && new Set(beforeStates.map(({ checkpoint }) => checkpoint.beforeManifestId)).size === 1) {
		const boundary = beforeStates[0]!;
		return {
			logicalLeafId,
			targetManifestId: boundary.checkpoint.beforeManifestId,
			undoStack: sessionStateFor(manager, boundary.physicalLeaf).getCheckpoints(identity),
		};
	}
	throw new Error("tree target 缺少精确的 checkpoint 边界");
}

function findCheckpointByEndLeaf(
	manager: ReadonlySessionManager,
	identity: SessionFileIdentity,
	endLeafId: string | null,
): CheckpointRecord | undefined {
	if (endLeafId === null) return undefined;
	const matches: CheckpointRecord[] = [];
	for (const entry of manager.getEntries() as unknown[]) {
		if (!isRecord(entry) || entry.type !== "custom" || entry.customType !== "pi-undo:checkpoint" || typeof entry.id !== "string") continue;
		const checkpoint = sessionStateFor(manager, entry.id).getCheckpoints(identity)
			.find((candidate) => candidate.endLeafId === endLeafId);
		if (checkpoint !== undefined) matches.push(checkpoint);
	}
	return matches.length === 1 ? matches[0] : undefined;
}

function findCheckpointByUserEntry(
	manager: ReadonlySessionManager,
	identity: SessionFileIdentity,
	userEntryId: string,
): CheckpointRecord | undefined {
	for (const entry of manager.getEntries() as unknown[]) {
		if (!isRecord(entry) || entry.type !== "custom" || entry.customType !== "pi-undo:checkpoint" || typeof entry.id !== "string") continue;
		const checkpoint = sessionStateFor(manager, entry.id).getCheckpoints(identity)
			.find((candidate) => candidate.userEntryId === userEntryId);
		if (checkpoint !== undefined) return checkpoint;
	}
	return undefined;
}

function findCheckpointById(
	manager: ReadonlySessionManager,
	identity: SessionFileIdentity,
	checkpointId: string,
): CheckpointRecord | undefined {
	for (const entry of manager.getEntries() as unknown[]) {
		if (!isRecord(entry) || entry.type !== "custom" || entry.customType !== "pi-undo:checkpoint" || typeof entry.id !== "string") continue;
		const checkpoint = sessionStateFor(manager, entry.id).getCheckpoints(identity)
			.find((candidate) => candidate.checkpointId === checkpointId);
		if (checkpoint !== undefined) return checkpoint;
	}
	return undefined;
}

function validCursors(manager: ReadonlySessionManager, identity: SessionFileIdentity) {
	const cursors = [];
	for (const entry of manager.getEntries() as unknown[]) {
		if (!isRecord(entry) || entry.type !== "custom" || entry.customType !== "pi-undo:cursor") continue;
		try {
			const cursor = assertCursor(entry.data);
			if (sameIdentity(cursor.sessionIdentity, identity)) cursors.push(cursor);
		} catch {
			// 旧分支中的损坏 cursor 不参与 frontier 重建。
		}
	}
	return cursors;
}

function physicalBranch(manager: ReadonlySessionManager, leafId: string | null): Record<string, unknown>[] {
	const entries = new Map<string, Record<string, unknown>>();
	for (const entry of manager.getEntries() as unknown[]) {
		if (isRecord(entry) && typeof entry.id === "string") entries.set(entry.id, entry);
	}
	const branch: Record<string, unknown>[] = [];
	const visited = new Set<string>();
	let current = leafId;
	while (current !== null) {
		if (visited.has(current)) throw new Error("session parent cycle");
		visited.add(current);
		const entry = entries.get(current);
		if (entry === undefined) throw new Error("session parent 缺失");
		branch.push(entry);
		if (entry.parentId !== null && typeof entry.parentId !== "string") throw new Error("session parent 无效");
		current = entry.parentId;
	}
	return branch.reverse();
}

function findLastIndex<T>(values: readonly T[], predicate: (value: T) => boolean): number {
	for (let index = values.length - 1; index >= 0; index -= 1) {
		if (predicate(values[index]!)) return index;
	}
	return -1;
}

function sameStrings(left: readonly string[], right: readonly string[]): boolean {
	return left.length === right.length && left.every((value, index) => value === right[index]);
}

function sameIdentity(left: SessionFileIdentity, right: SessionFileIdentity): boolean {
	return resolve(left.path) === resolve(right.path) && left.headerChecksum === right.headerChecksum;
}

function volatileSessionIdentity(manager: ReadonlySessionManager, cwd: string): SessionFileIdentity {
	const header = manager.getHeader() as unknown;
	const record = isRecord(header) ? header : {};
	const content = {
		id: typeof record.id === "string" ? record.id : manager.getSessionId(),
		timestamp: typeof record.timestamp === "string" ? record.timestamp : "volatile",
		cwd: typeof record.cwd === "string" ? record.cwd : cwd,
	};
	return {
		path: resolve(manager.getSessionFile() ?? join(manager.getSessionDir(), `.pi-undo/volatile-${manager.getSessionId()}.jsonl`)),
		headerChecksum: checksum(canonicalJson(content)),
	};
}

async function waitForIdle(context: ExtensionCommandContext | undefined, deadlineMs: number): Promise<boolean> {
	if (context === undefined) return false;
	checkOperation();
	const operation = currentOperationContext();
	const remaining = Math.max(0, Math.min(deadlineMs, operation?.deadline ?? Infinity) - Date.now());
	let timeout: ReturnType<typeof setTimeout> | undefined;
	let onAbort: (() => void) | undefined;
	try {
		return await Promise.race([
			context.waitForIdle().then(() => true, () => false),
			new Promise<boolean>((resolveTimeout) => {
				timeout = setTimeout(() => resolveTimeout(false), remaining);
				onAbort = () => resolveTimeout(false);
				operation?.signal.addEventListener("abort", onAbort, { once: true });
			}),
		]);
	} finally {
		if (timeout !== undefined) clearTimeout(timeout);
		if (onAbort !== undefined) operation?.signal.removeEventListener("abort", onAbort);
	}
}

function isRecord(value: unknown): value is Record<string, unknown> {
	return typeof value === "object" && value !== null && !Array.isArray(value);
}