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

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

test:
patch.test.ts
---find specs---
./test/patch.test.ts
---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"]
}

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

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

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

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)

File created successfully at: /home/user/app/scratch.test.ts (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)

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/scratch.test.ts has been updated successfully. (file state is current in your context , no need to Read it back)

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

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

RUN  v1.6.0 /home/user/app

filter:  scratch
include: test/**/*.test.ts
exclude:  **/node_modules/**, **/dist/**, **/cypress/**, **/.{idea,git,cache,output,temp}/**, **/{karma,rollup,webpack,vite,vitest,jest,ava,babel,nyc,cypress,tsup,build,eslint,prettier}.config.*
watch exclude:  **/node_modules/**, **/dist/**

No test files found, exiting with code 1

Object {
      "line": "c",
      "op": "del",
    },
    Object {
      "line": "a",
-     "op": "eq",
+     "op": "del",
    },
    Object {
      "line": "c",
      "op": "del",
    },
  ]

 ❯ test/scratch.test.ts:66:21
     64|         expect(got.filter((e) => e.op !== "eq").length).toBe(a.length …
     65|         // canonical
     66|         expect(got).toEqual(canonicalRef(a, b));
       |                     ^
     67|       }
     68|     }

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯[1/1]⎯

 Test Files  1 failed (1)
      Tests  1 failed | 1 passed (2)
   Start at  06:36:56
   Duration  415ms (transform 116ms, setup 0ms, collect 121ms, tests 19ms, environment 0ms, prepare 116ms)

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

1	import { describe, expect, it } from "vitest";
2	import { applyPatch } from "../src/diff/patch.js";
3	import { diff } from "../src/diff/myers.js";
4	import type { Edit } from "../src/diff/types.js";
5

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

CAP 8000000 A ["a","c","a","c"] B ["a"]
got ["eqa","delc","dela","delc"]
ref ["dela","delc","eqa","delc"]

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)

❯ test/scratch.test.ts  (2 tests | 1 failed) 190ms
   ❯ test/scratch.test.ts > diff validation > matches canonical ref + valid + minimal across random inputs (both paths)
⎯⎯⎯⎯⎯⎯⎯ Failed Tests 1 ⎯⎯⎯⎯⎯⎯⎯
 FAIL  test/scratch.test.ts > diff validation > matches canonical ref + valid + minimal across random inputs (both paths)
    167|  * row vectors (forward / prefix orientation).
 Test Files  1 failed (1)
      Tests  1 failed | 1 passed (2)

(Bash completed with no output)

===

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

(Bash completed with no output)

(Bash completed with no output)

RUN  v1.6.0 /home/user/app

 ❯ test/scratch.test.ts  (2 tests | 1 failed) 220ms
   ❯ test/scratch.test.ts > diff validation > matches canonical ref + valid + minimal across random inputs (both paths)
     → Maximum call stack size exceeded

⎯⎯⎯⎯⎯⎯⎯ Failed Tests 1 ⎯⎯⎯⎯⎯⎯⎯

 FAIL  test/scratch.test.ts > diff validation > matches canonical ref + valid + minimal across random inputs (both paths)
RangeError: Maximum call stack size exceeded
 ❯ lcsRowForward src/diff/myers.ts:169:10
    167|  * row vectors (forward / prefix orientation).
    168|  */
    169| function lcsRowForward(
       |          ^
    170|   a: string[],
    171|   ai0: number,
 ❯ diffRange src/diff/myers.ts:99:19
 ❯ diffRange src/diff/myers.ts:114:3
 ❯ diffRange src/diff/myers.ts:114:3
 ❯ diffRange src/diff/myers.ts:114:3
 ❯ diffRange src/diff/myers.ts:114:3
 ❯ diffRange src/diff/myers.ts:114:3
 ❯ diffRange src/diff/myers.ts:114:3
 ❯ diffRange src/diff/myers.ts:114:3
 ❯ diffRange src/diff/myers.ts:114:3

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯[1/1]⎯

 Test Files  1 failed (1)
      Tests  1 failed | 1 passed (2)
   Start at  06:41:17
   Duration  563ms (transform 99ms, setup 0ms, collect 106ms, tests 220ms, environment 0ms, prepare 102ms)

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)

❯ test/scratch.test.ts  (2 tests | 1 failed) 162ms
     → MISMATCH cap=1 A=["a","c","b","c"] B=["b","a","a","b","a"] got=["insb","eqa","delc","insa","eqb","delc","insa"] ref=["insb","insa","eqa","delc","eqb","delc","insa"]
⎯⎯⎯⎯⎯⎯⎯ Failed Tests 1 ⎯⎯⎯⎯⎯⎯⎯

62	
63	/**
64	 * Largest rectangle area handled by the dense suffix-LCS table. At ~8e6 the
65	 * `Int32Array` is ~32 MB; bigger rectangles use the linear-space path.
66	 */
67	const AREA_CAP = 8_000_000;
68	
69	/** Emit the canonical script for `a[ai0:ai1]` vs `b[bj0:bj1]` into `out`. */
70	function diffRange(
71	  a: string[],
72	  b: string[],
73	  ai0: number,
74	  ai1: number,
75	  bj0: number,
76	  bj1: number,
77	  out: Edit[],
78	): void {
79	  const n = ai1 - ai0;
80	  const m = bj1 - bj0;
81	
82	  if (n === 0) {
83	    for (let j = bj0; j < bj1; j++) out.push({ op: "ins", line: b[j] as string });
84	    return;
85	  }
86	  if (m === 0) {
87	    for (let i = ai0; i < ai1; i++) out.push({ op: "del", line: a[i] as string });
88	    return;
89	  }
90	
91	  if (n === 1 || n * m <= ((globalThis as Record<string, unknown>).__DIFF_AREA_CAP as number ?? AREA_CAP)) {
92	    diffDense(a, b, ai0, ai1, bj0, bj1, out);
93	    return;
94	  }
95	
96	  // Linear-space Hirschberg split. n >= 2 here (m <= input length keeps n*m
97	  // above the cap only when n is large), so ai0 < mid < ai1.
98	  const mid = (ai0 + ai1) >> 1;
99	  const forward = lcsRowForward(a, ai0, mid, b, bj0, bj1);
100	  const backward = lcsRowBackward(a, mid, ai1, b, bj0, bj1);
101	
102	  let best = -1;
103	  let bestC = 0;
104	  for (let c = 0; c <= m; c++) {
105	    const s = (forward[c] as number) + (backward[c] as number);
106	    if (s > best) {
107	      best = s;
108	      bestC = c;
109	    }
110	  }
111	  const splitB = bj0 + bestC;
112	
113	  diffRange(a, b, ai0, mid, bj0, splitB, out);
114	  diffRange(a, b, mid, ai1, splitB, bj1, out);
115	}
116	
117	/** Dense suffix-LCS table + canonical greedy walk. */
118	function diffDense(
119	  a: string[],
120	  b: string[],
121	  ai0: number,