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.

1 files changed, 30 insertions, 24 deletions

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<K, V, M: Deref<Target=RawTable<K, V>>> FullBucket<K, V, M> {
     /// 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<K, V> RawTable<K, V> {
@@ -591,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();
@@ -622,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,
@@ -999,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);