std: Stabilize the std::hash module

This commit aims to prepare the `std::hash` module for alpha by formalizing its
current interface whileholding off on adding `#[stable]` to the new APIs.  The
current usage with the `HashMap` and `HashSet` types is also reconciled by
separating out composable parts of the design. The primary goal of this slight
redesign is to separate the concepts of a hasher's state from a hashing
algorithm itself.

The primary change of this commit is to separate the `Hasher` trait into a
`Hasher` and a `HashState` trait. Conceptually the old `Hasher` trait was
actually just a factory for various states, but hashing had very little control
over how these states were used. Additionally the old `Hasher` trait was
actually fairly unrelated to hashing.

This commit redesigns the existing `Hasher` trait to match what the notion of a
`Hasher` normally implies with the following definition:

    trait Hasher {
        type Output;
        fn reset(&mut self);
        fn finish(&self) -> Output;
    }

This `Hasher` trait emphasizes that hashing algorithms may produce outputs other
than a `u64`, so the output type is made generic. Other than that, however, very
little is assumed about a particular hasher. It is left up to implementors to
provide specific methods or trait implementations to feed data into a hasher.

The corresponding `Hash` trait becomes:

    trait Hash<H: Hasher> {
        fn hash(&self, &mut H);
    }

The old default of `SipState` was removed from this trait as it's not something
that we're willing to stabilize until the end of time, but the type parameter is
always required to implement `Hasher`. Note that the type parameter `H` remains
on the trait to enable multidispatch for specialization of hashing for
particular hashers.

Note that `Writer` is not mentioned in either of `Hash` or `Hasher`, it is
simply used as part `derive` and the implementations for all primitive types.

With these definitions, the old `Hasher` trait is realized as a new `HashState`
trait in the `collections::hash_state` module as an unstable addition for
now. The current definition looks like:

    trait HashState {
        type Hasher: Hasher;
        fn hasher(&self) -> Hasher;
    }

The purpose of this trait is to emphasize that the one piece of functionality
for implementors is that new instances of `Hasher` can be created.  This
conceptually represents the two keys from which more instances of a
`SipHasher` can be created, and a `HashState` is what's stored in a
`HashMap`, not a `Hasher`.

Implementors of custom hash algorithms should implement the `Hasher` trait, and
only hash algorithms intended for use in hash maps need to implement or worry
about the `HashState` trait.

The entire module and `HashState` infrastructure remains `#[unstable]` due to it
being recently redesigned, but some other stability decision made for the
`std::hash` module are:

* The `Writer` trait remains `#[experimental]` as it's intended to be replaced
  with an `io::Writer` (more details soon).
* The top-level `hash` function is `#[unstable]` as it is intended to be generic
  over the hashing algorithm instead of hardwired to `SipHasher`
* The inner `sip` module is now private as its one export, `SipHasher` is
  reexported in the `hash` module.

And finally, a few changes were made to the default parameters on `HashMap`.

* The `RandomSipHasher` default type parameter was renamed to `RandomState`.
  This renaming emphasizes that it is not a hasher, but rather just state to
  generate hashers. It also moves away from the name "sip" as it may not always
  be implemented as `SipHasher`. This type lives in the
  `std::collections::hash_map` module as `#[unstable]`

* The associated `Hasher` type of `RandomState` is creatively called...
  `Hasher`! This concrete structure lives next to `RandomState` as an
  implemenation of the "default hashing algorithm" used for a `HashMap`. Under
  the hood this is currently implemented as `SipHasher`, but it draws an
  explicit interface for now and allows us to modify the implementation over
  time if necessary.

There are many breaking changes outlined above, and as a result this commit is
a:

[breaking-change]

1 files changed, 60 insertions, 43 deletions

diff --git a/src/libcoretest/hash/mod.rs b/src/libcoretest/hash/mod.rs
index 63bf9ec3314..63935894bf5 100644
--- a/src/libcoretest/hash/mod.rs
+++ b/src/libcoretest/hash/mod.rs
@@ -7,27 +7,22 @@
 // <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.
-use core::marker::Sized;
-use std::mem;
-
-use core::slice::SliceExt;
-use core::hash::{Hash, Hasher, Writer};
 
-struct MyWriterHasher;
+use std::mem;
+use std::hash::{Hash, Hasher, Writer};
+use std::default::Default;
 
