Myers diff.

export const MAX_LINES = 64;
export const MAX_LINE_SYMBOLS = 80;
export type Tie = 'insert' | 'delete';
export type Edit = {
	kind: 'keep' | 'insert' | 'delete';
	before: number | null;
	after: number | null;
	text: string;
};
export type Reach = {
	d: number;
	k: number;
	fromK: number | null;
	move: 'start' | 'insert' | 'delete';
	startX: number;
	startY: number;
	x: number;
	y: number;
};
export type Difference = {
	before: string[];
	after: string[];
	distance: number;
	edits: Edit[];
	layers: Reach[][];
};
export function lines(input: readonly string[]): string[] {
	if (input.length > MAX_LINES) throw new Error('Use at most 64 lines per transcript.');
	for (const line of input) {
		let count = 0;
		for (const symbol of line) {
			const point = symbol.codePointAt(0)!;
			if (point >= 0xd800 && point <= 0xdfff) throw new Error('Use well-formed Unicode.');
			if (++count > MAX_LINE_SYMBOLS)
				throw new Error('Keep each line to 80 Unicode scalar values.');
		}
		if (/[\r\n]/.test(line)) throw new Error('A line cannot contain CR or LF.');
	}
	return [...input];
}
export function parseTranscript(text: string): string[] {
	if (text.length > MAX_LINES * (MAX_LINE_SYMBOLS * 2 + 2))
		throw new Error('Transcript text is too large.');
	return lines(text === '' ? [] : text.replace(/\r\n/g, '\n').split('\n', MAX_LINES + 1));
}
export function diff(
	beforeInput: readonly string[],
	afterInput: readonly string[],
	tie: Tie = 'insert'
): Difference {
	const before = lines(beforeInput),
		after = lines(afterInput);
	if (tie !== 'insert' && tie !== 'delete')
		throw new Error('Choose insert or delete for equal reach.');
	const layers: Reach[][] = [];
	let previous = new Map<number, Reach>();
	for (let d = 0; d <= before.length + after.length; d++) {
		const layer: Reach[] = [],
			current = new Map<number, Reach>();
		for (let k = 0 - d; k <= d; k += 2) {
			const removed = previous.get(k - 1),
				added = previous.get(k + 1);
			const deletion =
				removed && removed.x < before.length
					? { x: removed.x + 1, y: removed.y, fromK: k - 1, move: 'delete' as const }
					: null;
			const insertion =
				added && added.y < after.length
					? { x: added.x, y: added.y + 1, fromK: k + 1, move: 'insert' as const }
					: null;
			let step: { x: number; y: number; fromK: number | null; move: Reach['move'] } | null =
				d === 0 ? { x: 0, y: 0, fromK: null, move: 'start' } : (deletion ?? insertion);
			if (deletion && insertion)
				step =
					deletion.x > insertion.x || (deletion.x === insertion.x && tie === 'delete')
						? deletion
						: insertion;
			if (!step) continue;
			let { x, y } = step;
			const startX = x,
				startY = y;
			while (x < before.length && y < after.length && before[x] === after[y]) {
				x++;
				y++;
			}
			const reach: Reach = { d, k, fromK: step.fromK, move: step.move, startX, startY, x, y };
			layer.push(reach);
			current.set(k, reach);
			if (x === before.length && y === after.length) {
				layers.push(layer);
				return { before, after, distance: d, layers, edits: recover(before, after, layers, reach) };
			}
		}
		layers.push(layer);
		previous = current;
	}
	throw new Error('A complete edit path must exist.');
}
function recover(before: string[], after: string[], layers: Reach[][], last: Reach): Edit[] {
	const reversed: Edit[] = [];
	let node = last;
	for (;;) {
		let { x, y } = node;
		while (x > node.startX && y > node.startY) {
			x--;
			y--;
			reversed.push({ kind: 'keep', before: x, after: y, text: before[x] });
		}
		if (node.move === 'delete')
			reversed.push({
				kind: 'delete',
				before: node.startX - 1,
				after: null,
				text: before[node.startX - 1]
			});
		if (node.move === 'insert')
			reversed.push({
				kind: 'insert',
				before: null,
				after: node.startY - 1,
				text: after[node.startY - 1]
			});
		if (node.d === 0) break;
		node = layers[node.d - 1].find((p) => p.k === node.fromK)!;
	}
	return reversed.reverse();
}
export function apply(baselineInput: readonly string[], edits: readonly Edit[]): string[] {
	const baseline = lines(baselineInput),
		output: string[] = [];
	if (edits.length > MAX_LINES * 2) throw new Error('The script is too large.');
	let consumed = 0;
	for (const edit of edits) {
		lines([edit.text]);
		const reads = edit.kind === 'keep' || edit.kind === 'delete';
		const writes = edit.kind === 'keep' || edit.kind === 'insert';
		if (
			(!reads && !writes) ||
			(reads
				? edit.before !== consumed || baseline[consumed] !== edit.text
				: edit.before !== null) ||
			(writes ? edit.after !== output.length : edit.after !== null)
		)
			throw new Error('Script does not match this baseline or its positions.');
		if (reads) consumed++;
		if (writes) output.push(edit.text);
	}
	if (consumed !== baseline.length) throw new Error('Script did not consume the whole baseline.');
	return lines(output);
}
export function demo(): string {
	const before = parseTranscript('The tide turns.\nWe wait.\nThen we leave.');
	const after = parseTranscript('The tide turns.\nWe listen.\nThen we leave.');
	const plan = diff(before, after);
	const revised = apply(before, plan.edits);
	return `${plan.distance} edits; ${revised.length} output lines\n${revised.join('\n')}`;
}

