add libcore from 2016-04-11 nightly

2 files changed, 619 insertions, 0 deletions

diff --git a/libcore/hash/mod.rs b/libcore/hash/mod.rs
new file mode 100644
index 0000000..4d0fed9
--- /dev/null
+++ b/libcore/hash/mod.rs
@@ -0,0 +1,380 @@
+// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! Generic hashing support.
+//!
+//! This module provides a generic way to compute the hash of a value. The
+//! simplest way to make a type hashable is to use `#[derive(Hash)]`:
+//!
+//! # Examples
+//!
+//! ```rust
+//! use std::hash::{Hash, SipHasher, Hasher};
+//!
+//! #[derive(Hash)]
+//! struct Person {
+//!     id: u32,
+//!     name: String,
+//!     phone: u64,
+//! }
+//!
+//! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 };
+//! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 };
+//!
+//! assert!(hash(&person1) != hash(&person2));
+//!
+//! fn hash<T: Hash>(t: &T) -> u64 {
+//!     let mut s = SipHasher::new();
+//!     t.hash(&mut s);
+//!     s.finish()
+//! }
+//! ```
+//!
+//! If you need more control over how a value is hashed, you need to implement
+//! the trait `Hash`:
+//!
+//! ```rust
+//! use std::hash::{Hash, Hasher, SipHasher};
+//!
+//! struct Person {
+//!     id: u32,
+//! # #[allow(dead_code)]
+//!     name: String,
+//!     phone: u64,
+//! }
+//!
+//! impl Hash for Person {
+//!     fn hash<H: Hasher>(&self, state: &mut H) {
+//!         self.id.hash(state);
+//!         self.phone.hash(state);
+//!     }
+//! }
+//!
+//! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 };
+//! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 };
+//!
+//! assert_eq!(hash(&person1), hash(&person2));
+//!
+//! fn hash<T: Hash>(t: &T) -> u64 {
+//!     let mut s = SipHasher::new();
+//!     t.hash(&mut s);
+//!     s.finish()
+//! }
+//! ```
+
+#![stable(feature = "rust1", since = "1.0.0")]
+
+use prelude::v1::*;
+
+use fmt;
+use marker;
+use mem;
+
+#[stable(feature = "rust1", since = "1.0.0")]
+pub use self::sip::SipHasher;
+
+mod sip;
+
+/// A hashable type.
+///
+/// The `H` type parameter is an abstract hash state that is used by the `Hash`
+/// to compute the hash.
+///
+/// If you are also implementing `Eq`, there is an additional property that
+/// is important:
+///
+/// ```text
+/// k1 == k2 -> hash(k1) == hash(k2)
+/// ```
+///
+/// In other words, if two keys are equal, their hashes should also be equal.
+/// `HashMap` and `HashSet` both rely on this behavior.
+///
+/// This trait can be used with `#[derive]`.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub trait Hash {
+    /// Feeds this value into the state given, updating the hasher as necessary.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    fn hash<H: Hasher>(&self, state: &mut H);
+
+    /// Feeds a slice of this type into the state provided.
+    #[stable(feature = "hash_slice", since = "1.3.0")]
+    fn hash_slice<H: Hasher>(data: &[Self], state: &mut H)
+        where Self: Sized
+    {
+        for piece in data {
+            piece.hash(state);
+        }
+    }
+}
+
+/// A trait which represents the ability to hash an arbitrary stream of bytes.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub trait Hasher {
+    /// Completes a round of hashing, producing the output hash generated.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    fn finish(&self) -> u64;
+
+    /// Writes some data into this `Hasher`
+    #[stable(feature = "rust1", since = "1.0.0")]
+    fn write(&mut self, bytes: &[u8]);
+
+    /// Write a single `u8` into this hasher
+    #[inline]
+    #[stable(feature = "hasher_write", since = "1.3.0")]
+    fn write_u8(&mut self, i: u8) {
+        self.write(&[i])
+    }
+    /// Write a single `u16` into this hasher.
+    #[inline]
+    #[stable(feature = "hasher_write", since = "1.3.0")]
+    fn write_u16(&mut self, i: u16) {
+        self.write(&unsafe { mem::transmute::<_, [u8; 2]>(i) })
+    }
+    /// Write a single `u32` into this hasher.
+    #[inline]
+    #[stable(feature = "hasher_write", since = "1.3.0")]
+    fn write_u32(&mut self, i: u32) {
+        self.write(&unsafe { mem::transmute::<_, [u8; 4]>(i) })
+    }
+    /// Write a single `u64` into this hasher.
+    #[inline]
+    #[stable(feature = "hasher_write", since = "1.3.0")]
+    fn write_u64(&mut self, i: u64) {
+        self.write(&unsafe { mem::transmute::<_, [u8; 8]>(i) })
+    }
+    /// Write a single `usize` into this hasher.
+    #[inline]
+    #[stable(feature = "hasher_write", since = "1.3.0")]
+    fn write_usize(&mut self, i: usize) {
+        let bytes = unsafe {
+            ::slice::from_raw_parts(&i as *const usize as *const u8, mem::size_of::<usize>())
+        };
+        self.write(bytes);
+    }
+
+    /// Write a single `i8` into this hasher.
+    #[inline]
+    #[stable(feature = "hasher_write", since = "1.3.0")]
+    fn write_i8(&mut self, i: i8) {
+        self.write_u8(i as u8)
+    }
+    /// Write a single `i16` into this hasher.
+    #[inline]
+    #[stable(feature = "hasher_write", since = "1.3.0")]
+    fn write_i16(&mut self, i: i16) {
+        self.write_u16(i as u16)
+    }
+    /// Write a single `i32` into this hasher.
+    #[inline]
+    #[stable(feature = "hasher_write", since = "1.3.0")]
+    fn write_i32(&mut self, i: i32) {
+        self.write_u32(i as u32)
+    }
+    /// Write a single `i64` into this hasher.
+    #[inline]
+    #[stable(feature = "hasher_write", since = "1.3.0")]
+    fn write_i64(&mut self, i: i64) {
+        self.write_u64(i as u64)
+    }
+    /// Write a single `isize` into this hasher.
+    #[inline]
+    #[stable(feature = "hasher_write", since = "1.3.0")]
+    fn write_isize(&mut self, i: isize) {
+        self.write_usize(i as usize)
+    }
+}
+
+/// A `BuildHasher` is typically used as a factory for instances of `Hasher`
+/// which a `HashMap` can then use to hash keys independently.
+///
+/// Note that for each instance of `BuildHasher`, the created hashers should be
+/// identical. That is, if the same stream of bytes is fed into each hasher, the
+/// same output will also be generated.
+#[stable(since = "1.7.0", feature = "build_hasher")]
+pub trait BuildHasher {
+    /// Type of the hasher that will be created.
+    #[stable(since = "1.7.0", feature = "build_hasher")]
+    type Hasher: Hasher;
+
+    /// Creates a new hasher.
+    #[stable(since = "1.7.0", feature = "build_hasher")]
+    fn build_hasher(&self) -> Self::Hasher;
+}
+
+/// A structure which implements `BuildHasher` for all `Hasher` types which also
+/// implement `Default`.
+///
+/// This struct is 0-sized and does not need construction.
+#[stable(since = "1.7.0", feature = "build_hasher")]
+pub struct BuildHasherDefault<H>(marker::PhantomData<H>);
+
+#[stable(since = "1.9.0", feature = "core_impl_debug")]
+impl<H> fmt::Debug for BuildHasherDefault<H> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.pad("BuildHasherDefault")
+    }
+}
+
+#[stable(since = "1.7.0", feature = "build_hasher")]
+impl<H: Default + Hasher> BuildHasher for BuildHasherDefault<H> {
+    type Hasher = H;
+
+    fn build_hasher(&self) -> H {
+        H::default()
+    }
+}
+
+#[stable(since = "1.7.0", feature = "build_hasher")]
+impl<H> Clone for BuildHasherDefault<H> {
+    fn clone(&self) -> BuildHasherDefault<H> {
+        BuildHasherDefault(marker::PhantomData)
+    }
+}
+
+#[stable(since = "1.7.0", feature = "build_hasher")]
+impl<H> Default for BuildHasherDefault<H> {
+    fn default() -> BuildHasherDefault<H> {
+        BuildHasherDefault(marker::PhantomData)
+    }
+}
+
+//////////////////////////////////////////////////////////////////////////////
+
+mod impls {
+    use prelude::v1::*;
+
+    use mem;
+    use slice;
+    use super::*;
+
+    macro_rules! impl_write {
+        ($(($ty:ident, $meth:ident),)*) => {$(
+            #[stable(feature = "rust1", since = "1.0.0")]
+            impl Hash for $ty {
+                fn hash<H: Hasher>(&self, state: &mut H) {
+                    state.$meth(*self)
+                }
+
+                fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
+                    let newlen = data.len() * mem::size_of::<$ty>();
+                    let ptr = data.as_ptr() as *const u8;
+                    state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
+                }
+            }
+        )*}
+    }
+
+    impl_write! {
+        (u8, write_u8),
+        (u16, write_u16),
+        (u32, write_u32),
+        (u64, write_u64),
+        (usize, write_usize),
+        (i8, write_i8),
+        (i16, write_i16),
+        (i32, write_i32),
+        (i64, write_i64),
+        (isize, write_isize),
+    }
+
+    #[stable(feature = "rust1", since = "1.0.0")]
+    impl Hash for bool {
+        fn hash<H: Hasher>(&self, state: &mut H) {
+            state.write_u8(*self as u8)
+        }
+    }
+
+    #[stable(feature = "rust1", since = "1.0.0")]
+    impl Hash for char {
+        fn hash<H: Hasher>(&self, state: &mut H) {
+            state.write_u32(*self as u32)
+        }
+    }
+
+    #[stable(feature = "rust1", since = "1.0.0")]
+    impl Hash for str {
+        fn hash<H: Hasher>(&self, state: &mut H) {
+            state.write(self.as_bytes());
+            state.write_u8(0xff)
+        }
+    }
+
+    macro_rules! impl_hash_tuple {
+        () => (
+            #[stable(feature = "rust1", since = "1.0.0")]
+            impl Hash for () {
+                fn hash<H: Hasher>(&self, _state: &mut H) {}
+            }
+        );
+
+        ( $($name:ident)+) => (
+            #[stable(feature = "rust1", since = "1.0.0")]
+            impl<$($name: Hash),*> Hash for ($($name,)*) {
+                #[allow(non_snake_case)]
+                fn hash<S: Hasher>(&self, state: &mut S) {
+                    let ($(ref $name,)*) = *self;
+                    $($name.hash(state);)*
+                }
+            }
+        );
+    }
+
+    impl_hash_tuple! {}
+    impl_hash_tuple! { A }
+    impl_hash_tuple! { A B }
+    impl_hash_tuple! { A B C }
+    impl_hash_tuple! { A B C D }
+    impl_hash_tuple! { A B C D E }
+    impl_hash_tuple! { A B C D E F }
+    impl_hash_tuple! { A B C D E F G }
+    impl_hash_tuple! { A B C D E F G H }
+    impl_hash_tuple! { A B C D E F G H I }
+    impl_hash_tuple! { A B C D E F G H I J }
+    impl_hash_tuple! { A B C D E F G H I J K }
+    impl_hash_tuple! { A B C D E F G H I J K L }
+
+    #[stable(feature = "rust1", since = "1.0.0")]
+    impl<T: Hash> Hash for [T] {
+        fn hash<H: Hasher>(&self, state: &mut H) {
+            self.len().hash(state);
+            Hash::hash_slice(self, state)
+        }
+    }
+
+
+    #[stable(feature = "rust1", since = "1.0.0")]
+    impl<'a, T: ?Sized + Hash> Hash for &'a T {
+        fn hash<H: Hasher>(&self, state: &mut H) {
+            (**self).hash(state);
+        }
+    }
+
+    #[stable(feature = "rust1", since = "1.0.0")]
+    impl<'a, T: ?Sized + Hash> Hash for &'a mut T {
+        fn hash<H: Hasher>(&self, state: &mut H) {
+            (**self).hash(state);
+        }
+    }
+
+    #[stable(feature = "rust1", since = "1.0.0")]
+    impl<T> Hash for *const T {
+        fn hash<H: Hasher>(&self, state: &mut H) {
+            state.write_usize(*self as usize)
+        }
+    }
+
+    #[stable(feature = "rust1", since = "1.0.0")]
+    impl<T> Hash for *mut T {
+        fn hash<H: Hasher>(&self, state: &mut H) {
+            state.write_usize(*self as usize)
+        }
+    }
+}
diff --git a/libcore/hash/sip.rs b/libcore/hash/sip.rs
new file mode 100644
index 0000000..fd1dab7
--- /dev/null
+++ b/libcore/hash/sip.rs
@@ -0,0 +1,239 @@
+// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! An implementation of SipHash 2-4.
+
+use prelude::v1::*;
+
+use ptr;
+use super::Hasher;
+
+/// An implementation of SipHash 2-4.
+///
+/// See: https://131002.net/siphash/
+///
+/// This is currently the default hashing function used by standard library
+/// (eg. `collections::HashMap` uses it by default).
+///
+/// SipHash is a general-purpose hashing function: it runs at a good
+/// speed (competitive with Spooky and City) and permits strong _keyed_
+/// hashing. This lets you key your hashtables from a strong RNG, such as
+/// [`rand::os::OsRng`](https://doc.rust-lang.org/rand/rand/os/struct.OsRng.html).
+///
+/// Although the SipHash algorithm is considered to be generally strong,
+/// it is not intended for cryptographic purposes. As such, all
+/// cryptographic uses of this implementation are _strongly discouraged_.
+#[derive(Debug)]
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct SipHasher {
+    k0: u64,
+    k1: u64,
+    length: usize, // how many bytes we've processed
+    // v0, v2 and v1, v3 show up in pairs in the algorithm,
+    // and simd implementations of SipHash will use vectors
+    // of v02 and v13. By placing them in this order in the struct,
+    // the compiler can pick up on just a few simd optimizations by itself.
+    v0: u64, // hash state
+    v2: u64,
+    v1: u64,
+    v3: u64,
+    tail: u64, // unprocessed bytes le
+    ntail: usize, // how many bytes in tail are valid
+}
+
+// sadly, these macro definitions can't appear later,
+// because they're needed in the following defs;
+// this design could be improved.
+
+macro_rules! u8to64_le {
+    ($buf:expr, $i:expr) =>
+    ($buf[0+$i] as u64 |
+     ($buf[1+$i] as u64) << 8 |
+     ($buf[2+$i] as u64) << 16 |
+     ($buf[3+$i] as u64) << 24 |
+     ($buf[4+$i] as u64) << 32 |
+     ($buf[5+$i] as u64) << 40 |
+     ($buf[6+$i] as u64) << 48 |
+     ($buf[7+$i] as u64) << 56);
+    ($buf:expr, $i:expr, $len:expr) =>
+    ({
+        let mut t = 0;
+        let mut out = 0;
+        while t < $len {
+            out |= ($buf[t+$i] as u64) << t*8;
+            t += 1;
+        }
+        out
+    });
+}
+
+/// Load a full u64 word from a byte stream, in LE order. Use
+/// `copy_nonoverlapping` to let the compiler generate the most efficient way
+/// to load u64 from a possibly unaligned address.
+///
+/// Unsafe because: unchecked indexing at i..i+8
+#[inline]
+unsafe fn load_u64_le(buf: &[u8], i: usize) -> u64 {
+    debug_assert!(i + 8 <= buf.len());
+    let mut data = 0u64;
+    ptr::copy_nonoverlapping(buf.get_unchecked(i), &mut data as *mut _ as *mut u8, 8);
+    data.to_le()
+}
+
+macro_rules! rotl {
+    ($x:expr, $b:expr) =>
+    (($x << $b) | ($x >> (64_i32.wrapping_sub($b))))
+}
+
+macro_rules! compress {
+    ($v0:expr, $v1:expr, $v2:expr, $v3:expr) =>
+    ({
+        $v0 = $v0.wrapping_add($v1); $v1 = rotl!($v1, 13); $v1 ^= $v0;
+        $v0 = rotl!($v0, 32);
+        $v2 = $v2.wrapping_add($v3); $v3 = rotl!($v3, 16); $v3 ^= $v2;
+        $v0 = $v0.wrapping_add($v3); $v3 = rotl!($v3, 21); $v3 ^= $v0;
+        $v2 = $v2.wrapping_add($v1); $v1 = rotl!($v1, 17); $v1 ^= $v2;
+        $v2 = rotl!($v2, 32);
+    })
+}
+
+impl SipHasher {
+    /// Creates a new `SipHasher` with the two initial keys set to 0.
+    #[inline]
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn new() -> SipHasher {
+        SipHasher::new_with_keys(0, 0)
+    }
+
+    /// Creates a `SipHasher` that is keyed off the provided keys.
+    #[inline]
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher {
+        let mut state = SipHasher {
+            k0: key0,
+            k1: key1,
+            length: 0,
+            v0: 0,
+            v1: 0,
+            v2: 0,
+            v3: 0,
+            tail: 0,
+            ntail: 0,
+        };
+        state.reset();
+        state
+    }
+
+    #[inline]
+    fn reset(&mut self) {
+        self.length = 0;
+        self.v0 = self.k0 ^ 0x736f6d6570736575;
+        self.v1 = self.k1 ^ 0x646f72616e646f6d;
+        self.v2 = self.k0 ^ 0x6c7967656e657261;
+        self.v3 = self.k1 ^ 0x7465646279746573;
+        self.ntail = 0;
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl Hasher for SipHasher {
+    #[inline]
+    fn write(&mut self, msg: &[u8]) {
+        let length = msg.len();
+        self.length += length;
+
+        let mut needed = 0;
+
+        if self.ntail != 0 {
+            needed = 8 - self.ntail;
+            if length < needed {
+                self.tail |= u8to64_le!(msg, 0, length) << 8 * self.ntail;
+                self.ntail += length;
+                return
+            }
+
+            let m = self.tail | u8to64_le!(msg, 0, needed) << 8 * self.ntail;
+
+            self.v3 ^= m;
+            compress!(self.v0, self.v1, self.v2, self.v3);
+            compress!(self.v0, self.v1, self.v2, self.v3);
+            self.v0 ^= m;
+
+            self.ntail = 0;
+        }
+
+        // Buffered tail is now flushed, process new input.
+        let len = length - needed;
+        let left = len & 0x7;
+
+        let mut i = needed;
+        while i < len - left {
+            let mi = unsafe { load_u64_le(msg, i) };
+
+            self.v3 ^= mi;
+            compress!(self.v0, self.v1, self.v2, self.v3);
+            compress!(self.v0, self.v1, self.v2, self.v3);
+            self.v0 ^= mi;
+
+            i += 8;
+        }
+
+        self.tail = u8to64_le!(msg, i, left);
+        self.ntail = left;
+    }
+
+    #[inline]
+    fn finish(&self) -> u64 {
+        let mut v0 = self.v0;
+        let mut v1 = self.v1;
+        let mut v2 = self.v2;
+        let mut v3 = self.v3;
+
+        let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail;
+
+        v3 ^= b;
+        compress!(v0, v1, v2, v3);
+        compress!(v0, v1, v2, v3);
+        v0 ^= b;
+
+        v2 ^= 0xff;
+        compress!(v0, v1, v2, v3);
+        compress!(v0, v1, v2, v3);
+        compress!(v0, v1, v2, v3);
+        compress!(v0, v1, v2, v3);
+
+        v0 ^ v1 ^ v2 ^ v3
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl Clone for SipHasher {
+    #[inline]
+    fn clone(&self) -> SipHasher {
+        SipHasher {
+            k0: self.k0,
+            k1: self.k1,
+            length: self.length,
+            v0: self.v0,
+            v1: self.v1,
+            v2: self.v2,
+            v3: self.v3,
+            tail: self.tail,
+            ntail: self.ntail,
+        }
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl Default for SipHasher {
+    fn default() -> SipHasher {
+        SipHasher::new()
+    }
+}