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