slices: new package

This copies parts of x/exp/slices into the standard library.
We omit all functions that depend on constraints.Ordered,
and the Func variants of all such functions. In particular this
omits the various Sort and Search functions.

Fixes #57433

Change-Id: I3c28f4c2e6bd1e3c9ad70e120a0dd68065388f77
Reviewed-on: https://go-review.googlesource.com/c/go/+/467417
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Eli Bendersky <eliben@google.com>
Run-TryBot: Ian Lance Taylor <iant@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Auto-Submit: Ian Lance Taylor <iant@google.com>

2 files changed, 800 insertions, 0 deletions

diff --git a/src/slices/slices.go b/src/slices/slices.go
new file mode 100644
index 0000000000..1a837c53c1
--- /dev/null
+++ b/src/slices/slices.go
@@ -0,0 +1,196 @@
+// 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 defines various functions useful with slices of any type.
+package slices
+
+// 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 {
+	if len(s1) != len(s2) {
+		return false
+	}
+	for i := range s1 {
+		if s1[i] != s2[i] {
+			return false
+		}
+	}
+	return true
+}
+
+// EqualFunc reports whether two slices are equal using a comparison
+// 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 {
+	if len(s1) != len(s2) {
+		return false
+	}
+	for i, v1 := range s1 {
+		v2 := s2[i]
+		if !eq(v1, v2) {
+			return false
+		}
+	}
+	return true
+}
+
+// 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 {
+	for i, vs := range s {
+		if v == vs {
+			return i
+		}
+	}
+	return -1
+}
+
+// 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 {
+	for i, v := range s {
+		if f(v) {
+			return i
+		}
+	}
+	return -1
+}
+
+// Contains reports whether v is present in s.
+func Contains[E comparable](s []E, 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 {
+	return IndexFunc(s, f) >= 0
+}
+
+// Insert inserts the values v... into s at index i,
+// returning the modified slice.
+// 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:])
+		copy(s2[i:], v)
+		return s2
+	}
+	s2 := make(S, tot)
+	copy(s2, s[:i])
+	copy(s2[i:], v)
+	copy(s2[i+len(v):], s[i:])
+	return s2
+}
+
+// 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
+// elements contain pointers you might consider zeroing those elements so that
+// objects they reference can be garbage collected.
+func Delete[S ~[]E, E any](s S, i, j int) S {
+	_ = s[i:j] // bounds check
+
+	return append(s[:i], s[j:]...)
+}
+
+// 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
+	tot := len(s[:i]) + len(v) + len(s[j:])
+	if tot <= cap(s) {
+		s2 := s[:tot]
+		copy(s2[i+len(v):], s[j:])
+		copy(s2[i:], v)
+		return s2
+	}
+	s2 := make(S, tot)
+	copy(s2, s[:i])
+	copy(s2[i:], v)
+	copy(s2[i+len(v):], s[j:])
+	return s2
+}
+
+// Clone returns a copy of the slice.
+// The elements are copied using assignment, so this is a shallow clone.
+func Clone[S ~[]E, E any](s S) S {
+	// Preserve nil in case it matters.
+	if s == nil {
+		return nil
+	}
+	return append(S([]E{}), 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.
+// 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.
+func Compact[S ~[]E, E comparable](s S) S {
+	if len(s) < 2 {
+		return s
+	}
+	i := 1
+	last := s[0]
+	for _, v := range s[1:] {
+		if v != last {
+			s[i] = v
+			i++
+			last = v
+		}
+	}
+	return s[:i]
+}
+
+// CompactFunc is like Compact but uses a comparison function.
+func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S {
+	if len(s) < 2 {
+		return s
+	}
+	i := 1
+	last := s[0]
+	for _, v := range s[1:] {
+		if !eq(v, last) {
+			s[i] = v
+			i++
+			last = v
+		}
+	}
+	return s[:i]
+}
+
+// Grow increases the slice's capacity, if necessary, to guarantee space for
+// another n elements. After Grow(n), at least n elements can be appended
+// to the slice without another allocation. If n is negative or too large to
+// allocate the memory, Grow panics.
+func Grow[S ~[]E, E any](s S, n int) S {
+	if n < 0 {
+		panic("cannot be negative")
+	}
+	if n -= cap(s) - len(s); n > 0 {
+		s = append(s[:cap(s)], make([]E, n)...)[:len(s)]
+	}
+	return s
+}
+
+// Clip removes unused capacity from the slice, returning s[:len(s):len(s)].
+func Clip[S ~[]E, E any](s S) S {
+	return s[:len(s):len(s)]
+}
diff --git a/src/slices/slices_test.go b/src/slices/slices_test.go
new file mode 100644
index 0000000000..97030bebbb
--- /dev/null
+++ b/src/slices/slices_test.go
@@ -0,0 +1,604 @@
+// 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
+
+import (
+	"internal/race"
+	"math"
+	"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)
+	}
+}
+
+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 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 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)
+		}
+	}
+}
+
+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)
+		}
+	}
+}
+
+func panics(f func()) (b bool) {
+	defer func() {
+		if x := recover(); x != nil {
+			b = true
+		}
+	}()
+	f()
+	return false
+}
+
+func TestDeletePanics(t *testing.T) {
+	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 invalid i>j", []int{42}, 1, 0},
+	} {
+		if !panics(func() { Delete(test.s, test.i, test.j) }) {
+			t.Errorf("Delete %s: got no panic, want panic", test.name)
+		}
+	}
+}
+
+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 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 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 {
+			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))
+	}
+}
+
+// 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) {
+	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},
+	} {
+		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 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...)
+			}
+		})
+	}
+
+}