Auto merge of #49163 - SimonSapin:range-bounds, r=alexcrichton

Rename RangeArgument to RangeBounds, move it and Bound to libcore

As proposed in the tracking issue: https://github.com/rust-lang/rust/issues/30877

Changes to *stable* items:

* `core::ops::Bound` / `std::ops::Bound` is new
* `std::collections::Bound` is a deprecated reexport of it (does this actually cause a warning?)

Changes to *unstable* items

* `alloc::Bound` is gone
* `alloc::range::RangeArgument` is moved to `core::ops::RangeBounds` / `std::ops::RangeBounds`
* `alloc::range` is gone
* `std::collections::range::RangeArgument` is deprecated reexport, to be removed later
* `std::collections::range` is deprecated, to be removed later
* `impl RangeBounds<T> for Range{,From,To,Inclusive,ToInclusive}<&T>` are added

The idea of replacing this trait with a type to be used with `Into<_>` is left for future consideration / work.

(Fixes https://github.com/rust-lang-nursery/rust-clippy/issues/2552.)

2 files changed, 265 insertions, 1 deletions

diff --git a/src/libcore/ops/mod.rs b/src/libcore/ops/mod.rs
index 234970a81fa..0b480b618fc 100644
--- a/src/libcore/ops/mod.rs
+++ b/src/libcore/ops/mod.rs
@@ -192,7 +192,7 @@ pub use self::index::{Index, IndexMut};
 pub use self::range::{Range, RangeFrom, RangeFull, RangeTo};
 
 #[stable(feature = "inclusive_range", since = "1.26.0")]
-pub use self::range::{RangeInclusive, RangeToInclusive};
+pub use self::range::{RangeInclusive, RangeToInclusive, RangeBounds, Bound};
 
 #[unstable(feature = "try_trait", issue = "42327")]
 pub use self::try::Try;
diff --git a/src/libcore/ops/range.rs b/src/libcore/ops/range.rs
index be51f5239b0..3f667407125 100644
--- a/src/libcore/ops/range.rs
+++ b/src/libcore/ops/range.rs
@@ -442,3 +442,267 @@ impl<Idx: PartialOrd<Idx>> RangeToInclusive<Idx> {
 
 // RangeToInclusive<Idx> cannot impl From<RangeTo<Idx>>
 // because underflow would be possible with (..0).into()
+
+/// An endpoint of a range of keys.
+///
+/// # Examples
+///
+/// `Bound`s are range endpoints:
+///
+/// ```
+/// #![feature(collections_range)]
+///
+/// use std::ops::Bound::*;
+/// use std::ops::RangeBounds;
+///
+/// assert_eq!((..100).start(), Unbounded);
+/// assert_eq!((1..12).start(), Included(&1));
+/// assert_eq!((1..12).end(), Excluded(&12));
+/// ```
+///
+/// Using a tuple of `Bound`s as an argument to [`BTreeMap::range`].
+/// Note that in most cases, it's better to use range syntax (`1..5`) instead.
+///
+/// ```
+/// use std::collections::BTreeMap;
+/// use std::ops::Bound::{Excluded, Included, Unbounded};
+///
+/// let mut map = BTreeMap::new();
+/// map.insert(3, "a");
+/// map.insert(5, "b");
+/// map.insert(8, "c");
+///
+/// for (key, value) in map.range((Excluded(3), Included(8))) {
+///     println!("{}: {}", key, value);
+/// }
+///
+/// assert_eq!(Some((&3, &"a")), map.range((Unbounded, Included(5))).next());
+/// ```
+///
+/// [`BTreeMap::range`]: ../../std/collections/btree_map/struct.BTreeMap.html#method.range
+#[stable(feature = "collections_bound", since = "1.17.0")]
+#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
+pub enum Bound<T> {
+    /// An inclusive bound.
+    #[stable(feature = "collections_bound", since = "1.17.0")]
+    Included(#[stable(feature = "collections_bound", since = "1.17.0")] T),
+    /// An exclusive bound.
+    #[stable(feature = "collections_bound", since = "1.17.0")]
+    Excluded(#[stable(feature = "collections_bound", since = "1.17.0")] T),
+    /// An infinite endpoint. Indicates that there is no bound in this direction.
+    #[stable(feature = "collections_bound", since = "1.17.0")]
+    Unbounded,
+}
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+/// `RangeBounds` is implemented by Rust's built-in range types, produced
+/// by range syntax like `..`, `a..`, `..b` or `c..d`.
+pub trait RangeBounds<T: ?Sized> {
+    /// Start index bound.
+    ///
+    /// Returns the start value as a `Bound`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(collections_range)]
+    ///
+    /// # fn main() {
+    /// use std::ops::Bound::*;
+    /// use std::ops::RangeBounds;
+    ///
+    /// assert_eq!((..10).start(), Unbounded);
+    /// assert_eq!((3..10).start(), Included(&3));
+    /// # }
+    /// ```
+    fn start(&self) -> Bound<&T>;
+
+    /// End index bound.
+    ///
+    /// Returns the end value as a `Bound`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(collections_range)]
+    ///
+    /// # fn main() {
+    /// use std::ops::Bound::*;
+    /// use std::ops::RangeBounds;
+    ///
+    /// assert_eq!((3..).end(), Unbounded);
+    /// assert_eq!((3..10).end(), Excluded(&10));
+    /// # }
+    /// ```
+    fn end(&self) -> Bound<&T>;
+}
+
+use self::Bound::{Excluded, Included, Unbounded};
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+impl<T: ?Sized> RangeBounds<T> for RangeFull {
+    fn start(&self) -> Bound<&T> {
+        Unbounded
+    }
+    fn end(&self) -> Bound<&T> {
+        Unbounded
+    }
+}
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+impl<T> RangeBounds<T> for RangeFrom<T> {
+    fn start(&self) -> Bound<&T> {
+        Included(&self.start)
+    }
+    fn end(&self) -> Bound<&T> {
+        Unbounded
+    }
+}
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+impl<T> RangeBounds<T> for RangeTo<T> {
+    fn start(&self) -> Bound<&T> {
+        Unbounded
+    }
+    fn end(&self) -> Bound<&T> {
+        Excluded(&self.end)
+    }
+}
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+impl<T> RangeBounds<T> for Range<T> {
+    fn start(&self) -> Bound<&T> {
+        Included(&self.start)
+    }
+    fn end(&self) -> Bound<&T> {
+        Excluded(&self.end)
+    }
+}
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+impl<T> RangeBounds<T> for RangeInclusive<T> {
+    fn start(&self) -> Bound<&T> {
+        Included(&self.start)
+    }
+    fn end(&self) -> Bound<&T> {
+        Included(&self.end)
+    }
+}
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+impl<T> RangeBounds<T> for RangeToInclusive<T> {
+    fn start(&self) -> Bound<&T> {
+        Unbounded
+    }
+    fn end(&self) -> Bound<&T> {
+        Included(&self.end)
+    }
+}
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+impl<T> RangeBounds<T> for (Bound<T>, Bound<T>) {
+    fn start(&self) -> Bound<&T> {
+        match *self {
+            (Included(ref start), _) => Included(start),
+            (Excluded(ref start), _) => Excluded(start),
+            (Unbounded, _)           => Unbounded,
+        }
+    }
+
+    fn end(&self) -> Bound<&T> {
+        match *self {
+            (_, Included(ref end)) => Included(end),
+            (_, Excluded(ref end)) => Excluded(end),
+            (_, Unbounded)         => Unbounded,
+        }
+    }
+}
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+impl<'a, T: ?Sized + 'a> RangeBounds<T> for (Bound<&'a T>, Bound<&'a T>) {
+    fn start(&self) -> Bound<&T> {
+        self.0
+    }
+
+    fn end(&self) -> Bound<&T> {
+        self.1
+    }
+}
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+impl<'a, T> RangeBounds<T> for RangeFrom<&'a T> {
+    fn start(&self) -> Bound<&T> {
+        Included(self.start)
+    }
+    fn end(&self) -> Bound<&T> {
+        Unbounded
+    }
+}
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+impl<'a, T> RangeBounds<T> for RangeTo<&'a T> {
+    fn start(&self) -> Bound<&T> {
+        Unbounded
+    }
+    fn end(&self) -> Bound<&T> {
+        Excluded(self.end)
+    }
+}
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+impl<'a, T> RangeBounds<T> for Range<&'a T> {
+    fn start(&self) -> Bound<&T> {
+        Included(self.start)
+    }
+    fn end(&self) -> Bound<&T> {
+        Excluded(self.end)
+    }
+}
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+impl<'a, T> RangeBounds<T> for RangeInclusive<&'a T> {
+    fn start(&self) -> Bound<&T> {
+        Included(self.start)
+    }
+    fn end(&self) -> Bound<&T> {
+        Included(self.end)
+    }
+}
+
+#[unstable(feature = "collections_range",
+           reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
+           issue = "30877")]
+impl<'a, T> RangeBounds<T> for RangeToInclusive<&'a T> {
+    fn start(&self) -> Bound<&T> {
+        Unbounded
+    }
+    fn end(&self) -> Bound<&T> {
+        Included(self.end)
+    }
+}