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