1// Copyright (c) 2012-2016 The go-diff authors. All rights reserved. 2// https://github.com/sergi/go-diff 3// See the included LICENSE file for license details. 4// 5// go-diff is a Go implementation of Google's Diff, Match, and Patch library 6// Original library is Copyright (c) 2006 Google Inc. 7// http://code.google.com/p/google-diff-match-patch/ 8 9package diffmatchpatch 10 11import ( 12 "bytes" 13 "fmt" 14 "strconv" 15 "strings" 16 "testing" 17 "time" 18 "unicode/utf8" 19 20 "github.com/stretchr/testify/assert" 21) 22 23func pretty(diffs []Diff) string { 24 var w bytes.Buffer 25 26 for i, diff := range diffs { 27 _, _ = w.WriteString(fmt.Sprintf("%v. ", i)) 28 29 switch diff.Type { 30 case DiffInsert: 31 _, _ = w.WriteString("DiffIns") 32 case DiffDelete: 33 _, _ = w.WriteString("DiffDel") 34 case DiffEqual: 35 _, _ = w.WriteString("DiffEql") 36 default: 37 _, _ = w.WriteString("Unknown") 38 } 39 40 _, _ = w.WriteString(fmt.Sprintf(": %v\n", diff.Text)) 41 } 42 43 return w.String() 44} 45 46func diffRebuildTexts(diffs []Diff) []string { 47 texts := []string{"", ""} 48 49 for _, d := range diffs { 50 if d.Type != DiffInsert { 51 texts[0] += d.Text 52 } 53 if d.Type != DiffDelete { 54 texts[1] += d.Text 55 } 56 } 57 58 return texts 59} 60 61func TestDiffCommonPrefix(t *testing.T) { 62 type TestCase struct { 63 Name string 64 65 Text1 string 66 Text2 string 67 68 Expected int 69 } 70 71 dmp := New() 72 73 for i, tc := range []TestCase{ 74 {"Null", "abc", "xyz", 0}, 75 {"Non-null", "1234abcdef", "1234xyz", 4}, 76 {"Whole", "1234", "1234xyz", 4}, 77 } { 78 actual := dmp.DiffCommonPrefix(tc.Text1, tc.Text2) 79 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) 80 } 81} 82 83func BenchmarkDiffCommonPrefix(b *testing.B) { 84 s := "ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ" 85 86 dmp := New() 87 88 for i := 0; i < b.N; i++ { 89 dmp.DiffCommonPrefix(s, s) 90 } 91} 92 93func TestCommonPrefixLength(t *testing.T) { 94 type TestCase struct { 95 Text1 string 96 Text2 string 97 98 Expected int 99 } 100 101 for i, tc := range []TestCase{ 102 {"abc", "xyz", 0}, 103 {"1234abcdef", "1234xyz", 4}, 104 {"1234", "1234xyz", 4}, 105 } { 106 actual := commonPrefixLength([]rune(tc.Text1), []rune(tc.Text2)) 107 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) 108 } 109} 110 111func TestDiffCommonSuffix(t *testing.T) { 112 type TestCase struct { 113 Name string 114 115 Text1 string 116 Text2 string 117 118 Expected int 119 } 120 121 dmp := New() 122 123 for i, tc := range []TestCase{ 124 {"Null", "abc", "xyz", 0}, 125 {"Non-null", "abcdef1234", "xyz1234", 4}, 126 {"Whole", "1234", "xyz1234", 4}, 127 } { 128 actual := dmp.DiffCommonSuffix(tc.Text1, tc.Text2) 129 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) 130 } 131} 132 133var SinkInt int // exported sink var to avoid compiler optimizations in benchmarks 134 135func BenchmarkDiffCommonSuffix(b *testing.B) { 136 s := "ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ" 137 138 dmp := New() 139 140 b.ResetTimer() 141 142 for i := 0; i < b.N; i++ { 143 SinkInt = dmp.DiffCommonSuffix(s, s) 144 } 145} 146 147func BenchmarkCommonLength(b *testing.B) { 148 data := []struct { 149 name string 150 x, y []rune 151 }{ 152 {name: "empty", x: nil, y: []rune{}}, 153 {name: "short", x: []rune("AABCC"), y: []rune("AA-CC")}, 154 {name: "long", 155 x: []rune(strings.Repeat("A", 1000) + "B" + strings.Repeat("C", 1000)), 156 y: []rune(strings.Repeat("A", 1000) + "-" + strings.Repeat("C", 1000)), 157 }, 158 } 159 b.Run("prefix", func(b *testing.B) { 160 for _, d := range data { 161 b.Run(d.name, func(b *testing.B) { 162 for i := 0; i < b.N; i++ { 163 SinkInt = commonPrefixLength(d.x, d.y) 164 } 165 }) 166 } 167 }) 168 b.Run("suffix", func(b *testing.B) { 169 for _, d := range data { 170 b.Run(d.name, func(b *testing.B) { 171 for i := 0; i < b.N; i++ { 172 SinkInt = commonSuffixLength(d.x, d.y) 173 } 174 }) 175 } 176 }) 177} 178 179func TestCommonSuffixLength(t *testing.T) { 180 type TestCase struct { 181 Text1 string 182 Text2 string 183 184 Expected int 185 } 186 187 for i, tc := range []TestCase{ 188 {"abc", "xyz", 0}, 189 {"abcdef1234", "xyz1234", 4}, 190 {"1234", "xyz1234", 4}, 191 {"123", "a3", 1}, 192 } { 193 actual := commonSuffixLength([]rune(tc.Text1), []rune(tc.Text2)) 194 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) 195 } 196} 197 198func TestDiffCommonOverlap(t *testing.T) { 199 type TestCase struct { 200 Name string 201 202 Text1 string 203 Text2 string 204 205 Expected int 206 } 207 208 dmp := New() 209 210 for i, tc := range []TestCase{ 211 {"Null", "", "abcd", 0}, 212 {"Whole", "abc", "abcd", 3}, 213 {"Null", "123456", "abcd", 0}, 214 {"Null", "123456xxx", "xxxabcd", 3}, 215 // Some overly clever languages (C#) may treat ligatures as equal to their component letters, e.g. U+FB01 == 'fi' 216 {"Unicode", "fi", "\ufb01i", 0}, 217 } { 218 actual := dmp.DiffCommonOverlap(tc.Text1, tc.Text2) 219 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) 220 } 221} 222 223func TestDiffHalfMatch(t *testing.T) { 224 type TestCase struct { 225 Text1 string 226 Text2 string 227 228 Expected []string 229 } 230 231 dmp := New() 232 dmp.DiffTimeout = 1 233 234 for i, tc := range []TestCase{ 235 // No match 236 {"1234567890", "abcdef", nil}, 237 {"12345", "23", nil}, 238 239 // Single Match 240 {"1234567890", "a345678z", []string{"12", "90", "a", "z", "345678"}}, 241 {"a345678z", "1234567890", []string{"a", "z", "12", "90", "345678"}}, 242 {"abc56789z", "1234567890", []string{"abc", "z", "1234", "0", "56789"}}, 243 {"a23456xyz", "1234567890", []string{"a", "xyz", "1", "7890", "23456"}}, 244 245 // Multiple Matches 246 {"121231234123451234123121", "a1234123451234z", []string{"12123", "123121", "a", "z", "1234123451234"}}, 247 {"x-=-=-=-=-=-=-=-=-=-=-=-=", "xx-=-=-=-=-=-=-=", []string{"", "-=-=-=-=-=", "x", "", "x-=-=-=-=-=-=-="}}, 248 {"-=-=-=-=-=-=-=-=-=-=-=-=y", "-=-=-=-=-=-=-=yy", []string{"-=-=-=-=-=", "", "", "y", "-=-=-=-=-=-=-=y"}}, 249 250 // Non-optimal halfmatch, ptimal diff would be -q+x=H-i+e=lloHe+Hu=llo-Hew+y not -qHillo+x=HelloHe-w+Hulloy 251 {"qHilloHelloHew", "xHelloHeHulloy", []string{"qHillo", "w", "x", "Hulloy", "HelloHe"}}, 252 } { 253 actual := dmp.DiffHalfMatch(tc.Text1, tc.Text2) 254 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) 255 } 256 257 dmp.DiffTimeout = 0 258 259 for i, tc := range []TestCase{ 260 // Optimal no halfmatch 261 {"qHilloHelloHew", "xHelloHeHulloy", nil}, 262 } { 263 actual := dmp.DiffHalfMatch(tc.Text1, tc.Text2) 264 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) 265 } 266} 267 268func BenchmarkDiffHalfMatch(b *testing.B) { 269 s1, s2 := speedtestTexts() 270 271 dmp := New() 272 273 b.ResetTimer() 274 275 for i := 0; i < b.N; i++ { 276 dmp.DiffHalfMatch(s1, s2) 277 } 278} 279 280func TestDiffBisectSplit(t *testing.T) { 281 type TestCase struct { 282 Text1 string 283 Text2 string 284 } 285 286 dmp := New() 287 288 for _, tc := range []TestCase{ 289 {"STUV\x05WX\x05YZ\x05[", "WĺĻļ\x05YZ\x05ĽľĿŀZ"}, 290 } { 291 diffs := dmp.diffBisectSplit([]rune(tc.Text1), 292 []rune(tc.Text2), 7, 6, time.Now().Add(time.Hour)) 293 294 for _, d := range diffs { 295 assert.True(t, utf8.ValidString(d.Text)) 296 } 297 298 // TODO define the expected outcome 299 } 300} 301 302func TestDiffLinesToChars(t *testing.T) { 303 type TestCase struct { 304 Text1 string 305 Text2 string 306 307 ExpectedChars1 string 308 ExpectedChars2 string 309 ExpectedLines []string 310 } 311 312 dmp := New() 313 314 for i, tc := range []TestCase{ 315 {"", "alpha\r\nbeta\r\n\r\n\r\n", "", "\u0001\u0002\u0003\u0003", []string{"", "alpha\r\n", "beta\r\n", "\r\n"}}, 316 {"a", "b", "\u0001", "\u0002", []string{"", "a", "b"}}, 317 // Omit final newline. 318 {"alpha\nbeta\nalpha", "", "\u0001\u0002\u0003", "", []string{"", "alpha\n", "beta\n", "alpha"}}, 319 } { 320 actualChars1, actualChars2, actualLines := dmp.DiffLinesToChars(tc.Text1, tc.Text2) 321 assert.Equal(t, tc.ExpectedChars1, actualChars1, fmt.Sprintf("Test case #%d, %#v", i, tc)) 322 assert.Equal(t, tc.ExpectedChars2, actualChars2, fmt.Sprintf("Test case #%d, %#v", i, tc)) 323 assert.Equal(t, tc.ExpectedLines, actualLines, fmt.Sprintf("Test case #%d, %#v", i, tc)) 324 } 325 326 // More than 256 to reveal any 8-bit limitations. 327 n := 300 328 lineList := []string{ 329 "", // Account for the initial empty element of the lines array. 330 } 331 var charList []rune 332 for x := 1; x < n+1; x++ { 333 lineList = append(lineList, strconv.Itoa(x)+"\n") 334 charList = append(charList, rune(x)) 335 } 336 lines := strings.Join(lineList, "") 337 chars := string(charList) 338 assert.Equal(t, n, utf8.RuneCountInString(chars)) 339 340 actualChars1, actualChars2, actualLines := dmp.DiffLinesToChars(lines, "") 341 assert.Equal(t, chars, actualChars1) 342 assert.Equal(t, "", actualChars2) 343 assert.Equal(t, lineList, actualLines) 344} 345 346func TestDiffCharsToLines(t *testing.T) { 347 type TestCase struct { 348 Diffs []Diff 349 Lines []string 350 351 Expected []Diff 352 } 353 354 dmp := New() 355 356 for i, tc := range []TestCase{ 357 { 358 Diffs: []Diff{ 359 {DiffEqual, "\u0001\u0002\u0001"}, 360 {DiffInsert, "\u0002\u0001\u0002"}, 361 }, 362 Lines: []string{"", "alpha\n", "beta\n"}, 363 364 Expected: []Diff{ 365 {DiffEqual, "alpha\nbeta\nalpha\n"}, 366 {DiffInsert, "beta\nalpha\nbeta\n"}, 367 }, 368 }, 369 } { 370 actual := dmp.DiffCharsToLines(tc.Diffs, tc.Lines) 371 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) 372 } 373 374 // More than 256 to reveal any 8-bit limitations. 375 n := 300 376 lineList := []string{ 377 "", // Account for the initial empty element of the lines array. 378 } 379 charList := []rune{} 380 for x := 1; x <= n; x++ { 381 lineList = append(lineList, strconv.Itoa(x)+"\n") 382 charList = append(charList, rune(x)) 383 } 384 assert.Equal(t, n, len(charList)) 385 386 actual := dmp.DiffCharsToLines([]Diff{Diff{DiffDelete, string(charList)}}, lineList) 387 assert.Equal(t, []Diff{Diff{DiffDelete, strings.Join(lineList, "")}}, actual) 388} 389 390func TestDiffCleanupMerge(t *testing.T) { 391 type TestCase struct { 392 Name string 393 394 Diffs []Diff 395 396 Expected []Diff 397 } 398 399 dmp := New() 400 401 for i, tc := range []TestCase{ 402 { 403 "Null case", 404 []Diff{}, 405 []Diff{}, 406 }, 407 { 408 "No Diff case", 409 []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "b"}, Diff{DiffInsert, "c"}}, 410 []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "b"}, Diff{DiffInsert, "c"}}, 411 }, 412 { 413 "Merge equalities", 414 []Diff{Diff{DiffEqual, "a"}, Diff{DiffEqual, "b"}, Diff{DiffEqual, "c"}}, 415 []Diff{Diff{DiffEqual, "abc"}}, 416 }, 417 { 418 "Merge deletions", 419 []Diff{Diff{DiffDelete, "a"}, Diff{DiffDelete, "b"}, Diff{DiffDelete, "c"}}, 420 []Diff{Diff{DiffDelete, "abc"}}, 421 }, 422 { 423 "Merge insertions", 424 []Diff{Diff{DiffInsert, "a"}, Diff{DiffInsert, "b"}, Diff{DiffInsert, "c"}}, 425 []Diff{Diff{DiffInsert, "abc"}}, 426 }, 427 { 428 "Merge interweave", 429 []Diff{Diff{DiffDelete, "a"}, Diff{DiffInsert, "b"}, Diff{DiffDelete, "c"}, Diff{DiffInsert, "d"}, Diff{DiffEqual, "e"}, Diff{DiffEqual, "f"}}, 430 []Diff{Diff{DiffDelete, "ac"}, Diff{DiffInsert, "bd"}, Diff{DiffEqual, "ef"}}, 431 }, 432 { 433 "Prefix and suffix detection", 434 []Diff{Diff{DiffDelete, "a"}, Diff{DiffInsert, "abc"}, Diff{DiffDelete, "dc"}}, 435 []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "d"}, Diff{DiffInsert, "b"}, Diff{DiffEqual, "c"}}, 436 }, 437 { 438 "Prefix and suffix detection with equalities", 439 []Diff{Diff{DiffEqual, "x"}, Diff{DiffDelete, "a"}, Diff{DiffInsert, "abc"}, Diff{DiffDelete, "dc"}, Diff{DiffEqual, "y"}}, 440 []Diff{Diff{DiffEqual, "xa"}, Diff{DiffDelete, "d"}, Diff{DiffInsert, "b"}, Diff{DiffEqual, "cy"}}, 441 }, 442 { 443 "Same test as above but with unicode (\u0101 will appear in diffs with at least 257 unique lines)", 444 []Diff{Diff{DiffEqual, "x"}, Diff{DiffDelete, "\u0101"}, Diff{DiffInsert, "\u0101bc"}, Diff{DiffDelete, "dc"}, Diff{DiffEqual, "y"}}, 445 []Diff{Diff{DiffEqual, "x\u0101"}, Diff{DiffDelete, "d"}, Diff{DiffInsert, "b"}, Diff{DiffEqual, "cy"}}, 446 }, 447 { 448 "Slide edit left", 449 []Diff{Diff{DiffEqual, "a"}, Diff{DiffInsert, "ba"}, Diff{DiffEqual, "c"}}, 450 []Diff{Diff{DiffInsert, "ab"}, Diff{DiffEqual, "ac"}}, 451 }, 452 { 453 "Slide edit right", 454 []Diff{Diff{DiffEqual, "c"}, Diff{DiffInsert, "ab"}, Diff{DiffEqual, "a"}}, 455 []Diff{Diff{DiffEqual, "ca"}, Diff{DiffInsert, "ba"}}, 456 }, 457 { 458 "Slide edit left recursive", 459 []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "b"}, Diff{DiffEqual, "c"}, Diff{DiffDelete, "ac"}, Diff{DiffEqual, "x"}}, 460 []Diff{Diff{DiffDelete, "abc"}, Diff{DiffEqual, "acx"}}, 461 }, 462 { 463 "Slide edit right recursive", 464 []Diff{Diff{DiffEqual, "x"}, Diff{DiffDelete, "ca"}, Diff{DiffEqual, "c"}, Diff{DiffDelete, "b"}, Diff{DiffEqual, "a"}}, 465 []Diff{Diff{DiffEqual, "xca"}, Diff{DiffDelete, "cba"}}, 466 }, 467 } { 468 actual := dmp.DiffCleanupMerge(tc.Diffs) 469 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) 470 } 471} 472 473func TestDiffCleanupSemanticLossless(t *testing.T) { 474 type TestCase struct { 475 Name string 476 477 Diffs []Diff 478 479 Expected []Diff 480 } 481 482 dmp := New() 483 484 for i, tc := range []TestCase{ 485 { 486 "Null case", 487 []Diff{}, 488 []Diff{}, 489 }, 490 { 491 "Blank lines", 492 []Diff{ 493 Diff{DiffEqual, "AAA\r\n\r\nBBB"}, 494 Diff{DiffInsert, "\r\nDDD\r\n\r\nBBB"}, 495 Diff{DiffEqual, "\r\nEEE"}, 496 }, 497 []Diff{ 498 Diff{DiffEqual, "AAA\r\n\r\n"}, 499 Diff{DiffInsert, "BBB\r\nDDD\r\n\r\n"}, 500 Diff{DiffEqual, "BBB\r\nEEE"}, 501 }, 502 }, 503 { 504 "Line boundaries", 505 []Diff{ 506 Diff{DiffEqual, "AAA\r\nBBB"}, 507 Diff{DiffInsert, " DDD\r\nBBB"}, 508 Diff{DiffEqual, " EEE"}, 509 }, 510 []Diff{ 511 Diff{DiffEqual, "AAA\r\n"}, 512 Diff{DiffInsert, "BBB DDD\r\n"}, 513 Diff{DiffEqual, "BBB EEE"}, 514 }, 515 }, 516 { 517 "Word boundaries", 518 []Diff{ 519 Diff{DiffEqual, "The c"}, 520 Diff{DiffInsert, "ow and the c"}, 521 Diff{DiffEqual, "at."}, 522 }, 523 []Diff{ 524 Diff{DiffEqual, "The "}, 525 Diff{DiffInsert, "cow and the "}, 526 Diff{DiffEqual, "cat."}, 527 }, 528 }, 529 { 530 "Alphanumeric boundaries", 531 []Diff{ 532 Diff{DiffEqual, "The-c"}, 533 Diff{DiffInsert, "ow-and-the-c"}, 534 Diff{DiffEqual, "at."}, 535 }, 536 []Diff{ 537 Diff{DiffEqual, "The-"}, 538 Diff{DiffInsert, "cow-and-the-"}, 539 Diff{DiffEqual, "cat."}, 540 }, 541 }, 542 { 543 "Hitting the start", 544 []Diff{ 545 Diff{DiffEqual, "a"}, 546 Diff{DiffDelete, "a"}, 547 Diff{DiffEqual, "ax"}, 548 }, 549 []Diff{ 550 Diff{DiffDelete, "a"}, 551 Diff{DiffEqual, "aax"}, 552 }, 553 }, 554 { 555 "Hitting the end", 556 []Diff{ 557 Diff{DiffEqual, "xa"}, 558 Diff{DiffDelete, "a"}, 559 Diff{DiffEqual, "a"}, 560 }, 561 []Diff{ 562 Diff{DiffEqual, "xaa"}, 563 Diff{DiffDelete, "a"}, 564 }, 565 }, 566 { 567 "Sentence boundaries", 568 []Diff{ 569 Diff{DiffEqual, "The xxx. The "}, 570 Diff{DiffInsert, "zzz. The "}, 571 Diff{DiffEqual, "yyy."}, 572 }, 573 []Diff{ 574 Diff{DiffEqual, "The xxx."}, 575 Diff{DiffInsert, " The zzz."}, 576 Diff{DiffEqual, " The yyy."}, 577 }, 578 }, 579 { 580 "UTF-8 strings", 581 []Diff{ 582 Diff{DiffEqual, "The ♕. The "}, 583 Diff{DiffInsert, "♔. The "}, 584 Diff{DiffEqual, "♖."}, 585 }, 586 []Diff{ 587 Diff{DiffEqual, "The ♕."}, 588 Diff{DiffInsert, " The ♔."}, 589 Diff{DiffEqual, " The ♖."}, 590 }, 591 }, 592 { 593 "Rune boundaries", 594 []Diff{ 595 Diff{DiffEqual, "♕♕"}, 596 Diff{DiffInsert, "♔♔"}, 597 Diff{DiffEqual, "♖♖"}, 598 }, 599 []Diff{ 600 Diff{DiffEqual, "♕♕"}, 601 Diff{DiffInsert, "♔♔"}, 602 Diff{DiffEqual, "♖♖"}, 603 }, 604 }, 605 } { 606 actual := dmp.DiffCleanupSemanticLossless(tc.Diffs) 607 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) 608 } 609} 610 611func TestDiffCleanupSemantic(t *testing.T) { 612 type TestCase struct { 613 Name string 614 615 Diffs []Diff 616 617 Expected []Diff 618 } 619 620 dmp := New() 621 622 for i, tc := range []TestCase{ 623 { 624 "Null case", 625 []Diff{}, 626 []Diff{}, 627 }, 628 { 629 "No elimination #1", 630 []Diff{ 631 {DiffDelete, "ab"}, 632 {DiffInsert, "cd"}, 633 {DiffEqual, "12"}, 634 {DiffDelete, "e"}, 635 }, 636 []Diff{ 637 {DiffDelete, "ab"}, 638 {DiffInsert, "cd"}, 639 {DiffEqual, "12"}, 640 {DiffDelete, "e"}, 641 }, 642 }, 643 { 644 "No elimination #2", 645 []Diff{ 646 {DiffDelete, "abc"}, 647 {DiffInsert, "ABC"}, 648 {DiffEqual, "1234"}, 649 {DiffDelete, "wxyz"}, 650 }, 651 []Diff{ 652 {DiffDelete, "abc"}, 653 {DiffInsert, "ABC"}, 654 {DiffEqual, "1234"}, 655 {DiffDelete, "wxyz"}, 656 }, 657 }, 658 { 659 "No elimination #3", 660 []Diff{ 661 {DiffEqual, "2016-09-01T03:07:1"}, 662 {DiffInsert, "5.15"}, 663 {DiffEqual, "4"}, 664 {DiffDelete, "."}, 665 {DiffEqual, "80"}, 666 {DiffInsert, "0"}, 667 {DiffEqual, "78"}, 668 {DiffDelete, "3074"}, 669 {DiffEqual, "1Z"}, 670 }, 671 []Diff{ 672 {DiffEqual, "2016-09-01T03:07:1"}, 673 {DiffInsert, "5.15"}, 674 {DiffEqual, "4"}, 675 {DiffDelete, "."}, 676 {DiffEqual, "80"}, 677 {DiffInsert, "0"}, 678 {DiffEqual, "78"}, 679 {DiffDelete, "3074"}, 680 {DiffEqual, "1Z"}, 681 }, 682 }, 683 { 684 "Simple elimination", 685 []Diff{ 686 {DiffDelete, "a"}, 687 {DiffEqual, "b"}, 688 {DiffDelete, "c"}, 689 }, 690 []Diff{ 691 {DiffDelete, "abc"}, 692 {DiffInsert, "b"}, 693 }, 694 }, 695 { 696 "Backpass elimination", 697 []Diff{ 698 {DiffDelete, "ab"}, 699 {DiffEqual, "cd"}, 700 {DiffDelete, "e"}, 701 {DiffEqual, "f"}, 702 {DiffInsert, "g"}, 703 }, 704 []Diff{ 705 {DiffDelete, "abcdef"}, 706 {DiffInsert, "cdfg"}, 707 }, 708 }, 709 { 710 "Multiple eliminations", 711 []Diff{ 712 {DiffInsert, "1"}, 713 {DiffEqual, "A"}, 714 {DiffDelete, "B"}, 715 {DiffInsert, "2"}, 716 {DiffEqual, "_"}, 717 {DiffInsert, "1"}, 718 {DiffEqual, "A"}, 719 {DiffDelete, "B"}, 720 {DiffInsert, "2"}, 721 }, 722 []Diff{ 723 {DiffDelete, "AB_AB"}, 724 {DiffInsert, "1A2_1A2"}, 725 }, 726 }, 727 { 728 "Word boundaries", 729 []Diff{ 730 {DiffEqual, "The c"}, 731 {DiffDelete, "ow and the c"}, 732 {DiffEqual, "at."}, 733 }, 734 []Diff{ 735 {DiffEqual, "The "}, 736 {DiffDelete, "cow and the "}, 737 {DiffEqual, "cat."}, 738 }, 739 }, 740 { 741 "No overlap elimination", 742 []Diff{ 743 {DiffDelete, "abcxx"}, 744 {DiffInsert, "xxdef"}, 745 }, 746 []Diff{ 747 {DiffDelete, "abcxx"}, 748 {DiffInsert, "xxdef"}, 749 }, 750 }, 751 { 752 "Overlap elimination", 753 []Diff{ 754 {DiffDelete, "abcxxx"}, 755 {DiffInsert, "xxxdef"}, 756 }, 757 []Diff{ 758 {DiffDelete, "abc"}, 759 {DiffEqual, "xxx"}, 760 {DiffInsert, "def"}, 761 }, 762 }, 763 { 764 "Reverse overlap elimination", 765 []Diff{ 766 {DiffDelete, "xxxabc"}, 767 {DiffInsert, "defxxx"}, 768 }, 769 []Diff{ 770 {DiffInsert, "def"}, 771 {DiffEqual, "xxx"}, 772 {DiffDelete, "abc"}, 773 }, 774 }, 775 { 776 "Two overlap eliminations", 777 []Diff{ 778 {DiffDelete, "abcd1212"}, 779 {DiffInsert, "1212efghi"}, 780 {DiffEqual, "----"}, 781 {DiffDelete, "A3"}, 782 {DiffInsert, "3BC"}, 783 }, 784 []Diff{ 785 {DiffDelete, "abcd"}, 786 {DiffEqual, "1212"}, 787 {DiffInsert, "efghi"}, 788 {DiffEqual, "----"}, 789 {DiffDelete, "A"}, 790 {DiffEqual, "3"}, 791 {DiffInsert, "BC"}, 792 }, 793 }, 794 { 795 "Test case for adapting DiffCleanupSemantic to be equal to the Python version #19", 796 []Diff{ 797 {DiffEqual, "James McCarthy "}, 798 {DiffDelete, "close to "}, 799 {DiffEqual, "sign"}, 800 {DiffDelete, "ing"}, 801 {DiffInsert, "s"}, 802 {DiffEqual, " new "}, 803 {DiffDelete, "E"}, 804 {DiffInsert, "fi"}, 805 {DiffEqual, "ve"}, 806 {DiffInsert, "-yea"}, 807 {DiffEqual, "r"}, 808 {DiffDelete, "ton"}, 809 {DiffEqual, " deal"}, 810 {DiffInsert, " at Everton"}, 811 }, 812 []Diff{ 813 {DiffEqual, "James McCarthy "}, 814 {DiffDelete, "close to "}, 815 {DiffEqual, "sign"}, 816 {DiffDelete, "ing"}, 817 {DiffInsert, "s"}, 818 {DiffEqual, " new "}, 819 {DiffInsert, "five-year deal at "}, 820 {DiffEqual, "Everton"}, 821 {DiffDelete, " deal"}, 822 }, 823 }, 824 } { 825 actual := dmp.DiffCleanupSemantic(tc.Diffs) 826 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) 827 } 828} 829 830func BenchmarkDiffCleanupSemantic(b *testing.B) { 831 s1, s2 := speedtestTexts() 832 833 dmp := New() 834 835 diffs := dmp.DiffMain(s1, s2, false) 836 837 b.ResetTimer() 838 839 for i := 0; i < b.N; i++ { 840 dmp.DiffCleanupSemantic(diffs) 841 } 842} 843 844func TestDiffCleanupEfficiency(t *testing.T) { 845 type TestCase struct { 846 Name string 847 848 Diffs []Diff 849 850 Expected []Diff 851 } 852 853 dmp := New() 854 dmp.DiffEditCost = 4 855 856 for i, tc := range []TestCase{ 857 { 858 "Null case", 859 []Diff{}, 860 []Diff{}, 861 }, 862 { 863 "No elimination", 864 []Diff{ 865 Diff{DiffDelete, "ab"}, 866 Diff{DiffInsert, "12"}, 867 Diff{DiffEqual, "wxyz"}, 868 Diff{DiffDelete, "cd"}, 869 Diff{DiffInsert, "34"}, 870 }, 871 []Diff{ 872 Diff{DiffDelete, "ab"}, 873 Diff{DiffInsert, "12"}, 874 Diff{DiffEqual, "wxyz"}, 875 Diff{DiffDelete, "cd"}, 876 Diff{DiffInsert, "34"}, 877 }, 878 }, 879 { 880 "Four-edit elimination", 881 []Diff{ 882 Diff{DiffDelete, "ab"}, 883 Diff{DiffInsert, "12"}, 884 Diff{DiffEqual, "xyz"}, 885 Diff{DiffDelete, "cd"}, 886 Diff{DiffInsert, "34"}, 887 }, 888 []Diff{ 889 Diff{DiffDelete, "abxyzcd"}, 890 Diff{DiffInsert, "12xyz34"}, 891 }, 892 }, 893 { 894 "Three-edit elimination", 895 []Diff{ 896 Diff{DiffInsert, "12"}, 897 Diff{DiffEqual, "x"}, 898 Diff{DiffDelete, "cd"}, 899 Diff{DiffInsert, "34"}, 900 }, 901 []Diff{ 902 Diff{DiffDelete, "xcd"}, 903 Diff{DiffInsert, "12x34"}, 904 }, 905 }, 906 { 907 "Backpass elimination", 908 []Diff{ 909 Diff{DiffDelete, "ab"}, 910 Diff{DiffInsert, "12"}, 911 Diff{DiffEqual, "xy"}, 912 Diff{DiffInsert, "34"}, 913 Diff{DiffEqual, "z"}, 914 Diff{DiffDelete, "cd"}, 915 Diff{DiffInsert, "56"}, 916 }, 917 []Diff{ 918 Diff{DiffDelete, "abxyzcd"}, 919 Diff{DiffInsert, "12xy34z56"}, 920 }, 921 }, 922 } { 923 actual := dmp.DiffCleanupEfficiency(tc.Diffs) 924 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) 925 } 926 927 dmp.DiffEditCost = 5 928 929 for i, tc := range []TestCase{ 930 { 931 "High cost elimination", 932 []Diff{ 933 Diff{DiffDelete, "ab"}, 934 Diff{DiffInsert, "12"}, 935 Diff{DiffEqual, "wxyz"}, 936 Diff{DiffDelete, "cd"}, 937 Diff{DiffInsert, "34"}, 938 }, 939 []Diff{ 940 Diff{DiffDelete, "abwxyzcd"}, 941 Diff{DiffInsert, "12wxyz34"}, 942 }, 943 }, 944 } { 945 actual := dmp.DiffCleanupEfficiency(tc.Diffs) 946 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) 947 } 948} 949 950func TestDiffPrettyHtml(t *testing.T) { 951 type TestCase struct { 952 Diffs []Diff 953 954 Expected string 955 } 956 957 dmp := New() 958 959 for i, tc := range []TestCase{ 960 { 961 Diffs: []Diff{ 962 {DiffEqual, "a\n"}, 963 {DiffDelete, "<B>b</B>"}, 964 {DiffInsert, "c&d"}, 965 }, 966 967 Expected: "<span>a¶<br></span><del style=\"background:#ffe6e6;\"><B>b</B></del><ins style=\"background:#e6ffe6;\">c&d</ins>", 968 }, 969 } { 970 actual := dmp.DiffPrettyHtml(tc.Diffs) 971 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) 972 } 973} 974 975func TestDiffPrettyText(t *testing.T) { 976 type TestCase struct { 977 Diffs []Diff 978 979 Expected string 980 } 981 982 dmp := New() 983 984 for i, tc := range []TestCase{ 985 { 986 Diffs: []Diff{ 987 {DiffEqual, "a\n"}, 988 {DiffDelete, "<B>b</B>"}, 989 {DiffInsert, "c&d"}, 990 }, 991 992 Expected: "a\n\x1b[31m<B>b</B>\x1b[0m\x1b[32mc&d\x1b[0m", 993 }, 994 } { 995 actual := dmp.DiffPrettyText(tc.Diffs) 996 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) 997 } 998} 999 1000func TestDiffText(t *testing.T) { 1001 type TestCase struct { 1002 Diffs []Diff 1003 1004 ExpectedText1 string 1005 ExpectedText2 string 1006 } 1007 1008 dmp := New() 1009 1010 for i, tc := range []TestCase{ 1011 { 1012 Diffs: []Diff{ 1013 {DiffEqual, "jump"}, 1014 {DiffDelete, "s"}, 1015 {DiffInsert, "ed"}, 1016 {DiffEqual, " over "}, 1017 {DiffDelete, "the"}, 1018 {DiffInsert, "a"}, 1019 {DiffEqual, " lazy"}, 1020 }, 1021 1022 ExpectedText1: "jumps over the lazy", 1023 ExpectedText2: "jumped over a lazy", 1024 }, 1025 } { 1026 actualText1 := dmp.DiffText1(tc.Diffs) 1027 assert.Equal(t, tc.ExpectedText1, actualText1, fmt.Sprintf("Test case #%d, %#v", i, tc)) 1028 1029 actualText2 := dmp.DiffText2(tc.Diffs) 1030 assert.Equal(t, tc.ExpectedText2, actualText2, fmt.Sprintf("Test case #%d, %#v", i, tc)) 1031 } 1032} 1033 1034func TestDiffDelta(t *testing.T) { 1035 type TestCase struct { 1036 Name string 1037 1038 Text string 1039 Delta string 1040 1041 ErrorMessagePrefix string 1042 } 1043 1044 dmp := New() 1045 1046 for i, tc := range []TestCase{ 1047 {"Delta shorter than text", "jumps over the lazyx", "=4\t-1\t+ed\t=6\t-3\t+a\t=5\t+old dog", "Delta length (19) is different from source text length (20)"}, 1048 {"Delta longer than text", "umps over the lazy", "=4\t-1\t+ed\t=6\t-3\t+a\t=5\t+old dog", "Delta length (19) is different from source text length (18)"}, 1049 {"Invalid URL escaping", "", "+%c3%xy", "invalid URL escape \"%xy\""}, 1050 {"Invalid UTF-8 sequence", "", "+%c3xy", "invalid UTF-8 token: \"\\xc3xy\""}, 1051 {"Invalid diff operation", "", "a", "Invalid diff operation in DiffFromDelta: a"}, 1052 {"Invalid diff syntax", "", "-", "strconv.ParseInt: parsing \"\": invalid syntax"}, 1053 {"Negative number in delta", "", "--1", "Negative number in DiffFromDelta: -1"}, 1054 {"Empty case", "", "", ""}, 1055 } { 1056 diffs, err := dmp.DiffFromDelta(tc.Text, tc.Delta) 1057 msg := fmt.Sprintf("Test case #%d, %s", i, tc.Name) 1058 if tc.ErrorMessagePrefix == "" { 1059 assert.Nil(t, err, msg) 1060 assert.Nil(t, diffs, msg) 1061 } else { 1062 e := err.Error() 1063 if strings.HasPrefix(e, tc.ErrorMessagePrefix) { 1064 e = tc.ErrorMessagePrefix 1065 } 1066 assert.Nil(t, diffs, msg) 1067 assert.Equal(t, tc.ErrorMessagePrefix, e, msg) 1068 } 1069 } 1070 1071 // Convert a diff into delta string. 1072 diffs := []Diff{ 1073 Diff{DiffEqual, "jump"}, 1074 Diff{DiffDelete, "s"}, 1075 Diff{DiffInsert, "ed"}, 1076 Diff{DiffEqual, " over "}, 1077 Diff{DiffDelete, "the"}, 1078 Diff{DiffInsert, "a"}, 1079 Diff{DiffEqual, " lazy"}, 1080 Diff{DiffInsert, "old dog"}, 1081 } 1082 text1 := dmp.DiffText1(diffs) 1083 assert.Equal(t, "jumps over the lazy", text1) 1084 1085 delta := dmp.DiffToDelta(diffs) 1086 assert.Equal(t, "=4\t-1\t+ed\t=6\t-3\t+a\t=5\t+old dog", delta) 1087 1088 // Convert delta string into a diff. 1089 deltaDiffs, err := dmp.DiffFromDelta(text1, delta) 1090 assert.Equal(t, diffs, deltaDiffs) 1091 1092 // Test deltas with special characters. 1093 diffs = []Diff{ 1094 Diff{DiffEqual, "\u0680 \x00 \t %"}, 1095 Diff{DiffDelete, "\u0681 \x01 \n ^"}, 1096 Diff{DiffInsert, "\u0682 \x02 \\ |"}, 1097 } 1098 text1 = dmp.DiffText1(diffs) 1099 assert.Equal(t, "\u0680 \x00 \t %\u0681 \x01 \n ^", text1) 1100 1101 // Lowercase, due to UrlEncode uses lower. 1102 delta = dmp.DiffToDelta(diffs) 1103 assert.Equal(t, "=7\t-7\t+%DA%82 %02 %5C %7C", delta) 1104 1105 deltaDiffs, err = dmp.DiffFromDelta(text1, delta) 1106 assert.Equal(t, diffs, deltaDiffs) 1107 assert.Nil(t, err) 1108 1109 // Verify pool of unchanged characters. 1110 diffs = []Diff{ 1111 Diff{DiffInsert, "A-Z a-z 0-9 - _ . ! ~ * ' ( ) ; / ? : @ & = + $ , # "}, 1112 } 1113 1114 delta = dmp.DiffToDelta(diffs) 1115 assert.Equal(t, "+A-Z a-z 0-9 - _ . ! ~ * ' ( ) ; / ? : @ & = + $ , # ", delta, "Unchanged characters.") 1116 1117 // Convert delta string into a diff. 1118 deltaDiffs, err = dmp.DiffFromDelta("", delta) 1119 assert.Equal(t, diffs, deltaDiffs) 1120 assert.Nil(t, err) 1121} 1122 1123func TestDiffXIndex(t *testing.T) { 1124 type TestCase struct { 1125 Name string 1126 1127 Diffs []Diff 1128 Location int 1129 1130 Expected int 1131 } 1132 1133 dmp := New() 1134 1135 for i, tc := range []TestCase{ 1136 {"Translation on equality", []Diff{{DiffDelete, "a"}, {DiffInsert, "1234"}, {DiffEqual, "xyz"}}, 2, 5}, 1137 {"Translation on deletion", []Diff{{DiffEqual, "a"}, {DiffDelete, "1234"}, {DiffEqual, "xyz"}}, 3, 1}, 1138 } { 1139 actual := dmp.DiffXIndex(tc.Diffs, tc.Location) 1140 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) 1141 } 1142} 1143 1144func TestDiffLevenshtein(t *testing.T) { 1145 type TestCase struct { 1146 Name string 1147 1148 Diffs []Diff 1149 1150 Expected int 1151 } 1152 1153 dmp := New() 1154 1155 for i, tc := range []TestCase{ 1156 {"Levenshtein with trailing equality", []Diff{{DiffDelete, "абв"}, {DiffInsert, "1234"}, {DiffEqual, "эюя"}}, 4}, 1157 {"Levenshtein with leading equality", []Diff{{DiffEqual, "эюя"}, {DiffDelete, "абв"}, {DiffInsert, "1234"}}, 4}, 1158 {"Levenshtein with middle equality", []Diff{{DiffDelete, "абв"}, {DiffEqual, "эюя"}, {DiffInsert, "1234"}}, 7}, 1159 } { 1160 actual := dmp.DiffLevenshtein(tc.Diffs) 1161 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) 1162 } 1163} 1164 1165func TestDiffBisect(t *testing.T) { 1166 type TestCase struct { 1167 Name string 1168 1169 Time time.Time 1170 1171 Expected []Diff 1172 } 1173 1174 dmp := New() 1175 1176 for i, tc := range []TestCase{ 1177 { 1178 Name: "normal", 1179 Time: time.Date(9999, time.December, 31, 23, 59, 59, 59, time.UTC), 1180 1181 Expected: []Diff{ 1182 {DiffDelete, "c"}, 1183 {DiffInsert, "m"}, 1184 {DiffEqual, "a"}, 1185 {DiffDelete, "t"}, 1186 {DiffInsert, "p"}, 1187 }, 1188 }, 1189 { 1190 Name: "Negative deadlines count as having infinite time", 1191 Time: time.Date(0001, time.January, 01, 00, 00, 00, 00, time.UTC), 1192 1193 Expected: []Diff{ 1194 {DiffDelete, "c"}, 1195 {DiffInsert, "m"}, 1196 {DiffEqual, "a"}, 1197 {DiffDelete, "t"}, 1198 {DiffInsert, "p"}, 1199 }, 1200 }, 1201 { 1202 Name: "Timeout", 1203 Time: time.Now().Add(time.Nanosecond), 1204 1205 Expected: []Diff{ 1206 {DiffDelete, "cat"}, 1207 {DiffInsert, "map"}, 1208 }, 1209 }, 1210 } { 1211 actual := dmp.DiffBisect("cat", "map", tc.Time) 1212 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %s", i, tc.Name)) 1213 } 1214 1215 // Test for invalid UTF-8 sequences 1216 assert.Equal(t, []Diff{ 1217 Diff{DiffEqual, "��"}, 1218 }, dmp.DiffBisect("\xe0\xe5", "\xe0\xe5", time.Now().Add(time.Minute))) 1219} 1220 1221func TestDiffMain(t *testing.T) { 1222 type TestCase struct { 1223 Text1 string 1224 Text2 string 1225 1226 Expected []Diff 1227 } 1228 1229 dmp := New() 1230 1231 // Perform a trivial diff. 1232 for i, tc := range []TestCase{ 1233 { 1234 "", 1235 "", 1236 nil, 1237 }, 1238 { 1239 "abc", 1240 "abc", 1241 []Diff{Diff{DiffEqual, "abc"}}, 1242 }, 1243 { 1244 "abc", 1245 "ab123c", 1246 []Diff{Diff{DiffEqual, "ab"}, Diff{DiffInsert, "123"}, Diff{DiffEqual, "c"}}, 1247 }, 1248 { 1249 "a123bc", 1250 "abc", 1251 []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "123"}, Diff{DiffEqual, "bc"}}, 1252 }, 1253 { 1254 "abc", 1255 "a123b456c", 1256 []Diff{Diff{DiffEqual, "a"}, Diff{DiffInsert, "123"}, Diff{DiffEqual, "b"}, Diff{DiffInsert, "456"}, Diff{DiffEqual, "c"}}, 1257 }, 1258 { 1259 "a123b456c", 1260 "abc", 1261 []Diff{Diff{DiffEqual, "a"}, Diff{DiffDelete, "123"}, Diff{DiffEqual, "b"}, Diff{DiffDelete, "456"}, Diff{DiffEqual, "c"}}, 1262 }, 1263 } { 1264 actual := dmp.DiffMain(tc.Text1, tc.Text2, false) 1265 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) 1266 } 1267 1268 // Perform a real diff and switch off the timeout. 1269 dmp.DiffTimeout = 0 1270 1271 for i, tc := range []TestCase{ 1272 { 1273 "a", 1274 "b", 1275 []Diff{Diff{DiffDelete, "a"}, Diff{DiffInsert, "b"}}, 1276 }, 1277 { 1278 "Apples are a fruit.", 1279 "Bananas are also fruit.", 1280 []Diff{ 1281 Diff{DiffDelete, "Apple"}, 1282 Diff{DiffInsert, "Banana"}, 1283 Diff{DiffEqual, "s are a"}, 1284 Diff{DiffInsert, "lso"}, 1285 Diff{DiffEqual, " fruit."}, 1286 }, 1287 }, 1288 { 1289 "ax\t", 1290 "\u0680x\u0000", 1291 []Diff{ 1292 Diff{DiffDelete, "a"}, 1293 Diff{DiffInsert, "\u0680"}, 1294 Diff{DiffEqual, "x"}, 1295 Diff{DiffDelete, "\t"}, 1296 Diff{DiffInsert, "\u0000"}, 1297 }, 1298 }, 1299 { 1300 "1ayb2", 1301 "abxab", 1302 []Diff{ 1303 Diff{DiffDelete, "1"}, 1304 Diff{DiffEqual, "a"}, 1305 Diff{DiffDelete, "y"}, 1306 Diff{DiffEqual, "b"}, 1307 Diff{DiffDelete, "2"}, 1308 Diff{DiffInsert, "xab"}, 1309 }, 1310 }, 1311 { 1312 "abcy", 1313 "xaxcxabc", 1314 []Diff{ 1315 Diff{DiffInsert, "xaxcx"}, 1316 Diff{DiffEqual, "abc"}, Diff{DiffDelete, "y"}, 1317 }, 1318 }, 1319 { 1320 "ABCDa=bcd=efghijklmnopqrsEFGHIJKLMNOefg", 1321 "a-bcd-efghijklmnopqrs", 1322 []Diff{ 1323 Diff{DiffDelete, "ABCD"}, 1324 Diff{DiffEqual, "a"}, 1325 Diff{DiffDelete, "="}, 1326 Diff{DiffInsert, "-"}, 1327 Diff{DiffEqual, "bcd"}, 1328 Diff{DiffDelete, "="}, 1329 Diff{DiffInsert, "-"}, 1330 Diff{DiffEqual, "efghijklmnopqrs"}, 1331 Diff{DiffDelete, "EFGHIJKLMNOefg"}, 1332 }, 1333 }, 1334 { 1335 "a [[Pennsylvania]] and [[New", 1336 " and [[Pennsylvania]]", 1337 []Diff{ 1338 Diff{DiffInsert, " "}, 1339 Diff{DiffEqual, "a"}, 1340 Diff{DiffInsert, "nd"}, 1341 Diff{DiffEqual, " [[Pennsylvania]]"}, 1342 Diff{DiffDelete, " and [[New"}, 1343 }, 1344 }, 1345 } { 1346 actual := dmp.DiffMain(tc.Text1, tc.Text2, false) 1347 assert.Equal(t, tc.Expected, actual, fmt.Sprintf("Test case #%d, %#v", i, tc)) 1348 } 1349 1350 // Test for invalid UTF-8 sequences 1351 assert.Equal(t, []Diff{ 1352 Diff{DiffDelete, "��"}, 1353 }, dmp.DiffMain("\xe0\xe5", "", false)) 1354} 1355 1356func TestDiffMainWithTimeout(t *testing.T) { 1357 dmp := New() 1358 dmp.DiffTimeout = 200 * time.Millisecond 1359 1360 a := "`Twas brillig, and the slithy toves\nDid gyre and gimble in the wabe:\nAll mimsy were the borogoves,\nAnd the mome raths outgrabe.\n" 1361 b := "I am the very model of a modern major general,\nI've information vegetable, animal, and mineral,\nI know the kings of England, and I quote the fights historical,\nFrom Marathon to Waterloo, in order categorical.\n" 1362 // Increase the text lengths by 1024 times to ensure a timeout. 1363 for x := 0; x < 13; x++ { 1364 a = a + a 1365 b = b + b 1366 } 1367 1368 startTime := time.Now() 1369 dmp.DiffMain(a, b, true) 1370 endTime := time.Now() 1371 1372 delta := endTime.Sub(startTime) 1373 1374 // Test that we took at least the timeout period. 1375 assert.True(t, delta >= dmp.DiffTimeout, fmt.Sprintf("%v !>= %v", delta, dmp.DiffTimeout)) 1376 1377 // Test that we didn't take forever (be very forgiving). Theoretically this test could fail very occasionally if the OS task swaps or locks up for a second at the wrong moment. 1378 assert.True(t, delta < (dmp.DiffTimeout*100), fmt.Sprintf("%v !< %v", delta, dmp.DiffTimeout*100)) 1379} 1380 1381func TestDiffMainWithCheckLines(t *testing.T) { 1382 type TestCase struct { 1383 Text1 string 1384 Text2 string 1385 } 1386 1387 dmp := New() 1388 dmp.DiffTimeout = 0 1389 1390 // Test cases must be at least 100 chars long to pass the cutoff. 1391 for i, tc := range []TestCase{ 1392 { 1393 "1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n", 1394 "abcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\n", 1395 }, 1396 { 1397 "1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890", 1398 "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghij", 1399 }, 1400 { 1401 "1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n", 1402 "abcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n", 1403 }, 1404 } { 1405 resultWithoutCheckLines := dmp.DiffMain(tc.Text1, tc.Text2, false) 1406 resultWithCheckLines := dmp.DiffMain(tc.Text1, tc.Text2, true) 1407 1408 // TODO this fails for the third test case, why? 1409 if i != 2 { 1410 assert.Equal(t, resultWithoutCheckLines, resultWithCheckLines, fmt.Sprintf("Test case #%d, %#v", i, tc)) 1411 } 1412 assert.Equal(t, diffRebuildTexts(resultWithoutCheckLines), diffRebuildTexts(resultWithCheckLines), fmt.Sprintf("Test case #%d, %#v", i, tc)) 1413 } 1414} 1415 1416func BenchmarkDiffMain(bench *testing.B) { 1417 s1 := "`Twas brillig, and the slithy toves\nDid gyre and gimble in the wabe:\nAll mimsy were the borogoves,\nAnd the mome raths outgrabe.\n" 1418 s2 := "I am the very model of a modern major general,\nI've information vegetable, animal, and mineral,\nI know the kings of England, and I quote the fights historical,\nFrom Marathon to Waterloo, in order categorical.\n" 1419 1420 // Increase the text lengths by 1024 times to ensure a timeout. 1421 for x := 0; x < 10; x++ { 1422 s1 = s1 + s1 1423 s2 = s2 + s2 1424 } 1425 1426 dmp := New() 1427 dmp.DiffTimeout = time.Second 1428 1429 bench.ResetTimer() 1430 1431 for i := 0; i < bench.N; i++ { 1432 dmp.DiffMain(s1, s2, true) 1433 } 1434} 1435 1436func BenchmarkDiffMainLarge(b *testing.B) { 1437 s1, s2 := speedtestTexts() 1438 1439 dmp := New() 1440 1441 b.ResetTimer() 1442 1443 for i := 0; i < b.N; i++ { 1444 dmp.DiffMain(s1, s2, true) 1445 } 1446} 1447 1448func BenchmarkDiffMainRunesLargeLines(b *testing.B) { 1449 s1, s2 := speedtestTexts() 1450 1451 dmp := New() 1452 1453 b.ResetTimer() 1454 1455 for i := 0; i < b.N; i++ { 1456 text1, text2, linearray := dmp.DiffLinesToRunes(s1, s2) 1457 1458 diffs := dmp.DiffMainRunes(text1, text2, false) 1459 diffs = dmp.DiffCharsToLines(diffs, linearray) 1460 } 1461} 1462