ComputeLineDiff returns a line-level diff between oldLines and newLines. Uses Myers-style LCS to find common subsequences, then emits context/added/deleted lines.
(oldLines, newLines []string)
| 25 | // ComputeLineDiff returns a line-level diff between oldLines and newLines. |
| 26 | // Uses Myers-style LCS to find common subsequences, then emits context/added/deleted lines. |
| 27 | func ComputeLineDiff(oldLines, newLines []string) []DiffLine { |
| 28 | m, n := len(oldLines), len(newLines) |
| 29 | if m == 0 && n == 0 { |
| 30 | return nil |
| 31 | } |
| 32 | |
| 33 | // LCS DP table |
| 34 | lcs := make([][]int, m+1) |
| 35 | for i := range lcs { |
| 36 | lcs[i] = make([]int, n+1) |
| 37 | } |
| 38 | for i := 1; i <= m; i++ { |
| 39 | for j := 1; j <= n; j++ { |
| 40 | if strings.EqualFold(strings.TrimSpace(oldLines[i-1]), strings.TrimSpace(newLines[j-1])) { |
| 41 | lcs[i][j] = lcs[i-1][j-1] + 1 |
| 42 | } else { |
| 43 | lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]) |
| 44 | } |
| 45 | } |
| 46 | } |
| 47 | |
| 48 | // Backtrack to produce diff |
| 49 | var result []DiffLine |
| 50 | i, j := m, n |
| 51 | back := make([]DiffLine, 0, max(m, n)*2) |
| 52 | for i > 0 || j > 0 { |
| 53 | if i > 0 && j > 0 && strings.EqualFold(strings.TrimSpace(oldLines[i-1]), strings.TrimSpace(newLines[j-1])) { |
| 54 | back = append(back, DiffLine{Type: DiffContext, Content: oldLines[i-1]}) |
| 55 | i-- |
| 56 | j-- |
| 57 | } else if j > 0 && (i == 0 || lcs[i][j-1] >= lcs[i-1][j]) { |
| 58 | back = append(back, DiffLine{Type: DiffAdded, Content: newLines[j-1]}) |
| 59 | j-- |
| 60 | } else { |
| 61 | back = append(back, DiffLine{Type: DiffDeleted, Content: oldLines[i-1]}) |
| 62 | i-- |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | // Reverse |
| 67 | for idx := len(back) - 1; idx >= 0; idx-- { |
| 68 | result = append(result, back[idx]) |
| 69 | } |
| 70 | return result |
| 71 | } |
| 72 | |
| 73 | func max(a, b int) int { |
| 74 | if a > b { |