| 17 | } |
| 18 | |
| 19 | function computeDiff(oldStr: string, newStr: string): DiffLine[] { |
| 20 | const oldLines = oldStr.split("\n"); |
| 21 | const newLines = newStr.split("\n"); |
| 22 | const m = oldLines.length; |
| 23 | const n = newLines.length; |
| 24 | |
| 25 | // Build LCS table |
| 26 | const dp: Uint32Array[] = Array.from( |
| 27 | { length: m + 1 }, |
| 28 | () => new Uint32Array(n + 1) |
| 29 | ); |
| 30 | for (let i = 1; i <= m; i++) { |
| 31 | for (let j = 1; j <= n; j++) { |
| 32 | if (oldLines[i - 1] === newLines[j - 1]) { |
| 33 | dp[i][j] = dp[i - 1][j - 1] + 1; |
| 34 | } else { |
| 35 | dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); |
| 36 | } |
| 37 | } |
| 38 | } |
| 39 | |
| 40 | // Backtrack to build diff |
| 41 | const result: DiffLine[] = []; |
| 42 | let i = m; |
| 43 | let j = n; |
| 44 | let oldLineNo = m; |
| 45 | let newLineNo = n; |
| 46 | |
| 47 | while (i > 0 || j > 0) { |
| 48 | if ( |
| 49 | i > 0 && |
| 50 | j > 0 && |
| 51 | oldLines[i - 1] === newLines[j - 1] |
| 52 | ) { |
| 53 | result.unshift({ |
| 54 | type: "equal", |
| 55 | content: oldLines[i - 1], |
| 56 | oldLineNo: oldLineNo--, |
| 57 | newLineNo: newLineNo--, |
| 58 | }); |
| 59 | i--; |
| 60 | j--; |
| 61 | } else if (j > 0 && (i === 0 || dp[i][j - 1] >= dp[i - 1][j])) { |
| 62 | result.unshift({ |
| 63 | type: "add", |
| 64 | content: newLines[j - 1], |
| 65 | newLineNo: newLineNo--, |
| 66 | }); |
| 67 | j--; |
| 68 | } else { |
| 69 | result.unshift({ |
| 70 | type: "remove", |
| 71 | content: oldLines[i - 1], |
| 72 | oldLineNo: oldLineNo--, |
| 73 | }); |
| 74 | i--; |
| 75 | } |
| 76 | } |