sim_lib_pattern/
lua_dialect.rs

1//! Lua text-pattern compiler for the shared VM.
2
3use sim_kernel::{Error, Result};
4
5use crate::{
6    Anchor, CaptureId, EnginePolicy, IrNode, PatternDialect, PatternIr, RepeatBounds, ScalarDomain,
7    TextClass, TextOp,
8};
9use std::collections::BTreeMap;
10
11/// Lua-only operations admitted by the shared text automaton.
12#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
13pub enum LuaExtension {
14    /// Match one character from a Lua character class.
15    Class(TextClass),
16    /// Match a delimiter pair, including nested pairs.
17    Balanced {
18        /// Opening delimiter.
19        open: char,
20        /// Closing delimiter.
21        close: char,
22    },
23    /// Assert a transition from outside to inside a Lua character class.
24    Frontier(TextClass),
25}
26
27/// Compiler for Lua-style text patterns.
28#[derive(Clone, Copy, Debug, Default)]
29pub struct LuaPatternDialect;
30
31impl PatternDialect for LuaPatternDialect {
32    fn compile(&self, pattern: &str) -> Result<Vec<TextOp>> {
33        let ir = self.compile_ir(pattern)?;
34        Ok(project_compatibility_program(ir.root()))
35    }
36}
37
38impl LuaPatternDialect {
39    /// Lowers Lua syntax directly into validated shared pattern IR.
40    pub fn compile_ir(self, pattern: &str) -> Result<PatternIr<ScalarDomain, LuaExtension>> {
41        LuaCompiler::new(pattern).compile()
42    }
43}
44
45/// Compiles a Lua-style text pattern into shared VM operations.
46///
47/// # Errors
48///
49/// Returns an error when the pattern is malformed.
50pub fn compile_lua_pattern(pattern: &str) -> Result<Vec<TextOp>> {
51    LuaPatternDialect.compile(pattern)
52}
53
54struct LuaCompiler {
55    chars: Vec<char>,
56    index: usize,
57}
58
59impl LuaCompiler {
60    fn new(pattern: &str) -> Self {
61        Self {
62            chars: pattern.chars().collect(),
63            index: 0,
64        }
65    }
66
67    fn compile(mut self) -> Result<PatternIr<ScalarDomain, LuaExtension>> {
68        let mut frames = vec![Vec::new()];
69        let mut next_capture = 0u32;
70        while let Some(ch) = self.next() {
71            match ch {
72                '^' if frames.len() == 1 && frames[0].is_empty() => {
73                    frames[0].push(IrNode::Anchor(Anchor::SubjectStart));
74                }
75                '^' => self.push_atom(&mut frames, IrNode::Symbol('^'))?,
76                '$' if self.is_end() => frames
77                    .last_mut()
78                    .expect("root frame exists")
79                    .push(IrNode::Anchor(Anchor::SubjectEnd)),
80                '$' => self.push_atom(&mut frames, IrNode::Symbol('$'))?,
81                '.' => self.push_atom(&mut frames, IrNode::Any)?,
82                '(' => frames.push(Vec::new()),
83                ')' => {
84                    if frames.len() == 1 {
85                        return Err(malformed("capture close without open"));
86                    }
87                    let body = IrNode::Concat(frames.pop().expect("capture frame exists"));
88                    frames
89                        .last_mut()
90                        .expect("parent frame exists")
91                        .push(IrNode::Capture {
92                            id: CaptureId(next_capture),
93                            node: Box::new(body),
94                        });
95                    next_capture += 1;
96                }
97                '[' => {
98                    let set = self.parse_set()?;
99                    self.push_atom(&mut frames, IrNode::Extension(LuaExtension::Class(set)))?;
100                }
101                '%' => {
102                    let escaped = self.parse_percent()?;
103                    match escaped {
104                        Escaped::Atom(node) => self.push_atom(&mut frames, node)?,
105                        Escaped::ZeroWidth(node) => {
106                            frames.last_mut().expect("root frame exists").push(node)
107                        }
108                    }
109                }
110                '*' | '+' | '-' | '?' => return Err(malformed("quantifier without atom")),
111                literal => self.push_atom(&mut frames, IrNode::Symbol(literal))?,
112            }
113        }
114        if frames.len() != 1 {
115            return Err(malformed("unterminated capture"));
116        }
117        let root = IrNode::Concat(frames.pop().expect("root frame exists"));
118        let extensions = collect_extensions(&root);
119        PatternIr::new(root, BTreeMap::new(), &EnginePolicy::new(extensions))
120            .map_err(|error| malformed(&error.to_string()))
121    }
122
123    fn push_atom(
124        &mut self,
125        frames: &mut [Vec<IrNode<char, LuaExtension>>],
126        mut node: IrNode<char, LuaExtension>,
127    ) -> Result<()> {
128        if let Some((min, max, greedy)) = self.peek().and_then(lua_quantifier) {
129            self.index += 1;
130            node = IrNode::Repeat {
131                node: Box::new(node),
132                bounds: RepeatBounds::new(min, max)
133                    .expect("Lua quantifiers have valid static bounds"),
134                greedy,
135            };
136        }
137        frames.last_mut().expect("root frame exists").push(node);
138        Ok(())
139    }
140
141    fn parse_percent(&mut self) -> Result<Escaped> {
142        let Some(ch) = self.next() else {
143            return Err(malformed("dangling percent escape"));
144        };
145        Ok(match ch {
146            'a' => class_atom(TextClass::Alpha),
147            'A' => class_atom(TextClass::Not(Box::new(TextClass::Alpha))),
148            'd' => class_atom(TextClass::Digit),
149            'D' => class_atom(TextClass::Not(Box::new(TextClass::Digit))),
150            'l' => class_atom(TextClass::Lower),
151            'L' => class_atom(TextClass::Not(Box::new(TextClass::Lower))),
152            'u' => class_atom(TextClass::Upper),
153            'U' => class_atom(TextClass::Not(Box::new(TextClass::Upper))),
154            'w' => class_atom(TextClass::Alnum),
155            'W' => class_atom(TextClass::Not(Box::new(TextClass::Alnum))),
156            's' => class_atom(TextClass::Space),
157            'S' => class_atom(TextClass::Not(Box::new(TextClass::Space))),
158            'p' => class_atom(TextClass::Punct),
159            'P' => class_atom(TextClass::Not(Box::new(TextClass::Punct))),
160            'x' => class_atom(TextClass::Hex),
161            'X' => class_atom(TextClass::Not(Box::new(TextClass::Hex))),
162            'z' => class_atom(TextClass::Zero),
163            'b' => {
164                let open = self
165                    .next()
166                    .ok_or_else(|| malformed("balanced pattern missing open delimiter"))?;
167                let close = self
168                    .next()
169                    .ok_or_else(|| malformed("balanced pattern missing close delimiter"))?;
170                Escaped::Atom(IrNode::Extension(LuaExtension::Balanced { open, close }))
171            }
172            'f' => {
173                if self.next() != Some('[') {
174                    return Err(malformed("frontier pattern requires a character set"));
175                }
176                Escaped::ZeroWidth(IrNode::Extension(LuaExtension::Frontier(self.parse_set()?)))
177            }
178            literal => Escaped::Atom(IrNode::Symbol(literal)),
179        })
180    }
181
182    fn parse_set(&mut self) -> Result<TextClass> {
183        let mut negated = false;
184        if self.peek() == Some('^') {
185            self.index += 1;
186            negated = true;
187        }
188        parse_set_body(
189            &self.chars,
190            &mut self.index,
191            negated,
192            "unterminated character set",
193        )
194    }
195
196    fn next(&mut self) -> Option<char> {
197        let ch = self.chars.get(self.index).copied()?;
198        self.index += 1;
199        Some(ch)
200    }
201
202    fn peek(&self) -> Option<char> {
203        self.chars.get(self.index).copied()
204    }
205
206    fn is_end(&self) -> bool {
207        self.index >= self.chars.len()
208    }
209}
210
211enum Escaped {
212    Atom(IrNode<char, LuaExtension>),
213    ZeroWidth(IrNode<char, LuaExtension>),
214}
215
216fn class_atom(class: TextClass) -> Escaped {
217    Escaped::Atom(IrNode::Extension(LuaExtension::Class(class)))
218}
219
220pub(crate) fn parse_set_body(
221    chars: &[char],
222    index: &mut usize,
223    negated: bool,
224    unterminated: &str,
225) -> Result<TextClass> {
226    let mut literals = Vec::new();
227    let mut ranges = Vec::new();
228    let mut classes = Vec::new();
229    let mut first = true;
230    while let Some(ch) = chars.get(*index).copied() {
231        *index += 1;
232        if ch == ']' && !first {
233            return Ok(TextClass::Set {
234                chars: literals,
235                ranges,
236                classes,
237                negated,
238            });
239        }
240        first = false;
241        let item = if ch == '%' {
242            let escaped = chars
243                .get(*index)
244                .copied()
245                .ok_or_else(|| malformed("dangling set escape"))?;
246            *index += 1;
247            set_escape(escaped)
248        } else {
249            SetItem::Literal(ch)
250        };
251        if let SetItem::Literal(start) = item {
252            if chars.get(*index).copied() == Some('-')
253                && chars.get(*index + 1).is_some_and(|end| *end != ']')
254            {
255                *index += 1;
256                let end = chars
257                    .get(*index)
258                    .copied()
259                    .ok_or_else(|| malformed(unterminated))?;
260                *index += 1;
261                ranges.push((start, end));
262            } else {
263                literals.push(start);
264            }
265        } else if let SetItem::Class(class) = item {
266            classes.push(class);
267        }
268    }
269    Err(malformed(unterminated))
270}
271
272enum SetItem {
273    Literal(char),
274    Class(TextClass),
275}
276
277fn set_escape(ch: char) -> SetItem {
278    match ch {
279        'a' => SetItem::Class(TextClass::Alpha),
280        'd' => SetItem::Class(TextClass::Digit),
281        'l' => SetItem::Class(TextClass::Lower),
282        'u' => SetItem::Class(TextClass::Upper),
283        'w' => SetItem::Class(TextClass::Alnum),
284        's' => SetItem::Class(TextClass::Space),
285        'p' => SetItem::Class(TextClass::Punct),
286        'x' => SetItem::Class(TextClass::Hex),
287        'z' => SetItem::Class(TextClass::Zero),
288        literal => SetItem::Literal(literal),
289    }
290}
291
292fn lua_quantifier(ch: char) -> Option<(usize, Option<usize>, bool)> {
293    match ch {
294        '*' => Some((0, None, true)),
295        '+' => Some((1, None, true)),
296        '-' => Some((0, None, false)),
297        '?' => Some((0, Some(1), true)),
298        _ => None,
299    }
300}
301
302fn collect_extensions(node: &IrNode<char, LuaExtension>) -> Vec<LuaExtension> {
303    let mut extensions = Vec::new();
304    visit(node, &mut |extension| extensions.push(extension.clone()));
305    extensions
306}
307
308fn project_compatibility_program(node: &IrNode<char, LuaExtension>) -> Vec<TextOp> {
309    let mut ops = Vec::new();
310    project(node, &mut ops);
311    ops
312}
313
314fn project(node: &IrNode<char, LuaExtension>, ops: &mut Vec<TextOp>) {
315    match node {
316        IrNode::Symbol(ch) => ops.push(TextOp::Literal(*ch)),
317        IrNode::Any => ops.push(TextOp::Any),
318        IrNode::Concat(nodes) | IrNode::Alternation(nodes) => {
319            for node in nodes {
320                project(node, ops);
321            }
322        }
323        IrNode::Repeat {
324            node,
325            bounds,
326            greedy,
327        } => {
328            project(node, ops);
329            ops.push(TextOp::Repeat {
330                min: bounds.min(),
331                max: bounds.max(),
332                greedy: *greedy,
333            });
334        }
335        IrNode::Group(node) => project(node, ops),
336        IrNode::Capture { node, .. } => {
337            ops.push(TextOp::CaptureStart);
338            project(node, ops);
339            ops.push(TextOp::CaptureEnd);
340        }
341        IrNode::Anchor(Anchor::SubjectStart) => ops.push(TextOp::AnchorStart),
342        IrNode::Anchor(Anchor::SubjectEnd) => ops.push(TextOp::AnchorEnd),
343        IrNode::Extension(LuaExtension::Class(class)) => ops.push(TextOp::Class(class.clone())),
344        IrNode::Extension(LuaExtension::Balanced { open, close }) => {
345            ops.push(TextOp::Balanced {
346                open: *open,
347                close: *close,
348            });
349        }
350        IrNode::Extension(LuaExtension::Frontier(class)) => {
351            ops.push(TextOp::Frontier(class.clone()));
352        }
353        IrNode::Assertion(_) => unreachable!("Lua lowering does not create assertions"),
354    }
355}
356
357fn visit(node: &IrNode<char, LuaExtension>, f: &mut impl FnMut(&LuaExtension)) {
358    match node {
359        IrNode::Concat(nodes) | IrNode::Alternation(nodes) => {
360            for node in nodes {
361                visit(node, f);
362            }
363        }
364        IrNode::Repeat { node, .. } | IrNode::Group(node) | IrNode::Capture { node, .. } => {
365            visit(node, f);
366        }
367        IrNode::Extension(extension) => f(extension),
368        IrNode::Symbol(_) | IrNode::Any | IrNode::Anchor(_) | IrNode::Assertion(_) => {}
369    }
370}
371
372fn malformed(message: &str) -> Error {
373    Error::Eval(format!("malformed Lua pattern: {message}"))
374}
375
376#[cfg(test)]
377mod tests {
378    use super::*;
379
380    #[test]
381    fn balanced_match_is_one_named_adapter_node() {
382        let ir = LuaPatternDialect.compile_ir("%b()").unwrap();
383        let mut extensions = Vec::new();
384        visit(ir.root(), &mut |extension| {
385            extensions.push(extension.clone())
386        });
387        assert_eq!(
388            extensions,
389            vec![LuaExtension::Balanced {
390                open: '(',
391                close: ')'
392            }]
393        );
394    }
395
396    #[test]
397    fn capture_ids_and_compatibility_boundaries_are_frozen() {
398        let ir = LuaPatternDialect.compile_ir("(%a+)%s+(%d+)").unwrap();
399        let mut ids = Vec::new();
400        fn collect(node: &IrNode<char, LuaExtension>, ids: &mut Vec<CaptureId>) {
401            match node {
402                IrNode::Concat(nodes) | IrNode::Alternation(nodes) => {
403                    for node in nodes {
404                        collect(node, ids);
405                    }
406                }
407                IrNode::Repeat { node, .. } | IrNode::Group(node) => collect(node, ids),
408                IrNode::Capture { id, node } => {
409                    ids.push(*id);
410                    collect(node, ids);
411                }
412                IrNode::Symbol(_)
413                | IrNode::Any
414                | IrNode::Anchor(_)
415                | IrNode::Assertion(_)
416                | IrNode::Extension(_) => {}
417            }
418        }
419        collect(ir.root(), &mut ids);
420        assert_eq!(ids, vec![CaptureId(0), CaptureId(1)]);
421        assert_eq!(
422            project_compatibility_program(ir.root())
423                .iter()
424                .filter(|op| matches!(op, TextOp::CaptureStart | TextOp::CaptureEnd))
425                .count(),
426            4
427        );
428    }
429}
sim_lib_pattern/lua_dialect.rs

sim_lib_pattern/
lua_dialect.rs
