openmina_node_invariants/
no_recursion.rs

1use node::{ActionKind, ActionWithMeta, Store};
2use strum::VariantArray;
3
4use crate::{Invariant, InvariantResult};
5
6/// Makes sure we don't have cycles in action chain.
7///
8/// Cycles in action chain can cause whole lot of issues:
9/// 1. Stack overflow (as long as actions live on stack).
10/// 2. Infinite loop.
11/// 3. Harder to reason about and debug state machine.
12#[derive(documented::Documented, Default, Clone, Copy)]
13pub struct NoRecursion;
14
15impl Invariant for NoRecursion {
16    type InternalState = Vec<ActionKind>;
17    fn triggers(&self) -> &[ActionKind] {
18        ActionKind::VARIANTS
19    }
20
21    fn check<S: redux::Service>(
22        self,
23        action_stack: &mut Self::InternalState,
24        _: &Store<S>,
25        action: &ActionWithMeta,
26    ) -> InvariantResult {
27        let action_kind = action.action().kind();
28        let action_depth = action.depth() as usize;
29
30        if action_stack.len() < action_depth {
31            assert_eq!(action_stack.len() + 1, action_depth);
32        } else {
33            action_stack.truncate(action_depth.saturating_sub(1));
34        }
35
36        // let is_recursing = action_stack.iter().any(|kind| *kind == action_kind);
37        let is_recursing = contains_cycle(action_stack);
38        action_stack.push(action_kind);
39
40        if is_recursing {
41            InvariantResult::Violation(format!("recursion detected: {action_stack:?}"))
42        } else {
43            InvariantResult::Updated
44        }
45    }
46}
47
48fn contains_cycle(stack: &[ActionKind]) -> bool {
49    let len = stack.len();
50    if len < 2 {
51        return false; // No cycle possible if the stack is too short
52    }
53
54    for cycle_length in 1..=(len / 2) {
55        let slice1 = &stack[len - cycle_length..];
56        let slice2 = &stack[len - 2 * cycle_length..len - cycle_length];
57        if slice1 == slice2 {
58            return true;
59        }
60    }
61    false
62}
openmina_node_invariants/no_recursion.rs

openmina_node_invariants/
no_recursion.rs
