wasm/execution/
value_stack.rs

1use alloc::vec::{Drain, Vec};
2
3use crate::core::indices::LocalIdx;
4use crate::core::reader::types::{FuncType, ValType};
5use crate::execution::assert_validated::UnwrapValidatedExt;
6use crate::execution::value::Value;
7use crate::{unreachable_validated, RuntimeError};
8
9use super::value::Ref;
10
11// TODO make these configurable
12const MAX_VALUE_STACK_SIZE: usize = 0xf0000; // 64 Kibi-Values
13const MAX_CALL_STACK_SIZE: usize = 0x1000; // 4 Kibi-Functions
14
15/// The stack at runtime containing
16/// 1. Values
17/// 2. Labels
18/// 3. Activations
19///
20/// See <https://webassembly.github.io/spec/core/exec/runtime.html#stack>
21#[derive(Default)]
22pub(crate) struct Stack {
23    /// WASM values on the stack, i.e. the actual data that instructions operate on
24    values: Vec<Value>,
25
26    /// Call frames
27    ///
28    /// Each time a function is called, a new frame is pushed, whenever a function returns, a frame is popped
29    frames: Vec<CallFrame>,
30}
31
32impl Stack {
33    pub fn new() -> Self {
34        Self::default()
35    }
36
37    pub fn new_with_values(values: Vec<Value>) -> Self {
38        Self {
39            values,
40            ..Self::default()
41        }
42    }
43
44    pub(super) fn into_values(self) -> Vec<Value> {
45        self.values
46    }
47
48    pub fn drop_value(&mut self) {
49        // If there is at least one call frame, we shall not pop values past the current
50        // call frame. However, there is one legitimate reason to pop when there is **no** current
51        // call frame: after the outermost function returns, to extract the final return values of
52        // this interpreter invocation.
53        debug_assert!(
54            if !self.frames.is_empty() {
55                self.values.len() > self.current_call_frame().value_stack_base_idx
56            } else {
57                true
58            },
59            "can not pop values past the current call frame"
60        );
61
62        self.values.pop().unwrap_validated();
63    }
64
65    /// Pop a reference of unknown type from the value stack
66    pub fn pop_unknown_ref(&mut self) -> Ref {
67        // If there is at least one call frame, we shall not pop values past the current
68        // call frame. However, there is one legitimate reason to pop when there is **no** current
69        // call frame: after the outermost function returns, to extract the final return values of
70        // this interpreter invocation.
71        debug_assert!(
72            if !self.frames.is_empty() {
73                self.values.len() > self.current_call_frame().value_stack_base_idx
74            } else {
75                true
76            },
77            "can not pop values past the current call frame"
78        );
79
80        let popped = self.values.pop().unwrap_validated();
81        match popped.to_ty() {
82            ValType::RefType(_) => match popped {
83                Value::Ref(rref) => rref,
84                _ => unreachable!(),
85            },
86            _ => unreachable_validated!(),
87        }
88    }
89
90    /// Pop a value of the given [ValType] from the value stack
91    pub fn pop_value(&mut self, ty: ValType) -> Value {
92        // If there is at least one call frame, we shall not pop values past the current
93        // call frame. However, there is one legitimate reason to pop when there is **no** current
94        // call frame: after the outermost function returns, to extract the final return values of
95        // this interpreter invocation.
96        debug_assert!(
97            if !self.frames.is_empty() {
98                self.values.len() > self.current_call_frame().value_stack_base_idx
99            } else {
100                true
101            },
102            "can not pop values past the current call frame"
103        );
104
105        let popped = self.values.pop().unwrap_validated();
106        if popped.to_ty() == ty {
107            popped
108        } else {
109            unreachable_validated!()
110        }
111    }
112
113    //unfortunately required for polymorphic select
114    pub fn pop_value_with_unknown_type(&mut self) -> Value {
115        self.values.pop().unwrap_validated()
116    }
117
118    /// Copy a value of the given [ValType] from the value stack without removing it
119    pub fn peek_value(&self, ty: ValType) -> Value {
120        let value = self.values.last().unwrap_validated();
121        if value.to_ty() == ty {
122            *value
123        } else {
124            unreachable_validated!()
125        }
126    }
127
128    /// Returns a cloned copy of the top value on the stack, or `None` if the stack is empty
129    pub fn peek_unknown_value(&self) -> Option<Value> {
130        self.values.last().copied()
131    }
132
133    /// Push a value to the value stack
134    pub fn push_value(&mut self, value: Value) -> Result<(), RuntimeError> {
135        // check for value stack exhaustion
136        if self.values.len() > MAX_VALUE_STACK_SIZE {
137            return Err(RuntimeError::StackExhaustion);
138        }
139
140        // push the value
141        self.values.push(value);
142
143        Ok(())
144    }
145
146    /// Copy a local variable to the top of the value stack
147    pub fn get_local(&mut self, idx: LocalIdx) -> Result<(), RuntimeError> {
148        let call_frame_base_idx = self.current_call_frame().call_frame_base_idx;
149        let local_value = self
150            .values
151            .get(call_frame_base_idx + idx)
152            .unwrap_validated();
153        self.push_value(*local_value)
154    }
155
156    /// Pop value from the top of the value stack, writing it to the given local
157    pub fn set_local(&mut self, idx: LocalIdx) {
158        debug_assert!(
159            self.values.len() > self.current_call_frame().value_stack_base_idx,
160            "can not pop values past the current call frame"
161        );
162
163        let call_frame_base_idx = self.current_call_frame().call_frame_base_idx;
164        let local_ty = self
165            .values
166            .get(call_frame_base_idx + idx)
167            .unwrap_validated()
168            .to_ty();
169        let stack_value = self.pop_value(local_ty);
170
171        trace!("Instruction: local.set [{stack_value:?}] -> []");
172
173        *self
174            .values
175            .get_mut(call_frame_base_idx + idx)
176            .unwrap_validated() = stack_value;
177    }
178
179    /// Copy value from top of the value stack to the given local
180    pub fn tee_local(&mut self, idx: LocalIdx) {
181        let call_frame_base_idx = self.current_call_frame().call_frame_base_idx;
182
183        let local_ty = self
184            .values
185            .get(call_frame_base_idx + idx)
186            .unwrap_validated()
187            .to_ty();
188        let stack_value = self.peek_value(local_ty);
189
190        trace!("Instruction: local.tee [{stack_value:?}] -> []");
191
192        *self
193            .values
194            .get_mut(call_frame_base_idx + idx)
195            .unwrap_validated() = stack_value;
196    }
197
198    /// Get a shared reference to the current [`CallFrame`]
199    pub fn current_call_frame(&self) -> &CallFrame {
200        self.frames.last().unwrap_validated()
201    }
202
203    /// Get a mutable reference to the current [`CallFrame`]
204    pub fn _current_call_frame_mut(&mut self) -> &mut CallFrame {
205        self.frames.last_mut().unwrap_validated()
206    }
207
208    /// Pop a [`CallFrame`] from the call stack, returning the caller function store address, return address, and the return stp
209    pub fn pop_call_frame(&mut self) -> (usize, usize, usize) {
210        let CallFrame {
211            return_func_addr,
212            return_addr,
213            call_frame_base_idx,
214            return_value_count,
215            return_stp,
216            ..
217        } = self.frames.pop().unwrap_validated();
218
219        let remove_count = self.values.len() - call_frame_base_idx - return_value_count;
220
221        self.remove_inbetween(remove_count, return_value_count);
222
223        debug_assert_eq!(
224            self.values.len(),
225            call_frame_base_idx + return_value_count,
226            "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"
227        );
228
229        (return_func_addr, return_addr, return_stp)
230    }
231
232    /// Push a call frame to the call stack
233    ///
234    /// Takes the current [`Self::values`]'s length as [`CallFrame::value_stack_base_idx`].
235    pub fn push_call_frame(
236        &mut self,
237        return_func_addr: usize,
238        func_ty: &FuncType,
239        remaining_locals: &[ValType],
240        return_addr: usize,
241        return_stp: usize,
242    ) -> Result<(), RuntimeError> {
243        // check for call stack exhaustion
244        if self.call_frame_count() > MAX_CALL_STACK_SIZE {
245            return Err(RuntimeError::StackExhaustion);
246        }
247
248        debug_assert!(
249            self.values.len() >= func_ty.params.valtypes.len(),
250            "when pushing a new call frame, at least as many values need to be on the stack as required by the new call frames's function"
251        );
252
253        // the topmost `param_count` values are transferred into/consumed by this new call frame
254        let param_count = func_ty.params.valtypes.len();
255        let call_frame_base_idx = self.values.len() - param_count;
256
257        // after the params, put the additional locals
258        for local in remaining_locals {
259            self.values.push(Value::default_from_ty(*local));
260        }
261
262        // now that the locals are all populated, the actual stack section of this call frame begins
263        let value_stack_base_idx = self.values.len();
264
265        self.frames.push(CallFrame {
266            return_func_addr,
267            return_addr,
268            value_stack_base_idx,
269            call_frame_base_idx,
270            return_value_count: func_ty.returns.valtypes.len(),
271            return_stp,
272        });
273
274        Ok(())
275    }
276
277    /// Returns how many call frames are on the stack, in total.
278    pub fn call_frame_count(&self) -> usize {
279        self.frames.len()
280    }
281
282    /// Pop `n` elements from the value stack's tail as an iterator, with the first element being
283    /// closest to the **bottom** of the value stack
284    ///
285    /// Note that this is providing the values in reverse order compared to popping `n` values
286    /// (which would yield the element closest to the **top** of the value stack first).
287    pub fn pop_tail_iter(&mut self, n: usize) -> Drain<'_, Value> {
288        let start = self.values.len() - n;
289        self.values.drain(start..)
290    }
291
292    /// Remove `remove_count` values from the stack, keeping the topmost `keep_count` values
293    ///
294    /// From the stack, remove `remove_count` elements, by sliding down the `keep_count` topmost
295    /// values `remove_count` positions.
296    ///
297    /// **Effects**
298    ///
299    /// - after the operation, [`Stack`] will contain `remove_count` fewer elements
300    /// - `keep_count` topmost elements will be identical before and after the operation
301    /// - all elements below the `remove_count + keep_count` topmost stack entry remain
302    pub fn remove_inbetween(&mut self, remove_count: usize, keep_count: usize) {
303        let len = self.values.len();
304        self.values
305            .copy_within(len - keep_count.., len - keep_count - remove_count);
306        self.values.truncate(len - remove_count);
307    }
308}
309
310/// 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.
311pub(crate) struct CallFrame {
312    /// Store address of the function that called this [`CallFrame`]'s function
313    pub return_func_addr: usize,
314
315    /// Value that the PC has to be set to when this function returns
316    pub return_addr: usize,
317
318    /// The index to the lowermost value in [`Stack::values`] belonging to this [`CallFrame`]'s
319    /// stack
320    ///
321    /// Values below this may still belong to this [`CallFrame`], but they are locals. Consequently,
322    /// this is the lowest index down to which the stack may be popped in this [`CallFrame`].
323    /// However, clearing up this [`CallFrame`] may require further popping, down to (and
324    /// including!) the index stored in [`Self::call_frame_base_idx`].
325    pub value_stack_base_idx: usize,
326
327    /// The index to the lowermost value on [`Stack::values`] that belongs to this [`CallFrame`]
328    ///
329    /// Clearing this [`CallFrame`] requires popping all elements on [`Stack::values`] down to (and
330    /// including!) this index.
331    pub call_frame_base_idx: usize,
332
333    /// Number of return values to retain on [`Stack::values`] when unwinding/popping a [`CallFrame`]
334    pub return_value_count: usize,
335
336    // Value that the stp has to be set to when this function returns
337    pub return_stp: usize,
338}
wasm/execution/value_stack.rs

wasm/execution/
value_stack.rs
