(before: string, after: string)
| 44 | * exceed `MAX_DIFF_CELLS`; callers should fall back to the raw tool output. |
| 45 | */ |
| 46 | export function buildDiffLines(before: string, after: string): DiffViewLine[] | null { |
| 47 | const oldLines = splitLines(before); |
| 48 | const newLines = splitLines(after); |
| 49 | const n = oldLines.length; |
| 50 | const m = newLines.length; |
| 51 | if (n === 0 && m === 0) return []; |
| 52 | if (n > MAX_DIFF_ROWS || m > MAX_DIFF_ROWS) return null; |
| 53 | if ((n + 1) * (m + 1) > MAX_DIFF_CELLS) return null; |
| 54 | |
| 55 | const dp: number[][] = Array.from({ length: n + 1 }, () => Array.from({ length: m + 1 }, () => 0)); |
| 56 | for (let i = 1; i <= n; i++) { |
| 57 | for (let j = 1; j <= m; j++) { |
| 58 | dp[i]![j] = |
| 59 | oldLines[i - 1] === newLines[j - 1] |
| 60 | ? dp[i - 1]![j - 1]! + 1 |
| 61 | : Math.max(dp[i - 1]![j]!, dp[i]![j - 1]!); |
| 62 | } |
| 63 | } |
| 64 | |
| 65 | type Op = { type: 'context' | 'add' | 'del'; text: string }; |
| 66 | const ops: Op[] = []; |
| 67 | let i = n; |
| 68 | let j = m; |
| 69 | while (i > 0 || j > 0) { |
| 70 | if (i > 0 && j > 0 && oldLines[i - 1] === newLines[j - 1]) { |
| 71 | ops.push({ type: 'context', text: oldLines[i - 1]! }); |
| 72 | i--; |
| 73 | j--; |
| 74 | } else if (j > 0 && (i === 0 || dp[i]![j - 1]! >= dp[i - 1]![j]!)) { |
| 75 | ops.push({ type: 'add', text: newLines[j - 1]! }); |
| 76 | j--; |
| 77 | } else { |
| 78 | ops.push({ type: 'del', text: oldLines[i - 1]! }); |
| 79 | i--; |
| 80 | } |
| 81 | } |
| 82 | ops.reverse(); |
| 83 | |
| 84 | const result: DiffViewLine[] = []; |
| 85 | let oldNo = 1; |
| 86 | let newNo = 1; |
| 87 | for (const op of ops) { |
| 88 | if (op.type === 'context') { |
| 89 | result.push({ type: 'context', text: op.text, oldNo, newNo }); |
| 90 | oldNo++; |
| 91 | newNo++; |
| 92 | } else if (op.type === 'add') { |
| 93 | result.push({ type: 'add', text: op.text, newNo }); |
| 94 | newNo++; |
| 95 | } else { |
| 96 | result.push({ type: 'del', text: op.text, oldNo }); |
| 97 | oldNo++; |
| 98 | } |
| 99 | } |
| 100 | return result; |
| 101 | } |
| 102 | |
| 103 | export function diffStats(lines: DiffViewLine[]): DiffStats { |
no test coverage detected