about summary refs log tree commit diff
path: root/third_party/nix/src/libexpr/eval.cc
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/nix/src/libexpr/eval.cc')
-rw-r--r--third_party/nix/src/libexpr/eval.cc2001
1 files changed, 2001 insertions, 0 deletions
diff --git a/third_party/nix/src/libexpr/eval.cc b/third_party/nix/src/libexpr/eval.cc
new file mode 100644
index 000000000000..0abf94c87445
--- /dev/null
+++ b/third_party/nix/src/libexpr/eval.cc
@@ -0,0 +1,2001 @@
+#include "eval.hh"
+
+#include <algorithm>
+#include <chrono>
+#include <cstring>
+#include <fstream>
+#include <iostream>
+#include <new>
+
+#include <gc/gc.h>
+#include <gc/gc_cpp.h>
+#include <glog/logging.h>
+#include <sys/resource.h>
+#include <sys/time.h>
+#include <unistd.h>
+
+#include "derivations.hh"
+#include "download.hh"
+#include "eval-inline.hh"
+#include "function-trace.hh"
+#include "globals.hh"
+#include "hash.hh"
+#include "json.hh"
+#include "store-api.hh"
+#include "util.hh"
+
+namespace nix {
+
+static char* dupString(const char* s) {
+  char* t;
+  t = GC_STRDUP(s);
+  if (t == nullptr) {
+    throw std::bad_alloc();
+  }
+  return t;
+}
+
+static void printValue(std::ostream& str, std::set<const Value*>& active,
+                       const Value& v) {
+  checkInterrupt();
+
+  if (active.find(&v) != active.end()) {
+    str << "<CYCLE>";
+    return;
+  }
+  active.insert(&v);
+
+  switch (v.type) {
+    case tInt:
+      str << v.integer;
+      break;
+    case tBool:
+      str << (v.boolean ? "true" : "false");
+      break;
+    case tString:
+      str << "\"";
+      for (const char* i = v.string.s; *i != 0; 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 {
+          str << *i;
+        }
+      }
+      str << "\"";
+      break;
+    case tPath:
+      str << v.path;  // !!! escaping?
+      break;
+    case tNull:
+      str << "null";
+      break;
+    case tAttrs: {
+      str << "{ ";
+      for (auto& i : v.attrs->lexicographicOrder()) {
+        str << i->name << " = ";
+        printValue(str, active, *i->value);
+        str << "; ";
+      }
+      str << "}";
+      break;
+    }
+    case tList1:
+    case tList2:
+    case tListN:
+      str << "[ ";
+      for (unsigned int n = 0; n < v.listSize(); ++n) {
+        printValue(str, active, *v.listElems()[n]);
+        str << " ";
+      }
+      str << "]";
+      break;
+    case tThunk:
+    case tApp:
+      str << "<CODE>";
+      break;
+    case tLambda:
+      str << "<LAMBDA>";
+      break;
+    case tPrimOp:
+      str << "<PRIMOP>";
+      break;
+    case tPrimOpApp:
+      str << "<PRIMOP-APP>";
+      break;
+    case tExternal:
+      str << *v.external;
+      break;
+    case tFloat:
+      str << v.fpoint;
+      break;
+    default:
+      throw Error("invalid value");
+  }
+
+  active.erase(&v);
+}
+
+std::ostream& operator<<(std::ostream& str, const Value& v) {
+  std::set<const Value*> active;
+  printValue(str, active, v);
+  return str;
+}
+
+const Value* getPrimOp(const Value& v) {
+  const Value* primOp = &v;
+  while (primOp->type == tPrimOpApp) {
+    primOp = primOp->primOpApp.left;
+  }
+  assert(primOp->type == tPrimOp);
+  return primOp;
+}
+
+string showType(const Value& v) {
+  switch (v.type) {
+    case tInt:
+      return "an integer";
+    case tBool:
+      return "a boolean";
+    case tString:
+      return v.string.context != nullptr ? "a string with context" : "a string";
+    case tPath:
+      return "a path";
+    case tNull:
+      return "null";
+    case tAttrs:
+      return "a set";
+    case tList1:
+    case tList2:
+    case tListN:
+      return "a list";
+    case tThunk:
+      return "a thunk";
+    case tApp:
+      return "a function application";
+    case tLambda:
+      return "a function";
+    case tBlackhole:
+      return "a black hole";
+    case tPrimOp:
+      return fmt("the built-in function '%s'", string(v.primOp->name));
+    case tPrimOpApp:
+      return fmt("the partially applied built-in function '%s'",
+                 string(getPrimOp(v)->primOp->name));
+    case tExternal:
+      return v.external->showType();
+    case tFloat:
+      return "a float";
+  }
+  abort();
+}
+
+#if HAVE_BOEHMGC
+/* Called when the Boehm GC runs out of memory. */
+static void* oomHandler(size_t requested) {
+  /* Convert this to a proper C++ exception. */
+  throw std::bad_alloc();
+}
+#endif
+
+static Symbol getName(const AttrName& name, EvalState& state, Env& env) {
+  if (name.symbol.set()) {
+    return name.symbol;
+  }
+  Value nameValue;
+  name.expr->eval(state, env, nameValue);
+  state.forceStringNoCtx(nameValue);
+  return state.symbols.Create(nameValue.string.s);
+}
+
+static bool gcInitialised = false;
+
+void initGC() {
+  if (gcInitialised) {
+    return;
+  }
+
+#if HAVE_BOEHMGC
+  /* Initialise the Boehm garbage collector. */
+
+  /* Don't look for interior pointers. This reduces the odds of
+     misdetection a bit. */
+  GC_set_all_interior_pointers(0);
+
+  /* We don't have any roots in data segments, so don't scan from
+     there. */
+  GC_set_no_dls(1);
+
+  GC_INIT();
+
+  GC_set_oom_fn(oomHandler);
+
+  /* Set the initial heap size to something fairly big (25% of
+     physical RAM, up to a maximum of 384 MiB) so that in most cases
+     we don't need to garbage collect at all.  (Collection has a
+     fairly significant overhead.)  The heap size can be overridden
+     through libgc's GC_INITIAL_HEAP_SIZE environment variable.  We
+     should probably also provide a nix.conf setting for this.  Note
+     that GC_expand_hp() causes a lot of virtual, but not physical
+     (resident) memory to be allocated.  This might be a problem on
+     systems that don't overcommit. */
+  if (getenv("GC_INITIAL_HEAP_SIZE") == nullptr) {
+    size_t size = 32 * 1024 * 1024;
+#if HAVE_SYSCONF && defined(_SC_PAGESIZE) && defined(_SC_PHYS_PAGES)
+    size_t maxSize = 384 * 1024 * 1024;
+    long pageSize = sysconf(_SC_PAGESIZE);
+    long pages = sysconf(_SC_PHYS_PAGES);
+    if (pageSize != -1) {
+      size = (pageSize * pages) / 4;
+    }  // 25% of RAM
+    if (size > maxSize) {
+      size = maxSize;
+    }
+#endif
+    DLOG(INFO) << "setting initial heap size to " << size << " bytes";
+    GC_expand_hp(size);
+  }
+
+#endif
+
+  gcInitialised = true;
+}
+
+/* Very hacky way to parse $NIX_PATH, which is colon-separated, but
+   can contain URLs (e.g. "nixpkgs=https://bla...:foo=https://"). */
+static Strings parseNixPath(const std::string& s) {
+  Strings res;
+
+  auto p = s.begin();
+
+  while (p != s.end()) {
+    auto start = p;
+    auto start2 = p;
+
+    while (p != s.end() && *p != ':') {
+      if (*p == '=') {
+        start2 = p + 1;
+      }
+      ++p;
+    }
+
+    if (p == s.end()) {
+      if (p != start) {
+        res.push_back(std::string(start, p));
+      }
+      break;
+    }
+
+    if (*p == ':') {
+      if (isUri(std::string(start2, s.end()))) {
+        ++p;
+        while (p != s.end() && *p != ':') {
+          ++p;
+        }
+      }
+      res.push_back(std::string(start, p));
+      if (p == s.end()) {
+        break;
+      }
+    }
+
+    ++p;
+  }
+
+  return res;
+}
+
+EvalState::EvalState(const Strings& _searchPath, const ref<Store>& store)
+    : sWith(symbols.Create("<with>")),
+      sOutPath(symbols.Create("outPath")),
+      sDrvPath(symbols.Create("drvPath")),
+      sType(symbols.Create("type")),
+      sMeta(symbols.Create("meta")),
+      sName(symbols.Create("name")),
+      sValue(symbols.Create("value")),
+      sSystem(symbols.Create("system")),
+      sOverrides(symbols.Create("__overrides")),
+      sOutputs(symbols.Create("outputs")),
+      sOutputName(symbols.Create("outputName")),
+      sIgnoreNulls(symbols.Create("__ignoreNulls")),
+      sFile(symbols.Create("file")),
+      sLine(symbols.Create("line")),
+      sColumn(symbols.Create("column")),
+      sFunctor(symbols.Create("__functor")),
+      sToString(symbols.Create("__toString")),
+      sRight(symbols.Create("right")),
+      sWrong(symbols.Create("wrong")),
+      sStructuredAttrs(symbols.Create("__structuredAttrs")),
+      sBuilder(symbols.Create("builder")),
+      sArgs(symbols.Create("args")),
+      sOutputHash(symbols.Create("outputHash")),
+      sOutputHashAlgo(symbols.Create("outputHashAlgo")),
+      sOutputHashMode(symbols.Create("outputHashMode")),
+      repair(NoRepair),
+      store(store),
+      baseEnv(allocEnv(128)),
+      staticBaseEnv(false, nullptr) {
+  countCalls = getEnv("NIX_COUNT_CALLS", "0") != "0";
+
+  assert(gcInitialised);
+
+  static_assert(sizeof(Env) <= 16, "environment must be <= 16 bytes");
+
+  /* Initialise the Nix expression search path. */
+  if (!evalSettings.pureEval) {
+    Strings paths = parseNixPath(getEnv("NIX_PATH", ""));
+    for (auto& i : _searchPath) {
+      addToSearchPath(i);
+    }
+    for (auto& i : paths) {
+      addToSearchPath(i);
+    }
+  }
+  addToSearchPath("nix=" +
+                  canonPath(settings.nixDataDir + "/nix/corepkgs", true));
+
+  if (evalSettings.restrictEval || evalSettings.pureEval) {
+    allowedPaths = PathSet();
+
+    for (auto& i : searchPath) {
+      auto r = resolveSearchPathElem(i);
+      if (!r.first) {
+        continue;
+      }
+
+      auto path = r.second;
+
+      if (store->isInStore(r.second)) {
+        PathSet closure;
+        store->computeFSClosure(store->toStorePath(r.second), closure);
+        for (auto& path : closure) {
+          allowedPaths->insert(path);
+        }
+      } else {
+        allowedPaths->insert(r.second);
+      }
+    }
+  }
+
+  clearValue(vEmptySet);
+  vEmptySet.type = tAttrs;
+  vEmptySet.attrs = Bindings::NewGC();
+
+  createBaseEnv();
+}
+
+EvalState::~EvalState() = default;
+
+Path EvalState::checkSourcePath(const Path& path_) {
+  if (!allowedPaths) {
+    return path_;
+  }
+
+  auto i = resolvedPaths.find(path_);
+  if (i != resolvedPaths.end()) {
+    return i->second;
+  }
+
+  bool found = false;
+
+  /* First canonicalize the path without symlinks, so we make sure an
+   * attacker can't append ../../... to a path that would be in allowedPaths
+   * and thus leak symlink targets.
+   */
+  Path abspath = canonPath(path_);
+
+  for (auto& i : *allowedPaths) {
+    if (isDirOrInDir(abspath, i)) {
+      found = true;
+      break;
+    }
+  }
+
+  if (!found) {
+    throw RestrictedPathError(
+        "access to path '%1%' is forbidden in restricted mode", abspath);
+  }
+
+  /* Resolve symlinks. */
+  DLOG(INFO) << "checking access to '" << abspath << "'";
+  Path path = canonPath(abspath, true);
+
+  for (auto& i : *allowedPaths) {
+    if (isDirOrInDir(path, i)) {
+      resolvedPaths[path_] = path;
+      return path;
+    }
+  }
+
+  throw RestrictedPathError(
+      "access to path '%1%' is forbidden in restricted mode", path);
+}
+
+void EvalState::checkURI(const std::string& uri) {
+  if (!evalSettings.restrictEval) {
+    return;
+  }
+
+  /* 'uri' should be equal to a prefix, or in a subdirectory of a
+     prefix. Thus, the prefix https://github.co does not permit
+     access to https://github.com. Note: this allows 'http://' and
+     'https://' as prefixes for any http/https URI. */
+  for (auto& prefix : evalSettings.allowedUris.get()) {
+    if (uri == prefix ||
+        (uri.size() > prefix.size() && !prefix.empty() &&
+         hasPrefix(uri, prefix) &&
+         (prefix[prefix.size() - 1] == '/' || uri[prefix.size()] == '/'))) {
+      return;
+    }
+  }
+
+  /* If the URI is a path, then check it against allowedPaths as
+     well. */
+  if (hasPrefix(uri, "/")) {
+    checkSourcePath(uri);
+    return;
+  }
+
+  if (hasPrefix(uri, "file://")) {
+    checkSourcePath(std::string(uri, 7));
+    return;
+  }
+
+  throw RestrictedPathError(
+      "access to URI '%s' is forbidden in restricted mode", uri);
+}
+
+Path EvalState::toRealPath(const Path& path, const PathSet& context) {
+  // FIXME: check whether 'path' is in 'context'.
+  return !context.empty() && store->isInStore(path) ? store->toRealPath(path)
+                                                    : path;
+};
+
+Value* EvalState::addConstant(const std::string& name, Value& v) {
+  Value* v2 = allocValue();
+  *v2 = v;
+  staticBaseEnv.vars[symbols.Create(name)] = baseEnvDispl;
+  baseEnv.values[baseEnvDispl++] = v2;
+  std::string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
+  baseEnv.values[0]->attrs->push_back(Attr(symbols.Create(name2), v2));
+  return v2;
+}
+
+Value* EvalState::addPrimOp(const std::string& name, size_t arity,
+                            PrimOpFun primOp) {
+  if (arity == 0) {
+    Value v;
+    primOp(*this, noPos, nullptr, v);
+    return addConstant(name, v);
+  }
+  Value* v = allocValue();
+  std::string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
+  Symbol sym = symbols.Create(name2);
+  v->type = tPrimOp;
+  v->primOp = new PrimOp(primOp, arity, sym);
+  staticBaseEnv.vars[symbols.Create(name)] = baseEnvDispl;
+  baseEnv.values[baseEnvDispl++] = v;
+  baseEnv.values[0]->attrs->push_back(Attr(sym, v));
+  return v;
+}
+
+Value& EvalState::getBuiltin(const std::string& name) {
+  return *baseEnv.values[0]->attrs->find(symbols.Create(name))->second.value;
+}
+
+/* Every "format" object (even temporary) takes up a few hundred bytes
+   of stack space, which is a real killer in the recursive
+   evaluator.  So here are some helper functions for throwing
+   exceptions. */
+
+LocalNoInlineNoReturn(void throwEvalError(const char* s,
+                                          const std::string& s2)) {
+  throw EvalError(format(s) % s2);
+}
+
+LocalNoInlineNoReturn(void throwEvalError(const char* s, const std::string& s2,
+                                          const Pos& pos)) {
+  throw EvalError(format(s) % s2 % pos);
+}
+
+LocalNoInlineNoReturn(void throwEvalError(const char* s, const std::string& s2,
+                                          const std::string& s3)) {
+  throw EvalError(format(s) % s2 % s3);
+}
+
+LocalNoInlineNoReturn(void throwEvalError(const char* s, const std::string& s2,
+                                          const std::string& s3,
+                                          const Pos& pos)) {
+  throw EvalError(format(s) % s2 % s3 % pos);
+}
+
+LocalNoInlineNoReturn(void throwEvalError(const char* s, const Symbol& sym,
+                                          const Pos& p1, const Pos& p2)) {
+  throw EvalError(format(s) % sym % p1 % p2);
+}
+
+LocalNoInlineNoReturn(void throwTypeError(const char* s, const Pos& pos)) {
+  throw TypeError(format(s) % pos);
+}
+
+LocalNoInlineNoReturn(void throwTypeError(const char* s,
+                                          const std::string& s1)) {
+  throw TypeError(format(s) % s1);
+}
+
+LocalNoInlineNoReturn(void throwTypeError(const char* s, const ExprLambda& fun,
+                                          const Symbol& s2, const Pos& pos)) {
+  throw TypeError(format(s) % fun.showNamePos() % s2 % pos);
+}
+
+LocalNoInlineNoReturn(void throwAssertionError(const char* s,
+                                               const std::string& s1,
+                                               const Pos& pos)) {
+  throw AssertionError(format(s) % s1 % pos);
+}
+
+LocalNoInlineNoReturn(void throwUndefinedVarError(const char* s,
+                                                  const std::string& s1,
+                                                  const Pos& pos)) {
+  throw UndefinedVarError(format(s) % s1 % pos);
+}
+
+LocalNoInline(void addErrorPrefix(Error& e, const char* s,
+                                  const std::string& s2)) {
+  e.addPrefix(format(s) % s2);
+}
+
+LocalNoInline(void addErrorPrefix(Error& e, const char* s,
+                                  const ExprLambda& fun, const Pos& pos)) {
+  e.addPrefix(format(s) % fun.showNamePos() % pos);
+}
+
+LocalNoInline(void addErrorPrefix(Error& e, const char* s,
+                                  const std::string& s2, const Pos& pos)) {
+  e.addPrefix(format(s) % s2 % pos);
+}
+
+void mkString(Value& v, const char* s) { mkStringNoCopy(v, dupString(s)); }
+
+Value& mkString(Value& v, const std::string& s, const PathSet& context) {
+  mkString(v, s.c_str());
+  if (!context.empty()) {
+    size_t n = 0;
+    v.string.context =
+        (const char**)allocBytes((context.size() + 1) * sizeof(char*));
+    for (auto& i : context) {
+      v.string.context[n++] = dupString(i.c_str());
+    }
+    v.string.context[n] = nullptr;
+  }
+  return v;
+}
+
+void mkPath(Value& v, const char* s) { mkPathNoCopy(v, dupString(s)); }
+
+inline Value* EvalState::lookupVar(Env* env, const ExprVar& var, bool noEval) {
+  for (size_t l = var.level; l != 0u; --l, env = env->up) {
+    ;
+  }
+
+  if (!var.fromWith) {
+    return env->values[var.displ];
+  }
+
+  while (true) {
+    if (env->type == Env::HasWithExpr) {
+      if (noEval) {
+        return nullptr;
+      }
+      Value* v = allocValue();
+      evalAttrs(*env->up, (Expr*)env->values[0], *v);
+      env->values[0] = v;
+      env->type = Env::HasWithAttrs;
+    }
+    Bindings::iterator j = env->values[0]->attrs->find(var.name);
+    if (j != env->values[0]->attrs->end()) {
+      if (countCalls && (j->second.pos != nullptr)) {
+        attrSelects[*j->second.pos]++;
+      }
+      return j->second.value;
+    }
+    if (env->prevWith == 0u) {
+      throwUndefinedVarError("undefined variable '%1%' at %2%", var.name,
+                             var.pos);
+    }
+    for (size_t l = env->prevWith; l != 0u; --l, env = env->up) {
+    }
+  }
+}
+
+Value* EvalState::allocValue() {
+  nrValues++;
+  return new (GC) Value;
+}
+
+Env& EvalState::allocEnv(size_t size) {
+  if (size > std::numeric_limits<decltype(Env::size)>::max()) {
+    throw Error("environment size %d is too big", size);
+  }
+
+  nrEnvs++;
+  nrValuesInEnvs += size;
+  Env* env = (Env*)allocBytes(sizeof(Env) + size * sizeof(Value*));
+  env->size = (decltype(Env::size))size;
+  env->type = Env::Plain;
+
+  /* We assume that env->values has been cleared by the allocator; maybeThunk()
+   * and lookupVar fromWith expect this. */
+
+  return *env;
+}
+
+void EvalState::mkList(Value& v, size_t size) {
+  clearValue(v);
+  if (size == 1) {
+    v.type = tList1;
+  } else if (size == 2) {
+    v.type = tList2;
+  } else {
+    v.type = tListN;
+    v.bigList.size = size;
+    v.bigList.elems =
+        size != 0u ? (Value**)allocBytes(size * sizeof(Value*)) : nullptr;
+  }
+  nrListElems += size;
+}
+
+unsigned long nrThunks = 0;
+
+static inline void mkThunk(Value& v, Env& env, Expr* expr) {
+  v.type = tThunk;
+  v.thunk.env = &env;
+  v.thunk.expr = expr;
+  nrThunks++;
+}
+
+void EvalState::mkThunk_(Value& v, Expr* expr) { mkThunk(v, baseEnv, expr); }
+
+void EvalState::mkPos(Value& v, Pos* pos) {
+  if ((pos != nullptr) && pos->file.set()) {
+    mkAttrs(v, 3);
+    mkString(*allocAttr(v, sFile), pos->file);
+    mkInt(*allocAttr(v, sLine), pos->line);
+    mkInt(*allocAttr(v, sColumn), pos->column);
+  } else {
+    mkNull(v);
+  }
+}
+
+/* Create a thunk for the delayed computation of the given expression
+   in the given environment.  But if the expression is a variable,
+   then look it up right away.  This significantly reduces the number
+   of thunks allocated. */
+Value* Expr::maybeThunk(EvalState& state, Env& env) {
+  Value* v = state.allocValue();
+  mkThunk(*v, env, this);
+  return v;
+}
+
+unsigned long nrAvoided = 0;
+
+Value* ExprVar::maybeThunk(EvalState& state, Env& env) {
+  Value* v = state.lookupVar(&env, *this, true);
+  /* The value might not be initialised in the environment yet.
+     In that case, ignore it. */
+  if (v != nullptr) {
+    nrAvoided++;
+    return v;
+  }
+  return Expr::maybeThunk(state, env);
+}
+
+Value* ExprString::maybeThunk(EvalState& state, Env& env) {
+  nrAvoided++;
+  return &v;
+}
+
+Value* ExprInt::maybeThunk(EvalState& state, Env& env) {
+  nrAvoided++;
+  return &v;
+}
+
+Value* ExprFloat::maybeThunk(EvalState& state, Env& env) {
+  nrAvoided++;
+  return &v;
+}
+
+Value* ExprPath::maybeThunk(EvalState& state, Env& env) {
+  nrAvoided++;
+  return &v;
+}
+
+void EvalState::evalFile(const Path& path_, Value& v) {
+  auto path = checkSourcePath(path_);
+
+  FileEvalCache::iterator i;
+  if ((i = fileEvalCache.find(path)) != fileEvalCache.end()) {
+    v = i->second;
+    return;
+  }
+
+  Path path2 = resolveExprPath(path);
+  if ((i = fileEvalCache.find(path2)) != fileEvalCache.end()) {
+    v = i->second;
+    return;
+  }
+
+  DLOG(INFO) << "evaluating file '" << path2 << "'";
+  Expr* e = nullptr;
+
+  auto j = fileParseCache.find(path2);
+  if (j != fileParseCache.end()) {
+    e = j->second;
+  }
+
+  if (e == nullptr) {
+    e = parseExprFromFile(checkSourcePath(path2));
+  }
+
+  fileParseCache[path2] = e;
+
+  try {
+    eval(e, v);
+  } catch (Error& e) {
+    addErrorPrefix(e, "while evaluating the file '%1%':\n", path2);
+    throw;
+  }
+
+  fileEvalCache[path2] = v;
+  if (path != path2) {
+    fileEvalCache[path] = v;
+  }
+}
+
+void EvalState::resetFileCache() {
+  fileEvalCache.clear();
+  fileParseCache.clear();
+}
+
+void EvalState::eval(Expr* e, Value& v) { e->eval(*this, baseEnv, v); }
+
+inline bool EvalState::evalBool(Env& env, Expr* e) {
+  Value v;
+  e->eval(*this, env, v);
+  if (v.type != tBool) {
+    throwTypeError("value is %1% while a Boolean was expected", v);
+  }
+  return v.boolean;
+}
+
+inline bool EvalState::evalBool(Env& env, Expr* e, const Pos& pos) {
+  Value v;
+  e->eval(*this, env, v);
+  if (v.type != tBool) {
+    throwTypeError("value is %1% while a Boolean was expected, at %2%", v, pos);
+  }
+  return v.boolean;
+}
+
+inline void EvalState::evalAttrs(Env& env, Expr* e, Value& v) {
+  e->eval(*this, env, v);
+  if (v.type != tAttrs) {
+    throwTypeError("value is %1% while a set was expected", v);
+  }
+}
+
+void Expr::eval(EvalState& state, Env& env, Value& v) { abort(); }
+
+void ExprInt::eval(EvalState& state, Env& env, Value& v) { v = this->v; }
+
+void ExprFloat::eval(EvalState& state, Env& env, Value& v) { v = this->v; }
+
+void ExprString::eval(EvalState& state, Env& env, Value& v) { v = this->v; }
+
+void ExprPath::eval(EvalState& state, Env& env, Value& v) { v = this->v; }
+
+void ExprAttrs::eval(EvalState& state, Env& env, Value& v) {
+  state.mkAttrs(v, attrs.size() + dynamicAttrs.size());
+  Env* dynamicEnv = &env;
+
+  if (recursive) {
+    /* Create a new environment that contains the attributes in
+       this `rec'. */
+    Env& env2(state.allocEnv(attrs.size()));
+    env2.up = &env;
+    dynamicEnv = &env2;
+
+    // TODO(tazjin): contains?
+    AttrDefs::iterator overrides = attrs.find(state.sOverrides);
+    bool hasOverrides = overrides != attrs.end();
+
+    /* The recursive attributes are evaluated in the new
+       environment, while the inherited attributes are evaluated
+       in the original environment. */
+    size_t displ = 0;
+    for (auto& i : attrs) {
+      Value* vAttr;
+      if (hasOverrides && !i.second.inherited) {
+        vAttr = state.allocValue();
+        mkThunk(*vAttr, env2, i.second.e);
+      } else {
+        vAttr = i.second.e->maybeThunk(state, i.second.inherited ? env : env2);
+      }
+      env2.values[displ++] = vAttr;
+      v.attrs->push_back(Attr(i.first, vAttr, &i.second.pos));
+    }
+
+    /* If the rec contains an attribute called `__overrides', then
+       evaluate it, and add the attributes in that set to the rec.
+       This allows overriding of recursive attributes, which is
+       otherwise not possible.  (You can use the // operator to
+       replace an attribute, but other attributes in the rec will
+       still reference the original value, because that value has
+       been substituted into the bodies of the other attributes.
+       Hence we need __overrides.) */
+    if (hasOverrides) {
+      Value* vOverrides = v.attrs->find(overrides->first)->second.value;
+      state.forceAttrs(*vOverrides);
+      Bindings* newBnds = Bindings::NewGC();
+      for (auto& i : *v.attrs) {  // TODO(tazjin): copy constructor?
+        newBnds->push_back(i.second);
+      }
+      for (auto& i : *vOverrides->attrs) {
+        auto j = attrs.find(i.second.name);
+        if (j != attrs.end()) {
+          newBnds->push_back(i.second);
+          env2.values[j->second.displ] = i.second.value;
+        } else {
+          newBnds->push_back(i.second);
+        }
+      }
+      v.attrs = newBnds;
+    }
+  } else {
+    // TODO(tazjin): insert range
+    for (auto& i : attrs) {
+      v.attrs->push_back(
+          Attr(i.first, i.second.e->maybeThunk(state, env), &i.second.pos));
+    }
+  }
+
+  /* Dynamic attrs apply *after* rec and __overrides. */
+  for (auto& i : dynamicAttrs) {
+    Value nameVal;
+    i.nameExpr->eval(state, *dynamicEnv, nameVal);
+    state.forceValue(nameVal, i.pos);
+    if (nameVal.type == tNull) {
+      continue;
+    }
+    state.forceStringNoCtx(nameVal);
+    Symbol nameSym = state.symbols.Create(nameVal.string.s);
+    Bindings::iterator j = v.attrs->find(nameSym);
+    if (j != v.attrs->end()) {
+      throwEvalError("dynamic attribute '%1%' at %2% already defined at %3%",
+                     nameSym, i.pos, *j->second.pos);
+    }
+
+    i.valueExpr->setName(nameSym);
+    v.attrs->push_back(
+        Attr(nameSym, i.valueExpr->maybeThunk(state, *dynamicEnv), &i.pos));
+  }
+}
+
+void ExprLet::eval(EvalState& state, Env& env, Value& v) {
+  /* Create a new environment that contains the attributes in this
+     `let'. */
+  Env& env2(state.allocEnv(attrs->attrs.size()));
+  env2.up = &env;
+
+  /* The recursive attributes are evaluated in the new environment,
+     while the inherited attributes are evaluated in the original
+     environment. */
+  size_t displ = 0;
+  for (auto& i : attrs->attrs) {
+    env2.values[displ++] =
+        i.second.e->maybeThunk(state, i.second.inherited ? env : env2);
+  }
+
+  body->eval(state, env2, v);
+}
+
+void ExprList::eval(EvalState& state, Env& env, Value& v) {
+  state.mkList(v, elems.size());
+  for (size_t n = 0; n < elems.size(); ++n) {
+    v.listElems()[n] = elems[n]->maybeThunk(state, env);
+  }
+}
+
+void ExprVar::eval(EvalState& state, Env& env, Value& v) {
+  Value* v2 = state.lookupVar(&env, *this, false);
+  state.forceValue(*v2, pos);
+  v = *v2;
+}
+
+static std::string showAttrPath(EvalState& state, Env& env,
+                                const AttrPath& attrPath) {
+  std::ostringstream out;
+  bool first = true;
+  for (auto& i : attrPath) {
+    if (!first) {
+      out << '.';
+    } else {
+      first = false;
+    }
+    try {
+      out << getName(i, state, env);
+    } catch (Error& e) {
+      assert(!i.symbol.set());
+      out << "\"${" << *i.expr << "}\"";
+    }
+  }
+  return out.str();
+}
+
+unsigned long nrLookups = 0;
+
+void ExprSelect::eval(EvalState& state, Env& env, Value& v) {
+  Value vTmp;
+  Pos* pos2 = nullptr;
+  Value* vAttrs = &vTmp;
+
+  e->eval(state, env, vTmp);
+
+  try {
+    for (auto& i : attrPath) {
+      nrLookups++;
+      Bindings::iterator j;
+      Symbol name = getName(i, state, env);
+      if (def != nullptr) {
+        state.forceValue(*vAttrs, pos);
+        if (vAttrs->type != tAttrs ||
+            (j = vAttrs->attrs->find(name)) == vAttrs->attrs->end()) {
+          def->eval(state, env, v);
+          return;
+        }
+      } else {
+        state.forceAttrs(*vAttrs, pos);
+        if ((j = vAttrs->attrs->find(name)) == vAttrs->attrs->end()) {
+          throwEvalError("attribute '%1%' missing, at %2%", name, pos);
+        }
+      }
+      vAttrs = j->second.value;
+      pos2 = j->second.pos;
+      if (state.countCalls && (pos2 != nullptr)) {
+        state.attrSelects[*pos2]++;
+      }
+    }
+
+    state.forceValue(*vAttrs, (pos2 != nullptr ? *pos2 : this->pos));
+
+  } catch (Error& e) {
+    if ((pos2 != nullptr) && pos2->file != state.sDerivationNix) {
+      addErrorPrefix(e, "while evaluating the attribute '%1%' at %2%:\n",
+                     showAttrPath(state, env, attrPath), *pos2);
+    }
+    throw;
+  }
+
+  v = *vAttrs;
+}
+
+void ExprOpHasAttr::eval(EvalState& state, Env& env, Value& v) {
+  Value vTmp;
+  Value* vAttrs = &vTmp;
+
+  e->eval(state, env, vTmp);
+
+  for (auto& i : attrPath) {
+    state.forceValue(*vAttrs);
+    Bindings::iterator j;
+    Symbol name = getName(i, state, env);
+    if (vAttrs->type != tAttrs ||
+        (j = vAttrs->attrs->find(name)) == vAttrs->attrs->end()) {
+      mkBool(v, false);
+      return;
+    }
+    vAttrs = j->second.value;
+  }
+
+  mkBool(v, true);
+}
+
+void ExprLambda::eval(EvalState& state, Env& env, Value& v) {
+  v.type = tLambda;
+  v.lambda.env = &env;
+  v.lambda.fun = this;
+}
+
+void ExprApp::eval(EvalState& state, Env& env, Value& v) {
+  /* FIXME: vFun prevents GCC from doing tail call optimisation. */
+  Value vFun;
+  e1->eval(state, env, vFun);
+  state.callFunction(vFun, *(e2->maybeThunk(state, env)), v, pos);
+}
+
+void EvalState::callPrimOp(Value& fun, Value& arg, Value& v, const Pos& pos) {
+  /* Figure out the number of arguments still needed. */
+  size_t argsDone = 0;
+  Value* primOp = &fun;
+  while (primOp->type == tPrimOpApp) {
+    argsDone++;
+    primOp = primOp->primOpApp.left;
+  }
+  assert(primOp->type == tPrimOp);
+  auto arity = primOp->primOp->arity;
+  auto argsLeft = arity - argsDone;
+
+  if (argsLeft == 1) {
+    /* We have all the arguments, so call the primop. */
+
+    /* Put all the arguments in an array. */
+    Value* vArgs[arity];
+    auto n = arity - 1;
+    vArgs[n--] = &arg;
+    for (Value* arg = &fun; arg->type == tPrimOpApp;
+         arg = arg->primOpApp.left) {
+      vArgs[n--] = arg->primOpApp.right;
+    }
+
+    /* And call the primop. */
+    nrPrimOpCalls++;
+    if (countCalls) {
+      primOpCalls[primOp->primOp->name]++;
+    }
+    primOp->primOp->fun(*this, pos, vArgs, v);
+  } else {
+    Value* fun2 = allocValue();
+    *fun2 = fun;
+    v.type = tPrimOpApp;
+    v.primOpApp.left = fun2;
+    v.primOpApp.right = &arg;
+  }
+}
+
+void EvalState::callFunction(Value& fun, Value& arg, Value& v, const Pos& pos) {
+  auto trace = evalSettings.traceFunctionCalls
+                   ? std::make_unique<FunctionCallTrace>(pos)
+                   : nullptr;
+
+  forceValue(fun, pos);
+
+  if (fun.type == tPrimOp || fun.type == tPrimOpApp) {
+    callPrimOp(fun, arg, v, pos);
+    return;
+  }
+
+  if (fun.type == tAttrs) {
+    auto found = fun.attrs->find(sFunctor);
+    if (found != fun.attrs->end()) {
+      /* fun may be allocated on the stack of the calling function,
+       * but for functors we may keep a reference, so heap-allocate
+       * a copy and use that instead.
+       */
+      auto& fun2 = *allocValue();
+      fun2 = fun;
+      /* !!! Should we use the attr pos here? */
+      Value v2;
+      callFunction(*found->second.value, fun2, v2, pos);
+      return callFunction(v2, arg, v, pos);
+    }
+  }
+
+  if (fun.type != tLambda) {
+    throwTypeError(
+        "attempt to call something which is not a function but %1%, at %2%",
+        fun, pos);
+  }
+
+  ExprLambda& lambda(*fun.lambda.fun);
+
+  auto size = (lambda.arg.empty() ? 0 : 1) +
+              (lambda.matchAttrs ? lambda.formals->formals.size() : 0);
+  Env& env2(allocEnv(size));
+  env2.up = fun.lambda.env;
+
+  size_t displ = 0;
+
+  if (!lambda.matchAttrs) {
+    env2.values[displ++] = &arg;
+
+  } else {
+    forceAttrs(arg, pos);
+
+    if (!lambda.arg.empty()) {
+      env2.values[displ++] = &arg;
+    }
+
+    /* For each formal argument, get the actual argument.  If
+       there is no matching actual argument but the formal
+       argument has a default, use the default. */
+    size_t attrsUsed = 0;
+    for (auto& i : lambda.formals->formals) {
+      Bindings::iterator j = arg.attrs->find(i.name);
+      if (j == arg.attrs->end()) {
+        if (i.def == nullptr) {
+          throwTypeError("%1% called without required argument '%2%', at %3%",
+                         lambda, i.name, pos);
+        }
+        env2.values[displ++] = i.def->maybeThunk(*this, env2);
+      } else {
+        attrsUsed++;
+        env2.values[displ++] = j->second.value;
+      }
+    }
+
+    /* Check that each actual argument is listed as a formal
+       argument (unless the attribute match specifies a `...'). */
+    if (!lambda.formals->ellipsis && attrsUsed != arg.attrs->size()) {
+      /* Nope, so show the first unexpected argument to the
+         user. */
+      for (auto& i : *arg.attrs) {
+        if (lambda.formals->argNames.find(i.second.name) ==
+            lambda.formals->argNames.end()) {
+          throwTypeError("%1% called with unexpected argument '%2%', at %3%",
+                         lambda, i.second.name, pos);
+        }
+      }
+      abort();  // can't happen
+    }
+  }
+
+  nrFunctionCalls++;
+  if (countCalls) {
+    incrFunctionCall(&lambda);
+  }
+
+  /* Evaluate the body.  This is conditional on showTrace, because
+     catching exceptions makes this function not tail-recursive. */
+  if (settings.showTrace) {
+    try {
+      lambda.body->eval(*this, env2, v);
+    } catch (Error& e) {
+      addErrorPrefix(e, "while evaluating %1%, called from %2%:\n", lambda,
+                     pos);
+      throw;
+    }
+  } else {
+    fun.lambda.fun->body->eval(*this, env2, v);
+  }
+}
+
+// Lifted out of callFunction() because it creates a temporary that
+// prevents tail-call optimisation.
+void EvalState::incrFunctionCall(ExprLambda* fun) { functionCalls[fun]++; }
+
+void EvalState::autoCallFunction(Bindings& args, Value& fun, Value& res) {
+  forceValue(fun);
+
+  if (fun.type == tAttrs) {
+    auto found = fun.attrs->find(sFunctor);
+    if (found != fun.attrs->end()) {
+      Value* v = allocValue();
+      callFunction(*found->second.value, fun, *v, noPos);
+      forceValue(*v);
+      return autoCallFunction(args, *v, res);
+    }
+  }
+
+  if (fun.type != tLambda || !fun.lambda.fun->matchAttrs) {
+    res = fun;
+    return;
+  }
+
+  Value* actualArgs = allocValue();
+  mkAttrs(*actualArgs, fun.lambda.fun->formals->formals.size());
+
+  for (auto& i : fun.lambda.fun->formals->formals) {
+    Bindings::iterator j = args.find(i.name);
+    if (j != args.end()) {
+      actualArgs->attrs->push_back(j->second);
+    } else if (i.def == nullptr) {
+      throwTypeError(
+          "cannot auto-call a function that has an argument without a default "
+          "value ('%1%')",
+          i.name);
+    }
+  }
+
+  callFunction(fun, *actualArgs, res, noPos);
+}
+
+void ExprWith::eval(EvalState& state, Env& env, Value& v) {
+  Env& env2(state.allocEnv(1));
+  env2.up = &env;
+  env2.prevWith = prevWith;
+  env2.type = Env::HasWithExpr;
+  env2.values[0] = (Value*)attrs;
+
+  body->eval(state, env2, v);
+}
+
+void ExprIf::eval(EvalState& state, Env& env, Value& v) {
+  (state.evalBool(env, cond) ? then : else_)->eval(state, env, v);
+}
+
+void ExprAssert::eval(EvalState& state, Env& env, Value& v) {
+  if (!state.evalBool(env, cond, pos)) {
+    std::ostringstream out;
+    cond->show(out);
+    throwAssertionError("assertion %1% failed at %2%", out.str(), pos);
+  }
+  body->eval(state, env, v);
+}
+
+void ExprOpNot::eval(EvalState& state, Env& env, Value& v) {
+  mkBool(v, !state.evalBool(env, e));
+}
+
+void ExprOpEq::eval(EvalState& state, Env& env, Value& v) {
+  Value v1;
+  e1->eval(state, env, v1);
+  Value v2;
+  e2->eval(state, env, v2);
+  mkBool(v, state.eqValues(v1, v2));
+}
+
+void ExprOpNEq::eval(EvalState& state, Env& env, Value& v) {
+  Value v1;
+  e1->eval(state, env, v1);
+  Value v2;
+  e2->eval(state, env, v2);
+  mkBool(v, !state.eqValues(v1, v2));
+}
+
+void ExprOpAnd::eval(EvalState& state, Env& env, Value& v) {
+  mkBool(v, state.evalBool(env, e1, pos) && state.evalBool(env, e2, pos));
+}
+
+void ExprOpOr::eval(EvalState& state, Env& env, Value& v) {
+  mkBool(v, state.evalBool(env, e1, pos) || state.evalBool(env, e2, pos));
+}
+
+void ExprOpImpl::eval(EvalState& state, Env& env, Value& v) {
+  mkBool(v, !state.evalBool(env, e1, pos) || state.evalBool(env, e2, pos));
+}
+
+void ExprOpUpdate::eval(EvalState& state, Env& env, Value& v) {
+  Value v1;
+  Value v2;
+  state.evalAttrs(env, e1, v1);
+  state.evalAttrs(env, e2, v2);
+
+  state.nrOpUpdates++;
+
+  if (v1.attrs->empty()) {
+    v = v2;
+    return;
+  }
+  if (v2.attrs->empty()) {
+    v = v1;
+    return;
+  }
+
+  state.mkAttrs(v, /* capacity = */ 0);
+
+  /* Merge the sets, preferring values from the second set.  Make
+     sure to keep the resulting vector in sorted order. */
+  v.attrs->merge(v1.attrs);
+  v.attrs->merge(v2.attrs);
+
+  state.nrOpUpdateValuesCopied += v.attrs->size();
+}
+
+void ExprOpConcatLists::eval(EvalState& state, Env& env, Value& v) {
+  Value v1;
+  e1->eval(state, env, v1);
+  Value v2;
+  e2->eval(state, env, v2);
+  Value* lists[2] = {&v1, &v2};
+  state.concatLists(v, 2, lists, pos);
+}
+
+void EvalState::concatLists(Value& v, size_t nrLists, Value** lists,
+                            const Pos& pos) {
+  nrListConcats++;
+
+  Value* nonEmpty = nullptr;
+  size_t len = 0;
+  for (size_t n = 0; n < nrLists; ++n) {
+    forceList(*lists[n], pos);
+    auto l = lists[n]->listSize();
+    len += l;
+    if (l != 0u) {
+      nonEmpty = lists[n];
+    }
+  }
+
+  if ((nonEmpty != nullptr) && len == nonEmpty->listSize()) {
+    v = *nonEmpty;
+    return;
+  }
+
+  mkList(v, len);
+  auto out = v.listElems();
+  for (size_t n = 0, pos = 0; n < nrLists; ++n) {
+    auto l = lists[n]->listSize();
+    if (l != 0u) {
+      memcpy(out + pos, lists[n]->listElems(), l * sizeof(Value*));
+    }
+    pos += l;
+  }
+}
+
+void ExprConcatStrings::eval(EvalState& state, Env& env, Value& v) {
+  PathSet context;
+  std::ostringstream s;
+  NixInt n = 0;
+  NixFloat nf = 0;
+
+  bool first = !forceString;
+  ValueType firstType = tString;
+
+  for (auto& i : *es) {
+    Value vTmp;
+    i->eval(state, env, vTmp);
+
+    /* If the first element is a path, then the result will also
+       be a path, we don't copy anything (yet - that's done later,
+       since paths are copied when they are used in a derivation),
+       and none of the strings are allowed to have contexts. */
+    if (first) {
+      firstType = vTmp.type;
+      first = false;
+    }
+
+    if (firstType == tInt) {
+      if (vTmp.type == tInt) {
+        n += vTmp.integer;
+      } else if (vTmp.type == tFloat) {
+        // Upgrade the type from int to float;
+        firstType = tFloat;
+        nf = n;
+        nf += vTmp.fpoint;
+      } else {
+        throwEvalError("cannot add %1% to an integer, at %2%", showType(vTmp),
+                       pos);
+      }
+    } else if (firstType == tFloat) {
+      if (vTmp.type == tInt) {
+        nf += vTmp.integer;
+      } else if (vTmp.type == tFloat) {
+        nf += vTmp.fpoint;
+      } else {
+        throwEvalError("cannot add %1% to a float, at %2%", showType(vTmp),
+                       pos);
+      }
+    } else {
+      s << state.coerceToString(pos, vTmp, context, false,
+                                firstType == tString);
+    }
+  }
+
+  if (firstType == tInt) {
+    mkInt(v, n);
+  } else if (firstType == tFloat) {
+    mkFloat(v, nf);
+  } else if (firstType == tPath) {
+    if (!context.empty()) {
+      throwEvalError(
+          "a string that refers to a store path cannot be appended to a path, "
+          "at %1%",
+          pos);
+    }
+    auto path = canonPath(s.str());
+    mkPath(v, path.c_str());
+  } else {
+    mkString(v, s.str(), context);
+  }
+}
+
+void ExprPos::eval(EvalState& state, Env& env, Value& v) {
+  state.mkPos(v, &pos);
+}
+
+void EvalState::forceValueDeep(Value& v) {
+  std::set<const Value*> seen;
+
+  std::function<void(Value & v)> recurse;
+
+  recurse = [&](Value& v) {
+    if (seen.find(&v) != seen.end()) {
+      return;
+    }
+    seen.insert(&v);
+
+    forceValue(v);
+
+    if (v.type == tAttrs) {
+      for (auto& i : *v.attrs) {
+        try {
+          recurse(*i.second.value);
+        } catch (Error& e) {
+          addErrorPrefix(e, "while evaluating the attribute '%1%' at %2%:\n",
+                         i.second.name, *i.second.pos);
+          throw;
+        }
+      }
+    } else if (v.isList()) {
+      for (size_t n = 0; n < v.listSize(); ++n) {
+        recurse(*v.listElems()[n]);
+      }
+    }
+  };
+
+  recurse(v);
+}
+
+NixInt EvalState::forceInt(Value& v, const Pos& pos) {
+  forceValue(v, pos);
+  if (v.type != tInt) {
+    throwTypeError("value is %1% while an integer was expected, at %2%", v,
+                   pos);
+  }
+  return v.integer;
+}
+
+NixFloat EvalState::forceFloat(Value& v, const Pos& pos) {
+  forceValue(v, pos);
+  if (v.type == tInt) {
+    return v.integer;
+  }
+  if (v.type != tFloat) {
+    throwTypeError("value is %1% while a float was expected, at %2%", v, pos);
+  }
+  return v.fpoint;
+}
+
+bool EvalState::forceBool(Value& v, const Pos& pos) {
+  forceValue(v);
+  if (v.type != tBool) {
+    throwTypeError("value is %1% while a Boolean was expected, at %2%", v, pos);
+  }
+  return v.boolean;
+}
+
+bool EvalState::isFunctor(Value& fun) {
+  return fun.type == tAttrs && fun.attrs->find(sFunctor) != fun.attrs->end();
+}
+
+void EvalState::forceFunction(Value& v, const Pos& pos) {
+  forceValue(v);
+  if (v.type != tLambda && v.type != tPrimOp && v.type != tPrimOpApp &&
+      !isFunctor(v)) {
+    throwTypeError("value is %1% while a function was expected, at %2%", v,
+                   pos);
+  }
+}
+
+string EvalState::forceString(Value& v, const Pos& pos) {
+  forceValue(v, pos);
+  if (v.type != tString) {
+    if (pos) {
+      throwTypeError("value is %1% while a string was expected, at %2%", v,
+                     pos);
+    } else {
+      throwTypeError("value is %1% while a string was expected", v);
+    }
+  }
+  return string(v.string.s);
+}
+
+void copyContext(const Value& v, PathSet& context) {
+  if (v.string.context != nullptr) {
+    for (const char** p = v.string.context; *p != nullptr; ++p) {
+      context.insert(*p);
+    }
+  }
+}
+
+string EvalState::forceString(Value& v, PathSet& context, const Pos& pos) {
+  std::string s = forceString(v, pos);
+  copyContext(v, context);
+  return s;
+}
+
+string EvalState::forceStringNoCtx(Value& v, const Pos& pos) {
+  std::string s = forceString(v, pos);
+  if (v.string.context != nullptr) {
+    if (pos) {
+      throwEvalError(
+          "the string '%1%' is not allowed to refer to a store path (such as "
+          "'%2%'), at %3%",
+          v.string.s, v.string.context[0], pos);
+    } else {
+      throwEvalError(
+          "the string '%1%' is not allowed to refer to a store path (such as "
+          "'%2%')",
+          v.string.s, v.string.context[0]);
+    }
+  }
+  return s;
+}
+
+bool EvalState::isDerivation(Value& v) {
+  if (v.type != tAttrs) {
+    return false;
+  }
+  Bindings::iterator i = v.attrs->find(sType);
+  if (i == v.attrs->end()) {
+    return false;
+  }
+  forceValue(*i->second.value);
+  if (i->second.value->type != tString) {
+    return false;
+  }
+  return strcmp(i->second.value->string.s, "derivation") == 0;
+}
+
+std::optional<string> EvalState::tryAttrsToString(const Pos& pos, Value& v,
+                                                  PathSet& context,
+                                                  bool coerceMore,
+                                                  bool copyToStore) {
+  auto i = v.attrs->find(sToString);
+  if (i != v.attrs->end()) {
+    Value v1;
+    callFunction(*i->second.value, v, v1, pos);
+    return coerceToString(pos, v1, context, coerceMore, copyToStore);
+  }
+
+  return {};
+}
+
+string EvalState::coerceToString(const Pos& pos, Value& v, PathSet& context,
+                                 bool coerceMore, bool copyToStore) {
+  forceValue(v);
+
+  std::string s;
+
+  if (v.type == tString) {
+    copyContext(v, context);
+    return v.string.s;
+  }
+
+  if (v.type == tPath) {
+    Path path(canonPath(v.path));
+    return copyToStore ? copyPathToStore(context, path) : path;
+  }
+
+  if (v.type == tAttrs) {
+    auto maybeString =
+        tryAttrsToString(pos, v, context, coerceMore, copyToStore);
+    if (maybeString) {
+      return *maybeString;
+    }
+    auto i = v.attrs->find(sOutPath);
+    if (i == v.attrs->end()) {
+      throwTypeError("cannot coerce a set to a string, at %1%", pos);
+    }
+    return coerceToString(pos, *i->second.value, context, coerceMore,
+                          copyToStore);
+  }
+
+  if (v.type == tExternal) {
+    return v.external->coerceToString(pos, context, coerceMore, copyToStore);
+  }
+
+  if (coerceMore) {
+    /* Note that `false' is represented as an empty string for
+       shell scripting convenience, just like `null'. */
+    if (v.type == tBool && v.boolean) {
+      return "1";
+    }
+    if (v.type == tBool && !v.boolean) {
+      return "";
+    }
+    if (v.type == tInt) {
+      return std::to_string(v.integer);
+    }
+    if (v.type == tFloat) {
+      return std::to_string(v.fpoint);
+    }
+    if (v.type == tNull) {
+      return "";
+    }
+
+    if (v.isList()) {
+      std::string result;
+      for (size_t n = 0; n < v.listSize(); ++n) {
+        result += coerceToString(pos, *v.listElems()[n], context, coerceMore,
+                                 copyToStore);
+        if (n < v.listSize() - 1
+            /* !!! not quite correct */
+            && (!v.listElems()[n]->isList() ||
+                v.listElems()[n]->listSize() != 0)) {
+          result += " ";
+        }
+      }
+      return result;
+    }
+  }
+
+  throwTypeError("cannot coerce %1% to a string, at %2%", v, pos);
+}
+
+string EvalState::copyPathToStore(PathSet& context, const Path& path) {
+  if (nix::isDerivation(path)) {
+    throwEvalError("file names are not allowed to end in '%1%'", drvExtension);
+  }
+
+  Path dstPath;
+  if (!srcToStore[path].empty()) {
+    dstPath = srcToStore[path];
+  } else {
+    dstPath =
+        settings.readOnlyMode
+            ? store
+                  ->computeStorePathForPath(baseNameOf(path),
+                                            checkSourcePath(path))
+                  .first
+            : store->addToStore(baseNameOf(path), checkSourcePath(path), true,
+                                htSHA256, defaultPathFilter, repair);
+    srcToStore[path] = dstPath;
+    DLOG(INFO) << "copied source '" << path << "' -> '" << dstPath << "'";
+  }
+
+  context.insert(dstPath);
+  return dstPath;
+}
+
+Path EvalState::coerceToPath(const Pos& pos, Value& v, PathSet& context) {
+  std::string path = coerceToString(pos, v, context, false, false);
+  if (path.empty() || path[0] != '/') {
+    throwEvalError("string '%1%' doesn't represent an absolute path, at %2%",
+                   path, pos);
+  }
+  return path;
+}
+
+bool EvalState::eqValues(Value& v1, Value& v2) {
+  forceValue(v1);
+  forceValue(v2);
+
+  /* !!! Hack to support some old broken code that relies on pointer
+     equality tests between sets.  (Specifically, builderDefs calls
+     uniqList on a list of sets.)  Will remove this eventually. */
+  if (&v1 == &v2) {
+    return true;
+  }
+
+  // Special case type-compatibility between float and int
+  if (v1.type == tInt && v2.type == tFloat) {
+    return v1.integer == v2.fpoint;
+  }
+  if (v1.type == tFloat && v2.type == tInt) {
+    return v1.fpoint == v2.integer;
+  }
+
+  // All other types are not compatible with each other.
+  if (v1.type != v2.type) {
+    return false;
+  }
+
+  switch (v1.type) {
+    case tInt:
+      return v1.integer == v2.integer;
+
+    case tBool:
+      return v1.boolean == v2.boolean;
+
+    case tString:
+      return strcmp(v1.string.s, v2.string.s) == 0;
+
+    case tPath:
+      return strcmp(v1.path, v2.path) == 0;
+
+    case tNull:
+      return true;
+
+    case tList1:
+    case tList2:
+    case tListN:
+      if (v1.listSize() != v2.listSize()) {
+        return false;
+      }
+      for (size_t n = 0; n < v1.listSize(); ++n) {
+        if (!eqValues(*v1.listElems()[n], *v2.listElems()[n])) {
+          return false;
+        }
+      }
+      return true;
+
+    case tAttrs: {
+      /* If both sets denote a derivation (type = "derivation"),
+         then compare their outPaths. */
+      if (isDerivation(v1) && isDerivation(v2)) {
+        Bindings::iterator i = v1.attrs->find(sOutPath);
+        Bindings::iterator j = v2.attrs->find(sOutPath);
+        if (i != v1.attrs->end() && j != v2.attrs->end()) {
+          return eqValues(*i->second.value, *j->second.value);
+        }
+      }
+
+      if (v1.attrs->size() != v2.attrs->size()) {
+        return false;
+      }
+
+      /* Otherwise, compare the attributes one by one. */
+      Bindings::iterator i;
+      Bindings::iterator j;
+      for (i = v1.attrs->begin(), j = v2.attrs->begin(); i != v1.attrs->end();
+           ++i, ++j) {
+        if (i->second.name != j->second.name ||
+            !eqValues(*i->second.value, *j->second.value)) {
+          return false;
+        }
+      }
+
+      return true;
+    }
+
+    /* Functions are incomparable. */
+    case tLambda:
+    case tPrimOp:
+    case tPrimOpApp:
+      return false;
+
+    case tExternal:
+      return *v1.external == *v2.external;
+
+    case tFloat:
+      return v1.fpoint == v2.fpoint;
+
+    default:
+      throwEvalError("cannot compare %1% with %2%", showType(v1), showType(v2));
+  }
+}
+
+void EvalState::printStats() {
+  bool showStats = getEnv("NIX_SHOW_STATS", "0") != "0";
+
+  struct rusage buf;
+  getrusage(RUSAGE_SELF, &buf);
+  float cpuTime = buf.ru_utime.tv_sec + ((float)buf.ru_utime.tv_usec / 1000000);
+
+  uint64_t bEnvs = nrEnvs * sizeof(Env) + nrValuesInEnvs * sizeof(Value*);
+  uint64_t bLists = nrListElems * sizeof(Value*);
+  uint64_t bValues = nrValues * sizeof(Value);
+  uint64_t bAttrsets =
+      nrAttrsets * sizeof(Bindings) + nrAttrsInAttrsets * sizeof(Attr);
+
+#if HAVE_BOEHMGC
+  GC_word heapSize;
+  GC_word totalBytes;
+  GC_get_heap_usage_safe(&heapSize, nullptr, nullptr, nullptr, &totalBytes);
+#endif
+  if (showStats) {
+    auto outPath = getEnv("NIX_SHOW_STATS_PATH", "-");
+    std::fstream fs;
+    if (outPath != "-") {
+      fs.open(outPath, std::fstream::out);
+    }
+    JSONObject topObj(outPath == "-" ? std::cerr : fs, true);
+    topObj.attr("cpuTime", cpuTime);
+    {
+      auto envs = topObj.object("envs");
+      envs.attr("number", nrEnvs);
+      envs.attr("elements", nrValuesInEnvs);
+      envs.attr("bytes", bEnvs);
+    }
+    {
+      auto lists = topObj.object("list");
+      lists.attr("elements", nrListElems);
+      lists.attr("bytes", bLists);
+      lists.attr("concats", nrListConcats);
+    }
+    {
+      auto values = topObj.object("values");
+      values.attr("number", nrValues);
+      values.attr("bytes", bValues);
+    }
+    {
+      auto syms = topObj.object("symbols");
+      syms.attr("number", symbols.Size());
+      syms.attr("bytes", symbols.TotalSize());
+    }
+    {
+      auto sets = topObj.object("sets");
+      sets.attr("number", nrAttrsets);
+      sets.attr("bytes", bAttrsets);
+      sets.attr("elements", nrAttrsInAttrsets);
+    }
+    {
+      auto sizes = topObj.object("sizes");
+      sizes.attr("Env", sizeof(Env));
+      sizes.attr("Value", sizeof(Value));
+      sizes.attr("Bindings", sizeof(Bindings));
+      sizes.attr("Attr", sizeof(Attr));
+    }
+    topObj.attr("nrOpUpdates", nrOpUpdates);
+    topObj.attr("nrOpUpdateValuesCopied", nrOpUpdateValuesCopied);
+    topObj.attr("nrThunks", nrThunks);
+    topObj.attr("nrAvoided", nrAvoided);
+    topObj.attr("nrLookups", nrLookups);
+    topObj.attr("nrPrimOpCalls", nrPrimOpCalls);
+    topObj.attr("nrFunctionCalls", nrFunctionCalls);
+#if HAVE_BOEHMGC
+    {
+      auto gc = topObj.object("gc");
+      gc.attr("heapSize", heapSize);
+      gc.attr("totalBytes", totalBytes);
+    }
+#endif
+
+    if (countCalls) {
+      {
+        auto obj = topObj.object("primops");
+        for (auto& i : primOpCalls) {
+          obj.attr(i.first, i.second);
+        }
+      }
+      {
+        auto list = topObj.list("functions");
+        for (auto& i : functionCalls) {
+          auto obj = list.object();
+          if (i.first->name.set()) {
+            obj.attr("name", (const std::string&)i.first->name);
+          } else {
+            obj.attr("name", nullptr);
+          }
+          if (i.first->pos) {
+            obj.attr("file", (const std::string&)i.first->pos.file);
+            obj.attr("line", i.first->pos.line);
+            obj.attr("column", i.first->pos.column);
+          }
+          obj.attr("count", i.second);
+        }
+      }
+      {
+        auto list = topObj.list("attributes");
+        for (auto& i : attrSelects) {
+          auto obj = list.object();
+          if (i.first) {
+            obj.attr("file", (const std::string&)i.first.file);
+            obj.attr("line", i.first.line);
+            obj.attr("column", i.first.column);
+          }
+          obj.attr("count", i.second);
+        }
+      }
+    }
+
+    // TODO(tazjin): what is this? commented out because .dump() is gone.
+    // if (getEnv("NIX_SHOW_SYMBOLS", "0") != "0") {
+    //   auto list = topObj.list("symbols");
+    //   symbols.dump([&](const std::string& s) { list.elem(s); });
+    // }
+  }
+}
+
+size_t valueSize(Value& v) {
+  std::set<const void*> seen;
+
+  auto doString = [&](const char* s) -> size_t {
+    if (seen.find(s) != seen.end()) {
+      return 0;
+    }
+    seen.insert(s);
+    return strlen(s) + 1;
+  };
+
+  std::function<size_t(Value & v)> doValue;
+  std::function<size_t(Env & v)> doEnv;
+
+  doValue = [&](Value& v) -> size_t {
+    if (seen.find(&v) != seen.end()) {
+      return 0;
+    }
+    seen.insert(&v);
+
+    size_t sz = sizeof(Value);
+
+    switch (v.type) {
+      case tString:
+        sz += doString(v.string.s);
+        if (v.string.context != nullptr) {
+          for (const char** p = v.string.context; *p != nullptr; ++p) {
+            sz += doString(*p);
+          }
+        }
+        break;
+      case tPath:
+        sz += doString(v.path);
+        break;
+      case tAttrs:
+        if (seen.find(v.attrs) == seen.end()) {
+          seen.insert(v.attrs);
+          sz += sizeof(Bindings) + sizeof(Attr) * v.attrs->capacity();
+          for (auto& i : *v.attrs) {
+            sz += doValue(*i.second.value);
+          }
+        }
+        break;
+      case tList1:
+      case tList2:
+      case tListN:
+        if (seen.find(v.listElems()) == seen.end()) {
+          seen.insert(v.listElems());
+          sz += v.listSize() * sizeof(Value*);
+          for (size_t n = 0; n < v.listSize(); ++n) {
+            sz += doValue(*v.listElems()[n]);
+          }
+        }
+        break;
+      case tThunk:
+        sz += doEnv(*v.thunk.env);
+        break;
+      case tApp:
+        sz += doValue(*v.app.left);
+        sz += doValue(*v.app.right);
+        break;
+      case tLambda:
+        sz += doEnv(*v.lambda.env);
+        break;
+      case tPrimOpApp:
+        sz += doValue(*v.primOpApp.left);
+        sz += doValue(*v.primOpApp.right);
+        break;
+      case tExternal:
+        if (seen.find(v.external) != seen.end()) {
+          break;
+        }
+        seen.insert(v.external);
+        sz += v.external->valueSize(seen);
+        break;
+      default:;
+    }
+
+    return sz;
+  };
+
+  doEnv = [&](Env& env) -> size_t {
+    if (seen.find(&env) != seen.end()) {
+      return 0;
+    }
+    seen.insert(&env);
+
+    size_t sz = sizeof(Env) + sizeof(Value*) * env.size;
+
+    if (env.type != Env::HasWithExpr) {
+      for (size_t i = 0; i < env.size; ++i) {
+        if (env.values[i] != nullptr) {
+          sz += doValue(*env.values[i]);
+        }
+      }
+    }
+
+    if (env.up != nullptr) {
+      sz += doEnv(*env.up);
+    }
+
+    return sz;
+  };
+
+  return doValue(v);
+}
+
+string ExternalValueBase::coerceToString(const Pos& pos, PathSet& context,
+                                         bool copyMore,
+                                         bool copyToStore) const {
+  throw TypeError(format("cannot coerce %1% to a string, at %2%") % showType() %
+                  pos);
+}
+
+bool ExternalValueBase::operator==(const ExternalValueBase& b) const {
+  return false;
+}
+
+std::ostream& operator<<(std::ostream& str, const ExternalValueBase& v) {
+  return v.print(str);
+}
+
+EvalSettings evalSettings;
+
+static GlobalConfig::Register r1(&evalSettings);
+
+}  // namespace nix