Checked_ sum() for all types that have both iter::Sum and checked_add()

It would be nice to have iter_over_i32.checked_sum() (and wrapping_sum, saturating_sum, overflowing_sum, unchecked_sum; no need for *_sum_unsigned(), though, as it doesn't make sense).

It is easy enough to implement with try_fold(0, |acc, v| acc.checked_add(*v)), but feels like it should be there.

Thoughts?

2 Likes

I'm concerned about adding tons of methods to the ubiquitous Iterator trait. Maybe a wrapper type with some clever trait implementations could support:

iter().sum::<Checked<u32>>()
2 Likes

std::num::Wrapping already exists for wrapping sums but it doesn't implement Sum<T>, only Sum<Wrapping<T>> (meaning you need to do .map(Wrapping).sum::<Wrapping<u32>>() for example).

However I don't think we'll see a design for the equivalent for checked, overflowing and unchecked sums, at least not soon. Checked and overflowing have return types that make implementing the math operators traits non-trivial. Similarly, unchecked can't implement them because they're safe and unchecked is not (unless you make creating an Unchecked unsafe, but at that point it can't implement Sum). Saturating may be an option though.

1 Like

This was discussed previously, and rejected by the libs-api team: Add `Iterator::checked_{sum, product}` by aDotInTheVoid Β· Pull Request #95485 Β· rust-lang/rust Β· GitHub

Based on that thread, you might consider writing an ACP for num::Checked instead, like there's num::Wrapping instead of Iterator::wrapping_sum.

2 Likes

Although saturating_add may be implemented, it doesn't really mean that there should be a saturating_sum, as its correct implementation would be much more complex than simply iterating with saturating_add.

For example, for the collection [i8::MIN, i8::MIN, i8::MAX, i8::MAX] I would expect saturating_sum to produce βˆ’128 + βˆ’128 + 127 + 127 = βˆ’2 which is within the range and shouldn't saturate. However, iterating with saturating_add would result in 126 because using saturating i8: ((βˆ’128 + βˆ’128) + 127) + 127 = (βˆ’128 + 127) + 127 = βˆ’1 + 127 = 126.

Similarly overflowing_sum would say that the result overflows even if the final result should be within the range; for the example above overflowing_sum with iteration would result in (-2, true) instead of the correct (-2, false). And checked_sum would return None.

That means that the only one that is simple to implement correctly and efficiently for signed primitives is the wrapping case, which is already supported using the Wrapping wrapper.

8 Likes

I think this thread has several reasons which show that my idea is not as good as it first seemed. I appreciate the feedback, and sorry that I didn't find the prior thread in my search.

Regards,

Tim

@softmoth I think checked_sum is great and I implement it as a sealed internal extension trait frequently where I deal with e.g. checked length computations over usize.

It seems like it won't be added to core though (I don't blame them; core should be conservative).

As others have noted, a Checked newtype seems like the way forward there. The checked crate provides an example of how it could be implemented. I really think something like that does belong in core though, as it feels like a pretty noteworthy gap that there's no equivalent newtype to Wrapping (and it seems the libs team is open to it).

3 Likes

Frankly I'd expect (-2, true) from overflowing_sum and i8::MIN from saturating_sum: once overflow/saturation has occurred, I would expect it to be irrecoverable.

2 Likes

Thinking about it I would agree for checked_sum, that is None is meaningful and checked_sum can be very useful.

But in contexts where I've used saturating* and overflowing*, I never had a use case where irrecoverable was useful. Do you have a use case where saturating_sum -> i8::MIN or overflowing_sum -> (-2, true) is actually useful and what you'd expect?

Absolutely if the implementation can recover that's fantastic.. but it would require performing the operation on a larger-size integer, and then there's still the possibility that a large enough sum could overflow that larger integer too: so when should a user expect a saturated/overflowed result and when should they not? Or to flip it around, what does a saturated/overflowed result tell them about their inputs?

I think it's not a good idea to add any library API, no matter how simple it may seem, on hypotheticals before there is an actual concrete use case where the API is used.

For checked_sum @bascule mentioned use cases that show the usefulness of that API. But for saturating_sum, adding a new API for "completeness of API" without an actual case where it would be useful will just make it harder if in the future a clear use case emerges with different requirements.

1 Like

The problem with CheckedU32 is that it would coalesce all overflows into a single None value. In a complex formula it would turn a single overflow into a None result of the whole computation, which is terrible for debugging. I can't imagine the case where it would really be desired behaviour. If you don't want overflows to happen anywhere, then the current behaviour with overflow-checks=true is more sensible, you get a panic exactly where the overflow occurs. In crypto code you will likely want to avoid the panic due to branching, but the same branching would occur inside of CheckedU32 operations, so it's also off the table. And if you want to handle overflow in more complex ways, by returning some special default values or branching on overflow, then the CheckedU32 with its unassuming arithmetic operators is definitely the wrong abstraction, the explicit checked_add calls are much better.

This leaves us with something like cehcked_sum or checked_product, where the fact that overflow occured is important, but the specific place isn't. But it's not worth it to add a newtype just for a single checked_sum method, and wrapping-unwrapping the numbers with a newtype will be more boilerplate than a simple fold call.

1 Like

The issue in my particular cryptographic isn't the branching but the panic, especially when operating on untrusted inputs.

In the RustCrypto project we generally aim for panic-minimal code with the goal of eventually making everything panic-free (once we can statically assert that, anyway). There are several contexts where panic-free code is desirable, like kernels, bootloaders, UEFI, embedded, etc.

The code I linked to earlier as an example is a format decoder/encoder, where checked_sum is used in several functions for summing the lengths of segments of messages. In that application an all-or-nothing result is fine: if it overflows, it overflows and the whole operation is aborted.

2 Likes

This is exactly what NAN does for floating-point, so it's not unreasonable. (Albeit the cost overhead of the checking will still be there for integers, which NANs avoid in floating-point.)

After all, one doesn't have to use it if it has different behaviour from what you want.

Well, arguably NaNs are unreasonable to debug, and their only merit as an error reporting mechanism is that they’re implemented in hardware.

1 Like

Do you think this is a good fit for itertools?

By the way, just keeping an i64 counter for overflows would be enough, as it would need more than 1.8Γ—1019 additions to overflow that counter. That is not going to happen: if you're adding using that many iterations then you need to use your own logic that is robust enough to survive the decades it would require to run.

Sure, for additions... but what about other arithmetic operations eg multiplication or exponentiation? (Granted this thread is about Sum but it would be very odd indeed if the equivalent operations behaved differently)

Unlike Sum, if integer Product overflows it will remain in overflow (except if a zero appears which is simple enough to handle). So overflowing_product needs just one flag for overflow, and saturating_product would require one extra flag to keep the sign of the result.

This is faulty logic. Counter-example:

fn main() {
    let mut x: i64 = 0;
    loop {
        x = x.checked_add(1).expect("this will never overflow")
    }
}
     Running `target/release/playground`
thread 'main' panicked at 'this will never overflow', src/main.rs:4:30
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
4 Likes