Recursion with max depth

2 files changed, 29 insertions, 8 deletions

diff --git a/src/model/eval.rs b/src/model/eval.rs
index ce1739ed..54007e76 100644
--- a/src/model/eval.rs
+++ b/src/model/eval.rs
@@ -20,6 +20,9 @@ use crate::syntax::{ast, Source, SourceId, Span, Spanned, SyntaxKind, SyntaxNode
 use crate::util::{format_eco, EcoString, PathExt};
 use crate::World;
 
+const MAX_ITERATIONS: usize = 10_000;
+const MAX_CALL_DEPTH: usize = 256;
+
 /// Evaluate a source file and return the resulting module.
 #[comemo::memoize]
 pub fn eval(
@@ -41,7 +44,7 @@ pub fn eval(
     // Evaluate the module.
     let route = unsafe { Route::insert(route, id) };
     let scopes = Scopes::new(Some(&library.scope));
-    let mut vm = Vm::new(world, route.track(), id, scopes);
+    let mut vm = Vm::new(world, route.track(), id, scopes, 0);
     let result = source.ast()?.eval(&mut vm);
 
     // Handle control flow.
@@ -70,6 +73,8 @@ pub struct Vm<'a> {
     pub(super) flow: Option<Flow>,
     /// The stack of scopes.
     pub(super) scopes: Scopes<'a>,
+    /// The current call depth.
+    pub(super) depth: usize,
 }
 
 impl<'a> Vm<'a> {
@@ -79,6 +84,7 @@ impl<'a> Vm<'a> {
         route: Tracked<'a, Route>,
         location: SourceId,
         scopes: Scopes<'a>,
+        depth: usize,
     ) -> Self {
         Self {
             world,
@@ -87,6 +93,7 @@ impl<'a> Vm<'a> {
             location,
             flow: None,
             scopes,
+            depth,
         }
     }
 
@@ -787,6 +794,10 @@ impl Eval for ast::FuncCall {
     type Output = Value;
 
     fn eval(&self, vm: &mut Vm) -> SourceResult<Self::Output> {
+        if vm.depth >= MAX_CALL_DEPTH {
+            bail!(self.span(), "maximum function call depth exceeded");
+        }
+
         let callee = self.callee().eval(vm)?;
         let args = self.args().eval(vm)?;
 
@@ -994,8 +1005,6 @@ impl Eval for ast::WhileLoop {
     type Output = Value;
 
     fn eval(&self, vm: &mut Vm) -> SourceResult<Self::Output> {
-        const MAX_ITERS: usize = 10_000;
-
         let flow = vm.flow.take();
         let mut output = Value::None;
         let mut i = 0;
@@ -1009,7 +1018,7 @@ impl Eval for ast::WhileLoop {
                 && !can_diverge(body.as_untyped())
             {
                 bail!(condition.span(), "condition is always true");
-            } else if i >= MAX_ITERS {
+            } else if i >= MAX_ITERATIONS {
                 bail!(self.span(), "loop seems to be infinite");
             }
 
diff --git a/src/model/func.rs b/src/model/func.rs
index f04b864e..3fb8f4d4 100644
--- a/src/model/func.rs
+++ b/src/model/func.rs
@@ -96,7 +96,7 @@ impl Func {
     pub fn call(&self, vm: &Vm, mut args: Args) -> SourceResult<Value> {
         let value = match self.0.as_ref() {
             Repr::Native(native) => (native.func)(vm, &mut args)?,
-            Repr::Closure(closure) => closure.call(vm, &mut args)?,
+            Repr::Closure(closure) => closure.call(vm, self, &mut args)?,
             Repr::With(wrapped, applied) => {
                 args.items.splice(..0, applied.items.iter().cloned());
                 return wrapped.call(vm, args);
@@ -115,7 +115,7 @@ impl Func {
         let route = Route::default();
         let id = SourceId::detached();
         let scopes = Scopes::new(None);
-        let vm = Vm::new(world, route.track(), id, scopes);
+        let vm = Vm::new(world, route.track(), id, scopes, 0);
         self.call(&vm, args)
     }
 
@@ -274,12 +274,17 @@ pub(super) struct Closure {
 
 impl Closure {
     /// Call the function in the context with the arguments.
-    fn call(&self, vm: &Vm, args: &mut Args) -> SourceResult<Value> {
+    fn call(&self, vm: &Vm, this: &Func, args: &mut Args) -> SourceResult<Value> {
         // Don't leak the scopes from the call site. Instead, we use the scope
         // of captured variables we collected earlier.
         let mut scopes = Scopes::new(None);
         scopes.top = self.captured.clone();
 
+        // Provide the closure itself for recursive calls.
+        if let Some(name) = &self.name {
+            scopes.top.define(name.clone(), Value::Func(this.clone()));
+        }
+
         // Parse the arguments according to the parameter list.
         for (param, default) in &self.params {
             scopes.top.define(
@@ -304,7 +309,7 @@ impl Closure {
         let route = if detached { fresh.track() } else { vm.route };
 
         // Evaluate the body.
-        let mut sub = Vm::new(vm.world, route, self.location, scopes);
+        let mut sub = Vm::new(vm.world, route, self.location, scopes, vm.depth + 1);
         let result = self.body.eval(&mut sub);
 
         // Handle control flow.
@@ -378,6 +383,10 @@ impl<'a> CapturesVisitor<'a> {
                     }
                 }
 
+                if let Some(name) = expr.name() {
+                    self.bind(name);
+                }
+
                 for param in expr.params() {
                     match param {
                         ast::Param::Pos(ident) => self.bind(ident),
@@ -456,6 +465,7 @@ mod tests {
     #[track_caller]
     fn test(text: &str, result: &[&str]) {
         let mut scopes = Scopes::new(None);
+        scopes.top.define("f", 0);
         scopes.top.define("x", 0);
         scopes.top.define("y", 0);
         scopes.top.define("z", 0);
@@ -477,6 +487,8 @@ mod tests {
         test("#let x = x", &["x"]);
         test("#let x; {x + y}", &["y"]);
         test("#let f(x, y) = x + y", &[]);
+        test("#let f(x, y) = f", &[]);
+        test("#let f = (x, y) => f", &["f"]);
 
         // Closure with different kinds of params.
         test("{(x, y) => x + z}", &["z"]);