feat(tvix/eval): Implement comparison for lists r/5221

Lists are compared lexicographically in C++ nix as of [0], and our
updated nix test suites depend on this. This implements comparison of
list values in `Value::nix_cmp` using a very similar algorithm to what
C++ does - similarly to there, this requires passing in the VM so we can
force thunks in the list elements as we go.

[0]: https://github.com/NixOS/nix/commit/09471d2680292af48b2788108de56a8da755d661#

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

7 files changed, 45 insertions, 3 deletions

diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs
index ea431977bdb6..5c029605f1ec 100644
--- a/tvix/eval/src/builtins/mod.rs
+++ b/tvix/eval/src/builtins/mod.rs
@@ -418,7 +418,7 @@ fn pure_builtins() -> Vec<Builtin> {
             &[false, false],
             |args: Vec<Value>, vm: &mut VM| {
                 Ok(Value::Bool(matches!(
-                    args[0].force(vm)?.nix_cmp(&*args[1].force(vm)?)?,
+                    args[0].force(vm)?.nix_cmp(&*args[1].force(vm)?, vm)?,
                     Some(Ordering::Less)
                 )))
             },
diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-compare-lists.exp b/tvix/eval/src/tests/tvix_tests/eval-okay-compare-lists.exp
new file mode 100644
index 000000000000..3b7fd398198a
--- /dev/null
+++ b/tvix/eval/src/tests/tvix_tests/eval-okay-compare-lists.exp
@@ -0,0 +1 @@
+[ false true true true false true false false false true false false false true true ]
diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-compare-lists.nix b/tvix/eval/src/tests/tvix_tests/eval-okay-compare-lists.nix
new file mode 100644
index 000000000000..9b73df61d84e
--- /dev/null
+++ b/tvix/eval/src/tests/tvix_tests/eval-okay-compare-lists.nix
@@ -0,0 +1,17 @@
+[
+  ([1 2] < [1])
+  ([1 2] < [2 3])
+  ([1 2] < [2])
+  ([1 2] < [1 2 3])
+  ([3 4] < [1])
+  ([1 2] > [1])
+  ([1 2] > [2 3])
+  ([1 2] > [2])
+  ([1 2] > [1 2 3])
+  ([3 4] > [1])
+  ([1 2] <= [1])
+  ([1 2] >= [2 3])
+  ([1 2] >= [2])
+  ([1 2] <= [1 2 3])
+  ([3 4] >= [1])
+]
diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs
index 8ea3db7aecf3..236a654ad88d 100644
--- a/tvix/eval/src/value/list.rs
+++ b/tvix/eval/src/value/list.rs
@@ -1,4 +1,6 @@
 //! This module implements Nix lists.
+use std::ops::Deref;
+
 use crate::errors::ErrorKind;
 use crate::vm::VM;
 
@@ -125,3 +127,11 @@ impl<'a> IntoIterator for &'a NixList {
         self.0.iter()
     }
 }
+
+impl Deref for NixList {
+    type Target = Vec<Value>;
+
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
diff --git a/tvix/eval/src/value/mod.rs b/tvix/eval/src/value/mod.rs
index 355540402d42..c590495b5344 100644
--- a/tvix/eval/src/value/mod.rs
+++ b/tvix/eval/src/value/mod.rs
@@ -351,12 +351,25 @@ impl Value {
     }
 
     /// Compare `self` against other using (fallible) Nix ordering semantics.
-    pub fn nix_cmp(&self, other: &Self) -> Result<Option<Ordering>, ErrorKind> {
+    pub fn nix_cmp(&self, other: &Self, vm: &mut VM) -> Result<Option<Ordering>, ErrorKind> {
         match (self, other) {
             // same types
             (Value::Integer(i1), Value::Integer(i2)) => Ok(i1.partial_cmp(i2)),
             (Value::Float(f1), Value::Float(f2)) => Ok(f1.partial_cmp(f2)),
             (Value::String(s1), Value::String(s2)) => Ok(s1.partial_cmp(s2)),
+            (Value::List(l1), Value::List(l2)) => {
+                for i in 0.. {
+                    if i == l2.len() {
+                        return Ok(Some(Ordering::Greater));
+                    } else if i == l1.len() {
+                        return Ok(Some(Ordering::Less));
+                    } else if !l1[i].nix_eq(&l2[i], vm)? {
+                        return l1[i].force(vm)?.nix_cmp(&*l2[i].force(vm)?, vm);
+                    }
+                }
+
+                unreachable!()
+            }
 
             // different types
             (Value::Integer(i1), Value::Float(f2)) => Ok((*i1 as f64).partial_cmp(f2)),
diff --git a/tvix/eval/src/vm.rs b/tvix/eval/src/vm.rs
index 6a5c56dc03bf..d011f651b982 100644
--- a/tvix/eval/src/vm.rs
+++ b/tvix/eval/src/vm.rs
@@ -123,7 +123,7 @@ macro_rules! cmp_op {
     ( $self:ident, $op:tt ) => {{
         let b = $self.pop();
         let a = $self.pop();
-        let ordering = fallible!($self, a.nix_cmp(&b));
+        let ordering = fallible!($self, a.nix_cmp(&b, $self));
         let result = Value::Bool(cmp_op!(@order $op ordering));
         $self.push(result);
     }};
diff --git a/tvix/verify-lang-tests/default.nix b/tvix/verify-lang-tests/default.nix
index e05ef17a85bf..ca7ea4b348a2 100644
--- a/tvix/verify-lang-tests/default.nix
+++ b/tvix/verify-lang-tests/default.nix
@@ -53,6 +53,7 @@ let
     "eval-okay-zipAttrsWith.nix" = [ nix ];
     # Comparable lists are not in Nix 2.3
     "eval-okay-sort.nix" = [ nix ];
+    "eval-okay-compare-lists.nix" = [ nix ];
     # getAttrPos gains support for functionArgs-returned sets after 2.3
     "eval-okay-getattrpos-functionargs.nix" = [ nix ];
   };