fix(tvix/eval/builtins): force acc not list element in foldl' r/5105

When investigating discrepancies between foldl' in tvix and C++ Nix,
I discovered that C++ Nix's foldl' doesn't seem to be strict at all.
Since this seemed wrong, I looked into Haskell's foldl' implementation
which doesn't force the list elements (`val` in our code), but the
accumulation value (`res` in our code). You can look at the code here:
https://hackage.haskell.org/package/base-4.17.0.0/docs/src/GHC.List.html#foldl%27

This actually makes a lot of sense: If `res` is not forced after each
application of `op`, we'll end up thunks nested as deeply as the list is
long, potentially taking up a lot of space. This can be limited by
forcing the `res` thunk before applying `op` again (and creating a new
thunk).

I've also PR-ed an equivalent change for C++ Nix at
https://github.com/NixOS/nix/pull/7158. Since this is not merged nor
backported to our Nix 2.3 fork, I've not copied the eval fail test yet,
since it wouldn't when checking our tests against C++ Nix in depot.

Change-Id: I34edf6fc3031fc1485c3e714f2280b4fba8f004b
Reviewed-on: https://cl.tvl.fyi/c/depot/+/6947
Autosubmit: sterni <sternenseemann@systemli.org>
Reviewed-by: grfn <grfn@gws.fyi>
Tested-by: BuildkiteCI

4 files changed, 12 insertions, 1 deletions

diff --git a/tvix/eval/docs/language-issues.md b/tvix/eval/docs/language-issues.md
index 20357cba02c5..fb74b1d3d324 100644
--- a/tvix/eval/docs/language-issues.md
+++ b/tvix/eval/docs/language-issues.md
@@ -17,6 +17,7 @@ maybe to get rid of the behavior in all implementations for good. Below is an
 * [Behaviour of nested attribute sets depends on definition order][i7111]
 * [Partially constructed attribute sets are observable during dynamic attr names construction][i7012]
 * [Nix parsers merges multiple attribute set literals for the same key incorrectly depending on definition order](i7115)
+* [builtins.foldl' doesn't seem to be strict](p7158)
 
 On the other hand, there is behavior that seems to violate one's expectation
 about the language at first, but has good enough reasons from an implementor's
@@ -37,3 +38,4 @@ perspective to keep them:
 [i7111]: https://github.com/NixOS/nix/issues/7111
 [i7012]: https://github.com/NixOS/nix/issues/7012
 [i7115]: https://github.com/NixOS/nix/issues/7115
+[p7158]: https://github.com/NixOS/nix/pull/7158
diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs
index 47e4eea63d90..05c5eceeffda 100644
--- a/tvix/eval/src/builtins/mod.rs
+++ b/tvix/eval/src/builtins/mod.rs
@@ -245,7 +245,7 @@ fn pure_builtins() -> Vec<Builtin> {
                 let mut res = args.pop().unwrap();
                 let op = args.pop().unwrap();
                 for val in list {
-                    val.force(vm)?;
+                    res.force(vm)?;
                     res = vm.call_with(&op, [val, res])?;
                 }
 
diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-foldlStrict-lazy-elements.exp b/tvix/eval/src/tests/tvix_tests/eval-okay-foldlStrict-lazy-elements.exp
new file mode 100644
index 000000000000..d81cc0710eb6
--- /dev/null
+++ b/tvix/eval/src/tests/tvix_tests/eval-okay-foldlStrict-lazy-elements.exp
@@ -0,0 +1 @@
+42
diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-foldlStrict-lazy-elements.nix b/tvix/eval/src/tests/tvix_tests/eval-okay-foldlStrict-lazy-elements.nix
new file mode 100644
index 000000000000..fc4129a2543a
--- /dev/null
+++ b/tvix/eval/src/tests/tvix_tests/eval-okay-foldlStrict-lazy-elements.nix
@@ -0,0 +1,8 @@
+let
+  lst = builtins.foldl'
+    (acc: x: acc ++ [ x ])
+    [ ]
+    [ 42 (throw "this shouldn't be evaluated") ];
+in
+
+builtins.head lst