IntoBounds::clamp and RangeBounds::is_empty

[pitaj]

Proposal

Problem statement

Range types are essentially abstract sets, defined by a start and end point. A common operation on sets is calculating the intersection, and in practice this applies to ranges as well.

Having a generic way to tell if the result is empty is also useful.

Motivating examples or use cases

A custom slice type where indexing always succeeds

use std::ops::{Index, IntoBounds};

pub struct Slice<T>([T]);

impl<T, R: IntoBounds<usize>> Index<R> for Slice<T> {
    type Output = [T];
    fn index(&self, index: R) -> &[T] {
        &self.0[index.clamp(..self.0.len())]
    }
}

The examples from #277 are also applicable to this proposal

• a database implementation using btree index where a parent node would split its total key range in ranges per child. To implement an operation to find keys within a given range it would need to check if child ranges overlap with an input range
• An interval map implementation would need to be able to check for overlaps
• A memory copy/move implementation operation may check for overlaps to decide if it needs to use move or copy
• A database implementation allowing to operate on ranges (eg range deletes, range queries, etc) would need to have an ability to check for range overlaps

Solution sketch

pub trait RangeBounds<T: ?Sized> {
    // ...

    /// Returns `true` if the range contains no items.
    /// One-sided ranges (`RangeFrom`, etc) always returns `true`.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::ops::RangeBounds;
    ///
    /// assert!(!(3..).is_empty());
    /// assert!(!(..2).is_empty());
    /// assert!(!RangeBounds::is_empty(&(3..5)));
    /// assert!( RangeBounds::is_empty(&(3..3)));
    /// assert!( RangeBounds::is_empty(&(3..2)));
    /// ```
    ///
    /// The range is empty if either side is incomparable:
    ///
    /// ```
    /// use std::ops::RangeBounds;
    ///
    /// assert!(!RangeBounds::is_empty(&(3.0..5.0)));
    /// assert!( RangeBounds::is_empty(&(3.0..f32::NAN)));
    /// assert!( RangeBounds::is_empty(&(f32::NAN..5.0)));
    /// ```
    ///
    /// But never empty is either side is unbounded:
    ///
    /// ```
    /// use std::ops::Bound::*;
    /// use playground::RangeBounds;
    ///
    /// assert!(!(..0).is_empty());
    /// assert!(!(i32::MAX..).is_empty());
    /// assert!(!RangeBounds::<u8>::is_empty(&(..)));
    /// ```
    ///
    /// `(Excluded(a), Excluded(b))` is only empty if `a >= b`:
    ///
    /// ```
    /// use std::ops::Bound::*;
    /// use std::ops::RangeBounds;
    ///
    /// assert!(!(Excluded(1), Excluded(3)).is_empty());
    /// assert!(!(Excluded(1), Excluded(2)).is_empty());
    /// assert!( (Excluded(1), Excluded(1)).is_empty());
    /// assert!( (Excluded(2), Excluded(1)).is_empty());
    /// assert!( (Excluded(3), Excluded(1)).is_empty());
    /// ```
    fn is_empty(&self) -> bool
    where
        T: PartialOrd,
    {
        !match (self.start_bound(), self.end_bound()) {
            (Unbounded, _) | (_, Unbounded) => true,
            (Included(start), Excluded(end))
            | (Excluded(start), Included(end))
            | (Excluded(start), Excluded(end)) => start < end,
            (Included(start), Included(end)) => start <= end,
        }
    }
}

pub trait IntoBounds<T>: RangeBounds<T> {
    fn into_bounds(self) -> (Bound<T>, Bound<T>);
    
