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<T>.

4 files changed, 15 insertions, 1 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..908b5267b69 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -224,6 +224,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 {
@@ -368,10 +371,11 @@ 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.
-        (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};