Skip to main content

vibe/stdlib_v2/text_and_collections/
linear_regex.rs

1//! Stateless Linear-Time $O(n)$ Non-Backtracking Thompson NFA Regular Expression Engine (`regex.*`).
2//!
3//! Eliminates JavaScript's stateful `RegExp.prototype.lastIndex` race conditions, catastrophic
4//! backtracking (ReDoS on patterns like `(a+)+b`), and `$&`/`$'` replacement string footguns.
5
6use std::collections::BTreeMap;
7
8use crate::error::{DiagCode, Diagnostic};
9use crate::span::Span;
10use crate::value::Value;
11
12use super::extract_str;
13
14#[derive(Clone, Debug)]
15enum ClassAtom {
16    Single(char),
17    Range(char, char),
18    Digit,
19    Word,
20    Space,
21}
22
23impl ClassAtom {
24    fn matches(&self, c: char) -> bool {
25        match self {
26            ClassAtom::Single(target) => c == *target,
27            ClassAtom::Range(lo, hi) => c >= *lo && c <= *hi,
28            ClassAtom::Digit => c.is_ascii_digit(),
29            ClassAtom::Word => c.is_ascii_alphanumeric() || c == '_',
30            ClassAtom::Space => c.is_whitespace(),
31        }
32    }
33}
34
35#[derive(Clone, Debug)]
36enum CharMatcher {
37    Literal(char),
38    AnyNotNewline,
39    Digit(bool),
40    Word(bool),
41    Space(bool),
42    Class { negated: bool, atoms: Vec<ClassAtom> },
43}
44
45impl CharMatcher {
46    fn matches(&self, c: char) -> bool {
47        match self {
48            CharMatcher::Literal(target) => c == *target,
49            CharMatcher::AnyNotNewline => c != '\n',
50            CharMatcher::Digit(pos) => c.is_ascii_digit() == *pos,
51            CharMatcher::Word(pos) => (c.is_ascii_alphanumeric() || c == '_') == *pos,
52            CharMatcher::Space(pos) => c.is_whitespace() == *pos,
53            CharMatcher::Class { negated, atoms } => {
54                let hit = atoms.iter().any(|a| a.matches(c));
55                if *negated { !hit } else { hit }
56            }
57        }
58    }
59}
60
61#[derive(Clone, Debug)]
62enum RegexAst {
63    Empty,
64    Matcher(CharMatcher),
65    AnchorStart,
66    AnchorEnd,
67    Seq(Vec<RegexAst>),
68    Alt(Box<RegexAst>, Box<RegexAst>),
69    Repeat { inner: Box<RegexAst>, min_one: bool, max_one: bool },
70}
71
72#[derive(Clone, Debug)]
73enum NfaState {
74    Match(CharMatcher, usize),
75    Split(usize, usize),
76    AnchorStart(usize),
77    AnchorEnd(usize),
78    Accept,
79}
80
81#[derive(Clone, Debug)]
82struct CompiledNfa {
83    states: Vec<NfaState>,
84    start: usize,
85}
86
87/// Dispatch `regex.*` bindings.
88pub(crate) fn call_linear_regex(
89    path: &str,
90    args: &[Value],
91    span: Span,
92) -> Result<Option<Value>, Diagnostic> {
93    match path {
94        "regex.compile" => {
95            let pattern = extract_str(args, 0, "regex.compile(pattern)", span)?;
96            let mut rec = BTreeMap::new();
97            rec.insert("pattern".to_string(), Value::String(pattern.clone()));
98            rec.insert("linear_time_guaranteed".to_string(), Value::Bool(true));
99            match compile_nfa(&pattern) {
100                Ok(nfa) => {
101                    rec.insert("valid".to_string(), Value::Bool(true));
102                    rec.insert("state_count".to_string(), Value::I64(nfa.states.len() as i64));
103                }
104                Err(err) => {
105                    rec.insert("valid".to_string(), Value::Bool(false));
106                    rec.insert("state_count".to_string(), Value::I64(0));
107                    rec.insert("error".to_string(), Value::String(err));
108                }
109            }
110            Ok(Some(Value::Record(rec)))
111        }
112        "regex.is_match" => {
113            let pattern = extract_str(args, 0, "regex.is_match(pattern, text)", span)?;
114            let text = extract_str(args, 1, "regex.is_match(pattern, text)", span)?;
115            let nfa = compile_nfa(&pattern)
116                .map_err(|e| Diagnostic::new(DiagCode::E100, span, format!("regex.is_match: {e}")))?;
117            Ok(Some(Value::Bool(nfa_is_match(&nfa, &text))))
118        }
119        "regex.find" => {
120            let pattern = extract_str(args, 0, "regex.find(pattern, text)", span)?;
121            let text = extract_str(args, 1, "regex.find(pattern, text)", span)?;
122            let nfa = compile_nfa(&pattern)
123                .map_err(|e| Diagnostic::new(DiagCode::E100, span, format!("regex.find: {e}")))?;
124            let mut rec = BTreeMap::new();
125            if let Some((b_start, b_end)) = find_first_match(&nfa, &text) {
126                rec.insert("matched".to_string(), Value::Bool(true));
127                rec.insert("text".to_string(), Value::String(text[b_start..b_end].to_string()));
128                rec.insert("start".to_string(), Value::I64(b_start as i64));
129                rec.insert("end".to_string(), Value::I64(b_end as i64));
130            } else {
131                rec.insert("matched".to_string(), Value::Bool(false));
132                rec.insert("text".to_string(), Value::String(String::new()));
133                rec.insert("start".to_string(), Value::I64(-1));
134                rec.insert("end".to_string(), Value::I64(-1));
135            }
136            Ok(Some(Value::Record(rec)))
137        }
138        "regex.find_all" => {
139            let pattern = extract_str(args, 0, "regex.find_all(pattern, text)", span)?;
140            let text = extract_str(args, 1, "regex.find_all(pattern, text)", span)?;
141            let nfa = compile_nfa(&pattern)
142                .map_err(|e| Diagnostic::new(DiagCode::E100, span, format!("regex.find_all: {e}")))?;
143            let matches = find_all_matches(&nfa, &text)
144                .into_iter()
145                .map(|(b_start, b_end)| {
146                    let mut m = BTreeMap::new();
147                    m.insert("text".to_string(), Value::String(text[b_start..b_end].to_string()));
148                    m.insert("start".to_string(), Value::I64(b_start as i64));
149                    m.insert("end".to_string(), Value::I64(b_end as i64));
150                    Value::Record(m)
151                })
152                .collect();
153            Ok(Some(Value::List(matches)))
154        }
155        "regex.replace_all" => {
156            let pattern = extract_str(args, 0, "regex.replace_all(pattern, text, replacement)", span)?;
157            let text = extract_str(args, 1, "regex.replace_all(pattern, text, replacement)", span)?;
158            let rep = extract_str(args, 2, "regex.replace_all(pattern, text, replacement)", span)?;
159            let nfa = compile_nfa(&pattern).map_err(|e| {
160                Diagnostic::new(DiagCode::E100, span, format!("regex.replace_all: {e}"))
161            })?;
162            let spans = find_all_matches(&nfa, &text);
163            if spans.is_empty() {
164                return Ok(Some(Value::String(text)));
165            }
166            let mut out = String::with_capacity(text.len());
167            let mut last = 0;
168            for (s, e) in spans {
169                out.push_str(&text[last..s]);
170                out.push_str(&rep);
171                last = e;
172            }
173            out.push_str(&text[last..]);
174            Ok(Some(Value::String(out)))
175        }
176        _ => Ok(None),
177    }
178}
179
180fn compile_nfa(pattern: &str) -> Result<CompiledNfa, String> {
181    let chars: Vec<char> = pattern.chars().collect();
182    let mut pos = 0;
183    let ast = parse_alt(&chars, &mut pos, false)?;
184    if pos < chars.len() {
185        return Err(format!("unexpected character '{}' at index {pos}", chars[pos]));
186    }
187    let mut states = vec![NfaState::Accept];
188    let start = build_nfa(&ast, 0, &mut states);
189    Ok(CompiledNfa { states, start })
190}
191
192fn parse_alt(chars: &[char], pos: &mut usize, in_group: bool) -> Result<RegexAst, String> {
193    let mut left = parse_seq(chars, pos, in_group)?;
194    while *pos < chars.len() && chars[*pos] == '|' {
195        *pos += 1;
196        let right = parse_seq(chars, pos, in_group)?;
197        left = RegexAst::Alt(Box::new(left), Box::new(right));
198    }
199    Ok(left)
200}
201
202fn parse_seq(chars: &[char], pos: &mut usize, in_group: bool) -> Result<RegexAst, String> {
203    let mut items = Vec::new();
204    while *pos < chars.len() {
205        let c = chars[*pos];
206        if c == '|' || (in_group && c == ')') {
207            break;
208        }
209        if c == ')' {
210            return Err(format!("unmatched ')' at index {}", *pos));
211        }
212        let mut atom = parse_atom(chars, pos)?;
213        while *pos < chars.len() {
214            let (min_one, max_one) = match chars[*pos] {
215                '*' => (false, false),
216                '+' => (true, false),
217                '?' => (false, true),
218                _ => break,
219            };
220            *pos += 1;
221            atom = RegexAst::Repeat { inner: Box::new(atom), min_one, max_one };
222        }
223        items.push(atom);
224    }
225    match items.len() {
226        0 => Ok(RegexAst::Empty),
227        1 => Ok(items.remove(0)),
228        _ => Ok(RegexAst::Seq(items)),
229    }
230}
231
232fn parse_atom(chars: &[char], pos: &mut usize) -> Result<RegexAst, String> {
233    let c = chars[*pos];
234    match c {
235        '*' | '+' | '?' => Err(format!("quantifier '{c}' nothing to repeat at index {}", *pos)),
236        '^' => { *pos += 1; Ok(RegexAst::AnchorStart) }
237        '$' => { *pos += 1; Ok(RegexAst::AnchorEnd) }
238        '.' => { *pos += 1; Ok(RegexAst::Matcher(CharMatcher::AnyNotNewline)) }
239        '(' => {
240            *pos += 1;
241            let inner = parse_alt(chars, pos, true)?;
242            if *pos >= chars.len() || chars[*pos] != ')' {
243                return Err("unclosed group '('".to_string());
244            }
245            *pos += 1;
246            Ok(inner)
247        }
248        '[' => parse_class(chars, pos),
249        '\\' => {
250            *pos += 1;
251            if *pos >= chars.len() {
252                return Err("trailing '\\' in regex pattern".to_string());
253            }
254            let esc = chars[*pos];
255            *pos += 1;
256            let matcher = match esc {
257                'd' => CharMatcher::Digit(true),
258                'D' => CharMatcher::Digit(false),
259                'w' => CharMatcher::Word(true),
260                'W' => CharMatcher::Word(false),
261                's' => CharMatcher::Space(true),
262                'S' => CharMatcher::Space(false),
263                'n' => CharMatcher::Literal('\n'),
264                'r' => CharMatcher::Literal('\r'),
265                't' => CharMatcher::Literal('\t'),
266                other => CharMatcher::Literal(other),
267            };
268            Ok(RegexAst::Matcher(matcher))
269        }
270        other => { *pos += 1; Ok(RegexAst::Matcher(CharMatcher::Literal(other))) }
271    }
272}
273
274fn parse_class(chars: &[char], pos: &mut usize) -> Result<RegexAst, String> {
275    *pos += 1;
276    let negated = if *pos < chars.len() && chars[*pos] == '^' { *pos += 1; true } else { false };
277    let mut atoms = Vec::new();
278    while *pos < chars.len() && chars[*pos] != ']' {
279        let ch = if chars[*pos] == '\\' {
280            *pos += 1;
281            if *pos >= chars.len() {
282                return Err("unclosed character class '['".to_string());
283            }
284            let esc = chars[*pos];
285            *pos += 1;
286            match esc {
287                'd' => { atoms.push(ClassAtom::Digit); continue; }
288                'w' => { atoms.push(ClassAtom::Word); continue; }
289                's' => { atoms.push(ClassAtom::Space); continue; }
290                'n' => '\n',
291                'r' => '\r',
292                't' => '\t',
293                other => other,
294            }
295        } else {
296            let c = chars[*pos];
297            *pos += 1;
298            c
299        };
300        if *pos + 1 < chars.len() && chars[*pos] == '-' && chars[*pos + 1] != ']' {
301            *pos += 1;
302            let hi = chars[*pos];
303            *pos += 1;
304            atoms.push(ClassAtom::Range(ch, hi));
305        } else {
306            atoms.push(ClassAtom::Single(ch));
307        }
308    }
309    if *pos >= chars.len() || chars[*pos] != ']' {
310        return Err("unclosed character class '['".to_string());
311    }
312    *pos += 1;
313    Ok(RegexAst::Matcher(CharMatcher::Class { negated, atoms }))
314}
315
316fn build_nfa(ast: &RegexAst, next: usize, states: &mut Vec<NfaState>) -> usize {
317    match ast {
318        RegexAst::Empty => next,
319        RegexAst::Matcher(m) => {
320            let id = states.len();
321            states.push(NfaState::Match(m.clone(), next));
322            id
323        }
324        RegexAst::AnchorStart => {
325            let id = states.len();
326            states.push(NfaState::AnchorStart(next));
327            id
328        }
329        RegexAst::AnchorEnd => {
330            let id = states.len();
331            states.push(NfaState::AnchorEnd(next));
332            id
333        }
334        RegexAst::Seq(items) => items.iter().rev().fold(next, |cur, item| build_nfa(item, cur, states)),
335        RegexAst::Alt(a, b) => {
336            let s_a = build_nfa(a, next, states);
337            let s_b = build_nfa(b, next, states);
338            let id = states.len();
339            states.push(NfaState::Split(s_a, s_b));
340            id
341        }
342        RegexAst::Repeat { inner, min_one: false, max_one: true } => {
343            let s_in = build_nfa(inner, next, states);
344            let id = states.len();
345            states.push(NfaState::Split(s_in, next));
346            id
347        }
348        RegexAst::Repeat { inner, min_one, max_one: false } => {
349            let split_id = states.len();
350            states.push(NfaState::Accept);
351            let s_in = build_nfa(inner, split_id, states);
352            states[split_id] = NfaState::Split(s_in, next);
353            if *min_one { s_in } else { split_id }
354        }
355        RegexAst::Repeat { inner, min_one: true, max_one: true } => build_nfa(inner, next, states),
356    }
357}
358
359fn add_epsilon_state(
360    nfa: &CompiledNfa,
361    state: usize,
362    pos: usize,
363    total_len: usize,
364    active: &mut Vec<usize>,
365    visited: &mut [bool],
366) {
367    if visited[state] {
368        return;
369    }
370    visited[state] = true;
371    match &nfa.states[state] {
372        NfaState::Split(a, b) => {
373            add_epsilon_state(nfa, *a, pos, total_len, active, visited);
374            add_epsilon_state(nfa, *b, pos, total_len, active, visited);
375        }
376        NfaState::AnchorStart(out) if pos == 0 => {
377            add_epsilon_state(nfa, *out, pos, total_len, active, visited);
378        }
379        NfaState::AnchorEnd(out) if pos == total_len => {
380            add_epsilon_state(nfa, *out, pos, total_len, active, visited);
381        }
382        NfaState::AnchorStart(_) | NfaState::AnchorEnd(_) => {}
383        _ => active.push(state),
384    }
385}
386
387fn nfa_is_match(nfa: &CompiledNfa, text: &str) -> bool {
388    let chars: Vec<(usize, char)> = text.char_indices().collect();
389    let total = chars.len();
390    let mut active = Vec::new();
391    let mut next_active = Vec::new();
392    let mut visited = vec![false; nfa.states.len()];
393
394    for i in 0..=total {
395        visited.fill(false);
396        for &s in &active {
397            add_epsilon_state(nfa, s, i, total, &mut next_active, &mut visited);
398        }
399        add_epsilon_state(nfa, nfa.start, i, total, &mut next_active, &mut visited);
400        std::mem::swap(&mut active, &mut next_active);
401        next_active.clear();
402
403        if active.iter().any(|&s| matches!(nfa.states[s], NfaState::Accept)) {
404            return true;
405        }
406        if i == total {
407            break;
408        }
409        let ch = chars[i].1;
410        for &s in &active {
411            if let NfaState::Match(ref m, out) = nfa.states[s] {
412                if m.matches(ch) {
413                    next_active.push(out);
414                }
415            }
416        }
417        std::mem::swap(&mut active, &mut next_active);
418        next_active.clear();
419    }
420    false
421}
422
423fn find_first_match(nfa: &CompiledNfa, text: &str) -> Option<(usize, usize)> {
424    let chars: Vec<(usize, char)> = text.char_indices().collect();
425    for start_idx in 0..=chars.len() {
426        if let Some(end_idx) = match_from_index(nfa, &chars, start_idx) {
427            let b_start = chars.get(start_idx).map(|p| p.0).unwrap_or(text.len());
428            let b_end = chars.get(end_idx).map(|p| p.0).unwrap_or(text.len());
429            return Some((b_start, b_end));
430        }
431    }
432    None
433}
434
435fn find_all_matches(nfa: &CompiledNfa, text: &str) -> Vec<(usize, usize)> {
436    let chars: Vec<(usize, char)> = text.char_indices().collect();
437    let mut out = Vec::new();
438    let mut idx = 0;
439    while idx <= chars.len() {
440        if let Some(end_idx) = match_from_index(nfa, &chars, idx) {
441            let b_start = chars.get(idx).map(|p| p.0).unwrap_or(text.len());
442            let b_end = chars.get(end_idx).map(|p| p.0).unwrap_or(text.len());
443            out.push((b_start, b_end));
444            idx = if end_idx > idx { end_idx } else { idx + 1 };
445        } else {
446            idx += 1;
447        }
448    }
449    out
450}
451
452fn match_from_index(nfa: &CompiledNfa, chars: &[(usize, char)], start_idx: usize) -> Option<usize> {
453    let total = chars.len();
454    let mut active = Vec::new();
455    let mut next_active = Vec::new();
456    let mut visited = vec![false; nfa.states.len()];
457
458    add_epsilon_state(nfa, nfa.start, start_idx, total, &mut active, &mut visited);
459    let mut longest_end = active
460        .iter()
461        .any(|&s| matches!(nfa.states[s], NfaState::Accept))
462        .then_some(start_idx);
463
464    for i in start_idx..total {
465        if active.is_empty() {
466            break;
467        }
468        let ch = chars[i].1;
469        visited.fill(false);
470        for &s in &active {
471            if let NfaState::Match(ref m, out) = nfa.states[s] {
472                if m.matches(ch) {
473                    add_epsilon_state(nfa, out, i + 1, total, &mut next_active, &mut visited);
474                }
475            }
476        }
477        std::mem::swap(&mut active, &mut next_active);
478        next_active.clear();
479        if active.iter().any(|&s| matches!(nfa.states[s], NfaState::Accept)) {
480            longest_end = Some(i + 1);
481        }
482    }
483    longest_end
484}