libgo/go/strings/strings_test.go

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