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         "math"
  10         "strings"
  11         "testing"
  12 )
  13
  14 var equalIntTests = []struct {
  15         s1, s2 []int
  16         want   bool
  17 }{
  18         {
  19                 []int{1},
  20                 nil,
  21                 false,
  22         },
  23         {
  24                 []int{},
  25                 nil,
  26                 true,
  27         },
  28         {
  29                 []int{1, 2, 3},
  30                 []int{1, 2, 3},
  31                 true,
  32         },
  33         {
  34                 []int{1, 2, 3},
  35                 []int{1, 2, 3, 4},
  36                 false,
  37         },
  38 }
  39
  40 var equalFloatTests = []struct {
  41         s1, s2       []float64
  42         wantEqual    bool
  43         wantEqualNaN bool
  44 }{
  45         {
  46                 []float64{1, 2},
  47                 []float64{1, 2},
  48                 true,
  49                 true,
  50         },
  51         {
  52                 []float64{1, 2, math.NaN()},
  53                 []float64{1, 2, math.NaN()},
  54                 false,
  55                 true,
  56         },
  57 }
  58
  59 func TestEqual(t *testing.T) {
  60         for _, test := range equalIntTests {
  61                 if got := Equal(test.s1, test.s2); got != test.want {
  62                         t.Errorf("Equal(%v, %v) = %t, want %t", test.s1, test.s2, got, test.want)
  63                 }
  64         }
  65         for _, test := range equalFloatTests {
  66                 if got := Equal(test.s1, test.s2); got != test.wantEqual {
  67                         t.Errorf("Equal(%v, %v) = %t, want %t", test.s1, test.s2, got, test.wantEqual)
  68                 }
  69         }
  70 }
  71
  72 // equal is simply ==.
  73 func equal[T comparable](v1, v2 T) bool {
  74         return v1 == v2
  75 }
  76
  77 // equalNaN is like == except that all NaNs are equal.
  78 func equalNaN[T comparable](v1, v2 T) bool {
  79         isNaN := func(f T) bool { return f != f }
  80         return v1 == v2 || (isNaN(v1) && isNaN(v2))
  81 }
  82
  83 // offByOne returns true if integers v1 and v2 differ by 1.
  84 func offByOne(v1, v2 int) bool {
  85         return v1 == v2+1 || v1 == v2-1
  86 }
  87
  88 func TestEqualFunc(t *testing.T) {
  89         for _, test := range equalIntTests {
  90                 if got := EqualFunc(test.s1, test.s2, equal[int]); got != test.want {
  91                         t.Errorf("EqualFunc(%v, %v, equal[int]) = %t, want %t", test.s1, test.s2, got, test.want)
  92                 }
  93         }
  94         for _, test := range equalFloatTests {
  95                 if got := EqualFunc(test.s1, test.s2, equal[float64]); got != test.wantEqual {
  96                         t.Errorf("Equal(%v, %v, equal[float64]) = %t, want %t", test.s1, test.s2, got, test.wantEqual)
  97                 }
  98                 if got := EqualFunc(test.s1, test.s2, equalNaN[float64]); got != test.wantEqualNaN {
  99                         t.Errorf("Equal(%v, %v, equalNaN[float64]) = %t, want %t", test.s1, test.s2, got, test.wantEqualNaN)
 100                 }
 101         }
 102
 103         s1 := []int{1, 2, 3}
 104         s2 := []int{2, 3, 4}
 105         if EqualFunc(s1, s1, offByOne) {
 106                 t.Errorf("EqualFunc(%v, %v, offByOne) = true, want false", s1, s1)
 107         }
 108         if !EqualFunc(s1, s2, offByOne) {
 109                 t.Errorf("EqualFunc(%v, %v, offByOne) = false, want true", s1, s2)
 110         }
 111
 112         s3 := []string{"a", "b", "c"}
 113         s4 := []string{"A", "B", "C"}
 114         if !EqualFunc(s3, s4, strings.EqualFold) {
 115                 t.Errorf("EqualFunc(%v, %v, strings.EqualFold) = false, want true", s3, s4)
 116         }
 117
 118         cmpIntString := func(v1 int, v2 string) bool {
 119                 return string(rune(v1)-1+'a') == v2
 120         }
 121         if !EqualFunc(s1, s3, cmpIntString) {
 122                 t.Errorf("EqualFunc(%v, %v, cmpIntString) = false, want true", s1, s3)
 123         }
 124 }
 125
 126 var indexTests = []struct {
 127         s    []int
 128         v    int
 129         want int
 130 }{
 131         {
 132                 nil,
 133                 0,
 134                 -1,
 135         },
 136         {
 137                 []int{},
 138                 0,
 139                 -1,
 140         },
 141         {
 142                 []int{1, 2, 3},
 143                 2,
 144                 1,
 145         },
 146         {
 147                 []int{1, 2, 2, 3},
 148                 2,
 149                 1,
 150         },
 151         {
 152                 []int{1, 2, 3, 2},
 153                 2,
 154                 1,
 155         },
 156 }
 157
 158 func TestIndex(t *testing.T) {
 159         for _, test := range indexTests {
 160                 if got := Index(test.s, test.v); got != test.want {
 161                         t.Errorf("Index(%v, %v) = %d, want %d", test.s, test.v, got, test.want)
 162                 }
 163         }
 164 }
 165
 166 func equalToIndex[T any](f func(T, T) bool, v1 T) func(T) bool {
 167         return func(v2 T) bool {
 168                 return f(v1, v2)
 169         }
 170 }
 171
 172 func TestIndexFunc(t *testing.T) {
 173         for _, test := range indexTests {
 174                 if got := IndexFunc(test.s, equalToIndex(equal[int], test.v)); got != test.want {
 175                         t.Errorf("IndexFunc(%v, equalToIndex(equal[int], %v)) = %d, want %d", test.s, test.v, got, test.want)
 176                 }
 177         }
 178
 179         s1 := []string{"hi", "HI"}
 180         if got := IndexFunc(s1, equalToIndex(equal[string], "HI")); got != 1 {
 181                 t.Errorf("IndexFunc(%v, equalToIndex(equal[string], %q)) = %d, want %d", s1, "HI", got, 1)
 182         }
 183         if got := IndexFunc(s1, equalToIndex(strings.EqualFold, "HI")); got != 0 {
 184                 t.Errorf("IndexFunc(%v, equalToIndex(strings.EqualFold, %q)) = %d, want %d", s1, "HI", got, 0)
 185         }
 186 }
 187
 188 func TestContains(t *testing.T) {
 189         for _, test := range indexTests {
 190                 if got := Contains(test.s, test.v); got != (test.want != -1) {
 191                         t.Errorf("Contains(%v, %v) = %t, want %t", test.s, test.v, got, test.want != -1)
 192                 }
 193         }
 194 }
 195
 196 func TestContainsFunc(t *testing.T) {
 197         for _, test := range indexTests {
 198                 if got := ContainsFunc(test.s, equalToIndex(equal[int], test.v)); got != (test.want != -1) {
 199                         t.Errorf("ContainsFunc(%v, equalToIndex(equal[int], %v)) = %t, want %t", test.s, test.v, got, test.want != -1)
 200                 }
 201         }
 202
 203         s1 := []string{"hi", "HI"}
 204         if got := ContainsFunc(s1, equalToIndex(equal[string], "HI")); got != true {
 205                 t.Errorf("ContainsFunc(%v, equalToContains(equal[string], %q)) = %t, want %t", s1, "HI", got, true)
 206         }
 207         if got := ContainsFunc(s1, equalToIndex(equal[string], "hI")); got != false {
 208                 t.Errorf("ContainsFunc(%v, equalToContains(strings.EqualFold, %q)) = %t, want %t", s1, "hI", got, false)
 209         }
 210         if got := ContainsFunc(s1, equalToIndex(strings.EqualFold, "hI")); got != true {
 211                 t.Errorf("ContainsFunc(%v, equalToContains(strings.EqualFold, %q)) = %t, want %t", s1, "hI", got, true)
 212         }
 213 }
 214
 215 var insertTests = []struct {
 216         s    []int
 217         i    int
 218         add  []int
 219         want []int
 220 }{
 221         {
 222                 []int{1, 2, 3},
 223                 0,
 224                 []int{4},
 225                 []int{4, 1, 2, 3},
 226         },
 227         {
 228                 []int{1, 2, 3},
 229                 1,
 230                 []int{4},
 231                 []int{1, 4, 2, 3},
 232         },
 233         {
 234                 []int{1, 2, 3},
 235                 3,
 236                 []int{4},
 237                 []int{1, 2, 3, 4},
 238         },
 239         {
 240                 []int{1, 2, 3},
 241                 2,
 242                 []int{4, 5},
 243                 []int{1, 2, 4, 5, 3},
 244         },
 245 }
 246
 247 func TestInsert(t *testing.T) {
 248         s := []int{1, 2, 3}
 249         if got := Insert(s, 0); !Equal(got, s) {
 250                 t.Errorf("Insert(%v, 0) = %v, want %v", s, got, s)
 251         }
 252         for _, test := range insertTests {
 253                 copy := Clone(test.s)
 254                 if got := Insert(copy, test.i, test.add...); !Equal(got, test.want) {
 255                         t.Errorf("Insert(%v, %d, %v...) = %v, want %v", test.s, test.i, test.add, got, test.want)
 256                 }
 257         }
 258 }
 259
 260 var deleteTests = []struct {
 261         s    []int
 262         i, j int
 263         want []int
 264 }{
 265         {
 266                 []int{1, 2, 3},
 267                 0,
 268                 0,
 269                 []int{1, 2, 3},
 270         },
 271         {
 272                 []int{1, 2, 3},
 273                 0,
 274                 1,
 275                 []int{2, 3},
 276         },
 277         {
 278                 []int{1, 2, 3},
 279                 3,
 280                 3,
 281                 []int{1, 2, 3},
 282         },
 283         {
 284                 []int{1, 2, 3},
 285                 0,
 286                 2,
 287                 []int{3},
 288         },
 289         {
 290                 []int{1, 2, 3},
 291                 0,
 292                 3,
 293                 []int{},
 294         },
 295 }
 296
 297 func TestDelete(t *testing.T) {
 298         for _, test := range deleteTests {
 299                 copy := Clone(test.s)
 300                 if got := Delete(copy, test.i, test.j); !Equal(got, test.want) {
 301                         t.Errorf("Delete(%v, %d, %d) = %v, want %v", test.s, test.i, test.j, got, test.want)
 302                 }
 303         }
 304 }
 305
 306 func panics(f func()) (b bool) {
 307         defer func() {
 308                 if x := recover(); x != nil {
 309                         b = true
 310                 }
 311         }()
 312         f()
 313         return false
 314 }
 315
 316 func TestDeletePanics(t *testing.T) {
 317         for _, test := range []struct {
 318                 name string
 319                 s    []int
 320                 i, j int
 321         }{
 322                 {"with negative first index", []int{42}, -2, 1},
 323                 {"with negative second index", []int{42}, 1, -1},
 324                 {"with out-of-bounds first index", []int{42}, 2, 3},
 325                 {"with out-of-bounds second index", []int{42}, 0, 2},
 326                 {"with invalid i>j", []int{42}, 1, 0},
 327         } {
 328                 if !panics(func() { Delete(test.s, test.i, test.j) }) {
 329                         t.Errorf("Delete %s: got no panic, want panic", test.name)
 330                 }
 331         }
 332 }
 333
 334 func TestClone(t *testing.T) {
 335         s1 := []int{1, 2, 3}
 336         s2 := Clone(s1)
 337         if !Equal(s1, s2) {
 338                 t.Errorf("Clone(%v) = %v, want %v", s1, s2, s1)
 339         }
 340         s1[0] = 4
 341         want := []int{1, 2, 3}
 342         if !Equal(s2, want) {
 343                 t.Errorf("Clone(%v) changed unexpectedly to %v", want, s2)
 344         }
 345         if got := Clone([]int(nil)); got != nil {
 346                 t.Errorf("Clone(nil) = %#v, want nil", got)
 347         }
 348         if got := Clone(s1[:0]); got == nil || len(got) != 0 {
 349                 t.Errorf("Clone(%v) = %#v, want %#v", s1[:0], got, s1[:0])
 350         }
 351 }
 352
 353 var compactTests = []struct {
 354         name string
 355         s    []int
 356         want []int
 357 }{
 358         {
 359                 "nil",
 360                 nil,
 361                 nil,
 362         },
 363         {
 364                 "one",
 365                 []int{1},
 366                 []int{1},
 367         },
 368         {
 369                 "sorted",
 370                 []int{1, 2, 3},
 371                 []int{1, 2, 3},
 372         },
 373         {
 374                 "1 item",
 375                 []int{1, 1, 2},
 376                 []int{1, 2},
 377         },
 378         {
 379                 "unsorted",
 380                 []int{1, 2, 1},
 381                 []int{1, 2, 1},
 382         },
 383         {
 384                 "many",
 385                 []int{1, 2, 2, 3, 3, 4},
 386                 []int{1, 2, 3, 4},
 387         },
 388 }
 389
 390 func TestCompact(t *testing.T) {
 391         for _, test := range compactTests {
 392                 copy := Clone(test.s)
 393                 if got := Compact(copy); !Equal(got, test.want) {
 394                         t.Errorf("Compact(%v) = %v, want %v", test.s, got, test.want)
 395                 }
 396         }
 397 }
 398
 399 func BenchmarkCompact(b *testing.B) {
 400         for _, c := range compactTests {
 401                 b.Run(c.name, func(b *testing.B) {
 402                         ss := make([]int, 0, 64)
 403                         for k := 0; k < b.N; k++ {
 404                                 ss = ss[:0]
 405                                 ss = append(ss, c.s...)
 406                                 _ = Compact(ss)
 407                         }
 408                 })
 409         }
 410
 411 }
 412
 413 func TestCompactFunc(t *testing.T) {
 414         for _, test := range compactTests {
 415                 copy := Clone(test.s)
 416                 if got := CompactFunc(copy, equal[int]); !Equal(got, test.want) {
 417                         t.Errorf("CompactFunc(%v, equal[int]) = %v, want %v", test.s, got, test.want)
 418                 }
 419         }
 420
 421         s1 := []string{"a", "a", "A", "B", "b"}
 422         copy := Clone(s1)
 423         want := []string{"a", "B"}
 424         if got := CompactFunc(copy, strings.EqualFold); !Equal(got, want) {
 425                 t.Errorf("CompactFunc(%v, strings.EqualFold) = %v, want %v", s1, got, want)
 426         }
 427 }
 428
 429 func TestGrow(t *testing.T) {
 430         s1 := []int{1, 2, 3}
 431
 432         copy := Clone(s1)
 433         s2 := Grow(copy, 1000)
 434         if !Equal(s1, s2) {
 435                 t.Errorf("Grow(%v) = %v, want %v", s1, s2, s1)
 436         }
 437         if cap(s2) < 1000+len(s1) {
 438                 t.Errorf("after Grow(%v) cap = %d, want >= %d", s1, cap(s2), 1000+len(s1))
 439         }
 440
 441         // Test mutation of elements between length and capacity.
 442         copy = Clone(s1)
 443         s3 := Grow(copy[:1], 2)[:3]
 444         if !Equal(s1, s3) {
 445                 t.Errorf("Grow should not mutate elements between length and capacity")
 446         }
 447         s3 = Grow(copy[:1], 1000)[:3]
 448         if !Equal(s1, s3) {
 449                 t.Errorf("Grow should not mutate elements between length and capacity")
 450         }
 451
 452         // Test number of allocations.
 453         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)) }); n != 0 {
 454                 t.Errorf("Grow should not allocate when given sufficient capacity; allocated %v times", n)
 455         }
 456         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)+1) }); n != 1 {
 457                 errorf := t.Errorf
 458                 if race.Enabled {
 459                         errorf = t.Logf // this allocates multiple times in race detector mode
 460                 }
 461                 errorf("Grow should allocate once when given insufficient capacity; allocated %v times", n)
 462         }
 463
 464         // Test for negative growth sizes.
 465         var gotPanic bool
 466         func() {
 467                 defer func() { gotPanic = recover() != nil }()
 468                 Grow(s1, -1)
 469         }()
 470         if !gotPanic {
 471                 t.Errorf("Grow(-1) did not panic; expected a panic")
 472         }
 473 }
 474
 475 func TestClip(t *testing.T) {
 476         s1 := []int{1, 2, 3, 4, 5, 6}[:3]
 477         orig := Clone(s1)
 478         if len(s1) != 3 {
 479                 t.Errorf("len(%v) = %d, want 3", s1, len(s1))
 480         }
 481         if cap(s1) < 6 {
 482                 t.Errorf("cap(%v[:3]) = %d, want >= 6", orig, cap(s1))
 483         }
 484         s2 := Clip(s1)
 485         if !Equal(s1, s2) {
 486                 t.Errorf("Clip(%v) = %v, want %v", s1, s2, s1)
 487         }
 488         if cap(s2) != 3 {
 489                 t.Errorf("cap(Clip(%v)) = %d, want 3", orig, cap(s2))
 490         }
 491 }
 492
 493 // naiveReplace is a baseline implementation to the Replace function.
 494 func naiveReplace[S ~[]E, E any](s S, i, j int, v ...E) S {
 495         s = Delete(s, i, j)
 496         s = Insert(s, i, v...)
 497         return s
 498 }
 499
 500 func TestReplace(t *testing.T) {
 501         for _, test := range []struct {
 502                 s, v []int
 503                 i, j int
 504         }{
 505                 {}, // all zero value
 506                 {
 507                         s: []int{1, 2, 3, 4},
 508                         v: []int{5},
 509                         i: 1,
 510                         j: 2,
 511                 },
 512                 {
 513                         s: []int{1, 2, 3, 4},
 514                         v: []int{5, 6, 7, 8},
 515                         i: 1,
 516                         j: 2,
 517                 },
 518                 {
 519                         s: func() []int {
 520                                 s := make([]int, 3, 20)
 521                                 s[0] = 0
 522                                 s[1] = 1
 523                                 s[2] = 2
 524                                 return s
 525                         }(),
 526                         v: []int{3, 4, 5, 6, 7},
 527                         i: 0,
 528                         j: 1,
 529                 },
 530         } {
 531                 ss, vv := Clone(test.s), Clone(test.v)
 532                 want := naiveReplace(ss, test.i, test.j, vv...)
 533                 got := Replace(test.s, test.i, test.j, test.v...)
 534                 if !Equal(got, want) {
 535                         t.Errorf("Replace(%v, %v, %v, %v) = %v, want %v", test.s, test.i, test.j, test.v, got, want)
 536                 }
 537         }
 538 }
 539
 540 func TestReplacePanics(t *testing.T) {
 541         for _, test := range []struct {
 542                 name string
 543                 s, v []int
 544                 i, j int
 545         }{
 546                 {"indexes out of order", []int{1, 2}, []int{3}, 2, 1},
 547                 {"large index", []int{1, 2}, []int{3}, 1, 10},
 548                 {"negative index", []int{1, 2}, []int{3}, -1, 2},
 549         } {
 550                 ss, vv := Clone(test.s), Clone(test.v)
 551                 if !panics(func() { Replace(ss, test.i, test.j, vv...) }) {
 552                         t.Errorf("Replace %s: should have panicked", test.name)
 553                 }
 554         }
 555 }
 556
 557 func BenchmarkReplace(b *testing.B) {
 558         cases := []struct {
 559                 name string
 560                 s, v func() []int
 561                 i, j int
 562         }{
 563                 {
 564                         name: "fast",
 565                         s: func() []int {
 566                                 return make([]int, 100)
 567                         },
 568                         v: func() []int {
 569                                 return make([]int, 20)
 570                         },
 571                         i: 10,
 572                         j: 40,
 573                 },
 574                 {
 575                         name: "slow",
 576                         s: func() []int {
 577                                 return make([]int, 100)
 578                         },
 579                         v: func() []int {
 580                                 return make([]int, 20)
 581                         },
 582                         i: 0,
 583                         j: 2,
 584                 },
 585         }
 586
 587         for _, c := range cases {
 588                 b.Run("naive-"+c.name, func(b *testing.B) {
 589                         for k := 0; k < b.N; k++ {
 590                                 s := c.s()
 591                                 v := c.v()
 592                                 _ = naiveReplace(s, c.i, c.j, v...)
 593                         }
 594                 })
 595                 b.Run("optimized-"+c.name, func(b *testing.B) {
 596                         for k := 0; k < b.N; k++ {
 597                                 s := c.s()
 598                                 v := c.v()
 599                                 _ = Replace(s, c.i, c.j, v...)
 600                         }
 601                 })
 602         }
 603
 604 }