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 "1 item",
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 [4 * 1024]byte
806
807 ss := make([]Large, 1024)
808 for i := 0; i < b.N; i++ {
809 _ = Compact(ss)
810 }
811 }
812
813 func TestCompactFunc(t *testing.T) {
814 for _, test := range compactTests {
815 copy := Clone(test.s)
816 if got := CompactFunc(copy, equal[int]); !Equal(got, test.want) {
817 t.Errorf("CompactFunc(%v, equal[int]) = %v, want %v", test.s, got, test.want)
818 }
819 }
820
821 s1 := []string{"a", "a", "A", "B", "b"}
822 copy := Clone(s1)
823 want := []string{"a", "B"}
824 if got := CompactFunc(copy, strings.EqualFold); !Equal(got, want) {
825 t.Errorf("CompactFunc(%v, strings.EqualFold) = %v, want %v", s1, got, want)
826 }
827 }
828
829 func TestCompactClearTail(t *testing.T) {
830 one, two, three, four := 1, 2, 3, 4
831 mem := []*int{&one, &one, &two, &two, &three, &four}
832 s := mem[0:5]
833 copy := Clone(s)
834
835 s = Compact(s)
836
837 if want := []*int{&one, &two, &three}; !Equal(s, want) {
838 t.Errorf("Compact(%v) = %v, want %v", copy, s, want)
839 }
840
841 if mem[3] != nil || mem[4] != nil {
842
843 t.Errorf("Compact: want nil discarded elements, got %v, %v", mem[3], mem[4])
844 }
845 if mem[5] != &four {
846 t.Errorf("Compact: want unchanged element beyond original len, got %v", mem[5])
847 }
848 }
849
850 func TestCompactFuncClearTail(t *testing.T) {
851 a, b, c, d, e, f := 1, 1, 2, 2, 3, 4
852 mem := []*int{&a, &b, &c, &d, &e, &f}
853 s := mem[0:5]
854 copy := Clone(s)
855
856 s = CompactFunc(s, func(x, y *int) bool {
857 if x == nil || y == nil {
858 return x == y
859 }
860 return *x == *y
861 })
862
863 if want := []*int{&a, &c, &e}; !Equal(s, want) {
864 t.Errorf("CompactFunc(%v) = %v, want %v", copy, s, want)
865 }
866
867 if mem[3] != nil || mem[4] != nil {
868
869 t.Errorf("CompactFunc: want nil discarded elements, got %v, %v", mem[3], mem[4])
870 }
871 if mem[5] != &f {
872 t.Errorf("CompactFunc: want unchanged elements beyond original len, got %v", mem[5])
873 }
874 }
875
876 func BenchmarkCompactFunc_Large(b *testing.B) {
877 type Large [4 * 1024]byte
878
879 ss := make([]Large, 1024)
880 for i := 0; i < b.N; i++ {
881 _ = CompactFunc(ss, func(a, b Large) bool { return a == b })
882 }
883 }
884
885 func TestGrow(t *testing.T) {
886 s1 := []int{1, 2, 3}
887
888 copy := Clone(s1)
889 s2 := Grow(copy, 1000)
890 if !Equal(s1, s2) {
891 t.Errorf("Grow(%v) = %v, want %v", s1, s2, s1)
892 }
893 if cap(s2) < 1000+len(s1) {
894 t.Errorf("after Grow(%v) cap = %d, want >= %d", s1, cap(s2), 1000+len(s1))
895 }
896
897
898 copy = Clone(s1)
899 s3 := Grow(copy[:1], 2)[:3]
900 if !Equal(s1, s3) {
901 t.Errorf("Grow should not mutate elements between length and capacity")
902 }
903 s3 = Grow(copy[:1], 1000)[:3]
904 if !Equal(s1, s3) {
905 t.Errorf("Grow should not mutate elements between length and capacity")
906 }
907
908
909 if n := testing.AllocsPerRun(100, func() { _ = Grow(s2, cap(s2)-len(s2)) }); n != 0 {
910 t.Errorf("Grow should not allocate when given sufficient capacity; allocated %v times", n)
911 }
912 if n := testing.AllocsPerRun(100, func() { _ = Grow(s2, cap(s2)-len(s2)+1) }); n != 1 {
913 errorf := t.Errorf
914 if race.Enabled || testenv.OptimizationOff() {
915 errorf = t.Logf
916 }
917 errorf("Grow should allocate once when given insufficient capacity; allocated %v times", n)
918 }
919
920
921 var gotPanic bool
922 func() {
923 defer func() { gotPanic = recover() != nil }()
924 _ = Grow(s1, -1)
925 }()
926 if !gotPanic {
927 t.Errorf("Grow(-1) did not panic; expected a panic")
928 }
929 }
930
931 func TestClip(t *testing.T) {
932 s1 := []int{1, 2, 3, 4, 5, 6}[:3]
933 orig := Clone(s1)
934 if len(s1) != 3 {
935 t.Errorf("len(%v) = %d, want 3", s1, len(s1))
936 }
937 if cap(s1) < 6 {
938 t.Errorf("cap(%v[:3]) = %d, want >= 6", orig, cap(s1))
939 }
940 s2 := Clip(s1)
941 if !Equal(s1, s2) {
942 t.Errorf("Clip(%v) = %v, want %v", s1, s2, s1)
943 }
944 if cap(s2) != 3 {
945 t.Errorf("cap(Clip(%v)) = %d, want 3", orig, cap(s2))
946 }
947 }
948
949 func TestReverse(t *testing.T) {
950 even := []int{3, 1, 4, 1, 5, 9}
951 Reverse(even)
952 if want := []int{9, 5, 1, 4, 1, 3}; !Equal(even, want) {
953 t.Errorf("Reverse(even) = %v, want %v", even, want)
954 }
955
956 odd := []int{3, 1, 4, 1, 5, 9, 2}
957 Reverse(odd)
958 if want := []int{2, 9, 5, 1, 4, 1, 3}; !Equal(odd, want) {
959 t.Errorf("Reverse(odd) = %v, want %v", odd, want)
960 }
961
962 words := strings.Fields("one two three")
963 Reverse(words)
964 if want := strings.Fields("three two one"); !Equal(words, want) {
965 t.Errorf("Reverse(words) = %v, want %v", words, want)
966 }
967
968 singleton := []string{"one"}
969 Reverse(singleton)
970 if want := []string{"one"}; !Equal(singleton, want) {
971 t.Errorf("Reverse(singeleton) = %v, want %v", singleton, want)
972 }
973
974 Reverse[[]string](nil)
975 }
976
977
978 func naiveReplace[S ~[]E, E any](s S, i, j int, v ...E) S {
979 s = Delete(s, i, j)
980 s = Insert(s, i, v...)
981 return s
982 }
983
984 func TestReplace(t *testing.T) {
985 for _, test := range []struct {
986 s, v []int
987 i, j int
988 }{
989 {},
990 {
991 s: []int{1, 2, 3, 4},
992 v: []int{5},
993 i: 1,
994 j: 2,
995 },
996 {
997 s: []int{1, 2, 3, 4},
998 v: []int{5, 6, 7, 8},
999 i: 1,
1000 j: 2,
1001 },
1002 {
1003 s: func() []int {
1004 s := make([]int, 3, 20)
1005 s[0] = 0
1006 s[1] = 1
1007 s[2] = 2
1008 return s
1009 }(),
1010 v: []int{3, 4, 5, 6, 7},
1011 i: 0,
1012 j: 1,
1013 },
1014 } {
1015 ss, vv := Clone(test.s), Clone(test.v)
1016 want := naiveReplace(ss, test.i, test.j, vv...)
1017 got := Replace(test.s, test.i, test.j, test.v...)
1018 if !Equal(got, want) {
1019 t.Errorf("Replace(%v, %v, %v, %v) = %v, want %v", test.s, test.i, test.j, test.v, got, want)
1020 }
1021 }
1022 }
1023
1024 func TestReplacePanics(t *testing.T) {
1025 s := []int{0, 1, 2, 3, 4}
1026 s = s[0:2]
1027 _ = s[0:4]
1028
1029 for _, test := range []struct {
1030 name string
1031 s, v []int
1032 i, j int
1033 }{
1034 {"indexes out of order", []int{1, 2}, []int{3}, 2, 1},
1035 {"large index", []int{1, 2}, []int{3}, 1, 10},
1036 {"negative index", []int{1, 2}, []int{3}, -1, 2},
1037 {"s[i:j] is valid and j > len(s)", s, nil, 0, 4},
1038 } {
1039 ss, vv := Clone(test.s), Clone(test.v)
1040 if !panics(func() { _ = Replace(ss, test.i, test.j, vv...) }) {
1041 t.Errorf("Replace %s: should have panicked", test.name)
1042 }
1043 }
1044 }
1045
1046 func TestReplaceGrow(t *testing.T) {
1047
1048
1049 a, b, c, d, e, f := 1, 2, 3, 4, 5, 6
1050 mem := []*int{&a, &b, &c, &d, &e, &f}
1051 memcopy := Clone(mem)
1052 s := mem[0:5]
1053 copy := Clone(s)
1054 original := s
1055
1056
1057 z := 99
1058 s = Replace(s, 1, 3, &z, &z, &z, &z)
1059
1060 if want := []*int{&a, &z, &z, &z, &z, &d, &e}; !Equal(s, want) {
1061 t.Errorf("Replace(%v, 1, 3, %v, %v, %v, %v) = %v, want %v", copy, &z, &z, &z, &z, s, want)
1062 }
1063
1064 if !Equal(original, copy) {
1065 t.Errorf("original slice has changed, got %v, want %v", original, copy)
1066 }
1067
1068 if !Equal(mem, memcopy) {
1069
1070 t.Errorf("original backing memory has changed, got %v, want %v", mem, memcopy)
1071 }
1072 }
1073
1074 func TestReplaceClearTail(t *testing.T) {
1075 a, b, c, d, e, f := 1, 2, 3, 4, 5, 6
1076 mem := []*int{&a, &b, &c, &d, &e, &f}
1077 s := mem[0:5]
1078 copy := Clone(s)
1079
1080 y, z := 8, 9
1081 s = Replace(s, 1, 4, &y, &z)
1082
1083 if want := []*int{&a, &y, &z, &e}; !Equal(s, want) {
1084 t.Errorf("Replace(%v) = %v, want %v", copy, s, want)
1085 }
1086
1087 if mem[4] != nil {
1088
1089 t.Errorf("Replace: want nil discarded element, got %v", mem[4])
1090 }
1091 if mem[5] != &f {
1092 t.Errorf("Replace: want unchanged elements beyond original len, got %v", mem[5])
1093 }
1094 }
1095
1096 func TestReplaceOverlap(t *testing.T) {
1097 const N = 10
1098 a := make([]int, N)
1099 want := make([]int, 2*N)
1100 for n := 0; n <= N; n++ {
1101 for i := 0; i <= n; i++ {
1102 for j := i; j <= n; j++ {
1103 for x := 0; x <= N; x++ {
1104 for y := x; y <= N; y++ {
1105 for k := 0; k < N; k++ {
1106 a[k] = k
1107 }
1108 want = want[:0]
1109 want = append(want, a[:i]...)
1110 want = append(want, a[x:y]...)
1111 want = append(want, a[j:n]...)
1112 got := Replace(a[:n], i, j, a[x:y]...)
1113 if !Equal(got, want) {
1114 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)
1115 }
1116 }
1117 }
1118 }
1119 }
1120 }
1121 }
1122
1123 func BenchmarkReplace(b *testing.B) {
1124 cases := []struct {
1125 name string
1126 s, v func() []int
1127 i, j int
1128 }{
1129 {
1130 name: "fast",
1131 s: func() []int {
1132 return make([]int, 100)
1133 },
1134 v: func() []int {
1135 return make([]int, 20)
1136 },
1137 i: 10,
1138 j: 40,
1139 },
1140 {
1141 name: "slow",
1142 s: func() []int {
1143 return make([]int, 100)
1144 },
1145 v: func() []int {
1146 return make([]int, 20)
1147 },
1148 i: 0,
1149 j: 2,
1150 },
1151 }
1152
1153 for _, c := range cases {
1154 b.Run("naive-"+c.name, func(b *testing.B) {
1155 for k := 0; k < b.N; k++ {
1156 s := c.s()
1157 v := c.v()
1158 _ = naiveReplace(s, c.i, c.j, v...)
1159 }
1160 })
1161 b.Run("optimized-"+c.name, func(b *testing.B) {
1162 for k := 0; k < b.N; k++ {
1163 s := c.s()
1164 v := c.v()
1165 _ = Replace(s, c.i, c.j, v...)
1166 }
1167 })
1168 }
1169
1170 }
1171
1172 func TestInsertGrowthRate(t *testing.T) {
1173 b := make([]byte, 1)
1174 maxCap := cap(b)
1175 nGrow := 0
1176 const N = 1e6
1177 for i := 0; i < N; i++ {
1178 b = Insert(b, len(b)-1, 0)
1179 if cap(b) > maxCap {
1180 maxCap = cap(b)
1181 nGrow++
1182 }
1183 }
1184 want := int(math.Log(N) / math.Log(1.25))
1185 if nGrow > want {
1186 t.Errorf("too many grows. got:%d want:%d", nGrow, want)
1187 }
1188 }
1189
1190 func TestReplaceGrowthRate(t *testing.T) {
1191 b := make([]byte, 2)
1192 maxCap := cap(b)
1193 nGrow := 0
1194 const N = 1e6
1195 for i := 0; i < N; i++ {
1196 b = Replace(b, len(b)-2, len(b)-1, 0, 0)
1197 if cap(b) > maxCap {
1198 maxCap = cap(b)
1199 nGrow++
1200 }
1201 }
1202 want := int(math.Log(N) / math.Log(1.25))
1203 if nGrow > want {
1204 t.Errorf("too many grows. got:%d want:%d", nGrow, want)
1205 }
1206 }
1207
1208 func apply[T any](v T, f func(T)) {
1209 f(v)
1210 }
1211
1212
1213 func TestInference(t *testing.T) {
1214 s1 := []int{1, 2, 3}
1215 apply(s1, Reverse)
1216 if want := []int{3, 2, 1}; !Equal(s1, want) {
1217 t.Errorf("Reverse(%v) = %v, want %v", []int{1, 2, 3}, s1, want)
1218 }
1219
1220 type S []int
1221 s2 := S{4, 5, 6}
1222 apply(s2, Reverse)
1223 if want := (S{6, 5, 4}); !Equal(s2, want) {
1224 t.Errorf("Reverse(%v) = %v, want %v", S{4, 5, 6}, s2, want)
1225 }
1226 }
1227
1228 func TestConcat(t *testing.T) {
1229 cases := []struct {
1230 s [][]int
1231 want []int
1232 }{
1233 {
1234 s: [][]int{nil},
1235 want: nil,
1236 },
1237 {
1238 s: [][]int{{1}},
1239 want: []int{1},
1240 },
1241 {
1242 s: [][]int{{1}, {2}},
1243 want: []int{1, 2},
1244 },
1245 {
1246 s: [][]int{{1}, nil, {2}},
1247 want: []int{1, 2},
1248 },
1249 }
1250 for _, tc := range cases {
1251 got := Concat(tc.s...)
1252 if !Equal(tc.want, got) {
1253 t.Errorf("Concat(%v) = %v, want %v", tc.s, got, tc.want)
1254 }
1255 var sink []int
1256 allocs := testing.AllocsPerRun(5, func() {
1257 sink = Concat(tc.s...)
1258 })
1259 _ = sink
1260 if allocs > 1 {
1261 errorf := t.Errorf
1262 if testenv.OptimizationOff() || race.Enabled {
1263 errorf = t.Logf
1264 }
1265 errorf("Concat(%v) allocated %v times; want 1", tc.s, allocs)
1266 }
1267 }
1268 }
1269
1270 func TestConcat_too_large(t *testing.T) {
1271
1272 type void struct{}
1273 cases := []struct {
1274 lengths []int
1275 shouldPanic bool
1276 }{
1277 {
1278 lengths: []int{0, 0},
1279 shouldPanic: false,
1280 },
1281 {
1282 lengths: []int{math.MaxInt, 0},
1283 shouldPanic: false,
1284 },
1285 {
1286 lengths: []int{0, math.MaxInt},
1287 shouldPanic: false,
1288 },
1289 {
1290 lengths: []int{math.MaxInt - 1, 1},
1291 shouldPanic: false,
1292 },
1293 {
1294 lengths: []int{math.MaxInt - 1, 1, 1},
1295 shouldPanic: true,
1296 },
1297 {
1298 lengths: []int{math.MaxInt, 1},
1299 shouldPanic: true,
1300 },
1301 {
1302 lengths: []int{math.MaxInt, math.MaxInt},
1303 shouldPanic: true,
1304 },
1305 }
1306 for _, tc := range cases {
1307 var r any
1308 ss := make([][]void, 0, len(tc.lengths))
1309 for _, l := range tc.lengths {
1310 s := make([]void, l)
1311 ss = append(ss, s)
1312 }
1313 func() {
1314 defer func() {
1315 r = recover()
1316 }()
1317 _ = Concat(ss...)
1318 }()
1319 if didPanic := r != nil; didPanic != tc.shouldPanic {
1320 t.Errorf("slices.Concat(lens(%v)) got panic == %v",
1321 tc.lengths, didPanic)
1322 }
1323 }
1324 }
1325
View as plain text