sim_lib_pattern/
text_vm.rs

1//! Bounded text-pattern virtual machine shared by pattern dialects.
2
3/// Character class understood by the shared text-pattern VM.
4#[derive(Clone, Debug, PartialEq, Eq)]
5pub enum TextClass {
6    /// ASCII alphabetic characters.
7    Alpha,
8    /// ASCII digits.
9    Digit,
10    /// ASCII lowercase alphabetic characters.
11    Lower,
12    /// ASCII uppercase alphabetic characters.
13    Upper,
14    /// ASCII alphanumeric characters.
15    Alnum,
16    /// ASCII whitespace characters.
17    Space,
18    /// ASCII punctuation characters.
19    Punct,
20    /// ASCII hexadecimal digits.
21    Hex,
22    /// The NUL character.
23    Zero,
24    /// A literal/range set, optionally including nested classes.
25    Set {
26        /// Literal characters accepted by the set.
27        chars: Vec<char>,
28        /// Inclusive character ranges accepted by the set.
29        ranges: Vec<(char, char)>,
30        /// Nested reusable classes accepted by the set.
31        classes: Vec<TextClass>,
32        /// Inverts the accepted membership.
33        negated: bool,
34    },
35    /// Inverts another class.
36    Not(Box<TextClass>),
37}
38
39impl TextClass {
40    /// Returns true when `ch` belongs to this class.
41    pub fn matches(&self, ch: char) -> bool {
42        match self {
43            Self::Alpha => ch.is_ascii_alphabetic(),
44            Self::Digit => ch.is_ascii_digit(),
45            Self::Lower => ch.is_ascii_lowercase(),
46            Self::Upper => ch.is_ascii_uppercase(),
47            Self::Alnum => ch.is_ascii_alphanumeric(),
48            Self::Space => ch.is_ascii_whitespace(),
49            Self::Punct => ch.is_ascii_punctuation(),
50            Self::Hex => ch.is_ascii_hexdigit(),
51            Self::Zero => ch == '\0',
52            Self::Set {
53                chars,
54                ranges,
55                classes,
56                negated,
57            } => {
58                let found = chars.contains(&ch)
59                    || ranges.iter().any(|(start, end)| *start <= ch && ch <= *end)
60                    || classes.iter().any(|class| class.matches(ch));
61                if *negated { !found } else { found }
62            }
63            Self::Not(class) => !class.matches(ch),
64        }
65    }
66}
67
68/// One operation in the shared text-pattern VM.
69#[derive(Clone, Debug, PartialEq, Eq)]
70pub enum TextOp {
71    /// Match one character from a class.
72    Class(TextClass),
73    /// Match one literal character.
74    Literal(char),
75    /// Match any one character.
76    Any,
77    /// Start a capture at the current byte offset.
78    CaptureStart,
79    /// End the most recent open capture at the current byte offset.
80    CaptureEnd,
81    /// Quantify the previous consuming operation.
82    Repeat {
83        /// Minimum number of repetitions.
84        min: usize,
85        /// Maximum number of repetitions, or unbounded when absent.
86        max: Option<usize>,
87        /// Prefer longer repetitions before shorter ones.
88        greedy: bool,
89    },
90    /// Match balanced text beginning with `open` and ending at its paired `close`.
91    Balanced {
92        /// Opening delimiter.
93        open: char,
94        /// Closing delimiter.
95        close: char,
96    },
97    /// Match a frontier before a character in the class.
98    Frontier(TextClass),
99    /// Match the start of the subject.
100    AnchorStart,
101    /// Match the end of the subject.
102    AnchorEnd,
103}
104
105/// A successful text-pattern match.
106#[derive(Clone, Debug, PartialEq, Eq)]
107pub struct TextMatch {
108    /// Start byte offset.
109    pub start: usize,
110    /// End byte offset.
111    pub end: usize,
112    /// Captured byte ranges.
113    pub captures: Vec<(usize, usize)>,
114}
115
116/// Step limits for the bounded VM.
117#[derive(Clone, Copy, Debug, PartialEq, Eq)]
118pub struct TextLimits {
119    /// Maximum recursive VM steps before the match fails closed.
120    pub max_steps: usize,
121}
122
123impl Default for TextLimits {
124    fn default() -> Self {
125        Self { max_steps: 10_000 }
126    }
127}
128
129#[derive(Clone, Debug)]
130struct CursorText {
131    chars: Vec<char>,
132    offsets: Vec<usize>,
133    len_bytes: usize,
134}
135
136impl CursorText {
137    fn new(subject: &str) -> Self {
138        let mut chars = Vec::new();
139        let mut offsets = Vec::new();
140        for (offset, ch) in subject.char_indices() {
141            offsets.push(offset);
142            chars.push(ch);
143        }
144        Self {
145            chars,
146            offsets,
147            len_bytes: subject.len(),
148        }
149    }
150
151    fn cursor_for_byte(&self, byte: usize) -> Option<usize> {
152        if byte == self.len_bytes {
153            return Some(self.chars.len());
154        }
155        self.offsets.iter().position(|offset| *offset == byte)
156    }
157
158    fn byte_for_cursor(&self, cursor: usize) -> usize {
159        self.offsets.get(cursor).copied().unwrap_or(self.len_bytes)
160    }
161}
162
163#[derive(Clone, Debug, PartialEq, Eq)]
164enum Atom {
165    Class(TextClass),
166    Literal(char),
167    Any,
168    Balanced { open: char, close: char },
169}
170
171#[derive(Clone, Copy, Debug, PartialEq, Eq)]
172struct Quantifier {
173    min: usize,
174    max: Option<usize>,
175    greedy: bool,
176}
177
178impl Default for Quantifier {
179    fn default() -> Self {
180        Self {
181            min: 1,
182            max: Some(1),
183            greedy: true,
184        }
185    }
186}
187
188#[derive(Clone, Debug, PartialEq, Eq)]
189enum Unit {
190    Atom(Atom, Quantifier),
191    CaptureStart,
192    CaptureEnd,
193    Frontier(TextClass),
194    AnchorStart,
195    AnchorEnd,
196}
197
198/// Runs a compiled text pattern over `subject` starting at byte offset `init`.
199///
200/// Unanchored programs search forward from `init`; programs beginning with
201/// [`TextOp::AnchorStart`] only attempt a match at subject start. The matcher
202/// fails closed when `limits.max_steps` is reached.
203pub fn run_text_pattern(
204    ops: &[TextOp],
205    subject: &str,
206    init: usize,
207    limits: TextLimits,
208) -> Option<TextMatch> {
209    let units = compile_units(ops)?;
210    let text = CursorText::new(subject);
211    let init_cursor = text.cursor_for_byte(init)?;
212    let anchored = matches!(units.first(), Some(Unit::AnchorStart));
213    let starts: Box<dyn Iterator<Item = usize>> = if anchored {
214        Box::new(std::iter::once(init_cursor).filter(|cursor| *cursor == 0))
215    } else {
216        Box::new(init_cursor..=text.chars.len())
217    };
218
219    for start_cursor in starts {
220        let mut engine = MatchEngine::new(&units, &text, limits.max_steps);
221        if let Some((end_cursor, captures)) =
222            engine.match_from(0, start_cursor, Vec::new(), Vec::new())
223        {
224            return Some(TextMatch {
225                start: text.byte_for_cursor(start_cursor),
226                end: text.byte_for_cursor(end_cursor),
227                captures,
228            });
229        }
230    }
231    None
232}
233
234fn compile_units(ops: &[TextOp]) -> Option<Vec<Unit>> {
235    let mut units = Vec::new();
236    for op in ops {
237        match op {
238            TextOp::Class(class) => units.push(Unit::Atom(
239                Atom::Class(class.clone()),
240                Quantifier::default(),
241            )),
242            TextOp::Literal(ch) => {
243                units.push(Unit::Atom(Atom::Literal(*ch), Quantifier::default()))
244            }
245            TextOp::Any => units.push(Unit::Atom(Atom::Any, Quantifier::default())),
246            TextOp::Balanced { open, close } => units.push(Unit::Atom(
247                Atom::Balanced {
248                    open: *open,
249                    close: *close,
250                },
251                Quantifier::default(),
252            )),
253            TextOp::Repeat { min, max, greedy } => {
254                let Some(Unit::Atom(_, quantifier)) = units.last_mut() else {
255                    return None;
256                };
257                *quantifier = Quantifier {
258                    min: *min,
259                    max: *max,
260                    greedy: *greedy,
261                };
262            }
263            TextOp::CaptureStart => units.push(Unit::CaptureStart),
264            TextOp::CaptureEnd => units.push(Unit::CaptureEnd),
265            TextOp::Frontier(class) => units.push(Unit::Frontier(class.clone())),
266            TextOp::AnchorStart => units.push(Unit::AnchorStart),
267            TextOp::AnchorEnd => units.push(Unit::AnchorEnd),
268        }
269    }
270    Some(units)
271}
272
273struct MatchEngine<'a> {
274    units: &'a [Unit],
275    text: &'a CursorText,
276    limit: usize,
277    steps: usize,
278}
279
280impl<'a> MatchEngine<'a> {
281    fn new(units: &'a [Unit], text: &'a CursorText, limit: usize) -> Self {
282        Self {
283            units,
284            text,
285            limit,
286            steps: 0,
287        }
288    }
289
290    fn match_from(
291        &mut self,
292        unit_index: usize,
293        cursor: usize,
294        captures: Vec<(usize, usize)>,
295        open_captures: Vec<usize>,
296    ) -> Option<(usize, Vec<(usize, usize)>)> {
297        self.steps += 1;
298        if self.steps > self.limit {
299            return None;
300        }
301        let Some(unit) = self.units.get(unit_index) else {
302            return if open_captures.is_empty() {
303                Some((cursor, captures))
304            } else {
305                None
306            };
307        };
308        match unit {
309            Unit::Atom(atom, quantifier) => {
310                let positions = repeated_positions(atom, *quantifier, self.text, cursor);
311                for next_cursor in positions {
312                    if let Some(result) = self.match_from(
313                        unit_index + 1,
314                        next_cursor,
315                        captures.clone(),
316                        open_captures.clone(),
317                    ) {
318                        return Some(result);
319                    }
320                }
321                None
322            }
323            Unit::CaptureStart => {
324                let mut open = open_captures;
325                open.push(self.text.byte_for_cursor(cursor));
326                self.match_from(unit_index + 1, cursor, captures, open)
327            }
328            Unit::CaptureEnd => {
329                let mut open = open_captures;
330                let start = open.pop()?;
331                let mut captures = captures;
332                captures.push((start, self.text.byte_for_cursor(cursor)));
333                self.match_from(unit_index + 1, cursor, captures, open)
334            }
335            Unit::Frontier(class) => {
336                let previous = cursor
337                    .checked_sub(1)
338                    .and_then(|index| self.text.chars.get(index));
339                let current = self.text.chars.get(cursor);
340                let previous_matches = previous.is_some_and(|ch| class.matches(*ch));
341                let current_matches = current.is_some_and(|ch| class.matches(*ch));
342                if !previous_matches && current_matches {
343                    self.match_from(unit_index + 1, cursor, captures, open_captures)
344                } else {
345                    None
346                }
347            }
348            Unit::AnchorStart => {
349                if cursor == 0 {
350                    self.match_from(unit_index + 1, cursor, captures, open_captures)
351                } else {
352                    None
353                }
354            }
355            Unit::AnchorEnd => {
356                if cursor == self.text.chars.len() {
357                    self.match_from(unit_index + 1, cursor, captures, open_captures)
358                } else {
359                    None
360                }
361            }
362        }
363    }
364}
365
366fn repeated_positions(
367    atom: &Atom,
368    quantifier: Quantifier,
369    text: &CursorText,
370    cursor: usize,
371) -> Vec<usize> {
372    let mut positions = vec![cursor];
373    let max = quantifier
374        .max
375        .unwrap_or_else(|| text.chars.len().saturating_sub(cursor));
376    let mut current = cursor;
377    for _ in 0..max {
378        let Some(next) = match_atom(atom, text, current) else {
379            break;
380        };
381        if next == current {
382            break;
383        }
384        positions.push(next);
385        current = next;
386    }
387    let mut selected = positions
388        .into_iter()
389        .enumerate()
390        .filter_map(|(count, position)| (count >= quantifier.min).then_some(position))
391        .collect::<Vec<_>>();
392    if quantifier.greedy {
393        selected.reverse();
394    }
395    selected
396}
397
398fn match_atom(atom: &Atom, text: &CursorText, cursor: usize) -> Option<usize> {
399    match atom {
400        Atom::Class(class) => text
401            .chars
402            .get(cursor)
403            .is_some_and(|ch| class.matches(*ch))
404            .then_some(cursor + 1),
405        Atom::Literal(expected) => text
406            .chars
407            .get(cursor)
408            .is_some_and(|ch| ch == expected)
409            .then_some(cursor + 1),
410        Atom::Any => (cursor < text.chars.len()).then_some(cursor + 1),
411        Atom::Balanced { open, close } => match_balanced(text, cursor, *open, *close),
412    }
413}
414
415fn match_balanced(text: &CursorText, cursor: usize, open: char, close: char) -> Option<usize> {
416    if text.chars.get(cursor).copied() != Some(open) {
417        return None;
418    }
419    let mut depth = 0usize;
420    for index in cursor..text.chars.len() {
421        let ch = text.chars[index];
422        if ch == open {
423            depth += 1;
424        }
425        if ch == close {
426            depth = depth.saturating_sub(1);
427            if depth == 0 {
428                return Some(index + 1);
429            }
430        }
431    }
432    None
433}
sim_lib_pattern/text_vm.rs

sim_lib_pattern/
text_vm.rs
