24 files changed, 6151 insertions, 0 deletions

diff --git a/src/libexpr/attr-path.cc b/src/libexpr/attr-path.cc
new file mode 100644
index 000000000000..4f28a549f035
--- /dev/null
+++ b/src/libexpr/attr-path.cc
@@ -0,0 +1,97 @@
+#include "attr-path.hh"
+#include "eval-inline.hh"
+#include "util.hh"
+
+
+namespace nix {
+
+
+static Strings parseAttrPath(const string & s)
+{
+    Strings res;
+    string cur;
+    string::const_iterator i = s.begin();
+    while (i != s.end()) {
+        if (*i == '.') {
+            res.push_back(cur);
+            cur.clear();
+        } else if (*i == '"') {
+            ++i;
+            while (1) {
+                if (i == s.end())
+                    throw Error(format("missing closing quote in selection path `%1%'") % s);
+                if (*i == '"') break;
+                cur.push_back(*i++);
+            }
+        } else
+            cur.push_back(*i);
+        ++i;
+    }
+    if (!cur.empty()) res.push_back(cur);
+    return res;
+}
+
+
+Value * findAlongAttrPath(EvalState & state, const string & attrPath,
+    Bindings & autoArgs, Value & vIn)
+{
+    Strings tokens = parseAttrPath(attrPath);
+
+    Error attrError =
+        Error(format("attribute selection path `%1%' does not match expression") % attrPath);
+
+    Value * v = &vIn;
+
+    foreach (Strings::iterator, i, tokens) {
+
+        /* Is *i an index (integer) or a normal attribute name? */
+        enum { apAttr, apIndex } apType = apAttr;
+        string attr = *i;
+        unsigned int attrIndex;
+        if (string2Int(attr, attrIndex)) apType = apIndex;
+
+        /* Evaluate the expression. */
+        Value * vNew = state.allocValue();
+        state.autoCallFunction(autoArgs, *v, *vNew);
+        v = vNew;
+        state.forceValue(*v);
+
+        /* It should evaluate to either a set or an expression,
+           according to what is specified in the attrPath. */
+
+        if (apType == apAttr) {
+
+            if (v->type != tAttrs)
+                throw TypeError(
+                    format("the expression selected by the selection path `%1%' should be a set but is %2%")
+                    % attrPath % showType(*v));
+
+            if (attr.empty())
+                throw Error(format("empty attribute name in selection path `%1%'") % attrPath);
+
+            Bindings::iterator a = v->attrs->find(state.symbols.create(attr));
+            if (a == v->attrs->end())
+                throw Error(format("attribute `%1%' in selection path `%2%' not found") % attr % attrPath);
+            v = &*a->value;
+        }
+
+        else if (apType == apIndex) {
+
+            if (v->type != tList)
+                throw TypeError(
+                    format("the expression selected by the selection path `%1%' should be a list but is %2%")
+                    % attrPath % showType(*v));
+
+            if (attrIndex >= v->list.length)
+                throw Error(format("list index %1% in selection path `%2%' is out of range") % attrIndex % attrPath);
+
+            v = v->list.elems[attrIndex];
+        }
+
+    }
+
+    return v;
+}
+
+
+}
diff --git a/src/libexpr/attr-path.hh b/src/libexpr/attr-path.hh
new file mode 100644
index 000000000000..46a341950939
--- /dev/null
+++ b/src/libexpr/attr-path.hh
@@ -0,0 +1,13 @@
+#pragma once
+
+#include "eval.hh"
+
+#include <string>
+#include <map>
+
+namespace nix {
+
+Value * findAlongAttrPath(EvalState & state, const string & attrPath,
+    Bindings & autoArgs, Value & vIn);
+
+}
diff --git a/src/libexpr/common-opts.cc b/src/libexpr/common-opts.cc
new file mode 100644
index 000000000000..0ee889a995ef
--- /dev/null
+++ b/src/libexpr/common-opts.cc
@@ -0,0 +1,59 @@
+#include "common-opts.hh"
+#include "../libmain/shared.hh"
+#include "util.hh"
+
+
+namespace nix {
+
+
+bool parseOptionArg(const string & arg, Strings::iterator & i,
+    const Strings::iterator & argsEnd, EvalState & state,
+    Bindings & autoArgs)
+{
+    if (arg != "--arg" && arg != "--argstr") return false;
+
+    UsageError error(format("`%1%' requires two arguments") % arg);
+    
+    if (i == argsEnd) throw error;
+    string name = *i++;
+    if (i == argsEnd) throw error;
+    string value = *i++;
+
+    /* !!! check for duplicates! */
+    Value * v = state.allocValue();
+    autoArgs.push_back(Attr(state.symbols.create(name), v));
+
+    if (arg == "--arg")
+        state.mkThunk_(*v, state.parseExprFromString(value, absPath(".")));
+    else
+        mkString(*v, value);
+
+    autoArgs.sort(); // !!! inefficient
+
+    return true;
+}
+
+
+bool parseSearchPathArg(const string & arg, Strings::iterator & i,
+    const Strings::iterator & argsEnd, EvalState & state)
+{
+    if (arg != "-I") return false;
+    if (i == argsEnd) throw UsageError(format("`%1%' requires an argument") % arg);;
+    state.addToSearchPath(*i++);
+    return true;
+}
+
+
+Path lookupFileArg(EvalState & state, string s)
+{
+    if (s.size() > 2 && s.at(0) == '<' && s.at(s.size() - 1) == '>') {
+        Path p = s.substr(1, s.size() - 2);
+        Path p2 = state.findFile(p);
+        if (p2 == "") throw Error(format("file `%1%' was not found in the Nix search path (add it using $NIX_PATH or -I)") % p);
+        return p2;
+    } else
+        return absPath(s);
+}
+
+
+}
diff --git a/src/libexpr/common-opts.hh b/src/libexpr/common-opts.hh
new file mode 100644
index 000000000000..e2e3fe77171c
--- /dev/null
+++ b/src/libexpr/common-opts.hh
@@ -0,0 +1,17 @@
+#pragma once
+
+#include "eval.hh"
+
+namespace nix {
+
+/* Some common option parsing between nix-env and nix-instantiate. */
+bool parseOptionArg(const string & arg, Strings::iterator & i,
+    const Strings::iterator & argsEnd, EvalState & state,
+    Bindings & autoArgs);
+    
+bool parseSearchPathArg(const string & arg, Strings::iterator & i,
+    const Strings::iterator & argsEnd, EvalState & state);
+
+Path lookupFileArg(EvalState & state, string s);
+
+}
diff --git a/src/libexpr/eval-inline.hh b/src/libexpr/eval-inline.hh
new file mode 100644
index 000000000000..5801a20c3b10
--- /dev/null
+++ b/src/libexpr/eval-inline.hh
@@ -0,0 +1,59 @@
+#pragma once
+
+#include "eval.hh"
+
+#define LocalNoInline(f) static f __attribute__((noinline)); f
+#define LocalNoInlineNoReturn(f) static f __attribute__((noinline, noreturn)); f
+
+namespace nix {
+
+LocalNoInlineNoReturn(void throwEvalError(const char * s))
+{
+    throw EvalError(s);
+}
+
+LocalNoInlineNoReturn(void throwTypeError(const char * s, const Value & v))
+{
+    throw TypeError(format(s) % showType(v));
+}
+
+
+void EvalState::forceValue(Value & v)
+{
+    if (v.type == tThunk) {
+        Env * env = v.thunk.env;
+        Expr * expr = v.thunk.expr;
+        try {
+            v.type = tBlackhole;
+            //checkInterrupt();
+            expr->eval(*this, *env, v);
+        } catch (Error & e) {
+            v.type = tThunk;
+            v.thunk.env = env;
+            v.thunk.expr = expr;
+            throw;
+        }
+    }
+    else if (v.type == tApp)
+        callFunction(*v.app.left, *v.app.right, v);
+    else if (v.type == tBlackhole)
+        throwEvalError("infinite recursion encountered");
+}
+
+
+inline void EvalState::forceAttrs(Value & v)
+{
+    forceValue(v);
+    if (v.type != tAttrs)
+        throwTypeError("value is %1% while a set was expected", v);
+}
+
+
+inline void EvalState::forceList(Value & v)
+{
+    forceValue(v);
+    if (v.type != tList)
+        throwTypeError("value is %1% while a list was expected", v);
+}
+
+}
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
new file mode 100644
index 000000000000..2087c7c43ffb
--- /dev/null
+++ b/src/libexpr/eval.cc
@@ -0,0 +1,1435 @@
+#include "eval.hh"
+#include "hash.hh"
+#include "util.hh"
+#include "store-api.hh"
+#include "derivations.hh"
+#include "globals.hh"
+#include "eval-inline.hh"
+
+#include <cstring>
+#include <unistd.h>
+#include <sys/time.h>
+#include <sys/resource.h>
+
+#if HAVE_BOEHMGC
+
+#include <gc/gc.h>
+#include <gc/gc_cpp.h>
+
+#define NEW new (UseGC)
+
+#else
+
+#define GC_STRDUP strdup
+#define GC_MALLOC malloc
+
+#define NEW new
+
+#endif
+
+
+namespace nix {
+
+
+Bindings::iterator Bindings::find(const Symbol & name)
+{
+    Attr key(name, 0);
+    iterator i = lower_bound(begin(), end(), key);
+    if (i != end() && i->name == name) return i;
+    return end();
+}
+
+
+void Bindings::sort()
+{
+    std::sort(begin(), end());
+}
+
+
+std::ostream & operator << (std::ostream & str, const Value & 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; 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 << "{ ";
+        typedef std::map<string, Value *> Sorted;
+        Sorted sorted;
+        foreach (Bindings::iterator, i, *v.attrs)
+            sorted[i->name] = i->value;
+        foreach (Sorted::iterator, i, sorted)
+            str << i->first << " = " << *i->second << "; ";
+        str << "}";
+        break;
+    }
+    case tList:
+        str << "[ ";
+        for (unsigned int n = 0; n < v.list.length; ++n)
+            str << *v.list.elems[n] << " ";
+        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;
+    default:
+        throw Error("invalid value");
+    }
+    return str;
+}
+
+
+string showType(const Value & v)
+{
+    switch (v.type) {
+        case tInt: return "an integer";
+        case tBool: return "a boolean";
+        case tString: return "a string";
+        case tPath: return "a path";
+        case tNull: return "null";
+        case tAttrs: return "a set";
+        case tList: 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 "a built-in function";
+        case tPrimOpApp: return "a partially applied built-in function";
+    }
+    abort();
+}
+
+
+/* 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();
+}
+
+
+static Symbol getName(const AttrName & name, EvalState & state, Env & env) {
+    if (name.symbol.set()) {
+        return name.symbol;
+    } else {
+        Value nameValue;
+        name.expr->eval(state, env, nameValue);
+        state.forceStringNoCtx(nameValue);
+        return state.symbols.create(nameValue.string.s);
+    }
+}
+
+
+EvalState::EvalState()
+    : 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"))
+    , repair(false)
+    , baseEnv(allocEnv(128))
+    , staticBaseEnv(false, 0)
+    , baseEnvDispl(0)
+{
+    nrEnvs = nrValuesInEnvs = nrValues = nrListElems = 0;
+    nrAttrsets = nrOpUpdates = nrOpUpdateValuesCopied = 0;
+    nrListConcats = nrPrimOpCalls = nrFunctionCalls = 0;
+    countCalls = getEnv("NIX_COUNT_CALLS", "0") != "0";
+
+#if HAVE_BOEHMGC
+    static bool gcInitialised = false;
+    if (!gcInitialised) {
+
+        /* Initialise the Boehm garbage collector.  This isn't
+           necessary on most platforms, but for portability we do it
+           anyway. */
+        GC_INIT();
+
+        GC_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")) {
+            size_t maxSize = 384 * 1024 * 1024;
+            size_t size = 32 * 1024 * 1024;
+#if HAVE_SYSCONF && defined(_SC_PAGESIZE) && defined(_SC_PHYS_PAGES)
+            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
+            debug(format("setting initial heap size to %1% bytes") % size);
+            GC_expand_hp(size);
+        }
+
+        gcInitialised = true;
+    }
+#endif
+
+    /* Initialise the Nix expression search path. */
+    searchPathInsertionPoint = searchPath.end();
+    Strings paths = tokenizeString<Strings>(getEnv("NIX_PATH", ""), ":");
+    foreach (Strings::iterator, i, paths) addToSearchPath(*i);
+    addToSearchPath("nix=" + settings.nixDataDir + "/nix/corepkgs");
+    searchPathInsertionPoint = searchPath.begin();
+
+    createBaseEnv();
+}
+
+
+EvalState::~EvalState()
+{
+}
+
+
+void EvalState::addConstant(const string & name, Value & v)
+{
+    Value * v2 = allocValue();
+    *v2 = v;
+    staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl;
+    baseEnv.values[baseEnvDispl++] = v2;
+    string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
+    baseEnv.values[0]->attrs->push_back(Attr(symbols.create(name2), v2));
+}
+
+
+void EvalState::addPrimOp(const string & name,
+    unsigned int arity, PrimOpFun primOp)
+{
+    Value * v = allocValue();
+    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));
+}
+
+
+void EvalState::getBuiltin(const string & name, Value & v)
+{
+    v = *baseEnv.values[0]->attrs->find(symbols.create(name))->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 string & s2))
+{
+    throw EvalError(format(s) % s2);
+}
+
+LocalNoInlineNoReturn(void throwEvalError(const char * s, const string & s2, const string & s3))
+{
+    throw EvalError(format(s) % s2 % s3);
+}
+
+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))
+{
+    throw TypeError(s);
+}
+
+LocalNoInlineNoReturn(void throwTypeError(const char * s, const string & s1))
+{
+    throw TypeError(format(s) % s1);
+}
+
+LocalNoInlineNoReturn(void throwTypeError(const char * s, const string & s1, const string & s2))
+{
+    throw TypeError(format(s) % s1 % s2);
+}
+
+LocalNoInlineNoReturn(void throwTypeError(const char * s, const ExprLambda & fun, const Symbol & s2))
+{
+    throw TypeError(format(s) % fun.showNamePos() % s2);
+}
+
+LocalNoInlineNoReturn(void throwAssertionError(const char * s, const Pos & pos))
+{
+    throw AssertionError(format(s) % pos);
+}
+
+LocalNoInlineNoReturn(void throwUndefinedVarError(const char * s, const string & s1, const Pos & pos))
+{
+    throw UndefinedVarError(format(s) % s1 % pos);
+}
+
+LocalNoInline(void addErrorPrefix(Error & e, const char * s, const string & s2))
+{
+    e.addPrefix(format(s) % s2);
+}
+
+LocalNoInline(void addErrorPrefix(Error & e, const char * s, const ExprLambda & fun))
+{
+    e.addPrefix(format(s) % fun.showNamePos());
+}
+
+LocalNoInline(void addErrorPrefix(Error & e, const char * s, const string & s2, const Pos & pos))
+{
+    e.addPrefix(format(s) % s2 % pos);
+}
+
+
+void mkString(Value & v, const char * s)
+{
+    mkStringNoCopy(v, GC_STRDUP(s));
+}
+
+
+void mkString(Value & v, const string & s, const PathSet & context)
+{
+    mkString(v, s.c_str());
+    if (!context.empty()) {
+        unsigned int n = 0;
+        v.string.context = (const char * *)
+            GC_MALLOC((context.size() + 1) * sizeof(char *));
+        foreach (PathSet::const_iterator, i, context)
+            v.string.context[n++] = GC_STRDUP(i->c_str());
+        v.string.context[n] = 0;
+    }
+}
+
+
+void mkPath(Value & v, const char * s)
+{
+    mkPathNoCopy(v, GC_STRDUP(s));
+}
+
+
+inline Value * EvalState::lookupVar(Env * env, const ExprVar & var, bool noEval)
+{
+    for (unsigned int l = var.level; l; --l, env = env->up) ;
+
+    if (!var.fromWith) return env->values[var.displ];
+
+    while (1) {
+        if (!env->haveWithAttrs) {
+            if (noEval) return 0;
+            Value * v = allocValue();
+            evalAttrs(*env->up, (Expr *) env->values[0], *v);
+            env->values[0] = v;
+            env->haveWithAttrs = true;
+        }
+        Bindings::iterator j = env->values[0]->attrs->find(var.name);
+        if (j != env->values[0]->attrs->end()) {
+            if (countCalls && j->pos) attrSelects[*j->pos]++;
+            return j->value;
+        }
+        if (!env->prevWith)
+            throwUndefinedVarError("undefined variable `%1%' at %2%", var.name, var.pos);
+        for (unsigned int l = env->prevWith; l; --l, env = env->up) ;
+    }
+}
+
+
+Value * EvalState::allocValue()
+{
+    nrValues++;
+    return (Value *) GC_MALLOC(sizeof(Value));
+}
+
+
+Env & EvalState::allocEnv(unsigned int size)
+{
+    nrEnvs++;
+    nrValuesInEnvs += size;
+    Env * env = (Env *) GC_MALLOC(sizeof(Env) + size * sizeof(Value *));
+
+    /* Clear the values because maybeThunk() and lookupVar fromWith expects this. */
+    for (unsigned i = 0; i < size; ++i)
+        env->values[i] = 0;
+
+    return *env;
+}
+
+
+Value * EvalState::allocAttr(Value & vAttrs, const Symbol & name)
+{
+    Value * v = allocValue();
+    vAttrs.attrs->push_back(Attr(name, v));
+    return v;
+}
+
+
+void EvalState::mkList(Value & v, unsigned int length)
+{
+    v.type = tList;
+    v.list.length = length;
+    v.list.elems = length ? (Value * *) GC_MALLOC(length * sizeof(Value *)) : 0;
+    nrListElems += length;
+}
+
+
+void EvalState::mkAttrs(Value & v, unsigned int expected)
+{
+    clearValue(v);
+    v.type = tAttrs;
+    v.attrs = NEW Bindings;
+    v.attrs->reserve(expected);
+    nrAttrsets++;
+}
+
+
+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) {
+        mkAttrs(v, 3);
+        mkString(*allocAttr(v, sFile), pos->file);
+        mkInt(*allocAttr(v, sLine), pos->line);
+        mkInt(*allocAttr(v, sColumn), pos->column);
+        v.attrs->sort();
+    } 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) { 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 * ExprPath::maybeThunk(EvalState & state, Env & env)
+{
+    nrAvoided++;
+    return &v;
+}
+
+
+void EvalState::evalFile(const Path & path, Value & v)
+{
+    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;
+    }
+
+    startNest(nest, lvlTalkative, format("evaluating file `%1%'") % path2);
+    Expr * e = parseExprFromFile(path2);
+    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();
+}
+
+
+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)
+{
+    Value v;
+    return evalBool(env, e, v);
+}
+
+
+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 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());
+    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;
+
+        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. */
+        unsigned int displ = 0;
+        foreach (AttrDefs::iterator, 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)[overrides->second.displ].value;
+            state.forceAttrs(*vOverrides);
+            foreach (Bindings::iterator, i, *vOverrides->attrs) {
+                AttrDefs::iterator j = attrs.find(i->name);
+                if (j != attrs.end()) {
+                    (*v.attrs)[j->second.displ] = *i;
+                    env2.values[j->second.displ] = i->value;
+                } else
+                    v.attrs->push_back(*i);
+            }
+            v.attrs->sort();
+        }
+    }
+
+    else
+        foreach (AttrDefs::iterator, 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 */
+    foreach (DynamicAttrDefs::iterator, i, dynamicAttrs) {
+        Value nameVal;
+        i->nameExpr->eval(state, *dynamicEnv, nameVal);
+        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->pos);
+
+        i->valueExpr->setName(nameSym);
+        /* Keep sorted order so find can catch duplicates */
+        v.attrs->insert(lower_bound(v.attrs->begin(), v.attrs->end(), Attr(nameSym, 0)),
+                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. */
+    unsigned int displ = 0;
+    foreach (ExprAttrs::AttrDefs::iterator, 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 (unsigned int n = 0; n < v.list.length; ++n)
+        v.list.elems[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);
+    v = *v2;
+}
+
+
+unsigned long nrLookups = 0;
+
+void ExprSelect::eval(EvalState & state, Env & env, Value & v)
+{
+    Value vTmp;
+    Pos * pos = 0;
+    Value * vAttrs = &vTmp;
+
+    e->eval(state, env, vTmp);
+
+    try {
+
+        foreach (AttrPath::const_iterator, i, attrPath) {
+            nrLookups++;
+            Bindings::iterator j;
+            Symbol name = getName(*i, state, env);
+            if (def) {
+                state.forceValue(*vAttrs);
+                if (vAttrs->type != tAttrs ||
+                    (j = vAttrs->attrs->find(name)) == vAttrs->attrs->end())
+                {
+                    def->eval(state, env, v);
+                    return;
+                }
+            } else {
+                state.forceAttrs(*vAttrs);
+                if ((j = vAttrs->attrs->find(name)) == vAttrs->attrs->end())
+                    throwEvalError("attribute `%1%' missing", showAttrPath(attrPath));
+            }
+            vAttrs = j->value;
+            pos = j->pos;
+            if (state.countCalls && pos) state.attrSelects[*pos]++;
+        }
+
+        state.forceValue(*vAttrs);
+
+    } catch (Error & e) {
+        if (pos && pos->file != state.sDerivationNix)
+            addErrorPrefix(e, "while evaluating the attribute `%1%' at %2%:\n",
+                showAttrPath(attrPath), *pos);
+        throw;
+    }
+
+    v = *vAttrs;
+}
+
+
+void ExprOpHasAttr::eval(EvalState & state, Env & env, Value & v)
+{
+    Value vTmp;
+    Value * vAttrs = &vTmp;
+
+    e->eval(state, env, vTmp);
+
+    foreach (AttrPath::const_iterator, 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;
+        } else {
+            vAttrs = j->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)
+{
+    e1->eval(state, env, v);
+    state.callFunction(v, *(e2->maybeThunk(state, env)), v);
+}
+
+
+void EvalState::callPrimOp(Value & fun, Value & arg, Value & v)
+{
+    /* Figure out the number of arguments still needed. */
+    unsigned int argsDone = 0;
+    Value * primOp = &fun;
+    while (primOp->type == tPrimOpApp) {
+        argsDone++;
+        primOp = primOp->primOpApp.left;
+    }
+    assert(primOp->type == tPrimOp);
+    unsigned int arity = primOp->primOp->arity;
+    unsigned int 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];
+        unsigned int 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, 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)
+{
+    if (fun.type == tPrimOp || fun.type == tPrimOpApp) {
+        callPrimOp(fun, arg, v);
+        return;
+    }
+
+    if (fun.type != tLambda)
+        throwTypeError("attempt to call something which is not a function but %1%", fun);
+
+    ExprLambda & lambda(*fun.lambda.fun);
+
+    unsigned int size =
+        (lambda.arg.empty() ? 0 : 1) +
+        (lambda.matchAttrs ? lambda.formals->formals.size() : 0);
+    Env & env2(allocEnv(size));
+    env2.up = fun.lambda.env;
+
+    unsigned int displ = 0;
+
+    if (!lambda.matchAttrs)
+        env2.values[displ++] = &arg;
+
+    else {
+        forceAttrs(arg);
+
+        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. */
+        unsigned int attrsUsed = 0;
+        foreach (Formals::Formals_::iterator, i, lambda.formals->formals) {
+            Bindings::iterator j = arg.attrs->find(i->name);
+            if (j == arg.attrs->end()) {
+                if (!i->def) throwTypeError("%1% called without required argument `%2%'",
+                    lambda, i->name);
+                env2.values[displ++] = i->def->maybeThunk(*this, env2);
+            } else {
+                attrsUsed++;
+                env2.values[displ++] = j->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. */
+            foreach (Bindings::iterator, i, *arg.attrs)
+                if (lambda.formals->argNames.find(i->name) == lambda.formals->argNames.end())
+                    throwTypeError("%1% called with unexpected argument `%2%'", lambda, i->name);
+            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%:\n", lambda);
+            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 != tLambda || !fun.lambda.fun->matchAttrs) {
+        res = fun;
+        return;
+    }
+
+    Value * actualArgs = allocValue();
+    mkAttrs(*actualArgs, fun.lambda.fun->formals->formals.size());
+
+    foreach (Formals::Formals_::iterator, i, fun.lambda.fun->formals->formals) {
+        Bindings::iterator j = args.find(i->name);
+        if (j != args.end())
+            actualArgs->attrs->push_back(*j);
+        else if (!i->def)
+            throwTypeError("cannot auto-call a function that has an argument without a default value (`%1%')", i->name);
+    }
+
+    actualArgs->attrs->sort();
+
+    callFunction(fun, *actualArgs, res);
+}
+
+
+void ExprWith::eval(EvalState & state, Env & env, Value & v)
+{
+    Env & env2(state.allocEnv(1));
+    env2.up = &env;
+    env2.prevWith = prevWith;
+    env2.haveWithAttrs = false;
+    env2.values[0] = (Value *) attrs;
+
+    body->eval(state, env2, v);
+}
+
+
+void ExprIf::eval(EvalState & state, Env & env, Value & v)
+{
+    (state.evalBool(env, cond, v) ? then : else_)->eval(state, env, v);
+}
+
+
+void ExprAssert::eval(EvalState & state, Env & env, Value & v)
+{
+    if (!state.evalBool(env, cond, v))
+        throwAssertionError("assertion failed at %1%", pos);
+    body->eval(state, env, v);
+}
+
+
+void ExprOpNot::eval(EvalState & state, Env & env, Value & v)
+{
+    mkBool(v, !state.evalBool(env, e));
+}
+
+
+void ExprBuiltin::eval(EvalState & state, Env & env, Value & v)
+{
+    // Not a hot path at all, but would be nice to access state.baseEnv directly
+    Env *baseEnv = &env;
+    while (baseEnv->up) baseEnv = baseEnv->up;
+    Bindings::iterator binding = baseEnv->values[0]->attrs->find(name);
+    assert(binding != baseEnv->values[0]->attrs->end());
+    v = *binding->value;
+}
+
+
+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) && state.evalBool(env, e2));
+}
+
+
+void ExprOpOr::eval(EvalState & state, Env & env, Value & v)
+{
+    mkBool(v, state.evalBool(env, e1) || state.evalBool(env, e2));
+}
+
+
+void ExprOpImpl::eval(EvalState & state, Env & env, Value & v)
+{
+    mkBool(v, !state.evalBool(env, e1) || state.evalBool(env, e2));
+}
+
+
+void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
+{
+    Value v1, v2;
+    state.evalAttrs(env, e1, v1);
+    state.evalAttrs(env, e2, v2);
+
+    state.nrOpUpdates++;
+
+    if (v1.attrs->size() == 0) { v = v2; return; }
+    if (v2.attrs->size() == 0) { v = v1; return; }
+
+    state.mkAttrs(v, v1.attrs->size() + v2.attrs->size());
+
+    /* Merge the sets, preferring values from the second set.  Make
+       sure to keep the resulting vector in sorted order. */
+    Bindings::iterator i = v1.attrs->begin();
+    Bindings::iterator j = v2.attrs->begin();
+
+    while (i != v1.attrs->end() && j != v2.attrs->end()) {
+        if (i->name == j->name) {
+            v.attrs->push_back(*j);
+            ++i; ++j;
+        }
+        else if (i->name < j->name)
+            v.attrs->push_back(*i++);
+        else
+            v.attrs->push_back(*j++);
+    }
+
+    while (i != v1.attrs->end()) v.attrs->push_back(*i++);
+    while (j != v2.attrs->end()) v.attrs->push_back(*j++);
+
+    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);
+}
+
+
+void EvalState::concatLists(Value & v, unsigned int nrLists, Value * * lists)
+{
+    nrListConcats++;
+
+    Value * nonEmpty = 0;
+    unsigned int len = 0;
+    for (unsigned int n = 0; n < nrLists; ++n) {
+        forceList(*lists[n]);
+        unsigned int l = lists[n]->list.length;
+        len += l;
+        if (l) nonEmpty = lists[n];
+    }
+
+    if (nonEmpty && len == nonEmpty->list.length) {
+        v = *nonEmpty;
+        return;
+    }
+
+    mkList(v, len);
+    for (unsigned int n = 0, pos = 0; n < nrLists; ++n) {
+        unsigned int l = lists[n]->list.length;
+        memcpy(v.list.elems + pos, lists[n]->list.elems, l * sizeof(Value *));
+        pos += l;
+    }
+}
+
+
+void ExprConcatStrings::eval(EvalState & state, Env & env, Value & v)
+{
+    PathSet context;
+    std::ostringstream s;
+    NixInt n = 0;
+
+    bool first = !forceString;
+    ValueType firstType = tString;
+
+    foreach (vector<Expr *>::iterator, 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)
+                throwEvalError("cannot add %1% to an integer", showType(vTmp));
+            n += vTmp.integer;
+        } else
+            s << state.coerceToString(vTmp, context, false, firstType == tString);
+    }
+
+    if (firstType == tInt)
+        mkInt(v, n);
+    else if (firstType == tPath) {
+        if (!context.empty())
+            throwEvalError("a string that refers to a store path cannot be appended to a path, in `%1%'", s.str());
+        mkPath(v, s.str().c_str());
+    } else
+        mkString(v, s.str(), context);
+}
+
+
+void ExprPos::eval(EvalState & state, Env & env, Value & v)
+{
+    state.mkPos(v, &pos);
+}
+
+
+void EvalState::strictForceValue(Value & v)
+{
+    forceValue(v);
+
+    if (v.type == tAttrs) {
+        foreach (Bindings::iterator, i, *v.attrs)
+            strictForceValue(*i->value);
+    }
+
+    else if (v.type == tList) {
+        for (unsigned int n = 0; n < v.list.length; ++n)
+            strictForceValue(*v.list.elems[n]);
+    }
+}
+
+
+NixInt EvalState::forceInt(Value & v)
+{
+    forceValue(v);
+    if (v.type != tInt)
+        throwTypeError("value is %1% while an integer was expected", v);
+    return v.integer;
+}
+
+
+bool EvalState::forceBool(Value & v)
+{
+    forceValue(v);
+    if (v.type != tBool)
+        throwTypeError("value is %1% while a Boolean was expected", v);
+    return v.boolean;
+}
+
+
+void EvalState::forceFunction(Value & v)
+{
+    forceValue(v);
+    if (v.type != tLambda && v.type != tPrimOp && v.type != tPrimOpApp)
+        throwTypeError("value is %1% while a function was expected", v);
+}
+
+
+string EvalState::forceString(Value & v)
+{
+    forceValue(v);
+    if (v.type != tString)
+        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)
+        for (const char * * p = v.string.context; *p; ++p)
+            context.insert(*p);
+}
+
+
+string EvalState::forceString(Value & v, PathSet & context)
+{
+    string s = forceString(v);
+    copyContext(v, context);
+    return s;
+}
+
+
+string EvalState::forceStringNoCtx(Value & v)
+{
+    string s = forceString(v);
+    if (v.string.context)
+        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->value);
+    if (i->value->type != tString) return false;
+    return strcmp(i->value->string.s, "derivation") == 0;
+}
+
+
+string EvalState::coerceToString(Value & v, PathSet & context,
+    bool coerceMore, bool copyToStore)
+{
+    forceValue(v);
+
+    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) {
+        Bindings::iterator i = v.attrs->find(sOutPath);
+        if (i == v.attrs->end()) throwTypeError("cannot coerce a set to a string");
+        return coerceToString(*i->value, 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 int2String(v.integer);
+        if (v.type == tNull) return "";
+
+        if (v.type == tList) {
+            string result;
+            for (unsigned int n = 0; n < v.list.length; ++n) {
+                result += coerceToString(*v.list.elems[n],
+                    context, coerceMore, copyToStore);
+                if (n < v.list.length - 1
+                    /* !!! not quite correct */
+                    && (v.list.elems[n]->type != tList || v.list.elems[n]->list.length != 0))
+                    result += " ";
+            }
+            return result;
+        }
+    }
+
+    throwTypeError("cannot coerce %1% to a string", v);
+}
+
+
+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] != "")
+        dstPath = srcToStore[path];
+    else {
+        dstPath = settings.readOnlyMode
+            ? computeStorePathForPath(path).first
+            : store->addToStore(path, true, htSHA256, defaultPathFilter, repair);
+        srcToStore[path] = dstPath;
+        printMsg(lvlChatty, format("copied source `%1%' -> `%2%'")
+            % path % dstPath);
+    }
+
+    context.insert(dstPath);
+    return dstPath;
+}
+
+
+Path EvalState::coerceToPath(Value & v, PathSet & context)
+{
+    string path = coerceToString(v, context, false, false);
+    if (path == "" || path[0] != '/')
+        throwEvalError("string `%1%' doesn't represent an absolute path", path);
+    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;
+
+    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: {
+            /* Compare both the string and its context. */
+            if (strcmp(v1.string.s, v2.string.s) != 0) return false;
+            const char * * p = v1.string.context, * * q = v2.string.context;
+            if (!p && !q) return true;
+            if (!p || !q) return false;
+            for ( ; *p && *q; ++p, ++q)
+                if (strcmp(*p, *q) != 0) return false;
+            if (*p || *q) return false;
+            return true;
+        }
+
+        case tPath:
+            return strcmp(v1.path, v2.path) == 0;
+
+        case tNull:
+            return true;
+
+        case tList:
+            if (v1.list.length != v2.list.length) return false;
+            for (unsigned int n = 0; n < v1.list.length; ++n)
+                if (!eqValues(*v1.list.elems[n], *v2.list.elems[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->value, *j->value);
+            }
+
+            if (v1.attrs->size() != v2.attrs->size()) return false;
+
+            /* Otherwise, compare the attributes one by one. */
+            Bindings::iterator i, j;
+            for (i = v1.attrs->begin(), j = v2.attrs->begin(); i != v1.attrs->end(); ++i, ++j)
+                if (i->name != j->name || !eqValues(*i->value, *j->value))
+                    return false;
+
+            return true;
+        }
+
+        /* Functions are incomparable. */
+        case tLambda:
+        case tPrimOp:
+        case tPrimOpApp:
+            return false;
+
+        default:
+            throwEvalError("cannot compare %1% with %2%", showType(v1), showType(v2));
+    }
+}
+
+
+void EvalState::printStats()
+{
+    bool showStats = getEnv("NIX_SHOW_STATS", "0") != "0";
+    Verbosity v = showStats ? lvlInfo : lvlDebug;
+    printMsg(v, "evaluation statistics:");
+
+    struct rusage buf;
+    getrusage(RUSAGE_SELF, &buf);
+    float cpuTime = buf.ru_utime.tv_sec + ((float) buf.ru_utime.tv_usec / 1000000);
+
+    printMsg(v, format("  time elapsed: %1%") % cpuTime);
+    printMsg(v, format("  size of a value: %1%") % sizeof(Value));
+    printMsg(v, format("  environments allocated: %1% (%2% bytes)")
+        % nrEnvs % (nrEnvs * sizeof(Env) + nrValuesInEnvs * sizeof(Value *)));
+    printMsg(v, format("  list elements: %1% (%2% bytes)")
+        % nrListElems % (nrListElems * sizeof(Value *)));
+    printMsg(v, format("  list concatenations: %1%") % nrListConcats);
+    printMsg(v, format("  values allocated: %1% (%2% bytes)")
+        % nrValues % (nrValues * sizeof(Value)));
+    printMsg(v, format("  sets allocated: %1%") % nrAttrsets);
+    printMsg(v, format("  right-biased unions: %1%") % nrOpUpdates);
+    printMsg(v, format("  values copied in right-biased unions: %1%") % nrOpUpdateValuesCopied);
+    printMsg(v, format("  symbols in symbol table: %1%") % symbols.size());
+    printMsg(v, format("  size of symbol table: %1%") % symbols.totalSize());
+    printMsg(v, format("  number of thunks: %1%") % nrThunks);
+    printMsg(v, format("  number of thunks avoided: %1%") % nrAvoided);
+    printMsg(v, format("  number of attr lookups: %1%") % nrLookups);
+    printMsg(v, format("  number of primop calls: %1%") % nrPrimOpCalls);
+    printMsg(v, format("  number of function calls: %1%") % nrFunctionCalls);
+
+    if (countCalls) {
+        v = lvlInfo;
+
+        printMsg(v, format("calls to %1% primops:") % primOpCalls.size());
+        typedef std::multimap<unsigned int, Symbol> PrimOpCalls_;
+        PrimOpCalls_ primOpCalls_;
+        foreach (PrimOpCalls::iterator, i, primOpCalls)
+            primOpCalls_.insert(std::pair<unsigned int, Symbol>(i->second, i->first));
+        foreach_reverse (PrimOpCalls_::reverse_iterator, i, primOpCalls_)
+            printMsg(v, format("%1$10d %2%") % i->first % i->second);
+
+        printMsg(v, format("calls to %1% functions:") % functionCalls.size());
+        typedef std::multimap<unsigned int, ExprLambda *> FunctionCalls_;
+        FunctionCalls_ functionCalls_;
+        foreach (FunctionCalls::iterator, i, functionCalls)
+            functionCalls_.insert(std::pair<unsigned int, ExprLambda *>(i->second, i->first));
+        foreach_reverse (FunctionCalls_::reverse_iterator, i, functionCalls_)
+            printMsg(v, format("%1$10d %2%") % i->first % i->second->showNamePos());
+
+        printMsg(v, format("evaluations of %1% attributes:") % attrSelects.size());
+        typedef std::multimap<unsigned int, Pos> AttrSelects_;
+        AttrSelects_ attrSelects_;
+        foreach (AttrSelects::iterator, i, attrSelects)
+            attrSelects_.insert(std::pair<unsigned int, Pos>(i->second, i->first));
+        foreach_reverse (AttrSelects_::reverse_iterator, i, attrSelects_)
+            printMsg(v, format("%1$10d %2%") % i->first % i->second);
+
+    }
+}
+
+
+}
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
new file mode 100644
index 000000000000..5ae5a1e3cf24
--- /dev/null
+++ b/src/libexpr/eval.hh
@@ -0,0 +1,294 @@
+#pragma once
+
+#include "value.hh"
+#include "nixexpr.hh"
+#include "symbol-table.hh"
+#include "hash.hh"
+
+#include <map>
+
+#if HAVE_BOEHMGC
+#include <gc/gc_allocator.h>
+#endif
+
+
+namespace nix {
+
+
+class EvalState;
+struct Attr;
+
+
+/* Sets are represented as a vector of attributes, sorted by symbol
+   (i.e. pointer to the attribute name in the symbol table). */
+#if HAVE_BOEHMGC
+typedef std::vector<Attr, gc_allocator<Attr> > BindingsBase;
+#else
+typedef std::vector<Attr> BindingsBase;
+#endif
+
+
+class Bindings : public BindingsBase
+{
+public:
+    iterator find(const Symbol & name);
+    void sort();
+};
+
+
+typedef void (* PrimOpFun) (EvalState & state, Value * * args, Value & v);
+
+
+struct PrimOp
+{
+    PrimOpFun fun;
+    unsigned int arity;
+    Symbol name;
+    PrimOp(PrimOpFun fun, unsigned int arity, Symbol name)
+        : fun(fun), arity(arity), name(name) { }
+};
+
+
+struct Env
+{
+    Env * up;
+    unsigned short prevWith; // nr of levels up to next `with' environment
+    bool haveWithAttrs;
+    Value * values[0];
+};
+
+
+struct Attr
+{
+    Symbol name;
+    Value * value;
+    Pos * pos;
+    Attr(Symbol name, Value * value, Pos * pos = &noPos)
+        : name(name), value(value), pos(pos) { };
+    Attr() : pos(&noPos) { };
+    bool operator < (const Attr & a) const
+    {
+        return name < a.name;
+    }
+};
+
+
+void mkString(Value & v, const string & s, const PathSet & context = PathSet());
+
+void copyContext(const Value & v, PathSet & context);
+
+
+/* Cache for calls to addToStore(); maps source paths to the store
+   paths. */
+typedef std::map<Path, Path> SrcToStore;
+
+
+std::ostream & operator << (std::ostream & str, const Value & v);
+
+
+class EvalState
+{
+public:
+    SymbolTable symbols;
+
+    const Symbol sWith, sOutPath, sDrvPath, sType, sMeta, sName, sValue,
+        sSystem, sOverrides, sOutputs, sOutputName, sIgnoreNulls,
+        sFile, sLine, sColumn;
+    Symbol sDerivationNix;
+
+    /* If set, force copying files to the Nix store even if they
+       already exist there. */
+    bool repair;
+
+private:
+    SrcToStore srcToStore;
+
+    /* A cache from path names to values. */
+#if HAVE_BOEHMGC
+    typedef std::map<Path, Value, std::less<Path>, gc_allocator<std::pair<const Path, Value> > > FileEvalCache;
+#else
+    typedef std::map<Path, Value> FileEvalCache;
+#endif
+    FileEvalCache fileEvalCache;
+
+    typedef list<std::pair<string, Path> > SearchPath;
+    SearchPath searchPath;
+    SearchPath::iterator searchPathInsertionPoint;
+
+public:
+
+    EvalState();
+    ~EvalState();
+
+    void addToSearchPath(const string & s);
+
+    /* Parse a Nix expression from the specified file. */
+    Expr * parseExprFromFile(const Path & path);
+
+    /* Parse a Nix expression from the specified string. */
+    Expr * parseExprFromString(const string & s, const Path & basePath, StaticEnv & staticEnv);
+    Expr * parseExprFromString(const string & s, const Path & basePath);
+
+    /* Evaluate an expression read from the given file to normal
+       form. */
+    void evalFile(const Path & path, Value & v);
+
+    void resetFileCache();
+
+    /* Look up a file in the search path. */
+    Path findFile(const string & path);
+
+    /* Evaluate an expression to normal form, storing the result in
+       value `v'. */
+    void eval(Expr * e, Value & v);
+
+    /* Evaluation the expression, then verify that it has the expected
+       type. */
+    inline bool evalBool(Env & env, Expr * e, Value & v);
+    inline bool evalBool(Env & env, Expr * e);
+    inline void evalAttrs(Env & env, Expr * e, Value & v);
+
+    /* If `v' is a thunk, enter it and overwrite `v' with the result
+       of the evaluation of the thunk.  If `v' is a delayed function
+       application, call the function and overwrite `v' with the
+       result.  Otherwise, this is a no-op. */
+    inline void forceValue(Value & v);
+
+    /* Force a value, then recursively force list elements and
+       attributes. */
+    void strictForceValue(Value & v);
+
+    /* Force `v', and then verify that it has the expected type. */
+    NixInt forceInt(Value & v);
+    bool forceBool(Value & v);
+    inline void forceAttrs(Value & v);
+    inline void forceList(Value & v);
+    void forceFunction(Value & v); // either lambda or primop
+    string forceString(Value & v);
+    string forceString(Value & v, PathSet & context);
+    string forceStringNoCtx(Value & v);
+
+    /* Return true iff the value `v' denotes a derivation (i.e. a
+       set with attribute `type = "derivation"'). */
+    bool isDerivation(Value & v);
+
+    /* String coercion.  Converts strings, paths and derivations to a
+       string.  If `coerceMore' is set, also converts nulls, integers,
+       booleans and lists to a string.  If `copyToStore' is set,
+       referenced paths are copied to the Nix store as a side effect. */
+    string coerceToString(Value & v, PathSet & context,
+        bool coerceMore = false, bool copyToStore = true);
+
+    string copyPathToStore(PathSet & context, const Path & path);
+
+    /* Path coercion.  Converts strings, paths and derivations to a
+       path.  The result is guaranteed to be a canonicalised, absolute
+       path.  Nothing is copied to the store. */
+    Path coerceToPath(Value & v, PathSet & context);
+
+public:
+
+    /* The base environment, containing the builtin functions and
+       values. */
+    Env & baseEnv;
+
+    /* The same, but used during parsing to resolve variables. */
+    StaticEnv staticBaseEnv; // !!! should be private
+
+private:
+
+    unsigned int baseEnvDispl;
+
+    void createBaseEnv();
+
+    void addConstant(const string & name, Value & v);
+
+    void addPrimOp(const string & name,
+        unsigned int arity, PrimOpFun primOp);
+
+public:
+
+    void getBuiltin(const string & name, Value & v);
+
+private:
+
+    inline Value * lookupVar(Env * env, const ExprVar & var, bool noEval);
+
+    friend struct ExprVar;
+    friend struct ExprAttrs;
+    friend struct ExprLet;
+
+    Expr * parse(const char * text, const Path & path,
+        const Path & basePath, StaticEnv & staticEnv);
+
+public:
+
+    /* Do a deep equality test between two values.  That is, list
+       elements and attributes are compared recursively. */
+    bool eqValues(Value & v1, Value & v2);
+
+    void callFunction(Value & fun, Value & arg, Value & v);
+    void callPrimOp(Value & fun, Value & arg, Value & v);
+
+    /* Automatically call a function for which each argument has a
+       default value or has a binding in the `args' map. */
+    void autoCallFunction(Bindings & args, Value & fun, Value & res);
+
+    /* Allocation primitives. */
+    Value * allocValue();
+    Env & allocEnv(unsigned int size);
+
+    Value * allocAttr(Value & vAttrs, const Symbol & name);
+
+    void mkList(Value & v, unsigned int length);
+    void mkAttrs(Value & v, unsigned int expected);
+    void mkThunk_(Value & v, Expr * expr);
+    void mkPos(Value & v, Pos * pos);
+
+    void concatLists(Value & v, unsigned int nrLists, Value * * lists);
+
+    /* Print statistics. */
+    void printStats();
+
+private:
+
+    unsigned long nrEnvs;
+    unsigned long nrValuesInEnvs;
+    unsigned long nrValues;
+    unsigned long nrListElems;
+    unsigned long nrAttrsets;
+    unsigned long nrOpUpdates;
+    unsigned long nrOpUpdateValuesCopied;
+    unsigned long nrListConcats;
+    unsigned long nrPrimOpCalls;
+    unsigned long nrFunctionCalls;
+
+    bool countCalls;
+
+    typedef std::map<Symbol, unsigned int> PrimOpCalls;
+    PrimOpCalls primOpCalls;
+
+    typedef std::map<ExprLambda *, unsigned int> FunctionCalls;
+    FunctionCalls functionCalls;
+
+    void incrFunctionCall(ExprLambda * fun);
+
+    typedef std::map<Pos, unsigned int> AttrSelects;
+    AttrSelects attrSelects;
+
+    friend struct ExprOpUpdate;
+    friend struct ExprOpConcatLists;
+    friend struct ExprSelect;
+    friend void prim_getAttr(EvalState & state, Value * * args, Value & v);
+};
+
+
+/* Return a string representing the type of the value `v'. */
+string showType(const Value & v);
+
+
+/* If `path' refers to a directory, then append "/default.nix". */
+Path resolveExprPath(Path path);
+
+
+}
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
new file mode 100644
index 000000000000..0ed644e9bc5b
--- /dev/null
+++ b/src/libexpr/get-drvs.cc
@@ -0,0 +1,305 @@
+#include "get-drvs.hh"
+#include "util.hh"
+#include "eval-inline.hh"
+
+#include <cstring>
+
+
+namespace nix {
+
+
+string DrvInfo::queryDrvPath()
+{
+    if (drvPath == "" && attrs) {
+        Bindings::iterator i = attrs->find(state->sDrvPath);
+        PathSet context;
+        drvPath = i != attrs->end() ? state->coerceToPath(*i->value, context) : "";
+    }
+    return drvPath;
+}
+
+
+string DrvInfo::queryOutPath()
+{
+    if (outPath == "" && attrs) {
+        Bindings::iterator i = attrs->find(state->sOutPath);
+        PathSet context;
+        outPath = i != attrs->end() ? state->coerceToPath(*i->value, context) : "";
+    }
+    return outPath;
+}
+
+
+DrvInfo::Outputs DrvInfo::queryOutputs()
+{
+    if (outputs.empty()) {
+        /* Get the ‘outputs’ list. */
+        Bindings::iterator i;
+        if (attrs && (i = attrs->find(state->sOutputs)) != attrs->end()) {
+            state->forceList(*i->value);
+
+            /* For each output... */
+            for (unsigned int j = 0; j < i->value->list.length; ++j) {
+                /* Evaluate the corresponding set. */
+                string name = state->forceStringNoCtx(*i->value->list.elems[j]);
+                Bindings::iterator out = attrs->find(state->symbols.create(name));
+                if (out == attrs->end()) continue; // FIXME: throw error?
+                state->forceAttrs(*out->value);
+
+                /* And evaluate its ‘outPath’ attribute. */
+                Bindings::iterator outPath = out->value->attrs->find(state->sOutPath);
+                if (outPath == out->value->attrs->end()) continue; // FIXME: throw error?
+                PathSet context;
+                outputs[name] = state->coerceToPath(*outPath->value, context);
+            }
+        } else
+            outputs["out"] = queryOutPath();
+    }
+    return outputs;
+}
+
+
+string DrvInfo::queryOutputName()
+{
+    if (outputName == "" && attrs) {
+        Bindings::iterator i = attrs->find(state->sOutputName);
+        outputName = i != attrs->end() ? state->forceStringNoCtx(*i->value) : "";
+    }
+    return outputName;
+}
+
+
+Bindings * DrvInfo::getMeta()
+{
+    if (meta) return meta;
+    if (!attrs) return 0;
+    Bindings::iterator a = attrs->find(state->sMeta);
+    if (a == attrs->end()) return 0;
+    state->forceAttrs(*a->value);
+    meta = a->value->attrs;
+    return meta;
+}
+
+
+StringSet DrvInfo::queryMetaNames()
+{
+    StringSet res;
+    if (!getMeta()) return res;
+    foreach (Bindings::iterator, i, *meta)
+        res.insert(i->name);
+    return res;
+}
+
+
+bool DrvInfo::checkMeta(Value & v)
+{
+    state->forceValue(v);
+    if (v.type == tList) {
+        for (unsigned int n = 0; n < v.list.length; ++n)
+            if (!checkMeta(*v.list.elems[n])) return false;
+        return true;
+    }
+    else if (v.type == tAttrs) {
+        Bindings::iterator i = v.attrs->find(state->sOutPath);
+        if (i != v.attrs->end()) return false;
+        foreach (Bindings::iterator, i, *v.attrs)
+            if (!checkMeta(*i->value)) return false;
+        return true;
+    }
+    else return v.type == tInt || v.type == tBool || v.type == tString;
+}
+
+
+Value * DrvInfo::queryMeta(const string & name)
+{
+    if (!getMeta()) return 0;
+    Bindings::iterator a = meta->find(state->symbols.create(name));
+    if (a == meta->end() || !checkMeta(*a->value)) return 0;
+    return a->value;
+}
+
+
+string DrvInfo::queryMetaString(const string & name)
+{
+    Value * v = queryMeta(name);
+    if (!v || v->type != tString) return "";
+    return v->string.s;
+}
+
+
+int DrvInfo::queryMetaInt(const string & name, int def)
+{
+    Value * v = queryMeta(name);
+    if (!v) return def;
+    if (v->type == tInt) return v->integer;
+    if (v->type == tString) {
+        /* Backwards compatibility with before we had support for
+           integer meta fields. */
+        int n;
+        if (string2Int(v->string.s, n)) return n;
+    }
+    return def;
+}
+
+
+bool DrvInfo::queryMetaBool(const string & name, bool def)
+{
+    Value * v = queryMeta(name);
+    if (!v) return def;
+    if (v->type == tBool) return v->boolean;
+    if (v->type == tString) {
+        /* Backwards compatibility with before we had support for
+           Boolean meta fields. */
+        if (strcmp(v->string.s, "true") == 0) return true;
+        if (strcmp(v->string.s, "false") == 0) return false;
+    }
+    return def;
+}
+
+
+void DrvInfo::setMeta(const string & name, Value * v)
+{
+    getMeta();
+    Bindings * old = meta;
+    meta = new Bindings();
+    Symbol sym = state->symbols.create(name);
+    if (old)
+        foreach (Bindings::iterator, i, *old)
+            if (i->name != sym)
+                meta->push_back(*i);
+    if (v) meta->push_back(Attr(sym, v));
+    meta->sort();
+}
+
+
+/* Cache for already considered attrsets. */
+typedef set<Bindings *> Done;
+
+
+/* Evaluate value `v'.  If it evaluates to a set of type `derivation',
+   then put information about it in `drvs' (unless it's already in
+   `doneExprs').  The result boolean indicates whether it makes sense
+   for the caller to recursively search for derivations in `v'. */
+static bool getDerivation(EvalState & state, Value & v,
+    const string & attrPath, DrvInfos & drvs, Done & done,
+    bool ignoreAssertionFailures)
+{
+    try {
+        state.forceValue(v);
+        if (!state.isDerivation(v)) return true;
+
+        /* Remove spurious duplicates (e.g., a set like `rec { x =
+           derivation {...}; y = x;}'. */
+        if (done.find(v.attrs) != done.end()) return false;
+        done.insert(v.attrs);
+
+        Bindings::iterator i = v.attrs->find(state.sName);
+        /* !!! We really would like to have a decent back trace here. */
+        if (i == v.attrs->end()) throw TypeError("derivation name missing");
+
+        Bindings::iterator i2 = v.attrs->find(state.sSystem);
+
+        DrvInfo drv(
+            state,
+            state.forceStringNoCtx(*i->value),
+            attrPath,
+            i2 == v.attrs->end() ? "unknown" : state.forceStringNoCtx(*i2->value),
+            v.attrs);
+
+        drvs.push_back(drv);
+        return false;
+
+    } catch (AssertionError & e) {
+        if (ignoreAssertionFailures) return false;
+        throw;
+    }
+}
+
+
+bool getDerivation(EvalState & state, Value & v, DrvInfo & drv,
+    bool ignoreAssertionFailures)
+{
+    Done done;
+    DrvInfos drvs;
+    getDerivation(state, v, "", drvs, done, ignoreAssertionFailures);
+    if (drvs.size() != 1) return false;
+    drv = drvs.front();
+    return true;
+}
+
+
+static string addToPath(const string & s1, const string & s2)
+{
+    return s1.empty() ? s2 : s1 + "." + s2;
+}
+
+
+static void getDerivations(EvalState & state, Value & vIn,
+    const string & pathPrefix, Bindings & autoArgs,
+    DrvInfos & drvs, Done & done,
+    bool ignoreAssertionFailures)
+{
+    Value v;
+    state.autoCallFunction(autoArgs, vIn, v);
+
+    /* Process the expression. */
+    if (!getDerivation(state, v, pathPrefix, drvs, done, ignoreAssertionFailures)) ;
+
+    else if (v.type == tAttrs) {
+
+        /* !!! undocumented hackery to support combining channels in
+           nix-env.cc. */
+        bool combineChannels = v.attrs->find(state.symbols.create("_combineChannels")) != v.attrs->end();
+
+        /* Consider the attributes in sorted order to get more
+           deterministic behaviour in nix-env operations (e.g. when
+           there are names clashes between derivations, the derivation
+           bound to the attribute with the "lower" name should take
+           precedence). */
+        typedef std::map<string, Symbol> SortedSymbols;
+        SortedSymbols attrs;
+        foreach (Bindings::iterator, i, *v.attrs)
+            attrs.insert(std::pair<string, Symbol>(i->name, i->name));
+
+        foreach (SortedSymbols::iterator, i, attrs) {
+            startNest(nest, lvlDebug, format("evaluating attribute `%1%'") % i->first);
+            string pathPrefix2 = addToPath(pathPrefix, i->first);
+            Value & v2(*v.attrs->find(i->second)->value);
+            if (combineChannels)
+                getDerivations(state, v2, pathPrefix2, autoArgs, drvs, done, ignoreAssertionFailures);
+            else if (getDerivation(state, v2, pathPrefix2, drvs, done, ignoreAssertionFailures)) {
+                /* If the value of this attribute is itself a set,
+                   should we recurse into it?  => Only if it has a
+                   `recurseForDerivations = true' attribute. */
+                if (v2.type == tAttrs) {
+                    Bindings::iterator j = v2.attrs->find(state.symbols.create("recurseForDerivations"));
+                    if (j != v2.attrs->end() && state.forceBool(*j->value))
+                        getDerivations(state, v2, pathPrefix2, autoArgs, drvs, done, ignoreAssertionFailures);
+                }
+            }
+        }
+    }
+
+    else if (v.type == tList) {
+        for (unsigned int n = 0; n < v.list.length; ++n) {
+            startNest(nest, lvlDebug,
+                format("evaluating list element"));
+            string pathPrefix2 = addToPath(pathPrefix, (format("%1%") % n).str());
+            if (getDerivation(state, *v.list.elems[n], pathPrefix2, drvs, done, ignoreAssertionFailures))
+                getDerivations(state, *v.list.elems[n], pathPrefix2, autoArgs, drvs, done, ignoreAssertionFailures);
+        }
+    }
+
+    else throw TypeError("expression does not evaluate to a derivation (or a set or list of those)");
+}
+
+
+void getDerivations(EvalState & state, Value & v, const string & pathPrefix,
+    Bindings & autoArgs, DrvInfos & drvs, bool ignoreAssertionFailures)
+{
+    Done done;
+    getDerivations(state, v, pathPrefix, autoArgs, drvs, done, ignoreAssertionFailures);
+}
+
+
+}
diff --git a/src/libexpr/get-drvs.hh b/src/libexpr/get-drvs.hh
new file mode 100644
index 000000000000..aaafff1905e7
--- /dev/null
+++ b/src/libexpr/get-drvs.hh
@@ -0,0 +1,93 @@
+#pragma once
+
+#include "eval.hh"
+
+#include <string>
+#include <map>
+
+#include <boost/shared_ptr.hpp>
+
+
+namespace nix {
+
+
+struct DrvInfo
+{
+public:
+    typedef std::map<string, Path> Outputs;
+
+private:
+    EvalState * state;
+
+    string drvPath;
+    string outPath;
+    string outputName;
+    Outputs outputs;
+
+    bool failed; // set if we get an AssertionError
+
+    Bindings * attrs, * meta;
+
+    Bindings * getMeta();
+
+    bool checkMeta(Value & v);
+
+public:
+    string name;
+    string attrPath; /* path towards the derivation */
+    string system;
+
+    DrvInfo(EvalState & state) : state(&state), failed(false), attrs(0), meta(0) { };
+    DrvInfo(EvalState & state, const string & name, const string & attrPath, const string & system, Bindings * attrs)
+        : state(&state), failed(false), attrs(attrs), meta(0), name(name), attrPath(attrPath), system(system) { };
+
+    string queryDrvPath();
+    string queryOutPath();
+    string queryOutputName();
+    Outputs queryOutputs();
+
+    StringSet queryMetaNames();
+    Value * queryMeta(const string & name);
+    string queryMetaString(const string & name);
+    int queryMetaInt(const string & name, int def);
+    bool queryMetaBool(const string & name, bool def);
+    void setMeta(const string & name, Value * v);
+
+    /*
+    MetaInfo queryMetaInfo(EvalState & state) const;
+    MetaValue queryMetaInfo(EvalState & state, const string & name) const;
+    */
+
+    void setDrvPath(const string & s)
+    {
+        drvPath = s;
+    }
+
+    void setOutPath(const string & s)
+    {
+        outPath = s;
+    }
+
+    void setFailed() { failed = true; };
+    bool hasFailed() { return failed; };
+};
+
+
+#if HAVE_BOEHMGC
+typedef list<DrvInfo, traceable_allocator<DrvInfo> > DrvInfos;
+#else
+typedef list<DrvInfo> DrvInfos;
+#endif
+
+
+/* If value `v' denotes a derivation, store information about the
+   derivation in `drv' and return true.  Otherwise, return false. */
+bool getDerivation(EvalState & state, Value & v, DrvInfo & drv,
+    bool ignoreAssertionFailures);
+
+void getDerivations(EvalState & state, Value & v, const string & pathPrefix,
+    Bindings & autoArgs, DrvInfos & drvs,
+    bool ignoreAssertionFailures);
+
+
+}
diff --git a/src/libexpr/lexer.l b/src/libexpr/lexer.l
new file mode 100644
index 000000000000..911850cc5ba5
--- /dev/null
+++ b/src/libexpr/lexer.l
@@ -0,0 +1,193 @@
+%option reentrant bison-bridge bison-locations
+%option noyywrap
+%option never-interactive
+
+
+%x STRING
+%x IND_STRING
+
+
+%{
+#include "nixexpr.hh"
+#include "parser-tab.hh"
+
+using namespace nix;
+
+namespace nix {
+
+
+static void initLoc(YYLTYPE * loc)
+{
+    loc->first_line = loc->last_line = 1;
+    loc->first_column = loc->last_column = 1;
+}
+
+
+static void adjustLoc(YYLTYPE * loc, const char * s, size_t len)
+{
+    loc->first_line = loc->last_line;
+    loc->first_column = loc->last_column;
+
+    while (len--) {
+       switch (*s++) {
+       case '\r':
+           if (*s == '\n') /* cr/lf */
+               s++;
+           /* fall through */
+       case '\n':
+           ++loc->last_line;
+           loc->last_column = 1;
+           break;
+       default:
+           ++loc->last_column;
+       }
+    }
+}
+
+
+static Expr * unescapeStr(SymbolTable & symbols, const char * s)
+{
+    string t;
+    char c;
+    while ((c = *s++)) {
+        if (c == '\\') {
+            assert(*s);
+            c = *s++;
+            if (c == 'n') t += '\n';
+            else if (c == 'r') t += '\r';
+            else if (c == 't') t += '\t';
+            else t += c;
+        }
+        else if (c == '\r') {
+            /* Normalise CR and CR/LF into LF. */
+            t += '\n';
+            if (*s == '\n') s++; /* cr/lf */
+        }
+        else t += c;
+    }
+    return new ExprString(symbols.create(t));
+}
+
+
+}
+
+#define YY_USER_INIT initLoc(yylloc)
+#define YY_USER_ACTION adjustLoc(yylloc, yytext, yyleng);
+
+%}
+
+
+ID          [a-zA-Z\_][a-zA-Z0-9\_\'\-]*
+INT         [0-9]+
+PATH        [a-zA-Z0-9\.\_\-\+]*(\/[a-zA-Z0-9\.\_\-\+]+)+
+SPATH       \<[a-zA-Z0-9\.\_\-\+]+(\/[a-zA-Z0-9\.\_\-\+]+)*\>
+URI         [a-zA-Z][a-zA-Z0-9\+\-\.]*\:[a-zA-Z0-9\%\/\?\:\@\&\=\+\$\,\-\_\.\!\~\*\']+
+
+
+%%
+
+
+if          { return IF; }
+then        { return THEN; }
+else        { return ELSE; }
+assert      { return ASSERT; }
+with        { return WITH; }
+let         { return LET; }
+in          { return IN; }
+rec         { return REC; }
+inherit     { return INHERIT; }
+or          { return OR_KW; }
+\.\.\.      { return ELLIPSIS; }
+
+\=\=        { return EQ; }
+\!\=        { return NEQ; }
+\<\=        { return LEQ; }
+\>\=        { return GEQ; }
+\&\&        { return AND; }
+\|\|        { return OR; }
+\-\>        { return IMPL; }
+\/\/        { return UPDATE; }
+\+\+        { return CONCAT; }
+
+{ID}        { yylval->id = strdup(yytext); return ID; }
+{INT}       { errno = 0;
+              yylval->n = strtol(yytext, 0, 10);
+              if (errno != 0)
+                  throw ParseError(format("invalid integer `%1%'") % yytext);
+              return INT;
+            }
+
+\$\{        { return DOLLAR_CURLY; }
+
+\"          { BEGIN(STRING); return '"'; }
+<STRING>([^\$\"\\]|\$[^\{\"]|\\.)+ {
+              /* !!! Not quite right: we want a follow restriction on
+                 "$", it shouldn't be followed by a "{".  Right now
+                 "$\"" will be consumed as part of a string, rather
+                 than a "$" followed by the string terminator.
+                 Disallow "$\"" for now. */
+              yylval->e = unescapeStr(data->symbols, yytext);
+              return STR;
+            }
+<STRING>\$\{  { BEGIN(INITIAL); return DOLLAR_CURLY; }
+<STRING>\"  { BEGIN(INITIAL); return '"'; }
+<STRING>.   return yytext[0]; /* just in case: shouldn't be reached */
+
+\'\'(\ *\n)?     { BEGIN(IND_STRING); return IND_STRING_OPEN; }
+<IND_STRING>([^\$\']|\$[^\{\']|\'[^\'\$])+ {
+                   yylval->e = new ExprIndStr(yytext);
+                   return IND_STR;
+                 }
+<IND_STRING>\'\'\$ {
+                   yylval->e = new ExprIndStr("$");
+                   return IND_STR;
+                 }
+<IND_STRING>\'\'\' {
+                   yylval->e = new ExprIndStr("''");
+                   return IND_STR;
+                 }
+<IND_STRING>\'\'\\. {
+                   yylval->e = unescapeStr(data->symbols, yytext + 2);
+                   return IND_STR;
+                 }
+<IND_STRING>\$\{ { BEGIN(INITIAL); return DOLLAR_CURLY; }
+<IND_STRING>\'\' { BEGIN(INITIAL); return IND_STRING_CLOSE; }
+<IND_STRING>\'   {
+                   yylval->e = new ExprIndStr("'");
+                   return IND_STR;
+                 }
+<IND_STRING>.    return yytext[0]; /* just in case: shouldn't be reached */
+
+{PATH}      { yylval->path = strdup(yytext); return PATH; }
+{SPATH}     { yylval->path = strdup(yytext); return SPATH; }
+{URI}       { yylval->uri = strdup(yytext); return URI; }
+
+[ \t\r\n]+    /* eat up whitespace */
+\#[^\r\n]*    /* single-line comments */
+\/\*([^*]|\*[^\/])*\*\/  /* long comments */
+
+.           return yytext[0];
+
+
+%%
+
+
+namespace nix {
+
+/* Horrible, disgusting hack: allow the parser to set the scanner
+   start condition back to STRING.  Necessary in interpolations like
+   "foo${expr}bar"; after the close brace we have to go back to the
+   STRING state. */
+void backToString(yyscan_t scanner)
+{
+    struct yyguts_t * yyg = (struct yyguts_t *) scanner;
+    BEGIN(STRING);
+}
+
+void backToIndString(yyscan_t scanner)
+{
+    struct yyguts_t * yyg = (struct yyguts_t *) scanner;
+    BEGIN(IND_STRING);
+}
+
+}
diff --git a/src/libexpr/local.mk b/src/libexpr/local.mk
new file mode 100644
index 000000000000..431f84b0999e
--- /dev/null
+++ b/src/libexpr/local.mk
@@ -0,0 +1,24 @@
+libraries += libexpr
+
+libexpr_NAME = libnixexpr
+
+libexpr_DIR := $(d)
+
+libexpr_SOURCES := $(wildcard $(d)/*.cc) $(d)/lexer-tab.cc $(d)/parser-tab.cc
+
+libexpr_LIBS = libutil libstore libformat
+
+# The dependency on libgc must be propagated (i.e. meaning that
+# programs/libraries that use libexpr must explicitly pass -lgc),
+# because inline functions in libexpr's header files call libgc.
+libexpr_LDFLAGS_PROPAGATED = $(BDW_GC_LIBS)
+
+$(d)/parser-tab.cc $(d)/parser-tab.hh: $(d)/parser.y
+	$(trace-gen) bison -v -o $(libexpr_DIR)/parser-tab.cc $< -d
+
+$(d)/lexer-tab.cc $(d)/lexer-tab.hh: $(d)/lexer.l
+	$(trace-gen) flex --outfile $(libexpr_DIR)/lexer-tab.cc --header-file=$(libexpr_DIR)/lexer-tab.hh $<
+
+clean-files += $(d)/parser-tab.cc $(d)/parser-tab.hh $(d)/lexer-tab.cc $(d)/lexer-tab.hh
+
+dist-files += $(d)/parser-tab.cc $(d)/parser-tab.hh $(d)/lexer-tab.cc $(d)/lexer-tab.hh
diff --git a/src/libexpr/names.cc b/src/libexpr/names.cc
new file mode 100644
index 000000000000..781c2b6468f9
--- /dev/null
+++ b/src/libexpr/names.cc
@@ -0,0 +1,104 @@
+#include "names.hh"
+#include "util.hh"
+
+
+namespace nix {
+
+
+DrvName::DrvName()
+{
+    name = "";
+}
+
+
+/* Parse a derivation name.  The `name' part of a derivation name is
+   everything up to but not including the first dash *not* followed by
+   a letter.  The `version' part is the rest (excluding the separating
+   dash).  E.g., `apache-httpd-2.0.48' is parsed to (`apache-httpd',
+   '2.0.48'). */
+DrvName::DrvName(const string & s) : hits(0)
+{
+    name = fullName = s;
+    for (unsigned int i = 0; i < s.size(); ++i) {
+        /* !!! isalpha/isdigit are affected by the locale. */
+        if (s[i] == '-' && i + 1 < s.size() && !isalpha(s[i + 1])) {
+            name = string(s, 0, i);
+            version = string(s, i + 1);
+            break;
+        }
+    }
+}
+
+
+bool DrvName::matches(DrvName & n)
+{
+    if (name != "*" && name != n.name) return false;
+    if (version != "" && version != n.version) return false;
+    return true;
+}
+
+
+static string nextComponent(string::const_iterator & p,
+    const string::const_iterator end)
+{
+    /* Skip any dots and dashes (component separators). */
+    while (p != end && (*p == '.' || *p == '-')) ++p;
+
+    if (p == end) return "";
+
+    /* If the first character is a digit, consume the longest sequence
+       of digits.  Otherwise, consume the longest sequence of
+       non-digit, non-separator characters. */
+    string s;
+    if (isdigit(*p))
+        while (p != end && isdigit(*p)) s += *p++;
+    else
+        while (p != end && (!isdigit(*p) && *p != '.' && *p != '-'))
+            s += *p++;
+
+    return s;
+}
+
+
+static bool componentsLT(const string & c1, const string & c2)
+{
+    int n1, n2;
+    bool c1Num = string2Int(c1, n1), c2Num = string2Int(c2, n2);
+
+    if (c1Num && c2Num) return n1 < n2;
+    else if (c1 == "" && c2Num) return true;
+    else if (c1 == "pre" && c2 != "pre") return true;
+    else if (c2 == "pre") return false;
+    /* Assume that `2.3a' < `2.3.1'. */
+    else if (c2Num) return true;
+    else if (c1Num) return false;
+    else return c1 < c2;
+}
+
+
+int compareVersions(const string & v1, const string & v2)
+{
+    string::const_iterator p1 = v1.begin();
+    string::const_iterator p2 = v2.begin();
+
+    while (p1 != v1.end() || p2 != v2.end()) {
+        string c1 = nextComponent(p1, v1.end());
+        string c2 = nextComponent(p2, v2.end());
+        if (componentsLT(c1, c2)) return -1;
+        else if (componentsLT(c2, c1)) return 1;
+    }
+
+    return 0;
+}
+
+
+DrvNames drvNamesFromArgs(const Strings & opArgs)
+{
+    DrvNames result;
+    foreach (Strings::const_iterator, i, opArgs)
+        result.push_back(DrvName(*i));
+    return result;
+}
+
+
+}
diff --git a/src/libexpr/names.hh b/src/libexpr/names.hh
new file mode 100644
index 000000000000..ebe113e82ac1
--- /dev/null
+++ b/src/libexpr/names.hh
@@ -0,0 +1,24 @@
+#pragma once
+
+#include "types.hh"
+
+namespace nix {
+
+struct DrvName
+{
+    string fullName;
+    string name;
+    string version;
+    unsigned int hits;
+
+    DrvName();
+    DrvName(const string & s);
+    bool matches(DrvName & n);
+};
+
+typedef list<DrvName> DrvNames;
+
+int compareVersions(const string & v1, const string & v2);
+DrvNames drvNamesFromArgs(const Strings & opArgs);
+
+}
diff --git a/src/libexpr/nix.sdf b/src/libexpr/nix.sdf
new file mode 100644
index 000000000000..42fb21c3baad
--- /dev/null
+++ b/src/libexpr/nix.sdf
@@ -0,0 +1,141 @@
+%% Note: this SDF grammar is no longer used in the Nix expression
+%% parser and may not be up to date.
+
+definition
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Top level syntax.
+
+module Main
+imports Nix-Exprs Nix-Layout
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Expressions.
+
+module Nix-Exprs
+imports Nix-Lexicals
+exports
+  sorts Expr Formal Bind ExprList
+  context-free start-symbols Expr
+  context-free syntax
+
+    Id -> Expr {cons("Var")}
+    Int -> Expr {cons("Int")}
+    Str -> Expr {cons("Str")}
+    Uri -> Expr {cons("Uri")}
+    Path -> Expr {cons("Path")}
+
+    "(" Expr ")" -> Expr {bracket}
+
+    Expr Expr -> Expr {cons("Call"), left}
+
+    Id ":" Expr -> Expr {cons("Function1")}
+    "{" {Formal ","}* "}" ":" Expr -> Expr {cons("Function")}
+    Id -> Formal {cons("NoDefFormal")}
+    Id "?" Expr -> Formal {cons("DefFormal")}
+
+    "assert" Expr ";" Expr -> Expr {cons("Assert")}
+
+    "with" Expr ";" Expr -> Expr {cons("With")}
+
+    "rec" "{" Bind* "}" -> Expr {cons("Rec")}
+    "let" Bind* "in" Expr -> Expr {cons("Let")}
+    "let" "{" Bind* "}" -> Expr {cons("LetRec")}
+    "{" Bind* "}" -> Expr {cons("Attrs")}
+
+    Id "=" Expr ";" -> Bind {cons("Bind")}
+    "inherit" ("(" Expr ")")? Id* ";" -> Bind {cons("Inherit")}
+
+    "[" ExprList "]" -> Expr {cons("List")}
+    -> ExprList {cons("ExprNil")}
+    Expr ExprList -> ExprList {cons("ExprCons")}
+
+    Expr "." Id -> Expr {cons("Select")}
+
+    "if" Expr "then" Expr "else" Expr -> Expr {cons("If")}
+
+    Expr "==" Expr -> Expr {cons("OpEq"), non-assoc}
+    Expr "!=" Expr -> Expr {cons("OpNEq"), non-assoc}
+
+    "!" Expr -> Expr {cons("OpNot")}
+    Expr "&&" Expr -> Expr {cons("OpAnd"), right}
+    Expr "||" Expr -> Expr {cons("OpOr"), right}
+    Expr "->" Expr -> Expr {cons("OpImpl"), right}
+
+    Expr "//" Expr -> Expr {cons("OpUpdate"), right}
+    Expr "~" Expr -> Expr {cons("SubPath"), non-assoc}
+    Expr "?" Id -> Expr {cons("OpHasAttr")}
+    Expr "+" Expr -> Expr {cons("OpPlus"), left}
+    Expr "++" Expr -> Expr {cons("OpConcat"), right}
+
+  context-free priorities
+
+    Expr "." Id -> Expr
+  > Expr ExprList -> ExprList
+  > Expr Expr -> Expr
+  > Expr "~" Expr -> Expr
+  > Expr "?" Id -> Expr
+  > Expr "++" Expr -> Expr
+  > Expr "+" Expr -> Expr
+  > "!" Expr -> Expr
+  > Expr "//" Expr -> Expr
+  > { Expr "==" Expr -> Expr
+      Expr "!=" Expr -> Expr
+    }
+  > Expr "&&" Expr -> Expr
+  > Expr "||" Expr -> Expr
+  > Expr "->" Expr -> Expr
+  > "if" Expr "then" Expr "else" Expr -> Expr
+  > "assert" Expr ";" Expr -> Expr
+  > "with" Expr ";" Expr -> Expr
+  > Id ":" Expr -> Expr
+  > "{" {Formal ","}* "}" ":" Expr -> Expr
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Lexical syntax.
+
+module Nix-Lexicals
+exports
+  sorts Id Int Str Path Uri
+  lexical syntax
+    [a-zA-Z\_][a-zA-Z0-9\_\']* -> Id
+    "rec" | "let" | "if" | "then" | "else" | "assert" | "with" | "inherit" -> Id {reject}
+
+    [0-9]+ -> Int
+
+    "\"" (~[\"\\] | ("\\" ~[]) )* "\"" -> Str
+    "''" (~[\"\\] | ("\\" ~[]) )* "''" -> Str
+
+    [a-zA-Z0-9\.\_\-\+]* ("/"[a-zA-Z0-9\.\_\-\+]+)+ -> Path
+
+    [a-zA-Z] [a-zA-Z0-9\+\-\.]* ":" [a-zA-Z0-9\%\/\?\:\@\&\=\+\$\,\-\_\.\!\~\*\']+ -> Uri
+
+  lexical restrictions
+    Id -/- [a-zA-Z0-9\_\']
+    Int -/- [0-9]
+    Path -/- [a-zA-Z0-9\.\_\-\+\/]
+    Uri -/- [a-zA-Z0-9\%\/\?\:\@\&\=\+\$\,\-\_\.\!\~\*\']
+    "rec" "let" "if" "then" "else" "assert" "with" "inherit" -/- [A-Za-z0-9\_\']
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Layout.
+
+module Nix-Layout
+exports
+  sorts HashComment Asterisk Comment
+  lexical syntax
+    [\ \t\n] -> LAYOUT
+    HashComment -> LAYOUT
+    Comment -> LAYOUT
+    "#" ~[\n]* -> HashComment
+    "/*" ( ~[\*] | Asterisk )* "*/" -> Comment
+    [\*] ~[\/] -> Asterisk
+  lexical restrictions
+    HashComment -/- ~[\n]
+  context-free restrictions
+    LAYOUT? -/- [\ \t\n\#]
+    LAYOUT? -/- [\/].[\*]
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
new file mode 100644
index 000000000000..9f0bc2630ddc
--- /dev/null
+++ b/src/libexpr/nixexpr.cc
@@ -0,0 +1,391 @@
+#include "nixexpr.hh"
+#include "derivations.hh"
+#include "util.hh"
+
+#include <cstdlib>
+
+
+namespace nix {
+
+
+/* Displaying abstract syntax trees. */
+
+std::ostream & operator << (std::ostream & str, Expr & e)
+{
+    e.show(str);
+    return str;
+}
+
+void Expr::show(std::ostream & str)
+{
+    abort();
+}
+
+void ExprInt::show(std::ostream & str)
+{
+    str << n;
+}
+
+void ExprString::show(std::ostream & str)
+{
+    str << "\"" << s << "\""; // !!! escaping
+}
+
+void ExprPath::show(std::ostream & str)
+{
+    str << s;
+}
+
+void ExprVar::show(std::ostream & str)
+{
+    str << name;
+}
+
+void ExprSelect::show(std::ostream & str)
+{
+    str << "(" << *e << ")." << showAttrPath(attrPath);
+    if (def) str << " or " << *def;
+}
+
+void ExprOpHasAttr::show(std::ostream & str)
+{
+    str << "(" << *e << ") ? " << showAttrPath(attrPath);
+}
+
+void ExprAttrs::show(std::ostream & str)
+{
+    if (recursive) str << "rec ";
+    str << "{ ";
+    foreach (AttrDefs::iterator, i, attrs)
+        if (i->second.inherited)
+            str << "inherit " << i->first << " " << "; ";
+        else
+            str << i->first << " = " << *i->second.e << "; ";
+    foreach (DynamicAttrDefs::iterator, i, dynamicAttrs)
+        str << "\"${" << *i->nameExpr << "}\" = " << *i->valueExpr << "; ";
+    str << "}";
+}
+
+void ExprList::show(std::ostream & str)
+{
+    str << "[ ";
+    foreach (vector<Expr *>::iterator, i, elems)
+        str << "(" << **i << ") ";
+    str << "]";
+}
+
+void ExprLambda::show(std::ostream & str)
+{
+    str << "(";
+    if (matchAttrs) {
+        str << "{ ";
+        bool first = true;
+        foreach (Formals::Formals_::iterator, i, formals->formals) {
+            if (first) first = false; else str << ", ";
+            str << i->name;
+            if (i->def) str << " ? " << *i->def;
+        }
+        str << " }";
+        if (!arg.empty()) str << " @ ";
+    }
+    if (!arg.empty()) str << arg;
+    str << ": " << *body << ")";
+}
+
+void ExprLet::show(std::ostream & str)
+{
+    str << "let ";
+    foreach (ExprAttrs::AttrDefs::iterator, i, attrs->attrs)
+        if (i->second.inherited)
+            str << "inherit " << i->first << "; ";
+        else
+            str << i->first << " = " << *i->second.e << "; ";
+    str << "in " << *body;
+}
+
+void ExprWith::show(std::ostream & str)
+{
+    str << "with " << *attrs << "; " << *body;
+}
+
+void ExprIf::show(std::ostream & str)
+{
+    str << "if " << *cond << " then " << *then << " else " << *else_;
+}
+
+void ExprAssert::show(std::ostream & str)
+{
+    str << "assert " << *cond << "; " << *body;
+}
+
+void ExprOpNot::show(std::ostream & str)
+{
+    str << "! " << *e;
+}
+
+void ExprBuiltin::show(std::ostream & str)
+{
+    str << "builtins." << name;
+}
+
+void ExprConcatStrings::show(std::ostream & str)
+{
+    bool first = true;
+    foreach (vector<Expr *>::iterator, i, *es) {
+        if (first) first = false; else str << " + ";
+        str << **i;
+    }
+}
+
+void ExprPos::show(std::ostream & str)
+{
+    str << "__curPos";
+}
+
+
+std::ostream & operator << (std::ostream & str, const Pos & pos)
+{
+    if (!pos.line)
+        str << "undefined position";
+    else
+        str << (format("`%1%:%2%:%3%'") % pos.file % pos.line % pos.column).str();
+    return str;
+}
+
+
+string showAttrPath(const AttrPath & attrPath)
+{
+    std::ostringstream out;
+    bool first = true;
+    foreach (AttrPath::const_iterator, i, attrPath) {
+        if (!first)
+            out << '.';
+        else
+            first = false;
+        if (i->symbol.set())
+            out << i->symbol;
+        else
+            out << "\"${" << *i->expr << "}\"";
+    }
+    return out.str();
+}
+
+
+Pos noPos;
+
+
+/* Computing levels/displacements for variables. */
+
+void Expr::bindVars(const StaticEnv & env)
+{
+    abort();
+}
+
+void ExprInt::bindVars(const StaticEnv & env)
+{
+}
+
+void ExprString::bindVars(const StaticEnv & env)
+{
+}
+
+void ExprPath::bindVars(const StaticEnv & env)
+{
+}
+
+void ExprVar::bindVars(const StaticEnv & env)
+{
+    /* Check whether the variable appears in the environment.  If so,
+       set its level and displacement. */
+    const StaticEnv * curEnv;
+    unsigned int level;
+    int withLevel = -1;
+    for (curEnv = &env, level = 0; curEnv; curEnv = curEnv->up, level++) {
+        if (curEnv->isWith) {
+            if (withLevel == -1) withLevel = level;
+        } else {
+            StaticEnv::Vars::const_iterator i = curEnv->vars.find(name);
+            if (i != curEnv->vars.end()) {
+                fromWith = false;
+                this->level = level;
+                displ = i->second;
+                return;
+            }
+        }
+    }
+
+    /* Otherwise, the variable must be obtained from the nearest
+       enclosing `with'.  If there is no `with', then we can issue an
+       "undefined variable" error now. */
+    if (withLevel == -1) throw UndefinedVarError(format("undefined variable `%1%' at %2%") % name % pos);
+
+    fromWith = true;
+    this->level = withLevel;
+}
+
+void ExprSelect::bindVars(const StaticEnv & env)
+{
+    e->bindVars(env);
+    if (def) def->bindVars(env);
+    foreach (AttrPath::iterator, i, attrPath)
+        if (!i->symbol.set())
+            i->expr->bindVars(env);
+}
+
+void ExprOpHasAttr::bindVars(const StaticEnv & env)
+{
+    e->bindVars(env);
+    foreach (AttrPath::iterator, i, attrPath)
+        if (!i->symbol.set())
+            i->expr->bindVars(env);
+}
+
+void ExprAttrs::bindVars(const StaticEnv & env)
+{
+    const StaticEnv *dynamicEnv = &env;
+    if (recursive) {
+        StaticEnv newEnv(false, &env);
+        dynamicEnv = &newEnv;
+
+        unsigned int displ = 0;
+        foreach (AttrDefs::iterator, i, attrs)
+            newEnv.vars[i->first] = i->second.displ = displ++;
+
+        foreach (AttrDefs::iterator, i, attrs)
+            i->second.e->bindVars(i->second.inherited ? env : newEnv);
+    }
+
+    else
+        foreach (AttrDefs::iterator, i, attrs)
+            i->second.e->bindVars(env);
+
+    foreach (DynamicAttrDefs::iterator, i, dynamicAttrs) {
+        i->nameExpr->bindVars(*dynamicEnv);
+        i->valueExpr->bindVars(*dynamicEnv);
+    }
+}
+
+void ExprList::bindVars(const StaticEnv & env)
+{
+    foreach (vector<Expr *>::iterator, i, elems)
+        (*i)->bindVars(env);
+}
+
+void ExprLambda::bindVars(const StaticEnv & env)
+{
+    StaticEnv newEnv(false, &env);
+
+    unsigned int displ = 0;
+
+    if (!arg.empty()) newEnv.vars[arg] = displ++;
+
+    if (matchAttrs) {
+        foreach (Formals::Formals_::iterator, i, formals->formals)
+            newEnv.vars[i->name] = displ++;
+
+        foreach (Formals::Formals_::iterator, i, formals->formals)
+            if (i->def) i->def->bindVars(newEnv);
+    }
+
+    body->bindVars(newEnv);
+}
+
+void ExprLet::bindVars(const StaticEnv & env)
+{
+    StaticEnv newEnv(false, &env);
+
+    unsigned int displ = 0;
+    foreach (ExprAttrs::AttrDefs::iterator, i, attrs->attrs)
+        newEnv.vars[i->first] = i->second.displ = displ++;
+
+    foreach (ExprAttrs::AttrDefs::iterator, i, attrs->attrs)
+        i->second.e->bindVars(i->second.inherited ? env : newEnv);
+
+    body->bindVars(newEnv);
+}
+
+void ExprWith::bindVars(const StaticEnv & env)
+{
+    /* Does this `with' have an enclosing `with'?  If so, record its
+       level so that `lookupVar' can look up variables in the previous
+       `with' if this one doesn't contain the desired attribute. */
+    const StaticEnv * curEnv;
+    unsigned int level;
+    prevWith = 0;
+    for (curEnv = &env, level = 1; curEnv; curEnv = curEnv->up, level++)
+        if (curEnv->isWith) {
+            prevWith = level;
+            break;
+        }
+
+    attrs->bindVars(env);
+    StaticEnv newEnv(true, &env);
+    body->bindVars(newEnv);
+}
+
+void ExprIf::bindVars(const StaticEnv & env)
+{
+    cond->bindVars(env);
+    then->bindVars(env);
+    else_->bindVars(env);
+}
+
+void ExprAssert::bindVars(const StaticEnv & env)
+{
+    cond->bindVars(env);
+    body->bindVars(env);
+}
+
+void ExprOpNot::bindVars(const StaticEnv & env)
+{
+    e->bindVars(env);
+}
+
+void ExprBuiltin::bindVars(const StaticEnv & env)
+{
+}
+
+void ExprConcatStrings::bindVars(const StaticEnv & env)
+{
+    foreach (vector<Expr *>::iterator, i, *es)
+        (*i)->bindVars(env);
+}
+
+void ExprPos::bindVars(const StaticEnv & env)
+{
+}
+
+
+/* Storing function names. */
+
+void Expr::setName(Symbol & name)
+{
+}
+
+
+void ExprLambda::setName(Symbol & name)
+{
+    this->name = name;
+    body->setName(name);
+}
+
+
+string ExprLambda::showNamePos() const
+{
+    return (format("%1% at %2%") % (name.set() ? "`" + (string) name + "'" : "an anonymous function") % pos).str();
+}
+
+
+
+/* Symbol table. */
+
+size_t SymbolTable::totalSize() const
+{
+    size_t n = 0;
+    foreach (Symbols::const_iterator, i, symbols)
+        n += i->size();
+    return n;
+}
+
+
+}
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
new file mode 100644
index 000000000000..7586fffb83d4
--- /dev/null
+++ b/src/libexpr/nixexpr.hh
@@ -0,0 +1,332 @@
+#pragma once
+
+#include "value.hh"
+#include "symbol-table.hh"
+
+#include <map>
+
+
+namespace nix {
+
+
+MakeError(EvalError, Error)
+MakeError(ParseError, Error)
+MakeError(AssertionError, EvalError)
+MakeError(ThrownError, AssertionError)
+MakeError(Abort, EvalError)
+MakeError(TypeError, EvalError)
+MakeError(ImportError, EvalError) // error building an imported derivation
+MakeError(UndefinedVarError, Error)
+
+
+/* Position objects. */
+
+struct Pos
+{
+    Symbol file;
+    unsigned int line, column;
+    Pos() : line(0), column(0) { };
+    Pos(const Symbol & file, unsigned int line, unsigned int column)
+        : file(file), line(line), column(column) { };
+    bool operator < (const Pos & p2) const
+    {
+        if (!line) return p2.line;
+        if (!p2.line) return false;
+        int d = ((string) file).compare((string) p2.file);
+        if (d < 0) return true;
+        if (d > 0) return false;
+        if (line < p2.line) return true;
+        if (line > p2.line) return false;
+        return column < p2.column;
+    }
+};
+
+extern Pos noPos;
+
+std::ostream & operator << (std::ostream & str, const Pos & pos);
+
+
+struct Env;
+struct Value;
+class EvalState;
+struct StaticEnv;
+struct Expr;
+
+
+/* An attribute path is a sequence of attribute names. */
+struct AttrName
+{
+    Symbol symbol;
+    Expr *expr;
+    AttrName(const Symbol & s) : symbol(s) {};
+    AttrName(Expr *e) : expr(e) {};
+};
+
+typedef std::vector<AttrName> AttrPath;
+
+string showAttrPath(const AttrPath & attrPath);
+
+
+/* Abstract syntax of Nix expressions. */
+
+struct Expr
+{
+    virtual ~Expr() { };
+    virtual void show(std::ostream & str);
+    virtual void bindVars(const StaticEnv & env);
+    virtual void eval(EvalState & state, Env & env, Value & v);
+    virtual Value * maybeThunk(EvalState & state, Env & env);
+    virtual void setName(Symbol & name);
+};
+
+std::ostream & operator << (std::ostream & str, Expr & e);
+
+#define COMMON_METHODS \
+    void show(std::ostream & str); \
+    void eval(EvalState & state, Env & env, Value & v); \
+    void bindVars(const StaticEnv & env);
+
+struct ExprInt : Expr
+{
+    NixInt n;
+    Value v;
+    ExprInt(NixInt n) : n(n) { mkInt(v, n); };
+    COMMON_METHODS
+    Value * maybeThunk(EvalState & state, Env & env);
+};
+
+struct ExprString : Expr
+{
+    Symbol s;
+    Value v;
+    ExprString(const Symbol & s) : s(s) { mkString(v, s); };
+    COMMON_METHODS
+    Value * maybeThunk(EvalState & state, Env & env);
+};
+
+/* Temporary class used during parsing of indented strings. */
+struct ExprIndStr : Expr
+{
+    string s;
+    ExprIndStr(const string & s) : s(s) { };
+};
+
+struct ExprPath : Expr
+{
+    string s;
+    Value v;
+    ExprPath(const string & s) : s(s) { mkPathNoCopy(v, this->s.c_str()); };
+    COMMON_METHODS
+    Value * maybeThunk(EvalState & state, Env & env);
+};
+
+struct ExprVar : Expr
+{
+    Pos pos;
+    Symbol name;
+
+    /* Whether the variable comes from an environment (e.g. a rec, let
+       or function argument) or from a "with". */
+    bool fromWith;
+
+    /* In the former case, the value is obtained by going `level'
+       levels up from the current environment and getting the
+       `displ'th value in that environment.  In the latter case, the
+       value is obtained by getting the attribute named `name' from
+       the set stored in the environment that is `level' levels up
+       from the current one.*/
+    unsigned int level;
+    unsigned int displ;
+
+    ExprVar(const Pos & pos, const Symbol & name) : pos(pos), name(name) { };
+    COMMON_METHODS
+    Value * maybeThunk(EvalState & state, Env & env);
+};
+
+struct ExprSelect : Expr
+{
+    Expr * e, * def;
+    AttrPath attrPath;
+    ExprSelect(Expr * e, const AttrPath & attrPath, Expr * def) : e(e), def(def), attrPath(attrPath) { };
+    ExprSelect(Expr * e, const Symbol & name) : e(e), def(0) { attrPath.push_back(AttrName(name)); };
+    COMMON_METHODS
+};
+
+struct ExprOpHasAttr : Expr
+{
+    Expr * e;
+    AttrPath attrPath;
+    ExprOpHasAttr(Expr * e, const AttrPath & attrPath) : e(e), attrPath(attrPath) { };
+    COMMON_METHODS
+};
+
+struct ExprAttrs : Expr
+{
+    bool recursive;
+    struct AttrDef {
+        bool inherited;
+        Expr * e;
+        Pos pos;
+        unsigned int displ; // displacement
+        AttrDef(Expr * e, const Pos & pos, bool inherited=false) : inherited(inherited), e(e), pos(pos) { };
+        AttrDef() { };
+    };
+    typedef std::map<Symbol, AttrDef> AttrDefs;
+    AttrDefs attrs;
+    struct DynamicAttrDef {
+        Expr * nameExpr;
+        Expr * valueExpr;
+        Pos pos;
+        DynamicAttrDef(Expr * nameExpr, Expr * valueExpr, const Pos & pos) : nameExpr(nameExpr), valueExpr(valueExpr), pos(pos) { };
+    };
+    typedef std::vector<DynamicAttrDef> DynamicAttrDefs;
+    DynamicAttrDefs dynamicAttrs;
+    ExprAttrs() : recursive(false) { };
+    COMMON_METHODS
+};
+
+struct ExprList : Expr
+{
+    std::vector<Expr *> elems;
+    ExprList() { };
+    COMMON_METHODS
+};
+
+struct Formal
+{
+    Symbol name;
+    Expr * def;
+    Formal(const Symbol & name, Expr * def) : name(name), def(def) { };
+};
+
+struct Formals
+{
+    typedef std::list<Formal> Formals_;
+    Formals_ formals;
+    std::set<Symbol> argNames; // used during parsing
+    bool ellipsis;
+};
+
+struct ExprLambda : Expr
+{
+    Pos pos;
+    Symbol name;
+    Symbol arg;
+    bool matchAttrs;
+    Formals * formals;
+    Expr * body;
+    ExprLambda(const Pos & pos, const Symbol & arg, bool matchAttrs, Formals * formals, Expr * body)
+        : pos(pos), arg(arg), matchAttrs(matchAttrs), formals(formals), body(body)
+    {
+        if (!arg.empty() && formals && formals->argNames.find(arg) != formals->argNames.end())
+            throw ParseError(format("duplicate formal function argument `%1%' at %2%")
+                % arg % pos);
+    };
+    void setName(Symbol & name);
+    string showNamePos() const;
+    COMMON_METHODS
+};
+
+struct ExprLet : Expr
+{
+    ExprAttrs * attrs;
+    Expr * body;
+    ExprLet(ExprAttrs * attrs, Expr * body) : attrs(attrs), body(body) { };
+    COMMON_METHODS
+};
+
+struct ExprWith : Expr
+{
+    Pos pos;
+    Expr * attrs, * body;
+    unsigned int prevWith;
+    ExprWith(const Pos & pos, Expr * attrs, Expr * body) : pos(pos), attrs(attrs), body(body) { };
+    COMMON_METHODS
+};
+
+struct ExprIf : Expr
+{
+    Expr * cond, * then, * else_;
+    ExprIf(Expr * cond, Expr * then, Expr * else_) : cond(cond), then(then), else_(else_) { };
+    COMMON_METHODS
+};
+
+struct ExprAssert : Expr
+{
+    Pos pos;
+    Expr * cond, * body;
+    ExprAssert(const Pos & pos, Expr * cond, Expr * body) : pos(pos), cond(cond), body(body) { };
+    COMMON_METHODS
+};
+
+struct ExprOpNot : Expr
+{
+    Expr * e;
+    ExprOpNot(Expr * e) : e(e) { };
+    COMMON_METHODS
+};
+
+struct ExprBuiltin : Expr
+{
+    Symbol name;
+    ExprBuiltin(const Symbol & name) : name(name) { };
+    COMMON_METHODS
+};
+
+#define MakeBinOp(name, s) \
+    struct Expr##name : Expr \
+    { \
+        Expr * e1, * e2; \
+        Expr##name(Expr * e1, Expr * e2) : e1(e1), e2(e2) { }; \
+        void show(std::ostream & str) \
+        { \
+            str << *e1 << " " s " " << *e2; \
+        } \
+        void bindVars(const StaticEnv & env) \
+        { \
+            e1->bindVars(env); e2->bindVars(env); \
+        } \
+        void eval(EvalState & state, Env & env, Value & v); \
+    };
+
+MakeBinOp(App, "")
+MakeBinOp(OpEq, "==")
+MakeBinOp(OpNEq, "!=")
+MakeBinOp(OpAnd, "&&")
+MakeBinOp(OpOr, "||")
+MakeBinOp(OpImpl, "->")
+MakeBinOp(OpUpdate, "//")
+MakeBinOp(OpConcatLists, "++")
+
+struct ExprConcatStrings : Expr
+{
+    bool forceString;
+    vector<Expr *> * es;
+    ExprConcatStrings(bool forceString, vector<Expr *> * es)
+        : forceString(forceString), es(es) { };
+    COMMON_METHODS
+};
+
+struct ExprPos : Expr
+{
+    Pos pos;
+    ExprPos(const Pos & pos) : pos(pos) { };
+    COMMON_METHODS
+};
+
+
+/* Static environments are used to map variable names onto (level,
+   displacement) pairs used to obtain the value of the variable at
+   runtime. */
+struct StaticEnv
+{
+    bool isWith;
+    const StaticEnv * up;
+    typedef std::map<Symbol, unsigned int> Vars;
+    Vars vars;
+    StaticEnv(bool isWith, const StaticEnv * up) : isWith(isWith), up(up) { };
+};
+
+
+
+}
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
new file mode 100644
index 000000000000..8a084fea0697
--- /dev/null
+++ b/src/libexpr/parser.y
@@ -0,0 +1,650 @@
+%glr-parser
+%pure-parser
+%locations
+%error-verbose
+%defines
+/* %no-lines */
+%parse-param { void * scanner }
+%parse-param { nix::ParseData * data }
+%lex-param { void * scanner }
+%lex-param { nix::ParseData * data }
+%expect 1
+%expect-rr 1
+
+%code requires {
+
+#ifndef BISON_HEADER
+#define BISON_HEADER
+
+#include "util.hh"
+
+#include "nixexpr.hh"
+#include "eval.hh"
+
+namespace nix {
+
+    struct ParseData
+    {
+        EvalState & state;
+        SymbolTable & symbols;
+        Expr * result;
+        Path basePath;
+        Symbol path;
+        string error;
+        Symbol sLetBody;
+        ParseData(EvalState & state)
+            : state(state)
+            , symbols(state.symbols)
+            , sLetBody(symbols.create("<let-body>"))
+            { };
+    };
+
+}
+
+#define YY_DECL int yylex \
+    (YYSTYPE * yylval_param, YYLTYPE * yylloc_param, yyscan_t yyscanner, nix::ParseData * data)
+
+#endif
+
+}
+
+%{
+
+#include "parser-tab.hh"
+#include "lexer-tab.hh"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+YY_DECL;
+
+using namespace nix;
+
+
+namespace nix {
+
+
+static void dupAttr(const AttrPath & attrPath, const Pos & pos, const Pos & prevPos)
+{
+    throw ParseError(format("attribute `%1%' at %2% already defined at %3%")
+        % showAttrPath(attrPath) % pos % prevPos);
+}
+
+
+static void dupAttr(Symbol attr, const Pos & pos, const Pos & prevPos)
+{
+    throw ParseError(format("attribute `%1%' at %2% already defined at %3%")
+        % attr % pos % prevPos);
+}
+
+
+static void addAttr(ExprAttrs * attrs, AttrPath & attrPath,
+    Expr * e, const Pos & pos)
+{
+    AttrPath::iterator i;
+    // All attrpaths have at least one attr
+    assert(!attrPath.empty());
+    for (i = attrPath.begin(); i + 1 < attrPath.end(); i++) {
+        if (i->symbol.set()) {
+            ExprAttrs::AttrDefs::iterator j = attrs->attrs.find(i->symbol);
+            if (j != attrs->attrs.end()) {
+                if (!j->second.inherited) {
+                    ExprAttrs * attrs2 = dynamic_cast<ExprAttrs *>(j->second.e);
+                    if (!attrs2) dupAttr(attrPath, pos, j->second.pos);
+                    attrs = attrs2;
+                } else
+                    dupAttr(attrPath, pos, j->second.pos);
+            } else {
+                ExprAttrs * nested = new ExprAttrs;
+                attrs->attrs[i->symbol] = ExprAttrs::AttrDef(nested, pos);
+                attrs = nested;
+            }
+        } else {
+            ExprAttrs *nested = new ExprAttrs;
+            attrs->dynamicAttrs.push_back(ExprAttrs::DynamicAttrDef(i->expr, nested, pos));
+            attrs = nested;
+        }
+    }
+    if (i->symbol.set()) {
+        ExprAttrs::AttrDefs::iterator j = attrs->attrs.find(i->symbol);
+        if (j != attrs->attrs.end()) {
+            dupAttr(attrPath, pos, j->second.pos);
+        } else {
+            attrs->attrs[i->symbol] = ExprAttrs::AttrDef(e, pos);
+            e->setName(i->symbol);
+        }
+    } else {
+        attrs->dynamicAttrs.push_back(ExprAttrs::DynamicAttrDef(i->expr, e, pos));
+    }
+}
+
+
+static void addFormal(const Pos & pos, Formals * formals, const Formal & formal)
+{
+    if (formals->argNames.find(formal.name) != formals->argNames.end())
+        throw ParseError(format("duplicate formal function argument `%1%' at %2%")
+            % formal.name % pos);
+    formals->formals.push_front(formal);
+    formals->argNames.insert(formal.name);
+}
+
+
+static Expr * stripIndentation(SymbolTable & symbols, vector<Expr *> & es)
+{
+    if (es.empty()) return new ExprString(symbols.create(""));
+
+    /* Figure out the minimum indentation.  Note that by design
+       whitespace-only final lines are not taken into account.  (So
+       the " " in "\n ''" is ignored, but the " " in "\n foo''" is.) */
+    bool atStartOfLine = true; /* = seen only whitespace in the current line */
+    unsigned int minIndent = 1000000;
+    unsigned int curIndent = 0;
+    foreach (vector<Expr *>::iterator, i, es) {
+        ExprIndStr * e = dynamic_cast<ExprIndStr *>(*i);
+        if (!e) {
+            /* Anti-quotations end the current start-of-line whitespace. */
+            if (atStartOfLine) {
+                atStartOfLine = false;
+                if (curIndent < minIndent) minIndent = curIndent;
+            }
+            continue;
+        }
+        for (unsigned int j = 0; j < e->s.size(); ++j) {
+            if (atStartOfLine) {
+                if (e->s[j] == ' ')
+                    curIndent++;
+                else if (e->s[j] == '\n') {
+                    /* Empty line, doesn't influence minimum
+                       indentation. */
+                    curIndent = 0;
+                } else {
+                    atStartOfLine = false;
+                    if (curIndent < minIndent) minIndent = curIndent;
+                }
+            } else if (e->s[j] == '\n') {
+                atStartOfLine = true;
+                curIndent = 0;
+            }
+        }
+    }
+
+    /* Strip spaces from each line. */
+    vector<Expr *> * es2 = new vector<Expr *>;
+    atStartOfLine = true;
+    unsigned int curDropped = 0;
+    unsigned int n = es.size();
+    for (vector<Expr *>::iterator i = es.begin(); i != es.end(); ++i, --n) {
+        ExprIndStr * e = dynamic_cast<ExprIndStr *>(*i);
+        if (!e) {
+            atStartOfLine = false;
+            curDropped = 0;
+            es2->push_back(*i);
+            continue;
+        }
+
+        string s2;
+        for (unsigned int j = 0; j < e->s.size(); ++j) {
+            if (atStartOfLine) {
+                if (e->s[j] == ' ') {
+                    if (curDropped++ >= minIndent)
+                        s2 += e->s[j];
+                }
+                else if (e->s[j] == '\n') {
+                    curDropped = 0;
+                    s2 += e->s[j];
+                } else {
+                    atStartOfLine = false;
+                    curDropped = 0;
+                    s2 += e->s[j];
+                }
+            } else {
+                s2 += e->s[j];
+                if (e->s[j] == '\n') atStartOfLine = true;
+            }
+        }
+
+        /* Remove the last line if it is empty and consists only of
+           spaces. */
+        if (n == 1) {
+            string::size_type p = s2.find_last_of('\n');
+            if (p != string::npos && s2.find_first_not_of(' ', p + 1) == string::npos)
+                s2 = string(s2, 0, p + 1);
+        }
+
+        es2->push_back(new ExprString(symbols.create(s2)));
+    }
+
+    /* If this is a single string, then don't do a concatenation. */
+    return es2->size() == 1 && dynamic_cast<ExprString *>((*es2)[0]) ? (*es2)[0] : new ExprConcatStrings(true, es2);
+}
+
+
+void backToString(yyscan_t scanner);
+void backToIndString(yyscan_t scanner);
+
+
+static Pos makeCurPos(const YYLTYPE & loc, ParseData * data)
+{
+    return Pos(data->path, loc.first_line, loc.first_column);
+}
+
+#define CUR_POS makeCurPos(*yylocp, data)
+
+
+}
+
+
+void yyerror(YYLTYPE * loc, yyscan_t scanner, ParseData * data, const char * error)
+{
+    data->error = (format("%1%, at %2%")
+        % error % makeCurPos(*loc, data)).str();
+}
+
+
+%}
+
+%union {
+  // !!! We're probably leaking stuff here.
+  nix::Expr * e;
+  nix::ExprList * list;
+  nix::ExprAttrs * attrs;
+  nix::Formals * formals;
+  nix::Formal * formal;
+  nix::NixInt n;
+  const char * id; // !!! -> Symbol
+  char * path;
+  char * uri;
+  std::vector<nix::AttrName> * attrNames;
+  std::vector<nix::Expr *> * string_parts;
+}
+
+%type <e> start expr expr_function expr_if expr_op
+%type <e> expr_app expr_select expr_simple
+%type <list> expr_list
+%type <attrs> binds
+%type <formals> formals
+%type <formal> formal
+%type <attrNames> attrs attrpath
+%type <string_parts> string_parts_interpolated ind_string_parts
+%type <e> string_parts string_attr
+%type <id> attr
+%token <id> ID ATTRPATH
+%token <e> STR IND_STR
+%token <n> INT
+%token <path> PATH SPATH
+%token <uri> URI
+%token IF THEN ELSE ASSERT WITH LET IN REC INHERIT EQ NEQ AND OR IMPL OR_KW
+%token DOLLAR_CURLY /* == ${ */
+%token IND_STRING_OPEN IND_STRING_CLOSE
+%token ELLIPSIS
+
+%nonassoc IMPL
+%left OR
+%left AND
+%nonassoc EQ NEQ
+%left '<' '>' LEQ GEQ
+%right UPDATE
+%left NOT
+%left '+' '-'
+%left '*' '/'
+%right CONCAT
+%nonassoc '?'
+%nonassoc '~'
+%nonassoc NEGATE
+
+%%
+
+start: expr { data->result = $1; };
+
+expr: expr_function;
+
+expr_function
+  : ID ':' expr_function
+    { $$ = new ExprLambda(CUR_POS, data->symbols.create($1), false, 0, $3); }
+  | '{' formals '}' ':' expr_function
+    { $$ = new ExprLambda(CUR_POS, data->symbols.create(""), true, $2, $5); }
+  | '{' formals '}' '@' ID ':' expr_function
+    { $$ = new ExprLambda(CUR_POS, data->symbols.create($5), true, $2, $7); }
+  | ID '@' '{' formals '}' ':' expr_function
+    { $$ = new ExprLambda(CUR_POS, data->symbols.create($1), true, $4, $7); }
+  | ASSERT expr ';' expr_function
+    { $$ = new ExprAssert(CUR_POS, $2, $4); }
+  | WITH expr ';' expr_function
+    { $$ = new ExprWith(CUR_POS, $2, $4); }
+  | LET binds IN expr_function
+    { if (!$2->dynamicAttrs.empty())
+        throw ParseError(format("dynamic attributes not allowed in let at %1%")
+            % CUR_POS);
+      $$ = new ExprLet($2, $4);
+    }
+  | expr_if
+  ;
+
+expr_if
+  : IF expr THEN expr ELSE expr { $$ = new ExprIf($2, $4, $6); }
+  | expr_op
+  ;
+
+expr_op
+  : '!' expr_op %prec NOT { $$ = new ExprOpNot($2); }
+| '-' expr_op %prec NEGATE { $$ = new ExprApp(new ExprApp(new ExprBuiltin(data->symbols.create("sub")), new ExprInt(0)), $2); }
+  | expr_op EQ expr_op { $$ = new ExprOpEq($1, $3); }
+  | expr_op NEQ expr_op { $$ = new ExprOpNEq($1, $3); }
+  | expr_op '<' expr_op { $$ = new ExprApp(new ExprApp(new ExprBuiltin(data->symbols.create("lessThan")), $1), $3); }
+  | expr_op LEQ expr_op { $$ = new ExprOpNot(new ExprApp(new ExprApp(new ExprBuiltin(data->symbols.create("lessThan")), $3), $1)); }
+  | expr_op '>' expr_op { $$ = new ExprApp(new ExprApp(new ExprBuiltin(data->symbols.create("lessThan")), $3), $1); }
+  | expr_op GEQ expr_op { $$ = new ExprOpNot(new ExprApp(new ExprApp(new ExprBuiltin(data->symbols.create("lessThan")), $1), $3)); }
+  | expr_op AND expr_op { $$ = new ExprOpAnd($1, $3); }
+  | expr_op OR expr_op { $$ = new ExprOpOr($1, $3); }
+  | expr_op IMPL expr_op { $$ = new ExprOpImpl($1, $3); }
+  | expr_op UPDATE expr_op { $$ = new ExprOpUpdate($1, $3); }
+  | expr_op '?' attrpath { $$ = new ExprOpHasAttr($1, *$3); }
+  | expr_op '+' expr_op
+    { vector<Expr *> * l = new vector<Expr *>;
+      l->push_back($1);
+      l->push_back($3);
+      $$ = new ExprConcatStrings(false, l);
+    }
+  | expr_op '-' expr_op { $$ = new ExprApp(new ExprApp(new ExprBuiltin(data->symbols.create("sub")), $1), $3); }
+  | expr_op '*' expr_op { $$ = new ExprApp(new ExprApp(new ExprBuiltin(data->symbols.create("mul")), $1), $3); }
+  | expr_op '/' expr_op { $$ = new ExprApp(new ExprApp(new ExprBuiltin(data->symbols.create("div")), $1), $3); }
+  | expr_op CONCAT expr_op { $$ = new ExprOpConcatLists($1, $3); }
+  | expr_app
+  ;
+
+expr_app
+  : expr_app expr_select
+    { $$ = new ExprApp($1, $2); }
+  | expr_select { $$ = $1; }
+  ;
+
+expr_select
+  : expr_simple '.' attrpath
+    { $$ = new ExprSelect($1, *$3, 0); }
+  | expr_simple '.' attrpath OR_KW expr_select
+    { $$ = new ExprSelect($1, *$3, $5); }
+  | /* Backwards compatibility: because Nixpkgs has a rarely used
+       function named ‘or’, allow stuff like ‘map or [...]’. */
+    expr_simple OR_KW
+    { $$ = new ExprApp($1, new ExprVar(CUR_POS, data->symbols.create("or"))); }
+  | expr_simple { $$ = $1; }
+  ;
+
+expr_simple
+  : ID {
+      if (strcmp($1, "__curPos") == 0)
+          $$ = new ExprPos(CUR_POS);
+      else
+          $$ = new ExprVar(CUR_POS, data->symbols.create($1));
+  }
+  | INT { $$ = new ExprInt($1); }
+  | '"' string_parts '"' { $$ = $2; }
+  | IND_STRING_OPEN ind_string_parts IND_STRING_CLOSE {
+      $$ = stripIndentation(data->symbols, *$2);
+  }
+  | PATH { $$ = new ExprPath(absPath($1, data->basePath)); }
+  | SPATH {
+      string path($1 + 1, strlen($1) - 2);
+      Path path2 = data->state.findFile(path);
+      /* The file wasn't found in the search path.  However, we can't
+         throw an error here, because the expression might never be
+         evaluated.  So return an expression that lazily calls
+         ‘throw’. */
+      $$ = path2 == ""
+          ? (Expr * ) new ExprApp(
+              new ExprBuiltin(data->symbols.create("throw")),
+              new ExprString(data->symbols.create(
+                      (format("file `%1%' was not found in the Nix search path (add it using $NIX_PATH or -I)") % path).str())))
+          : (Expr * ) new ExprPath(path2);
+  }
+  | URI { $$ = new ExprString(data->symbols.create($1)); }
+  | '(' expr ')' { $$ = $2; }
+  /* Let expressions `let {..., body = ...}' are just desugared
+     into `(rec {..., body = ...}).body'. */
+  | LET '{' binds '}'
+    { $3->recursive = true; $$ = new ExprSelect($3, data->symbols.create("body")); }
+  | REC '{' binds '}'
+    { $3->recursive = true; $$ = $3; }
+  | '{' binds '}'
+    { $$ = $2; }
+  | '[' expr_list ']' { $$ = $2; }
+  ;
+
+string_parts
+  : STR
+  | string_parts_interpolated { $$ = new ExprConcatStrings(true, $1); }
+  | { $$ = new ExprString(data->symbols.create("")); }
+  ;
+
+string_parts_interpolated
+  : string_parts_interpolated STR { $$ = $1; $1->push_back($2); }
+  | string_parts_interpolated DOLLAR_CURLY expr '}' { backToString(scanner); $$ = $1; $1->push_back($3); }
+  | STR DOLLAR_CURLY expr '}'
+    {
+      backToString(scanner);
+      $$ = new vector<Expr *>;
+      $$->push_back($1);
+      $$->push_back($3);
+    }
+  | DOLLAR_CURLY expr '}'
+    {
+      backToString(scanner);
+      $$ = new vector<Expr *>;
+      $$->push_back($2);
+    }
+  ;
+
+ind_string_parts
+  : ind_string_parts IND_STR { $$ = $1; $1->push_back($2); }
+  | ind_string_parts DOLLAR_CURLY expr '}' { backToIndString(scanner); $$ = $1; $1->push_back($3); }
+  | { $$ = new vector<Expr *>; }
+  ;
+
+binds
+  : binds attrpath '=' expr ';' { $$ = $1; addAttr($$, *$2, $4, makeCurPos(@2, data)); }
+  | binds INHERIT attrs ';'
+    { $$ = $1;
+      foreach (AttrPath::iterator, i, *$3) {
+          if ($$->attrs.find(i->symbol) != $$->attrs.end())
+              dupAttr(i->symbol, makeCurPos(@3, data), $$->attrs[i->symbol].pos);
+          Pos pos = makeCurPos(@3, data);
+          $$->attrs[i->symbol] = ExprAttrs::AttrDef(new ExprVar(CUR_POS, i->symbol), pos, true);
+      }
+    }
+  | binds INHERIT '(' expr ')' attrs ';'
+    { $$ = $1;
+      /* !!! Should ensure sharing of the expression in $4. */
+      foreach (AttrPath::iterator, i, *$6) {
+          if ($$->attrs.find(i->symbol) != $$->attrs.end())
+              dupAttr(i->symbol, makeCurPos(@6, data), $$->attrs[i->symbol].pos);
+          $$->attrs[i->symbol] = ExprAttrs::AttrDef(new ExprSelect($4, i->symbol), makeCurPos(@6, data));
+      }
+    }
+  | { $$ = new ExprAttrs; }
+  ;
+
+attrs
+  : attrs attr { $$ = $1; $1->push_back(AttrName(data->symbols.create($2))); }
+  | attrs string_attr
+    { $$ = $1;
+      ExprString *str = dynamic_cast<ExprString *>($2);
+      if (str) {
+          $$->push_back(AttrName(str->s));
+          delete str;
+      } else
+        throw ParseError(format("dynamic attributes not allowed in inherit at %1%")
+            % makeCurPos(@2, data));
+    }
+  | { $$ = new AttrPath; }
+  ;
+
+attrpath
+  : attrpath '.' attr { $$ = $1; $1->push_back(AttrName(data->symbols.create($3))); }
+  | attrpath '.' string_attr
+    { $$ = $1;
+      ExprString *str = dynamic_cast<ExprString *>($3);
+      if (str) {
+          $$->push_back(AttrName(str->s));
+          delete str;
+      } else
+          $$->push_back(AttrName($3));
+    }
+  | attr { $$ = new vector<AttrName>; $$->push_back(AttrName(data->symbols.create($1))); }
+  | string_attr
+    { $$ = new vector<AttrName>;
+      ExprString *str = dynamic_cast<ExprString *>($1);
+      if (str) {
+          $$->push_back(AttrName(str->s));
+          delete str;
+      } else
+          $$->push_back(AttrName($1));
+    }
+  ;
+
+attr
+  : ID { $$ = $1; }
+  | OR_KW { $$ = "or"; }
+  ;
+
+string_attr
+  : '"' string_parts '"' { $$ = $2; }
+  | DOLLAR_CURLY expr '}' { $$ = new ExprConcatStrings(true, new vector<Expr*>(1, $2)); }
+  ;
+
+expr_list
+  : expr_list expr_select { $$ = $1; $1->elems.push_back($2); /* !!! dangerous */ }
+  | { $$ = new ExprList; }
+  ;
+
+formals
+  : formal ',' formals
+    { $$ = $3; addFormal(CUR_POS, $$, *$1); }
+  | formal
+    { $$ = new Formals; addFormal(CUR_POS, $$, *$1); $$->ellipsis = false; }
+  |
+    { $$ = new Formals; $$->ellipsis = false; }
+  | ELLIPSIS
+    { $$ = new Formals; $$->ellipsis = true; }
+  ;
+
+formal
+  : ID { $$ = new Formal(data->symbols.create($1), 0); }
+  | ID '?' expr { $$ = new Formal(data->symbols.create($1), $3); }
+  ;
+
+%%
+
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+
+#include <eval.hh>
+
+
+namespace nix {
+
+
+Expr * EvalState::parse(const char * text,
+    const Path & path, const Path & basePath, StaticEnv & staticEnv)
+{
+    yyscan_t scanner;
+    ParseData data(*this);
+    data.basePath = basePath;
+    data.path = data.symbols.create(path);
+
+    yylex_init(&scanner);
+    yy_scan_string(text, scanner);
+    int res = yyparse(scanner, &data);
+    yylex_destroy(scanner);
+
+    if (res) throw ParseError(data.error);
+
+    data.result->bindVars(staticEnv);
+
+    return data.result;
+}
+
+
+Path resolveExprPath(Path path)
+{
+    assert(path[0] == '/');
+
+    /* If `path' is a symlink, follow it.  This is so that relative
+       path references work. */
+    struct stat st;
+    while (true) {
+        if (lstat(path.c_str(), &st))
+            throw SysError(format("getting status of `%1%'") % path);
+        if (!S_ISLNK(st.st_mode)) break;
+        path = absPath(readLink(path), dirOf(path));
+    }
+
+    /* If `path' refers to a directory, append `/default.nix'. */
+    if (S_ISDIR(st.st_mode))
+        path = canonPath(path + "/default.nix");
+
+    return path;
+}
+
+
+Expr * EvalState::parseExprFromFile(const Path & path)
+{
+    return parse(readFile(path).c_str(), path, dirOf(path), staticBaseEnv);
+}
+
+
+Expr * EvalState::parseExprFromString(const string & s, const Path & basePath, StaticEnv & staticEnv)
+{
+    return parse(s.c_str(), "(string)", basePath, staticEnv);
+}
+
+
+Expr * EvalState::parseExprFromString(const string & s, const Path & basePath)
+{
+    return parseExprFromString(s, basePath, staticBaseEnv);
+}
+
+
+void EvalState::addToSearchPath(const string & s)
+{
+    size_t pos = s.find('=');
+    string prefix;
+    Path path;
+    if (pos == string::npos) {
+        path = s;
+    } else {
+        prefix = string(s, 0, pos);
+        path = string(s, pos + 1);
+    }
+
+    path = absPath(path);
+    if (pathExists(path)) {
+        debug(format("adding path `%1%' to the search path") % path);
+        searchPath.insert(searchPathInsertionPoint, std::pair<string, Path>(prefix, path));
+    }
+}
+
+
+Path EvalState::findFile(const string & path)
+{
+    foreach (SearchPath::iterator, i, searchPath) {
+        Path res;
+        if (i->first.empty())
+            res = i->second + "/" + path;
+        else {
+            if (path.compare(0, i->first.size(), i->first) != 0 ||
+                (path.size() > i->first.size() && path[i->first.size()] != '/'))
+                continue;
+            res = i->second +
+                (path.size() == i->first.size() ? "" : "/" + string(path, i->first.size()));
+        }
+        if (pathExists(res)) return canonPath(res);
+    }
+    return "";
+}
+
+
+}
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
new file mode 100644
index 000000000000..ca316f08af13
--- /dev/null
+++ b/src/libexpr/primops.cc
@@ -0,0 +1,1336 @@
+#include "eval.hh"
+#include "misc.hh"
+#include "globals.hh"
+#include "store-api.hh"
+#include "util.hh"
+#include "archive.hh"
+#include "value-to-xml.hh"
+#include "value-to-json.hh"
+#include "names.hh"
+#include "eval-inline.hh"
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#include <algorithm>
+#include <cstring>
+
+
+namespace nix {
+
+
+/*************************************************************
+ * Miscellaneous
+ *************************************************************/
+
+
+/* Decode a context string ‘!<name>!<path>’ into a pair <path,
+   name>. */
+std::pair<string, string> decodeContext(const string & s)
+{
+    if (s.at(0) == '!') {
+        size_t index = s.find("!", 1);
+        return std::pair<string, string>(string(s, index + 1), string(s, 1, index - 1));
+    } else
+        return std::pair<string, string>(s, "");
+}
+
+
+/* Load and evaluate an expression from path specified by the
+   argument. */
+static void prim_import(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    Path path = state.coerceToPath(*args[0], context);
+
+    foreach (PathSet::iterator, i, context) {
+        Path ctx = decodeContext(*i).first;
+        assert(isStorePath(ctx));
+        if (!store->isValidPath(ctx))
+            throw EvalError(format("cannot import `%1%', since path `%2%' is not valid")
+                % path % ctx);
+        if (isDerivation(ctx))
+            try {
+                /* For performance, prefetch all substitute info. */
+                PathSet willBuild, willSubstitute, unknown;
+                unsigned long long downloadSize, narSize;
+                queryMissing(*store, singleton<PathSet>(ctx),
+                    willBuild, willSubstitute, unknown, downloadSize, narSize);
+
+                /* !!! If using a substitute, we only need to fetch
+                   the selected output of this derivation. */
+                store->buildPaths(singleton<PathSet>(ctx));
+            } catch (Error & e) {
+                throw ImportError(e.msg());
+            }
+    }
+
+    if (isStorePath(path) && store->isValidPath(path) && isDerivation(path)) {
+        Derivation drv = parseDerivation(readFile(path));
+        Value & w = *state.allocValue();
+        state.mkAttrs(w, 1 + drv.outputs.size());
+        mkString(*state.allocAttr(w, state.sDrvPath), path, singleton<PathSet>("=" + path));
+        state.mkList(*state.allocAttr(w, state.symbols.create("outputs")), drv.outputs.size());
+        unsigned int outputs_index = 0;
+
+        Value * outputsVal = w.attrs->find(state.symbols.create("outputs"))->value;
+        foreach (DerivationOutputs::iterator, i, drv.outputs) {
+            mkString(*state.allocAttr(w, state.symbols.create(i->first)),
+                i->second.path, singleton<PathSet>("!" + i->first + "!" + path));
+            mkString(*(outputsVal->list.elems[outputs_index++] = state.allocValue()),
+                i->first);
+        }
+        w.attrs->sort();
+        Value fun;
+        state.evalFile(state.findFile("nix/imported-drv-to-derivation.nix"), fun);
+        state.forceFunction(fun);
+        mkApp(v, fun, w);
+        state.forceAttrs(v);
+    } else {
+        state.evalFile(path, v);
+    }
+}
+
+
+/* Return a string representing the type of the expression. */
+static void prim_typeOf(EvalState & state, Value * * args, Value & v)
+{
+    state.forceValue(*args[0]);
+    string t;
+    switch (args[0]->type) {
+        case tInt: t = "int"; break;
+        case tBool: t = "bool"; break;
+        case tString: t = "string"; break;
+        case tPath: t = "path"; break;
+        case tNull: t = "null"; break;
+        case tAttrs: t = "set"; break;
+        case tList: t = "list"; break;
+        case tLambda:
+        case tPrimOp:
+        case tPrimOpApp:
+            t = "lambda";
+            break;
+        default: abort();
+    }
+    mkString(v, state.symbols.create(t));
+}
+
+
+/* Determine whether the argument is the null value. */
+static void prim_isNull(EvalState & state, Value * * args, Value & v)
+{
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tNull);
+}
+
+
+/* Determine whether the argument is a function. */
+static void prim_isFunction(EvalState & state, Value * * args, Value & v)
+{
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tLambda);
+}
+
+
+/* Determine whether the argument is an integer. */
+static void prim_isInt(EvalState & state, Value * * args, Value & v)
+{
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tInt);
+}
+
+
+/* Determine whether the argument is a string. */
+static void prim_isString(EvalState & state, Value * * args, Value & v)
+{
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tString);
+}
+
+
+/* Determine whether the argument is a Boolean. */
+static void prim_isBool(EvalState & state, Value * * args, Value & v)
+{
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tBool);
+}
+
+
+struct CompareValues
+{
+    bool operator () (const Value * v1, const Value * v2) const
+    {
+        if (v1->type != v2->type)
+            throw EvalError("cannot compare values of different types");
+        switch (v1->type) {
+            case tInt:
+                return v1->integer < v2->integer;
+            case tString:
+                return strcmp(v1->string.s, v2->string.s) < 0;
+            case tPath:
+                return strcmp(v1->path, v2->path) < 0;
+            default:
+                throw EvalError(format("cannot compare %1% with %2%") % showType(*v1) % showType(*v2));
+        }
+    }
+};
+
+
+#if HAVE_BOEHMGC
+typedef list<Value *, gc_allocator<Value *> > ValueList;
+#else
+typedef list<Value *> ValueList;
+#endif
+
+
+static void prim_genericClosure(EvalState & state, Value * * args, Value & v)
+{
+    startNest(nest, lvlDebug, "finding dependencies");
+
+    state.forceAttrs(*args[0]);
+
+    /* Get the start set. */
+    Bindings::iterator startSet =
+        args[0]->attrs->find(state.symbols.create("startSet"));
+    if (startSet == args[0]->attrs->end())
+        throw EvalError("attribute `startSet' required");
+    state.forceList(*startSet->value);
+
+    ValueList workSet;
+    for (unsigned int n = 0; n < startSet->value->list.length; ++n)
+        workSet.push_back(startSet->value->list.elems[n]);
+
+    /* Get the operator. */
+    Bindings::iterator op =
+        args[0]->attrs->find(state.symbols.create("operator"));
+    if (op == args[0]->attrs->end())
+        throw EvalError("attribute `operator' required");
+    state.forceValue(*op->value);
+
+    /* Construct the closure by applying the operator to element of
+       `workSet', adding the result to `workSet', continuing until
+       no new elements are found. */
+    ValueList res;
+    // `doneKeys' doesn't need to be a GC root, because its values are
+    // reachable from res.
+    set<Value *, CompareValues> doneKeys;
+    while (!workSet.empty()) {
+        Value * e = *(workSet.begin());
+        workSet.pop_front();
+
+        state.forceAttrs(*e);
+
+        Bindings::iterator key =
+            e->attrs->find(state.symbols.create("key"));
+        if (key == e->attrs->end())
+            throw EvalError("attribute `key' required");
+        state.forceValue(*key->value);
+
+        if (doneKeys.find(key->value) != doneKeys.end()) continue;
+        doneKeys.insert(key->value);
+        res.push_back(e);
+
+        /* Call the `operator' function with `e' as argument. */
+        Value call;
+        mkApp(call, *op->value, *e);
+        state.forceList(call);
+
+        /* Add the values returned by the operator to the work set. */
+        for (unsigned int n = 0; n < call.list.length; ++n) {
+            state.forceValue(*call.list.elems[n]);
+            workSet.push_back(call.list.elems[n]);
+        }
+    }
+
+    /* Create the result list. */
+    state.mkList(v, res.size());
+    unsigned int n = 0;
+    foreach (ValueList::iterator, i, res)
+        v.list.elems[n++] = *i;
+}
+
+
+static void prim_abort(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    throw Abort(format("evaluation aborted with the following error message: `%1%'") %
+        state.coerceToString(*args[0], context));
+}
+
+
+static void prim_throw(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    throw ThrownError(format("%1%") % state.coerceToString(*args[0], context));
+}
+
+
+static void prim_addErrorContext(EvalState & state, Value * * args, Value & v)
+{
+    try {
+        state.forceValue(*args[1]);
+        v = *args[1];
+    } catch (Error & e) {
+        PathSet context;
+        e.addPrefix(format("%1%\n") % state.coerceToString(*args[0], context));
+        throw;
+    }
+}
+
+
+/* Try evaluating the argument. Success => {success=true; value=something;},
+ * else => {success=false; value=false;} */
+static void prim_tryEval(EvalState & state, Value * * args, Value & v)
+{
+    state.mkAttrs(v, 2);
+    try {
+        state.forceValue(*args[0]);
+        v.attrs->push_back(Attr(state.sValue, args[0]));
+        mkBool(*state.allocAttr(v, state.symbols.create("success")), true);
+    } catch (AssertionError & e) {
+        mkBool(*state.allocAttr(v, state.sValue), false);
+        mkBool(*state.allocAttr(v, state.symbols.create("success")), false);
+    }
+    v.attrs->sort();
+}
+
+
+/* Return an environment variable.  Use with care. */
+static void prim_getEnv(EvalState & state, Value * * args, Value & v)
+{
+    string name = state.forceStringNoCtx(*args[0]);
+    mkString(v, getEnv(name));
+}
+
+
+/* Evaluate the first expression and print it on standard error.  Then
+   return the second expression.  Useful for debugging. */
+static void prim_trace(EvalState & state, Value * * args, Value & v)
+{
+    state.forceValue(*args[0]);
+    if (args[0]->type == tString)
+        printMsg(lvlError, format("trace: %1%") % args[0]->string.s);
+    else
+        printMsg(lvlError, format("trace: %1%") % *args[0]);
+    state.forceValue(*args[1]);
+    v = *args[1];
+}
+
+
+/*************************************************************
+ * Derivations
+ *************************************************************/
+
+
+/* Construct (as a unobservable side effect) a Nix derivation
+   expression that performs the derivation described by the argument
+   set.  Returns the original set extended with the following
+   attributes: `outPath' containing the primary output path of the
+   derivation; `drvPath' containing the path of the Nix expression;
+   and `type' set to `derivation' to indicate that this is a
+   derivation. */
+static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
+{
+    startNest(nest, lvlVomit, "evaluating derivation");
+
+    state.forceAttrs(*args[0]);
+
+    /* Figure out the name first (for stack backtraces). */
+    Bindings::iterator attr = args[0]->attrs->find(state.sName);
+    if (attr == args[0]->attrs->end())
+        throw EvalError("required attribute `name' missing");
+    string drvName;
+    Pos & posDrvName(*attr->pos);
+    try {
+        drvName = state.forceStringNoCtx(*attr->value);
+    } catch (Error & e) {
+        e.addPrefix(format("while evaluating the derivation attribute `name' at %1%:\n") % posDrvName);
+        throw;
+    }
+
+    /* Check whether null attributes should be ignored. */
+    bool ignoreNulls = false;
+    attr = args[0]->attrs->find(state.sIgnoreNulls);
+    if (attr != args[0]->attrs->end())
+        ignoreNulls = state.forceBool(*attr->value);
+
+    /* Build the derivation expression by processing the attributes. */
+    Derivation drv;
+
+    PathSet context;
+
+    string outputHash, outputHashAlgo;
+    bool outputHashRecursive = false;
+
+    StringSet outputs;
+    outputs.insert("out");
+
+    foreach (Bindings::iterator, i, *args[0]->attrs) {
+        if (i->name == state.sIgnoreNulls) continue;
+        string key = i->name;
+        startNest(nest, lvlVomit, format("processing attribute `%1%'") % key);
+
+        try {
+
+            if (ignoreNulls) {
+                state.forceValue(*i->value);
+                if (i->value->type == tNull) continue;
+            }
+
+            /* The `args' attribute is special: it supplies the
+               command-line arguments to the builder. */
+            if (key == "args") {
+                state.forceList(*i->value);
+                for (unsigned int n = 0; n < i->value->list.length; ++n) {
+                    string s = state.coerceToString(*i->value->list.elems[n], context, true);
+                    drv.args.push_back(s);
+                }
+            }
+
+            /* All other attributes are passed to the builder through
+               the environment. */
+            else {
+                string s = state.coerceToString(*i->value, context, true);
+                drv.env[key] = s;
+                if (key == "builder") drv.builder = s;
+                else if (i->name == state.sSystem) drv.platform = s;
+                else if (i->name == state.sName) {
+                    drvName = s;
+                    printMsg(lvlVomit, format("derivation name is `%1%'") % drvName);
+                }
+                else if (key == "outputHash") outputHash = s;
+                else if (key == "outputHashAlgo") outputHashAlgo = s;
+                else if (key == "outputHashMode") {
+                    if (s == "recursive") outputHashRecursive = true;
+                    else if (s == "flat") outputHashRecursive = false;
+                    else throw EvalError(format("invalid value `%1%' for `outputHashMode' attribute") % s);
+                }
+                else if (key == "outputs") {
+                    Strings tmp = tokenizeString<Strings>(s);
+                    outputs.clear();
+                    foreach (Strings::iterator, j, tmp) {
+                        if (outputs.find(*j) != outputs.end())
+                            throw EvalError(format("duplicate derivation output `%1%'") % *j);
+                        /* !!! Check whether *j is a valid attribute
+                           name. */
+                        /* Derivations cannot be named ‘drv’, because
+                           then we'd have an attribute ‘drvPath’ in
+                           the resulting set. */
+                        if (*j == "drv")
+                            throw EvalError(format("invalid derivation output name `drv'") % *j);
+                        outputs.insert(*j);
+                    }
+                    if (outputs.empty())
+                        throw EvalError("derivation cannot have an empty set of outputs");
+                }
+            }
+
+        } catch (Error & e) {
+            e.addPrefix(format("while evaluating the attribute `%1%' of the derivation `%2%' at %3%:\n")
+                % key % drvName % posDrvName);
+            throw;
+        }
+    }
+
+    /* Everything in the context of the strings in the derivation
+       attributes should be added as dependencies of the resulting
+       derivation. */
+    foreach (PathSet::iterator, i, context) {
+        Path path = *i;
+
+        /* Paths marked with `=' denote that the path of a derivation
+           is explicitly passed to the builder.  Since that allows the
+           builder to gain access to every path in the dependency
+           graph of the derivation (including all outputs), all paths
+           in the graph must be added to this derivation's list of
+           inputs to ensure that they are available when the builder
+           runs. */
+        if (path.at(0) == '=') {
+            /* !!! This doesn't work if readOnlyMode is set. */
+            PathSet refs; computeFSClosure(*store, string(path, 1), refs);
+            foreach (PathSet::iterator, j, refs) {
+                drv.inputSrcs.insert(*j);
+                if (isDerivation(*j))
+                    drv.inputDrvs[*j] = store->queryDerivationOutputNames(*j);
+            }
+        }
+
+        /* See prim_unsafeDiscardOutputDependency. */
+        else if (path.at(0) == '~')
+            drv.inputSrcs.insert(string(path, 1));
+
+        /* Handle derivation outputs of the form ‘!<name>!<path>’. */
+        else if (path.at(0) == '!') {
+            std::pair<string, string> ctx = decodeContext(path);
+            drv.inputDrvs[ctx.first].insert(ctx.second);
+        }
+
+        /* Handle derivation contexts returned by
+           ‘builtins.storePath’. */
+        else if (isDerivation(path))
+            drv.inputDrvs[path] = store->queryDerivationOutputNames(path);
+
+        /* Otherwise it's a source file. */
+        else
+            drv.inputSrcs.insert(path);
+    }
+
+    /* Do we have all required attributes? */
+    if (drv.builder == "")
+        throw EvalError("required attribute `builder' missing");
+    if (drv.platform == "")
+        throw EvalError("required attribute `system' missing");
+
+    /* Check whether the derivation name is valid. */
+    checkStoreName(drvName);
+    if (isDerivation(drvName))
+        throw EvalError(format("derivation names are not allowed to end in `%1%'")
+            % drvExtension);
+
+    if (outputHash != "") {
+        /* Handle fixed-output derivations. */
+        if (outputs.size() != 1 || *(outputs.begin()) != "out")
+            throw Error("multiple outputs are not supported in fixed-output derivations");
+
+        HashType ht = parseHashType(outputHashAlgo);
+        if (ht == htUnknown)
+            throw EvalError(format("unknown hash algorithm `%1%'") % outputHashAlgo);
+        Hash h = parseHash16or32(ht, outputHash);
+        outputHash = printHash(h);
+        if (outputHashRecursive) outputHashAlgo = "r:" + outputHashAlgo;
+
+        Path outPath = makeFixedOutputPath(outputHashRecursive, ht, h, drvName);
+        drv.env["out"] = outPath;
+        drv.outputs["out"] = DerivationOutput(outPath, outputHashAlgo, outputHash);
+    }
+
+    else {
+        /* Construct the "masked" store derivation, which is the final
+           one except that in the list of outputs, the output paths
+           are empty, and the corresponding environment variables have
+           an empty value.  This ensures that changes in the set of
+           output names do get reflected in the hash. */
+        foreach (StringSet::iterator, i, outputs) {
+            drv.env[*i] = "";
+            drv.outputs[*i] = DerivationOutput("", "", "");
+        }
+
+        /* Use the masked derivation expression to compute the output
+           path. */
+        Hash h = hashDerivationModulo(*store, drv);
+
+        foreach (DerivationOutputs::iterator, i, drv.outputs)
+            if (i->second.path == "") {
+                Path outPath = makeOutputPath(i->first, h, drvName);
+                drv.env[i->first] = outPath;
+                i->second.path = outPath;
+            }
+    }
+
+    /* Write the resulting term into the Nix store directory. */
+    Path drvPath = writeDerivation(*store, drv, drvName, state.repair);
+
+    printMsg(lvlChatty, format("instantiated `%1%' -> `%2%'")
+        % drvName % drvPath);
+
+    /* Optimisation, but required in read-only mode! because in that
+       case we don't actually write store derivations, so we can't
+       read them later. */
+    drvHashes[drvPath] = hashDerivationModulo(*store, drv);
+
+    state.mkAttrs(v, 1 + drv.outputs.size());
+    mkString(*state.allocAttr(v, state.sDrvPath), drvPath, singleton<PathSet>("=" + drvPath));
+    foreach (DerivationOutputs::iterator, i, drv.outputs) {
+        mkString(*state.allocAttr(v, state.symbols.create(i->first)),
+            i->second.path, singleton<PathSet>("!" + i->first + "!" + drvPath));
+    }
+    v.attrs->sort();
+}
+
+
+/*************************************************************
+ * Paths
+ *************************************************************/
+
+
+/* Convert the argument to a path.  !!! obsolete? */
+static void prim_toPath(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    Path path = state.coerceToPath(*args[0], context);
+    mkString(v, canonPath(path), context);
+}
+
+
+/* Allow a valid store path to be used in an expression.  This is
+   useful in some generated expressions such as in nix-push, which
+   generates a call to a function with an already existing store path
+   as argument.  You don't want to use `toPath' here because it copies
+   the path to the Nix store, which yields a copy like
+   /nix/store/newhash-oldhash-oldname.  In the past, `toPath' had
+   special case behaviour for store paths, but that created weird
+   corner cases. */
+static void prim_storePath(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    Path path = state.coerceToPath(*args[0], context);
+    /* Resolve symlinks in ‘path’, unless ‘path’ itself is a symlink
+       directly in the store.  The latter condition is necessary so
+       e.g. nix-push does the right thing. */
+    if (!isStorePath(path)) path = canonPath(path, true);
+    if (!isInStore(path))
+        throw EvalError(format("path `%1%' is not in the Nix store") % path);
+    Path path2 = toStorePath(path);
+    if (!settings.readOnlyMode)
+        store->ensurePath(path2);
+    context.insert(path2);
+    mkString(v, path, context);
+}
+
+
+static void prim_pathExists(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    Path path = state.coerceToPath(*args[0], context);
+    if (!context.empty())
+        throw EvalError(format("string `%1%' cannot refer to other paths") % path);
+    mkBool(v, pathExists(path));
+}
+
+
+/* Return the base name of the given string, i.e., everything
+   following the last slash. */
+static void prim_baseNameOf(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    mkString(v, baseNameOf(state.coerceToString(*args[0], context)), context);
+}
+
+
+/* Return the directory of the given path, i.e., everything before the
+   last slash.  Return either a path or a string depending on the type
+   of the argument. */
+static void prim_dirOf(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    Path dir = dirOf(state.coerceToPath(*args[0], context));
+    if (args[0]->type == tPath) mkPath(v, dir.c_str()); else mkString(v, dir, context);
+}
+
+
+/* Return the contents of a file as a string. */
+static void prim_readFile(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    Path path = state.coerceToPath(*args[0], context);
+    if (!context.empty())
+        throw EvalError(format("string `%1%' cannot refer to other paths") % path);
+    mkString(v, readFile(path).c_str());
+}
+
+
+/*************************************************************
+ * Creating files
+ *************************************************************/
+
+
+/* Convert the argument (which can be any Nix expression) to an XML
+   representation returned in a string.  Not all Nix expressions can
+   be sensibly or completely represented (e.g., functions). */
+static void prim_toXML(EvalState & state, Value * * args, Value & v)
+{
+    std::ostringstream out;
+    PathSet context;
+    printValueAsXML(state, true, false, *args[0], out, context);
+    mkString(v, out.str(), context);
+}
+
+
+/* Convert the argument (which can be any Nix expression) to a JSON
+   string.  Not all Nix expressions can be sensibly or completely
+   represented (e.g., functions). */
+static void prim_toJSON(EvalState & state, Value * * args, Value & v)
+{
+    std::ostringstream out;
+    PathSet context;
+    printValueAsJSON(state, true, *args[0], out, context);
+    mkString(v, out.str(), context);
+}
+
+
+/* Store a string in the Nix store as a source file that can be used
+   as an input by derivations. */
+static void prim_toFile(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    string name = state.forceStringNoCtx(*args[0]);
+    string contents = state.forceString(*args[1], context);
+
+    PathSet refs;
+
+    foreach (PathSet::iterator, i, context) {
+        Path path = *i;
+        if (path.at(0) == '=') path = string(path, 1);
+        if (isDerivation(path))
+            throw EvalError(format("in `toFile': the file `%1%' cannot refer to derivation outputs") % name);
+        refs.insert(path);
+    }
+
+    Path storePath = settings.readOnlyMode
+        ? computeStorePathForText(name, contents, refs)
+        : store->addTextToStore(name, contents, refs, state.repair);
+
+    /* Note: we don't need to add `context' to the context of the
+       result, since `storePath' itself has references to the paths
+       used in args[1]. */
+
+    mkString(v, storePath, singleton<PathSet>(storePath));
+}
+
+
+struct FilterFromExpr : PathFilter
+{
+    EvalState & state;
+    Value & filter;
+
+    FilterFromExpr(EvalState & state, Value & filter)
+        : state(state), filter(filter)
+    {
+    }
+
+    bool operator () (const Path & path)
+    {
+        struct stat st;
+        if (lstat(path.c_str(), &st))
+            throw SysError(format("getting attributes of path `%1%'") % path);
+
+        /* Call the filter function.  The first argument is the path,
+           the second is a string indicating the type of the file. */
+        Value arg1;
+        mkString(arg1, path);
+
+        Value fun2;
+        state.callFunction(filter, arg1, fun2);
+
+        Value arg2;
+        mkString(arg2,
+            S_ISREG(st.st_mode) ? "regular" :
+            S_ISDIR(st.st_mode) ? "directory" :
+            S_ISLNK(st.st_mode) ? "symlink" :
+            "unknown" /* not supported, will fail! */);
+
+        Value res;
+        state.callFunction(fun2, arg2, res);
+
+        return state.forceBool(res);
+    }
+};
+
+
+static void prim_filterSource(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    Path path = state.coerceToPath(*args[1], context);
+    if (!context.empty())
+        throw EvalError(format("string `%1%' cannot refer to other paths") % path);
+
+    state.forceValue(*args[0]);
+    if (args[0]->type != tLambda)
+        throw TypeError(format("first argument in call to `filterSource' is not a function but %1%") % showType(*args[0]));
+
+    FilterFromExpr filter(state, *args[0]);
+
+    Path dstPath = settings.readOnlyMode
+        ? computeStorePathForPath(path, true, htSHA256, filter).first
+        : store->addToStore(path, true, htSHA256, filter, state.repair);
+
+    mkString(v, dstPath, singleton<PathSet>(dstPath));
+}
+
+
+/*************************************************************
+ * Sets
+ *************************************************************/
+
+
+/* Return the names of the attributes in a set as a sorted list of
+   strings. */
+static void prim_attrNames(EvalState & state, Value * * args, Value & v)
+{
+    state.forceAttrs(*args[0]);
+
+    state.mkList(v, args[0]->attrs->size());
+
+    StringSet names;
+    foreach (Bindings::iterator, i, *args[0]->attrs)
+        names.insert(i->name);
+
+    unsigned int n = 0;
+    foreach (StringSet::iterator, i, names)
+        mkString(*(v.list.elems[n++] = state.allocValue()), *i);
+}
+
+
+/* Dynamic version of the `.' operator. */
+void prim_getAttr(EvalState & state, Value * * args, Value & v)
+{
+    string attr = state.forceStringNoCtx(*args[0]);
+    state.forceAttrs(*args[1]);
+    // !!! Should we create a symbol here or just do a lookup?
+    Bindings::iterator i = args[1]->attrs->find(state.symbols.create(attr));
+    if (i == args[1]->attrs->end())
+        throw EvalError(format("attribute `%1%' missing") % attr);
+    // !!! add to stack trace?
+    if (state.countCalls && i->pos) state.attrSelects[*i->pos]++;
+    state.forceValue(*i->value);
+    v = *i->value;
+}
+
+
+/* Return position information of the specified attribute. */
+void prim_unsafeGetAttrPos(EvalState & state, Value * * args, Value & v)
+{
+    string attr = state.forceStringNoCtx(*args[0]);
+    state.forceAttrs(*args[1]);
+    Bindings::iterator i = args[1]->attrs->find(state.symbols.create(attr));
+    if (i == args[1]->attrs->end())
+        mkNull(v);
+    else
+        state.mkPos(v, i->pos);
+}
+
+
+/* Dynamic version of the `?' operator. */
+static void prim_hasAttr(EvalState & state, Value * * args, Value & v)
+{
+    string attr = state.forceStringNoCtx(*args[0]);
+    state.forceAttrs(*args[1]);
+    mkBool(v, args[1]->attrs->find(state.symbols.create(attr)) != args[1]->attrs->end());
+}
+
+
+/* Determine whether the argument is a set. */
+static void prim_isAttrs(EvalState & state, Value * * args, Value & v)
+{
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tAttrs);
+}
+
+
+static void prim_removeAttrs(EvalState & state, Value * * args, Value & v)
+{
+    state.forceAttrs(*args[0]);
+    state.forceList(*args[1]);
+
+    /* Get the attribute names to be removed. */
+    std::set<Symbol> names;
+    for (unsigned int i = 0; i < args[1]->list.length; ++i) {
+        state.forceStringNoCtx(*args[1]->list.elems[i]);
+        names.insert(state.symbols.create(args[1]->list.elems[i]->string.s));
+    }
+
+    /* Copy all attributes not in that set.  Note that we don't need
+       to sort v.attrs because it's a subset of an already sorted
+       vector. */
+    state.mkAttrs(v, args[0]->attrs->size());
+    foreach (Bindings::iterator, i, *args[0]->attrs) {
+        if (names.find(i->name) == names.end())
+            v.attrs->push_back(*i);
+    }
+}
+
+
+/* Builds a set from a list specifying (name, value) pairs.  To be
+   precise, a list [{name = "name1"; value = value1;} ... {name =
+   "nameN"; value = valueN;}] is transformed to {name1 = value1;
+   ... nameN = valueN;}.  In case of duplicate occurences of the same
+   name, the first takes precedence. */
+static void prim_listToAttrs(EvalState & state, Value * * args, Value & v)
+{
+    state.forceList(*args[0]);
+
+    state.mkAttrs(v, args[0]->list.length);
+
+    std::set<Symbol> seen;
+
+    for (unsigned int i = 0; i < args[0]->list.length; ++i) {
+        Value & v2(*args[0]->list.elems[i]);
+        state.forceAttrs(v2);
+
+        Bindings::iterator j = v2.attrs->find(state.sName);
+        if (j == v2.attrs->end())
+            throw TypeError("`name' attribute missing in a call to `listToAttrs'");
+        string name = state.forceStringNoCtx(*j->value);
+
+        Symbol sym = state.symbols.create(name);
+        if (seen.find(sym) == seen.end()) {
+            Bindings::iterator j2 = v2.attrs->find(state.symbols.create(state.sValue));
+            if (j2 == v2.attrs->end())
+                throw TypeError("`value' attribute missing in a call to `listToAttrs'");
+
+            v.attrs->push_back(Attr(sym, j2->value, j2->pos));
+            seen.insert(sym);
+        }
+    }
+
+    v.attrs->sort();
+}
+
+
+/* Return the right-biased intersection of two sets as1 and as2,
+   i.e. a set that contains every attribute from as2 that is also a
+   member of as1. */
+static void prim_intersectAttrs(EvalState & state, Value * * args, Value & v)
+{
+    state.forceAttrs(*args[0]);
+    state.forceAttrs(*args[1]);
+
+    state.mkAttrs(v, std::min(args[0]->attrs->size(), args[1]->attrs->size()));
+
+    foreach (Bindings::iterator, i, *args[0]->attrs) {
+        Bindings::iterator j = args[1]->attrs->find(i->name);
+        if (j != args[1]->attrs->end())
+            v.attrs->push_back(*j);
+    }
+}
+
+
+/* Return a set containing the names of the formal arguments expected
+   by the function `f'.  The value of each attribute is a Boolean
+   denoting whether has a default value.  For instance,
+
+      functionArgs ({ x, y ? 123}: ...)
+   => { x = false; y = true; }
+
+   "Formal argument" here refers to the attributes pattern-matched by
+   the function.  Plain lambdas are not included, e.g.
+
+      functionArgs (x: ...)
+   => { }
+*/
+static void prim_functionArgs(EvalState & state, Value * * args, Value & v)
+{
+    state.forceValue(*args[0]);
+    if (args[0]->type != tLambda)
+        throw TypeError("`functionArgs' requires a function");
+
+    if (!args[0]->lambda.fun->matchAttrs) {
+        state.mkAttrs(v, 0);
+        return;
+    }
+
+    state.mkAttrs(v, args[0]->lambda.fun->formals->formals.size());
+    foreach (Formals::Formals_::iterator, i, args[0]->lambda.fun->formals->formals)
+        // !!! should optimise booleans (allocate only once)
+        mkBool(*state.allocAttr(v, i->name), i->def);
+    v.attrs->sort();
+}
+
+
+/*************************************************************
+ * Lists
+ *************************************************************/
+
+
+/* Determine whether the argument is a list. */
+static void prim_isList(EvalState & state, Value * * args, Value & v)
+{
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tList);
+}
+
+
+static void elemAt(EvalState & state, Value & list, int n, Value & v)
+{
+    state.forceList(list);
+    if (n < 0 || n >= list.list.length)
+        throw Error(format("list index %1% is out of bounds") % n);
+    state.forceValue(*list.list.elems[n]);
+    v = *list.list.elems[n];
+}
+
+
+/* Return the n-1'th element of a list. */
+static void prim_elemAt(EvalState & state, Value * * args, Value & v)
+{
+    elemAt(state, *args[0], state.forceInt(*args[1]), v);
+}
+
+
+/* Return the first element of a list. */
+static void prim_head(EvalState & state, Value * * args, Value & v)
+{
+    elemAt(state, *args[0], 0, v);
+}
+
+
+/* Return a list consisting of everything but the the first element of
+   a list.  Warning: this function takes O(n) time, so you probably
+   don't want to use it!  */
+static void prim_tail(EvalState & state, Value * * args, Value & v)
+{
+    state.forceList(*args[0]);
+    if (args[0]->list.length == 0)
+        throw Error("`tail' called on an empty list");
+    state.mkList(v, args[0]->list.length - 1);
+    for (unsigned int n = 0; n < v.list.length; ++n)
+        v.list.elems[n] = args[0]->list.elems[n + 1];
+}
+
+
+/* Apply a function to every element of a list. */
+static void prim_map(EvalState & state, Value * * args, Value & v)
+{
+    state.forceFunction(*args[0]);
+    state.forceList(*args[1]);
+
+    state.mkList(v, args[1]->list.length);
+
+    for (unsigned int n = 0; n < v.list.length; ++n)
+        mkApp(*(v.list.elems[n] = state.allocValue()),
+            *args[0], *args[1]->list.elems[n]);
+}
+
+
+/* Filter a list using a predicate; that is, return a list containing
+   every element from the list for which the predicate function
+   returns true. */
+static void prim_filter(EvalState & state, Value * * args, Value & v)
+{
+    state.forceFunction(*args[0]);
+    state.forceList(*args[1]);
+
+    // FIXME: putting this on the stack is risky.
+    Value * vs[args[1]->list.length];
+    unsigned int k = 0;
+
+    bool same = true;
+    for (unsigned int n = 0; n < args[1]->list.length; ++n) {
+        Value res;
+        state.callFunction(*args[0], *args[1]->list.elems[n], res);
+        if (state.forceBool(res))
+            vs[k++] = args[1]->list.elems[n];
+        else
+            same = false;
+    }
+
+    if (same)
+        v = *args[1];
+    else {
+        state.mkList(v, k);
+        for (unsigned int n = 0; n < k; ++n) v.list.elems[n] = vs[n];
+    }
+}
+
+
+/* Return true if a list contains a given element. */
+static void prim_elem(EvalState & state, Value * * args, Value & v)
+{
+    bool res = false;
+    state.forceList(*args[1]);
+    for (unsigned int n = 0; n < args[1]->list.length; ++n)
+        if (state.eqValues(*args[0], *args[1]->list.elems[n])) {
+            res = true;
+            break;
+        }
+    mkBool(v, res);
+}
+
+
+/* Concatenate a list of lists. */
+static void prim_concatLists(EvalState & state, Value * * args, Value & v)
+{
+    state.forceList(*args[0]);
+    state.concatLists(v, args[0]->list.length, args[0]->list.elems);
+}
+
+
+/* Return the length of a list.  This is an O(1) time operation. */
+static void prim_length(EvalState & state, Value * * args, Value & v)
+{
+    state.forceList(*args[0]);
+    mkInt(v, args[0]->list.length);
+}
+
+
+/*************************************************************
+ * Integer arithmetic
+ *************************************************************/
+
+
+static void prim_add(EvalState & state, Value * * args, Value & v)
+{
+    mkInt(v, state.forceInt(*args[0]) + state.forceInt(*args[1]));
+}
+
+
+static void prim_sub(EvalState & state, Value * * args, Value & v)
+{
+    mkInt(v, state.forceInt(*args[0]) - state.forceInt(*args[1]));
+}
+
+
+static void prim_mul(EvalState & state, Value * * args, Value & v)
+{
+    mkInt(v, state.forceInt(*args[0]) * state.forceInt(*args[1]));
+}
+
+
+static void prim_div(EvalState & state, Value * * args, Value & v)
+{
+    NixInt i2 = state.forceInt(*args[1]);
+    if (i2 == 0) throw EvalError("division by zero");
+    mkInt(v, state.forceInt(*args[0]) / i2);
+}
+
+
+static void prim_lessThan(EvalState & state, Value * * args, Value & v)
+{
+    state.forceValue(*args[0]);
+    state.forceValue(*args[1]);
+    CompareValues comp;
+    mkBool(v, comp(args[0], args[1]));
+}
+
+
+/*************************************************************
+ * String manipulation
+ *************************************************************/
+
+
+/* Convert the argument to a string.  Paths are *not* copied to the
+   store, so `toString /foo/bar' yields `"/foo/bar"', not
+   `"/nix/store/whatever..."'. */
+static void prim_toString(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    string s = state.coerceToString(*args[0], context, true, false);
+    mkString(v, s, context);
+}
+
+
+/* `substring start len str' returns the substring of `str' starting
+   at character position `min(start, stringLength str)' inclusive and
+   ending at `min(start + len, stringLength str)'.  `start' must be
+   non-negative. */
+static void prim_substring(EvalState & state, Value * * args, Value & v)
+{
+    int start = state.forceInt(*args[0]);
+    int len = state.forceInt(*args[1]);
+    PathSet context;
+    string s = state.coerceToString(*args[2], context);
+
+    if (start < 0) throw EvalError("negative start position in `substring'");
+
+    mkString(v, start >= s.size() ? "" : string(s, start, len), context);
+}
+
+
+static void prim_stringLength(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    string s = state.coerceToString(*args[0], context);
+    mkInt(v, s.size());
+}
+
+
+static void prim_unsafeDiscardStringContext(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    string s = state.coerceToString(*args[0], context);
+    mkString(v, s, PathSet());
+}
+
+
+/* Sometimes we want to pass a derivation path (i.e. pkg.drvPath) to a
+   builder without causing the derivation to be built (for instance,
+   in the derivation that builds NARs in nix-push, when doing
+   source-only deployment).  This primop marks the string context so
+   that builtins.derivation adds the path to drv.inputSrcs rather than
+   drv.inputDrvs. */
+static void prim_unsafeDiscardOutputDependency(EvalState & state, Value * * args, Value & v)
+{
+    PathSet context;
+    string s = state.coerceToString(*args[0], context);
+
+    PathSet context2;
+    foreach (PathSet::iterator, i, context) {
+        Path p = *i;
+        if (p.at(0) == '=') p = "~" + string(p, 1);
+        context2.insert(p);
+    }
+
+    mkString(v, s, context2);
+}
+
+
+/* Return the cryptographic hash of a string in base-16. */
+static void prim_hashString(EvalState & state, Value * * args, Value & v)
+{
+    string type = state.forceStringNoCtx(*args[0]);
+    HashType ht = parseHashType(type);
+    if (ht == htUnknown)
+      throw Error(format("unknown hash type `%1%'") % type);
+
+    PathSet context; // discarded
+    string s = state.forceString(*args[1], context);
+
+    mkString(v, printHash(hashString(ht, s)), context);
+};
+
+
+/*************************************************************
+ * Versions
+ *************************************************************/
+
+
+static void prim_parseDrvName(EvalState & state, Value * * args, Value & v)
+{
+    string name = state.forceStringNoCtx(*args[0]);
+    DrvName parsed(name);
+    state.mkAttrs(v, 2);
+    mkString(*state.allocAttr(v, state.sName), parsed.name);
+    mkString(*state.allocAttr(v, state.symbols.create("version")), parsed.version);
+    v.attrs->sort();
+}
+
+
+static void prim_compareVersions(EvalState & state, Value * * args, Value & v)
+{
+    string version1 = state.forceStringNoCtx(*args[0]);
+    string version2 = state.forceStringNoCtx(*args[1]);
+    mkInt(v, compareVersions(version1, version2));
+}
+
+
+/*************************************************************
+ * Primop registration
+ *************************************************************/
+
+
+void EvalState::createBaseEnv()
+{
+    baseEnv.up = 0;
+
+    /* Add global constants such as `true' to the base environment. */
+    Value v;
+
+    /* `builtins' must be first! */
+    mkAttrs(v, 128);
+    addConstant("builtins", v);
+
+    mkBool(v, true);
+    addConstant("true", v);
+
+    mkBool(v, false);
+    addConstant("false", v);
+
+    mkNull(v);
+    addConstant("null", v);
+
+    mkInt(v, time(0));
+    addConstant("__currentTime", v);
+
+    mkString(v, settings.thisSystem.c_str());
+    addConstant("__currentSystem", v);
+
+    mkString(v, nixVersion.c_str());
+    addConstant("__nixVersion", v);
+
+    /* Language version.  This should be increased every time a new
+       language feature gets added.  It's not necessary to increase it
+       when primops get added, because you can just use `builtins ?
+       primOp' to check. */
+    mkInt(v, 2);
+    addConstant("__langVersion", v);
+
+    // Miscellaneous
+    addPrimOp("import", 1, prim_import);
+    addPrimOp("__typeOf", 1, prim_typeOf);
+    addPrimOp("isNull", 1, prim_isNull);
+    addPrimOp("__isFunction", 1, prim_isFunction);
+    addPrimOp("__isString", 1, prim_isString);
+    addPrimOp("__isInt", 1, prim_isInt);
+    addPrimOp("__isBool", 1, prim_isBool);
+    addPrimOp("__genericClosure", 1, prim_genericClosure);
+    addPrimOp("abort", 1, prim_abort);
+    addPrimOp("throw", 1, prim_throw);
+    addPrimOp("__addErrorContext", 2, prim_addErrorContext);
+    addPrimOp("__tryEval", 1, prim_tryEval);
+    addPrimOp("__getEnv", 1, prim_getEnv);
+    addPrimOp("__trace", 2, prim_trace);
+
+    // Paths
+    addPrimOp("__toPath", 1, prim_toPath);
+    addPrimOp("__storePath", 1, prim_storePath);
+    addPrimOp("__pathExists", 1, prim_pathExists);
+    addPrimOp("baseNameOf", 1, prim_baseNameOf);
+    addPrimOp("dirOf", 1, prim_dirOf);
+    addPrimOp("__readFile", 1, prim_readFile);
+
+    // Creating files
+    addPrimOp("__toXML", 1, prim_toXML);
+    addPrimOp("__toJSON", 1, prim_toJSON);
+    addPrimOp("__toFile", 2, prim_toFile);
+    addPrimOp("__filterSource", 2, prim_filterSource);
+
+    // Sets
+    addPrimOp("__attrNames", 1, prim_attrNames);
+    addPrimOp("__getAttr", 2, prim_getAttr);
+    addPrimOp("__unsafeGetAttrPos", 2, prim_unsafeGetAttrPos);
+    addPrimOp("__hasAttr", 2, prim_hasAttr);
+    addPrimOp("__isAttrs", 1, prim_isAttrs);
+    addPrimOp("removeAttrs", 2, prim_removeAttrs);
+    addPrimOp("__listToAttrs", 1, prim_listToAttrs);
+    addPrimOp("__intersectAttrs", 2, prim_intersectAttrs);
+    addPrimOp("__functionArgs", 1, prim_functionArgs);
+
+    // Lists
+    addPrimOp("__isList", 1, prim_isList);
+    addPrimOp("__elemAt", 2, prim_elemAt);
+    addPrimOp("__head", 1, prim_head);
+    addPrimOp("__tail", 1, prim_tail);
+    addPrimOp("map", 2, prim_map);
+    addPrimOp("__filter", 2, prim_filter);
+    addPrimOp("__elem", 2, prim_elem);
+    addPrimOp("__concatLists", 1, prim_concatLists);
+    addPrimOp("__length", 1, prim_length);
+
+    // Integer arithmetic
+    addPrimOp("__add", 2, prim_add);
+    addPrimOp("__sub", 2, prim_sub);
+    addPrimOp("__mul", 2, prim_mul);
+    addPrimOp("__div", 2, prim_div);
+    addPrimOp("__lessThan", 2, prim_lessThan);
+
+    // String manipulation
+    addPrimOp("toString", 1, prim_toString);
+    addPrimOp("__substring", 3, prim_substring);
+    addPrimOp("__stringLength", 1, prim_stringLength);
+    addPrimOp("__unsafeDiscardStringContext", 1, prim_unsafeDiscardStringContext);
+    addPrimOp("__unsafeDiscardOutputDependency", 1, prim_unsafeDiscardOutputDependency);
+    addPrimOp("__hashString", 2, prim_hashString);
+
+    // Versions
+    addPrimOp("__parseDrvName", 1, prim_parseDrvName);
+    addPrimOp("__compareVersions", 2, prim_compareVersions);
+
+    // Derivations
+    addPrimOp("derivationStrict", 1, prim_derivationStrict);
+
+    /* Add a wrapper around the derivation primop that computes the
+       `drvPath' and `outPath' attributes lazily. */
+    string path = findFile("nix/derivation.nix");
+    assert(!path.empty());
+    sDerivationNix = symbols.create(path);
+    evalFile(path, v);
+    addConstant("derivation", v);
+
+    /* Now that we've added all primops, sort the `builtins' set,
+       because attribute lookups expect it to be sorted. */
+    baseEnv.values[0]->attrs->sort();
+}
+
+
+}
diff --git a/src/libexpr/symbol-table.hh b/src/libexpr/symbol-table.hh
new file mode 100644
index 000000000000..08e31d496585
--- /dev/null
+++ b/src/libexpr/symbol-table.hh
@@ -0,0 +1,95 @@
+#pragma once
+
+#include "config.h"
+
+#include <map>
+
+#if HAVE_TR1_UNORDERED_SET
+#include <tr1/unordered_set>
+#endif
+
+#include "types.hh"
+
+namespace nix {
+
+/* Symbol table used by the parser and evaluator to represent and look
+   up identifiers and attributes efficiently.  SymbolTable::create()
+   converts a string into a symbol.  Symbols have the property that
+   they can be compared efficiently (using a pointer equality test),
+   because the symbol table stores only one copy of each string. */
+
+class Symbol
+{
+private:
+    const string * s; // pointer into SymbolTable
+    Symbol(const string * s) : s(s) { };
+    friend class SymbolTable;
+
+public:
+    Symbol() : s(0) { };
+
+    bool operator == (const Symbol & s2) const
+    {
+        return s == s2.s;
+    }
+
+    bool operator != (const Symbol & s2) const
+    {
+        return s != s2.s;
+    }
+
+    bool operator < (const Symbol & s2) const
+    {
+        return s < s2.s;
+    }
+
+    operator const string & () const
+    {
+        return *s;
+    }
+
+    bool set() const
+    {
+        return s;
+    }
+
+    bool empty() const
+    {
+        return s->empty();
+    }
+
+    friend std::ostream & operator << (std::ostream & str, const Symbol & sym);
+};
+
+inline std::ostream & operator << (std::ostream & str, const Symbol & sym)
+{
+    str << *sym.s;
+    return str;
+}
+
+class SymbolTable
+{
+private:
+#if HAVE_TR1_UNORDERED_SET
+    typedef std::tr1::unordered_set<string> Symbols;
+#else
+    typedef std::set<string> Symbols;
+#endif
+    Symbols symbols;
+
+public:
+    Symbol create(const string & s)
+    {
+        std::pair<Symbols::iterator, bool> res = symbols.insert(s);
+        return Symbol(&*res.first);
+    }
+
+    unsigned int size() const
+    {
+        return symbols.size();
+    }
+
+    size_t totalSize() const;
+};
+
+}
diff --git a/src/libexpr/value-to-json.cc b/src/libexpr/value-to-json.cc
new file mode 100644
index 000000000000..a2004df5c8c5
--- /dev/null
+++ b/src/libexpr/value-to-json.cc
@@ -0,0 +1,86 @@
+#include "value-to-json.hh"
+#include "eval-inline.hh"
+#include "util.hh"
+
+#include <cstdlib>
+
+
+namespace nix {
+
+
+void escapeJSON(std::ostream & str, const string & s)
+{
+    str << "\"";
+    foreach (string::const_iterator, i, s)
+        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 << "\"";
+}
+
+
+void printValueAsJSON(EvalState & state, bool strict,
+    Value & v, std::ostream & str, PathSet & context)
+{
+    checkInterrupt();
+
+    if (strict) state.forceValue(v);
+
+    switch (v.type) {
+
+        case tInt:
+            str << v.integer;
+            break;
+
+        case tBool:
+            str << (v.boolean ? "true" : "false");
+            break;
+
+        case tString:
+            copyContext(v, context);
+            escapeJSON(str, v.string.s);
+            break;
+
+        case tPath:
+            escapeJSON(str, state.copyPathToStore(context, v.path));
+            break;
+
+        case tNull:
+            str << "null";
+            break;
+
+        case tAttrs: {
+            Bindings::iterator i = v.attrs->find(state.sOutPath);
+            if (i == v.attrs->end()) {
+                JSONObject json(str);
+                StringSet names;
+                foreach (Bindings::iterator, i, *v.attrs)
+                    names.insert(i->name);
+                foreach (StringSet::iterator, i, names) {
+                    Attr & a(*v.attrs->find(state.symbols.create(*i)));
+                    json.attr(*i);
+                    printValueAsJSON(state, strict, *a.value, str, context);
+                }
+            } else
+                printValueAsJSON(state, strict, *i->value, str, context);
+            break;
+        }
+
+        case tList: {
+            JSONList json(str);
+            for (unsigned int n = 0; n < v.list.length; ++n) {
+                json.elem();
+                printValueAsJSON(state, strict, *v.list.elems[n], str, context);
+            }
+            break;
+        }
+
+        default:
+            throw TypeError(format("cannot convert %1% to JSON") % showType(v));
+    }
+}
+
+
+}
diff --git a/src/libexpr/value-to-json.hh b/src/libexpr/value-to-json.hh
new file mode 100644
index 000000000000..e3a97efe4269
--- /dev/null
+++ b/src/libexpr/value-to-json.hh
@@ -0,0 +1,64 @@
+#pragma once
+
+#include "nixexpr.hh"
+#include "eval.hh"
+
+#include <string>
+#include <map>
+
+namespace nix {
+
+void printValueAsJSON(EvalState & state, bool strict,
+    Value & v, std::ostream & out, PathSet & context);
+
+void escapeJSON(std::ostream & str, const string & s);
+
+struct JSONObject
+{
+    std::ostream & str;
+    bool first;
+    JSONObject(std::ostream & str) : str(str), first(true)
+    {
+        str << "{";
+    }
+    ~JSONObject()
+    {
+        str << "}";
+    }
+    void attr(const string & s)
+    {
+        if (!first) str << ","; else first = false;
+        escapeJSON(str, s);
+        str << ":";
+    }
+    void attr(const string & s, const string & t)
+    {
+        attr(s);
+        escapeJSON(str, t);
+    }
+};
+
+struct JSONList
+{
+    std::ostream & str;
+    bool first;
+    JSONList(std::ostream & str) : str(str), first(true)
+    {
+        str << "[";
+    }
+    ~JSONList()
+    {
+        str << "]";
+    }
+    void elem()
+    {
+        if (!first) str << ","; else first = false;
+    }
+    void elem(const string & s)
+    {
+        elem();
+        escapeJSON(str, s);
+    }
+};
+
+}
diff --git a/src/libexpr/value-to-xml.cc b/src/libexpr/value-to-xml.cc
new file mode 100644
index 000000000000..3934a83eec25
--- /dev/null
+++ b/src/libexpr/value-to-xml.cc
@@ -0,0 +1,163 @@
+#include "value-to-xml.hh"
+#include "xml-writer.hh"
+#include "eval-inline.hh"
+#include "util.hh"
+
+#include <cstdlib>
+
+
+namespace nix {
+
+    
+static XMLAttrs singletonAttrs(const string & name, const string & value)
+{
+    XMLAttrs attrs;
+    attrs[name] = value;
+    return attrs;
+}
+
+
+static void printValueAsXML(EvalState & state, bool strict, bool location,
+    Value & v, XMLWriter & doc, PathSet & context, PathSet & drvsSeen);
+
+
+static void posToXML(XMLAttrs & xmlAttrs, const Pos & pos)
+{
+    xmlAttrs["path"] = pos.file;
+    xmlAttrs["line"] = (format("%1%") % pos.line).str();
+    xmlAttrs["column"] = (format("%1%") % pos.column).str();
+}
+
+
+static void showAttrs(EvalState & state, bool strict, bool location,
+    Bindings & attrs, XMLWriter & doc, PathSet & context, PathSet & drvsSeen)
+{
+    StringSet names;
+    
+    foreach (Bindings::iterator, i, attrs)
+        names.insert(i->name);
+    
+    foreach (StringSet::iterator, i, names) {
+        Attr & a(*attrs.find(state.symbols.create(*i)));
+        
+        XMLAttrs xmlAttrs;
+        xmlAttrs["name"] = *i;
+        if (location && a.pos != &noPos) posToXML(xmlAttrs, *a.pos);
+        
+        XMLOpenElement _(doc, "attr", xmlAttrs);
+        printValueAsXML(state, strict, location,
+            *a.value, doc, context, drvsSeen);
+    }
+}
+
+
+static void printValueAsXML(EvalState & state, bool strict, bool location,
+    Value & v, XMLWriter & doc, PathSet & context, PathSet & drvsSeen)
+{
+    checkInterrupt();
+
+    if (strict) state.forceValue(v);
+        
+    switch (v.type) {
+
+        case tInt:
+            doc.writeEmptyElement("int", singletonAttrs("value", (format("%1%") % v.integer).str()));
+            break;
+
+        case tBool:
+            doc.writeEmptyElement("bool", singletonAttrs("value", v.boolean ? "true" : "false"));
+            break;
+
+        case tString:
+            /* !!! show the context? */
+            copyContext(v, context);
+            doc.writeEmptyElement("string", singletonAttrs("value", v.string.s));
+            break;
+
+        case tPath:
+            doc.writeEmptyElement("path", singletonAttrs("value", v.path));
+            break;
+
+        case tNull:
+            doc.writeEmptyElement("null");
+            break;
+
+        case tAttrs:
+            if (state.isDerivation(v)) {
+                XMLAttrs xmlAttrs;
+            
+                Bindings::iterator a = v.attrs->find(state.symbols.create("derivation"));
+
+                Path drvPath;
+                a = v.attrs->find(state.sDrvPath);
+                if (a != v.attrs->end()) {
+                    if (strict) state.forceValue(*a->value);
+                    if (a->value->type == tString)
+                        xmlAttrs["drvPath"] = drvPath = a->value->string.s;
+                }
+        
+                a = v.attrs->find(state.sOutPath);
+                if (a != v.attrs->end()) {
+                    if (strict) state.forceValue(*a->value);
+                    if (a->value->type == tString)
+                        xmlAttrs["outPath"] = a->value->string.s;
+                }
+
+                XMLOpenElement _(doc, "derivation", xmlAttrs);
+
+                if (drvPath != "" && drvsSeen.find(drvPath) == drvsSeen.end()) {
+                    drvsSeen.insert(drvPath);
+                    showAttrs(state, strict, location, *v.attrs, doc, context, drvsSeen);
+                } else
+                    doc.writeEmptyElement("repeated");
+            }
+
+            else {
+                XMLOpenElement _(doc, "attrs");
+                showAttrs(state, strict, location, *v.attrs, doc, context, drvsSeen);
+            }
+            
+            break;
+
+        case tList: {
+            XMLOpenElement _(doc, "list");
+            for (unsigned int n = 0; n < v.list.length; ++n)
+                printValueAsXML(state, strict, location, *v.list.elems[n], doc, context, drvsSeen);
+            break;
+        }
+
+        case tLambda: {
+            XMLAttrs xmlAttrs;
+            if (location) posToXML(xmlAttrs, v.lambda.fun->pos);
+            XMLOpenElement _(doc, "function", xmlAttrs);
+            
+            if (v.lambda.fun->matchAttrs) {
+                XMLAttrs attrs;
+                if (!v.lambda.fun->arg.empty()) attrs["name"] = v.lambda.fun->arg;
+                if (v.lambda.fun->formals->ellipsis) attrs["ellipsis"] = "1";
+                XMLOpenElement _(doc, "attrspat", attrs);
+                foreach (Formals::Formals_::iterator, i, v.lambda.fun->formals->formals)
+                    doc.writeEmptyElement("attr", singletonAttrs("name", i->name));
+            } else
+                doc.writeEmptyElement("varpat", singletonAttrs("name", v.lambda.fun->arg));
+            
+            break;
+        }
+
+        default:
+            doc.writeEmptyElement("unevaluated");
+    }
+}
+
+
+void printValueAsXML(EvalState & state, bool strict, bool location,
+    Value & v, std::ostream & out, PathSet & context)
+{
+    XMLWriter doc(true, out);
+    XMLOpenElement root(doc, "expr");
+    PathSet drvsSeen;    
+    printValueAsXML(state, strict, location, v, doc, context, drvsSeen);
+}
+
+ 
+}
diff --git a/src/libexpr/value-to-xml.hh b/src/libexpr/value-to-xml.hh
new file mode 100644
index 000000000000..97657327edba
--- /dev/null
+++ b/src/libexpr/value-to-xml.hh
@@ -0,0 +1,14 @@
+#pragma once
+
+#include "nixexpr.hh"
+#include "eval.hh"
+
+#include <string>
+#include <map>
+
+namespace nix {
+
+void printValueAsXML(EvalState & state, bool strict, bool location,
+    Value & v, std::ostream & out, PathSet & context);
+    
+}
diff --git a/src/libexpr/value.hh b/src/libexpr/value.hh
new file mode 100644
index 000000000000..2feb2f9492ca
--- /dev/null
+++ b/src/libexpr/value.hh
@@ -0,0 +1,162 @@
+#pragma once
+
+#include "symbol-table.hh"
+
+namespace nix {
+
+
+typedef enum {
+    tInt = 1,
+    tBool,
+    tString,
+    tPath,
+    tNull,
+    tAttrs,
+    tList,
+    tThunk,
+    tApp,
+    tLambda,
+    tBlackhole,
+    tPrimOp,
+    tPrimOpApp,
+} ValueType;
+
+
+class Bindings;
+struct Env;
+struct Expr;
+struct ExprLambda;
+struct PrimOp;
+struct PrimOp;
+class Symbol;
+
+
+typedef long NixInt;
+
+
+struct Value
+{
+    ValueType type;
+    union
+    {
+        NixInt integer;
+        bool boolean;
+
+        /* Strings in the evaluator carry a so-called `context' which
+           is a list of strings representing store paths.  This is to
+           allow users to write things like
+
+             "--with-freetype2-library=" + freetype + "/lib"
+
+           where `freetype' is a derivation (or a source to be copied
+           to the store).  If we just concatenated the strings without
+           keeping track of the referenced store paths, then if the
+           string is used as a derivation attribute, the derivation
+           will not have the correct dependencies in its inputDrvs and
+           inputSrcs.
+
+           The semantics of the context is as follows: when a string
+           with context C is used as a derivation attribute, then the
+           derivations in C will be added to the inputDrvs of the
+           derivation, and the other store paths in C will be added to
+           the inputSrcs of the derivations.
+
+           For canonicity, the store paths should be in sorted order. */
+        struct {
+            const char * s;
+            const char * * context; // must be in sorted order
+        } string;
+
+        const char * path;
+        Bindings * attrs;
+        struct {
+            unsigned int length;
+            Value * * elems;
+        } list;
+        struct {
+            Env * env;
+            Expr * expr;
+        } thunk;
+        struct {
+            Value * left, * right;
+        } app;
+        struct {
+            Env * env;
+            ExprLambda * fun;
+        } lambda;
+        PrimOp * primOp;
+        struct {
+            Value * left, * right;
+        } primOpApp;
+    };
+};
+
+
+/* After overwriting an app node, be sure to clear pointers in the
+   Value to ensure that the target isn't kept alive unnecessarily. */
+static inline void clearValue(Value & v)
+{
+    v.app.right = 0;
+}
+
+
+static inline void mkInt(Value & v, NixInt n)
+{
+    clearValue(v);
+    v.type = tInt;
+    v.integer = n;
+}
+
+
+static inline void mkBool(Value & v, bool b)
+{
+    clearValue(v);
+    v.type = tBool;
+    v.boolean = b;
+}
+
+
+static inline void mkNull(Value & v)
+{
+    v.type = tNull;
+    v.app.left = v.app.right = 00; // scrub
+}
+
+
+static inline void mkApp(Value & v, Value & left, Value & right)
+{
+    v.type = tApp;
+    v.app.left = &left;
+    v.app.right = &right;
+}
+
+
+static inline void mkStringNoCopy(Value & v, const char * s)
+{
+    v.type = tString;
+    v.string.s = s;
+    v.string.context = 0;
+}
+
+
+static inline void mkString(Value & v, const Symbol & s)
+{
+    mkStringNoCopy(v, ((const string &) s).c_str());
+}
+
+
+void mkString(Value & v, const char * s);
+
+
+static inline void mkPathNoCopy(Value & v, const char * s)
+{
+    clearValue(v);
+    v.type = tPath;
+    v.path = s;
+}
+
+
+void mkPath(Value & v, const char * s);
+
+
+}