retex_engine/
hash.rs

1//! The control-sequence table (TeX's `hash`).
2//!
3//! Every control sequence gets a dense [`CsId`]. A name is a byte string in
4//! (extended) UTF-8. A name of exactly one character is a *single-character*
5//! control sequence such as `\a` or `\ `. Active characters live in their
6//! own namespace. *Frozen* control sequences (TeX's `frozen_…` locations)
7//! have a printable name but cannot be looked up by name.
8
9use std::collections::HashMap;
10
11use crate::utf8x;
12
13/// Identifier of a control sequence.
14#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, PartialOrd, Ord, Default)]
15pub struct CsId(pub u32);
16
17/// What kind of control sequence an id refers to.
18#[derive(Clone, Debug, PartialEq, Eq)]
19pub enum CsKind {
20    /// An active character.
21    Active(u32),
22    /// `\csname\endcsname`: the control sequence with the empty name.
23    Null,
24    /// A single-character control sequence.
25    Single(u32),
26    /// A multi-letter control sequence.
27    Multi,
28    /// A frozen copy of a primitive or special location.
29    Frozen,
30    /// The undefined control sequence location used for error recovery.
31    Undefined,
32    /// An anonymous internal quantity printed as its bare name (LuaTeX's
33    /// `[internal backend integer]` and friends).
34    Internal,
35}
36
37/// Prefix of active-character keys; never appears in UTF-8 text.
38const ACTIVE_PREFIX: u8 = 0xFF;
39
40/// A fast hash for short keys (control-sequence names): words are folded
41/// in with a multiply and a rotation. Not resistant to collision attacks,
42/// which do not matter for a TeX run.
43#[derive(Default, Clone, Copy)]
44pub struct FastHasher(u64);
45
46impl std::hash::Hasher for FastHasher {
47    #[inline]
48    fn write(&mut self, bytes: &[u8]) {
49        let mut h = self.0;
50        let mut chunks = bytes.chunks_exact(8);
51        for c in &mut chunks {
52            let w = u64::from_le_bytes([c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7]]);
53            h = (h ^ w).wrapping_mul(0x9E37_79B9_7F4A_7C15).rotate_left(29);
54        }
55        let mut last = 0u64;
56        for (i, &b) in chunks.remainder().iter().enumerate() {
57            last |= u64::from(b) << (8 * i);
58        }
59        h = (h ^ last ^ (bytes.len() as u64)).wrapping_mul(0x9E37_79B9_7F4A_7C15);
60        self.0 = h ^ (h >> 31);
61    }
62
63    #[inline]
64    fn write_u32(&mut self, n: u32) {
65        self.0 = (self.0 ^ u64::from(n)).wrapping_mul(0x9E37_79B9_7F4A_7C15);
66        self.0 ^= self.0 >> 31;
67    }
68
69    #[inline]
70    fn write_usize(&mut self, n: usize) {
71        self.0 = (self.0 ^ n as u64).wrapping_mul(0x9E37_79B9_7F4A_7C15);
72        self.0 ^= self.0 >> 31;
73    }
74
75    #[inline]
76    fn finish(&self) -> u64 {
77        self.0
78    }
79}
80
81/// [`std::hash::BuildHasher`] for [`FastHasher`].
82pub type FastHash = std::hash::BuildHasherDefault<FastHasher>;
83
84/// The control-sequence table.
85#[derive(Debug, Clone)]
86pub struct CsTable {
87    map: HashMap<Box<[u8]>, CsId, FastHash>,
88    names: Vec<Box<[u8]>>,
89    kinds: Vec<CsKind>,
90    /// Ids of active characters already looked up.
91    actives: HashMap<u32, CsId, FastHash>,
92}
93
94/// "No control sequence" (TeX's `cur_cs = 0` for character tokens).
95pub const NO_CS: CsId = CsId(0);
96/// The id of `\csname\endcsname`.
97pub const NULL_CS: CsId = CsId(1);
98/// The id of the undefined control sequence (TeX's
99/// `undefined_control_sequence`), used as a dummy.
100pub const UNDEFINED_CS: CsId = CsId(2);
101
102impl Default for CsTable {
103    fn default() -> Self {
104        Self::new()
105    }
106}
107
108impl CsTable {
109    /// A table containing only [`NO_CS`], [`NULL_CS`] and [`UNDEFINED_CS`].
110    pub fn new() -> Self {
111        let mut t = CsTable {
112            map: HashMap::with_capacity_and_hasher(32768, FastHash::default()),
113            names: Vec::with_capacity(32768),
114            kinds: Vec::with_capacity(32768),
115            actives: HashMap::default(),
116        };
117        t.names.push(Box::from(&b""[..]));
118        t.kinds.push(CsKind::Undefined);
119        let null = t.lookup_or_insert(b"");
120        debug_assert_eq!(null, NULL_CS);
121        t.names.push(Box::from(&b""[..]));
122        t.kinds.push(CsKind::Undefined);
123        t
124    }
125
126    /// Number of ids allocated so far.
127    pub fn len(&self) -> usize {
128        self.names.len()
129    }
130
131    /// Whether the table is empty (never true: three ids are preallocated).
132    pub fn is_empty(&self) -> bool {
133        self.names.is_empty()
134    }
135
136    /// Looks a name up, creating the control sequence if necessary.
137    pub fn lookup_or_insert(&mut self, name: &[u8]) -> CsId {
138        if let Some(&id) = self.map.get(name) {
139            return id;
140        }
141        let id = CsId(self.names.len() as u32);
142        let kind = if name.is_empty() {
143            CsKind::Null
144        } else if let Some(c) = utf8x::single_char(name) {
145            CsKind::Single(c)
146        } else {
147            CsKind::Multi
148        };
149        self.names.push(Box::from(name));
150        self.kinds.push(kind);
151        self.map.insert(Box::from(name), id);
152        id
153    }
154
155    /// Looks a name up without creating it.
156    pub fn lookup(&self, name: &[u8]) -> Option<CsId> {
157        self.map.get(name).copied()
158    }
159
160    /// The id of active character `c`, creating it if necessary.
161    pub fn active(&mut self, c: u32) -> CsId {
162        if let Some(&id) = self.actives.get(&c) {
163            return id;
164        }
165        let mut key = vec![ACTIVE_PREFIX];
166        utf8x::push(&mut key, c);
167        if let Some(&id) = self.map.get(&key[..]) {
168            self.actives.insert(c, id);
169            return id;
170        }
171        let id = CsId(self.names.len() as u32);
172        self.names.push(utf8x::encode(c).into_boxed_slice());
173        self.kinds.push(CsKind::Active(c));
174        self.map.insert(key.into_boxed_slice(), id);
175        self.actives.insert(c, id);
176        id
177    }
178
179    /// The id of active character `c`, if it exists.
180    pub fn lookup_active(&self, c: u32) -> Option<CsId> {
181        let mut key = vec![ACTIVE_PREFIX];
182        utf8x::push(&mut key, c);
183        self.map.get(&key[..]).copied()
184    }
185
186    /// The id of the single-character control sequence `\c`.
187    pub fn single(&mut self, c: u32) -> CsId {
188        self.lookup_or_insert(&utf8x::encode(c))
189    }
190
191    /// Allocates an internal control sequence printed as the bare `name`.
192    pub fn new_internal(&mut self, name: &[u8]) -> CsId {
193        let id = CsId(self.names.len() as u32);
194        self.names.push(Box::from(name));
195        self.kinds.push(CsKind::Internal);
196        id
197    }
198
199    /// Allocates a frozen control sequence printed as `name`.
200    pub fn new_frozen(&mut self, name: &[u8]) -> CsId {
201        let id = CsId(self.names.len() as u32);
202        self.names.push(Box::from(name));
203        self.kinds.push(CsKind::Frozen);
204        id
205    }
206
207    /// The name of a control sequence (for active characters: the
208    /// character's encoding).
209    pub fn name(&self, id: CsId) -> &[u8] {
210        &self.names[id.0 as usize]
211    }
212
213    /// The kind of a control sequence.
214    pub fn kind(&self, id: CsId) -> &CsKind {
215        &self.kinds[id.0 as usize]
216    }
217
218    /// Whether `id` names an entry of the table.
219    pub fn contains(&self, id: CsId) -> bool {
220        (id.0 as usize) < self.kinds.len()
221    }
222
223    /// All entries as (name, kind) in id order, for format dumping.
224    pub fn entries(&self) -> impl Iterator<Item = (&[u8], &CsKind)> {
225        self.names.iter().map(|n| &n[..]).zip(self.kinds.iter())
226    }
227
228    /// Rebuilds a table from dumped entries (the inverse of
229    /// [`entries`](Self::entries)).
230    pub fn from_entries(entries: Vec<(Box<[u8]>, CsKind)>) -> CsTable {
231        let mut t = CsTable {
232            map: HashMap::with_capacity_and_hasher(entries.len(), FastHash::default()),
233            names: Vec::with_capacity(entries.len()),
234            kinds: Vec::with_capacity(entries.len()),
235            actives: HashMap::default(),
236        };
237        for (i, (name, kind)) in entries.into_iter().enumerate() {
238            let id = CsId(i as u32);
239            match &kind {
240                CsKind::Active(c) => {
241                    let mut key = vec![ACTIVE_PREFIX];
242                    utf8x::push(&mut key, *c);
243                    t.map.insert(key.into_boxed_slice(), id);
244                }
245                CsKind::Null | CsKind::Single(_) | CsKind::Multi => {
246                    if i != 0 && i != 2 {
247                        t.map.insert(name.clone(), id);
248                    }
249                }
250                _ => {}
251            }
252            t.names.push(name);
253            t.kinds.push(kind);
254        }
255        t
256    }
257
258    /// Iterates over all (name, id) pairs that can be looked up by name
259    /// (excluding active characters).
260    pub fn iter_named(&self) -> impl Iterator<Item = (&[u8], CsId)> {
261        self.map
262            .iter()
263            .filter(|(k, _)| k.first() != Some(&ACTIVE_PREFIX))
264            .map(|(k, v)| (&k[..], *v))
265    }
266}
267
268#[cfg(test)]
269mod tests {
270    use super::*;
271
272    #[test]
273    fn interning() {
274        let mut t = CsTable::new();
275        let a = t.lookup_or_insert(b"relax");
276        assert_eq!(t.lookup_or_insert(b"relax"), a);
277        assert_eq!(t.kind(a), &CsKind::Multi);
278        let s = t.single('a' as u32);
279        assert_eq!(t.kind(s), &CsKind::Single('a' as u32));
280        assert_eq!(t.lookup(b"a"), Some(s));
281        let act = t.active('a' as u32);
282        assert_ne!(act, s);
283        assert_eq!(t.kind(act), &CsKind::Active('a' as u32));
284        let f = t.new_frozen(b"fi");
285        assert_eq!(t.name(f), b"fi");
286        assert_eq!(t.lookup(b"fi"), None);
287        assert_eq!(t.kind(NULL_CS), &CsKind::Null);
288    }
289}
retex_engine/hash.rs

retex_engine/
hash.rs
