Add `saturating_shl` and `saturating_shr` for ints

[kellerkindt]

Proposal

Problem statement

There is wrapping_shr and wrapping_shl a well as overflowing_shr and oveflowing_shl but no saturating_shl and saturating_shr.

So on the one hand, this is for completion purposes. But I also think this should be implemented before the Saturating type is stabilized ... if the effort is reasonable.

Motivating examples or use cases

I am working on this mostly to get a Saturating type stabilized with more or less feature parity to the Wrapping type.

Solution sketch

Will reopen rust-lang/rust#103441

Alternatives

Doing nothing and stabilize the Saturating type without saturating_shl / saturating_shr.

Links and related work

• wrapping_shr
• wrapping_shl
• overflowing_shr
• oveflowing_shl

What happens now?

This issue is part of the libs-api team API change proposal process. 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.

[Amanieu]

We discussed this in the libs-api meeting last week and we are open to adding these functions but there were concerns about the lack of a clear motivating example for how these functions could be used. There were also concerns that the exact semantics of saturating shifts aren't clear.

---

With that said, I've spent some time thinking over this and there's only one reasonable definition of a saturating operation: it involves performing the operation with infinite precision and then saturating the result to fit into the destination type. In the case of saturating_shl, the operation is multiplication by 2^shift, and in the case of saturating_shr the operation is division by 2^n and rounding to -infinity (negative numbers saturate to -1, positive numbers to 0).

[Amanieu]

We discussed this in the libs-api meeting today but did not come to a consensus. Some clear use case examples would help.

[kellerkindt]

Hi, thanks for looking into it. The reason for this proposal is to get the Saturating type to somewhere close to feature parity to the Wrapping type before stabilizing it. Both types use their respective integer functions under the hood (like here).

Personally, I only have use cases for the simple arithmetic operations like addition, subtraction and multiplication.

[the8472]

I don't think feature parity is a prerequisite for stabilization. Methods could be added later if someone actually needs them.

[Amanieu]

The main issue with saturating shifts is that it's not clear whether the result is saturated (1u8 << 1000 saturates to 255) or the shift amount (1u8 << 1000 saturates to 0). Perhaps it would help to have separate methods for each case?

[pitaj]

Add an outsider, it's pretty intuitive to me that any "saturating" operation applies to the result, not the operands.

[cuviper]

Add an outsider, it's pretty intuitive to me that any "saturating" operation applies to the result, not the operands.

Do you also think that about checked/overflowing/wrapping shifts? Because all of those apply to the shift amount, not the result. Yes, that's often confusing, but that's what we have nonetheless.

[pitaj]

I see. That's a very good point then. On the one hand, people will often expect the following to be equal:

foo.saturating_mul(2)
foo.saturating_shl(1)

But people will also expect saturating_shl to behave like wrapping_shl and co.

I suppose the reason that wrapping_shl and co behave this way is because a shift right will never overflow, which also applies to saturating_shr.

[CAD97]

I personally think it's more useful for saturating_sh[lr] to be consistent with the other methods and refer to the shift operand saturating instead of the shift result... except that the "mathematically useful" definition wants .sat_shl(BITS) == 0, not .sat_shl(BITS) == .shl(BITS - 1). It doesn't particularly help that the signed .saturating_shr is actually isomorphic to the "mathematically useful" version...

This is one of those cases where the Saturating type is most useful, actually, to disambiguate between whether Saturating(n) << m (if bits would be shifted out, produce MAX), n << Saturating(m) (if shift amount would overflow, shift by BITS - 1 instead), or n.checked_shl(m).unwrap_or(0) is actually the desired semantics.

Keep in mind that even overflowing_sh[lr] refers to overflowing the shift value, not whether bits are shifted out of the result value. (Given a time machine, I'd remove the Wrapping(n) << m impl of n.wrapping_shl(m); it's applying wrapping semantics to the wrong value!)

.saturating.sh[lr] (with shift amount saturates semantics) probably deserve to exist, but like .wrapping_sh[lr] have a note that you might want .rotate_{left|right} instead, they would need a note explaining what exactly the saturating semantics are, as well as how to get the other potentially desired semantics.

(Did Euclid happen to discuss ring arithmetic shifts, so we can justify calling the "mathematically useful" version .sh[lr]_euclid (half-joking)? In analogy to {div|rem}_euclid being the "mathematically useful" definition.)

semantics	impl
shift checking	if m < BITS { Some(n << m) } else { None }
shift wrapping	n << m.rem_euclid(BITS)
shift saturating	n << m.clamp(0, BITS - 1)
result checking	if m < n.leading_zeros() { Some(n << m) } else { None }
result wrapping	n.rotate_left(m.rem_euclid(BITS))
result saturating	if m < n.leading_zeros() { n << m } else { -1 as _ }
signed result saturating	if m < n.trailing_zeros() { n >> m } else if n < 0 { -1 } else { 0 }
result truncating	if m < BITS { n << m } else { 0 }
signed result truncating1	if m < BITS { n >> m } else if n < 0 { -1 } else { 0 }

Footnotes

1. I'm defining "result truncating" as doing the operation in infinite precision and then truncating to the bits that fit in the output range. This works unambiguously for unsigned types, but doesn't quite work perfectly for signed types. If there's a good definition of shl for signed ints that doesn't rely on doing the operation in unsigned space, though, I don't know it. ↩

[scottmcm]

I think the current definitions of shifts were a mistake, in retrospect. Picking the "this is efficient on x86" definition over the "this makes sense" definition is usually not what Rust does for the default.

But saturating_sh[lr] ought -- if it exists -- to be consistent with wrapping_sh[lr] and checked_sh[lr] and overflowing_sh[lr], because doing anything else is more confusing.

---

Drastic idea: What if we did an edition change?

We could add new ShiftLeft/ShiftRight traits, and use those in the new edition. They'd use the ">> n is the same as doing >> 1 n times" definition, and there's manual masking or unchecked_shl for people who really need something faster than that. (Maybe only take unsigned RHSs too.)

Or just add .shift_left(u32)+.shift_right(u32) methods that do the logical thing, and encourage those instead.

[programmerjake]

semantics impl
shift checking if m < BITS { Some(n << m) } else { None }
shift wrapping n << m.rem_euclid(BITS)
shift saturating n << m.clamp(0, BITS - 1)
result checking if m < n.leading_zeros() { Some(n << m) } else { None }
result wrapping n.rotate_left(m.rem_euclid(BITS))

that's not what's generally accepted to be wrapping-result. rotate is basically never a substitute for shifting. wrapping generally means the value is computed to infinite precision and then reduced mod 2BITS, with signed results computing the mod operation to provide balanced results rather than strictly positive. this is equivalent to shifting then extracting the lower BITS-bits, so shift amounts as big or bigger than BITS always return 0.

result saturating if m < n.leading_zeros() { n << m } else { -1 as _ }

this is wrong because: 0 << anything == 0

1. I'm defining "result truncating" as doing the operation in infinite precision and then truncating to the bits that fit in the output range. This works unambiguously for unsigned types, but doesn't quite work perfectly for signed types. If there's a good definition of shl for signed ints that doesn't rely on doing the operation in unsigned space, though, I don't know it. ↩

there is, it's the definition i gave for wrapping result