diffLines computes a line-level diff between two sequences using Hirschberg's linear-space LCS algorithm, producing output compatible with difflib.Diff. Unlike the O(N*M) space used by difflib.Diff's full-matrix dynamic programming approach, this implementation requires only O(N+M) space, which pre
(seq1, seq2 []string)
| 13 | // |
| 14 | // See https://github.com/databus23/helm-diff/issues/996 |
| 15 | func diffLines(seq1, seq2 []string) []difflib.DiffRecord { |
| 16 | start, end := numEqualStartAndEndElements(seq1, seq2) |
| 17 | |
| 18 | var result []difflib.DiffRecord |
| 19 | |
| 20 | for i := 0; i < start; i++ { |
| 21 | result = append(result, difflib.DiffRecord{Payload: seq1[i], Delta: difflib.Common}) |
| 22 | } |
| 23 | |
| 24 | mid1 := seq1[start : len(seq1)-end] |
| 25 | mid2 := seq2[start : len(seq2)-end] |
| 26 | result = append(result, hirschbergDiff(mid1, mid2)...) |
| 27 | |
| 28 | for i := len(seq1) - end; i < len(seq1); i++ { |
| 29 | result = append(result, difflib.DiffRecord{Payload: seq1[i], Delta: difflib.Common}) |
| 30 | } |
| 31 | |
| 32 | return result |
| 33 | } |
| 34 | |
| 35 | func numEqualStartAndEndElements(seq1, seq2 []string) (start, end int) { |
| 36 | for start < len(seq1) && start < len(seq2) && seq1[start] == seq2[start] { |