metrale_grammar/fsm/builder/
regex_ir.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// RegexIr — the intermediate representation a regex string is parsed
4// into, plus its NFA construction (`Build` / `visit`). Port of `RegexIR`
5// from `cpp/fsm_builder.cc`.
6//
7// The C++ uses `std::variant`; Rust uses a plain enum. Leaf FSMs are
8// built directly from regex fragments via `build_leaf_fsm`.
9
10use crate::fsm::fsm::Fsm;
11use crate::fsm::with_start_end::FsmWithStartEnd;
12
13/// Sentinel for an unbounded repeat upper bound (`{n,}`).
14pub const REPEAT_NO_UPPER_BOUND: i32 = -1;
15
16/// A postfix-style regex quantifier.
17#[derive(Debug, Clone, Copy, PartialEq, Eq)]
18pub enum RegexSymbol {
19    /// `*`
20    Star,
21    /// `+`
22    Plus,
23    /// `?`
24    Optional,
25}
26
27/// A node of the regex IR tree.
28#[derive(Debug, Clone)]
29pub enum RegexState {
30    /// A literal fragment or character class, e.g. `"a"` or `"[a-z]"`.
31    /// Stored as raw bytes — the regex grammar is byte-wise, so a
32    /// fragment may split a UTF-8 codepoint across multiple `Leaf`s.
33    Leaf { regex: Vec<u8> },
34    /// A quantifier applied to a single child.
35    Symbol {
36        symbol: RegexSymbol,
37        state: Box<RegexState>,
38    },
39    /// An alternation of branches.
40    Union { states: Vec<RegexState> },
41    /// A parenthesized concatenation.
42    Bracket { states: Vec<RegexState> },
43    /// A counted repetition `{lower,upper}`.
44    Repeat {
45        states: Vec<RegexState>,
46        lower_bound: i32,
47        upper_bound: i32,
48    },
49}
50
51/// The whole parsed regex: a sequence of top-level states.
52#[derive(Debug, Default, Clone)]
53pub struct RegexIr {
54    /// Top-level concatenation of states.
55    pub states: Vec<RegexState>,
56}
57
58impl RegexIr {
59    /// Build the NFA for the entire IR.
60    pub fn build(&self) -> Result<FsmWithStartEnd, String> {
61        if self.states.is_empty() {
62            // The empty regex accepts only the empty string.
63            let empty = Fsm::with_states(1);
64            return Ok(FsmWithStartEnd::new(empty, 0, vec![true], false));
65        }
66        let mut fsm_list: Vec<FsmWithStartEnd> = Vec::new();
67        for state in &self.states {
68            fsm_list.push(visit(state)?);
69        }
70        if fsm_list.len() > 1 {
71            Ok(FsmWithStartEnd::concat(&fsm_list))
72        } else {
73            Ok(fsm_list.into_iter().next().unwrap())
74        }
75    }
76}
77
78/// Construct the NFA for a single IR node.
79pub fn visit(state: &RegexState) -> Result<FsmWithStartEnd, String> {
80    match state {
81        RegexState::Leaf { regex } => Ok(build_leaf_fsm(regex)),
82        // (see build_leaf_fsm — takes a &[u8])
83        RegexState::Symbol { symbol, state } => {
84            let child = visit(state)?;
85            Ok(match symbol {
86                RegexSymbol::Plus => child.plus(),
87                RegexSymbol::Star => child.star(),
88                RegexSymbol::Optional => child.optional(),
89            })
90        }
91        RegexState::Union { states } => {
92            let mut list = Vec::new();
93            for child in states {
94                list.push(visit(child)?);
95            }
96            if list.len() <= 1 {
97                return Err("Invalid union".to_string());
98            }
99            Ok(FsmWithStartEnd::union(&list))
100        }
101        RegexState::Bracket { states } => {
102            let mut list = Vec::new();
103            for child in states {
104                list.push(visit(child)?);
105            }
106            if list.is_empty() {
107                return Err("Invalid bracket".to_string());
108            }
109            Ok(FsmWithStartEnd::concat(&list))
110        }
111        RegexState::Repeat {
112            states,
113            lower_bound,
114            upper_bound,
115        } => {
116            if states.len() != 1 {
117                return Err("Invalid repeat".to_string());
118            }
119            visit_repeat(&states[0], *lower_bound, *upper_bound)
120        }
121    }
122}
123
124/// NFA construction for a `{lower,upper}` repetition.
125fn visit_repeat(
126    child_state: &RegexState,
127    lower_bound: i32,
128    upper_bound: i32,
129) -> Result<FsmWithStartEnd, String> {
130    let child = visit(child_state)?;
131    let mut result = child.copy();
132    let mut new_ends: Vec<usize> = Vec::new();
133
134    if lower_bound == 1 {
135        for end in 0..result.num_states() {
136            if result.is_end_state(end) {
137                new_ends.push(end);
138            }
139        }
140    }
141
142    if upper_bound == REPEAT_NO_UPPER_BOUND {
143        // {n,}: repeat n times, then loop back to the n-th copy's start.
144        let mut i = 2;
145        while i < lower_bound {
146            result = FsmWithStartEnd::concat(&[result.clone(), child.clone()]);
147            i += 1;
148        }
149        let mut end_of_lower = -1i64;
150        for end in 0..result.num_states() {
151            if result.is_end_state(end) {
152                end_of_lower = end as i64;
153                break;
154            }
155        }
156        debug_assert!(end_of_lower != -1, "No end state in lower-bound FSM.");
157        result = FsmWithStartEnd::concat(&[result, child]);
158        for end in 0..result.num_states() {
159            if result.is_end_state(end) {
160                result
161                    .fsm_mut()
162                    .add_epsilon_edge(end, end_of_lower as usize);
163            }
164        }
165        return Ok(result);
166    }
167
168    // {n,m} or {n}
169    let mut i = 2;
170    while i <= upper_bound {
171        result = FsmWithStartEnd::concat(&[result, child.clone()]);
172        if i >= lower_bound {
173            for end in 0..result.num_states() {
174                if result.is_end_state(end) {
175                    new_ends.push(end);
176                }
177            }
178        }
179        i += 1;
180    }
181    for end in new_ends {
182        result.add_end_state(end);
183    }
184    Ok(result)
185}
186
187// Leaf-FSM construction lives in `regex_leaf.rs`; re-exported here
188// so existing call sites (`super::regex_ir::build_leaf_fsm`) keep
189// working.
190pub use super::regex_leaf::{build_leaf_fsm, handle_escapes};
191
192#[cfg(test)]
193#[path = "regex_ir_tests.rs"]
194mod tests;
metrale_grammar/fsm/builder/regex_ir.rs

metrale_grammar/fsm/builder/
regex_ir.rs
