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

Coverage
92.4% 183/198 statements
Δ
+0.0
Blob
361e59c
Uncovered L173L202L221-L222L225-L226L228-L229L235-L236L342L346L356-L359L367L392-L396
1 package prosediff
2
3 import "sort"
4
5 // Tuning constants for block alignment. They are deliberately package-level
6 // and documented rather than hidden in the code, because they are the knobs
7 // that decide whether a review page reads well.
8 const (
9 // modifyThreshold is the token similarity two blocks need before they
10 // are called "the same block, edited" rather than a delete plus an
11 // insert. Below it, presenting a word diff would be noise.
12 modifyThreshold = 0.40
13
14 // shortBlockTokens is the size below which a block is considered too
15 // small to judge by similarity alone.
16 shortBlockTokens = 6
17
18 // shortBlockThreshold applies instead of modifyThreshold when either
19 // block is short: pairing "yes" with "no" on a 0.4 score helps nobody.
20 shortBlockThreshold = 0.60
21
22 // moveMinTokens is the smallest block that may be reported as moved.
23 // Below it, identical content is far more likely to be coincidence
24 // (a repeated "```", a "- see above") than an actual move.
25 moveMinTokens = 5
26
27 // pairBudget caps the similarity matrix inside one changed region. Past
28 // it, only pairs within pairWindow of each other are considered; a
29 // region with hundreds of blocks on both sides has no readable pairing
30 // anyway.
31 pairBudget = 4096
32 pairWindow = 8
33 )
34
35 // region is one changed stretch of the alignment: blocks deleted from the old
36 // revision and blocks inserted into the new one, adjacent in the edit script.
37 type region struct {
38 del []int // indices into old
39 ins []int // indices into nw
40 }
41
42 // align turns two block sequences into the diff's change list.
43 //
44 // Three passes, in this order:
45 // 1. Myers over block hashes finds the unchanged skeleton.
46 // 2. Blocks left over from pass 1 that reappear verbatim elsewhere are
47 // moves, grown outwards over their neighbours.
48 // 3. Similar-enough leftovers inside one changed region are modifications.
49 //
50 // Anything still unmatched is a plain insert or delete.
51 32 func align(old, nw []Block) []BlockChange {
52 32 in := newInterner()
53 32 oldIDs := make([]int, len(old))
54 79 for i, b := range old {
55 79 oldIDs[i] = in.id(b.Hash)
56 79 }
57 32 newIDs := make([]int, len(nw))
58 85 for i, b := range nw {
59 85 newIDs[i] = in.id(b.Hash)
60 85 }
61 32 script := diffInts(oldIDs, newIDs)
62 32
63 32 var (
64 32 out []BlockChange
65 32 regions []region
66 32 // slots[i] is where region i's entries go in the output.
67 32 slots []int
68 32 )
69 32
70 32 i, j := 0, 0
71 64 for k := 0; k < len(script); {
72 64 if script[k].op == OpEqual {
73 50 for n := 0; n < script[k].n; n++ {
74 50 o, w := old[i+n], nw[j+n]
75 50 out = append(out, BlockChange{Kind: ChangeEqual, Old: &o, New: &w})
76 50 }
77 31 i += script[k].n
78 31 j += script[k].n
79 31 k++
80 31 continue
81 }
82 33 var r region
83 53 for ; k < len(script) && script[k].op != OpEqual; k++ {
84 53 if script[k].op == OpDelete {
85 29 for n := 0; n < script[k].n; n++ {
86 29 r.del = append(r.del, i+n)
87 29 }
88 24 i += script[k].n
89 29 } else {
90 35 for n := 0; n < script[k].n; n++ {
91 35 r.ins = append(r.ins, j+n)
92 35 }
93 29 j += script[k].n
94 }
95 }
96 33 regions = append(regions, r)
97 33 slots = append(slots, len(out))
98 33 out = append(out, BlockChange{}) // placeholder, expanded below
99 }
100
101 32 moveOf, editedInMove := detectMoves(old, nw, regions)
102 32
103 32 // Build each region's entries, then splice them in at their slot.
104 32 expanded := make([][]BlockChange, len(regions))
105 33 for ri, r := range regions {
106 33 expanded[ri] = expandRegion(old, nw, r.del, r.ins, moveOf, editedInMove)
107 33 }
108 32 final := make([]BlockChange, 0, len(out)+len(regions))
109 32 next := 0
110 83 for idx := 0; idx < len(out); idx++ {
111 83 if next < len(slots) && slots[next] == idx {
112 33 final = append(final, expanded[next]...)
113 33 next++
114 33 continue
115 }
116 50 final = append(final, out[idx])
117 }
118 32 return final
119 }
120
121 // movePair records that old block o and new block n are the same content in a
122 // different place.
123 type movePair struct {
124 oldIdx int
125 newIdx int
126 }
127
128 // detectMoves matches leftover blocks across regions, seeding on exact hash
129 // equality and then growing each seed over its neighbours.
130 //
131 // Deliberate limitation: every move must be anchored by at least one block
132 // whose content is byte-identical after normalization. A block that moved and
133 // was edited is recognised only when it sits *between* two such anchors; a
134 // section that moved and was rewritten throughout falls through as a delete
135 // plus an insert. Matching moves by similarity alone would claim
136 // relationships between blocks that merely share boilerplate, and a wrong
137 // "moved from" costs a reviewer more than an honest add+remove.
138 32 func detectMoves(old, nw []Block, regions []region) (moves, edited map[int]movePair) {
139 32 freeOld := map[int]bool{}
140 32 freeNew := map[int]bool{}
141 32 byHash := map[string][]int{}
142 33 for _, r := range regions {
143 33 for _, oi := range r.del {
144 29 freeOld[oi] = true
145 29 if len(Tokenize(old[oi].Text)) >= moveMinTokens {
146 22 byHash[old[oi].Hash] = append(byHash[old[oi].Hash], oi)
147 22 }
148 }
149 35 for _, ni := range r.ins {
150 35 freeNew[ni] = true
151 35 }
152 }
153
154 32 out := map[int]movePair{}
155 32 edited = map[int]movePair{}
156 32 pair := func(oi, ni int) {
157 6 p := movePair{oldIdx: oi, newIdx: ni}
158 6 out[oldKey(oi)] = p
159 6 out[newKey(ni)] = p
160 6 delete(freeOld, oi)
161 6 delete(freeNew, ni)
162 6 }
163
164 // Seed: blocks big enough that identical content cannot be coincidence.
165 32 var seeds []movePair
166 33 for _, r := range regions {
167 35 for _, ni := range r.ins {
168 35 if len(Tokenize(nw[ni].Text)) < moveMinTokens {
169 11 continue
170 }
171 24 for _, oi := range byHash[nw[ni].Hash] {
172 3 if !freeOld[oi] || !freeNew[ni] {
173 0 continue
174 }
175 3 pair(oi, ni)
176 3 seeds = append(seeds, movePair{oi, ni})
177 3 break
178 }
179 }
180 }
181
182 // Grow each seed outwards while the neighbouring blocks are also
183 // unmatched and identical. This is what keeps a moved section's heading
184 // and its short trailing blocks attached to the move, instead of
185 // stranding them as a delete plus an insert either side of it.
186 //
187 // Growth also bridges a single edited block, but only when the block
188 // *past* it matches exactly — "a section was moved and one paragraph in
189 // it was touched" is common, while a lone similar block at the edge of a
190 // move is just as likely to be coincidence.
191 32 for _, s := range seeds {
192 6 for step := -1; step <= 1; step += 2 {
193 6 oi, ni := s.oldIdx+step, s.newIdx+step
194 6 for freeOld[oi] && freeNew[ni] {
195 3 if old[oi].Hash == nw[ni].Hash {
196 2 pair(oi, ni)
197 2 oi += step
198 2 ni += step
199 2 continue
200 }
201 1 if !bridgeable(old, nw, oi, ni, step, freeOld, freeNew, out) {
202 0 break
203 }
204 1 pair(oi, ni)
205 1 edited[oldKey(oi)] = movePair{oi, ni}
206 1 edited[newKey(ni)] = movePair{oi, ni}
207 1 oi += step
208 1 ni += step
209 }
210 }
211 }
212 32 return out, edited
213 }
214
215 // bridgeable reports whether old[oi] and nw[ni] are an edited version of one
216 // another sitting inside a run of moved blocks. The anchor past the gap may
217 // be either still unclaimed or already paired to its counterpart by an
218 // earlier seed — both mean "the move continues on the far side".
219 1 func bridgeable(old, nw []Block, oi, ni, step int, freeOld, freeNew map[int]bool, moves map[int]movePair) bool {
220 1 if old[oi].Kind != nw[ni].Kind {
221 0 return false
222 0 }
223 1 no, nn := oi+step, ni+step
224 1 if no < 0 || no >= len(old) || nn < 0 || nn >= len(nw) {
225 0 return false
226 0 }
227 1 if old[no].Hash != nw[nn].Hash {
228 0 return false
229 0 }
230 1 anchored := freeOld[no] && freeNew[nn]
231 1 if p, ok := moves[oldKey(no)]; ok && p.newIdx == nn {
232 1 anchored = true
233 1 }
234 1 if !anchored {
235 0 return false
236 0 }
237 1 return blockSimilarity(old[oi], nw[ni]) >= thresholdFor(old[oi], nw[ni])
238 }
239
240 // Move bookkeeping keys old and new indices into one map without colliding.
241 66 func oldKey(i int) int { return i * 2 }
242 111 func newKey(i int) int { return i*2 + 1 }
243
244 33 func expandRegion(old, nw []Block, del, ins []int, moveOf, editedInMove map[int]movePair) []BlockChange {
245 33 pairs := pairModified(old, nw, del, ins, moveOf)
246 33 pairedOld := map[int]int{} // old index -> new index
247 33 pairedNew := map[int]bool{}
248 33 for _, p := range pairs {
249 18 pairedOld[p.oldIdx] = p.newIdx
250 18 pairedNew[p.newIdx] = true
251 18 }
252
253 33 var out []BlockChange
254 33 for _, oi := range del {
255 29 o := old[oi]
256 29 if mp, ok := moveOf[oldKey(oi)]; ok {
257 6 // A block that moved and was edited is announced here and
258 6 // shown in full at its new position, where the reviewer
259 6 // reads the section it now belongs to.
260 6 n := nw[mp.newIdx]
261 6 out = append(out, BlockChange{Kind: ChangeMoveOut, Old: &o, New: &n})
262 6 continue
263 }
264 23 if ni, ok := pairedOld[oi]; ok {
265 18 n := nw[ni]
266 18 out = append(out, modifyChange(o, n))
267 18 continue
268 }
269 5 out = append(out, BlockChange{Kind: ChangeDelete, Old: &o})
270 }
271 35 for _, ni := range ins {
272 35 n := nw[ni]
273 35 if mp, ok := editedInMove[newKey(ni)]; ok {
274 1 c := modifyChange(old[mp.oldIdx], n)
275 1 c.Moved = true
276 1 out = append(out, c)
277 1 continue
278 }
279 34 if mp, ok := moveOf[newKey(ni)]; ok {
280 5 o := old[mp.oldIdx]
281 5 out = append(out, BlockChange{Kind: ChangeMoveIn, Old: &o, New: &n})
282 5 continue
283 }
284 29 if pairedNew[ni] {
285 18 continue // already emitted as a modification
286 }
287 11 out = append(out, BlockChange{Kind: ChangeInsert, New: &n})
288 }
289 33 return out
290 }
291
292 19 func modifyChange(o, n Block) BlockChange {
293 19 c := BlockChange{Kind: ChangeModify, Old: &o, New: &n}
294 19 if o.Kind.Prose() {
295 15 c.Words = DiffWords(o.Text, n.Text)
296 15 c.StructureOnly = !hasChange(c.Words)
297 15 } else {
298 4 c.Lines = DiffLines(o.Lines, n.Lines)
299 4 c.StructureOnly = !hasChange(c.Lines)
300 4 }
301 19 c.Similarity = blockSimilarity(o, n)
302 19 return c
303 }
304
305 19 func hasChange(spans []Span) bool {
306 37 for _, s := range spans {
307 37 if s.Op != OpEqual {
308 17 return true
309 17 }
310 }
311 2 return false
312 }
313
314 // pairModified greedily matches the most similar delete/insert pairs left in
315 // one changed region, best first.
316 33 func pairModified(old, nw []Block, del, ins []int, moveOf map[int]movePair) []movePair {
317 33 var cand []int
318 33 for _, oi := range del {
319 29 if _, moved := moveOf[oldKey(oi)]; !moved {
320 23 cand = append(cand, oi)
321 23 }
322 }
323 33 var cins []int
324 35 for _, ni := range ins {
325 35 if _, moved := moveOf[newKey(ni)]; !moved {
326 29 cins = append(cins, ni)
327 29 }
328 }
329 33 if len(cand) == 0 || len(cins) == 0 {
330 13 return nil
331 13 }
332 20 windowed := len(cand)*len(cins) > pairBudget
333 20
334 20 type scored struct {
335 20 p movePair
336 20 s float64
337 20 }
338 20 var all []scored
339 20 for a, oi := range cand {
340 20 for b, ni := range cins {
341 20 if windowed && abs(a-b) > pairWindow {
342 0 continue
343 }
344 20 o, n := old[oi], nw[ni]
345 20 if o.Kind != n.Kind {
346 0 continue
347 }
348 20 s := blockSimilarity(o, n)
349 20 if s < thresholdFor(o, n) {
350 2 continue
351 }
352 18 all = append(all, scored{movePair{oi, ni}, s})
353 }
354 }
355 20 sort.SliceStable(all, func(i, j int) bool {
356 0 if all[i].s != all[j].s {
357 0 return all[i].s > all[j].s
358 0 }
359 0 return all[i].p.oldIdx < all[j].p.oldIdx
360 })
361
362 20 usedOld := map[int]bool{}
363 20 usedNew := map[int]bool{}
364 20 var out []movePair
365 20 for _, c := range all {
366 18 if usedOld[c.p.oldIdx] || usedNew[c.p.newIdx] {
367 0 continue
368 }
369 18 usedOld[c.p.oldIdx] = true
370 18 usedNew[c.p.newIdx] = true
371 18 out = append(out, c.p)
372 }
373 20 return out
374 }
375
376 21 func thresholdFor(a, b Block) float64 {
377 21 if len(Tokenize(a.Text)) < shortBlockTokens || len(Tokenize(b.Text)) < shortBlockTokens {
378 4 return shortBlockThreshold
379 4 }
380 17 return modifyThreshold
381 }
382
383 // blockSimilarity is token similarity for prose and line similarity for code.
384 40 func blockSimilarity(a, b Block) float64 {
385 40 in := newInterner()
386 40 if a.Kind.Prose() {
387 32 return ratio(in.all(TokenTexts(Tokenize(a.Text))), in.all(TokenTexts(Tokenize(b.Text))))
388 32 }
389 8 return ratio(in.all(a.Lines), in.all(b.Lines))
390 }
391
392 0 func abs(i int) int {
393 0 if i < 0 {
394 0 return -i
395 0 }
396 0 return i
397 }