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