stack_assembly/
eval.rs

1use crate::{
2    Effect, Memory, OperandStack,
3    script::{Operator, OperatorIndex, Script},
4};
5
6/// # The ongoing evaluation of a script
7///
8/// This, alongside [`Script`] is one of the main entry points into this
9/// library's API. To evaluate a script, first initialize an `Eval` instance
10/// using [`Eval::new`], then use [`Eval::run`] or [`Eval::step`] to advance the
11/// evaluation.
12///
13/// ## Example
14///
15/// ```
16/// use stack_assembly::{Eval, Script};
17///
18/// let script = Script::compile("1 2 +");
19///
20/// let mut eval = Eval::new();
21/// eval.run(&script);
22///
23/// assert_eq!(eval.operand_stack.to_i32_slice(), &[3]);
24/// ```
25#[derive(Debug, Default)]
26pub struct Eval {
27    next_operator: OperatorIndex,
28    call_stack: Vec<OperatorIndex>,
29    effect: Option<(Effect, OperatorIndex)>,
30
31    /// # The operand stack
32    ///
33    /// StackAssembly's evaluation model is based on an implicit stack which
34    /// stores all operands. An operator's output is pushed to that stack, and
35    /// any of its inputs are popped from there.
36    ///
37    /// Alongside [`memory`], this field is the primary channel for
38    /// communication between script and host.
39    ///
40    /// Most hosts should restrict modifications to this field to when the
41    /// script triggers [`Effect::Yield`], and then only do so in a
42    /// well-reasoned and documented manner. Anything else might make reasoning
43    /// about the script's behavior very difficult.
44    ///
45    /// None the less, the host has full access to this field, as to not
46    /// restrict any experimental or non-standard use cases.
47    ///
48    /// [`memory`]: #structfield.memory
49    pub operand_stack: OperandStack,
50
51    /// # The memory
52    ///
53    /// StackAssembly provides a linear memory that is freely addressable per
54    /// word.
55    ///
56    /// Alongside [`operand_stack`], this field is the primary channel for
57    /// communication between script and host.
58    ///
59    /// Most hosts should restrict modifications to this field to when the
60    /// script triggers [`Effect::Yield`], and then only do so in a
61    /// well-reasoned and documented manner. Anything else might make reasoning
62    /// about the script's behavior very difficult.
63    ///
64    /// None the less, the host has full access to this field, as to not
65    /// restrict any experimental or non-standard use cases.
66    ///
67    /// [`operand_stack`]: #structfield.operand_stack
68    pub memory: Memory,
69}
70
71impl Eval {
72    /// # Construct a new instance of `Eval`
73    ///
74    /// To evaluate a script using the returned instance, you must call
75    /// [`Eval::run`] or [`Eval::step`].
76    pub fn new() -> Self {
77        Self::default()
78    }
79
80    /// # Access the current call stack
81    ///
82    /// The returned iterator yields operator indices on the call stack,
83    /// starting with the top-most one.
84    ///
85    /// The yielded operator indices identify the operators where evaluation
86    /// will continue after evaluating a `return` operator; _not_ the operators
87    /// that were the source of a call.
88    pub fn call_stack(&self) -> impl Iterator<Item = OperatorIndex> {
89        self.call_stack.iter().copied().rev().map(|index| {
90            let Some(value) = index.value.checked_sub(1) else {
91                unreachable!(
92                    "Operator indices on call stack identify the operator to \
93                    return to after the call, which is the operator _after_ \
94                    the calling operator. Hence, an operator before that one \
95                    exists, and subtracting from the index of the call stack \
96                    cannot overflow."
97                );
98            };
99
100            OperatorIndex { value }
101        })
102    }
103
104    /// # Advance the evaluation until it triggers an effect
105    ///
106    /// If an effect is currently active, do nothing and return immediately.
107    /// Otherwise, keep evaluating operators until one triggers an effect.
108    ///
109    /// The operator index returned alongside the effect identifies the operator
110    /// that triggered the effect.
111    ///
112    /// If you need more control over the evaluation, consider using
113    /// [`Eval::step`] instead.
114    pub fn run(&mut self, script: &Script) -> (Effect, OperatorIndex) {
115        loop {
116            if let Some(effect) = self.step(script) {
117                return effect;
118            }
119        }
120    }
121
122    /// # Advance the evaluation by one step
123    ///
124    /// If an effect is currently active, do nothing and return immediately.
125    /// Otherwise, evaluate the next operator. If that triggers an effect,
126    /// return that.
127    ///
128    /// The operator index returned alongside the effect identifies the operator
129    /// that triggered the effect.
130    ///
131    /// This function may be used for advancing the evaluation of the script in
132    /// a controlled manner. If you just want to keep evaluating until the next
133    /// effect triggers, consider using [`Eval::run`] instead.
134    pub fn step(&mut self, script: &Script) -> Option<(Effect, OperatorIndex)> {
135        let operator = self.next_operator;
136        self.next_operator.value += 1;
137
138        if self.effect.is_none()
139            && let Err(effect) = self.evaluate_operator(operator, script)
140        {
141            self.effect = Some((effect, operator));
142        }
143
144        self.effect
145    }
146
147    /// # Clear the active effect, if any
148    ///
149    /// If no effect is active, this call does nothing. If an effect has been
150    /// cleared, return that.
151    ///
152    /// The operator index returned alongside the effect identifies the operator
153    /// that triggered the effect.
154    pub fn clear_effect(&mut self) -> Option<(Effect, OperatorIndex)> {
155        self.effect.take()
156    }
157
158    fn evaluate_operator(
159        &mut self,
160        operator: OperatorIndex,
161        script: &Script,
162    ) -> Result<(), Effect> {
163        let operator = script.get_operator(operator)?;
164
165        match operator {
166            Operator::Identifier { value: identifier } => {
167                if identifier == "*" {
168                    let b = self.operand_stack.pop()?.to_i32();
169                    let a = self.operand_stack.pop()?.to_i32();
170
171                    self.operand_stack.push(a.wrapping_mul(b));
172                } else if identifier == "+" {
173                    let b = self.operand_stack.pop()?.to_i32();
174                    let a = self.operand_stack.pop()?.to_i32();
175
176                    self.operand_stack.push(a.wrapping_add(b));
177                } else if identifier == "-" {
178                    let b = self.operand_stack.pop()?.to_i32();
179                    let a = self.operand_stack.pop()?.to_i32();
180
181                    self.operand_stack.push(a.wrapping_sub(b));
182                } else if identifier == "/" {
183                    let b = self.operand_stack.pop()?.to_i32();
184                    let a = self.operand_stack.pop()?.to_i32();
185
186                    if b == 0 {
187                        return Err(Effect::DivisionByZero);
188                    }
189                    if a == i32::MIN && b == -1 {
190                        return Err(Effect::IntegerOverflow);
191                    }
192
193                    self.operand_stack.push(a / b);
194                    self.operand_stack.push(a % b);
195                } else if identifier == "<" {
196                    let b = self.operand_stack.pop()?.to_i32();
197                    let a = self.operand_stack.pop()?.to_i32();
198
199                    self.operand_stack.push(a < b);
200                } else if identifier == "<=" {
201                    let b = self.operand_stack.pop()?.to_i32();
202                    let a = self.operand_stack.pop()?.to_i32();
203
204                    self.operand_stack.push(a <= b);
205                } else if identifier == "=" {
206                    let b = self.operand_stack.pop()?.to_i32();
207                    let a = self.operand_stack.pop()?.to_i32();
208
209                    self.operand_stack.push(a == b);
210                } else if identifier == ">" {
211                    let b = self.operand_stack.pop()?.to_i32();
212                    let a = self.operand_stack.pop()?.to_i32();
213
214                    self.operand_stack.push(a > b);
215                } else if identifier == ">=" {
216                    let b = self.operand_stack.pop()?.to_i32();
217                    let a = self.operand_stack.pop()?.to_i32();
218
219                    self.operand_stack.push(a >= b);
220                } else if identifier == "and" {
221                    let b = self.operand_stack.pop()?.to_i32();
222                    let a = self.operand_stack.pop()?.to_i32();
223
224                    self.operand_stack.push(a & b);
225                } else if identifier == "or" {
226                    let b = self.operand_stack.pop()?.to_i32();
227                    let a = self.operand_stack.pop()?.to_i32();
228
229                    self.operand_stack.push(a | b);
230                } else if identifier == "xor" {
231                    let b = self.operand_stack.pop()?.to_i32();
232                    let a = self.operand_stack.pop()?.to_i32();
233
234                    self.operand_stack.push(a ^ b);
235                } else if identifier == "count_ones" {
236                    let a = self.operand_stack.pop()?.to_i32();
237
238                    self.operand_stack.push(a.count_ones());
239                } else if identifier == "leading_zeros" {
240                    let a = self.operand_stack.pop()?.to_i32();
241
242                    self.operand_stack.push(a.leading_zeros());
243                } else if identifier == "trailing_zeros" {
244                    let a = self.operand_stack.pop()?.to_i32();
245
246                    self.operand_stack.push(a.trailing_zeros());
247                } else if identifier == "rotate_left" {
248                    let num_positions = self.operand_stack.pop()?.to_u32();
249                    let a = self.operand_stack.pop()?.to_i32();
250
251                    self.operand_stack.push(a.rotate_left(num_positions));
252                } else if identifier == "rotate_right" {
253                    let num_positions = self.operand_stack.pop()?.to_u32();
254                    let a = self.operand_stack.pop()?.to_i32();
255
256                    self.operand_stack.push(a.rotate_right(num_positions));
257                } else if identifier == "shift_left" {
258                    let num_positions = self.operand_stack.pop()?.to_i32();
259                    let a = self.operand_stack.pop()?.to_i32();
260
261                    self.operand_stack.push(a << num_positions);
262                } else if identifier == "shift_right" {
263                    let num_positions = self.operand_stack.pop()?.to_i32();
264                    let a = self.operand_stack.pop()?.to_i32();
265
266                    self.operand_stack.push(a >> num_positions);
267                } else if identifier == "copy" {
268                    let index_from_top = self.operand_stack.pop()?.to_u32();
269                    let index_from_bottom = convert_operand_stack_index(
270                        &self.operand_stack,
271                        index_from_top,
272                    )?;
273
274                    let Some(value) = self
275                        .operand_stack
276                        .values
277                        .get(index_from_bottom)
278                        .copied()
279                    else {
280                        unreachable!(
281                            "We computed the index from the top, based on the \
282                            number of values on the stack. Since that did not \
283                            result in an integer overflow, it's not possible \
284                            that we ended up with an out-of-range index."
285                        );
286                    };
287
288                    self.operand_stack.push(value);
289                } else if identifier == "drop" {
290                    let index_from_top = self.operand_stack.pop()?.to_u32();
291                    let index_from_bottom = convert_operand_stack_index(
292                        &self.operand_stack,
293                        index_from_top,
294                    )?;
295
296                    // This could theoretically panic, but actually won't, for
297                    // the same reason that the index must be valid in the
298                    // implementation of `copy`.
299                    self.operand_stack.values.remove(index_from_bottom);
300                } else if identifier == "jump" {
301                    let index = self.operand_stack.pop()?.to_u32();
302
303                    self.next_operator.value = index;
304                } else if identifier == "jump_if" {
305                    let index = self.operand_stack.pop()?.to_u32();
306                    let condition = self.operand_stack.pop()?.to_bool();
307
308                    if condition {
309                        self.next_operator.value = index;
310                    }
311                } else if identifier == "call" {
312                    self.call_stack.push(self.next_operator);
313
314                    let index = self.operand_stack.pop()?.to_u32();
315
316                    self.next_operator.value = index;
317                } else if identifier == "call_either" {
318                    self.call_stack.push(self.next_operator);
319
320                    let else_ = self.operand_stack.pop()?.to_u32();
321                    let then = self.operand_stack.pop()?.to_u32();
322                    let condition = self.operand_stack.pop()?.to_bool();
323
324                    self.next_operator = {
325                        let value = if condition { then } else { else_ };
326                        OperatorIndex { value }
327                    };
328                } else if identifier == "return" {
329                    let Some(index) = self.call_stack.pop() else {
330                        return Err(Effect::Return);
331                    };
332
333                    self.next_operator = index;
334                } else if identifier == "assert" {
335                    let condition = self.operand_stack.pop()?.to_bool();
336
337                    if !condition {
338                        return Err(Effect::AssertionFailed);
339                    }
340                } else if identifier == "yield" {
341                    return Err(Effect::Yield);
342                } else if identifier == "read" {
343                    let address = self.operand_stack.pop()?.to_u32();
344
345                    let value = self.memory.read(address)?;
346
347                    self.operand_stack.push(value);
348                } else if identifier == "write" {
349                    let value = self.operand_stack.pop()?;
350                    let address = self.operand_stack.pop()?.to_u32();
351
352                    self.memory.write(address, value)?;
353                } else {
354                    return Err(Effect::UnknownIdentifier);
355                }
356            }
357            Operator::Integer { value } => {
358                self.operand_stack.push(*value);
359            }
360            Operator::Reference { name } => {
361                let operator = script.resolve_reference(name)?;
362                self.operand_stack.push(operator.value);
363            }
364        }
365
366        Ok(())
367    }
368}
369
370fn convert_operand_stack_index(
371    operand_stack: &OperandStack,
372    index_from_top: u32,
373) -> Result<usize, Effect> {
374    let Ok(index_from_top): Result<usize, _> = index_from_top.try_into() else {
375        // It is not possible to have a stack larger than what `usize` can
376        // address. So by definition, any index that's too large to convert to
377        // `usize`, can not be valid.
378        return Err(Effect::InvalidOperandStackIndex);
379    };
380
381    let index_from_bottom = operand_stack
382        .values
383        .len()
384        .checked_sub(1)
385        .and_then(|index| index.checked_sub(index_from_top));
386
387    index_from_bottom.ok_or(Effect::InvalidOperandStackIndex)
388}
stack_assembly/eval.rs

stack_assembly/
eval.rs
