diff options
Diffstat (limited to 'tvix/eval/src/value')
| -rw-r--r-- | tvix/eval/src/value/attrs.rs | 67 | ||||
| -rw-r--r-- | tvix/eval/src/value/attrs/tests.rs | 52 | ||||
| -rw-r--r-- | tvix/eval/src/value/builtin.rs | 78 | ||||
| -rw-r--r-- | tvix/eval/src/value/list.rs | 32 | ||||
| -rw-r--r-- | tvix/eval/src/value/mod.rs | 401 | ||||
| -rw-r--r-- | tvix/eval/src/value/thunk.rs | 264 |
6 files changed, 232 insertions, 662 deletions
diff --git a/tvix/eval/src/value/attrs.rs b/tvix/eval/src/value/attrs.rs index b9c5adba19b8..64a1dc035b54 100644 --- a/tvix/eval/src/value/attrs.rs +++ b/tvix/eval/src/value/attrs.rs @@ -13,7 +13,6 @@ use serde::ser::SerializeMap; use serde::{Deserialize, Serialize}; use crate::errors::ErrorKind; -use crate::vm::VM; use super::string::NixString; use super::thunk::ThunkSet; @@ -394,72 +393,6 @@ impl NixAttrs { pub(crate) fn from_kv(name: Value, value: Value) -> Self { NixAttrs(AttrsRep::KV { name, value }) } - - /// Compare `self` against `other` for equality using Nix equality semantics - pub fn nix_eq(&self, other: &Self, vm: &mut VM) -> 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::Im(map)) | (AttrsRep::Im(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, vm)? && v1.nix_eq(v2, vm)?), - - (AttrsRep::Im(map), AttrsRep::KV { name, value }) - | (AttrsRep::KV { name, value }, AttrsRep::Im(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, vm)? && value.nix_eq(m_value, vm)?); - } - - Ok(false) - } - - (AttrsRep::Im(m1), AttrsRep::Im(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, vm)? { - 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 ccf8dc7c10e0..39ac55b6799a 100644 --- a/tvix/eval/src/value/attrs/tests.rs +++ b/tvix/eval/src/value/attrs/tests.rs @@ -1,57 +1,5 @@ use super::*; -mod nix_eq { - use crate::observer::NoOpObserver; - - use super::*; - use proptest::prelude::ProptestConfig; - use test_strategy::proptest; - - #[proptest(ProptestConfig { cases: 2, ..Default::default() })] - fn reflexive(x: NixAttrs) { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - assert!(x.nix_eq(&x, &mut vm).unwrap()) - } - - #[proptest(ProptestConfig { cases: 2, ..Default::default() })] - fn symmetric(x: NixAttrs, y: NixAttrs) { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - assert_eq!( - x.nix_eq(&y, &mut vm).unwrap(), - y.nix_eq(&x, &mut vm).unwrap() - ) - } - - #[proptest(ProptestConfig { cases: 2, ..Default::default() })] - fn transitive(x: NixAttrs, y: NixAttrs, z: NixAttrs) { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - if x.nix_eq(&y, &mut vm).unwrap() && y.nix_eq(&z, &mut vm).unwrap() { - assert!(x.nix_eq(&z, &mut vm).unwrap()) - } - } -} - #[test] fn test_empty_attrs() { let attrs = NixAttrs::construct(0, vec![]).expect("empty attr construction should succeed"); diff --git a/tvix/eval/src/value/builtin.rs b/tvix/eval/src/value/builtin.rs index c7fc33903d96..0577111030a2 100644 --- a/tvix/eval/src/value/builtin.rs +++ b/tvix/eval/src/value/builtin.rs @@ -3,7 +3,7 @@ //! //! Builtins are directly backed by Rust code operating on Nix values. -use crate::{errors::ErrorKind, vm::VM}; +use crate::vm::generators::Generator; use super::Value; @@ -12,40 +12,38 @@ use std::{ rc::Rc, }; -/// Trait for closure types of builtins implemented directly by -/// backing Rust code. +/// Trait for closure types of builtins. /// -/// Builtins declare their arity and are passed a vector with the -/// right number of arguments. Additionally, as they might have to -/// force the evaluation of thunks, they are passed a reference to the -/// current VM which they can use for forcing a value. +/// Builtins are expected to yield a generator which can be run by the VM to +/// produce the final value. /// -/// Errors returned from a builtin will be annotated with the location -/// of the call to the builtin. -pub trait BuiltinFn: Fn(Vec<Value>, &mut VM) -> Result<Value, ErrorKind> {} -impl<F: Fn(Vec<Value>, &mut VM) -> Result<Value, ErrorKind>> BuiltinFn for F {} - -/// Description of a single argument passed to a builtin -pub struct BuiltinArgument { - /// Whether the argument should be forced before the underlying builtin function is called - pub strict: bool, - /// The name of the argument, to be used in docstrings and error messages - pub name: &'static str, -} +/// Implementors should use the builtins-macros to create these functions +/// instead of handling the argument-passing logic manually. +pub trait BuiltinGen: Fn(Vec<Value>) -> Generator {} +impl<F: Fn(Vec<Value>) -> Generator> BuiltinGen for F {} #[derive(Clone)] pub struct BuiltinRepr { name: &'static str, - /// Array of arguments to the builtin. - arguments: &'static [BuiltinArgument], /// Optional documentation for the builtin. documentation: Option<&'static str>, - func: Rc<dyn BuiltinFn>, + arg_count: usize, + + func: Rc<dyn BuiltinGen>, /// Partially applied function arguments. partials: Vec<Value>, } +pub enum BuiltinResult { + /// Builtin was not ready to be called (arguments missing) and remains + /// partially applied. + Partial(Builtin), + + /// Builtin was called and constructed a generator that the VM must run. + Called(Generator), +} + /// Represents a single built-in function which directly executes Rust /// code that operates on a Nix value. /// @@ -68,16 +66,16 @@ impl From<BuiltinRepr> for Builtin { } impl Builtin { - pub fn new<F: BuiltinFn + 'static>( + pub fn new<F: BuiltinGen + 'static>( name: &'static str, - arguments: &'static [BuiltinArgument], documentation: Option<&'static str>, + arg_count: usize, func: F, ) -> Self { BuiltinRepr { name, - arguments, documentation, + arg_count, func: Rc::new(func), partials: vec![], } @@ -92,23 +90,25 @@ impl Builtin { self.0.documentation } - /// Apply an additional argument to the builtin, which will either - /// lead to execution of the function or to returning a partial - /// builtin. - pub fn apply(mut self, vm: &mut VM, arg: Value) -> Result<Value, ErrorKind> { + /// Apply an additional argument to the builtin. After this, [`call`] *must* + /// be called, otherwise it may leave the builtin in an incorrect state. + pub fn apply_arg(&mut self, arg: Value) { self.0.partials.push(arg); - if self.0.partials.len() == self.0.arguments.len() { - for (idx, BuiltinArgument { strict, .. }) in self.0.arguments.iter().enumerate() { - if *strict { - self.0.partials[idx].force(vm)?; - } - } - return (self.0.func)(self.0.partials, vm); - } + debug_assert!( + self.0.partials.len() <= self.0.arg_count, + "Tvix bug: pushed too many arguments to builtin" + ); + } - // Function is not yet ready to be called. - Ok(Value::Builtin(self)) + /// Attempt to call a builtin, which will produce a generator if it is fully + /// applied or return the builtin if it is partially applied. + pub fn call(self) -> BuiltinResult { + if self.0.partials.len() == self.0.arg_count { + BuiltinResult::Called((self.0.func)(self.0.partials)) + } else { + BuiltinResult::Partial(self) + } } } diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs index e5ddc7bb96b9..9f39b7c6a3d3 100644 --- a/tvix/eval/src/value/list.rs +++ b/tvix/eval/src/value/list.rs @@ -5,11 +5,10 @@ use imbl::{vector, Vector}; use serde::{Deserialize, Serialize}; -use crate::errors::AddContext; -use crate::errors::ErrorKind; -use crate::vm::generators; -use crate::vm::generators::GenCo; -use crate::vm::VM; +use crate::generators; +use crate::generators::GenCo; +use crate::AddContext; +use crate::ErrorKind; use super::thunk::ThunkSet; use super::TotalDisplay; @@ -70,29 +69,6 @@ impl NixList { self.0.ptr_eq(&other.0) } - /// Compare `self` against `other` for equality using Nix equality semantics - pub fn nix_eq(&self, other: &Self, vm: &mut VM) -> Result<bool, ErrorKind> { - if self.ptr_eq(other) { - return Ok(true); - } - if self.len() != other.len() { - return Ok(false); - } - - for (v1, v2) in self.iter().zip(other.iter()) { - if !v1.nix_eq(v2, vm)? { - return Ok(false); - } - } - - Ok(true) - } - - /// force each element of the list (shallowly), making it safe to call .get().value() - pub fn force_elements(&self, vm: &mut VM) -> Result<(), ErrorKind> { - self.iter().try_for_each(|v| v.force(vm).map(|_| ())) - } - pub fn into_inner(self) -> Vector<Value> { self.0 } diff --git a/tvix/eval/src/value/mod.rs b/tvix/eval/src/value/mod.rs index a869c0167524..81e537313227 100644 --- a/tvix/eval/src/value/mod.rs +++ b/tvix/eval/src/value/mod.rs @@ -1,11 +1,12 @@ //! This module implements the backing representation of runtime //! values in the Nix language. use std::cmp::Ordering; +use std::fmt::Display; +use std::future::Future; use std::num::{NonZeroI32, NonZeroUsize}; -use std::ops::Deref; use std::path::PathBuf; +use std::pin::Pin; use std::rc::Rc; -use std::{cell::Ref, fmt::Display}; use lexical_core::format::CXX_LITERAL; use serde::{Deserialize, Serialize}; @@ -20,12 +21,12 @@ mod path; mod string; mod thunk; -use crate::errors::{AddContext, ErrorKind}; +use crate::errors::ErrorKind; use crate::opcode::StackIdx; use crate::vm::generators::{self, GenCo}; -use crate::vm::VM; +use crate::AddContext; pub use attrs::NixAttrs; -pub use builtin::{Builtin, BuiltinArgument}; +pub use builtin::{Builtin, BuiltinResult}; pub(crate) use function::Formals; pub use function::{Closure, Lambda}; pub use list::NixList; @@ -139,8 +140,6 @@ macro_rules! gen_is { /// Describes what input types are allowed when coercing a `Value` to a string #[derive(Clone, Copy, PartialEq, Debug)] pub enum CoercionKind { - /// Force thunks, but perform no other coercions. - ThunksOnly, /// Only coerce already "stringly" types like strings and paths, but also /// coerce sets that have a `__toString` attribute. Equivalent to /// `!coerceMore` in C++ Nix. @@ -151,26 +150,6 @@ pub enum CoercionKind { Strong, } -/// A reference to a [`Value`] returned by a call to [`Value::force`], whether the value was -/// originally a thunk or not. -/// -/// Implements [`Deref`] to [`Value`], so can generally be used as a [`Value`] -pub enum ForceResult<'a> { - ForcedThunk(Ref<'a, Value>), - Immediate(&'a Value), -} - -impl<'a> Deref for ForceResult<'a> { - type Target = Value; - - fn deref(&self) -> &Self::Target { - match self { - ForceResult::ForcedThunk(r) => r, - ForceResult::Immediate(v) => v, - } - } -} - impl<T> From<T> for Value where T: Into<NixString>, @@ -204,33 +183,80 @@ pub enum PointerEquality { } impl Value { + /// Deeply forces a value, traversing e.g. lists and attribute sets and forcing + /// their contents, too. + /// + /// This is a generator function. + pub(super) async fn deep_force( + self, + co: GenCo, + thunk_set: SharedThunkSet, + ) -> Result<Value, ErrorKind> { + // Get rid of any top-level thunks, and bail out of self-recursive + // thunks. + let value = if let Value::Thunk(ref t) = &self { + if !thunk_set.insert(t) { + return Ok(self); + } + generators::request_force(&co, self).await + } else { + self + }; + + match &value { + // Short-circuit on already evaluated values, or fail on internal values. + Value::Null + | Value::Bool(_) + | Value::Integer(_) + | Value::Float(_) + | Value::String(_) + | Value::Path(_) + | Value::Closure(_) + | Value::Builtin(_) => return Ok(value), + + Value::List(list) => { + for val in list { + generators::request_deep_force(&co, val.clone(), thunk_set.clone()).await; + } + } + + Value::Attrs(attrs) => { + for (_, val) in attrs.iter() { + generators::request_deep_force(&co, val.clone(), thunk_set.clone()).await; + } + } + + Value::Thunk(_) => panic!("Tvix bug: force_value() returned a thunk"), + + Value::AttrNotFound + | Value::Blueprint(_) + | Value::DeferredUpvalue(_) + | Value::UnresolvedPath(_) => panic!( + "Tvix bug: internal value left on stack: {}", + value.type_of() + ), + }; + + Ok(value) + } + /// Coerce a `Value` to a string. See `CoercionKind` for a rundown of what /// input types are accepted under what circumstances. - pub fn coerce_to_string( - &self, - kind: CoercionKind, - vm: &mut VM, - ) -> Result<NixString, ErrorKind> { - // TODO: eventually, this will need to handle string context and importing - // files into the Nix store depending on what context the coercion happens in - if let Value::Thunk(t) = self { - t.force(vm)?; - } - - match (self, kind) { - // deal with thunks - (Value::Thunk(t), _) => t.value().coerce_to_string(kind, vm), + pub async fn coerce_to_string(self, co: GenCo, kind: CoercionKind) -> Result<Value, ErrorKind> { + let value = generators::request_force(&co, self).await; + match (value, kind) { // coercions that are always done - (Value::String(s), _) => Ok(s.clone()), + tuple @ (Value::String(_), _) => Ok(tuple.0), // TODO(sterni): Think about proper encoding handling here. This needs // general consideration anyways, since one current discrepancy between // C++ Nix and Tvix is that the former's strings are arbitrary byte // sequences without NUL bytes, whereas Tvix only allows valid // Unicode. See also b/189. - (Value::Path(p), kind) if kind != CoercionKind::ThunksOnly => { - let imported = vm.io().import_path(p)?; + (Value::Path(p), _) => { + // TODO(tazjin): there are cases where coerce_to_string does not import + let imported = generators::request_path_import(&co, p).await; Ok(imported.to_string_lossy().into_owned().into()) } @@ -238,38 +264,32 @@ impl Value { // `__toString` attribute which holds a function that receives the // set itself or an `outPath` attribute which should be a string. // `__toString` is preferred. - (Value::Attrs(attrs), kind) if kind != CoercionKind::ThunksOnly => { + (Value::Attrs(attrs), kind) => { match (attrs.select("__toString"), attrs.select("outPath")) { (None, None) => Err(ErrorKind::NotCoercibleToString { from: "set", kind }), (Some(f), _) => { - // use a closure here to deal with the thunk borrow we need to do below - let call_to_string = |value: &Value, vm: &mut VM| { - // Leave self on the stack as an argument to the function call. - vm.push(self.clone()); - vm.call_value(value)?; - let result = vm.pop(); - - match result { - Value::String(s) => Ok(s), - // Attribute set coercion actually works - // recursively, e.g. you can even return - // /another/ set with a __toString attr. - _ => result.coerce_to_string(kind, vm), - } - }; - - if let Value::Thunk(t) = f { - t.force(vm)?; - let guard = t.value(); - call_to_string(&guard, vm) - } else { - call_to_string(f, vm) - } + let callable = generators::request_force(&co, f.clone()).await; + + // Leave the attribute set on the stack as an argument + // to the function call. + generators::request_stack_push(&co, Value::Attrs(attrs)).await; + + // Call the callable ... + let result = generators::request_call(&co, callable).await; + + // Recurse on the result, as attribute set coercion + // actually works recursively, e.g. you can even return + // /another/ set with a __toString attr. + let s = generators::request_string_coerce(&co, result, kind).await; + Ok(Value::String(s)) } // Similarly to `__toString` we also coerce recursively for `outPath` - (None, Some(s)) => s.coerce_to_string(kind, vm), + (None, Some(s)) => { + let s = generators::request_string_coerce(&co, s.clone(), kind).await; + Ok(Value::String(s)) + } } } @@ -287,30 +307,31 @@ impl Value { } // Lists are coerced by coercing their elements and interspersing spaces - (Value::List(l), CoercionKind::Strong) => { - // TODO(sterni): use intersperse when it becomes available? - // https://github.com/rust-lang/rust/issues/79524 - l.iter() - .map(|v| v.coerce_to_string(kind, vm)) - .reduce(|acc, string| { - let a = acc?; - let s = &string?; - Ok(a.concat(&" ".into()).concat(s)) - }) - // None from reduce indicates empty iterator - .unwrap_or_else(|| Ok("".into())) + (Value::List(list), CoercionKind::Strong) => { + let mut out = String::new(); + + for (idx, elem) in list.into_iter().enumerate() { + if idx > 0 { + out.push(' '); + } + + let s = generators::request_string_coerce(&co, elem, kind).await; + out.push_str(s.as_str()); + } + + Ok(Value::String(out.into())) } - (Value::Path(_), _) - | (Value::Attrs(_), _) - | (Value::Closure(_), _) - | (Value::Builtin(_), _) - | (Value::Null, _) - | (Value::Bool(_), _) - | (Value::Integer(_), _) - | (Value::Float(_), _) - | (Value::List(_), _) => Err(ErrorKind::NotCoercibleToString { - from: self.type_of(), + (Value::Thunk(_), _) => panic!("Tvix bug: force returned unforced thunk"), + + val @ (Value::Closure(_), _) + | val @ (Value::Builtin(_), _) + | val @ (Value::Null, _) + | val @ (Value::Bool(_), _) + | val @ (Value::Integer(_), _) + | val @ (Value::Float(_), _) + | val @ (Value::List(_), _) => Err(ErrorKind::NotCoercibleToString { + from: val.0.type_of(), kind, }), @@ -333,7 +354,7 @@ impl Value { /// The `top_level` parameter controls whether this invocation is the top-level /// comparison, or a nested value comparison. See /// `//tvix/docs/value-pointer-equality.md` - pub(crate) async fn neo_nix_eq( + pub(crate) async fn nix_eq( self, other: Value, co: GenCo, @@ -530,49 +551,52 @@ 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. - /// - /// Takes a reference to the `VM` to allow forcing thunks during comparison - pub fn nix_eq(&self, other: &Self, vm: &mut VM) -> Result<bool, ErrorKind> { - match (self, other) { - // Trivial comparisons - (Value::Null, Value::Null) => Ok(true), - (Value::Bool(b1), Value::Bool(b2)) => Ok(b1 == b2), - (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), - - (Value::Attrs(_), Value::Attrs(_)) - | (Value::List(_), Value::List(_)) - | (Value::Thunk(_), _) - | (_, Value::Thunk(_)) => Ok(vm.nix_eq(self.clone(), other.clone(), false)?), - - // Everything else is either incomparable (e.g. internal - // types) or false. - _ => Ok(false), - } + /// Internal helper to allow `nix_cmp_ordering` to recurse. + fn nix_cmp_boxed( + self, + other: Self, + co: GenCo, + ) -> Pin<Box<dyn Future<Output = Result<Option<Ordering>, ErrorKind>>>> { + Box::pin(self.nix_cmp_ordering(other, co)) } /// Compare `self` against other using (fallible) Nix ordering semantics. - pub fn nix_cmp(&self, other: &Self, vm: &mut VM) -> Result<Option<Ordering>, ErrorKind> { + /// + /// Note that as this returns an `Option<Ordering>` it can not directly be + /// used as a generator function in the VM. The exact use depends on the + /// callsite, as the meaning is interpreted in different ways e.g. based on + /// the comparison operator used. + /// + /// The function is intended to be used from within other generator + /// functions or `gen!` blocks. + pub async fn nix_cmp_ordering( + self, + other: Self, + co: GenCo, + ) -> 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::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 !vm.nix_eq(l1[i].clone(), l2[i].clone(), true)? { - return l1[i].force(vm)?.nix_cmp(&*l2[i].force(vm)?, vm); + } else if !generators::check_equality( + &co, + l1[i].clone(), + l2[i].clone(), + PointerEquality::AllowAll, + ) + .await? + { + // TODO: do we need to control `top_level` here? + let v1 = generators::request_force(&co, l1[i].clone()).await; + let v2 = generators::request_force(&co, l2[i].clone()).await; + return v1.nix_cmp_boxed(v2, co).await; } } @@ -580,8 +604,8 @@ impl Value { } // different types - (Value::Integer(i1), Value::Float(f2)) => Ok((*i1 as f64).partial_cmp(f2)), - (Value::Float(f1), Value::Integer(i2)) => Ok(f1.partial_cmp(&(*i2 as f64))), + (Value::Integer(i1), Value::Float(f2)) => Ok((i1 as f64).partial_cmp(&f2)), + (Value::Float(f1), Value::Integer(i2)) => Ok(f1.partial_cmp(&(i2 as f64))), // unsupported types (lhs, rhs) => Err(ErrorKind::Incomparable { @@ -591,58 +615,12 @@ impl Value { } } - /// Ensure `self` is forced if it is a thunk, and return a reference to the resulting value. - pub fn force(&self, vm: &mut VM) -> Result<ForceResult, ErrorKind> { - match self { - Self::Thunk(thunk) => { - thunk.force(vm)?; - Ok(ForceResult::ForcedThunk(thunk.value())) - } - _ => Ok(ForceResult::Immediate(self)), + pub async fn force(self, co: GenCo) -> Result<Value, ErrorKind> { + if let Value::Thunk(thunk) = self { + return thunk.force(co).await; } - } - - /// Ensure `self` is *deeply* forced, including all recursive sub-values - pub(crate) fn deep_force( - &self, - vm: &mut VM, - thunk_set: &mut ThunkSet, - ) -> Result<(), ErrorKind> { - match self { - Value::Null - | Value::Bool(_) - | Value::Integer(_) - | Value::Float(_) - | Value::String(_) - | Value::Path(_) - | Value::Closure(_) - | Value::Builtin(_) - | Value::AttrNotFound - | Value::Blueprint(_) - | Value::DeferredUpvalue(_) - | Value::UnresolvedPath(_) => Ok(()), - Value::Attrs(a) => { - for (_, v) in a.iter() { - v.deep_force(vm, thunk_set)?; - } - Ok(()) - } - Value::List(l) => { - for val in l { - val.deep_force(vm, thunk_set)?; - } - Ok(()) - } - Value::Thunk(thunk) => { - if !thunk_set.insert(thunk) { - return Ok(()); - } - thunk.force(vm)?; - let value = thunk.value().clone(); - value.deep_force(vm, thunk_set) - } - } + Ok(self) } /// Explain a value in a human-readable way, e.g. by presenting @@ -835,9 +813,6 @@ fn type_error(expected: &'static str, actual: &Value) -> ErrorKind { #[cfg(test)] mod tests { - use super::*; - use imbl::vector; - mod floats { use crate::value::total_fmt_float; @@ -865,72 +840,4 @@ mod tests { } } } - - mod nix_eq { - use crate::observer::NoOpObserver; - - use super::*; - use proptest::prelude::ProptestConfig; - use test_strategy::proptest; - - #[proptest(ProptestConfig { cases: 5, ..Default::default() })] - fn reflexive(x: Value) { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - assert!(x.nix_eq(&x, &mut vm).unwrap()) - } - - #[proptest(ProptestConfig { cases: 5, ..Default::default() })] - fn symmetric(x: Value, y: Value) { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - assert_eq!( - x.nix_eq(&y, &mut vm).unwrap(), - y.nix_eq(&x, &mut vm).unwrap() - ) - } - - #[proptest(ProptestConfig { cases: 5, ..Default::default() })] - fn transitive(x: Value, y: Value, z: Value) { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - if x.nix_eq(&y, &mut vm).unwrap() && y.nix_eq(&z, &mut vm).unwrap() { - assert!(x.nix_eq(&z, &mut vm).unwrap()) - } - } - - #[test] - fn list_int_float_fungibility() { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - let v1 = Value::List(NixList::from(vector![Value::Integer(1)])); - let v2 = Value::List(NixList::from(vector![Value::Float(1.0)])); - - assert!(v1.nix_eq(&v2, &mut vm).unwrap()) - } - } } diff --git a/tvix/eval/src/value/thunk.rs b/tvix/eval/src/value/thunk.rs index 43adb314a211..42e8ec869ac5 100644 --- a/tvix/eval/src/value/thunk.rs +++ b/tvix/eval/src/value/thunk.rs @@ -28,11 +28,11 @@ use std::{ use serde::Serialize; use crate::{ - errors::{Error, ErrorKind}, + errors::ErrorKind, spans::LightSpan, upvalues::Upvalues, value::Closure, - vm::{Trampoline, TrampolineAction, VM}, + vm::generators::{self, GenCo}, Value, }; @@ -115,78 +115,16 @@ impl Thunk { ))))) } - /// Force a thunk from a context that can't handle trampoline - /// continuations, eg outside the VM's normal execution loop. Calling - /// `force_trampoline()` instead should be preferred whenever possible. - pub fn force(&self, vm: &mut VM) -> Result<(), ErrorKind> { + pub async fn force(self, co: GenCo) -> Result<Value, ErrorKind> { + // If the current thunk is already fully evaluated, return its evaluated + // value. The VM will continue running the code that landed us here. if self.is_forced() { - return Ok(()); - } - - let mut trampoline = Self::force_trampoline(vm, Value::Thunk(self.clone()))?; - loop { - match trampoline.action { - None => (), - Some(TrampolineAction::EnterFrame { - lambda, - upvalues, - arg_count, - light_span: _, - }) => vm.enter_frame(lambda, upvalues, arg_count)?, - } - match trampoline.continuation { - None => break, - Some(cont) => { - trampoline = cont(vm)?; - continue; - } - } - } - vm.pop(); - Ok(()) - } - - /// Evaluate the content of a thunk, potentially repeatedly, until a - /// non-thunk value is returned. - /// - /// When this function returns, the result of one "round" of forcing is left - /// at the top of the stack. This may still be a partially evaluated thunk - /// which must be further run through the trampoline. - pub fn force_trampoline(vm: &mut VM, outer: Value) -> Result<Trampoline, ErrorKind> { - match outer { - Value::Thunk(thunk) => thunk.force_trampoline_self(vm), - v => { - vm.push(v); - Ok(Trampoline::default()) - } - } - } - - /// Analyses `self` and, upon finding a suspended thunk, requests evaluation - /// of the contained code from the VM. Control flow may pass back and forth - /// between this function and the VM multiple times through continuations - /// that call `force_trampoline` again if nested thunks are encountered. - /// - /// This function is entered again by returning a continuation that calls - /// [force_trampoline]. - // When working on this function, care should be taken to ensure that each - // evaluated thunk's *own copy* of its inner representation is replaced by - // evaluated results and blackholes, as appropriate. It is a critical error - // to move the representation of one thunk into another and can lead to - // hard-to-debug performance issues. - // TODO: check Rc count when replacing inner repr, to skip it optionally - fn force_trampoline_self(&self, vm: &mut VM) -> Result<Trampoline, ErrorKind> { - // If the current thunk is already fully evaluated, leave its evaluated - // value on the stack and return an empty trampoline. The VM will - // continue running the code that landed us here. - if self.is_forced() { - vm.push(self.value().clone()); - return Ok(Trampoline::default()); + return Ok(self.value().clone()); } // Begin evaluation of this thunk by marking it as a blackhole, meaning - // that any other trampoline loop round encountering this thunk before - // its evaluation is completed detected an evaluation cycle. + // that any other forcing frame encountering this thunk before its + // evaluation is completed detected an evaluation cycle. let inner = self.0.replace(ThunkRepr::Blackhole); match inner { @@ -195,171 +133,44 @@ impl Thunk { ThunkRepr::Blackhole => Err(ErrorKind::InfiniteRecursion), // If there is a native function stored in the thunk, evaluate it - // and replace this thunk's representation with it. Then bounces off - // the trampoline, to handle the case of the native function - // returning another thunk. + // and replace this thunk's representation with the result. ThunkRepr::Native(native) => { let value = native.0()?; - self.0.replace(ThunkRepr::Evaluated(value)); - let self_clone = self.clone(); - - Ok(Trampoline { - action: None, - continuation: Some(Box::new(move |vm| { - Thunk::force_trampoline(vm, Value::Thunk(self_clone)) - .map_err(|kind| Error::new(kind, todo!("BUG: b/238"))) - })), - }) + + // Force the returned value again, in case the native call + // returned a thunk. + let value = generators::request_force(&co, value).await; + + self.0.replace(ThunkRepr::Evaluated(value.clone())); + Ok(value) } - // When encountering a suspended thunk, construct a trampoline that - // enters the thunk's code in the VM and replaces the thunks - // representation with the evaluated one upon return. + // When encountering a suspended thunk, request that the VM enters + // it and produces the result. // - // Thunks may be nested, so this case initiates another round of - // trampolining to ensure that the returned value is forced. ThunkRepr::Suspended { lambda, upvalues, light_span, } => { - // Clone self to move an Rc pointing to *this* thunk instance - // into the continuation closure. - let self_clone = self.clone(); - - Ok(Trampoline { - // Ask VM to enter frame of this thunk ... - action: Some(TrampolineAction::EnterFrame { - lambda, - upvalues, - arg_count: 0, - light_span: light_span.clone(), - }), - - // ... and replace the inner representation once that is done, - // looping back around to here. - continuation: Some(Box::new(move |vm: &mut VM| { - let should_be_blackhole = - self_clone.0.replace(ThunkRepr::Evaluated(vm.pop())); - debug_assert!(matches!(should_be_blackhole, ThunkRepr::Blackhole)); - - Thunk::force_trampoline(vm, Value::Thunk(self_clone)) - .map_err(|kind| Error::new(kind, light_span.span())) - })), - }) - } + let value = + generators::request_enter_lambda(&co, lambda, upvalues, light_span).await; - // Note by tazjin: I have decided at this point to fully unroll the inner thunk handling - // here, leaving no room for confusion about how inner thunks are handled. This *could* - // be written in a shorter way (for example by using a helper function that handles all - // cases in which inner thunks can trivially be turned into a value), but given that we - // have been bitten by this logic repeatedly, I think it is better to let it be slightly - // verbose for now. - - // If an inner thunk is found and already fully-forced, we can - // short-circuit and replace the representation of self with it. - ThunkRepr::Evaluated(Value::Thunk(ref inner)) if inner.is_forced() => { - self.0.replace(ThunkRepr::Evaluated(inner.value().clone())); - vm.push(inner.value().clone()); - Ok(Trampoline::default()) - } + // This may have returned another thunk, so we need to request + // that the VM forces this value, too. + let value = generators::request_force(&co, value).await; - // Otherwise we handle inner thunks mostly as above, with the - // primary difference that we set the representations of *both* - // thunks in this case. - ThunkRepr::Evaluated(Value::Thunk(ref inner)) => { - // The inner thunk is now under evaluation, mark it as such. - let inner_repr = inner.0.replace(ThunkRepr::Blackhole); - - match inner_repr { - ThunkRepr::Blackhole => Err(ErrorKind::InfiniteRecursion), - - // Same as for the native case above, but results are placed - // in *both* thunks. - ThunkRepr::Native(native) => { - let value = native.0()?; - self.0.replace(ThunkRepr::Evaluated(value.clone())); - inner.0.replace(ThunkRepr::Evaluated(value)); - let self_clone = self.clone(); - - Ok(Trampoline { - action: None, - continuation: Some(Box::new(move |vm| { - Thunk::force_trampoline(vm, Value::Thunk(self_clone)) - .map_err(|kind| Error::new(kind, todo!("BUG: b/238"))) - })), - }) - } - - // Inner suspended thunks are trampolined to the VM, and - // their results written to both thunks in the continuation. - ThunkRepr::Suspended { - lambda, - upvalues, - light_span, - } => { - let self_clone = self.clone(); - let inner_clone = inner.clone(); - - Ok(Trampoline { - // Ask VM to enter frame of this thunk ... - action: Some(TrampolineAction::EnterFrame { - lambda, - upvalues, - arg_count: 0, - light_span: light_span.clone(), - }), - - // ... and replace the inner representations. - continuation: Some(Box::new(move |vm: &mut VM| { - let result = vm.pop(); - - let self_blackhole = - self_clone.0.replace(ThunkRepr::Evaluated(result.clone())); - debug_assert!(matches!(self_blackhole, ThunkRepr::Blackhole)); - - let inner_blackhole = - inner_clone.0.replace(ThunkRepr::Evaluated(result)); - debug_assert!(matches!(inner_blackhole, ThunkRepr::Blackhole)); - - Thunk::force_trampoline(vm, Value::Thunk(self_clone)) - .map_err(|kind| Error::new(kind, light_span.span())) - })), - }) - } - - // If the inner thunk is some arbitrary other value (this is - // almost guaranteed to be another thunk), change our - // representation to the same inner thunk and bounce off the - // trampoline. The inner thunk is changed *back* to the same - // state. - // - // This is safe because we are not cloning the innermost - // thunk's representation, so while the inner thunk will not - // eventually have its representation replaced by _this_ - // trampoline run, we will return the correct representation - // out of here and memoize the innermost thunk. - ThunkRepr::Evaluated(v) => { - self.0.replace(ThunkRepr::Evaluated(v.clone())); - inner.0.replace(ThunkRepr::Evaluated(v)); - let self_clone = self.clone(); - - Ok(Trampoline { - action: None, - continuation: Some(Box::new(move |vm: &mut VM| { - // TODO(tazjin): not sure about this span ... - // let span = vm.current_span(); - Thunk::force_trampoline(vm, Value::Thunk(self_clone)) - .map_err(|kind| Error::new(kind, todo!("BUG: b/238"))) - })), - }) - } - } + self.0.replace(ThunkRepr::Evaluated(value.clone())); + Ok(value) } - // This branch can not occur here, it would have been caught by our - // `self.is_forced()` check above. - ThunkRepr::Evaluated(_) => unreachable!("BUG: definition of Thunk::is_forced changed"), + // If an inner value is found, force it and then update. This is + // most likely an inner thunk, as `Thunk:is_forced` returned false. + ThunkRepr::Evaluated(val) => { + let value = generators::request_force(&co, val).await; + self.0.replace(ThunkRepr::Evaluated(value.clone())); + Ok(value) + } } } @@ -381,7 +192,6 @@ impl Thunk { /// Returns true if forcing this thunk will not change it. pub fn is_forced(&self) -> bool { match *self.0.borrow() { - ThunkRepr::Blackhole => panic!("is_forced() called on a blackholed thunk"), ThunkRepr::Evaluated(Value::Thunk(_)) => false, ThunkRepr::Evaluated(_) => true, _ => false, @@ -452,13 +262,9 @@ impl TotalDisplay for Thunk { return f.write_str("<CYCLE>"); } - match self.0.try_borrow() { - Ok(repr) => match &*repr { - ThunkRepr::Evaluated(v) => v.total_fmt(f, set), - _ => f.write_str("internal[thunk]"), - }, - - _ => f.write_str("internal[thunk]"), + match &*self.0.borrow() { + ThunkRepr::Evaluated(v) => v.total_fmt(f, set), + other => write!(f, "internal[{}]", other.debug_repr()), } } } |