Skip to main content

file_identify/
table.rs

1//! Static string-keyed lookup tables generated from identify.
2//!
3//! Each table is a sorted `(key, TagSet)` slice plus a precomputed
4//! open-addressing index (FNV-1a, Fibonacci hashing, linear probing with a
5//! known maximum probe length), so a lookup hashes the key once, compares it
6//! against at most `max_probe + 1` candidates and never allocates.
7//!
8//! The hash functions must stay identical to `xtask/src/codegen.rs`.
9
10use core::fmt;
11use core::iter::FusedIterator;
12
13use crate::tags::TagSet;
14
15const EMPTY_SLOT: u16 = u16::MAX;
16
17/// FNV-1a over `key`, with the offset basis perturbed by `seed`.
18fn hash(seed: u64, key: &[u8]) -> u64 {
19    key.iter().fold(0xcbf2_9ce4_8422_2325_u64 ^ seed, |h, &b| {
20        (h ^ u64::from(b)).wrapping_mul(0x0000_0100_0000_01b3)
21    })
22}
23
24/// Fibonacci hashing of `h` into `64 - shift` bits.
25fn slot(h: u64, shift: u32) -> usize {
26    let s = h
27        .wrapping_mul(0x9e37_79b9_7f4a_7c15)
28        .checked_shr(shift)
29        .unwrap_or(0);
30    usize::try_from(s).unwrap_or(0)
31}
32
33/// A generated perfect-ish hash index from byte strings to positions in a
34/// key array.
35pub(crate) struct StrIndex {
36    seed: u64,
37    shift: u32,
38    max_probe: u32,
39    /// Shortest and longest key in bytes (cheap rejection before hashing).
40    min_len: usize,
41    max_len: usize,
42    slots: &'static [u16],
43}
44
45impl StrIndex {
46    pub(crate) const fn new(
47        seed: u64,
48        shift: u32,
49        max_probe: u32,
50        (min_len, max_len): (usize, usize),
51        slots: &'static [u16],
52    ) -> Self {
53        Self {
54            seed,
55            shift,
56            max_probe,
57            min_len,
58            max_len,
59            slots,
60        }
61    }
62
63    /// Position of `key`, given `key_at(i)` returning the `i`-th key.
64    pub(crate) fn find(
65        &self,
66        key: &[u8],
67        key_at: impl Fn(usize) -> Option<&'static str>,
68    ) -> Option<usize> {
69        if key.len() < self.min_len || key.len() > self.max_len {
70            return None;
71        }
72        let mask = self.slots.len().checked_sub(1)?;
73        let mut s = slot(hash(self.seed, key), self.shift) & mask;
74        for _ in 0..=self.max_probe {
75            let idx = *self.slots.get(s)?;
76            if idx == EMPTY_SLOT {
77                return None;
78            }
79            let idx = usize::from(idx);
80            if key_at(idx)?.as_bytes() == key {
81                return Some(idx);
82            }
83            s = (s + 1) & mask;
84        }
85        None
86    }
87}
88
89/// One of identify's lookup tables ([`EXTENSIONS`](crate::extensions::EXTENSIONS),
90/// [`NAMES`](crate::extensions::NAMES), …): a static map from `&str` keys to
91/// [`TagSet`]s.
92///
93/// Lookups hash the key once and never allocate. Iteration yields entries
94/// sorted by key.
95pub struct TagTable {
96    entries: &'static [(&'static str, TagSet)],
97    index: StrIndex,
98}
99
100impl TagTable {
101    pub(crate) const fn new(entries: &'static [(&'static str, TagSet)], index: StrIndex) -> Self {
102        Self { entries, index }
103    }
104
105    /// The tags stored for `key` (exact, case-sensitive match).
106    #[must_use]
107    pub fn get(&self, key: &str) -> Option<TagSet> {
108        self.get_bytes(key.as_bytes())
109    }
110
111    /// Like [`get`](TagTable::get) for a key given as bytes (e.g. a
112    /// non-UTF-8 file name, which never matches).
113    #[must_use]
114    pub fn get_bytes(&self, key: &[u8]) -> Option<TagSet> {
115        let i = self
116            .index
117            .find(key, |i| self.entries.get(i).map(|(k, _)| *k))?;
118        self.entries.get(i).map(|(_, tags)| *tags)
119    }
120
121    /// Whether `key` is in the table.
122    #[must_use]
123    pub fn contains_key(&self, key: &str) -> bool {
124        self.get(key).is_some()
125    }
126
127    /// Number of entries.
128    #[must_use]
129    pub const fn len(&self) -> usize {
130        self.entries.len()
131    }
132
133    /// Whether the table has no entries.
134    #[must_use]
135    pub const fn is_empty(&self) -> bool {
136        self.entries.is_empty()
137    }
138
139    /// All `(key, tags)` entries, sorted by key.
140    #[must_use]
141    pub const fn entries(&self) -> &'static [(&'static str, TagSet)] {
142        self.entries
143    }
144
145    /// Iterate over `(key, tags)` entries sorted by key.
146    #[must_use = "iterators are lazy and do nothing unless consumed"]
147    pub fn iter(
148        &self,
149    ) -> impl DoubleEndedIterator<Item = (&'static str, TagSet)> + ExactSizeIterator + FusedIterator
150    {
151        self.entries.iter().copied()
152    }
153
154    /// Iterate over the keys in sorted order.
155    #[must_use = "iterators are lazy and do nothing unless consumed"]
156    pub fn keys(
157        &self,
158    ) -> impl DoubleEndedIterator<Item = &'static str> + ExactSizeIterator + FusedIterator {
159        self.entries.iter().map(|(k, _)| *k)
160    }
161
162    /// Iterate over the tag sets in key order.
163    #[must_use = "iterators are lazy and do nothing unless consumed"]
164    pub fn values(
165        &self,
166    ) -> impl DoubleEndedIterator<Item = TagSet> + ExactSizeIterator + FusedIterator {
167        self.entries.iter().map(|(_, v)| *v)
168    }
169}
170
171impl fmt::Debug for TagTable {
172    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
173        f.debug_map().entries(self.iter()).finish()
174    }
175}
176
177impl<'a> IntoIterator for &'a TagTable {
178    type Item = &'a (&'static str, TagSet);
179    type IntoIter = core::slice::Iter<'a, (&'static str, TagSet)>;
180
181    fn into_iter(self) -> Self::IntoIter {
182        self.entries.iter()
183    }
184}
185
186#[cfg(test)]
187mod tests {
188    use crate::extensions::{EXTENSIONS, EXTENSIONS_NEED_BINARY_CHECK, NAMES};
189    use crate::interpreters::INTERPRETERS;
190
191    #[test]
192    fn every_key_is_found_through_the_index() {
193        for table in [
194            &EXTENSIONS,
195            &EXTENSIONS_NEED_BINARY_CHECK,
196            &NAMES,
197            &INTERPRETERS,
198        ] {
199            assert!(
200                table.keys().zip(table.keys().skip(1)).all(|(a, b)| a < b),
201                "sorted"
202            );
203            for (key, tags) in table.iter() {
204                assert_eq!(table.get(key), Some(tags), "{key}");
205            }
206        }
207    }
208
209    #[test]
210    fn misses() {
211        for key in [
212            "",
213            "PY",
214            "py ",
215            "xx",
216            "a-very-long-key-that-is-not-there",
217            "\u{fffd}",
218        ] {
219            assert_eq!(EXTENSIONS.get(key), None, "{key}");
220        }
221        assert_eq!(NAMES.get_bytes(b"\xff\xfe"), None);
222        assert!(!INTERPRETERS.is_empty());
223        assert!(format!("{INTERPRETERS:?}").contains("\"python3\""));
224        assert_eq!((&NAMES).into_iter().count(), NAMES.len());
225    }
226}