feat(tvix/eval): Implement builtins.genericClosure r/5295

This implementation closely follows the original implementation in
Nix, including the use of an equality-based "set" structure to track
keys that have already been processed.

Note that this test does not yet enable the `notyetpassing` test for
builtins.genericClosure because (for as of yet unknown reasons) this
test compares against XML output (however, evaluating the test case
actually does work).

This takes us one step closer to nixpkgs eval.

This commit was written somewhere in the North Sea.

Co-Authored-By: Griffin Smith <root@gws.fyi>
Change-Id: I450a866e6f2888b27c2fe7c7f77ce0f79bfe3e6c
Reviewed-on: https://cl.tvl.fyi/c/depot/+/7310
Tested-by: BuildkiteCI
Reviewed-by: sterni <sternenseemann@systemli.org>

1 files changed, 47 insertions, 0 deletions

diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs
index 41fa4d4d9992..3ceafa498fcd 100644
--- a/tvix/eval/src/builtins/mod.rs
+++ b/tvix/eval/src/builtins/mod.rs
@@ -54,6 +54,8 @@ pub fn coerce_value_to_path(v: &Value, vm: &mut VM) -> Result<PathBuf, ErrorKind
 
 #[builtins]
 mod pure_builtins {
+    use std::collections::VecDeque;
+
     use super::*;
 
     #[builtin("abort")]
@@ -343,6 +345,51 @@ mod pure_builtins {
         json.try_into()
     }
 
+    #[builtin("genericClosure")]
+    fn builtin_generic_closure(vm: &mut VM, input: Value) -> Result<Value, ErrorKind> {
+        let attrs = input.to_attrs()?;
+
+        // The work set is maintained as a VecDeque because new items
+        // are popped from the front.
+        let mut work_set: VecDeque<Value> = attrs
+            .select_required("startSet")?
+            .force(vm)?
+            .to_list()?
+            .into_iter()
+            .collect();
+
+        let operator = attrs.select_required("operator")?;
+
+        let mut res = NixList::new();
+        let mut done_keys: Vec<Value> = vec![];
+
+        let mut insert_key = |k: Value, vm: &mut VM| -> Result<bool, ErrorKind> {
+            for existing in &done_keys {
+                if existing.nix_eq(&k, vm)? {
+                    return Ok(false);
+                }
+            }
+            done_keys.push(k);
+            Ok(true)
+        };
+
+        while let Some(val) = work_set.pop_front() {
+            let attrs = val.force(vm)?.to_attrs()?;
+            let key = attrs.select_required("key")?;
+
+            if !insert_key(key.clone(), vm)? {
+                continue;
+            }
+
+            res.push(val.clone());
+
+            let op_result = vm.call_with(operator, Some(val))?.force(vm)?.to_list()?;
+            work_set.extend(op_result.into_iter());
+        }
+
+        Ok(Value::List(res))
+    }
+
     #[builtin("genList")]
     fn builtin_gen_list(vm: &mut VM, generator: Value, length: Value) -> Result<Value, ErrorKind> {
         let len = length.as_int()?;