Integer overflow, round -2147483648

classic Classic list List threaded Threaded
165 messages Options
1234 ... 9
Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Gábor Lehel-2
# Exposition

We've debated the subject of integer overflow quite a bit, without much
apparent progress. Essentially, we've been running in circles around two
core facts: wrapping is bad, but checking is slow. The current consensus
seems to be to, albeit grudgingly, stick with the status quo.

I think we've established that a perfect, one-size-fits-all solution is not
possible. But I don't think this means that we're out of options, or have
no room for improvement. I think there are several imperfect, partial
solutions we could pursue, to address the various use cases in a
divide-and-conquer fashion.

This is not a formal RFC, more of a grab bag of thoughts and ideas.

The central consideration has to be the observation that, while wrapping
around on overflow is well-supported by hardware, for the large majority of
programs, it's the wrong behavior.

Basically, programs are just hoping that overflow won't happen. And if it
ever does happen, it's going to result in unexpected behavior and bugs.
(Including the possibility of security bugs: not all security bugs are
memory safety bugs.) This is a step up from C's insanity of undefined
behavior for signed overflow, where the compiler assumes that overflow
*cannot* happen and even optimizes based on that assumption, but it's still
a sad state of affairs. If we're clearing the bar, that's only because it's
been buried underground.

We can divide programs into three categories. (I'm using "program" in the
general sense of "piece of code which does a thing".)

 1) Programs where wrapping around on overflow is the desired semantics.

 2) Programs where wrapping around on overflow is not the desired
semantics, but performance is not critical.

 3) Programs where wrapping around on overflow is not the desired semantics
and performance is critical.

Programs in (1) are well-served by the language and libraries as they are,
and there's not much to do except to avoid regressing.

Programs in (2) and (3) are not as well-served.


# Checked math

For (2), the standard library offers checked math in the `CheckedAdd`,
`CheckedMul` etc. traits, as well as integer types of unbounded size:
`BigInt` and `BigUint`. This is good, but it's not enough. The acid test
has to be whether for non-performance-critical code, people are actually
*using* checked math. If they're not, then we've failed.

`CheckedAdd` and co. are important to have for flexibility, but they're far
too unwieldy for general use. People aren't going to write
`.checked_add(2).unwrap()` when they can write `+ 2`. A more adequate
design might be something like this:

 * Have traits for all the arithmetic operations for both checking on
overflow and for wrapping around on overflow, e.g. `CheckedAdd` (as now),
`WrappingAdd`, `CheckedSub`, `WrappingSub`, and so on.

 * Offer convenience methods for the Checked traits which perform
`unwrap()` automatically.

 * Have separate sets of integer types which check for overflow and which
wrap around on overflow. Whatever they're called: `CheckedU8`,
`checked::u8`, `uc8`, ...

 * Both sets of types implement all of the Checked* and Wrapping* traits.
You can use explicit calls to get either behavior with either types.

 * The checked types use the Checked traits to implement the operator
overloads (`Add`, Mul`, etc.), while the wrapping types use the Wrapping
traits to implement them. In other words, the difference between the types
is (probably only) in the behavior of the operators.

 * `BigInt` also implements all of the Wrapping and Checked traits: because
overflow never happens, it can claim to do anything if it "does happen".
`BigUint` implements all of them except for the Wrapping traits which may
underflow, such as `WrappingSub`, because it has nowhere to wrap around to.

Another option would be to have just one set of types but two sets of
operators, like Swift does. I think that would work as well, or even
better, but we've been avoiding having any operators which aren't familiar
from C.


#  Unbounded integers

While checked math helps catch instances of overflow and prevent
misbehaviors and bugs, many programs would prefer integer types which do
the right thing and don't overflow in the first place. For this, again, we
currently have `BigInt` and `BigUint`. There's one problem with these:
because they may allocate, they no longer `Copy`, which means that they
can't be just drop-in replacements for the fixed-size types.

To partially address this, once we have tracing GC, and if we manage to
make `Gc<T>: Copy`, we should add unbounded `Integer` (as in Haskell) and
`Natural` types which internally use `Gc`, and so are also `Copy`. (In
exchange, they wouldn't be `Send`, but that's far less pervasive.) These
would (again, asides from `Send`) look and feel just like the built-in
fixed-size types, while having the semantics of actual mathematical
integers, resp. naturals (up to resource exhaustion of course). They would
be ideal for code which is not performance critical and doesn't mind
incurring, or already uses, garbage collection. For those cases, you
wouldn't have to think about the tradeoffs, or make difficult choices:
`Integer` is what you use.

One concern with this would be the possibility of programs incurring GC
accidentally by using these types. There's several ways to deal with this:

 * Note the fact that they use GC prominently in the documentation.

 * Make sure the No-GC lint catches any use of them.

 * Offer a "no GC in this task" mode which fails the task if GC allocation
is invoked, to catch mistakes at runtime.

I think these would be more than adequate to address the concern.


# Between a rock and a hard place

Having dispatched the "easy" cases above, for category #3 we're left
between the rock (wraparound on overflow is wrong) and the hard place
(checking for overflow is slow).

Even here, we may have options.

An observation:

 * We are adamantly opposed to compiler switches to turn off array bounds
checking, because we are unwilling to compromise memory safety.

 * We are relatively unbothered by unchecked arithmetic, because it
*doesn't* compromise memory safety.

Taking these together, I think we should at least be less than adamantly
opposed to compiler switches for enabling or disabling checked arithmetic.

Consider the status quo. People use integer types which wrap on overflow.
If they ever do overflow, it means misbehaviors and bugs. If we had a
compiler flag to turn on checked arithmetic, even if it were only used a
few times in testing, it would be a strict improvement: more bugs would be
caught with less effort.

But we clearly can't just add this flag for existing types, because they're
well-defined to wrap around on overflow, and some programs (category #1)
rely on this. So we need to have separate types.

One option is therefore to just define this set of types as failing the
task on overflow if checked arithmetic is enabled, and to wrap around if
it's disabled. But it doesn't necessarily make sense to specify wraparound
in the latter case, given that programs are not supposed to depend on it:
they may be compiled with either flag, and should avoid overflow.

Another observation:

 * Undefined behavior is anathema to the safe subset of the language. That
would mean that it's not safe.

 * But *unspecified results* are maybe not so bad. We might already have
them for bit-shifts. (Question for the audience: do we?)

If unspecified results are acceptable, then we could instead say that these
types fail on overflow if checked arithmetic is enabled, and have
unspecified results if it isn't. But saying they wrap around is fine as
well.

This way, we can put off the choice between the rock and the hard place
from program-writing time to compile time, at least.


# Defaults

Even if we provide the various options from above, from the perspective of
what types people end up using, defaults are very important.

There's two kinds of defaults:

* The de jure default, inferred by the type system in the absence of other
information, which used to be `int`. Thankfully, we're removing this.

* The de facto, cultural default. For instance, if there is a type called
"int", most people will use it without thinking.

The latter question is still something we need to think about. Should we
have a clear cultural default? Or should we force people to explicitly
choose between checked and wrapping arithmetic?

For the most part, this boils down to:

 * If `int` is checked, the default is slow

 * If `int` wraps, the default is wrong

 * If there is no `int`, people are confused

Regarding the first, we seem to be living in deathly fear of someone
naively writing an arithmetic benchmark in Rust, putting it up on the
internet, and saying, "Look: Rust is slow". This is not an unrealistic
scenario, sadly. The question is whether we'd rather have more programs be
accidentally incorrect in order to avoid bad publicity from benchmarks
being accidentally slow.

Regarding the third, even if the only types we have are `intc`, `intw`,
`ic8`, `iw8`, and so on, we *still* can't entirely escape creating a
cultural default, because we still need to choose types for functions in
the standard library and for built-in operations like array indexing. Then
the path of least resistance for any given program will be to use the same
types.

There's one thing that might help resolve this conundrum, which is if we
consider the previously-described scheme with compiler flags to control
checked arithmetic to be acceptable. In that case, I think those types
would be the clear choice to be the de facto defaults. Then we would have:

 * `i8`, `u8` .. `i64`, `u64`, `int`, and `uint` types, which fail the task
on overflow if checked arithmetic is turned on, and either wrap around or
have an unspecified result if it's off

 * a corresponding set of types somewhere in the standard library, which
wrap around no matter what

 * and another set of corresponding types, which are checked no matter what


-G?bor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140618/70dce952/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Tony Arcieri
On Wed, Jun 18, 2014 at 10:08 AM, G?bor Lehel <glaebhoerl at gmail.com> wrote:
>
> # Between a rock and a hard place
>
> Having dispatched the "easy" cases above, for category #3 we're left
> between the rock (wraparound on overflow is wrong) and the hard place
> (checking for overflow is slow).
>
> Even here, we may have options.
>

I really like what Swift did: define two sets of operators, a default one
which checks/errors on overflow, and a second set of "overflow operators"
(which look like &+ &- etc) when you need the performance of unchecked
operations or otherwise desire overflow behavior:

https://developer.apple.com/library/prerelease/ios/documentation/swift/conceptual/swift_programming_language/AdvancedOperators.html#//apple_ref/doc/uid/TP40014097-CH27-XID_37

--
Tony Arcieri
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140618/e46ad77b/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Daniel Micay
In reply to this post by Gábor Lehel-2
On 18/06/14 01:08 PM, G?bor Lehel wrote:

> # Exposition
>
> We've debated the subject of integer overflow quite a bit, without much
> apparent progress. Essentially, we've been running in circles around two
> core facts: wrapping is bad, but checking is slow. The current consensus
> seems to be to, albeit grudgingly, stick with the status quo.
>
> I think we've established that a perfect, one-size-fits-all solution is
> not possible. But I don't think this means that we're out of options, or
> have no room for improvement. I think there are several imperfect,
> partial solutions we could pursue, to address the various use cases in a
> divide-and-conquer fashion.
>
> This is not a formal RFC, more of a grab bag of thoughts and ideas.
>
> The central consideration has to be the observation that, while wrapping
> around on overflow is well-supported by hardware, for the large majority
> of programs, it's the wrong behavior.
>
> Basically, programs are just hoping that overflow won't happen. And if
> it ever does happen, it's going to result in unexpected behavior and
> bugs. (Including the possibility of security bugs: not all security bugs
> are memory safety bugs.) This is a step up from C's insanity of
> undefined behavior for signed overflow, where the compiler assumes that
> overflow *cannot* happen and even optimizes based on that assumption,
> but it's still a sad state of affairs. If we're clearing the bar, that's
> only because it's been buried underground.
>
> We can divide programs into three categories. (I'm using "program" in
> the general sense of "piece of code which does a thing".)
>
>  1) Programs where wrapping around on overflow is the desired semantics.
>
>  2) Programs where wrapping around on overflow is not the desired
> semantics, but performance is not critical.

If performance wasn't critical, the program wouldn't be written in Rust.
The language isn't aimed at use cases where performance isn't a bug
deal, as it makes many sacrifices to provide the level of control that's
available.

>  3) Programs where wrapping around on overflow is not the desired
> semantics and performance is critical.
>
> Programs in (1) are well-served by the language and libraries as they
> are, and there's not much to do except to avoid regressing.
>
> Programs in (2) and (3) are not as well-served.
>
>
> # Checked math
>
> For (2), the standard library offers checked math in the `CheckedAdd`,
> `CheckedMul` etc. traits, as well as integer types of unbounded size:
> `BigInt` and `BigUint`. This is good, but it's not enough. The acid test
> has to be whether for non-performance-critical code, people are actually
> *using* checked math. If they're not, then we've failed.
>
> `CheckedAdd` and co. are important to have for flexibility, but they're
> far too unwieldy for general use. People aren't going to write
> `.checked_add(2).unwrap()` when they can write `+ 2`. A more adequate
> design might be something like this:
>
>  * Have traits for all the arithmetic operations for both checking on
> overflow and for wrapping around on overflow, e.g. `CheckedAdd` (as
> now), `WrappingAdd`, `CheckedSub`, `WrappingSub`, and so on.
>
>  * Offer convenience methods for the Checked traits which perform
> `unwrap()` automatically.
>
>  * Have separate sets of integer types which check for overflow and
> which wrap around on overflow. Whatever they're called: `CheckedU8`,
> `checked::u8`, `uc8`, ...
>
>  * Both sets of types implement all of the Checked* and Wrapping*
> traits. You can use explicit calls to get either behavior with either types.
>
>  * The checked types use the Checked traits to implement the operator
> overloads (`Add`, Mul`, etc.), while the wrapping types use the Wrapping
> traits to implement them. In other words, the difference between the
> types is (probably only) in the behavior of the operators.
>
>  * `BigInt` also implements all of the Wrapping and Checked traits:
> because overflow never happens, it can claim to do anything if it "does
> happen". `BigUint` implements all of them except for the Wrapping traits
> which may underflow, such as `WrappingSub`, because it has nowhere to
> wrap around to.
>
> Another option would be to have just one set of types but two sets of
> operators, like Swift does. I think that would work as well, or even
> better, but we've been avoiding having any operators which aren't
> familiar from C.
>
>
> #  Unbounded integers
>
> While checked math helps catch instances of overflow and prevent
> misbehaviors and bugs, many programs would prefer integer types which do
> the right thing and don't overflow in the first place. For this, again,
> we currently have `BigInt` and `BigUint`. There's one problem with
> these: because they may allocate, they no longer `Copy`, which means
> that they can't be just drop-in replacements for the fixed-size types.
>
>
> To partially address this, once we have tracing GC, and if we manage to
> make `Gc<T>: Copy`, we should add unbounded `Integer` (as in Haskell)
> and `Natural` types which internally use `Gc`, and so are also `Copy`.
> (In exchange, they wouldn't be `Send`, but that's far less pervasive.)
> These would (again, asides from `Send`) look and feel just like the
> built-in fixed-size types, while having the semantics of actual
> mathematical integers, resp. naturals (up to resource exhaustion of
> course). They would be ideal for code which is not performance critical
> and doesn't mind incurring, or already uses, garbage collection. For
> those cases, you wouldn't have to think about the tradeoffs, or make
> difficult choices: `Integer` is what you use.

