retex-engine 1.0.0

//! The control-sequence table (TeX's `hash`).
//!
//! Every control sequence gets a dense [`CsId`]. A name is a byte string in
//! (extended) UTF-8. A name of exactly one character is a *single-character*
//! control sequence such as `\a` or `\ `. Active characters live in their
//! own namespace. *Frozen* control sequences (TeX's `frozen_…` locations)
//! have a printable name but cannot be looked up by name.

use std::collections::HashMap;

use crate::utf8x;

/// Identifier of a control sequence.
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, PartialOrd, Ord, Default)]
pub struct CsId(pub u32);

/// What kind of control sequence an id refers to.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum CsKind {
    /// An active character.
    Active(u32),
    /// `\csname\endcsname`: the control sequence with the empty name.
    Null,
    /// A single-character control sequence.
    Single(u32),
    /// A multi-letter control sequence.
    Multi,
    /// A frozen copy of a primitive or special location.
    Frozen,
    /// The undefined control sequence location used for error recovery.
    Undefined,
    /// An anonymous internal quantity printed as its bare name (LuaTeX's
    /// `[internal backend integer]` and friends).
    Internal,
}

/// Prefix of active-character keys; never appears in UTF-8 text.
const ACTIVE_PREFIX: u8 = 0xFF;

/// A fast hash for short keys (control-sequence names): words are folded
/// in with a multiply and a rotation. Not resistant to collision attacks,
/// which do not matter for a TeX run.
#[derive(Default, Clone, Copy)]
pub struct FastHasher(u64);

impl std::hash::Hasher for FastHasher {
    #[inline]
    fn write(&mut self, bytes: &[u8]) {
        let mut h = self.0;
        let mut chunks = bytes.chunks_exact(8);
        for c in &mut chunks {
            let w = u64::from_le_bytes([c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7]]);
            h = (h ^ w).wrapping_mul(0x9E37_79B9_7F4A_7C15).rotate_left(29);
        }
        let mut last = 0u64;
        for (i, &b) in chunks.remainder().iter().enumerate() {
            last |= u64::from(b) << (8 * i);
        }
        h = (h ^ last ^ (bytes.len() as u64)).wrapping_mul(0x9E37_79B9_7F4A_7C15);
        self.0 = h ^ (h >> 31);
    }

    #[inline]
    fn write_u32(&mut self, n: u32) {
        self.0 = (self.0 ^ u64::from(n)).wrapping_mul(0x9E37_79B9_7F4A_7C15);
        self.0 ^= self.0 >> 31;
    }

    #[inline]
    fn write_usize(&mut self, n: usize) {
        self.0 = (self.0 ^ n as u64).wrapping_mul(0x9E37_79B9_7F4A_7C15);
        self.0 ^= self.0 >> 31;
    }

    #[inline]
    fn finish(&self) -> u64 {
        self.0
    }
}

/// [`std::hash::BuildHasher`] for [`FastHasher`].
pub type FastHash = std::hash::BuildHasherDefault<FastHasher>;

/// The control-sequence table.
#[derive(Debug, Clone)]
pub struct CsTable {
    map: HashMap<Box<[u8]>, CsId, FastHash>,
    names: Vec<Box<[u8]>>,
    kinds: Vec<CsKind>,
    /// Ids of active characters already looked up.
    actives: HashMap<u32, CsId, FastHash>,
}

/// "No control sequence" (TeX's `cur_cs = 0` for character tokens).
pub const NO_CS: CsId = CsId(0);
/// The id of `\csname\endcsname`.
pub const NULL_CS: CsId = CsId(1);
/// The id of the undefined control sequence (TeX's
/// `undefined_control_sequence`), used as a dummy.
pub const UNDEFINED_CS: CsId = CsId(2);

impl Default for CsTable {
    fn default() -> Self {
        Self::new()
    }
}

impl CsTable {
    /// A table containing only [`NO_CS`], [`NULL_CS`] and [`UNDEFINED_CS`].
    pub fn new() -> Self {
        let mut t = CsTable {
            map: HashMap::with_capacity_and_hasher(32768, FastHash::default()),
            names: Vec::with_capacity(32768),
            kinds: Vec::with_capacity(32768),
            actives: HashMap::default(),
        };
        t.names.push(Box::from(&b""[..]));
        t.kinds.push(CsKind::Undefined);
        let null = t.lookup_or_insert(b"");
        debug_assert_eq!(null, NULL_CS);
        t.names.push(Box::from(&b""[..]));
        t.kinds.push(CsKind::Undefined);
        t
    }

    /// Number of ids allocated so far.
    pub fn len(&self) -> usize {
        self.names.len()
    }

    /// Whether the table is empty (never true: three ids are preallocated).
    pub fn is_empty(&self) -> bool {
        self.names.is_empty()
    }

    /// Looks a name up, creating the control sequence if necessary.
    pub fn lookup_or_insert(&mut self, name: &[u8]) -> CsId {
        if let Some(&id) = self.map.get(name) {
            return id;
        }
        let id = CsId(self.names.len() as u32);
        let kind = if name.is_empty() {
            CsKind::Null
        } else if let Some(c) = utf8x::single_char(name) {
            CsKind::Single(c)
        } else {
            CsKind::Multi
        };
        self.names.push(Box::from(name));
        self.kinds.push(kind);
        self.map.insert(Box::from(name), id);
        id
    }

