about summary refs log tree commit diff
AgeCommit message (Collapse)AuthorFilesLines
2023-03-15 r/6009 refactor(tvix/nix-compat): -derivation::Hash, +NixHashFlorian Klink8-87/+201
This stops using our own custom Hash structure, which was mostly only used because we had to parse the JSON representation somehow. Since cl/8217, there's a `NixHash` struct, which is better suited to hold this data. Converting the format requires a bit of serde labor though, but that only really matters when interacting with JSON representations (which we mostly don't). Change-Id: Idc5ee511e36e6726c71f66face8300a441b0bf4c Reviewed-on: https://cl.tvl.fyi/c/depot/+/8304 Autosubmit: flokli <flokli@flokli.de> Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su>
2023-03-14 r/6008 style(tvix): add new logo to the Tvix READMEVincent Ambo1-2/+5
Change-Id: Ibb8061be75d6fd16e8f813bc94e3bacaae890454 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8309 Tested-by: BuildkiteCI Autosubmit: tazjin <tazjin@tvl.su> Reviewed-by: flokli <flokli@flokli.de>
2023-03-14 r/6007 chore(tvix/store): drop separate bin packageFlorian Klink5-29/+8
Apparently, having multiple packages with the same path is a bad thing: ``` The bin target `tvix-store` in package `tvix-store-bin v0.1.0 (/home/flokli/tvl/tvix/store)` has the same output filename as the lib target `tvix_store` in package `tvix-store-bin v0.1.0 (/home/flokli/tvl/tvix/store)`. Colliding filename is: /home/flokli/tvl/tvix/target/doc/tvix_store/index.html The output filenames should be unique. This is a known bug where multiple crates with the same name use the same path; see <https://github.com/rust-lang/cargo/issues/6313>. ``` Change-Id: Ic785c0349070783baf5e8fd23f5fb60603a3c995 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8308 Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su>
2023-03-14 r/6006 fix(tvix): build all tvix crate docsFlorian Klink1-1/+3
There's still some shadowing going on, but that's left for a followup CL. Change-Id: I02992f1eb494faca99857a3a5ee4dcd47f1b9fd0 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8306 Reviewed-by: tazjin <tazjin@tvl.su> Autosubmit: flokli <flokli@flokli.de> Tested-by: BuildkiteCI
2023-03-14 r/6005 feat(ops): serve Tvix website & docs on (docs.)tvix.devVincent Ambo2-0/+40
Change-Id: I198ea197867f9b9a48e51665d0665f722202e02e Reviewed-on: https://cl.tvl.fyi/c/depot/+/8299 Reviewed-by: flokli <flokli@flokli.de> Autosubmit: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI
2023-03-14 r/6004 feat(tvix): build (some of) our Rust documentation in NixVincent Ambo1-1/+32
This will be published on docs.tvix.dev Change-Id: I348e057351d5295ad20953c9e9a32c257abab089 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8298 Tested-by: BuildkiteCI Reviewed-by: flokli <flokli@flokli.de>
2023-03-14 r/6003 feat(ops/glesys): add CNAME for docs.tvix.devVincent Ambo1-0/+7
Change-Id: Ie1994ac4d14344c82ae184f4e3cd9f5292d96c84 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8297 Reviewed-by: flokli <flokli@flokli.de> Tested-by: BuildkiteCI
2023-03-14 r/6002 feat(tvix): add simple initial websiteVincent Ambo3-0/+68
The website itself contains no useful information that we don't already have published anywhere, but it's a decent landing place. Mostly I want to have something on the root of tvix.dev, so that we can start using it for other purposes. Change-Id: Id2b4dabc7f6e4dd26b61484b86dbde2f39aa1719 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8296 Tested-by: BuildkiteCI Reviewed-by: flokli <flokli@flokli.de>
2023-03-14 r/6001 feat(ops/glesys): point tvix.dev at whitbyVincent Ambo1-0/+40
Change-Id: Ied022e6c1a8039a9db375a8593afb76edcaa6dbd Reviewed-on: https://cl.tvl.fyi/c/depot/+/8295 Reviewed-by: flokli <flokli@flokli.de> Reviewed-by: tazjin <tazjin@tvl.su> Autosubmit: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI
2023-03-14 r/6000 refactor(tvix/nix-compat): rename helper funcFlorian Klink1-3/+3
This only trims the output paths from a Derivation struct, not the output hashes. Change-Id: I9250fec4602ed05bb64540c4a89ddb6fb052be1f Reviewed-on: https://cl.tvl.fyi/c/depot/+/8303 Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su> Autosubmit: flokli <flokli@flokli.de>
2023-03-14 r/5999 refactor(tvix/nix-compat): remove manual mapFlorian Klink1-8/+6
Change-Id: I1652e24c9be28112d98683de2d2db51dc46001ed Reviewed-on: https://cl.tvl.fyi/c/depot/+/8302 Reviewed-by: tazjin <tazjin@tvl.su> Autosubmit: flokli <flokli@flokli.de> Tested-by: BuildkiteCI
2023-03-14 r/5998 refactor(tvix/nix-compat): rename test nameFlorian Klink1-1/+1
Change-Id: Ia6af8d4b53fbd4d9ea26f0094cd98dde66a91f78 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8301 Autosubmit: flokli <flokli@flokli.de> Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI
2023-03-14 r/5997 fix(tvix/store/derivation): fix commentFlorian Klink1-1/+1
The digest is encoded in LOWERHEX here, not nixbase32. Change-Id: I8e14742f0135966424073bfdb93ada8cd7bd52e2 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8300 Tested-by: BuildkiteCI Autosubmit: flokli <flokli@flokli.de> Reviewed-by: tazjin <tazjin@tvl.su>
2023-03-14 r/5996 chore(tvix/cli): don't set COREPKGS anymoreFlorian Klink1-4/+0
Since cl/8213, tvix bundles corepkgs. Change-Id: I17fa4452a6a1d554ae67b4aed9d9b1e77cb495f5 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8305 Autosubmit: flokli <flokli@flokli.de> Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI
2023-03-14 r/5995 refactor(tvix/nix-compat): replace calculate_drv_replacement_strFlorian Klink4-71/+98
Call this function derivation_or_fod_hash, and return a NixHash. This is more in line with how cppnix calls this, and allows using to_nix_hash_string() in some places. Change-Id: Iebf5355f08ed5c9a044844739350f829f874f0ce Reviewed-on: https://cl.tvl.fyi/c/depot/+/8293 Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI
2023-03-14 r/5994 docs(tvix/eval): suggested layout adjustment to VM loop diagramAdam Joseph1-11/+11
Change-Id: I5467cd66801ad8fe6c4ec0ae337763f1762cea1c Reviewed-on: https://cl.tvl.fyi/c/depot/+/8252 Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI Autosubmit: Adam Joseph <adam@westernsemico.com>
2023-03-14 r/5993 docs(tvix/eval): document inner workings of the new VM loopVincent Ambo1-45/+284
Change-Id: I8224bf039f739c401900b5a2ddc839810c87cf6e Reviewed-on: https://cl.tvl.fyi/c/depot/+/8226 Tested-by: BuildkiteCI Reviewed-by: Adam Joseph <adam@westernsemico.com>
2023-03-14 r/5992 chore(tvix): Generator{Request|Response} -> VM{Request|Response}Vincent Ambo3-130/+121
We settled on this being the most reasonable name for this construct. Change-Id: Ic31c45461a842f22aa05f4446123fe3a61dfdbc0 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8291 Tested-by: BuildkiteCI Autosubmit: tazjin <tazjin@tvl.su> Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-13 r/5991 chore(tvix/eval): mark async functions which are called by the VMAdam Joseph3-0/+9
Given Rust's current lack of support for tail calls, we cannot avoid using `async` for builtins. This is the only way to avoid overflowing the cpu stack when we have arbitrarily deep builtin/interpreted/builtin/interpreted/... "sandwiches" There are only five `async fn` functions which are not builtins (some come in multiple "flavors"): - add_values - resolve_with - force, final_deep_force - nix_eq, nix_cmp_eq - coerce_to_string These can be written iteratively rather than recursively (and in fact nix_eq used to be written that way!). I volunteer to rewrite them. If written iteratively they would no longer need to be `async`. There are two motivations for limiting our reliance on `async` to only the situation (builtins) where we have no other choice: 1. Performance. We don't really have any good measurement of the performance hit that the Box<dyn Future>s impose on us. Right now all of our large (nixpkgs-eval) tests are swamped by the cost of other things (e.g. fork()ing `nix-store`) so we can't really measure it. Builtins tend to be expensive operations anyways (regexp-matching, sorting, etc) that are likely to already cost more than the `async` overhead. 2. Preserving the ability to switch to `musttail` calls. Clang/LLVM recently got `musttail` (mandatory-elimination tail calls). Rust has refused to add this mainly because WASM doesn't support, but WASM `tail_call` has been implemented and was recently moved to phase 4 (standardization). It is very likely that Rust will get tail calls sometime in the next year; if it does, we won't need async anymore. In the meantime, I'd like to avoid adding any further reliance on `async` in places where it wouldn't be straightforward to replace it with a tail call. https://reviews.llvm.org/D99517 https://github.com/WebAssembly/proposals/pull/157 https: //github.com/rust-lang/rfcs/issues/2691#issuecomment-1462152908 Change-Id: Id15945d5a92bf52c16d93456e3437f91d93bdc57 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8290 Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI Autosubmit: Adam Joseph <adam@westernsemico.com>
2023-03-13 r/5990 refactor(tvix/eval): reduce fetch{forced|captured}_with visibilityAdam Joseph1-22/+22
This commit moves fetch_forced_with and fetch_captured_with into the scope of their only caller (resolve_with). Change-Id: I9a8bc27228888729d591e8cb021c431b2b6468f5 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8289 Autosubmit: Adam Joseph <adam@westernsemico.com> Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI
2023-03-13 r/5989 feat(tvix/eval): rewrite nix_cmp_ordering to be nonrecursiveAdam Joseph1-45/+46
This rewrites nix_cmp_ordering as an iterative loop, which eliminates the extra pinned-boxing helper function. Change-Id: I33d0ecc913e02affd8fd4c7bc1c9ecfdf4c7deb9 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8288 Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI Autosubmit: Adam Joseph <adam@westernsemico.com>
2023-03-13 r/5988 chore(tvix/eval): prune some dependencies & featuresVincent Ambo4-597/+28
* We no longer need backtrace-on-stack-overflow, as we no longer overflow the stack with the recent eval refactorings. This was weird voodoo anyways, introduced earlier to debug some cases where stack overflows occured. * default features of genawaiter crate are not needed, as we don't use their proc macros Change-Id: I346fc5a18d7f117ee805909a8be8f535b96be76c Reviewed-on: https://cl.tvl.fyi/c/depot/+/8263 Reviewed-by: flokli <flokli@flokli.de> Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-13 r/5987 refactor(tvix/eval): reorder bytecode operations match by frequencyVincent Ambo1-265/+264
This reorders the operations in the VM's main `match` statement while evaluating bytecode according to the frequency with which these operations appear in some nixpkgs evaluations. I used raw data that looks like this: https://gist.github.com/tazjin/63d0788a78eb8575b04defaad4ef610d This has a small but noticeable impact on evaluation performance. No operations have changed in any way, this is purely moving code around. Change-Id: Iaa4ef4f0577e98144e8905fec88149c41e8c315c Reviewed-on: https://cl.tvl.fyi/c/depot/+/8262 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Reviewed-by: flokli <flokli@flokli.de> Tested-by: BuildkiteCI
2023-03-13 r/5986 chore(tvix/cli): silence useless warningVincent Ambo1-0/+1
Change-Id: I18f567d5dcbbeb934428bf9111eb5fae5fef0342 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8261 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Tested-by: BuildkiteCI Reviewed-by: flokli <flokli@flokli.de>
2023-03-13 r/5985 docs(tvix/eval): fix reference to `Empty` message in a commentVincent Ambo1-1/+1
Change-Id: I3dc30cca33fbbd8e8686655635ee471f5937d9f8 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8257 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-13 r/5984 refactor(tvix/eval): rename VM::tail_call_value -> VM::call_valueVincent Ambo2-4/+4
The name of this was not accurate anymore after all the recent shuffling, as noted by amjoseph. Conceptual tail calls here only occur for Nix bytecode calling Nix bytecode, but things like a builtin call actually push a new native frame. Change-Id: I1dea8c9663daf86482b8c7b5a23133254b5ca321 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8256 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-13 r/5983 fix(tvix/eval): emit warnings from builtins.import againVincent Ambo3-14/+35
Wires up generator logic to emit warnings that already have spans attached again. Change-Id: I9f878cec3b9d4f6f7819e7c71bab7ae70bd3f08b Reviewed-on: https://cl.tvl.fyi/c/depot/+/8224 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-13 r/5982 fix(tvix/eval): more closely line up path resolution with cppnixVincent Ambo2-23/+51
... except now the tests fail, but at least it works Change-Id: I05e86c173f40533ae65548585c1ddaa200ac5235 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8214 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Tested-by: BuildkiteCI
2023-03-13 r/5981 feat(tvix/cli): bundle corepkgs/fetchurl.nix with tvix-cliVincent Ambo3-1/+76
This file which ships with C++ Nix is required for evaluating nixpkgs. Like C++ Nix, we now inject a pseudo path in EvalIO from which this will resolve as <nix/fetchurl.nix> Change-Id: Ic948c476a2cfc6381d5655d308bc2d5fa25b7123 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8213 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Tested-by: BuildkiteCI
2023-03-13 r/5980 refactor(tvix/eval): VM struct no longer needs to be publicVincent Ambo2-2/+2
Change-Id: I93b485ddd280cc15fcbaecf4aed5fcd22e28a8a8 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8212 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Tested-by: BuildkiteCI
2023-03-13 r/5979 fix(tvix/eval): implement cppnix JSON-serialisation semanticsVincent Ambo12-70/+138
This drops the usage of serde::Serialize, as the trait can not be used to implement the correct semantics (function colouring!). Instead, a manual JSON serialisation function is written which correctly handles toString, outPath and other similar weirdnesses. Unexpectedly, the eval-okay-tojson test from the C++ Nix test suite now passes, too. This fixes an issue where serialising data structures containing derivations to JSON would fail. Change-Id: I5c39e3d8356ee93a07eda481410f88610f6dd9f8 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8209 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Tested-by: BuildkiteCI
2023-03-13 r/5978 feat(tvix/eval): give generators human-readable namesVincent Ambo5-51/+80
This adds static strings to generator frames that describe the generator in a human-readable fashion, which are then logged in observers. This makes runtime traces very precise, explaining exactly what is being requested from where. Change-Id: I695659a6bd0b7b0bdee75bc8049651f62b150e0c Reviewed-on: https://cl.tvl.fyi/c/depot/+/8206 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-13 r/5977 fix(tvix/eval): handle toJSON on attribute sets with `outPath`Vincent Ambo5-6/+38
These are serialised as the serialisation of the value of that field. Change-Id: Ida51708b1f43ce09b0ec835f4e265918aa31dd09 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8205 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Tested-by: BuildkiteCI
2023-03-13 r/5976 fix(tvix/eval): handle `__toString` when JSON-serialising attrsetsVincent Ambo5-0/+29
These must be serialised to a JSON string of the *result* of coercing the function application to a string. Change-Id: Ib7f49ccd950503ddbdbf99643cd59565e26b50da Reviewed-on: https://cl.tvl.fyi/c/depot/+/8204 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Tested-by: BuildkiteCI
2023-03-13 r/5975 refactor(tvix/eval): move `__toString` calling to a helper functionVincent Ambo2-24/+34
It turns out that this is used not just in coerceToString, but also in toJSON. Change-Id: I1c324b115a0b8bb6d83446d5bf70453c9b90685e Reviewed-on: https://cl.tvl.fyi/c/depot/+/8203 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-13 r/5974 refactor(tvix/eval): print only *types* when observing generatorsVincent Ambo1-7/+11
Do not print the entire value (they're likely to be thunks anyways). This is useful because there *can* be cases where something like `nixpkgs` itself is sent through one of these messages, in which case the observer trying to print it will just blow up. Change-Id: I1fa37ea071d75efa0eb3428c6e2fe4351c62be6b Reviewed-on: https://cl.tvl.fyi/c/depot/+/8202 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-13 r/5973 fix(tvix/eval): don't print full stack in observerVincent Ambo1-1/+8
Print only the top 6 values of the stack, not the entire stack. There's very few operations that deal with more values anyways, so the rest are not likely to be useful. This gets us one step closer to tracing VERY large executions without blowing up. Change-Id: I97472321b0321b25d534d9f53b3aadfacc2318fa Reviewed-on: https://cl.tvl.fyi/c/depot/+/8201 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-13 r/5972 fix(tvix/eval): don't print full values in observerVincent Ambo1-1/+14
This can actually blow up when tracing arbitrary execution, as some of the data structures just get too large to run through a tabwriter. Change-Id: I6ec4c30ee48655b8a62954ca219107404fb2c256 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8200 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-13 r/5971 refactor(tvix/eval): condense observer's stack writing logicVincent Ambo1-53/+24
Change-Id: I1282c3387ac1e0d1528b894814f2a495ca5a6a32 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8199 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-13 r/5970 fix(tvix/eval): correctly thunk deferred formals accessVincent Ambo3-1/+18
Formals can be initialised with deferred default values (see the test cases), in which case they need an extra thunk to have something that can be finalised appropriately when the setup is done. Fixes: b/255 Change-Id: I380e3770be68eaa83ace96d450c7cead32dacc9f Reviewed-on: https://cl.tvl.fyi/c/depot/+/8196 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-13 r/5969 refactor(tvix/eval): box PathBufVincent Ambo5-13/+16
This shaves another 8 bytes off Value. How did that type get so big?! Change-Id: I65e9b59a1636bd57e3cc4aec5fea16887070b832 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8153 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Tested-by: BuildkiteCI
2023-03-13 r/5968 chore(tvix/eval): remove `From<SmolStr> for NixString` instanceVincent Ambo3-14/+12
No longer needed, and in some cases caused some extra work. Change-Id: I64e8e7292573bdc92a9c7a8e470e33f8c526f311 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8152 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Tested-by: BuildkiteCI
2023-03-13 r/5967 refactor(tvix/eval): simplify NixString representation(s)Vincent Ambo3-65/+37
Instead of the two different representations (which we don't really use much), use a `Box<str>` (which potentially shaves another 8 bytes off `Value`). NixString values themselves are immutable anyways (which was a guarantee we already had with `SmolStr`), so this doesn't change anything else. Change-Id: I1d8454c056c21ecb0aebc473cfb3ae06cd70dbb6 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8151 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Reviewed-by: flokli <flokli@flokli.de> Tested-by: BuildkiteCI
2023-03-13 r/5966 refactor(tvix/eval): wrap NixList in RcVincent Ambo2-14/+16
The size of a `Vector<Value>` is 64 *bytes*, which is quite large, and it bloated the entire Value type to this size. This change adds an indirection for the inner vector through Rc. Initially I tried to use a Box, but this breaks pointer equality guarantees for the Vector when it is small enough to be inlined. This reduces the size of Value from 64 to 32 bytes. Change-Id: Ic3211e861b1966c78b2c3d536ba291fea92647fd Reviewed-on: https://cl.tvl.fyi/c/depot/+/8150 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Tested-by: BuildkiteCI
2023-03-13 r/5965 test(tvix/eval): add test for infinite recursion detectionVincent Ambo1-0/+1
Change-Id: Ief20544a44c3542fe40a5c09f81d0f064a346f44 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8149 Reviewed-by: flokli <flokli@flokli.de> Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-13 r/5964 refactor(tvix/eval): flatten call stack of VM using generatorsVincent Ambo24-2677/+2500
Warning: This is probably the biggest refactor in tvix-eval history, so far. This replaces all instances of trampolines and recursion during evaluation of the VM loop with generators. A generator is an asynchronous function that can be suspended to yield a message (in our case, vm::generators::GeneratorRequest) and receive a response (vm::generators::GeneratorResponsee). The `genawaiter` crate provides an interpreter for generators that can drive their execution and lets us move control flow between the VM and suspended generators. To do this, massive changes have occured basically everywhere in the code. On a high-level: 1. The VM is now organised around a frame stack. A frame is either a call frame (execution of Tvix bytecode) or a generator frame (a running or suspended generator). The VM has an outer loop that pops a frame off the frame stack, and then enters an inner loop either driving the execution of the bytecode or the execution of a generator. Both types of frames have several branches that can result in the frame re-enqueuing itself, and enqueuing some other work (in the form of a different frame) on top of itself. The VM will eventually resume the frame when everything "above" it has been suspended. In this way, the VM's new frame stack takes over much of the work that was previously achieved by recursion. 2. All methods previously taking a VM have been refactored into async functions that instead emit/receive generator messages for communication with the VM. Notably, this includes *all* builtins. This has had some other effects: - Some test have been removed or commented out, either because they tested code that was mostly already dead (nix_eq) or because they now require generator scaffolding which we do not have in place for tests (yet). - Because generator functions are technically async (though no async IO is involved), we lose the ability to use much of the Rust standard library e.g. in builtins. This has led to many algorithms being unrolled into iterative versions instead of iterator combinations, and things like sorting had to be implemented from scratch. - Many call sites that previously saw a `Result<..., ErrorKind>` bubble up now only see the result value, as the error handling is encapsulated within the generator loop. This reduces number of places inside of builtin implementations where error context can be attached to calls that can fail. Currently what we gain in this tradeoff is significantly more detailed span information (which we still need to bubble up, this commit does not change the error display). We'll need to do some analysis later of how useful the errors turn out to be and potentially introduce some methods for attaching context to a generator frame again. This change is very difficult to do in stages, as it is very much an "all or nothing" change that affects huge parts of the codebase. I've tried to isolate changes that can be isolated into the parent CLs of this one, but this change is still quite difficult to wrap one's mind and I'm available to discuss it and explain things to any reviewer. Fixes: b/238, b/237, b/251 and potentially others. Change-Id: I39244163ff5bbecd169fe7b274df19262b515699 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8104 Reviewed-by: raitobezarius <tvl@lahfa.xyz> Reviewed-by: Adam Joseph <adam@westernsemico.com> Tested-by: BuildkiteCI
2023-03-13 r/5963 feat(tvix/eval): implement generator-based Nix equality logicVincent Ambo2-6/+182
Adds a `Value::neo_nix_eq` method (the `neo_` prefix will be dropped when we flip over to the generator implementation of the VM) which implements Nix equality semantics using async, generator-based comparisons. Instead of tracking the "kind" of equality that is being compared (see the pointer-equality doc) through a pair of booleans, I've introduced an enum that explicitly lists the possible comparisons. Change-Id: I3354cc1470eeccb3000a5ae24f2418db1a7a2edc Reviewed-on: https://cl.tvl.fyi/c/depot/+/8241 Tested-by: BuildkiteCI Reviewed-by: Adam Joseph <adam@westernsemico.com>
2023-03-13 r/5962 feat(tvix/eval): add generator-related functions to RuntimeObserverVincent Ambo2-7/+89
These functions will be used by the changes in the VM to observe the runtime execution of generator frames, and provide a more linear view of the execution of the Tvix VM. Change-Id: I10b1b1933dedc065e7c61d5d6062f0aaeee0097e Reviewed-on: https://cl.tvl.fyi/c/depot/+/8240 Tested-by: BuildkiteCI Reviewed-by: Adam Joseph <adam@westernsemico.com>
2023-03-13 r/5961 feat(tvix/eval): implement asynchronous list sorting algorithmVincent Ambo1-0/+47
In order to implement an asynchronous builtins.sort (required for moving builtins to generators), we need an `async` sorting algorithm as our comparators involve invoking a Nix function. This commit implements a fairly simple, optimised bubble sort as the sorting algorithm used in our `async fn sort_by`. There don't seem to be any crates providing async versions of things like this, and they might actually be pretty hard to implement generically due to some constraints about how `async` works. Note that this algorithm is less efficient than the hybrid "timsort/mergesort/insert sort" used in the Rust standard library. I tried to write a merge sort implementation, but ran into isuses with the sort becoming unstable because our comparators can not yield equality. This is the simplest implementation which I know to be correct. Note that as of this commit this is *not* covered by the Tvix test suite, but it will be as soon as the rest of the generator code lands. Change-Id: Ia9a604f7dd941d6acc9212c902e0e637ed75bebc Reviewed-on: https://cl.tvl.fyi/c/depot/+/8239 Reviewed-by: Adam Joseph <adam@westernsemico.com> Tested-by: BuildkiteCI
2023-03-13 r/5960 feat(tvix/store): drop BlobWriterFlorian Klink2-142/+0
All code initially using this has been replaced by the simpler and more performant implementation with StreamCDC and read_all_and_chunk. Change-Id: I08889e9a6984de91c5debcf2b612cb68ae5072d1 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8265 Autosubmit: flokli <flokli@flokli.de> Reviewed-by: tazjin <tazjin@tvl.su> Reviewed-by: raitobezarius <tvl@lahfa.xyz> Tested-by: BuildkiteCI