A tracing garbage collector for Rust is a possibility but not a
certainty. I don't think it would make sense to have `Gc<T>` support
`Copy` but have it left out for `Rc<T>`. The fact that an arbitrary
compiler decision like that would determine the most convenient type is
a great reason to avoid making that arbitrary choice.

There's no opportunity for cycles in integers, and `Rc<T>` will be
faster along with using far less memory. It doesn't have the overhead
associated with reference counting in other languages due to being
task-local (not atomic) and much of the reference counting is elided by
move semantics / borrows.

With the help of sized deallocation, Rust can have an incredibly fast
allocator implementation. Since `Rc<T>` is task-local, it also doesn't
need to be using the same allocator entry point as sendable types. It
can make use of a thread-local allocator with less complexity and
overhead, although this could also be available on an opt-in basis for
sendable types by changing the allocator parameter from the default.

> One concern with this would be the possibility of programs incurring GC
> accidentally by using these types. There's several ways to deal with this:
>
>  * Note the fact that they use GC prominently in the documentation.
>
>  * Make sure the No-GC lint catches any use of them.
>
>  * Offer a "no GC in this task" mode which fails the task if GC
> allocation is invoked, to catch mistakes at runtime.
>
> I think these would be more than adequate to address the concern.

I don't think encouraging tracing garbage collection is appropriate for
a language designed around avoiding it. It would be fine to have it as a
choice if it never gets in the way, but it shouldn't be promoted as a
default.

> # Between a rock and a hard place
>
> Having dispatched the "easy" cases above, for category #3 we're left
> between the rock (wraparound on overflow is wrong) and the hard place
> (checking for overflow is slow).
>
> Even here, we may have options.
>
> An observation:
>
>  * We are adamantly opposed to compiler switches to turn off array
> bounds checking, because we are unwilling to compromise memory safety.
>
>  * We are relatively unbothered by unchecked arithmetic, because it
> *doesn't* compromise memory safety.
>
> Taking these together, I think we should at least be less than adamantly
> opposed to compiler switches for enabling or disabling checked arithmetic.

I think compiler switches or attributes enabling a different dialect of
the language are a bad idea as a whole. Code from libraries is directly
mixed into other crates, so changing the semantics of the language is
inherently broken.

