diff options
Diffstat (limited to 'tvix/eval/src')
| -rw-r--r-- | tvix/eval/src/builtins/impure.rs | 32 | ||||
| -rw-r--r-- | tvix/eval/src/builtins/mod.rs | 608 | ||||
| -rw-r--r-- | tvix/eval/src/compiler/import.rs | 164 | ||||
| -rw-r--r-- | tvix/eval/src/compiler/mod.rs | 7 | ||||
| -rw-r--r-- | tvix/eval/src/errors.rs | 1 | ||||
| -rw-r--r-- | tvix/eval/src/lib.rs | 6 | ||||
| -rw-r--r-- | tvix/eval/src/observer.rs | 2 | ||||
| -rw-r--r-- | tvix/eval/src/opcode.rs | 8 | ||||
| -rw-r--r-- | tvix/eval/src/tests/mod.rs | 6 | ||||
| -rw-r--r-- | tvix/eval/src/value/attrs.rs | 67 | ||||
| -rw-r--r-- | tvix/eval/src/value/attrs/tests.rs | 52 | ||||
| -rw-r--r-- | tvix/eval/src/value/builtin.rs | 78 | ||||
| -rw-r--r-- | tvix/eval/src/value/list.rs | 32 | ||||
| -rw-r--r-- | tvix/eval/src/value/mod.rs | 401 | ||||
| -rw-r--r-- | tvix/eval/src/value/thunk.rs | 264 | ||||
| -rw-r--r-- | tvix/eval/src/vm.rs | 1218 | ||||
| -rw-r--r-- | tvix/eval/src/vm/generators.rs | 285 | ||||
| -rw-r--r-- | tvix/eval/src/vm/macros.rs | 70 | ||||
| -rw-r--r-- | tvix/eval/src/vm/mod.rs | 1120 |
19 files changed, 2093 insertions, 2328 deletions
diff --git a/tvix/eval/src/builtins/impure.rs b/tvix/eval/src/builtins/impure.rs index 91dce152e54a..f4bf400338ee 100644 --- a/tvix/eval/src/builtins/impure.rs +++ b/tvix/eval/src/builtins/impure.rs @@ -1,4 +1,5 @@ use builtin_macros::builtins; +use genawaiter::rc::Gen; use smol_str::SmolStr; use std::{ @@ -6,7 +7,13 @@ use std::{ time::{SystemTime, UNIX_EPOCH}, }; -use crate::{errors::ErrorKind, io::FileType, value::NixAttrs, vm::VM, Value}; +use crate::{ + errors::ErrorKind, + io::FileType, + value::NixAttrs, + vm::generators::{self, GenCo}, + Value, +}; #[builtins] mod impure_builtins { @@ -14,21 +21,22 @@ mod impure_builtins { use crate::builtins::coerce_value_to_path; #[builtin("getEnv")] - fn builtin_get_env(_: &mut VM, var: Value) -> Result<Value, ErrorKind> { + async fn builtin_get_env(co: GenCo, var: Value) -> Result<Value, ErrorKind> { Ok(env::var(var.to_str()?).unwrap_or_else(|_| "".into()).into()) } #[builtin("pathExists")] - fn builtin_path_exists(vm: &mut VM, s: Value) -> Result<Value, ErrorKind> { - let path = coerce_value_to_path(&s, vm)?; - vm.io().path_exists(path).map(Value::Bool) + async fn builtin_path_exists(co: GenCo, path: Value) -> Result<Value, ErrorKind> { + let path = coerce_value_to_path(&co, path).await?; + Ok(generators::request_path_exists(&co, path).await) } #[builtin("readDir")] - fn builtin_read_dir(vm: &mut VM, path: Value) -> Result<Value, ErrorKind> { - let path = coerce_value_to_path(&path, vm)?; + async fn builtin_read_dir(co: GenCo, path: Value) -> Result<Value, ErrorKind> { + let path = coerce_value_to_path(&co, path).await?; - let res = vm.io().read_dir(path)?.into_iter().map(|(name, ftype)| { + let dir = generators::request_read_dir(&co, path).await; + let res = dir.into_iter().map(|(name, ftype)| { ( name, Value::String( @@ -47,11 +55,9 @@ mod impure_builtins { } #[builtin("readFile")] - fn builtin_read_file(vm: &mut VM, path: Value) -> Result<Value, ErrorKind> { - let path = coerce_value_to_path(&path, vm)?; - vm.io() - .read_to_string(path) - .map(|s| Value::String(s.into())) + async fn builtin_read_file(co: GenCo, path: Value) -> Result<Value, ErrorKind> { + let path = coerce_value_to_path(&co, path).await?; + Ok(generators::request_read_to_string(&co, path).await) } } diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs index 42b217d55f77..79aff9619847 100644 --- a/tvix/eval/src/builtins/mod.rs +++ b/tvix/eval/src/builtins/mod.rs @@ -3,19 +3,21 @@ //! See //tvix/eval/docs/builtins.md for a some context on the //! available builtins in Nix. +use builtin_macros::builtins; +use genawaiter::rc::Gen; +use regex::Regex; use std::cmp::{self, Ordering}; +use std::collections::VecDeque; use std::collections::{BTreeMap, HashSet}; use std::path::PathBuf; -use builtin_macros::builtins; -use regex::Regex; - use crate::arithmetic_op; +use crate::value::PointerEquality; +use crate::vm::generators::{self, GenCo}; use crate::warnings::WarningKind; use crate::{ - errors::{ErrorKind, EvalResult}, - value::{CoercionKind, NixAttrs, NixList, NixString, Value}, - vm::VM, + errors::ErrorKind, + value::{CoercionKind, NixAttrs, NixList, NixString, SharedThunkSet, Value}, }; use self::versions::{VersionPart, VersionPartsIter}; @@ -37,46 +39,44 @@ pub const CURRENT_PLATFORM: &str = env!("TVIX_CURRENT_SYSTEM"); /// builtin. This coercion can _never_ be performed in a Nix program /// without using builtins (i.e. the trick `path: /. + path` to /// convert from a string to a path wouldn't hit this code). -pub fn coerce_value_to_path(v: &Value, vm: &mut VM) -> Result<PathBuf, ErrorKind> { - let value = v.force(vm)?; - match &*value { - Value::Thunk(t) => coerce_value_to_path(&t.value(), vm), - Value::Path(p) => Ok(p.clone()), - _ => value - .coerce_to_string(CoercionKind::Weak, vm) - .map(|s| PathBuf::from(s.as_str())) - .and_then(|path| { - if path.is_absolute() { - Ok(path) - } else { - Err(ErrorKind::NotAnAbsolutePath(path)) - } - }), +pub async fn coerce_value_to_path(co: &GenCo, v: Value) -> Result<PathBuf, ErrorKind> { + let value = generators::request_force(co, v).await; + if let Value::Path(p) = value { + return Ok(p); + } + + let vs = generators::request_string_coerce(co, value, CoercionKind::Weak).await; + let path = PathBuf::from(vs.as_str()); + if path.is_absolute() { + Ok(path) + } else { + Err(ErrorKind::NotAnAbsolutePath(path)) } } #[builtins] mod pure_builtins { - use std::collections::VecDeque; + use crate::value::PointerEquality; use super::*; #[builtin("abort")] - fn builtin_abort(_vm: &mut VM, message: Value) -> Result<Value, ErrorKind> { + async fn builtin_abort(co: GenCo, message: Value) -> Result<Value, ErrorKind> { Err(ErrorKind::Abort(message.to_str()?.to_string())) } #[builtin("add")] - fn builtin_add(vm: &mut VM, #[lazy] x: Value, #[lazy] y: Value) -> Result<Value, ErrorKind> { - arithmetic_op!(&*x.force(vm)?, &*y.force(vm)?, +) + async fn builtin_add(co: GenCo, x: Value, y: Value) -> Result<Value, ErrorKind> { + arithmetic_op!(&x, &y, +) } #[builtin("all")] - fn builtin_all(vm: &mut VM, pred: Value, list: Value) -> Result<Value, ErrorKind> { + async fn builtin_all(co: GenCo, pred: Value, list: Value) -> Result<Value, ErrorKind> { for value in list.to_list()?.into_iter() { - let pred_result = vm.call_with(&pred, [value])?; + let pred_result = generators::request_call_with(&co, pred.clone(), [value]).await; + let pred_result = generators::request_force(&co, pred_result).await; - if !pred_result.force(vm)?.as_bool()? { + if !pred_result.as_bool()? { return Ok(Value::Bool(false)); } } @@ -85,11 +85,12 @@ mod pure_builtins { } #[builtin("any")] - fn builtin_any(vm: &mut VM, pred: Value, list: Value) -> Result<Value, ErrorKind> { + async fn builtin_any(co: GenCo, pred: Value, list: Value) -> Result<Value, ErrorKind> { for value in list.to_list()?.into_iter() { - let pred_result = vm.call_with(&pred, [value])?; + let pred_result = generators::request_call_with(&co, pred.clone(), [value]).await; + let pred_result = generators::request_force(&co, pred_result).await; - if pred_result.force(vm)?.as_bool()? { + if pred_result.as_bool()? { return Ok(Value::Bool(true)); } } @@ -98,7 +99,7 @@ mod pure_builtins { } #[builtin("attrNames")] - fn builtin_attr_names(_: &mut VM, set: Value) -> Result<Value, ErrorKind> { + async fn builtin_attr_names(co: GenCo, set: Value) -> Result<Value, ErrorKind> { let xs = set.to_attrs()?; let mut output = Vec::with_capacity(xs.len()); @@ -110,7 +111,7 @@ mod pure_builtins { } #[builtin("attrValues")] - fn builtin_attr_values(_: &mut VM, set: Value) -> Result<Value, ErrorKind> { + async fn builtin_attr_values(co: GenCo, set: Value) -> Result<Value, ErrorKind> { let xs = set.to_attrs()?; let mut output = Vec::with_capacity(xs.len()); @@ -122,35 +123,36 @@ mod pure_builtins { } #[builtin("baseNameOf")] - fn builtin_base_name_of(vm: &mut VM, s: Value) -> Result<Value, ErrorKind> { - let s = s.coerce_to_string(CoercionKind::Weak, vm)?; + async fn builtin_base_name_of(co: GenCo, s: Value) -> Result<Value, ErrorKind> { + let s = s.coerce_to_string(co, CoercionKind::Weak).await?.to_str()?; let result: String = s.rsplit_once('/').map(|(_, x)| x).unwrap_or(&s).into(); Ok(result.into()) } #[builtin("bitAnd")] - fn builtin_bit_and(_: &mut VM, x: Value, y: Value) -> Result<Value, ErrorKind> { + async fn builtin_bit_and(co: GenCo, x: Value, y: Value) -> Result<Value, ErrorKind> { Ok(Value::Integer(x.as_int()? & y.as_int()?)) } #[builtin("bitOr")] - fn builtin_bit_or(_: &mut VM, x: Value, y: Value) -> Result<Value, ErrorKind> { + async fn builtin_bit_or(co: GenCo, x: Value, y: Value) -> Result<Value, ErrorKind> { Ok(Value::Integer(x.as_int()? | y.as_int()?)) } #[builtin("bitXor")] - fn builtin_bit_xor(_: &mut VM, x: Value, y: Value) -> Result<Value, ErrorKind> { + async fn builtin_bit_xor(co: GenCo, x: Value, y: Value) -> Result<Value, ErrorKind> { Ok(Value::Integer(x.as_int()? ^ y.as_int()?)) } #[builtin("catAttrs")] - fn builtin_cat_attrs(vm: &mut VM, key: Value, list: Value) -> Result<Value, ErrorKind> { + async fn builtin_cat_attrs(co: GenCo, key: Value, list: Value) -> Result<Value, ErrorKind> { let key = key.to_str()?; let list = list.to_list()?; let mut output = vec![]; for item in list.into_iter() { - let set = item.force(vm)?.to_attrs()?; + let set = generators::request_force(&co, item).await.to_attrs()?; + if let Some(value) = set.select(key.as_str()) { output.push(value.clone()); } @@ -160,12 +162,12 @@ mod pure_builtins { } #[builtin("ceil")] - fn builtin_ceil(_: &mut VM, double: Value) -> Result<Value, ErrorKind> { + async fn builtin_ceil(co: GenCo, double: Value) -> Result<Value, ErrorKind> { Ok(Value::Integer(double.as_float()?.ceil() as i64)) } #[builtin("compareVersions")] - fn builtin_compare_versions(_: &mut VM, x: Value, y: Value) -> Result<Value, ErrorKind> { + async fn builtin_compare_versions(co: GenCo, x: Value, y: Value) -> Result<Value, ErrorKind> { let s1 = x.to_str()?; let s1 = VersionPartsIter::new_for_cmp(s1.as_str()); let s2 = y.to_str()?; @@ -179,34 +181,32 @@ mod pure_builtins { } #[builtin("concatLists")] - fn builtin_concat_lists(vm: &mut VM, lists: Value) -> Result<Value, ErrorKind> { - let list = lists.to_list()?; - let lists = list - .into_iter() - .map(|elem| { - let value = elem.force(vm)?; - value.to_list() - }) - .collect::<Result<Vec<NixList>, ErrorKind>>()?; + async fn builtin_concat_lists(co: GenCo, lists: Value) -> Result<Value, ErrorKind> { + let mut out = imbl::Vector::new(); - Ok(Value::List(NixList::from( - lists.into_iter().flatten().collect::<imbl::Vector<Value>>(), - ))) + for value in lists.to_list()? { + let list = generators::request_force(&co, value).await.to_list()?; + out.extend(list.into_iter()); + } + + Ok(Value::List(out.into())) } #[builtin("concatMap")] - fn builtin_concat_map(vm: &mut VM, f: Value, list: Value) -> Result<Value, ErrorKind> { + async fn builtin_concat_map(co: GenCo, f: Value, list: Value) -> Result<Value, ErrorKind> { let list = list.to_list()?; let mut res = imbl::Vector::new(); for val in list { - res.extend(vm.call_with(&f, [val])?.force(vm)?.to_list()?); + let out = generators::request_call_with(&co, f.clone(), [val]).await; + let out = generators::request_force(&co, out).await; + res.extend(out.to_list()?); } Ok(Value::List(res.into())) } #[builtin("concatStringsSep")] - fn builtin_concat_strings_sep( - vm: &mut VM, + async fn builtin_concat_strings_sep( + co: GenCo, separator: Value, list: Value, ) -> Result<Value, ErrorKind> { @@ -217,25 +217,27 @@ mod pure_builtins { if i != 0 { res.push_str(&separator); } - res.push_str(&val.force(vm)?.coerce_to_string(CoercionKind::Weak, vm)?); + let s = generators::request_string_coerce(&co, val, CoercionKind::Weak).await; + res.push_str(s.as_str()); } Ok(res.into()) } #[builtin("deepSeq")] - fn builtin_deep_seq(vm: &mut VM, x: Value, y: Value) -> Result<Value, ErrorKind> { - x.deep_force(vm, &mut Default::default())?; + async fn builtin_deep_seq(co: GenCo, x: Value, y: Value) -> Result<Value, ErrorKind> { + generators::request_deep_force(&co, x, SharedThunkSet::default()).await; Ok(y) } #[builtin("div")] - fn builtin_div(vm: &mut VM, #[lazy] x: Value, #[lazy] y: Value) -> Result<Value, ErrorKind> { - arithmetic_op!(&*x.force(vm)?, &*y.force(vm)?, /) + async fn builtin_div(co: GenCo, x: Value, y: Value) -> Result<Value, ErrorKind> { + arithmetic_op!(&x, &y, /) } #[builtin("dirOf")] - fn builtin_dir_of(vm: &mut VM, s: Value) -> Result<Value, ErrorKind> { - let str = s.coerce_to_string(CoercionKind::Weak, vm)?; + async fn builtin_dir_of(co: GenCo, s: Value) -> Result<Value, ErrorKind> { + let is_path = s.is_path(); + let str = s.coerce_to_string(co, CoercionKind::Weak).await?.to_str()?; let result = str .rsplit_once('/') .map(|(x, _)| match x { @@ -243,7 +245,7 @@ mod pure_builtins { _ => x, }) .unwrap_or("."); - if s.is_path() { + if is_path { Ok(Value::Path(result.into())) } else { Ok(result.into()) @@ -251,9 +253,9 @@ mod pure_builtins { } #[builtin("elem")] - fn builtin_elem(vm: &mut VM, x: Value, xs: Value) -> Result<Value, ErrorKind> { + async fn builtin_elem(co: GenCo, x: Value, xs: Value) -> Result<Value, ErrorKind> { for val in xs.to_list()? { - if vm.nix_eq(val, x.clone(), true)? { + if generators::check_equality(&co, x.clone(), val, PointerEquality::AllowAll).await? { return Ok(true.into()); } } @@ -261,7 +263,7 @@ mod pure_builtins { } #[builtin("elemAt")] - fn builtin_elem_at(_: &mut VM, xs: Value, i: Value) -> Result<Value, ErrorKind> { + async fn builtin_elem_at(co: GenCo, xs: Value, i: Value) -> Result<Value, ErrorKind> { let xs = xs.to_list()?; let i = i.as_int()?; if i < 0 { @@ -275,57 +277,68 @@ mod pure_builtins { } #[builtin("filter")] - fn builtin_filter(vm: &mut VM, pred: Value, list: Value) -> Result<Value, ErrorKind> { + async fn builtin_filter(co: GenCo, pred: Value, list: Value) -> Result<Value, ErrorKind> { let list: NixList = list.to_list()?; + let mut out = imbl::Vector::new(); - list.into_iter() - .filter_map(|elem| { - let result = match vm.call_with(&pred, [elem.clone()]) { - Err(err) => return Some(Err(err)), - Ok(result) => result, - }; - - // Must be assigned to a local to avoid a borrowcheck - // failure related to the ForceResult destructor. - let result = match result.force(vm) { - Err(err) => Some(Err(vm.error(err))), - Ok(value) => match value.as_bool() { - Ok(true) => Some(Ok(elem)), - Ok(false) => None, - Err(err) => Some(Err(vm.error(err))), - }, - }; - - result - }) - .collect::<Result<imbl::Vector<Value>, _>>() - .map(|list| Value::List(NixList::from(list))) - .map_err(Into::into) + for value in list { + let result = generators::request_call_with(&co, pred.clone(), [value.clone()]).await; + + if generators::request_force(&co, result).await.as_bool()? { + out.push_back(value); + } + } + + Ok(Value::List(out.into())) + // list.into_iter() + // .filter_map(|elem| { + // let result = match vm.call_with(&pred, [elem.clone()]) { + // Err(err) => return Some(Err(err)), + // Ok(result) => result, + // }; + + // // Must be assigned to a local to avoid a borrowcheck + // // failure related to the ForceResult destructor. + // let result = match result.force(vm) { + // Err(err) => Some(Err(vm.error(err))), + // Ok(value) => match value.as_bool() { + // Ok(true) => Some(Ok(elem)), + // Ok(false) => None, + // Err(err) => Some(Err(vm.error(err))), + // }, + // }; + + // result + // }) + // .collect::<Result<imbl::Vector<Value>, _>>() + // .map(|list| Value::List(NixList::from(list))) + // .map_err(Into::into) } #[builtin("floor")] - fn builtin_floor(_: &mut VM, double: Value) -> Result<Value, ErrorKind> { + async fn builtin_floor(co: GenCo, double: Value) -> Result<Value, ErrorKind> { Ok(Value::Integer(double.as_float()?.floor() as i64)) } #[builtin("foldl'")] - fn builtin_foldl( - vm: &mut VM, + async fn builtin_foldl( + co: GenCo, op: Value, - #[lazy] mut nul: Value, + #[lazy] nul: Value, list: Value, ) -> Result<Value, ErrorKind> { + let mut nul = nul; let list = list.to_list()?; for val in list { - nul = vm.call_with(&op, [nul, val])?; - nul.force(vm)?; + nul = generators::request_call_with(&co, op.clone(), [nul, val]).await; + nul = generators::request_force(&co, nul).await; } Ok(nul) } #[builtin("functionArgs")] - fn builtin_function_args(_: &mut VM, f: Value) -> Result<Value, ErrorKind> { + async fn builtin_function_args(co: GenCo, f: Value) -> Result<Value, ErrorKind> { let lambda = &f.as_closure()?.lambda(); let formals = if let Some(formals) = &lambda.formals { formals @@ -338,87 +351,88 @@ mod pure_builtins { } #[builtin("fromJSON")] - fn builtin_from_json(_: &mut VM, json: Value) -> Result<Value, ErrorKind> { + async fn builtin_from_json(co: GenCo, json: Value) -> Result<Value, ErrorKind> { let json_str = json.to_str()?; serde_json::from_str(&json_str).map_err(|err| err.into()) } #[builtin("toJSON")] - fn builtin_to_json(vm: &mut VM, val: Value) -> Result<Value, ErrorKind> { + async fn builtin_to_json(co: GenCo, val: Value) -> Result<Value, ErrorKind> { // All thunks need to be evaluated before serialising, as the - // data structure is fully traversed by the Serializer (which - // does not have a `VM` available). - val.deep_force(vm, &mut Default::default())?; - + // data structure is fully traversed by the Serializer. + let val = generators::request_deep_force(&co, val, SharedThunkSet::default()).await; let json_str = serde_json::to_string(&val)?; Ok(json_str.into()) } #[builtin("fromTOML")] - fn builtin_from_toml(_: &mut VM, toml: Value) -> Result<Value, ErrorKind> { + async fn builtin_from_toml(co: GenCo, toml: Value) -> Result<Value, ErrorKind> { let toml_str = toml.to_str()?; toml::from_str(&toml_str).map_err(|err| err.into()) } #[builtin("genericClosure")] - fn builtin_generic_closure(vm: &mut VM, input: Value) -> Result<Value, ErrorKind> { + async fn builtin_generic_closure(co: GenCo, input: Value) -> Result<Value, ErrorKind> { let attrs = input.to_attrs()?; // The work set is maintained as a VecDeque because new items // are popped from the front. - let mut work_set: VecDeque<Value> = attrs - .select_required("startSet")? - .force(vm)? - .to_list()? - .into_iter() - .collect(); + let mut work_set: VecDeque<Value> = + generators::request_force(&co, attrs.select_required("startSet")?.clone()) + .await + .to_list()? + .into_iter() + .collect(); let operator = attrs.select_required("operator")?; let mut res = imbl::Vector::new(); let mut done_keys: Vec<Value> = vec![]; - let mut insert_key = |k: Value, vm: &mut VM| -> Result<bool, ErrorKind> { - for existing in &done_keys { - if existing.nix_eq(&k, vm)? { - return Ok(false); - } - } - done_keys.push(k); - Ok(true) - }; - while let Some(val) = work_set.pop_front() { - let attrs = val.force(vm)?.to_attrs()?; + let val = generators::request_force(&co, val).await; + let attrs = val.to_attrs()?; let key = attrs.select_required("key")?; - if !insert_key(key.clone(), vm)? { + if !bgc_insert_key(&co, key.clone(), &mut done_keys).await? { continue; } res.push_back(val.clone()); - let op_result = vm.call_with(operator, Some(val))?.force(vm)?.to_list()?; - work_set.extend(op_result.into_iter()); + let op_result = generators::request_force( + &co, + generators::request_call_with(&co, operator.clone(), [val]).await, + ) + .await; + + work_set.extend(op_result.to_list()?.into_iter()); } Ok(Value::List(NixList::from(res))) } #[builtin("genList")] - fn builtin_gen_list(vm: &mut VM, generator: Value, length: Value) -> Result<Value, ErrorKind> { + async fn builtin_gen_list( + co: GenCo, + generator: Value, + length: Value, + ) -> Result<Value, ErrorKind> { + let mut out = imbl::Vector::<Value>::new(); let len = length.as_int()?; - (0..len) - .map(|i| vm.call_with(&generator, [i.into()])) - .collect::<Result<imbl::Vector<Value>, _>>() - .map(|list| Value::List(NixList::from(list))) - .map_err(Into::into) + + for i in 0..len { + let val = generators::request_call_with(&co, generator.clone(), [i.into()]).await; + out.push_back(val); + } + + Ok(Value::List(out.into())) } #[builtin("getAttr")] - fn builtin_get_attr(_: &mut VM, key: Value, set: Value) -> Result<Value, ErrorKind> { + async fn builtin_get_attr(co: GenCo, key: Value, set: Value) -> Result<Value, ErrorKind> { let k = key.to_str()?; let xs = set.to_attrs()?; @@ -431,10 +445,16 @@ mod pure_builtins { } #[builtin("groupBy")] - fn builtin_group_by(vm: &mut VM, f: Value, list: Value) -> Result<Value, ErrorKind> { + async fn builtin_group_by(co: GenCo, f: Value, list: Value) -> Result<Value, ErrorKind> { let mut res: BTreeMap<NixString, imbl::Vector<Value>> = BTreeMap::new(); for val in list.to_list()? { - let key = vm.call_with(&f, [val.clone()])?.force(vm)?.to_str()?; + let key = generators::request_force( + &co, + generators::request_call_with(&co, f.clone(), [val.clone()]).await, + ) + .await + .to_str()?; + res.entry(key) .or_insert_with(imbl::Vector::new) .push_back(val); @@ -446,7 +466,7 @@ mod pure_builtins { } #[builtin("hasAttr")] - fn builtin_has_attr(_: &mut VM, key: Value, set: Value) -> Result<Value, ErrorKind> { + async fn builtin_has_attr(co: GenCo, key: Value, set: Value) -> Result<Value, ErrorKind> { let k = key.to_str()?; let xs = set.to_attrs()?; @@ -454,7 +474,7 @@ mod pure_builtins { } #[builtin("head")] - fn builtin_head(_: &mut VM, list: Value) -> Result<Value, ErrorKind> { + async fn builtin_head(co: GenCo, list: Value) -> Result<Value, ErrorKind> { match list.to_list()?.get(0) { Some(x) => Ok(x.clone()), None => Err(ErrorKind::IndexOutOfBounds { index: 0 }), @@ -462,7 +482,7 @@ mod pure_builtins { } #[builtin("intersectAttrs")] - fn builtin_intersect_attrs(_: &mut VM, x: Value, y: Value) -> Result<Value, ErrorKind> { + async fn builtin_intersect_attrs(co: GenCo, x: Value, y: Value) -> Result<Value, ErrorKind> { let attrs1 = x.to_attrs()?; let attrs2 = y.to_attrs()?; let res = attrs2.iter().filter_map(|(k, v)| { @@ -475,89 +495,76 @@ mod pure_builtins { Ok(Value::attrs(NixAttrs::from_iter(res))) } - // For `is*` predicates we force manually, as Value::force also unwraps any Thunks - #[builtin("isAttrs")] - fn builtin_is_attrs(vm: &mut VM, #[lazy] x: Value) -> Result<Value, ErrorKind> { - let value = x.force(vm)?; - Ok(Value::Bool(matches!(*value, Value::Attrs(_)))) + async fn builtin_is_attrs(co: GenCo, value: Value) -> Result<Value, ErrorKind> { + Ok(Value::Bool(matches!(value, Value::Attrs(_)))) } #[builtin("isBool")] - fn builtin_is_bool(vm: &mut VM, #[lazy] x: Value) -> Result<Value, ErrorKind> { - let value = x.force(vm)?; - Ok(Value::Bool(matches!(*value, Value::Bool(_)))) + async fn builtin_is_bool(co: GenCo, value: Value) -> Result<Value, ErrorKind> { + Ok(Value::Bool(matches!(value, Value::Bool(_)))) } #[builtin("isFloat")] - fn builtin_is_float(vm: &mut VM, #[lazy] x: Value) -> Result<Value, ErrorKind> { - let value = x.force(vm)?; - Ok(Value::Bool(matches!(*value, Value::Float(_)))) + async fn builtin_is_float(co: GenCo, value: Value) -> Result<Value, ErrorKind> { + Ok(Value::Bool(matches!(value, Value::Float(_)))) } #[builtin("isFunction")] - fn builtin_is_function(vm: &mut VM, #[lazy] x: Value) -> Result<Value, ErrorKind> { - let value = x.force(vm)?; + async fn builtin_is_function(co: GenCo, value: Value) -> Result<Value, ErrorKind> { Ok(Value::Bool(matches!( - *value, + value, Value::Closure(_) | Value::Builtin(_) ))) } #[builtin("isInt")] - fn builtin_is_int(vm: &mut VM, #[lazy] x: Value) -> Result<Value, ErrorKind> { - let value = x.force(vm)?; - Ok(Value::Bool(matches!(*value, Value::Integer(_)))) + async fn builtin_is_int(co: GenCo, value: Value) -> Result<Value, ErrorKind> { + Ok(Value::Bool(matches!(value, Value::Integer(_)))) } #[builtin("isList")] - fn builtin_is_list(vm: &mut VM, #[lazy] x: Value) -> Result<Value, ErrorKind> { - let value = x.force(vm)?; - Ok(Value::Bool(matches!(*value, Value::List(_)))) + async fn builtin_is_list(co: GenCo, value: Value) -> Result<Value, ErrorKind> { + Ok(Value::Bool(matches!(value, Value::List(_)))) } #[builtin("isNull")] - fn builtin_is_null(vm: &mut VM, #[lazy] x: Value) -> Result<Value, ErrorKind> { - let value = x.force(vm)?; - Ok(Value::Bool(matches!(*value, Value::Null))) + async fn builtin_is_null(co: GenCo, value: Value) -> Result<Value, ErrorKind> { + Ok(Value::Bool(matches!(value, Value::Null))) } #[builtin("isPath")] - fn builtin_is_path(vm: &mut VM, #[lazy] x: Value) -> Result<Value, ErrorKind> { - let value = x.force(vm)?; - Ok(Value::Bool(matches!(*value, Value::Path(_)))) + async fn builtin_is_path(co: GenCo, value: Value) -> Result<Value, ErrorKind> { + Ok(Value::Bool(matches!(value, Value::Path(_)))) } #[builtin("isString")] - fn builtin_is_string(vm: &mut VM, #[lazy] x: Value) -> Result<Value, ErrorKind> { - let value = x.force(vm)?; - Ok(Value::Bool(matches!(*value, Value::String(_)))) + async fn builtin_is_string(co: GenCo, value: Value) -> Result<Value, ErrorKind> { + Ok(Value::Bool(matches!(value, Value::String(_)))) } #[builtin("length")] - fn builtin_length(_: &mut VM, list: Value) -> Result<Value, ErrorKind> { + async fn builtin_length(co: GenCo, list: Value) -> Result<Value, ErrorKind> { Ok(Value::Integer(list.to_list()?.len() as i64)) } #[builtin("lessThan")] - fn builtin_less_than( - vm: &mut VM, - #[lazy] x: Value, - #[lazy] y: Value, - ) -> Result<Value, ErrorKind> { + async fn builtin_less_than(co: GenCo, x: Value, y: Value) -> Result<Value, ErrorKind> { Ok(Value::Bool(matches!( - x.force(vm)?.nix_cmp(&*y.force(vm)?, vm)?, + x.nix_cmp_ordering(y, co).await?, Some(Ordering::Less) ))) } #[builtin("listToAttrs")] - fn builtin_list_to_attrs(vm: &mut VM, list: Value) -> Result<Value, ErrorKind> { + async fn builtin_list_to_attrs(co: GenCo, list: Value) -> Result<Value, ErrorKind> { let list = list.to_list()?; let mut map = BTreeMap::new(); for val in list { - let attrs = val.force(vm)?.to_attrs()?; - let name = attrs.select_required("name")?.force(vm)?.to_str()?; + let attrs = generators::request_force(&co, val).await.to_attrs()?; + let name = generators::request_force(&co, attrs.select_required("name")?.clone()) + .await + .to_str()?; let value = attrs.select_required("value")?.clone(); // Map entries earlier in the list take precedence over entries later in the list map.entry(name).or_insert(value); @@ -566,32 +573,41 @@ mod pure_builtins { } #[builtin("map")] - fn builtin_map(vm: &mut VM, f: Value, list: Value) -> Result<Value, ErrorKind> { - let list: NixList = list.to_list()?; + async fn builtin_map(co: GenCo, f: Value, list: Value) -> Result<Value, ErrorKind> { + let mut out = imbl::Vector::<Value>::new(); - list.into_iter() - .map(|val| vm.call_with(&f, [val])) - .collect::<Result<imbl::Vector<Value>, _>>() - .map(|list| Value::List(NixList::from(list))) - .map_err(Into::into) + for val in list.to_list()? { + let result = generators::request_call_with(&co, f.clone(), [val]).await; + out.push_back(result) + } + + Ok(Value::List(out.into())) } #[builtin("mapAttrs")] - fn builtin_map_attrs(vm: &mut VM, f: Value, attrs: Value) -> Result<Value, ErrorKind> { + async fn builtin_map_attrs(co: GenCo, f: Value, attrs: Value) -> Result<Value, ErrorKind> { let attrs = attrs.to_attrs()?; - let res = - attrs - .as_ref() - .into_iter() - .flat_map(|(key, value)| -> EvalResult<(NixString, Value)> { - let value = vm.call_with(&f, [key.clone().into(), value.clone()])?; - Ok((key.to_owned(), value)) - }); - Ok(Value::attrs(NixAttrs::from_iter(res))) + let mut out = imbl::OrdMap::new(); + + for (key, value) in attrs.into_iter() { + let result = + generators::request_call_with(&co, f.clone(), [key.clone().into(), value]).await; + out.insert(key, result); + } + + // let res = + // attrs + // .as_ref() + // .into_iter() + // .flat_map(|(key, value)| -> EvalResult<(NixString, Value)> { + // let value = vm.call_with(&f, [key.clone().into(), value.clone()])?; + // Ok((key.to_owned(), value)) + // }); + Ok(Value::attrs(out.into())) } #[builtin("match")] - fn builtin_match(_: &mut VM, regex: Value, str: Value) -> Result<Value, ErrorKind> { + async fn builtin_match(co: GenCo, regex: Value, str: Value) -> Result<Value, ErrorKind> { let s = str.to_str()?; let re = regex.to_str()?; let re: Regex = Regex::new(&format!("^{}$", re.as_str())).unwrap(); @@ -608,12 +624,12 @@ mod pure_builtins { } #[builtin("mul")] - fn builtin_mul(vm: &mut VM, #[lazy] x: Value, #[lazy] y: Value) -> Result<Value, ErrorKind> { - arithmetic_op!(&*x.force(vm)?, &*y.force(vm)?, *) + async fn builtin_mul(co: GenCo, x: Value, y: Value) -> Result<Value, ErrorKind> { + arithmetic_op!(&x, &y, *) } #[builtin("parseDrvName")] - fn builtin_parse_drv_name(_vm: &mut VM, s: Value) -> Result<Value, ErrorKind> { + async fn builtin_parse_drv_name(co: GenCo, s: Value) -> Result<Value, ErrorKind> { // This replicates cppnix's (mis?)handling of codepoints // above U+007f following 0x2d ('-') let s = s.to_str()?; @@ -636,16 +652,17 @@ mod pure_builtins { [("name", core::str::from_utf8(name)?), ("version", version)].into_iter(), ))) } + #[builtin("partition")] - fn builtin_partition(vm: &mut VM, pred: Value, list: Value) -> Result<Value, ErrorKind> { + async fn builtin_partition(co: GenCo, pred: Value, list: Value) -> Result<Value, ErrorKind> { let mut right: imbl::Vector<Value> = Default::default(); let mut wrong: imbl::Vector<Value> = Default::default(); let list: NixList = list.to_list()?; for elem in list { - let result = vm.call_with(&pred, [elem.clone()])?; + let result = generators::request_call_with(&co, pred.clone(), [elem.clone()]).await; - if result.force(vm)?.as_bool()? { + if generators::request_force(&co, result).await.as_bool()? { right.push_back(elem); } else { wrong.push_back(elem); @@ -661,7 +678,11 @@ mod pure_builtins { } #[builtin("removeAttrs")] - fn builtin_remove_attrs(_: &mut VM, attrs: Value, keys: Value) -> Result<Value, ErrorKind> { + async fn builtin_remove_attrs( + co: GenCo, + attrs: Value, + keys: Value, + ) -> Result<Value, ErrorKind> { let attrs = attrs.to_attrs()?; let keys = keys .to_list()? @@ -679,16 +700,22 @@ mod pure_builtins { } #[builtin("replaceStrings")] - fn builtin_replace_strings( - vm: &mut VM, + async fn builtin_replace_strings( + co: GenCo, from: Value, to: Value, s: Value, ) -> Result<Value, ErrorKind> { let from = from.to_list()?; - from.force_elements(vm)?; + for val in &from { + generators::request_force(&co, val.clone()).await; + } + let to = to.to_list()?; - to.force_elements(vm)?; + for val in &to { + generators::request_force(&co, val.clone()).await; + } + let string = s.to_str()?; let mut res = String::new(); @@ -755,14 +782,14 @@ mod pure_builtins { } #[builtin("seq")] - fn builtin_seq(_: &mut VM, _x: Value, y: Value) -> Result<Value, ErrorKind> { + async fn builtin_seq(co: GenCo, _x: Value, y: Value) -> Result<Value, ErrorKind> { // The builtin calling infra has already forced both args for us, so // we just return the second and ignore the first Ok(y) } #[builtin("split")] - fn builtin_split(_: &mut VM, regex: Value, str: Value) -> Result<Value, ErrorKind> { + async fn builtin_split(co: GenCo, regex: Value, str: Value) -> Result<Value, ErrorKind> { let s = str.to_str()?; let text = s.as_str(); let re = regex.to_str()?; @@ -798,51 +825,14 @@ mod pure_builtins { } #[builtin("sort")] - fn builtin_sort(vm: &mut VM, comparator: Value, list: Value) -> Result<Value, ErrorKind> { - // TODO: the bound on the sort function in - // `imbl::Vector::sort_by` is `Fn(...)`, which means that we can - // not use the mutable VM inside of its closure, hence the - // dance via `Vec`. I think this is just an unnecessarily - // restrictive bound in `im`, not a functional requirement. - let mut list = list.to_list()?.into_iter().collect::<Vec<_>>(); - - // Used to let errors "escape" from the sorting closure. If anything - // ends up setting an error, it is returned from this function. - let mut error: Option<ErrorKind> = None; - - list.sort_by(|lhs, rhs| { - let result = vm - .call_with(&comparator, [lhs.clone(), rhs.clone()]) - .map_err(|err| ErrorKind::ThunkForce(Box::new(err))) - .and_then(|v| v.force(vm)?.as_bool()); - - match (&error, result) { - // The contained closure only returns a "less - // than?"-boolean, no way to yield "equal". - (None, Ok(true)) => Ordering::Less, - (None, Ok(false)) => Ordering::Greater, - - // Closest thing to short-circuiting out if an error was - // thrown. - (Some(_), _) => Ordering::Equal, - - // Propagate the error if one was encountered. - (_, Err(e)) => { - error = Some(e); - Ordering::Equal - } - } - }); - - match error { - #[allow(deprecated)] // imbl::Vector usage prevented by its API - None => Ok(Value::List(NixList::from_vec(list))), - Some(e) => Err(e), - } + async fn builtin_sort(co: GenCo, comparator: Value, list: Value) -> Result<Value, ErrorKind> { + let mut list = list.to_list()?; + list.sort_by(&co, comparator).await?; + Ok(Value::List(list)) } #[builtin("splitVersion")] - fn builtin_split_version(_: &mut VM, s: Value) -> Result<Value, ErrorKind> { + async fn builtin_split_version(co: GenCo, s: Value) -> Result<Value, ErrorKind> { let s = s.to_str()?; let s = VersionPartsIter::new(s.as_str()); @@ -858,20 +848,20 @@ mod pure_builtins { } #[builtin("stringLength")] - fn builtin_string_length(vm: &mut VM, #[lazy] s: Value) -> Result<Value, ErrorKind> { + async fn builtin_string_length(co: GenCo, #[lazy] s: Value) -> Result<Value, ErrorKind> { // also forces the value - let s = s.coerce_to_string(CoercionKind::Weak, vm)?; - Ok(Value::Integer(s.as_str().len() as i64)) + let s = s.coerce_to_string(co, CoercionKind::Weak).await?; + Ok(Value::Integer(s.to_str()?.as_str().len() as i64)) } #[builtin("sub")] - fn builtin_sub(vm: &mut VM, #[lazy] x: Value, #[lazy] y: Value) -> Result<Value, ErrorKind> { - arithmetic_op!(&*x.force(vm)?, &*y.force(vm)?, -) + async fn builtin_sub(co: GenCo, x: Value, y: Value) -> Result<Value, ErrorKind> { + arithmetic_op!(&x, &y, -) } #[builtin("substring")] - fn builtin_substring( - _: &mut VM, + async fn builtin_substring( + co: GenCo, start: Value, len: Value, s: Value, @@ -903,7 +893,7 @@ mod pure_builtins { } #[builtin("tail")] - fn builtin_tail(_: &mut VM, list: Value) -> Result<Value, ErrorKind> { + async fn builtin_tail(co: GenCo, list: Value) -> Result<Value, ErrorKind> { let xs = list.to_list()?; if xs.is_empty() { @@ -915,34 +905,32 @@ mod pure_builtins { } #[builtin("throw")] - fn builtin_throw(_: &mut VM, message: Value) -> Result<Value, ErrorKind> { + async fn builtin_throw(co: GenCo, message: Value) -> Result<Value, ErrorKind> { Err(ErrorKind::Throw(message.to_str()?.to_string())) } #[builtin("toString")] - fn builtin_to_string(vm: &mut VM, #[lazy] x: Value) -> Result<Value, ErrorKind> { + async fn builtin_to_string(co: GenCo, #[lazy] x: Value) -> Result<Value, ErrorKind> { // coerce_to_string forces for us - x.coerce_to_string(CoercionKind::Strong, vm) - .map(Value::String) + x.coerce_to_string(co, CoercionKind::Strong).await } #[builtin("toXML")] - fn builtin_to_xml(vm: &mut VM, value: Value) -> Result<Value, ErrorKind> { - value.deep_force(vm, &mut Default::default())?; + async fn builtin_to_xml(co: GenCo, value: Value) -> Result<Value, ErrorKind> { + let value = generators::request_deep_force(&co, value, SharedThunkSet::default()).await; let mut buf: Vec<u8> = vec![]; to_xml::value_to_xml(&mut buf, &value)?; Ok(String::from_utf8(buf)?.into()) } #[builtin("placeholder")] - fn builtin_placeholder(vm: &mut VM, #[lazy] _: Value) -> Result<Value, ErrorKind> { - // TODO(amjoseph) - vm.emit_warning(WarningKind::NotImplemented("builtins.placeholder")); + async fn builtin_placeholder(co: GenCo, #[lazy] _x: Value) -> Result<Value, ErrorKind> { + generators::emit_warning(&co, WarningKind::NotImplemented("builtins.placeholder")).await; Ok("<builtins.placeholder-is-not-implemented-in-tvix-yet>".into()) } #[builtin("trace")] - fn builtin_trace(_: &mut VM, message: Value, value: Value) -> Result<Value, ErrorKind> { + async fn builtin_trace(co: GenCo, message: Value, value: Value) -> Result<Value, ErrorKind> { // TODO(grfn): `trace` should be pluggable and capturable, probably via a method on // the VM println!("trace: {} :: {}", message, message.type_of()); @@ -950,31 +938,48 @@ mod pure_builtins { } #[builtin("toPath")] - fn builtin_to_path(vm: &mut VM, #[lazy] s: Value) -> Result<Value, ErrorKind> { - let path: Value = crate::value::canon_path(coerce_value_to_path(&s, vm)?).into(); - Ok(path.coerce_to_string(CoercionKind::Weak, vm)?.into()) + async fn builtin_to_path(co: GenCo, s: Value) -> Result<Value, ErrorKind> { + let path: Value = crate::value::canon_path(coerce_value_to_path(&co, s).await?).into(); + Ok(path.coerce_to_string(co, CoercionKind::Weak).await?) } #[builtin("tryEval")] - fn builtin_try_eval(vm: &mut VM, #[lazy] e: Value) -> Result<Value, ErrorKind> { - let res = match e.force(vm) { - Ok(value) => [("value", (*value).clone()), ("success", true.into())], - Err(e) if e.is_catchable() => [("value", false.into()), ("success", false.into())], - Err(e) => return Err(e), + async fn builtin_try_eval(co: GenCo, #[lazy] e: Value) -> Result<Value, ErrorKind> { + let res = match generators::request_try_force(&co, e).await { + Some(value) => [("value", value), ("success", true.into())], + None => [("value", false.into()), ("success", false.into())], }; + Ok(Value::attrs(NixAttrs::from_iter(res.into_iter()))) } #[builtin("typeOf")] - fn builtin_type_of(vm: &mut VM, #[lazy] x: Value) -> Result<Value, ErrorKind> { - // We force manually here because it also unwraps the Thunk - // representation, if any. - // TODO(sterni): it'd be nice if we didn't have to worry about this - let value = x.force(vm)?; - Ok(Value::String(value.type_of().into())) + async fn builtin_type_of(co: GenCo, x: Value) -> Result<Value, ErrorKind> { + Ok(Value::String(x.type_of().into())) } } +/// Internal helper function for genericClosure, determining whether a +/// value has been seen before. +async fn bgc_insert_key(co: &GenCo, key: Value, done: &mut Vec<Value>) -> Result<bool, ErrorKind> { + for existing in done.iter() { + if generators::check_equality( + co, + existing.clone(), + key.clone(), + // TODO(tazjin): not actually sure which semantics apply here + PointerEquality::ForbidAll, + ) + .await? + { + return Ok(false); + } + } + + done.push(key); + Ok(true) +} + /// The set of standard pure builtins in Nix, mostly concerned with /// data structure manipulation (string, attrs, list, etc. functions). pub fn pure_builtins() -> Vec<(&'static str, Value)> { @@ -999,32 +1004,37 @@ pub fn pure_builtins() -> Vec<(&'static str, Value)> { mod placeholder_builtins { use super::*; - #[builtin("addErrorContext")] - fn builtin_add_error_context( - vm: &mut VM, - #[lazy] _context: Value, - #[lazy] val: Value, - ) -> Result<Value, ErrorKind> { - vm.emit_warning(WarningKind::NotImplemented("builtins.addErrorContext")); - Ok(val) - } - #[builtin("unsafeDiscardStringContext")] - fn builtin_unsafe_discard_string_context( - _: &mut VM, + async fn builtin_unsafe_discard_string_context( + _: GenCo, #[lazy] s: Value, ) -> Result<Value, ErrorKind> { // Tvix does not manually track contexts, and this is a no-op for us. Ok(s) } + #[builtin("addErrorContext")] + async fn builtin_add_error_context( + co: GenCo, + #[lazy] _context: Value, + #[lazy] val: Value, + ) -> Result<Value, ErrorKind> { + generators::emit_warning(&co, WarningKind::NotImplemented("builtins.addErrorContext")) + .await; + Ok(val) + } + #[builtin("unsafeGetAttrPos")] - fn builtin_unsafe_get_attr_pos( - vm: &mut VM, + async fn builtin_unsafe_get_attr_pos( + co: GenCo, _name: Value, _attrset: Value, ) -> Result<Value, ErrorKind> { - vm.emit_warning(WarningKind::NotImplemented("builtins.unsafeGetAttrsPos")); + generators::emit_warning( + &co, + WarningKind::NotImplemented("builtins.unsafeGetAttrsPos"), + ) + .await; let res = [ ("line", 42.into()), ("col", 42.into()), diff --git a/tvix/eval/src/compiler/import.rs b/tvix/eval/src/compiler/import.rs index 3a8847f2cbb4..467fc256afc6 100644 --- a/tvix/eval/src/compiler/import.rs +++ b/tvix/eval/src/compiler/import.rs @@ -5,21 +5,98 @@ //! compiler and VM state (such as the [`crate::SourceCode`] //! instance, or observers). +use super::GlobalsMap; +use genawaiter::rc::Gen; use std::rc::Weak; use crate::{ + builtins::coerce_value_to_path, + generators::pin_generator, observer::NoOpObserver, - value::{Builtin, BuiltinArgument, Thunk}, - vm::VM, + value::{Builtin, Thunk}, + vm::generators::{self, GenCo}, ErrorKind, SourceCode, Value, }; -use super::GlobalsMap; -use crate::builtins::coerce_value_to_path; +async fn import_impl( + co: GenCo, + globals: Weak<GlobalsMap>, + source: SourceCode, + mut args: Vec<Value>, +) -> Result<Value, ErrorKind> { + let mut path = coerce_value_to_path(&co, args.pop().unwrap()).await?; + + if path.is_dir() { + path.push("default.nix"); + } + + if let Some(cached) = generators::request_import_cache_lookup(&co, path.clone()).await { + return Ok(cached); + } + + // TODO(tazjin): make this return a string directly instead + let contents = generators::request_read_to_string(&co, path.clone()) + .await + .to_str()? + .as_str() + .to_string(); + + let parsed = rnix::ast::Root::parse(&contents); + let errors = parsed.errors(); + let file = source.add_file(path.to_string_lossy().to_string(), contents); + + if !errors.is_empty() { + return Err(ErrorKind::ImportParseError { + path, + file, + errors: errors.to_vec(), + }); + } + + let result = crate::compiler::compile( + &parsed.tree().expr().unwrap(), + Some(path.clone()), + file, + // The VM must ensure that a strong reference to the globals outlives + // any self-references (which are weak) embedded within the globals. If + // the expect() below panics, it means that did not happen. + globals + .upgrade() + .expect("globals dropped while still in use"), + &mut NoOpObserver::default(), + ) + .map_err(|err| ErrorKind::ImportCompilerError { + path: path.clone(), + errors: vec![err], + })?; + + if !result.errors.is_empty() { + return Err(ErrorKind::ImportCompilerError { + path, + errors: result.errors, + }); + } + + // TODO: emit not just the warning kind, hmm + // for warning in result.warnings { + // vm.push_warning(warning); + // } + + // Compilation succeeded, we can construct a thunk from whatever it spat + // out and return that. + let res = Value::Thunk(Thunk::new_suspended( + result.lambda, + generators::request_span(&co).await, + )); + + generators::request_import_cache_put(&co, path, res.clone()).await; + + Ok(res) +} -/// Constructs and inserts the `import` builtin. This builtin is special in that -/// it needs to capture the [crate::SourceCode] structure to correctly track -/// source code locations while invoking a compiler. +/// Constructs the `import` builtin. This builtin is special in that +/// it needs to capture the [crate::SourceCode] structure to correctly +/// track source code locations while invoking a compiler. // TODO: need to be able to pass through a CompilationObserver, too. // TODO: can the `SourceCode` come from the compiler? pub(super) fn builtins_import(globals: &Weak<GlobalsMap>, source: SourceCode) -> Builtin { @@ -31,75 +108,10 @@ pub(super) fn builtins_import(globals: &Weak<GlobalsMap>, source: SourceCode) -> Builtin::new( "import", - &[BuiltinArgument { - strict: true, - name: "path", - }], - None, - move |mut args: Vec<Value>, vm: &mut VM| { - let mut path = coerce_value_to_path(&args.pop().unwrap(), vm)?; - if path.is_dir() { - path.push("default.nix"); - } - - let current_span = vm.current_light_span(); - - if let Some(cached) = vm.import_cache.get(&path) { - return Ok(cached.clone()); - } - - let contents = vm.io().read_to_string(path.clone())?; - - let parsed = rnix::ast::Root::parse(&contents); - let errors = parsed.errors(); - - let file = source.add_file(path.to_string_lossy().to_string(), contents); - - if !errors.is_empty() { - return Err(ErrorKind::ImportParseError { - path, - file, - errors: errors.to_vec(), - }); - } - - let result = crate::compiler::compile( - &parsed.tree().expr().unwrap(), - Some(path.clone()), - file, - // The VM must ensure that a strong reference to the - // globals outlives any self-references (which are - // weak) embedded within the globals. If the - // expect() below panics, it means that did not - // happen. - globals - .upgrade() - .expect("globals dropped while still in use"), - &mut NoOpObserver::default(), - ) - .map_err(|err| ErrorKind::ImportCompilerError { - path: path.clone(), - errors: vec![err], - })?; - - if !result.errors.is_empty() { - return Err(ErrorKind::ImportCompilerError { - path, - errors: result.errors, - }); - } - - // Compilation succeeded, we can construct a thunk from whatever it spat - // out and return that. - let res = Value::Thunk(Thunk::new_suspended(result.lambda, current_span)); - - vm.import_cache.insert(path, res.clone()); - - for warning in result.warnings { - vm.push_warning(warning); - } - - Ok(res) + Some("Import the given file and return the Nix value it evaluates to"), + 1, + move |args| { + Gen::new(|co| pin_generator(import_impl(co, globals.clone(), source.clone(), args))) }, ) } diff --git a/tvix/eval/src/compiler/mod.rs b/tvix/eval/src/compiler/mod.rs index 69c232926b41..80e1cd27c953 100644 --- a/tvix/eval/src/compiler/mod.rs +++ b/tvix/eval/src/compiler/mod.rs @@ -1021,6 +1021,12 @@ impl Compiler<'_> { // lambda as a constant. let mut compiled = self.contexts.pop().unwrap(); + // Emit an instruction to inform the VM that the chunk has ended. + compiled + .lambda + .chunk + .push_op(OpCode::OpReturn, self.span_for(node)); + // Capturing the with stack counts as an upvalue, as it is // emitted as an upvalue data instruction. if compiled.captures_with_stack { @@ -1433,6 +1439,7 @@ pub fn compile( // unevaluated state (though in practice, a value *containing* a // thunk might be returned). c.emit_force(expr); + c.push_op(OpCode::OpReturn, &root_span); let lambda = Rc::new(c.contexts.pop().unwrap().lambda); c.observer.observe_compiled_toplevel(&lambda); diff --git a/tvix/eval/src/errors.rs b/tvix/eval/src/errors.rs index 5000afed947f..ec697fa84288 100644 --- a/tvix/eval/src/errors.rs +++ b/tvix/eval/src/errors.rs @@ -365,7 +365,6 @@ to a missing value in the attribute set(s) included via `with`."#, ErrorKind::NotCoercibleToString { kind, from } => { let kindly = match kind { - CoercionKind::ThunksOnly => "thunksonly", CoercionKind::Strong => "strongly", CoercionKind::Weak => "weakly", }; diff --git a/tvix/eval/src/lib.rs b/tvix/eval/src/lib.rs index a8e3d70f2e30..adf38b4bc411 100644 --- a/tvix/eval/src/lib.rs +++ b/tvix/eval/src/lib.rs @@ -52,13 +52,11 @@ pub use crate::errors::{AddContext, Error, ErrorKind, EvalResult}; pub use crate::io::{DummyIO, EvalIO, FileType}; pub use crate::pretty_ast::pretty_print_expr; pub use crate::source::SourceCode; -pub use crate::vm::VM; +pub use crate::vm::{generators, VM}; pub use crate::warnings::{EvalWarning, WarningKind}; pub use builtin_macros; -pub use crate::value::{ - Builtin, BuiltinArgument, CoercionKind, NixAttrs, NixList, NixString, Value, -}; +pub use crate::value::{Builtin, CoercionKind, NixAttrs, NixList, NixString, Value}; #[cfg(feature = "impure")] pub use crate::io::StdIO; diff --git a/tvix/eval/src/observer.rs b/tvix/eval/src/observer.rs index 533182f09531..7dc3ac1cd6d6 100644 --- a/tvix/eval/src/observer.rs +++ b/tvix/eval/src/observer.rs @@ -11,9 +11,9 @@ use std::rc::Rc; use tabwriter::TabWriter; use crate::chunk::Chunk; +use crate::generators::GeneratorRequest; use crate::opcode::{CodeIdx, OpCode}; use crate::value::Lambda; -use crate::vm::generators::GeneratorRequest; use crate::SourceCode; use crate::Value; diff --git a/tvix/eval/src/opcode.rs b/tvix/eval/src/opcode.rs index 445b994b04d8..130e242668d6 100644 --- a/tvix/eval/src/opcode.rs +++ b/tvix/eval/src/opcode.rs @@ -154,6 +154,14 @@ pub enum OpCode { /// index (which must be a Value::Thunk) after the scope is fully bound. OpFinalise(StackIdx), + /// Final instruction emitted in a chunk. Does not have an + /// inherent effect, but can simplify VM logic as a marker in some + /// cases. + /// + /// Can be thought of as "returning" the value to the parent + /// frame, hence the name. + OpReturn, + // [`OpClosure`], [`OpThunkSuspended`], and [`OpThunkClosure`] have a // variable number of arguments to the instruction, which is // represented here by making their data part of the opcodes. diff --git a/tvix/eval/src/tests/mod.rs b/tvix/eval/src/tests/mod.rs index aeec75b2ae9d..b998600cda43 100644 --- a/tvix/eval/src/tests/mod.rs +++ b/tvix/eval/src/tests/mod.rs @@ -10,12 +10,12 @@ mod one_offs; mod mock_builtins { //! Builtins which are required by language tests, but should not //! actually exist in //tvix/eval. + use crate::generators::GenCo; use crate::*; + use genawaiter::rc::Gen; #[builtin("derivation")] - fn builtin_derivation(vm: &mut VM, input: Value) -> Result<Value, ErrorKind> { - vm.emit_warning(WarningKind::NotImplemented("builtins.derivation")); - + async fn builtin_derivation(co: GenCo, input: Value) -> Result<Value, ErrorKind> { let input = input.to_attrs()?; let attrs = input.update(NixAttrs::from_iter( [ diff --git a/tvix/eval/src/value/attrs.rs b/tvix/eval/src/value/attrs.rs index b9c5adba19b8..64a1dc035b54 100644 --- a/tvix/eval/src/value/attrs.rs +++ b/tvix/eval/src/value/attrs.rs @@ -13,7 +13,6 @@ use serde::ser::SerializeMap; use serde::{Deserialize, Serialize}; use crate::errors::ErrorKind; -use crate::vm::VM; use super::string::NixString; use super::thunk::ThunkSet; @@ -394,72 +393,6 @@ impl NixAttrs { pub(crate) fn from_kv(name: Value, value: Value) -> Self { NixAttrs(AttrsRep::KV { name, value }) } - - /// Compare `self` against `other` for equality using Nix equality semantics - pub fn nix_eq(&self, other: &Self, vm: &mut VM) -> Result<bool, ErrorKind> { - match (&self.0, &other.0) { - (AttrsRep::Empty, AttrsRep::Empty) => Ok(true), - - // It is possible to create an empty attribute set that - // has Map representation like so: ` { ${null} = 1; }`. - // - // Preventing this would incur a cost on all attribute set - // construction (we'd have to check the actual number of - // elements after key construction). In practice this - // probably does not happen, so it's better to just bite - // the bullet and implement this branch. - (AttrsRep::Empty, AttrsRep::Im(map)) | (AttrsRep::Im(map), AttrsRep::Empty) => { - Ok(map.is_empty()) - } - - // Other specialised representations (KV ...) definitely - // do not match `Empty`. - (AttrsRep::Empty, _) | (_, AttrsRep::Empty) => Ok(false), - - ( - AttrsRep::KV { - name: n1, - value: v1, - }, - AttrsRep::KV { - name: n2, - value: v2, - }, - ) => Ok(n1.nix_eq(n2, vm)? && v1.nix_eq(v2, vm)?), - - (AttrsRep::Im(map), AttrsRep::KV { name, value }) - | (AttrsRep::KV { name, value }, AttrsRep::Im(map)) => { - if map.len() != 2 { - return Ok(false); - } - - if let (Some(m_name), Some(m_value)) = - (map.get(&NixString::NAME), map.get(&NixString::VALUE)) - { - return Ok(name.nix_eq(m_name, vm)? && value.nix_eq(m_value, vm)?); - } - - Ok(false) - } - - (AttrsRep::Im(m1), AttrsRep::Im(m2)) => { - if m1.len() != m2.len() { - return Ok(false); - } - - for (k, v1) in m1 { - if let Some(v2) = m2.get(k) { - if !v1.nix_eq(v2, vm)? { - return Ok(false); - } - } else { - return Ok(false); - } - } - Ok(true) - } - } - } } /// In Nix, name/value attribute pairs are frequently constructed from diff --git a/tvix/eval/src/value/attrs/tests.rs b/tvix/eval/src/value/attrs/tests.rs index ccf8dc7c10e0..39ac55b6799a 100644 --- a/tvix/eval/src/value/attrs/tests.rs +++ b/tvix/eval/src/value/attrs/tests.rs @@ -1,57 +1,5 @@ use super::*; -mod nix_eq { - use crate::observer::NoOpObserver; - - use super::*; - use proptest::prelude::ProptestConfig; - use test_strategy::proptest; - - #[proptest(ProptestConfig { cases: 2, ..Default::default() })] - fn reflexive(x: NixAttrs) { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - assert!(x.nix_eq(&x, &mut vm).unwrap()) - } - - #[proptest(ProptestConfig { cases: 2, ..Default::default() })] - fn symmetric(x: NixAttrs, y: NixAttrs) { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - assert_eq!( - x.nix_eq(&y, &mut vm).unwrap(), - y.nix_eq(&x, &mut vm).unwrap() - ) - } - - #[proptest(ProptestConfig { cases: 2, ..Default::default() })] - fn transitive(x: NixAttrs, y: NixAttrs, z: NixAttrs) { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - if x.nix_eq(&y, &mut vm).unwrap() && y.nix_eq(&z, &mut vm).unwrap() { - assert!(x.nix_eq(&z, &mut vm).unwrap()) - } - } -} - #[test] fn test_empty_attrs() { let attrs = NixAttrs::construct(0, vec![]).expect("empty attr construction should succeed"); diff --git a/tvix/eval/src/value/builtin.rs b/tvix/eval/src/value/builtin.rs index c7fc33903d96..0577111030a2 100644 --- a/tvix/eval/src/value/builtin.rs +++ b/tvix/eval/src/value/builtin.rs @@ -3,7 +3,7 @@ //! //! Builtins are directly backed by Rust code operating on Nix values. -use crate::{errors::ErrorKind, vm::VM}; +use crate::vm::generators::Generator; use super::Value; @@ -12,40 +12,38 @@ use std::{ rc::Rc, }; -/// Trait for closure types of builtins implemented directly by -/// backing Rust code. +/// Trait for closure types of builtins. /// -/// Builtins declare their arity and are passed a vector with the -/// right number of arguments. Additionally, as they might have to -/// force the evaluation of thunks, they are passed a reference to the -/// current VM which they can use for forcing a value. +/// Builtins are expected to yield a generator which can be run by the VM to +/// produce the final value. /// -/// Errors returned from a builtin will be annotated with the location -/// of the call to the builtin. -pub trait BuiltinFn: Fn(Vec<Value>, &mut VM) -> Result<Value, ErrorKind> {} -impl<F: Fn(Vec<Value>, &mut VM) -> Result<Value, ErrorKind>> BuiltinFn for F {} - -/// Description of a single argument passed to a builtin -pub struct BuiltinArgument { - /// Whether the argument should be forced before the underlying builtin function is called - pub strict: bool, - /// The name of the argument, to be used in docstrings and error messages - pub name: &'static str, -} +/// Implementors should use the builtins-macros to create these functions +/// instead of handling the argument-passing logic manually. +pub trait BuiltinGen: Fn(Vec<Value>) -> Generator {} +impl<F: Fn(Vec<Value>) -> Generator> BuiltinGen for F {} #[derive(Clone)] pub struct BuiltinRepr { name: &'static str, - /// Array of arguments to the builtin. - arguments: &'static [BuiltinArgument], /// Optional documentation for the builtin. documentation: Option<&'static str>, - func: Rc<dyn BuiltinFn>, + arg_count: usize, + + func: Rc<dyn BuiltinGen>, /// Partially applied function arguments. partials: Vec<Value>, } +pub enum BuiltinResult { + /// Builtin was not ready to be called (arguments missing) and remains + /// partially applied. + Partial(Builtin), + + /// Builtin was called and constructed a generator that the VM must run. + Called(Generator), +} + /// Represents a single built-in function which directly executes Rust /// code that operates on a Nix value. /// @@ -68,16 +66,16 @@ impl From<BuiltinRepr> for Builtin { } impl Builtin { - pub fn new<F: BuiltinFn + 'static>( + pub fn new<F: BuiltinGen + 'static>( name: &'static str, - arguments: &'static [BuiltinArgument], documentation: Option<&'static str>, + arg_count: usize, func: F, ) -> Self { BuiltinRepr { name, - arguments, documentation, + arg_count, func: Rc::new(func), partials: vec![], } @@ -92,23 +90,25 @@ impl Builtin { self.0.documentation } - /// Apply an additional argument to the builtin, which will either - /// lead to execution of the function or to returning a partial - /// builtin. - pub fn apply(mut self, vm: &mut VM, arg: Value) -> Result<Value, ErrorKind> { + /// Apply an additional argument to the builtin. After this, [`call`] *must* + /// be called, otherwise it may leave the builtin in an incorrect state. + pub fn apply_arg(&mut self, arg: Value) { self.0.partials.push(arg); - if self.0.partials.len() == self.0.arguments.len() { - for (idx, BuiltinArgument { strict, .. }) in self.0.arguments.iter().enumerate() { - if *strict { - self.0.partials[idx].force(vm)?; - } - } - return (self.0.func)(self.0.partials, vm); - } + debug_assert!( + self.0.partials.len() <= self.0.arg_count, + "Tvix bug: pushed too many arguments to builtin" + ); + } - // Function is not yet ready to be called. - Ok(Value::Builtin(self)) + /// Attempt to call a builtin, which will produce a generator if it is fully + /// applied or return the builtin if it is partially applied. + pub fn call(self) -> BuiltinResult { + if self.0.partials.len() == self.0.arg_count { + BuiltinResult::Called((self.0.func)(self.0.partials)) + } else { + BuiltinResult::Partial(self) + } } } diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs index e5ddc7bb96b9..9f39b7c6a3d3 100644 --- a/tvix/eval/src/value/list.rs +++ b/tvix/eval/src/value/list.rs @@ -5,11 +5,10 @@ use imbl::{vector, Vector}; use serde::{Deserialize, Serialize}; -use crate::errors::AddContext; -use crate::errors::ErrorKind; -use crate::vm::generators; -use crate::vm::generators::GenCo; -use crate::vm::VM; +use crate::generators; +use crate::generators::GenCo; +use crate::AddContext; +use crate::ErrorKind; use super::thunk::ThunkSet; use super::TotalDisplay; @@ -70,29 +69,6 @@ impl NixList { self.0.ptr_eq(&other.0) } - /// Compare `self` against `other` for equality using Nix equality semantics - pub fn nix_eq(&self, other: &Self, vm: &mut VM) -> Result<bool, ErrorKind> { - if self.ptr_eq(other) { - return Ok(true); - } - if self.len() != other.len() { - return Ok(false); - } - - for (v1, v2) in self.iter().zip(other.iter()) { - if !v1.nix_eq(v2, vm)? { - return Ok(false); - } - } - - Ok(true) - } - - /// force each element of the list (shallowly), making it safe to call .get().value() - pub fn force_elements(&self, vm: &mut VM) -> Result<(), ErrorKind> { - self.iter().try_for_each(|v| v.force(vm).map(|_| ())) - } - pub fn into_inner(self) -> Vector<Value> { self.0 } diff --git a/tvix/eval/src/value/mod.rs b/tvix/eval/src/value/mod.rs index a869c0167524..81e537313227 100644 --- a/tvix/eval/src/value/mod.rs +++ b/tvix/eval/src/value/mod.rs @@ -1,11 +1,12 @@ //! This module implements the backing representation of runtime //! values in the Nix language. use std::cmp::Ordering; +use std::fmt::Display; +use std::future::Future; use std::num::{NonZeroI32, NonZeroUsize}; -use std::ops::Deref; use std::path::PathBuf; +use std::pin::Pin; use std::rc::Rc; -use std::{cell::Ref, fmt::Display}; use lexical_core::format::CXX_LITERAL; use serde::{Deserialize, Serialize}; @@ -20,12 +21,12 @@ mod path; mod string; mod thunk; -use crate::errors::{AddContext, ErrorKind}; +use crate::errors::ErrorKind; use crate::opcode::StackIdx; use crate::vm::generators::{self, GenCo}; -use crate::vm::VM; +use crate::AddContext; pub use attrs::NixAttrs; -pub use builtin::{Builtin, BuiltinArgument}; +pub use builtin::{Builtin, BuiltinResult}; pub(crate) use function::Formals; pub use function::{Closure, Lambda}; pub use list::NixList; @@ -139,8 +140,6 @@ macro_rules! gen_is { /// Describes what input types are allowed when coercing a `Value` to a string #[derive(Clone, Copy, PartialEq, Debug)] pub enum CoercionKind { - /// Force thunks, but perform no other coercions. - ThunksOnly, /// Only coerce already "stringly" types like strings and paths, but also /// coerce sets that have a `__toString` attribute. Equivalent to /// `!coerceMore` in C++ Nix. @@ -151,26 +150,6 @@ pub enum CoercionKind { Strong, } -/// A reference to a [`Value`] returned by a call to [`Value::force`], whether the value was -/// originally a thunk or not. -/// -/// Implements [`Deref`] to [`Value`], so can generally be used as a [`Value`] -pub enum ForceResult<'a> { - ForcedThunk(Ref<'a, Value>), - Immediate(&'a Value), -} - -impl<'a> Deref for ForceResult<'a> { - type Target = Value; - - fn deref(&self) -> &Self::Target { - match self { - ForceResult::ForcedThunk(r) => r, - ForceResult::Immediate(v) => v, - } - } -} - impl<T> From<T> for Value where T: Into<NixString>, @@ -204,33 +183,80 @@ pub enum PointerEquality { } impl Value { + /// Deeply forces a value, traversing e.g. lists and attribute sets and forcing + /// their contents, too. + /// + /// This is a generator function. + pub(super) async fn deep_force( + self, + co: GenCo, + thunk_set: SharedThunkSet, + ) -> Result<Value, ErrorKind> { + // Get rid of any top-level thunks, and bail out of self-recursive + // thunks. + let value = if let Value::Thunk(ref t) = &self { + if !thunk_set.insert(t) { + return Ok(self); + } + generators::request_force(&co, self).await + } else { + self + }; + + match &value { + // Short-circuit on already evaluated values, or fail on internal values. + Value::Null + | Value::Bool(_) + | Value::Integer(_) + | Value::Float(_) + | Value::String(_) + | Value::Path(_) + | Value::Closure(_) + | Value::Builtin(_) => return Ok(value), + + Value::List(list) => { + for val in list { + generators::request_deep_force(&co, val.clone(), thunk_set.clone()).await; + } + } + + Value::Attrs(attrs) => { + for (_, val) in attrs.iter() { + generators::request_deep_force(&co, val.clone(), thunk_set.clone()).await; + } + } + + Value::Thunk(_) => panic!("Tvix bug: force_value() returned a thunk"), + + Value::AttrNotFound + | Value::Blueprint(_) + | Value::DeferredUpvalue(_) + | Value::UnresolvedPath(_) => panic!( + "Tvix bug: internal value left on stack: {}", + value.type_of() + ), + }; + + Ok(value) + } + /// Coerce a `Value` to a string. See `CoercionKind` for a rundown of what /// input types are accepted under what circumstances. - pub fn coerce_to_string( - &self, - kind: CoercionKind, - vm: &mut VM, - ) -> Result<NixString, ErrorKind> { - // TODO: eventually, this will need to handle string context and importing - // files into the Nix store depending on what context the coercion happens in - if let Value::Thunk(t) = self { - t.force(vm)?; - } - - match (self, kind) { - // deal with thunks - (Value::Thunk(t), _) => t.value().coerce_to_string(kind, vm), + pub async fn coerce_to_string(self, co: GenCo, kind: CoercionKind) -> Result<Value, ErrorKind> { + let value = generators::request_force(&co, self).await; + match (value, kind) { // coercions that are always done - (Value::String(s), _) => Ok(s.clone()), + tuple @ (Value::String(_), _) => Ok(tuple.0), // TODO(sterni): Think about proper encoding handling here. This needs // general consideration anyways, since one current discrepancy between // C++ Nix and Tvix is that the former's strings are arbitrary byte // sequences without NUL bytes, whereas Tvix only allows valid // Unicode. See also b/189. - (Value::Path(p), kind) if kind != CoercionKind::ThunksOnly => { - let imported = vm.io().import_path(p)?; + (Value::Path(p), _) => { + // TODO(tazjin): there are cases where coerce_to_string does not import + let imported = generators::request_path_import(&co, p).await; Ok(imported.to_string_lossy().into_owned().into()) } @@ -238,38 +264,32 @@ impl Value { // `__toString` attribute which holds a function that receives the // set itself or an `outPath` attribute which should be a string. // `__toString` is preferred. - (Value::Attrs(attrs), kind) if kind != CoercionKind::ThunksOnly => { + (Value::Attrs(attrs), kind) => { match (attrs.select("__toString"), attrs.select("outPath")) { (None, None) => Err(ErrorKind::NotCoercibleToString { from: "set", kind }), (Some(f), _) => { - // use a closure here to deal with the thunk borrow we need to do below - let call_to_string = |value: &Value, vm: &mut VM| { - // Leave self on the stack as an argument to the function call. - vm.push(self.clone()); - vm.call_value(value)?; - let result = vm.pop(); - - match result { - Value::String(s) => Ok(s), - // Attribute set coercion actually works - // recursively, e.g. you can even return - // /another/ set with a __toString attr. - _ => result.coerce_to_string(kind, vm), - } - }; - - if let Value::Thunk(t) = f { - t.force(vm)?; - let guard = t.value(); - call_to_string(&guard, vm) - } else { - call_to_string(f, vm) - } + let callable = generators::request_force(&co, f.clone()).await; + + // Leave the attribute set on the stack as an argument + // to the function call. + generators::request_stack_push(&co, Value::Attrs(attrs)).await; + + // Call the callable ... + let result = generators::request_call(&co, callable).await; + + // Recurse on the result, as attribute set coercion + // actually works recursively, e.g. you can even return + // /another/ set with a __toString attr. + let s = generators::request_string_coerce(&co, result, kind).await; + Ok(Value::String(s)) } // Similarly to `__toString` we also coerce recursively for `outPath` - (None, Some(s)) => s.coerce_to_string(kind, vm), + (None, Some(s)) => { + let s = generators::request_string_coerce(&co, s.clone(), kind).await; + Ok(Value::String(s)) + } } } @@ -287,30 +307,31 @@ impl Value { } // Lists are coerced by coercing their elements and interspersing spaces - (Value::List(l), CoercionKind::Strong) => { - // TODO(sterni): use intersperse when it becomes available? - // https://github.com/rust-lang/rust/issues/79524 - l.iter() - .map(|v| v.coerce_to_string(kind, vm)) - .reduce(|acc, string| { - let a = acc?; - let s = &string?; - Ok(a.concat(&" ".into()).concat(s)) - }) - // None from reduce indicates empty iterator - .unwrap_or_else(|| Ok("".into())) + (Value::List(list), CoercionKind::Strong) => { + let mut out = String::new(); + + for (idx, elem) in list.into_iter().enumerate() { + if idx > 0 { + out.push(' '); + } + + let s = generators::request_string_coerce(&co, elem, kind).await; + out.push_str(s.as_str()); + } + + Ok(Value::String(out.into())) } - (Value::Path(_), _) - | (Value::Attrs(_), _) - | (Value::Closure(_), _) - | (Value::Builtin(_), _) - | (Value::Null, _) - | (Value::Bool(_), _) - | (Value::Integer(_), _) - | (Value::Float(_), _) - | (Value::List(_), _) => Err(ErrorKind::NotCoercibleToString { - from: self.type_of(), + (Value::Thunk(_), _) => panic!("Tvix bug: force returned unforced thunk"), + + val @ (Value::Closure(_), _) + | val @ (Value::Builtin(_), _) + | val @ (Value::Null, _) + | val @ (Value::Bool(_), _) + | val @ (Value::Integer(_), _) + | val @ (Value::Float(_), _) + | val @ (Value::List(_), _) => Err(ErrorKind::NotCoercibleToString { + from: val.0.type_of(), kind, }), @@ -333,7 +354,7 @@ impl Value { /// The `top_level` parameter controls whether this invocation is the top-level /// comparison, or a nested value comparison. See /// `//tvix/docs/value-pointer-equality.md` - pub(crate) async fn neo_nix_eq( + pub(crate) async fn nix_eq( self, other: Value, co: GenCo, @@ -530,49 +551,52 @@ impl Value { gen_is!(is_number, Value::Integer(_) | Value::Float(_)); gen_is!(is_bool, Value::Bool(_)); - /// Compare `self` against `other` for equality using Nix equality semantics. - /// - /// Takes a reference to the `VM` to allow forcing thunks during comparison - pub fn nix_eq(&self, other: &Self, vm: &mut VM) -> Result<bool, ErrorKind> { - match (self, other) { - // Trivial comparisons - (Value::Null, Value::Null) => Ok(true), - (Value::Bool(b1), Value::Bool(b2)) => Ok(b1 == b2), - (Value::String(s1), Value::String(s2)) => Ok(s1 == s2), - (Value::Path(p1), Value::Path(p2)) => Ok(p1 == p2), - - // Numerical comparisons (they work between float & int) - (Value::Integer(i1), Value::Integer(i2)) => Ok(i1 == i2), - (Value::Integer(i), Value::Float(f)) => Ok(*i as f64 == *f), - (Value::Float(f1), Value::Float(f2)) => Ok(f1 == f2), - (Value::Float(f), Value::Integer(i)) => Ok(*i as f64 == *f), - - (Value::Attrs(_), Value::Attrs(_)) - | (Value::List(_), Value::List(_)) - | (Value::Thunk(_), _) - | (_, Value::Thunk(_)) => Ok(vm.nix_eq(self.clone(), other.clone(), false)?), - - // Everything else is either incomparable (e.g. internal - // types) or false. - _ => Ok(false), - } + /// Internal helper to allow `nix_cmp_ordering` to recurse. + fn nix_cmp_boxed( + self, + other: Self, + co: GenCo, + ) -> Pin<Box<dyn Future<Output = Result<Option<Ordering>, ErrorKind>>>> { + Box::pin(self.nix_cmp_ordering(other, co)) } /// Compare `self` against other using (fallible) Nix ordering semantics. - pub fn nix_cmp(&self, other: &Self, vm: &mut VM) -> Result<Option<Ordering>, ErrorKind> { + /// + /// Note that as this returns an `Option<Ordering>` it can not directly be + /// used as a generator function in the VM. The exact use depends on the + /// callsite, as the meaning is interpreted in different ways e.g. based on + /// the comparison operator used. + /// + /// The function is intended to be used from within other generator + /// functions or `gen!` blocks. + pub async fn nix_cmp_ordering( + self, + other: Self, + co: GenCo, + ) -> Result<Option<Ordering>, ErrorKind> { match (self, other) { // same types - (Value::Integer(i1), Value::Integer(i2)) => Ok(i1.partial_cmp(i2)), - (Value::Float(f1), Value::Float(f2)) => Ok(f1.partial_cmp(f2)), - (Value::String(s1), Value::String(s2)) => Ok(s1.partial_cmp(s2)), + (Value::Integer(i1), Value::Integer(i2)) => Ok(i1.partial_cmp(&i2)), + (Value::Float(f1), Value::Float(f2)) => Ok(f1.partial_cmp(&f2)), + (Value::String(s1), Value::String(s2)) => Ok(s1.partial_cmp(&s2)), (Value::List(l1), Value::List(l2)) => { for i in 0.. { if i == l2.len() { return Ok(Some(Ordering::Greater)); } else if i == l1.len() { return Ok(Some(Ordering::Less)); - } else if !vm.nix_eq(l1[i].clone(), l2[i].clone(), true)? { - return l1[i].force(vm)?.nix_cmp(&*l2[i].force(vm)?, vm); + } else if !generators::check_equality( + &co, + l1[i].clone(), + l2[i].clone(), + PointerEquality::AllowAll, + ) + .await? + { + // TODO: do we need to control `top_level` here? + let v1 = generators::request_force(&co, l1[i].clone()).await; + let v2 = generators::request_force(&co, l2[i].clone()).await; + return v1.nix_cmp_boxed(v2, co).await; } } @@ -580,8 +604,8 @@ impl Value { } // different types - (Value::Integer(i1), Value::Float(f2)) => Ok((*i1 as f64).partial_cmp(f2)), - (Value::Float(f1), Value::Integer(i2)) => Ok(f1.partial_cmp(&(*i2 as f64))), + (Value::Integer(i1), Value::Float(f2)) => Ok((i1 as f64).partial_cmp(&f2)), + (Value::Float(f1), Value::Integer(i2)) => Ok(f1.partial_cmp(&(i2 as f64))), // unsupported types (lhs, rhs) => Err(ErrorKind::Incomparable { @@ -591,58 +615,12 @@ impl Value { } } - /// Ensure `self` is forced if it is a thunk, and return a reference to the resulting value. - pub fn force(&self, vm: &mut VM) -> Result<ForceResult, ErrorKind> { - match self { - Self::Thunk(thunk) => { - thunk.force(vm)?; - Ok(ForceResult::ForcedThunk(thunk.value())) - } - _ => Ok(ForceResult::Immediate(self)), + pub async fn force(self, co: GenCo) -> Result<Value, ErrorKind> { + if let Value::Thunk(thunk) = self { + return thunk.force(co).await; } - } - - /// Ensure `self` is *deeply* forced, including all recursive sub-values - pub(crate) fn deep_force( - &self, - vm: &mut VM, - thunk_set: &mut ThunkSet, - ) -> Result<(), ErrorKind> { - match self { - Value::Null - | Value::Bool(_) - | Value::Integer(_) - | Value::Float(_) - | Value::String(_) - | Value::Path(_) - | Value::Closure(_) - | Value::Builtin(_) - | Value::AttrNotFound - | Value::Blueprint(_) - | Value::DeferredUpvalue(_) - | Value::UnresolvedPath(_) => Ok(()), - Value::Attrs(a) => { - for (_, v) in a.iter() { - v.deep_force(vm, thunk_set)?; - } - Ok(()) - } - Value::List(l) => { - for val in l { - val.deep_force(vm, thunk_set)?; - } - Ok(()) - } - Value::Thunk(thunk) => { - if !thunk_set.insert(thunk) { - return Ok(()); - } - thunk.force(vm)?; - let value = thunk.value().clone(); - value.deep_force(vm, thunk_set) - } - } + Ok(self) } /// Explain a value in a human-readable way, e.g. by presenting @@ -835,9 +813,6 @@ fn type_error(expected: &'static str, actual: &Value) -> ErrorKind { #[cfg(test)] mod tests { - use super::*; - use imbl::vector; - mod floats { use crate::value::total_fmt_float; @@ -865,72 +840,4 @@ mod tests { } } } - - mod nix_eq { - use crate::observer::NoOpObserver; - - use super::*; - use proptest::prelude::ProptestConfig; - use test_strategy::proptest; - - #[proptest(ProptestConfig { cases: 5, ..Default::default() })] - fn reflexive(x: Value) { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - assert!(x.nix_eq(&x, &mut vm).unwrap()) - } - - #[proptest(ProptestConfig { cases: 5, ..Default::default() })] - fn symmetric(x: Value, y: Value) { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - assert_eq!( - x.nix_eq(&y, &mut vm).unwrap(), - y.nix_eq(&x, &mut vm).unwrap() - ) - } - - #[proptest(ProptestConfig { cases: 5, ..Default::default() })] - fn transitive(x: Value, y: Value, z: Value) { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - if x.nix_eq(&y, &mut vm).unwrap() && y.nix_eq(&z, &mut vm).unwrap() { - assert!(x.nix_eq(&z, &mut vm).unwrap()) - } - } - - #[test] - fn list_int_float_fungibility() { - let mut observer = NoOpObserver {}; - let mut vm = VM::new( - Default::default(), - Box::new(crate::DummyIO), - &mut observer, - Default::default(), - ); - - let v1 = Value::List(NixList::from(vector![Value::Integer(1)])); - let v2 = Value::List(NixList::from(vector![Value::Float(1.0)])); - - assert!(v1.nix_eq(&v2, &mut vm).unwrap()) - } - } } diff --git a/tvix/eval/src/value/thunk.rs b/tvix/eval/src/value/thunk.rs index 43adb314a211..42e8ec869ac5 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()), } } } diff --git a/tvix/eval/src/vm.rs b/tvix/eval/src/vm.rs deleted file mode 100644 index f5107f9ed738..000000000000 --- a/tvix/eval/src/vm.rs +++ /dev/null @@ -1,1218 +0,0 @@ -//! This module implements the virtual (or abstract) machine that runs -//! Tvix bytecode. - -pub mod generators; - -use serde_json::json; -use std::{cmp::Ordering, collections::HashMap, ops::DerefMut, path::PathBuf, rc::Rc}; - -use crate::{ - chunk::Chunk, - compiler::GlobalsMap, - errors::{Error, ErrorKind, EvalResult}, - io::EvalIO, - nix_search_path::NixSearchPath, - observer::RuntimeObserver, - opcode::{CodeIdx, Count, JumpOffset, OpCode, StackIdx, UpvalueIdx}, - spans::LightSpan, - upvalues::Upvalues, - value::{Builtin, Closure, CoercionKind, Lambda, NixAttrs, NixList, Thunk, Value}, - warnings::{EvalWarning, WarningKind}, -}; - -/// Representation of a VM continuation; -/// see: https://en.wikipedia.org/wiki/Continuation-passing_style#CPS_in_Haskell -type Continuation = Box<dyn FnOnce(&mut VM) -> EvalResult<Trampoline>>; - -/// A description of how to continue evaluation of a thunk when returned to by the VM -/// -/// This struct is used when forcing thunks to avoid stack-based recursion, which for deeply nested -/// evaluation can easily overflow the stack. -#[must_use = "this `Trampoline` may be a continuation request, which should be handled"] -#[derive(Default)] -pub struct Trampoline { - /// The action to perform upon return to the trampoline - pub action: Option<TrampolineAction>, - - /// The continuation to execute after the action has completed - pub continuation: Option<Continuation>, -} - -impl Trampoline { - /// Add the execution of a new [`Continuation`] to the existing continuation - /// of this `Trampoline`, returning the resulting `Trampoline`. - pub fn append_to_continuation(self, f: Continuation) -> Self { - Trampoline { - action: self.action, - continuation: match self.continuation { - None => Some(f), - Some(f0) => Some(Box::new(move |vm| { - let trampoline = f0(vm)?; - Ok(trampoline.append_to_continuation(f)) - })), - }, - } - } -} - -/// Description of an action to perform upon return to a [`Trampoline`] by the VM -pub enum TrampolineAction { - /// Enter a new stack frame - EnterFrame { - lambda: Rc<Lambda>, - upvalues: Rc<Upvalues>, - light_span: LightSpan, - arg_count: usize, - }, -} - -struct CallFrame { - /// The lambda currently being executed. - lambda: Rc<Lambda>, - - /// Optional captured upvalues of this frame (if a thunk or - /// closure if being evaluated). - upvalues: Rc<Upvalues>, - - /// Instruction pointer to the instruction currently being - /// executed. - ip: CodeIdx, - - /// Stack offset, i.e. the frames "view" into the VM's full stack. - stack_offset: usize, - - continuation: Option<Continuation>, -} - -impl CallFrame { - /// Retrieve an upvalue from this frame at the given index. - fn upvalue(&self, idx: UpvalueIdx) -> &Value { - &self.upvalues[idx] - } -} - -pub struct VM<'o> { - /// The VM call stack. One element is pushed onto this stack - /// each time a function is called or a thunk is forced. - frames: Vec<CallFrame>, - - /// The VM value stack. This is actually a "stack of stacks", - /// with one stack-of-Values for each CallFrame in frames. This - /// is represented as a Vec<Value> rather than as - /// Vec<Vec<Value>> or a Vec<Value> inside CallFrame for - /// efficiency reasons: it avoids having to allocate a Vec on - /// the heap each time a CallFrame is entered. - stack: Vec<Value>, - - /// Stack indices (absolute indexes into `stack`) of attribute - /// sets from which variables should be dynamically resolved - /// (`with`). - with_stack: Vec<usize>, - - /// Runtime warnings collected during evaluation. - warnings: Vec<EvalWarning>, - - /// Import cache, mapping absolute file paths to the value that - /// they compile to. Note that this reuses thunks, too! - // TODO: should probably be based on a file hash - pub import_cache: Box<HashMap<PathBuf, Value>>, - - /// Parsed Nix search path, which is used to resolve `<...>` - /// references. - nix_search_path: NixSearchPath, - - /// Implementation of I/O operations used for impure builtins and - /// features like `import`. - io_handle: Box<dyn EvalIO>, - - /// Runtime observer which can print traces of runtime operations. - observer: &'o mut dyn RuntimeObserver, - - /// Strong reference to the globals, guaranteeing that they are - /// kept alive for the duration of evaluation. - /// - /// This is important because recursive builtins (specifically - /// `import`) hold a weak reference to the builtins, while the - /// original strong reference is held by the compiler which does - /// not exist anymore at runtime. - #[allow(dead_code)] - globals: Rc<GlobalsMap>, -} - -/// The result of a VM's runtime evaluation. -pub struct RuntimeResult { - pub value: Value, - pub warnings: Vec<EvalWarning>, -} - -/// This macro wraps a computation that returns an ErrorKind or a -/// result, and wraps the ErrorKind in an Error struct if present. -/// -/// The reason for this macro's existence is that calculating spans is -/// potentially expensive, so it should be avoided to the last moment -/// (i.e. definite instantiation of a runtime error) if possible. -macro_rules! fallible { - ( $self:ident, $body:expr) => { - match $body { - Ok(result) => result, - Err(kind) => return Err(Error::new(kind, $self.current_span())), - } - }; -} - -#[macro_export] -macro_rules! arithmetic_op { - ( $self:ident, $op:tt ) => {{ - let b = $self.pop(); - let a = $self.pop(); - let result = fallible!($self, arithmetic_op!(&a, &b, $op)); - $self.push(result); - }}; - - ( $a:expr, $b:expr, $op:tt ) => {{ - match ($a, $b) { - (Value::Integer(i1), Value::Integer(i2)) => Ok(Value::Integer(i1 $op i2)), - (Value::Float(f1), Value::Float(f2)) => Ok(Value::Float(f1 $op f2)), - (Value::Integer(i1), Value::Float(f2)) => Ok(Value::Float(*i1 as f64 $op f2)), - (Value::Float(f1), Value::Integer(i2)) => Ok(Value::Float(f1 $op *i2 as f64)), - - (v1, v2) => Err(ErrorKind::TypeError { - expected: "number (either int or float)", - actual: if v1.is_number() { - v2.type_of() - } else { - v1.type_of() - }, - }), - } - }}; -} - -#[macro_export] -macro_rules! cmp_op { - ( $self:ident, $op:tt ) => {{ - let b = $self.pop(); - let a = $self.pop(); - let ordering = fallible!($self, a.nix_cmp(&b, $self)); - let result = Value::Bool(cmp_op!(@order $op ordering)); - $self.push(result); - }}; - - (@order < $ordering:expr) => { - $ordering == Some(Ordering::Less) - }; - - (@order > $ordering:expr) => { - $ordering == Some(Ordering::Greater) - }; - - (@order <= $ordering:expr) => { - !matches!($ordering, None | Some(Ordering::Greater)) - }; - - (@order >= $ordering:expr) => { - !matches!($ordering, None | Some(Ordering::Less)) - }; -} - -impl<'o> VM<'o> { - pub fn new( - nix_search_path: NixSearchPath, - io_handle: Box<dyn EvalIO>, - observer: &'o mut dyn RuntimeObserver, - globals: Rc<GlobalsMap>, - ) -> Self { - // Backtrace-on-stack-overflow is some seriously weird voodoo and - // very unsafe. This double-guard prevents it from accidentally - // being enabled on release builds. - #[cfg(debug_assertions)] - #[cfg(feature = "backtrace_overflow")] - unsafe { - backtrace_on_stack_overflow::enable(); - }; - - Self { - nix_search_path, - io_handle, - observer, - globals, - frames: vec![], - stack: vec![], - with_stack: vec![], - warnings: vec![], - import_cache: Default::default(), - } - } - - fn frame(&self) -> &CallFrame { - &self.frames[self.frames.len() - 1] - } - - fn chunk(&self) -> &Chunk { - &self.frame().lambda.chunk - } - - fn frame_mut(&mut self) -> &mut CallFrame { - let idx = self.frames.len() - 1; - &mut self.frames[idx] - } - - fn inc_ip(&mut self) -> OpCode { - let op = self.chunk()[self.frame().ip]; - self.frame_mut().ip += 1; - op - } - - pub fn pop(&mut self) -> Value { - self.stack.pop().expect("runtime stack empty") - } - - pub fn pop_then_drop(&mut self, num_items: usize) { - self.stack.truncate(self.stack.len() - num_items); - } - - pub fn push(&mut self, value: Value) { - self.stack.push(value) - } - - fn peek(&self, offset: usize) -> &Value { - &self.stack[self.stack.len() - 1 - offset] - } - - /// Returns the source span of the instruction currently being - /// executed. - pub(crate) fn current_span(&self) -> codemap::Span { - self.chunk().get_span(self.frame().ip - 1) - } - - /// Returns the information needed to calculate the current span, - /// but without performing that calculation. - pub(crate) fn current_light_span(&self) -> LightSpan { - LightSpan::new_delayed(self.frame().lambda.clone(), self.frame().ip - 1) - } - - /// Access the I/O handle used for filesystem access in this VM. - pub(crate) fn io(&self) -> &dyn EvalIO { - &*self.io_handle - } - - /// Construct an error from the given ErrorKind and the source - /// span of the current instruction. - pub fn error(&self, kind: ErrorKind) -> Error { - Error::new(kind, self.current_span()) - } - - /// Push an already constructed warning. - pub fn push_warning(&mut self, warning: EvalWarning) { - self.warnings.push(warning); - } - - /// Emit a warning with the given WarningKind and the source span - /// of the current instruction. - pub fn emit_warning(&mut self, kind: WarningKind) { - self.push_warning(EvalWarning { - kind, - span: self.current_span(), - }); - } - - /// Execute the given value in this VM's context, if it is a - /// callable. - /// - /// The stack of the VM must be prepared with all required - /// arguments before calling this and the value must have already - /// been forced. - pub fn call_value(&mut self, callable: &Value) -> EvalResult<()> { - match callable { - Value::Closure(c) => self.enter_frame(c.lambda(), c.upvalues(), 1), - - Value::Builtin(b) => self.call_builtin(b.clone()), - - Value::Thunk(t) => { - debug_assert!(t.is_evaluated(), "call_value called with unevaluated thunk"); - self.call_value(&t.value()) - } - - // Attribute sets with a __functor attribute are callable. - Value::Attrs(ref attrs) => match attrs.select("__functor") { - None => Err(self.error(ErrorKind::NotCallable(callable.type_of()))), - Some(functor) => { - // The functor receives the set itself as its first argument - // and needs to be called with it. However, this call is - // synthetic (i.e. there is no corresponding OpCall for the - // first call in the bytecode.) - self.push(callable.clone()); - self.call_value(functor)?; - let primed = self.pop(); - self.call_value(&primed) - } - }, - - // TODO: this isn't guaranteed to be a useful span, actually - other => Err(self.error(ErrorKind::NotCallable(other.type_of()))), - } - } - - /// Call the given `callable` value with the given list of `args` - /// - /// # Panics - /// - /// Panics if the passed list of `args` is empty - #[track_caller] - pub fn call_with<I>(&mut self, callable: &Value, args: I) -> EvalResult<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; - self.push(arg); - } - - if num_args == 0 { - panic!("call_with called with an empty list of args"); - } - - self.call_value(callable)?; - let mut res = self.pop(); - - for _ in 0..(num_args - 1) { - res.force(self).map_err(|e| self.error(e))?; - self.call_value(&res)?; - res = self.pop(); - } - - Ok(res) - } - - fn tail_call_value(&mut self, callable: Value) -> EvalResult<()> { - match callable { - Value::Builtin(builtin) => self.call_builtin(builtin), - Value::Thunk(thunk) => self.tail_call_value(thunk.value().clone()), - - Value::Closure(closure) => { - let lambda = closure.lambda(); - self.observer.observe_tail_call(self.frames.len(), &lambda); - - // Replace the current call frames internals with - // that of the tail-called closure. - let mut frame = self.frame_mut(); - frame.lambda = lambda; - frame.upvalues = closure.upvalues(); - frame.ip = CodeIdx(0); // reset instruction pointer to beginning - Ok(()) - } - - // Attribute sets with a __functor attribute are callable. - Value::Attrs(ref attrs) => match attrs.select("__functor") { - None => Err(self.error(ErrorKind::NotCallable(callable.type_of()))), - Some(functor) => { - if let Value::Thunk(thunk) = &functor { - fallible!(self, thunk.force(self)); - } - - // The functor receives the set itself as its first argument - // and needs to be called with it. However, this call is - // synthetic (i.e. there is no corresponding OpCall for the - // first call in the bytecode.) - self.push(callable.clone()); - self.call_value(functor)?; - let primed = self.pop(); - self.tail_call_value(primed) - } - }, - - _ => Err(self.error(ErrorKind::NotCallable(callable.type_of()))), - } - } - - /// Execute the given lambda in this VM's context, leaving the - /// computed value on its stack after the frame completes. - pub fn enter_frame( - &mut self, - lambda: Rc<Lambda>, - upvalues: Rc<Upvalues>, - arg_count: usize, - ) -> EvalResult<()> { - self.observer - .observe_enter_call_frame(arg_count, &lambda, self.frames.len() + 1); - - let frame = CallFrame { - lambda, - upvalues, - ip: CodeIdx(0), - stack_offset: self.stack.len() - arg_count, - continuation: None, - }; - - let starting_frames_depth = self.frames.len(); - self.frames.push(frame); - - let result = loop { - let op = self.inc_ip(); - - self.observer - .observe_execute_op(self.frame().ip, &op, &self.stack); - - let res = self.run_op(op); - - let mut retrampoline: Option<Continuation> = None; - - // we need to pop the frame before checking `res` for an - // error in order to implement `tryEval` correctly. - if self.frame().ip.0 == self.chunk().code.len() { - let frame = self.frames.pop(); - retrampoline = frame.and_then(|frame| frame.continuation); - } - self.trampoline_loop(res?, retrampoline)?; - if self.frames.len() == starting_frames_depth { - break Ok(()); - } - }; - - self.observer - .observe_exit_call_frame(self.frames.len() + 1, &self.stack); - - result - } - - fn trampoline_loop( - &mut self, - mut trampoline: Trampoline, - mut retrampoline: Option<Continuation>, - ) -> EvalResult<()> { - loop { - if let Some(TrampolineAction::EnterFrame { - lambda, - upvalues, - arg_count, - light_span: _, - }) = trampoline.action - { - let frame = CallFrame { - lambda, - upvalues, - ip: CodeIdx(0), - stack_offset: self.stack.len() - arg_count, - continuation: match retrampoline { - None => trampoline.continuation, - Some(retrampoline) => match trampoline.continuation { - None => None, - Some(cont) => Some(Box::new(|vm| { - Ok(cont(vm)?.append_to_continuation(retrampoline)) - })), - }, - }, - }; - self.frames.push(frame); - break; - } - - match trampoline.continuation { - None => { - if let Some(cont) = retrampoline.take() { - trampoline = cont(self)?; - } else { - break; - } - } - Some(cont) => { - trampoline = cont(self)?; - continue; - } - } - } - Ok(()) - } - - pub(crate) fn nix_eq( - &mut self, - v1: Value, - v2: Value, - allow_top_level_pointer_equality_on_functions_and_thunks: bool, - ) -> EvalResult<bool> { - self.push(v1); - self.push(v2); - let res = self.nix_op_eq(allow_top_level_pointer_equality_on_functions_and_thunks); - self.trampoline_loop(res?, None)?; - match self.pop() { - Value::Bool(b) => Ok(b), - v => panic!("run_op(OpEqual) left a non-boolean on the stack: {v:#?}"), - } - } - - pub(crate) fn nix_op_eq( - &mut self, - allow_top_level_pointer_equality_on_functions_and_thunks: bool, - ) -> EvalResult<Trampoline> { - // This bit gets set to `true` (if it isn't already) as soon - // as we start comparing the contents of two - // {lists,attrsets} -- but *not* the contents of two thunks. - // See tvix/docs/value-pointer-equality.md for details. - let mut allow_pointer_equality_on_functions_and_thunks = - allow_top_level_pointer_equality_on_functions_and_thunks; - - let mut numpairs: usize = 1; - let res = 'outer: loop { - if numpairs == 0 { - break true; - } else { - numpairs -= 1; - } - let v2 = self.pop(); - let v1 = self.pop(); - let v2 = match v2 { - Value::Thunk(thunk) => { - if allow_top_level_pointer_equality_on_functions_and_thunks { - if let Value::Thunk(t1) = &v1 { - if t1.ptr_eq(&thunk) { - continue; - } - } - } - fallible!(self, thunk.force(self)); - thunk.value().clone() - } - v => v, - }; - let v1 = match v1 { - Value::Thunk(thunk) => { - fallible!(self, thunk.force(self)); - thunk.value().clone() - } - v => v, - }; - match (v1, v2) { - (Value::List(l1), Value::List(l2)) => { - allow_pointer_equality_on_functions_and_thunks = true; - if l1.ptr_eq(&l2) { - continue; - } - if l1.len() != l2.len() { - break false; - } - for (vi1, vi2) in l1.into_iter().zip(l2.into_iter()) { - self.stack.push(vi1); - self.stack.push(vi2); - numpairs += 1; - } - } - (_, Value::List(_)) => break false, - (Value::List(_), _) => break false, - - (Value::Attrs(a1), Value::Attrs(a2)) => { - if allow_pointer_equality_on_functions_and_thunks && a1.ptr_eq(&a2) { - continue; - } - allow_pointer_equality_on_functions_and_thunks = true; - match (a1.select("type"), a2.select("type")) { - (Some(v1), Some(v2)) - if "derivation" - == fallible!( - self, - v1.coerce_to_string(CoercionKind::ThunksOnly, self) - ) - .as_str() - && "derivation" - == fallible!( - self, - v2.coerce_to_string(CoercionKind::ThunksOnly, self) - ) - .as_str() => - { - if fallible!( - self, - a1.select("outPath") - .expect("encountered a derivation with no `outPath` attribute!") - .coerce_to_string(CoercionKind::ThunksOnly, self) - ) == fallible!( - self, - a2.select("outPath") - .expect("encountered a derivation with no `outPath` attribute!") - .coerce_to_string(CoercionKind::ThunksOnly, self) - ) { - continue; - } - break false; - } - _ => {} - } - let iter1 = a1.into_iter_sorted(); - let iter2 = a2.into_iter_sorted(); - if iter1.len() != iter2.len() { - break false; - } - for ((k1, v1), (k2, v2)) in iter1.zip(iter2) { - if k1 != k2 { - break 'outer false; - } - self.stack.push(v1); - self.stack.push(v2); - numpairs += 1; - } - } - (Value::Attrs(_), _) => break false, - (_, Value::Attrs(_)) => break false, - - (v1, v2) => { - if allow_pointer_equality_on_functions_and_thunks { - if let (Value::Closure(c1), Value::Closure(c2)) = (&v1, &v2) { - if Rc::ptr_eq(c1, c2) { - continue; - } - } - } - if !fallible!(self, v1.nix_eq(&v2, self)) { - break false; - } - } - } - }; - self.pop_then_drop(numpairs * 2); - self.push(Value::Bool(res)); - Ok(Trampoline::default()) - } - - pub(crate) fn run_op(&mut self, op: OpCode) -> EvalResult<Trampoline> { - match op { - OpCode::OpConstant(idx) => { - let c = self.chunk()[idx].clone(); - self.push(c); - } - - OpCode::OpPop => { - self.pop(); - } - - OpCode::OpAdd => { - let b = self.pop(); - let a = self.pop(); - - let result = match (&a, &b) { - (Value::Path(p), v) => { - let mut path = p.to_string_lossy().into_owned(); - path.push_str( - &v.coerce_to_string(CoercionKind::Weak, self) - .map_err(|ek| self.error(ek))?, - ); - crate::value::canon_path(PathBuf::from(path)).into() - } - (Value::String(s1), Value::String(s2)) => Value::String(s1.concat(s2)), - (Value::String(s1), v) => Value::String( - s1.concat( - &v.coerce_to_string(CoercionKind::Weak, self) - .map_err(|ek| self.error(ek))?, - ), - ), - (v, Value::String(s2)) => Value::String( - v.coerce_to_string(CoercionKind::Weak, self) - .map_err(|ek| self.error(ek))? - .concat(s2), - ), - _ => fallible!(self, arithmetic_op!(&a, &b, +)), - }; - - self.push(result) - } - - OpCode::OpSub => arithmetic_op!(self, -), - OpCode::OpMul => arithmetic_op!(self, *), - OpCode::OpDiv => { - let b = self.peek(0); - - match b { - Value::Integer(0) => return Err(self.error(ErrorKind::DivisionByZero)), - Value::Float(b) => { - if *b == 0.0_f64 { - return Err(self.error(ErrorKind::DivisionByZero)); - } - arithmetic_op!(self, /) - } - _ => arithmetic_op!(self, /), - }; - } - - OpCode::OpInvert => { - let v = fallible!(self, self.pop().as_bool()); - self.push(Value::Bool(!v)); - } - - OpCode::OpNegate => match self.pop() { - Value::Integer(i) => self.push(Value::Integer(-i)), - Value::Float(f) => self.push(Value::Float(-f)), - v => { - return Err(self.error(ErrorKind::TypeError { - expected: "number (either int or float)", - actual: v.type_of(), - })); - } - }, - - OpCode::OpEqual => return self.nix_op_eq(false), - - OpCode::OpLess => cmp_op!(self, <), - OpCode::OpLessOrEq => cmp_op!(self, <=), - OpCode::OpMore => cmp_op!(self, >), - OpCode::OpMoreOrEq => cmp_op!(self, >=), - - OpCode::OpAttrs(Count(count)) => self.run_attrset(count)?, - - OpCode::OpAttrsUpdate => { - let rhs = fallible!(self, self.pop().to_attrs()); - let lhs = fallible!(self, self.pop().to_attrs()); - - self.push(Value::attrs(lhs.update(*rhs))) - } - - OpCode::OpAttrsSelect => { - let key = fallible!(self, self.pop().to_str()); - let attrs = fallible!(self, self.pop().to_attrs()); - - match attrs.select(key.as_str()) { - Some(value) => self.push(value.clone()), - - None => { - return Err(self.error(ErrorKind::AttributeNotFound { - name: key.as_str().to_string(), - })) - } - } - } - - OpCode::OpAttrsTrySelect => { - let key = fallible!(self, self.pop().to_str()); - let value = match self.pop() { - Value::Attrs(attrs) => match attrs.select(key.as_str()) { - Some(value) => value.clone(), - None => Value::AttrNotFound, - }, - - _ => Value::AttrNotFound, - }; - - self.push(value); - } - - OpCode::OpHasAttr => { - let key = fallible!(self, self.pop().to_str()); - let result = match self.pop() { - Value::Attrs(attrs) => attrs.contains(key.as_str()), - - // Nix allows use of `?` on non-set types, but - // always returns false in those cases. - _ => false, - }; - - self.push(Value::Bool(result)); - } - - OpCode::OpValidateClosedFormals => { - let formals = self.frame().lambda.formals.as_ref().expect( - "OpValidateClosedFormals called within the frame of a lambda without formals", - ); - let args = self.peek(0).to_attrs().map_err(|err| self.error(err))?; - for arg in args.keys() { - if !formals.contains(arg) { - return Err(self.error(ErrorKind::UnexpectedArgument { - arg: arg.clone(), - formals_span: formals.span, - })); - } - } - } - - OpCode::OpList(Count(count)) => { - let list = - NixList::construct(count, self.stack.split_off(self.stack.len() - count)); - self.push(Value::List(list)); - } - - OpCode::OpConcat => { - let rhs = fallible!(self, self.pop().to_list()).into_inner(); - let lhs = fallible!(self, self.pop().to_list()).into_inner(); - self.push(Value::List(NixList::from(lhs + rhs))) - } - - OpCode::OpInterpolate(Count(count)) => self.run_interpolate(count)?, - - OpCode::OpCoerceToString => { - // TODO: handle string context, copying to store - let string = fallible!( - self, - // note that coerce_to_string also forces - self.pop().coerce_to_string(CoercionKind::Weak, self) - ); - self.push(Value::String(string)); - } - - OpCode::OpFindFile => match self.pop() { - Value::UnresolvedPath(path) => { - let resolved = self - .nix_search_path - .resolve(path) - .map_err(|e| self.error(e))?; - self.push(resolved.into()); - } - - _ => panic!("tvix compiler bug: OpFindFile called on non-UnresolvedPath"), - }, - - OpCode::OpResolveHomePath => match self.pop() { - Value::UnresolvedPath(path) => { - match dirs::home_dir() { - None => { - return Err(self.error(ErrorKind::RelativePathResolution( - "failed to determine home directory".into(), - ))); - } - Some(mut buf) => { - buf.push(path); - self.push(buf.into()); - } - }; - } - - _ => { - panic!("tvix compiler bug: OpResolveHomePath called on non-UnresolvedPath") - } - }, - - OpCode::OpJump(JumpOffset(offset)) => { - debug_assert!(offset != 0); - self.frame_mut().ip += offset; - } - - OpCode::OpJumpIfTrue(JumpOffset(offset)) => { - debug_assert!(offset != 0); - if fallible!(self, self.peek(0).as_bool()) { - self.frame_mut().ip += offset; - } - } - - OpCode::OpJumpIfFalse(JumpOffset(offset)) => { - debug_assert!(offset != 0); - if !fallible!(self, self.peek(0).as_bool()) { - self.frame_mut().ip += offset; - } - } - - OpCode::OpJumpIfNotFound(JumpOffset(offset)) => { - debug_assert!(offset != 0); - if matches!(self.peek(0), Value::AttrNotFound) { - self.pop(); - self.frame_mut().ip += offset; - } - } - - // These assertion operations error out if the stack - // top is not of the expected type. This is necessary - // to implement some specific behaviours of Nix - // exactly. - OpCode::OpAssertBool => { - let val = self.peek(0); - if !val.is_bool() { - return Err(self.error(ErrorKind::TypeError { - expected: "bool", - actual: val.type_of(), - })); - } - } - - // Remove the given number of elements from the stack, - // but retain the top value. - OpCode::OpCloseScope(Count(count)) => { - // Immediately move the top value into the right - // position. - let target_idx = self.stack.len() - 1 - count; - self.stack[target_idx] = self.pop(); - - // Then drop the remaining values. - for _ in 0..(count - 1) { - self.pop(); - } - } - - OpCode::OpGetLocal(StackIdx(local_idx)) => { - let idx = self.frame().stack_offset + local_idx; - self.push(self.stack[idx].clone()); - } - - OpCode::OpPushWith(StackIdx(idx)) => { - self.with_stack.push(self.frame().stack_offset + idx) - } - - OpCode::OpPopWith => { - self.with_stack.pop(); - } - - OpCode::OpResolveWith => { - let ident = fallible!(self, self.pop().to_str()); - let value = self.resolve_with(ident.as_str())?; - self.push(value) - } - - OpCode::OpAssertFail => { - return Err(self.error(ErrorKind::AssertionFailed)); - } - - OpCode::OpCall => { - let callable = self.pop(); - self.tail_call_value(callable)?; - } - - OpCode::OpGetUpvalue(upv_idx) => { - let value = self.frame().upvalue(upv_idx).clone(); - self.push(value); - } - - OpCode::OpClosure(idx) => { - let blueprint = match &self.chunk()[idx] { - Value::Blueprint(lambda) => lambda.clone(), - _ => panic!("compiler bug: non-blueprint in blueprint slot"), - }; - - let upvalue_count = blueprint.upvalue_count; - debug_assert!( - upvalue_count > 0, - "OpClosure should not be called for plain lambdas" - ); - let mut upvalues = Upvalues::with_capacity(blueprint.upvalue_count); - self.populate_upvalues(upvalue_count, &mut upvalues)?; - self.push(Value::Closure(Rc::new(Closure::new_with_upvalues( - Rc::new(upvalues), - blueprint, - )))); - } - - OpCode::OpThunkSuspended(idx) | OpCode::OpThunkClosure(idx) => { - let blueprint = match &self.chunk()[idx] { - Value::Blueprint(lambda) => lambda.clone(), - _ => panic!("compiler bug: non-blueprint in blueprint slot"), - }; - - let upvalue_count = blueprint.upvalue_count; - let thunk = if matches!(op, OpCode::OpThunkClosure(_)) { - debug_assert!( - upvalue_count > 0, - "OpThunkClosure should not be called for plain lambdas" - ); - Thunk::new_closure(blueprint) - } else { - Thunk::new_suspended(blueprint, self.current_light_span()) - }; - let upvalues = thunk.upvalues_mut(); - self.push(Value::Thunk(thunk.clone())); - - // From this point on we internally mutate the - // upvalues. The closure (if `is_closure`) is - // already in its stack slot, which means that it - // can capture itself as an upvalue for - // self-recursion. - self.populate_upvalues(upvalue_count, upvalues)?; - } - - OpCode::OpForce => { - if let Some(Value::Thunk(_)) = self.stack.last() { - let value = self.pop(); - let trampoline = fallible!(self, Thunk::force_trampoline(self, value)); - return Ok(trampoline); - } - } - - OpCode::OpFinalise(StackIdx(idx)) => { - match &self.stack[self.frame().stack_offset + idx] { - Value::Closure(_) => panic!("attempted to finalise a closure"), - - Value::Thunk(thunk) => thunk.finalise(&self.stack[self.frame().stack_offset..]), - - // In functions with "formals" attributes, it is - // possible for `OpFinalise` to be called on a - // non-capturing value, in which case it is a no-op. - // - // TODO: detect this in some phase and skip the finalise; fail here - _ => { /* TODO: panic here again to catch bugs */ } - } - } - - // Data-carrying operands should never be executed, - // that is a critical error in the VM. - OpCode::DataStackIdx(_) - | OpCode::DataDeferredLocal(_) - | OpCode::DataUpvalueIdx(_) - | OpCode::DataCaptureWith => { - panic!("VM bug: attempted to execute data-carrying operand") - } - } - - Ok(Trampoline::default()) - } - - fn run_attrset(&mut self, count: usize) -> EvalResult<()> { - let attrs = fallible!( - self, - NixAttrs::construct(count, self.stack.split_off(self.stack.len() - count * 2)) - ); - - self.push(Value::attrs(attrs)); - Ok(()) - } - - /// Interpolate string fragments by popping the specified number of - /// fragments of the stack, evaluating them to strings, and pushing - /// the concatenated result string back on the stack. - fn run_interpolate(&mut self, count: usize) -> EvalResult<()> { - let mut out = String::new(); - - for _ in 0..count { - out.push_str(fallible!(self, self.pop().to_str()).as_str()); - } - - self.push(Value::String(out.into())); - Ok(()) - } - - /// Resolve a dynamic identifier through the with-stack at runtime. - fn resolve_with(&mut self, ident: &str) -> EvalResult<Value> { - // Iterate over the with_stack manually to avoid borrowing - // self, which is required for forcing the set. - for with_stack_idx in (0..self.with_stack.len()).rev() { - let with = self.stack[self.with_stack[with_stack_idx]].clone(); - - if let Value::Thunk(thunk) = &with { - fallible!(self, thunk.force(self)); - } - - match fallible!(self, with.to_attrs()).select(ident) { - None => continue, - Some(val) => return Ok(val.clone()), - } - } - - // Iterate over the captured with stack if one exists. This is - // extra tricky to do without a lot of cloning. - for idx in (0..self.frame().upvalues.with_stack_len()).rev() { - // This will not panic because having an index here guarantees - // that the stack is present. - let with = self.frame().upvalues.with_stack().unwrap()[idx].clone(); - if let Value::Thunk(thunk) = &with { - fallible!(self, thunk.force(self)); - } - - match fallible!(self, with.to_attrs()).select(ident) { - None => continue, - Some(val) => return Ok(val.clone()), - } - } - - Err(self.error(ErrorKind::UnknownDynamicVariable(ident.to_string()))) - } - - /// Populate the upvalue fields of a thunk or closure under construction. - fn populate_upvalues( - &mut self, - count: usize, - mut upvalues: impl DerefMut<Target = Upvalues>, - ) -> EvalResult<()> { - for _ in 0..count { - match self.inc_ip() { - OpCode::DataStackIdx(StackIdx(stack_idx)) => { - let idx = self.frame().stack_offset + stack_idx; - - let val = match self.stack.get(idx) { - Some(val) => val.clone(), - None => { - return Err(self.error(ErrorKind::TvixBug { - msg: "upvalue to be captured was missing on stack", - metadata: Some(Rc::new(json!({ - "ip": format!("{:#x}", self.frame().ip.0 - 1), - "stack_idx(relative)": stack_idx, - "stack_idx(absolute)": idx, - }))), - })) - } - }; - - upvalues.deref_mut().push(val); - } - - OpCode::DataUpvalueIdx(upv_idx) => { - upvalues - .deref_mut() - .push(self.frame().upvalue(upv_idx).clone()); - } - - OpCode::DataDeferredLocal(idx) => { - upvalues.deref_mut().push(Value::DeferredUpvalue(idx)); - } - - OpCode::DataCaptureWith => { - // Start the captured with_stack off of the - // current call frame's captured with_stack, ... - let mut captured_with_stack = self - .frame() - .upvalues - .with_stack() - .map(Clone::clone) - // ... or make an empty one if there isn't one already. - .unwrap_or_else(|| Vec::with_capacity(self.with_stack.len())); - - for idx in &self.with_stack { - captured_with_stack.push(self.stack[*idx].clone()); - } - - upvalues.deref_mut().set_with_stack(captured_with_stack); - } - - _ => panic!("compiler error: missing closure operand"), - } - } - - Ok(()) - } - - pub fn call_builtin(&mut self, builtin: Builtin) -> EvalResult<()> { - let builtin_name = builtin.name(); - self.observer.observe_enter_builtin(builtin_name); - - let arg = self.pop(); - let result = fallible!(self, builtin.apply(self, arg)); - - self.observer - .observe_exit_builtin(builtin_name, &self.stack); - - self.push(result); - - Ok(()) - } -} - -pub fn run_lambda( - nix_search_path: NixSearchPath, - io_handle: Box<dyn EvalIO>, - observer: &mut dyn RuntimeObserver, - globals: Rc<GlobalsMap>, - lambda: Rc<Lambda>, -) -> EvalResult<RuntimeResult> { - let mut vm = VM::new(nix_search_path, io_handle, observer, globals); - - // Retain the top-level span of the expression in this lambda, as - // synthetic "calls" in deep_force will otherwise not have a span - // to fall back to. - // - // We exploit the fact that the compiler emits a final instruction - // with the span of the entire file for top-level expressions. - let root_span = lambda.chunk.get_span(CodeIdx(lambda.chunk.code.len() - 1)); - - vm.enter_frame(lambda, Rc::new(Upvalues::with_capacity(0)), 0)?; - let value = vm.pop(); - - value - .deep_force(&mut vm, &mut Default::default()) - .map_err(|kind| Error::new(kind, root_span))?; - - Ok(RuntimeResult { - value, - warnings: vm.warnings, - }) -} diff --git a/tvix/eval/src/vm/generators.rs b/tvix/eval/src/vm/generators.rs index 2a6a8fa730d8..df1696f08d5c 100644 --- a/tvix/eval/src/vm/generators.rs +++ b/tvix/eval/src/vm/generators.rs @@ -136,7 +136,6 @@ impl Display for GeneratorRequest { GeneratorRequest::StringCoerce(v, kind) => match kind { CoercionKind::Weak => write!(f, "weak_string_coerce({})", v), CoercionKind::Strong => write!(f, "strong_string_coerce({})", v), - CoercionKind::ThunksOnly => todo!("remove this branch (not live)"), }, GeneratorRequest::Call(v) => write!(f, "call({})", v), GeneratorRequest::EnterLambda { lambda, .. } => { @@ -211,6 +210,240 @@ pub fn pin_generator( 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, span: LightSpan, generator: Generator) { + self.frames.push(Frame::Generator { + generator, + span, + state: GeneratorState::AwaitingValue, + }); + } + + /// Helper function to enqueue a new generator. + pub(super) fn enqueue_generator<F, G>(&mut self, span: LightSpan, gen: G) + where + F: Future<Output = Result<Value, ErrorKind>> + 'static, + G: FnOnce(GenCo) -> F, + { + self.frames.push(Frame::Generator { + 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, + span: LightSpan, + frame_id: usize, + state: GeneratorState, + mut generator: Generator, + initial_message: Option<GeneratorResponse>, + ) -> 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) => GeneratorResponse::Empty, + + // If control returned here, and the generator is + // awaiting a value, send it the top of the stack. + (_, GeneratorState::AwaitingValue) => GeneratorResponse::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(&request); + + match request { + GeneratorRequest::StackPush(value) => { + self.stack.push(value); + message = GeneratorResponse::Empty; + } + + GeneratorRequest::StackPop => { + message = GeneratorResponse::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. + GeneratorRequest::ForceValue(value) => { + self.reenqueue_generator(span.clone(), generator); + self.enqueue_generator(span, |co| value.force(co)); + return Ok(false); + } + + // Generator has requested a deep-force. + GeneratorRequest::DeepForceValue(value, thunk_set) => { + self.reenqueue_generator(span.clone(), generator); + self.enqueue_generator(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. + GeneratorRequest::WithValue(idx) => { + self.reenqueue_generator(span.clone(), generator); + + let value = self.stack[self.with_stack[idx]].clone(); + self.enqueue_generator(span, |co| value.force(co)); + + 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. + GeneratorRequest::CapturedWithValue(idx) => { + self.reenqueue_generator(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(span, |co| value.force(co)); + + return Ok(false); + } + + GeneratorRequest::NixEquality(values, ptr_eq) => { + let values = *values; + self.reenqueue_generator(span.clone(), generator); + self.enqueue_generator(span, |co| { + values.0.nix_eq(values.1, co, ptr_eq) + }); + return Ok(false); + } + + GeneratorRequest::StringCoerce(val, kind) => { + self.reenqueue_generator(span.clone(), generator); + self.enqueue_generator(span, |co| val.coerce_to_string(co, kind)); + return Ok(false); + } + + GeneratorRequest::Call(callable) => { + self.reenqueue_generator(span.clone(), generator); + self.tail_call_value(span, None, callable)?; + return Ok(false); + } + + GeneratorRequest::EnterLambda { + lambda, + upvalues, + light_span, + } => { + self.reenqueue_generator(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); + } + + GeneratorRequest::EmitWarning(kind) => { + self.emit_warning(kind); + message = GeneratorResponse::Empty; + } + + GeneratorRequest::ImportCacheLookup(path) => { + if let Some(cached) = self.import_cache.get(&path) { + message = GeneratorResponse::Value(cached.clone()); + } else { + message = GeneratorResponse::Empty; + } + } + + GeneratorRequest::ImportCachePut(path, value) => { + self.import_cache.insert(path, value); + message = GeneratorResponse::Empty; + } + + GeneratorRequest::PathImport(path) => { + let imported = self + .io_handle + .import_path(&path) + .map_err(|kind| Error::new(kind, span.span()))?; + + message = GeneratorResponse::Path(imported); + } + + GeneratorRequest::ReadToString(path) => { + let content = self + .io_handle + .read_to_string(path) + .map_err(|kind| Error::new(kind, span.span()))?; + + message = GeneratorResponse::Value(Value::String(content.into())) + } + + GeneratorRequest::PathExists(path) => { + let exists = self + .io_handle + .path_exists(path) + .map(Value::Bool) + .map_err(|kind| Error::new(kind, span.span()))?; + + message = GeneratorResponse::Value(exists); + } + + GeneratorRequest::ReadDir(path) => { + let dir = self + .io_handle + .read_dir(path) + .map_err(|kind| Error::new(kind, span.span()))?; + + message = GeneratorResponse::Directory(dir); + } + + GeneratorRequest::Span => { + message = GeneratorResponse::Span(self.reasonable_light_span()); + } + + GeneratorRequest::TryForce(value) => { + self.try_eval_frames.push(frame_id); + self.reenqueue_generator(span.clone(), generator); + + debug_assert!( + self.frames.len() == frame_id + 1, + "generator should be reenqueued with the same frame ID" + ); + + self.enqueue_generator(span, |co| value.force(co)); + return Ok(false); + } + } + } + + // Generator has completed, and its result value should + // be left on the stack. + genawaiter::GeneratorState::Complete(result) => { + let value = result.map_err(|kind| Error::new(kind, span.span()))?; + self.stack.push(value); + return Ok(true); + } + } + } + } +} + pub type GenCo = Co<GeneratorRequest, GeneratorResponse>; // -- Implementation of concrete generator use-cases. @@ -335,28 +568,6 @@ pub async fn request_deep_force(co: &GenCo, val: Value, thunk_set: SharedThunkSe } } -/// Fetch and force a value on the with-stack from the VM. -async fn fetch_forced_with(co: &GenCo, idx: usize) -> Value { - match co.yield_(GeneratorRequest::WithValue(idx)).await { - GeneratorResponse::Value(value) => value, - msg => panic!( - "Tvix bug: VM responded with incorrect generator message: {}", - msg - ), - } -} - -/// Fetch and force a value on the *captured* with-stack from the VM. -async fn fetch_captured_with(co: &GenCo, idx: usize) -> Value { - match co.yield_(GeneratorRequest::CapturedWithValue(idx)).await { - GeneratorResponse::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, @@ -486,34 +697,6 @@ pub(crate) async fn request_span(co: &GenCo) -> LightSpan { } } -pub(crate) async fn neo_resolve_with( - co: GenCo, - ident: String, - vm_with_len: usize, - upvalue_with_len: usize, -) -> Result<Value, ErrorKind> { - for with_stack_idx in (0..vm_with_len).rev() { - // TODO(tazjin): is this branch still live with the current with-thunking? - let with = fetch_forced_with(&co, with_stack_idx).await; - - match with.to_attrs()?.select(&ident) { - None => continue, - Some(val) => return Ok(val.clone()), - } - } - - for upvalue_with_idx in (0..upvalue_with_len).rev() { - let with = fetch_captured_with(&co, upvalue_with_idx).await; - - match with.to_attrs()?.select(&ident) { - None => continue, - Some(val) => return Ok(val.clone()), - } - } - - Err(ErrorKind::UnknownDynamicVariable(ident)) -} - /// 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. diff --git a/tvix/eval/src/vm/macros.rs b/tvix/eval/src/vm/macros.rs new file mode 100644 index 000000000000..4c027b0f6440 --- /dev/null +++ b/tvix/eval/src/vm/macros.rs @@ -0,0 +1,70 @@ +/// This module provides macros which are used in the implementation +/// of the VM for the implementation of repetitive operations. + +/// This macro simplifies the implementation of arithmetic operations, +/// correctly handling the behaviour on different pairings of number +/// types. +#[macro_export] +macro_rules! arithmetic_op { + ( $self:ident, $op:tt ) => {{ // TODO: remove + let b = $self.pop(); + let a = $self.pop(); + let result = fallible!($self, arithmetic_op!(&a, &b, $op)); + $self.push(result); + }}; + + ( $a:expr, $b:expr, $op:tt ) => {{ + match ($a, $b) { + (Value::Integer(i1), Value::Integer(i2)) => Ok(Value::Integer(i1 $op i2)), + (Value::Float(f1), Value::Float(f2)) => Ok(Value::Float(f1 $op f2)), + (Value::Integer(i1), Value::Float(f2)) => Ok(Value::Float(*i1 as f64 $op f2)), + (Value::Float(f1), Value::Integer(i2)) => Ok(Value::Float(f1 $op *i2 as f64)), + + (v1, v2) => Err(ErrorKind::TypeError { + expected: "number (either int or float)", + actual: if v1.is_number() { + v2.type_of() + } else { + v1.type_of() + }, + }), + } + }}; +} + +/// This macro simplifies the implementation of comparison operations. +#[macro_export] +macro_rules! cmp_op { + ( $vm:ident, $frame:ident, $span:ident, $op:tt ) => {{ + let b = $vm.stack_pop(); + let a = $vm.stack_pop(); + + async fn compare(a: Value, b: Value, co: GenCo) -> Result<Value, ErrorKind> { + let a = generators::request_force(&co, a).await; + let b = generators::request_force(&co, b).await; + let ordering = a.nix_cmp_ordering(b, co).await?; + Ok(Value::Bool(cmp_op!(@order $op ordering))) + } + + let gen_span = $frame.current_light_span(); + $vm.push_call_frame($span, $frame); + $vm.enqueue_generator(gen_span, |co| compare(a, b, co)); + return Ok(false); + }}; + + (@order < $ordering:expr) => { + $ordering == Some(Ordering::Less) + }; + + (@order > $ordering:expr) => { + $ordering == Some(Ordering::Greater) + }; + + (@order <= $ordering:expr) => { + !matches!($ordering, None | Some(Ordering::Greater)) + }; + + (@order >= $ordering:expr) => { + !matches!($ordering, None | Some(Ordering::Less)) + }; +} diff --git a/tvix/eval/src/vm/mod.rs b/tvix/eval/src/vm/mod.rs new file mode 100644 index 000000000000..4d38707ba023 --- /dev/null +++ b/tvix/eval/src/vm/mod.rs @@ -0,0 +1,1120 @@ +//! This module implements the abstract/virtual machine that runs Tvix +//! bytecode. +//! +//! The operation of the VM is facilitated by the [`Frame`] type, +//! which controls the current execution state of the VM and is +//! processed within the VM's operating loop. +//! +//! A [`VM`] is used by instantiating it with an initial [`Frame`], +//! then triggering its execution and waiting for the VM to return or +//! yield an error. + +pub mod generators; +mod macros; + +use serde_json::json; +use std::{cmp::Ordering, collections::HashMap, ops::DerefMut, path::PathBuf, rc::Rc}; + +use crate::{ + arithmetic_op, + chunk::Chunk, + cmp_op, + compiler::GlobalsMap, + errors::{Error, ErrorKind, EvalResult}, + io::EvalIO, + nix_search_path::NixSearchPath, + observer::RuntimeObserver, + opcode::{CodeIdx, Count, JumpOffset, OpCode, StackIdx, UpvalueIdx}, + spans::LightSpan, + upvalues::Upvalues, + value::{ + Builtin, BuiltinResult, Closure, CoercionKind, Lambda, NixAttrs, NixList, PointerEquality, + SharedThunkSet, Thunk, Value, + }, + vm::generators::GenCo, + warnings::{EvalWarning, WarningKind}, +}; + +use generators::{call_functor, Generator, GeneratorState}; + +use self::generators::{GeneratorRequest, GeneratorResponse}; + +/// Internal helper trait for ergonomically converting from a `Result<T, +/// ErrorKind>` to a `Result<T, Error>` using the current span of a call frame. +trait WithSpan<T> { + fn with_span(self, frame: &CallFrame) -> Result<T, Error>; +} + +impl<T> WithSpan<T> for Result<T, ErrorKind> { + fn with_span(self, frame: &CallFrame) -> Result<T, Error> { + self.map_err(|kind| frame.error(kind)) + } +} + +struct CallFrame { + /// The lambda currently being executed. + lambda: Rc<Lambda>, + + /// Optional captured upvalues of this frame (if a thunk or + /// closure if being evaluated). + upvalues: Rc<Upvalues>, + + /// Instruction pointer to the instruction currently being + /// executed. + ip: CodeIdx, + + /// Stack offset, i.e. the frames "view" into the VM's full stack. + stack_offset: usize, +} + +impl CallFrame { + /// Retrieve an upvalue from this frame at the given index. + fn upvalue(&self, idx: UpvalueIdx) -> &Value { + &self.upvalues[idx] + } + + /// Borrow the chunk of this frame's lambda. + fn chunk(&self) -> &Chunk { + &self.lambda.chunk + } + + /// Increment this frame's instruction pointer and return the operation that + /// the pointer moved past. + fn inc_ip(&mut self) -> OpCode { + let op = self.chunk()[self.ip]; + self.ip += 1; + op + } + + /// Construct an error from the given ErrorKind and the source span of the + /// current instruction. + pub fn error(&self, kind: ErrorKind) -> Error { + Error::new(kind, self.chunk().get_span(self.ip - 1)) + } + + /// Returns the information needed to calculate the current span, + /// but without performing that calculation. + // TODO: why pub? + pub(crate) fn current_light_span(&self) -> LightSpan { + LightSpan::new_delayed(self.lambda.clone(), self.ip - 1) + } +} + +/// A frame represents an execution state of the VM. The VM has a stack of +/// frames representing the nesting of execution inside of the VM, and operates +/// on the frame at the top. +/// +/// When a frame has been fully executed, it is removed from the VM's frame +/// stack and expected to leave a result [`Value`] on the top of the stack. +enum Frame { + /// CallFrame represents the execution of Tvix bytecode within a thunk, + /// function or closure. + CallFrame { + /// The call frame itself, separated out into another type to pass it + /// around easily. + call_frame: CallFrame, + + /// Span from which the call frame was launched. + span: LightSpan, + }, + + /// Generator represents a frame that can yield further + /// instructions to the VM while its execution is being driven. + /// + /// A generator is essentially an asynchronous function that can + /// be suspended while waiting for the VM to do something (e.g. + /// thunk forcing), and resume at the same point. + Generator { + /// Span from which the generator was launched. + span: LightSpan, + + state: GeneratorState, + + /// Generator itself, which can be resumed with `.resume()`. + generator: Generator, + }, +} + +impl Frame { + pub fn span(&self) -> LightSpan { + match self { + Frame::CallFrame { span, .. } | Frame::Generator { span, .. } => span.clone(), + } + } +} + +pub struct VM<'o> { + /// VM's frame stack, representing the execution contexts the VM is working + /// through. Elements are usually pushed when functions are called, or + /// thunks are being forced. + frames: Vec<Frame>, + + /// The VM's top-level value stack. Within this stack, each code-executing + /// frame holds a "view" of the stack representing the slice of the + /// top-level stack that is relevant to its operation. This is done to avoid + /// allocating a new `Vec` for each frame's stack. + pub(crate) stack: Vec<Value>, + + /// Stack indices (absolute indexes into `stack`) of attribute + /// sets from which variables should be dynamically resolved + /// (`with`). + with_stack: Vec<usize>, + + /// Runtime warnings collected during evaluation. + warnings: Vec<EvalWarning>, + + /// Import cache, mapping absolute file paths to the value that + /// they compile to. Note that this reuses thunks, too! + // TODO: should probably be based on a file hash + pub import_cache: Box<HashMap<PathBuf, Value>>, + + /// Parsed Nix search path, which is used to resolve `<...>` + /// references. + nix_search_path: NixSearchPath, + + /// Implementation of I/O operations used for impure builtins and + /// features like `import`. + io_handle: Box<dyn EvalIO>, + + /// Runtime observer which can print traces of runtime operations. + observer: &'o mut dyn RuntimeObserver, + + /// Strong reference to the globals, guaranteeing that they are + /// kept alive for the duration of evaluation. + /// + /// This is important because recursive builtins (specifically + /// `import`) hold a weak reference to the builtins, while the + /// original strong reference is held by the compiler which does + /// not exist anymore at runtime. + #[allow(dead_code)] + globals: Rc<GlobalsMap>, + + /// A reasonably applicable span that can be used for errors in each + /// execution situation. + /// + /// The VM should update this whenever control flow changes take place (i.e. + /// entering or exiting a frame to yield control somewhere). + reasonable_span: LightSpan, + + /// This field is responsible for handling `builtins.tryEval`. When that + /// builtin is encountered, it sends a special message to the VM which + /// pushes the frame index that requested to be informed of catchable + /// errors in this field. + /// + /// The frame stack is then laid out like this: + /// + /// ```notrust + /// ┌──┬──────────────────────────┐ + /// │ 0│ `Result`-producing frame │ + /// ├──┼──────────────────────────┤ + /// │-1│ `builtins.tryEval` frame │ + /// ├──┼──────────────────────────┤ + /// │..│ ... other frames ... │ + /// └──┴──────────────────────────┘ + /// ``` + /// + /// Control is yielded to the outer VM loop, which evaluates the next frame + /// and returns the result itself to the `builtins.tryEval` frame. + try_eval_frames: Vec<usize>, +} + +impl<'o> VM<'o> { + pub fn new( + nix_search_path: NixSearchPath, + io_handle: Box<dyn EvalIO>, + observer: &'o mut dyn RuntimeObserver, + globals: Rc<GlobalsMap>, + reasonable_span: LightSpan, + ) -> Self { + // Backtrace-on-stack-overflow is some seriously weird voodoo and + // very unsafe. This double-guard prevents it from accidentally + // being enabled on release builds. + #[cfg(debug_assertions)] + #[cfg(feature = "backtrace_overflow")] + unsafe { + backtrace_on_stack_overflow::enable(); + }; + + Self { + nix_search_path, + io_handle, + observer, + globals, + reasonable_span, + frames: vec![], + stack: vec![], + with_stack: vec![], + warnings: vec![], + import_cache: Default::default(), + try_eval_frames: vec![], + } + } + + /// Push a call frame onto the frame stack. + fn push_call_frame(&mut self, span: LightSpan, call_frame: CallFrame) { + self.frames.push(Frame::CallFrame { span, call_frame }) + } + + /// Run the VM's primary (outer) execution loop, continuing execution based + /// on the current frame at the top of the frame stack. + fn execute(mut self) -> EvalResult<RuntimeResult> { + let mut catchable_error_occurred = false; + + while let Some(frame) = self.frames.pop() { + self.reasonable_span = frame.span(); + let frame_id = self.frames.len(); + + match frame { + Frame::CallFrame { call_frame, span } => { + self.observer + .observe_enter_call_frame(0, &call_frame.lambda, frame_id); + + match self.execute_bytecode(span, call_frame) { + Ok(true) => self.observer.observe_exit_call_frame(frame_id, &self.stack), + Ok(false) => self + .observer + .observe_suspend_call_frame(frame_id, &self.stack), + + Err(err) => { + if let Some(catching_frame_idx) = self.try_eval_frames.pop() { + if err.kind.is_catchable() { + self.observer.observe_exit_call_frame(frame_id, &self.stack); + catchable_error_occurred = true; + + // truncate the frame stack back to the + // frame that can catch this error + self.frames.truncate(/* len = */ catching_frame_idx + 1); + continue; + } + } + + return Err(err); + } + }; + } + + // Handle generator frames, which can request thunk forcing + // during their execution. + Frame::Generator { + span, + state, + generator, + } => { + self.observer.observe_enter_generator(frame_id, &self.stack); + + let initial_msg = if catchable_error_occurred { + catchable_error_occurred = false; + Some(GeneratorResponse::ForceError) + } else { + None + }; + + match self.run_generator(span, frame_id, state, generator, initial_msg) { + Ok(true) => self.observer.observe_exit_generator(frame_id, &self.stack), + Ok(false) => self + .observer + .observe_suspend_generator(frame_id, &self.stack), + + Err(err) => { + if let Some(catching_frame_idx) = self.try_eval_frames.pop() { + if err.kind.is_catchable() { + self.observer.observe_exit_generator(frame_id, &self.stack); + catchable_error_occurred = true; + + // truncate the frame stack back to the + // frame that can catch this error + self.frames.truncate(/* len = */ catching_frame_idx + 1); + continue; + } + } + + return Err(err); + } + }; + } + } + } + + // Once no more frames are present, return the stack's top value as the + // result. + Ok(RuntimeResult { + value: self + .stack + .pop() + .expect("tvix bug: runtime stack empty after execution"), + + warnings: self.warnings, + }) + } + + /// Run the VM's inner execution loop, processing Tvix bytecode from a + /// chunk. This function returns if: + /// + /// 1. The code has run to the end, and has left a value on the top of the + /// stack. In this case, the frame is not returned to the frame stack. + /// + /// 2. The code encounters a generator, in which case the frame in its + /// current state is pushed back on the stack, and the generator is left on + /// top of it for the outer loop to execute. + /// + /// 3. An error is encountered. + /// + /// This function *must* ensure that it leaves the frame stack in the + /// correct order, especially when re-enqueuing a frame to execute. + /// + /// The return value indicates whether the bytecode has been executed to + /// completion, or whether it has been suspended in favour of a generator. + fn execute_bytecode(&mut self, span: LightSpan, mut frame: CallFrame) -> EvalResult<bool> { + loop { + let op = frame.inc_ip(); + self.observer.observe_execute_op(frame.ip, &op, &self.stack); + + // TODO: might be useful to reorder ops with most frequent ones first + match op { + // Discard the current frame. + OpCode::OpReturn => { + return Ok(true); + } + + OpCode::OpConstant(idx) => { + let c = frame.chunk()[idx].clone(); + self.stack.push(c); + } + + OpCode::OpPop => { + self.stack.pop(); + } + + OpCode::OpAdd => { + let b = self.stack_pop(); + let a = self.stack_pop(); + + let gen_span = frame.current_light_span(); + self.push_call_frame(span, frame); + + // OpAdd can add not just numbers, but also string-like + // things, which requires more VM logic. This operation is + // evaluated in a generator frame. + self.enqueue_generator(gen_span, |co| add_values(co, a, b)); + return Ok(false); + } + + OpCode::OpSub => { + let b = self.stack_pop(); + let a = self.stack_pop(); + let result = arithmetic_op!(&a, &b, -).with_span(&frame)?; + self.stack.push(result); + } + + OpCode::OpMul => { + let b = self.stack_pop(); + let a = self.stack_pop(); + let result = arithmetic_op!(&a, &b, *).with_span(&frame)?; + self.stack.push(result); + } + + OpCode::OpDiv => { + let b = self.stack_pop(); + + match b { + Value::Integer(0) => return Err(frame.error(ErrorKind::DivisionByZero)), + Value::Float(b) if b == 0.0_f64 => { + return Err(frame.error(ErrorKind::DivisionByZero)) + } + _ => {} + }; + + let a = self.stack_pop(); + let result = arithmetic_op!(&a, &b, /).with_span(&frame)?; + self.stack.push(result); + } + + OpCode::OpInvert => { + let v = self.stack_pop().as_bool().with_span(&frame)?; + self.stack.push(Value::Bool(!v)); + } + + OpCode::OpNegate => match self.stack_pop() { + Value::Integer(i) => self.stack.push(Value::Integer(-i)), + Value::Float(f) => self.stack.push(Value::Float(-f)), + v => { + return Err(frame.error(ErrorKind::TypeError { + expected: "number (either int or float)", + actual: v.type_of(), + })); + } + }, + + OpCode::OpEqual => { + let b = self.stack_pop(); + let a = self.stack_pop(); + let gen_span = frame.current_light_span(); + self.push_call_frame(span, frame); + self.enqueue_generator(gen_span, |co| { + a.nix_eq(b, co, PointerEquality::ForbidAll) + }); + return Ok(false); + } + + OpCode::OpLess => cmp_op!(self, frame, span, <), + OpCode::OpLessOrEq => cmp_op!(self, frame, span, <=), + OpCode::OpMore => cmp_op!(self, frame, span, >), + OpCode::OpMoreOrEq => cmp_op!(self, frame, span, >=), + + OpCode::OpAttrs(Count(count)) => self.run_attrset(&frame, count)?, + + OpCode::OpAttrsUpdate => { + let rhs = self.stack_pop().to_attrs().with_span(&frame)?; + let lhs = self.stack_pop().to_attrs().with_span(&frame)?; + + self.stack.push(Value::attrs(lhs.update(*rhs))) + } + + OpCode::OpAttrsSelect => { + let key = self.stack_pop().to_str().with_span(&frame)?; + let attrs = self.stack_pop().to_attrs().with_span(&frame)?; + + match attrs.select(key.as_str()) { + Some(value) => self.stack.push(value.clone()), + + None => { + return Err(frame.error(ErrorKind::AttributeNotFound { + name: key.as_str().to_string(), + })) + } + } + } + + OpCode::OpAttrsTrySelect => { + let key = self.stack_pop().to_str().with_span(&frame)?; + let value = match self.stack_pop() { + Value::Attrs(attrs) => match attrs.select(key.as_str()) { + Some(value) => value.clone(), + None => Value::AttrNotFound, + }, + + _ => Value::AttrNotFound, + }; + + self.stack.push(value); + } + + OpCode::OpHasAttr => { + let key = self.stack_pop().to_str().with_span(&frame)?; + let result = match self.stack_pop() { + Value::Attrs(attrs) => attrs.contains(key.as_str()), + + // Nix allows use of `?` on non-set types, but + // always returns false in those cases. + _ => false, + }; + + self.stack.push(Value::Bool(result)); + } + + OpCode::OpValidateClosedFormals => { + let formals = frame.lambda.formals.as_ref().expect( + "OpValidateClosedFormals called within the frame of a lambda without formals", + ); + + let args = self.stack_peek(0).to_attrs().with_span(&frame)?; + for arg in args.keys() { + if !formals.contains(arg) { + return Err(frame.error(ErrorKind::UnexpectedArgument { + arg: arg.clone(), + formals_span: formals.span, + })); + } + } + } + + OpCode::OpList(Count(count)) => { + let list = + NixList::construct(count, self.stack.split_off(self.stack.len() - count)); + + self.stack.push(Value::List(list)); + } + + OpCode::OpConcat => { + let rhs = self.stack_pop().to_list().with_span(&frame)?.into_inner(); + let lhs = self.stack_pop().to_list().with_span(&frame)?.into_inner(); + self.stack.push(Value::List(NixList::from(lhs + rhs))) + } + + OpCode::OpInterpolate(Count(count)) => self.run_interpolate(&frame, count)?, + + OpCode::OpCoerceToString => { + let value = self.stack_pop(); + let gen_span = frame.current_light_span(); + self.push_call_frame(span, frame); + + self.enqueue_generator(gen_span, |co| { + value.coerce_to_string(co, CoercionKind::Weak) + }); + + return Ok(false); + } + + OpCode::OpFindFile => match self.stack_pop() { + Value::UnresolvedPath(path) => { + let resolved = self.nix_search_path.resolve(path).with_span(&frame)?; + self.stack.push(resolved.into()); + } + + _ => panic!("tvix compiler bug: OpFindFile called on non-UnresolvedPath"), + }, + + OpCode::OpResolveHomePath => match self.stack_pop() { + Value::UnresolvedPath(path) => { + match dirs::home_dir() { + None => { + return Err(frame.error(ErrorKind::RelativePathResolution( + "failed to determine home directory".into(), + ))); + } + Some(mut buf) => { + buf.push(path); + self.stack.push(buf.into()); + } + }; + } + + _ => { + panic!("tvix compiler bug: OpResolveHomePath called on non-UnresolvedPath") + } + }, + + OpCode::OpJump(JumpOffset(offset)) => { + debug_assert!(offset != 0); + frame.ip += offset; + } + + OpCode::OpJumpIfTrue(JumpOffset(offset)) => { + debug_assert!(offset != 0); + if self.stack_peek(0).as_bool().with_span(&frame)? { + frame.ip += offset; + } + } + + OpCode::OpJumpIfFalse(JumpOffset(offset)) => { + debug_assert!(offset != 0); + if !self.stack_peek(0).as_bool().with_span(&frame)? { + frame.ip += offset; + } + } + + OpCode::OpJumpIfNotFound(JumpOffset(offset)) => { + debug_assert!(offset != 0); + if matches!(self.stack_peek(0), Value::AttrNotFound) { + self.stack_pop(); + frame.ip += offset; + } + } + + // These assertion operations error out if the stack + // top is not of the expected type. This is necessary + // to implement some specific behaviours of Nix + // exactly. + OpCode::OpAssertBool => { + let val = self.stack_peek(0); + if !val.is_bool() { + return Err(frame.error(ErrorKind::TypeError { + expected: "bool", + actual: val.type_of(), + })); + } + } + + // Remove the given number of elements from the stack, + // but retain the top value. + OpCode::OpCloseScope(Count(count)) => { + // Immediately move the top value into the right + // position. + let target_idx = self.stack.len() - 1 - count; + self.stack[target_idx] = self.stack_pop(); + + // Then drop the remaining values. + for _ in 0..(count - 1) { + self.stack.pop(); + } + } + + OpCode::OpGetLocal(StackIdx(local_idx)) => { + let idx = frame.stack_offset + local_idx; + self.stack.push(self.stack[idx].clone()); + } + + OpCode::OpPushWith(StackIdx(idx)) => self.with_stack.push(frame.stack_offset + idx), + + OpCode::OpPopWith => { + self.with_stack.pop(); + } + + OpCode::OpResolveWith => { + let ident = self.stack_pop().to_str().with_span(&frame)?; + + // Re-enqueue this frame. + let op_span = frame.current_light_span(); + self.push_call_frame(span, frame); + + // Construct a generator frame doing the lookup in constant + // stack space. + let with_stack_len = self.with_stack.len(); + let closed_with_stack_len = self + .last_call_frame() + .map(|frame| frame.upvalues.with_stack_len()) + .unwrap_or(0); + + self.enqueue_generator(op_span, |co| { + resolve_with( + co, + ident.as_str().to_owned(), + with_stack_len, + closed_with_stack_len, + ) + }); + + return Ok(false); + } + + OpCode::OpAssertFail => { + return Err(frame.error(ErrorKind::AssertionFailed)); + } + + OpCode::OpCall => { + let callable = self.stack_pop(); + self.tail_call_value(frame.current_light_span(), Some(frame), callable)?; + + // exit this loop and let the outer loop enter the new call + return Ok(true); + } + + OpCode::OpGetUpvalue(upv_idx) => { + let value = frame.upvalue(upv_idx).clone(); + self.stack.push(value); + } + + OpCode::OpClosure(idx) => { + let blueprint = match &frame.chunk()[idx] { + Value::Blueprint(lambda) => lambda.clone(), + _ => panic!("compiler bug: non-blueprint in blueprint slot"), + }; + + let upvalue_count = blueprint.upvalue_count; + debug_assert!( + upvalue_count > 0, + "OpClosure should not be called for plain lambdas" + ); + + let mut upvalues = Upvalues::with_capacity(blueprint.upvalue_count); + self.populate_upvalues(&mut frame, upvalue_count, &mut upvalues)?; + self.stack + .push(Value::Closure(Rc::new(Closure::new_with_upvalues( + Rc::new(upvalues), + blueprint, + )))); + } + + OpCode::OpThunkSuspended(idx) | OpCode::OpThunkClosure(idx) => { + let blueprint = match &frame.chunk()[idx] { + Value::Blueprint(lambda) => lambda.clone(), + _ => panic!("compiler bug: non-blueprint in blueprint slot"), + }; + + let upvalue_count = blueprint.upvalue_count; + let thunk = if matches!(op, OpCode::OpThunkClosure(_)) { + debug_assert!( + upvalue_count > 0, + "OpThunkClosure should not be called for plain lambdas" + ); + Thunk::new_closure(blueprint) + } else { + Thunk::new_suspended(blueprint, frame.current_light_span()) + }; + let upvalues = thunk.upvalues_mut(); + self.stack.push(Value::Thunk(thunk.clone())); + + // From this point on we internally mutate the + // upvalues. The closure (if `is_closure`) is + // already in its stack slot, which means that it + // can capture itself as an upvalue for + // self-recursion. + self.populate_upvalues(&mut frame, upvalue_count, upvalues)?; + } + + OpCode::OpForce => { + if let Some(Value::Thunk(_)) = self.stack.last() { + let thunk = match self.stack_pop() { + Value::Thunk(t) => t, + _ => unreachable!(), + }; + + let gen_span = frame.current_light_span(); + + self.push_call_frame(span, frame); + self.enqueue_generator(gen_span, |co| thunk.force(co)); + return Ok(false); + } + } + + OpCode::OpFinalise(StackIdx(idx)) => { + match &self.stack[frame.stack_offset + idx] { + Value::Closure(_) => panic!("attempted to finalise a closure"), + Value::Thunk(thunk) => thunk.finalise(&self.stack[frame.stack_offset..]), + + // In functions with "formals" attributes, it is + // possible for `OpFinalise` to be called on a + // non-capturing value, in which case it is a no-op. + // + // TODO: detect this in some phase and skip the finalise; fail here + _ => { /* TODO: panic here again to catch bugs */ } + } + } + + // Data-carrying operands should never be executed, + // that is a critical error in the VM/compiler. + OpCode::DataStackIdx(_) + | OpCode::DataDeferredLocal(_) + | OpCode::DataUpvalueIdx(_) + | OpCode::DataCaptureWith => { + panic!("Tvix bug: attempted to execute data-carrying operand") + } + } + } + } +} + +/// Implementation of helper functions for the runtime logic above. +impl<'o> VM<'o> { + pub(crate) fn stack_pop(&mut self) -> Value { + self.stack.pop().expect("runtime stack empty") + } + + fn stack_peek(&self, offset: usize) -> &Value { + &self.stack[self.stack.len() - 1 - offset] + } + + fn run_attrset(&mut self, frame: &CallFrame, count: usize) -> EvalResult<()> { + let attrs = NixAttrs::construct(count, self.stack.split_off(self.stack.len() - count * 2)) + .with_span(frame)?; + + self.stack.push(Value::attrs(attrs)); + Ok(()) + } + + /// Access the last call frame present in the frame stack. + fn last_call_frame(&self) -> Option<&CallFrame> { + for frame in self.frames.iter().rev() { + if let Frame::CallFrame { call_frame, .. } = frame { + return Some(call_frame); + } + } + + None + } + + /// Push an already constructed warning. + pub fn push_warning(&mut self, warning: EvalWarning) { + self.warnings.push(warning); + } + + /// Emit a warning with the given WarningKind and the source span + /// of the current instruction. + pub fn emit_warning(&mut self, _kind: WarningKind) { + // TODO: put LightSpan in warning, calculate only *after* eval + // TODO: what to do with the spans? + // self.push_warning(EvalWarning { + // kind, + // span: self.current_span(), + // }); + } + + /// Interpolate string fragments by popping the specified number of + /// fragments of the stack, evaluating them to strings, and pushing + /// the concatenated result string back on the stack. + fn run_interpolate(&mut self, frame: &CallFrame, count: usize) -> EvalResult<()> { + let mut out = String::new(); + + for _ in 0..count { + out.push_str(self.stack_pop().to_str().with_span(frame)?.as_str()); + } + + self.stack.push(Value::String(out.into())); + Ok(()) + } + + /// Returns a reasonable light span for the current situation that the VM is + /// in. + pub fn reasonable_light_span(&self) -> LightSpan { + self.reasonable_span.clone() + } + + /// Construct an error from the given ErrorKind and the source + /// span of the current instruction. + pub fn error(&self, kind: ErrorKind) -> Error { + Error::new(kind, self.reasonable_span.span()) + } + + /// Apply an argument from the stack to a builtin, and attempt to call it. + /// + /// All calls are tail-calls in Tvix, as every function application is a + /// separate thunk and OpCall is thus the last result in the thunk. + /// + /// Due to this, once control flow exits this function, the generator will + /// automatically be run by the VM. + fn call_builtin(&mut self, span: LightSpan, mut builtin: Builtin) -> EvalResult<()> { + let builtin_name = builtin.name(); + self.observer.observe_enter_builtin(builtin_name); + + builtin.apply_arg(self.stack_pop()); + + match builtin.call() { + // Partially applied builtin is just pushed back on the stack. + BuiltinResult::Partial(partial) => self.stack.push(Value::Builtin(partial)), + + // Builtin is fully applied and the generator needs to be run by the VM. + BuiltinResult::Called(generator) => self.frames.push(Frame::Generator { + generator, + span, + state: GeneratorState::Running, + }), + } + + Ok(()) + } + + fn tail_call_value( + &mut self, + span: LightSpan, + parent: Option<CallFrame>, + callable: Value, + ) -> EvalResult<()> { + match callable { + Value::Builtin(builtin) => self.call_builtin(span, builtin), + Value::Thunk(thunk) => self.tail_call_value(span, parent, thunk.value().clone()), + + Value::Closure(closure) => { + let lambda = closure.lambda(); + self.observer.observe_tail_call(self.frames.len(), &lambda); + + // The stack offset is always `stack.len() - arg_count`, and + // since this branch handles native Nix functions (which always + // take only a single argument and are curried), the offset is + // `stack_len - 1`. + let stack_offset = self.stack.len() - 1; + + self.push_call_frame( + span, + CallFrame { + lambda, + upvalues: closure.upvalues(), + ip: CodeIdx(0), + stack_offset, + }, + ); + + Ok(()) + } + + // Attribute sets with a __functor attribute are callable. + val @ Value::Attrs(_) => { + let gen_span = parent + .map(|p| p.current_light_span()) + .unwrap_or_else(|| self.reasonable_light_span()); + + self.enqueue_generator(gen_span, |co| call_functor(co, val)); + Ok(()) + } + v => Err(self.error(ErrorKind::NotCallable(v.type_of()))), + } + } + + /// Populate the upvalue fields of a thunk or closure under construction. + fn populate_upvalues( + &mut self, + frame: &mut CallFrame, + count: usize, + mut upvalues: impl DerefMut<Target = Upvalues>, + ) -> EvalResult<()> { + for _ in 0..count { + match frame.inc_ip() { + OpCode::DataStackIdx(StackIdx(stack_idx)) => { + let idx = frame.stack_offset + stack_idx; + + let val = match self.stack.get(idx) { + Some(val) => val.clone(), + None => { + return Err(frame.error(ErrorKind::TvixBug { + msg: "upvalue to be captured was missing on stack", + metadata: Some(Rc::new(json!({ + "ip": format!("{:#x}", frame.ip.0 - 1), + "stack_idx(relative)": stack_idx, + "stack_idx(absolute)": idx, + }))), + })) + } + }; + + upvalues.deref_mut().push(val); + } + + OpCode::DataUpvalueIdx(upv_idx) => { + upvalues.deref_mut().push(frame.upvalue(upv_idx).clone()); + } + + OpCode::DataDeferredLocal(idx) => { + upvalues.deref_mut().push(Value::DeferredUpvalue(idx)); + } + + OpCode::DataCaptureWith => { + // Start the captured with_stack off of the + // current call frame's captured with_stack, ... + let mut captured_with_stack = frame + .upvalues + .with_stack() + .map(Clone::clone) + // ... or make an empty one if there isn't one already. + .unwrap_or_else(|| Vec::with_capacity(self.with_stack.len())); + + for idx in &self.with_stack { + captured_with_stack.push(self.stack[*idx].clone()); + } + + upvalues.deref_mut().set_with_stack(captured_with_stack); + } + + _ => panic!("compiler error: missing closure operand"), + } + } + + Ok(()) + } +} + +/// Fetch and force a value on the with-stack from the VM. +async fn fetch_forced_with(co: &GenCo, idx: usize) -> Value { + match co.yield_(GeneratorRequest::WithValue(idx)).await { + GeneratorResponse::Value(value) => value, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +/// Fetch and force a value on the *captured* with-stack from the VM. +async fn fetch_captured_with(co: &GenCo, idx: usize) -> Value { + match co.yield_(GeneratorRequest::CapturedWithValue(idx)).await { + GeneratorResponse::Value(value) => value, + msg => panic!( + "Tvix bug: VM responded with incorrect generator message: {}", + msg + ), + } +} + +/// Resolve a dynamically bound identifier (through `with`) by looking +/// for matching values in the with-stacks carried at runtime. +async fn resolve_with( + co: GenCo, + ident: String, + vm_with_len: usize, + upvalue_with_len: usize, +) -> Result<Value, ErrorKind> { + for with_stack_idx in (0..vm_with_len).rev() { + // TODO(tazjin): is this branch still live with the current with-thunking? + let with = fetch_forced_with(&co, with_stack_idx).await; + + match with.to_attrs()?.select(&ident) { + None => continue, + Some(val) => return Ok(val.clone()), + } + } + + for upvalue_with_idx in (0..upvalue_with_len).rev() { + let with = fetch_captured_with(&co, upvalue_with_idx).await; + + match with.to_attrs()?.select(&ident) { + None => continue, + Some(val) => return Ok(val.clone()), + } + } + + Err(ErrorKind::UnknownDynamicVariable(ident)) +} + +async fn add_values(co: GenCo, a: Value, b: Value) -> Result<Value, ErrorKind> { + let result = match (a, b) { + (Value::Path(p), v) => { + let mut path = p.to_string_lossy().into_owned(); + let vs = generators::request_string_coerce(&co, v, CoercionKind::Weak).await; + path.push_str(vs.as_str()); + crate::value::canon_path(PathBuf::from(path)).into() + } + (Value::String(s1), Value::String(s2)) => Value::String(s1.concat(&s2)), + (Value::String(s1), v) => Value::String( + s1.concat(&generators::request_string_coerce(&co, v, CoercionKind::Weak).await), + ), + (v, Value::String(s2)) => Value::String( + generators::request_string_coerce(&co, v, CoercionKind::Weak) + .await + .concat(&s2), + ), + (a, b) => arithmetic_op!(&a, &b, +)?, + }; + + Ok(result) +} + +/// The result of a VM's runtime evaluation. +pub struct RuntimeResult { + pub value: Value, + pub warnings: Vec<EvalWarning>, +} + +/// Generator that retrieves the final value from the stack, and deep-forces it +/// before returning. +async fn final_deep_force(co: GenCo) -> Result<Value, ErrorKind> { + let value = generators::request_stack_pop(&co).await; + Ok(generators::request_deep_force(&co, value, SharedThunkSet::default()).await) +} + +pub fn run_lambda( + nix_search_path: NixSearchPath, + io_handle: Box<dyn EvalIO>, + observer: &mut dyn RuntimeObserver, + globals: Rc<GlobalsMap>, + lambda: Rc<Lambda>, +) -> EvalResult<RuntimeResult> { + // Retain the top-level span of the expression in this lambda, as + // synthetic "calls" in deep_force will otherwise not have a span + // to fall back to. + // + // We exploit the fact that the compiler emits a final instruction + // with the span of the entire file for top-level expressions. + let root_span = lambda.chunk.get_span(CodeIdx(lambda.chunk.code.len() - 1)); + + let mut vm = VM::new( + nix_search_path, + io_handle, + observer, + globals, + root_span.into(), + ); + + // Synthesise a frame that will instruct the VM to deep-force the final + // value before returning it. + vm.enqueue_generator(root_span.into(), final_deep_force); + + vm.frames.push(Frame::CallFrame { + span: root_span.into(), + call_frame: CallFrame { + lambda, + upvalues: Rc::new(Upvalues::with_capacity(0)), + ip: CodeIdx(0), + stack_offset: 0, + }, + }); + + vm.execute() +} |