Ergonomics of wrapping operations

[DanielKeep]

Is there any particular reason (aside from Self == Output not being possible) that Rust doesn’t just do this:

trait Op<RHS> {
    type Output;
    fn op(self, rhs: RHS) -> Output;
    fn op_assign(&mut self, rhs: RHS) where Self: Copy, Self == Output {
        let r = self.op(rhs);
        *self = r;
    }
}

[glaebhoerl]

What I’m concerned about, without dedicated operations, is code like this:

b += 4;

Is that wrapping or non-wrapping? I can’t tell without going to track down the (possibly type-inferred) declaration.

That’s a general tradeoff of monomorphic versus ad-hoc polymorphic (trait-based) code, though, not specific to +/+=.

[aidancully]

First, thank you for taking the argument seriously.

Even with all of the ergonomic issues fixed, though, I’m still uncomfortable with using a newtype to change the fundamental behavior of “+”. I feel like having two variables next to each other both being added, you would expect to get the same behavior. However, if one of them is a Wrapping and the other is a bare type, you won’t.

I think that whether the change to the behavior of “+” should be considered fundamental is domain-dependent. I think that, for crypto, wrapping vs. overflowing + seems to be a fundamental distinction, and you’d want a way to have both operations available at the same time with different names (design idea for that is below): crypto algorithms will usually have to consider the full field of available values, so that behavior on overflow (including whether overflow is allowed) is a core part of crypto design consideration. But for a 16-bit current-time-in-milliseconds, we’d interpret a + b as “what will the time be b milliseconds after time a?” There is, I think, little-to-no fundamental difference between that and, on Unix, time() + 10, even though time()-values on Unix should use checked semantics instead of wrapping. (There is, however, a semantic distinction between time_t (for the LHS) and time_diff_t (for the RHS).)

[example of making numerical operations semantics explicit. using this would, I’m sure, want the casting problem I mentioned earlier to have a better solution. but this idea makes it even more explicit that overflowing vs. wrapping is considered than a + b vs. a.wrapping_add(b) do.]

#[derive(Copy)]
struct CryptoNum<T: Int> CryptoNum(T);
trait CryptoAdd {
  fn overflowing_add(self, rhs: Self) -> Self;
  fn wrapping_add(self, rhs: Self) -> Self;
}
impl<T: Int> CryptoAdd for CryptoNum<T> { ... }

[lfairy]

One solution, which I don’t think anyone’s mentioned yet, is using a syntax extension. We can expose a macro (let’s say, wrapping!()) which desugars arithmetic operations to their wrapping counterparts.

For example, this code:

wrapping! {
    let x = y + z * w;
}

would expand to

{
    use std::num::wrapping::WrappingOps;
    let x = y.wrapping_add(z.wrapping_mul(w));
}

This is a simple AST transform, and can be implemented as a library on crates.io.

The only downside I see is that syntax extensions aren’t stable yet, but we can work around this issue by implementing it in libsyntax itself.

[John_Nagle]

Perhaps trying to do this through the type system is overcomplicating the problem. This is really a numerical problem, not a linguistic problem. What you want is to reduce a numerical result by some modulus. The “%” operator is ready and willing to do that job. That’s well-understood and already part of the language. It’s just a performance issue to do it that way.

So just add an optimization for the “%” operator for unsigned operands where the modulus is a constant power of 2, and especially for powers of 256*(2^N), which, of course, are the word sizes for 8, 16, 32, and 64 bit unsigned arithmetic. No new syntax. It just works. Thank you.

[dhardy]

@John_Nagle there are three problems with that: it requires carrying extra precision (including potentially negative numbers when doing unsigned arithmetic), it requires deferring the overflow check, and % isn’t really a “modulus” operator.

[llogiq]

I tend to disagree here: This is not about the possibility of wrapping operations, but about the ergonomics. Requiring users to write (a + b) % 4294967296 (which either would require a –hopefully optimizable– cast to u64/i64 or be outright illegal) is highly unergonomic.

That said, I suspect apart from security-related work, most people will either use wrapping operations or checked operations throughout their code, with scarce occurrences of the other way. I for one would not use wrapping operations unless I explicitly need them.

[John_Nagle]

Modular arithmetic at word sizes is more of a machine artifact than a desirable behavior. There are a few common use cases, TCP sequence numbers, checksums, cryptographic algorithms, and big-number arithmetic being the classic ones.

The semantics of modular subtraction can be expressed as (a + k - b) % k, where k is the maximum unsigned value + 1. This is optimizable, numerically unambiguous, and independent of the machine architecture. (Admittedly you’re not likely to encounter a 36-bit CPU any more, although Unisys still makes some 36-bit and 48- bit machines.)

[lfairy]

One solution, which I don’t think anyone’s mentioned yet, is using a syntax extension. We can expose a macro (let’s say, wrapping!()) which desugars arithmetic operations to their wrapping counterparts.

I’ve implemented this solution here: https://github.com/lfairy/wrapping_macros

