myersdiff_test.gno
9.83 Kb · 278 lines
1package myersdiff
2
3import (
4 "strings"
5 "testing"
6
7 "gno.land/p/nt/uassert/v0"
8)
9
10// render turns a script into one compact string per line, so a table case can
11// state the whole expected script as text instead of a slice literal.
12func render(s Script) string {
13 var sb strings.Builder
14 for i, e := range s.Edits {
15 if i > 0 {
16 sb.WriteString("|")
17 }
18 sb.WriteString(e.Op.String())
19 sb.WriteString(e.Line)
20 }
21 return sb.String()
22}
23
24func TestScript(t *testing.T) {
25 cases := []struct {
26 name string
27 a string
28 b string
29 want string
30 }{
31 {"identical", "a\nb\nc", "a\nb\nc", " a| b| c"},
32 {"both empty", "", "", ""},
33 {"insert into empty", "", "a\nb", "+a|+b"},
34 {"delete to empty", "a\nb", "", "-a|-b"},
35 {"append one", "a", "a\nb", " a|+b"},
36 {"prepend one", "b", "a\nb", "+a| b"},
37 {"substitute middle", "a\nb\nc", "a\nx\nc", " a|-b|+x| c"},
38 {"delete middle", "a\nb\nc", "a\nc", " a|-b| c"},
39 {"nothing in common", "a\nb", "x\ny", "-a|-b|+x|+y"},
40 {"trailing newline is a line", "a", "a\n", " a|+"},
41 {"move one line down", "a\nb\nc", "b\nc\na", "-a| b| c|+a"},
42 }
43
44 for _, tc := range cases {
45 t.Run(tc.name, func(t *testing.T) {
46 got := Lines(tc.a, tc.b)
47 uassert.True(t, got.Minimal, "expected a minimal script")
48 uassert.Equal(t, tc.want, render(got))
49 })
50 }
51}
52
53// TestScriptIsShortest is the property the algorithm exists for. A correct but
54// lazy implementation (delete everything, insert everything) passes every
55// round-trip test, so the count of changed lines is asserted separately.
56func TestScriptIsShortest(t *testing.T) {
57 cases := []struct {
58 name string
59 a string
60 b string
61 changed int
62 }{
63 {"one substitution", "a\nb\nc", "a\nx\nc", 2},
64 {"one insertion", "a\nb\nc", "a\nb\nx\nc", 1},
65 {"one deletion", "a\nb\nc", "a\nc", 1},
66 {"two far apart", "a\nb\nc\nd\ne", "x\nb\nc\nd\ny", 4},
67 {"classic abcabba to cbabac", "a\nb\nc\na\nb\nb\na", "c\nb\na\nb\na\nc", 5},
68 }
69
70 for _, tc := range cases {
71 t.Run(tc.name, func(t *testing.T) {
72 s := Lines(tc.a, tc.b)
73 changed := s.Added() + s.Deleted()
74 uassert.Equal(t, tc.changed, changed)
75 })
76 }
77}
78
79// TestApplyRoundTrips is the correctness half: whatever script comes out, it
80// has to turn a back into b. Checked on the minimal path and on the budget
81// fallback, because the fallback is the one nobody looks at.
82func TestApplyRoundTrips(t *testing.T) {
83 cases := []struct {
84 name string
85 a string
86 b string
87 budget int
88 }{
89 {"typical patch", "one\ntwo\nthree\nfour", "one\n2\nthree\nfour\nfive", 0},
90 {"full rewrite", "a\nb\nc\nd", "w\nx\ny\nz", 0},
91 {"starved budget", "a\nb\nc\nd", "w\nx\ny\nz", 1},
92 {"empty to empty", "", "", 0},
93 {"repeated lines", "x\nx\nx\nx", "x\nx", 0},
94 }
95
96 for _, tc := range cases {
97 t.Run(tc.name, func(t *testing.T) {
98 s := Budget(split(tc.a), split(tc.b), tc.budget)
99 lines, ok := s.Apply(split(tc.a))
100 uassert.True(t, ok, "the script should describe its own source")
101 uassert.Equal(t, tc.b, strings.Join(lines, "\n"))
102 })
103 }
104}
105
106// TestBudgetFallback pins what a starved search returns. The script stops being
107// minimal and says so; it does not stop being correct and it does not panic.
108func TestBudgetFallback(t *testing.T) {
109 a := split("a\nb\nc\nd\ne\nf")
110 b := split("u\nv\nw\nx\ny\nz")
111
112 starved := Budget(a, b, 2)
113 uassert.False(t, starved.Minimal, "a two-round budget cannot reach a 12-edit script")
114 uassert.Equal(t, 6, starved.Deleted())
115 uassert.Equal(t, 6, starved.Added())
116 uassert.Equal(t, 0, starved.Unchanged())
117
118 full := Budget(a, b, 0)
119 uassert.True(t, full.Minimal, "the default budget is enough for six lines")
120 applied, ok := full.Apply(a)
121 uassert.True(t, ok, "the minimal script should describe its own source")
122 uassert.Equal(t, strings.Join(b, "\n"), strings.Join(applied, "\n"))
123
124 // A budget above what the script needs changes nothing, and a budget larger
125 // than any possible script is not an error.
126 wide := Budget(a, b, 10000)
127 uassert.True(t, wide.Minimal, "an oversized budget still terminates")
128 uassert.Equal(t, render(full), render(wide))
129}
130
131func TestCounts(t *testing.T) {
132 s := Lines("a\nb\nc", "a\nx\ny\nc")
133 uassert.Equal(t, 2, s.Added())
134 uassert.Equal(t, 1, s.Deleted())
135 uassert.Equal(t, 2, s.Unchanged())
136}
137
138func TestHunks(t *testing.T) {
139 // Eleven lines, two changes far enough apart to stay separate at context 1
140 // and to merge at context 3.
141 a := "1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n11"
142 b := "1\n2\nX\n4\n5\n6\n7\n8\nY\n10\n11"
143 s := Lines(a, b)
144
145 narrow := Hunks(s, 1)
146 uassert.Equal(t, 2, len(narrow))
147 uassert.Equal(t, "@@ -2,3 +2,3 @@", narrow[0].Header())
148 uassert.Equal(t, "@@ -8,3 +8,3 @@", narrow[1].Header())
149
150 wide := Hunks(s, 3)
151 uassert.Equal(t, 1, len(wide))
152 uassert.Equal(t, "@@ -1,11 +1,11 @@", wide[0].Header())
153
154 none := Hunks(Lines(a, a), 3)
155 uassert.Equal(t, 0, len(none))
156
157 zero := Hunks(s, 0)
158 uassert.Equal(t, 2, len(zero))
159 uassert.Equal(t, "@@ -3 +3 @@", zero[0].Header())
160}
161
162// TestHunkHeaderEmptySide pins the one header convention that is not obvious:
163// a side contributing no lines reports the line before the hunk and a length of
164// zero, which is what diff(1) prints and what patch(1) expects to read back.
165func TestHunkHeaderEmptySide(t *testing.T) {
166 into := Hunks(Lines("", "a\nb"), 0)
167 uassert.Equal(t, 1, len(into))
168 uassert.Equal(t, "@@ -0,0 +1,2 @@", into[0].Header())
169
170 outOf := Hunks(Lines("a\nb", ""), 0)
171 uassert.Equal(t, 1, len(outOf))
172 uassert.Equal(t, "@@ -1,2 +0,0 @@", outOf[0].Header())
173
174 negative := Hunks(Lines("a", "b"), -5)
175 uassert.Equal(t, 1, len(negative))
176 uassert.Equal(t, "@@ -1 +1 @@", negative[0].Header())
177}
178
179func TestUnified(t *testing.T) {
180 a := "the quick\nbrown fox\njumps over\nthe lazy dog"
181 b := "the quick\nred fox\njumps over\nthe lazy dog\nand runs"
182
183 want := "@@ -1,4 +1,5 @@\n the quick\n-brown fox\n+red fox\n jumps over\n the lazy dog\n+and runs\n"
184 uassert.Equal(t, want, Unified(a, b, 3))
185
186 uassert.Equal(t, "", Unified(a, a, 3))
187 uassert.Equal(t, Unified(a, b, 3), UnifiedScript(Lines(a, b), 3))
188}
189
190func TestOpString(t *testing.T) {
191 uassert.Equal(t, "-", Delete.String())
192 uassert.Equal(t, " ", Equal.String())
193 uassert.Equal(t, "+", Insert.String())
194}
195
196func TestMaxLines(cur realm, t *testing.T) {
197 big := make([]string, MaxLines+1)
198 ok := make([]string, MaxLines)
199 uassert.PanicsWithMessage(t, cur, "myersdiff: input exceeds MaxLines", func() { Budget(big, ok, 0) })
200 uassert.PanicsWithMessage(t, cur, "myersdiff: input exceeds MaxLines", func() { Budget(ok, big, 0) })
201 // MaxLines identical lines is the cheap case: d is zero, so the search ends
202 // in the first round whatever the size.
203 uassert.NotPanics(t, cur, func() { Budget(ok, ok, 0) })
204}
205
206// TestApplyChecksTheSourceIsWhatTheScriptDescribes closes the gap a review
207// found on the first pass: Apply used to ignore its argument entirely, so it
208// replayed any script into the script's own right-hand side and reported
209// nothing. The round trip then proved only that the script agreed with itself,
210// and the demo's applies() check was vacuous for the same reason.
211func TestApplyChecksTheSourceIsWhatTheScriptDescribes(t *testing.T) {
212 s := Lines("a\nb\nc", "a\nx\nc")
213
214 got, ok := s.Apply([]string{"a", "b", "c"})
215 uassert.True(t, ok, "the script's own source should be accepted")
216 uassert.Equal(t, "a\nx\nc", strings.Join(got, "\n"))
217
218 _, ok = s.Apply([]string{"q", "b", "c"})
219 uassert.False(t, ok, "an Equal line absent from the source is not a script for it")
220
221 _, ok = s.Apply([]string{"a", "q", "c"})
222 uassert.False(t, ok, "a Delete line absent from the source is not a script for it")
223
224 _, ok = s.Apply([]string{"a", "b"})
225 uassert.False(t, ok, "a source shorter than the script consumes")
226
227 _, ok = s.Apply([]string{"a", "b", "c", "d"})
228 uassert.False(t, ok, "a source with a line the script never consumed")
229
230 _, ok = s.Apply([]string{})
231 uassert.False(t, ok, "an empty source against a three-line script")
232}
233
234// TestLinesEnforcesTheLineCap covers the other half of the same review:
235// MaxLines guarded the comparison but not the strings.Split in front of it, so
236// a caller could force an arbitrarily large line slice and only then be
237// refused. Nothing here distinguishes the two orders, because the difference is
238// an allocation and gno test cannot observe one. What it does pin is that Lines
239// and Unified enforce the cap at all, which nothing asserted before.
240func TestLinesEnforcesTheLineCap(cur realm, t *testing.T) {
241 over := strings.Repeat("x\n", MaxLines)
242 atCap := strings.Repeat("x\n", MaxLines-1) + "x"
243
244 uassert.PanicsWithMessage(t, cur, "myersdiff: input exceeds MaxLines", func() { Lines(over, "") })
245 uassert.PanicsWithMessage(t, cur, "myersdiff: input exceeds MaxLines", func() { Lines("", over) })
246 uassert.PanicsWithMessage(t, cur, "myersdiff: input exceeds MaxLines", func() { Unified("", over, 1) })
247 uassert.NotPanics(t, cur, func() { Lines(atCap, atCap) })
248}
249
250// TestEffectiveRounds pins the one number that decides how much memory the
251// search can be made to allocate. The frontier is snapshotted once per round,
252// so the round count is the memory bound, and before MaxBudget existed a caller
253// could ask for 8,192 rounds by passing a large budget with two MaxLines
254// documents. This is asserted directly rather than through a diff, because the
255// inputs that would show it behaviourally take minutes to run.
256func TestEffectiveRounds(t *testing.T) {
257 cases := []struct {
258 name string
259 budget int
260 n, m int
261 want int
262 }{
263 {"default applies when unset", 0, 1000, 1000, DefaultBudget},
264 {"default applies when negative", -7, 1000, 1000, DefaultBudget},
265 {"a small budget is kept", 5, 100, 100, 5},
266 {"no script is longer than n+m", 0, 10, 10, 20},
267 {"a large budget is capped at MaxBudget", 100000, MaxLines, MaxLines, MaxBudget},
268 {"MaxBudget never exceeds n+m either", 100000, 3, 4, 7},
269 }
270
271 for _, tc := range cases {
272 t.Run(tc.name, func(t *testing.T) {
273 uassert.Equal(t, tc.want, effectiveRounds(tc.budget, tc.n, tc.m))
274 })
275 }
276
277 uassert.True(t, MaxBudget >= DefaultBudget, "the cap must leave the default reachable")
278}
