metrale_grammar/fsm/builder/
regex.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// RegexFsmBuilder — parses a regex string into a `RegexIr` and builds the
4// NFA. Port of `RegexFSMBuilder::Build` (+ `RegexIR::CheckRepeat`) from
5// `cpp/fsm_builder.cc`.
6//
7// The parser is a single left-to-right pass over the regex with an
8// explicit stack. Stack entries are either a finished IR node or a raw
9// control char (`(` or `|`).
10
11use crate::fsm::with_start_end::FsmWithStartEnd;
12
13use super::regex_ir::{REPEAT_NO_UPPER_BOUND, RegexIr, RegexState, RegexSymbol};
14use super::regex_parse::{finalize_ir, parse_group_close};
15
16/// A stack entry: a finished IR node, or a raw `(` / `|` control char.
17#[derive(Debug, Clone)]
18pub(crate) enum StackItem {
19    State(RegexState),
20    Ctrl(u8),
21}
22
23/// Parse `regex` and build its NFA.
24pub fn build_regex(regex: &str) -> Result<FsmWithStartEnd, String> {
25    let ir = parse_to_ir(regex)?;
26    ir.build()
27}
28
29/// Parse `{n}` / `{n,}` / `{n,m}` starting at `start` (which must point
30/// at `{`). On success returns `(lower, upper, index-of-'}')`.
31fn check_repeat(regex: &[u8], mut start: usize) -> Result<(i32, i32, usize), String> {
32    if regex[start] != b'{' {
33        return Err("Invalid repeat format1".to_string());
34    }
35    start += 1;
36    let mut lower = 0i32;
37    let mut upper = REPEAT_NO_UPPER_BOUND;
38    let skip_spaces = |s: &mut usize| {
39        while *s < regex.len() && regex[*s] == b' ' {
40            *s += 1;
41        }
42    };
43    skip_spaces(&mut start);
44    let mut num = String::new();
45    while start < regex.len() && regex[start].is_ascii_digit() {
46        num.push(regex[start] as char);
47        start += 1;
48    }
49    if num.is_empty() {
50        return Err("Invalid repeat format2".to_string());
51    }
52    lower = num.parse().unwrap_or(lower);
53    skip_spaces(&mut start);
54    if start >= regex.len() {
55        return Err("Invalid repeat format5".to_string());
56    }
57    if regex[start] == b'}' {
58        return Ok((lower, lower, start));
59    }
60    if regex[start] != b',' {
61        return Err("Invalid repeat format3".to_string());
62    }
63    start += 1;
64    skip_spaces(&mut start);
65    if start < regex.len() && regex[start] == b'}' {
66        return Ok((lower, upper, start));
67    }
68    num.clear();
69    while start < regex.len() && regex[start].is_ascii_digit() {
70        num.push(regex[start] as char);
71        start += 1;
72    }
73    if num.is_empty() {
74        return Err("Invalid repeat format4".to_string());
75    }
76    upper = num.parse().unwrap_or(upper);
77    skip_spaces(&mut start);
78    if start >= regex.len() || regex[start] != b'}' {
79        return Err("Invalid repeat format5".to_string());
80    }
81    Ok((lower, upper, start))
82}
83
84/// Parse the regex string into a [`RegexIr`].
85fn parse_to_ir(regex: &str) -> Result<RegexIr, String> {
86    let bytes = regex.as_bytes();
87    let mut stack: Vec<StackItem> = Vec::new();
88    let mut left_bracket: i64 = -1;
89    let n = bytes.len();
90    let mut i = 0usize;
91
92    while i < n {
93        let c = bytes[i];
94        // Anchors `^` (at start) / `$` (at end) are ignored.
95        if i == 0 && c == b'^' {
96            i += 1;
97            continue;
98        }
99        if i == n - 1 && c == b'$' {
100            i += 1;
101            continue;
102        }
103        // Character class `[...]`.
104        if c == b'[' {
105            if left_bracket != -1 {
106                return Err("Nested middle bracket!".to_string());
107            }
108            left_bracket = i as i64;
109            i += 1;
110            continue;
111        }
112        if c == b']' {
113            if left_bracket == -1 {
114                return Err("Invalid middle bracket!".to_string());
115            }
116            let lb = left_bracket as usize;
117            stack.push(StackItem::State(RegexState::Leaf {
118                regex: bytes[lb..=i].to_vec(),
119            }));
120            left_bracket = -1;
121            i += 1;
122            continue;
123        }
124        if left_bracket != -1 {
125            // inside `[...]`, skip escaped bytes
126            if c == b'\\' {
127                i += 1;
128            }
129            i += 1;
130            continue;
131        }
132        // Quantifiers `+ * ?`.
133        if c == b'+' || c == b'*' || c == b'?' {
134            let top = stack.pop();
135            let child = match top {
136                Some(StackItem::State(s)) => s,
137                _ => return Err("Invalid regex: no state before operator!".to_string()),
138            };
139            let symbol = match c {
140                b'+' => RegexSymbol::Plus,
141                b'*' => RegexSymbol::Star,
142                _ => RegexSymbol::Optional,
143            };
144            stack.push(StackItem::State(RegexState::Symbol {
145                symbol,
146                state: Box::new(child),
147            }));
148            i += 1;
149            continue;
150        }
151        // Group open / alternation.
152        if c == b'(' || c == b'|' {
153            stack.push(StackItem::Ctrl(c));
154            // skip `(?:` and `(?!` / `(?=` prefixes
155            if c == b'('
156                && i + 2 < n
157                && bytes[i + 1] == b'?'
158                && matches!(bytes[i + 2], b':' | b'!' | b'=')
159            {
160                i += 3;
161                continue;
162            }
163            i += 1;
164            continue;
165        }
166        // Group close.
167        if c == b')' {
168            parse_group_close(&mut stack)?;
169            i += 1;
170            continue;
171        }
172        // Repeat `{...}`.
173        if c == b'{' {
174            let top = stack.pop();
175            let child = match top {
176                Some(StackItem::State(s)) => s,
177                _ => return Err("Invalid regex: no state before repeat!".to_string()),
178            };
179            let (lower, upper, end) = check_repeat(bytes, i)?;
180            stack.push(StackItem::State(RegexState::Repeat {
181                states: vec![child],
182                lower_bound: lower,
183                upper_bound: upper,
184            }));
185            i = end + 1;
186            continue;
187        }
188        // Plain literal byte (possibly escaped). Sliced on `bytes` so a
189        // multi-byte UTF-8 codepoint splits cleanly into per-byte leaves.
190        let leaf_regex = if c != b'\\' {
191            let s = bytes[i..i + 1].to_vec();
192            i += 1;
193            s
194        } else {
195            let s = bytes[i..(i + 2).min(n)].to_vec();
196            i += 2;
197            s
198        };
199        stack.push(StackItem::State(RegexState::Leaf { regex: leaf_regex }));
200    }
201
202    finalize_ir(stack)
203}
204
205// Stack helpers (`parse_group_close`, `finalize_ir`) live in
206// `regex_parse.rs` — imported above via `use super::regex_parse::*`.
207
208#[cfg(test)]
209#[path = "regex_tests.rs"]
210mod tests;
metrale_grammar/fsm/builder/regex.rs

metrale_grammar/fsm/builder/
regex.rs
