Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

slices: add Reverse #58565

Closed
adonovan opened this issue Feb 16, 2023 · 16 comments
Closed

slices: add Reverse #58565

adonovan opened this issue Feb 16, 2023 · 16 comments

Comments

@adonovan
Copy link
Member

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 gopherbot added this to the Proposal milestone Feb 16, 2023
@gopherbot
Copy link

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

@hherman1
Copy link

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
Copy link
Member Author

adonovan commented Feb 22, 2023

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
Copy link

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:

imagen

@fzipp
Copy link
Contributor

fzipp commented Mar 8, 2023

@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
Copy link

@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
Copy link
Contributor

fzipp commented Mar 9, 2023

@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
Copy link

icholy commented Apr 20, 2023

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
Copy link
Contributor

rsc commented May 10, 2023

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 rsc changed the title proposal: a slices.Reverse function proposal: slices: add Reverse May 10, 2023
@rsc
Copy link
Contributor

rsc commented May 17, 2023

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

@amnonbc
Copy link

amnonbc commented May 18, 2023

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

@adonovan
Copy link
Member Author

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
Copy link
Contributor

leonklingele commented May 18, 2023 via email

@fzipp
Copy link
Contributor

fzipp commented May 19, 2023

Closed before accepted?

@fzipp
Copy link
Contributor

fzipp commented May 19, 2023

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

@rsc
Copy link
Contributor

rsc commented May 24, 2023

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

@rsc rsc changed the title proposal: slices: add Reverse slices: add Reverse May 24, 2023
@rsc rsc modified the milestones: Proposal, Backlog May 24, 2023
@dmitshur dmitshur modified the milestones: Backlog, Go1.21 Jun 4, 2023
eric pushed a commit to fancybits/go that referenced this issue Sep 7, 2023
Fixes golang#58565

Change-Id: I583f8380c12386178fb18e553322bbb019d9fae0
Reviewed-on: https://go-review.googlesource.com/c/go/+/468855
Run-TryBot: Alan Donovan <adonovan@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Shay Nehmad <dude500@gmail.com>
eric pushed a commit to fancybits/go that referenced this issue Sep 7, 2023
Fixes golang#58565

Change-Id: I583f8380c12386178fb18e553322bbb019d9fae0
Reviewed-on: https://go-review.googlesource.com/c/go/+/468855
Run-TryBot: Alan Donovan <adonovan@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Shay Nehmad <dude500@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Status: Accepted
Development

No branches or pull requests

10 participants