Source file src/bytes/bytes_test.go

Documentation: bytes

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

View as plain text