diff options
author | Ian Lance Taylor <iant@golang.org> | 2023-06-13 09:46:50 -0700 |
---|---|---|
committer | Gopher Robot <gobot@golang.org> | 2023-06-14 17:09:34 +0000 |
commit | 0a48e5cbfabd679eecdec1efa731692cd6babf83 (patch) | |
tree | 50f1d76e401a530536c40af010459bc08fad0d69 /src/slices | |
parent | 01b649b7ef45b89610a47efa048b8e73e76b078e (diff) | |
download | go-0a48e5cbfabd679eecdec1efa731692cd6babf83.tar.gz go-0a48e5cbfabd679eecdec1efa731692cd6babf83.zip |
slices: consistently use S ~[]E
Make all functions use a constraint S ~[]E even if they don't return
the slice type. This makes explicitly instantiating the functions more
consistent: you don't have to remember which take ~[]E and which do not.
It also permits inferring the type when passing one of these functions
to some other function that is using a named slice type.
Fixes #60546
Change-Id: Ib3435255d0177fdbf03455ae527d08599b1ce012
Reviewed-on: https://go-review.googlesource.com/c/go/+/502955
Reviewed-by: Ian Lance Taylor <iant@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@google.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Axel Wagner <axel.wagner.hh@googlemail.com>
Reviewed-by: Eli Bendersky <eliben@google.com>
Run-TryBot: Ian Lance Taylor <iant@google.com>
Auto-Submit: Ian Lance Taylor <iant@google.com>
Diffstat (limited to 'src/slices')
-rw-r--r-- | src/slices/slices.go | 28 | ||||
-rw-r--r-- | src/slices/slices_test.go | 22 | ||||
-rw-r--r-- | src/slices/sort.go | 22 |
3 files changed, 46 insertions, 26 deletions
diff --git a/src/slices/slices.go b/src/slices/slices.go index be869fe480..c8eacae90e 100644 --- a/src/slices/slices.go +++ b/src/slices/slices.go @@ -15,7 +15,7 @@ import ( // Otherwise, the elements are compared in increasing index order, and the // comparison stops at the first unequal pair. // Floating point NaNs are not considered equal. -func Equal[E comparable](s1, s2 []E) bool { +func Equal[S ~[]E, E comparable](s1, s2 S) bool { if len(s1) != len(s2) { return false } @@ -32,7 +32,7 @@ func Equal[E comparable](s1, s2 []E) bool { // EqualFunc returns false. Otherwise, the elements are compared in // increasing index order, and the comparison stops at the first index // for which eq returns false. -func EqualFunc[E1, E2 any](s1 []E1, s2 []E2, eq func(E1, E2) bool) bool { +func EqualFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, eq func(E1, E2) bool) bool { if len(s1) != len(s2) { return false } @@ -52,7 +52,7 @@ func EqualFunc[E1, E2 any](s1 []E1, s2 []E2, eq func(E1, E2) bool) bool { // If both slices are equal until one of them ends, the shorter slice is // considered less than the longer one. // The result is 0 if s1 == s2, -1 if s1 < s2, and +1 if s1 > s2. -func Compare[E cmp.Ordered](s1, s2 []E) int { +func Compare[S ~[]E, E cmp.Ordered](s1, s2 S) int { for i, v1 := range s1 { if i >= len(s2) { return +1 @@ -73,7 +73,7 @@ func Compare[E cmp.Ordered](s1, s2 []E) int { // The result is the first non-zero result of cmp; if cmp always // returns 0 the result is 0 if len(s1) == len(s2), -1 if len(s1) < len(s2), // and +1 if len(s1) > len(s2). -func CompareFunc[E1, E2 any](s1 []E1, s2 []E2, cmp func(E1, E2) int) int { +func CompareFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, cmp func(E1, E2) int) int { for i, v1 := range s1 { if i >= len(s2) { return +1 @@ -91,7 +91,7 @@ func CompareFunc[E1, E2 any](s1 []E1, s2 []E2, cmp func(E1, E2) int) int { // Index returns the index of the first occurrence of v in s, // or -1 if not present. -func Index[E comparable](s []E, v E) int { +func Index[S ~[]E, E comparable](s S, v E) int { for i := range s { if v == s[i] { return i @@ -102,7 +102,7 @@ func Index[E comparable](s []E, v E) int { // IndexFunc returns the first index i satisfying f(s[i]), // or -1 if none do. -func IndexFunc[E any](s []E, f func(E) bool) int { +func IndexFunc[S ~[]E, E any](s S, f func(E) bool) int { for i := range s { if f(s[i]) { return i @@ -112,13 +112,13 @@ func IndexFunc[E any](s []E, f func(E) bool) int { } // Contains reports whether v is present in s. -func Contains[E comparable](s []E, v E) bool { +func Contains[S ~[]E, E comparable](s S, v E) bool { return Index(s, v) >= 0 } // ContainsFunc reports whether at least one // element e of s satisfies f(e). -func ContainsFunc[E any](s []E, f func(E) bool) bool { +func ContainsFunc[S ~[]E, E any](s S, f func(E) bool) bool { return IndexFunc(s, f) >= 0 } @@ -441,7 +441,7 @@ func Clip[S ~[]E, E any](s S) S { // rotateLeft rotates b left by n spaces. // s_final[i] = s_orig[i+r], wrapping around. -func rotateLeft[S ~[]E, E any](s S, r int) { +func rotateLeft[E any](s []E, r int) { for r != 0 && r != len(s) { if r*2 <= len(s) { swap(s[:r], s[len(s)-r:]) @@ -452,19 +452,19 @@ func rotateLeft[S ~[]E, E any](s S, r int) { } } } -func rotateRight[S ~[]E, E any](s S, r int) { +func rotateRight[E any](s []E, r int) { rotateLeft(s, len(s)-r) } // swap swaps the contents of x and y. x and y must be equal length and disjoint. -func swap[S ~[]E, E any](x, y S) { +func swap[E any](x, y []E) { for i := 0; i < len(x); i++ { x[i], y[i] = y[i], x[i] } } // overlaps reports whether the memory ranges a[0:len(a)] and b[0:len(b)] overlap. -func overlaps[S ~[]E, E any](a, b S) bool { +func overlaps[E any](a, b []E) bool { if len(a) == 0 || len(b) == 0 { return false } @@ -480,7 +480,7 @@ func overlaps[S ~[]E, E any](a, b S) bool { // startIdx returns the index in haystack where the needle starts. // prerequisite: the needle must be aliased entirely inside the haystack. -func startIdx[S ~[]E, E any](haystack, needle S) int { +func startIdx[E any](haystack, needle []E) int { p := &needle[0] for i := range haystack { if p == &haystack[i] { @@ -492,7 +492,7 @@ func startIdx[S ~[]E, E any](haystack, needle S) int { } // Reverse reverses the elements of the slice in place. -func Reverse[E any](s []E) { +func Reverse[S ~[]E, E any](s S) { for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 { s[i], s[j] = s[j], s[i] } diff --git a/src/slices/slices_test.go b/src/slices/slices_test.go index 8f683a7ae6..e6da3b0e03 100644 --- a/src/slices/slices_test.go +++ b/src/slices/slices_test.go @@ -856,7 +856,7 @@ func TestReverse(t *testing.T) { t.Errorf("Reverse(singeleton) = %v, want %v", singleton, want) } - Reverse[string](nil) + Reverse[[]string](nil) } // naiveReplace is a baseline implementation to the Replace function. @@ -1053,3 +1053,23 @@ func TestReplaceGrowthRate(t *testing.T) { 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) + } +} diff --git a/src/slices/sort.go b/src/slices/sort.go index 9b83b23056..24fc6e26b6 100644 --- a/src/slices/sort.go +++ b/src/slices/sort.go @@ -11,7 +11,7 @@ import ( // Sort sorts a slice of any ordered type in ascending order. // When sorting floating-point numbers, NaNs are ordered before other values. -func Sort[E cmp.Ordered](x []E) { +func Sort[S ~[]E, E cmp.Ordered](x S) { n := len(x) pdqsortOrdered(x, 0, n, bits.Len(uint(n))) } @@ -23,19 +23,19 @@ func Sort[E cmp.Ordered](x []E) { // // SortFunc requires that cmp is a strict weak ordering. // See https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings. -func SortFunc[E any](x []E, cmp func(a, b E) int) { +func SortFunc[S ~[]E, E any](x S, cmp func(a, b E) int) { n := len(x) pdqsortCmpFunc(x, 0, n, bits.Len(uint(n)), cmp) } // SortStableFunc sorts the slice x while keeping the original order of equal // elements, using cmp to compare elements. -func SortStableFunc[E any](x []E, cmp func(a, b E) int) { +func SortStableFunc[S ~[]E, E any](x S, cmp func(a, b E) int) { stableCmpFunc(x, len(x), cmp) } // IsSorted reports whether x is sorted in ascending order. -func IsSorted[E cmp.Ordered](x []E) bool { +func IsSorted[S ~[]E, E cmp.Ordered](x S) bool { for i := len(x) - 1; i > 0; i-- { if cmp.Less(x[i], x[i-1]) { return false @@ -46,7 +46,7 @@ func IsSorted[E cmp.Ordered](x []E) bool { // IsSortedFunc reports whether x is sorted in ascending order, with cmp as the // comparison function. -func IsSortedFunc[E any](x []E, cmp func(a, b E) int) bool { +func IsSortedFunc[S ~[]E, E any](x S, cmp func(a, b E) int) bool { for i := len(x) - 1; i > 0; i-- { if cmp(x[i], x[i-1]) < 0 { return false @@ -58,7 +58,7 @@ func IsSortedFunc[E any](x []E, cmp func(a, b E) int) bool { // Min returns the minimal value in x. It panics if x is empty. // For floating-point numbers, Min propagates NaNs (any NaN value in x // forces the output to be NaN). -func Min[E cmp.Ordered](x []E) E { +func Min[S ~[]E, E cmp.Ordered](x S) E { if len(x) < 1 { panic("slices.Min: empty list") } @@ -71,7 +71,7 @@ func Min[E cmp.Ordered](x []E) E { // MinFunc returns the minimal value in x, using cmp to compare elements. // It panics if x is empty. -func MinFunc[E any](x []E, cmp func(a, b E) int) E { +func MinFunc[S ~[]E, E any](x S, cmp func(a, b E) int) E { if len(x) < 1 { panic("slices.MinFunc: empty list") } @@ -87,7 +87,7 @@ func MinFunc[E any](x []E, cmp func(a, b E) int) E { // Max returns the maximal value in x. It panics if x is empty. // For floating-point E, Max propagates NaNs (any NaN value in x // forces the output to be NaN). -func Max[E cmp.Ordered](x []E) E { +func Max[S ~[]E, E cmp.Ordered](x S) E { if len(x) < 1 { panic("slices.Max: empty list") } @@ -100,7 +100,7 @@ func Max[E cmp.Ordered](x []E) E { // MaxFunc returns the maximal value in x, using cmp to compare elements. // It panics if x is empty. -func MaxFunc[E any](x []E, cmp func(a, b E) int) E { +func MaxFunc[S ~[]E, E any](x S, cmp func(a, b E) int) E { if len(x) < 1 { panic("slices.MaxFunc: empty list") } @@ -117,7 +117,7 @@ func MaxFunc[E any](x []E, cmp func(a, b E) int) E { // where target is found, or the position where target would appear in the // sort order; it also returns a bool saying whether the target is really found // in the slice. The slice must be sorted in increasing order. -func BinarySearch[E cmp.Ordered](x []E, target E) (int, bool) { +func BinarySearch[S ~[]E, E cmp.Ordered](x S, target E) (int, bool) { // Inlining is faster than calling BinarySearchFunc with a lambda. n := len(x) // Define x[-1] < target and x[n] >= target. @@ -143,7 +143,7 @@ func BinarySearch[E cmp.Ordered](x []E, target E) (int, bool) { // or a positive number if the slice element follows the target. // cmp must implement the same ordering as the slice, such that if // cmp(a, t) < 0 and cmp(b, t) >= 0, then a must precede b in the slice. -func BinarySearchFunc[E, T any](x []E, target T, cmp func(E, T) int) (int, bool) { +func BinarySearchFunc[S ~[]E, E, T any](x S, target T, cmp func(E, T) int) (int, bool) { n := len(x) // Define cmp(x[-1], target) < 0 and cmp(x[n], target) >= 0 . // Invariant: cmp(x[i - 1], target) < 0, cmp(x[j], target) >= 0. |