From 8adc9c56f21d8418dc5f4b73a4327d04cd10ebd3 Mon Sep 17 00:00:00 2001 From: sterni Date: Tue, 27 Jun 2023 01:20:17 +0200 Subject: docs(tvix): document when pointer equality is preserved in C++ Nix This explicitly documents behavior of C++ Nix that goes against the intuition you'd gather from this document: that e.g. a simple select from an attribute set causes a value to no longer be pointer equal to its former self. The point of documenting this is that we can show in a to be written section on the use of pointer equality in nixpkgs that pointer equality is only needed in a limited sense for evaluating it (C++ Nix's exterior pointer equality). Tvix's pointer equality is far more powerful since value identity preserving operations also preserve pointer equality, generally speaking (this is because we implement interior pointer equality in my made up terminology). This should eventually also be documented. Change-Id: I6ce7ef2d67b012f5ebc92f9e81bba33fb9dce7d0 Reviewed-on: https://cl.tvl.fyi/c/depot/+/8856 Tested-by: BuildkiteCI Autosubmit: sterni Reviewed-by: tazjin --- tvix/docs/value-pointer-equality.md | 131 ++++++++++++++++++++- .../eval-okay-builtins-set-pointer-equality.exp | 2 +- .../eval-okay-builtins-set-pointer-equality.nix | 13 +- ...eval-okay-non-identifier-pointer-inequality.exp | 1 + ...eval-okay-non-identifier-pointer-inequality.nix | 28 +++++ 5 files changed, 169 insertions(+), 6 deletions(-) create mode 100644 tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-non-identifier-pointer-inequality.exp create mode 100644 tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-non-identifier-pointer-inequality.nix (limited to 'tvix') diff --git a/tvix/docs/value-pointer-equality.md b/tvix/docs/value-pointer-equality.md index 2e5050a822db..d84efcb50ca9 100644 --- a/tvix/docs/value-pointer-equality.md +++ b/tvix/docs/value-pointer-equality.md @@ -47,7 +47,7 @@ works in C++ Nix, the only production ready Nix implementation currently availab ## Nix (Pointer) Equality in C++ Nix -TIP: The summary presented here is up-to-date as of 2023-06-20 and was tested +TIP: The summary presented here is up-to-date as of 2023-06-27 and was tested with Nix 2.3, 2.11 and 2.15. ### `EvalState::eqValues` and `ExprOpEq::eval` @@ -163,6 +163,132 @@ in builtins.elem f [ f 2 3 ] # => true ``` +### Pointer Equality Preserving Nix Operations + +We have seen that pointer equality is established by comparing the memory +location of two C++ `Value` structs. But how does this _representation_ relate +to Nix values _themselves_ (in the sense of a platonic ideal if you will)? In +Nix, values have no identity (ignoring `unsafeGetAttrPos`) or memory location. + +Since Nix is purely functional, values can't be mutated, so they need to be +copied frequently. With Nix being garbage collected, there is no strong +expectation when a copy is made, we probably just hope it is done as seldomly as +possible to save on memory. With pointer equality leaking the memory location of +the `Value` structs to an extent, it is now suddenly our business to know +exactly _when_ a copy of a value is made. + +Evaluation in C++ Nix mainly proceeds along the following [two +functions][eval-maybeThunk]. + +```cpp +struct Expr +{ + /* … */ + virtual void eval(EvalState & state, Env & env, Value & v); + virtual Value * maybeThunk(EvalState & state, Env & env); + /* … */ +}; +``` + +As you can see, `Expr::eval` always takes a reference to a struct _allocated by +the caller_ to place the evaluation result in. Anything that is processed using +`Expr::eval` will be a copy of the `Value` struct even if the value before and +after are the same. + +`Expr::maybeThunk`, on the other hand, returns a pointer to a `Value` which may +already exist or be newly allocated. So, if evaluation passes through `maybeThunk`, +Nix values _can_ retain their pointer equality. Since Nix is lazy, a lot of +evaluation needs to be thunked and pass through `maybeThunk`—knowing under what +circumstances `maybeThunk` will return a pointer to an already existing `Value` +struct thus means knowing the circumstances under which pointer equality of a +Nix value will be preserved in C++ Nix. + +The [default case][maybeThunk-default] of `Expr::maybeThunk` allocates a new +`Value` which holds the delayed computation of the `Expr` as a thunk: + +```cpp + +Value * Expr::maybeThunk(EvalState & state, Env & env) +{ + Value * v = state.allocValue(); + mkThunk(*v, env, this); + return v; +} +``` + +Consequently, only special cased expressions could preserve pointer equality. +These are `ExprInt`, `ExprFloat`, `ExprString`, `ExprPath`—all of which relate +to creating new values—and [finally, `ExprVar`][maybeThunk-ExprVar]: + +```cpp +Value * ExprVar::maybeThunk(EvalState & state, Env & env) +{ + Value * v = state.lookupVar(&env, *this, true); + /* The value might not be initialised in the environment yet. + In that case, ignore it. */ + if (v) { state.nrAvoided++; return v; } + return Expr::maybeThunk(state, env); +} +``` + +Here we may actually return an already existing `Value` struct. Consequently, +accessing a value from the scope is the only thing you can do with a value in +C++ Nix that preserves its pointer equality, as the following example shows: +For example, using the select operator to get a value from an attribute set +or even passing a value trough the identity function invalidates its pointer +equality to itself (or rather, its former self). + +```nix +let + pointerEqual = a: b: [ a ] == [ b ]; + id = x: x; + + f = _: null; + x = { inherit f; }; + y = { inherit f; }; +in + +[ + (pointerEqual f f) # => true + + (pointerEqual f (id f)) # => false + + (pointerEqual x.f y.f) # => false + (pointerEqual x.f x.f) # => false + + (pointerEqual x x) # => true + (pointerEqual x y) # => true +] +``` + +In the last two cases, the example also shows that there is another way to +preserve pointer equality: Storing a value in an attribute set (or list) +preserves its pointer equality even if the structure holding it is modified in +some way (as long as the value we care about is left untouched). The catch is, +of course, that there is no way to get the value out of the structure while +preserving pointer equality (which requires using the select operator or a call +to `builtins.elemAt`). + +We initially illustrated the issue of pointer equality using the following +true expressions: + +* `stdenv.hostPlatform.canExecute != stdenv.hostPlatform.canExecute` +* `stdenv.hostPlatform == stdenv.hostPlatform` + +We can now add a third one, illustrating that pointer equality is invalidated +by select operations: + +* `[ stdenv.hostPlatform.canExecute ] != [ stdenv.hostPlatform.canExecute ]` + +To summarize, pointer equality is established on the memory location of the +`Value` struct in C++ Nix. Except for simple values (`int`, `bool`, …), +the `Value` struct only consists of a pointer to the actual representation +of the value (attribute set, list, function, …) and is thus cheap to copy. +In practice, this happens when a value passes through the evaluation of +almost any Nix expression. Only in the select cases described above +a value preserves its pointer equality despite being unchanged by an +expression. We can call this behavior *exterior pointer equality*. + ## Summary When comparing two Nix values, we must force both of them (non-recursively!), but are @@ -207,3 +333,6 @@ its original introduction (maybe performance?). [outlived builderDefs]: https://github.com/NixOS/nixpkgs/issues/4210 [CompareValues]: https://github.com/NixOS/nix/blob/3c618c43c6044eda184df235c193877529e951cb/src/libexpr/primops.cc#L569-L610 [nix-2.5-changelog]: https://nixos.org/manual/nix/stable/release-notes/rl-2.5.html +[eval-maybeThunk]: https://github.com/NixOS/nix/blob/3c618c43c6044eda184df235c193877529e951cb/src/libexpr/nixexpr.hh#L161-L162 +[maybeThunk-default]: https://github.com/NixOS/nix/blob/8e770dac9f68162cfbb368e53f928df491babff3/src/libexpr/eval.cc#L1076-L1081 +[maybeThunk-ExprVar]: https://github.com/NixOS/nix/blob/8e770dac9f68162cfbb368e53f928df491babff3/src/libexpr/eval.cc#L1084-L1091 diff --git a/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-builtins-set-pointer-equality.exp b/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-builtins-set-pointer-equality.exp index eb05f4caf03b..097eb2033aa5 100644 --- a/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-builtins-set-pointer-equality.exp +++ b/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-builtins-set-pointer-equality.exp @@ -1 +1 @@ -[ true true true true true true true true false false true ] +[ true true true true true true true true true true ] diff --git a/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-builtins-set-pointer-equality.nix b/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-builtins-set-pointer-equality.nix index 678d6139ee03..aa2a0a1e198f 100644 --- a/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-builtins-set-pointer-equality.nix +++ b/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-builtins-set-pointer-equality.nix @@ -12,9 +12,14 @@ in (alias == builtins.builtins) ([ builtins ] == [ builtins ]) - # Surprisingly this only works with the set - ([ builtins.add ] == [ builtins.add ]) - ({ inherit (builtins) import; } == { inherit (builtins) import; }) - # But this does + # Surprisingly the following expressions don't work. They are + # here for documentation purposes and covered only + # by eval-okay-select-pointer-inequality.nix. Reasoning is that + # we may not want / be able to replicate this behavior at all. + # ([ builtins.add ] == [ builtins.add ]) + # ({ inherit (builtins) import; } == { inherit (builtins) import; }) + + # These expressions work as expected, however: (let x = { inherit (builtins) add; }; in x == x) + (let inherit (builtins) add; in [ add ] == [ add ]) ] diff --git a/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-non-identifier-pointer-inequality.exp b/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-non-identifier-pointer-inequality.exp new file mode 100644 index 000000000000..69fd1d084749 --- /dev/null +++ b/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-non-identifier-pointer-inequality.exp @@ -0,0 +1 @@ +[ false false false false false true false false ] diff --git a/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-non-identifier-pointer-inequality.nix b/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-non-identifier-pointer-inequality.nix new file mode 100644 index 000000000000..821aa47a0d2c --- /dev/null +++ b/tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-non-identifier-pointer-inequality.nix @@ -0,0 +1,28 @@ +# C++ Nix frequently creates copies of Value structs when evaluating +# a variety of expressions. As a result, pointer equality doesn't +# work for many (all?) expressions that go beyond simple identifier +# access from the scope: Even if the inner representation of the +# value still has the same memory location, C++ Nix has created +# a copy of the struct that holds the pointer to this memory. +# Since pointer equality is established via the location of +# the latter, not the former, the values are no longer equal +# by pointer. +let + foo = { bar = x: x; }; + + id = x: x; +in + +[ + ({ inherit (foo) bar; } == { inherit (foo) bar; }) + ([ foo.bar ] == [ foo.bar ]) + + ([ builtins.add ] == [ builtins.add ]) + ({ inherit (builtins) import; } == { inherit (builtins) import; }) + + ([ (id id) ] == [ (id id) ]) + ([ id ] == [ id ]) + + (with foo; [ bar ] == [ bar ]) + (with builtins; [ add ] == [ add ]) +] -- cgit 1.4.1