components/draft-compare/draft-compare-diff.ts

Functions

Imports

It imports no other module of this repo. Imported by components/draft-compare/draft-compare-render.ts, components/draft-compare/draft-compare.ts.

Source

1// Draft compare's diff: by sentence, then by word, and the counts (draft-compare.ts).
2
3// ---------------------------------------------------------------------------------------
4// The diff
5// ---------------------------------------------------------------------------------------
6
7export type Op = "same" | "ins" | "del";
8
9// One stretch of a sentence: unchanged text, an insertion (only in `after`) or a deletion
10// (only in `before`). Joining the `same` and `del` parts gives the before text; joining the
11// `same` and `ins` parts gives the after text, up to whitespace.
12export interface WordPart {
13  op: Op;
14  text: string;
15}
16
17interface Token {
18  text: string;
19  // The whitespace before it ("" when it touches the token before).
20  lead: string;
21}
22
23// A word (letters and digits, with an inner apostrophe or hyphen), or one punctuation mark.
24const TOKEN = /(\s*)([\p{L}\p{N}]+(?:['’-][\p{L}\p{N}]+)*|[^\s\p{L}\p{N}])/gu;
25const WORDY = /[\p{L}\p{N}]/u;
26
27export function tokenize(s: string): Token[] {
28  const out: Token[] = [];
29  for (const m of s.matchAll(TOKEN)) out.push({ lead: m[1] ?? "", text: m[2] ?? "" });
30  return out;
31}
32
33// How many words a string holds (punctuation and spacing do not count).
34export function countWords(s: string): number {
35  let n = 0;
36  for (const t of tokenize(s)) if (WORDY.test(t.text)) n++;
37  return n;
38}
39
40export interface DiffOptions {
41  // The most edits (insertions plus deletions) the search will look for before it gives up
42  // and calls the whole stretch replaced. Bounds memory on two texts with nothing in common.
43  maxEdits?: number;
44}
45
46const DEFAULT_MAX_EDITS = 2000;
47
48// The longest common subsequence of two lists of strings, as index pairs, by Myers' O(ND)
49// algorithm. Equal runs at either end are taken first. Returns null when more than
50// `maxEdits` edits would be needed.
51export function commonSubsequence(a: readonly string[], b: readonly string[], maxEdits = DEFAULT_MAX_EDITS): Array<[number, number]> | null {
52  let lo = 0;
53  while (lo < a.length && lo < b.length && a[lo] === b[lo]) lo++;
54  let ea = a.length;
55  let eb = b.length;
56  while (ea > lo && eb > lo && a[ea - 1] === b[eb - 1]) {
57    ea--;
58    eb--;
59  }
60  const out: Array<[number, number]> = [];
61  for (let i = 0; i < lo; i++) out.push([i, i]);
62  const mid = middle(a.slice(lo, ea), b.slice(lo, eb), maxEdits);
63  if (mid === null) return null;
64  for (const [x, y] of mid) out.push([x + lo, y + lo]);
65  for (let i = 0; i < a.length - ea; i++) out.push([ea + i, eb + i]);
66  return out;
67}
68
69function middle(a: readonly string[], b: readonly string[], maxEdits: number): Array<[number, number]> | null {
70  const n = a.length;
71  const m = b.length;
72  if (n === 0 || m === 0) return [];
73  const limit = Math.min(n + m, maxEdits);
74  const off = limit + 1;
75  const v = new Int32Array(2 * limit + 3);
76  // trace[d] is v as round d began, for k in -d-1 .. d+1 (read as snap[k + d + 1]).
77  const trace: Int32Array[] = [];
78  let found = -1;
79  for (let d = 0; d <= limit && found < 0; d++) {
80    trace.push(v.slice(off - d - 1, off + d + 2));
81    for (let k = -d; k <= d; k += 2) {
82      let x = k === -d || (k !== d && (v[off + k - 1] ?? 0) < (v[off + k + 1] ?? 0)) ? (v[off + k + 1] ?? 0) : (v[off + k - 1] ?? 0) + 1;
83      let y = x - k;
84      while (x < n && y < m && a[x] === b[y]) {
85        x++;
86        y++;
87      }
88      v[off + k] = x;
89      if (x >= n && y >= m) {
90        found = d;
91        break;
92      }
93    }
94  }
95  if (found < 0) return null;
96  const out: Array<[number, number]> = [];
97  let x = n;
98  let y = m;
99  for (let d = found; d > 0; d--) {
100    const snap = trace[d] as Int32Array;
101    const k = x - y;
102    const prevK = k === -d || (k !== d && (snap[k - 1 + d + 1] ?? 0) < (snap[k + 1 + d + 1] ?? 0)) ? k + 1 : k - 1;
103    const prevX = snap[prevK + d + 1] ?? 0;
104    const prevY = prevX - prevK;
105    while (x > prevX && y > prevY) {
106      x--;
107      y--;
108      out.push([x, y]);
109    }
110    x = prevX;
111    y = prevY;
112  }
113  while (x > 0 && y > 0) {
114    x--;
115    y--;
116    out.push([x, y]);
117  }
118  return out.reverse();
119}
120
121type Marked = { op: Op; text: string; lead: string };
122
123// Folds marked tokens into parts: a run of one op is one part, and the space that opens an
124// insertion or a deletion stays outside it, as plain text, so a mark never underlines a gap.
125function fold(tokens: Marked[]): WordPart[] {
126  const parts: WordPart[] = [];
127  const push = (op: Op, text: string) => {
128    if (text === "") return;
129    const last = parts[parts.length - 1];
130    if (last && last.op === op) last.text += text;
131    else parts.push({ op, text });
132  };
133  let first = true;
134  let i = 0;
135  while (i < tokens.length) {
136    const op = (tokens[i] as Marked).op;
137    let j = i;
138    let text = "";
139    while (j < tokens.length && (tokens[j] as Marked).op === op) {
140      const t = tokens[j] as Marked;
141      text += (j === i ? "" : t.lead) + t.text;
142      j++;
143    }
144    const lead = first ? "" : (tokens[i] as Marked).lead;
145    push("same", lead);
146    push(op, text);
147    first = false;
148    i = j;
149  }
150  return parts;
151}
152
153// The words that differ between two strings. Whitespace is not compared (a double space or a
154// line break is not a change); punctuation marks are words of their own, so "end." becoming
155// "end" shows the full stop as removed.
156export function diffWords(a: string, b: string, options: DiffOptions = {}): WordPart[] {
157  const A = tokenize(a);
158  const B = tokenize(b);
159  const keys = (t: Token[]) => t.map((x) => x.text);
160  const pairs = commonSubsequence(keys(A), keys(B), options.maxEdits) ?? [];
161  const marked: Marked[] = [];
162  let i = 0;
163  let j = 0;
164  const del = (t: Token) => marked.push({ op: "del", text: t.text, lead: t.lead });
165  const ins = (t: Token) => marked.push({ op: "ins", text: t.text, lead: t.lead });
166  for (const [mi, mj] of [...pairs, [A.length, B.length] as [number, number]]) {
167    while (i < mi) del(A[i++] as Token);
168    while (j < mj) ins(B[j++] as Token);
169    if (mi < A.length && mj < B.length) {
170      const ta = A[mi] as Token;
171      const tb = B[mj] as Token;
172      // A word that followed a deleted one by a space keeps that space.
173      const prev = marked[marked.length - 1];
174      const lead = tb.lead === "" && ta.lead !== "" && prev?.op === "del" ? ta.lead : tb.lead;
175      marked.push({ op: "same", text: tb.text, lead });
176      i = mi + 1;
177      j = mj + 1;
178    }
179  }
180  return fold(marked);
181}
182
183export interface Sentence {
184  text: string;
185  // Where it sits in the string it came from.
186  start: number;
187  end: number;
188  // It opens a paragraph: the first one, or the first after a blank line.
189  para: boolean;
190}
191
192const ABBREVIATION = /(?:\b(?:Dr|Mr|Mrs|Ms|Prof|St|vs|Fig|No|Inc|Ltd|Jr|Sr|e\.g|i\.e|cf)|\b\p{Lu})\.$/u;
193const BOUNDARY = /[.!?]+["'”’)\]]*(\s+)(?=["'“‘(\[]?[\p{Lu}\p{N}])/gu;
194
195// Splits text into sentences. Each line is its own set of sentences (a heading, a list item
196// or a paragraph line), a full stop, question mark or exclamation mark ends one when a capital
197// or a number follows, and a short list of abbreviations ("Dr.", "e.g.", an initial) does not.
198export function splitSentences(text: string): Sentence[] {
199  const out: Sentence[] = [];
200  let offset = 0;
201  let para = true;
202  for (const line of text.split("\n")) {
203    const lineStart = offset;
204    offset += line.length + 1;
205    if (line.trim() === "") {
206      para = true;
207      continue;
208    }
209    let from = 0;
210    const emit = (end: number) => {
211      const raw = line.slice(from, end);
212      const body = raw.trim();
213      if (body === "") return;
214      const start = lineStart + from + (raw.length - raw.trimStart().length);
215      out.push({ text: body, start, end: start + body.length, para });
216      para = false;
217    };
218    for (const m of line.matchAll(BOUNDARY)) {
219      const end = m.index + m[0].length - (m[1] ?? "").length;
220      if (ABBREVIATION.test(line.slice(from, end))) continue;
221      emit(end);
222      from = m.index + m[0].length;
223    }
224    emit(line.length);
225    para = false;
226  }
227  return out;
228}
229
230export type Entry =
231  | { op: "same"; a: Sentence; b: Sentence }
232  // The sentence is in both, edited: its words, marked.
233  | { op: "change"; a: Sentence; b: Sentence; parts: WordPart[] }
234  | { op: "del"; a: Sentence; b?: undefined }
235  | { op: "ins"; b: Sentence; a?: undefined };
236
237const squash = (s: string) => s.replace(/\s+/g, " ").trim();
238
239// How alike two sentences are, 0 to 1: shared words over all words.
240function similarity(a: string, b: string): number {
241  const ka = tokenize(a).map((t) => t.text);
242  const kb = tokenize(b).map((t) => t.text);
243  if (ka.length === 0 || kb.length === 0) return 0;
244  const common = commonSubsequence(ka, kb, 400)?.length ?? 0;
245  return (2 * common) / (ka.length + kb.length);
246}
247
248// Two runs of sentences with no exact match between them: pair those that are the same
249// sentence edited (alike enough), leave the rest as removed or added. A best alignment by
250// similarity, in order.
251function align(as: Sentence[], bs: Sentence[], threshold: number): Entry[] {
252  const n = as.length;
253  const m = bs.length;
254  if (n === 0) return bs.map((b) => ({ op: "ins", b }));
255  if (m === 0) return as.map((a) => ({ op: "del", a }));
256  // Very long runs: pair in order, no search.
257  if (n * m > 40000) {
258    const out: Entry[] = [];
259    for (let i = 0; i < Math.max(n, m); i++) {
260      const a = as[i];
261      const b = bs[i];
262      if (a && b) out.push({ op: "change", a, b, parts: diffWords(a.text, b.text) });
263      else if (a) out.push({ op: "del", a });
264      else if (b) out.push({ op: "ins", b });
265    }
266    return out;
267  }
268  const sim: number[][] = as.map((a) => bs.map((b) => similarity(a.text, b.text)));
269  const best: number[][] = Array.from({ length: n + 1 }, () => new Array<number>(m + 1).fill(0));
270  for (let i = n - 1; i >= 0; i--) {
271    for (let j = m - 1; j >= 0; j--) {
272      const s = (sim[i] as number[])[j] as number;
273      const pair = s >= threshold ? s + ((best[i + 1] as number[])[j + 1] as number) : -1;
274      (best[i] as number[])[j] = Math.max(pair, (best[i + 1] as number[])[j] as number, (best[i] as number[])[j + 1] as number);
275    }
276  }
277  const out: Entry[] = [];
278  let i = 0;
279  let j = 0;
280  while (i < n || j < m) {
281    const a = as[i];
282    const b = bs[j];
283    if (a && b) {
284      const s = (sim[i] as number[])[j] as number;
285      const here = (best[i] as number[])[j] as number;
286      if (s >= threshold && Math.abs(here - (s + ((best[i + 1] as number[])[j + 1] as number))) < 1e-9) {
287        out.push({ op: "change", a, b, parts: diffWords(a.text, b.text) });
288        i++;
289        j++;
290        continue;
291      }
292      if (Math.abs(here - ((best[i + 1] as number[])[j] as number)) < 1e-9) {
293        out.push({ op: "del", a });
294        i++;
295      } else {
296        out.push({ op: "ins", b });
297        j++;
298      }
299    } else if (a) {
300      out.push({ op: "del", a });
301      i++;
302    } else if (b) {
303      out.push({ op: "ins", b });
304      j++;
305    }
306  }
307  return out;
308}
309
310export interface SentenceOptions extends DiffOptions {
311  // How alike (0 to 1) two sentences must be to count as one sentence edited rather than one
312  // removed and another added. Default 0.4.
313  similarity?: number;
314}
315
316// Compares two texts sentence by sentence: sentences that match exactly (whitespace aside)
317// are anchors; between anchors, sentences alike enough are paired and compared by word, the
318// rest are removed or added.
319export function diffSentences(a: string, b: string, options: SentenceOptions = {}): Entry[] {
320  const A = splitSentences(a);
321  const B = splitSentences(b);
322  const threshold = options.similarity ?? 0.4;
323  const pairs = commonSubsequence(A.map((s) => squash(s.text)), B.map((s) => squash(s.text)), options.maxEdits) ?? [];
324  const out: Entry[] = [];
325  let i = 0;
326  let j = 0;
327  for (const [mi, mj] of [...pairs, [A.length, B.length] as [number, number]]) {
328    out.push(...align(A.slice(i, mi), B.slice(j, mj), threshold));
329    if (mi < A.length && mj < B.length) out.push({ op: "same", a: A[mi] as Sentence, b: B[mj] as Sentence });
330    i = mi + 1;
331    j = mj + 1;
332  }
333  return out;
334}
335
336// ---------------------------------------------------------------------------------------
337// The analysis a view is drawn from
338// ---------------------------------------------------------------------------------------
339
340export interface Counts {
341  added: number;
342  removed: number;
343  changes: number;
344}
345
346export interface Analysis {
347  entries: Entry[];
348  // For each entry: the number (from 1) of the change it belongs to, or 0 when unchanged.
349  // A change is a run of edited sentences in one paragraph.
350  group: number[];
351  // Per change, from 1: its words added and removed.
352  perChange: Array<{ added: number; removed: number }>;
353  counts: Counts;
354  // Nothing differs, word for word.
355  identical: boolean;
356}
357
358const wordsOf = (parts: WordPart[], op: Op) => parts.reduce((n, p) => (p.op === op ? n + countWords(p.text) : n), 0);
359
360// Counts what an entry adds and removes, in words.
361function entryWords(e: Entry): { added: number; removed: number } {
362  if (e.op === "ins") return { added: countWords(e.b.text), removed: 0 };
363  if (e.op === "del") return { added: 0, removed: countWords(e.a.text) };
364  if (e.op === "change") return { added: wordsOf(e.parts, "ins"), removed: wordsOf(e.parts, "del") };
365  return { added: 0, removed: 0 };
366}
367
368export function analyse(before: string, after: string, options: SentenceOptions = {}): Analysis {
369  const entries = diffSentences(before, after, options);
370  const group: number[] = [];
371  const perChange: Array<{ added: number; removed: number }> = [];
372  let n = 0;
373  let prevChanged = false;
374  const counts: Counts = { added: 0, removed: 0, changes: 0 };
375  for (const e of entries) {
376    if (e.op === "same") {
377      group.push(0);
378      prevChanged = false;
379      continue;
380    }
381    const opens = (e.b?.para ?? false) || (e.a?.para ?? false);
382    if (!prevChanged || opens) {
383      n++;
384      perChange.push({ added: 0, removed: 0 });
385    }
386    prevChanged = true;
387    group.push(n);
388    const w = entryWords(e);
389    const c = perChange[n - 1] as { added: number; removed: number };
390    c.added += w.added;
391    c.removed += w.removed;
392    counts.added += w.added;
393    counts.removed += w.removed;
394  }
395  counts.changes = n;
396  return { entries, group, perChange, counts, identical: n === 0 };
397}
398
399// "14 words added, 9 removed, 3 changes".
400export function countsText(c: Counts): string {
401  const w = (n: number) => `${n} word${n === 1 ? "" : "s"}`;
402  return `${w(c.added)} added, ${c.removed} removed, ${c.changes} change${c.changes === 1 ? "" : "s"}`;
403}