1#![forbid(unsafe_code)]
2#![no_std]
3
4#[macro_use]
5extern crate alloc;
6
7use netsblox_ast as ast;
8use netsblox_ast::compact_str::{CompactString, ToCompactString, format_compact};
9
10use graphviz_rust::dot_structures as dot;
11
12use alloc::collections::{VecDeque, BTreeMap};
13use alloc::fmt::Write as _;
14use alloc::boxed::Box;
15use alloc::vec::Vec;
16use alloc::string::{ToString, String};
17
18pub use graphviz_rust as graphviz;
19
20macro_rules! count_exprs {
21 () => { 0usize };
22 ($head:expr $(,$tail:expr)* $(,)?) => { 1usize + count_exprs!($($tail),*) };
23}
24macro_rules! deque {
25 ($($values:expr),* $(,)?) => {{
26 #[allow(unused_mut)]
27 let mut res = VecDeque::with_capacity(count_exprs!($($values),*));
28 $(res.push_back($values);)*
29 res
30 }}
31}
32
33mod condition;
34pub use condition::*;
35
36trait VecDequeUtil<T> {
37 fn extend_front<I: Iterator<Item = T> + DoubleEndedIterator>(&mut self, iter: I);
38}
39impl<T> VecDequeUtil<T> for VecDeque<T> {
40 fn extend_front<I: Iterator<Item = T> + DoubleEndedIterator>(&mut self, iter: I) {
41 for val in iter.rev() {
42 self.push_front(val);
43 }
44 }
45}
46
47fn punctuate<'a, I: Iterator<Item = &'a str>>(mut values: I, sep: &str) -> Option<(CompactString, usize)> {
48 let mut res = CompactString::new(values.next()?);
49 let mut separators = 0;
50 for x in values {
51 res.push_str(sep);
52 res.push_str(x);
53 separators += 1;
54 }
55 Some((res, separators))
56}
57
58fn common_suffix<T: PartialEq, I: Iterator<Item = J>, J: Iterator<Item = T> + DoubleEndedIterator>(mut sequences: I) -> Vec<T> {
59 let mut suffix: Vec<T> = match sequences.next() {
60 None => return <_>::default(),
61 Some(x) => x.collect(),
62 };
63 for sequence in sequences {
64 let common = suffix.iter().rev().zip(sequence.rev()).take_while(|(a, b)| *a == b).count();
65 suffix.drain(..suffix.len() - common);
66 }
67 suffix
68}
69#[test]
70fn test_common_suffix() {
71 assert_eq!(common_suffix(Vec::<alloc::vec::IntoIter<i32>>::new().into_iter()), &[]);
72 assert_eq!(common_suffix([vec![1, 2, 3].into_iter()].into_iter()), &[1, 2, 3]);
73 assert_eq!(common_suffix([vec![1, 2, 3].into_iter(), vec![2, 1, 3].into_iter()].into_iter()), &[3]);
74 assert_eq!(common_suffix([vec![1, 2, 3].into_iter(), vec![2, 2, 3].into_iter()].into_iter()), &[2, 3]);
75 assert_eq!(common_suffix([vec![1, 2, 3].into_iter(), vec![2, 3].into_iter(), vec![2, 2, 3].into_iter()].into_iter()), &[2, 3]);
76 assert_eq!(common_suffix([vec![1, 2, 3].into_iter(), vec![3, 3].into_iter(), vec![2, 2, 3].into_iter()].into_iter()), &[3]);
77 assert_eq!(common_suffix([vec![1, 2, 3].into_iter(), vec![3, 4].into_iter(), vec![2, 2, 3].into_iter()].into_iter()), &[]);
78 assert_eq!(common_suffix([vec![2, 2, 3].into_iter(), vec![2, 2, 3].into_iter(), vec![2, 2, 3].into_iter()].into_iter()), &[2, 2, 3]);
79 assert_eq!(common_suffix([vec![2, 2, 3].into_iter(), vec![2, 2, 4].into_iter(), vec![2, 2, 3].into_iter()].into_iter()), &[]);
80 assert_eq!(common_suffix([vec![2, 2, 3].into_iter(), vec![2, 1, 3].into_iter(), vec![2, 2, 3].into_iter()].into_iter()), &[3]);
81 assert_eq!(common_suffix([vec![2, 2, 3].into_iter(), vec![1, 2, 3].into_iter(), vec![2, 2, 3].into_iter()].into_iter()), &[2, 3]);
82}
83
84struct RenamePool<F: for<'a> FnMut(&'a str) -> Result<CompactString, ()>> {
85 forward: BTreeMap<CompactString, CompactString>,
86 backward: BTreeMap<CompactString, CompactString>,
87 f: F,
88}
89impl<F: for<'a> FnMut(&'a str) -> Result<CompactString, ()>> RenamePool<F> {
90 fn new(f: F) -> Self {
91 Self { forward: Default::default(), backward: Default::default(), f }
92 }
93 fn rename(&mut self, x: &str) -> Result<CompactString, CompileError> {
94 if let Some(res) = self.forward.get(x) {
95 return Ok(res.clone());
96 }
97
98 let y = (self.f)(x).map_err(|()| CompileError::RenameFailure { before: x.into() })?;
99 assert!(self.forward.insert(x.into(), y.clone()).is_none());
100
101 if let Some(prev) = self.backward.insert(y.clone(), x.into()) {
102 return Err(CompileError::RenameConflict { before: (x.into(), prev.clone()), after: y });
103 }
104
105 Ok(y)
106 }
107}
108
109#[derive(Debug, PartialEq, Eq)]
110pub enum CompileError {
111 ParseError(Box<ast::Error>),
112
113 RoleCount { count: usize },
114 UnknownRole { name: CompactString },
115
116 RenameFailure { before: CompactString },
117 RenameConflict { before: (CompactString, CompactString), after: CompactString },
118
119 TransitionEmptyTarget { state_machine: CompactString, state: CompactString },
120 UnsupportedBlock { state_machine: CompactString, state: CompactString, info: CompactString },
121 NonTerminalTransition { state_machine: CompactString, state: CompactString },
122 MultipleHandlers { state_machine: CompactString, state: CompactString },
123 ComplexTransitionName { state_machine: CompactString, state: CompactString },
124 VariadicBlocks { state_machine: CompactString, state: CompactString },
125 ActionsOutsideTransition { state_machine: CompactString, state: CompactString },
126 VariableOverlap { state_machines: (CompactString, CompactString), variable: CompactString },
127 TransitionForeignMachine { state_machine: CompactString, state: CompactString, foreign_machine: CompactString },
128}
129
130#[derive(Debug, PartialEq, Eq, Clone, Copy)]
131pub enum VariableKind {
132 Local, Input, Output,
133}
134
135#[derive(Debug, PartialEq, Eq)]
136pub struct Project {
137 pub name: CompactString,
138 pub role: CompactString,
139 pub state_machines: BTreeMap<CompactString, StateMachine>,
140}
141#[derive(Debug, PartialEq, Eq)]
142pub struct StateMachine {
143 pub variables: BTreeMap<CompactString, Variable>,
144 pub states: BTreeMap<CompactString, State>,
145 pub initial_state: Option<CompactString>,
146 pub current_state: Option<CompactString>,
147}
148#[derive(Debug, PartialEq, Eq)]
149pub struct Variable {
150 pub init: CompactString,
151 pub kind: VariableKind,
152}
153#[derive(Debug, PartialEq, Eq)]
154pub struct State {
155 pub parent: Option<CompactString>,
156 pub transitions: VecDeque<Transition>,
157}
158#[derive(Debug, PartialEq, Eq)]
159pub struct Transition {
160 pub ordered_condition: Condition,
161 pub unordered_condition: Condition,
162 pub actions: VecDeque<CompactString>,
163 pub new_state: Option<CompactString>,
164}
165
166#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
167pub struct Settings {
168 pub omit_unknown_blocks: bool,
169}
170struct Context {
171 variables: Vec<ast::VariableRef>,
172 junctions: Vec<(CompactString, State)>,
173 settings: Settings,
174}
175
176fn prune_unreachable(transitions: &mut VecDeque<Transition>) {
177 transitions.retain(|t| t.ordered_condition != Condition::constant(false) && t.unordered_condition != Condition::constant(false));
178}
179
180fn translate_value(state_machine: &str, state: &str, value: &ast::Value) -> Result<CompactString, CompileError> {
181 Ok(match value {
182 ast::Value::String(x) => x.clone(),
183 ast::Value::Number(x) => x.to_compact_string(),
184 ast::Value::Bool(x) => if *x { "true" } else { "false" }.into(),
185 ast::Value::Constant(x) => match x {
186 ast::Constant::E => core::f64::consts::E.to_compact_string(),
187 ast::Constant::Pi => core::f64::consts::PI.to_compact_string(),
188 }
189 x => return Err(CompileError::UnsupportedBlock { state_machine: state_machine.into(), state: state.into(), info: format_compact!("{x:?}") }),
190 })
191}
192fn translate_expr(state_machine: &str, state: &str, expr: &ast::Expr, context: &mut Context) -> Result<CompactString, CompileError> {
193 fn extract_fixed_variadic(state_machine: &str, state: &str, values: &ast::Expr, context: &mut Context) -> Result<Vec<CompactString>, CompileError> {
194 match &values.kind {
195 ast::ExprKind::MakeList { values } => Ok(values.iter().map(|x| translate_expr(state_machine, state, x, context)).collect::<Result<_,_>>()?),
196 ast::ExprKind::Value(ast::Value::List(values, _)) => Ok(values.iter().map(|x| translate_value(state_machine, state, x)).collect::<Result<_,_>>()?),
197 _ => Err(CompileError::VariadicBlocks { state_machine: state_machine.into(), state: state.into() }),
198 }
199 }
200
201 Ok(match &expr.kind {
202 ast::ExprKind::Value(x) => translate_value(state_machine, state, x)?,
203 ast::ExprKind::Variable { var } => {
204 context.variables.push(var.clone());
205 var.trans_name.clone()
206 }
207 ast::ExprKind::Sin { value } => format_compact!("sind({})", translate_expr(state_machine, state, value, context)?),
208 ast::ExprKind::Cos { value } => format_compact!("cosd({})", translate_expr(state_machine, state, value, context)?),
209 ast::ExprKind::Tan { value } => format_compact!("tand({})", translate_expr(state_machine, state, value, context)?),
210 ast::ExprKind::Asin { value } => format_compact!("asind({})", translate_expr(state_machine, state, value, context)?),
211 ast::ExprKind::Acos { value } => format_compact!("acosd({})", translate_expr(state_machine, state, value, context)?),
212 ast::ExprKind::Atan { value } => format_compact!("atand({})", translate_expr(state_machine, state, value, context)?),
213 ast::ExprKind::Sqrt { value } => format_compact!("sqrt({})", translate_expr(state_machine, state, value, context)?),
214 ast::ExprKind::Floor { value } => format_compact!("floor({})", translate_expr(state_machine, state, value, context)?),
215 ast::ExprKind::Ceil { value } => format_compact!("ceil({})", translate_expr(state_machine, state, value, context)?),
216 ast::ExprKind::Round { value } => format_compact!("round({})", translate_expr(state_machine, state, value, context)?),
217 ast::ExprKind::Sign { value } => format_compact!("sign({})", translate_expr(state_machine, state, value, context)?),
218 ast::ExprKind::Neg { value } => format_compact!("-{}", translate_expr(state_machine, state, value, context)?),
219 ast::ExprKind::Abs { value } => format_compact!("abs({})", translate_expr(state_machine, state, value, context)?),
220 ast::ExprKind::Sub { left, right } => format_compact!("({} - {})", translate_expr(state_machine, state, left, context)?, translate_expr(state_machine, state, right, context)?),
221 ast::ExprKind::Div { left, right } => format_compact!("({} / {})", translate_expr(state_machine, state, left, context)?, translate_expr(state_machine, state, right, context)?),
222 ast::ExprKind::Mod { left, right } => format_compact!("mod({}, {})", translate_expr(state_machine, state, left, context)?, translate_expr(state_machine, state, right, context)?),
223 ast::ExprKind::Log { value, base } => format_compact!("(log({}) / log({}))", translate_expr(state_machine, state, value, context)?, translate_expr(state_machine, state, base, context)?),
224 ast::ExprKind::Atan2 { y, x } => format_compact!("atan2d({}, {})", translate_expr(state_machine, state, y, context)?, translate_expr(state_machine, state, x, context)?),
225 ast::ExprKind::Add { values } => punctuate(extract_fixed_variadic(state_machine,state, values, context)?.iter().map(|x| x.as_str()), " + ").map(|x| format_compact!("({})", x.0)).unwrap_or_else(|| "0".into()),
226 ast::ExprKind::Mul { values } => punctuate(extract_fixed_variadic(state_machine,state, values, context)?.iter().map(|x| x.as_str()), " * ").map(|x| format_compact!("({})", x.0)).unwrap_or_else(|| "1".into()),
227 ast::ExprKind::Pow { base, power } => format_compact!("({} ^ {})", translate_expr(state_machine, state, base, context)?, translate_expr(state_machine, state, power, context)?),
228 ast::ExprKind::Eq { left, right } => format_compact!("{} == {}", translate_expr(state_machine, state, left, context)?, translate_expr(state_machine, state, right, context)?),
229 ast::ExprKind::Neq { left, right } => format_compact!("{} ~= {}", translate_expr(state_machine, state, left, context)?, translate_expr(state_machine, state, right, context)?),
230 ast::ExprKind::Greater { left, right } => format_compact!("{} > {}", translate_expr(state_machine, state, left, context)?, translate_expr(state_machine, state, right, context)?),
231 ast::ExprKind::GreaterEq { left, right } => format_compact!("{} >= {}", translate_expr(state_machine, state, left, context)?, translate_expr(state_machine, state, right, context)?),
232 ast::ExprKind::Less { left, right } => format_compact!("{} < {}", translate_expr(state_machine, state, left, context)?, translate_expr(state_machine, state, right, context)?),
233 ast::ExprKind::LessEq { left, right } => format_compact!("{} <= {}", translate_expr(state_machine, state, left, context)?, translate_expr(state_machine, state, right, context)?),
234 ast::ExprKind::And { left, right } => format_compact!("{} & {}", translate_expr(state_machine, state, left, context)?, translate_expr(state_machine, state, right, context)?),
235 ast::ExprKind::Or { left, right } => format_compact!("({} | {})", translate_expr(state_machine, state, left, context)?, translate_expr(state_machine, state, right, context)?),
236 ast::ExprKind::Not { value } => format_compact!("~({})", translate_expr(state_machine, state, value, context)?),
237 ast::ExprKind::Timer => "t".into(),
238 ast::ExprKind::Random { a, b } => match (translate_expr(state_machine, state, a, context)?.as_str(), translate_expr(state_machine, state, b, context)?.as_str()) {
239 ("1", b) => format_compact!("randi({b})"),
240 (a, b) => format_compact!("randi([{a}, {b}])"),
241 }
242 x => match context.settings.omit_unknown_blocks {
243 true => "?".into(),
244 false => return Err(CompileError::UnsupportedBlock { state_machine: state_machine.into(), state: state.into(), info: format_compact!("{x:?}") }),
245 }
246 })
247}
248fn translate_condition(state_machine: &str, state: &str, expr: &ast::Expr, context: &mut Context) -> Result<Condition, CompileError> {
249 Ok(match &expr.kind {
250 ast::ExprKind::And { left, right } => translate_condition(state_machine, state, left, context)? & translate_condition(state_machine, state, right, context)?,
251 ast::ExprKind::Or { left, right } => translate_condition(state_machine, state, left, context)? | translate_condition(state_machine, state, right, context)?,
252 ast::ExprKind::Not { value } => !translate_condition(state_machine, state, value, context)?,
253 ast::ExprKind::Value(ast::Value::Bool(x)) => Condition::constant(*x),
254 ast::ExprKind::Value(ast::Value::String(x)) if x.is_empty() => Condition::constant(true),
255 _ => Condition::atom(translate_expr(state_machine, state, expr, context)?),
256 })
257}
258fn parse_actions(state_machine: &str, state: &str, stmt: &ast::Stmt, context: &mut Context) -> Result<Vec<CompactString>, CompileError> {
259 Ok(match &stmt.kind {
260 ast::StmtKind::Assign { var, value } => {
261 context.variables.push(var.clone());
262 vec![format_compact!("{} = {}", var.trans_name, translate_expr(state_machine, state, value, context)?)]
263 }
264 ast::StmtKind::AddAssign { var, value } => {
265 context.variables.push(var.clone());
266 vec![format_compact!("{} = {} + {}", var.trans_name, var.trans_name, translate_expr(state_machine, state, value, context)?)]
267 }
268 ast::StmtKind::ResetTimer => vec!["t = 0".into()],
269 x => match context.settings.omit_unknown_blocks {
270 true => vec!["?".into()],
271 false => return Err(CompileError::UnsupportedBlock { state_machine: state_machine.into(), state: state.into(), info: format_compact!("{x:?}") }),
272 }
273 })
274}
275fn parse_transitions(state_machine: &str, state: &str, stmt: &ast::Stmt, terminal: bool, context: &mut Context) -> Result<Option<(VecDeque<Transition>, Condition, bool)>, CompileError> {
276 fn parse_transition_target(state_machine: &str, state: &str, expr: &ast::Expr, context: &mut Context) -> Result<VecDeque<Transition>, CompileError> {
277 Ok(match &expr.kind {
278 ast::ExprKind::Value(ast::Value::String(x)) => match x.as_str() {
279 "" => return Err(CompileError::TransitionEmptyTarget { state_machine: state_machine.into(), state: state.into() }),
280 _ => deque![Transition { ordered_condition: Condition::constant(true), unordered_condition: Condition::constant(true), actions: <_>::default(), new_state: Some(x.clone()) }],
281 }
282 ast::ExprKind::Conditional { condition, then, otherwise } => {
283 let condition = translate_condition(state_machine, state, condition, context)?;
284 let mut then_transitions = parse_transition_target(state_machine, state, then, context)?;
285 let mut otherwise_transitions = parse_transition_target(state_machine, state, otherwise, context)?;
286
287 for transition in then_transitions.iter_mut() {
288 for target in [&mut transition.unordered_condition, &mut transition.ordered_condition] {
289 *target = condition.clone() & target.clone();
290 }
291 }
292 for transition in otherwise_transitions.iter_mut() {
293 transition.unordered_condition = !condition.clone() & transition.unordered_condition.clone();
294 }
295
296 then_transitions.extend(otherwise_transitions);
297 then_transitions
298 }
299 _ => return Err(CompileError::ComplexTransitionName { state_machine: state_machine.into(), state: state.into() }),
300 })
301 }
302
303 Ok(match &stmt.kind {
304 ast::StmtKind::UnknownBlock { name, args } => match (name.as_str(), args.as_slice()) {
305 ("smTransition", [var, value]) => match &var.kind {
306 ast::ExprKind::Value(ast::Value::String(var)) => match *var == state_machine {
307 true => Some((parse_transition_target(state_machine, state, value, context)?, Condition::constant(false), true)),
308 false => return Err(CompileError::TransitionForeignMachine { state_machine: state_machine.into(), state: state.into(), foreign_machine: var.clone() }),
309 }
310 _ => None,
311 }
312 _ => None,
313 }
314 ast::StmtKind::Assign { var, value } if var.name == state_machine => match terminal {
315 true => Some((parse_transition_target(state_machine, state, value, context)?, Condition::constant(false), true)),
316 false => return Err(CompileError::NonTerminalTransition { state_machine: state_machine.into(), state: state.into() }),
317 }
318 ast::StmtKind::If { condition, then } => {
319 let condition = translate_condition(state_machine, state, condition, context)?;
320 let (mut transitions, body_terminal, volatile) = parse_stmts(state_machine, state, then, terminal, context, false)?;
321
322 if volatile {
323 make_junction(state, &mut <_>::default(), &mut transitions, context);
324 debug_assert_eq!(transitions.len(), 1);
325 }
326
327 let tail_condition = match body_terminal {
328 true => !condition.clone(),
329 false => transitions.iter().map(|t| t.ordered_condition.clone()).reduce(|a, b| a | b).map(|c| !(condition.clone() & c)).unwrap_or(Condition::constant(true)),
330 };
331
332 for transition in transitions.iter_mut() {
333 for target in [&mut transition.unordered_condition, &mut transition.ordered_condition] {
334 *target = condition.clone() & target.clone();
335 }
336 }
337
338 Some((transitions, tail_condition, false))
339 }
340 ast::StmtKind::IfElse { condition, then, otherwise } => {
341 let condition = translate_condition(state_machine, state, condition, context)?;
342
343 let (mut transitions_1, body_terminal_1, volatile_1) = parse_stmts(state_machine, state, then, terminal, context, false)?;
344 let (mut transitions_2, body_terminal_2, volatile_2) = parse_stmts(state_machine, state, otherwise, terminal, context, false)?;
345
346 if volatile_1 {
347 make_junction(state, &mut <_>::default(), &mut transitions_1, context);
348 debug_assert_eq!(transitions_1.len(), 1);
349 }
350 if volatile_2 {
351 make_junction(state, &mut <_>::default(), &mut transitions_2, context);
352 debug_assert_eq!(transitions_2.len(), 1);
353 }
354
355 let cond_1 = transitions_1.back().map(|t| t.unordered_condition.clone()).unwrap_or(Condition::constant(false));
356 let cond_2 = transitions_2.back().map(|t| t.unordered_condition.clone()).unwrap_or(Condition::constant(false));
357
358 let tail_condition = match (body_terminal_1, body_terminal_2) {
359 (true, true) => Condition::constant(false),
360 (true, false) => !condition.clone() & !cond_2,
361 (false, true) => condition.clone() & !cond_1,
362 (false, false) => !(condition.clone() & cond_1) & !(!condition.clone() & cond_2),
363 };
364
365 for transition in transitions_1.iter_mut() {
366 for target in [&mut transition.unordered_condition, &mut transition.ordered_condition] {
367 *target = condition.clone() & target.clone();
368 }
369 }
370 for transition in transitions_2.iter_mut() {
371 let targets = match body_terminal_1 {
372 true => [Some(&mut transition.unordered_condition), None],
373 false => [Some(&mut transition.unordered_condition), Some(&mut transition.ordered_condition)],
374 };
375 for target in targets.into_iter().flatten() {
376 *target = !condition.clone() & target.clone();
377 }
378 }
379
380 transitions_1.extend(transitions_2);
381 Some((transitions_1, tail_condition, body_terminal_1 && body_terminal_2))
382 }
383 _ => None,
384 })
385}
386fn make_junction<'a>(state: &str, actions: &mut VecDeque<CompactString>, transitions: &mut VecDeque<Transition>, context: &'a mut Context) {
387 prune_unreachable(transitions);
388
389 let junction = format_compact!("::junction-{}::", context.junctions.len());
390 let mut junction_state = State { parent: Some(state.into()), transitions: core::mem::take(transitions) };
391
392 if junction_state.transitions.back().map(|t| t.ordered_condition != Condition::constant(true)).unwrap_or(true) {
393 let return_condition: Condition = junction_state.transitions.iter().map(|t| t.unordered_condition.clone()).fold(Condition::constant(true), |a, b| a & !b);
394 junction_state.transitions.push_back(Transition {
395 unordered_condition: return_condition,
396 ordered_condition: Condition::constant(true),
397 actions: deque![],
398 new_state: Some(state.into()),
399 });
400 }
401
402 transitions.push_front(Transition { ordered_condition: Condition::constant(true), unordered_condition: Condition::constant(true), actions: core::mem::take(actions), new_state: Some(junction.clone()) });
403 context.junctions.push((junction, junction_state));
404}
405fn handle_actions(state_machine: &str, state: &str, actions: &mut VecDeque<CompactString>, transitions: &mut VecDeque<Transition>, terminal: bool, volatile: &mut bool, context: &mut Context) -> Result<(), CompileError> {
406 prune_unreachable(transitions);
407
408 if !actions.is_empty() {
409 if terminal && transitions.is_empty() {
410 transitions.push_front(Transition { ordered_condition: Condition::constant(true), unordered_condition: Condition::constant(true), actions: core::mem::take(actions), new_state: Some(state.into()) });
411 } else if transitions.len() == 1 && transitions[0].unordered_condition == Condition::constant(true) {
412 transitions[0].actions.extend_front(core::mem::take(actions).into_iter());
413 } else if terminal {
414 make_junction(state, actions, transitions, context);
415 debug_assert_eq!(transitions.len(), 1);
416 *volatile = false;
417 } else {
418 return Err(CompileError::ActionsOutsideTransition { state_machine: state_machine.into(), state: state.into() });
419 }
420 }
421
422 debug_assert_eq!(actions.len(), 0);
423 Ok(())
424}
425fn parse_stmts(state_machine: &str, state: &str, stmts: &[ast::Stmt], script_terminal: bool, context: &mut Context, top_level: bool) -> Result<(VecDeque<Transition>, bool, bool), CompileError> {
426 let mut actions: VecDeque<CompactString> = <_>::default();
427 let mut transitions: VecDeque<Transition> = <_>::default();
428 let mut body_terminal = false;
429 let mut volatile = false;
430
431 if top_level {
432 transitions.push_back(Transition { unordered_condition: Condition::constant(true), ordered_condition: Condition::constant(true), actions: <_>::default(), new_state: Some(state.into()) });
433 }
434
435 let mut stmts = stmts.iter().rev().peekable();
436 while let Some(stmt) = stmts.peek() {
437 match &stmt.kind {
438 ast::StmtKind::Return { value: _ } => (),
439 _ => break,
440 }
441 stmts.next();
442 body_terminal = true;
443 }
444
445 let mut last = true;
446 for stmt in stmts {
447 match parse_transitions(state_machine, state, stmt, (script_terminal || body_terminal) && last, context)? {
448 Some((sub_transitions, tail_condition, sub_body_terminal)) => {
449 handle_actions(state_machine, state, &mut actions, &mut transitions, script_terminal || body_terminal, &mut volatile, context)?;
450 debug_assert_eq!(actions.len(), 0);
451
452 if volatile {
453 make_junction(state, &mut actions, &mut transitions, context);
454 debug_assert_eq!(actions.len(), 0);
455 debug_assert_eq!(transitions.len(), 1);
456 volatile = false;
457 }
458
459 body_terminal |= sub_body_terminal;
460 for transition in transitions.iter_mut() {
461 transition.unordered_condition = tail_condition.clone() & transition.unordered_condition.clone();
462 }
463 transitions.extend_front(sub_transitions.into_iter());
464 }
465 None => match &stmt.kind {
466 ast::StmtKind::Sleep { seconds } => {
467 handle_actions(state_machine, state, &mut actions, &mut transitions, script_terminal || body_terminal, &mut volatile, context)?;
468 debug_assert_eq!(actions.len(), 0);
469
470 match transitions.as_slices() {
471 ([t], []) if t.unordered_condition == Condition::constant(true) => (),
472 _ => {
473 make_junction(state, &mut actions, &mut transitions, context);
474 debug_assert_eq!(actions.len(), 0);
475 debug_assert_eq!(transitions.len(), 1);
476 }
477 };
478
479 let condition = Condition::atom(format_compact!("after({}, sec)", translate_expr(state_machine, state, seconds, context)?));
480 for transition in transitions.iter_mut() {
481 for target in [&mut transition.unordered_condition, &mut transition.ordered_condition] {
482 *target = target.clone() & condition.clone();
483 }
484 }
485
486 transitions.push_back(Transition {
487 unordered_condition: !condition,
488 ordered_condition: Condition::constant(true),
489 actions: <_>::default(),
490 new_state: None,
491 });
492
493 volatile = true;
494 }
495 _ => actions.extend_front(parse_actions(state_machine, state, stmt, context)?.into_iter()),
496 }
497 }
498 last = false;
499 }
500
501 handle_actions(state_machine, state, &mut actions, &mut transitions, script_terminal || body_terminal, &mut volatile, context)?;
502 debug_assert_eq!(actions.len(), 0);
503
504 Ok((transitions, body_terminal, volatile))
505}
506
507fn dot_id(name: &str) -> dot::Id {
508 dot::Id::Escaped(format!("{name:?}"))
509}
510
511impl Project {
512 pub fn compile(xml: &str, role: Option<&str>, settings: Settings) -> Result<Project, CompileError> {
513 let parser = ast::Parser {
514 name_transformer: Box::new(ast::util::c_ident),
515 ..Default::default()
516 };
517 let proj = parser.parse(xml).map_err(CompileError::ParseError)?;
518 let role = match role {
519 Some(name) => match proj.roles.iter().find(|r| r.name == name) {
520 Some(x) => x,
521 None => return Err(CompileError::UnknownRole { name: name.into() }),
522 }
523 None => match proj.roles.as_slice() {
524 [x] => x,
525 x => return Err(CompileError::RoleCount { count: x.len() }),
526 }
527 };
528
529 let mut state_machines: BTreeMap<CompactString, (StateMachine, Context)> = <_>::default();
530 for entity in role.entities.iter() {
531 for script in entity.scripts.iter() {
532 let (state_machine_name, state_name) = match script.hat.as_ref().map(|x| &x.kind) {
533 Some(ast::HatKind::When { condition }) => match &condition.kind {
534 ast::ExprKind::Eq { left, right } => match (&left.kind, &right.kind) {
535 (ast::ExprKind::Variable { var }, ast::ExprKind::Value(ast::Value::String(val))) => (&var.name, val),
536 (ast::ExprKind::Value(ast::Value::String(val)), ast::ExprKind::Variable { var }) => (&var.name, val),
537 _ => continue,
538 }
539 ast::ExprKind::UnknownBlock { name, args } => match (name.as_str(), args.as_slice()) {
540 ("smInState", [var, val]) => match (&var.kind, &val.kind) {
541 (ast::ExprKind::Value(ast::Value::String(var)), ast::ExprKind::Value(ast::Value::String(val))) => (var, val),
542 _ => continue,
543 }
544 _ => continue,
545 }
546 _ => continue,
547 }
548 _ => continue,
549 };
550
551 let (state_machine, context) = state_machines.entry(state_machine_name.clone()).or_insert_with(|| {
552 (StateMachine { variables: <_>::default(), states: <_>::default(), initial_state: None, current_state: None }, Context { variables: vec![], junctions: vec![], settings })
553 });
554 if state_machine.states.contains_key(state_name.as_str()) {
555 return Err(CompileError::MultipleHandlers { state_machine: state_machine_name.clone(), state: state_name.clone() });
556 }
557
558 let (transitions, _, _) = parse_stmts(state_machine_name, state_name, &script.stmts, true, context, true)?;
559 assert!(state_machine.states.insert(state_name.clone(), State { parent: None, transitions }).is_none());
560 }
561 }
562
563 for (state_machine, _) in state_machines.values_mut() {
564 for state in state_machine.states.values_mut() {
565 prune_unreachable(&mut state.transitions);
566 if let Some(last) = state.transitions.back_mut() {
567 last.ordered_condition = Condition::constant(true);
568 }
569 }
570 }
571
572 let mut state_machines = state_machines.into_iter().map(|(state_machine_name, (mut state_machine, context))| {
573 for (name, junction) in context.junctions {
574 assert!(state_machine.states.insert(name, junction).is_none());
575 }
576 for variable in context.variables {
577 state_machine.variables.insert(variable.trans_name, Variable { init: "0".into(), kind: VariableKind::Local });
578 }
579 (state_machine_name, state_machine)
580 }).collect::<BTreeMap<_,_>>();
581
582 for state_machine in state_machines.values_mut() {
583 let target_states: Vec<_> = state_machine.states.values().flat_map(|s| s.transitions.iter().flat_map(|t| t.new_state.clone())).collect();
584 for target_state in target_states {
585 state_machine.states.entry(target_state.clone()).or_insert_with(|| State {
586 parent: None,
587 transitions: deque![Transition { unordered_condition: Condition::constant(true), ordered_condition: Condition::constant(true), actions: <_>::default(), new_state: Some(target_state) }]
588 });
589 }
590 }
591
592 let mut var_inits: BTreeMap<&CompactString, &ast::Expr> = BTreeMap::new();
593 let mut var_kinds: BTreeMap<&CompactString, VariableKind> = BTreeMap::new();
594 for entity in role.entities.iter() {
595 for script in entity.scripts.iter() {
596 if let Some(ast::HatKind::OnFlag) = script.hat.as_ref().map(|x| &x.kind) {
597 for stmt in script.stmts.iter() {
598 match &stmt.kind {
599 ast::StmtKind::Assign { var, value } => match state_machines.get_mut(&var.name) {
600 Some(state_machine) => if let ast::ExprKind::Value(ast::Value::String(value)) = &value.kind {
601 if state_machine.states.contains_key(value) { state_machine.initial_state = Some(value.clone()); }
602 }
603 None => { var_inits.insert(&var.trans_name, value); }
604 }
605 ast::StmtKind::UnknownBlock { name, args } => match (name.as_str(), args.as_slice()) {
606 ("smTransition", [var, value]) => if let (ast::ExprKind::Value(ast::Value::String(var)), ast::ExprKind::Value(ast::Value::String(value))) = (&var.kind, &value.kind) {
607 if let Some(state_machine) = state_machines.get_mut(var) {
608 if state_machine.states.contains_key(value) { state_machine.initial_state = Some(value.clone()); }
609 }
610 }
611 ("smMarkVar", [var, kind]) => if let (ast::ExprKind::Value(ast::Value::String(var)), ast::ExprKind::Value(ast::Value::String(kind))) = (&var.kind, &kind.kind) {
612 let kind = match kind.as_str() {
613 "local" => VariableKind::Local,
614 "input" => VariableKind::Input,
615 "output" => VariableKind::Output,
616 _ => continue,
617 };
618 var_kinds.insert(var, kind);
619 }
620 _ => (),
621 }
622 _ => (),
623 }
624 }
625 }
626 }
627 }
628
629 let mut var_inits_context = Context { variables: vec![], junctions: vec![], settings };
630 for (state_machine_name, state_machine) in state_machines.iter_mut() {
631 if let Some(ast::Value::String(init)) = role.globals.iter().find(|g| g.def.name == state_machine_name).map(|g| &g.init) {
632 if state_machine.states.contains_key(init) {
633 state_machine.current_state = Some(init.clone());
634 }
635 }
636
637 for (var, info) in state_machine.variables.iter_mut() {
638 if let Some(&init) = var_inits.get(var) {
639 info.init = translate_expr(state_machine_name, "<init>", init, &mut var_inits_context)?;
640 }
641 if let Some(&kind) = var_kinds.get(var) {
642 info.kind = kind;
643 }
644 }
645 }
646 debug_assert_eq!(var_inits_context.variables.len(), 0);
647 debug_assert_eq!(var_inits_context.junctions.len(), 0);
648 drop(var_inits_context);
649
650 let mut machines = state_machines.iter();
651 while let Some(machine_1) = machines.next() {
652 if let Some((machine_2, var)) = machines.clone().find_map(|machine_2| machine_1.1.variables.keys().find(|&k| machine_2.1.variables.contains_key(k)).map(|x| (machine_2, x))) {
653 return Err(CompileError::VariableOverlap { state_machines: (machine_1.0.clone(), machine_2.0.clone()), variable: var.clone() });
654 }
655 if let Some(var) = machine_1.1.variables.keys().find(|&x| state_machines.contains_key(x)) {
656 return Err(CompileError::VariableOverlap { state_machines: (machine_1.0.clone(), var.clone()), variable: var.clone() });
657 }
658 }
659
660 for machine in state_machines.values_mut() {
661 for (state_name, state) in machine.states.iter_mut() {
662 for transition in state.transitions.iter_mut() {
663 if matches!(&transition.new_state, Some(x) if x == state_name) {
664 transition.new_state = None;
665 }
666 }
667 }
668 }
669
670 Ok(Project { name: proj.name, role: role.name.clone(), state_machines })
671 }
672 pub fn to_graphviz(&self) -> dot::Graph {
673 let stmts = self.state_machines.iter().map(|(name, state_machine)| {
674 let node_id = |state: &str| dot::NodeId(if !state.is_empty() { dot_id(&format!("{name} {state}")) } else { dot_id(name) }, None);
675
676 let mut stmts = vec![];
677 if let Some(init) = state_machine.initial_state.as_ref() {
678 let attributes = vec![
679 dot::Attribute(dot::Id::Plain("shape".into()), dot::Id::Plain("point".into())),
680 dot::Attribute(dot::Id::Plain("width".into()), dot::Id::Plain("0.1".into())),
681 ];
682 stmts.push(dot::Stmt::Node(dot::Node { id: node_id(""), attributes }));
683 stmts.push(dot::Stmt::Edge(dot::Edge { ty: dot::EdgeTy::Pair(dot::Vertex::N(node_id("")), dot::Vertex::N(node_id(init))), attributes: vec![] }));
684 }
685 for (state_name, state) in state_machine.states.iter() {
686 let mut attributes = vec![];
687
688 if state.parent.is_none() {
689 attributes.push(dot::Attribute(dot::Id::Plain("label".into()), dot_id(state_name)));
690 } else {
691 attributes.push(dot::Attribute(dot::Id::Plain("label".into()), dot_id("")));
692 attributes.push(dot::Attribute(dot::Id::Plain("shape".into()), dot::Id::Plain("circle".into())));
693 attributes.push(dot::Attribute(dot::Id::Plain("width".into()), dot::Id::Plain("0.1".into())));
694 }
695
696 if state_machine.current_state.as_ref().map(|x| x == state_name).unwrap_or(false) {
697 attributes.push(dot::Attribute(dot::Id::Plain("style".into()), dot::Id::Plain("filled".into())));
698 }
699
700 stmts.push(dot::Stmt::Node(dot::Node { id: node_id(state_name), attributes }));
701 }
702 for (state_name, state) in state_machine.states.iter() {
703 let included_transitions = state.transitions.iter().filter(|t| t.new_state.as_ref().unwrap_or(state_name) != state_name || !t.actions.is_empty() || t.ordered_condition != Condition::constant(true)).collect::<Vec<_>>();
704
705 let labeler: fn (usize, Option<String>) -> dot::Id = match included_transitions.len() {
706 1 => |_, t| t.map(|t| dot_id(&format!(" {t} "))).unwrap_or_else(|| dot_id("")),
707 _ => |i, t| t.map(|t| dot_id(&format!(" {}: {t} ", i + 1))).unwrap_or_else(|| dot_id(&format!(" {} ", i + 1))),
708 };
709 for (i, transition) in included_transitions.iter().enumerate() {
710 stmts.push(dot::Stmt::Edge(dot::Edge { ty: dot::EdgeTy::Pair(dot::Vertex::N(node_id(state_name)), dot::Vertex::N(node_id(transition.new_state.as_ref().unwrap_or(state_name)))), attributes: vec![
711 dot::Attribute(dot::Id::Plain("label".into()), labeler(i, if transition.ordered_condition != Condition::constant(true) { Some(transition.ordered_condition.to_string()) } else { None })),
712 ] }));
713 }
714 }
715 dot::Stmt::Subgraph(dot::Subgraph { id: dot_id(name), stmts })
716 }).collect();
717 dot::Graph::DiGraph { id: dot_id(&self.name), strict: false, stmts }
718 }
719 pub fn to_stateflow(&self) -> Result<CompactString, CompileError> {
720 let mut rename_pool = RenamePool::new(ast::util::c_ident);
721 let mut rename = move |x| rename_pool.rename(x);
722 let model_name = rename(&self.name)?;
723
724 let state_size = (100, 100);
725 let junction_size = (100, 20);
726 let padding = (100, 100);
727
728 fn stateflow_escape(full: &str) -> String {
729 let mut res = String::new();
730 for line in full.lines() {
731 if !res.is_empty() {
732 res.push_str(" + newline + ");
733 }
734 write!(res, "{line:?}").unwrap();
735 }
736 res
737 }
738
739 let mut res = CompactString::default();
740 writeln!(res, "sfnew {model_name}").unwrap();
741 for (state_machine_idx, (state_machine_name, state_machine)) in self.state_machines.iter().enumerate() {
742 let state_numbers: BTreeMap<&str, usize> = state_machine.states.iter().enumerate().map(|x| (x.1.0.as_str(), x.0)).collect();
743 let parent_state_numbers: BTreeMap<&str, usize> = state_machine.states.iter().filter(|x| x.1.parent.is_none()).enumerate().map(|x| (x.1.0.as_str(), x.0)).collect();
744
745 if state_machine_idx == 0 {
746 writeln!(res, "chart = find(sfroot, \"-isa\", \"Stateflow.Chart\")").unwrap();
747 writeln!(res, "chart.Name = {state_machine_name:?}").unwrap();
748 } else {
749 writeln!(res, "chart = add_block(\"sflib/Chart\", {:?})", format!("{model_name}/{state_machine_name}")).unwrap();
750 }
751
752 let included_transitions = state_machine.states.iter().map(|(state_name, state)| {
753 (state as *const State, state.transitions.iter().filter(|t| t.new_state.as_ref().unwrap_or(state_name) != state_name || !t.actions.is_empty() || t.ordered_condition != Condition::constant(true)).collect::<Vec<_>>())
754 }).collect::<BTreeMap<_,_>>();
755
756 let entry_actions = state_machine.states.iter().filter(|s| s.1.parent.is_none()).map(|(state_name, _)| {
757 let actions = match state_machine.initial_state.as_ref().map(|i| i != state_name).unwrap_or(true) {
758 true => common_suffix(state_machine.states.iter().flat_map(|(n, s)| included_transitions[&(s as _)].iter().filter(|t| t.new_state.as_ref().unwrap_or(n) == state_name)).map(|t| t.actions.iter())),
759 false => <_>::default(),
760 };
761 (state_name, actions)
762 }).collect::<BTreeMap<_,_>>();
763 let exit_actions = state_machine.states.iter().filter(|s| s.1.parent.is_none()).map(|(state_name, state)| {
764 let actions = common_suffix(included_transitions[&(state as _)].iter().map(|t| t.actions.iter().take(t.actions.len() - entry_actions.get(t.new_state.as_ref().unwrap_or(state_name)).map(|x| x.len()).unwrap_or(0))));
765 (state_name, actions)
766 }).collect::<BTreeMap<_,_>>();
767
768 let mut child_counts: BTreeMap<&str, usize> = Default::default();
769 for (state_idx, (state_name, state)) in state_machine.states.iter().enumerate() {
770 match state.parent.as_deref() {
771 Some(parent) => {
772 *child_counts.entry(parent).or_default() += 1;
773 writeln!(res, "s{state_idx} = Stateflow.State(chart)").unwrap();
774 writeln!(res, "s{state_idx}.LabelString = \"{}_{}\"", rename(parent)?, child_counts[parent]).unwrap();
775 writeln!(res, "s{state_idx}.Position = [{}, {}, {}, {}]", parent_state_numbers[parent] * (state_size.0 + padding.0) + (state_size.0 - junction_size.0) / 2, state_size.1 + padding.1 * child_counts[parent], junction_size.0, junction_size.1).unwrap();
776 }
777 None => {
778 let mut label = rename(state_name)?;
779 match entry_actions.get(state_name) {
780 Some(actions) if !actions.is_empty() => {
781 label.push_str("\nentry:");
782 for action in actions {
783 write!(label, " {action};").unwrap();
784 }
785 }
786 _ => (),
787 }
788 match exit_actions.get(state_name) {
789 Some(actions) if !actions.is_empty() => {
790 label.push_str("\nexit:");
791 for action in actions {
792 write!(label, " {action};").unwrap();
793 }
794 }
795 _ => (),
796 }
797
798 writeln!(res, "s{state_idx} = Stateflow.State(chart)").unwrap();
799 writeln!(res, "s{state_idx}.LabelString = {}", stateflow_escape(&label)).unwrap();
800 writeln!(res, "s{state_idx}.Position = [{}, {}, {}, {}]", parent_state_numbers[state_name.as_str()] * (state_size.0 + padding.0), 0, state_size.0, state_size.1).unwrap();
801 }
802 }
803 }
804 for (state_idx, (state_name, state)) in state_machine.states.iter().enumerate() {
805 for transition in &included_transitions[&(state as _)] {
806 writeln!(res, "t = Stateflow.Transition(chart)").unwrap();
807 writeln!(res, "t.Source = s{state_idx}").unwrap();
808 writeln!(res, "t.Destination = s{}", state_numbers[transition.new_state.as_deref().unwrap_or(state_name)]).unwrap();
809
810 let mut label = CompactString::default();
811 if transition.unordered_condition != Condition::constant(true) {
812 write!(label, "[{}]", transition.unordered_condition).unwrap();
813 }
814
815 let entry_action_count = entry_actions.get(transition.new_state.as_ref().unwrap_or(state_name)).map(|x| x.len()).unwrap_or(0);
816 let exit_action_count = exit_actions.get(state_name).map(|x| x.len()).unwrap_or(0);
817 if transition.actions.len() > entry_action_count + exit_action_count {
818 label.push('{');
819 for action in transition.actions.iter().take(transition.actions.len() - (entry_action_count + exit_action_count)) {
820 write!(label, "{action};").unwrap();
821 }
822 label.push('}');
823 }
824
825 writeln!(res, "t.LabelString = {label:?}").unwrap();
826 }
827 }
828 if let Some(initial_state) = state_machine.initial_state.as_deref() {
829 writeln!(res, "t = Stateflow.Transition(chart)").unwrap();
830 writeln!(res, "t.Destination = s{}", state_numbers[initial_state]).unwrap();
831 writeln!(res, "t.DestinationOClock = 0").unwrap();
832 writeln!(res, "t.SourceEndpoint = t.DestinationEndpoint - [0 30]").unwrap();
833 writeln!(res, "t.Midpoint = t.DestinationEndpoint - [0 15]").unwrap();
834 }
835 for (var, info) in state_machine.variables.iter() {
836 writeln!(res, "d = Stateflow.Data(chart)").unwrap();
837 writeln!(res, "d.Name = {var:?}").unwrap();
838 writeln!(res, "d.Props.InitialValue = {:?}", info.init).unwrap();
839 writeln!(res, "d.Scope = \"{:?}\"", info.kind).unwrap();
840 }
841 }
842 debug_assert_eq!(res.chars().next_back(), Some('\n'));
843 res.pop();
844 Ok(res)
845 }
846}