metrale_grammar/fsm/
fsm_ops.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// Regular-operation constructors on FsmWithStartEnd — Star, Plus,
4// Optional, Union, Concat. Split out of `with_start_end.rs` to keep
5// each file under the 250-line cap. Port of the corresponding
6// `FSMWithStartEnd` methods from `cpp/fsm.cc`.
7
8use super::fsm::Fsm;
9use super::with_start_end::FsmWithStartEnd;
10
11impl FsmWithStartEnd {
12    /// `self*` — Kleene star.
13    pub fn star(&self) -> FsmWithStartEnd {
14        let mut fsm = self.fsm.clone();
15        let new_start = fsm.add_state();
16        for end in 0..self.num_states() {
17            if self.is_end_state(end) {
18                fsm.add_epsilon_edge(end, new_start);
19            }
20        }
21        fsm.add_epsilon_edge(new_start, self.start);
22        let mut is_end = vec![false; self.num_states() + 1];
23        is_end[new_start] = true;
24        FsmWithStartEnd::new(fsm, new_start, is_end, false)
25    }
26
27    /// `self+` — one or more.
28    pub fn plus(&self) -> FsmWithStartEnd {
29        let mut fsm = self.fsm.clone();
30        for end in 0..self.num_states() {
31            if self.is_end_state(end) {
32                fsm.add_epsilon_edge(end, self.start);
33            }
34        }
35        FsmWithStartEnd::new(fsm, self.start, self.ends.clone(), false)
36    }
37
38    /// `self?` — optional.
39    pub fn optional(&self) -> FsmWithStartEnd {
40        let mut fsm = self.fsm.clone();
41        for end in 0..self.num_states() {
42            if self.is_end_state(end) {
43                fsm.add_epsilon_edge(self.start, end);
44                break;
45            }
46        }
47        FsmWithStartEnd::new(fsm, self.start, self.ends.clone(), false)
48    }
49
50    /// Parallel union of several FSMs — accepts any of their languages.
51    pub fn union(fsms: &[FsmWithStartEnd]) -> FsmWithStartEnd {
52        if fsms.len() == 1 {
53            return fsms[0].clone();
54        }
55        debug_assert!(fsms.len() > 1, "Union of 0 FSMs is not allowed.");
56        let mut fsm = Fsm::with_states(1);
57        let start = 0;
58        let mut ends = vec![false];
59        for sub in fsms {
60            let mapping = fsm.add_fsm(&sub.fsm);
61            fsm.add_epsilon_edge(start, mapping[sub.start]);
62            for state in 0..sub.num_states() {
63                ends.push(sub.is_end_state(state));
64            }
65        }
66        FsmWithStartEnd::new(fsm, start, ends, false)
67    }
68
69    /// Sequential concatenation of several FSMs.
70    pub fn concat(fsms: &[FsmWithStartEnd]) -> FsmWithStartEnd {
71        if fsms.len() == 1 {
72            return fsms[0].clone();
73        }
74        debug_assert!(fsms.len() > 1, "Concatenation of 0 FSMs is not allowed.");
75        let mut fsm = Fsm::with_states(0);
76        let mut start = 0;
77        let mut ends: Vec<bool> = Vec::new();
78        let mut previous_ends: Vec<usize> = Vec::new();
79        let last = fsms.len() - 1;
80        for (i, sub) in fsms.iter().enumerate() {
81            let mapping = fsm.add_fsm(&sub.fsm);
82            if i == 0 {
83                start = mapping[sub.start];
84            } else {
85                let this_start = mapping[sub.start];
86                for &end in &previous_ends {
87                    fsm.add_epsilon_edge(end, this_start);
88                }
89            }
90            if i == last {
91                ends = vec![false; fsm.num_states()];
92                for end in 0..sub.num_states() {
93                    if sub.is_end_state(end) {
94                        ends[mapping[end]] = true;
95                    }
96                }
97            } else {
98                previous_ends.clear();
99                for end in 0..sub.num_states() {
100                    if sub.is_end_state(end) {
101                        previous_ends.push(mapping[end]);
102                    }
103                }
104            }
105        }
106        FsmWithStartEnd::new(fsm, start, ends, false)
107    }
108}
metrale_grammar/fsm/fsm_ops.rs

metrale_grammar/fsm/
fsm_ops.rs
