Merge branch 'master' into debug-step

25 files changed, 1074 insertions, 800 deletions

diff --git a/src/libexpr/attr-path.cc b/src/libexpr/attr-path.cc
index c50c6d92b..bf0c1dabc 100644
--- a/src/libexpr/attr-path.cc
+++ b/src/libexpr/attr-path.cc
@@ -58,7 +58,7 @@ std::pair<Value *, Pos> findAlongAttrPath(EvalState & state, const string & attr
         Value * vNew = state.allocValue();
         state.autoCallFunction(autoArgs, *v, *vNew);
         v = vNew;
-        state.forceValue(*v);
+        state.forceValue(*v, noPos);
 
         /* It should evaluate to either a set or an expression,
            according to what is specified in the attrPath. */
@@ -121,7 +121,7 @@ Pos findPackageFilename(EvalState & state, Value & v, std::string what)
     std::string filename(pos, 0, colon);
     unsigned int lineno;
     try {
-        lineno = std::stoi(std::string(pos, colon + 1));
+        lineno = std::stoi(std::string(pos, colon + 1, string::npos));
     } catch (std::invalid_argument & e) {
         throw ParseError("cannot parse line number '%s'", pos);
     }
diff --git a/src/libexpr/attr-set.cc b/src/libexpr/attr-set.cc
index b6091c955..52ac47e9b 100644
--- a/src/libexpr/attr-set.cc
+++ b/src/libexpr/attr-set.cc
@@ -7,26 +7,19 @@
 namespace nix {
 
 
+
 /* Allocate a new array of attributes for an attribute set with a specific
    capacity. The space is implicitly reserved after the Bindings
    structure. */
 Bindings * EvalState::allocBindings(size_t capacity)
 {
+    if (capacity == 0)
+        return &emptyBindings;
     if (capacity > std::numeric_limits<Bindings::size_t>::max())
         throw Error("attribute set of size %d is too big", capacity);
-    return new (allocBytes(sizeof(Bindings) + sizeof(Attr) * capacity)) Bindings((Bindings::size_t) capacity);
-}
-
-
-void EvalState::mkAttrs(Value & v, size_t capacity)
-{
-    if (capacity == 0) {
-        v = vEmptySet;
-        return;
-    }
-    v.mkAttrs(allocBindings(capacity));
     nrAttrsets++;
     nrAttrsInAttrsets += capacity;
+    return new (allocBytes(sizeof(Bindings) + sizeof(Attr) * capacity)) Bindings((Bindings::size_t) capacity);
 }
 
 
@@ -41,15 +34,36 @@ Value * EvalState::allocAttr(Value & vAttrs, const Symbol & name)
 }
 
 
-Value * EvalState::allocAttr(Value & vAttrs, const std::string & name)
+Value * EvalState::allocAttr(Value & vAttrs, std::string_view name)
 {
     return allocAttr(vAttrs, symbols.create(name));
 }
 
 
+Value & BindingsBuilder::alloc(const Symbol & name, ptr<Pos> pos)
+{
+    auto value = state.allocValue();
+    bindings->push_back(Attr(name, value, pos));
+    return *value;
+}
+
+
+Value & BindingsBuilder::alloc(std::string_view name, ptr<Pos> pos)
+{
+    return alloc(state.symbols.create(name), pos);
+}
+
+
 void Bindings::sort()
 {
-    std::sort(begin(), end());
+    if (size_) std::sort(begin(), end());
+}
+
+
+Value & Value::mkAttrs(BindingsBuilder & bindings)
+{
+    mkAttrs(bindings.finish());
+    return *this;
 }
 
 
diff --git a/src/libexpr/attr-set.hh b/src/libexpr/attr-set.hh
index 7d6ffc9f3..3e4899efc 100644
--- a/src/libexpr/attr-set.hh
+++ b/src/libexpr/attr-set.hh
@@ -113,5 +113,52 @@ public:
     friend class EvalState;
 };
 
+/* A wrapper around Bindings that ensures that its always in sorted
+   order at the end. The only way to consume a BindingsBuilder is to
+   call finish(), which sorts the bindings. */
+class BindingsBuilder
+{
+    Bindings * bindings;
+
+public:
+    // needed by std::back_inserter
+    using value_type = Attr;
+
+    EvalState & state;
+
+    BindingsBuilder(EvalState & state, Bindings * bindings)
+        : bindings(bindings), state(state)
+    { }
+
+    void insert(Symbol name, Value * value, ptr<Pos> pos = ptr(&noPos))
+    {
+        insert(Attr(name, value, pos));
+    }
+
+    void insert(const Attr & attr)
+    {
+        push_back(attr);
+    }
+
+    void push_back(const Attr & attr)
+    {
+        bindings->push_back(attr);
+    }
+
+    Value & alloc(const Symbol & name, ptr<Pos> pos = ptr(&noPos));
+
+    Value & alloc(std::string_view name, ptr<Pos> pos = ptr(&noPos));
+
+    Bindings * finish()
+    {
+        bindings->sort();
+        return bindings;
+    }
+
+    Bindings * alreadySorted()
+    {
+        return bindings;
+    }
+};
 
 }
diff --git a/src/libexpr/common-eval-args.cc b/src/libexpr/common-eval-args.cc
index fb0932c00..fffca4ac5 100644
--- a/src/libexpr/common-eval-args.cc
+++ b/src/libexpr/common-eval-args.cc
@@ -73,17 +73,16 @@ MixEvalArgs::MixEvalArgs()
 
 Bindings * MixEvalArgs::getAutoArgs(EvalState & state)
 {
-    Bindings * res = state.allocBindings(autoArgs.size());
+    auto res = state.buildBindings(autoArgs.size());
     for (auto & i : autoArgs) {
-        Value * v = state.allocValue();
+        auto v = state.allocValue();
         if (i.second[0] == 'E')
             state.mkThunk_(*v, state.parseExprFromString(string(i.second, 1), absPath(".")));
         else
-            mkString(*v, string(i.second, 1));
-        res->push_back(Attr(state.symbols.create(i.first), v));
+            v->mkString(((std::string_view) i.second).substr(1));
+        res.insert(state.symbols.create(i.first), v);
     }
-    res->sort();
-    return res;
+    return res.finish();
 }
 
 Path lookupFileArg(EvalState & state, string s)
diff --git a/src/libexpr/eval-cache.cc b/src/libexpr/eval-cache.cc
index d7e21783d..d6b9ea29b 100644
--- a/src/libexpr/eval-cache.cc
+++ b/src/libexpr/eval-cache.cc
@@ -336,7 +336,7 @@ Value & AttrCursor::getValue()
     if (!_value) {
         if (parent) {
             auto & vParent = parent->first->getValue();
-            root->state.forceAttrs(vParent);
+            root->state.forceAttrs(vParent, noPos);
             auto attr = vParent.attrs->get(parent->second);
             if (!attr)
                 throw Error("attribute '%s' is unexpectedly missing", getAttrPathStr());
@@ -381,7 +381,7 @@ Value & AttrCursor::forceValue()
     auto & v = getValue();
 
     try {
-        root->state.forceValue(v);
+        root->state.forceValue(v, noPos);
     } catch (EvalError &) {
         debug("setting '%s' to failed", getAttrPathStr());
         if (root->db)
diff --git a/src/libexpr/eval-inline.hh b/src/libexpr/eval-inline.hh
index 655408cd3..aef1f6351 100644
--- a/src/libexpr/eval-inline.hh
+++ b/src/libexpr/eval-inline.hh
@@ -15,12 +15,6 @@ LocalNoInlineNoReturn(void throwEvalError(const Pos & pos, const char * s))
     });
 }
 