    /// Looks a name up without creating it.
    pub fn lookup(&self, name: &[u8]) -> Option<CsId> {
        self.map.get(name).copied()
    }

    /// The id of active character `c`, creating it if necessary.
    pub fn active(&mut self, c: u32) -> CsId {
        if let Some(&id) = self.actives.get(&c) {
            return id;
        }
        let mut key = vec![ACTIVE_PREFIX];
        utf8x::push(&mut key, c);
        if let Some(&id) = self.map.get(&key[..]) {
            self.actives.insert(c, id);
            return id;
        }
        let id = CsId(self.names.len() as u32);
        self.names.push(utf8x::encode(c).into_boxed_slice());
        self.kinds.push(CsKind::Active(c));
        self.map.insert(key.into_boxed_slice(), id);
        self.actives.insert(c, id);
        id
    }

    /// The id of active character `c`, if it exists.
    pub fn lookup_active(&self, c: u32) -> Option<CsId> {
        let mut key = vec![ACTIVE_PREFIX];
        utf8x::push(&mut key, c);
        self.map.get(&key[..]).copied()
    }

    /// The id of the single-character control sequence `\c`.
    pub fn single(&mut self, c: u32) -> CsId {
        self.lookup_or_insert(&utf8x::encode(c))
    }

    /// Allocates an internal control sequence printed as the bare `name`.
    pub fn new_internal(&mut self, name: &[u8]) -> CsId {
        let id = CsId(self.names.len() as u32);
        self.names.push(Box::from(name));
        self.kinds.push(CsKind::Internal);
        id
    }

    /// Allocates a frozen control sequence printed as `name`.
    pub fn new_frozen(&mut self, name: &[u8]) -> CsId {
        let id = CsId(self.names.len() as u32);
        self.names.push(Box::from(name));
        self.kinds.push(CsKind::Frozen);
        id
    }

    /// The name of a control sequence (for active characters: the
    /// character's encoding).
    pub fn name(&self, id: CsId) -> &[u8] {
        &self.names[id.0 as usize]
    }

    /// The kind of a control sequence.
    pub fn kind(&self, id: CsId) -> &CsKind {
        &self.kinds[id.0 as usize]
    }

    /// Whether `id` names an entry of the table.
    pub fn contains(&self, id: CsId) -> bool {
        (id.0 as usize) < self.kinds.len()
    }

    /// All entries as (name, kind) in id order, for format dumping.
    pub fn entries(&self) -> impl Iterator<Item = (&[u8], &CsKind)> {
        self.names.iter().map(|n| &n[..]).zip(self.kinds.iter())
    }

    /// Rebuilds a table from dumped entries (the inverse of
    /// [`entries`](Self::entries)).
    pub fn from_entries(entries: Vec<(Box<[u8]>, CsKind)>) -> CsTable {
        let mut t = CsTable {
            map: HashMap::with_capacity_and_hasher(entries.len(), FastHash::default()),
            names: Vec::with_capacity(entries.len()),
            kinds: Vec::with_capacity(entries.len()),
            actives: HashMap::default(),
        };
        for (i, (name, kind)) in entries.into_iter().enumerate() {
            let id = CsId(i as u32);
            match &kind {
                CsKind::Active(c) => {
                    let mut key = vec![ACTIVE_PREFIX];
                    utf8x::push(&mut key, *c);
                    t.map.insert(key.into_boxed_slice(), id);
                }
                CsKind::Null | CsKind::Single(_) | CsKind::Multi => {
                    if i != 0 && i != 2 {
                        t.map.insert(name.clone(), id);
                    }
                }
                _ => {}
            }
            t.names.push(name);
            t.kinds.push(kind);
        }
        t
    }

    /// Iterates over all (name, id) pairs that can be looked up by name
    /// (excluding active characters).
    pub fn iter_named(&self) -> impl Iterator<Item = (&[u8], CsId)> {
        self.map
            .iter()
            .filter(|(k, _)| k.first() != Some(&ACTIVE_PREFIX))
            .map(|(k, v)| (&k[..], *v))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn interning() {
        let mut t = CsTable::new();
        let a = t.lookup_or_insert(b"relax");
        assert_eq!(t.lookup_or_insert(b"relax"), a);
        assert_eq!(t.kind(a), &CsKind::Multi);
        let s = t.single('a' as u32);
        assert_eq!(t.kind(s), &CsKind::Single('a' as u32));
        assert_eq!(t.lookup(b"a"), Some(s));
        let act = t.active('a' as u32);
        assert_ne!(act, s);
        assert_eq!(t.kind(act), &CsKind::Active('a' as u32));
        let f = t.new_frozen(b"fi");
        assert_eq!(t.name(f), b"fi");
        assert_eq!(t.lookup(b"fi"), None);
        assert_eq!(t.kind(NULL_CS), &CsKind::Null);
    }
}