> Consider the status quo. People use integer types which wrap on
> overflow. If they ever do overflow, it means misbehaviors and bugs. If
> we had a compiler flag to turn on checked arithmetic, even if it were
> only used a few times in testing, it would be a strict improvement: more
> bugs would be caught with less effort.
>
> But we clearly can't just add this flag for existing types, because
> they're well-defined to wrap around on overflow, and some programs
> (category #1) rely on this. So we need to have separate types.
>
> One option is therefore to just define this set of types as failing the
> task on overflow if checked arithmetic is enabled, and to wrap around if
> it's disabled. But it doesn't necessarily make sense to specify
> wraparound in the latter case, given that programs are not supposed to
> depend on it: they may be compiled with either flag, and should avoid
> overflow.
>
> Another observation:
>
>  * Undefined behavior is anathema to the safe subset of the language.
> That would mean that it's not safe.
>
>  * But *unspecified results* are maybe not so bad. We might already have
> them for bit-shifts. (Question for the audience: do we?)
>
> If unspecified results are acceptable, then we could instead say that
> these types fail on overflow if checked arithmetic is enabled, and have
> unspecified results if it isn't. But saying they wrap around is fine as
> well.
>
> This way, we can put off the choice between the rock and the hard place
> from program-writing time to compile time, at least.
>
>
> # Defaults
>
> Even if we provide the various options from above, from the perspective
> of what types people end up using, defaults are very important.
>
> There's two kinds of defaults:
>
> * The de jure default, inferred by the type system in the absence of
> other information, which used to be `int`. Thankfully, we're removing this.
>
> * The de facto, cultural default. For instance, if there is a type
> called "int", most people will use it without thinking.
>
> The latter question is still something we need to think about. Should we
> have a clear cultural default? Or should we force people to explicitly
> choose between checked and wrapping arithmetic?
>
> For the most part, this boils down to:
>
>  * If `int` is checked, the default is slow
>  
>  * If `int` wraps, the default is wrong
>
>  * If there is no `int`, people are confused
>
> Regarding the first, we seem to be living in deathly fear of someone
> naively writing an arithmetic benchmark in Rust, putting it up on the
> internet, and saying, "Look: Rust is slow". This is not an unrealistic
> scenario, sadly. The question is whether we'd rather have more programs
> be accidentally incorrect in order to avoid bad publicity from
> benchmarks being accidentally slow.
>
> Regarding the third, even if the only types we have are `intc`, `intw`,
> `ic8`, `iw8`, and so on, we *still* can't entirely escape creating a
> cultural default, because we still need to choose types for functions in
> the standard library and for built-in operations like array indexing.
> Then the path of least resistance for any given program will be to use
> the same types.
>
> There's one thing that might help resolve this conundrum, which is if we
> consider the previously-described scheme with compiler flags to control
> checked arithmetic to be acceptable. In that case, I think those types
> would be the clear choice to be the de facto defaults. Then we would have:
>
>  * `i8`, `u8` .. `i64`, `u64`, `int`, and `uint` types, which fail the
> task on overflow if checked arithmetic is turned on, and either wrap
> around or have an unspecified result if it's off
>
>  * a corresponding set of types somewhere in the standard library, which
> wrap around no matter what
>
>  * and another set of corresponding types, which are checked no matter what
>
>
> -G?bor

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140618/93354284/attachment.sig>

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Brian Anderson
In reply to this post by Gábor Lehel-2

On 06/18/2014 10:08 AM, G?bor Lehel wrote:

>
> # Checked math
>
> For (2), the standard library offers checked math in the `CheckedAdd`,
> `CheckedMul` etc. traits, as well as integer types of unbounded size:
> `BigInt` and `BigUint`. This is good, but it's not enough. The acid
> test has to be whether for non-performance-critical code, people are
> actually *using* checked math. If they're not, then we've failed.
>
> `CheckedAdd` and co. are important to have for flexibility, but
> they're far too unwieldy for general use. People aren't going to write
> `.checked_add(2).unwrap()` when they can write `+ 2`. A more adequate
> design might be something like this:
>
>  * Have traits for all the arithmetic operations for both checking on
> overflow and for wrapping around on overflow, e.g. `CheckedAdd` (as
> now), `WrappingAdd`, `CheckedSub`, `WrappingSub`, and so on.
>
>  * Offer convenience methods for the Checked traits which perform
> `unwrap()` automatically.
>
>  * Have separate sets of integer types which check for overflow and
> which wrap around on overflow. Whatever they're called: `CheckedU8`,
> `checked::u8`, `uc8`, ...
>
>  * Both sets of types implement all of the Checked* and Wrapping*
> traits. You can use explicit calls to get either behavior with either
> types.
>
>  * The checked types use the Checked traits to implement the operator
> overloads (`Add`, Mul`, etc.), while the wrapping types use the
> Wrapping traits to implement them. In other words, the difference
> between the types is (probably only) in the behavior of the operators.
>
>  * `BigInt` also implements all of the Wrapping and Checked traits:
> because overflow never happens, it can claim to do anything if it
> "does happen". `BigUint` implements all of them except for the
> Wrapping traits which may underflow, such as `WrappingSub`, because it
> has nowhere to wrap around to.
>
> Another option would be to have just one set of types but two sets of
> operators, like Swift does. I think that would work as well, or even
> better, but we've been avoiding having any operators which aren't
> familiar from C.

The general flavor of this proposal w/r/t checked arithmetic sounds
pretty reasonable to me, and we can probably make progress on this now.
I particularly think that having checked types that use operator
overloading is important for ergonomics.

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

comex
In reply to this post by Gábor Lehel-2
On Wed, Jun 18, 2014 at 1:08 PM, G?bor Lehel <glaebhoerl at gmail.com> wrote:
> To partially address this, once we have tracing GC, and if we manage to make
> `Gc<T>: Copy`, we should add unbounded `Integer` (as in Haskell) and
> `Natural` types which internally use `Gc`, and so are also `Copy`. (In
> exchange, they wouldn't be `Send`, but that's far less pervasive.)

Wait, what?  Since when is sharing data between threads an uncommon use case?

(Personally I think this more points to the unwieldiness of typing
.clone() for cheap and potentially frequent clones like Rc...)

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Gregory Maxwell
In reply to this post by Gábor Lehel-2
On Wed, Jun 18, 2014 at 10:08 AM, G?bor Lehel <glaebhoerl at gmail.com> wrote:
> memory safety bugs.) This is a step up from C's insanity of undefined
> behavior for signed overflow, where the compiler assumes that overflow
> *cannot* happen and even optimizes based on that assumption, but it's still
> a sad state of affairs.

C's behavior is not without an advantage.  It means that every
operation on signed values in C has an implicit latent assertion for
analysis tools:  If wrapping can happen in operation the program is
wrong, end of story.  This means you can use existing static and
dynamic analysis tools while testing and have a zero false positive
rate? not just on your own code but on any third party code you're
depending on too.

In languages like rust where signed overflow is defined, no such
promises exists? signed overflow at runtime might be perfectly valid
behavior, and so analysis and testing require more work to produce
useful results.  You might impose a standard on your own code that
requires that all valid signed overflow must be annotated in some
manner, but this does nothing for third party code (including the
standard libraries).

The value here persists even when there is normally no checking at
runtime, because the tools can still be run sometimes? which is less
of a promise than always on runtime checking but it also has no
runtime cost.

So I think there would be a value in rust of having types for which
wrap is communicated by the developer as being invalid, even if it
were not normally checked at runtime. Being able to switch between
safety levels is not generally the rust way? or so it seems to me? and
may not be justifiably in cases where the risk vs cost ratio is
especially high (e.g. bounds checking on memory)... but I think it's
better than not having the safety facility at all.

The fact that C can optimize non-overflow is also fairly useful in
proving loop bounds and allowing the autovectorization to work.  I've
certantly had signal processing codebases where this made a
difference, but I'm not sure if the same communication to the
optimizer might not be available in other ways in rust.

> `CheckedAdd` and co. are important to have for flexibility, but they're far
> too unwieldy for general use. People aren't going to write
> `.checked_add(2).unwrap()` when they can write `+ 2`. A more adequate design
> might be something like this:

Not only does friction like that discourage use? it also gets in the
way of people switching behaviors between testing and production when
performance considerations really do preclude always on testing.

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Daniel Micay
In reply to this post by comex
On 18/06/14 03:40 PM, comex wrote:
> On Wed, Jun 18, 2014 at 1:08 PM, G?bor Lehel <glaebhoerl at gmail.com> wrote:
>> To partially address this, once we have tracing GC, and if we manage to make
>> `Gc<T>: Copy`, we should add unbounded `Integer` (as in Haskell) and
>> `Natural` types which internally use `Gc`, and so are also `Copy`. (In
>> exchange, they wouldn't be `Send`, but that's far less pervasive.)
>
> Wait, what?  Since when is sharing data between threads an uncommon use case?

Data remaining local to the thread it was allocated in is the common
case. That doesn't mean that sending dynamic allocations to other tasks
or sharing dynamic allocations is bad. `Rc<T>` is inherently local to a
thread, so it might as well be using an allocator leveraging that.

> (Personally I think this more points to the unwieldiness of typing
> .clone() for cheap and potentially frequent clones like Rc...)

Either way, it doesn't make sense to make a special case for `Gc<T>`.

If `copy_nonoverlapping_memory` isn't enough to move it somewhere, then
it's not `Copy`. A special-case shouldn't be arbitrarily created for it
without providing the same thing for user-defined types. That's exactly
the kind of poor design that Rust has been fleeing from.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140618/2a026b0b/attachment.sig>

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Jerry Morrison
In reply to this post by Brian Anderson
Nice analysis!

Over what scope should programmers pick between G?bor's 3 categories?

The "wraparound is desired" category should only occur in narrow parts of
code, like computing a hash. That suits a wraparound-operator better than a
wraparound-type, and certainly better than a compiler switch. And it
doesn't make sense for a type like 'int' that doesn't have a fixed size.

The "wraparound is undesired but performance is critical" category occurs
in the most performance critical bits of code [I'm doubting that all parts
of all Rust programs are performance critical], and programmers need to
make the trade-off over that limited scope. Maybe via operators or types,
but not by a compiler switch over whole compilation units.

That leaves "wraparound is undesired and performance is not critical"
category for everything else. The choice between checked vs. unbounded
sounds like typing.

BigUint is weird: It can underflow but not overflow. When you use its value
in a more bounded way you'll need to bounds-check it then, whether it can
go negative or not. Wouldn't it be easier to discard it than squeeze it
into the wraparound or checked models?


On Wed, Jun 18, 2014 at 11:21 AM, Brian Anderson <banderson at mozilla.com>
wrote:

>
> On 06/18/2014 10:08 AM, G?bor Lehel wrote:
>
>>
>> # Checked math
>>
>> For (2), the standard library offers checked math in the `CheckedAdd`,
>> `CheckedMul` etc. traits, as well as integer types of unbounded size:
>> `BigInt` and `BigUint`. This is good, but it's not enough. The acid test
>> has to be whether for non-performance-critical code, people are actually
>> *using* checked math. If they're not, then we've failed.
>>
>> `CheckedAdd` and co. are important to have for flexibility, but they're
>> far too unwieldy for general use. People aren't going to write
>> `.checked_add(2).unwrap()` when they can write `+ 2`. A more adequate
>> design might be something like this:
>>
>>  * Have traits for all the arithmetic operations for both checking on
>> overflow and for wrapping around on overflow, e.g. `CheckedAdd` (as now),
>> `WrappingAdd`, `CheckedSub`, `WrappingSub`, and so on.
>>
>>  * Offer convenience methods for the Checked traits which perform
>> `unwrap()` automatically.
>>
>>  * Have separate sets of integer types which check for overflow and which
>> wrap around on overflow. Whatever they're called: `CheckedU8`,
>> `checked::u8`, `uc8`, ...
>>
>>  * Both sets of types implement all of the Checked* and Wrapping* traits.
>> You can use explicit calls to get either behavior with either types.
>>
>>  * The checked types use the Checked traits to implement the operator
>> overloads (`Add`, Mul`, etc.), while the wrapping types use the Wrapping
>> traits to implement them. In other words, the difference between the types
>> is (probably only) in the behavior of the operators.
>>
>>  * `BigInt` also implements all of the Wrapping and Checked traits:
>> because overflow never happens, it can claim to do anything if it "does
>> happen". `BigUint` implements all of them except for the Wrapping traits
>> which may underflow, such as `WrappingSub`, because it has nowhere to wrap
>> around to.
>>
>> Another option would be to have just one set of types but two sets of
>> operators, like Swift does. I think that would work as well, or even
>> better, but we've been avoiding having any operators which aren't familiar
>> from C.
>>
>
> The general flavor of this proposal w/r/t checked arithmetic sounds pretty
> reasonable to me, and we can probably make progress on this now. I
> particularly think that having checked types that use operator overloading
> is important for ergonomics.
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev
>



--
   Jerry
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140619/f8a30925/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Daniel Micay
On 19/06/14 03:05 AM, Jerry Morrison wrote:
>
> BigUint is weird: It can underflow but not overflow. When you use its
> value in a more bounded way you'll need to bounds-check it then, whether
> it can go negative or not. Wouldn't it be easier to discard it than
> squeeze it into the wraparound or checked models?

I don't think we should have a big unsigned integer. It's not something
I've seen other big integer libraries do.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140619/9c87977b/attachment.sig>

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Igor Bukanov
On 19 June 2014 21:03, Daniel Micay <danielmicay at gmail.com> wrote:
> I don't think we should have a big unsigned integer. It's not something
> I've seen other big integer libraries do.

I once spent some time figuring out a bug in a crypto library. It was
caused by writing in a corner case b - a, not a - b. unsigned BigNum
library that faults on a - b when a < b would have trivially caught
that. In addition unsigned BigNum could be more efficient (important
for crypto) as extra sign checks that signed BigNum often use may bear
non-trivial cost.

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Dietrich Epp
It?s a mistake to write crypto using general-purpose big number libraries.  You usually want crypto code to protect against timing attacks, for example, and your average big number library aims for performance; the two goals are at odds.

On Jun 19, 2014, at 10:04 PM, Igor Bukanov <igor at mir2.org> wrote:

> On 19 June 2014 21:03, Daniel Micay <danielmicay at gmail.com> wrote:
>> I don't think we should have a big unsigned integer. It's not something
>> I've seen other big integer libraries do.
>
> I once spent some time figuring out a bug in a crypto library. It was
> caused by writing in a corner case b - a, not a - b. unsigned BigNum
> library that faults on a - b when a < b would have trivially caught
> that. In addition unsigned BigNum could be more efficient (important
> for crypto) as extra sign checks that signed BigNum often use may bear
> non-trivial cost.
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev


Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Gábor Lehel-2
In reply to this post by Daniel Micay
On Wed, Jun 18, 2014 at 8:20 PM, Daniel Micay <danielmicay at gmail.com> wrote:

> On 18/06/14 01:08 PM, G?bor Lehel wrote:
> > # Exposition
> >
> > We've debated the subject of integer overflow quite a bit, without much
> > apparent progress. Essentially, we've been running in circles around two
> > core facts: wrapping is bad, but checking is slow. The current consensus
> > seems to be to, albeit grudgingly, stick with the status quo.
> >
> > I think we've established that a perfect, one-size-fits-all solution is
> > not possible. But I don't think this means that we're out of options, or
> > have no room for improvement. I think there are several imperfect,
> > partial solutions we could pursue, to address the various use cases in a
> > divide-and-conquer fashion.
> >
> > This is not a formal RFC, more of a grab bag of thoughts and ideas.
> >
> > The central consideration has to be the observation that, while wrapping
> > around on overflow is well-supported by hardware, for the large majority
> > of programs, it's the wrong behavior.
> >
> > Basically, programs are just hoping that overflow won't happen. And if
> > it ever does happen, it's going to result in unexpected behavior and
> > bugs. (Including the possibility of security bugs: not all security bugs
> > are memory safety bugs.) This is a step up from C's insanity of
> > undefined behavior for signed overflow, where the compiler assumes that
> > overflow *cannot* happen and even optimizes based on that assumption,
> > but it's still a sad state of affairs. If we're clearing the bar, that's
> > only because it's been buried underground.
> >
> > We can divide programs into three categories. (I'm using "program" in
> > the general sense of "piece of code which does a thing".)
> >
> >  1) Programs where wrapping around on overflow is the desired semantics.
> >
> >  2) Programs where wrapping around on overflow is not the desired
> > semantics, but performance is not critical.
>
> If performance wasn't critical, the program wouldn't be written in Rust.
> The language isn't aimed at use cases where performance isn't a bug
> deal, as it makes many sacrifices to provide the level of control that's
> available.
>

