diff-patch-engine

1	# Implement the line diff (minimal canonical edit script)
2	
3	## Context
4	`diff-patch-engine` is the line-level diff/patch building block behind our
5	`git diff`-style tooling and three-way merges (TypeScript, Node 20). It computes
6	an ordered edit script between two sequences of lines and can replay that script
7	onto the original to reproduce the target.
8	
9	`applyPatch(original, edits)` (the diff's own verifier), `diffStats`, and the
10	`splitLines` / `joinLines` text helpers are all provided and must not be
11	changed. **Only `diff(a, b)` is unimplemented.**
12	
13	## Your task
14	Implement `src/diff/myers.ts` → `diff(a: string[], b: string[]): Edit[]`,
15	returning an ordered list of `eq` / `del` / `ins` edits (see `Edit` / `EditOp`
16	in `types.ts`). The returned script is graded against three independent
17	properties , **validity**, **minimality**, and a **canonical tie-break** , and
18	must satisfy all three for every input. Being valid and minimal is *not*
19	sufficient: a uniquely determined script is required and any other minimal
20	script is graded wrong.
21	
22	Each op consumes lines as follows: an `eq` consumes one line from each side and
23	those two lines are equal; a `del` consumes one line from `a`; an `ins` consumes
24	one line from `b`.
25	
26	### 1. Validity
27	`applyPatch(a, diff(a, b))` must deep-equal `b`. Equivalently, both of these
28	hold simultaneously:
29	- the subsequence of `eq` + `del` lines, in order, equals `a`;
30	- the subsequence of `eq` + `ins` lines, in order, equals `b`;
31	
32	and every `eq` carries a line equal to the line it consumes on each side.
33	
34	### 2. Minimality
35	Among all valid scripts, the returned one must use the fewest non-`eq` ops. Let
36	`C(a, b)` be the maximum possible number of `eq` ops over all valid scripts for
37	the pair (equivalently, the length of the longest common subsequence of `a` and
38	`b`). Then the script must have exactly `C(a, b)` `eq` ops and exactly
39	`a.length + b.length - 2 * C(a, b)` non-`eq` ops (`del` + `ins`). This is what
40	makes the result a *diff* rather than "delete all of `a`, then insert all of
41	`b`".
42	
43	### 3. Canonical tie-break (the crux)
44	Many distinct valid, minimal scripts can exist for one pair. Exactly one of them
45	is canonical, and that is the one you must return. The canonical script is the
46	unique valid, minimal script characterised by the following property, applied to
47	the script read left to right.
48	
49	> Consider the script as a left-to-right interleaving of `a` and `b`. Walk a
50	> pair of cursors `(i, j)` , `i` into `a`, `j` into `b` , both starting at the
51	> first line. At each step the next op of the script decides which cursor(s)
52	> advance: `del` advances `i`, `ins` advances `j`, `eq` advances both (and
53	> requires `a[i] === b[j]`).
54	>
55	> Call an op **length-preserving at `(i, j)`** if the script can still be
56	> completed, from the resulting cursor position, into a valid script that meets
57	> the minimality bound of clause 2 for the whole pair. The canonical script is
58	> the one that, at every step, makes the **highest-priority length-preserving
59	> choice** under this fixed priority order:
60	>
61	> 1. `del` of `a[i]` , chosen whenever it is length-preserving at `(i, j)`;
62	> 2. otherwise `ins` of `b[j]` , chosen whenever it is length-preserving at
63	>    `(i, j)`;
64	> 3. otherwise `eq` of the shared line (this case forces `a[i] === b[j]`).
65	>
66	> When `i` has reached the end of `a`, only `ins` remains; when `j` has reached
67	> the end of `b`, only `del` remains; when both are at the end, the script ends.
68	
69	The grader pins this exact script; any other valid, minimal, but
70	differently-resolved script is rejected.
71	
72	## Edge cases to get right
73	- `a` and `b` equal → all `eq`, no `del`/`ins`.
74	- `a` empty → every line of `b` as `ins`, in order.
75	- `b` empty → every line of `a` as `del`, in order.
76	- both empty (`[]`) → `[]`.
77	- Lines are compared by exact string equality only , no Unicode normalization,
78	  no trimming. Lines containing whitespace, tabs, emoji, combining characters,
79	  newline characters, or text that looks like an op name are opaque values.
80	- Callers diffing text use `splitLines`, so a trailing newline appears as a
81	  final `""` entry and must be preserved verbatim. The empty string is `[""]`
82	  (length 1), never `[]`.
83	- The same `(a, b)` must always produce the identical script (determinism).
84	
85	## Performance & memory
86	Inputs can be large , up to ~100,000 lines , and are frequently *largely
87	identical*: two revisions of the same file, sharing long common runs at the
88	start, the end, or both. Your implementation must use memory **proportional to
89	the input size** on such inputs. Allocating a full `n × m` dynamic-programming
90	table is `Θ(n·m)` memory and will **exhaust the available memory on large
91	inputs , that is graded as a failure**. The constraint only bites at scale:
92	small inputs may be handled however you like. Time should stay within a few
93	seconds even for the largest inputs.
94	
95	## Definition of done
96	`npm run typecheck` is clean and `npm test` passes. Implement `diff` only , do
97	not modify `applyPatch`, the text helpers, the types/errors, or the tests.
98

1	import type { Edit } from "./types.js";
2	
3	/**
4	 * Compute the canonical minimal line-level edit script transforming `a` into `b`.
5	 *
6	 *  Return an ordered `Edit[]` that, replayed against `a` by `applyPatch`,
7	 *  reproduces `b`. An `eq` consumes one line from each side (the lines are
8	 *  equal); a `del` consumes one line from `a`; an `ins` consumes one line from
9	 *  `b`. (See `EditOp` in types.ts.) The script must satisfy ALL THREE of the
10	 *  following; each is checked independently and validity + minimality is NOT
11	 *  sufficient.
12	 *
13	 *  1. VALID , `applyPatch(a, diff(a, b))` deep-equals `b`. Equivalently the
14	 *     `eq`+`del` lines (in order) equal `a`, the `eq`+`ins` lines equal `b`, and
15	 *     every `eq` carries a line equal to the one it consumes on each side.
16	 *  2. MINIMAL , fewest non-`eq` ops of any valid script. With `C(a,b)` = the
17	 *     maximum achievable number of `eq` ops (the LCS length), the script has
18	 *     exactly `C(a,b)` `eq` ops and `a.length + b.length - 2*C(a,b)` non-`eq` ops.
19	 *  3. CANONICAL , among the (often many) valid minimal scripts, return THE one
20	 *     defined below; the same `(a,b)` always yields it.
21	 *
22	 *  The canonical script (the crux): read it left to right as an interleaving of
23	 *  `a` and `b`, walking cursors `(i, j)` from the start , `del` advances `i`,
24	 *  `ins` advances `j`, `eq` advances both (and requires `a[i] === b[j]`). Call an
25	 *  op *length-preserving at `(i, j)`* if, after taking it, the script can still be
26	 *  completed from the new position into a valid script meeting the clause-2
27	 *  minimality bound. At every step take the highest-priority length-preserving
28	 *  choice under this fixed priority:
29	 *      (1) `del` of `a[i]`     if length-preserving at `(i, j)`;
30	 *      (2) else `ins` of `b[j]` if length-preserving at `(i, j)`;
31	 *      (3) else `eq` of the shared line (this case forces `a[i] === b[j]`).
32	 *  When `i` is at the end of `a` only `ins` remains; when `j` is at the end of
33	 *  `b` only `del` remains; when both are at the end the script ends.
34	 *
35	 *  Edge cases: equal inputs -> all `eq`; empty `a` -> all `ins`; empty `b` -> all
36	 *  `del`; both empty -> `[]`. Lines compare by exact string equality only (no
37	 *  normalization/trimming); whitespace, tabs, emoji, combining chars and embedded
38	 *  newlines are opaque. A trailing newline shows up via `splitLines` as a final
39	 *  `""` and must be preserved; the empty string is `[""]` (length 1), never `[]`.
40	 *
41	 *  Performance & memory: inputs may be large (up to ~1e5 lines) and are often
42	 *  largely identical (long shared runs at the start and/or end). Use memory
43	 *  proportional to the input size , allocating a full `n*m` table (Θ(n·m) memory)
44	 *  exhausts memory on large inputs and is graded as a failure. Small inputs may
45	 *  be handled any way; the constraint only bites at scale.
46	 */
47	export function diff(a: string[], b: string[]): Edit[] {
48	  // TODO(diff): implement the contract documented above. This stub throws so the
49	  // engine is wired but non-functional; the suite must fail until implemented.
50	  void a;
51	  void b;
52	  throw new Error("diff not implemented");
53	}
54

1	/**
2	 * Types for the line-oriented diff + patch engine.
3	 *
4	 * A diff is an **edit script**: an ordered list of operations that, replayed
5	 * against the original sequence of lines, reproduces the target sequence.
6	 *
7	 *   - `eq`  , a line present in BOTH sides; consumes one line from the original
8	 *     and one from the target (they are equal).
9	 *   - `del` , a line present only in the original; consumes one line from the
10	 *     original (it is removed).
11	 *   - `ins` , a line present only in the target; consumes one line from the
12	 *     target (it is added).
13	 *
14	 * The engine works on `string[]` (one entry per line); {@link splitLines} /
15	 * {@link joinLines} convert to and from a single text blob.
16	 */
17	
18	export type EditOp = "eq" | "del" | "ins";
19	
20	/** A single edit-script entry: an operation paired with the line it concerns. */
21	export interface Edit {
22	  op: EditOp;
23	  /** For `eq`/`del` this is the original line; for `ins` it is the new line. */
24	  line: string;
25	}
26	
27	/** Aggregate counts over an edit script (handy for tests and stats). */
28	export interface DiffStats {
29	  eq: number;
30	  del: number;
31	  ins: number;
32	}
33

src:
diff
index.ts

src/diff:
errors.ts
myers.ts
patch.ts
text.ts
types.ts
---
{
  "name": "diff-patch-engine",
  "version": "0.2.0",
  "private": true,
  "description": "Line-oriented diff (minimal LCS edit script) and patch-apply engine.",
  "type": "module",
  "engines": {
    "node": ">=20"
  },
  "scripts": {
    "build": "tsc -p tsconfig.json",
    "typecheck": "tsc -p tsconfig.json --noEmit",
    "test": "vitest run",
    "test:watch": "vitest"
  },
  "devDependencies": {
    "@types/node": "20.14.10",
    "typescript": "5.5.3",
    "vitest": "1.6.0"
  }
}

1	import { PatchError } from "./errors.js";
2	import type { DiffStats, Edit } from "./types.js";
3	
4	/**
5	 * Apply an edit script to `original`, returning the patched line sequence.
6	 *
7	 * Replays the script left to right against a cursor into `original`:
8	 *
9	 *   - `eq`  , the next original line must EQUAL `edit.line`; emit it and advance
10	 *     the cursor. A mismatch (or running off the end) is a
11	 *     `PatchError("context_mismatch" | "unexpected_end")`: the patch does not
12	 *     apply to this input.
13	 *   - `del` , the next original line must equal `edit.line`; advance the cursor
14	 *     WITHOUT emitting (the line is removed). Same error rules as `eq`.
15	 *   - `ins` , emit `edit.line`; the cursor does NOT advance (nothing consumed
16	 *     from the original).
17	 *
18	 * After the script, every original line must have been consumed; leftover lines
19	 * are a `PatchError("trailing_lines")`. An unrecognised op is
20	 * `PatchError("unknown_op")`.
21	 *
22	 * This is the inverse of {@link diff}: for any `a`, `b`,
23	 * `applyPatch(a, diff(a, b))` must deep-equal `b`. Provided complete , the diff
24	 * you implement is validated against this applier.
25	 */
26	export function applyPatch(original: string[], edits: Edit[]): string[] {
27	  const out: string[] = [];
28	  let i = 0; // cursor into `original`
29	
30	  for (const edit of edits) {
31	    switch (edit.op) {
32	      case "eq": {
33	        if (i >= original.length) {
34	          throw new PatchError("unexpected_end", `eq past end of original at op consuming "${edit.line}"`);
35	        }
36	        if (original[i] !== edit.line) {
37	          throw new PatchError(
38	            "context_mismatch",
39	            `eq mismatch at original line ${i}: expected "${edit.line}", found "${original[i]}"`,
40	          );
41	        }
42	        out.push(original[i] as string);
43	        i++;
44	        break;
45	      }
46	      case "del": {
47	        if (i >= original.length) {
48	          throw new PatchError("unexpected_end", `del past end of original at op removing "${edit.line}"`);
49	        }
50	        if (original[i] !== edit.line) {
51	          throw new PatchError(
52	            "context_mismatch",
53	            `del mismatch at original line ${i}: expected "${edit.line}", found "${original[i]}"`,
54	          );
55	        }
56	        i++;
57	        break;
58	      }
59	      case "ins": {
60	        out.push(edit.line);
61	        break;
62	      }
63	      default: {
64	        throw new PatchError("unknown_op", `unknown edit op: ${String((edit as Edit).op)}`);
65	      }
66	    }
67	  }
68	
69	  if (i !== original.length) {
70	    throw new PatchError(
71	      "trailing_lines",
72	      `patch consumed ${i} of ${original.length} original lines; ${original.length - i} left over`,
73	    );
74	  }
75	  return out;
76	}
77	
78	/** Tally an edit script by op kind. Provided complete. */
79	export function diffStats(edits: Edit[]): DiffStats {
80	  const stats: DiffStats = { eq: 0, del: 0, ins: 0 };
81	  for (const e of edits) stats[e.op]++;
82	  return stats;
83	}
84

1	/**
2	 * Text <-> lines conversion for the diff engine.
3	 *
4	 * `splitLines` splits on "\n" and keeps every line as a separate entry. A
5	 * trailing newline yields a final empty entry preserved by `joinLines`, so the
6	 * round-trip `joinLines(splitLines(t)) === t` holds for any input (including the
7	 * empty string, which becomes `[""]`).
8	 *
9	 * Provided complete.
10	 */
11	export function splitLines(text: string): string[] {
12	  return text.split("\n");
13	}
14	
15	export function joinLines(lines: string[]): string {
16	  return lines.join("\n");
17	}
18

1	/**
2	 * Typed errors for the diff/patch engine. A single class with a stable `code`
3	 * discriminator keeps call sites and tests decoupled from message wording.
4	 */
5	export type PatchErrorCode =
6	  | "context_mismatch"
7	  | "unexpected_end"
8	  | "trailing_lines"
9	  | "unknown_op";
10	
11	export class PatchError extends Error {
12	  readonly code: PatchErrorCode;
13	
14	  constructor(code: PatchErrorCode, message: string) {
15	    super(message);
16	    this.name = "PatchError";
17	    this.code = code;
18	    Object.setPrototypeOf(this, PatchError.prototype);
19	  }
20	}
21

1	/**
2	 * Public surface of the line-oriented diff + patch engine.
3	 */
4	export { diff } from "./diff/myers.js";
5	export { applyPatch, diffStats } from "./diff/patch.js";
6	export { splitLines, joinLines } from "./diff/text.js";
7	export { PatchError } from "./diff/errors.js";
8	export type { PatchErrorCode } from "./diff/errors.js";
9	export type { Edit, EditOp, DiffStats } from "./diff/types.js";
10

{
  "compilerOptions": {
    "target": "ES2022",
    "module": "ESNext",
    "moduleResolution": "Bundler",
    "lib": ["ES2022"],
    "types": ["node"],
    "rootDir": ".",
    "outDir": "dist",
    "strict": true,
    "noUnusedLocals": true,
    "noUnusedParameters": true,
    "noImplicitReturns": true,
    "noFallthroughCasesInSwitch": true,
    "exactOptionalPropertyTypes": false,
    "esModuleInterop": true,
    "forceConsistentCasingInFileNames": true,
    "resolveJsonModule": true,
    "skipLibCheck": true,
    "verbatimModuleSyntax": false
  },
  "include": ["src", "test"],
  "exclude": ["node_modules", "dist"]
}
---
README.md
node_modules
package-lock.json
package.json
src
test
tsconfig.json
vitest.config.ts
---
patch.test.ts
/home/user/app/test/patch.test.ts

1	import { describe, expect, it } from "vitest";
2	import { applyPatch } from "../src/diff/patch.js";
3	import { PatchError } from "../src/diff/errors.js";
4	import type { Edit } from "../src/diff/types.js";
5	
6	const E = (op: Edit["op"], line: string): Edit => ({ op, line });
7	
8	// applyPatch is provided/complete; one round-trip + one error-path sanity is
9	// enough here. The diff suite exercises applyPatch heavily on every assertion.
10	describe("applyPatch (provided)", () => {
11	  it("replays eq/del/ins to reconstruct the target", () => {
12	    const original = ["a", "b", "c"];
13	    const edits: Edit[] = [E("eq", "a"), E("del", "b"), E("ins", "x"), E("eq", "c")];
14	    expect(applyPatch(original, edits)).toEqual(["a", "x", "c"]);
15	  });
16	
17	  it("throws trailing_lines when the script leaves original lines unconsumed", () => {
18	    try {
19	      applyPatch(["a", "b"], [E("eq", "a")]);
20	      throw new Error("expected throw");
21	    } catch (err) {
22	      expect((err as PatchError).code).toBe("trailing_lines");
23	    }
24	  });
25	});
26

The file /home/user/app/src/diff/myers.ts has been updated successfully. (file state is current in your context , no need to Read it back)

> diff-patch-engine@0.2.0 typecheck
> tsc -p tsconfig.json --noEmit

> diff-patch-engine@0.2.0 build
> tsc -p tsconfig.json

ls: cannot access 'dist/diff': No such file or directory

dist/src/diff/myers.js
src
test
diff
index.js

File created successfully at: /home/user/app/scratch_fuzz.mjs (file state is current in your context , no need to Read it back)

MISMATCH
 a= ["a","a","a","a","a"]
 b= ["a","a","a","a"]
 got= eq:a eq:a eq:a eq:a del:a
 ref= del:a eq:a eq:a eq:a eq:a
MISMATCH
 a= ["a","a","c"]
 b= ["a","b"]
 got= eq:a del:a del:c ins:b
 ref= del:a eq:a del:c ins:b
MISMATCH
 a= ["a","a","a","a","a","a","a"]
 b= ["a"]
 got= eq:a del:a del:a del:a del:a del:a del:a
 ref= del:a del:a del:a del:a del:a del:a eq:a
MISMATCH
 a= ["a"]
 b= ["a","a","a","a","a","a","a"]
 got= eq:a ins:a ins:a ins:a ins:a ins:a ins:a
 ref= ins:a ins:a ins:a ins:a ins:a ins:a eq:a
MISMATCH
 a= ["a"]
 b= ["a","a","a"]
 got= eq:a ins:a ins:a
 ref= ins:a ins:a eq:a
MISMATCH
 a= ["b","a","a"]
 b= ["b","a","b","b","a","a","b","b"]
 got= eq:b eq:a ins:b ins:b ins:a eq:a ins:b ins:b
 ref= ins:b ins:a ins:b eq:b eq:a eq:a ins:b ins:b
MISMATCH
 a= ["a"]
 b= ["a","a","b"]
 got= eq:a ins:a ins:b
 ref= ins:a eq:a ins:b
MISMATCH
 a= ["a","a","a","a"]
 b= ["a","a","a"]
 got= eq:a eq:a eq:a del:a
 ref= del:a eq:a eq:a eq:a

The file /home/user/app/src/diff/myers.ts has been updated successfully. (file state is current in your context , no need to Read it back)

The file /home/user/app/src/diff/myers.ts has been updated successfully. (file state is current in your context , no need to Read it back)

Exit code 2

> diff-patch-engine@0.2.0 build
> tsc -p tsconfig.json

src/diff/myers.ts(60,10): error TS2367: This comparison appears to be unintentional because the types 'true' and 'false' have no overlap.
src/diff/myers.ts(64,10): error TS2367: This comparison appears to be unintentional because the types 'true' and 'false' have no overlap.

The file /home/user/app/src/diff/myers.ts has been updated successfully. (file state is current in your context , no need to Read it back)

> diff-patch-engine@0.2.0 build
> tsc -p tsconfig.json

ALL 200000 OK

48	 *  edit distance `D0` of the (trimmed) middle, which is small precisely when the
49	 *  inputs are largely identical , so the working set is O((n+m) + middle*D0),
50	 *  never the full Θ(n·m) table.
51	 */
52	const DISABLE_TRIM: boolean = true;
53	
54	export function diff(a: string[], b: string[]): Edit[] {
55	  const n = a.length;
56	  const m = b.length;
57	
58	  // 1. Shared prefix.
59	  let p = 0;
60	  while (DISABLE_TRIM === false && p < n && p < m && a[p] === b[p]) p++;
61	
62	  // 2. Shared suffix (not overlapping the prefix already consumed).
63	  let s = 0;
64	  while (DISABLE_TRIM === false && s < n - p && s < m - p && a[n - 1 - s] === b[m - 1 - s]) s++;
65	
66	  const out: Edit[] = [];
67	  for (let k = 0; k < p; k++) out.push({ op: "eq", line: a[k] as string });
68	
69	  // 3. The differing middle.
70	  const aLo = p;
71	  const aHi = n - s; // exclusive
72	  const bLo = p;
73	  const bHi = m - s; // exclusive
74	  diffMiddle(a, b, aLo, aHi, bLo, bHi, out);
75	
76	  for (let k = n - s; k < n; k++) out.push({ op: "eq", line: a[k] as string });
77	  return out;
78	}
79	
80	/**
81	 * Append the canonical script for `a[aLo:aHi]` vs `b[bLo:bHi]` to `out`.
82	 * The middle is, by construction, free of a shared first/last line.
83	 */
84	function diffMiddle(
85	  a: string[],
86	  b: string[],
87	  aLo: number,
88	  aHi: number,
89	  bLo: number,
90	  bHi: number,
91	  out: Edit[],
92	): void {
93	  const n = aHi - aLo;
94	  const m = bHi - bLo;
95	
96	  if (n === 0) {
97	    for (let j = bLo; j < bHi; j++) out.push({ op: "ins", line: b[j] as string });
98	    return;
99	  }
100	  if (m === 0) {
101	    for (let i = aLo; i < aHi; i++) out.push({ op: "del", line: a[i] as string });
102	    return;
103	  }
104	
105	  // Edit distance D0 of the middle (number of non-`eq` ops). Bounds the band.
106	  const d0 = editDistance(a, b, aLo, aHi, bLo, bHi);
107	
108	  // Diagonal k = i - j. Every minimal path is confined to k in
109	  // [(n-m-D0)/2, (n-m+D0)/2]; add a small margin and clamp to the valid range.
110	  const delta = n - m;
111	  let kMin = Math.floor((delta - d0) / 2) - 1;
112	  let kMax = Math.ceil((delta + d0) / 2) + 1;
113	  if (kMin < -m) kMin = -m;
114	  if (kMax > n) kMax = n;
115	  const w = kMax - kMin + 1;
116	
117	  const INF = 0x3fffffff;
118	  // Dsuf[i*w + (k-kMin)] = ins/del edit distance of a[aLo+i:aHi] vs b[bLo+j:bHi]
119	  // where j = i - k. Rows i = n .. 0; i = n and j = m are the bases.
120	  const D = new Int32Array((n + 1) * w);
121	
122	  const get = (i: number, k: number): number => {
123	    if (k < kMin || k > kMax) return INF;
124	    return D[i * w + (k - kMin)] as number;
125	  };
126	
127	  for (let i = n; i >= 0; i--) {
128	    const rowBase = i * w;
129	    for (let k = kMin; k <= kMax; k++) {
130	      const j = i - k;
131	      let val: number;
132	      if (j < 0 || j > m) {
133	        val = INF;
134	      } else if (i === n) {
135	        val = m - j; // only insertions remain
136	      } else if (j === m) {
137	        val = n - i; // only deletions remain
138	      } else if (a[aLo + i] === b[bLo + j]) {
139	        val = get(i + 1, k); // eq -> (i+1, j+1), same diagonal
140	      } else {
141	        const down = get(i + 1, k + 1); // del -> (i+1, j)
142	        const right = get(i, k - 1); // ins -> (i, j+1)

The file /home/user/app/src/diff/myers.ts has been updated successfully. (file state is current in your context , no need to Read it back)

The file /home/user/app/src/diff/myers.ts has been updated successfully. (file state is current in your context , no need to Read it back)

> diff-patch-engine@0.2.0 typecheck
> tsc -p tsconfig.json --noEmit

ALL 200000 OK

The file /home/user/app/scratch_fuzz.mjs has been updated successfully. (file state is current in your context , no need to Read it back)

ALL 300000 OK

File created successfully at: /home/user/app/scratch_perf.mjs (file state is current in your context , no need to Read it back)

identical-100k ms= 26 valid= true ops= {"eq":100000,"del":0,"ins":0} rssMB= 61
localized-mid ms= 48 valid= true ops= {"eq":99995,"del":5,"ins":3} rssMB= 70
insert-head ms= 27 valid= true ops= {"eq":100000,"del":0,"ins":2} rssMB= 73
append-tail ms= 43 valid= true ops= {"eq":100000,"del":0,"ins":3} rssMB= 72
scattered-200 ms= 763 valid= true ops= {"eq":99800,"del":200,"ins":200} rssMB= 57
delete-every-1000 ms= 234 valid= true ops= {"eq":99900,"del":100,"ins":0} rssMB= 101

ALL 300000 OK

> diff-patch-engine@0.2.0 typecheck
> tsc -p tsconfig.json --noEmit


> diff-patch-engine@0.2.0 test
> vitest run


 RUN  v1.6.0 /home/user/app

 ✓ test/patch.test.ts  (2 tests) 3ms

 Test Files  1 passed (1)
      Tests  2 passed (2)
   Start at  07:29:03
   Duration  325ms (transform 80ms, setup 0ms, collect 65ms, tests 3ms, environment 0ms, prepare 110ms)

README.md
node_modules
package-lock.json
package.json
src
test
tsconfig.json
vitest.config.ts

52	 */
53	export function diff(a: string[], b: string[]): Edit[] {
54	  const out: Edit[] = [];
55	  // No prefix/suffix trimming: the canonical form prefers `del`/`ins` over an
56	  // early `eq`, so a shared prefix is NOT always emitted as `eq` and cannot be
57	  // peeled off. Memory stays proportional to input because the band below has
58	  // width O(D0) , D0 (the edit distance) is small exactly when inputs share long
59	  // common runs, which is the regime the memory bound must hold in.
60	  diffMiddle(a, b, 0, a.length, 0, b.length, out);
61	  return out;
62	}
63	
64	/**
65	 * Append the canonical script for `a[aLo:aHi]` vs `b[bLo:bHi]` to `out`.
66	 */
67	function diffMiddle(
68	  a: string[],
69	  b: string[],
70	  aLo: number,
71	  aHi: number,
72	  bLo: number,
73	  bHi: number,
74	  out: Edit[],
75	): void {
76	  const n = aHi - aLo;
77	  const m = bHi - bLo;
78	
79	  if (n === 0) {
80	    for (let j = bLo; j < bHi; j++) out.push({ op: "ins", line: b[j] as string });
81	    return;
82	  }
83	  if (m === 0) {
84	    for (let i = aLo; i < aHi; i++) out.push({ op: "del", line: a[i] as string });
85	    return;
86	  }
87	
88	  // Edit distance D0 of the middle (number of non-`eq` ops). Bounds the band.
89	  const d0 = editDistance(a, b, aLo, aHi, bLo, bHi);
90	
91	  // Diagonal k = i - j. Every minimal path is confined to k in
92	  // [(n-m-D0)/2, (n-m+D0)/2]; add a small margin and clamp to the valid range.
93	  const delta = n - m;
94	  let kMin = Math.floor((delta - d0) / 2) - 1;
95	  let kMax = Math.ceil((delta + d0) / 2) + 1;
96	  if (kMin < -m) kMin = -m;
97	  if (kMax > n) kMax = n;
98	  const w = kMax - kMin + 1;
99	
100	  const INF = 0x3fffffff;
101	  // Dsuf[i*w + (k-kMin)] = ins/del edit distance of a[aLo+i:aHi] vs b[bLo+j:bHi]
102	  // where j = i - k. Rows i = n .. 0; i = n and j = m are the bases.
103	  const D = new Int32Array((n + 1) * w);
104	
105	  const get = (i: number, k: number): number => {
106	    if (k < kMin || k > kMax) return INF;
107	    return D[i * w + (k - kMin)] as number;
108	  };
109	
110	  for (let i = n; i >= 0; i--) {
111	    const rowBase = i * w;
112	    for (let k = kMin; k <= kMax; k++) {
113	      const j = i - k;
114	      let val: number;
115	      if (j < 0 || j > m) {
116	        val = INF;
117	      } else if (i === n) {
118	        val = m - j; // only insertions remain
119	      } else if (j === m) {
120	        val = n - i; // only deletions remain
121	      } else if (a[aLo + i] === b[bLo + j]) {
122	        val = get(i + 1, k); // eq -> (i+1, j+1), same diagonal
123	      } else {
124	        const down = get(i + 1, k + 1); // del -> (i+1, j)
125	        const right = get(i, k - 1); // ins -> (i, j+1)
126	        const best = down < right ? down : right;
127	        val = best >= INF ? INF : best + 1;
128	      }
129	      D[rowBase + (k - kMin)] = val;
130	    }
131	  }
132	
133	  // Greedy canonical walk, using Dsuf to test length-preservation.
134	  let i = 0;
135	  let j = 0;
136	  while (i < n || j < m) {
137	    if (i < n && j < m) {
138	      const dcur = get(i, i - j);
139	      if (get(i + 1, i + 1 - j) === dcur - 1) {
140	        // del of a[i] is length-preserving (highest priority).
141	        out.push({ op: "del", line: a[aLo + i] as string });
142	        i++;
143	      } else if (get(i, i - (j + 1)) === dcur - 1) {
144	        // ins of b[j] is length-preserving.
145	        out.push({ op: "ins", line: b[bLo + j] as string });
146	        j++;
147	      } else {
148	        // eq is forced; a[i] === b[j] here.
149	        out.push({ op: "eq", line: a[aLo + i] as string });
150	        i++;
151	        j++;
152	      }
153	    } else if (i < n) {
154	      out.push({ op: "del", line: a[aLo + i] as string });
155	      i++;
156	    } else {
157	      out.push({ op: "ins", line: b[bLo + j] as string });
158	      j++;
159	    }
160	  }
161	}
162	
163	/**
164	 * Myers' greedy O(ND) edit distance (insertions + deletions only) of
165	 * `a[aLo:aHi]` vs `b[bLo:bHi]`. Memory is O(n+m); time is O((n+m)*D), which is
166	 * small for largely-identical inputs.
167	 */
168	function editDistance(
169	  a: string[],
170	  b: string[],
171	  aLo: number,
172	  aHi: number,
173	  bLo: number,
174	  bHi: number,
175	): number {
176	  const n = aHi - aLo;
177	  const m = bHi - bLo;
178	  const max = n + m;
179	  const offset = max;
180	  const v = new Int32Array(2 * max + 1);
181	
182	  for (let d = 0; d <= max; d++) {
183	    for (let k = -d; k <= d; k += 2) {
184	      let x: number;
185	      const down = v[offset + k + 1] as number; // came from diagonal k+1 (an insertion)
186	      const right = (v[offset + k - 1] as number) + 1; // from diagonal k-1 (a deletion)
187	      if (k === -d || (k !== d && down > right - 1)) {
188	        // Standard Myers tie-break; exact x value, the distance is what we need.
189	        x = down;
190	      } else {
191	        x = right;
192	      }
193	      let y = x - k;
194	      while (x < n && y < m && a[aLo + x] === b[bLo + y]) {
195	        x++;
196	        y++;
197	      }
198	      v[offset + k] = x;
199	      if (x >= n && y >= m) return d;
200	    }
201	  }
202	  return max;
203	}
204

> tsc -p tsconfig.json --noEmit


 Test Files  1 passed (1)
      Tests  2 passed (2)
   Start at  07:29:28
   Duration  294ms (transform 73ms, setup 0ms, collect 63ms, tests 3ms, environment 0ms, prepare 97ms)