Source file
src/slices/slices_test.go
1
2
3
4
5 package slices_test
6
7 import (
8 "cmp"
9 "internal/race"
10 "internal/testenv"
11 "math"
12 . "slices"
13 "strings"
14 "testing"
15 )
16
17 var equalIntTests = []struct {
18 s1, s2 []int
19 want bool
20 }{
21 {
22 []int{1},
23 nil,
24 false,
25 },
26 {
27 []int{},
28 nil,
29 true,
30 },
31 {
32 []int{1, 2, 3},
33 []int{1, 2, 3},
34 true,
35 },
36 {
37 []int{1, 2, 3},
38 []int{1, 2, 3, 4},
39 false,
40 },
41 }
42
43 var equalFloatTests = []struct {
44 s1, s2 []float64
45 wantEqual bool
46 wantEqualNaN bool
47 }{
48 {
49 []float64{1, 2},
50 []float64{1, 2},
51 true,
52 true,
53 },
54 {
55 []float64{1, 2, math.NaN()},
56 []float64{1, 2, math.NaN()},
57 false,
58 true,
59 },
60 }
61
62 func TestEqual(t *testing.T) {
63 for _, test := range equalIntTests {
64 if got := Equal(test.s1, test.s2); got != test.want {
65 t.Errorf("Equal(%v, %v) = %t, want %t", test.s1, test.s2, got, test.want)
66 }
67 }
68 for _, test := range equalFloatTests {
69 if got := Equal(test.s1, test.s2); got != test.wantEqual {
70 t.Errorf("Equal(%v, %v) = %t, want %t", test.s1, test.s2, got, test.wantEqual)
71 }
72 }
73 }
74
75
76 func equal[T comparable](v1, v2 T) bool {
77 return v1 == v2
78 }
79
80
81 func equalNaN[T comparable](v1, v2 T) bool {
82 isNaN := func(f T) bool { return f != f }
83 return v1 == v2 || (isNaN(v1) && isNaN(v2))
84 }
85
86
87 func offByOne(v1, v2 int) bool {
88 return v1 == v2+1 || v1 == v2-1
89 }
90
91 func TestEqualFunc(t *testing.T) {
92 for _, test := range equalIntTests {
93 if got := EqualFunc(test.s1, test.s2, equal[int]); got != test.want {
94 t.Errorf("EqualFunc(%v, %v, equal[int]) = %t, want %t", test.s1, test.s2, got, test.want)
95 }
96 }
97 for _, test := range equalFloatTests {
98 if got := EqualFunc(test.s1, test.s2, equal[float64]); got != test.wantEqual {
99 t.Errorf("Equal(%v, %v, equal[float64]) = %t, want %t", test.s1, test.s2, got, test.wantEqual)
100 }
101 if got := EqualFunc(test.s1, test.s2, equalNaN[float64]); got != test.wantEqualNaN {
102 t.Errorf("Equal(%v, %v, equalNaN[float64]) = %t, want %t", test.s1, test.s2, got, test.wantEqualNaN)
103 }
104 }
105
106 s1 := []int{1, 2, 3}
107 s2 := []int{2, 3, 4}
108 if EqualFunc(s1, s1, offByOne) {
109 t.Errorf("EqualFunc(%v, %v, offByOne) = true, want false", s1, s1)
110 }
111 if !EqualFunc(s1, s2, offByOne) {
112 t.Errorf("EqualFunc(%v, %v, offByOne) = false, want true", s1, s2)
113 }
114
115 s3 := []string{"a", "b", "c"}
116 s4 := []string{"A", "B", "C"}
117 if !EqualFunc(s3, s4, strings.EqualFold) {
118 t.Errorf("EqualFunc(%v, %v, strings.EqualFold) = false, want true", s3, s4)
119 }
120
121 cmpIntString := func(v1 int, v2 string) bool {
122 return string(rune(v1)-1+'a') == v2
123 }
124 if !EqualFunc(s1, s3, cmpIntString) {
125 t.Errorf("EqualFunc(%v, %v, cmpIntString) = false, want true", s1, s3)
126 }
127 }
128
129 func BenchmarkEqualFunc_Large(b *testing.B) {
130 type Large [4 * 1024]byte
131
132 xs := make([]Large, 1024)
133 ys := make([]Large, 1024)
134 for i := 0; i < b.N; i++ {
135 _ = EqualFunc(xs, ys, func(x, y Large) bool { return x == y })
136 }
137 }
138
139 var compareIntTests = []struct {
140 s1, s2 []int
141 want int
142 }{
143 {
144 []int{1},
145 []int{1},
146 0,
147 },
148 {
149 []int{1},
150 []int{},
151 1,
152 },
153 {
154 []int{},
155 []int{1},
156 -1,
157 },
158 {
159 []int{},
160 []int{},
161 0,
162 },
163 {
164 []int{1, 2, 3},
165 []int{1, 2, 3},
166 0,
167 },
168 {
169 []int{1, 2, 3},
170 []int{1, 2, 3, 4},
171 -1,
172 },
173 {
174 []int{1, 2, 3, 4},
175 []int{1, 2, 3},
176 +1,
177 },
178 {
179 []int{1, 2, 3},
180 []int{1, 4, 3},
181 -1,
182 },
183 {
184 []int{1, 4, 3},
185 []int{1, 2, 3},
186 +1,
187 },
188 {
189 []int{1, 4, 3},
190 []int{1, 2, 3, 8, 9},
191 +1,
192 },
193 }
194
195 var compareFloatTests = []struct {
196 s1, s2 []float64
197 want int
198 }{
199 {
200 []float64{},
201 []float64{},
202 0,
203 },
204 {
205 []float64{1},
206 []float64{1},
207 0,
208 },
209 {
210 []float64{math.NaN()},
211 []float64{math.NaN()},
212 0,
213 },
214 {
215 []float64{1, 2, math.NaN()},
216 []float64{1, 2, math.NaN()},
217 0,
218 },
219 {
220 []float64{1, math.NaN(), 3},
221 []float64{1, math.NaN(), 4},
222 -1,
223 },
224 {
225 []float64{1, math.NaN(), 3},
226 []float64{1, 2, 4},
227 -1,
228 },
229 {
230 []float64{1, math.NaN(), 3},
231 []float64{1, 2, math.NaN()},
232 -1,
233 },
234 {
235 []float64{1, 2, 3},
236 []float64{1, 2, math.NaN()},
237 +1,
238 },
239 {
240 []float64{1, 2, 3},
241 []float64{1, math.NaN(), 3},
242 +1,
243 },
244 {
245 []float64{1, math.NaN(), 3, 4},
246 []float64{1, 2, math.NaN()},
247 -1,
248 },
249 }
250
251 func TestCompare(t *testing.T) {
252 intWant := func(want bool) string {
253 if want {
254 return "0"
255 }
256 return "!= 0"
257 }
258 for _, test := range equalIntTests {
259 if got := Compare(test.s1, test.s2); (got == 0) != test.want {
260 t.Errorf("Compare(%v, %v) = %d, want %s", test.s1, test.s2, got, intWant(test.want))
261 }
262 }
263 for _, test := range equalFloatTests {
264 if got := Compare(test.s1, test.s2); (got == 0) != test.wantEqualNaN {
265 t.Errorf("Compare(%v, %v) = %d, want %s", test.s1, test.s2, got, intWant(test.wantEqualNaN))
266 }
267 }
268
269 for _, test := range compareIntTests {
270 if got := Compare(test.s1, test.s2); got != test.want {
271 t.Errorf("Compare(%v, %v) = %d, want %d", test.s1, test.s2, got, test.want)
272 }
273 }
274 for _, test := range compareFloatTests {
275 if got := Compare(test.s1, test.s2); got != test.want {
276 t.Errorf("Compare(%v, %v) = %d, want %d", test.s1, test.s2, got, test.want)
277 }
278 }
279 }
280
281 func equalToCmp[T comparable](eq func(T, T) bool) func(T, T) int {
282 return func(v1, v2 T) int {
283 if eq(v1, v2) {
284 return 0
285 }
286 return 1
287 }
288 }
289
290 func TestCompareFunc(t *testing.T) {
291 intWant := func(want bool) string {
292 if want {
293 return "0"
294 }
295 return "!= 0"
296 }
297 for _, test := range equalIntTests {
298 if got := CompareFunc(test.s1, test.s2, equalToCmp(equal[int])); (got == 0) != test.want {
299 t.Errorf("CompareFunc(%v, %v, equalToCmp(equal[int])) = %d, want %s", test.s1, test.s2, got, intWant(test.want))
300 }
301 }
302 for _, test := range equalFloatTests {
303 if got := CompareFunc(test.s1, test.s2, equalToCmp(equal[float64])); (got == 0) != test.wantEqual {
304 t.Errorf("CompareFunc(%v, %v, equalToCmp(equal[float64])) = %d, want %s", test.s1, test.s2, got, intWant(test.wantEqual))
305 }
306 }
307
308 for _, test := range compareIntTests {
309 if got := CompareFunc(test.s1, test.s2, cmp.Compare[int]); got != test.want {
310 t.Errorf("CompareFunc(%v, %v, cmp[int]) = %d, want %d", test.s1, test.s2, got, test.want)
311 }
312 }
313 for _, test := range compareFloatTests {
314 if got := CompareFunc(test.s1, test.s2, cmp.Compare[float64]); got != test.want {
315 t.Errorf("CompareFunc(%v, %v, cmp[float64]) = %d, want %d", test.s1, test.s2, got, test.want)
316 }
317 }
318
319 s1 := []int{1, 2, 3}
320 s2 := []int{2, 3, 4}
321 if got := CompareFunc(s1, s2, equalToCmp(offByOne)); got != 0 {
322 t.Errorf("CompareFunc(%v, %v, offByOne) = %d, want 0", s1, s2, got)
323 }
324
325 s3 := []string{"a", "b", "c"}
326 s4 := []string{"A", "B", "C"}
327 if got := CompareFunc(s3, s4, strings.Compare); got != 1 {
328 t.Errorf("CompareFunc(%v, %v, strings.Compare) = %d, want 1", s3, s4, got)
329 }
330
331 compareLower := func(v1, v2 string) int {
332 return strings.Compare(strings.ToLower(v1), strings.ToLower(v2))
333 }
334 if got := CompareFunc(s3, s4, compareLower); got != 0 {
335 t.Errorf("CompareFunc(%v, %v, compareLower) = %d, want 0", s3, s4, got)
336 }
337
338 cmpIntString := func(v1 int, v2 string) int {
339 return strings.Compare(string(rune(v1)-1+'a'), v2)
340 }
341 if got := CompareFunc(s1, s3, cmpIntString); got != 0 {
342 t.Errorf("CompareFunc(%v, %v, cmpIntString) = %d, want 0", s1, s3, got)
343 }
344 }
345
346 var indexTests = []struct {
347 s []int
348 v int
349 want int
350 }{
351 {
352 nil,
353 0,
354 -1,
355 },
356 {
357 []int{},
358 0,
359 -1,
360 },
361 {
362 []int{1, 2, 3},
363 2,
364 1,
365 },
366 {
367 []int{1, 2, 2, 3},
368 2,
369 1,
370 },
371 {
372 []int{1, 2, 3, 2},
373 2,
374 1,
375 },
376 }
377
378 func TestIndex(t *testing.T) {
379 for _, test := range indexTests {
380 if got := Index(test.s, test.v); got != test.want {
381 t.Errorf("Index(%v, %v) = %d, want %d", test.s, test.v, got, test.want)
382 }
383 }
384 }
385
386 func equalToIndex[T any](f func(T, T) bool, v1 T) func(T) bool {
387 return func(v2 T) bool {
388 return f(v1, v2)
389 }
390 }
391
392 func BenchmarkIndex_Large(b *testing.B) {
393 type Large [4 * 1024]byte
394
395 ss := make([]Large, 1024)
396 for i := 0; i < b.N; i++ {
397 _ = Index(ss, Large{1})
398 }
399 }
400
401 func TestIndexFunc(t *testing.T) {
402 for _, test := range indexTests {
403 if got := IndexFunc(test.s, equalToIndex(equal[int], test.v)); got != test.want {
404 t.Errorf("IndexFunc(%v, equalToIndex(equal[int], %v)) = %d, want %d", test.s, test.v, got, test.want)
405 }
406 }
407
408 s1 := []string{"hi", "HI"}
409 if got := IndexFunc(s1, equalToIndex(equal[string], "HI")); got != 1 {
410 t.Errorf("IndexFunc(%v, equalToIndex(equal[string], %q)) = %d, want %d", s1, "HI", got, 1)
411 }
412 if got := IndexFunc(s1, equalToIndex(strings.EqualFold, "HI")); got != 0 {
413 t.Errorf("IndexFunc(%v, equalToIndex(strings.EqualFold, %q)) = %d, want %d", s1, "HI", got, 0)
414 }
415 }
416
417 func BenchmarkIndexFunc_Large(b *testing.B) {
418 type Large [4 * 1024]byte
419
420 ss := make([]Large, 1024)
421 for i := 0; i < b.N; i++ {
422 _ = IndexFunc(ss, func(e Large) bool {
423 return e == Large{1}
424 })
425 }
426 }
427
428 func TestContains(t *testing.T) {
429 for _, test := range indexTests {
430 if got := Contains(test.s, test.v); got != (test.want != -1) {
431 t.Errorf("Contains(%v, %v) = %t, want %t", test.s, test.v, got, test.want != -1)
432 }
433 }
434 }
435
436 func TestContainsFunc(t *testing.T) {
437 for _, test := range indexTests {
438 if got := ContainsFunc(test.s, equalToIndex(equal[int], test.v)); got != (test.want != -1) {
439 t.Errorf("ContainsFunc(%v, equalToIndex(equal[int], %v)) = %t, want %t", test.s, test.v, got, test.want != -1)
440 }
441 }
442
443 s1 := []string{"hi", "HI"}
444 if got := ContainsFunc(s1, equalToIndex(equal[string], "HI")); got != true {
445 t.Errorf("ContainsFunc(%v, equalToContains(equal[string], %q)) = %t, want %t", s1, "HI", got, true)
446 }
447 if got := ContainsFunc(s1, equalToIndex(equal[string], "hI")); got != false {
448 t.Errorf("ContainsFunc(%v, equalToContains(strings.EqualFold, %q)) = %t, want %t", s1, "hI", got, false)
449 }
450 if got := ContainsFunc(s1, equalToIndex(strings.EqualFold, "hI")); got != true {
451 t.Errorf("ContainsFunc(%v, equalToContains(strings.EqualFold, %q)) = %t, want %t", s1, "hI", got, true)
452 }
453 }
454
455 var insertTests = []struct {
456 s []int
457 i int
458 add []int
459 want []int
460 }{
461 {
462 []int{1, 2, 3},
463 0,
464 []int{4},
465 []int{4, 1, 2, 3},
466 },
467 {
468 []int{1, 2, 3},
469 1,
470 []int{4},
471 []int{1, 4, 2, 3},
472 },
473 {
474 []int{1, 2, 3},
475 3,
476 []int{4},
477 []int{1, 2, 3, 4},
478 },
479 {
480 []int{1, 2, 3},
481 2,
482 []int{4, 5},
483 []int{1, 2, 4, 5, 3},
484 },
485 }
486
487 func TestInsert(t *testing.T) {
488 s := []int{1, 2, 3}
489 if got := Insert(s, 0); !Equal(got, s) {
490 t.Errorf("Insert(%v, 0) = %v, want %v", s, got, s)
491 }
492 for _, test := range insertTests {
493 copy := Clone(test.s)
494 if got := Insert(copy, test.i, test.add...); !Equal(got, test.want) {
495 t.Errorf("Insert(%v, %d, %v...) = %v, want %v", test.s, test.i, test.add, got, test.want)
496 }
497 }
498
499 if !testenv.OptimizationOff() && !race.Enabled {
500
501 const count = 50
502 n := testing.AllocsPerRun(10, func() {
503 s := []int{1, 2, 3}
504 for i := 0; i < count; i++ {
505 s = Insert(s, 0, 1)
506 }
507 })
508 if n > count/2 {
509 t.Errorf("too many allocations inserting %d elements: got %v, want less than %d", count, n, count/2)
510 }
511 }
512 }
513
514 func TestInsertOverlap(t *testing.T) {
515 const N = 10
516 a := make([]int, N)
517 want := make([]int, 2*N)
518 for n := 0; n <= N; n++ {
519 for i := 0; i <= n; i++ {
520 for x := 0; x <= N; x++ {
521 for y := x; y <= N; y++ {
522 for k := 0; k < N; k++ {
523 a[k] = k
524 }
525 want = want[:0]
526 want = append(want, a[:i]...)
527 want = append(want, a[x:y]...)
528 want = append(want, a[i:n]...)
529 got := Insert(a[:n], i, a[x:y]...)
530 if !Equal(got, want) {
531 t.Errorf("Insert with overlap failed n=%d i=%d x=%d y=%d, got %v want %v", n, i, x, y, got, want)
532 }
533 }
534 }
535 }
536 }
537 }
538
539 func TestInsertPanics(t *testing.T) {
540 a := [3]int{}
541 b := [1]int{}
542 for _, test := range []struct {
543 name string
544 s []int
545 i int
546 v []int
547 }{
548
549 {"with negative index", a[:1:1], -1, nil},
550 {"with out-of-bounds index and > cap", a[:1:1], 2, nil},
551 {"with out-of-bounds index and = cap", a[:1:2], 2, nil},
552 {"with out-of-bounds index and < cap", a[:1:3], 2, nil},
553
554
555 {"with negative index", a[:1:1], -1, b[:]},
556 {"with out-of-bounds index and > cap", a[:1:1], 2, b[:]},
557 {"with out-of-bounds index and = cap", a[:1:2], 2, b[:]},
558 {"with out-of-bounds index and < cap", a[:1:3], 2, b[:]},
559 } {
560 if !panics(func() { _ = Insert(test.s, test.i, test.v...) }) {
561 t.Errorf("Insert %s: got no panic, want panic", test.name)
562 }
563 }
564 }
565
566 var deleteTests = []struct {
567 s []int
568 i, j int
569 want []int
570 }{
571 {
572 []int{1, 2, 3},
573 0,
574 0,
575 []int{1, 2, 3},
576 },
577 {
578 []int{1, 2, 3},
579 0,
580 1,
581 []int{2, 3},
582 },
583 {
584 []int{1, 2, 3},
585 3,
586 3,
587 []int{1, 2, 3},
588 },
589 {
590 []int{1, 2, 3},
591 0,
592 2,
593 []int{3},
594 },
595 {
596 []int{1, 2, 3},
597 0,
598 3,
599 []int{},
600 },
601 }
602
603 func TestDelete(t *testing.T) {
604 for _, test := range deleteTests {
605 copy := Clone(test.s)
606 if got := Delete(copy, test.i, test.j); !Equal(got, test.want) {
607 t.Errorf("Delete(%v, %d, %d) = %v, want %v", test.s, test.i, test.j, got, test.want)
608 }
609 }
610 }
611
612 var deleteFuncTests = []struct {
613 s []int
614 fn func(int) bool
615 want []int
616 }{
617 {
618 nil,
619 func(int) bool { return true },
620 nil,
621 },
622 {
623 []int{1, 2, 3},
624 func(int) bool { return true },
625 nil,
626 },
627 {
628 []int{1, 2, 3},
629 func(int) bool { return false },
630 []int{1, 2, 3},
631 },
632 {
633 []int{1, 2, 3},
634 func(i int) bool { return i > 2 },
635 []int{1, 2},
636 },
637 {
638 []int{1, 2, 3},
639 func(i int) bool { return i < 2 },
640 []int{2, 3},
641 },
642 {
643 []int{10, 2, 30},
644 func(i int) bool { return i >= 10 },
645 []int{2},
646 },
647 }
648
649 func TestDeleteFunc(t *testing.T) {
650 for i, test := range deleteFuncTests {
651 copy := Clone(test.s)
652 if got := DeleteFunc(copy, test.fn); !Equal(got, test.want) {
653 t.Errorf("DeleteFunc case %d: got %v, want %v", i, got, test.want)
654 }
655 }
656 }
657
658 func panics(f func()) (b bool) {
659 defer func() {
660 if x := recover(); x != nil {
661 b = true
662 }
663 }()
664 f()
665 return false
666 }
667
668 func TestDeletePanics(t *testing.T) {
669 s := []int{0, 1, 2, 3, 4}
670 s = s[0:2]
671 _ = s[0:4]
672
673 for _, test := range []struct {
674 name string
675 s []int
676 i, j int
677 }{
678 {"with negative first index", []int{42}, -2, 1},
679 {"with negative second index", []int{42}, 1, -1},
680 {"with out-of-bounds first index", []int{42}, 2, 3},
681 {"with out-of-bounds second index", []int{42}, 0, 2},
682 {"with out-of-bounds both indexes", []int{42}, 2, 2},
683 {"with invalid i>j", []int{42}, 1, 0},
684 {"s[i:j] is valid and j > len(s)", s, 0, 4},
685 {"s[i:j] is valid and i == j > len(s)", s, 3, 3},
686 } {
687 if !panics(func() { _ = Delete(test.s, test.i, test.j) }) {
688 t.Errorf("Delete %s: got no panic, want panic", test.name)
689 }
690 }
691 }
692
693 func TestDeleteClearTail(t *testing.T) {
694 mem := []*int{new(int), new(int), new(int), new(int), new(int), new(int)}
695 s := mem[0:5]
696
697 s = Delete(s, 2, 4)
698
699 if mem[3] != nil || mem[4] != nil {
700
701 t.Errorf("Delete: want nil discarded elements, got %v, %v", mem[3], mem[4])
702 }
703 if mem[5] == nil {
704 t.Errorf("Delete: want unchanged elements beyond original len, got nil")
705 }
706 }
707
708 func TestDeleteFuncClearTail(t *testing.T) {
709 mem := []*int{new(int), new(int), new(int), new(int), new(int), new(int)}
710 *mem[2], *mem[3] = 42, 42
711 s := mem[0:5]
712
713 s = DeleteFunc(s, func(i *int) bool {
714 return i != nil && *i == 42
715 })
716
717 if mem[3] != nil || mem[4] != nil {
718
719 t.Errorf("DeleteFunc: want nil discarded elements, got %v, %v", mem[3], mem[4])
720 }
721 if mem[5] == nil {
722 t.Errorf("DeleteFunc: want unchanged elements beyond original len, got nil")
723 }
724 }
725
726 func TestClone(t *testing.T) {
727 s1 := []int{1, 2, 3}
728 s2 := Clone(s1)
729 if !Equal(s1, s2) {
730 t.Errorf("Clone(%v) = %v, want %v", s1, s2, s1)
731 }
732 s1[0] = 4
733 want := []int{1, 2, 3}
734 if !Equal(s2, want) {
735 t.Errorf("Clone(%v) changed unexpectedly to %v", want, s2)
736 }
737 if got := Clone([]int(nil)); got != nil {
738 t.Errorf("Clone(nil) = %#v, want nil", got)
739 }
740 if got := Clone(s1[:0]); got == nil || len(got) != 0 {
741 t.Errorf("Clone(%v) = %#v, want %#v", s1[:0], got, s1[:0])
742 }
743 }
744
745 var compactTests = []struct {
746 name string
747 s []int
748 want []int
749 }{
750 {
751 "nil",
752 nil,
753 nil,
754 },
755 {
756 "one",
757 []int{1},
758 []int{1},
759 },
760 {
761 "sorted",
762 []int{1, 2, 3},
763 []int{1, 2, 3},
764 },
765 {
766 "2 items",
767 []int{1, 1, 2},
768 []int{1, 2},
769 },
770 {
771 "unsorted",
772 []int{1, 2, 1},
773 []int{1, 2, 1},
774 },
775 {
776 "many",
777 []int{1, 2, 2, 3, 3, 4},
778 []int{1, 2, 3, 4},
779 },
780 }
781
782 func TestCompact(t *testing.T) {
783 for _, test := range compactTests {
784 copy := Clone(test.s)
785 if got := Compact(copy); !Equal(got, test.want) {
786 t.Errorf("Compact(%v) = %v, want %v", test.s, got, test.want)
787 }
788 }
789 }
790
791 func BenchmarkCompact(b *testing.B) {
792 for _, c := range compactTests {
793 b.Run(c.name, func(b *testing.B) {
794 ss := make([]int, 0, 64)
795 for k := 0; k < b.N; k++ {
796 ss = ss[:0]
797 ss = append(ss, c.s...)
798 _ = Compact(ss)
799 }
800 })
801 }
802 }
803
804 func BenchmarkCompact_Large(b *testing.B) {
805 type Large [16]int
806 const N = 1024
807
808 b.Run("all_dup", func(b *testing.B) {
809 ss := make([]Large, N)
810 b.ResetTimer()
811 for i := 0; i < b.N; i++ {
812 _ = Compact(ss)
813 }
814 })
815 b.Run("no_dup", func(b *testing.B) {
816 ss := make([]Large, N)
817 for i := range ss {
818 ss[i][0] = i
819 }
820 b.ResetTimer()
821 for i := 0; i < b.N; i++ {
822 _ = Compact(ss)
823 }
824 })
825 }
826
827 func TestCompactFunc(t *testing.T) {
828 for _, test := range compactTests {
829 copy := Clone(test.s)
830 if got := CompactFunc(copy, equal[int]); !Equal(got, test.want) {
831 t.Errorf("CompactFunc(%v, equal[int]) = %v, want %v", test.s, got, test.want)
832 }
833 }
834
835 s1 := []string{"a", "a", "A", "B", "b"}
836 copy := Clone(s1)
837 want := []string{"a", "B"}
838 if got := CompactFunc(copy, strings.EqualFold); !Equal(got, want) {
839 t.Errorf("CompactFunc(%v, strings.EqualFold) = %v, want %v", s1, got, want)
840 }
841 }
842
843 func TestCompactClearTail(t *testing.T) {
844 one, two, three, four := 1, 2, 3, 4
845 mem := []*int{&one, &one, &two, &two, &three, &four}
846 s := mem[0:5]
847 copy := Clone(s)
848
849 s = Compact(s)
850
851 if want := []*int{&one, &two, &three}; !Equal(s, want) {
852 t.Errorf("Compact(%v) = %v, want %v", copy, s, want)
853 }
854
855 if mem[3] != nil || mem[4] != nil {
856
857 t.Errorf("Compact: want nil discarded elements, got %v, %v", mem[3], mem[4])
858 }
859 if mem[5] != &four {
860 t.Errorf("Compact: want unchanged element beyond original len, got %v", mem[5])
861 }
862 }
863
864 func TestCompactFuncClearTail(t *testing.T) {
865 a, b, c, d, e, f := 1, 1, 2, 2, 3, 4
866 mem := []*int{&a, &b, &c, &d, &e, &f}
867 s := mem[0:5]
868 copy := Clone(s)
869
870 s = CompactFunc(s, func(x, y *int) bool {
871 if x == nil || y == nil {
872 return x == y
873 }
874 return *x == *y
875 })
876
877 if want := []*int{&a, &c, &e}; !Equal(s, want) {
878 t.Errorf("CompactFunc(%v) = %v, want %v", copy, s, want)
879 }
880
881 if mem[3] != nil || mem[4] != nil {
882
883 t.Errorf("CompactFunc: want nil discarded elements, got %v, %v", mem[3], mem[4])
884 }
885 if mem[5] != &f {
886 t.Errorf("CompactFunc: want unchanged elements beyond original len, got %v", mem[5])
887 }
888 }
889
890 func BenchmarkCompactFunc(b *testing.B) {
891 for _, c := range compactTests {
892 b.Run(c.name, func(b *testing.B) {
893 ss := make([]int, 0, 64)
894 for k := 0; k < b.N; k++ {
895 ss = ss[:0]
896 ss = append(ss, c.s...)
897 _ = CompactFunc(ss, func(a, b int) bool { return a == b })
898 }
899 })
900 }
901 }
902
903 func BenchmarkCompactFunc_Large(b *testing.B) {
904 type Element = int
905 const N = 1024 * 1024
906
907 b.Run("all_dup", func(b *testing.B) {
908 ss := make([]Element, N)
909 b.ResetTimer()
910 for i := 0; i < b.N; i++ {
911 _ = CompactFunc(ss, func(a, b Element) bool { return a == b })
912 }
913 })
914 b.Run("no_dup", func(b *testing.B) {
915 ss := make([]Element, N)
916 for i := range ss {
917 ss[i] = i
918 }
919 b.ResetTimer()
920 for i := 0; i < b.N; i++ {
921 _ = CompactFunc(ss, func(a, b Element) bool { return a == b })
922 }
923 })
924 }
925
926 func TestGrow(t *testing.T) {
927 s1 := []int{1, 2, 3}
928
929 copy := Clone(s1)
930 s2 := Grow(copy, 1000)
931 if !Equal(s1, s2) {
932 t.Errorf("Grow(%v) = %v, want %v", s1, s2, s1)
933 }
934 if cap(s2) < 1000+len(s1) {
935 t.Errorf("after Grow(%v) cap = %d, want >= %d", s1, cap(s2), 1000+len(s1))
936 }
937
938
939 copy = Clone(s1)
940 s3 := Grow(copy[:1], 2)[:3]
941 if !Equal(s1, s3) {
942 t.Errorf("Grow should not mutate elements between length and capacity")
943 }
944 s3 = Grow(copy[:1], 1000)[:3]
945 if !Equal(s1, s3) {
946 t.Errorf("Grow should not mutate elements between length and capacity")
947 }
948
949
950 if n := testing.AllocsPerRun(100, func() { _ = Grow(s2, cap(s2)-len(s2)) }); n != 0 {
951 t.Errorf("Grow should not allocate when given sufficient capacity; allocated %v times", n)
952 }
953 if n := testing.AllocsPerRun(100, func() { _ = Grow(s2, cap(s2)-len(s2)+1) }); n != 1 {
954 errorf := t.Errorf
955 if race.Enabled || testenv.OptimizationOff() {
956 errorf = t.Logf
957 }
958 errorf("Grow should allocate once when given insufficient capacity; allocated %v times", n)
959 }
960
961
962 var gotPanic bool
963 func() {
964 defer func() { gotPanic = recover() != nil }()
965 _ = Grow(s1, -1)
966 }()
967 if !gotPanic {
968 t.Errorf("Grow(-1) did not panic; expected a panic")
969 }
970 }
971
972 func TestClip(t *testing.T) {
973 s1 := []int{1, 2, 3, 4, 5, 6}[:3]
974 orig := Clone(s1)
975 if len(s1) != 3 {
976 t.Errorf("len(%v) = %d, want 3", s1, len(s1))
977 }
978 if cap(s1) < 6 {
979 t.Errorf("cap(%v[:3]) = %d, want >= 6", orig, cap(s1))
980 }
981 s2 := Clip(s1)
982 if !Equal(s1, s2) {
983 t.Errorf("Clip(%v) = %v, want %v", s1, s2, s1)
984 }
985 if cap(s2) != 3 {
986 t.Errorf("cap(Clip(%v)) = %d, want 3", orig, cap(s2))
987 }
988 }
989
990 func TestReverse(t *testing.T) {
991 even := []int{3, 1, 4, 1, 5, 9}
992 Reverse(even)
993 if want := []int{9, 5, 1, 4, 1, 3}; !Equal(even, want) {
994 t.Errorf("Reverse(even) = %v, want %v", even, want)
995 }
996
997 odd := []int{3, 1, 4, 1, 5, 9, 2}
998 Reverse(odd)
999 if want := []int{2, 9, 5, 1, 4, 1, 3}; !Equal(odd, want) {
1000 t.Errorf("Reverse(odd) = %v, want %v", odd, want)
1001 }
1002
1003 words := strings.Fields("one two three")
1004 Reverse(words)
1005 if want := strings.Fields("three two one"); !Equal(words, want) {
1006 t.Errorf("Reverse(words) = %v, want %v", words, want)
1007 }
1008
1009 singleton := []string{"one"}
1010 Reverse(singleton)
1011 if want := []string{"one"}; !Equal(singleton, want) {
1012 t.Errorf("Reverse(singeleton) = %v, want %v", singleton, want)
1013 }
1014
1015 Reverse[[]string](nil)
1016 }
1017
1018
1019 func naiveReplace[S ~[]E, E any](s S, i, j int, v ...E) S {
1020 s = Delete(s, i, j)
1021 s = Insert(s, i, v...)
1022 return s
1023 }
1024
1025 func TestReplace(t *testing.T) {
1026 for _, test := range []struct {
1027 s, v []int
1028 i, j int
1029 }{
1030 {},
1031 {
1032 s: []int{1, 2, 3, 4},
1033 v: []int{5},
1034 i: 1,
1035 j: 2,
1036 },
1037 {
1038 s: []int{1, 2, 3, 4},
1039 v: []int{5, 6, 7, 8},
1040 i: 1,
1041 j: 2,
1042 },
1043 {
1044 s: func() []int {
1045 s := make([]int, 3, 20)
1046 s[0] = 0
1047 s[1] = 1
1048 s[2] = 2
1049 return s
1050 }(),
1051 v: []int{3, 4, 5, 6, 7},
1052 i: 0,
1053 j: 1,
1054 },
1055 } {
1056 ss, vv := Clone(test.s), Clone(test.v)
1057 want := naiveReplace(ss, test.i, test.j, vv...)
1058 got := Replace(test.s, test.i, test.j, test.v...)
1059 if !Equal(got, want) {
1060 t.Errorf("Replace(%v, %v, %v, %v) = %v, want %v", test.s, test.i, test.j, test.v, got, want)
1061 }
1062 }
1063 }
1064
1065 func TestReplacePanics(t *testing.T) {
1066 s := []int{0, 1, 2, 3, 4}
1067 s = s[0:2]
1068 _ = s[0:4]
1069
1070 for _, test := range []struct {
1071 name string
1072 s, v []int
1073 i, j int
1074 }{
1075 {"indexes out of order", []int{1, 2}, []int{3}, 2, 1},
1076 {"large index", []int{1, 2}, []int{3}, 1, 10},
1077 {"negative index", []int{1, 2}, []int{3}, -1, 2},
1078 {"s[i:j] is valid and j > len(s)", s, nil, 0, 4},
1079 } {
1080 ss, vv := Clone(test.s), Clone(test.v)
1081 if !panics(func() { _ = Replace(ss, test.i, test.j, vv...) }) {
1082 t.Errorf("Replace %s: should have panicked", test.name)
1083 }
1084 }
1085 }
1086
1087 func TestReplaceGrow(t *testing.T) {
1088
1089
1090 a, b, c, d, e, f := 1, 2, 3, 4, 5, 6
1091 mem := []*int{&a, &b, &c, &d, &e, &f}
1092 memcopy := Clone(mem)
1093 s := mem[0:5]
1094 copy := Clone(s)
1095 original := s
1096
1097
1098 z := 99
1099 s = Replace(s, 1, 3, &z, &z, &z, &z)
1100
1101 if want := []*int{&a, &z, &z, &z, &z, &d, &e}; !Equal(s, want) {
1102 t.Errorf("Replace(%v, 1, 3, %v, %v, %v, %v) = %v, want %v", copy, &z, &z, &z, &z, s, want)
1103 }
1104
1105 if !Equal(original, copy) {
1106 t.Errorf("original slice has changed, got %v, want %v", original, copy)
1107 }
1108
1109 if !Equal(mem, memcopy) {
1110
1111 t.Errorf("original backing memory has changed, got %v, want %v", mem, memcopy)
1112 }
1113 }
1114
1115 func TestReplaceClearTail(t *testing.T) {
1116 a, b, c, d, e, f := 1, 2, 3, 4, 5, 6
1117 mem := []*int{&a, &b, &c, &d, &e, &f}
1118 s := mem[0:5]
1119 copy := Clone(s)
1120
1121 y, z := 8, 9
1122 s = Replace(s, 1, 4, &y, &z)
1123
1124 if want := []*int{&a, &y, &z, &e}; !Equal(s, want) {
1125 t.Errorf("Replace(%v) = %v, want %v", copy, s, want)
1126 }
1127
1128 if mem[4] != nil {
1129
1130 t.Errorf("Replace: want nil discarded element, got %v", mem[4])
1131 }
1132 if mem[5] != &f {
1133 t.Errorf("Replace: want unchanged elements beyond original len, got %v", mem[5])
1134 }
1135 }
1136
1137 func TestReplaceOverlap(t *testing.T) {
1138 const N = 10
1139 a := make([]int, N)
1140 want := make([]int, 2*N)
1141 for n := 0; n <= N; n++ {
1142 for i := 0; i <= n; i++ {
1143 for j := i; j <= n; j++ {
1144 for x := 0; x <= N; x++ {
1145 for y := x; y <= N; y++ {
1146 for k := 0; k < N; k++ {
1147 a[k] = k
1148 }
1149 want = want[:0]
1150 want = append(want, a[:i]...)
1151 want = append(want, a[x:y]...)
1152 want = append(want, a[j:n]...)
1153 got := Replace(a[:n], i, j, a[x:y]...)
1154 if !Equal(got, want) {
1155 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)
1156 }
1157 }
1158 }
1159 }
1160 }
1161 }
1162 }
1163
1164 func TestReplaceEndClearTail(t *testing.T) {
1165 s := []int{11, 22, 33}
1166 v := []int{99}
1167
1168 i, j := 1, 3
1169 s = Replace(s, i, j, v...)
1170
1171 x := s[:3][2]
1172 if want := 0; x != want {
1173 t.Errorf("TestReplaceEndClearTail: obsolete element is %d, want %d", x, want)
1174 }
1175 }
1176
1177 func BenchmarkReplace(b *testing.B) {
1178 cases := []struct {
1179 name string
1180 s, v func() []int
1181 i, j int
1182 }{
1183 {
1184 name: "fast",
1185 s: func() []int {
1186 return make([]int, 100)
1187 },
1188 v: func() []int {
1189 return make([]int, 20)
1190 },
1191 i: 10,
1192 j: 40,
1193 },
1194 {
1195 name: "slow",
1196 s: func() []int {
1197 return make([]int, 100)
1198 },
1199 v: func() []int {
1200 return make([]int, 20)
1201 },
1202 i: 0,
1203 j: 2,
1204 },
1205 }
1206
1207 for _, c := range cases {
1208 b.Run("naive-"+c.name, func(b *testing.B) {
1209 for k := 0; k < b.N; k++ {
1210 s := c.s()
1211 v := c.v()
1212 _ = naiveReplace(s, c.i, c.j, v...)
1213 }
1214 })
1215 b.Run("optimized-"+c.name, func(b *testing.B) {
1216 for k := 0; k < b.N; k++ {
1217 s := c.s()
1218 v := c.v()
1219 _ = Replace(s, c.i, c.j, v...)
1220 }
1221 })
1222 }
1223
1224 }
1225
1226 func TestInsertGrowthRate(t *testing.T) {
1227 b := make([]byte, 1)
1228 maxCap := cap(b)
1229 nGrow := 0
1230 const N = 1e6
1231 for i := 0; i < N; i++ {
1232 b = Insert(b, len(b)-1, 0)
1233 if cap(b) > maxCap {
1234 maxCap = cap(b)
1235 nGrow++
1236 }
1237 }
1238 want := int(math.Log(N) / math.Log(1.25))
1239 if nGrow > want {
1240 t.Errorf("too many grows. got:%d want:%d", nGrow, want)
1241 }
1242 }
1243
1244 func TestReplaceGrowthRate(t *testing.T) {
1245 b := make([]byte, 2)
1246 maxCap := cap(b)
1247 nGrow := 0
1248 const N = 1e6
1249 for i := 0; i < N; i++ {
1250 b = Replace(b, len(b)-2, len(b)-1, 0, 0)
1251 if cap(b) > maxCap {
1252 maxCap = cap(b)
1253 nGrow++
1254 }
1255 }
1256 want := int(math.Log(N) / math.Log(1.25))
1257 if nGrow > want {
1258 t.Errorf("too many grows. got:%d want:%d", nGrow, want)
1259 }
1260 }
1261
1262 func apply[T any](v T, f func(T)) {
1263 f(v)
1264 }
1265
1266
1267 func TestInference(t *testing.T) {
1268 s1 := []int{1, 2, 3}
1269 apply(s1, Reverse)
1270 if want := []int{3, 2, 1}; !Equal(s1, want) {
1271 t.Errorf("Reverse(%v) = %v, want %v", []int{1, 2, 3}, s1, want)
1272 }
1273
1274 type S []int
1275 s2 := S{4, 5, 6}
1276 apply(s2, Reverse)
1277 if want := (S{6, 5, 4}); !Equal(s2, want) {
1278 t.Errorf("Reverse(%v) = %v, want %v", S{4, 5, 6}, s2, want)
1279 }
1280 }
1281
1282 func TestConcat(t *testing.T) {
1283 cases := []struct {
1284 s [][]int
1285 want []int
1286 }{
1287 {
1288 s: [][]int{nil},
1289 want: nil,
1290 },
1291 {
1292 s: [][]int{{1}},
1293 want: []int{1},
1294 },
1295 {
1296 s: [][]int{{1}, {2}},
1297 want: []int{1, 2},
1298 },
1299 {
1300 s: [][]int{{1}, nil, {2}},
1301 want: []int{1, 2},
1302 },
1303 }
1304 for _, tc := range cases {
1305 got := Concat(tc.s...)
1306 if !Equal(tc.want, got) {
1307 t.Errorf("Concat(%v) = %v, want %v", tc.s, got, tc.want)
1308 }
1309 var sink []int
1310 allocs := testing.AllocsPerRun(5, func() {
1311 sink = Concat(tc.s...)
1312 })
1313 _ = sink
1314 if allocs > 1 {
1315 errorf := t.Errorf
1316 if testenv.OptimizationOff() || race.Enabled {
1317 errorf = t.Logf
1318 }
1319 errorf("Concat(%v) allocated %v times; want 1", tc.s, allocs)
1320 }
1321 }
1322 }
1323
1324 func TestConcat_too_large(t *testing.T) {
1325
1326 type void struct{}
1327 cases := []struct {
1328 lengths []int
1329 shouldPanic bool
1330 }{
1331 {
1332 lengths: []int{0, 0},
1333 shouldPanic: false,
1334 },
1335 {
1336 lengths: []int{math.MaxInt, 0},
1337 shouldPanic: false,
1338 },
1339 {
1340 lengths: []int{0, math.MaxInt},
1341 shouldPanic: false,
1342 },
1343 {
1344 lengths: []int{math.MaxInt - 1, 1},
1345 shouldPanic: false,
1346 },
1347 {
1348 lengths: []int{math.MaxInt - 1, 1, 1},
1349 shouldPanic: true,
1350 },
1351 {
1352 lengths: []int{math.MaxInt, 1},
1353 shouldPanic: true,
1354 },
1355 {
1356 lengths: []int{math.MaxInt, math.MaxInt},
1357 shouldPanic: true,
1358 },
1359 }
1360 for _, tc := range cases {
1361 var r any
1362 ss := make([][]void, 0, len(tc.lengths))
1363 for _, l := range tc.lengths {
1364 s := make([]void, l)
1365 ss = append(ss, s)
1366 }
1367 func() {
1368 defer func() {
1369 r = recover()
1370 }()
1371 _ = Concat(ss...)
1372 }()
1373 if didPanic := r != nil; didPanic != tc.shouldPanic {
1374 t.Errorf("slices.Concat(lens(%v)) got panic == %v",
1375 tc.lengths, didPanic)
1376 }
1377 }
1378 }
1379
1380 func TestRepeat(t *testing.T) {
1381
1382 for _, tc := range []struct {
1383 x []int
1384 count int
1385 want []int
1386 }{
1387 {x: []int(nil), count: 0, want: []int{}},
1388 {x: []int(nil), count: 1, want: []int{}},
1389 {x: []int(nil), count: math.MaxInt, want: []int{}},
1390 {x: []int{}, count: 0, want: []int{}},
1391 {x: []int{}, count: 1, want: []int{}},
1392 {x: []int{}, count: math.MaxInt, want: []int{}},
1393 {x: []int{0}, count: 0, want: []int{}},
1394 {x: []int{0}, count: 1, want: []int{0}},
1395 {x: []int{0}, count: 2, want: []int{0, 0}},
1396 {x: []int{0}, count: 3, want: []int{0, 0, 0}},
1397 {x: []int{0}, count: 4, want: []int{0, 0, 0, 0}},
1398 {x: []int{0, 1}, count: 0, want: []int{}},
1399 {x: []int{0, 1}, count: 1, want: []int{0, 1}},
1400 {x: []int{0, 1}, count: 2, want: []int{0, 1, 0, 1}},
1401 {x: []int{0, 1}, count: 3, want: []int{0, 1, 0, 1, 0, 1}},
1402 {x: []int{0, 1}, count: 4, want: []int{0, 1, 0, 1, 0, 1, 0, 1}},
1403 {x: []int{0, 1, 2}, count: 0, want: []int{}},
1404 {x: []int{0, 1, 2}, count: 1, want: []int{0, 1, 2}},
1405 {x: []int{0, 1, 2}, count: 2, want: []int{0, 1, 2, 0, 1, 2}},
1406 {x: []int{0, 1, 2}, count: 3, want: []int{0, 1, 2, 0, 1, 2, 0, 1, 2}},
1407 {x: []int{0, 1, 2}, count: 4, want: []int{0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2}},
1408 } {
1409 if got := Repeat(tc.x, tc.count); got == nil || cap(got) != cap(tc.want) || !Equal(got, tc.want) {
1410 t.Errorf("Repeat(%v, %v): got: %v, want: %v, (got == nil): %v, cap(got): %v, cap(want): %v",
1411 tc.x, tc.count, got, tc.want, got == nil, cap(got), cap(tc.want))
1412 }
1413 }
1414
1415
1416 for _, tc := range []struct {
1417 x []struct{}
1418 count int
1419 want []struct{}
1420 }{
1421 {x: make([]struct{}, math.MaxInt/1-0), count: 1, want: make([]struct{}, 1*(math.MaxInt/1-0))},
1422 {x: make([]struct{}, math.MaxInt/2-1), count: 2, want: make([]struct{}, 2*(math.MaxInt/2-1))},
1423 {x: make([]struct{}, math.MaxInt/3-2), count: 3, want: make([]struct{}, 3*(math.MaxInt/3-2))},
1424 {x: make([]struct{}, math.MaxInt/4-3), count: 4, want: make([]struct{}, 4*(math.MaxInt/4-3))},
1425 {x: make([]struct{}, math.MaxInt/5-4), count: 5, want: make([]struct{}, 5*(math.MaxInt/5-4))},
1426 {x: make([]struct{}, math.MaxInt/6-5), count: 6, want: make([]struct{}, 6*(math.MaxInt/6-5))},
1427 {x: make([]struct{}, math.MaxInt/7-6), count: 7, want: make([]struct{}, 7*(math.MaxInt/7-6))},
1428 {x: make([]struct{}, math.MaxInt/8-7), count: 8, want: make([]struct{}, 8*(math.MaxInt/8-7))},
1429 {x: make([]struct{}, math.MaxInt/9-8), count: 9, want: make([]struct{}, 9*(math.MaxInt/9-8))},
1430 } {
1431 if got := Repeat(tc.x, tc.count); got == nil || len(got) != len(tc.want) || cap(got) != cap(tc.want) {
1432 t.Errorf("Repeat(make([]struct{}, %v), %v): (got == nil): %v, len(got): %v, len(want): %v, cap(got): %v, cap(want): %v",
1433 len(tc.x), tc.count, got == nil, len(got), len(tc.want), cap(got), cap(tc.want))
1434 }
1435 }
1436 }
1437
1438 func TestRepeatPanics(t *testing.T) {
1439 for _, test := range []struct {
1440 name string
1441 x []struct{}
1442 count int
1443 }{
1444 {name: "cannot be negative", x: make([]struct{}, 0), count: -1},
1445 {name: "the result of (len(x) * count) overflows, hi > 0", x: make([]struct{}, 3), count: math.MaxInt},
1446 {name: "the result of (len(x) * count) overflows, lo > maxInt", x: make([]struct{}, 2), count: 1 + math.MaxInt/2},
1447 } {
1448 if !panics(func() { _ = Repeat(test.x, test.count) }) {
1449 t.Errorf("Repeat %s: got no panic, want panic", test.name)
1450 }
1451 }
1452 }
1453
View as plain text