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

proposal: Go 2: spec: add integer types with explicit overflow behavior, and remove unchecked operations on built-in integers #30209

Open
bcmills opened this issue Feb 13, 2019 · 24 comments

Comments

@bcmills
Copy link
Member

commented Feb 13, 2019

This proposal is intended to accomplish the same goals as #19624, but in a way that complies with the migration strategy outlined in https://github.com/golang/proposal/blob/master/design/28221-go2-transitions.md#language-redefinitions.

See #19624 for background.

Summary
This proposal would:

  1. Add three new packages: checked, wrapped, and unbounded, containing integer types with distinguished semantics to be defined in the language spec.
  2. Add the , ok form (as described in #19624) to explicitly check for overflow in expressions of any bounded numeric type.
  3. Remove the ability to perform unchecked arithmetic operations on the predeclared integer types.

New packages

The three new packages each provide a set of integer types:

// Package checked defines integer types whose arithmetic operations and conversions
// panic on overflow.
// Bitwise operations and logical shifts will not trigger a panic.
package checked

type Uint8 <builtin>
type Uint16 <builtin>
[…]

type Int8 <builtin>
[…]

type Byte = Uint8
type Rune <builtin>

type Int <builtin>
type Uint <builtin>
type Uintptr <builtin>
// Package wrapped defines integer types whose arithmetic operations and conversions wrap
// using two's-complement arithmetic.
package wrapped

type Uint8 <builtin>
[…]

type Int8 <builtin>
[…]

type Byte = Uint8
type Rune <builtin>

type Int <builtin>
type Uint <builtin>
type Uintptr <builtin>
// Package unbounded defines an arbitrary-precision integer type with unbounded range.
// Unbounded types do not support bitwise XOR, complement, or clear operations.
package unbounded

type Int <builtin>

Defined types

Defined types that have checked, wrapped, or unbounded types as their underlying type have the same operations and behavior as the underlying type.

Defined types that have builtin integer types as their underlying type have the same behavior as the underlying type, except that they are not mutually-assignable with checked or wrapped types.

Checked assignment

A checked assignment uses the form x, ok = <expression> or x, ok := <expression>, where <expression> can comprise any number of arithmetic, bitwise, logical, and/or conversion operations yielding a checked, wrapped, unbounded, user-defined, or builtin integer type. The operations in a checked assignment do not panic even if they involve checked or builtin integer types. The ok result, which may be assigned to any boolean type, indicates whether any arithmetic operation or conversion within the expression overflowed. The x result has the type of <expression> and a value computed using two's-complement wrapping.

Bitwise operations and logical shifts do not overflow, and therefore do not set the ok result. (Recall that signed shifts are defined to be arithmetic, while unsigned shifts are defined to be logical.)

Unchecked arithmetic operations on builtin integer types are a compile-time error.

var x int32 = 1<<31 - 1
y := x + 1  // compile-time error: `x + 1` is not checked for overflow
var x int32 = 1<<31 - 1
y, ok := x + 1  // y = -2147483648; ok = false
var x checked.Int32 = 1<<31 - 1
y := x + 1  // run-time panic: `x + 1` overflows
var x checked.Int32 = 1<<31 - 1
y, ok := x + 1  // y = -2147483648; ok = false
var x wrapped.Int32 = 1<<31 - 1
y := x + 1  // y = -2147483648
var x wrapped.Int32 = 1<<31 - 1
y, ok := x + 1  // y = -2147483648; ok = false
var x int32 = 1<<30
y, ok := x<<1  // y = -2147483648; ok = false
// signed shift is arithmetic, and shifting into the sign bit overflows
var x uint32 = 1<<31
y, ok := x<<1  // y = 0; ok = true
// unsigned shift is logical, and by definition cannot overflow

Conversion

Any integer type can be explicitly converted to a checked, wrapped, or unbounded integer type.
A checked, wrapped, or unbounded integer type can be converted to a builtin type only if either the conversion is checked or the destination type can represent all possible values of the source type.

var x checked.Int32 = 1<<31 - 1
var y = int32(x)  // y = 2147483647
var x checked.Uint32 = 1<<31 - 1
var y = int32(x)  // compile-time error: conversion from checked.Uint32 may overflow int32
var x checked.Uint32 = 1<<31
y, _ = int32(x)  // y = -2147483648

An unchecked conversion to a checked type panics if the value cannot be represented in the destination type.

var x int64 = 1<<31
y := checked.Int32(x)  // run-time panic: `x` overflows checked.Int32
var x int64 = 1<<31
y, ok := checked.Int32(x)  // y = -2147483648; ok = false

A conversion to a wrapped type wraps if the value cannot be represented in the destination type, even if the operand is of a larger checked type.

var x checked.Int64 = 1<<31
y := wrapped.Int32(x)  // y = -2147483648

A conversion to unbounded.Int from any integer type always succeeds. The conversion is applied after the operand is fully evaluated.

var x int64 = 1<<31
y := unbounded.Int(x)  // y = 2147483648
var x checked.Int32 = 1<<31-1
y := unbounded.Int(x+1)  // run-time panic: `x+1` overflows checked.Int32
var x wrapped.Int32 = 1<<31-1
y := unbounded.Int(x+1)  // y = -2147483648
var x checked.Int32 = 1<<31-1
y, ok := unbounded.Int(x+1)  // y = -2147483648; ok = false

Assignability

Each sized type in the checked and wrapped package is mutually assignable with the corresponding builtin sized type, but not with the type in the opposing package, nor with defined types of any underlying integer type.

var x wrapped.Int32 = 1<<31 - 1
var y int32
[…]
y = x + 1  // y = -2147483648
var x checked.Int32 = 1<<31-1
var y wrapped.Int32
[…]
y = x + 1  // compile-time error: checked.Int32 is not assignable to wrapped.Int32
type MyInt32 wrapped.Int32
var x wrapped.Int32 = 1<<31 - 1
var y MyInt32
[…]
y = x + 1  // compile-time error: wrapped.Int32 is not assignable to MyInt32
type MyInt32 int32
var x wrapped.Int32 = 1<<31 - 1
var y MyInt32
[…]
y = x + 1  // compile-time error: wrapped.Int32 is not assignable to MyInt32
var f func() int32
var g func(int32)
var x checked.Int32
x = f()
g(x + 1)  // ok: x+1 is checked, then passed to g as an int32

This allows functions to perform operations on checked or wrapped types, but to expose and use the corresponding builtin types at API boundaries (with less syntactic overhead for all involved).

Arithmetic operators

The type of an arithmetic expression depends on its operands. If both operands are of checked, wrapped, unbounded, or defined types, then they must have exactly the same type. If one operand is a checked, wrapped, or unbounded integer or a defined type with one of those types as its underlying type, and the other is either a builtin integer or untyped constant assignable to the first, then the result of the operation is the checked, wrapped, unbounded, or defined type.

If both operands are of a builtin integer type or a defined type with a builtin integer as its underlying type, the expression must be a checked assignment, bitwise operator, or logical shift, and its result is the same type as the operands.

Constants

An untyped integer constant can be assigned to any checked, wrapped, or unbounded integer type that can represent its value.

Unfortunately, in order to comply with https://github.com/golang/proposal/blob/master/design/28221-go2-transitions.md#language-changes, the inferred type of a variable initialized from an untyped constant must remain the built-in int.

@gopherbot gopherbot added this to the Proposal milestone Feb 13, 2019

@gopherbot gopherbot added the Proposal label Feb 13, 2019

@bcmills bcmills changed the title proposal: spec: add integer types with explicit overflow behavior and remove unchecked operations on built-in integers proposal: spec: add integer types with explicit overflow behavior, and remove unchecked operations on built-in integers Feb 13, 2019

@bcmills

This comment has been minimized.

Copy link
Member Author

commented Feb 13, 2019

Note that part (1) would be trivial if we had operator overloading, and part (3) could really just be a vet check.

The assignability rule could perhaps be eliminated from the proposal without causing too much damage. That would make the code much more verbose, but not fundamentally alter its structure.

Similarly, the conversion check might be implementable using generic constructor functions, and can be implemented (inefficiently and without type-safety) using reflection.

IMO, the interesting part of this proposal is part (2), the aggregation of overflow checks to the whole expression. That would otherwise require constructing an overflow-tracking object, using its methods in place of the existing arithmetic expressions, and remembering to check its result at the end — a lot of syntax, and much more error-prone than a regular old , ok.

@ericlagergren

This comment has been minimized.

Copy link
Contributor

commented Feb 13, 2019

How come the unbounded package only has a signed integer? An unsigned integer would be beneficial for some things I have in mind.

@bcmills

This comment has been minimized.

Copy link
Member Author

commented Feb 13, 2019

@ericlagergren An unbounded signed integer type can represent all of the unsigned values too, and is closed under subtraction.

In contrast, an unsigned type carries the risk of overflow: what would the behavior be for unbounded.Uint(0) - unbounded.Uint(1)? The whole point of the unbounded package is that its behavior on overflow is “not possible by definition”.

@josharian

This comment has been minimized.

Copy link
Contributor

commented Feb 14, 2019

I’ll admit I haven’t read this too carefully, but I hope you’ll permit me some questions anyway:

  • Why have wrapped? How does it differ from what we have now?
  • In the same vein, what do you think about adding saturating? (I think this was discussed elsewhere as well.)
  • I see the value in package checked as a namespace, but ISTM we could dispense with unbounded in favor of a new predeclared type, like integer or infinint (joking).
wking added a commit to wking/hive that referenced this issue Feb 14, 2019
*: Bump to install-config v0.12.0
Catching up with openshift/installer@dafc79f (Generate
Network.cluster config instead of NetworkConfig.networkoperator,
2019-01-15, openshift/installer#1013) and openshift/installer@3b393da
(pkg/types/aws/machinepool: Drop IAM-role overrides, 2019-01-30,
openshift/installer#1154).

The uint32 -> int32 cast is slightly dangerous, because it will
silently wrap overflowing values [1,2].  But I'll try and get the
installer updated to use unsigned types as well, and then we won't
have to worry about converting.

[1]: golang/go#19624
[2]: golang/go#30209
@bcmills

This comment has been minimized.

Copy link
Member Author

commented Feb 14, 2019

  • Why have wrapped? How does it differ from what we have now?

The wrapped types have the same semantics as the builtin types today.

The wrapped package exists so that we can remove the arithmetic operators from the built-in types.
Otherwise, it's much too easy to forget to convert a value to checked and end up with (undiagnosed) wrapping behavior where you really meant for the operations to never overflow.

@bcmills

This comment has been minimized.

Copy link
Member Author

commented Feb 14, 2019

  • In the same vein, what do you think about adding saturating? (I think this was discussed elsewhere as well.)

I think that would be fine. I don't know of many cases where it's actually useful, but it doesn't seem actively harmful either.

@bcmills

This comment has been minimized.

Copy link
Member Author

commented Feb 14, 2019

  • I see the value in package checked as a namespace, but ISTM we could dispense with unbounded in favor of a new predeclared type, like integer or infinint (joking).

Indeed. I don't feel strongly about that either way — I'm happy to go with whatever makes the proposal more palatable to the folks making the final decision. 🙂

@bcmills bcmills closed this Feb 14, 2019

@bcmills bcmills reopened this Feb 14, 2019

wking added a commit to wking/hive that referenced this issue Feb 14, 2019
*: Bump to install-config v0.12.0
Catching up with openshift/installer@dafc79f (Generate
Network.cluster config instead of NetworkConfig.networkoperator,
2019-01-15, openshift/installer#1013) and openshift/installer@3b393da
(pkg/types/aws/machinepool: Drop IAM-role overrides, 2019-01-30,
openshift/installer#1154).

The uint32 -> int32 cast is slightly dangerous, because it will
silently wrap overflowing values [1,2].  But I'll try and get the
installer updated to use unsigned types as well, and then we won't
have to worry about converting.

[1]: golang/go#19624
[2]: golang/go#30209
wking added a commit to wking/hive that referenced this issue Feb 14, 2019
*: Bump to install-config v0.12.0
Catching up with openshift/installer@dafc79f (Generate
Network.cluster config instead of NetworkConfig.networkoperator,
2019-01-15, openshift/installer#1013), openshift/installer@3b393da
(pkg/types/aws/machinepool: Drop IAM-role overrides, 2019-01-30,
openshift/installer#1154), and openshift/installer@9ad20c3
(pkg/destroy/aws: Remove ClusterName consumer, 2019-01-31,
openshift/installer#1170).

The uint32 -> int32 cast is slightly dangerous, because it will
silently wrap overflowing values [1,2].  But I'll try and get the
installer updated to use unsigned types as well, and then we won't
have to worry about converting.

[1]: golang/go#19624
[2]: golang/go#30209
wking added a commit to wking/hive that referenced this issue Feb 14, 2019
*: Bump to install-config v0.12.0
Catching up with openshift/installer@dafc79f (Generate
Network.cluster config instead of NetworkConfig.networkoperator,
2019-01-15, openshift/installer#1013), openshift/installer@3b393da
(pkg/types/aws/machinepool: Drop IAM-role overrides, 2019-01-30,
openshift/installer#1154), and openshift/installer@9ad20c3
(pkg/destroy/aws: Remove ClusterName consumer, 2019-01-31,
openshift/installer#1170).

The uint32 -> int32 cast is slightly dangerous, because it will
silently wrap overflowing values [1,2].  But I'll try and get the
installer updated to use unsigned types as well, and then we won't
have to worry about converting.

[1]: golang/go#19624
[2]: golang/go#30209
wking added a commit to wking/hive that referenced this issue Feb 14, 2019
*: Bump to install-config v0.12.0
Catching up with openshift/installer@dafc79f (Generate
Network.cluster config instead of NetworkConfig.networkoperator,
2019-01-15, openshift/installer#1013), openshift/installer@3b393da
(pkg/types/aws/machinepool: Drop IAM-role overrides, 2019-01-30,
openshift/installer#1154), and openshift/installer@9ad20c3
(pkg/destroy/aws: Remove ClusterName consumer, 2019-01-31,
openshift/installer#1170).

The uint32 -> int32 cast is slightly dangerous, because it will
silently wrap overflowing values [1,2].  But I'll try and get the
installer updated to use unsigned types as well, and then we won't
have to worry about converting.

[1]: golang/go#19624
[2]: golang/go#30209
wking added a commit to wking/hive that referenced this issue Feb 14, 2019
*: Bump to install-config v0.12.0
Catching up with openshift/installer@dafc79f (Generate
Network.cluster config instead of NetworkConfig.networkoperator,
2019-01-15, openshift/installer#1013), openshift/installer@3b393da
(pkg/types/aws/machinepool: Drop IAM-role overrides, 2019-01-30,
openshift/installer#1154), and openshift/installer@9ad20c3
(pkg/destroy/aws: Remove ClusterName consumer, 2019-01-31,
openshift/installer#1170).

The uint32 -> int32 cast is slightly dangerous, because it will
silently wrap overflowing values [1,2].  But I'll try and get the
installer updated to use unsigned types as well, and then we won't
have to worry about converting.

[1]: golang/go#19624
[2]: golang/go#30209
@tv42

This comment has been minimized.

Copy link

commented Feb 14, 2019

I'm sorry I haven't read everything carefully but how exactly is this backwards compatible?

Unchecked arithmetic operations on builtin integer types are a compile-time error.

var x int32 = 1<<31 - 1
y := x + 1  // compile-time error: `x + 1` is not checked for overflow

EDIT: I guess it's not intended to be? Is there any idea of how much existing code this would break?

@ianlancetaylor ianlancetaylor changed the title proposal: spec: add integer types with explicit overflow behavior, and remove unchecked operations on built-in integers proposal: Go 2: spec: add integer types with explicit overflow behavior, and remove unchecked operations on built-in integers Feb 14, 2019

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Feb 14, 2019

Unchecked arithmetic operations on builtin integer types are a compile-time error.

If I'm reading this correctly essentially every existing Go program would become invalid, because they all have arithmetic operations on builtin integer types. That seems like a very heavy lift.

@networkimprov

This comment has been minimized.

Copy link

commented Feb 14, 2019

@ianlancetaylor do you consider backwards-incompatible features which are trivially accommodated by go fix to be problematic? (Not sure whether this particular concept is easily go-fixable...)

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Feb 14, 2019

Running go fix can certainly help, but it's not a panacea. We also have to consider all existing books, documentation, tutorials, etc.

@dpinela

This comment has been minimized.

Copy link
Contributor

commented Feb 15, 2019

I'd prefer to see plain int become arbitrary-precision (#19623). Usually when I'm writing code that uses integers I don't want to choose whether I want it them to wrap or panic on overflow. I'd rather just get the (mathematically) correct result by default without having to type unbounded.Int everywhere to get it, and use the fixed-size types - either the existing ones or the ones in this proposal - if I need to optimise.

Even in the latter case, I feel like this proposal would make bounded arithmetic code overly verbose.

As an aside, why disallow XOR and complement on unbounded ints? Assuming they're signed, aren't both operations well-defined and guaranteed to yield a finite result?

@bcmills

This comment has been minimized.

Copy link
Member Author

commented Feb 15, 2019

If I'm reading this correctly essentially every existing Go program would become invalid, because they all have arithmetic operations on builtin integer types.

Probably every program, but not every package: in particular, packages that use range loops rather than indices for iteration would be mostly unaffected. (The point of the breaking change is to prompt code owners to make an explicit decision about the overflow behavior they intend.)

Also note that it would be possible to adopt parts (1) and (2) of this proposal — the new packages and checked assignment — without the breaking change of part (3). That would provide a much smaller benefit, but at a much smaller corresponding cost.

@bcmills

This comment has been minimized.

Copy link
Member Author

commented Feb 15, 2019

I'd prefer to see plain int become arbitrary-precision (#19623).

Note that that proposal does not comply with the migration strategy outlined in https://github.com/golang/proposal/blob/master/design/28221-go2-transitions.md#language-redefinitions.

@bcmills

This comment has been minimized.

Copy link
Member Author

commented Feb 15, 2019

As an aside, why disallow XOR and complement on unbounded ints? Assuming they're signed, aren't both operations well-defined and guaranteed to yield a finite result?

Interesting question. Mostly I think it's weird to apply two's-complement arithmetic when the sign bit is infinitely far away, but I suppose it is still well-defined. Perhaps they would be ok after all.

@ericlagergren

This comment has been minimized.

Copy link
Contributor

commented Feb 15, 2019

It’s basically a big.Int, and that has XOR.

@beoran

This comment has been minimized.

Copy link

commented Feb 15, 2019

I am aginst part 3 of the proposal, since that would take us too far.
But I am in favor of part 1 and 2, particularly for checked types. I don't care too much about wrapping types. Now, if we combine part 1 and 2 with my ranged types proposal here: https://gist.github.com/beoran/83526ce0c1ff2971a9119d103822533a, then we could write:

// Package checked defines integer types whose arithmetic operations and conversions
// panic on overflow.
package checked

type Uint8 = range uint8[0:255]
type Uint16 = range uint16[0:65535]
type Int8 = range int8[-127:127]
type Int16 = range int16[-32767..32768]

So, with my proposal, that will include the result, ok := form, the checked part of this proposal becomes a package that is user-implementable. And, arguably, this approach is more useful because you can also have checked types with a narrower range of values.

@bcmills

This comment has been minimized.

Copy link
Member Author

commented Feb 15, 2019

@beoran I like the generalization to ranged types, but note that there is one subtle mismatch between this proposal and yours. Your proposal requires:

For all ranged types, whenever possible the compiler checks at compile time that any assignments to a variable of a ranged type respects either the bounds or is one of the enumerated values, and emits a compile error if the value of a variable or constant can be proven to be not in range.

This proposal explicitly does not: the overflow check in this proposal is always dynamic, because that's much easier to implement portably, and it is possible that the part of the code in which the overflow occurs may not actually be reachable (for example, because it is on a code path that is only reachable on an architecture with a different-sized uintptr).

@beoran

This comment has been minimized.

Copy link

commented Feb 15, 2019

csrwng added a commit to csrwng/hive that referenced this issue Feb 19, 2019
*: Bump to install-config v0.12.0
Catching up with openshift/installer@dafc79f (Generate
Network.cluster config instead of NetworkConfig.networkoperator,
2019-01-15, openshift/installer#1013), openshift/installer@3b393da
(pkg/types/aws/machinepool: Drop IAM-role overrides, 2019-01-30,
openshift/installer#1154), and openshift/installer@9ad20c3
(pkg/destroy/aws: Remove ClusterName consumer, 2019-01-31,
openshift/installer#1170).

The uint32 -> int32 cast is slightly dangerous, because it will
silently wrap overflowing values [1,2].  But I'll try and get the
installer updated to use unsigned types as well, and then we won't
have to worry about converting.

[1]: golang/go#19624
[2]: golang/go#30209
@beoran

This comment has been minimized.

Copy link

commented Feb 20, 2019

I amended the proposal. Now I propose the range check is on compile type for constants, and run time for variables, although the compiler may still do the range checking at compile time (implementation defined). I also detailed the spec of len(range), worked out other details more. I also disallowed complex underlying types for range types and for range boundaries since for complex64 and complex128, the meaning of "range" becomes quite complex, indeed.

wking added a commit to wking/hive that referenced this issue Feb 21, 2019
*: Bump to install-config v0.12.0
Catching up with openshift/installer@dafc79f (Generate
Network.cluster config instead of NetworkConfig.networkoperator,
2019-01-15, openshift/installer#1013), openshift/installer@3b393da
(pkg/types/aws/machinepool: Drop IAM-role overrides, 2019-01-30,
openshift/installer#1154), and openshift/installer@9ad20c3
(pkg/destroy/aws: Remove ClusterName consumer, 2019-01-31,
openshift/installer#1170).

The uint32 -> int32 cast is slightly dangerous, because it will
silently wrap overflowing values [1,2].  But I'll try and get the
installer updated to use unsigned types as well, and then we won't
have to worry about converting.

[1]: golang/go#19624
[2]: golang/go#30209
@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Mar 12, 2019

I would argue that the comma-ok idea suggested here, part 2 of the proposal, should not be done initially. I argue this on two points. First, I think that few people will actually want that feature. Second, for those people who really do want it, they can already write it by using a deferred function that calls recover. So I think it's appropriate to simply postpone that part of the proposal indefinitely, until we have a clearer understanding of how often would want to use it.

@bcmills

This comment has been minimized.

Copy link
Member Author

commented May 13, 2019

I would be ok with omitting the , ok form for now.

I think its major use-cases are for down-casting checked types (for which an explicit range check isn't a lot of extra code) and for omitting double-conversions when writing isolated arithmetic expressions in mostly-non-arithmetic (or mostly-checked) blocks of code, but the alternatives using explicit conversions for those use-cases don't seem terrible.

@bcmills

This comment has been minimized.

Copy link
Member Author

commented Jul 29, 2019

#33342 found a neat overflow in the runtime package:

if rate != 1 && int32(size) < c.next_sample {

@beoran

This comment has been minimized.

Copy link

commented Jul 30, 2019

This is why I feel ranged types are an important feature of Ada and other Wirth-like languages: they help writing correct programs without overflow. As it stands now, in Go, like other C inspired languages, it is still too easy to accidentally cause overflow. Go would do well to adopt range types to prevent this.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
9 participants
You can’t perform that action at this time.