diff --git a/crates/calc/src/eval.rs b/crates/calc/src/eval.rs --- a/crates/calc/src/eval.rs +++ b/crates/calc/src/eval.rs @@ -53,6 +53,28 @@ pub struct Lambda { pub env: Vec<(String, Ev)>, } +/// What the tail of a LAMBDA body came to. +enum Tail { + Done(Ev), + /// A call to make in place of the current one, its arguments evaluated. + Call(Arc, Vec<(String, Ev)>), +} + +/// A tail call can pass a closure that captures the previous one, thousands deep. Releasing the +/// chain is a loop, not a recursion, so it cannot overflow the native stack. +impl Drop for Lambda { + fn drop(&mut self) { + let mut pending = std::mem::take(&mut self.env); + while let Some((_, ev)) = pending.pop() { + if let Ev::L(l) = ev + && let Ok(mut inner) = Arc::try_unwrap(l) + { + pending.append(&mut inner.env); + } + } + } +} + #[derive(Clone, Debug)] pub enum Ev { V(Value), @@ -75,6 +97,11 @@ fn err(e: CellError) -> Ev { /// calls in progress, so it still runs. const MAX_LAMBDA_CALLS: usize = 140; +/// Tail calls one LAMBDA call may chain. They run in a loop on one native frame, so this only keeps +/// an endless tail recursion finite. Excel computes a tail countdown to 5,459 and answers `#NUM!` +/// for 5,460, which is 5,460 invocations in the chain. +const MAX_TAIL_CALLS: usize = 5460; + /// Native stack, in bytes, that one formula's evaluation may use below its first `eval`. Past it, /// `eval` answers `#NUM!`. It guards the stack and leaves 128 KiB of a 1 MiB thread for the frames /// above the formula. A cell that another cell's formula computes on demand shares the budget of the diff --git a/crates/calc/src/eval/call.rs b/crates/calc/src/eval/call.rs --- a/crates/calc/src/eval/call.rs +++ b/crates/calc/src/eval/call.rs @@ -4,6 +4,17 @@ use super::special::{ev_shape, resized_sum_range, resizes_sum_range}; use super::*; impl<'h> Evaluator<'h> { + /// `IF` with an array condition: element-wise. + pub(super) fn if_elementwise(&mut self, arr: &Array, args: &[Expr]) -> Ev { + let t = self.arg_val(args, 1).unwrap_or(Value::Bool(true)); + let f = if args.len() > 2 { self.arg_val(args, 2).unwrap_or(Value::Bool(false)) } else { Value::Bool(false) }; + Ev::V(zip3(arr, &t, &f, |c, t, f| match c.to_bool() { + Ok(true) => t.clone(), + Ok(false) => f.clone(), + Err(e) => Value::Error(e), + })) + } + pub(super) fn call(&mut self, name: &str, args: &[Expr]) -> Ev { match name { "IF" => { @@ -12,14 +23,7 @@ impl<'h> Evaluator<'h> { } let c = self.arg_val(args, 0).unwrap_or_default(); if let Value::Array(arr) = &c { - // Array condition: element-wise. - let t = self.arg_val(args, 1).unwrap_or(Value::Bool(true)); - let f = if args.len() > 2 { self.arg_val(args, 2).unwrap_or(Value::Bool(false)) } else { Value::Bool(false) }; - return Ev::V(zip3(arr, &t, &f, |c, t, f| match c.to_bool() { - Ok(true) => t.clone(), - Ok(false) => f.clone(), - Err(e) => Value::Error(e), - })); + return self.if_elementwise(arr, args); } match c.to_bool() { Ok(true) => match args.get(1) { diff --git a/crates/calc/src/eval/lambda.rs b/crates/calc/src/eval/lambda.rs --- a/crates/calc/src/eval/lambda.rs +++ b/crates/calc/src/eval/lambda.rs @@ -1,15 +1,24 @@ use super::array::{broadcast_len, single}; +use super::special::is_special; use super::*; impl<'h> Evaluator<'h> { pub fn apply_lambda(&mut self, l: &Lambda, args: &[Expr]) -> Ev { + match self.bind_args(l, args) { + Ok(bound) => self.call_lambda_values(l, bound), + Err(e) => e, + } + } + + /// The arguments of a call to `l`, evaluated in the current scope. + fn bind_args(&mut self, l: &Lambda, args: &[Expr]) -> Result, Ev> { // Too many or too few argument positions is #VALUE!. An explicitly empty position, as in // `(1,)`, is `Expr::Missing` and still counts as a position (it binds as omitted). `f()` // parses to no arguments, which for a one-parameter lambda can also be read as one empty // position, so that call still binds the parameter as omitted. let positions_ok = args.len() == l.params.len() || (args.is_empty() && l.params.len() == 1); if !positions_ok { - return err(CellError::Value); + return Err(err(CellError::Value)); } let mut bound = Vec::with_capacity(l.params.len()); for (i, p) in l.params.iter().enumerate() { @@ -19,7 +28,56 @@ impl<'h> Evaluator<'h> { }; bound.push((p.clone(), v)); } - self.call_lambda_values(l, bound) + Ok(bound) + } + + /// Follows `e` through the positions whose value is the value of a LAMBDA call (`IF` branches, + /// parentheses), and returns the call with its arguments evaluated instead of making it, so + /// that `call_lambda_values` can loop. Anything else is evaluated here. + fn tail_step(&mut self, e: &Expr) -> Tail { + match e { + Expr::Paren(x) => self.tail_step(x), + Expr::Call(name, args) if name == "IF" && (2..=3).contains(&args.len()) => { + let c = self.arg_val(args, 0).unwrap_or_default(); + if let Value::Array(arr) = &c { + return Tail::Done(self.if_elementwise(arr, args)); + } + match c.to_bool() { + Ok(true) => self.tail_step_branch(args.get(1)), + Ok(false) => match args.get(2) { + Some(_) => self.tail_step_branch(args.get(2)), + None => Tail::Done(Ev::V(Value::Bool(false))), + }, + Err(x) => Tail::Done(err(x)), + } + } + Expr::Call(name, args) if gridcraft_functions::lookup(name).is_none() && !is_special(name) => match self.name(name) { + Ev::L(l) => self.tail_call(l, args), + Ev::V(Value::Error(x)) => Tail::Done(err(x)), + _ => Tail::Done(err(CellError::Name)), + }, + Expr::Invoke(callee, args) => match self.eval(callee) { + Ev::L(l) => self.tail_call(l, args), + Ev::V(Value::Error(x)) => Tail::Done(err(x)), + _ => Tail::Done(err(CellError::Value)), + }, + _ => Tail::Done(self.eval(e)), + } + } + + /// An `IF` branch; an omitted one (`IF(c,,1)`) is 0. + fn tail_step_branch(&mut self, branch: Option<&Expr>) -> Tail { + match branch { + Some(Expr::Missing) | None => Tail::Done(Ev::V(Value::Number(0.0))), + Some(b) => self.tail_step(b), + } + } + + fn tail_call(&mut self, l: Arc, args: &[Expr]) -> Tail { + match self.bind_args(&l, args) { + Ok(bound) => Tail::Call(l, bound), + Err(e) => Tail::Done(e), + } } pub(super) fn call_lambda_values(&mut self, l: &Lambda, bound: Vec<(String, Ev)>) -> Ev { @@ -36,7 +94,29 @@ impl<'h> Evaluator<'h> { self.calls += 1; let saved = std::mem::replace(&mut self.env, l.env.clone()); self.env.extend(bound); - let r = self.eval(&l.body); + // A call in tail position replaces this one instead of nesting under it, so a tail recursion + // uses no more native stack at 5,000 deep than at 5. Each link still spends fuel. + let mut tails = 0; + let mut step = self.tail_step(&l.body); + let r = loop { + match step { + Tail::Done(v) => break v, + Tail::Call(next, bound) => { + tails += 1; + if tails >= MAX_TAIL_CALLS { + break err(CellError::Num); + } + self.fuel = match self.fuel.checked_sub(1) { + Some(f) => f, + None => break err(CellError::Calc), + }; + self.env.clear(); + self.env.extend(next.env.iter().cloned()); + self.env.extend(bound); + step = self.tail_step(&next.body); + } + } + }; self.env = saved; self.calls -= 1; r diff --git a/crates/calc/src/eval/special.rs b/crates/calc/src/eval/special.rs --- a/crates/calc/src/eval/special.rs +++ b/crates/calc/src/eval/special.rs @@ -84,7 +84,7 @@ pub fn precedents(wb: &Workbook, sheet: usize, e: &Expr) -> (Vec, bool) { (out, dynamic) } -fn is_special(n: &str) -> bool { +pub(super) fn is_special(n: &str) -> bool { matches!( n, "IF" | "IFS" diff --git a/crates/calc/src/tests.rs b/crates/calc/src/tests.rs --- a/crates/calc/src/tests.rs +++ b/crates/calc/src/tests.rs @@ -1097,17 +1097,67 @@ fn a_recursive_lambda_stops_at_the_same_call_on_any_stack_size() { comment: String::new(), hidden: false, }); - // F(F,n) has n + 1 calls in progress at its deepest; W adds one more call per step. + // W's call to `f` is a tail call, so a wrapped call level costs one call in progress, not two. A tail call reuses its frame, so the tail chain is bounded by `MAX_TAIL_CALLS`, as in Excel + // (5,459 ok, 5,460 #NUM!). F(F,n) otherwise has n + 1 calls in progress at its deepest; W adds + // one more call per step. let tail = |n: u32| format!("=LET(F,LAMBDA(me,n,IF(n=0,0,me(me,n-1))),F(F,{n}))"); let wrapped = |n: u32| format!("=LET(W,LAMBDA(f,k,f(f,k)),F,LAMBDA(me,n,IF(n<=0,0,1+W(me,n-1))),F(F,{n}))"); - [tail(139), tail(140), wrapped(69), wrapped(70), "=CNT(131)".to_string()].map(|f| crate::evaluate(&wb, 0, c("B1"), &f)) + [tail(5459), tail(5460), wrapped(69), wrapped(70), "=CNT(131)".to_string()].map(|f| crate::evaluate(&wb, 0, c("B1"), &f)) }) .expect("spawn") .join() .expect("recursion must not overflow the stack") }; let small = run(1 << 20); - assert_eq!(small, [Value::Number(0.0), Value::Error(CellError::Num), Value::Number(69.0), Value::Error(CellError::Num), Value::Number(131.0)]); + assert_eq!(small, [Value::Number(0.0), Value::Error(CellError::Num), Value::Number(69.0), Value::Number(70.0), Value::Number(131.0)]); + assert_eq!(run(64 << 20), small); +} + +#[test] +fn a_tail_recursive_lambda_reaches_excels_depth_on_a_small_stack() { + // Excel (measured): a tail countdown is 0 at 5,000 and 5,459 and #NUM! at 5,460 and 10,000. + let run = |stack: usize| { + std::thread::Builder::new() + .stack_size(stack) + .spawn(|| { + let mut wb = Workbook::new(); + wb.names.push(gridcraft_model::DefinedName { + name: "TAILN".into(), + scope: None, + formula: "LAMBDA(n,IF(n=0,0,TAILN(n-1)))".into(), + comment: String::new(), + hidden: false, + }); + let tail = |n: u32| format!("=LET(F,LAMBDA(me,n,IF(n=0,0,me(me,n-1))),F(F,{n}))"); + // The same chain through parentheses and an applied lambda, and one that returns the base case's value. + let paren = "=LET(F,LAMBDA(me,n,IF(n=0,7,(me(me,n-1)))),F(F,5000))".to_string(); + let invoke = "=LET(F,LAMBDA(me,n,IF(n=0,7,LAMBDA(a,b,me(me,a))(n-1,0))),F(F,2000))".to_string(); + let endless = "=LET(f,LAMBDA(g,x,g(g,x)),f(f,1))".to_string(); + // Each call passes a closure that captures the last, 5,000 deep: releasing them must not recurse. + let closures = "=LET(F,LAMBDA(me,n,acc,IF(n=0,0,me(me,n-1,LAMBDA(x,acc)))),F(F,5000,0))".to_string(); + [tail(5000), tail(5459), tail(5460), tail(10000), paren, invoke, endless, "=TAILN(5000)".to_string(), closures] + .map(|f| crate::evaluate(&wb, 0, c("B1"), &f)) + }) + .expect("spawn") + .join() + .expect("tail recursion must not overflow the stack") + }; + let num = Value::Error(CellError::Num); + let small = run(1 << 20); + assert_eq!( + small, + [ + Value::Number(0.0), + Value::Number(0.0), + num.clone(), + num.clone(), + Value::Number(7.0), + Value::Number(7.0), + num, + Value::Number(0.0), + Value::Number(0.0) + ] + ); assert_eq!(run(64 << 20), small); }