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.

Sign up for GitHub

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

Jump to bottom

slices: Incorrect implementation of slices.Insert and slices.Replace #60138

Closed
merykitty opened this issue May 12, 2023 · 2 comments
Closed

slices: Incorrect implementation of slices.Insert and slices.Replace #60138

merykitty opened this issue May 12, 2023 · 2 comments
Assignees
@cuonglm
Labels
NeedsFix The path to resolution is known, but the work has not been done. release-blocker
Milestone
Go1.21

Comments

@merykitty
Copy link

What did you do?

Crafted an example such that the memory referenced by the result overlaps with the insert-from slice, playground

a := []int{1, 2, 3, 4, 5, 6, 7, 8}
b := a[:4]         // 1, 2, 3, 4
c := a[4:6]        // 5, 6
res := slices.Insert(b, 2, c...)
fmt.Println(res)

What did you expect to see?

[1 2 5 6 3 4]

What did you see instead?

[1 2 3 4 3 4]

Note: This is because the implementation of slices.Insert slides the upper range of the first operand forward before copying the content of the third operand into the freed space. This risks overwrite the content in that operand. I believe slices.Replace suffers the same issue, too.

A conservative solution is to create a temporary buffer to copy the content of the second slice into before sliding the first one, while a more aggressive one would be to do pointer arithmetic to check the aliasness.
@cuonglm cuonglm added the NeedsFix The path to resolution is known, but the work has not been done. label May 12, 2023
@cuonglm cuonglm added this to the Go1.21 milestone May 12, 2023
@cuonglm cuonglm self-assigned this May 12, 2023
@gopherbot
Copy link

Change https://go.dev/cl/494536 mentions this issue: slices: do not re-use underlying array if two slices are overlapped

@gopherbot
Copy link

Change https://go.dev/cl/494817 mentions this issue: slices: handle aliasing cases in Insert/Replace

@randall77 randall77 mentioned this issue May 16, 2023
Open
@randall77 randall77 mentioned this issue May 17, 2023
Closed
eric pushed a commit to fancybits/go that referenced this issue Sep 7, 2023
@randall77 @eric
slices: handle aliasing cases in Insert/Replace
35efa77 
Handle cases where the inserted slice is actually part of the slice
that is being inserted into.

Requires a bit more work, but no more allocations. (Compare to #494536.)

Not entirely sure this is worth the complication.

Fixes golang#60138

Change-Id: Ia72c872b04309b99025e6ca5a4a326ebed2abb69
Reviewed-on: https://go-review.googlesource.com/c/go/+/494817
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Keith Randall <khr@google.com>
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: Bryan Mills <bcmills@google.com>
eric pushed a commit to fancybits/go that referenced this issue Sep 7, 2023
@randall77 @eric
slices: handle aliasing cases in Insert/Replace
0b27596 
Handle cases where the inserted slice is actually part of the slice
that is being inserted into.

Requires a bit more work, but no more allocations. (Compare to #494536.)

Not entirely sure this is worth the complication.

Fixes golang#60138

Change-Id: Ia72c872b04309b99025e6ca5a4a326ebed2abb69
Reviewed-on: https://go-review.googlesource.com/c/go/+/494817
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Keith Randall <khr@google.com>
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: Bryan Mills <bcmills@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@cuonglm cuonglm

Labels
NeedsFix The path to resolution is known, but the work has not been done. release-blocker
Projects
None yet
Milestone
Go1.21
Development

No branches or pull requests
4 participants
@cuonglm @bcmills @gopherbot @merykitty