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 var indexTests = []struct {
 128         s    []int
 129         v    int
 130         want int
 131 }{
 132         {
 133                 nil,
 134                 0,
 135                 -1,
 136         },
 137         {
 138                 []int{},
 139                 0,
 140                 -1,
 141         },
 142         {
 143                 []int{1, 2, 3},
 144                 2,
 145                 1,
 146         },
 147         {
 148                 []int{1, 2, 2, 3},
 149                 2,
 150                 1,
 151         },
 152         {
 153                 []int{1, 2, 3, 2},
 154                 2,
 155                 1,
 156         },
 157 }
 158
 159 func TestIndex(t *testing.T) {
 160         for _, test := range indexTests {
 161                 if got := Index(test.s, test.v); got != test.want {
 162                         t.Errorf("Index(%v, %v) = %d, want %d", test.s, test.v, got, test.want)
 163                 }
 164         }
 165 }
 166
 167 func equalToIndex[T any](f func(T, T) bool, v1 T) func(T) bool {
 168         return func(v2 T) bool {
 169                 return f(v1, v2)
 170         }
 171 }
 172
 173 func TestIndexFunc(t *testing.T) {
 174         for _, test := range indexTests {
 175                 if got := IndexFunc(test.s, equalToIndex(equal[int], test.v)); got != test.want {
 176                         t.Errorf("IndexFunc(%v, equalToIndex(equal[int], %v)) = %d, want %d", test.s, test.v, got, test.want)
 177                 }
 178         }
 179
 180         s1 := []string{"hi", "HI"}
 181         if got := IndexFunc(s1, equalToIndex(equal[string], "HI")); got != 1 {
 182                 t.Errorf("IndexFunc(%v, equalToIndex(equal[string], %q)) = %d, want %d", s1, "HI", got, 1)
 183         }
 184         if got := IndexFunc(s1, equalToIndex(strings.EqualFold, "HI")); got != 0 {
 185                 t.Errorf("IndexFunc(%v, equalToIndex(strings.EqualFold, %q)) = %d, want %d", s1, "HI", got, 0)
 186         }
 187 }
 188
 189 func TestContains(t *testing.T) {
 190         for _, test := range indexTests {
 191                 if got := Contains(test.s, test.v); got != (test.want != -1) {
 192                         t.Errorf("Contains(%v, %v) = %t, want %t", test.s, test.v, got, test.want != -1)
 193                 }
 194         }
 195 }
 196
 197 func TestContainsFunc(t *testing.T) {
 198         for _, test := range indexTests {
 199                 if got := ContainsFunc(test.s, equalToIndex(equal[int], test.v)); got != (test.want != -1) {
 200                         t.Errorf("ContainsFunc(%v, equalToIndex(equal[int], %v)) = %t, want %t", test.s, test.v, got, test.want != -1)
 201                 }
 202         }
 203
 204         s1 := []string{"hi", "HI"}
 205         if got := ContainsFunc(s1, equalToIndex(equal[string], "HI")); got != true {
 206                 t.Errorf("ContainsFunc(%v, equalToContains(equal[string], %q)) = %t, want %t", s1, "HI", got, true)
 207         }
 208         if got := ContainsFunc(s1, equalToIndex(equal[string], "hI")); got != false {
 209                 t.Errorf("ContainsFunc(%v, equalToContains(strings.EqualFold, %q)) = %t, want %t", s1, "hI", got, false)
 210         }
 211         if got := ContainsFunc(s1, equalToIndex(strings.EqualFold, "hI")); got != true {
 212                 t.Errorf("ContainsFunc(%v, equalToContains(strings.EqualFold, %q)) = %t, want %t", s1, "hI", got, true)
 213         }
 214 }
 215
 216 var insertTests = []struct {
 217         s    []int
 218         i    int
 219         add  []int
 220         want []int
 221 }{
 222         {
 223                 []int{1, 2, 3},
 224                 0,
 225                 []int{4},
 226                 []int{4, 1, 2, 3},
 227         },
 228         {
 229                 []int{1, 2, 3},
 230                 1,
 231                 []int{4},
 232                 []int{1, 4, 2, 3},
 233         },
 234         {
 235                 []int{1, 2, 3},
 236                 3,
 237                 []int{4},
 238                 []int{1, 2, 3, 4},
 239         },
 240         {
 241                 []int{1, 2, 3},
 242                 2,
 243                 []int{4, 5},
 244                 []int{1, 2, 4, 5, 3},
 245         },
 246 }
 247
 248 func TestInsert(t *testing.T) {
 249         s := []int{1, 2, 3}
 250         if got := Insert(s, 0); !Equal(got, s) {
 251                 t.Errorf("Insert(%v, 0) = %v, want %v", s, got, s)
 252         }
 253         for _, test := range insertTests {
 254                 copy := Clone(test.s)
 255                 if got := Insert(copy, test.i, test.add...); !Equal(got, test.want) {
 256                         t.Errorf("Insert(%v, %d, %v...) = %v, want %v", test.s, test.i, test.add, got, test.want)
 257                 }
 258         }
 259 }
 260
 261 var deleteTests = []struct {
 262         s    []int
 263         i, j int
 264         want []int
 265 }{
 266         {
 267                 []int{1, 2, 3},
 268                 0,
 269                 0,
 270                 []int{1, 2, 3},
 271         },
 272         {
 273                 []int{1, 2, 3},
 274                 0,
 275                 1,
 276                 []int{2, 3},
 277         },
 278         {
 279                 []int{1, 2, 3},
 280                 3,
 281                 3,
 282                 []int{1, 2, 3},
 283         },
 284         {
 285                 []int{1, 2, 3},
 286                 0,
 287                 2,
 288                 []int{3},
 289         },
 290         {
 291                 []int{1, 2, 3},
 292                 0,
 293                 3,
 294                 []int{},
 295         },
 296 }
 297
 298 func TestDelete(t *testing.T) {
 299         for _, test := range deleteTests {
 300                 copy := Clone(test.s)
 301                 if got := Delete(copy, test.i, test.j); !Equal(got, test.want) {
 302                         t.Errorf("Delete(%v, %d, %d) = %v, want %v", test.s, test.i, test.j, got, test.want)
 303                 }
 304         }
 305 }
 306
 307 var deleteFuncTests = []struct {
 308         s    []int
 309         fn   func(int) bool
 310         want []int
 311 }{
 312         {
 313                 nil,
 314                 func(int) bool { return true },
 315                 nil,
 316         },
 317         {
 318                 []int{1, 2, 3},
 319                 func(int) bool { return true },
 320                 nil,
 321         },
 322         {
 323                 []int{1, 2, 3},
 324                 func(int) bool { return false },
 325                 []int{1, 2, 3},
 326         },
 327         {
 328                 []int{1, 2, 3},
 329                 func(i int) bool { return i > 2 },
 330                 []int{1, 2},
 331         },
 332         {
 333                 []int{1, 2, 3},
 334                 func(i int) bool { return i < 2 },
 335                 []int{2, 3},
 336         },
 337         {
 338                 []int{10, 2, 30},
 339                 func(i int) bool { return i >= 10 },
 340                 []int{2},
 341         },
 342 }
 343
 344 func TestDeleteFunc(t *testing.T) {
 345         for i, test := range deleteFuncTests {
 346                 copy := Clone(test.s)
 347                 if got := DeleteFunc(copy, test.fn); !Equal(got, test.want) {
 348                         t.Errorf("DeleteFunc case %d: got %v, want %v", i, got, test.want)
 349                 }
 350         }
 351 }
 352
 353 func panics(f func()) (b bool) {
 354         defer func() {
 355                 if x := recover(); x != nil {
 356                         b = true
 357                 }
 358         }()
 359         f()
 360         return false
 361 }
 362
 363 func TestDeletePanics(t *testing.T) {
 364         for _, test := range []struct {
 365                 name string
 366                 s    []int
 367                 i, j int
 368         }{
 369                 {"with negative first index", []int{42}, -2, 1},
 370                 {"with negative second index", []int{42}, 1, -1},
 371                 {"with out-of-bounds first index", []int{42}, 2, 3},
 372                 {"with out-of-bounds second index", []int{42}, 0, 2},
 373                 {"with invalid i>j", []int{42}, 1, 0},
 374         } {
 375                 if !panics(func() { Delete(test.s, test.i, test.j) }) {
 376                         t.Errorf("Delete %s: got no panic, want panic", test.name)
 377                 }
 378         }
 379 }
 380
 381 func TestClone(t *testing.T) {
 382         s1 := []int{1, 2, 3}
 383         s2 := Clone(s1)
 384         if !Equal(s1, s2) {
 385                 t.Errorf("Clone(%v) = %v, want %v", s1, s2, s1)
 386         }
 387         s1[0] = 4
 388         want := []int{1, 2, 3}
 389         if !Equal(s2, want) {
 390                 t.Errorf("Clone(%v) changed unexpectedly to %v", want, s2)
 391         }
 392         if got := Clone([]int(nil)); got != nil {
 393                 t.Errorf("Clone(nil) = %#v, want nil", got)
 394         }
 395         if got := Clone(s1[:0]); got == nil || len(got) != 0 {
 396                 t.Errorf("Clone(%v) = %#v, want %#v", s1[:0], got, s1[:0])
 397         }
 398 }
 399
 400 var compactTests = []struct {
 401         name string
 402         s    []int
 403         want []int
 404 }{
 405         {
 406                 "nil",
 407                 nil,
 408                 nil,
 409         },
 410         {
 411                 "one",
 412                 []int{1},
 413                 []int{1},
 414         },
 415         {
 416                 "sorted",
 417                 []int{1, 2, 3},
 418                 []int{1, 2, 3},
 419         },
 420         {
 421                 "1 item",
 422                 []int{1, 1, 2},
 423                 []int{1, 2},
 424         },
 425         {
 426                 "unsorted",
 427                 []int{1, 2, 1},
 428                 []int{1, 2, 1},
 429         },
 430         {
 431                 "many",
 432                 []int{1, 2, 2, 3, 3, 4},
 433                 []int{1, 2, 3, 4},
 434         },
 435 }
 436
 437 func TestCompact(t *testing.T) {
 438         for _, test := range compactTests {
 439                 copy := Clone(test.s)
 440                 if got := Compact(copy); !Equal(got, test.want) {
 441                         t.Errorf("Compact(%v) = %v, want %v", test.s, got, test.want)
 442                 }
 443         }
 444 }
 445
 446 func BenchmarkCompact(b *testing.B) {
 447         for _, c := range compactTests {
 448                 b.Run(c.name, func(b *testing.B) {
 449                         ss := make([]int, 0, 64)
 450                         for k := 0; k < b.N; k++ {
 451                                 ss = ss[:0]
 452                                 ss = append(ss, c.s...)
 453                                 _ = Compact(ss)
 454                         }
 455                 })
 456         }
 457
 458 }
 459
 460 func TestCompactFunc(t *testing.T) {
 461         for _, test := range compactTests {
 462                 copy := Clone(test.s)
 463                 if got := CompactFunc(copy, equal[int]); !Equal(got, test.want) {
 464                         t.Errorf("CompactFunc(%v, equal[int]) = %v, want %v", test.s, got, test.want)
 465                 }
 466         }
 467
 468         s1 := []string{"a", "a", "A", "B", "b"}
 469         copy := Clone(s1)
 470         want := []string{"a", "B"}
 471         if got := CompactFunc(copy, strings.EqualFold); !Equal(got, want) {
 472                 t.Errorf("CompactFunc(%v, strings.EqualFold) = %v, want %v", s1, got, want)
 473         }
 474 }
 475
 476 func TestGrow(t *testing.T) {
 477         s1 := []int{1, 2, 3}
 478
 479         copy := Clone(s1)
 480         s2 := Grow(copy, 1000)
 481         if !Equal(s1, s2) {
 482                 t.Errorf("Grow(%v) = %v, want %v", s1, s2, s1)
 483         }
 484         if cap(s2) < 1000+len(s1) {
 485                 t.Errorf("after Grow(%v) cap = %d, want >= %d", s1, cap(s2), 1000+len(s1))
 486         }
 487
 488         // Test mutation of elements between length and capacity.
 489         copy = Clone(s1)
 490         s3 := Grow(copy[:1], 2)[:3]
 491         if !Equal(s1, s3) {
 492                 t.Errorf("Grow should not mutate elements between length and capacity")
 493         }
 494         s3 = Grow(copy[:1], 1000)[:3]
 495         if !Equal(s1, s3) {
 496                 t.Errorf("Grow should not mutate elements between length and capacity")
 497         }
 498
 499         // Test number of allocations.
 500         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)) }); n != 0 {
 501                 t.Errorf("Grow should not allocate when given sufficient capacity; allocated %v times", n)
 502         }
 503         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)+1) }); n != 1 {
 504                 errorf := t.Errorf
 505                 if race.Enabled || testenv.OptimizationOff() {
 506                         errorf = t.Logf // this allocates multiple times in race detector mode
 507                 }
 508                 errorf("Grow should allocate once when given insufficient capacity; allocated %v times", n)
 509         }
 510
 511         // Test for negative growth sizes.
 512         var gotPanic bool
 513         func() {
 514                 defer func() { gotPanic = recover() != nil }()
 515                 Grow(s1, -1)
 516         }()
 517         if !gotPanic {
 518                 t.Errorf("Grow(-1) did not panic; expected a panic")
 519         }
 520 }
 521
 522 func TestClip(t *testing.T) {
 523         s1 := []int{1, 2, 3, 4, 5, 6}[:3]
 524         orig := Clone(s1)
 525         if len(s1) != 3 {
 526                 t.Errorf("len(%v) = %d, want 3", s1, len(s1))
 527         }
 528         if cap(s1) < 6 {
 529                 t.Errorf("cap(%v[:3]) = %d, want >= 6", orig, cap(s1))
 530         }
 531         s2 := Clip(s1)
 532         if !Equal(s1, s2) {
 533                 t.Errorf("Clip(%v) = %v, want %v", s1, s2, s1)
 534         }
 535         if cap(s2) != 3 {
 536                 t.Errorf("cap(Clip(%v)) = %d, want 3", orig, cap(s2))
 537         }
 538 }
 539
 540 // naiveReplace is a baseline implementation to the Replace function.
 541 func naiveReplace[S ~[]E, E any](s S, i, j int, v ...E) S {
 542         s = Delete(s, i, j)
 543         s = Insert(s, i, v...)
 544         return s
 545 }
 546
 547 func TestReplace(t *testing.T) {
 548         for _, test := range []struct {
 549                 s, v []int
 550                 i, j int
 551         }{
 552                 {}, // all zero value
 553                 {
 554                         s: []int{1, 2, 3, 4},
 555                         v: []int{5},
 556                         i: 1,
 557                         j: 2,
 558                 },
 559                 {
 560                         s: []int{1, 2, 3, 4},
 561                         v: []int{5, 6, 7, 8},
 562                         i: 1,
 563                         j: 2,
 564                 },
 565                 {
 566                         s: func() []int {
 567                                 s := make([]int, 3, 20)
 568                                 s[0] = 0
 569                                 s[1] = 1
 570                                 s[2] = 2
 571                                 return s
 572                         }(),
 573                         v: []int{3, 4, 5, 6, 7},
 574                         i: 0,
 575                         j: 1,
 576                 },
 577         } {
 578                 ss, vv := Clone(test.s), Clone(test.v)
 579                 want := naiveReplace(ss, test.i, test.j, vv...)
 580                 got := Replace(test.s, test.i, test.j, test.v...)
 581                 if !Equal(got, want) {
 582                         t.Errorf("Replace(%v, %v, %v, %v) = %v, want %v", test.s, test.i, test.j, test.v, got, want)
 583                 }
 584         }
 585 }
 586
 587 func TestReplacePanics(t *testing.T) {
 588         for _, test := range []struct {
 589                 name string
 590                 s, v []int
 591                 i, j int
 592         }{
 593                 {"indexes out of order", []int{1, 2}, []int{3}, 2, 1},
 594                 {"large index", []int{1, 2}, []int{3}, 1, 10},
 595                 {"negative index", []int{1, 2}, []int{3}, -1, 2},
 596         } {
 597                 ss, vv := Clone(test.s), Clone(test.v)
 598                 if !panics(func() { Replace(ss, test.i, test.j, vv...) }) {
 599                         t.Errorf("Replace %s: should have panicked", test.name)
 600                 }
 601         }
 602 }
 603
 604 func BenchmarkReplace(b *testing.B) {
 605         cases := []struct {
 606                 name string
 607                 s, v func() []int
 608                 i, j int
 609         }{
 610                 {
 611                         name: "fast",
 612                         s: func() []int {
 613                                 return make([]int, 100)
 614                         },
 615                         v: func() []int {
 616                                 return make([]int, 20)
 617                         },
 618                         i: 10,
 619                         j: 40,
 620                 },
 621                 {
 622                         name: "slow",
 623                         s: func() []int {
 624                                 return make([]int, 100)
 625                         },
 626                         v: func() []int {
 627                                 return make([]int, 20)
 628                         },
 629                         i: 0,
 630                         j: 2,
 631                 },
 632         }
 633
 634         for _, c := range cases {
 635                 b.Run("naive-"+c.name, func(b *testing.B) {
 636                         for k := 0; k < b.N; k++ {
 637                                 s := c.s()
 638                                 v := c.v()
 639                                 _ = naiveReplace(s, c.i, c.j, v...)
 640                         }
 641                 })
 642                 b.Run("optimized-"+c.name, func(b *testing.B) {
 643                         for k := 0; k < b.N; k++ {
 644                                 s := c.s()
 645                                 v := c.v()
 646                                 _ = Replace(s, c.i, c.j, v...)
 647                         }
 648                 })
 649         }
 650
 651 }