feat(tvix/eval): Implement builtins.deepSeq r/5175

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 <tazjin@tvl.su>
Change-Id: Iefddefcf09fae3b6a4d161a5873febcff54b9157
Reviewed-on: https://cl.tvl.fyi/c/depot/+/7000
Tested-by: BuildkiteCI
Reviewed-by: grfn <grfn@gws.fyi>
Reviewed-by: tazjin <tazjin@tvl.su>

10 files changed, 100 insertions, 62 deletions

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
@@ -192,6 +192,16 @@ fn pure_builtins() -> Vec<Builtin> {
             },
         ),
         Builtin::new(
+            "deepSeq",
+            &[true, true],
+            |mut args: Vec<Value>, 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],
             |args: Vec<Value>, vm: &mut VM| arithmetic_op!(&*args[0].force(vm)?, &*args[1].force(vm)?, /),
diff --git a/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-deepseq.exp b/tvix/eval/src/tests/nix_tests/eval-okay-deepseq.exp
index 8d38505c16..8d38505c16 100644
--- a/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-deepseq.exp
+++ b/tvix/eval/src/tests/nix_tests/eval-okay-deepseq.exp
diff --git a/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-deepseq.nix b/tvix/eval/src/tests/nix_tests/eval-okay-deepseq.nix
index 53aa4b1dc2..53aa4b1dc2 100644
--- a/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-deepseq.nix
+++ b/tvix/eval/src/tests/nix_tests/eval-okay-deepseq.nix
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,