//! 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; 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), /// 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, upvalues: Rc, 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 opens the specified file and provides a reader. OpenFile(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, CoercionKind { strong, import_paths, }, ) => write!( f, "{}_{}importing_string_coerce({})", if *strong { "strong" } else { "weak" }, if *import_paths { "" } else { "non_" }, 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::OpenFile(p) => { write!(f, "open_file({})", 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), /// [std::io::Reader] produced by the VM in response to some IO operation. Reader(Box), } 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"), VMResponse::Reader(_) => write!(f, "reader"), } } } pub(crate) type Generator = Gen>>>>; /// Helper function to provide type annotations which are otherwise difficult to /// infer. pub fn pin_generator( f: impl Future> + 'static, ) -> Pin>>> { Box::pin(f) } impl<'o, IO> VM<'o, IO> where IO: AsRef + 'static, { /// 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(&mut self, name: &'static str, span: LightSpan, gen: G) where F: Future> + '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, ) -> EvalResult { // 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_owned_genco(co, span) }); return Ok(false); } // Generator has requested a deep-force. VMRequest::DeepForceValue(value) => { self.reenqueue_generator(name, span.clone(), generator); self.enqueue_generator("deep_force", span.clone(), |co| { value.deep_force(co, span) }); 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_owned_genco(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_owned_genco(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.clone(), |co| { values.0.nix_eq_owned_genco(values.1, co, ptr_eq, span) }); return Ok(false); } VMRequest::StringCoerce(val, kind) => { self.reenqueue_generator(name, span.clone(), generator); self.enqueue_generator("coerce_to_string", span.clone(), |co| { val.coerce_to_string(co, kind, span) }); 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 .as_ref() .import_path(&path) .map_err(|e| ErrorKind::IO { path: Some(path), error: e.into(), }) .with_span(&span, self)?; message = VMResponse::Path(imported); } VMRequest::OpenFile(path) => { let reader = self .io_handle .as_ref() .open(&path) .map_err(|e| ErrorKind::IO { path: Some(path), error: e.into(), }) .with_span(&span, self)?; message = VMResponse::Reader(reader) } VMRequest::PathExists(path) => { let exists = self .io_handle .as_ref() .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 .as_ref() .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_owned_genco(co, span) }); return Ok(false); } VMRequest::ToJson(value) => { self.reenqueue_generator(name, span.clone(), generator); self.enqueue_generator("to_json", span, |co| { value.into_contextful_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; // -- 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(co: &GenCo, mut callable: Value, args: I) -> Value where I: IntoIterator, 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 { 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_contextful_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) -> Value { match co.yield_(VMRequest::DeepForceValue(val)).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, ErrorKind> { match co .yield_(VMRequest::NixEquality(Box::new((a, b)), ptr_eq)) .await { VMResponse::Value(Value::Bool(b)) => Ok(Ok(b)), VMResponse::Value(Value::Catchable(cek)) => Ok(Err(*cek)), 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, upvalues: Rc, 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 { 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 ), } } /// Request that the VM open a [std::io::Read] for the specified file. pub async fn request_open_file(co: &GenCo, path: PathBuf) -> Box { match co.yield_(VMRequest::OpenFile(path)).await { VMResponse::Reader(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, ) -> Result<(serde_json::Value, NixContext), CatchableErrorKind> { match co.yield_(VMRequest::ToJson(value)).await { VMResponse::Value(Value::Json(json_with_ctx)) => Ok(*json_with_ctx), VMResponse::Value(Value::Catchable(cek)) => Err(*cek), 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 { 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) } } }