about summary refs log tree commit diff
diff options
context:
space:
mode:
-rw-r--r--tvix/docs/value-pointer-equality.md131
-rw-r--r--tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-builtins-set-pointer-equality.exp2
-rw-r--r--tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-builtins-set-pointer-equality.nix13
-rw-r--r--tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-non-identifier-pointer-inequality.exp1
-rw-r--r--tvix/eval/src/tests/tvix_tests/notyetpassing/eval-okay-non-identifier-pointer-inequality.nix28
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 ])
+]