vyre_libs/scan/nfa/
plan.rs

1//! NFA compiled-plan data model and literal-pattern state budgeting.
2
3use super::alloc::reserve_vec;
4
5/// Compiled plan for a pattern set.
6#[derive(Debug, Clone)]
7pub struct NfaPlan {
8    /// Total NFA state count (across every pattern + the shared entry).
9    pub num_states: u32,
10    /// Input buffer length the plan was compiled against.
11    pub input_len: u32,
12    /// One `(pattern_id, pattern_len)` per accept state.
13    pub accept_states: Vec<(u32, u32)>,
14    /// NFA state id for each entry in [`accept_states`](Self::accept_states).
15    pub accept_state_ids: Vec<u32>,
16    /// Per-accept flag requiring the match start offset to be zero.
17    pub accept_start_anchored: Vec<bool>,
18    /// Per-accept flag requiring the match end offset to equal input length.
19    pub accept_end_anchored: Vec<bool>,
20}
21
22impl NfaPlan {
23    /// Attach the expected input length.
24    #[must_use]
25    pub fn for_input_len(mut self, input_len: u32) -> Self {
26        self.input_len = input_len;
27        self
28    }
29}
30
31/// Errors returned by fallible NFA compilation and table construction.
32#[derive(Debug, Clone, Eq, PartialEq)]
33pub enum NfaCompileError {
34    /// Pattern count does not fit the GPU ABI's `u32` pattern id field.
35    PatternCountOverflow {
36        /// Number of patterns supplied by the caller.
37        count: usize,
38    },
39    /// One literal length does not fit the GPU ABI's `u32` length field.
40    PatternLengthOverflow {
41        /// Index of the oversized pattern.
42        pattern_index: usize,
43        /// UTF-8 byte length of the oversized pattern.
44        len: usize,
45    },
46    /// Total NFA state count overflowed the GPU ABI's `u32` state id field.
47    StateCountOverflow,
48    /// Transition or epsilon table word count overflowed host `usize`.
49    TableWordCountOverflow {
50        /// Table being built.
51        table: &'static str,
52    },
53    /// Compiler staging allocation failed.
54    StorageReserveFailed {
55        /// Scratch vector being reserved.
56        field: &'static str,
57        /// Requested target capacity.
58        requested: usize,
59        /// Allocator failure details.
60        message: String,
61    },
62}
63
64impl std::fmt::Display for NfaCompileError {
65    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
66        match self {
67            Self::PatternCountOverflow { count } => write!(
68                f,
69                "NFA pattern count {count} exceeds u32 capacity. Fix: shard the pattern set before NFA compilation."
70            ),
71            Self::PatternLengthOverflow { pattern_index, len } => write!(
72                f,
73                "NFA pattern {pattern_index} length {len} exceeds u32 capacity. Fix: split or reject oversized literals before NFA compilation."
74            ),
75            Self::StateCountOverflow => write!(
76                f,
77                "NFA state count overflows u32. Fix: use plan_shards to split the pattern set before compilation."
78            ),
79            Self::TableWordCountOverflow { table } => write!(
80                f,
81                "NFA {table} table word count overflows host usize. Fix: shard the pattern set before table construction."
82            ),
83            Self::StorageReserveFailed {
84                field,
85                requested,
86                message,
87            } => write!(
88                f,
89                "NFA compilation could not reserve {requested} {field} slot(s): {message}. Fix: shard the pattern set before compilation."
90            ),
91        }
92    }
93}
94
95impl std::error::Error for NfaCompileError {}
96
97/// Compile patterns into an [`NfaPlan`]. Literal-only: each pattern
98/// contributes `len(p)` states; all patterns share state 0 (entry),
99/// so total state count is `1 + sum(len(p))`.
100///
101/// # Panics
102/// Panics when the pattern set exceeds the NFA state cap. An entry-only plan would
103/// build a scanner that matches nothing, so callers that must recover use
104/// [`try_compile`].
105#[must_use]
106pub fn compile(patterns: &[&str]) -> NfaPlan {
107    match try_compile(patterns) {
108        Ok(plan) => plan,
109        Err(error) => {
110            // Returning a 1-state entry-only plan would build a scanner with no
111            // accept states, it silently matches NOTHING, reporting every
112            // input as clean. That is a total recall-loss silent fallback
113            // (Law 10). Fail closed. Callers that must recover use try_compile.
114            panic!(
115                "vyre-libs NFA compile failed: {error}: \
116                 returning an empty entry-only plan would build a scanner that silently matches nothing; \
117                 use try_compile and reduce the pattern set below the state cap."
118            )
119        }
120    }
121}
122
123/// Fallible counterpart of [`compile`].
124///
125/// # Errors
126///
127/// Returns [`NfaCompileError`] when pattern ids, pattern lengths, aggregate
128/// state counts, or compiler scratch allocation cannot be represented safely.
129pub fn try_compile(patterns: &[&str]) -> Result<NfaPlan, NfaCompileError> {
130    let _pattern_count =
131        u32::try_from(patterns.len()).map_err(|_| NfaCompileError::PatternCountOverflow {
132            count: patterns.len(),
133        })?;
134    let mut accept_states = Vec::new();
135    reserve_vec(&mut accept_states, patterns.len(), "accept state")?;
136    let mut accept_state_ids = Vec::new();
137    reserve_vec(&mut accept_state_ids, patterns.len(), "accept state id")?;
138    let mut accept_start_anchored = Vec::new();
139    reserve_vec(
140        &mut accept_start_anchored,
141        patterns.len(),
142        "accept start-anchor flag",
143    )?;
144    accept_start_anchored.resize(patterns.len(), false);
145    let mut accept_end_anchored = Vec::new();
146    reserve_vec(
147        &mut accept_end_anchored,
148        patterns.len(),
149        "accept end-anchor flag",
150    )?;
151    accept_end_anchored.resize(patterns.len(), false);
152    let mut next_state: u32 = 1;
153    for (pid, p) in patterns.iter().enumerate() {
154        let pid = u32::try_from(pid).map_err(|_| NfaCompileError::PatternCountOverflow {
155            count: patterns.len(),
156        })?;
157        let len = u32::try_from(p.len()).map_err(|_| NfaCompileError::PatternLengthOverflow {
158            pattern_index: pid as usize,
159            len: p.len(),
160        })?;
161        let accept_state_id = if len == 0 {
162            0
163        } else {
164            next_state
165                .checked_add(len)
166                .and_then(|value| value.checked_sub(1))
167                .ok_or(NfaCompileError::StateCountOverflow)?
168        };
169        accept_states.push((pid, len));
170        accept_state_ids.push(accept_state_id);
171        next_state = next_state
172            .checked_add(len)
173            .ok_or(NfaCompileError::StateCountOverflow)?;
174    }
175    Ok(NfaPlan {
176        num_states: next_state,
177        input_len: 0,
178        accept_states,
179        accept_state_ids,
180        accept_start_anchored,
181        accept_end_anchored,
182    })
183}
184
185/// The degenerate entry-only plan. Used only by tests to pin the empty-pattern
186/// contract; production `compile` no longer falls back to this on error (it
187/// fails loud, see the panic arm above), so this is `#[cfg(test)]` to keep it
188/// from being mistaken for a usable silent-fallback target.
189#[cfg(test)]
190fn empty_plan() -> NfaPlan {
191    NfaPlan {
192        num_states: 1,
193        input_len: 0,
194        accept_states: Vec::new(),
195        accept_state_ids: Vec::new(),
196        accept_start_anchored: Vec::new(),
197        accept_end_anchored: Vec::new(),
198    }
199}
200
201#[cfg(test)]
202mod tests {
203    use super::{compile, empty_plan, try_compile};
204
205    #[test]
206    fn compile_empty_patterns_returns_real_entry_state() {
207        let plan = compile(&[]);
208
209        assert_eq!(plan.num_states, 1);
210        assert!(plan.accept_states.is_empty());
211        assert!(plan.accept_state_ids.is_empty());
212    }
213
214    #[test]
215    fn empty_plan_matches_try_compile_empty_contract() {
216        let fallible = try_compile(&[]).expect("Fix: empty NFA compile must fit ABI");
217        let fallback = empty_plan();
218
219        assert_eq!(fallback.num_states, fallible.num_states);
220        assert_eq!(fallback.accept_states, fallible.accept_states);
221        assert_eq!(fallback.accept_state_ids, fallible.accept_state_ids);
222    }
223}
vyre_libs/scan/nfa/plan.rs

vyre_libs/scan/nfa/
plan.rs
