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         if !testenv.OptimizationOff() && !race.Enabled {
 261                 // Allocations should be amortized.
 262                 const count = 50
 263                 n := testing.AllocsPerRun(10, func() {
 264                         s := []int{1, 2, 3}
 265                         for i := 0; i < count; i++ {
 266                                 s = Insert(s, 0, 1)
 267                         }
 268                 })
 269                 if n > count/2 {
 270                         t.Errorf("too many allocations inserting %d elements: got %v, want less than %d", count, n, count/2)
 271                 }
 272         }
 273 }
 274
 275 var deleteTests = []struct {
 276         s    []int
 277         i, j int
 278         want []int
 279 }{
 280         {
 281                 []int{1, 2, 3},
 282                 0,
 283                 0,
 284                 []int{1, 2, 3},
 285         },
 286         {
 287                 []int{1, 2, 3},
 288                 0,
 289                 1,
 290                 []int{2, 3},
 291         },
 292         {
 293                 []int{1, 2, 3},
 294                 3,
 295                 3,
 296                 []int{1, 2, 3},
 297         },
 298         {
 299                 []int{1, 2, 3},
 300                 0,
 301                 2,
 302                 []int{3},
 303         },
 304         {
 305                 []int{1, 2, 3},
 306                 0,
 307                 3,
 308                 []int{},
 309         },
 310 }
 311
 312 func TestDelete(t *testing.T) {
 313         for _, test := range deleteTests {
 314                 copy := Clone(test.s)
 315                 if got := Delete(copy, test.i, test.j); !Equal(got, test.want) {
 316                         t.Errorf("Delete(%v, %d, %d) = %v, want %v", test.s, test.i, test.j, got, test.want)
 317                 }
 318         }
 319 }
 320
 321 var deleteFuncTests = []struct {
 322         s    []int
 323         fn   func(int) bool
 324         want []int
 325 }{
 326         {
 327                 nil,
 328                 func(int) bool { return true },
 329                 nil,
 330         },
 331         {
 332                 []int{1, 2, 3},
 333                 func(int) bool { return true },
 334                 nil,
 335         },
 336         {
 337                 []int{1, 2, 3},
 338                 func(int) bool { return false },
 339                 []int{1, 2, 3},
 340         },
 341         {
 342                 []int{1, 2, 3},
 343                 func(i int) bool { return i > 2 },
 344                 []int{1, 2},
 345         },
 346         {
 347                 []int{1, 2, 3},
 348                 func(i int) bool { return i < 2 },
 349                 []int{2, 3},
 350         },
 351         {
 352                 []int{10, 2, 30},
 353                 func(i int) bool { return i >= 10 },
 354                 []int{2},
 355         },
 356 }
 357
 358 func TestDeleteFunc(t *testing.T) {
 359         for i, test := range deleteFuncTests {
 360                 copy := Clone(test.s)
 361                 if got := DeleteFunc(copy, test.fn); !Equal(got, test.want) {
 362                         t.Errorf("DeleteFunc case %d: got %v, want %v", i, got, test.want)
 363                 }
 364         }
 365 }
 366
 367 func panics(f func()) (b bool) {
 368         defer func() {
 369                 if x := recover(); x != nil {
 370                         b = true
 371                 }
 372         }()
 373         f()
 374         return false
 375 }
 376
 377 func TestDeletePanics(t *testing.T) {
 378         for _, test := range []struct {
 379                 name string
 380                 s    []int
 381                 i, j int
 382         }{
 383                 {"with negative first index", []int{42}, -2, 1},
 384                 {"with negative second index", []int{42}, 1, -1},
 385                 {"with out-of-bounds first index", []int{42}, 2, 3},
 386                 {"with out-of-bounds second index", []int{42}, 0, 2},
 387                 {"with invalid i>j", []int{42}, 1, 0},
 388         } {
 389                 if !panics(func() { Delete(test.s, test.i, test.j) }) {
 390                         t.Errorf("Delete %s: got no panic, want panic", test.name)
 391                 }
 392         }
 393 }
 394
 395 func TestClone(t *testing.T) {
 396         s1 := []int{1, 2, 3}
 397         s2 := Clone(s1)
 398         if !Equal(s1, s2) {
 399                 t.Errorf("Clone(%v) = %v, want %v", s1, s2, s1)
 400         }
 401         s1[0] = 4
 402         want := []int{1, 2, 3}
 403         if !Equal(s2, want) {
 404                 t.Errorf("Clone(%v) changed unexpectedly to %v", want, s2)
 405         }
 406         if got := Clone([]int(nil)); got != nil {
 407                 t.Errorf("Clone(nil) = %#v, want nil", got)
 408         }
 409         if got := Clone(s1[:0]); got == nil || len(got) != 0 {
 410                 t.Errorf("Clone(%v) = %#v, want %#v", s1[:0], got, s1[:0])
 411         }
 412 }
 413
 414 var compactTests = []struct {
 415         name string
 416         s    []int
 417         want []int
 418 }{
 419         {
 420                 "nil",
 421                 nil,
 422                 nil,
 423         },
 424         {
 425                 "one",
 426                 []int{1},
 427                 []int{1},
 428         },
 429         {
 430                 "sorted",
 431                 []int{1, 2, 3},
 432                 []int{1, 2, 3},
 433         },
 434         {
 435                 "1 item",
 436                 []int{1, 1, 2},
 437                 []int{1, 2},
 438         },
 439         {
 440                 "unsorted",
 441                 []int{1, 2, 1},
 442                 []int{1, 2, 1},
 443         },
 444         {
 445                 "many",
 446                 []int{1, 2, 2, 3, 3, 4},
 447                 []int{1, 2, 3, 4},
 448         },
 449 }
 450
 451 func TestCompact(t *testing.T) {
 452         for _, test := range compactTests {
 453                 copy := Clone(test.s)
 454                 if got := Compact(copy); !Equal(got, test.want) {
 455                         t.Errorf("Compact(%v) = %v, want %v", test.s, got, test.want)
 456                 }
 457         }
 458 }
 459
 460 func BenchmarkCompact(b *testing.B) {
 461         for _, c := range compactTests {
 462                 b.Run(c.name, func(b *testing.B) {
 463                         ss := make([]int, 0, 64)
 464                         for k := 0; k < b.N; k++ {
 465                                 ss = ss[:0]
 466                                 ss = append(ss, c.s...)
 467                                 _ = Compact(ss)
 468                         }
 469                 })
 470         }
 471
 472 }
 473
 474 func TestCompactFunc(t *testing.T) {
 475         for _, test := range compactTests {
 476                 copy := Clone(test.s)
 477                 if got := CompactFunc(copy, equal[int]); !Equal(got, test.want) {
 478                         t.Errorf("CompactFunc(%v, equal[int]) = %v, want %v", test.s, got, test.want)
 479                 }
 480         }
 481
 482         s1 := []string{"a", "a", "A", "B", "b"}
 483         copy := Clone(s1)
 484         want := []string{"a", "B"}
 485         if got := CompactFunc(copy, strings.EqualFold); !Equal(got, want) {
 486                 t.Errorf("CompactFunc(%v, strings.EqualFold) = %v, want %v", s1, got, want)
 487         }
 488 }
 489
 490 func TestGrow(t *testing.T) {
 491         s1 := []int{1, 2, 3}
 492
 493         copy := Clone(s1)
 494         s2 := Grow(copy, 1000)
 495         if !Equal(s1, s2) {
 496                 t.Errorf("Grow(%v) = %v, want %v", s1, s2, s1)
 497         }
 498         if cap(s2) < 1000+len(s1) {
 499                 t.Errorf("after Grow(%v) cap = %d, want >= %d", s1, cap(s2), 1000+len(s1))
 500         }
 501
 502         // Test mutation of elements between length and capacity.
 503         copy = Clone(s1)
 504         s3 := Grow(copy[:1], 2)[:3]
 505         if !Equal(s1, s3) {
 506                 t.Errorf("Grow should not mutate elements between length and capacity")
 507         }
 508         s3 = Grow(copy[:1], 1000)[:3]
 509         if !Equal(s1, s3) {
 510                 t.Errorf("Grow should not mutate elements between length and capacity")
 511         }
 512
 513         // Test number of allocations.
 514         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)) }); n != 0 {
 515                 t.Errorf("Grow should not allocate when given sufficient capacity; allocated %v times", n)
 516         }
 517         if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)+1) }); n != 1 {
 518                 errorf := t.Errorf
 519                 if race.Enabled || testenv.OptimizationOff() {
 520                         errorf = t.Logf // this allocates multiple times in race detector mode
 521                 }
 522                 errorf("Grow should allocate once when given insufficient capacity; allocated %v times", n)
 523         }
 524
 525         // Test for negative growth sizes.
 526         var gotPanic bool
 527         func() {
 528                 defer func() { gotPanic = recover() != nil }()
 529                 Grow(s1, -1)
 530         }()
 531         if !gotPanic {
 532                 t.Errorf("Grow(-1) did not panic; expected a panic")
 533         }
 534 }
 535
 536 func TestClip(t *testing.T) {
 537         s1 := []int{1, 2, 3, 4, 5, 6}[:3]
 538         orig := Clone(s1)
 539         if len(s1) != 3 {
 540                 t.Errorf("len(%v) = %d, want 3", s1, len(s1))
 541         }
 542         if cap(s1) < 6 {
 543                 t.Errorf("cap(%v[:3]) = %d, want >= 6", orig, cap(s1))
 544         }
 545         s2 := Clip(s1)
 546         if !Equal(s1, s2) {
 547                 t.Errorf("Clip(%v) = %v, want %v", s1, s2, s1)
 548         }
 549         if cap(s2) != 3 {
 550                 t.Errorf("cap(Clip(%v)) = %d, want 3", orig, cap(s2))
 551         }
 552 }
 553
 554 // naiveReplace is a baseline implementation to the Replace function.
 555 func naiveReplace[S ~[]E, E any](s S, i, j int, v ...E) S {
 556         s = Delete(s, i, j)
 557         s = Insert(s, i, v...)
 558         return s
 559 }
 560
 561 func TestReplace(t *testing.T) {
 562         for _, test := range []struct {
 563                 s, v []int
 564                 i, j int
 565         }{
 566                 {}, // all zero value
 567                 {
 568                         s: []int{1, 2, 3, 4},
 569                         v: []int{5},
 570                         i: 1,
 571                         j: 2,
 572                 },
 573                 {
 574                         s: []int{1, 2, 3, 4},
 575                         v: []int{5, 6, 7, 8},
 576                         i: 1,
 577                         j: 2,
 578                 },
 579                 {
 580                         s: func() []int {
 581                                 s := make([]int, 3, 20)
 582                                 s[0] = 0
 583                                 s[1] = 1
 584                                 s[2] = 2
 585                                 return s
 586                         }(),
 587                         v: []int{3, 4, 5, 6, 7},
 588                         i: 0,
 589                         j: 1,
 590                 },
 591         } {
 592                 ss, vv := Clone(test.s), Clone(test.v)
 593                 want := naiveReplace(ss, test.i, test.j, vv...)
 594                 got := Replace(test.s, test.i, test.j, test.v...)
 595                 if !Equal(got, want) {
 596                         t.Errorf("Replace(%v, %v, %v, %v) = %v, want %v", test.s, test.i, test.j, test.v, got, want)
 597                 }
 598         }
 599 }
 600
 601 func TestReplacePanics(t *testing.T) {
 602         for _, test := range []struct {
 603                 name string
 604                 s, v []int
 605                 i, j int
 606         }{
 607                 {"indexes out of order", []int{1, 2}, []int{3}, 2, 1},
 608                 {"large index", []int{1, 2}, []int{3}, 1, 10},
 609                 {"negative index", []int{1, 2}, []int{3}, -1, 2},
 610         } {
 611                 ss, vv := Clone(test.s), Clone(test.v)
 612                 if !panics(func() { Replace(ss, test.i, test.j, vv...) }) {
 613                         t.Errorf("Replace %s: should have panicked", test.name)
 614                 }
 615         }
 616 }
 617
 618 func BenchmarkReplace(b *testing.B) {
 619         cases := []struct {
 620                 name string
 621                 s, v func() []int
 622                 i, j int
 623         }{
 624                 {
 625                         name: "fast",
 626                         s: func() []int {
 627                                 return make([]int, 100)
 628                         },
 629                         v: func() []int {
 630                                 return make([]int, 20)
 631                         },
 632                         i: 10,
 633                         j: 40,
 634                 },
 635                 {
 636                         name: "slow",
 637                         s: func() []int {
 638                                 return make([]int, 100)
 639                         },
 640                         v: func() []int {
 641                                 return make([]int, 20)
 642                         },
 643                         i: 0,
 644                         j: 2,
 645                 },
 646         }
 647
 648         for _, c := range cases {
 649                 b.Run("naive-"+c.name, func(b *testing.B) {
 650                         for k := 0; k < b.N; k++ {
 651                                 s := c.s()
 652                                 v := c.v()
 653                                 _ = naiveReplace(s, c.i, c.j, v...)
 654                         }
 655                 })
 656                 b.Run("optimized-"+c.name, func(b *testing.B) {
 657                         for k := 0; k < b.N; k++ {
 658                                 s := c.s()
 659                                 v := c.v()
 660                                 _ = Replace(s, c.i, c.j, v...)
 661                         }
 662                 })
 663         }
 664
 665 }