about summary refs log tree commit diff
path: root/third_party/nix/src/libutil
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/nix/src/libutil')
-rw-r--r--third_party/nix/src/libutil/CMakeLists.txt68
-rw-r--r--third_party/nix/src/libutil/affinity.cc60
-rw-r--r--third_party/nix/src/libutil/affinity.hh9
-rw-r--r--third_party/nix/src/libutil/archive.cc398
-rw-r--r--third_party/nix/src/libutil/archive.hh77
-rw-r--r--third_party/nix/src/libutil/args.cc219
-rw-r--r--third_party/nix/src/libutil/args.hh221
-rw-r--r--third_party/nix/src/libutil/compression.cc400
-rw-r--r--third_party/nix/src/libutil/compression.hh31
-rw-r--r--third_party/nix/src/libutil/config.cc370
-rw-r--r--third_party/nix/src/libutil/config.hh228
-rw-r--r--third_party/nix/src/libutil/finally.hh13
-rw-r--r--third_party/nix/src/libutil/hash.cc484
-rw-r--r--third_party/nix/src/libutil/hash.hh147
-rw-r--r--third_party/nix/src/libutil/istringstream_nocopy.hh85
-rw-r--r--third_party/nix/src/libutil/json.cc198
-rw-r--r--third_party/nix/src/libutil/json.hh144
-rw-r--r--third_party/nix/src/libutil/lazy.hh45
-rw-r--r--third_party/nix/src/libutil/lru-cache.hh90
-rw-r--r--third_party/nix/src/libutil/monitor-fd.hh57
-rw-r--r--third_party/nix/src/libutil/pool.hh176
-rw-r--r--third_party/nix/src/libutil/proto.hh174
-rw-r--r--third_party/nix/src/libutil/ref.hh65
-rw-r--r--third_party/nix/src/libutil/serialise.cc311
-rw-r--r--third_party/nix/src/libutil/serialise.hh289
-rw-r--r--third_party/nix/src/libutil/status.hh17
-rw-r--r--third_party/nix/src/libutil/sync.hh84
-rw-r--r--third_party/nix/src/libutil/thread-pool.cc163
-rw-r--r--third_party/nix/src/libutil/thread-pool.hh140
-rw-r--r--third_party/nix/src/libutil/types.hh118
-rw-r--r--third_party/nix/src/libutil/util.cc1426
-rw-r--r--third_party/nix/src/libutil/util.hh476
-rw-r--r--third_party/nix/src/libutil/visitor.hh19
-rw-r--r--third_party/nix/src/libutil/xml-writer.cc93
-rw-r--r--third_party/nix/src/libutil/xml-writer.hh52
35 files changed, 6947 insertions, 0 deletions
diff --git a/third_party/nix/src/libutil/CMakeLists.txt b/third_party/nix/src/libutil/CMakeLists.txt
new file mode 100644
index 000000000000..0b36929218e8
--- /dev/null
+++ b/third_party/nix/src/libutil/CMakeLists.txt
@@ -0,0 +1,68 @@
+# -*- mode: cmake; -*-
+add_library(nixutil SHARED)
+set_property(TARGET nixutil PROPERTY CXX_STANDARD 17)
+include_directories(${PROJECT_BINARY_DIR}) # for config.h
+target_compile_features(nixutil PUBLIC cxx_std_17)
+
+set(HEADER_FILES
+    affinity.hh
+    archive.hh
+    args.hh
+    compression.hh
+    config.hh
+    finally.hh
+    hash.hh
+    istringstream_nocopy.hh
+    json.hh
+    lazy.hh
+    lru-cache.hh
+    monitor-fd.hh
+    pool.hh
+    proto.hh
+    ref.hh
+    serialise.hh
+    status.hh
+    sync.hh
+    thread-pool.hh
+    types.hh
+    util.hh
+    visitor.hh
+    xml-writer.hh
+)
+
+target_sources(nixutil
+  PUBLIC
+    ${HEADER_FILES}
+
+  PRIVATE
+    affinity.cc
+    archive.cc
+    args.cc
+    compression.cc
+    config.cc
+    hash.cc
+    json.cc
+    serialise.cc
+    thread-pool.cc
+    util.cc
+    xml-writer.cc
+)
+
+target_link_libraries(nixutil
+  nixproto
+  absl::strings
+  absl::statusor
+  glog
+  BZip2::BZip2
+  LibLZMA::LibLZMA
+  Boost::context
+  brotlienc
+  brotlidec
+  ssl
+)
+
+# Install header files to include/libutil and mark them for automatic
+# inclusion in targets that link to this one.
+target_include_directories(nixutil PUBLIC "${nix_SOURCE_DIR}/src")
+INSTALL(FILES ${HEADER_FILES} DESTINATION ${CMAKE_INSTALL_INCLUDEDIR}/nix/libutil)
+INSTALL(TARGETS nixutil DESTINATION ${CMAKE_INSTALL_LIBDIR})
diff --git a/third_party/nix/src/libutil/affinity.cc b/third_party/nix/src/libutil/affinity.cc
new file mode 100644
index 000000000000..03fbe1243992
--- /dev/null
+++ b/third_party/nix/src/libutil/affinity.cc
@@ -0,0 +1,60 @@
+#include "libutil/affinity.hh"
+
+#include <glog/logging.h>
+
+#include "libutil/types.hh"
+#include "libutil/util.hh"
+
+#if __linux__
+#include <sched.h>
+#endif
+
+namespace nix {
+
+#if __linux__
+static bool didSaveAffinity = false;
+static cpu_set_t savedAffinity;
+#endif
+
+void setAffinityTo(int cpu) {
+#if __linux__
+  if (sched_getaffinity(0, sizeof(cpu_set_t), &savedAffinity) == -1) {
+    return;
+  }
+
+  didSaveAffinity = true;
+  DLOG(INFO) << "locking this thread to CPU " << cpu;
+  cpu_set_t newAffinity;
+  CPU_ZERO(&newAffinity);
+  CPU_SET(cpu, &newAffinity);
+  if (sched_setaffinity(0, sizeof(cpu_set_t), &newAffinity) == -1) {
+    LOG(ERROR) << "failed to lock thread to CPU " << cpu;
+  }
+#endif
+}
+
+int lockToCurrentCPU() {
+#if __linux__
+  int cpu = sched_getcpu();
+  if (cpu != -1) {
+    setAffinityTo(cpu);
+  }
+  return cpu;
+#else
+  return -1;
+#endif
+}
+
+void restoreAffinity() {
+#if __linux__
+  if (!didSaveAffinity) {
+    return;
+  }
+
+  if (sched_setaffinity(0, sizeof(cpu_set_t), &savedAffinity) == -1) {
+    LOG(ERROR) << "failed to restore affinity";
+  }
+#endif
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/affinity.hh b/third_party/nix/src/libutil/affinity.hh
new file mode 100644
index 000000000000..5e5ef9b0de0d
--- /dev/null
+++ b/third_party/nix/src/libutil/affinity.hh
@@ -0,0 +1,9 @@
+#pragma once
+
+namespace nix {
+
+void setAffinityTo(int cpu);
+int lockToCurrentCPU();
+void restoreAffinity();
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/archive.cc b/third_party/nix/src/libutil/archive.cc
new file mode 100644
index 000000000000..e470ad7be6ce
--- /dev/null
+++ b/third_party/nix/src/libutil/archive.cc
@@ -0,0 +1,398 @@
+#include "libutil/archive.hh"
+
+#include <algorithm>
+#include <cerrno>
+#include <map>
+#include <vector>
+
+#include <dirent.h>
+#include <fcntl.h>
+#include <glog/logging.h>
+#include <strings.h>  // for strcasecmp
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include "libutil/config.hh"
+#include "libutil/util.hh"
+
+namespace nix {
+
+struct ArchiveSettings : Config {
+  Setting<bool> useCaseHack {
+    this,
+#if __APPLE__
+        true,
+#else
+        false,
+#endif
+        "use-case-hack",
+        "Whether to enable a Darwin-specific hack for dealing with file name "
+        "collisions."
+  };
+};
+
+static ArchiveSettings archiveSettings;
+
+static GlobalConfig::Register r1(&archiveSettings);
+
+constexpr std::string_view kCaseHackSuffix = "~nix~case~hack~";
+
+PathFilter defaultPathFilter = [](const Path& /*unused*/) { return true; };
+
+static void dumpContents(const Path& path, size_t size, Sink& sink) {
+  sink << "contents" << size;
+
+  AutoCloseFD fd(open(path.c_str(), O_RDONLY | O_CLOEXEC));
+  if (!fd) {
+    throw SysError(format("opening file '%1%'") % path);
+  }
+
+  std::vector<unsigned char> buf(65536);
+  size_t left = size;
+
+  while (left > 0) {
+    auto n = std::min(left, buf.size());
+    readFull(fd.get(), buf.data(), n);
+    left -= n;
+    sink(buf.data(), n);
+  }
+
+  writePadding(size, sink);
+}
+
+static void dump(const Path& path, Sink& sink, PathFilter& filter) {
+  checkInterrupt();
+
+  struct stat st;
+  if (lstat(path.c_str(), &st) != 0) {
+    throw SysError(format("getting attributes of path '%1%'") % path);
+  }
+
+  sink << "(";
+
+  if (S_ISREG(st.st_mode)) {
+    sink << "type"
+         << "regular";
+    if ((st.st_mode & S_IXUSR) != 0u) {
+      sink << "executable"
+           << "";
+    }
+    dumpContents(path, static_cast<size_t>(st.st_size), sink);
+  }
+
+  else if (S_ISDIR(st.st_mode)) {
+    sink << "type"
+         << "directory";
+
+    /* If we're on a case-insensitive system like macOS, undo
+       the case hack applied by restorePath(). */
+    std::map<std::string, std::string> unhacked;
+    for (auto& i : readDirectory(path)) {
+      if (archiveSettings.useCaseHack) {
+        std::string name(i.name);
+        size_t pos = i.name.find(kCaseHackSuffix);
+        if (pos != std::string::npos) {
+          DLOG(INFO) << "removing case hack suffix from " << path << "/"
+                     << i.name;
+
+          name.erase(pos);
+        }
+        if (unhacked.find(name) != unhacked.end()) {
+          throw Error(format("file name collision in between '%1%' and '%2%'") %
+                      (path + "/" + unhacked[name]) % (path + "/" + i.name));
+        }
+        unhacked[name] = i.name;
+      } else {
+        unhacked[i.name] = i.name;
+      }
+    }
+
+    for (auto& i : unhacked) {
+      if (filter(path + "/" + i.first)) {
+        sink << "entry"
+             << "("
+             << "name" << i.first << "node";
+        dump(path + "/" + i.second, sink, filter);
+        sink << ")";
+      }
+    }
+  }
+
+  else if (S_ISLNK(st.st_mode)) {
+    sink << "type"
+         << "symlink"
+         << "target" << readLink(path);
+
+  } else {
+    throw Error(format("file '%1%' has an unsupported type") % path);
+  }
+
+  sink << ")";
+}
+
+void dumpPath(const Path& path, Sink& sink, PathFilter& filter) {
+  sink << std::string(kNarVersionMagic1);
+  dump(path, sink, filter);
+}
+
+void dumpString(const std::string& s, Sink& sink) {
+  sink << std::string(kNarVersionMagic1) << "("
+       << "type"
+       << "regular"
+       << "contents" << s << ")";
+}
+
+static SerialisationError badArchive(const std::string& s) {
+  return SerialisationError("bad archive: " + s);
+}
+
+#if 0
+static void skipGeneric(Source & source)
+{
+    if (readString(source) == "(") {
+        while (readString(source) != ")")
+            skipGeneric(source);
+    }
+}
+#endif
+
+static void parseContents(ParseSink& sink, Source& source, const Path& path) {
+  unsigned long long size = readLongLong(source);
+
+  sink.preallocateContents(size);
+
+  unsigned long long left = size;
+  std::vector<unsigned char> buf(65536);
+
+  while (left != 0u) {
+    checkInterrupt();
+    auto n = buf.size();
+    if (static_cast<unsigned long long>(n) > left) {
+      n = left;
+    }
+    source(buf.data(), n);
+    sink.receiveContents(buf.data(), n);
+    left -= n;
+  }
+
+  readPadding(size, source);
+}
+
+struct CaseInsensitiveCompare {
+  bool operator()(const std::string& a, const std::string& b) const {
+    return strcasecmp(a.c_str(), b.c_str()) < 0;
+  }
+};
+
+static void parse(ParseSink& sink, Source& source, const Path& path) {
+  std::string s;
+
+  s = readString(source);
+  if (s != "(") {
+    throw badArchive("expected open tag");
+  }
+
+  enum { tpUnknown, tpRegular, tpDirectory, tpSymlink } type = tpUnknown;
+
+  std::map<Path, int, CaseInsensitiveCompare> names;
+
+  while (true) {
+    checkInterrupt();
+
+    s = readString(source);
+
+    if (s == ")") {
+      break;
+    }
+
+    if (s == "type") {
+      if (type != tpUnknown) {
+        throw badArchive("multiple type fields");
+      }
+      std::string t = readString(source);
+
+      if (t == "regular") {
+        type = tpRegular;
+        sink.createRegularFile(path);
+      }
+
+      else if (t == "directory") {
+        sink.createDirectory(path);
+        type = tpDirectory;
+      }
+
+      else if (t == "symlink") {
+        type = tpSymlink;
+      }
+
+      else {
+        throw badArchive("unknown file type " + t);
+      }
+
+    }
+
+    else if (s == "contents" && type == tpRegular) {
+      parseContents(sink, source, path);
+    }
+
+    else if (s == "executable" && type == tpRegular) {
+      auto s = readString(source);
+      if (!s.empty()) {
+        throw badArchive("executable marker has non-empty value");
+      }
+      sink.isExecutable();
+    }
+
+    else if (s == "entry" && type == tpDirectory) {
+      std::string name;
+      std::string prevName;
+
+      s = readString(source);
+      if (s != "(") {
+        throw badArchive("expected open tag");
+      }
+
+      while (true) {
+        checkInterrupt();
+
+        s = readString(source);
+
+        if (s == ")") {
+          break;
+        }
+        if (s == "name") {
+          name = readString(source);
+          if (name.empty() || name == "." || name == ".." ||
+              name.find('/') != std::string::npos ||
+              name.find(static_cast<char>(0)) != std::string::npos) {
+            throw Error(format("NAR contains invalid file name '%1%'") % name);
+          }
+          if (name <= prevName) {
+            throw Error("NAR directory is not sorted");
+          }
+          prevName = name;
+          if (archiveSettings.useCaseHack) {
+            auto i = names.find(name);
+            if (i != names.end()) {
+              DLOG(INFO) << "case collision between '" << i->first << "' and '"
+                         << name << "'";
+              name += kCaseHackSuffix;
+              name += std::to_string(++i->second);
+            } else {
+              names[name] = 0;
+            }
+          }
+        } else if (s == "node") {
+          if (s.empty()) {
+            throw badArchive("entry name missing");
+          }
+          parse(sink, source, path + "/" + name);
+        } else {
+          throw badArchive("unknown field " + s);
+        }
+      }
+    }
+
+    else if (s == "target" && type == tpSymlink) {
+      std::string target = readString(source);
+      sink.createSymlink(path, target);
+    }
+
+    else {
+      throw badArchive("unknown field " + s);
+    }
+  }
+}
+
+void parseDump(ParseSink& sink, Source& source) {
+  std::string version;
+  try {
+    version = readString(source, kNarVersionMagic1.size());
+  } catch (SerialisationError& e) {
+    /* This generally means the integer at the start couldn't be
+       decoded.  Ignore and throw the exception below. */
+  }
+  if (version != kNarVersionMagic1) {
+    throw badArchive("input doesn't look like a Nix archive");
+  }
+  parse(sink, source, "");
+}
+
+struct RestoreSink : ParseSink {
+  Path dstPath;
+  AutoCloseFD fd;
+
+  void createDirectory(const Path& path) override {
+    Path p = dstPath + path;
+    if (mkdir(p.c_str(), 0777) == -1) {
+      throw SysError(format("creating directory '%1%'") % p);
+    }
+  };
+
+  void createRegularFile(const Path& path) override {
+    Path p = dstPath + path;
+    fd = AutoCloseFD(
+        open(p.c_str(), O_CREAT | O_EXCL | O_WRONLY | O_CLOEXEC, 0666));
+    if (!fd) {
+      throw SysError(format("creating file '%1%'") % p);
+    }
+  }
+
+  void isExecutable() override {
+    struct stat st;
+    if (fstat(fd.get(), &st) == -1) {
+      throw SysError("fstat");
+    }
+    if (fchmod(fd.get(), st.st_mode | (S_IXUSR | S_IXGRP | S_IXOTH)) == -1) {
+      throw SysError("fchmod");
+    }
+  }
+
+  void preallocateContents(unsigned long long len) override {
+#if HAVE_POSIX_FALLOCATE
+    if (len != 0u) {
+      errno = posix_fallocate(fd.get(), 0, len);
+      /* Note that EINVAL may indicate that the underlying
+         filesystem doesn't support preallocation (e.g. on
+         OpenSolaris).  Since preallocation is just an
+         optimisation, ignore it. */
+      if (errno && errno != EINVAL && errno != EOPNOTSUPP && errno != ENOSYS) {
+        throw SysError(format("preallocating file of %1% bytes") % len);
+      }
+    }
+#endif
+  }
+
+  void receiveContents(unsigned char* data, unsigned int len) override {
+    writeFull(fd.get(), data, len);
+  }
+
+  void createSymlink(const Path& path, const std::string& target) override {
+    Path p = dstPath + path;
+    nix::createSymlink(target, p);
+  }
+};
+
+void restorePath(const Path& path, Source& source) {
+  RestoreSink sink;
+  sink.dstPath = path;
+  parseDump(sink, source);
+}
+
+void copyNAR(Source& source, Sink& sink) {
+  // FIXME: if 'source' is the output of dumpPath() followed by EOF,
+  // we should just forward all data directly without parsing.
+
+  ParseSink parseSink; /* null sink; just parse the NAR */
+
+  LambdaSource wrapper([&](unsigned char* data, size_t len) {
+    auto n = source.read(data, len);
+    sink(data, n);
+    return n;
+  });
+
+  parseDump(parseSink, wrapper);
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/archive.hh b/third_party/nix/src/libutil/archive.hh
new file mode 100644
index 000000000000..396627878541
--- /dev/null
+++ b/third_party/nix/src/libutil/archive.hh
@@ -0,0 +1,77 @@
+#pragma once
+
+#include "libutil/serialise.hh"
+#include "libutil/types.hh"
+
+namespace nix {
+
+/* dumpPath creates a Nix archive of the specified path.  The format
+   is as follows:
+
+   IF path points to a REGULAR FILE:
+     dump(path) = attrs(
+       [ ("type", "regular")
+       , ("contents", contents(path))
+       ])
+
+   IF path points to a DIRECTORY:
+     dump(path) = attrs(
+       [ ("type", "directory")
+       , ("entries", concat(map(f, sort(entries(path)))))
+       ])
+       where f(fn) = attrs(
+         [ ("name", fn)
+         , ("file", dump(path + "/" + fn))
+         ])
+
+   where:
+
+     attrs(as) = concat(map(attr, as)) + encN(0)
+     attrs((a, b)) = encS(a) + encS(b)
+
+     encS(s) = encN(len(s)) + s + (padding until next 64-bit boundary)
+
+     encN(n) = 64-bit little-endian encoding of n.
+
+     contents(path) = the contents of a regular file.
+
+     sort(strings) = lexicographic sort by 8-bit value (strcmp).
+
+     entries(path) = the entries of a directory, without `.' and
+     `..'.
+
+     `+' denotes string concatenation. */
+
+void dumpPath(const Path& path, Sink& sink,
+              PathFilter& filter = defaultPathFilter);
+
+void dumpString(const std::string& s, Sink& sink);
+
+/* FIXME: fix this API, it sucks. */
+struct ParseSink {
+  virtual void createDirectory(const Path& path){};
+
+  virtual void createRegularFile(const Path& path){};
+  virtual void isExecutable(){};
+  virtual void preallocateContents(unsigned long long size){};
+  virtual void receiveContents(unsigned char* data, unsigned int len){};
+
+  virtual void createSymlink(const Path& path, const std::string& target){};
+};
+
+struct TeeSink : ParseSink {
+  TeeSource source;
+
+  explicit TeeSink(Source& source) : source(source) {}
+};
+
+void parseDump(ParseSink& sink, Source& source);
+
+void restorePath(const Path& path, Source& source);
+
+/* Read a NAR from 'source' and write it to 'sink'. */
+void copyNAR(Source& source, Sink& sink);
+
+constexpr std::string_view kNarVersionMagic1 = "nix-archive-1";
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/args.cc b/third_party/nix/src/libutil/args.cc
new file mode 100644
index 000000000000..2be8a1b0ce2a
--- /dev/null
+++ b/third_party/nix/src/libutil/args.cc
@@ -0,0 +1,219 @@
+#include "libutil/args.hh"
+
+#include "libutil/hash.hh"
+
+namespace nix {
+
+Args::FlagMaker Args::mkFlag() { return FlagMaker(*this); }
+
+Args::FlagMaker::~FlagMaker() {
+  assert(!flag->longName.empty());
+  args.longFlags[flag->longName] = flag;
+  if (flag->shortName != 0) {
+    args.shortFlags[flag->shortName] = flag;
+  }
+}
+
+void Args::parseCmdline(const Strings& _cmdline) {
+  Strings pendingArgs;
+  bool dashDash = false;
+
+  Strings cmdline(_cmdline);
+
+  for (auto pos = cmdline.begin(); pos != cmdline.end();) {
+    auto arg = *pos;
+
+    /* Expand compound dash options (i.e., `-qlf' -> `-q -l -f',
+       `-j3` -> `-j 3`). */
+    if (!dashDash && arg.length() > 2 && arg[0] == '-' && arg[1] != '-' &&
+        (isalpha(arg[1]) != 0)) {
+      *pos = std::string("-") + arg[1];
+      auto next = pos;
+      ++next;
+      for (unsigned int j = 2; j < arg.length(); j++) {
+        if (isalpha(arg[j]) != 0) {
+          cmdline.insert(next, std::string("-") + arg[j]);
+        } else {
+          cmdline.insert(next, std::string(arg, j));
+          break;
+        }
+      }
+      arg = *pos;
+    }
+
+    if (!dashDash && arg == "--") {
+      dashDash = true;
+      ++pos;
+    } else if (!dashDash && std::string(arg, 0, 1) == "-") {
+      if (!processFlag(pos, cmdline.end())) {
+        throw UsageError(format("unrecognised flag '%1%'") % arg);
+      }
+    } else {
+      pendingArgs.push_back(*pos++);
+      if (processArgs(pendingArgs, false)) {
+        pendingArgs.clear();
+      }
+    }
+  }
+
+  processArgs(pendingArgs, true);
+}
+
+void Args::printHelp(const std::string& programName, std::ostream& out) {
+  std::cout << "Usage: " << programName << " <FLAGS>...";
+  for (auto& exp : expectedArgs) {
+    std::cout << renderLabels({exp.label});
+    // FIXME: handle arity > 1
+    if (exp.arity == 0) {
+      std::cout << "...";
+    }
+    if (exp.optional) {
+      std::cout << "?";
+    }
+  }
+  std::cout << "\n";
+
+  auto s = description();
+  if (!s.empty()) {
+    std::cout << "\nSummary: " << s << ".\n";
+  }
+
+  if (!longFlags.empty() != 0u) {
+    std::cout << "\n";
+    std::cout << "Flags:\n";
+    printFlags(out);
+  }
+}
+
+void Args::printFlags(std::ostream& out) {
+  Table2 table;
+  for (auto& flag : longFlags) {
+    if (hiddenCategories.count(flag.second->category) != 0u) {
+      continue;
+    }
+    table.push_back(std::make_pair(
+        (flag.second->shortName != 0
+             ? std::string("-") + flag.second->shortName + ", "
+             : "    ") +
+            "--" + flag.first + renderLabels(flag.second->labels),
+        flag.second->description));
+  }
+  printTable(out, table);
+}
+
+bool Args::processFlag(Strings::iterator& pos, Strings::iterator end) {
+  assert(pos != end);
+
+  auto process = [&](const std::string& name, const Flag& flag) -> bool {
+    ++pos;
+    std::vector<std::string> args;
+    for (size_t n = 0; n < flag.arity; ++n) {
+      if (pos == end) {
+        if (flag.arity == ArityAny) {
+          break;
+        }
+        throw UsageError(format("flag '%1%' requires %2% argument(s)") % name %
+                         flag.arity);
+      }
+      args.push_back(*pos++);
+    }
+    flag.handler(std::move(args));
+    return true;
+  };
+
+  if (std::string(*pos, 0, 2) == "--") {
+    auto i = longFlags.find(std::string(*pos, 2));
+    if (i == longFlags.end()) {
+      return false;
+    }
+    return process("--" + i->first, *i->second);
+  }
+
+  if (std::string(*pos, 0, 1) == "-" && pos->size() == 2) {
+    auto c = (*pos)[1];
+    auto i = shortFlags.find(c);
+    if (i == shortFlags.end()) {
+      return false;
+    }
+    return process(std::string("-") + c, *i->second);
+  }
+
+  return false;
+}
+
+bool Args::processArgs(const Strings& args, bool finish) {
+  if (expectedArgs.empty()) {
+    if (!args.empty()) {
+      throw UsageError(format("unexpected argument '%1%'") % args.front());
+    }
+    return true;
+  }
+
+  auto& exp = expectedArgs.front();
+
+  bool res = false;
+
+  if ((exp.arity == 0 && finish) ||
+      (exp.arity > 0 && args.size() == exp.arity)) {
+    std::vector<std::string> ss;
+    for (auto& s : args) {
+      ss.push_back(s);
+    }
+    exp.handler(std::move(ss));
+    expectedArgs.pop_front();
+    res = true;
+  }
+
+  if (finish && !expectedArgs.empty() && !expectedArgs.front().optional) {
+    throw UsageError("more arguments are required");
+  }
+
+  return res;
+}
+
+Args::FlagMaker& Args::FlagMaker::mkHashTypeFlag(HashType* ht) {
+  arity(1);
+  label("type");
+  description("hash algorithm ('md5', 'sha1', 'sha256', or 'sha512')");
+  handler([ht](const std::string& s) {
+    *ht = parseHashType(s);
+    if (*ht == htUnknown) {
+      throw UsageError("unknown hash type '%1%'", s);
+    }
+  });
+  return *this;
+}
+
+Strings argvToStrings(int argc, char** argv) {
+  Strings args;
+  argc--;
+  argv++;
+  while ((argc--) != 0) {
+    args.push_back(*argv++);
+  }
+  return args;
+}
+
+std::string renderLabels(const Strings& labels) {
+  std::string res;
+  for (auto label : labels) {
+    for (auto& c : label) {
+      c = std::toupper(c);
+    }
+    res += " <" + label + ">";
+  }
+  return res;
+}
+
+void printTable(std::ostream& out, const Table2& table) {
+  size_t max = 0;
+  for (auto& row : table) {
+    max = std::max(max, row.first.size());
+  }
+  for (auto& row : table) {
+    out << "  " << row.first << std::string(max - row.first.size() + 2, ' ')
+        << row.second << "\n";
+  }
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/args.hh b/third_party/nix/src/libutil/args.hh
new file mode 100644
index 000000000000..bb1ef43912bb
--- /dev/null
+++ b/third_party/nix/src/libutil/args.hh
@@ -0,0 +1,221 @@
+#pragma once
+
+#include <iostream>
+#include <map>
+#include <memory>
+
+#include <absl/strings/numbers.h>
+
+#include "libutil/util.hh"
+
+namespace nix {
+
+MakeError(UsageError, Error);
+
+enum HashType : char;
+
+class Args {
+ public:
+  /* Parse the command line, throwing a UsageError if something goes
+     wrong. */
+  void parseCmdline(const Strings& cmdline);
+
+  virtual void printHelp(const std::string& programName, std::ostream& out);
+
+  virtual std::string description() { return ""; }
+
+ protected:
+  static const size_t ArityAny = std::numeric_limits<size_t>::max();
+
+  /* Flags. */
+  struct Flag {
+    typedef std::shared_ptr<Flag> ptr;
+    std::string longName;
+    char shortName = 0;
+    std::string description;
+    Strings labels;
+    size_t arity = 0;
+    std::function<void(std::vector<std::string>)> handler;
+    std::string category;
+  };
+
+  std::map<std::string, Flag::ptr> longFlags;
+  std::map<char, Flag::ptr> shortFlags;
+
+  virtual bool processFlag(Strings::iterator& pos, Strings::iterator end);
+
+  virtual void printFlags(std::ostream& out);
+
+  /* Positional arguments. */
+  struct ExpectedArg {
+    std::string label;
+    size_t arity;  // 0 = any
+    bool optional;
+    std::function<void(std::vector<std::string>)> handler;
+  };
+
+  std::list<ExpectedArg> expectedArgs;
+
+  virtual bool processArgs(const Strings& args, bool finish);
+
+  std::set<std::string> hiddenCategories;
+
+ public:
+  class FlagMaker {
+    Args& args;
+    Flag::ptr flag;
+    friend class Args;
+    explicit FlagMaker(Args& args)
+        : args(args), flag(std::make_shared<Flag>()){};
+
+   public:
+    ~FlagMaker();
+    FlagMaker& longName(const std::string& s) {
+      flag->longName = s;
+      return *this;
+    };
+    FlagMaker& shortName(char s) {
+      flag->shortName = s;
+      return *this;
+    };
+    FlagMaker& description(const std::string& s) {
+      flag->description = s;
+      return *this;
+    };
+    FlagMaker& label(const std::string& l) {
+      flag->arity = 1;
+      flag->labels = {l};
+      return *this;
+    };
+    FlagMaker& labels(const Strings& ls) {
+      flag->arity = ls.size();
+      flag->labels = ls;
+      return *this;
+    };
+    FlagMaker& arity(size_t arity) {
+      flag->arity = arity;
+      return *this;
+    };
+    FlagMaker& handler(std::function<void(std::vector<std::string>)> handler) {
+      flag->handler = handler;
+      return *this;
+    };
+    FlagMaker& handler(std::function<void()> handler) {
+      flag->handler = [handler](std::vector<std::string>) { handler(); };
+      return *this;
+    };
+    FlagMaker& handler(std::function<void(std::string)> handler) {
+      flag->arity = 1;
+      flag->handler = [handler](std::vector<std::string> ss) {
+        handler(std::move(ss[0]));
+      };
+      return *this;
+    };
+    FlagMaker& category(const std::string& s) {
+      flag->category = s;
+      return *this;
+    };
+
+    template <class T>
+    FlagMaker& dest(T* dest) {
+      flag->arity = 1;
+      flag->handler = [=](std::vector<std::string> ss) { *dest = ss[0]; };
+      return *this;
+    }
+
+    template <class T>
+    FlagMaker& set(T* dest, const T& val) {
+      flag->arity = 0;
+      flag->handler = [=](std::vector<std::string> ss) { *dest = val; };
+      return *this;
+    }
+
+    FlagMaker& mkHashTypeFlag(HashType* ht);
+  };
+
+  FlagMaker mkFlag();
+
+  /* Helper functions for constructing flags / positional
+     arguments. */
+
+  void mkFlag1(char shortName, const std::string& longName,
+               const std::string& label, const std::string& description,
+               std::function<void(std::string)> fun) {
+    mkFlag()
+        .shortName(shortName)
+        .longName(longName)
+        .labels({label})
+        .description(description)
+        .arity(1)
+        .handler([=](std::vector<std::string> ss) { fun(ss[0]); });
+  }
+
+  void mkFlag(char shortName, const std::string& name,
+              const std::string& description, bool* dest) {
+    mkFlag(shortName, name, description, dest, true);
+  }
+
+  template <class T>
+  void mkFlag(char shortName, const std::string& longName,
+              const std::string& description, T* dest, const T& value) {
+    mkFlag()
+        .shortName(shortName)
+        .longName(longName)
+        .description(description)
+        .handler([=](std::vector<std::string> ss) { *dest = value; });
+  }
+
+  template <class I>
+  void mkIntFlag(char shortName, const std::string& longName,
+                 const std::string& description, I* dest) {
+    mkFlag<I>(shortName, longName, description, [=](I n) { *dest = n; });
+  }
+
+  template <class I>
+  void mkFlag(char shortName, const std::string& longName,
+              const std::string& description, std::function<void(I)> fun) {
+    mkFlag()
+        .shortName(shortName)
+        .longName(longName)
+        .labels({"N"})
+        .description(description)
+        .arity(1)
+        .handler([=](std::vector<std::string> ss) {
+          I n;
+          if (!absl::SimpleAtoi(ss[0], &n)) {
+            throw UsageError("flag '--%s' requires a integer argument",
+                             longName);
+          }
+          fun(n);
+        });
+  }
+
+  /* Expect a string argument. */
+  void expectArg(const std::string& label, std::string* dest,
+                 bool optional = false) {
+    expectedArgs.push_back(
+        ExpectedArg{label, 1, optional,
+                    [=](std::vector<std::string> ss) { *dest = ss[0]; }});
+  }
+
+  /* Expect 0 or more arguments. */
+  void expectArgs(const std::string& label, std::vector<std::string>* dest) {
+    expectedArgs.push_back(ExpectedArg{
+        label, 0, false,
+        [=](std::vector<std::string> ss) { *dest = std::move(ss); }});
+  }
+
+  friend class MultiCommand;
+};
+
+Strings argvToStrings(int argc, char** argv);
+
+/* Helper function for rendering argument labels. */
+std::string renderLabels(const Strings& labels);
+
+/* Helper function for printing 2-column tables. */
+using Table2 = std::vector<std::pair<std::string, std::string> >;
+
+void printTable(std::ostream& out, const Table2& table);
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/compression.cc b/third_party/nix/src/libutil/compression.cc
new file mode 100644
index 000000000000..d0895ca5fda4
--- /dev/null
+++ b/third_party/nix/src/libutil/compression.cc
@@ -0,0 +1,400 @@
+#include "libutil/compression.hh"
+
+#include <cstdio>
+#include <cstring>
+#include <iostream>
+
+#include <brotli/decode.h>
+#include <brotli/encode.h>
+#include <bzlib.h>
+#include <glog/logging.h>
+#include <lzma.h>
+
+#include "libutil/finally.hh"
+#include "libutil/util.hh"
+
+namespace nix {
+
+// Don't feed brotli too much at once.
+struct ChunkedCompressionSink : CompressionSink {
+  uint8_t outbuf[32 * 1024];
+
+  void write(const unsigned char* data, size_t len) override {
+    const size_t CHUNK_SIZE = sizeof(outbuf) << 2;
+    while (len != 0u) {
+      size_t n = std::min(CHUNK_SIZE, len);
+      writeInternal(data, n);
+      data += n;
+      len -= n;
+    }
+  }
+
+  virtual void writeInternal(const unsigned char* data, size_t len) = 0;
+};
+
+struct NoneSink : CompressionSink {
+  Sink& nextSink;
+  explicit NoneSink(Sink& nextSink) : nextSink(nextSink) {}
+  void finish() override { flush(); }
+  void write(const unsigned char* data, size_t len) override {
+    nextSink(data, len);
+  }
+};
+
+struct XzDecompressionSink : CompressionSink {
+  Sink& nextSink;
+  uint8_t outbuf[BUFSIZ];
+  lzma_stream strm = LZMA_STREAM_INIT;
+  bool finished = false;
+
+  explicit XzDecompressionSink(Sink& nextSink) : nextSink(nextSink) {
+    lzma_ret ret = lzma_stream_decoder(&strm, UINT64_MAX, LZMA_CONCATENATED);
+    if (ret != LZMA_OK) {
+      throw CompressionError("unable to initialise lzma decoder");
+    }
+
+    strm.next_out = outbuf;
+    strm.avail_out = sizeof(outbuf);
+  }
+
+  ~XzDecompressionSink() override { lzma_end(&strm); }
+
+  void finish() override {
+    CompressionSink::flush();
+    write(nullptr, 0);
+  }
+
+  void write(const unsigned char* data, size_t len) override {
+    strm.next_in = data;
+    strm.avail_in = len;
+
+    while (!finished && ((data == nullptr) || (strm.avail_in != 0u))) {
+      checkInterrupt();
+
+      lzma_ret ret = lzma_code(&strm, data != nullptr ? LZMA_RUN : LZMA_FINISH);
+      if (ret != LZMA_OK && ret != LZMA_STREAM_END) {
+        throw CompressionError("error %d while decompressing xz file", ret);
+      }
+
+      finished = ret == LZMA_STREAM_END;
+
+      if (strm.avail_out < sizeof(outbuf) || strm.avail_in == 0) {
+        nextSink(outbuf, sizeof(outbuf) - strm.avail_out);
+        strm.next_out = outbuf;
+        strm.avail_out = sizeof(outbuf);
+      }
+    }
+  }
+};
+
+struct BzipDecompressionSink : ChunkedCompressionSink {
+  Sink& nextSink;
+  bz_stream strm;
+  bool finished = false;
+
+  explicit BzipDecompressionSink(Sink& nextSink) : nextSink(nextSink) {
+    memset(&strm, 0, sizeof(strm));
+    int ret = BZ2_bzDecompressInit(&strm, 0, 0);
+    if (ret != BZ_OK) {
+      throw CompressionError("unable to initialise bzip2 decoder");
+    }
+
+    strm.next_out = reinterpret_cast<char*>(outbuf);
+    strm.avail_out = sizeof(outbuf);
+  }
+
+  ~BzipDecompressionSink() override { BZ2_bzDecompressEnd(&strm); }
+
+  void finish() override {
+    flush();
+    write(nullptr, 0);
+  }
+
+  void writeInternal(const unsigned char* data, size_t len) override {
+    assert(len <= std::numeric_limits<decltype(strm.avail_in)>::max());
+
+    strm.next_in = (char*)data;
+    strm.avail_in = len;
+
+    while (strm.avail_in != 0u) {
+      checkInterrupt();
+
+      int ret = BZ2_bzDecompress(&strm);
+      if (ret != BZ_OK && ret != BZ_STREAM_END) {
+        throw CompressionError("error while decompressing bzip2 file");
+      }
+
+      finished = ret == BZ_STREAM_END;
+
+      if (strm.avail_out < sizeof(outbuf) || strm.avail_in == 0) {
+        nextSink(outbuf, sizeof(outbuf) - strm.avail_out);
+        strm.next_out = reinterpret_cast<char*>(outbuf);
+        strm.avail_out = sizeof(outbuf);
+      }
+    }
+  }
+};
+
+struct BrotliDecompressionSink : ChunkedCompressionSink {
+  Sink& nextSink;
+  BrotliDecoderState* state;
+  bool finished = false;
+
+  explicit BrotliDecompressionSink(Sink& nextSink) : nextSink(nextSink) {
+    state = BrotliDecoderCreateInstance(nullptr, nullptr, nullptr);
+    if (state == nullptr) {
+      throw CompressionError("unable to initialize brotli decoder");
+    }
+  }
+
+  ~BrotliDecompressionSink() override { BrotliDecoderDestroyInstance(state); }
+
+  void finish() override {
+    flush();
+    writeInternal(nullptr, 0);
+  }
+
+  void writeInternal(const unsigned char* data, size_t len) override {
+    const uint8_t* next_in = data;
+    size_t avail_in = len;
+    uint8_t* next_out = outbuf;
+    size_t avail_out = sizeof(outbuf);
+
+    while (!finished && ((data == nullptr) || (avail_in != 0u))) {
+      checkInterrupt();
+
+      if (BrotliDecoderDecompressStream(state, &avail_in, &next_in, &avail_out,
+                                        &next_out, nullptr) == 0u) {
+        throw CompressionError("error while decompressing brotli file");
+      }
+
+      if (avail_out < sizeof(outbuf) || avail_in == 0) {
+        nextSink(outbuf, sizeof(outbuf) - avail_out);
+        next_out = outbuf;
+        avail_out = sizeof(outbuf);
+      }
+
+      finished = (BrotliDecoderIsFinished(state) != 0);
+    }
+  }
+};
+
+ref<std::string> decompress(const std::string& method, const std::string& in) {
+  StringSink ssink;
+  auto sink = makeDecompressionSink(method, ssink);
+  (*sink)(in);
+  sink->finish();
+  return ssink.s;
+}
+
+ref<CompressionSink> makeDecompressionSink(const std::string& method,
+                                           Sink& nextSink) {
+  if (method == "none" || method.empty()) {
+    return make_ref<NoneSink>(nextSink);
+  }
+  if (method == "xz") {
+    return make_ref<XzDecompressionSink>(nextSink);
+  } else if (method == "bzip2") {
+    return make_ref<BzipDecompressionSink>(nextSink);
+  } else if (method == "br") {
+    return make_ref<BrotliDecompressionSink>(nextSink);
+  } else {
+    throw UnknownCompressionMethod("unknown compression method '%s'", method);
+  }
+}
+
+struct XzCompressionSink : CompressionSink {
+  Sink& nextSink;
+  uint8_t outbuf[BUFSIZ];
+  lzma_stream strm = LZMA_STREAM_INIT;
+  bool finished = false;
+
+  XzCompressionSink(Sink& nextSink, bool parallel) : nextSink(nextSink) {
+    lzma_ret ret;
+    bool done = false;
+
+    if (parallel) {
+      lzma_mt mt_options = {};
+      mt_options.flags = 0;
+      mt_options.timeout = 300;  // Using the same setting as the xz cmd line
+      mt_options.preset = LZMA_PRESET_DEFAULT;
+      mt_options.filters = NULL;
+      mt_options.check = LZMA_CHECK_CRC64;
+      mt_options.threads = lzma_cputhreads();
+      mt_options.block_size = 0;
+      if (mt_options.threads == 0) {
+        mt_options.threads = 1;
+      }
+      // FIXME: maybe use lzma_stream_encoder_mt_memusage() to control the
+      // number of threads.
+      ret = lzma_stream_encoder_mt(&strm, &mt_options);
+      done = true;
+    }
+
+    if (!done) {
+      ret = lzma_easy_encoder(&strm, 6, LZMA_CHECK_CRC64);
+    }
+
+    if (ret != LZMA_OK) {
+      throw CompressionError("unable to initialise lzma encoder");
+    }
+
+    // FIXME: apply the x86 BCJ filter?
+
+    strm.next_out = outbuf;
+    strm.avail_out = sizeof(outbuf);
+  }
+
+  ~XzCompressionSink() override { lzma_end(&strm); }
+
+  void finish() override {
+    CompressionSink::flush();
+    write(nullptr, 0);
+  }
+
+  void write(const unsigned char* data, size_t len) override {
+    strm.next_in = data;
+    strm.avail_in = len;
+
+    while (!finished && ((data == nullptr) || (strm.avail_in != 0u))) {
+      checkInterrupt();
+
+      lzma_ret ret = lzma_code(&strm, data != nullptr ? LZMA_RUN : LZMA_FINISH);
+      if (ret != LZMA_OK && ret != LZMA_STREAM_END) {
+        throw CompressionError("error %d while compressing xz file", ret);
+      }
+
+      finished = ret == LZMA_STREAM_END;
+
+      if (strm.avail_out < sizeof(outbuf) || strm.avail_in == 0) {
+        nextSink(outbuf, sizeof(outbuf) - strm.avail_out);
+        strm.next_out = outbuf;
+        strm.avail_out = sizeof(outbuf);
+      }
+    }
+  }
+};
+
+struct BzipCompressionSink : ChunkedCompressionSink {
+  Sink& nextSink;
+  bz_stream strm;
+  bool finished = false;
+
+  explicit BzipCompressionSink(Sink& nextSink) : nextSink(nextSink) {
+    memset(&strm, 0, sizeof(strm));
+    int ret = BZ2_bzCompressInit(&strm, 9, 0, 30);
+    if (ret != BZ_OK) {
+      throw CompressionError("unable to initialise bzip2 encoder");
+    }
+
+    strm.next_out = reinterpret_cast<char*>(outbuf);
+    strm.avail_out = sizeof(outbuf);
+  }
+
+  ~BzipCompressionSink() override { BZ2_bzCompressEnd(&strm); }
+
+  void finish() override {
+    flush();
+    writeInternal(nullptr, 0);
+  }
+
+  void writeInternal(const unsigned char* data, size_t len) override {
+    assert(len <= std::numeric_limits<decltype(strm.avail_in)>::max());
+
+    strm.next_in = (char*)data;
+    strm.avail_in = len;
+
+    while (!finished && ((data == nullptr) || (strm.avail_in != 0u))) {
+      checkInterrupt();
+
+      int ret = BZ2_bzCompress(&strm, data != nullptr ? BZ_RUN : BZ_FINISH);
+      if (ret != BZ_RUN_OK && ret != BZ_FINISH_OK && ret != BZ_STREAM_END) {
+        throw CompressionError("error %d while compressing bzip2 file", ret);
+      }
+
+      finished = ret == BZ_STREAM_END;
+
+      if (strm.avail_out < sizeof(outbuf) || strm.avail_in == 0) {
+        nextSink(outbuf, sizeof(outbuf) - strm.avail_out);
+        strm.next_out = reinterpret_cast<char*>(outbuf);
+        strm.avail_out = sizeof(outbuf);
+      }
+    }
+  }
+};
+
+struct BrotliCompressionSink : ChunkedCompressionSink {
+  Sink& nextSink;
+  uint8_t outbuf[BUFSIZ];
+  BrotliEncoderState* state;
+  bool finished = false;
+
+  explicit BrotliCompressionSink(Sink& nextSink) : nextSink(nextSink) {
+    state = BrotliEncoderCreateInstance(nullptr, nullptr, nullptr);
+    if (state == nullptr) {
+      throw CompressionError("unable to initialise brotli encoder");
+    }
+  }
+
+  ~BrotliCompressionSink() override { BrotliEncoderDestroyInstance(state); }
+
+  void finish() override {
+    flush();
+    writeInternal(nullptr, 0);
+  }
+
+  void writeInternal(const unsigned char* data, size_t len) override {
+    const uint8_t* next_in = data;
+    size_t avail_in = len;
+    uint8_t* next_out = outbuf;
+    size_t avail_out = sizeof(outbuf);
+
+    while (!finished && ((data == nullptr) || (avail_in != 0u))) {
+      checkInterrupt();
+
+      if (BrotliEncoderCompressStream(state,
+                                      data != nullptr ? BROTLI_OPERATION_PROCESS
+                                                      : BROTLI_OPERATION_FINISH,
+                                      &avail_in, &next_in, &avail_out,
+                                      &next_out, nullptr) == 0) {
+        throw CompressionError("error while compressing brotli compression");
+      }
+
+      if (avail_out < sizeof(outbuf) || avail_in == 0) {
+        nextSink(outbuf, sizeof(outbuf) - avail_out);
+        next_out = outbuf;
+        avail_out = sizeof(outbuf);
+      }
+
+      finished = (BrotliEncoderIsFinished(state) != 0);
+    }
+  }
+};
+
+ref<CompressionSink> makeCompressionSink(const std::string& method,
+                                         Sink& nextSink, const bool parallel) {
+  if (method == "none") {
+    return make_ref<NoneSink>(nextSink);
+  }
+  if (method == "xz") {
+    return make_ref<XzCompressionSink>(nextSink, parallel);
+  } else if (method == "bzip2") {
+    return make_ref<BzipCompressionSink>(nextSink);
+  } else if (method == "br") {
+    return make_ref<BrotliCompressionSink>(nextSink);
+  } else {
+    throw UnknownCompressionMethod(format("unknown compression method '%s'") %
+                                   method);
+  }
+}
+
+ref<std::string> compress(const std::string& method, const std::string& in,
+                          const bool parallel) {
+  StringSink ssink;
+  auto sink = makeCompressionSink(method, ssink, parallel);
+  (*sink)(in);
+  sink->finish();
+  return ssink.s;
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/compression.hh b/third_party/nix/src/libutil/compression.hh
new file mode 100644
index 000000000000..8ec340ab7447
--- /dev/null
+++ b/third_party/nix/src/libutil/compression.hh
@@ -0,0 +1,31 @@
+#pragma once
+
+#include <string>
+
+#include "libutil/ref.hh"
+#include "libutil/serialise.hh"
+#include "libutil/types.hh"
+
+namespace nix {
+
+struct CompressionSink : BufferedSink {
+  virtual void finish() = 0;
+};
+
+ref<std::string> decompress(const std::string& method, const std::string& in);
+
+ref<CompressionSink> makeDecompressionSink(const std::string& method,
+                                           Sink& nextSink);
+
+ref<std::string> compress(const std::string& method, const std::string& in,
+                          const bool parallel = false);
+
+ref<CompressionSink> makeCompressionSink(const std::string& method,
+                                         Sink& nextSink,
+                                         const bool parallel = false);
+
+MakeError(UnknownCompressionMethod, Error);
+
+MakeError(CompressionError, Error);
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/config.cc b/third_party/nix/src/libutil/config.cc
new file mode 100644
index 000000000000..7c6e7af48752
--- /dev/null
+++ b/third_party/nix/src/libutil/config.cc
@@ -0,0 +1,370 @@
+#include "libutil/config.hh"
+
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <absl/strings/numbers.h>
+#include <absl/strings/str_split.h>
+#include <absl/strings/string_view.h>
+#include <glog/logging.h>
+
+#include "libutil/args.hh"
+#include "libutil/json.hh"
+
+namespace nix {
+
+bool Config::set(const std::string& name, const std::string& value) {
+  auto i = _settings.find(name);
+  if (i == _settings.end()) {
+    return false;
+  }
+  i->second.setting->set(value);
+  i->second.setting->overriden = true;
+  return true;
+}
+
+void Config::addSetting(AbstractSetting* setting) {
+  _settings.emplace(setting->name, Config::SettingData(false, setting));
+  for (auto& alias : setting->aliases) {
+    _settings.emplace(alias, Config::SettingData(true, setting));
+  }
+
+  bool set = false;
+
+  auto i = unknownSettings.find(setting->name);
+  if (i != unknownSettings.end()) {
+    setting->set(i->second);
+    setting->overriden = true;
+    unknownSettings.erase(i);
+    set = true;
+  }
+
+  for (auto& alias : setting->aliases) {
+    auto i = unknownSettings.find(alias);
+    if (i != unknownSettings.end()) {
+      if (set) {
+        LOG(WARNING) << "setting '" << alias
+                     << "' is set, but it's an alias of '" << setting->name
+                     << "', which is also set";
+      }
+
+      else {
+        setting->set(i->second);
+        setting->overriden = true;
+        unknownSettings.erase(i);
+        set = true;
+      }
+    }
+  }
+}
+
+void AbstractConfig::warnUnknownSettings() {
+  for (auto& s : unknownSettings) {
+    LOG(WARNING) << "unknown setting: " << s.first;
+  }
+}
+
+void AbstractConfig::reapplyUnknownSettings() {
+  auto unknownSettings2 = std::move(unknownSettings);
+  for (auto& s : unknownSettings2) {
+    set(s.first, s.second);
+  }
+}
+
+void Config::getSettings(std::map<std::string, SettingInfo>& res,
+                         bool overridenOnly) {
+  for (auto& opt : _settings) {
+    if (!opt.second.isAlias &&
+        (!overridenOnly || opt.second.setting->overriden)) {
+      res.emplace(opt.first, SettingInfo{opt.second.setting->to_string(),
+                                         opt.second.setting->description});
+    }
+  }
+}
+
+void AbstractConfig::applyConfigFile(const Path& path) {
+  try {
+    std::string contents = readFile(path);
+
+    unsigned int pos = 0;
+
+    while (pos < contents.size()) {
+      std::string line;
+      while (pos < contents.size() && contents[pos] != '\n') {
+        line += contents[pos++];
+      }
+      pos++;
+
+      std::string::size_type hash = line.find('#');
+      if (hash != std::string::npos) {
+        line = std::string(line, 0, hash);
+      }
+
+      // TODO(tazjin): absl::string_view after path functions are fixed.
+      std::vector<std::string> tokens = absl::StrSplit(
+          line, absl::ByAnyChar(" \t\n\r"), absl::SkipWhitespace());
+      if (tokens.empty()) {
+        continue;
+      }
+
+      if (tokens.size() < 2) {
+        throw UsageError("illegal configuration line '%1%' in '%2%'", line,
+                         path);
+      }
+
+      auto include = false;
+      auto ignoreMissing = false;
+      if (tokens[0] == "include") {
+        include = true;
+      } else if (tokens[0] == "!include") {
+        include = true;
+        ignoreMissing = true;
+      }
+
+      if (include) {
+        if (tokens.size() != 2) {
+          throw UsageError("illegal configuration line '%1%' in '%2%'", line,
+                           path);
+        }
+        auto p = absPath(tokens[1], dirOf(path));
+        if (pathExists(p)) {
+          applyConfigFile(p);
+        } else if (!ignoreMissing) {
+          throw Error("file '%1%' included from '%2%' not found", p, path);
+        }
+        continue;
+      }
+
+      if (tokens[1] != "=") {
+        throw UsageError("illegal configuration line '%1%' in '%2%'", line,
+                         path);
+      }
+
+      std::string name = tokens[0];
+
+      auto i = tokens.begin();
+      advance(i, 2);
+
+      set(name,
+          concatStringsSep(" ", Strings(i, tokens.end())));  // FIXME: slow
+    };
+  } catch (SysError&) {
+  }
+}
+
+void Config::resetOverriden() {
+  for (auto& s : _settings) {
+    s.second.setting->overriden = false;
+  }
+}
+
+void Config::toJSON(JSONObject& out) {
+  for (auto& s : _settings) {
+    if (!s.second.isAlias) {
+      JSONObject out2(out.object(s.first));
+      out2.attr("description", s.second.setting->description);
+      JSONPlaceholder out3(out2.placeholder("value"));
+      s.second.setting->toJSON(out3);
+    }
+  }
+}
+
+void Config::convertToArgs(Args& args, const std::string& category) {
+  for (auto& s : _settings) {
+    if (!s.second.isAlias) {
+      s.second.setting->convertToArg(args, category);
+    }
+  }
+}
+
+AbstractSetting::AbstractSetting(std::string name, std::string description,
+                                 std::set<std::string> aliases)
+    : name(std::move(name)),
+      description(std::move(description)),
+      aliases(std::move(aliases)) {}
+
+void AbstractSetting::toJSON(JSONPlaceholder& out) { out.write(to_string()); }
+
+void AbstractSetting::convertToArg(Args& args, const std::string& category) {}
+
+template <typename T>
+void BaseSetting<T>::toJSON(JSONPlaceholder& out) {
+  out.write(value);
+}
+
+template <typename T>
+void BaseSetting<T>::convertToArg(Args& args, const std::string& category) {
+  args.mkFlag()
+      .longName(name)
+      .description(description)
+      .arity(1)
+      .handler([=](std::vector<std::string> ss) {
+        overriden = true;
+        set(ss[0]);
+      })
+      .category(category);
+}
+
+template <>
+void BaseSetting<std::string>::set(const std::string& str) {
+  value = str;
+}
+
+template <>
+std::string BaseSetting<std::string>::to_string() {
+  return value;
+}
+
+template <typename T>
+void BaseSetting<T>::set(const std::string& str) {
+  static_assert(std::is_integral<T>::value, "Integer required.");
+  if (!absl::SimpleAtoi(str, &value)) {
+    throw UsageError("setting '%s' has invalid value '%s'", name, str);
+  }
+}
+
+template <typename T>
+std::string BaseSetting<T>::to_string() {
+  static_assert(std::is_integral<T>::value, "Integer required.");
+  return std::to_string(value);
+}
+
+template <>
+void BaseSetting<bool>::set(const std::string& str) {
+  if (str == "true" || str == "yes" || str == "1") {
+    value = true;
+  } else if (str == "false" || str == "no" || str == "0") {
+    value = false;
+  } else {
+    throw UsageError("Boolean setting '%s' has invalid value '%s'", name, str);
+  }
+}
+
+template <>
+std::string BaseSetting<bool>::to_string() {
+  return value ? "true" : "false";
+}
+
+template <>
+void BaseSetting<bool>::convertToArg(Args& args, const std::string& category) {
+  args.mkFlag()
+      .longName(name)
+      .description(description)
+      .handler([=](const std::vector<std::string>& ss) { override(true); })
+      .category(category);
+  args.mkFlag()
+      .longName("no-" + name)
+      .description(description)
+      .handler([=](const std::vector<std::string>& ss) { override(false); })
+      .category(category);
+}
+
+template <>
+void BaseSetting<Strings>::set(const std::string& str) {
+  value = absl::StrSplit(str, absl::ByAnyChar(" \t\n\r"), absl::SkipEmpty());
+}
+
+template <>
+std::string BaseSetting<Strings>::to_string() {
+  return concatStringsSep(" ", value);
+}
+
+template <>
+void BaseSetting<Strings>::toJSON(JSONPlaceholder& out) {
+  JSONList list(out.list());
+  for (auto& s : value) {
+    list.elem(s);
+  }
+}
+
+template <>
+void BaseSetting<StringSet>::set(const std::string& str) {
+  value = absl::StrSplit(str, absl::ByAnyChar(" \t\n\r"), absl::SkipEmpty());
+}
+
+template <>
+std::string BaseSetting<StringSet>::to_string() {
+  return concatStringsSep(" ", value);
+}
+
+template <>
+void BaseSetting<StringSet>::toJSON(JSONPlaceholder& out) {
+  JSONList list(out.list());
+  for (auto& s : value) {
+    list.elem(s);
+  }
+}
+
+template class BaseSetting<int>;
+template class BaseSetting<unsigned int>;
+template class BaseSetting<long>;
+template class BaseSetting<unsigned long>;
+template class BaseSetting<long long>;
+template class BaseSetting<unsigned long long>;
+template class BaseSetting<bool>;
+template class BaseSetting<std::string>;
+template class BaseSetting<Strings>;
+template class BaseSetting<StringSet>;
+
+void PathSetting::set(const std::string& str) {
+  if (str.empty()) {
+    if (allowEmpty) {
+      value = "";
+    } else {
+      throw UsageError("setting '%s' cannot be empty", name);
+    }
+  } else {
+    value = canonPath(str);
+  }
+}
+
+bool GlobalConfig::set(const std::string& name, const std::string& value) {
+  for (auto& config : *configRegistrations) {
+    if (config->set(name, value)) {
+      return true;
+    }
+  }
+
+  unknownSettings.emplace(name, value);
+
+  return false;
+}
+
+void GlobalConfig::getSettings(std::map<std::string, SettingInfo>& res,
+                               bool overridenOnly) {
+  for (auto& config : *configRegistrations) {
+    config->getSettings(res, overridenOnly);
+  }
+}
+
+void GlobalConfig::resetOverriden() {
+  for (auto& config : *configRegistrations) {
+    config->resetOverriden();
+  }
+}
+
+void GlobalConfig::toJSON(JSONObject& out) {
+  for (auto& config : *configRegistrations) {
+    config->toJSON(out);
+  }
+}
+
+void GlobalConfig::convertToArgs(Args& args, const std::string& category) {
+  for (auto& config : *configRegistrations) {
+    config->convertToArgs(args, category);
+  }
+}
+
+GlobalConfig globalConfig;
+
+GlobalConfig::ConfigRegistrations* GlobalConfig::configRegistrations;
+
+GlobalConfig::Register::Register(Config* config) {
+  if (configRegistrations == nullptr) {
+    configRegistrations = new ConfigRegistrations;
+  }
+  configRegistrations->emplace_back(config);
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/config.hh b/third_party/nix/src/libutil/config.hh
new file mode 100644
index 000000000000..81b1c80e0e97
--- /dev/null
+++ b/third_party/nix/src/libutil/config.hh
@@ -0,0 +1,228 @@
+#include <map>
+#include <set>
+
+#include "libutil/types.hh"
+
+#pragma once
+
+namespace nix {
+
+class Args;
+class AbstractSetting;
+class JSONPlaceholder;
+class JSONObject;
+
+class AbstractConfig {
+ protected:
+  StringMap unknownSettings;
+
+  explicit AbstractConfig(const StringMap& initials = {})
+      : unknownSettings(initials) {}
+
+ public:
+  virtual bool set(const std::string& name, const std::string& value) = 0;
+
+  struct SettingInfo {
+    std::string value;
+    std::string description;
+  };
+
+  virtual void getSettings(std::map<std::string, SettingInfo>& res,
+                           bool overridenOnly = false) = 0;
+
+  void applyConfigFile(const Path& path);
+
+  virtual void resetOverriden() = 0;
+
+  virtual void toJSON(JSONObject& out) = 0;
+
+  virtual void convertToArgs(Args& args, const std::string& category) = 0;
+
+  void warnUnknownSettings();
+
+  void reapplyUnknownSettings();
+};
+
+/* A class to simplify providing configuration settings. The typical
+   use is to inherit Config and add Setting<T> members:
+
+   class MyClass : private Config
+   {
+     Setting<int> foo{this, 123, "foo", "the number of foos to use"};
+     Setting<std::string> bar{this, "blabla", "bar", "the name of the bar"};
+
+     MyClass() : Config(readConfigFile("/etc/my-app.conf"))
+     {
+       std::cout << foo << "\n"; // will print 123 unless overriden
+     }
+   };
+*/
+
+class Config : public AbstractConfig {
+  friend class AbstractSetting;
+
+ public:
+  struct SettingData {
+    bool isAlias;
+    AbstractSetting* setting;
+    SettingData(bool isAlias, AbstractSetting* setting)
+        : isAlias(isAlias), setting(setting) {}
+  };
+
+  typedef std::map<std::string, SettingData> Settings;
+
+ private:
+  Settings _settings;
+
+ public:
+  explicit Config(const StringMap& initials = {}) : AbstractConfig(initials) {}
+
+  bool set(const std::string& name, const std::string& value) override;
+
+  void addSetting(AbstractSetting* setting);
+
+  void getSettings(std::map<std::string, SettingInfo>& res,
+                   bool overridenOnly = false) override;
+
+  void resetOverriden() override;
+
+  void toJSON(JSONObject& out) override;
+
+  void convertToArgs(Args& args, const std::string& category) override;
+};
+
+class AbstractSetting {
+  friend class Config;
+
+ public:
+  const std::string name;
+  const std::string description;
+  const std::set<std::string> aliases;
+
+  int created = 123;
+
+  bool overriden = false;
+
+ protected:
+  AbstractSetting(std::string name, std::string description,
+                  std::set<std::string> aliases);
+
+  virtual ~AbstractSetting() {
+    // Check against a gcc miscompilation causing our constructor
+    // not to run (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80431).
+    assert(created == 123);
+  }
+
+  virtual void set(const std::string& value) = 0;
+
+  virtual std::string to_string() = 0;
+
+  virtual void toJSON(JSONPlaceholder& out);
+
+  virtual void convertToArg(Args& args, const std::string& category);
+
+  bool isOverriden() { return overriden; }
+};
+
+/* A setting of type T. */
+template <typename T>
+class BaseSetting : public AbstractSetting {
+ protected:
+  T value;
+
+ public:
+  BaseSetting(const T& def, const std::string& name,
+              const std::string& description,
+              const std::set<std::string>& aliases = {})
+      : AbstractSetting(name, description, aliases), value(def) {}
+
+  operator const T&() const { return value; }
+  operator T&() { return value; }
+  const T& get() const { return value; }
+  bool operator==(const T& v2) const { return value == v2; }
+  bool operator!=(const T& v2) const { return value != v2; }
+  void operator=(const T& v) { assign(v); }
+  virtual void assign(const T& v) { value = v; }
+
+  void set(const std::string& str) override;
+
+  virtual void override(const T& v) {
+    overriden = true;
+    value = v;
+  }
+
+  std::string to_string() override;
+
+  void convertToArg(Args& args, const std::string& category) override;
+
+  void toJSON(JSONPlaceholder& out) override;
+};
+
+template <typename T>
+std::ostream& operator<<(std::ostream& str, const BaseSetting<T>& opt) {
+  str << (const T&)opt;
+  return str;
+}
+
+template <typename T>
+bool operator==(const T& v1, const BaseSetting<T>& v2) {
+  return v1 == (const T&)v2;
+}
+
+template <typename T>
+class Setting : public BaseSetting<T> {
+ public:
+  Setting(Config* options, const T& def, const std::string& name,
+          const std::string& description,
+          const std::set<std::string>& aliases = {})
+      : BaseSetting<T>(def, name, description, aliases) {
+    options->addSetting(this);
+  }
+
+  void operator=(const T& v) { this->assign(v); }
+};
+
+/* A special setting for Paths. These are automatically canonicalised
+   (e.g. "/foo//bar/" becomes "/foo/bar"). */
+class PathSetting : public BaseSetting<Path> {
+  bool allowEmpty;
+
+ public:
+  PathSetting(Config* options, bool allowEmpty, const Path& def,
+              const std::string& name, const std::string& description,
+              const std::set<std::string>& aliases = {})
+      : BaseSetting<Path>(def, name, description, aliases),
+        allowEmpty(allowEmpty) {
+    options->addSetting(this);
+  }
+
+  void set(const std::string& str) override;
+
+  Path operator+(const char* p) const { return value + p; }
+
+  void operator=(const Path& v) { this->assign(v); }
+};
+
+struct GlobalConfig : public AbstractConfig {
+  using ConfigRegistrations = std::vector<Config*>;
+  static ConfigRegistrations* configRegistrations;
+
+  bool set(const std::string& name, const std::string& value) override;
+
+  void getSettings(std::map<std::string, SettingInfo>& res,
+                   bool overridenOnly = false) override;
+
+  void resetOverriden() override;
+
+  void toJSON(JSONObject& out) override;
+
+  void convertToArgs(Args& args, const std::string& category) override;
+
+  struct Register {
+    explicit Register(Config* config);
+  };
+};
+
+extern GlobalConfig globalConfig;
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/finally.hh b/third_party/nix/src/libutil/finally.hh
new file mode 100644
index 000000000000..2ead8661a6e7
--- /dev/null
+++ b/third_party/nix/src/libutil/finally.hh
@@ -0,0 +1,13 @@
+#pragma once
+
+#include <functional>
+
+/* A trivial class to run a function at the end of a scope. */
+class Finally {
+ private:
+  std::function<void()> fun;
+
+ public:
+  explicit Finally(std::function<void()> fun) : fun(fun) {}
+  ~Finally() { fun(); }
+};
diff --git a/third_party/nix/src/libutil/hash.cc b/third_party/nix/src/libutil/hash.cc
new file mode 100644
index 000000000000..ba61254392e0
--- /dev/null
+++ b/third_party/nix/src/libutil/hash.cc
@@ -0,0 +1,484 @@
+#include "libutil/hash.hh"
+
+#include <cstring>
+#include <iostream>
+
+#include <absl/strings/escaping.h>
+#include <absl/strings/str_format.h>
+#include <fcntl.h>
+#include <glog/logging.h>
+#include <openssl/md5.h>
+#include <openssl/sha.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include "libutil/archive.hh"
+#include "libutil/istringstream_nocopy.hh"
+#include "libutil/util.hh"
+
+namespace nix {
+
+std::optional<HashType> hash_type_from(nix::proto::HashType hash_type) {
+  switch (hash_type) {
+    case nix::proto::HashType::UNKNOWN:
+      return HashType::htUnknown;
+    case nix::proto::HashType::MD5:
+      return HashType::htMD5;
+    case nix::proto::HashType::SHA1:
+      return HashType::htSHA1;
+    case nix::proto::HashType::SHA256:
+      return HashType::htSHA256;
+    case nix::proto::HashType::SHA512:
+      return HashType::htSHA512;
+    default:
+      return {};
+  }
+}
+
+nix::proto::HashType HashTypeToProto(HashType hash_type) {
+  switch (hash_type) {
+    case HashType::htMD5:
+      return nix::proto::HashType::MD5;
+    case HashType::htSHA1:
+      return nix::proto::HashType::SHA1;
+    case HashType::htSHA256:
+      return nix::proto::HashType::SHA256;
+    case HashType::htSHA512:
+      return nix::proto::HashType::SHA512;
+    default:
+      return nix::proto::HashType::UNKNOWN;
+  }
+}
+
+void Hash::init() {
+  if (type == htMD5) {
+    hashSize = md5HashSize;
+  } else if (type == htSHA1) {
+    hashSize = sha1HashSize;
+  } else if (type == htSHA256) {
+    hashSize = sha256HashSize;
+  } else if (type == htSHA512) {
+    hashSize = sha512HashSize;
+  } else {
+    abort();
+  }
+  assert(hashSize <= maxHashSize);
+  memset(hash, 0, maxHashSize);
+}
+
+bool Hash::operator==(const Hash& h2) const {
+  if (hashSize != h2.hashSize) {
+    return false;
+  }
+  for (unsigned int i = 0; i < hashSize; i++) {
+    if (hash[i] != h2.hash[i]) {
+      return false;
+    }
+  }
+  return true;
+}
+
+bool Hash::operator!=(const Hash& h2) const { return !(*this == h2); }
+
+bool Hash::operator<(const Hash& h) const {
+  if (hashSize < h.hashSize) {
+    return true;
+  }
+  if (hashSize > h.hashSize) {
+    return false;
+  }
+  for (unsigned int i = 0; i < hashSize; i++) {
+    if (hash[i] < h.hash[i]) {
+      return true;
+    }
+    if (hash[i] > h.hash[i]) {
+      return false;
+    }
+  }
+  return false;
+}
+
+const std::string base16Chars = "0123456789abcdef";
+
+static std::string printHash16(const Hash& hash) {
+  char buf[hash.hashSize * 2];
+  for (unsigned int i = 0; i < hash.hashSize; i++) {
+    buf[i * 2] = base16Chars[hash.hash[i] >> 4];
+    buf[i * 2 + 1] = base16Chars[hash.hash[i] & 0x0f];
+  }
+  return std::string(buf, hash.hashSize * 2);
+}
+
+bool Hash::IsValidBase16(absl::string_view s) {
+  for (char c : s) {
+    if ('0' <= c && c <= '9') {
+      continue;
+    }
+    if ('a' <= c && c <= 'f') {
+      continue;
+    }
+    if ('A' <= c && c <= 'F') {
+      continue;
+    }
+    return false;
+  }
+  return true;
+}
+
+constexpr signed char kUnBase32[] = {
+    -1, -1, -1, -1, -1, -1, -1, -1, /* unprintables */
+    -1, -1, -1, -1, -1, -1, -1, -1, /* unprintables */
+    -1, -1, -1, -1, -1, -1, -1, -1, /* unprintables */
+    -1, -1, -1, -1, -1, -1, -1, -1, /* unprintables */
+    -1, -1, -1, -1, -1, -1, -1, -1, /* SP..' */
+    -1, -1, -1, -1, -1, -1, -1, -1, /* (../ */
+    0,  1,  2,  3,  4,  5,  6,  7,  /* 0..7 */
+    8,  9,  -1, -1, -1, -1, -1, -1, /* 8..? */
+    -1, -1, -1, -1, -1, -1, -1, -1, /* @..G */
+    -1, -1, -1, -1, -1, -1, -1, -1, /* H..O */
+    -1, -1, -1, -1, -1, -1, -1, -1, /* P..W */
+    -1, -1, -1, -1, -1, -1, -1, -1, /* X.._ */
+    -1, 10, 11, 12, 13, -1, 14, 15, /* `..g */
+    16, 17, 18, 19, 20, 21, 22, -1, /* h..o */
+    23, 24, 25, 26, -1, -1, 27, 28, /* p..w */
+    29, 30, 31, -1, -1, -1, -1, -1, /* x..DEL */
+
+    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
+    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
+    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
+    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
+    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
+    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
+    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
+    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
+};
+
+bool Hash::IsValidBase32(absl::string_view s) {
+  static_assert(sizeof(kUnBase32) == 256);
+
+  for (char c : s) {
+    if (kUnBase32[static_cast<unsigned char>(c)] == -1) {
+      return false;
+    }
+  }
+  return true;
+}
+
+std::string Hash::ToStorePathHash() const {
+  return compressHash(*this, kStorePathHashSize).to_string(Base32, false);
+}
+
+static std::string printHash32(const Hash& hash) {
+  assert(hash.hashSize);
+  size_t len = hash.base32Len();
+  assert(len);
+
+  std::string s;
+  s.reserve(len);
+
+  for (int n = static_cast<int>(len) - 1; n >= 0; n--) {
+    unsigned int b = n * 5;
+    unsigned int i = b / 8;
+    unsigned int j = b % 8;
+    unsigned char c =
+        (hash.hash[i] >> j) |
+        (i >= hash.hashSize - 1 ? 0 : hash.hash[i + 1] << (8 - j));
+    s.push_back(base32Chars[c & 0x1f]);
+  }
+
+  return s;
+}
+
+std::string printHash16or32(const Hash& hash) {
+  return hash.to_string(hash.type == htMD5 ? Base16 : Base32, false);
+}
+
+std::string Hash::to_string(Base base, bool includeType) const {
+  std::string s;
+  if (base == SRI || includeType) {
+    s += printHashType(type);
+    s += base == SRI ? '-' : ':';
+  }
+  switch (base) {
+    case Base16:
+      s += printHash16(*this);
+      break;
+    case Base32:
+      s += printHash32(*this);
+      break;
+    case Base64:
+    case SRI:
+      std::string b64;
+      absl::Base64Escape(
+          std::string(reinterpret_cast<const char*>(hash), hashSize), &b64);
+      s += b64;
+      break;
+  }
+  return s;
+}
+
+Hash::Hash(std::string_view s, HashType type) : type(type) {
+  absl::StatusOr<Hash> result = deserialize(s, type);
+  *this = unwrap_throw(result);
+}
+
+// TODO(riking): change ht to an optional
+absl::StatusOr<Hash> Hash::deserialize(std::string_view s, HashType type) {
+  size_t pos = 0;
+  bool isSRI = false;
+
+  auto sep = s.find(':');
+  if (sep == std::string::npos) {
+    sep = s.find('-');
+    if (sep != std::string::npos) {
+      isSRI = true;
+    } else if (type == htUnknown) {
+      return absl::InvalidArgumentError(
+          absl::StrCat("hash string '", s, " does not include a type"));
+    }
+  }
+
+  HashType parsedType = type;
+  if (sep != std::string::npos) {
+    std::string hts = std::string(s, 0, sep);
+    parsedType = parseHashType(hts);
+    if (type != htUnknown && parsedType != type) {
+      return absl::InvalidArgumentError(
+          absl::StrCat("hash '", s, "' should have type '", printHashType(type),
+                       "', found '", printHashType(parsedType), "'"));
+    }
+    pos = sep + 1;
+  }
+
+  Hash dest(parsedType);
+
+  size_t size = s.size() - pos;
+  absl::string_view sv(s.data() + pos, size);
+
+  if (!isSRI && size == dest.base16Len()) {
+    std::string bytes;
+    if (!IsValidBase16(sv)) {
+      return absl::InvalidArgumentError(
+          absl::StrCat("invalid base-16 hash: bad character in '", s, "'"));
+    }
+    bytes = absl::HexStringToBytes(sv);
+    if (bytes.size() != dest.hashSize) {
+      return absl::InvalidArgumentError(
+          absl::StrCat("hash '", s, "' has wrong length for base16 ",
+                       printHashType(dest.type)));
+    }
+    memcpy(dest.hash, bytes.data(), dest.hashSize);
+  }
+
+  else if (!isSRI && size == dest.base32Len()) {
+    for (unsigned int n = 0; n < size; ++n) {
+      char c = sv[size - n - 1];
+      // range: -1, 0..31
+      signed char digit = kUnBase32[static_cast<unsigned char>(c)];
+      if (digit < 0) {
+        return absl::InvalidArgumentError(
+            absl::StrCat("invalid base-32 hash: bad character ",
+                         absl::CEscape(absl::string_view(&c, 1))));
+      }
+      unsigned int b = n * 5;
+      unsigned int i = b / 8;
+      unsigned int j = b % 8;
+      dest.hash[i] |= digit << j;
+
+      if (i < dest.hashSize - 1) {
+        dest.hash[i + 1] |= digit >> (8 - j);
+      } else {
+        if ((digit >> (8 - j)) != 0) {
+          return absl::InvalidArgumentError(
+              absl::StrCat("invalid base-32 hash '", s, "'"));
+        }
+      }
+    }
+  }
+
+  else if (isSRI || size == dest.base64Len()) {
+    std::string decoded;
+    if (!absl::Base64Unescape(sv, &decoded)) {
+      return absl::InvalidArgumentError("invalid base-64 hash");
+    }
+    if (decoded.size() != dest.hashSize) {
+      return absl::InvalidArgumentError(
+          absl::StrCat("hash '", s, "' has wrong length for base64 ",
+                       printHashType(dest.type)));
+    }
+    memcpy(dest.hash, decoded.data(), dest.hashSize);
+  }
+
+  else {
+    return absl::InvalidArgumentError(absl::StrCat(
+        "hash '", s, "' has wrong length for ", printHashType(dest.type)));
+  }
+
+  return dest;
+}
+
+Hash Hash::unwrap_throw(absl::StatusOr<Hash> hash) {
+  if (hash.ok()) {
+    return *hash;
+  } else {
+    throw BadHash(hash.status().message());
+  }
+}
+
+namespace hash {
+
+union Ctx {
+  MD5_CTX md5;
+  SHA_CTX sha1;
+  SHA256_CTX sha256;
+  SHA512_CTX sha512;
+};
+
+static void start(HashType ht, Ctx& ctx) {
+  if (ht == htMD5) {
+    MD5_Init(&ctx.md5);
+  } else if (ht == htSHA1) {
+    SHA1_Init(&ctx.sha1);
+  } else if (ht == htSHA256) {
+    SHA256_Init(&ctx.sha256);
+  } else if (ht == htSHA512) {
+    SHA512_Init(&ctx.sha512);
+  }
+}
+
+static void update(HashType ht, Ctx& ctx, const unsigned char* bytes,
+                   size_t len) {
+  if (ht == htMD5) {
+    MD5_Update(&ctx.md5, bytes, len);
+  } else if (ht == htSHA1) {
+    SHA1_Update(&ctx.sha1, bytes, len);
+  } else if (ht == htSHA256) {
+    SHA256_Update(&ctx.sha256, bytes, len);
+  } else if (ht == htSHA512) {
+    SHA512_Update(&ctx.sha512, bytes, len);
+  }
+}
+
+static void finish(HashType ht, Ctx& ctx, unsigned char* hash) {
+  if (ht == htMD5) {
+    MD5_Final(hash, &ctx.md5);
+  } else if (ht == htSHA1) {
+    SHA1_Final(hash, &ctx.sha1);
+  } else if (ht == htSHA256) {
+    SHA256_Final(hash, &ctx.sha256);
+  } else if (ht == htSHA512) {
+    SHA512_Final(hash, &ctx.sha512);
+  }
+}
+
+}  // namespace hash
+
+Hash hashString(HashType ht, const std::string& s) {
+  hash::Ctx ctx{};
+  Hash hash(ht);
+  start(ht, ctx);
+  update(ht, ctx, reinterpret_cast<const unsigned char*>(s.data()), s.length());
+  finish(ht, ctx, hash.hash);
+  return hash;
+}
+
+Hash hashFile(HashType ht, const Path& path) {
+  hash::Ctx ctx{};
+  Hash hash(ht);
+  start(ht, ctx);
+
+  AutoCloseFD fd(open(path.c_str(), O_RDONLY | O_CLOEXEC));
+  if (!fd) {
+    throw SysError(format("opening file '%1%'") % path);
+  }
+
+  std::vector<unsigned char> buf(8192);
+  ssize_t n;
+  while ((n = read(fd.get(), buf.data(), buf.size())) != 0) {
+    checkInterrupt();
+    if (n == -1) {
+      throw SysError(format("reading file '%1%'") % path);
+    }
+    update(ht, ctx, buf.data(), n);
+  }
+
+  finish(ht, ctx, hash.hash);
+  return hash;
+}
+
+HashSink::HashSink(HashType ht)
+    : ht(ht), ctx(std::make_unique<hash::Ctx>()), bytes(0) {
+  start(ht, *ctx);
+}
+
+HashSink::~HashSink() { bufPos = 0; }
+
+void HashSink::write(const unsigned char* data, size_t len) {
+  bytes += len;
+  nix::hash::update(ht, *ctx, data, len);
+}
+
+HashResult HashSink::finish() {
+  flush();
+  Hash hash(ht);
+  nix::hash::finish(ht, *ctx, hash.hash);
+  return HashResult(hash, bytes);
+}
+
+HashResult HashSink::currentHash() {
+  flush();
+  nix::hash::Ctx ctx2 = *ctx;
+  Hash hash(ht);
+  nix::hash::finish(ht, ctx2, hash.hash);
+  return HashResult(hash, bytes);
+}
+
+HashResult hashPath(HashType ht, const Path& path, PathFilter& filter) {
+  HashSink sink(ht);
+  dumpPath(path, sink, filter);
+  return sink.finish();
+}
+
+Hash compressHash(const Hash& hash, unsigned int newSize) {
+  Hash h;
+  h.hashSize = newSize;
+  for (unsigned int i = 0; i < hash.hashSize; ++i) {
+    h.hash[i % newSize] ^= hash.hash[i];
+  }
+  return h;
+}
+
+HashType parseHashType(const std::string& s) {
+  if (s == "md5") {
+    return htMD5;
+  }
+  if (s == "sha1") {
+    return htSHA1;
+  } else if (s == "sha256") {
+    return htSHA256;
+  } else if (s == "sha512") {
+    return htSHA512;
+  } else {
+    return htUnknown;
+  }
+}
+
+std::string printHashType(HashType ht) {
+  if (ht == htMD5) {
+    return "md5";
+  }
+  if (ht == htSHA1) {
+    return "sha1";
+  } else if (ht == htSHA256) {
+    return "sha256";
+  } else if (ht == htSHA512) {
+    return "sha512";
+  } else if (ht == htUnknown) {
+    return "<unknown>";
+  } else {
+    LOG(FATAL) << "Unrecognized hash type: " << static_cast<int>(ht);
+    abort();
+  }
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/hash.hh b/third_party/nix/src/libutil/hash.hh
new file mode 100644
index 000000000000..8b52ac657e7f
--- /dev/null
+++ b/third_party/nix/src/libutil/hash.hh
@@ -0,0 +1,147 @@
+#pragma once
+
+#include <absl/status/statusor.h>
+
+#include "libproto/worker.grpc.pb.h"
+#include "libutil/serialise.hh"
+#include "libutil/types.hh"
+
+namespace nix {
+
+// Size of the hashes rendered in store paths, in bytes
+constexpr unsigned int kStorePathHashSize = 20;
+
+MakeError(BadHash, Error);
+
+// TODO(grfn): Replace this with the hash type enum from the daemon proto so we
+// don't have to juggle two different types
+enum HashType : char { htUnknown, htMD5, htSHA1, htSHA256, htSHA512 };
+
+std::optional<HashType> hash_type_from(nix::proto::HashType hash_type);
+
+nix::proto::HashType HashTypeToProto(HashType hash_type);
+
+const int md5HashSize = 16;
+const int sha1HashSize = 20;
+const int sha256HashSize = 32;
+const int sha512HashSize = 64;
+
+// omitted: E O U T
+constexpr char base32Chars[] = "0123456789abcdfghijklmnpqrsvwxyz";
+
+enum Base : int { Base64, Base32, Base16, SRI };
+
+struct Hash {
+  static const unsigned int maxHashSize = 64;
+  unsigned int hashSize = 0;
+  unsigned char hash[maxHashSize] = {};
+
+  HashType type = htUnknown;
+
+  /* Create an unset hash object. */
+  Hash(){};
+
+  /* Create a zero-filled hash object. */
+  explicit Hash(HashType type) : type(type) { init(); };
+
+  /* Initialize the hash from a string representation, in the format
+     "[<type>:]<base16|base32|base64>" or "<type>-<base64>" (a
+     Subresource Integrity hash expression). If the 'type' argument
+     is htUnknown, then the hash type must be specified in the
+     string. */
+  explicit Hash(std::string_view s, HashType type = htUnknown);
+
+  /* Status-returning version of above constructor */
+  static absl::StatusOr<Hash> deserialize(std::string_view s,
+                                          HashType type = htUnknown);
+
+  // Legacy unwrapper for StatusOr. Throws BadHash.
+  static Hash unwrap_throw(absl::StatusOr<Hash> hash) noexcept(false);
+
+  void init();
+
+  /* Check whether a hash is set. */
+  explicit operator bool() const { return type != htUnknown; }
+
+  /* Check whether two hash are equal. */
+  bool operator==(const Hash& h2) const;
+
+  /* Check whether two hash are not equal. */
+  bool operator!=(const Hash& h2) const;
+
+  /* For sorting. */
+  bool operator<(const Hash& h) const;
+
+  /* Returns the length of a base-16 representation of this hash. */
+  size_t base16Len() const { return hashSize * 2; }
+
+  /* Returns the length of a base-32 representation of this hash. */
+  size_t base32Len() const { return (hashSize * 8 - 1) / 5 + 1; }
+
+  /* Returns the length of a base-64 representation of this hash. */
+  size_t base64Len() const { return ((4 * hashSize / 3) + 3) & ~3; }
+
+  /* Return a string representation of the hash, in base-16, base-32
+     or base-64. By default, this is prefixed by the hash type
+     (e.g. "sha256:"). */
+  std::string to_string(Base base = Base32, bool includeType = true) const;
+
+  /* Returns whether the passed string contains entirely valid base16
+     characters. */
+  static bool IsValidBase16(absl::string_view s);
+
+  /* Returns whether the passed string contains entirely valid base32
+     characters. */
+  static bool IsValidBase32(absl::string_view s);
+
+  // Convert this Hash to the format expected in store paths
+  [[nodiscard]] std::string ToStorePathHash() const;
+};
+
+/* Print a hash in base-16 if it's MD5, or base-32 otherwise. */
+std::string printHash16or32(const Hash& hash);
+
+/* Compute the hash of the given string. */
+Hash hashString(HashType ht, const std::string& s);
+
+/* Compute the hash of the given file. */
+Hash hashFile(HashType ht, const Path& path);
+
+/* A pair of the Hash, and the number of bytes consumed. */
+typedef std::pair<Hash, unsigned long long> HashResult;
+
+/* Compute the hash of the given path.  The hash is defined as
+   (essentially) hashString(ht, dumpPath(path)). */
+HashResult hashPath(HashType ht, const Path& path,
+                    PathFilter& filter = defaultPathFilter);
+
+/* Compress a hash to the specified number of bytes by cyclically
+   XORing bytes together. */
+Hash compressHash(const Hash& hash, unsigned int newSize);
+
+/* Parse a string representing a hash type. */
+HashType parseHashType(const std::string& s);
+
+/* And the reverse. */
+std::string printHashType(HashType ht);
+
+namespace hash {
+union Ctx;
+}
+
+class HashSink : public BufferedSink {
+ private:
+  HashType ht;
+  std::unique_ptr<hash::Ctx> ctx;
+  unsigned long long bytes;
+
+ public:
+  explicit HashSink(HashType ht);
+  HashSink(const HashSink& h);
+  ~HashSink();
+  void write(const unsigned char* data, size_t len);
+  HashResult finish();
+  HashResult currentHash();
+};
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/istringstream_nocopy.hh b/third_party/nix/src/libutil/istringstream_nocopy.hh
new file mode 100644
index 000000000000..31683d37c91b
--- /dev/null
+++ b/third_party/nix/src/libutil/istringstream_nocopy.hh
@@ -0,0 +1,85 @@
+/* This file provides a variant of std::istringstream that doesn't
+   copy its string argument. This is useful for large strings. The
+   caller must ensure that the string object is not destroyed while
+   it's referenced by this object. */
+
+#pragma once
+
+#include <iostream>
+#include <string>
+
+template <class CharT, class Traits = std::char_traits<CharT>,
+          class Allocator = std::allocator<CharT>>
+class basic_istringbuf_nocopy : public std::basic_streambuf<CharT, Traits> {
+ public:
+  using string_type = std::basic_string<CharT, Traits, Allocator>;
+
+  using off_type = typename std::basic_streambuf<CharT, Traits>::off_type;
+
+  using pos_type = typename std::basic_streambuf<CharT, Traits>::pos_type;
+
+  using int_type = typename std::basic_streambuf<CharT, Traits>::int_type;
+
+  using traits_type = typename std::basic_streambuf<CharT, Traits>::traits_type;
+
+ private:
+  const string_type& s;
+
+  off_type off;
+
+ public:
+  explicit basic_istringbuf_nocopy(const string_type& s) : s{s}, off{0} {}
+
+ private:
+  pos_type seekoff(off_type off, std::ios_base::seekdir dir,
+                   std::ios_base::openmode which) {
+    if (which & std::ios_base::in) {
+      this->off =
+          dir == std::ios_base::beg
+              ? off
+              : (dir == std::ios_base::end ? s.size() + off : this->off + off);
+    }
+    return pos_type(this->off);
+  }
+
+  pos_type seekpos(pos_type pos, std::ios_base::openmode which) {
+    return seekoff(pos, std::ios_base::beg, which);
+  }
+
+  std::streamsize showmanyc() { return s.size() - off; }
+
+  int_type underflow() {
+    if (typename string_type::size_type(off) == s.size()) {
+      return traits_type::eof();
+    }
+    return traits_type::to_int_type(s[off]);
+  }
+
+  int_type uflow() {
+    if (typename string_type::size_type(off) == s.size()) {
+      return traits_type::eof();
+    }
+    return traits_type::to_int_type(s[off++]);
+  }
+
+  int_type pbackfail(int_type ch) {
+    if (off == 0 || (ch != traits_type::eof() && ch != s[off - 1])) {
+      return traits_type::eof();
+    }
+
+    return traits_type::to_int_type(s[--off]);
+  }
+};
+
+template <class CharT, class Traits = std::char_traits<CharT>,
+          class Allocator = std::allocator<CharT>>
+class basic_istringstream_nocopy : public std::basic_iostream<CharT, Traits> {
+  using buf_type = basic_istringbuf_nocopy<CharT, Traits, Allocator>;
+  buf_type buf;
+
+ public:
+  explicit basic_istringstream_nocopy(const typename buf_type::string_type& s)
+      : std::basic_iostream<CharT, Traits>(&buf), buf(s){};
+};
+
+using istringstream_nocopy = basic_istringstream_nocopy<char>;
diff --git a/third_party/nix/src/libutil/json.cc b/third_party/nix/src/libutil/json.cc
new file mode 100644
index 000000000000..59ff74f5796f
--- /dev/null
+++ b/third_party/nix/src/libutil/json.cc
@@ -0,0 +1,198 @@
+#include "libutil/json.hh"
+
+#include <cstring>
+#include <iomanip>
+
+namespace nix {
+
+void toJSON(std::ostream& str, const char* start, const char* end) {
+  str << '"';
+  for (auto i = start; i != end; i++) {
+    if (*i == '\"' || *i == '\\') {
+      str << '\\' << *i;
+    } else if (*i == '\n') {
+      str << "\\n";
+    } else if (*i == '\r') {
+      str << "\\r";
+    } else if (*i == '\t') {
+      str << "\\t";
+    } else if (*i >= 0 && *i < 32) {
+      str << "\\u" << std::setfill('0') << std::setw(4) << std::hex
+          << static_cast<uint16_t>(*i) << std::dec;
+    } else {
+      str << *i;
+    }
+  }
+  str << '"';
+}
+
+void toJSON(std::ostream& str, const char* s) {
+  if (s == nullptr) {
+    str << "null";
+  } else {
+    toJSON(str, s, s + strlen(s));
+  }
+}
+
+template <>
+void toJSON<int>(std::ostream& str, const int& n) {
+  str << n;
+}
+template <>
+void toJSON<unsigned int>(std::ostream& str, const unsigned int& n) {
+  str << n;
+}
+template <>
+void toJSON<long>(std::ostream& str, const long& n) {
+  str << n;
+}
+template <>
+void toJSON<unsigned long>(std::ostream& str, const unsigned long& n) {
+  str << n;
+}
+template <>
+void toJSON<long long>(std::ostream& str, const long long& n) {
+  str << n;
+}
+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<bool>(std::ostream& str, const bool& b) {
+  str << (b ? "true" : "false");
+}
+
+template <>
+void toJSON<std::nullptr_t>(std::ostream& str, const std::nullptr_t& b) {
+  str << "null";
+}
+
+JSONWriter::JSONWriter(std::ostream& str, bool indent)
+    : state(new JSONState(str, indent)) {
+  state->stack++;
+}
+
+JSONWriter::JSONWriter(JSONState* state) : state(state) { state->stack++; }
+
+JSONWriter::~JSONWriter() {
+  if (state != nullptr) {
+    assertActive();
+    state->stack--;
+    if (state->stack == 0) {
+      delete state;
+    }
+  }
+}
+
+void JSONWriter::comma() {
+  assertActive();
+  if (first) {
+    first = false;
+  } else {
+    state->str << ',';
+  }
+  if (state->indent) {
+    indent();
+  }
+}
+
+void JSONWriter::indent() {
+  state->str << '\n' << std::string(state->depth * 2, ' ');
+}
+
+void JSONList::open() {
+  state->depth++;
+  state->str << '[';
+}
+
+JSONList::~JSONList() {
+  state->depth--;
+  if (state->indent && !first) {
+    indent();
+  }
+  state->str << "]";
+}
+
+JSONList JSONList::list() {
+  comma();
+  return JSONList(state);
+}
+
+JSONObject JSONList::object() {
+  comma();
+  return JSONObject(state);
+}
+
+JSONPlaceholder JSONList::placeholder() {
+  comma();
+  return JSONPlaceholder(state);
+}
+
+void JSONObject::open() {
+  state->depth++;
+  state->str << '{';
+}
+
+JSONObject::~JSONObject() {
+  if (state != nullptr) {
+    state->depth--;
+    if (state->indent && !first) {
+      indent();
+    }
+    state->str << "}";
+  }
+}
+
+void JSONObject::attr(const std::string& s) {
+  comma();
+  toJSON(state->str, s);
+  state->str << ':';
+  if (state->indent) {
+    state->str << ' ';
+  }
+}
+
+JSONList JSONObject::list(const std::string& name) {
+  attr(name);
+  return JSONList(state);
+}
+
+JSONObject JSONObject::object(const std::string& name) {
+  attr(name);
+  return JSONObject(state);
+}
+
+JSONPlaceholder JSONObject::placeholder(const std::string& name) {
+  attr(name);
+  return JSONPlaceholder(state);
+}
+
+JSONList JSONPlaceholder::list() {
+  assertValid();
+  first = false;
+  return JSONList(state);
+}
+
+JSONObject JSONPlaceholder::object() {
+  assertValid();
+  first = false;
+  return JSONObject(state);
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/json.hh b/third_party/nix/src/libutil/json.hh
new file mode 100644
index 000000000000..14d61d8a5716
--- /dev/null
+++ b/third_party/nix/src/libutil/json.hh
@@ -0,0 +1,144 @@
+#pragma once
+
+#include <cassert>
+#include <iostream>
+#include <vector>
+
+namespace nix {
+
+void toJSON(std::ostream& str, const char* start, const char* end);
+void toJSON(std::ostream& str, const char* s);
+
+template <typename T>
+void toJSON(std::ostream& str, const T& n);
+
+class JSONWriter {
+ protected:
+  struct JSONState {
+    std::ostream& str;
+    bool indent;
+    size_t depth = 0;
+    size_t stack = 0;
+    JSONState(std::ostream& str, bool indent) : str(str), indent(indent) {}
+    ~JSONState() { assert(stack == 0); }
+  };
+
+  JSONState* state;
+
+  bool first = true;
+
+  JSONWriter(std::ostream& str, bool indent);
+
+  explicit JSONWriter(JSONState* state);
+
+  ~JSONWriter();
+
+  void assertActive() { assert(state->stack != 0); }
+
+  void comma();
+
+  void indent();
+};
+
+class JSONObject;
+class JSONPlaceholder;
+
+class JSONList : JSONWriter {
+ private:
+  friend class JSONObject;
+  friend class JSONPlaceholder;
+
+  void open();
+
+  explicit JSONList(JSONState* state) : JSONWriter(state) { open(); }
+
+ public:
+  explicit JSONList(std::ostream& str, bool indent = false)
+      : JSONWriter(str, indent) {
+    open();
+  }
+
+  ~JSONList();
+
+  template <typename T>
+  JSONList& elem(const T& v) {
+    comma();
+    toJSON(state->str, v);
+    return *this;
+  }
+
+  JSONList list();
+
+  JSONObject object();
+
+  JSONPlaceholder placeholder();
+};
+
+class JSONObject : JSONWriter {
+ private:
+  friend class JSONList;
+  friend class JSONPlaceholder;
+
+  void open();
+
+  explicit JSONObject(JSONState* state) : JSONWriter(state) { open(); }
+
+  void attr(const std::string& s);
+
+ public:
+  explicit JSONObject(std::ostream& str, bool indent = false)
+      : JSONWriter(str, indent) {
+    open();
+  }
+
+  JSONObject(const JSONObject& obj) = delete;
+
+  JSONObject(JSONObject&& obj) : JSONWriter(obj.state) { obj.state = 0; }
+
+  ~JSONObject();
+
+  template <typename T>
+  JSONObject& attr(const std::string& name, const T& v) {
+    attr(name);
+    toJSON(state->str, v);
+    return *this;
+  }
+
+  JSONList list(const std::string& name);
+
+  JSONObject object(const std::string& name);
+
+  JSONPlaceholder placeholder(const std::string& name);
+};
+
+class JSONPlaceholder : JSONWriter {
+ private:
+  friend class JSONList;
+  friend class JSONObject;
+
+  explicit JSONPlaceholder(JSONState* state) : JSONWriter(state) {}
+
+  void assertValid() {
+    assertActive();
+    assert(first);
+  }
+
+ public:
+  explicit JSONPlaceholder(std::ostream& str, bool indent = false)
+      : JSONWriter(str, indent) {}
+
+  ~JSONPlaceholder() { assert(!first || std::uncaught_exception()); }
+
+  template <typename T>
+  void write(const T& v) {
+    assertValid();
+    first = false;
+    toJSON(state->str, v);
+  }
+
+  JSONList list();
+
+  JSONObject object();
+};
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/lazy.hh b/third_party/nix/src/libutil/lazy.hh
new file mode 100644
index 000000000000..5c6ff5d8df6a
--- /dev/null
+++ b/third_party/nix/src/libutil/lazy.hh
@@ -0,0 +1,45 @@
+#include <exception>
+#include <functional>
+#include <mutex>
+
+namespace nix {
+
+/* A helper class for lazily-initialized variables.
+
+     Lazy<T> var([]() { return value; });
+
+   declares a variable of type T that is initialized to 'value' (in a
+   thread-safe way) on first use, that is, when var() is first
+   called. If the initialiser code throws an exception, then all
+   subsequent calls to var() will rethrow that exception. */
+template <typename T>
+class Lazy {
+  typedef std::function<T()> Init;
+
+  Init init;
+
+  std::once_flag done;
+
+  T value;
+
+  std::exception_ptr ex;
+
+ public:
+  explicit Lazy(Init init) : init(init) {}
+
+  const T& operator()() {
+    std::call_once(done, [&]() {
+      try {
+        value = init();
+      } catch (...) {
+        ex = std::current_exception();
+      }
+    });
+    if (ex) {
+      std::rethrow_exception(ex);
+    }
+    return value;
+  }
+};
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/lru-cache.hh b/third_party/nix/src/libutil/lru-cache.hh
new file mode 100644
index 000000000000..1832c542449e
--- /dev/null
+++ b/third_party/nix/src/libutil/lru-cache.hh
@@ -0,0 +1,90 @@
+#pragma once
+
+#include <list>
+#include <map>
+#include <optional>
+
+namespace nix {
+
+/* A simple least-recently used cache. Not thread-safe. */
+template <typename Key, typename Value>
+class LRUCache {
+ private:
+  size_t capacity;
+
+  // Stupid wrapper to get around circular dependency between Data
+  // and LRU.
+  struct LRUIterator;
+
+  using Data = std::map<Key, std::pair<LRUIterator, Value>>;
+  using LRU = std::list<typename Data::iterator>;
+
+  struct LRUIterator {
+    typename LRU::iterator it;
+  };
+
+  Data data;
+  LRU lru;
+
+ public:
+  explicit LRUCache(size_t capacity) : capacity(capacity) {}
+
+  /* Insert or upsert an item in the cache. */
+  void upsert(const Key& key, const Value& value) {
+    if (capacity == 0) {
+      return;
+    }
+
+    erase(key);
+
+    if (data.size() >= capacity) {
+      /* Retire the oldest item. */
+      auto oldest = lru.begin();
+      data.erase(*oldest);
+      lru.erase(oldest);
+    }
+
+    auto res = data.emplace(key, std::make_pair(LRUIterator(), value));
+    assert(res.second);
+    auto& i(res.first);
+
+    auto j = lru.insert(lru.end(), i);
+
+    i->second.first.it = j;
+  }
+
+  bool erase(const Key& key) {
+    auto i = data.find(key);
+    if (i == data.end()) {
+      return false;
+    }
+    lru.erase(i->second.first.it);
+    data.erase(i);
+    return true;
+  }
+
+  /* Look up an item in the cache. If it exists, it becomes the most
+     recently used item. */
+  std::optional<Value> get(const Key& key) {
+    auto i = data.find(key);
+    if (i == data.end()) {
+      return {};
+    }
+
+    /* Move this item to the back of the LRU list. */
+    lru.erase(i->second.first.it);
+    auto j = lru.insert(lru.end(), i);
+    i->second.first.it = j;
+
+    return i->second.second;
+  }
+
+  size_t size() { return data.size(); }
+
+  void clear() {
+    data.clear();
+    lru.clear();
+  }
+};
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/monitor-fd.hh b/third_party/nix/src/libutil/monitor-fd.hh
new file mode 100644
index 000000000000..c818c5826116
--- /dev/null
+++ b/third_party/nix/src/libutil/monitor-fd.hh
@@ -0,0 +1,57 @@
+#pragma once
+
+#include <atomic>
+#include <cstdlib>
+#include <thread>
+
+#include <poll.h>
+#include <signal.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+namespace nix {
+
+class MonitorFdHup {
+ private:
+  std::thread thread;
+
+ public:
+  MonitorFdHup(int fd) {
+    thread = std::thread([fd]() {
+      while (true) {
+        /* Wait indefinitely until a POLLHUP occurs. */
+        struct pollfd fds[1];
+        fds[0].fd = fd;
+        /* This shouldn't be necessary, but macOS doesn't seem to
+           like a zeroed out events field.
+           See rdar://37537852.
+        */
+        fds[0].events = POLLHUP;
+        auto count = poll(fds, 1, -1);
+        if (count == -1) {
+          abort();
+        }  // can't happen
+        /* This shouldn't happen, but can on macOS due to a bug.
+           See rdar://37550628.
+
+           This may eventually need a delay or further
+           coordination with the main thread if spinning proves
+           too harmful.
+         */
+        if (count == 0) {
+          continue;
+        }
+        assert(fds[0].revents & POLLHUP);
+        triggerInterrupt();
+        break;
+      }
+    });
+  };
+
+  ~MonitorFdHup() {
+    pthread_cancel(thread.native_handle());
+    thread.join();
+  }
+};
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/pool.hh b/third_party/nix/src/libutil/pool.hh
new file mode 100644
index 000000000000..b5c3c4b5c43f
--- /dev/null
+++ b/third_party/nix/src/libutil/pool.hh
@@ -0,0 +1,176 @@
+#pragma once
+
+#include <cassert>
+#include <functional>
+#include <limits>
+#include <list>
+#include <memory>
+
+#include "libutil/ref.hh"
+#include "libutil/sync.hh"
+
+namespace nix {
+
+/* This template class implements a simple pool manager of resources
+   of some type R, such as database connections. It is used as
+   follows:
+
+     class Connection { ... };
+
+     Pool<Connection> pool;
+
+     {
+       auto conn(pool.get());
+       conn->exec("select ...");
+     }
+
+   Here, the Connection object referenced by โ€˜connโ€™ is automatically
+   returned to the pool when โ€˜connโ€™ goes out of scope.
+*/
+
+template <class R>
+class Pool {
+ public:
+  /* A function that produces new instances of R on demand. */
+  typedef std::function<ref<R>()> Factory;
+
+  /* A function that checks whether an instance of R is still
+     usable. Unusable instances are removed from the pool. */
+  using Validator = std::function<bool(const ref<R>&)>;
+
+ private:
+  Factory factory;
+  Validator validator;
+
+  struct State {
+    size_t inUse = 0;
+    size_t max;
+    std::vector<ref<R>> idle;
+  };
+
+  Sync<State> state;
+
+  std::condition_variable wakeup;
+
+ public:
+  explicit Pool(
+      size_t max = std::numeric_limits<size_t>::max(),
+      const Factory& factory = []() { return make_ref<R>(); },
+      const Validator& validator = [](ref<R> r) { return true; })
+      : factory(factory), validator(validator) {
+    auto state_(state.lock());
+    state_->max = max;
+  }
+
+  void incCapacity() {
+    auto state_(state.lock());
+    state_->max++;
+    /* we could wakeup here, but this is only used when we're
+     * about to nest Pool usages, and we want to save the slot for
+     * the nested use if we can
+     */
+  }
+
+  void decCapacity() {
+    auto state_(state.lock());
+    state_->max--;
+  }
+
+  ~Pool() {
+    auto state_(state.lock());
+    assert(!state_->inUse);
+    state_->max = 0;
+    state_->idle.clear();
+  }
+
+  class Handle {
+   private:
+    Pool& pool;
+    std::shared_ptr<R> r;
+    bool bad = false;
+
+    friend Pool;
+
+    Handle(Pool& pool, std::shared_ptr<R> r) : pool(pool), r(r) {}
+
+   public:
+    Handle(Handle&& h) : pool(h.pool), r(h.r) { h.r.reset(); }
+
+    Handle(const Handle& l) = delete;
+
+    ~Handle() {
+      if (!r) {
+        return;
+      }
+      {
+        auto state_(pool.state.lock());
+        if (!bad) {
+          state_->idle.push_back(ref<R>(r));
+        }
+        assert(state_->inUse);
+        state_->inUse--;
+      }
+      pool.wakeup.notify_one();
+    }
+
+    R* operator->() { return &*r; }
+    R& operator*() { return *r; }
+
+    void markBad() { bad = true; }
+  };
+
+  Handle get() {
+    {
+      auto state_(state.lock());
+
+      /* If we're over the maximum number of instance, we need
+         to wait until a slot becomes available. */
+      while (state_->idle.empty() && state_->inUse >= state_->max) {
+        state_.wait(wakeup);
+      }
+
+      while (!state_->idle.empty()) {
+        auto p = state_->idle.back();
+        state_->idle.pop_back();
+        if (validator(p)) {
+          state_->inUse++;
+          return Handle(*this, p);
+        }
+      }
+
+      state_->inUse++;
+    }
+
+    /* We need to create a new instance. Because that might take a
+       while, we don't hold the lock in the meantime. */
+    try {
+      Handle h(*this, factory());
+      return h;
+    } catch (...) {
+      auto state_(state.lock());
+      state_->inUse--;
+      wakeup.notify_one();
+      throw;
+    }
+  }
+
+  size_t count() {
+    auto state_(state.lock());
+    return state_->idle.size() + state_->inUse;
+  }
+
+  size_t capacity() { return state.lock()->max; }
+
+  void flushBad() {
+    auto state_(state.lock());
+    std::vector<ref<R>> left;
+    for (auto& p : state_->idle) {
+      if (validator(p)) {
+        left.push_back(p);
+      }
+    }
+    std::swap(state_->idle, left);
+  }
+};
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/proto.hh b/third_party/nix/src/libutil/proto.hh
new file mode 100644
index 000000000000..058cb7b7b452
--- /dev/null
+++ b/third_party/nix/src/libutil/proto.hh
@@ -0,0 +1,174 @@
+#pragma once
+
+#include <absl/status/status.h>
+#include <grpcpp/impl/codegen/status.h>
+#include <grpcpp/impl/codegen/status_code_enum.h>
+
+#include "libproto/worker.pb.h"
+#include "libutil/types.hh"
+
+namespace nix::util::proto {
+
+inline ::nix::proto::StorePath StorePath(const Path& path) {
+  ::nix::proto::StorePath store_path;
+  store_path.set_path(path);
+  return store_path;
+}
+
+inline ::nix::proto::StorePaths StorePaths(const PathSet& paths) {
+  ::nix::proto::StorePaths result;
+  for (const auto& path : paths) {
+    result.add_paths(path);
+  }
+  return result;
+}
+
+template <typename T, typename U>
+T FillFrom(const U& src) {
+  T result;
+  result.insert(src.begin(), src.end());
+  return result;
+}
+
+constexpr absl::StatusCode GRPCStatusCodeToAbsl(grpc::StatusCode code) {
+  switch (code) {
+    case grpc::StatusCode::OK:
+      return absl::StatusCode::kOk;
+    case grpc::StatusCode::CANCELLED:
+      return absl::StatusCode::kCancelled;
+    case grpc::StatusCode::UNKNOWN:
+      return absl::StatusCode::kUnknown;
+    case grpc::StatusCode::INVALID_ARGUMENT:
+      return absl::StatusCode::kInvalidArgument;
+    case grpc::StatusCode::DEADLINE_EXCEEDED:
+      return absl::StatusCode::kDeadlineExceeded;
+    case grpc::StatusCode::NOT_FOUND:
+      return absl::StatusCode::kNotFound;
+    case grpc::StatusCode::ALREADY_EXISTS:
+      return absl::StatusCode::kAlreadyExists;
+    case grpc::StatusCode::PERMISSION_DENIED:
+      return absl::StatusCode::kPermissionDenied;
+    case grpc::StatusCode::UNAUTHENTICATED:
+      return absl::StatusCode::kUnauthenticated;
+    case grpc::StatusCode::RESOURCE_EXHAUSTED:
+      return absl::StatusCode::kResourceExhausted;
+    case grpc::StatusCode::FAILED_PRECONDITION:
+      return absl::StatusCode::kFailedPrecondition;
+    case grpc::StatusCode::ABORTED:
+      return absl::StatusCode::kAborted;
+    case grpc::StatusCode::OUT_OF_RANGE:
+      return absl::StatusCode::kOutOfRange;
+    case grpc::StatusCode::UNIMPLEMENTED:
+      return absl::StatusCode::kUnimplemented;
+    case grpc::StatusCode::INTERNAL:
+      return absl::StatusCode::kInternal;
+    case grpc::StatusCode::UNAVAILABLE:
+      return absl::StatusCode::kUnavailable;
+    case grpc::StatusCode::DATA_LOSS:
+      return absl::StatusCode::kDataLoss;
+    default:
+      return absl::StatusCode::kInternal;
+  }
+}
+
+constexpr grpc::StatusCode AbslStatusCodeToGRPC(absl::StatusCode code) {
+  switch (code) {
+    case absl::StatusCode::kOk:
+      return grpc::StatusCode::OK;
+    case absl::StatusCode::kCancelled:
+      return grpc::StatusCode::CANCELLED;
+    case absl::StatusCode::kUnknown:
+      return grpc::StatusCode::UNKNOWN;
+    case absl::StatusCode::kInvalidArgument:
+      return grpc::StatusCode::INVALID_ARGUMENT;
+    case absl::StatusCode::kDeadlineExceeded:
+      return grpc::StatusCode::DEADLINE_EXCEEDED;
+    case absl::StatusCode::kNotFound:
+      return grpc::StatusCode::NOT_FOUND;
+    case absl::StatusCode::kAlreadyExists:
+      return grpc::StatusCode::ALREADY_EXISTS;
+    case absl::StatusCode::kPermissionDenied:
+      return grpc::StatusCode::PERMISSION_DENIED;
+    case absl::StatusCode::kUnauthenticated:
+      return grpc::StatusCode::UNAUTHENTICATED;
+    case absl::StatusCode::kResourceExhausted:
+      return grpc::StatusCode::RESOURCE_EXHAUSTED;
+    case absl::StatusCode::kFailedPrecondition:
+      return grpc::StatusCode::FAILED_PRECONDITION;
+    case absl::StatusCode::kAborted:
+      return grpc::StatusCode::ABORTED;
+    case absl::StatusCode::kOutOfRange:
+      return grpc::StatusCode::OUT_OF_RANGE;
+    case absl::StatusCode::kUnimplemented:
+      return grpc::StatusCode::UNIMPLEMENTED;
+    case absl::StatusCode::kInternal:
+      return grpc::StatusCode::INTERNAL;
+    case absl::StatusCode::kUnavailable:
+      return grpc::StatusCode::UNAVAILABLE;
+    case absl::StatusCode::kDataLoss:
+      return grpc::StatusCode::DATA_LOSS;
+    default:
+      return grpc::StatusCode::INTERNAL;
+  }
+}
+
+constexpr absl::string_view GRPCStatusCodeDescription(grpc::StatusCode code) {
+  switch (code) {
+    case grpc::StatusCode::OK:
+      return "OK";
+    case grpc::StatusCode::CANCELLED:
+      return "CANCELLED";
+    case grpc::StatusCode::UNKNOWN:
+      return "UNKNOWN";
+    case grpc::StatusCode::INVALID_ARGUMENT:
+      return "INVALID_ARGUMENT";
+    case grpc::StatusCode::DEADLINE_EXCEEDED:
+      return "DEADLINE_EXCEEDED";
+    case grpc::StatusCode::NOT_FOUND:
+      return "NOT_FOUND";
+    case grpc::StatusCode::ALREADY_EXISTS:
+      return "ALREADY_EXISTS";
+    case grpc::StatusCode::PERMISSION_DENIED:
+      return "PERMISSION_DENIED";
+    case grpc::StatusCode::UNAUTHENTICATED:
+      return "UNAUTHENTICATED";
+    case grpc::StatusCode::RESOURCE_EXHAUSTED:
+      return "RESOURCE_EXHAUSTED";
+    case grpc::StatusCode::FAILED_PRECONDITION:
+      return "FAILED_PRECONDITION";
+    case grpc::StatusCode::ABORTED:
+      return "ABORTED";
+    case grpc::StatusCode::OUT_OF_RANGE:
+      return "OUT_OF_RANGE";
+    case grpc::StatusCode::UNIMPLEMENTED:
+      return "UNIMPLEMENTED";
+    case grpc::StatusCode::INTERNAL:
+      return "INTERNAL";
+    case grpc::StatusCode::UNAVAILABLE:
+      return "UNAVAILABLE";
+    case grpc::StatusCode::DATA_LOSS:
+      return "DATA_LOSS";
+    default:
+      return "<BAD ERROR CODE>";
+  };
+}
+
+inline absl::Status GRPCStatusToAbsl(grpc::Status status) {
+  if (status.ok()) {
+    return absl::OkStatus();
+  }
+
+  return absl::Status(GRPCStatusCodeToAbsl(status.error_code()),
+                      status.error_message());
+}
+
+inline grpc::Status AbslToGRPCStatus(absl::Status status) {
+  if (status.ok()) {
+    return grpc::Status::OK;
+  }
+
+  return grpc::Status(AbslStatusCodeToGRPC(status.code()),
+                      std::string(status.message()));
+}
+
+}  // namespace nix::util::proto
diff --git a/third_party/nix/src/libutil/ref.hh b/third_party/nix/src/libutil/ref.hh
new file mode 100644
index 000000000000..3c375491fd0b
--- /dev/null
+++ b/third_party/nix/src/libutil/ref.hh
@@ -0,0 +1,65 @@
+#pragma once
+
+#include <exception>
+#include <memory>
+#include <stdexcept>
+
+namespace nix {
+
+/* A simple non-nullable reference-counted pointer. Actually a wrapper
+   around std::shared_ptr that prevents non-null constructions. */
+template <typename T>
+class ref {  // TODO(tazjin): rename to brainworm_ref or something
+ private:
+  std::shared_ptr<T> p;
+
+ public:
+  ref<T>(const ref<T>& r) : p(r.p) {}
+
+  explicit ref<T>(const std::shared_ptr<T>& p) : p(p) {
+    if (!p) {
+      throw std::invalid_argument("null pointer cast to ref");
+    }
+  }
+
+  explicit ref<T>(T* p) : p(p) {
+    if (!p) {
+      throw std::invalid_argument("null pointer cast to ref");
+    }
+  }
+
+  T* operator->() const { return &*p; }
+
+  T& operator*() const { return *p; }
+
+  operator std::shared_ptr<T>() const { return p; }
+
+  std::shared_ptr<T> get_ptr() const { return p; }
+
+  template <typename T2>
+  ref<T2> cast() const {
+    return ref<T2>(std::dynamic_pointer_cast<T2>(p));
+  }
+
+  template <typename T2>
+  std::shared_ptr<T2> dynamic_pointer_cast() const {
+    return std::dynamic_pointer_cast<T2>(p);
+  }
+
+  template <typename T2>
+  operator ref<T2>() const {
+    return ref<T2>((std::shared_ptr<T2>)p);
+  }
+
+ private:
+  template <typename T2, typename... Args>
+  friend ref<T2> make_ref(Args&&... args);
+};
+
+template <typename T, typename... Args>
+inline ref<T> make_ref(Args&&... args) {
+  auto p = std::make_shared<T>(std::forward<Args>(args)...);
+  return ref<T>(p);
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/serialise.cc b/third_party/nix/src/libutil/serialise.cc
new file mode 100644
index 000000000000..288255089bb6
--- /dev/null
+++ b/third_party/nix/src/libutil/serialise.cc
@@ -0,0 +1,311 @@
+#include "libutil/serialise.hh"
+
+#include <boost/coroutine2/coroutine.hpp>
+#include <cerrno>
+#include <cstring>
+#include <memory>
+#include <utility>
+
+#include <glog/logging.h>
+
+#include "libutil/util.hh"
+
+namespace nix {
+
+void BufferedSink::operator()(const unsigned char* data, size_t len) {
+  if (!buffer) {
+    buffer = decltype(buffer)(new unsigned char[bufSize]);
+  }
+
+  while (len != 0u) {
+    /* Optimisation: bypass the buffer if the data exceeds the
+       buffer size. */
+    if (bufPos + len >= bufSize) {
+      flush();
+      write(data, len);
+      break;
+    }
+    /* Otherwise, copy the bytes to the buffer.  Flush the buffer
+       when it's full. */
+    size_t n = bufPos + len > bufSize ? bufSize - bufPos : len;
+    memcpy(buffer.get() + bufPos, data, n);
+    data += n;
+    bufPos += n;
+    len -= n;
+    if (bufPos == bufSize) {
+      flush();
+    }
+  }
+}
+
+void BufferedSink::flush() {
+  if (bufPos == 0) {
+    return;
+  }
+  size_t n = bufPos;
+  bufPos = 0;  // don't trigger the assert() in ~BufferedSink()
+  write(buffer.get(), n);
+}
+
+FdSink::~FdSink() {
+  try {
+    flush();
+  } catch (...) {
+    ignoreException();
+  }
+}
+
+size_t threshold = 256 * 1024 * 1024;
+
+static void warnLargeDump() {
+  LOG(WARNING)
+      << "dumping very large path (> 256 MiB); this may run out of memory";
+}
+
+void FdSink::write(const unsigned char* data, size_t len) {
+  written += len;
+  static bool warned = false;
+  if (warn && !warned) {
+    if (written > threshold) {
+      warnLargeDump();
+      warned = true;
+    }
+  }
+  try {
+    writeFull(fd, data, len);
+  } catch (SysError& e) {
+    _good = false;
+    throw;
+  }
+}
+
+bool FdSink::good() { return _good; }
+
+void Source::operator()(unsigned char* data, size_t len) {
+  while (len != 0u) {
+    size_t n = read(data, len);
+    data += n;
+    len -= n;
+  }
+}
+
+std::string Source::drain() {
+  std::string s;
+  std::vector<unsigned char> buf(8192);
+  while (true) {
+    size_t n;
+    try {
+      n = read(buf.data(), buf.size());
+      s.append(reinterpret_cast<char*>(buf.data()), n);
+    } catch (EndOfFile&) {
+      break;
+    }
+  }
+  return s;
+}
+
+size_t BufferedSource::read(unsigned char* data, size_t len) {
+  if (!buffer) {
+    buffer = decltype(buffer)(new unsigned char[bufSize]);
+  }
+
+  if (bufPosIn == 0u) {
+    bufPosIn = readUnbuffered(buffer.get(), bufSize);
+  }
+
+  /* Copy out the data in the buffer. */
+  size_t n = len > bufPosIn - bufPosOut ? bufPosIn - bufPosOut : len;
+  memcpy(data, buffer.get() + bufPosOut, n);
+  bufPosOut += n;
+  if (bufPosIn == bufPosOut) {
+    bufPosIn = bufPosOut = 0;
+  }
+  return n;
+}
+
+bool BufferedSource::hasData() { return bufPosOut < bufPosIn; }
+
+size_t FdSource::readUnbuffered(unsigned char* data, size_t len) {
+  ssize_t n;
+  do {
+    checkInterrupt();
+    n = ::read(fd, reinterpret_cast<char*>(data), len);
+  } while (n == -1 && errno == EINTR);
+  if (n == -1) {
+    _good = false;
+    throw SysError("reading from file");
+  }
+  if (n == 0) {
+    _good = false;
+    throw EndOfFile("unexpected end-of-file");
+  }
+  read += n;
+  return n;
+}
+
+bool FdSource::good() { return _good; }
+
+size_t StringSource::read(unsigned char* data, size_t len) {
+  if (pos == s.size()) {
+    throw EndOfFile("end of string reached");
+  }
+  size_t n = s.copy(reinterpret_cast<char*>(data), len, pos);
+  pos += n;
+  return n;
+}
+
+#if BOOST_VERSION >= 106300 && BOOST_VERSION < 106600
+#error Coroutines are broken in this version of Boost!
+#endif
+
+std::unique_ptr<Source> sinkToSource(const std::function<void(Sink&)>& fun,
+                                     const std::function<void()>& eof) {
+  struct SinkToSource : Source {
+    using coro_t = boost::coroutines2::coroutine<std::string>;
+
+    std::function<void(Sink&)> fun;
+    std::function<void()> eof;
+    std::optional<coro_t::pull_type> coro;
+    bool started = false;
+
+    SinkToSource(std::function<void(Sink&)> fun, std::function<void()> eof)
+        : fun(std::move(fun)), eof(std::move(eof)) {}
+
+    std::string cur;
+    size_t pos = 0;
+
+    size_t read(unsigned char* data, size_t len) override {
+      if (!coro) {
+        coro = coro_t::pull_type([&](coro_t::push_type& yield) {
+          LambdaSink sink([&](const unsigned char* data, size_t len) {
+            if (len != 0u) {
+              yield(std::string(reinterpret_cast<const char*>(data), len));
+            }
+          });
+          fun(sink);
+        });
+      }
+
+      if (!*coro) {
+        eof();
+        abort();
+      }
+
+      if (pos == cur.size()) {
+        if (!cur.empty()) {
+          (*coro)();
+        }
+        cur = coro->get();
+        pos = 0;
+      }
+
+      auto n = std::min(cur.size() - pos, len);
+      memcpy(data, reinterpret_cast<unsigned char*>(cur.data()) + pos, n);
+      pos += n;
+
+      return n;
+    }
+  };
+
+  return std::make_unique<SinkToSource>(fun, eof);
+}
+
+void writePadding(size_t len, Sink& sink) {
+  if ((len % 8) != 0u) {
+    unsigned char zero[8];
+    memset(zero, 0, sizeof(zero));
+    sink(zero, 8 - (len % 8));
+  }
+}
+
+void writeString(const unsigned char* buf, size_t len, Sink& sink) {
+  sink << len;
+  sink(buf, len);
+  writePadding(len, sink);
+}
+
+Sink& operator<<(Sink& sink, const std::string& s) {
+  writeString(reinterpret_cast<const unsigned char*>(s.data()), s.size(), sink);
+  return sink;
+}
+
+template <class T>
+void writeStrings(const T& ss, Sink& sink) {
+  sink << ss.size();
+  for (auto& i : ss) {
+    sink << i;
+  }
+}
+
+Sink& operator<<(Sink& sink, const Strings& s) {
+  writeStrings(s, sink);
+  return sink;
+}
+
+Sink& operator<<(Sink& sink, const StringSet& s) {
+  writeStrings(s, sink);
+  return sink;
+}
+
+void readPadding(size_t len, Source& source) {
+  if ((len % 8) != 0u) {
+    unsigned char zero[8];
+    size_t n = 8 - (len % 8);
+    source(zero, n);
+    for (unsigned int i = 0; i < n; i++) {
+      if (zero[i] != 0u) {
+        throw SerialisationError("non-zero padding");
+      }
+    }
+  }
+}
+
+size_t readString(unsigned char* buf, size_t max, Source& source) {
+  auto len = readNum<size_t>(source);
+  if (len > max) {
+    throw SerialisationError("string is too long");
+  }
+  source(buf, len);
+  readPadding(len, source);
+  return len;
+}
+
+std::string readString(Source& source, size_t max) {
+  auto len = readNum<size_t>(source);
+  if (len > max) {
+    throw SerialisationError("string is too long");
+  }
+  std::string res(len, 0);
+  source(reinterpret_cast<unsigned char*>(res.data()), len);
+  readPadding(len, source);
+  return res;
+}
+
+Source& operator>>(Source& in, std::string& s) {
+  s = readString(in);
+  return in;
+}
+
+template <class T>
+T readStrings(Source& source) {
+  auto count = readNum<size_t>(source);
+  T ss;
+  while (count--) {
+    ss.insert(ss.end(), readString(source));
+  }
+  return ss;
+}
+
+template Paths readStrings(Source& source);
+template PathSet readStrings(Source& source);
+
+void StringSink::operator()(const unsigned char* data, size_t len) {
+  static bool warned = false;
+  if (!warned && s->size() > threshold) {
+    warnLargeDump();
+    warned = true;
+  }
+  s->append(reinterpret_cast<const char*>(data), len);
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/serialise.hh b/third_party/nix/src/libutil/serialise.hh
new file mode 100644
index 000000000000..c6d1d814dbdd
--- /dev/null
+++ b/third_party/nix/src/libutil/serialise.hh
@@ -0,0 +1,289 @@
+#pragma once
+
+#include <memory>
+
+#include "libutil/types.hh"
+#include "libutil/util.hh"
+
+namespace nix {
+
+/* Abstract destination of binary data. */
+struct Sink {
+  virtual ~Sink() {}
+  virtual void operator()(const unsigned char* data, size_t len) = 0;
+  virtual bool good() { return true; }
+
+  void operator()(const std::string& s) {
+    (*this)((const unsigned char*)s.data(), s.size());
+  }
+};
+
+/* A buffered abstract sink. */
+struct BufferedSink : Sink {
+  size_t bufSize, bufPos;
+  std::unique_ptr<unsigned char[]> buffer;
+
+  explicit BufferedSink(size_t bufSize = 32 * 1024)
+      : bufSize(bufSize), bufPos(0), buffer(nullptr) {}
+
+  void operator()(const unsigned char* data, size_t len) override;
+
+  void operator()(const std::string& s) { Sink::operator()(s); }
+
+  void flush();
+
+  virtual void write(const unsigned char* data, size_t len) = 0;
+};
+
+/* Abstract source of binary data. */
+struct Source {
+  virtual ~Source() {}
+
+  /* Store exactly โ€˜lenโ€™ bytes in the buffer pointed to by โ€˜dataโ€™.
+     It blocks until all the requested data is available, or throws
+     an error if it is not going to be available.   */
+  void operator()(unsigned char* data, size_t len);
+
+  /* Store up to โ€˜lenโ€™ in the buffer pointed to by โ€˜dataโ€™, and
+     return the number of bytes stored.  It blocks until at least
+     one byte is available. */
+  virtual size_t read(unsigned char* data, size_t len) = 0;
+
+  virtual bool good() { return true; }
+
+  std::string drain();
+};
+
+/* A buffered abstract source. */
+struct BufferedSource : Source {
+  size_t bufSize, bufPosIn, bufPosOut;
+  std::unique_ptr<unsigned char[]> buffer;
+
+  explicit BufferedSource(size_t bufSize = 32 * 1024)
+      : bufSize(bufSize), bufPosIn(0), bufPosOut(0), buffer(nullptr) {}
+
+  size_t read(unsigned char* data, size_t len) override;
+
+  bool hasData();
+
+ protected:
+  /* Underlying read call, to be overridden. */
+  virtual size_t readUnbuffered(unsigned char* data, size_t len) = 0;
+};
+
+/* A sink that writes data to a file descriptor. */
+struct FdSink : BufferedSink {
+  int fd;
+  bool warn = false;
+  size_t written = 0;
+
+  FdSink() : fd(-1) {}
+  explicit FdSink(int fd) : fd(fd) {}
+  FdSink(FdSink&&) = default;
+
+  FdSink& operator=(FdSink&& s) {
+    flush();
+    fd = s.fd;
+    s.fd = -1;
+    warn = s.warn;
+    written = s.written;
+    return *this;
+  }
+
+  ~FdSink();
+
+  void write(const unsigned char* data, size_t len) override;
+
+  bool good() override;
+
+ private:
+  bool _good = true;
+};
+
+/* A source that reads data from a file descriptor. */
+struct FdSource : BufferedSource {
+  int fd;
+  size_t read = 0;
+
+  FdSource() : fd(-1) {}
+  explicit FdSource(int fd) : fd(fd) {}
+  FdSource(FdSource&&) = default;
+
+  FdSource& operator=(FdSource&& s) {
+    fd = s.fd;
+    s.fd = -1;
+    read = s.read;
+    return *this;
+  }
+
+  bool good() override;
+
+ protected:
+  size_t readUnbuffered(unsigned char* data, size_t len) override;
+
+ private:
+  bool _good = true;
+};
+
+/* A sink that writes data to a string. */
+struct StringSink : Sink {
+  ref<std::string> s;
+  StringSink() : s(make_ref<std::string>()){};
+  explicit StringSink(ref<std::string> s) : s(s){};
+  void operator()(const unsigned char* data, size_t len) override;
+};
+
+/* A source that reads data from a string. */
+struct StringSource : Source {
+  const std::string& s;
+  size_t pos;
+  explicit StringSource(const std::string& _s) : s(_s), pos(0) {}
+  size_t read(unsigned char* data, size_t len) override;
+};
+
+/* Adapter class of a Source that saves all data read to `s'. */
+struct TeeSource : Source {
+  Source& orig;
+  ref<std::string> data;
+  explicit TeeSource(Source& orig)
+      : orig(orig), data(make_ref<std::string>()) {}
+  size_t read(unsigned char* data, size_t len) {
+    size_t n = orig.read(data, len);
+    this->data->append((const char*)data, n);
+    return n;
+  }
+};
+
+/* A reader that consumes the original Source until 'size'. */
+struct SizedSource : Source {
+  Source& orig;
+  size_t remain;
+  SizedSource(Source& orig, size_t size) : orig(orig), remain(size) {}
+  size_t read(unsigned char* data, size_t len) {
+    if (this->remain <= 0) {
+      throw EndOfFile("sized: unexpected end-of-file");
+    }
+    len = std::min(len, this->remain);
+    size_t n = this->orig.read(data, len);
+    this->remain -= n;
+    return n;
+  }
+
+  /* Consume the original source until no remain data is left to consume. */
+  size_t drainAll() {
+    std::vector<unsigned char> buf(8192);
+    size_t sum = 0;
+    while (this->remain > 0) {
+      size_t n = read(buf.data(), buf.size());
+      sum += n;
+    }
+    return sum;
+  }
+};
+
+/* Convert a function into a sink. */
+struct LambdaSink : Sink {
+  typedef std::function<void(const unsigned char*, size_t)> lambda_t;
+
+  lambda_t lambda;
+
+  explicit LambdaSink(const lambda_t& lambda) : lambda(lambda) {}
+
+  virtual void operator()(const unsigned char* data, size_t len) {
+    lambda(data, len);
+  }
+};
+
+/* Convert a function into a source. */
+struct LambdaSource : Source {
+  using lambda_t = std::function<size_t(unsigned char*, size_t)>;
+
+  lambda_t lambda;
+
+  explicit LambdaSource(const lambda_t& lambda) : lambda(lambda) {}
+
+  size_t read(unsigned char* data, size_t len) override {
+    return lambda(data, len);
+  }
+};
+
+/* Convert a function that feeds data into a Sink into a Source. The
+   Source executes the function as a coroutine. */
+std::unique_ptr<Source> sinkToSource(
+    const std::function<void(Sink&)>& fun,
+    const std::function<void()>& eof = []() {
+      throw EndOfFile("coroutine has finished");
+    });
+
+void writePadding(size_t len, Sink& sink);
+void writeString(const unsigned char* buf, size_t len, Sink& sink);
+
+inline Sink& operator<<(Sink& sink, uint64_t n) {
+  unsigned char buf[8];
+  buf[0] = n & 0xff;
+  buf[1] = (n >> 8) & 0xff;
+  buf[2] = (n >> 16) & 0xff;
+  buf[3] = (n >> 24) & 0xff;
+  buf[4] = (n >> 32) & 0xff;
+  buf[5] = (n >> 40) & 0xff;
+  buf[6] = (n >> 48) & 0xff;
+  buf[7] = (unsigned char)(n >> 56) & 0xff;
+  sink(buf, sizeof(buf));
+  return sink;
+}
+
+Sink& operator<<(Sink& sink, const std::string& s);
+Sink& operator<<(Sink& sink, const Strings& s);
+Sink& operator<<(Sink& sink, const StringSet& s);
+
+MakeError(SerialisationError, Error);
+
+template <typename T>
+T readNum(Source& source) {
+  unsigned char buf[8];
+  source(buf, sizeof(buf));
+
+  uint64_t n =
+      ((unsigned long long)buf[0]) | ((unsigned long long)buf[1] << 8) |
+      ((unsigned long long)buf[2] << 16) | ((unsigned long long)buf[3] << 24) |
+      ((unsigned long long)buf[4] << 32) | ((unsigned long long)buf[5] << 40) |
+      ((unsigned long long)buf[6] << 48) | ((unsigned long long)buf[7] << 56);
+
+  if (n > std::numeric_limits<T>::max()) {
+    throw SerialisationError("serialised integer %d is too large for type '%s'",
+                             n, typeid(T).name());
+  }
+
+  return (T)n;
+}
+
+inline unsigned int readInt(Source& source) {
+  return readNum<unsigned int>(source);
+}
+
+inline uint64_t readLongLong(Source& source) {
+  return readNum<uint64_t>(source);
+}
+
+void readPadding(size_t len, Source& source);
+size_t readString(unsigned char* buf, size_t max, Source& source);
+std::string readString(Source& source,
+                       size_t max = std::numeric_limits<size_t>::max());
+template <class T>
+T readStrings(Source& source);
+
+Source& operator>>(Source& in, std::string& s);
+
+template <typename T>
+Source& operator>>(Source& in, T& n) {
+  n = readNum<T>(in);
+  return in;
+}
+
+template <typename T>
+Source& operator>>(Source& in, bool& b) {
+  b = readNum<uint64_t>(in);
+  return in;
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/status.hh b/third_party/nix/src/libutil/status.hh
new file mode 100644
index 000000000000..aeee0f502257
--- /dev/null
+++ b/third_party/nix/src/libutil/status.hh
@@ -0,0 +1,17 @@
+#pragma once
+
+#include <absl/status/status.h>
+#include <absl/strings/str_format.h>
+#include <absl/strings/string_view.h>
+
+#include "libutil/types.hh"
+
+namespace nix::util {
+
+inline void OkOrThrow(absl::Status status) {
+  if (!status.ok()) {
+    throw Error(absl::StrFormat("Operation failed: %s", status.ToString()));
+  }
+}
+
+}  // namespace nix::util
diff --git a/third_party/nix/src/libutil/sync.hh b/third_party/nix/src/libutil/sync.hh
new file mode 100644
index 000000000000..ef640d5b56ef
--- /dev/null
+++ b/third_party/nix/src/libutil/sync.hh
@@ -0,0 +1,84 @@
+#pragma once
+
+#include <cassert>
+#include <condition_variable>
+#include <cstdlib>
+#include <mutex>
+
+namespace nix {
+
+/* This template class ensures synchronized access to a value of type
+   T. It is used as follows:
+
+     struct Data { int x; ... };
+
+     Sync<Data> data;
+
+     {
+       auto data_(data.lock());
+       data_->x = 123;
+     }
+
+   Here, "data" is automatically unlocked when "data_" goes out of
+   scope.
+*/
+
+template <class T, class M = std::mutex>
+class Sync {
+ private:
+  M mutex;
+  T data;
+
+ public:
+  Sync() {}
+  explicit Sync(const T& data) : data(data) {}
+  explicit Sync(T&& data) noexcept : data(std::move(data)) {}
+
+  class Lock {
+   private:
+    Sync* s;
+    std::unique_lock<M> lk;
+    friend Sync;
+    explicit Lock(Sync* s) : s(s), lk(s->mutex) {}
+
+   public:
+    Lock(Lock&& l) : s(l.s) { abort(); }
+    Lock(const Lock& l) = delete;
+    ~Lock() {}
+    T* operator->() { return &s->data; }
+    T& operator*() { return s->data; }
+
+    void wait(std::condition_variable& cv) {
+      assert(s);
+      cv.wait(lk);
+    }
+
+    template <class Rep, class Period>
+    std::cv_status wait_for(
+        std::condition_variable& cv,
+        const std::chrono::duration<Rep, Period>& duration) {
+      assert(s);
+      return cv.wait_for(lk, duration);
+    }
+
+    template <class Rep, class Period, class Predicate>
+    bool wait_for(std::condition_variable& cv,
+                  const std::chrono::duration<Rep, Period>& duration,
+                  Predicate pred) {
+      assert(s);
+      return cv.wait_for(lk, duration, pred);
+    }
+
+    template <class Clock, class Duration>
+    std::cv_status wait_until(
+        std::condition_variable& cv,
+        const std::chrono::time_point<Clock, Duration>& duration) {
+      assert(s);
+      return cv.wait_until(lk, duration);
+    }
+  };
+
+  Lock lock() { return Lock(this); }
+};
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/thread-pool.cc b/third_party/nix/src/libutil/thread-pool.cc
new file mode 100644
index 000000000000..7c6b0a1b469b
--- /dev/null
+++ b/third_party/nix/src/libutil/thread-pool.cc
@@ -0,0 +1,163 @@
+#include "libutil/thread-pool.hh"
+
+#include <glog/logging.h>
+
+#include "libutil/affinity.hh"
+
+namespace nix {
+
+ThreadPool::ThreadPool(size_t _maxThreads) : maxThreads(_maxThreads) {
+  restoreAffinity();  // FIXME
+
+  if (maxThreads == 0u) {
+    maxThreads = std::thread::hardware_concurrency();
+    if (maxThreads == 0u) {
+      maxThreads = 1;
+    }
+  }
+
+  DLOG(INFO) << "starting pool of " << maxThreads - 1 << " threads";
+}
+
+ThreadPool::~ThreadPool() { shutdown(); }
+
+void ThreadPool::shutdown() {
+  std::vector<std::thread> workers;
+  {
+    auto state(state_.lock());
+    quit = true;
+    std::swap(workers, state->workers);
+  }
+
+  if (workers.empty()) {
+    return;
+  }
+
+  DLOG(INFO) << "reaping " << workers.size() << " worker threads";
+
+  work.notify_all();
+
+  for (auto& thr : workers) {
+    thr.join();
+  }
+}
+
+void ThreadPool::enqueue(const work_t& t) {
+  auto state(state_.lock());
+  if (quit) {
+    throw ThreadPoolShutDown(
+        "cannot enqueue a work item while the thread pool is shutting down");
+  }
+  state->pending.push(t);
+  /* Note: process() also executes items, so count it as a worker. */
+  if (state->pending.size() > state->workers.size() + 1 &&
+      state->workers.size() + 1 < maxThreads) {
+    state->workers.emplace_back(&ThreadPool::doWork, this, false);
+  }
+  work.notify_one();
+}
+
+void ThreadPool::process() {
+  state_.lock()->draining = true;
+
+  /* Do work until no more work is pending or active. */
+  try {
+    doWork(true);
+
+    auto state(state_.lock());
+
+    assert(quit);
+
+    if (state->exception) {
+      std::rethrow_exception(state->exception);
+    }
+
+  } catch (...) {
+    /* In the exceptional case, some workers may still be
+       active. They may be referencing the stack frame of the
+       caller. So wait for them to finish. (~ThreadPool also does
+       this, but it might be destroyed after objects referenced by
+       the work item lambdas.) */
+    shutdown();
+    throw;
+  }
+}
+
+void ThreadPool::doWork(bool mainThread) {
+  if (!mainThread) {
+    interruptCheck = [&]() { return (bool)quit; };
+  }
+
+  bool didWork = false;
+  std::exception_ptr exc;
+
+  while (true) {
+    work_t w;
+    {
+      auto state(state_.lock());
+
+      if (didWork) {
+        assert(state->active);
+        state->active--;
+
+        if (exc) {
+          if (!state->exception) {
+            state->exception = exc;
+            // Tell the other workers to quit.
+            quit = true;
+            work.notify_all();
+          } else {
+            /* Print the exception, since we can't
+               propagate it. */
+            try {
+              std::rethrow_exception(exc);
+            } catch (std::exception& e) {
+              if ((dynamic_cast<Interrupted*>(&e) == nullptr) &&
+                  (dynamic_cast<ThreadPoolShutDown*>(&e) == nullptr)) {
+                ignoreException();
+              }
+            } catch (...) {
+            }
+          }
+        }
+      }
+
+      /* Wait until a work item is available or we're asked to
+         quit. */
+      while (true) {
+        if (quit) {
+          return;
+        }
+
+        if (!state->pending.empty()) {
+          break;
+        }
+
+        /* If there are no active or pending items, and the
+           main thread is running process(), then no new items
+           can be added. So exit. */
+        if ((state->active == 0u) && state->draining) {
+          quit = true;
+          work.notify_all();
+          return;
+        }
+
+        state.wait(work);
+      }
+
+      w = std::move(state->pending.front());
+      state->pending.pop();
+      state->active++;
+    }
+
+    try {
+      w();
+    } catch (...) {
+      exc = std::current_exception();
+    }
+
+    didWork = true;
+  }
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/thread-pool.hh b/third_party/nix/src/libutil/thread-pool.hh
new file mode 100644
index 000000000000..0efc4c1bfc67
--- /dev/null
+++ b/third_party/nix/src/libutil/thread-pool.hh
@@ -0,0 +1,140 @@
+#pragma once
+
+#include <atomic>
+#include <functional>
+#include <map>
+#include <queue>
+#include <thread>
+
+#include "libutil/sync.hh"
+#include "libutil/util.hh"
+
+namespace nix {
+
+MakeError(ThreadPoolShutDown, Error);
+
+/* A simple thread pool that executes a queue of work items
+   (lambdas). */
+class ThreadPool {
+ public:
+  explicit ThreadPool(size_t maxThreads = 0);
+
+  ~ThreadPool();
+
+  // FIXME: use std::packaged_task?
+  typedef std::function<void()> work_t;
+
+  /* Enqueue a function to be executed by the thread pool. */
+  void enqueue(const work_t& t);
+
+  /* Execute work items until the queue is empty. Note that work
+     items are allowed to add new items to the queue; this is
+     handled correctly. Queue processing stops prematurely if any
+     work item throws an exception. This exception is propagated to
+     the calling thread. If multiple work items throw an exception
+     concurrently, only one item is propagated; the others are
+     printed on stderr and otherwise ignored. */
+  void process();
+
+ private:
+  size_t maxThreads;
+
+  struct State {
+    std::queue<work_t> pending;
+    size_t active = 0;
+    std::exception_ptr exception;
+    std::vector<std::thread> workers;
+    bool draining = false;
+  };
+
+  std::atomic_bool quit{false};
+
+  Sync<State> state_;
+
+  std::condition_variable work;
+
+  void doWork(bool mainThread);
+
+  void shutdown();
+};
+
+/* Process in parallel a set of items of type T that have a partial
+   ordering between them. Thus, any item is only processed after all
+   its dependencies have been processed. */
+template <typename T>
+void processGraph(ThreadPool& pool, const std::set<T>& nodes,
+                  std::function<std::set<T>(const T&)> getEdges,
+                  std::function<void(const T&)> processNode) {
+  struct Graph {
+    std::set<T> left;
+    std::map<T, std::set<T>> refs, rrefs;
+  };
+
+  Sync<Graph> graph_(Graph{nodes, {}, {}});
+
+  std::function<void(const T&)> worker;
+
+  worker = [&](const T& node) {
+    {
+      auto graph(graph_.lock());
+      auto i = graph->refs.find(node);
+      if (i == graph->refs.end()) {
+        goto getRefs;
+      }
+      goto doWork;
+    }
+
+  getRefs : {
+    auto refs = getEdges(node);
+    refs.erase(node);
+
+    {
+      auto graph(graph_.lock());
+      for (auto& ref : refs) {
+        if (graph->left.count(ref)) {
+          graph->refs[node].insert(ref);
+          graph->rrefs[ref].insert(node);
+        }
+      }
+      if (graph->refs[node].empty()) {
+        goto doWork;
+      }
+    }
+  }
+
+    return;
+
+  doWork:
+    processNode(node);
+
+    /* Enqueue work for all nodes that were waiting on this one
+       and have no unprocessed dependencies. */
+    {
+      auto graph(graph_.lock());
+      for (auto& rref : graph->rrefs[node]) {
+        auto& refs(graph->refs[rref]);
+        auto i = refs.find(node);
+        assert(i != refs.end());
+        refs.erase(i);
+        if (refs.empty()) {
+          pool.enqueue(std::bind(worker, rref));
+        }
+      }
+      graph->left.erase(node);
+      graph->refs.erase(node);
+      graph->rrefs.erase(node);
+    }
+  };
+
+  for (auto& node : nodes) {
+    pool.enqueue(std::bind(worker, std::ref(node)));
+  }
+
+  pool.process();
+
+  if (!graph_.lock()->left.empty()) {
+    throw Error("graph processing incomplete (cyclic reference?)");
+  }
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/types.hh b/third_party/nix/src/libutil/types.hh
new file mode 100644
index 000000000000..bf95206d0824
--- /dev/null
+++ b/third_party/nix/src/libutil/types.hh
@@ -0,0 +1,118 @@
+#pragma once
+
+#include <boost/format.hpp>
+#include <list>
+#include <map>
+#include <memory>
+#include <set>
+#include <string>
+
+#include "libutil/ref.hh"
+
+/* Before 4.7, gcc's std::exception uses empty throw() specifiers for
+ * its (virtual) destructor and what() in c++11 mode, in violation of spec
+ */
+#ifdef __GNUC__
+#if __GNUC__ < 4 || (__GNUC__ == 4 && __GNUC_MINOR__ < 7)
+#define EXCEPTION_NEEDS_THROW_SPEC
+#endif
+#endif
+
+namespace nix {
+
+/* Inherit some names from other namespaces for convenience. */
+using boost::format;
+
+/* A variadic template that does nothing. Useful to call a function
+   for all variadic arguments but ignoring the result. */
+struct nop {
+  template <typename... T>
+  explicit nop(T...) {}
+};
+
+struct FormatOrString {
+  std::string s;
+  FormatOrString(const std::string& s) : s(s){};
+  FormatOrString(const format& f) : s(f.str()){};
+  FormatOrString(const char* s) : s(s){};
+};
+
+/* A helper for formatting strings. โ€˜fmt(format, a_0, ..., a_n)โ€™ is
+   equivalent to โ€˜boost::format(format) % a_0 % ... %
+   ... a_nโ€™. However, โ€˜fmt(s)โ€™ is equivalent to โ€˜sโ€™ (so no %-expansion
+   takes place). */
+
+inline std::string fmt(const std::string& s) { return s; }
+
+inline std::string fmt(std::string_view s) { return std::string(s); }
+
+inline std::string fmt(const char* s) { return s; }
+
+inline std::string fmt(const FormatOrString& fs) { return fs.s; }
+
+template <typename... Args>
+inline std::string fmt(const std::string& fs, Args... args) {
+  boost::format f(fs);
+  f.exceptions(boost::io::all_error_bits ^ boost::io::too_many_args_bit);
+  nop{boost::io::detail::feed(f, args)...};
+  return f.str();
+}
+
+/* BaseError should generally not be caught, as it has Interrupted as
+   a subclass. Catch Error instead. */
+class BaseError : public std::exception {
+ protected:
+  std::string prefix_;  // used for location traces etc.
+  std::string err;
+
+ public:
+  unsigned int status = 1;  // exit status
+
+  template <typename... Args>
+  explicit BaseError(unsigned int status, Args... args)
+      : err(fmt(args...)), status(status) {}
+
+  template <typename... Args>
+  explicit BaseError(Args... args) : err(fmt(args...)) {}
+
+#ifdef EXCEPTION_NEEDS_THROW_SPEC
+  ~BaseError() noexcept {};
+  const char* what() const noexcept { return err.c_str(); }
+#else
+  const char* what() const noexcept { return err.c_str(); }
+#endif
+
+  const std::string& msg() const { return err; }
+  const std::string& prefix() const { return prefix_; }
+  BaseError& addPrefix(const FormatOrString& fs);
+};
+
+#define MakeError(newClass, superClass) \
+  class newClass : public superClass {  \
+   public:                              \
+    using superClass::superClass;       \
+  };
+
+MakeError(Error, BaseError);
+
+class SysError : public Error {
+ public:
+  int errNo;
+
+  template <typename... Args>
+  explicit SysError(Args... args) : Error(addErrno(fmt(args...))) {}
+
+ private:
+  std::string addErrno(const std::string& s);
+};
+
+typedef std::list<std::string> Strings;
+using StringSet = std::set<std::string>;
+using StringMap = std::map<std::string, std::string>;
+
+/* Paths are just strings. */
+using Path = std::string;
+using Paths = std::list<Path>;
+using PathSet = std::set<Path>;
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/util.cc b/third_party/nix/src/libutil/util.cc
new file mode 100644
index 000000000000..aea1e68e3c77
--- /dev/null
+++ b/third_party/nix/src/libutil/util.cc
@@ -0,0 +1,1426 @@
+#include "libutil/util.hh"
+
+#include <cctype>
+#include <cerrno>
+#include <climits>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+#include <future>
+#include <iostream>
+#include <sstream>
+#include <thread>
+#include <utility>
+
+#include <absl/strings/str_split.h>
+#include <absl/strings/string_view.h>
+#include <fcntl.h>
+#include <glog/logging.h>
+#include <grp.h>
+#include <pwd.h>
+#include <sys/ioctl.h>
+#include <sys/prctl.h>
+#include <sys/types.h>
+#include <sys/wait.h>
+#include <unistd.h>
+
+#include "libutil/affinity.hh"
+#include "libutil/finally.hh"
+#include "libutil/lazy.hh"
+#include "libutil/serialise.hh"
+#include "libutil/sync.hh"
+#include "nix_config.h"
+
+namespace nix {
+
+const std::string nativeSystem = SYSTEM;
+
+BaseError& BaseError::addPrefix(const FormatOrString& fs) {
+  prefix_ = fs.s + prefix_;
+  return *this;
+}
+
+std::string SysError::addErrno(const std::string& s) {
+  errNo = errno;
+  return s + ": " + strerror(errNo);
+}
+
+std::optional<std::string> getEnv(const std::string& key) {
+  char* value = getenv(key.c_str());
+  if (value == nullptr) return {};
+  return std::string(value);
+}
+
+std::map<std::string, std::string> getEnv() {
+  std::map<std::string, std::string> env;
+  for (size_t i = 0; environ[i] != nullptr; ++i) {
+    auto s = environ[i];
+    auto eq = strchr(s, '=');
+    if (eq == nullptr) {
+      // invalid env, just keep going
+      continue;
+    }
+    env.emplace(std::string(s, eq), std::string(eq + 1));
+  }
+  return env;
+}
+
+void clearEnv() {
+  for (auto& name : getEnv()) {
+    unsetenv(name.first.c_str());
+  }
+}
+
+void replaceEnv(const std::map<std::string, std::string>& newEnv) {
+  clearEnv();
+  for (const auto& newEnvVar : newEnv) {
+    setenv(newEnvVar.first.c_str(), newEnvVar.second.c_str(), 1);
+  }
+}
+
+Path absPath(Path path, Path dir) {
+  if (path[0] != '/') {
+    if (dir.empty()) {
+#ifdef __GNU__
+      /* GNU (aka. GNU/Hurd) doesn't have any limitation on path
+         lengths and doesn't define `PATH_MAX'.  */
+      char* buf = getcwd(NULL, 0);
+      if (buf == NULL)
+#else
+      char buf[PATH_MAX];
+      if (getcwd(buf, sizeof(buf)) == nullptr) {
+#endif
+        throw SysError("cannot get cwd");
+    }
+    dir = buf;
+#ifdef __GNU__
+    free(buf);
+#endif
+  }
+  path = dir + "/" + path;
+}
+return canonPath(path);
+}  // namespace nix
+
+Path canonPath(const Path& path, bool resolveSymlinks) {
+  assert(!path.empty());
+
+  std::string s;
+
+  if (path[0] != '/') {
+    throw Error(format("not an absolute path: '%1%'") % path);
+  }
+
+  std::string::const_iterator i = path.begin();
+  std::string::const_iterator end = path.end();
+  std::string temp;
+
+  /* Count the number of times we follow a symlink and stop at some
+     arbitrary (but high) limit to prevent infinite loops. */
+  unsigned int followCount = 0;
+  unsigned int maxFollow = 1024;
+
+  while (true) {
+    /* Skip slashes. */
+    while (i != end && *i == '/') {
+      i++;
+    }
+    if (i == end) {
+      break;
+    }
+
+    /* Ignore `.'. */
+    if (*i == '.' && (i + 1 == end || i[1] == '/')) {
+      i++;
+    }
+
+    /* If `..', delete the last component. */
+    else if (*i == '.' && i + 1 < end && i[1] == '.' &&
+             (i + 2 == end || i[2] == '/')) {
+      if (!s.empty()) {
+        s.erase(s.rfind('/'));
+      }
+      i += 2;
+    }
+
+    /* Normal component; copy it. */
+    else {
+      s += '/';
+      while (i != end && *i != '/') {
+        s += *i++;
+      }
+
+      /* If s points to a symlink, resolve it and restart (since
+         the symlink target might contain new symlinks). */
+      if (resolveSymlinks && isLink(s)) {
+        if (++followCount >= maxFollow) {
+          throw Error(format("infinite symlink recursion in path '%1%'") %
+                      path);
+        }
+        temp = absPath(readLink(s), dirOf(s)) + std::string(i, end);
+        i = temp.begin(); /* restart */
+        end = temp.end();
+        s = "";
+      }
+    }
+  }
+
+  return s.empty() ? "/" : s;
+}
+
+// TODO(grfn) remove in favor of std::filesystem::path::parent_path()
+Path dirOf(absl::string_view path) {
+  Path::size_type pos = path.rfind('/');
+  if (pos == std::string::npos) {
+    return ".";
+  }
+  return pos == 0 ? "/" : Path(path, 0, pos);
+}
+
+// TODO(grfn) remove in favor of std::filesystem::path::root_name()
+std::string baseNameOf(const Path& path) {
+  if (path.empty()) {
+    return "";
+  }
+
+  Path::size_type last = path.length() - 1;
+  if (path[last] == '/' && last > 0) {
+    last -= 1;
+  }
+
+  Path::size_type pos = path.rfind('/', last);
+  if (pos == std::string::npos) {
+    pos = 0;
+  } else {
+    pos += 1;
+  }
+
+  return std::string(path, pos, last - pos + 1);
+}
+
+bool isInDir(const Path& path, const Path& dir) {
+  return path[0] == '/' && std::string(path, 0, dir.size()) == dir &&
+         path.size() >= dir.size() + 2 && path[dir.size()] == '/';
+}
+
+bool isDirOrInDir(const Path& path, const Path& dir) {
+  return path == dir || isInDir(path, dir);
+}
+
+struct stat lstat(const Path& path) {
+  struct stat st;
+  if (lstat(path.c_str(), &st) != 0) {
+    throw SysError(format("getting status of '%1%'") % path);
+  }
+  return st;
+}
+
+bool pathExists(const Path& path) {
+  int res;
+  struct stat st;
+  res = lstat(path.c_str(), &st);
+  if (res == 0) {
+    return true;
+  }
+  if (errno != ENOENT && errno != ENOTDIR) {
+    throw SysError(format("getting status of %1%") % path);
+  }
+  return false;
+}
+
+Path readLink(const Path& path) {
+  checkInterrupt();
+  std::vector<char> buf;
+  for (ssize_t bufSize = PATH_MAX / 4; true; bufSize += bufSize / 2) {
+    buf.resize(bufSize);
+    ssize_t rlSize = readlink(path.c_str(), buf.data(), bufSize);
+    if (rlSize == -1) {
+      if (errno == EINVAL) {
+        throw Error("'%1%' is not a symlink", path);
+      }
+      throw SysError("reading symbolic link '%1%'", path);
+
+    } else if (rlSize < bufSize) {
+      return std::string(buf.data(), rlSize);
+    }
+  }
+}
+
+bool isLink(const Path& path) {
+  struct stat st = lstat(path);
+  return S_ISLNK(st.st_mode);
+}
+
+DirEntries readDirectory(DIR* dir, const Path& path) {
+  DirEntries entries;
+  entries.reserve(64);
+
+  struct dirent* dirent;
+  while (errno = 0, dirent = readdir(dir)) { /* sic */
+    checkInterrupt();
+    std::string name = dirent->d_name;
+    if (name == "." || name == "..") {
+      continue;
+    }
+    entries.emplace_back(name, dirent->d_ino,
+#ifdef HAVE_STRUCT_DIRENT_D_TYPE
+                         dirent->d_type
+#else
+                         DT_UNKNOWN
+#endif
+    );
+  }
+  if (errno) {
+    throw SysError(format("reading directory '%1%'") % path);
+  }
+
+  return entries;
+}
+
+DirEntries readDirectory(const Path& path) {
+  AutoCloseDir dir(opendir(path.c_str()));
+  if (!dir) {
+    throw SysError(format("opening directory '%1%'") % path);
+  }
+
+  return readDirectory(dir.get(), path);
+}
+
+unsigned char getFileType(const Path& path) {
+  struct stat st = lstat(path);
+  if (S_ISDIR(st.st_mode)) {
+    return DT_DIR;
+  }
+  if (S_ISLNK(st.st_mode)) {
+    return DT_LNK;
+  }
+  if (S_ISREG(st.st_mode)) {
+    return DT_REG;
+  }
+  return DT_UNKNOWN;
+}
+
+std::string readFile(int fd) {
+  struct stat st;
+  if (fstat(fd, &st) == -1) {
+    throw SysError("statting file");
+  }
+
+  std::vector<unsigned char> buf(st.st_size);
+  readFull(fd, buf.data(), st.st_size);
+
+  return std::string(reinterpret_cast<char*>(buf.data()), st.st_size);
+}
+
+std::string readFile(absl::string_view path, bool drain) {
+  AutoCloseFD fd(open(std::string(path).c_str(), O_RDONLY | O_CLOEXEC));
+  if (!fd) {
+    throw SysError(format("opening file '%1%'") % path);
+  }
+  return drain ? drainFD(fd.get()) : readFile(fd.get());
+}
+
+void readFile(absl::string_view path, Sink& sink) {
+  // TODO(tazjin): use stdlib functions for this stuff
+  AutoCloseFD fd(open(std::string(path).c_str(), O_RDONLY | O_CLOEXEC));
+  if (!fd) {
+    throw SysError("opening file '%s'", path);
+  }
+  drainFD(fd.get(), sink);
+}
+
+void writeFile(const Path& path, const std::string& s, mode_t mode) {
+  AutoCloseFD fd(
+      open(path.c_str(), O_WRONLY | O_TRUNC | O_CREAT | O_CLOEXEC, mode));
+  if (!fd) {
+    throw SysError(format("opening file '%1%'") % path);
+  }
+  writeFull(fd.get(), s);
+}
+
+void writeFile(const Path& path, Source& source, mode_t mode) {
+  AutoCloseFD fd(
+      open(path.c_str(), O_WRONLY | O_TRUNC | O_CREAT | O_CLOEXEC, mode));
+  if (!fd) {
+    throw SysError(format("opening file '%1%'") % path);
+  }
+
+  std::vector<unsigned char> buf(64 * 1024);
+
+  while (true) {
+    try {
+      auto n = source.read(buf.data(), buf.size());
+      writeFull(fd.get(), static_cast<unsigned char*>(buf.data()), n);
+    } catch (EndOfFile&) {
+      break;
+    }
+  }
+}
+
+std::string readLine(int fd) {
+  std::string s;
+  while (true) {
+    checkInterrupt();
+    char ch;
+    // FIXME: inefficient
+    ssize_t rd = read(fd, &ch, 1);
+    if (rd == -1) {
+      if (errno != EINTR) {
+        throw SysError("reading a line");
+      }
+    } else if (rd == 0) {
+      throw EndOfFile("unexpected EOF reading a line");
+    } else {
+      if (ch == '\n') {
+        return s;
+      }
+      s += ch;
+    }
+  }
+}
+
+void writeLine(int fd, std::string s) {
+  s += '\n';
+  writeFull(fd, s);
+}
+
+static void _deletePath(int parentfd, const Path& path,
+                        unsigned long long& bytesFreed) {
+  checkInterrupt();
+
+  std::string name(baseNameOf(path));
+
+  struct stat st;
+  if (fstatat(parentfd, name.c_str(), &st, AT_SYMLINK_NOFOLLOW) == -1) {
+    if (errno == ENOENT) {
+      return;
+    }
+    throw SysError(format("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)) {
+    /* Make the directory accessible. */
+    const auto PERM_MASK = S_IRUSR | S_IWUSR | S_IXUSR;
+    if ((st.st_mode & PERM_MASK) != PERM_MASK) {
+      if (fchmodat(parentfd, name.c_str(), st.st_mode | PERM_MASK, 0) == -1) {
+        throw SysError(format("chmod '%1%'") % path);
+      }
+    }
+
+    int fd = openat(parentfd, path.c_str(), O_RDONLY);
+    if (!fd) {
+      throw SysError(format("opening directory '%1%'") % path);
+    }
+    AutoCloseDir dir(fdopendir(fd));
+    if (!dir) {
+      throw SysError(format("opening directory '%1%'") % path);
+    }
+    for (auto& i : readDirectory(dir.get(), path)) {
+      _deletePath(dirfd(dir.get()), path + "/" + i.name, bytesFreed);
+    }
+  }
+
+  int flags = S_ISDIR(st.st_mode) ? AT_REMOVEDIR : 0;
+  if (unlinkat(parentfd, name.c_str(), flags) == -1) {
+    if (errno == ENOENT) {
+      return;
+    }
+    throw SysError(format("cannot unlink '%1%'") % path);
+  }
+}
+
+static void _deletePath(const Path& path, unsigned long long& bytesFreed) {
+  Path dir = dirOf(path);
+  if (dir == "") {
+    dir = "/";
+  }
+
+  AutoCloseFD dirfd(open(dir.c_str(), O_RDONLY));
+  if (!dirfd) {
+    // This really shouldn't fail silently, but it's left this way
+    // for backwards compatibility.
+    if (errno == ENOENT) {
+      return;
+    }
+
+    throw SysError(format("opening directory '%1%'") % path);
+  }
+
+  _deletePath(dirfd.get(), path, bytesFreed);
+}
+
+void deletePath(const Path& path) {
+  unsigned long long dummy;
+  deletePath(path, dummy);
+}
+
+void deletePath(const Path& path, unsigned long long& bytesFreed) {
+  // Activity act(*logger, lvlDebug, format("recursively deleting path '%1%'") %
+  // path);
+  bytesFreed = 0;
+  _deletePath(path, 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();
+  }
+  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 (true) {
+    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(format("setting group of directory '%1%'") % tmpDir);
+#endif
+      return tmpDir;
+    }
+    if (errno != EEXIST) {
+      throw SysError(format("creating directory '%1%'") % tmpDir);
+    }
+  }
+}
+
+std::string getUserName() {
+  auto pw = getpwuid(geteuid());
+  std::optional<std::string> name =
+      pw != nullptr ? pw->pw_name : getEnv("USER");
+  if (!name.has_value()) {
+    throw Error("cannot figure out user name");
+  }
+  return *name;
+}
+
+static Lazy<Path> getHome2([]() {
+  std::optional<Path> homeDir = getEnv("HOME");
+  if (!homeDir) {
+    std::vector<char> buf(16384);
+    struct passwd pwbuf;
+    struct passwd* pw;
+    if (getpwuid_r(geteuid(), &pwbuf, buf.data(), buf.size(), &pw) != 0 ||
+        (pw == nullptr) || (pw->pw_dir == nullptr) || (pw->pw_dir[0] == 0)) {
+      throw Error("cannot determine user's home directory");
+    }
+    return std::string(pw->pw_dir);
+  }
+  return homeDir.value();
+});
+
+Path getHome() { return getHome2(); }
+
+Path getCacheDir() {
+  return getEnv("XDG_CACHE_HOME").value_or(getHome() + "/.cache");
+}
+
+Path getConfigDir() {
+  return getEnv("XDG_CONFIG_HOME").value_or(getHome() + "/.config");
+}
+
+std::vector<Path> getConfigDirs() {
+  Path configHome = getConfigDir();
+  std::string configDirs = getEnv("XDG_CONFIG_DIRS").value_or("");
+  std::vector<std::string> result =
+      absl::StrSplit(configDirs, absl::ByChar(':'), absl::SkipEmpty());
+  result.insert(result.begin(), configHome);
+  return result;
+}
+
+Path getDataDir() {
+  return getEnv("XDG_DATA_HOME").value_or(getHome() + "/.local/share");
+}
+
+// TODO(grfn): Remove in favor of std::filesystem::create_directories
+Paths createDirs(const Path& path) {
+  Paths created;
+  if (path == "/") {
+    return created;
+  }
+
+  struct stat st;
+  if (lstat(path.c_str(), &st) == -1) {
+    created = createDirs(dirOf(path));
+    if (mkdir(path.c_str(), 0777) == -1 && errno != EEXIST) {
+      throw SysError(format("creating directory '%1%'") % path);
+    }
+    st = lstat(path);
+    created.push_back(path);
+  }
+
+  if (S_ISLNK(st.st_mode) && stat(path.c_str(), &st) == -1) {
+    throw SysError(format("statting symlink '%1%'") % path);
+  }
+
+  if (!S_ISDIR(st.st_mode)) {
+    throw Error(format("'%1%' is not a directory") % path);
+  }
+
+  return created;
+}
+
+void createSymlink(const Path& target, const Path& link) {
+  if (symlink(target.c_str(), link.c_str()) != 0) {
+    throw SysError(format("creating symlink from '%1%' to '%2%'") % link %
+                   target);
+  }
+}
+
+void replaceSymlink(const Path& target, const Path& link) {
+  for (unsigned int n = 0; true; n++) {
+    Path tmp = canonPath(fmt("%s/.%d_%s", dirOf(link), n, baseNameOf(link)));
+
+    try {
+      createSymlink(target, tmp);
+    } catch (SysError& e) {
+      if (e.errNo == EEXIST) {
+        continue;
+      }
+      throw;
+    }
+
+    if (rename(tmp.c_str(), link.c_str()) != 0) {
+      throw SysError(format("renaming '%1%' to '%2%'") % tmp % link);
+    }
+
+    break;
+  }
+}
+
+void readFull(int fd, unsigned char* buf, size_t count) {
+  while (count != 0u) {
+    checkInterrupt();
+    ssize_t res = read(fd, reinterpret_cast<char*>(buf), count);
+    if (res == -1) {
+      if (errno == EINTR) {
+        continue;
+      }
+      throw SysError("reading from file");
+    }
+    if (res == 0) {
+      throw EndOfFile("unexpected end-of-file");
+    }
+    count -= res;
+    buf += res;
+  }
+}
+
+void writeFull(int fd, const unsigned char* buf, size_t count,
+               bool allowInterrupts) {
+  while (count != 0u) {
+    if (allowInterrupts) {
+      checkInterrupt();
+    }
+    ssize_t res = write(fd, (char*)buf, count);
+    if (res == -1 && errno != EINTR) {
+      throw SysError("writing to file");
+    }
+    if (res > 0) {
+      count -= res;
+      buf += res;
+    }
+  }
+}
+
+void writeFull(int fd, const std::string& s, bool allowInterrupts) {
+  writeFull(fd, reinterpret_cast<const unsigned char*>(s.data()), s.size(),
+            allowInterrupts);
+}
+
+std::string drainFD(int fd, bool block) {
+  StringSink sink;
+  drainFD(fd, sink, block);
+  return std::move(*sink.s);
+}
+
+void drainFD(int fd, Sink& sink, bool block) {
+  int saved;
+
+  Finally finally([&]() {
+    if (!block) {
+      if (fcntl(fd, F_SETFL, saved) == -1) {
+        throw SysError("making file descriptor blocking");
+      }
+    }
+  });
+
+  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 (true) {
+    checkInterrupt();
+    ssize_t rd = read(fd, buf.data(), buf.size());
+    if (rd == -1) {
+      if (!block && (errno == EAGAIN || errno == EWOULDBLOCK)) {
+        break;
+      }
+      if (errno != EINTR) {
+        throw SysError("reading from file");
+      }
+    } else if (rd == 0) {
+      break;
+    } else {
+      sink(buf.data(), rd);
+    }
+  }
+}
+
+//////////////////////////////////////////////////////////////////////
+
+AutoDelete::AutoDelete() : del{false} {}
+
+AutoDelete::AutoDelete(std::string p, bool recursive) : path(std::move(p)) {
+  del = true;
+  this->recursive = recursive;
+}
+
+AutoDelete::~AutoDelete() {
+  try {
+    if (del) {
+      if (recursive) {
+        deletePath(path);
+      } else {
+        if (remove(path.c_str()) == -1) {
+          throw SysError(format("cannot unlink '%1%'") % path);
+        }
+      }
+    }
+  } catch (...) {
+    ignoreException();
+  }
+}
+
+void AutoDelete::cancel() { del = false; }
+
+void AutoDelete::reset(const Path& p, bool recursive) {
+  path = p;
+  this->recursive = recursive;
+  del = true;
+}
+
+//////////////////////////////////////////////////////////////////////
+
+AutoCloseFD::AutoCloseFD() : fd{-1} {}
+
+AutoCloseFD::AutoCloseFD(int fd) : fd{fd} {}
+
+AutoCloseFD::AutoCloseFD(AutoCloseFD&& that) : fd{that.fd} { that.fd = -1; }
+
+AutoCloseFD& AutoCloseFD::operator=(AutoCloseFD&& that) {
+  close();
+  fd = that.fd;
+  that.fd = -1;
+  return *this;
+}
+
+AutoCloseFD::~AutoCloseFD() {
+  try {
+    close();
+  } catch (...) {
+    ignoreException();
+  }
+}
+
+int AutoCloseFD::get() const { return fd; }
+
+void AutoCloseFD::close() {
+  if (fd != -1) {
+    if (::close(fd) == -1) { /* This should never happen. */
+      throw SysError(format("closing file descriptor %1%") % fd);
+    }
+  }
+}
+
+AutoCloseFD::operator bool() const { return fd != -1; }
+
+int AutoCloseFD::release() {
+  int oldFD = fd;
+  fd = -1;
+  return oldFD;
+}
+
+void Pipe::create() {
+  int fds[2];
+#if HAVE_PIPE2
+  if (pipe2(fds, O_CLOEXEC) != 0) {
+    throw SysError("creating pipe");
+  }
+#else
+  if (pipe(fds) != 0) {
+    throw SysError("creating pipe");
+  }
+  closeOnExec(fds[0]);
+  closeOnExec(fds[1]);
+#endif
+  readSide = AutoCloseFD(fds[0]);
+  writeSide = AutoCloseFD(fds[1]);
+}
+
+//////////////////////////////////////////////////////////////////////
+
+Pid::Pid() = default;
+
+Pid::Pid(pid_t pid) : pid(pid) {}
+
+Pid::~Pid() {
+  if (pid != -1) {
+    kill();
+  }
+}
+
+void Pid::operator=(pid_t pid) {
+  if (this->pid != -1 && this->pid != pid) {
+    kill();
+  }
+  this->pid = pid;
+  killSignal = SIGKILL;  // reset signal to default
+}
+
+Pid::operator pid_t() { return pid; }
+
+int Pid::kill() {
+  assert(pid != -1);
+
+  DLOG(INFO) << "killing process " << pid;
+
+  /* Send the requested signal to the child.  If it has its own
+     process group, send the signal to every process in the child
+     process group (which hopefully includes *all* its children). */
+  if (::kill(separatePG ? -pid : pid, killSignal) != 0) {
+    LOG(ERROR) << SysError("killing process %d", pid).msg();
+  }
+
+  return wait();
+}
+
+int Pid::wait() {
+  assert(pid != -1);
+  while (true) {
+    int status;
+    int res = waitpid(pid, &status, 0);
+    if (res == pid) {
+      pid = -1;
+      return status;
+    }
+    if (errno != EINTR) {
+      throw SysError("cannot get child exit status");
+    }
+    checkInterrupt();
+  }
+}
+
+void Pid::setSeparatePG(bool separatePG) { this->separatePG = separatePG; }
+
+void Pid::setKillSignal(int signal) { this->killSignal = signal; }
+
+pid_t Pid::release() {
+  pid_t p = pid;
+  pid = -1;
+  return p;
+}
+
+void killUser(uid_t uid) {
+  DLOG(INFO) << "killing all processes running under UID " << uid;
+
+  assert(uid != 0); /* just to be safe... */
+
+  /* The system call kill(-1, sig) sends the signal `sig' to all
+     users to which the current process can send signals.  So we
+     fork a process, switch to uid, and send a mass kill. */
+
+  ProcessOptions options;
+
+  Pid pid(startProcess(
+      [&]() {
+        if (setuid(uid) == -1) {
+          throw SysError("setting uid");
+        }
+
+        while (true) {
+          if (kill(-1, SIGKILL) == 0) {
+            break;
+          }
+          if (errno == ESRCH) {
+            break;
+          } /* no more processes */
+          if (errno != EINTR) {
+            throw SysError(format("cannot kill processes for uid '%1%'") % uid);
+          }
+        }
+
+        _exit(0);
+      },
+      options));
+
+  int status = pid.wait();
+  if (status != 0) {
+    throw Error(format("cannot kill processes for uid '%1%': %2%") % uid %
+                statusToString(status));
+  }
+
+  /* !!! We should really do some check to make sure that there are
+     no processes left running under `uid', but there is no portable
+     way to do so (I think).  The most reliable way may be `ps -eo
+     uid | grep -q $uid'. */
+}
+
+//////////////////////////////////////////////////////////////////////
+
+/*
+ * Please note that it is not legal for this function to call vfork().  If the
+ * process created by vfork() returns from the function in which vfork() was
+ * called, or calls any other function before successfully calling _exit() or
+ * one of the exec*() family of functions, the behavior is undefined.
+ */
+static pid_t doFork(const std::function<void()>& fun) __attribute__((noinline));
+static pid_t doFork(const std::function<void()>& fun) {
+#ifdef __linux__
+  // TODO(kanepyork): call clone() instead for faster forking
+#endif
+
+  pid_t pid = fork();
+  if (pid != 0) {
+    return pid;
+  }
+  fun();
+  abort();
+}
+
+pid_t startProcess(std::function<void()> fun, const ProcessOptions& options) {
+  auto wrapper = [&]() {
+    try {
+#if __linux__
+      if (options.dieWithParent && prctl(PR_SET_PDEATHSIG, SIGKILL) == -1) {
+        throw SysError("setting death signal");
+      }
+#endif
+      restoreAffinity();
+      fun();
+    } catch (std::exception& e) {
+      try {
+        LOG(ERROR) << options.errorPrefix << e.what();
+      } catch (...) {
+      }
+    } catch (...) {
+    }
+    if (options.runExitHandlers) {
+      exit(1);
+    } else {
+      _exit(1);
+    }
+  };
+
+  pid_t pid = doFork(wrapper);
+  if (pid == -1) {
+    throw SysError("unable to fork");
+  }
+
+  return pid;
+}
+
+std::vector<char*> stringsToCharPtrs(const Strings& ss) {
+  std::vector<char*> res;
+  for (auto& s : ss) {
+    res.push_back(const_cast<char*>(s.c_str()));
+  }
+  res.push_back(nullptr);
+  return res;
+}
+
+std::string runProgram(const Path& program, bool searchPath,
+                       const Strings& args,
+                       const std::optional<std::string>& input) {
+  RunOptions opts(program, args);
+  opts.searchPath = searchPath;
+  opts.input = input;
+
+  auto res = runProgram(opts);
+
+  if (!statusOk(res.first)) {
+    throw ExecError(res.first, fmt("program '%1%' %2%", program,
+                                   statusToString(res.first)));
+  }
+
+  return res.second;
+}
+
+std::pair<int, std::string> runProgram(const RunOptions& options_) {
+  RunOptions options(options_);
+  StringSink sink;
+  options.standardOut = &sink;
+
+  int status = 0;
+
+  try {
+    runProgram2(options);
+  } catch (ExecError& e) {
+    status = e.status;
+  }
+
+  return {status, std::move(*sink.s)};
+}
+
+void runProgram2(const RunOptions& options) {
+  checkInterrupt();
+
+  assert(!(options.standardIn && options.input));
+
+  std::unique_ptr<Source> source_;
+  Source* source = options.standardIn;
+
+  if (options.input) {
+    source_ = std::make_unique<StringSource>(*options.input);
+    source = source_.get();
+  }
+
+  /* Create a pipe. */
+  Pipe out;
+  Pipe in;
+  if (options.standardOut != nullptr) {
+    out.create();
+  }
+  if (source != nullptr) {
+    in.create();
+  }
+
+  ProcessOptions processOptions;
+
+  /* Fork. */
+  Pid pid(startProcess(
+      [&]() {
+        if (options.environment) {
+          replaceEnv(*options.environment);
+        }
+        if ((options.standardOut != nullptr) &&
+            dup2(out.writeSide.get(), STDOUT_FILENO) == -1) {
+          throw SysError("dupping stdout");
+        }
+        if (options.mergeStderrToStdout) {
+          if (dup2(STDOUT_FILENO, STDERR_FILENO) == -1) {
+            throw SysError("cannot dup stdout into stderr");
+          }
+        }
+        if ((source != nullptr) &&
+            dup2(in.readSide.get(), STDIN_FILENO) == -1) {
+          throw SysError("dupping stdin");
+        }
+
+        if (options.chdir && chdir((*options.chdir).c_str()) == -1) {
+          throw SysError("chdir failed");
+        }
+        if (options.gid && setgid(*options.gid) == -1) {
+          throw SysError("setgid failed");
+        }
+        /* Drop all other groups if we're setgid. */
+        if (options.gid && setgroups(0, nullptr) == -1) {
+          throw SysError("setgroups failed");
+        }
+        if (options.uid && setuid(*options.uid) == -1) {
+          throw SysError("setuid failed");
+        }
+
+        Strings args_(options.args);
+        args_.push_front(options.program);
+
+        restoreSignals();
+
+        if (options.searchPath) {
+          execvp(options.program.c_str(), stringsToCharPtrs(args_).data());
+        } else {
+          execv(options.program.c_str(), stringsToCharPtrs(args_).data());
+        }
+
+        throw SysError("executing '%1%'", options.program);
+      },
+      processOptions));
+
+  out.writeSide = AutoCloseFD(-1);
+
+  std::thread writerThread;
+
+  std::promise<void> promise;
+
+  Finally doJoin([&]() {
+    if (writerThread.joinable()) {
+      writerThread.join();
+    }
+  });
+
+  if (source != nullptr) {
+    in.readSide = AutoCloseFD(-1);
+    writerThread = std::thread([&]() {
+      try {
+        std::vector<unsigned char> buf(8 * 1024);
+        while (true) {
+          size_t n;
+          try {
+            n = source->read(buf.data(), buf.size());
+          } catch (EndOfFile&) {
+            break;
+          }
+          writeFull(in.writeSide.get(), buf.data(), n);
+        }
+        promise.set_value();
+      } catch (...) {
+        promise.set_exception(std::current_exception());
+      }
+      in.writeSide = AutoCloseFD(-1);
+    });
+  }
+
+  if (options.standardOut != nullptr) {
+    drainFD(out.readSide.get(), *options.standardOut);
+  }
+
+  /* Wait for the child to finish. */
+  int status = pid.wait();
+
+  /* Wait for the writer thread to finish. */
+  if (source != nullptr) {
+    promise.get_future().get();
+  }
+
+  if (status != 0) {
+    throw ExecError(status, fmt("program '%1%' %2%", options.program,
+                                statusToString(status)));
+  }
+}
+
+void closeMostFDs(const std::set<int>& exceptions) {
+#if __linux__
+  try {
+    for (auto& s : readDirectory("/proc/self/fd")) {
+      auto fd = std::stoi(s.name);
+      if (exceptions.count(fd) == 0u) {
+        DLOG(INFO) << "closing leaked FD " << fd;
+        close(fd);
+      }
+    }
+    return;
+  } catch (SysError&) {
+  }
+#endif
+
+  int maxFD = 0;
+  maxFD = sysconf(_SC_OPEN_MAX);
+  for (int fd = 0; fd < maxFD; ++fd) {
+    if (exceptions.count(fd) == 0u) {
+      close(fd);
+    } /* ignore result */
+  }
+}
+
+void closeOnExec(int fd) {
+  int prev;
+  if ((prev = fcntl(fd, F_GETFD, 0)) == -1 ||
+      fcntl(fd, F_SETFD, prev | FD_CLOEXEC) == -1) {
+    throw SysError("setting close-on-exec flag");
+  }
+}
+
+//////////////////////////////////////////////////////////////////////
+
+bool _isInterrupted = false;
+
+static thread_local bool interruptThrown = false;
+thread_local std::function<bool()> interruptCheck;
+
+void setInterruptThrown() { interruptThrown = true; }
+
+void _interrupted() {
+  /* Block user interrupts while an exception is being handled.
+     Throwing an exception while another exception is being handled
+     kills the program! */
+  if (!interruptThrown && (std::uncaught_exceptions() == 0)) {
+    interruptThrown = true;
+    throw Interrupted("interrupted by the user");
+  }
+}
+
+//////////////////////////////////////////////////////////////////////
+
+std::string concatStringsSep(const std::string& sep, const Strings& ss) {
+  std::string s;
+  for (auto& i : ss) {
+    if (!s.empty()) {
+      s += sep;
+    }
+    s += i;
+  }
+  return s;
+}
+
+std::string concatStringsSep(const std::string& sep, const StringSet& ss) {
+  std::string s;
+  for (auto& i : ss) {
+    if (!s.empty()) {
+      s += sep;
+    }
+    s += i;
+  }
+  return s;
+}
+
+std::string replaceStrings(const std::string& s, const std::string& from,
+                           const std::string& to) {
+  if (from.empty()) {
+    return s;
+  }
+  std::string res = s;
+  size_t pos = 0;
+  while ((pos = res.find(from, pos)) != std::string::npos) {
+    res.replace(pos, from.size(), to);
+    pos += to.size();
+  }
+  return res;
+}
+
+std::string statusToString(int status) {
+  if (!WIFEXITED(status) || WEXITSTATUS(status) != 0) {
+    if (WIFEXITED(status)) {
+      return (format("failed with exit code %1%") % WEXITSTATUS(status)).str();
+    }
+    if (WIFSIGNALED(status)) {
+      int sig = WTERMSIG(status);
+#if HAVE_STRSIGNAL
+      const char* description = strsignal(sig);
+      return (format("failed due to signal %1% (%2%)") % sig % description)
+          .str();
+#else
+      return (format("failed due to signal %1%") % sig).str();
+#endif
+    } else {
+      return "died abnormally";
+    }
+  } else {
+    return "succeeded";
+  }
+}
+
+bool statusOk(int status) {
+  return WIFEXITED(status) && WEXITSTATUS(status) == 0;
+}
+
+std::string toLower(const std::string& s) {
+  std::string r(s);
+  for (auto& c : r) {
+    c = std::tolower(c);
+  }
+  return r;
+}
+
+std::string shellEscape(const std::string& s) {
+  std::string r = "'";
+  for (auto& i : s) {
+    if (i == '\'') {
+      r += "'\\''";
+    } else {
+      r += i;
+    }
+  }
+  r += '\'';
+  return r;
+}
+
+void ignoreException() {
+  try {
+    throw;
+  } catch (std::exception& e) {
+    LOG(ERROR) << "error (ignored): " << e.what();
+  }
+}
+
+std::string filterANSIEscapes(const std::string& s, bool filterAll,
+                              unsigned int width) {
+  std::string t;
+  std::string e;
+  size_t w = 0;
+  auto i = s.begin();
+
+  while (w < static_cast<size_t>(width) && i != s.end()) {
+    if (*i == '\e') {
+      std::string e;
+      e += *i++;
+      char last = 0;
+
+      if (i != s.end() && *i == '[') {
+        e += *i++;
+        // eat parameter bytes
+        while (i != s.end() && *i >= 0x30 && *i <= 0x3f) {
+          e += *i++;
+        }
+        // eat intermediate bytes
+        while (i != s.end() && *i >= 0x20 && *i <= 0x2f) {
+          e += *i++;
+        }
+        // eat final byte
+        if (i != s.end() && *i >= 0x40 && *i <= 0x7e) {
+          e += last = *i++;
+        }
+      } else {
+        if (i != s.end() && *i >= 0x40 && *i <= 0x5f) {
+          e += *i++;
+        }
+      }
+
+      if (!filterAll && last == 'm') {
+        t += e;
+      }
+    }
+
+    else if (*i == '\t') {
+      i++;
+      t += ' ';
+      w++;
+      while (w < static_cast<size_t>(width) && ((w % 8) != 0u)) {
+        t += ' ';
+        w++;
+      }
+    }
+
+    else if (*i == '\r') {
+      // do nothing for now
+      i++;
+
+    } else {
+      t += *i++;
+      w++;
+    }
+  }
+
+  return t;
+}
+
+void callFailure(const std::function<void(std::exception_ptr exc)>& failure,
+                 const std::exception_ptr& exc) {
+  try {
+    failure(exc);
+  } catch (std::exception& e) {
+    LOG(ERROR) << "uncaught exception: " << e.what();
+    abort();
+  }
+}
+
+static Sync<std::pair<unsigned short, unsigned short>> windowSize{{0, 0}};
+
+static void updateWindowSize() {
+  struct winsize ws;
+  if (ioctl(2, TIOCGWINSZ, &ws) == 0) {
+    auto windowSize_(windowSize.lock());
+    windowSize_->first = ws.ws_row;
+    windowSize_->second = ws.ws_col;
+  }
+}
+
+std::pair<unsigned short, unsigned short> getWindowSize() {
+  return *windowSize.lock();
+}
+
+static Sync<std::list<std::function<void()>>> _interruptCallbacks;
+
+static void signalHandlerThread(sigset_t set) {
+  while (true) {
+    int signal = 0;
+    sigwait(&set, &signal);
+
+    if (signal == SIGINT || signal == SIGTERM || signal == SIGHUP) {
+      triggerInterrupt();
+
+    } else if (signal == SIGWINCH) {
+      updateWindowSize();
+    }
+  }
+}
+
+void triggerInterrupt() {
+  _isInterrupted = true;
+
+  {
+    auto interruptCallbacks(_interruptCallbacks.lock());
+    for (auto& callback : *interruptCallbacks) {
+      try {
+        callback();
+      } catch (...) {
+        ignoreException();
+      }
+    }
+  }
+}
+
+static sigset_t savedSignalMask;
+
+void startSignalHandlerThread() {
+  updateWindowSize();
+
+  if (sigprocmask(SIG_BLOCK, nullptr, &savedSignalMask) != 0) {
+    throw SysError("quering signal mask");
+  }
+
+  sigset_t set;
+  sigemptyset(&set);
+  sigaddset(&set, SIGINT);
+  sigaddset(&set, SIGTERM);
+  sigaddset(&set, SIGHUP);
+  sigaddset(&set, SIGPIPE);
+  sigaddset(&set, SIGWINCH);
+  if (pthread_sigmask(SIG_BLOCK, &set, nullptr) != 0) {
+    throw SysError("blocking signals");
+  }
+
+  std::thread(signalHandlerThread, set).detach();
+}
+
+void restoreSignals() {
+  if (sigprocmask(SIG_SETMASK, &savedSignalMask, nullptr) != 0) {
+    throw SysError("restoring signals");
+  }
+}
+
+/* RAII helper to automatically deregister a callback. */
+struct InterruptCallbackImpl : InterruptCallback {
+  std::list<std::function<void()>>::iterator it;
+  ~InterruptCallbackImpl() override { _interruptCallbacks.lock()->erase(it); }
+};
+
+std::unique_ptr<InterruptCallback> createInterruptCallback(
+    const std::function<void()>& callback) {
+  auto interruptCallbacks(_interruptCallbacks.lock());
+  interruptCallbacks->push_back(callback);
+
+  auto res = std::make_unique<InterruptCallbackImpl>();
+  res->it = interruptCallbacks->end();
+  res->it--;
+
+  return std::unique_ptr<InterruptCallback>(res.release());
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/util.hh b/third_party/nix/src/libutil/util.hh
new file mode 100644
index 000000000000..b3349c4f39c4
--- /dev/null
+++ b/third_party/nix/src/libutil/util.hh
@@ -0,0 +1,476 @@
+#pragma once
+
+#include <cstdio>
+#include <functional>
+#include <future>
+#include <limits>
+#include <map>
+#include <optional>
+#include <sstream>
+
+#include <absl/strings/string_view.h>
+#include <dirent.h>
+#include <signal.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include "libutil/types.hh"
+
+namespace nix {
+
+struct Sink;
+struct Source;
+
+/* The system for which Nix is compiled. */
+extern const std::string nativeSystem;
+
+/* Return an environment variable. */
+std::optional<std::string> getEnv(const std::string& key);
+
+/* Get the entire environment. */
+std::map<std::string, std::string> getEnv();
+
+/* Clear the environment. */
+void clearEnv();
+
+/* Return an absolutized path, resolving paths relative to the
+   specified directory, or the current directory otherwise.  The path
+   is also canonicalised. */
+Path absPath(Path path, Path dir = "");
+
+/* Canonicalise a path by removing all `.' or `..' components and
+   double or trailing slashes.  Optionally resolves all symlink
+   components such that each component of the resulting path is *not*
+   a symbolic link. */
+Path canonPath(const Path& path, bool resolveSymlinks = false);
+
+/* Return the directory part of the given canonical path, i.e.,
+   everything before the final `/'.  If the path is the root or an
+   immediate child thereof (e.g., `/foo'), this means an empty string
+   is returned. */
+Path dirOf(absl::string_view path);
+
+/* Return the base name of the given canonical path, i.e., everything
+   following the final `/'. */
+std::string baseNameOf(const Path& path);
+
+/* Check whether 'path' is a descendant of 'dir'. */
+bool isInDir(const Path& path, const Path& dir);
+
+/* Check whether 'path' is equal to 'dir' or a descendant of 'dir'. */
+bool isDirOrInDir(const Path& path, const Path& dir);
+
+/* Get status of `path'. */
+struct stat lstat(const Path& path);
+
+/* Return true iff the given path exists. */
+bool pathExists(const Path& path);
+
+/* Read the contents (target) of a symbolic link.  The result is not
+   in any way canonicalised. */
+Path readLink(const Path& path);
+
+bool isLink(const Path& path);
+
+/* Read the contents of a directory.  The entries `.' and `..' are
+   removed. */
+struct DirEntry {
+  std::string name;
+  ino_t ino;
+  unsigned char type;  // one of DT_*
+  DirEntry(const std::string& name, ino_t ino, unsigned char type)
+      : name(name), ino(ino), type(type) {}
+};
+
+typedef std::vector<DirEntry> DirEntries;
+
+DirEntries readDirectory(const Path& path);
+
+unsigned char getFileType(const Path& path);
+
+/* Read the contents of a file into a string. */
+std::string readFile(int fd);
+std::string readFile(absl::string_view path, bool drain = false);
+void readFile(absl::string_view path, Sink& sink);
+
+/* Write a string to a file. */
+void writeFile(const Path& path, const std::string& s, mode_t mode = 0666);
+
+void writeFile(const Path& path, Source& source, mode_t mode = 0666);
+
+/* Read a line from a file descriptor. */
+std::string readLine(int fd);
+
+/* Write a line to a file descriptor. */
+void writeLine(int fd, std::string s);
+
+/* Delete a path; i.e., in the case of a directory, it is deleted
+   recursively. It's not an error if the path does not exist. The
+   second variant returns the number of bytes and blocks freed. */
+void deletePath(const Path& path);
+
+void deletePath(const Path& path, unsigned long long& bytesFreed);
+
+/* Create a temporary directory. */
+Path createTempDir(const Path& tmpRoot = "", const Path& prefix = "nix",
+                   bool includePid = true, bool useGlobalCounter = true,
+                   mode_t mode = 0755);
+
+std::string getUserName();
+
+/* Return $HOME or the user's home directory from /etc/passwd. */
+Path getHome();
+
+/* Return $XDG_CACHE_HOME or $HOME/.cache. */
+Path getCacheDir();
+
+/* Return $XDG_CONFIG_HOME or $HOME/.config. */
+Path getConfigDir();
+
+/* Return the directories to search for user configuration files */
+std::vector<Path> getConfigDirs();
+
+/* Return $XDG_DATA_HOME or $HOME/.local/share. */
+Path getDataDir();
+
+/* Create a directory and all its parents, if necessary.  Returns the
+   list of created directories, in order of creation. */
+Paths createDirs(const Path& path);
+
+/* Create a symlink. */
+void createSymlink(const Path& target, const Path& link);
+
+/* Atomically create or replace a symlink. */
+void replaceSymlink(const Path& target, const Path& link);
+
+/* Wrappers arount read()/write() that read/write exactly the
+   requested number of bytes. */
+void readFull(int fd, unsigned char* buf, size_t count);
+void writeFull(int fd, const unsigned char* buf, size_t count,
+               bool allowInterrupts = true);
+void writeFull(int fd, const std::string& s, bool allowInterrupts = true);
+
+MakeError(EndOfFile, Error);
+
+/* Read a file descriptor until EOF occurs. */
+std::string drainFD(int fd, bool block = true);
+
+void drainFD(int fd, Sink& sink, bool block = true);
+
+/* Automatic cleanup of resources. */
+
+class AutoDelete {
+  Path path;
+  bool del;
+  bool recursive;
+
+ public:
+  AutoDelete();
+  explicit AutoDelete(Path p, bool recursive = true);
+  ~AutoDelete();
+  void cancel();
+  void reset(const Path& p, bool recursive = true);
+  explicit operator Path() const { return path; }
+};
+
+class AutoCloseFD {
+  int fd;
+  void close();
+
+ public:
+  AutoCloseFD();
+  explicit AutoCloseFD(int fd);
+  AutoCloseFD(const AutoCloseFD& fd) = delete;
+  AutoCloseFD(AutoCloseFD&& that);
+  ~AutoCloseFD();
+  AutoCloseFD& operator=(const AutoCloseFD& fd) = delete;
+  AutoCloseFD& operator=(AutoCloseFD&& that);
+  int get() const;
+  explicit operator bool() const;
+  int release();
+};
+
+class Pipe {
+ public:
+  AutoCloseFD readSide, writeSide;
+  void create();
+};
+
+struct DIRDeleter {
+  void operator()(DIR* dir) const { closedir(dir); }
+};
+
+using AutoCloseDir = std::unique_ptr<DIR, DIRDeleter>;
+
+class Pid {
+  pid_t pid = -1;
+  bool separatePG = false;
+  int killSignal = SIGKILL;
+
+ public:
+  Pid();
+  explicit Pid(pid_t pid);
+  ~Pid();
+  void operator=(pid_t pid);
+  explicit operator pid_t();
+  int kill();
+  int wait();
+
+  void setSeparatePG(bool separatePG);
+  void setKillSignal(int signal);
+  pid_t release();
+
+  friend bool operator==(const Pid& lhs, const Pid& rhs) {
+    return lhs.pid == rhs.pid;
+  }
+
+  friend bool operator!=(const Pid& lhs, const Pid& rhs) {
+    return !(lhs == rhs);
+  }
+};
+
+/* Kill all processes running under the specified uid by sending them
+   a SIGKILL. */
+void killUser(uid_t uid);
+
+/* Fork a process that runs the given function, and return the child
+   pid to the caller. */
+struct ProcessOptions {
+  std::string errorPrefix = "error: ";
+  bool dieWithParent = true;
+  bool runExitHandlers = false;
+};
+
+pid_t startProcess(std::function<void()> fun,
+                   const ProcessOptions& options = ProcessOptions());
+
+/* Run a program and return its stdout in a string (i.e., like the
+   shell backtick operator). */
+std::string runProgram(const Path& program, bool searchPath = false,
+                       const Strings& args = Strings(),
+                       const std::optional<std::string>& input = {});
+
+struct RunOptions {
+  std::optional<uid_t> uid;
+  std::optional<uid_t> gid;
+  std::optional<Path> chdir;
+  std::optional<std::map<std::string, std::string>> environment;
+  Path program;
+  bool searchPath = true;
+  Strings args;
+  std::optional<std::string> input;
+  Source* standardIn = nullptr;
+  Sink* standardOut = nullptr;
+  bool mergeStderrToStdout = false;
+  bool _killStderr = false;
+
+  RunOptions(const Path& program, const Strings& args)
+      : program(program), args(args){};
+
+  RunOptions& killStderr(bool v) {
+    _killStderr = true;
+    return *this;
+  }
+};
+
+std::pair<int, std::string> runProgram(const RunOptions& options);
+
+void runProgram2(const RunOptions& options);
+
+class ExecError : public Error {
+ public:
+  int status;
+
+  template <typename... Args>
+  explicit ExecError(int status, Args... args)
+      : Error(args...), status(status) {}
+};
+
+/* Convert a list of strings to a null-terminated vector of char
+   *'s. The result must not be accessed beyond the lifetime of the
+   list of strings. */
+std::vector<char*> stringsToCharPtrs(const Strings& ss);
+
+/* Close all file descriptors except those listed in the given set.
+   Good practice in child processes. */
+void closeMostFDs(const std::set<int>& exceptions);
+
+/* Set the close-on-exec flag for the given file descriptor. */
+void closeOnExec(int fd);
+
+/* User interruption. */
+
+extern bool _isInterrupted;
+
+extern thread_local std::function<bool()> interruptCheck;
+
+void setInterruptThrown();
+
+void _interrupted();
+
+void inline checkInterrupt() {
+  if (_isInterrupted || (interruptCheck && interruptCheck())) {
+    _interrupted();
+  }
+}
+
+MakeError(Interrupted, BaseError);
+
+MakeError(FormatError, Error);
+
+/* Concatenate the given strings with a separator between the
+   elements. */
+std::string concatStringsSep(const std::string& sep, const Strings& ss);
+std::string concatStringsSep(const std::string& sep, const StringSet& ss);
+
+/* Replace all occurrences of a string inside another string. */
+std::string replaceStrings(const std::string& s, const std::string& from,
+                           const std::string& to);
+
+/* Convert the exit status of a child as returned by wait() into an
+   error string. */
+std::string statusToString(int status);
+
+bool statusOk(int status);
+
+/* Parse a string into a float. */
+template <class N>
+bool string2Float(const std::string& s, N& n) {
+  std::istringstream str(s);
+  str >> n;
+  return str && str.get() == EOF;
+}
+
+/* Convert a string to lower case. */
+std::string toLower(const std::string& s);
+
+/* Escape a string as a shell word. */
+std::string shellEscape(const std::string& s);
+
+/* Exception handling in destructors: print an error message, then
+   ignore the exception. */
+void ignoreException();
+
+/* Some ANSI escape sequences. */
+#define ANSI_NORMAL "\e[0m"
+#define ANSI_BOLD "\e[1m"
+#define ANSI_FAINT "\e[2m"
+#define ANSI_RED "\e[31;1m"
+#define ANSI_GREEN "\e[32;1m"
+#define ANSI_BLUE "\e[34;1m"
+
+/* Truncate a string to 'width' printable characters. If 'filterAll'
+   is true, all ANSI escape sequences are filtered out. Otherwise,
+   some escape sequences (such as colour setting) are copied but not
+   included in the character count. Also, tabs are expanded to
+   spaces. */
+std::string filterANSIEscapes(
+    const std::string& s, bool filterAll = false,
+    unsigned int width = std::numeric_limits<unsigned int>::max());
+
+/* Get a value for the specified key from an associate container, or a
+   default value if the key doesn't exist. */
+template <class T>
+std::string get(const T& map, const std::string& key,
+                const std::string& def = "") {
+  auto i = map.find(key);
+  return i == map.end() ? def : i->second;
+}
+
+/* A callback is a wrapper around a lambda that accepts a valid of
+   type T or an exception. (We abuse std::future<T> to pass the value or
+   exception.) */
+template <typename T>
+class Callback {
+  std::function<void(std::future<T>)> fun;
+  std::atomic_flag done = ATOMIC_FLAG_INIT;
+
+ public:
+  explicit Callback(std::function<void(std::future<T>)> fun) : fun(fun) {}
+
+  Callback(Callback&& callback) : fun(std::move(callback.fun)) {
+    auto prev = callback.done.test_and_set();
+    if (prev) {
+      done.test_and_set();
+    }
+  }
+
+// The unused-variable assert is disabled in this block because the
+// `prev` variables are only used in debug mode (in the asserts).
+#pragma clang diagnostic push
+#pragma clang diagnostic ignored "-Wunused-variable"
+
+  void operator()(T&& t) noexcept {
+    auto prev = done.test_and_set();
+    assert(!prev);
+    std::promise<T> promise;
+    promise.set_value(std::move(t));
+    fun(promise.get_future());
+  }
+
+  void rethrow(
+      const std::exception_ptr& exc = std::current_exception()) noexcept {
+    auto prev = done.test_and_set();
+    assert(!prev);
+    std::promise<T> promise;
+    promise.set_exception(exc);
+    fun(promise.get_future());
+  }
+
+#pragma clang diagnostic pop
+};
+
+/* Start a thread that handles various signals. Also block those signals
+   on the current thread (and thus any threads created by it). */
+void startSignalHandlerThread();
+
+/* Restore default signal handling. */
+void restoreSignals();
+
+struct InterruptCallback {
+  virtual ~InterruptCallback(){};
+};
+
+/* Register a function that gets called on SIGINT (in a non-signal
+   context). */
+std::unique_ptr<InterruptCallback> createInterruptCallback(
+    const std::function<void()>& callback);
+
+void triggerInterrupt();
+
+/* A RAII class that causes the current thread to receive SIGUSR1 when
+   the signal handler thread receives SIGINT. That is, this allows
+   SIGINT to be multiplexed to multiple threads. */
+struct ReceiveInterrupts {
+  pthread_t target;
+  std::unique_ptr<InterruptCallback> callback;
+
+  ReceiveInterrupts()
+      : target(pthread_self()), callback(createInterruptCallback([&]() {
+          pthread_kill(target, SIGUSR1);
+        })) {}
+};
+
+/* A RAII helper that increments a counter on construction and
+   decrements it on destruction. */
+template <typename T>
+struct MaintainCount {
+  T& counter;
+  long delta;
+  explicit MaintainCount(T& counter, long delta = 1)
+      : counter(counter), delta(delta) {
+    counter += delta;
+  }
+  ~MaintainCount() { counter -= delta; }
+};
+
+/* Return the number of rows and columns of the terminal. */
+std::pair<unsigned short, unsigned short> getWindowSize();
+
+/* Used in various places. */
+using PathFilter = std::function<bool(const Path&)>;
+
+extern PathFilter defaultPathFilter;
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/visitor.hh b/third_party/nix/src/libutil/visitor.hh
new file mode 100644
index 000000000000..bf1d665af77f
--- /dev/null
+++ b/third_party/nix/src/libutil/visitor.hh
@@ -0,0 +1,19 @@
+#pragma once
+
+namespace nix::util {
+
+// Helper class used for visiting std::variants by creating a variadic
+// list of lambda expressions that delegates calls to each of the
+// callables.
+//
+// See e.g.
+// https://dev.to/tmr232/that-overloaded-trick-overloading-lambdas-in-c17
+template <class... Ts>
+struct overloaded : Ts... {
+  using Ts::operator()...;
+};
+
+template <class... Ts>
+overloaded(Ts...) -> overloaded<Ts...>;
+
+}  // namespace nix::util
diff --git a/third_party/nix/src/libutil/xml-writer.cc b/third_party/nix/src/libutil/xml-writer.cc
new file mode 100644
index 000000000000..8274ed769eb4
--- /dev/null
+++ b/third_party/nix/src/libutil/xml-writer.cc
@@ -0,0 +1,93 @@
+#include "libutil/xml-writer.hh"
+
+#include <cassert>
+
+namespace nix {
+
+XMLWriter::XMLWriter(bool indent, std::ostream& output)
+    : output(output), indent(indent) {
+  output << "<?xml version='1.0' encoding='utf-8'?>" << std::endl;
+  closed = false;
+}
+
+XMLWriter::~XMLWriter() { close(); }
+
+void XMLWriter::close() {
+  if (closed) {
+    return;
+  }
+  while (!pendingElems.empty()) {
+    closeElement();
+  }
+  closed = true;
+}
+
+void XMLWriter::indent_(size_t depth) {
+  if (!indent) {
+    return;
+  }
+  output << std::string(depth * 2, ' ');
+}
+
+void XMLWriter::openElement(const std::string& name, const XMLAttrs& attrs) {
+  assert(!closed);
+  indent_(pendingElems.size());
+  output << "<" << name;
+  writeAttrs(attrs);
+  output << ">";
+  if (indent) {
+    output << std::endl;
+  }
+  pendingElems.push_back(name);
+}
+
+void XMLWriter::closeElement() {
+  assert(!pendingElems.empty());
+  indent_(pendingElems.size() - 1);
+  output << "</" << pendingElems.back() << ">";
+  if (indent) {
+    output << std::endl;
+  }
+  pendingElems.pop_back();
+  if (pendingElems.empty()) {
+    closed = true;
+  }
+}
+
+void XMLWriter::writeEmptyElement(const std::string& name,
+                                  const XMLAttrs& attrs) {
+  assert(!closed);
+  indent_(pendingElems.size());
+  output << "<" << name;
+  writeAttrs(attrs);
+  output << " />";
+  if (indent) {
+    output << std::endl;
+  }
+}
+
+void XMLWriter::writeAttrs(const XMLAttrs& attrs) {
+  for (auto& i : attrs) {
+    output << " " << i.first << "=\"";
+    for (char c : i.second) {
+      if (c == '"') {
+        output << "&quot;";
+      } else if (c == '<') {
+        output << "&lt;";
+      } else if (c == '>') {
+        output << "&gt;";
+      } else if (c == '&') {
+        output << "&amp;";
+        /* Escape newlines to prevent attribute normalisation (see
+           XML spec, section 3.3.3. */
+      } else if (c == '\n') {
+        output << "&#xA;";
+      } else {
+        output << c;
+      }
+    }
+    output << "\"";
+  }
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libutil/xml-writer.hh b/third_party/nix/src/libutil/xml-writer.hh
new file mode 100644
index 000000000000..d6f7cddb35ac
--- /dev/null
+++ b/third_party/nix/src/libutil/xml-writer.hh
@@ -0,0 +1,52 @@
+#pragma once
+
+#include <iostream>
+#include <list>
+#include <map>
+#include <string>
+
+namespace nix {
+
+typedef std::map<std::string, std::string> XMLAttrs;
+
+class XMLWriter {
+ private:
+  std::ostream& output;
+
+  bool indent;
+  bool closed;
+
+  std::list<std::string> pendingElems;
+
+ public:
+  XMLWriter(bool indent, std::ostream& output);
+  ~XMLWriter();
+
+  void close();
+
+  void openElement(const std::string& name, const XMLAttrs& attrs = XMLAttrs());
+  void closeElement();
+
+  void writeEmptyElement(const std::string& name,
+                         const XMLAttrs& attrs = XMLAttrs());
+
+ private:
+  void writeAttrs(const XMLAttrs& attrs);
+
+  void indent_(size_t depth);
+};
+
+class XMLOpenElement {
+ private:
+  XMLWriter& writer;
+
+ public:
+  XMLOpenElement(XMLWriter& writer, const std::string& name,
+                 const XMLAttrs& attrs = XMLAttrs())
+      : writer(writer) {
+    writer.openElement(name, attrs);
+  }
+  ~XMLOpenElement() { writer.closeElement(); }
+};
+
+}  // namespace nix