feat(tvix/eval): introduce Value::Thunk variant r/4673

Introduces the representation of runtime thunks, that is lazily
evaluated values. Their representation is very similar to closures.

Change-Id: I24d1ab7947c070ae72ca6260a7bbe6198bc8c7c5
Reviewed-on: https://cl.tvl.fyi/c/depot/+/6343
Tested-by: BuildkiteCI
Reviewed-by: sterni <sternenseemann@systemli.org>

2 files changed, 61 insertions, 1 deletions

diff --git a/tvix/eval/src/value/mod.rs b/tvix/eval/src/value/mod.rs
index 2c83948414..f4a67eb8b9 100644
--- a/tvix/eval/src/value/mod.rs
+++ b/tvix/eval/src/value/mod.rs
@@ -8,6 +8,7 @@ mod builtin;
 mod function;
 mod list;
 mod string;
+mod thunk;
 
 use crate::errors::{ErrorKind, EvalResult};
 use crate::opcode::StackIdx;
@@ -16,6 +17,7 @@ pub use builtin::Builtin;
 pub use function::{Closure, Lambda};
 pub use list::NixList;
 pub use string::NixString;
+pub use thunk::Thunk;
 
 #[warn(variant_size_differences)]
 #[derive(Clone, Debug)]
@@ -33,6 +35,7 @@ pub enum Value {
 
     // Internal values that, while they technically exist at runtime,
     // are never returned to or created directly by users.
+    Thunk(Thunk),
     AttrPath(Vec<NixString>),
     AttrNotFound,
     DynamicUpvalueMissing(NixString),
@@ -58,7 +61,8 @@ impl Value {
             Value::Closure(_) | Value::Builtin(_) => "lambda",
 
             // Internal types
-            Value::AttrPath(_)
+            Value::Thunk(_)
+            | Value::AttrPath(_)
             | Value::AttrNotFound
             | Value::DynamicUpvalueMissing(_)
             | Value::Blueprint(_)
@@ -169,6 +173,7 @@ impl Display for Value {
             }
 
             // internal types
+            Value::Thunk(_) => f.write_str("internal[thunk]"),
             Value::AttrPath(path) => write!(f, "internal[attrpath({})]", path.len()),
             Value::AttrNotFound => f.write_str("internal[not found]"),
             Value::Blueprint(_) => f.write_str("internal[blueprint]"),
diff --git a/tvix/eval/src/value/thunk.rs b/tvix/eval/src/value/thunk.rs
new file mode 100644
index 0000000000..15179388dc
--- /dev/null
+++ b/tvix/eval/src/value/thunk.rs
@@ -0,0 +1,55 @@
+//! This module implements the runtime representation of Thunks.
+//!
+//! Thunks are a special kind of Nix value, similar to a 0-argument
+//! closure that yields some value. Thunks are used to implement the
+//! lazy evaluation behaviour of Nix:
+//!
+//! Whenever the compiler determines that an expression should be
+//! evaluated lazily, it creates a thunk instead of compiling the
+//! expression value directly. At any point in the runtime where the
+//! actual value of a thunk is required, it is "forced", meaning that
+//! the encompassing computation takes place and the thunk takes on
+//! its new value.
+//!
+//! Thunks have interior mutability to be able to memoise their
+//! computation. Once a thunk is evaluated, its internal
+//! representation becomes the result of the expression. It is legal
+//! for the runtime to replace a thunk object directly with its value
+//! object, but when forcing a thunk, the runtime *must* mutate the
+//! memoisable slot.
+
+use std::{cell::RefCell, rc::Rc};
+
+use crate::Value;
+
+use super::Lambda;
+
+/// Internal representation of the different states of a thunk.
+#[derive(Debug)]
+enum ThunkRepr {
+    /// Thunk is suspended and awaiting execution.
+    Suspended { lambda: Lambda },
+
+    /// Thunk is closed over some values, suspended and awaiting
+    /// execution.
+    ClosedSuspended {
+        lambda: Lambda,
+        upvalues: Vec<Value>,
+    },
+
+    /// Thunk currently under-evaluation; encountering a blackhole
+    /// value means that infinite recursion has occured.
+    Blackhole,
+
+    /// Fully evaluated thunk.
+    Evaluated(Value),
+}
+
+#[derive(Clone, Debug)]
+pub struct Thunk(Rc<RefCell<ThunkRepr>>);
+
+impl Thunk {
+    pub fn new(lambda: Lambda) -> Self {
+        Thunk(Rc::new(RefCell::new(ThunkRepr::Suspended { lambda })))
+    }
+}