Ergonomics of wrapping operations

[nikomatsakis]

@wackywendell

Numeric literals should convert to Wrapping<T> as easily as to T, with the same rules that apply to numeric literals converting to u32, u64, f32, f64.

This could be tricky. There are places that we currently rely on numeric literals being known to be some sort of scalar type -- even if we don't know which one. Some sort of suffix (2w) would work fine. We might also be able to lift those restrictions from type inference; I haven't investigated deeply in a while.

[nikomatsakis]

@rkjnsn

I would still be opposed to this solution, even restricted to functions and blocks. I really don't like the idea of changing code semantics based on attributes. It makes it easy to make mistakes such as copy-pasting code that suddenly has a different meaning, not checking operations that should be checked because they're in a #[wrapping] function and one either forgets or finds it too unergonomic to explicitly use debug-checked operations for the block, etc.

I find this persuasive.

[wackywendell]

@nikomatsakis

This could be tricky. There are places that we currently rely on numeric literals being known to be some sort of scalar type -- even if we don't know which one. Some sort of suffix (2w) would work fine. We might also be able to lift those restrictions from type inference; I haven't investigated deeply in a while.

Mm, that's unfortunate. I'm not too familiar with the internals - what do you mean by "some sort of scalar type"? Would it be possible to make Wrapping<T> a "scalar type", for "scalar types" T?

[nikomatsakis]

@DaGenix

So, I described it as the "wrapocalypse" - but, the end result of all that work is that now Rust-Crypto is much better - if you read through the code, it is explicitly clear which operations wrap and which don't. This is a huge win. But, I think there is too much focus on "how can we make newtypes work" - I don't think they can. wrapping_{add,sub,mul} is not especially ergonomic, but, even in a code base that makes unusually high use of wrapping operations, I'd say that the transition to these operations was a big win. I think the solution to the ergonomic problem is to treat the wrapping ops as distinct ops - give them their own operations ala Swift. It fixes all of the ergonomic issues (in my opinion) while keeping the code clear and not inflicting wrapping math on operations that shouldn't be wrapping just because they happen to be located in a function that is doing lots of wrapping math.

Thanks, I found this very interesting.

[glaebhoerl]

If we want to add wrapping operators +%, -%, *%, etc. and also want to be complete, then we will also want to add assignment versions of those operators: +%=, -%=, *%=, etc. That’s two different axes of new operators! We’d be getting close to lens territory. (Of course, we could also choose to just forsake the desire for completeness.)

[DaGenix]

@tbu

It fixes all these problems for wrapping operations. While wrapping operations certainly are common, I worry that we "close the door" for other operations that should be implemented, e.g. my example from above, if you want to implement one's-complement arithmetic for dealing with IP headers.

My thinking is that non-wrapping and wrapping math are common enough that it would be really good to support them with nice, ergonomic interfaces. Ones-complement / saturating math are rare enough that my thinking is its less important if they aren't quite as ergonomic. At least, that's my thinking which is likely very biased due to working on Rust-Crypto with lots of wrapping math and no ones-complement or saturating math.

[DaGenix]

@aidancully

I think this is the crux of your argument, but I have to somewhat disagree: a type representing an odometer should never use non-wrapping operations. (To make this more targeted to the domains Rust is interested in, instead of odometer, think TimeInMilliseconds: u16, in which you're interested in the difference between two times, but allow that the time can wrap around pretty quickly.) A type-system is for statically declaring what operations make sense against which types of data, so an odometer-reading type should be prevented at the type-level from using non-wrapping operations. Most numbers should never use the wrapping operations, and the type-system should enforce this, too. Crypto is the special case, in that it should support both types of operations at once, and you've used the correct way of representing that (by naming the operations differently, rather than the types).

I understand that this means there are ergonomic issues with converting types between different arithmetic semantics. Those should be solved. It is, IMO, a general problem that Vec[NewType<T>] cannot be safely-and-explicitly casted to Vec[T], and there should be a general solution to that problem.

I shared this point of view until I tried to convert Rust-Crypto to use Wrapping - which I why I didn't contribute to the discussion's regarding creating Wrapping: I agreed, so, I had nothing to add. Doing the work to update Rust-Crypto, however, changed my opinion. It took a while - I tried very hard to make Wrapping work and I couldn't. A big part of it not working were all of the ergonomic issues that have been described here. Fixing those ergonomic issues would go a long way to making Wrapping more usable, although, its not clear to me that all of the issues are fixable. 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 a dedicated operator for wrapping math makes it much clearer what is going on.

Lets say we fixed all of the ergonomic problems and also that we had wrapping ops like Swift - ie: "&+" means "wrapping add". In that case, if Wrapping were defined to only permit the wrapping ops - that would be pretty interesting. In that case, this code would be fine:

let a = Wrapping(0u32);
a &+= 4;

But this would be an error

let a = Wrapping(0u32);
a += 4; // Error - trying to use non-wrapping ops on a Wrapping type

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. So, Wrapping to make sure that you use the right operations sounds pretty interesting to me. Outside of the existing ergonomic issues, though, what I'm also concerned about is how Wrapping changes the operation being done without making it clear at the place where the operation is used.

[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]

@DaGenix

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.

@DaGenix

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> { ... }

[lambda-fairy]

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.)

[lambda-fairy]

@lambda-fairy

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: GitHub - lambda-fairy/wrapping_macros: 💝 A macro for wrapping arithmetic

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.