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/value/thunk.rs | 29 +++++++++++++++++++++++------ 1 file changed, 23 insertions(+), 6 deletions(-) (limited to 'tvix/eval/src/value/thunk.rs') diff --git a/tvix/eval/src/value/thunk.rs b/tvix/eval/src/value/thunk.rs index 818ec0f58aec..7bad7e8777ba 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) + } +} -- cgit 1.4.1