DSTify Hash

- The signature of the `*_equiv` methods of `HashMap` and similar structures
have changed, and now require one less level of indirection. Change your code
from:

```
hashmap.find_equiv(&"Hello");
hashmap.find_equiv(&&[0u8, 1, 2]);
```

to:

```
hashmap.find_equiv("Hello");
hashmap.find_equiv(&[0u8, 1, 2]);
```

- The generic parameter `T` of the `Hasher::hash<T>` method have become
`Sized?`. Downstream code must add `Sized?` to that method in their
implementations. For example:

```
impl Hasher<FnvState> for FnvHasher {
    fn hash<T: Hash<FnvState>>(&self, t: &T) -> u64 { /* .. */ }
}
```

must be changed to:

```
impl Hasher<FnvState> for FnvHasher {
    fn hash<Sized? T: Hash<FnvState>>(&self, t: &T) -> u64 { /* .. */ }
    //      ^^^^^^
}
```

[breaking-change]

4 files changed, 17 insertions, 14 deletions

diff --git a/src/libstd/collections/hashmap/map.rs b/src/libstd/collections/hashmap/map.rs
index cb47c28f8be..881ffd21d71 100644
--- a/src/libstd/collections/hashmap/map.rs
+++ b/src/libstd/collections/hashmap/map.rs
@@ -17,6 +17,7 @@ use default::Default;
 use fmt::{mod, Show};
 use hash::{Hash, Hasher, RandomSipHasher};
 use iter::{mod, Iterator, FromIterator, Extendable};
+use kinds::Sized;
 use mem::{mod, replace};
 use num;
 use ops::{Deref, Index, IndexMut};
@@ -419,17 +420,17 @@ impl<K, V, M> SearchResult<K, V, M> {
 }
 
 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
-    fn make_hash<X: Hash<S>>(&self, x: &X) -> SafeHash {
+    fn make_hash<Sized? X: Hash<S>>(&self, x: &X) -> SafeHash {
         table::make_hash(&self.hasher, x)
     }
 
-    fn search_equiv<'a, Q: Hash<S> + Equiv<K>>(&'a self, q: &Q)
+    fn search_equiv<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a self, q: &Q)
                     -> Option<FullBucketImm<'a, K, V>> {
         let hash = self.make_hash(q);
         search_hashed_generic(&self.table, &hash, |k| q.equiv(k)).into_option()
     }
 
-    fn search_equiv_mut<'a, Q: Hash<S> + Equiv<K>>(&'a mut self, q: &Q)
+    fn search_equiv_mut<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a mut self, q: &Q)
                     -> Option<FullBucketMut<'a, K, V>> {
         let hash = self.make_hash(q);
         search_hashed_generic(&mut self.table, &hash, |k| q.equiv(k)).into_option()
@@ -857,7 +858,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// using equivalence.
     ///
     /// See [pop_equiv](#method.pop_equiv) for an extended example.
