From d4fa3152e92ef72d9ee050000b1fd4952203e383 Mon Sep 17 00:00:00 2001 From: Griffin Smith Date: Wed, 12 Oct 2022 22:47:23 -0400 Subject: feat(tvix/eval): Implement builtins.deepSeq This is done via a new `deepForce` function on Value. Since values can be cyclical (for example, see the test-case), we need to do some extra work to avoid RefCell borrow errors if we ever hit a graph cycle: While deep-forcing values, we keep a set of thunks that we have already seen and avoid doing any work on the same thunk twice. The set is encapsulated in a separate type to stop potentially invalid pointers from leaking out. Finally, since deep_force is conceptually similar to `VM::force_for_output` (but more suited to usage in eval since it doesn't clone the values) this removes the latter, replacing it with the former. Co-Authored-By: Vincent Ambo Change-Id: Iefddefcf09fae3b6a4d161a5873febcff54b9157 Reviewed-on: https://cl.tvl.fyi/c/depot/+/7000 Tested-by: BuildkiteCI Reviewed-by: grfn Reviewed-by: tazjin --- tvix/eval/src/builtins/mod.rs | 10 ++++ .../eval/src/tests/nix_tests/eval-okay-deepseq.exp | 1 + .../eval/src/tests/nix_tests/eval-okay-deepseq.nix | 1 + .../nix_tests/notyetpassing/eval-okay-deepseq.exp | 1 - .../nix_tests/notyetpassing/eval-okay-deepseq.nix | 1 - .../src/tests/tvix_tests/eval-fail-deepseq.nix | 1 + .../src/tests/tvix_tests/eval-okay-deepseq.exp | 1 + .../src/tests/tvix_tests/eval-okay-deepseq.nix | 1 + tvix/eval/src/value/list.rs | 10 ++++ tvix/eval/src/value/mod.rs | 45 +++++++++++++++ tvix/eval/src/value/thunk.rs | 29 ++++++++-- tvix/eval/src/vm.rs | 65 +++------------------- 12 files changed, 102 insertions(+), 64 deletions(-) create mode 100644 tvix/eval/src/tests/nix_tests/eval-okay-deepseq.exp create mode 100644 tvix/eval/src/tests/nix_tests/eval-okay-deepseq.nix delete mode 100644 tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-deepseq.exp delete mode 100644 tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-deepseq.nix create mode 100644 tvix/eval/src/tests/tvix_tests/eval-fail-deepseq.nix create mode 100644 tvix/eval/src/tests/tvix_tests/eval-okay-deepseq.exp create mode 100644 tvix/eval/src/tests/tvix_tests/eval-okay-deepseq.nix (limited to 'tvix/eval') diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs index 0b5911de85..14eb673f78 100644 --- a/tvix/eval/src/builtins/mod.rs +++ b/tvix/eval/src/builtins/mod.rs @@ -191,6 +191,16 @@ fn pure_builtins() -> Vec { Ok(res.into()) }, ), + Builtin::new( + "deepSeq", + &[true, true], + |mut args: Vec, vm: &mut VM| { + let arg2 = args.pop().unwrap(); + let arg1 = args.pop().unwrap(); + arg1.deep_force(vm, &mut Default::default())?; + Ok(arg2) + }, + ), Builtin::new( "div", &[false, false], diff --git a/tvix/eval/src/tests/nix_tests/eval-okay-deepseq.exp b/tvix/eval/src/tests/nix_tests/eval-okay-deepseq.exp new file mode 100644 index 0000000000..8d38505c16 --- /dev/null +++ b/tvix/eval/src/tests/nix_tests/eval-okay-deepseq.exp @@ -0,0 +1 @@ +456 diff --git a/tvix/eval/src/tests/nix_tests/eval-okay-deepseq.nix b/tvix/eval/src/tests/nix_tests/eval-okay-deepseq.nix new file mode 100644 index 0000000000..53aa4b1dc2 --- /dev/null +++ b/tvix/eval/src/tests/nix_tests/eval-okay-deepseq.nix @@ -0,0 +1 @@ +builtins.deepSeq (let as = { x = 123; y = as; }; in as) 456 diff --git a/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-deepseq.exp b/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-deepseq.exp deleted file mode 100644 index 8d38505c16..0000000000 --- a/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-deepseq.exp +++ /dev/null @@ -1 +0,0 @@ -456 diff --git a/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-deepseq.nix b/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-deepseq.nix deleted file mode 100644 index 53aa4b1dc2..0000000000 --- a/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-deepseq.nix +++ /dev/null @@ -1 +0,0 @@ -builtins.deepSeq (let as = { x = 123; y = as; }; in as) 456 diff --git a/tvix/eval/src/tests/tvix_tests/eval-fail-deepseq.nix b/tvix/eval/src/tests/tvix_tests/eval-fail-deepseq.nix new file mode 100644 index 0000000000..9baa49b063 --- /dev/null +++ b/tvix/eval/src/tests/tvix_tests/eval-fail-deepseq.nix @@ -0,0 +1 @@ +builtins.deepSeq { x = abort "foo"; } 456 diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-deepseq.exp b/tvix/eval/src/tests/tvix_tests/eval-okay-deepseq.exp new file mode 100644 index 0000000000..8d38505c16 --- /dev/null +++ b/tvix/eval/src/tests/tvix_tests/eval-okay-deepseq.exp @@ -0,0 +1 @@ +456 diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-deepseq.nix b/tvix/eval/src/tests/tvix_tests/eval-okay-deepseq.nix new file mode 100644 index 0000000000..53aa4b1dc2 --- /dev/null +++ b/tvix/eval/src/tests/tvix_tests/eval-okay-deepseq.nix @@ -0,0 +1 @@ +builtins.deepSeq (let as = { x = 123; y = as; }; in as) 456 diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs index 3be5d41457..42d91b6b26 100644 --- a/tvix/eval/src/value/list.rs +++ b/tvix/eval/src/value/list.rs @@ -102,3 +102,13 @@ impl IntoIterator for NixList { self.0.into_iter() } } + +impl<'a> IntoIterator for &'a NixList { + type Item = &'a Value; + + type IntoIter = std::slice::Iter<'a, Value>; + + fn into_iter(self) -> Self::IntoIter { + self.0.iter() + } +} diff --git a/tvix/eval/src/value/mod.rs b/tvix/eval/src/value/mod.rs index 78f4f5de67..1dc39d6832 100644 --- a/tvix/eval/src/value/mod.rs +++ b/tvix/eval/src/value/mod.rs @@ -27,6 +27,8 @@ pub use path::canon_path; pub use string::NixString; pub use thunk::Thunk; +use self::thunk::ThunkSet; + #[warn(variant_size_differences)] #[derive(Clone, Debug, PartialEq)] pub enum Value { @@ -341,6 +343,49 @@ impl Value { _ => Ok(ForceResult::Immediate(self)), } } + + /// 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) + } + } + } } impl Display for Value { diff --git a/tvix/eval/src/value/thunk.rs b/tvix/eval/src/value/thunk.rs index 818ec0f58a..7bad7e8777 100644 --- a/tvix/eval/src/value/thunk.rs +++ b/tvix/eval/src/value/thunk.rs @@ -20,6 +20,7 @@ use std::{ cell::{Ref, RefCell, RefMut}, + collections::HashSet, fmt::Display, rc::Rc, }; @@ -86,13 +87,12 @@ impl Thunk { }))) } - /// Evaluate the content of a thunk, potentially repeatedly, until - /// a non-thunk value is returned. + /// Evaluate the content of a thunk, potentially repeatedly, until a + /// non-thunk value is returned. /// - /// This will change the existing thunk (and thus all references - /// to it, providing memoization) through interior mutability. In - /// case of nested thunks, the intermediate thunk representations - /// are replaced. + /// This will change the existing thunk (and thus all references to it, + /// providing memoization) through interior mutability. In case of nested + /// thunks, the intermediate thunk representations are replaced. pub fn force(&self, vm: &mut VM) -> Result<(), ErrorKind> { loop { let mut thunk_mut = self.0.borrow_mut(); @@ -200,3 +200,20 @@ impl Display for Thunk { } } } + +/// A wrapper type for tracking which thunks have already been seen in a +/// context. This is necessary for cycle detection. +/// +/// The inner `HashSet` is not available on the outside, as it would be +/// potentially unsafe to interact with the pointers in the set. +#[derive(Default)] +pub struct ThunkSet(HashSet<*mut ThunkRepr>); + +impl ThunkSet { + /// Check whether the given thunk has already been seen. Will mark the thunk + /// as seen otherwise. + pub fn insert(&mut self, thunk: &Thunk) -> bool { + let ptr: *mut ThunkRepr = thunk.0.as_ptr(); + self.0.insert(ptr) + } +} diff --git a/tvix/eval/src/vm.rs b/tvix/eval/src/vm.rs index 9e25da7d23..75fe8b32ac 100644 --- a/tvix/eval/src/vm.rs +++ b/tvix/eval/src/vm.rs @@ -3,8 +3,6 @@ use std::{ops::DerefMut, path::PathBuf, rc::Rc}; -use codemap::Span; - use crate::{ chunk::Chunk, errors::{Error, ErrorKind, EvalResult}, @@ -858,57 +856,6 @@ impl<'o> VM<'o> { Ok(()) } - /// Strictly evaluate the supplied value for outputting it. This - /// will ensure that lists and attribute sets do not contain - /// chunks which, for users, are displayed in a strange and often - /// unexpected way. - fn force_for_output(&mut self, value: &Value, root_span: Span) -> EvalResult<()> { - match value { - Value::Attrs(attrs) => { - for (_, value) in attrs.iter() { - self.force_for_output(value, root_span)?; - } - Ok(()) - } - - Value::List(list) => list - .iter() - .try_for_each(|elem| self.force_for_output(elem, root_span)), - - Value::Thunk(thunk) => { - // This force is "synthetic", in that there is no - // outer expression from which a top-level span for - // the call can be derived, so we need to set this - // span manually. - thunk.force(self).map_err(|kind| Error { - kind, - span: root_span, - })?; - - let value = thunk.value().clone(); - self.force_for_output(&value, root_span) - } - - // If any of these internal values are encountered here a - // critical error has happened (likely a compiler bug). - Value::AttrNotFound - | Value::Blueprint(_) - | Value::DeferredUpvalue(_) - | Value::UnresolvedPath(_) => { - panic!("tvix bug: internal value left on stack: {:?}", value) - } - - Value::Null - | Value::Bool(_) - | Value::Integer(_) - | Value::Float(_) - | Value::String(_) - | Value::Path(_) - | Value::Closure(_) - | Value::Builtin(_) => Ok(()), - } - } - pub fn call_builtin(&mut self, builtin: Builtin) -> EvalResult<()> { let builtin_name = builtin.name(); self.observer.observe_enter_builtin(builtin_name); @@ -939,8 +886,8 @@ pub fn run_lambda( let mut vm = VM::new(nix_search_path, observer); // Retain the top-level span of the expression in this lambda, as - // synthetic "calls" in force_for_output will otherwise not have a - // span to fall back to. + // synthetic "calls" in deep_force will otherwise not have a span + // to fall back to. // // We exploit the fact that the compiler emits a final instruction // with the span of the entire file for top-level expressions. @@ -948,7 +895,13 @@ pub fn run_lambda( vm.enter_frame(lambda, Upvalues::with_capacity(0), 0)?; let value = vm.pop(); - vm.force_for_output(&value, root_span)?; + + value + .deep_force(&mut vm, &mut Default::default()) + .map_err(|kind| Error { + kind, + span: root_span, + })?; Ok(RuntimeResult { value, -- cgit 1.4.1