libgo/go/bytes/bytes_test.go

   1 // Copyright 2009 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.
   4
   5 package bytes_test
   6
   7 import (
   8         . "bytes"
   9         "fmt"
  10         "internal/testenv"
  11         "math/rand"
  12         "reflect"
  13         "runtime"
  14         "strings"
  15         "testing"
  16         "unicode"
  17         "unicode/utf8"
  18 )
  19
  20 func eq(a, b []string) bool {
  21         if len(a) != len(b) {
  22                 return false
  23         }
  24         for i := 0; i < len(a); i++ {
  25                 if a[i] != b[i] {
  26                         return false
  27                 }
  28         }
  29         return true
  30 }
  31
  32 func sliceOfString(s [][]byte) []string {
  33         result := make([]string, len(s))
  34         for i, v := range s {
  35                 result[i] = string(v)
  36         }
  37         return result
  38 }
  39
  40 // For ease of reading, the test cases use strings that are converted to byte
  41 // slices before invoking the functions.
  42
  43 var abcd = "abcd"
  44 var faces = "☺☻☹"
  45 var commas = "1,2,3,4"
  46 var dots = "1....2....3....4"
  47
  48 type BinOpTest struct {
  49         a string
  50         b string
  51         i int
  52 }
  53
  54 func TestEqual(t *testing.T) {
  55         // Run the tests and check for allocation at the same time.
  56         allocs := testing.AllocsPerRun(10, func() {
  57                 for _, tt := range compareTests {
  58                         eql := Equal(tt.a, tt.b)
  59                         if eql != (tt.i == 0) {
  60                                 t.Errorf(`Equal(%q, %q) = %v`, tt.a, tt.b, eql)
  61                         }
  62                 }
  63         })
  64         if allocs > 0 {
  65                 t.Errorf("Equal allocated %v times", allocs)
  66         }
  67 }
  68
  69 func TestEqualExhaustive(t *testing.T) {
  70         var size = 128
  71         if testing.Short() {
  72                 size = 32
  73         }
  74         a := make([]byte, size)
  75         b := make([]byte, size)
  76         b_init := make([]byte, size)
  77         // randomish but deterministic data
  78         for i := 0; i < size; i++ {
  79                 a[i] = byte(17 * i)
  80                 b_init[i] = byte(23*i + 100)
  81         }
  82
  83         for len := 0; len <= size; len++ {
  84                 for x := 0; x <= size-len; x++ {
  85                         for y := 0; y <= size-len; y++ {
  86                                 copy(b, b_init)
  87                                 copy(b[y:y+len], a[x:x+len])
  88                                 if !Equal(a[x:x+len], b[y:y+len]) || !Equal(b[y:y+len], a[x:x+len]) {
  89                                         t.Errorf("Equal(%d, %d, %d) = false", len, x, y)
  90                                 }
  91                         }
  92                 }
  93         }
  94 }
  95
  96 // make sure Equal returns false for minimally different strings. The data
  97 // is all zeros except for a single one in one location.
  98 func TestNotEqual(t *testing.T) {
  99         var size = 128
 100         if testing.Short() {
 101                 size = 32
 102         }
 103         a := make([]byte, size)
 104         b := make([]byte, size)
 105
 106         for len := 0; len <= size; len++ {
 107                 for x := 0; x <= size-len; x++ {
 108                         for y := 0; y <= size-len; y++ {
 109                                 for diffpos := x; diffpos < x+len; diffpos++ {
 110                                         a[diffpos] = 1
 111                                         if Equal(a[x:x+len], b[y:y+len]) || Equal(b[y:y+len], a[x:x+len]) {
 112                                                 t.Errorf("NotEqual(%d, %d, %d, %d) = true", len, x, y, diffpos)
 113                                         }
 114                                         a[diffpos] = 0
 115                                 }
 116                         }
 117                 }
 118         }
 119 }
 120
 121 var indexTests = []BinOpTest{
 122         {"", "", 0},
 123         {"", "a", -1},
 124         {"", "foo", -1},
 125         {"fo", "foo", -1},
 126         {"foo", "baz", -1},
 127         {"foo", "foo", 0},
 128         {"oofofoofooo", "f", 2},
 129         {"oofofoofooo", "foo", 4},
 130         {"barfoobarfoo", "foo", 3},
 131         {"foo", "", 0},
 132         {"foo", "o", 1},
 133         {"abcABCabc", "A", 3},
 134         // cases with one byte strings - test IndexByte and special case in Index()
 135         {"", "a", -1},
 136         {"x", "a", -1},
 137         {"x", "x", 0},
 138         {"abc", "a", 0},
 139         {"abc", "b", 1},
 140         {"abc", "c", 2},
 141         {"abc", "x", -1},
 142         {"barfoobarfooyyyzzzyyyzzzyyyzzzyyyxxxzzzyyy", "x", 33},
 143         {"foofyfoobarfoobar", "y", 4},
 144         {"oooooooooooooooooooooo", "r", -1},
 145         {"oxoxoxoxoxoxoxoxoxoxoxoy", "oy", 22},
 146         {"oxoxoxoxoxoxoxoxoxoxoxox", "oy", -1},
 147         // test fallback to Rabin-Karp.
 148         {"000000000000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000000001", 5},
 149 }
 150
 151 var lastIndexTests = []BinOpTest{
 152         {"", "", 0},
 153         {"", "a", -1},
 154         {"", "foo", -1},
 155         {"fo", "foo", -1},
 156         {"foo", "foo", 0},
 157         {"foo", "f", 0},
 158         {"oofofoofooo", "f", 7},
 159         {"oofofoofooo", "foo", 7},
 160         {"barfoobarfoo", "foo", 9},
 161         {"foo", "", 3},
 162         {"foo", "o", 2},
 163         {"abcABCabc", "A", 3},
 164         {"abcABCabc", "a", 6},
 165 }
 166
 167 var indexAnyTests = []BinOpTest{
 168         {"", "", -1},
 169         {"", "a", -1},
 170         {"", "abc", -1},
 171         {"a", "", -1},
 172         {"a", "a", 0},
 173         {"\x80", "\xffb", 0},
 174         {"aaa", "a", 0},
 175         {"abc", "xyz", -1},
 176         {"abc", "xcz", 2},
 177         {"ab☺c", "x☺yz", 2},
 178         {"a☺b☻c☹d", "cx", len("a☺b☻")},
 179         {"a☺b☻c☹d", "uvw☻xyz", len("a☺b")},
 180         {"aRegExp*", ".(|)*+?^$[]", 7},
 181         {dots + dots + dots, " ", -1},
 182         {"012abcba210", "\xffb", 4},
 183         {"012\x80bcb\x80210", "\xffb", 3},
 184         {"0123456\xcf\x80abc", "\xcfb\x80", 10},
 185 }
 186
 187 var lastIndexAnyTests = []BinOpTest{
 188         {"", "", -1},
 189         {"", "a", -1},
 190         {"", "abc", -1},
 191         {"a", "", -1},
 192         {"a", "a", 0},
 193         {"\x80", "\xffb", 0},
 194         {"aaa", "a", 2},
 195         {"abc", "xyz", -1},
 196         {"abc", "ab", 1},
 197         {"ab☺c", "x☺yz", 2},
 198         {"a☺b☻c☹d", "cx", len("a☺b☻")},
 199         {"a☺b☻c☹d", "uvw☻xyz", len("a☺b")},
 200         {"a.RegExp*", ".(|)*+?^$[]", 8},
 201         {dots + dots + dots, " ", -1},
 202         {"012abcba210", "\xffb", 6},
 203         {"012\x80bcb\x80210", "\xffb", 7},
 204         {"0123456\xcf\x80abc", "\xcfb\x80", 10},
 205 }
 206
 207 // Execute f on each test case.  funcName should be the name of f; it's used
 208 // in failure reports.
 209 func runIndexTests(t *testing.T, f func(s, sep []byte) int, funcName string, testCases []BinOpTest) {
 210         for _, test := range testCases {
 211                 a := []byte(test.a)
 212                 b := []byte(test.b)
 213                 actual := f(a, b)
 214                 if actual != test.i {
 215                         t.Errorf("%s(%q,%q) = %v; want %v", funcName, a, b, actual, test.i)
 216                 }
 217         }
 218         var allocTests = []struct {
 219                 a []byte
 220                 b []byte
 221                 i int
 222         }{
 223                 // case for function Index.
 224                 {[]byte("000000000000000000000000000000000000000000000000000000000000000000000001"), []byte("0000000000000000000000000000000000000000000000000000000000000000001"), 5},
 225                 // case for function LastIndex.
 226                 {[]byte("000000000000000000000000000000000000000000000000000000000000000010000"), []byte("00000000000000000000000000000000000000000000000000000000000001"), 3},
 227         }
 228         allocs := testing.AllocsPerRun(100, func() {
 229                 if i := Index(allocTests[1].a, allocTests[1].b); i != allocTests[1].i {
 230                         t.Errorf("Index([]byte(%q), []byte(%q)) = %v; want %v", allocTests[1].a, allocTests[1].b, i, allocTests[1].i)
 231                 }
 232                 if i := LastIndex(allocTests[0].a, allocTests[0].b); i != allocTests[0].i {
 233                         t.Errorf("LastIndex([]byte(%q), []byte(%q)) = %v; want %v", allocTests[0].a, allocTests[0].b, i, allocTests[0].i)
 234                 }
 235         })
 236         if allocs != 0 {
 237                 t.Errorf("expected no allocations, got %f", allocs)
 238         }
 239 }
 240
 241 func runIndexAnyTests(t *testing.T, f func(s []byte, chars string) int, funcName string, testCases []BinOpTest) {
 242         for _, test := range testCases {
 243                 a := []byte(test.a)
 244                 actual := f(a, test.b)
 245                 if actual != test.i {
 246                         t.Errorf("%s(%q,%q) = %v; want %v", funcName, a, test.b, actual, test.i)
 247                 }
 248         }
 249 }
 250
 251 func TestIndex(t *testing.T)     { runIndexTests(t, Index, "Index", indexTests) }
 252 func TestLastIndex(t *testing.T) { runIndexTests(t, LastIndex, "LastIndex", lastIndexTests) }
 253 func TestIndexAny(t *testing.T)  { runIndexAnyTests(t, IndexAny, "IndexAny", indexAnyTests) }
 254 func TestLastIndexAny(t *testing.T) {
 255         runIndexAnyTests(t, LastIndexAny, "LastIndexAny", lastIndexAnyTests)
 256 }
 257
 258 func TestIndexByte(t *testing.T) {
 259         for _, tt := range indexTests {
 260                 if len(tt.b) != 1 {
 261                         continue
 262                 }
 263                 a := []byte(tt.a)
 264                 b := tt.b[0]
 265                 pos := IndexByte(a, b)
 266                 if pos != tt.i {
 267                         t.Errorf(`IndexByte(%q, '%c') = %v`, tt.a, b, pos)
 268                 }
 269                 posp := IndexBytePortable(a, b)
 270                 if posp != tt.i {
 271                         t.Errorf(`indexBytePortable(%q, '%c') = %v`, tt.a, b, posp)
 272                 }
 273         }
 274 }
 275
 276 func TestLastIndexByte(t *testing.T) {
 277         testCases := []BinOpTest{
 278                 {"", "q", -1},
 279                 {"abcdef", "q", -1},
 280                 {"abcdefabcdef", "a", len("abcdef")},      // something in the middle
 281                 {"abcdefabcdef", "f", len("abcdefabcde")}, // last byte
 282                 {"zabcdefabcdef", "z", 0},                 // first byte
 283                 {"a☺b☻c☹d", "b", len("a☺")},               // non-ascii
 284         }
 285         for _, test := range testCases {
 286                 actual := LastIndexByte([]byte(test.a), test.b[0])
 287                 if actual != test.i {
 288                         t.Errorf("LastIndexByte(%q,%c) = %v; want %v", test.a, test.b[0], actual, test.i)
 289                 }
 290         }
 291 }
 292
 293 // test a larger buffer with different sizes and alignments
 294 func TestIndexByteBig(t *testing.T) {
 295         var n = 1024
 296         if testing.Short() {
 297                 n = 128
 298         }
 299         b := make([]byte, n)
 300         for i := 0; i < n; i++ {
 301                 // different start alignments
 302                 b1 := b[i:]
 303                 for j := 0; j < len(b1); j++ {
 304                         b1[j] = 'x'
 305                         pos := IndexByte(b1, 'x')
 306                         if pos != j {
 307                                 t.Errorf("IndexByte(%q, 'x') = %v", b1, pos)
 308                         }
 309                         b1[j] = 0
 310                         pos = IndexByte(b1, 'x')
 311                         if pos != -1 {
 312                                 t.Errorf("IndexByte(%q, 'x') = %v", b1, pos)
 313                         }
 314                 }
 315                 // different end alignments
 316                 b1 = b[:i]
 317                 for j := 0; j < len(b1); j++ {
 318                         b1[j] = 'x'
 319                         pos := IndexByte(b1, 'x')
 320                         if pos != j {
 321                                 t.Errorf("IndexByte(%q, 'x') = %v", b1, pos)
 322                         }
 323                         b1[j] = 0
 324                         pos = IndexByte(b1, 'x')
 325                         if pos != -1 {
 326                                 t.Errorf("IndexByte(%q, 'x') = %v", b1, pos)
 327                         }
 328                 }
 329                 // different start and end alignments
 330                 b1 = b[i/2 : n-(i+1)/2]
 331                 for j := 0; j < len(b1); j++ {
 332                         b1[j] = 'x'
 333                         pos := IndexByte(b1, 'x')
 334                         if pos != j {
 335                                 t.Errorf("IndexByte(%q, 'x') = %v", b1, pos)
 336                         }
 337                         b1[j] = 0
 338                         pos = IndexByte(b1, 'x')
 339                         if pos != -1 {
 340                                 t.Errorf("IndexByte(%q, 'x') = %v", b1, pos)
 341                         }
 342                 }
 343         }
 344 }
 345
 346 // test a small index across all page offsets
 347 func TestIndexByteSmall(t *testing.T) {
 348         b := make([]byte, 5015) // bigger than a page
 349         // Make sure we find the correct byte even when straddling a page.
 350         for i := 0; i <= len(b)-15; i++ {
 351                 for j := 0; j < 15; j++ {
 352                         b[i+j] = byte(100 + j)
 353                 }
 354                 for j := 0; j < 15; j++ {
 355                         p := IndexByte(b[i:i+15], byte(100+j))
 356                         if p != j {
 357                                 t.Errorf("IndexByte(%q, %d) = %d", b[i:i+15], 100+j, p)
 358                         }
 359                 }
 360                 for j := 0; j < 15; j++ {
 361                         b[i+j] = 0
 362                 }
 363         }
 364         // Make sure matches outside the slice never trigger.
 365         for i := 0; i <= len(b)-15; i++ {
 366                 for j := 0; j < 15; j++ {
 367                         b[i+j] = 1
 368                 }
 369                 for j := 0; j < 15; j++ {
 370                         p := IndexByte(b[i:i+15], byte(0))
 371                         if p != -1 {
 372                                 t.Errorf("IndexByte(%q, %d) = %d", b[i:i+15], 0, p)
 373                         }
 374                 }
 375                 for j := 0; j < 15; j++ {
 376                         b[i+j] = 0
 377                 }
 378         }
 379 }
 380
 381 func TestIndexRune(t *testing.T) {
 382         tests := []struct {
 383                 in   string
 384                 rune rune
 385                 want int
 386         }{
 387                 {"", 'a', -1},
 388                 {"", '☺', -1},
 389                 {"foo", '☹', -1},
 390                 {"foo", 'o', 1},
 391                 {"foo☺bar", '☺', 3},
 392                 {"foo☺☻☹bar", '☹', 9},
 393                 {"a A x", 'A', 2},
 394                 {"some_text=some_value", '=', 9},
 395                 {"☺a", 'a', 3},
 396                 {"a☻☺b", '☺', 4},
 397
 398                 // RuneError should match any invalid UTF-8 byte sequence.
 399                 {"�", '�', 0},
 400                 {"\xff", '�', 0},
 401                 {"☻x�", '�', len("☻x")},
 402                 {"☻x\xe2\x98", '�', len("☻x")},
 403                 {"☻x\xe2\x98�", '�', len("☻x")},
 404                 {"☻x\xe2\x98x", '�', len("☻x")},
 405
 406                 // Invalid rune values should never match.
 407                 {"a☺b☻c☹d\xe2\x98�\xff�\xed\xa0\x80", -1, -1},
 408                 {"a☺b☻c☹d\xe2\x98�\xff�\xed\xa0\x80", 0xD800, -1}, // Surrogate pair
 409                 {"a☺b☻c☹d\xe2\x98�\xff�\xed\xa0\x80", utf8.MaxRune + 1, -1},
 410         }
 411         for _, tt := range tests {
 412                 if got := IndexRune([]byte(tt.in), tt.rune); got != tt.want {
 413                         t.Errorf("IndexRune(%q, %d) = %v; want %v", tt.in, tt.rune, got, tt.want)
 414                 }
 415         }
 416
 417         haystack := []byte("test世界")
 418         allocs := testing.AllocsPerRun(1000, func() {
 419                 if i := IndexRune(haystack, 's'); i != 2 {
 420                         t.Fatalf("'s' at %d; want 2", i)
 421                 }
 422                 if i := IndexRune(haystack, '世'); i != 4 {
 423                         t.Fatalf("'世' at %d; want 4", i)
 424                 }
 425         })
 426         if allocs != 0 {
 427                 if runtime.Compiler == "gccgo" {
 428                         t.Log("does not work on gccgo without better escape analysis")
 429                 } else {
 430                         t.Errorf("expected no allocations, got %f", allocs)
 431                 }
 432         }
 433 }
 434
 435 // test count of a single byte across page offsets
 436 func TestCountByte(t *testing.T) {
 437         b := make([]byte, 5015) // bigger than a page
 438         windows := []int{1, 2, 3, 4, 15, 16, 17, 31, 32, 33, 63, 64, 65, 128}
 439         testCountWindow := func(i, window int) {
 440                 for j := 0; j < window; j++ {
 441                         b[i+j] = byte(100)
 442                         p := Count(b[i:i+window], []byte{100})
 443                         if p != j+1 {
 444                                 t.Errorf("TestCountByte.Count(%q, 100) = %d", b[i:i+window], p)
 445                         }
 446                 }
 447         }
 448
 449         maxWnd := windows[len(windows)-1]
 450
 451         for i := 0; i <= 2*maxWnd; i++ {
 452                 for _, window := range windows {
 453                         if window > len(b[i:]) {
 454                                 window = len(b[i:])
 455                         }
 456                         testCountWindow(i, window)
 457                         for j := 0; j < window; j++ {
 458                                 b[i+j] = byte(0)
 459                         }
 460                 }
 461         }
 462         for i := 4096 - (maxWnd + 1); i < len(b); i++ {
 463                 for _, window := range windows {
 464                         if window > len(b[i:]) {
 465                                 window = len(b[i:])
 466                         }
 467                         testCountWindow(i, window)
 468                         for j := 0; j < window; j++ {
 469                                 b[i+j] = byte(0)
 470                         }
 471                 }
 472         }
 473 }
 474
 475 // Make sure we don't count bytes outside our window
 476 func TestCountByteNoMatch(t *testing.T) {
 477         b := make([]byte, 5015)
 478         windows := []int{1, 2, 3, 4, 15, 16, 17, 31, 32, 33, 63, 64, 65, 128}
 479         for i := 0; i <= len(b); i++ {
 480                 for _, window := range windows {
 481                         if window > len(b[i:]) {
 482                                 window = len(b[i:])
 483                         }
 484                         // Fill the window with non-match
 485                         for j := 0; j < window; j++ {
 486                                 b[i+j] = byte(100)
 487                         }
 488                         // Try to find something that doesn't exist
 489                         p := Count(b[i:i+window], []byte{0})
 490                         if p != 0 {
 491                                 t.Errorf("TestCountByteNoMatch(%q, 0) = %d", b[i:i+window], p)
 492                         }
 493                         for j := 0; j < window; j++ {
 494                                 b[i+j] = byte(0)
 495                         }
 496                 }
 497         }
 498 }
 499
 500 var bmbuf []byte
 501
 502 func valName(x int) string {
 503         if s := x >> 20; s<<20 == x {
 504                 return fmt.Sprintf("%dM", s)
 505         }
 506         if s := x >> 10; s<<10 == x {
 507                 return fmt.Sprintf("%dK", s)
 508         }
 509         return fmt.Sprint(x)
 510 }
 511
 512 func benchBytes(b *testing.B, sizes []int, f func(b *testing.B, n int)) {
 513         for _, n := range sizes {
 514                 if isRaceBuilder && n > 4<<10 {
 515                         continue
 516                 }
 517                 b.Run(valName(n), func(b *testing.B) {
 518                         if len(bmbuf) < n {
 519                                 bmbuf = make([]byte, n)
 520                         }
 521                         b.SetBytes(int64(n))
 522                         f(b, n)
 523                 })
 524         }
 525 }
 526
 527 var indexSizes = []int{10, 32, 4 << 10, 4 << 20, 64 << 20}
 528
 529 var isRaceBuilder = strings.HasSuffix(testenv.Builder(), "-race")
 530
 531 func BenchmarkIndexByte(b *testing.B) {
 532         benchBytes(b, indexSizes, bmIndexByte(IndexByte))
 533 }
 534
 535 func BenchmarkIndexBytePortable(b *testing.B) {
 536         benchBytes(b, indexSizes, bmIndexByte(IndexBytePortable))
 537 }
 538
 539 func bmIndexByte(index func([]byte, byte) int) func(b *testing.B, n int) {
 540         return func(b *testing.B, n int) {
 541                 buf := bmbuf[0:n]
 542                 buf[n-1] = 'x'
 543                 for i := 0; i < b.N; i++ {
 544                         j := index(buf, 'x')
 545                         if j != n-1 {
 546                                 b.Fatal("bad index", j)
 547                         }
 548                 }
 549                 buf[n-1] = '\x00'
 550         }
 551 }
 552
 553 func BenchmarkIndexRune(b *testing.B) {
 554         benchBytes(b, indexSizes, bmIndexRune(IndexRune))
 555 }
 556
 557 func BenchmarkIndexRuneASCII(b *testing.B) {
 558         benchBytes(b, indexSizes, bmIndexRuneASCII(IndexRune))
 559 }
 560
 561 func bmIndexRuneASCII(index func([]byte, rune) int) func(b *testing.B, n int) {
 562         return func(b *testing.B, n int) {
 563                 buf := bmbuf[0:n]
 564                 buf[n-1] = 'x'
 565                 for i := 0; i < b.N; i++ {
 566                         j := index(buf, 'x')
 567                         if j != n-1 {
 568                                 b.Fatal("bad index", j)
 569                         }
 570                 }
 571                 buf[n-1] = '\x00'
 572         }
 573 }
 574
 575 func bmIndexRune(index func([]byte, rune) int) func(b *testing.B, n int) {
 576         return func(b *testing.B, n int) {
 577                 buf := bmbuf[0:n]
 578                 utf8.EncodeRune(buf[n-3:], '世')
 579                 for i := 0; i < b.N; i++ {
 580                         j := index(buf, '世')
 581                         if j != n-3 {
 582                                 b.Fatal("bad index", j)
 583                         }
 584                 }
 585                 buf[n-3] = '\x00'
 586                 buf[n-2] = '\x00'
 587                 buf[n-1] = '\x00'
 588         }
 589 }
 590
 591 func BenchmarkEqual(b *testing.B) {
 592         b.Run("0", func(b *testing.B) {
 593                 var buf [4]byte
 594                 buf1 := buf[0:0]
 595                 buf2 := buf[1:1]
 596                 for i := 0; i < b.N; i++ {
 597                         eq := Equal(buf1, buf2)
 598                         if !eq {
 599                                 b.Fatal("bad equal")
 600                         }
 601                 }
 602         })
 603
 604         sizes := []int{1, 6, 9, 15, 16, 20, 32, 4 << 10, 4 << 20, 64 << 20}
 605         benchBytes(b, sizes, bmEqual(Equal))
 606 }
 607
 608 func bmEqual(equal func([]byte, []byte) bool) func(b *testing.B, n int) {
 609         return func(b *testing.B, n int) {
 610                 if len(bmbuf) < 2*n {
 611                         bmbuf = make([]byte, 2*n)
 612                 }
 613                 buf1 := bmbuf[0:n]
 614                 buf2 := bmbuf[n : 2*n]
 615                 buf1[n-1] = 'x'
 616                 buf2[n-1] = 'x'
 617                 for i := 0; i < b.N; i++ {
 618                         eq := equal(buf1, buf2)
 619                         if !eq {
 620                                 b.Fatal("bad equal")
 621                         }
 622                 }
 623                 buf1[n-1] = '\x00'
 624                 buf2[n-1] = '\x00'
 625         }
 626 }
 627
 628 func BenchmarkIndex(b *testing.B) {
 629         benchBytes(b, indexSizes, func(b *testing.B, n int) {
 630                 buf := bmbuf[0:n]
 631                 buf[n-1] = 'x'
 632                 for i := 0; i < b.N; i++ {
 633                         j := Index(buf, buf[n-7:])
 634                         if j != n-7 {
 635                                 b.Fatal("bad index", j)
 636                         }
 637                 }
 638                 buf[n-1] = '\x00'
 639         })
 640 }
 641
 642 func BenchmarkIndexEasy(b *testing.B) {
 643         benchBytes(b, indexSizes, func(b *testing.B, n int) {
 644                 buf := bmbuf[0:n]
 645                 buf[n-1] = 'x'
 646                 buf[n-7] = 'x'
 647                 for i := 0; i < b.N; i++ {
 648                         j := Index(buf, buf[n-7:])
 649                         if j != n-7 {
 650                                 b.Fatal("bad index", j)
 651                         }
 652                 }
 653                 buf[n-1] = '\x00'
 654                 buf[n-7] = '\x00'
 655         })
 656 }
 657
 658 func BenchmarkCount(b *testing.B) {
 659         benchBytes(b, indexSizes, func(b *testing.B, n int) {
 660                 buf := bmbuf[0:n]
 661                 buf[n-1] = 'x'
 662                 for i := 0; i < b.N; i++ {
 663                         j := Count(buf, buf[n-7:])
 664                         if j != 1 {
 665                                 b.Fatal("bad count", j)
 666                         }
 667                 }
 668                 buf[n-1] = '\x00'
 669         })
 670 }
 671
 672 func BenchmarkCountEasy(b *testing.B) {
 673         benchBytes(b, indexSizes, func(b *testing.B, n int) {
 674                 buf := bmbuf[0:n]
 675                 buf[n-1] = 'x'
 676                 buf[n-7] = 'x'
 677                 for i := 0; i < b.N; i++ {
 678                         j := Count(buf, buf[n-7:])
 679                         if j != 1 {
 680                                 b.Fatal("bad count", j)
 681                         }
 682                 }
 683                 buf[n-1] = '\x00'
 684                 buf[n-7] = '\x00'
 685         })
 686 }
 687
 688 func BenchmarkCountSingle(b *testing.B) {
 689         benchBytes(b, indexSizes, func(b *testing.B, n int) {
 690                 buf := bmbuf[0:n]
 691                 step := 8
 692                 for i := 0; i < len(buf); i += step {
 693                         buf[i] = 1
 694                 }
 695                 expect := (len(buf) + (step - 1)) / step
 696                 for i := 0; i < b.N; i++ {
 697                         j := Count(buf, []byte{1})
 698                         if j != expect {
 699                                 b.Fatal("bad count", j, expect)
 700                         }
 701                 }
 702                 for i := 0; i < len(buf); i++ {
 703                         buf[i] = 0
 704                 }
 705         })
 706 }
 707
 708 type SplitTest struct {
 709         s   string
 710         sep string
 711         n   int
 712         a   []string
 713 }
 714
 715 var splittests = []SplitTest{
 716         {"", "", -1, []string{}},
 717         {abcd, "a", 0, nil},
 718         {abcd, "", 2, []string{"a", "bcd"}},
 719         {abcd, "a", -1, []string{"", "bcd"}},
 720         {abcd, "z", -1, []string{"abcd"}},
 721         {abcd, "", -1, []string{"a", "b", "c", "d"}},
 722         {commas, ",", -1, []string{"1", "2", "3", "4"}},
 723         {dots, "...", -1, []string{"1", ".2", ".3", ".4"}},
 724         {faces, "☹", -1, []string{"☺☻", ""}},
 725         {faces, "~", -1, []string{faces}},
 726         {faces, "", -1, []string{"☺", "☻", "☹"}},
 727         {"1 2 3 4", " ", 3, []string{"1", "2", "3 4"}},
 728         {"1 2", " ", 3, []string{"1", "2"}},
 729         {"123", "", 2, []string{"1", "23"}},
 730         {"123", "", 17, []string{"1", "2", "3"}},
 731 }
 732
 733 func TestSplit(t *testing.T) {
 734         for _, tt := range splittests {
 735                 a := SplitN([]byte(tt.s), []byte(tt.sep), tt.n)
 736
 737                 // Appending to the results should not change future results.
 738                 var x []byte
 739                 for _, v := range a {
 740                         x = append(v, 'z')
 741                 }
 742
 743                 result := sliceOfString(a)
 744                 if !eq(result, tt.a) {
 745                         t.Errorf(`Split(%q, %q, %d) = %v; want %v`, tt.s, tt.sep, tt.n, result, tt.a)
 746                         continue
 747                 }
 748                 if tt.n == 0 || len(a) == 0 {
 749                         continue
 750                 }
 751
 752                 if want := tt.a[len(tt.a)-1] + "z"; string(x) != want {
 753                         t.Errorf("last appended result was %s; want %s", x, want)
 754                 }
 755
 756                 s := Join(a, []byte(tt.sep))
 757                 if string(s) != tt.s {
 758                         t.Errorf(`Join(Split(%q, %q, %d), %q) = %q`, tt.s, tt.sep, tt.n, tt.sep, s)
 759                 }
 760                 if tt.n < 0 {
 761                         b := Split([]byte(tt.s), []byte(tt.sep))
 762                         if !reflect.DeepEqual(a, b) {
 763                                 t.Errorf("Split disagrees withSplitN(%q, %q, %d) = %v; want %v", tt.s, tt.sep, tt.n, b, a)
 764                         }
 765                 }
 766                 if len(a) > 0 {
 767                         in, out := a[0], s
 768                         if cap(in) == cap(out) && &in[:1][0] == &out[:1][0] {
 769                                 t.Errorf("Join(%#v, %q) didn't copy", a, tt.sep)
 770                         }
 771                 }
 772         }
 773 }
 774
 775 var splitaftertests = []SplitTest{
 776         {abcd, "a", -1, []string{"a", "bcd"}},
 777         {abcd, "z", -1, []string{"abcd"}},
 778         {abcd, "", -1, []string{"a", "b", "c", "d"}},
 779         {commas, ",", -1, []string{"1,", "2,", "3,", "4"}},
 780         {dots, "...", -1, []string{"1...", ".2...", ".3...", ".4"}},
 781         {faces, "☹", -1, []string{"☺☻☹", ""}},
 782         {faces, "~", -1, []string{faces}},
 783         {faces, "", -1, []string{"☺", "☻", "☹"}},
 784         {"1 2 3 4", " ", 3, []string{"1 ", "2 ", "3 4"}},
 785         {"1 2 3", " ", 3, []string{"1 ", "2 ", "3"}},
 786         {"1 2", " ", 3, []string{"1 ", "2"}},
 787         {"123", "", 2, []string{"1", "23"}},
 788         {"123", "", 17, []string{"1", "2", "3"}},
 789 }
 790
 791 func TestSplitAfter(t *testing.T) {
 792         for _, tt := range splitaftertests {
 793                 a := SplitAfterN([]byte(tt.s), []byte(tt.sep), tt.n)
 794
 795                 // Appending to the results should not change future results.
 796                 var x []byte
 797                 for _, v := range a {
 798                         x = append(v, 'z')
 799                 }
 800
 801                 result := sliceOfString(a)
 802                 if !eq(result, tt.a) {
 803                         t.Errorf(`Split(%q, %q, %d) = %v; want %v`, tt.s, tt.sep, tt.n, result, tt.a)
 804                         continue
 805                 }
 806
 807                 if want := tt.a[len(tt.a)-1] + "z"; string(x) != want {
 808                         t.Errorf("last appended result was %s; want %s", x, want)
 809                 }
 810
 811                 s := Join(a, nil)
 812                 if string(s) != tt.s {
 813                         t.Errorf(`Join(Split(%q, %q, %d), %q) = %q`, tt.s, tt.sep, tt.n, tt.sep, s)
 814                 }
 815                 if tt.n < 0 {
 816                         b := SplitAfter([]byte(tt.s), []byte(tt.sep))
 817                         if !reflect.DeepEqual(a, b) {
 818                                 t.Errorf("SplitAfter disagrees withSplitAfterN(%q, %q, %d) = %v; want %v", tt.s, tt.sep, tt.n, b, a)
 819                         }
 820                 }
 821         }
 822 }
 823
 824 type FieldsTest struct {
 825         s string
 826         a []string
 827 }
 828
 829 var fieldstests = []FieldsTest{
 830         {"", []string{}},
 831         {" ", []string{}},
 832         {" \t ", []string{}},
 833         {"  abc  ", []string{"abc"}},
 834         {"1 2 3 4", []string{"1", "2", "3", "4"}},
 835         {"1  2  3  4", []string{"1", "2", "3", "4"}},
 836         {"1\t\t2\t\t3\t4", []string{"1", "2", "3", "4"}},
 837         {"1\u20002\u20013\u20024", []string{"1", "2", "3", "4"}},
 838         {"\u2000\u2001\u2002", []string{}},
 839         {"\n™\t™\n", []string{"™", "™"}},
 840         {faces, []string{faces}},
 841 }
 842
 843 func TestFields(t *testing.T) {
 844         for _, tt := range fieldstests {
 845                 b := []byte(tt.s)
 846                 a := Fields(b)
 847
 848                 // Appending to the results should not change future results.
 849                 var x []byte
 850                 for _, v := range a {
 851                         x = append(v, 'z')
 852                 }
 853
 854                 result := sliceOfString(a)
 855                 if !eq(result, tt.a) {
 856                         t.Errorf("Fields(%q) = %v; want %v", tt.s, a, tt.a)
 857                         continue
 858                 }
 859
 860                 if string(b) != tt.s {
 861                         t.Errorf("slice changed to %s; want %s", string(b), tt.s)
 862                 }
 863                 if len(tt.a) > 0 {
 864                         if want := tt.a[len(tt.a)-1] + "z"; string(x) != want {
 865                                 t.Errorf("last appended result was %s; want %s", x, want)
 866                         }
 867                 }
 868         }
 869 }
 870
 871 func TestFieldsFunc(t *testing.T) {
 872         for _, tt := range fieldstests {
 873                 a := FieldsFunc([]byte(tt.s), unicode.IsSpace)
 874                 result := sliceOfString(a)
 875                 if !eq(result, tt.a) {
 876                         t.Errorf("FieldsFunc(%q, unicode.IsSpace) = %v; want %v", tt.s, a, tt.a)
 877                         continue
 878                 }
 879         }
 880         pred := func(c rune) bool { return c == 'X' }
 881         var fieldsFuncTests = []FieldsTest{
 882                 {"", []string{}},
 883                 {"XX", []string{}},
 884                 {"XXhiXXX", []string{"hi"}},
 885                 {"aXXbXXXcX", []string{"a", "b", "c"}},
 886         }
 887         for _, tt := range fieldsFuncTests {
 888                 b := []byte(tt.s)
 889                 a := FieldsFunc(b, pred)
 890
 891                 // Appending to the results should not change future results.
 892                 var x []byte
 893                 for _, v := range a {
 894                         x = append(v, 'z')
 895                 }
 896
 897                 result := sliceOfString(a)
 898                 if !eq(result, tt.a) {
 899                         t.Errorf("FieldsFunc(%q) = %v, want %v", tt.s, a, tt.a)
 900                 }
 901
 902                 if string(b) != tt.s {
 903                         t.Errorf("slice changed to %s; want %s", b, tt.s)
 904                 }
 905                 if len(tt.a) > 0 {
 906                         if want := tt.a[len(tt.a)-1] + "z"; string(x) != want {
 907                                 t.Errorf("last appended result was %s; want %s", x, want)
 908                         }
 909                 }
 910         }
 911 }
 912
 913 // Test case for any function which accepts and returns a byte slice.
 914 // For ease of creation, we write the input byte slice as a string.
 915 type StringTest struct {
 916         in  string
 917         out []byte
 918 }
 919
 920 var upperTests = []StringTest{
 921         {"", []byte("")},
 922         {"ONLYUPPER", []byte("ONLYUPPER")},
 923         {"abc", []byte("ABC")},
 924         {"AbC123", []byte("ABC123")},
 925         {"azAZ09_", []byte("AZAZ09_")},
 926         {"longStrinGwitHmixofsmaLLandcAps", []byte("LONGSTRINGWITHMIXOFSMALLANDCAPS")},
 927         {"long\u0250string\u0250with\u0250nonascii\u2C6Fchars", []byte("LONG\u2C6FSTRING\u2C6FWITH\u2C6FNONASCII\u2C6FCHARS")},
 928         {"\u0250\u0250\u0250\u0250\u0250", []byte("\u2C6F\u2C6F\u2C6F\u2C6F\u2C6F")}, // grows one byte per char
 929         {"a\u0080\U0010FFFF", []byte("A\u0080\U0010FFFF")},                           // test utf8.RuneSelf and utf8.MaxRune
 930 }
 931
 932 var lowerTests = []StringTest{
 933         {"", []byte("")},
 934         {"abc", []byte("abc")},
 935         {"AbC123", []byte("abc123")},
 936         {"azAZ09_", []byte("azaz09_")},
 937         {"longStrinGwitHmixofsmaLLandcAps", []byte("longstringwithmixofsmallandcaps")},
 938         {"LONG\u2C6FSTRING\u2C6FWITH\u2C6FNONASCII\u2C6FCHARS", []byte("long\u0250string\u0250with\u0250nonascii\u0250chars")},
 939         {"\u2C6D\u2C6D\u2C6D\u2C6D\u2C6D", []byte("\u0251\u0251\u0251\u0251\u0251")}, // shrinks one byte per char
 940         {"A\u0080\U0010FFFF", []byte("a\u0080\U0010FFFF")},                           // test utf8.RuneSelf and utf8.MaxRune
 941 }
 942
 943 const space = "\t\v\r\f\n\u0085\u00a0\u2000\u3000"
 944
 945 var trimSpaceTests = []StringTest{
 946         {"", nil},
 947         {"  a", []byte("a")},
 948         {"b  ", []byte("b")},
 949         {"abc", []byte("abc")},
 950         {space + "abc" + space, []byte("abc")},
 951         {" ", nil},
 952         {"\u3000 ", nil},
 953         {" \u3000", nil},
 954         {" \t\r\n \t\t\r\r\n\n ", nil},
 955         {" \t\r\n x\t\t\r\r\n\n ", []byte("x")},
 956         {" \u2000\t\r\n x\t\t\r\r\ny\n \u3000", []byte("x\t\t\r\r\ny")},
 957         {"1 \t\r\n2", []byte("1 \t\r\n2")},
 958         {" x\x80", []byte("x\x80")},
 959         {" x\xc0", []byte("x\xc0")},
 960         {"x \xc0\xc0 ", []byte("x \xc0\xc0")},
 961         {"x \xc0", []byte("x \xc0")},
 962         {"x \xc0 ", []byte("x \xc0")},
 963         {"x \xc0\xc0 ", []byte("x \xc0\xc0")},
 964         {"x ☺\xc0\xc0 ", []byte("x ☺\xc0\xc0")},
 965         {"x ☺ ", []byte("x ☺")},
 966 }
 967
 968 // Execute f on each test case.  funcName should be the name of f; it's used
 969 // in failure reports.
 970 func runStringTests(t *testing.T, f func([]byte) []byte, funcName string, testCases []StringTest) {
 971         for _, tc := range testCases {
 972                 actual := f([]byte(tc.in))
 973                 if actual == nil && tc.out != nil {
 974                         t.Errorf("%s(%q) = nil; want %q", funcName, tc.in, tc.out)
 975                 }
 976                 if actual != nil && tc.out == nil {
 977                         t.Errorf("%s(%q) = %q; want nil", funcName, tc.in, actual)
 978                 }
 979                 if !Equal(actual, tc.out) {
 980                         t.Errorf("%s(%q) = %q; want %q", funcName, tc.in, actual, tc.out)
 981                 }
 982         }
 983 }
 984
 985 func tenRunes(r rune) string {
 986         runes := make([]rune, 10)
 987         for i := range runes {
 988                 runes[i] = r
 989         }
 990         return string(runes)
 991 }
 992
 993 // User-defined self-inverse mapping function
 994 func rot13(r rune) rune {
 995         const step = 13
 996         if r >= 'a' && r <= 'z' {
 997                 return ((r - 'a' + step) % 26) + 'a'
 998         }
 999         if r >= 'A' && r <= 'Z' {
1000                 return ((r - 'A' + step) % 26) + 'A'
1001         }
1002         return r
1003 }
1004
1005 func TestMap(t *testing.T) {
1006         // Run a couple of awful growth/shrinkage tests
1007         a := tenRunes('a')
1008
1009         // 1.  Grow. This triggers two reallocations in Map.
1010         maxRune := func(r rune) rune { return unicode.MaxRune }
1011         m := Map(maxRune, []byte(a))
1012         expect := tenRunes(unicode.MaxRune)
1013         if string(m) != expect {
1014                 t.Errorf("growing: expected %q got %q", expect, m)
1015         }
1016
1017         // 2. Shrink
1018         minRune := func(r rune) rune { return 'a' }
1019         m = Map(minRune, []byte(tenRunes(unicode.MaxRune)))
1020         expect = a
1021         if string(m) != expect {
1022                 t.Errorf("shrinking: expected %q got %q", expect, m)
1023         }
1024
1025         // 3. Rot13
1026         m = Map(rot13, []byte("a to zed"))
1027         expect = "n gb mrq"
1028         if string(m) != expect {
1029                 t.Errorf("rot13: expected %q got %q", expect, m)
1030         }
1031
1032         // 4. Rot13^2
1033         m = Map(rot13, Map(rot13, []byte("a to zed")))
1034         expect = "a to zed"
1035         if string(m) != expect {
1036                 t.Errorf("rot13: expected %q got %q", expect, m)
1037         }
1038
1039         // 5. Drop
1040         dropNotLatin := func(r rune) rune {
1041                 if unicode.Is(unicode.Latin, r) {
1042                         return r
1043                 }
1044                 return -1
1045         }
1046         m = Map(dropNotLatin, []byte("Hello, 세계"))
1047         expect = "Hello"
1048         if string(m) != expect {
1049                 t.Errorf("drop: expected %q got %q", expect, m)
1050         }
1051
1052         // 6. Invalid rune
1053         invalidRune := func(r rune) rune {
1054                 return utf8.MaxRune + 1
1055         }
1056         m = Map(invalidRune, []byte("x"))
1057         expect = "\uFFFD"
1058         if string(m) != expect {
1059                 t.Errorf("invalidRune: expected %q got %q", expect, m)
1060         }
1061 }
1062
1063 func TestToUpper(t *testing.T) { runStringTests(t, ToUpper, "ToUpper", upperTests) }
1064
1065 func TestToLower(t *testing.T) { runStringTests(t, ToLower, "ToLower", lowerTests) }
1066
1067 func BenchmarkToUpper(b *testing.B) {
1068         for _, tc := range upperTests {
1069                 tin := []byte(tc.in)
1070                 b.Run(tc.in, func(b *testing.B) {
1071                         for i := 0; i < b.N; i++ {
1072                                 actual := ToUpper(tin)
1073                                 if !Equal(actual, tc.out) {
1074                                         b.Errorf("ToUpper(%q) = %q; want %q", tc.in, actual, tc.out)
1075                                 }
1076                         }
1077                 })
1078         }
1079 }
1080
1081 func BenchmarkToLower(b *testing.B) {
1082         for _, tc := range lowerTests {
1083                 tin := []byte(tc.in)
1084                 b.Run(tc.in, func(b *testing.B) {
1085                         for i := 0; i < b.N; i++ {
1086                                 actual := ToLower(tin)
1087                                 if !Equal(actual, tc.out) {
1088                                         b.Errorf("ToLower(%q) = %q; want %q", tc.in, actual, tc.out)
1089                                 }
1090                         }
1091                 })
1092         }
1093 }
1094
1095 var toValidUTF8Tests = []struct {
1096         in   string
1097         repl string
1098         out  string
1099 }{
1100         {"", "\uFFFD", ""},
1101         {"abc", "\uFFFD", "abc"},
1102         {"\uFDDD", "\uFFFD", "\uFDDD"},
1103         {"a\xffb", "\uFFFD", "a\uFFFDb"},
1104         {"a\xffb\uFFFD", "X", "aXb\uFFFD"},
1105         {"a☺\xffb☺\xC0\xAFc☺\xff", "", "a☺b☺c☺"},
1106         {"a☺\xffb☺\xC0\xAFc☺\xff", "日本語", "a☺日本語b☺日本語c☺日本語"},
1107         {"\xC0\xAF", "\uFFFD", "\uFFFD"},
1108         {"\xE0\x80\xAF", "\uFFFD", "\uFFFD"},
1109         {"\xed\xa0\x80", "abc", "abc"},
1110         {"\xed\xbf\xbf", "\uFFFD", "\uFFFD"},
1111         {"\xF0\x80\x80\xaf", "☺", "☺"},
1112         {"\xF8\x80\x80\x80\xAF", "\uFFFD", "\uFFFD"},
1113         {"\xFC\x80\x80\x80\x80\xAF", "\uFFFD", "\uFFFD"},
1114 }
1115
1116 func TestToValidUTF8(t *testing.T) {
1117         for _, tc := range toValidUTF8Tests {
1118                 got := ToValidUTF8([]byte(tc.in), []byte(tc.repl))
1119                 if !Equal(got, []byte(tc.out)) {
1120                         t.Errorf("ToValidUTF8(%q, %q) = %q; want %q", tc.in, tc.repl, got, tc.out)
1121                 }
1122         }
1123 }
1124
1125 func TestTrimSpace(t *testing.T) { runStringTests(t, TrimSpace, "TrimSpace", trimSpaceTests) }
1126
1127 type RepeatTest struct {
1128         in, out string
1129         count   int
1130 }
1131
1132 var RepeatTests = []RepeatTest{
1133         {"", "", 0},
1134         {"", "", 1},
1135         {"", "", 2},
1136         {"-", "", 0},
1137         {"-", "-", 1},
1138         {"-", "----------", 10},
1139         {"abc ", "abc abc abc ", 3},
1140 }
1141
1142 func TestRepeat(t *testing.T) {
1143         for _, tt := range RepeatTests {
1144                 tin := []byte(tt.in)
1145                 tout := []byte(tt.out)
1146                 a := Repeat(tin, tt.count)
1147                 if !Equal(a, tout) {
1148                         t.Errorf("Repeat(%q, %d) = %q; want %q", tin, tt.count, a, tout)
1149                         continue
1150                 }
1151         }
1152 }
1153
1154 func repeat(b []byte, count int) (err error) {
1155         defer func() {
1156                 if r := recover(); r != nil {
1157                         switch v := r.(type) {
1158                         case error:
1159                                 err = v
1160                         default:
1161                                 err = fmt.Errorf("%s", v)
1162                         }
1163                 }
1164         }()
1165
1166         Repeat(b, count)
1167
1168         return
1169 }
1170
1171 // See Issue golang.org/issue/16237
1172 func TestRepeatCatchesOverflow(t *testing.T) {
1173         tests := [...]struct {
1174                 s      string
1175                 count  int
1176                 errStr string
1177         }{
1178                 0: {"--", -2147483647, "negative"},
1179                 1: {"", int(^uint(0) >> 1), ""},
1180                 2: {"-", 10, ""},
1181                 3: {"gopher", 0, ""},
1182                 4: {"-", -1, "negative"},
1183                 5: {"--", -102, "negative"},
1184                 6: {string(make([]byte, 255)), int((^uint(0))/255 + 1), "overflow"},
1185         }
1186
1187         for i, tt := range tests {
1188                 err := repeat([]byte(tt.s), tt.count)
1189                 if tt.errStr == "" {
1190                         if err != nil {
1191                                 t.Errorf("#%d panicked %v", i, err)
1192                         }
1193                         continue
1194                 }
1195
1196                 if err == nil || !strings.Contains(err.Error(), tt.errStr) {
1197                         t.Errorf("#%d expected %q got %q", i, tt.errStr, err)
1198                 }
1199         }
1200 }
1201
1202 func runesEqual(a, b []rune) bool {
1203         if len(a) != len(b) {
1204                 return false
1205         }
1206         for i, r := range a {
1207                 if r != b[i] {
1208                         return false
1209                 }
1210         }
1211         return true
1212 }
1213
1214 type RunesTest struct {
1215         in    string
1216         out   []rune
1217         lossy bool
1218 }
1219
1220 var RunesTests = []RunesTest{
1221         {"", []rune{}, false},
1222         {" ", []rune{32}, false},
1223         {"ABC", []rune{65, 66, 67}, false},
1224         {"abc", []rune{97, 98, 99}, false},
1225         {"\u65e5\u672c\u8a9e", []rune{26085, 26412, 35486}, false},
1226         {"ab\x80c", []rune{97, 98, 0xFFFD, 99}, true},
1227         {"ab\xc0c", []rune{97, 98, 0xFFFD, 99}, true},
1228 }
1229
1230 func TestRunes(t *testing.T) {
1231         for _, tt := range RunesTests {
1232                 tin := []byte(tt.in)
1233                 a := Runes(tin)
1234                 if !runesEqual(a, tt.out) {
1235                         t.Errorf("Runes(%q) = %v; want %v", tin, a, tt.out)
1236                         continue
1237                 }
1238                 if !tt.lossy {
1239                         // can only test reassembly if we didn't lose information
1240                         s := string(a)
1241                         if s != tt.in {
1242                                 t.Errorf("string(Runes(%q)) = %x; want %x", tin, s, tin)
1243                         }
1244                 }
1245         }
1246 }
1247
1248 type TrimTest struct {
1249         f            string
1250         in, arg, out string
1251 }
1252
1253 var trimTests = []TrimTest{
1254         {"Trim", "abba", "a", "bb"},
1255         {"Trim", "abba", "ab", ""},
1256         {"TrimLeft", "abba", "ab", ""},
1257         {"TrimRight", "abba", "ab", ""},
1258         {"TrimLeft", "abba", "a", "bba"},
1259         {"TrimLeft", "abba", "b", "abba"},
1260         {"TrimRight", "abba", "a", "abb"},
1261         {"TrimRight", "abba", "b", "abba"},
1262         {"Trim", "<tag>", "<>", "tag"},
1263         {"Trim", "* listitem", " *", "listitem"},
1264         {"Trim", `"quote"`, `"`, "quote"},
1265         {"Trim", "\u2C6F\u2C6F\u0250\u0250\u2C6F\u2C6F", "\u2C6F", "\u0250\u0250"},
1266         {"Trim", "\x80test\xff", "\xff", "test"},
1267         {"Trim", " Ġ ", " ", "Ġ"},
1268         {"Trim", " Ġİ0", "0 ", "Ġİ"},
1269         //empty string tests
1270         {"Trim", "abba", "", "abba"},
1271         {"Trim", "", "123", ""},
1272         {"Trim", "", "", ""},
1273         {"TrimLeft", "abba", "", "abba"},
1274         {"TrimLeft", "", "123", ""},
1275         {"TrimLeft", "", "", ""},
1276         {"TrimRight", "abba", "", "abba"},
1277         {"TrimRight", "", "123", ""},
1278         {"TrimRight", "", "", ""},
1279         {"TrimRight", "☺\xc0", "☺", "☺\xc0"},
1280         {"TrimPrefix", "aabb", "a", "abb"},
1281         {"TrimPrefix", "aabb", "b", "aabb"},
1282         {"TrimSuffix", "aabb", "a", "aabb"},
1283         {"TrimSuffix", "aabb", "b", "aab"},
1284 }
1285
1286 func TestTrim(t *testing.T) {
1287         for _, tc := range trimTests {
1288                 name := tc.f
1289                 var f func([]byte, string) []byte
1290                 var fb func([]byte, []byte) []byte
1291                 switch name {
1292                 case "Trim":
1293                         f = Trim
1294                 case "TrimLeft":
1295                         f = TrimLeft
1296                 case "TrimRight":
1297                         f = TrimRight
1298                 case "TrimPrefix":
1299                         fb = TrimPrefix
1300                 case "TrimSuffix":
1301                         fb = TrimSuffix
1302                 default:
1303                         t.Errorf("Undefined trim function %s", name)
1304                 }
1305                 var actual string
1306                 if f != nil {
1307                         actual = string(f([]byte(tc.in), tc.arg))
1308                 } else {
1309                         actual = string(fb([]byte(tc.in), []byte(tc.arg)))
1310                 }
1311                 if actual != tc.out {
1312                         t.Errorf("%s(%q, %q) = %q; want %q", name, tc.in, tc.arg, actual, tc.out)
1313                 }
1314         }
1315 }
1316
1317 type predicate struct {
1318         f    func(r rune) bool
1319         name string
1320 }
1321
1322 var isSpace = predicate{unicode.IsSpace, "IsSpace"}
1323 var isDigit = predicate{unicode.IsDigit, "IsDigit"}
1324 var isUpper = predicate{unicode.IsUpper, "IsUpper"}
1325 var isValidRune = predicate{
1326         func(r rune) bool {
1327                 return r != utf8.RuneError
1328         },
1329         "IsValidRune",
1330 }
1331
1332 type TrimFuncTest struct {
1333         f        predicate
1334         in       string
1335         trimOut  []byte
1336         leftOut  []byte
1337         rightOut []byte
1338 }
1339
1340 func not(p predicate) predicate {
1341         return predicate{
1342                 func(r rune) bool {
1343                         return !p.f(r)
1344                 },
1345                 "not " + p.name,
1346         }
1347 }
1348
1349 var trimFuncTests = []TrimFuncTest{
1350         {isSpace, space + " hello " + space,
1351                 []byte("hello"),
1352                 []byte("hello " + space),
1353                 []byte(space + " hello")},
1354         {isDigit, "\u0e50\u0e5212hello34\u0e50\u0e51",
1355                 []byte("hello"),
1356                 []byte("hello34\u0e50\u0e51"),
1357                 []byte("\u0e50\u0e5212hello")},
1358         {isUpper, "\u2C6F\u2C6F\u2C6F\u2C6FABCDhelloEF\u2C6F\u2C6FGH\u2C6F\u2C6F",
1359                 []byte("hello"),
1360                 []byte("helloEF\u2C6F\u2C6FGH\u2C6F\u2C6F"),
1361                 []byte("\u2C6F\u2C6F\u2C6F\u2C6FABCDhello")},
1362         {not(isSpace), "hello" + space + "hello",
1363                 []byte(space),
1364                 []byte(space + "hello"),
1365                 []byte("hello" + space)},
1366         {not(isDigit), "hello\u0e50\u0e521234\u0e50\u0e51helo",
1367                 []byte("\u0e50\u0e521234\u0e50\u0e51"),
1368                 []byte("\u0e50\u0e521234\u0e50\u0e51helo"),
1369                 []byte("hello\u0e50\u0e521234\u0e50\u0e51")},
1370         {isValidRune, "ab\xc0a\xc0cd",
1371                 []byte("\xc0a\xc0"),
1372                 []byte("\xc0a\xc0cd"),
1373                 []byte("ab\xc0a\xc0")},
1374         {not(isValidRune), "\xc0a\xc0",
1375                 []byte("a"),
1376                 []byte("a\xc0"),
1377                 []byte("\xc0a")},
1378         // The nils returned by TrimLeftFunc are odd behavior, but we need
1379         // to preserve backwards compatibility.
1380         {isSpace, "",
1381                 nil,
1382                 nil,
1383                 []byte("")},
1384         {isSpace, " ",
1385                 nil,
1386                 nil,
1387                 []byte("")},
1388 }
1389
1390 func TestTrimFunc(t *testing.T) {
1391         for _, tc := range trimFuncTests {
1392                 trimmers := []struct {
1393                         name string
1394                         trim func(s []byte, f func(r rune) bool) []byte
1395                         out  []byte
1396                 }{
1397                         {"TrimFunc", TrimFunc, tc.trimOut},
1398                         {"TrimLeftFunc", TrimLeftFunc, tc.leftOut},
1399                         {"TrimRightFunc", TrimRightFunc, tc.rightOut},
1400                 }
1401                 for _, trimmer := range trimmers {
1402                         actual := trimmer.trim([]byte(tc.in), tc.f.f)
1403                         if actual == nil && trimmer.out != nil {
1404                                 t.Errorf("%s(%q, %q) = nil; want %q", trimmer.name, tc.in, tc.f.name, trimmer.out)
1405                         }
1406                         if actual != nil && trimmer.out == nil {
1407                                 t.Errorf("%s(%q, %q) = %q; want nil", trimmer.name, tc.in, tc.f.name, actual)
1408                         }
1409                         if !Equal(actual, trimmer.out) {
1410                                 t.Errorf("%s(%q, %q) = %q; want %q", trimmer.name, tc.in, tc.f.name, actual, trimmer.out)
1411                         }
1412                 }
1413         }
1414 }
1415
1416 type IndexFuncTest struct {
1417         in          string
1418         f           predicate
1419         first, last int
1420 }
1421
1422 var indexFuncTests = []IndexFuncTest{
1423         {"", isValidRune, -1, -1},
1424         {"abc", isDigit, -1, -1},
1425         {"0123", isDigit, 0, 3},
1426         {"a1b", isDigit, 1, 1},
1427         {space, isSpace, 0, len(space) - 3}, // last rune in space is 3 bytes
1428         {"\u0e50\u0e5212hello34\u0e50\u0e51", isDigit, 0, 18},
1429         {"\u2C6F\u2C6F\u2C6F\u2C6FABCDhelloEF\u2C6F\u2C6FGH\u2C6F\u2C6F", isUpper, 0, 34},
1430         {"12\u0e50\u0e52hello34\u0e50\u0e51", not(isDigit), 8, 12},
1431
1432         // tests of invalid UTF-8
1433         {"\x801", isDigit, 1, 1},
1434         {"\x80abc", isDigit, -1, -1},
1435         {"\xc0a\xc0", isValidRune, 1, 1},
1436         {"\xc0a\xc0", not(isValidRune), 0, 2},
1437         {"\xc0☺\xc0", not(isValidRune), 0, 4},
1438         {"\xc0☺\xc0\xc0", not(isValidRune), 0, 5},
1439         {"ab\xc0a\xc0cd", not(isValidRune), 2, 4},
1440         {"a\xe0\x80cd", not(isValidRune), 1, 2},
1441 }
1442
1443 func TestIndexFunc(t *testing.T) {
1444         for _, tc := range indexFuncTests {
1445                 first := IndexFunc([]byte(tc.in), tc.f.f)
1446                 if first != tc.first {
1447                         t.Errorf("IndexFunc(%q, %s) = %d; want %d", tc.in, tc.f.name, first, tc.first)
1448                 }
1449                 last := LastIndexFunc([]byte(tc.in), tc.f.f)
1450                 if last != tc.last {
1451                         t.Errorf("LastIndexFunc(%q, %s) = %d; want %d", tc.in, tc.f.name, last, tc.last)
1452                 }
1453         }
1454 }
1455
1456 type ReplaceTest struct {
1457         in       string
1458         old, new string
1459         n        int
1460         out      string
1461 }
1462
1463 var ReplaceTests = []ReplaceTest{
1464         {"hello", "l", "L", 0, "hello"},
1465         {"hello", "l", "L", -1, "heLLo"},
1466         {"hello", "x", "X", -1, "hello"},
1467         {"", "x", "X", -1, ""},
1468         {"radar", "r", "<r>", -1, "<r>ada<r>"},
1469         {"", "", "<>", -1, "<>"},
1470         {"banana", "a", "<>", -1, "b<>n<>n<>"},
1471         {"banana", "a", "<>", 1, "b<>nana"},
1472         {"banana", "a", "<>", 1000, "b<>n<>n<>"},
1473         {"banana", "an", "<>", -1, "b<><>a"},
1474         {"banana", "ana", "<>", -1, "b<>na"},
1475         {"banana", "", "<>", -1, "<>b<>a<>n<>a<>n<>a<>"},
1476         {"banana", "", "<>", 10, "<>b<>a<>n<>a<>n<>a<>"},
1477         {"banana", "", "<>", 6, "<>b<>a<>n<>a<>n<>a"},
1478         {"banana", "", "<>", 5, "<>b<>a<>n<>a<>na"},
1479         {"banana", "", "<>", 1, "<>banana"},
1480         {"banana", "a", "a", -1, "banana"},
1481         {"banana", "a", "a", 1, "banana"},
1482         {"☺☻☹", "", "<>", -1, "<>☺<>☻<>☹<>"},
1483 }
1484
1485 func TestReplace(t *testing.T) {
1486         for _, tt := range ReplaceTests {
1487                 in := append([]byte(tt.in), "<spare>"...)
1488                 in = in[:len(tt.in)]
1489                 out := Replace(in, []byte(tt.old), []byte(tt.new), tt.n)
1490                 if s := string(out); s != tt.out {
1491                         t.Errorf("Replace(%q, %q, %q, %d) = %q, want %q", tt.in, tt.old, tt.new, tt.n, s, tt.out)
1492                 }
1493                 if cap(in) == cap(out) && &in[:1][0] == &out[:1][0] {
1494                         t.Errorf("Replace(%q, %q, %q, %d) didn't copy", tt.in, tt.old, tt.new, tt.n)
1495                 }
1496                 if tt.n == -1 {
1497                         out := ReplaceAll(in, []byte(tt.old), []byte(tt.new))
1498                         if s := string(out); s != tt.out {
1499                                 t.Errorf("ReplaceAll(%q, %q, %q) = %q, want %q", tt.in, tt.old, tt.new, s, tt.out)
1500                         }
1501                 }
1502         }
1503 }
1504
1505 type TitleTest struct {
1506         in, out string
1507 }
1508
1509 var TitleTests = []TitleTest{
1510         {"", ""},
1511         {"a", "A"},
1512         {" aaa aaa aaa ", " Aaa Aaa Aaa "},
1513         {" Aaa Aaa Aaa ", " Aaa Aaa Aaa "},
1514         {"123a456", "123a456"},
1515         {"double-blind", "Double-Blind"},
1516         {"ÿøû", "Ÿøû"},
1517         {"with_underscore", "With_underscore"},
1518         {"unicode \xe2\x80\xa8 line separator", "Unicode \xe2\x80\xa8 Line Separator"},
1519 }
1520
1521 func TestTitle(t *testing.T) {
1522         for _, tt := range TitleTests {
1523                 if s := string(Title([]byte(tt.in))); s != tt.out {
1524                         t.Errorf("Title(%q) = %q, want %q", tt.in, s, tt.out)
1525                 }
1526         }
1527 }
1528
1529 var ToTitleTests = []TitleTest{
1530         {"", ""},
1531         {"a", "A"},
1532         {" aaa aaa aaa ", " AAA AAA AAA "},
1533         {" Aaa Aaa Aaa ", " AAA AAA AAA "},
1534         {"123a456", "123A456"},
1535         {"double-blind", "DOUBLE-BLIND"},
1536         {"ÿøû", "ŸØÛ"},
1537 }
1538
1539 func TestToTitle(t *testing.T) {
1540         for _, tt := range ToTitleTests {
1541                 if s := string(ToTitle([]byte(tt.in))); s != tt.out {
1542                         t.Errorf("ToTitle(%q) = %q, want %q", tt.in, s, tt.out)
1543                 }
1544         }
1545 }
1546
1547 var EqualFoldTests = []struct {
1548         s, t string
1549         out  bool
1550 }{
1551         {"abc", "abc", true},
1552         {"ABcd", "ABcd", true},
1553         {"123abc", "123ABC", true},
1554         {"αβδ", "ΑΒΔ", true},
1555         {"abc", "xyz", false},
1556         {"abc", "XYZ", false},
1557         {"abcdefghijk", "abcdefghijX", false},
1558         {"abcdefghijk", "abcdefghij\u212A", true},
1559         {"abcdefghijK", "abcdefghij\u212A", true},
1560         {"abcdefghijkz", "abcdefghij\u212Ay", false},
1561         {"abcdefghijKz", "abcdefghij\u212Ay", false},
1562 }
1563
1564 func TestEqualFold(t *testing.T) {
1565         for _, tt := range EqualFoldTests {
1566                 if out := EqualFold([]byte(tt.s), []byte(tt.t)); out != tt.out {
1567                         t.Errorf("EqualFold(%#q, %#q) = %v, want %v", tt.s, tt.t, out, tt.out)
1568                 }
1569                 if out := EqualFold([]byte(tt.t), []byte(tt.s)); out != tt.out {
1570                         t.Errorf("EqualFold(%#q, %#q) = %v, want %v", tt.t, tt.s, out, tt.out)
1571                 }
1572         }
1573 }
1574
1575 var cutTests = []struct {
1576         s, sep        string
1577         before, after string
1578         found         bool
1579 }{
1580         {"abc", "b", "a", "c", true},
1581         {"abc", "a", "", "bc", true},
1582         {"abc", "c", "ab", "", true},
1583         {"abc", "abc", "", "", true},
1584         {"abc", "", "", "abc", true},
1585         {"abc", "d", "abc", "", false},
1586         {"", "d", "", "", false},
1587         {"", "", "", "", true},
1588 }
1589
1590 func TestCut(t *testing.T) {
1591         for _, tt := range cutTests {
1592                 if before, after, found := Cut([]byte(tt.s), []byte(tt.sep)); string(before) != tt.before || string(after) != tt.after || found != tt.found {
1593                         t.Errorf("Cut(%q, %q) = %q, %q, %v, want %q, %q, %v", tt.s, tt.sep, before, after, found, tt.before, tt.after, tt.found)
1594                 }
1595         }
1596 }
1597
1598 func TestBufferGrowNegative(t *testing.T) {
1599         defer func() {
1600                 if err := recover(); err == nil {
1601                         t.Fatal("Grow(-1) should have panicked")
1602                 }
1603         }()
1604         var b Buffer
1605         b.Grow(-1)
1606 }
1607
1608 func TestBufferTruncateNegative(t *testing.T) {
1609         defer func() {
1610                 if err := recover(); err == nil {
1611                         t.Fatal("Truncate(-1) should have panicked")
1612                 }
1613         }()
1614         var b Buffer
1615         b.Truncate(-1)
1616 }
1617
1618 func TestBufferTruncateOutOfRange(t *testing.T) {
1619         defer func() {
1620                 if err := recover(); err == nil {
1621                         t.Fatal("Truncate(20) should have panicked")
1622                 }
1623         }()
1624         var b Buffer
1625         b.Write(make([]byte, 10))
1626         b.Truncate(20)
1627 }
1628
1629 var containsTests = []struct {
1630         b, subslice []byte
1631         want        bool
1632 }{
1633         {[]byte("hello"), []byte("hel"), true},
1634         {[]byte("日本語"), []byte("日本"), true},
1635         {[]byte("hello"), []byte("Hello, world"), false},
1636         {[]byte("東京"), []byte("京東"), false},
1637 }
1638
1639 func TestContains(t *testing.T) {
1640         for _, tt := range containsTests {
1641                 if got := Contains(tt.b, tt.subslice); got != tt.want {
1642                         t.Errorf("Contains(%q, %q) = %v, want %v", tt.b, tt.subslice, got, tt.want)
1643                 }
1644         }
1645 }
1646
1647 var ContainsAnyTests = []struct {
1648         b        []byte
1649         substr   string
1650         expected bool
1651 }{
1652         {[]byte(""), "", false},
1653         {[]byte(""), "a", false},
1654         {[]byte(""), "abc", false},
1655         {[]byte("a"), "", false},
1656         {[]byte("a"), "a", true},
1657         {[]byte("aaa"), "a", true},
1658         {[]byte("abc"), "xyz", false},
1659         {[]byte("abc"), "xcz", true},
1660         {[]byte("a☺b☻c☹d"), "uvw☻xyz", true},
1661         {[]byte("aRegExp*"), ".(|)*+?^$[]", true},
1662         {[]byte(dots + dots + dots), " ", false},
1663 }
1664
1665 func TestContainsAny(t *testing.T) {
1666         for _, ct := range ContainsAnyTests {
1667                 if ContainsAny(ct.b, ct.substr) != ct.expected {
1668                         t.Errorf("ContainsAny(%s, %s) = %v, want %v",
1669                                 ct.b, ct.substr, !ct.expected, ct.expected)
1670                 }
1671         }
1672 }
1673
1674 var ContainsRuneTests = []struct {
1675         b        []byte
1676         r        rune
1677         expected bool
1678 }{
1679         {[]byte(""), 'a', false},
1680         {[]byte("a"), 'a', true},
1681         {[]byte("aaa"), 'a', true},
1682         {[]byte("abc"), 'y', false},
1683         {[]byte("abc"), 'c', true},
1684         {[]byte("a☺b☻c☹d"), 'x', false},
1685         {[]byte("a☺b☻c☹d"), '☻', true},
1686         {[]byte("aRegExp*"), '*', true},
1687 }
1688
1689 func TestContainsRune(t *testing.T) {
1690         for _, ct := range ContainsRuneTests {
1691                 if ContainsRune(ct.b, ct.r) != ct.expected {
1692                         t.Errorf("ContainsRune(%q, %q) = %v, want %v",
1693                                 ct.b, ct.r, !ct.expected, ct.expected)
1694                 }
1695         }
1696 }
1697
1698 var makeFieldsInput = func() []byte {
1699         x := make([]byte, 1<<20)
1700         // Input is ~10% space, ~10% 2-byte UTF-8, rest ASCII non-space.
1701         for i := range x {
1702                 switch rand.Intn(10) {
1703                 case 0:
1704                         x[i] = ' '
1705                 case 1:
1706                         if i > 0 && x[i-1] == 'x' {
1707                                 copy(x[i-1:], "χ")
1708                                 break
1709                         }
1710                         fallthrough
1711                 default:
1712                         x[i] = 'x'
1713                 }
1714         }
1715         return x
1716 }
1717
1718 var makeFieldsInputASCII = func() []byte {
1719         x := make([]byte, 1<<20)
1720         // Input is ~10% space, rest ASCII non-space.
1721         for i := range x {
1722                 if rand.Intn(10) == 0 {
1723                         x[i] = ' '
1724                 } else {
1725                         x[i] = 'x'
1726                 }
1727         }
1728         return x
1729 }
1730
1731 var bytesdata = []struct {
1732         name string
1733         data []byte
1734 }{
1735         {"ASCII", makeFieldsInputASCII()},
1736         {"Mixed", makeFieldsInput()},
1737 }
1738
1739 func BenchmarkFields(b *testing.B) {
1740         for _, sd := range bytesdata {
1741                 b.Run(sd.name, func(b *testing.B) {
1742                         for j := 1 << 4; j <= 1<<20; j <<= 4 {
1743                                 b.Run(fmt.Sprintf("%d", j), func(b *testing.B) {
1744                                         b.ReportAllocs()
1745                                         b.SetBytes(int64(j))
1746                                         data := sd.data[:j]
1747                                         for i := 0; i < b.N; i++ {
1748                                                 Fields(data)
1749                                         }
1750                                 })
1751                         }
1752                 })
1753         }
1754 }
1755
1756 func BenchmarkFieldsFunc(b *testing.B) {
1757         for _, sd := range bytesdata {
1758                 b.Run(sd.name, func(b *testing.B) {
1759                         for j := 1 << 4; j <= 1<<20; j <<= 4 {
1760                                 b.Run(fmt.Sprintf("%d", j), func(b *testing.B) {
1761                                         b.ReportAllocs()
1762                                         b.SetBytes(int64(j))
1763                                         data := sd.data[:j]
1764                                         for i := 0; i < b.N; i++ {
1765                                                 FieldsFunc(data, unicode.IsSpace)
1766                                         }
1767                                 })
1768                         }
1769                 })
1770         }
1771 }
1772
1773 func BenchmarkTrimSpace(b *testing.B) {
1774         tests := []struct {
1775                 name  string
1776                 input []byte
1777         }{
1778                 {"NoTrim", []byte("typical")},
1779                 {"ASCII", []byte("  foo bar  ")},
1780                 {"SomeNonASCII", []byte("    \u2000\t\r\n x\t\t\r\r\ny\n \u3000    ")},
1781                 {"JustNonASCII", []byte("\u2000\u2000\u2000☺☺☺☺\u3000\u3000\u3000")},
1782         }
1783         for _, test := range tests {
1784                 b.Run(test.name, func(b *testing.B) {
1785                         for i := 0; i < b.N; i++ {
1786                                 TrimSpace(test.input)
1787                         }
1788                 })
1789         }
1790 }
1791
1792 func BenchmarkToValidUTF8(b *testing.B) {
1793         tests := []struct {
1794                 name  string
1795                 input []byte
1796         }{
1797                 {"Valid", []byte("typical")},
1798                 {"InvalidASCII", []byte("foo\xffbar")},
1799                 {"InvalidNonASCII", []byte("日本語\xff日本語")},
1800         }
1801         replacement := []byte("\uFFFD")
1802         b.ResetTimer()
1803         for _, test := range tests {
1804                 b.Run(test.name, func(b *testing.B) {
1805                         for i := 0; i < b.N; i++ {
1806                                 ToValidUTF8(test.input, replacement)
1807                         }
1808                 })
1809         }
1810 }
1811
1812 func makeBenchInputHard() []byte {
1813         tokens := [...]string{
1814                 "<a>", "<p>", "<b>", "<strong>",
1815                 "</a>", "</p>", "</b>", "</strong>",
1816                 "hello", "world",
1817         }
1818         x := make([]byte, 0, 1<<20)
1819         for {
1820                 i := rand.Intn(len(tokens))
1821                 if len(x)+len(tokens[i]) >= 1<<20 {
1822                         break
1823                 }
1824                 x = append(x, tokens[i]...)
1825         }
1826         return x
1827 }
1828
1829 var benchInputHard = makeBenchInputHard()
1830
1831 func benchmarkIndexHard(b *testing.B, sep []byte) {
1832         for i := 0; i < b.N; i++ {
1833                 Index(benchInputHard, sep)
1834         }
1835 }
1836
1837 func benchmarkLastIndexHard(b *testing.B, sep []byte) {
1838         for i := 0; i < b.N; i++ {
1839                 LastIndex(benchInputHard, sep)
1840         }
1841 }
1842
1843 func benchmarkCountHard(b *testing.B, sep []byte) {
1844         for i := 0; i < b.N; i++ {
1845                 Count(benchInputHard, sep)
1846         }
1847 }
1848
1849 func BenchmarkIndexHard1(b *testing.B) { benchmarkIndexHard(b, []byte("<>")) }
1850 func BenchmarkIndexHard2(b *testing.B) { benchmarkIndexHard(b, []byte("</pre>")) }
1851 func BenchmarkIndexHard3(b *testing.B) { benchmarkIndexHard(b, []byte("<b>hello world</b>")) }
1852 func BenchmarkIndexHard4(b *testing.B) {
1853         benchmarkIndexHard(b, []byte("<pre><b>hello</b><strong>world</strong></pre>"))
1854 }
1855
1856 func BenchmarkLastIndexHard1(b *testing.B) { benchmarkLastIndexHard(b, []byte("<>")) }
1857 func BenchmarkLastIndexHard2(b *testing.B) { benchmarkLastIndexHard(b, []byte("</pre>")) }
1858 func BenchmarkLastIndexHard3(b *testing.B) { benchmarkLastIndexHard(b, []byte("<b>hello world</b>")) }
1859
1860 func BenchmarkCountHard1(b *testing.B) { benchmarkCountHard(b, []byte("<>")) }
1861 func BenchmarkCountHard2(b *testing.B) { benchmarkCountHard(b, []byte("</pre>")) }
1862 func BenchmarkCountHard3(b *testing.B) { benchmarkCountHard(b, []byte("<b>hello world</b>")) }
1863
1864 func BenchmarkSplitEmptySeparator(b *testing.B) {
1865         for i := 0; i < b.N; i++ {
1866                 Split(benchInputHard, nil)
1867         }
1868 }
1869
1870 func BenchmarkSplitSingleByteSeparator(b *testing.B) {
1871         sep := []byte("/")
1872         for i := 0; i < b.N; i++ {
1873                 Split(benchInputHard, sep)
1874         }
1875 }
1876
1877 func BenchmarkSplitMultiByteSeparator(b *testing.B) {
1878         sep := []byte("hello")
1879         for i := 0; i < b.N; i++ {
1880                 Split(benchInputHard, sep)
1881         }
1882 }
1883
1884 func BenchmarkSplitNSingleByteSeparator(b *testing.B) {
1885         sep := []byte("/")
1886         for i := 0; i < b.N; i++ {
1887                 SplitN(benchInputHard, sep, 10)
1888         }
1889 }
1890
1891 func BenchmarkSplitNMultiByteSeparator(b *testing.B) {
1892         sep := []byte("hello")
1893         for i := 0; i < b.N; i++ {
1894                 SplitN(benchInputHard, sep, 10)
1895         }
1896 }
1897
1898 func BenchmarkRepeat(b *testing.B) {
1899         for i := 0; i < b.N; i++ {
1900                 Repeat([]byte("-"), 80)
1901         }
1902 }
1903
1904 func BenchmarkBytesCompare(b *testing.B) {
1905         for n := 1; n <= 2048; n <<= 1 {
1906                 b.Run(fmt.Sprint(n), func(b *testing.B) {
1907                         var x = make([]byte, n)
1908                         var y = make([]byte, n)
1909
1910                         for i := 0; i < n; i++ {
1911                                 x[i] = 'a'
1912                         }
1913
1914                         for i := 0; i < n; i++ {
1915                                 y[i] = 'a'
1916                         }
1917
1918                         b.ResetTimer()
1919                         for i := 0; i < b.N; i++ {
1920                                 Compare(x, y)
1921                         }
1922                 })
1923         }
1924 }
1925
1926 func BenchmarkIndexAnyASCII(b *testing.B) {
1927         x := Repeat([]byte{'#'}, 2048) // Never matches set
1928         cs := "0123456789abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz"
1929         for k := 1; k <= 2048; k <<= 4 {
1930                 for j := 1; j <= 64; j <<= 1 {
1931                         b.Run(fmt.Sprintf("%d:%d", k, j), func(b *testing.B) {
1932                                 for i := 0; i < b.N; i++ {
1933                                         IndexAny(x[:k], cs[:j])
1934                                 }
1935                         })
1936                 }
1937         }
1938 }
1939
1940 func BenchmarkIndexAnyUTF8(b *testing.B) {
1941         x := Repeat([]byte{'#'}, 2048) // Never matches set
1942         cs := "你好世界, hello world. 你好世界, hello world. 你好世界, hello world."
1943         for k := 1; k <= 2048; k <<= 4 {
1944                 for j := 1; j <= 64; j <<= 1 {
1945                         b.Run(fmt.Sprintf("%d:%d", k, j), func(b *testing.B) {
1946                                 for i := 0; i < b.N; i++ {
1947                                         IndexAny(x[:k], cs[:j])
1948                                 }
1949                         })
1950                 }
1951         }
1952 }
1953
1954 func BenchmarkLastIndexAnyASCII(b *testing.B) {
1955         x := Repeat([]byte{'#'}, 2048) // Never matches set
1956         cs := "0123456789abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz"
1957         for k := 1; k <= 2048; k <<= 4 {
1958                 for j := 1; j <= 64; j <<= 1 {
1959                         b.Run(fmt.Sprintf("%d:%d", k, j), func(b *testing.B) {
1960                                 for i := 0; i < b.N; i++ {
1961                                         LastIndexAny(x[:k], cs[:j])
1962                                 }
1963                         })
1964                 }
1965         }
1966 }
1967
1968 func BenchmarkLastIndexAnyUTF8(b *testing.B) {
1969         x := Repeat([]byte{'#'}, 2048) // Never matches set
1970         cs := "你好世界, hello world. 你好世界, hello world. 你好世界, hello world."
1971         for k := 1; k <= 2048; k <<= 4 {
1972                 for j := 1; j <= 64; j <<= 1 {
1973                         b.Run(fmt.Sprintf("%d:%d", k, j), func(b *testing.B) {
1974                                 for i := 0; i < b.N; i++ {
1975                                         LastIndexAny(x[:k], cs[:j])
1976                                 }
1977                         })
1978                 }
1979         }
1980 }
1981
1982 func BenchmarkTrimASCII(b *testing.B) {
1983         cs := "0123456789abcdef"
1984         for k := 1; k <= 4096; k <<= 4 {
1985                 for j := 1; j <= 16; j <<= 1 {
1986                         b.Run(fmt.Sprintf("%d:%d", k, j), func(b *testing.B) {
1987                                 x := Repeat([]byte(cs[:j]), k) // Always matches set
1988                                 for i := 0; i < b.N; i++ {
1989                                         Trim(x[:k], cs[:j])
1990                                 }
1991                         })
1992                 }
1993         }
1994 }
1995
1996 func BenchmarkTrimByte(b *testing.B) {
1997         x := []byte("  the quick brown fox   ")
1998         for i := 0; i < b.N; i++ {
1999                 Trim(x, " ")
2000         }
2001 }
2002
2003 func BenchmarkIndexPeriodic(b *testing.B) {
2004         key := []byte{1, 1}
2005         for _, skip := range [...]int{2, 4, 8, 16, 32, 64} {
2006                 b.Run(fmt.Sprintf("IndexPeriodic%d", skip), func(b *testing.B) {
2007                         buf := make([]byte, 1<<16)
2008                         for i := 0; i < len(buf); i += skip {
2009                                 buf[i] = 1
2010                         }
2011                         for i := 0; i < b.N; i++ {
2012                                 Index(buf, key)
2013                         }
2014                 })
2015         }
2016 }