Skip to main content

voce_validator/passes/
state_machine.rs

1//! State machine validation pass.
2//!
3//! Checks that StateMachines have valid structure: initial state exists,
4//! all states are reachable, no deadlocks, transitions reference valid states.
5
6use std::collections::{HashSet, VecDeque};
7
8use crate::errors::{Diagnostic, Severity, ValidationResult};
9use crate::index::NodeIndex;
10use crate::ir::{ChildNode, StateMachine, VoceIr};
11use crate::passes::ValidationPass;
12
13pub struct StateMachinePass;
14
15impl ValidationPass for StateMachinePass {
16    fn name(&self) -> &'static str {
17        "state-machine"
18    }
19
20    fn run(&self, ir: &VoceIr, _index: &NodeIndex, result: &mut ValidationResult) {
21        let root = match &ir.root {
22            Some(r) => r,
23            None => return,
24        };
25
26        if let Some(ref children) = root.children {
27            self.find_and_check(children, "/root/children", result);
28        }
29    }
30}
31
32impl StateMachinePass {
33    fn find_and_check(
34        &self,
35        children: &[ChildNode],
36        parent_path: &str,
37        result: &mut ValidationResult,
38    ) {
39        for (i, child) in children.iter().enumerate() {
40            let path = format!("{parent_path}/{i}");
41
42            if child.type_name() == "StateMachine" {
43                if let Some(sm) = child.as_type::<StateMachine>() {
44                    self.check_state_machine(&sm, &path, result);
45                }
46            }
47
48            // Recurse
49            if let Some(grandchildren) = child.children() {
50                self.find_and_check(&grandchildren, &format!("{path}/children"), result);
51            }
52        }
53    }
54
55    fn check_state_machine(&self, sm: &StateMachine, path: &str, result: &mut ValidationResult) {
56        let states = match &sm.states {
57            Some(s) if !s.is_empty() => s,
58            _ => {
59                // STA001: Must have at least one state
60                result.diagnostics.push(Diagnostic {
61                    severity: Severity::Error,
62                    code: "STA001".to_string(),
63                    message: "StateMachine has no states".to_string(),
64                    node_path: path.to_string(),
65                    pass: self.name().to_string(),
66                    hint: None,
67                });
68                return;
69            }
70        };
71
72        let transitions = sm.transitions.as_deref().unwrap_or(&[]);
73        let state_names: HashSet<&str> = states.iter().filter_map(|s| s.name.as_deref()).collect();
74
75        // STA002: Must have exactly one initial state
76        let initial_states: Vec<&str> = states
77            .iter()
78            .filter(|s| s.initial)
79            .filter_map(|s| s.name.as_deref())
80            .collect();
81
82        if initial_states.is_empty() {
83            result.diagnostics.push(Diagnostic {
84                severity: Severity::Error,
85                code: "STA002".to_string(),
86                message: "StateMachine has no initial state (set initial: true on one state)"
87                    .to_string(),
88                node_path: path.to_string(),
89                pass: self.name().to_string(),
90                hint: None,
91            });
92            return;
93        }
94
95        if initial_states.len() > 1 {
96            result.diagnostics.push(Diagnostic {
97                severity: Severity::Error,
98                code: "STA002".to_string(),
99                message: format!(
100                    "StateMachine has {} initial states (only one allowed): {}",
101                    initial_states.len(),
102                    initial_states.join(", ")
103                ),
104                node_path: path.to_string(),
105                pass: self.name().to_string(),
106                hint: None,
107            });
108        }
109
110        // Check transitions reference valid states
111        for (j, t) in transitions.iter().enumerate() {
112            let t_path = format!("{path}/transitions/{j}");
113
114            if let Some(ref from) = t.from {
115                if !state_names.contains(from.as_str()) {
116                    // REF004: Transition `from` references non-existent state
117                    result.diagnostics.push(Diagnostic {
118                        severity: Severity::Error,
119                        code: "REF004".to_string(),
120                        message: format!(
121                            "Transition from state \"{from}\" does not exist in this StateMachine"
122                        ),
123                        node_path: t_path.clone(),
124                        pass: self.name().to_string(),
125                        hint: None,
126                    });
127                }
128            }
129
130            if let Some(ref to) = t.to {
131                if !state_names.contains(to.as_str()) {
132                    result.diagnostics.push(Diagnostic {
133                        severity: Severity::Error,
134                        code: "REF004".to_string(),
135                        message: format!(
136                            "Transition to state \"{to}\" does not exist in this StateMachine"
137                        ),
138                        node_path: t_path,
139                        pass: self.name().to_string(),
140                        hint: None,
141                    });
142                }
143            }
144        }
145
146        // STA003: All states must be reachable from initial
147        if let Some(initial) = initial_states.first() {
148            let reachable = self.find_reachable(initial, transitions);
149            for state in states {
150                if let Some(ref name) = state.name {
151                    if !reachable.contains(name.as_str()) {
152                        result.diagnostics.push(Diagnostic {
153                            severity: Severity::Warning,
154                            code: "STA003".to_string(),
155                            message: format!(
156                                "State \"{name}\" is not reachable from initial state \"{initial}\""
157                            ),
158                            node_path: path.to_string(),
159                            pass: self.name().to_string(),
160                            hint: None,
161                        });
162                    }
163                }
164            }
165        }
166
167        // STA004: Duplicate transitions (same from + event)
168        let mut seen: HashSet<(String, String)> = HashSet::new();
169        for (j, t) in transitions.iter().enumerate() {
170            if let (Some(from), Some(event)) = (&t.from, &t.event) {
171                let key = (from.clone(), event.clone());
172                if !seen.insert(key) {
173                    result.diagnostics.push(Diagnostic {
174                        severity: Severity::Warning,
175                        code: "STA004".to_string(),
176                        message: format!(
177                            "Duplicate transition: state \"{from}\" + event \"{event}\" appears multiple times"
178                        ),
179                        node_path: format!("{path}/transitions/{j}"),
180                        pass: self.name().to_string(),
181                    hint: None,
182                    });
183                }
184            }
185        }
186    }
187
188    /// BFS from initial state to find all reachable states.
189    fn find_reachable<'a>(
190        &self,
191        initial: &'a str,
192        transitions: &'a [crate::ir::Transition],
193    ) -> HashSet<&'a str> {
194        let mut visited: HashSet<&str> = HashSet::new();
195        let mut queue: VecDeque<&str> = VecDeque::new();
196
197        visited.insert(initial);
198        queue.push_back(initial);
199
200        while let Some(current) = queue.pop_front() {
201            for t in transitions {
202                if t.from.as_deref() == Some(current) {
203                    if let Some(ref to) = t.to {
204                        if visited.insert(to.as_str()) {
205                            queue.push_back(to.as_str());
206                        }
207                    }
208                }
209            }
210        }
211
212        visited
213    }
214}