rune/runtime/
stack.rs

Help
1use core::array;
2use core::convert::Infallible;
3use core::fmt;
4use core::mem::replace;
5use core::slice;
6
7use crate::alloc::alloc::Global;
8use crate::alloc::prelude::*;
9use crate::alloc::{self, Vec};
10use crate::runtime::{InstAddress, Output, Value, VmErrorKind};
11
12// This is a bit tricky. We know that `Value::empty()` is `Sync` but we can't
13// convince Rust that is the case.
14struct AssertSync<T>(T);
15unsafe impl<T> Sync for AssertSync<T> {}
16
17static EMPTY: AssertSync<Value> = AssertSync(Value::empty());
18
19/// An error raised when accessing an address on the stack.
20#[derive(Debug)]
21#[cfg_attr(test, derive(PartialEq))]
22#[non_exhaustive]
23pub struct StackError {
24    addr: InstAddress,
25}
26
27impl From<Infallible> for StackError {
28    #[inline]
29    fn from(value: Infallible) -> Self {
30        match value {}
31    }
32}
33
34impl fmt::Display for StackError {
35    #[inline]
36    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
37        write!(f, "Tried to access out-of-bounds stack entry {}", self.addr)
38    }
39}
40
41impl core::error::Error for StackError {}
42
43/// An error raised when accessing a slice on the stack.
44#[derive(Debug)]
45#[cfg_attr(test, derive(PartialEq))]
46#[non_exhaustive]
47pub struct SliceError {
48    addr: InstAddress,
49    len: usize,
50    stack: usize,
51}
52
53impl fmt::Display for SliceError {
54    #[inline]
55    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
56        write!(
57            f,
58            "Tried to access out-of-bounds stack slice {}-{} in 0-{}",
59            self.addr,
60            self.addr.offset() + self.len,
61            self.stack
62        )
63    }
64}
65
66impl core::error::Error for SliceError {}
67
68pub(crate) enum Pair<'a> {
69    Same(&'a mut Value),
70    Pair(&'a mut Value, &'a Value),
71}
72
73/// Memory access.
74pub trait Memory {
75    /// Get the slice at the given address with the given length.
76    ///
77    /// # Examples
78    ///
79    /// ```
80    /// use rune::vm_try;
81    /// use rune::runtime::{Output, Memory, ToValue, VmResult, InstAddress};
82    ///
83    /// fn sum(stack: &mut dyn Memory, addr: InstAddress, args: usize, out: Output) -> VmResult<()> {
84    ///     let mut number = 0;
85    ///
86    ///     for value in vm_try!(stack.slice_at(addr, args)) {
87    ///         number += vm_try!(value.as_integer::<i64>());
88    ///     }
89    ///
90    ///     out.store(stack, number);
91    ///     VmResult::Ok(())
92    /// }
93    /// ```
94    fn slice_at(&self, addr: InstAddress, len: usize) -> Result<&[Value], SliceError>;
95
96    /// Access the given slice mutably.
97    ///
98    /// # Examples
99    ///
100    /// ```
101    /// use rune::vm_try;
102    /// use rune::runtime::{Output, Memory, InstAddress, Value, VmResult};
103    ///
104    /// fn drop_values(stack: &mut dyn Memory, addr: InstAddress, args: usize, out: Output) -> VmResult<()> {
105    ///     for value in vm_try!(stack.slice_at_mut(addr, args)) {
106    ///         *value = Value::empty();
107    ///     }
108    ///
109    ///     out.store(stack, ());
110    ///     VmResult::Ok(())
111    /// }
112    /// ```
113    fn slice_at_mut(&mut self, addr: InstAddress, len: usize) -> Result<&mut [Value], SliceError>;
114
115    /// Get a value mutable at the given index from the stack bottom.
116    ///
117    /// # Examples
118    ///
119    /// ```
120    /// use rune::vm_try;
121    /// use rune::Module;
122    /// use rune::runtime::{Output, Memory, VmResult, InstAddress};
123    ///
124    /// fn add_one(stack: &mut dyn Memory, addr: InstAddress, args: usize, out: Output) -> VmResult<()> {
125    ///     let mut value = vm_try!(stack.at_mut(addr));
126    ///     let number = vm_try!(value.as_integer::<i64>());
127    ///     *value = vm_try!(rune::to_value(number + 1));
128    ///     out.store(stack, ());
129    ///     VmResult::Ok(())
130    /// }
131    /// ```
132    fn at_mut(&mut self, addr: InstAddress) -> Result<&mut Value, StackError>;
133
134    /// Get the slice at the given address with the given static length.
135    fn array_at<const N: usize>(&self, addr: InstAddress) -> Result<[&Value; N], SliceError>
136    where
137        Self: Sized,
138    {
139        let slice = self.slice_at(addr, N)?;
140        Ok(array::from_fn(|i| &slice[i]))
141    }
142}
143
144impl<M> Memory for &mut M
145where
146    M: Memory + ?Sized,
147{
148    #[inline]
149    fn slice_at(&self, addr: InstAddress, len: usize) -> Result<&[Value], SliceError> {
150        (**self).slice_at(addr, len)
151    }
152
153    #[inline]
154    fn slice_at_mut(&mut self, addr: InstAddress, len: usize) -> Result<&mut [Value], SliceError> {
155        (**self).slice_at_mut(addr, len)
156    }
157
158    #[inline]
159    fn at_mut(&mut self, addr: InstAddress) -> Result<&mut Value, StackError> {
160        (**self).at_mut(addr)
161    }
162}
163
164impl<const N: usize> Memory for [Value; N] {
165    fn slice_at(&self, addr: InstAddress, len: usize) -> Result<&[Value], SliceError> {
166        if len == 0 {
167            return Ok(&[]);
168        }
169
170        let start = addr.offset();
171
172        let Some(values) = start.checked_add(len).and_then(|end| self.get(start..end)) else {
173            return Err(SliceError {
174                addr,
175                len,
176                stack: N,
177            });
178        };
179
180        Ok(values)
181    }
182
183    fn slice_at_mut(&mut self, addr: InstAddress, len: usize) -> Result<&mut [Value], SliceError> {
184        if len == 0 {
185            return Ok(&mut []);
186        }
187
188        let start = addr.offset();
189
190        let Some(values) = start
191            .checked_add(len)
192            .and_then(|end| self.get_mut(start..end))
193        else {
194            return Err(SliceError {
195                addr,
196                len,
197                stack: N,
198            });
199        };
200
201        Ok(values)
202    }
203
204    #[inline]
205    fn at_mut(&mut self, addr: InstAddress) -> Result<&mut Value, StackError> {
206        let Some(value) = self.get_mut(addr.offset()) else {
207            return Err(StackError { addr });
208        };
209
210        Ok(value)
211    }
212}
213
214/// The stack of the virtual machine, where all values are stored.
215#[derive(Default, Debug)]
216pub struct Stack {
217    /// The current stack of values.
218    stack: Vec<Value>,
219    /// The top of the current stack frame.
220    ///
221    /// It is not possible to interact with values below this stack frame.
222    top: usize,
223}
224
225impl Stack {
226    /// Construct a new stack.
227    pub(crate) const fn new() -> Self {
228        Self {
229            stack: Vec::new(),
230            top: 0,
231        }
232    }
233
234    /// Access the value at the given frame offset.
235    ///
236    /// # Examples
237    ///
238    /// ```
239    /// use rune::vm_try;
240    /// use rune::Module;
241    /// use rune::runtime::{Output, Stack, VmResult, InstAddress};
242    ///
243    /// fn add_one(stack: &mut Stack, addr: InstAddress, args: usize, out: Output) -> VmResult<()> {
244    ///     let value = vm_try!(stack.at(addr).as_integer::<i64>());
245    ///     out.store(stack, value + 1);
246    ///     VmResult::Ok(())
247    /// }
248    /// ```
249    #[inline(always)]
250    pub fn at(&self, addr: InstAddress) -> &Value {
251        self.top
252            .checked_add(addr.offset())
253            .and_then(|n| self.stack.get(n))
254            .unwrap_or(&EMPTY.0)
255    }
256
257    /// Get a value mutable at the given index from the stack bottom.
258    ///
259    /// # Examples
260    ///
261    /// ```
262    /// use rune::vm_try;
263    /// use rune::Module;
264    /// use rune::runtime::{Output, Stack, VmResult, InstAddress};
265    ///
266    /// fn add_one(stack: &mut Stack, addr: InstAddress, args: usize, out: Output) -> VmResult<()> {
267    ///     let mut value = vm_try!(stack.at_mut(addr));
268    ///     let number = vm_try!(value.as_integer::<i64>());
269    ///     *value = vm_try!(rune::to_value(number + 1));
270    ///     out.store(stack, ());
271    ///     VmResult::Ok(())
272    /// }
273    /// ```
274    pub fn at_mut(&mut self, addr: InstAddress) -> Result<&mut Value, StackError> {
275        self.top
276            .checked_add(addr.offset())
277            .and_then(|n| self.stack.get_mut(n))
278            .ok_or(StackError { addr })
279    }
280
281    /// Get the slice at the given address with the given length.
282    ///
283    /// # Examples
284    ///
285    /// ```
286    /// use rune::vm_try;
287    /// use rune::Module;
288    /// use rune::runtime::{Output, Stack, ToValue, VmResult, InstAddress};
289    ///
290    /// fn sum(stack: &mut Stack, addr: InstAddress, args: usize, out: Output) -> VmResult<()> {
291    ///     let mut number = 0;
292    ///
293    ///     for value in vm_try!(stack.slice_at(addr, args)) {
294    ///         number += vm_try!(value.as_integer::<i64>());
295    ///     }
296    ///
297    ///     out.store(stack, number);
298    ///     VmResult::Ok(())
299    /// }
300    /// ```
301    pub fn slice_at(&self, addr: InstAddress, len: usize) -> Result<&[Value], SliceError> {
302        let stack_len = self.stack.len();
303
304        if let Some(slice) = inner_slice_at(&self.stack, self.top, addr, len) {
305            return Ok(slice);
306        }
307
308        Err(slice_error(stack_len, self.top, addr, len))
309    }
310
311    /// Get the mutable slice at the given address with the given length.
312    ///
313    /// # Examples
314    ///
315    /// ```
316    /// use rune::vm_try;
317    /// use rune::Module;
318    /// use rune::runtime::{Output, Stack, VmResult, InstAddress};
319    ///
320    /// fn sum(stack: &mut Stack, addr: InstAddress, args: usize, out: Output) -> VmResult<()> {
321    ///     for value in vm_try!(stack.slice_at_mut(addr, args)) {
322    ///         let number = vm_try!(value.as_integer::<i64>());
323    ///         *value = vm_try!(rune::to_value(number + 1));
324    ///     }
325    ///
326    ///     out.store(stack, ());
327    ///     VmResult::Ok(())
328    /// }
329    /// ```
330    pub fn slice_at_mut(
331        &mut self,
332        addr: InstAddress,
333        len: usize,
334    ) -> Result<&mut [Value], SliceError> {
335        let stack_len = self.stack.len();
336
337        if let Some(slice) = inner_slice_at_mut(&mut self.stack, self.top, addr, len) {
338            return Ok(slice);
339        }
340
341        Err(slice_error(stack_len, self.top, addr, len))
342    }
343
344    /// The current top address of the stack.
345    #[inline]
346    pub(crate) const fn addr(&self) -> InstAddress {
347        InstAddress::new(self.stack.len().saturating_sub(self.top))
348    }
349
350    /// Try to resize the stack with space for the given size.
351    pub(crate) fn resize(&mut self, size: usize) -> alloc::Result<()> {
352        if size == 0 {
353            return Ok(());
354        }
355
356        self.stack.try_resize_with(self.top + size, Value::empty)?;
357        Ok(())
358    }
359
360    /// Construct a new stack with the given capacity pre-allocated.
361    pub(crate) fn with_capacity(capacity: usize) -> alloc::Result<Self> {
362        Ok(Self {
363            stack: Vec::try_with_capacity(capacity)?,
364            top: 0,
365        })
366    }
367
368    /// Perform a raw access over the stack.
369    ///
370    /// This ignores [top] and will just check that the given slice
371    /// index is within range.
372    ///
373    /// [top]: Self::top()
374    #[cfg(feature = "cli")]
375    pub(crate) fn get<I>(&self, index: I) -> Option<&<I as slice::SliceIndex<[Value]>>::Output>
376    where
377        I: slice::SliceIndex<[Value]>,
378    {
379        self.stack.get(index)
380    }
381
382    /// Push a value onto the stack.
383    pub(crate) fn push<T>(&mut self, value: T) -> alloc::Result<()>
384    where
385        T: TryInto<Value, Error: Into<alloc::Error>>,
386    {
387        self.stack.try_push(value.try_into().map_err(Into::into)?)?;
388        Ok(())
389    }
390
391    /// Truncate the stack at the given address.
392    pub(crate) fn truncate(&mut self, addr: InstAddress) {
393        if let Some(len) = self.top.checked_add(addr.offset()) {
394            self.stack.truncate(len);
395        }
396    }
397
398    /// Drain the current stack down to the current stack bottom.
399    pub(crate) fn drain(&mut self) -> impl DoubleEndedIterator<Item = Value> + '_ {
400        self.stack.drain(self.top..)
401    }
402
403    /// Clear the current stack.
404    pub(crate) fn clear(&mut self) {
405        self.stack.clear();
406        self.top = 0;
407    }
408
409    /// Get the offset that corresponds to the bottom of the stack right now.
410    ///
411    /// The stack is partitioned into call frames, and once we enter a call
412    /// frame the bottom of the stack corresponds to the bottom of the current
413    /// call frame.
414    #[cfg_attr(not(feature = "tracing"), allow(unused))]
415    pub(crate) const fn top(&self) -> usize {
416        self.top
417    }
418
419    /// Get the length of the stack.
420    #[cfg_attr(not(feature = "tracing"), allow(unused))]
421    pub(crate) const fn len(&self) -> usize {
422        self.stack.len()
423    }
424
425    /// Swap the value at position a with the value at position b.
426    pub(crate) fn swap(&mut self, a: InstAddress, b: InstAddress) -> Result<(), StackError> {
427        if a == b {
428            return Ok(());
429        }
430
431        let a = self
432            .top
433            .checked_add(a.offset())
434            .filter(|&n| n < self.stack.len())
435            .ok_or(StackError { addr: a })?;
436
437        let b = self
438            .top
439            .checked_add(b.offset())
440            .filter(|&n| n < self.stack.len())
441            .ok_or(StackError { addr: b })?;
442
443        self.stack.swap(a, b);
444        Ok(())
445    }
446
447    /// Modify stack top by subtracting the given count from it while checking
448    /// that it is in bounds of the stack.
449    ///
450    /// This is used internally when returning from a call frame.
451    ///
452    /// Returns the old stack top.
453    #[tracing::instrument(skip_all)]
454    pub(crate) fn swap_top(&mut self, addr: InstAddress, len: usize) -> Result<usize, VmErrorKind> {
455        let old_len = self.stack.len();
456
457        if len == 0 {
458            return Ok(replace(&mut self.top, old_len));
459        }
460
461        let Some(start) = self.top.checked_add(addr.offset()) else {
462            return Err(VmErrorKind::StackError {
463                error: StackError { addr },
464            });
465        };
466
467        let Some(new_len) = old_len.checked_add(len) else {
468            return Err(VmErrorKind::StackError {
469                error: StackError { addr },
470            });
471        };
472
473        if old_len < start + len {
474            return Err(VmErrorKind::StackError {
475                error: StackError { addr },
476            });
477        }
478
479        self.stack.try_reserve(len)?;
480
481        // SAFETY: We've ensured that the collection has space for the new
482        // values. It is also guaranteed to be non-overlapping.
483        unsafe {
484            let ptr = self.stack.as_mut_ptr();
485            let from = slice::from_raw_parts_mut(ptr.add(start), len);
486
487            for (value, n) in from.iter_mut().zip(old_len..) {
488                ptr.add(n).write(replace(value, Value::empty()));
489            }
490
491            self.stack.set_len(new_len);
492        }
493
494        Ok(replace(&mut self.top, old_len))
495    }
496
497    /// Pop the current stack top and modify it to a different one.
498    #[tracing::instrument(skip_all)]
499    pub(crate) fn pop_stack_top(&mut self, top: usize) {
500        tracing::trace!(stack = self.stack.len(), self.top);
501        self.stack.truncate(self.top);
502        self.top = top;
503    }
504
505    /// Copy the value at the given address to the output.
506    pub(crate) fn copy(&mut self, from: InstAddress, out: Output) -> Result<(), StackError> {
507        let Some(to) = out.as_addr() else {
508            return Ok(());
509        };
510
511        if from == to {
512            return Ok(());
513        }
514
515        let from = self.top.wrapping_add(from.offset());
516        let to = self.top.wrapping_add(to.offset());
517
518        if from.max(to) >= self.stack.len() {
519            return Err(StackError {
520                addr: InstAddress::new(from.max(to).wrapping_sub(self.top)),
521            });
522        }
523
524        // SAFETY: We've checked that both addresses are in-bound and different
525        // just above.
526        unsafe {
527            let ptr = self.stack.as_mut_ptr();
528            (*ptr.add(to)).clone_from(&*ptr.add(from).cast_const());
529        }
530
531        Ok(())
532    }
533
534    /// Get a pair of addresses.
535    pub(crate) fn pair(&mut self, a: InstAddress, b: InstAddress) -> Result<Pair<'_>, StackError> {
536        if a == b {
537            return Ok(Pair::Same(self.at_mut(a)?));
538        }
539
540        let a = self
541            .top
542            .checked_add(a.offset())
543            .filter(|&n| n < self.stack.len())
544            .ok_or(StackError { addr: a })?;
545
546        let b = self
547            .top
548            .checked_add(b.offset())
549            .filter(|&n| n < self.stack.len())
550            .ok_or(StackError { addr: b })?;
551
552        let pair = unsafe {
553            let ptr = self.stack.as_mut_ptr();
554            Pair::Pair(&mut *ptr.add(a), &*ptr.add(b).cast_const())
555        };
556
557        Ok(pair)
558    }
559}
560
561impl Memory for Stack {
562    #[inline]
563    fn slice_at(&self, addr: InstAddress, len: usize) -> Result<&[Value], SliceError> {
564        Stack::slice_at(self, addr, len)
565    }
566
567    #[inline]
568    fn slice_at_mut(&mut self, addr: InstAddress, len: usize) -> Result<&mut [Value], SliceError> {
569        Stack::slice_at_mut(self, addr, len)
570    }
571
572    #[inline]
573    fn at_mut(&mut self, addr: InstAddress) -> Result<&mut Value, StackError> {
574        Stack::at_mut(self, addr)
575    }
576}
577
578#[inline(always)]
579fn inner_slice_at(values: &[Value], top: usize, addr: InstAddress, len: usize) -> Option<&[Value]> {
580    if len == 0 {
581        return Some(&[]);
582    }
583
584    let start = top.checked_add(addr.offset())?;
585    let end = start.checked_add(len)?;
586    values.get(start..end)
587}
588
589#[inline(always)]
590fn inner_slice_at_mut(
591    values: &mut [Value],
592    top: usize,
593    addr: InstAddress,
594    len: usize,
595) -> Option<&mut [Value]> {
596    if len == 0 {
597        return Some(&mut []);
598    }
599
600    let start = top.checked_add(addr.offset())?;
601    let end = start.checked_add(len)?;
602    values.get_mut(start..end)
603}
604
605#[inline(always)]
606fn slice_error(stack: usize, bottom: usize, addr: InstAddress, len: usize) -> SliceError {
607    SliceError {
608        addr,
609        len,
610        stack: stack.saturating_sub(bottom),
611    }
612}
613
614impl TryClone for Stack {
615    fn try_clone(&self) -> alloc::Result<Self> {
616        Ok(Self {
617            stack: self.stack.try_clone()?,
618            top: self.top,
619        })
620    }
621}
622
623impl TryFromIteratorIn<Value, Global> for Stack {
624    #[inline]
625    fn try_from_iter_in<T: IntoIterator<Item = Value>>(
626        iter: T,
627        alloc: Global,
628    ) -> alloc::Result<Self> {
629        Ok(Self {
630            stack: iter.into_iter().try_collect_in(alloc)?,
631            top: 0,
632        })
633    }
634}
635
636impl From<Vec<Value>> for Stack {
637    fn from(stack: Vec<Value>) -> Self {
638        Self { stack, top: 0 }
639    }
640}
rune/runtime/stack.rs

rune/runtime/
stack.rs
