//! 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::{Ref, RefCell, RefMut},
collections::HashSet,
fmt::Debug,
rc::Rc,
};
use serde::Serialize;
use crate::{
errors::{Error, ErrorKind},
spans::LightSpan,
upvalues::Upvalues,
value::Closure,
vm::{Trampoline, TrampolineAction, VM},
Value,
};
use super::{Lambda, TotalDisplay};
/// Internal representation of a suspended native thunk.
struct SuspendedNative(Box<dyn Fn(&mut VM) -> Result<Value, ErrorKind>>);
impl Debug for SuspendedNative {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "SuspendedNative({:p})", self.0)
}
}
/// Internal representation of the different states of a thunk.
///
/// Upvalues must be finalised before leaving the initial state
/// (Suspended or RecursiveClosure). The [`value()`] function may
/// not be called until the thunk is in the final state (Evaluated).
#[derive(Debug)]
enum ThunkRepr {
/// Thunk is closed over some values, suspended and awaiting
/// execution.
Suspended {
lambda: Rc<Lambda>,
upvalues: Rc<Upvalues>,
light_span: LightSpan,
},
/// Thunk is a suspended native computation.
Native(SuspendedNative),
/// Thunk currently under-evaluation; encountering a blackhole
/// value means that infinite recursion has occured.
Blackhole,
/// Fully evaluated thunk.
Evaluated(Value),
}
impl ThunkRepr {
fn debug_repr(&self) -> String {
match self {
ThunkRepr::Evaluated(v) => format!("thunk(val|{})", v),
ThunkRepr::Blackhole => "thunk(blackhole)".to_string(),
ThunkRepr::Native(_) => "thunk(native)".to_string(),
ThunkRepr::Suspended { lambda, .. } => format!("thunk({:p})", *lambda),
}
}
}
/// A thunk is created for any value which requires non-strict
/// evaluation due to self-reference or lazy semantics (or both).
/// Every reference cycle involving `Value`s will contain at least
/// one `Thunk`.
#[derive(Clone, Debug)]
pub struct Thunk(Rc<RefCell<ThunkRepr>>);
impl Thunk {
pub fn new_closure(lambda: Rc<Lambda>) -> Self {
Thunk(Rc::new(RefCell::new(ThunkRepr::Evaluated(Value::Closure(
Rc::new(Closure {
upvalues: Rc::new(Upvalues::with_capacity(lambda.upvalue_count)),
lambda: lambda.clone(),
}),
)))))
}
pub fn new_suspended(lambda: Rc<Lambda>, light_span: LightSpan) -> Self {
Thunk(Rc::new(RefCell::new(ThunkRepr::Suspended {
upvalues: Rc::new(Upvalues::with_capacity(lambda.upvalue_count)),
lambda: lambda.clone(),
light_span,
})))
}
pub fn new_suspended_native(native: Box<dyn Fn(&mut VM) -> Result<Value, ErrorKind>>) -> Self {
Thunk(Rc::new(RefCell::new(ThunkRepr::Native(SuspendedNative(
native,
)))))
}
/// 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> {
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());
}
// 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.
let inner = self.0.replace(ThunkRepr::Blackhole);
match inner {
// If there was already a blackhole in the thunk, this is an
// evaluation cycle.
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.
ThunkRepr::Native(native) => {
let value = native.0(vm)?;
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")))
})),
})
}
// 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.
//
// 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()))
})),
})
}
// 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())
}
// 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(vm)?;
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")))
})),
})
}
}
}
// 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"),
}
}
pub fn finalise(&self, stack: &[Value]) {
self.upvalues_mut().resolve_deferred_upvalues(stack);
}
pub fn is_evaluated(&self) -> bool {
matches!(*self.0.borrow(), ThunkRepr::Evaluated(_))
}
pub fn is_suspended(&self) -> bool {
matches!(
*self.0.borrow(),
ThunkRepr::Suspended { .. } | ThunkRepr::Native(_)
)
}
/// 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,
}
}
/// Returns a reference to the inner evaluated value of a thunk.
/// It is an error to call this on a thunk that has not been
/// forced, or is not otherwise known to be fully evaluated.
// Note: Due to the interior mutability of thunks this is
// difficult to represent in the type system without impacting the
// API too much.
pub fn value(&self) -> Ref<Value> {
Ref::map(self.0.borrow(), |thunk| match thunk {
ThunkRepr::Evaluated(value) => value,
ThunkRepr::Blackhole => panic!("Thunk::value called on a black-holed thunk"),
ThunkRepr::Suspended { .. } | ThunkRepr::Native(_) => {
panic!("Thunk::value called on a suspended thunk")
}
})
}
pub fn upvalues(&self) -> Ref<'_, Upvalues> {
Ref::map(self.0.borrow(), |thunk| match thunk {
ThunkRepr::Suspended { upvalues, .. } => upvalues.as_ref(),
ThunkRepr::Evaluated(Value::Closure(c)) => &c.upvalues,
_ => panic!("upvalues() on non-suspended thunk"),
})
}
pub fn upvalues_mut(&self) -> RefMut<'_, Upvalues> {
RefMut::map(self.0.borrow_mut(), |thunk| match thunk {
ThunkRepr::Suspended { upvalues, .. } => Rc::get_mut(upvalues).unwrap(),
ThunkRepr::Evaluated(Value::Closure(c)) => Rc::get_mut(
&mut Rc::get_mut(c).unwrap().upvalues,
)
.expect(
"upvalues_mut() was called on a thunk which already had multiple references to it",
),
thunk => panic!("upvalues() on non-suspended thunk: {thunk:?}"),
})
}
/// Do not use this without first reading and understanding
/// `tvix/docs/value-pointer-equality.md`.
pub(crate) fn ptr_eq(&self, other: &Self) -> bool {
if Rc::ptr_eq(&self.0, &other.0) {
return true;
}
match &*self.0.borrow() {
ThunkRepr::Evaluated(Value::Closure(c1)) => match &*other.0.borrow() {
ThunkRepr::Evaluated(Value::Closure(c2)) => Rc::ptr_eq(c1, c2),
_ => false,
},
_ => false,
}
}
/// Helper function to format thunks in observer output.
pub(crate) fn debug_repr(&self) -> String {
self.0.borrow().debug_repr()
}
}
impl TotalDisplay for Thunk {
fn total_fmt(&self, f: &mut std::fmt::Formatter<'_>, set: &mut ThunkSet) -> std::fmt::Result {
if !set.insert(self) {
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]"),
}
}
}
impl Serialize for Thunk {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: serde::Serializer,
{
self.value().serialize(serializer)
}
}
/// 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<*const 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: *const ThunkRepr = thunk.0.as_ptr();
self.0.insert(ptr)
}
}
#[derive(Default, Clone)]
pub struct SharedThunkSet(Rc<RefCell<ThunkSet>>);
impl SharedThunkSet {
/// Check whether the given thunk has already been seen. Will mark the thunk
/// as seen otherwise.
pub fn insert(&self, thunk: &Thunk) -> bool {
self.0.borrow_mut().insert(thunk)
}
}
