iterator: Add `StepBy::size_hint` method

Fixes `Step::steps_between` implementations by integer types
to correctly handle `by != 1`.

1 files changed, 41 insertions, 15 deletions

diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs
index 0fa27a4312d..20720b93641 100644
--- a/src/libcore/iter.rs
+++ b/src/libcore/iter.rs
@@ -2402,14 +2402,10 @@ pub trait Step: PartialOrd {
     /// Steps `self` if possible.
     fn step(&self, by: &Self) -> Option<Self>;
 
-    /// Returns the number of steps between two step objects.
+    /// Returns the number of steps between two step objects. The count is
+    /// inclusive of `start` and exclusive of `end`.
     ///
-    /// `start` should always be less than `end`, so the result should never
-    /// be negative.
-    ///
-    /// `by` must be > 0.
-    ///
-    /// Returns `None` if it is not possible to calculate steps_between
+    /// Returns `None` if it is not possible to calculate `steps_between`
     /// without overflow.
     fn steps_between(start: &Self, end: &Self, by: &Self) -> Option<usize>;
 }
@@ -2424,9 +2420,16 @@ macro_rules! step_impl_unsigned {
             #[inline]
             #[allow(trivial_numeric_casts)]
             fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
-                if *start <= *end {
+                if *by == 0 { return None; }
+                if *start < *end {
                     // Note: We assume $t <= usize here
-                    Some((*end - *start) as usize / (*by as usize))
+                    let diff = (*end - *start) as usize;
+                    let by = *by as usize;
+                    if diff % by > 0 {
+                        Some(diff / by + 1)
+                    } else {
+                        Some(diff / by)
+                    }
                 } else {
                     Some(0)
                 }
@@ -2444,16 +2447,29 @@ macro_rules! step_impl_signed {
             #[inline]
             #[allow(trivial_numeric_casts)]
             fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
-                if *start <= *end {
+                if *by == 0 { return None; }
+                let mut diff: usize;
+                let mut by_u: usize;
+                if *by > 0 {
+                    if *start >= *end {
+                        return Some(0);
+                    }
                     // 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.
-                    Some(
-                        ((*end as isize).wrapping_sub(*start as isize) as usize
-                        / (*by as usize))
-                    )
+                    diff = (*end as isize).wrapping_sub(*start as isize) as usize;
+                    by_u = *by as usize;
                 } else {
-                    Some(0)
+                    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)
+                } else {
+                    Some(diff / by_u)
                 }
             }
         }
@@ -2675,6 +2691,16 @@ impl<A: Step + Zero + Clone> Iterator for StepBy<A, ops::Range<A>> {
             None
         }
     }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        match Step::steps_between(&self.range.start,
+                                  &self.range.end,
+                                  &self.step_by) {
+            Some(hint) => (hint, Some(hint)),
+            None       => (0, None)
+        }
+    }
 }
 
 macro_rules! range_exact_iter_impl {