It handles binary + - * correctly, but doesn’t deal with unary minus (#1). That problem could be fixed by re-introducing the WrappingOps trait, or at least adding a wrapping_neg method.

EDIT: I just realized we can translate -x to x.wrapping_mul(-1) instead. This side-steps the ambiguity problem because the literal is now on the right-hand side. I’ll try this solution tomorrow.

EDIT #2: Since -1 is no longer a valid unsigned integer, I switched to x.wrapping_mul(!0) instead which has an identical bit pattern.

[nikomatsakis]

I certainly considered macros – they offer a similar trade-off to #[wrapping]. One concern I had is that you wind up reproducing the expr grammar in your macro if you want to support all kinds of expressions (e.g., foo.bar(X::Y(3 + y)) + z and so forth).

[nikomatsakis]

Ah, I see you used a syntax extension rather than macro-rules. That is also an option but of course not currently stable. =)

[ferris]

Hey there, I notice this is listed as “ideas (deprecated)”, is this because the discussion is old or is there updated information about the topic? I for one am quite interested in having better ergonomics for wrapping arithmetic. The proposal I like most in this thread is the addition of sugared operators a la Swift, as it seems like it would be the least-intrusive way to improve the situation.

With the Wrapping type as it is now, I feel like I should just be able to replace all of my i32's on my struct with Wrapping<i32>'s and bang, now all my arithmetic wraps and it’s no problem. But of course, since that requires all my code that interacts with the struct to now also use Wrapping types, this is pretty painful.

Like the crypto and emulator projects mentioned above, I also have a project (emulator) that relies on wrapping arithmetic to function properly across a fairly large piece of code. Currently I simply ignore the problem and only run release builds, and clearly this is not ideal. I’ve started to fix it, but it’s pretty painful to work with the wrapping stuff as it is now. The best option I have currently is to follow @DaGenix’s example and replace all my arithmetic with wrapping_add etc calls, which will work, but makes the code much less readable IMHO.

Is this discussion simply over, shelved, or what? I’d really like to hear what the current thoughts are on the matter.

[stebalien]

The ideas category it self is deprecated, not necessarily this topic.

[ferris]

aha, I see that now. Thanks for the clarification consider this a friendly bump for the topic then

[vadimcn]

Yeah, the current recommendation is to either use wrapping_xxx methods or the Wrapping<T> types, whichever is more convenient.

With the Wrapping type as it is now, I feel like I should just be able to replace all of my i32’s on my struct with Wrapping<i32>'s and bang, now all my arithmetic wraps and it’s no problem. But of course, since that requires all my code that interacts with the struct to now also use Wrapping types, this is pretty painful.

I am curious to find out why all of your code would need to switch to Wrapping. I’d have thought that you’d only need to deal with Wrapping at the interface boundary?

[glaebhoerl]

FWIW, one of the major pain-points with Wrapping<T> is that heterogeneous operations - e.g. T + Wrapping<T> - are not permitted. This is because it’s not obvious whether such an operation should wrap or not. In different words, one of the operands essentially needs to be casted before performing the operation, and it’s not clear which one.

I’m now kind of leaning towards saying that Wrapping<T> should “win”: in other words, that we should have impl Add<u32> for Wrapping<u32> { type Output = Wrapping<u32>; ... } (and vice versa), and likewise for the other types. The intuition is this: the reason why “plain” T (e.g. u32) panics on over/underflow is not because this is well-known to be the behavior that’s desired by users of u32; rather, the reason is precisely that we don’t have any information about the programmer’s intent, so our only reasonable option is to signal the unhandled circumstance by panicking. (This is also underscored by the fact that panicking only happens in debug builds: if we knew that panicking is what the programmer explicitly wants, then we would do it always.)

Now in the case of u32 + Wrapping<u32>, if we think of it as a unification problem, then “no available information” unifies with “it should wrap” to yield “it should wrap”.

(Incidentally, for completeness’s sake, we should presumably also have Saturating<T>, Checked<T>, and Overflowing<T> for the other possible policies, with analogous impls. And see also.)

[llogiq]

I disagree. This would amount to making one Wrapping value “infect” all surrounding operations with non-wrapping values; and sometimes wrapping can lead to counter-intuitive results. Therefore if we allow it, the Output type should be u32. One can always add another Wrapping(…) around it to ensure the result wraps.

[glaebhoerl]

Hmm. The idea was actually to protect against accidents by giving a type error if u32 was expected but a Wrapping<u32> resulted (i.e., the scenario where I wrote T + Wrapping<T> but didn’t actually want it to wrap). I’m not sure how that squares with the “unification of information” idea, actually. I can see how it might backfire when the result type is inferred instead of checked.

One place where there aren’t questions around the choice of result type, though, is AddAssign (+=) and family. I think it would be completely, unambiguously fine to have impl AddAssign<u32> for Wrapping<u32> as a wrapping operation. (Right now it seems we don’t even have AddAssign<Wrapping<u32>> for Wrapping<u32>!)

[rkjnsn]

I worry that this could get rather confusing for more complicated expressions. For example, even just u32 + u32 + Wrapping<u32> would yield a Wrapping<u32>, but could still panic if the first addition overflowed. Maybe that’s what is desired, but it seems more likely that it isn’t.

[nikomatsakis]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.