rune/runtime/
memory.rs

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

rune/runtime/
memory.rs
