blueprint_strong_hash/
lib.rs

1/*
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
3 *
4 * This source code is dual-licensed under either the MIT license found in the
5 * LICENSE-MIT file in the root directory of this source tree or the Apache
6 * License, Version 2.0 found in the LICENSE-APACHE file in the root directory
7 * of this source tree. You may select, at your option, one of the
8 * above-listed licenses.
9 */
10
11use std::collections::BTreeMap;
12use std::collections::HashMap;
13use std::hash::Hash;
14use std::hash::Hasher;
15use std::marker::PhantomData;
16use std::sync::Arc;
17
18use ref_cast::RefCast;
19pub use blueprint_strong_hash_derive::StrongHash;
20
21use crate as strong_hash;
22
23mod impls;
24
25/// `StrongHash`` is a trait that is notionally similar to `std::hash::Hash`, but carries the
26/// implicit expectation that the hash that will be produced should be as perturbed as possible.
27///
28/// `StrongHash` must be implemented such that - when combined with a crypto hasher - the hash value
29/// is suitable to use for equality checks. That means fields must not be omitted and pre-computed
30/// hash values cannot be used if the hasher used for them is weak.
31///
32/// `StrongHash` can be derived on enums and structs if all of their members implement `StrongHash`.
33/// For example:
34///
35/// ```ignore
36/// #[derive(StrongHash)]
37/// struct MyStruct {
38///     a: u32,
39///     b: String,
40///     c: Vec<u8>,
41/// }
42/// ```
43///
44/// `StrongHash` can also be implemented manually similar to std::hash::Hash. For example:
45///
46/// ```ignore
47/// struct MyStruct {
48///     a: u32,
49///     b: String,
50///     c: Vec<u8>,
51/// }
52///
53/// impl StrongHash for MyStruct {
54///     fn strong_hash<H: StrongHasher>(&self, state: &mut H) {
55///         self.a.strong_hash(state);
56///         self.b.strong_hash(state);
57///         self.c.strong_hash(state);
58///     }
59/// }
60/// ```
61pub trait StrongHash {
62    fn strong_hash<H: Hasher>(&self, state: &mut H);
63}
64
65#[macro_export]
66macro_rules! impl_strong_hash_for_impl_hash {
67    ($($t:ty)*) => {
68        $(
69            impl strong_hash::StrongHash for $t {
70                fn strong_hash<H: std::hash::Hasher>(&self, state: &mut H) {
71                    std::hash::Hash::hash(self, state);
72                }
73            }
74        )*
75    };
76}
77
78impl_strong_hash_for_impl_hash!(bool u8 i8 u16 i16 u32 i32 u64 i64 usize str &str String);
79
80impl<T: StrongHash> StrongHash for [T] {
81    fn strong_hash<H: Hasher>(&self, state: &mut H) {
82        self.len().strong_hash(state);
83        for item in self.iter() {
84            item.strong_hash(state);
85        }
86    }
87}
88
89impl<T: StrongHash> StrongHash for &[T] {
90    fn strong_hash<H: Hasher>(&self, state: &mut H) {
91        <[T] as StrongHash>::strong_hash(*self, state);
92    }
93}
94
95impl<T: StrongHash> StrongHash for Vec<T> {
96    fn strong_hash<H: Hasher>(&self, state: &mut H) {
97        self.len().strong_hash(state);
98        (&self[..]).strong_hash(state);
99    }
100}
101
102impl<T: StrongHash> StrongHash for Option<T> {
103    fn strong_hash<H: Hasher>(&self, state: &mut H) {
104        self.is_some().strong_hash(state);
105        if let Some(t) = self.as_ref() {
106            t.strong_hash(state);
107        }
108    }
109}
110
111impl StrongHash for () {
112    fn strong_hash<H: Hasher>(&self, _state: &mut H) {}
113}
114
115impl<A: StrongHash> StrongHash for (A,) {
116    fn strong_hash<H: Hasher>(&self, state: &mut H) {
117        1.strong_hash(state);
118        self.0.strong_hash(state);
119    }
120}
121
122impl<A: StrongHash, B: StrongHash> StrongHash for (A, B) {
123    fn strong_hash<H: Hasher>(&self, state: &mut H) {
124        2.strong_hash(state);
125        self.0.strong_hash(state);
126        self.1.strong_hash(state);
127    }
128}
129
130impl<A: StrongHash, B: StrongHash, C: StrongHash> StrongHash for (A, B, C) {
131    fn strong_hash<H: Hasher>(&self, state: &mut H) {
132        3.strong_hash(state);
133        self.0.strong_hash(state);
134        self.1.strong_hash(state);
135        self.2.strong_hash(state);
136    }
137}
138
139impl<T: StrongHash + ?Sized> StrongHash for Box<T> {
140    fn strong_hash<H: Hasher>(&self, state: &mut H) {
141        self.as_ref().strong_hash(state);
142    }
143}
144
145impl<T: StrongHash + ?Sized> StrongHash for Arc<T> {
146    fn strong_hash<H: Hasher>(&self, state: &mut H) {
147        self.as_ref().strong_hash(state);
148    }
149}
150
151impl<K: StrongHash, V: StrongHash> StrongHash for BTreeMap<K, V> {
152    fn strong_hash<H: Hasher>(&self, state: &mut H) {
153        self.len().strong_hash(state);
154        for (k, v) in self.iter() {
155            k.strong_hash(state);
156            v.strong_hash(state);
157        }
158    }
159}
160
161impl<K: StrongHash, V: StrongHash> StrongHash for HashMap<K, V> {
162    fn strong_hash<H: Hasher>(&self, state: &mut H) {
163        self.len().strong_hash(state);
164        for (k, v) in self.iter() {
165            k.strong_hash(state);
166            v.strong_hash(state);
167        }
168    }
169}
170
171impl StrongHash for *const () {
172    fn strong_hash<H: Hasher>(&self, state: &mut H) {
173        (*self as usize).strong_hash(state);
174    }
175}
176
177impl<T: ?Sized> StrongHash for PhantomData<T> {
178    fn strong_hash<H: Hasher>(&self, state: &mut H) {
179        self.hash(state);
180    }
181}
182
183/// A wrapper can be used to implement `Hash` using the inner type's `StrongHash`.
184#[derive(RefCast)]
185#[repr(transparent)]
186pub struct UseStrongHashing<T: ?Sized>(pub T);
187
188impl<T> Hash for UseStrongHashing<T>
189where
190    T: ?Sized + StrongHash,
191{
192    fn hash<H: Hasher>(&self, state: &mut H) {
193        self.0.strong_hash(state);
194    }
195}
196
197#[cfg(test)]
198mod test {
199    use super::*;
200
201    struct TestHashable {
202        hash: u64,
203        strong_hash: u64,
204    }
205
206    impl Hash for TestHashable {
207        fn hash<H: Hasher>(&self, state: &mut H) {
208            self.hash.hash(state);
209        }
210    }
211
212    impl StrongHash for TestHashable {
213        fn strong_hash<H: Hasher>(&self, state: &mut H) {
214            self.strong_hash.strong_hash(state);
215        }
216    }
217
218    fn hash<T: Hash>(t: &T) -> u64 {
219        let mut hasher = std::collections::hash_map::DefaultHasher::new();
220        t.hash(&mut hasher);
221        hasher.finish()
222    }
223
224    fn strong_hash<T: StrongHash>(t: &T) -> u64 {
225        let mut hasher = std::collections::hash_map::DefaultHasher::new();
226        t.strong_hash(&mut hasher);
227        hasher.finish()
228    }
229
230    #[test]
231    fn test_use_strong_hashing() {
232        let x = TestHashable {
233            hash: 1,
234            strong_hash: 2,
235        };
236
237        let y = TestHashable {
238            hash: 1,
239            strong_hash: 3,
240        };
241
242        assert_eq!(hash(&x), hash(&y));
243
244        assert_eq!(strong_hash(&x), hash(UseStrongHashing::ref_cast(&x)));
245
246        assert_ne!(
247            hash(UseStrongHashing::ref_cast(&x)),
248            hash(UseStrongHashing::ref_cast(&y))
249        );
250    }
251}
blueprint_strong_hash/lib.rs

blueprint_strong_hash/
lib.rs
