ACP: `TwoSidedRange` trait

[pitaj]

Proposal

Problem statement

RangeBounds exists as a useful generic abstraction that lets users write functions that take any range type. However, is not uncommon that users want to only accept ranges with both start and end bounds (Range and RangeInclusive). If they choose to use RangeBounds for this, they have to resort to runtime panics. Or they have to write their own trait only implemented for the given ranges.

Motivating examples or use cases

The rand crate has a SampleRange trait implemented only for Range and RangeInclusive.

If TwoSidedRange existed, they could use that instead.

TODO: Other examples

Solution sketch

pub trait TwoSidedRange<T>: RangeBounds<T> {
    // Should this unconditionally clone to match `end_*`?
    /// Returns the incisive starting bound of the range
    fn start_inclusive(&self) -> &T;

    /// `None` if range is empty, otherwise returns the inclusive end bound 
    fn end_inclusive(&self) -> Option<T>;

    /// `None` if end bound would overflow `T`, otherwise returns the exclusive end bound
    // Maybe return `Result` instead?
    fn end_exclusive(&self) -> Option<T>;

    /// Returns the number of steps covered by the range
    fn width(&self) -> Option<usize>;
}

impl<T: Step> TwoSidedRange<T> for Range<T> { ... }
impl<T: Step> TwoSidedRange<T> for RangeInclusive<T> { ... }

Alternatives

The design of width (airways returning usize) is not ideal, we could instead return the next larger unsigned integer or something instead, but that would require a special trait.

The functions could live on rangebounds instead for better visibility.

Could instead have two traits: StartBoundRange and EndBoundRange and then TwoSidedRange would be expressed with StartBoundRange + EndBoundRange but providing fn width would be tough.

width is similar to ExactSizeIterator::len but implemented fallibly, whereas .len() can silently return incorrect results on platforms where usize is 16 bits.

Links and related work

• Brought up on RFC 3550: RFC: New range types for Edition 2024 rfcs#3550 (comment)
• Discussed on Zulip: https://rust-lang.zulipchat.com/#narrow/stream/219381-t-libs/topic/Abstracting.20over.20ranges.2C.20.60RangeBounds.60.20alternatives

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.

[kennytm]

sorry gotta -1 this one if this is the only motivation:

The rand crate has a SampleRange trait implemented only for Range and RangeInclusive.

I don't find this motivating enough. While the SampleRange trait is implemented over Range and RangeInclusive only, the definition of the trait cannot benefit from the proposed TwoSidedRange at all.

pub trait SampleRange<T> {
    fn sample_single<R: RngCore + ?Sized>(self, rng: &mut R) -> T;  // <- certainly out of scope for a std TwoSidedRange
    fn is_empty(&self) -> bool;
}

furthermore, since T is not required to be Copy, it can't even be properly implemented relying on the proposed solution sketch

impl<B, T> SampleRange<T> for B
where
    T: SampleUniform + PartialOrd,
    B: TwoSidedRange<T>,
{
    fn sample_single<R: RngCore +?Sized>(self, rng: &mut R) -> T {
        let start = self.start_inclusive();
        if let Some(end) = self.end_inclusive() {
            T::Sampler::sample_single_inclusive(*start, *end, rng) // actually can't move out start and end
        } else if let Some(end) = self.end_exclusive() {
            T::Sampler::sample_single(*start, *end, rng) // ditto
        } else {
            panic!("the range has no inclusive nor exclusive end why oh why");
        }
    }
    fn is_empty(&self) -> bool {
        self.width() <= Some(0)
    }
}

