Merge remote-tracking branch 'origin/master' into auto-uid-allocation

44 files changed, 1259 insertions, 346 deletions

diff --git a/src/libutil/archive.cc b/src/libutil/archive.cc
index eda004756..4b0636129 100644
--- a/src/libutil/archive.cc
+++ b/src/libutil/archive.cc
@@ -64,11 +64,12 @@ static void dumpContents(const Path & path, off_t size,
 }
 
 
-static void dump(const Path & path, Sink & sink, PathFilter & filter)
+static time_t dump(const Path & path, Sink & sink, PathFilter & filter)
 {
     checkInterrupt();
 
     auto st = lstat(path);
+    time_t result = st.st_mtime;
 
     sink << "(";
 
@@ -103,7 +104,10 @@ static void dump(const Path & path, Sink & sink, PathFilter & filter)
         for (auto & i : unhacked)
             if (filter(path + "/" + i.first)) {
                 sink << "entry" << "(" << "name" << i.first << "node";
-                dump(path + "/" + i.second, sink, filter);
+                auto tmp_mtime = dump(path + "/" + i.second, sink, filter);
+                if (tmp_mtime > result) {
+                    result = tmp_mtime;
+                }
                 sink << ")";
             }
     }
@@ -114,13 +118,20 @@ static void dump(const Path & path, Sink & sink, PathFilter & filter)
     else throw Error("file '%1%' has an unsupported type", path);
 
     sink << ")";
+
+    return result;
 }
 
 
-void dumpPath(const Path & path, Sink & sink, PathFilter & filter)
+time_t dumpPathAndGetMtime(const Path & path, Sink & sink, PathFilter & filter)
 {
     sink << narVersionMagic1;
-    dump(path, sink, filter);
+    return dump(path, sink, filter);
+}
+
+void dumpPath(const Path & path, Sink & sink, PathFilter & filter)
+{
+    dumpPathAndGetMtime(path, sink, filter);
 }
 
 
@@ -223,6 +234,7 @@ static void parse(ParseSink & sink, Source & source, const Path & path)
 
         else if (s == "contents" && type == tpRegular) {
             parseContents(sink, source, path);
+            sink.closeRegularFile();
         }
 
         else if (s == "executable" && type == tpRegular) {
@@ -313,6 +325,12 @@ struct RestoreSink : ParseSink
         if (!fd) throw SysError("creating file '%1%'", p);
     }
 
+    void closeRegularFile() override
+    {
+        /* Call close explicitly to make sure the error is checked */
+        fd.close();
+    }
+
     void isExecutable() override
     {
         struct stat st;
diff --git a/src/libutil/archive.hh b/src/libutil/archive.hh
index fca351605..ac4183bf5 100644
--- a/src/libutil/archive.hh
+++ b/src/libutil/archive.hh
@@ -48,6 +48,10 @@ namespace nix {
 void dumpPath(const Path & path, Sink & sink,
     PathFilter & filter = defaultPathFilter);
 
+/* Same as `void dumpPath()`, but returns the last modified date of the path */
+time_t dumpPathAndGetMtime(const Path & path, Sink & sink,
+    PathFilter & filter = defaultPathFilter);
+
 void dumpString(std::string_view s, Sink & sink);
 
 /* FIXME: fix this API, it sucks. */
@@ -56,6 +60,7 @@ struct ParseSink
     virtual void createDirectory(const Path & path) { };
 
     virtual void createRegularFile(const Path & path) { };
+    virtual void closeRegularFile() { };
     virtual void isExecutable() { };
     virtual void preallocateContents(uint64_t size) { };
     virtual void receiveContents(std::string_view data) { };
diff --git a/src/libutil/args.cc b/src/libutil/args.cc
index f970c0e9e..753980fd4 100644
--- a/src/libutil/args.cc
+++ b/src/libutil/args.cc
@@ -124,14 +124,14 @@ bool Args::processFlag(Strings::iterator & pos, Strings::iterator end)
         bool anyCompleted = false;
         for (size_t n = 0 ; n < flag.handler.arity; ++n) {
             if (pos == end) {
-                if (flag.handler.arity == ArityAny) break;
+                if (flag.handler.arity == ArityAny || anyCompleted) break;
                 throw UsageError("flag '%s' requires %d argument(s)", name, flag.handler.arity);
             }
-            if (flag.completer)
-                if (auto prefix = needsCompletion(*pos)) {
-                    anyCompleted = true;
+            if (auto prefix = needsCompletion(*pos)) {
+                anyCompleted = true;
+                if (flag.completer)
                     flag.completer(n, *prefix);
-                }
+            }
             args.push_back(*pos++);
         }
         if (!anyCompleted)
@@ -146,6 +146,7 @@ bool Args::processFlag(Strings::iterator & pos, Strings::iterator end)
                     && hasPrefix(name, std::string(*prefix, 2)))
                     completions->add("--" + name, flag->description);
             }
+            return false;
         }
         auto i = longFlags.find(std::string(*pos, 2));
         if (i == longFlags.end()) return false;
@@ -187,10 +188,12 @@ bool Args::processArgs(const Strings & args, bool finish)
     {
         std::vector<std::string> ss;
         for (const auto &[n, s] : enumerate(args)) {
-            ss.push_back(s);
-            if (exp.completer)
-                if (auto prefix = needsCompletion(s))
+            if (auto prefix = needsCompletion(s)) {
+                ss.push_back(*prefix);
+                if (exp.completer)
                     exp.completer(n, *prefix);
+            } else
+                ss.push_back(s);
         }
         exp.handler.fun(ss);
         expectedArgs.pop_front();
@@ -213,7 +216,7 @@ nlohmann::json Args::toJSON()
         if (flag->shortName)
             j["shortName"] = std::string(1, flag->shortName);
         if (flag->description != "")
-            j["description"] = flag->description;
+            j["description"] = trim(flag->description);
         j["category"] = flag->category;
         if (flag->handler.arity != ArityAny)
             j["arity"] = flag->handler.arity;
@@ -234,7 +237,7 @@ nlohmann::json Args::toJSON()
     }
 
     auto res = nlohmann::json::object();
-    res["description"] = description();
+    res["description"] = trim(description());
     res["flags"] = std::move(flags);
     res["args"] = std::move(args);
     auto s = doc();
@@ -279,21 +282,22 @@ static void _completePath(std::string_view prefix, bool onlyDirs)
 {
     completionType = ctFilenames;
     glob_t globbuf;
-    int flags = GLOB_NOESCAPE | GLOB_TILDE;
+    int flags = GLOB_NOESCAPE;
     #ifdef GLOB_ONLYDIR
     if (onlyDirs)
         flags |= GLOB_ONLYDIR;
     #endif
-    if (glob((std::string(prefix) + "*").c_str(), flags, nullptr, &globbuf) == 0) {
+    // using expandTilde here instead of GLOB_TILDE(_CHECK) so that ~<Tab> expands to /home/user/
+    if (glob((expandTilde(prefix) + "*").c_str(), flags, nullptr, &globbuf) == 0) {
         for (size_t i = 0; i < globbuf.gl_pathc; ++i) {
             if (onlyDirs) {
-                auto st = lstat(globbuf.gl_pathv[i]);
+                auto st = stat(globbuf.gl_pathv[i]);
                 if (!S_ISDIR(st.st_mode)) continue;
             }
             completions->add(globbuf.gl_pathv[i]);
         }
-        globfree(&globbuf);
     }
+    globfree(&globbuf);
 }
 
 void completePath(size_t, std::string_view prefix)
@@ -322,16 +326,21 @@ MultiCommand::MultiCommand(const Commands & commands_)
         .optional = true,
         .handler = {[=](std::string s) {
             assert(!command);
-            if (auto prefix = needsCompletion(s)) {
-                for (auto & [name, command] : commands)
-                    if (hasPrefix(name, *prefix))
-                        completions->add(name);
-            }
             auto i = commands.find(s);
-            if (i == commands.end())
-                throw UsageError("'%s' is not a recognised command", s);
+            if (i == commands.end()) {
+                std::set<std::string> commandNames;
+                for (auto & [name, _] : commands)
+                    commandNames.insert(name);
+                auto suggestions = Suggestions::bestMatches(commandNames, s);
+                throw UsageError(suggestions, "'%s' is not a recognised command", s);
+            }
             command = {s, i->second()};
             command->second->parent = this;
+        }},
+        .completer = {[&](size_t, std::string_view prefix) {
+            for (auto & [name, command] : commands)
+                if (hasPrefix(name, prefix))
+                    completions->add(name);
         }}
     });
 
@@ -353,6 +362,14 @@ bool MultiCommand::processArgs(const Strings & args, bool finish)
         return Args::processArgs(args, finish);
 }
 
+void MultiCommand::completionHook()
+{
+    if (command)
+        return command->second->completionHook();
+    else
+        return Args::completionHook();
+}
+
 nlohmann::json MultiCommand::toJSON()
 {
     auto cmds = nlohmann::json::object();
@@ -362,7 +379,7 @@ nlohmann::json MultiCommand::toJSON()
         auto j = command->toJSON();
         auto cat = nlohmann::json::object();
         cat["id"] = command->category();
-        cat["description"] = categories[command->category()];
+        cat["description"] = trim(categories[command->category()]);
         j["category"] = std::move(cat);
         cmds[name] = std::move(j);
     }
diff --git a/src/libutil/args.hh b/src/libutil/args.hh
index fdd036f9a..84866f12b 100644
--- a/src/libutil/args.hh
+++ b/src/libutil/args.hh
@@ -25,6 +25,8 @@ public:
     /* Return a short one-line description of the command. */
     virtual std::string description() { return ""; }
 
+    virtual bool forceImpureByDefault() { return false; }
+
     /* Return documentation about this command, in Markdown format. */
     virtual std::string doc() { return ""; }
 
@@ -146,6 +148,11 @@ protected:
        argument (if any) have been processed. */
     virtual void initialFlagsProcessed() {}
 
+    /* Called after the command line has been processed if we need to generate
+       completions. Useful for commands that need to know the whole command line
+       in order to know what completions to generate. */
+    virtual void completionHook() { }
+
 public:
 
     void addFlag(Flag && flag);
@@ -221,6 +228,8 @@ public:
 
     bool processArgs(const Strings & args, bool finish) override;
 
+    void completionHook() override;
+
     nlohmann::json toJSON() override;
 };
 
