From 1246d4067fdc034d064dfb78f88c2c3c079c3f4f Mon Sep 17 00:00:00 2001 From: James Miller Date: Fri, 9 Jan 2015 16:10:57 +1300 Subject: Add `core::num::wrapping` and fix overflow errors. Many of the core rust libraries have places that rely on integer wrapping behaviour. These places have been altered to use the wrapping_* methods: * core::hash::sip - A number of macros * core::str - The `maximal_suffix` method in `TwoWaySearcher` * rustc::util::nodemap - Implementation of FnvHash * rustc_back::sha2 - A number of macros and other places * rand::isaac - Isaac64Rng, changed to use the Wrapping helper type Some places had "benign" underflow. This is when underflow or overflow occurs, but the unspecified value is not used due to other conditions. * collections::bit::Bitv - underflow when `self.nbits` is zero. * collections::hash::{map,table} - Underflow when searching an empty table. Did cause undefined behaviour in this case due to an out-of-bounds ptr::offset based on the underflowed index. However the resulting pointers would never be read from. * syntax::ext::deriving::encodable - Underflow when calculating the index of the last field in a variant with no fields. These cases were altered to avoid the underflow, often by moving the underflowing operation to a place where underflow could not happen. There was one case that relied on the fact that unsigned arithmetic and two's complement arithmetic are identical with wrapping semantics. This was changed to use the wrapping_* methods. Finally, the calculation of variant discriminants could overflow if the preceeding discriminant was `U64_MAX`. The logic in `rustc::middle::ty` for this was altered to avoid the overflow completely, while the remaining places were changed to use wrapping methods. This is because `rustc::middle::ty::enum_variants` now throws an error when the calculated discriminant value overflows a `u64`. This behaviour can be triggered by the following code: ``` enum Foo { A = U64_MAX, B } ``` This commit also implements the remaining integer operators for Wrapped. --- src/libstd/collections/hash/map.rs | 7 +++++++ src/libstd/collections/hash/table.rs | 6 +++++- src/libstd/num/mod.rs | 1 + src/libstd/prelude/v1.rs | 2 ++ 4 files changed, 15 insertions(+), 1 deletion(-) (limited to 'src/libstd') 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(table: M, M: Deref>, 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..908b5267b69 100644 --- a/src/libstd/collections/hash/table.rs +++ b/src/libstd/collections/hash/table.rs @@ -224,6 +224,9 @@ impl>> Bucket { } pub fn at_index(table: M, ib_index: usize) -> Bucket { + // 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 { @@ -368,10 +371,11 @@ impl>> FullBucket { /// In the cited blog posts above, this is called the "distance to /// initial bucket", or DIB. Also known as "probe count". pub fn distance(&self) -> usize { + use core::num::wrapping::WrappingOps; // 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] diff --git a/src/libstd/num/mod.rs b/src/libstd/num/mod.rs index d776079efae..d4428282b14 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; 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}; -- cgit 1.4.1-3-g733a5 From e7c986105f8af0b4ec4a91a63fbd1706282d401c Mon Sep 17 00:00:00 2001 From: "Felix S. Klock II" Date: Thu, 19 Feb 2015 08:33:32 +0100 Subject: Fixes to collections to accommodate arith-overflow changes. * `collections::btree::node`: accommodate (transient) underflow. * `collections::btree::map`: avoid underflow during `fn next` for `BTreeMap::range` methods. * `collections::slice`: note that pnkfelix deliberately used `new_pos_wrapping` only once; the other cases of arithmetic do not over- nor underflow, which is a useful property to leave implicitly checked/documented via the remaining calls to `fn new_pos(..)`. * `collections::vec_deque` applied wrapping ops (somewhat blindly) to two implementation methods, and many tests. * `std::collections::hash::table` : Use `OverflowingOps` trait to track overflow during `calculate_offsets` and `calculate_allocation` functions. --- src/libcollections/btree/map.rs | 4 +-- src/libcollections/btree/node.rs | 3 +- src/libcollections/slice.rs | 11 ++++-- src/libcollections/vec_deque.rs | 67 ++++++++++++++++++++++-------------- src/libstd/collections/hash/table.rs | 54 ++++++++++++++++------------- 5 files changed, 83 insertions(+), 56 deletions(-) (limited to 'src/libstd') diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs index 8a3a1fcb9f3..1fa592ac477 100644 --- a/src/libcollections/btree/map.rs +++ b/src/libcollections/btree/map.rs @@ -25,7 +25,7 @@ use core::fmt::Debug; use core::hash::{Hash, Hasher}; use core::iter::{Map, FromIterator, IntoIterator}; use core::ops::{Index, IndexMut}; -use core::{iter, fmt, mem}; +use core::{iter, fmt, mem, usize}; use Bound::{self, Included, Excluded, Unbounded}; use borrow::Borrow; @@ -1467,7 +1467,7 @@ macro_rules! range_impl { $Range { inner: AbsIter { traversals: traversals, - size: 0, // unused + size: usize::MAX, // unused } } } diff --git a/src/libcollections/btree/node.rs b/src/libcollections/btree/node.rs index 4a80d75575e..f2a6910a302 100644 --- a/src/libcollections/btree/node.rs +++ b/src/libcollections/btree/node.rs @@ -1215,7 +1215,8 @@ impl Node { ptr::copy( self.edges_mut().as_mut_ptr().offset(index as isize), self.edges().as_ptr().offset(index as isize + 1), - self.len() - index + 1 + // index can be == len+1, so do the +1 first to avoid underflow. + (self.len() + 1) - index ); edge diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs index a2924f8fe53..2660161c506 100644 --- a/src/libcollections/slice.rs +++ b/src/libcollections/slice.rs @@ -96,6 +96,7 @@ use core::iter::{range_step, MultiplicativeIterator}; use core::marker::Sized; use core::mem::size_of; use core::mem; +use core::num::wrapping::WrappingOps; use core::ops::FnMut; use core::option::Option::{self, Some, None}; use core::ptr::PtrExt; @@ -1209,10 +1210,14 @@ struct SizeDirection { impl Iterator for ElementSwaps { type Item = (usize, usize); - #[inline] + // #[inline] fn next(&mut self) -> Option<(usize, usize)> { + fn new_pos_wrapping(i: usize, s: Direction) -> usize { + i.wrapping_add(match s { Pos => 1, Neg => -1 }) + } + fn new_pos(i: usize, s: Direction) -> usize { - i + match s { Pos => 1, Neg => -1 } + match s { Pos => i + 1, Neg => i - 1 } } // Find the index of the largest mobile element: @@ -1220,7 +1225,7 @@ impl Iterator for ElementSwaps { // swap should be with a smaller `size` element. let max = self.sdir.iter().cloned().enumerate() .filter(|&(i, sd)| - new_pos(i, sd.dir) < self.sdir.len() && + new_pos_wrapping(i, sd.dir) < self.sdir.len() && self.sdir[new_pos(i, sd.dir)].size < sd.size) .max_by(|&(_, sd)| sd.size); match max { diff --git a/src/libcollections/vec_deque.rs b/src/libcollections/vec_deque.rs index abcc0cef9f1..3f086dd6247 100644 --- a/src/libcollections/vec_deque.rs +++ b/src/libcollections/vec_deque.rs @@ -26,6 +26,7 @@ use core::fmt; use core::iter::{self, repeat, FromIterator, IntoIterator, RandomAccessIterator}; use core::mem; use core::num::{Int, UnsignedInt}; +use core::num::wrapping::WrappingOps; use core::ops::{Index, IndexMut}; use core::ptr::{self, Unique}; use core::raw::Slice as RawSlice; @@ -120,6 +121,20 @@ impl VecDeque { #[inline] fn wrap_index(&self, idx: usize) -> usize { wrap_index(idx, self.cap) } + /// Returns the index in the underlying buffer for a given logical element + /// index + addend. + #[inline] + fn wrap_add(&self, idx: usize, addend: usize) -> usize { + wrap_index(idx.wrapping_add(addend), self.cap) + } + + /// Returns the index in the underlying buffer for a given logical element + /// index - subtrahend. + #[inline] + fn wrap_sub(&self, idx: usize, subtrahend: usize) -> usize { + wrap_index(idx.wrapping_sub(subtrahend), self.cap) + } + /// Copies a contiguous block of memory len long from src to dst #[inline] unsafe fn copy(&self, dst: usize, src: usize, len: usize) { @@ -197,7 +212,7 @@ impl VecDeque { #[stable(feature = "rust1", since = "1.0.0")] pub fn get(&self, i: usize) -> Option<&T> { if i < self.len() { - let idx = self.wrap_index(self.tail + i); + let idx = self.wrap_add(self.tail, i); unsafe { Some(&*self.ptr.offset(idx as isize)) } } else { None @@ -227,7 +242,7 @@ impl VecDeque { #[stable(feature = "rust1", since = "1.0.0")] pub fn get_mut(&mut self, i: usize) -> Option<&mut T> { if i < self.len() { - let idx = self.wrap_index(self.tail + i); + let idx = self.wrap_add(self.tail, i); unsafe { Some(&mut *self.ptr.offset(idx as isize)) } } else { None @@ -257,8 +272,8 @@ impl VecDeque { pub fn swap(&mut self, i: usize, j: usize) { assert!(i < self.len()); assert!(j < self.len()); - let ri = self.wrap_index(self.tail + i); - let rj = self.wrap_index(self.tail + j); + let ri = self.wrap_add(self.tail, i); + let rj = self.wrap_add(self.tail, j); unsafe { ptr::swap(self.ptr.offset(ri as isize), self.ptr.offset(rj as isize)) } @@ -427,7 +442,7 @@ impl VecDeque { // [. . . o o o o o o o . . . . . . ] // H T // [o o . o o o o o ] - let len = self.wrap_index(self.head - target_cap); + let len = self.wrap_sub(self.head, target_cap); unsafe { self.copy_nonoverlapping(0, target_cap, len); } @@ -438,7 +453,7 @@ impl VecDeque { // [o o o o o . . . . . . . . . o o ] // H T // [o o o o o . o o ] - debug_assert!(self.wrap_index(self.head - 1) < target_cap); + debug_assert!(self.wrap_sub(self.head, 1) < target_cap); let len = self.cap - self.tail; let new_tail = target_cap - len; unsafe { @@ -775,7 +790,7 @@ impl VecDeque { None } else { let tail = self.tail; - self.tail = self.wrap_index(self.tail + 1); + self.tail = self.wrap_add(self.tail, 1); unsafe { Some(self.buffer_read(tail)) } } } @@ -799,7 +814,7 @@ impl VecDeque { debug_assert!(!self.is_full()); } - self.tail = self.wrap_index(self.tail - 1); + self.tail = self.wrap_sub(self.tail, 1); let tail = self.tail; unsafe { self.buffer_write(tail, t); } } @@ -824,7 +839,7 @@ impl VecDeque { } let head = self.head; - self.head = self.wrap_index(self.head + 1); + self.head = self.wrap_add(self.head, 1); unsafe { self.buffer_write(head, t) } } @@ -847,7 +862,7 @@ impl VecDeque { if self.is_empty() { None } else { - self.head = self.wrap_index(self.head - 1); + self.head = self.wrap_sub(self.head, 1); let head = self.head; unsafe { Some(self.buffer_read(head)) } } @@ -971,7 +986,7 @@ impl VecDeque { // A - The element that should be after the insertion point // M - Indicates element was moved - let idx = self.wrap_index(self.tail + i); + let idx = self.wrap_add(self.tail, i); let distance_to_tail = i; let distance_to_head = self.len() - i; @@ -990,7 +1005,7 @@ impl VecDeque { // [A o o o o o o o . . . . . I] // - self.tail = self.wrap_index(self.tail - 1); + self.tail = self.wrap_sub(self.tail, 1); }, (true, true, _) => unsafe { // contiguous, insert closer to tail: @@ -1012,7 +1027,7 @@ impl VecDeque { // [o I A o o o o o . . . . . . . o] // M M - let new_tail = self.wrap_index(self.tail - 1); + let new_tail = self.wrap_sub(self.tail, 1); self.copy(new_tail, self.tail, 1); // Already moved the tail, so we only copy `i - 1` elements. @@ -1031,7 +1046,7 @@ impl VecDeque { // M M M self.copy(idx + 1, idx, self.head - idx); - self.head = self.wrap_index(self.head + 1); + self.head = self.wrap_add(self.head, 1); }, (false, true, true) => unsafe { // discontiguous, insert closer to tail, tail section: @@ -1123,7 +1138,7 @@ impl VecDeque { } // tail might've been changed so we need to recalculate - let new_idx = self.wrap_index(self.tail + i); + let new_idx = self.wrap_add(self.tail, i); unsafe { self.buffer_write(new_idx, t); } @@ -1170,7 +1185,7 @@ impl VecDeque { // R - Indicates element that is being removed // M - Indicates element was moved - let idx = self.wrap_index(self.tail + i); + let idx = self.wrap_add(self.tail, i); let elem = unsafe { Some(self.buffer_read(idx)) @@ -1219,7 +1234,7 @@ impl VecDeque { // M M self.copy(self.tail + 1, self.tail, i); - self.tail = self.wrap_index(self.tail + 1); + self.tail = self.wrap_add(self.tail, 1); }, (false, false, false) => unsafe { // discontiguous, remove closer to head, head section: @@ -1265,7 +1280,7 @@ impl VecDeque { self.copy(0, 1, self.head - 1); } - self.head = self.wrap_index(self.head - 1); + self.head = self.wrap_sub(self.head, 1); }, (false, true, false) => unsafe { // discontiguous, remove closer to tail, head section: @@ -1286,7 +1301,7 @@ impl VecDeque { // move elements from tail to end forward, excluding the last one self.copy(self.tail + 1, self.tail, self.cap - self.tail - 1); - self.tail = self.wrap_index(self.tail + 1); + self.tail = self.wrap_add(self.tail, 1); } } @@ -1354,7 +1369,7 @@ impl VecDeque { } // Cleanup where the ends of the buffers are - self.head = self.wrap_index(self.head - other_len); + self.head = self.wrap_sub(self.head, other_len); other.head = other.wrap_index(other_len); other @@ -1429,7 +1444,7 @@ fn wrap_index(index: usize, size: usize) -> usize { #[inline] fn count(tail: usize, head: usize, size: usize) -> usize { // size is always a power of 2 - (head - tail) & (size - 1) + (head.wrapping_sub(tail)) & (size - 1) } /// `VecDeque` iterator. @@ -1461,7 +1476,7 @@ impl<'a, T> Iterator for Iter<'a, T> { return None; } let tail = self.tail; - self.tail = wrap_index(self.tail + 1, self.ring.len()); + self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len()); unsafe { Some(self.ring.get_unchecked(tail)) } } @@ -1479,7 +1494,7 @@ impl<'a, T> DoubleEndedIterator for Iter<'a, T> { if self.tail == self.head { return None; } - self.head = wrap_index(self.head - 1, self.ring.len()); + self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len()); unsafe { Some(self.ring.get_unchecked(self.head)) } } } @@ -1500,7 +1515,7 @@ impl<'a, T> RandomAccessIterator for Iter<'a, T> { if j >= self.indexable() { None } else { - let idx = wrap_index(self.tail + j, self.ring.len()); + let idx = wrap_index(self.tail.wrapping_add(j), self.ring.len()); unsafe { Some(self.ring.get_unchecked(idx)) } } } @@ -1524,7 +1539,7 @@ impl<'a, T> Iterator for IterMut<'a, T> { return None; } let tail = self.tail; - self.tail = wrap_index(self.tail + 1, self.ring.len()); + self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len()); unsafe { let elem = self.ring.get_unchecked_mut(tail); @@ -1546,7 +1561,7 @@ impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { if self.tail == self.head { return None; } - self.head = wrap_index(self.head - 1, self.ring.len()); + self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len()); unsafe { let elem = self.ring.get_unchecked_mut(self.head); diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs index 908b5267b69..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}; @@ -371,7 +372,6 @@ impl>> FullBucket { /// In the cited blog posts above, this is called the "distance to /// initial bucket", or DIB. Also known as "probe count". pub fn distance(&self) -> usize { - use core::num::wrapping::WrappingOps; // 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. @@ -528,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, @@ -542,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 RawTable { @@ -591,12 +591,14 @@ impl RawTable { // 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::(), 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::().checked_add(size_of::()).unwrap() .checked_add(size_of::()).unwrap(); @@ -622,10 +624,11 @@ impl RawTable { let keys_size = self.capacity * size_of::(); let buffer = *self.hashes as *mut u8; - let (keys_offset, vals_offset) = calculate_offsets(hashes_size, - keys_size, min_align_of::(), - min_align_of::()); - + let (keys_offset, vals_offset, oflo) = + calculate_offsets(hashes_size, + keys_size, min_align_of::(), + min_align_of::()); + debug_assert!(!oflo, "capacity overflow"); unsafe { RawBucket { hash: *self.hashes, @@ -999,9 +1002,12 @@ impl Drop for RawTable { let hashes_size = self.capacity * size_of::(); let keys_size = self.capacity * size_of::(); let vals_size = self.capacity * size_of::(); - let (align, _, size) = calculate_allocation(hashes_size, min_align_of::(), - keys_size, min_align_of::(), - vals_size, min_align_of::()); + let (align, _, size, oflo) = + calculate_allocation(hashes_size, min_align_of::(), + keys_size, min_align_of::(), + vals_size, min_align_of::()); + + debug_assert!(!oflo, "should be impossible"); unsafe { deallocate(*self.hashes as *mut u8, size, align); -- cgit 1.4.1-3-g733a5 From c8db89aa82573b89481fde598da6e54371f266cb Mon Sep 17 00:00:00 2001 From: "Felix S. Klock II" Date: Thu, 19 Feb 2015 15:14:48 +0100 Subject: Accommodate arith-overflow in `core::num`, `std::num`, `coretest::num`. * `core::num`: adjust `UnsignedInt::is_power_of_two`, `UnsignedInt::next_power_of_two`, `Int::pow`. In particular for `Int::pow`: (1.) do not panic when `base` overflows if `acc` never observes the overflowed `base`, and (2.) if `acc` does observe the overflowed `base`, make sure we only panic if we would have otherwise (e.g. during a computation of `base * base`). * also in `core::num`: avoid underflow during computation of `uint::MAX`. * `std::num`: adjust tests `uint::test_uint_from_str_overflow`, `uint::test_uint_to_str_overflow`, `strconv` * `coretest::num`: adjust `test::test_int_from_str_overflow`. --- src/libcore/num/mod.rs | 26 +++++++++++++++++++++----- src/libcore/num/uint_macros.rs | 2 +- src/libcoretest/num/mod.rs | 8 ++++---- src/libstd/num/mod.rs | 16 ++++++++-------- src/libstd/num/strconv.rs | 9 +++++---- 5 files changed, 39 insertions(+), 22 deletions(-) (limited to 'src/libstd') diff --git a/src/libcore/num/mod.rs b/src/libcore/num/mod.rs index 3ed059520b1..92cdd84160b 100644 --- a/src/libcore/num/mod.rs +++ b/src/libcore/num/mod.rs @@ -15,6 +15,8 @@ #![stable(feature = "rust1", since = "1.0.0")] #![allow(missing_docs)] +use self::wrapping::{OverflowingOps, WrappingOps}; + use char::CharExt; use clone::Clone; use cmp::{PartialEq, Eq, PartialOrd, Ord}; @@ -51,6 +53,8 @@ pub trait Int + BitXor + Shl + Shr + + WrappingOps + + OverflowingOps { /// Returns the `0` value of this integer type. // FIXME (#5527): Should be an associated constant @@ -379,11 +383,23 @@ pub trait Int let mut base = self; let mut acc: Self = Int::one(); + let mut prev_base = self; + let mut base_oflo = false; while exp > 0 { if (exp & 1) == 1 { - acc = acc * base; + if base_oflo { + // ensure overflow occurs in the same manner it + // would have otherwise (i.e. signal any exception + // it would have otherwise). + acc = acc * (prev_base * prev_base); + } else { + acc = acc * base; + } } - base = base * base; + prev_base = base; + let (new_base, new_base_oflo) = base.overflowing_mul(base); + base = new_base; + base_oflo = new_base_oflo; exp /= 2; } acc @@ -694,12 +710,12 @@ signed_int_impl! { int } /// A built-in unsigned integer. #[stable(feature = "rust1", since = "1.0.0")] -pub trait UnsignedInt: Int { +pub trait UnsignedInt: Int + WrappingOps { /// Returns `true` iff `self == 2^k` for some `k`. #[stable(feature = "rust1", since = "1.0.0")] #[inline] fn is_power_of_two(self) -> bool { - (self - Int::one()) & self == Int::zero() && !(self == Int::zero()) + (self.wrapping_sub(Int::one())) & self == Int::zero() && !(self == Int::zero()) } /// Returns the smallest power of two greater than or equal to `self`. @@ -709,7 +725,7 @@ pub trait UnsignedInt: Int { fn next_power_of_two(self) -> Self { let bits = size_of::() * 8; let one: Self = Int::one(); - one << ((bits - (self - one).leading_zeros() as usize) % bits) + one << ((bits - self.wrapping_sub(one).leading_zeros() as usize) % bits) } /// Returns the smallest power of two greater than or equal to `n`. If the diff --git a/src/libcore/num/uint_macros.rs b/src/libcore/num/uint_macros.rs index 330f0b91bf1..d0c4885ad00 100644 --- a/src/libcore/num/uint_macros.rs +++ b/src/libcore/num/uint_macros.rs @@ -20,6 +20,6 @@ pub const BYTES : u32 = ($bits / 8); #[stable(feature = "rust1", since = "1.0.0")] pub const MIN: $T = 0 as $T; #[stable(feature = "rust1", since = "1.0.0")] -pub const MAX: $T = 0 as $T - 1 as $T; +pub const MAX: $T = !0 as $T; ) } diff --git a/src/libcoretest/num/mod.rs b/src/libcoretest/num/mod.rs index 1cd1989c11d..721354b6a44 100644 --- a/src/libcoretest/num/mod.rs +++ b/src/libcoretest/num/mod.rs @@ -92,7 +92,7 @@ mod test { assert_eq!("127".parse::().ok(), Some(i8_val)); assert_eq!("128".parse::().ok(), None); - i8_val += 1 as i8; + i8_val = i8_val.wrapping_add(1); assert_eq!("-128".parse::().ok(), Some(i8_val)); assert_eq!("-129".parse::().ok(), None); @@ -100,7 +100,7 @@ mod test { assert_eq!("32767".parse::().ok(), Some(i16_val)); assert_eq!("32768".parse::().ok(), None); - i16_val += 1 as i16; + i16_val = i16_val.wrapping_add(1); assert_eq!("-32768".parse::().ok(), Some(i16_val)); assert_eq!("-32769".parse::().ok(), None); @@ -108,7 +108,7 @@ mod test { assert_eq!("2147483647".parse::().ok(), Some(i32_val)); assert_eq!("2147483648".parse::().ok(), None); - i32_val += 1 as i32; + i32_val = i32_val.wrapping_add(1); assert_eq!("-2147483648".parse::().ok(), Some(i32_val)); assert_eq!("-2147483649".parse::().ok(), None); @@ -116,7 +116,7 @@ mod test { assert_eq!("9223372036854775807".parse::().ok(), Some(i64_val)); assert_eq!("9223372036854775808".parse::().ok(), None); - i64_val += 1 as i64; + i64_val = i64_val.wrapping_add(1); assert_eq!("-9223372036854775808".parse::().ok(), Some(i64_val)); assert_eq!("-9223372036854775809".parse::().ok(), None); } diff --git a/src/libstd/num/mod.rs b/src/libstd/num/mod.rs index d4428282b14..0bca60ed1a0 100644 --- a/src/libstd/num/mod.rs +++ b/src/libstd/num/mod.rs @@ -1758,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"); } @@ -1790,7 +1790,7 @@ mod tests { assert_eq!(from_str::("255"), Some(u8_val)); assert_eq!(from_str::("256"), None); - u8_val += 1 as u8; + u8_val = u8_val.wrapping_add(1); assert_eq!(from_str::("0"), Some(u8_val)); assert_eq!(from_str::("-1"), None); @@ -1798,7 +1798,7 @@ mod tests { assert_eq!(from_str::("65535"), Some(u16_val)); assert_eq!(from_str::("65536"), None); - u16_val += 1 as u16; + u16_val = u16_val.wrapping_add(1); assert_eq!(from_str::("0"), Some(u16_val)); assert_eq!(from_str::("-1"), None); @@ -1806,7 +1806,7 @@ mod tests { assert_eq!(from_str::("4294967295"), Some(u32_val)); assert_eq!(from_str::("4294967296"), None); - u32_val += 1 as u32; + u32_val = u32_val.wrapping_add(1); assert_eq!(from_str::("0"), Some(u32_val)); assert_eq!(from_str::("-1"), None); @@ -1814,7 +1814,7 @@ mod tests { assert_eq!(from_str::("18446744073709551615"), Some(u64_val)); assert_eq!(from_str::("18446744073709551616"), None); - u64_val += 1 as u64; + u64_val = u64_val.wrapping_add(1); assert_eq!(from_str::("0"), Some(u64_val)); assert_eq!(from_str::("-1"), None); } diff --git a/src/libstd/num/strconv.rs b/src/libstd/num/strconv.rs index ca2e6ba5d5d..8ec19c01098 100644 --- a/src/libstd/num/strconv.rs +++ b/src/libstd/num/strconv.rs @@ -427,6 +427,7 @@ static 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"); } } -- cgit 1.4.1-3-g733a5 From 6189e99c8605578aae841be6fba9e27bfbad97fc Mon Sep 17 00:00:00 2001 From: "Felix S. Klock II" Date: Fri, 20 Feb 2015 00:10:08 +0100 Subject: Accommodate arith-overflow in `rand` and `std::rand`. Regarding the `rand` changes: It is unfortunate that Wrapping(T) does not support the `+=` operator. We may want to try to fix that before 1.0 to make porting code like this palatable. Regarding `std::rand`, just arith-overflow in first example from `std::rand::random()` doc. --- src/librand/chacha.rs | 11 ++++--- src/librand/distributions/range.rs | 2 +- src/librand/isaac.rs | 62 ++++++++++++++++++++------------------ src/libstd/rand/mod.rs | 4 +-- 4 files changed, 41 insertions(+), 38 deletions(-) (limited to 'src/libstd') diff --git a/src/librand/chacha.rs b/src/librand/chacha.rs index 2673649f344..71ace016d6b 100644 --- a/src/librand/chacha.rs +++ b/src/librand/chacha.rs @@ -12,6 +12,7 @@ use core::prelude::*; use core::num::Int; +use core::num::wrapping::WrappingOps; use {Rng, SeedableRng, Rand}; const KEY_WORDS : uint = 8; // 8 words for the 256-bit key @@ -43,10 +44,10 @@ static EMPTY: ChaChaRng = ChaChaRng { macro_rules! quarter_round{ ($a: expr, $b: expr, $c: expr, $d: expr) => {{ - $a += $b; $d ^= $a; $d = $d.rotate_left(16); - $c += $d; $b ^= $c; $b = $b.rotate_left(12); - $a += $b; $d ^= $a; $d = $d.rotate_left( 8); - $c += $d; $b ^= $c; $b = $b.rotate_left( 7); + $a = $a.wrapping_add($b); $d = $d ^ $a; $d = $d.rotate_left(16); + $c = $c.wrapping_add($d); $b = $b ^ $c; $b = $b.rotate_left(12); + $a = $a.wrapping_add($b); $d = $d ^ $a; $d = $d.rotate_left( 8); + $c = $c.wrapping_add($d); $b = $b ^ $c; $b = $b.rotate_left( 7); }} } @@ -74,7 +75,7 @@ fn core(output: &mut [u32; STATE_WORDS], input: &[u32; STATE_WORDS]) { } for i in 0..STATE_WORDS { - output[i] += input[i]; + output[i] = output[i].wrapping_add(input[i]); } } diff --git a/src/librand/distributions/range.rs b/src/librand/distributions/range.rs index 04c67b16a7c..fb73a44c2b9 100644 --- a/src/librand/distributions/range.rs +++ b/src/librand/distributions/range.rs @@ -123,7 +123,7 @@ macro_rules! integer_impl { // be uniformly distributed) if v < r.accept_zone as $unsigned { // and return it, with some adjustments - return r.low + (v % r.range as $unsigned) as $ty; + return r.low.wrapping_add((v % r.range as $unsigned) as $ty); } } } diff --git a/src/librand/isaac.rs b/src/librand/isaac.rs index 63eb8417655..6bc00abd85f 100644 --- a/src/librand/isaac.rs +++ b/src/librand/isaac.rs @@ -13,6 +13,7 @@ use core::prelude::*; use core::slice; use core::iter::{range_step, repeat}; +use core::num::wrapping::Wrapping; use {Rng, SeedableRng, Rand}; @@ -60,7 +61,7 @@ impl IsaacRng { /// of `rsl` as a seed, otherwise construct one algorithmically (not /// randomly). fn init(&mut self, use_rsl: bool) { - let mut a = 0x9e3779b9; + let mut a = Wrapping(0x9e3779b9); let mut b = a; let mut c = a; let mut d = a; @@ -71,14 +72,14 @@ impl IsaacRng { macro_rules! mix { () => {{ - a^=b<<11; d+=a; b+=c; - b^=c>>2; e+=b; c+=d; - c^=d<<8; f+=c; d+=e; - d^=e>>16; g+=d; e+=f; - e^=f<<10; h+=e; f+=g; - f^=g>>4; a+=f; g+=h; - g^=h<<8; b+=g; h+=a; - h^=a>>9; c+=h; a+=b; + a=a^(b<<11); d=d+a; b=b+c; + b=b^(c>>2); e=e+b; c=c+d; + c=c^(d<<8); f=f+c; d=d+e; + d=d^(e>>16); g=g+d; e=e+f; + e=e^(f<<10); h=h+e; f=f+g; + f=f^(g>>4); a=a+f; g=g+h; + g=g^(h<<8); b=b+g; h=h+a; + h=h^(a>>9); c=c+h; a=a+b; }} } @@ -90,15 +91,15 @@ impl IsaacRng { macro_rules! memloop { ($arr:expr) => {{ for i in range_step(0, RAND_SIZE as uint, 8) { - a+=$arr[i ]; b+=$arr[i+1]; - c+=$arr[i+2]; d+=$arr[i+3]; - e+=$arr[i+4]; f+=$arr[i+5]; - g+=$arr[i+6]; h+=$arr[i+7]; + a=a+Wrapping($arr[i ]); b=b+Wrapping($arr[i+1]); + c=c+Wrapping($arr[i+2]); d=d+Wrapping($arr[i+3]); + e=e+Wrapping($arr[i+4]); f=f+Wrapping($arr[i+5]); + g=g+Wrapping($arr[i+6]); h=h+Wrapping($arr[i+7]); mix!(); - self.mem[i ]=a; self.mem[i+1]=b; - self.mem[i+2]=c; self.mem[i+3]=d; - self.mem[i+4]=e; self.mem[i+5]=f; - self.mem[i+6]=g; self.mem[i+7]=h; + self.mem[i ]=a.0; self.mem[i+1]=b.0; + self.mem[i+2]=c.0; self.mem[i+3]=d.0; + self.mem[i+4]=e.0; self.mem[i+5]=f.0; + self.mem[i+6]=g.0; self.mem[i+7]=h.0; } }} } @@ -108,10 +109,10 @@ impl IsaacRng { } else { for i in range_step(0, RAND_SIZE as uint, 8) { mix!(); - self.mem[i ]=a; self.mem[i+1]=b; - self.mem[i+2]=c; self.mem[i+3]=d; - self.mem[i+4]=e; self.mem[i+5]=f; - self.mem[i+6]=g; self.mem[i+7]=h; + self.mem[i ]=a.0; self.mem[i+1]=b.0; + self.mem[i+2]=c.0; self.mem[i+3]=d.0; + self.mem[i+4]=e.0; self.mem[i+5]=f.0; + self.mem[i+6]=g.0; self.mem[i+7]=h.0; } } @@ -130,7 +131,8 @@ impl IsaacRng { static MIDPOINT: uint = (RAND_SIZE / 2) as uint; macro_rules! ind { - ($x:expr) => ( self.mem[(($x >> 2) as uint & ((RAND_SIZE - 1) as uint))] ) + ($x:expr) => (Wrapping( self.mem[(($x >> 2) as uint & + ((RAND_SIZE - 1) as uint))] )) } let r = [(0, MIDPOINT), (MIDPOINT, 0)]; @@ -142,11 +144,11 @@ impl IsaacRng { let mix = a << $shift as uint; let x = self.mem[base + mr_offset]; - a = (a ^ mix) + self.mem[base + m2_offset]; - let y = ind!(x) + a + b; - self.mem[base + mr_offset] = y; + a = (Wrapping(a ^ mix) + Wrapping(self.mem[base + m2_offset])).0; + let y = ind!(x) + Wrapping(a) + Wrapping(b); + self.mem[base + mr_offset] = y.0; - b = ind!(y >> RAND_SIZE_LEN as uint) + x; + b = (ind!(y.0 >> RAND_SIZE_LEN as uint) + Wrapping(x)).0; self.rsl[base + mr_offset] = b; }} } @@ -157,11 +159,11 @@ impl IsaacRng { let mix = a >> $shift as uint; let x = self.mem[base + mr_offset]; - a = (a ^ mix) + self.mem[base + m2_offset]; - let y = ind!(x) + a + b; - self.mem[base + mr_offset] = y; + a = (Wrapping(a ^ mix) + Wrapping(self.mem[base + m2_offset])).0; + let y = ind!(x) + Wrapping(a) + Wrapping(b); + self.mem[base + mr_offset] = y.0; - b = ind!(y >> RAND_SIZE_LEN as uint) + x; + b = (ind!(y.0 >> RAND_SIZE_LEN as uint) + Wrapping(x)).0; self.rsl[base + mr_offset] = b; }} } diff --git a/src/libstd/rand/mod.rs b/src/libstd/rand/mod.rs index 5c891441198..ac7622fc7f7 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::(); /// println!("{}", y); -- cgit 1.4.1-3-g733a5 From 185c074798ce87429118868c292d2c2c7dc46cfc Mon Sep 17 00:00:00 2001 From: Manish Goregaokar Date: Mon, 2 Mar 2015 16:11:01 +0530 Subject: Fix backtrace tests for Linux --- src/libstd/sys/unix/backtrace.rs | 2 +- src/test/run-pass/backtrace-debuginfo.rs | 8 ++++---- 2 files changed, 5 insertions(+), 5 deletions(-) (limited to 'src/libstd') diff --git a/src/libstd/sys/unix/backtrace.rs b/src/libstd/sys/unix/backtrace.rs index 3695b615f62..0b8b43413e9 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 _; diff --git a/src/test/run-pass/backtrace-debuginfo.rs b/src/test/run-pass/backtrace-debuginfo.rs index a2a63d44a78..23aadbc7053 100644 --- a/src/test/run-pass/backtrace-debuginfo.rs +++ b/src/test/run-pass/backtrace-debuginfo.rs @@ -68,7 +68,7 @@ fn dump_filelines(filelines: &[Pos]) { } #[inline(never)] -fn inner(counter: &mut u32, main_pos: Pos, outer_pos: Pos) { +fn inner(counter: &mut i32, main_pos: Pos, outer_pos: Pos) { check!(counter; main_pos, outer_pos); check!(counter; main_pos, outer_pos); let inner_pos = pos!(); aux::callback(|aux_pos| { @@ -80,12 +80,12 @@ fn inner(counter: &mut u32, main_pos: Pos, outer_pos: Pos) { } #[inline(always)] -fn inner_inlined(counter: &mut u32, main_pos: Pos, outer_pos: Pos) { +fn inner_inlined(counter: &mut i32, main_pos: Pos, outer_pos: Pos) { check!(counter; main_pos, outer_pos); check!(counter; main_pos, outer_pos); #[inline(always)] - fn inner_further_inlined(counter: &mut u32, main_pos: Pos, outer_pos: Pos, inner_pos: Pos) { + fn inner_further_inlined(counter: &mut i32, main_pos: Pos, outer_pos: Pos, inner_pos: Pos) { check!(counter; main_pos, outer_pos, inner_pos); } inner_further_inlined(counter, main_pos, outer_pos, pos!()); @@ -103,7 +103,7 @@ fn inner_inlined(counter: &mut u32, main_pos: Pos, outer_pos: Pos) { } #[inline(never)] -fn outer(mut counter: u32, main_pos: Pos) { +fn outer(mut counter: i32, main_pos: Pos) { inner(&mut counter, main_pos, pos!()); inner_inlined(&mut counter, main_pos, pos!()); } -- cgit 1.4.1-3-g733a5 From 243c5164ea32b38c4ac44fdd5e0ceb2da45c283f Mon Sep 17 00:00:00 2001 From: "Felix S. Klock II" Date: Tue, 3 Mar 2015 12:07:48 +0100 Subject: sidestep potential over- and underflow in estimated stack bounds. See buildlog here for evidence of such occurring: http://buildbot.rust-lang.org/builders/auto-linux-32-opt/builds/3910/steps/test/logs/stdio --- src/libstd/rt/mod.rs | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-) (limited to 'src/libstd') 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, -- cgit 1.4.1-3-g733a5