coverage — ~bigbes/sr-ht-spec — 64cae3af — prosediff/myers.go

Coverage
87.8% 101/115 statements
Δ
+0.0
Blob
9286c8d
Uncovered L19-L26L28L139L181-L184L189-L190L192-L193L206L209-L210
1 package prosediff
2
3 // Myers O(ND) sequence diff, used at three levels: blocks, words and code
4 // lines. Sequences are always interned to []int first, so equality is exact
5 // integer equality and there is no hash-collision risk.
6
7 // Op is the role of a run in an edit script.
8 type Op uint8
9
10 const (
11 // OpEqual marks content present, unchanged, in both revisions.
12 OpEqual Op = iota
13 // OpDelete marks content present only in the old revision.
14 OpDelete
15 // OpInsert marks content present only in the new revision.
16 OpInsert
17 )
18
19 0 func (o Op) String() string {
20 0 switch o {
21 0 case OpEqual:
22 0 return "equal"
23 0 case OpDelete:
24 0 return "delete"
25 0 case OpInsert:
26 0 return "insert"
27 }
28 0 return "unknown"
29 }
30
31 // edit is one run of an edit script: n consecutive elements sharing an Op.
32 type edit struct {
33 op Op
34 n int
35 }
36
37 // interner maps arbitrary strings to dense ints so sequence comparison is
38 // integer equality.
39 type interner struct {
40 ids map[string]int
41 }
42
43 101 func newInterner() *interner { return &interner{ids: make(map[string]int)} }
44
45 1118 func (in *interner) id(s string) int {
46 1118 if v, ok := in.ids[s]; ok {
47 484 return v
48 484 }
49 634 v := len(in.ids) + 1
50 634 in.ids[s] = v
51 634 return v
52 }
53
54 138 func (in *interner) all(ss []string) []int {
55 138 out := make([]int, len(ss))
56 954 for i, s := range ss {
57 954 out[i] = in.id(s)
58 954 }
59 138 return out
60 }
61
62 // diffInts returns the edit script turning a into b, as a coalesced run list.
63 // The script is a minimal edit script (Myers), with common prefix and suffix
64 // trimmed first so the expensive part only runs over the changed middle.
65 512 func diffInts(a, b []int) []edit {
66 512 pre := 0
67 512 for pre < len(a) && pre < len(b) && a[pre] == b[pre] {
68 395 pre++
69 395 }
70 512 suf := 0
71 512 for suf < len(a)-pre && suf < len(b)-pre && a[len(a)-1-suf] == b[len(b)-1-suf] {
72 210 suf++
73 210 }
74 512 var out []edit
75 512 if pre > 0 {
76 147 out = append(out, edit{OpEqual, pre})
77 147 }
78 512 out = append(out, myers(a[pre:len(a)-suf], b[pre:len(b)-suf])...)
79 512 if suf > 0 {
80 130 out = append(out, edit{OpEqual, suf})
81 130 }
82 512 return coalesce(out)
83 }
84
85 // vsnap is the V array of one Myers iteration, stored only over the diagonals
86 // [-d, d] that iteration can reach.
87 type vsnap struct {
88 d int
89 vals []int32
90 }
91
92 6925 func (s vsnap) get(k int) int { return int(s.vals[k+s.d]) }
93
94 512 func myers(a, b []int) []edit {
95 512 n, m := len(a), len(b)
96 512 switch {
97 14 case n == 0 && m == 0:
98 14 return nil
99 44 case n == 0:
100 44 return []edit{{OpInsert, m}}
101 35 case m == 0:
102 35 return []edit{{OpDelete, n}}
103 }
104
105 419 maxD := n + m
106 419 v := make([]int32, 2*maxD+1)
107 419 off := maxD
108 419 trace := make([]vsnap, 0, 16)
109 419
110 3560 for d := 0; d <= maxD; d++ {
111 3560 done := false
112 18067 for k := -d; k <= d; k += 2 {
113 18067 var x int
114 18067 if k == -d || (k != d && v[off+k-1] < v[off+k+1]) {
115 13289 x = int(v[off+k+1]) // move down: consume one element of b
116 13289 } else {
117 4778 x = int(v[off+k-1]) + 1 // move right: consume one element of a
118 4778 }
119 18067 y := x - k
120 18067 for x < n && y < m && a[x] == b[y] {
121 1604 x++
122 1604 y++
123 1604 }
124 18067 v[off+k] = int32(x)
125 18067 if x >= n && y >= m {
126 419 done = true
127 419 break
128 }
129 }
130 3560 snap := vsnap{d: d, vals: make([]int32, 2*d+1)}
131 19668 for k := -d; k <= d; k += 2 {
132 19668 snap.vals[k+d] = v[off+k]
133 19668 }
134 3560 trace = append(trace, snap)
135 3560 if done {
136 419 return backtrack(trace, n, m)
137 419 }
138 }
139 0 panic("prosediff: myers did not converge")
140 }
141
142 // backtrack walks the saved V arrays from the end point back to the origin,
143 // emitting the edit script in reverse and then flipping it.
144 419 func backtrack(trace []vsnap, n, m int) []edit {
145 419 var rev []edit
146 4027 push := func(op Op) {
147 4027 if len(rev) > 0 && rev[len(rev)-1].op == op {
148 1770 rev[len(rev)-1].n++
149 1770 return
150 1770 }
151 2257 rev = append(rev, edit{op, 1})
152 }
153
154 419 x, y := n, m
155 3141 for d := len(trace) - 1; d > 0; d-- {
156 3141 prev := trace[d-1]
157 3141 k := x - y
158 3141 var prevK int
159 3141 if k == -d || (k != d && prev.get(k-1) < prev.get(k+1)) {
160 1601 prevK = k + 1
161 1601 } else {
162 1540 prevK = k - 1
163 1540 }
164 3141 prevX := prev.get(prevK)
165 3141 prevY := prevX - prevK
166 3141 for x > prevX && y > prevY {
167 886 push(OpEqual)
168 886 x--
169 886 y--
170 886 }
171 3141 if x == prevX {
172 1601 push(OpInsert)
173 1601 y--
174 1601 } else {
175 1540 push(OpDelete)
176 1540 x--
177 1540 }
178 3141 x, y = prevX, prevY
179 }
180 419 for x > 0 && y > 0 {
181 0 push(OpEqual)
182 0 x--
183 0 y--
184 0 }
185 // d == 0 leaves at most one of x, y non-zero only when the other
186 // sequence was fully consumed on the diagonal, which the prefix trim
187 // already handled; keep the guard rather than assume.
188 419 for ; x > 0; x-- {
189 0 push(OpDelete)
190 0 }
191 419 for ; y > 0; y-- {
192 0 push(OpInsert)
193 0 }
194
195 419 out := make([]edit, 0, len(rev))
196 2257 for i := len(rev) - 1; i >= 0; i-- {
197 2257 out = append(out, rev[i])
198 2257 }
199 419 return coalesce(out)
200 }
201
202 948 func coalesce(in []edit) []edit {
203 948 out := in[:0:0]
204 4940 for _, e := range in {
205 4940 if e.n == 0 {
206 0 continue
207 }
208 4940 if len(out) > 0 && out[len(out)-1].op == e.op {
209 0 out[len(out)-1].n += e.n
210 0 continue
211 }
212 4940 out = append(out, e)
213 }
214 948 return out
215 }
216
217 // commonCount reports how many elements the edit script keeps equal.
218 443 func commonCount(script []edit) int {
219 443 n := 0
220 2420 for _, e := range script {
221 2420 if e.op == OpEqual {
222 916 n += e.n
223 916 }
224 }
225 443 return n
226 }
227
228 // ratio is the classic 2*common/(len(a)+len(b)) similarity in [0,1].
229 44 func ratio(a, b []int) float64 {
230 44 if len(a) == 0 && len(b) == 0 {
231 1 return 1
232 1 }
233 43 return 2 * float64(commonCount(diffInts(a, b))) / float64(len(a)+len(b))
234 }