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>

diff --git a/api/go1.21.txt b/api/go1.21.txt
index 964392e0ec1f759a31f9cc4478be93f15bb82652..6435d10914cfd9f82fb7c9e096e3415e80131d2b 100644 (file)
--- a/api/go1.21.txt
+++ b/api/go1.21.txt
@@ -365,35 +365,35 @@ pkg runtime, method (*Pinner) Pin(interface{}) #46787
 pkg runtime, method (*Pinner) Unpin() #46787
 pkg runtime, type PanicNilError struct #25448
 pkg runtime, type Pinner struct #46787
-pkg slices, func BinarySearch[$0 cmp.Ordered]([]$0, $0) (int, bool) #60091
-pkg slices, func BinarySearchFunc[$0 interface{}, $1 interface{}]([]$0, $1, func($0, $1) int) (int, bool) #60091
+pkg slices, func BinarySearch[$0 interface{ ~[]$1 }, $1 cmp.Ordered]($0, $1) (int, bool) #60091
+pkg slices, func BinarySearchFunc[$0 interface{ ~[]$1 }, $1 interface{}, $2 interface{}]($0, $2, func($1, $2) int) (int, bool) #60091
 pkg slices, func Clip[$0 interface{ ~[]$1 }, $1 interface{}]($0) $0 #57433
 pkg slices, func Clone[$0 interface{ ~[]$1 }, $1 interface{}]($0) $0 #57433
 pkg slices, func Compact[$0 interface{ ~[]$1 }, $1 comparable]($0) $0 #57433
 pkg slices, func CompactFunc[$0 interface{ ~[]$1 }, $1 interface{}]($0, func($1, $1) bool) $0 #57433
-pkg slices, func Compare[$0 cmp.Ordered]([]$0, []$0) int #60091
-pkg slices, func CompareFunc[$0 interface{}, $1 interface{}]([]$0, []$1, func($0, $1) int) int #60091
-pkg slices, func Contains[$0 comparable]([]$0, $0) bool #57433
-pkg slices, func ContainsFunc[$0 interface{}]([]$0, func($0) bool) bool #57433
+pkg slices, func Compare[$0 interface{ ~[]$1 }, $1 cmp.Ordered]($0, $0) int #60091
+pkg slices, func CompareFunc[$0 interface{ ~[]$2 }, $1 interface{ ~[]$3 }, $2 interface{}, $3 interface{}]($0, $1, func($2, $3) int) int #60091
+pkg slices, func Contains[$0 interface{ ~[]$1 }, $1 comparable]($0, $1) bool #57433
+pkg slices, func ContainsFunc[$0 interface{ ~[]$1 }, $1 interface{}]($0, func($1) bool) bool #57433
 pkg slices, func Delete[$0 interface{ ~[]$1 }, $1 interface{}]($0, int, int) $0 #57433
 pkg slices, func DeleteFunc[$0 interface{ ~[]$1 }, $1 interface{}]($0, func($1) bool) $0 #54768
-pkg slices, func Equal[$0 comparable]([]$0, []$0) bool #57433
-pkg slices, func EqualFunc[$0 interface{}, $1 interface{}]([]$0, []$1, func($0, $1) bool) bool #57433
+pkg slices, func Equal[$0 interface{ ~[]$1 }, $1 comparable]($0, $0) bool #57433
+pkg slices, func EqualFunc[$0 interface{ ~[]$2 }, $1 interface{ ~[]$3 }, $2 interface{}, $3 interface{}]($0, $1, func($2, $3) bool) bool #57433
 pkg slices, func Grow[$0 interface{ ~[]$1 }, $1 interface{}]($0, int) $0 #57433
-pkg slices, func Index[$0 comparable]([]$0, $0) int #57433
-pkg slices, func IndexFunc[$0 interface{}]([]$0, func($0) bool) int #57433
+pkg slices, func Index[$0 interface{ ~[]$1 }, $1 comparable]($0, $1) int #57433
+pkg slices, func IndexFunc[$0 interface{ ~[]$1 }, $1 interface{}]($0, func($1) bool) int #57433
 pkg slices, func Insert[$0 interface{ ~[]$1 }, $1 interface{}]($0, int, ...$1) $0 #57433
-pkg slices, func IsSorted[$0 cmp.Ordered]([]$0) bool #60091
-pkg slices, func IsSortedFunc[$0 interface{}]([]$0, func($0, $0) int) bool #60091
-pkg slices, func Max[$0 cmp.Ordered]([]$0) $0 #60091
-pkg slices, func MaxFunc[$0 interface{}]([]$0, func($0, $0) int) $0 #60091
-pkg slices, func Min[$0 cmp.Ordered]([]$0) $0 #60091
-pkg slices, func MinFunc[$0 interface{}]([]$0, func($0, $0) int) $0 #60091
+pkg slices, func IsSorted[$0 interface{ ~[]$1 }, $1 cmp.Ordered]($0) bool #60091
+pkg slices, func IsSortedFunc[$0 interface{ ~[]$1 }, $1 interface{}]($0, func($1, $1) int) bool #60091
+pkg slices, func Max[$0 interface{ ~[]$1 }, $1 cmp.Ordered]($0) $1 #60091
+pkg slices, func MaxFunc[$0 interface{ ~[]$1 }, $1 interface{}]($0, func($1, $1) int) $1 #60091
+pkg slices, func Min[$0 interface{ ~[]$1 }, $1 cmp.Ordered]($0) $1 #60091
+pkg slices, func MinFunc[$0 interface{ ~[]$1 }, $1 interface{}]($0, func($1, $1) int) $1 #60091
 pkg slices, func Replace[$0 interface{ ~[]$1 }, $1 interface{}]($0, int, int, ...$1) $0 #57433
-pkg slices, func Reverse[$0 interface{}]([]$0) #58565
-pkg slices, func Sort[$0 cmp.Ordered]([]$0) #60091
-pkg slices, func SortFunc[$0 interface{}]([]$0, func($0, $0) int) #60091
-pkg slices, func SortStableFunc[$0 interface{}]([]$0, func($0, $0) int) #60091
+pkg slices, func Reverse[$0 interface{ ~[]$1 }, $1 interface{}]($0) #58565
+pkg slices, func Sort[$0 interface{ ~[]$1 }, $1 cmp.Ordered]($0) #60091
+pkg slices, func SortFunc[$0 interface{ ~[]$1 }, $1 interface{}]($0, func($1, $1) int) #60091
+pkg slices, func SortStableFunc[$0 interface{ ~[]$1 }, $1 interface{}]($0, func($1, $1) int) #60091
 pkg strings, func ContainsFunc(string, func(int32) bool) bool #54386
 pkg sync, func OnceFunc(func()) func() #56102
 pkg sync, func OnceValue[$0 interface{}](func() $0) func() $0 #56102

diff --git a/src/slices/slices.go b/src/slices/slices.go
index be869fe480ae2cdbc7f12139b7d00b16adaa2880..c8eacae90e541107afb69ad073e404391b8b9d49 100644 (file)
--- 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 8f683a7ae662edbad6336e67fc071843fe17889b..e6da3b0e039c5d1a057ef85a99e2f362d7a2457a 100644 (file)
--- 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 9b83b2305683ef0fb766057a4a2a3fd8a6ddf96d..24fc6e26b61c18f1eb321bc21d1628cde7812e2d 100644 (file)
--- 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.