20 files changed, 2285 insertions, 0 deletions

diff --git a/src/libstore/Makefile.am b/src/libstore/Makefile.am
new file mode 100644
index 000000000000..472b1b079313
--- /dev/null
+++ b/src/libstore/Makefile.am
@@ -0,0 +1,17 @@
+noinst_LIBRARIES = libstore.a
+
+libstore_a_SOURCES = \
+ store.cc expr.cc normalise.cc exec.cc \
+ globals.cc db.cc references.cc pathlocks.cc
+
+AM_CXXFLAGS = -DSYSTEM=\"@host@\" -Wall \
+ -I.. -I../../externals/inst/include -I../libutil
+
+EXTRA_DIST = *.hh *.h test-builder-*.sh
+
+check_PROGRAMS = test-aterm
+
+test_aterm_SOURCES = test-aterm.cc
+test_aterm_LDADD = libstore.a $(LDADD) ../boost/format/libformat.a \
+ -L../../externals/inst/lib -ldb_cxx -lATerm
+
diff --git a/src/libstore/db.cc b/src/libstore/db.cc
new file mode 100644
index 000000000000..63ec2724fcb3
--- /dev/null
+++ b/src/libstore/db.cc
@@ -0,0 +1,425 @@
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+
+#include <memory>
+
+#include "db.hh"
+#include "util.hh"
+#include "pathlocks.hh"
+
+
+/* Wrapper class to ensure proper destruction. */
+class DestroyDbc 
+{
+    Dbc * dbc;
+public:
+    DestroyDbc(Dbc * _dbc) : dbc(_dbc) { }
+    ~DestroyDbc() { dbc->close(); /* close() frees dbc */ }
+};
+
+
+static void rethrow(DbException & e)
+{
+    throw Error(e.what());
+}
+
+
+Transaction::Transaction()
+    : txn(0)
+{
+}
+
+
+Transaction::Transaction(Database & db)
+{
+    db.requireEnv();
+    try {
+        db.env->txn_begin(0, &txn, 0);
+    } catch (DbException e) { rethrow(e); }
+}
+
+
+Transaction::~Transaction()
+{
+    if (txn) abort();
+}
+
+
+void Transaction::commit()
+{
+    if (!txn) throw Error("commit called on null transaction");
+    debug(format("committing transaction %1%") % (void *) txn);
+    DbTxn * txn2 = txn;
+    txn = 0;
+    try {
+        txn2->commit(0);
+    } catch (DbException e) { rethrow(e); }
+}
+
+
+void Transaction::abort()
+{
+    if (!txn) throw Error("abort called on null transaction");
+    debug(format("aborting transaction %1%") % (void *) txn);
+    DbTxn * txn2 = txn;
+    txn = 0;
+    try {
+        txn2->abort();
+    } catch (DbException e) { rethrow(e); }
+}
+
+
+void Transaction::moveTo(Transaction & t)
+{
+    if (t.txn) throw Error("target txn already exists");
+    t.txn = txn;
+    txn = 0;
+}
+
+
+void Database::requireEnv()
+{
+    if (!env) throw Error("database environment not open");
+}
+
+
+Db * Database::getDb(TableId table)
+{
+    map<TableId, Db *>::iterator i = tables.find(table);
+    if (i == tables.end())
+        throw Error("unknown table id");
+    return i->second;
+}
+
+
+Database::Database()
+    : env(0)
+    , nextId(1)
+{
+}
+
+
+Database::~Database()
+{
+    close();
+}
+
+
+int getAccessorCount(int fd)
+{
+    if (lseek(fd, 0, SEEK_SET) == -1)
+        throw SysError("seeking accessor count");
+    char buf[128];
+    int len;
+    if ((len = read(fd, buf, sizeof(buf) - 1)) == -1)
+        throw SysError("reading accessor count");
+    buf[len] = 0;
+    int count;
+    if (sscanf(buf, "%d", &count) != 1) {
+        debug(format("accessor count is invalid: `%1%'") % buf);
+        return -1;
+    }
+    return count;
+}
+
+
+void setAccessorCount(int fd, int n)
+{
+    if (lseek(fd, 0, SEEK_SET) == -1)
+        throw SysError("seeking accessor count");
+    string s = (format("%1%") % n).str();
+    const char * s2 = s.c_str();
+    if (write(fd, s2, strlen(s2)) != (ssize_t) strlen(s2) ||
+        ftruncate(fd, strlen(s2)) != 0)
+        throw SysError("writing accessor count");
+}
+
+
+void openEnv(DbEnv * env, const string & path, u_int32_t flags)
+{
+    env->open(path.c_str(),
+        DB_INIT_LOCK | DB_INIT_LOG | DB_INIT_MPOOL | DB_INIT_TXN |
+        DB_CREATE | flags,
+        0666);
+}
+
+
+void Database::open(const string & path)
+{
+    if (env) throw Error(format("environment already open"));
+
+    try {
+
+        debug(format("opening database environment"));
+
+
+        /* Create the database environment object. */
+        env = new DbEnv(0);
+
+        env->set_lg_bsize(32 * 1024); /* default */
+        env->set_lg_max(256 * 1024); /* must be > 4 * lg_bsize */
+        env->set_lk_detect(DB_LOCK_DEFAULT);
+        env->set_flags(DB_TXN_WRITE_NOSYNC, 1);
+        
+
+        /* The following code provides automatic recovery of the
+           database environment.  Recovery is necessary when a process
+           dies while it has the database open.  To detect this,
+           processes atomically increment a counter when the open the
+           database, and decrement it when they close it.  If we see
+           that counter is > 0 but no processes are accessing the
+           database---determined by attempting to obtain a write lock
+           on a lock file on which all accessors have a read lock---we
+           must run recovery.  Note that this also ensures that we
+           only run recovery when there are no other accessors (which
+           could cause database corruption). */
+
+        /* !!! close fdAccessors / fdLock on exception */
+
+        /* Open the accessor count file. */
+        string accessorsPath = path + "/accessor_count";
+        fdAccessors = ::open(accessorsPath.c_str(), O_RDWR | O_CREAT, 0666);
+        if (fdAccessors == -1)
+            throw SysError(format("opening file `%1%'") % accessorsPath);
+
+        /* Open the lock file. */
+        string lockPath = path + "/access_lock";
+        fdLock = ::open(lockPath.c_str(), O_RDWR | O_CREAT, 0666);
+        if (fdLock == -1)
+            throw SysError(format("opening lock file `%1%'") % lockPath);
+
+        /* Try to acquire a write lock. */
+        debug(format("attempting write lock on `%1%'") % lockPath);
+        if (lockFile(fdLock, ltWrite, false)) { /* don't wait */
+
+            debug(format("write lock granted"));
+
+            /* We have a write lock, which means that there are no
+               other readers or writers. */
+
+            int n = getAccessorCount(fdAccessors);
+                setAccessorCount(fdAccessors, 1);
+
+            if (n != 0) {
+                printMsg(lvlTalkative,
+                    format("accessor count is %1%, running recovery") % n);
+
+                /* Open the environment after running recovery. */
+                openEnv(env, path, DB_RECOVER);
+            }
+            
+            else 
+                /* Open the environment normally. */
+                openEnv(env, path, 0);
+
+            /* Downgrade to a read lock. */
+            debug(format("downgrading to read lock on `%1%'") % lockPath);
+            lockFile(fdLock, ltRead, true);
+
+        } else {
+            /* There are other accessors. */ 
+            debug(format("write lock refused"));
+
+            /* Acquire a read lock. */
+            debug(format("acquiring read lock on `%1%'") % lockPath);
+            lockFile(fdLock, ltRead, true); /* wait indefinitely */
+
+            /* Increment the accessor count. */
+            lockFile(fdAccessors, ltWrite, true);
+            int n = getAccessorCount(fdAccessors) + 1;
+            setAccessorCount(fdAccessors, n);
+            debug(format("incremented accessor count to %1%") % n);
+            lockFile(fdAccessors, ltNone, true);
+
+            /* Open the environment normally. */
+            openEnv(env, path, 0);
+        }
+
+    } catch (DbException e) { rethrow(e); }
+}
+
+
+void Database::close()
+{
+    if (!env) return;
+
+    /* Close the database environment. */
+    debug(format("closing database environment"));
+
+    try {
+
+        for (map<TableId, Db *>::iterator i = tables.begin();
+             i != tables.end(); i++)
+        {
+            Db * db = i->second;
+            db->close(DB_NOSYNC);
+            delete db;
+        }
+
+//         env->txn_checkpoint(0, 0, 0);
+        env->close(0);
+
+    } catch (DbException e) { rethrow(e); }
+
+    delete env;
+
+    /* Decrement the accessor count. */
+    lockFile(fdAccessors, ltWrite, true);
+    int n = getAccessorCount(fdAccessors) - 1;
+    setAccessorCount(fdAccessors, n);
+    debug(format("decremented accessor count to %1%") % n);
+    lockFile(fdAccessors, ltNone, true);
+
+    ::close(fdAccessors);
+    ::close(fdLock);
+}
+
+
+TableId Database::openTable(const string & tableName)
+{
+    requireEnv();
+    TableId table = nextId++;
+
+    try {
+
+        Db * db = new Db(env, 0);
+
+        try {
+            db->open(0, tableName.c_str(), 0, 
+                DB_HASH, DB_CREATE | DB_AUTO_COMMIT, 0666);
+        } catch (...) {
+            delete db;
+            throw;
+        }
+
+        tables[table] = db;
+
+    } catch (DbException e) { rethrow(e); }
+
+    return table;
+}
+
+
+bool Database::queryString(const Transaction & txn, TableId table, 
+    const string & key, string & data)
+{
+    try {
+        Db * db = getDb(table);
+
+        Dbt kt((void *) key.c_str(), key.length());
+        Dbt dt;
+
+        int err = db->get(txn.txn, &kt, &dt, 0);
+        if (err) return false;
+
+        if (!dt.get_data())
+            data = "";
+        else
+            data = string((char *) dt.get_data(), dt.get_size());
+    
+    } catch (DbException e) { rethrow(e); }
+
+    return true;
+}
+
+
+bool Database::queryStrings(const Transaction & txn, TableId table, 
+    const string & key, Strings & data)
+{
+    string d;
+
+    if (!queryString(txn, table, key, d))
+        return false;
+
+    string::iterator it = d.begin();
+    
+    while (it != d.end()) {
+
+        if (it + 4 > d.end())
+            throw Error(format("short db entry: `%1%'") % d);
+        
+        unsigned int len;
+        len = (unsigned char) *it++;
+        len |= ((unsigned char) *it++) << 8;
+        len |= ((unsigned char) *it++) << 16;
+        len |= ((unsigned char) *it++) << 24;
+        
+        if (it + len > d.end())
+            throw Error(format("short db entry: `%1%'") % d);
+
+        string s;
+        while (len--) s += *it++;
+
+        data.push_back(s);
+    }
+
+    return true;
+}
+
+
+void Database::setString(const Transaction & txn, TableId table,
+    const string & key, const string & data)
+{
+    try {
+        Db * db = getDb(table);
+        Dbt kt((void *) key.c_str(), key.length());
+        Dbt dt((void *) data.c_str(), data.length());
+        db->put(txn.txn, &kt, &dt, 0);
+    } catch (DbException e) { rethrow(e); }
+}
+
+
+void Database::setStrings(const Transaction & txn, TableId table,
+    const string & key, const Strings & data)
+{
+    string d;
+    
+    for (Strings::const_iterator it = data.begin();
+         it != data.end(); it++)
+    {
+        string s = *it;
+        unsigned int len = s.size();
+
+        d += len & 0xff;
+        d += (len >> 8) & 0xff;
+        d += (len >> 16) & 0xff;
+        d += (len >> 24) & 0xff;
+        
+        d += s;
+    }
+
+    setString(txn, table, key, d);
+}
+
+
+void Database::delPair(const Transaction & txn, TableId table,
+    const string & key)
+{
+    try {
+        Db * db = getDb(table);
+        Dbt kt((void *) key.c_str(), key.length());
+        db->del(txn.txn, &kt, 0);
+        /* Non-existence of a pair with the given key is not an
+           error. */
+    } catch (DbException e) { rethrow(e); }
+}
+
+
+void Database::enumTable(const Transaction & txn, TableId table,
+    Strings & keys)
+{
+    try {
+        Db * db = getDb(table);
+
+        Dbc * dbc;
+        db->cursor(txn.txn, &dbc, 0);
+        DestroyDbc destroyDbc(dbc);
+
+        Dbt kt, dt;
+        while (dbc->get(&kt, &dt, DB_NEXT) != DB_NOTFOUND)
+            keys.push_back(
+                string((char *) kt.get_data(), kt.get_size()));
+
+    } catch (DbException e) { rethrow(e); }
+}
diff --git a/src/libstore/db.hh b/src/libstore/db.hh
new file mode 100644
index 000000000000..1c681b9b5419
--- /dev/null
+++ b/src/libstore/db.hh
@@ -0,0 +1,89 @@
+#ifndef __DB_H
+#define __DB_H
+
+#include <string>
+#include <list>
+#include <map>
+
+#include <db_cxx.h>
+
+#include "util.hh"
+
+using namespace std;
+
+
+class Database;
+
+
+class Transaction
+{
+    friend class Database;
+
+private:
+    DbTxn * txn;
+    
+public:
+    Transaction();
+    Transaction(Database & _db);
+    ~Transaction();
+
+    void abort();
+    void commit();
+
+    void moveTo(Transaction & t);
+};
+
+
+#define noTxn Transaction()
+
+
+typedef unsigned int TableId; /* table handles */
+
+
+class Database
+{
+    friend class Transaction;
+
+private:
+    DbEnv * env;
+
+    int fdLock;
+    int fdAccessors;
+
+    TableId nextId;
+    map<TableId, Db *> tables;
+
+    void requireEnv();
+
+    Db * getDb(TableId table);
+
+public:
+    Database();
+    ~Database();
+    
+    void open(const string & path);
+    void close();
+
+    TableId openTable(const string & table);
+
+    bool queryString(const Transaction & txn, TableId table, 
+        const string & key, string & data);
+
+    bool queryStrings(const Transaction & txn, TableId table, 
+        const string & key, Strings & data);
+
+    void setString(const Transaction & txn, TableId table,
+        const string & key, const string & data);
+
+    void setStrings(const Transaction & txn, TableId table,
+        const string & key, const Strings & data);
+
+    void delPair(const Transaction & txn, TableId table,
+        const string & key);
+
+    void enumTable(const Transaction & txn, TableId table,
+        Strings & keys);
+};
+
+
+#endif /* !__DB_H */
diff --git a/src/libstore/exec.cc b/src/libstore/exec.cc
new file mode 100644
index 000000000000..47a385f147d5
--- /dev/null
+++ b/src/libstore/exec.cc
@@ -0,0 +1,127 @@
+#include <iostream>
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/wait.h>
+#include <unistd.h>
+#include <fcntl.h>
+
+#include "exec.hh"
+#include "util.hh"
+#include "globals.hh"
+
+
+static string pathNullDevice = "/dev/null";
+
+
+/* Run a program. */
+void runProgram(const string & program, 
+    const Strings & args, const Environment & env,
+    const string & logFileName)
+{
+    /* Create a log file. */
+    string logCommand = 
+	verbosity >= lvlDebug 
+	? "tee "  + logFileName + " >&2"
+	: "cat > " + logFileName;
+    /* !!! auto-pclose on exit */
+    FILE * logFile = popen(logCommand.c_str(), "w"); /* !!! escaping */
+    if (!logFile)
+        throw SysError(format("creating log file `%1%'") % logFileName);
+
+    /* Create a temporary directory where the build will take
+       place. */
+    string tmpDir = createTempDir();
+
+    AutoDelete delTmpDir(tmpDir);
+
+    /* Fork a child to build the package. */
+    pid_t pid;
+    switch (pid = fork()) {
+            
+    case -1:
+        throw SysError("unable to fork");
+
+    case 0: 
+
+        try { /* child */
+
+            if (chdir(tmpDir.c_str()) == -1)
+                throw SysError(format("changing into to `%1%'") % tmpDir);
+
+            /* Fill in the arguments. */
+            const char * argArr[args.size() + 2];
+            const char * * p = argArr;
+            string progName = baseNameOf(program);
+            *p++ = progName.c_str();
+            for (Strings::const_iterator i = args.begin();
+                 i != args.end(); i++)
+                *p++ = i->c_str();
+            *p = 0;
+
+            /* Fill in the environment. */
+            Strings envStrs;
+            const char * envArr[env.size() + 1];
+            p = envArr;
+            for (Environment::const_iterator i = env.begin();
+                 i != env.end(); i++)
+                *p++ = envStrs.insert(envStrs.end(), 
+                    i->first + "=" + i->second)->c_str();
+            *p = 0;
+
+            /* Dup the log handle into stderr. */
+            if (dup2(fileno(logFile), STDERR_FILENO) == -1)
+                throw SysError("cannot pipe standard error into log file");
+            
+            /* Dup stderr to stdin. */
+            if (dup2(STDERR_FILENO, STDOUT_FILENO) == -1)
+                throw SysError("cannot dup stderr into stdout");
+
+	    /* Reroute stdin to /dev/null. */
+	    int fdDevNull = open(pathNullDevice.c_str(), O_RDWR);
+	    if (fdDevNull == -1)
+		throw SysError(format("cannot open `%1%'") % pathNullDevice);
+	    if (dup2(fdDevNull, STDIN_FILENO) == -1)
+		throw SysError("cannot dup null device into stdin");
+
+            /* Execute the program.  This should not return. */
+            execve(program.c_str(), (char * *) argArr, (char * *) envArr);
+
+            throw SysError(format("unable to execute %1%") % program);
+            
+        } catch (exception & e) {
+            cerr << format("build error: %1%\n") % e.what();
+        }
+        _exit(1);
+
+    }
+
+    /* parent */
+
+    /* Close the logging pipe.  Note that this should not cause
+       the logger to exit until builder exits (because the latter
+       has an open file handle to the former). */
+    pclose(logFile);
+    
+    /* Wait for the child to finish. */
+    int status;
+    if (waitpid(pid, &status, 0) != pid)
+        throw Error("unable to wait for child");
+    
+    if (!WIFEXITED(status) || WEXITSTATUS(status) != 0) {
+	if (keepFailed) {
+	    printMsg(lvlTalkative, 
+		format("program `%1%' failed; keeping build directory `%2%'")
+                % program % tmpDir);
+	    delTmpDir.cancel();
+	}
+        if (WIFEXITED(status))
+            throw Error(format("program `%1%' failed with exit code %2%")
+                % program % WEXITSTATUS(status));
+        else if (WIFSIGNALED(status))
+            throw Error(format("program `%1%' failed due to signal %2%")
+                % program % WTERMSIG(status));
+        else
+            throw Error(format("program `%1%' died abnormally") % program);
+    }
+}
diff --git a/src/libstore/exec.hh b/src/libstore/exec.hh
new file mode 100644
index 000000000000..fc5bd6ac8d0b
--- /dev/null
+++ b/src/libstore/exec.hh
@@ -0,0 +1,22 @@
+#ifndef __EXEC_H
+#define __EXEC_H
+
+#include <string>
+#include <map>
+
+#include "util.hh"
+
+using namespace std;
+
+
+/* A Unix environment is a mapping from strings to strings. */
+typedef map<string, string> Environment;
+
+
+/* Run a program. */
+void runProgram(const string & program, 
+    const Strings & args, const Environment & env,
+    const string & logFileName);
+
+
+#endif /* !__EXEC_H */
diff --git a/src/libstore/expr.cc b/src/libstore/expr.cc
new file mode 100644
index 000000000000..7bb1f5306129
--- /dev/null
+++ b/src/libstore/expr.cc
@@ -0,0 +1,210 @@
+#include "expr.hh"
+#include "globals.hh"
+#include "store.hh"
+
+
+Error badTerm(const format & f, ATerm t)
+{
+    char * s = ATwriteToString(t);
+    if (!s) throw Error("cannot print term");
+    if (strlen(s) > 1000) {
+        int len;
+        s = ATwriteToSharedString(t, &len);
+        if (!s) throw Error("cannot print term");
+    }
+    return Error(format("%1%, in `%2%'") % f.str() % (string) s);
+}
+
+
+Hash hashTerm(ATerm t)
+{
+    return hashString(atPrint(t));
+}
+
+
+Path writeTerm(ATerm t, const string & suffix)
+{
+    /* The id of a term is its hash. */
+    Hash h = hashTerm(t);
+
+    Path path = canonPath(nixStore + "/" + 
+        (string) h + suffix + ".nix");
+
+    if (!isValidPath(path)) {
+        char * s = ATwriteToString(t);
+        if (!s) throw Error(format("cannot write aterm to `%1%'") % path);
+        addTextToStore(path, string(s));
+    }
+    
+    return path;
+}
+
+
+static void parsePaths(ATermList paths, PathSet & out)
+{
+    ATMatcher m;
+    for (ATermIterator i(paths); i; ++i) {
+        string s;
+        if (!(atMatch(m, *i) >> s))
+            throw badTerm("not a path", *i);
+        out.insert(s);
+    }
+}
+
+
+static void checkClosure(const Closure & closure)
+{
+    if (closure.elems.size() == 0)
+        throw Error("empty closure");
+
+    PathSet decl;
+    for (ClosureElems::const_iterator i = closure.elems.begin();
+         i != closure.elems.end(); i++)
+        decl.insert(i->first);
+    
+    for (PathSet::const_iterator i = closure.roots.begin();
+         i != closure.roots.end(); i++)
+        if (decl.find(*i) == decl.end())
+            throw Error(format("undefined root path `%1%'") % *i);
+    
+    for (ClosureElems::const_iterator i = closure.elems.begin();
+         i != closure.elems.end(); i++)
+        for (PathSet::const_iterator j = i->second.refs.begin();
+             j != i->second.refs.end(); j++)
+            if (decl.find(*j) == decl.end())
+                throw Error(
+		    format("undefined path `%1%' referenced by `%2%'")
+		    % *j % i->first);
+}
+
+
+/* Parse a closure. */
+static bool parseClosure(ATerm t, Closure & closure)
+{
+    ATermList roots, elems;
+    ATMatcher m;
+
+    if (!(atMatch(m, t) >> "Closure" >> roots >> elems))
+        return false;
+
+    parsePaths(roots, closure.roots);
+
+    for (ATermIterator i(elems); i; ++i) {
+        string path;
+        ATermList refs;
+        if (!(atMatch(m, *i) >> "" >> path >> refs))
+            throw badTerm("not a closure element", *i);
+        ClosureElem elem;
+        parsePaths(refs, elem.refs);
+        closure.elems[path] = elem;
+    }
+
+    checkClosure(closure);
+    return true;
+}
+
+
+static bool parseDerivation(ATerm t, Derivation & derivation)
+{
+    ATMatcher m;
+    ATermList outs, ins, args, bnds;
+    string builder, platform;
+
+    if (!(atMatch(m, t) >> "Derive" >> outs >> ins >> platform
+            >> builder >> args >> bnds))
+        return false;
+
+    parsePaths(outs, derivation.outputs);
+    parsePaths(ins, derivation.inputs);
+
+    derivation.builder = builder;
+    derivation.platform = platform;
+    
+    for (ATermIterator i(args); i; ++i) {
+        string s;
+        if (!(atMatch(m, *i) >> s))
+            throw badTerm("string expected", *i);
+        derivation.args.push_back(s);
+    }
+
+    for (ATermIterator i(bnds); i; ++i) {
+        string s1, s2;
+        if (!(atMatch(m, *i) >> "" >> s1 >> s2))
+            throw badTerm("tuple of strings expected", *i);
+        derivation.env[s1] = s2;
+    }
+
+    return true;
+}
+
+
+NixExpr parseNixExpr(ATerm t)
+{
+    NixExpr ne;
+    if (parseClosure(t, ne.closure))
+        ne.type = NixExpr::neClosure;
+    else if (parseDerivation(t, ne.derivation))
+        ne.type = NixExpr::neDerivation;
+    else throw badTerm("not a Nix expression", t);
+    return ne;
+}
+
+
+static ATermList unparsePaths(const PathSet & paths)
+{
+    ATermList l = ATempty;
+    for (PathSet::const_iterator i = paths.begin();
+         i != paths.end(); i++)
+        l = ATinsert(l, ATmake("<str>", i->c_str()));
+    return ATreverse(l);
+}
+
+
+static ATerm unparseClosure(const Closure & closure)
+{
+    ATermList roots = unparsePaths(closure.roots);
+    
+    ATermList elems = ATempty;
+    for (ClosureElems::const_iterator i = closure.elems.begin();
+         i != closure.elems.end(); i++)
+        elems = ATinsert(elems,
+            ATmake("(<str>, <term>)",
+                i->first.c_str(),
+                unparsePaths(i->second.refs)));
+
+    return ATmake("Closure(<term>, <term>)", roots, elems);
+}
+
+
+static ATerm unparseDerivation(const Derivation & derivation)
+{
+    ATermList args = ATempty;
+    for (Strings::const_iterator i = derivation.args.begin();
+         i != derivation.args.end(); i++)
+        args = ATinsert(args, ATmake("<str>", i->c_str()));
+
+    ATermList env = ATempty;
+    for (StringPairs::const_iterator i = derivation.env.begin();
+         i != derivation.env.end(); i++)
+        env = ATinsert(env,
+            ATmake("(<str>, <str>)", 
+                i->first.c_str(), i->second.c_str()));
+
+    return ATmake("Derive(<term>, <term>, <str>, <str>, <term>, <term>)",
+        unparsePaths(derivation.outputs),
+        unparsePaths(derivation.inputs),
+        derivation.platform.c_str(),
+        derivation.builder.c_str(),
+        ATreverse(args),
+        ATreverse(env));
+}
+
+
+ATerm unparseNixExpr(const NixExpr & ne)
+{
+    if (ne.type == NixExpr::neClosure)
+        return unparseClosure(ne.closure);
+    else if (ne.type == NixExpr::neDerivation)
+        return unparseDerivation(ne.derivation);
+    else abort();
+}
diff --git a/src/libstore/expr.hh b/src/libstore/expr.hh
new file mode 100644
index 000000000000..f5abf9af0d3a
--- /dev/null
+++ b/src/libstore/expr.hh
@@ -0,0 +1,60 @@
+#ifndef __FSTATE_H
+#define __FSTATE_H
+
+#include "aterm.hh"
+#include "store.hh"
+
+
+/* Abstract syntax of Nix expressions. */
+
+struct ClosureElem
+{
+    PathSet refs;
+};
+
+typedef map<Path, ClosureElem> ClosureElems;
+
+struct Closure
+{
+    PathSet roots;
+    ClosureElems elems;
+};
+
+typedef map<string, string> StringPairs;
+
+struct Derivation
+{
+    PathSet outputs;
+    PathSet inputs; /* Nix expressions, not actual inputs */
+    string platform;
+    Path builder;
+    Strings args;
+    StringPairs env;
+};
+
+struct NixExpr
+{
+    enum { neClosure, neDerivation } type;
+    Closure closure;
+    Derivation derivation;
+};
+
+
+/* Throw an exception with an error message containing the given
+   aterm. */
+Error badTerm(const format & f, ATerm t);
+
+/* Hash an aterm. */
+Hash hashTerm(ATerm t);
+
+/* Write an aterm to the Nix store directory, and return its path. */
+Path writeTerm(ATerm t, const string & suffix);
+
+/* Parse a Nix expression. */
+NixExpr parseNixExpr(ATerm t);
+
+/* Parse a Nix expression. */
+ATerm unparseNixExpr(const NixExpr & ne);
+
+
+#endif /* !__FSTATE_H */
diff --git a/src/libstore/globals.cc b/src/libstore/globals.cc
new file mode 100644
index 000000000000..a292b49aeae0
--- /dev/null
+++ b/src/libstore/globals.cc
@@ -0,0 +1,8 @@
+#include "globals.hh"
+
+string nixStore = "/UNINIT";
+string nixDataDir = "/UNINIT";
+string nixLogDir = "/UNINIT";
+string nixDBPath = "/UNINIT";
+
+bool keepFailed = false;
diff --git a/src/libstore/globals.hh b/src/libstore/globals.hh
new file mode 100644
index 000000000000..1b4d0bde3ffe
--- /dev/null
+++ b/src/libstore/globals.hh
@@ -0,0 +1,29 @@
+#ifndef __GLOBALS_H
+#define __GLOBALS_H
+
+#include <string>
+
+using namespace std;
+
+/* Path names. */
+
+/* nixStore is the directory where we generally store atomic and
+   derived files. */
+extern string nixStore;
+
+extern string nixDataDir; /* !!! fix */
+
+/* nixLogDir is the directory where we log various operations. */ 
+extern string nixLogDir;
+
+/* nixDBPath is the path name of our Berkeley DB environment. */
+extern string nixDBPath;
+
+
+/* Misc. global flags. */
+
+/* Whether to keep temporary directories of failed builds. */
+extern bool keepFailed;
+
+
+#endif /* !__GLOBALS_H */
diff --git a/src/libstore/normalise.cc b/src/libstore/normalise.cc
new file mode 100644
index 000000000000..cb2bf4f5b183
--- /dev/null
+++ b/src/libstore/normalise.cc
@@ -0,0 +1,369 @@
+#include <map>
+
+#include "normalise.hh"
+#include "references.hh"
+#include "exec.hh"
+#include "pathlocks.hh"
+#include "globals.hh"
+
+
+static Path useSuccessor(const Path & path)
+{
+    string pathSucc;
+    if (querySuccessor(path, pathSucc)) {
+        debug(format("successor %1% -> %2%") % (string) path % pathSucc);
+        return pathSucc;
+    } else
+        return path;
+}
+
+
+Path normaliseNixExpr(const Path & _nePath, PathSet pending)
+{
+    startNest(nest, lvlTalkative,
+        format("normalising expression in `%1%'") % (string) _nePath);
+
+    /* Try to substitute the expression by any known successors in
+       order to speed up the rewrite process. */
+    Path nePath = useSuccessor(_nePath);
+
+    /* Get the Nix expression. */
+    NixExpr ne = exprFromPath(nePath, pending);
+
+    /* If this is a normal form (i.e., a closure) we are done. */
+    if (ne.type == NixExpr::neClosure) return nePath;
+    if (ne.type != NixExpr::neDerivation) abort();
+    
+
+    /* Otherwise, it's a derivation expression, and we have to build it to
+       determine its normal form. */
+
+
+    /* Some variables. */
+
+    /* Input paths, with their closure elements. */
+    ClosureElems inClosures; 
+
+    /* Referenceable paths (i.e., input and output paths). */
+    PathSet allPaths;
+
+    /* The environment to be passed to the builder. */
+    Environment env; 
+
+    /* The result. */
+    NixExpr nf;
+    nf.type = NixExpr::neClosure;
+
+
+    /* The outputs are referenceable paths. */
+    for (PathSet::iterator i = ne.derivation.outputs.begin();
+         i != ne.derivation.outputs.end(); i++)
+    {
+        debug(format("building path `%1%'") % *i);
+        allPaths.insert(*i);
+    }
+
+    /* Obtain locks on all output paths.  The locks are automatically
+       released when we exit this function or Nix crashes. */
+    PathLocks outputLocks(ne.derivation.outputs);
+
+    /* Now check again whether there is a successor.  This is because
+       another process may have started building in parallel.  After
+       it has finished and released the locks, we can (and should)
+       reuse its results.  (Strictly speaking the first successor
+       check above can be omitted, but that would be less efficient.)
+       Note that since we now hold the locks on the output paths, no
+       other process can build this expression, so no further checks
+       are necessary. */
+    {
+        Path nePath2 = useSuccessor(nePath);
+        if (nePath != nePath2) {
+            NixExpr ne = exprFromPath(nePath2, pending);
+            debug(format("skipping build of expression `%1%', someone beat us to it")
+		  % (string) nePath);
+            if (ne.type != NixExpr::neClosure) abort();
+            return nePath2;
+        }
+    }
+
+    /* Right platform? */
+    if (ne.derivation.platform != thisSystem)
+        throw Error(format("a `%1%' is required, but I am a `%2%'")
+		    % ne.derivation.platform % thisSystem);
+        
+    /* Realise inputs (and remember all input paths). */
+    for (PathSet::iterator i = ne.derivation.inputs.begin();
+         i != ne.derivation.inputs.end(); i++)
+    {
+        Path nfPath = normaliseNixExpr(*i, pending);
+        realiseClosure(nfPath, pending);
+        /* !!! nfPath should be a root of the garbage collector while
+           we are building */
+        NixExpr ne = exprFromPath(nfPath, pending);
+        if (ne.type != NixExpr::neClosure) abort();
+        for (ClosureElems::iterator j = ne.closure.elems.begin();
+             j != ne.closure.elems.end(); j++)
+	{
+            inClosures[j->first] = j->second;
+	    allPaths.insert(j->first);
+	}
+    }
+
+    /* Most shells initialise PATH to some default (/bin:/usr/bin:...) when
+       PATH is not set.  We don't want this, so we fill it in with some dummy
+       value. */
+    env["PATH"] = "/path-not-set";
+
+    /* Set HOME to a non-existing path to prevent certain programs from using
+       /etc/passwd (or NIS, or whatever) to locate the home directory (for
+       example, wget looks for ~/.wgetrc).  I.e., these tools use /etc/passwd
+       if HOME is not set, but they will just assume that the settings file
+       they are looking for does not exist if HOME is set but points to some
+       non-existing path. */
+    env["HOME"] = "/homeless-shelter";
+
+    /* Build the environment. */
+    for (StringPairs::iterator i = ne.derivation.env.begin();
+         i != ne.derivation.env.end(); i++)
+        env[i->first] = i->second;
+
+    /* We can skip running the builder if all output paths are already
+       valid. */
+    bool fastBuild = true;
+    for (PathSet::iterator i = ne.derivation.outputs.begin();
+         i != ne.derivation.outputs.end(); i++)
+    {
+        if (!isValidPath(*i)) { 
+            fastBuild = false;
+            break;
+        }
+    }
+
+    if (!fastBuild) {
+
+        /* If any of the outputs already exist but are not registered,
+           delete them. */
+        for (PathSet::iterator i = ne.derivation.outputs.begin(); 
+             i != ne.derivation.outputs.end(); i++)
+        {
+            Path path = *i;
+            if (isValidPath(path))
+                throw Error(format("obstructed build: path `%1%' exists") % path);
+            if (pathExists(path)) {
+                debug(format("removing unregistered path `%1%'") % path);
+                deletePath(path);
+            }
+        }
+
+        /* Run the builder. */
+        printMsg(lvlChatty, format("building..."));
+        runProgram(ne.derivation.builder, ne.derivation.args, env,
+            nixLogDir + "/" + baseNameOf(nePath));
+        printMsg(lvlChatty, format("build completed"));
+        
+    } else
+        printMsg(lvlChatty, format("fast build succesful"));
+
+    /* Check whether the output paths were created, and grep each
+       output path to determine what other paths it references.  Also make all
+       output paths read-only. */
+    PathSet usedPaths;
+    for (PathSet::iterator i = ne.derivation.outputs.begin(); 
+         i != ne.derivation.outputs.end(); i++)
+    {
+        Path path = *i;
+        if (!pathExists(path))
+            throw Error(format("path `%1%' does not exist") % path);
+        nf.closure.roots.insert(path);
+
+	makePathReadOnly(path);
+
+	/* For this output path, find the references to other paths contained
+	   in it. */
+        Strings refPaths = filterReferences(path, 
+            Strings(allPaths.begin(), allPaths.end()));
+
+	/* Construct a closure element for this output path. */
+        ClosureElem elem;
+
+	/* For each path referenced by this output path, add its id to the
+	   closure element and add the id to the `usedPaths' set (so that the
+	   elements referenced by *its* closure are added below). */
+        for (Paths::iterator j = refPaths.begin();
+	     j != refPaths.end(); j++)
+	{
+	    Path path = *j;
+	    elem.refs.insert(path);
+            if (inClosures.find(path) != inClosures.end())
+                usedPaths.insert(path);
+	    else if (ne.derivation.outputs.find(path) == ne.derivation.outputs.end())
+		abort();
+        }
+
+        nf.closure.elems[path] = elem;
+    }
+
+    /* Close the closure.  That is, for any referenced path, add the paths
+       referenced by it. */
+    PathSet donePaths;
+
+    while (!usedPaths.empty()) {
+	PathSet::iterator i = usedPaths.begin();
+	Path path = *i;
+	usedPaths.erase(i);
+
+	if (donePaths.find(path) != donePaths.end()) continue;
+	donePaths.insert(path);
+
+	ClosureElems::iterator j = inClosures.find(path);
+	if (j == inClosures.end()) abort();
+
+	nf.closure.elems[path] = j->second;
+
+	for (PathSet::iterator k = j->second.refs.begin();
+	     k != j->second.refs.end(); k++)
+	    usedPaths.insert(*k);
+    }
+
+    /* For debugging, print out the referenced and unreferenced paths. */
+    for (ClosureElems::iterator i = inClosures.begin();
+         i != inClosures.end(); i++)
+    {
+        PathSet::iterator j = donePaths.find(i->first);
+        if (j == donePaths.end())
+            debug(format("NOT referenced: `%1%'") % i->first);
+        else
+            debug(format("referenced: `%1%'") % i->first);
+    }
+
+    /* Write the normal form.  This does not have to occur in the
+       transaction below because writing terms is idem-potent. */
+    ATerm nfTerm = unparseNixExpr(nf);
+    printMsg(lvlVomit, format("normal form: %1%") % atPrint(nfTerm));
+    Path nfPath = writeTerm(nfTerm, "-s");
+
+    /* Register each outpat path, and register the normal form.  This
+       is wrapped in one database transaction to ensure that if we
+       crash, either everything is registered or nothing is.  This is
+       for recoverability: unregistered paths in the store can be
+       deleted arbitrarily, while registered paths can only be deleted
+       by running the garbage collector. */
+    Transaction txn;
+    createStoreTransaction(txn);
+    for (PathSet::iterator i = ne.derivation.outputs.begin(); 
+         i != ne.derivation.outputs.end(); i++)
+        registerValidPath(txn, *i);
+    registerSuccessor(txn, nePath, nfPath);
+    txn.commit();
+
+    return nfPath;
+}
+
+
+void realiseClosure(const Path & nePath, PathSet pending)
+{
+    startNest(nest, lvlDebug, format("realising closure `%1%'") % nePath);
+
+    NixExpr ne = exprFromPath(nePath, pending);
+    if (ne.type != NixExpr::neClosure)
+        throw Error(format("expected closure in `%1%'") % nePath);
+    
+    for (ClosureElems::const_iterator i = ne.closure.elems.begin();
+         i != ne.closure.elems.end(); i++)
+        ensurePath(i->first, pending);
+}
+
+
+void ensurePath(const Path & path, PathSet pending)
+{
+    /* If the path is already valid, we're done. */
+    if (isValidPath(path)) return;
+    
+    /* Otherwise, try the substitutes. */
+    Paths subPaths = querySubstitutes(path);
+
+    for (Paths::iterator i = subPaths.begin(); 
+         i != subPaths.end(); i++)
+    {
+        try {
+            normaliseNixExpr(*i, pending);
+            if (isValidPath(path)) return;
+            throw Error(format("substitute failed to produce expected output path"));
+        } catch (Error & e) {
+            printMsg(lvlTalkative, 
+                format("building of substitute `%1%' for `%2%' failed: %3%")
+                % *i % path % e.what());
+        }
+    }
+
+    throw Error(format("path `%1%' is required, "
+        "but there are no (successful) substitutes") % path);
+}
+
+
+NixExpr exprFromPath(const Path & path, PathSet pending)
+{
+    ensurePath(path, pending);
+    ATerm t = ATreadFromNamedFile(path.c_str());
+    if (!t) throw Error(format("cannot read aterm from `%1%'") % path);
+    return parseNixExpr(t);
+}
+
+
+PathSet nixExprRoots(const Path & nePath)
+{
+    PathSet paths;
+
+    NixExpr ne = exprFromPath(nePath);
+
+    if (ne.type == NixExpr::neClosure)
+        paths.insert(ne.closure.roots.begin(), ne.closure.roots.end());
+    else if (ne.type == NixExpr::neDerivation)
+        paths.insert(ne.derivation.outputs.begin(),
+            ne.derivation.outputs.end());
+    else abort();
+
+    return paths;
+}
+
+
+static void requisitesWorker(const Path & nePath,
+    bool includeExprs, bool includeSuccessors,
+    PathSet & paths, PathSet & doneSet)
+{
+    if (doneSet.find(nePath) != doneSet.end()) return;
+    doneSet.insert(nePath);
+
+    NixExpr ne = exprFromPath(nePath);
+
+    if (ne.type == NixExpr::neClosure)
+        for (ClosureElems::iterator i = ne.closure.elems.begin();
+             i != ne.closure.elems.end(); i++)
+            paths.insert(i->first);
+    
+    else if (ne.type == NixExpr::neDerivation)
+        for (PathSet::iterator i = ne.derivation.inputs.begin();
+             i != ne.derivation.inputs.end(); i++)
+            requisitesWorker(*i,
+                includeExprs, includeSuccessors, paths, doneSet);
+
+    else abort();
+
+    if (includeExprs) paths.insert(nePath);
+
+    string nfPath;
+    if (includeSuccessors && (nfPath = useSuccessor(nePath)) != nePath)
+        requisitesWorker(nfPath, includeExprs, includeSuccessors,
+            paths, doneSet);
+}
+
+
+PathSet nixExprRequisites(const Path & nePath,
+    bool includeExprs, bool includeSuccessors)
+{
+    PathSet paths;
+    PathSet doneSet;
+    requisitesWorker(nePath, includeExprs, includeSuccessors,
+        paths, doneSet);
+    return paths;
+}
diff --git a/src/libstore/normalise.hh b/src/libstore/normalise.hh
new file mode 100644
index 000000000000..bbe846404cc0
--- /dev/null
+++ b/src/libstore/normalise.hh
@@ -0,0 +1,46 @@
+#ifndef __NORMALISE_H
+#define __NORMALISE_H
+
+#include "expr.hh"
+
+
+/* Normalise a Nix expression.  That is, if the expression is a
+   derivation, a path containing an equivalent closure expression is
+   returned.  This requires that the derivation is performed, unless a
+   successor is known. */
+Path normaliseNixExpr(const Path & nePath, PathSet pending = PathSet());
+
+/* Realise a closure expression in the file system. 
+
+   The pending paths are those that are already being realised.  This
+   prevents infinite recursion for paths realised through a substitute
+   (since when we build the substitute, we would first try to realise
+   its output paths through substitutes... kaboom!). */
+void realiseClosure(const Path & nePath, PathSet pending = PathSet());
+
+/* Ensure that a path exists, possibly by instantiating it by
+   realising a substitute. */
+void ensurePath(const Path & path, PathSet pending = PathSet());
+
+/* Read a Nix expression, after ensuring its existence through
+   ensurePath(). */
+NixExpr exprFromPath(const Path & path, PathSet pending = PathSet());
+
+/* Get the list of root (output) paths of the given Nix expression. */
+PathSet nixExprRoots(const Path & nePath);
+
+/* Get the list of paths that are required to realise the given
+   expression.  For a derive expression, this is the union of
+   requisites of the inputs; for a closure expression, it is the path of
+   each element in the closure.  If `includeExprs' is true, include the
+   paths of the Nix expressions themselves.  If `includeSuccessors' is
+   true, include the requisites of successors. */
+PathSet nixExprRequisites(const Path & nePath,
+    bool includeExprs, bool includeSuccessors);
+
+/* Return the list of the paths of all known Nix expressions whose
+   output paths are completely contained in the set `outputs'. */
+PathSet findGenerators(const PathSet & outputs);
+
+
+#endif /* !__NORMALISE_H */
diff --git a/src/libstore/pathlocks.cc b/src/libstore/pathlocks.cc
new file mode 100644
index 000000000000..3ecbbbcbafd5
--- /dev/null
+++ b/src/libstore/pathlocks.cc
@@ -0,0 +1,90 @@
+#include <cerrno>
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+
+#include "pathlocks.hh"
+
+
+bool lockFile(int fd, LockType lockType, bool wait)
+{
+    struct flock lock;
+    if (lockType == ltRead) lock.l_type = F_RDLCK;
+    else if (lockType == ltWrite) lock.l_type = F_WRLCK;
+    else if (lockType == ltNone) lock.l_type = F_UNLCK;
+    else abort();
+    lock.l_whence = SEEK_SET;
+    lock.l_start = 0;
+    lock.l_len = 0; /* entire file */
+
+    if (wait) {
+        while (fcntl(fd, F_SETLKW, &lock) != 0)
+            if (errno != EINTR)
+                throw SysError(format("acquiring/releasing lock"));
+    } else {
+        while (fcntl(fd, F_SETLK, &lock) != 0) {
+            if (errno == EACCES || errno == EAGAIN) return false;
+            if (errno != EINTR) 
+                throw SysError(format("acquiring/releasing lock"));
+        }
+    }
+
+    return true;
+}
+
+
+/* This enables us to check whether are not already holding a lock on
+   a file ourselves.  POSIX locks (fcntl) suck in this respect: if we
+   close a descriptor, the previous lock will be closed as well.  And
+   there is no way to query whether we already have a lock (F_GETLK
+   only works on locks held by other processes). */
+static StringSet lockedPaths; /* !!! not thread-safe */
+
+
+PathLocks::PathLocks(const PathSet & _paths)
+{
+    /* Note that `fds' is built incrementally so that the destructor
+       will only release those locks that we have already acquired. */
+
+    /* Sort the paths.  This assures that locks are always acquired in
+       the same order, thus preventing deadlocks. */
+    Paths paths(_paths.begin(), _paths.end());
+    paths.sort();
+    
+    /* Acquire the lock for each path. */
+    for (Paths::iterator i = paths.begin(); i != paths.end(); i++) {
+        Path path = *i;
+        Path lockPath = path + ".lock";
+
+        debug(format("locking path `%1%'") % path);
+
+        if (lockedPaths.find(lockPath) != lockedPaths.end()) {
+            debug(format("already holding lock on `%1%'") % lockPath);
+            continue;
+        }
+        
+        /* Open/create the lock file. */
+        int fd = open(lockPath.c_str(), O_WRONLY | O_CREAT, 0666);
+        if (fd == -1)
+            throw SysError(format("opening lock file `%1%'") % lockPath);
+
+        fds.push_back(fd);
+        this->paths.push_back(lockPath);
+
+        /* Acquire an exclusive lock. */
+        lockFile(fd, ltWrite, true);
+
+        lockedPaths.insert(lockPath);
+    }
+}
+
+
+PathLocks::~PathLocks()
+{
+    for (list<int>::iterator i = fds.begin(); i != fds.end(); i++)
+        close(*i);
+
+    for (Paths::iterator i = paths.begin(); i != paths.end(); i++)
+        lockedPaths.erase(*i);
+}
diff --git a/src/libstore/pathlocks.hh b/src/libstore/pathlocks.hh
new file mode 100644
index 000000000000..ce61386d6df0
--- /dev/null
+++ b/src/libstore/pathlocks.hh
@@ -0,0 +1,24 @@
+#ifndef __PATHLOCKS_H
+#define __PATHLOCKS_H
+
+#include "util.hh"
+
+
+typedef enum LockType { ltRead, ltWrite, ltNone };
+
+bool lockFile(int fd, LockType lockType, bool wait);
+
+
+class PathLocks 
+{
+private:
+    list<int> fds;
+    Paths paths;
+
+public:
+    PathLocks(const PathSet & _paths);
+    ~PathLocks();
+};
+
+
+#endif /* !__PATHLOCKS_H */
diff --git a/src/libstore/references.cc b/src/libstore/references.cc
new file mode 100644
index 000000000000..ab743f76d2d3
--- /dev/null
+++ b/src/libstore/references.cc
@@ -0,0 +1,106 @@
+#include <cerrno>
+#include <map>
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+#include <dirent.h>
+#include <fcntl.h>
+
+#include "references.hh"
+#include "hash.hh"
+
+
+static void search(const string & s,
+    Strings & ids, Strings & seen)
+{
+    for (Strings::iterator i = ids.begin();
+         i != ids.end(); )
+    {
+        if (s.find(*i) == string::npos)
+            i++;
+        else {
+            debug(format("found reference to `%1%'") % *i);
+            seen.push_back(*i);
+            i = ids.erase(i);
+        }
+    }
+}
+
+
+void checkPath(const string & path,
+    Strings & ids, Strings & seen)
+{
+    struct stat st;
+    if (lstat(path.c_str(), &st))
+        throw SysError(format("getting attributes of path `%1%'") % path);
+
+    if (S_ISDIR(st.st_mode)) {
+        AutoCloseDir dir = opendir(path.c_str());
+
+        struct dirent * dirent;
+        while (errno = 0, dirent = readdir(dir)) {
+            string name = dirent->d_name;
+            if (name == "." || name == "..") continue;
+            search(name, ids, seen);
+            checkPath(path + "/" + name, ids, seen);
+        }
+    }
+
+    else if (S_ISREG(st.st_mode)) {
+        
+        debug(format("checking `%1%'") % path);
+
+        AutoCloseFD fd = open(path.c_str(), O_RDONLY);
+        if (fd == -1) throw SysError(format("opening file `%1%'") % path);
+
+        unsigned char * buf = new unsigned char[st.st_size];
+
+        readFull(fd, buf, st.st_size);
+
+        search(string((char *) buf, st.st_size), ids, seen);
+        
+        delete buf; /* !!! autodelete */
+    }
+    
+    else if (S_ISLNK(st.st_mode)) {
+        char buf[st.st_size];
+        if (readlink(path.c_str(), buf, st.st_size) != st.st_size)
+            throw SysError(format("reading symbolic link `%1%'") % path);
+        search(string(buf, st.st_size), ids, seen);
+    }
+    
+    else throw Error(format("unknown file type: %1%") % path);
+}
+
+
+Strings filterReferences(const string & path, const Strings & paths)
+{
+    map<string, string> backMap;
+    Strings ids;
+    Strings seen;
+
+    /* For efficiency (and a higher hit rate), just search for the
+       hash part of the file name.  (This assumes that all references
+       have the form `HASH-bla'). */
+    for (Strings::const_iterator i = paths.begin();
+         i != paths.end(); i++)
+    {
+        string s = string(baseNameOf(*i), 0, 32);
+        parseHash(s);
+        ids.push_back(s);
+        backMap[s] = *i;
+    }
+
+    checkPath(path, ids, seen);
+
+    Strings found;
+    for (Strings::iterator i = seen.begin(); i != seen.end(); i++)
+    {
+        map<string, string>::iterator j;
+        if ((j = backMap.find(*i)) == backMap.end()) abort();
+        found.push_back(j->second);
+    }
+
+    return found;
+}
diff --git a/src/libstore/references.hh b/src/libstore/references.hh
new file mode 100644
index 000000000000..ada23a883302
--- /dev/null
+++ b/src/libstore/references.hh
@@ -0,0 +1,10 @@
+#ifndef __REFERENCES_H
+#define __REFERENCES_H
+
+#include "util.hh"
+
+
+Strings filterReferences(const Path & path, const Strings & refs);
+
+
+#endif /* !__REFERENCES_H */
diff --git a/src/libstore/store.cc b/src/libstore/store.cc
new file mode 100644
index 000000000000..c83316cf6ad5
--- /dev/null
+++ b/src/libstore/store.cc
@@ -0,0 +1,407 @@
+#include <iostream>
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/wait.h>
+#include <fcntl.h>
+#include <unistd.h>
+
+#include "store.hh"
+#include "globals.hh"
+#include "db.hh"
+#include "archive.hh"
+#include "pathlocks.hh"
+
+
+/* Nix database. */
+static Database nixDB;
+
+
+/* Database tables. */
+
+/* dbValidPaths :: Path -> ()
+
+   The existence of a key $p$ indicates that path $p$ is valid (that
+   is, produced by a succesful build). */
+static TableId dbValidPaths;
+
+/* dbSuccessors :: Path -> Path
+
+   Each pair $(p_1, p_2)$ in this mapping records the fact that the
+   Nix expression stored at path $p_1$ has a successor expression
+   stored at path $p_2$.
+
+   Note that a term $y$ is a successor of $x$ iff there exists a
+   sequence of rewrite steps that rewrites $x$ into $y$.
+*/
+static TableId dbSuccessors;
+
+/* dbSuccessorsRev :: Path -> [Path]
+
+   The reverse mapping of dbSuccessors (i.e., it stores the
+   predecessors of a Nix expression).
+*/
+static TableId dbSuccessorsRev;
+
+/* dbSubstitutes :: Path -> [Path]
+
+   Each pair $(p, [ps])$ tells Nix that it can realise any of the
+   Nix expressions stored at paths $ps$ to produce a path $p$.
+
+   The main purpose of this is for distributed caching of derivates.
+   One system can compute a derivate and put it on a website (as a Nix
+   archive), for instance, and then another system can register a
+   substitute for that derivate.  The substitute in this case might be
+   a Nix expression that fetches the Nix archive.
+*/
+static TableId dbSubstitutes;
+
+/* dbSubstitutesRev :: Path -> [Path]
+
+   The reverse mapping of dbSubstitutes.
+*/
+static TableId dbSubstitutesRev;
+
+
+void openDB()
+{
+    nixDB.open(nixDBPath);
+    dbValidPaths = nixDB.openTable("validpaths");
+    dbSuccessors = nixDB.openTable("successors");
+    dbSuccessorsRev = nixDB.openTable("successors-rev");
+    dbSubstitutes = nixDB.openTable("substitutes");
+    dbSubstitutesRev = nixDB.openTable("substitutes-rev");
+}
+
+
+void initDB()
+{
+}
+
+
+void createStoreTransaction(Transaction & txn)
+{
+    Transaction txn2(nixDB);
+    txn2.moveTo(txn);
+}
+
+
+/* Path copying. */
+
+struct CopySink : DumpSink
+{
+    int fd;
+    virtual void operator () (const unsigned char * data, unsigned int len)
+    {
+        writeFull(fd, data, len);
+    }
+};
+
+
+struct CopySource : RestoreSource
+{
+    int fd;
+    virtual void operator () (unsigned char * data, unsigned int len)
+    {
+        readFull(fd, data, len);
+    }
+};
+
+
+void copyPath(const Path & src, const Path & dst)
+{
+    debug(format("copying `%1%' to `%2%'") % src % dst);
+
+    /* Unfortunately C++ doesn't support coprocedures, so we have no
+       nice way to chain CopySink and CopySource together.  Instead we
+       fork off a child to run the sink.  (Fork-less platforms should
+       use a thread). */
+
+    /* Create a pipe. */
+    int fds[2];
+    if (pipe(fds) == -1) throw SysError("creating pipe");
+
+    /* Fork. */
+    pid_t pid;
+    switch (pid = fork()) {
+
+    case -1:
+        throw SysError("unable to fork");
+
+    case 0: /* child */
+        try {
+            close(fds[1]);
+            CopySource source;
+            source.fd = fds[0];
+            restorePath(dst, source);
+            _exit(0);
+        }  catch (exception & e) {
+            cerr << "error: " << e.what() << endl;
+        }
+        _exit(1);        
+    }
+
+    close(fds[0]);
+    
+    /* Parent. */
+
+    CopySink sink;
+    sink.fd = fds[1];
+    dumpPath(src, sink);
+
+    /* Wait for the child to finish. */
+    int status;
+    if (waitpid(pid, &status, 0) != pid)
+        throw SysError("waiting for child");
+
+    if (!WIFEXITED(status) || WEXITSTATUS(status) != 0)
+        throw Error("cannot copy file: child died");
+}
+
+
+void registerSuccessor(const Transaction & txn,
+    const Path & srcPath, const Path & sucPath)
+{
+    Path known;
+    if (nixDB.queryString(txn, dbSuccessors, srcPath, known) &&
+        known != sucPath)
+    {
+        throw Error(format(
+            "the `impossible' happened: expression in path "
+            "`%1%' appears to have multiple successors "
+            "(known `%2%', new `%3%'")
+            % srcPath % known % sucPath);
+    }
+
+    Paths revs;
+    nixDB.queryStrings(txn, dbSuccessorsRev, sucPath, revs);
+    if (find(revs.begin(), revs.end(), srcPath) == revs.end())
+        revs.push_back(srcPath);
+
+    nixDB.setString(txn, dbSuccessors, srcPath, sucPath);
+    nixDB.setStrings(txn, dbSuccessorsRev, sucPath, revs);
+}
+
+
+bool querySuccessor(const Path & srcPath, Path & sucPath)
+{
+    return nixDB.queryString(noTxn, dbSuccessors, srcPath, sucPath);
+}
+
+
+Paths queryPredecessors(const Path & sucPath)
+{
+    Paths revs;
+    nixDB.queryStrings(noTxn, dbSuccessorsRev, sucPath, revs);
+    return revs;
+}
+
+
+void registerSubstitute(const Path & srcPath, const Path & subPath)
+{
+    Transaction txn(nixDB);
+
+    Paths subs;
+    nixDB.queryStrings(txn, dbSubstitutes, srcPath, subs);
+
+    if (find(subs.begin(), subs.end(), subPath) != subs.end()) {
+        /* Nothing to do if the substitute is already known. */
+        txn.abort();
+        return;
+    }
+    subs.push_front(subPath); /* new substitutes take precedence */
+
+    Paths revs;
+    nixDB.queryStrings(txn, dbSubstitutesRev, subPath, revs);
+    if (find(revs.begin(), revs.end(), srcPath) == revs.end())
+        revs.push_back(srcPath);
+    
+    nixDB.setStrings(txn, dbSubstitutes, srcPath, subs);
+    nixDB.setStrings(txn, dbSubstitutesRev, subPath, revs);
+
+    txn.commit();
+}
+
+
+Paths querySubstitutes(const Path & srcPath)
+{
+    Paths subPaths;
+    nixDB.queryStrings(noTxn, dbSubstitutes, srcPath, subPaths);
+    return subPaths;
+}
+
+
+void registerValidPath(const Transaction & txn, const Path & _path)
+{
+    Path path(canonPath(_path));
+    debug(format("registering path `%1%'") % path);
+    nixDB.setString(txn, dbValidPaths, path, "");
+}
+
+
+bool isValidPath(const Path & path)
+{
+    string s;
+    return nixDB.queryString(noTxn, dbValidPaths, path, s);
+}
+
+
+void unregisterValidPath(const Path & _path)
+{
+    Path path(canonPath(_path));
+    Transaction txn(nixDB);
+
+    debug(format("unregistering path `%1%'") % path);
+
+    nixDB.delPair(txn, dbValidPaths, path);
+
+    txn.commit();
+}
+
+
+static bool isInPrefix(const string & path, const string & _prefix)
+{
+    string prefix = canonPath(_prefix + "/");
+    return string(path, 0, prefix.size()) == prefix;
+}
+
+
+Path addToStore(const Path & _srcPath)
+{
+    Path srcPath(absPath(_srcPath));
+    debug(format("adding `%1%' to the store") % srcPath);
+
+    Hash h = hashPath(srcPath);
+
+    string baseName = baseNameOf(srcPath);
+    Path dstPath = canonPath(nixStore + "/" + (string) h + "-" + baseName);
+
+    if (!isValidPath(dstPath)) { 
+
+        /* The first check above is an optimisation to prevent
+           unnecessary lock acquisition. */
+
+        PathSet lockPaths;
+        lockPaths.insert(dstPath);
+        PathLocks outputLock(lockPaths);
+
+        if (!isValidPath(dstPath)) {
+            copyPath(srcPath, dstPath);
+
+            Transaction txn(nixDB);
+            registerValidPath(txn, dstPath);
+            txn.commit();
+        }
+    }
+
+    return dstPath;
+}
+
+
+void addTextToStore(const Path & dstPath, const string & s)
+{
+    if (!isValidPath(dstPath)) {
+
+        PathSet lockPaths;
+        lockPaths.insert(dstPath);
+        PathLocks outputLock(lockPaths);
+
+        if (!isValidPath(dstPath)) {
+
+            AutoCloseFD fd = open(dstPath.c_str(), O_CREAT | O_EXCL | O_WRONLY, 0666);
+            if (fd == -1) throw SysError(format("creating store file `%1%'") % dstPath);
+
+            writeFull(fd, (unsigned char *) s.c_str(), s.size());
+
+            Transaction txn(nixDB);
+            registerValidPath(txn, dstPath);
+            txn.commit();
+        }
+    }
+}
+
+
+void deleteFromStore(const Path & _path)
+{
+    Path path(canonPath(_path));
+
+    if (!isInPrefix(path, nixStore))
+        throw Error(format("path `%1%' is not in the store") % path);
+
+    unregisterValidPath(path);
+
+    deletePath(path);
+}
+
+
+void verifyStore()
+{
+    Transaction txn(nixDB);
+
+    Paths paths;
+    nixDB.enumTable(txn, dbValidPaths, paths);
+
+    for (Paths::iterator i = paths.begin();
+         i != paths.end(); i++)
+    {
+        Path path = *i;
+        if (!pathExists(path)) {
+            debug(format("path `%1%' disappeared") % path);
+            nixDB.delPair(txn, dbValidPaths, path);
+            nixDB.delPair(txn, dbSuccessorsRev, path);
+            nixDB.delPair(txn, dbSubstitutesRev, path);
+        }
+    }
+
+#if 0    
+    Strings subs;
+    nixDB.enumTable(txn, dbSubstitutes, subs);
+
+    for (Strings::iterator i = subs.begin();
+         i != subs.end(); i++)
+    {
+        FSId srcId = parseHash(*i);
+
+        Strings subIds;
+        nixDB.queryStrings(txn, dbSubstitutes, srcId, subIds);
+
+        for (Strings::iterator j = subIds.begin();     
+             j != subIds.end(); )
+        {
+            FSId subId = parseHash(*j);
+            
+            Strings subPaths;
+            nixDB.queryStrings(txn, dbId2Paths, subId, subPaths);
+            if (subPaths.size() == 0) {
+                debug(format("erasing substitute %1% for %2%") 
+                    % (string) subId % (string) srcId);
+                j = subIds.erase(j);
+            } else j++;
+        }
+
+        nixDB.setStrings(txn, dbSubstitutes, srcId, subIds);
+    }
+#endif
+
+    Paths sucs;
+    nixDB.enumTable(txn, dbSuccessors, sucs);
+
+    for (Paths::iterator i = sucs.begin(); i != sucs.end(); i++) {
+        Path srcPath = *i;
+
+        Path sucPath;
+        if (!nixDB.queryString(txn, dbSuccessors, srcPath, sucPath)) abort();
+
+        Paths revs;
+        nixDB.queryStrings(txn, dbSuccessorsRev, sucPath, revs);
+
+        if (find(revs.begin(), revs.end(), srcPath) == revs.end()) {
+            debug(format("reverse successor mapping from `%1%' to `%2%' missing")
+                  % srcPath % sucPath);
+            revs.push_back(srcPath);
+            nixDB.setStrings(txn, dbSuccessorsRev, sucPath, revs);
+        }
+    }
+
+    txn.commit();
+}
diff --git a/src/libstore/store.hh b/src/libstore/store.hh
new file mode 100644
index 000000000000..dab3d603f802
--- /dev/null
+++ b/src/libstore/store.hh
@@ -0,0 +1,72 @@
+#ifndef __STORE_H
+#define __STORE_H
+
+#include <string>
+
+#include "hash.hh"
+#include "db.hh"
+
+using namespace std;
+
+
+/* Open the database environment. */
+void openDB();
+
+/* Create the required database tables. */
+void initDB();
+
+/* Get a transaction object. */
+void createStoreTransaction(Transaction & txn);
+
+/* Copy a path recursively. */
+void copyPath(const Path & src, const Path & dst);
+
+/* Register a successor.  This function accepts a transaction handle
+   so that it can be enclosed in an atomic operation with calls to
+   registerValidPath().  This must be atomic, since if we register a
+   successor for a derivation without registering the paths built in
+   the derivation, we have a successor with dangling pointers, and if
+   we do it in reverse order, we can get an obstructed build (since to
+   rebuild the successor, the outputs paths must not exist). */
+void registerSuccessor(const Transaction & txn,
+    const Path & srcPath, const Path & sucPath);
+
+/* Return the predecessors of the Nix expression stored at the given
+   path. */
+bool querySuccessor(const Path & srcPath, Path & sucPath);
+
+/* Return the predecessors of the Nix expression stored at the given
+   path. */
+Paths queryPredecessors(const Path & sucPath);
+
+/* Register a substitute. */
+void registerSubstitute(const Path & srcPath, const Path & subPath);
+
+/* Return the substitutes expression for the given path. */
+Paths querySubstitutes(const Path & srcPath);
+
+/* Register the validity of a path. */
+void registerValidPath(const Transaction & txn, const Path & path);
+
+/* Unregister the validity of a path. */
+void unregisterValidPath(const Path & path);
+
+/* Checks whether a path is valid. */ 
+bool isValidPath(const Path & path);
+
+/* Copy the contents of a path to the store and register the validity
+   the resulting path.  The resulting path is returned. */
+Path addToStore(const Path & srcPath);
+
+/* Like addToStore, but the path of the output is given, and the
+   contents written to the output path is a regular file containing
+   the given string. */
+void addTextToStore(const Path & dstPath, const string & s);
+
+/* Delete a value from the nixStore directory. */
+void deleteFromStore(const Path & path);
+
+void verifyStore();
+
+
+#endif /* !__STORE_H */
diff --git a/src/libstore/test-builder-1.sh b/src/libstore/test-builder-1.sh
new file mode 100755
index 000000000000..80e23354c3b9
--- /dev/null
+++ b/src/libstore/test-builder-1.sh
@@ -0,0 +1,3 @@
+#! /bin/sh
+
+echo "Hello World" > $out
diff --git a/src/libstore/test-builder-2.sh b/src/libstore/test-builder-2.sh
new file mode 100755
index 000000000000..0794fa96a401
--- /dev/null
+++ b/src/libstore/test-builder-2.sh
@@ -0,0 +1,9 @@
+#! /bin/sh
+
+echo "builder 2"
+
+/bin/mkdir $out || exit 1
+cd $out || exit 1
+echo "Hallo Wereld" > bla
+echo $builder >> bla
+echo $out >> bla
diff --git a/src/libstore/test.cc b/src/libstore/test.cc
new file mode 100644
index 000000000000..457fecf245f0
--- /dev/null
+++ b/src/libstore/test.cc
@@ -0,0 +1,162 @@
+#include <iostream>
+
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include "hash.hh"
+#include "archive.hh"
+#include "util.hh"
+#include "normalise.hh"
+#include "globals.hh"
+
+
+void realise(Path nePath)
+{
+    Nest nest(lvlDebug, format("TEST: realising `%1%'") % nePath);
+    realiseClosure(normaliseNixExpr(nePath));
+}
+
+
+struct MySink : DumpSink
+{
+    virtual void operator () (const unsigned char * data, unsigned int len)
+    {
+        /* Don't use cout, it's slow as hell! */
+        writeFull(STDOUT_FILENO, data, len);
+    }
+};
+
+
+struct MySource : RestoreSource
+{
+    virtual void operator () (unsigned char * data, unsigned int len)
+    {
+        readFull(STDIN_FILENO, data, len);
+    }
+};
+
+
+void runTests()
+{
+    verbosity = (Verbosity) 100;
+
+    /* Hashing. */
+    string s = "0b0ffd0538622bfe20b92c4aa57254d9";
+    Hash h = parseHash(s);
+    if ((string) h != s) abort();
+
+    try {
+        h = parseHash("blah blah");
+        abort();
+    } catch (Error err) { };
+
+    try {
+        h = parseHash("0b0ffd0538622bfe20b92c4aa57254d99");
+        abort();
+    } catch (Error err) { };
+
+    /* Path canonicalisation. */
+    cout << canonPath("/./../././//") << endl;
+    cout << canonPath("/foo/bar") << endl;
+    cout << canonPath("///foo/////bar//") << endl;
+    cout << canonPath("/././/foo/////bar//.") << endl;
+    cout << canonPath("/foo////bar//..///x/") << endl;
+    cout << canonPath("/foo////bar//..//..//x/y/../z/") << endl;
+    cout << canonPath("/foo/bar/../../../..///") << endl;
+
+    /* Dumping. */
+
+#if 0
+    MySink sink;
+    dumpPath("scratch", sink);
+    cout << (string) hashPath("scratch") << endl;
+#endif
+
+    /* Restoring. */
+#if 0
+    MySource source;
+    restorePath("outdir", source);
+    cout << (string) hashPath("outdir") << endl;
+    return;
+#endif
+
+    /* Set up the test environment. */
+
+    mkdir("scratch", 0777);
+    mkdir("scratch/db", 0777);
+
+    string testDir = absPath("scratch");
+    cout << testDir << endl;
+
+    nixStore = testDir;
+    nixLogDir = testDir;
+    nixDBPath = testDir + "/db";
+
+    openDB();
+    initDB();
+
+    /* Expression evaluation. */
+
+    Path builder1fn;
+    builder1fn = addToStore("./test-builder-1.sh");
+
+    ATerm fs1 = ATmake(
+        "Closure([<str>], [(<str>, [])])",
+        builder1fn.c_str(),
+        builder1fn.c_str());
+    Path fs1ne = writeTerm(fs1, "-c");
+
+    realise(fs1ne);
+    realise(fs1ne);
+
+    string out1h = hashString("foo"); /* !!! bad */
+    Path out1fn = nixStore + "/" + (string) out1h + "-hello.txt";
+    ATerm fs3 = ATmake(
+        "Derive([<str>], [<str>], <str>, <str>, [], [(\"out\", <str>)])",
+        out1fn.c_str(),
+        fs1ne.c_str(),
+        thisSystem.c_str(),
+        builder1fn.c_str(),
+        out1fn.c_str());
+    debug(printTerm(fs3));
+    Path fs3ne = writeTerm(fs3, "-d");
+
+    realise(fs3ne);
+    realise(fs3ne);
+
+
+    Path builder4fn = addToStore("./test-builder-2.sh");
+
+    ATerm fs4 = ATmake(
+        "Closure([<str>], [(<str>, [])])",
+        builder4fn.c_str(),
+        builder4fn.c_str());
+    Path fs4ne = writeTerm(fs4, "-c");
+
+    realise(fs4ne);
+
+    string out5h = hashString("bar"); /* !!! bad */
+    Path out5fn = nixStore + "/" + (string) out5h + "-hello2";
+    ATerm fs5 = ATmake(
+        "Derive([<str>], [<str>], <str>, <str>, [], [(\"out\", <str>), (\"builder\", <str>)])",
+        out5fn.c_str(),
+        fs4ne.c_str(),
+        thisSystem.c_str(),
+        builder4fn.c_str(),
+        out5fn.c_str(),
+        builder4fn.c_str());
+    debug(printTerm(fs5));
+    Path fs5ne = writeTerm(fs5, "-d");
+
+    realise(fs5ne);
+    realise(fs5ne);
+}
+
+
+void run(Strings args)
+{
+    runTests();
+}
+
+
+string programId = "test";