People write GUI frameworks and applications in C++ and even in C. Just
because a language is appropriate for low-level and performance-critical
code doesn't mean it needs to be inappropriate for anything else. I think
Rust is far superior as a general-purpose language to most of today's
mainstream languages.

And even in applications where some parts are performance-critical, many
parts may not be. I expect the ratios may be tilted differently for Rust
code, but not the fundamental pattern to be different.


>
> >  3) Programs where wrapping around on overflow is not the desired
> > semantics and performance is critical.
> >
> > Programs in (1) are well-served by the language and libraries as they
> > are, and there's not much to do except to avoid regressing.
> >
> > Programs in (2) and (3) are not as well-served.
> >
> >
> > # Checked math
> >
> > For (2), the standard library offers checked math in the `CheckedAdd`,
> > `CheckedMul` etc. traits, as well as integer types of unbounded size:
> > `BigInt` and `BigUint`. This is good, but it's not enough. The acid test
> > has to be whether for non-performance-critical code, people are actually
> > *using* checked math. If they're not, then we've failed.
> >
> > `CheckedAdd` and co. are important to have for flexibility, but they're
> > far too unwieldy for general use. People aren't going to write
> > `.checked_add(2).unwrap()` when they can write `+ 2`. A more adequate
> > design might be something like this:
> >
> >  * Have traits for all the arithmetic operations for both checking on
> > overflow and for wrapping around on overflow, e.g. `CheckedAdd` (as
> > now), `WrappingAdd`, `CheckedSub`, `WrappingSub`, and so on.
> >
> >  * Offer convenience methods for the Checked traits which perform
> > `unwrap()` automatically.
> >
> >  * Have separate sets of integer types which check for overflow and
> > which wrap around on overflow. Whatever they're called: `CheckedU8`,
> > `checked::u8`, `uc8`, ...
> >
> >  * Both sets of types implement all of the Checked* and Wrapping*
> > traits. You can use explicit calls to get either behavior with either
> types.
> >
> >  * The checked types use the Checked traits to implement the operator
> > overloads (`Add`, Mul`, etc.), while the wrapping types use the Wrapping
> > traits to implement them. In other words, the difference between the
> > types is (probably only) in the behavior of the operators.
> >
> >  * `BigInt` also implements all of the Wrapping and Checked traits:
> > because overflow never happens, it can claim to do anything if it "does
> > happen". `BigUint` implements all of them except for the Wrapping traits
> > which may underflow, such as `WrappingSub`, because it has nowhere to
> > wrap around to.
> >
> > Another option would be to have just one set of types but two sets of
> > operators, like Swift does. I think that would work as well, or even
> > better, but we've been avoiding having any operators which aren't
> > familiar from C.
> >
> >
> > #  Unbounded integers
> >
> > While checked math helps catch instances of overflow and prevent
> > misbehaviors and bugs, many programs would prefer integer types which do
> > the right thing and don't overflow in the first place. For this, again,
> > we currently have `BigInt` and `BigUint`. There's one problem with
> > these: because they may allocate, they no longer `Copy`, which means
> > that they can't be just drop-in replacements for the fixed-size types.
> >
> >
> > To partially address this, once we have tracing GC, and if we manage to
> > make `Gc<T>: Copy`, we should add unbounded `Integer` (as in Haskell)
> > and `Natural` types which internally use `Gc`, and so are also `Copy`.
> > (In exchange, they wouldn't be `Send`, but that's far less pervasive.)
> > These would (again, asides from `Send`) look and feel just like the
> > built-in fixed-size types, while having the semantics of actual
> > mathematical integers, resp. naturals (up to resource exhaustion of
> > course). They would be ideal for code which is not performance critical
> > and doesn't mind incurring, or already uses, garbage collection. For
> > those cases, you wouldn't have to think about the tradeoffs, or make
> > difficult choices: `Integer` is what you use.
>
> A tracing garbage collector for Rust is a possibility but not a
> certainty. I don't think it would make sense to have `Gc<T>` support
> `Copy` but have it left out for `Rc<T>`. The fact that an arbitrary
> compiler decision like that would determine the most convenient type is
> a great reason to avoid making that arbitrary choice.
>
> There's no opportunity for cycles in integers, and `Rc<T>` will be
> faster along with using far less memory. It doesn't have the overhead
> associated with reference counting in other languages due to being
> task-local (not atomic) and much of the reference counting is elided by
> move semantics / borrows.
>
> With the help of sized deallocation, Rust can have an incredibly fast
> allocator implementation. Since `Rc<T>` is task-local, it also doesn't
> need to be using the same allocator entry point as sendable types. It
> can make use of a thread-local allocator with less complexity and
> overhead, although this could also be available on an opt-in basis for
> sendable types by changing the allocator parameter from the default.
>
> > One concern with this would be the possibility of programs incurring GC
> > accidentally by using these types. There's several ways to deal with
> this:
> >
> >  * Note the fact that they use GC prominently in the documentation.
> >
> >  * Make sure the No-GC lint catches any use of them.
> >
> >  * Offer a "no GC in this task" mode which fails the task if GC
> > allocation is invoked, to catch mistakes at runtime.
> >
> > I think these would be more than adequate to address the concern.
>
> I don't think encouraging tracing garbage collection is appropriate for
> a language designed around avoiding it. It would be fine to have it as a
> choice if it never gets in the way, but it shouldn't be promoted as a
> default.
>

The idea is to pick the low-hanging fruit. For programs that use garbage
collection, we can offer an integer type that requires neither ergonomic
nor semantic compromises. So let's.


>
> > # Between a rock and a hard place
> >
> > Having dispatched the "easy" cases above, for category #3 we're left
> > between the rock (wraparound on overflow is wrong) and the hard place
> > (checking for overflow is slow).
> >
> > Even here, we may have options.
> >
> > An observation:
> >
> >  * We are adamantly opposed to compiler switches to turn off array
> > bounds checking, because we are unwilling to compromise memory safety.
> >
> >  * We are relatively unbothered by unchecked arithmetic, because it
> > *doesn't* compromise memory safety.
> >
> > Taking these together, I think we should at least be less than adamantly
> > opposed to compiler switches for enabling or disabling checked
> arithmetic.
>
> I think compiler switches or attributes enabling a different dialect of
> the language are a bad idea as a whole. Code from libraries is directly
> mixed into other crates, so changing the semantics of the language is
> inherently broken.
>

Even if checked arithmetic is only turned on for testing/debugging and not
in production code, it's still a strict improvement over the status quo.
Under the status quo, except where wraparound is the intended semantics,
overflow is silently wrong 100% of the time. With the alternative, that
percentage is smaller.


>
> > Consider the status quo. People use integer types which wrap on
> > overflow. If they ever do overflow, it means misbehaviors and bugs. If
> > we had a compiler flag to turn on checked arithmetic, even if it were
> > only used a few times in testing, it would be a strict improvement: more
> > bugs would be caught with less effort.
> >
> > But we clearly can't just add this flag for existing types, because
> > they're well-defined to wrap around on overflow, and some programs
> > (category #1) rely on this. So we need to have separate types.
> >
> > One option is therefore to just define this set of types as failing the
> > task on overflow if checked arithmetic is enabled, and to wrap around if
> > it's disabled. But it doesn't necessarily make sense to specify
> > wraparound in the latter case, given that programs are not supposed to
> > depend on it: they may be compiled with either flag, and should avoid
> > overflow.
> >
> > Another observation:
> >
> >  * Undefined behavior is anathema to the safe subset of the language.
> > That would mean that it's not safe.
> >
> >  * But *unspecified results* are maybe not so bad. We might already have
> > them for bit-shifts. (Question for the audience: do we?)
> >
> > If unspecified results are acceptable, then we could instead say that
> > these types fail on overflow if checked arithmetic is enabled, and have
> > unspecified results if it isn't. But saying they wrap around is fine as
> > well.
> >
> > This way, we can put off the choice between the rock and the hard place
> > from program-writing time to compile time, at least.
> >
> >
> > # Defaults
> >
> > Even if we provide the various options from above, from the perspective
> > of what types people end up using, defaults are very important.
> >
> > There's two kinds of defaults:
> >
> > * The de jure default, inferred by the type system in the absence of
> > other information, which used to be `int`. Thankfully, we're removing
> this.
> >
> > * The de facto, cultural default. For instance, if there is a type
> > called "int", most people will use it without thinking.
> >
> > The latter question is still something we need to think about. Should we
> > have a clear cultural default? Or should we force people to explicitly
> > choose between checked and wrapping arithmetic?
> >
> > For the most part, this boils down to:
> >
> >  * If `int` is checked, the default is slow
> >
> >  * If `int` wraps, the default is wrong
> >
> >  * If there is no `int`, people are confused
> >
> > Regarding the first, we seem to be living in deathly fear of someone
> > naively writing an arithmetic benchmark in Rust, putting it up on the
> > internet, and saying, "Look: Rust is slow". This is not an unrealistic
> > scenario, sadly. The question is whether we'd rather have more programs
> > be accidentally incorrect in order to avoid bad publicity from
> > benchmarks being accidentally slow.
> >
> > Regarding the third, even if the only types we have are `intc`, `intw`,
> > `ic8`, `iw8`, and so on, we *still* can't entirely escape creating a
> > cultural default, because we still need to choose types for functions in
> > the standard library and for built-in operations like array indexing.
> > Then the path of least resistance for any given program will be to use
> > the same types.
> >
> > There's one thing that might help resolve this conundrum, which is if we
> > consider the previously-described scheme with compiler flags to control
> > checked arithmetic to be acceptable. In that case, I think those types
> > would be the clear choice to be the de facto defaults. Then we would
> have:
> >
> >  * `i8`, `u8` .. `i64`, `u64`, `int`, and `uint` types, which fail the
> > task on overflow if checked arithmetic is turned on, and either wrap
> > around or have an unspecified result if it's off
> >
> >  * a corresponding set of types somewhere in the standard library, which
> > wrap around no matter what
> >
> >  * and another set of corresponding types, which are checked no matter
> what
> >
> >
> > -G?bor
>
>
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140620/56baaca3/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Gábor Lehel-2
In reply to this post by Gregory Maxwell
On Wed, Jun 18, 2014 at 10:05 PM, Gregory Maxwell <gmaxwell at gmail.com>
wrote:

> On Wed, Jun 18, 2014 at 10:08 AM, G?bor Lehel <glaebhoerl at gmail.com>
> wrote:
> > memory safety bugs.) This is a step up from C's insanity of undefined
> > behavior for signed overflow, where the compiler assumes that overflow
> > *cannot* happen and even optimizes based on that assumption, but it's
> still
> > a sad state of affairs.
>
> C's behavior is not without an advantage.  It means that every
> operation on signed values in C has an implicit latent assertion for
> analysis tools:  If wrapping can happen in operation the program is
> wrong, end of story.  This means you can use existing static and
> dynamic analysis tools while testing and have a zero false positive
> rate? not just on your own code but on any third party code you're
> depending on too.
>
> In languages like rust where signed overflow is defined, no such
> promises exists? signed overflow at runtime might be perfectly valid
> behavior, and so analysis and testing require more work to produce
> useful results.  You might impose a standard on your own code that
> requires that all valid signed overflow must be annotated in some
> manner, but this does nothing for third party code (including the
> standard libraries).
>
> The value here persists even when there is normally no checking at
> runtime, because the tools can still be run sometimes? which is less
> of a promise than always on runtime checking but it also has no
> runtime cost.
>
> So I think there would be a value in rust of having types for which
> wrap is communicated by the developer as being invalid, even if it
> were not normally checked at runtime. Being able to switch between
> safety levels is not generally the rust way? or so it seems to me? and
> may not be justifiably in cases where the risk vs cost ratio is
> especially high (e.g. bounds checking on memory)... but I think it's
> better than not having the safety facility at all.
>
> The fact that C can optimize non-overflow is also fairly useful in
> proving loop bounds and allowing the autovectorization to work.  I've
> certantly had signal processing codebases where this made a
> difference, but I'm not sure if the same communication to the
> optimizer might not be available in other ways in rust.
>


You seem to be making the same arguments that I did in the "Between a rock
and a hard place" section. Is that intentional?


>
> > `CheckedAdd` and co. are important to have for flexibility, but they're
> far
> > too unwieldy for general use. People aren't going to write
> > `.checked_add(2).unwrap()` when they can write `+ 2`. A more adequate
> design
> > might be something like this:
>
> Not only does friction like that discourage use? it also gets in the
> way of people switching behaviors between testing and production when
> performance considerations really do preclude always on testing.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140620/7e8783ee/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Gábor Lehel-2
In reply to this post by Daniel Micay
On Wed, Jun 18, 2014 at 10:19 PM, Daniel Micay <danielmicay at gmail.com>
wrote:

> On 18/06/14 03:40 PM, comex wrote:
> > On Wed, Jun 18, 2014 at 1:08 PM, G?bor Lehel <glaebhoerl at gmail.com>
> wrote:
> >> To partially address this, once we have tracing GC, and if we manage to
> make
> >> `Gc<T>: Copy`, we should add unbounded `Integer` (as in Haskell) and
> >> `Natural` types which internally use `Gc`, and so are also `Copy`. (In
> >> exchange, they wouldn't be `Send`, but that's far less pervasive.)
> >
> > Wait, what?  Since when is sharing data between threads an uncommon use
> case?
>
> Data remaining local to the thread it was allocated in is the common
> case. That doesn't mean that sending dynamic allocations to other tasks
> or sharing dynamic allocations is bad. `Rc<T>` is inherently local to a
> thread, so it might as well be using an allocator leveraging that.
>
> > (Personally I think this more points to the unwieldiness of typing
> > .clone() for cheap and potentially frequent clones like Rc...)
>
> Either way, it doesn't make sense to make a special case for `Gc<T>`.
>
> If `copy_nonoverlapping_memory` isn't enough to move it somewhere, then
> it's not `Copy`. A special-case shouldn't be arbitrarily created for it
> without providing the same thing for user-defined types. That's exactly
> the kind of poor design that Rust has been fleeing from.
>

I agree. Sorry if I wasn't clear: I wasn't supposing we might bend the
rules for `Gc<T>`, but that `Gc<T>` might fit them.


>
>
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140620/5b56927e/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Gábor Lehel-2
In reply to this post by Jerry Morrison
On Thu, Jun 19, 2014 at 9:05 AM, Jerry Morrison <jhm456 at gmail.com> wrote:

> Nice analysis!
>
> Over what scope should programmers pick between G?bor's 3 categories?
>
> The "wraparound is desired" category should only occur in narrow parts of
> code, like computing a hash. That suits a wraparound-operator better than a
> wraparound-type, and certainly better than a compiler switch. And it
> doesn't make sense for a type like 'int' that doesn't have a fixed size.
>

I thought hash algorithms were precisely the kind of case where you might
opt for types which were clearly defined as wrapping. Why do you think
using different operators instead would be preferred?


>
> The "wraparound is undesired but performance is critical" category occurs
> in the most performance critical bits of code [I'm doubting that all parts
> of all Rust programs are performance critical], and programmers need to
> make the trade-off over that limited scope. Maybe via operators or types,
> but not by a compiler switch over whole compilation units.
>
> That leaves "wraparound is undesired and performance is not critical"
> category for everything else. The choice between checked vs. unbounded
> sounds like typing.
>
> BigUint is weird: It can underflow but not overflow. When you use its
> value in a more bounded way you'll need to bounds-check it then, whether it
> can go negative or not. Wouldn't it be easier to discard it than squeeze it
> into the wraparound or checked models?
>

Making the unbounded integer types implement the Checking/Wrapping traits
is more for completeness than anything else, I'm not sure whether it has
practical value.

A BigUint/Natural type is not as important as BigInt/Integer, but it can be
nice to have. Haskell only has Integer in the Prelude, but an external
package provides Natural, and there've been proposals to mainline it. It's
useful for function inputs where only nonnegative values make sense. You
could write asserts manually, but you might as well factor them out. And
types are documentation.

The Haskell implementation of Natural is just a newtype over Integer with
added checks, and the same thing might make sense for Rust.


On Wed, Jun 18, 2014 at 11:21 AM, Brian Anderson <banderson at mozilla.com>
wrote:

>
> On 06/18/2014 10:08 AM, G?bor Lehel wrote:
>
>>
>> # Checked math
>>
>> For (2), the standard library offers checked math in the `CheckedAdd`,
>> `CheckedMul` etc. traits, as well as integer types of unbounded size:
>> `BigInt` and `BigUint`. This is good, but it's not enough. The acid test
>> has to be whether for non-performance-critical code, people are actually
>> *using* checked math. If they're not, then we've failed.
>>
>> `CheckedAdd` and co. are important to have for flexibility, but they're
>> far too unwieldy for general use. People aren't going to write
>> `.checked_add(2).unwrap()` when they can write `+ 2`. A more adequate
>> design might be something like this:
>>
>>  * Have traits for all the arithmetic operations for both checking on
>> overflow and for wrapping around on overflow, e.g. `CheckedAdd` (as now),
>> `WrappingAdd`, `CheckedSub`, `WrappingSub`, and so on.
>>
>>  * Offer convenience methods for the Checked traits which perform
>> `unwrap()` automatically.
>>
>>  * Have separate sets of integer types which check for overflow and which
>> wrap around on overflow. Whatever they're called: `CheckedU8`,
>> `checked::u8`, `uc8`, ...
>>
>>  * Both sets of types implement all of the Checked* and Wrapping* traits.
>> You can use explicit calls to get either behavior with either types.
>>
>>  * The checked types use the Checked traits to implement the operator
>> overloads (`Add`, Mul`, etc.), while the wrapping types use the Wrapping
>> traits to implement them. In other words, the difference between the types
>> is (probably only) in the behavior of the operators.
>>
>>  * `BigInt` also implements all of the Wrapping and Checked traits:
>> because overflow never happens, it can claim to do anything if it "does
>> happen". `BigUint` implements all of them except for the Wrapping traits
>> which may underflow, such as `WrappingSub`, because it has nowhere to wrap
>> around to.
>>
>> Another option would be to have just one set of types but two sets of
>> operators, like Swift does. I think that would work as well, or even
>> better, but we've been avoiding having any operators which aren't familiar
>> from C.
>>
>
> The general flavor of this proposal w/r/t checked arithmetic sounds pretty
> reasonable to me, and we can probably make progress on this now. I
> particularly think that having checked types that use operator overloading
> is important for ergonomics.
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev
>