-impl Hasher<MyWriter> for MyWriterHasher {
-    fn hash<T: ?Sized + Hash<MyWriter>>(&self, value: &T) -> u64 {
-        let mut state = MyWriter { hash: 0 };
-        value.hash(&mut state);
-        state.hash
-    }
+struct MyHasher {
+    hash: u64,
 }
 
-struct MyWriter {
-    hash: u64,
+impl Default for MyHasher {
+    fn default() -> MyHasher {
+        MyHasher { hash: 0 }
+    }
 }
 
-impl Writer for MyWriter {
+impl Writer for MyHasher {
     // Most things we'll just add up the bytes.
     fn write(&mut self, buf: &[u8]) {
         for byte in buf.iter() {
@@ -36,66 +31,88 @@ impl Writer for MyWriter {
     }
 }
 
+impl Hasher for MyHasher {
+    type Output = u64;
+    fn reset(&mut self) { self.hash = 0; }
+    fn finish(&self) -> u64 { self.hash }
+}
+
+
 #[test]
 fn test_writer_hasher() {
-    let hasher = MyWriterHasher;
+    fn hash<T: Hash<MyHasher>>(t: &T) -> u64 {
+        ::std::hash::hash::<_, MyHasher>(t)
+    }
 
-    assert_eq!(hasher.hash(&()), 0);
+    assert_eq!(hash(&()), 0);
 
-    assert_eq!(hasher.hash(&5u8), 5);
-    assert_eq!(hasher.hash(&5u16), 5);
-    assert_eq!(hasher.hash(&5u32), 5);
-    assert_eq!(hasher.hash(&5u64), 5);
-    assert_eq!(hasher.hash(&5u), 5);
+    assert_eq!(hash(&5u8), 5);
+    assert_eq!(hash(&5u16), 5);
+    assert_eq!(hash(&5u32), 5);
+    assert_eq!(hash(&5u64), 5);
+    assert_eq!(hash(&5u), 5);
 
-    assert_eq!(hasher.hash(&5i8), 5);
-    assert_eq!(hasher.hash(&5i16), 5);
-    assert_eq!(hasher.hash(&5i32), 5);
-    assert_eq!(hasher.hash(&5i64), 5);
-    assert_eq!(hasher.hash(&5i), 5);
+    assert_eq!(hash(&5i8), 5);
+    assert_eq!(hash(&5i16), 5);
+    assert_eq!(hash(&5i32), 5);
+    assert_eq!(hash(&5i64), 5);
+    assert_eq!(hash(&5i), 5);
 
-    assert_eq!(hasher.hash(&false), 0);
-    assert_eq!(hasher.hash(&true), 1);
+    assert_eq!(hash(&false), 0);
+    assert_eq!(hash(&true), 1);
 
-    assert_eq!(hasher.hash(&'a'), 97);
+    assert_eq!(hash(&'a'), 97);
 
     let s: &str = "a";
-    assert_eq!(hasher.hash(& s), 97 + 0xFF);
+    assert_eq!(hash(& s), 97 + 0xFF);
     // FIXME (#18283) Enable test
     //let s: Box<str> = box "a";
     //assert_eq!(hasher.hash(& s), 97 + 0xFF);
     let cs: &[u8] = &[1u8, 2u8, 3u8];
-    assert_eq!(hasher.hash(& cs), 9);
+    assert_eq!(hash(& cs), 9);
     let cs: Box<[u8]> = box [1u8, 2u8, 3u8];
-    assert_eq!(hasher.hash(& cs), 9);
+    assert_eq!(hash(& cs), 9);
 
     // FIXME (#18248) Add tests for hashing Rc<str> and Rc<[T]>
 
     unsafe {
         let ptr: *const int = mem::transmute(5i);
-        assert_eq!(hasher.hash(&ptr), 5);
+        assert_eq!(hash(&ptr), 5);
     }
 
     unsafe {
         let ptr: *mut int = mem::transmute(5i);
-        assert_eq!(hasher.hash(&ptr), 5);
+        assert_eq!(hash(&ptr), 5);
     }
 }
 
-struct Custom {
-    hash: u64
+struct Custom { hash: u64 }
+struct CustomHasher { output: u64 }
+
+impl Hasher for CustomHasher {
+    type Output = u64;
+    fn reset(&mut self) { self.output = 0; }
+    fn finish(&self) -> u64 { self.output }
+}
+
+impl Default for CustomHasher {
+    fn default() -> CustomHasher {
+        CustomHasher { output: 0 }
+    }
 }
 
-impl Hash<u64> for Custom {
-    fn hash(&self, state: &mut u64) {
-        *state = self.hash;
+impl Hash<CustomHasher> for Custom {
+    fn hash(&self, state: &mut CustomHasher) {
+        state.output = self.hash;
     }
 }
 
 #[test]
 fn test_custom_state() {
+    fn hash<T: Hash<CustomHasher>>(t: &T) -> u64 {
+        ::std::hash::hash::<_, CustomHasher>(t)
+    }
+
     let custom = Custom { hash: 5 };
-    let mut state = 0;
-    custom.hash(&mut state);
-    assert_eq!(state, 5);
+    assert_eq!(hash(&Custom { hash: 5 }), 5);
 }