vertep_core/
compile.rs

1//! The compiled chart: a validated IR flattened into dense tables for the step kernel.
2//!
3//! States are numbered in document order with the `<scxml>` root at index [`ROOT`]; because the
4//! numbering is a pre-order walk, the descendants of a state occupy the contiguous index range
5//! `i + 1 ..= last`, so `isDescendant` is two comparisons. Ascending index order is entry order
6//! and descending index order is exit order. Every compound state (and the root) gets a
7//! synthesized default-entry transition resolved by [`crate::validate::resolve_initial`], and
8//! transition domains are precomputed whenever they do not depend on history. The compiled
9//! chart is derived data and is never serialized; only the IR is.
10
11use alloc::collections::BTreeMap;
12use alloc::string::String;
13use alloc::vec::Vec;
14
15use crate::bitset::StateSet;
16use crate::ir::{
17    Binding, Block, Chart, Data, DoneData, Expr, Invoke, StateElement, StateKind, TransitionType,
18};
19use crate::kernel;
20use crate::validate::{Flat, Violation, resolve_initial, resolve_root_initial, validate};
21
22/// Dense index of a state; [`ROOT`] is the `<scxml>` element.
23pub type StateIdx = usize;
24/// Dense index of a transition in [`CompiledChart::transitions`].
25pub type TransIdx = usize;
26/// Index of the `<scxml>` root.
27pub const ROOT: StateIdx = 0;
28
29/// A state in the compiled chart.
30#[derive(Clone, Debug, PartialEq)]
31pub struct CState {
32    /// The state identifier; empty for the root.
33    pub id: String,
34    /// The kind; the root is [`StateKind::Compound`].
35    pub kind: StateKind,
36    /// The parent; `None` only for the root.
37    pub parent: Option<StateIdx>,
38    /// The last index of this state's subtree (itself when it has no descendants).
39    pub last: StateIdx,
40    /// Child states that are not history states, in document order.
41    pub children: Vec<StateIdx>,
42    /// History children in document order.
43    pub history: Vec<StateIdx>,
44    /// Transitions declared on the state, in document order (for a history state: its default).
45    pub transitions: Vec<TransIdx>,
46    /// The default-entry transition of a compound state or the root.
47    pub initial: Option<TransIdx>,
48    /// `onentry` blocks.
49    pub onentry: Vec<Block>,
50    /// `onexit` blocks.
51    pub onexit: Vec<Block>,
52    /// Data items declared by the state (for the root: the top-level datamodel).
53    pub data: Vec<Data>,
54    /// Invokes in document order.
55    pub invokes: Vec<Invoke>,
56    /// `donedata` of a final state.
57    pub donedata: Option<DoneData>,
58}
59
60/// The transition domain, precomputed when it does not depend on history.
61#[derive(Clone, Copy, Debug, PartialEq, Eq)]
62pub enum Domain {
63    /// The transition has no targets and exits nothing.
64    Targetless,
65    /// The domain is fixed.
66    Static(StateIdx),
67    /// A target is a history state, so the domain depends on the recorded history.
68    Dynamic,
69}
70
71/// A transition in the compiled chart.
72#[derive(Clone, Debug, PartialEq)]
73pub struct CTransition {
74    /// The source state.
75    pub source: StateIdx,
76    /// Index in the source's IR `transitions`, or `None` for a synthesized default entry.
77    pub index: Option<usize>,
78    /// Event descriptors; empty for an eventless transition.
79    pub events: Vec<String>,
80    /// The guard.
81    pub cond: Option<Expr>,
82    /// Targets in document order of the source.
83    pub targets: Vec<StateIdx>,
84    /// Whether the transition is of type internal.
85    pub internal: bool,
86    /// Executable content.
87    pub body: Block,
88    /// The precomputed domain.
89    pub domain: Domain,
90}
91
92/// A validated chart flattened into tables for the step kernel.
93#[derive(Clone, Debug)]
94pub struct CompiledChart {
95    chart: Chart,
96    states: Vec<CState>,
97    transitions: Vec<CTransition>,
98    by_id: BTreeMap<String, StateIdx>,
99}
100
101impl CompiledChart {
102    /// Validate and compile a chart. Fails with every well-formedness violation.
103    pub fn new(chart: Chart) -> Result<Self, Vec<Violation>> {
104        validate(&chart)?;
105        Ok(Self::build(chart))
106    }
107
108    fn build(chart: Chart) -> Self {
109        let flat = Flat::new(&chart);
110        let n = flat.states.len() + 1;
111        let mut states: Vec<CState> = Vec::with_capacity(n);
112        let mut by_id = BTreeMap::new();
113        states.push(CState {
114            id: String::new(),
115            kind: StateKind::Compound,
116            parent: None,
117            last: n - 1,
118            children: Vec::new(),
119            history: Vec::new(),
120            transitions: Vec::new(),
121            initial: None,
122            onentry: Vec::new(),
123            onexit: Vec::new(),
124            data: chart.data.clone(),
125            invokes: Vec::new(),
126            donedata: None,
127        });
128        for (i, s) in flat.states.iter().enumerate() {
129            let idx = i + 1;
130            let parent = flat.parent[i].map(|p| p + 1).unwrap_or(ROOT);
131            by_id.insert(s.id.clone(), idx);
132            states.push(CState {
133                id: s.id.clone(),
134                kind: s.kind(),
135                parent: Some(parent),
136                last: flat.last[i] + 1,
137                children: Vec::new(),
138                history: Vec::new(),
139                transitions: Vec::new(),
140                initial: None,
141                onentry: s.onentry.clone(),
142                onexit: s.onexit.clone(),
143                data: s.data.clone(),
144                invokes: s.invokes.clone(),
145                donedata: s.donedata.clone(),
146            });
147            if matches!(s.element, StateElement::History(_)) {
148                states[parent].history.push(idx);
149            } else {
150                states[parent].children.push(idx);
151            }
152        }
153        let resolve = |ids: &[&str]| -> Vec<StateIdx> {
154            ids.iter()
155                .filter_map(|id| by_id.get(*id).copied())
156                .collect()
157        };
158
159        let mut transitions: Vec<CTransition> = Vec::new();
160        // Root default entry.
161        let root_init = resolve_root_initial(&chart);
162        transitions.push(CTransition {
163            source: ROOT,
164            index: None,
165            events: Vec::new(),
166            cond: None,
167            targets: resolve(&root_init.targets),
168            internal: true,
169            body: Block::new(),
170            domain: Domain::Static(ROOT),
171        });
172        states[ROOT].initial = Some(0);
173
174        for (i, s) in flat.states.iter().enumerate() {
175            let idx = i + 1;
176            if s.kind() == StateKind::Compound {
177                let r = resolve_initial(s);
178                let t = transitions.len();
179                transitions.push(CTransition {
180                    source: idx,
181                    index: None,
182                    events: Vec::new(),
183                    cond: None,
184                    targets: resolve(&r.targets),
185                    internal: true,
186                    body: r.body.cloned().unwrap_or_default(),
187                    domain: Domain::Static(idx),
188                });
189                states[idx].initial = Some(t);
190            }
191            for (ti, tr) in s.transitions.iter().enumerate() {
192                let t = transitions.len();
193                transitions.push(CTransition {
194                    source: idx,
195                    index: Some(ti),
196                    events: tr.events.clone(),
197                    cond: tr.cond.clone(),
198                    targets: tr
199                        .targets
200                        .iter()
201                        .filter_map(|id| by_id.get(id.as_str()).copied())
202                        .collect(),
203                    internal: tr.kind == TransitionType::Internal,
204                    body: tr.body.clone(),
205                    domain: Domain::Targetless,
206                });
207                states[idx].transitions.push(t);
208            }
209        }
210
211        // A history state without a default transition defaults to its parent's default entry
212        // (compound parent) or to all regions (parallel parent).
213        for h in 0..states.len() {
214            if matches!(states[h].kind, StateKind::History(_)) && states[h].transitions.is_empty() {
215                let p = states[h].parent.unwrap_or(ROOT);
216                let targets = match states[p].initial {
217                    Some(ti) => transitions[ti].targets.clone(),
218                    None => states[p].children.clone(),
219                };
220                let t = transitions.len();
221                transitions.push(CTransition {
222                    source: h,
223                    index: None,
224                    events: Vec::new(),
225                    cond: None,
226                    targets,
227                    internal: false,
228                    body: Block::new(),
229                    domain: Domain::Targetless,
230                });
231                states[h].transitions.push(t);
232            }
233        }
234
235        let mut cc = CompiledChart {
236            chart,
237            states,
238            transitions,
239            by_id,
240        };
241        // Precompute domains that do not depend on history.
242        let empty = kernel::History::new(cc.states.len());
243        for t in 0..cc.transitions.len() {
244            let tr = &cc.transitions[t];
245            // Default-entry transitions keep their owning state as domain.
246            let default_entry =
247                tr.index.is_none() && !matches!(cc.states[tr.source].kind, StateKind::History(_));
248            if default_entry {
249                continue;
250            }
251            let domain = if tr.targets.is_empty() {
252                Domain::Targetless
253            } else if tr
254                .targets
255                .iter()
256                .any(|s| matches!(cc.states[*s].kind, StateKind::History(_)))
257            {
258                Domain::Dynamic
259            } else {
260                match kernel::compute_domain(&cc, &empty, t) {
261                    Some(d) => Domain::Static(d),
262                    None => Domain::Targetless,
263                }
264            };
265            cc.transitions[t].domain = domain;
266        }
267        cc
268    }
269
270    /// The IR this chart was compiled from.
271    pub fn chart(&self) -> &Chart {
272        &self.chart
273    }
274
275    /// The datamodel name the chart requires (`"null"` when it names none).
276    pub fn datamodel(&self) -> &str {
277        if self.chart.datamodel.is_empty() {
278            "null"
279        } else {
280            &self.chart.datamodel
281        }
282    }
283
284    /// The binding mode.
285    pub fn binding(&self) -> Binding {
286        self.chart.binding
287    }
288
289    /// All states; index [`ROOT`] is the root.
290    pub fn states(&self) -> &[CState] {
291        &self.states
292    }
293
294    /// One state.
295    pub fn state(&self, i: StateIdx) -> &CState {
296        &self.states[i]
297    }
298
299    /// All transitions.
300    pub fn transitions(&self) -> &[CTransition] {
301        &self.transitions
302    }
303
304    /// One transition.
305    pub fn transition(&self, t: TransIdx) -> &CTransition {
306        &self.transitions[t]
307    }
308
309    /// The number of states including the root.
310    pub fn len(&self) -> usize {
311        self.states.len()
312    }
313
314    /// Whether the chart has no states besides the root (never true for a valid chart).
315    pub fn is_empty(&self) -> bool {
316        self.states.len() <= 1
317    }
318
319    /// The index of the state with this identifier.
320    pub fn index_of(&self, id: &str) -> Option<StateIdx> {
321        self.by_id.get(id).copied()
322    }
323
324    /// Whether `d` is a proper descendant of `a`.
325    pub fn is_descendant(&self, d: StateIdx, a: StateIdx) -> bool {
326        a < d && d <= self.states[a].last
327    }
328
329    /// The resolved default entry of a compound state or the root, as state indices.
330    pub fn default_entry(&self, s: StateIdx) -> &[StateIdx] {
331        match self.states[s].initial {
332            Some(t) => &self.transitions[t].targets,
333            None => &[],
334        }
335    }
336
337    /// An empty configuration sized for this chart.
338    pub fn empty_set(&self) -> StateSet {
339        StateSet::new(self.states.len())
340    }
341
342    /// State identifiers of a set, in document order.
343    pub fn ids(&self, set: &StateSet) -> Vec<String> {
344        set.to_vec()
345            .into_iter()
346            .map(|i| self.states[i].id.clone())
347            .collect()
348    }
349}
vertep_core/compile.rs

vertep_core/
compile.rs
