Use `std::set<StringContextElem>` not `PathSet` for string contexts

Motivation

`PathSet` is not correct because string contexts have other forms
(`Built` and `DrvDeep`) that are not rendered as plain store paths.
Instead of wrongly using `PathSet`, or "stringly typed" using
`StringSet`, use `std::std<StringContextElem>`.

-----

In support of this change, `NixStringContext` is now defined as
`std::std<StringContextElem>` not `std:vector<StringContextElem>`. The
old definition was just used by a `getContext` method which was only
used by the eval cache. It can be deleted altogether since the types are
now unified and the preexisting `copyContext` function already suffices.

Summarizing the previous paragraph:

Old:

  - `value/context.hh`: `NixStringContext = std::vector<StringContextElem>`
  - `value.hh`: `NixStringContext Value::getContext(...)`
  - `value.hh`: `copyContext(...)`

New:

  - `value/context.hh`: `NixStringContext = std::set<StringContextElem>`
  - `value.hh`: `copyContext(...)`
----

The string representation of string context elements no longer contains
the store dir. The diff of `src/libexpr/tests/value/context.cc` should
make clear what the new representation is, so we recommend reviewing
that file first. This was done for two reasons:

Less API churn:

`Value::mkString` and friends did not take a `Store` before. But if
`NixStringContextElem::{parse, to_string}` *do* take a store (as they
did before), then we cannot have the `Value` functions use them (in
order to work with the fully-structured `NixStringContext`) without
adding that argument.

That would have been a lot of churn of threading the store, and this
diff is already large enough, so the easier and less invasive thing to
do was simply make the element `parse` and `to_string` functions not
take the `Store` reference, and the easiest way to do that was to simply
drop the store dir.

Space usage:

Dropping the `/nix/store/` (or similar) from the internal representation
will safe space in the heap of the Nix programming being interpreted. If
the heap contains many strings with non-trivial contexts, the saving
could add up to something significant.

----

The eval cache version is bumped.

The eval cache serialization uses `NixStringContextElem::{parse,
to_string}`, and since those functions are changed per the above, that
means the on-disk representation is also changed.

