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