| // Copyright 2021 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package slices_test |
| |
| import ( |
| "cmp" |
| "internal/race" |
| "internal/testenv" |
| "math" |
| . "slices" |
| "strings" |
| "testing" |
| ) |
| |
| var equalIntTests = []struct { |
| s1, s2 []int |
| want bool |
| }{ |
| { |
| []int{1}, |
| nil, |
| false, |
| }, |
| { |
| []int{}, |
| nil, |
| true, |
| }, |
| { |
| []int{1, 2, 3}, |
| []int{1, 2, 3}, |
| true, |
| }, |
| { |
| []int{1, 2, 3}, |
| []int{1, 2, 3, 4}, |
| false, |
| }, |
| } |
| |
| var equalFloatTests = []struct { |
| s1, s2 []float64 |
| wantEqual bool |
| wantEqualNaN bool |
| }{ |
| { |
| []float64{1, 2}, |
| []float64{1, 2}, |
| true, |
| true, |
| }, |
| { |
| []float64{1, 2, math.NaN()}, |
| []float64{1, 2, math.NaN()}, |
| false, |
| true, |
| }, |
| } |
| |
| func TestEqual(t *testing.T) { |
| for _, test := range equalIntTests { |
| if got := Equal(test.s1, test.s2); got != test.want { |
| t.Errorf("Equal(%v, %v) = %t, want %t", test.s1, test.s2, got, test.want) |
| } |
| } |
| for _, test := range equalFloatTests { |
| if got := Equal(test.s1, test.s2); got != test.wantEqual { |
| t.Errorf("Equal(%v, %v) = %t, want %t", test.s1, test.s2, got, test.wantEqual) |
| } |
| } |
| } |
| |
| // equal is simply ==. |
| func equal[T comparable](v1, v2 T) bool { |
| return v1 == v2 |
| } |
| |
| // equalNaN is like == except that all NaNs are equal. |
| func equalNaN[T comparable](v1, v2 T) bool { |
| isNaN := func(f T) bool { return f != f } |
| return v1 == v2 || (isNaN(v1) && isNaN(v2)) |
| } |
| |
| // offByOne returns true if integers v1 and v2 differ by 1. |
| func offByOne(v1, v2 int) bool { |
| return v1 == v2+1 || v1 == v2-1 |
| } |
| |
| func TestEqualFunc(t *testing.T) { |
| for _, test := range equalIntTests { |
| if got := EqualFunc(test.s1, test.s2, equal[int]); got != test.want { |
| t.Errorf("EqualFunc(%v, %v, equal[int]) = %t, want %t", test.s1, test.s2, got, test.want) |
| } |
| } |
| for _, test := range equalFloatTests { |
| if got := EqualFunc(test.s1, test.s2, equal[float64]); got != test.wantEqual { |
| t.Errorf("Equal(%v, %v, equal[float64]) = %t, want %t", test.s1, test.s2, got, test.wantEqual) |
| } |
| if got := EqualFunc(test.s1, test.s2, equalNaN[float64]); got != test.wantEqualNaN { |
| t.Errorf("Equal(%v, %v, equalNaN[float64]) = %t, want %t", test.s1, test.s2, got, test.wantEqualNaN) |
| } |
| } |
| |
| s1 := []int{1, 2, 3} |
| s2 := []int{2, 3, 4} |
| if EqualFunc(s1, s1, offByOne) { |
| t.Errorf("EqualFunc(%v, %v, offByOne) = true, want false", s1, s1) |
| } |
| if !EqualFunc(s1, s2, offByOne) { |
| t.Errorf("EqualFunc(%v, %v, offByOne) = false, want true", s1, s2) |
| } |
| |
| s3 := []string{"a", "b", "c"} |
| s4 := []string{"A", "B", "C"} |
| if !EqualFunc(s3, s4, strings.EqualFold) { |
| t.Errorf("EqualFunc(%v, %v, strings.EqualFold) = false, want true", s3, s4) |
| } |
| |
| cmpIntString := func(v1 int, v2 string) bool { |
| return string(rune(v1)-1+'a') == v2 |
| } |
| if !EqualFunc(s1, s3, cmpIntString) { |
| t.Errorf("EqualFunc(%v, %v, cmpIntString) = false, want true", s1, s3) |
| } |
| } |
| |
| 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 |
| want int |
| }{ |
| { |
| nil, |
| 0, |
| -1, |
| }, |
| { |
| []int{}, |
| 0, |
| -1, |
| }, |
| { |
| []int{1, 2, 3}, |
| 2, |
| 1, |
| }, |
| { |
| []int{1, 2, 2, 3}, |
| 2, |
| 1, |
| }, |
| { |
| []int{1, 2, 3, 2}, |
| 2, |
| 1, |
| }, |
| } |
| |
| func TestIndex(t *testing.T) { |
| for _, test := range indexTests { |
| if got := Index(test.s, test.v); got != test.want { |
| t.Errorf("Index(%v, %v) = %d, want %d", test.s, test.v, got, test.want) |
| } |
| } |
| } |
| |
| func equalToIndex[T any](f func(T, T) bool, v1 T) func(T) bool { |
| return func(v2 T) bool { |
| return f(v1, v2) |
| } |
| } |
| |
| 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 { |
| t.Errorf("IndexFunc(%v, equalToIndex(equal[int], %v)) = %d, want %d", test.s, test.v, got, test.want) |
| } |
| } |
| |
| s1 := []string{"hi", "HI"} |
| if got := IndexFunc(s1, equalToIndex(equal[string], "HI")); got != 1 { |
| t.Errorf("IndexFunc(%v, equalToIndex(equal[string], %q)) = %d, want %d", s1, "HI", got, 1) |
| } |
| if got := IndexFunc(s1, equalToIndex(strings.EqualFold, "HI")); got != 0 { |
| t.Errorf("IndexFunc(%v, equalToIndex(strings.EqualFold, %q)) = %d, want %d", s1, "HI", got, 0) |
| } |
| } |
| |
| 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("Contains(%v, %v) = %t, want %t", test.s, test.v, got, test.want != -1) |
| } |
| } |
| } |
| |
| func TestContainsFunc(t *testing.T) { |
| for _, test := range indexTests { |
| if got := ContainsFunc(test.s, equalToIndex(equal[int], test.v)); got != (test.want != -1) { |
| t.Errorf("ContainsFunc(%v, equalToIndex(equal[int], %v)) = %t, want %t", test.s, test.v, got, test.want != -1) |
| } |
| } |
| |
| s1 := []string{"hi", "HI"} |
| if got := ContainsFunc(s1, equalToIndex(equal[string], "HI")); got != true { |
| t.Errorf("ContainsFunc(%v, equalToContains(equal[string], %q)) = %t, want %t", s1, "HI", got, true) |
| } |
| if got := ContainsFunc(s1, equalToIndex(equal[string], "hI")); got != false { |
| t.Errorf("ContainsFunc(%v, equalToContains(strings.EqualFold, %q)) = %t, want %t", s1, "hI", got, false) |
| } |
| if got := ContainsFunc(s1, equalToIndex(strings.EqualFold, "hI")); got != true { |
| t.Errorf("ContainsFunc(%v, equalToContains(strings.EqualFold, %q)) = %t, want %t", s1, "hI", got, true) |
| } |
| } |
| |
| var insertTests = []struct { |
| s []int |
| i int |
| add []int |
| want []int |
| }{ |
| { |
| []int{1, 2, 3}, |
| 0, |
| []int{4}, |
| []int{4, 1, 2, 3}, |
| }, |
| { |
| []int{1, 2, 3}, |
| 1, |
| []int{4}, |
| []int{1, 4, 2, 3}, |
| }, |
| { |
| []int{1, 2, 3}, |
| 3, |
| []int{4}, |
| []int{1, 2, 3, 4}, |
| }, |
| { |
| []int{1, 2, 3}, |
| 2, |
| []int{4, 5}, |
| []int{1, 2, 4, 5, 3}, |
| }, |
| } |
| |
| func TestInsert(t *testing.T) { |
| s := []int{1, 2, 3} |
| if got := Insert(s, 0); !Equal(got, s) { |
| t.Errorf("Insert(%v, 0) = %v, want %v", s, got, s) |
| } |
| for _, test := range insertTests { |
| copy := Clone(test.s) |
| if got := Insert(copy, test.i, test.add...); !Equal(got, test.want) { |
| 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{} |
| b := [1]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}, |
| |
| // There are values. |
| {"with negative index", a[:1:1], -1, b[:]}, |
| {"with out-of-bounds index and > cap", a[:1:1], 2, b[:]}, |
| {"with out-of-bounds index and = cap", a[:1:2], 2, b[:]}, |
| {"with out-of-bounds index and < cap", a[:1:3], 2, b[:]}, |
| } { |
| if !panics(func() { _ = Insert(test.s, test.i, test.v...) }) { |
| t.Errorf("Insert %s: got no panic, want panic", test.name) |
| } |
| } |
| } |
| |
| var deleteTests = []struct { |
| s []int |
| i, j int |
| want []int |
| }{ |
| { |
| []int{1, 2, 3}, |
| 0, |
| 0, |
| []int{1, 2, 3}, |
| }, |
| { |
| []int{1, 2, 3}, |
| 0, |
| 1, |
| []int{2, 3}, |
| }, |
| { |
| []int{1, 2, 3}, |
| 3, |
| 3, |
| []int{1, 2, 3}, |
| }, |
| { |
| []int{1, 2, 3}, |
| 0, |
| 2, |
| []int{3}, |
| }, |
| { |
| []int{1, 2, 3}, |
| 0, |
| 3, |
| []int{}, |
| }, |
| } |
| |
| func TestDelete(t *testing.T) { |
| for _, test := range deleteTests { |
| copy := Clone(test.s) |
| if got := Delete(copy, test.i, test.j); !Equal(got, test.want) { |
| t.Errorf("Delete(%v, %d, %d) = %v, want %v", test.s, test.i, test.j, got, test.want) |
| } |
| } |
| } |
| |
| var deleteFuncTests = []struct { |
| s []int |
| fn func(int) bool |
| want []int |
| }{ |
| { |
| nil, |
| func(int) bool { return true }, |
| nil, |
| }, |
| { |
| []int{1, 2, 3}, |
| func(int) bool { return true }, |
| nil, |
| }, |
| { |
| []int{1, 2, 3}, |
| func(int) bool { return false }, |
| []int{1, 2, 3}, |
| }, |
| { |
| []int{1, 2, 3}, |
| func(i int) bool { return i > 2 }, |
| []int{1, 2}, |
| }, |
| { |
| []int{1, 2, 3}, |
| func(i int) bool { return i < 2 }, |
| []int{2, 3}, |
| }, |
| { |
| []int{10, 2, 30}, |
| func(i int) bool { return i >= 10 }, |
| []int{2}, |
| }, |
| } |
| |
| func TestDeleteFunc(t *testing.T) { |
| for i, test := range deleteFuncTests { |
| copy := Clone(test.s) |
| if got := DeleteFunc(copy, test.fn); !Equal(got, test.want) { |
| t.Errorf("DeleteFunc case %d: got %v, want %v", i, got, test.want) |
| } |
| } |
| } |
| |
| func panics(f func()) (b bool) { |
| defer func() { |
| if x := recover(); x != nil { |
| b = true |
| } |
| }() |
| f() |
| return false |
| } |
| |
| 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 |
| i, j int |
| }{ |
| {"with negative first index", []int{42}, -2, 1}, |
| {"with negative second index", []int{42}, 1, -1}, |
| {"with out-of-bounds first index", []int{42}, 2, 3}, |
| {"with out-of-bounds second index", []int{42}, 0, 2}, |
| {"with out-of-bounds both indexes", []int{42}, 2, 2}, |
| {"with invalid i>j", []int{42}, 1, 0}, |
| {"s[i:j] is valid and j > len(s)", s, 0, 4}, |
| {"s[i:j] is valid and i == j > len(s)", s, 3, 3}, |
| } { |
| if !panics(func() { _ = Delete(test.s, test.i, test.j) }) { |
| t.Errorf("Delete %s: got no panic, want panic", test.name) |
| } |
| } |
| } |
| |
| func TestDeleteClearTail(t *testing.T) { |
| mem := []*int{new(int), new(int), new(int), new(int), new(int), new(int)} |
| s := mem[0:5] // there is 1 element beyond len(s), within cap(s) |
| |
| s = Delete(s, 2, 4) |
| |
| if mem[3] != nil || mem[4] != nil { |
| // Check that potential memory leak is avoided |
| t.Errorf("Delete: want nil discarded elements, got %v, %v", mem[3], mem[4]) |
| } |
| if mem[5] == nil { |
| t.Errorf("Delete: want unchanged elements beyond original len, got nil") |
| } |
| } |
| |
| func TestDeleteFuncClearTail(t *testing.T) { |
| mem := []*int{new(int), new(int), new(int), new(int), new(int), new(int)} |
| *mem[2], *mem[3] = 42, 42 |
| s := mem[0:5] // there is 1 element beyond len(s), within cap(s) |
| |
| s = DeleteFunc(s, func(i *int) bool { |
| return i != nil && *i == 42 |
| }) |
| |
| if mem[3] != nil || mem[4] != nil { |
| // Check that potential memory leak is avoided |
| t.Errorf("DeleteFunc: want nil discarded elements, got %v, %v", mem[3], mem[4]) |
| } |
| if mem[5] == nil { |
| t.Errorf("DeleteFunc: want unchanged elements beyond original len, got nil") |
| } |
| } |
| |
| func TestClone(t *testing.T) { |
| s1 := []int{1, 2, 3} |
| s2 := Clone(s1) |
| if !Equal(s1, s2) { |
| t.Errorf("Clone(%v) = %v, want %v", s1, s2, s1) |
| } |
| s1[0] = 4 |
| want := []int{1, 2, 3} |
| if !Equal(s2, want) { |
| t.Errorf("Clone(%v) changed unexpectedly to %v", want, s2) |
| } |
| if got := Clone([]int(nil)); got != nil { |
| t.Errorf("Clone(nil) = %#v, want nil", got) |
| } |
| if got := Clone(s1[:0]); got == nil || len(got) != 0 { |
| t.Errorf("Clone(%v) = %#v, want %#v", s1[:0], got, s1[:0]) |
| } |
| } |
| |
| var compactTests = []struct { |
| name string |
| s []int |
| want []int |
| }{ |
| { |
| "nil", |
| nil, |
| nil, |
| }, |
| { |
| "one", |
| []int{1}, |
| []int{1}, |
| }, |
| { |
| "sorted", |
| []int{1, 2, 3}, |
| []int{1, 2, 3}, |
| }, |
| { |
| "1 item", |
| []int{1, 1, 2}, |
| []int{1, 2}, |
| }, |
| { |
| "unsorted", |
| []int{1, 2, 1}, |
| []int{1, 2, 1}, |
| }, |
| { |
| "many", |
| []int{1, 2, 2, 3, 3, 4}, |
| []int{1, 2, 3, 4}, |
| }, |
| } |
| |
| func TestCompact(t *testing.T) { |
| for _, test := range compactTests { |
| copy := Clone(test.s) |
| if got := Compact(copy); !Equal(got, test.want) { |
| t.Errorf("Compact(%v) = %v, want %v", test.s, got, test.want) |
| } |
| } |
| } |
| |
| func BenchmarkCompact(b *testing.B) { |
| for _, c := range compactTests { |
| b.Run(c.name, func(b *testing.B) { |
| ss := make([]int, 0, 64) |
| for k := 0; k < b.N; k++ { |
| ss = ss[:0] |
| ss = append(ss, c.s...) |
| _ = Compact(ss) |
| } |
| }) |
| } |
| } |
| |
| 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) { |
| for _, test := range compactTests { |
| copy := Clone(test.s) |
| if got := CompactFunc(copy, equal[int]); !Equal(got, test.want) { |
| t.Errorf("CompactFunc(%v, equal[int]) = %v, want %v", test.s, got, test.want) |
| } |
| } |
| |
| s1 := []string{"a", "a", "A", "B", "b"} |
| copy := Clone(s1) |
| want := []string{"a", "B"} |
| if got := CompactFunc(copy, strings.EqualFold); !Equal(got, want) { |
| t.Errorf("CompactFunc(%v, strings.EqualFold) = %v, want %v", s1, got, want) |
| } |
| } |
| |
| func TestCompactClearTail(t *testing.T) { |
| one, two, three, four := 1, 2, 3, 4 |
| mem := []*int{&one, &one, &two, &two, &three, &four} |
| s := mem[0:5] // there is 1 element beyond len(s), within cap(s) |
| copy := Clone(s) |
| |
| s = Compact(s) |
| |
| if want := []*int{&one, &two, &three}; !Equal(s, want) { |
| t.Errorf("Compact(%v) = %v, want %v", copy, s, want) |
| } |
| |
| if mem[3] != nil || mem[4] != nil { |
| // Check that potential memory leak is avoided |
| t.Errorf("Compact: want nil discarded elements, got %v, %v", mem[3], mem[4]) |
| } |
| if mem[5] != &four { |
| t.Errorf("Compact: want unchanged element beyond original len, got %v", mem[5]) |
| } |
| } |
| |
| func TestCompactFuncClearTail(t *testing.T) { |
| a, b, c, d, e, f := 1, 1, 2, 2, 3, 4 |
| mem := []*int{&a, &b, &c, &d, &e, &f} |
| s := mem[0:5] // there is 1 element beyond len(s), within cap(s) |
| copy := Clone(s) |
| |
| s = CompactFunc(s, func(x, y *int) bool { |
| if x == nil || y == nil { |
| return x == y |
| } |
| return *x == *y |
| }) |
| |
| if want := []*int{&a, &c, &e}; !Equal(s, want) { |
| t.Errorf("CompactFunc(%v) = %v, want %v", copy, s, want) |
| } |
| |
| if mem[3] != nil || mem[4] != nil { |
| // Check that potential memory leak is avoided |
| t.Errorf("CompactFunc: want nil discarded elements, got %v, %v", mem[3], mem[4]) |
| } |
| if mem[5] != &f { |
| t.Errorf("CompactFunc: want unchanged elements beyond original len, got %v", mem[5]) |
| } |
| } |
| |
| 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} |
| |
| copy := Clone(s1) |
| s2 := Grow(copy, 1000) |
| if !Equal(s1, s2) { |
| t.Errorf("Grow(%v) = %v, want %v", s1, s2, s1) |
| } |
| if cap(s2) < 1000+len(s1) { |
| t.Errorf("after Grow(%v) cap = %d, want >= %d", s1, cap(s2), 1000+len(s1)) |
| } |
| |
| // Test mutation of elements between length and capacity. |
| copy = Clone(s1) |
| s3 := Grow(copy[:1], 2)[:3] |
| if !Equal(s1, s3) { |
| t.Errorf("Grow should not mutate elements between length and capacity") |
| } |
| s3 = Grow(copy[:1], 1000)[:3] |
| if !Equal(s1, s3) { |
| t.Errorf("Grow should not mutate elements between length and capacity") |
| } |
| |
| // Test number of allocations. |
| if n := testing.AllocsPerRun(100, func() { _ = Grow(s2, cap(s2)-len(s2)) }); n != 0 { |
| t.Errorf("Grow should not allocate when given sufficient capacity; allocated %v times", n) |
| } |
| if n := testing.AllocsPerRun(100, func() { _ = Grow(s2, cap(s2)-len(s2)+1) }); n != 1 { |
| errorf := t.Errorf |
| if race.Enabled || testenv.OptimizationOff() { |
| errorf = t.Logf // this allocates multiple times in race detector mode |
| } |
| errorf("Grow should allocate once when given insufficient capacity; allocated %v times", n) |
| } |
| |
| // Test for negative growth sizes. |
| var gotPanic bool |
| func() { |
| defer func() { gotPanic = recover() != nil }() |
| _ = Grow(s1, -1) |
| }() |
| if !gotPanic { |
| t.Errorf("Grow(-1) did not panic; expected a panic") |
| } |
| } |
| |
| func TestClip(t *testing.T) { |
| s1 := []int{1, 2, 3, 4, 5, 6}[:3] |
| orig := Clone(s1) |
| if len(s1) != 3 { |
| t.Errorf("len(%v) = %d, want 3", s1, len(s1)) |
| } |
| if cap(s1) < 6 { |
| t.Errorf("cap(%v[:3]) = %d, want >= 6", orig, cap(s1)) |
| } |
| s2 := Clip(s1) |
| if !Equal(s1, s2) { |
| t.Errorf("Clip(%v) = %v, want %v", s1, s2, s1) |
| } |
| if cap(s2) != 3 { |
| t.Errorf("cap(Clip(%v)) = %d, want 3", orig, cap(s2)) |
| } |
| } |
| |
| 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) |
| s = Insert(s, i, v...) |
| return s |
| } |
| |
| func TestReplace(t *testing.T) { |
| for _, test := range []struct { |
| s, v []int |
| i, j int |
| }{ |
| {}, // all zero value |
| { |
| s: []int{1, 2, 3, 4}, |
| v: []int{5}, |
| i: 1, |
| j: 2, |
| }, |
| { |
| s: []int{1, 2, 3, 4}, |
| v: []int{5, 6, 7, 8}, |
| i: 1, |
| j: 2, |
| }, |
| { |
| s: func() []int { |
| s := make([]int, 3, 20) |
| s[0] = 0 |
| s[1] = 1 |
| s[2] = 2 |
| return s |
| }(), |
| v: []int{3, 4, 5, 6, 7}, |
| i: 0, |
| j: 1, |
| }, |
| } { |
| ss, vv := Clone(test.s), Clone(test.v) |
| want := naiveReplace(ss, test.i, test.j, vv...) |
| got := Replace(test.s, test.i, test.j, test.v...) |
| if !Equal(got, want) { |
| t.Errorf("Replace(%v, %v, %v, %v) = %v, want %v", test.s, test.i, test.j, test.v, got, want) |
| } |
| } |
| } |
| |
| 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 |
| i, j 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...) }) { |
| t.Errorf("Replace %s: should have panicked", test.name) |
| } |
| } |
| } |
| |
| func TestReplaceGrow(t *testing.T) { |
| // When Replace needs to allocate a new slice, we want the original slice |
| // to not be changed. |
| a, b, c, d, e, f := 1, 2, 3, 4, 5, 6 |
| mem := []*int{&a, &b, &c, &d, &e, &f} |
| memcopy := Clone(mem) |
| s := mem[0:5] // there is 1 element beyond len(s), within cap(s) |
| copy := Clone(s) |
| original := s |
| |
| // The new elements don't fit within cap(s), so Replace will allocate. |
| z := 99 |
| s = Replace(s, 1, 3, &z, &z, &z, &z) |
| |
| if want := []*int{&a, &z, &z, &z, &z, &d, &e}; !Equal(s, want) { |
| t.Errorf("Replace(%v, 1, 3, %v, %v, %v, %v) = %v, want %v", copy, &z, &z, &z, &z, s, want) |
| } |
| |
| if !Equal(original, copy) { |
| t.Errorf("original slice has changed, got %v, want %v", original, copy) |
| } |
| |
| if !Equal(mem, memcopy) { |
| // Changing the original tail s[len(s):cap(s)] is unwanted |
| t.Errorf("original backing memory has changed, got %v, want %v", mem, memcopy) |
| } |
| } |
| |
| func TestReplaceClearTail(t *testing.T) { |
| a, b, c, d, e, f := 1, 2, 3, 4, 5, 6 |
| mem := []*int{&a, &b, &c, &d, &e, &f} |
| s := mem[0:5] // there is 1 element beyond len(s), within cap(s) |
| copy := Clone(s) |
| |
| y, z := 8, 9 |
| s = Replace(s, 1, 4, &y, &z) |
| |
| if want := []*int{&a, &y, &z, &e}; !Equal(s, want) { |
| t.Errorf("Replace(%v) = %v, want %v", copy, s, want) |
| } |
| |
| if mem[4] != nil { |
| // Check that potential memory leak is avoided |
| t.Errorf("Replace: want nil discarded element, got %v", mem[4]) |
| } |
| if mem[5] != &f { |
| t.Errorf("Replace: want unchanged elements beyond original len, got %v", mem[5]) |
| } |
| } |
| |
| 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 TestReplaceEndClearTail(t *testing.T) { |
| s := []int{11, 22, 33} |
| v := []int{99} |
| // case when j == len(s) |
| i, j := 1, 3 |
| s = Replace(s, i, j, v...) |
| |
| x := s[:3][2] |
| if want := 0; x != want { |
| t.Errorf("TestReplaceEndClearTail: obsolete element is %d, want %d", x, want) |
| } |
| } |
| |
| func BenchmarkReplace(b *testing.B) { |
| cases := []struct { |
| name string |
| s, v func() []int |
| i, j int |
| }{ |
| { |
| name: "fast", |
| s: func() []int { |
| return make([]int, 100) |
| }, |
| v: func() []int { |
| return make([]int, 20) |
| }, |
| i: 10, |
| j: 40, |
| }, |
| { |
| name: "slow", |
| s: func() []int { |
| return make([]int, 100) |
| }, |
| v: func() []int { |
| return make([]int, 20) |
| }, |
| i: 0, |
| j: 2, |
| }, |
| } |
| |
| for _, c := range cases { |
| b.Run("naive-"+c.name, func(b *testing.B) { |
| for k := 0; k < b.N; k++ { |
| s := c.s() |
| v := c.v() |
| _ = naiveReplace(s, c.i, c.j, v...) |
| } |
| }) |
| b.Run("optimized-"+c.name, func(b *testing.B) { |
| for k := 0; k < b.N; k++ { |
| s := c.s() |
| v := c.v() |
| _ = Replace(s, c.i, c.j, v...) |
| } |
| }) |
| } |
| |
| } |
| |
| 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) |
| } |
| } |
| } |
| |
| func TestRepeat(t *testing.T) { |
| // normal cases |
| for _, tc := range []struct { |
| x []int |
| count int |
| want []int |
| }{ |
| {x: []int(nil), count: 0, want: []int{}}, |
| {x: []int(nil), count: 1, want: []int{}}, |
| {x: []int(nil), count: math.MaxInt, want: []int{}}, |
| {x: []int{}, count: 0, want: []int{}}, |
| {x: []int{}, count: 1, want: []int{}}, |
| {x: []int{}, count: math.MaxInt, want: []int{}}, |
| {x: []int{0}, count: 0, want: []int{}}, |
| {x: []int{0}, count: 1, want: []int{0}}, |
| {x: []int{0}, count: 2, want: []int{0, 0}}, |
| {x: []int{0}, count: 3, want: []int{0, 0, 0}}, |
| {x: []int{0}, count: 4, want: []int{0, 0, 0, 0}}, |
| {x: []int{0, 1}, count: 0, want: []int{}}, |
| {x: []int{0, 1}, count: 1, want: []int{0, 1}}, |
| {x: []int{0, 1}, count: 2, want: []int{0, 1, 0, 1}}, |
| {x: []int{0, 1}, count: 3, want: []int{0, 1, 0, 1, 0, 1}}, |
| {x: []int{0, 1}, count: 4, want: []int{0, 1, 0, 1, 0, 1, 0, 1}}, |
| {x: []int{0, 1, 2}, count: 0, want: []int{}}, |
| {x: []int{0, 1, 2}, count: 1, want: []int{0, 1, 2}}, |
| {x: []int{0, 1, 2}, count: 2, want: []int{0, 1, 2, 0, 1, 2}}, |
| {x: []int{0, 1, 2}, count: 3, want: []int{0, 1, 2, 0, 1, 2, 0, 1, 2}}, |
| {x: []int{0, 1, 2}, count: 4, want: []int{0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2}}, |
| } { |
| if got := Repeat(tc.x, tc.count); got == nil || cap(got) != cap(tc.want) || !Equal(got, tc.want) { |
| t.Errorf("Repeat(%v, %v): got: %v, want: %v, (got == nil): %v, cap(got): %v, cap(want): %v", |
| tc.x, tc.count, got, tc.want, got == nil, cap(got), cap(tc.want)) |
| } |
| } |
| |
| // big slices |
| for _, tc := range []struct { |
| x []struct{} |
| count int |
| want []struct{} |
| }{ |
| {x: make([]struct{}, math.MaxInt/1-0), count: 1, want: make([]struct{}, 1*(math.MaxInt/1-0))}, |
| {x: make([]struct{}, math.MaxInt/2-1), count: 2, want: make([]struct{}, 2*(math.MaxInt/2-1))}, |
| {x: make([]struct{}, math.MaxInt/3-2), count: 3, want: make([]struct{}, 3*(math.MaxInt/3-2))}, |
| {x: make([]struct{}, math.MaxInt/4-3), count: 4, want: make([]struct{}, 4*(math.MaxInt/4-3))}, |
| {x: make([]struct{}, math.MaxInt/5-4), count: 5, want: make([]struct{}, 5*(math.MaxInt/5-4))}, |
| {x: make([]struct{}, math.MaxInt/6-5), count: 6, want: make([]struct{}, 6*(math.MaxInt/6-5))}, |
| {x: make([]struct{}, math.MaxInt/7-6), count: 7, want: make([]struct{}, 7*(math.MaxInt/7-6))}, |
| {x: make([]struct{}, math.MaxInt/8-7), count: 8, want: make([]struct{}, 8*(math.MaxInt/8-7))}, |
| {x: make([]struct{}, math.MaxInt/9-8), count: 9, want: make([]struct{}, 9*(math.MaxInt/9-8))}, |
| } { |
| if got := Repeat(tc.x, tc.count); got == nil || len(got) != len(tc.want) || cap(got) != cap(tc.want) { |
| t.Errorf("Repeat(make([]struct{}, %v), %v): (got == nil): %v, len(got): %v, len(want): %v, cap(got): %v, cap(want): %v", |
| len(tc.x), tc.count, got == nil, len(got), len(tc.want), cap(got), cap(tc.want)) |
| } |
| } |
| } |
| |
| func TestRepeatPanics(t *testing.T) { |
| for _, test := range []struct { |
| name string |
| x []struct{} |
| count int |
| }{ |
| {name: "cannot be negative", x: make([]struct{}, 0), count: -1}, |
| {name: "the result of (len(x) * count) overflows, hi > 0", x: make([]struct{}, 3), count: math.MaxInt}, |
| {name: "the result of (len(x) * count) overflows, lo > maxInt", x: make([]struct{}, 2), count: 1 + math.MaxInt/2}, |
| } { |
| if !panics(func() { _ = Repeat(test.x, test.count) }) { |
| t.Errorf("Repeat %s: got no panic, want panic", test.name) |
| } |
| } |
| } |