rune/core/env/
stack.rs

1use crate::core::{
2    gc::{Context, IntoRoot, Rt, Rto, Slot},
3    object::{ByteFn, NIL, Object, WithLifetime},
4};
5use rune_macros::Trace;
6use std::ops::{Deref, DerefMut, Index, IndexMut, RangeBounds, RangeTo};
7
8/// The stack of lisp objects used to pass and store arguments in the bytecode
9/// VM and interpreter. The top of the stack is index 0 and all indexing
10/// functions operate from top to bottom. The stack is partitioned into frames.
11/// Each frame represents a function call and it's arguments. The API is
12/// designed so that code cannot access elements outside of their frame (doing
13/// so results in a panic). Frames are added and removed with
14/// [push_frame](RootedLispStack::push_frame) and
15/// [pop_frame](RootedLispStack::pop_frame) respectively.
16#[derive(Debug, Default, Trace)]
17pub(crate) struct LispStack<'a> {
18    vec: Vec<Slot<Object<'a>>>,
19    #[no_trace]
20    current: Frame,
21    frames: Vec<FrameStore<'a>>,
22}
23
24/// A function call frame. These mirror the lisp call stack and are used to
25/// display backtraces as well as return.
26#[derive(Debug, Clone, Copy)]
27struct Frame {
28    /// The start of the call frame, as a index from the bottom of the stack
29    /// (not the top).
30    start: usize,
31    /// The maximum size this stack frame can grow.
32    end: usize,
33    /// Number of arguments in this call frame. The first is the count and the
34    /// second is boolean indicating if the last argument is a cons with the
35    /// remaining variadic arguments.
36    arg_cnt: (u16, bool),
37}
38
39impl Default for Frame {
40    fn default() -> Self {
41        Self { start: 0, end: usize::MAX, arg_cnt: (0, false) }
42    }
43}
44
45#[derive(Debug, Clone, Trace)]
46struct ByteFrame<'a> {
47    func: Slot<&'a ByteFn>,
48    #[no_trace]
49    pc_offset: usize,
50}
51
52#[derive(Debug, Clone, Trace)]
53struct FrameStore<'a> {
54    #[no_trace]
55    frame: Frame,
56    bytecode: Option<ByteFrame<'a>>,
57}
58
59impl<'new> IntoRoot<FrameStore<'new>> for FrameStore<'_> {
60    unsafe fn into_root(self) -> FrameStore<'new> {
61        self.with_lifetime()
62    }
63}
64
65impl<'ob> FrameStore<'ob> {
66    fn new(frame: Frame) -> Self {
67        Self { frame, bytecode: None }
68    }
69
70    fn new_bytecode(frame: Frame, func: &'ob ByteFn, pc_offset: usize) -> Self {
71        Self { frame, bytecode: Some(ByteFrame { func: Slot::new(func), pc_offset }) }
72    }
73}
74
75impl<'old, 'new> WithLifetime<'new> for FrameStore<'old> {
76    type Out = FrameStore<'new>;
77
78    unsafe fn with_lifetime(self) -> Self::Out {
79        std::mem::transmute::<FrameStore<'old>, FrameStore<'new>>(self)
80    }
81}
82
83/// Type representing a slice of arguments on the stack. Used to avoid
84/// allocations and copies when calling functions.
85#[derive(Copy, Clone)]
86pub(crate) struct ArgSlice(usize);
87
88impl ArgSlice {
89    pub(crate) fn new(size: usize) -> Self {
90        Self(size)
91    }
92
93    pub(crate) fn len(&self) -> usize {
94        self.0
95    }
96}
97
98// To make this simpler we implement indexing from the top of the stack (end of
99// the vec) instead of the bottom. This is the convention that all the bytecode
100// functions use.
101impl<'a> Index<usize> for RootedLispStack<'a> {
102    type Output = Rto<Object<'a>>;
103
104    fn index(&self, index: usize) -> &Self::Output {
105        let index = self.offset_end(index);
106        &self.vec[index]
107    }
108}
109
110// This impl is specifically for the Stack. It takes the index from the end of
111// the vector instead of the start. This matches how the lisp stack behaves.
112impl IndexMut<usize> for RootedLispStack<'_> {
113    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
114        let index = self.offset_end(index);
115        &mut self.vec[index]
116    }
117}
118
119// This impl is specifically for the Stack. It takes the range from the end of
120// the vector instead of the start. This matches how the lisp stack behaves.
121impl<'a> Index<RangeTo<usize>> for RootedLispStack<'a> {
122    type Output = [Rto<Object<'a>>];
123
124    fn index(&self, index: RangeTo<usize>) -> &Self::Output {
125        assert!(index.end <= self.len());
126        let end = self.len() - index.end;
127        let vec: &[Rto<Object>] = &self.vec;
128        &vec[end..]
129    }
130}
131
132impl<'a> RootedLispStack<'a> {
133    pub(crate) fn push_bytecode_frame(
134        &mut self,
135        start: usize,
136        depth: usize,
137        func: &ByteFn,
138        pc: usize,
139    ) {
140        assert!(start <= self.len());
141        assert!(self.current.start <= start);
142        self.frames.push(FrameStore::new_bytecode(self.current, func, pc));
143        let end = start + depth;
144        // allocate space so that we don't have to reallocate later. This will
145        // also let us do unchecked pushes later.
146        if end > self.vec.capacity() {
147            assert!(end - self.vec.len() < 100); // make sure this doesn't blow up
148            self.vec.reserve(end - self.vec.len());
149        }
150        self.current = Frame { start, end, ..Frame::default() };
151    }
152
153    pub(crate) fn push_frame(&mut self, arg_cnt: usize) {
154        assert!(arg_cnt <= self.len());
155        let start = self.len() - arg_cnt;
156        assert!(self.current.start <= start);
157        self.frames.push(FrameStore::new(self.current));
158        self.current =
159            Frame { start, arg_cnt: (u16::try_from(arg_cnt).unwrap(), false), ..Frame::default() };
160    }
161
162    /// Remove all the stack variables in the current frame and switch to the
163    /// previous one
164    pub(crate) fn pop_frame(&mut self) {
165        self.vec.truncate(self.current.start);
166        self.current = self.frames.last().unwrap().frame;
167        self.frames.pop();
168    }
169
170    pub(crate) fn get_bytecode_frame(&self, idx: usize) -> Option<(&Rto<&'a ByteFn>, usize)> {
171        let frame = self.frames.get(idx)?;
172        let bytecode = frame.bytecode.as_ref()?;
173        let func = &bytecode.func;
174        let pc = bytecode.pc_offset;
175        Some((func, pc))
176    }
177
178    pub(crate) fn prev_bytecode_frame(&self) -> Option<(&Rto<&'a ByteFn>, usize)> {
179        self.get_bytecode_frame(self.frames.len() - 1)
180    }
181
182    pub(crate) fn current_frame(&self) -> usize {
183        self.frames.len()
184    }
185
186    pub(crate) fn unwind_frames(&mut self, frame: usize) {
187        if frame == self.current_frame() {
188            return; /* no frames to unwind */
189        }
190        assert!(frame < self.current_frame());
191        self.current = self.frames[frame].frame;
192        self.frames.truncate(frame);
193    }
194
195    pub(crate) fn len(&self) -> usize {
196        self.vec.len()
197    }
198
199    pub(crate) fn set_depth(&mut self, depth: usize) {
200        let end = self.current.start + depth;
201        self.current.end = end;
202
203        if end > self.vec.capacity() {
204            assert!(end - self.vec.len() < 1000); // make sure this doesn't blow up if we have a bug
205            self.vec.reserve(end - self.vec.len());
206        }
207    }
208
209    pub(crate) fn set_arg_count(&mut self, arg_cnt: u16, rest: bool) {
210        self.current.arg_cnt = (arg_cnt, rest);
211    }
212
213    pub(crate) fn push<T: IntoRoot<Slot<Object<'a>>>>(&mut self, value: T) {
214        if self.len() >= self.current.end {
215            panic!(
216                "overflowed max depth - len was {}, but limit was {}",
217                self.len(),
218                self.current.end
219            );
220        }
221        // could use https://github.com/rust-lang/rust/issues/100486
222        self.vec.push(value);
223    }
224
225    pub(crate) fn pop<'ob>(&mut self, cx: &'ob Context) -> Object<'ob> {
226        assert!(self.len() > self.current.start);
227        *self.vec.bind_mut(cx).pop().unwrap()
228    }
229
230    pub(crate) fn top(&mut self) -> &mut Rto<Object<'a>> {
231        assert!(self.len() > self.current.start);
232        self.vec.last_mut().unwrap()
233    }
234
235    pub(crate) fn offset_end(&self, i: usize) -> usize {
236        assert!(i < self.len());
237        let from_end = self.len() - (i + 1);
238        assert!(self.current.start <= from_end);
239        from_end
240    }
241
242    pub(crate) fn push_ref(&mut self, i: impl Into<i32>, cx: &Context) {
243        let obj = self[i.into() as usize].bind(cx);
244        self.push(obj);
245    }
246
247    pub(crate) fn set_ref(&mut self, i: impl Into<usize>) {
248        let index = self.offset_end(i.into());
249        self.vec.swap_remove(index);
250    }
251
252    pub(crate) fn fill_extra_args(&mut self, fill_args: u16) {
253        for _ in 0..fill_args {
254            self.push(NIL);
255        }
256    }
257
258    pub(crate) fn remove_top(&mut self, i: usize) {
259        if i == 0 {
260            return;
261        }
262        let offset = self.offset_end(i - 1);
263        self.truncate(offset);
264    }
265
266    pub(crate) fn truncate(&mut self, len: usize) {
267        self.vec.truncate(len);
268    }
269
270    pub(crate) fn extend_from_slice(&mut self, src: &[Object]) {
271        self.vec.extend_from_slice(src);
272    }
273
274    // This indexing is backwards from the normal stack sematics, so we add
275    // "as_vec" to the name to hopefully make it clearer
276    pub(crate) fn extend_as_vec_from_within(&mut self, src: impl RangeBounds<usize>) {
277        self.vec.extend_from_within(src);
278    }
279
280    pub(crate) fn frames<'b>(&'b self) -> &'b [Rto<Object<'a>>] {
281        &self.vec[self.current.start..]
282    }
283
284    pub(crate) fn arg_count(&self) -> usize {
285        self.len() - self.current.start
286    }
287
288    pub(crate) fn current_args(&self) -> &[Rto<Object<'a>>] {
289        // index as vec
290        &self.vec[self.current.start..]
291    }
292
293    pub(crate) fn arg_slice(&self, arg_slice: ArgSlice) -> &[Rto<Object<'a>>] {
294        // index as stack
295        &self[..arg_slice.0]
296    }
297}
298
299/// A function call Frame.
300///
301/// This is a guard type that will pop the frame when it
302/// goes out of scope.
303pub(crate) struct CallFrame<'brw, 'rt> {
304    env: &'brw mut Rt<super::Env<'rt>>,
305}
306
307impl<'brw, 'rt> CallFrame<'brw, 'rt> {
308    /// Create a new function call frame with a drop guard to be removed when
309    /// this goes out of scope.
310    pub(crate) fn new(env: &'brw mut Rt<super::Env<'rt>>) -> Self {
311        Self::new_with_args(env, 0)
312    }
313
314    /// Create a new function call frame with the top args on the stack. This
315    /// frame will be removed when the `CallFrame` goes out of scope.
316    pub(crate) fn new_with_args(env: &'brw mut Rt<super::Env<'rt>>, args: usize) -> Self {
317        env.stack.push_frame(args);
318        Self { env }
319    }
320
321    /// Push an argument onto the stack as part of this call frame
322    pub(crate) fn push_arg(&mut self, arg: impl IntoRoot<Slot<Object<'rt>>>) {
323        self.env.stack.push(arg);
324    }
325
326    /// Set the total argument count before a function call
327    pub(crate) fn finalize_arguments(&mut self) {
328        let args = self.env.stack.arg_count().try_into().unwrap();
329        self.env.stack.set_arg_count(args, false);
330    }
331
332    pub(crate) fn arg_count(&self) -> usize {
333        let count1 = self.env.stack.arg_count();
334        let count2 = self.env.stack.current.arg_cnt.0 as usize;
335        assert_eq!(count1, count2);
336        count1
337    }
338
339    pub(crate) fn arg_slice(&self) -> &[Rto<Object<'rt>>] {
340        &self.env.stack[..self.arg_count()]
341    }
342
343    /// Push a slice of arguments onto the stack as part of this call frame.
344    pub(crate) fn push_arg_slice(&mut self, src: &[Object]) {
345        self.env.stack.extend_from_slice(src);
346    }
347}
348
349impl Drop for CallFrame<'_, '_> {
350    fn drop(&mut self) {
351        self.env.stack.pop_frame();
352    }
353}
354
355impl<'rt> Deref for CallFrame<'_, 'rt> {
356    type Target = Rt<super::Env<'rt>>;
357
358    fn deref(&self) -> &Self::Target {
359        self.env
360    }
361}
362
363impl DerefMut for CallFrame<'_, '_> {
364    fn deref_mut(&mut self) -> &mut Self::Target {
365        self.env
366    }
367}