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 func TestInsertPanics(t *testing.T) {
 540         a := [3]int{}
 541         for _, test := range []struct {
 542                 name string
 543                 s    []int
 544                 i    int
 545                 v    []int
 546         }{
 547                 // There are no values.
 548                 {"with negative index", a[:1:1], -1, nil},
 549                 {"with out-of-bounds index and > cap", a[:1:1], 2, nil},
 550                 {"with out-of-bounds index and = cap", a[:1:2], 2, nil},
 551                 {"with out-of-bounds index and < cap", a[:1:3], 2, nil},
 552         } {
 553                 if !panics(func() { Insert(test.s, test.i, test.v...) }) {
 554                         t.Errorf("Insert %s: got no panic, want panic", test.name)
 555                 }
 556         }
 557 }
 558
 559 var deleteTests = []struct {
 560         s    []int
 561         i, j int
 562         want []int
 563 }{
 564         {
 565                 []int{1, 2, 3},
 566                 0,
 567                 0,
 568                 []int{1, 2, 3},
 569         },
 570         {
 571                 []int{1, 2, 3},
 572                 0,
 573                 1,
 574                 []int{2, 3},
 575         },
 576         {
 577                 []int{1, 2, 3},
 578                 3,
 579                 3,
 580                 []int{1, 2, 3},
 581         },
 582         {
 583                 []int{1, 2, 3},
 584                 0,
 585                 2,
 586                 []int{3},
 587         },
 588         {
 589                 []int{1, 2, 3},
 590                 0,
 591                 3,
 592                 []int{},
 593         },
 594 }
 595
 596 func TestDelete(t *testing.T) {
 597         for _, test := range deleteTests {
 598                 copy := Clone(test.s)
 599                 if got := Delete(copy, test.i, test.j); !Equal(got, test.want) {
 600                         t.Errorf("Delete(%v, %d, %d) = %v, want %v", test.s, test.i, test.j, got, test.want)
 601                 }
 602         }
 603 }
 604
 605 var deleteFuncTests = []struct {
 606         s    []int
 607         fn   func(int) bool
 608         want []int
 609 }{
 610         {
 611                 nil,
 612                 func(int) bool { return true },
 613                 nil,
 614         },
 615         {
 616                 []int{1, 2, 3},
 617                 func(int) bool { return true },
 618                 nil,
 619         },
 620         {
 621                 []int{1, 2, 3},
 622                 func(int) bool { return false },
 623                 []int{1, 2, 3},
 624         },
 625         {
 626                 []int{1, 2, 3},
 627                 func(i int) bool { return i > 2 },
 628                 []int{1, 2},
 629         },
 630         {
 631                 []int{1, 2, 3},
 632                 func(i int) bool { return i < 2 },
 633                 []int{2, 3},
 634         },
 635         {
 636                 []int{10, 2, 30},
 637                 func(i int) bool { return i >= 10 },
 638                 []int{2},
 639         },
 640 }
 641
 642 func TestDeleteFunc(t *testing.T) {
 643         for i, test := range deleteFuncTests {
 644                 copy := Clone(test.s)
 645                 if got := DeleteFunc(copy, test.fn); !Equal(got, test.want) {
 646                         t.Errorf("DeleteFunc case %d: got %v, want %v", i, got, test.want)
 647                 }
 648         }
 649 }
 650
 651 func panics(f func()) (b bool) {
 652         defer func() {
 653                 if x := recover(); x != nil {
 654                         b = true
 655                 }
 656         }()
 657         f()
 658         return false
 659 }
 660
 661 func TestDeletePanics(t *testing.T) {
 662         for _, test := range []struct {
 663                 name string
 664                 s    []int
 665                 i, j int
 666         }{
 667                 {"with negative first index", []int{42}, -2, 1},
 668                 {"with negative second index", []int{42}, 1, -1},
 669                 {"with out-of-bounds first index", []int{42}, 2, 3},
 670                 {"with out-of-bounds second index", []int{42}, 0, 2},
 671                 {"with invalid i>j", []int{42}, 1, 0},
 672         } {
 673                 if !panics(func() { Delete(test.s, test.i, test.j) }) {
 674                         t.Errorf("Delete %s: got no panic, want panic", test.name)
 675                 }
 676         }
 677 }
 678
 679 func TestClone(t *testing.T) {
 680         s1 := []int{1, 2, 3}
 681         s2 := Clone(s1)
 682         if !Equal(s1, s2) {
 683                 t.Errorf("Clone(%v) = %v, want %v", s1, s2, s1)
 684         }
 685         s1[0] = 4
 686         want := []int{1, 2, 3}
 687         if !Equal(s2, want) {
 688                 t.Errorf("Clone(%v) changed unexpectedly to %v", want, s2)
 689         }
 690         if got := Clone([]int(nil)); got != nil {
 691                 t.Errorf("Clone(nil) = %#v, want nil", got)
 692         }
 693         if got := Clone(s1[:0]); got == nil || len(got) != 0 {
 694                 t.Errorf("Clone(%v) = %#v, want %#v", s1[:0], got, s1[:0])
 695         }
 696 }
 697
 698 var compactTests = []struct {
 699         name string
 700         s    []int
 701         want []int
 702 }{
 703         {
 704                 "nil",
 705                 nil,
 706                 nil,
 707         },
 708         {
 709                 "one",
 710                 []int{1},
 711                 []int{1},
 712         },
 713         {
 714                 "sorted",
 715                 []int{1, 2, 3},
 716                 []int{1, 2, 3},
 717         },
 718         {
 719                 "1 item",
 720                 []int{1, 1, 2},
 721                 []int{1, 2},
 722         },
 723         {
 724                 "unsorted",
 725                 []int{1, 2, 1},
 726                 []int{1, 2, 1},
 727         },
 728         {
 729                 "many",
 730                 []int{1, 2, 2, 3, 3, 4},
 731                 []int{1, 2, 3, 4},
 732         },
 733 }
 734
 735 func TestCompact(t *testing.T) {
 736         for _, test := range compactTests {
 737                 copy := Clone(test.s)
 738                 if got := Compact(copy); !Equal(got, test.want) {
 739                         t.Errorf("Compact(%v) = %v, want %v", test.s, got, test.want)
 740                 }
 741         }
 742 }
 743
 744 func BenchmarkCompact(b *testing.B) {
 745         for _, c := range compactTests {
 746                 b.Run(c.name, func(b *testing.B) {
 747                         ss := make([]int, 0, 64)
 748                         for k := 0; k < b.N; k++ {
 749                                 ss = ss[:0]
 750                                 ss = append(ss, c.s...)
 751                                 _ = Compact(ss)
 752                         }
 753                 })
 754         }
 755 }
 756
 757 func BenchmarkCompact_Large(b *testing.B) {
 758         type Large [4 * 1024]byte
 759
 760         ss := make([]Large, 1024)
 761         for i := 0; i < b.N; i++ {
 762                 _ = Compact(ss)
 763         }
 764 }
 765
 766 func TestCompactFunc(t *testing.T) {
 767         for _, test := range compactTests {
 768                 copy := Clone(test.s)
 769                 if got := CompactFunc(copy, equal[int]); !Equal(got, test.want) {
 770                         t.Errorf("CompactFunc(%v, equal[int]) = %v, want %v", test.s, got, test.want)
 771                 }
 772         }
 773
 774         s1 := []string{"a", "a", "A", "B", "b"}
 775         copy := Clone(s1)
 776         want := []string{"a", "B"}
 777         if got := CompactFunc(copy, strings.EqualFold); !Equal(got, want) {
 778                 t.Errorf("CompactFunc(%v, strings.EqualFold) = %v, want %v", s1, got, want)
 779         }
 780 }
 781
 782 func BenchmarkCompactFunc_Large(b *testing.B) {
 783         type Large [4 * 1024]byte
 784
 785         ss := make([]Large, 1024)
 786         for i := 0; i < b.N; i++ {
 787                 _ = CompactFunc(ss, func(a, b Large) bool { return a == b })
 788         }
 789 }
 790
 791 func TestGrow(t *testing.T) {
 792         s1 := []int{1, 2, 3}
 793
 794         copy := Clone(s1)
 795         s2 := Grow(copy, 1000)
 796         if !Equal(s1, s2) {
 797                 t.Errorf("Grow(%v) = %v, want %v", s1, s2, s1)
 798         }
 799         if cap(s2) < 1000+len(s1) {
 800                 t.Errorf("after Grow(%v) cap = %d, want >= %d", s1, cap(s2), 1000+len(s1))
 801         }
 802
 803         // Test mutation of elements between length and capacity.
 804         copy = Clone(s1)
 805         s3 := Grow(copy[:1], 2)[:3]
 806         if !Equal(s1, s3) {
 807                 t.Errorf("Grow should not mutate elements between length and capacity")
 808         }
 809         s3 = Grow(copy[:1], 1000)[:3]
 810         if !Equal(s1, s3) {
 811                 t.Errorf("Grow should not mutate elements between length and capacity")
 812         }
 813
 814         // Test number of allocations.
 815         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)) }); n != 0 {
 816                 t.Errorf("Grow should not allocate when given sufficient capacity; allocated %v times", n)
 817         }
 818         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)+1) }); n != 1 {
 819                 errorf := t.Errorf
 820                 if race.Enabled || testenv.OptimizationOff() {
 821                         errorf = t.Logf // this allocates multiple times in race detector mode
 822                 }
 823                 errorf("Grow should allocate once when given insufficient capacity; allocated %v times", n)
 824         }
 825
 826         // Test for negative growth sizes.
 827         var gotPanic bool
 828         func() {
 829                 defer func() { gotPanic = recover() != nil }()
 830                 Grow(s1, -1)
 831         }()
 832         if !gotPanic {
 833                 t.Errorf("Grow(-1) did not panic; expected a panic")
 834         }
 835 }
 836
 837 func TestClip(t *testing.T) {
 838         s1 := []int{1, 2, 3, 4, 5, 6}[:3]
 839         orig := Clone(s1)
 840         if len(s1) != 3 {
 841                 t.Errorf("len(%v) = %d, want 3", s1, len(s1))
 842         }
 843         if cap(s1) < 6 {
 844                 t.Errorf("cap(%v[:3]) = %d, want >= 6", orig, cap(s1))
 845         }
 846         s2 := Clip(s1)
 847         if !Equal(s1, s2) {
 848                 t.Errorf("Clip(%v) = %v, want %v", s1, s2, s1)
 849         }
 850         if cap(s2) != 3 {
 851                 t.Errorf("cap(Clip(%v)) = %d, want 3", orig, cap(s2))
 852         }
 853 }
 854
 855 func TestReverse(t *testing.T) {
 856         even := []int{3, 1, 4, 1, 5, 9} // len = 6
 857         Reverse(even)
 858         if want := []int{9, 5, 1, 4, 1, 3}; !Equal(even, want) {
 859                 t.Errorf("Reverse(even) = %v, want %v", even, want)
 860         }
 861
 862         odd := []int{3, 1, 4, 1, 5, 9, 2} // len = 7
 863         Reverse(odd)
 864         if want := []int{2, 9, 5, 1, 4, 1, 3}; !Equal(odd, want) {
 865                 t.Errorf("Reverse(odd) = %v, want %v", odd, want)
 866         }
 867
 868         words := strings.Fields("one two three")
 869         Reverse(words)
 870         if want := strings.Fields("three two one"); !Equal(words, want) {
 871                 t.Errorf("Reverse(words) = %v, want %v", words, want)
 872         }
 873
 874         singleton := []string{"one"}
 875         Reverse(singleton)
 876         if want := []string{"one"}; !Equal(singleton, want) {
 877                 t.Errorf("Reverse(singeleton) = %v, want %v", singleton, want)
 878         }
 879
 880         Reverse[[]string](nil)
 881 }
 882
 883 // naiveReplace is a baseline implementation to the Replace function.
 884 func naiveReplace[S ~[]E, E any](s S, i, j int, v ...E) S {
 885         s = Delete(s, i, j)
 886         s = Insert(s, i, v...)
 887         return s
 888 }
 889
 890 func TestReplace(t *testing.T) {
 891         for _, test := range []struct {
 892                 s, v []int
 893                 i, j int
 894         }{
 895                 {}, // all zero value
 896                 {
 897                         s: []int{1, 2, 3, 4},
 898                         v: []int{5},
 899                         i: 1,
 900                         j: 2,
 901                 },
 902                 {
 903                         s: []int{1, 2, 3, 4},
 904                         v: []int{5, 6, 7, 8},
 905                         i: 1,
 906                         j: 2,
 907                 },
 908                 {
 909                         s: func() []int {
 910                                 s := make([]int, 3, 20)
 911                                 s[0] = 0
 912                                 s[1] = 1
 913                                 s[2] = 2
 914                                 return s
 915                         }(),
 916                         v: []int{3, 4, 5, 6, 7},
 917                         i: 0,
 918                         j: 1,
 919                 },
 920         } {
 921                 ss, vv := Clone(test.s), Clone(test.v)
 922                 want := naiveReplace(ss, test.i, test.j, vv...)
 923                 got := Replace(test.s, test.i, test.j, test.v...)
 924                 if !Equal(got, want) {
 925                         t.Errorf("Replace(%v, %v, %v, %v) = %v, want %v", test.s, test.i, test.j, test.v, got, want)
 926                 }
 927         }
 928 }
 929
 930 func TestReplacePanics(t *testing.T) {
 931         for _, test := range []struct {
 932                 name string
 933                 s, v []int
 934                 i, j int
 935         }{
 936                 {"indexes out of order", []int{1, 2}, []int{3}, 2, 1},
 937                 {"large index", []int{1, 2}, []int{3}, 1, 10},
 938                 {"negative index", []int{1, 2}, []int{3}, -1, 2},
 939         } {
 940                 ss, vv := Clone(test.s), Clone(test.v)
 941                 if !panics(func() { Replace(ss, test.i, test.j, vv...) }) {
 942                         t.Errorf("Replace %s: should have panicked", test.name)
 943                 }
 944         }
 945 }
 946
 947 func TestReplaceOverlap(t *testing.T) {
 948         const N = 10
 949         a := make([]int, N)
 950         want := make([]int, 2*N)
 951         for n := 0; n <= N; n++ { // length
 952                 for i := 0; i <= n; i++ { // insertion point 1
 953                         for j := i; j <= n; j++ { // insertion point 2
 954                                 for x := 0; x <= N; x++ { // start of inserted data
 955                                         for y := x; y <= N; y++ { // end of inserted data
 956                                                 for k := 0; k < N; k++ {
 957                                                         a[k] = k
 958                                                 }
 959                                                 want = want[:0]
 960                                                 want = append(want, a[:i]...)
 961                                                 want = append(want, a[x:y]...)
 962                                                 want = append(want, a[j:n]...)
 963                                                 got := Replace(a[:n], i, j, a[x:y]...)
 964                                                 if !Equal(got, want) {
 965                                                         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)
 966                                                 }
 967                                         }
 968                                 }
 969                         }
 970                 }
 971         }
 972 }
 973
 974 func BenchmarkReplace(b *testing.B) {
 975         cases := []struct {
 976                 name string
 977                 s, v func() []int
 978                 i, j int
 979         }{
 980                 {
 981                         name: "fast",
 982                         s: func() []int {
 983                                 return make([]int, 100)
 984                         },
 985                         v: func() []int {
 986                                 return make([]int, 20)
 987                         },
 988                         i: 10,
 989                         j: 40,
 990                 },
 991                 {
 992                         name: "slow",
 993                         s: func() []int {
 994                                 return make([]int, 100)
 995                         },
 996                         v: func() []int {
 997                                 return make([]int, 20)
 998                         },
 999                         i: 0,
1000                         j: 2,
1001                 },
1002         }
1003
1004         for _, c := range cases {
1005                 b.Run("naive-"+c.name, func(b *testing.B) {
1006                         for k := 0; k < b.N; k++ {
1007                                 s := c.s()
1008                                 v := c.v()
1009                                 _ = naiveReplace(s, c.i, c.j, v...)
1010                         }
1011                 })
1012                 b.Run("optimized-"+c.name, func(b *testing.B) {
1013                         for k := 0; k < b.N; k++ {
1014                                 s := c.s()
1015                                 v := c.v()
1016                                 _ = Replace(s, c.i, c.j, v...)
1017                         }
1018                 })
1019         }
1020
1021 }
1022
1023 func TestInsertGrowthRate(t *testing.T) {
1024         b := make([]byte, 1)
1025         maxCap := cap(b)
1026         nGrow := 0
1027         const N = 1e6
1028         for i := 0; i < N; i++ {
1029                 b = Insert(b, len(b)-1, 0)
1030                 if cap(b) > maxCap {
1031                         maxCap = cap(b)
1032                         nGrow++
1033                 }
1034         }
1035         want := int(math.Log(N) / math.Log(1.25)) // 1.25 == growth rate for large slices
1036         if nGrow > want {
1037                 t.Errorf("too many grows. got:%d want:%d", nGrow, want)
1038         }
1039 }
1040
1041 func TestReplaceGrowthRate(t *testing.T) {
1042         b := make([]byte, 2)
1043         maxCap := cap(b)
1044         nGrow := 0
1045         const N = 1e6
1046         for i := 0; i < N; i++ {
1047                 b = Replace(b, len(b)-2, len(b)-1, 0, 0)
1048                 if cap(b) > maxCap {
1049                         maxCap = cap(b)
1050                         nGrow++
1051                 }
1052         }
1053         want := int(math.Log(N) / math.Log(1.25)) // 1.25 == growth rate for large slices
1054         if nGrow > want {
1055                 t.Errorf("too many grows. got:%d want:%d", nGrow, want)
1056         }
1057 }
1058
1059 func apply[T any](v T, f func(T)) {
1060         f(v)
1061 }
1062
1063 // Test type inference with a named slice type.
1064 func TestInference(t *testing.T) {
1065         s1 := []int{1, 2, 3}
1066         apply(s1, Reverse)
1067         if want := []int{3, 2, 1}; !Equal(s1, want) {
1068                 t.Errorf("Reverse(%v) = %v, want %v", []int{1, 2, 3}, s1, want)
1069         }
1070
1071         type S []int
1072         s2 := S{4, 5, 6}
1073         apply(s2, Reverse)
1074         if want := (S{6, 5, 4}); !Equal(s2, want) {
1075                 t.Errorf("Reverse(%v) = %v, want %v", S{4, 5, 6}, s2, want)
1076         }
1077 }
1078
1079 func TestConcat(t *testing.T) {
1080         cases := []struct {
1081                 s    [][]int
1082                 want []int
1083         }{
1084                 {
1085                         s:    [][]int{nil},
1086                         want: nil,
1087                 },
1088                 {
1089                         s:    [][]int{{1}},
1090                         want: []int{1},
1091                 },
1092                 {
1093                         s:    [][]int{{1}, {2}},
1094                         want: []int{1, 2},
1095                 },
1096                 {
1097                         s:    [][]int{{1}, nil, {2}},
1098                         want: []int{1, 2},
1099                 },
1100         }
1101         for _, tc := range cases {
1102                 got := Concat(tc.s...)
1103                 if !Equal(tc.want, got) {
1104                         t.Errorf("Concat(%v) = %v, want %v", tc.s, got, tc.want)
1105                 }
1106                 var sink []int
1107                 allocs := testing.AllocsPerRun(5, func() {
1108                         sink = Concat(tc.s...)
1109                 })
1110                 _ = sink
1111                 if allocs > 1 {
1112                         errorf := t.Errorf
1113                         if testenv.OptimizationOff() || race.Enabled {
1114                                 errorf = t.Logf
1115                         }
1116                         errorf("Concat(%v) allocated %v times; want 1", tc.s, allocs)
1117                 }
1118         }
1119 }
1120
1121 func TestConcat_too_large(t *testing.T) {
1122         // Use zero length element to minimize memory in testing
1123         type void struct{}
1124         cases := []struct {
1125                 lengths     []int
1126                 shouldPanic bool
1127         }{
1128                 {
1129                         lengths:     []int{0, 0},
1130                         shouldPanic: false,
1131                 },
1132                 {
1133                         lengths:     []int{math.MaxInt, 0},
1134                         shouldPanic: false,
1135                 },
1136                 {
1137                         lengths:     []int{0, math.MaxInt},
1138                         shouldPanic: false,
1139                 },
1140                 {
1141                         lengths:     []int{math.MaxInt - 1, 1},
1142                         shouldPanic: false,
1143                 },
1144                 {
1145                         lengths:     []int{math.MaxInt - 1, 1, 1},
1146                         shouldPanic: true,
1147                 },
1148                 {
1149                         lengths:     []int{math.MaxInt, 1},
1150                         shouldPanic: true,
1151                 },
1152                 {
1153                         lengths:     []int{math.MaxInt, math.MaxInt},
1154                         shouldPanic: true,
1155                 },
1156         }
1157         for _, tc := range cases {
1158                 var r any
1159                 ss := make([][]void, 0, len(tc.lengths))
1160                 for _, l := range tc.lengths {
1161                         s := make([]void, l)
1162                         ss = append(ss, s)
1163                 }
1164                 func() {
1165                         defer func() {
1166                                 r = recover()
1167                         }()
1168                         _ = Concat(ss...)
1169                 }()
1170                 if didPanic := r != nil; didPanic != tc.shouldPanic {
1171                         t.Errorf("slices.Concat(lens(%v)) got panic == %v",
1172                                 tc.lengths, didPanic)
1173                 }
1174         }
1175 }