wasm/execution/
value_stack.rs

1use alloc::vec::{Drain, Vec};
2
3use crate::core::indices::{FuncIdx, LocalIdx};
4use crate::core::reader::types::{FuncType, ValType};
5use crate::execution::assert_validated::UnwrapValidatedExt;
6use crate::execution::value::Value;
7use crate::locals::Locals;
8use crate::{unreachable_validated, RuntimeError};
9
10use super::value::Ref;
11
12// TODO make these configurable
13const MAX_VALUE_STACK_SIZE: usize = 0xf1000; // 4096
14const MAX_CALL_STACK_SIZE: usize = 0xff; // 256
15
16/// The stack at runtime containing
17/// 1. Values
18/// 2. Labels
19/// 3. Activations
20///
21/// See <https://webassembly.github.io/spec/core/exec/runtime.html#stack>
22#[derive(Default)]
23pub(crate) struct Stack {
24    /// WASM values on the stack, i.e. the actual data that instructions operate on
25    values: Vec<Value>,
26
27    /// Stack frames
28    ///
29    /// Each time a function is called, a new frame is pushed, whenever a function returns, a frame is popped
30    frames: Vec<CallFrame>,
31}
32
33impl Stack {
34    pub fn new() -> Self {
35        Self::default()
36    }
37
38    pub fn drop_value(&mut self) {
39        // If there is at least one stack frame, we shall not pop values past the current
40        // stackframe. However, there is one legitimate reason to pop when there is **no** current
41        // stackframe: after the outermost function returns, to extract the final return values of
42        // this interpreter invocation.
43        debug_assert!(
44            if !self.frames.is_empty() {
45                self.values.len() > self.current_stackframe().value_stack_base_idx
46            } else {
47                true
48            },
49            "can not pop values past the current stackframe"
50        );
51
52        self.values.pop().unwrap_validated();
53    }
54
55    /// Pop a reference of unknown type from the value stack
56    pub fn pop_unknown_ref(&mut self) -> Ref {
57        // If there is at least one stack frame, we shall not pop values past the current
58        // stackframe. However, there is one legitimate reason to pop when there is **no** current
59        // stackframe: after the outermost function returns, to extract the final return values of
60        // this interpreter invocation.
61        debug_assert!(
62            if !self.frames.is_empty() {
63                self.values.len() > self.current_stackframe().value_stack_base_idx
64            } else {
65                true
66            },
67            "can not pop values past the current stackframe"
68        );
69
70        let popped = self.values.pop().unwrap_validated();
71        match popped.to_ty() {
72            ValType::RefType(_) => match popped {
73                Value::Ref(rref) => rref,
74                _ => unreachable!(),
75            },
76            _ => unreachable_validated!(),
77        }
78    }
79
80    /// Pop a value of the given [ValType] from the value stack
81    pub fn pop_value(&mut self, ty: ValType) -> Value {
82        // If there is at least one stack frame, we shall not pop values past the current
83        // stackframe. However, there is one legitimate reason to pop when there is **no** current
84        // stackframe: after the outermost function returns, to extract the final return values of
85        // this interpreter invocation.
86        debug_assert!(
87            if !self.frames.is_empty() {
88                self.values.len() > self.current_stackframe().value_stack_base_idx
89            } else {
90                true
91            },
92            "can not pop values past the current stackframe"
93        );
94
95        let popped = self.values.pop().unwrap_validated();
96        if popped.to_ty() == ty {
97            popped
98        } else {
99            unreachable_validated!()
100        }
101    }
102
103    //unfortunately required for polymorphic select
104    pub fn pop_value_with_unknown_type(&mut self) -> Value {
105        self.values.pop().unwrap_validated()
106    }
107
108    /// Copy a value of the given [ValType] from the value stack without removing it
109    pub fn peek_value(&self, ty: ValType) -> Value {
110        let value = self.values.last().unwrap_validated();
111        if value.to_ty() == ty {
112            *value
113        } else {
114            unreachable_validated!()
115        }
116    }
117
118    /// Returns a cloned copy of the top value on the stack, or `None` if the stack is empty
119    pub fn peek_unknown_value(&self) -> Option<Value> {
120        self.values.last().copied()
121    }
122
123    /// Push a value to the value stack
124    pub fn push_value(&mut self, value: Value) -> Result<(), RuntimeError> {
125        // check for value stack exhaustion
126        if self.values.len() > MAX_VALUE_STACK_SIZE {
127            return Err(RuntimeError::StackExhaustion);
128        }
129
130        // push the value
131        self.values.push(value);
132
133        Ok(())
134    }
135
136    /// Copy a local variable to the top of the value stack
137    pub fn get_local(&mut self, idx: LocalIdx) -> Result<(), RuntimeError> {
138        let local_value = self.frames.last().unwrap_validated().locals.get(idx);
139        self.push_value(*local_value)
140    }
141
142    /// Pop value from the top of the value stack, writing it to the given local
143    pub fn set_local(&mut self, idx: LocalIdx) {
144        debug_assert!(
145            self.values.len() > self.current_stackframe().value_stack_base_idx,
146            "can not pop values past the current stackframe"
147        );
148
149        let local_ty = self.current_stackframe().locals.get_ty(idx);
150        let stack_value = self.pop_value(local_ty);
151
152        trace!("Instruction: local.set [{stack_value:?}] -> []");
153        *self.current_stackframe_mut().locals.get_mut(idx) = stack_value;
154    }
155
156    /// Copy value from top of the value stack to the given local
157    pub fn tee_local(&mut self, idx: LocalIdx) {
158        let local_ty = self.current_stackframe().locals.get_ty(idx);
159        let stack_value = self.peek_value(local_ty);
160
161        trace!("Instruction: local.tee [{stack_value:?}] -> []");
162        *self.current_stackframe_mut().locals.get_mut(idx) = stack_value;
163    }
164
165    /// Get a shared reference to the current [`CallFrame`]
166    pub fn current_stackframe(&self) -> &CallFrame {
167        self.frames.last().unwrap_validated()
168    }
169
170    /// Get a mutable reference to the current [`CallFrame`]
171    pub fn current_stackframe_mut(&mut self) -> &mut CallFrame {
172        self.frames.last_mut().unwrap_validated()
173    }
174
175    /// Pop a [`CallFrame`] from the call stack, returning the module id, return address, and the return stp
176    pub fn pop_stackframe(&mut self) -> (usize, usize, usize) {
177        let CallFrame {
178            module_idx,
179            return_addr,
180            value_stack_base_idx,
181            return_value_count,
182            return_stp,
183            ..
184        } = self.frames.pop().unwrap_validated();
185
186        let truncation_top = self.values.len() - return_value_count;
187        let _ = self.values.drain(value_stack_base_idx..truncation_top);
188
189        debug_assert_eq!(
190            self.values.len(),
191            value_stack_base_idx + return_value_count,
192            "after a function call finished, the stack must have exactly as many values as it had before calling the function plus the number of function return values"
193        );
194
195        (module_idx, return_addr, return_stp)
196    }
197
198    /// Push a stackframe to the call stack
199    ///
200    /// Takes the current [`Self::values`]'s length as [`CallFrame::value_stack_base_idx`].
201    pub fn push_stackframe(
202        &mut self,
203        return_module_idx: usize,
204        func_idx: FuncIdx,
205        func_ty: &FuncType,
206        locals: Locals,
207        return_addr: usize,
208        return_stp: usize,
209    ) -> Result<(), RuntimeError> {
210        // check for call stack exhaustion
211        if self.frames.len() > MAX_CALL_STACK_SIZE {
212            return Err(RuntimeError::StackExhaustion);
213        }
214
215        self.frames.push(CallFrame {
216            module_idx: return_module_idx,
217            func_idx,
218            locals,
219            return_addr,
220            value_stack_base_idx: self.values.len(),
221            return_value_count: func_ty.returns.valtypes.len(),
222            return_stp,
223        });
224
225        Ok(())
226    }
227
228    /// Returns how many stackframes are on the stack, in total.
229    pub fn callframe_count(&self) -> usize {
230        self.frames.len()
231    }
232
233    /// Pop `n` elements from the value stack's tail as an iterator, with the first element being
234    /// closest to the **bottom** of the value stack
235    ///
236    /// Note that this is providing the values in reverse order compared to popping `n` values
237    /// (which would yield the element closest to the **top** of the value stack first).
238    pub fn pop_tail_iter(&mut self, n: usize) -> Drain<Value> {
239        let start = self.values.len() - n;
240        self.values.drain(start..)
241    }
242
243    // TODO change this interface
244    pub fn pop_n_values(&mut self, n: usize) {
245        self.values.truncate(self.values.len() - n);
246    }
247}
248
249/// The [WASM spec](https://webassembly.github.io/spec/core/exec/runtime.html#stack) calls this `Activations`, however it refers to the call frames of functions.
250pub(crate) struct CallFrame {
251    /// Index to the module idx the function originates in.
252    /// This seems to be used as a return module id LOL
253    pub module_idx: usize,
254
255    /// Index to the function of this [`CallFrame`]
256    pub func_idx: FuncIdx,
257
258    /// Local variables such as parameters for this [`CallFrame`]'s function
259    pub locals: Locals,
260
261    /// Value that the PC has to be set to when this function returns
262    pub return_addr: usize,
263
264    /// The index to the first value on [`Stack::values`] that belongs to this [`CallFrame`]
265    pub value_stack_base_idx: usize,
266
267    /// Number of return values to retain on [`Stack::values`] when unwinding/popping a [`CallFrame`]
268    pub return_value_count: usize,
269
270    // Value that the stp has to be set to when this function returns
271    pub return_stp: usize,
272}
wasm/execution/value_stack.rs

wasm/execution/
value_stack.rs
