refactor(tvix/eval): Don't (ab)use PartialEq for Nix equality r/4908

Using rust's PartialEq trait to implement Nix equality semantics is
reasonably fraught with peril, both because the actual laws are
different than what nix expects, and (more importantly) because certain
things actually require extra context to compare for equality (for
example, thunks need to be forced). This converts the manual PartialEq
impl for Value (and all its descendants) to a *derived* PartialEq
impl (which requires a lot of extra PartialEq derives on miscellanious
other types within the codebase), and converts the previous
nix-semantics equality comparison into a new `nix_eq` method. This
returns an EvalResult, even though it can't currently return an error,
to allow it to fail when eg forcing thunks (which it will do soon).

Since the PartialEq impls for Value and NixAttrs are now quite boring,
this converts the generated proptests for those into handwritten ones
that cover `nix_eq` instead

Change-Id: If3da7171f88c22eda5b7a60030d8b00c3b76f672
Reviewed-on: https://cl.tvl.fyi/c/depot/+/6650
Autosubmit: grfn <grfn@gws.fyi>
Tested-by: BuildkiteCI
Reviewed-by: tazjin <tazjin@tvl.su>

11 files changed, 196 insertions, 118 deletions

diff --git a/tvix/eval/src/chunk.rs b/tvix/eval/src/chunk.rs
index 552a4bf6b6..8810f4e1c4 100644
--- a/tvix/eval/src/chunk.rs
+++ b/tvix/eval/src/chunk.rs
@@ -17,7 +17,7 @@ use crate::value::Value;
 /// the textual representation of that span from the codemap, or to
 /// even re-parse the AST using rnix to create more semantically
 /// interesting errors.
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, PartialEq)]
 struct SourceSpan {
     /// Span into the [codemap::Codemap].
     span: codemap::Span,
@@ -29,7 +29,7 @@ struct SourceSpan {
 /// A chunk is a representation of a sequence of bytecode
 /// instructions, associated constants and additional metadata as
 /// emitted by the compiler.
-#[derive(Clone, Debug, Default)]
+#[derive(Clone, Debug, Default, PartialEq)]
 pub struct Chunk {
     pub code: Vec<OpCode>,
     pub constants: Vec<Value>,
diff --git a/tvix/eval/src/properties.rs b/tvix/eval/src/properties.rs
index 8ca11d6729..45c1cdfce9 100644
--- a/tvix/eval/src/properties.rs
+++ b/tvix/eval/src/properties.rs
@@ -35,7 +35,6 @@ macro_rules! eq_laws {
 
             #[proptest($config)]
             fn transitive(#[$meta] x: $ty, #[$meta] y: $ty, #[$meta] z: $ty) {
-                dbg!(&x, &y, &z);
                 if x == y && y == z {
                     assert!(x == z);
                 }
diff --git a/tvix/eval/src/upvalues.rs b/tvix/eval/src/upvalues.rs
index ddde8db95a..7dd25b9f3f 100644
--- a/tvix/eval/src/upvalues.rs
+++ b/tvix/eval/src/upvalues.rs
@@ -13,7 +13,7 @@ use crate::{opcode::UpvalueIdx, Value};
 /// Structure for carrying upvalues inside of thunks & closures. The
 /// implementation of this struct encapsulates the logic for capturing
 /// and accessing upvalues.
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, PartialEq)]
 pub struct Upvalues {
     upvalues: Vec<Value>,
     with_stack: Option<Vec<Value>>,
diff --git a/tvix/eval/src/value/attrs.rs b/tvix/eval/src/value/attrs.rs
index 0551fe20d9..6802d195e8 100644
--- a/tvix/eval/src/value/attrs.rs
+++ b/tvix/eval/src/value/attrs.rs
@@ -18,7 +18,7 @@ use super::Value;
 #[cfg(test)]
 mod tests;
 
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, PartialEq)]
 enum AttrsRep {
     Empty,
     Map(BTreeMap<NixString, Value>),
@@ -71,7 +71,7 @@ impl AttrsRep {
 }
 
 #[repr(transparent)]
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, PartialEq)]
 pub struct NixAttrs(AttrsRep);
 
 impl Display for NixAttrs {
@@ -97,58 +97,6 @@ impl Display for NixAttrs {
     }
 }
 
-impl PartialEq for NixAttrs {
-    fn eq(&self, other: &Self) -> bool {
-        match (&self.0, &other.0) {
-            (AttrsRep::Empty, AttrsRep::Empty) => true,
-
-            // It is possible to create an empty attribute set that
-            // has Map representation like so: ` { ${null} = 1; }`.
-            //
-            // Preventing this would incur a cost on all attribute set
-            // construction (we'd have to check the actual number of
-            // elements after key construction). In practice this
-            // probably does not happen, so it's better to just bite
-            // the bullet and implement this branch.
-            (AttrsRep::Empty, AttrsRep::Map(map)) | (AttrsRep::Map(map), AttrsRep::Empty) => {
-                map.is_empty()
-            }
-
-            // Other specialised representations (KV ...) definitely
-            // do not match `Empty`.
-            (AttrsRep::Empty, _) | (_, AttrsRep::Empty) => false,
-
-            (
-                AttrsRep::KV {
-                    name: n1,
-                    value: v1,
-                },
-                AttrsRep::KV {
-                    name: n2,
-                    value: v2,
-                },
-            ) => n1 == n2 && v1 == v2,
-
-            (AttrsRep::Map(map), AttrsRep::KV { name, value })
-            | (AttrsRep::KV { name, value }, AttrsRep::Map(map)) => {
-                if map.len() != 2 {
-                    return false;
-                }
-
-                if let (Some(m_name), Some(m_value)) =
-                    (map.get(&NixString::NAME), map.get(&NixString::VALUE))
-                {
-                    return name == m_name && value == m_value;
-                }
-
-                false
-            }
-
-            (AttrsRep::Map(m1), AttrsRep::Map(m2)) => m1 == m2,
-        }
-    }
-}
-
 #[cfg(feature = "arbitrary")]
 mod arbitrary {
     use super::*;
@@ -337,6 +285,72 @@ impl NixAttrs {
     pub(crate) fn from_map(map: BTreeMap<NixString, Value>) -> Self {
         NixAttrs(AttrsRep::Map(map))
     }
+
+    /// Compare `self` against `other` for equality using Nix equality semantics
+    pub fn nix_eq(&self, other: &Self) -> Result<bool, ErrorKind> {
+        match (&self.0, &other.0) {
+            (AttrsRep::Empty, AttrsRep::Empty) => Ok(true),
+
+            // It is possible to create an empty attribute set that
+            // has Map representation like so: ` { ${null} = 1; }`.
+            //
+            // Preventing this would incur a cost on all attribute set
+            // construction (we'd have to check the actual number of
+            // elements after key construction). In practice this
+            // probably does not happen, so it's better to just bite
+            // the bullet and implement this branch.
+            (AttrsRep::Empty, AttrsRep::Map(map)) | (AttrsRep::Map(map), AttrsRep::Empty) => {
+                Ok(map.is_empty())
+            }
+
+            // Other specialised representations (KV ...) definitely
+            // do not match `Empty`.
+            (AttrsRep::Empty, _) | (_, AttrsRep::Empty) => Ok(false),
+
+            (
+                AttrsRep::KV {
+                    name: n1,
+                    value: v1,
+                },
+                AttrsRep::KV {
+                    name: n2,
+                    value: v2,
+                },
+            ) => Ok(n1.nix_eq(n2)? && v1.nix_eq(v2)?),
+
+            (AttrsRep::Map(map), AttrsRep::KV { name, value })
+            | (AttrsRep::KV { name, value }, AttrsRep::Map(map)) => {
+                if map.len() != 2 {
+                    return Ok(false);
+                }
+
+                if let (Some(m_name), Some(m_value)) =
+                    (map.get(&NixString::NAME), map.get(&NixString::VALUE))
+                {
+                    return Ok(name.nix_eq(m_name)? && value.nix_eq(m_value)?);
+                }
+
+                Ok(false)
+            }
+
+            (AttrsRep::Map(m1), AttrsRep::Map(m2)) => {
+                if m1.len() != m2.len() {
+                    return Ok(false);
+                }
+
+                for (k, v1) in m1 {
+                    if let Some(v2) = m2.get(k) {
+                        if !v1.nix_eq(v2)? {
+                            return Ok(false);
+                        }
+                    } else {
+                        return Ok(false);
+                    }
+                }
+                Ok(true)
+            }
+        }
+    }
 }
 
 /// In Nix, name/value attribute pairs are frequently constructed from
diff --git a/tvix/eval/src/value/attrs/tests.rs b/tvix/eval/src/value/attrs/tests.rs
index e25b362d25..e96d50855b 100644
--- a/tvix/eval/src/value/attrs/tests.rs
+++ b/tvix/eval/src/value/attrs/tests.rs
@@ -1,15 +1,27 @@
-use proptest::prelude::ProptestConfig;
-
 use super::*;
-use crate::properties::eq_laws;
 
-eq_laws!(
-    NixAttrs,
-    ProptestConfig {
-        cases: 5,
-        ..Default::default()
+mod nix_eq {
+    use super::*;
+    use proptest::prelude::ProptestConfig;
+    use test_strategy::proptest;
+
+    #[proptest(ProptestConfig { cases: 5, ..Default::default() })]
+    fn reflexive(x: NixAttrs) {
+        assert!(x.nix_eq(&x).unwrap())
+    }
+
+    #[proptest(ProptestConfig { cases: 5, ..Default::default() })]
+    fn symmetric(x: NixAttrs, y: NixAttrs) {
+        assert_eq!(x.nix_eq(&y).unwrap(), y.nix_eq(&x).unwrap())
     }
-);
+
+    #[proptest(ProptestConfig { cases: 5, ..Default::default() })]
+    fn transitive(x: NixAttrs, y: NixAttrs, z: NixAttrs) {
+        if x.nix_eq(&y).unwrap() && y.nix_eq(&z).unwrap() {
+            assert!(x.nix_eq(&z).unwrap())
+        }
+    }
+}
 
 #[test]
 fn test_empty_attrs() {
diff --git a/tvix/eval/src/value/builtin.rs b/tvix/eval/src/value/builtin.rs
index 5d39a0a9f5..e79451392c 100644
--- a/tvix/eval/src/value/builtin.rs
+++ b/tvix/eval/src/value/builtin.rs
@@ -87,3 +87,10 @@ impl Display for Builtin {
         }
     }
 }
+
+/// Builtins are uniquely identified by their name
+impl PartialEq for Builtin {
+    fn eq(&self, other: &Self) -> bool {
+        self.name == other.name
+    }
+}
diff --git a/tvix/eval/src/value/function.rs b/tvix/eval/src/value/function.rs
index 758994504e..c875b82aee 100644
--- a/tvix/eval/src/value/function.rs
+++ b/tvix/eval/src/value/function.rs
@@ -9,7 +9,7 @@ use crate::{
     upvalues::{UpvalueCarrier, Upvalues},
 };
 
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, PartialEq)]
 pub struct Lambda {
     // name: Option<NixString>,
     pub(crate) chunk: Chunk,
@@ -30,14 +30,14 @@ impl Lambda {
     }
 }
 
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, PartialEq)]
 pub struct InnerClosure {
     pub lambda: Rc<Lambda>,
     upvalues: Upvalues,
 }
 
 #[repr(transparent)]
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, PartialEq)]
 pub struct Closure(Rc<RefCell<InnerClosure>>);
 
 impl Closure {
diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs
index 19415c0d55..8563c2256f 100644
--- a/tvix/eval/src/value/list.rs
+++ b/tvix/eval/src/value/list.rs
@@ -1,6 +1,8 @@
 //! This module implements Nix lists.
 use std::fmt::Display;
 
+use crate::errors::ErrorKind;
+
 use super::Value;
 
 #[repr(transparent)]
@@ -20,6 +22,12 @@ impl Display for NixList {
     }
 }
 
