1 #![doc(html_root_url = "https://docs.rs/phf_shared/0.9")]
2 #![cfg_attr(not(feature = "std"), no_std)]
3
4 #[cfg(feature = "std")]
5 extern crate std as core;
6
7 use core::fmt;
8 use core::hash::{Hash, Hasher};
9 use core::num::Wrapping;
10 use siphasher::sip128::{Hash128, Hasher128, SipHasher13};
11
12 #[non_exhaustive]
13 pub struct Hashes {
14 pub g: u32,
15 pub f1: u32,
16 pub f2: u32,
17 }
18
19 /// A central typedef for hash keys
20 ///
21 /// Makes experimentation easier by only needing to be updated here.
22 pub type HashKey = u64;
23
24 #[inline]
displace(f1: u32, f2: u32, d1: u32, d2: u32) -> u3225 pub fn displace(f1: u32, f2: u32, d1: u32, d2: u32) -> u32 {
26 (Wrapping(d2) + Wrapping(f1) * Wrapping(d1) + Wrapping(f2)).0
27 }
28
29 /// `key` is from `phf_generator::HashState`.
30 #[inline]
hash<T: ?Sized + PhfHash>(x: &T, key: &HashKey) -> Hashes31 pub fn hash<T: ?Sized + PhfHash>(x: &T, key: &HashKey) -> Hashes {
32 let mut hasher = SipHasher13::new_with_keys(0, *key);
33 x.phf_hash(&mut hasher);
34
35 let Hash128 {
36 h1: lower,
37 h2: upper,
38 } = hasher.finish128();
39
40 Hashes {
41 g: (lower >> 32) as u32,
42 f1: lower as u32,
43 f2: upper as u32,
44 }
45 }
46
47 /// Return an index into `phf_generator::HashState::map`.
48 ///
49 /// * `hash` is from `hash()` in this crate.
50 /// * `disps` is from `phf_generator::HashState::disps`.
51 /// * `len` is the length of `phf_generator::HashState::map`.
52 #[inline]
get_index(hashes: &Hashes, disps: &[(u32, u32)], len: usize) -> u3253 pub fn get_index(hashes: &Hashes, disps: &[(u32, u32)], len: usize) -> u32 {
54 let (d1, d2) = disps[(hashes.g % (disps.len() as u32)) as usize];
55 displace(hashes.f1, hashes.f2, d1, d2) % (len as u32)
56 }
57
58 /// A trait implemented by types which can be used in PHF data structures.
59 ///
60 /// This differs from the standard library's `Hash` trait in that `PhfHash`'s
61 /// results must be architecture independent so that hashes will be consistent
62 /// between the host and target when cross compiling.
63 pub trait PhfHash {
64 /// Feeds the value into the state given, updating the hasher as necessary.
phf_hash<H: Hasher>(&self, state: &mut H)65 fn phf_hash<H: Hasher>(&self, state: &mut H);
66
67 /// Feeds a slice of this type into the state provided.
phf_hash_slice<H: Hasher>(data: &[Self], state: &mut H) where Self: Sized,68 fn phf_hash_slice<H: Hasher>(data: &[Self], state: &mut H)
69 where
70 Self: Sized,
71 {
72 for piece in data {
73 piece.phf_hash(state);
74 }
75 }
76 }
77
78 /// Trait for printing types with `const` constructors, used by `phf_codegen` and `phf_macros`.
79 pub trait FmtConst {
80 /// Print a `const` expression representing this value.
fmt_const(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result81 fn fmt_const(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result;
82 }
83
84 /// Identical to `std::borrow::Borrow` except omitting blanket impls to facilitate other
85 /// borrowing patterns.
86 ///
87 /// The same semantic requirements apply:
88 ///
89 /// > In particular `Eq`, `Ord` and `Hash` must be equivalent for borrowed and owned values:
90 /// `x.borrow() == y.borrow()` should give the same result as `x == y`.
91 ///
92 /// (This crate's API only requires `Eq` and `PhfHash`, however.)
93 ///
94 /// ### Motivation
95 /// The conventional signature for lookup methods on collections looks something like this:
96 ///
97 /// ```rust,ignore
98 /// impl<K, V> Map<K, V> where K: PhfHash + Eq {
99 /// fn get<T: ?Sized>(&self, key: &T) -> Option<&V> where T: PhfHash + Eq, K: Borrow<T> {
100 /// ...
101 /// }
102 /// }
103 /// ```
104 ///
105 /// This allows the key type used for lookup to be different than the key stored in the map so for
106 /// example you can use `&str` to look up a value in a `Map<String, _>`. However, this runs into
107 /// a problem in the case where `T` and `K` are both a `Foo<_>` type constructor but
108 /// the contained type is different (even being the same type with different lifetimes).
109 ///
110 /// The main issue for this crate's API is that, with this method signature, you cannot perform a
111 /// lookup on a `Map<UniCase<&'static str>, _>` with a `UniCase<&'a str>` where `'a` is not
112 /// `'static`; there is no impl of `Borrow` that resolves to
113 /// `impl Borrow<UniCase<'a>> for UniCase<&'static str>` and one cannot be added either because of
114 /// all the blanket impls.
115 ///
116 /// Instead, this trait is implemented conservatively, without blanket impls, so that impls like
117 /// this may be added. This is feasible since the set of types that implement `PhfHash` is
118 /// intentionally small.
119 ///
120 /// This likely won't be fixable with specialization alone but will require full support for lattice
121 /// impls since we technically want to add overlapping blanket impls.
122 pub trait PhfBorrow<B: ?Sized> {
123 /// Convert a reference to `self` to a reference to the borrowed type.
borrow(&self) -> &B124 fn borrow(&self) -> &B;
125 }
126
127 /// Create an impl of `FmtConst` delegating to `fmt::Debug` for types that can deal with it.
128 ///
129 /// Ideally with specialization this could be just one default impl and then specialized where
130 /// it doesn't apply.
131 macro_rules! delegate_debug (
132 ($ty:ty) => {
133 impl FmtConst for $ty {
134 fn fmt_const(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
135 write!(f, "{:?}", self)
136 }
137 }
138 }
139 );
140
141 delegate_debug!(str);
142 delegate_debug!(char);
143 delegate_debug!(u8);
144 delegate_debug!(i8);
145 delegate_debug!(u16);
146 delegate_debug!(i16);
147 delegate_debug!(u32);
148 delegate_debug!(i32);
149 delegate_debug!(u64);
150 delegate_debug!(i64);
151 delegate_debug!(u128);
152 delegate_debug!(i128);
153 delegate_debug!(bool);
154
155 /// `impl PhfBorrow<T> for T`
156 macro_rules! impl_reflexive(
157 ($($t:ty),*) => (
158 $(impl PhfBorrow<$t> for $t {
159 fn borrow(&self) -> &$t {
160 self
161 }
162 })*
163 )
164 );
165
166 impl_reflexive!(
167 str,
168 char,
169 u8,
170 i8,
171 u16,
172 i16,
173 u32,
174 i32,
175 u64,
176 i64,
177 u128,
178 i128,
179 bool,
180 [u8]
181 );
182
183 #[cfg(feature = "std")]
184 impl PhfBorrow<str> for String {
borrow(&self) -> &str185 fn borrow(&self) -> &str {
186 self
187 }
188 }
189
190 #[cfg(feature = "std")]
191 impl PhfBorrow<[u8]> for Vec<u8> {
borrow(&self) -> &[u8]192 fn borrow(&self) -> &[u8] {
193 self
194 }
195 }
196
197 #[cfg(feature = "std")]
198 delegate_debug!(String);
199
200 #[cfg(feature = "std")]
201 impl PhfHash for String {
202 #[inline]
phf_hash<H: Hasher>(&self, state: &mut H)203 fn phf_hash<H: Hasher>(&self, state: &mut H) {
204 (**self).phf_hash(state)
205 }
206 }
207
208 #[cfg(feature = "std")]
209 impl PhfHash for Vec<u8> {
210 #[inline]
phf_hash<H: Hasher>(&self, state: &mut H)211 fn phf_hash<H: Hasher>(&self, state: &mut H) {
212 (**self).phf_hash(state)
213 }
214 }
215
216 impl<'a, T: 'a + PhfHash + ?Sized> PhfHash for &'a T {
phf_hash<H: Hasher>(&self, state: &mut H)217 fn phf_hash<H: Hasher>(&self, state: &mut H) {
218 (*self).phf_hash(state)
219 }
220 }
221
222 impl<'a, T: 'a + FmtConst + ?Sized> FmtConst for &'a T {
fmt_const(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result223 fn fmt_const(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
224 (*self).fmt_const(f)
225 }
226 }
227
228 impl<'a> PhfBorrow<str> for &'a str {
borrow(&self) -> &str229 fn borrow(&self) -> &str {
230 self
231 }
232 }
233
234 impl<'a> PhfBorrow<[u8]> for &'a [u8] {
borrow(&self) -> &[u8]235 fn borrow(&self) -> &[u8] {
236 self
237 }
238 }
239
240 impl PhfHash for str {
241 #[inline]
phf_hash<H: Hasher>(&self, state: &mut H)242 fn phf_hash<H: Hasher>(&self, state: &mut H) {
243 self.as_bytes().phf_hash(state)
244 }
245 }
246
247 impl PhfHash for [u8] {
248 #[inline]
phf_hash<H: Hasher>(&self, state: &mut H)249 fn phf_hash<H: Hasher>(&self, state: &mut H) {
250 state.write(self);
251 }
252 }
253
254 impl FmtConst for [u8] {
255 #[inline]
fmt_const(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result256 fn fmt_const(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
257 // slices need a leading reference
258 write!(f, "&{:?}", self)
259 }
260 }
261
262 #[cfg(feature = "unicase")]
263 impl<S> PhfHash for unicase::UniCase<S>
264 where
265 unicase::UniCase<S>: Hash,
266 {
267 #[inline]
phf_hash<H: Hasher>(&self, state: &mut H)268 fn phf_hash<H: Hasher>(&self, state: &mut H) {
269 self.hash(state)
270 }
271 }
272
273 #[cfg(feature = "unicase")]
274 impl<S> FmtConst for unicase::UniCase<S>
275 where
276 S: AsRef<str>,
277 {
fmt_const(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result278 fn fmt_const(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
279 if self.is_ascii() {
280 f.write_str("UniCase::ascii(")?;
281 } else {
282 f.write_str("UniCase::unicode(")?;
283 }
284
285 self.as_ref().fmt_const(f)?;
286 f.write_str(")")
287 }
288 }
289
290 #[cfg(feature = "unicase")]
291 impl<'b, 'a: 'b, S: ?Sized + 'a> PhfBorrow<unicase::UniCase<&'b S>> for unicase::UniCase<&'a S> {
borrow(&self) -> &unicase::UniCase<&'b S>292 fn borrow(&self) -> &unicase::UniCase<&'b S> {
293 self
294 }
295 }
296
297 #[cfg(feature = "uncased")]
298 impl PhfHash for uncased::UncasedStr {
299 #[inline]
phf_hash<H: Hasher>(&self, state: &mut H)300 fn phf_hash<H: Hasher>(&self, state: &mut H) {
301 self.hash(state)
302 }
303 }
304
305 #[cfg(feature = "uncased")]
306 impl FmtConst for uncased::UncasedStr {
fmt_const(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result307 fn fmt_const(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
308 // transmute is not stable in const fns (rust-lang/rust#53605), so
309 // `UncasedStr::new` can't be a const fn itself, but we can inline the
310 // call to transmute here in the meantime.
311 f.write_str("unsafe { ::std::mem::transmute::<&'static str, &'static UncasedStr>(")?;
312 self.as_str().fmt_const(f)?;
313 f.write_str(") }")
314 }
315 }
316
317 #[cfg(feature = "uncased")]
318 impl PhfBorrow<uncased::UncasedStr> for &uncased::UncasedStr {
borrow(&self) -> &uncased::UncasedStr319 fn borrow(&self) -> &uncased::UncasedStr {
320 self
321 }
322 }
323
324 macro_rules! sip_impl (
325 (le $t:ty) => (
326 impl PhfHash for $t {
327 #[inline]
328 fn phf_hash<H: Hasher>(&self, state: &mut H) {
329 self.to_le().hash(state);
330 }
331 }
332 );
333 ($t:ty) => (
334 impl PhfHash for $t {
335 #[inline]
336 fn phf_hash<H: Hasher>(&self, state: &mut H) {
337 self.hash(state);
338 }
339 }
340 )
341 );
342
343 sip_impl!(u8);
344 sip_impl!(i8);
345 sip_impl!(le u16);
346 sip_impl!(le i16);
347 sip_impl!(le u32);
348 sip_impl!(le i32);
349 sip_impl!(le u64);
350 sip_impl!(le i64);
351 sip_impl!(le u128);
352 sip_impl!(le i128);
353 sip_impl!(bool);
354
355 impl PhfHash for char {
356 #[inline]
phf_hash<H: Hasher>(&self, state: &mut H)357 fn phf_hash<H: Hasher>(&self, state: &mut H) {
358 (*self as u32).phf_hash(state)
359 }
360 }
361
362 // minimize duplicated code since formatting drags in quite a bit
fmt_array(array: &[u8], f: &mut fmt::Formatter<'_>) -> fmt::Result363 fn fmt_array(array: &[u8], f: &mut fmt::Formatter<'_>) -> fmt::Result {
364 write!(f, "{:?}", array)
365 }
366
367 macro_rules! array_impl (
368 ($t:ty, $n:expr) => (
369 impl PhfHash for [$t; $n] {
370 #[inline]
371 fn phf_hash<H: Hasher>(&self, state: &mut H) {
372 state.write(self);
373 }
374 }
375
376 impl FmtConst for [$t; $n] {
377 fn fmt_const(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
378 fmt_array(self, f)
379 }
380 }
381
382 impl PhfBorrow<[$t]> for [$t; $n] {
383 fn borrow(&self) -> &[$t] {
384 self
385 }
386 }
387 )
388 );
389
390 array_impl!(u8, 1);
391 array_impl!(u8, 2);
392 array_impl!(u8, 3);
393 array_impl!(u8, 4);
394 array_impl!(u8, 5);
395 array_impl!(u8, 6);
396 array_impl!(u8, 7);
397 array_impl!(u8, 8);
398 array_impl!(u8, 9);
399 array_impl!(u8, 10);
400 array_impl!(u8, 11);
401 array_impl!(u8, 12);
402 array_impl!(u8, 13);
403 array_impl!(u8, 14);
404 array_impl!(u8, 15);
405 array_impl!(u8, 16);
406 array_impl!(u8, 17);
407 array_impl!(u8, 18);
408 array_impl!(u8, 19);
409 array_impl!(u8, 20);
410 array_impl!(u8, 21);
411 array_impl!(u8, 22);
412 array_impl!(u8, 23);
413 array_impl!(u8, 24);
414 array_impl!(u8, 25);
415 array_impl!(u8, 26);
416 array_impl!(u8, 27);
417 array_impl!(u8, 28);
418 array_impl!(u8, 29);
419 array_impl!(u8, 30);
420 array_impl!(u8, 31);
421 array_impl!(u8, 32);
422