From 95be21df477655131627def1943de73922b1f6a4 Mon Sep 17 00:00:00 2001
From: Ulrik Sverdrup <root@localhost>
Date: Mon, 27 Apr 2015 13:27:24 +0200
Subject: [PATCH] core: Fix size_hint for signed integer Range<T> iterators

There was an overflow bug in .size_hint() for signed iterators, which
produced an hilariously incorrect size or an overflow panic.

Incorrect size is a serious bug since the iterators are marked
ExactSizeIterator. (And leads to abort() on (-1i8..127).collect() when
the collection tries to preallocate too much).

All signed range iterators were affected.

> (-1i8..127).size_hint()
(18446744073709551488, Some(18446744073709551488))

Bug found using quickcheck.

Fixes #24851
---
 src/libcore/iter.rs     | 39 +++++++++++++++++++++++++++++++++++----
 src/libcoretest/iter.rs |  6 ++++++
 2 files changed, 41 insertions(+), 4 deletions(-)

diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs
index 233ed018119..5e98dd8b7df 100644
--- a/src/libcore/iter.rs
+++ b/src/libcore/iter.rs
@@ -2407,12 +2407,14 @@ pub trait Step: PartialOrd {
     /// `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
     /// without overflow.
     fn steps_between(start: &Self, end: &Self, by: &Self) -> Option<usize>;
 }
 
-macro_rules! step_impl {
+macro_rules! step_impl_unsigned {
     ($($t:ty)*) => ($(
         impl Step for $t {
             #[inline]
@@ -2423,7 +2425,33 @@ fn step(&self, by: &$t) -> Option<$t> {
             #[allow(trivial_numeric_casts)]
             fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
                 if *start <= *end {
-                    Some(((*end - *start) / *by) as usize)
+                    // Note: We assume $t <= usize here
+                    Some((*end - *start) as usize / (*by as usize))
+                } else {
+                    Some(0)
+                }
+            }
+        }
+    )*)
+}
+macro_rules! step_impl_signed {
+    ($($t:ty)*) => ($(
+        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 *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.
+                    Some(
+                        ((*end as isize).wrapping_sub(*start as isize) as usize
+                        / (*by as usize))
+                    )
                 } else {
                     Some(0)
                 }
@@ -2447,9 +2475,12 @@ fn steps_between(_a: &$t, _b: &$t, _by: &$t) -> Option<usize> {
     )*)
 }
 
-step_impl!(usize u8 u16 u32 isize i8 i16 i32);
+step_impl_unsigned!(usize u8 u16 u32);
+step_impl_signed!(isize i8 i16 i32);
+#[cfg(target_pointer_width = "64")]
+step_impl_unsigned!(u64);
 #[cfg(target_pointer_width = "64")]
-step_impl!(u64 i64);
+step_impl_signed!(i64);
 #[cfg(target_pointer_width = "32")]
 step_impl_no_between!(u64 i64);
 
diff --git a/src/libcoretest/iter.rs b/src/libcoretest/iter.rs
index 2866c193c3b..bb36630f168 100644
--- a/src/libcoretest/iter.rs
+++ b/src/libcoretest/iter.rs
@@ -11,6 +11,7 @@
 use core::iter::*;
 use core::iter::order::*;
 use core::iter::MinMaxResult::*;
+use core::isize;
 use core::usize;
 use core::cmp;
 
@@ -758,6 +759,11 @@ fn test_range() {
     assert_eq!((usize::MAX - 1..usize::MAX).size_hint(), (1, Some(1)));
     assert_eq!((-10..-1).size_hint(), (9, Some(9)));
     assert_eq!((-1..-10).size_hint(), (0, Some(0)));
+
+    assert_eq!((-70..58i8).size_hint(), (128, Some(128)));
+    assert_eq!((-128..127i8).size_hint(), (255, Some(255)));
+    assert_eq!((-2..isize::MAX).size_hint(),
+               (isize::MAX as usize + 2, Some(isize::MAX as usize + 2)));
 }
 
 #[test]
-- 
2.44.0