Ensure that attrsets are sorted

Previously you had to remember to call value->attrs->sort() after
populating value->attrs. Now there is a BindingsBuilder helper that
wraps Bindings and ensures that sort() is called before you can use
it.

17 files changed, 261 insertions, 199 deletions

diff --git a/src/libexpr/attr-set.cc b/src/libexpr/attr-set.cc
index b6091c955..d74243f45 100644
--- a/src/libexpr/attr-set.cc
+++ b/src/libexpr/attr-set.cc
@@ -41,16 +41,39 @@ 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());
 }
 
 
+Value & Value::mkAttrs(BindingsBuilder & bindings)
+{
+    clearValue();
+    internalType = tAttrs;
+    attrs = bindings.finish();
+    return *this;
+}
+
+
 }
diff --git a/src/libexpr/attr-set.hh b/src/libexpr/attr-set.hh
index 7d6ffc9f3..903289b69 100644
--- a/src/libexpr/attr-set.hh
+++ b/src/libexpr/attr-set.hh
@@ -113,5 +113,39 @@ 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
+{
+    EvalState & state;
+    Bindings * bindings;
+
+public:
+
+    BindingsBuilder(EvalState & state, Bindings * bindings)
+        : state(state), bindings(bindings)
+    { }
+
+    void insert(Symbol name, Value * value, ptr<Pos> pos = ptr(&noPos))
+    {
+        insert(Attr(name, value, pos));
+    }
+
+    void insert(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;
+    }
+};
 
 }
diff --git a/src/libexpr/common-eval-args.cc b/src/libexpr/common-eval-args.cc
index fb0932c00..ecae2ca1f 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));
+        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.cc b/src/libexpr/eval.cc
index a95726f5f..0710ce270 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -772,18 +772,30 @@ void mkString(Value & v, const char * s)
 }
 
 
+void Value::mkString(std::string_view s)
+{
+    mkString(dupStringWithLen(s.data(), s.size()));
+}
+
+
 Value & mkString(Value & v, std::string_view s, const PathSet & context)
 {
-    v.mkString(dupStringWithLen(s.data(), s.size()));
+    v.mkString(s, context);
+    return v;
+}
+
+
+void Value::mkString(std::string_view s, const PathSet & context)
+{
+    mkString(s);
     if (!context.empty()) {
         size_t n = 0;
-        v.string.context = (const char * *)
+        string.context = (const char * *)
             allocBytes((context.size() + 1) * sizeof(char *));
         for (auto & i : context)
-            v.string.context[n++] = dupString(i.c_str());
-        v.string.context[n] = 0;
+            string.context[n++] = dupString(i.c_str());
+        string.context[n] = 0;
     }
-    return v;
 }
 
 
@@ -882,11 +894,11 @@ 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);
 }
@@ -1341,7 +1353,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->argNames.count(i.name))
                             throwTypeError(pos, "%1% called with unexpected argument '%2%'", lambda, i.name);
                     abort(); // can't happen
                 }
@@ -1484,22 +1496,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%')
 
@@ -1512,9 +1522,7 @@ https://nixos.org/manual/nix/stable/#ss-functions.)", i.name);
         }
     }
 
-    actualArgs->attrs->sort();
-
-    callFunction(fun, *actualArgs, res, noPos);
+    callFunction(fun, allocValue()->mkAttrs(attrs), res, noPos);
 }
 
 
@@ -1719,7 +1727,7 @@ void ExprConcatStrings::eval(EvalState & state, Env & env, Value & v)
         auto path = canonPath(s.str());
         mkPath(v, path.c_str());
     } else
-        mkString(v, s.str(), context);
+        v.mkString(s.str(), context);
 }
 
 
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index d7ef7b88a..44ccc6593 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -339,10 +339,15 @@ 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);
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index ed4c47fbb..25fd9b949 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -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();
 }
 
 
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index ab99962f7..daf5fc927 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -125,13 +125,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
@@ -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);
+        mkApp(v, **state.vImportedDrvToDerivation, *w);
         state.forceAttrs(v, pos);
     }
 
@@ -802,16 +800,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]);
+        mkBool(attrs.alloc("success"), true);
     } catch (AssertionError & e) {
-        mkBool(*state.allocAttr(v, state.sValue), false);
-        mkBool(*state.allocAttr(v, state.symbols.create("success")), false);
+        mkBool(attrs.alloc(state.sValue), false);
+        mkBool(attrs.alloc("success"), false);
     }
