docs(tvix): document when pointer equality is preserved in C++ Nix r/6405

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 <sternenseemann@systemli.org>
Reviewed-by: tazjin <tazjin@tvl.su>

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 ])
+]