rsaeb 0.5.0

A no_std + alloc interpreter for A=B ordered rewrite programs.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

use super::action::StepApplication;
use super::budget::StepBudget;
use super::input::{InitialStateBytes, RuntimeInput};
use super::matcher::{RuleSearch, find_next_match};
use super::once::OnceRunStates;
use super::rewrite::RewriteScratch;
use super::state::State;
use super::terminal::ExecutionTerminal;
use crate::error::RunError;
use crate::program::{Program, RunLimits, StepCount};
use crate::rule::{PayloadView, RuleView};
use crate::trace::RuntimeStateView;

/// Result of asking an [`Execution`] to advance by one rule application.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ExecutionStep<'program, 'run> {
    /// One ordinary rewrite rule was applied and execution can be stepped again.
    Applied {
        /// One-based applied step count.
        step: StepCount,
        /// Structured view of the applied rule.
        rule: RuleView<'program>,
        /// Borrowed runtime state after the applied rewrite step.
        state: RuntimeStateView<'run>,
    },
    /// No rule matched the final runtime state.
    Stable {
        /// Number of rewrite steps applied before reaching the stable state.
        steps: StepCount,
        /// Borrowed final runtime state.
        state: RuntimeStateView<'run>,
    },
    /// A matched rule executed `(return)`.
    Return {
        /// One-based applied step count for the return rule.
        step: StepCount,
        /// Structured view of the return rule.
        rule: RuleView<'program>,
        /// Borrowed return payload from the parsed program.
        output: PayloadView<'program>,
    },
}

/// Stateful execution of one parsed program against one runtime input.
///
/// An execution owns the mutable runtime state, rewrite scratch buffer,
/// completed-step budget, and per-run `(once)` state for one invocation.
#[derive(Debug)]
pub struct Execution<'program> {
    program: &'program Program,
    pub(super) state: State,
    pub(super) scratch: RewriteScratch,
    pub(super) step_budget: StepBudget,
    pub(super) once_states: OnceRunStates,
    pub(super) limits: RunLimits,
    pub(super) terminal: ExecutionTerminal<'program>,
}

impl<'program> Execution<'program> {
    pub(crate) fn new(
        program: &'program Program,
        input: RuntimeInput<'_>,
        limits: RunLimits,
    ) -> Result<Self, RunError> {
        let input = InitialStateBytes::materialize(input, limits)?;
        let state = State::from_input(input);
        let once_states = OnceRunStates::new(program.once_slot_count())?;
        let scratch = RewriteScratch::new();

        Ok(Self {
            program,
            state,
            scratch,
            step_budget: StepBudget::new(limits.step_limit()),
            once_states,
            limits,
            terminal: ExecutionTerminal::Running,
        })
    }

    /// Number of rewrite steps that have already completed in this execution.
    #[must_use]
    pub const fn completed_steps(&self) -> StepCount {
        self.step_budget.completed_steps()
    }

    /// Advances this execution by at most one matching rule.
    ///
    /// Returns [`ExecutionStep::Applied`] after one ordinary rewrite step.
    /// Returns [`ExecutionStep::Stable`] when no rule matches.
    /// Returns [`ExecutionStep::Return`] when the next matching rule executes
    /// `(return)`.
    ///
    /// # Errors
    ///
    /// Returns `RunError` when applying the next matching rule would exceed the
    /// configured limits, allocation fails, state-size arithmetic overflows, or
    /// an internal runtime invariant is violated. On error, no rewrite step is
    /// completed: the runtime state, `(once)`
    /// state, and completed-step count remain unchanged.
    pub fn step(&mut self) -> Result<ExecutionStep<'program, '_>, RunError> {
        match self.terminal {
            ExecutionTerminal::Running => {}
            ExecutionTerminal::Stable => {
                return Ok(ExecutionStep::Stable {
                    steps: self.step_budget.completed_steps(),
                    state: self.state.view(),
                });
            }
            ExecutionTerminal::Return { step, rule, output } => {
                return Ok(ExecutionStep::Return {
                    step,
                    rule: rule.view(),
                    output,
                });
            }
        }

        let matched = match self.find_next_match()? {
            RuleSearch::Matched(matched) => matched,
            RuleSearch::Stable => {
                self.terminal = ExecutionTerminal::Stable;
                return Ok(ExecutionStep::Stable {
                    steps: self.step_budget.completed_steps(),
                    state: self.state.view(),
                });
            }
        };

        let applied = self.apply_matched_rule(matched)?;
        match applied.effect {
            StepApplication::Continue => Ok(ExecutionStep::Applied {
                step: applied.step,
                rule: applied.rule.view(),
                state: self.state.view(),
            }),
            StepApplication::Return(output) => Ok(ExecutionStep::Return {
                step: applied.step,
                rule: applied.rule.view(),
                output,
            }),
        }
    }

    pub(super) fn find_next_match(&self) -> Result<RuleSearch<'program>, RunError> {
        find_next_match(self.program.rule_slice(), &self.state, &self.once_states)
    }
}