+impl From<Vec<Value>> for NixList {
+    fn from(vs: Vec<Value>) -> Self {
+        Self(vs)
+    }
+}
+
 #[cfg(feature = "arbitrary")]
 mod arbitrary {
     use proptest::{
@@ -73,4 +81,19 @@ impl NixList {
     pub fn into_iter(self) -> std::vec::IntoIter<Value> {
         self.0.into_iter()
     }
+
+    /// Compare `self` against `other` for equality using Nix equality semantics
+    pub fn nix_eq(&self, other: &Self) -> Result<bool, ErrorKind> {
+        if self.len() != other.len() {
+            return Ok(false);
+        }
+
+        for (v1, v2) in self.iter().zip(other.iter()) {
+            if !v1.nix_eq(v2)? {
+                return Ok(false);
+            }
+        }
+
+        Ok(true)
+    }
 }
diff --git a/tvix/eval/src/value/mod.rs b/tvix/eval/src/value/mod.rs
index 594c1fd473..34dfbddfa1 100644
--- a/tvix/eval/src/value/mod.rs
+++ b/tvix/eval/src/value/mod.rs
@@ -24,7 +24,7 @@ pub use string::NixString;
 pub use thunk::Thunk;
 
 #[warn(variant_size_differences)]
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, PartialEq)]
 pub enum Value {
     Null,
     Bool(bool),
@@ -253,6 +253,40 @@ impl Value {
 
     gen_is!(is_number, Value::Integer(_) | Value::Float(_));
     gen_is!(is_bool, Value::Bool(_));
+
+    /// Compare `self` against `other` for equality using Nix equality semantics
+    pub fn nix_eq(&self, other: &Self) -> Result<bool, ErrorKind> {
+        match (self, other) {
+            // Trivial comparisons
+            (Value::Null, Value::Null) => Ok(true),
+            (Value::Bool(b1), Value::Bool(b2)) => Ok(b1 == b2),
+            (Value::List(l1), Value::List(l2)) => l1.nix_eq(l2),
+            (Value::String(s1), Value::String(s2)) => Ok(s1 == s2),
+            (Value::Path(p1), Value::Path(p2)) => Ok(p1 == p2),
+
+            // Numerical comparisons (they work between float & int)
+            (Value::Integer(i1), Value::Integer(i2)) => Ok(i1 == i2),
+            (Value::Integer(i), Value::Float(f)) => Ok(*i as f64 == *f),
+            (Value::Float(f1), Value::Float(f2)) => Ok(f1 == f2),
+            (Value::Float(f), Value::Integer(i)) => Ok(*i as f64 == *f),
+
+            // Optimised attribute set comparison
+            (Value::Attrs(a1), Value::Attrs(a2)) => Ok(Rc::ptr_eq(a1, a2) || a1.nix_eq(a2)?),
+
+            // If either value is a thunk, the inner value must be
+            // compared instead. The compiler should ensure that
+            // thunks under comparison have been forced, otherwise it
+            // is a bug.
+            (Value::Thunk(lhs), Value::Thunk(rhs)) => Ok(*lhs.value() == *rhs.value()),
+            (Value::Thunk(lhs), rhs) => Ok(&*lhs.value() == rhs),
+            (lhs, Value::Thunk(rhs)) => Ok(lhs == &*rhs.value()),
+
+            // Everything else is either incomparable (e.g. internal
+            // types) or false.
+            // TODO(tazjin): mirror Lambda equality behaviour
+            _ => Ok(false),
+        }
+    }
 }
 
 impl Display for Value {
@@ -291,41 +325,6 @@ impl Display for Value {
     }
 }
 
-impl PartialEq for Value {
-    fn eq(&self, other: &Self) -> bool {
-        match (self, other) {
-            // Trivial comparisons
-            (Value::Null, Value::Null) => true,
-            (Value::Bool(b1), Value::Bool(b2)) => b1 == b2,
-            (Value::List(l1), Value::List(l2)) => l1 == l2,
-            (Value::String(s1), Value::String(s2)) => s1 == s2,
-            (Value::Path(p1), Value::Path(p2)) => p1 == p2,
-
-            // Numerical comparisons (they work between float & int)
-            (Value::Integer(i1), Value::Integer(i2)) => i1 == i2,
-            (Value::Integer(i), Value::Float(f)) => *i as f64 == *f,
-            (Value::Float(f1), Value::Float(f2)) => f1 == f2,
-            (Value::Float(f), Value::Integer(i)) => *i as f64 == *f,
-
-            // Optimised attribute set comparison
-            (Value::Attrs(a1), Value::Attrs(a2)) => Rc::ptr_eq(a1, a2) || { a1 == a2 },
-
-            // If either value is a thunk, the inner value must be
-            // compared instead. The compiler should ensure that
-            // thunks under comparison have been forced, otherwise it
-            // is a bug.
-            (Value::Thunk(lhs), Value::Thunk(rhs)) => *lhs.value() == *rhs.value(),
-            (Value::Thunk(lhs), rhs) => &*lhs.value() == rhs,
-            (lhs, Value::Thunk(rhs)) => lhs == &*rhs.value(),
-
-            // Everything else is either incomparable (e.g. internal
-            // types) or false.
-            // TODO(tazjin): mirror Lambda equality behaviour
-            _ => false,
-        }
-    }
-}
-
 fn type_error(expected: &'static str, actual: &Value) -> ErrorKind {
     ErrorKind::TypeError {
         expected,
@@ -335,16 +334,39 @@ fn type_error(expected: &'static str, actual: &Value) -> ErrorKind {
 
 #[cfg(test)]
 mod tests {
-    use crate::properties::eq_laws;
-    use proptest::prelude::ProptestConfig;
-
     use super::*;
 
-    eq_laws!(
-        Value,
-        ProptestConfig {
-            cases: 20,
-            ..Default::default()
+    #[test]
+    fn test_name() {}
+
+    mod nix_eq {
+        use super::*;
+        use proptest::prelude::ProptestConfig;
+        use test_strategy::proptest;
+
+        #[proptest(ProptestConfig { cases: 5, ..Default::default() })]
+        fn reflexive(x: Value) {
+            assert!(x.nix_eq(&x).unwrap())
+        }
+
+        #[proptest(ProptestConfig { cases: 5, ..Default::default() })]
+        fn symmetric(x: Value, y: Value) {
+            assert_eq!(x.nix_eq(&y).unwrap(), y.nix_eq(&x).unwrap())
+        }
+
+        #[proptest(ProptestConfig { cases: 5, ..Default::default() })]
+        fn transitive(x: Value, y: Value, z: Value) {
+            if x.nix_eq(&y).unwrap() && y.nix_eq(&z).unwrap() {
+                assert!(x.nix_eq(&z).unwrap())
+            }
+        }
+
+        #[test]
+        fn list_int_float_fungibility() {
+            let v1 = Value::List(NixList::from(vec![Value::Integer(1)]));
+            let v2 = Value::List(NixList::from(vec![Value::Float(1.0)]));
+
+            assert!(v1.nix_eq(&v2).unwrap())
         }
-    );
+    }
 }
diff --git a/tvix/eval/src/value/thunk.rs b/tvix/eval/src/value/thunk.rs
index 5098be186f..ed994ebd7d 100644
--- a/tvix/eval/src/value/thunk.rs
+++ b/tvix/eval/src/value/thunk.rs
@@ -34,7 +34,7 @@ use crate::{
 use super::Lambda;
 
 /// Internal representation of the different states of a thunk.
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, PartialEq)]
 enum ThunkRepr {
     /// Thunk is closed over some values, suspended and awaiting
     /// execution.
@@ -51,7 +51,7 @@ enum ThunkRepr {
     Evaluated(Value),
 }
 
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, PartialEq)]
 pub struct Thunk(Rc<RefCell<ThunkRepr>>);
 
 impl Thunk {
diff --git a/tvix/eval/src/vm.rs b/tvix/eval/src/vm.rs
index a0eb7d8ad2..52819a6e21 100644
--- a/tvix/eval/src/vm.rs
+++ b/tvix/eval/src/vm.rs
@@ -265,8 +265,9 @@ impl<'o> VM<'o> {
                 OpCode::OpEqual => {
                     let v2 = self.pop();
                     let v1 = self.pop();
+                    let res = fallible!(self, v1.nix_eq(&v2));
 
-                    self.push(Value::Bool(v1 == v2))
+                    self.push(Value::Bool(res))
                 }
 
                 OpCode::OpLess => cmp_op!(self, <),