diff options
Diffstat (limited to 'tvix/eval/src/vm/generators.rs')
| -rw-r--r-- | tvix/eval/src/vm/generators.rs | 783 |
1 files changed, 783 insertions, 0 deletions
diff --git a/tvix/eval/src/vm/generators.rs b/tvix/eval/src/vm/generators.rs new file mode 100644 index 000000000000..f9c5786d8f8f --- /dev/null +++ b/tvix/eval/src/vm/generators.rs @@ -0,0 +1,783 @@ +//! This module implements generator logic for the VM. Generators are functions +//! used during evaluation which can suspend their execution during their +//! control flow, and request that the VM do something. +//! +//! This is used to keep the VM's stack size constant even when evaluating +//! deeply nested recursive data structures. +//! +//! We implement generators using the [`genawaiter`] crate. + +use core::pin::Pin; +use genawaiter::rc::Co; +pub use genawaiter::rc::Gen; +use std::fmt::Display; +use std::future::Future; + +use crate::value::{PointerEquality, SharedThunkSet}; +use crate::warnings::{EvalWarning, WarningKind}; +use crate::FileType; +use crate::NixString; + +use super::*; + +// -- Implementation of generic generator logic. + +/// States that a generator can be in while being driven by the VM. +pub(crate) enum GeneratorState { + /// Normal execution of the generator. + Running, + + /// Generator is awaiting the result of a forced value. + AwaitingValue, +} + +/// Messages that can be sent from generators *to* the VM. In most +/// cases, the VM will suspend the generator when receiving a message +/// and enter some other frame to process the request. +/// +/// Responses are returned to generators via the [`GeneratorResponse`] type. +pub enum VMRequest { + /// Request that the VM forces this value. This message is first sent to the + /// VM with the unforced value, then returned to the generator with the + /// forced result. + ForceValue(Value), + + /// Request that the VM deep-forces the value. + DeepForceValue(Value, SharedThunkSet), + + /// Request the value at the given index from the VM's with-stack, in forced + /// state. + /// + /// The value is returned in the `ForceValue` message. + WithValue(usize), + + /// Request the value at the given index from the *captured* with-stack, in + /// forced state. + CapturedWithValue(usize), + + /// Request that the two values be compared for Nix equality. The result is + /// returned in the `ForceValue` message. + NixEquality(Box<(Value, Value)>, PointerEquality), + + /// Push the given value to the VM's stack. This is used to prepare the + /// stack for requesting a function call from the VM. + /// + /// The VM does not respond to this request, so the next message received is + /// `Empty`. + StackPush(Value), + + /// Pop a value from the stack and return it to the generator. + StackPop, + + /// Request that the VM coerces this value to a string. + StringCoerce(Value, CoercionKind), + + /// Request that the VM calls the given value, with arguments already + /// prepared on the stack. Value must already be forced. + Call(Value), + + /// Request a call frame entering the given lambda immediately. This can be + /// used to force thunks. + EnterLambda { + lambda: Rc<Lambda>, + upvalues: Rc<Upvalues>, + light_span: LightSpan, + }, + + /// Emit a runtime warning (already containing a span) through the VM. + EmitWarning(EvalWarning), + + /// Emit a runtime warning through the VM. The span of the current generator + /// is used for the final warning. + EmitWarningKind(WarningKind), + + /// Request a lookup in the VM's import cache, which tracks the + /// thunks yielded by previously imported files. + ImportCacheLookup(PathBuf), + + /// Provide the VM with an imported value for a given path, which + /// it can populate its input cache with. + ImportCachePut(PathBuf, Value), + + /// Request that the VM imports the given path through its I/O interface. + PathImport(PathBuf), + + /// Request that the VM reads the given path to a string. + ReadToString(PathBuf), + + /// Request that the VM checks whether the given path exists. + PathExists(PathBuf), + + /// Request that the VM reads the given path. + ReadDir(PathBuf), + + /// Request a reasonable span from the VM. + Span, + + /// Request evaluation of `builtins.tryEval` from the VM. See + /// [`VM::catch_result`] for an explanation of how this works. + TryForce(Value), + + /// Request serialisation of a value to JSON, according to the + /// slightly odd Nix evaluation rules. + ToJson(Value), +} + +/// Human-readable representation of a generator message, used by observers. +impl Display for VMRequest { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + VMRequest::ForceValue(v) => write!(f, "force_value({})", v.type_of()), + VMRequest::DeepForceValue(v, _) => { + write!(f, "deep_force_value({})", v.type_of()) + } + VMRequest::WithValue(_) => write!(f, "with_value"), + VMRequest::CapturedWithValue(_) => write!(f, "captured_with_value"), + VMRequest::NixEquality(values, ptr_eq) => { + write!( + f, + "nix_eq({}, {}, PointerEquality::{:?})", + values.0.type_of(), + values.1.type_of(), + ptr_eq + ) + } + VMRequest::StackPush(v) => write!(f, "stack_push({})", v.type_of()), + VMRequest::StackPop => write!(f, "stack_pop"), + VMRequest::StringCoerce(v, kind) => match kind { + CoercionKind::Weak => write!(f, "weak_string_coerce({})", v.type_of()), + CoercionKind::Strong => write!(f, "strong_string_coerce({})", v.type_of()), + }, + VMRequest::Call(v) => write!(f, "call({})", v), + VMRequest::EnterLambda { lambda, .. } => { + write!(f, "enter_lambda({:p})", *lambda) + } + VMRequest::EmitWarning(_) => write!(f, "emit_warning"), + VMRequest::EmitWarningKind(_) => write!(f, "emit_warning_kind"), + VMRequest::ImportCacheLookup(p) => { + write!(f, "import_cache_lookup({})", p.to_string_lossy()) + } + VMRequest::ImportCachePut(p, _) => { + write!(f, "import_cache_put({})", p.to_string_lossy()) + } + VMRequest::PathImport(p) => write!(f, "path_import({})", p.to_string_lossy()), + VMRequest::ReadToString(p) => { + write!(f, "read_to_string({})", p.to_string_lossy()) + } + VMRequest::PathExists(p) => write!(f, "path_exists({})", p.to_string_lossy()), + VMRequest::ReadDir(p) => write!(f, "read_dir({})", p.to_string_lossy()), + VMRequest::Span => write!(f, "span"), + VMRequest::TryForce(v) => write!(f, "try_force({})", v.type_of()), + VMRequest::ToJson(v) => write!(f, "to_json({})", v.type_of()), + } + } +} + +/// Responses returned to generators *from* the VM. +pub enum VMResponse { + /// Empty message. Passed to the generator as the first message, + /// or when return values were optional. + Empty, + + /// Value produced by the VM and returned to the generator. + Value(Value), + + /// Path produced by the VM in response to some IO operation. + Path(PathBuf), + + /// VM response with the contents of a directory. + Directory(Vec<(bytes::Bytes, FileType)>), + + /// VM response with a span to use at the current point. + Span(LightSpan), +} + +impl Display for VMResponse { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + VMResponse::Empty => write!(f, "empty"), + VMResponse::Value(v) => write!(f, "value({})", v), + VMResponse::Path(p) => write!(f, "path({})", p.to_string_lossy()), + VMResponse::Directory(d) => write!(f, "dir(len = {})", d.len()), + VMResponse::Span(_) => write!(f, "span"), + } + } +} + +pub(crate) type Generator = + Gen<VMRequest, VMResponse, Pin<Box<dyn Future<Output = Result<Value, ErrorKind>>>>>; + +/// Helper function to provide type annotations which are otherwise difficult to +/// infer. +pub fn pin_generator( + f: impl Future<Output = Result<Value, ErrorKind>> + 'static, +) -> Pin<Box<dyn Future<Output = Result<Value, ErrorKind>>>> { + Box::pin(f) +} + +impl<'o> VM<'o> { + /// Helper function to re-enqueue the current generator while it + /// is awaiting a value. + fn reenqueue_generator(&mut self, name: &'static str, span: LightSpan, generator: Generator) { + self.frames.push(Frame::Generator { + name, + generator, + span, + state: GeneratorState::AwaitingValue, + }); + } + + /// Helper function to enqueue a new generator. + pub(super) fn enqueue_generator<F, G>(&mut self, name: &'static str, span: LightSpan, gen: G) + where + F: Future<Output = Result<Value, ErrorKind>> + 'static, + G: FnOnce(GenCo) -> F, + { + self.frames.push(Frame::Generator { + name, + span, + state: GeneratorState::Running, + generator: Gen::new(|co| pin_generator(gen(co))), + }); + } + + /// Run a generator frame until it yields to the outer control loop, or runs + /// to completion. + /// + /// The return value indicates whether the generator has completed (true), + /// or was suspended (false). + pub(crate) fn run_generator( + &mut self, + name: &'static str, + span: LightSpan, + frame_id: usize, + state: GeneratorState, + mut generator: Generator, + initial_message: Option<VMResponse>, + ) -> EvalResult<bool> { + // Determine what to send to the generator based on its state. + let mut message = match (initial_message, state) { + (Some(msg), _) => msg, + (_, GeneratorState::Running) => VMResponse::Empty, + + // If control returned here, and the generator is + // awaiting a value, send it the top of the stack. + (_, GeneratorState::AwaitingValue) => VMResponse::Value(self.stack_pop()), + }; + + loop { + match generator.resume_with(message) { + // If the generator yields, it contains an instruction + // for what the VM should do. + genawaiter::GeneratorState::Yielded(request) => { + self.observer.observe_generator_request(name, &request); + + match request { + VMRequest::StackPush(value) => { + self.stack.push(value); + message = VMResponse::Empty; + } + + VMRequest::StackPop => { + message = VMResponse::Value(self.stack_pop()); + } + + // Generator has requested a force, which means that + // this function prepares the frame stack and yields + // back to the outer VM loop. + VMRequest::ForceValue(value) => { + self.reenqueue_generator(name, span.clone(), generator); + self.enqueue_generator("force", span.clone(), |co| { + value.force(co, span) + }); + return Ok(false); + } + + // Generator has requested a deep-force. + VMRequest::DeepForceValue(value, thunk_set) => { + self.reenqueue_generator(name, span.clone(), generator); + self.enqueue_generator("deep_force", span, |co| { + value.deep_force(co, thunk_set) + }); + return Ok(false); + } + + // Generator has requested a value from the with-stack. + // Logic is similar to `ForceValue`, except with the + // value being taken from that stack. + VMRequest::WithValue(idx) => { + self.reenqueue_generator(name, span.clone(), generator); + + let value = self.stack[self.with_stack[idx]].clone(); + self.enqueue_generator("force", span.clone(), |co| { + value.force(co, span) + }); + + return Ok(false); + } + + // Generator has requested a value from the *captured* + // with-stack. Logic is same as above, except for the + // value being from that stack. + VMRequest::CapturedWithValue(idx) => { + self.reenqueue_generator(name, span.clone(), generator); + + let call_frame = self.last_call_frame() + .expect("Tvix bug: generator requested captured with-value, but there is no call frame"); + + let value = call_frame.upvalues.with_stack().unwrap()[idx].clone(); + self.enqueue_generator("force", span.clone(), |co| { + value.force(co, span) + }); + + return Ok(false); + } + + VMRequest::NixEquality(values, ptr_eq) => { + let values = *values; + self.reenqueue_generator(name, span.clone(), generator); + self.enqueue_generator("nix_eq", span, |co| { + values.0.nix_eq(values.1, co, ptr_eq) + }); + return Ok(false); + } + + VMRequest::StringCoerce(val, kind) => { + self.reenqueue_generator(name, span.clone(), generator); + self.enqueue_generator("coerce_to_string", span, |co| { + val.coerce_to_string(co, kind) + }); + return Ok(false); + } + + VMRequest::Call(callable) => { + self.reenqueue_generator(name, span.clone(), generator); + self.call_value(span, None, callable)?; + return Ok(false); + } + + VMRequest::EnterLambda { + lambda, + upvalues, + light_span, + } => { + self.reenqueue_generator(name, span, generator); + + self.frames.push(Frame::CallFrame { + span: light_span, + call_frame: CallFrame { + lambda, + upvalues, + ip: CodeIdx(0), + stack_offset: self.stack.len(), + }, + }); + + return Ok(false); + } + + VMRequest::EmitWarning(warning) => { + self.push_warning(warning); + message = VMResponse::Empty; + } + + VMRequest::EmitWarningKind(kind) => { + self.emit_warning(kind); + message = VMResponse::Empty; + } + + VMRequest::ImportCacheLookup(path) => { + if let Some(cached) = self.import_cache.get(path) { + message = VMResponse::Value(cached.clone()); + } else { + message = VMResponse::Empty; + } + } + + VMRequest::ImportCachePut(path, value) => { + self.import_cache.insert(path, value); + message = VMResponse::Empty; + } + + VMRequest::PathImport(path) => { + let imported = self + .io_handle + .import_path(&path) + .map_err(|e| ErrorKind::IO { + path: Some(path), + error: e.into(), + }) + .with_span(&span, self)?; + + message = VMResponse::Path(imported); + } + + VMRequest::ReadToString(path) => { + let content = self + .io_handle + .read_to_string(&path) + .map_err(|e| ErrorKind::IO { + path: Some(path), + error: e.into(), + }) + .with_span(&span, self)?; + + message = VMResponse::Value(Value::String(content.into())) + } + + VMRequest::PathExists(path) => { + let exists = self + .io_handle + .path_exists(&path) + .map_err(|e| ErrorKind::IO { + path: Some(path), + error: e.into(), + }) + .map(Value::Bool) + .with_span(&span, self)?; + + message = VMResponse::Value(exists); + } + + VMRequest::ReadDir(path) => { + let dir = self + .io_handle + .read_dir(&path) + .map_err(|e| ErrorKind::IO { + path: Some(path), + error: e.into(), + }) + .with_span(&span, self)?; + message = VMResponse::Directory(dir); + } + + VMRequest::Span => { + message = VMResponse::Span(self.reasonable_light_span()); + } + + VMRequest::TryForce(value) => { + self.try_eval_frames.push(frame_id); + self.reenqueue_generator(name, span.clone(), generator); + + debug_assert!( + self.frames.len() == frame_id + 1, + "generator should be reenqueued with the same frame ID" + ); + + self.enqueue_generator("force", span.clone(), |co| { + value.force(co, span) + }); + return Ok(false); + } + + VMRequest::ToJson(value) => { + self.reenqueue_generator(name, span.clone(), generator); + self.enqueue_generator("to_json", span, |co| { + value.to_json_generator(co) + }); + return Ok(false); + } + } + } + + // Generator has completed, and its result value should + // be left on the stack. + genawaiter::GeneratorState::Complete(result) => { + let value = result.with_span(&span, self)?; + self.stack.push(value); + return Ok(true); + } + } + } + } +} + +pub type GenCo = Co<VMRequest, VMResponse>; + +// -- Implementation of concrete generator use-cases. + +/// Request that the VM place the given value on its stack. +pub async fn request_stack_push(co: &GenCo, val: Value) { + match co.yield_(VMRequest::StackPush(val)).await { + VMResponse::Empty => {} + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +/// Request that the VM pop a value from the stack and return it to the +/// generator. +pub async fn request_stack_pop(co: &GenCo) -> Value { + match co.yield_(VMRequest::StackPop).await { + VMResponse::Value(value) => value, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +/// Force any value and return the evaluated result from the VM. +pub async fn request_force(co: &GenCo, val: Value) -> Value { + if let Value::Thunk(_) = val { + match co.yield_(VMRequest::ForceValue(val)).await { + VMResponse::Value(value) => value, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } + } else { + val + } +} + +/// Force a value +pub(crate) async fn request_try_force(co: &GenCo, val: Value) -> Value { + if let Value::Thunk(_) = val { + match co.yield_(VMRequest::TryForce(val)).await { + VMResponse::Value(value) => value, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } + } else { + val + } +} + +/// Call the given value as a callable. The argument(s) must already be prepared +/// on the stack. +pub async fn request_call(co: &GenCo, val: Value) -> Value { + let val = request_force(co, val).await; + match co.yield_(VMRequest::Call(val)).await { + VMResponse::Value(value) => value, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +/// Helper function to call the given value with the provided list of arguments. +/// This uses the StackPush and Call messages under the hood. +pub async fn request_call_with<I>(co: &GenCo, mut callable: Value, args: I) -> Value +where + I: IntoIterator<Item = Value>, + I::IntoIter: DoubleEndedIterator, +{ + let mut num_args = 0_usize; + for arg in args.into_iter().rev() { + num_args += 1; + request_stack_push(co, arg).await; + } + + debug_assert!(num_args > 0, "call_with called with an empty list of args"); + + while num_args > 0 { + callable = request_call(co, callable).await; + num_args -= 1; + } + + callable +} + +pub async fn request_string_coerce( + co: &GenCo, + val: Value, + kind: CoercionKind, +) -> Result<NixString, CatchableErrorKind> { + match val { + Value::String(s) => Ok(s), + _ => match co.yield_(VMRequest::StringCoerce(val, kind)).await { + VMResponse::Value(Value::Catchable(c)) => Err(c), + VMResponse::Value(value) => Ok(value + .to_str() + .expect("coerce_to_string always returns a string")), + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + }, + } +} + +/// Deep-force any value and return the evaluated result from the VM. +pub async fn request_deep_force(co: &GenCo, val: Value, thunk_set: SharedThunkSet) -> Value { + match co.yield_(VMRequest::DeepForceValue(val, thunk_set)).await { + VMResponse::Value(value) => value, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +/// Ask the VM to compare two values for equality. +pub(crate) async fn check_equality( + co: &GenCo, + a: Value, + b: Value, + ptr_eq: PointerEquality, +) -> Result<bool, ErrorKind> { + match co + .yield_(VMRequest::NixEquality(Box::new((a, b)), ptr_eq)) + .await + { + VMResponse::Value(value) => value.as_bool(), + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +/// Emit a fully constructed runtime warning. +pub(crate) async fn emit_warning(co: &GenCo, warning: EvalWarning) { + match co.yield_(VMRequest::EmitWarning(warning)).await { + VMResponse::Empty => {} + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +/// Emit a runtime warning with the span of the current generator. +pub async fn emit_warning_kind(co: &GenCo, kind: WarningKind) { + match co.yield_(VMRequest::EmitWarningKind(kind)).await { + VMResponse::Empty => {} + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +/// Request that the VM enter the given lambda. +pub(crate) async fn request_enter_lambda( + co: &GenCo, + lambda: Rc<Lambda>, + upvalues: Rc<Upvalues>, + light_span: LightSpan, +) -> Value { + let msg = VMRequest::EnterLambda { + lambda, + upvalues, + light_span, + }; + + match co.yield_(msg).await { + VMResponse::Value(value) => value, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +/// Request a lookup in the VM's import cache. +pub(crate) async fn request_import_cache_lookup(co: &GenCo, path: PathBuf) -> Option<Value> { + match co.yield_(VMRequest::ImportCacheLookup(path)).await { + VMResponse::Value(value) => Some(value), + VMResponse::Empty => None, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +/// Request that the VM populate its input cache for the given path. +pub(crate) async fn request_import_cache_put(co: &GenCo, path: PathBuf, value: Value) { + match co.yield_(VMRequest::ImportCachePut(path, value)).await { + VMResponse::Empty => {} + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +/// Request that the VM import the given path. +pub(crate) async fn request_path_import(co: &GenCo, path: PathBuf) -> PathBuf { + match co.yield_(VMRequest::PathImport(path)).await { + VMResponse::Path(path) => path, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +pub(crate) async fn request_read_to_string(co: &GenCo, path: PathBuf) -> Value { + match co.yield_(VMRequest::ReadToString(path)).await { + VMResponse::Value(value) => value, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +pub(crate) async fn request_path_exists(co: &GenCo, path: PathBuf) -> Value { + match co.yield_(VMRequest::PathExists(path)).await { + VMResponse::Value(value) => value, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +pub(crate) async fn request_read_dir(co: &GenCo, path: PathBuf) -> Vec<(bytes::Bytes, FileType)> { + match co.yield_(VMRequest::ReadDir(path)).await { + VMResponse::Directory(dir) => dir, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +pub(crate) async fn request_span(co: &GenCo) -> LightSpan { + match co.yield_(VMRequest::Span).await { + VMResponse::Span(span) => span, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +pub(crate) async fn request_to_json(co: &GenCo, value: Value) -> serde_json::Value { + match co.yield_(VMRequest::ToJson(value)).await { + VMResponse::Value(Value::Json(json)) => json, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +/// Call the given value as if it was an attribute set containing a functor. The +/// arguments must already be prepared on the stack when a generator frame from +/// this function is invoked. +/// +pub(crate) async fn call_functor(co: GenCo, value: Value) -> Result<Value, ErrorKind> { + let attrs = value.to_attrs()?; + + match attrs.select("__functor") { + None => Err(ErrorKind::NotCallable("set without `__functor_` attribute")), + Some(functor) => { + // The functor receives the set itself as its first argument and + // needs to be called with it. + let functor = request_force(&co, functor.clone()).await; + let primed = request_call_with(&co, functor, [value]).await; + Ok(request_call(&co, primed).await) + } + } +} |