    /// Clamp `self` within the bounds of `other`.
    /// In set terms, this is the _intersection_.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::ops::Bound::*;
    /// use std::ops::IntoBounds;
    ///
    /// assert_eq!((3..).clamp(..5), (Included(3), Excluded(5)));
    /// assert_eq!((-12..387).clamp(0..256), (Included(0), Excluded(256)));
    /// assert_eq!((1..5).clamp(..), (Included(1), Excluded(5)));
    /// assert_eq!((1..=9).clamp(0..10), (Included(1), Included(9)));
    /// assert_eq!((7..=13).clamp(8..13), (Included(8), Excluded(13)));
    /// ```
    ///
    /// Combine with `is_empty` to determine if two ranges overlap.
    ///
    /// ```
    /// use std::ops::{RangeBounds, IntoBounds};
    ///
    /// assert!(!(3..).clamp(..5).is_empty());
    /// assert!(!(-12..387).clamp(0..256).is_empty());
    /// assert!((1..5).clamp(6..).is_empty());
    /// ```
    fn clamp<R>(self, other: R) -> (Bound<T>, Bound<T>)
    where
        Self: Sized,
        T: Ord,
        R: Sized + IntoBounds<T>,
    {
        let (self_start, self_end) = IntoBounds::into_bounds(self);
        let (other_start, other_end) = IntoBounds::into_bounds(other);

        let start = match (self_start, other_start) {
            (Included(a), Included(b)) => Included(Ord::max(a, b)),
            (Excluded(a), Excluded(b)) => Excluded(Ord::max(a, b)),
            (Unbounded, Unbounded) => Unbounded,
            
            (x, Unbounded) | (Unbounded, x) => x,
            
            (Included(i), Excluded(e))
            | (Excluded(e), Included(i)) => if i > e {
                Included(i)
            } else {
                Excluded(e)
            }
        };
        let end = match (self_end, other_end) {
            (Included(a), Included(b)) => Included(Ord::min(a, b)),
            (Excluded(a), Excluded(b)) => Excluded(Ord::min(a, b)),
            (Unbounded, Unbounded) => Unbounded,
            
            (x, Unbounded) | (Unbounded, x) => x,
            
            (Included(i), Excluded(e))
            | (Excluded(e), Included(i)) => if i < e {
                Included(i)
            } else {
                Excluded(e)
            }
        };
        
        (start, end)
    }
}

Alternatives

Just provide a generic way to tell if two ranges overlap, without actually calculating the overlap, aka #277. RangeBounds::overlap is more flexible, since it can operate without Ord or IntoBounds.

Links and related work

• [ACP] RangeBounds::overlaps #277
• playground

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.

[programmerjake]

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=3fdf9ff5b37aecbf4cc31c1f9ffa2113

// you claimed: assert!(!(Excluded(1), Excluded(2)).is_empty());
//
// but, that's wrong (for indexes/integers),
// since there are no integers strictly between 1 and 2
assert_eq!(&"abcdef"[(Bound::Excluded(1), Bound::Excluded(2))], "");

[kennytm]

@programmerjake See #277 (comment).

[joshtriplett]

We discussed this in today's @rust-lang/libs-api meeting.

We'd like to see clamp renamed to intersect. Otherwise, we're happy to approve this, together with is_empty.

Separately from this ACP, we also had a mild interest in seeing a way to get back a Range type for an intersection of ranges, but we agreed that that would take a lot more API design and should not be made a part of this ACP.

[kennytm]

we also had a mild interest in seeing a way to get back a Range type for an intersection of ranges, but we agreed that that would take a lot more API design and should not be made a part of this ACP.

We would need to support (0..10).intersect(1..=5) == 1..=5 and (0..10).intersect(1..=50) == 1..10 simultaneously. At least anonymous sum type is needed.

Turning that into 2 steps by adding impl<T> TryFrom<(Bound<T>, Bound<T>)> for Range<T> sounds more practical.

[Amanieu]

we also had a mild interest in seeing a way to get back a Range type for an intersection of ranges, but we agreed that that would take a lot more API design and should not be made a part of this ACP.

We would need to support (0..10).intersect(1..=5) == 1..=5 and (0..10).intersect(1..=50) == 1..10 simultaneously. At least anonymous sum type is needed.

Turning that into 2 steps by adding impl<T> TryFrom<(Bound<T>, Bound<T>)> for Range<T> sounds more practical.

The idea was to restrict Range::insersection to only take a Range and return a Range. Similarly RangeInclusive::intersection would only accept another RangeInclusive and return a RangeInclusive. This is sufficient to satisfy the majority of use cases. For more general cases the generic version on RangeBounds can be used which returns a pair of Bounds.

[kennytm]

The idea was to restrict Range::insersection to only take a Range and return a Range. Similarly RangeInclusive::intersection would only accept another RangeInclusive and return a RangeInclusive. This is sufficient to satisfy the majority of use cases.

I thought the biggest use case was something like std::slice::range (which is why the ACP function name was clamp instead of intersect) which fits neither scenario 😅

[pitaj]

If we were to add this alternative, realistically Range could accept any other range with exclusive end (or unbounded) and RangeInclusive could accept any other range with inclusive end (or unbounded).

We could also use a Step bound to convert between inclusive and exclusive in order to support any IntoBounds - there would be no risk of overflow.

[joshtriplett]

Any kind of "intersect two ranges to get a range" mechanism is going to need a lot of API design. Let's not do that in the GitHub comments of a now-approved-and-closed ACP, and create a lot of noise for people who are looking for the status of the API this ACP proposed.

For the API design of some future feature, may I suggest Zulip or IRLO or somewhere else?