feat(tvix/eval): implement capture of self-recursive upvalues r/4653

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 <sternenseemann@systemli.org>

4 files changed, 22 insertions, 7 deletions

diff --git a/tvix/eval/src/compiler/mod.rs b/tvix/eval/src/compiler/mod.rs
index 520eb3bd6404..6ba470a7af9f 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 000000000000..be54b4b4e39e
--- /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 000000000000..bda364f42992
--- /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 527f58ddc8d6..5b6536e98664 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,