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 func panics(f func()) (b bool) {
 308         defer func() {
 309                 if x := recover(); x != nil {
 310                         b = true
 311                 }
 312         }()
 313         f()
 314         return false
 315 }
 316
 317 func TestDeletePanics(t *testing.T) {
 318         for _, test := range []struct {
 319                 name string
 320                 s    []int
 321                 i, j int
 322         }{
 323                 {"with negative first index", []int{42}, -2, 1},
 324                 {"with negative second index", []int{42}, 1, -1},
 325                 {"with out-of-bounds first index", []int{42}, 2, 3},
 326                 {"with out-of-bounds second index", []int{42}, 0, 2},
 327                 {"with invalid i>j", []int{42}, 1, 0},
 328         } {
 329                 if !panics(func() { Delete(test.s, test.i, test.j) }) {
 330                         t.Errorf("Delete %s: got no panic, want panic", test.name)
 331                 }
 332         }
 333 }
 334
 335 func TestClone(t *testing.T) {
 336         s1 := []int{1, 2, 3}
 337         s2 := Clone(s1)
 338         if !Equal(s1, s2) {
 339                 t.Errorf("Clone(%v) = %v, want %v", s1, s2, s1)
 340         }
 341         s1[0] = 4
 342         want := []int{1, 2, 3}
 343         if !Equal(s2, want) {
 344                 t.Errorf("Clone(%v) changed unexpectedly to %v", want, s2)
 345         }
 346         if got := Clone([]int(nil)); got != nil {
 347                 t.Errorf("Clone(nil) = %#v, want nil", got)
 348         }
 349         if got := Clone(s1[:0]); got == nil || len(got) != 0 {
 350                 t.Errorf("Clone(%v) = %#v, want %#v", s1[:0], got, s1[:0])
 351         }
 352 }
 353
 354 var compactTests = []struct {
 355         name string
 356         s    []int
 357         want []int
 358 }{
 359         {
 360                 "nil",
 361                 nil,
 362                 nil,
 363         },
 364         {
 365                 "one",
 366                 []int{1},
 367                 []int{1},
 368         },
 369         {
 370                 "sorted",
 371                 []int{1, 2, 3},
 372                 []int{1, 2, 3},
 373         },
 374         {
 375                 "1 item",
 376                 []int{1, 1, 2},
 377                 []int{1, 2},
 378         },
 379         {
 380                 "unsorted",
 381                 []int{1, 2, 1},
 382                 []int{1, 2, 1},
 383         },
 384         {
 385                 "many",
 386                 []int{1, 2, 2, 3, 3, 4},
 387                 []int{1, 2, 3, 4},
 388         },
 389 }
 390
 391 func TestCompact(t *testing.T) {
 392         for _, test := range compactTests {
 393                 copy := Clone(test.s)
 394                 if got := Compact(copy); !Equal(got, test.want) {
 395                         t.Errorf("Compact(%v) = %v, want %v", test.s, got, test.want)
 396                 }
 397         }
 398 }
 399
 400 func BenchmarkCompact(b *testing.B) {
 401         for _, c := range compactTests {
 402                 b.Run(c.name, func(b *testing.B) {
 403                         ss := make([]int, 0, 64)
 404                         for k := 0; k < b.N; k++ {
 405                                 ss = ss[:0]
 406                                 ss = append(ss, c.s...)
 407                                 _ = Compact(ss)
 408                         }
 409                 })
 410         }
 411
 412 }
 413
 414 func TestCompactFunc(t *testing.T) {
 415         for _, test := range compactTests {
 416                 copy := Clone(test.s)
 417                 if got := CompactFunc(copy, equal[int]); !Equal(got, test.want) {
 418                         t.Errorf("CompactFunc(%v, equal[int]) = %v, want %v", test.s, got, test.want)
 419                 }
 420         }
 421
 422         s1 := []string{"a", "a", "A", "B", "b"}
 423         copy := Clone(s1)
 424         want := []string{"a", "B"}
 425         if got := CompactFunc(copy, strings.EqualFold); !Equal(got, want) {
 426                 t.Errorf("CompactFunc(%v, strings.EqualFold) = %v, want %v", s1, got, want)
 427         }
 428 }
 429
 430 func TestGrow(t *testing.T) {
 431         s1 := []int{1, 2, 3}
 432
 433         copy := Clone(s1)
 434         s2 := Grow(copy, 1000)
 435         if !Equal(s1, s2) {
 436                 t.Errorf("Grow(%v) = %v, want %v", s1, s2, s1)
 437         }
 438         if cap(s2) < 1000+len(s1) {
 439                 t.Errorf("after Grow(%v) cap = %d, want >= %d", s1, cap(s2), 1000+len(s1))
 440         }
 441
 442         // Test mutation of elements between length and capacity.
 443         copy = Clone(s1)
 444         s3 := Grow(copy[:1], 2)[:3]
 445         if !Equal(s1, s3) {
 446                 t.Errorf("Grow should not mutate elements between length and capacity")
 447         }
 448         s3 = Grow(copy[:1], 1000)[:3]
 449         if !Equal(s1, s3) {
 450                 t.Errorf("Grow should not mutate elements between length and capacity")
 451         }
 452
 453         // Test number of allocations.
 454         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)) }); n != 0 {
 455                 t.Errorf("Grow should not allocate when given sufficient capacity; allocated %v times", n)
 456         }
 457         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)+1) }); n != 1 {
 458                 errorf := t.Errorf
 459                 if race.Enabled || testenv.OptimizationOff() {
 460                         errorf = t.Logf // this allocates multiple times in race detector mode
 461                 }
 462                 errorf("Grow should allocate once when given insufficient capacity; allocated %v times", n)
 463         }
 464
 465         // Test for negative growth sizes.
 466         var gotPanic bool
 467         func() {
 468                 defer func() { gotPanic = recover() != nil }()
 469                 Grow(s1, -1)
 470         }()
 471         if !gotPanic {
 472                 t.Errorf("Grow(-1) did not panic; expected a panic")
 473         }
 474 }
 475
 476 func TestClip(t *testing.T) {
 477         s1 := []int{1, 2, 3, 4, 5, 6}[:3]
 478         orig := Clone(s1)
 479         if len(s1) != 3 {
 480                 t.Errorf("len(%v) = %d, want 3", s1, len(s1))
 481         }
 482         if cap(s1) < 6 {
 483                 t.Errorf("cap(%v[:3]) = %d, want >= 6", orig, cap(s1))
 484         }
 485         s2 := Clip(s1)
 486         if !Equal(s1, s2) {
 487                 t.Errorf("Clip(%v) = %v, want %v", s1, s2, s1)
 488         }
 489         if cap(s2) != 3 {
 490                 t.Errorf("cap(Clip(%v)) = %d, want 3", orig, cap(s2))
 491         }
 492 }
 493
 494 // naiveReplace is a baseline implementation to the Replace function.
 495 func naiveReplace[S ~[]E, E any](s S, i, j int, v ...E) S {
 496         s = Delete(s, i, j)
 497         s = Insert(s, i, v...)
 498         return s
 499 }
 500
 501 func TestReplace(t *testing.T) {
 502         for _, test := range []struct {
 503                 s, v []int
 504                 i, j int
 505         }{
 506                 {}, // all zero value
 507                 {
 508                         s: []int{1, 2, 3, 4},
 509                         v: []int{5},
 510                         i: 1,
 511                         j: 2,
 512                 },
 513                 {
 514                         s: []int{1, 2, 3, 4},
 515                         v: []int{5, 6, 7, 8},
 516                         i: 1,
 517                         j: 2,
 518                 },
 519                 {
 520                         s: func() []int {
 521                                 s := make([]int, 3, 20)
 522                                 s[0] = 0
 523                                 s[1] = 1
 524                                 s[2] = 2
 525                                 return s
 526                         }(),
 527                         v: []int{3, 4, 5, 6, 7},
 528                         i: 0,
 529                         j: 1,
 530                 },
 531         } {
 532                 ss, vv := Clone(test.s), Clone(test.v)
 533                 want := naiveReplace(ss, test.i, test.j, vv...)
 534                 got := Replace(test.s, test.i, test.j, test.v...)
 535                 if !Equal(got, want) {
 536                         t.Errorf("Replace(%v, %v, %v, %v) = %v, want %v", test.s, test.i, test.j, test.v, got, want)
 537                 }
 538         }
 539 }
 540
 541 func TestReplacePanics(t *testing.T) {
 542         for _, test := range []struct {
 543                 name string
 544                 s, v []int
 545                 i, j int
 546         }{
 547                 {"indexes out of order", []int{1, 2}, []int{3}, 2, 1},
 548                 {"large index", []int{1, 2}, []int{3}, 1, 10},
 549                 {"negative index", []int{1, 2}, []int{3}, -1, 2},
 550         } {
 551                 ss, vv := Clone(test.s), Clone(test.v)
 552                 if !panics(func() { Replace(ss, test.i, test.j, vv...) }) {
 553                         t.Errorf("Replace %s: should have panicked", test.name)
 554                 }
 555         }
 556 }
 557
 558 func BenchmarkReplace(b *testing.B) {
 559         cases := []struct {
 560                 name string
 561                 s, v func() []int
 562                 i, j int
 563         }{
 564                 {
 565                         name: "fast",
 566                         s: func() []int {
 567                                 return make([]int, 100)
 568                         },
 569                         v: func() []int {
 570                                 return make([]int, 20)
 571                         },
 572                         i: 10,
 573                         j: 40,
 574                 },
 575                 {
 576                         name: "slow",
 577                         s: func() []int {
 578                                 return make([]int, 100)
 579                         },
 580                         v: func() []int {
 581                                 return make([]int, 20)
 582                         },
 583                         i: 0,
 584                         j: 2,
 585                 },
 586         }
 587
 588         for _, c := range cases {
 589                 b.Run("naive-"+c.name, func(b *testing.B) {
 590                         for k := 0; k < b.N; k++ {
 591                                 s := c.s()
 592                                 v := c.v()
 593                                 _ = naiveReplace(s, c.i, c.j, v...)
 594                         }
 595                 })
 596                 b.Run("optimized-"+c.name, func(b *testing.B) {
 597                         for k := 0; k < b.N; k++ {
 598                                 s := c.s()
 599                                 v := c.v()
 600                                 _ = Replace(s, c.i, c.j, v...)
 601                         }
 602                 })
 603         }
 604
 605 }