Merge branch 'path-info' into ca-drv-exotic

1 files changed, 585 insertions, 419 deletions

diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 8f6e937ec..027030879 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -12,6 +12,8 @@
 #include "value-to-xml.hh"
 #include "primops.hh"
 
+#include <boost/container/small_vector.hpp>
+
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <unistd.h>
@@ -35,9 +37,10 @@ namespace nix {
 InvalidPathError::InvalidPathError(const Path & path) :
     EvalError("path '%s' is not valid", path), path(path) {}
 
-void EvalState::realiseContext(const PathSet & context)
+StringMap EvalState::realiseContext(const PathSet & context)
 {
     std::vector<DerivedPath::Built> drvs;
+    StringMap res;
 
     for (auto & i : context) {
         auto [ctxS, outputName] = decodeContext(i);
@@ -46,10 +49,12 @@ void EvalState::realiseContext(const PathSet & context)
             throw InvalidPathError(store->printStorePath(ctx));
         if (!outputName.empty() && ctx.isDerivation()) {
             drvs.push_back({ctx, {outputName}});
+        } else {
+            res.insert_or_assign(ctxS, ctxS);
         }
     }
 
-    if (drvs.empty()) return;
+    if (drvs.empty()) return {};
 
     if (!evalSettings.enableImportFromDerivation)
         throw Error(
@@ -61,19 +66,62 @@ void EvalState::realiseContext(const PathSet & context)
     for (auto & d : drvs) buildReqs.emplace_back(DerivedPath { d });
     store->buildPaths(buildReqs);
 
+    /* Get all the output paths corresponding to the placeholders we had */
+    for (auto & [drvPath, outputs] : drvs) {
+        auto outputPaths = store->queryDerivationOutputMap(drvPath);
+        for (auto & outputName : outputs) {
+            if (outputPaths.count(outputName) == 0)
+                throw Error("derivation '%s' does not have an output named '%s'",
+                        store->printStorePath(drvPath), outputName);
+            res.insert_or_assign(
+                downstreamPlaceholder(*store, drvPath, outputName),
+                store->printStorePath(outputPaths.at(outputName))
+            );
+        }
+    }
+
     /* Add the output of this derivations to the allowed
        paths. */
     if (allowedPaths) {
-        for (auto & [drvPath, outputs] : drvs) {
-            auto outputPaths = store->queryDerivationOutputMap(drvPath);
-            for (auto & outputName : outputs) {
-                if (outputPaths.count(outputName) == 0)
-                    throw Error("derivation '%s' does not have an output named '%s'",
-                            store->printStorePath(drvPath), outputName);
-                allowedPaths->insert(store->printStorePath(outputPaths.at(outputName)));
-            }
+        for (auto & [_placeholder, outputPath] : res) {
+            allowPath(store->toRealPath(outputPath));
         }
     }
+
+    return res;
+}
+
+struct RealisePathFlags {
+    // Whether to check that the path is allowed in pure eval mode
+    bool checkForPureEval = true;
+};
+
+static Path realisePath(EvalState & state, const Pos & pos, Value & v, const RealisePathFlags flags = {})
+{
+    PathSet context;
+
+    auto path = [&]()
+    {
+        try {
+            return state.coerceToPath(pos, v, context);
+        } catch (Error & e) {
+            e.addTrace(pos, "while realising the context of a path");
+            throw;
+        }
+    }();
+
+    try {
+        StringMap rewrites = state.realiseContext(context);
+
+        auto realPath = state.toRealPath(rewriteStrings(path, rewrites), context);
+
+        return flags.checkForPureEval
+            ? state.checkSourcePath(realPath)
+            : realPath;
+    } catch (Error & e) {
+        e.addTrace(pos, "while realising the context of path '%s'", path);
+        throw;
+    }
 }
 
 /* Add and attribute to the given attribute map from the output name to
@@ -88,13 +136,15 @@ void EvalState::realiseContext(const PathSet & context)
    the actual path.
 
    The 'drv' and 'drvPath' outputs must correspond. */
-static void mkOutputString(EvalState & state, Value & v,
-    const StorePath & drvPath, const BasicDerivation & drv,
-    std::pair<string, DerivationOutput> o)
+static void mkOutputString(
+    EvalState & state,
+    BindingsBuilder & attrs,
+    const StorePath & drvPath,
+    const BasicDerivation & drv,
+    const std::pair<std::string, DerivationOutput> & o)
 {
     auto optOutputPath = o.second.path(*state.store, drv.name, o.first);
-    mkString(
-        *state.allocAttr(v, state.symbols.create(o.first)),
+    attrs.alloc(o.first).mkString(
         optOutputPath
             ? state.store->printStorePath(*optOutputPath)
             /* Downstream we would substitute this for an actual path once
@@ -109,22 +159,7 @@ static void mkOutputString(EvalState & state, Value & v,
    argument. */
 static void import(EvalState & state, const Pos & pos, Value & vPath, Value * vScope, Value & v)
 {
-    PathSet context;
-    Path path = state.coerceToPath(pos, vPath, context);
-
-    try {
-        state.realiseContext(context);
-    } catch (InvalidPathError & e) {
-        throw EvalError({
-            .msg = hintfmt("cannot import '%1%', since path '%2%' is not valid", path, e.path),
-            .errPos = pos
-        });
-    } catch (Error & e) {
-        e.addTrace(pos, "while importing '%s'", path);
-        throw;
-    }
-
-    Path realPath = state.checkSourcePath(state.toRealPath(path, context));
+    auto path = realisePath(state, pos, vPath);
 
     // FIXME
     auto isValidDerivationInStore = [&]() -> std::optional<StorePath> {
@@ -139,23 +174,19 @@ static void import(EvalState & state, const Pos & pos, Value & vPath, Value * vS
     if (auto optStorePath = isValidDerivationInStore()) {
         auto storePath = *optStorePath;
         Derivation drv = state.store->readDerivation(storePath);
-        Value & w = *state.allocValue();
-        state.mkAttrs(w, 3 + drv.outputs.size());
-        Value * v2 = state.allocAttr(w, state.sDrvPath);
-        mkString(*v2, path, {"=" + path});
-        v2 = state.allocAttr(w, state.sName);
-        mkString(*v2, drv.env["name"]);
-        Value * outputsVal =
-            state.allocAttr(w, state.symbols.create("outputs"));
-        state.mkList(*outputsVal, drv.outputs.size());
-        unsigned int outputs_index = 0;
-
-        for (const auto & o : drv.outputs) {
-            mkOutputString(state, w, storePath, drv, o);
-            outputsVal->listElems()[outputs_index] = state.allocValue();
-            mkString(*(outputsVal->listElems()[outputs_index++]), o.first);
+        auto attrs = state.buildBindings(3 + drv.outputs.size());
+        attrs.alloc(state.sDrvPath).mkString(path, {"=" + path});
+        attrs.alloc(state.sName).mkString(drv.env["name"]);
+        auto & outputsVal = attrs.alloc(state.sOutputs);
+        state.mkList(outputsVal, drv.outputs.size());
+
+        for (const auto & [i, o] : enumerate(drv.outputs)) {
+            mkOutputString(state, attrs, storePath, drv, o);
+            (outputsVal.listElems()[i] = state.allocValue())->mkString(o.first);
         }
-        w.attrs->sort();
+
+        auto w = state.allocValue();
+        w->mkAttrs(attrs);
 
         if (!state.vImportedDrvToDerivation) {
             state.vImportedDrvToDerivation = allocRootValue(state.allocValue());
@@ -165,7 +196,7 @@ static void import(EvalState & state, const Pos & pos, Value & vPath, Value * vS
         }
 
         state.forceFunction(**state.vImportedDrvToDerivation, pos);
-        mkApp(v, **state.vImportedDrvToDerivation, w);
+        v.mkApp(*state.vImportedDrvToDerivation, w);
         state.forceAttrs(v, pos);
     }
 
@@ -177,23 +208,26 @@ static void import(EvalState & state, const Pos & pos, Value & vPath, Value * vS
 
     else {
         if (!vScope)
-            state.evalFile(realPath, v);
+            state.evalFile(path, v);
         else {
-            state.forceAttrs(*vScope);
+            state.forceAttrs(*vScope, pos);
 
             Env * env = &state.allocEnv(vScope->attrs->size());
             env->up = &state.baseEnv;
 
-            StaticEnv staticEnv(false, &state.staticBaseEnv);
+            StaticEnv staticEnv(false, &state.staticBaseEnv, vScope->attrs->size());
 
             unsigned int displ = 0;
             for (auto & attr : *vScope->attrs) {
-                staticEnv.vars[attr.name] = displ;
+                staticEnv.vars.emplace_back(attr.name, displ);
                 env->values[displ++] = attr.value;
             }
 
-            printTalkative("evaluating file '%1%'", realPath);
-            Expr * e = state.parseExprFromFile(resolveExprPath(realPath), staticEnv);
+            // No need to call staticEnv.sort(), because
+            // args[0]->attrs is already sorted.
+
+            printTalkative("evaluating file '%1%'", path);
+            Expr * e = state.parseExprFromFile(resolveExprPath(path), staticEnv);
 
             e->eval(state, *env, v);
         }
@@ -278,23 +312,9 @@ extern "C" typedef void (*ValueInitializer)(EvalState & state, Value & v);
 /* Load a ValueInitializer from a DSO and return whatever it initializes */
 void prim_importNative(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    PathSet context;
-    Path path = state.coerceToPath(pos, *args[0], context);
-
-    try {
-        state.realiseContext(context);
-    } catch (InvalidPathError & e) {
-        throw EvalError({
-            .msg = hintfmt(
-                "cannot import '%1%', since path '%2%' is not valid",
-                path, e.path),
-            .errPos = pos
-        });
-    }
-
-    path = state.checkSourcePath(path);
+    auto path = realisePath(state, pos, *args[0]);
 
-    string sym = state.forceStringNoCtx(*args[1], pos);
+    std::string sym(state.forceStringNoCtx(*args[1], pos));
 
     void *handle = dlopen(path.c_str(), RTLD_LAZY | RTLD_LOCAL);
     if (!handle)
@@ -330,13 +350,13 @@ void prim_exec(EvalState & state, const Pos & pos, Value * * args, Value & v)
         });
     }
     PathSet context;
-    auto program = state.coerceToString(pos, *elems[0], context, false, false);
+    auto program = state.coerceToString(pos, *elems[0], context, false, false).toOwned();
     Strings commandArgs;
     for (unsigned int i = 1; i < args[0]->listSize(); ++i) {
-        commandArgs.emplace_back(state.coerceToString(pos, *elems[i], context, false, false));
+        commandArgs.push_back(state.coerceToString(pos, *elems[i], context, false, false).toOwned());
     }
     try {
-        state.realiseContext(context);
+        auto _ = state.realiseContext(context); // FIXME: Handle CA derivations
     } catch (InvalidPathError & e) {
         throw EvalError({
             .msg = hintfmt("cannot execute '%1%', since path '%2%' is not valid",
@@ -348,7 +368,7 @@ void prim_exec(EvalState & state, const Pos & pos, Value * * args, Value & v)
     auto output = runProgram(program, true, commandArgs);
     Expr * parsed;
     try {
-        parsed = state.parseExprFromString(output, pos.file);
+        parsed = state.parseExprFromString(std::move(output), pos.file);
     } catch (Error & e) {
         e.addTrace(pos, "While parsing the output from '%1%'", program);
         throw;
@@ -366,7 +386,7 @@ void prim_exec(EvalState & state, const Pos & pos, Value * * args, Value & v)
 static void prim_typeOf(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceValue(*args[0], pos);
-    string t;
+    std::string t;
     switch (args[0]->type()) {
         case nInt: t = "int"; break;
         case nBool: t = "bool"; break;
@@ -382,7 +402,7 @@ static void prim_typeOf(EvalState & state, const Pos & pos, Value * * args, Valu
         case nFloat: t = "float"; break;
         case nThunk: abort();
     }
-    mkString(v, state.symbols.create(t));
+    v.mkString(state.symbols.create(t));
 }
 
 static RegisterPrimOp primop_typeOf({
@@ -400,7 +420,7 @@ static RegisterPrimOp primop_typeOf({
 static void prim_isNull(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceValue(*args[0], pos);
-    mkBool(v, args[0]->type() == nNull);
+    v.mkBool(args[0]->type() == nNull);
 }
 
 static RegisterPrimOp primop_isNull({
@@ -420,7 +440,7 @@ static RegisterPrimOp primop_isNull({
 static void prim_isFunction(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceValue(*args[0], pos);
-    mkBool(v, args[0]->type() == nFunction);
+    v.mkBool(args[0]->type() == nFunction);
 }
 
 static RegisterPrimOp primop_isFunction({
@@ -436,7 +456,7 @@ static RegisterPrimOp primop_isFunction({
 static void prim_isInt(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceValue(*args[0], pos);
-    mkBool(v, args[0]->type() == nInt);
+    v.mkBool(args[0]->type() == nInt);
 }
 
 static RegisterPrimOp primop_isInt({
@@ -452,7 +472,7 @@ static RegisterPrimOp primop_isInt({
 static void prim_isFloat(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceValue(*args[0], pos);
-    mkBool(v, args[0]->type() == nFloat);
+    v.mkBool(args[0]->type() == nFloat);
 }
 
 static RegisterPrimOp primop_isFloat({
@@ -468,7 +488,7 @@ static RegisterPrimOp primop_isFloat({
 static void prim_isString(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceValue(*args[0], pos);
-    mkBool(v, args[0]->type() == nString);
+    v.mkBool(args[0]->type() == nString);
 }
 
 static RegisterPrimOp primop_isString({
@@ -484,7 +504,7 @@ static RegisterPrimOp primop_isString({
 static void prim_isBool(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceValue(*args[0], pos);
-    mkBool(v, args[0]->type() == nBool);
+    v.mkBool(args[0]->type() == nBool);
 }
 
 static RegisterPrimOp primop_isBool({
@@ -500,7 +520,7 @@ static RegisterPrimOp primop_isBool({
 static void prim_isPath(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceValue(*args[0], pos);
-    mkBool(v, args[0]->type() == nPath);
+    v.mkBool(args[0]->type() == nPath);
 }
 
 static RegisterPrimOp primop_isPath({
@@ -514,7 +534,11 @@ static RegisterPrimOp primop_isPath({
 
 struct CompareValues
 {
-    bool operator () (const Value * v1, const Value * v2) const
+    EvalState & state;
+
+    CompareValues(EvalState & state) : state(state) { };
+
+    bool operator () (Value * v1, Value * v2) const
     {
         if (v1->type() == nFloat && v2->type() == nInt)
             return v1->fpoint < v2->integer;
@@ -531,6 +555,17 @@ struct CompareValues
                 return strcmp(v1->string.s, v2->string.s) < 0;
             case nPath:
                 return strcmp(v1->path, v2->path) < 0;
+            case nList:
+                // Lexicographic comparison
+                for (size_t i = 0;; i++) {
+                    if (i == v2->listSize()) {
+                        return false;
+                    } else if (i == v1->listSize()) {
+                        return true;
+                    } else if (!state.eqValues(*v1->listElems()[i], *v2->listElems()[i])) {
+                        return (*this)(v1->listElems()[i], v2->listElems()[i]);
+                    }
+                }
             default:
                 throw EvalError("cannot compare %1% with %2%", showType(*v1), showType(*v2));
         }
@@ -539,24 +574,24 @@ struct CompareValues
 
 
 #if HAVE_BOEHMGC
-typedef list<Value *, gc_allocator<Value *> > ValueList;
+typedef std::list<Value *, gc_allocator<Value *> > ValueList;
 #else
-typedef list<Value *> ValueList;
+typedef std::list<Value *> ValueList;
 #endif
 
 
 static Bindings::iterator getAttr(
     EvalState & state,
-    string funcName,
-    string attrName,
+    std::string_view funcName,
+    Symbol attrSym,
     Bindings * attrSet,
     const Pos & pos)
 {
-    Bindings::iterator value = attrSet->find(state.symbols.create(attrName));
+    Bindings::iterator value = attrSet->find(attrSym);
     if (value == attrSet->end()) {
         hintformat errorMsg = hintfmt(
             "attribute '%s' missing for call to '%s'",
-            attrName,
+            attrSym,
             funcName
         );
 
@@ -575,7 +610,7 @@ static Bindings::iterator getAttr(
             // Adding another trace for the function name to make it clear
             // which call received wrong arguments.
             e.addTrace(pos, hintfmt("while invoking '%s'", funcName));
-            throw;
+            throw e;
         }
     }
 
@@ -590,7 +625,7 @@ static void prim_genericClosure(EvalState & state, const Pos & pos, Value * * ar
     Bindings::iterator startSet = getAttr(
         state,
         "genericClosure",
-        "startSet",
+        state.sStartSet,
         args[0]->attrs,
         pos
     );
@@ -598,14 +633,14 @@ static void prim_genericClosure(EvalState & state, const Pos & pos, Value * * ar
     state.forceList(*startSet->value, pos);
 
     ValueList workSet;
-    for (unsigned int n = 0; n < startSet->value->listSize(); ++n)
-        workSet.push_back(startSet->value->listElems()[n]);
+    for (auto elem : startSet->value->listItems())
+        workSet.push_back(elem);
 
     /* Get the operator. */
     Bindings::iterator op = getAttr(
         state,
         "genericClosure",
-        "operator",
+        state.sOperator,
         args[0]->attrs,
         pos
     );
@@ -618,7 +653,8 @@ static void prim_genericClosure(EvalState & state, const Pos & pos, Value * * ar
     ValueList res;
     // `doneKeys' doesn't need to be a GC root, because its values are
     // reachable from res.
-    set<Value *, CompareValues> doneKeys;
+    auto cmp = CompareValues(state);
+    std::set<Value *, decltype(cmp)> doneKeys(cmp);
     while (!workSet.empty()) {
         Value * e = *(workSet.begin());
         workSet.pop_front();
@@ -626,7 +662,7 @@ static void prim_genericClosure(EvalState & state, const Pos & pos, Value * * ar
         state.forceAttrs(*e, pos);
 
         Bindings::iterator key =
-            e->attrs->find(state.symbols.create("key"));
+            e->attrs->find(state.sKey);
         if (key == e->attrs->end())
             throw EvalError({
                 .msg = hintfmt("attribute 'key' required"),
@@ -639,13 +675,13 @@ static void prim_genericClosure(EvalState & state, const Pos & pos, Value * * ar
 
         /* Call the `operator' function with `e' as argument. */
         Value call;
-        mkApp(call, *op->value, *e);
+        call.mkApp(op->value, e);
         state.forceList(call, pos);
 
         /* Add the values returned by the operator to the work set. */
-        for (unsigned int n = 0; n < call.listSize(); ++n) {
-            state.forceValue(*call.listElems()[n], pos);
-            workSet.push_back(call.listElems()[n]);
+        for (auto elem : call.listItems()) {
+            state.forceValue(*elem, pos);
+            workSet.push_back(elem);
         }
     }
 
@@ -671,7 +707,7 @@ static RegisterPrimOp primop_abort({
     .fun = [](EvalState & state, const Pos & pos, Value * * args, Value & v)
     {
         PathSet context;
-        string s = state.coerceToString(pos, *args[0], context);
+        auto s = state.coerceToString(pos, *args[0], context).toOwned();
         throw Abort("evaluation aborted with the following error message: '%1%'", s);
     }
 });
@@ -689,7 +725,7 @@ static RegisterPrimOp primop_throw({
     .fun = [](EvalState & state, const Pos & pos, Value * * args, Value & v)
     {
       PathSet context;
-      string s = state.coerceToString(pos, *args[0], context);
+      auto s = state.coerceToString(pos, *args[0], context).toOwned();
       throw ThrownError(s);
     }
 });
@@ -701,7 +737,7 @@ static void prim_addErrorContext(EvalState & state, const Pos & pos, Value * * a
         v = *args[1];
     } catch (Error & e) {
         PathSet context;
-        e.addTrace(std::nullopt, state.coerceToString(pos, *args[0], context));
+        e.addTrace(std::nullopt, state.coerceToString(pos, *args[0], context).toOwned());
         throw;
     }
 }
@@ -715,7 +751,7 @@ static RegisterPrimOp primop_addErrorContext(RegisterPrimOp::Info {
 static void prim_ceil(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     auto value = state.forceFloat(*args[0], args[0]->determinePos(pos));
-    mkInt(v, ceil(value));
+    v.mkInt(ceil(value));
 }
 
 static RegisterPrimOp primop_ceil({
@@ -734,7 +770,7 @@ static RegisterPrimOp primop_ceil({
 static void prim_floor(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     auto value = state.forceFloat(*args[0], args[0]->determinePos(pos));
-    mkInt(v, floor(value));
+    v.mkInt(floor(value));
 }
 
 static RegisterPrimOp primop_floor({
@@ -754,16 +790,16 @@ static RegisterPrimOp primop_floor({
  * else => {success=false; value=false;} */
 static void prim_tryEval(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    state.mkAttrs(v, 2);
+    auto attrs = state.buildBindings(2);
     try {
         state.forceValue(*args[0], pos);
-        v.attrs->push_back(Attr(state.sValue, args[0]));
-        mkBool(*state.allocAttr(v, state.symbols.create("success")), true);
+        attrs.insert(state.sValue, args[0]);
+        attrs.alloc("success").mkBool(true);
     } catch (AssertionError & e) {
-        mkBool(*state.allocAttr(v, state.sValue), false);
-        mkBool(*state.allocAttr(v, state.symbols.create("success")), false);
+        attrs.alloc(state.sValue).mkBool(false);
+        attrs.alloc("success").mkBool(false);
     }
-    v.attrs->sort();
+    v.mkAttrs(attrs);
 }
 
 static RegisterPrimOp primop_tryEval({
@@ -790,8 +826,8 @@ static RegisterPrimOp primop_tryEval({
 /* Return an environment variable.  Use with care. */
 static void prim_getEnv(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    string name = state.forceStringNoCtx(*args[0], pos);
-    mkString(v, evalSettings.restrictEval || evalSettings.pureEval ? "" : getEnv(name).value_or(""));
+    std::string name(state.forceStringNoCtx(*args[0], pos));
+    v.mkString(evalSettings.restrictEval || evalSettings.pureEval ? "" : getEnv(name).value_or(""));
 }
 
 static RegisterPrimOp primop_getEnv({
@@ -899,7 +935,7 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
         pos
     );
 
-    string drvName;
+    std::string drvName;
     Pos & posDrvName(*attr->pos);
     try {
         drvName = state.forceStringNoCtx(*attr->value, pos);
@@ -937,10 +973,10 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
 
     for (auto & i : args[0]->attrs->lexicographicOrder()) {
         if (i->name == state.sIgnoreNulls) continue;
-        const string & key = i->name;
+        const std::string & key = i->name;
         vomit("processing attribute '%1%'", key);
 
-        auto handleHashMode = [&](const std::string & s) {
+        auto handleHashMode = [&](const std::string_view s) {
             if (s == "recursive") ingestionMethod = FileIngestionMethod::Recursive;
             else if (s == "flat") ingestionMethod = FileIngestionMethod::Flat;
             else if (s == "text") ingestionMethod = TextHashMethod {};
@@ -986,16 +1022,17 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
             }
 
             if (i->name == state.sContentAddressed) {
-                settings.requireExperimentalFeature("ca-derivations");
                 contentAddressed = state.forceBool(*i->value, pos);
+                if (contentAddressed)
+                    settings.requireExperimentalFeature(Xp::CaDerivations);
             }
 
             /* The `args' attribute is special: it supplies the
                command-line arguments to the builder. */
             else if (i->name == state.sArgs) {
                 state.forceList(*i->value, pos);
-                for (unsigned int n = 0; n < i->value->listSize(); ++n) {
-                    string s = state.coerceToString(posDrvName, *i->value->listElems()[n], context, true);
+                for (auto elem : i->value->listItems()) {
+                    auto s = state.coerceToString(posDrvName, *elem, context, true).toOwned();
                     drv.args.push_back(s);
                 }
             }
@@ -1009,7 +1046,7 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
                     if (i->name == state.sStructuredAttrs) continue;
 
                     auto placeholder(jsonObject->placeholder(key));
-                    printValueAsJSON(state, true, *i->value, placeholder, context);
+                    printValueAsJSON(state, true, *i->value, pos, placeholder, context);
 
                     if (i->name == state.sBuilder)
                         drv.builder = state.forceString(*i->value, context, posDrvName);
@@ -1025,18 +1062,18 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
                         /* Require ‘outputs’ to be a list of strings. */
                         state.forceList(*i->value, posDrvName);
                         Strings ss;
-                        for (unsigned int n = 0; n < i->value->listSize(); ++n)
-                            ss.emplace_back(state.forceStringNoCtx(*i->value->listElems()[n], posDrvName));
+                        for (auto elem : i->value->listItems())
+                            ss.emplace_back(state.forceStringNoCtx(*elem, posDrvName));
                         handleOutputs(ss);
                     }
 
                 } else {
-                    auto s = state.coerceToString(*i->pos, *i->value, context, true);
+                    auto s = state.coerceToString(*i->pos, *i->value, context, true).toOwned();
                     drv.env.emplace(key, s);
-                    if (i->name == state.sBuilder) drv.builder = s;
-                    else if (i->name == state.sSystem) drv.platform = s;
-                    else if (i->name == state.sOutputHash) outputHash = s;
-                    else if (i->name == state.sOutputHashAlgo) outputHashAlgo = s;
+                    if (i->name == state.sBuilder) drv.builder = std::move(s);
+                    else if (i->name == state.sSystem) drv.platform = std::move(s);
+                    else if (i->name == state.sOutputHash) outputHash = std::move(s);
+                    else if (i->name == state.sOutputHashAlgo) outputHashAlgo = std::move(s);
                     else if (i->name == state.sOutputHashMode) handleHashMode(s);
                     else if (i->name == state.sOutputs)
                         handleOutputs(tokenizeString<Strings>(s));
@@ -1085,7 +1122,7 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
 
         /* Handle derivation outputs of the form ‘!<name>!<path>’. */
         else if (path.at(0) == '!') {
-            std::pair<string, string> ctx = decodeContext(path);
+            auto ctx = decodeContext(path);
             drv.inputDrvs[state.store->parseStorePath(ctx.first)].insert(ctx.second);
         }
 
@@ -1147,7 +1184,7 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
             drv.outputs.insert_or_assign(i, DerivationOutput {
                 .output = DerivationOutputCAFloating {
                     .method = ingestionMethod,
-                    .hashType = std::move(ht),
+                    .hashType = ht,
                 },
             });
         }
@@ -1220,11 +1257,11 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
         drvHashes.lock()->insert_or_assign(drvPath, h);
     }
 
-    state.mkAttrs(v, 1 + drv.outputs.size());
-    mkString(*state.allocAttr(v, state.sDrvPath), drvPathS, {"=" + drvPathS});
+    auto attrs = state.buildBindings(1 + drv.outputs.size());
+    attrs.alloc(state.sDrvPath).mkString(drvPathS, {"=" + drvPathS});
     for (auto & i : drv.outputs)
-        mkOutputString(state, v, drvPath, drv, i);
-    v.attrs->sort();
+        mkOutputString(state, attrs, drvPath, drv, i);
+    v.mkAttrs(attrs);
 }
 
 static RegisterPrimOp primop_derivationStrict(RegisterPrimOp::Info {
@@ -1237,12 +1274,12 @@ static RegisterPrimOp primop_derivationStrict(RegisterPrimOp::Info {
    substituted by the corresponding output path at build time. For
    example, 'placeholder "out"' returns the string
    /1rz4g4znpzjwh1xymhjpm42vipw92pr73vdgl6xs1hycac8kf2n9. At build
-   time, any occurence of this string in an derivation attribute will
+   time, any occurrence of this string in an derivation attribute will
    be replaced with the concrete path in the Nix store of the output
    ‘out’. */
 static void prim_placeholder(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    mkString(v, hashPlaceholder(state.forceStringNoCtx(*args[0], pos)));
+    v.mkString(hashPlaceholder(state.forceStringNoCtx(*args[0], pos)));
 }
 
 static RegisterPrimOp primop_placeholder({
@@ -1267,7 +1304,7 @@ static void prim_toPath(EvalState & state, const Pos & pos, Value * * args, Valu
 {
     PathSet context;
     Path path = state.coerceToPath(pos, *args[0], context);
-    mkString(v, canonPath(path), context);
+    v.mkString(canonPath(path), context);
 }
 
 static RegisterPrimOp primop_toPath({
@@ -1311,7 +1348,7 @@ static void prim_storePath(EvalState & state, const Pos & pos, Value * * args, V
     if (!settings.readOnlyMode)
         state.store->ensurePath(path2);
     context.insert(state.store->printStorePath(path2));
-    mkString(v, path, context);
+    v.mkString(path, context);
 }
 
 static RegisterPrimOp primop_storePath({
@@ -1334,27 +1371,21 @@ static RegisterPrimOp primop_storePath({
 
 static void prim_pathExists(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    PathSet context;
-    Path path = state.coerceToPath(pos, *args[0], context);
-    try {
-        state.realiseContext(context);
-    } catch (InvalidPathError & e) {
-        throw EvalError({
-            .msg = hintfmt(
-                "cannot check the existence of '%1%', since path '%2%' is not valid",
-                path, e.path),
-            .errPos = pos
-        });
-    }
+    /* We don’t check the path right now, because we don’t want to
+      throw if the path isn’t allowed, but just return false (and we
+      can’t just catch the exception here because we still want to
+      throw if something in the evaluation of `*args[0]` tries to
+      access an unauthorized path). */
+    auto path = realisePath(state, pos, *args[0], { .checkForPureEval = false });
 
     try {
-        mkBool(v, pathExists(state.checkSourcePath(path)));
+        v.mkBool(pathExists(state.checkSourcePath(path)));
     } catch (SysError & e) {
         /* Don't give away info from errors while canonicalising
            ‘path’ in restricted mode. */
-        mkBool(v, false);
+        v.mkBool(false);
     } catch (RestrictedPathError & e) {
-        mkBool(v, false);
+        v.mkBool(false);
     }
 }
 
@@ -1373,7 +1404,7 @@ static RegisterPrimOp primop_pathExists({
 static void prim_baseNameOf(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     PathSet context;
-    mkString(v, baseNameOf(state.coerceToString(pos, *args[0], context, false, false)), context);
+    v.mkString(baseNameOf(*state.coerceToString(pos, *args[0], context, false, false)), context);
 }
 
 static RegisterPrimOp primop_baseNameOf({
@@ -1393,8 +1424,9 @@ static RegisterPrimOp primop_baseNameOf({
 static void prim_dirOf(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     PathSet context;
-    Path dir = dirOf(state.coerceToString(pos, *args[0], context, false, false));
-    if (args[0]->type() == nPath) mkPath(v, dir.c_str()); else mkString(v, dir, context);
+    auto path = state.coerceToString(pos, *args[0], context, false, false);
+    auto dir = dirOf(*path);
+    if (args[0]->type() == nPath) v.mkPath(dir); else v.mkString(dir, context);
 }
 
 static RegisterPrimOp primop_dirOf({
@@ -1411,20 +1443,19 @@ static RegisterPrimOp primop_dirOf({
 /* Return the contents of a file as a string. */
 static void prim_readFile(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    PathSet context;
-    Path path = state.coerceToPath(pos, *args[0], context);
-    try {
-        state.realiseContext(context);
-    } catch (InvalidPathError & e) {
-        throw EvalError({
-            .msg = hintfmt("cannot read '%1%', since path '%2%' is not valid", path, e.path),
-            .errPos = pos
-        });
-    }
-    string s = readFile(state.checkSourcePath(state.toRealPath(path, context)));
-    if (s.find((char) 0) != string::npos)
+    auto path = realisePath(state, pos, *args[0]);
+    auto s = readFile(path);
+    if (s.find((char) 0) != std::string::npos)
         throw Error("the contents of the file '%1%' cannot be represented as a Nix string", path);
-    mkString(v, s.c_str());
+    StorePathSet refs;
+    if (state.store->isInStore(path)) {
+        try {
+            refs = state.store->queryPathInfo(state.store->toStorePath(path).first)->references;
+        } catch (Error &) { // FIXME: should be InvalidPathError
+        }
+    }
+    auto context = state.store->printStorePathSet(refs);
+    v.mkString(s, context);
 }
 
 static RegisterPrimOp primop_readFile({
@@ -1444,28 +1475,28 @@ static void prim_findFile(EvalState & state, const Pos & pos, Value * * args, Va
 
     SearchPath searchPath;
 
-    for (unsigned int n = 0; n < args[0]->listSize(); ++n) {
-        Value & v2(*args[0]->listElems()[n]);
-        state.forceAttrs(v2, pos);
+    for (auto v2 : args[0]->listItems()) {
+        state.forceAttrs(*v2, pos);
 
-        string prefix;
-        Bindings::iterator i = v2.attrs->find(state.symbols.create("prefix"));
-        if (i != v2.attrs->end())
+        std::string prefix;
+        Bindings::iterator i = v2->attrs->find(state.sPrefix);
+        if (i != v2->attrs->end())
             prefix = state.forceStringNoCtx(*i->value, pos);
 
         i = getAttr(
             state,
             "findFile",
-            "path",
-            v2.attrs,
+            state.sPath,
+            v2->attrs,
             pos
         );
 
         PathSet context;
-        string path = state.coerceToString(pos, *i->value, context, false, false);
+        auto path = state.coerceToString(pos, *i->value, context, false, false).toOwned();
 
         try {
-            state.realiseContext(context);
+            auto rewrites = state.realiseContext(context);
+            path = rewriteStrings(path, rewrites);
         } catch (InvalidPathError & e) {
             throw EvalError({
                 .msg = hintfmt("cannot find '%1%', since path '%2%' is not valid", path, e.path),
@@ -1473,12 +1504,13 @@ static void prim_findFile(EvalState & state, const Pos & pos, Value * * args, Va
             });
         }
 
+
         searchPath.emplace_back(prefix, path);
     }
 
-    string path = state.forceStringNoCtx(*args[1], pos);
+    auto path = state.forceStringNoCtx(*args[1], pos);
 
-    mkPath(v, state.checkSourcePath(state.findFile(searchPath, path, pos)).c_str());
+    v.mkPath(state.checkSourcePath(state.findFile(searchPath, path, pos)));
 }
 
 static RegisterPrimOp primop_findFile(RegisterPrimOp::Info {
@@ -1490,7 +1522,7 @@ static RegisterPrimOp primop_findFile(RegisterPrimOp::Info {
 /* Return the cryptographic hash of a file in base-16. */
 static void prim_hashFile(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    string type = state.forceStringNoCtx(*args[0], pos);
+    auto type = state.forceStringNoCtx(*args[0], pos);
     std::optional<HashType> ht = parseHashType(type);
     if (!ht)
         throw Error({
@@ -1498,15 +1530,9 @@ static void prim_hashFile(EvalState & state, const Pos & pos, Value * * args, Va
             .errPos = pos
         });
 
-    PathSet context;
-    Path path = state.coerceToPath(pos, *args[1], context);
-    try {
-        state.realiseContext(context);
-    } catch (InvalidPathError & e) {
-        throw EvalError("cannot read '%s' since path '%s' is not valid, at %s", path, e.path, pos);
-    }
+    auto path = realisePath(state, pos, *args[1]);
 
-    mkString(v, hashFile(*ht, state.checkSourcePath(state.toRealPath(path, context))).to_string(Base16, false));
+    v.mkString(hashFile(*ht, path).to_string(Base16, false));
 }
 
 static RegisterPrimOp primop_hashFile({
@@ -1523,32 +1549,23 @@ static RegisterPrimOp primop_hashFile({
 /* Read a directory (without . or ..) */
 static void prim_readDir(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    PathSet ctx;
-    Path path = state.coerceToPath(pos, *args[0], ctx);
-    try {
-        state.realiseContext(ctx);
-    } catch (InvalidPathError & e) {
-        throw EvalError({
-            .msg = hintfmt("cannot read '%1%', since path '%2%' is not valid", path, e.path),
-            .errPos = pos
-        });
-    }
+    auto path = realisePath(state, pos, *args[0]);
 
-    DirEntries entries = readDirectory(state.checkSourcePath(path));
-    state.mkAttrs(v, entries.size());
+    DirEntries entries = readDirectory(path);
+
+    auto attrs = state.buildBindings(entries.size());
 
     for (auto & ent : entries) {
-        Value * ent_val = state.allocAttr(v, state.symbols.create(ent.name));
         if (ent.type == DT_UNKNOWN)
             ent.type = getFileType(path + "/" + ent.name);
-        ent_val->mkString(
+        attrs.alloc(ent.name).mkString(
             ent.type == DT_REG ? "regular" :
             ent.type == DT_DIR ? "directory" :
             ent.type == DT_LNK ? "symlink" :
             "unknown");
     }
 
-    v.attrs->sort();
+    v.mkAttrs(attrs);
 }
 
 static RegisterPrimOp primop_readDir({
@@ -1583,8 +1600,8 @@ static void prim_toXML(EvalState & state, const Pos & pos, Value * * args, Value
 {
     std::ostringstream out;
     PathSet context;
-    printValueAsXML(state, true, false, *args[0], out, context);
-    mkString(v, out.str(), context);
+    printValueAsXML(state, true, false, *args[0], out, context, pos);
+    v.mkString(out.str(), context);
 }
 
 static RegisterPrimOp primop_toXML({
@@ -1691,8 +1708,8 @@ static void prim_toJSON(EvalState & state, const Pos & pos, Value * * args, Valu
 {
     std::ostringstream out;
     PathSet context;
-    printValueAsJSON(state, true, *args[0], out, context);
-    mkString(v, out.str(), context);
+    printValueAsJSON(state, true, *args[0], pos, out, context);
+    v.mkString(out.str(), context);
 }
 
 static RegisterPrimOp primop_toJSON({
@@ -1712,7 +1729,7 @@ static RegisterPrimOp primop_toJSON({
 /* Parse a JSON string to a value. */
 static void prim_fromJSON(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    string s = state.forceStringNoCtx(*args[0], pos);
+    auto s = state.forceStringNoCtx(*args[0], pos);
     try {
         parseJSON(state, s, v);
     } catch (JSONParseError &e) {
@@ -1741,8 +1758,8 @@ static RegisterPrimOp primop_fromJSON({
 static void prim_toFile(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     PathSet context;
-    string name = state.forceStringNoCtx(*args[0], pos);
-    string contents = state.forceString(*args[1], context, pos);
+    std::string name(state.forceStringNoCtx(*args[0], pos));
+    std::string contents(state.forceString(*args[1], context, pos));
 
     StorePathSet refs;
 
@@ -1766,7 +1783,7 @@ static void prim_toFile(EvalState & state, const Pos & pos, Value * * args, Valu
        result, since `storePath' itself has references to the paths
        used in args[1]. */
 
-    mkString(v, storePath, {storePath});
+    v.mkString(storePath, {storePath});
 }
 
 static RegisterPrimOp primop_toFile({
@@ -1850,7 +1867,7 @@ static RegisterPrimOp primop_toFile({
 static void addPath(
     EvalState & state,
     const Pos & pos,
-    const string & name,
+    const std::string & name,
     Path path,
     Value * filterFun,
     FileIngestionMethod method,
@@ -1861,15 +1878,19 @@ static void addPath(
     try {
         // FIXME: handle CA derivation outputs (where path needs to
         // be rewritten to the actual output).
-        state.realiseContext(context);
+        auto rewrites = state.realiseContext(context);
+        path = state.toRealPath(rewriteStrings(path, rewrites), context);
+
+        StorePathSet refs;
 
         if (state.store->isInStore(path)) {
-            auto [storePath, subPath] = state.store->toStorePath(path);
-            auto info = state.store->queryPathInfo(storePath);
-            if (!info->references.empty())
-                throw EvalError("store path '%s' is not allowed to have references",
-                    state.store->printStorePath(storePath));
-            path = state.store->toRealPath(storePath) + subPath;
+            try {
+                auto [storePath, subPath] = state.store->toStorePath(path);
+                // FIXME: we should scanForReferences on the path before adding it
+                refs = state.store->queryPathInfo(storePath)->references;
+                path = state.store->toRealPath(storePath) + subPath;
+            } catch (Error &) { // FIXME: should be InvalidPathError
+            }
         }
 
         path = evalSettings.pureEval && expectedHash
@@ -1882,20 +1903,18 @@ static void addPath(
             /* Call the filter function.  The first argument is the path,
                the second is a string indicating the type of the file. */
             Value arg1;
-            mkString(arg1, path);
-
-            Value fun2;
-            state.callFunction(*filterFun, arg1, fun2, noPos);
+            arg1.mkString(path);
 
             Value arg2;
-            mkString(arg2,
+            arg2.mkString(
                 S_ISREG(st.st_mode) ? "regular" :
                 S_ISDIR(st.st_mode) ? "directory" :
                 S_ISLNK(st.st_mode) ? "symlink" :
                 "unknown" /* not supported, will fail! */);
 
+            Value * args []{&arg1, &arg2};
             Value res;
-            state.callFunction(fun2, arg2, res, noPos);
+            state.callFunction(*filterFun, 2, args, res, pos);
 
             return state.forceBool(res, pos);
         }) : defaultPathFilter;
@@ -1910,20 +1929,15 @@ static void addPath(
                 {},
             });
 
-        Path dstPath;
         if (!expectedHash || !state.store->isValidPath(*expectedStorePath)) {
-            dstPath = state.store->printStorePath(settings.readOnlyMode
+            StorePath dstPath = settings.readOnlyMode
                 ? state.store->computeStorePathForPath(name, path, method, htSHA256, filter).first
-                : state.store->addToStore(name, path, method, htSHA256, filter, state.repair));
-            if (expectedHash && expectedStorePath != state.store->parseStorePath(dstPath))
+                : state.store->addToStore(name, path, method, htSHA256, filter, state.repair, refs);
+            if (expectedHash && expectedStorePath != dstPath)
                 throw Error("store path mismatch in (possibly filtered) path added from '%s'", path);
+            state.allowAndSetStorePathString(dstPath, v);
         } else
-            dstPath = state.store->printStorePath(*expectedStorePath);
-
-        mkString(v, dstPath, {dstPath});
-
-        state.allowPath(dstPath);
-
+            state.allowAndSetStorePathString(*expectedStorePath, v);
     } catch (Error & e) {
         e.addTrace(pos, "while adding path '%s'", path);
         throw;
@@ -2007,14 +2021,14 @@ static void prim_path(EvalState & state, const Pos & pos, Value * * args, Value
 {
     state.forceAttrs(*args[0], pos);
     Path path;
-    string name;
+    std::string name;
     Value * filterFun = nullptr;
     auto method = FileIngestionMethod::Recursive;
     std::optional<Hash> expectedHash;
     PathSet context;
 
     for (auto & attr : *args[0]->attrs) {
-        const string & n(attr.name);
+        auto & n(attr.name);
         if (n == "path")
             path = state.coerceToPath(*attr.pos, *attr.value, context);
         else if (attr.name == state.sName)
@@ -2094,7 +2108,7 @@ static void prim_attrNames(EvalState & state, const Pos & pos, Value * * args, V
 
     size_t n = 0;
     for (auto & i : *args[0]->attrs)
-        mkString(*(v.listElems()[n++] = state.allocValue()), i.name);
+        (v.listElems()[n++] = state.allocValue())->mkString(i.name);
 
     std::sort(v.listElems(), v.listElems() + n,
               [](Value * v1, Value * v2) { return strcmp(v1->string.s, v2->string.s) < 0; });
@@ -2124,7 +2138,10 @@ static void prim_attrValues(EvalState & state, const Pos & pos, Value * * args,
         v.listElems()[n++] = (Value *) &i;
 
     std::sort(v.listElems(), v.listElems() + n,
-        [](Value * v1, Value * v2) { return (string) ((Attr *) v1)->name < (string) ((Attr *) v2)->name; });
+        [](Value * v1, Value * v2) {
+            std::string_view s1 = ((Attr *) v1)->name, s2 = ((Attr *) v2)->name;
+            return s1 < s2;
+        });
 
     for (unsigned int i = 0; i < n; ++i)
         v.listElems()[i] = ((Attr *) v.listElems()[i])->value;
@@ -2143,13 +2160,12 @@ static RegisterPrimOp primop_attrValues({
 /* Dynamic version of the `.' operator. */
 void prim_getAttr(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    string attr = state.forceStringNoCtx(*args[0], pos);
+    auto attr = state.forceStringNoCtx(*args[0], pos);
     state.forceAttrs(*args[1], pos);
-    // !!! Should we create a symbol here or just do a lookup?
     Bindings::iterator i = getAttr(
         state,
         "getAttr",
-        attr,
+        state.symbols.create(attr),
         args[1]->attrs,
         pos
     );
@@ -2174,11 +2190,11 @@ static RegisterPrimOp primop_getAttr({
 /* Return position information of the specified attribute. */
 static void prim_unsafeGetAttrPos(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    string attr = state.forceStringNoCtx(*args[0], pos);
+    auto attr = state.forceStringNoCtx(*args[0], pos);
     state.forceAttrs(*args[1], pos);
     Bindings::iterator i = args[1]->attrs->find(state.symbols.create(attr));
     if (i == args[1]->attrs->end())
-        mkNull(v);
+        v.mkNull();
     else
         state.mkPos(v, i->pos);
 }
@@ -2192,9 +2208,9 @@ static RegisterPrimOp primop_unsafeGetAttrPos(RegisterPrimOp::Info {
 /* Dynamic version of the `?' operator. */
 static void prim_hasAttr(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    string attr = state.forceStringNoCtx(*args[0], pos);
+    auto attr = state.forceStringNoCtx(*args[0], pos);
     state.forceAttrs(*args[1], pos);
-    mkBool(v, args[1]->attrs->find(state.symbols.create(attr)) != args[1]->attrs->end());
+    v.mkBool(args[1]->attrs->find(state.symbols.create(attr)) != args[1]->attrs->end());
 }
 
 static RegisterPrimOp primop_hasAttr({
@@ -2212,7 +2228,7 @@ static RegisterPrimOp primop_hasAttr({
 static void prim_isAttrs(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceValue(*args[0], pos);
-    mkBool(v, args[0]->type() == nAttrs);
+    v.mkBool(args[0]->type() == nAttrs);
 }
 
 static RegisterPrimOp primop_isAttrs({
@@ -2229,21 +2245,26 @@ static void prim_removeAttrs(EvalState & state, const Pos & pos, Value * * args,
     state.forceAttrs(*args[0], pos);
     state.forceList(*args[1], pos);
 
-    /* Get the attribute names to be removed. */
-    std::set<Symbol> names;
-    for (unsigned int i = 0; i < args[1]->listSize(); ++i) {
-        state.forceStringNoCtx(*args[1]->listElems()[i], pos);
-        names.insert(state.symbols.create(args[1]->listElems()[i]->string.s));
+    /* Get the attribute names to be removed.
+       We keep them as Attrs instead of Symbols so std::set_difference
+       can be used to remove them from attrs[0]. */
+    boost::container::small_vector<Attr, 64> names;
+    names.reserve(args[1]->listSize());
+    for (auto elem : args[1]->listItems()) {
+        state.forceStringNoCtx(*elem, pos);
+        names.emplace_back(state.symbols.create(elem->string.s), nullptr);
     }
+    std::sort(names.begin(), names.end());
 
     /* Copy all attributes not in that set.  Note that we don't need
        to sort v.attrs because it's a subset of an already sorted
        vector. */
-    state.mkAttrs(v, args[0]->attrs->size());
-    for (auto & i : *args[0]->attrs) {
-        if (names.find(i.name) == names.end())
-            v.attrs->push_back(i);
-    }
+    auto attrs = state.buildBindings(args[0]->attrs->size());
+    std::set_difference(
+        args[0]->attrs->begin(), args[0]->attrs->end(),
+        names.begin(), names.end(),
+        std::back_inserter(attrs));
+    v.mkAttrs(attrs.alreadySorted());
 }
 
 static RegisterPrimOp primop_removeAttrs({
@@ -2265,29 +2286,28 @@ static RegisterPrimOp primop_removeAttrs({
 /* Builds a set from a list specifying (name, value) pairs.  To be
    precise, a list [{name = "name1"; value = value1;} ... {name =
    "nameN"; value = valueN;}] is transformed to {name1 = value1;
-   ... nameN = valueN;}.  In case of duplicate occurences of the same
+   ... nameN = valueN;}.  In case of duplicate occurrences of the same
    name, the first takes precedence. */
 static void prim_listToAttrs(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceList(*args[0], pos);
 
-    state.mkAttrs(v, args[0]->listSize());
+    auto attrs = state.buildBindings(args[0]->listSize());
 
     std::set<Symbol> seen;
 
-    for (unsigned int i = 0; i < args[0]->listSize(); ++i) {
-        Value & v2(*args[0]->listElems()[i]);
-        state.forceAttrs(v2, pos);
+    for (auto v2 : args[0]->listItems()) {
+        state.forceAttrs(*v2, pos);
 
         Bindings::iterator j = getAttr(
             state,
             "listToAttrs",
             state.sName,
-            v2.attrs,
+            v2->attrs,
             pos
         );
 
-        string name = state.forceStringNoCtx(*j->value, *j->pos);
+        auto name = state.forceStringNoCtx(*j->value, *j->pos);
 
         Symbol sym = state.symbols.create(name);
         if (seen.insert(sym).second) {
@@ -2295,14 +2315,14 @@ static void prim_listToAttrs(EvalState & state, const Pos & pos, Value * * args,
                 state,
                 "listToAttrs",
                 state.sValue,
-                v2.attrs,
+                v2->attrs,
                 pos
             );
-            v.attrs->push_back(Attr(sym, j2->value, j2->pos));
+            attrs.insert(sym, j2->value, j2->pos);
         }
     }
 
-    v.attrs->sort();
+    v.mkAttrs(attrs);
 }
 
 static RegisterPrimOp primop_listToAttrs({
@@ -2335,13 +2355,15 @@ static void prim_intersectAttrs(EvalState & state, const Pos & pos, Value * * ar
     state.forceAttrs(*args[0], pos);
     state.forceAttrs(*args[1], pos);
 
-    state.mkAttrs(v, std::min(args[0]->attrs->size(), args[1]->attrs->size()));
+    auto attrs = state.buildBindings(std::min(args[0]->attrs->size(), args[1]->attrs->size()));
 
     for (auto & i : *args[0]->attrs) {
         Bindings::iterator j = args[1]->attrs->find(i.name);
         if (j != args[1]->attrs->end())
-            v.attrs->push_back(*j);
+            attrs.insert(*j);
     }
+
+    v.mkAttrs(attrs.alreadySorted());
 }
 
 static RegisterPrimOp primop_intersectAttrs({
@@ -2362,11 +2384,10 @@ static void prim_catAttrs(EvalState & state, const Pos & pos, Value * * args, Va
     Value * res[args[1]->listSize()];
     unsigned int found = 0;
 
-    for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
-        Value & v2(*args[1]->listElems()[n]);
-        state.forceAttrs(v2, pos);
-        Bindings::iterator i = v2.attrs->find(attrName);
-        if (i != v2.attrs->end())
+    for (auto v2 : args[1]->listItems()) {
+        state.forceAttrs(*v2, pos);
+        Bindings::iterator i = v2->attrs->find(attrName);
+        if (i != v2->attrs->end())
             res[found++] = i->value;
     }
 
@@ -2396,7 +2417,7 @@ static void prim_functionArgs(EvalState & state, const Pos & pos, Value * * args
 {
     state.forceValue(*args[0], pos);
     if (args[0]->isPrimOpApp() || args[0]->isPrimOp()) {
-        state.mkAttrs(v, 0);
+        v.mkAttrs(&state.emptyBindings);
         return;
     }
     if (!args[0]->isLambda())
@@ -2406,18 +2427,15 @@ static void prim_functionArgs(EvalState & state, const Pos & pos, Value * * args
         });
 
     if (!args[0]->lambda.fun->hasFormals()) {
-        state.mkAttrs(v, 0);
+        v.mkAttrs(&state.emptyBindings);
         return;
     }
 
-    state.mkAttrs(v, args[0]->lambda.fun->formals->formals.size());
-    for (auto & i : args[0]->lambda.fun->formals->formals) {
+    auto attrs = state.buildBindings(args[0]->lambda.fun->formals->formals.size());
+    for (auto & i : args[0]->lambda.fun->formals->formals)
         // !!! should optimise booleans (allocate only once)
-        Value * value = state.allocValue();
-        v.attrs->push_back(Attr(i.name, value, ptr(&i.pos)));
-        mkBool(*value, i.def);
-    }
-    v.attrs->sort();
+        attrs.alloc(i.name, ptr(&i.pos)).mkBool(i.def);
+    v.mkAttrs(attrs);
 }
 
 static RegisterPrimOp primop_functionArgs({
@@ -2442,15 +2460,17 @@ static void prim_mapAttrs(EvalState & state, const Pos & pos, Value * * args, Va
 {
     state.forceAttrs(*args[1], pos);
 
-    state.mkAttrs(v, args[1]->attrs->size());
+    auto attrs = state.buildBindings(args[1]->attrs->size());
 
     for (auto & i : *args[1]->attrs) {
         Value * vName = state.allocValue();
         Value * vFun2 = state.allocValue();
-        mkString(*vName, i.name);
-        mkApp(*vFun2, *args[0], *vName);
-        mkApp(*state.allocAttr(v, i.name), *vFun2, *i.value);
+        vName->mkString(i.name);
+        vFun2->mkApp(args[0], vName);
+        attrs.alloc(i.name).mkApp(vFun2, i.value);
     }
+
+    v.mkAttrs(attrs.alreadySorted());
 }
 
 static RegisterPrimOp primop_mapAttrs({
@@ -2468,6 +2488,91 @@ static RegisterPrimOp primop_mapAttrs({
     .fun = prim_mapAttrs,
 });
 
+static void prim_zipAttrsWith(EvalState & state, const Pos & pos, Value * * args, Value & v)
+{
+    // we will first count how many values are present for each given key.
+    // we then allocate a single attrset and pre-populate it with lists of
+    // appropriate sizes, stash the pointers to the list elements of each,
+    // and populate the lists. after that we replace the list in the every
+    // attribute with the merge function application. this way we need not
+    // use (slightly slower) temporary storage the GC does not know about.
+
+    std::map<Symbol, std::pair<size_t, Value * *>> attrsSeen;
+
+    state.forceFunction(*args[0], pos);
+    state.forceList(*args[1], pos);
+    const auto listSize = args[1]->listSize();
+    const auto listElems = args[1]->listElems();
+
+    for (unsigned int n = 0; n < listSize; ++n) {
+        Value * vElem = listElems[n];
+        try {
+            state.forceAttrs(*vElem, noPos);
+            for (auto & attr : *vElem->attrs)
+                attrsSeen[attr.name].first++;
+        } catch (TypeError & e) {
+            e.addTrace(pos, hintfmt("while invoking '%s'", "zipAttrsWith"));
+            throw;
+        }
+    }
+
+    auto attrs = state.buildBindings(attrsSeen.size());
+    for (auto & [sym, elem] : attrsSeen) {
+        auto & list = attrs.alloc(sym);
+        state.mkList(list, elem.first);
+        elem.second = list.listElems();
+    }
+    v.mkAttrs(attrs.alreadySorted());
+
+    for (unsigned int n = 0; n < listSize; ++n) {
+        Value * vElem = listElems[n];
+        for (auto & attr : *vElem->attrs)
+            *attrsSeen[attr.name].second++ = attr.value;
+    }
+
+    for (auto & attr : *v.attrs) {
+        auto name = state.allocValue();
+        name->mkString(attr.name);
+        auto call1 = state.allocValue();
+        call1->mkApp(args[0], name);
+        auto call2 = state.allocValue();
+        call2->mkApp(call1, attr.value);
+        attr.value = call2;
+    }
+}
+
+static RegisterPrimOp primop_zipAttrsWith({
+    .name = "__zipAttrsWith",
+    .args = {"f", "list"},
+    .doc = R"(
+      Transpose a list of attribute sets into an attribute set of lists,
+      then apply `mapAttrs`.
+
+      `f` receives two arguments: the attribute name and a non-empty
+      list of all values encountered for that attribute name.
+
+      The result is an attribute set where the attribute names are the
+      union of the attribute names in each element of `list`. The attribute
+      values are the return values of `f`.
+
+      ```nix
+      builtins.zipAttrsWith
+        (name: values: { inherit name values; })
+        [ { a = "x"; } { a = "y"; b = "z"; } ]
+      ```
+
+      evaluates to
+
+      ```
+      {
+        a = { name = "a"; values = [ "x" "y" ]; };
+        b = { name = "b"; values = [ "z" ]; };
+      }
+      ```
+    )",
+    .fun = prim_zipAttrsWith,
+});
+
 
 /*************************************************************
  * Lists
@@ -2478,7 +2583,7 @@ static RegisterPrimOp primop_mapAttrs({
 static void prim_isList(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceValue(*args[0], pos);
-    mkBool(v, args[0]->type() == nList);
+    v.mkBool(args[0]->type() == nList);
 }
 
 static RegisterPrimOp primop_isList({
@@ -2576,8 +2681,8 @@ static void prim_map(EvalState & state, const Pos & pos, Value * * args, Value &
     state.mkList(v, args[1]->listSize());
 
     for (unsigned int n = 0; n < v.listSize(); ++n)
-        mkApp(*(v.listElems()[n] = state.allocValue()),
-            *args[0], *args[1]->listElems()[n]);
+        (v.listElems()[n] = state.allocValue())->mkApp(
+            args[0], args[1]->listElems()[n]);
 }
 
 static RegisterPrimOp primop_map({
@@ -2641,12 +2746,12 @@ static void prim_elem(EvalState & state, const Pos & pos, Value * * args, Value
 {
     bool res = false;
     state.forceList(*args[1], pos);
-    for (unsigned int n = 0; n < args[1]->listSize(); ++n)
-        if (state.eqValues(*args[0], *args[1]->listElems()[n])) {
+    for (auto elem : args[1]->listItems())
+        if (state.eqValues(*args[0], *elem)) {
             res = true;
             break;
         }
-    mkBool(v, res);
+    v.mkBool(res);
 }
 
 static RegisterPrimOp primop_elem({
@@ -2679,7 +2784,7 @@ static RegisterPrimOp primop_concatLists({
 static void prim_length(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceList(*args[0], pos);
-    mkInt(v, args[0]->listSize());
+    v.mkInt(args[0]->listSize());
 }
 
 static RegisterPrimOp primop_length({
@@ -2701,11 +2806,10 @@ static void prim_foldlStrict(EvalState & state, const Pos & pos, Value * * args,
     if (args[2]->listSize()) {
         Value * vCur = args[1];
 
-        for (unsigned int n = 0; n < args[2]->listSize(); ++n) {
-            Value vTmp;
-            state.callFunction(*args[0], *vCur, vTmp, pos);
+        for (auto [n, elem] : enumerate(args[2]->listItems())) {
+            Value * vs []{vCur, elem};
             vCur = n == args[2]->listSize() - 1 ? &v : state.allocValue();
-            state.callFunction(vTmp, *args[2]->listElems()[n], *vCur, pos);
+            state.callFunction(*args[0], 2, vs, *vCur, pos);
         }
         state.forceValue(v, pos);
     } else {
@@ -2719,9 +2823,9 @@ static RegisterPrimOp primop_foldlStrict({
     .args = {"op", "nul", "list"},
     .doc = R"(
       Reduce a list by applying a binary operator, from left to right,
-      e.g. `foldl’ op nul [x0 x1 x2 ...] = op (op (op nul x0) x1) x2)
+      e.g. `foldl' op nul [x0 x1 x2 ...] = op (op (op nul x0) x1) x2)
       ...`. The operator is applied strictly, i.e., its arguments are
-      evaluated first. For example, `foldl’ (x: y: x + y) 0 [1 2 3]`
+      evaluated first. For example, `foldl' (x: y: x + y) 0 [1 2 3]`
       evaluates to 6.
     )",
     .fun = prim_foldlStrict,
@@ -2733,16 +2837,16 @@ static void anyOrAll(bool any, EvalState & state, const Pos & pos, Value * * arg
     state.forceList(*args[1], pos);
 
     Value vTmp;
-    for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
-        state.callFunction(*args[0], *args[1]->listElems()[n], vTmp, pos);
+    for (auto elem : args[1]->listItems()) {
+        state.callFunction(*args[0], *elem, vTmp, pos);
         bool res = state.forceBool(vTmp, pos);
         if (res == any) {
-            mkBool(v, any);
+            v.mkBool(any);
             return;
         }
     }
 
-    mkBool(v, !any);
+    v.mkBool(!any);
 }
 
 
@@ -2789,9 +2893,9 @@ static void prim_genList(EvalState & state, const Pos & pos, Value * * args, Val
     state.mkList(v, len);
 
     for (unsigned int n = 0; n < (unsigned int) len; ++n) {
-        Value * arg = state.allocValue();
-        mkInt(*arg, n);
-        mkApp(*(v.listElems()[n] = state.allocValue()), *args[0], *arg);
+        auto arg = state.allocValue();
+        arg->mkInt(n);
+        (v.listElems()[n] = state.allocValue())->mkApp(args[0], arg);
     }
 }
 
@@ -2826,17 +2930,16 @@ static void prim_sort(EvalState & state, const Pos & pos, Value * * args, Value
         v.listElems()[n] = args[1]->listElems()[n];
     }
 
-
     auto comparator = [&](Value * a, Value * b) {
         /* Optimization: if the comparator is lessThan, bypass
            callFunction. */
         if (args[0]->isPrimOp() && args[0]->primOp->fun == prim_lessThan)
-            return CompareValues()(a, b);
+            return CompareValues(state)(a, b);
 
-        Value vTmp1, vTmp2;
-        state.callFunction(*args[0], *a, vTmp1, pos);
-        state.callFunction(vTmp1, *b, vTmp2, pos);
-        return state.forceBool(vTmp2, pos);
+        Value * vs[] = {a, b};
+        Value vBool;
+        state.callFunction(*args[0], 2, vs, vBool, pos);
+        return state.forceBool(vBool, pos);
     };
 
     /* FIXME: std::sort can segfault if the comparator is not a strict
@@ -2886,21 +2989,21 @@ static void prim_partition(EvalState & state, const Pos & pos, Value * * args, V
             wrong.push_back(vElem);
     }
 
-    state.mkAttrs(v, 2);
+    auto attrs = state.buildBindings(2);
 
-    Value * vRight = state.allocAttr(v, state.sRight);
+    auto & vRight = attrs.alloc(state.sRight);
     auto rsize = right.size();
-    state.mkList(*vRight, rsize);
+    state.mkList(vRight, rsize);
     if (rsize)
-        memcpy(vRight->listElems(), right.data(), sizeof(Value *) * rsize);
+        memcpy(vRight.listElems(), right.data(), sizeof(Value *) * rsize);
 
-    Value * vWrong = state.allocAttr(v, state.sWrong);
+    auto & vWrong = attrs.alloc(state.sWrong);
     auto wsize = wrong.size();
-    state.mkList(*vWrong, wsize);
+    state.mkList(vWrong, wsize);
     if (wsize)
-        memcpy(vWrong->listElems(), wrong.data(), sizeof(Value *) * wsize);
+        memcpy(vWrong.listElems(), wrong.data(), sizeof(Value *) * wsize);
 
-    v.attrs->sort();
+    v.mkAttrs(attrs);
 }
 
 static RegisterPrimOp primop_partition({
@@ -2926,6 +3029,58 @@ static RegisterPrimOp primop_partition({
     .fun = prim_partition,
 });
 
+static void prim_groupBy(EvalState & state, const Pos & pos, Value * * args, Value & v)
+{
+    state.forceFunction(*args[0], pos);
+    state.forceList(*args[1], pos);
+
+    ValueVectorMap attrs;
+
+    for (auto vElem : args[1]->listItems()) {
+        Value res;
+        state.callFunction(*args[0], *vElem, res, pos);
+        auto name = state.forceStringNoCtx(res, pos);
+        Symbol sym = state.symbols.create(name);
+        auto vector = attrs.try_emplace(sym, ValueVector()).first;
+        vector->second.push_back(vElem);
+    }
+
+    auto attrs2 = state.buildBindings(attrs.size());
+
+    for (auto & i : attrs) {
+        auto & list = attrs2.alloc(i.first);
+        auto size = i.second.size();
+        state.mkList(list, size);
+        memcpy(list.listElems(), i.second.data(), sizeof(Value *) * size);
+    }
+
+    v.mkAttrs(attrs2.alreadySorted());
+}
+
+static RegisterPrimOp primop_groupBy({
+    .name = "__groupBy",
+    .args = {"f", "list"},
+    .doc = R"(
+      Groups elements of *list* together by the string returned from the
+      function *f* called on each element. It returns an attribute set
+      where each attribute value contains the elements of *list* that are
+      mapped to the same corresponding attribute name returned by *f*.
+
+      For example,
+
+      ```nix
+      builtins.groupBy (builtins.substring 0 1) ["foo" "bar" "baz"]
+      ```
+
+      evaluates to
+
+      ```nix
+      { b = [ "bar" "baz" ]; f = [ "foo" ]; }
+      ```
+    )",
+    .fun = prim_groupBy,
+});
+
 static void prim_concatMap(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceFunction(*args[0], pos);
@@ -2978,9 +3133,9 @@ static void prim_add(EvalState & state, const Pos & pos, Value * * args, Value &
     state.forceValue(*args[0], pos);
     state.forceValue(*args[1], pos);
     if (args[0]->type() == nFloat || args[1]->type() == nFloat)
-        mkFloat(v, state.forceFloat(*args[0], pos) + state.forceFloat(*args[1], pos));
+        v.mkFloat(state.forceFloat(*args[0], pos) + state.forceFloat(*args[1], pos));
     else
-        mkInt(v, state.forceInt(*args[0], pos) + state.forceInt(*args[1], pos));
+        v.mkInt(state.forceInt(*args[0], pos) + state.forceInt(*args[1], pos));
 }
 
 static RegisterPrimOp primop_add({
@@ -2997,9 +3152,9 @@ static void prim_sub(EvalState & state, const Pos & pos, Value * * args, Value &
     state.forceValue(*args[0], pos);
     state.forceValue(*args[1], pos);
     if (args[0]->type() == nFloat || args[1]->type() == nFloat)
-        mkFloat(v, state.forceFloat(*args[0], pos) - state.forceFloat(*args[1], pos));
+        v.mkFloat(state.forceFloat(*args[0], pos) - state.forceFloat(*args[1], pos));
     else
-        mkInt(v, state.forceInt(*args[0], pos) - state.forceInt(*args[1], pos));
+        v.mkInt(state.forceInt(*args[0], pos) - state.forceInt(*args[1], pos));
 }
 
 static RegisterPrimOp primop_sub({
@@ -3016,9 +3171,9 @@ static void prim_mul(EvalState & state, const Pos & pos, Value * * args, Value &
     state.forceValue(*args[0], pos);
     state.forceValue(*args[1], pos);
     if (args[0]->type() == nFloat || args[1]->type() == nFloat)
-        mkFloat(v, state.forceFloat(*args[0], pos) * state.forceFloat(*args[1], pos));
+        v.mkFloat(state.forceFloat(*args[0], pos) * state.forceFloat(*args[1], pos));
     else
-        mkInt(v, state.forceInt(*args[0], pos) * state.forceInt(*args[1], pos));
+        v.mkInt(state.forceInt(*args[0], pos) * state.forceInt(*args[1], pos));
 }
 
 static RegisterPrimOp primop_mul({
@@ -3043,7 +3198,7 @@ static void prim_div(EvalState & state, const Pos & pos, Value * * args, Value &
         });
 
     if (args[0]->type() == nFloat || args[1]->type() == nFloat) {
-        mkFloat(v, state.forceFloat(*args[0], pos) / state.forceFloat(*args[1], pos));
+        v.mkFloat(state.forceFloat(*args[0], pos) / state.forceFloat(*args[1], pos));
     } else {
         NixInt i1 = state.forceInt(*args[0], pos);
         NixInt i2 = state.forceInt(*args[1], pos);
@@ -3054,7 +3209,7 @@ static void prim_div(EvalState & state, const Pos & pos, Value * * args, Value &
                 .errPos = pos
             });
 
-        mkInt(v, i1 / i2);
+        v.mkInt(i1 / i2);
     }
 }
 
@@ -3069,7 +3224,7 @@ static RegisterPrimOp primop_div({
 
 static void prim_bitAnd(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    mkInt(v, state.forceInt(*args[0], pos) & state.forceInt(*args[1], pos));
+    v.mkInt(state.forceInt(*args[0], pos) & state.forceInt(*args[1], pos));
 }
 
 static RegisterPrimOp primop_bitAnd({
@@ -3083,7 +3238,7 @@ static RegisterPrimOp primop_bitAnd({
 
 static void prim_bitOr(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    mkInt(v, state.forceInt(*args[0], pos) | state.forceInt(*args[1], pos));
+    v.mkInt(state.forceInt(*args[0], pos) | state.forceInt(*args[1], pos));
 }
 
 static RegisterPrimOp primop_bitOr({
@@ -3097,7 +3252,7 @@ static RegisterPrimOp primop_bitOr({
 
 static void prim_bitXor(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    mkInt(v, state.forceInt(*args[0], pos) ^ state.forceInt(*args[1], pos));
+    v.mkInt(state.forceInt(*args[0], pos) ^ state.forceInt(*args[1], pos));
 }
 
 static RegisterPrimOp primop_bitXor({
@@ -3113,8 +3268,8 @@ static void prim_lessThan(EvalState & state, const Pos & pos, Value * * args, Va
 {
     state.forceValue(*args[0], pos);
     state.forceValue(*args[1], pos);
-    CompareValues comp;
-    mkBool(v, comp(args[0], args[1]));
+    CompareValues comp{state};
+    v.mkBool(comp(args[0], args[1]));
 }
 
 static RegisterPrimOp primop_lessThan({
@@ -3140,8 +3295,8 @@ static RegisterPrimOp primop_lessThan({
 static void prim_toString(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     PathSet context;
-    string s = state.coerceToString(pos, *args[0], context, true, false);
-    mkString(v, s, context);
+    auto s = state.coerceToString(pos, *args[0], context, true, false);
+    v.mkString(*s, context);
 }
 
 static RegisterPrimOp primop_toString({
@@ -3177,7 +3332,7 @@ static void prim_substring(EvalState & state, const Pos & pos, Value * * args, V
     int start = state.forceInt(*args[0], pos);
     int len = state.forceInt(*args[1], pos);
     PathSet context;
-    string s = state.coerceToString(pos, *args[2], context);
+    auto s = state.coerceToString(pos, *args[2], context);
 
     if (start < 0)
         throw EvalError({
@@ -3185,7 +3340,7 @@ static void prim_substring(EvalState & state, const Pos & pos, Value * * args, V
             .errPos = pos
         });
 
-    mkString(v, (unsigned int) start >= s.size() ? "" : string(s, start, len), context);
+    v.mkString((unsigned int) start >= s->size() ? "" : s->substr(start, len), context);
 }
 
 static RegisterPrimOp primop_substring({
@@ -3211,8 +3366,8 @@ static RegisterPrimOp primop_substring({
 static void prim_stringLength(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     PathSet context;
-    string s = state.coerceToString(pos, *args[0], context);
-    mkInt(v, s.size());
+    auto s = state.coerceToString(pos, *args[0], context);
+    v.mkInt(s->size());
 }
 
 static RegisterPrimOp primop_stringLength({
@@ -3228,7 +3383,7 @@ static RegisterPrimOp primop_stringLength({
 /* Return the cryptographic hash of a string in base-16. */
 static void prim_hashString(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    string type = state.forceStringNoCtx(*args[0], pos);
+    auto type = state.forceStringNoCtx(*args[0], pos);
     std::optional<HashType> ht = parseHashType(type);
     if (!ht)
         throw Error({
@@ -3237,9 +3392,9 @@ static void prim_hashString(EvalState & state, const Pos & pos, Value * * args,
         });
 
     PathSet context; // discarded
-    string s = state.forceString(*args[1], context, pos);
+    auto s = state.forceString(*args[1], context, pos);
 
-    mkString(v, hashString(*ht, s).to_string(Base16, false));
+    v.mkString(hashString(*ht, s).to_string(Base16, false));
 }
 
 static RegisterPrimOp primop_hashString({
@@ -3255,7 +3410,18 @@ static RegisterPrimOp primop_hashString({
 
 struct RegexCache
 {
-    std::unordered_map<std::string, std::regex> cache;
+    // TODO use C++20 transparent comparison when available
+    std::unordered_map<std::string_view, std::regex> cache;
+    std::list<std::string> keys;
+
+    std::regex get(std::string_view re)
+    {
+        auto it = cache.find(re);
+        if (it != cache.end())
+            return it->second;
+        keys.emplace_back(re);
+        return cache.emplace(keys.back(), std::regex(keys.back(), std::regex::extended)).first->second;
+    }
 };
 
 std::shared_ptr<RegexCache> makeRegexCache()
@@ -3269,16 +3435,14 @@ void prim_match(EvalState & state, const Pos & pos, Value * * args, Value & v)
 
     try {
 
-        auto regex = state.regexCache->cache.find(re);
-        if (regex == state.regexCache->cache.end())
-            regex = state.regexCache->cache.emplace(re, std::regex(re, std::regex::extended)).first;
+        auto regex = state.regexCache->get(re);
 
         PathSet context;
-        const std::string str = state.forceString(*args[1], context, pos);
+        const auto str = state.forceString(*args[1], context, pos);
 
-        std::smatch match;
-        if (!std::regex_match(str, match, regex->second)) {
-            mkNull(v);
+        std::cmatch match;
+        if (!std::regex_match(str.begin(), str.end(), match, regex)) {
+            v.mkNull();
             return;
         }
 
@@ -3287,9 +3451,9 @@ void prim_match(EvalState & state, const Pos & pos, Value * * args, Value & v)
         state.mkList(v, len);
         for (size_t i = 0; i < len; ++i) {
             if (!match[i+1].matched)
-                mkNull(*(v.listElems()[i] = state.allocValue()));
+                (v.listElems()[i] = state.allocValue())->mkNull();
             else
-                mkString(*(v.listElems()[i] = state.allocValue()), match[i + 1].str().c_str());
+                (v.listElems()[i] = state.allocValue())->mkString(match[i + 1].str());
         }
 
     } catch (std::regex_error &e) {
@@ -3346,58 +3510,55 @@ static RegisterPrimOp primop_match({
 
 /* Split a string with a regular expression, and return a list of the
    non-matching parts interleaved by the lists of the matching groups. */
-static void prim_split(EvalState & state, const Pos & pos, Value * * args, Value & v)
+void prim_split(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     auto re = state.forceStringNoCtx(*args[0], pos);
 
     try {
 
-        std::regex regex(re, std::regex::extended);
+        auto regex = state.regexCache->get(re);
 
         PathSet context;
-        const std::string str = state.forceString(*args[1], context, pos);
+        const auto str = state.forceString(*args[1], context, pos);
 
-        auto begin = std::sregex_iterator(str.begin(), str.end(), regex);
-        auto end = std::sregex_iterator();
+        auto begin = std::cregex_iterator(str.begin(), str.end(), regex);
+        auto end = std::cregex_iterator();
 
         // Any matches results are surrounded by non-matching results.
         const size_t len = std::distance(begin, end);
         state.mkList(v, 2 * len + 1);
         size_t idx = 0;
-        Value * elem;
 
         if (len == 0) {
             v.listElems()[idx++] = args[1];
             return;
         }
 
-        for (std::sregex_iterator i = begin; i != end; ++i) {
+        for (auto i = begin; i != end; ++i) {
             assert(idx <= 2 * len + 1 - 3);
-            std::smatch match = *i;
+            auto match = *i;
 
             // Add a string for non-matched characters.
-            elem = v.listElems()[idx++] = state.allocValue();
-            mkString(*elem, match.prefix().str().c_str());
+            (v.listElems()[idx++] = state.allocValue())->mkString(match.prefix().str());
 
             // Add a list for matched substrings.
             const size_t slen = match.size() - 1;
-            elem = v.listElems()[idx++] = state.allocValue();
+            auto elem = v.listElems()[idx++] = state.allocValue();
 
             // Start at 1, beacause the first match is the whole string.
             state.mkList(*elem, slen);
             for (size_t si = 0; si < slen; ++si) {
                 if (!match[si + 1].matched)
-                    mkNull(*(elem->listElems()[si] = state.allocValue()));
+                    (elem->listElems()[si] = state.allocValue())->mkNull();
                 else
-                    mkString(*(elem->listElems()[si] = state.allocValue()), match[si + 1].str().c_str());
+                    (elem->listElems()[si] = state.allocValue())->mkString(match[si + 1].str());
             }
 
             // Add a string for non-matched suffix characters.
-            if (idx == 2 * len) {
-                elem = v.listElems()[idx++] = state.allocValue();
-                mkString(*elem, match.suffix().str().c_str());
-            }
+            if (idx == 2 * len)
+                (v.listElems()[idx++] = state.allocValue())->mkString(match.suffix().str());
         }
+
         assert(idx == 2 * len + 1);
 
     } catch (std::regex_error &e) {
@@ -3460,16 +3621,16 @@ static void prim_concatStringsSep(EvalState & state, const Pos & pos, Value * *
     auto sep = state.forceString(*args[0], context, pos);
     state.forceList(*args[1], pos);
 
-    string res;
+    std::string res;
     res.reserve((args[1]->listSize() + 32) * sep.size());
     bool first = true;
 
-    for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
+    for (auto elem : args[1]->listItems()) {
         if (first) first = false; else res += sep;
-        res += state.coerceToString(pos, *args[1]->listElems()[n], context);
+        res += *state.coerceToString(pos, *elem, context);
     }
 
-    mkString(v, res, context);
+    v.mkString(res, context);
 }
 
 static RegisterPrimOp primop_concatStringsSep({
@@ -3493,23 +3654,23 @@ static void prim_replaceStrings(EvalState & state, const Pos & pos, Value * * ar
             .errPos = pos
         });
 
-    vector<string> from;
+    std::vector<std::string> from;
     from.reserve(args[0]->listSize());
-    for (unsigned int n = 0; n < args[0]->listSize(); ++n)
-        from.push_back(state.forceString(*args[0]->listElems()[n], pos));
+    for (auto elem : args[0]->listItems())
+        from.emplace_back(state.forceString(*elem, pos));
 
-    vector<std::pair<string, PathSet>> to;
+    std::vector<std::pair<std::string, PathSet>> to;
     to.reserve(args[1]->listSize());
-    for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
+    for (auto elem : args[1]->listItems()) {
         PathSet ctx;
-        auto s = state.forceString(*args[1]->listElems()[n], ctx, pos);
-        to.push_back(std::make_pair(std::move(s), std::move(ctx)));
+        auto s = state.forceString(*elem, ctx, pos);
+        to.emplace_back(s, std::move(ctx));
     }
 
     PathSet context;
     auto s = state.forceString(*args[2], context, pos);
 
-    string res;
+    std::string res;
     // Loops one past last character to handle the case where 'from' contains an empty string.
     for (size_t p = 0; p <= s.size(); ) {
         bool found = false;
@@ -3538,7 +3699,7 @@ static void prim_replaceStrings(EvalState & state, const Pos & pos, Value * * ar
         }
     }
 
-    mkString(v, res, context);
+    v.mkString(res, context);
 }
 
 static RegisterPrimOp primop_replaceStrings({
@@ -3565,12 +3726,12 @@ static RegisterPrimOp primop_replaceStrings({
 
 static void prim_parseDrvName(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    string name = state.forceStringNoCtx(*args[0], pos);
+    auto name = state.forceStringNoCtx(*args[0], pos);
     DrvName parsed(name);
-    state.mkAttrs(v, 2);
-    mkString(*state.allocAttr(v, state.sName), parsed.name);
-    mkString(*state.allocAttr(v, state.symbols.create("version")), parsed.version);
-    v.attrs->sort();
+    auto attrs = state.buildBindings(2);
+    attrs.alloc(state.sName).mkString(parsed.name);
+    attrs.alloc("version").mkString(parsed.version);
+    v.mkAttrs(attrs);
 }
 
 static RegisterPrimOp primop_parseDrvName({
@@ -3589,9 +3750,9 @@ static RegisterPrimOp primop_parseDrvName({
 
 static void prim_compareVersions(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    string version1 = state.forceStringNoCtx(*args[0], pos);
-    string version2 = state.forceStringNoCtx(*args[1], pos);
-    mkInt(v, compareVersions(version1, version2));
+    auto version1 = state.forceStringNoCtx(*args[0], pos);
+    auto version2 = state.forceStringNoCtx(*args[1], pos);
+    v.mkInt(compareVersions(version1, version2));
 }
 
 static RegisterPrimOp primop_compareVersions({
@@ -3609,21 +3770,18 @@ static RegisterPrimOp primop_compareVersions({
 
 static void prim_splitVersion(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    string version = state.forceStringNoCtx(*args[0], pos);
+    auto version = state.forceStringNoCtx(*args[0], pos);
     auto iter = version.cbegin();
     Strings components;
     while (iter != version.cend()) {
         auto component = nextComponent(iter, version.cend());
         if (component.empty())
             break;
-        components.emplace_back(std::move(component));
+        components.emplace_back(component);
     }
     state.mkList(v, components.size());
-    unsigned int n = 0;
-    for (auto & component : components) {
-        auto listElem = v.listElems()[n++] = state.allocValue();
-        mkString(*listElem, std::move(component));
-    }
+    for (const auto & [n, component] : enumerate(components))
+        (v.listElems()[n] = state.allocValue())->mkString(std::move(component));
 }
 
 static RegisterPrimOp primop_splitVersion({
@@ -3673,37 +3831,37 @@ void EvalState::createBaseEnv()
     Value v;
 
     /* `builtins' must be first! */
-    mkAttrs(v, 128);
+    v.mkAttrs(buildBindings(128).finish());
     addConstant("builtins", v);
 
-    mkBool(v, true);
+    v.mkBool(true);
     addConstant("true", v);
 
-    mkBool(v, false);
+    v.mkBool(false);
     addConstant("false", v);
 
-    mkNull(v);
+    v.mkNull();
     addConstant("null", v);
 
     if (!evalSettings.pureEval) {
-        mkInt(v, time(0));
+        v.mkInt(time(0));
         addConstant("__currentTime", v);
 
-        mkString(v, settings.thisSystem.get());
+        v.mkString(settings.thisSystem.get());
         addConstant("__currentSystem", v);
     }
 
-    mkString(v, nixVersion);
+    v.mkString(nixVersion);
     addConstant("__nixVersion", v);
 
-    mkString(v, store->storeDir);
+    v.mkString(store->storeDir);
     addConstant("__storeDir", v);
 
     /* Language version.  This should be increased every time a new
        language feature gets added.  It's not necessary to increase it
        when primops get added, because you can just use `builtins ?
        primOp' to check. */
-    mkInt(v, 5);
+    v.mkInt(6);
     addConstant("__langVersion", v);
 
     // Miscellaneous
@@ -3716,11 +3874,10 @@ void EvalState::createBaseEnv()
     mkList(v, searchPath.size());
     int n = 0;
     for (auto & i : searchPath) {
-        auto v2 = v.listElems()[n++] = allocValue();
-        mkAttrs(*v2, 2);
-        mkString(*allocAttr(*v2, symbols.create("path")), i.second);
-        mkString(*allocAttr(*v2, symbols.create("prefix")), i.first);
-        v2->attrs->sort();
+        auto attrs = buildBindings(2);
+        attrs.alloc("path").mkString(i.second);
+        attrs.alloc("prefix").mkString(i.first);
+        (v.listElems()[n++] = allocValue())->mkAttrs(attrs);
     }
     addConstant("__nixPath", v);
 
@@ -3730,21 +3887,30 @@ void EvalState::createBaseEnv()
                 .fun = primOp.fun,
                 .arity = std::max(primOp.args.size(), primOp.arity),
                 .name = symbols.create(primOp.name),
-                .args = std::move(primOp.args),
+                .args = primOp.args,
                 .doc = primOp.doc,
             });
 
     /* Add a wrapper around the derivation primop that computes the
        `drvPath' and `outPath' attributes lazily. */
     sDerivationNix = symbols.create("//builtin/derivation.nix");
-    eval(parse(
-        #include "primops/derivation.nix.gen.hh"
-        , foFile, sDerivationNix, "/", staticBaseEnv), v);
-    addConstant("derivation", v);
+    auto vDerivation = allocValue();
+    addConstant("derivation", vDerivation);
 
     /* Now that we've added all primops, sort the `builtins' set,
        because attribute lookups expect it to be sorted. */
     baseEnv.values[0]->attrs->sort();
+
+    staticBaseEnv.sort();
+
+    /* Note: we have to initialize the 'derivation' constant *after*
+       building baseEnv/staticBaseEnv because it uses 'builtins'. */
+    char code[] =
+        #include "primops/derivation.nix.gen.hh"
+        // the parser needs two NUL bytes as terminators; one of them
+        // is implied by being a C string.
+        "\0";
+    eval(parse(code, sizeof(code), foFile, sDerivationNix, "/", staticBaseEnv), *vDerivation);
 }