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