--
   Jerry

>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140620/7bcdb534/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Jerry Morrison
On Fri, Jun 20, 2014 at 2:07 PM, G?bor Lehel <glaebhoerl at gmail.com> wrote:

>
>
>
> On Thu, Jun 19, 2014 at 9:05 AM, Jerry Morrison <jhm456 at gmail.com> wrote:
>
>> Nice analysis!
>>
>> Over what scope should programmers pick between G?bor's 3 categories?
>>
>> The "wraparound is desired" category should only occur in narrow parts of
>> code, like computing a hash. That suits a wraparound-operator better than a
>> wraparound-type, and certainly better than a compiler switch. And it
>> doesn't make sense for a type like 'int' that doesn't have a fixed size.
>>
>
> I thought hash algorithms were precisely the kind of case where you might
> opt for types which were clearly defined as wrapping. Why do you think
> using different operators instead would be preferred?
>

Considering a hashing or CRC example, the code reads a bunch of
non-wraparound values, mashes them together using wraparound arithmetic,
then uses the result in a way that does not mean to wrap around at the
integer size.

It's workable to convert inputs to wraparound types and use
wraparound accumulators, then convert the result to a non-wraparound type.
But using wraparound operators seems simpler, more visible, and less
error-prone. E.g. it'd be a mistake if the hash function returned a
wraparound type, which gets assigned with type inference, and so downstream
operations wrap around.


