rexact_core/

dfa.rs

//! Derivative automaton, matching, minimisation and canonical form
//! (FR-B03..B05).
//!
//! Contract: [`Dfa`] explores derivatives of a start term lazily and caches
//! every transition, so matching costs O(input length) after the states it
//! needs exist (FR-B05). [`Dfa::minimize`] returns the unique minimal complete
//! automaton over the coarsest symbol-class partition, numbered canonically,
//! so two terms have equal [`MinDfa::canonical_form`] exactly when their
//! languages are equal (FR-B04).
//!
//! Invariants: state 0 is the start; the automaton is complete (the dead state
//! is the `Empty` term); classes partition the universe and are ordered by
//! smallest member. Failure modes: every state creation is charged to the
//! [`Budget`]; a breach returns its [`ErrorCode`] and leaves the automaton
//! consistent.

use crate::charset::CharSet;
use crate::limits::Budget;
use crate::sha256::sha256_hex;
use crate::term::{TermId, TermStore, NO_CTX};
use rexact_syntax::error::ErrorCode;
use std::collections::HashMap;

const UNSET: u32 = u32::MAX;
/// Rough bytes charged per interned term, for the memory limit.
const TERM_BYTES: u64 = 96;

/// Lazily built deterministic automaton over symbol classes.
pub struct Dfa {
    classes: Vec<CharSet>,
    /// (lo, hi, class) sorted by `lo`, for symbol-to-class lookup.
    lookup: Vec<(u32, u32, u32)>,
    states: Vec<TermId>,
    /// Context of each state (matters only for context-dependent terms).
    ctxs: Vec<u32>,
    index: HashMap<(TermId, u32), u32>,
    trans: Vec<u32>,
    accepting: Vec<bool>,
    seen_terms: usize,
    alphabet: &'static str,
}

impl Dfa {
    /// Start an automaton at `start`. The symbol classes are those of `start`.
    pub fn new(
        store: &mut TermStore,
        start: TermId,
        alphabet: &'static str,
        budget: &mut Budget,
    ) -> Result<Dfa, ErrorCode> {
        let classes = (*store.partition(start)).clone();
        let mut lookup: Vec<(u32, u32, u32)> = Vec::new();
        for (i, c) in classes.iter().enumerate() {
            for &(lo, hi) in c.ranges() {
                lookup.push((lo, hi, i as u32));
            }
        }
        lookup.sort_unstable();
        let mut d = Dfa {
            classes,
            lookup,
            states: Vec::new(),
            ctxs: Vec::new(),
            index: HashMap::new(),
            trans: Vec::new(),
            accepting: Vec::new(),
            seen_terms: store.len(),
            alphabet,
        };
        let ctx = if store.ctx_dep(start) {
            store.ctx_start()
        } else {
            NO_CTX
        };
        d.intern_state(store, start, ctx, budget)?;
        Ok(d)
    }

    /// Number of states created so far.
    pub fn num_states(&self) -> usize {
        self.states.len()
    }
    /// Number of symbol classes.
    pub fn num_classes(&self) -> usize {
        self.classes.len()
    }

    fn intern_state(
        &mut self,
        store: &TermStore,
        t: TermId,
        ctx: u32,
        budget: &mut Budget,
    ) -> Result<u32, ErrorCode> {
        // Only context-dependent terms care what came before.
        let ctx = if store.ctx_dep(t) { ctx } else { NO_CTX };
        if let Some(&s) = self.index.get(&(t, ctx)) {
            return Ok(s);
        }
        budget.add_states(1)?;
        budget.add_memory(4 * self.classes.len() as u64 + TERM_BYTES)?;
        budget.check_time()?;
        let id = self.states.len() as u32;
        self.states.push(t);
        self.ctxs.push(ctx);
        self.index.insert((t, ctx), id);
        self.trans
            .extend(std::iter::repeat(UNSET).take(self.classes.len()));
        self.accepting.push(store.accepting(t, ctx));
        Ok(id)
    }

    /// Class index of a symbol, or `None` when outside the universe.
    pub fn class_of(&self, c: u32) -> Option<usize> {
        let i = self.lookup.partition_point(|&(lo, _, _)| lo <= c);
        let &(_, hi, k) = self.lookup.get(i.checked_sub(1)?)?;
        (c <= hi).then_some(k as usize)
    }

    /// Transition from `s` on `class`, computed once and cached.
    pub fn step(
        &mut self,
        store: &mut TermStore,
        s: u32,
        class: usize,
        budget: &mut Budget,
    ) -> Result<u32, ErrorCode> {
        let slot = s as usize * self.classes.len() + class;
        if self.trans[slot] != UNSET {
            return Ok(self.trans[slot]);
        }
        let rep = self.classes[class].smallest().unwrap_or(0);
        let (term, ctx) = (self.states[s as usize], self.ctxs[s as usize]);
        let d = store.deriv_in(term, rep, ctx);
        let next_ctx = if store.ctx_dep(d) {
            store.advance_ctx(ctx, rep)
        } else {
            NO_CTX
        };
        let grown = store.len().saturating_sub(self.seen_terms) as u64;
        self.seen_terms = store.len();
        budget.add_memory(grown * TERM_BYTES)?;
        let t = self.intern_state(store, d, next_ctx, budget)?;
        self.trans[slot] = t;
        Ok(t)
    }

