actually checked bitshifts

[lolbinarycat]

Proposal

Problem statement

For every integer operation with a symbolic operator, there is a corresponding checked_* method that returns None if an overflow occurs...

except for bitshifts, whose checked_* functions do something entirely different.

For example, 255_u8.checked_shl(1) evaluates to Some(254).

The closest existing functions are overflowing_{shl,shr}, but those must also return a result in the overflowing case, ruling out implementations that check for overflow before doing the shift. EDIT: the overflowing_* functions ALSO don't do what you would expect.

Motivating examples or use cases

This could be used to detect overflow when parsing certain types of positional integer notation, from ascii decimal to certain VLQs.

Solution Sketch

• (optional) Deprecate checked_shr and checked_shl and give them less confusing names.
• Add new shift functions that return None on overflow

Links and related work

• the check_shl_overflow macro used in the linux kernel

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[lolbinarycat]

Here's two possible implementations:

pub fn check_shl_overflow_reshift(n: u64, shift_amount: u32) -> Option<u64> {
    let r = n << shift_amount;
    if r >> shift_amount == n {
        Some(r)
    } else {
        None
    }
}

pub fn check_shl_overflow_rotate(n: u64, shift_amount: u32) -> Option<u64> {
    let r = n.rotate_left(shift_amount);
    if r & ((shift_amount-1) as u64) == 0 {
        Some(r)
    } else {
        None
    }
}

compare on godbolt

[programmerjake]

imo check_shl_overflow_reshift is not correct, you also need to check for shift_amount being too big.

[pitaj]

There are the recently stabilized unbounded_shl and unbounded_shr APIs.

We could add a checked_ version of those, but checked_unbounded_shl is a mouthful.

[lolbinarycat]

@pitaj is it more of a mouthful than overflowing_sub_unsigned, or any of the other similar method names on integers?

[pitaj]

I wasn't saying we should block this proposal based on the name, just maybe think if better names exist. One alternative I thought of is bounded_shl.

Also note on implementation, you should be able to implement checked_unbounded_shl in terms of unbounded_shl and leading_zeroes.

[lolbinarycat]

bounded_shl does not seem to be a technically correct name to me, my understanding is that normal shl is considered "bounded" (ie. a large RHS will cause an overflow and possibly a panic)

[kennytm]

What OP wanted is not any existing Rust stdlib variant of bit shift, which shifting bits beyond out of MSB is a well-defined and valid behavior, but a weird version like x.checked_mul(1 << b) for "shl".

(Not sure what the "weird_checked" version of "shr" looks like.)

[pitaj]

Yeah the shl behavior is pretty intuitive, but when should shr return None?

[programmerjake]

maybe name it a.checked_mul_by_two_pow(b) == a.checked_mul(<int>::checked_pow(2, b)?)

[pitaj]

What OP wanted is not any existing Rust stdlib variant of bit shift, which shifting bits beyond out of MSB is a well-defined and valid behavior, but a weird version like x.checked_mul(1 << b) for "shl".

unbounded_shl is essentially the wrapping version of this new kind of shift operation. Which brings up another question: do we want saturating or strict versions of unbounded_shl too?

[programmerjake]

unbounded_shl is essentially the wrapping version of this new kind of shift operation. Which brings up another question: do we want saturating or strict versions of unbounded_shl too?

strict_unbounded_shl is unbounded_shl -- it never panics. (edit: nvm, had my brain on backwards) I could get behind adding checked_unbounded_shl and saturating_unbounded_shl

though if we use checked_unbounded_shl as the name, it may be less efficient since it'd have to return Some(0) for 0.checked_unbounded_shl(12345) even though that's waay out of the supported range for shifting any non-zero value.

[lolbinarycat]

@kennytm It's the reverse, where shifting bits off the right rerurns None.

basically, if the result would have less bits set than the input, None is returned.

[scottmcm]

Which brings up another question: do we want saturating or strict versions of unbounded_shl too?

I'd say no. To me, the point of it is that a large shift isn't an error, so it doesn't need to be checked in debug (and checking would be a breaking change, arguably) and doesn't need all the extra variants as a result.

---

If you want to be inspired by LLVM and its unsafe versions of shifts, they have shl n[su]w and [al]shr exact for the "this is reversible" cases. Basically, shl nuw %a, 3 is the one that's the same as mul nuw %a, 8.