append overwrites memory in extremely non-intuitive/difficult to debug way

[fosrias]

What version of Go are you using (go version)?

go 1.11.1

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

Reproducible on go playground and on OSX

What did you do?

https://play.golang.org/p/m5q_dukI-21

What did you expect to see?

Same, correct sorted value.

What did you see instead?

Different values.

What is happening in this algorithm, is that in the incorrect sort, when it gets to sorting the last 2, it appends the 2 onto first := A[:i] ([1, 2]. When this happens, it appears to overwrite first memory address of last := A[:i] with the appended value, discarding the prior value that was desired to be maintained. Thus, instead of last being [3, 4], it is at that point [2,4], which when appended on insert result, gives the wrong answer.

The work around is to copy the slices first. Then all works fine.

This just feels wrong that append works this way and may be a bug. At the very least, it seems some documentation on this is warranted to highlight this non-intuitive behavior that appending to a partial slice can overwrite the original slice's memory allocation.

[fosrias]

Created simpler script to highlight issue:

https://play.golang.org/p/1BRWOxmXaoU

[randall77]

This is working as intended. Slices of an array share the same backing store, and that backing store is used for append while there is space.

You might want to read https://blog.golang.org/go-slices-usage-and-internals

You can use the 3-arg form of slicing to restrict the capacity, so append will always allocate a new backing store.

[ALTree]

Regarding documentation: this is a fairly direct consequence of the fact that a slice is just a view into an array. This is explained in the go tour (which is probably the main entry point to the language for beginners, and the most basic piece of documentation we have):

An array has a fixed size. A slice, on the other hand, is a dynamically-sized, flexible view into the elements of an array.

A slice does not store any data, it just describes a section of an underlying array.
Changing the elements of a slice modifies the corresponding elements of its underlying array.
Other slices that share the same underlying array will see those changes.

(https://tour.golang.org/moretypes/7 and the following page).

[fosrias]

@ALTree The documentation there is clear in the context of a slice and changing an element of the slice mutating the original array. I think the addition of append and the wording on available capacity and allocating a new array is a little unclear. Basically, with append, depending on the nature of the slice, you will get two different results. In any case, made another mental note about unexpected mutation possibilities in go.

Thx.