>
>>
>> The "wraparound is undesired but performance is critical" category occurs
>> in the most performance critical bits of code [I'm doubting that all parts
>> of all Rust programs are performance critical], and programmers need to
>> make the trade-off over that limited scope. Maybe via operators or types,
>> but not by a compiler switch over whole compilation units.
>>
>> That leaves "wraparound is undesired and performance is not critical"
>> category for everything else. The choice between checked vs. unbounded
>> sounds like typing.
>>
>> BigUint is weird: It can underflow but not overflow. When you use its
>> value in a more bounded way you'll need to bounds-check it then, whether it
>> can go negative or not. Wouldn't it be easier to discard it than squeeze it
>> into the wraparound or checked models?
>>
>
> Making the unbounded integer types implement the Checking/Wrapping traits
> is more for completeness than anything else, I'm not sure whether it has
> practical value.
>
> A BigUint/Natural type is not as important as BigInt/Integer, but it can
> be nice to have. Haskell only has Integer in the Prelude, but an external
> package provides Natural, and there've been proposals to mainline it. It's
> useful for function inputs where only nonnegative values make sense. You
> could write asserts manually, but you might as well factor them out. And
> types are documentation.
>
> The Haskell implementation of Natural is just a newtype over Integer with
> added checks, and the same thing might make sense for Rust.
>

I see. Good points.


