diff options
| author | sterni <sternenseemann@systemli.org> | 2022-10-11T12·34+0200 |
|---|---|---|
| committer | clbot <clbot@tvl.fyi> | 2022-10-11T15·53+0000 |
| commit | fcd5e5370320d934f371bb96069a4719e94aafcd (patch) | |
| tree | fc535dcc04336d5f9ae5e4b9db09647706a83ad6 /tvix/eval/src | |
| parent | b319e008313d68f2639de0f656d346ed9a823e41 (diff) | |
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
Diffstat (limited to 'tvix/eval/src')
3 files changed, 10 insertions, 1 deletions
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 |