about summary refs log tree commit diff
path: root/tvix/eval/docs/bindings.md
diff options
context:
space:
mode:
Diffstat (limited to 'tvix/eval/docs/bindings.md')
-rw-r--r--tvix/eval/docs/bindings.md133
1 files changed, 0 insertions, 133 deletions
diff --git a/tvix/eval/docs/bindings.md b/tvix/eval/docs/bindings.md
deleted file mode 100644
index 17867acfe9f9..000000000000
--- a/tvix/eval/docs/bindings.md
+++ /dev/null
@@ -1,133 +0,0 @@
-Compilation of bindings
-=======================
-
-Compilation of Nix bindings is one of the most mind-bending parts of Nix
-evaluation. The implementation of just the compilation is currently almost 1000
-lines of code, excluding the various insane test cases we dreamt up for it.
-
-## What is a binding?
-
-In short, any attribute set or `let`-expression. Tvix currently does not treat
-formals in function parameters (e.g. `{ name ? "fred" }: ...`) the same as these
-bindings.
-
-They have two very difficult features:
-
-1. Keys can mutually refer to each other in `rec` sets or `let`-bindings,
-   including out of definition order.
-2. Attribute sets can be nested, and parts of one attribute set can be defined
-   in multiple separate bindings.
-
-Tvix resolves as much of this logic statically (i.e. at compile-time) as
-possible, but the procedure is quite complicated.
-
-## High-level concept
-
-The idea behind the way we compile bindings is to fully resolve nesting
-statically, and use the usual mechanisms (i.e. recursion/thunking/value
-capturing) for resolving dynamic values.
-
-This is done by compiling bindings in several phases:
-
-1. An initial compilation phase *only* for plain inherit statements (i.e.
-   `inherit name;`), *not* for namespaced inherits (i.e. `inherit (from)
-   name;`).
-
-2. A declaration-only phase, in which we use the compiler's scope tracking logic
-   to calculate the physical runtime stack indices (further referred to as
-   "stack slots" or just "slots") that all values will end up in.
-
-   In this phase, whenever we encounter a nested attribute set, it is merged
-   into a custom data structure that acts like a synthetic AST node.
-
-   This can be imagined similar to a rewrite like this:
-
-   ```nix
-   # initial code:
-   {
-       a.b = 1;
-       a.c = 2;
-   }
-
-   # rewritten form:
-   {
-       a = {
-           b = 1;
-           c = 2;
-       };
-   }
-   ```
-
-   The rewrite applies to attribute sets and `let`-bindings alike.
-
-   At the end of this phase, we know the stack slots of all namespaces for
-   inheriting from, all values inherited from them, and all values (and
-   optionally keys) of bindings at the current level.
-
-   Only statically known keys are actually merged, so any dynamic keys that
-   conflict will lead to a "key already defined" error at runtime.
-
-3. A compilation phase, in which all values (and, when necessary, keys) are
-   actually compiled. In this phase the custom data structure used for merging
-   is encountered when compiling values.
-
-   As this data structure acts like an AST node, the process begins recursively
-   for each nested attribute set.
-
-At the end of this process we have bytecode that leaves the required values (and
-optionally keys) on the stack. In the case of attribute sets, a final operation
-is emitted that constructs the actual attribute set structure at runtime. For
-`let`-bindings a final operation is emitted that removes these locals from the
-stack when the scope ends.
-
-## Moving parts
-
-WARNING: This documents the *current* implementation. If you only care about the
-conceptual aspects, see above.
-
-There's a few types involved:
-
-* `PeekableAttrs`: peekable iterator over an attribute path (e.g. `a.b.c`)
-* `BindingsKind`: enum defining the kind of bindings (attrs/recattrs/let)
-* `AttributeSet`: struct holding the bindings kind, the AST nodes with inherits
-  (both namespaced and not), and an internal representation of bindings
-  (essentially a vector of tuples of the peekable attrs and the expression to
-  compile for the value).
-* `Binding`: enum describing the kind of binding (namespaced inherit, attribute
-  set, plain binding of *any other value type*)
-* `KeySlot`: enum describing the location in which a key slot is placed at
-  runtime (nowhere, statically known value in a slot, dynamic value in a slot)
-* `TrackedBinding`: struct representing statically known information about a
-  single binding (its key slot, value slot and `Binding`)
-* `TrackedBindings`: vector of tracked bindings, which implements logic for
-  merging attribute sets together
-
-And quite a few methods on `Compiler`:
-
-* `compile_bindings`: entry point for compiling anything that looks like a
-  binding, this calls out to the functions below.
-* `compile_plain_inherits`: takes all inherits of a bindings node and compiles
-  the ones that are trivial to compile (i.e. just plain inherits without a
-  namespace). The `rnix` parser does not represent namespaced/plain inherits in
-  different nodes, so this function also aggregates the namespaced inherits and
-  returns them for further use
-* `declare_namespaced_inherits`: passes over all namespaced inherits and
-  declares them on the locals stack, as well as inserts them into the provided
-  `TrackedBindings`
-* `declare_bindings`: declares all regular key/value bindings in a bindings
-  scope, but without actually compiling their keys or values.
-
-  There's a lot of heavy lifting going on here:
-
-  1. It invokes the various pieces of logic responsible for merging nested
-     attribute sets together, creating intermediate data structures in the value
-     slots of bindings that can be recursively processed the same way.
-  2. It decides on the key slots of expressions based on the kind of bindings,
-     and the type of expression providing the key.
-* `bind_values`: runs the actual compilation of values. Notably this function is
-  responsible for recursively compiling merged attribute sets when it encounters
-  a `Binding::Set` (on which it invokes `compile_bindings` itself).
-
-In addition to these several methods (such as `compile_attr_set`,
-`compile_let_in`, ...) invoke the binding-kind specific logic and then call out
-to the functions above.