Pick any line to see why it is the way it is: the commit, the pull request and issue it came from, and what the agent was thinking.
| Docs: a workspace knowledge base people and agents write together | 1 | /** |
| 2 | * What changed between two versions of a page: a line diff of their | |
| 3 | * Markdown (longest common subsequence), for history. Pure. | |
| 4 | */ | |
| 5 | import type { DocDiffLine } from "@g1t/contracts"; | |
| 6 | ||
| 7 | /** Past this many lines on both sides, the middle is compared as a whole block. */ | |
| 8 | const MAX_CELLS = 4_000_000; | |
| 9 | ||
| 10 | export function diffLines(before: string, after: string): DocDiffLine[] { | |
| 11 | const a = before ? before.replace(/\n$/, "").split("\n") : []; | |
| 12 | const b = after ? after.replace(/\n$/, "").split("\n") : []; | |
| 13 | // Common head and tail first: most edits touch a few lines. | |
| 14 | let head = 0; | |
| 15 | while (head < a.length && head < b.length && a[head] === b[head]) head++; | |
| 16 | let tail = 0; | |
| 17 | while (tail < a.length - head && tail < b.length - head && a[a.length - 1 - tail] === b[b.length - 1 - tail]) tail++; | |
| 18 | const midA = a.slice(head, a.length - tail); | |
| 19 | const midB = b.slice(head, b.length - tail); | |
| 20 | const out: DocDiffLine[] = a.slice(0, head).map((text) => ({ op: "same" as const, text })); | |
| 21 | if (midA.length * midB.length > MAX_CELLS) { | |
| 22 | for (const text of midA) out.push({ op: "del", text }); | |
| 23 | for (const text of midB) out.push({ op: "add", text }); | |
| 24 | } else { | |
| 25 | const n = midA.length; | |
| 26 | const m = midB.length; | |
| 27 | // lcs[i][j]: the longest common subsequence of midA[i..] and midB[j..]. | |
| 28 | const lcs = Array.from({ length: n + 1 }, () => new Uint32Array(m + 1)); | |
| 29 | for (let i = n - 1; i >= 0; i--) { | |
| 30 | for (let j = m - 1; j >= 0; j--) { | |
| 31 | lcs[i]![j] = midA[i] === midB[j] ? lcs[i + 1]![j + 1]! + 1 : Math.max(lcs[i + 1]![j]!, lcs[i]![j + 1]!); | |
| 32 | } | |
| 33 | } | |
| 34 | let i = 0; | |
| 35 | let j = 0; | |
| 36 | while (i < n && j < m) { | |
| 37 | if (midA[i] === midB[j]) { | |
| 38 | out.push({ op: "same", text: midA[i]! }); | |
| 39 | i++; | |
| 40 | j++; | |
| 41 | } else if (lcs[i + 1]![j]! >= lcs[i]![j + 1]!) out.push({ op: "del", text: midA[i++]! }); | |
| 42 | else out.push({ op: "add", text: midB[j++]! }); | |
| 43 | } | |
| 44 | while (i < n) out.push({ op: "del", text: midA[i++]! }); | |
| 45 | while (j < m) out.push({ op: "add", text: midB[j++]! }); | |
| 46 | } | |
| 47 | for (const text of a.slice(a.length - tail)) out.push({ op: "same", text }); | |
| 48 | return out; | |
| 49 | } | |
| 50 | ||
| 51 | /** How many lines were added and removed. */ | |
| 52 | export function diffStats(lines: DocDiffLine[]): { added: number; removed: number } { | |
| 53 | let added = 0; | |
| 54 | let removed = 0; | |
| 55 | for (const l of lines) { | |
| 56 | if (l.op === "add") added++; | |
| 57 | if (l.op === "del") removed++; | |
| 58 | } | |
| 59 | return { added, removed }; | |
| 60 | } |
