Rangeless Shifts · Issue #428 · rust-lang/libs-team (original) (raw)

Proposal

Problem statement

Rust presently has a few options for shifts:

• val << bits/val >> bits does a shift by bits with normally checked behaviour for out-of-range shifts,
• val.wrapping_shl(bits)/val.wrapping_shr(bits) likewise does a shift by bits, but wraps bits to the width of the type.

(There are also rotates_ which likewise wrap at width boundary).

This has a problem because the wrapping behaviour here is not the intuitive one (as it wraps the shift quantity, not the shift result). Operations may perform a shift with an undetermined quantity that may exceed the width of the type, e.g. to produce a bitmask of possible values.

Motivating examples or use cases

Producing an n-bit mask of an integer type up to n bits:

pub const fn mk_mask64(bits: u32) -> u64{ (1 << bits) }

Determining which bit to check for a carry-out of a wide operation

pub fn test_carry_bit(val: u64, bits: u32) -> u64{ val & (1 << bits) }

Both of these functions are ones I'm currently using in an architecture emulator which does native integer operations of varying sizes up to 64-bit.

Solution sketch

The names of the methods are subject to bikeshed, I don't have a good name for them.

impl Int { // Int is any signed or unsigned integer type, including u128/i128 and usize/isize`/ pub const fn rangeless_shl(self, width: u32) -> Self; pub const fn rangeless_shr(self, width: u32) -> Self; }

Formally, the behaviour of both of these methods involves evaluating the shift on a type with infinite width (or concretely, a width of u32::MAX + 1), then wrapping the result modulo (2 ^ Self::WIDTH).

Practically this means that:

• For a.rangeless_shl(bits), if bits < Self::WIDTH, the result is exactly a << bits. Otherwise the result is 0
• For a.rangeless_shr(bits), if bits < Self::WIDTH, the result is exactly a >> bits. Otherwise the result depends on the signedness:
  • For unsigned types, the result is 0 like for wrapping_shl, which corresponds with the logical right shift of the value by the full width of the type,
  • For signed types, the result is either 0 or -1 depending on whether the value is signed or unsigned, which corresponds to an arithmetic right shift of the value by the full width of the type.

The result does not differ when the shift quantity is exactly Self::WIDTH or is any value that exceeds it.

Alternatives

There are a few ways to implement the rangeless shifts concretely:

• self.checked_{shl,shr}(bits).unwrap_or(exceeds_width_result) , or, verbosely:
• if bits < Self::WIDTH { self (op) bits} else { exceeds_width_result }

(where exceeds_width_result is the appropriate value for the type and op)

Both versions are verbose and somewhat error prone (particularily for signed rangeless_shr) to write inline.

This could be an external crate, but has one of two major limitations due to current language features

1. It must be a free function, or
2. It cannot be made a const fn.

The ergonomics of having a method call, and the ability to do this as const makes me of the opinion that it should be an inherent method of the integer types in the standard library. A standard library function could also potentially benefit from optimizations on architectures where this behaviour is the behaviour of an out-of-range shift. I do not know whether or not the versions written above will do this, on x86 the unsigned versions will optimize to a cmov however.

Links and related work

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.