1 files changed, 297 insertions, 56 deletions

diff --git a/vendor/golang.org/x/exp/slices/slices.go b/vendor/golang.org/x/exp/slices/slices.go
index 2540bd682..5e8158bba 100644
--- a/vendor/golang.org/x/exp/slices/slices.go
+++ b/vendor/golang.org/x/exp/slices/slices.go
@@ -3,23 +3,20 @@
 // license that can be found in the LICENSE file.
 
 // Package slices defines various functions useful with slices of any type.
-// Unless otherwise specified, these functions all apply to the elements
-// of a slice at index 0 <= i < len(s).
-//
-// Note that the less function in IsSortedFunc, SortFunc, SortStableFunc requires a
-// strict weak ordering (https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings),
-// or the sorting may fail to sort correctly. A common case is when sorting slices of
-// floating-point numbers containing NaN values.
 package slices
 
-import "golang.org/x/exp/constraints"
+import (
+	"unsafe"
+
+	"golang.org/x/exp/constraints"
+)
 
 // Equal reports whether two slices are equal: the same length and all
 // elements equal. If the lengths are different, Equal returns false.
 // 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
 	}
@@ -31,12 +28,12 @@ func Equal[E comparable](s1, s2 []E) bool {
 	return true
 }
 
-// EqualFunc reports whether two slices are equal using a comparison
+// EqualFunc reports whether two slices are equal using an equality
 // function on each pair of elements. If the lengths are different,
 // 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
 	}
@@ -49,45 +46,37 @@ func EqualFunc[E1, E2 any](s1 []E1, s2 []E2, eq func(E1, E2) bool) bool {
 	return true
 }
 
-// Compare compares the elements of s1 and s2.
-// The elements are compared sequentially, starting at index 0,
+// Compare compares the elements of s1 and s2, using [cmp.Compare] on each pair
+// of elements. The elements are compared sequentially, starting at index 0,
 // until one element is not equal to the other.
 // The result of comparing the first non-matching elements is returned.
 // 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.
