Merge branch 'master' into debug-exploratory-PR

16 files changed, 431 insertions, 271 deletions

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index ac437e69d..851058b3e 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -121,8 +121,8 @@ void printValue(std::ostream & str, std::set<const Value *> & active, const Valu
     case tList2:
     case tListN:
         str << "[ ";
-        for (unsigned int n = 0; n < v.listSize(); ++n) {
-            printValue(str, active, *v.listElems()[n]);
+        for (auto v2 : v.listItems()) {
+            printValue(str, active, *v2);
             str << " ";
         }
         str << "]";
@@ -521,8 +521,12 @@ Path EvalState::checkSourcePath(const Path & path_)
         }
     }
 
-    if (!found)
-        throw RestrictedPathError("access to absolute path '%1%' is forbidden in restricted mode", abspath);
+    if (!found) {
+        auto modeInformation = evalSettings.pureEval
+            ? "in pure eval mode (use '--impure' to override)"
+            : "in restricted mode";
+        throw RestrictedPathError("access to absolute path '%1%' is forbidden %2%", abspath, modeInformation);
+    }
 
     /* Resolve symlinks. */
     debug(format("checking access to '%s'") % abspath);
@@ -960,8 +964,23 @@ inline Value * EvalState::lookupVar(Env * env, const ExprVar & var, bool noEval)
 
 Value * EvalState::allocValue()
 {
+    /* We use the boehm batch allocator to speed up allocations of Values (of which there are many).
+       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();
+    }
+
+    /* 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));
+    GC_NEXT(p) = nullptr;
+
     nrValues++;
-    auto v = (Value *) allocBytes(sizeof(Value));
+    auto v = (Value *) p;
     return v;
 }
 
@@ -1314,8 +1333,8 @@ void ExprLet::eval(EvalState & state, Env & env, Value & v)
 void ExprList::eval(EvalState & state, Env & env, Value & v)
 {
     state.mkList(v, elems.size());
-    for (size_t n = 0; n < elems.size(); ++n)
-        v.listElems()[n] = elems[n]->maybeThunk(state, env);
+    for (auto [n, v2] : enumerate(v.listItems()))
+        const_cast<Value * &>(v2) = elems[n]->maybeThunk(state, env);
 }
 
 
@@ -1834,7 +1853,7 @@ void ExprConcatStrings::eval(EvalState & state, Env & env, Value & v)
     bool first = !forceString;
     ValueType firstType = nString;
 
-    for (auto & i : *es) {
+    for (auto & [i_pos, i] : *es) {
         Value vTmp;
         i->eval(state, env, vTmp);
 
@@ -1855,7 +1874,7 @@ void ExprConcatStrings::eval(EvalState & state, Env & env, Value & v)
                 nf = n;
                 nf += vTmp.fpoint;
             } else {
-                throwEvalError(pos, "cannot add %1% to an integer", showType(vTmp), env, this);
+                throwEvalError(i_pos, "cannot add %1% to an integer", showType(vTmp), env, this);
             }
         } else if (firstType == nFloat) {
             if (vTmp.type() == nInt) {
@@ -1863,12 +1882,12 @@ void ExprConcatStrings::eval(EvalState & state, Env & env, Value & v)
             } else if (vTmp.type() == nFloat) {
                 nf += vTmp.fpoint;
             } else
-                throwEvalError(pos, "cannot add %1% to a float", showType(vTmp), env, this);
+                throwEvalError(i_pos, "cannot add %1% to a float", showType(vTmp), env, this);
         } else
             /* 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(pos, vTmp, context, false, firstType == nString, !first);
+            s << state.coerceToString(i_pos, vTmp, context, false, firstType == nString, !first);
 
         first = false;
     }
@@ -1925,8 +1944,8 @@ void EvalState::forceValueDeep(Value & v)
         }
 
         else if (v.isList()) {
-            for (size_t n = 0; n < v.listSize(); ++n)
-                recurse(*v.listElems()[n]);
+            for (auto v2 : v.listItems())
+                recurse(*v2);
         }
     };
 
@@ -2113,12 +2132,12 @@ string EvalState::coerceToString(const Pos & pos, Value & v, PathSet & context,
 
         if (v.isList()) {
             string result;
-            for (size_t n = 0; n < v.listSize(); ++n) {
-                result += coerceToString(pos, *v.listElems()[n],
+            for (auto [n, v2] : enumerate(v.listItems())) {
+                result += coerceToString(pos, *v2,
                     context, coerceMore, copyToStore);
                 if (n < v.listSize() - 1
                     /* !!! not quite correct */
-                    && (!v.listElems()[n]->isList() || v.listElems()[n]->listSize() != 0))
+                    && (!v2->isList() || v2->listSize() != 0))
                     result += " ";
             }
             return result;
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 2f8cc82b0..5dbb9b5e5 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -145,6 +145,9 @@ private:
     /* Cache used by prim_match(). */
     std::shared_ptr<RegexCache> regexCache;
 
