myersdiff.gno
12.69 Kb · 452 lines
1// Package myersdiff computes the shortest edit script between two sequences of
2// lines, using Myers' greedy algorithm: the same one git, diff and every review
3// tool run to turn two documents into a list of additions and deletions.
4//
5// A realm that stores text and lets it be edited has two versions of it and no
6// way to show what moved between them. Storing a diff instead of a snapshot is
7// the usual answer, and this is the half that produces it.
8//
9// The cost of the search is bounded by a budget, not by the input size alone:
10// see [Budget] for why a minimal diff is sometimes the wrong answer on chain.
11//
12// Live demo: [r/moul/x/daily/myersdiffdemo](/r/moul/x/daily/myersdiffdemo/v0).
13package myersdiff
14
15import (
16 "strconv"
17 "strings"
18)
19
20// Op is what happened to one line.
21type Op int8
22
23const (
24 // Delete marks a line present in a and absent from b.
25 Delete Op = -1
26 // Equal marks a line present in both, unchanged.
27 Equal Op = 0
28 // Insert marks a line absent from a and present in b.
29 Insert Op = 1
30)
31
32// String renders the op as the single character a unified diff uses.
33func (o Op) String() string {
34 switch o {
35 case Delete:
36 return "-"
37 case Insert:
38 return "+"
39 default:
40 return " "
41 }
42}
43
44// Edit is one line of the edit script.
45type Edit struct {
46 Op Op
47 Line string
48}
49
50// Script is a complete edit script turning a into b.
51//
52// Minimal is false when the search hit its budget and the script fell back to
53// deleting everything and inserting everything. That script is still correct:
54// applying it to a yields b. It is simply not the shortest one.
55type Script struct {
56 Edits []Edit
57 Minimal bool
58}
59
60// Added counts inserted lines.
61func (s Script) Added() int { return s.count(Insert) }
62
63// Deleted counts deleted lines.
64func (s Script) Deleted() int { return s.count(Delete) }
65
66// Unchanged counts lines carried over untouched.
67func (s Script) Unchanged() int { return s.count(Equal) }
68
69func (s Script) count(op Op) int {
70 n := 0
71 for _, e := range s.Edits {
72 if e.Op == op {
73 n++
74 }
75 }
76 return n
77}
78
79// Apply replays the script against a and returns the lines it produces, which
80// is b when the script came from Slices(a, b).
81//
82// The second return reports whether a is the document the script describes:
83// every Equal and Delete edit has to match the line it consumes, and the script
84// has to consume all of a. It is false for a script built against a different
85// document, which is the check that makes a stored diff verifiable rather than
86// merely replayable. The lines are returned either way, because they are what
87// the script says and a caller deciding what to do about a mismatch usually
88// wants to see both.
89func (s Script) Apply(a []string) ([]string, bool) {
90 out := []string{}
91 ok := true
92 i := 0
93 for _, e := range s.Edits {
94 switch e.Op {
95 case Equal:
96 if i >= len(a) || a[i] != e.Line {
97 ok = false
98 }
99 i++
100 out = append(out, e.Line)
101 case Delete:
102 if i >= len(a) || a[i] != e.Line {
103 ok = false
104 }
105 i++
106 case Insert:
107 out = append(out, e.Line)
108 }
109 }
110 if i != len(a) {
111 ok = false
112 }
113 return out, ok
114}
115
116// DefaultBudget caps the number of rounds the search may run before it gives up
117// and returns a non-minimal script. Myers' algorithm costs O((n+m)*d) where d is
118// the number of differing lines, so two similar documents are cheap at any size
119// and two unrelated ones are quadratic. On chain the caller picks the input, so
120// the cost has to be bounded by something the caller does not control.
121//
122// The threshold this sets is worth stating plainly, because it is not a size:
123// the default gives up past 256 changed lines, at any file size. Two 4,000-line
124// documents differing in 10 lines are diffed minimally; two 300-line documents
125// sharing nothing are not. A caller whose documents are large and similar is
126// well inside it; a caller diffing unrelated text is always outside it and
127// should pass a small budget rather than pay for the search before the
128// fallback.
129//
130// The cost is in gas, not just in time: a search that runs to the default
131// ceiling against two MaxLines documents was measured in the billions of gas
132// against a 3,000,000,000 block limit during the review of this package, before
133// the frontier was resized to the round ceiling. Treat a full-ceiling search as
134// something to avoid rather than something to budget for.
135const DefaultBudget = 256
136
137// MaxBudget is the hard ceiling on the rounds any caller can ask for, whatever
138// budget it passes.
139//
140// It exists because the round count, not the input size, is what the search
141// allocates against: one snapshot of the frontier is kept per round so the
142// script can be walked back out of them. Without the ceiling, two documents at
143// MaxLines and a large budget would permit 8,192 snapshots, and the budget
144// parameter would hand a caller the memory bill as a dial. The useful direction
145// for a caller is downwards.
146const MaxBudget = 1024
147
148// MaxLines caps each side of the comparison. The algorithm allocates two slices
149// proportional to n+m before it compares anything, so the size is checked before
150// the work starts rather than discovered during it.
151const MaxLines = 4096
152
153// Lines splits a and b on "\n" and diffs them with DefaultBudget.
154//
155// A trailing newline produces a trailing empty line on that side, which is what
156// makes "a\n" and "a" different documents here, as they are to diff(1).
157func Lines(a, b string) Script {
158 checkLineCap(a)
159 checkLineCap(b)
160 return Slices(split(a), split(b))
161}
162
163// checkLineCap refuses an oversized document before strings.Split allocates a
164// slice for it. MaxLines is checked again in Budget, for a caller that supplies
165// its own slices; this is the copy that matters, because counting newlines
166// allocates nothing and splitting them allocates everything.
167func checkLineCap(s string) {
168 if s == "" {
169 return
170 }
171 if strings.Count(s, "\n")+1 > MaxLines {
172 panic("myersdiff: input exceeds MaxLines")
173 }
174}
175
176func split(s string) []string {
177 if s == "" {
178 return []string{}
179 }
180 return strings.Split(s, "\n")
181}
182
183// Slices diffs two line sequences with DefaultBudget.
184func Slices(a, b []string) Script {
185 return Budget(a, b, DefaultBudget)
186}
187
188// Budget diffs two line sequences, stopping the search after at most budget
189// rounds. A budget of zero or less means DefaultBudget; a budget larger than
190// len(a)+len(b) is capped at it, since no minimal script is longer than that.
191//
192// It panics when either side exceeds MaxLines. Construction is a transaction,
193// where aborting is the useful answer; reading is where totality matters, and
194// every method on the resulting Script is total.
195func Budget(a, b []string, budget int) Script {
196 if len(a) > MaxLines || len(b) > MaxLines {
197 panic("myersdiff: input exceeds MaxLines")
198 }
199 if budget <= 0 {
200 budget = DefaultBudget
201 }
202 edits, ok := search(a, b, effectiveRounds(budget, len(a), len(b)))
203 if !ok {
204 return Script{Edits: replaceAll(a, b), Minimal: false}
205 }
206 return Script{Edits: edits, Minimal: true}
207}
208
209func replaceAll(a, b []string) []Edit {
210 edits := []Edit{}
211 for _, line := range a {
212 edits = append(edits, Edit{Op: Delete, Line: line})
213 }
214 for _, line := range b {
215 edits = append(edits, Edit{Op: Insert, Line: line})
216 }
217 return edits
218}
219
220// effectiveRounds is how many rounds the search may run: the caller's budget,
221// defaulted when unset and capped by both MaxBudget and n+m, since no minimal
222// script is longer than n+m.
223func effectiveRounds(budget, n, m int) int {
224 if budget <= 0 {
225 budget = DefaultBudget
226 }
227 if budget > MaxBudget {
228 budget = MaxBudget
229 }
230 if budget > n+m {
231 budget = n + m
232 }
233 return budget
234}
235
236// search runs the greedy forward pass, recording one snapshot of the frontier
237// per round, then walks the snapshots backwards into an edit script. It reports
238// false when the budget ran out before the two ends met.
239func search(a, b []string, budget int) ([]Edit, bool) {
240 n := len(a)
241 m := len(b)
242 maxD := budget
243
244 // At round d only the diagonals -d..d are live, and d never exceeds maxD,
245 // so the frontier is sized by the round ceiling rather than by the input.
246 // That is what keeps a snapshot small when two large documents are being
247 // compared under a small budget.
248 offset := maxD + 1
249 v := make([]int, 2*maxD+3)
250 trace := [][]int{}
251
252 for d := 0; d <= maxD; d++ {
253 snapshot := make([]int, len(v))
254 copy(snapshot, v)
255 trace = append(trace, snapshot)
256
257 for k := -d; k <= d; k += 2 {
258 var x int
259 // Move down (an insertion) when the diagonal below reaches further,
260 // or when there is no diagonal to the left to come from at all.
261 if k == -d || (k != d && v[offset+k-1] < v[offset+k+1]) {
262 x = v[offset+k+1]
263 } else {
264 x = v[offset+k-1] + 1
265 }
266 y := x - k
267 for x < n && y < m && a[x] == b[y] {
268 x++
269 y++
270 }
271 v[offset+k] = x
272 if x >= n && y >= m {
273 return backtrack(a, b, trace, offset), true
274 }
275 }
276 }
277 return nil, false
278}
279
280// backtrack walks the recorded frontiers from the end back to the origin. Each
281// snapshot is the state before its own round, so the same rule that chose a move
282// forwards identifies the predecessor backwards.
283func backtrack(a, b []string, trace [][]int, offset int) []Edit {
284 x := len(a)
285 y := len(b)
286 rev := []Edit{}
287
288 for d := len(trace) - 1; d >= 0; d-- {
289 v := trace[d]
290 k := x - y
291
292 var prevK int
293 if k == -d || (k != d && v[offset+k-1] < v[offset+k+1]) {
294 prevK = k + 1
295 } else {
296 prevK = k - 1
297 }
298 prevX := v[offset+prevK]
299 prevY := prevX - prevK
300
301 for x > prevX && y > prevY {
302 rev = append(rev, Edit{Op: Equal, Line: a[x-1]})
303 x--
304 y--
305 }
306 if d > 0 {
307 if x == prevX {
308 rev = append(rev, Edit{Op: Insert, Line: b[prevY]})
309 } else {
310 rev = append(rev, Edit{Op: Delete, Line: a[prevX]})
311 }
312 }
313 x = prevX
314 y = prevY
315 }
316
317 edits := make([]Edit, len(rev))
318 for i, e := range rev {
319 edits[len(rev)-1-i] = e
320 }
321 return edits
322}
323
324// Hunk is a contiguous run of the script worth printing: every change, plus up
325// to context unchanged lines on each side of it.
326//
327// AStart and BStart are 1-based line numbers. When a side contributes no lines
328// at all, its start is the number of the line before the hunk and its length is
329// zero, which is what diff(1) prints for a pure insertion into an empty file.
330type Hunk struct {
331 AStart int
332 ALines int
333 BStart int
334 BLines int
335 Edits []Edit
336}
337
338// Header renders the @@ line of a unified diff.
339func (h Hunk) Header() string {
340 return "@@ -" + rangeOf(h.AStart, h.ALines) + " +" + rangeOf(h.BStart, h.BLines) + " @@"
341}
342
343func rangeOf(start, length int) string {
344 if length == 1 {
345 return strconv.Itoa(start)
346 }
347 return strconv.Itoa(start) + "," + strconv.Itoa(length)
348}
349
350// Hunks groups a script into the runs a unified diff prints, with context
351// unchanged lines around each change. A negative context is treated as zero; a
352// script with no changes produces no hunks.
353func Hunks(s Script, context int) []Hunk {
354 if context < 0 {
355 context = 0
356 }
357 edits := s.Edits
358
359 // aPos[i] and bPos[i] are how many lines of each side precede edit i.
360 aPos := make([]int, len(edits)+1)
361 bPos := make([]int, len(edits)+1)
362 for i, e := range edits {
363 aPos[i+1] = aPos[i]
364 bPos[i+1] = bPos[i]
365 if e.Op != Insert {
366 aPos[i+1]++
367 }
368 if e.Op != Delete {
369 bPos[i+1]++
370 }
371 }
372
373 hunks := []Hunk{}
374 i := 0
375 for i < len(edits) {
376 if edits[i].Op == Equal {
377 i++
378 continue
379 }
380
381 start := i - context
382 if start < 0 {
383 start = 0
384 }
385 last := i
386
387 // Extend while the next change is close enough that the context around
388 // the two would overlap. A longer run of equals ends the hunk.
389 j := i + 1
390 for j < len(edits) {
391 if edits[j].Op != Equal {
392 last = j
393 j++
394 continue
395 }
396 run := 0
397 for j+run < len(edits) && edits[j+run].Op == Equal {
398 run++
399 }
400 if j+run >= len(edits) || run > 2*context {
401 break
402 }
403 j += run
404 }
405
406 stop := last + context
407 if stop > len(edits)-1 {
408 stop = len(edits) - 1
409 }
410
411 h := Hunk{
412 AStart: aPos[start] + 1,
413 ALines: aPos[stop+1] - aPos[start],
414 BStart: bPos[start] + 1,
415 BLines: bPos[stop+1] - bPos[start],
416 Edits: edits[start : stop+1],
417 }
418 if h.ALines == 0 {
419 h.AStart = aPos[start]
420 }
421 if h.BLines == 0 {
422 h.BStart = bPos[start]
423 }
424 hunks = append(hunks, h)
425
426 i = stop + 1
427 }
428 return hunks
429}
430
431// Unified renders the body of a unified diff: the @@ headers and their lines,
432// and nothing else. The --- and +++ file headers name files, which a realm does
433// not have, so they are the caller's to add.
434func Unified(a, b string, context int) string {
435 return UnifiedScript(Lines(a, b), context)
436}
437
438// UnifiedScript renders an already-computed script, for a caller that wants the
439// counts or the Minimal flag as well as the text.
440func UnifiedScript(s Script, context int) string {
441 var sb strings.Builder
442 for _, h := range Hunks(s, context) {
443 sb.WriteString(h.Header())
444 sb.WriteString("\n")
445 for _, e := range h.Edits {
446 sb.WriteString(e.Op.String())
447 sb.WriteString(e.Line)
448 sb.WriteString("\n")
449 }
450 }
451 return sb.String()
452}
