diff options
| -rw-r--r-- | tvix/eval/src/chunk.rs | 4 | ||||
| -rw-r--r-- | tvix/eval/src/properties.rs | 1 | ||||
| -rw-r--r-- | tvix/eval/src/upvalues.rs | 2 | ||||
| -rw-r--r-- | tvix/eval/src/value/attrs.rs | 122 | ||||
| -rw-r--r-- | tvix/eval/src/value/attrs/tests.rs | 30 | ||||
| -rw-r--r-- | tvix/eval/src/value/builtin.rs | 7 | ||||
| -rw-r--r-- | tvix/eval/src/value/function.rs | 6 | ||||
| -rw-r--r-- | tvix/eval/src/value/list.rs | 23 | ||||
| -rw-r--r-- | tvix/eval/src/value/mod.rs | 112 | ||||
| -rw-r--r-- | tvix/eval/src/value/thunk.rs | 4 | ||||
| -rw-r--r-- | 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<OpCode>, pub constants: Vec<Value>, 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<Value>, with_stack: Option<Vec<Value>>, 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<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 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<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 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<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 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<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 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<RefCell<ThunkRepr>>); 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, <), |