LCS-based line diff. Falls back to whole-block replace on very large inputs.
(oldLines: string[], newLines: string[])
| 4 | |
| 5 | /** LCS-based line diff. Falls back to whole-block replace on very large inputs. */ |
| 6 | function diffLines(oldLines: string[], newLines: string[]): Op[] { |
| 7 | // Trim common prefix/suffix so the DP table only covers the changed middle. |
| 8 | let start = 0 |
| 9 | while (start < oldLines.length && start < newLines.length && oldLines[start] === newLines[start]) { |
| 10 | start++ |
| 11 | } |
| 12 | let oldEnd = oldLines.length |
| 13 | let newEnd = newLines.length |
| 14 | while (oldEnd > start && newEnd > start && oldLines[oldEnd - 1] === newLines[newEnd - 1]) { |
| 15 | oldEnd-- |
| 16 | newEnd-- |
| 17 | } |
| 18 | |
| 19 | const a = oldLines.slice(start, oldEnd) |
| 20 | const b = newLines.slice(start, newEnd) |
| 21 | |
| 22 | let middle: Op[] |
| 23 | if (a.length * b.length > 1_000_000) { |
| 24 | // Too large for DP; show as a block replace. |
| 25 | middle = [ |
| 26 | ...a.map((text): Op => ({ type: "-", text })), |
| 27 | ...b.map((text): Op => ({ type: "+", text })), |
| 28 | ] |
| 29 | } else { |
| 30 | // Standard LCS dynamic program. |
| 31 | const rows = a.length + 1 |
| 32 | const cols = b.length + 1 |
| 33 | const table = new Uint32Array(rows * cols) |
| 34 | for (let i = a.length - 1; i >= 0; i--) { |
| 35 | for (let j = b.length - 1; j >= 0; j--) { |
| 36 | table[i * cols + j] = |
| 37 | a[i] === b[j] |
| 38 | ? table[(i + 1) * cols + j + 1] + 1 |
| 39 | : Math.max(table[(i + 1) * cols + j], table[i * cols + j + 1]) |
| 40 | } |
| 41 | } |
| 42 | middle = [] |
| 43 | let i = 0 |
| 44 | let j = 0 |
| 45 | while (i < a.length && j < b.length) { |
| 46 | if (a[i] === b[j]) { |
| 47 | middle.push({ type: " ", text: a[i] }) |
| 48 | i++ |
| 49 | j++ |
| 50 | } else if (table[(i + 1) * cols + j] >= table[i * cols + j + 1]) { |
| 51 | middle.push({ type: "-", text: a[i] }) |
| 52 | i++ |
| 53 | } else { |
| 54 | middle.push({ type: "+", text: b[j] }) |
| 55 | j++ |
| 56 | } |
| 57 | } |
| 58 | while (i < a.length) middle.push({ type: "-", text: a[i++] }) |
| 59 | while (j < b.length) middle.push({ type: "+", text: b[j++] }) |
| 60 | } |
| 61 | |
| 62 | return [ |
| 63 | ...oldLines.slice(0, start).map((text): Op => ({ type: " ", text })), |