Where is std::num::Saturating? (Going to pre-RFC!)

libs
21

Or completely identical, using the add_with_carry_using_overflowing from my previous godbolt: Compiler Explorer

1 Like
22

Note that this version produces some fairly garbage assembly for the adc() function in -Oz; you should use a bool for the carry like @scottmcm did. (See also why I really think this should be an intrinsic...). https://godbolt.org/z/WoWKK1

(In -Oz rustc fails to inline any of these for whatever reason, though that's not included in the example.)

23

Alright, so if I didn't miss it, there should be all the methods for all the cases – checked, wrapping and overflow –, but so far only Wrapping exists and the two remaining cases could be possibly added to make this corner of std::num complete. And it seems there are good uses for it.

I think it is worth making an RFC, isn't it?

24

While for unsigned integers those give access to the carry flag, for signed integers they give access to the overflow flag. So for example to access the carry bit in i64 addition, you'd need to first cast the integers to u64, then use overflowing_add, and then cast the sum back to i64.

2 Likes
25

there is an RFC for this (widening_mul) widening_mul by strake · Pull Request #2417 · rust-lang/rfcs · GitHub.

26

Yup, mentioned that in post #11 above :upside_down_face:

27

Because it seems that more people would like to close the gap, I prepared a pre-RFC. Thanks for your comments in advance.

  • Feature Name: missing_integer_wrappers
  • Start Date: 2020-10-10
  • RFC PR:
  • Rust Issue:

Summary

This RFC proposes the addition of Saturating, Overflowing and Checked types in the std::num module.

Motivation

For convenience, the std::num module provides a Wrapping type. This type improves ergonomy of wrapping arithmetics. However, the remaining operation modes (saturating, overflowing and checked) lack similar support. This RFC suggests to close this gap and make this part of the std::num module complete.

According to this discussion on Rust Internals, closing the gap would be appreciated. For instance, checked operations are considered essential for secure implementations of many types of cryptography.

Guide-level explanation

The default semantics of integer arithmetic operations consider an overflow to be an error and panics in debug mode. Built-in integer types provide methods for altenative semantics, which provide better control of the outcome. For instance wrapping_add performs wrapping (modular) addition, or checked_add returns an Option with the None variant when the result overflows.

However, using these methods can be cumbersome and worse readable than arithmetic operators. The Wrapping, Saturating, Overflowing and Checked types allow natural use of arithmetic operators with alternative semantics (as indicated by their names):

let value = (Checked(u32::MAX) + Checked(2)) / Checked(8);
// The computation encountered an overflow, so the overall result is None
assert_eq!(None, value.0);

Reference-level explanation

The Saturating<T> can be almost identical to the existing Wrapping<T> type, it just has to delegate to T::saturating_* methods instead of T::wrapping_*.

The Checked<T> type wraps an Option<T> type:

pub struct Checked<T>(pub Option<T>);

It delegates to T::checked_* methods if none operand of the operation is None. If an operand is None or the delegated method invocation returns None, the result wraps None as well.

The Overflowing<T> type wraps (T, bool):

pub Overflowing<T>(pub T, pub bool);

It delegates to T::overflowing_* methods and just wraps their result, hence the bool component tracks whether an overflow occurred.

Drawbacks

It increases the size of the standard library.

Rationale and alternatives

All the types should provide similar user experience and features. Therefore the described design follows closely the existing implementation and avoids proposals that would affect it.

For the Overflowing type an alternative representation could be:

pub Overflowing<T>(pub Result<T, T>);

The Err variant carries the result that overflew. This approach allows leveraging the feature-rich Result type. The disadvantage is the difference from the return type of overflowing_* methods.

It is worth mentioning some features of the Checked type implemented in the checked crate:

  • It implements the From trait as a convenient alternative to Checked(Some(number)).
  • It implements the Deref and DerefMut traits to return a reference to the wrapped Option.
  • It implements binary operators that take a built-in integer as well.

Implementing the From trait seems to be harmless and it should be probably implemented for the Wrapping type anyway. It would provide the same means for wrapping an integer value, regardless of the actual structure of the wrapping type.

Implementing Deref, DerefMut and the binary operators is more questionable as the boundaries between arithmetic modes become less visible. And while it yet works for the Checked type, because the wrapped Option type can't be confused with a numeric type, it is not viable for the Wrapping and Saturating types.

Prior art

Future possibilities

It might be worth implementing macros for a scoped change of the arithmetic mode:

let value = checked! { a + b * foo(x) }.ok().map(|n| overflowing! { n + 1 })?;

The operands in the expressions are wrapped in the appropriate wrapper type. Here the advantage of using the Result type for the Overflowing wrapper are clearly visible.

2 Likes
28

For Checked and Overflowing, I'd be wary of exposing their fields publicly, at least in a first pass. The following is perhaps enough, because I cannot see the usefulness of building a failed Checked or an already overflowed Overflowing.

pub struct Checked<T>(Option<T>);
impl<T> Checked<T> {
    pub fn new(x: T) -> Self { Self(Some(x)) }
    pub fn into_inner(self) -> Option<T> { self.0 }
}

pub struct Overflowing<T>(T, bool);
impl<T> Overflowing<T> {
    pub fn new(x: T) -> Self { Self(x, false) }
    pub fn has_overflowed(&self) -> bool { self.1 }
    pub fn into_inner(self) -> T { self.0 }
}
1 Like
29

With wrapping operations, it makes sense to work consistently with the numbers wrapping every time. It's what you would use when you have worked out that your working should not overflow and do not want to pay the cost of checking for overflow for every operation.

For checked and overflowing operations, the return type is not equal to self, so the wrapper would not be usable as a substitute to the numbers themselves. So I would not call it a wrapper.

For saturating operations, the return type is equal to self, so Saturating could be a wrapper similar to Wrapping. It could arguably be useful for example in a DSP application where overflow could occur and the designer decides to tolerate it: in that case saturation can produce less distortion than wrapping. But that could be kind of a niche usage, and I think it makes more sense for it to be an external crate, at least until there is a reasonable amount of usage.

In general, I do not like the idea of adding features that are somehow similar to other implemented features just for completeness if there isn't a clear use case which makes them worth their maintenance burden.

One wrapper which I think could be useful is a wrapper similar to Wrapping but panicking on every overflow. Basically right now primitives have two behaviors: 1. wrapping, used when debug_assertions are disabled, 2. panicking, used when debug_assertions are enabled. The first usage has a wrapper, but the second usage, which can be useful when overflow is simply a bug and panicking is reasonable, has no wrapper. In the fixed crate, there is an experimental Unwrapped wrapper which I plan to stabilize in the next minor version which does exactly this. (I called it Unwrapped because it is functionally equivalent to using checked operations and unwrapping immediately, and I like that it sounds kind of opposite to Wrapping which wraps automatically.)

30

As I mentioned earlier in this thread, cryptography would benefit greatly from Checked

31

You're right, Checked is quite useful. Maybe I'm missing something; my concern with it is that you cannot use for example ch1 + ch2 + ch3, or ch1 += ch2, so I don't know how that wrapper would be used.

32

I would expect it to be the monadic lift (see Lifting binary operations, e.g. T+T → Option<T> + Option<T> - #8 by scottmcm), so those would be fine, and would just stay None if they're ever None (kinda like a null object pattern).

The particularly interesting thing to me about them is that they should probably be PartialOrd but not Ord -- like in SQL, the None should be neither greater, less, nor equal to zero.

5 Likes
33

Oh, so they could work like floating-point numbers with NaN, where NaN takes over.

2 Likes
34

I hesitated about this point. On the other hand, I don't like much that wrapping.0 works and checked.0 does not. We can't turn the time back and make Wrapping more discreet about its private parts, so what now? Anyway, having a method that returns the inner part with the same name for all the types (including Wrapping) looks good to me. It could be definitely one of the points mentioned in the alternatives and I guess that it is on the same level as implementing the From trait.

35

Could certainly start with just having From and TryFrom for it, and decide later exactly how it should be represented and whether its fields are exposed.

36

I suppose that @scottmcm already explained it much better that I could :wink:

But… I admit that Overflowing seems the least usable to me and I think that nobody in the discussion above missed it or presented a use case for such a type. I added this one in the proposal for mere completeness indeed and I don't intend to defend this idea much, unless someone presents a use case which would defend its usefulness.

37

I was thinking yet about extending this part. The num-traits crate defines traits like CheckedAdd. I think that adding these traits in std could make the implementation of the proposed types easier and make them even more general, so that they could work even for custom numeric types (checked complex numbers, yay!).

Now, a bolder proposal could go further: see the checked! macro above? What if it meant that for instance + would be implemented with CheckedAdd, if available, rather than with just Add? I guess that such an idea has been presented somewhere. But I guess it fits this section of this proposal. However, it needs much polishing. For instance, should the macro require CheckedAdd or could it fall back to Add? There are no doubts with the explicit Checked type. How about nesting? Etc.

38

I've been thinking about writing a library to provide these wrapper types. Of the arithmetic modes provided by std, wrapping and saturating are "trivial" in the sense that the operations are closed over T, with signatures T -> T or T -> T -> T. On the other hand, checked and overflowing lift their results to Option<T> and (T, bool) respectively. Both of these have a monadic structure; in the former case it is already implemented by Rust, so checked operations can be easily composed with the standard combinators. The latter, on the other hand, does not have an existing monad instance, but one can be written easily enough:

pub trait Overflowing<T> : Sized {
    fn map(self, f: impl Fn(T) -> T) -> Self;
    fn and_then(self, f: impl Fn(T) -> Self) -> Self;
}

impl<T> Overflowing<T> for (T, bool) {
    fn map(self, f: impl Fn(T) -> T) -> Self {
        (f(self.0), self.1)
    }
    fn and_then(self, f: impl Fn(T) -> Self) -> Self {
        let res = f(self.0);
        (res.0, self.1 | res.1)
    }
}

pub fn overflowing<T>(x: T) -> (T, bool) {
    (x, false)
}

(playground)

Writing convenience operator overloads on top of these instances is straightforward, although we need newtype wrappers to do so outside the std. But we want those anyway for abstraction purposes, so that's fine.

1 Like
39

For overflowing operations there is also another thing to be careful about. Let's say we're adding i8 values. If we add 127 + 5 + -6, then we have 127 + 5 which overflows to (-124, true), which is followed by (-124, true) + -6 which overflows again to (126, true). Treating the whole list of operations together would have returned (126, false). Which shows that for multiple operations, the overflow flag would indicate a maybe-overflow instead of a definitely-overflow condition. It is very easy to misinterpret (126, true) as a strong indication that the result is not 126.

Contrast this with Checked which would give None. It is true that a smarter ternary add could have returned Some(126), but it is much more difficult to interpret None incorrectly, and it's easier to simply state that None means that some overflow occurred somewhere.

It might be considered a contrived example, but in my code I did find this pattern in some code that can be simplified to:

let (wrapped1, overflow1) = overflowing_op1(value);
let (wrapped2, overflow2) = overflowing_op2(wrapped1);
if some_condition(wrapped2, something) {
    (wrapped2, overflow1)
} else {
    (wrapped2, overflow1 || overflow2)
}

Using an Overflow wrapper that lifts to (T, bool) would have hidden the overflows. Now it could be argued that in such a case you can simply not use the wrapper. But I would be wary of introducing wrappers with caveats when there is no clear use case anyway. This is exactly the kind of thing that makes me skeptical of adding features for completeness without a use case.

1 Like
40

For me, the above example simply demonstrates that the normal associative law of arithmetic
    ((x + y) + z) == (x + (y + z))
does not hold for these proposed operations (though it does for wrapping integer arithmetic as well as unchecked integer arithmetic). That should be considered by, and documented in, the RFC.

1 Like