diff --git a/src/libutil/chunked-vector.hh b/src/libutil/chunked-vector.hh
new file mode 100644
index 000000000..0a4f0b400
--- /dev/null
+++ b/src/libutil/chunked-vector.hh
@@ -0,0 +1,68 @@
+#pragma once
+
+#include <cstdint>
+#include <cstdlib>
+#include <vector>
+#include <limits>
+
+namespace nix {
+
+/* Provides an indexable container like vector<> with memory overhead
+   guarantees like list<> by allocating storage in chunks of ChunkSize
+   elements instead of using a contiguous memory allocation like vector<>
+   does. Not using a single vector that is resized reduces memory overhead
+   on large data sets by on average (growth factor)/2, mostly
+   eliminates copies within the vector during resizing, and provides stable
+   references to its elements. */
+template<typename T, size_t ChunkSize>
+class ChunkedVector {
+private:
+    uint32_t size_ = 0;
+    std::vector<std::vector<T>> chunks;
+
+    /* keep this out of the ::add hot path */
+    [[gnu::noinline]]
+    auto & addChunk()
+    {
+        if (size_ >= std::numeric_limits<uint32_t>::max() - ChunkSize)
+            abort();
+        chunks.emplace_back();
+        chunks.back().reserve(ChunkSize);
+        return chunks.back();
+    }
+
+public:
+    ChunkedVector(uint32_t reserve)
+    {
+        chunks.reserve(reserve);
+        addChunk();
+    }
+
+    uint32_t size() const { return size_; }
+
+    std::pair<T &, uint32_t> add(T value)
+    {
+        const auto idx = size_++;
+        auto & chunk = [&] () -> auto & {
+            if (auto & back = chunks.back(); back.size() < ChunkSize)
+                return back;
+            return addChunk();
+        }();
+        auto & result = chunk.emplace_back(std::move(value));
+        return {result, idx};
+    }
+
+    const T & operator[](uint32_t idx) const
+    {
+        return chunks[idx / ChunkSize][idx % ChunkSize];
+    }
+
+    template<typename Fn>
+    void forEach(Fn fn) const
+    {
+        for (const auto & c : chunks)
+            for (const auto & e : c)
+                fn(e);
+    }
+};
+}
diff --git a/src/libutil/error.cc b/src/libutil/error.cc
index dcd2f82a5..9172f67a6 100644
--- a/src/libutil/error.cc
+++ b/src/libutil/error.cc
@@ -9,10 +9,9 @@ namespace nix {
 
 const std::string nativeSystem = SYSTEM;
 
-BaseError & BaseError::addTrace(std::optional<ErrPos> e, hintformat hint)
+void BaseError::addTrace(std::optional<ErrPos> e, hintformat hint)
 {
     err.traces.push_front(Trace { .pos = e, .hint = hint });
-    return *this;
 }
 
 // c++ std::exception descendants must have a 'const char* what()' function.
@@ -22,12 +21,9 @@ const std::string & BaseError::calcWhat() const
     if (what_.has_value())
         return *what_;
     else {
-        err.name = sname();
-
         std::ostringstream oss;
         showErrorInfo(oss, err, loggerSettings.showTrace);
         what_ = oss.str();
-
         return *what_;
     }
 }
@@ -282,6 +278,13 @@ std::ostream & showErrorInfo(std::ostream & out, const ErrorInfo & einfo, bool s
         }
     }
 
+    auto suggestions = einfo.suggestions.trim();
+    if (! suggestions.suggestions.empty()){
+        oss << "Did you mean " <<
+            suggestions.trim() <<
+            "?" << std::endl;
+    }
+
     // traces
     if (showTrace && !einfo.traces.empty()) {
         for (auto iter = einfo.traces.rbegin(); iter != einfo.traces.rend(); ++iter) {
diff --git a/src/libutil/error.hh b/src/libutil/error.hh
index d55e1d701..3d1479c54 100644
--- a/src/libutil/error.hh
+++ b/src/libutil/error.hh
@@ -1,5 +1,6 @@
 #pragma once
 
+#include "suggestions.hh"
 #include "ref.hh"
 #include "types.hh"
 #include "fmt.hh"
@@ -53,6 +54,7 @@ typedef enum {
     lvlVomit
 } Verbosity;
 
+/* adjust Pos::origin bit width when adding stuff here */
 typedef enum {
     foFile,
     foStdin,
@@ -85,11 +87,7 @@ struct ErrPos {
         origin = pos.origin;
         line = pos.line;
         column = pos.column;
-        // is file symbol null?
-        if (pos.file.set())
-            file = pos.file;
-        else
-            file = "";
+        file = pos.file;
         return *this;
     }
 
@@ -100,6 +98,15 @@ struct ErrPos {
     }
 };
 
+std::optional<LinesOfCode> getCodeLines(const ErrPos & errPos);
+
+void printCodeLines(std::ostream & out,
+    const std::string & prefix,
+    const ErrPos & errPos,
+    const LinesOfCode & loc);
+
+void printAtPos(const ErrPos & pos, std::ostream & out);
+
 struct Trace {
     std::optional<ErrPos> pos;
     hintformat hint;
@@ -107,11 +114,12 @@ struct Trace {
 
 struct ErrorInfo {
     Verbosity level;
-    std::string name; // FIXME: rename
     hintformat msg;
     std::optional<ErrPos> errPos;
     std::list<Trace> traces;
 
+    Suggestions suggestions;
+
     static std::optional<std::string> programName;
 };
 
@@ -141,6 +149,11 @@ public:
         : err { .level = lvlError, .msg = hintfmt(fs, args...) }
     { }
 
+    template<typename... Args>
+    BaseError(const Suggestions & sug, const Args & ... args)
+        : err { .level = lvlError, .msg = hintfmt(args...), .suggestions = sug }
+    { }
+
     BaseError(hintformat hint)
         : err { .level = lvlError, .msg = hint }
     { }
@@ -153,8 +166,6 @@ public:
         : err(e)
     { }
 
-    virtual const char* sname() const { return "BaseError"; }
-
 #ifdef EXCEPTION_NEEDS_THROW_SPEC
     ~BaseError() throw () { };
     const char * what() const throw () { return calcWhat().c_str(); }
@@ -166,12 +177,12 @@ public:
     const ErrorInfo & info() const { calcWhat(); return err; }
 
     template<typename... Args>
-    BaseError & addTrace(std::optional<ErrPos> e, const std::string & fs, const Args & ... args)
+    void addTrace(std::optional<ErrPos> e, const std::string & fs, const Args & ... args)
     {
-        return addTrace(e, hintfmt(fs, args...));
+        addTrace(e, hintfmt(fs, args...));
     }
 
-    BaseError & addTrace(std::optional<ErrPos> e, hintformat hint);
+    void addTrace(std::optional<ErrPos> e, hintformat hint);
 
     bool hasTrace() const { return !err.traces.empty(); }
 };
@@ -181,7 +192,6 @@ public:
     {                                                   \
     public:                                             \
         using superClass::superClass;                   \
-        virtual const char* sname() const override { return #newClass; } \
     }
 
 MakeError(Error, BaseError);
@@ -194,15 +204,19 @@ public:
     int errNo;
 
     template<typename... Args>
-    SysError(const Args & ... args)
+    SysError(int errNo_, const Args & ... args)
         : Error("")
     {
-        errNo = errno;
+        errNo = errNo_;
         auto hf = hintfmt(args...);
         err.msg = hintfmt("%1%: %2%", normaltxt(hf.str()), strerror(errNo));
     }
 
-    virtual const char* sname() const override { return "SysError"; }
+    template<typename... Args>
+    SysError(const Args & ... args)
+        : SysError(errno, args ...)
+    {
+    }
 };
 
 }
diff --git a/src/libutil/experimental-features.cc b/src/libutil/experimental-features.cc
index 52ba549a3..30d071408 100644
--- a/src/libutil/experimental-features.cc
+++ b/src/libutil/experimental-features.cc
@@ -7,10 +7,13 @@ namespace nix {
 
 std::map<ExperimentalFeature, std::string> stringifiedXpFeatures = {
     { Xp::CaDerivations, "ca-derivations" },
+    { Xp::ImpureDerivations, "impure-derivations" },
     { Xp::Flakes, "flakes" },
     { Xp::NixCommand, "nix-command" },
     { Xp::RecursiveNix, "recursive-nix" },
     { Xp::NoUrlLiterals, "no-url-literals" },
+    { Xp::FetchClosure, "fetch-closure" },
+    { Xp::ReplFlake, "repl-flake" },
 	{ Xp::AutoAllocateUids, "auto-allocate-uids" },
 	{ Xp::SystemdCgroup, "systemd-cgroup" },
 };
@@ -35,7 +38,9 @@ const std::optional<ExperimentalFeature> parseExperimentalFeature(const std::str
 
 std::string_view showExperimentalFeature(const ExperimentalFeature feature)
 {
-    return stringifiedXpFeatures.at(feature);
+    const auto ret = get(stringifiedXpFeatures, feature);
+    assert(ret);
+    return *ret;
 }
 
 std::set<ExperimentalFeature> parseFeatures(const std::set<std::string> & rawFeatures)
@@ -58,4 +63,20 @@ std::ostream & operator <<(std::ostream & str, const ExperimentalFeature & featu
     return str << showExperimentalFeature(feature);
 }
 
+void to_json(nlohmann::json & j, const ExperimentalFeature & feature)
+{
+    j = showExperimentalFeature(feature);
+}
+
+void from_json(const nlohmann::json & j, ExperimentalFeature & feature)
+{
+    const std::string input = j;
+    const auto parsed = parseExperimentalFeature(input);
+
+    if (parsed.has_value())
+        feature = *parsed;
+    else
+        throw Error("Unknown experimental feature '%s' in JSON input", input);
+}
+
 }
diff --git a/src/libutil/experimental-features.hh b/src/libutil/experimental-features.hh
index 00df8b165..c749d4767 100644
--- a/src/libutil/experimental-features.hh
+++ b/src/libutil/experimental-features.hh
@@ -16,10 +16,13 @@ namespace nix {
 enum struct ExperimentalFeature
 {
     CaDerivations,
+    ImpureDerivations,
     Flakes,
     NixCommand,
     RecursiveNix,
     NoUrlLiterals,
+    FetchClosure,
+    ReplFlake,
     AutoAllocateUids,
     SystemdCgroup,
 };
@@ -49,10 +52,13 @@ public:
     ExperimentalFeature missingFeature;
 
     MissingExperimentalFeature(ExperimentalFeature);
-    virtual const char * sname() const override
-    {
-        return "MissingExperimentalFeature";
-    }
 };
 
+/**
+ * Semi-magic conversion to and from json.
+ * See the nlohmann/json readme for more details.
+ */
+void to_json(nlohmann::json &, const ExperimentalFeature &);
+void from_json(const nlohmann::json &, ExperimentalFeature &);
+
 }
diff --git a/src/libutil/filesystem.cc b/src/libutil/filesystem.cc
new file mode 100644
index 000000000..403389e60
--- /dev/null
+++ b/src/libutil/filesystem.cc
@@ -0,0 +1,172 @@
+#include <sys/time.h>
+#include <filesystem>
+
+#include "finally.hh"
+#include "util.hh"
+#include "types.hh"
+
+namespace fs = std::filesystem;
+
+namespace nix {
+
+static Path tempName(Path tmpRoot, const Path & prefix, bool includePid,
+    int & counter)
+{
+    tmpRoot = canonPath(tmpRoot.empty() ? getEnv("TMPDIR").value_or("/tmp") : tmpRoot, true);
+    if (includePid)
+        return (format("%1%/%2%-%3%-%4%") % tmpRoot % prefix % getpid() % counter++).str();
+    else
+        return (format("%1%/%2%-%3%") % tmpRoot % prefix % counter++).str();
+}
+
+Path createTempDir(const Path & tmpRoot, const Path & prefix,
+    bool includePid, bool useGlobalCounter, mode_t mode)
+{
+    static int globalCounter = 0;
+    int localCounter = 0;
+    int & counter(useGlobalCounter ? globalCounter : localCounter);
+
+    while (1) {
+        checkInterrupt();
+        Path tmpDir = tempName(tmpRoot, prefix, includePid, counter);
+        if (mkdir(tmpDir.c_str(), mode) == 0) {
+#if __FreeBSD__
+            /* Explicitly set the group of the directory.  This is to
+               work around around problems caused by BSD's group
+               ownership semantics (directories inherit the group of
+               the parent).  For instance, the group of /tmp on
+               FreeBSD is "wheel", so all directories created in /tmp
+               will be owned by "wheel"; but if the user is not in
+               "wheel", then "tar" will fail to unpack archives that
+               have the setgid bit set on directories. */
+            if (chown(tmpDir.c_str(), (uid_t) -1, getegid()) != 0)
+                throw SysError("setting group of directory '%1%'", tmpDir);
+#endif
+            return tmpDir;
+        }
+        if (errno != EEXIST)
+            throw SysError("creating directory '%1%'", tmpDir);
+    }
+}
+
+
+std::pair<AutoCloseFD, Path> createTempFile(const Path & prefix)
+{
+    Path tmpl(getEnv("TMPDIR").value_or("/tmp") + "/" + prefix + ".XXXXXX");
+    // Strictly speaking, this is UB, but who cares...
+    // FIXME: use O_TMPFILE.
+    AutoCloseFD fd(mkstemp((char *) tmpl.c_str()));
+    if (!fd)
+        throw SysError("creating temporary file '%s'", tmpl);
+    closeOnExec(fd.get());
+    return {std::move(fd), tmpl};
+}
+
+void createSymlink(const Path & target, const Path & link,
+    std::optional<time_t> mtime)
+{
+    if (symlink(target.c_str(), link.c_str()))
+        throw SysError("creating symlink from '%1%' to '%2%'", link, target);
+    if (mtime) {
+        struct timeval times[2];
+        times[0].tv_sec = *mtime;
+        times[0].tv_usec = 0;
+        times[1].tv_sec = *mtime;
+        times[1].tv_usec = 0;
+        if (lutimes(link.c_str(), times))
+            throw SysError("setting time of symlink '%s'", link);
+    }
+}
+
+void replaceSymlink(const Path & target, const Path & link,
+    std::optional<time_t> mtime)
+{
+    for (unsigned int n = 0; true; n++) {
+        Path tmp = canonPath(fmt("%s/.%d_%s", dirOf(link), n, baseNameOf(link)));
+
+        try {
+            createSymlink(target, tmp, mtime);
+        } catch (SysError & e) {
+            if (e.errNo == EEXIST) continue;
+            throw;
+        }
+
+        renameFile(tmp, link);
+
+        break;
+    }
+}
+
+void setWriteTime(const fs::path & p, const struct stat & st)
+{
+    struct timeval times[2];
+    times[0] = {
+        .tv_sec = st.st_atime,
+        .tv_usec = 0,
+    };
+    times[1] = {
+        .tv_sec = st.st_mtime,
+        .tv_usec = 0,
+    };
+    if (lutimes(p.c_str(), times) != 0)
+        throw SysError("changing modification time of '%s'", p);
+}
+
+void copy(const fs::directory_entry & from, const fs::path & to, bool andDelete)
+{
+    // TODO: Rewrite the `is_*` to use `symlink_status()`
+    auto statOfFrom = lstat(from.path().c_str());
+    auto fromStatus = from.symlink_status();
+
+    // Mark the directory as writable so that we can delete its children
+    if (andDelete && fs::is_directory(fromStatus)) {
+        fs::permissions(from.path(), fs::perms::owner_write, fs::perm_options::add | fs::perm_options::nofollow);
+    }
+
+
+    if (fs::is_symlink(fromStatus) || fs::is_regular_file(fromStatus)) {
+        fs::copy(from.path(), to, fs::copy_options::copy_symlinks | fs::copy_options::overwrite_existing);
+    } else if (fs::is_directory(fromStatus)) {
+        fs::create_directory(to);
+        for (auto & entry : fs::directory_iterator(from.path())) {
+            copy(entry, to / entry.path().filename(), andDelete);
+        }
+    } else {
+        throw Error("file '%s' has an unsupported type", from.path());
+    }
+
+    setWriteTime(to, statOfFrom);
+    if (andDelete) {
+        if (!fs::is_symlink(fromStatus))
+            fs::permissions(from.path(), fs::perms::owner_write, fs::perm_options::add | fs::perm_options::nofollow);
+        fs::remove(from.path());
+    }
+}
+
+void renameFile(const Path & oldName, const Path & newName)
+{
+    fs::rename(oldName, newName);
+}
+
+void moveFile(const Path & oldName, const Path & newName)
+{
+    try {
+        renameFile(oldName, newName);
+    } catch (fs::filesystem_error & e) {
+        auto oldPath = fs::path(oldName);
+        auto newPath = fs::path(newName);
+        // For the move to be as atomic as possible, copy to a temporary
+        // directory
+        fs::path temp = createTempDir(newPath.parent_path(), "rename-tmp");
+        Finally removeTemp = [&]() { fs::remove(temp); };
+        auto tempCopyTarget = temp / "copy-target";
+        if (e.code().value() == EXDEV) {
+            fs::remove(newPath);
+            warn("Can’t rename %s as %s, copying instead", oldName, newName);
+            copy(fs::directory_entry(oldPath), tempCopyTarget, true);
+            renameFile(tempCopyTarget, newPath);
+        }
+    }
+}
+
+}
diff --git a/src/libutil/finally.hh b/src/libutil/finally.hh
index 7760cfe9a..dee2e8d2f 100644
--- a/src/libutil/finally.hh
+++ b/src/libutil/finally.hh
@@ -1,14 +1,13 @@
 #pragma once
 
-#include <functional>
-
 /* A trivial class to run a function at the end of a scope. */
+template<typename Fn>
 class Finally
 {
 private:
-    std::function<void()> fun;
+    Fn fun;
 
 public:
-    Finally(std::function<void()> fun) : fun(fun) { }
+    Finally(Fn fun) : fun(std::move(fun)) { }
     ~Finally() { fun(); }
 };
diff --git a/src/libutil/fmt.hh b/src/libutil/fmt.hh
index 0821b3b74..7664e5c04 100644
--- a/src/libutil/fmt.hh
+++ b/src/libutil/fmt.hh
@@ -2,7 +2,6 @@
 
 #include <boost/format.hpp>
 #include <string>
-#include <regex>
 #include "ansicolor.hh"
 
 
@@ -155,15 +154,4 @@ inline hintformat hintfmt(std::string plain_string)
     return hintfmt("%s", normaltxt(plain_string));
 }
 
-/* Highlight all the given matches in the given string `s` by wrapping
-   them between `prefix` and `postfix`.
-
-   If some matches overlap, then their union will be wrapped rather
-   than the individual matches. */
-std::string hiliteMatches(
-    std::string_view s,
-    std::vector<std::smatch> matches,
-    std::string_view prefix,
-    std::string_view postfix);
-
 }
