about summary refs log tree commit diff
path: root/tvix/eval/src/compiler/mod.rs
AgeCommit message (Collapse)AuthorFilesLines
2024-02-13 r/7508 feat(tvix/eval): Box Value::CatchableAspen Smith1-2/+2
This is now the only enum variant for Value that is larger than 8 bytes (it's 16 bytes), so boxing it (especially since it's not perf-critical) allows us to get the Value size down to only 16 bytes! Change-Id: I98598e2b762944448bef982e8ff7da6d6683c4aa Reviewed-on: https://cl.tvl.fyi/c/depot/+/10798 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz> Autosubmit: aspen <root@gws.fyi>
2024-02-13 r/7507 revert(tvix/eval): Don't double-box Path valuesAspen Smith1-6/+3
This reverts commit d3d41552cf1f6485f8ebc597a2128a0d15b030a5. This was well-intentioned, but now the boxed Path values are actually the *largest* Value enum variants, at 16 bytes (because they're fat-pointers, with a len) instead of 8 bytes like all the other values. Having the double reference is a reasonable price to pay (it seems; more benchmarks may end up disagreeing) for a smaller Value repr. Change-Id: I0d3e84f646c8f5ffd0b7259c4e456637eea360f7 Reviewed-on: https://cl.tvl.fyi/c/depot/+/10797 Tested-by: BuildkiteCI Autosubmit: aspen <root@gws.fyi> Reviewed-by: sterni <sternenseemann@systemli.org>
2024-02-02 r/7467 refactor(tvix/eval): Box Value::StringAspen Smith1-3/+3
NixString is *quite* large - like 80 bytes - because of the extra capacity value for BString and because of the context. We want to keep Value small since we're passing it around a lot, so let's box the NixString inside Value::String to save on some memory, and make cloning ostensibly a little cheaper Change-Id: I343c8b4e7f61dc3dcbbaba4382efb3b3e5bbabb2 Reviewed-on: https://cl.tvl.fyi/c/depot/+/10729 Tested-by: BuildkiteCI Reviewed-by: sterni <sternenseemann@systemli.org>
2024-02-01 r/7463 feat(tvix/eval): Don't emit OpForce for non-thunk constantsAspen Smith1-0/+9
In the compiler, skip emitting an OpForce if the last op was an OpConstant for a non-thunk constant. This gives a small (~1% on my machine) perf boost, eg when evaluating hello.outPath: ❯ hyperfine \ "./before --no-warnings -E '(import <nixpkgs> {}).hello.outPath'" \ "./after --no-warnings -E '(import <nixpkgs> {}).hello.outPath'" Benchmark 1: ./before --no-warnings -E '(import <nixpkgs> {}).hello.outPath' Time (mean ± σ): 1.151 s ± 0.022 s [User: 1.003 s, System: 0.151 s] Range (min … max): 1.123 s … 1.184 s 10 runs Benchmark 2: ./after --no-warnings -E '(import <nixpkgs> {}).hello.outPath' Time (mean ± σ): 1.140 s ± 0.022 s [User: 0.989 s, System: 0.152 s] Range (min … max): 1.115 s … 1.175 s 10 runs Summary ./after --no-warnings -E '(import <nixpkgs> {}).hello.outPath' ran 1.01 ± 0.03 times faster than ./before --no-warnings -E '(import <nixpkgs> {}).hello.outPath' Change-Id: I2105fd431d4bad699087907e16c789418e9a4062 Reviewed-on: https://cl.tvl.fyi/c/depot/+/10714 Reviewed-by: sterni <sternenseemann@systemli.org> Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI
2024-02-01 r/7461 refactor(tvix/eval): Don't double-box Path valuesAspen Smith1-3/+6
PathBuf internally contains a heap pointer (an OsString), so we were in effect double-boxing here. Removing the extra layer by making Tvix::Value represented by a Box<Path> rather than a Box<PathBuf> saves us an indirection, while still avoiding the extra memory overhead of the capacity which was the reason we were boxing PathBuf in the first place. Change-Id: I8c185b9d4646161d1921917f83e87421496a3e24 Reviewed-on: https://cl.tvl.fyi/c/depot/+/10725 Reviewed-by: sterni <sternenseemann@systemli.org> Autosubmit: aspen <root@gws.fyi> Tested-by: BuildkiteCI
2024-01-31 r/7460 fix(tvix): Represent strings as byte arraysAspen Smith1-1/+1
C++ nix uses C-style zero-terminated char pointers to represent strings internally - however, up to this point, tvix has used Rust `String` and `str` for string values. Since those are required to be valid utf-8, we haven't been able to properly represent all the string values that Nix supports. To fix that, this change converts the internal representation of the NixString struct from `Box<str>` to `BString`, from the `bstr` crate - this is a wrapper around a `Vec<u8>` with extra functions for treating that byte vector as a "morally string-like" value, which is basically exactly what we need. Since this changes a pretty fundamental assumption about a pretty core type, there are a *lot* of changes in a lot of places to make this work, but I've tried to keep the general philosophy and intent of most of the code in most places intact. Most notably, there's nothing that's been done to make the derivation stuff in //tvix/glue work with non-utf8 strings everywhere, instead opting to just convert to String/str when passing things into that - there *might* be something to be done there, but I don't know what the rules should be and I don't want to figure them out in this change. To deal with OS-native paths in a way that also works in WASM for tvixbolt, this also adds a dependency on the "os_str_bytes" crate. Fixes: b/189 Fixes: b/337 Change-Id: I5e6eb29c62f47dd91af954f5e12bfc3d186f5526 Reviewed-on: https://cl.tvl.fyi/c/depot/+/10200 Reviewed-by: tazjin <tazjin@tvl.su> Reviewed-by: flokli <flokli@flokli.de> Reviewed-by: sterni <sternenseemann@systemli.org> Autosubmit: aspen <root@gws.fyi> Tested-by: BuildkiteCI
2024-01-25 r/7448 feat(tvix/eval): track pattern binding namesFlorian Klink1-3/+11
These need to be preserved at least for builtins.toXML. Also, we incorrectly only wrote an <attrspat> in case ellipsis was true, but that's not the case. Change-Id: I6bff9c47c2922f878d5c43e48280cda9c9ddb692 Reviewed-on: https://cl.tvl.fyi/c/depot/+/10686 Tested-by: BuildkiteCI Autosubmit: flokli <flokli@flokli.de> Reviewed-by: aspen <root@gws.fyi>
2024-01-24 r/7447 fix(tvix/eval/value/function): use BTreeMap for function arg namesFlorian Klink1-2/+2
At least toXML wants to get these out in a sorted fashion. Change-Id: I6373d7488fff7c40dc2ddeeecd03ba537c92c4af Reviewed-on: https://cl.tvl.fyi/c/depot/+/10685 Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI
2023-12-29 r/7272 refactor(tvix/eval): let OpCoerceToString select the CoercionKindAdam Joseph1-1/+8
Change-Id: I92d58ef216d7e0766af70f019b3dcd445284a95d Reviewed-on: https://cl.tvl.fyi/c/depot/+/10344 Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI
2023-12-12 r/7193 fix(tvix/eval): add unimplemented __curPos and builtins.filterSourceAdam Joseph1-0/+1
This commit adds __curPos (to the global scope, yuck) and builtins.filterSource. These are not implemented; forcing them will produce the same result as `throw "message"`. Unfortunately these two post-2.3 features are used throughout nixpkgs. Since an unresolved indentifier is a catchable error, this breaks the entire release eval. With this commit, it simply causes those broken packages that use these features to appear as they are: broken. Change-Id: Ib43dea571f6a9fab4d54869349f80ee4ec5424c2 Reviewed-on: https://cl.tvl.fyi/c/depot/+/10297 Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI Autosubmit: Adam Joseph <adam@westernsemico.com>
2023-12-12 r/7192 fix(tvix/eval): propagate catchables through `&&`Adam Joseph1-0/+2
Change-Id: I7bb5ac1ef47b41c47269e64cee0e90eb64c6fcce Reviewed-on: https://cl.tvl.fyi/c/depot/+/10322 Autosubmit: Adam Joseph <adam@westernsemico.com> Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su>
2023-12-12 r/7191 fix(tvix/eval): make `||` propagate catchablesAdam Joseph1-0/+2
Change-Id: I42f994d7c9228368d5f6c30c4730c24666f7bc69 Reviewed-on: https://cl.tvl.fyi/c/depot/+/10320 Autosubmit: Adam Joseph <adam@westernsemico.com> Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su>
2023-12-12 r/7190 fix(tvix/eval): fix nested assertions b/340Adam Joseph1-0/+2
This commit fixes our handling of `throw` within an `assert` condition. Fixes: b/340 Change-Id: I40a383639ec266da50a853f16216b1b7868495da Reviewed-on: https://cl.tvl.fyi/c/depot/+/10318 Autosubmit: Adam Joseph <adam@westernsemico.com> Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su>
2023-12-12 r/7186 fix(tvix/eval): fix catchables in named formalsAdam Joseph1-11/+27
Fixes b/348. Change-Id: I5e8d56b5fd26a19eac32ec5e11baf93765691dc8 Reviewed-on: https://cl.tvl.fyi/c/depot/+/10296 Autosubmit: Adam Joseph <adam@westernsemico.com> Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI
2023-12-12 r/7180 fix(tvix/eval): fix recovering from throws in implicationsAdam Joseph1-0/+2
This fixes b/345. Change-Id: Ic0d3b6ffacd2a5e0050d22354d08320b69a4fe13 Reviewed-on: https://cl.tvl.fyi/c/depot/+/10290 Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su> Autosubmit: Adam Joseph <adam@westernsemico.com>
2023-12-12 r/7178 fix(tvix/eval): fix branching on catchable defaults (b/343)Adam Joseph1-0/+6
This commit adds Opcode::OpJumpIfCatchable, which can be inserted ahead of most VM operations which expect a boolean on the stack, in order to handle catchables in branching position properly. Other than remembering to patch the jump, no other changes should be required. This commit also fixes b/343 by emitting this new opcode when compiling if-then-else. There are probably other places where we need to do the same thing. Change-Id: I48de3010014c0bbeba15d34fc0d4800e0bb5a1ef Reviewed-on: https://cl.tvl.fyi/c/depot/+/10288 Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su> Autosubmit: Adam Joseph <adam@westernsemico.com>
2023-11-05 r/6955 chore(tvix): fix trivial clippy lintsVincent Ambo1-4/+4
Relates to b/321. Change-Id: I37284f89b186e469eb432e2bbedb37aa125a6ad4 Reviewed-on: https://cl.tvl.fyi/c/depot/+/9961 Tested-by: BuildkiteCI Reviewed-by: flokli <flokli@flokli.de> Autosubmit: tazjin <tazjin@tvl.su>
2023-09-24 r/6650 fix(tvix/eval): fix b/281 by adding Value::CatchableAdam Joseph1-3/+3
This commit makes catchable errors a variant of Value. The main downside of this approach is that we lose the ability to use Rust's `?` syntax for propagating catchable errors. Change-Id: Ibe89438d8a70dcec29e016df692b5bf88a5cad13 Reviewed-on: https://cl.tvl.fyi/c/depot/+/9289 Reviewed-by: tazjin <tazjin@tvl.su> Autosubmit: Adam Joseph <adam@westernsemico.com> Tested-by: BuildkiteCI
2023-09-24 r/6649 refactor(tvix/eval): factor CatchableErrorKind out of ErrorKindAdam Joseph1-2/+4
This commit creates a separate enum for "catchable" errors (the kind that `builtins.tryEval` can detect). Change-Id: Ie81d1112526d852255d9842f67045f88eab192af Reviewed-on: https://cl.tvl.fyi/c/depot/+/9287 Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su> Autosubmit: Adam Joseph <adam@westernsemico.com>
2023-09-22 r/6624 docs(tvix/eval): fix some broken docstr referencesFlorian Klink1-1/+1
There's some more left, but they've been renamed/refactored out of sight. Change-Id: I41579dedc74342b4c5f8cb39d2995b5b0c90b0f4 Reviewed-on: https://cl.tvl.fyi/c/depot/+/9372 Tested-by: BuildkiteCI Reviewed-by: Connor Brewster <cbrewster@hey.com> Autosubmit: flokli <flokli@flokli.de>
2023-06-20 r/6336 fix(tvix/eval): only finalise formal arguments if defaultingsterni1-34/+165
When dealing with a formal argument in a function argument pattern that has a default expression, there are two different things that can happen at runtime: Either we select its value from the passed attribute successfully or we need to use the default expression. Both of these may be thunks and both of these may need finalisers. However, in the former case this is taken care of elsewhere, the value will always be finalised already if necessary. In the latter case we may need to finalise the thunk resulting from the default expression. However, the thunk corresponding to the expression may never end up in the local's stack slot. Since finalisation goes by stack slot (and not constants), we need to prevent a case where we don't fall back to the default expression, but finalise anyways. Previously, we worked around this by making `OpFinalise` ignore non-thunks. Since finalisation of already evaluated thunks still crashed, the faulty compilation of function pattern arguments could still cause a crash. As a new approach, we reinstate the old behavior of `OpFinalise` to crash whenever encountering something that is either not a thunk or doesn't need finalisation. This can also help catching (similar) miscompilations in the future. To then prevent the crash, we need to track whether we have fallen back or not at runtime. This is done using an additional phantom on the stack that holds a new `FinaliseRequest` value. When it comes to finalisation we check this value and conditionally execute `OpFinalise` based on its value. Resolves b/261 and b/265 (partially). Change-Id: Ic04fb80ec671a2ba11fa645090769c335fb7f58b Reviewed-on: https://cl.tvl.fyi/c/depot/+/8705 Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI Autosubmit: sterni <sternenseemann@systemli.org>
2023-06-14 r/6297 fix(tvix/eval): don't thunk home relative pathssterni1-11/+10
C++ Nix resolves home relative paths at [parse] time. This is not an option for us, since it prevents being able to separate the compilation and execution phase later (e.g. precompiled nix expressions). However, a practical consequence of this is that paths expressions are always literals (strict) and never thunks. [parse]: https://github.com/NixOS/nix/blob/7066d21a0ddb421967980094222c4bc1f5a0f45a/src/libexpr/parser.y#L518-L527 Change-Id: Ie4b9dc68f62c86d6c7fd5f1c9460c850d97ed1ca Reviewed-on: https://cl.tvl.fyi/c/depot/+/7041 Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su>
2023-06-07 r/6244 fix(tvix/eval): use normal thunking behavior for default in formalssterni1-9/+2
When comparing to C++ Nix, we notice that the thunking of default expressions in function formals corresponds to their normal thunking, e.g. literals are not thunked. This means that we can just invoke compile() without much of a care and trust that it will sort it out correctly. If function formals blow up as a result of this, it likely indicates that the expression is treated incorrectly by compile(), not compile_param_pattern(). Change-Id: I64acbff2f251423eb72ce43e56a0603379305e1d Reviewed-on: https://cl.tvl.fyi/c/depot/+/8704 Autosubmit: sterni <sternenseemann@systemli.org> Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su>
2023-06-07 r/6243 fix(tvix/eval): type check function argument with set patternsterni1-0/+1
C++ Nix forces and typechecks the passed argument even if it is not necessary in order to compute the return value of the function. I discovered this when I thought our formals miscompilation might be that we are too strict, but doesn't look like it in this case. Change-Id: Ifb3c92592293052c489d1e3ae8c7c54e4b6b4dc6 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8701 Tested-by: BuildkiteCI Autosubmit: sterni <sternenseemann@systemli.org> Reviewed-by: tazjin <tazjin@tvl.su>
2023-06-07 r/6242 refactor(tvix/eval): don't track idx twice in compile_param_patternsterni1-9/+7
Change-Id: I27f9105ddb20d84342550b2a73b479a7764ee3fe Reviewed-on: https://cl.tvl.fyi/c/depot/+/8699 Reviewed-by: tazjin <tazjin@tvl.su> Autosubmit: sterni <sternenseemann@systemli.org> Tested-by: BuildkiteCI
2023-05-29 r/6217 fix(tvix/eval): thunk lambda expressionssterni1-5/+3
As cl/8658 and b/274 reveal, lambda expressions are also wrapped in thunks. Resolves b/274. Change-Id: I02fe5c8730ac76748d940e4f4427116587875275 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8662 Autosubmit: sterni <sternenseemann@systemli.org> Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su>
2023-05-29 r/6216 fix(tvix/eval): thunk HasAttr expressionssterni1-1/+3
HasAttrs was weird because with longer attribute paths it would sometimes not turn out to be a thunk. If it was a thunk, it'd usually still do some eval strictly which we'll want to avoid. Verified against C++ Nix using a new test suite introduced in a later CL. Change-Id: I6d047ccc68d046bb268462f170a3c4f3c5ddeffe Reviewed-on: https://cl.tvl.fyi/c/depot/+/8656 Autosubmit: sterni <sternenseemann@systemli.org> Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su>
2023-05-29 r/6215 fix(tvix/eval): thunk legacy let to match regular onesterni1-1/+3
Probably no real world code broken by this overzealous evaluation, but let's be thorough! Change-Id: Ib405a677182eab7940ace940c68e107573473a54 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8655 Reviewed-by: tazjin <tazjin@tvl.su> Autosubmit: sterni <sternenseemann@systemli.org> Tested-by: BuildkiteCI
2023-05-29 r/6214 fix(tvix/eval): thunk unary operator applicationssterni1-1/+1
Unary operator applications are thunked which can easily be observed by nix-instantiate --eval -E '[ (!true) (-1) ]' Unfortunately, there are few simple expressions where this makes a difference in the end result. Thus it only cropped up when using nixpkgs for cross compilation: Here we would compile the expression !(stdenv.cc.isGNU or false) to assemble python3Minimal's passthru attribute set (at least this seems to be the most likely explanation from the backtraces I've studied). This means that an unthunked <stdenv.cc.isGNU or false> OpForce OpInvert would be performed in order to assemble this attribute set, causing stdenv.cc to be evaluated too early, causing an infinite recursion. Resolves b/273. It seems that having a test suite that doesn't use --strict and relies on thunks rendered as <CODE> would be beneficial for catching such issues. I've not been able to find a test case with --strict that demonstrates the problem fixed in this CL. Change-Id: I640a5827b963f5b9d0f86fa2142e75e3a6bbee78 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8654 Tested-by: BuildkiteCI Autosubmit: sterni <sternenseemann@systemli.org> Reviewed-by: tazjin <tazjin@tvl.su>
2023-05-25 r/6205 feat(tvix/eval): unthunk empty lists and attribute setsVincent Ambo1-0/+4
Change-Id: Ie66cb1b163a544d45d113fd0f866286f230b0188 Reviewed-on: https://cl.tvl.fyi/c/depot/+/7960 Tested-by: BuildkiteCI Reviewed-by: grfn <grfn@gws.fyi>
2023-05-25 r/6204 feat(tvix/eval): implement unthunking in compilerVincent Ambo1-1/+22
This feature allows the compiler to detect situations where the created thunk is useless and can be merged into the parent chunk instead. The only case where the compiler does this initially is when statically optimising a select expression. For example, previously the expression `builtins.length` compiled into two thunks: 1. An "inner" thunk which contained an `OpConstant` that had the optimised `length` builtin in it. 2. An "outer" thunk which contained an `OpConstant` to access the inner thunk, and the trailing OpForce of the top-level program. With this change, the inner thunk is skipped completely and the outer chunk directly contains the `length` builtin access. This can be applied in several situations, some easier than others, and we will add them in as we go along. Change-Id: Ie44521445fce1199f99b5b17712833faea9bc357 Reviewed-on: https://cl.tvl.fyi/c/depot/+/7959 Tested-by: BuildkiteCI Reviewed-by: flokli <flokli@flokli.de>
2023-03-17 r/6027 fix(tvix/eval): use span of `set` for OpForce in attribute accessVincent Ambo1-2/+2
Emits the span of the `set` that is being accessed in the `force` operation of an attribute access. Looking at traces, it's a lot more useful to get information about *what* is being forced, as in cases like `foo.bar` it can be misleading to have an error highlight `bar`, when the error occured while forcing `foo` to be able to access `bar` in the first place. Change-Id: Id46ff28f20c67cb4971727ac52cc4811795cea2d Reviewed-on: https://cl.tvl.fyi/c/depot/+/8272 Reviewed-by: flokli <flokli@flokli.de> Autosubmit: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI
2023-03-17 r/6024 feat(tvix/eval): add generator "name" to NativeError kindVincent Ambo1-1/+4
This produces traces in which we can see what kind of native code was run. Note that these "names" are named after the generator message, so these aren't *really* intended for end-user consumption, but we can give them saner names later. Example: https://gist.github.com/tazjin/82b24e92ace8e821008954867ee05057 This already makes the traces a little easier to parse. Change-Id: Idcd601baf84f492211b732ea0f04b377112e10d0 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8268 Reviewed-by: flokli <flokli@flokli.de> Tested-by: BuildkiteCI Autosubmit: tazjin <tazjin@tvl.su>
2023-03-17 r/6023 feat(tvix/eval): enrich errors with VM's frame stack informationVincent Ambo1-1/+2
When emitting an error at runtime, the VM will now use the new `NativeError` and `BytecodeError` error kinds (which just wrap inner errors) to create a set of diagnostics to emit. The primary diagnostic is emitted last, with `error` type (so it will be coloured red in terminals), the other ones will be emitted with `note` type, highlighting the causal chain. Example: https://gist.github.com/tazjin/25feba7d211702453c9ebd5f8fd378e4 This is currently quite verbose, and we can cut down on this further, but the purpose of this commit is to surface more information first of all before worrying about the exact display. Change-Id: I058104a178c37031c0db6b4b3e4f4170cf76087d Reviewed-on: https://cl.tvl.fyi/c/depot/+/8266 Autosubmit: tazjin <tazjin@tvl.su> Reviewed-by: flokli <flokli@flokli.de> Tested-by: BuildkiteCI
2023-03-13 r/5970 fix(tvix/eval): correctly thunk deferred formals accessVincent Ambo1-1/+11
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 Ambo1-3/+6
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/5964 refactor(tvix/eval): flatten call stack of VM using generatorsVincent Ambo1-0/+7
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-11 r/5954 feat(tvix/eval): don't warn twice about dead codeFlorian Klink1-1/+3
We currently send two warnings in case of detecting dead code - W008 inside compile_dead_code, and a more detailed warning in all places that invoke compile_dead_code: ``` warning[W007]: useless operation on boolean: this expression is always false --> /nix/store/qz3gjn95gazab4fkb7s8lm6hz17rdzzy-414z9nnj1wy66ymq6vgb693x9xjz6hf2-nixpkgs-src/pkgs/top-level/perl-packages.nix:12079:15 | 12079 | doCheck = false && !stdenv.isDarwin; | ^^^^^^^^^^^^^^^^^^^^^^^^^ warning[W008]: this code will never be executed --> /nix/store/qz3gjn95gazab4fkb7s8lm6hz17rdzzy-414z9nnj1wy66ymq6vgb693x9xjz6hf2-nixpkgs-src/pkgs/top-level/perl-packages.nix:12079:24 | 12079 | doCheck = false && !stdenv.isDarwin; | ^^^^^^^^^^^^^^^^ ``` The place invoking `compile_dead_code` has more context to why the code is unused, so it's error message is much more useful. Stop emitting the less informative warning inside compile_dead_code (W008), and update the comment that we expect the caller to emit a warning. I kept W008 itself still around, in case we end up having places this will get used again. Change-Id: I2c5d84fc0cb4035872cd4b71cc3e9e34e120eb37 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8024 Tested-by: BuildkiteCI Autosubmit: flokli <flokli@flokli.de> Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-07 r/5898 refactor(tvix/eval): merge OpCall & OpTailCallVincent Ambo1-18/+0
As applies are thunked, there was no situation where OpCall could be emitted. In practice, all calls were already tail calls. Change-Id: Id0d441dcdd86f804d7cddd0cc14f589bbfc75e5b Reviewed-on: https://cl.tvl.fyi/c/depot/+/8147 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-04 r/5888 refactor(tvix/eval): remove VM argument from suspended native thunksVincent Ambo1-2/+2
Because they do not use it, and it can not be passed with the coming generator refactoring. Change-Id: I0d96f2357a7ee79cd8a0f401583d4286230d4a6b Reviewed-on: https://cl.tvl.fyi/c/depot/+/8146 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
2023-03-03 r/5870 chore(tvix/eval): fix clippy warningsVincent Ambo1-2/+2
Change-Id: I4c02f0104c455ac00a3f299c1fbf75cbb08e8972 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8142 Reviewed-by: flokli <flokli@flokli.de> Tested-by: BuildkiteCI Autosubmit: tazjin <tazjin@tvl.su>
2023-02-04 r/5837 fix(tvix/eval): fix the default case for path parsingVincent Ambo1-10/+4
Plain paths like `foo/bar.nix` are also allowed, so we can not determine this based on the prefix. The upstream PR that is referenced in a comment here has a significantly different interface than we expected, so I'm not touching that comment yet in this CL before I've had more time to digest it. Change-Id: Iea33bbb35de9c00a7d7fedf64d02253c75c1cc9e Reviewed-on: https://cl.tvl.fyi/c/depot/+/8032 Autosubmit: tazjin <tazjin@tvl.su> Reviewed-by: Alyssa Ross <hi@alyssa.is> Reviewed-by: flokli <flokli@flokli.de> Tested-by: BuildkiteCI
2023-02-03 r/5831 refactor(tvix/eval): statically resolve select from constant attrsVincent Ambo1-3/+86
When resolving a select expression (`attrs.name` or `attrs.name or default`), if the set compiles to a constant attribute set (as is most notably the case with `builtins`) we can backtrack and replace that attribute set directly with the compiled value. For something like `builtins.length`, this will directly emit an `OpConstant` that leaves the `length` builtin on the stack. Change-Id: I639654e065a06e8cfcbcacb528c6da7ec9e513ee Reviewed-on: https://cl.tvl.fyi/c/depot/+/7957 Tested-by: BuildkiteCI Reviewed-by: flokli <flokli@flokli.de>
2023-02-03 r/5828 fix(tvix/eval): ensure all evaluated thunks are correctly memoizedVincent Ambo1-2/+2
This fixes a very complicated bug (b/246). Evaluation progresses *much* further after this, leading to several less complicated bugs likely being uncovered by this What was the problem? ===================== Previously, when evaluating a thunk, we had a code path that looked like this: match *thunk { ThunkRepr::Evaluated(Value::Thunk(ref inner_thunk)) => { let inner_repr = inner_thunk.0.borrow().clone(); drop(thunk); self.0.replace(inner_repr); } /* ... */ } This code path created a copy of the inner `ThunkRepr` of a nested thunk, and moved that copy into the `ThunkRepr` of the parent. The effect of this was that the original `ThunkRepr` (unforced!) lived on in the original thunk, without the memoization of the subsequent forcing applying to it. This had the result that Tvix would repeatedly evaluate these thunks without ever memoizing them, if they occured repeatedly as shared inner thunks. Most notably, this would *always* occur when builtins.import was used. What's the solution? ==================== I have completely rewritten `Thunk::force_trampoline_self` to make all flows that can occur in it explicit. I have also removed the outer loop inside of that function, and resorted to more use of trampolining instead. The function is now well-commented and it should be possible to read it from top-to-bottom and get a general sense of what is going on, though the trampolining itself (which is implemented in the VM) needs to be at least partially understood for this. What's the new problem(s)? ========================== One new (known) problem is that we have to construct `Error` instances in all error types here, but we do not have spans available in some thunk-related situations. Due to b/238 we cannot ask the VM for an arbitrary span from the callsite leading to the force. This means that there are now code paths where, under certain conditions, causing an evaluation error during thunk forcing will panic. To fix this we will need to investigate and fix b/238, and/or add a span tracking mechanism to thunks themselves. What other impacts does this have? ================================== With this commit, eval of nixpkgs mostly succeeds (things like stdenv evaluate to the same hashes for us and C++ Nix, meaning we now construct identical derivations without eval breaking). Due to this we progress much further into nixpkgs, which lets us uncover more additional bugs. For example, after this commit we can quickly see that cl/7949 introduces some kind of behavioural issue and should not be merged as-is (this was not apparent before). Additionally, tvix-eval is now seemingly very fast. When doing performance analysis of a nixpkgs eval, we now mostly see the code path for shelling out to C++ Nix to add things to the store in there. We still need those code paths, so we can not (yet) do a performance analysis beyond that. Change-Id: I738525bad8bc5ede5d8c737f023b14b8f4160612 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8012 Tested-by: BuildkiteCI Reviewed-by: flokli <flokli@flokli.de>
2023-01-22 r/5735 feat(tvix/eval): support builtins implemented in Nix itselfVincent Ambo1-16/+76
This makes it possible to inject builtins into the builtin set that are written in Nix code, and which at runtime are represented by a thunk that will compile them the first time they are used. Change-Id: Ia632367328f66fb2f26cb64ae464f8f3dc9c6d30 Reviewed-on: https://cl.tvl.fyi/c/depot/+/7891 Tested-by: BuildkiteCI Reviewed-by: flokli <flokli@flokli.de>
2023-01-22 r/5734 docs(tvix/eval): update some outdated commentsVincent Ambo1-8/+3
These don't apply anymore since the "antidote-CL". Change-Id: I40ee73ef43d44bbfc650a8fe6c2b33263dd06959 Reviewed-on: https://cl.tvl.fyi/c/depot/+/7890 Tested-by: BuildkiteCI Reviewed-by: flokli <flokli@flokli.de>
2023-01-21 r/5721 refactor(tvix/eval): administer antidote for poisonAdam Joseph1-68/+22
The codebase contains a lot of complexity and odd roundabout handling for shadowing globals. I'm pretty sure none of this is necessary, and all of it disappears if you simply make the globals part of the ordinary identifier resolution chain, with their own scope up above the root scope. Then the ordinary shadowing routines do the right thing, and no special cases or new terminology are required. This commit does that. Note by tazjin: This commit was originally abandoned when Adam decided not to take away reviewer bandwidth for this at the time (eval was still in a much earlier stage). As we've recently done some significant refactoring of globals initialisation this came up again, and it seems we can easily cover the use-cases of the poison tracking in other ways now, so I've rebased, updated and resurrected the CL. Co-Authored-By: Vincent Ambo <tazjin@tvl.su> Signed-off-by: Adam Joseph <adam@westernsemico.com> Change-Id: Ib3309a47a7b31fa5bf10466bade0d876b76ae462 Reviewed-on: https://cl.tvl.fyi/c/depot/+/7089 Reviewed-by: tazjin <tazjin@tvl.su> Tested-by: BuildkiteCI Reviewed-by: flokli <flokli@flokli.de>
2023-01-20 r/5706 feat(tvix/eval): add error contexts to annotate error kindsVincent Ambo1-7/+9
This makes it possible for users to add additional context to an error, which will then be rendered as an additional secondary span in the formatted error output. We should strive to do this basically anywhere errors are raised that can occur multiple times, *especially* during type casts. This was triggered by me debugging a type cast error attached to a fairly large-ish span (a builtin invocation). Change-Id: I51be41fabee00cf04de973935daf34fe6424e76f Reviewed-on: https://cl.tvl.fyi/c/depot/+/7849 Tested-by: BuildkiteCI Reviewed-by: flokli <flokli@flokli.de>
2023-01-17 r/5675 refactor(tvix/eval): remove `Box` in new_suspended_nativeVincent Ambo1-2/+2
This is unnecessary, Rc already provides all the boxing we need. Change-Id: I08cf0939c48da43f04c847526c7e5dae5336d528 Reviewed-on: https://cl.tvl.fyi/c/depot/+/7749 Tested-by: BuildkiteCI Reviewed-by: grfn <grfn@gws.fyi> Reviewed-by: sterni <sternenseemann@systemli.org>
2023-01-17 r/5674 feat(tvix/eval): add builtins to builtinsVincent Ambo1-2/+32
This is a somewhat terrifying hack that enables us to support `builtins.builtins`, by running a "fake compilation" inside of a suspended native thunk that can resolve the weak pointer to the globals. With this implementation, the thunk at `builtins.builtins` actually resolves to the "real" `builtins` (verified with a new test). This is kind of ugly, and it's something users shouldn't use, but bubbling a warning out of this is difficult at the moment due to a little bit of trickery with how the spans in suspended native thunks work (they don't) (see b/237, b/238) Change-Id: I67d0e93246dd5b279c960aeda00402031aa12af3 Reviewed-on: https://cl.tvl.fyi/c/depot/+/7748 Tested-by: BuildkiteCI Reviewed-by: flokli <flokli@flokli.de>