sim_lib_pattern/
compile.rs

1//! Stable tagged-Thompson compilation for validated pattern IR.
2
3use crate::{Anchor, AssertionId, CaptureId, IrNode, PatternIr, SymbolDomain, TextClass};
4use core::fmt;
5use std::collections::BTreeMap;
6
7/// Stable identifier of an automaton state.
8#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
9pub struct StateId(pub u32);
10
11/// The action performed by one automaton state.
12#[derive(Clone, Debug, PartialEq, Eq)]
13pub enum Instruction<S, E> {
14    /// Accept the pattern.
15    Accept,
16    /// Continue without consuming input.
17    Epsilon {
18        /// Successor state.
19        next: StateId,
20    },
21    /// Consume one exact symbol.
22    Symbol {
23        /// Required symbol.
24        symbol: S,
25        /// Successor after consumption.
26        next: StateId,
27    },
28    /// Consume any one symbol.
29    Any {
30        /// Successor after consumption.
31        next: StateId,
32    },
33    /// Delegate symbol recognition to an admitted extension.
34    Extension {
35        /// Admitted extension matcher.
36        extension: E,
37        /// Successor after consumption.
38        next: StateId,
39    },
40    /// Choose either successor without consuming input.
41    Split {
42        /// Ordered branch entry states.
43        alternatives: Vec<StateId>,
44    },
45    /// Record a capture boundary without consuming input.
46    Tag {
47        /// Stable capture identifier.
48        capture: CaptureId,
49        /// Boundary being recorded.
50        boundary: TagBoundary,
51        /// Successor state.
52        next: StateId,
53    },
54    /// Test a subject boundary without consuming input.
55    Anchor {
56        /// Boundary predicate.
57        anchor: Anchor,
58        /// Successor when the predicate holds.
59        next: StateId,
60    },
61    /// Invoke a separately compiled zero-width assertion.
62    Assertion {
63        /// Stable assertion identifier.
64        assertion: AssertionId,
65        /// Successor when the assertion holds.
66        next: StateId,
67    },
68    /// Enter a bounded or unbounded repetition loop.
69    Repeat {
70        /// Repeated body entry.
71        body: StateId,
72        /// Loop exit.
73        exit: StateId,
74        /// Required iteration count.
75        min: usize,
76        /// Maximum iteration count, or no bound.
77        max: Option<usize>,
78        /// Whether the body precedes the exit in execution priority.
79        greedy: bool,
80    },
81}
82
83/// A capture-tag boundary.
84#[derive(Clone, Copy, Debug, PartialEq, Eq)]
85pub enum TagBoundary {
86    /// Opening boundary.
87    Start,
88    /// Closing boundary.
89    End,
90}
91
92/// One stable state in a compiled automaton.
93#[derive(Clone, Debug, PartialEq, Eq)]
94pub struct State<S, E> {
95    /// Stable, dense identifier equal to this state's position.
96    pub id: StateId,
97    /// State behavior and outgoing edges.
98    pub instruction: Instruction<S, E>,
99}
100
101/// Browsable facts about a compilation.
102#[derive(Clone, Copy, Debug, PartialEq, Eq)]
103pub struct CompilationEvidence {
104    /// Total number of graph states.
105    pub state_count: usize,
106    /// Number of capture tags in the graph.
107    pub capture_count: usize,
108    /// Conservative work per subject position for an NFA state-set executor.
109    pub estimated_work_per_symbol: usize,
110}
111
112/// A compiled, explicitly branching tagged automaton.
113#[derive(Clone, Debug, PartialEq, Eq)]
114pub struct Automaton<S, E> {
115    start: StateId,
116    states: Vec<State<S, E>>,
117    evidence: CompilationEvidence,
118    assertions: BTreeMap<AssertionId, AssertionProgram<S, E>>,
119}
120
121/// A separately compiled lookahead whose width is known before execution.
122#[derive(Clone, Debug, PartialEq, Eq)]
123pub struct AssertionProgram<S, E> {
124    automaton: Box<Automaton<S, E>>,
125    width: usize,
126}
127
128impl<S, E> AssertionProgram<S, E> {
129    /// Compiled regular program used by the zero-width assertion.
130    pub fn automaton(&self) -> &Automaton<S, E> {
131        &self.automaton
132    }
133
134    /// Exact number of subject symbols inspected by the assertion.
135    pub const fn width(&self) -> usize {
136        self.width
137    }
138}
139
140impl<S, E> Automaton<S, E> {
141    /// Entry state.
142    pub const fn start(&self) -> StateId {
143        self.start
144    }
145    /// Dense state table.
146    pub fn states(&self) -> &[State<S, E>] {
147        &self.states
148    }
149    /// Compilation size and work estimate.
150    pub const fn evidence(&self) -> CompilationEvidence {
151        self.evidence
152    }
153
154    /// Returns a compiled fixed-width assertion when its definition is regular.
155    pub fn assertion(&self, id: AssertionId) -> Option<&AssertionProgram<S, E>> {
156        self.assertions.get(&id)
157    }
158}
159
160/// Compile validated IR into a stable tagged Thompson graph.
161pub fn compile<D, E>(ir: &PatternIr<D, E>) -> Automaton<D::Symbol, E>
162where
163    D: SymbolDomain,
164    D::Symbol: Clone,
165    E: Clone + fmt::Debug + Ord,
166{
167    let mut builder = Builder { states: Vec::new() };
168    let accept = builder.push(Instruction::Accept);
169    let start = builder.node(ir.root(), accept);
170    let capture_count = builder
171        .states
172        .iter()
173        .filter(|state| {
174            matches!(
175                state.instruction,
176                Instruction::Tag {
177                    boundary: TagBoundary::Start,
178                    ..
179                }
180            )
181        })
182        .count();
183    let state_count = builder.states.len();
184    let assertions: BTreeMap<AssertionId, AssertionProgram<D::Symbol, E>> = ir
185        .assertions()
186        .iter()
187        .filter_map(|(id, node)| {
188            fixed_width(node).map(|width| {
189                (
190                    *id,
191                    AssertionProgram {
192                        automaton: Box::new(compile_node(node)),
193                        width,
194                    },
195                )
196            })
197        })
198        .collect();
199    let assertion_state_count = assertions
200        .values()
201        .map(|program| program.automaton.evidence.state_count)
202        .sum::<usize>();
203    Automaton {
204        start,
205        states: builder.states,
206        evidence: CompilationEvidence {
207            state_count: state_count + assertion_state_count,
208            capture_count,
209            estimated_work_per_symbol: state_count + assertion_state_count,
210        },
211        assertions,
212    }
213}
214
215fn compile_node<S: Clone, E: Clone>(node: &IrNode<S, E>) -> Automaton<S, E> {
216    let mut builder = Builder { states: Vec::new() };
217    let accept = builder.push(Instruction::Accept);
218    let start = builder.node(node, accept);
219    let state_count = builder.states.len();
220    Automaton {
221        start,
222        states: builder.states,
223        evidence: CompilationEvidence {
224            state_count,
225            capture_count: 0,
226            estimated_work_per_symbol: state_count,
227        },
228        assertions: BTreeMap::new(),
229    }
230}
231
232fn fixed_width<S, E>(node: &IrNode<S, E>) -> Option<usize> {
233    match node {
234        IrNode::Symbol(_) | IrNode::Any | IrNode::Extension(_) => Some(1),
235        IrNode::Anchor(_) => Some(0),
236        // Nested assertion composition needs its referenced definition to prove
237        // width. Keep it in the typed extension lane until compilation carries
238        // that dependency closure explicitly.
239        IrNode::Assertion(_) => None,
240        IrNode::Concat(nodes) => nodes
241            .iter()
242            .try_fold(0usize, |sum, node| sum.checked_add(fixed_width(node)?)),
243        IrNode::Alternation(nodes) => {
244            let mut widths = nodes.iter().map(fixed_width);
245            let first = widths.next()??;
246            widths.all(|width| width == Some(first)).then_some(first)
247        }
248        IrNode::Repeat { node, bounds, .. } if bounds.max() == Some(bounds.min()) => {
249            fixed_width(node)?.checked_mul(bounds.min())
250        }
251        IrNode::Group(node) | IrNode::Capture { node, .. } => fixed_width(node),
252        IrNode::Repeat { .. } => None,
253    }
254}
255
256struct Builder<S, E> {
257    states: Vec<State<S, E>>,
258}
259
260impl<S: Clone, E: Clone> Builder<S, E> {
261    fn push(&mut self, instruction: Instruction<S, E>) -> StateId {
262        let id =
263            StateId(u32::try_from(self.states.len()).expect("pattern state count exceeds u32"));
264        self.states.push(State { id, instruction });
265        id
266    }
267
268    fn node(&mut self, node: &IrNode<S, E>, next: StateId) -> StateId {
269        match node {
270            IrNode::Symbol(symbol) => self.push(Instruction::Symbol {
271                symbol: symbol.clone(),
272                next,
273            }),
274            IrNode::Any => self.push(Instruction::Any { next }),
275            IrNode::Concat(nodes) => nodes
276                .iter()
277                .rev()
278                .fold(next, |tail, node| self.node(node, tail)),
279            IrNode::Alternation(nodes) => {
280                let alternatives = nodes.iter().map(|node| self.node(node, next)).collect();
281                self.push(Instruction::Split { alternatives })
282            }
283            IrNode::Repeat {
284                node,
285                bounds,
286                greedy,
287            } => {
288                let repeat = self.push(Instruction::Epsilon { next });
289                let body = self.node(node, repeat);
290                self.states[repeat.0 as usize].instruction = Instruction::Repeat {
291                    body,
292                    exit: next,
293                    min: bounds.min(),
294                    max: bounds.max(),
295                    greedy: *greedy,
296                };
297                repeat
298            }
299            IrNode::Group(node) => self.node(node, next),
300            IrNode::Capture { id, node } => {
301                let end = self.push(Instruction::Tag {
302                    capture: *id,
303                    boundary: TagBoundary::End,
304                    next,
305                });
306                let body = self.node(node, end);
307                self.push(Instruction::Tag {
308                    capture: *id,
309                    boundary: TagBoundary::Start,
310                    next: body,
311                })
312            }
313            IrNode::Anchor(anchor) => self.push(Instruction::Anchor {
314                anchor: *anchor,
315                next,
316            }),
317            IrNode::Assertion(assertion) => self.push(Instruction::Assertion {
318                assertion: *assertion,
319                next,
320            }),
321            IrNode::Extension(extension) => self.push(Instruction::Extension {
322                extension: extension.clone(),
323                next,
324            }),
325        }
326    }
327}
328
329impl Instruction<char, TextClass> {
330    /// Tests whether this instruction consumes `symbol`, reusing `TextClass` membership.
331    pub fn matches(&self, symbol: char) -> bool {
332        match self {
333            Self::Symbol {
334                symbol: expected, ..
335            } => *expected == symbol,
336            Self::Any { .. } => true,
337            Self::Extension { extension, .. } => extension.matches(symbol),
338            _ => false,
339        }
340    }
341}
342
343#[cfg(test)]
344mod tests {
345    use super::*;
346    use crate::{ByteDomain, EnginePolicy, RepeatBounds, ScalarDomain};
347    use std::collections::BTreeMap;
348
349    fn byte_ir(root: IrNode<u8, &'static str>) -> PatternIr<ByteDomain, &'static str> {
350        PatternIr::new(root, BTreeMap::new(), &EnginePolicy::new([])).unwrap()
351    }
352
353    #[test]
354    fn state_growth_is_linear_across_regular_constructs() {
355        let patterns = [
356            IrNode::Symbol(b'a'),
357            IrNode::Concat(vec![
358                IrNode::Symbol(b'a'),
359                IrNode::Any,
360                IrNode::Anchor(Anchor::SubjectEnd),
361            ]),
362            IrNode::Alternation(vec![IrNode::Symbol(b'a'), IrNode::Symbol(b'b')]),
363            IrNode::Alternation(vec![
364                IrNode::Alternation(vec![IrNode::Symbol(b'a'), IrNode::Symbol(b'b')]),
365                IrNode::Alternation(vec![IrNode::Symbol(b'c'), IrNode::Symbol(b'd')]),
366            ]),
367            IrNode::Repeat {
368                node: Box::new(IrNode::Group(Box::new(IrNode::Symbol(b'x')))),
369                bounds: RepeatBounds::new(3, None).unwrap(),
370                greedy: true,
371            },
372        ];
373        for root in patterns {
374            let automaton = compile(&byte_ir(root.clone()));
375            assert!(automaton.evidence().state_count <= 2 * node_count(&root) + 1);
376            assert_eq!(
377                automaton.evidence().estimated_work_per_symbol,
378                automaton.states().len()
379            );
380        }
381    }
382
383    #[test]
384    fn capture_and_state_ids_survive_recompilation() {
385        let ir = byte_ir(IrNode::Capture {
386            id: CaptureId(41),
387            node: Box::new(IrNode::Alternation(vec![
388                IrNode::Symbol(b'a'),
389                IrNode::Symbol(b'b'),
390            ])),
391        });
392        let first = compile(&ir);
393        assert_eq!(first, compile(&ir));
394        assert!(first.states().iter().any(|state| matches!(
395            state.instruction,
396            Instruction::Tag {
397                capture: CaptureId(41),
398                boundary: TagBoundary::Start,
399                ..
400            }
401        )));
402        assert!(
403            first
404                .states()
405                .iter()
406                .enumerate()
407                .all(|(index, state)| state.id.0 as usize == index)
408        );
409    }
410
411    #[test]
412    fn text_classes_reuse_shared_membership() {
413        let ir = PatternIr::<ScalarDomain, TextClass>::new(
414            IrNode::Extension(TextClass::Digit),
415            BTreeMap::new(),
416            &EnginePolicy::new([TextClass::Digit]),
417        )
418        .unwrap();
419        let automaton = compile(&ir);
420        let instruction = &automaton.states()[automaton.start().0 as usize].instruction;
421        assert!(instruction.matches('7'));
422        assert!(!instruction.matches('x'));
423    }
424
425    fn node_count<S, E>(node: &IrNode<S, E>) -> usize {
426        1 + match node {
427            IrNode::Concat(nodes) | IrNode::Alternation(nodes) => {
428                nodes.iter().map(node_count).sum()
429            }
430            IrNode::Repeat { node, .. } | IrNode::Group(node) | IrNode::Capture { node, .. } => {
431                node_count(node)
432            }
433            _ => 0,
434        }
435    }
436}
sim_lib_pattern/compile.rs

sim_lib_pattern/
compile.rs