    /// Full-match test: does the whole input belong to the language?
    pub fn matches(
        &mut self,
        store: &mut TermStore,
        input: &[u32],
        budget: &mut Budget,
    ) -> Result<bool, ErrorCode> {
        let mut s = 0u32;
        for &c in input {
            let Some(k) = self.class_of(c) else {
                return Ok(false);
            };
            s = self.step(store, s, k, budget)?;
            if self.states[s as usize] == store.empty() {
                return Ok(false);
            }
        }
        Ok(self.accepting[s as usize])
    }

    /// Build every reachable state and transition.
    pub fn explore(&mut self, store: &mut TermStore, budget: &mut Budget) -> Result<(), ErrorCode> {
        let mut i = 0;
        while i < self.states.len() {
            for c in 0..self.classes.len() {
                self.step(store, i as u32, c, budget)?;
            }
            i += 1;
        }
        Ok(())
    }

    /// Minimal complete automaton in canonical numbering.
    pub fn minimize(
        &mut self,
        store: &mut TermStore,
        budget: &mut Budget,
    ) -> Result<MinDfa, ErrorCode> {
        self.explore(store, budget)?;
        let (n, k) = (self.states.len(), self.classes.len());

        // Hopcroft partition refinement: O(n k log n), so long chains such as
        // a{0,9999} (n = 10,000) stay fast where Moore refinement is quadratic.
        let (block, count) = hopcroft(n, k, &self.trans, &self.accepting, budget)?;

        // Quotient automaton: one row per block.
        let mut rep = vec![usize::MAX; count];
        for (i, &b) in block.iter().enumerate() {
            if rep[b as usize] == usize::MAX {
                rep[b as usize] = i;
            }
        }
        let q = |b: usize, c: usize| block[self.trans[rep[b] * k + c] as usize];

        // Merge symbol classes with identical columns (coarsest partition).
        let mut groups: Vec<Vec<usize>> = Vec::new();
        let mut by_col: HashMap<Vec<u32>, usize> = HashMap::new();
        for c in 0..k {
            let col: Vec<u32> = (0..count).map(|b| q(b, c)).collect();
            let g = *by_col.entry(col).or_insert_with(|| {
                groups.push(Vec::new());
                groups.len() - 1
            });
            groups[g].push(c);
        }
        let merged: Vec<CharSet> = groups
            .iter()
            .map(|g| {
                g.iter()
                    .fold(CharSet::empty(), |acc, &c| acc.union(&self.classes[c]))
            })
            .collect();
        let k2 = groups.len();

        // Canonical numbering: breadth-first from the start, merged classes in order.
        let start = block[0] as usize;
        let mut canon = vec![u32::MAX; count];
        let mut order = vec![start];
        canon[start] = 0;
        let mut i = 0;
        while i < order.len() {
            for g in &groups {
                let t = q(order[i], g[0]) as usize;
                if canon[t] == u32::MAX {
                    canon[t] = order.len() as u32;
                    order.push(t);
                }
            }
            i += 1;
        }
        let mut trans = Vec::with_capacity(order.len() * k2);
        let mut accepting = Vec::with_capacity(order.len());
        for &b in &order {
            for g in &groups {
                trans.push(canon[q(b, g[0]) as usize]);
            }
            accepting.push(self.accepting[rep[b]]);
        }
        Ok(MinDfa {
            alphabet: self.alphabet,
            classes: merged,
            trans,
            accepting,
        })
    }
}

/// Minimal complete automaton with canonical numbering.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MinDfa {
    alphabet: &'static str,
    classes: Vec<CharSet>,
    trans: Vec<u32>,
    accepting: Vec<bool>,
}

impl MinDfa {
    /// Number of states.
    pub fn num_states(&self) -> usize {
        self.accepting.len()
    }
    /// Number of symbol classes after merging indistinguishable ones.
    pub fn num_classes(&self) -> usize {
        self.classes.len()
    }
    /// Symbol classes, ordered by smallest member.
    pub fn classes(&self) -> &[CharSet] {
        &self.classes
    }
    /// Is state `s` accepting?
    pub fn is_accepting(&self, s: usize) -> bool {
        self.accepting[s]
    }
    /// Transition table lookup.
    pub fn next(&self, s: usize, class: usize) -> usize {
        self.trans[s * self.classes.len() + class] as usize
    }

    /// Full-match test on the minimal automaton.
    pub fn accepts(&self, input: &[u32]) -> bool {
        let mut s = 0usize;
        for &c in input {
            match self.classes.iter().position(|k| k.contains(c)) {
                Some(k) => s = self.next(s, k),
                None => return false,
            }
        }
        self.accepting[s]
    }

