diff options
5 files changed, 169 insertions, 6 deletions
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 ]) +] |