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>

2 files changed, 32 insertions, 0 deletions

diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-builtins-thunked-function-calls.exp b/tvix/eval/src/tests/tvix_tests/eval-okay-builtins-thunked-function-calls.exp
new file mode 100644
index 000000000000..3d4204d5a83e
--- /dev/null
+++ b/tvix/eval/src/tests/tvix_tests/eval-okay-builtins-thunked-function-calls.exp
@@ -0,0 +1 @@
+[ 2 [ "Hans" "James" "Joachim" ] 2 [ "Clawdia" "Mynheer" ] 981 3 2 2 ]
diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-builtins-thunked-function-calls.nix b/tvix/eval/src/tests/tvix_tests/eval-okay-builtins-thunked-function-calls.nix
new file mode 100644
index 000000000000..d96ddb3bd16d
--- /dev/null
+++ b/tvix/eval/src/tests/tvix_tests/eval-okay-builtins-thunked-function-calls.nix
@@ -0,0 +1,31 @@
+[
+  # This is independent of builtins
+  (builtins.length [ (builtins.throw "Ferge") (builtins.throw "Wehsal") ])
+  (builtins.attrNames {
+    Hans = throw "Castorp";
+    Joachim = throw "Ziemßen";
+    James = "Tienappel";
+  })
+
+  (builtins.length (builtins.map builtins.throw [ "Settembrini" "Naphta" ]))
+
+  (builtins.attrNames (builtins.mapAttrs builtins.throw {
+    Clawdia = "Chauchat";
+    Mynheer = "Peeperkorn";
+  }))
+
+  (builtins.length (builtins.genList (builtins.add "Marusja") 981))
+  (builtins.length (builtins.genList builtins.throw 3))
+
+  # These are hard to get wrong since the outer layer needs to be forced anyways
+  (builtins.length (builtins.genericClosure {
+    startSet = [
+      { key = 1; initial = true; }
+    ];
+    operator = { key, initial, ... }:
+      if initial
+      then [ { key = key - 1; initial = false;  value = throw "lol"; } ]
+      else [ ];
+  }))
+  (builtins.length (builtins.concatMap (m: [ m (builtins.throw m) ]) [ "Marusja" ]))
+]