Auto merge of #22532 - pnkfelix:arith-overflow, r=pnkfelix,eddyb

Rebase and follow-through on work done by @cmr and @aatch.

Implements most of rust-lang/rfcs#560. Errors encountered from the checks during building were fixed.

The checks for division, remainder and bit-shifting have not been implemented yet.

See also PR #20795

cc @Aatch ; cc @nikomatsakis

8 files changed, 75 insertions, 40 deletions

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index faddbba5059..8eb29a8327a 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -314,6 +314,13 @@ fn search_hashed<K, V, M, F>(table: M,
     M: Deref<Target=RawTable<K, V>>,
     F: FnMut(&K) -> bool,
 {
+    // This is the only function where capacity can be zero. To avoid
+    // undefined behaviour when Bucket::new gets the raw bucket in this
+    // case, immediately return the appropriate search result.
+    if table.capacity() == 0 {
+        return TableRef(table);
+    }
+
     let size = table.size();
     let mut probe = Bucket::new(table, hash);
     let ib = probe.index();
diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index 4c03d8915eb..2670cd0c003 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -20,6 +20,7 @@ use marker::{Copy, Send, Sync, Sized, self};
 use mem::{min_align_of, size_of};
 use mem;
 use num::{Int, UnsignedInt};
+use num::wrapping::{OverflowingOps, WrappingOps};
 use ops::{Deref, DerefMut, Drop};
 use option::Option;
 use option::Option::{Some, None};
@@ -224,6 +225,9 @@ impl<K, V, M: Deref<Target=RawTable<K, V>>> Bucket<K, V, M> {
     }
 
     pub fn at_index(table: M, ib_index: usize) -> Bucket<K, V, M> {
+        // if capacity is 0, then the RawBucket will be populated with bogus pointers.
+        // This is an uncommon case though, so avoid it in release builds.
+        debug_assert!(table.capacity() > 0, "Table should have capacity at this point");
         let ib_index = ib_index & (table.capacity() - 1);
         Bucket {
             raw: unsafe {
@@ -371,7 +375,7 @@ impl<K, V, M: Deref<Target=RawTable<K, V>>> FullBucket<K, V, M> {
         // Calculates the distance one has to travel when going from
         // `hash mod capacity` onwards to `idx mod capacity`, wrapping around
         // if the destination is not reached before the end of the table.
-        (self.idx - self.hash().inspect() as usize) & (self.table.capacity() - 1)
+        (self.idx.wrapping_sub(self.hash().inspect() as usize)) & (self.table.capacity() - 1)
     }
 
     #[inline]
@@ -524,13 +528,13 @@ fn test_rounding() {
 fn calculate_offsets(hashes_size: usize,
                      keys_size: usize, keys_align: usize,
                      vals_align: usize)
-                     -> (usize, usize) {
+                     -> (usize, usize, bool) {
     let keys_offset = round_up_to_next(hashes_size, keys_align);
-    let end_of_keys = keys_offset + keys_size;
+    let (end_of_keys, oflo) = keys_offset.overflowing_add(keys_size);
 
     let vals_offset = round_up_to_next(end_of_keys, vals_align);
 
-    (keys_offset, vals_offset)
+    (keys_offset, vals_offset, oflo)
 }
 
 // Returns a tuple of (minimum required malloc alignment, hash_offset,
@@ -538,26 +542,26 @@ fn calculate_offsets(hashes_size: usize,
 fn calculate_allocation(hash_size: usize, hash_align: usize,
                         keys_size: usize, keys_align: usize,
                         vals_size: usize, vals_align: usize)
-                        -> (usize, usize, usize) {
+                        -> (usize, usize, usize, bool) {
     let hash_offset = 0;
-    let (_, vals_offset) = calculate_offsets(hash_size,
-                                             keys_size, keys_align,
-                                                        vals_align);
-    let end_of_vals = vals_offset + vals_size;
+    let (_, vals_offset, oflo) = calculate_offsets(hash_size,
+                                                   keys_size, keys_align,
+                                                              vals_align);
+    let (end_of_vals, oflo2) = vals_offset.overflowing_add(vals_size);
 
     let min_align = cmp::max(hash_align, cmp::max(keys_align, vals_align));
 
-    (min_align, hash_offset, end_of_vals)
+    (min_align, hash_offset, end_of_vals, oflo || oflo2)
 }
 
 #[test]
 fn test_offset_calculation() {
-    assert_eq!(calculate_allocation(128, 8, 15, 1, 4,  4), (8, 0, 148));
-    assert_eq!(calculate_allocation(3,   1, 2,  1, 1,  1), (1, 0, 6));
-    assert_eq!(calculate_allocation(6,   2, 12, 4, 24, 8), (8, 0, 48));
-    assert_eq!(calculate_offsets(128, 15, 1, 4), (128, 144));
-    assert_eq!(calculate_offsets(3,   2,  1, 1), (3,   5));
-    assert_eq!(calculate_offsets(6,   12, 4, 8), (8,   24));
+    assert_eq!(calculate_allocation(128, 8, 15, 1, 4,  4), (8, 0, 148, false));
+    assert_eq!(calculate_allocation(3,   1, 2,  1, 1,  1), (1, 0, 6, false));
+    assert_eq!(calculate_allocation(6,   2, 12, 4, 24, 8), (8, 0, 48, false));
+    assert_eq!(calculate_offsets(128, 15, 1, 4), (128, 144, false));
+    assert_eq!(calculate_offsets(3,   2,  1, 1), (3,   5, false));
+    assert_eq!(calculate_offsets(6,   12, 4, 8), (8,   24, false));
 }
 
 impl<K, V> RawTable<K, V> {
@@ -587,12 +591,14 @@ impl<K, V> RawTable<K, V> {
         // This is great in theory, but in practice getting the alignment
         // right is a little subtle. Therefore, calculating offsets has been
         // factored out into a different function.
-        let (malloc_alignment, hash_offset, size) =
+        let (malloc_alignment, hash_offset, size, oflo) =
             calculate_allocation(
                 hashes_size, min_align_of::<u64>(),
                 keys_size,   min_align_of::< K >(),
                 vals_size,   min_align_of::< V >());
 
+        assert!(!oflo, "capacity overflow");
+
         // One check for overflow that covers calculation and rounding of size.
         let size_of_bucket = size_of::<u64>().checked_add(size_of::<K>()).unwrap()
                                              .checked_add(size_of::<V>()).unwrap();
@@ -618,10 +624,11 @@ impl<K, V> RawTable<K, V> {
         let keys_size = self.capacity * size_of::<K>();
 
         let buffer = *self.hashes as *mut u8;
-        let (keys_offset, vals_offset) = calculate_offsets(hashes_size,
-                                                           keys_size, min_align_of::<K>(),
-                                                           min_align_of::<V>());
-
+        let (keys_offset, vals_offset, oflo) =
+            calculate_offsets(hashes_size,
+                              keys_size, min_align_of::<K>(),
+                              min_align_of::<V>());
+        debug_assert!(!oflo, "capacity overflow");
         unsafe {
             RawBucket {
                 hash: *self.hashes,
@@ -995,9 +1002,12 @@ impl<K, V> Drop for RawTable<K, V> {
         let hashes_size = self.capacity * size_of::<u64>();
         let keys_size = self.capacity * size_of::<K>();
         let vals_size = self.capacity * size_of::<V>();
-        let (align, _, size) = calculate_allocation(hashes_size, min_align_of::<u64>(),
-                                                    keys_size, min_align_of::<K>(),
-                                                    vals_size, min_align_of::<V>());
+        let (align, _, size, oflo) =
+            calculate_allocation(hashes_size, min_align_of::<u64>(),
+                                 keys_size, min_align_of::<K>(),
+                                 vals_size, min_align_of::<V>());
+
+        debug_assert!(!oflo, "should be impossible");
 
         unsafe {
             deallocate(*self.hashes as *mut u8, size, align);
diff --git a/src/libstd/num/mod.rs b/src/libstd/num/mod.rs
index d776079efae..0bca60ed1a0 100644
--- a/src/libstd/num/mod.rs
+++ b/src/libstd/num/mod.rs
@@ -30,6 +30,7 @@ pub use core::num::{from_uint, from_u8, from_u16, from_u32, from_u64};
 pub use core::num::{from_f32, from_f64};
 pub use core::num::{FromStrRadix, from_str_radix};
 pub use core::num::{FpCategory, ParseIntError, ParseFloatError};
+pub use core::num::wrapping;
 
 use option::Option;
 
@@ -1757,25 +1758,25 @@ mod tests {
         let mut u8_val: u8 = 255_u8;
         assert_eq!(u8_val.to_string(), "255");
 
-        u8_val += 1 as u8;
+        u8_val = u8_val.wrapping_add(1);
         assert_eq!(u8_val.to_string(), "0");
 
         let mut u16_val: u16 = 65_535_u16;
         assert_eq!(u16_val.to_string(), "65535");
 
-        u16_val += 1 as u16;
+        u16_val = u16_val.wrapping_add(1);
         assert_eq!(u16_val.to_string(), "0");
 
         let mut u32_val: u32 = 4_294_967_295_u32;
         assert_eq!(u32_val.to_string(), "4294967295");
 
-        u32_val += 1 as u32;
+        u32_val = u32_val.wrapping_add(1);
         assert_eq!(u32_val.to_string(), "0");
 
         let mut u64_val: u64 = 18_446_744_073_709_551_615_u64;
         assert_eq!(u64_val.to_string(), "18446744073709551615");
 
-        u64_val += 1 as u64;
+        u64_val = u64_val.wrapping_add(1);
         assert_eq!(u64_val.to_string(), "0");
     }
 
@@ -1789,7 +1790,7 @@ mod tests {
         assert_eq!(from_str::<u8>("255"), Some(u8_val));
         assert_eq!(from_str::<u8>("256"), None);
 
-        u8_val += 1 as u8;
+        u8_val = u8_val.wrapping_add(1);
         assert_eq!(from_str::<u8>("0"), Some(u8_val));
         assert_eq!(from_str::<u8>("-1"), None);
 
@@ -1797,7 +1798,7 @@ mod tests {
         assert_eq!(from_str::<u16>("65535"), Some(u16_val));
         assert_eq!(from_str::<u16>("65536"), None);
 
-        u16_val += 1 as u16;
+        u16_val = u16_val.wrapping_add(1);
         assert_eq!(from_str::<u16>("0"), Some(u16_val));
         assert_eq!(from_str::<u16>("-1"), None);
 
@@ -1805,7 +1806,7 @@ mod tests {
         assert_eq!(from_str::<u32>("4294967295"), Some(u32_val));
         assert_eq!(from_str::<u32>("4294967296"), None);
 
-        u32_val += 1 as u32;
+        u32_val = u32_val.wrapping_add(1);
         assert_eq!(from_str::<u32>("0"), Some(u32_val));
         assert_eq!(from_str::<u32>("-1"), None);
 
@@ -1813,7 +1814,7 @@ mod tests {
         assert_eq!(from_str::<u64>("18446744073709551615"), Some(u64_val));
         assert_eq!(from_str::<u64>("18446744073709551616"), None);
 
-        u64_val += 1 as u64;
+        u64_val = u64_val.wrapping_add(1);
         assert_eq!(from_str::<u64>("0"), Some(u64_val));
         assert_eq!(from_str::<u64>("-1"), None);
     }
diff --git a/src/libstd/num/strconv.rs b/src/libstd/num/strconv.rs
index a9fdeed13f0..b38c52dad1a 100644
--- a/src/libstd/num/strconv.rs
+++ b/src/libstd/num/strconv.rs
@@ -427,6 +427,7 @@ const DIGIT_E_RADIX: u32 = ('e' as u32) - ('a' as u32) + 11;
 
 #[cfg(test)]
 mod tests {
+    use core::num::wrapping::WrappingOps;
     use string::ToString;
 
     #[test]
@@ -434,25 +435,25 @@ mod tests {
         let mut i8_val: i8 = 127_i8;
         assert_eq!(i8_val.to_string(), "127");
 
-        i8_val += 1 as i8;
+        i8_val = i8_val.wrapping_add(1);
         assert_eq!(i8_val.to_string(), "-128");
 
         let mut i16_val: i16 = 32_767_i16;
         assert_eq!(i16_val.to_string(), "32767");
 
-        i16_val += 1 as i16;
+        i16_val = i16_val.wrapping_add(1);
         assert_eq!(i16_val.to_string(), "-32768");
 
         let mut i32_val: i32 = 2_147_483_647_i32;
         assert_eq!(i32_val.to_string(), "2147483647");
 
-        i32_val += 1 as i32;
+        i32_val = i32_val.wrapping_add(1);
         assert_eq!(i32_val.to_string(), "-2147483648");
 
         let mut i64_val: i64 = 9_223_372_036_854_775_807_i64;
         assert_eq!(i64_val.to_string(), "9223372036854775807");
 
-        i64_val += 1 as i64;
+        i64_val = i64_val.wrapping_add(1);
         assert_eq!(i64_val.to_string(), "-9223372036854775808");
     }
 }
diff --git a/src/libstd/prelude/v1.rs b/src/libstd/prelude/v1.rs
index dad0ff0a15e..60e1354482c 100644
--- a/src/libstd/prelude/v1.rs
+++ b/src/libstd/prelude/v1.rs
@@ -58,3 +58,5 @@
 #[doc(no_inline)] pub use old_io::{Buffer, Writer, Reader, Seek, BufferPrelude};
 // NB: remove when range syntax lands
 #[doc(no_inline)] pub use iter::range;
+
+#[doc(no_inline)] pub use num::wrapping::{Wrapping, WrappingOps};
diff --git a/src/libstd/rand/mod.rs b/src/libstd/rand/mod.rs
index 7fe20c37c6c..a49db012882 100644
--- a/src/libstd/rand/mod.rs
+++ b/src/libstd/rand/mod.rs
@@ -386,8 +386,8 @@ impl Rng for ThreadRng {
 /// ```
 /// use std::rand;
 ///
-/// let x = rand::random();
-/// println!("{}", 2u8 * x);
+/// let x: u8 = rand::random();
+/// println!("{}", 2 * x as u16);
 ///
 /// let y = rand::random::<f64>();
 /// println!("{}", y);
diff --git a/src/libstd/rt/mod.rs b/src/libstd/rt/mod.rs
index 42cca73e5e2..fe32a51e81c 100644
--- a/src/libstd/rt/mod.rs
+++ b/src/libstd/rt/mod.rs
@@ -27,6 +27,7 @@ use marker::Send;
 use ops::FnOnce;
 use sys;
 use thunk::Thunk;
+use usize;
 
 // Reexport some of our utilities which are expected by other crates.
 pub use self::util::{default_sched_threads, min_stack, running_on_valgrind};
@@ -78,7 +79,20 @@ fn lang_start(main: *const u8, argc: int, argv: *const *const u8) -> int {
     // FIXME #11359 we just assume that this thread has a stack of a
     // certain size, and estimate that there's at most 20KB of stack
     // frames above our current position.
-    let my_stack_bottom = my_stack_top + 20000 - OS_DEFAULT_STACK_ESTIMATE;
+    const TWENTY_KB: uint = 20000;
+
+    // saturating-add to sidestep overflow
+    let top_plus_spill = if usize::MAX - TWENTY_KB < my_stack_top {
+        usize::MAX
+    } else {
+        my_stack_top + TWENTY_KB
+    };
+    // saturating-sub to sidestep underflow
+    let my_stack_bottom = if top_plus_spill < OS_DEFAULT_STACK_ESTIMATE {
+        0
+    } else {
+        top_plus_spill - OS_DEFAULT_STACK_ESTIMATE
+    };
 
     let failed = unsafe {
         // First, make sure we don't trigger any __morestack overflow checks,
diff --git a/src/libstd/sys/unix/backtrace.rs b/src/libstd/sys/unix/backtrace.rs
index d78cfd0ca37..e7ac6e2cd01 100644
--- a/src/libstd/sys/unix/backtrace.rs
+++ b/src/libstd/sys/unix/backtrace.rs
@@ -176,7 +176,7 @@ pub fn write(w: &mut Writer) -> IoResult<()> {
         let mut ip = unsafe {
             uw::_Unwind_GetIPInfo(ctx, &mut ip_before_insn) as *mut libc::c_void
         };
-        if ip_before_insn == 0 {
+        if !ip.is_null() && ip_before_insn == 0 {
             // this is a non-signaling frame, so `ip` refers to the address
             // after the calling instruction. account for that.
             ip = (ip as usize - 1) as *mut _;