bombay_transition/
machine.rs

1//! Statically composed, structurally representable executable machines.
2
3/// Compact identity of a topology vertex.
4#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
5pub struct VertexId(pub u8);
6
7/// Compact identity of an input trigger.
8#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
9pub struct TriggerId(pub u8);
10
11/// One named topology vertex.
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub struct Vertex {
14    /// Identity used by execution and structural interpreters.
15    pub id: VertexId,
16    /// Human-readable label used only by renderers.
17    pub label: &'static str,
18}
19
20/// One declared edge in a base machine's topology.
21#[derive(Debug, Clone, Copy, PartialEq, Eq)]
22pub struct Transition {
23    /// Source vertex identity.
24    pub from: VertexId,
25    /// Input identity selecting the edge.
26    pub trigger: TriggerId,
27    /// Destination vertex identity.
28    pub to: VertexId,
29    /// Human-readable trigger label used only by renderers.
30    pub label: &'static str,
31}
32
33/// Inspectable metadata for one indivisible machine.
34#[derive(Debug, Clone, Copy, PartialEq, Eq)]
35pub struct Topology {
36    /// Stable component name.
37    pub name: &'static str,
38    /// Initial vertex.
39    pub initial: VertexId,
40    /// Declared vertices.
41    pub vertices: &'static [Vertex],
42    /// Declared transition graph.
43    pub transitions: &'static [Transition],
44}
45
46/// Topology whose identities, references, and reachability were validated.
47#[derive(Debug, Clone, Copy, PartialEq, Eq)]
48pub struct ValidatedTopology(Topology);
49
50impl ValidatedTopology {
51    /// Borrow the validated descriptive topology.
52    #[must_use]
53    pub const fn topology(self) -> Topology {
54        self.0
55    }
56}
57
58/// Structural defect found in a topology.
59#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
60pub enum TopologyError {
61    /// Two vertices have the same identity.
62    #[error("two vertices share an identity")]
63    DuplicateVertex(VertexId),
64    /// Two edges share a source vertex and trigger.
65    #[error("two transitions share a source and trigger")]
66    DuplicateTransition(Transition),
67    /// The initial identity is not a declared vertex.
68    #[error("initial identity is not a declared vertex")]
69    UnknownInitial(VertexId),
70    /// An edge refers to an undeclared vertex.
71    #[error("transition refers to an undeclared vertex")]
72    UnknownVertex(VertexId),
73    /// A declared vertex cannot be reached from the initial vertex.
74    #[error("declared vertex is unreachable from the initial vertex")]
75    UnreachableVertex(VertexId),
76}
77
78impl Topology {
79    /// Validate and retain this topology for executable machine construction.
80    ///
81    /// # Errors
82    ///
83    /// Returns the first structural defect in declaration order.
84    pub fn validated(self) -> Result<ValidatedTopology, TopologyError> {
85        self.validate()?;
86        Ok(ValidatedTopology(self))
87    }
88
89    /// Validate identity uniqueness, references, initial state, and reachability.
90    ///
91    /// Validation uses fixed stack storage because vertex identities are bytes;
92    /// it performs no allocation and is suitable for `no_std` interpreters.
93    ///
94    /// # Errors
95    ///
96    /// Returns the first uniqueness, reference, initial-state, or reachability
97    /// defect encountered in deterministic declaration order.
98    pub fn validate(self) -> Result<(), TopologyError> {
99        for (index, vertex) in self.vertices.iter().enumerate() {
100            if self.vertices[..index]
101                .iter()
102                .any(|known| known.id == vertex.id)
103            {
104                return Err(TopologyError::DuplicateVertex(vertex.id));
105            }
106        }
107        if !self.vertices.iter().any(|vertex| vertex.id == self.initial) {
108            return Err(TopologyError::UnknownInitial(self.initial));
109        }
110        for (index, edge) in self.transitions.iter().enumerate() {
111            if self.transitions[..index]
112                .iter()
113                .any(|known| known.from == edge.from && known.trigger == edge.trigger)
114            {
115                return Err(TopologyError::DuplicateTransition(*edge));
116            }
117            for vertex in [edge.from, edge.to] {
118                if !self.vertices.iter().any(|known| known.id == vertex) {
119                    return Err(TopologyError::UnknownVertex(vertex));
120                }
121            }
122        }
123        let mut reachable = [false; 256];
124        reachable[usize::from(self.initial.0)] = true;
125        for _ in 0..self.vertices.len() {
126            for edge in self.transitions {
127                if reachable[usize::from(edge.from.0)] {
128                    reachable[usize::from(edge.to.0)] = true;
129                }
130            }
131        }
132        self.vertices
133            .iter()
134            .find(|vertex| !reachable[usize::from(vertex.id.0)])
135            .map_or(Ok(()), |vertex| {
136                Err(TopologyError::UnreachableVertex(vertex.id))
137            })
138    }
139
140    /// Render a deterministic Mermaid state diagram into any formatting sink.
141    ///
142    /// # Errors
143    ///
144    /// Returns a formatting error from the sink or when an edge references an
145    /// unknown vertex. [`Self::validate`] diagnoses the latter precisely.
146    pub fn write_mermaid(self, output: &mut impl core::fmt::Write) -> core::fmt::Result {
147        writeln!(output, "stateDiagram-v2")?;
148        let initial = self.label(self.initial).ok_or(core::fmt::Error)?;
149        writeln!(output, "    [*] --> {initial}")?;
150        self.transitions.iter().try_for_each(|edge| {
151            let from = self.label(edge.from).ok_or(core::fmt::Error)?;
152            let to = self.label(edge.to).ok_or(core::fmt::Error)?;
153            writeln!(output, "    {from} --> {to}: {}", edge.label)
154        })
155    }
156
157    fn label(self, id: VertexId) -> Option<&'static str> {
158        self.vertices
159            .iter()
160            .find(|vertex| vertex.id == id)
161            .map(|vertex| vertex.label)
162    }
163}
164
165/// A stateful transducer whose composition remains structurally inspectable.
166pub trait Machine {
167    /// Input consumed by one step.
168    type Input;
169
170    /// Output produced for one input.
171    type Output;
172
173    /// Consume one input and return the output plus successor machine.
174    fn step(self, input: Self::Input) -> (Self::Output, Self)
175    where
176        Self: Sized;
177
178    /// Fold the retained composition tree with a structural interpreter.
179    fn describe<V: Structure>(&self, visitor: &mut V) -> V::Output;
180}
181
182/// Structural composition operations available to every machine.
183pub trait Compose: Machine + Sized {
184    /// Compose this machine sequentially with another machine.
185    fn then<N>(self, next: N) -> Then<Self, N> {
186        Then(self, next)
187    }
188
189    /// Compose this machine in a product with another machine.
190    fn product<N>(self, other: N) -> Product<Self, N> {
191        Product(self, other)
192    }
193
194    /// Compose this machine as an alternative to another machine.
195    fn routed<N>(self, other: N) -> Routed<Self, N> {
196        Routed(self, other)
197    }
198}
199
200impl<M: Machine> Compose for M {}
201
202/// Interpreter for the composition structure of a machine.
203pub trait Structure {
204    /// Representation produced for each subtree.
205    type Output;
206
207    /// Interpret an indivisible machine.
208    fn base(&mut self, topology: Topology) -> Self::Output;
209
210    /// Interpret sequential composition.
211    fn then(&mut self, first: Self::Output, second: Self::Output) -> Self::Output;
212
213    /// Interpret product composition.
214    fn product(&mut self, left: Self::Output, right: Self::Output) -> Self::Output;
215
216    /// Interpret sum composition.
217    fn routed(&mut self, left: Self::Output, right: Self::Output) -> Self::Output;
218}
219
220/// An indivisible stateful machine and its inspectable topology.
221pub struct Base<S, F, I, O> {
222    state: S,
223    transition: F,
224    topology: ValidatedTopology,
225    signature: core::marker::PhantomData<fn(I) -> O>,
226}
227
228impl<S, F, I, O> Base<S, F, I, O> {
229    /// Construct a base machine from state, topology, and transition function.
230    pub const fn new(state: S, topology: ValidatedTopology, transition: F) -> Self {
231        Self {
232            state,
233            transition,
234            topology,
235            signature: core::marker::PhantomData,
236        }
237    }
238
239    /// Borrow the retained machine state.
240    #[must_use]
241    pub const fn state(&self) -> &S {
242        &self.state
243    }
244}
245
246impl<S, I, O, F> Machine for Base<S, F, I, O>
247where
248    F: FnMut(S, I) -> (O, S),
249{
250    type Input = I;
251    type Output = O;
252
253    fn step(self, input: Self::Input) -> (Self::Output, Self) {
254        let Self {
255            state,
256            mut transition,
257            topology,
258            signature,
259        } = self;
260        let (output, state) = transition(state, input);
261        (
262            output,
263            Self {
264                state,
265                transition,
266                topology,
267                signature,
268            },
269        )
270    }
271
272    fn describe<V: Structure>(&self, visitor: &mut V) -> V::Output {
273        visitor.base(self.topology.topology())
274    }
275}
276
277/// Sequential composition of two machines.
278pub struct Then<A, B>(A, B);
279
280impl<A, B> Machine for Then<A, B>
281where
282    A: Machine,
283    B: Machine<Input = A::Output>,
284{
285    type Input = A::Input;
286    type Output = B::Output;
287
288    fn step(self, input: Self::Input) -> (Self::Output, Self) {
289        let (middle, first) = self.0.step(input);
290        let (output, second) = self.1.step(middle);
291        (output, Self(first, second))
292    }
293
294    fn describe<V: Structure>(&self, visitor: &mut V) -> V::Output {
295        let first = self.0.describe(visitor);
296        let second = self.1.describe(visitor);
297        visitor.then(first, second)
298    }
299}
300
301/// Product composition of two independent machines.
302pub struct Product<A, B>(A, B);
303
304impl<A, B> Machine for Product<A, B>
305where
306    A: Machine,
307    B: Machine,
308{
309    type Input = (A::Input, B::Input);
310    type Output = (A::Output, B::Output);
311
312    fn step(self, (left, right): Self::Input) -> (Self::Output, Self) {
313        let (left_output, left_machine) = self.0.step(left);
314        let (right_output, right_machine) = self.1.step(right);
315        (
316            (left_output, right_output),
317            Self(left_machine, right_machine),
318        )
319    }
320
321    fn describe<V: Structure>(&self, visitor: &mut V) -> V::Output {
322        let left = self.0.describe(visitor);
323        let right = self.1.describe(visitor);
324        visitor.product(left, right)
325    }
326}
327
328/// One of two alternatives.
329#[derive(Debug, Clone, Copy, PartialEq, Eq)]
330pub enum Either<L, R> {
331    /// Left alternative.
332    Left(L),
333    /// Right alternative.
334    Right(R),
335}
336
337/// Sum composition routing each alternative to its corresponding machine.
338pub struct Routed<A, B>(A, B);
339
340impl<A, B> Machine for Routed<A, B>
341where
342    A: Machine,
343    B: Machine,
344{
345    type Input = Either<A::Input, B::Input>;
346    type Output = Either<A::Output, B::Output>;
347
348    fn step(self, input: Self::Input) -> (Self::Output, Self) {
349        match input {
350            Either::Left(left) => {
351                let (output, machine) = self.0.step(left);
352                (Either::Left(output), Self(machine, self.1))
353            }
354            Either::Right(right) => {
355                let (output, machine) = self.1.step(right);
356                (Either::Right(output), Self(self.0, machine))
357            }
358        }
359    }
360
361    fn describe<V: Structure>(&self, visitor: &mut V) -> V::Output {
362        let left = self.0.describe(visitor);
363        let right = self.1.describe(visitor);
364        visitor.routed(left, right)
365    }
366}
367
368#[cfg(test)]
369mod tests {
370    use alloc::string::ToString;
371
372    use super::{
373        Base, Compose, Machine, Structure, Topology, TopologyError, Transition, TriggerId, Vertex,
374        VertexId,
375    };
376
377    #[test]
378    fn topology_error_reports_each_defect() {
379        assert_eq!(
380            TopologyError::DuplicateVertex(READY).to_string(),
381            "two vertices share an identity"
382        );
383        assert_eq!(
384            TopologyError::UnknownInitial(READY).to_string(),
385            "initial identity is not a declared vertex"
386        );
387        assert_eq!(
388            TopologyError::UnknownVertex(READY).to_string(),
389            "transition refers to an undeclared vertex"
390        );
391        assert_eq!(
392            TopologyError::UnreachableVertex(READY).to_string(),
393            "declared vertex is unreachable from the initial vertex"
394        );
395        assert_eq!(
396            TopologyError::DuplicateTransition(EDGES[0]).to_string(),
397            "two transitions share a source and trigger"
398        );
399    }
400
401    const READY: VertexId = VertexId(0);
402    const VERTICES: &[Vertex] = &[Vertex {
403        id: READY,
404        label: "ready",
405    }];
406
407    const EDGES: &[Transition] = &[Transition {
408        from: READY,
409        trigger: TriggerId(0),
410        to: READY,
411        label: "advance",
412    }];
413    const UNKNOWN: VertexId = VertexId(9);
414    const UNKNOWN_EDGE: &[Transition] = &[Transition {
415        from: READY,
416        trigger: TriggerId(1),
417        to: UNKNOWN,
418        label: "lost",
419    }];
420    const STRANDED: VertexId = VertexId(1);
421    const STRANDED_VERTICES: &[Vertex] = &[
422        VERTICES[0],
423        Vertex {
424            id: STRANDED,
425            label: "stranded",
426        },
427    ];
428    const DUPLICATE_EDGES: &[Transition] = &[EDGES[0], EDGES[0]];
429    const AMBIGUOUS: &[Transition] = &[
430        EDGES[0],
431        Transition {
432            from: READY,
433            trigger: TriggerId(0),
434            to: STRANDED,
435            label: "different presentation",
436        },
437    ];
438
439    fn topology(name: &'static str) -> Topology {
440        Topology {
441            name,
442            initial: READY,
443            vertices: VERTICES,
444            transitions: EDGES,
445        }
446    }
447
448    #[derive(Debug, PartialEq, Eq)]
449    struct Shape {
450        bases: usize,
451        sequences: usize,
452        products: usize,
453        choices: usize,
454    }
455
456    struct Count;
457
458    impl Structure for Count {
459        type Output = Shape;
460
461        fn base(&mut self, _topology: Topology) -> Self::Output {
462            Shape {
463                bases: 1,
464                sequences: 0,
465                products: 0,
466                choices: 0,
467            }
468        }
469
470        fn then(&mut self, first: Self::Output, second: Self::Output) -> Self::Output {
471            Shape {
472                bases: first.bases + second.bases,
473                sequences: first.sequences + second.sequences + 1,
474                products: first.products + second.products,
475                choices: first.choices + second.choices,
476            }
477        }
478
479        fn product(&mut self, left: Self::Output, right: Self::Output) -> Self::Output {
480            Shape {
481                bases: left.bases + right.bases,
482                sequences: left.sequences + right.sequences,
483                products: left.products + right.products + 1,
484                choices: left.choices + right.choices,
485            }
486        }
487
488        fn routed(&mut self, left: Self::Output, right: Self::Output) -> Self::Output {
489            Shape {
490                bases: left.bases + right.bases,
491                sequences: left.sequences + right.sequences,
492                products: left.products + right.products,
493                choices: left.choices + right.choices + 1,
494            }
495        }
496    }
497
498    #[test]
499    fn sequential_machine_executes_and_retains_its_structure() {
500        let increment = Base::new(
501            0_u8,
502            topology("increment").validated().unwrap(),
503            |state: u8, input: u8| {
504                let state = state + input;
505                (state, state)
506            },
507        );
508        let double = Base::new(
509            (),
510            topology("double").validated().unwrap(),
511            |(), input: u8| (input * 2, ()),
512        );
513        let machine = increment.then(double);
514
515        let (output, machine) = machine.step(3);
516        assert_eq!(output, 6);
517        let (output, machine) = machine.step(1);
518        assert_eq!(output, 8);
519        assert_eq!(
520            machine.describe(&mut Count),
521            Shape {
522                bases: 2,
523                sequences: 1,
524                products: 0,
525                choices: 0,
526            }
527        );
528    }
529
530    #[test]
531    fn topology_validation_rejects_each_structural_defect() {
532        const DUPLICATE_VERTICES: &[Vertex] = &[
533            Vertex {
534                id: READY,
535                label: "ready",
536            },
537            Vertex {
538                id: READY,
539                label: "again",
540            },
541        ];
542        assert_eq!(
543            Topology {
544                name: "duplicate",
545                initial: READY,
546                vertices: DUPLICATE_VERTICES,
547                transitions: &[]
548            }
549            .validate(),
550            Err(super::TopologyError::DuplicateVertex(READY))
551        );
552
553        assert_eq!(
554            Topology {
555                name: "initial",
556                initial: UNKNOWN,
557                vertices: VERTICES,
558                transitions: &[]
559            }
560            .validate(),
561            Err(super::TopologyError::UnknownInitial(UNKNOWN))
562        );
563
564        assert_eq!(
565            Topology {
566                name: "reference",
567                initial: READY,
568                vertices: VERTICES,
569                transitions: UNKNOWN_EDGE
570            }
571            .validate(),
572            Err(super::TopologyError::UnknownVertex(UNKNOWN))
573        );
574
575        assert_eq!(
576            Topology {
577                name: "reachability",
578                initial: READY,
579                vertices: STRANDED_VERTICES,
580                transitions: &[]
581            }
582            .validate(),
583            Err(super::TopologyError::UnreachableVertex(STRANDED))
584        );
585
586        assert_eq!(
587            Topology {
588                name: "edge",
589                initial: READY,
590                vertices: VERTICES,
591                transitions: DUPLICATE_EDGES
592            }
593            .validate(),
594            Err(super::TopologyError::DuplicateTransition(EDGES[0]))
595        );
596
597        assert_eq!(
598            Topology {
599                name: "ambiguous",
600                initial: READY,
601                vertices: STRANDED_VERTICES,
602                transitions: AMBIGUOUS,
603            }
604            .validate(),
605            Err(super::TopologyError::DuplicateTransition(AMBIGUOUS[1]))
606        );
607    }
608
609    #[test]
610    fn product_and_routed_composition_preserve_untouched_affine_state() {
611        struct Affine(u8);
612
613        let left = Base::new(
614            Affine(1),
615            topology("left").validated().unwrap(),
616            |state: Affine, input: u8| (state.0 + input, Affine(state.0 + input)),
617        );
618        let right = Base::new(
619            Affine(10),
620            topology("right").validated().unwrap(),
621            |state: Affine, input: u8| (state.0 + input, Affine(state.0 + input)),
622        );
623        let (output, product) = left.product(right).step((2, 3));
624        assert_eq!(output, (3, 13));
625
626        let left = Base::new(
627            Affine(1),
628            topology("left").validated().unwrap(),
629            |state: Affine, input: u8| (state.0 + input, Affine(state.0 + input)),
630        );
631        let right = Base::new(
632            Affine(10),
633            topology("right").validated().unwrap(),
634            |state: Affine, input: u8| (state.0 + input, Affine(state.0 + input)),
635        );
636        let (output, routed) = left.routed(right).step(super::Either::Left(2));
637        assert_eq!(output, super::Either::Left(3));
638        let (output, _) = routed.step(super::Either::Right(3));
639        assert_eq!(output, super::Either::Right(13));
640        assert_eq!(product.describe(&mut Count).products, 1);
641    }
642}
bombay_transition/machine.rs

bombay_transition/
machine.rs
