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	/**
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

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

errors.ts
myers.ts
patch.ts
text.ts
types.ts
---
/**
 * Typed errors for the diff/patch engine. A single class with a stable `code`
 * discriminator keeps call sites and tests decoupled from message wording.
 */
export type PatchErrorCode =
---package---
{
  "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

{
  "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"]
}
---text.ts---
/**
 * Text <-> lines conversion for the diff engine.
 *
 * `splitLines` splits on "\n" and keeps every line as a separate entry. A
 * trailing newline yields a final empty entry preserved by `joinLines`, so the
 * round-trip `joinLines(splitLines(t)) === t` holds for any input (including the
 * empty string, which becomes `[""]`).
 *
 * Provided complete.
 */
export function splitLines(text: string): string[] {
  return text.split("\n");
}

export function joinLines(lines: string[]): string {
  return lines.join("\n");
}
---tests dir---
/home/user/app/test:
patch.test.ts
/home/user/app/test/patch.test.ts

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

===TEST===

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


 RUN  v1.6.0 /home/user/app

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

 Test Files  1 passed (1)
      Tests  2 passed (2)
   Start at  05:19:42
   Duration  380ms (transform 91ms, setup 0ms, collect 84ms, tests 4ms, environment 0ms, prepare 138ms)

node:internal/process/esm_loader:40
      internalBinding('errors').triggerUncaughtException(
                                ^
Error [ERR_MODULE_NOT_FOUND]: Cannot find module '/tmp/src/diff/myers.ts' imported from /tmp/verify.mjs
Did you mean to import ../../home/user/app/src/diff/myers.ts?
    at new NodeError (node:internal/errors:406:5)
    at finalizeResolution (node:internal/modules/esm/resolve:233:11)
    at moduleResolve (node:internal/modules/esm/resolve:845:10)
    at defaultResolve (node:internal/modules/esm/resolve:1043:11)
    at nextResolve (node:internal/modules/esm/hooks:833:28)
    at resolveBase (file:///home/user/.npm/_npx/fd45a72a545557e9/node_modules/tsx/dist/register-CqMfTiWi.mjs:2:8141)
    at resolveDirectory (file:///home/user/.npm/_npx/fd45a72a545557e9/node_modules/tsx/dist/register-CqMfTiWi.mjs:2:9227)
    at resolveTsPaths (file:///home/user/.npm/_npx/fd45a72a545557e9/node_modules/tsx/dist/register-CqMfTiWi.mjs:2:10757)
    at resolve2 (file:///home/user/.npm/_npx/fd45a72a545557e9/node_modules/tsx/dist/register-CqMfTiWi.mjs:2:11938)
    at nextResolve (node:internal/modules/esm/hooks:833:28) {
  url: 'file:///tmp/src/diff/myers.ts',
  code: 'ERR_MODULE_NOT_FOUND'
}

Node.js v20.9.0

small random tests: 20000 fails: 0

NONCANON t 4 lenA 4305
 first diff at 2124 got {"op":"eq","line":"S2124"} ref {"op":"del","line":"S2124"}
strip-path stress fails: 2
/home/user/app/src/diff/myers.ts:113
  const L = new Int32Array((N + 1) * W);
            ^


RangeError: Array buffer allocation failed
    at new ArrayBuffer (<anonymous>)
    at new Int32Array (<anonymous>)
    at canonicalWalk (/home/user/app/src/diff/myers.ts:113:13)
    at diff (/home/user/app/src/diff/myers.ts:88:21)
    at file:///tmp/verify2.mjs:36:9
    at ModuleJob.run (node:internal/modules/esm/module_job:217:25)
    at async ModuleLoader.import (node:internal/modules/esm/loader:316:24)
    at async loadESM (node:internal/process/esm_loader:34:7)
    at async handleMainPromise (node:internal/modules/run_main:66:12)

Node.js v20.9.0

NONCANON ["d","c","c","d"] ["d","a"]
 my   [{"op":"eq","line":"d"},{"op":"del","line":"c"},{"op":"del","line":"c"},{"op":"del","line":"d"},{"op":"ins","line":"a"}]
 gold [{"op":"del","line":"d"},{"op":"del","line":"c"},{"op":"del","line":"c"},{"op":"eq","line":"d"},{"op":"ins","line":"a"}]
NONCANON ["b","a","a","a","a","b","b"] ["b"]
 my   [{"op":"eq","line":"b"},{"op":"del","line":"a"},{"op":"del","line":"a"},{"op":"del","line":"a"},{"op":"del","line":"a"},{"op":"del","line":"b"},{"op":"del","line":"b"}]
 gold [{"op":"del","line":"b"},{"op":"del","line":"a"},{"op":"del","line":"a"},{"op":"del","line":"a"},{"op":"del","line":"a"},{"op":"del","line":"b"},{"op":"eq","line":"b"}]
NONCANON ["d","a","b","a","d","b"] ["b","d","b","e","c","b"]
 my   [{"op":"del","line":"d"},{"op":"del","line":"a"},{"op":"eq","line":"b"},{"op":"del","line":"a"},{"op":"eq","line":"d"},{"op":"eq","line":"b"},{"op":"ins","line":"e"},{"op":"ins","line":"c"},{"op":"ins","line":"b"}]
 gold [{"op":"del","line":"d"},{"op":"del","line":"a"},{"op":"eq","line":"b"},{"op":"del","line":"a"},{"op":"eq","line":"d"},{"op":"ins","line":"b"},{"op":"ins","line":"e"},{"op":"ins","line":"c"},{"op":"eq","line":"b"}]
NONCANON ["b","a","b","a","a","b","a"] ["b","a","a","b","a","b","b"]
 my   [{"op":"eq","line":"b"},{"op":"eq","line":"a"},{"op":"del","line":"b"},{"op":"del","line":"a"},{"op":"eq","line":"a"},{"op":"eq","line":"b"},{"op":"eq","line":"a"},{"op":"ins","line":"b"},{"op":"ins","line":"b"}]
 gold [{"op":"del","line":"b"},{"op":"del","line":"a"},{"op":"eq","line":"b"},{"op":"eq","line":"a"},{"op":"eq","line":"a"},{"op":"eq","line":"b"},{"op":"eq","line":"a"},{"op":"ins","line":"b"},{"op":"ins","line":"b"}]
tot 50000 invalid 0 nonmin 0 noncanon 11689

strip vs gold: tot 50000 noncanon 9897
a ["a","c","b","a","d","a","d","a"] b ["a","c","c","d","d","d","c"]
 strip ["eqa","eqc","delb","dela","insc","insd","eqd","dela","eqd","dela","insc"]
 gold  ["eqa","insc","eqc","delb","dela","insd","eqd","dela","eqd","dela","insc"]
a ["c","a","b","c","b","b","d"] b ["c","b"]
 strip ["eqc","dela","delb","delc","delb","eqb","deld"]
 gold  ["delc","dela","delb","eqc","delb","eqb","deld"]
a ["c","c"] b ["c","a","a","b","b"]
 strip ["eqc","delc","insa","insa","insb","insb"]
 gold  ["delc","eqc","insa","insa","insb","insb"]
a ["b","a","b","a","a","b","a"] b ["b","b","a"]
 strip ["eqb","dela","delb","dela","dela","eqb","eqa"]
 gold  ["delb","dela","eqb","dela","dela","eqb","eqa"]
a ["a","d","b"] b ["a","a","a","d","d","c","a"]
 strip ["eqa","insa","insa","insd","eqd","delb","insc","insa"]
 gold  ["insa","insa","eqa","insd","eqd","delb","insc","insa"]
a ["a","b","a","b","a","a","a","a"] b ["a"]
 strip ["eqa","delb","dela","delb","dela","dela","dela","dela"]
 gold  ["dela","delb","dela","delb","dela","dela","dela","eqa"]

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

1. small-path dense: fails 0
2. large strip distinct-core vs gold: fails 0
3. concentrated 1e5: valid true ms 22.2 heapMB 23 edits 100033

1. small-path dense: fails 0
2. large strip distinct-core vs gold: fails 0
3. concentrated 1e5: valid true ms 20.2 heapMB 23 edits 100033

exit 0
Shell cwd was reset to /home/user/app

node:internal/errors:497
    ErrorCaptureStackTrace(err);
    ^

TypeError [ERR_UNKNOWN_FILE_EXTENSION]: Unknown file extension ".ts" for /home/user/app/src/diff/myers.ts
    at new NodeError (node:internal/errors:406:5)
    at Object.getFileProtocolModuleFormat [as file:] (node:internal/modules/esm/get_format:99:9)
    at defaultGetFormat (node:internal/modules/esm/get_format:142:36)
    at defaultLoad (node:internal/modules/esm/load:120:20)
    at ModuleLoader.load (node:internal/modules/esm/loader:396:13)
    at ModuleLoader.moduleProvider (node:internal/modules/esm/loader:278:56)
    at new ModuleJob (node:internal/modules/esm/module_job:65:26)
    at #createModuleJob (node:internal/modules/esm/loader:290:17)
    at ModuleLoader.getJobFromResolveResult (node:internal/modules/esm/loader:248:34)
    at ModuleLoader.getModuleJob (node:internal/modules/esm/loader:229:17) {
  code: 'ERR_UNKNOWN_FILE_EXTENSION'
}

Node.js v20.9.0
---try direct tsx---
rc=137
Shell cwd was reset to /home/user/app

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

1. small-path dense: fails 0
2. large strip distinct-core vs gold: fails 0
3. concentrated 1e5: valid true ms 16.2 heapMB 23 edits 100033
4. scattered 1e5: valid true ms 61.4 heapMB 37
5. identical 1e5: alleq true len 100000 ms 8.7
   empties: [] [{"op":"eq","line":""}] 1 1
rc=0

> vitest run


 RUN  v1.6.0 /home/user/app

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

 Test Files  1 passed (1)
      Tests  2 passed (2)
   Start at  05:33:22
   Duration  342ms (transform 70ms, setup 0ms, collect 69ms, tests 2ms, environment 0ms, prepare 113ms)

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