Go Slice with Cap

Go Slice with Cap

Russ Cox

June 2013

Abstract

I propose to add to Go 1.2 a variant of the slice operation that allows reducing the capacity of a slice.

Fixes issue 1642. Discussion on the mailing list.

Background

It would occasionally be useful, for example in custom []byte allocation managers, to be able to hand a slice to a caller and know that the caller cannot edit values beyond a given subrange of the true array.

The addition of append to the language made this somewhat more important, because append lets programmers overwrite entries between len and cap without realizing it or even mentioning cap.

Issue 1642 was filed for this by Roger Peppe after this discussion in 2011.

The need does not come up often, but it does come up occasionally. The most important argument in favor is that giving programmers a way to control cap gives them more control over append.

Proposed Definition

For an array, pointer to array, or slice a, the primary expression

a[i : j : k]

constructs a slice. The result has indices starting at 0, length equal to j - i, and capacity equal to k - i. The evaluation panics if i ≤ j ≤ k ≤ cap(a) is not true.

For convenience, the index i may be omitted: it defaults to zero. The other indices j and k are required. Once we have sufficient experience using this form we might choose appropriate defaults for them.

(This definition is in addition to, not a replacement for, the current two-index slice syntax.)

Implications

As mentioned above, the most important implication is that control over cap gives programmers control over append, especially when handing a slice to code in another package.

A second implication is to remove the ability to test for aliasing of slices without the unsafe package. Specifically, it has been observed that the current implementation, in which capacity can never shrink, allows checking for aliasing of two slices x and y by testing the address of the final element: &x[:cap(x)][cap(x)-1] == &y[:cap(y)][cap(y)-1]. Being able to control the capacity breaks this test. However, in practice I do not believe this test is widely used.

The most important use for determining overlap is to decide how to run a copy, and the builtin function now handles that. The only code I can find anywhere (including public Go code) containing such a test is math/big’s func alias. Since math/big already uses assembly, it would be reasonable for it to use unsafe to do a real pointer comparison instead.

Also, math/big only uses this test on its own slices, which are not exposed directly to client code. So since math/big does not reduce the capacity of those slices, nothing does, so the test can stay as is.

This test does not exactly roll off the tongue. I have vague memories of using the idiom when writing go/build or cmd/go, but the test was later removed entirely by someone else, in part because I had gotten the implementation wrong anyway.

I don’t see a compelling argument that overlap testing is important enough to warrant language support beyond package unsafe. If that argument is made, we could consider it then.

Implementation

The implementation of the language operation is trivial.

The new language operation would need to be made available in package reflect as well. reflect.Value defines:

func (v Value) SetLen(len int)

func (v Value) Slice(low, high int) Value

The API would probably be extended to define:

func (v Value) SetCap(cap int)

func (v Value) Slice3(low, high, max int) Value

When defaults are decided, we can use gofmt -r to simplify existing expressions.

Defaults for j and k

There are a number of sensible possibilities for what the defaults for j and k should be. They are recorded here for discussion later, after we have real use cases against which we can evaluate them. We are not interested in discussing these now.

The examples assume x = make([]int, 10, 20).

The comparison ≡ means the slices have the same base, len, and cap.

Case 1: j defaults to len(x), k defaults to cap(x).

x[i::] ≡ x[i:]

x[i:j:] ≡ x[i:j]

x[::] ≡ x

x[::n] depends on n vs len

x[::15] ≡ x[0:10:15]

x[::5] panics (implicit j = 10 > k = 5)

x[0:15:] ≡ x[0:15]

Case 2: j defaults to k, k defaults to cap(x)

x[i::] ≡ x[i:20]

x[i:j:] ≡ x[i:j]

x[::] ≡ x[:20] // an idiom for growing a slice?

x[::n] ≡ x[0:n:n]

x[::15] ≡ x[0:15:15]

x[::5] ≡ x[0:5:5]

x[0:15:] ≡ x[0:15]

Case 3: j defaults to min(len(x), k), k defaults to cap(x)

x[i::] ≡ x[i:]

x[i:j:] ≡ x[i:j]

x[::] ≡ x

x[::n] depends on n vs len

x[::15] = x[0:10:15] // len stayed where it was

x[::5] ≡ x[0:5:5] // len pulled down by new cap

x[0:15:] ≡ x[0:15]

Case 4: j defaults to len(x), k defaults to len(x)

x[i::] ≡ x[i:10:10], NOT same as x[i:]

x[i:j:] ≡ x[i:j:10], NOT same as x[i:j]

x[::] ≡ x[0:10:10] // an idiom for shrinking a slice?

x[::15] ≡ x[0:10:15]

x[::5] panics (implicit j = 10 > k = 5)

x[0:15:] panics (j = 15 > implicit k = 10), NOT same as x[0:15]

Case 5: j defaults to k, k defaults to len(x).

x[i::] ≡ x[i:10:10], NOT same as x[i:]

x[i:j:] ≡ x[i:j:10], NOT same as x[i:j]

x[::] ≡ x[:10:10] // an idiom for shrinking a slice?

x[::15] ≡ x[0:15:15] // slice cap shrank, len grew

x[::5] ≡ x[0:5:5]

x[0:15:] panics (j = 15 > implicit k = 10)

Case 6: j defaults to min(len(x), k), k defaults to len(x).

x[i::] ≡ x[i:10:10], NOT same as x[i:]

x[i:j:] ≡ x[i:j:10], NOT same as x[i:j]

x[::] ≡ x[:10:10] // an idiom for shrinking a slice?

x[::15] ≡ x[0:10:15] // len stayed where it was

x[::5] ≡ x[0:5:5] // len pulled down by new cap

x[0:15:] panics (j = 15 > implicit k = 10)