From ae531a2245e83d44ce58ba6c588713265984dbbf Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Sat, 27 Aug 2022 22:58:39 +0300 Subject: feat(tvix/eval): implement capture of self-recursive upvalues With this change, it becomes possible for functions to call themselves as they are being defined in local bindings. Change-Id: Ib46a39ba17b1452b5673d96fa729d633d237241a Reviewed-on: https://cl.tvl.fyi/c/depot/+/6314 Tested-by: BuildkiteCI Reviewed-by: sterni --- tvix/eval/src/compiler/mod.rs | 12 ++++++++---- tvix/eval/src/tests/tvix_tests/eval-okay-closure-self.exp | 1 + tvix/eval/src/tests/tvix_tests/eval-okay-closure-self.nix | 4 ++++ tvix/eval/src/vm.rs | 12 +++++++++--- 4 files changed, 22 insertions(+), 7 deletions(-) create mode 100644 tvix/eval/src/tests/tvix_tests/eval-okay-closure-self.exp create mode 100644 tvix/eval/src/tests/tvix_tests/eval-okay-closure-self.nix diff --git a/tvix/eval/src/compiler/mod.rs b/tvix/eval/src/compiler/mod.rs index 520eb3bd64..6ba470a7af 100644 --- a/tvix/eval/src/compiler/mod.rs +++ b/tvix/eval/src/compiler/mod.rs @@ -709,9 +709,9 @@ impl Compiler { self.chunk().push_op(OpCode::OpResolveWith) } - LocalPosition::Recursive(_) => todo!("self-recursive upvalue"), - LocalPosition::Known(idx) => self.chunk().push_op(OpCode::OpGetLocal(idx)), + + LocalPosition::Recursive(_) => panic!("TODO: unclear if this can happen"), }; } @@ -981,10 +981,14 @@ impl Compiler { // Determine whether the upvalue is a local in the enclosing context. match self.contexts[ctx_idx - 1].scope.resolve_local(name) { - LocalPosition::Known(idx) => { + // recursive upvalues are dealt with the same way as + // standard known ones, as thunks and closures are + // guaranteed to be placed on the stack (i.e. in the right + // position) *during* their runtime construction + LocalPosition::Known(idx) | LocalPosition::Recursive(idx) => { return Some(self.add_upvalue(ctx_idx, Upvalue::Stack(idx))) } - LocalPosition::Recursive(_) => todo!("self-recursive upvalue"), + LocalPosition::Unknown => { /* continue below */ } }; diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-closure-self.exp b/tvix/eval/src/tests/tvix_tests/eval-okay-closure-self.exp new file mode 100644 index 0000000000..be54b4b4e3 --- /dev/null +++ b/tvix/eval/src/tests/tvix_tests/eval-okay-closure-self.exp @@ -0,0 +1 @@ +"done" diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-closure-self.nix b/tvix/eval/src/tests/tvix_tests/eval-okay-closure-self.nix new file mode 100644 index 0000000000..bda364f429 --- /dev/null +++ b/tvix/eval/src/tests/tvix_tests/eval-okay-closure-self.nix @@ -0,0 +1,4 @@ +let + # self-recursive function should be able to close over itself + f = n: if n <= 0 then "done" else f (n - 1); +in f 10 diff --git a/tvix/eval/src/vm.rs b/tvix/eval/src/vm.rs index 527f58ddc8..5b6536e986 100644 --- a/tvix/eval/src/vm.rs +++ b/tvix/eval/src/vm.rs @@ -359,7 +359,15 @@ impl VM { } OpCode::OpClosure(idx) => { - let closure = self.chunk().constant(idx).clone().to_closure()?; + let value = self.chunk().constant(idx).clone(); + self.push(value.clone()); + + // This refers to the same Rc, and from this point + // on internally mutates the closure objects + // upvalues. The closure is already in its stack + // slot, which means that it can capture itself as + // an upvalue for self-recursion. + let closure = value.to_closure()?; debug_assert!( closure.upvalue_count() > 0, @@ -387,8 +395,6 @@ impl VM { _ => panic!("compiler error: missing closure operand"), } } - - self.push(Value::Closure(closure)); } // Data-carrying operands should never be executed, -- cgit 1.4.1