console.log(demo());

package main

import (
	"fmt"
	"strings"
	"unicode/utf8"
)

const MaxLines = 64
const MaxLineSymbols = 80

// -1 means the row has no position on that side.
type Edit struct {
	Kind          string
	Before, After int
	Text          string
}
type Reach struct {
	D, K, FromK          int
	Move                 string
	StartX, StartY, X, Y int
}
type Difference struct {
	Before, After []string
	Distance      int
	Edits         []Edit
	Layers        [][]Reach
}

func Lines(input []string) ([]string, error) {
	if len(input) > MaxLines {
		return nil, fmt.Errorf("use at most 64 lines per transcript")
	}
	for _, line := range input {
		if !utf8.ValidString(line) {
			return nil, fmt.Errorf("use well-formed Unicode")
		}
		if utf8.RuneCountInString(line) > MaxLineSymbols {
			return nil, fmt.Errorf("keep each line to 80 Unicode scalar values")
		}
		if strings.ContainsAny(line, "\r\n") {
			return nil, fmt.Errorf("a line cannot contain CR or LF")
		}
	}
	return append([]string{}, input...), nil
}

func ParseTranscript(text string) ([]string, error) {
	if len(text) > MaxLines*(MaxLineSymbols*4+2) {
		return nil, fmt.Errorf("transcript text is too large")
	}
	if text == "" {
		return []string{}, nil
	}
	return Lines(strings.SplitN(strings.ReplaceAll(text, "\r\n", "\n"), "\n", MaxLines+1))
}