This is simply done by changing the name of the used for the eval cache
from `eval-cache-v4` to eval-cache-v5`.

----

To avoid some duplication `EvalCache::mkPathString` is added to abstract
over the simple case of turning a store path to a string with just that
string in the context.

Context

This PR picks up where #7543 left off. That one introduced the fully
structured `NixStringContextElem` data type, but kept `PathSet context`
as an awkward middle ground between internal `char[][]` interpreter heap
string contexts and `NixStringContext` fully parsed string contexts.

The infelicity of `PathSet context` was specifically called out during
Nix team group review, but it was agreeing that fixing it could be left
as future work. This is that future work.

A possible follow-up step would be to get rid of the `char[][]`
evaluator heap representation, too, but it is not yet clear how to do
that. To use `NixStringContextElem` there we would need to get the STL
containers to GC pointers in the GC build, and I am not sure how to do
that.

----

PR #7543 effectively is writing the inverse of a `mkPathString`,
`mkOutputString`, and one more such function for the `DrvDeep` case. I
would like that PR to have property tests ensuring it is actually the
inverse as expected.

This PR sets things up nicely so that reworking that PR to be in that
more elegant and better tested way is possible.

Co-authored-by: Théophane Hufschmitt <7226587+thufschmitt@users.noreply.github.com>

4 files changed, 38 insertions, 33 deletions

diff --git a/src/libexpr/primops/context.cc b/src/libexpr/primops/context.cc
index db43e5771..07bf400cf 100644
--- a/src/libexpr/primops/context.cc
+++ b/src/libexpr/primops/context.cc
@@ -7,7 +7,7 @@ namespace nix {
 
 static void prim_unsafeDiscardStringContext(EvalState & state, const PosIdx pos, Value * * args, Value & v)
 {
-    PathSet context;
+    NixStringContext context;
     auto s = state.coerceToString(pos, *args[0], context, "while evaluating the argument passed to builtins.unsafeDiscardStringContext");
     v.mkString(*s);
 }
@@ -17,7 +17,7 @@ static RegisterPrimOp primop_unsafeDiscardStringContext("__unsafeDiscardStringCo
 
 static void prim_hasContext(EvalState & state, const PosIdx pos, Value * * args, Value & v)
 {
-    PathSet context;
+    NixStringContext context;
     state.forceString(*args[0], context, pos, "while evaluating the argument passed to builtins.hasContext");
     v.mkBool(!context.empty());
 }
@@ -33,17 +33,18 @@ static RegisterPrimOp primop_hasContext("__hasContext", 1, prim_hasContext);
    drv.inputDrvs. */
 static void prim_unsafeDiscardOutputDependency(EvalState & state, const PosIdx pos, Value * * args, Value & v)
 {
-    PathSet context;
+    NixStringContext context;
     auto s = state.coerceToString(pos, *args[0], context, "while evaluating the argument passed to builtins.unsafeDiscardOutputDependency");
 
-    PathSet context2;
-    for (auto && p : context) {
-        auto c = NixStringContextElem::parse(*state.store, p);
+    NixStringContext context2;
+    for (auto && c : context) {
         if (auto * ptr = std::get_if<NixStringContextElem::DrvDeep>(&c)) {
-            context2.emplace(state.store->printStorePath(ptr->drvPath));
+            context2.emplace(NixStringContextElem::Opaque {
+                .path = ptr->drvPath
+            });
         } else {
             /* Can reuse original item */
-            context2.emplace(std::move(p));
+            context2.emplace(std::move(c));
         }
     }
 
@@ -79,22 +80,21 @@ static void prim_getContext(EvalState & state, const PosIdx pos, Value * * args,
         bool allOutputs = false;
         Strings outputs;
     };
-    PathSet context;
+    NixStringContext context;
     state.forceString(*args[0], context, pos, "while evaluating the argument passed to builtins.getContext");
     auto contextInfos = std::map<StorePath, ContextInfo>();
-    for (const auto & p : context) {
-        NixStringContextElem ctx = NixStringContextElem::parse(*state.store, p);
+    for (auto && i : context) {
         std::visit(overloaded {
-            [&](NixStringContextElem::DrvDeep & d) {
-                contextInfos[d.drvPath].allOutputs = true;
+            [&](NixStringContextElem::DrvDeep && d) {
+                contextInfos[std::move(d.drvPath)].allOutputs = true;
             },
-            [&](NixStringContextElem::Built & b) {
-                contextInfos[b.drvPath].outputs.emplace_back(std::move(b.output));
+            [&](NixStringContextElem::Built && b) {
+                contextInfos[std::move(b.drvPath)].outputs.emplace_back(std::move(b.output));
             },
-            [&](NixStringContextElem::Opaque & o) {
-                contextInfos[o.path].path = true;
+            [&](NixStringContextElem::Opaque && o) {
+                contextInfos[std::move(o.path)].path = true;
             },
-        }, ctx.raw());
+        }, ((NixStringContextElem &&) i).raw());
     }
 
     auto attrs = state.buildBindings(contextInfos.size());
@@ -129,7 +129,7 @@ static RegisterPrimOp primop_getContext("__getContext", 1, prim_getContext);
 */
 static void prim_appendContext(EvalState & state, const PosIdx pos, Value * * args, Value & v)
 {
-    PathSet context;
+    NixStringContext context;
     auto orig = state.forceString(*args[0], context, noPos, "while evaluating the first argument passed to builtins.appendContext");
 
     state.forceAttrs(*args[1], pos, "while evaluating the second argument passed to builtins.appendContext");
@@ -143,13 +143,16 @@ static void prim_appendContext(EvalState & state, const PosIdx pos, Value * * ar
                 .msg = hintfmt("context key '%s' is not a store path", name),
                 .errPos = state.positions[i.pos]
             });
+        auto namePath = state.store->parseStorePath(name);
         if (!settings.readOnlyMode)
-            state.store->ensurePath(state.store->parseStorePath(name));
+            state.store->ensurePath(namePath);
         state.forceAttrs(*i.value, i.pos, "while evaluating the value of a string context");
         auto iter = i.value->attrs->find(sPath);
         if (iter != i.value->attrs->end()) {
             if (state.forceBool(*iter->value, iter->pos, "while evaluating the `path` attribute of a string context"))
-                context.emplace(name);
+                context.emplace(NixStringContextElem::Opaque {
+                    .path = namePath,
+                });
         }
 
         iter = i.value->attrs->find(sAllOutputs);
@@ -161,7 +164,9 @@ static void prim_appendContext(EvalState & state, const PosIdx pos, Value * * ar
                         .errPos = state.positions[i.pos]
                     });
                 }
-                context.insert(concatStrings("=", name));
+                context.emplace(NixStringContextElem::DrvDeep {
+                    .drvPath = namePath,
+                });
             }
         }
 
@@ -176,7 +181,10 @@ static void prim_appendContext(EvalState & state, const PosIdx pos, Value * * ar
             }
             for (auto elem : iter->value->listItems()) {
                 auto outputName = state.forceStringNoCtx(*elem, iter->pos, "while evaluating an output name within a string context");
-                context.insert(concatStrings("!", outputName, "!", name));
+                context.emplace(NixStringContextElem::Built {
+                    .drvPath = namePath,
+                    .output = std::string { outputName },
+                });
             }
         }
     }
diff --git a/src/libexpr/primops/fetchClosure.cc b/src/libexpr/primops/fetchClosure.cc
index 0dfa97fa3..4cf1f1e0b 100644
--- a/src/libexpr/primops/fetchClosure.cc
+++ b/src/libexpr/primops/fetchClosure.cc
@@ -18,7 +18,7 @@ static void prim_fetchClosure(EvalState & state, const PosIdx pos, Value * * arg
         const auto & attrName = state.symbols[attr.name];
 
         if (attrName == "fromPath") {
-            PathSet context;
+            NixStringContext context;
             fromPath = state.coerceToStorePath(attr.pos, *attr.value, context,
                     "while evaluating the 'fromPath' attribute passed to builtins.fetchClosure");
         }
@@ -27,7 +27,7 @@ static void prim_fetchClosure(EvalState & state, const PosIdx pos, Value * * arg
             state.forceValue(*attr.value, attr.pos);
             toCA = true;
             if (attr.value->type() != nString || attr.value->string.s != std::string("")) {
-                PathSet context;
+                NixStringContext context;
                 toPath = state.coerceToStorePath(attr.pos, *attr.value, context,
                         "while evaluating the 'toPath' attribute passed to builtins.fetchClosure");
             }
@@ -114,8 +114,7 @@ static void prim_fetchClosure(EvalState & state, const PosIdx pos, Value * * arg
             });
     }
 
-    auto toPathS = state.store->printStorePath(*toPath);
-    v.mkString(toPathS, {toPathS});
+    state.mkStorePathString(*toPath, v);
 }
 
 static RegisterPrimOp primop_fetchClosure({
diff --git a/src/libexpr/primops/fetchMercurial.cc b/src/libexpr/primops/fetchMercurial.cc
index c41bd60b6..2c0d98e74 100644
--- a/src/libexpr/primops/fetchMercurial.cc
+++ b/src/libexpr/primops/fetchMercurial.cc
@@ -13,7 +13,7 @@ static void prim_fetchMercurial(EvalState & state, const PosIdx pos, Value * * a
     std::optional<Hash> rev;
     std::optional<std::string> ref;
     std::string_view name = "source";
-    PathSet context;
+    NixStringContext context;
 
     state.forceValue(*args[0], pos);
 
@@ -73,8 +73,7 @@ static void prim_fetchMercurial(EvalState & state, const PosIdx pos, Value * * a
     auto [tree, input2] = input.fetch(state.store);
 
     auto attrs2 = state.buildBindings(8);
-    auto storePath = state.store->printStorePath(tree.storePath);
-    attrs2.alloc(state.sOutPath).mkString(storePath, {storePath});
+    state.mkStorePathString(tree.storePath, attrs2.alloc(state.sOutPath));
     if (input2.getRef())
         attrs2.alloc("branch").mkString(*input2.getRef());
     // Backward compatibility: set 'rev' to
diff --git a/src/libexpr/primops/fetchTree.cc b/src/libexpr/primops/fetchTree.cc
index 2e150c9d0..cd7039025 100644
--- a/src/libexpr/primops/fetchTree.cc
+++ b/src/libexpr/primops/fetchTree.cc
@@ -24,9 +24,8 @@ void emitTreeAttrs(
 
     auto attrs = state.buildBindings(8);
 
-    auto storePath = state.store->printStorePath(tree.storePath);
 
-    attrs.alloc(state.sOutPath).mkString(storePath, {storePath});
+    state.mkStorePathString(tree.storePath, attrs.alloc(state.sOutPath));
 
     // FIXME: support arbitrary input attributes.
 
@@ -107,7 +106,7 @@ static void fetchTree(
     const FetchTreeParams & params = FetchTreeParams{}
 ) {
     fetchers::Input input;
-    PathSet context;
+    NixStringContext context;
 
     state.forceValue(*args[0], pos);