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 TestDeleteClearTail(t *testing.T) {
 685         mem := []*int{new(int), new(int), new(int), new(int), new(int), new(int)}
 686         s := mem[0:5] // there is 1 element beyond len(s), within cap(s)
 687
 688         s = Delete(s, 2, 4)
 689
 690         if mem[3] != nil || mem[4] != nil {
 691                 // Check that potential memory leak is avoided
 692                 t.Errorf("Delete: want nil discarded elements, got %v, %v", mem[3], mem[4])
 693         }
 694         if mem[5] == nil {
 695                 t.Errorf("Delete: want unchanged elements beyond original len, got nil")
 696         }
 697 }
 698
 699 func TestDeleteFuncClearTail(t *testing.T) {
 700         mem := []*int{new(int), new(int), new(int), new(int), new(int), new(int)}
 701         *mem[2], *mem[3] = 42, 42
 702         s := mem[0:5] // there is 1 element beyond len(s), within cap(s)
 703
 704         s = DeleteFunc(s, func(i *int) bool {
 705                 return i != nil && *i == 42
 706         })
 707
 708         if mem[3] != nil || mem[4] != nil {
 709                 // Check that potential memory leak is avoided
 710                 t.Errorf("DeleteFunc: want nil discarded elements, got %v, %v", mem[3], mem[4])
 711         }
 712         if mem[5] == nil {
 713                 t.Errorf("DeleteFunc: want unchanged elements beyond original len, got nil")
 714         }
 715 }
 716
 717 func TestClone(t *testing.T) {
 718         s1 := []int{1, 2, 3}
 719         s2 := Clone(s1)
 720         if !Equal(s1, s2) {
 721                 t.Errorf("Clone(%v) = %v, want %v", s1, s2, s1)
 722         }
 723         s1[0] = 4
 724         want := []int{1, 2, 3}
 725         if !Equal(s2, want) {
 726                 t.Errorf("Clone(%v) changed unexpectedly to %v", want, s2)
 727         }
 728         if got := Clone([]int(nil)); got != nil {
 729                 t.Errorf("Clone(nil) = %#v, want nil", got)
 730         }
 731         if got := Clone(s1[:0]); got == nil || len(got) != 0 {
 732                 t.Errorf("Clone(%v) = %#v, want %#v", s1[:0], got, s1[:0])
 733         }
 734 }
 735
 736 var compactTests = []struct {
 737         name string
 738         s    []int
 739         want []int
 740 }{
 741         {
 742                 "nil",
 743                 nil,
 744                 nil,
 745         },
 746         {
 747                 "one",
 748                 []int{1},
 749                 []int{1},
 750         },
 751         {
 752                 "sorted",
 753                 []int{1, 2, 3},
 754                 []int{1, 2, 3},
 755         },
 756         {
 757                 "1 item",
 758                 []int{1, 1, 2},
 759                 []int{1, 2},
 760         },
 761         {
 762                 "unsorted",
 763                 []int{1, 2, 1},
 764                 []int{1, 2, 1},
 765         },
 766         {
 767                 "many",
 768                 []int{1, 2, 2, 3, 3, 4},
 769                 []int{1, 2, 3, 4},
 770         },
 771 }
 772
 773 func TestCompact(t *testing.T) {
 774         for _, test := range compactTests {
 775                 copy := Clone(test.s)
 776                 if got := Compact(copy); !Equal(got, test.want) {
 777                         t.Errorf("Compact(%v) = %v, want %v", test.s, got, test.want)
 778                 }
 779         }
 780 }
 781
 782 func BenchmarkCompact(b *testing.B) {
 783         for _, c := range compactTests {
 784                 b.Run(c.name, func(b *testing.B) {
 785                         ss := make([]int, 0, 64)
 786                         for k := 0; k < b.N; k++ {
 787                                 ss = ss[:0]
 788                                 ss = append(ss, c.s...)
 789                                 _ = Compact(ss)
 790                         }
 791                 })
 792         }
 793 }
 794
 795 func BenchmarkCompact_Large(b *testing.B) {
 796         type Large [4 * 1024]byte
 797
 798         ss := make([]Large, 1024)
 799         for i := 0; i < b.N; i++ {
 800                 _ = Compact(ss)
 801         }
 802 }
 803
 804 func TestCompactFunc(t *testing.T) {
 805         for _, test := range compactTests {
 806                 copy := Clone(test.s)
 807                 if got := CompactFunc(copy, equal[int]); !Equal(got, test.want) {
 808                         t.Errorf("CompactFunc(%v, equal[int]) = %v, want %v", test.s, got, test.want)
 809                 }
 810         }
 811
 812         s1 := []string{"a", "a", "A", "B", "b"}
 813         copy := Clone(s1)
 814         want := []string{"a", "B"}
 815         if got := CompactFunc(copy, strings.EqualFold); !Equal(got, want) {
 816                 t.Errorf("CompactFunc(%v, strings.EqualFold) = %v, want %v", s1, got, want)
 817         }
 818 }
 819
 820 func TestCompactClearTail(t *testing.T) {
 821         one, two, three, four := 1, 2, 3, 4
 822         mem := []*int{&one, &one, &two, &two, &three, &four}
 823         s := mem[0:5] // there is 1 element beyond len(s), within cap(s)
 824         copy := Clone(s)
 825
 826         s = Compact(s)
 827
 828         if want := []*int{&one, &two, &three}; !Equal(s, want) {
 829                 t.Errorf("Compact(%v) = %v, want %v", copy, s, want)
 830         }
 831
 832         if mem[3] != nil || mem[4] != nil {
 833                 // Check that potential memory leak is avoided
 834                 t.Errorf("Compact: want nil discarded elements, got %v, %v", mem[3], mem[4])
 835         }
 836         if mem[5] != &four {
 837                 t.Errorf("Compact: want unchanged element beyond original len, got %v", mem[5])
 838         }
 839 }
 840
 841 func TestCompactFuncClearTail(t *testing.T) {
 842         a, b, c, d, e, f := 1, 1, 2, 2, 3, 4
 843         mem := []*int{&a, &b, &c, &d, &e, &f}
 844         s := mem[0:5] // there is 1 element beyond len(s), within cap(s)
 845         copy := Clone(s)
 846
 847         s = CompactFunc(s, func(x, y *int) bool {
 848                 if x == nil || y == nil {
 849                         return x == y
 850                 }
 851                 return *x == *y
 852         })
 853
 854         if want := []*int{&a, &c, &e}; !Equal(s, want) {
 855                 t.Errorf("CompactFunc(%v) = %v, want %v", copy, s, want)
 856         }
 857
 858         if mem[3] != nil || mem[4] != nil {
 859                 // Check that potential memory leak is avoided
 860                 t.Errorf("CompactFunc: want nil discarded elements, got %v, %v", mem[3], mem[4])
 861         }
 862         if mem[5] != &f {
 863                 t.Errorf("CompactFunc: want unchanged elements beyond original len, got %v", mem[5])
 864         }
 865 }
 866
 867 func BenchmarkCompactFunc_Large(b *testing.B) {
 868         type Large [4 * 1024]byte
 869
 870         ss := make([]Large, 1024)
 871         for i := 0; i < b.N; i++ {
 872                 _ = CompactFunc(ss, func(a, b Large) bool { return a == b })
 873         }
 874 }
 875
 876 func TestGrow(t *testing.T) {
 877         s1 := []int{1, 2, 3}
 878
 879         copy := Clone(s1)
 880         s2 := Grow(copy, 1000)
 881         if !Equal(s1, s2) {
 882                 t.Errorf("Grow(%v) = %v, want %v", s1, s2, s1)
 883         }
 884         if cap(s2) < 1000+len(s1) {
 885                 t.Errorf("after Grow(%v) cap = %d, want >= %d", s1, cap(s2), 1000+len(s1))
 886         }
 887
 888         // Test mutation of elements between length and capacity.
 889         copy = Clone(s1)
 890         s3 := Grow(copy[:1], 2)[:3]
 891         if !Equal(s1, s3) {
 892                 t.Errorf("Grow should not mutate elements between length and capacity")
 893         }
 894         s3 = Grow(copy[:1], 1000)[:3]
 895         if !Equal(s1, s3) {
 896                 t.Errorf("Grow should not mutate elements between length and capacity")
 897         }
 898
 899         // Test number of allocations.
 900         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)) }); n != 0 {
 901                 t.Errorf("Grow should not allocate when given sufficient capacity; allocated %v times", n)
 902         }
 903         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)+1) }); n != 1 {
 904                 errorf := t.Errorf
 905                 if race.Enabled || testenv.OptimizationOff() {
 906                         errorf = t.Logf // this allocates multiple times in race detector mode
 907                 }
 908                 errorf("Grow should allocate once when given insufficient capacity; allocated %v times", n)
 909         }
 910
 911         // Test for negative growth sizes.
 912         var gotPanic bool
 913         func() {
 914                 defer func() { gotPanic = recover() != nil }()
 915                 Grow(s1, -1)
 916         }()
 917         if !gotPanic {
 918                 t.Errorf("Grow(-1) did not panic; expected a panic")
 919         }
 920 }
 921
 922 func TestClip(t *testing.T) {
 923         s1 := []int{1, 2, 3, 4, 5, 6}[:3]
 924         orig := Clone(s1)
 925         if len(s1) != 3 {
 926                 t.Errorf("len(%v) = %d, want 3", s1, len(s1))
 927         }
 928         if cap(s1) < 6 {
 929                 t.Errorf("cap(%v[:3]) = %d, want >= 6", orig, cap(s1))
 930         }
 931         s2 := Clip(s1)
 932         if !Equal(s1, s2) {
 933                 t.Errorf("Clip(%v) = %v, want %v", s1, s2, s1)
 934         }
 935         if cap(s2) != 3 {
 936                 t.Errorf("cap(Clip(%v)) = %d, want 3", orig, cap(s2))
 937         }
 938 }
 939
 940 func TestReverse(t *testing.T) {
 941         even := []int{3, 1, 4, 1, 5, 9} // len = 6
 942         Reverse(even)
 943         if want := []int{9, 5, 1, 4, 1, 3}; !Equal(even, want) {
 944                 t.Errorf("Reverse(even) = %v, want %v", even, want)
 945         }
 946
 947         odd := []int{3, 1, 4, 1, 5, 9, 2} // len = 7
 948         Reverse(odd)
 949         if want := []int{2, 9, 5, 1, 4, 1, 3}; !Equal(odd, want) {
 950                 t.Errorf("Reverse(odd) = %v, want %v", odd, want)
 951         }
 952
 953         words := strings.Fields("one two three")
 954         Reverse(words)
 955         if want := strings.Fields("three two one"); !Equal(words, want) {
 956                 t.Errorf("Reverse(words) = %v, want %v", words, want)
 957         }
 958
 959         singleton := []string{"one"}
 960         Reverse(singleton)
 961         if want := []string{"one"}; !Equal(singleton, want) {
 962                 t.Errorf("Reverse(singeleton) = %v, want %v", singleton, want)
 963         }
 964
 965         Reverse[[]string](nil)
 966 }
 967
 968 // naiveReplace is a baseline implementation to the Replace function.
 969 func naiveReplace[S ~[]E, E any](s S, i, j int, v ...E) S {
 970         s = Delete(s, i, j)
 971         s = Insert(s, i, v...)
 972         return s
 973 }
 974
 975 func TestReplace(t *testing.T) {
 976         for _, test := range []struct {
 977                 s, v []int
 978                 i, j int
 979         }{
 980                 {}, // all zero value
 981                 {
 982                         s: []int{1, 2, 3, 4},
 983                         v: []int{5},
 984                         i: 1,
 985                         j: 2,
 986                 },
 987                 {
 988                         s: []int{1, 2, 3, 4},
 989                         v: []int{5, 6, 7, 8},
 990                         i: 1,
 991                         j: 2,
 992                 },
 993                 {
 994                         s: func() []int {
 995                                 s := make([]int, 3, 20)
 996                                 s[0] = 0
 997                                 s[1] = 1
 998                                 s[2] = 2
 999                                 return s
1000                         }(),
1001                         v: []int{3, 4, 5, 6, 7},
1002                         i: 0,
1003                         j: 1,
1004                 },
1005         } {
1006                 ss, vv := Clone(test.s), Clone(test.v)
1007                 want := naiveReplace(ss, test.i, test.j, vv...)
1008                 got := Replace(test.s, test.i, test.j, test.v...)
1009                 if !Equal(got, want) {
1010                         t.Errorf("Replace(%v, %v, %v, %v) = %v, want %v", test.s, test.i, test.j, test.v, got, want)
1011                 }
1012         }
1013 }
1014
1015 func TestReplacePanics(t *testing.T) {
1016         s := []int{0, 1, 2, 3, 4}
1017         s = s[0:2]
1018         _ = s[0:4] // this is a valid slice of s
1019
1020         for _, test := range []struct {
1021                 name string
1022                 s, v []int
1023                 i, j int
1024         }{
1025                 {"indexes out of order", []int{1, 2}, []int{3}, 2, 1},
1026                 {"large index", []int{1, 2}, []int{3}, 1, 10},
1027                 {"negative index", []int{1, 2}, []int{3}, -1, 2},
1028                 {"s[i:j] is valid and j > len(s)", s, nil, 0, 4},
1029         } {
1030                 ss, vv := Clone(test.s), Clone(test.v)
1031                 if !panics(func() { Replace(ss, test.i, test.j, vv...) }) {
1032                         t.Errorf("Replace %s: should have panicked", test.name)
1033                 }
1034         }
1035 }
1036
1037 func TestReplaceGrow(t *testing.T) {
1038         // When Replace needs to allocate a new slice, we want the original slice
1039         // to not be changed.
1040         a, b, c, d, e, f := 1, 2, 3, 4, 5, 6
1041         mem := []*int{&a, &b, &c, &d, &e, &f}
1042         memcopy := Clone(mem)
1043         s := mem[0:5] // there is 1 element beyond len(s), within cap(s)
1044         copy := Clone(s)
1045         original := s
1046
1047         // The new elements don't fit within cap(s), so Replace will allocate.
1048         z := 99
1049         s = Replace(s, 1, 3, &z, &z, &z, &z)
1050
1051         if want := []*int{&a, &z, &z, &z, &z, &d, &e}; !Equal(s, want) {
1052                 t.Errorf("Replace(%v, 1, 3, %v, %v, %v, %v) = %v, want %v", copy, &z, &z, &z, &z, s, want)
1053         }
1054
1055         if !Equal(original, copy) {
1056                 t.Errorf("original slice has changed, got %v, want %v", original, copy)
1057         }
1058
1059         if !Equal(mem, memcopy) {
1060                 // Changing the original tail s[len(s):cap(s)] is unwanted
1061                 t.Errorf("original backing memory has changed, got %v, want %v", mem, memcopy)
1062         }
1063 }
1064
1065 func TestReplaceClearTail(t *testing.T) {
1066         a, b, c, d, e, f := 1, 2, 3, 4, 5, 6
1067         mem := []*int{&a, &b, &c, &d, &e, &f}
1068         s := mem[0:5] // there is 1 element beyond len(s), within cap(s)
1069         copy := Clone(s)
1070
1071         y, z := 8, 9
1072         s = Replace(s, 1, 4, &y, &z)
1073
1074         if want := []*int{&a, &y, &z, &e}; !Equal(s, want) {
1075                 t.Errorf("Replace(%v) = %v, want %v", copy, s, want)
1076         }
1077
1078         if mem[4] != nil {
1079                 // Check that potential memory leak is avoided
1080                 t.Errorf("Replace: want nil discarded element, got %v", mem[4])
1081         }
1082         if mem[5] != &f {
1083                 t.Errorf("Replace: want unchanged elements beyond original len, got %v", mem[5])
1084         }
1085 }
1086
1087 func TestReplaceOverlap(t *testing.T) {
1088         const N = 10
1089         a := make([]int, N)
1090         want := make([]int, 2*N)
1091         for n := 0; n <= N; n++ { // length
1092                 for i := 0; i <= n; i++ { // insertion point 1
1093                         for j := i; j <= n; j++ { // insertion point 2
1094                                 for x := 0; x <= N; x++ { // start of inserted data
1095                                         for y := x; y <= N; y++ { // end of inserted data
1096                                                 for k := 0; k < N; k++ {
1097                                                         a[k] = k
1098                                                 }
1099                                                 want = want[:0]
1100                                                 want = append(want, a[:i]...)
1101                                                 want = append(want, a[x:y]...)
1102                                                 want = append(want, a[j:n]...)
1103                                                 got := Replace(a[:n], i, j, a[x:y]...)
1104                                                 if !Equal(got, want) {
1105                                                         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)
1106                                                 }
1107                                         }
1108                                 }
1109                         }
1110                 }
1111         }
1112 }
1113
1114 func BenchmarkReplace(b *testing.B) {
1115         cases := []struct {
1116                 name string
1117                 s, v func() []int
1118                 i, j int
1119         }{
1120                 {
1121                         name: "fast",
1122                         s: func() []int {
1123                                 return make([]int, 100)
1124                         },
1125                         v: func() []int {
1126                                 return make([]int, 20)
1127                         },
1128                         i: 10,
1129                         j: 40,
1130                 },
1131                 {
1132                         name: "slow",
1133                         s: func() []int {
1134                                 return make([]int, 100)
1135                         },
1136                         v: func() []int {
1137                                 return make([]int, 20)
1138                         },
1139                         i: 0,
1140                         j: 2,
1141                 },
1142         }
1143
1144         for _, c := range cases {
1145                 b.Run("naive-"+c.name, func(b *testing.B) {
1146                         for k := 0; k < b.N; k++ {
1147                                 s := c.s()
1148                                 v := c.v()
1149                                 _ = naiveReplace(s, c.i, c.j, v...)
1150                         }
1151                 })
1152                 b.Run("optimized-"+c.name, func(b *testing.B) {
1153                         for k := 0; k < b.N; k++ {
1154                                 s := c.s()
1155                                 v := c.v()
1156                                 _ = Replace(s, c.i, c.j, v...)
1157                         }
1158                 })
1159         }
1160
1161 }
1162
1163 func TestInsertGrowthRate(t *testing.T) {
1164         b := make([]byte, 1)
1165         maxCap := cap(b)
1166         nGrow := 0
1167         const N = 1e6
1168         for i := 0; i < N; i++ {
1169                 b = Insert(b, len(b)-1, 0)
1170                 if cap(b) > maxCap {
1171                         maxCap = cap(b)
1172                         nGrow++
1173                 }
1174         }
1175         want := int(math.Log(N) / math.Log(1.25)) // 1.25 == growth rate for large slices
1176         if nGrow > want {
1177                 t.Errorf("too many grows. got:%d want:%d", nGrow, want)
1178         }
1179 }
1180
1181 func TestReplaceGrowthRate(t *testing.T) {
1182         b := make([]byte, 2)
1183         maxCap := cap(b)
1184         nGrow := 0
1185         const N = 1e6
1186         for i := 0; i < N; i++ {
1187                 b = Replace(b, len(b)-2, len(b)-1, 0, 0)
1188                 if cap(b) > maxCap {
1189                         maxCap = cap(b)
1190                         nGrow++
1191                 }
1192         }
1193         want := int(math.Log(N) / math.Log(1.25)) // 1.25 == growth rate for large slices
1194         if nGrow > want {
1195                 t.Errorf("too many grows. got:%d want:%d", nGrow, want)
1196         }
1197 }
1198
1199 func apply[T any](v T, f func(T)) {
1200         f(v)
1201 }
1202
1203 // Test type inference with a named slice type.
1204 func TestInference(t *testing.T) {
1205         s1 := []int{1, 2, 3}
1206         apply(s1, Reverse)
1207         if want := []int{3, 2, 1}; !Equal(s1, want) {
1208                 t.Errorf("Reverse(%v) = %v, want %v", []int{1, 2, 3}, s1, want)
1209         }
1210
1211         type S []int
1212         s2 := S{4, 5, 6}
1213         apply(s2, Reverse)
1214         if want := (S{6, 5, 4}); !Equal(s2, want) {
1215                 t.Errorf("Reverse(%v) = %v, want %v", S{4, 5, 6}, s2, want)
1216         }
1217 }
1218
1219 func TestConcat(t *testing.T) {
1220         cases := []struct {
1221                 s    [][]int
1222                 want []int
1223         }{
1224                 {
1225                         s:    [][]int{nil},
1226                         want: nil,
1227                 },
1228                 {
1229                         s:    [][]int{{1}},
1230                         want: []int{1},
1231                 },
1232                 {
1233                         s:    [][]int{{1}, {2}},
1234                         want: []int{1, 2},
1235                 },
1236                 {
1237                         s:    [][]int{{1}, nil, {2}},
1238                         want: []int{1, 2},
1239                 },
1240         }
1241         for _, tc := range cases {
1242                 got := Concat(tc.s...)
1243                 if !Equal(tc.want, got) {
1244                         t.Errorf("Concat(%v) = %v, want %v", tc.s, got, tc.want)
1245                 }
1246                 var sink []int
1247                 allocs := testing.AllocsPerRun(5, func() {
1248                         sink = Concat(tc.s...)
1249                 })
1250                 _ = sink
1251                 if allocs > 1 {
1252                         errorf := t.Errorf
1253                         if testenv.OptimizationOff() || race.Enabled {
1254                                 errorf = t.Logf
1255                         }
1256                         errorf("Concat(%v) allocated %v times; want 1", tc.s, allocs)
1257                 }
1258         }
1259 }
1260
1261 func TestConcat_too_large(t *testing.T) {
1262         // Use zero length element to minimize memory in testing
1263         type void struct{}
1264         cases := []struct {
1265                 lengths     []int
1266                 shouldPanic bool
1267         }{
1268                 {
1269                         lengths:     []int{0, 0},
1270                         shouldPanic: false,
1271                 },
1272                 {
1273                         lengths:     []int{math.MaxInt, 0},
1274                         shouldPanic: false,
1275                 },
1276                 {
1277                         lengths:     []int{0, math.MaxInt},
1278                         shouldPanic: false,
1279                 },
1280                 {
1281                         lengths:     []int{math.MaxInt - 1, 1},
1282                         shouldPanic: false,
1283                 },
1284                 {
1285                         lengths:     []int{math.MaxInt - 1, 1, 1},
1286                         shouldPanic: true,
1287                 },
1288                 {
1289                         lengths:     []int{math.MaxInt, 1},
1290                         shouldPanic: true,
1291                 },
1292                 {
1293                         lengths:     []int{math.MaxInt, math.MaxInt},
1294                         shouldPanic: true,
1295                 },
1296         }
1297         for _, tc := range cases {
1298                 var r any
1299                 ss := make([][]void, 0, len(tc.lengths))
1300                 for _, l := range tc.lengths {
1301                         s := make([]void, l)
1302                         ss = append(ss, s)
1303                 }
1304                 func() {
1305                         defer func() {
1306                                 r = recover()
1307                         }()
1308                         _ = Concat(ss...)
1309                 }()
1310                 if didPanic := r != nil; didPanic != tc.shouldPanic {
1311                         t.Errorf("slices.Concat(lens(%v)) got panic == %v",
1312                                 tc.lengths, didPanic)
1313                 }
1314         }
1315 }