//! Reverse dictionary automaton (`SMH-SPEC-SPEC0001`, Authentication). //! //! Persistent transition maps make every transition bounded by alphabet depth, //! including branches in the JSON token graph; no runtime failure-chain walk. #[derive(Clone, Copy, Default)] struct Branch { left: u32, right: u32, } #[derive(Default)] struct BuildingNode { transition: u32, failure: u32, edge_start: u32, edge_count: u16, longest: u16, } struct Node { transition: u32, longest: u16, } pub(super) struct Automaton { alphabet: Box<[u32]>, nodes: Box<[Node]>, branches: Vec, #[cfg(test)] comparisons: std::cell::Cell, } impl Automaton { pub(super) fn new(mut patterns: Vec>) -> Self { patterns.sort_unstable(); let total: usize = patterns.iter().map(Vec::len).sum(); assert!( total <= super::CREDENTIAL_TOTAL_BYTES_MAX, "automaton input must have passed aggregate credential validation" ); let mut alphabet: Vec<_> = patterns.iter().flatten().copied().collect(); alphabet.sort_unstable(); alphabet.dedup(); let mut nodes = Vec::with_capacity(total + 1); nodes.push(BuildingNode::default()); let mut edges = Vec::with_capacity(total); let mut path = Vec::new(); path.push(0_u32); let mut previous: &[u32] = &[]; for pattern in &patterns { let common = previous .iter() .zip(pattern) .take_while(|(a, b)| a == b) .count(); path.truncate(common + 1); for &symbol in &pattern[common..] { let parent = path[path.len() - 1]; let child = index(nodes.len()); edges.push((parent, symbol, child)); nodes.push(BuildingNode::default()); path.push(child); } nodes[path[path.len() - 1] as usize].longest = super::length(pattern.len()); previous = pattern; } edges.sort_unstable(); for (index, &(parent, _, _)) in edges.iter().enumerate() { let node = &mut nodes[parent as usize]; if node.edge_count == 0 { node.edge_start = self::index(index); } node.edge_count += 1; } let depth = alphabet.len().next_power_of_two().trailing_zeros() as usize; let mut branches = Vec::with_capacity(1 + edges.len() * (depth + 1)); branches.push(Branch::default()); let mut queue = Vec::with_capacity(nodes.len()); queue.push(0_u32); let mut cursor = 0; while cursor < queue.len() { let index = queue[cursor] as usize; cursor += 1; let failure = nodes[index].failure as usize; let mut transition = nodes[failure].transition; nodes[index].longest = nodes[index].longest.max(nodes[failure].longest); let start = nodes[index].edge_start as usize; let end = start + usize::from(nodes[index].edge_count); for &(_, symbol, child) in &edges[start..end] { let rank = alphabet.partition_point(|candidate| *candidate < symbol); nodes[child as usize].failure = if index == 0 { 0 } else { lookup(&branches, nodes[failure].transition, rank, depth) }; transition = insert(&mut branches, transition, rank, depth, child); queue.push(child); } nodes[index].transition = transition; } Self { alphabet: alphabet.into_boxed_slice(), nodes: nodes .into_iter() .map(|node| Node { transition: node.transition, longest: node.longest, }) .collect(), branches, #[cfg(test)] comparisons: std::cell::Cell::new(0), } } pub(super) fn advance(&self, state: u32, symbol: u32) -> u32 { let rank = self.alphabet.binary_search_by(|candidate| { #[cfg(test)] self.comparisons.set(self.comparisons.get() + 1); candidate.cmp(&symbol) }); let Ok(rank) = rank else { return 0; }; let depth = self.alphabet.len().next_power_of_two().trailing_zeros() as usize; #[cfg(test)] self.comparisons .set(self.comparisons.get() + depth as u64 + 1); lookup( &self.branches, self.nodes[state as usize].transition, rank, depth, ) } pub(super) fn longest(&self, state: u32) -> usize { usize::from(self.nodes[state as usize].longest) } #[cfg(test)] pub(super) fn comparisons(&self) -> u64 { self.comparisons.get() } } fn lookup(branches: &[Branch], mut root: u32, rank: usize, depth: usize) -> u32 { for shift in (0..depth).rev() { let branch = branches[root as usize]; root = if rank & (1 << shift) == 0 { branch.left } else { branch.right }; } branches[root as usize].left } fn insert(branches: &mut Vec, root: u32, rank: usize, depth: usize, value: u32) -> u32 { let mut branch = branches[root as usize]; if depth == 0 { branch.left = value; } else { let slot = if rank & (1 << (depth - 1)) == 0 { &mut branch.left } else { &mut branch.right }; *slot = insert(branches, *slot, rank, depth - 1, value); } branches.push(branch); // Recursion appended descendants before this branch. index(branches.len() - 1) } #[expect( clippy::cast_possible_truncation, reason = "validated dictionary bounds keep every index below u32::MAX" )] pub(super) fn index(value: usize) -> u32 { assert!( u32::try_from(value).is_ok(), "automaton index must fit in u32" ); value as u32 } #[cfg(test)] mod tests { //! SMH-SPEC-SPEC0001: compact request-owned dictionary records. use super::*; #[test] fn dictionary_records_have_exact_sizes() { assert_eq!(std::mem::size_of::(), 8); assert_eq!(std::mem::size_of::(), 8); assert_eq!(std::mem::size_of::(), 16); } }