telltale_runtime/effects/
algebra.rs

1// Free algebra for choreographic effects
2//
3// This module provides a data representation of choreographic programs
4// that can be analyzed, transformed, and interpreted separately from execution.
5
6use crate::effects::extension::ExtensionEffect;
7use crate::effects::{MessageTag, RoleId};
8use std::any::TypeId;
9use std::time::Duration;
10
11#[path = "algebra_program_analysis.rs"]
12mod program_analysis;
13pub use program_analysis::{InterpretResult, InterpreterState, ProgramError, ProgramMessage};
14
15/// A choreographic effect that can be performed by a role
16#[derive(Debug)]
17pub enum Effect<R: RoleId, M> {
18    /// Send a message to another role
19    Send { to: R, msg: M },
20
21    /// Receive a message from another role
22    Recv { from: R, msg_tag: MessageTag },
23
24    /// Make an internal choice and broadcast the label
25    Choose { at: R, label: <R as RoleId>::Label },
26
27    /// Wait for an external choice from another role
28    Offer { from: R },
29
30    /// Branch based on a choice - includes all possible continuations
31    /// The choosing role has already selected via Choose effect
32    /// Other roles use Offer to receive the label, then select matching branch
33    Branch {
34        choosing_role: R,
35        branches: Vec<(<R as RoleId>::Label, Program<R, M>)>,
36    },
37
38    /// Loop that executes body a fixed number of times or until a condition
39    Loop {
40        /// Number of iterations (None = infinite/until break)
41        iterations: Option<usize>,
42        body: Box<Program<R, M>>,
43    },
44
45    /// Execute a sub-program with a timeout
46    ///
47    /// If `on_timeout` is Some, executes that program when timeout occurs.
48    /// Otherwise, the handler decides what to do on timeout (typically error).
49    Timeout {
50        at: R,
51        dur: Duration,
52        body: Box<Program<R, M>>,
53        /// Optional fallback program to execute if timeout occurs
54        on_timeout: Option<Box<Program<R, M>>>,
55    },
56
57    /// Execute multiple programs using deterministic normalized ordering.
58    ///
59    /// The interpreter executes sub-programs in declaration order. This keeps
60    /// behavior reproducible across runtimes while preserving the high-level
61    /// "parallel composition" intent.
62    Parallel { programs: Vec<Program<R, M>> },
63
64    /// Extension effect for domain-specific operations
65    ///
66    /// Extensions are boxed trait objects that implement `ExtensionEffect`.
67    /// Use `Effect::ext()` or `Program::ext()` for construction.
68    ///
69    /// # Type Safety
70    ///
71    /// Extensions are identified by `TypeId` and use trait object downcasting
72    /// for type-safe access. Unknown extensions cause runtime errors (fail-fast).
73    ///
74    /// # Projection
75    ///
76    /// Extensions project based on `participating_roles()`:
77    /// - Empty roles → appears in all projections
78    /// - Non-empty → appears only in specified role projections
79    Extension(Box<dyn ExtensionEffect<R>>),
80
81    /// End of program
82    End,
83}
84
85impl<R: RoleId, M: Clone> Clone for Effect<R, M> {
86    fn clone(&self) -> Self {
87        match self {
88            Effect::Send { to, msg } => Effect::Send {
89                to: *to,
90                msg: msg.clone(),
91            },
92            Effect::Recv { from, msg_tag } => Effect::Recv {
93                from: *from,
94                msg_tag: *msg_tag,
95            },
96            Effect::Choose { at, label } => Effect::Choose {
97                at: *at,
98                label: *label,
99            },
100            Effect::Offer { from } => Effect::Offer { from: *from },
101            Effect::Branch {
102                choosing_role,
103                branches,
104            } => Effect::Branch {
105                choosing_role: *choosing_role,
106                branches: branches.clone(),
107            },
108            Effect::Loop { iterations, body } => Effect::Loop {
109                iterations: *iterations,
110                body: body.clone(),
111            },
112            Effect::Timeout {
113                at,
114                dur,
115                body,
116                on_timeout,
117            } => Effect::Timeout {
118                at: *at,
119                dur: *dur,
120                body: body.clone(),
121                on_timeout: on_timeout.clone(),
122            },
123            Effect::Parallel { programs } => Effect::Parallel {
124                programs: programs.clone(),
125            },
126            Effect::Extension(ext) => Effect::Extension(ext.clone_box()),
127            Effect::End => Effect::End,
128        }
129    }
130}
131
132/// A choreographic program as a sequence of effects
133#[derive(Debug, Clone)]
134pub struct Program<R: RoleId, M> {
135    effects: Vec<Effect<R, M>>,
136}
137
138/// Builder for choreographic programs that enforces structural invariants.
139#[derive(Debug, Clone)]
140pub struct ProgramBuilder<R: RoleId, M> {
141    effects: Vec<Effect<R, M>>,
142    ended: bool,
143}
144
145impl<R: RoleId, M> Program<R, M> {
146    /// Create a new program builder.
147    #[must_use]
148    #[allow(clippy::new_ret_no_self)]
149    pub fn new() -> ProgramBuilder<R, M> {
150        ProgramBuilder::new()
151    }
152
153    /// Create a new program builder.
154    #[must_use]
155    pub fn builder() -> ProgramBuilder<R, M> {
156        ProgramBuilder::new()
157    }
158
159    /// Construct a program from effects after validation.
160    fn from_effects(effects: Vec<Effect<R, M>>) -> Result<Self, ProgramError> {
161        let program = Self { effects };
162        program.validate()?;
163        Ok(program)
164    }
165
166    /// Borrow the program's effects.
167    #[must_use]
168    pub fn effects(&self) -> &[Effect<R, M>] {
169        &self.effects
170    }
171
172    /// Consume the program and return its effects.
173    #[must_use]
174    pub fn into_effects(self) -> Vec<Effect<R, M>> {
175        self.effects
176    }
177
178    /// Extend this program with another program.
179    ///
180    /// If `self` ends with `Effect::End`, that terminal marker is removed before
181    /// appending `other`, so composition preserves the single-terminal-`End`
182    /// invariant.
183    ///
184    /// # Panics
185    ///
186    /// Panics only if the composed program violates structural invariants. Use
187    /// `try_then` for fallible composition.
188    #[must_use]
189    pub fn then(self, other: Program<R, M>) -> Program<R, M> {
190        self.try_then(other)
191            .unwrap_or_else(|err| panic!("invalid program composition: {err}"))
192    }
193
194    /// Fallible version of [`Program::then`].
195    pub fn try_then(self, other: Program<R, M>) -> Result<Program<R, M>, ProgramError> {
196        let mut effects = self.effects;
197        if matches!(effects.last(), Some(Effect::End)) {
198            effects.pop();
199        }
200        effects.extend(other.effects);
201        Program::from_effects(effects)
202    }
203
204    /// Check if the program is empty.
205    #[must_use]
206    pub fn is_empty(&self) -> bool {
207        self.effects.is_empty()
208    }
209
210    /// Get the length of the program (number of effects).
211    #[must_use]
212    pub fn len(&self) -> usize {
213        self.effects.len()
214    }
215}
216
217impl<R: RoleId, M> Default for ProgramBuilder<R, M> {
218    fn default() -> Self {
219        Self::new()
220    }
221}
222
223impl<R: RoleId, M> ProgramBuilder<R, M> {
224    /// Create a new empty builder.
225    #[must_use]
226    pub fn new() -> Self {
227        Self {
228            effects: Vec::new(),
229            ended: false,
230        }
231    }
232
233    /// Push an effect onto the builder.
234    fn try_push(&mut self, effect: Effect<R, M>) -> Result<(), ProgramError> {
235        if self.ended {
236            return Err(ProgramError::InvalidStructure(
237                "cannot add effects after end".to_string(),
238            ));
239        }
240        if matches!(effect, Effect::End) {
241            self.ended = true;
242        }
243        self.effects.push(effect);
244        Ok(())
245    }
246
247    /// Fallible `send`.
248    pub fn try_send(mut self, to: R, msg: M) -> Result<Self, ProgramError> {
249        self.try_push(Effect::Send { to, msg })?;
250        Ok(self)
251    }
252
253    /// Add a send effect.
254    pub fn send(mut self, to: R, msg: M) -> Self {
255        self = self
256            .try_send(to, msg)
257            .unwrap_or_else(|err| panic!("invalid send composition: {err}"));
258        self
259    }
260
261    /// Fallible `recv`.
262    pub fn try_recv<T: 'static>(mut self, from: R) -> Result<Self, ProgramError> {
263        self.try_push(Effect::Recv {
264            from,
265            msg_tag: MessageTag::of::<T>(),
266        })?;
267        Ok(self)
268    }
269
270    /// Add a receive effect.
271    pub fn recv<T: 'static>(mut self, from: R) -> Self {
272        self = self
273            .try_recv::<T>(from)
274            .unwrap_or_else(|err| panic!("invalid recv composition: {err}"));
275        self
276    }
277
278    /// Fallible `choose`.
279    pub fn try_choose(mut self, at: R, label: <R as RoleId>::Label) -> Result<Self, ProgramError> {
280        self.try_push(Effect::Choose { at, label })?;
281        Ok(self)
282    }
283
284    /// Add a choice effect.
285    pub fn choose(mut self, at: R, label: <R as RoleId>::Label) -> Self {
286        self = self
287            .try_choose(at, label)
288            .unwrap_or_else(|err| panic!("invalid choose composition: {err}"));
289        self
290    }
291
292    /// Fallible `offer`.
293    pub fn try_offer(mut self, from: R) -> Result<Self, ProgramError> {
294        self.try_push(Effect::Offer { from })?;
295        Ok(self)
296    }
297
298    /// Add an offer effect.
299    pub fn offer(mut self, from: R) -> Self {
300        self = self
301            .try_offer(from)
302            .unwrap_or_else(|err| panic!("invalid offer composition: {err}"));
303        self
304    }
305
306    /// Fallible `with_timeout`.
307    pub fn try_with_timeout(
308        mut self,
309        at: R,
310        dur: Duration,
311        body: Program<R, M>,
312    ) -> Result<Self, ProgramError> {
313        self.try_push(Effect::Timeout {
314            at,
315            dur,
316            body: Box::new(body),
317            on_timeout: None,
318        })?;
319        Ok(self)
320    }
321
322    /// Add a timeout effect.
323    pub fn with_timeout(mut self, at: R, dur: Duration, body: Program<R, M>) -> Self {
324        self = self
325            .try_with_timeout(at, dur, body)
326            .unwrap_or_else(|err| panic!("invalid timeout composition: {err}"));
327        self
328    }
329
330    /// Add a timed choice effect - races body against timeout.
331    ///
332    /// If body completes before timeout, executes body.
333    /// If timeout fires first, executes on_timeout instead.
334    /// This is the effect-level representation of timed_choice syntax.
335    pub fn with_timed_choice(
336        mut self,
337        at: R,
338        dur: Duration,
339        body: Program<R, M>,
340        on_timeout: Program<R, M>,
341    ) -> Self {
342        self.try_push(Effect::Timeout {
343            at,
344            dur,
345            body: Box::new(body),
346            on_timeout: Some(Box::new(on_timeout)),
347        })
348        .unwrap_or_else(|err| panic!("invalid timed choice composition: {err}"));
349        self
350    }
351
352    /// Add a parallel composition effect.
353    pub fn try_parallel(mut self, programs: Vec<Program<R, M>>) -> Result<Self, ProgramError> {
354        self.try_push(Effect::Parallel { programs })?;
355        Ok(self)
356    }
357
358    /// Add a parallel composition effect.
359    #[must_use]
360    pub fn parallel(mut self, programs: Vec<Program<R, M>>) -> Self {
361        self = self
362            .try_parallel(programs)
363            .unwrap_or_else(|err| panic!("invalid parallel composition: {err}"));
364        self
365    }
366
367    /// Add a branch effect with multiple labeled continuations.
368    pub fn try_branch(
369        mut self,
370        choosing_role: R,
371        branches: Vec<(<R as RoleId>::Label, Program<R, M>)>,
372    ) -> Result<Self, ProgramError> {
373        self.try_push(Effect::Branch {
374            choosing_role,
375            branches,
376        })?;
377        Ok(self)
378    }
379
380    /// Add a branch effect with multiple labeled continuations.
381    pub fn branch(
382        mut self,
383        choosing_role: R,
384        branches: Vec<(<R as RoleId>::Label, Program<R, M>)>,
385    ) -> Self {
386        self = self
387            .try_branch(choosing_role, branches)
388            .unwrap_or_else(|err| panic!("invalid branch composition: {err}"));
389        self
390    }
391
392    /// Add a loop effect.
393    pub fn try_loop_n(
394        mut self,
395        iterations: usize,
396        body: Program<R, M>,
397    ) -> Result<Self, ProgramError> {
398        self.try_push(Effect::Loop {
399            iterations: Some(iterations),
400            body: Box::new(body),
401        })?;
402        Ok(self)
403    }
404
405    /// Add a loop effect.
406    #[must_use]
407    pub fn loop_n(mut self, iterations: usize, body: Program<R, M>) -> Self {
408        self = self
409            .try_loop_n(iterations, body)
410            .unwrap_or_else(|err| panic!("invalid loop composition: {err}"));
411        self
412    }
413
414    /// Add an infinite loop effect (or until break).
415    pub fn try_loop_inf(mut self, body: Program<R, M>) -> Result<Self, ProgramError> {
416        self.try_push(Effect::Loop {
417            iterations: None,
418            body: Box::new(body),
419        })?;
420        Ok(self)
421    }
422
423    /// Add an infinite loop effect (or until break).
424    #[must_use]
425    pub fn loop_inf(mut self, body: Program<R, M>) -> Self {
426        self = self
427            .try_loop_inf(body)
428            .unwrap_or_else(|err| panic!("invalid infinite loop composition: {err}"));
429        self
430    }
431
432    /// Add a domain-specific extension effect.
433    pub fn try_ext<E: ExtensionEffect<R> + 'static>(
434        mut self,
435        extension: E,
436    ) -> Result<Self, ProgramError> {
437        self.try_push(Effect::Extension(Box::new(extension)))?;
438        Ok(self)
439    }
440
441    /// Add a domain-specific extension effect.
442    pub fn ext<E: ExtensionEffect<R> + 'static>(mut self, extension: E) -> Self {
443        self = self
444            .try_ext(extension)
445            .unwrap_or_else(|err| panic!("invalid extension composition: {err}"));
446        self
447    }
448
449    /// Add multiple extension effects.
450    pub fn try_exts<E: ExtensionEffect<R> + 'static>(
451        mut self,
452        extensions: impl IntoIterator<Item = E>,
453    ) -> Result<Self, ProgramError> {
454        for ext in extensions {
455            self.try_push(Effect::Extension(Box::new(ext)))?;
456        }
457        Ok(self)
458    }
459
460    /// Add multiple extension effects.
461    pub fn exts<E: ExtensionEffect<R> + 'static>(
462        mut self,
463        extensions: impl IntoIterator<Item = E>,
464    ) -> Self {
465        self = self
466            .try_exts(extensions)
467            .unwrap_or_else(|err| panic!("invalid extension sequence composition: {err}"));
468        self
469    }
470
471    /// Mark the end of the program and finalize it.
472    ///
473    /// Prefer [`ProgramBuilder::try_end`] for fallible construction.
474    pub fn end(self) -> Program<R, M> {
475        self.try_end()
476            .unwrap_or_else(|err| panic!("invalid program: {err}"))
477    }
478
479    /// Fallible variant of [`ProgramBuilder::end`].
480    pub fn try_end(mut self) -> Result<Program<R, M>, ProgramError> {
481        self.try_push(Effect::End)?;
482        self.build()
483    }
484
485    /// Validate and build the program without appending `End`.
486    pub fn build(self) -> Result<Program<R, M>, ProgramError> {
487        Program::from_effects(self.effects)
488    }
489}
490
491impl<R: RoleId, M> Default for Program<R, M> {
492    /// Returns an empty program with no effects.
493    ///
494    /// An empty program is always valid, so this cannot fail.
495    fn default() -> Self {
496        // Empty program is always valid - no panic possible
497        Self {
498            effects: Vec::new(),
499        }
500    }
501}
502
503/// Extension effect helper methods
504impl<R: RoleId, M> Effect<R, M> {
505    /// Create an extension effect from any type implementing `ExtensionEffect`
506    pub fn ext<E: ExtensionEffect<R> + 'static>(extension: E) -> Self {
507        Effect::Extension(Box::new(extension))
508    }
509
510    /// Check if this is an extension effect of a specific type
511    pub fn is_extension<E: ExtensionEffect<R> + 'static>(&self) -> bool {
512        match self {
513            Effect::Extension(ext) => ext.type_id() == TypeId::of::<E>(),
514            _ => false,
515        }
516    }
517
518    /// Extract extension data with type checking
519    ///
520    /// Returns `Some(&E)` if this is an extension of type `E`, `None` otherwise.
521    pub fn as_extension<E: ExtensionEffect<R> + 'static>(&self) -> Option<&E> {
522        match self {
523            Effect::Extension(ext) => ext.as_any().downcast_ref::<E>(),
524            _ => None,
525        }
526    }
527
528    /// Extract mutable extension data with type checking
529    pub fn as_extension_mut<E: ExtensionEffect<R> + 'static>(&mut self) -> Option<&mut E> {
530        match self {
531            Effect::Extension(ext) => ext.as_any_mut().downcast_mut::<E>(),
532            _ => None,
533        }
534    }
535
536    /// Get the TypeId of an extension effect
537    pub fn extension_type_id(&self) -> Option<TypeId> {
538        match self {
539            Effect::Extension(ext) => Some(ext.type_id()),
540            _ => None,
541        }
542    }
543}
544
545#[cfg(test)]
546mod tests {
547    use super::*;
548    use crate::identifiers::RoleName;
549    use cfg_if::cfg_if;
550
551    cfg_if! {
552        if #[cfg(not(target_arch = "wasm32"))] {
553            use proptest::prelude::*;
554        }
555    }
556
557    #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
558    enum TestRole {
559        Alice,
560        Bob,
561    }
562
563    #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
564    enum TestLabel {
565        L0,
566    }
567
568    impl crate::effects::LabelId for TestLabel {
569        fn as_str(&self) -> &'static str {
570            "L0"
571        }
572
573        fn from_str(label: &str) -> Option<Self> {
574            (label == "L0").then_some(Self::L0)
575        }
576    }
577
578    impl RoleId for TestRole {
579        type Label = TestLabel;
580
581        fn role_name(&self) -> RoleName {
582            match self {
583                Self::Alice => RoleName::from_static("Alice"),
584                Self::Bob => RoleName::from_static("Bob"),
585            }
586        }
587    }
588
589    #[test]
590    fn then_composes_ended_programs_without_panic() {
591        let left = Program::<TestRole, String>::new()
592            .send(TestRole::Bob, "hello".to_string())
593            .end();
594        let right = Program::<TestRole, String>::new()
595            .recv::<String>(TestRole::Alice)
596            .end();
597        let composed = left.then(right);
598        assert!(matches!(composed.effects().last(), Some(Effect::End)));
599        assert_eq!(
600            composed
601                .effects()
602                .iter()
603                .filter(|effect| matches!(effect, Effect::End))
604                .count(),
605            1
606        );
607    }
608
609    #[test]
610    fn try_builder_apis_reject_effects_after_end() {
611        let builder = ProgramBuilder::<TestRole, String> {
612            effects: vec![Effect::End],
613            ended: true,
614        };
615        let err = builder
616            .try_send(TestRole::Bob, "late-msg".to_string())
617            .expect_err("try_send must reject effects after end");
618        assert!(matches!(err, ProgramError::InvalidStructure(_)));
619    }
620
621    #[test]
622    fn try_end_is_fallible_and_builds_valid_program() {
623        let program = Program::<TestRole, String>::builder()
624            .try_send(TestRole::Bob, "hello".to_string())
625            .expect("try_send should succeed")
626            .try_end()
627            .expect("try_end should succeed");
628        assert!(matches!(program.effects().last(), Some(Effect::End)));
629    }
630
631    #[test]
632    fn try_then_rejects_invalid_composition_shapes() {
633        let left = Program::<TestRole, String>::builder()
634            .try_end()
635            .expect("left");
636        let invalid_right = Program::<TestRole, String> {
637            effects: vec![
638                Effect::End,
639                Effect::Send {
640                    to: TestRole::Bob,
641                    msg: "invalid".to_string(),
642                },
643            ],
644        };
645
646        let err = left
647            .try_then(invalid_right)
648            .expect_err("try_then must reject invalid end placement");
649        assert!(matches!(err, ProgramError::InvalidStructure(_)));
650    }
651
652    cfg_if! {
653        if #[cfg(not(target_arch = "wasm32"))] {
654            proptest! {
655                #[test]
656                fn try_then_keeps_single_terminal_end(include_left_send in any::<bool>(), include_right_recv in any::<bool>()) {
657                    let left_builder = Program::<TestRole, String>::builder();
658                    let left_builder = if include_left_send {
659                        left_builder.send(TestRole::Bob, "msg".to_string())
660                    } else {
661                        left_builder
662                    };
663                    let left = left_builder.end();
664
665                    let right_builder = Program::<TestRole, String>::builder();
666                    let right_builder = if include_right_recv {
667                        right_builder.recv::<String>(TestRole::Alice)
668                    } else {
669                        right_builder
670                    };
671                    let right = right_builder.end();
672
673                    let composed = left
674                        .try_then(right)
675                        .expect("composition should be structurally valid");
676                    let end_count = composed
677                        .effects()
678                        .iter()
679                        .filter(|effect| matches!(effect, Effect::End))
680                        .count();
681                    prop_assert_eq!(end_count, 1);
682                    prop_assert!(matches!(composed.effects().last(), Some(Effect::End)));
683                }
684            }
685        }
686    }
687}
telltale_runtime/effects/algebra.rs

telltale_runtime/effects/
algebra.rs