>
> On Wed, Jun 18, 2014 at 11:21 AM, Brian Anderson <banderson at mozilla.com>
> wrote:
>
>>
>> On 06/18/2014 10:08 AM, G?bor Lehel wrote:
>>
>>>
>>> # Checked math
>>>
>>> For (2), the standard library offers checked math in the `CheckedAdd`,
>>> `CheckedMul` etc. traits, as well as integer types of unbounded size:
>>> `BigInt` and `BigUint`. This is good, but it's not enough. The acid test
>>> has to be whether for non-performance-critical code, people are actually
>>> *using* checked math. If they're not, then we've failed.
>>>
>>> `CheckedAdd` and co. are important to have for flexibility, but they're
>>> far too unwieldy for general use. People aren't going to write
>>> `.checked_add(2).unwrap()` when they can write `+ 2`. A more adequate
>>> design might be something like this:
>>>
>>>  * Have traits for all the arithmetic operations for both checking on
>>> overflow and for wrapping around on overflow, e.g. `CheckedAdd` (as now),
>>> `WrappingAdd`, `CheckedSub`, `WrappingSub`, and so on.
>>>
>>>  * Offer convenience methods for the Checked traits which perform
>>> `unwrap()` automatically.
>>>
>>>  * Have separate sets of integer types which check for overflow and
>>> which wrap around on overflow. Whatever they're called: `CheckedU8`,
>>> `checked::u8`, `uc8`, ...
>>>
>>>  * Both sets of types implement all of the Checked* and Wrapping*
>>> traits. You can use explicit calls to get either behavior with either types.
>>>
>>>  * The checked types use the Checked traits to implement the operator
>>> overloads (`Add`, Mul`, etc.), while the wrapping types use the Wrapping
>>> traits to implement them. In other words, the difference between the types
>>> is (probably only) in the behavior of the operators.
>>>
>>>  * `BigInt` also implements all of the Wrapping and Checked traits:
>>> because overflow never happens, it can claim to do anything if it "does
>>> happen". `BigUint` implements all of them except for the Wrapping traits
>>> which may underflow, such as `WrappingSub`, because it has nowhere to wrap
>>> around to.
>>>
>>> Another option would be to have just one set of types but two sets of
>>> operators, like Swift does. I think that would work as well, or even
>>> better, but we've been avoiding having any operators which aren't familiar
>>> from C.
>>>
>>
>> The general flavor of this proposal w/r/t checked arithmetic sounds
>> pretty reasonable to me, and we can probably make progress on this now. I
>> particularly think that having checked types that use operator overloading
>> is important for ergonomics.
>>  _______________________________________________
>> Rust-dev mailing list
>> Rust-dev at mozilla.org
>> https://mail.mozilla.org/listinfo/rust-dev
>>
>
>
>
> --
>    Jerry
>
>>
>


--
   Jerry
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140620/90036333/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Gábor Lehel-2
On Sat, Jun 21, 2014 at 1:37 AM, Jerry Morrison <jhm456 at gmail.com> wrote:

>
> On Fri, Jun 20, 2014 at 2:07 PM, G?bor Lehel <glaebhoerl at gmail.com> wrote:
>
>>
>>
>>
>> On Thu, Jun 19, 2014 at 9:05 AM, Jerry Morrison <jhm456 at gmail.com> wrote:
>>
>>> Nice analysis!
>>>
>>> Over what scope should programmers pick between G?bor's 3 categories?
>>>
>>> The "wraparound is desired" category should only occur in narrow parts
>>> of code, like computing a hash. That suits a wraparound-operator better
>>> than a wraparound-type, and certainly better than a compiler switch. And it
>>> doesn't make sense for a type like 'int' that doesn't have a fixed size.
>>>
>>
>> I thought hash algorithms were precisely the kind of case where you might
>> opt for types which were clearly defined as wrapping. Why do you think
>> using different operators instead would be preferred?
>>
>
> Considering a hashing or CRC example, the code reads a bunch of
> non-wraparound values, mashes them together using wraparound arithmetic,
> then uses the result in a way that does not mean to wrap around at the
> integer size.
>
> It's workable to convert inputs to wraparound types and use
> wraparound accumulators, then convert the result to a non-wraparound type.
> But using wraparound operators seems simpler, more visible, and less
> error-prone. E.g. it'd be a mistake if the hash function returned a
> wraparound type, which gets assigned with type inference, and so downstream
> operations wrap around.
>

Yes, the signature of the hash function shouldn't necessarily expose the
implementation's use of wraparound types... though it's not completely
obvious to me. What kind of downstream operations would it make sense to
perform on a hash value anyway? Anything besides further hashing?

I'm only minimally knowledgeable about hashing algorithms, but I would've
thought that casting the inputs to wraparound types at the outset and then
casting the result back at the end would be *less* error prone than making
sure to use the wraparound version for every operation in the function. Is
that wrong? Are there any operations within the body of the hash function
where overflow should be caught?

And if we'd be going with separate operators instead of separate types,
hash functions are a niche enough use case that, in themselves, I don't
think they *warrant* having distinct symbolic operators for the wraparound
operations; they could just use named methods instead.

Hashing is the one that always comes up, but are there any other instances
where wraparound is the desired semantics?




>
>
>>
>>>
>>> The "wraparound is undesired but performance is critical" category
>>> occurs in the most performance critical bits of code [I'm doubting that all
>>> parts of all Rust programs are performance critical], and programmers need
>>> to make the trade-off over that limited scope. Maybe via operators or
>>> types, but not by a compiler switch over whole compilation units.
>>>
>>> That leaves "wraparound is undesired and performance is not critical"
>>> category for everything else. The choice between checked vs. unbounded
>>> sounds like typing.
>>>
>>> BigUint is weird: It can underflow but not overflow. When you use its
>>> value in a more bounded way you'll need to bounds-check it then, whether it
>>> can go negative or not. Wouldn't it be easier to discard it than squeeze it
>>> into the wraparound or checked models?
>>>
>>
>> Making the unbounded integer types implement the Checking/Wrapping traits
>> is more for completeness than anything else, I'm not sure whether it has
>> practical value.
>>
>>  A BigUint/Natural type is not as important as BigInt/Integer, but it can
>> be nice to have. Haskell only has Integer in the Prelude, but an external
>> package provides Natural, and there've been proposals to mainline it. It's
>> useful for function inputs where only nonnegative values make sense. You
>> could write asserts manually, but you might as well factor them out. And
>> types are documentation.
>>
>> The Haskell implementation of Natural is just a newtype over Integer with
>> added checks, and the same thing might make sense for Rust.
>>
>
> I see. Good points.
>
>
>>
>> On Wed, Jun 18, 2014 at 11:21 AM, Brian Anderson <banderson at mozilla.com>
>> wrote:
>>
>>>
>>> On 06/18/2014 10:08 AM, G?bor Lehel wrote:
>>>
>>>>
>>>> # Checked math
>>>>
>>>> For (2), the standard library offers checked math in the `CheckedAdd`,
>>>> `CheckedMul` etc. traits, as well as integer types of unbounded size:
>>>> `BigInt` and `BigUint`. This is good, but it's not enough. The acid test
>>>> has to be whether for non-performance-critical code, people are actually
>>>> *using* checked math. If they're not, then we've failed.
>>>>
>>>> `CheckedAdd` and co. are important to have for flexibility, but they're
>>>> far too unwieldy for general use. People aren't going to write
>>>> `.checked_add(2).unwrap()` when they can write `+ 2`. A more adequate
>>>> design might be something like this:
>>>>
>>>>  * Have traits for all the arithmetic operations for both checking on
>>>> overflow and for wrapping around on overflow, e.g. `CheckedAdd` (as now),
>>>> `WrappingAdd`, `CheckedSub`, `WrappingSub`, and so on.
>>>>
>>>>  * Offer convenience methods for the Checked traits which perform
>>>> `unwrap()` automatically.
>>>>
>>>>  * Have separate sets of integer types which check for overflow and
>>>> which wrap around on overflow. Whatever they're called: `CheckedU8`,
>>>> `checked::u8`, `uc8`, ...
>>>>
>>>>  * Both sets of types implement all of the Checked* and Wrapping*
>>>> traits. You can use explicit calls to get either behavior with either types.
>>>>
>>>>  * The checked types use the Checked traits to implement the operator
>>>> overloads (`Add`, Mul`, etc.), while the wrapping types use the Wrapping
>>>> traits to implement them. In other words, the difference between the types
>>>> is (probably only) in the behavior of the operators.
>>>>
>>>>  * `BigInt` also implements all of the Wrapping and Checked traits:
>>>> because overflow never happens, it can claim to do anything if it "does
>>>> happen". `BigUint` implements all of them except for the Wrapping traits
>>>> which may underflow, such as `WrappingSub`, because it has nowhere to wrap
>>>> around to.
>>>>
>>>> Another option would be to have just one set of types but two sets of
>>>> operators, like Swift does. I think that would work as well, or even
>>>> better, but we've been avoiding having any operators which aren't familiar
>>>> from C.
>>>>
>>>
>>> The general flavor of this proposal w/r/t checked arithmetic sounds
>>> pretty reasonable to me, and we can probably make progress on this now. I
>>> particularly think that having checked types that use operator overloading
>>> is important for ergonomics.
>>>  _______________________________________________
>>> Rust-dev mailing list
>>> Rust-dev at mozilla.org
>>> https://mail.mozilla.org/listinfo/rust-dev
>>>
>>
>>
>>
>> --
>>    Jerry
>>
>>>
>>
>
>
> --
>    Jerry
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140621/0d9d9448/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Jerry Morrison
On Fri, Jun 20, 2014 at 5:36 PM, G?bor Lehel <glaebhoerl at gmail.com> wrote:

>
>
>
> On Sat, Jun 21, 2014 at 1:37 AM, Jerry Morrison <jhm456 at gmail.com> wrote:
>
>>
>> On Fri, Jun 20, 2014 at 2:07 PM, G?bor Lehel <glaebhoerl at gmail.com>
>> wrote:
>>
>>>
>>>
>>>
>>> On Thu, Jun 19, 2014 at 9:05 AM, Jerry Morrison <jhm456 at gmail.com>
>>> wrote:
>>>
>>>> Nice analysis!
>>>>
>>>> Over what scope should programmers pick between G?bor's 3 categories?
>>>>
>>>> The "wraparound is desired" category should only occur in narrow parts
>>>> of code, like computing a hash. That suits a wraparound-operator better
>>>> than a wraparound-type, and certainly better than a compiler switch. And it
>>>> doesn't make sense for a type like 'int' that doesn't have a fixed size.
>>>>
>>>
>>> I thought hash algorithms were precisely the kind of case where you
>>> might opt for types which were clearly defined as wrapping. Why do you
>>> think using different operators instead would be preferred?
>>>
>>
>> Considering a hashing or CRC example, the code reads a bunch of
>> non-wraparound values, mashes them together using wraparound arithmetic,
>> then uses the result in a way that does not mean to wrap around at the
>> integer size.
>>
>> It's workable to convert inputs to wraparound types and use
>> wraparound accumulators, then convert the result to a non-wraparound type.
>> But using wraparound operators seems simpler, more visible, and less
>> error-prone. E.g. it'd be a mistake if the hash function returned a
>> wraparound type, which gets assigned with type inference, and so downstream
>> operations wrap around.
>>
>
> Yes, the signature of the hash function shouldn't necessarily expose the
> implementation's use of wraparound types... though it's not completely
> obvious to me. What kind of downstream operations would it make sense to
> perform on a hash value anyway? Anything besides further hashing?
>
> I'm only minimally knowledgeable about hashing algorithms, but I would've
> thought that casting the inputs to wraparound types at the outset and then
> casting the result back at the end would be *less* error prone than making
> sure to use the wraparound version for every operation in the function. Is
> that wrong? Are there any operations within the body of the hash function
> where overflow should be caught?
>
> And if we'd be going with separate operators instead of separate types,
> hash functions are a niche enough use case that, in themselves, I don't
> think they *warrant* having distinct symbolic operators for the wraparound
> operations; they could just use named methods instead.
>
> Hashing is the one that always comes up, but are there any other instances
> where wraparound is the desired semantics?
>

