1 // Copyright 2017, The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
15 func TestDifference(t *testing.T) {
17 // Before passing x and y to Difference, we strip all spaces so that
18 // they can be used by the test author to indicate a missing symbol
19 // in one of the lists.
21 want string // '|' separated list of possible outputs
55 x: "##########0123456789",
57 want: "XXXXXXXXXX..........",
60 y: "##########0123456789",
61 want: "YYYYYYYYYY..........",
63 x: "#####0123456789#####",
65 want: "XXXXX..........XXXXX",
68 y: "#####0123456789#####",
69 want: "YYYYY..........YYYYY",
71 x: "01234##########56789",
73 want: ".....XXXXXXXXXX.....",
76 y: "01234##########56789",
77 want: ".....YYYYYYYYYY.....",
79 x: "0123456789##########",
81 want: "..........XXXXXXXXXX",
84 y: "0123456789##########",
85 want: "..........YYYYYYYYYY",
87 x: "abcdefghij0123456789",
88 y: "ABCDEFGHIJ0123456789",
89 want: "MMMMMMMMMM..........",
91 x: "ABCDEFGHIJ0123456789",
92 y: "abcdefghij0123456789",
93 want: "MMMMMMMMMM..........",
95 x: "01234abcdefghij56789",
96 y: "01234ABCDEFGHIJ56789",
97 want: ".....MMMMMMMMMM.....",
99 x: "01234ABCDEFGHIJ56789",
100 y: "01234abcdefghij56789",
101 want: ".....MMMMMMMMMM.....",
103 x: "0123456789abcdefghij",
104 y: "0123456789ABCDEFGHIJ",
105 want: "..........MMMMMMMMMM",
107 x: "0123456789ABCDEFGHIJ",
108 y: "0123456789abcdefghij",
109 want: "..........MMMMMMMMMM",
111 x: "ABCDEFGHIJ0123456789 ",
112 y: " 0123456789abcdefghij",
113 want: "XXXXXXXXXX..........YYYYYYYYYY",
115 x: " 0123456789abcdefghij",
116 y: "ABCDEFGHIJ0123456789 ",
117 want: "YYYYYYYYYY..........XXXXXXXXXX",
119 x: "ABCDE0123456789 FGHIJ",
120 y: " 0123456789abcdefghij",
121 want: "XXXXX..........YYYYYMMMMM",
123 x: " 0123456789abcdefghij",
124 y: "ABCDE0123456789 FGHIJ",
125 want: "YYYYY..........XXXXXMMMMM",
127 x: "ABCDE01234F G H I J 56789 ",
128 y: " 01234 a b c d e56789fghij",
129 want: "XXXXX.....XYXYXYXYXY.....YYYYY",
131 x: " 01234a b c d e 56789fghij",
132 y: "ABCDE01234 F G H I J56789 ",
133 want: "YYYYY.....XYXYXYXYXY.....XXXXX",
135 x: "FGHIJ01234ABCDE56789 ",
136 y: " 01234abcde56789fghij",
137 want: "XXXXX.....MMMMM.....YYYYY",
139 x: " 01234abcde56789fghij",
140 y: "FGHIJ01234ABCDE56789 ",
141 want: "YYYYY.....MMMMM.....XXXXX",
145 want: "XX.X.Y..Y|XX.Y.X..Y",
153 want: ".Y....YXY..X.X",
155 x: "###z#z###### x #",
156 y: "#y##Z#Z###### yy#",
157 want: ".Y..M.M......XYY.",
159 x: "0 12z3x 456789 x x 0",
160 y: "0y12Z3 y456789y y y0",
161 want: ".Y..M.XY......YXYXY.|.Y..M.XY......XYXYY.",
163 x: "0 2 4 6 8 ..................abXXcdEXF.ghXi",
164 y: " 1 3 5 7 9..................AB CDE F.GH I",
165 want: "XYXYXYXYXY..................MMXXMM.X..MMXM",
167 x: "I HG.F EDC BA..................9 7 5 3 1 ",
168 y: "iXhg.FXEdcXXba.................. 8 6 4 2 0",
169 want: "MYMM..Y.MMYYMM..................XYXYXYXYXY",
201 want: "YY........XX",
205 want: "YYY.......XXX",
209 want: "YYYY......XXXX",
213 want: "XXXXX.....YYYYY|YYYYY.....XXXXX",
217 want: "XXXX......YYYY",
221 want: "XXX.......YYY",
225 want: "XX........YY",
231 x: "0 1 2 3 45 6 7 8 9 ",
232 y: " 9 8 7 6 54 3 2 1 0",
233 want: "XYXYXYXYX.YXYXYXYXY",
237 want: "XYXY.XX.XX.Y.YYY",
239 x: "F B Q M O I G T L N72X90 E 4S P 651HKRJU DA 83CVZW",
240 y: " 5 W H XO10R9IV K ZLCTAJ8P3N SEQM4 7 2G6 UBD F ",
241 want: "XYXYXYXY.YYYY.YXYXY.YYYYYYY.XXXXXY.YY.XYXYY.XXXXXX.Y.XYXXXXXX",
244 for _, tt := range tests {
245 t.Run("", func(t *testing.T) {
246 x := strings.Replace(tt.x, " ", "", -1)
247 y := strings.Replace(tt.y, " ", "", -1)
248 es := testStrings(t, x, y)
251 for _, want = range strings.Split(tt.want, "|") {
256 t.Errorf("Difference(%s, %s):\ngot %s\nwant %s", x, y, got, want)
261 func TestDifferenceFuzz(t *testing.T) {
262 tests := []struct{ px, py, pm float32 }{
263 {px: 0.0, py: 0.0, pm: 0.1},
264 {px: 0.0, py: 0.1, pm: 0.0},
265 {px: 0.1, py: 0.0, pm: 0.0},
266 {px: 0.0, py: 0.1, pm: 0.1},
267 {px: 0.1, py: 0.0, pm: 0.1},
268 {px: 0.2, py: 0.2, pm: 0.2},
269 {px: 0.3, py: 0.1, pm: 0.2},
270 {px: 0.1, py: 0.3, pm: 0.2},
271 {px: 0.2, py: 0.2, pm: 0.2},
272 {px: 0.3, py: 0.3, pm: 0.3},
273 {px: 0.1, py: 0.1, pm: 0.5},
274 {px: 0.4, py: 0.1, pm: 0.5},
275 {px: 0.3, py: 0.2, pm: 0.5},
276 {px: 0.2, py: 0.3, pm: 0.5},
277 {px: 0.1, py: 0.4, pm: 0.5},
280 for i, tt := range tests {
281 t.Run(fmt.Sprintf("P%d", i), func(t *testing.T) {
282 // Sweep from 1B to 1KiB.
283 for n := 1; n <= 1024; n <<= 1 {
284 t.Run(fmt.Sprintf("N%d", n), func(t *testing.T) {
285 for j := 0; j < 10; j++ {
286 x, y := generateStrings(n, tt.px, tt.py, tt.pm, int64(j))
295 func BenchmarkDifference(b *testing.B) {
296 for n := 1 << 10; n <= 1<<20; n <<= 2 {
297 b.Run(fmt.Sprintf("N%d", n), func(b *testing.B) {
298 x, y := generateStrings(n, 0.05, 0.05, 0.10, 0)
300 b.SetBytes(int64(len(x) + len(y)))
301 for i := 0; i < b.N; i++ {
302 Difference(len(x), len(y), func(ix, iy int) Result {
303 return compareByte(x[ix], y[iy])
310 func generateStrings(n int, px, py, pm float32, seed int64) (string, string) {
312 panic("invalid probabilities")
318 r := rand.New(rand.NewSource(seed))
323 switch p := r.Float32(); {
324 case p < px: // UniqueX
326 case p < py: // UniqueY
328 case p < pm: // Modified
329 x = append(x, 'A'+(b[0]%26))
330 y = append(y, 'a'+(b[0]%26))
337 return string(x), string(y)
340 func testStrings(t *testing.T, x, y string) EditScript {
341 es := Difference(len(x), len(y), func(ix, iy int) Result {
342 return compareByte(x[ix], y[iy])
344 if es.LenX() != len(x) {
345 t.Errorf("es.LenX = %d, want %d", es.LenX(), len(x))
347 if es.LenY() != len(y) {
348 t.Errorf("es.LenY = %d, want %d", es.LenY(), len(y))
350 if !validateScript(x, y, es) {
351 t.Errorf("invalid edit script: %v", es)
356 func validateScript(x, y string, es EditScript) bool {
358 for _, e := range es {
361 if !compareByte(x[len(bx)], y[len(by)]).Equal() {
364 bx = append(bx, x[len(bx)])
365 by = append(by, y[len(by)])
367 bx = append(bx, x[len(bx)])
369 by = append(by, y[len(by)])
371 if !compareByte(x[len(bx)], y[len(by)]).Similar() {
374 bx = append(bx, x[len(bx)])
375 by = append(by, y[len(by)])
378 return string(bx) == x && string(by) == y
381 // compareByte returns a Result where the result is Equal if x == y,
382 // similar if x and y differ only in casing, and different otherwise.
383 func compareByte(x, y byte) (r Result) {
386 return equalResult // Identity
387 case unicode.ToUpper(rune(x)) == unicode.ToUpper(rune(y)):
388 return similarResult // Modified
390 return differentResult // UniqueX or UniqueY
395 equalResult = Result{NumDiff: 0}
396 similarResult = Result{NumDiff: 1}
397 differentResult = Result{NumDiff: 2}
400 func TestResult(t *testing.T) {
406 // equalResult is equal since NumDiff == 0, by definition of Equal method.
407 {equalResult, true, true},
408 // similarResult is similar since it is a binary result where only one
409 // element was compared (i.e., Either NumSame==1 or NumDiff==1).
410 {similarResult, false, true},
411 // differentResult is different since there are enough differences that
412 // it isn't even considered similar.
413 {differentResult, false, false},
415 // Zero value is always equal.
416 {Result{NumSame: 0, NumDiff: 0}, true, true},
418 // Binary comparisons (where NumSame+NumDiff == 1) are always similar.
419 {Result{NumSame: 1, NumDiff: 0}, true, true},
420 {Result{NumSame: 0, NumDiff: 1}, false, true},
422 // More complex ratios. The exact ratio for similarity may change,
423 // and may require updates to these test cases.
424 {Result{NumSame: 1, NumDiff: 1}, false, true},
425 {Result{NumSame: 1, NumDiff: 2}, false, true},
426 {Result{NumSame: 1, NumDiff: 3}, false, false},
427 {Result{NumSame: 2, NumDiff: 1}, false, true},
428 {Result{NumSame: 2, NumDiff: 2}, false, true},
429 {Result{NumSame: 2, NumDiff: 3}, false, true},
430 {Result{NumSame: 3, NumDiff: 1}, false, true},
431 {Result{NumSame: 3, NumDiff: 2}, false, true},
432 {Result{NumSame: 3, NumDiff: 3}, false, true},
433 {Result{NumSame: 1000, NumDiff: 0}, true, true},
434 {Result{NumSame: 1000, NumDiff: 1}, false, true},
435 {Result{NumSame: 1000, NumDiff: 2}, false, true},
436 {Result{NumSame: 0, NumDiff: 1000}, false, false},
437 {Result{NumSame: 1, NumDiff: 1000}, false, false},
438 {Result{NumSame: 2, NumDiff: 1000}, false, false},
441 for _, tt := range tests {
442 if got := tt.result.Equal(); got != tt.wantEqual {
443 t.Errorf("%#v.Equal() = %v, want %v", tt.result, got, tt.wantEqual)
445 if got := tt.result.Similar(); got != tt.wantSimilar {
446 t.Errorf("%#v.Similar() = %v, want %v", tt.result, got, tt.wantSimilar)