sim_lib_lang_javascript/
regexp.rs

1// conformance: ECMAScript regular expressions lower into the shared pattern organ.
2
3//! Faithful, deliberately narrow ECMAScript RegExp compiler.
4
5use sim_lib_pattern::{
6    Anchor, Automaton, CaptureId, CodeUnitDomain, DomainExecutionOutcome, EnginePolicy, IrNode,
7    PatternIr, RepeatBounds, TextLimits, TextMatch, compile, execute_code_units,
8};
9use sim_text::CodeUnitString;
10use std::collections::{BTreeMap, BTreeSet};
11
12/// Required successor for usable ECMAScript regular expressions.
13pub const JAVASCRIPT_REGEXP_SUCCESSOR: &str = "remaining ECMAScript RegExp clauses";
14
15/// An explicitly unsupported ECMAScript RegExp clause.
16#[derive(Clone, Copy, Debug, Eq, PartialEq)]
17pub enum JavascriptRegExpGap {
18    /// Any flag (`d g i m s u v y`) is currently rejected; no stateful `lastIndex` is emulated.
19    Flags,
20    /// Backreferences.
21    Backreferences,
22    /// Lookahead or lookbehind.
23    Lookaround,
24    /// Unicode property escapes and Unicode-set notation.
25    UnicodeProperties,
26    /// Word-boundary assertions.
27    WordBoundary,
28}
29/// Exact first-release gap manifest.
30pub const fn javascript_regexp_gaps() -> &'static [JavascriptRegExpGap] {
31    &[
32        JavascriptRegExpGap::Flags,
33        JavascriptRegExpGap::Backreferences,
34        JavascriptRegExpGap::Lookaround,
35        JavascriptRegExpGap::UnicodeProperties,
36        JavascriptRegExpGap::WordBoundary,
37    ]
38}
39/// RegExp admission error; unsupported syntax is never approximated.
40#[derive(Clone, Debug, Eq, PartialEq)]
41pub enum JavascriptRegExpError {
42    /// A flag is unsupported.
43    UnsupportedFlag(char),
44    /// Syntax is unsupported or malformed at a byte offset.
45    UnsupportedSyntax {
46        /// Byte offset.
47        offset: usize,
48        /// Stable explanation.
49        reason: &'static str,
50    },
51}
52/// A faithfully compiled RegExp program for the shared bounded text VM.
53#[derive(Clone, Debug, Eq, PartialEq)]
54pub struct JavascriptRegExp {
55    source: String,
56    automaton: Automaton<u16, CodeUnitClass>,
57    anchored_start: bool,
58}
59impl JavascriptRegExp {
60    /// Compile the regular intersection, including alternation, groups,
61    /// captures, anchors, classes, and greedy/lazy counted quantifiers.
62    pub fn compile(source: &str, flags: &str) -> Result<Self, JavascriptRegExpError> {
63        if let Some(flag) = flags.chars().next() {
64            return Err(JavascriptRegExpError::UnsupportedFlag(flag));
65        }
66        let root = Parser::new(source).parse()?;
67        let policy = EnginePolicy::new(classes_in(&root));
68        let ir = PatternIr::<CodeUnitDomain, CodeUnitClass>::new(root, BTreeMap::new(), &policy)
69            .map_err(|_| syntax(0, "invalid regular expression"))?;
70        Ok(Self {
71            source: source.into(),
72            automaton: compile(&ir),
73            anchored_start: source.starts_with('^'),
74        })
75    }
76    /// Original source.
77    pub fn source(&self) -> &str {
78        &self.source
79    }
80    /// Execute under an explicit shared-engine transition bound.
81    /// Match and capture offsets are ECMAScript UTF-16 code-unit offsets.
82    pub fn find(&self, subject: &str, init: usize, max_steps: usize) -> Option<TextMatch> {
83        let subject = CodeUnitString::from_scalar(subject);
84        let mut starts = if self.anchored_start {
85            (init == 0).then_some(0..=0)
86        } else {
87            Some(init..=subject.len())
88        }?;
89        starts.find_map(|start| {
90            let tail = CodeUnitString::from_code_units(subject.as_code_units()[start..].to_vec());
91            match execute_code_units(
92                &self.automaton,
93                &tail,
94                TextLimits {
95                    max_steps,
96                    ..TextLimits::default()
97                },
98                |class, unit| class.matches(*unit),
99            ) {
100                DomainExecutionOutcome::Match { matched, .. } => Some(TextMatch {
101                    start: start + matched.start.get(),
102                    end: start + matched.end.get(),
103                    captures: matched
104                        .captures
105                        .values()
106                        .map(|span| (start + span.start.get(), start + span.end.get()))
107                        .collect(),
108                }),
109                _ => None,
110            }
111        })
112    }
113}
114fn syntax(offset: usize, reason: &'static str) -> JavascriptRegExpError {
115    JavascriptRegExpError::UnsupportedSyntax { offset, reason }
116}
117#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
118enum CodeUnitClass {
119    Digit(bool),
120    Space(bool),
121    Word(bool),
122    LineTerminator(bool),
123    Set {
124        units: Vec<u16>,
125        ranges: Vec<(u16, u16)>,
126        classes: Vec<CodeUnitClass>,
127        negated: bool,
128    },
129}
130impl CodeUnitClass {
131    fn matches(&self, unit: u16) -> bool {
132        match self {
133            Self::Digit(negated) => (b'0' as u16..=b'9' as u16).contains(&unit) != *negated,
134            Self::Space(negated) => {
135                matches!(unit, 0x09..=0x0d | 0x20 | 0x00a0 | 0x1680 | 0x2000..=0x200a | 0x2028 | 0x2029 | 0x202f | 0x205f | 0x3000 | 0xfeff)
136                    != *negated
137            }
138            Self::Word(negated) => {
139                ((b'0' as u16..=b'9' as u16).contains(&unit)
140                    || (b'A' as u16..=b'Z' as u16).contains(&unit)
141                    || (b'a' as u16..=b'z' as u16).contains(&unit)
142                    || unit == b'_' as u16)
143                    != *negated
144            }
145            Self::LineTerminator(negated) => {
146                matches!(unit, 0x0a | 0x0d | 0x2028 | 0x2029) != *negated
147            }
148            Self::Set {
149                units,
150                ranges,
151                classes,
152                negated,
153            } => {
154                (units.contains(&unit)
155                    || ranges.iter().any(|(a, b)| *a <= unit && unit <= *b)
156                    || classes.iter().any(|class| class.matches(unit)))
157                    != *negated
158            }
159        }
160    }
161}
162fn classes_in(root: &IrNode<u16, CodeUnitClass>) -> BTreeSet<CodeUnitClass> {
163    fn visit(node: &IrNode<u16, CodeUnitClass>, found: &mut BTreeSet<CodeUnitClass>) {
164        match node {
165            IrNode::Extension(class) => {
166                found.insert(class.clone());
167            }
168            IrNode::Concat(nodes) | IrNode::Alternation(nodes) => {
169                nodes.iter().for_each(|node| visit(node, found))
170            }
171            IrNode::Repeat { node, .. } | IrNode::Group(node) | IrNode::Capture { node, .. } => {
172                visit(node, found)
173            }
174            IrNode::Symbol(_) | IrNode::Any | IrNode::Anchor(_) | IrNode::Assertion(_) => {}
175        }
176    }
177    let mut found = BTreeSet::new();
178    visit(root, &mut found);
179    found
180}
181fn escape_atom(
182    ch: char,
183    offset: usize,
184) -> Result<IrNode<u16, CodeUnitClass>, JavascriptRegExpError> {
185    Ok(match ch {
186        'd' => IrNode::Extension(CodeUnitClass::Digit(false)),
187        'D' => IrNode::Extension(CodeUnitClass::Digit(true)),
188        's' => IrNode::Extension(CodeUnitClass::Space(false)),
189        'S' => IrNode::Extension(CodeUnitClass::Space(true)),
190        'w' => IrNode::Extension(CodeUnitClass::Word(false)),
191        'W' => IrNode::Extension(CodeUnitClass::Word(true)),
192        'b' | 'B' => return Err(syntax(offset, "word-boundary assertions are unsupported")),
193        '1'..='9' => return Err(syntax(offset, "backreferences are unsupported")),
194        'p' | 'P' => return Err(syntax(offset, "Unicode property escapes are unsupported")),
195        other => literal(other),
196    })
197}
198fn literal(ch: char) -> IrNode<u16, CodeUnitClass> {
199    let nodes = ch
200        .encode_utf16(&mut [0; 2])
201        .iter()
202        .copied()
203        .map(IrNode::Symbol)
204        .collect::<Vec<_>>();
205    if nodes.len() == 1 {
206        nodes.into_iter().next().unwrap()
207    } else {
208        IrNode::Concat(nodes)
209    }
210}
211
212struct Parser {
213    chars: Vec<(usize, char)>,
214    at: usize,
215    capture: u32,
216}
217impl Parser {
218    fn new(source: &str) -> Self {
219        Self {
220            chars: source.char_indices().collect(),
221            at: 0,
222            capture: 0,
223        }
224    }
225    fn parse(mut self) -> Result<IrNode<u16, CodeUnitClass>, JavascriptRegExpError> {
226        let root = self.alternation()?;
227        if let Some((offset, _)) = self.peek() {
228            return Err(syntax(offset, "unmatched closing parenthesis"));
229        }
230        Ok(root)
231    }
232    fn alternation(&mut self) -> Result<IrNode<u16, CodeUnitClass>, JavascriptRegExpError> {
233        let mut branches = vec![self.sequence()?];
234        while self.take('|') {
235            branches.push(self.sequence()?);
236        }
237        Ok(if branches.len() == 1 {
238            branches.pop().unwrap()
239        } else {
240            IrNode::Alternation(branches)
241        })
242    }
243    fn sequence(&mut self) -> Result<IrNode<u16, CodeUnitClass>, JavascriptRegExpError> {
244        let mut nodes = Vec::new();
245        while self.peek().is_some_and(|(_, ch)| ch != ')' && ch != '|') {
246            nodes.push(self.quantified()?);
247        }
248        Ok(IrNode::Concat(nodes))
249    }
250    fn quantified(&mut self) -> Result<IrNode<u16, CodeUnitClass>, JavascriptRegExpError> {
251        let mut node = self.atom()?;
252        let Some((offset, ch)) = self.peek() else {
253            return Ok(node);
254        };
255        let bounds = match ch {
256            '*' => {
257                self.at += 1;
258                Some(RepeatBounds::new(0, None).unwrap())
259            }
260            '+' => {
261                self.at += 1;
262                Some(RepeatBounds::new(1, None).unwrap())
263            }
264            '?' => {
265                self.at += 1;
266                Some(RepeatBounds::new(0, Some(1)).unwrap())
267            }
268            '{' => Some(self.counted(offset)?),
269            _ => None,
270        };
271        if let Some(bounds) = bounds {
272            let greedy = !self.take('?');
273            node = IrNode::Repeat {
274                node: Box::new(node),
275                bounds,
276                greedy,
277            };
278        }
279        Ok(node)
280    }
281    fn counted(&mut self, offset: usize) -> Result<RepeatBounds, JavascriptRegExpError> {
282        self.at += 1;
283        let min = self
284            .number()
285            .ok_or_else(|| syntax(offset, "malformed counted quantifier"))?;
286        let max = if self.take('}') {
287            Some(min)
288        } else if self.take(',') {
289            let max = self.number();
290            if !self.take('}') {
291                return Err(syntax(offset, "unterminated counted quantifier"));
292            }
293            max
294        } else {
295            return Err(syntax(offset, "malformed counted quantifier"));
296        };
297        RepeatBounds::new(min, max)
298            .map_err(|_| syntax(offset, "counted quantifier maximum is below minimum"))
299    }
300    fn number(&mut self) -> Option<usize> {
301        let start = self.at;
302        let mut value = 0usize;
303        while let Some((_, ch)) = self.peek().filter(|(_, ch)| ch.is_ascii_digit()) {
304            value = value
305                .checked_mul(10)?
306                .checked_add(ch.to_digit(10)? as usize)?;
307            self.at += 1;
308        }
309        (self.at > start).then_some(value)
310    }
311    fn atom(&mut self) -> Result<IrNode<u16, CodeUnitClass>, JavascriptRegExpError> {
312        let (offset, ch) = self.peek().ok_or_else(|| syntax(0, "missing atom"))?;
313        self.at += 1;
314        match ch {
315            '^' => Ok(IrNode::Anchor(Anchor::SubjectStart)),
316            '$' => Ok(IrNode::Anchor(Anchor::SubjectEnd)),
317            '.' => Ok(IrNode::Extension(CodeUnitClass::LineTerminator(true))),
318            '(' => {
319                let capture = if self.take('?') {
320                    if self.take(':') {
321                        None
322                    } else {
323                        return Err(syntax(
324                            offset,
325                            "lookaround and special groups are unsupported",
326                        ));
327                    }
328                } else {
329                    let id = CaptureId(self.capture);
330                    self.capture += 1;
331                    Some(id)
332                };
333                let node = self.alternation()?;
334                if !self.take(')') {
335                    return Err(syntax(offset, "unterminated group"));
336                }
337                Ok(match capture {
338                    Some(id) => IrNode::Capture {
339                        id,
340                        node: Box::new(node),
341                    },
342                    None => IrNode::Group(Box::new(node)),
343                })
344            }
345            '[' => self.class(offset),
346            '\\' => {
347                let (_, escaped) = self
348                    .peek()
349                    .ok_or_else(|| syntax(offset, "trailing escape"))?;
350                self.at += 1;
351                escape_atom(escaped, offset)
352            }
353            '*' | '+' | '?' | '{' => Err(syntax(offset, "quantifier has no admissible atom")),
354            ')' | '|' => unreachable!(),
355            _ => Ok(literal(ch)),
356        }
357    }
358    fn class(
359        &mut self,
360        offset: usize,
361    ) -> Result<IrNode<u16, CodeUnitClass>, JavascriptRegExpError> {
362        let negated = self.take('^');
363        let mut units = Vec::new();
364        let mut ranges = Vec::new();
365        let mut classes = Vec::new();
366        while let Some((pos, ch)) = self.peek() {
367            if ch == ']' {
368                self.at += 1;
369                return Ok(IrNode::Extension(CodeUnitClass::Set {
370                    units,
371                    ranges,
372                    classes,
373                    negated,
374                }));
375            }
376            self.at += 1;
377            let first = if ch == '\\' {
378                let (_, e) = self
379                    .peek()
380                    .ok_or_else(|| syntax(pos, "trailing class escape"))?;
381                self.at += 1;
382                if matches!(e, 'p' | 'P') {
383                    return Err(syntax(pos, "Unicode property escapes are unsupported"));
384                }
385                if let Some(class) = match e {
386                    'd' => Some(CodeUnitClass::Digit(false)),
387                    'D' => Some(CodeUnitClass::Digit(true)),
388                    's' => Some(CodeUnitClass::Space(false)),
389                    'S' => Some(CodeUnitClass::Space(true)),
390                    'w' => Some(CodeUnitClass::Word(false)),
391                    'W' => Some(CodeUnitClass::Word(true)),
392                    _ => None,
393                } {
394                    classes.push(class);
395                    continue;
396                }
397                e
398            } else {
399                ch
400            };
401            let mut first_units = [0; 2];
402            let encoded = first.encode_utf16(&mut first_units);
403            if encoded.len() != 1 {
404                return Err(syntax(
405                    pos,
406                    "non-BMP character classes require Unicode set support",
407                ));
408            }
409            let first = encoded[0];
410            if self.take('-') && self.peek().is_some_and(|(_, c)| c != ']') {
411                let (end_pos, end) = self.peek().unwrap();
412                self.at += 1;
413                let mut end_units = [0; 2];
414                let encoded = end.encode_utf16(&mut end_units);
415                if encoded.len() != 1 || first > encoded[0] {
416                    return Err(syntax(end_pos, "invalid character-class range"));
417                }
418                ranges.push((first, encoded[0]));
419            } else {
420                units.push(first);
421            }
422        }
423        Err(syntax(offset, "unterminated character class"))
424    }
425    fn peek(&self) -> Option<(usize, char)> {
426        self.chars.get(self.at).copied()
427    }
428    fn take(&mut self, expected: char) -> bool {
429        if self.peek().is_some_and(|(_, ch)| ch == expected) {
430            self.at += 1;
431            true
432        } else {
433            false
434        }
435    }
436}
437
438#[cfg(test)]
439mod tests {
440    use super::*;
441    use std::sync::Arc;
442
443    use sim_kernel::{Cx, Datum, DefaultFactory, NoopEvalPolicy, Ref, Symbol};
444    use sim_lib_standard_core::{
445        BoundedLane, CanonicalObservation, CanonicalOutcome, CharacterizationCapture,
446        ScenarioLimits, ScenarioObservationLane, ScenarioSpec, publish_characterization_capture,
447    };
448
449    fn case(name: &str, fields: &[(&str, String)]) -> Datum {
450        Datum::Node {
451            tag: Symbol::qualified("javascript-regexp-characterization", "case/v1"),
452            fields: std::iter::once((Symbol::new("name"), Datum::String(name.to_owned())))
453                .chain(
454                    fields
455                        .iter()
456                        .map(|(key, value)| (Symbol::new(*key), Datum::String(value.clone()))),
457                )
458                .collect(),
459        }
460    }
461
462    fn refusal(source: &str, flags: &str, clause: &str) -> Datum {
463        let error = JavascriptRegExp::compile(source, flags).unwrap_err();
464        let (class, diagnostic) = match error {
465            JavascriptRegExpError::UnsupportedFlag(flag) => {
466                ("unsupported-flag", format!("flag {flag} is unsupported"))
467            }
468            JavascriptRegExpError::UnsupportedSyntax { offset, reason } => {
469                ("unsupported-syntax", format!("byte {offset}: {reason}"))
470            }
471        };
472        for roadmap_family in ["PATTERN", "CHARACTERIZE", "ROADMAP"] {
473            assert!(!diagnostic.contains(roadmap_family), "{diagnostic}");
474        }
475        case(
476            "refusal",
477            &[
478                ("clause", clause.to_owned()),
479                ("class", class.to_owned()),
480                ("diagnostic", diagnostic),
481            ],
482        )
483    }
484
485    fn gap_name(gap: JavascriptRegExpGap) -> &'static str {
486        match gap {
487            JavascriptRegExpGap::Flags => "flags",
488            JavascriptRegExpGap::Backreferences => "backreferences",
489            JavascriptRegExpGap::Lookaround => "lookaround",
490            JavascriptRegExpGap::UnicodeProperties => "unicode-properties",
491            JavascriptRegExpGap::WordBoundary => "word-boundary",
492        }
493    }
494    #[test]
495    fn admitted_subset_executes_in_bounded_organ() {
496        let r = JavascriptRegExp::compile(r"^[A-Z]+\d?$", "").unwrap();
497        assert!(r.find("SIM4", 0, 1000).is_some());
498        assert!(r.find("sim", 0, 1000).is_none());
499    }
500    #[test]
501    fn shared_regular_features_report_code_unit_spans() {
502        let regexp = JavascriptRegExp::compile("^(?:ab|\u{1f600}){2,3}(c+?)$", "").unwrap();
503        let matched = regexp.find("ab\u{1f600}cc", 0, 10_000).unwrap();
504        assert_eq!((matched.start, matched.end), (0, 6));
505        assert_eq!(matched.captures, [(4, 6)]);
506        assert!(regexp.find("xababcc", 0, 10_000).is_none());
507        assert!(
508            JavascriptRegExp::compile(r"^[\d]+$", "")
509                .unwrap()
510                .find("42", 0, 1_000)
511                .is_some()
512        );
513        assert!(
514            JavascriptRegExp::compile("^.$", "")
515                .unwrap()
516                .find("\n", 0, 1_000)
517                .is_none()
518        );
519    }
520    #[test]
521    fn refused_clause_keeps_its_typed_diagnostic() {
522        assert_eq!(
523            JavascriptRegExp::compile(r"\bword", ""),
524            Err(JavascriptRegExpError::UnsupportedSyntax {
525                offset: 0,
526                reason: "word-boundary assertions are unsupported",
527            })
528        );
529    }
530    #[test]
531    fn unsupported_features_fail_closed() {
532        for p in [r"(a)\1", r"\p{Letter}", r"\bword", "(?=a)"] {
533            assert!(JavascriptRegExp::compile(p, "").is_err(), "{p}");
534        }
535        assert_eq!(
536            JavascriptRegExp::compile("a", "g"),
537            Err(JavascriptRegExpError::UnsupportedFlag('g'))
538        );
539    }
540    #[test]
541    fn gaps_and_successor_are_blunt() {
542        assert_eq!(javascript_regexp_gaps().len(), 5);
543        assert_eq!(
544            JAVASCRIPT_REGEXP_SUCCESSOR,
545            "remaining ECMAScript RegExp clauses"
546        );
547    }
548
549    #[test]
550    fn current_regexp_behavior_is_a_stable_characterization_capture() {
551        let unicode = JavascriptRegExp::compile("\u{1f600}+", "").unwrap();
552        let unicode_match = unicode.find("x\u{1f600}\u{1f600}y", 0, 1_000).unwrap();
553        let greedy = JavascriptRegExp::compile("a*a", "")
554            .unwrap()
555            .find("aaa", 0, 1_000);
556        let lazy = JavascriptRegExp::compile("a*?a", "")
557            .unwrap()
558            .find("aaa", 0, 1_000);
559        let empty = JavascriptRegExp::compile("a*", "")
560            .unwrap()
561            .find("bbb", 0, 1_000);
562        let limited = JavascriptRegExp::compile("a*b", "")
563            .unwrap()
564            .find("aaab", 0, 1);
565        let cases = vec![
566            case(
567                "unicode-byte-offsets",
568                &[(
569                    "span",
570                    format!("{}..{}", unicode_match.start, unicode_match.end),
571                )],
572            ),
573            case("greedy-repetition", &[("match", format!("{greedy:?}"))]),
574            case("lazy-repetition", &[("match", format!("{lazy:?}"))]),
575            case("empty-match", &[("match", format!("{empty:?}"))]),
576            case(
577                "limit-exhaustion",
578                &[
579                    ("clause", "maximum VM steps".to_owned()),
580                    (
581                        "outcome",
582                        if limited.is_none() {
583                            "refused"
584                        } else {
585                            "matched"
586                        }
587                        .to_owned(),
588                    ),
589                ],
590            ),
591            refusal("a", "g", "flags"),
592            refusal(r"\bword", "", "word-boundary"),
593            refusal("\\", "", "trailing-escape"),
594            refusal("*", "", "quantifier-without-atom"),
595        ];
596        let scenario = ScenarioSpec::new(
597            Symbol::qualified("javascript-regexp-characterization", "current/v1"),
598            Symbol::qualified("javascript-regexp-characterization", "shared-text-vm/v1"),
599        )
600        .with_limits(ScenarioLimits::new(0, cases.len()))
601        .observing(ScenarioObservationLane::ValueOrFailure);
602        let capture = CharacterizationCapture::new(
603            Symbol::qualified("javascript-regexp-characterization", "dialect-cases/v1"),
604            CanonicalObservation {
605                outcome: Some(CanonicalOutcome::Success(Datum::Vector(cases))),
606                events: BoundedLane::Absent,
607                receipts: BoundedLane::Absent,
608                browse: BoundedLane::Absent,
609            },
610        );
611        let mut cx = Cx::new(Arc::new(NoopEvalPolicy), Arc::new(DefaultFactory));
612        let first = publish_characterization_capture(&mut cx, &scenario, &capture).unwrap();
613        let replay = publish_characterization_capture(&mut cx, &scenario, &capture).unwrap();
614        assert!(matches!(first, Ref::Content(_)));
615        assert_eq!(first, replay);
616    }
617
618    #[test]
619    fn public_gap_data_is_frozen_clause_for_clause() {
620        let clauses = javascript_regexp_gaps()
621            .iter()
622            .copied()
623            .map(gap_name)
624            .collect::<Vec<_>>();
625        assert_eq!(
626            clauses,
627            [
628                "flags",
629                "backreferences",
630                "lookaround",
631                "unicode-properties",
632                "word-boundary",
633            ]
634        );
635    }
636}
sim_lib_lang_javascript/regexp.rs

sim_lib_lang_javascript/
regexp.rs
