src/slices/slices_test.go

   1 // Copyright 2021 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 slices_test
   6
   7 import (
   8         "cmp"
   9         "internal/race"
  10         "internal/testenv"
  11         "math"
  12         . "slices"
  13         "strings"
  14         "testing"
  15 )
  16
  17 var equalIntTests = []struct {
  18         s1, s2 []int
  19         want   bool
  20 }{
  21         {
  22                 []int{1},
  23                 nil,
  24                 false,
  25         },
  26         {
  27                 []int{},
  28                 nil,
  29                 true,
  30         },
  31         {
  32                 []int{1, 2, 3},
  33                 []int{1, 2, 3},
  34                 true,
  35         },
  36         {
  37                 []int{1, 2, 3},
  38                 []int{1, 2, 3, 4},
  39                 false,
  40         },
  41 }
  42
  43 var equalFloatTests = []struct {
  44         s1, s2       []float64
  45         wantEqual    bool
  46         wantEqualNaN bool
  47 }{
  48         {
  49                 []float64{1, 2},
  50                 []float64{1, 2},
  51                 true,
  52                 true,
  53         },
  54         {
  55                 []float64{1, 2, math.NaN()},
  56                 []float64{1, 2, math.NaN()},
  57                 false,
  58                 true,
  59         },
  60 }
  61
  62 func TestEqual(t *testing.T) {
  63         for _, test := range equalIntTests {
  64                 if got := Equal(test.s1, test.s2); got != test.want {
  65                         t.Errorf("Equal(%v, %v) = %t, want %t", test.s1, test.s2, got, test.want)
  66                 }
  67         }
  68         for _, test := range equalFloatTests {
  69                 if got := Equal(test.s1, test.s2); got != test.wantEqual {
  70                         t.Errorf("Equal(%v, %v) = %t, want %t", test.s1, test.s2, got, test.wantEqual)
  71                 }
  72         }
  73 }
  74
  75 // equal is simply ==.
  76 func equal[T comparable](v1, v2 T) bool {
  77         return v1 == v2
  78 }
  79
  80 // equalNaN is like == except that all NaNs are equal.
  81 func equalNaN[T comparable](v1, v2 T) bool {
  82         isNaN := func(f T) bool { return f != f }
  83         return v1 == v2 || (isNaN(v1) && isNaN(v2))
  84 }
  85
  86 // offByOne returns true if integers v1 and v2 differ by 1.
  87 func offByOne(v1, v2 int) bool {
  88         return v1 == v2+1 || v1 == v2-1
  89 }
  90
  91 func TestEqualFunc(t *testing.T) {
  92         for _, test := range equalIntTests {
  93                 if got := EqualFunc(test.s1, test.s2, equal[int]); got != test.want {
  94                         t.Errorf("EqualFunc(%v, %v, equal[int]) = %t, want %t", test.s1, test.s2, got, test.want)
  95                 }
  96         }
  97         for _, test := range equalFloatTests {
  98                 if got := EqualFunc(test.s1, test.s2, equal[float64]); got != test.wantEqual {
  99                         t.Errorf("Equal(%v, %v, equal[float64]) = %t, want %t", test.s1, test.s2, got, test.wantEqual)
 100                 }
 101                 if got := EqualFunc(test.s1, test.s2, equalNaN[float64]); got != test.wantEqualNaN {
 102                         t.Errorf("Equal(%v, %v, equalNaN[float64]) = %t, want %t", test.s1, test.s2, got, test.wantEqualNaN)
 103                 }
 104         }
 105
 106         s1 := []int{1, 2, 3}
 107         s2 := []int{2, 3, 4}
 108         if EqualFunc(s1, s1, offByOne) {
 109                 t.Errorf("EqualFunc(%v, %v, offByOne) = true, want false", s1, s1)
 110         }
 111         if !EqualFunc(s1, s2, offByOne) {
 112                 t.Errorf("EqualFunc(%v, %v, offByOne) = false, want true", s1, s2)
 113         }
 114
 115         s3 := []string{"a", "b", "c"}
 116         s4 := []string{"A", "B", "C"}
 117         if !EqualFunc(s3, s4, strings.EqualFold) {
 118                 t.Errorf("EqualFunc(%v, %v, strings.EqualFold) = false, want true", s3, s4)
 119         }
 120
 121         cmpIntString := func(v1 int, v2 string) bool {
 122                 return string(rune(v1)-1+'a') == v2
 123         }
 124         if !EqualFunc(s1, s3, cmpIntString) {
 125                 t.Errorf("EqualFunc(%v, %v, cmpIntString) = false, want true", s1, s3)
 126         }
 127 }
 128
 129 func BenchmarkEqualFunc_Large(b *testing.B) {
 130         type Large [4 * 1024]byte
 131
 132         xs := make([]Large, 1024)
 133         ys := make([]Large, 1024)
 134         for i := 0; i < b.N; i++ {
 135                 _ = EqualFunc(xs, ys, func(x, y Large) bool { return x == y })
 136         }
 137 }
 138
 139 var compareIntTests = []struct {
 140         s1, s2 []int
 141         want   int
 142 }{
 143         {
 144                 []int{1},
 145                 []int{1},
 146                 0,
 147         },
 148         {
 149                 []int{1},
 150                 []int{},
 151                 1,
 152         },
 153         {
 154                 []int{},
 155                 []int{1},
 156                 -1,
 157         },
 158         {
 159                 []int{},
 160                 []int{},
 161                 0,
 162         },
 163         {
 164                 []int{1, 2, 3},
 165                 []int{1, 2, 3},
 166                 0,
 167         },
 168         {
 169                 []int{1, 2, 3},
 170                 []int{1, 2, 3, 4},
 171                 -1,
 172         },
 173         {
 174                 []int{1, 2, 3, 4},
 175                 []int{1, 2, 3},
 176                 +1,
 177         },
 178         {
 179                 []int{1, 2, 3},
 180                 []int{1, 4, 3},
 181                 -1,
 182         },
 183         {
 184                 []int{1, 4, 3},
 185                 []int{1, 2, 3},
 186                 +1,
 187         },
 188         {
 189                 []int{1, 4, 3},
 190                 []int{1, 2, 3, 8, 9},
 191                 +1,
 192         },
 193 }
 194
 195 var compareFloatTests = []struct {
 196         s1, s2 []float64
 197         want   int
 198 }{
 199         {
 200                 []float64{},
 201                 []float64{},
 202                 0,
 203         },
 204         {
 205                 []float64{1},
 206                 []float64{1},
 207                 0,
 208         },
 209         {
 210                 []float64{math.NaN()},
 211                 []float64{math.NaN()},
 212                 0,
 213         },
 214         {
 215                 []float64{1, 2, math.NaN()},
 216                 []float64{1, 2, math.NaN()},
 217                 0,
 218         },
 219         {
 220                 []float64{1, math.NaN(), 3},
 221                 []float64{1, math.NaN(), 4},
 222                 -1,
 223         },
 224         {
 225                 []float64{1, math.NaN(), 3},
 226                 []float64{1, 2, 4},
 227                 -1,
 228         },
 229         {
 230                 []float64{1, math.NaN(), 3},
 231                 []float64{1, 2, math.NaN()},
 232                 -1,
 233         },
 234         {
 235                 []float64{1, 2, 3},
 236                 []float64{1, 2, math.NaN()},
 237                 +1,
 238         },
 239         {
 240                 []float64{1, 2, 3},
 241                 []float64{1, math.NaN(), 3},
 242                 +1,
 243         },
 244         {
 245                 []float64{1, math.NaN(), 3, 4},
 246                 []float64{1, 2, math.NaN()},
 247                 -1,
 248         },
 249 }
 250
 251 func TestCompare(t *testing.T) {
 252         intWant := func(want bool) string {
 253                 if want {
 254                         return "0"
 255                 }
 256                 return "!= 0"
 257         }
 258         for _, test := range equalIntTests {
 259                 if got := Compare(test.s1, test.s2); (got == 0) != test.want {
 260                         t.Errorf("Compare(%v, %v) = %d, want %s", test.s1, test.s2, got, intWant(test.want))
 261                 }
 262         }
 263         for _, test := range equalFloatTests {
 264                 if got := Compare(test.s1, test.s2); (got == 0) != test.wantEqualNaN {
 265                         t.Errorf("Compare(%v, %v) = %d, want %s", test.s1, test.s2, got, intWant(test.wantEqualNaN))
 266                 }
 267         }
 268
 269         for _, test := range compareIntTests {
 270                 if got := Compare(test.s1, test.s2); got != test.want {
 271                         t.Errorf("Compare(%v, %v) = %d, want %d", test.s1, test.s2, got, test.want)
 272                 }
 273         }
 274         for _, test := range compareFloatTests {
 275                 if got := Compare(test.s1, test.s2); got != test.want {
 276                         t.Errorf("Compare(%v, %v) = %d, want %d", test.s1, test.s2, got, test.want)
 277                 }
 278         }
 279 }
 280
 281 func equalToCmp[T comparable](eq func(T, T) bool) func(T, T) int {
 282         return func(v1, v2 T) int {
 283                 if eq(v1, v2) {
 284                         return 0
 285                 }
 286                 return 1
 287         }
 288 }
 289
 290 func TestCompareFunc(t *testing.T) {
 291         intWant := func(want bool) string {
 292                 if want {
 293                         return "0"
 294                 }
 295                 return "!= 0"
 296         }
 297         for _, test := range equalIntTests {
 298                 if got := CompareFunc(test.s1, test.s2, equalToCmp(equal[int])); (got == 0) != test.want {
 299                         t.Errorf("CompareFunc(%v, %v, equalToCmp(equal[int])) = %d, want %s", test.s1, test.s2, got, intWant(test.want))
 300                 }
 301         }
 302         for _, test := range equalFloatTests {
 303                 if got := CompareFunc(test.s1, test.s2, equalToCmp(equal[float64])); (got == 0) != test.wantEqual {
 304                         t.Errorf("CompareFunc(%v, %v, equalToCmp(equal[float64])) = %d, want %s", test.s1, test.s2, got, intWant(test.wantEqual))
 305                 }
 306         }
 307
 308         for _, test := range compareIntTests {
 309                 if got := CompareFunc(test.s1, test.s2, cmp.Compare[int]); got != test.want {
 310                         t.Errorf("CompareFunc(%v, %v, cmp[int]) = %d, want %d", test.s1, test.s2, got, test.want)
 311                 }
 312         }
 313         for _, test := range compareFloatTests {
 314                 if got := CompareFunc(test.s1, test.s2, cmp.Compare[float64]); got != test.want {
 315                         t.Errorf("CompareFunc(%v, %v, cmp[float64]) = %d, want %d", test.s1, test.s2, got, test.want)
 316                 }
 317         }
 318
 319         s1 := []int{1, 2, 3}
 320         s2 := []int{2, 3, 4}
 321         if got := CompareFunc(s1, s2, equalToCmp(offByOne)); got != 0 {
 322                 t.Errorf("CompareFunc(%v, %v, offByOne) = %d, want 0", s1, s2, got)
 323         }
 324
 325         s3 := []string{"a", "b", "c"}
 326         s4 := []string{"A", "B", "C"}
 327         if got := CompareFunc(s3, s4, strings.Compare); got != 1 {
 328                 t.Errorf("CompareFunc(%v, %v, strings.Compare) = %d, want 1", s3, s4, got)
 329         }
 330
 331         compareLower := func(v1, v2 string) int {
 332                 return strings.Compare(strings.ToLower(v1), strings.ToLower(v2))
 333         }
 334         if got := CompareFunc(s3, s4, compareLower); got != 0 {
 335                 t.Errorf("CompareFunc(%v, %v, compareLower) = %d, want 0", s3, s4, got)
 336         }
 337
 338         cmpIntString := func(v1 int, v2 string) int {
 339                 return strings.Compare(string(rune(v1)-1+'a'), v2)
 340         }
 341         if got := CompareFunc(s1, s3, cmpIntString); got != 0 {
 342                 t.Errorf("CompareFunc(%v, %v, cmpIntString) = %d, want 0", s1, s3, got)
 343         }
 344 }
 345
 346 var indexTests = []struct {
 347         s    []int
 348         v    int
 349         want int
 350 }{
 351         {
 352                 nil,
 353                 0,
 354                 -1,
 355         },
 356         {
 357                 []int{},
 358                 0,
 359                 -1,
 360         },
 361         {
 362                 []int{1, 2, 3},
 363                 2,
 364                 1,
 365         },
 366         {
 367                 []int{1, 2, 2, 3},
 368                 2,
 369                 1,
 370         },
 371         {
 372                 []int{1, 2, 3, 2},
 373                 2,
 374                 1,
 375         },
 376 }
 377
 378 func TestIndex(t *testing.T) {
 379         for _, test := range indexTests {
 380                 if got := Index(test.s, test.v); got != test.want {
 381                         t.Errorf("Index(%v, %v) = %d, want %d", test.s, test.v, got, test.want)
 382                 }
 383         }
 384 }
 385
 386 func equalToIndex[T any](f func(T, T) bool, v1 T) func(T) bool {
 387         return func(v2 T) bool {
 388                 return f(v1, v2)
 389         }
 390 }
 391
 392 func BenchmarkIndex_Large(b *testing.B) {
 393         type Large [4 * 1024]byte
 394
 395         ss := make([]Large, 1024)
 396         for i := 0; i < b.N; i++ {
 397                 _ = Index(ss, Large{1})
 398         }
 399 }
 400
 401 func TestIndexFunc(t *testing.T) {
 402         for _, test := range indexTests {
 403                 if got := IndexFunc(test.s, equalToIndex(equal[int], test.v)); got != test.want {
 404                         t.Errorf("IndexFunc(%v, equalToIndex(equal[int], %v)) = %d, want %d", test.s, test.v, got, test.want)
 405                 }
 406         }
 407
 408         s1 := []string{"hi", "HI"}
 409         if got := IndexFunc(s1, equalToIndex(equal[string], "HI")); got != 1 {
 410                 t.Errorf("IndexFunc(%v, equalToIndex(equal[string], %q)) = %d, want %d", s1, "HI", got, 1)
 411         }
 412         if got := IndexFunc(s1, equalToIndex(strings.EqualFold, "HI")); got != 0 {
 413                 t.Errorf("IndexFunc(%v, equalToIndex(strings.EqualFold, %q)) = %d, want %d", s1, "HI", got, 0)
 414         }
 415 }
 416
 417 func BenchmarkIndexFunc_Large(b *testing.B) {
 418         type Large [4 * 1024]byte
 419
 420         ss := make([]Large, 1024)
 421         for i := 0; i < b.N; i++ {
 422                 _ = IndexFunc(ss, func(e Large) bool {
 423                         return e == Large{1}
 424                 })
 425         }
 426 }
 427
 428 func TestContains(t *testing.T) {
 429         for _, test := range indexTests {
 430                 if got := Contains(test.s, test.v); got != (test.want != -1) {
 431                         t.Errorf("Contains(%v, %v) = %t, want %t", test.s, test.v, got, test.want != -1)
 432                 }
 433         }
 434 }
 435
 436 func TestContainsFunc(t *testing.T) {
 437         for _, test := range indexTests {
 438                 if got := ContainsFunc(test.s, equalToIndex(equal[int], test.v)); got != (test.want != -1) {
 439                         t.Errorf("ContainsFunc(%v, equalToIndex(equal[int], %v)) = %t, want %t", test.s, test.v, got, test.want != -1)
 440                 }
 441         }
 442
 443         s1 := []string{"hi", "HI"}
 444         if got := ContainsFunc(s1, equalToIndex(equal[string], "HI")); got != true {
 445                 t.Errorf("ContainsFunc(%v, equalToContains(equal[string], %q)) = %t, want %t", s1, "HI", got, true)
 446         }
 447         if got := ContainsFunc(s1, equalToIndex(equal[string], "hI")); got != false {
 448                 t.Errorf("ContainsFunc(%v, equalToContains(strings.EqualFold, %q)) = %t, want %t", s1, "hI", got, false)
 449         }
 450         if got := ContainsFunc(s1, equalToIndex(strings.EqualFold, "hI")); got != true {
 451                 t.Errorf("ContainsFunc(%v, equalToContains(strings.EqualFold, %q)) = %t, want %t", s1, "hI", got, true)
 452         }
 453 }
 454
 455 var insertTests = []struct {
 456         s    []int
 457         i    int
 458         add  []int
 459         want []int
 460 }{
 461         {
 462                 []int{1, 2, 3},
 463                 0,
 464                 []int{4},
 465                 []int{4, 1, 2, 3},
 466         },
 467         {
 468                 []int{1, 2, 3},
 469                 1,
 470                 []int{4},
 471                 []int{1, 4, 2, 3},
 472         },
 473         {
 474                 []int{1, 2, 3},
 475                 3,
 476                 []int{4},
 477                 []int{1, 2, 3, 4},
 478         },
 479         {
 480                 []int{1, 2, 3},
 481                 2,
 482                 []int{4, 5},
 483                 []int{1, 2, 4, 5, 3},
 484         },
 485 }
 486
 487 func TestInsert(t *testing.T) {
 488         s := []int{1, 2, 3}
 489         if got := Insert(s, 0); !Equal(got, s) {
 490                 t.Errorf("Insert(%v, 0) = %v, want %v", s, got, s)
 491         }
 492         for _, test := range insertTests {
 493                 copy := Clone(test.s)
 494                 if got := Insert(copy, test.i, test.add...); !Equal(got, test.want) {
 495                         t.Errorf("Insert(%v, %d, %v...) = %v, want %v", test.s, test.i, test.add, got, test.want)
 496                 }
 497         }
 498
 499         if !testenv.OptimizationOff() && !race.Enabled {
 500                 // Allocations should be amortized.
 501                 const count = 50
 502                 n := testing.AllocsPerRun(10, func() {
 503                         s := []int{1, 2, 3}
 504                         for i := 0; i < count; i++ {
 505                                 s = Insert(s, 0, 1)
 506                         }
 507                 })
 508                 if n > count/2 {
 509                         t.Errorf("too many allocations inserting %d elements: got %v, want less than %d", count, n, count/2)
 510                 }
 511         }
 512 }
 513
 514 func TestInsertOverlap(t *testing.T) {
 515         const N = 10
 516         a := make([]int, N)
 517         want := make([]int, 2*N)
 518         for n := 0; n <= N; n++ { // length
 519                 for i := 0; i <= n; i++ { // insertion point
 520                         for x := 0; x <= N; x++ { // start of inserted data
 521                                 for y := x; y <= N; y++ { // end of inserted data
 522                                         for k := 0; k < N; k++ {
 523                                                 a[k] = k
 524                                         }
 525                                         want = want[:0]
 526                                         want = append(want, a[:i]...)
 527                                         want = append(want, a[x:y]...)
 528                                         want = append(want, a[i:n]...)
 529                                         got := Insert(a[:n], i, a[x:y]...)
 530                                         if !Equal(got, want) {
 531                                                 t.Errorf("Insert with overlap failed n=%d i=%d x=%d y=%d, got %v want %v", n, i, x, y, got, want)
 532                                         }
 533                                 }
 534                         }
 535                 }
 536         }
 537 }
 538
 539 var deleteTests = []struct {
 540         s    []int
 541         i, j int
 542         want []int
 543 }{
 544         {
 545                 []int{1, 2, 3},
 546                 0,
 547                 0,
 548                 []int{1, 2, 3},
 549         },
 550         {
 551                 []int{1, 2, 3},
 552                 0,
 553                 1,
 554                 []int{2, 3},
 555         },
 556         {
 557                 []int{1, 2, 3},
 558                 3,
 559                 3,
 560                 []int{1, 2, 3},
 561         },
 562         {
 563                 []int{1, 2, 3},
 564                 0,
 565                 2,
 566                 []int{3},
 567         },
 568         {
 569                 []int{1, 2, 3},
 570                 0,
 571                 3,
 572                 []int{},
 573         },
 574 }
 575
 576 func TestDelete(t *testing.T) {
 577         for _, test := range deleteTests {
 578                 copy := Clone(test.s)
 579                 if got := Delete(copy, test.i, test.j); !Equal(got, test.want) {
 580                         t.Errorf("Delete(%v, %d, %d) = %v, want %v", test.s, test.i, test.j, got, test.want)
 581                 }
 582         }
 583 }
 584
 585 var deleteFuncTests = []struct {
 586         s    []int
 587         fn   func(int) bool
 588         want []int
 589 }{
 590         {
 591                 nil,
 592                 func(int) bool { return true },
 593                 nil,
 594         },
 595         {
 596                 []int{1, 2, 3},
 597                 func(int) bool { return true },
 598                 nil,
 599         },
 600         {
 601                 []int{1, 2, 3},
 602                 func(int) bool { return false },
 603                 []int{1, 2, 3},
 604         },
 605         {
 606                 []int{1, 2, 3},
 607                 func(i int) bool { return i > 2 },
 608                 []int{1, 2},
 609         },
 610         {
 611                 []int{1, 2, 3},
 612                 func(i int) bool { return i < 2 },
 613                 []int{2, 3},
 614         },
 615         {
 616                 []int{10, 2, 30},
 617                 func(i int) bool { return i >= 10 },
 618                 []int{2},
 619         },
 620 }
 621
 622 func TestDeleteFunc(t *testing.T) {
 623         for i, test := range deleteFuncTests {
 624                 copy := Clone(test.s)
 625                 if got := DeleteFunc(copy, test.fn); !Equal(got, test.want) {
 626                         t.Errorf("DeleteFunc case %d: got %v, want %v", i, got, test.want)
 627                 }
 628         }
 629 }
 630
 631 func panics(f func()) (b bool) {
 632         defer func() {
 633                 if x := recover(); x != nil {
 634                         b = true
 635                 }
 636         }()
 637         f()
 638         return false
 639 }
 640
 641 func TestDeletePanics(t *testing.T) {
 642         for _, test := range []struct {
 643                 name string
 644                 s    []int
 645                 i, j int
 646         }{
 647                 {"with negative first index", []int{42}, -2, 1},
 648                 {"with negative second index", []int{42}, 1, -1},
 649                 {"with out-of-bounds first index", []int{42}, 2, 3},
 650                 {"with out-of-bounds second index", []int{42}, 0, 2},
 651                 {"with invalid i>j", []int{42}, 1, 0},
 652         } {
 653                 if !panics(func() { Delete(test.s, test.i, test.j) }) {
 654                         t.Errorf("Delete %s: got no panic, want panic", test.name)
 655                 }
 656         }
 657 }
 658
 659 func TestClone(t *testing.T) {
 660         s1 := []int{1, 2, 3}
 661         s2 := Clone(s1)
 662         if !Equal(s1, s2) {
 663                 t.Errorf("Clone(%v) = %v, want %v", s1, s2, s1)
 664         }
 665         s1[0] = 4
 666         want := []int{1, 2, 3}
 667         if !Equal(s2, want) {
 668                 t.Errorf("Clone(%v) changed unexpectedly to %v", want, s2)
 669         }
 670         if got := Clone([]int(nil)); got != nil {
 671                 t.Errorf("Clone(nil) = %#v, want nil", got)
 672         }
 673         if got := Clone(s1[:0]); got == nil || len(got) != 0 {
 674                 t.Errorf("Clone(%v) = %#v, want %#v", s1[:0], got, s1[:0])
 675         }
 676 }
 677
 678 var compactTests = []struct {
 679         name string
 680         s    []int
 681         want []int
 682 }{
 683         {
 684                 "nil",
 685                 nil,
 686                 nil,
 687         },
 688         {
 689                 "one",
 690                 []int{1},
 691                 []int{1},
 692         },
 693         {
 694                 "sorted",
 695                 []int{1, 2, 3},
 696                 []int{1, 2, 3},
 697         },
 698         {
 699                 "1 item",
 700                 []int{1, 1, 2},
 701                 []int{1, 2},
 702         },
 703         {
 704                 "unsorted",
 705                 []int{1, 2, 1},
 706                 []int{1, 2, 1},
 707         },
 708         {
 709                 "many",
 710                 []int{1, 2, 2, 3, 3, 4},
 711                 []int{1, 2, 3, 4},
 712         },
 713 }
 714
 715 func TestCompact(t *testing.T) {
 716         for _, test := range compactTests {
 717                 copy := Clone(test.s)
 718                 if got := Compact(copy); !Equal(got, test.want) {
 719                         t.Errorf("Compact(%v) = %v, want %v", test.s, got, test.want)
 720                 }
 721         }
 722 }
 723
 724 func BenchmarkCompact(b *testing.B) {
 725         for _, c := range compactTests {
 726                 b.Run(c.name, func(b *testing.B) {
 727                         ss := make([]int, 0, 64)
 728                         for k := 0; k < b.N; k++ {
 729                                 ss = ss[:0]
 730                                 ss = append(ss, c.s...)
 731                                 _ = Compact(ss)
 732                         }
 733                 })
 734         }
 735 }
 736
 737 func BenchmarkCompact_Large(b *testing.B) {
 738         type Large [4 * 1024]byte
 739
 740         ss := make([]Large, 1024)
 741         for i := 0; i < b.N; i++ {
 742                 _ = Compact(ss)
 743         }
 744 }
 745
 746 func TestCompactFunc(t *testing.T) {
 747         for _, test := range compactTests {
 748                 copy := Clone(test.s)
 749                 if got := CompactFunc(copy, equal[int]); !Equal(got, test.want) {
 750                         t.Errorf("CompactFunc(%v, equal[int]) = %v, want %v", test.s, got, test.want)
 751                 }
 752         }
 753
 754         s1 := []string{"a", "a", "A", "B", "b"}
 755         copy := Clone(s1)
 756         want := []string{"a", "B"}
 757         if got := CompactFunc(copy, strings.EqualFold); !Equal(got, want) {
 758                 t.Errorf("CompactFunc(%v, strings.EqualFold) = %v, want %v", s1, got, want)
 759         }
 760 }
 761
 762 func BenchmarkCompactFunc_Large(b *testing.B) {
 763         type Large [4 * 1024]byte
 764
 765         ss := make([]Large, 1024)
 766         for i := 0; i < b.N; i++ {
 767                 _ = CompactFunc(ss, func(a, b Large) bool { return a == b })
 768         }
 769 }
 770
 771 func TestGrow(t *testing.T) {
 772         s1 := []int{1, 2, 3}
 773
 774         copy := Clone(s1)
 775         s2 := Grow(copy, 1000)
 776         if !Equal(s1, s2) {
 777                 t.Errorf("Grow(%v) = %v, want %v", s1, s2, s1)
 778         }
 779         if cap(s2) < 1000+len(s1) {
 780                 t.Errorf("after Grow(%v) cap = %d, want >= %d", s1, cap(s2), 1000+len(s1))
 781         }
 782
 783         // Test mutation of elements between length and capacity.
 784         copy = Clone(s1)
 785         s3 := Grow(copy[:1], 2)[:3]
 786         if !Equal(s1, s3) {
 787                 t.Errorf("Grow should not mutate elements between length and capacity")
 788         }
 789         s3 = Grow(copy[:1], 1000)[:3]
 790         if !Equal(s1, s3) {
 791                 t.Errorf("Grow should not mutate elements between length and capacity")
 792         }
 793
 794         // Test number of allocations.
 795         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)) }); n != 0 {
 796                 t.Errorf("Grow should not allocate when given sufficient capacity; allocated %v times", n)
 797         }
 798         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)+1) }); n != 1 {
 799                 errorf := t.Errorf
 800                 if race.Enabled || testenv.OptimizationOff() {
 801                         errorf = t.Logf // this allocates multiple times in race detector mode
 802                 }
 803                 errorf("Grow should allocate once when given insufficient capacity; allocated %v times", n)
 804         }
 805
 806         // Test for negative growth sizes.
 807         var gotPanic bool
 808         func() {
 809                 defer func() { gotPanic = recover() != nil }()
 810                 Grow(s1, -1)
 811         }()
 812         if !gotPanic {
 813                 t.Errorf("Grow(-1) did not panic; expected a panic")
 814         }
 815 }
 816
 817 func TestClip(t *testing.T) {
 818         s1 := []int{1, 2, 3, 4, 5, 6}[:3]
 819         orig := Clone(s1)
 820         if len(s1) != 3 {
 821                 t.Errorf("len(%v) = %d, want 3", s1, len(s1))
 822         }
 823         if cap(s1) < 6 {
 824                 t.Errorf("cap(%v[:3]) = %d, want >= 6", orig, cap(s1))
 825         }
 826         s2 := Clip(s1)
 827         if !Equal(s1, s2) {
 828                 t.Errorf("Clip(%v) = %v, want %v", s1, s2, s1)
 829         }
 830         if cap(s2) != 3 {
 831                 t.Errorf("cap(Clip(%v)) = %d, want 3", orig, cap(s2))
 832         }
 833 }
 834
 835 func TestReverse(t *testing.T) {
 836         even := []int{3, 1, 4, 1, 5, 9} // len = 6
 837         Reverse(even)
 838         if want := []int{9, 5, 1, 4, 1, 3}; !Equal(even, want) {
 839                 t.Errorf("Reverse(even) = %v, want %v", even, want)
 840         }
 841
 842         odd := []int{3, 1, 4, 1, 5, 9, 2} // len = 7
 843         Reverse(odd)
 844         if want := []int{2, 9, 5, 1, 4, 1, 3}; !Equal(odd, want) {
 845                 t.Errorf("Reverse(odd) = %v, want %v", odd, want)
 846         }
 847
 848         words := strings.Fields("one two three")
 849         Reverse(words)
 850         if want := strings.Fields("three two one"); !Equal(words, want) {
 851                 t.Errorf("Reverse(words) = %v, want %v", words, want)
 852         }
 853
 854         singleton := []string{"one"}
 855         Reverse(singleton)
 856         if want := []string{"one"}; !Equal(singleton, want) {
 857                 t.Errorf("Reverse(singeleton) = %v, want %v", singleton, want)
 858         }
 859
 860         Reverse[[]string](nil)
 861 }
 862
 863 // naiveReplace is a baseline implementation to the Replace function.
 864 func naiveReplace[S ~[]E, E any](s S, i, j int, v ...E) S {
 865         s = Delete(s, i, j)
 866         s = Insert(s, i, v...)
 867         return s
 868 }
 869
 870 func TestReplace(t *testing.T) {
 871         for _, test := range []struct {
 872                 s, v []int
 873                 i, j int
 874         }{
 875                 {}, // all zero value
 876                 {
 877                         s: []int{1, 2, 3, 4},
 878                         v: []int{5},
 879                         i: 1,
 880                         j: 2,
 881                 },
 882                 {
 883                         s: []int{1, 2, 3, 4},
 884                         v: []int{5, 6, 7, 8},
 885                         i: 1,
 886                         j: 2,
 887                 },
 888                 {
 889                         s: func() []int {
 890                                 s := make([]int, 3, 20)
 891                                 s[0] = 0
 892                                 s[1] = 1
 893                                 s[2] = 2
 894                                 return s
 895                         }(),
 896                         v: []int{3, 4, 5, 6, 7},
 897                         i: 0,
 898                         j: 1,
 899                 },
 900         } {
 901                 ss, vv := Clone(test.s), Clone(test.v)
 902                 want := naiveReplace(ss, test.i, test.j, vv...)
 903                 got := Replace(test.s, test.i, test.j, test.v...)
 904                 if !Equal(got, want) {
 905                         t.Errorf("Replace(%v, %v, %v, %v) = %v, want %v", test.s, test.i, test.j, test.v, got, want)
 906                 }
 907         }
 908 }
 909
 910 func TestReplacePanics(t *testing.T) {
 911         for _, test := range []struct {
 912                 name string
 913                 s, v []int
 914                 i, j int
 915         }{
 916                 {"indexes out of order", []int{1, 2}, []int{3}, 2, 1},
 917                 {"large index", []int{1, 2}, []int{3}, 1, 10},
 918                 {"negative index", []int{1, 2}, []int{3}, -1, 2},
 919         } {
 920                 ss, vv := Clone(test.s), Clone(test.v)
 921                 if !panics(func() { Replace(ss, test.i, test.j, vv...) }) {
 922                         t.Errorf("Replace %s: should have panicked", test.name)
 923                 }
 924         }
 925 }
 926
 927 func TestReplaceOverlap(t *testing.T) {
 928         const N = 10
 929         a := make([]int, N)
 930         want := make([]int, 2*N)
 931         for n := 0; n <= N; n++ { // length
 932                 for i := 0; i <= n; i++ { // insertion point 1
 933                         for j := i; j <= n; j++ { // insertion point 2
 934                                 for x := 0; x <= N; x++ { // start of inserted data
 935                                         for y := x; y <= N; y++ { // end of inserted data
 936                                                 for k := 0; k < N; k++ {
 937                                                         a[k] = k
 938                                                 }
 939                                                 want = want[:0]
 940                                                 want = append(want, a[:i]...)
 941                                                 want = append(want, a[x:y]...)
 942                                                 want = append(want, a[j:n]...)
 943                                                 got := Replace(a[:n], i, j, a[x:y]...)
 944                                                 if !Equal(got, want) {
 945                                                         t.Errorf("Insert with overlap failed n=%d i=%d j=%d x=%d y=%d, got %v want %v", n, i, j, x, y, got, want)
 946                                                 }
 947                                         }
 948                                 }
 949                         }
 950                 }
 951         }
 952 }
 953
 954 func BenchmarkReplace(b *testing.B) {
 955         cases := []struct {
 956                 name string
 957                 s, v func() []int
 958                 i, j int
 959         }{
 960                 {
 961                         name: "fast",
 962                         s: func() []int {
 963                                 return make([]int, 100)
 964                         },
 965                         v: func() []int {
 966                                 return make([]int, 20)
 967                         },
 968                         i: 10,
 969                         j: 40,
 970                 },
 971                 {
 972                         name: "slow",
 973                         s: func() []int {
 974                                 return make([]int, 100)
 975                         },
 976                         v: func() []int {
 977                                 return make([]int, 20)
 978                         },
 979                         i: 0,
 980                         j: 2,
 981                 },
 982         }
 983
 984         for _, c := range cases {
 985                 b.Run("naive-"+c.name, func(b *testing.B) {
 986                         for k := 0; k < b.N; k++ {
 987                                 s := c.s()
 988                                 v := c.v()
 989                                 _ = naiveReplace(s, c.i, c.j, v...)
 990                         }
 991                 })
 992                 b.Run("optimized-"+c.name, func(b *testing.B) {
 993                         for k := 0; k < b.N; k++ {
 994                                 s := c.s()
 995                                 v := c.v()
 996                                 _ = Replace(s, c.i, c.j, v...)
 997                         }
 998                 })
 999         }
1000
1001 }
1002
1003 func TestInsertGrowthRate(t *testing.T) {
1004         b := make([]byte, 1)
1005         maxCap := cap(b)
1006         nGrow := 0
1007         const N = 1e6
1008         for i := 0; i < N; i++ {
1009                 b = Insert(b, len(b)-1, 0)
1010                 if cap(b) > maxCap {
1011                         maxCap = cap(b)
1012                         nGrow++
1013                 }
1014         }
1015         want := int(math.Log(N) / math.Log(1.25)) // 1.25 == growth rate for large slices
1016         if nGrow > want {
1017                 t.Errorf("too many grows. got:%d want:%d", nGrow, want)
1018         }
1019 }
1020
1021 func TestReplaceGrowthRate(t *testing.T) {
1022         b := make([]byte, 2)
1023         maxCap := cap(b)
1024         nGrow := 0
1025         const N = 1e6
1026         for i := 0; i < N; i++ {
1027                 b = Replace(b, len(b)-2, len(b)-1, 0, 0)
1028                 if cap(b) > maxCap {
1029                         maxCap = cap(b)
1030                         nGrow++
1031                 }
1032         }
1033         want := int(math.Log(N) / math.Log(1.25)) // 1.25 == growth rate for large slices
1034         if nGrow > want {
1035                 t.Errorf("too many grows. got:%d want:%d", nGrow, want)
1036         }
1037 }
1038
1039 func apply[T any](v T, f func(T)) {
1040         f(v)
1041 }
1042
1043 // Test type inference with a named slice type.
1044 func TestInference(t *testing.T) {
1045         s1 := []int{1, 2, 3}
1046         apply(s1, Reverse)
1047         if want := []int{3, 2, 1}; !Equal(s1, want) {
1048                 t.Errorf("Reverse(%v) = %v, want %v", []int{1, 2, 3}, s1, want)
1049         }
1050
1051         type S []int
1052         s2 := S{4, 5, 6}
1053         apply(s2, Reverse)
1054         if want := (S{6, 5, 4}); !Equal(s2, want) {
1055                 t.Errorf("Reverse(%v) = %v, want %v", S{4, 5, 6}, s2, want)
1056         }
1057 }