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::locals::Locals;
8use crate::{unreachable_validated, RuntimeError};
9
10use super::value::Ref;
11
12// TODO make these configurable
13const MAX_VALUE_STACK_SIZE: usize = 0xf0000; // 64 Kibi-Values
14const MAX_CALL_STACK_SIZE: usize = 0x1000; // 4 Kibi-Functions
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(super) fn into_values(self) -> Vec<Value> {
39        self.values
40    }
41
42    pub fn drop_value(&mut self) {
43        // If there is at least one stack frame, we shall not pop values past the current
44        // stackframe. However, there is one legitimate reason to pop when there is **no** current
45        // stackframe: after the outermost function returns, to extract the final return values of
46        // this interpreter invocation.
47        debug_assert!(
48            if !self.frames.is_empty() {
49                self.values.len() > self.current_stackframe().value_stack_base_idx
50            } else {
51                true
52            },
53            "can not pop values past the current stackframe"
54        );
55
56        self.values.pop().unwrap_validated();
57    }
58
59    /// Pop a reference of unknown type from the value stack
60    pub fn pop_unknown_ref(&mut self) -> Ref {
61        // If there is at least one stack frame, we shall not pop values past the current
62        // stackframe. However, there is one legitimate reason to pop when there is **no** current
63        // stackframe: after the outermost function returns, to extract the final return values of
64        // this interpreter invocation.
65        debug_assert!(
66            if !self.frames.is_empty() {
67                self.values.len() > self.current_stackframe().value_stack_base_idx
68            } else {
69                true
70            },
71            "can not pop values past the current stackframe"
72        );
73
74        let popped = self.values.pop().unwrap_validated();
75        match popped.to_ty() {
76            ValType::RefType(_) => match popped {
77                Value::Ref(rref) => rref,
78                _ => unreachable!(),
79            },
80            _ => unreachable_validated!(),
81        }
82    }
83
84    /// Pop a value of the given [ValType] from the value stack
85    pub fn pop_value(&mut self, ty: ValType) -> Value {
86        // If there is at least one stack frame, we shall not pop values past the current
87        // stackframe. However, there is one legitimate reason to pop when there is **no** current
88        // stackframe: after the outermost function returns, to extract the final return values of
89        // this interpreter invocation.
90        debug_assert!(
91            if !self.frames.is_empty() {
92                self.values.len() > self.current_stackframe().value_stack_base_idx
93            } else {
94                true
95            },
96            "can not pop values past the current stackframe"
97        );
98
99        let popped = self.values.pop().unwrap_validated();
100        if popped.to_ty() == ty {
101            popped
102        } else {
103            unreachable_validated!()
104        }
105    }
106
107    //unfortunately required for polymorphic select
108    pub fn pop_value_with_unknown_type(&mut self) -> Value {
109        self.values.pop().unwrap_validated()
110    }
111
112    /// Copy a value of the given [ValType] from the value stack without removing it
113    pub fn peek_value(&self, ty: ValType) -> Value {
114        let value = self.values.last().unwrap_validated();
115        if value.to_ty() == ty {
116            *value
117        } else {
118            unreachable_validated!()
119        }
120    }
121
122    /// Returns a cloned copy of the top value on the stack, or `None` if the stack is empty
123    pub fn peek_unknown_value(&self) -> Option<Value> {
124        self.values.last().copied()
125    }
126
127    /// Push a value to the value stack
128    pub fn push_value(&mut self, value: Value) -> Result<(), RuntimeError> {
129        // check for value stack exhaustion
130        if self.values.len() > MAX_VALUE_STACK_SIZE {
131            return Err(RuntimeError::StackExhaustion);
132        }
133
134        // push the value
135        self.values.push(value);
136
137        Ok(())
138    }
139
140    /// Copy a local variable to the top of the value stack
141    pub fn get_local(&mut self, idx: LocalIdx) -> Result<(), RuntimeError> {
142        let local_value = self.frames.last().unwrap_validated().locals.get(idx);
143        self.push_value(*local_value)
144    }
145
146    /// Pop value from the top of the value stack, writing it to the given local
147    pub fn set_local(&mut self, idx: LocalIdx) {
148        debug_assert!(
149            self.values.len() > self.current_stackframe().value_stack_base_idx,
150            "can not pop values past the current stackframe"
151        );
152
153        let local_ty = self.current_stackframe().locals.get_ty(idx);
154        let stack_value = self.pop_value(local_ty);
155
156        trace!("Instruction: local.set [{stack_value:?}] -> []");
157        *self.current_stackframe_mut().locals.get_mut(idx) = stack_value;
158    }
159
160    /// Copy value from top of the value stack to the given local
161    pub fn tee_local(&mut self, idx: LocalIdx) {
162        let local_ty = self.current_stackframe().locals.get_ty(idx);
163        let stack_value = self.peek_value(local_ty);
164
165        trace!("Instruction: local.tee [{stack_value:?}] -> []");
166        *self.current_stackframe_mut().locals.get_mut(idx) = stack_value;
167    }
168
169    /// Get a shared reference to the current [`CallFrame`]
170    pub fn current_stackframe(&self) -> &CallFrame {
171        self.frames.last().unwrap_validated()
172    }
173
174    /// Get a mutable reference to the current [`CallFrame`]
175    pub fn current_stackframe_mut(&mut self) -> &mut CallFrame {
176        self.frames.last_mut().unwrap_validated()
177    }
178
179    /// Pop a [`CallFrame`] from the call stack, returning the caller function store address, return address, and the return stp
180    pub fn pop_stackframe(&mut self) -> (usize, usize, usize) {
181        let CallFrame {
182            return_func_addr,
183            return_addr,
184            value_stack_base_idx,
185            return_value_count,
186            return_stp,
187            ..
188        } = self.frames.pop().unwrap_validated();
189
190        let truncation_top = self.values.len() - return_value_count;
191        let _ = self.values.drain(value_stack_base_idx..truncation_top);
192
193        debug_assert_eq!(
194            self.values.len(),
195            value_stack_base_idx + return_value_count,
196            "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"
197        );
198
199        (return_func_addr, return_addr, return_stp)
200    }
201
202    /// Push a stackframe to the call stack
203    ///
204    /// Takes the current [`Self::values`]'s length as [`CallFrame::value_stack_base_idx`].
205    pub fn push_stackframe(
206        &mut self,
207        return_func_addr: usize,
208        func_ty: &FuncType,
209        locals: Locals,
210        return_addr: usize,
211        return_stp: usize,
212    ) -> Result<(), RuntimeError> {
213        // check for call stack exhaustion
214        if self.frames.len() > MAX_CALL_STACK_SIZE {
215            return Err(RuntimeError::StackExhaustion);
216        }
217
218        self.frames.push(CallFrame {
219            return_func_addr,
220            locals,
221            return_addr,
222            value_stack_base_idx: self.values.len(),
223            return_value_count: func_ty.returns.valtypes.len(),
224            return_stp,
225        });
226
227        Ok(())
228    }
229
230    /// Returns how many stackframes are on the stack, in total.
231    pub fn callframe_count(&self) -> usize {
232        self.frames.len()
233    }
234
235    /// Pop `n` elements from the value stack's tail as an iterator, with the first element being
236    /// closest to the **bottom** of the value stack
237    ///
238    /// Note that this is providing the values in reverse order compared to popping `n` values
239    /// (which would yield the element closest to the **top** of the value stack first).
240    pub fn pop_tail_iter(&mut self, n: usize) -> Drain<'_, Value> {
241        let start = self.values.len() - n;
242        self.values.drain(start..)
243    }
244
245    /// Remove `remove_count` values from the stack, keeping the topmost `keep_count` values
246    ///
247    /// From the stack, remove `remove_count` elements, by sliding down the `keep_count` topmost
248    /// values `remove_count` positions.
249    ///
250    /// **Effects**
251    ///
252    /// - after the operation, [`Stack`] will contain `remove_count` fewer elements
253    /// - `keep_count` topmost elements will be identical before and after the operation
254    /// - all elements below the `remove_count + keep_count` topmost stack entry remain
255    pub fn remove_inbetween(&mut self, remove_count: usize, keep_count: usize) {
256        let len = self.values.len();
257        self.values
258            .copy_within(len - keep_count.., len - keep_count - remove_count);
259        self.values.truncate(len - remove_count);
260    }
261}
262
263/// 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.
264pub(crate) struct CallFrame {
265    /// Store address of the function that called this [`CallFrame`]'s function
266    pub return_func_addr: usize,
267
268    /// Local variables such as parameters for this [`CallFrame`]'s function
269    pub locals: Locals,
270
271    /// Value that the PC has to be set to when this function returns
272    pub return_addr: usize,
273
274    /// The index to the first value on [`Stack::values`] that belongs to this [`CallFrame`]
275    pub value_stack_base_idx: usize,
276
277    /// Number of return values to retain on [`Stack::values`] when unwinding/popping a [`CallFrame`]
278    pub return_value_count: usize,
279
280    // Value that the stp has to be set to when this function returns
281    pub return_stp: usize,
282}
wasm/execution/value_stack.rs

wasm/execution/
value_stack.rs