-// Comparisons involving floating point NaNs are ignored.
-func Compare[E constraints.Ordered](s1, s2 []E) int {
-	s2len := len(s2)
+func Compare[S ~[]E, E constraints.Ordered](s1, s2 S) int {
 	for i, v1 := range s1 {
-		if i >= s2len {
+		if i >= len(s2) {
 			return +1
 		}
 		v2 := s2[i]
-		switch {
-		case v1 < v2:
-			return -1
-		case v1 > v2:
-			return +1
+		if c := cmpCompare(v1, v2); c != 0 {
+			return c
 		}
 	}
-	if len(s1) < s2len {
+	if len(s1) < len(s2) {
 		return -1
 	}
 	return 0
 }
 
-// CompareFunc is like Compare but uses a comparison function
-// on each pair of elements. The elements are compared in increasing
-// index order, and the comparisons stop after the first time cmp
-// returns non-zero.
+// CompareFunc is like [Compare] but uses a custom comparison function on each
+// pair of elements.
 // 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 {
-	s2len := len(s2)
+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 >= s2len {
+		if i >= len(s2) {
 			return +1
 		}
 		v2 := s2[i]
@@ -95,7 +84,7 @@ func CompareFunc[E1, E2 any](s1 []E1, s2 []E2, cmp func(E1, E2) int) int {
 			return c
 		}
 	}
-	if len(s1) < s2len {
+	if len(s1) < len(s2) {
 		return -1
 	}
 	return 0
@@ -103,7 +92,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
@@ -114,7 +103,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
@@ -124,39 +113,104 @@ 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
 }
 
 // Insert inserts the values v... into s at index i,
 // returning the modified slice.
-// In the returned slice r, r[i] == v[0].
+// The elements at s[i:] are shifted up to make room.
+// In the returned slice r, r[i] == v[0],
+// and r[i+len(v)] == value originally at r[i].
 // Insert panics if i is out of range.
 // This function is O(len(s) + len(v)).
 func Insert[S ~[]E, E any](s S, i int, v ...E) S {
-	tot := len(s) + len(v)
-	if tot <= cap(s) {
-		s2 := s[:tot]
-		copy(s2[i+len(v):], s[i:])
+	m := len(v)
+	if m == 0 {
+		return s
+	}
+	n := len(s)
+	if i == n {
+		return append(s, v...)
+	}
+	if n+m > cap(s) {
+		// Use append rather than make so that we bump the size of
+		// the slice up to the next storage class.
+		// This is what Grow does but we don't call Grow because
+		// that might copy the values twice.
+		s2 := append(s[:i], make(S, n+m-i)...)
 		copy(s2[i:], v)
+		copy(s2[i+m:], s[i:])
 		return s2
 	}
-	s2 := make(S, tot)
-	copy(s2, s[:i])
-	copy(s2[i:], v)
-	copy(s2[i+len(v):], s[i:])
-	return s2
+	s = s[:n+m]
+
+	// before:
+	// s: aaaaaaaabbbbccccccccdddd
+	//            ^   ^       ^   ^
+	//            i  i+m      n  n+m
+	// after:
+	// s: aaaaaaaavvvvbbbbcccccccc
+	//            ^   ^       ^   ^
+	//            i  i+m      n  n+m
+	//
+	// a are the values that don't move in s.
+	// v are the values copied in from v.
+	// b and c are the values from s that are shifted up in index.
+	// d are the values that get overwritten, never to be seen again.
+
+	if !overlaps(v, s[i+m:]) {
+		// Easy case - v does not overlap either the c or d regions.
+		// (It might be in some of a or b, or elsewhere entirely.)
+		// The data we copy up doesn't write to v at all, so just do it.
+
+		copy(s[i+m:], s[i:])
+
+		// Now we have
+		// s: aaaaaaaabbbbbbbbcccccccc
+		//            ^   ^       ^   ^
+		//            i  i+m      n  n+m
+		// Note the b values are duplicated.
+
+		copy(s[i:], v)
+
+		// Now we have
+		// s: aaaaaaaavvvvbbbbcccccccc
+		//            ^   ^       ^   ^
+		//            i  i+m      n  n+m
+		// That's the result we want.
+		return s
+	}
+
+	// The hard case - v overlaps c or d. We can't just shift up
+	// the data because we'd move or clobber the values we're trying
+	// to insert.
+	// So instead, write v on top of d, then rotate.
+	copy(s[n:], v)
+
+	// Now we have
+	// s: aaaaaaaabbbbccccccccvvvv
+	//            ^   ^       ^   ^
+	//            i  i+m      n  n+m
+
+	rotateRight(s[i:], m)
+
+	// Now we have
+	// s: aaaaaaaavvvvbbbbcccccccc
+	//            ^   ^       ^   ^
+	//            i  i+m      n  n+m
+	// That's the result we want.
+	return s
 }
 
 // Delete removes the elements s[i:j] from s, returning the modified slice.
 // Delete panics if s[i:j] is not a valid slice of s.
-// Delete modifies the contents of the slice s; it does not create a new slice.
 // Delete is O(len(s)-j), so if many items must be deleted, it is better to
 // make a single call deleting them all together than to delete one at a time.
 // Delete might not modify the elements s[len(s)-(j-i):len(s)]. If those
@@ -168,22 +222,113 @@ func Delete[S ~[]E, E any](s S, i, j int) S {
 	return append(s[:i], s[j:]...)
 }
 
+// DeleteFunc removes any elements from s for which del returns true,
+// returning the modified slice.
+// When DeleteFunc removes m elements, it might not modify the elements
+// s[len(s)-m:len(s)]. If those elements contain pointers you might consider
+// zeroing those elements so that objects they reference can be garbage
+// collected.
+func DeleteFunc[S ~[]E, E any](s S, del func(E) bool) S {
+	i := IndexFunc(s, del)
+	if i == -1 {
+		return s
+	}
+	// Don't start copying elements until we find one to delete.
+	for j := i + 1; j < len(s); j++ {
+		if v := s[j]; !del(v) {
+			s[i] = v
+			i++
+		}
+	}
+	return s[:i]
+}
+
 // Replace replaces the elements s[i:j] by the given v, and returns the
 // modified slice. Replace panics if s[i:j] is not a valid slice of s.
 func Replace[S ~[]E, E any](s S, i, j int, v ...E) S {
 	_ = s[i:j] // verify that i:j is a valid subslice
+
+	if i == j {
+		return Insert(s, i, v...)
+	}
+	if j == len(s) {
+		return append(s[:i], v...)
+	}
+
 	tot := len(s[:i]) + len(v) + len(s[j:])
-	if tot <= cap(s) {
-		s2 := s[:tot]
-		copy(s2[i+len(v):], s[j:])
+	if tot > cap(s) {
+		// Too big to fit, allocate and copy over.
+		s2 := append(s[:i], make(S, tot-i)...) // See Insert
 		copy(s2[i:], v)
+		copy(s2[i+len(v):], s[j:])
 		return s2
 	}
-	s2 := make(S, tot)
-	copy(s2, s[:i])
-	copy(s2[i:], v)
-	copy(s2[i+len(v):], s[j:])
-	return s2
+
+	r := s[:tot]
+
+	if i+len(v) <= j {
+		// Easy, as v fits in the deleted portion.
+		copy(r[i:], v)
+		if i+len(v) != j {
+			copy(r[i+len(v):], s[j:])
+		}
+		return r
+	}
+
+	// We are expanding (v is bigger than j-i).
+	// The situation is something like this:
+	// (example has i=4,j=8,len(s)=16,len(v)=6)
+	// s: aaaaxxxxbbbbbbbbyy
+	//        ^   ^       ^ ^
+	//        i   j  len(s) tot
+	// a: prefix of s
+	// x: deleted range
+	// b: more of s
+	// y: area to expand into
+
+	if !overlaps(r[i+len(v):], v) {
+		// Easy, as v is not clobbered by the first copy.
+		copy(r[i+len(v):], s[j:])
+		copy(r[i:], v)
+		return r
+	}
+
+	// This is a situation where we don't have a single place to which
+	// we can copy v. Parts of it need to go to two different places.
+	// We want to copy the prefix of v into y and the suffix into x, then
+	// rotate |y| spots to the right.
+	//
+	//        v[2:]      v[:2]
+	//         |           |
+	// s: aaaavvvvbbbbbbbbvv
+	//        ^   ^       ^ ^
+	//        i   j  len(s) tot
+	//
+	// If either of those two destinations don't alias v, then we're good.
+	y := len(v) - (j - i) // length of y portion
+
+	if !overlaps(r[i:j], v) {
+		copy(r[i:j], v[y:])
+		copy(r[len(s):], v[:y])
+		rotateRight(r[i:], y)
+		return r
+	}
+	if !overlaps(r[len(s):], v) {
+		copy(r[len(s):], v[:y])
+		copy(r[i:j], v[y:])
+		rotateRight(r[i:], y)
+		return r
+	}
+
+	// Now we know that v overlaps both x and y.
+	// That means that the entirety of b is *inside* v.
+	// So we don't need to preserve b at all; instead we
+	// can copy v first, then copy the b part of v out of
+	// v to the right destination.
+	k := startIdx(v, s[j:])
+	copy(r[i:], v)
+	copy(r[i+len(v):], r[i+k:])
+	return r
 }
 
 // Clone returns a copy of the slice.
@@ -198,7 +343,8 @@ func Clone[S ~[]E, E any](s S) S {
 
 // Compact replaces consecutive runs of equal elements with a single copy.
 // This is like the uniq command found on Unix.
-// Compact modifies the contents of the slice s; it does not create a new slice.
+// Compact modifies the contents of the slice s and returns the modified slice,
+// which may have a smaller length.
 // When Compact discards m elements in total, it might not modify the elements
 // s[len(s)-m:len(s)]. If those elements contain pointers you might consider
 // zeroing those elements so that objects they reference can be garbage collected.
@@ -218,7 +364,8 @@ func Compact[S ~[]E, E comparable](s S) S {
 	return s[:i]
 }
 
-// CompactFunc is like Compact but uses a comparison function.
+// CompactFunc is like [Compact] but uses an equality function to compare elements.
+// For runs of elements that compare equal, CompactFunc keeps the first one.
 func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S {
 	if len(s) < 2 {
 		return s
@@ -256,3 +403,97 @@ func Grow[S ~[]E, E any](s S, n int) S {
 func Clip[S ~[]E, E any](s S) S {
 	return s[:len(s):len(s)]
 }
+
+// Rotation algorithm explanation:
+//
+// rotate left by 2
+// start with
+//   0123456789
+// split up like this
+//   01 234567 89
+// swap first 2 and last 2
+//   89 234567 01
+// join first parts
+//   89234567 01
+// recursively rotate first left part by 2
+//   23456789 01
+// join at the end
+//   2345678901
+//
+// rotate left by 8
+// start with
+//   0123456789
+// split up like this
+//   01 234567 89
+// swap first 2 and last 2
+//   89 234567 01
+// join last parts
+//   89 23456701
+// recursively rotate second part left by 6
+//   89 01234567
+// join at the end
+//   8901234567
+
+// TODO: There are other rotate algorithms.
+// This algorithm has the desirable property that it moves each element exactly twice.
+// The triple-reverse algorithm is simpler and more cache friendly, but takes more writes.
+// The follow-cycles algorithm can be 1-write but it is not very cache friendly.
+
+// rotateLeft rotates b left by n spaces.
+// s_final[i] = s_orig[i+r], wrapping around.
+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:])
+			s = s[:len(s)-r]
+		} else {
+			swap(s[:len(s)-r], s[r:])
+			s, r = s[len(s)-r:], r*2-len(s)
+		}
+	}
+}
+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[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[E any](a, b []E) bool {
+	if len(a) == 0 || len(b) == 0 {
+		return false
+	}
+	elemSize := unsafe.Sizeof(a[0])
+	if elemSize == 0 {
+		return false
+	}
+	// TODO: use a runtime/unsafe facility once one becomes available. See issue 12445.
+	// Also see crypto/internal/alias/alias.go:AnyOverlap
+	return uintptr(unsafe.Pointer(&a[0])) <= uintptr(unsafe.Pointer(&b[len(b)-1]))+(elemSize-1) &&
+		uintptr(unsafe.Pointer(&b[0])) <= uintptr(unsafe.Pointer(&a[len(a)-1]))+(elemSize-1)
+}
+
+// startIdx returns the index in haystack where the needle starts.
+// prerequisite: the needle must be aliased entirely inside the haystack.
+func startIdx[E any](haystack, needle []E) int {
+	p := &needle[0]
+	for i := range haystack {
+		if p == &haystack[i] {
+			return i
+		}
+	}
+	// TODO: what if the overlap is by a non-integral number of Es?
+	panic("needle not found")
+}
+
+// Reverse reverses the elements of the slice in place.
+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]
+	}
+}