Proposal: Permit signed integer values as shift count (language change)

Author: Robert Griesemer

Last updated: 2/15/2017

Abstract

We propose to change the language spec such that the shift count (the rhs operand in a << or >> operation) may be a signed or unsigned (non-constant) integer, or any non-negative constant value that can be represented as an integer.

Background

See Rationale section below.

Proposal

We change the language spec regarding shift operations as follows: In the section on Operators, the text:

The right operand in a shift expression must have unsigned integer type or be an untyped constant that can be converted to unsigned integer type.

to

The right operand in a shift expression must have integer type or be an untyped constant that can be converted to an integer type. If the right operand is constant, it must not be negative.

Furthermore, in the section on Integer operators, we change the text:

The shift operators shift the left operand by the shift count specified by the right operand.

to

The shift operators shift the left operand by the shift count specified by the right operand. A run-time panic occurs if a non-constant shift count is negative.

Rationale

Since Go's inception, shift counts had to be of unsigned integer type (or a non-negative constant representable as an unsigned integer). The idea behind this rule was that a) the spec didn't have to explain what happened for negative values, and b) the implementation didn't have to deal with negative values possibly occurring at run-time.

In retrospect, this may have been a mistake; a sentiment most recently expressed by @rsc here. It turns out that we could actually change the spec in a backward-compatible way in this regard, and this proposal is suggesting that we do that.

There are other language features where the result (len(x)), argument (n in make([]T, n)) or constant (n in [n]T) are known to be never negative or must not be negative, yet we return an int (for len, cap) or permit any integer type. Requiring an unsigned integer type for shift counts is frequently a non-issue because the shift count is constant (see below); but in some cases explicit uint conversions are needed, or the code around the shift is carefully crafted to use unsigned integers. In either case, readability is (slightly) infringed, and more decision making is required when crafting the code (should we use a conversion or type other variables as unsigned integers). Finally, and perhaps most importantly, there may be cases where we simply convert an integer to an unsigned integer and in the process inadvertently make an (invalid) negative value positive in the process, possibly hiding a bug that way (resulting in a shift by a very large number leading to 0).

If we permit any integer type, the existing code will continue to work. Places where we currently use a uint conversion won't need it anymore, and code that is crafted such that we have an unsigned shift count may not require unsigned integers elsewhere.

An investigation of shifts in the current std library and tests (excluding package-external tests) as of 2/15/2017 (this includes the proposed math/bits package) shows that we have:

• 8081 shifts; or 5457 (68%) right shifts vs 2624 (32%) left shifts
• 6151 (76%) of those are shifts by a (typed or untyped) constant
• 1666 (21%) shifts are in tests (_test.go files)
• 253 (3.1%) shifts use an explicit uint conversion for the shift count

If we only look at shifts outside of test files we have:

• 6415 shifts; or 4548 (71%) right shifts vs 1867 (29%) left shifts
• 5759 (90%) of those are shifts by a (typed or untyped) constant
• 243 (3.8%) shifts use an explicit uint conversion for the shift count

The overwhelming majority (90%) of shifts outside of testing code is by constant values, and none of those turns out to require a conversion. This proposal won't affect that code.

From the remaining 10% of all shifts, 38% (i.e., 3.8% of all shifts) require a uint conversion. That's a significant number. In the remaining 62% of non-constant shifts, the shift count expression must be using a variable that's of unsigned integer type, and often a conversion is required there. A typical example is (archive/tar/strconv.go:77):

func fitsInBase256(n int, x int64) bool {
	var binBits = uint(n-1) * 8    // <<<< uint cast
	return n >= 9 || (x >= -1<<binBits && x < 1<<binBits)
}

In this case, n is an incoming argument and we can't be sure that n > 1 without further analysis of the callers, and thus there's a possibility that n - 1 is negative. The uint conversions hides that error silently.

Another one is (cmd/compile/internal/gc/esc.go:1417):

	shift := uint(bitsPerOutputInTag*(vargen-1) + EscReturnBits)    // <<<< uint cast
	old := (e >> shift) & bitsMaskForTag

Or this one (/Users/gri/go/src/fmt/scan.go:613):

	n := uint(bitSize)    // uint cast
	x := (r << (64 - n)) >> (64 - n)

Many (most?) of the non-constant shifts that don't use an explicit uint conversion in the shift expression itself appear to have a uint conversion before that expression. Most (all?) of these conversions wouldn't be necessary anymore.

The drawback of permitting signed integers where negative values are not permitted is that we need to check for them (negative values) at run-time and (most probably) panic, as we do elsewhere (e.g., for make). This requires a bit more code in the critical path (an estimated two instructions per non-constant shift: a test and a branch), and it probably will cost extra execution time.

However, none of the existing code will incur that cost because all shift counts are unsigned integers at this point, thus the compiler can omit the check. For new code using non-constant integer shift counts, often the compiler may be able to prove that the operand is non-negative. Furthermore, we can always introduce an explicit uint conversion, telling the compiler that we know the value is non-negative. This may be the policy of choice in performance-critical code using shifts (e.g., math/bits).

On the plus side, code that used a uint conversion before won't need it anymore, and will be safer for that since possibly negative values are not silently converted into positive ones.

Compatibility

This is a backward-compatible language change: Any valid program will continue to be valid, and will continue to run exactly the same, without any performance impact. New programs may be using non-constant integer shift counts as right operands in shift operations. Except for fairly small changes to the spec, the compiler, and go/types, (and possibly go/vet and go/lint if they look at shift operations), no other code needs to be changed.

There's a (remote) chance that some code makes use of negative shift count values:

var shift int = <some expression> // use negative value to indicate that we want a 0 result
result := x << uint(shift)

Here, uint(shift) will produce a very large positive value if shift is negative, resulting in x << uint(shift) becoming 0. Because such code required an explicit conversion and will continue to require an explicit conversion, it will continue to work.

Implementation

TBD

Open issues (if applicable)

TBD