+    /* Allocation cache for GC'd Value objects. */
+    void * valueAllocCache = nullptr;
+
 public:
 
     EvalState(
@@ -362,7 +365,10 @@ public:
     /* Print statistics. */
     void printStats();
 
-    void realiseContext(const PathSet & context);
+    /* Realise the given context, and return a mapping from the placeholders
+     * used to construct the associated value to their final store path
+     */
+    [[nodiscard]] StringMap realiseContext(const PathSet & context);
 
 private:
 
diff --git a/src/libexpr/flake/config.cc b/src/libexpr/flake/config.cc
index c03f4106c..7ecd61816 100644
--- a/src/libexpr/flake/config.cc
+++ b/src/libexpr/flake/config.cc
@@ -38,11 +38,11 @@ void ConfigFile::apply()
 
         // FIXME: Move into libutil/config.cc.
         std::string valueS;
-        if (auto s = std::get_if<std::string>(&value))
+        if (auto* s = std::get_if<std::string>(&value))
             valueS = *s;
-        else if (auto n = std::get_if<int64_t>(&value))
-            valueS = fmt("%d", n);
-        else if (auto b = std::get_if<Explicit<bool>>(&value))
+        else if (auto* n = std::get_if<int64_t>(&value))
+            valueS = fmt("%d", *n);
+        else if (auto* b = std::get_if<Explicit<bool>>(&value))
             valueS = b->t ? "true" : "false";
         else if (auto ss = std::get_if<std::vector<std::string>>(&value))
             valueS = concatStringsSep(" ", *ss); // FIXME: evil
diff --git a/src/libexpr/flake/flake.cc b/src/libexpr/flake/flake.cc
index f5be67d67..c549c5971 100644
--- a/src/libexpr/flake/flake.cc
+++ b/src/libexpr/flake/flake.cc
@@ -155,7 +155,7 @@ static FlakeInput parseFlakeInput(EvalState & state,
         if (!attrs.empty())
             throw Error("unexpected flake input attribute '%s', at %s", attrs.begin()->first, pos);
         if (url)
-            input.ref = parseFlakeRef(*url, baseDir, true);
+            input.ref = parseFlakeRef(*url, baseDir, true, input.isFlake);
     }
 
     if (!input.follows && !input.ref)
@@ -194,8 +194,8 @@ static Flake getFlake(
         state, originalRef, allowLookup, flakeCache);
 
     // Guard against symlink attacks.
-    auto flakeDir = canonPath(sourceInfo.actualPath + "/" + lockedRef.subdir);
-    auto flakeFile = canonPath(flakeDir + "/flake.nix");
+    auto flakeDir = canonPath(sourceInfo.actualPath + "/" + lockedRef.subdir, true);
+    auto flakeFile = canonPath(flakeDir + "/flake.nix", true);
     if (!isInDir(flakeFile, sourceInfo.actualPath))
         throw Error("'flake.nix' file of flake '%s' escapes from '%s'",
             lockedRef, state.store->printStorePath(sourceInfo.storePath));
@@ -254,11 +254,10 @@ static Flake getFlake(
             else if (setting.value->type() == nInt)
                 flake.config.settings.insert({setting.name, state.forceInt(*setting.value, *setting.pos)});
             else if (setting.value->type() == nBool)
-                flake.config.settings.insert({setting.name, state.forceBool(*setting.value, *setting.pos)});
+                flake.config.settings.insert({setting.name, Explicit<bool> { state.forceBool(*setting.value, *setting.pos) }});
             else if (setting.value->type() == nList) {
                 std::vector<std::string> ss;
-                for (unsigned int n = 0; n < setting.value->listSize(); ++n) {
-                    auto elem = setting.value->listElems()[n];
+                for (auto elem : setting.value->listItems()) {
                     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));
@@ -345,7 +344,8 @@ LockedFlake lockFlake(
             const InputPath & inputPathPrefix,
             std::shared_ptr<const Node> oldNode,
             const LockParent & parent,
-            const Path & parentPath)>
+            const Path & parentPath,
+            bool trustLock)>
             computeLocks;
 
         computeLocks = [&](
@@ -354,7 +354,8 @@ LockedFlake lockFlake(
             const InputPath & inputPathPrefix,
             std::shared_ptr<const Node> oldNode,
             const LockParent & parent,
-            const Path & parentPath)
+            const Path & parentPath,
+            bool trustLock)
         {
             debug("computing lock file node '%s'", printInputPath(inputPathPrefix));
 
@@ -465,14 +466,20 @@ LockedFlake lockFlake(
                                         .isFlake = (*lockedNode)->isFlake,
                                     });
                                 } else if (auto follows = std::get_if<1>(&i.second)) {
-                                    auto o = input.overrides.find(i.first);
-                                    // If the override disappeared, we have to refetch the flake,
-                                    // since some of the inputs may not be present in the lockfile.
-                                    if (o == input.overrides.end()) {
-                                        mustRefetch = true;
-                                        // There's no point populating the rest of the fake inputs,
-                                        // since we'll refetch the flake anyways.
-                                        break;
+                                    if (! trustLock) {
+                                        // It is possible that the flake has changed,
+                                        // so we must confirm all the follows that are in the lockfile are also in the flake.
+                                        auto overridePath(inputPath);
+                                        overridePath.push_back(i.first);
+                                        auto o = overrides.find(overridePath);
+                                        // If the override disappeared, we have to refetch the flake,
+                                        // since some of the inputs may not be present in the lockfile.
+                                        if (o == overrides.end()) {
+                                            mustRefetch = true;
+                                            // There's no point populating the rest of the fake inputs,
+                                            // since we'll refetch the flake anyways.
+                                            break;
+                                        }
                                     }
                                     fakeInputs.emplace(i.first, FlakeInput {
                                         .follows = *follows,
@@ -481,11 +488,16 @@ LockedFlake lockFlake(
                             }
                         }
 
+                        LockParent newParent {
+                            .path = inputPath,
+                            .absolute = true
+                        };
+
                         computeLocks(
                             mustRefetch
                             ? getFlake(state, oldLock->lockedRef, false, flakeCache).inputs
                             : fakeInputs,
-                            childNode, inputPath, oldLock, parent, parentPath);
+                            childNode, inputPath, oldLock, newParent, parentPath, !mustRefetch);
 
                     } else {
                         /* We need to create a new lock file entry. So fetch
@@ -542,7 +554,7 @@ LockedFlake lockFlake(
                                 ? std::dynamic_pointer_cast<const Node>(oldLock)
                                 : LockFile::read(
                                     inputFlake.sourceInfo->actualPath + "/" + inputFlake.lockedRef.subdir + "/flake.lock").root,
-                                newParent, localPath);
+                                newParent, localPath, false);
                         }
 
                         else {
@@ -566,11 +578,11 @@ LockedFlake lockFlake(
         };
 
         // Bring in the current ref for relative path resolution if we have it
-        auto parentPath = canonPath(flake.sourceInfo->actualPath + "/" + flake.lockedRef.subdir);
+        auto parentPath = canonPath(flake.sourceInfo->actualPath + "/" + flake.lockedRef.subdir, true);
 
         computeLocks(
             flake.inputs, newLockFile.root, {},
-            lockFlags.recreateLockFile ? nullptr : oldLockFile.root, parent, parentPath);
+            lockFlags.recreateLockFile ? nullptr : oldLockFile.root, parent, parentPath, false);
 
         for (auto & i : lockFlags.inputOverrides)
             if (!overridesUsed.count(i.first))
diff --git a/src/libexpr/flake/flakeref.cc b/src/libexpr/flake/flakeref.cc
index 29128d789..c3b74e0fe 100644
--- a/src/libexpr/flake/flakeref.cc
+++ b/src/libexpr/flake/flakeref.cc
@@ -48,9 +48,12 @@ FlakeRef FlakeRef::resolve(ref<Store> store) const
 }
 
 FlakeRef parseFlakeRef(
-    const std::string & url, const std::optional<Path> & baseDir, bool allowMissing)
+    const std::string & url,
+    const std::optional<Path> & baseDir,
+    bool allowMissing,
+    bool isFlake)
 {
-    auto [flakeRef, fragment] = parseFlakeRefWithFragment(url, baseDir, allowMissing);
+    auto [flakeRef, fragment] = parseFlakeRefWithFragment(url, baseDir, allowMissing, isFlake);
     if (fragment != "")
         throw Error("unexpected fragment '%s' in flake reference '%s'", fragment, url);
     return flakeRef;
@@ -67,7 +70,10 @@ std::optional<FlakeRef> maybeParseFlakeRef(
 }
 
 std::pair<FlakeRef, std::string> parseFlakeRefWithFragment(
-    const std::string & url, const std::optional<Path> & baseDir, bool allowMissing)
+    const std::string & url,
+    const std::optional<Path> & baseDir,
+    bool allowMissing,
+    bool isFlake)
 {
     using namespace fetchers;
 
@@ -112,46 +118,49 @@ std::pair<FlakeRef, std::string> parseFlakeRefWithFragment(
                to 'baseDir'). If so, search upward to the root of the
                repo (i.e. the directory containing .git). */
 
-            path = absPath(path, baseDir, true);
+            path = absPath(path, baseDir);
 
-            if (!S_ISDIR(lstat(path).st_mode))
-                throw BadURL("path '%s' is not a flake (because it's not a directory)", path);
+            if (isFlake) {
 
-            if (!allowMissing && !pathExists(path + "/flake.nix"))
-                throw BadURL("path '%s' is not a flake (because it doesn't contain a 'flake.nix' file)", path);
+                if (!S_ISDIR(lstat(path).st_mode))
+                    throw BadURL("path '%s' is not a flake (because it's not a directory)", path);
 
-            auto flakeRoot = path;
-            std::string subdir;
+                if (!allowMissing && !pathExists(path + "/flake.nix"))
+                    throw BadURL("path '%s' is not a flake (because it doesn't contain a 'flake.nix' file)", path);
 
-            while (flakeRoot != "/") {
-                if (pathExists(flakeRoot + "/.git")) {
-                    auto base = std::string("git+file://") + flakeRoot;
+                auto flakeRoot = path;
+                std::string subdir;
 
-                    auto parsedURL = ParsedURL{
-                        .url = base, // FIXME
-                        .base = base,
-                        .scheme = "git+file",
-                        .authority = "",
-                        .path = flakeRoot,
-                        .query = decodeQuery(match[2]),
-                    };
+                while (flakeRoot != "/") {
+                    if (pathExists(flakeRoot + "/.git")) {
+                        auto base = std::string("git+file://") + flakeRoot;
 
-                    if (subdir != "") {
-                        if (parsedURL.query.count("dir"))
-                            throw Error("flake URL '%s' has an inconsistent 'dir' parameter", url);
-                        parsedURL.query.insert_or_assign("dir", subdir);
-                    }
+                        auto parsedURL = ParsedURL{
+                            .url = base, // FIXME
+                            .base = base,
+                            .scheme = "git+file",
+                            .authority = "",
+                            .path = flakeRoot,
+                            .query = decodeQuery(match[2]),
+                        };
 
-                    if (pathExists(flakeRoot + "/.git/shallow"))
-                        parsedURL.query.insert_or_assign("shallow", "1");
+                        if (subdir != "") {
+                            if (parsedURL.query.count("dir"))
+                                throw Error("flake URL '%s' has an inconsistent 'dir' parameter", url);
+                            parsedURL.query.insert_or_assign("dir", subdir);
+                        }
 
-                    return std::make_pair(
-                        FlakeRef(Input::fromURL(parsedURL), get(parsedURL.query, "dir").value_or("")),
-                        fragment);
-                }
+                        if (pathExists(flakeRoot + "/.git/shallow"))
+                            parsedURL.query.insert_or_assign("shallow", "1");
 
-                subdir = std::string(baseNameOf(flakeRoot)) + (subdir.empty() ? "" : "/" + subdir);
-                flakeRoot = dirOf(flakeRoot);
+                        return std::make_pair(
+                            FlakeRef(Input::fromURL(parsedURL), get(parsedURL.query, "dir").value_or("")),
+                            fragment);
+                    }
+
+                    subdir = std::string(baseNameOf(flakeRoot)) + (subdir.empty() ? "" : "/" + subdir);
+                    flakeRoot = dirOf(flakeRoot);
+                }
             }
 
         } else {
diff --git a/src/libexpr/flake/flakeref.hh b/src/libexpr/flake/flakeref.hh
index 0292eb210..1fddfd9a0 100644
--- a/src/libexpr/flake/flakeref.hh
+++ b/src/libexpr/flake/flakeref.hh
@@ -62,13 +62,19 @@ struct FlakeRef
 std::ostream & operator << (std::ostream & str, const FlakeRef & flakeRef);
 
 FlakeRef parseFlakeRef(
-    const std::string & url, const std::optional<Path> & baseDir = {}, bool allowMissing = false);
+    const std::string & url,
+    const std::optional<Path> & baseDir = {},
+    bool allowMissing = false,
+    bool isFlake = true);
 
 std::optional<FlakeRef> maybeParseFlake(
     const std::string & url, const std::optional<Path> & baseDir = {});
 
 std::pair<FlakeRef, std::string> parseFlakeRefWithFragment(
-    const std::string & url, const std::optional<Path> & baseDir = {}, bool allowMissing = false);
+    const std::string & url,
+    const std::optional<Path> & baseDir = {},
+    bool allowMissing = false,
+    bool isFlake = true);
 
 std::optional<std::pair<FlakeRef, std::string>> maybeParseFlakeRefWithFragment(
     const std::string & url, const std::optional<Path> & baseDir = {});
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index f774e6493..ed4c47fbb 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -102,9 +102,9 @@ DrvInfo::Outputs DrvInfo::queryOutputs(bool onlyOutputsToInstall)
             state->forceList(*i->value, *i->pos);
 
             /* For each output... */
-            for (unsigned int j = 0; j < i->value->listSize(); ++j) {
+            for (auto elem : i->value->listItems()) {
                 /* Evaluate the corresponding set. */
-                string name = state->forceStringNoCtx(*i->value->listElems()[j], *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);
@@ -128,9 +128,9 @@ DrvInfo::Outputs DrvInfo::queryOutputs(bool onlyOutputsToInstall)
         /* ^ this shows during `nix-env -i` right under the bad derivation */
     if (!outTI->isList()) throw errMsg;
     Outputs result;
-    for (auto i = outTI->listElems(); i != outTI->listElems() + outTI->listSize(); ++i) {
-        if ((*i)->type() != nString) throw errMsg;
-        auto out = outputs.find((*i)->string.s);
+    for (auto elem : outTI->listItems()) {
+        if (elem->type() != nString) throw errMsg;
+        auto out = outputs.find(elem->string.s);
         if (out == outputs.end()) throw errMsg;
         result.insert(*out);
     }
@@ -174,8 +174,8 @@ bool DrvInfo::checkMeta(Value & v)
 {
     state->forceValue(v);
     if (v.type() == nList) {
-        for (unsigned int n = 0; n < v.listSize(); ++n)
-            if (!checkMeta(*v.listElems()[n])) return false;
+        for (auto elem : v.listItems())
+            if (!checkMeta(*elem)) return false;
         return true;
     }
     else if (v.type() == nAttrs) {
@@ -364,10 +364,10 @@ static void getDerivations(EvalState & state, Value & vIn,
     }
 
     else if (v.type() == nList) {
-        for (unsigned int n = 0; n < v.listSize(); ++n) {
-            string pathPrefix2 = addToPath(pathPrefix, (format("%1%") % n).str());
-            if (getDerivation(state, *v.listElems()[n], pathPrefix2, drvs, done, ignoreAssertionFailures))
-                getDerivations(state, *v.listElems()[n], pathPrefix2, autoArgs, drvs, done, ignoreAssertionFailures);
+        for (auto [n, elem] : enumerate(v.listItems())) {
+            string pathPrefix2 = addToPath(pathPrefix, fmt("%d", n));
+            if (getDerivation(state, *elem, pathPrefix2, drvs, done, ignoreAssertionFailures))
+                getDerivations(state, *elem, pathPrefix2, autoArgs, drvs, done, ignoreAssertionFailures);
         }
     }
 
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index dd0031a7c..f7541d32c 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;
+        str << i.second;
     }
     str << ")";
 }
@@ -490,7 +490,7 @@ void ExprConcatStrings::bindVars(const std::shared_ptr<const StaticEnv> &env)
         staticenv = env;
 
     for (auto & i : *es)
-        i->bindVars(env);
+        i.second->bindVars(env);
 }
 
 void ExprPos::bindVars(const std::shared_ptr<const StaticEnv> &env)
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
index bfa215fda..c4c459f0b 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -354,8 +354,8 @@ struct ExprConcatStrings : Expr
 {
     Pos pos;
     bool forceString;
-    vector<Expr *> * es;
-    ExprConcatStrings(const Pos & pos, bool forceString, vector<Expr *> * es)
+    vector<std::pair<Pos, Expr *> > * es;
+    ExprConcatStrings(const Pos & pos, bool forceString, vector<std::pair<Pos, Expr *> > * es)
         : pos(pos), forceString(forceString), es(es) { };
     Pos* getPos() { return &pos; }
     COMMON_METHODS
@@ -392,6 +392,13 @@ struct StaticEnv
             [](const Vars::value_type & a, const Vars::value_type & b) { return a.first < b.first; });
     }
 
+    void deduplicate()
+    {
+        const auto last = std::unique(vars.begin(), vars.end(),
+            [] (const Vars::value_type & a, const Vars::value_type & b) { return a.first == b.first; });
+        vars.erase(last, vars.end());
+    }
+
     Vars::const_iterator find(const Symbol & name) const
     {
         Vars::value_type key(name, 0);
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index c537aa0c2..db2d4e204 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -153,7 +153,7 @@ static void addFormal(const Pos & pos, Formals * formals, const Formal & formal)
 }
 
 
-static Expr * stripIndentation(const Pos & pos, SymbolTable & symbols, vector<Expr *> & es)
+static Expr * stripIndentation(const Pos & pos, SymbolTable & symbols, vector<std::pair<Pos, Expr *> > & es)
 {
     if (es.empty()) return new ExprString(symbols.create(""));
 
@@ -163,7 +163,7 @@ static Expr * stripIndentation(const Pos & pos, SymbolTable & symbols, vector<Ex
     bool atStartOfLine = true; /* = seen only whitespace in the current line */
     size_t minIndent = 1000000;
     size_t curIndent = 0;
-    for (auto & i : es) {
+    for (auto & [i_pos, i] : es) {
         ExprIndStr * e = dynamic_cast<ExprIndStr *>(i);
         if (!e) {
             /* Anti-quotations end the current start-of-line whitespace. */
@@ -193,12 +193,12 @@ static Expr * stripIndentation(const Pos & pos, SymbolTable & symbols, vector<Ex
     }
 
     /* Strip spaces from each line. */
-    vector<Expr *> * es2 = new vector<Expr *>;
+    vector<std::pair<Pos, Expr *> > * es2 = new vector<std::pair<Pos, Expr *> >;
     atStartOfLine = true;
     size_t curDropped = 0;
     size_t n = es.size();
-    for (vector<Expr *>::iterator i = es.begin(); i != es.end(); ++i, --n) {
-        ExprIndStr * e = dynamic_cast<ExprIndStr *>(*i);
+    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;
@@ -235,11 +235,11 @@ static Expr * stripIndentation(const Pos & pos, SymbolTable & symbols, vector<Ex
                 s2 = string(s2, 0, p + 1);
         }
 
-        es2->push_back(new ExprString(symbols.create(s2)));
+        es2->emplace_back(i->first, new ExprString(symbols.create(s2)));
     }
 
     /* If this is a single string, then don't do a concatenation. */
-    return es2->size() == 1 && dynamic_cast<ExprString *>((*es2)[0]) ? (*es2)[0] : new ExprConcatStrings(pos, true, es2);
+    return es2->size() == 1 && dynamic_cast<ExprString *>((*es2)[0].second) ? (*es2)[0].second : new ExprConcatStrings(pos, true, es2);
 }
 
 
@@ -278,7 +278,7 @@ void yyerror(YYLTYPE * loc, yyscan_t scanner, ParseData * data, const char * err
   char * path;
   char * uri;
   std::vector<nix::AttrName> * attrNames;
-  std::vector<nix::Expr *> * string_parts;
+  std::vector<std::pair<nix::Pos, nix::Expr *> > * string_parts;
 }
 
 %type <e> start expr expr_function expr_if expr_op
@@ -365,7 +365,7 @@ expr_op
   | expr_op UPDATE expr_op { $$ = new ExprOpUpdate(CUR_POS, $1, $3); }
   | expr_op '?' attrpath { $$ = new ExprOpHasAttr($1, *$3); }
   | expr_op '+' expr_op
-    { $$ = new ExprConcatStrings(CUR_POS, false, new vector<Expr *>({$1, $3})); }
+    { $$ = new ExprConcatStrings(CUR_POS, false, new vector<std::pair<Pos, Expr *> >({{makeCurPos(@1, data), $1}, {makeCurPos(@3, data), $3}})); }
   | expr_op '-' expr_op { $$ = new ExprCall(CUR_POS, new ExprVar(data->symbols.create("__sub")), {$1, $3}); }
   | expr_op '*' expr_op { $$ = new ExprCall(CUR_POS, new ExprVar(data->symbols.create("__mul")), {$1, $3}); }
   | expr_op '/' expr_op { $$ = new ExprCall(CUR_POS, new ExprVar(data->symbols.create("__div")), {$1, $3}); }
@@ -411,7 +411,7 @@ expr_simple
   }
   | path_start PATH_END { $$ = $1; }
   | path_start string_parts_interpolated PATH_END {
-      $2->insert($2->begin(), $1);
+      $2->insert($2->begin(), {makeCurPos(@1, data), $1});
       $$ = new ExprConcatStrings(CUR_POS, false, $2);
   }
   | SPATH {
@@ -449,13 +449,13 @@ string_parts
   ;
 
 string_parts_interpolated
-  : string_parts_interpolated STR { $$ = $1; $1->push_back($2); }
-  | string_parts_interpolated DOLLAR_CURLY expr '}' { $$ = $1; $1->push_back($3); }
-  | DOLLAR_CURLY expr '}' { $$ = new vector<Expr *>; $$->push_back($2); }
+  : string_parts_interpolated STR { $$ = $1; $1->emplace_back(makeCurPos(@2, data), $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<Expr *>;
-      $$->push_back($1);
-      $$->push_back($3);
+      $$ = new vector<std::pair<Pos, Expr *> >;
+      $$->emplace_back(makeCurPos(@1, data), $1);
+      $$->emplace_back(makeCurPos(@2, data), $3);
     }
   ;
 
@@ -474,9 +474,9 @@ path_start
   ;
 
 ind_string_parts
-  : ind_string_parts IND_STR { $$ = $1; $1->push_back($2); }
-  | ind_string_parts DOLLAR_CURLY expr '}' { $$ = $1; $1->push_back($3); }
-  | { $$ = new vector<Expr *>; }
+  : 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 *> >; }
   ;
 
 binds
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 2638b0076..66265f917 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -35,9 +35,10 @@ namespace nix {
 InvalidPathError::InvalidPathError(const Path & path) :
     EvalError("path '%s' is not valid", path), path(path) {}
 
-void EvalState::realiseContext(const PathSet & context)
+StringMap EvalState::realiseContext(const PathSet & context)
 {
     std::vector<DerivedPath::Built> drvs;
+    StringMap res;
 
     for (auto & i : context) {
         auto [ctxS, outputName] = decodeContext(i);
@@ -46,10 +47,12 @@ void EvalState::realiseContext(const PathSet & context)
             throw InvalidPathError(store->printStorePath(ctx));
         if (!outputName.empty() && ctx.isDerivation()) {
             drvs.push_back({ctx, {outputName}});
+        } else {
+            res.insert_or_assign(ctxS, ctxS);
         }
     }
 
-    if (drvs.empty()) return;
+    if (drvs.empty()) return {};
 
     if (!evalSettings.enableImportFromDerivation)
         throw Error(
@@ -61,19 +64,53 @@ void EvalState::realiseContext(const PathSet & context)
     for (auto & d : drvs) buildReqs.emplace_back(DerivedPath { d });
     store->buildPaths(buildReqs);
 
+    /* Get all the output paths corresponding to the placeholders we had */
+    for (auto & [drvPath, outputs] : drvs) {
+        auto outputPaths = store->queryDerivationOutputMap(drvPath);
+        for (auto & outputName : outputs) {
+            if (outputPaths.count(outputName) == 0)
+                throw Error("derivation '%s' does not have an output named '%s'",
+                        store->printStorePath(drvPath), outputName);
+            res.insert_or_assign(
+                downstreamPlaceholder(*store, drvPath, outputName),
+                store->printStorePath(outputPaths.at(outputName))
+            );
+        }
+    }
+
     /* Add the output of this derivations to the allowed
        paths. */
     if (allowedPaths) {
-        for (auto & [drvPath, outputs] : drvs) {
-            auto outputPaths = store->queryDerivationOutputMap(drvPath);
-            for (auto & outputName : outputs) {
-                if (outputPaths.count(outputName) == 0)
-                    throw Error("derivation '%s' does not have an output named '%s'",
-                            store->printStorePath(drvPath), outputName);
-                allowPath(outputPaths.at(outputName));
-            }
+        for (auto & [_placeholder, outputPath] : res) {
+            allowPath(store->toRealPath(outputPath));
         }
     }
+
+    return res;
+}
+
+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;
+};
+
+static Path realisePath(EvalState & state, const Pos & pos, Value & v, const RealisePathFlags flags = {})
+{
+    PathSet context;
+
+    Path path = flags.requireAbsolutePath
+        ? state.coerceToPath(pos, v, context)
+        : state.coerceToString(pos, v, context, false, false);
+
+    StringMap rewrites = state.realiseContext(context);
+
+    auto realPath = state.toRealPath(rewriteStrings(path, rewrites), context);
+
+    return flags.checkForPureEval
+        ? state.checkSourcePath(realPath)
+        : realPath;
 }
 
 /* Add and attribute to the given attribute map from the output name to
@@ -109,11 +146,9 @@ static void mkOutputString(EvalState & state, Value & v,
    argument. */
 static void import(EvalState & state, const Pos & pos, Value & vPath, Value * vScope, Value & v)
 {
-    PathSet context;
-    Path path = state.coerceToPath(pos, vPath, context);
-
+    Path path;
     try {
-        state.realiseContext(context);
+        path = realisePath(state, pos, vPath);
     } catch (InvalidPathError & e) {
         throw EvalError({
             .msg = hintfmt("cannot import '%1%', since path '%2%' is not valid", path, e.path),
@@ -124,8 +159,6 @@ static void import(EvalState & state, const Pos & pos, Value & vPath, Value * vS
         throw;
     }
 
-    Path realPath = state.checkSourcePath(state.toRealPath(path, context));
-
     // FIXME
     auto isValidDerivationInStore = [&]() -> std::optional<StorePath> {
         if (!state.store->isStorePath(path))
@@ -177,7 +210,7 @@ static void import(EvalState & state, const Pos & pos, Value & vPath, Value * vS
 
     else {
         if (!vScope)
-            state.evalFile(realPath, v);
+            state.evalFile(path, v);
         else {
             state.forceAttrs(*vScope);
 
@@ -195,8 +228,8 @@ static void import(EvalState & state, const Pos & pos, Value & vPath, Value * vS
             // No need to call staticEnv.sort(), because
             // args[0]->attrs is already sorted.
 
-            printTalkative("evaluating file '%1%'", realPath);
-            Expr * e = state.parseExprFromFile(resolveExprPath(realPath), staticEnv);
+            printTalkative("evaluating file '%1%'", path);
+            Expr * e = state.parseExprFromFile(resolveExprPath(path), staticEnv);
 
             e->eval(state, *env, v);
         }
@@ -281,22 +314,19 @@ extern "C" typedef void (*ValueInitializer)(EvalState & state, Value & v);
 /* Load a ValueInitializer from a DSO and return whatever it initializes */
 void prim_importNative(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    PathSet context;
-    Path path = state.coerceToPath(pos, *args[0], context);
-
+    Path path;
     try {
-        state.realiseContext(context);
+        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),
+            .msg = hintfmt("cannot import '%1%', since path '%2%' is not valid", path, e.path),
             .errPos = pos
         });
+    } catch (Error & e) {
+        e.addTrace(pos, "while importing '%s'", path);
+        throw;
     }
 
-    path = state.checkSourcePath(path);
-
     string sym = state.forceStringNoCtx(*args[1], pos);
 
     void *handle = dlopen(path.c_str(), RTLD_LAZY | RTLD_LOCAL);
@@ -335,11 +365,10 @@ void prim_exec(EvalState & state, const Pos & pos, Value * * args, Value & v)
     PathSet context;
     auto program = state.coerceToString(pos, *elems[0], context, false, false);
     Strings commandArgs;
-    for (unsigned int i = 1; i < args[0]->listSize(); ++i) {
+    for (unsigned int i = 1; i < args[0]->listSize(); ++i)
         commandArgs.emplace_back(state.coerceToString(pos, *elems[i], context, false, false));
-    }
     try {
-        state.realiseContext(context);
+        auto _ = state.realiseContext(context); // FIXME: Handle CA derivations
     } catch (InvalidPathError & e) {
         throw EvalError({
             .msg = hintfmt("cannot execute '%1%', since path '%2%' is not valid",
@@ -616,8 +645,8 @@ static void prim_genericClosure(EvalState & state, const Pos & pos, Value * * ar
     state.forceList(*startSet->value, pos);
 
     ValueList workSet;
-    for (unsigned int n = 0; n < startSet->value->listSize(); ++n)
-        workSet.push_back(startSet->value->listElems()[n]);
+    for (auto elem : startSet->value->listItems())
+        workSet.push_back(elem);
 
     /* Get the operator. */
     Bindings::iterator op = getAttr(
@@ -662,9 +691,9 @@ static void prim_genericClosure(EvalState & state, const Pos & pos, Value * * ar
         state.forceList(call, pos);
 
         /* Add the values returned by the operator to the work set. */
-        for (unsigned int n = 0; n < call.listSize(); ++n) {
-            state.forceValue(*call.listElems()[n], pos);
-            workSet.push_back(call.listElems()[n]);
+        for (auto elem : call.listItems()) {
+            state.forceValue(*elem, pos);
+            workSet.push_back(elem);
         }
     }
 
@@ -1013,8 +1042,8 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
                command-line arguments to the builder. */
             else if (i->name == state.sArgs) {
                 state.forceList(*i->value, pos);
-                for (unsigned int n = 0; n < i->value->listSize(); ++n) {
-                    string s = state.coerceToString(posDrvName, *i->value->listElems()[n], context, true);
+                for (auto elem : i->value->listItems()) {
+                    string s = state.coerceToString(posDrvName, *elem, context, true);
                     drv.args.push_back(s);
                 }
             }
@@ -1044,8 +1073,8 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
                         /* Require ‘outputs’ to be a list of strings. */
                         state.forceList(*i->value, posDrvName);
                         Strings ss;
-                        for (unsigned int n = 0; n < i->value->listSize(); ++n)
-                            ss.emplace_back(state.forceStringNoCtx(*i->value->listElems()[n], posDrvName));
+                        for (auto elem : i->value->listItems())
+                            ss.emplace_back(state.forceStringNoCtx(*elem, posDrvName));
                         handleOutputs(ss);
                     }
 
@@ -1350,10 +1379,14 @@ static RegisterPrimOp primop_storePath({
 
 static void prim_pathExists(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    PathSet context;
-    Path path = state.coerceToPath(pos, *args[0], context);
+    Path path;
     try {
-        state.realiseContext(context);
+        // 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(
@@ -1427,17 +1460,16 @@ static RegisterPrimOp primop_dirOf({
 /* Return the contents of a file as a string. */
 static void prim_readFile(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    PathSet context;
-    Path path = state.coerceToPath(pos, *args[0], context);
+    Path path;
     try {
-        state.realiseContext(context);
+        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
         });
     }
-    string s = readFile(state.checkSourcePath(state.toRealPath(path, context)));
+    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());
@@ -1460,28 +1492,26 @@ static void prim_findFile(EvalState & state, const Pos & pos, Value * * args, Va
 
     SearchPath searchPath;
 
-    for (unsigned int n = 0; n < args[0]->listSize(); ++n) {
-        Value & v2(*args[0]->listElems()[n]);
-        state.forceAttrs(v2, pos);
+    for (auto v2 : args[0]->listItems()) {
+        state.forceAttrs(*v2, pos);
 
         string prefix;
-        Bindings::iterator i = v2.attrs->find(state.symbols.create("prefix"));
-        if (i != v2.attrs->end())
+        Bindings::iterator i = v2->attrs->find(state.symbols.create("prefix"));
+        if (i != v2->attrs->end())
             prefix = state.forceStringNoCtx(*i->value, pos);
 
         i = getAttr(
             state,
             "findFile",
             "path",
-            v2.attrs,
+            v2->attrs,
             pos
         );
 
-        PathSet context;
-        string path = state.coerceToString(pos, *i->value, context, false, false);
+        Path path;
 
         try {
-            state.realiseContext(context);
+            path = realisePath(state, pos, *i->value, { .requireAbsolutePath = false });
         } catch (InvalidPathError & e) {
             throw EvalError({
                 .msg = hintfmt("cannot find '%1%', since path '%2%' is not valid", path, e.path),
@@ -1514,15 +1544,14 @@ static void prim_hashFile(EvalState & state, const Pos & pos, Value * * args, Va
             .errPos = pos
         });
 
-    PathSet context;
-    Path path = state.coerceToPath(pos, *args[1], context);
+    Path path;
     try {
-        state.realiseContext(context);
+        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);
     }
 
-    mkString(v, hashFile(*ht, state.checkSourcePath(state.toRealPath(path, context))).to_string(Base16, false));
+    mkString(v, hashFile(*ht, path).to_string(Base16, false));
 }
 
 static RegisterPrimOp primop_hashFile({
@@ -1539,10 +1568,9 @@ static RegisterPrimOp primop_hashFile({
 /* Read a directory (without . or ..) */
 static void prim_readDir(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    PathSet ctx;
-    Path path = state.coerceToPath(pos, *args[0], ctx);
+    Path path;
     try {
-        state.realiseContext(ctx);
+        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),
@@ -1550,7 +1578,7 @@ static void prim_readDir(EvalState & state, const Pos & pos, Value * * args, Val
         });
     }
 
-    DirEntries entries = readDirectory(state.checkSourcePath(path));
+    DirEntries entries = readDirectory(path);
     state.mkAttrs(v, entries.size());
 
     for (auto & ent : entries) {
@@ -1877,7 +1905,8 @@ static void addPath(
     try {
         // FIXME: handle CA derivation outputs (where path needs to
         // be rewritten to the actual output).
-        state.realiseContext(context);
+        auto rewrites = state.realiseContext(context);
+        path = state.toRealPath(rewriteStrings(path, rewrites), context);
 
         StorePathSet refs;
 
@@ -2239,9 +2268,9 @@ static void prim_removeAttrs(EvalState & state, const Pos & pos, Value * * args,
 
     /* Get the attribute names to be removed. */
     std::set<Symbol> names;
-    for (unsigned int i = 0; i < args[1]->listSize(); ++i) {
-        state.forceStringNoCtx(*args[1]->listElems()[i], pos);
-        names.insert(state.symbols.create(args[1]->listElems()[i]->string.s));
+    for (auto elem : args[1]->listItems()) {
+        state.forceStringNoCtx(*elem, pos);
+        names.insert(state.symbols.create(elem->string.s));
     }
 
     /* Copy all attributes not in that set.  Note that we don't need
@@ -2249,7 +2278,7 @@ static void prim_removeAttrs(EvalState & state, const Pos & pos, Value * * args,
        vector. */
     state.mkAttrs(v, args[0]->attrs->size());
     for (auto & i : *args[0]->attrs) {
-        if (names.find(i.name) == names.end())
+        if (!names.count(i.name))
             v.attrs->push_back(i);
     }
 }
@@ -2283,15 +2312,14 @@ static void prim_listToAttrs(EvalState & state, const Pos & pos, Value * * args,
 
     std::set<Symbol> seen;
 
-    for (unsigned int i = 0; i < args[0]->listSize(); ++i) {
-        Value & v2(*args[0]->listElems()[i]);
-        state.forceAttrs(v2, pos);
+    for (auto v2 : args[0]->listItems()) {
+        state.forceAttrs(*v2, pos);
 
         Bindings::iterator j = getAttr(
             state,
             "listToAttrs",
             state.sName,
-            v2.attrs,
+            v2->attrs,
             pos
         );
 
@@ -2303,7 +2331,7 @@ static void prim_listToAttrs(EvalState & state, const Pos & pos, Value * * args,
                 state,
                 "listToAttrs",
                 state.sValue,
-                v2.attrs,
+                v2->attrs,
                 pos
             );
             v.attrs->push_back(Attr(sym, j2->value, j2->pos));
@@ -2370,11 +2398,10 @@ static void prim_catAttrs(EvalState & state, const Pos & pos, Value * * args, Va
     Value * res[args[1]->listSize()];
     unsigned int found = 0;
 
-    for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
-        Value & v2(*args[1]->listElems()[n]);
-        state.forceAttrs(v2, pos);
-        Bindings::iterator i = v2.attrs->find(attrName);
-        if (i != v2.attrs->end())
+    for (auto v2 : args[1]->listItems()) {
+        state.forceAttrs(*v2, pos);
+        Bindings::iterator i = v2->attrs->find(attrName);
+        if (i != v2->attrs->end())
             res[found++] = i->value;
     }
 
@@ -2649,8 +2676,8 @@ static void prim_elem(EvalState & state, const Pos & pos, Value * * args, Value
 {
     bool res = false;
     state.forceList(*args[1], pos);
-    for (unsigned int n = 0; n < args[1]->listSize(); ++n)
-        if (state.eqValues(*args[0], *args[1]->listElems()[n])) {
+    for (auto elem : args[1]->listItems())
+        if (state.eqValues(*args[0], *elem)) {
             res = true;
             break;
         }
@@ -2709,8 +2736,8 @@ static void prim_foldlStrict(EvalState & state, const Pos & pos, Value * * args,
     if (args[2]->listSize()) {
         Value * vCur = args[1];
 
-        for (unsigned int n = 0; n < args[2]->listSize(); ++n) {
-            Value * vs []{vCur, args[2]->listElems()[n]};
+        for (auto [n, elem] : enumerate(args[2]->listItems())) {
+            Value * vs []{vCur, elem};
             vCur = n == args[2]->listSize() - 1 ? &v : state.allocValue();
             state.callFunction(*args[0], 2, vs, *vCur, pos);
         }
@@ -2740,8 +2767,8 @@ static void anyOrAll(bool any, EvalState & state, const Pos & pos, Value * * arg
     state.forceList(*args[1], pos);
 
     Value vTmp;
-    for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
-        state.callFunction(*args[0], *args[1]->listElems()[n], vTmp, pos);
+    for (auto elem : args[1]->listItems()) {
+        state.callFunction(*args[0], *elem, vTmp, pos);
         bool res = state.forceBool(vTmp, pos);
         if (res == any) {
             mkBool(v, any);
@@ -2932,6 +2959,56 @@ static RegisterPrimOp primop_partition({
     .fun = prim_partition,
 });
 
+static void prim_groupBy(EvalState & state, const Pos & pos, Value * * args, Value & v)
+{
+    state.forceFunction(*args[0], pos);
+    state.forceList(*args[1], pos);
+
+    ValueVectorMap attrs;
+
+    for (auto vElem : args[1]->listItems()) {
+        Value res;
+        state.callFunction(*args[0], *vElem, res, pos);
+        string 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());
+
+    for (auto & i : attrs) {
+        Value * list = state.allocAttr(v, i.first);
+        auto size = i.second.size();
+        state.mkList(*list, size);
+        memcpy(list->listElems(), i.second.data(), sizeof(Value *) * size);
+    }
+}
+
+static RegisterPrimOp primop_groupBy({
+    .name = "__groupBy",
+    .args = {"f", "list"},
+    .doc = R"(
+      Groups elements of *list* together by the string returned from the
+      function *f* called on each element. It returns an attribute set
+      where each attribute value contains the elements of *list* that are
+      mapped to the same corresponding attribute name returned by *f*.
+
+      For example,
+
+      ```nix
+      builtins.groupBy (builtins.substring 0 1) ["foo" "bar" "baz"]
+      ```
+
+      evaluates to
+
+      ```nix
+      { b = [ "bar" "baz" ]; f = [ "foo" ]; }
+      ```
+    )",
+    .fun = prim_groupBy,
+});
+
 static void prim_concatMap(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceFunction(*args[0], pos);
@@ -3470,9 +3547,9 @@ static void prim_concatStringsSep(EvalState & state, const Pos & pos, Value * *
     res.reserve((args[1]->listSize() + 32) * sep.size());
     bool first = true;
 
-    for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
+    for (auto elem : args[1]->listItems()) {
         if (first) first = false; else res += sep;
-        res += state.coerceToString(pos, *args[1]->listElems()[n], context);
+        res += state.coerceToString(pos, *elem, context);
     }
 
     mkString(v, res, context);
@@ -3501,14 +3578,14 @@ static void prim_replaceStrings(EvalState & state, const Pos & pos, Value * * ar
 
     vector<string> from;
     from.reserve(args[0]->listSize());
-    for (unsigned int n = 0; n < args[0]->listSize(); ++n)
-        from.push_back(state.forceString(*args[0]->listElems()[n], pos));
+    for (auto elem : args[0]->listItems())
+        from.push_back(state.forceString(*elem, pos));
 
     vector<std::pair<string, PathSet>> to;
     to.reserve(args[1]->listSize());
-    for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
+    for (auto elem : args[1]->listItems()) {
         PathSet ctx;
-        auto s = state.forceString(*args[1]->listElems()[n], ctx, pos);
+        auto s = state.forceString(*elem, ctx, pos);
         to.push_back(std::make_pair(std::move(s), std::move(ctx)));
     }
 
@@ -3736,7 +3813,7 @@ void EvalState::createBaseEnv()
                 .fun = primOp.fun,
                 .arity = std::max(primOp.args.size(), primOp.arity),
                 .name = symbols.create(primOp.name),
-                .args = std::move(primOp.args),
+                .args = primOp.args,
                 .doc = primOp.doc,
             });
 
diff --git a/src/libexpr/primops/context.cc b/src/libexpr/primops/context.cc
index 31cf812b4..20545afd0 100644
--- a/src/libexpr/primops/context.cc
+++ b/src/libexpr/primops/context.cc
@@ -118,9 +118,8 @@ static void prim_getContext(EvalState & state, const Pos & pos, Value * * args,
             auto & outputsVal = *state.allocAttr(infoVal, state.sOutputs);
             state.mkList(outputsVal, info.second.outputs.size());
             size_t i = 0;
-            for (const auto & output : info.second.outputs) {
+            for (const auto & output : info.second.outputs)
                 mkString(*(outputsVal.listElems()[i++] = state.allocValue()), output);
-            }
         }
         infoVal.attrs->sort();
     }
@@ -181,8 +180,8 @@ static void prim_appendContext(EvalState & state, const Pos & pos, Value * * arg
                     .errPos = *i.pos
                 });
             }
-            for (unsigned int n = 0; n < iter->value->listSize(); ++n) {
-                auto name = state.forceStringNoCtx(*iter->value->listElems()[n], *iter->pos);
+            for (auto elem : iter->value->listItems()) {
+                auto name = state.forceStringNoCtx(*elem, *iter->pos);
                 context.insert("!" + name + "!" + string(i.name));
             }
         }
diff --git a/src/libexpr/primops/fromTOML.cc b/src/libexpr/primops/fromTOML.cc
index 4c6682dfd..30466fc5b 100644
--- a/src/libexpr/primops/fromTOML.cc
+++ b/src/libexpr/primops/fromTOML.cc
@@ -1,86 +1,79 @@
 #include "primops.hh"
 #include "eval-inline.hh"
 
-#include "../../cpptoml/cpptoml.h"
+#include "../../toml11/toml.hpp"
 
 namespace nix {
 
-static void prim_fromTOML(EvalState & state, const Pos & pos, Value * * args, Value & v)
+static void prim_fromTOML(EvalState & state, const Pos & pos, Value * * args, Value & val)
 {
-    using namespace cpptoml;
-
     auto toml = state.forceStringNoCtx(*args[0], pos);
 
     std::istringstream tomlStream(toml);
 
-    std::function<void(Value &, std::shared_ptr<base>)> visit;
-
-    visit = [&](Value & v, std::shared_ptr<base> t) {
-
-        if (auto t2 = t->as_table()) {
-
-            size_t size = 0;
-            for (auto & i : *t2) { (void) i; size++; }
-
-            state.mkAttrs(v, size);
-
-            for (auto & i : *t2) {
-                auto & v2 = *state.allocAttr(v, state.symbols.create(i.first));
-
-                if (auto i2 = i.second->as_table_array()) {
-                    size_t size2 = i2->get().size();
-                    state.mkList(v2, size2);
-                    for (size_t j = 0; j < size2; ++j)
-                        visit(*(v2.listElems()[j] = state.allocValue()), i2->get()[j]);
-                }
-                else
-                    visit(v2, i.second);
-            }
+    std::function<void(Value &, toml::value)> visit;
 
-            v.attrs->sort();
-        }
+    visit = [&](Value & v, toml::value t) {
 
-        else if (auto t2 = t->as_array()) {
-            size_t size = t2->get().size();
+        switch(t.type())
+        {
+            case toml::value_t::table:
+                {
+                    auto table = toml::get<toml::table>(t);
 
-            state.mkList(v, size);
+                    size_t size = 0;
+                    for (auto & i : table) { (void) i; size++; }
 
-            for (size_t i = 0; i < size; ++i)
-                visit(*(v.listElems()[i] = state.allocValue()), t2->get()[i]);
-        }
+                    state.mkAttrs(v, size);
 
-        // Handle cases like 'a = [[{ a = true }]]', which IMHO should be
-        // parsed as a array containing an array containing a table,
-        // but instead are parsed as an array containing a table array
-        // containing a table.
-        else if (auto t2 = t->as_table_array()) {
-            size_t size = t2->get().size();
+                    for(auto & elem: table) {
 
-            state.mkList(v, size);
+                        auto & v2 = *state.allocAttr(v, state.symbols.create(elem.first));
+                        visit(v2, elem.second);
+                    }
 
-            for (size_t j = 0; j < size; ++j)
-                visit(*(v.listElems()[j] = state.allocValue()), t2->get()[j]);
-        }
+                    v.attrs->sort();
+                }
+                break;;
+            case toml::value_t::array:
+                {
+                    auto array = toml::get<std::vector<toml::value>>(t);
+
+                    size_t size = array.size();
+                    state.mkList(v, size);
+                    for (size_t i = 0; i < size; ++i)
+                        visit(*(v.listElems()[i] = state.allocValue()), array[i]);
+                }
+                break;;
+            case toml::value_t::boolean:
+                mkBool(v, toml::get<bool>(t));
+                break;;
+            case toml::value_t::integer:
+                mkInt(v, toml::get<int64_t>(t));
+                break;;
+            case toml::value_t::floating:
+                mkFloat(v, toml::get<NixFloat>(t));
+                break;;
+            case toml::value_t::string:
+                mkString(v, toml::get<std::string>(t));
+                break;;
+            case toml::value_t::local_datetime:
+            case toml::value_t::offset_datetime:
+            case toml::value_t::local_date:
+            case toml::value_t::local_time:
+                // We fail since Nix doesn't have date and time types
+                throw std::runtime_error("Dates and times are not supported");
+                break;;
+            case toml::value_t::empty:
+                mkNull(v);
+                break;;
 
-        else if (t->is_value()) {
-            if (auto val = t->as<int64_t>())
-                mkInt(v, val->get());
-            else if (auto val = t->as<NixFloat>())
-                mkFloat(v, val->get());
-            else if (auto val = t->as<bool>())
-                mkBool(v, val->get());
-            else if (auto val = t->as<std::string>())
-                mkString(v, val->get());
-            else
-                throw EvalError("unsupported value type in TOML");
         }
-
-        else abort();
     };
 
     try {
-        visit(v, parser(tomlStream).parse());
-    } catch (std::runtime_error & e) {
+        visit(val, toml::parse(tomlStream, "fromTOML" /* the "filename" */));
+    } catch (std::exception & e) { // TODO: toml::syntax_error
         throw EvalError({
             .msg = hintfmt("while parsing a TOML string: %s", e.what()),
             .errPos = pos
diff --git a/src/libexpr/value-to-json.cc b/src/libexpr/value-to-json.cc
index 4d642c720..517da4c01 100644
--- a/src/libexpr/value-to-json.cc
+++ b/src/libexpr/value-to-json.cc
@@ -63,9 +63,9 @@ void printValueAsJSON(EvalState & state, bool strict,
 
         case nList: {
             auto list(out.list());
-            for (unsigned int n = 0; n < v.listSize(); ++n) {
+            for (auto elem : v.listItems()) {
                 auto placeholder(list.placeholder());
-                printValueAsJSON(state, strict, *v.listElems()[n], pos, placeholder, context);
+                printValueAsJSON(state, strict, *elem, pos, placeholder, context);
             }
             break;
         }
diff --git a/src/libexpr/value-to-xml.cc b/src/libexpr/value-to-xml.cc
index 54268ece0..a875f82d7 100644
--- a/src/libexpr/value-to-xml.cc
+++ b/src/libexpr/value-to-xml.cc
@@ -122,8 +122,8 @@ static void printValueAsXML(EvalState & state, bool strict, bool location,
 
         case nList: {
             XMLOpenElement _(doc, "list");
-            for (unsigned int n = 0; n < v.listSize(); ++n)
-                printValueAsXML(state, strict, location, *v.listElems()[n], doc, context, drvsSeen, pos);
+            for (auto v2 : v.listItems())
+                printValueAsXML(state, strict, location, *v2, doc, context, drvsSeen, pos);
             break;
         }
 
diff --git a/src/libexpr/value.hh b/src/libexpr/value.hh
index 3bb97b3c2..6b4f3c0ae 100644
--- a/src/libexpr/value.hh
+++ b/src/libexpr/value.hh
@@ -1,5 +1,7 @@
 #pragma once
 
+#include <cassert>
+
 #include "symbol-table.hh"
 
 #if HAVE_BOEHMGC
@@ -350,6 +352,34 @@ public:
     bool isTrivial() const;
 
     std::vector<std::pair<Path, std::string>> getContext();
+
+    auto listItems()
+    {
+        struct ListIterable
+        {
+            typedef Value * const * iterator;
+            iterator _begin, _end;
+            iterator begin() const { return _begin; }
+            iterator end() const { return _end; }
+        };
+        assert(isList());
+        auto begin = listElems();
+        return ListIterable { begin, begin + listSize() };
+    }
+
+    auto listItems() const
+    {
+        struct ConstListIterable
+        {
+            typedef const Value * const * iterator;
+            iterator _begin, _end;
+            iterator begin() const { return _begin; }
+            iterator end() const { return _end; }
+        };
+        assert(isList());
+        auto begin = listElems();
+        return ConstListIterable { begin, begin + listSize() };
+    }
 };
 
 
@@ -395,9 +425,11 @@ 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;
+typedef std::map<Symbol, ValueVector, std::less<Symbol>, traceable_allocator<std::pair<const Symbol, ValueVector> > > ValueVectorMap;
 #else
 typedef std::vector<Value *> ValueVector;
 typedef std::map<Symbol, Value *> ValueMap;
+typedef std::map<Symbol, ValueVector> ValueVectorMap;
 #endif