sim_lib_pattern/
text_vm.rs

1//! Legacy text-program compatibility lowering into the shared pattern engine.
2
3use crate::{
4    Anchor, CaptureId, EnginePolicy, ExecutionOutcome, IrNode, PatternIr, RepeatBounds,
5    ScalarDomain, compile, execute::execute_spanning,
6};
7use std::collections::BTreeMap;
8
9/// Character class understood by the shared text-pattern VM.
10#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
11pub enum TextClass {
12    /// ASCII alphabetic characters.
13    Alpha,
14    /// ASCII digits.
15    Digit,
16    /// ASCII lowercase alphabetic characters.
17    Lower,
18    /// ASCII uppercase alphabetic characters.
19    Upper,
20    /// ASCII alphanumeric characters.
21    Alnum,
22    /// ASCII whitespace characters.
23    Space,
24    /// ASCII punctuation characters.
25    Punct,
26    /// ASCII hexadecimal digits.
27    Hex,
28    /// The NUL character.
29    Zero,
30    /// A literal/range set, optionally including nested classes.
31    Set {
32        /// Literal characters accepted by the set.
33        chars: Vec<char>,
34        /// Inclusive character ranges accepted by the set.
35        ranges: Vec<(char, char)>,
36        /// Nested reusable classes accepted by the set.
37        classes: Vec<TextClass>,
38        /// Inverts the accepted membership.
39        negated: bool,
40    },
41    /// Inverts another class.
42    Not(Box<TextClass>),
43}
44
45impl TextClass {
46    /// Returns true when `ch` belongs to this class.
47    pub fn matches(&self, ch: char) -> bool {
48        match self {
49            Self::Alpha => ch.is_ascii_alphabetic(),
50            Self::Digit => ch.is_ascii_digit(),
51            Self::Lower => ch.is_ascii_lowercase(),
52            Self::Upper => ch.is_ascii_uppercase(),
53            Self::Alnum => ch.is_ascii_alphanumeric(),
54            Self::Space => ch.is_ascii_whitespace(),
55            Self::Punct => ch.is_ascii_punctuation(),
56            Self::Hex => ch.is_ascii_hexdigit(),
57            Self::Zero => ch == '\0',
58            Self::Set {
59                chars,
60                ranges,
61                classes,
62                negated,
63            } => {
64                let found = chars.contains(&ch)
65                    || ranges.iter().any(|(start, end)| *start <= ch && ch <= *end)
66                    || classes.iter().any(|class| class.matches(ch));
67                if *negated { !found } else { found }
68            }
69            Self::Not(class) => !class.matches(ch),
70        }
71    }
72}
73
74/// One operation in the shared text-pattern VM.
75#[derive(Clone, Debug, PartialEq, Eq)]
76pub enum TextOp {
77    /// Match one character from a class.
78    Class(TextClass),
79    /// Match one literal character.
80    Literal(char),
81    /// Match any one character.
82    Any,
83    /// Start a capture at the current byte offset.
84    CaptureStart,
85    /// End the most recent open capture at the current byte offset.
86    CaptureEnd,
87    /// Quantify the previous consuming operation.
88    Repeat {
89        /// Minimum number of repetitions.
90        min: usize,
91        /// Maximum number of repetitions, or unbounded when absent.
92        max: Option<usize>,
93        /// Prefer longer repetitions before shorter ones.
94        greedy: bool,
95    },
96    /// Match balanced text beginning with `open` and ending at its paired `close`.
97    Balanced {
98        /// Opening delimiter.
99        open: char,
100        /// Closing delimiter.
101        close: char,
102    },
103    /// Match a frontier before a character in the class.
104    Frontier(TextClass),
105    /// Match the start of the subject.
106    AnchorStart,
107    /// Match the end of the subject.
108    AnchorEnd,
109}
110
111/// A successful text-pattern match.
112#[derive(Clone, Debug, PartialEq, Eq)]
113pub struct TextMatch {
114    /// Start byte offset.
115    pub start: usize,
116    /// End byte offset.
117    pub end: usize,
118    /// Captured byte ranges.
119    pub captures: Vec<(usize, usize)>,
120}
121
122/// Step limits for the bounded VM.
123#[derive(Clone, Copy, Debug, PartialEq, Eq)]
124pub struct TextLimits {
125    /// Maximum total transitions (the legacy text VM treats these as steps).
126    pub max_steps: usize,
127    /// Maximum automaton states admitted by one execution.
128    pub max_states: usize,
129    /// Maximum capture-boundary records retained by one execution.
130    pub max_capture_history: usize,
131    /// Maximum subject symbols inspected by one execution.
132    pub max_subject_symbols: usize,
133}
134
135impl Default for TextLimits {
136    fn default() -> Self {
137        Self {
138            max_steps: 10_000,
139            max_states: 4_096,
140            max_capture_history: 10_000,
141            max_subject_symbols: 1_000_000,
142        }
143    }
144}
145
146#[derive(Clone, Debug)]
147struct CursorText {
148    chars: Vec<char>,
149    offsets: Vec<usize>,
150    len_bytes: usize,
151}
152
153impl CursorText {
154    fn new(subject: &str) -> Self {
155        let mut chars = Vec::new();
156        let mut offsets = Vec::new();
157        for (offset, ch) in subject.char_indices() {
158            offsets.push(offset);
159            chars.push(ch);
160        }
161        Self {
162            chars,
163            offsets,
164            len_bytes: subject.len(),
165        }
166    }
167
168    fn cursor_for_byte(&self, byte: usize) -> Option<usize> {
169        if byte == self.len_bytes {
170            return Some(self.chars.len());
171        }
172        self.offsets.iter().position(|offset| *offset == byte)
173    }
174
175    fn byte_for_cursor(&self, cursor: usize) -> usize {
176        self.offsets.get(cursor).copied().unwrap_or(self.len_bytes)
177    }
178}
179
180#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
181enum TextExtension {
182    Class(TextClass),
183    Balanced { open: char, close: char },
184    Frontier(TextClass),
185}
186
187/// Runs a compiled text pattern over `subject` starting at byte offset `init`.
188///
189/// Unanchored programs search forward from `init`; programs beginning with
190/// [`TextOp::AnchorStart`] only attempt a match at subject start. The matcher
191/// fails closed when `limits.max_steps` is reached.
192pub fn run_text_pattern(
193    ops: &[TextOp],
194    subject: &str,
195    init: usize,
196    limits: TextLimits,
197) -> Option<TextMatch> {
198    let anchored = matches!(ops.first(), Some(TextOp::AnchorStart));
199    let ir = lower_text_program(ops)?;
200    let automaton = compile(&ir);
201    let text = CursorText::new(subject);
202    let init_cursor = text.cursor_for_byte(init)?;
203    let starts: Box<dyn Iterator<Item = usize>> = if anchored {
204        Box::new(std::iter::once(init_cursor).filter(|cursor| *cursor == 0))
205    } else {
206        Box::new(init_cursor..=text.chars.len())
207    };
208
209    for start_cursor in starts {
210        let slice = &text.chars[start_cursor..];
211        let outcome =
212            execute_spanning(
213                &automaton,
214                slice,
215                limits,
216                |extension, _, position| match extension {
217                    TextExtension::Class(class) => slice
218                        .get(position)
219                        .is_some_and(|ch| class.matches(*ch))
220                        .then_some(position + 1),
221                    TextExtension::Balanced { open, close } => {
222                        match_balanced(slice, position, *open, *close)
223                    }
224                    TextExtension::Frontier(class) => {
225                        let absolute = start_cursor + position;
226                        let previous = absolute.checked_sub(1).and_then(|i| text.chars.get(i));
227                        let current = text.chars.get(absolute);
228                        (!previous.is_some_and(|ch| class.matches(*ch))
229                            && current.is_some_and(|ch| class.matches(*ch)))
230                        .then_some(position)
231                    }
232                },
233            );
234        if let ExecutionOutcome::Match { matched, .. } = outcome {
235            let captures = matched
236                .captures
237                .values()
238                .map(|span| {
239                    (
240                        text.byte_for_cursor(start_cursor + span.start),
241                        text.byte_for_cursor(start_cursor + span.end),
242                    )
243                })
244                .collect();
245            return Some(TextMatch {
246                start: text.byte_for_cursor(start_cursor),
247                end: text.byte_for_cursor(start_cursor + matched.end),
248                captures,
249            });
250        }
251    }
252    None
253}
254
255fn lower_text_program(ops: &[TextOp]) -> Option<PatternIr<ScalarDomain, TextExtension>> {
256    let mut frames = vec![Vec::new()];
257    let mut next_capture = 0u32;
258    for op in ops {
259        let nodes = frames.last_mut()?;
260        match op {
261            TextOp::Class(class) => {
262                nodes.push(IrNode::Extension(TextExtension::Class(class.clone())))
263            }
264            TextOp::Literal(ch) => nodes.push(IrNode::Symbol(*ch)),
265            TextOp::Any => nodes.push(IrNode::Any),
266            TextOp::Balanced { open, close } => {
267                nodes.push(IrNode::Extension(TextExtension::Balanced {
268                    open: *open,
269                    close: *close,
270                }))
271            }
272            TextOp::Repeat { min, max, greedy } => {
273                let node = nodes.pop()?;
274                nodes.push(IrNode::Repeat {
275                    node: Box::new(node),
276                    bounds: RepeatBounds::new(*min, *max).ok()?,
277                    greedy: *greedy,
278                });
279            }
280            TextOp::CaptureStart => frames.push(Vec::new()),
281            TextOp::CaptureEnd => {
282                if frames.len() == 1 {
283                    return None;
284                }
285                let body = IrNode::Concat(frames.pop()?);
286                let id = CaptureId(next_capture);
287                next_capture += 1;
288                frames.last_mut()?.push(IrNode::Capture {
289                    id,
290                    node: Box::new(body),
291                });
292            }
293            TextOp::Frontier(class) => {
294                nodes.push(IrNode::Extension(TextExtension::Frontier(class.clone())))
295            }
296            TextOp::AnchorStart => nodes.push(IrNode::Anchor(Anchor::SubjectStart)),
297            TextOp::AnchorEnd => nodes.push(IrNode::Anchor(Anchor::SubjectEnd)),
298        }
299    }
300    if frames.len() != 1 {
301        return None;
302    }
303    let extensions = ops.iter().filter_map(|op| match op {
304        TextOp::Class(class) => Some(TextExtension::Class(class.clone())),
305        TextOp::Balanced { open, close } => Some(TextExtension::Balanced {
306            open: *open,
307            close: *close,
308        }),
309        TextOp::Frontier(class) => Some(TextExtension::Frontier(class.clone())),
310        _ => None,
311    });
312    PatternIr::new(
313        IrNode::Concat(frames.pop()?),
314        BTreeMap::new(),
315        &EnginePolicy::new(extensions),
316    )
317    .ok()
318}
319
320fn match_balanced(text: &[char], cursor: usize, open: char, close: char) -> Option<usize> {
321    if text.get(cursor).copied() != Some(open) {
322        return None;
323    }
324    let mut depth = 0usize;
325    for (index, ch) in text.iter().copied().enumerate().skip(cursor) {
326        if ch == open {
327            depth += 1;
328        }
329        if ch == close {
330            depth = depth.saturating_sub(1);
331            if depth == 0 {
332                return Some(index + 1);
333            }
334        }
335    }
336    None
337}
sim_lib_pattern/text_vm.rs

sim_lib_pattern/
text_vm.rs
