Luigit
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);
    }
}