diff --git a/src/libutil/git.cc b/src/libutil/git.cc
new file mode 100644
index 000000000..f35c2fdb7
--- /dev/null
+++ b/src/libutil/git.cc
@@ -0,0 +1,25 @@
+#include "git.hh"
+
+#include <regex>
+
+namespace nix {
+namespace git {
+
+std::optional<LsRemoteRefLine> parseLsRemoteLine(std::string_view line)
+{
+    const static std::regex line_regex("^(ref: *)?([^\\s]+)(?:\\t+(.*))?$");
+    std::match_results<std::string_view::const_iterator> match;
+    if (!std::regex_match(line.cbegin(), line.cend(), match, line_regex))
+        return std::nullopt;
+
+    return LsRemoteRefLine {
+        .kind = match[1].length() == 0
+            ? LsRemoteRefLine::Kind::Object
+            : LsRemoteRefLine::Kind::Symbolic,
+        .target = match[2],
+        .reference = match[3].length() == 0 ? std::nullopt : std::optional<std::string>{ match[3] }
+    };
+}
+
+}
+}
diff --git a/src/libutil/git.hh b/src/libutil/git.hh
new file mode 100644
index 000000000..cb13ef0e5
--- /dev/null
+++ b/src/libutil/git.hh
@@ -0,0 +1,40 @@
+#pragma once
+
+#include <string>
+#include <string_view>
+#include <optional>
+
+namespace nix {
+
+namespace git {
+
+// A line from the output of `git ls-remote --symref`.
+//
+// These can be of two kinds:
+//
+// - Symbolic references of the form
+//
+//      ref: {target}	{reference}
+//
+//    where {target} is itself a reference and {reference} is optional
+//
+// - Object references of the form
+//
+//      {target}	{reference}
+//
+//    where {target} is a commit id and {reference} is mandatory
+struct LsRemoteRefLine {
+    enum struct Kind {
+        Symbolic,
+        Object
+    };
+    Kind kind;
+    std::string target;
+    std::optional<std::string> reference;
+};
+
+std::optional<LsRemoteRefLine> parseLsRemoteLine(std::string_view line);
+
+}
+
+}
diff --git a/src/libutil/hash.cc b/src/libutil/hash.cc
index a4d632161..d2fd0c15a 100644
--- a/src/libutil/hash.cc
+++ b/src/libutil/hash.cc
@@ -155,7 +155,7 @@ static std::pair<std::optional<HashType>, bool> getParsedTypeAndSRI(std::string_
 {
     bool isSRI = false;
 
-    // Parse the has type before the separater, if there was one.
+    // Parse the hash type before the separator, if there was one.
     std::optional<HashType> optParsedType;
     {
         auto hashRaw = splitPrefixTo(rest, ':');
diff --git a/src/libutil/hash.hh b/src/libutil/hash.hh
index 56b5938b3..00f70a572 100644
--- a/src/libutil/hash.hh
+++ b/src/libutil/hash.hh
@@ -93,13 +93,11 @@ public:
 
     std::string gitRev() const
     {
-        assert(type == htSHA1);
         return to_string(Base16, false);
     }
 
     std::string gitShortRev() const
     {
-        assert(type == htSHA1);
         return std::string(to_string(Base16, false), 0, 7);
     }
 
diff --git a/src/libutil/fmt.cc b/src/libutil/hilite.cc
index 3dd93d73e..e5088230d 100644
--- a/src/libutil/fmt.cc
+++ b/src/libutil/hilite.cc
@@ -1,6 +1,4 @@
-#include "fmt.hh"
-
-#include <regex>
+#include "hilite.hh"
 
 namespace nix {
 
@@ -10,9 +8,9 @@ std::string hiliteMatches(
     std::string_view prefix,
     std::string_view postfix)
 {
-    // Avoid copy on zero matches
+    // Avoid extra work on zero matches
     if (matches.size() == 0)
-        return (std::string) s;
+        return std::string(s);
 
     std::sort(matches.begin(), matches.end(), [](const auto & a, const auto & b) {
         return a.position() < b.position();
diff --git a/src/libutil/hilite.hh b/src/libutil/hilite.hh
new file mode 100644
index 000000000..f8bdbfc55
--- /dev/null
+++ b/src/libutil/hilite.hh
@@ -0,0 +1,20 @@
+#pragma once
+
+#include <regex>
+#include <vector>
+#include <string>
+
+namespace nix {
+
+/* Highlight all the given matches in the given string `s` by wrapping
+   them between `prefix` and `postfix`.
+
+   If some matches overlap, then their union will be wrapped rather
+   than the individual matches. */
+std::string hiliteMatches(
+    std::string_view s,
+    std::vector<std::smatch> matches,
+    std::string_view prefix,
+    std::string_view postfix);
+
+}
diff --git a/src/libutil/json-utils.hh b/src/libutil/json-utils.hh
new file mode 100644
index 000000000..b8a031227
--- /dev/null
+++ b/src/libutil/json-utils.hh
@@ -0,0 +1,21 @@
+#pragma once
+
+#include <nlohmann/json.hpp>
+
+namespace nix {
+
+const nlohmann::json * get(const nlohmann::json & map, const std::string & key)
+{
+    auto i = map.find(key);
+    if (i == map.end()) return nullptr;
+    return &*i;
+}
+
+nlohmann::json * get(nlohmann::json & map, const std::string & key)
+{
+    auto i = map.find(key);
+    if (i == map.end()) return nullptr;
+    return &*i;
+}
+
+}
diff --git a/src/libutil/json.cc b/src/libutil/json.cc
index 3a981376f..2f9e97ff5 100644
--- a/src/libutil/json.cc
+++ b/src/libutil/json.cc
@@ -1,11 +1,13 @@
 #include "json.hh"
 
 #include <iomanip>
+#include <cstdint>
 #include <cstring>
 
 namespace nix {
 
-void toJSON(std::ostream & str, const char * start, const char * end)
+template<>
+void toJSON<std::string_view>(std::ostream & str, const std::string_view & s)
 {
     constexpr size_t BUF_SIZE = 4096;
     char buf[BUF_SIZE + 7]; // BUF_SIZE + largest single sequence of puts
@@ -20,7 +22,7 @@ void toJSON(std::ostream & str, const char * start, const char * end)
     };
 
     put('"');
-    for (auto i = start; i != end; i++) {
+    for (auto i = s.begin(); i != s.end(); i++) {
         if (bufPos >= BUF_SIZE) flush();
         if (*i == '\"' || *i == '\\') { put('\\'); put(*i); }
         else if (*i == '\n') { put('\\'); put('n'); }
@@ -43,7 +45,7 @@ void toJSON(std::ostream & str, const char * start, const char * end)
 
 void toJSON(std::ostream & str, const char * s)
 {
-    if (!s) str << "null"; else toJSON(str, s, s + strlen(s));
+    if (!s) str << "null"; else toJSON(str, std::string_view(s));
 }
 
 template<> void toJSON<int>(std::ostream & str, const int & n) { str << n; }
@@ -54,11 +56,7 @@ template<> void toJSON<long long>(std::ostream & str, const long long & n) { str
 template<> void toJSON<unsigned long long>(std::ostream & str, const unsigned long long & n) { str << n; }
 template<> void toJSON<float>(std::ostream & str, const float & n) { str << n; }
 template<> void toJSON<double>(std::ostream & str, const double & n) { str << n; }
-
-template<> void toJSON<std::string>(std::ostream & str, const std::string & s)
-{
-    toJSON(str, s.c_str(), s.c_str() + s.size());
-}
+template<> void toJSON<std::string>(std::ostream & str, const std::string & s) { toJSON(str, (std::string_view) s); }
 
 template<> void toJSON<bool>(std::ostream & str, const bool & b)
 {
@@ -153,7 +151,7 @@ JSONObject::~JSONObject()
     }
 }
 
-void JSONObject::attr(const std::string & s)
+void JSONObject::attr(std::string_view s)
 {
     comma();
     toJSON(state->str, s);
@@ -161,19 +159,19 @@ void JSONObject::attr(const std::string & s)
     if (state->indent) state->str << ' ';
 }
 
-JSONList JSONObject::list(const std::string & name)
+JSONList JSONObject::list(std::string_view name)
 {
     attr(name);
     return JSONList(state);
 }
 
-JSONObject JSONObject::object(const std::string & name)
+JSONObject JSONObject::object(std::string_view name)
 {
     attr(name);
     return JSONObject(state);
 }
 
-JSONPlaceholder JSONObject::placeholder(const std::string & name)
+JSONPlaceholder JSONObject::placeholder(std::string_view name)
 {
     attr(name);
     return JSONPlaceholder(state);
@@ -195,7 +193,11 @@ JSONObject JSONPlaceholder::object()
 
 JSONPlaceholder::~JSONPlaceholder()
 {
-    assert(!first || std::uncaught_exceptions());
+    if (first) {
+        assert(std::uncaught_exceptions());
+        if (state->stack != 0)
+            write(nullptr);
+    }
 }
 
 }
diff --git a/src/libutil/json.hh b/src/libutil/json.hh
index 83213ca66..3790b1a2e 100644
--- a/src/libutil/json.hh
+++ b/src/libutil/json.hh
@@ -6,7 +6,6 @@
 
 namespace nix {
 
-void toJSON(std::ostream & str, const char * start, const char * end);
 void toJSON(std::ostream & str, const char * s);
 
 template<typename T>
@@ -107,7 +106,7 @@ private:
         open();
     }
 
-    void attr(const std::string & s);
+    void attr(std::string_view s);
 
 public:
 
@@ -128,18 +127,18 @@ public:
     ~JSONObject();
 
     template<typename T>
-    JSONObject & attr(const std::string & name, const T & v)
+    JSONObject & attr(std::string_view name, const T & v)
     {
         attr(name);
         toJSON(state->str, v);
         return *this;
     }
 
-    JSONList list(const std::string & name);
+    JSONList list(std::string_view name);
 
-    JSONObject object(const std::string & name);
+    JSONObject object(std::string_view name);
 
-    JSONPlaceholder placeholder(const std::string & name);
+    JSONPlaceholder placeholder(std::string_view name);
 };
 
 class JSONPlaceholder : JSONWriter
diff --git a/src/libutil/logging.cc b/src/libutil/logging.cc
index 74ee2f063..cb2b15b41 100644
--- a/src/libutil/logging.cc
+++ b/src/libutil/logging.cc
@@ -266,51 +266,63 @@ static Logger::Fields getFields(nlohmann::json & json)
     return fields;
 }
 
-bool handleJSONLogMessage(const std::string & msg,
-    const Activity & act, std::map<ActivityId, Activity> & activities, bool trusted)
+std::optional<nlohmann::json> parseJSONMessage(const std::string & msg)
 {
-    if (!hasPrefix(msg, "@nix ")) return false;
-
+    if (!hasPrefix(msg, "@nix ")) return std::nullopt;
     try {
-        auto json = nlohmann::json::parse(std::string(msg, 5));
-
-        std::string action = json["action"];
-
-        if (action == "start") {
-            auto type = (ActivityType) json["type"];
-            if (trusted || type == actFileTransfer)
-                activities.emplace(std::piecewise_construct,
-                    std::forward_as_tuple(json["id"]),
-                    std::forward_as_tuple(*logger, (Verbosity) json["level"], type,
-                        json["text"], getFields(json["fields"]), act.id));
-        }
+        return nlohmann::json::parse(std::string(msg, 5));
+    } catch (std::exception & e) {
+        printError("bad JSON log message from builder: %s", e.what());
+    }
+    return std::nullopt;
+}
 
-        else if (action == "stop")
-            activities.erase((ActivityId) json["id"]);
+bool handleJSONLogMessage(nlohmann::json & json,
+    const Activity & act, std::map<ActivityId, Activity> & activities,
+    bool trusted)
+{
+    std::string action = json["action"];
+
+    if (action == "start") {
+        auto type = (ActivityType) json["type"];
+        if (trusted || type == actFileTransfer)
+            activities.emplace(std::piecewise_construct,
+                std::forward_as_tuple(json["id"]),
+                std::forward_as_tuple(*logger, (Verbosity) json["level"], type,
+                    json["text"], getFields(json["fields"]), act.id));
+    }
 
-        else if (action == "result") {
-            auto i = activities.find((ActivityId) json["id"]);
-            if (i != activities.end())
-                i->second.result((ResultType) json["type"], getFields(json["fields"]));
-        }
+    else if (action == "stop")
+        activities.erase((ActivityId) json["id"]);
 
-        else if (action == "setPhase") {
-            std::string phase = json["phase"];
-            act.result(resSetPhase, phase);
-        }
+    else if (action == "result") {
+        auto i = activities.find((ActivityId) json["id"]);
+        if (i != activities.end())
+            i->second.result((ResultType) json["type"], getFields(json["fields"]));
+    }
 
-        else if (action == "msg") {
-            std::string msg = json["msg"];
-            logger->log((Verbosity) json["level"], msg);
-        }
+    else if (action == "setPhase") {
+        std::string phase = json["phase"];
+        act.result(resSetPhase, phase);
+    }
 
-    } catch (std::exception & e) {
-        printError("bad JSON log message from builder: %s", e.what());
+    else if (action == "msg") {
+        std::string msg = json["msg"];
+        logger->log((Verbosity) json["level"], msg);
     }
 
     return true;
 }
 
+bool handleJSONLogMessage(const std::string & msg,
+    const Activity & act, std::map<ActivityId, Activity> & activities, bool trusted)
+{
+    auto json = parseJSONMessage(msg);
+    if (!json) return false;
+
+    return handleJSONLogMessage(*json, act, activities, trusted);
+}
+
 Activity::~Activity()
 {
     try {
diff --git a/src/libutil/logging.hh b/src/libutil/logging.hh
index bd28036ae..d0817b4a9 100644
--- a/src/libutil/logging.hh
+++ b/src/libutil/logging.hh
@@ -4,6 +4,8 @@
 #include "error.hh"
 #include "config.hh"
 
+#include <nlohmann/json_fwd.hpp>
+
 namespace nix {
 
 typedef enum {
@@ -109,6 +111,9 @@ public:
 
     virtual std::optional<char> ask(std::string_view s)
     { return {}; }
+
+    virtual void setPrintBuildLogs(bool printBuildLogs)
+    { }
 };
 
 ActivityId getCurActivity();
@@ -166,6 +171,12 @@ Logger * makeSimpleLogger(bool printBuildLogs = true);
 
 Logger * makeJSONLogger(Logger & prevLogger);
 
+std::optional<nlohmann::json> parseJSONMessage(const std::string & msg);
+
+bool handleJSONLogMessage(nlohmann::json & json,
+    const Activity & act, std::map<ActivityId, Activity> & activities,
+    bool trusted);
+
 bool handleJSONLogMessage(const std::string & msg,
     const Activity & act, std::map<ActivityId, Activity> & activities,
     bool trusted);
diff --git a/src/libutil/ref.hh b/src/libutil/ref.hh
index 347b81f73..bf26321db 100644
--- a/src/libutil/ref.hh
+++ b/src/libutil/ref.hh
@@ -7,7 +7,7 @@
 namespace nix {
 
 /* A simple non-nullable reference-counted pointer. Actually a wrapper
-   around std::shared_ptr that prevents non-null constructions. */
+   around std::shared_ptr that prevents null constructions. */
 template<typename T>
 class ref
 {
@@ -99,47 +99,4 @@ make_ref(Args&&... args)
     return ref<T>(p);
 }
 
-
-/* A non-nullable pointer.
-   This is similar to a C++ "& reference", but mutable.
-   This is similar to ref<T> but backed by a regular pointer instead of a smart pointer.
- */
-template<typename T>
-class ptr {
-private:
-    T * p;
-
-public:
-    ptr<T>(const ptr<T> & r)
-        : p(r.p)
-    { }
-
-    explicit ptr<T>(T * p)
-        : p(p)
-    {
-        if (!p)
-            throw std::invalid_argument("null pointer cast to ptr");
-    }
-
-    T* operator ->() const
-    {
-        return &*p;
-    }
-
-    T& operator *() const
-    {
-        return *p;
-    }
-
-    bool operator == (const ptr<T> & other) const
-    {
-        return p == other.p;
-    }
-
-    bool operator != (const ptr<T> & other) const
-    {
-        return p != other.p;
-    }
-};
-
 }
diff --git a/src/libutil/serialise.cc b/src/libutil/serialise.cc
index 6445b3f1b..2c3597775 100644
--- a/src/libutil/serialise.cc
+++ b/src/libutil/serialise.cc
@@ -48,24 +48,9 @@ FdSink::~FdSink()
 }
 
 
-size_t threshold = 256 * 1024 * 1024;
-
-static void warnLargeDump()
-{
-    warn("dumping very large path (> 256 MiB); this may run out of memory");
-}
-
-
 void FdSink::write(std::string_view data)
 {
     written += data.size();
-    static bool warned = false;
-    if (warn && !warned) {
-        if (written > threshold) {
-            warnLargeDump();
-            warned = true;
-        }
-    }
     try {
         writeFull(fd, data);
     } catch (SysError & e) {
@@ -357,7 +342,7 @@ Sink & operator << (Sink & sink, const Error & ex)
     sink
         << "Error"
         << info.level
-        << info.name
+        << "Error" // removed
         << info.msg.str()
         << 0 // FIXME: info.errPos
         << info.traces.size();
@@ -426,11 +411,10 @@ Error readError(Source & source)
     auto type = readString(source);
     assert(type == "Error");
     auto level = (Verbosity) readInt(source);
-    auto name = readString(source);
+    auto name = readString(source); // removed
     auto msg = readString(source);
     ErrorInfo info {
         .level = level,
-        .name = name,
         .msg = hintformat(std::move(format("%s") % msg)),
     };
     auto havePos = readNum<size_t>(source);
@@ -449,11 +433,6 @@ Error readError(Source & source)
 
 void StringSink::operator () (std::string_view data)
 {
-    static bool warned = false;
-    if (!warned && s.size() > threshold) {
-        warnLargeDump();
-        warned = true;
-    }
     s.append(data);
 }
 
diff --git a/src/libutil/serialise.hh b/src/libutil/serialise.hh
index 13da26c6a..84847835a 100644
--- a/src/libutil/serialise.hh
+++ b/src/libutil/serialise.hh
@@ -97,19 +97,17 @@ protected:
 struct FdSink : BufferedSink
 {
     int fd;
-    bool warn = false;
     size_t written = 0;
 
     FdSink() : fd(-1) { }
     FdSink(int fd) : fd(fd) { }
     FdSink(FdSink&&) = default;
 
-    FdSink& operator=(FdSink && s)
+    FdSink & operator=(FdSink && s)
     {
         flush();
         fd = s.fd;
         s.fd = -1;
-        warn = s.warn;
         written = s.written;
         return *this;
     }
diff --git a/src/libutil/suggestions.cc b/src/libutil/suggestions.cc
new file mode 100644
index 000000000..9510a5f0c
--- /dev/null
+++ b/src/libutil/suggestions.cc
@@ -0,0 +1,114 @@
+#include "suggestions.hh"
+#include "ansicolor.hh"
+#include "util.hh"
+#include <algorithm>
+
+namespace nix {
+
+int levenshteinDistance(std::string_view first, std::string_view second)
+{
+    // Implementation borrowed from
+    // https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows
+
+    int m = first.size();
+    int n = second.size();
+
+    auto v0 = std::vector<int>(n+1);
+    auto v1 = std::vector<int>(n+1);
+
+    for (auto i = 0; i <= n; i++)
+        v0[i] = i;
+
+    for (auto i = 0; i < m; i++) {
+        v1[0] = i+1;
+
+        for (auto j = 0; j < n; j++) {
+            auto deletionCost = v0[j+1] + 1;
+            auto insertionCost = v1[j] + 1;
+            auto substitutionCost = first[i] == second[j] ? v0[j] : v0[j] + 1;
+            v1[j+1] = std::min({deletionCost, insertionCost, substitutionCost});
+        }
+
+        std::swap(v0, v1);
+    }
+
+    return v0[n];
+}
+
+Suggestions Suggestions::bestMatches (
+    std::set<std::string> allMatches,
+    std::string query)
+{
+    std::set<Suggestion> res;
+    for (const auto & possibleMatch : allMatches) {
+        res.insert(Suggestion {
+            .distance = levenshteinDistance(query, possibleMatch),
+            .suggestion = possibleMatch,
+        });
+    }
+    return Suggestions { res };
+}
+
+Suggestions Suggestions::trim(int limit, int maxDistance) const
+{
+    std::set<Suggestion> res;
+
+    int count = 0;
+
+    for (auto & elt : suggestions) {
+        if (count >= limit || elt.distance > maxDistance)
+            break;
+        count++;
+        res.insert(elt);
+    }
+
+    return Suggestions{res};
+}
+
+std::string Suggestion::to_string() const
+{
+    return ANSI_WARNING + filterANSIEscapes(suggestion) + ANSI_NORMAL;
+}
+
+std::string Suggestions::to_string() const
+{
+    switch (suggestions.size()) {
+        case 0:
+            return "";
+        case 1:
+            return suggestions.begin()->to_string();
+        default: {
+            std::string res = "one of ";
+            auto iter = suggestions.begin();
+            res += iter->to_string(); // Iter can’t be end() because the container isn’t null
+            iter++;
+            auto last = suggestions.end(); last--;
+            for ( ; iter != suggestions.end() ; iter++) {
+                res += (iter == last) ? " or " : ", ";
+                res += iter->to_string();
+            }
+            return res;
+        }
+    }
+}
+
+Suggestions & Suggestions::operator+=(const Suggestions & other)
+{
+    suggestions.insert(
+            other.suggestions.begin(),
+            other.suggestions.end()
+    );
+    return *this;
+}
+
+std::ostream & operator<<(std::ostream & str, const Suggestion & suggestion)
+{
+    return str << suggestion.to_string();
+}
+
+std::ostream & operator<<(std::ostream & str, const Suggestions & suggestions)
+{
+    return str << suggestions.to_string();
+}
+
+}
diff --git a/src/libutil/suggestions.hh b/src/libutil/suggestions.hh
new file mode 100644
index 000000000..d54dd8e31
--- /dev/null
+++ b/src/libutil/suggestions.hh
@@ -0,0 +1,102 @@
+#pragma once
+
+#include "comparator.hh"
+#include "types.hh"
+#include <set>
+
+namespace nix {
+
+int levenshteinDistance(std::string_view first, std::string_view second);
+
+/**
+ * A potential suggestion for the cli interface.
+ */
+class Suggestion {
+public:
+    int distance; // The smaller the better
+    std::string suggestion;
+
+    std::string to_string() const;
+
+    GENERATE_CMP(Suggestion, me->distance, me->suggestion)
+};
+
+class Suggestions {
+public:
+    std::set<Suggestion> suggestions;
+
+    std::string to_string() const;
+
+    Suggestions trim(
+        int limit = 5,
+        int maxDistance = 2
+    ) const;
+
+    static Suggestions bestMatches (
+        std::set<std::string> allMatches,
+        std::string query
+    );
+
+    Suggestions& operator+=(const Suggestions & other);
+};
+
+std::ostream & operator<<(std::ostream & str, const Suggestion &);
+std::ostream & operator<<(std::ostream & str, const Suggestions &);
+
+// Either a value of type `T`, or some suggestions
+template<typename T>
+class OrSuggestions {
+public:
+    using Raw = std::variant<T, Suggestions>;
+
+    Raw raw;
+
+    T* operator ->()
+    {
+        return &**this;
+    }
+
+    T& operator *()
+    {
+        return std::get<T>(raw);
+    }
+
+    operator bool() const noexcept
+    {
+        return std::holds_alternative<T>(raw);
+    }
+
+    OrSuggestions(T t)
+        : raw(t)
+    {
+    }
+
+    OrSuggestions()
+        : raw(Suggestions{})
+    {
+    }
+
+    static OrSuggestions<T> failed(const Suggestions & s)
+    {
+        auto res = OrSuggestions<T>();
+        res.raw = s;
+        return res;
+    }
+
+    static OrSuggestions<T> failed()
+    {
+        return OrSuggestions<T>::failed(Suggestions{});
+    }
+
+    const Suggestions & getSuggestions()
+    {
+        static Suggestions noSuggestions;
+        if (const auto & suggestions = std::get_if<Suggestions>(&raw))
+            return *suggestions;
+        else
+            return noSuggestions;
+    }
+
+};
+
+}
diff --git a/src/libutil/tarfile.cc b/src/libutil/tarfile.cc
index 790bc943a..a7db58559 100644
--- a/src/libutil/tarfile.cc
+++ b/src/libutil/tarfile.cc
@@ -39,28 +39,30 @@ void TarArchive::check(int err, const std::string & reason)
         throw Error(reason, archive_error_string(this->archive));
 }
 
-TarArchive::TarArchive(Source & source, bool raw)
-    : source(&source), buffer(4096)
+TarArchive::TarArchive(Source & source, bool raw) : buffer(4096)
 {
-    init();
-    if (!raw)
+    this->archive = archive_read_new();
+    this->source = &source;
+
+    if (!raw) {
+        archive_read_support_filter_all(archive);
         archive_read_support_format_all(archive);
-    else
+    } else {
+        archive_read_support_filter_all(archive);
         archive_read_support_format_raw(archive);
+        archive_read_support_format_empty(archive);
+    }
     check(archive_read_open(archive, (void *)this, callback_open, callback_read, callback_close), "Failed to open archive (%s)");
 }
 
+
 TarArchive::TarArchive(const Path & path)
 {
-    init();
-    archive_read_support_format_all(archive);
-    check(archive_read_open_filename(archive, path.c_str(), 16384), "failed to open archive: %s");
-}
+    this->archive = archive_read_new();
 
-void TarArchive::init()
-{
-    archive = archive_read_new();
     archive_read_support_filter_all(archive);
+    archive_read_support_format_all(archive);
+    check(archive_read_open_filename(archive, path.c_str(), 16384), "failed to open archive: %s");
 }
 
 void TarArchive::close()
diff --git a/src/libutil/tarfile.hh b/src/libutil/tarfile.hh
index f107a7e2e..4d9141fd4 100644
--- a/src/libutil/tarfile.hh
+++ b/src/libutil/tarfile.hh
@@ -17,13 +17,10 @@ struct TarArchive {
     // disable copy constructor
     TarArchive(const TarArchive &) = delete;
 
-    void init();
-
     void close();
 
     ~TarArchive();
 };
-
 void unpackTarfile(Source & source, const Path & destDir);
 
 void unpackTarfile(const Path & tarFile, const Path & destDir);
diff --git a/src/libutil/tests/chunked-vector.cc b/src/libutil/tests/chunked-vector.cc
new file mode 100644
index 000000000..868d11f6f
--- /dev/null
+++ b/src/libutil/tests/chunked-vector.cc
@@ -0,0 +1,54 @@
+#include "chunked-vector.hh"
+
+#include <gtest/gtest.h>
+
+namespace nix {
+    TEST(ChunkedVector, InitEmpty) {
+        auto v = ChunkedVector<int, 2>(100);
+        ASSERT_EQ(v.size(), 0);
+    }
+
+    TEST(ChunkedVector, GrowsCorrectly) {
+        auto v = ChunkedVector<int, 2>(100);
+        for (auto i = 1; i < 20; i++) {
+            v.add(i);
+            ASSERT_EQ(v.size(), i);
+        }
+    }
+
+    TEST(ChunkedVector, AddAndGet) {
+        auto v = ChunkedVector<int, 2>(100);
+        for (auto i = 1; i < 20; i++) {
+            auto [i2, idx] = v.add(i);
+            auto & i3 = v[idx];
+            ASSERT_EQ(i, i2);
+            ASSERT_EQ(&i2, &i3);
+        }
+    }
+
+    TEST(ChunkedVector, ForEach) {
+        auto v = ChunkedVector<int, 2>(100);
+        for (auto i = 1; i < 20; i++) {
+            v.add(i);
+        }
+        int count = 0;
+        v.forEach([&count](int elt) {
+            count++;
+        });
+        ASSERT_EQ(count, v.size());
+    }
+
+    TEST(ChunkedVector, OverflowOK) {
+        // Similar to the AddAndGet, but intentionnally use a small
+        // initial ChunkedVector to force it to overflow
+        auto v = ChunkedVector<int, 2>(2);
+        for (auto i = 1; i < 20; i++) {
+            auto [i2, idx] = v.add(i);
+            auto & i3 = v[idx];
+            ASSERT_EQ(i, i2);
+            ASSERT_EQ(&i2, &i3);
+        }
+    }
+
+}
+
diff --git a/src/libutil/tests/git.cc b/src/libutil/tests/git.cc
new file mode 100644
index 000000000..5b5715fc2
--- /dev/null
+++ b/src/libutil/tests/git.cc
@@ -0,0 +1,33 @@
+#include "git.hh"
+#include <gtest/gtest.h>
+
+namespace nix {
+
+    TEST(GitLsRemote, parseSymrefLineWithReference) {
+        auto line = "ref: refs/head/main	HEAD";
+        auto res = git::parseLsRemoteLine(line);
+        ASSERT_TRUE(res.has_value());
+        ASSERT_EQ(res->kind, git::LsRemoteRefLine::Kind::Symbolic);
+        ASSERT_EQ(res->target, "refs/head/main");
+        ASSERT_EQ(res->reference, "HEAD");
+    }
+
+    TEST(GitLsRemote, parseSymrefLineWithNoReference) {
+        auto line = "ref: refs/head/main";
+        auto res = git::parseLsRemoteLine(line);
+        ASSERT_TRUE(res.has_value());
+        ASSERT_EQ(res->kind, git::LsRemoteRefLine::Kind::Symbolic);
+        ASSERT_EQ(res->target, "refs/head/main");
+        ASSERT_EQ(res->reference, std::nullopt);
+    }
+
+    TEST(GitLsRemote, parseObjectRefLine) {
+        auto line = "abc123	refs/head/main";
+        auto res = git::parseLsRemoteLine(line);
+        ASSERT_TRUE(res.has_value());
+        ASSERT_EQ(res->kind, git::LsRemoteRefLine::Kind::Object);
+        ASSERT_EQ(res->target, "abc123");
+        ASSERT_EQ(res->reference, "refs/head/main");
+    }
+}
+
diff --git a/src/libutil/tests/fmt.cc b/src/libutil/tests/hilite.cc
index 33772162c..1ff5980d5 100644
--- a/src/libutil/tests/fmt.cc
+++ b/src/libutil/tests/hilite.cc
@@ -1,9 +1,7 @@
-#include "fmt.hh"
+#include "hilite.hh"
 
 #include <gtest/gtest.h>
 
-#include <regex>
-
 namespace nix {
 /* ----------- tests for fmt.hh -------------------------------------------------*/
 
diff --git a/src/libutil/tests/json.cc b/src/libutil/tests/json.cc
index dea73f53a..156286999 100644
--- a/src/libutil/tests/json.cc
+++ b/src/libutil/tests/json.cc
@@ -102,8 +102,8 @@ namespace nix {
 
     TEST(toJSON, substringEscape) {
         std::stringstream out;
-        const char *s = "foo\t";
-        toJSON(out, s+3, s + strlen(s));
+        std::string_view s = "foo\t";
+        toJSON(out, s.substr(3));
 
         ASSERT_EQ(out.str(), "\"\\t\"");
     }
diff --git a/src/libutil/tests/logging.cc b/src/libutil/tests/logging.cc
index cef3bd481..2ffdc2e9b 100644
--- a/src/libutil/tests/logging.cc
+++ b/src/libutil/tests/logging.cc
@@ -359,7 +359,7 @@ namespace nix {
 
       // constructing without access violation.
       ErrPos ep(invalid);
-    
+
       // assignment without access violation.
       ep = invalid;
 
diff --git a/src/libutil/tests/suggestions.cc b/src/libutil/tests/suggestions.cc
new file mode 100644
index 000000000..279994abc
--- /dev/null
+++ b/src/libutil/tests/suggestions.cc
@@ -0,0 +1,43 @@
+#include "suggestions.hh"
+#include <gtest/gtest.h>
+
+namespace nix {
+
+    struct LevenshteinDistanceParam {
+        std::string s1, s2;
+        int distance;
+    };
+
+    class LevenshteinDistanceTest :
+        public testing::TestWithParam<LevenshteinDistanceParam> {
+    };
+
+    TEST_P(LevenshteinDistanceTest, CorrectlyComputed) {
+        auto params = GetParam();
+
+        ASSERT_EQ(levenshteinDistance(params.s1, params.s2), params.distance);
+        ASSERT_EQ(levenshteinDistance(params.s2, params.s1), params.distance);
+    }
+
+    INSTANTIATE_TEST_SUITE_P(LevenshteinDistance, LevenshteinDistanceTest,
+            testing::Values(
+                LevenshteinDistanceParam{"foo", "foo", 0},
+                LevenshteinDistanceParam{"foo", "", 3},
+                LevenshteinDistanceParam{"", "", 0},
+                LevenshteinDistanceParam{"foo", "fo", 1},
+                LevenshteinDistanceParam{"foo", "oo", 1},
+                LevenshteinDistanceParam{"foo", "fao", 1},
+                LevenshteinDistanceParam{"foo", "abc", 3}
+            )
+    );
+
+    TEST(Suggestions, Trim) {
+        auto suggestions = Suggestions::bestMatches({"foooo", "bar", "fo", "gao"}, "foo");
+        auto onlyOne = suggestions.trim(1);
+        ASSERT_EQ(onlyOne.suggestions.size(), 1);
+        ASSERT_TRUE(onlyOne.suggestions.begin()->suggestion == "fo");
+
+        auto closest = suggestions.trim(999, 2);
+        ASSERT_EQ(closest.suggestions.size(), 3);
+    }
+}
diff --git a/src/libutil/tests/tests.cc b/src/libutil/tests/tests.cc
index 92972ed14..6e325db98 100644
--- a/src/libutil/tests/tests.cc
+++ b/src/libutil/tests/tests.cc
@@ -548,7 +548,7 @@ namespace nix {
 
     TEST(get, emptyContainer) {
         StringMap s = { };
-        auto expected = std::nullopt;
+        auto expected = nullptr;
 
         ASSERT_EQ(get(s, "one"), expected);
     }
@@ -559,7 +559,23 @@ namespace nix {
         s["two"] = "er";
         auto expected = "yi";
 
-        ASSERT_EQ(get(s, "one"), expected);
+        ASSERT_EQ(*get(s, "one"), expected);
+    }
+
+    TEST(getOr, emptyContainer) {
+        StringMap s = { };
+        auto expected = "yi";
+
+        ASSERT_EQ(getOr(s, "one", "yi"), expected);
+    }
+
+    TEST(getOr, getFromContainer) {
+        StringMap s;
+        s["one"] = "yi";
+        s["two"] = "er";
+        auto expected = "yi";
+
+        ASSERT_EQ(getOr(s, "one", "nope"), expected);
     }
 
     /* ----------------------------------------------------------------------------
diff --git a/src/libutil/tests/url.cc b/src/libutil/tests/url.cc
index f20e2dc41..c3b233797 100644
--- a/src/libutil/tests/url.cc
+++ b/src/libutil/tests/url.cc
@@ -178,7 +178,7 @@ namespace nix {
     }
 
     TEST(parseURL, parseFileURLWithQueryAndFragment) {
-        auto s = "file:///none/of/your/business";
+        auto s = "file:///none/of//your/business";
         auto parsed = parseURL(s);
 
         ParsedURL expected {
@@ -186,7 +186,7 @@ namespace nix {
             .base = "",
             .scheme = "file",
             .authority = "",
-            .path = "/none/of/your/business",
+            .path = "/none/of//your/business",
             .query = (StringMap) { },
             .fragment = "",
         };
diff --git a/src/libutil/types.hh b/src/libutil/types.hh
index 00ba567c6..6bcbd7e1d 100644
--- a/src/libutil/types.hh
+++ b/src/libutil/types.hh
@@ -5,6 +5,7 @@
 #include <list>
 #include <set>
 #include <string>
+#include <limits>
 #include <map>
 #include <variant>
 #include <vector>
diff --git a/src/libutil/url-parts.hh b/src/libutil/url-parts.hh
index da10a6bbc..d5e6a2736 100644
--- a/src/libutil/url-parts.hh
+++ b/src/libutil/url-parts.hh
@@ -18,7 +18,7 @@ const static std::string userRegex = "(?:(?:" + unreservedRegex + "|" + pctEncod
 const static std::string authorityRegex = "(?:" + userRegex + "@)?" + hostRegex + "(?::[0-9]+)?";
 const static std::string pcharRegex = "(?:" + unreservedRegex + "|" + pctEncoded + "|" + subdelimsRegex + "|[:@])";
 const static std::string queryRegex = "(?:" + pcharRegex + "|[/? \"])*";
-const static std::string segmentRegex = "(?:" + pcharRegex + "+)";
+const static std::string segmentRegex = "(?:" + pcharRegex + "*)";
 const static std::string absPathRegex = "(?:(?:/" + segmentRegex + ")*/?)";
 const static std::string pathRegex = "(?:" + segmentRegex + "(?:/" + segmentRegex + ")*/?)";
 
diff --git a/src/libutil/url.cc b/src/libutil/url.cc
index f6232d255..5b7abeb49 100644
--- a/src/libutil/url.cc
+++ b/src/libutil/url.cc
@@ -1,6 +1,7 @@
 #include "url.hh"
 #include "url-parts.hh"
 #include "util.hh"
+#include "split.hh"
 
 namespace nix {
 
@@ -136,4 +137,21 @@ bool ParsedURL::operator ==(const ParsedURL & other) const
         && fragment == other.fragment;
 }
 
+/**
+ * Parse a URL scheme of the form '(applicationScheme\+)?transportScheme'
+ * into a tuple '(applicationScheme, transportScheme)'
+ *
+ * > parseUrlScheme("http") == ParsedUrlScheme{ {}, "http"}
+ * > parseUrlScheme("tarball+http") == ParsedUrlScheme{ {"tarball"}, "http"}
+ */
+ParsedUrlScheme parseUrlScheme(std::string_view scheme)
+{
+    auto application = splitPrefixTo(scheme, '+');
+    auto transport = scheme;
+    return ParsedUrlScheme {
+        .application = application,
+        .transport = transport,
+    };
+}
+
 }
diff --git a/src/libutil/url.hh b/src/libutil/url.hh
index 6e77142e3..2a9fb34c1 100644
--- a/src/libutil/url.hh
+++ b/src/libutil/url.hh
@@ -27,4 +27,19 @@ std::map<std::string, std::string> decodeQuery(const std::string & query);
 
 ParsedURL parseURL(const std::string & url);
 
+/*
+ * Although that’s not really standardized anywhere, an number of tools
+ * use a scheme of the form 'x+y' in urls, where y is the “transport layer”
+ * scheme, and x is the “application layer” scheme.
+ *
+ * For example git uses `git+https` to designate remotes using a Git
+ * protocol over http.
+ */
+struct ParsedUrlScheme {
+    std::optional<std::string_view> application;
+    std::string_view transport;
+};
+
+ParsedUrlScheme parseUrlScheme(std::string_view scheme);
+
 }
diff --git a/src/libutil/util.cc b/src/libutil/util.cc
index 88c5ae806..623b74bdd 100644
--- a/src/libutil/util.cc
+++ b/src/libutil/util.cc
@@ -29,11 +29,15 @@
 
 #ifdef __APPLE__
 #include <sys/syscall.h>
+#include <mach-o/dyld.h>
 #endif
 
 #ifdef __linux__
 #include <sys/prctl.h>
 #include <sys/resource.h>
+
+#include <mntent.h>
+#include <cmath>
 #endif
 
 
@@ -71,13 +75,11 @@ void clearEnv()
         unsetenv(name.first.c_str());
 }
 
-void replaceEnv(std::map<std::string, std::string> newEnv)
+void replaceEnv(const std::map<std::string, std::string> & newEnv)
 {
     clearEnv();
-    for (auto newEnvVar : newEnv)
-    {
+    for (auto & newEnvVar : newEnv)
         setenv(newEnvVar.first.c_str(), newEnvVar.second.c_str(), 1);
-    }
 }
 
 
@@ -200,6 +202,17 @@ std::string_view baseNameOf(std::string_view path)
 }
 
 
+std::string expandTilde(std::string_view path)
+{
+    // TODO: expand ~user ?
+    auto tilde = path.substr(0, 2);
+    if (tilde == "~/" || tilde == "~")
+        return getHome() + std::string(path.substr(1));
+    else
+        return std::string(path);
+}
+
+
 bool isInDir(std::string_view path, std::string_view dir)
 {
     return path.substr(0, 1) == "/"
@@ -215,6 +228,15 @@ bool isDirOrInDir(std::string_view path, std::string_view dir)
 }
 
 
+struct stat stat(const Path & path)
+{
+    struct stat st;
+    if (stat(path.c_str(), &st))
+        throw SysError("getting status of '%1%'", path);
+    return st;
+}
+
+
 struct stat lstat(const Path & path)
 {
     struct stat st;
@@ -331,7 +353,7 @@ void readFile(const Path & path, Sink & sink)
 }
 
 
-void writeFile(const Path & path, std::string_view s, mode_t mode)
+void writeFile(const Path & path, std::string_view s, mode_t mode, bool sync)
 {
     AutoCloseFD fd = open(path.c_str(), O_WRONLY | O_TRUNC | O_CREAT | O_CLOEXEC, mode);
     if (!fd)
@@ -342,10 +364,16 @@ void writeFile(const Path & path, std::string_view s, mode_t mode)
         e.addTrace({}, "writing file '%1%'", path);
         throw;
     }
+    if (sync)
+        fd.fsync();
+    // Explicitly close to make sure exceptions are propagated.
+    fd.close();
+    if (sync)
+        syncParent(path);
 }
 
 
-void writeFile(const Path & path, Source & source, mode_t mode)
+void writeFile(const Path & path, Source & source, mode_t mode, bool sync)
 {
     AutoCloseFD fd = open(path.c_str(), O_WRONLY | O_TRUNC | O_CREAT | O_CLOEXEC, mode);
     if (!fd)
@@ -364,6 +392,20 @@ void writeFile(const Path & path, Source & source, mode_t mode)
         e.addTrace({}, "writing file '%1%'", path);
         throw;
     }
+    if (sync)
+        fd.fsync();
+    // Explicitly close to make sure exceptions are propagated.
+    fd.close();
+    if (sync)
+        syncParent(path);
+}
+
+void syncParent(const Path & path)
+{
+    AutoCloseFD fd = open(dirOf(path).c_str(), O_RDONLY, 0);
+    if (!fd)
+        throw SysError("opening file '%1%'", path);
+    fd.fsync();
 }
 
 std::string readLine(int fd)
@@ -406,8 +448,29 @@ static void _deletePath(int parentfd, const Path & path, uint64_t & bytesFreed)
         throw SysError("getting status of '%1%'", path);
     }
 
-    if (!S_ISDIR(st.st_mode) && st.st_nlink == 1)
-        bytesFreed += st.st_size;
+    if (!S_ISDIR(st.st_mode)) {
+        /* We are about to delete a file. Will it likely free space? */
+
+        switch (st.st_nlink) {
+            /* Yes: last link. */
+            case 1:
+                bytesFreed += st.st_size;
+                break;
+            /* Maybe: yes, if 'auto-optimise-store' or manual optimisation
+               was performed. Instead of checking for real let's assume
+               it's an optimised file and space will be freed.
+
+               In worst case we will double count on freed space for files
+               with exactly two hardlinks for unoptimised packages.
+             */
+            case 2:
+                bytesFreed += st.st_size;
+                break;
+            /* No: 3+ links. */
+            default:
+                break;
+        }
+    }
 
     if (S_ISDIR(st.st_mode)) {
         /* Make the directory accessible. */
@@ -465,61 +528,6 @@ void deletePath(const Path & path, uint64_t & bytesFreed)
 }
 
 
-static Path tempName(Path tmpRoot, const Path & prefix, bool includePid,
-    int & counter)
-{
-    tmpRoot = canonPath(tmpRoot.empty() ? getEnv("TMPDIR").value_or("/tmp") : tmpRoot, true);
-    if (includePid)
-        return (format("%1%/%2%-%3%-%4%") % tmpRoot % prefix % getpid() % counter++).str();
-    else
-        return (format("%1%/%2%-%3%") % tmpRoot % prefix % counter++).str();
-}
-
-
-Path createTempDir(const Path & tmpRoot, const Path & prefix,
-    bool includePid, bool useGlobalCounter, mode_t mode)
-{
-    static int globalCounter = 0;
-    int localCounter = 0;
-    int & counter(useGlobalCounter ? globalCounter : localCounter);
-
-    while (1) {
-        checkInterrupt();
-        Path tmpDir = tempName(tmpRoot, prefix, includePid, counter);
-        if (mkdir(tmpDir.c_str(), mode) == 0) {
-#if __FreeBSD__
-            /* Explicitly set the group of the directory.  This is to
-               work around around problems caused by BSD's group
-               ownership semantics (directories inherit the group of
-               the parent).  For instance, the group of /tmp on
-               FreeBSD is "wheel", so all directories created in /tmp
-               will be owned by "wheel"; but if the user is not in
-               "wheel", then "tar" will fail to unpack archives that
-               have the setgid bit set on directories. */
-            if (chown(tmpDir.c_str(), (uid_t) -1, getegid()) != 0)
-                throw SysError("setting group of directory '%1%'", tmpDir);
-#endif
-            return tmpDir;
-        }
-        if (errno != EEXIST)
-            throw SysError("creating directory '%1%'", tmpDir);
-    }
-}
-
-
-std::pair<AutoCloseFD, Path> createTempFile(const Path & prefix)
-{
-    Path tmpl(getEnv("TMPDIR").value_or("/tmp") + "/" + prefix + ".XXXXXX");
-    // Strictly speaking, this is UB, but who cares...
-    // FIXME: use O_TMPFILE.
-    AutoCloseFD fd(mkstemp((char *) tmpl.c_str()));
-    if (!fd)
-        throw SysError("creating temporary file '%s'", tmpl);
-    closeOnExec(fd.get());
-    return {std::move(fd), tmpl};
-}
-
-
 std::string getUserName()
 {
     auto pw = getpwuid(geteuid());
@@ -534,7 +542,21 @@ Path getHome()
 {
     static Path homeDir = []()
     {
+        std::optional<std::string> unownedUserHomeDir = {};
         auto homeDir = getEnv("HOME");
+        if (homeDir) {
+            // Only use $HOME if doesn't exist or is owned by the current user.
+            struct stat st;
+            int result = stat(homeDir->c_str(), &st);
+            if (result != 0) {
+                if (errno != ENOENT) {
+                    warn("couldn't stat $HOME ('%s') for reason other than not existing ('%d'), falling back to the one defined in the 'passwd' file", *homeDir, errno);
+                    homeDir.reset();
+                }
+            } else if (st.st_uid != geteuid()) {
+                unownedUserHomeDir.swap(homeDir);
+            }
+        }
         if (!homeDir) {
             std::vector<char> buf(16384);
             struct passwd pwbuf;
@@ -543,6 +565,9 @@ Path getHome()
                 || !pw || !pw->pw_dir || !pw->pw_dir[0])
                 throw Error("cannot determine user's home directory");
             homeDir = pw->pw_dir;
+            if (unownedUserHomeDir.has_value() && unownedUserHomeDir != homeDir) {
+                warn("$HOME ('%s') is not owned by you, falling back to the one defined in the 'passwd' file ('%s')", *unownedUserHomeDir, *homeDir);
+            }
         }
         return *homeDir;
     }();
@@ -580,6 +605,27 @@ Path getDataDir()
 }
 
 
+std::optional<Path> getSelfExe()
+{
+    static auto cached = []() -> std::optional<Path>
+    {
+        #if __linux__
+        return readLink("/proc/self/exe");
+        #elif __APPLE__
+        char buf[1024];
+        uint32_t size = sizeof(buf);
+        if (_NSGetExecutablePath(buf, &size) == 0)
+            return buf;
+        else
+            return std::nullopt;
+        #else
+        return std::nullopt;
+        #endif
+    }();
+    return cached;
+}
+
+
 Paths createDirs(const Path & path)
 {
     Paths created;
@@ -603,44 +649,6 @@ Paths createDirs(const Path & path)
 }
 
 
-void createSymlink(const Path & target, const Path & link,
-    std::optional<time_t> mtime)
-{
-    if (symlink(target.c_str(), link.c_str()))
-        throw SysError("creating symlink from '%1%' to '%2%'", link, target);
-    if (mtime) {
-        struct timeval times[2];
-        times[0].tv_sec = *mtime;
-        times[0].tv_usec = 0;
-        times[1].tv_sec = *mtime;
-        times[1].tv_usec = 0;
-        if (lutimes(link.c_str(), times))
-            throw SysError("setting time of symlink '%s'", link);
-    }
-}
-
-
-void replaceSymlink(const Path & target, const Path & link,
-    std::optional<time_t> mtime)
-{
-    for (unsigned int n = 0; true; n++) {
-        Path tmp = canonPath(fmt("%s/.%d_%s", dirOf(link), n, baseNameOf(link)));
-
-        try {
-            createSymlink(target, tmp, mtime);
-        } catch (SysError & e) {
-            if (e.errNo == EEXIST) continue;
-            throw;
-        }
-
-        if (rename(tmp.c_str(), link.c_str()) != 0)
-            throw SysError("renaming '%1%' to '%2%'", tmp, link);
-
-        break;
-    }
-}
-
-
 void readFull(int fd, char * buf, size_t count)
 {
     while (count) {
@@ -682,7 +690,14 @@ std::string drainFD(int fd, bool block, const size_t reserveSize)
 
 void drainFD(int fd, Sink & sink, bool block)
 {
-    int saved;
+    // silence GCC maybe-uninitialized warning in finally
+    int saved = 0;
+
+    if (!block) {
+        saved = fcntl(fd, F_GETFL);
+        if (fcntl(fd, F_SETFL, saved | O_NONBLOCK) == -1)
+            throw SysError("making file descriptor non-blocking");
+    }
 
     Finally finally([&]() {
         if (!block) {
@@ -691,12 +706,6 @@ void drainFD(int fd, Sink & sink, bool block)
         }
     });
 
-    if (!block) {
-        saved = fcntl(fd, F_GETFL);
-        if (fcntl(fd, F_SETFL, saved | O_NONBLOCK) == -1)
-            throw SysError("making file descriptor non-blocking");
-    }
-
     std::vector<unsigned char> buf(64 * 1024);
     while (1) {
         checkInterrupt();
@@ -712,7 +721,55 @@ void drainFD(int fd, Sink & sink, bool block)
     }
 }
 
+//////////////////////////////////////////////////////////////////////
+
+unsigned int getMaxCPU()
+{
+    #if __linux__
+    try {
+        FILE *fp = fopen("/proc/mounts", "r");
+        if (!fp)
+            return 0;
+
+        Strings cgPathParts;
+
+        struct mntent *ent;
+        while ((ent = getmntent(fp))) {
+            std::string mountType, mountPath;
 
+            mountType = ent->mnt_type;
+            mountPath = ent->mnt_dir;
+
+            if (mountType == "cgroup2") {
+                cgPathParts.push_back(mountPath);
+                break;
+            }
+        }
+
+        fclose(fp);
+
+        if (cgPathParts.size() > 0 && pathExists("/proc/self/cgroup")) {
+            std::string currentCgroup = readFile("/proc/self/cgroup");
+            Strings cgValues = tokenizeString<Strings>(currentCgroup, ":");
+            cgPathParts.push_back(trim(cgValues.back(), "\n"));
+            cgPathParts.push_back("cpu.max");
+            std::string fullCgPath = canonPath(concatStringsSep("/", cgPathParts));
+
+            if (pathExists(fullCgPath)) {
+                std::string cpuMax = readFile(fullCgPath);
+                std::vector<std::string> cpuMaxParts = tokenizeString<std::vector<std::string>>(cpuMax, " ");
+                std::string quota = cpuMaxParts[0];
+                std::string period = trim(cpuMaxParts[1], "\n");
+
+                if (quota != "max")
+                    return std::ceil(std::stoi(quota) / std::stof(period));
+            }
+        }
+    } catch (Error &) { ignoreException(); }
+    #endif
+
+    return 0;
+}
 
 //////////////////////////////////////////////////////////////////////
 
@@ -804,6 +861,20 @@ void AutoCloseFD::close()
     }
 }
 
+void AutoCloseFD::fsync()
+{
+  if (fd != -1) {
+      int result;
+#if __APPLE__
+      result = ::fcntl(fd, F_FULLFSYNC);
+#else
+      result = ::fsync(fd);
+#endif
+      if (result == -1)
+          throw SysError("fsync file descriptor %1%", fd);
+  }
+}
+
 
 AutoCloseFD::operator bool() const
 {
@@ -1042,7 +1113,7 @@ std::string runProgram(Path program, bool searchPath, const Strings & args,
     auto res = runProgram(RunOptions {.program = program, .searchPath = searchPath, .args = args, .input = input});
 
     if (!statusOk(res.first))
-        throw ExecError(res.first, fmt("program '%1%' %2%", program, statusToString(res.first)));
+        throw ExecError(res.first, "program '%1%' %2%", program, statusToString(res.first));
 
     return res.second;
 }
@@ -1170,7 +1241,7 @@ void runProgram2(const RunOptions & options)
     if (source) promise.get_future().get();
 
     if (status)
-        throw ExecError(status, fmt("program '%1%' %2%", options.program, statusToString(status)));
+        throw ExecError(status, "program '%1%' %2%", options.program, statusToString(status));
 }
 
 
@@ -1239,9 +1310,9 @@ template<class C> C tokenizeString(std::string_view s, std::string_view separato
 {
     C result;
     auto pos = s.find_first_not_of(separators, 0);
-    while (pos != std::string::npos) {
+    while (pos != std::string_view::npos) {
         auto end = s.find_first_of(separators, pos + 1);
-        if (end == std::string::npos) end = s.size();
+        if (end == std::string_view::npos) end = s.size();
         result.insert(result.end(), std::string(s, pos, end - pos));
         pos = s.find_first_not_of(separators, end);
     }
@@ -1263,9 +1334,9 @@ std::string chomp(std::string_view s)
 std::string trim(std::string_view s, std::string_view whitespace)
 {
     auto i = s.find_first_not_of(whitespace);
-    if (i == std::string_view::npos) return "";
+    if (i == s.npos) return "";
     auto j = s.find_last_not_of(whitespace);
-    return std::string(s, i, j == std::string::npos ? j : j - i + 1);
+    return std::string(s, i, j == s.npos ? j : j - i + 1);
 }
 
 
@@ -1412,7 +1483,7 @@ std::string filterANSIEscapes(const std::string & s, bool filterAll, unsigned in
             }
         }
 
-        else if (*i == '\r')
+        else if (*i == '\r' || *i == '\a')
             // do nothing for now
             i++;
 
@@ -1451,6 +1522,7 @@ constexpr char base64Chars[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv
 std::string base64Encode(std::string_view s)
 {
     std::string res;
+    res.reserve((s.size() + 2) / 3 * 4);
     int data = 0, nbits = 0;
 
     for (char c : s) {
@@ -1482,6 +1554,9 @@ std::string base64Decode(std::string_view s)
     }();
 
     std::string res;
+    // Some sequences are missing the padding consisting of up to two '='.
+    //                    vvv
+    res.reserve((s.size() + 2) / 4 * 3);
     unsigned int d = 0, bits = 0;
 
     for (char c : s) {
@@ -1544,7 +1619,6 @@ std::string stripIndentation(std::string_view s)
 
 //////////////////////////////////////////////////////////////////////
 
-
 static Sync<std::pair<unsigned short, unsigned short>> windowSize{{0, 0}};
 
 
@@ -1668,7 +1742,9 @@ void setStackSize(size_t stackSize)
     #endif
 }
 
+#if __linux__
 static AutoCloseFD fdSavedMountNamespace;
+#endif
 
 void saveMountNamespace()
 {
@@ -1687,8 +1763,13 @@ void restoreMountNamespace()
 {
 #if __linux__
     try {
+        auto savedCwd = absPath(".");
+
         if (fdSavedMountNamespace && setns(fdSavedMountNamespace.get(), CLONE_NEWNS) == -1)
             throw SysError("restoring parent mount namespace");
+        if (chdir(savedCwd.c_str()) == -1) {
+            throw SysError("restoring cwd");
+        }
     } catch (Error & e) {
         debug(e.msg());
     }
@@ -1768,7 +1849,7 @@ AutoCloseFD createUnixDomainSocket(const Path & path, mode_t mode)
     if (chmod(path.c_str(), mode) == -1)
         throw SysError("changing permissions on '%1%'", path);
 
-    if (listen(fdSocket.get(), 5) == -1)
+    if (listen(fdSocket.get(), 100) == -1)
         throw SysError("cannot listen on socket '%1%'", path);
 
     return fdSocket;
diff --git a/src/libutil/util.hh b/src/libutil/util.hh
index 20591952d..e5c678682 100644
--- a/src/libutil/util.hh
+++ b/src/libutil/util.hh
@@ -68,6 +68,9 @@ Path dirOf(const PathView path);
    following the final `/' (trailing slashes are removed). */
 std::string_view baseNameOf(std::string_view path);
 
+/* Perform tilde expansion on a path. */
+std::string expandTilde(std::string_view path);
+
 /* Check whether 'path' is a descendant of 'dir'. Both paths must be
    canonicalized. */
 bool isInDir(std::string_view path, std::string_view dir);
@@ -77,6 +80,7 @@ bool isInDir(std::string_view path, std::string_view dir);
 bool isDirOrInDir(std::string_view path, std::string_view dir);
 
 /* Get status of `path'. */
+struct stat stat(const Path & path);
 struct stat lstat(const Path & path);
 
 /* Return true iff the given path exists. */
@@ -111,9 +115,12 @@ std::string readFile(const Path & path);
 void readFile(const Path & path, Sink & sink);
 
 /* Write a string to a file. */
-void writeFile(const Path & path, std::string_view s, mode_t mode = 0666);
+void writeFile(const Path & path, std::string_view s, mode_t mode = 0666, bool sync = false);
+
+void writeFile(const Path & path, Source & source, mode_t mode = 0666, bool sync = false);
 
-void writeFile(const Path & path, Source & source, mode_t mode = 0666);
+/* Flush a file's parent directory to disk */
+void syncParent(const Path & path);
 
 /* Read a line from a file descriptor. */
 std::string readLine(int fd);
@@ -145,10 +152,14 @@ std::vector<Path> getConfigDirs();
 /* Return $XDG_DATA_HOME or $HOME/.local/share. */
 Path getDataDir();
 
+/* Return the path of the current executable. */
+std::optional<Path> getSelfExe();
+
 /* Create a directory and all its parents, if necessary.  Returns the
    list of created directories, in order of creation. */
 Paths createDirs(const Path & path);
-inline Paths createDirs(PathView path) {
+inline Paths createDirs(PathView path)
+{
     return createDirs(Path(path));
 }
 
@@ -160,6 +171,17 @@ void createSymlink(const Path & target, const Path & link,
 void replaceSymlink(const Path & target, const Path & link,
     std::optional<time_t> mtime = {});
 
+void renameFile(const Path & src, const Path & dst);
+
+/**
+ * Similar to 'renameFile', but fallback to a copy+remove if `src` and `dst`
+ * are on a different filesystem.
+ *
+ * Beware that this might not be atomic because of the copy that happens behind
+ * the scenes
+ */
+void moveFile(const Path & src, const Path & dst);
+
 
 /* Wrappers arount read()/write() that read/write exactly the
    requested number of bytes. */
@@ -174,6 +196,9 @@ std::string drainFD(int fd, bool block = true, const size_t reserveSize=0);
 
 void drainFD(int fd, Sink & sink, bool block = true);
 
+/* If cgroups are active, attempt to calculate the number of CPUs available.
+   If cgroups are unavailable or if cpu.max is set to "max", return 0. */
+unsigned int getMaxCPU();
 
 /* Automatic cleanup of resources. */
 
@@ -209,6 +234,7 @@ public:
     explicit operator bool() const;
     int release();
     void close();
+    void fsync();
 };
 
 
@@ -539,13 +565,31 @@ std::string stripIndentation(std::string_view s);
 
 /* Get a value for the specified key from an associate container. */
 template <class T>
-std::optional<typename T::mapped_type> get(const T & map, const typename T::key_type & key)
+const typename T::mapped_type * get(const T & map, const typename T::key_type & key)
+{
+    auto i = map.find(key);
+    if (i == map.end()) return nullptr;
+    return &i->second;
+}
+
+template <class T>
+typename T::mapped_type * get(T & map, const typename T::key_type & key)
 {
     auto i = map.find(key);
-    if (i == map.end()) return {};
-    return std::optional<typename T::mapped_type>(i->second);
+    if (i == map.end()) return nullptr;
+    return &i->second;
 }
 
+/* Get a value for the specified key from an associate container, or a default value if the key isn't present. */
+template <class T>
+const typename T::mapped_type & getOr(T & map,
+    const typename T::key_type & key,
+    const typename T::mapped_type & defaultValue)
+{
+    auto i = map.find(key);
+    if (i == map.end()) return defaultValue;
+    return i->second;
+}
 
 /* Remove and return the first item from a container. */
 template <class T>
@@ -678,4 +722,19 @@ template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;
 std::string showBytes(uint64_t bytes);
 
 
+/* Provide an addition operator between strings and string_views
+   inexplicably omitted from the standard library. */
+inline std::string operator + (const std::string & s1, std::string_view s2)
+{
+    auto s = s1;
+    s.append(s2);
+    return s;
+}
+
+inline std::string operator + (std::string && s, std::string_view s2)
+{
+    s.append(s2);
+    return std::move(s);
+}
+
 }