-    pub fn contains_key_equiv<Q: Hash<S> + Equiv<K>>(&self, key: &Q) -> bool {
+    pub fn contains_key_equiv<Sized? Q: Hash<S> + Equiv<K>>(&self, key: &Q) -> bool {
         self.search_equiv(key).is_some()
     }
 
@@ -865,7 +866,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// equivalence.
     ///
     /// See [pop_equiv](#method.pop_equiv) for an extended example.
-    pub fn find_equiv<'a, Q: Hash<S> + Equiv<K>>(&'a self, k: &Q) -> Option<&'a V> {
+    pub fn find_equiv<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a self, k: &Q) -> Option<&'a V> {
         match self.search_equiv(k) {
             None      => None,
             Some(bucket) => {
@@ -921,7 +922,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///
     /// ```
     #[experimental]
-    pub fn pop_equiv<Q:Hash<S> + Equiv<K>>(&mut self, k: &Q) -> Option<V> {
+    pub fn pop_equiv<Sized? Q:Hash<S> + Equiv<K>>(&mut self, k: &Q) -> Option<V> {
         if self.table.size() == 0 {
             return None
         }
@@ -1879,11 +1880,11 @@ mod test_map {
         m.insert("baz".to_string(), baz);
 
 
-        assert_eq!(m.find_equiv(&("foo")), Some(&foo));
-        assert_eq!(m.find_equiv(&("bar")), Some(&bar));
-        assert_eq!(m.find_equiv(&("baz")), Some(&baz));
+        assert_eq!(m.find_equiv("foo"), Some(&foo));
+        assert_eq!(m.find_equiv("bar"), Some(&bar));
+        assert_eq!(m.find_equiv("baz"), Some(&baz));
 
-        assert_eq!(m.find_equiv(&("qux")), None);
+        assert_eq!(m.find_equiv("qux"), None);
     }
 
     #[test]
diff --git a/src/libstd/collections/hashmap/set.rs b/src/libstd/collections/hashmap/set.rs
index ca954679c1c..e4016c70320 100644
--- a/src/libstd/collections/hashmap/set.rs
+++ b/src/libstd/collections/hashmap/set.rs
@@ -13,6 +13,7 @@
 use clone::Clone;
 use cmp::{Eq, Equiv, PartialEq};
 use collections::{Collection, Mutable, Set, MutableSet, Map, MutableMap};
+use core::kinds::Sized;
 use default::Default;
 use fmt::Show;
 use fmt;
@@ -221,7 +222,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert!(!set.contains_equiv(&EvenOrOdd { num: 2u }));
     ///
     /// ```
-    pub fn contains_equiv<Q: Hash<S> + Equiv<T>>(&self, value: &Q) -> bool {
+    pub fn contains_equiv<Sized? Q: Hash<S> + Equiv<T>>(&self, value: &Q) -> bool {
       self.map.contains_key_equiv(value)
     }
 
diff --git a/src/libstd/collections/hashmap/table.rs b/src/libstd/collections/hashmap/table.rs
index ca20c3ddb74..faff68c75ff 100644
--- a/src/libstd/collections/hashmap/table.rs
+++ b/src/libstd/collections/hashmap/table.rs
@@ -14,7 +14,7 @@ use clone::Clone;
 use cmp;
 use hash::{Hash, Hasher};
 use iter::{Iterator, count};
-use kinds::marker;
+use kinds::{Sized, marker};
 use mem::{min_align_of, size_of};
 use mem;
 use num::{CheckedAdd, CheckedMul, is_power_of_two};
@@ -131,7 +131,7 @@ impl SafeHash {
 /// We need to remove hashes of 0. That's reserved for empty buckets.
 /// This function wraps up `hash_keyed` to be the only way outside this
 /// module to generate a SafeHash.
-pub fn make_hash<T: Hash<S>, S, H: Hasher<S>>(hasher: &H, t: &T) -> SafeHash {
+pub fn make_hash<Sized? T: Hash<S>, S, H: Hasher<S>>(hasher: &H, t: &T) -> SafeHash {
     match hasher.hash(t) {
         // This constant is exceedingly likely to hash to the same
         // bucket, but it won't be counted as empty! Just so we can maintain
diff --git a/src/libstd/hash.rs b/src/libstd/hash.rs
index 55d1411d77e..e4017ea5a47 100644
--- a/src/libstd/hash.rs
+++ b/src/libstd/hash.rs
@@ -65,6 +65,7 @@
 
 pub use core_collections::hash::{Hash, Hasher, Writer, hash, sip};
 
+use core::kinds::Sized;
 use default::Default;
 use rand::Rng;
 use rand;
@@ -91,7 +92,7 @@ impl RandomSipHasher {
 
 impl Hasher<sip::SipState> for RandomSipHasher {
     #[inline]
-    fn hash<T: Hash<sip::SipState>>(&self, value: &T) -> u64 {
+    fn hash<Sized? T: Hash<sip::SipState>>(&self, value: &T) -> u64 {
         self.hasher.hash(value)
     }
 }