rune/
interpreter.rs

Help
1//! The basic elisp interpreter.
2use crate::{
3    core::{
4        cons::{Cons, ElemStreamIter, IntoArray},
5        env::{CallFrame, Env, sym},
6        error::{Type, TypeError},
7        gc::{Context, Rt, Rto, Slot},
8        object::{Function, Gc, List, ListType, NIL, Object, ObjectType, Symbol, TRUE, TagType},
9    },
10    data::LispError,
11    eval::{ErrorType, EvalError, EvalResult, add_trace},
12    rooted_iter,
13};
14use anyhow::Context as _;
15use anyhow::Result as AnyResult;
16use anyhow::{bail, ensure};
17use fallible_streaming_iterator::FallibleStreamingIterator;
18use rune_core::macros::{bail_err, call, error, rebind, root};
19use rune_macros::defun;
20
21struct Interpreter<'brw, 'rt> {
22    vars: &'brw mut Rt<Vec<Slot<&'rt Cons>>>,
23    env: &'brw mut Rt<Env<'rt>>,
24}
25
26#[defun]
27pub(crate) fn eval<'ob>(
28    form: &Rto<Object>,
29    lexical: Option<&Rto<Object>>,
30    env: &mut Rt<Env>,
31    cx: &'ob mut Context,
32) -> Result<Object<'ob>, anyhow::Error> {
33    cx.garbage_collect(false);
34    root!(vars, new(Vec<Slot<&Cons>>), cx);
35    if let Some(ObjectType::Cons(cons)) = lexical.map(|x| x.untag(cx)) {
36        for var in cons.elements() {
37            if let Some(binding) = var?.cons() {
38                vars.push(binding);
39            }
40        }
41    }
42    let mut interpreter = Interpreter { vars, env };
43    interpreter.eval_form(form, cx).map_err(Into::into)
44}
45
46impl Interpreter<'_, '_> {
47    fn eval_form<'ob>(&mut self, rt: &Rto<Object>, cx: &'ob mut Context) -> EvalResult<'ob> {
48        match rt.untag(cx) {
49            ObjectType::Symbol(sym) => self.var_ref(sym, cx),
50            ObjectType::Cons(_) => {
51                let x = rt.try_as().unwrap();
52                self.eval_sexp(x, cx)
53            }
54            _ => Ok(rt.bind(cx)),
55        }
56    }
57
58    pub(crate) fn eval_sexp<'ob>(
59        &mut self,
60        cons: &Rto<Gc<&Cons>>,
61        cx: &'ob mut Context,
62    ) -> EvalResult<'ob> {
63        let cons = cons.bind(cx);
64        let forms = cons.cdr();
65        root!(forms, cx);
66        match cons.car().untag() {
67            ObjectType::Symbol(sym) => match sym {
68                sym::QUOTE => self.quote(forms.bind(cx), cx),
69                sym::LET => self.eval_let(forms, true, cx),
70                sym::LET_STAR => self.eval_let(forms, false, cx),
71                sym::IF => self.eval_if(forms, cx),
72                sym::AND => self.eval_and(forms, cx),
73                sym::OR => self.eval_or(forms, cx),
74                sym::COND => self.eval_cond(forms, cx),
75                sym::WHILE => self.eval_while(forms, cx),
76                sym::PROGN | sym::INLINE => self.eval_progn(forms, cx),
77                sym::PROG1 => self.eval_progx(forms, 1, cx),
78                sym::PROG2 => self.eval_progx(forms, 2, cx),
79                sym::SETQ => self.setq(forms, cx),
80                sym::DEFVAR | sym::DEFCONST => self.defvar(forms, cx),
81                sym::FUNCTION => self.eval_function(forms, cx),
82                sym::INTERACTIVE => Ok(NIL), // TODO: implement
83                sym::CATCH => self.catch(forms, cx),
84                sym::THROW => self.throw(forms.bind(cx), cx),
85                sym::CONDITION_CASE => self.condition_case(forms, cx),
86                sym::SAVE_CURRENT_BUFFER => self.save_current_buffer(forms, cx),
87                sym::SAVE_EXCURSION => self.save_excursion(forms, cx),
88                sym::UNWIND_PROTECT => self.unwind_protect(forms, cx),
89                _ => {
90                    root!(sym, cx);
91                    self.eval_call(sym, forms, cx)
92                }
93            },
94            other => Err(error!("Invalid Function: {other}")),
95        }
96    }
97
98    fn catch<'ob>(&mut self, obj: &Rto<Object>, cx: &'ob mut Context) -> EvalResult<'ob> {
99        rooted_iter!(forms, obj, cx);
100        let Some(tag) = forms.next()? else {
101            bail_err!(LispError::arg_cnt(sym::CATCH, 1, 0, cx))
102        };
103        // push this tag on the catch stack
104        self.env.catch_stack.push(tag);
105        let result = match self.implicit_progn(forms, cx) {
106            Ok(x) => Ok(rebind!(x, cx)),
107            Err(e) => {
108                if let ErrorType::Throw(id) = e.error
109                    && let Some((throw_tag, data)) = self.env.get_exception(id)
110                {
111                    let catch_tag = self.env.catch_stack.last().unwrap();
112                    // TODO: Remove binds
113                    if catch_tag == throw_tag {
114                        return Ok(data.bind(cx));
115                    }
116                }
117                Err(e)
118            }
119        };
120        // pop this tag from the catch stack
121        self.env.catch_stack.pop();
122        result
123    }
124
125    fn throw<'ob>(&mut self, obj: Object, cx: &'ob Context) -> EvalResult<'ob> {
126        let [tag, value] = match obj.into_array()? {
127            Ok(x) => x,
128            Err(e) => bail_err!(LispError::arg_cnt(sym::THROW, 2, e, cx)),
129        };
130
131        // Need to check now that there is a catch, because we may have a
132        // condition-case along the unwind path
133        if self.env.catch_stack.iter().any(|x| x.bind(cx) == tag) {
134            Err(EvalError::throw(tag, value, self.env))
135        } else {
136            Err(error!("No catch for {tag}"))
137        }
138    }
139
140    fn defvar<'ob>(&mut self, obj: &Rto<Object>, cx: &'ob mut Context) -> EvalResult<'ob> {
141        rooted_iter!(forms, obj, cx);
142        // (defvar x ...)                 // (defvar)
143        let Some(sym) = forms.next()? else {
144            bail_err!(LispError::arg_cnt(sym::DEFVAR, 1, 0, cx))
145        };
146        let name: Symbol = sym.bind(cx).try_into()?;
147        root!(name, cx);
148        let value = match forms.next()? {
149            // (defvar x y)
150            Some(value) => rebind!(self.eval_form(value, cx)?),
151            // (defvar x)
152            None => NIL,
153        };
154        self.env.defvar(name.bind(cx), value)?;
155        Ok(value)
156    }
157
158    fn eval_call<'ob>(
159        &mut self,
160        sym: &Rto<Symbol>,
161        args: &Rto<Object>,
162        cx: &'ob mut Context,
163    ) -> EvalResult<'ob> {
164        let Some(func) = sym.bind(cx).follow_indirect(cx) else {
165            bail_err!("Invalid function: {sym}")
166        };
167        root!(func, cx);
168
169        match func.bind(cx).as_cons_pair() {
170            Ok((sym::AUTOLOAD, _)) => {
171                crate::eval::autoload_do_load(func.cast(), None, None, self.env, cx)
172                    .map_err(|e| add_trace(e, "autoload", &[]))?;
173                func.set(sym.bind(cx).follow_indirect(cx).unwrap());
174            }
175            Ok((sym::MACRO, mcro)) => {
176                let iter = args.bind(cx).into_list()?;
177                let mut frame = CallFrame::new(self.env);
178                for arg in iter {
179                    frame.push_arg(arg?);
180                }
181                root!(mcro, mcro.tag(), cx);
182                let name = sym.bind(cx).name().to_owned();
183                let value = mcro.call(&mut frame, Some(&name), cx)?;
184                drop(frame);
185                root!(value, cx);
186                return self.eval_form(value, cx);
187            }
188            _ => {}
189        }
190
191        rooted_iter!(iter, args, cx);
192        root!(args, new(Vec), cx);
193        while let Some(x) = iter.next()? {
194            let result = self.eval_form(x, cx)?;
195            args.push(result);
196        }
197        let frame = &mut CallFrame::new(self.env);
198        frame.push_arg_slice(Rt::bind_slice(args, cx));
199        let name = sym.bind(cx).name().to_owned();
200        func.call(frame, Some(&name), cx)
201    }
202
203    fn eval_function<'ob>(
204        &mut self,
205        obj: &Rto<Object<'ob>>,
206        cx: &'ob mut Context,
207    ) -> EvalResult<'ob> {
208        let form = match obj.bind(cx).into_array()? {
209            Ok([x]) => x,
210            Err(e) => bail_err!(LispError::arg_cnt(sym::FUNCTION, 1, e, cx)),
211        };
212        root!(form, cx); // Polonius
213        let Ok((sym::LAMBDA, doc)) = form.bind(cx).as_cons_pair() else {
214            return Ok(form.bind(cx));
215        };
216        root!(doc, doc.tag(), cx);
217        let body = rebind!(self.replace_doc_symbol(doc, cx)?);
218        let env = {
219            let vars = self.vars.bind_ref(cx);
220            let mut tail = Object::from(Cons::new1(true, cx));
221            for var in vars {
222                tail = Cons::new(**var, tail, cx).into();
223            }
224            tail
225        };
226        // This function will trim the environment down to only what is actually
227        // captured in the closure
228        if let Some(closure_fn) = self.env.vars.get(sym::INTERNAL_MAKE_INTERPRETED_CLOSURE_FUNCTION)
229            && closure_fn.bind(cx) != sym::NIL
230        {
231            let closure_fn: Result<&Rto<Function>, _> = closure_fn.try_as();
232            if let Ok(closure_fn) = closure_fn {
233                let lambda = Object::from(Cons::new(sym::LAMBDA, body, cx));
234                let closure_fn: Function = closure_fn.bind(cx);
235                root!(closure_fn, cx);
236                return call!(closure_fn, lambda, env; self.env, cx);
237            }
238        }
239        // If the closure capture function is not defined, use the whole environment
240        let end = Cons::new(env, body, cx);
241        Ok(Cons::new(sym::CLOSURE, end, cx).into())
242    }
243
244    /// Handle special case of (:documentation form) to build the docstring
245    /// dynamically. If the docstring is not of this form, just return the current body.
246    fn replace_doc_symbol<'ob>(
247        &mut self,
248        quoted: &Rto<Object>,
249        cx: &'ob mut Context,
250    ) -> Result<Object<'ob>, EvalError> {
251        let Some((arg_list, doc, body)) = (|| {
252            let mut forms = quoted.bind(cx).as_list().ok()?;
253            let arg_list = forms.next()?.ok()?;
254            let doc = forms.next()?.ok()?;
255            let body = forms.rest().ok()?.map(Into::into).unwrap_or(NIL);
256            match doc.as_cons_pair() {
257                Ok((sym::KW_DOCUMENTATION, ObjectType::Cons(doc))) => {
258                    Some((arg_list, doc, cx.bind(body)))
259                }
260                _ => None,
261            }
262        })() else {
263            return Ok(quoted.bind(cx));
264        };
265        root!(arg_list, cx);
266        root!(body, cx);
267        // ((<args..>) (doc_str) ...)
268        let docstring = {
269            root!(doc_form, doc.car(), cx);
270            let docstring = rebind!(self.eval_form(doc_form, cx)?);
271            // Handle the special case of oclosure docstrings being a symbol
272            match docstring.untag() {
273                ObjectType::Symbol(sym) => cx.add(sym.name()),
274                _ => docstring,
275            }
276        };
277        // ((<args..>) (:documentation <form>) body)
278        Ok(Cons::new(arg_list, Cons::new(docstring, body, cx), cx).into())
279    }
280
281    fn eval_progx<'ob>(
282        &mut self,
283        obj: &Rto<Object>,
284        prog_num: u16,
285        cx: &'ob mut Context,
286    ) -> EvalResult<'ob> {
287        let mut count = 0;
288        root!(returned_form, None::<Object>, cx);
289        rooted_iter!(forms, obj, cx);
290        while let Some(form) = forms.next()? {
291            let value = self.eval_form(form, cx)?;
292            count += 1;
293            if prog_num == count {
294                returned_form.set(Some(value));
295            }
296        }
297        match &**returned_form {
298            Some(x) => Ok(x.bind(cx)),
299            None => {
300                let name = match prog_num {
301                    1 => sym::PROG1,
302                    2 => sym::PROG2,
303                    _ => sym::PROGN,
304                };
305                Err(LispError::arg_cnt(name, prog_num, count, cx).into())
306            }
307        }
308    }
309
310    fn eval_progn<'ob>(&mut self, obj: &Rto<Object>, cx: &'ob mut Context) -> EvalResult<'ob> {
311        rooted_iter!(forms, obj, cx);
312        self.implicit_progn(forms, cx)
313    }
314
315    fn eval_while<'ob>(&mut self, obj: &Rto<Object>, cx: &'ob mut Context) -> EvalResult<'ob> {
316        let (condition, body) = {
317            let list: List = obj.bind(cx).try_into()?;
318            match list.untag() {
319                ListType::Nil => bail_err!(LispError::arg_cnt(sym::WHILE, 1, 0, cx)),
320                ListType::Cons(cons) => (cons.car(), cons.cdr()),
321            }
322        };
323        root!(condition, cx);
324        root!(body, cx);
325        while self.eval_form(condition, cx)? != NIL {
326            rooted_iter!(forms, &*body, cx);
327            self.implicit_progn(forms, cx)?;
328        }
329        Ok(NIL)
330    }
331
332    fn eval_cond<'ob>(&mut self, obj: &Rto<Object>, cx: &'ob mut Context) -> EvalResult<'ob> {
333        rooted_iter!(forms, obj, cx);
334        while let Some(form) = forms.next()? {
335            rooted_iter!(clause, form, cx);
336            if let Some(first) = clause.next()? {
337                let condition = self.eval_form(first, cx)?;
338                if condition != NIL {
339                    return if clause.is_empty() {
340                        Ok(rebind!(condition, cx))
341                    } else {
342                        self.implicit_progn(clause, cx)
343                    };
344                }
345            }
346        }
347        Ok(NIL)
348    }
349
350    fn eval_and<'ob>(&mut self, obj: &Rto<Object>, cx: &'ob mut Context) -> EvalResult<'ob> {
351        root!(last, TRUE, cx);
352        rooted_iter!(forms, obj, cx);
353        while let Some(form) = forms.next()? {
354            let result = self.eval_form(form, cx)?;
355            if result == NIL {
356                return Ok(NIL);
357            }
358            last.set(result);
359        }
360        Ok(last.bind(cx))
361    }
362
363    fn eval_or<'ob>(&mut self, obj: &Rto<Object>, cx: &'ob mut Context) -> EvalResult<'ob> {
364        rooted_iter!(forms, obj, cx);
365        while let Some(form) = forms.next()? {
366            let result = self.eval_form(form, cx)?;
367            if result != NIL {
368                return Ok(rebind!(result, cx));
369            }
370        }
371        Ok(NIL)
372    }
373
374    fn eval_if<'ob>(&mut self, obj: &Rto<Object>, cx: &'ob mut Context) -> EvalResult<'ob> {
375        rooted_iter!(forms, obj, cx);
376        let Some(condition) = forms.next()? else {
377            bail_err!(LispError::arg_cnt(sym::IF, 2, 0, cx))
378        };
379        root!(condition, cx);
380        let Some(true_branch) = forms.next()? else {
381            bail_err!(LispError::arg_cnt(sym::IF, 2, 1, cx))
382        };
383        root!(true_branch, cx);
384        #[expect(clippy::if_not_else)]
385        if self.eval_form(condition, cx)? != NIL {
386            self.eval_form(true_branch, cx)
387        } else {
388            self.implicit_progn(forms, cx)
389        }
390    }
391
392    fn setq<'ob>(&mut self, obj: &Rto<Object>, cx: &'ob mut Context) -> EvalResult<'ob> {
393        rooted_iter!(forms, obj, cx);
394        let mut arg_cnt = 0;
395        root!(last_value, NIL, cx);
396        while let Some((var, val)) = Self::pairs(&mut forms, cx)? {
397            match (var.untag(), val) {
398                (ObjectType::Symbol(var), Some(val)) => {
399                    root!(var, cx);
400                    root!(val, cx);
401                    let val = rebind!(self.eval_form(val, cx)?);
402                    self.var_set(var.bind(cx), val, cx)?;
403                    last_value.set(val);
404                }
405                (_, Some(_)) => bail_err!(TypeError::new(Type::Symbol, var)),
406                (_, None) => bail_err!(LispError::arg_cnt(sym::SETQ, arg_cnt, arg_cnt + 1, cx)),
407            }
408            arg_cnt += 2;
409        }
410        if arg_cnt < 2 {
411            Err(LispError::arg_cnt(sym::SETQ, 2, arg_cnt, cx).into())
412        } else {
413            Ok(last_value.bind(cx))
414        }
415    }
416
417    fn pairs<'ob>(
418        iter: &mut ElemStreamIter<'_>,
419        cx: &'ob Context,
420    ) -> AnyResult<Option<(Object<'ob>, Option<Object<'ob>>)>> {
421        let first = iter.next()?.map(|x| x.bind(cx));
422        let second = iter.next()?.map(|x| x.bind(cx));
423        Ok(first.map(|first| (first, second)))
424    }
425
426    fn var_ref<'ob>(&self, sym: Symbol, cx: &'ob Context) -> EvalResult<'ob> {
427        if sym.is_const() {
428            Ok(sym.into())
429        } else {
430            let mut iter = self.vars.iter().rev();
431            match iter.find_map(|cons| (cons.car(cx) == sym).then(|| cons.cdr(cx))) {
432                Some(value) => Ok(value),
433                None => match self.env.vars.get(sym) {
434                    Some(v) => Ok(v.bind(cx)),
435                    None => Err(error!("Void variable: {sym}")),
436                },
437            }
438        }
439    }
440
441    fn var_set(&mut self, name: Symbol, new_value: Object, cx: &Context) -> AnyResult<()> {
442        let mut iter = self.vars.iter().rev();
443        match iter.find(|cons| (cons.car(cx) == name)) {
444            Some(value) => {
445                value.bind(cx).set_cdr(new_value).expect("variables should never be immutable");
446                Ok(())
447            }
448            None => self.env.set_var(name, new_value),
449        }
450    }
451
452    fn quote<'ob>(&self, value: Object<'ob>, cx: &Context) -> EvalResult<'ob> {
453        match value.into_array()? {
454            Ok([x]) => Ok(x),
455            Err(e) => Err(LispError::arg_cnt(sym::QUOTE, 1, e, cx).into()),
456        }
457    }
458
459    fn eval_let<'ob>(
460        &mut self,
461        form: &Rto<Object>,
462        parallel: bool,
463        cx: &'ob mut Context,
464    ) -> EvalResult<'ob> {
465        rooted_iter!(iter, form, cx);
466        let prev_len = self.vars.len();
467        // (let x ...)                   // (let)
468        let Some(obj) = iter.next()? else { bail_err!(LispError::arg_cnt(sym::LET, 1, 0, cx)) };
469        let varbind_count = if parallel {
470            self.let_bind_parallel(obj, cx)
471        } else {
472            self.let_bind_serial(obj, cx)
473        }?;
474        let obj = rebind!(self.implicit_progn(iter, cx)?);
475        // Remove old bindings
476        self.vars.truncate(prev_len);
477        self.env.unbind(varbind_count, cx);
478        Ok(obj)
479    }
480
481    fn let_bind_serial(&mut self, form: &Rto<Object>, cx: &mut Context) -> Result<u16, EvalError> {
482        let mut varbind_count = 0;
483        rooted_iter!(bindings, form, cx);
484        while let Some(binding) = bindings.next()? {
485            match binding.untag(cx) {
486                // (let ((x y)))
487                ObjectType::Cons(_) => {
488                    let cons = binding.as_cons();
489                    let val = rebind!(self.let_bind_value(cons, cx)?);
490                    let var: Symbol =
491                        cons.untag(cx).car().try_into().context("let variable must be a symbol")?;
492                    varbind_count += self.create_let_binding(var, val, cx);
493                }
494                // (let (x))
495                ObjectType::Symbol(sym) => {
496                    varbind_count += self.create_let_binding(sym, NIL, cx);
497                }
498                // (let (1))
499                x => bail_err!(TypeError::new(Type::Cons, x)),
500            }
501        }
502        Ok(varbind_count)
503    }
504
505    fn let_bind_parallel(
506        &mut self,
507        form: &Rto<Object>,
508        cx: &mut Context,
509    ) -> Result<u16, EvalError> {
510        root!(let_bindings, new(Vec<(Slot<Symbol>, Slot<Object>)>), cx);
511        rooted_iter!(bindings, form, cx);
512        while let Some(binding) = bindings.next()? {
513            match binding.untag(cx) {
514                // (let ((x y)))
515                ObjectType::Cons(_) => {
516                    let cons = binding.as_cons();
517                    let var = rebind!(self.let_bind_value(cons, cx)?);
518                    let sym: Symbol =
519                        cons.untag(cx).car().try_into().context("let variable must be a symbol")?;
520                    let_bindings.push((sym, var));
521                }
522                // (let (x))
523                ObjectType::Symbol(sym) => {
524                    let_bindings.push((sym, NIL));
525                }
526                // (let (1))
527                x => bail_err!(TypeError::new(Type::Cons, x)),
528            }
529        }
530        let mut sum = 0;
531        for (var, val) in let_bindings.bind_ref(cx) {
532            sum += self.create_let_binding(**var, **val, cx);
533        }
534        Ok(sum)
535    }
536
537    fn create_let_binding(&mut self, var: Symbol, val: Object, cx: &Context) -> u16 {
538        if var.is_special() {
539            self.env.varbind(var, val, cx);
540            // return 1 if the variable is bound
541            1
542        } else {
543            self.vars.push(Cons::new(var, val, cx));
544            0
545        }
546    }
547
548    fn let_bind_value<'ob>(
549        &mut self,
550        cons: &Rto<Gc<&Cons>>,
551        cx: &'ob mut Context,
552    ) -> Result<Object<'ob>, EvalError> {
553        rooted_iter!(iter, cons.bind(cx).cdr(), cx);
554        let value = match iter.next()? {
555            // (let ((x y)))
556            Some(x) => self.eval_form(x, cx)?,
557            // (let ((x)))
558            None => NIL,
559        };
560        // (let ((x y z ..)))
561        if !iter.is_empty() {
562            bail_err!("Let binding can only have 1 value");
563        }
564        Ok(value)
565    }
566
567    fn implicit_progn<'ob>(
568        &mut self,
569        mut forms: ElemStreamIter<'_>,
570        cx: &'ob mut Context,
571    ) -> EvalResult<'ob> {
572        root!(last, NIL, cx);
573        while let Some(form) = forms.next()? {
574            let value = self.eval_form(form, cx)?;
575            last.set(value);
576        }
577        Ok(last.bind(cx))
578    }
579
580    fn unwind_protect<'ob>(&mut self, obj: &Rto<Object>, cx: &'ob mut Context) -> EvalResult<'ob> {
581        rooted_iter!(forms, obj, cx);
582        let Some(body) = forms.next()? else {
583            bail_err!(LispError::arg_cnt(sym::UNWIND_PROTECT, 1, 0, cx))
584        };
585        match self.eval_form(body, cx) {
586            Ok(x) => {
587                root!(x, cx);
588                self.implicit_progn(forms, cx)?;
589                Ok(x.bind(cx))
590            }
591            Err(e) => {
592                self.implicit_progn(forms, cx)?;
593                Err(e)
594            }
595        }
596    }
597
598    fn save_excursion<'ob>(&mut self, form: &Rto<Object>, cx: &'ob mut Context) -> EvalResult<'ob> {
599        let point = self.env.current_buffer.get().text.cursor();
600        let buffer = self.env.current_buffer.get().lisp_buffer(cx);
601        root!(buffer, cx);
602        let result = rebind!(self.eval_progn(form, cx)?);
603        self.env.set_buffer(buffer.bind(cx));
604        let buf = self.env.current_buffer.get_mut();
605        buf.text.set_cursor(point.chars());
606        Ok(result)
607    }
608
609    fn save_current_buffer<'ob>(
610        &mut self,
611        form: &Rto<Object>,
612        cx: &'ob mut Context,
613    ) -> EvalResult<'ob> {
614        let buffer = self.env.current_buffer.get().lisp_buffer(cx);
615        root!(buffer, cx);
616        let result = rebind!(self.eval_progn(form, cx)?);
617        self.env.set_buffer(buffer.bind(cx));
618        Ok(result)
619    }
620
621    fn condition_case<'ob>(&mut self, form: &Rto<Object>, cx: &'ob mut Context) -> EvalResult<'ob> {
622        rooted_iter!(forms, form, cx);
623        let Some(var) = forms.next()? else {
624            bail_err!(LispError::arg_cnt(sym::CONDITION_CASE, 2, 0, cx))
625        };
626        root!(var, cx);
627        let Some(bodyform) = forms.next()? else {
628            bail_err!(LispError::arg_cnt(sym::CONDITION_CASE, 2, 1, cx))
629        };
630        let err = match self.eval_form(bodyform, cx) {
631            Ok(x) => return Ok(rebind!(x, cx)),
632            Err(e) => e,
633        };
634        if matches!(err.error, ErrorType::Throw(_)) {
635            return Err(err);
636        }
637        while let Some(handler) = forms.next()? {
638            match handler.untag(cx) {
639                ObjectType::Cons(cons) => {
640                    // Check that conditions match
641                    let condition = cons.car();
642                    match condition.untag() {
643                        ObjectType::Symbol(sym::ERROR | sym::VOID_VARIABLE) => {}
644                        // TODO: Remove this once error handling is correctly implemented
645                        ObjectType::Symbol(s) if s.name() == "cl--generic-cyclic-definition" => {}
646                        ObjectType::Cons(conditions) => {
647                            for condition in conditions {
648                                let condition = condition?;
649                                // TODO: Handle different error symbols
650                                if condition != sym::DEBUG && condition != sym::ERROR {
651                                    bail_err!("non-error conditions {condition} not yet supported")
652                                }
653                            }
654                        }
655                        _ => bail_err!("Invalid condition handler: {condition}"),
656                    }
657
658                    // Call handlers with error
659                    let error = match err.error {
660                        ErrorType::Signal(id) => {
661                            let Some((sym, data)) = self.env.get_exception(id) else {
662                                unreachable!("Exception not found")
663                            };
664                            Cons::new(sym, data, cx)
665                        }
666                        ErrorType::Err(err) => {
667                            let err_str = format!("{err}");
668                            if let Ok(lisp_error) = err.downcast::<LispError>() {
669                                lisp_error.bind(cx)
670                            } else {
671                                // TODO: Need to remove the anyhow branch once
672                                // full errors are implemented
673                                Cons::new(sym::ERROR, err_str, cx)
674                            }
675                        }
676                        _ => unreachable!("Error type throw was not handled"),
677                    };
678
679                    let binding = Cons::new(var, error, cx);
680                    self.vars.push(binding);
681                    let list: List = match cons.cdr().try_into() {
682                        Ok(x) => x,
683                        Err(_) => return Ok(NIL),
684                    };
685                    rooted_iter!(handlers, list, cx);
686                    let result = self.implicit_progn(handlers, cx)?;
687                    self.vars.pop();
688                    return Ok(result);
689                }
690                ObjectType::NIL => {}
691                invalid => bail_err!("Invalid condition handler: {invalid}"),
692            }
693        }
694        Err(err)
695    }
696}
697
698pub(crate) fn call_closure<'ob>(
699    closure: &Rto<Gc<&Cons>>,
700    arg_cnt: usize,
701    name: &str,
702    env: &mut Rt<Env>,
703    cx: &'ob mut Context,
704) -> EvalResult<'ob> {
705    cx.garbage_collect(false);
706    let closure: &Cons = closure.untag(cx);
707    match closure.car().untag() {
708        ObjectType::Symbol(sym::CLOSURE) => {
709            rooted_iter!(forms, closure.cdr(), cx);
710            let args = Rt::bind_slice(&env.stack[..arg_cnt], cx);
711            let vars = bind_variables(&mut forms, args, name, cx)?;
712            debug!("call vars: {vars:?}");
713            root!(vars, cx);
714            Interpreter { vars, env }.implicit_progn(forms, cx)
715        }
716        other => Err(TypeError::new(Type::Func, other).into()),
717    }
718}
719
720fn bind_variables<'a>(
721    forms: &mut ElemStreamIter<'_>,
722    args: &[Object<'a>],
723    name: &str,
724    cx: &'a Context,
725) -> AnyResult<Vec<&'a Cons>> {
726    // Add closure environment to variables
727    // (closure ((x . 1) (y . 2) t) ...)
728    //          ^^^^^^^^^^^^^^^^^^^
729    let Some(env) = forms.next()? else { bail!("Closure missing environment") };
730    let mut vars = parse_closure_env(env.bind(cx))?;
731
732    // Add function arguments to variables
733    // (closure (t) (x y &rest z) ...)
734    //              ^^^^^^^^^^^^^
735    let Some(arg_list) = forms.next()? else { bail!("Closure missing argument list") };
736    bind_args(arg_list.bind(cx), args, &mut vars, name, cx)?;
737    Ok(vars)
738}
739
740fn parse_closure_env(obj: Object<'_>) -> AnyResult<Vec<&Cons>> {
741    let forms = obj.as_list()?;
742    let mut env = Vec::new();
743    for form in forms {
744        match form?.untag() {
745            ObjectType::Cons(pair) => {
746                env.push(pair);
747            }
748            ObjectType::TRUE => break,
749            x => bail!("Invalid closure environment member: {x}"),
750        }
751    }
752    // The highest priority bindings are at the start of the closure list, but
753    // the end of the enviroment vector
754    env.reverse();
755    Ok(env)
756}
757
758fn bind_args<'a>(
759    arg_list: Object,
760    args: &[Object<'a>],
761    vars: &mut Vec<&'a Cons>,
762    name: &str,
763    cx: &'a Context,
764) -> AnyResult<()> {
765    let (required, optional, rest) = parse_arg_list(arg_list)?;
766
767    let num_required_args = required.len() as u16;
768    let num_optional_args = optional.len() as u16;
769    let num_actual_args = args.len() as u16;
770    // Ensure the minimum number of arguments is present
771    ensure!(
772        num_actual_args >= num_required_args,
773        LispError::arg_cnt(name, num_required_args, num_actual_args, cx)
774    );
775
776    let mut arg_values = args.iter().copied();
777    let rest_offset = args.len().min(required.len() + optional.len());
778
779    for name in required {
780        let val = arg_values.next().unwrap();
781        vars.push(Cons::new(name, val, cx));
782    }
783
784    for name in optional {
785        let val = arg_values.next().unwrap_or_default();
786        vars.push(Cons::new(name, val, cx));
787    }
788
789    if let Some(rest_name) = rest {
790        let list = crate::fns::slice_into_list(&args[rest_offset..], None, cx);
791        vars.push(Cons::new(rest_name, list, cx));
792    } else {
793        // Ensure too many args were not provided
794        ensure!(
795            arg_values.next().is_none(),
796            LispError::arg_cnt(name, num_required_args + num_optional_args, num_actual_args, cx)
797        );
798    }
799    Ok(())
800}
801
802pub(crate) fn parse_arg_list(
803    bindings: Object,
804) -> AnyResult<(Vec<Symbol>, Vec<Symbol>, Option<Symbol>)> {
805    let mut required = Vec::new();
806    let mut optional = Vec::new();
807    let mut rest = None;
808    let mut arg_type = &mut required;
809    let mut iter = bindings.as_list()?;
810    while let Some(binding) = iter.next() {
811        let sym: Symbol = binding?.try_into()?;
812        match sym {
813            sym::AND_OPTIONAL => arg_type = &mut optional,
814            sym::AND_REST => {
815                if let Some(last) = iter.next() {
816                    rest = Some(last?.try_into()?);
817                    ensure!(iter.next().is_none(), "Found multiple arguments after &rest");
818                }
819            }
820            _ => {
821                arg_type.push(sym);
822            }
823        }
824    }
825    Ok((required, optional, rest))
826}
827
828#[cfg(test)]
829pub(crate) fn assert_lisp(compare: &str, expect: &str) {
830    let roots = &crate::core::gc::RootSet::default();
831    let cx = &mut Context::new(roots);
832    sym::init_symbols();
833    root!(env, new(Env), cx);
834    println!("Test String: {compare}");
835    let compare = {
836        let obj = crate::reader::read(compare, cx).unwrap().0;
837        root!(obj, cx);
838        rebind!(eval(obj, None, env, cx).unwrap())
839    };
840    let expect = crate::reader::read(expect, cx).unwrap().0;
841    assert_eq!(compare, expect);
842}
843
844#[cfg(test)]
845mod test {
846    use crate::core::{env::intern, gc::RootSet, object::IntoObject};
847    use rune_core::macros::list;
848
849    use super::*;
850
851    fn check_interpreter<T>(test_str: &str, expect: T, cx: &mut Context)
852    where
853        T: IntoObject,
854    {
855        sym::init_symbols();
856        root!(env, new(Env), cx);
857        println!("Test String: {test_str}");
858        let obj = crate::reader::read(test_str, cx).unwrap().0;
859        root!(obj, cx);
860        let compare = rebind!(eval(obj, None, env, cx).unwrap());
861        let expect: Object = expect.into_obj(cx).as_obj_copy();
862        assert_eq!(compare, expect);
863    }
864
865    fn check_error(test_str: &str, cx: &mut Context) {
866        root!(env, new(Env), cx);
867        println!("Test String: {test_str}");
868        let obj = crate::reader::read(test_str, cx).unwrap().0;
869        root!(obj, cx);
870        assert!(eval(obj, None, env, cx).is_err());
871    }
872
873    #[test]
874    fn basic() {
875        let roots = &RootSet::default();
876        let cx = &mut Context::new(roots);
877        check_interpreter("1", 1, cx);
878        check_interpreter("1.5", 1.5, cx);
879        check_interpreter("nil", false, cx);
880        check_interpreter("t", true, cx);
881        check_interpreter("\"foo\"", "foo", cx);
882        let list = list!(1, 2; cx);
883        root!(list, cx);
884        check_interpreter("'(1 2)", list, cx);
885    }
886
887    #[test]
888    fn variables() {
889        let roots = &RootSet::default();
890        let cx = &mut Context::new(roots);
891        check_interpreter("(let ())", false, cx);
892        check_interpreter("(let (x) x)", false, cx);
893        check_interpreter("(let ((x 1)) x)", 1, cx);
894        check_interpreter("(let ((x 1)))", false, cx);
895        check_interpreter("(let ((x 1) (y 2)) x y)", 2, cx);
896        check_interpreter("(let ((x 1)) (let ((x 3)) x))", 3, cx);
897        check_interpreter("(let ((x 1)) (let ((y 3)) x))", 1, cx);
898        check_interpreter("(let ((x 1)) (setq x 2) x)", 2, cx);
899        check_interpreter("(let* ())", false, cx);
900        check_interpreter("(let* ((x 1) (y x)) y)", 1, cx);
901    }
902
903    #[test]
904    fn dyn_variables() {
905        let roots = &RootSet::default();
906        let cx = &mut Context::new(roots);
907        check_interpreter("(progn (defvar dyn_test1 1) dyn_test1)", 1, cx);
908        check_interpreter("(progn (defvar dyn_test2 1) (let ((dyn_test2 3)) dyn_test2))", 3, cx);
909        check_interpreter("(progn (defvar dyn_test3 1) (let ((dyn_test3 3))) dyn_test3)", 1, cx);
910        check_interpreter("(let ((dyn_test4 7)) (defvar dyn_test4 3) dyn_test4)", 7, cx);
911        check_interpreter(
912            "(progn (defvar dyn_test5 1) (let (bar) (let ((dyn_test5 3)) (setq bar dyn_test5)) bar))",
913            3,
914            cx,
915        );
916        // Special but unbound
917        check_interpreter(
918            "(progn (defvar dyn_test6 1) (makunbound 'dyn_test6) (let ((fn #'(lambda () (defvar dyn_test6 3))) (dyn_test6 7)) (funcall fn)) dyn_test6)",
919            3,
920            cx,
921        );
922        check_interpreter(
923            "(progn (defvar dyn_test7 1) (makunbound 'dyn_test7) (let ((dyn_test7 7)) dyn_test7))",
924            7,
925            cx,
926        );
927        check_interpreter("(eq (make-symbol \"bar\") 'bar)", false, cx);
928        check_interpreter(
929            "(let ((x (make-symbol \"x\"))) (put x 'p t) (garbage-collect) (get x 'p))",
930            true,
931            cx,
932        );
933    }
934
935    #[test]
936    fn conditionals() {
937        let roots = &RootSet::default();
938        let cx = &mut Context::new(roots);
939        check_interpreter("(if nil 1)", false, cx);
940        check_interpreter("(if t 1)", 1, cx);
941        check_interpreter("(if nil 1 2)", 2, cx);
942        check_interpreter("(if t 1 2)", 1, cx);
943        check_interpreter("(if nil 1 2 3)", 3, cx);
944        check_interpreter("(and)", true, cx);
945        check_interpreter("(and 1)", 1, cx);
946        check_interpreter("(and 1 2)", 2, cx);
947        check_interpreter("(and 1 nil)", false, cx);
948        check_interpreter("(and nil 1)", false, cx);
949        check_interpreter("(or)", false, cx);
950        check_interpreter("(or nil)", false, cx);
951        check_interpreter("(or nil 1)", 1, cx);
952        check_interpreter("(or 1 2)", 1, cx);
953        check_interpreter("(cond)", false, cx);
954        check_interpreter("(cond nil)", false, cx);
955        check_interpreter("(cond (1))", 1, cx);
956        check_interpreter("(cond (1 2))", 2, cx);
957        check_interpreter("(cond (nil 1) (2 3))", 3, cx);
958        check_interpreter("(cond (nil 1) (2 3) (4 5))", 3, cx);
959    }
960
961    #[test]
962    fn test_loops() {
963        let roots = &RootSet::default();
964        let cx = &mut Context::new(roots);
965        check_interpreter(
966            "(let ((i 3) (x 0)) (while (> i 0) (setq x (+ x i) i (1- i) )) x)",
967            6,
968            cx,
969        );
970        check_interpreter(
971            "(let ((i 3) (x 0)) (while (progn (setq x (1- x)) (> i 0)) (setq x (+ x i) i (1- i) )) x)",
972            2,
973            cx,
974        );
975    }
976
977    #[test]
978    fn special_forms() {
979        let roots = &RootSet::default();
980        let cx = &mut Context::new(roots);
981        check_interpreter("(prog1 1 2 3)", 1, cx);
982        check_interpreter("(prog2 1 2 3)", 2, cx);
983        check_interpreter("(progn 1 2 3 4)", 4, cx);
984        check_interpreter("(function 1)", 1, cx);
985        check_interpreter("(quote 1)", 1, cx);
986        check_interpreter("(if 1 2 3)", 2, cx);
987        check_interpreter("(if nil 2 3)", 3, cx);
988        check_interpreter("(if (and 1 nil) 2 3)", 3, cx);
989    }
990
991    #[test]
992    fn test_functions() {
993        let roots = &RootSet::default();
994        let cx = &mut Context::new(roots);
995        let list = list![sym::CLOSURE, list![true; cx]; cx];
996        root!(list, cx);
997        check_interpreter("(function (lambda))", list, cx);
998        let x = intern("x", cx);
999        let list = list![sym::CLOSURE, list![true; cx], list![x; cx], x; cx];
1000        root!(list, cx);
1001        check_interpreter("(function (lambda (x) x))", list, cx);
1002        // TODO: fix this duplicate intern
1003        let x = intern("x", cx);
1004        let y = intern("y", cx);
1005        let list: Object =
1006            list![sym::CLOSURE, list![Cons::new(y, 1, cx), true; cx], list![x; cx], x; cx];
1007        root!(list, cx);
1008        check_interpreter("(let ((y 1)) (function (lambda (x) x)))", list, cx);
1009
1010        let list = list!(5, false; cx);
1011        root!(list, cx);
1012        check_interpreter(
1013            "(let ((x #'(lambda (x &optional y &rest z) (cons x (cons y z))))) (funcall x 5))",
1014            list,
1015            cx,
1016        );
1017        let list = list!(5, 7; cx);
1018        root!(list, cx);
1019        check_interpreter(
1020            "(let ((x #'(lambda (x &optional y &rest z) (cons x (cons y z))))) (funcall x 5 7))",
1021            list,
1022            cx,
1023        );
1024        let list = list!(5, 7, 11; cx);
1025        root!(list, cx);
1026        check_interpreter(
1027            "(let ((x #'(lambda (x &optional y &rest z) (cons x (cons y z))))) (funcall x 5 7 11))",
1028            list,
1029            cx,
1030        );
1031        check_interpreter(
1032            "(let (z) (setq z (let ((x 5)) (let ((x 3)) (function (lambda () x))))) (funcall z))",
1033            3,
1034            cx,
1035        );
1036    }
1037
1038    #[test]
1039    fn test_call() {
1040        let roots = &RootSet::default();
1041        let cx = &mut Context::new(roots);
1042        check_interpreter("(let ((x #'(lambda (x) x))) (funcall x 5))", 5, cx);
1043        check_interpreter("(let ((x #'(lambda () 3))) (funcall x))", 3, cx);
1044        check_interpreter(
1045            "(progn (defvar foo 1) (let ((x #'(lambda () foo)) (foo 5)) (funcall x)))",
1046            5,
1047            cx,
1048        );
1049        check_interpreter(
1050            "(progn (defalias 'int-test-call #'(lambda (x) (+ x 3)))  (int-test-call 7))",
1051            10,
1052            cx,
1053        );
1054        // Test closures
1055        check_interpreter("(let* ((y 7)(x #'(lambda () y))) (funcall x))", 7, cx);
1056        check_interpreter("(let* ((y 7)(x #'(lambda (x) (+ x y)))) (funcall x 3))", 10, cx);
1057        // Test that closures capture their environments
1058        check_interpreter(
1059            "(progn (setq func (let ((x 3)) #'(lambda (y) (+ y x)))) (funcall func 5))",
1060            8,
1061            cx,
1062        );
1063        // Test multiple closures
1064        check_interpreter(
1065            "(progn (setq funcs (let ((x 3)) (cons #'(lambda (y) (+ y x)) #'(lambda (y) (- y x))))) (* (funcall (car funcs) 5) (funcall (cdr funcs) 1)))",
1066            -16,
1067            cx,
1068        );
1069        // Test that closures close over variables
1070        check_interpreter(
1071            "(progn (setq funcs (let ((x 3)) (cons #'(lambda (y) (setq x y)) #'(lambda (y) (+ y x))))) (funcall (car funcs) 5) (funcall (cdr funcs) 4))",
1072            9,
1073            cx,
1074        );
1075        // Test that closures in global function close over values and not
1076        // variables
1077        check_interpreter(
1078            "(progn (setq func (let ((x 3)) (defalias 'int-test-no-cap #'(lambda (y) (+ y x))) #'(lambda (y) (setq x y)))) (funcall func 4) (int-test-no-cap 5))",
1079            8,
1080            cx,
1081        );
1082
1083        // takes 1 arg
1084        check_error("(1+)", cx);
1085        check_error("(/)", cx);
1086        check_error("(1+ 1 2)", cx);
1087    }
1088
1089    #[test]
1090    fn test_condition_case() {
1091        let roots = &RootSet::default();
1092        let cx = &mut Context::new(roots);
1093        check_interpreter("(condition-case nil nil)", false, cx);
1094        check_interpreter("(condition-case nil 1)", 1, cx);
1095        check_interpreter("(condition-case nil (if) (error 7))", 7, cx);
1096        check_interpreter("(condition-case nil (if) (error 7 9 11))", 11, cx);
1097        check_interpreter("(condition-case nil (if) (error . 7))", false, cx);
1098        check_interpreter("(condition-case nil (if) ((debug error) 7))", 7, cx);
1099        // Ensure that errors don't get garbage collected
1100        check_interpreter(
1101            "(condition-case e (if t) (error (progn (garbage-collect) (nth 2 e))))",
1102            2,
1103            cx,
1104        );
1105        check_error("(condition-case nil (if))", cx);
1106        check_error("(condition-case nil (if) nil)", cx);
1107        check_error("(condition-case nil (if) 5 (error 7))", cx);
1108    }
1109
1110    #[test]
1111    fn test_throw_catch() {
1112        let roots = &RootSet::default();
1113        let cx = &mut Context::new(roots);
1114        check_interpreter("(catch nil)", false, cx);
1115        check_interpreter("(catch nil nil)", false, cx);
1116        check_interpreter("(catch 1 (throw 1 2))", 2, cx);
1117        check_interpreter("(catch 1 (throw 1 2) 3)", 2, cx);
1118        check_interpreter("(catch 1 5 (throw 1 2) 3)", 2, cx);
1119        check_interpreter("(catch 1 (throw 1 2) (if))", 2, cx);
1120        check_interpreter("(condition-case nil (throw 1 2) (error 3))", 3, cx);
1121        check_interpreter("(catch 1 (condition-case nil (throw 1 2) (error 3)))", 2, cx);
1122        check_interpreter("(catch 1 (catch 2 (throw 1 3)))", 3, cx);
1123        check_error("(throw 1 2)", cx);
1124        check_error("(catch 2 (throw 3 4))", cx);
1125    }
1126}
rune/interpreter.rs

rune/
interpreter.rs
