refactor(tvix/eval): flatten call stack of VM using generators r/5964

Warning: This is probably the biggest refactor in tvix-eval history,
so far.

This replaces all instances of trampolines and recursion during
evaluation of the VM loop with generators. A generator is an
asynchronous function that can be suspended to yield a message (in our
case, vm::generators::GeneratorRequest) and receive a
response (vm::generators::GeneratorResponsee).

The `genawaiter` crate provides an interpreter for generators that can
drive their execution and lets us move control flow between the VM and
suspended generators.

To do this, massive changes have occured basically everywhere in the
code. On a high-level:

1. The VM is now organised around a frame stack. A frame is either a
   call frame (execution of Tvix bytecode) or a generator frame (a
   running or suspended generator).

   The VM has an outer loop that pops a frame off the frame stack, and
   then enters an inner loop either driving the execution of the
   bytecode or the execution of a generator.

   Both types of frames have several branches that can result in the
   frame re-enqueuing itself, and enqueuing some other work (in the
   form of a different frame) on top of itself. The VM will eventually
   resume the frame when everything "above" it has been suspended.

   In this way, the VM's new frame stack takes over much of the work
   that was previously achieved by recursion.

2. All methods previously taking a VM have been refactored into async
   functions that instead emit/receive generator messages for
   communication with the VM.

   Notably, this includes *all* builtins.

This has had some other effects:

- Some test have been removed or commented out, either because they
  tested code that was mostly already dead (nix_eq) or because they
  now require generator scaffolding which we do not have in place for
  tests (yet).

- Because generator functions are technically async (though no async
  IO is involved), we lose the ability to use much of the Rust
  standard library e.g. in builtins. This has led to many algorithms
  being unrolled into iterative versions instead of iterator
  combinations, and things like sorting had to be implemented from scratch.

- Many call sites that previously saw a `Result<..., ErrorKind>`
  bubble up now only see the result value, as the error handling is
  encapsulated within the generator loop.

  This reduces number of places inside of builtin implementations
  where error context can be attached to calls that can fail.
  Currently what we gain in this tradeoff is significantly more
  detailed span information (which we still need to bubble up, this
  commit does not change the error display).

  We'll need to do some analysis later of how useful the errors turn
  out to be and potentially introduce some methods for attaching
  context to a generator frame again.

This change is very difficult to do in stages, as it is very much an
"all or nothing" change that affects huge parts of the codebase. I've
tried to isolate changes that can be isolated into the parent CLs of
this one, but this change is still quite difficult to wrap one's mind
and I'm available to discuss it and explain things to any reviewer.

Fixes: b/238, b/237, b/251 and potentially others.
Change-Id: I39244163ff5bbecd169fe7b274df19262b515699
Reviewed-on: https://cl.tvl.fyi/c/depot/+/8104
Reviewed-by: raitobezarius <tvl@lahfa.xyz>
Reviewed-by: Adam Joseph <adam@westernsemico.com>
Tested-by: BuildkiteCI

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()),
         }
     }
 }