diff options
Diffstat (limited to 'tvix/eval/src/value/thunk.rs')
| -rw-r--r-- | tvix/eval/src/value/thunk.rs | 264 |
1 files changed, 35 insertions, 229 deletions
diff --git a/tvix/eval/src/value/thunk.rs b/tvix/eval/src/value/thunk.rs index 43adb314a2..42e8ec869a 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()), } } } |