MCPcopy Create free account
hub / github.com/alibaba/open-code-review / ComputeLineDiff

Function ComputeLineDiff

internal/suggestdiff/diff.go:27–77  ·  view source on GitHub ↗

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)

Source from the content-addressed store, hash-verified

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.
27func 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 if oldLines[i-1] == newLines[j-1] {
55 back = append(back, DiffLine{Type: DiffContext, Content: oldLines[i-1]})
56 } else {
57 // Fuzzy equality is only for alignment; preserve raw changes in the rendered diff.
58 back = append(back, DiffLine{Type: DiffAdded, Content: newLines[j-1]})
59 back = append(back, DiffLine{Type: DiffDeleted, Content: oldLines[i-1]})
60 }
61 i--
62 j--
63 } else if j > 0 && (i == 0 || lcs[i][j-1] >= lcs[i-1][j]) {
64 back = append(back, DiffLine{Type: DiffAdded, Content: newLines[j-1]})
65 j--
66 } else {
67 back = append(back, DiffLine{Type: DiffDeleted, Content: oldLines[i-1]})
68 i--
69 }
70 }
71
72 // Reverse
73 for idx := len(back) - 1; idx >= 0; idx-- {
74 result = append(result, back[idx])
75 }
76 return result
77}
78
79func max(a, b int) int {
80 if a > b {

Calls 1

maxFunction · 0.85