* Refactored the source tree.

27 files changed, 3947 insertions, 0 deletions

diff --git a/src/libnix/archive.cc b/src/libnix/archive.cc
new file mode 100644
index 000000000000..9039ad7db43e
--- /dev/null
+++ b/src/libnix/archive.cc
@@ -0,0 +1,340 @@
+#include <cerrno>
+#include <algorithm>
+#include <vector>
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+#include <dirent.h>
+#include <fcntl.h>
+
+#include "archive.hh"
+#include "util.hh"
+
+
+static string archiveVersion1 = "nix-archive-1";
+
+
+static void writePadding(unsigned int len, DumpSink & sink)
+{
+    if (len % 8) {
+        unsigned char zero[8];
+        memset(zero, 0, sizeof(zero));
+        sink(zero, 8 - (len % 8));
+    }
+}
+
+
+static void writeInt(unsigned int n, DumpSink & sink)
+{
+    unsigned char buf[8];
+    memset(buf, 0, sizeof(buf));
+    buf[0] = n & 0xff;
+    buf[1] = (n >> 8) & 0xff;
+    buf[2] = (n >> 16) & 0xff;
+    buf[3] = (n >> 24) & 0xff;
+    sink(buf, sizeof(buf));
+}
+
+
+static void writeString(const string & s, DumpSink & sink)
+{
+    unsigned int len = s.length();
+    writeInt(len, sink);
+    sink((const unsigned char *) s.c_str(), len);
+    writePadding(len, sink);
+}
+
+
+static void dump(const string & path, DumpSink & sink);
+
+
+static void dumpEntries(const Path & path, DumpSink & sink)
+{
+    DIR * dir = opendir(path.c_str());
+    if (!dir) throw SysError("opening directory " + path);
+
+    vector<string> names;
+
+    struct dirent * dirent;
+    while (errno = 0, dirent = readdir(dir)) {
+        string name = dirent->d_name;
+        if (name == "." || name == "..") continue;
+        names.push_back(name);
+    }
+    if (errno) throw SysError("reading directory " + path);
+
+    sort(names.begin(), names.end());
+
+    for (vector<string>::iterator it = names.begin();
+         it != names.end(); it++)
+    {
+        writeString("entry", sink);
+        writeString("(", sink);
+        writeString("name", sink);
+        writeString(*it, sink);
+        writeString("node", sink);
+        dump(path + "/" + *it, sink);
+        writeString(")", sink);
+    }
+    
+    closedir(dir); /* !!! close on exception */
+}
+
+
+static void dumpContents(const Path & path, unsigned int size, 
+    DumpSink & sink)
+{
+    writeString("contents", sink);
+    writeInt(size, sink);
+
+    int fd = open(path.c_str(), O_RDONLY);
+    if (fd == -1) throw SysError(format("opening file `%1%'") % path);
+    
+    unsigned char buf[65536];
+
+    unsigned int total = 0;
+    ssize_t n;
+    while ((n = read(fd, buf, sizeof(buf)))) {
+        if (n == -1) throw SysError("reading file " + path);
+        total += n;
+        sink(buf, n);
+    }
+
+    if (total != size)
+        throw SysError("file changed while reading it: " + path);
+
+    writePadding(size, sink);
+
+    close(fd); /* !!! close on exception */
+}
+
+
+static void dump(const Path & path, DumpSink & sink)
+{
+    struct stat st;
+    if (lstat(path.c_str(), &st))
+        throw SysError(format("getting attributes of path `%1%'") % path);
+
+    writeString("(", sink);
+
+    if (S_ISREG(st.st_mode)) {
+        writeString("type", sink);
+        writeString("regular", sink);
+        if (st.st_mode & S_IXUSR) {
+            writeString("executable", sink);
+            writeString("", sink);
+        }
+        dumpContents(path, st.st_size, sink);
+    } 
+
+    else if (S_ISDIR(st.st_mode)) {
+        writeString("type", sink);
+        writeString("directory", sink);
+        dumpEntries(path, sink);
+    }
+
+    else if (S_ISLNK(st.st_mode)) {
+        writeString("type", sink);
+        writeString("symlink", sink);
+        char buf[st.st_size];
+        if (readlink(path.c_str(), buf, st.st_size) != st.st_size)
+            throw SysError("reading symbolic link " + path);
+        writeString("target", sink);
+        writeString(string(buf, st.st_size), sink);
+    }
+
+    else throw Error("unknown file type: " + path);
+
+    writeString(")", sink);
+}
+
+
+void dumpPath(const Path & path, DumpSink & sink)
+{
+    writeString(archiveVersion1, sink);
+    dump(path, sink);
+}
+
+
+static Error badArchive(string s)
+{
+    return Error("bad archive: " + s);
+}
+
+
+static void readPadding(unsigned int len, RestoreSource & source)
+{
+    if (len % 8) {
+        unsigned char zero[8];
+        unsigned int n = 8 - (len % 8);
+        source(zero, n);
+        for (unsigned int i = 0; i < n; i++)
+            if (zero[i]) throw badArchive("non-zero padding");
+    }
+}
+
+static unsigned int readInt(RestoreSource & source)
+{
+    unsigned char buf[8];
+    source(buf, sizeof(buf));
+    if (buf[4] || buf[5] || buf[6] || buf[7])
+        throw Error("implementation cannot deal with > 32-bit integers");
+    return
+        buf[0] |
+        (buf[1] << 8) |
+        (buf[2] << 16) |
+        (buf[3] << 24);
+}
+
+
+static string readString(RestoreSource & source)
+{
+    unsigned int len = readInt(source);
+    char buf[len];
+    source((unsigned char *) buf, len);
+    readPadding(len, source);
+    return string(buf, len);
+}
+
+
+static void skipGeneric(RestoreSource & source)
+{
+    if (readString(source) == "(") {
+        while (readString(source) != ")")
+            skipGeneric(source);
+    }
+}
+
+
+static void restore(const Path & path, RestoreSource & source);
+
+
+static void restoreEntry(const Path & path, RestoreSource & source)
+{
+    string s, name;
+
+    s = readString(source);
+    if (s != "(") throw badArchive("expected open tag");
+
+    while (1) {
+        s = readString(source);
+
+        if (s == ")") {
+            break;
+        } else if (s == "name") {
+            name = readString(source);
+        } else if (s == "node") {
+            if (s == "") throw badArchive("entry name missing");
+            restore(path + "/" + name, source);
+        } else {
+            throw badArchive("unknown field " + s);
+            skipGeneric(source);
+        }
+    }
+}
+
+
+static void restoreContents(int fd, const Path & path, RestoreSource & source)
+{
+    unsigned int size = readInt(source);
+    unsigned int left = size;
+    unsigned char buf[65536];
+
+    while (left) {
+        unsigned int n = sizeof(buf);
+        if (n > left) n = left;
+        source(buf, n);
+        if (write(fd, buf, n) != (ssize_t) n)
+            throw SysError("writing file " + path);
+        left -= n;
+    }
+
+    readPadding(size, source);
+}
+
+
+static void restore(const Path & path, RestoreSource & source)
+{
+    string s;
+
+    s = readString(source);
+    if (s != "(") throw badArchive("expected open tag");
+
+    enum { tpUnknown, tpRegular, tpDirectory, tpSymlink } type = tpUnknown;
+    int fd = -1; /* !!! close on exception */
+
+    while (1) {
+        s = readString(source);
+
+        if (s == ")") {
+            break;
+        }
+
+        else if (s == "type") {
+            if (type != tpUnknown)
+                throw badArchive("multiple type fields");
+            string t = readString(source);
+
+            if (t == "regular") {
+                type = tpRegular;
+                fd = open(path.c_str(), O_CREAT | O_EXCL | O_WRONLY, 0666);
+                if (fd == -1)
+                    throw SysError("creating file " + path);
+            }
+
+            else if (t == "directory") {
+                type = tpDirectory;
+                if (mkdir(path.c_str(), 0777) == -1)
+                    throw SysError("creating directory " + path);
+            }
+
+            else if (t == "symlink") {
+                type = tpSymlink;
+            }
+            
+            else throw badArchive("unknown file type " + t);
+            
+        }
+
+        else if (s == "contents" && type == tpRegular) {
+            restoreContents(fd, path, source);
+        }
+
+        else if (s == "executable" && type == tpRegular) {
+            readString(source);
+            struct stat st;
+            if (fstat(fd, &st) == -1)
+                throw SysError("fstat");
+            if (fchmod(fd, st.st_mode | (S_IXUSR | S_IXGRP | S_IXOTH)) == -1)
+                throw SysError("fchmod");
+        }
+
+        else if (s == "entry" && type == tpDirectory) {
+            restoreEntry(path, source);
+        }
+
+        else if (s == "target" && type == tpSymlink) {
+            string target = readString(source);
+            if (symlink(target.c_str(), path.c_str()) == -1)
+                throw SysError("creating symlink " + path);
+        }
+
+        else {
+            throw badArchive("unknown field " + s);
+            skipGeneric(source);
+        }
+        
+    }
+
+    if (fd != -1) close(fd);
+}
+
+
+void restorePath(const Path & path, RestoreSource & source)
+{
+    if (readString(source) != archiveVersion1)
+        throw badArchive("expected Nix archive");
+    restore(path, source);
+}
+
diff --git a/src/libnix/archive.hh b/src/libnix/archive.hh
new file mode 100644
index 000000000000..67e236668a06
--- /dev/null
+++ b/src/libnix/archive.hh
@@ -0,0 +1,60 @@
+#include <string>
+
+#include "util.hh"
+
+
+/* dumpPath creates a Nix archive of the specified path.  The format
+   is as follows:
+
+   IF path points to a REGULAR FILE:
+     dump(path) = attrs(
+       [ ("type", "regular")
+       , ("contents", contents(path))
+       ])
+
+   IF path points to a DIRECTORY:
+     dump(path) = attrs(
+       [ ("type", "directory")
+       , ("entries", concat(map(f, sort(entries(path)))))
+       ])
+       where f(fn) = attrs(
+         [ ("name", fn)
+         , ("file", dump(path + "/" + fn))
+         ])
+
+   where:
+
+     attrs(as) = concat(map(attr, as)) + encN(0) 
+     attrs((a, b)) = encS(a) + encS(b)
+
+     encS(s) = encN(len(s)) + s + (padding until next 64-bit boundary)
+
+     encN(n) = 64-bit little-endian encoding of n.
+
+     contents(path) = the contents of a regular file.
+
+     sort(strings) = lexicographic sort by 8-bit value (strcmp).
+
+     entries(path) = the entries of a directory, without `.' and
+     `..'.
+
+     `+' denotes string concatenation. */
+
+struct DumpSink 
+{
+    virtual void operator () (const unsigned char * data, unsigned int len) = 0;
+};
+
+void dumpPath(const Path & path, DumpSink & sink);
+
+
+struct RestoreSource
+{
+    /* The callee should store exactly *len bytes in the buffer
+       pointed to by data.  It should block if that much data is not
+       yet available, or throw an error if it is not going to be
+       available. */
+    virtual void operator () (unsigned char * data, unsigned int len) = 0;
+};
+
+void restorePath(const Path & path, RestoreSource & source);
diff --git a/src/libnix/db.cc b/src/libnix/db.cc
new file mode 100644
index 000000000000..2f53ca3b5231
--- /dev/null
+++ b/src/libnix/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) {
+                msg(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++)
+        {
+            debug(format("closing table %1%") % i->first);
+            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/libnix/db.hh b/src/libnix/db.hh
new file mode 100644
index 000000000000..1c681b9b5419
--- /dev/null
+++ b/src/libnix/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/libnix/exec.cc b/src/libnix/exec.cc
new file mode 100644
index 000000000000..2e092b2e0dd6
--- /dev/null
+++ b/src/libnix/exec.cc
@@ -0,0 +1,144 @@
+#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"
+
+
+class AutoDelete
+{
+    string path;
+    bool del;
+public:
+
+    AutoDelete(const string & p) : path(p) 
+    {
+        del = true;
+    }
+
+    ~AutoDelete()
+    {
+        if (del) deletePath(path);
+    }
+
+    void cancel()
+    {
+        del = false;
+    }
+};
+
+
+static string pathNullDevice = "/dev/null";
+
+
+/* Run a program. */
+void runProgram(const string & program, 
+    const Strings & args, const Environment & env)
+{
+    /* Create a log file. */
+    string logFileName = nixLogDir + "/run.log";
+    string logCommand = 
+	verbosity >= lvlDebug 
+	? "tee -a "  + 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) {
+	    msg(lvlTalkative, 
+		format("build failed; keeping build directory `%1%'") % tmpDir);
+	    delTmpDir.cancel();
+	}
+        throw Error("unable to build package");
+    }
+}
+
+
diff --git a/src/libnix/exec.hh b/src/libnix/exec.hh
new file mode 100644
index 000000000000..8d410e404383
--- /dev/null
+++ b/src/libnix/exec.hh
@@ -0,0 +1,21 @@
+#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);
+
+
+#endif /* !__EXEC_H */
diff --git a/src/libnix/expr.cc b/src/libnix/expr.cc
new file mode 100644
index 000000000000..cead803425ba
--- /dev/null
+++ b/src/libnix/expr.cc
@@ -0,0 +1,222 @@
+#include "expr.hh"
+#include "globals.hh"
+#include "store.hh"
+
+
+string printTerm(ATerm t)
+{
+    char * s = ATwriteToString(t);
+    return s;
+}
+
+
+Error badTerm(const format & f, ATerm t)
+{
+    return Error(format("%1%, in `%2%'") % f.str() % printTerm(t));
+}
+
+
+Hash hashTerm(ATerm t)
+{
+    return hashString(printTerm(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)
+{
+    while (!ATisEmpty(paths)) {
+        char * s;
+        ATerm t = ATgetFirst(paths);
+        if (!ATmatch(t, "<str>", &s))
+            throw badTerm("not a path", t);
+        out.insert(s);
+        paths = ATgetNext(paths);
+    }
+}
+
+
+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;
+    
+    if (!ATmatch(t, "Closure([<list>], [<list>])", &roots, &elems))
+        return false;
+
+    parsePaths(roots, closure.roots);
+
+    while (!ATisEmpty(elems)) {
+        char * s1;
+        ATermList refs;
+        ATerm t = ATgetFirst(elems);
+        if (!ATmatch(t, "(<str>, [<list>])", &s1, &refs))
+            throw badTerm("not a closure element", t);
+        ClosureElem elem;
+        parsePaths(refs, elem.refs);
+        closure.elems[s1] = elem;
+        elems = ATgetNext(elems);
+    }
+
+    checkClosure(closure);
+    return true;
+}
+
+
+static bool parseDerivation(ATerm t, Derivation & derivation)
+{
+    ATermList outs, ins, args, bnds;
+    char * builder;
+    char * platform;
+
+    if (!ATmatch(t, "Derive([<list>], [<list>], <str>, <str>, [<list>], [<list>])",
+            &outs, &ins, &platform, &builder, &args, &bnds))
+    {
+        /* !!! compatibility -> remove eventually */
+        if (!ATmatch(t, "Derive([<list>], [<list>], <str>, <str>, [<list>])",
+                &outs, &ins, &builder, &platform, &bnds))
+            return false;
+        args = ATempty;
+    }
+
+    parsePaths(outs, derivation.outputs);
+    parsePaths(ins, derivation.inputs);
+
+    derivation.builder = builder;
+    derivation.platform = platform;
+    
+    while (!ATisEmpty(args)) {
+        char * s;
+        ATerm arg = ATgetFirst(args);
+        if (!ATmatch(arg, "<str>", &s))
+            throw badTerm("string expected", arg);
+        derivation.args.push_back(s);
+        args = ATgetNext(args);
+    }
+
+    while (!ATisEmpty(bnds)) {
+        char * s1, * s2;
+        ATerm bnd = ATgetFirst(bnds);
+        if (!ATmatch(bnd, "(<str>, <str>)", &s1, &s2))
+            throw badTerm("tuple of strings expected", bnd);
+        derivation.env[s1] = s2;
+        bnds = ATgetNext(bnds);
+    }
+
+    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/libnix/expr.hh b/src/libnix/expr.hh
new file mode 100644
index 000000000000..7d0420935f9d
--- /dev/null
+++ b/src/libnix/expr.hh
@@ -0,0 +1,66 @@
+#ifndef __FSTATE_H
+#define __FSTATE_H
+
+extern "C" {
+#include <aterm2.h>
+}
+
+#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;
+};
+
+
+/* Return a canonical textual representation of an expression. */
+string printTerm(ATerm t);
+
+/* 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/libnix/globals.cc b/src/libnix/globals.cc
new file mode 100644
index 000000000000..a292b49aeae0
--- /dev/null
+++ b/src/libnix/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/libnix/globals.hh b/src/libnix/globals.hh
new file mode 100644
index 000000000000..1b4d0bde3ffe
--- /dev/null
+++ b/src/libnix/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/libnix/hash.cc b/src/libnix/hash.cc
new file mode 100644
index 000000000000..752b269125cb
--- /dev/null
+++ b/src/libnix/hash.cc
@@ -0,0 +1,124 @@
+#include <iostream>
+
+extern "C" {
+#include "md5.h"
+}
+
+#include "hash.hh"
+#include "archive.hh"
+
+
+Hash::Hash()
+{
+    memset(hash, 0, sizeof(hash));
+}
+
+
+bool Hash::operator == (const Hash & h2) const
+{
+    for (unsigned int i = 0; i < hashSize; i++)
+        if (hash[i] != h2.hash[i]) return false;
+    return true;
+}
+
+
+bool Hash::operator != (const Hash & h2) const
+{
+    return !(*this == h2);
+}
+
+
+bool Hash::operator < (const Hash & h) const
+{
+    for (unsigned int i = 0; i < hashSize; i++) {
+        if (hash[i] < h.hash[i]) return true;
+        if (hash[i] > h.hash[i]) return false;
+    }
+    return false;
+}
+
+
+Hash::operator string() const
+{
+    ostringstream str;
+    for (unsigned int i = 0; i < hashSize; i++) {
+        str.fill('0');
+        str.width(2);
+        str << hex << (int) hash[i];
+    }
+    return str.str();
+}
+
+    
+Hash parseHash(const string & s)
+{
+    Hash hash;
+    if (s.length() != Hash::hashSize * 2)
+        throw Error(format("invalid hash `%1%'") % s);
+    for (unsigned int i = 0; i < Hash::hashSize; i++) {
+        string s2(s, i * 2, 2);
+        if (!isxdigit(s2[0]) || !isxdigit(s2[1])) 
+            throw Error(format("invalid hash `%1%'") % s);
+        istringstream str(s2);
+        int n;
+        str >> hex >> n;
+        hash.hash[i] = n;
+    }
+    return hash;
+}
+
+
+bool isHash(const string & s)
+{
+    if (s.length() != 32) return false;
+    for (int i = 0; i < 32; i++) {
+        char c = s[i];
+        if (!((c >= '0' && c <= '9') ||
+              (c >= 'a' && c <= 'f')))
+            return false;
+    }
+    return true;
+}
+
+
+Hash hashString(const string & s)
+{
+    Hash hash;
+    md5_buffer(s.c_str(), s.length(), hash.hash);
+    return hash;
+}
+
+
+Hash hashFile(const Path & path)
+{
+    Hash hash;
+    FILE * file = fopen(path.c_str(), "rb");
+    if (!file)
+        throw SysError(format("file `%1%' does not exist") % path);
+    int err = md5_stream(file, hash.hash);
+    fclose(file);
+    if (err) throw SysError(format("cannot hash file `%1%'") % path);
+    return hash;
+}
+
+
+struct HashSink : DumpSink
+{
+    struct md5_ctx ctx;
+    virtual void operator ()
+        (const unsigned char * data, unsigned int len)
+    {
+        md5_process_bytes(data, len, &ctx);
+    }
+};
+
+
+Hash hashPath(const Path & path)
+{
+    Hash hash;
+    HashSink sink;
+    md5_init_ctx(&sink.ctx);
+    dumpPath(path, sink);
+    md5_finish_ctx(&sink.ctx, hash.hash);
+    return hash;
+}
diff --git a/src/libnix/hash.hh b/src/libnix/hash.hh
new file mode 100644
index 000000000000..0062f987c021
--- /dev/null
+++ b/src/libnix/hash.hh
@@ -0,0 +1,51 @@
+#ifndef __HASH_H
+#define __HASH_H
+
+#include <string>
+
+#include "util.hh"
+
+using namespace std;
+
+
+struct Hash
+{
+    static const unsigned int hashSize = 16;
+    unsigned char hash[hashSize];
+
+    /* Create a zeroed hash object. */
+    Hash();
+
+    /* Check whether two hash are equal. */
+    bool operator == (const Hash & h2) const;
+
+    /* Check whether two hash are not equal. */
+    bool operator != (const Hash & h2) const;
+
+    /* For sorting. */
+    bool operator < (const Hash & h) const;
+
+    /* Convert a hash code into a hexadecimal representation. */
+    operator string() const;
+};
+
+
+/* Parse a hexadecimal representation of a hash code. */
+Hash parseHash(const string & s);
+
+/* Verify that the given string is a valid hash code. */
+bool isHash(const string & s);
+
+/* Compute the hash of the given string. */
+Hash hashString(const string & s);
+
+/* Compute the hash of the given file. */
+Hash hashFile(const Path & path);
+
+/* Compute the hash of the given path.  The hash is defined as
+   md5(dump(path)).
+*/
+Hash hashPath(const Path & path);
+
+
+#endif /* !__HASH_H */
diff --git a/src/libnix/md5.c b/src/libnix/md5.c
new file mode 100644
index 000000000000..fa67ebfcdbdf
--- /dev/null
+++ b/src/libnix/md5.c
@@ -0,0 +1,448 @@
+/* Functions to compute MD5 message digest of files or memory blocks.
+   according to the definition of MD5 in RFC 1321 from April 1992.
+   Copyright (C) 1995,1996,1997,1999,2000,2001 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+   02111-1307 USA.  */
+
+/* Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <sys/types.h>
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "md5.h"
+
+
+static md5_uint32 SWAP(md5_uint32 n)
+{
+  static int checked = 0;
+  static int bigendian = 0;
+  static md5_uint32 test;
+
+  if (!checked) {
+    test = 1;
+    if (* (char *) &test == 0)
+      bigendian = 1;
+    checked = 1;
+  }
+
+  if (bigendian)
+    return (((n) << 24) | (((n) & 0xff00) << 8) | (((n) >> 8) & 0xff00) | ((n) >> 24));
+  else
+    return n;
+}
+
+
+/* This array contains the bytes used to pad the buffer to the next
+   64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
+static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
+
+
+/* Initialize structure containing state of computation.
+   (RFC 1321, 3.3: Step 3)  */
+void
+md5_init_ctx (ctx)
+     struct md5_ctx *ctx;
+{
+  ctx->A = 0x67452301;
+  ctx->B = 0xefcdab89;
+  ctx->C = 0x98badcfe;
+  ctx->D = 0x10325476;
+
+  ctx->total[0] = ctx->total[1] = 0;
+  ctx->buflen = 0;
+}
+
+/* Put result from CTX in first 16 bytes following RESBUF.  The result
+   must be in little endian byte order.
+
+   IMPORTANT: On some systems it is required that RESBUF is correctly
+   aligned for a 32 bits value.  */
+void *
+md5_read_ctx (ctx, resbuf)
+     const struct md5_ctx *ctx;
+     void *resbuf;
+{
+  ((md5_uint32 *) resbuf)[0] = SWAP (ctx->A);
+  ((md5_uint32 *) resbuf)[1] = SWAP (ctx->B);
+  ((md5_uint32 *) resbuf)[2] = SWAP (ctx->C);
+  ((md5_uint32 *) resbuf)[3] = SWAP (ctx->D);
+
+  return resbuf;
+}
+
+/* Process the remaining bytes in the internal buffer and the usual
+   prolog according to the standard and write the result to RESBUF.
+
+   IMPORTANT: On some systems it is required that RESBUF is correctly
+   aligned for a 32 bits value.  */
+void *
+md5_finish_ctx (ctx, resbuf)
+     struct md5_ctx *ctx;
+     void *resbuf;
+{
+  /* Take yet unprocessed bytes into account.  */
+  md5_uint32 bytes = ctx->buflen;
+  size_t pad;
+
+  /* Now count remaining bytes.  */
+  ctx->total[0] += bytes;
+  if (ctx->total[0] < bytes)
+    ++ctx->total[1];
+
+  pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
+  memcpy (&ctx->buffer[bytes], fillbuf, pad);
+
+  /* Put the 64-bit file length in *bits* at the end of the buffer.  */
+  *(md5_uint32 *) &ctx->buffer[bytes + pad] = SWAP (ctx->total[0] << 3);
+  *(md5_uint32 *) &ctx->buffer[bytes + pad + 4] = SWAP ((ctx->total[1] << 3) |
+							(ctx->total[0] >> 29));
+
+  /* Process last bytes.  */
+  md5_process_block (ctx->buffer, bytes + pad + 8, ctx);
+
+  return md5_read_ctx (ctx, resbuf);
+}
+
+/* Compute MD5 message digest for bytes read from STREAM.  The
+   resulting message digest number will be written into the 16 bytes
+   beginning at RESBLOCK.  */
+int
+md5_stream (stream, resblock)
+     FILE *stream;
+     void *resblock;
+{
+  /* Important: BLOCKSIZE must be a multiple of 64.  */
+#define BLOCKSIZE 4096
+  struct md5_ctx ctx;
+  char buffer[BLOCKSIZE + 72];
+  size_t sum;
+
+  /* Initialize the computation context.  */
+  md5_init_ctx (&ctx);
+
+  /* Iterate over full file contents.  */
+  while (1)
+    {
+      /* We read the file in blocks of BLOCKSIZE bytes.  One call of the
+	 computation function processes the whole buffer so that with the
+	 next round of the loop another block can be read.  */
+      size_t n;
+      sum = 0;
+
+      /* Read block.  Take care for partial reads.  */
+      do
+	{
+	  n = fread (buffer + sum, 1, BLOCKSIZE - sum, stream);
+
+	  sum += n;
+	}
+      while (sum < BLOCKSIZE && n != 0);
+      if (n == 0 && ferror (stream))
+        return 1;
+
+      /* If end of file is reached, end the loop.  */
+      if (n == 0)
+	break;
+
+      /* Process buffer with BLOCKSIZE bytes.  Note that
+			BLOCKSIZE % 64 == 0
+       */
+      md5_process_block (buffer, BLOCKSIZE, &ctx);
+    }
+
+  /* Add the last bytes if necessary.  */
+  if (sum > 0)
+    md5_process_bytes (buffer, sum, &ctx);
+
+  /* Construct result in desired memory.  */
+  md5_finish_ctx (&ctx, resblock);
+  return 0;
+}
+
+/* Compute MD5 message digest for LEN bytes beginning at BUFFER.  The
+   result is always in little endian byte order, so that a byte-wise
+   output yields to the wanted ASCII representation of the message
+   digest.  */
+void *
+md5_buffer (buffer, len, resblock)
+     const char *buffer;
+     size_t len;
+     void *resblock;
+{
+  struct md5_ctx ctx;
+
+  /* Initialize the computation context.  */
+  md5_init_ctx (&ctx);
+
+  /* Process whole buffer but last len % 64 bytes.  */
+  md5_process_bytes (buffer, len, &ctx);
+
+  /* Put result in desired memory area.  */
+  return md5_finish_ctx (&ctx, resblock);
+}
+
+
+void
+md5_process_bytes (buffer, len, ctx)
+     const void *buffer;
+     size_t len;
+     struct md5_ctx *ctx;
+{
+  /* When we already have some bits in our internal buffer concatenate
+     both inputs first.  */
+  if (ctx->buflen != 0)
+    {
+      size_t left_over = ctx->buflen;
+      size_t add = 128 - left_over > len ? len : 128 - left_over;
+
+      memcpy (&ctx->buffer[left_over], buffer, add);
+      ctx->buflen += add;
+
+      if (ctx->buflen > 64)
+	{
+	  md5_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
+
+	  ctx->buflen &= 63;
+	  /* The regions in the following copy operation cannot overlap.  */
+	  memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
+		  ctx->buflen);
+	}
+
+      buffer = (const char *) buffer + add;
+      len -= add;
+    }
+
+  /* Process available complete blocks.  */
+  if (len >= 64)
+    {
+#if !_STRING_ARCH_unaligned
+/* To check alignment gcc has an appropriate operator.  Other
+   compilers don't.  */
+# if __GNUC__ >= 2
+#  define UNALIGNED_P(p) (((md5_uintptr) p) % __alignof__ (md5_uint32) != 0)
+# else
+#  define UNALIGNED_P(p) (((md5_uintptr) p) % sizeof (md5_uint32) != 0)
+# endif
+      if (UNALIGNED_P (buffer))
+	while (len > 64)
+	  {
+	    md5_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
+	    buffer = (const char *) buffer + 64;
+	    len -= 64;
+	  }
+      else
+#endif
+	{
+	  md5_process_block (buffer, len & ~63, ctx);
+	  buffer = (const char *) buffer + (len & ~63);
+	  len &= 63;
+	}
+    }
+
+  /* Move remaining bytes in internal buffer.  */
+  if (len > 0)
+    {
+      size_t left_over = ctx->buflen;
+
+      memcpy (&ctx->buffer[left_over], buffer, len);
+      left_over += len;
+      if (left_over >= 64)
+	{
+	  md5_process_block (ctx->buffer, 64, ctx);
+	  left_over -= 64;
+	  memcpy (ctx->buffer, &ctx->buffer[64], left_over);
+	}
+      ctx->buflen = left_over;
+    }
+}
+
+
+/* These are the four functions used in the four steps of the MD5 algorithm
+   and defined in the RFC 1321.  The first function is a little bit optimized
+   (as found in Colin Plumbs public domain implementation).  */
+/* #define FF(b, c, d) ((b & c) | (~b & d)) */
+#define FF(b, c, d) (d ^ (b & (c ^ d)))
+#define FG(b, c, d) FF (d, b, c)
+#define FH(b, c, d) (b ^ c ^ d)
+#define FI(b, c, d) (c ^ (b | ~d))
+
+/* Process LEN bytes of BUFFER, accumulating context into CTX.
+   It is assumed that LEN % 64 == 0.  */
+
+void
+md5_process_block (buffer, len, ctx)
+     const void *buffer;
+     size_t len;
+     struct md5_ctx *ctx;
+{
+  md5_uint32 correct_words[16];
+  const md5_uint32 *words = buffer;
+  size_t nwords = len / sizeof (md5_uint32);
+  const md5_uint32 *endp = words + nwords;
+  md5_uint32 A = ctx->A;
+  md5_uint32 B = ctx->B;
+  md5_uint32 C = ctx->C;
+  md5_uint32 D = ctx->D;
+
+  /* First increment the byte count.  RFC 1321 specifies the possible
+     length of the file up to 2^64 bits.  Here we only compute the
+     number of bytes.  Do a double word increment.  */
+  ctx->total[0] += len;
+  if (ctx->total[0] < len)
+    ++ctx->total[1];
+
+  /* Process all bytes in the buffer with 64 bytes in each round of
+     the loop.  */
+  while (words < endp)
+    {
+      md5_uint32 *cwp = correct_words;
+      md5_uint32 A_save = A;
+      md5_uint32 B_save = B;
+      md5_uint32 C_save = C;
+      md5_uint32 D_save = D;
+
+      /* First round: using the given function, the context and a constant
+	 the next context is computed.  Because the algorithms processing
+	 unit is a 32-bit word and it is determined to work on words in
+	 little endian byte order we perhaps have to change the byte order
+	 before the computation.  To reduce the work for the next steps
+	 we store the swapped words in the array CORRECT_WORDS.  */
+
+#define OP(a, b, c, d, s, T)						\
+      do								\
+        {								\
+	  a += FF (b, c, d) + (*cwp++ = SWAP (*words)) + T;		\
+	  ++words;							\
+	  CYCLIC (a, s);						\
+	  a += b;							\
+        }								\
+      while (0)
+
+      /* It is unfortunate that C does not provide an operator for
+	 cyclic rotation.  Hope the C compiler is smart enough.  */
+#define CYCLIC(w, s) (w = (w << s) | (w >> (32 - s)))
+
+      /* Before we start, one word to the strange constants.
+	 They are defined in RFC 1321 as
+
+	 T[i] = (int) (4294967296.0 * fabs (sin (i))), i=1..64
+       */
+
+      /* Round 1.  */
+      OP (A, B, C, D,  7, 0xd76aa478);
+      OP (D, A, B, C, 12, 0xe8c7b756);
+      OP (C, D, A, B, 17, 0x242070db);
+      OP (B, C, D, A, 22, 0xc1bdceee);
+      OP (A, B, C, D,  7, 0xf57c0faf);
+      OP (D, A, B, C, 12, 0x4787c62a);
+      OP (C, D, A, B, 17, 0xa8304613);
+      OP (B, C, D, A, 22, 0xfd469501);
+      OP (A, B, C, D,  7, 0x698098d8);
+      OP (D, A, B, C, 12, 0x8b44f7af);
+      OP (C, D, A, B, 17, 0xffff5bb1);
+      OP (B, C, D, A, 22, 0x895cd7be);
+      OP (A, B, C, D,  7, 0x6b901122);
+      OP (D, A, B, C, 12, 0xfd987193);
+      OP (C, D, A, B, 17, 0xa679438e);
+      OP (B, C, D, A, 22, 0x49b40821);
+
+      /* For the second to fourth round we have the possibly swapped words
+	 in CORRECT_WORDS.  Redefine the macro to take an additional first
+	 argument specifying the function to use.  */
+#undef OP
+#define OP(f, a, b, c, d, k, s, T)					\
+      do 								\
+	{								\
+	  a += f (b, c, d) + correct_words[k] + T;			\
+	  CYCLIC (a, s);						\
+	  a += b;							\
+	}								\
+      while (0)
+
+      /* Round 2.  */
+      OP (FG, A, B, C, D,  1,  5, 0xf61e2562);
+      OP (FG, D, A, B, C,  6,  9, 0xc040b340);
+      OP (FG, C, D, A, B, 11, 14, 0x265e5a51);
+      OP (FG, B, C, D, A,  0, 20, 0xe9b6c7aa);
+      OP (FG, A, B, C, D,  5,  5, 0xd62f105d);
+      OP (FG, D, A, B, C, 10,  9, 0x02441453);
+      OP (FG, C, D, A, B, 15, 14, 0xd8a1e681);
+      OP (FG, B, C, D, A,  4, 20, 0xe7d3fbc8);
+      OP (FG, A, B, C, D,  9,  5, 0x21e1cde6);
+      OP (FG, D, A, B, C, 14,  9, 0xc33707d6);
+      OP (FG, C, D, A, B,  3, 14, 0xf4d50d87);
+      OP (FG, B, C, D, A,  8, 20, 0x455a14ed);
+      OP (FG, A, B, C, D, 13,  5, 0xa9e3e905);
+      OP (FG, D, A, B, C,  2,  9, 0xfcefa3f8);
+      OP (FG, C, D, A, B,  7, 14, 0x676f02d9);
+      OP (FG, B, C, D, A, 12, 20, 0x8d2a4c8a);
+
+      /* Round 3.  */
+      OP (FH, A, B, C, D,  5,  4, 0xfffa3942);
+      OP (FH, D, A, B, C,  8, 11, 0x8771f681);
+      OP (FH, C, D, A, B, 11, 16, 0x6d9d6122);
+      OP (FH, B, C, D, A, 14, 23, 0xfde5380c);
+      OP (FH, A, B, C, D,  1,  4, 0xa4beea44);
+      OP (FH, D, A, B, C,  4, 11, 0x4bdecfa9);
+      OP (FH, C, D, A, B,  7, 16, 0xf6bb4b60);
+      OP (FH, B, C, D, A, 10, 23, 0xbebfbc70);
+      OP (FH, A, B, C, D, 13,  4, 0x289b7ec6);
+      OP (FH, D, A, B, C,  0, 11, 0xeaa127fa);
+      OP (FH, C, D, A, B,  3, 16, 0xd4ef3085);
+      OP (FH, B, C, D, A,  6, 23, 0x04881d05);
+      OP (FH, A, B, C, D,  9,  4, 0xd9d4d039);
+      OP (FH, D, A, B, C, 12, 11, 0xe6db99e5);
+      OP (FH, C, D, A, B, 15, 16, 0x1fa27cf8);
+      OP (FH, B, C, D, A,  2, 23, 0xc4ac5665);
+
+      /* Round 4.  */
+      OP (FI, A, B, C, D,  0,  6, 0xf4292244);
+      OP (FI, D, A, B, C,  7, 10, 0x432aff97);
+      OP (FI, C, D, A, B, 14, 15, 0xab9423a7);
+      OP (FI, B, C, D, A,  5, 21, 0xfc93a039);
+      OP (FI, A, B, C, D, 12,  6, 0x655b59c3);
+      OP (FI, D, A, B, C,  3, 10, 0x8f0ccc92);
+      OP (FI, C, D, A, B, 10, 15, 0xffeff47d);
+      OP (FI, B, C, D, A,  1, 21, 0x85845dd1);
+      OP (FI, A, B, C, D,  8,  6, 0x6fa87e4f);
+      OP (FI, D, A, B, C, 15, 10, 0xfe2ce6e0);
+      OP (FI, C, D, A, B,  6, 15, 0xa3014314);
+      OP (FI, B, C, D, A, 13, 21, 0x4e0811a1);
+      OP (FI, A, B, C, D,  4,  6, 0xf7537e82);
+      OP (FI, D, A, B, C, 11, 10, 0xbd3af235);
+      OP (FI, C, D, A, B,  2, 15, 0x2ad7d2bb);
+      OP (FI, B, C, D, A,  9, 21, 0xeb86d391);
+
+      /* Add the starting values of the context.  */
+      A += A_save;
+      B += B_save;
+      C += C_save;
+      D += D_save;
+    }
+
+  /* Put checksum in context given as argument.  */
+  ctx->A = A;
+  ctx->B = B;
+  ctx->C = C;
+  ctx->D = D;
+}
diff --git a/src/libnix/md5.h b/src/libnix/md5.h
new file mode 100644
index 000000000000..6301e4558ca1
--- /dev/null
+++ b/src/libnix/md5.h
@@ -0,0 +1,151 @@
+/* Declaration of functions and data types used for MD5 sum computing
+   library functions.
+   Copyright (C) 1995,1996,1997,1999,2000,2001 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+   02111-1307 USA.  */
+
+#ifndef _MD5_H
+#define _MD5_H 1
+
+#include <stdio.h>
+
+#if defined HAVE_LIMITS_H || _LIBC
+# include <limits.h>
+#endif
+
+/* The following contortions are an attempt to use the C preprocessor
+   to determine an unsigned integral type that is 32 bits wide.  An
+   alternative approach is to use autoconf's AC_CHECK_SIZEOF macro, but
+   doing that would require that the configure script compile and *run*
+   the resulting executable.  Locally running cross-compiled executables
+   is usually not possible.  */
+
+#ifdef _LIBC
+# include <stdint.h>
+typedef uint32_t md5_uint32;
+typedef uintptr_t md5_uintptr;
+#else
+# if defined __STDC__ && __STDC__
+#  define UINT_MAX_32_BITS 4294967295U
+# else
+#  define UINT_MAX_32_BITS 0xFFFFFFFF
+# endif
+
+/* If UINT_MAX isn't defined, assume it's a 32-bit type.
+   This should be valid for all systems GNU cares about because
+   that doesn't include 16-bit systems, and only modern systems
+   (that certainly have <limits.h>) have 64+-bit integral types.  */
+
+# ifndef UINT_MAX
+#  define UINT_MAX UINT_MAX_32_BITS
+# endif
+
+# if UINT_MAX == UINT_MAX_32_BITS
+   typedef unsigned int md5_uint32;
+# else
+#  if USHRT_MAX == UINT_MAX_32_BITS
+    typedef unsigned short md5_uint32;
+#  else
+#   if ULONG_MAX == UINT_MAX_32_BITS
+     typedef unsigned long md5_uint32;
+#   else
+     /* The following line is intended to evoke an error.
+        Using #error is not portable enough.  */
+     "Cannot determine unsigned 32-bit data type."
+#   endif
+#  endif
+# endif
+/* We have to make a guess about the integer type equivalent in size
+   to pointers which should always be correct.  */
+typedef unsigned long int md5_uintptr;
+#endif
+
+#undef __P
+#if defined (__STDC__) && __STDC__
+# define __P(x) x
+#else
+# define __P(x) ()
+#endif
+
+/* Structure to save state of computation between the single steps.  */
+struct md5_ctx
+{
+  md5_uint32 A;
+  md5_uint32 B;
+  md5_uint32 C;
+  md5_uint32 D;
+
+  md5_uint32 total[2];
+  md5_uint32 buflen;
+  char buffer[128] __attribute__ ((__aligned__ (__alignof__ (md5_uint32))));
+};
+
+/*
+ * The following three functions are build up the low level used in
+ * the functions `md5_stream' and `md5_buffer'.
+ */
+
+/* Initialize structure containing state of computation.
+   (RFC 1321, 3.3: Step 3)  */
+extern void md5_init_ctx __P ((struct md5_ctx *ctx));
+
+/* Starting with the result of former calls of this function (or the
+   initialization function update the context for the next LEN bytes
+   starting at BUFFER.
+   It is necessary that LEN is a multiple of 64!!! */
+extern void md5_process_block __P ((const void *buffer, size_t len,
+				      struct md5_ctx *ctx));
+
+/* Starting with the result of former calls of this function (or the
+   initialization function update the context for the next LEN bytes
+   starting at BUFFER.
+   It is NOT required that LEN is a multiple of 64.  */
+extern void md5_process_bytes __P ((const void *buffer, size_t len,
+				      struct md5_ctx *ctx));
+
+/* Process the remaining bytes in the buffer and put result from CTX
+   in first 16 bytes following RESBUF.  The result is always in little
+   endian byte order, so that a byte-wise output yields to the wanted
+   ASCII representation of the message digest.
+
+   IMPORTANT: On some systems it is required that RESBUF is correctly
+   aligned for a 32 bits value.  */
+extern void *md5_finish_ctx __P ((struct md5_ctx *ctx, void *resbuf));
+
+
+/* Put result from CTX in first 16 bytes following RESBUF.  The result is
+   always in little endian byte order, so that a byte-wise output yields
+   to the wanted ASCII representation of the message digest.
+
+   IMPORTANT: On some systems it is required that RESBUF is correctly
+   aligned for a 32 bits value.  */
+extern void *md5_read_ctx __P ((const struct md5_ctx *ctx, void *resbuf));
+
+
+/* Compute MD5 message digest for bytes read from STREAM.  The
+   resulting message digest number will be written into the 16 bytes
+   beginning at RESBLOCK.  */
+extern int md5_stream __P ((FILE *stream, void *resblock));
+
+/* Compute MD5 message digest for LEN bytes beginning at BUFFER.  The
+   result is always in little endian byte order, so that a byte-wise
+   output yields to the wanted ASCII representation of the message
+   digest.  */
+extern void *md5_buffer __P ((const char *buffer, size_t len,
+				void *resblock));
+    
+#endif /* md5.h */
diff --git a/src/libnix/normalise.cc b/src/libnix/normalise.cc
new file mode 100644
index 000000000000..be71081ffb25
--- /dev/null
+++ b/src/libnix/normalise.cc
@@ -0,0 +1,469 @@
+#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;
+}
+
+
+#if 0
+/* Return a path whose contents have the given hash.  If target is
+   not empty, ensure that such a path is realised in target (if
+   necessary by copying from another location).  If prefix is not
+   empty, only return a path that is an descendent of prefix. */
+
+string expandId(const FSId & id, const string & target = "",
+    const string & prefix = "/", FSIdSet pending = FSIdSet(),
+    bool ignoreSubstitutes = false)
+{
+    xxx
+}
+
+
+string expandId(const FSId & id, const string & target,
+    const string & prefix, FSIdSet pending, bool ignoreSubstitutes)
+{
+    Nest nest(lvlDebug, format("expanding %1%") % (string) id);
+
+    Strings paths;
+
+    if (!target.empty() && !isInPrefix(target, prefix))
+        abort();
+
+    nixDB.queryStrings(noTxn, dbId2Paths, id, paths);
+
+    /* Pick one equal to `target'. */
+    if (!target.empty()) {
+
+        for (Strings::iterator i = paths.begin();
+             i != paths.end(); i++)
+        {
+            string path = *i;
+            if (path == target && pathExists(path))
+                return path;
+        }
+        
+    }
+
+    /* Arbitrarily pick the first one that exists and isn't stale. */
+    for (Strings::iterator it = paths.begin();
+         it != paths.end(); it++)
+    {
+        string path = *it;
+        if (isInPrefix(path, prefix) && pathExists(path)) {
+            if (target.empty())
+                return path;
+            else {
+                /* Acquire a lock on the target path. */
+                Strings lockPaths;
+                lockPaths.push_back(target);
+                PathLocks outputLock(lockPaths);
+
+                /* Copy. */
+                copyPath(path, target);
+
+                /* Register the target path. */
+                Transaction txn(nixDB);
+                registerPath(txn, target, id);
+                txn.commit();
+
+                return target;
+            }
+        }
+    }
+
+    if (!ignoreSubstitutes) {
+        
+        if (pending.find(id) != pending.end())
+            throw Error(format("id %1% already being expanded") % (string) id);
+        pending.insert(id);
+
+        /* Try to realise the substitutes, but only if this id is not
+           already being realised by a substitute. */
+        Strings subs;
+        nixDB.queryStrings(noTxn, dbSubstitutes, id, subs); /* non-existence = ok */
+
+        for (Strings::iterator it = subs.begin(); it != subs.end(); it++) {
+            FSId subId = parseHash(*it);
+
+            debug(format("trying substitute %1%") % (string) subId);
+
+            realiseClosure(normaliseNixExpr(subId, pending), pending);
+
+            return expandId(id, target, prefix, pending);
+        }
+
+    }
+    
+    throw Error(format("cannot expand id `%1%'") % (string) id);
+}
+#endif
+
+    
+Path normaliseNixExpr(const Path & _nePath, PathSet pending)
+{
+    Nest 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 we can expand all output
+       paths from their ids. */
+    bool fastBuild = false;
+#if 0
+    bool fastBuild = true;
+    for (PathSet::iterator i = ne.derivation.outputs.begin();
+         i != ne.derivation.outputs.end(); i++)
+    {
+        try {
+            expandId(i->second, i->first, "/", pending);
+        } catch (Error & e) {
+            debug(format("fast build failed for `%1%': %2%")
+		  % i->first % e.what());
+            fastBuild = false;
+            break;
+        }
+    }
+#endif
+
+    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. */
+        msg(lvlChatty, format("building..."));
+        runProgram(ne.derivation.builder, ne.derivation.args, env);
+        msg(lvlChatty, format("build completed"));
+        
+    } else
+        msg(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);
+    msg(lvlVomit, format("normal form: %1%") % printTerm(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)
+{
+    Nest 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) {
+            msg(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/libnix/normalise.hh b/src/libnix/normalise.hh
new file mode 100644
index 000000000000..bbe846404cc0
--- /dev/null
+++ b/src/libnix/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/libnix/pathlocks.cc b/src/libnix/pathlocks.cc
new file mode 100644
index 000000000000..3ecbbbcbafd5
--- /dev/null
+++ b/src/libnix/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/libnix/pathlocks.hh b/src/libnix/pathlocks.hh
new file mode 100644
index 000000000000..ce61386d6df0
--- /dev/null
+++ b/src/libnix/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/libnix/references.cc b/src/libnix/references.cc
new file mode 100644
index 000000000000..be432665b884
--- /dev/null
+++ b/src/libnix/references.cc
@@ -0,0 +1,110 @@
+#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)) {
+        DIR * 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);
+        }
+
+        closedir(dir); /* !!! close on exception */
+    }
+
+    else if (S_ISREG(st.st_mode)) {
+        
+        debug(format("checking `%1%'") % path);
+
+        int 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 */
+
+        close(fd); /* !!! close on exception */
+    }
+    
+    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/libnix/references.hh b/src/libnix/references.hh
new file mode 100644
index 000000000000..d009453d6a00
--- /dev/null
+++ b/src/libnix/references.hh
@@ -0,0 +1,10 @@
+#ifndef __VALUES_H
+#define __VALUES_H
+
+#include "util.hh"
+
+
+Strings filterReferences(const Path & path, const Strings & refs);
+
+
+#endif /* !__VALUES_H */
diff --git a/src/libnix/store.cc b/src/libnix/store.cc
new file mode 100644
index 000000000000..2d223313b612
--- /dev/null
+++ b/src/libnix/store.cc
@@ -0,0 +1,405 @@
+#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)) {
+
+        /* !!! locking? -> parallel writes are probably idempotent */
+
+        int fd = open(dstPath.c_str(), O_CREAT | O_EXCL | O_WRONLY, 0666);
+        if (fd == -1) throw SysError(format("creating store file `%1%'") % dstPath);
+
+        if (write(fd, s.c_str(), s.size()) != (ssize_t) s.size())
+            throw SysError(format("writing store file `%1%'") % dstPath);
+
+        close(fd); /* !!! close on exception */
+
+        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/libnix/store.hh b/src/libnix/store.hh
new file mode 100644
index 000000000000..dab3d603f802
--- /dev/null
+++ b/src/libnix/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/libnix/test-builder-1.sh b/src/libnix/test-builder-1.sh
new file mode 100755
index 000000000000..80e23354c3b9
--- /dev/null
+++ b/src/libnix/test-builder-1.sh
@@ -0,0 +1,3 @@
+#! /bin/sh
+
+echo "Hello World" > $out
diff --git a/src/libnix/test-builder-2.sh b/src/libnix/test-builder-2.sh
new file mode 100755
index 000000000000..0794fa96a401
--- /dev/null
+++ b/src/libnix/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/libnix/test.cc b/src/libnix/test.cc
new file mode 100644
index 000000000000..457fecf245f0
--- /dev/null
+++ b/src/libnix/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";
diff --git a/src/libnix/util.cc b/src/libnix/util.cc
new file mode 100644
index 000000000000..c1d0fedea8aa
--- /dev/null
+++ b/src/libnix/util.cc
@@ -0,0 +1,253 @@
+#include <iostream>
+#include <cerrno>
+#include <cstdio>
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+#include <dirent.h>
+
+#include "util.hh"
+
+
+string thisSystem = SYSTEM;
+
+
+Error::Error(const format & f)
+{
+    err = f.str();
+}
+
+
+SysError::SysError(const format & f)
+    : Error(format("%1%: %2%") % f.str() % strerror(errno))
+{
+}
+
+
+Path absPath(Path path, Path dir)
+{
+    if (path[0] != '/') {
+        if (dir == "") {
+            char buf[PATH_MAX];
+            if (!getcwd(buf, sizeof(buf)))
+                throw SysError("cannot get cwd");
+            dir = buf;
+        }
+        path = dir + "/" + path;
+    }
+    return canonPath(path);
+}
+
+
+Path canonPath(const Path & path)
+{
+    string s;
+
+    if (path[0] != '/')
+        throw Error(format("not an absolute path: `%1%'") % path);
+
+    string::const_iterator i = path.begin(), end = path.end();
+
+    while (1) {
+
+        /* Skip slashes. */
+        while (i != end && *i == '/') i++;
+        if (i == end) break;
+
+        /* Ignore `.'. */
+        if (*i == '.' && (i + 1 == end || i[1] == '/'))
+            i++;
+
+        /* If `..', delete the last component. */
+        else if (*i == '.' && i + 1 < end && i[1] == '.' && 
+            (i + 2 == end || i[2] == '/'))
+        {
+            if (!s.empty()) s.erase(s.rfind('/'));
+            i += 2;
+        }
+
+        /* Normal component; copy it. */
+        else {
+            s += '/';
+            while (i != end && *i != '/') s += *i++;
+        }
+    }
+
+    return s.empty() ? "/" : s;
+}
+
+
+Path dirOf(const Path & path)
+{
+    unsigned int pos = path.rfind('/');
+    if (pos == string::npos)
+        throw Error(format("invalid file name: %1%") % path);
+    return Path(path, 0, pos);
+}
+
+
+string baseNameOf(const Path & path)
+{
+    unsigned int pos = path.rfind('/');
+    if (pos == string::npos)
+        throw Error(format("invalid file name %1% ") % path);
+    return string(path, pos + 1);
+}
+
+
+bool pathExists(const Path & path)
+{
+    int res;
+    struct stat st;
+    res = stat(path.c_str(), &st);
+    if (!res) return true;
+    if (errno != ENOENT)
+        throw SysError(format("getting status of %1%") % path);
+    return false;
+}
+
+
+void deletePath(const Path & path)
+{
+    msg(lvlVomit, format("deleting path `%1%'") % path);
+
+    struct stat st;
+    if (lstat(path.c_str(), &st))
+	throw SysError(format("getting attributes of path `%1%'") % path);
+
+    if (S_ISDIR(st.st_mode)) {
+	Strings names;
+
+        DIR * dir = opendir(path.c_str());
+
+        struct dirent * dirent;
+        while (errno = 0, dirent = readdir(dir)) {
+            string name = dirent->d_name;
+            if (name == "." || name == "..") continue;
+	    names.push_back(name);
+        }
+
+        closedir(dir); /* !!! close on exception */
+
+	/* Make the directory writable. */
+	if (!(st.st_mode & S_IWUSR)) {
+	    if (chmod(path.c_str(), st.st_mode | S_IWUSR) == -1)
+		throw SysError(format("making `%1%' writable"));
+	}
+
+	for (Strings::iterator i = names.begin(); i != names.end(); i++)
+            deletePath(path + "/" + *i);
+    }
+
+    if (remove(path.c_str()) == -1)
+        throw SysError(format("cannot unlink `%1%'") % path);
+}
+
+
+void makePathReadOnly(const Path & path)
+{
+    struct stat st;
+    if (lstat(path.c_str(), &st))
+	throw SysError(format("getting attributes of path `%1%'") % path);
+
+    if (!S_ISLNK(st.st_mode) && (st.st_mode & S_IWUSR)) {
+	if (chmod(path.c_str(), st.st_mode & ~S_IWUSR) == -1)
+	    throw SysError(format("making `%1%' read-only") % path);
+    }
+
+    if (S_ISDIR(st.st_mode)) {
+        DIR * dir = opendir(path.c_str());
+
+        struct dirent * dirent;
+        while (errno = 0, dirent = readdir(dir)) {
+            string name = dirent->d_name;
+            if (name == "." || name == "..") continue;
+	    makePathReadOnly(path + "/" + name);
+        }
+
+        closedir(dir); /* !!! close on exception */
+    }
+}
+
+
+static Path tempName()
+{
+    static int counter = 0;
+    char * s = getenv("TMPDIR");
+    Path tmpRoot = s ? canonPath(Path(s)) : "/tmp";
+    return (format("%1%/nix-%2%-%3%") % tmpRoot % getpid() % counter++).str();
+}
+
+
+Path createTempDir()
+{
+    while (1) {
+	Path tmpDir = tempName();
+	if (mkdir(tmpDir.c_str(), 0777) == 0) return tmpDir;
+	if (errno != EEXIST)
+	    throw SysError(format("creating directory `%1%'") % tmpDir);
+    }
+}
+
+
+Verbosity verbosity = lvlError;
+
+static int nestingLevel = 0;
+
+
+Nest::Nest(Verbosity level, const format & f)
+{
+    if (level > verbosity)
+        nest = false;
+    else {
+        msg(level, f);
+        nest = true;
+        nestingLevel++;
+    }
+}
+
+
+Nest::~Nest()
+{
+    if (nest) nestingLevel--;
+}
+
+
+void msg(Verbosity level, const format & f)
+{
+    if (level > verbosity) return;
+    string spaces;
+    for (int i = 0; i < nestingLevel; i++)
+        spaces += "|   ";
+    cerr << format("%1%%2%\n") % spaces % f.str();
+}
+
+
+void debug(const format & f)
+{
+    msg(lvlDebug, f);
+}
+
+
+void readFull(int fd, unsigned char * buf, size_t count)
+{
+    while (count) {
+        ssize_t res = read(fd, (char *) buf, count);
+        if (res == -1) throw SysError("reading from file");
+        if (res == 0) throw Error("unexpected end-of-file");
+        count -= res;
+        buf += res;
+    }
+}
+
+
+void writeFull(int fd, const unsigned char * buf, size_t count)
+{
+    while (count) {
+        ssize_t res = write(fd, (char *) buf, count);
+        if (res == -1) throw SysError("writing to file");
+        count -= res;
+        buf += res;
+    }
+}
diff --git a/src/libnix/util.hh b/src/libnix/util.hh
new file mode 100644
index 000000000000..016289176be8
--- /dev/null
+++ b/src/libnix/util.hh
@@ -0,0 +1,116 @@
+#ifndef __UTIL_H
+#define __UTIL_H
+
+#include <string>
+#include <list>
+#include <set>
+#include <sstream>
+
+#include <unistd.h>
+
+#include <boost/format.hpp>
+
+using namespace std;
+using namespace boost;
+
+
+class Error : public exception
+{
+protected:
+    string err;
+public:
+    Error(const format & f);
+    ~Error() throw () { };
+    const char * what() const throw () { return err.c_str(); }
+    const string & msg() const throw () { return err; }
+};
+
+class SysError : public Error
+{
+public:
+    SysError(const format & f);
+};
+
+class UsageError : public Error
+{
+public:
+    UsageError(const format & f) : Error(f) { };
+};
+
+
+typedef list<string> Strings;
+typedef set<string> StringSet;
+
+
+/* Paths are just strings. */
+typedef string Path;
+typedef list<Path> Paths;
+typedef set<Path> PathSet;
+
+
+/* The canonical system name, as returned by config.guess. */ 
+extern string thisSystem;
+
+
+/* Return an absolutized path, resolving paths relative to the
+   specified directory, or the current directory otherwise.  The path
+   is also canonicalised. */
+Path absPath(Path path, Path dir = "");
+
+/* Canonicalise a path (as in realpath(3)). */
+Path canonPath(const Path & path);
+
+/* Return the directory part of the given path, i.e., everything
+   before the final `/'. */
+Path dirOf(const Path & path);
+
+/* Return the base name of the given path, i.e., everything following
+   the final `/'. */
+string baseNameOf(const Path & path);
+
+/* Return true iff the given path exists. */
+bool pathExists(const Path & path);
+
+/* Delete a path; i.e., in the case of a directory, it is deleted
+   recursively.  Don't use this at home, kids. */
+void deletePath(const Path & path);
+
+/* Make a path read-only recursively. */
+void makePathReadOnly(const Path & path);
+
+/* Create a temporary directory. */
+Path createTempDir();
+
+
+/* Messages. */
+
+typedef enum { 
+    lvlError, 
+    lvlTalkative,
+    lvlChatty,
+    lvlDebug,
+    lvlVomit
+} Verbosity;
+
+extern Verbosity verbosity; /* supress msgs > this */
+
+class Nest
+{
+private:
+    bool nest;
+public:
+    Nest(Verbosity level, const format & f);
+    ~Nest();
+};
+
+void msg(Verbosity level, const format & f);
+void debug(const format & f); /* short-hand for msg(lvlDebug, ...) */
+
+
+/* Wrappers arount read()/write() that read/write exactly the
+   requested number of bytes. */
+void readFull(int fd, unsigned char * buf, size_t count);
+void writeFull(int fd, const unsigned char * buf, size_t count);
+
+
+#endif /* !__UTIL_H */