repositories / smith
smith
There are many coding harnesses - but this one is fast
owned by admin
smith-harness/src/response_sanitizer/automaton.rs
Raw//! 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<Branch>,
#[cfg(test)]
comparisons: std::cell::Cell<u64>,
}
impl Automaton {
pub(super) fn new(mut patterns: Vec<Vec<u32>>) -> 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<Branch>, 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::<Branch>(), 8);
assert_eq!(std::mem::size_of::<Node>(), 8);
assert_eq!(std::mem::size_of::<BuildingNode>(), 16);
}
}