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