From 511f0b8a3de5a166fc96aba5170782c9abf92101 Mon Sep 17 00:00:00 2001 From: Alex Crichton Date: Tue, 9 Dec 2014 12:37:23 -0800 Subject: 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 { 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] --- src/libserialize/collection_impls.rs | 60 +++++++++++++++++------------------- src/libserialize/lib.rs | 1 - 2 files changed, 29 insertions(+), 32 deletions(-) (limited to 'src/libserialize') diff --git a/src/libserialize/collection_impls.rs b/src/libserialize/collection_impls.rs index d89a4754d2e..42498328ff6 100644 --- a/src/libserialize/collection_impls.rs +++ b/src/libserialize/collection_impls.rs @@ -13,6 +13,7 @@ use std::uint; use std::default::Default; use std::hash::{Hash, Hasher}; +use std::collections::hash_state::HashState; use {Decodable, Encodable, Decoder, Encoder}; use std::collections::{DList, RingBuf, BTreeMap, BTreeSet, HashMap, HashSet, VecMap}; @@ -156,13 +157,12 @@ impl< } } -#[old_impl_check] -impl< - K: Encodable + Hash + Eq, - V: Encodable, - X, - H: Hasher -> Encodable for HashMap { +impl Encodable for HashMap + where K: Encodable + Hash< ::Hasher> + Eq, + V: Encodable, + S: HashState, + ::Hasher: Hasher +{ fn encode(&self, e: &mut S) -> Result<(), S::Error> { e.emit_map(self.len(), |e| { let mut i = 0; @@ -176,17 +176,16 @@ impl< } } -#[old_impl_check] -impl< - K: Decodable + Hash + Eq, - V: Decodable, - S, - H: Hasher + Default -> Decodable for HashMap { - fn decode(d: &mut D) -> Result, D::Error> { +impl Decodable for HashMap + where K: Decodable + Hash< ::Hasher> + Eq, + V: Decodable, + S: HashState + Default, + ::Hasher: Hasher +{ + fn decode(d: &mut D) -> Result, D::Error> { d.read_map(|d, len| { - let hasher = Default::default(); - let mut map = HashMap::with_capacity_and_hasher(len, hasher); + let state = Default::default(); + let mut map = HashMap::with_capacity_and_hash_state(len, state); for i in range(0u, len) { let key = try!(d.read_map_elt_key(i, |d| Decodable::decode(d))); let val = try!(d.read_map_elt_val(i, |d| Decodable::decode(d))); @@ -197,12 +196,11 @@ impl< } } -#[old_impl_check] -impl< - T: Encodable + Hash + Eq, - X, - H: Hasher -> Encodable for HashSet { +impl Encodable for HashSet + where T: Encodable + Hash< ::Hasher> + Eq, + S: HashState, + ::Hasher: Hasher +{ fn encode(&self, s: &mut S) -> Result<(), S::Error> { s.emit_seq(self.len(), |s| { let mut i = 0; @@ -215,15 +213,15 @@ impl< } } -#[old_impl_check] -impl< - T: Decodable + Hash + Eq, - S, - H: Hasher + Default -> Decodable for HashSet { - fn decode(d: &mut D) -> Result, D::Error> { +impl Decodable for HashSet + where T: Decodable + Hash< ::Hasher> + Eq, + S: HashState + Default, + ::Hasher: Hasher +{ + fn decode(d: &mut D) -> Result, D::Error> { d.read_seq(|d, len| { - let mut set = HashSet::with_capacity_and_hasher(len, Default::default()); + let state = Default::default(); + let mut set = HashSet::with_capacity_and_hash_state(len, state); for i in range(0u, len) { set.insert(try!(d.read_seq_elt(i, |d| Decodable::decode(d)))); } diff --git a/src/libserialize/lib.rs b/src/libserialize/lib.rs index 139170fc012..fd155261934 100644 --- a/src/libserialize/lib.rs +++ b/src/libserialize/lib.rs @@ -24,7 +24,6 @@ Core encoding and decoding interfaces. html_playground_url = "http://play.rust-lang.org/")] #![allow(unknown_features)] #![feature(slicing_syntax)] -#![feature(old_impl_check)] #![cfg_attr(stage0, allow(unused_attributes))] // test harness access -- cgit 1.4.1-3-g733a5