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