The rand they should just implement SampleRange over all 4 new and old + inclusive and exclusive range types and done (rand can't use any sort of TwoSidedRange without breaking MSRV anyway)

[Voultapher]

For completeness sake, I'm posting the original situation I found RangeBounds lacking for:

/// Returns a new `Vec` with `len` elements, where the elements are uniformly random in the `range`.
fn random_uniform<R: RangeBounds<i32>>(len: usize, range: R) -> Vec<i32>

Given the existing trait, implementing this function felt so cumbersome I decided to go a different route in the past. I think abstracting over ranges is a reasonable thing to do. So something like width seems like a good idea to me.

Another situation where I found the RangeBounds trait lacking, was implementing an interpreter for a DSL. The DSL has ranges, and initially I thought that mapping them to Rust ranges in the AST would be a good fit. That didn't work out in the end for other reasons, but even if they would map semantically, once you have a R: RangeBounds<T> how would you implement a for loop for it with the current trait? Yes one can write the appropriate match statements, but that seems needlessly complicated. I'd argue that one of the fundamental properties of ranges are the width they define, so there ought to be an easy-to-use way to get that value.

[pitaj]

I will add more examples when I get home (submitted this on my phone).

If you read the comments, I called out explicitly whether start_inclusive should return by value. If it does, your code works practically without change:

impl<B, T> SampleRange<T> for B
where
    T: SampleUniform + PartialOrd,
    B: TwoEndedRange<T>,
{
    fn sample_single<R: RngCore +?Sized>(self, rng: &mut R) -> T {
        let start = self.start_inclusive();
        // Exclusive end bound can always convert
        // to inclusive, unless the range is empty
        // But we explicitly don't support empty
        let end = self.end_inclusive().expect("range was empty");
        T::Sampler::sample_single_inclusive(start, end, rng)
    }
    fn is_empty(&self) -> bool {
        RangeBounds::is_empty(self)
    }
}

[kennytm]

The new sample code doesn't work because if start_inclusive() returned by value it would need to consume self, making self.end_inclusive() failing to compile. For a return-by-value method you'll need to return both bounds simultaneously.

trait TwoSidedRange<T> {
    fn try_into_range(self) -> Result<Range<T>, Self>;
    fn try_into_range_inclusive(self) -> Result<RangeInclusive<T>, Self>;
}

[pitaj]

The new sample code doesn't work because if start_inclusive() returned by value it would need to consume self, making self.end_inclusive() failing to compile. For a return-by-value method you'll need to return both bounds simultaneously.

No, you can just clone the bound. Step implies Clone, so the impl for TwoSidedRange can look like this:

impl<T: Step> TwoSidedRange<T> for Range<T> {
    // Just a copy for every `Step` type at the moment
    fn start_inclusive(&self) { self.start.clone() }
    ...
}

[kennytm]

The original implementation of sample_single does not require a clone, only moving. Consider that T can be a BigInt. This is an unnecessary performance degradation only because of limitation of the trait.

Edit: Also, rand::SampleRange did not require the T: Step bound, only T: SampleUniform + PartialOrd, changing the requirement to T: Step is totally unacceptable.

(P.S. I think RangeBounds should introduce an fn into_bounds(self) -> (Bound<T>, Bound<T>) as well, but this is out-of-scope.)

[kennytm]

@Voultapher

For completeness sake, I'm posting the original situation I found RangeBounds lacking for:

/// Returns a new `Vec` with `len` elements, where the elements are uniformly random in the `range`.
fn random_uniform<R: RangeBounds<i32>>(len: usize, range: R) -> Vec<i32>

Given the existing trait, implementing this function felt so cumbersome I decided to go a different route in the past. I think abstracting over ranges is a reasonable thing to do. So something like width seems like a good idea to me.

Yeah a .width() would be useful here because you're constraining to ranges of i32.

But rand's SampleUniform is also implemented for SIMD types (u32x2 etc) and floating point (f64) which a fn width(&self) -> Option<usize> does not seem helpful.

[Voultapher]

@kennytm unless I'm missing something, even if the proposed API extension doesn't help with rand's SampleUniform that wouldn't exclude it from being helpful in other use-cases as outlined, right?

[pitaj]

Indeed, the sketch solution doesn't resolve the rand case because those other types don't implement Step.

A more general solution would be something like

struct BoundIE<T> {
    Included(T),
    Excluded(T),
}
fn into_bounds(self) -> (T, BoundIE<T>);

// Or with pattern types

fn into_bounds(self) -> (T, Bound<T> is Bound::Included(_) | Bound::Excluded(_));

Which wouldn't require Step.

[kennytm]

@Voultapher That's why the first sentence of my comment is "gotta -1 this one (rand::SampleRange) if this is the only motivation"

So far the other motivation is your DSL use case in #365 (comment).

[Voultapher]

@kennytm I provided two motivating examples, random_uniform and the DSL.

[kennytm]

@Voultapher why do you want to implement your own random_uniform, that is valid only for i32, when rand::distributions::Uniform existed?

[Voultapher]

@kennytm while I could explain why that signature makes sense in my use-case, I don't see how that's relevant here. And looking at rand::distributions::Uniform it implements From for Range and RangeInclusive individually, it could instead with this proposal implement it for TwoSidedRange and save on duplication. I took 5 minutes and searched for .start_bound() via grep.app and found a variety of places that would benefit from the proposed API:

• Rust stdlib https://github.com/rust-lang/rust/blob/8d490e33ad7bbcdeab7975be787653b1e46e48e4/library/core/src/slice/index.rs#L702
• luminal https://github.com/jafioti/luminal/blob/239af0df26ef973df0fa0df28092670709d328e1/src/shape/slice.rs#L4
• clap https://github.com/clap-rs/clap/blob/9d14f394ba22f65f8957310a03ae5fd613f89d76/clap_builder/src/builder/value_parser.rs#L1365
• Xline https://github.com/xline-kv/Xline/blob/e35b35abc4b1b8316041bc71dbe7fe44785fdae0/crates/xlineapi/src/command.rs#L76

And the list goes on. If most users of the API end up doing the same match, why not provide it as part of the stdlib?