    /// Exact textual form; equal strings iff equal languages (same alphabet).
    pub fn canonical_form(&self) -> String {
        let mut out = format!(
            "rexact-dfa v1\nalphabet {}\nclasses {}\n",
            self.alphabet,
            self.classes.len()
        );
        for c in &self.classes {
            let parts: Vec<String> = c
                .ranges()
                .iter()
                .map(|&(l, h)| format!("{l:X}-{h:X}"))
                .collect();
            out.push_str(&parts.join(","));
            out.push('\n');
        }
        out.push_str(&format!("states {}\n", self.accepting.len()));
        out.push_str(
            &self
                .accepting
                .iter()
                .map(|&a| if a { '1' } else { '0' })
                .collect::<String>(),
        );
        out.push('\n');
        let k = self.classes.len();
        for s in 0..self.accepting.len() {
            let row: Vec<String> = (0..k).map(|c| self.trans[s * k + c].to_string()).collect();
            out.push_str(&row.join(" "));
            out.push('\n');
        }
        out
    }

    /// SHA-256 of the canonical form: the language fingerprint (FR-B04). The
    /// canonical form is the authority; the hash is its compact name.
    pub fn fingerprint(&self) -> String {
        sha256_hex(self.canonical_form().as_bytes())
    }
}

/// Hopcroft's partition refinement. Returns the block of every state and the
/// number of blocks (ids are dense, `0..count`).
fn hopcroft(
    n: usize,
    k: usize,
    trans: &[u32],
    accepting: &[bool],
    budget: &mut Budget,
) -> Result<(Vec<u32>, usize), ErrorCode> {
    // Inverse transitions per class in CSR form: predecessors of t on class c
    // are list[c*n + start[c*(n+1)+t] .. start[c*(n+1)+t+1]].
    let mut start = vec![0u32; k * (n + 1)];
    let mut list = vec![0u32; k * n];
    for c in 0..k {
        let base = c * (n + 1);
        for s in 0..n {
            start[base + trans[s * k + c] as usize + 1] += 1;
        }
        for t in 0..n {
            start[base + t + 1] += start[base + t];
        }
        let mut fill: Vec<u32> = start[base..base + n].to_vec();
        for s in 0..n {
            let t = trans[s * k + c] as usize;
            list[c * n + fill[t] as usize] = s as u32;
            fill[t] += 1;
        }
    }

    let mut block_of = vec![0u32; n];
    let mut members: Vec<Vec<u32>> = Vec::new();
    let (mut fin, mut non) = (Vec::new(), Vec::new());
    for (s, &is_final) in accepting.iter().enumerate() {
        if is_final {
            fin.push(s as u32);
        } else {
            non.push(s as u32);
        }
    }
    for g in [non, fin] {
        if !g.is_empty() {
            let id = members.len() as u32;
            for &s in &g {
                block_of[s as usize] = id;
            }
            members.push(g);
        }
    }
    let mut in_work = vec![false; members.len()];
    let mut inx: Vec<Vec<u32>> = vec![Vec::new(); members.len()];
    let mut work: Vec<u32> = Vec::new();
    if members.len() == 2 {
        let small = if members[0].len() <= members[1].len() {
            0
        } else {
            1
        };
        work.push(small);
        in_work[small as usize] = true;
    }

    let mut mark = vec![0u32; n];
    let mut stamp = 0u32;
    let mut touched: Vec<u32> = Vec::new();
    while let Some(a) = work.pop() {
        in_work[a as usize] = false;
        budget.check_time()?;
        let splitter = members[a as usize].clone();
        for c in 0..k {
            stamp += 1;
            touched.clear();
            let base = c * (n + 1);
            for &t in &splitter {
                let lo = start[base + t as usize] as usize;
                let hi = start[base + t as usize + 1] as usize;
                for &s in &list[c * n + lo..c * n + hi] {
                    if mark[s as usize] != stamp {
                        mark[s as usize] = stamp;
                        let b = block_of[s as usize];
                        if inx[b as usize].is_empty() {
                            touched.push(b);
                        }
                        inx[b as usize].push(s);
                    }
                }
            }
            for &b in &touched {
                let moved = std::mem::take(&mut inx[b as usize]);
                if moved.len() == members[b as usize].len() {
                    continue; // the whole block is inside X: no split
                }
                let nb = members.len() as u32;
                members[b as usize].retain(|&s| mark[s as usize] != stamp);
                for &s in &moved {
                    block_of[s as usize] = nb;
                }
                members.push(moved);
                in_work.push(false);
                inx.push(Vec::new());
                if in_work[b as usize] {
                    in_work[nb as usize] = true;
                    work.push(nb);
                } else {
                    let small = if members[b as usize].len() <= members[nb as usize].len() {
                        b
                    } else {
                        nb
                    };
                    in_work[small as usize] = true;
                    work.push(small);
                }
            }
        }
    }
    Ok((block_of, members.len()))
}