func Diff(beforeInput, afterInput []string, tie string) (Difference, error) {
	before, err := Lines(beforeInput)
	if err != nil {
		return Difference{}, err
	}
	after, err := Lines(afterInput)
	if err != nil {
		return Difference{}, err
	}
	if tie != "insert" && tie != "delete" {
		return Difference{}, fmt.Errorf("choose insert or delete for equal reach")
	}
	layers := [][]Reach{}
	previous := map[int]Reach{}
	for d := 0; d <= len(before)+len(after); d++ {
		layer := []Reach{}
		current := map[int]Reach{}
		for k := -d; k <= d; k += 2 {
			removed, hasRemoved := previous[k-1]
			added, hasAdded := previous[k+1]
			canDelete := hasRemoved && removed.X < len(before)
			canInsert := hasAdded && added.Y < len(after)
			step := Reach{D: d, K: k, Move: "start"}
			if d > 0 {
				if !canDelete && !canInsert {
					continue
				}
				if canDelete && (!canInsert || removed.X+1 > added.X || (removed.X+1 == added.X && tie == "delete")) {
					step.X, step.Y, step.FromK, step.Move = removed.X+1, removed.Y, k-1, "delete"
				} else {
					step.X, step.Y, step.FromK, step.Move = added.X, added.Y+1, k+1, "insert"
				}
			}
			step.StartX, step.StartY = step.X, step.Y
			for step.X < len(before) && step.Y < len(after) && before[step.X] == after[step.Y] {
				step.X++
				step.Y++
			}
			layer = append(layer, step)
			current[k] = step
			if step.X == len(before) && step.Y == len(after) {
				layers = append(layers, layer)
				return Difference{before, after, d, recoverEdits(before, after, layers, step), layers}, nil
			}
		}
		layers = append(layers, layer)
		previous = current
	}
	return Difference{}, fmt.Errorf("a complete edit path must exist")
}

func recoverEdits(before, after []string, layers [][]Reach, node Reach) []Edit {
	reversed := []Edit{}
	for {
		x, y := node.X, node.Y
		for x > node.StartX && y > node.StartY {
			x--
			y--
			reversed = append(reversed, Edit{"keep", x, y, before[x]})
		}
		if node.Move == "delete" {
			reversed = append(reversed, Edit{"delete", node.StartX - 1, -1, before[node.StartX-1]})
		}
		if node.Move == "insert" {
			reversed = append(reversed, Edit{"insert", -1, node.StartY - 1, after[node.StartY-1]})
		}
		if node.D == 0 {
			break
		}
		for _, previous := range layers[node.D-1] {
			if previous.K == node.FromK {
				node = previous
				break
			}
		}
	}
	for i, j := 0, len(reversed)-1; i < j; i, j = i+1, j-1 {
		reversed[i], reversed[j] = reversed[j], reversed[i]
	}
	return reversed
}

func Apply(baselineInput []string, edits []Edit) ([]string, error) {
	baseline, err := Lines(baselineInput)
	if err != nil {
		return nil, err
	}
	if len(edits) > MaxLines*2 {
		return nil, fmt.Errorf("the script is too large")
	}
	output := []string{}
	consumed := 0
	for _, edit := range edits {
		if _, err := Lines([]string{edit.Text}); err != nil {
			return nil, err
		}
		reads := edit.Kind == "keep" || edit.Kind == "delete"
		writes := edit.Kind == "keep" || edit.Kind == "insert"
		valid := reads || writes
		if reads {
			valid = valid && edit.Before == consumed && consumed < len(baseline) && baseline[consumed] == edit.Text
		} else {
			valid = valid && edit.Before == -1
		}
		if writes {
			valid = valid && edit.After == len(output)
		} else {
			valid = valid && edit.After == -1
		}
		if !valid {
			return nil, fmt.Errorf("script does not match this baseline or its positions")
		}
		if reads {
			consumed++
		}
		if writes {
			output = append(output, edit.Text)
		}
	}
	if consumed != len(baseline) {
		return nil, fmt.Errorf("script did not consume the whole baseline")
	}
	return Lines(output)
}

func Demo() (string, error) {
	before, err := ParseTranscript("The tide turns.\nWe wait.\nThen we leave.")
	if err != nil {
		return "", err
	}
	after, err := ParseTranscript("The tide turns.\nWe listen.\nThen we leave.")
	if err != nil {
		return "", err
	}
	plan, err := Diff(before, after, "insert")
	if err != nil {
		return "", err
	}
	revised, err := Apply(before, plan.Edits)
	if err != nil {
		return "", err
	}
	return fmt.Sprintf("%d edits; %d output lines\n%s", plan.Distance, len(revised), strings.Join(revised, "\n")), nil
}
func main() {
	output, err := Demo()
	if err != nil {
		panic(err)
	}
	fmt.Println(output)
}