metrale_grammar/fsm/builder/
regex_parse.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// Regex-parser stack helpers — group-close handling and the final
4// stack drain. Split out of `regex.rs` to keep each file under the
5// 250-line cap. Port of the `)`-handling and post-loop logic in
6// `RegexFSMBuilder::Build` from `cpp/fsm_builder.cc`.
7
8use super::regex::StackItem;
9use super::regex_ir::{RegexIr, RegexState};
10
11/// Handle a `)` — pop until the matching `(`, build a `Bracket` or
12/// `Union` node, and push it back.
13pub(crate) fn parse_group_close(stack: &mut Vec<StackItem>) -> Result<(), String> {
14    let mut popped: Vec<StackItem> = Vec::new();
15    let mut paired = false;
16    let mut unioned = false;
17    while let Some(item) = stack.pop() {
18        match item {
19            StackItem::Ctrl(b'(') => {
20                paired = true;
21                break;
22            }
23            StackItem::Ctrl(b'|') => {
24                unioned = true;
25                popped.push(StackItem::Ctrl(b'|'));
26            }
27            other => popped.push(other),
28        }
29    }
30    if !paired {
31        return Err("Invalid regex: no paired bracket!".to_string());
32    }
33    if popped.is_empty() {
34        return Ok(());
35    }
36    // `popped` is in reverse source order; reverse to source order.
37    popped.reverse();
38    if !unioned {
39        let states: Vec<RegexState> = popped
40            .into_iter()
41            .map(|it| match it {
42                StackItem::State(s) => Ok(s),
43                _ => Err("Invalid regex: no paired bracket!".to_string()),
44            })
45            .collect::<Result<_, _>>()?;
46        stack.push(StackItem::State(RegexState::Bracket { states }));
47    } else {
48        let mut union_states: Vec<RegexState> = Vec::new();
49        let mut bracket: Vec<RegexState> = Vec::new();
50        for it in popped {
51            match it {
52                StackItem::Ctrl(b'|') => {
53                    union_states.push(RegexState::Bracket {
54                        states: std::mem::take(&mut bracket),
55                    });
56                }
57                StackItem::State(s) => bracket.push(s),
58                _ => return Err("Invalid regex: no paired bracket!".to_string()),
59            }
60        }
61        union_states.push(RegexState::Bracket { states: bracket });
62        stack.push(StackItem::State(RegexState::Union {
63            states: union_states,
64        }));
65    }
66    Ok(())
67}
68
69/// Drain the parse stack into a finished [`RegexIr`].
70pub(crate) fn finalize_ir(stack: Vec<StackItem>) -> Result<RegexIr, String> {
71    let mut ir = RegexIr::default();
72    let mut res_states: Vec<RegexState> = Vec::new();
73    let mut union_list: Vec<Vec<RegexState>> = Vec::new();
74    let mut unioned = false;
75
76    // The stack is processed top-to-bottom (LIFO), as in the C++.
77    for item in stack.into_iter().rev() {
78        match item {
79            StackItem::Ctrl(b'|') => {
80                union_list.push(std::mem::take(&mut res_states));
81                unioned = true;
82            }
83            StackItem::Ctrl(_) => {
84                return Err("Invalid regex: no paired!".to_string());
85            }
86            StackItem::State(s) => res_states.push(s),
87        }
88    }
89
90    if !unioned {
91        // res_states is in reverse source order — reverse it.
92        for s in res_states.into_iter().rev() {
93            ir.states.push(s);
94        }
95    } else {
96        union_list.push(res_states);
97        let mut union_state: Vec<RegexState> = Vec::new();
98        for branch in union_list {
99            let mut bracket: Vec<RegexState> = Vec::new();
100            for s in branch.into_iter().rev() {
101                bracket.push(s);
102            }
103            union_state.push(RegexState::Bracket { states: bracket });
104        }
105        ir.states.push(RegexState::Union {
106            states: union_state,
107        });
108    }
109    Ok(ir)
110}
metrale_grammar/fsm/builder/regex_parse.rs

metrale_grammar/fsm/builder/
regex_parse.rs
