sim_lib_lang_javascript/
regexp.rs

1//! Faithful, deliberately narrow ECMAScript RegExp compiler.
2
3use sim_lib_pattern::{TextClass, TextLimits, TextMatch, TextOp, run_text_pattern};
4
5/// Required successor for usable ECMAScript regular expressions.
6pub const JAVASCRIPT_REGEXP_SUCCESSOR: &str = "JAVA_SCRIPT_6 pattern-engine work";
7
8/// An explicitly unsupported ECMAScript RegExp clause.
9#[derive(Clone, Copy, Debug, Eq, PartialEq)]
10pub enum JavascriptRegExpGap {
11    /// Any flag (`d g i m s u v y`) is currently rejected; no stateful `lastIndex` is emulated.
12    Flags,
13    /// Alternation.
14    Alternation,
15    /// Capturing and noncapturing groups.
16    Groups,
17    /// Backreferences.
18    Backreferences,
19    /// Lookahead or lookbehind.
20    Lookaround,
21    /// Unicode property escapes and Unicode-set notation.
22    UnicodeProperties,
23    /// Word-boundary assertions.
24    WordBoundary,
25    /// Counted quantifiers (`{m,n}`).
26    CountedQuantifiers,
27}
28/// Exact first-release gap manifest.
29pub const fn javascript_regexp_gaps() -> &'static [JavascriptRegExpGap] {
30    &[
31        JavascriptRegExpGap::Flags,
32        JavascriptRegExpGap::Alternation,
33        JavascriptRegExpGap::Groups,
34        JavascriptRegExpGap::Backreferences,
35        JavascriptRegExpGap::Lookaround,
36        JavascriptRegExpGap::UnicodeProperties,
37        JavascriptRegExpGap::WordBoundary,
38        JavascriptRegExpGap::CountedQuantifiers,
39    ]
40}
41/// RegExp admission error; unsupported syntax is never approximated.
42#[derive(Clone, Debug, Eq, PartialEq)]
43pub enum JavascriptRegExpError {
44    /// A flag is unsupported.
45    UnsupportedFlag(char),
46    /// Syntax is unsupported or malformed at a byte offset.
47    UnsupportedSyntax {
48        /// Byte offset.
49        offset: usize,
50        /// Stable explanation.
51        reason: &'static str,
52    },
53}
54/// A faithfully compiled RegExp program for the shared bounded text VM.
55#[derive(Clone, Debug, Eq, PartialEq)]
56pub struct JavascriptRegExp {
57    source: String,
58    ops: Vec<TextOp>,
59}
60impl JavascriptRegExp {
61    /// Compile the v1 intersection: literals, `.`, `^`, `$`, simple classes,
62    /// `\d \D \s \S \w \W`, and greedy/lazy `? * +` quantifiers.
63    pub fn compile(source: &str, flags: &str) -> Result<Self, JavascriptRegExpError> {
64        if let Some(flag) = flags.chars().next() {
65            return Err(JavascriptRegExpError::UnsupportedFlag(flag));
66        }
67        let chars: Vec<(usize, char)> = source.char_indices().collect();
68        let mut at = 0;
69        let mut ops = Vec::new();
70        while at < chars.len() {
71            let (offset, ch) = chars[at];
72            match ch {
73                '^' if at == 0 => ops.push(TextOp::AnchorStart),
74                '$' if at + 1 == chars.len() => ops.push(TextOp::AnchorEnd),
75                '.' => ops.push(TextOp::Any),
76                '[' => {
77                    let (class, next) = compile_class(&chars, at)?;
78                    ops.push(TextOp::Class(class));
79                    at = next - 1;
80                }
81                '\\' => {
82                    at += 1;
83                    let Some((_, escaped)) = chars.get(at).copied() else {
84                        return Err(syntax(offset, "trailing escape"));
85                    };
86                    ops.push(escape_atom(escaped, offset)?);
87                }
88                '*' | '+' | '?' => {
89                    let (min, max) = match ch {
90                        '*' => (0, None),
91                        '+' => (1, None),
92                        '?' => (0, Some(1)),
93                        _ => unreachable!(),
94                    };
95                    if !matches!(
96                        ops.last(),
97                        Some(TextOp::Literal(_) | TextOp::Any | TextOp::Class(_))
98                    ) {
99                        return Err(syntax(offset, "quantifier has no admissible atom"));
100                    }
101                    let lazy = chars.get(at + 1).is_some_and(|(_, c)| *c == '?');
102                    ops.push(TextOp::Repeat {
103                        min,
104                        max,
105                        greedy: !lazy,
106                    });
107                    if lazy {
108                        at += 1;
109                    }
110                }
111                '|' | '(' | ')' | '{' | '}' => {
112                    return Err(syntax(
113                        offset,
114                        "syntax requires JAVA_SCRIPT_6 pattern-engine work",
115                    ));
116                }
117                _ => ops.push(TextOp::Literal(ch)),
118            }
119            at += 1;
120        }
121        Ok(Self {
122            source: source.into(),
123            ops,
124        })
125    }
126    /// Original source.
127    pub fn source(&self) -> &str {
128        &self.source
129    }
130    /// Inspect the shared-VM program.
131    pub fn ops(&self) -> &[TextOp] {
132        &self.ops
133    }
134    /// Execute under an explicit shared-VM step bound.
135    pub fn find(&self, subject: &str, init: usize, max_steps: usize) -> Option<TextMatch> {
136        run_text_pattern(&self.ops, subject, init, TextLimits { max_steps })
137    }
138}
139fn syntax(offset: usize, reason: &'static str) -> JavascriptRegExpError {
140    JavascriptRegExpError::UnsupportedSyntax { offset, reason }
141}
142fn escape_atom(ch: char, offset: usize) -> Result<TextOp, JavascriptRegExpError> {
143    Ok(match ch {
144        'd' => TextOp::Class(TextClass::Digit),
145        'D' => TextOp::Class(TextClass::Not(Box::new(TextClass::Digit))),
146        's' => TextOp::Class(TextClass::Space),
147        'S' => TextOp::Class(TextClass::Not(Box::new(TextClass::Space))),
148        'w' => TextOp::Class(TextClass::Alnum),
149        'W' => TextOp::Class(TextClass::Not(Box::new(TextClass::Alnum))),
150        'b' | 'B' => return Err(syntax(offset, "word-boundary assertions are unsupported")),
151        '1'..='9' => return Err(syntax(offset, "backreferences are unsupported")),
152        'p' | 'P' => return Err(syntax(offset, "Unicode property escapes are unsupported")),
153        other => TextOp::Literal(other),
154    })
155}
156fn compile_class(
157    chars: &[(usize, char)],
158    start: usize,
159) -> Result<(TextClass, usize), JavascriptRegExpError> {
160    let offset = chars[start].0;
161    let mut at = start + 1;
162    let negated = chars.get(at).is_some_and(|(_, c)| *c == '^');
163    if negated {
164        at += 1;
165    }
166    let mut literals = Vec::new();
167    let mut ranges = Vec::new();
168    let mut classes = Vec::new();
169    while let Some((pos, ch)) = chars.get(at).copied() {
170        if ch == ']' && at > start + 1 {
171            return Ok((
172                TextClass::Set {
173                    chars: literals,
174                    ranges,
175                    classes,
176                    negated,
177                },
178                at + 1,
179            ));
180        }
181        let atom = if ch == '\\' {
182            at += 1;
183            let Some((_, e)) = chars.get(at).copied() else {
184                return Err(syntax(pos, "trailing class escape"));
185            };
186            match escape_atom(e, pos)? {
187                TextOp::Class(c) => {
188                    classes.push(c);
189                    None
190                }
191                TextOp::Literal(c) => Some(c),
192                _ => None,
193            }
194        } else {
195            Some(ch)
196        };
197        if let Some(first) = atom {
198            if chars.get(at + 1).is_some_and(|(_, c)| *c == '-')
199                && chars.get(at + 2).is_some_and(|(_, c)| *c != ']')
200            {
201                let end = chars[at + 2].1;
202                if first > end {
203                    return Err(syntax(pos, "descending character-class range"));
204                }
205                ranges.push((first, end));
206                at += 2;
207            } else {
208                literals.push(first);
209            }
210        }
211        at += 1;
212    }
213    Err(syntax(offset, "unterminated character class"))
214}
215
216#[cfg(test)]
217mod tests {
218    use super::*;
219    #[test]
220    fn admitted_subset_executes_in_bounded_organ() {
221        let r = JavascriptRegExp::compile(r"^[A-Z]+\d?$", "").unwrap();
222        assert!(r.find("SIM4", 0, 1000).is_some());
223        assert!(r.find("sim", 0, 1000).is_none());
224    }
225    #[test]
226    fn unsupported_features_fail_closed() {
227        for p in ["a|b", "(a)", r"(a)\1", r"\p{Letter}", r"\bword"] {
228            assert!(JavascriptRegExp::compile(p, "").is_err(), "{p}");
229        }
230        assert_eq!(
231            JavascriptRegExp::compile("a", "g"),
232            Err(JavascriptRegExpError::UnsupportedFlag('g'))
233        );
234    }
235    #[test]
236    fn gaps_and_successor_are_blunt() {
237        assert_eq!(javascript_regexp_gaps().len(), 8);
238        assert_eq!(
239            JAVASCRIPT_REGEXP_SUCCESSOR,
240            "JAVA_SCRIPT_6 pattern-engine work"
241        );
242    }
243}
sim_lib_lang_javascript/regexp.rs

sim_lib_lang_javascript/
regexp.rs