-LocalNoInlineNoReturn(void throwTypeError(const char * s, const Value & v))
-{
-    throw TypeError(s, showType(v));
-}
-
-
 LocalNoInlineNoReturn(void throwTypeError(const Pos & pos, const char * s, const Value & v))
 {
     throw TypeError({
@@ -32,6 +26,13 @@ LocalNoInlineNoReturn(void throwTypeError(const Pos & pos, const char * s, const
 
 void EvalState::forceValue(Value & v, const Pos & pos)
 {
+    forceValue(v, [&]() { return pos; });
+}
+
+
+template<typename Callable>
+void EvalState::forceValue(Value & v, Callable getPos)
+{
     if (v.isThunk()) {
         Env * env = v.thunk.env;
         Expr * expr = v.thunk.expr;
@@ -47,31 +48,22 @@ void EvalState::forceValue(Value & v, const Pos & pos)
     else if (v.isApp())
         callFunction(*v.app.left, *v.app.right, v, noPos);
     else if (v.isBlackhole())
-        throwEvalError(pos, "infinite recursion encountered");
-}
-
-
-inline void EvalState::forceAttrs(Value & v)
-{
-    forceValue(v);
-    if (v.type() != nAttrs)
-        throwTypeError("value is %1% while a set was expected", v);
+        throwEvalError(getPos(), "infinite recursion encountered");
 }
 
 
 inline void EvalState::forceAttrs(Value & v, const Pos & pos)
 {
-    forceValue(v, pos);
-    if (v.type() != nAttrs)
-        throwTypeError(pos, "value is %1% while a set was expected", v);
+    forceAttrs(v, [&]() { return pos; });
 }
 
 
-inline void EvalState::forceList(Value & v)
+template <typename Callable>
+inline void EvalState::forceAttrs(Value & v, Callable getPos)
 {
-    forceValue(v);
-    if (!v.isList())
-        throwTypeError("value is %1% while a list was expected", v);
+    forceValue(v, getPos);
+    if (v.type() != nAttrs)
+        throwTypeError(getPos(), "value is %1% while a set was expected", v);
 }
 
 
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 426cff2d3..790b00ace 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -1,5 +1,6 @@
 #include "eval.hh"
 #include "hash.hh"
+#include "types.hh"
 #include "util.hh"
 #include "store-api.hh"
 #include "derivations.hh"
@@ -38,6 +39,19 @@ namespace nix {
 
 std::function<void(const Error * error, const Env & env, const Expr & expr)> debuggerHook;
 
+static char * allocString(size_t size)
+{
+    char * t;
+#if HAVE_BOEHMGC
+    t = (char *) GC_MALLOC_ATOMIC(size);
+#else
+    t = malloc(size);
+#endif
+    if (!t) throw std::bad_alloc();
+    return t;
+}
+
+
 static char * dupString(const char * s)
 {
     char * t;
@@ -147,7 +161,7 @@ void printValue(std::ostream & str, std::set<const Value *> & active, const Valu
         str << v.fpoint;
         break;
     default:
-        throw Error("invalid value");
+        abort();
     }
 
     active.erase(&v);
@@ -207,7 +221,7 @@ string showType(const Value & v)
     }
 }
 
-Pos Value::determinePos(const Pos &pos) const
+Pos Value::determinePos(const Pos & pos) const
 {
     switch (internalType) {
         case tAttrs: return *attrs->pos;
@@ -414,11 +428,22 @@ EvalState::EvalState(
     , sDescription(symbols.create("description"))
     , sSelf(symbols.create("self"))
     , sEpsilon(symbols.create(""))
+    , sStartSet(symbols.create("startSet"))
+    , sOperator(symbols.create("operator"))
+    , sKey(symbols.create("key"))
+    , sPath(symbols.create("path"))
+    , sPrefix(symbols.create("prefix"))
     , repair(NoRepair)
+    , emptyBindings(0)
     , store(store)
     , buildStore(buildStore ? buildStore : store)
     , debugStop(true)
     , regexCache(makeRegexCache())
+#if HAVE_BOEHMGC
+    , valueAllocCache(std::allocate_shared<void *>(traceable_allocator<void *>(), nullptr))
+#else
+    , valueAllocCache(std::make_shared<void *>(nullptr))
+#endif
     , baseEnv(allocEnv(128))
     , staticBaseEnv(new StaticEnv(false, 0))
 {
@@ -457,8 +482,6 @@ EvalState::EvalState(
         }
     }
 
-    vEmptySet.mkAttrs(allocBindings(0));
-
     createBaseEnv();
 }
 
@@ -616,7 +639,7 @@ Value * EvalState::addPrimOp(const string & name,
         auto vPrimOp = allocValue();
         vPrimOp->mkPrimOp(new PrimOp { .fun = primOp, .arity = 1, .name = sym });
         Value v;
-        mkApp(v, *vPrimOp, *vPrimOp);
+        v.mkApp(vPrimOp, vPrimOp);
         return addConstant(name, v);
     }
 
@@ -638,7 +661,7 @@ Value * EvalState::addPrimOp(PrimOp && primOp)
         auto vPrimOp = allocValue();
         vPrimOp->mkPrimOp(new PrimOp(std::move(primOp)));
         Value v;
-        mkApp(v, *vPrimOp, *vPrimOp);
+        v.mkApp(vPrimOp, vPrimOp);
         return addConstant(primOp.name, v);
     }
 
@@ -863,6 +886,13 @@ LocalNoInlineNoReturn(void throwTypeError(const Pos & pos, const char * s, const
     throw error;
 }
 
+// LocalNoInlineNoReturn(void throwTypeError(const char * s, const Value & v, Env & env, Expr *expr))
+// {
+//     auto error = TypeError({ 
+//           .msg = hintfmt(s, showType(v))
+//           .errPos = e ;
+// }
+
 LocalNoInlineNoReturn(void throwAssertionError(const Pos & pos, const char * s, const string & s1, Env & env, Expr *expr))
 {
     auto error = AssertionError({
@@ -935,14 +965,14 @@ DebugTraceStacker::DebugTraceStacker(EvalState &evalState, DebugTrace t)
         debuggerHook(0, t.env, t.expr);
 }
 
-void mkString(Value & v, const char * s)
+void Value::mkString(std::string_view s)
 {
-    v.mkString(dupString(s));
+    mkString(dupStringWithLen(s.data(), s.size()));
 }
 
-Value & mkString(Value & v, std::string_view s, const PathSet & context)
+
+static void copyContextToValue(Value & v, const PathSet & context)
 {
-    v.mkString(dupStringWithLen(s.data(), s.size()));
     if (!context.empty()) {
         size_t n = 0;
         v.string.context = (const char * *)
@@ -951,13 +981,24 @@ Value & mkString(Value & v, std::string_view s, const PathSet & context)
             v.string.context[n++] = dupString(i.c_str());
         v.string.context[n] = 0;
     }
-    return v;
 }
 
+void Value::mkString(std::string_view s, const PathSet & context)
+{
+    mkString(s);
+    copyContextToValue(*this, context);
+}
 
-void mkPath(Value & v, const char * s)
+void Value::mkStringMove(const char * s, const PathSet & context)
 {
-    v.mkPath(dupString(s));
+    mkString(s);
+    copyContextToValue(*this, context);
+}
+
+
+void Value::mkPath(std::string_view s)
+{
+    mkPath(dupStringWithLen(s.data(), s.size()));
 }
 
 
@@ -994,15 +1035,15 @@ Value * EvalState::allocValue()
        GC_malloc_many returns a linked list of objects of the given size, where the first word
        of each object is also the pointer to the next object in the list. This also means that we
        have to explicitly clear the first word of every object we take. */
-    if (!valueAllocCache) {
-        valueAllocCache = GC_malloc_many(sizeof(Value));
-        if (!valueAllocCache) throw std::bad_alloc();
+    if (!*valueAllocCache) {
+        *valueAllocCache = GC_malloc_many(sizeof(Value));
+        if (!*valueAllocCache) throw std::bad_alloc();
     }
 
     /* GC_NEXT is a convenience macro for accessing the first word of an object.
        Take the first list item, advance the list to the next item, and clear the next pointer. */
-    void * p = valueAllocCache;
-    GC_PTR_STORE_AND_DIRTY(&valueAllocCache, GC_NEXT(p));
+    void * p = *valueAllocCache;
+    GC_PTR_STORE_AND_DIRTY(&*valueAllocCache, GC_NEXT(p));
     GC_NEXT(p) = nullptr;
 
     nrValues++;
@@ -1061,13 +1102,13 @@ void EvalState::mkThunk_(Value & v, Expr * expr)
 void EvalState::mkPos(Value & v, ptr<Pos> pos)
 {
     if (pos->file.set()) {
-        mkAttrs(v, 3);
-        mkString(*allocAttr(v, sFile), pos->file);
-        mkInt(*allocAttr(v, sLine), pos->line);
-        mkInt(*allocAttr(v, sColumn), pos->column);
-        v.attrs->sort();
+        auto attrs = buildBindings(3);
+        attrs.alloc(sFile).mkString(pos->file);
+        attrs.alloc(sLine).mkInt(pos->line);
+        attrs.alloc(sColumn).mkInt(pos->column);
+        v.mkAttrs(attrs);
     } else
-        mkNull(v);
+        v.mkNull();
 }
 
 
@@ -1256,8 +1297,8 @@ void ExprPath::eval(EvalState & state, Env & env, Value & v)
 
 void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
 {
-    state.mkAttrs(v, attrs.size() + dynamicAttrs.size());
-    Env *dynamicEnv = &env;
+    v.mkAttrs(state.buildBindings(attrs.size() + dynamicAttrs.size()).finish());
+    auto dynamicEnv = &env;
 
     if (recursive) {
         /* Create a new environment that contains the attributes in
@@ -1294,7 +1335,7 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
            Hence we need __overrides.) */
         if (hasOverrides) {
             Value * vOverrides = (*v.attrs)[overrides->second.displ].value;
-            state.forceAttrs(*vOverrides);
+            state.forceAttrs(*vOverrides, [&]() { return vOverrides->determinePos(noPos); });
             Bindings * newBnds = state.allocBindings(v.attrs->capacity() + vOverrides->attrs->size());
             for (auto & i : *v.attrs)
                 newBnds->push_back(i);
@@ -1453,20 +1494,20 @@ void ExprOpHasAttr::eval(EvalState & state, Env & env, Value & v)
     e->eval(state, env, vTmp);
 
     for (auto & i : attrPath) {
-        state.forceValue(*vAttrs);
+        state.forceValue(*vAttrs, noPos);
         Bindings::iterator j;
         Symbol name = getName(i, state, env);
         if (vAttrs->type() != nAttrs ||
             (j = vAttrs->attrs->find(name)) == vAttrs->attrs->end())
         {
-            mkBool(v, false);
+            v.mkBool(false);
             return;
         } else {
             vAttrs = j->value;
         }
     }
 
-    mkBool(v, true);
+    v.mkBool(true);
 }
 
 
@@ -1540,7 +1581,7 @@ void EvalState::callFunction(Value & fun, size_t nrArgs, Value * * args, Value &
                     /* Nope, so show the first unexpected argument to the
                        user. */
                     for (auto & i : *args[0]->attrs)
-                        if (lambda.formals->argNames.find(i.name) == lambda.formals->argNames.end())
+                        if (!lambda.formals->has(i.name))
                             throwTypeError(pos, "%1% called with unexpected argument '%2%'",
                                 lambda, i.name, *fun.lambda.env, &lambda);
                     abort(); // can't happen
@@ -1676,14 +1717,16 @@ void EvalState::incrFunctionCall(ExprLambda * fun)
 
 void EvalState::autoCallFunction(Bindings & args, Value & fun, Value & res)
 {
-    forceValue(fun);
+    auto pos = fun.determinePos(noPos);
+
+    forceValue(fun, pos);
 
     if (fun.type() == nAttrs) {
         auto found = fun.attrs->find(sFunctor);
         if (found != fun.attrs->end()) {
             Value * v = allocValue();
-            callFunction(*found->value, fun, *v, noPos);
-            forceValue(*v);
+            callFunction(*found->value, fun, *v, pos);
+            forceValue(*v, pos);
             return autoCallFunction(args, *v, res);
         }
     }
@@ -1693,22 +1736,20 @@ void EvalState::autoCallFunction(Bindings & args, Value & fun, Value & res)
         return;
     }
 
-    Value * actualArgs = allocValue();
-    mkAttrs(*actualArgs, std::max(static_cast<uint32_t>(fun.lambda.fun->formals->formals.size()), args.size()));
+    auto attrs = buildBindings(std::max(static_cast<uint32_t>(fun.lambda.fun->formals->formals.size()), args.size()));
 
     if (fun.lambda.fun->formals->ellipsis) {
         // If the formals have an ellipsis (eg the function accepts extra args) pass
         // all available automatic arguments (which includes arguments specified on
         // the command line via --arg/--argstr)
-        for (auto& v : args) {
-            actualArgs->attrs->push_back(v);
-        }
+        for (auto & v : args)
+            attrs.insert(v);
     } else {
         // Otherwise, only pass the arguments that the function accepts
         for (auto & i : fun.lambda.fun->formals->formals) {
             Bindings::iterator j = args.find(i.name);
             if (j != args.end()) {
-                actualArgs->attrs->push_back(*j);
+                attrs.insert(*j);
             } else if (!i.def) {
                 throwMissingArgumentError(i.pos, R"(cannot evaluate a function that has an argument without a value ('%1%')
 
@@ -1722,9 +1763,7 @@ https://nixos.org/manual/nix/stable/#ss-functions.)",
         }
     }
 
-    actualArgs->attrs->sort();
-
-    callFunction(fun, *actualArgs, res, noPos);
+    callFunction(fun, allocValue()->mkAttrs(attrs), res, noPos);
 }
 
 
@@ -1759,7 +1798,7 @@ void ExprAssert::eval(EvalState & state, Env & env, Value & v)
 
 void ExprOpNot::eval(EvalState & state, Env & env, Value & v)
 {
-    mkBool(v, !state.evalBool(env, e));
+    v.mkBool(!state.evalBool(env, e));
 }
 
 
@@ -1767,7 +1806,7 @@ void ExprOpEq::eval(EvalState & state, Env & env, Value & v)
 {
     Value v1; e1->eval(state, env, v1);
     Value v2; e2->eval(state, env, v2);
-    mkBool(v, state.eqValues(v1, v2));
+    v.mkBool(state.eqValues(v1, v2));
 }
 
 
@@ -1775,25 +1814,25 @@ void ExprOpNEq::eval(EvalState & state, Env & env, Value & v)
 {
     Value v1; e1->eval(state, env, v1);
     Value v2; e2->eval(state, env, v2);
-    mkBool(v, !state.eqValues(v1, v2));
+    v.mkBool(!state.eqValues(v1, v2));
 }
 
 
 void ExprOpAnd::eval(EvalState & state, Env & env, Value & v)
 {
-    mkBool(v, state.evalBool(env, e1, pos) && state.evalBool(env, e2, pos));
+    v.mkBool(state.evalBool(env, e1, pos) && state.evalBool(env, e2, pos));
 }
 
 
 void ExprOpOr::eval(EvalState & state, Env & env, Value & v)
 {
-    mkBool(v, state.evalBool(env, e1, pos) || state.evalBool(env, e2, pos));
+    v.mkBool(state.evalBool(env, e1, pos) || state.evalBool(env, e2, pos));
 }
 
 
 void ExprOpImpl::eval(EvalState & state, Env & env, Value & v)
 {
-    mkBool(v, !state.evalBool(env, e1, pos) || state.evalBool(env, e2, pos));
+    v.mkBool(!state.evalBool(env, e1, pos) || state.evalBool(env, e2, pos));
 }
 
 
@@ -1808,7 +1847,7 @@ void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
     if (v1.attrs->size() == 0) { v = v2; return; }
     if (v2.attrs->size() == 0) { v = v1; return; }
 
-    state.mkAttrs(v, v1.attrs->size() + v2.attrs->size());
+    auto attrs = state.buildBindings(v1.attrs->size() + v2.attrs->size());
 
     /* Merge the sets, preferring values from the second set.  Make
        sure to keep the resulting vector in sorted order. */
@@ -1817,17 +1856,19 @@ void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
 
     while (i != v1.attrs->end() && j != v2.attrs->end()) {
         if (i->name == j->name) {
-            v.attrs->push_back(*j);
+            attrs.insert(*j);
             ++i; ++j;
         }
         else if (i->name < j->name)
-            v.attrs->push_back(*i++);
+            attrs.insert(*i++);
         else
-            v.attrs->push_back(*j++);
+            attrs.insert(*j++);
     }
 
-    while (i != v1.attrs->end()) v.attrs->push_back(*i++);
-    while (j != v2.attrs->end()) v.attrs->push_back(*j++);
+    while (i != v1.attrs->end()) attrs.insert(*i++);
+    while (j != v2.attrs->end()) attrs.insert(*j++);
+
+    v.mkAttrs(attrs.alreadySorted());
 
     state.nrOpUpdateValuesCopied += v.attrs->size();
 }
@@ -1874,15 +1915,39 @@ void EvalState::concatLists(Value & v, size_t nrLists, Value * * lists, const Po
 void ExprConcatStrings::eval(EvalState & state, Env & env, Value & v)
 {
     PathSet context;
-    std::ostringstream s;
+    std::vector<BackedStringView> s;
+    size_t sSize = 0;
     NixInt n = 0;
     NixFloat nf = 0;
 
     bool first = !forceString;
     ValueType firstType = nString;
 
+    const auto str = [&] {
+        std::string result;
+        result.reserve(sSize);
+        for (const auto & part : s) result += *part;
+        return result;
+    };
+    /* c_str() is not str().c_str() because we want to create a string
+       Value. allocating a GC'd string directly and moving it into a
+       Value lets us avoid an allocation and copy. */
+    const auto c_str = [&] {
+        char * result = allocString(sSize + 1);
+        char * tmp = result;
+        for (const auto & part : s) {
+            memcpy(tmp, part->data(), part->size());
+            tmp += part->size();
+        }
+        *tmp = 0;
+        return result;
+    };
+
+    Value values[es->size()];
+    Value * vTmpP = values;
+
     for (auto & [i_pos, i] : *es) {
-        Value vTmp;
+        Value & vTmp = *vTmpP++;
         i->eval(state, env, vTmp);
 
         /* If the first element is a path, then the result will also
@@ -1911,26 +1976,29 @@ void ExprConcatStrings::eval(EvalState & state, Env & env, Value & v)
                 nf += vTmp.fpoint;
             } else
                 throwEvalError(i_pos, "cannot add %1% to a float", showType(vTmp), env, this);
-        } else
+        } else {
+            if (s.empty()) s.reserve(es->size());
             /* skip canonization of first path, which would only be not
             canonized in the first place if it's coming from a ./${foo} type
             path */
-            s << state.coerceToString(i_pos, vTmp, context, false, firstType == nString, !first);
+            auto part = state.coerceToString(i_pos, vTmp, context, false, firstType == nString, !first);
+            sSize += part->size();
+            s.emplace_back(std::move(part));
+        }
 
         first = false;
     }
 
     if (firstType == nInt)
-        mkInt(v, n);
+        v.mkInt(n);
     else if (firstType == nFloat)
-        mkFloat(v, nf);
+        v.mkFloat(nf);
     else if (firstType == nPath) {
         if (!context.empty())
             throwEvalError(pos, "a string that refers to a store path cannot be appended to a path");
-        auto path = canonPath(s.str());
-        mkPath(v, path.c_str());
+        v.mkPath(canonPath(str()));
     } else
-        mkString(v, s.str(), context);
+        v.mkStringMove(c_str(), context);
 }
 
 
@@ -1949,7 +2017,7 @@ void EvalState::forceValueDeep(Value & v)
     recurse = [&](Value & v) {
         if (!seen.insert(&v).second) return;
 
-        forceValue(v);
+        forceValue(v, [&]() { return v.determinePos(noPos); });
 
         if (v.type() == nAttrs) {
             for (auto & i : *v.attrs)
@@ -2028,14 +2096,14 @@ void EvalState::forceFunction(Value & v, const Pos & pos)
 }
 
 
-string EvalState::forceString(Value & v, const Pos & pos)
+std::string_view EvalState::forceString(Value & v, const Pos & pos)
 {
     forceValue(v, pos);
     if (v.type() != nString) {
         throwTypeError(pos, "value is %1% while a string was expected", v,
             fakeEnv(1), 0);
     }
-    return string(v.string.s);
+    return v.string.s;
 }
 
 
@@ -2070,17 +2138,17 @@ std::vector<std::pair<Path, std::string>> Value::getContext()
 }
 
 
-string EvalState::forceString(Value & v, PathSet & context, const Pos & pos)
+std::string_view EvalState::forceString(Value & v, PathSet & context, const Pos & pos)
 {
-    string s = forceString(v, pos);
+    auto s = forceString(v, pos);
     copyContext(v, context);
     return s;
 }
 
 
-string EvalState::forceStringNoCtx(Value & v, const Pos & pos)
+std::string_view EvalState::forceStringNoCtx(Value & v, const Pos & pos)
 {
-    string s = forceString(v, pos);
+    auto s = forceString(v, pos);
     if (v.string.context) {
         if (pos)
             throwEvalError(pos, "the string '%1%' is not allowed to refer to a store path (such as '%2%')",
@@ -2098,7 +2166,7 @@ bool EvalState::isDerivation(Value & v)
     if (v.type() != nAttrs) return false;
     Bindings::iterator i = v.attrs->find(sType);
     if (i == v.attrs->end()) return false;
-    forceValue(*i->value);
+    forceValue(*i->value, *i->pos);
     if (i->value->type() != nString) return false;
     return strcmp(i->value->string.s, "derivation") == 0;
 }
@@ -2111,34 +2179,35 @@ std::optional<string> EvalState::tryAttrsToString(const Pos & pos, Value & v,
     if (i != v.attrs->end()) {
         Value v1;
         callFunction(*i->value, v, v1, pos);
-        return coerceToString(pos, v1, context, coerceMore, copyToStore);
+        return coerceToString(pos, v1, context, coerceMore, copyToStore).toOwned();
     }
 
     return {};
 }
 
-string EvalState::coerceToString(const Pos & pos, Value & v, PathSet & context,
+BackedStringView EvalState::coerceToString(const Pos & pos, Value & v, PathSet & context,
     bool coerceMore, bool copyToStore, bool canonicalizePath)
 {
     forceValue(v, pos);
 
-    string s;
-
     if (v.type() == nString) {
         copyContext(v, context);
-        return v.string.s;
+        return std::string_view(v.string.s);
     }
 
     if (v.type() == nPath) {
-        Path path(canonicalizePath ? canonPath(v.path) : v.path);
-        return copyToStore ? copyPathToStore(context, path) : path;
+        BackedStringView path(PathView(v.path));
+        if (canonicalizePath)
+            path = canonPath(*path);
+        if (copyToStore)
+            path = copyPathToStore(context, std::move(path).toOwned());
+        return path;
     }
 
     if (v.type() == nAttrs) {
         auto maybeString = tryAttrsToString(pos, v, context, coerceMore, copyToStore);
-        if (maybeString) {
-            return *maybeString;
-        }
+        if (maybeString)
+            return std::move(*maybeString);
         auto i = v.attrs->find(sOutPath);
         if (i == v.attrs->end())
             throwTypeError(pos, "cannot coerce a set to a string",
@@ -2161,14 +2230,13 @@ string EvalState::coerceToString(const Pos & pos, Value & v, PathSet & context,
         if (v.isList()) {
             string result;
             for (auto [n, v2] : enumerate(v.listItems())) {
-                result += coerceToString(pos, *v2,
-                    context, coerceMore, copyToStore);
+                result += *coerceToString(pos, *v2, context, coerceMore, copyToStore);
                 if (n < v.listSize() - 1
                     /* !!! not quite correct */
                     && (!v2->isList() || v2->listSize() != 0))
                     result += " ";
             }
-            return result;
+            return std::move(result);
         }
     }
 
@@ -2205,7 +2273,7 @@ string EvalState::copyPathToStore(PathSet & context, const Path & path)
 
 Path EvalState::coerceToPath(const Pos & pos, Value & v, PathSet & context)
 {
-    string path = coerceToString(pos, v, context, false, false);
+    string path = coerceToString(pos, v, context, false, false).toOwned();
     if (path == "" || path[0] != '/')
         throwEvalError(pos, "string '%1%' doesn't represent an absolute path", path,
             fakeEnv(1), 0);
@@ -2215,8 +2283,8 @@ Path EvalState::coerceToPath(const Pos & pos, Value & v, PathSet & context)
 
 bool EvalState::eqValues(Value & v1, Value & v2)
 {
-    forceValue(v1);
-    forceValue(v2);
+    forceValue(v1, noPos);
+    forceValue(v2, noPos);
 
     /* !!! Hack to support some old broken code that relies on pointer
        equality tests between sets.  (Specifically, builderDefs calls
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 649fda778..8c4430bc8 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "attr-set.hh"
+#include "types.hh"
 #include "value.hh"
 #include "nixexpr.hh"
 #include "symbol-table.hh"
@@ -49,8 +50,6 @@ struct Env
 
 valmap * mapStaticEnvBindings(const StaticEnv &se, const Env &env);
 
-Value & mkString(Value & v, std::string_view s, const PathSet & context = PathSet());
-
 void copyContext(const Value & v, PathSet & context);
 
 
@@ -93,7 +92,8 @@ public:
         sContentAddressed,
         sOutputHash, sOutputHashAlgo, sOutputHashMode,
         sRecurseForDerivations,
-        sDescription, sSelf, sEpsilon;
+        sDescription, sSelf, sEpsilon, sStartSet, sOperator, sKey, sPath,
+        sPrefix;
     Symbol sDerivationNix;
 
     /* If set, force copying files to the Nix store even if they
@@ -104,7 +104,7 @@ public:
        mode. */
     std::optional<PathSet> allowedPaths;
 
-    Value vEmptySet;
+    Bindings emptyBindings;
 
     /* Store used to materialise .drv files. */
     const ref<Store> store;
@@ -148,7 +148,7 @@ private:
     std::shared_ptr<RegexCache> regexCache;
 
     /* Allocation cache for GC'd Value objects. */
-    void * valueAllocCache = nullptr;
+    std::shared_ptr<void *> valueAllocCache;
 
 public:
 
@@ -195,8 +195,8 @@ public:
     Expr * parseExprFromFile(const Path & path, std::shared_ptr<StaticEnv> & staticEnv);
 
     /* Parse a Nix expression from the specified string. */
-    Expr * parseExprFromString(std::string_view s, const Path & basePath, std::shared_ptr<StaticEnv> & staticEnv);
-    Expr * parseExprFromString(std::string_view s, const Path & basePath);
+    Expr * parseExprFromString(std::string s, const Path & basePath, , std::shared_ptr<StaticEnv> & staticEnv);
+    Expr * parseExprFromString(std::string s, const Path & basePath);
 
     Expr * parseStdin();
 
@@ -216,8 +216,8 @@ public:
     void resetFileCache();
 
     /* Look up a file in the search path. */
-    Path findFile(const string & path);
-    Path findFile(SearchPath & searchPath, const string & path, const Pos & pos = noPos);
+    Path findFile(const std::string_view path);
+    Path findFile(SearchPath & searchPath, const std::string_view path, const Pos & pos = noPos);
 
     /* If the specified search path element is a URI, download it. */
     std::pair<bool, std::string> resolveSearchPathElem(const SearchPathElem & elem);
@@ -236,7 +236,10 @@ public:
        of the evaluation of the thunk.  If `v' is a delayed function
        application, call the function and overwrite `v' with the
        result.  Otherwise, this is a no-op. */
-    inline void forceValue(Value & v, const Pos & pos = noPos);
+    inline void forceValue(Value & v, const Pos & pos);
+
+    template <typename Callable>
+    inline void forceValue(Value & v, Callable getPos);
 
     /* Force a value, then recursively force list elements and
        attributes. */
@@ -246,14 +249,17 @@ public:
     NixInt forceInt(Value & v, const Pos & pos);
     NixFloat forceFloat(Value & v, const Pos & pos);
     bool forceBool(Value & v, const Pos & pos);
-    inline void forceAttrs(Value & v);
-    inline void forceAttrs(Value & v, const Pos & pos);
-    inline void forceList(Value & v);
+
+    void forceAttrs(Value & v, const Pos & pos);
+
+    template <typename Callable>
+    inline void forceAttrs(Value & v, Callable getPos);
+
     inline void forceList(Value & v, const Pos & pos);
     void forceFunction(Value & v, const Pos & pos); // either lambda or primop
-    string forceString(Value & v, const Pos & pos = noPos);
-    string forceString(Value & v, PathSet & context, const Pos & pos = noPos);
-    string forceStringNoCtx(Value & v, const Pos & pos = noPos);
+    std::string_view forceString(Value & v, const Pos & pos = noPos);
+    std::string_view forceString(Value & v, PathSet & context, const Pos & pos = noPos);
+    std::string_view forceStringNoCtx(Value & v, const Pos & pos = noPos);
 
     /* Return true iff the value `v' denotes a derivation (i.e. a
        set with attribute `type = "derivation"'). */
@@ -266,7 +272,7 @@ public:
        string.  If `coerceMore' is set, also converts nulls, integers,
        booleans and lists to a string.  If `copyToStore' is set,
        referenced paths are copied to the Nix store as a side effect. */
-    string coerceToString(const Pos & pos, Value & v, PathSet & context,
+    BackedStringView coerceToString(const Pos & pos, Value & v, PathSet & context,
         bool coerceMore = false, bool copyToStore = true,
         bool canonicalizePath = true);
 
@@ -324,7 +330,7 @@ private:
     friend struct ExprAttrs;
     friend struct ExprLet;
 
-    Expr * parse(const char * text, FileOrigin origin, const Path & path,
+    Expr * parse(char * text, size_t length, FileOrigin origin, const PathView path,
         const Path & basePath, std::shared_ptr<StaticEnv> & staticEnv);
 
 public:
@@ -353,12 +359,16 @@ public:
     Env & allocEnv(size_t size);
 
     Value * allocAttr(Value & vAttrs, const Symbol & name);
-    Value * allocAttr(Value & vAttrs, const std::string & name);
+    Value * allocAttr(Value & vAttrs, std::string_view name);
 
     Bindings * allocBindings(size_t capacity);
 
+    BindingsBuilder buildBindings(size_t capacity)
+    {
+        return BindingsBuilder(*this, allocBindings(capacity));
+    }
+
     void mkList(Value & v, size_t length);
-    void mkAttrs(Value & v, size_t capacity);
     void mkThunk_(Value & v, Expr * expr);
     void mkPos(Value & v, ptr<Pos> pos);
 
@@ -411,6 +421,9 @@ private:
     friend struct ExprSelect;
     friend void prim_getAttr(EvalState & state, const Pos & pos, Value * * args, Value & v);
     friend void prim_match(EvalState & state, const Pos & pos, Value * * args, Value & v);
+    friend void prim_split(EvalState & state, const Pos & pos, Value * * args, Value & v);
+
+    friend struct Value;
 };
 
 class DebugTraceStacker {
diff --git a/src/libexpr/flake/flake.cc b/src/libexpr/flake/flake.cc
index c549c5971..9f3b58909 100644
--- a/src/libexpr/flake/flake.cc
+++ b/src/libexpr/flake/flake.cc
@@ -89,11 +89,11 @@ static void expectType(EvalState & state, ValueType type,
 
 static std::map<FlakeId, FlakeInput> parseFlakeInputs(
     EvalState & state, Value * value, const Pos & pos,
-    const std::optional<Path> & baseDir);
+    const std::optional<Path> & baseDir, InputPath lockRootPath);
 
 static FlakeInput parseFlakeInput(EvalState & state,
     const std::string & inputName, Value * value, const Pos & pos,
-    const std::optional<Path> & baseDir)
+    const std::optional<Path> & baseDir, InputPath lockRootPath)
 {
     expectType(state, nAttrs, *value, pos);
 
@@ -117,10 +117,12 @@ static FlakeInput parseFlakeInput(EvalState & state,
                 expectType(state, nBool, *attr.value, *attr.pos);
                 input.isFlake = attr.value->boolean;
             } else if (attr.name == sInputs) {
-                input.overrides = parseFlakeInputs(state, attr.value, *attr.pos, baseDir);
+                input.overrides = parseFlakeInputs(state, attr.value, *attr.pos, baseDir, lockRootPath);
             } else if (attr.name == sFollows) {
                 expectType(state, nString, *attr.value, *attr.pos);
-                input.follows = parseInputPath(attr.value->string.s);
+                auto follows(parseInputPath(attr.value->string.s));
+                follows.insert(follows.begin(), lockRootPath.begin(), lockRootPath.end());
+                input.follows = follows;
             } else {
                 switch (attr.value->type()) {
                     case nString:
@@ -166,7 +168,7 @@ static FlakeInput parseFlakeInput(EvalState & state,
 
 static std::map<FlakeId, FlakeInput> parseFlakeInputs(
     EvalState & state, Value * value, const Pos & pos,
-    const std::optional<Path> & baseDir)
+    const std::optional<Path> & baseDir, InputPath lockRootPath)
 {
     std::map<FlakeId, FlakeInput> inputs;
 
@@ -178,7 +180,8 @@ static std::map<FlakeId, FlakeInput> parseFlakeInputs(
                 inputAttr.name,
                 inputAttr.value,
                 *inputAttr.pos,
-                baseDir));
+                baseDir,
+                lockRootPath));
     }
 
     return inputs;
@@ -188,7 +191,8 @@ static Flake getFlake(
     EvalState & state,
     const FlakeRef & originalRef,
     bool allowLookup,
-    FlakeCache & flakeCache)
+    FlakeCache & flakeCache,
+    InputPath lockRootPath)
 {
     auto [sourceInfo, resolvedRef, lockedRef] = fetchOrSubstituteTree(
         state, originalRef, allowLookup, flakeCache);
@@ -223,7 +227,7 @@ static Flake getFlake(
     auto sInputs = state.symbols.create("inputs");
 
     if (auto inputs = vInfo.attrs->get(sInputs))
-        flake.inputs = parseFlakeInputs(state, inputs->value, *inputs->pos, flakeDir);
+        flake.inputs = parseFlakeInputs(state, inputs->value, *inputs->pos, flakeDir, lockRootPath);
 
     auto sOutputs = state.symbols.create("outputs");
 
@@ -250,7 +254,13 @@ static Flake getFlake(
         for (auto & setting : *nixConfig->value->attrs) {
             forceTrivialValue(state, *setting.value, *setting.pos);
             if (setting.value->type() == nString)
-                flake.config.settings.insert({setting.name, state.forceStringNoCtx(*setting.value, *setting.pos)});
+                flake.config.settings.insert({setting.name, string(state.forceStringNoCtx(*setting.value, *setting.pos))});
+            else if (setting.value->type() == nPath) {
+                PathSet emptyContext = {};
+                flake.config.settings.emplace(
+                    setting.name,
+                    state.coerceToString(*setting.pos, *setting.value, emptyContext, false, true, true) .toOwned());
+            }
             else if (setting.value->type() == nInt)
                 flake.config.settings.insert({setting.name, state.forceInt(*setting.value, *setting.pos)});
             else if (setting.value->type() == nBool)
@@ -261,7 +271,7 @@ static Flake getFlake(
                     if (elem->type() != nString)
                         throw TypeError("list element in flake configuration setting '%s' is %s while a string is expected",
                             setting.name, showType(*setting.value));
-                    ss.push_back(state.forceStringNoCtx(*elem, *setting.pos));
+                    ss.emplace_back(state.forceStringNoCtx(*elem, *setting.pos));
                 }
                 flake.config.settings.insert({setting.name, ss});
             }
@@ -283,6 +293,11 @@ static Flake getFlake(
     return flake;
 }
 
+Flake getFlake(EvalState & state, const FlakeRef & originalRef, bool allowLookup, FlakeCache & flakeCache)
+{
+    return getFlake(state, originalRef, allowLookup, flakeCache, {});
+}
+
 Flake getFlake(EvalState & state, const FlakeRef & originalRef, bool allowLookup)
 {
     FlakeCache flakeCache;
@@ -328,22 +343,12 @@ LockedFlake lockFlake(
 
         std::vector<FlakeRef> parents;
 
-        struct LockParent {
-            /* The path to this parent. */
-            InputPath path;
-
-            /* Whether we are currently inside a top-level lockfile
-               (inputs absolute) or subordinate lockfile (inputs
-               relative). */
-            bool absolute;
-        };
-
         std::function<void(
             const FlakeInputs & flakeInputs,
             std::shared_ptr<Node> node,
             const InputPath & inputPathPrefix,
             std::shared_ptr<const Node> oldNode,
-            const LockParent & parent,
+            const InputPath & lockRootPath,
             const Path & parentPath,
             bool trustLock)>
             computeLocks;
@@ -353,7 +358,7 @@ LockedFlake lockFlake(
             std::shared_ptr<Node> node,
             const InputPath & inputPathPrefix,
             std::shared_ptr<const Node> oldNode,
-            const LockParent & parent,
+            const InputPath & lockRootPath,
             const Path & parentPath,
             bool trustLock)
         {
@@ -398,17 +403,7 @@ LockedFlake lockFlake(
                     if (input.follows) {
                         InputPath target;
 
-                        if (parent.absolute && !hasOverride) {
-                            target = *input.follows;
-                        } else {
-                            if (hasOverride) {
-                                target = inputPathPrefix;
-                                target.pop_back();
-                            } else
-                                target = parent.path;
-
-                            for (auto & i : *input.follows) target.push_back(i);
-                        }
+                        target.insert(target.end(), input.follows->begin(), input.follows->end());
 
                         debug("input '%s' follows '%s'", inputPathS, printInputPath(target));
                         node->inputs.insert_or_assign(id, target);
@@ -481,23 +476,25 @@ LockedFlake lockFlake(
                                             break;
                                         }
                                     }
+                                    auto absoluteFollows(lockRootPath);
+                                    absoluteFollows.insert(absoluteFollows.end(), follows->begin(), follows->end());
                                     fakeInputs.emplace(i.first, FlakeInput {
-                                        .follows = *follows,
+                                        .follows = absoluteFollows,
                                     });
                                 }
                             }
                         }
 
-                        LockParent newParent {
-                            .path = inputPath,
-                            .absolute = true
-                        };
-
+                        auto localPath(parentPath);
+                        // If this input is a path, recurse it down.
+                        // This allows us to resolve path inputs relative to the current flake.
+                        if ((*input.ref).input.getType() == "path")
+                            localPath = absPath(*input.ref->input.getSourcePath(), parentPath);
                         computeLocks(
                             mustRefetch
-                            ? getFlake(state, oldLock->lockedRef, false, flakeCache).inputs
+                            ? getFlake(state, oldLock->lockedRef, false, flakeCache, inputPath).inputs
                             : fakeInputs,
-                            childNode, inputPath, oldLock, newParent, parentPath, !mustRefetch);
+                            childNode, inputPath, oldLock, lockRootPath, parentPath, !mustRefetch);
 
                     } else {
                         /* We need to create a new lock file entry. So fetch
@@ -516,7 +513,7 @@ LockedFlake lockFlake(
                             if (localRef.input.getType() == "path")
                                 localPath = absPath(*input.ref->input.getSourcePath(), parentPath);
 
-                            auto inputFlake = getFlake(state, localRef, useRegistries, flakeCache);
+                            auto inputFlake = getFlake(state, localRef, useRegistries, flakeCache, inputPath);
 
                             /* Note: in case of an --override-input, we use
                                the *original* ref (input2.ref) for the
@@ -537,13 +534,6 @@ LockedFlake lockFlake(
                             parents.push_back(*input.ref);
                             Finally cleanup([&]() { parents.pop_back(); });
 
-                            // Follows paths from existing inputs in the top-level lockfile are absolute,
-                            // whereas paths in subordinate lockfiles are relative to those lockfiles.
-                            LockParent newParent {
-                                .path = inputPath,
-                                .absolute = oldLock ? true : false
-                            };
-
                             /* Recursively process the inputs of this
                                flake. Also, unless we already have this flake
                                in the top-level lock file, use this flake's
@@ -554,7 +544,7 @@ LockedFlake lockFlake(
                                 ? std::dynamic_pointer_cast<const Node>(oldLock)
                                 : LockFile::read(
                                     inputFlake.sourceInfo->actualPath + "/" + inputFlake.lockedRef.subdir + "/flake.lock").root,
-                                newParent, localPath, false);
+                                oldLock ? lockRootPath : inputPath, localPath, false);
                         }
 
                         else {
@@ -572,17 +562,12 @@ LockedFlake lockFlake(
             }
         };
 
-        LockParent parent {
-            .path = {},
-            .absolute = true
-        };
-
         // Bring in the current ref for relative path resolution if we have it
         auto parentPath = canonPath(flake.sourceInfo->actualPath + "/" + flake.lockedRef.subdir, true);
 
         computeLocks(
             flake.inputs, newLockFile.root, {},
-            lockFlags.recreateLockFile ? nullptr : oldLockFile.root, parent, parentPath, false);
+            lockFlags.recreateLockFile ? nullptr : oldLockFile.root, {}, parentPath, false);
 
         for (auto & i : lockFlags.inputOverrides)
             if (!overridesUsed.count(i.first))
@@ -629,12 +614,24 @@ LockedFlake lockFlake(
 
                         newLockFile.write(path);
 
+                        std::optional<std::string> commitMessage = std::nullopt;
+                        if (lockFlags.commitLockFile) {
+                            std::string cm;
+
+                            cm = settings.commitLockFileSummary.get();
+
+                            if (cm == "") {
+                                cm = fmt("%s: %s", relPath, lockFileExists ? "Update" : "Add");
+                            }
+
+                            cm += "\n\nFlake lock file updates:\n\n";
+                            cm += filterANSIEscapes(diff, true);
+                            commitMessage = cm;
+                        }
+
                         topRef.input.markChangedFile(
                             (topRef.subdir == "" ? "" : topRef.subdir + "/") + "flake.lock",
-                            lockFlags.commitLockFile
-                            ? std::optional<std::string>(fmt("%s: %s\n\nFlake lock file changes:\n\n%s",
-                                    relPath, lockFileExists ? "Update" : "Add", filterANSIEscapes(diff, true)))
-                            : std::nullopt);
+                            commitMessage);
 
                         /* Rewriting the lockfile changed the top-level
                            repo, so we should re-read it. FIXME: we could
@@ -682,7 +679,7 @@ void callFlake(EvalState & state,
     auto vTmp1 = state.allocValue();
     auto vTmp2 = state.allocValue();
 
-    mkString(*vLocks, lockedFlake.lockFile.to_string());
+    vLocks->mkString(lockedFlake.lockFile.to_string());
 
     emitTreeAttrs(
         state,
@@ -692,7 +689,7 @@ void callFlake(EvalState & state,
         false,
         lockedFlake.flake.forceDirty);
 
-    mkString(*vRootSubdir, lockedFlake.flake.lockedRef.subdir);
+    vRootSubdir->mkString(lockedFlake.flake.lockedRef.subdir);
 
     if (!state.vCallFlake) {
         state.vCallFlake = allocRootValue(state.allocValue());
@@ -710,7 +707,7 @@ static void prim_getFlake(EvalState & state, const Pos & pos, Value * * args, Va
 {
     state.requireExperimentalFeatureOnEvaluation(Xp::Flakes, "builtins.getFlake", pos);
 
-    auto flakeRefS = state.forceStringNoCtx(*args[0], pos);
+    string flakeRefS(state.forceStringNoCtx(*args[0], pos));
     auto flakeRef = parseFlakeRef(flakeRefS, {}, true);
     if (evalSettings.pureEval && !flakeRef.input.isImmutable())
         throw Error("cannot call 'getFlake' on mutable flake reference '%s', at %s (use --impure to override)", flakeRefS, pos);
diff --git a/src/libexpr/flake/flakeref.cc b/src/libexpr/flake/flakeref.cc
index c3b74e0fe..930ed9ccd 100644
--- a/src/libexpr/flake/flakeref.cc
+++ b/src/libexpr/flake/flakeref.cc
@@ -122,6 +122,28 @@ std::pair<FlakeRef, std::string> parseFlakeRefWithFragment(
 
             if (isFlake) {
 
+                if (!allowMissing && !pathExists(path + "/flake.nix")){
+                    notice("path '%s' does not contain a 'flake.nix', searching up",path);
+
+                    // Save device to detect filesystem boundary
+                    dev_t device = lstat(path).st_dev;
+                    bool found = false;
+                    while (path != "/") {
+                        if (pathExists(path + "/flake.nix")) {
+                            found = true;
+                            break;
+                        } else if (pathExists(path + "/.git"))
+                            throw Error("path '%s' is not part of a flake (neither it nor its parent directories contain a 'flake.nix' file)", path);
+                        else {
+                            if (lstat(path).st_dev != device)
+                                throw Error("unable to find a flake before encountering filesystem boundary at '%s'", path);
+                        }
+                        path = dirOf(path);
+                    }
+                    if (!found)
+                        throw BadURL("could not find a flake.nix file");
+                }
+
                 if (!S_ISDIR(lstat(path).st_mode))
                     throw BadURL("path '%s' is not a flake (because it's not a directory)", path);
 
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index ed4c47fbb..5995a857b 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -104,10 +104,10 @@ DrvInfo::Outputs DrvInfo::queryOutputs(bool onlyOutputsToInstall)
             /* For each output... */
             for (auto elem : i->value->listItems()) {
                 /* Evaluate the corresponding set. */
-                string name = state->forceStringNoCtx(*elem, *i->pos);
+                string name(state->forceStringNoCtx(*elem, *i->pos));
                 Bindings::iterator out = attrs->find(state->symbols.create(name));
                 if (out == attrs->end()) continue; // FIXME: throw error?
-                state->forceAttrs(*out->value);
+                state->forceAttrs(*out->value, *i->pos);
 
                 /* And evaluate its ‘outPath’ attribute. */
                 Bindings::iterator outPath = out->value->attrs->find(state->sOutPath);
@@ -172,7 +172,7 @@ StringSet DrvInfo::queryMetaNames()
 
 bool DrvInfo::checkMeta(Value & v)
 {
-    state->forceValue(v);
+    state->forceValue(v, [&]() { return v.determinePos(noPos); });
     if (v.type() == nList) {
         for (auto elem : v.listItems())
             if (!checkMeta(*elem)) return false;
@@ -254,15 +254,14 @@ bool DrvInfo::queryMetaBool(const string & name, bool def)
 void DrvInfo::setMeta(const string & name, Value * v)
 {
     getMeta();
-    Bindings * old = meta;
-    meta = state->allocBindings(1 + (old ? old->size() : 0));
+    auto attrs = state->buildBindings(1 + (meta ? meta->size() : 0));
     Symbol sym = state->symbols.create(name);
-    if (old)
-        for (auto i : *old)
+    if (meta)
+        for (auto i : *meta)
             if (i.name != sym)
-                meta->push_back(i);
-    if (v) meta->push_back(Attr(sym, v));
-    meta->sort();
+                attrs.insert(i);
+    if (v) attrs.insert(sym, v);
+    meta = attrs.finish();
 }
 
 
@@ -279,7 +278,7 @@ static bool getDerivation(EvalState & state, Value & v,
     bool ignoreAssertionFailures)
 {
     try {
-        state.forceValue(v);
+        state.forceValue(v, [&]() { return v.determinePos(noPos); });
         if (!state.isDerivation(v)) return true;
 
         /* Remove spurious duplicates (e.g., a set like `rec { x =
diff --git a/src/libexpr/json-to-value.cc b/src/libexpr/json-to-value.cc
index 9ca5ac86d..99a475ff9 100644
--- a/src/libexpr/json-to-value.cc
+++ b/src/libexpr/json-to-value.cc
@@ -37,10 +37,10 @@ class JSONSax : nlohmann::json_sax<json> {
         ValueMap attrs;
         std::unique_ptr<JSONState> resolve(EvalState & state) override
         {
-            Value & v = parent->value(state);
-            state.mkAttrs(v, attrs.size());
+            auto attrs2 = state.buildBindings(attrs.size());
             for (auto & i : attrs)
-                v.attrs->push_back(Attr(i.first, i.second));
+                attrs2.insert(i.first, i.second);
+            parent->value(state).mkAttrs(attrs2.alreadySorted());
             return std::move(parent);
         }
         void add() override { v = nullptr; }
@@ -76,45 +76,51 @@ class JSONSax : nlohmann::json_sax<json> {
     EvalState & state;
     std::unique_ptr<JSONState> rs;
 
-    template<typename T, typename... Args> inline bool handle_value(T f, Args... args)
-    {
-        f(rs->value(state), args...);
-        rs->add();
-        return true;
-    }
-
 public:
     JSONSax(EvalState & state, Value & v) : state(state), rs(new JSONState(&v)) {};
 
     bool null()
     {
-        return handle_value(mkNull);
+        rs->value(state).mkNull();
+        rs->add();
+        return true;
     }
 
     bool boolean(bool val)
     {
-        return handle_value(mkBool, val);
+        rs->value(state).mkBool(val);
+        rs->add();
+        return true;
     }
 
     bool number_integer(number_integer_t val)
     {
-        return handle_value(mkInt, val);
+        rs->value(state).mkInt(val);
+        rs->add();
+        return true;
     }
 
     bool number_unsigned(number_unsigned_t val)
     {
-        return handle_value(mkInt, val);
+        rs->value(state).mkInt(val);
+        rs->add();
+        return true;
     }
 
     bool number_float(number_float_t val, const string_t & s)
     {
-        return handle_value(mkFloat, val);
+        rs->value(state).mkFloat(val);
+        rs->add();
+        return true;
     }
 
     bool string(string_t & val)
     {
-        return handle_value<void(Value&, const char*)>(mkString, val.c_str());
+        rs->value(state).mkString(val);
+        rs->add();
+        return true;
     }
+
 #if NLOHMANN_JSON_VERSION_MAJOR >= 3 && NLOHMANN_JSON_VERSION_MINOR >= 8
     bool binary(binary_t&)
     {
@@ -157,7 +163,7 @@ public:
     }
 };
 
-void parseJSON(EvalState & state, const string & s_, Value & v)
+void parseJSON(EvalState & state, const std::string_view & s_, Value & v)
 {
     JSONSax parser(state, v);
     bool res = json::sax_parse(s_, &parser);
diff --git a/src/libexpr/json-to-value.hh b/src/libexpr/json-to-value.hh
index 3b0fdae11..84bec4eba 100644
--- a/src/libexpr/json-to-value.hh
+++ b/src/libexpr/json-to-value.hh
@@ -8,6 +8,6 @@ namespace nix {
 
 MakeError(JSONParseError, EvalError);
 
-void parseJSON(EvalState & state, const string & s, Value & v);
+void parseJSON(EvalState & state, const std::string_view & s, Value & v);
 
 }
diff --git a/src/libexpr/lexer.l b/src/libexpr/lexer.l
index c18877e29..e276b0467 100644
--- a/src/libexpr/lexer.l
+++ b/src/libexpr/lexer.l
@@ -64,29 +64,32 @@ static void adjustLoc(YYLTYPE * loc, const char * s, size_t len)
 }
 
 
-// FIXME: optimize
-static Expr * unescapeStr(SymbolTable & symbols, const char * s, size_t length)
+// we make use of the fact that the parser receives a private copy of the input
+// string and can munge around in it.
+static StringToken unescapeStr(SymbolTable & symbols, char * s, size_t length)
 {
-    string t;
-    t.reserve(length);
+    char * result = s;
+    char * t = s;
     char c;
+    // the input string is terminated with *two* NULs, so we can safely take
+    // *one* character after the one being checked against.
     while ((c = *s++)) {
         if (c == '\\') {
-            assert(*s);
             c = *s++;
-            if (c == 'n') t += '\n';
-            else if (c == 'r') t += '\r';
-            else if (c == 't') t += '\t';
-            else t += c;
+            if (c == 'n') *t = '\n';
+            else if (c == 'r') *t = '\r';
+            else if (c == 't') *t = '\t';
+            else *t = c;
         }
         else if (c == '\r') {
             /* Normalise CR and CR/LF into LF. */
-            t += '\n';
+            *t = '\n';
             if (*s == '\n') s++; /* cr/lf */
         }
-        else t += c;
+        else *t = c;
+        t++;
     }
-    return new ExprString(symbols.create(t));
+    return {result, size_t(t - result)};
 }
 
 
@@ -139,7 +142,7 @@ or          { return OR_KW; }
 \/\/        { return UPDATE; }
 \+\+        { return CONCAT; }
 
-{ID}        { yylval->id = strdup(yytext); return ID; }
+{ID}        { yylval->id = {yytext, (size_t) yyleng}; return ID; }
 {INT}       { errno = 0;
               try {
                   yylval->n = boost::lexical_cast<int64_t>(yytext);
@@ -173,7 +176,7 @@ or          { return OR_KW; }
                 /* It is impossible to match strings ending with '$' with one
                    regex because trailing contexts are only valid at the end
                    of a rule. (A sane but undocumented limitation.) */
-                yylval->e = unescapeStr(data->symbols, yytext, yyleng);
+                yylval->str = unescapeStr(data->symbols, yytext, yyleng);
                 return STR;
               }
 <STRING>\$\{  { PUSH_STATE(DEFAULT); return DOLLAR_CURLY; }
@@ -188,26 +191,26 @@ or          { return OR_KW; }
 
 \'\'(\ *\n)?     { PUSH_STATE(IND_STRING); return IND_STRING_OPEN; }
 <IND_STRING>([^\$\']|\$[^\{\']|\'[^\'\$])+ {
-                   yylval->e = new ExprIndStr(yytext);
+                   yylval->str = {yytext, (size_t) yyleng, true};
                    return IND_STR;
                  }
 <IND_STRING>\'\'\$ |
 <IND_STRING>\$   {
-                   yylval->e = new ExprIndStr("$");
+                   yylval->str = {"$", 1};
                    return IND_STR;
                  }
 <IND_STRING>\'\'\' {
-                   yylval->e = new ExprIndStr("''");
+                   yylval->str = {"''", 2};
                    return IND_STR;
                  }
 <IND_STRING>\'\'\\{ANY} {
-                   yylval->e = unescapeStr(data->symbols, yytext + 2, yyleng - 2);
+                   yylval->str = unescapeStr(data->symbols, yytext + 2, yyleng - 2);
                    return IND_STR;
                  }
 <IND_STRING>\$\{ { PUSH_STATE(DEFAULT); return DOLLAR_CURLY; }
 <IND_STRING>\'\' { POP_STATE(); return IND_STRING_CLOSE; }
 <IND_STRING>\'   {
-                   yylval->e = new ExprIndStr("'");
+                   yylval->str = {"'", 1};
                    return IND_STR;
                  }
 
@@ -221,14 +224,14 @@ or          { return OR_KW; }
 <PATH_START>{PATH_SEG} {
   POP_STATE();
   PUSH_STATE(INPATH_SLASH);
-  yylval->path = strdup(yytext);
+  yylval->path = {yytext, (size_t) yyleng};
   return PATH;
 }
 
 <PATH_START>{HPATH_START} {
   POP_STATE();
   PUSH_STATE(INPATH_SLASH);
-  yylval->path = strdup(yytext);
+  yylval->path = {yytext, (size_t) yyleng};
   return HPATH;
 }
 
@@ -237,7 +240,7 @@ or          { return OR_KW; }
     PUSH_STATE(INPATH_SLASH);
   else
     PUSH_STATE(INPATH);
-  yylval->path = strdup(yytext);
+  yylval->path = {yytext, (size_t) yyleng};
   return PATH;
 }
 {HPATH} {
@@ -245,7 +248,7 @@ or          { return OR_KW; }
     PUSH_STATE(INPATH_SLASH);
   else
     PUSH_STATE(INPATH);
-  yylval->path = strdup(yytext);
+  yylval->path = {yytext, (size_t) yyleng};
   return HPATH;
 }
 
@@ -261,7 +264,7 @@ or          { return OR_KW; }
       PUSH_STATE(INPATH_SLASH);
   else
       PUSH_STATE(INPATH);
-  yylval->e = new ExprString(data->symbols.create(string(yytext)));
+  yylval->str = {yytext, (size_t) yyleng};
   return STR;
 }
 <INPATH>{ANY} |
@@ -280,8 +283,8 @@ or          { return OR_KW; }
   throw ParseError("path has a trailing slash");
 }
 
-{SPATH}     { yylval->path = strdup(yytext); return SPATH; }
-{URI}       { yylval->uri = strdup(yytext); return URI; }
+{SPATH}     { yylval->path = {yytext, (size_t) yyleng}; return SPATH; }
+{URI}       { yylval->uri = {yytext, (size_t) yyleng}; return URI; }
 
 [ \t\r\n]+    /* eat up whitespace */
 \#[^\r\n]*    /* single-line comments */
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index f7541d32c..41ee92d27 100644
--- a/src/libexpr/nixexpr.cc
+++ b/src/libexpr/nixexpr.cc
@@ -190,7 +190,7 @@ void ExprConcatStrings::show(std::ostream & str) const
     str << "(";
     for (auto & i : *es) {
         if (first) first = false; else str << " + ";
-        str << i.second;
+        str << *i.second;
     }
     str << ")";
 }
@@ -527,7 +527,7 @@ string ExprLambda::showNamePos() const
 size_t SymbolTable::totalSize() const
 {
     size_t n = 0;
-    for (auto & i : symbols)
+    for (auto & i : store)
         n += i.size();
     return n;
 }
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
index 8012c616e..64375b5ab 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -98,7 +98,7 @@ struct ExprInt : Expr
 {
     NixInt n;
     Value v;
-    ExprInt(NixInt n) : n(n) { mkInt(v, n); };
+    ExprInt(NixInt n) : n(n) { v.mkInt(n); };
     Value * maybeThunk(EvalState & state, Env & env);
     Pos* getPos() { return 0; }
     COMMON_METHODS
@@ -108,7 +108,7 @@ struct ExprFloat : Expr
 {
     NixFloat nf;
     Value v;
-    ExprFloat(NixFloat nf) : nf(nf) { mkFloat(v, nf); };
+    ExprFloat(NixFloat nf) : nf(nf) { v.mkFloat(nf); };
     Value * maybeThunk(EvalState & state, Env & env);
     Pos* getPos() { return 0; }
     COMMON_METHODS
@@ -116,22 +116,14 @@ struct ExprFloat : Expr
 
 struct ExprString : Expr
 {
-    Symbol s;
+    string s;
     Value v;
-    ExprString(const Symbol & s) : s(s) { mkString(v, s); };
+    ExprString(std::string s) : s(std::move(s)) { v.mkString(this->s.data()); };
     Value * maybeThunk(EvalState & state, Env & env);
     Pos* getPos() { return 0; }
     COMMON_METHODS
 };
 
-/* Temporary class used during parsing of indented strings. */
-struct ExprIndStr : Expr
-{
-    string s;
-    ExprIndStr(const string & s) : s(s) { };
-    Pos* getPos() { return 0; }
-};
-
 struct ExprPath : Expr
 {
     string s;
@@ -237,10 +229,25 @@ struct Formal
 
 struct Formals
 {
-    typedef std::list<Formal> Formals_;
+    typedef std::vector<Formal> Formals_;
     Formals_ formals;
-    std::set<Symbol> argNames; // used during parsing
     bool ellipsis;
+
+    bool has(Symbol arg) const {
+        auto it = std::lower_bound(formals.begin(), formals.end(), arg,
+            [] (const Formal & f, const Symbol & sym) { return f.name < sym; });
+        return it != formals.end() && it->name == arg;
+    }
+
+    std::vector<Formal> lexicographicOrder() const
+    {
+        std::vector<Formal> result(formals.begin(), formals.end());
+        std::sort(result.begin(), result.end(),
+            [] (const Formal & a, const Formal & b) {
+                return std::string_view(a.name) < std::string_view(b.name);
+            });
+        return result;
+    }
 };
 
 struct ExprLambda : Expr
@@ -253,11 +260,6 @@ struct ExprLambda : Expr
     ExprLambda(const Pos & pos, const Symbol & arg, Formals * formals, Expr * body)
         : pos(pos), arg(arg), formals(formals), body(body)
     {
-        if (!arg.empty() && formals && formals->argNames.find(arg) != formals->argNames.end())
-            throw ParseError({
-                .msg = hintfmt("duplicate formal function argument '%1%'", arg),
-                .errPos = pos
-            });
     };
     void setName(Symbol & name);
     string showNamePos() const;
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index db2d4e204..d9291e7a2 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -16,6 +16,8 @@
 #ifndef BISON_HEADER
 #define BISON_HEADER
 
+#include <variant>
+
 #include "util.hh"
 
 #include "nixexpr.hh"
@@ -40,8 +42,22 @@ namespace nix {
             { };
     };
 
+    struct ParserFormals {
+        std::vector<Formal> formals;
+        bool ellipsis = false;
+    };
+
 }
 
+// using C a struct allows us to avoid having to define the special
+// members that using string_view here would implicitly delete.
+struct StringToken {
+  const char * p;
+  size_t l;
+  bool hasIndentation;
+  operator std::string_view() const { return {p, l}; }
+};
+
 #define YY_DECL int yylex \
     (YYSTYPE * yylval_param, YYLTYPE * yylloc_param, yyscan_t yyscanner, nix::ParseData * data)
 
@@ -141,21 +157,46 @@ static void addAttr(ExprAttrs * attrs, AttrPath & attrPath,
 }
 
 
-static void addFormal(const Pos & pos, Formals * formals, const Formal & formal)
+static Formals * toFormals(ParseData & data, ParserFormals * formals,
+    Pos pos = noPos, Symbol arg = {})
 {
-    if (!formals->argNames.insert(formal.name).second)
+    std::sort(formals->formals.begin(), formals->formals.end(),
+        [] (const auto & a, const auto & b) {
+            return std::tie(a.name, a.pos) < std::tie(b.name, b.pos);
+        });
+
+    std::optional<std::pair<Symbol, Pos>> duplicate;
+    for (size_t i = 0; i + 1 < formals->formals.size(); i++) {
+        if (formals->formals[i].name != formals->formals[i + 1].name)
+            continue;
+        std::pair thisDup{formals->formals[i].name, formals->formals[i + 1].pos};
+        duplicate = std::min(thisDup, duplicate.value_or(thisDup));
+    }
+    if (duplicate)
+        throw ParseError({
+            .msg = hintfmt("duplicate formal function argument '%1%'", duplicate->first),
+            .errPos = duplicate->second
+        });
+
+    Formals result;
+    result.ellipsis = formals->ellipsis;
+    result.formals = std::move(formals->formals);
+
+    if (arg.set() && result.has(arg))
         throw ParseError({
-            .msg = hintfmt("duplicate formal function argument '%1%'",
-                formal.name),
+            .msg = hintfmt("duplicate formal function argument '%1%'", arg),
             .errPos = pos
         });
-    formals->formals.push_front(formal);
+
+    delete formals;
+    return new Formals(std::move(result));
 }
 
 
-static Expr * stripIndentation(const Pos & pos, SymbolTable & symbols, vector<std::pair<Pos, Expr *> > & es)
+static Expr * stripIndentation(const Pos & pos, SymbolTable & symbols,
+    vector<std::pair<Pos, std::variant<Expr *, StringToken> > > & es)
 {
-    if (es.empty()) return new ExprString(symbols.create(""));
+    if (es.empty()) return new ExprString("");
 
     /* Figure out the minimum indentation.  Note that by design
        whitespace-only final lines are not taken into account.  (So
@@ -164,20 +205,20 @@ static Expr * stripIndentation(const Pos & pos, SymbolTable & symbols, vector<st
     size_t minIndent = 1000000;
     size_t curIndent = 0;
     for (auto & [i_pos, i] : es) {
-        ExprIndStr * e = dynamic_cast<ExprIndStr *>(i);
-        if (!e) {
-            /* Anti-quotations end the current start-of-line whitespace. */
+        auto * str = std::get_if<StringToken>(&i);
+        if (!str || !str->hasIndentation) {
+            /* Anti-quotations and escaped characters end the current start-of-line whitespace. */
             if (atStartOfLine) {
                 atStartOfLine = false;
                 if (curIndent < minIndent) minIndent = curIndent;
             }
             continue;
         }
-        for (size_t j = 0; j < e->s.size(); ++j) {
+        for (size_t j = 0; j < str->l; ++j) {
             if (atStartOfLine) {
-                if (e->s[j] == ' ')
+                if (str->p[j] == ' ')
                     curIndent++;
-                else if (e->s[j] == '\n') {
+                else if (str->p[j] == '\n') {
                     /* Empty line, doesn't influence minimum
                        indentation. */
                     curIndent = 0;
@@ -185,7 +226,7 @@ static Expr * stripIndentation(const Pos & pos, SymbolTable & symbols, vector<st
                     atStartOfLine = false;
                     if (curIndent < minIndent) minIndent = curIndent;
                 }
-            } else if (e->s[j] == '\n') {
+            } else if (str->p[j] == '\n') {
                 atStartOfLine = true;
                 curIndent = 0;
             }
@@ -197,33 +238,31 @@ static Expr * stripIndentation(const Pos & pos, SymbolTable & symbols, vector<st
     atStartOfLine = true;
     size_t curDropped = 0;
     size_t n = es.size();
-    for (vector<std::pair<Pos, Expr *> >::iterator i = es.begin(); i != es.end(); ++i, --n) {
-        ExprIndStr * e = dynamic_cast<ExprIndStr *>(i->second);
-        if (!e) {
-            atStartOfLine = false;
-            curDropped = 0;
-            es2->push_back(*i);
-            continue;
-        }
-
+    auto i = es.begin();
+    const auto trimExpr = [&] (Expr * e) {
+        atStartOfLine = false;
+        curDropped = 0;
+        es2->emplace_back(i->first, e);
+    };
+    const auto trimString = [&] (const StringToken & t) {
         string s2;
-        for (size_t j = 0; j < e->s.size(); ++j) {
+        for (size_t j = 0; j < t.l; ++j) {
             if (atStartOfLine) {
-                if (e->s[j] == ' ') {
+                if (t.p[j] == ' ') {
                     if (curDropped++ >= minIndent)
-                        s2 += e->s[j];
+                        s2 += t.p[j];
                 }
-                else if (e->s[j] == '\n') {
+                else if (t.p[j] == '\n') {
                     curDropped = 0;
-                    s2 += e->s[j];
+                    s2 += t.p[j];
                 } else {
                     atStartOfLine = false;
                     curDropped = 0;
-                    s2 += e->s[j];
+                    s2 += t.p[j];
                 }
             } else {
-                s2 += e->s[j];
-                if (e->s[j] == '\n') atStartOfLine = true;
+                s2 += t.p[j];
+                if (t.p[j] == '\n') atStartOfLine = true;
             }
         }
 
@@ -235,7 +274,10 @@ static Expr * stripIndentation(const Pos & pos, SymbolTable & symbols, vector<st
                 s2 = string(s2, 0, p + 1);
         }
 
-        es2->emplace_back(i->first, new ExprString(symbols.create(s2)));
+        es2->emplace_back(i->first, new ExprString(s2));
+    };
+    for (; i != es.end(); ++i, --n) {
+        std::visit(overloaded { trimExpr, trimString }, i->second);
     }
 
     /* If this is a single string, then don't do a concatenation. */
@@ -270,15 +312,17 @@ void yyerror(YYLTYPE * loc, yyscan_t scanner, ParseData * data, const char * err
   nix::Expr * e;
   nix::ExprList * list;
   nix::ExprAttrs * attrs;
-  nix::Formals * formals;
+  nix::ParserFormals * formals;
   nix::Formal * formal;
   nix::NixInt n;
   nix::NixFloat nf;
-  const char * id; // !!! -> Symbol
-  char * path;
-  char * uri;
+  StringToken id; // !!! -> Symbol
+  StringToken path;
+  StringToken uri;
+  StringToken str;
   std::vector<nix::AttrName> * attrNames;
   std::vector<std::pair<nix::Pos, nix::Expr *> > * string_parts;
+  std::vector<std::pair<nix::Pos, std::variant<nix::Expr *, StringToken> > > * ind_string_parts;
 }
 
 %type <e> start expr expr_function expr_if expr_op
@@ -288,11 +332,12 @@ void yyerror(YYLTYPE * loc, yyscan_t scanner, ParseData * data, const char * err
 %type <formals> formals
 %type <formal> formal
 %type <attrNames> attrs attrpath
-%type <string_parts> string_parts_interpolated ind_string_parts
+%type <string_parts> string_parts_interpolated
+%type <ind_string_parts> ind_string_parts
 %type <e> path_start string_parts string_attr
 %type <id> attr
 %token <id> ID ATTRPATH
-%token <e> STR IND_STR
+%token <str> STR IND_STR
 %token <n> INT
 %token <nf> FLOAT
 %token <path> PATH HPATH SPATH PATH_END
@@ -325,11 +370,17 @@ expr_function
   : ID ':' expr_function
     { $$ = new ExprLambda(CUR_POS, data->symbols.create($1), 0, $3); }
   | '{' formals '}' ':' expr_function
-    { $$ = new ExprLambda(CUR_POS, data->symbols.create(""), $2, $5); }
+    { $$ = new ExprLambda(CUR_POS, data->symbols.create(""), toFormals(*data, $2), $5); }
   | '{' formals '}' '@' ID ':' expr_function
-    { $$ = new ExprLambda(CUR_POS, data->symbols.create($5), $2, $7); }
+    {
+      Symbol arg = data->symbols.create($5);
+      $$ = new ExprLambda(CUR_POS, arg, toFormals(*data, $2, CUR_POS, arg), $7);
+    }
   | ID '@' '{' formals '}' ':' expr_function
-    { $$ = new ExprLambda(CUR_POS, data->symbols.create($1), $4, $7); }
+    {
+      Symbol arg = data->symbols.create($1);
+      $$ = new ExprLambda(CUR_POS, arg, toFormals(*data, $4, CUR_POS, arg), $7);
+    }
   | ASSERT expr ';' expr_function
     { $$ = new ExprAssert(CUR_POS, $2, $4); }
   | WITH expr ';' expr_function
@@ -398,7 +449,8 @@ expr_select
 
 expr_simple
   : ID {
-      if (strcmp($1, "__curPos") == 0)
+      std::string_view s = "__curPos";
+      if ($1.l == s.size() && strncmp($1.p, s.data(), s.size()) == 0)
           $$ = new ExprPos(CUR_POS);
       else
           $$ = new ExprVar(CUR_POS, data->symbols.create($1));
@@ -415,11 +467,11 @@ expr_simple
       $$ = new ExprConcatStrings(CUR_POS, false, $2);
   }
   | SPATH {
-      string path($1 + 1, strlen($1) - 2);
+      string path($1.p + 1, $1.l - 2);
       $$ = new ExprCall(CUR_POS,
           new ExprVar(data->symbols.create("__findFile")),
           {new ExprVar(data->symbols.create("__nixPath")),
-           new ExprString(data->symbols.create(path))});
+           new ExprString(path)});
   }
   | URI {
       static bool noURLLiterals = settings.isExperimentalFeatureEnabled(Xp::NoUrlLiterals);
@@ -428,7 +480,7 @@ expr_simple
               .msg = hintfmt("URL literals are disabled"),
               .errPos = CUR_POS
           });
-      $$ = new ExprString(data->symbols.create($1));
+      $$ = new ExprString(string($1));
   }
   | '(' expr ')' { $$ = $2; }
   /* Let expressions `let {..., body = ...}' are just desugared
@@ -443,32 +495,33 @@ expr_simple
   ;
 
 string_parts
-  : STR
+  : STR { $$ = new ExprString(string($1)); }
   | string_parts_interpolated { $$ = new ExprConcatStrings(CUR_POS, true, $1); }
-  | { $$ = new ExprString(data->symbols.create("")); }
+  | { $$ = new ExprString(""); }
   ;
 
 string_parts_interpolated
-  : string_parts_interpolated STR { $$ = $1; $1->emplace_back(makeCurPos(@2, data), $2); }
+  : string_parts_interpolated STR
+  { $$ = $1; $1->emplace_back(makeCurPos(@2, data), new ExprString(string($2))); }
   | string_parts_interpolated DOLLAR_CURLY expr '}' { $$ = $1; $1->emplace_back(makeCurPos(@2, data), $3); }
   | DOLLAR_CURLY expr '}' { $$ = new vector<std::pair<Pos, Expr *> >; $$->emplace_back(makeCurPos(@1, data), $2); }
   | STR DOLLAR_CURLY expr '}' {
       $$ = new vector<std::pair<Pos, Expr *> >;
-      $$->emplace_back(makeCurPos(@1, data), $1);
+      $$->emplace_back(makeCurPos(@1, data), new ExprString(string($1)));
       $$->emplace_back(makeCurPos(@2, data), $3);
     }
   ;
 
 path_start
   : PATH {
-    Path path(absPath($1, data->basePath));
+    Path path(absPath({$1.p, $1.l}, data->basePath));
     /* add back in the trailing '/' to the first segment */
-    if ($1[strlen($1)-1] == '/' && strlen($1) > 1)
+    if ($1.p[$1.l-1] == '/' && $1.l > 1)
       path += "/";
     $$ = new ExprPath(path);
   }
   | HPATH {
-    Path path(getHome() + string($1 + 1));
+    Path path(getHome() + string($1.p + 1, $1.l - 1));
     $$ = new ExprPath(path);
   }
   ;
@@ -476,7 +529,7 @@ path_start
 ind_string_parts
   : ind_string_parts IND_STR { $$ = $1; $1->emplace_back(makeCurPos(@2, data), $2); }
   | ind_string_parts DOLLAR_CURLY expr '}' { $$ = $1; $1->emplace_back(makeCurPos(@2, data), $3); }
-  | { $$ = new vector<std::pair<Pos, Expr *> >; }
+  | { $$ = new vector<std::pair<Pos, std::variant<Expr *, StringToken> > >; }
   ;
 
 binds
@@ -508,7 +561,7 @@ attrs
     { $$ = $1;
       ExprString * str = dynamic_cast<ExprString *>($2);
       if (str) {
-          $$->push_back(AttrName(str->s));
+          $$->push_back(AttrName(data->symbols.create(str->s)));
           delete str;
       } else
           throw ParseError({
@@ -525,7 +578,7 @@ attrpath
     { $$ = $1;
       ExprString * str = dynamic_cast<ExprString *>($3);
       if (str) {
-          $$->push_back(AttrName(str->s));
+          $$->push_back(AttrName(data->symbols.create(str->s)));
           delete str;
       } else
           $$->push_back(AttrName($3));
@@ -535,7 +588,7 @@ attrpath
     { $$ = new vector<AttrName>;
       ExprString *str = dynamic_cast<ExprString *>($1);
       if (str) {
-          $$->push_back(AttrName(str->s));
+          $$->push_back(AttrName(data->symbols.create(str->s)));
           delete str;
       } else
           $$->push_back(AttrName($1));
@@ -544,7 +597,7 @@ attrpath
 
 attr
   : ID { $$ = $1; }
-  | OR_KW { $$ = "or"; }
+  | OR_KW { $$ = {"or", 2}; }
   ;
 
 string_attr
@@ -559,13 +612,13 @@ expr_list
 
 formals
   : formal ',' formals
-    { $$ = $3; addFormal(CUR_POS, $$, *$1); }
+    { $$ = $3; $$->formals.push_back(*$1); }
   | formal
-    { $$ = new Formals; addFormal(CUR_POS, $$, *$1); $$->ellipsis = false; }
+    { $$ = new ParserFormals; $$->formals.push_back(*$1); $$->ellipsis = false; }
   |
-    { $$ = new Formals; $$->ellipsis = false; }
+    { $$ = new ParserFormals; $$->ellipsis = false; }
   | ELLIPSIS
-    { $$ = new Formals; $$->ellipsis = true; }
+    { $$ = new ParserFormals; $$->ellipsis = true; }
   ;
 
 formal
@@ -590,8 +643,8 @@ formal
 namespace nix {
 
 
-Expr * EvalState::parse(const char * text, FileOrigin origin,
-    const Path & path, const Path & basePath, std::shared_ptr<StaticEnv> & staticEnv)
+Expr * EvalState::parse(char * text, size_t length, FileOrigin origin,
+    const PathView path, const PathView basePath, std::shared_ptr<StaticEnv> & staticEnv)
 {
     yyscan_t scanner;
     ParseData data(*this);
@@ -610,7 +663,7 @@ Expr * EvalState::parse(const char * text, FileOrigin origin,
     data.basePath = basePath;
 
     yylex_init(&scanner);
-    yy_scan_string(text, scanner);
+    yy_scan_buffer(text, length, scanner);
     int res = yyparse(scanner, &data);
     yylex_destroy(scanner);
 
@@ -656,26 +709,33 @@ Expr * EvalState::parseExprFromFile(const Path & path)
 
 Expr * EvalState::parseExprFromFile(const Path & path, std::shared_ptr<StaticEnv> & staticEnv)
 {
-    return parse(readFile(path).c_str(), foFile, path, dirOf(path), staticEnv);
+    auto buffer = readFile(path);
+    // readFile should have left some extra space for terminators
+    buffer.append("\0\0", 2);
+    return parse(buffer.data(), buffer.size(), foFile, path, dirOf(path), staticEnv);
 }
 
 
-Expr * EvalState::parseExprFromString(std::string_view s, const Path & basePath, std::shared_ptr<StaticEnv> & staticEnv)
+Expr * EvalState::parseExprFromString(std::string s, const Path & basePath, std::shared_ptr<StaticEnv> & staticEnv)
 {
-    return parse(s.data(), foString, "", basePath, staticEnv);
+    s.append("\0\0", 2);
+    return parse(s.data(), s.size(), foString, "", basePath, staticEnv);
 }
 
 
-Expr * EvalState::parseExprFromString(std::string_view s, const Path & basePath)
+Expr * EvalState::parseExprFromString(std::string s, const Path & basePath)
 {
-    return parseExprFromString(s, basePath, staticBaseEnv);
+    return parseExprFromString(std::move(s), basePath, staticBaseEnv);
 }
 
 
 Expr * EvalState::parseStdin()
 {
     //Activity act(*logger, lvlTalkative, format("parsing standard input"));
-    return parse(drainFD(0).data(), foStdin, "", absPath("."), staticBaseEnv);
+    auto buffer = drainFD(0);
+    // drainFD should have left some extra space for terminators
+    buffer.append("\0\0", 2);
+    return parse(buffer.data(), buffer.size(), foStdin, "", absPath("."), staticBaseEnv);
 }
 
 
@@ -695,24 +755,24 @@ void EvalState::addToSearchPath(const string & s)
 }
 
 
-Path EvalState::findFile(const string & path)
+Path EvalState::findFile(const std::string_view path)
 {
     return findFile(searchPath, path);
 }
 
 
-Path EvalState::findFile(SearchPath & searchPath, const string & path, const Pos & pos)
+Path EvalState::findFile(SearchPath & searchPath, const std::string_view path, const Pos & pos)
 {
     for (auto & i : searchPath) {
         std::string suffix;
         if (i.first.empty())
-            suffix = "/" + path;
+            suffix = concatStrings("/", path);
         else {
             auto s = i.first.size();
             if (path.compare(0, s, i.first) != 0 ||
                 (path.size() > s && path[s] != '/'))
                 continue;
-            suffix = path.size() == s ? "" : "/" + string(path, s);
+            suffix = path.size() == s ? "" : concatStrings("/", path.substr(s));
         }
         auto r = resolveSearchPathElem(i);
         if (!r.first) continue;
@@ -721,7 +781,7 @@ Path EvalState::findFile(SearchPath & searchPath, const string & path, const Pos
     }
 
     if (hasPrefix(path, "nix/"))
-        return corepkgsPrefix + path.substr(4);
+        return concatStrings(corepkgsPrefix, path.substr(4));
 
     throw ThrownError({
         .msg = hintfmt(evalSettings.pureEval
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 48a10cd27..3b429f328 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>
@@ -90,8 +92,6 @@ StringMap EvalState::realiseContext(const PathSet & context)
 }
 
 struct RealisePathFlags {
-    // Whether to check whether the path is a valid absolute path
-    bool requireAbsolutePath = true;
     // Whether to check that the path is allowed in pure eval mode
     bool checkForPureEval = true;
 };
@@ -100,17 +100,28 @@ static Path realisePath(EvalState & state, const Pos & pos, Value & v, const Rea
 {
     PathSet context;
 
-    Path path = flags.requireAbsolutePath
-        ? state.coerceToPath(pos, v, context)
-        : state.coerceToString(pos, v, context, false, false);
+    auto path = [&]()
+    {
+        try {
+            return state.coerceToPath(pos, v, context);
+        } catch (Error & e) {
+            e.addTrace(pos, "while realising the context of a path");
+            throw;
+        }
+    }();
 
-    StringMap rewrites = state.realiseContext(context);
+    try {
+        StringMap rewrites = state.realiseContext(context);
 
-    auto realPath = state.toRealPath(rewriteStrings(path, rewrites), context);
+        auto realPath = state.toRealPath(rewriteStrings(path, rewrites), context);
 
-    return flags.checkForPureEval
-        ? state.checkSourcePath(realPath)
-        : realPath;
+        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
@@ -125,13 +136,15 @@ static Path realisePath(EvalState & state, const Pos & pos, Value & v, const Rea
    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<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
@@ -146,18 +159,7 @@ static void mkOutputString(EvalState & state, Value & v,
    argument. */
 static void import(EvalState & state, const Pos & pos, Value & vPath, Value * vScope, Value & v)
 {
-    Path path;
-    try {
-        path = realisePath(state, pos, vPath);
-    } 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;
-    }
+    auto path = realisePath(state, pos, vPath);
 
     // FIXME
     auto isValidDerivationInStore = [&]() -> std::optional<StorePath> {
@@ -172,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());
@@ -198,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);
     }
 
@@ -212,7 +210,7 @@ static void import(EvalState & state, const Pos & pos, Value & vPath, Value * vS
         if (!vScope)
             state.evalFile(path, v);
         else {
-            state.forceAttrs(*vScope);
+            state.forceAttrs(*vScope, pos);
 
             Env * env = &state.allocEnv(vScope->attrs->size());
             env->up = &state.baseEnv;
@@ -314,20 +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)
 {
-    Path path;
-    try {
-        path = realisePath(state, pos, *args[0]);
-    } 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;
-    }
+    auto path = realisePath(state, pos, *args[0]);
 
-    string sym = state.forceStringNoCtx(*args[1], pos);
+    string sym(state.forceStringNoCtx(*args[1], pos));
 
     void *handle = dlopen(path.c_str(), RTLD_LAZY | RTLD_LOCAL);
     if (!handle)
@@ -363,10 +350,11 @@ 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));
+    for (unsigned int i = 1; i < args[0]->listSize(); ++i) {
+        commandArgs.push_back(state.coerceToString(pos, *elems[i], context, false, false).toOwned());
+    }
     try {
         auto _ = state.realiseContext(context); // FIXME: Handle CA derivations
     } catch (InvalidPathError & e) {
@@ -380,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;
@@ -414,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({
@@ -432,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({
@@ -452,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({
@@ -468,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({
@@ -484,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({
@@ -500,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({
@@ -516,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({
@@ -532,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({
@@ -594,16 +582,16 @@ typedef list<Value *> ValueList;
 
 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
         );
 
@@ -637,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
     );
@@ -652,7 +640,7 @@ static void prim_genericClosure(EvalState & state, const Pos & pos, Value * * ar
     Bindings::iterator op = getAttr(
         state,
         "genericClosure",
-        "operator",
+        state.sOperator,
         args[0]->attrs,
         pos
     );
@@ -674,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"),
@@ -687,7 +675,7 @@ 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. */
@@ -745,7 +733,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);
+        string s = state.coerceToString(pos, *args[0], context).toOwned();
         throw Abort("evaluation aborted with the following error message: '%1%'", s);
     }
 });
@@ -763,7 +751,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);
+      string s = state.coerceToString(pos, *args[0], context).toOwned();
       throw ThrownError(s);
     }
 });
@@ -775,7 +763,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;
     }
 }
@@ -789,7 +777,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({
@@ -808,7 +796,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({
@@ -828,16 +816,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({
@@ -864,8 +852,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(""));
+    string name(state.forceStringNoCtx(*args[0], pos));
+    v.mkString(evalSettings.restrictEval || evalSettings.pureEval ? "" : getEnv(name).value_or(""));
 }
 
 static RegisterPrimOp primop_getEnv({
@@ -1014,7 +1002,7 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
         const 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
@@ -1069,7 +1057,7 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
             else if (i->name == state.sArgs) {
                 state.forceList(*i->value, pos);
                 for (auto elem : i->value->listItems()) {
-                    string s = state.coerceToString(posDrvName, *elem, context, true);
+                    string s = state.coerceToString(posDrvName, *elem, context, true).toOwned();
                     drv.args.push_back(s);
                 }
             }
@@ -1105,12 +1093,12 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
                     }
 
                 } 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));
@@ -1218,7 +1206,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,
                 },
             });
         }
@@ -1291,11 +1279,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 {
@@ -1308,12 +1296,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({
@@ -1338,7 +1326,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({
@@ -1382,7 +1370,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({
@@ -1405,31 +1393,21 @@ static RegisterPrimOp primop_storePath({
 
 static void prim_pathExists(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    Path path;
-    try {
-        // 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)
-        path = realisePath(state, pos, *args[0], { .checkForPureEval = false });
-    } 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);
     }
 }
 
@@ -1448,7 +1426,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({
@@ -1468,8 +1446,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({
@@ -1486,19 +1465,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)
 {
-    Path path;
-    try {
-        path = realisePath(state, pos, *args[0]);
-    } 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]);
     string s = readFile(path);
     if (s.find((char) 0) != 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({
@@ -1522,22 +1501,24 @@ static void prim_findFile(EvalState & state, const Pos & pos, Value * * args, Va
         state.forceAttrs(*v2, pos);
 
         string prefix;
-        Bindings::iterator i = v2->attrs->find(state.symbols.create("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",
+            state.sPath,
             v2->attrs,
             pos
         );
 
-        Path path;
+        PathSet context;
+        string path = state.coerceToString(pos, *i->value, context, false, false).toOwned();
 
         try {
-            path = realisePath(state, pos, *i->value, { .requireAbsolutePath = false });
+            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),
@@ -1545,12 +1526,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 {
@@ -1562,7 +1544,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({
@@ -1570,14 +1552,9 @@ static void prim_hashFile(EvalState & state, const Pos & pos, Value * * args, Va
             .errPos = pos
         });
 
-    Path path;
-    try {
-        path = realisePath(state, pos, *args[1]);
-    } 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, path).to_string(Base16, false));
+    v.mkString(hashFile(*ht, path).to_string(Base16, false));
 }
 
 static RegisterPrimOp primop_hashFile({
@@ -1594,31 +1571,23 @@ static RegisterPrimOp primop_hashFile({
 /* Read a directory (without . or ..) */
 static void prim_readDir(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    Path path;
-    try {
-        path = realisePath(state, pos, *args[0]);
-    } 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(path);
-    state.mkAttrs(v, entries.size());
+
+    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({
@@ -1654,7 +1623,7 @@ 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, pos);
-    mkString(v, out.str(), context);
+    v.mkString(out.str(), context);
 }
 
 static RegisterPrimOp primop_toXML({
@@ -1762,7 +1731,7 @@ static void prim_toJSON(EvalState & state, const Pos & pos, Value * * args, Valu
     std::ostringstream out;
     PathSet context;
     printValueAsJSON(state, true, *args[0], pos, out, context);
-    mkString(v, out.str(), context);
+    v.mkString(out.str(), context);
 }
 
 static RegisterPrimOp primop_toJSON({
@@ -1782,7 +1751,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) {
@@ -1811,8 +1780,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);
+    string name(state.forceStringNoCtx(*args[0], pos));
+    string contents(state.forceString(*args[1], context, pos));
 
     StorePathSet refs;
 
@@ -1836,7 +1805,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({
@@ -1937,10 +1906,13 @@ static void addPath(
         StorePathSet refs;
 
         if (state.store->isInStore(path)) {
-            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;
+            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
@@ -1953,10 +1925,10 @@ 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);
+            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" :
@@ -1983,7 +1955,7 @@ static void addPath(
         } else
             dstPath = state.store->printStorePath(*expectedStorePath);
 
-        mkString(v, dstPath, {dstPath});
+        v.mkString(dstPath, {dstPath});
 
         state.allowPath(dstPath);
 
@@ -2157,7 +2129,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; });
@@ -2187,7 +2159,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;
@@ -2206,13 +2181,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
     );
@@ -2237,11 +2211,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);
 }
@@ -2255,9 +2229,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({
@@ -2275,7 +2249,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({
@@ -2292,21 +2266,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;
+    /* 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.insert(state.symbols.create(elem->string.s));
+        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.count(i.name))
-            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({
@@ -2328,13 +2307,13 @@ 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;
 
@@ -2349,7 +2328,7 @@ static void prim_listToAttrs(EvalState & state, const Pos & pos, Value * * args,
             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) {
@@ -2360,11 +2339,11 @@ static void prim_listToAttrs(EvalState & state, const Pos & pos, Value * * args,
                 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({
@@ -2397,13 +2376,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({
@@ -2457,7 +2438,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())
@@ -2467,18 +2448,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({
@@ -2503,15 +2481,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({
@@ -2529,6 +2509,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
@@ -2539,7 +2604,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({
@@ -2637,8 +2702,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({
@@ -2707,7 +2772,7 @@ static void prim_elem(EvalState & state, const Pos & pos, Value * * args, Value
             res = true;
             break;
         }
-    mkBool(v, res);
+    v.mkBool(res);
 }
 
 static RegisterPrimOp primop_elem({
@@ -2740,7 +2805,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({
@@ -2797,12 +2862,12 @@ static void anyOrAll(bool any, EvalState & state, const Pos & pos, Value * * arg
         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);
 }
 
 
@@ -2849,9 +2914,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);
     }
 }
 
@@ -2945,21 +3010,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({
@@ -2995,20 +3060,22 @@ static void prim_groupBy(EvalState & state, const Pos & pos, Value * * args, Val
     for (auto vElem : args[1]->listItems()) {
         Value res;
         state.callFunction(*args[0], *vElem, res, pos);
-        string name = state.forceStringNoCtx(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);
     }
 
-    state.mkAttrs(v, attrs.size());
+    auto attrs2 = state.buildBindings(attrs.size());
 
     for (auto & i : attrs) {
-        Value * list = state.allocAttr(v, i.first);
+        auto & list = attrs2.alloc(i.first);
         auto size = i.second.size();
-        state.mkList(*list, size);
-        memcpy(list->listElems(), i.second.data(), sizeof(Value *) * size);
+        state.mkList(list, size);
+        memcpy(list.listElems(), i.second.data(), sizeof(Value *) * size);
     }
+
+    v.mkAttrs(attrs2.alreadySorted());
 }
 
 static RegisterPrimOp primop_groupBy({
@@ -3087,9 +3154,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({
@@ -3106,9 +3173,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({
@@ -3125,9 +3192,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({
@@ -3152,7 +3219,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);
@@ -3163,7 +3230,7 @@ static void prim_div(EvalState & state, const Pos & pos, Value * * args, Value &
                 .errPos = pos
             });
 
-        mkInt(v, i1 / i2);
+        v.mkInt(i1 / i2);
     }
 }
 
@@ -3178,7 +3245,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({
@@ -3192,7 +3259,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({
@@ -3206,7 +3273,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({
@@ -3223,7 +3290,7 @@ static void prim_lessThan(EvalState & state, const Pos & pos, Value * * args, Va
     state.forceValue(*args[0], pos);
     state.forceValue(*args[1], pos);
     CompareValues comp{state};
-    mkBool(v, comp(args[0], args[1]));
+    v.mkBool(comp(args[0], args[1]));
 }
 
 static RegisterPrimOp primop_lessThan({
@@ -3249,8 +3316,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({
@@ -3286,7 +3353,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({
@@ -3294,7 +3361,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({
@@ -3320,8 +3387,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({
@@ -3337,7 +3404,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({
@@ -3346,9 +3413,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({
@@ -3364,7 +3431,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()
@@ -3378,16 +3456,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;
         }
 
@@ -3396,9 +3472,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) {
@@ -3455,58 +3531,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) {
@@ -3575,10 +3648,10 @@ static void prim_concatStringsSep(EvalState & state, const Pos & pos, Value * *
 
     for (auto elem : args[1]->listItems()) {
         if (first) first = false; else res += sep;
-        res += state.coerceToString(pos, *elem, context);
+        res += *state.coerceToString(pos, *elem, context);
     }
 
-    mkString(v, res, context);
+    v.mkString(res, context);
 }
 
 static RegisterPrimOp primop_concatStringsSep({
@@ -3605,14 +3678,14 @@ static void prim_replaceStrings(EvalState & state, const Pos & pos, Value * * ar
     vector<string> from;
     from.reserve(args[0]->listSize());
     for (auto elem : args[0]->listItems())
-        from.push_back(state.forceString(*elem, pos));
+        from.emplace_back(state.forceString(*elem, pos));
 
     vector<std::pair<string, PathSet>> to;
     to.reserve(args[1]->listSize());
     for (auto elem : args[1]->listItems()) {
         PathSet ctx;
         auto s = state.forceString(*elem, ctx, pos);
-        to.push_back(std::make_pair(std::move(s), std::move(ctx)));
+        to.emplace_back(s, std::move(ctx));
     }
 
     PathSet context;
@@ -3647,7 +3720,7 @@ static void prim_replaceStrings(EvalState & state, const Pos & pos, Value * * ar
         }
     }
 
-    mkString(v, res, context);
+    v.mkString(res, context);
 }
 
 static RegisterPrimOp primop_replaceStrings({
@@ -3674,12 +3747,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({
@@ -3698,9 +3771,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({
@@ -3718,21 +3791,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({
@@ -3782,37 +3852,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, 6);
+    v.mkInt(6);
     addConstant("__langVersion", v);
 
     // Miscellaneous
@@ -3825,11 +3895,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);
 
@@ -3857,9 +3926,12 @@ void EvalState::createBaseEnv()
 
     /* Note: we have to initialize the 'derivation' constant *after*
        building baseEnv/staticBaseEnv because it uses 'builtins'. */
-    eval(parse(
+    char code[] =
         #include "primops/derivation.nix.gen.hh"
-        , foFile, sDerivationNix, "/", staticBaseEnv), *vDerivation);
+        // 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);
 }
 
 
diff --git a/src/libexpr/primops/context.cc b/src/libexpr/primops/context.cc
index 20545afd0..654251c23 100644
--- a/src/libexpr/primops/context.cc
+++ b/src/libexpr/primops/context.cc
@@ -7,8 +7,8 @@ namespace nix {
 static void prim_unsafeDiscardStringContext(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     PathSet context;
-    string s = state.coerceToString(pos, *args[0], context);
-    mkString(v, s, PathSet());
+    auto s = state.coerceToString(pos, *args[0], context);
+    v.mkString(*s);
 }
 
 static RegisterPrimOp primop_unsafeDiscardStringContext("__unsafeDiscardStringContext", 1, prim_unsafeDiscardStringContext);
@@ -18,7 +18,7 @@ static void prim_hasContext(EvalState & state, const Pos & pos, Value * * args,
 {
     PathSet context;
     state.forceString(*args[0], context, pos);
-    mkBool(v, !context.empty());
+    v.mkBool(!context.empty());
 }
 
 static RegisterPrimOp primop_hasContext("__hasContext", 1, prim_hasContext);
@@ -33,13 +33,13 @@ static RegisterPrimOp primop_hasContext("__hasContext", 1, prim_hasContext);
 static void prim_unsafeDiscardOutputDependency(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);
 
     PathSet context2;
     for (auto & p : context)
         context2.insert(p.at(0) == '=' ? string(p, 1) : p);
 
-    mkString(v, s, context2);
+    v.mkString(*s, context2);
 }
 
 static RegisterPrimOp primop_unsafeDiscardOutputDependency("__unsafeDiscardOutputDependency", 1, prim_unsafeDiscardOutputDependency);
@@ -103,27 +103,26 @@ static void prim_getContext(EvalState & state, const Pos & pos, Value * * args,
         }
     }
 
-    state.mkAttrs(v, contextInfos.size());
+    auto attrs = state.buildBindings(contextInfos.size());
 
     auto sPath = state.symbols.create("path");
     auto sAllOutputs = state.symbols.create("allOutputs");
     for (const auto & info : contextInfos) {
-        auto & infoVal = *state.allocAttr(v, state.symbols.create(info.first));
-        state.mkAttrs(infoVal, 3);
+        auto infoAttrs = state.buildBindings(3);
         if (info.second.path)
-            mkBool(*state.allocAttr(infoVal, sPath), true);
+            infoAttrs.alloc(sPath).mkBool(true);
         if (info.second.allOutputs)
-            mkBool(*state.allocAttr(infoVal, sAllOutputs), true);
+            infoAttrs.alloc(sAllOutputs).mkBool(true);
         if (!info.second.outputs.empty()) {
-            auto & outputsVal = *state.allocAttr(infoVal, state.sOutputs);
+            auto & outputsVal = infoAttrs.alloc(state.sOutputs);
             state.mkList(outputsVal, info.second.outputs.size());
-            size_t i = 0;
-            for (const auto & output : info.second.outputs)
-                mkString(*(outputsVal.listElems()[i++] = state.allocValue()), output);
+            for (const auto & [i, output] : enumerate(info.second.outputs))
+                (outputsVal.listElems()[i] = state.allocValue())->mkString(output);
         }
-        infoVal.attrs->sort();
+        attrs.alloc(info.first).mkAttrs(infoAttrs);
     }
-    v.attrs->sort();
+
+    v.mkAttrs(attrs);
 }
 
 static RegisterPrimOp primop_getContext("__getContext", 1, prim_getContext);
@@ -182,12 +181,12 @@ static void prim_appendContext(EvalState & state, const Pos & pos, Value * * arg
             }
             for (auto elem : iter->value->listItems()) {
                 auto name = state.forceStringNoCtx(*elem, *iter->pos);
-                context.insert("!" + name + "!" + string(i.name));
+                context.insert(concatStrings("!", name, "!", i.name));
             }
         }
     }
 
-    mkString(v, orig, context);
+    v.mkString(orig, context);
 }
 
 static RegisterPrimOp primop_appendContext("__appendContext", 2, prim_appendContext);
diff --git a/src/libexpr/primops/fetchMercurial.cc b/src/libexpr/primops/fetchMercurial.cc
index c23480853..c4e1a7bf0 100644
--- a/src/libexpr/primops/fetchMercurial.cc
+++ b/src/libexpr/primops/fetchMercurial.cc
@@ -12,7 +12,7 @@ static void prim_fetchMercurial(EvalState & state, const Pos & pos, Value * * ar
     std::string url;
     std::optional<Hash> rev;
     std::optional<std::string> ref;
-    std::string name = "source";
+    std::string_view name = "source";
     PathSet context;
 
     state.forceValue(*args[0], pos);
@@ -22,14 +22,14 @@ static void prim_fetchMercurial(EvalState & state, const Pos & pos, Value * * ar
         state.forceAttrs(*args[0], pos);
 
         for (auto & attr : *args[0]->attrs) {
-            string n(attr.name);
+            std::string_view n(attr.name);
             if (n == "url")
-                url = state.coerceToString(*attr.pos, *attr.value, context, false, false);
+                url = state.coerceToString(*attr.pos, *attr.value, context, false, false).toOwned();
             else if (n == "rev") {
                 // Ugly: unlike fetchGit, here the "rev" attribute can
                 // be both a revision or a branch/tag name.
                 auto value = state.forceStringNoCtx(*attr.value, *attr.pos);
-                if (std::regex_match(value, revRegex))
+                if (std::regex_match(value.begin(), value.end(), revRegex))
                     rev = Hash::parseAny(value, htSHA1);
                 else
                     ref = value;
@@ -50,7 +50,7 @@ static void prim_fetchMercurial(EvalState & state, const Pos & pos, Value * * ar
             });
 
     } else
-        url = state.coerceToString(pos, *args[0], context, false, false);
+        url = state.coerceToString(pos, *args[0], context, false, false).toOwned();
 
     // FIXME: git externals probably can be used to bypass the URI
     // whitelist. Ah well.
@@ -62,7 +62,7 @@ static void prim_fetchMercurial(EvalState & state, const Pos & pos, Value * * ar
     fetchers::Attrs attrs;
     attrs.insert_or_assign("type", "hg");
     attrs.insert_or_assign("url", url.find("://") != std::string::npos ? url : "file://" + url);
-    attrs.insert_or_assign("name", name);
+    attrs.insert_or_assign("name", string(name));
     if (ref) attrs.insert_or_assign("ref", *ref);
     if (rev) attrs.insert_or_assign("rev", rev->gitRev());
     auto input = fetchers::Input::fromAttrs(std::move(attrs));
@@ -70,19 +70,19 @@ static void prim_fetchMercurial(EvalState & state, const Pos & pos, Value * * ar
     // FIXME: use name
     auto [tree, input2] = input.fetch(state.store);
 
-    state.mkAttrs(v, 8);
+    auto attrs2 = state.buildBindings(8);
     auto storePath = state.store->printStorePath(tree.storePath);
-    mkString(*state.allocAttr(v, state.sOutPath), storePath, PathSet({storePath}));
+    attrs2.alloc(state.sOutPath).mkString(storePath, {storePath});
     if (input2.getRef())
-        mkString(*state.allocAttr(v, state.symbols.create("branch")), *input2.getRef());
+        attrs2.alloc("branch").mkString(*input2.getRef());
     // Backward compatibility: set 'rev' to
     // 0000000000000000000000000000000000000000 for a dirty tree.
     auto rev2 = input2.getRev().value_or(Hash(htSHA1));
-    mkString(*state.allocAttr(v, state.symbols.create("rev")), rev2.gitRev());
-    mkString(*state.allocAttr(v, state.symbols.create("shortRev")), std::string(rev2.gitRev(), 0, 12));
+    attrs2.alloc("rev").mkString(rev2.gitRev());
+    attrs2.alloc("shortRev").mkString(rev2.gitRev().substr(0, 12));
     if (auto revCount = input2.getRevCount())
-        mkInt(*state.allocAttr(v, state.symbols.create("revCount")), *revCount);
-    v.attrs->sort();
+        attrs2.alloc("revCount").mkInt(*revCount);
+    v.mkAttrs(attrs2);
 
     state.allowPath(tree.storePath);
 }
diff --git a/src/libexpr/primops/fetchTree.cc b/src/libexpr/primops/fetchTree.cc
index 079513873..d09e2d9e1 100644
--- a/src/libexpr/primops/fetchTree.cc
+++ b/src/libexpr/primops/fetchTree.cc
@@ -21,49 +21,48 @@ void emitTreeAttrs(
 {
     assert(input.isImmutable());
 
-    state.mkAttrs(v, 8);
+    auto attrs = state.buildBindings(8);
 
     auto storePath = state.store->printStorePath(tree.storePath);
 
-    mkString(*state.allocAttr(v, state.sOutPath), storePath, PathSet({storePath}));
+    attrs.alloc(state.sOutPath).mkString(storePath, {storePath});
 
     // FIXME: support arbitrary input attributes.
 
     auto narHash = input.getNarHash();
     assert(narHash);
-    mkString(*state.allocAttr(v, state.symbols.create("narHash")),
-        narHash->to_string(SRI, true));
+    attrs.alloc("narHash").mkString(narHash->to_string(SRI, true));
 
     if (input.getType() == "git")
-        mkBool(*state.allocAttr(v, state.symbols.create("submodules")),
+        attrs.alloc("submodules").mkBool(
             fetchers::maybeGetBoolAttr(input.attrs, "submodules").value_or(false));
 
     if (!forceDirty) {
 
         if (auto rev = input.getRev()) {
-            mkString(*state.allocAttr(v, state.symbols.create("rev")), rev->gitRev());
-            mkString(*state.allocAttr(v, state.symbols.create("shortRev")), rev->gitShortRev());
+            attrs.alloc("rev").mkString(rev->gitRev());
+            attrs.alloc("shortRev").mkString(rev->gitShortRev());
         } else if (emptyRevFallback) {
             // Backwards compat for `builtins.fetchGit`: dirty repos return an empty sha1 as rev
             auto emptyHash = Hash(htSHA1);
-            mkString(*state.allocAttr(v, state.symbols.create("rev")), emptyHash.gitRev());
-            mkString(*state.allocAttr(v, state.symbols.create("shortRev")), emptyHash.gitShortRev());
+            attrs.alloc("rev").mkString(emptyHash.gitRev());
+            attrs.alloc("shortRev").mkString(emptyHash.gitShortRev());
         }
 
         if (auto revCount = input.getRevCount())
-            mkInt(*state.allocAttr(v, state.symbols.create("revCount")), *revCount);
+            attrs.alloc("revCount").mkInt(*revCount);
         else if (emptyRevFallback)
-            mkInt(*state.allocAttr(v, state.symbols.create("revCount")), 0);
+            attrs.alloc("revCount").mkInt(0);
 
     }
 
     if (auto lastModified = input.getLastModified()) {
-        mkInt(*state.allocAttr(v, state.symbols.create("lastModified")), *lastModified);
-        mkString(*state.allocAttr(v, state.symbols.create("lastModifiedDate")),
+        attrs.alloc("lastModified").mkInt(*lastModified);
+        attrs.alloc("lastModifiedDate").mkString(
             fmt("%s", std::put_time(std::gmtime(&*lastModified), "%Y%m%d%H%M%S")));
     }
 
-    v.attrs->sort();
+    v.mkAttrs(attrs);
 }
 
 std::string fixURI(std::string uri, EvalState & state, const std::string & defaultScheme = "file")
@@ -126,7 +125,7 @@ static void fetchTree(
             if (attr.name == state.sType) continue;
             state.forceValue(*attr.value, *attr.pos);
             if (attr.value->type() == nPath || attr.value->type() == nString) {
-                auto s = state.coerceToString(*attr.pos, *attr.value, context, false, false);
+                auto s = state.coerceToString(*attr.pos, *attr.value, context, false, false).toOwned();
                 attrs.emplace(attr.name,
                     attr.name == "url"
                     ? type == "git"
@@ -152,7 +151,7 @@ static void fetchTree(
 
         input = fetchers::Input::fromAttrs(std::move(attrs));
     } else {
-        auto url = state.coerceToString(pos, *args[0], context, false, false);
+        auto url = state.coerceToString(pos, *args[0], context, false, false).toOwned();
 
         if (type == "git") {
             fetchers::Attrs attrs;
@@ -248,7 +247,7 @@ static void fetch(EvalState & state, const Pos & pos, Value * * args, Value & v,
     state.allowPath(storePath);
 
     auto path = state.store->printStorePath(storePath);
-    mkString(v, path, PathSet({path}));
+    v.mkString(path, PathSet({path}));
 }
 
 static void prim_fetchurl(EvalState & state, const Pos & pos, Value * * args, Value & v)
diff --git a/src/libexpr/primops/fromTOML.cc b/src/libexpr/primops/fromTOML.cc
index 30466fc5b..c0e858b61 100644
--- a/src/libexpr/primops/fromTOML.cc
+++ b/src/libexpr/primops/fromTOML.cc
@@ -9,7 +9,7 @@ static void prim_fromTOML(EvalState & state, const Pos & pos, Value * * args, Va
 {
     auto toml = state.forceStringNoCtx(*args[0], pos);
 
-    std::istringstream tomlStream(toml);
+    std::istringstream tomlStream(string{toml});
 
     std::function<void(Value &, toml::value)> visit;
 
@@ -24,15 +24,12 @@ static void prim_fromTOML(EvalState & state, const Pos & pos, Value * * args, Va
                     size_t size = 0;
                     for (auto & i : table) { (void) i; size++; }
 
-                    state.mkAttrs(v, size);
+                    auto attrs = state.buildBindings(size);
 
-                    for(auto & elem: table) {
+                    for(auto & elem : table)
+                        visit(attrs.alloc(elem.first), elem.second);
 
-                        auto & v2 = *state.allocAttr(v, state.symbols.create(elem.first));
-                        visit(v2, elem.second);
-                    }
-
-                    v.attrs->sort();
+                    v.mkAttrs(attrs);
                 }
                 break;;
             case toml::value_t::array:
@@ -46,16 +43,16 @@ static void prim_fromTOML(EvalState & state, const Pos & pos, Value * * args, Va
                 }
                 break;;
             case toml::value_t::boolean:
-                mkBool(v, toml::get<bool>(t));
+                v.mkBool(toml::get<bool>(t));
                 break;;
             case toml::value_t::integer:
-                mkInt(v, toml::get<int64_t>(t));
+                v.mkInt(toml::get<int64_t>(t));
                 break;;
             case toml::value_t::floating:
-                mkFloat(v, toml::get<NixFloat>(t));
+                v.mkFloat(toml::get<NixFloat>(t));
                 break;;
             case toml::value_t::string:
-                mkString(v, toml::get<std::string>(t));
+                v.mkString(toml::get<std::string>(t));
                 break;;
             case toml::value_t::local_datetime:
             case toml::value_t::offset_datetime:
@@ -65,7 +62,7 @@ static void prim_fromTOML(EvalState & state, const Pos & pos, Value * * args, Va
                 throw std::runtime_error("Dates and times are not supported");
                 break;;
             case toml::value_t::empty:
-                mkNull(v);
+                v.mkNull();
                 break;;
 
         }
diff --git a/src/libexpr/symbol-table.hh b/src/libexpr/symbol-table.hh
index 4eb6dac81..a090ebae5 100644
--- a/src/libexpr/symbol-table.hh
+++ b/src/libexpr/symbol-table.hh
@@ -1,7 +1,8 @@
 #pragma once
 
+#include <list>
 #include <map>
-#include <unordered_set>
+#include <unordered_map>
 
 #include "types.hh"
 
@@ -70,15 +71,21 @@ public:
 class SymbolTable
 {
 private:
-    typedef std::unordered_set<string> Symbols;
-    Symbols symbols;
+    std::unordered_map<std::string_view, Symbol> symbols;
+    std::list<string> store;
 
 public:
     Symbol create(std::string_view s)
     {
-        // FIXME: avoid allocation if 's' already exists in the symbol table.
-        std::pair<Symbols::iterator, bool> res = symbols.emplace(std::string(s));
-        return Symbol(&*res.first);
+        // Most symbols are looked up more than once, so we trade off insertion performance
+        // for lookup performance.
+        // TODO: could probably be done more efficiently with transparent Hash and Equals
+        // on the original implementation using unordered_set
+        auto it = symbols.find(s);
+        if (it != symbols.end()) return it->second;
+
+        const string & rawSym = store.emplace_back(s);
+        return symbols.emplace(rawSym, Symbol(&rawSym)).first->second;
     }
 
     size_t size() const
@@ -91,7 +98,7 @@ public:
     template<typename T>
     void dump(T callback)
     {
-        for (auto & s : symbols)
+        for (auto & s : store)
             callback(s);
     }
 };
diff --git a/src/libexpr/value-to-xml.cc b/src/libexpr/value-to-xml.cc
index a875f82d7..a9fb60b0e 100644
--- a/src/libexpr/value-to-xml.cc
+++ b/src/libexpr/value-to-xml.cc
@@ -142,7 +142,7 @@ static void printValueAsXML(EvalState & state, bool strict, bool location,
                 if (!v.lambda.fun->arg.empty()) attrs["name"] = v.lambda.fun->arg;
                 if (v.lambda.fun->formals->ellipsis) attrs["ellipsis"] = "1";
                 XMLOpenElement _(doc, "attrspat", attrs);
-                for (auto & i : v.lambda.fun->formals->formals)
+                for (auto & i : v.lambda.fun->formals->lexicographicOrder())
                     doc.writeEmptyElement("attr", singletonAttrs("name", i.name));
             } else
                 doc.writeEmptyElement("varpat", singletonAttrs("name", v.lambda.fun->arg));
diff --git a/src/libexpr/value.hh b/src/libexpr/value.hh
index 6b4f3c0ae..bef5cd6bd 100644
--- a/src/libexpr/value.hh
+++ b/src/libexpr/value.hh
@@ -10,6 +10,8 @@
 
 namespace nix {
 
+class BindingsBuilder;
+
 
 typedef enum {
     tInt = 1,
@@ -235,6 +237,17 @@ public:
         string.context = context;
     }
 
+    void mkString(std::string_view s);
+
+    void mkString(std::string_view s, const PathSet & context);
+
+    void mkStringMove(const char * s, const PathSet & context);
+
+    inline void mkString(const Symbol & s)
+    {
+        mkString(((const std::string &) s).c_str());
+    }
+
     inline void mkPath(const char * s)
     {
         clearValue();
@@ -242,6 +255,8 @@ public:
         path = s;
     }
 
+    void mkPath(std::string_view s);
+
     inline void mkNull()
     {
         clearValue();
@@ -255,6 +270,8 @@ public:
         attrs = a;
     }
 
+    Value & mkAttrs(BindingsBuilder & bindings);
+
     inline void mkList(size_t size)
     {
         clearValue();
@@ -344,7 +361,7 @@ public:
         return internalType == tList1 ? 1 : internalType == tList2 ? 2 : bigList.size;
     }
 
-    Pos determinePos(const Pos &pos) const;
+    Pos determinePos(const Pos & pos) const;
 
     /* Check whether forcing this value requires a trivial amount of
        computation. In particular, function applications are
@@ -383,45 +400,6 @@ public:
 };
 
 
-
-// TODO: Remove these static functions, replace call sites with v.mk* instead
-static inline void mkInt(Value & v, NixInt n)
-{
-    v.mkInt(n);
-}
-
-static inline void mkFloat(Value & v, NixFloat n)
-{
-    v.mkFloat(n);
-}
-
-static inline void mkBool(Value & v, bool b)
-{
-    v.mkBool(b);
-}
-
-static inline void mkNull(Value & v)
-{
-    v.mkNull();
-}
-
-static inline void mkApp(Value & v, Value & left, Value & right)
-{
-    v.mkApp(&left, &right);
-}
-
-static inline void mkString(Value & v, const Symbol & s)
-{
-    v.mkString(((const string &) s).c_str());
-}
-
-
-void mkString(Value & v, const char * s);
-
-
-void mkPath(Value & v, const char * s);
-
-
 #if HAVE_BOEHMGC
 typedef std::vector<Value *, traceable_allocator<Value *> > ValueVector;
 typedef std::map<Symbol, Value *, std::less<Symbol>, traceable_allocator<std::pair<const Symbol, Value *> > > ValueMap;