From 915ff5ac2a180cbd736ce8404c46566a14d484ba Mon Sep 17 00:00:00 2001 From: Griffin Smith Date: Sun, 18 Sep 2022 14:04:40 -0400 Subject: refactor(tvix/eval): Don't (ab)use PartialEq for Nix equality 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 Tested-by: BuildkiteCI Reviewed-by: tazjin --- tvix/eval/src/chunk.rs | 4 +- tvix/eval/src/properties.rs | 1 - tvix/eval/src/upvalues.rs | 2 +- tvix/eval/src/value/attrs.rs | 122 +++++++++++++++++++++---------------- tvix/eval/src/value/attrs/tests.rs | 30 ++++++--- tvix/eval/src/value/builtin.rs | 7 +++ tvix/eval/src/value/function.rs | 6 +- tvix/eval/src/value/list.rs | 23 +++++++ tvix/eval/src/value/mod.rs | 112 ++++++++++++++++++++-------------- tvix/eval/src/value/thunk.rs | 4 +- tvix/eval/src/vm.rs | 3 +- 11 files changed, 196 insertions(+), 118 deletions(-) diff --git a/tvix/eval/src/chunk.rs b/tvix/eval/src/chunk.rs index 552a4bf6b6d4..8810f4e1c441 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, pub constants: Vec, diff --git a/tvix/eval/src/properties.rs b/tvix/eval/src/properties.rs index 8ca11d6729c0..45c1cdfce911 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 ddde8db95a21..7dd25b9f3f1a 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, with_stack: Option>, diff --git a/tvix/eval/src/value/attrs.rs b/tvix/eval/src/value/attrs.rs index 0551fe20d905..6802d195e8e2 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), @@ -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) -> Self { NixAttrs(AttrsRep::Map(map)) } + + /// Compare `self` against `other` for equality using Nix equality semantics + pub fn nix_eq(&self, other: &Self) -> Result { + 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 e25b362d2565..e96d50855b84 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 5d39a0a9f557..e79451392c2b 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 758994504e45..c875b82aee05 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, pub(crate) chunk: Chunk, @@ -30,14 +30,14 @@ impl Lambda { } } -#[derive(Clone, Debug)] +#[derive(Clone, Debug, PartialEq)] pub struct InnerClosure { pub lambda: Rc, upvalues: Upvalues, } #[repr(transparent)] -#[derive(Clone, Debug)] +#[derive(Clone, Debug, PartialEq)] pub struct Closure(Rc>); impl Closure { diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs index 19415c0d557f..8563c2256f07 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> for NixList { + fn from(vs: Vec) -> Self { + Self(vs) + } +} + #[cfg(feature = "arbitrary")] mod arbitrary { use proptest::{ @@ -73,4 +81,19 @@ impl NixList { pub fn into_iter(self) -> std::vec::IntoIter { self.0.into_iter() } + + /// Compare `self` against `other` for equality using Nix equality semantics + pub fn nix_eq(&self, other: &Self) -> Result { + 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 594c1fd4735c..34dfbddfa167 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 { + 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 5098be186fa8..ed994ebd7d57 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>); impl Thunk { diff --git a/tvix/eval/src/vm.rs b/tvix/eval/src/vm.rs index a0eb7d8ad2ee..52819a6e210b 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, <), -- cgit 1.4.1