Auto merge of #43077 - SimonSapin:ranges, r=alexcrichton

Implement O(1)-time Iterator::nth for Range*, and slim the Step trait

Fixes #43064.
Fixes part of #39975.
Fixes items 1 <s>and 3</s> of #42168.
CC #27741.

I think #42310 and #43012 should not have landed without the `nth` part of this PR, but oh well.

5 files changed, 196 insertions, 174 deletions

diff --git a/src/libcore/iter/range.rs b/src/libcore/iter/range.rs
index 1dad8157948..32c32e327eb 100644
--- a/src/libcore/iter/range.rs
+++ b/src/libcore/iter/range.rs
@@ -8,6 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use convert::TryFrom;
 use mem;
 use ops::{self, Add, Sub};
 use usize;
@@ -21,22 +22,13 @@ use super::{FusedIterator, TrustedLen};
 #[unstable(feature = "step_trait",
            reason = "likely to be replaced by finer-grained traits",
            issue = "42168")]
-pub trait Step: PartialOrd + Sized {
-    /// Steps `self` if possible.
-    fn step(&self, by: &Self) -> Option<Self>;
-
+pub trait Step: Clone + PartialOrd + Sized {
     /// Returns the number of steps between two step objects. The count is
     /// inclusive of `start` and exclusive of `end`.
     ///
     /// Returns `None` if it is not possible to calculate `steps_between`
     /// without overflow.
-    fn steps_between(start: &Self, end: &Self, by: &Self) -> Option<usize>;
-
-    /// Same as `steps_between`, but with a `by` of 1
-    fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize>;
-
-    /// Tests whether this step is negative or not (going backwards)
-    fn is_negative(&self) -> bool;
+    fn steps_between(start: &Self, end: &Self) -> Option<usize>;
 
     /// Replaces this step with `1`, returning itself
     fn replace_one(&mut self) -> Self;
@@ -49,6 +41,34 @@ pub trait Step: PartialOrd + Sized {
 
     /// Subtracts one to this step, returning the result
     fn sub_one(&self) -> Self;
+
+    /// Add an usize, returning None on overflow
+    fn add_usize(&self, n: usize) -> Option<Self>;
+}
+
+// These are still macro-generated because the integer literals resolve to different types.
+macro_rules! step_identical_methods {
+    () => {
+        #[inline]
+        fn replace_one(&mut self) -> Self {
+            mem::replace(self, 1)
+        }
+
+        #[inline]
+        fn replace_zero(&mut self) -> Self {
+            mem::replace(self, 0)
+        }
+
+        #[inline]
+        fn add_one(&self) -> Self {
+            Add::add(*self, 1)
+        }
+
+        #[inline]
+        fn sub_one(&self) -> Self {
+            Sub::sub(*self, 1)
+        }
+    }
 }
 
 macro_rules! step_impl_unsigned {
@@ -58,127 +78,66 @@ macro_rules! step_impl_unsigned {
                    issue = "42168")]
         impl Step for $t {
             #[inline]
-            fn step(&self, by: &$t) -> Option<$t> {
-                (*self).checked_add(*by)
-            }
-            #[inline]
             #[allow(trivial_numeric_casts)]
-            fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
-                if *by == 0 { return None; }
+            fn steps_between(start: &$t, end: &$t) -> Option<usize> {
                 if *start < *end {
                     // Note: We assume $t <= usize here
-                    let diff = (*end - *start) as usize;
-                    let by = *by as usize;
-                    if diff % by > 0 {
-                        Some(diff / by + 1)
-                    } else {
-                        Some(diff / by)
-                    }
+                    Some((*end - *start) as usize)
                 } else {
                     Some(0)
                 }
             }
 
             #[inline]
-            fn is_negative(&self) -> bool {
-                false
-            }
-
-            #[inline]
-            fn replace_one(&mut self) -> Self {
-                mem::replace(self, 1)
-            }
-
-            #[inline]
-            fn replace_zero(&mut self) -> Self {
-                mem::replace(self, 0)
-            }
-
-            #[inline]
-            fn add_one(&self) -> Self {
-                Add::add(*self, 1)
-            }
-
-            #[inline]
-            fn sub_one(&self) -> Self {
-                Sub::sub(*self, 1)
+            fn add_usize(&self, n: usize) -> Option<Self> {
+                match <$t>::try_from(n) {
+                    Ok(n_as_t) => self.checked_add(n_as_t),
+                    Err(_) => None,
+                }
             }
 
-            #[inline]
-            fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
-                Self::steps_between(start, end, &1)
-            }
+            step_identical_methods!();
         }
     )*)
 }
 macro_rules! step_impl_signed {
-    ($($t:ty)*) => ($(
+    ($( [$t:ty : $unsigned:ty] )*) => ($(
         #[unstable(feature = "step_trait",
                    reason = "likely to be replaced by finer-grained traits",
                    issue = "42168")]
         impl Step for $t {
             #[inline]
-            fn step(&self, by: &$t) -> Option<$t> {
-                (*self).checked_add(*by)
-            }
-            #[inline]
             #[allow(trivial_numeric_casts)]
-            fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
-                if *by == 0 { return None; }
-                let diff: usize;
-                let by_u: usize;
-                if *by > 0 {
-                    if *start >= *end {
-                        return Some(0);
-                    }
+            fn steps_between(start: &$t, end: &$t) -> Option<usize> {
+                if *start < *end {
                     // Note: We assume $t <= isize here
                     // Use .wrapping_sub and cast to usize to compute the
                     // difference that may not fit inside the range of isize.
-                    diff = (*end as isize).wrapping_sub(*start as isize) as usize;
-                    by_u = *by as usize;
-                } else {
-                    if *start <= *end {
-                        return Some(0);
-                    }
-                    diff = (*start as isize).wrapping_sub(*end as isize) as usize;
-                    by_u = (*by as isize).wrapping_mul(-1) as usize;
-                }
-                if diff % by_u > 0 {
-                    Some(diff / by_u + 1)
+                    Some((*end as isize).wrapping_sub(*start as isize) as usize)
                 } else {
-                    Some(diff / by_u)
+                    Some(0)
                 }
             }
 
             #[inline]
-            fn is_negative(&self) -> bool {
-                *self < 0
-            }
-
-            #[inline]
-            fn replace_one(&mut self) -> Self {
-                mem::replace(self, 1)
-            }
-
-            #[inline]
-            fn replace_zero(&mut self) -> Self {
-                mem::replace(self, 0)
-            }
-
-            #[inline]
-            fn add_one(&self) -> Self {
-                Add::add(*self, 1)
-            }
-
-            #[inline]
-            fn sub_one(&self) -> Self {
-                Sub::sub(*self, 1)
+            fn add_usize(&self, n: usize) -> Option<Self> {
+                match <$unsigned>::try_from(n) {
+                    Ok(n_as_unsigned) => {
+                        // Wrapping in unsigned space handles cases like
+                        // `-120_i8.add_usize(200) == Some(80_i8)`,
+                        // even though 200_usize is out of range for i8.
+                        let wrapped = (*self as $unsigned).wrapping_add(n_as_unsigned) as $t;
+                        if wrapped >= *self {
+                            Some(wrapped)
+                        } else {
+                            None  // Addition overflowed
+                        }
+                    }
+                    Err(_) => None,
+                }
             }
 
-            #[inline]
-            fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
-                Self::steps_between(start, end, &1)
-            }
+            step_identical_methods!();
         }
     )*)
 }
@@ -190,54 +149,26 @@ macro_rules! step_impl_no_between {
                    issue = "42168")]
         impl Step for $t {
             #[inline]
-            fn step(&self, by: &$t) -> Option<$t> {
-                (*self).checked_add(*by)
-            }
-            #[inline]
-            fn steps_between(_a: &$t, _b: &$t, _by: &$t) -> Option<usize> {
+            fn steps_between(_start: &Self, _end: &Self) -> Option<usize> {
                 None
             }
 
             #[inline]
-            #[allow(unused_comparisons)]
-            fn is_negative(&self) -> bool {
-                *self < 0
-            }
-
-            #[inline]
-            fn replace_one(&mut self) -> Self {
-                mem::replace(self, 1)
-            }
-
-            #[inline]
-            fn replace_zero(&mut self) -> Self {
-                mem::replace(self, 0)
-            }
-
-            #[inline]
-            fn add_one(&self) -> Self {
-                Add::add(*self, 1)
+            fn add_usize(&self, n: usize) -> Option<Self> {
+                self.checked_add(n as $t)
             }
 
-            #[inline]
-            fn sub_one(&self) -> Self {
-                Sub::sub(*self, 1)
-            }
-
-            #[inline]
-            fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
-                Self::steps_between(start, end, &1)
-            }
+            step_identical_methods!();
         }
     )*)
 }
 
 step_impl_unsigned!(usize u8 u16 u32);
