fix(tvix): don't call function eagerly in genList, map & mapAttrs r/6207

mapAttrs, map and genList call Nix functions provided by the caller and
store the result of applying them in a Nix data structure that does not
force all of its contents when forced itself. This means that when such
a builtin application is forced, the Nix function calls performed by the
builtin should not be forced: They may be forced later, but it is also
possible that they will never be forced, e.g. in

    builtins.length (builtins.map (builtins.add 2) [ 1 2 3 ])

it is not necessary to compute a single application of builtins.add.

Since request_call_with immediately performs the function call
requested, Tvix would compute function applications unnecessarily before
this change. Because this was not followed by a request_force, the
impact of this was relatively low in Nix code (most functions return a
new thunk after being applied), but it was enough to cause a lot of
bogus builtins.trace applications when evaluating anything from
`lib.modules`. The newly added test includes many cases where Tvix
previously incorrectly applied a builtin, breaking a working expression.

To fix this we add a new helper to construct a Thunk performing a
function application at runtime from a function and argument given as
`Value`s. This mimics the compiler's compile_apply(), but does itself
not require a compiler, since the necessary Lambda can be constructed
independently.

I also looked into other builtins that call a Nix function to verify
that they don't exhibit such a problem:

- Many builtins immediately use the resulting value in a way that makes
  it necessary to compute all the function calls they do as soon as
  the outer builtin application is forced:

  * all
  * any
  * filter
  * groupBy
  * partition

- concatMap needs to (shallowly) force the returned list for
  concatenation.

- foldl' is strict in the application of `op` (I added a comment that
  makes this explicit).

- genericClosure needs to (shallowly) force the resulting list and some
  keys of the attribute sets inside.

Resolves b/272.

Change-Id: I1fa53f744bcffc035da84c1f97ed25d146830446
Reviewed-on: https://cl.tvl.fyi/c/depot/+/8651
Autosubmit: sterni <sternenseemann@systemli.org>
Tested-by: BuildkiteCI
Reviewed-by: tazjin <tazjin@tvl.su>

1 files changed, 31 insertions, 0 deletions

diff --git a/tvix/eval/src/value/thunk.rs b/tvix/eval/src/value/thunk.rs
index 1acb50a94b21..9c048d40b499 100644
--- a/tvix/eval/src/value/thunk.rs
+++ b/tvix/eval/src/value/thunk.rs
@@ -27,6 +27,7 @@ use std::{
 
 use crate::{
     errors::ErrorKind,
+    opcode::OpCode,
     spans::LightSpan,
     upvalues::Upvalues,
     value::Closure,
@@ -124,6 +125,36 @@ impl Thunk {
         )))))
     }
 
+    /// Helper function to create a [`Thunk`] that calls a function given as the
+    /// [`Value`] `callee` with the argument `arg` when it is forced. This is
+    /// particularly useful in builtin implementations if the result of calling
+    /// a function does not need to be forced immediately, because e.g. it is
+    /// stored in an attribute set.
+    pub fn new_suspended_call(callee: Value, arg: Value, light_span: LightSpan) -> Self {
+        let mut lambda = Lambda::default();
+        let span = light_span.span();
+
+        let arg_idx = lambda.chunk().push_constant(arg);
+        let f_idx = lambda.chunk().push_constant(callee);
+
+        // This is basically a recreation of compile_apply():
+        // We need to push the argument onto the stack and then the function.
+        // The function (not the argument) needs to be forced before calling.
+        lambda.chunk.push_op(OpCode::OpConstant(arg_idx), span);
+        lambda.chunk().push_op(OpCode::OpConstant(f_idx), span);
+        lambda.chunk.push_op(OpCode::OpForce, span);
+        lambda.chunk.push_op(OpCode::OpCall, span);
+
+        // Inform the VM that the chunk has ended
+        lambda.chunk.push_op(OpCode::OpReturn, span);
+
+        Thunk(Rc::new(RefCell::new(ThunkRepr::Suspended {
+            upvalues: Rc::new(Upvalues::with_capacity(0)),
+            lambda: Rc::new(lambda),
+            light_span,
+        })))
+    }
+
     fn prepare_blackhole(&self, forced_at: LightSpan) -> ThunkRepr {
         match &*self.0.borrow() {
             ThunkRepr::Suspended {