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

/home/user/app/src:
diff
index.ts

/home/user/app/src/diff:
errors.ts
myers.ts
patch.ts
text.ts
types.ts
---
import type { Edit } from "./types.js";

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

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

{
  "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"
  }
}
---TSCONFIG---
{
  "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"]
}

<tool_use_error>File has not been read yet. Read it first before writing to it.</tool_use_error>

1	import type { Edit } from "./types.js";
2	
3	/**
4	 * Compute the canonical minimal line-level edit script transforming `a` into `b`.
5	 *

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

patch.test.ts
npm WARN exec The following package was not found and will be installed: tsx@4.22.4

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

ALL OK

node: bad option: --experimental-strip-types

node:internal/modules/cjs/loader:1051
  throw err;
  ^

Error: Cannot find module '/home/user/app/node_modules/.bin/tsx'
    at Module._resolveFilename (node:internal/modules/cjs/loader:1048:15)
    at Module._load (node:internal/modules/cjs/loader:901:27)
    at Function.executeUserEntryPoint [as runMain] (node:internal/modules/run_main:83:12)
    at node:internal/main/run_main_module:23:47 {
  code: 'MODULE_NOT_FOUND',
  requireStack: []
}

Node.js v20.9.0

valid= true ops= 100023 time(ms)= 77.523324 heapMB= 22.8
/home/user/app/src/diff/myers.ts:138
  const L = new Int32Array((na + 1) * width);
            ^


RangeError: Array buffer allocation failed
    at new ArrayBuffer (<anonymous>)
    at new Int32Array (<anonymous>)
    at diffCore (/home/user/app/src/diff/myers.ts:138:13)
    at diff (/home/user/app/src/diff/myers.ts:110:3)
    at file:///tmp/perf.mjs:25:10
    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

UNSOUND cand>act 3 0 ["a","b","a"] ["a","b","a","b","b","b","a","b","a"]
UNSOUND cand>act 4 3 ["a","","c","b","","b","","b"] ["a","","c","b","b","","b","","a"]
UNSOUND cand>act 3 0 ["a","a","a"] ["a","a","a","a","a","a","b","a","a"]
UNSOUND cand>act 7 4 ["b","a","a","b","a","a","a"] ["b","a","a","b","a","a","a","b","b","b","a"]
UNSOUND cand>act 3 0 ["b","a","a"] ["b","a","a","b","a","a","a"]
unsound(bad)= 75035 conservative(missed)= 74712

snake-trim mismatches: 59591 /300000
a= ["b",""] b= ["b","a","b","a","c","a"]
 exp ["insb","insa","eqb","del","insa","insc","insa"]
 got ["eqb","del","insa","insb","insa","insc","insa"]
a= ["a","","a","a",""] b= ["a","c","","c","c"]
 exp ["dela","del","dela","eqa","insc","eq","insc","insc"]
 got ["eqa","del","dela","dela","insc","eq","insc","insc"]
a= ["a","a","b"] b= ["a","a","b","b","a","a"]
 exp ["eqa","eqa","insb","eqb","insa","insa"]
 got ["eqa","eqa","eqb","insb","insa","insa"]
a= ["a","b","a","b","b","b"] b= ["a","b","a","a","b","a"]
 exp ["eqa","eqb","insa","eqa","delb","delb","eqb","insa"]
 got ["eqa","eqb","eqa","delb","delb","insa","eqb","insa"]
a= ["","","","","a","","a"] b= ["","b","b",""]
 exp ["del","del","del","eq","dela","insb","insb","eq","dela"]
 got ["eq","del","del","del","dela","insb","insb","eq","dela"]
a= ["","","b","b","b"] b= ["","a"]
 exp ["del","eq","delb","delb","delb","insa"]
 got ["eq","del","delb","delb","delb","insa"]
a= ["a"] b= ["a","","","a","b","b"]
 exp ["insa","ins","ins","eqa","insb","insb"]
 got ["eqa","ins","ins","insa","insb","insb"]
a= ["a","a","a","b"] b= ["a","a","a","b","b"]
 exp ["eqa","eqa","eqa","insb","eqb"]
 got ["eqa","eqa","eqa","eqb","insb"]

{"smallest":31296,"largest":17563,"total":38887}
smallest mismatches:
[["c","c"],["c","a","a","c","b","b","c","c"],1,7,[1,2,3,4,5,6,7]]
[["a","b","a","b","a","a","b"],["b","b","b","a","b","a"],3,4,[1,2,4]]
[["a","a"],["a","b","a","a"],1,3,[1,2,3]]
[["b","b","a","b","a","b","b"],["b","a","a","b","a","a"],3,3,[2,3,5]]
[["b","b","a","b","b","b","b"],["a","a","a"],3,3,[1,2,3]]
[["c","a","b","b","a","b","a"],["c","c","a","c","c","b"],3,2,[1,2,3,4,5,6]]