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")]
5extern crate std as core;
6
7use core::fmt;
8use core::hash::{Hash, Hasher};
9use core::num::Wrapping;
10use siphasher::sip128::{Hash128, Hasher128, SipHasher13};
11
12#[non_exhaustive]
13pub 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.
22pub type HashKey = u64;
23
24#[inline]
25pub 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]
31pub fn hash<T: ?Sized + PhfHash>(x: &T, key: &HashKey) -> Hashes {
32 let mut hasher: SipHasher13 = SipHasher13::new_with_keys(key0:0, *key);
33 x.phf_hash(&mut hasher);
34
35 let Hash128 {
36 h1: lower: u64,
37 h2: upper: u64,
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]
53pub fn get_index(hashes: &Hashes, disps: &[(u32, u32)], len: usize) -> u32 {
54 let (d1: u32, d2: u32) = 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.
63pub trait PhfHash {
64 /// Feeds the value into the state given, updating the hasher as necessary.
65 fn phf_hash<H: Hasher>(&self, state: &mut H);
66
67 /// Feeds a slice of this type into the state provided.
68 fn phf_hash_slice<H: Hasher>(data: &[Self], state: &mut H)
69 where
70 Self: Sized,
71 {
72 for piece: &Self 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`.
79pub trait FmtConst {
80 /// Print a `const` expression representing this value.
81 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.
122pub trait PhfBorrow<B: ?Sized> {
123 /// Convert a reference to `self` to a reference to the borrowed type.
124 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.
131macro_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
141delegate_debug!(str);
142delegate_debug!(char);
143delegate_debug!(u8);
144delegate_debug!(i8);
145delegate_debug!(u16);
146delegate_debug!(i16);
147delegate_debug!(u32);
148delegate_debug!(i32);
149delegate_debug!(u64);
150delegate_debug!(i64);
151delegate_debug!(u128);
152delegate_debug!(i128);
153delegate_debug!(bool);
154
155/// `impl PhfBorrow<T> for T`
156macro_rules! impl_reflexive(
157 ($($t:ty),*) => (
158 $(impl PhfBorrow<$t> for $t {
159 fn borrow(&self) -> &$t {
160 self
161 }
162 })*
163 )
164);
165
166impl_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")]
184impl PhfBorrow<str> for String {
185 fn borrow(&self) -> &str {
186 self
187 }
188}
189
190#[cfg(feature = "std")]
191impl PhfBorrow<[u8]> for Vec<u8> {
192 fn borrow(&self) -> &[u8] {
193 self
194 }
195}
196
197#[cfg(feature = "std")]
198delegate_debug!(String);
199
200#[cfg(feature = "std")]
201impl PhfHash for String {
202 #[inline]
203 fn phf_hash<H: Hasher>(&self, state: &mut H) {
204 (**self).phf_hash(state)
205 }
206}
207
208#[cfg(feature = "std")]
209impl PhfHash for Vec<u8> {
210 #[inline]
211 fn phf_hash<H: Hasher>(&self, state: &mut H) {
212 (**self).phf_hash(state)
213 }
214}
215
216impl<'a, T: 'a + PhfHash + ?Sized> PhfHash for &'a T {
217 fn phf_hash<H: Hasher>(&self, state: &mut H) {
218 (*self).phf_hash(state)
219 }
220}
221
222impl<'a, T: 'a + FmtConst + ?Sized> FmtConst for &'a T {
223 fn fmt_const(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
224 (*self).fmt_const(f)
225 }
226}
227
228impl<'a> PhfBorrow<str> for &'a str {
229 fn borrow(&self) -> &str {
230 self
231 }
232}
233
234impl<'a> PhfBorrow<[u8]> for &'a [u8] {
235 fn borrow(&self) -> &[u8] {
236 self
237 }
238}
239
240impl PhfHash for str {
241 #[inline]
242 fn phf_hash<H: Hasher>(&self, state: &mut H) {
243 self.as_bytes().phf_hash(state)
244 }
245}
246
247impl PhfHash for [u8] {
248 #[inline]
249 fn phf_hash<H: Hasher>(&self, state: &mut H) {
250 state.write(self);
251 }
252}
253
254impl FmtConst for [u8] {
255 #[inline]
256 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")]
263impl<S> PhfHash for unicase::UniCase<S>
264where
265 unicase::UniCase<S>: Hash,
266{
267 #[inline]
268 fn phf_hash<H: Hasher>(&self, state: &mut H) {
269 self.hash(state)
270 }
271}
272
273#[cfg(feature = "unicase")]
274impl<S> FmtConst for unicase::UniCase<S>
275where
276 S: AsRef<str>,
277{
278 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")]
291impl<'b, 'a: 'b, S: ?Sized + 'a> PhfBorrow<unicase::UniCase<&'b S>> for unicase::UniCase<&'a S> {
292 fn borrow(&self) -> &unicase::UniCase<&'b S> {
293 self
294 }
295}
296
297#[cfg(feature = "uncased")]
298impl PhfHash for uncased::UncasedStr {
299 #[inline]
300 fn phf_hash<H: Hasher>(&self, state: &mut H) {
301 self.hash(state)
302 }
303}
304
305#[cfg(feature = "uncased")]
306impl FmtConst for uncased::UncasedStr {
307 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")]
318impl PhfBorrow<uncased::UncasedStr> for &uncased::UncasedStr {
319 fn borrow(&self) -> &uncased::UncasedStr {
320 self
321 }
322}
323
324macro_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
343sip_impl!(u8);
344sip_impl!(i8);
345sip_impl!(le u16);
346sip_impl!(le i16);
347sip_impl!(le u32);
348sip_impl!(le i32);
349sip_impl!(le u64);
350sip_impl!(le i64);
351sip_impl!(le u128);
352sip_impl!(le i128);
353sip_impl!(bool);
354
355impl PhfHash for char {
356 #[inline]
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
363fn fmt_array(array: &[u8], f: &mut fmt::Formatter<'_>) -> fmt::Result {
364 write!(f, "{:?}", array)
365}
366
367macro_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
390array_impl!(u8, 1);
391array_impl!(u8, 2);
392array_impl!(u8, 3);
393array_impl!(u8, 4);
394array_impl!(u8, 5);
395array_impl!(u8, 6);
396array_impl!(u8, 7);
397array_impl!(u8, 8);
398array_impl!(u8, 9);
399array_impl!(u8, 10);
400array_impl!(u8, 11);
401array_impl!(u8, 12);
402array_impl!(u8, 13);
403array_impl!(u8, 14);
404array_impl!(u8, 15);
405array_impl!(u8, 16);
406array_impl!(u8, 17);
407array_impl!(u8, 18);
408array_impl!(u8, 19);
409array_impl!(u8, 20);
410array_impl!(u8, 21);
411array_impl!(u8, 22);
412array_impl!(u8, 23);
413array_impl!(u8, 24);
414array_impl!(u8, 25);
415array_impl!(u8, 26);
416array_impl!(u8, 27);
417array_impl!(u8, 28);
418array_impl!(u8, 29);
419array_impl!(u8, 30);
420array_impl!(u8, 31);
421array_impl!(u8, 32);
422