-    v.attrs->sort();
+    v.mkAttrs(attrs);
 }
 
 static RegisterPrimOp primop_tryEval({
@@ -839,7 +837,7 @@ static RegisterPrimOp primop_tryEval({
 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(""));
+    v.mkString(evalSettings.restrictEval || evalSettings.pureEval ? "" : getEnv(name).value_or(""));
 }
 
 static RegisterPrimOp primop_getEnv({
@@ -1265,11 +1263,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 {
@@ -1579,20 +1577,20 @@ static void prim_readDir(EvalState & state, const Pos & pos, Value * * args, Val
     }
 
     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({
@@ -2308,7 +2306,7 @@ static void prim_listToAttrs(EvalState & state, const Pos & pos, Value * * args,
 {
     state.forceList(*args[0], pos);
 
-    state.mkAttrs(v, args[0]->listSize());
+    auto attrs = state.buildBindings(args[0]->listSize());
 
     std::set<Symbol> seen;
 
@@ -2334,11 +2332,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({
@@ -2445,14 +2443,11 @@ static void prim_functionArgs(EvalState & state, const Pos & pos, Value * * args
         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();
+        mkBool(attrs.alloc(i.name, ptr(&i.pos)), i.def);
+    v.mkAttrs(attrs);
 }
 
 static RegisterPrimOp primop_functionArgs({
@@ -3003,21 +2998,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({
@@ -3734,10 +3729,10 @@ static void prim_parseDrvName(EvalState & state, const Pos & pos, Value * * args
 {
     string 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({
@@ -3883,11 +3878,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);
 
diff --git a/src/libexpr/primops/context.cc b/src/libexpr/primops/context.cc
index 20545afd0..ab08303d8 100644
--- a/src/libexpr/primops/context.cc
+++ b/src/libexpr/primops/context.cc
@@ -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);
+            mkBool(infoAttrs.alloc(sPath), true);
         if (info.second.allOutputs)
-            mkBool(*state.allocAttr(infoVal, sAllOutputs), true);
+            mkBool(infoAttrs.alloc(sAllOutputs), 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);
diff --git a/src/libexpr/primops/fetchMercurial.cc b/src/libexpr/primops/fetchMercurial.cc
index c23480853..42214c207 100644
--- a/src/libexpr/primops/fetchMercurial.cc
+++ b/src/libexpr/primops/fetchMercurial.cc
@@ -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..a97bfcae7 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")
diff --git a/src/libexpr/primops/fromTOML.cc b/src/libexpr/primops/fromTOML.cc
index 30466fc5b..a328b6736 100644
--- a/src/libexpr/primops/fromTOML.cc
+++ b/src/libexpr/primops/fromTOML.cc
@@ -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:
diff --git a/src/libexpr/value.hh b/src/libexpr/value.hh
index 6b4f3c0ae..a8fea02dc 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,10 @@ public:
         string.context = context;
     }
 
+    void mkString(std::string_view s);
+
+    void mkString(std::string_view s, const PathSet & context);
+
     inline void mkPath(const char * s)
     {
         clearValue();
@@ -255,6 +261,8 @@ public:
         attrs = a;
     }
 
+    Value & mkAttrs(BindingsBuilder & bindings);
+
     inline void mkList(size_t size)
     {
         clearValue();
diff --git a/src/nix-build/nix-build.cc b/src/nix-build/nix-build.cc
index d3d6ce1ce..b73eb0795 100755
--- a/src/nix-build/nix-build.cc
+++ b/src/nix-build/nix-build.cc
@@ -258,13 +258,10 @@ static void main_nix_build(int argc, char * * argv)
     auto autoArgs = myArgs.getAutoArgs(*state);
 
     if (runEnv) {
-        auto newArgs = state->allocBindings(autoArgs->size() + 1);
-        auto tru = state->allocValue();
-        mkBool(*tru, true);
-        newArgs->push_back(Attr(state->symbols.create("inNixShell"), tru));
-        for (auto & i : *autoArgs) newArgs->push_back(i);
-        newArgs->sort();
-        autoArgs = newArgs;
+        auto newArgs = state->buildBindings(autoArgs->size() + 1);
+        newArgs.alloc("inNixShell").mkBool(true);
+        for (auto & i : *autoArgs) newArgs.insert(i);
+        autoArgs = newArgs.finish();
     }
 
     if (packages) {
diff --git a/src/nix-env/nix-env.cc b/src/nix-env/nix-env.cc
index b9e7be1c6..171f1c440 100644
--- a/src/nix-env/nix-env.cc
+++ b/src/nix-env/nix-env.cc
@@ -98,8 +98,11 @@ static bool isNixExpr(const Path & path, struct stat & st)
 }
 
 
+static constexpr size_t maxAttrs = 1024;
+
+
 static void getAllExprs(EvalState & state,
-    const Path & path, StringSet & attrs, Value & v)
+    const Path & path, StringSet & seen, BindingsBuilder & attrs)
 {
     StringSet namesSorted;
     for (auto & i : readDirectory(path)) namesSorted.insert(i.name);
@@ -124,22 +127,21 @@ static void getAllExprs(EvalState & state,
             string attrName = i;
             if (hasSuffix(attrName, ".nix"))
                 attrName = string(attrName, 0, attrName.size() - 4);
-            if (!attrs.insert(attrName).second) {
+            if (!seen.insert(attrName).second) {
                 printError("warning: name collision in input Nix expressions, skipping '%1%'", path2);
                 continue;
             }
             /* Load the expression on demand. */
-            Value & vFun = state.getBuiltin("import");
-            Value & vArg(*state.allocValue());
-            mkString(vArg, path2);
-            if (v.attrs->size() == v.attrs->capacity())
+            auto vArg = state.allocValue();
+            vArg->mkString(path2);
+            if (seen.size() == maxAttrs)
                 throw Error("too many Nix expressions in directory '%1%'", path);
-            mkApp(*state.allocAttr(v, state.symbols.create(attrName)), vFun, vArg);
+            attrs.alloc(attrName).mkApp(&state.getBuiltin("import"), vArg);
         }
         else if (S_ISDIR(st.st_mode))
             /* `path2' is a directory (with no default.nix in it);
                recurse into it. */
-            getAllExprs(state, path2, attrs, v);
+            getAllExprs(state, path2, seen, attrs);
     }
 }
 
@@ -161,11 +163,11 @@ static void loadSourceExpr(EvalState & state, const Path & path, Value & v)
        ~/.nix-defexpr directory that includes some system-wide
        directory). */
     else if (S_ISDIR(st.st_mode)) {
-        state.mkAttrs(v, 1024);
-        state.mkList(*state.allocAttr(v, state.symbols.create("_combineChannels")), 0);
-        StringSet attrs;
-        getAllExprs(state, path, attrs, v);
-        v.attrs->sort();
+        auto attrs = state.buildBindings(maxAttrs);
+        attrs.alloc("_combineChannels").mkList(0);
+        StringSet seen;
+        getAllExprs(state, path, seen, attrs);
+        v.mkAttrs(attrs);
     }
 
     else throw Error("path '%s' is not a directory or a Nix expression", path);
diff --git a/src/nix-env/user-env.cc b/src/nix-env/user-env.cc
index 1fd4bcbd3..68c1c16b2 100644
--- a/src/nix-env/user-env.cc
+++ b/src/nix-env/user-env.cc
@@ -50,7 +50,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
     StorePathSet references;
     Value manifest;
     state.mkList(manifest, elems.size());
-    unsigned int n = 0;
+    size_t n = 0;
     for (auto & i : elems) {
         /* Create a pseudo-derivation containing the name, system,
            output paths, and optionally the derivation path, as well
@@ -59,28 +59,25 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
         DrvInfo::Outputs outputs = i.queryOutputs(true);
         StringSet metaNames = i.queryMetaNames();
 
-        Value & v(*state.allocValue());
-        manifest.listElems()[n++] = &v;
-        state.mkAttrs(v, 7 + outputs.size());
+        auto attrs = state.buildBindings(7 + outputs.size());
 
-        mkString(*state.allocAttr(v, state.sType), "derivation");
-        mkString(*state.allocAttr(v, state.sName), i.queryName());
+        attrs.alloc(state.sType).mkString("derivation");
+        attrs.alloc(state.sName).mkString(i.queryName());
         auto system = i.querySystem();
         if (!system.empty())
-            mkString(*state.allocAttr(v, state.sSystem), system);
-        mkString(*state.allocAttr(v, state.sOutPath), i.queryOutPath());
+            attrs.alloc(state.sSystem).mkString(system);
+        attrs.alloc(state.sOutPath).mkString(i.queryOutPath());
         if (drvPath != "")
-            mkString(*state.allocAttr(v, state.sDrvPath), i.queryDrvPath());
+            attrs.alloc(state.sDrvPath).mkString(i.queryDrvPath());
 
         // Copy each output meant for installation.
-        Value & vOutputs = *state.allocAttr(v, state.sOutputs);
+        auto & vOutputs = attrs.alloc(state.sOutputs);
         state.mkList(vOutputs, outputs.size());
-        unsigned int m = 0;
-        for (auto & j : outputs) {
-            mkString(*(vOutputs.listElems()[m++] = state.allocValue()), j.first);
-            Value & vOutputs = *state.allocAttr(v, state.symbols.create(j.first));
-            state.mkAttrs(vOutputs, 2);
-            mkString(*state.allocAttr(vOutputs, state.sOutPath), j.second);
+        for (const auto & [m, j] : enumerate(outputs)) {
+            (vOutputs.listElems()[m] = state.allocValue())->mkString(j.first);
+            auto outputAttrs = state.buildBindings(2);
+            outputAttrs.alloc(state.sOutPath).mkString(j.second);
+            attrs.alloc(j.first).mkAttrs(outputAttrs);
 
             /* This is only necessary when installing store paths, e.g.,
                `nix-env -i /nix/store/abcd...-foo'. */
@@ -91,15 +88,16 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
         }
 
         // Copy the meta attributes.
-        Value & vMeta = *state.allocAttr(v, state.sMeta);
-        state.mkAttrs(vMeta, metaNames.size());
+        auto meta = state.buildBindings(metaNames.size());
         for (auto & j : metaNames) {
             Value * v = i.queryMeta(j);
             if (!v) continue;
-            vMeta.attrs->push_back(Attr(state.symbols.create(j), v));
+            meta.insert(state.symbols.create(j), v);
         }
-        vMeta.attrs->sort();
-        v.attrs->sort();
+
+        attrs.alloc(state.sMeta).mkAttrs(meta);
+
+        (manifest.listElems()[n++] = state.allocValue())->mkAttrs(attrs);
 
         if (drvPath != "") references.insert(state.store->parseStorePath(drvPath));
     }
@@ -118,13 +116,16 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
 
     /* Construct a Nix expression that calls the user environment
        builder with the manifest as argument. */
-    Value args, topLevel;
-    state.mkAttrs(args, 3);
-    mkString(*state.allocAttr(args, state.symbols.create("manifest")),
-        state.store->printStorePath(manifestFile), {state.store->printStorePath(manifestFile)});
-    args.attrs->push_back(Attr(state.symbols.create("derivations"), &manifest));
-    args.attrs->sort();
-    mkApp(topLevel, envBuilder, args);
+    auto attrs = state.buildBindings(3);
+    attrs.alloc("manifest").mkString(
+        state.store->printStorePath(manifestFile),
+        {state.store->printStorePath(manifestFile)});
+    attrs.insert(state.symbols.create("derivations"), &manifest);
+    Value args;
+    args.mkAttrs(attrs);
+
+    Value topLevel;
+    topLevel.mkApp(&envBuilder, &args);
 
     /* Evaluate it. */
     debug("evaluating user environment builder");
diff --git a/src/nix/bundle.cc b/src/nix/bundle.cc
index aca024bca..adb5b3e73 100644
--- a/src/nix/bundle.cc
+++ b/src/nix/bundle.cc
@@ -78,20 +78,20 @@ struct CmdBundle : InstallableCommand
             Strings{bundlerName == "" ? "defaultBundler" : bundlerName},
             Strings({"bundlers."}), lockFlags);
 
-        Value * arg = evalState->allocValue();
-        evalState->mkAttrs(*arg, 2);
+        auto attrs = evalState->buildBindings(2);
 
         PathSet context;
         for (auto & i : app.context)
             context.insert("=" + store->printStorePath(i.path));
-        mkString(*evalState->allocAttr(*arg, evalState->symbols.create("program")), app.program, context);
+        attrs.alloc("program").mkString(app.program, context);
 
-        mkString(*evalState->allocAttr(*arg, evalState->symbols.create("system")), settings.thisSystem.get());
-
-        arg->attrs->sort();
+        attrs.alloc("system").mkString(settings.thisSystem.get());
 
         auto vRes = evalState->allocValue();
-        evalState->callFunction(*bundler.toValue(*evalState).first, *arg, *vRes, noPos);
+        evalState->callFunction(
+            *bundler.toValue(*evalState).first,
+            evalState->allocValue()->mkAttrs(attrs),
+            *vRes, noPos);
 
         if (!evalState->isDerivation(*vRes))
             throw Error("the bundler '%s' does not produce a derivation", bundler.what());
diff --git a/src/nix/main.cc b/src/nix/main.cc
index 759118fd5..fe7469be4 100644
--- a/src/nix/main.cc
+++ b/src/nix/main.cc
@@ -187,14 +187,11 @@ static void showHelp(std::vector<std::string> subcommand, MultiCommand & topleve
             , "/"),
         *vUtils);
 
-    auto vArgs = state.allocValue();
-    state.mkAttrs(*vArgs, 16);
-    auto vJson = state.allocAttr(*vArgs, state.symbols.create("command"));
-    mkString(*vJson, toplevel.toJSON().dump());
-    vArgs->attrs->sort();
+    auto attrs = state.buildBindings(16);
+    attrs.alloc("command").mkString(toplevel.toJSON().dump());
 
     auto vRes = state.allocValue();
-    state.callFunction(*vGenerateManpage, *vArgs, *vRes, noPos);
+    state.callFunction(*vGenerateManpage, state.allocValue()->mkAttrs(attrs), *vRes, noPos);
 
     auto attr = vRes->attrs->get(state.symbols.create(mdName + ".md"));
     if (!attr)