Type-smart `intersect` on ranges -- v2

(This is based on https://github.com/rust-lang/libs-team/issues/808#issuecomment-4722366762, replacing that proposal)

Proposal

Problem statement

Range intersection is a really useful operation, but IntoBounds::intersect feels kinda bad to use. If I'm dealing in a concrete range type, I almost never want to get (Bound<_>, Bound<_>). I want the concrete type that lets me use fields and doesn't force me to deal with all 9 cases in that tuple, many of which I know are impossible based on my inputs.

Motivating examples or use cases

Suppose I calculated two Range<usize>s into my array based on user input, and want to make sure they don't overlap. I'd like to intersect them and check whether the intersection is empty. Doing the full intersection -- rather than just a bool overlap check -- is useful because I can then give a nice error back to the caller if they do overlap that says where.

But I want to put a Range<usize> in my error, since that's a great specific type for representing the intersection of two Range<usize>s. I don't want to put (Bound<_>, Bound<_>) in my error.

And this is true for other combinations as well. If I was representing things as RangeInclusive<usize>, intersecting two of those should also give me RangeInclusive<usize>. Or maybe I intersected a Range<usize> with RangeTo<usize> as something like .intersect(..foo.len()) to truncate a range. That's still perfectly representable in a Range<usize>; I still don't want a pair-of-bound even though it's a mixed case.

Solution sketch

// in core::range

/// This trait is not implemented for all combinations,
/// only the ones with a good `Self::Intersection` type available.
///
/// However, because `(Bound<_>, Bound<_>): RangeIntersect`,
/// you can always use `a.into_bounds().intersect(b.into_bounds())`
/// for any two `impl IntoBounds` if needed.
trait RangeIntersect<RHS = Self> : Sized {
    type Intersection;
    fn intersect(self, rhs: RHS) -> Self::Intersection;
}

impl<T: Ord> RangeIntersect for (Bound<T>, Bound<T>) {
    type Intersection = Self;
    ...
}

// Everything homogeneous
impl<T: Ord> RangeIntersect for range::Range<T> {
    type Intersection = Self;
    ...
}
impl<T: Ord> RangeIntersect for range::RangeInclusive<T> {
    type Intersection = Self;
    ...
}
impl<T: Ord> RangeIntersect for range::RangeFrom<T> {
    type Intersection = Self;
    ...
}
impl RangeIntersect for range::RangeFull {
    type Intersection = Self;
    ...
}
... and more...

// Various heterogeneous ones, but we can always add more later
impl<T: Ord> RangeIntersect<range::RangeTo<T>> for range::Range<T> {
    type Intersection = range::Range<T>;
    ...
}
impl<T: Ord> RangeIntersect<range::Range<T>> for range::RangeTo<T> {
    type Intersection = range::Range<T>;
    ...
}
impl<T: Ord> RangeIntersect<range::RangeFull> for range::RangeTo<T> {
    type Intersection = range::Range<T>;
    ...
}
impl<T: Ord> RangeIntersect<range::Range<T>> for range::RangeFull {
    type Intersection = range::Range<T>;
    ...
}
... and more...

(And remove IntoBounds::intersect)

I would propose no mixing of legacy and range concrete types, because there's no good way to pick which type to return for intersect(legacy::Range, range::Range). We can support both intersect(legacy::Range, legacy::Range) and intersect(range::Range, range::Range), leaving it up to the caller to convert one or the other into the non-legacy form.

Alternatives

• Keep things as they are and have people deal in (Bound<_>, Bound<_>).
• Only do homogeneous intersects via inherent methods
• Add a T generic to the RangeIntersect trait
  • It was in @joshtriplett's sketch (https://github.com/rust-lang/libs-team/issues/808#issuecomment-4722366762) but it didn't seem necessary so I removed it.
• Add a supertrait of some sort or a trait bound to the associated type
  • Doing that would probably need the <T> parameter on RangeIntersect again
• Add a blanket impl for RangeFull that always just returns the other thing.
• Use ops::BitAnd for this, like HashSet does (https://doc.rust-lang.org/std/collections/struct.HashSet.html#impl-BitAnd%3C%26HashSet%3CT,+S%3E%3E-for-%26HashSet%3CT,+S%3E) rather than a new trait.
• Only implement it for the new range ranges, not the old ones, to avoid any future issues with people trying to migrate things from the legacy ones to the new ones.
• Implement the full cartesian product between legacy and new ranges, picking one kind or the other as we think it most helpful to mid-migration cases.

Links and related work

• ACP for the always-bounds intersect: https://github.com/rust-lang/libs-team/issues/539
• Previous "type-smart intersect" ACP: https://github.com/rust-lang/libs-team/issues/808
  • In particular, see @kennytm's table in https://github.com/rust-lang/libs-team/issues/808#issuecomment-4723128993 of what the intersection types would be, and which we wouldn't provide.

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.

Start with core::range's IntoBounds::intersect and the proposed RangeIntersect trait, then compare the linked ACPs and intersection-type table. Done means the libs-api team has decided whether this API proposal and its alternatives should proceed; the issue does not identify implementation files or tests.