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