Here's an example hash function from *Effective Java
<http://www.amazon.com/Effective-Java-2nd-Joshua-Bloch-ebook/dp/B000WJOUPA/ref=sr_1_1?ie=UTF8&qid=1403312109&sr=8-1&keywords=joshua+bloch+effective+java>*
(page
48) following its recipe for writing hash functions by combining the
object's significant fields:

@Override public int hashCode() {

int result = 17;

result = 31 * result + areaCode;

result = 31 * result + prefix;

result = 31 * result + lineNumber;

return result;

}


So using Swift's wraparound operators in Java looks like:

@Override public int hashCode() {

int result = 17;

result = 31 &* result &+ areaCode;

result = 31 &* result &+ prefix;

result = 31 &* result &+ lineNumber;

return result;

}


Alternatively, with a wraparound integer type wint (note that int is
defined to be 32 bits in Java):

@Override public int hashCode() {

wint result = 17;

result = (wint) 31 * result + (wint) areaCode;

result = (wint) 31 * result + (wint) prefix;

result = (wint) 31 * result + (wint) lineNumber;

return (int) result;

}


In this example, it's easier to get the first one right than the second one.

The prototypical use for a hash code is to index into a hash table modulo
the table's current size. It can also be used for debugging, e.g. Java's
default toString() method uses the object's class name and hash, returning
something like "PhoneNumber at 163b91".

Another example of wraparound math is computing a checksum like CRC32.
The checksum value is typically sent over a wire or stored in a storage
medium to cross-check data integrity at the receiving end. After computing
the checksum, you only want to pass it around and compare it.

The only other example that comes to mind is emulating the arithmetic
operations of a target CPU or other hardware.

In other cases of bounded numbers, like ARGB color components, one wants to
deal with overflow, not silently wraparound.

Implementing BigInt can use wraparound math if it can also get the carry
bit.

Yes, these cases are so few that named operators may suffice. That's a bit
less convenient but linguistically simpler than Swift's 5 wraparound
arithmetic operators.



>>
>>>
>>>>
>>>> The "wraparound is undesired but performance is critical" category
>>>> occurs in the most performance critical bits of code [I'm doubting that all
>>>> parts of all Rust programs are performance critical], and programmers need
>>>> to make the trade-off over that limited scope. Maybe via operators or
>>>> types, but not by a compiler switch over whole compilation units.
>>>>
>>>> That leaves "wraparound is undesired and performance is not critical"
>>>> category for everything else. The choice between checked vs. unbounded
>>>> sounds like typing.
>>>>
>>>> BigUint is weird: It can underflow but not overflow. When you use its
>>>> value in a more bounded way you'll need to bounds-check it then, whether it
>>>> can go negative or not. Wouldn't it be easier to discard it than squeeze it
>>>> into the wraparound or checked models?
>>>>
>>>
>>> Making the unbounded integer types implement the Checking/Wrapping
>>> traits is more for completeness than anything else, I'm not sure whether it
>>> has practical value.
>>>
>>>  A BigUint/Natural type is not as important as BigInt/Integer, but it
>>> can be nice to have. Haskell only has Integer in the Prelude, but an
>>> external package provides Natural, and there've been proposals to mainline
>>> it. It's useful for function inputs where only nonnegative values make
>>> sense. You could write asserts manually, but you might as well factor them
>>> out. And types are documentation.
>>>
>>> The Haskell implementation of Natural is just a newtype over Integer
>>> with added checks, and the same thing might make sense for Rust.
>>>
>>
>> I see. Good points.
>>
>>
>>>
>>> On Wed, Jun 18, 2014 at 11:21 AM, Brian Anderson <banderson at mozilla.com>
>>> wrote:
>>>
>>>>
>>>> On 06/18/2014 10:08 AM, G?bor Lehel wrote:
>>>>
>>>>>
>>>>> # Checked math
>>>>>
>>>>> For (2), the standard library offers checked math in the `CheckedAdd`,
>>>>> `CheckedMul` etc. traits, as well as integer types of unbounded size:
>>>>> `BigInt` and `BigUint`. This is good, but it's not enough. The acid test
>>>>> has to be whether for non-performance-critical code, people are actually
>>>>> *using* checked math. If they're not, then we've failed.
>>>>>
>>>>> `CheckedAdd` and co. are important to have for flexibility, but
>>>>> they're far too unwieldy for general use. People aren't going to write
>>>>> `.checked_add(2).unwrap()` when they can write `+ 2`. A more adequate
>>>>> design might be something like this:
>>>>>
>>>>>  * Have traits for all the arithmetic operations for both checking on
>>>>> overflow and for wrapping around on overflow, e.g. `CheckedAdd` (as now),
>>>>> `WrappingAdd`, `CheckedSub`, `WrappingSub`, and so on.
>>>>>
>>>>>  * Offer convenience methods for the Checked traits which perform
>>>>> `unwrap()` automatically.
>>>>>
>>>>>  * Have separate sets of integer types which check for overflow and
>>>>> which wrap around on overflow. Whatever they're called: `CheckedU8`,
>>>>> `checked::u8`, `uc8`, ...
>>>>>
>>>>>  * Both sets of types implement all of the Checked* and Wrapping*
>>>>> traits. You can use explicit calls to get either behavior with either types.
>>>>>
>>>>>  * The checked types use the Checked traits to implement the operator
>>>>> overloads (`Add`, Mul`, etc.), while the wrapping types use the Wrapping
>>>>> traits to implement them. In other words, the difference between the types
>>>>> is (probably only) in the behavior of the operators.
>>>>>
>>>>>  * `BigInt` also implements all of the Wrapping and Checked traits:
>>>>> because overflow never happens, it can claim to do anything if it "does
>>>>> happen". `BigUint` implements all of them except for the Wrapping traits
>>>>> which may underflow, such as `WrappingSub`, because it has nowhere to wrap
>>>>> around to.
>>>>>
>>>>> Another option would be to have just one set of types but two sets of
>>>>> operators, like Swift does. I think that would work as well, or even
>>>>> better, but we've been avoiding having any operators which aren't familiar
>>>>> from C.
>>>>>
>>>>
>>>> The general flavor of this proposal w/r/t checked arithmetic sounds
>>>> pretty reasonable to me, and we can probably make progress on this now. I
>>>> particularly think that having checked types that use operator overloading
>>>> is important for ergonomics.
>>>>  _______________________________________________
>>>> Rust-dev mailing list
>>>> Rust-dev at mozilla.org
>>>> https://mail.mozilla.org/listinfo/rust-dev
>>>>
>>>
>>>
>>>
>>> --
>>>    Jerry
>>>
>>>>
>>>
>>
>>
>> --
>>    Jerry
>>
>
>


--
   Jerry
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140620/5754af0c/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Gregory Maxwell
In reply to this post by Gábor Lehel-2
On Wed, Jun 18, 2014 at 10:08 AM, G?bor Lehel <glaebhoerl at gmail.com> wrote:
> core facts: wrapping is bad, but checking is slow. The current consensus

On this point, has anyone tried changing the emitted code for all i32
operations to add trivial checks, hopefully in a way that llvm can
optimize out when value analysis proves them redundant, which do
something trivial update a per task counter when hit and benchmarked
servo / language benchmark game programs to try to get a sane bound on
how bad the hit is even when the programmers aren't making any effort
to avoid the overhead?

Reply | Threaded
Open this post in threaded view
|

Integer overflow, round -2147483648

Diggory Hardy-2
As far as I am aware, using theorem proving tools[1] to provide limits on value ranges is pretty
hard and often computationally intensive to do in /simple/ code. I've only seen prototype systems
where the user is expected to write full contracts on exactly how every function may modify
every value it could, as well as often providing hints to the prover (especially for loops). So I really
don't think this is going to help much.

[1]: https://en.wikipedia.org/wiki/Interactive_theorem_proving

On Friday 20 Jun 2014 19:20:58 Gregory Maxwell wrote:

> On Wed, Jun 18, 2014 at 10:08 AM, G?bor Lehel <glaebhoerl at gmail.com> wrote:
> > core facts: wrapping is bad, but checking is slow. The current consensus
>
> On this point, has anyone tried changing the emitted code for all i32
> operations to add trivial checks, hopefully in a way that llvm can
> optimize out when value analysis proves them redundant, which do
> something trivial update a per task counter when hit and benchmarked
> servo / language benchmark game programs to try to get a sane bound on
> how bad the hit is even when the programmers aren't making any effort
> to avoid the overhead?
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140621/dad29e51/attachment.html>

1234 ... 9