-step_impl_signed!(isize i8 i16 i32);
+step_impl_signed!([isize: usize] [i8: u8] [i16: u16] [i32: u32]);
 #[cfg(target_pointer_width = "64")]
 step_impl_unsigned!(u64);
 #[cfg(target_pointer_width = "64")]
-step_impl_signed!(i64);
+step_impl_signed!([i64: u64]);
 // If the target pointer width is not 64-bits, we
 // assume here that it is less than 64-bits.
 #[cfg(not(target_pointer_width = "64"))]
@@ -277,9 +208,7 @@ macro_rules! range_incl_trusted_len_impl {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A: Step> Iterator for ops::Range<A> where
-    for<'a> &'a A: Add<&'a A, Output = A>
-{
+impl<A: Step> Iterator for ops::Range<A> {
     type Item = A;
 
     #[inline]
@@ -295,11 +224,24 @@ impl<A: Step> Iterator for ops::Range<A> where
 
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
-        match Step::steps_between_by_one(&self.start, &self.end) {
+        match Step::steps_between(&self.start, &self.end) {
             Some(hint) => (hint, Some(hint)),
             None => (0, None)
         }
     }
+
+    #[inline]
+    fn nth(&mut self, n: usize) -> Option<A> {
+        if let Some(plus_n) = self.start.add_usize(n) {
+            if plus_n < self.end {
+                self.start = plus_n.add_one();
+                return Some(plus_n)
+            }
+        }
+
+        self.start = self.end.clone();
+        None
+    }
 }
 
 // These macros generate `ExactSizeIterator` impls for various range types.
@@ -317,10 +259,7 @@ range_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 i64 u64);
 range_incl_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 i64 u64);
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A: Step + Clone> DoubleEndedIterator for ops::Range<A> where
-    for<'a> &'a A: Add<&'a A, Output = A>,
-    for<'a> &'a A: Sub<&'a A, Output = A>
-{
+impl<A: Step> DoubleEndedIterator for ops::Range<A> {
     #[inline]
     fn next_back(&mut self) -> Option<A> {
         if self.start < self.end {
@@ -333,13 +272,10 @@ impl<A: Step + Clone> DoubleEndedIterator for ops::Range<A> where
 }
 
 #[unstable(feature = "fused", issue = "35602")]
-impl<A> FusedIterator for ops::Range<A>
-    where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}
+impl<A: Step> FusedIterator for ops::Range<A> {}
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A: Step> Iterator for ops::RangeFrom<A> where
-    for<'a> &'a A: Add<&'a A, Output = A>
-{
+impl<A: Step> Iterator for ops::RangeFrom<A> {
     type Item = A;
 
     #[inline]
@@ -353,16 +289,20 @@ impl<A: Step> Iterator for ops::RangeFrom<A> where
     fn size_hint(&self) -> (usize, Option<usize>) {
         (usize::MAX, None)
     }
+
+    #[inline]
+    fn nth(&mut self, n: usize) -> Option<A> {
+        let plus_n = self.start.add_usize(n).expect("overflow in RangeFrom::nth");
+        self.start = plus_n.add_one();
+        Some(plus_n)
+    }
 }
 
 #[unstable(feature = "fused", issue = "35602")]
-impl<A> FusedIterator for ops::RangeFrom<A>
-    where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}
+impl<A: Step> FusedIterator for ops::RangeFrom<A> {}
 
 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
-impl<A: Step> Iterator for ops::RangeInclusive<A> where
-    for<'a> &'a A: Add<&'a A, Output = A>
-{
+impl<A: Step> Iterator for ops::RangeInclusive<A> {
     type Item = A;
 
     #[inline]
@@ -389,18 +329,39 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> where
             return (0, Some(0));
         }
 
-        match Step::steps_between_by_one(&self.start, &self.end) {
+        match Step::steps_between(&self.start, &self.end) {
             Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
             None => (0, None),
         }
     }
+
+    #[inline]
+    fn nth(&mut self, n: usize) -> Option<A> {
+        if let Some(plus_n) = self.start.add_usize(n) {
+            use cmp::Ordering::*;
+
+            match plus_n.partial_cmp(&self.end) {
+                Some(Less) => {
+                    self.start = plus_n.add_one();
+                    return Some(plus_n)
+                }
+                Some(Equal) => {
+                    self.start.replace_one();
+                    self.end.replace_zero();
+                    return Some(plus_n)
+                }
+                _ => {}
+            }
+        }
+
+        self.start.replace_one();
+        self.end.replace_zero();
+        None
+    }
 }
 
 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
-impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> where
-    for<'a> &'a A: Add<&'a A, Output = A>,
-    for<'a> &'a A: Sub<&'a A, Output = A>
-{
+impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
     #[inline]
     fn next_back(&mut self) -> Option<A> {
         use cmp::Ordering::*;
@@ -421,5 +382,4 @@ impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> where
 }
 
 #[unstable(feature = "fused", issue = "35602")]
-impl<A> FusedIterator for ops::RangeInclusive<A>
-    where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}
+impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}
diff --git a/src/libcore/tests/iter.rs b/src/libcore/tests/iter.rs
index 14f0260f571..a1249a5f22c 100644
--- a/src/libcore/tests/iter.rs
+++ b/src/libcore/tests/iter.rs
@@ -1077,6 +1077,75 @@ fn test_range() {
 }
 
 #[test]
+fn test_range_inclusive_exhaustion() {
+    let mut r = 10...10;
+    assert_eq!(r.next(), Some(10));
+    assert_eq!(r, 1...0);
+
+    let mut r = 10...10;
+    assert_eq!(r.next_back(), Some(10));
+    assert_eq!(r, 1...0);
+
+    let mut r = 10...12;
+    assert_eq!(r.nth(2), Some(12));
+    assert_eq!(r, 1...0);
+
+    let mut r = 10...12;
+    assert_eq!(r.nth(5), None);
+    assert_eq!(r, 1...0);
+
+}
+
+#[test]
+fn test_range_nth() {
+    assert_eq!((10..15).nth(0), Some(10));
+    assert_eq!((10..15).nth(1), Some(11));
+    assert_eq!((10..15).nth(4), Some(14));
+    assert_eq!((10..15).nth(5), None);
+
+    let mut r = 10..20;
+    assert_eq!(r.nth(2), Some(12));
+    assert_eq!(r, 13..20);
+    assert_eq!(r.nth(2), Some(15));
+    assert_eq!(r, 16..20);
+    assert_eq!(r.nth(10), None);
+    assert_eq!(r, 20..20);
+}
+
+#[test]
+fn test_range_from_nth() {
+    assert_eq!((10..).nth(0), Some(10));
+    assert_eq!((10..).nth(1), Some(11));
+    assert_eq!((10..).nth(4), Some(14));
+
+    let mut r = 10..;
+    assert_eq!(r.nth(2), Some(12));
+    assert_eq!(r, 13..);
+    assert_eq!(r.nth(2), Some(15));
+    assert_eq!(r, 16..);
+    assert_eq!(r.nth(10), Some(26));
+    assert_eq!(r, 27..);
+}
+
+#[test]
+fn test_range_inclusive_nth() {
+    assert_eq!((10...15).nth(0), Some(10));
+    assert_eq!((10...15).nth(1), Some(11));
+    assert_eq!((10...15).nth(5), Some(15));
+    assert_eq!((10...15).nth(6), None);
+
+    let mut r = 10_u8...20;
+    assert_eq!(r.nth(2), Some(12));
+    assert_eq!(r, 13...20);
+    assert_eq!(r.nth(2), Some(15));
+    assert_eq!(r, 16...20);
+    assert_eq!(r.is_empty(), false);
+    assert_eq!(r.nth(10), None);
+    assert_eq!(r.is_empty(), true);
+    assert_eq!(r, 1...0);  // We may not want to document/promise this detail
+}
+
+#[test]
 fn test_range_step() {
     #![allow(deprecated)]
 
diff --git a/src/libcore/tests/lib.rs b/src/libcore/tests/lib.rs
index 8d3e367d237..26e4c21dc8f 100644
--- a/src/libcore/tests/lib.rs
+++ b/src/libcore/tests/lib.rs
@@ -18,12 +18,14 @@
 #![feature(core_private_diy_float)]
 #![feature(dec2flt)]
 #![feature(decode_utf8)]
+#![feature(exact_size_is_empty)]
 #![feature(fixed_size_array)]
 #![feature(flt2dec)]
 #![feature(fmt_internals)]
 #![feature(iterator_step_by)]
 #![feature(i128_type)]
 #![feature(inclusive_range)]
+#![feature(inclusive_range_syntax)]
 #![feature(iter_rfind)]
 #![feature(libc)]
 #![feature(nonzero)]
diff --git a/src/test/compile-fail/range-1.rs b/src/test/compile-fail/range-1.rs
index dc6833163a4..58794e3b35d 100644
--- a/src/test/compile-fail/range-1.rs
+++ b/src/test/compile-fail/range-1.rs
@@ -18,7 +18,6 @@ pub fn main() {
     // Bool => does not implement iterator.
     for i in false..true {}
     //~^ ERROR `bool: std::iter::Step` is not satisfied
-    //~^^ ERROR `for<'a> &'a bool: std::ops::Add` is not satisfied
 
     // Unsized type.
     let arr: &[_] = &[1, 2, 3];
diff --git a/src/test/run-pass/impl-trait/example-calendar.rs b/src/test/run-pass/impl-trait/example-calendar.rs
index 2a9af26881c..84d86cfdf65 100644
--- a/src/test/run-pass/impl-trait/example-calendar.rs
+++ b/src/test/run-pass/impl-trait/example-calendar.rs
@@ -162,22 +162,10 @@ impl<'a, 'b> std::ops::Add<&'b NaiveDate> for &'a NaiveDate {
 }
 
 impl std::iter::Step for NaiveDate {
-    fn step(&self, by: &Self) -> Option<Self> {
-        Some(self + by)
-    }
-
-    fn steps_between(_: &Self, _: &Self, _: &Self) -> Option<usize> {
-        unimplemented!()
-    }
-
-    fn steps_between_by_one(_: &Self, _: &Self) -> Option<usize> {
+    fn steps_between(_: &Self, _: &Self) -> Option<usize> {
         unimplemented!()
     }
 
-    fn is_negative(&self) -> bool {
-        false
-    }
-
     fn replace_one(&mut self) -> Self {
         mem::replace(self, NaiveDate(0, 0, 1))
     }
@@ -193,6 +181,10 @@ impl std::iter::Step for NaiveDate {
     fn sub_one(&self) -> Self {
         unimplemented!()
     }
+
+    fn add_usize(&self, _: usize) -> Option<Self> {
+        unimplemented!()
+    }
 }
 
 #[derive(Copy, Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]