slices: add Reverse

[adonovan]

During the review of the proposal for the new slices package I mentioned that Reverse, a common slice operation, seemed to be missing, and was advised to file a separate proposal. So here it is. I propose we add this function:

package slices

// 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]
       }
}

You can see the full implementation in https://go.dev/cl/468855. ;-)

[gopherbot]

Change https://go.dev/cl/468855 mentions this issue: slices: add in-place Reverse function

[hherman1]

What are the use cases for reverse? This has come up a lot in criticisms of go but I find that in my day job I rarely want for it. the only time I recall using a reverse function was for swapping sort order (which it was useful for). Wondering if there might be others I’m not thinking of.

[adonovan]

It comes up whenever a function produces a slice whose elements are in the opposite order. ;-)

I too find it's not something that comes up a lot in my own code, but that's usually because I control the producer and consumer of ordered slices and I can usually make them agree on a sensible order. But still it comes up, and it's a very clearly defined operation.

A few examples quickly found in GOROOT:

goroot$ ag '\[.*\], .*\[.*\] = .*\[.*\], .*\['  | grep -e -1-
src/cmd/compile/internal/ssa/copyelim_test.go:34:		values[i], values[len(values)-1-i] = values[len(values)-1-i], values[i]
src/cmd/vendor/golang.org/x/tools/go/ast/astutil/enclosing.go:150:			path[i], path[l-1-i] = path[l-1-i], path[i]
src/crypto/internal/nistec/fiat/p224.go:132:		v[i], v[len(v)-1-i] = v[len(v)-1-i], v[i]
src/crypto/internal/nistec/fiat/generate.go:277:		v[i], v[len(v)-1-i] = v[len(v)-1-i], v[i]
src/crypto/internal/nistec/fiat/p521.go:132:		v[i], v[len(v)-1-i] = v[len(v)-1-i], v[i]
src/crypto/internal/nistec/fiat/p384.go:132:		v[i], v[len(v)-1-i] = v[len(v)-1-i], v[i]
src/crypto/internal/nistec/fiat/p256.go:132:		v[i], v[len(v)-1-i] = v[len(v)-1-i], v[i]
src/go/constant/value.go:155:		x[i], x[n-1-i] = x[n-1-i], x[i]

and in x/tools:

xtools$ ag '\[.*\], .*\[.*\] = .*\[.*\], .*\['  | grep -e -1-
go/ast/astutil/enclosing.go:150:			path[i], path[l-1-i] = path[l-1-i], path[i]
gopls/internal/lsp/source/completion/completion.go:2280:		objs[i], objs[len(objs)-1-i] = objs[len(objs)-1-i], objs[i]
gopls/internal/lsp/source/implementation.go:478:		path[i], path[len(path)-1-i] = path[len(path)-1-i], path[i]
internal/gcimporter/iexport_test.go:404:		bytes[i], bytes[len(bytes)-1-i] = bytes[len(bytes)-1-i], bytes[i]
internal/gcimporter/bexport.go:656:		bytes[i], bytes[len(bytes)-1-i] = bytes[len(bytes)-1-i], bytes[i]
internal/fuzzy/matcher.go:181:		ret[i], ret[len(ret)-1-i] = ret[len(ret)-1-i], ret[i]

[jmwielandt]

What are the use cases for reverse? This has come up a lot in criticisms of go but I find that in my day job I rarely want for it. the only time I recall using a reverse function was for swapping sort order (which it was useful for). Wondering if there might be others I’m not thinking of.

Imagine you have a big slice, and a function that returns a slice of indexes form the big slice which have to be deleted. If you do sth like:

bigSlice := []any{...}
indexesToDelete := []int{ ... }

for _, indexToDelete := range indexesToDelete {
    bigSlice = append(bigSlice[:indexToDelete], bigSlice[indexToDelete+1:]...)
}

you will have a bug, because the following indexes are now pointing to the wrong elements. There are two easy ways to fix this:

1. have a counter of how many elements you have deleted and apply that correction
2. reverse the slice indexesToDelete.

I just have run into this reviewing a PR 😅

Proof of what I say:

[fzipp]

@jmwielandt Why would you rather move memory around with slices.Reverse instead of just counting backwards?

for i := len(indexesToDelete) - 1; i >= 0; i-- {
	indexToDelete := indexesToDelete[i]
	// ...
}

[jmwielandt]

@jmwielandt Why would you rather move memory around with slices.Reverse instead of just counting backwards?

for i := len(indexesToDelete) - 1; i >= 0; i-- {
	indexToDelete := indexesToDelete[i]
	// ...
}

That sounds like "why would you use 'range' instead of a good ol' for loop" to me.

for _, x := range adds readability. Maybe a slice.Reverse is not the best and there should be a reverse built-in function just like append that when called on a range statement do your optimization.
@fzipp

[fzipp]

@jmwielandt For iteration there are other better ideas like user-defined iteration using range over func values, so I would say that use case arguments for a memory moving slices.Reverse function should not be based on simple reverse iteration needs.

[icholy]

I have a Trie implementation where I needed a Reverse function.

// Query returns all matched values along the key path.
// The returned elements are sorted in order of proximity to the key.
// The first element in the slice is the closest value to the key.
func (t *Trie[T]) Query(key string) []Entry[T] {
	ee := []Entry[T]{}
	if t.root.hasValue {
		ee = append(ee, Entry[T]{Value: t.root.value})
	}
	n := &t.root
	for i, r := range key {
		var ok bool
		if n, ok = n.children[r]; !ok {
			break
		}
		if n.hasValue {
			ee = append(ee, Entry[T]{
				Key:   key[:i+1],
				Value: n.value,
			})
		}
	}
	common.Reverse(ee)
	return ee
}

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[rsc]

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

[amnonbc]

We should also add a double-reverse function, for those times when a single reverse just is not enough....

[adonovan]

We should also add a double-reverse function, for those times when a single reverse just is not enough....

The compiler already inserts calls to its highly optimized implementation of double-reverse in all the necessary places.

[leonklingele]

I suggest using double ROT13 for this.

[fzipp]

Closed before accepted?

[fzipp]

Oh, sorry, I now saw the comment in the CL: https://go-review.googlesource.com/c/go/+/468855/9#message-fc275fcf37f3207e30d99afe18cb2cc5c9686e28

[rsc]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group