diff.ts · Source

diff.tspackages/editor/src/diff.tsraw ← src6,736 B← Back to the app
1/**
2 * @factory/editor — TASK-0123: deterministic word-level diff.
3 *
4 * `wordDiff(oldText, newText)` splits both texts into words (whitespace-
5 * separated, preserving the whitespace runs as `same` segments between them)
6 * and returns the minimal edit script via LCS (longest common subsequence) on
7 * the word lists:
8 *
9 *   [{ type: "same", text: "Hello " }, { type: "del", text: "old" },
10 *    { type: "add", text: "new" }, { type: "same", text: " world." }]
11 *
12 * Pure + deterministic — the UI renders the script as spans (`add` =
13 * highlighted insertion, `del` = struck-through deletion) and the unit
14 * tests pin byte-stable output. For very large texts (> 2000 words each)
15 * LCS is quadratic, so it degrades to `del(old) + add(new)` — still
16 * deterministic, still correct as a diff.
17 */
18 
19export type DiffSegment = {
20  type: "same" | "add" | "del";
21  text: string;
22};
23 
24/** Split text into words + the whitespace between them.
25 *  `split("a  b\n")` → `[{w:"a"},{s:"  "},{w:"b"},{s:"\n"}]`. */
26function tokenize(text: string): Array<{ kind: "w" | "s"; value: string }> {
27  const out: Array<{ kind: "w" | "s"; value: string }> = [];
28  if (!text) return out;
29  const re = /(\s+)/g;
30  let last = 0;
31  let m: RegExpExecArray | null;
32  while ((m = re.exec(text)) !== null) {
33    if (m.index > last) out.push({ kind: "w", value: text.slice(last, m.index) });
34    out.push({ kind: "s", value: m[0] });
35    last = m.index + m[0].length;
36  }
37  if (last < text.length) out.push({ kind: "w", value: text.slice(last) });
38  return out;
39}
40 
41/** LCS edit script over two word arrays → segments.
42 *  Standard DP with a back-pointer walk; O(n·m) memory/bounded by the
43 *  2000-word guard in {@link wordDiff}. */
44function lcsSegments(oldWords: string[], newWords: string[]): Array<{ type: "same" | "add" | "del"; word: string }> {
45  const n = oldWords.length;
46  const m = newWords.length;
47  // dp[i][j] = LCS length of oldWords[i:] vs newWords[j:]
48  const dp: number[][] = Array.from({ length: n + 1 }, () => new Array<number>(m + 1).fill(0));
49  for (let i = n - 1; i >= 0; i--) {
50    for (let j = m - 1; j >= 0; j--) {
51      dp[i]![j] = oldWords[i] === newWords[j] ? dp[i + 1]![j + 1]! + 1 : Math.max(dp[i + 1]![j]!, dp[i]![j + 1]!);
52    }
53  }
54  const out: Array<{ type: "same" | "add" | "del"; word: string }> = [];
55  let i = 0;
56  let j = 0;
57  while (i < n && j < m) {
58    if (oldWords[i] === newWords[j]) {
59      out.push({ type: "same", word: oldWords[i]! });
60      i++;
61      j++;
62    } else if (dp[i + 1]![j]! >= dp[i]![j + 1]!) {
63      out.push({ type: "del", word: oldWords[i]! });
64      i++;
65    } else {
66      out.push({ type: "add", word: newWords[j]! });
67      j++;
68    }
69  }
70  while (i < n) out.push({ type: "del", word: oldWords[i++]! });
71  while (j < m) out.push({ type: "add", word: newWords[j++]! });
72  return out;
73}
74 
75/** Merge per-word segments back into runs, re-attaching whitespace so both
76 *  reconstruction invariants hold EXACTLY:
77 *    same+del (their whitespace) == oldText
78 *    same+add (their whitespace) == newText
79 *  Rule: a word carries the whitespace that FOLLOWS it in its own source
80 *  string (old words → old whitespace, new words → new whitespace). `same`
81 *  words are old-side for the old text and new-side for the new text, so
82 *  they are emitted with BOTH whitespace runs: `word + oldWS` (del/same
83 *  side) followed by `newWS` (add/same side) when they differ — the UI
84 *  renders whitespace as plain text either way. */
85function mergeToSegments(
86  oldText: string,
87  newText: string,
88  wordScript: Array<{ type: "same" | "add" | "del"; word: string }>,
89): DiffSegment[] {
90  const oldTok = tokenize(oldText);
91  const newTok = tokenize(newText);
92  const oldWords = oldTok.filter((t) => t.kind === "w").map((t) => t.value);
93  const newWords = newTok.filter((t) => t.kind === "w").map((t) => t.value);
94  const afterOf = (tok: Array<{ kind: "w" | "s"; value: string }>): string[] => {
95    const out: string[] = [];
96    tok.forEach((t, idx) => {
97      if (t.kind === "w") out.push(tok[idx + 1]?.kind === "s" ? tok[idx + 1]!.value : "");
98    });
99    return out;
100  };
101  const oldAfter = afterOf(oldTok);
102  const newAfter = afterOf(newTok);
103 
104  const out: DiffSegment[] = [];
105  const push = (type: DiffSegment["type"], text: string) => {
106    if (!text) return;
107    const lastSeg = out[out.length - 1];
108    if (lastSeg && lastSeg.type === type) lastSeg.text += text;
109    else out.push({ type, text });
110  };
111 
112  let oi = 0;
113  let ni = 0;
114  for (const step of wordScript) {
115    if (step.type === "same") {
116      const oldWS = oldAfter[oi]!;
117      const newWS = newAfter[ni]!;
118      push("same", oldWords[oi]!);
119      if (oldWS === newWS) {
120        push("same", oldWS);
121      } else {
122        // spacing differs around an unchanged word: the old spacing is a
123        // deletion, the new spacing an insertion — both invariants hold.
124        push("del", oldWS);
125        push("add", newWS);
126      }
127      oi++;
128      ni++;
129    } else if (step.type === "del") {
130      push("del", oldWords[oi]! + oldAfter[oi]!);
131      oi++;
132    } else {
133      push("add", newWords[ni]! + newAfter[ni]!);
134      ni++;
135    }
136  }
137  return out;
138}
139 
140/** Quadratic guard: LCS over > 2000 words per side would be > 4M cells —
141 *  above that we degrade to full-replace (still deterministic + correct). */
142const MAX_LCS_WORDS = 2000;
143 
144/** Diff `oldText` → `newText` as a minimal word-level edit script.
145 *  Pure/deterministic; empty inputs yield `[]` (empty old → all add). */
146export function wordDiff(oldText: string, newText: string): DiffSegment[] {
147  if (oldText === newText) return oldText ? [{ type: "same", text: oldText }] : [];
148  const oldTok = tokenize(oldText);
149  const newTok = tokenize(newText);
150  const oldWords = oldTok.filter((t) => t.kind === "w").map((t) => t.value);
151  const newWords = newTok.filter((t) => t.kind === "w").map((t) => t.value);
152  if (oldWords.length === 0) return newText ? [{ type: "add", text: newText }] : [];
153  if (newWords.length === 0) return oldText ? [{ type: "del", text: oldText }] : [];
154  if (oldWords.length > MAX_LCS_WORDS || newWords.length > MAX_LCS_WORDS) {
155    return [
156      { type: "del", text: oldText },
157      { type: "add", text: newText },
158    ];
159  }
160  return mergeToSegments(oldText, newText, lcsSegments(oldWords, newWords));
161}
162 
163/** Reconstruct the source/new text from a diff script — invariant helpers
164 *  for the unit tests (same+del = old, same+add = new). */
165export function reconstructOld(segments: DiffSegment[]): string {
166  return segments.filter((s) => s.type !== "add").map((s) => s.text).join("");
167}
168 
169export function reconstructNew(segments: DiffSegment[]): string {
170  return segments.filter((s) => s.type !== "del").map((s) => s.text).join("");
171}
172