// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
-package slices
+package slices_test
import (
+ "cmp"
"internal/race"
"internal/testenv"
"math"
+ . "slices"
"strings"
"testing"
)
}
}
+func BenchmarkEqualFunc_Large(b *testing.B) {
+ type Large [4 * 1024]byte
+
+ xs := make([]Large, 1024)
+ ys := make([]Large, 1024)
+ for i := 0; i < b.N; i++ {
+ _ = EqualFunc(xs, ys, func(x, y Large) bool { return x == y })
+ }
+}
+
+var compareIntTests = []struct {
+ s1, s2 []int
+ want int
+}{
+ {
+ []int{1},
+ []int{1},
+ 0,
+ },
+ {
+ []int{1},
+ []int{},
+ 1,
+ },
+ {
+ []int{},
+ []int{1},
+ -1,
+ },
+ {
+ []int{},
+ []int{},
+ 0,
+ },
+ {
+ []int{1, 2, 3},
+ []int{1, 2, 3},
+ 0,
+ },
+ {
+ []int{1, 2, 3},
+ []int{1, 2, 3, 4},
+ -1,
+ },
+ {
+ []int{1, 2, 3, 4},
+ []int{1, 2, 3},
+ +1,
+ },
+ {
+ []int{1, 2, 3},
+ []int{1, 4, 3},
+ -1,
+ },
+ {
+ []int{1, 4, 3},
+ []int{1, 2, 3},
+ +1,
+ },
+ {
+ []int{1, 4, 3},
+ []int{1, 2, 3, 8, 9},
+ +1,
+ },
+}
+
+var compareFloatTests = []struct {
+ s1, s2 []float64
+ want int
+}{
+ {
+ []float64{},
+ []float64{},
+ 0,
+ },
+ {
+ []float64{1},
+ []float64{1},
+ 0,
+ },
+ {
+ []float64{math.NaN()},
+ []float64{math.NaN()},
+ 0,
+ },
+ {
+ []float64{1, 2, math.NaN()},
+ []float64{1, 2, math.NaN()},
+ 0,
+ },
+ {
+ []float64{1, math.NaN(), 3},
+ []float64{1, math.NaN(), 4},
+ -1,
+ },
+ {
+ []float64{1, math.NaN(), 3},
+ []float64{1, 2, 4},
+ -1,
+ },
+ {
+ []float64{1, math.NaN(), 3},
+ []float64{1, 2, math.NaN()},
+ -1,
+ },
+ {
+ []float64{1, 2, 3},
+ []float64{1, 2, math.NaN()},
+ +1,
+ },
+ {
+ []float64{1, 2, 3},
+ []float64{1, math.NaN(), 3},
+ +1,
+ },
+ {
+ []float64{1, math.NaN(), 3, 4},
+ []float64{1, 2, math.NaN()},
+ -1,
+ },
+}
+
+func TestCompare(t *testing.T) {
+ intWant := func(want bool) string {
+ if want {
+ return "0"
+ }
+ return "!= 0"
+ }
+ for _, test := range equalIntTests {
+ if got := Compare(test.s1, test.s2); (got == 0) != test.want {
+ t.Errorf("Compare(%v, %v) = %d, want %s", test.s1, test.s2, got, intWant(test.want))
+ }
+ }
+ for _, test := range equalFloatTests {
+ if got := Compare(test.s1, test.s2); (got == 0) != test.wantEqualNaN {
+ t.Errorf("Compare(%v, %v) = %d, want %s", test.s1, test.s2, got, intWant(test.wantEqualNaN))
+ }
+ }
+
+ for _, test := range compareIntTests {
+ if got := Compare(test.s1, test.s2); got != test.want {
+ t.Errorf("Compare(%v, %v) = %d, want %d", test.s1, test.s2, got, test.want)
+ }
+ }
+ for _, test := range compareFloatTests {
+ if got := Compare(test.s1, test.s2); got != test.want {
+ t.Errorf("Compare(%v, %v) = %d, want %d", test.s1, test.s2, got, test.want)
+ }
+ }
+}
+
+func equalToCmp[T comparable](eq func(T, T) bool) func(T, T) int {
+ return func(v1, v2 T) int {
+ if eq(v1, v2) {
+ return 0
+ }
+ return 1
+ }
+}
+
+func TestCompareFunc(t *testing.T) {
+ intWant := func(want bool) string {
+ if want {
+ return "0"
+ }
+ return "!= 0"
+ }
+ for _, test := range equalIntTests {
+ if got := CompareFunc(test.s1, test.s2, equalToCmp(equal[int])); (got == 0) != test.want {
+ t.Errorf("CompareFunc(%v, %v, equalToCmp(equal[int])) = %d, want %s", test.s1, test.s2, got, intWant(test.want))
+ }
+ }
+ for _, test := range equalFloatTests {
+ if got := CompareFunc(test.s1, test.s2, equalToCmp(equal[float64])); (got == 0) != test.wantEqual {
+ t.Errorf("CompareFunc(%v, %v, equalToCmp(equal[float64])) = %d, want %s", test.s1, test.s2, got, intWant(test.wantEqual))
+ }
+ }
+
+ for _, test := range compareIntTests {
+ if got := CompareFunc(test.s1, test.s2, cmp.Compare[int]); got != test.want {
+ t.Errorf("CompareFunc(%v, %v, cmp[int]) = %d, want %d", test.s1, test.s2, got, test.want)
+ }
+ }
+ for _, test := range compareFloatTests {
+ if got := CompareFunc(test.s1, test.s2, cmp.Compare[float64]); got != test.want {
+ t.Errorf("CompareFunc(%v, %v, cmp[float64]) = %d, want %d", test.s1, test.s2, got, test.want)
+ }
+ }
+
+ s1 := []int{1, 2, 3}
+ s2 := []int{2, 3, 4}
+ if got := CompareFunc(s1, s2, equalToCmp(offByOne)); got != 0 {
+ t.Errorf("CompareFunc(%v, %v, offByOne) = %d, want 0", s1, s2, got)
+ }
+
+ s3 := []string{"a", "b", "c"}
+ s4 := []string{"A", "B", "C"}
+ if got := CompareFunc(s3, s4, strings.Compare); got != 1 {
+ t.Errorf("CompareFunc(%v, %v, strings.Compare) = %d, want 1", s3, s4, got)
+ }
+
+ compareLower := func(v1, v2 string) int {
+ return strings.Compare(strings.ToLower(v1), strings.ToLower(v2))
+ }
+ if got := CompareFunc(s3, s4, compareLower); got != 0 {
+ t.Errorf("CompareFunc(%v, %v, compareLower) = %d, want 0", s3, s4, got)
+ }
+
+ cmpIntString := func(v1 int, v2 string) int {
+ return strings.Compare(string(rune(v1)-1+'a'), v2)
+ }
+ if got := CompareFunc(s1, s3, cmpIntString); got != 0 {
+ t.Errorf("CompareFunc(%v, %v, cmpIntString) = %d, want 0", s1, s3, got)
+ }
+}
+
var indexTests = []struct {
s []int
v int
}
}
+func BenchmarkIndex_Large(b *testing.B) {
+ type Large [4 * 1024]byte
+
+ ss := make([]Large, 1024)
+ for i := 0; i < b.N; i++ {
+ _ = Index(ss, Large{1})
+ }
+}
+
func TestIndexFunc(t *testing.T) {
for _, test := range indexTests {
if got := IndexFunc(test.s, equalToIndex(equal[int], test.v)); got != test.want {
}
}
+func BenchmarkIndexFunc_Large(b *testing.B) {
+ type Large [4 * 1024]byte
+
+ ss := make([]Large, 1024)
+ for i := 0; i < b.N; i++ {
+ _ = IndexFunc(ss, func(e Large) bool {
+ return e == Large{1}
+ })
+ }
+}
+
func TestContains(t *testing.T) {
for _, test := range indexTests {
if got := Contains(test.s, test.v); got != (test.want != -1) {
t.Errorf("Insert(%v, %d, %v...) = %v, want %v", test.s, test.i, test.add, got, test.want)
}
}
+
+ if !testenv.OptimizationOff() && !race.Enabled {
+ // Allocations should be amortized.
+ const count = 50
+ n := testing.AllocsPerRun(10, func() {
+ s := []int{1, 2, 3}
+ for i := 0; i < count; i++ {
+ s = Insert(s, 0, 1)
+ }
+ })
+ if n > count/2 {
+ t.Errorf("too many allocations inserting %d elements: got %v, want less than %d", count, n, count/2)
+ }
+ }
+}
+
+func TestInsertOverlap(t *testing.T) {
+ const N = 10
+ a := make([]int, N)
+ want := make([]int, 2*N)
+ for n := 0; n <= N; n++ { // length
+ for i := 0; i <= n; i++ { // insertion point
+ for x := 0; x <= N; x++ { // start of inserted data
+ for y := x; y <= N; y++ { // end of inserted data
+ for k := 0; k < N; k++ {
+ a[k] = k
+ }
+ want = want[:0]
+ want = append(want, a[:i]...)
+ want = append(want, a[x:y]...)
+ want = append(want, a[i:n]...)
+ got := Insert(a[:n], i, a[x:y]...)
+ if !Equal(got, want) {
+ t.Errorf("Insert with overlap failed n=%d i=%d x=%d y=%d, got %v want %v", n, i, x, y, got, want)
+ }
+ }
+ }
+ }
+ }
+}
+
+func TestInsertPanics(t *testing.T) {
+ a := [3]int{}
+ for _, test := range []struct {
+ name string
+ s []int
+ i int
+ v []int
+ }{
+ // There are no values.
+ {"with negative index", a[:1:1], -1, nil},
+ {"with out-of-bounds index and > cap", a[:1:1], 2, nil},
+ {"with out-of-bounds index and = cap", a[:1:2], 2, nil},
+ {"with out-of-bounds index and < cap", a[:1:3], 2, nil},
+ } {
+ if !panics(func() { Insert(test.s, test.i, test.v...) }) {
+ t.Errorf("Insert %s: got no panic, want panic", test.name)
+ }
+ }
}
var deleteTests = []struct {
}
func TestDeletePanics(t *testing.T) {
+ s := []int{0, 1, 2, 3, 4}
+ s = s[0:2]
+ _ = s[0:4] // this is a valid slice of s
+
for _, test := range []struct {
name string
s []int
{"with out-of-bounds first index", []int{42}, 2, 3},
{"with out-of-bounds second index", []int{42}, 0, 2},
{"with invalid i>j", []int{42}, 1, 0},
+ {"s[i:j] is valid and j > len(s)", s, 0, 4},
} {
if !panics(func() { Delete(test.s, test.i, test.j) }) {
t.Errorf("Delete %s: got no panic, want panic", test.name)
}
})
}
+}
+
+func BenchmarkCompact_Large(b *testing.B) {
+ type Large [4 * 1024]byte
+ ss := make([]Large, 1024)
+ for i := 0; i < b.N; i++ {
+ _ = Compact(ss)
+ }
}
func TestCompactFunc(t *testing.T) {
}
}
+func BenchmarkCompactFunc_Large(b *testing.B) {
+ type Large [4 * 1024]byte
+
+ ss := make([]Large, 1024)
+ for i := 0; i < b.N; i++ {
+ _ = CompactFunc(ss, func(a, b Large) bool { return a == b })
+ }
+}
+
func TestGrow(t *testing.T) {
s1 := []int{1, 2, 3}
}
}
+func TestReverse(t *testing.T) {
+ even := []int{3, 1, 4, 1, 5, 9} // len = 6
+ Reverse(even)
+ if want := []int{9, 5, 1, 4, 1, 3}; !Equal(even, want) {
+ t.Errorf("Reverse(even) = %v, want %v", even, want)
+ }
+
+ odd := []int{3, 1, 4, 1, 5, 9, 2} // len = 7
+ Reverse(odd)
+ if want := []int{2, 9, 5, 1, 4, 1, 3}; !Equal(odd, want) {
+ t.Errorf("Reverse(odd) = %v, want %v", odd, want)
+ }
+
+ words := strings.Fields("one two three")
+ Reverse(words)
+ if want := strings.Fields("three two one"); !Equal(words, want) {
+ t.Errorf("Reverse(words) = %v, want %v", words, want)
+ }
+
+ singleton := []string{"one"}
+ Reverse(singleton)
+ if want := []string{"one"}; !Equal(singleton, want) {
+ t.Errorf("Reverse(singeleton) = %v, want %v", singleton, want)
+ }
+
+ Reverse[[]string](nil)
+}
+
// naiveReplace is a baseline implementation to the Replace function.
func naiveReplace[S ~[]E, E any](s S, i, j int, v ...E) S {
s = Delete(s, i, j)
}
func TestReplacePanics(t *testing.T) {
+ s := []int{0, 1, 2, 3, 4}
+ s = s[0:2]
+ _ = s[0:4] // this is a valid slice of s
+
for _, test := range []struct {
name string
s, v []int
{"indexes out of order", []int{1, 2}, []int{3}, 2, 1},
{"large index", []int{1, 2}, []int{3}, 1, 10},
{"negative index", []int{1, 2}, []int{3}, -1, 2},
+ {"s[i:j] is valid and j > len(s)", s, nil, 0, 4},
} {
ss, vv := Clone(test.s), Clone(test.v)
if !panics(func() { Replace(ss, test.i, test.j, vv...) }) {
}
}
+func TestReplaceOverlap(t *testing.T) {
+ const N = 10
+ a := make([]int, N)
+ want := make([]int, 2*N)
+ for n := 0; n <= N; n++ { // length
+ for i := 0; i <= n; i++ { // insertion point 1
+ for j := i; j <= n; j++ { // insertion point 2
+ for x := 0; x <= N; x++ { // start of inserted data
+ for y := x; y <= N; y++ { // end of inserted data
+ for k := 0; k < N; k++ {
+ a[k] = k
+ }
+ want = want[:0]
+ want = append(want, a[:i]...)
+ want = append(want, a[x:y]...)
+ want = append(want, a[j:n]...)
+ got := Replace(a[:n], i, j, a[x:y]...)
+ if !Equal(got, want) {
+ 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)
+ }
+ }
+ }
+ }
+ }
+ }
+}
+
func BenchmarkReplace(b *testing.B) {
cases := []struct {
name string
}
}
+
+func TestInsertGrowthRate(t *testing.T) {
+ b := make([]byte, 1)
+ maxCap := cap(b)
+ nGrow := 0
+ const N = 1e6
+ for i := 0; i < N; i++ {
+ b = Insert(b, len(b)-1, 0)
+ if cap(b) > maxCap {
+ maxCap = cap(b)
+ nGrow++
+ }
+ }
+ want := int(math.Log(N) / math.Log(1.25)) // 1.25 == growth rate for large slices
+ if nGrow > want {
+ t.Errorf("too many grows. got:%d want:%d", nGrow, want)
+ }
+}
+
+func TestReplaceGrowthRate(t *testing.T) {
+ b := make([]byte, 2)
+ maxCap := cap(b)
+ nGrow := 0
+ const N = 1e6
+ for i := 0; i < N; i++ {
+ b = Replace(b, len(b)-2, len(b)-1, 0, 0)
+ if cap(b) > maxCap {
+ maxCap = cap(b)
+ nGrow++
+ }
+ }
+ want := int(math.Log(N) / math.Log(1.25)) // 1.25 == growth rate for large slices
+ if nGrow > want {
+ t.Errorf("too many grows. got:%d want:%d", nGrow, want)
+ }
+}
+
+func apply[T any](v T, f func(T)) {
+ f(v)
+}
+
+// Test type inference with a named slice type.
+func TestInference(t *testing.T) {
+ s1 := []int{1, 2, 3}
+ apply(s1, Reverse)
+ if want := []int{3, 2, 1}; !Equal(s1, want) {
+ t.Errorf("Reverse(%v) = %v, want %v", []int{1, 2, 3}, s1, want)
+ }
+
+ type S []int
+ s2 := S{4, 5, 6}
+ apply(s2, Reverse)
+ if want := (S{6, 5, 4}); !Equal(s2, want) {
+ t.Errorf("Reverse(%v) = %v, want %v", S{4, 5, 6}, s2, want)
+ }
+}
+
+func TestConcat(t *testing.T) {
+ cases := []struct {
+ s [][]int
+ want []int
+ }{
+ {
+ s: [][]int{nil},
+ want: nil,
+ },
+ {
+ s: [][]int{{1}},
+ want: []int{1},
+ },
+ {
+ s: [][]int{{1}, {2}},
+ want: []int{1, 2},
+ },
+ {
+ s: [][]int{{1}, nil, {2}},
+ want: []int{1, 2},
+ },
+ }
+ for _, tc := range cases {
+ got := Concat(tc.s...)
+ if !Equal(tc.want, got) {
+ t.Errorf("Concat(%v) = %v, want %v", tc.s, got, tc.want)
+ }
+ var sink []int
+ allocs := testing.AllocsPerRun(5, func() {
+ sink = Concat(tc.s...)
+ })
+ _ = sink
+ if allocs > 1 {
+ errorf := t.Errorf
+ if testenv.OptimizationOff() || race.Enabled {
+ errorf = t.Logf
+ }
+ errorf("Concat(%v) allocated %v times; want 1", tc.s, allocs)
+ }
+ }
+}
+
+func TestConcat_too_large(t *testing.T) {
+ // Use zero length element to minimize memory in testing
+ type void struct{}
+ cases := []struct {
+ lengths []int
+ shouldPanic bool
+ }{
+ {
+ lengths: []int{0, 0},
+ shouldPanic: false,
+ },
+ {
+ lengths: []int{math.MaxInt, 0},
+ shouldPanic: false,
+ },
+ {
+ lengths: []int{0, math.MaxInt},
+ shouldPanic: false,
+ },
+ {
+ lengths: []int{math.MaxInt - 1, 1},
+ shouldPanic: false,
+ },
+ {
+ lengths: []int{math.MaxInt - 1, 1, 1},
+ shouldPanic: true,
+ },
+ {
+ lengths: []int{math.MaxInt, 1},
+ shouldPanic: true,
+ },
+ {
+ lengths: []int{math.MaxInt, math.MaxInt},
+ shouldPanic: true,
+ },
+ }
+ for _, tc := range cases {
+ var r any
+ ss := make([][]void, 0, len(tc.lengths))
+ for _, l := range tc.lengths {
+ s := make([]void, l)
+ ss = append(ss, s)
+ }
+ func() {
+ defer func() {
+ r = recover()
+ }()
+ _ = Concat(ss...)
+ }()
+ if didPanic := r != nil; didPanic != tc.shouldPanic {
+ t.Errorf("slices.Concat(lens(%v)) got panic == %v",
+ tc.lengths, didPanic)
+ }
+ }
+}