* Started implementing the new evaluation model.

* Lots of refactorings.
* Unit tests.

15 files changed, 741 insertions, 201 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index a56a0ae0e8..80d9e4af8d 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -9,16 +9,15 @@ nix_LDADD = -ldb_cxx-4 -lATerm
 fix_SOURCES = fix.cc util.cc hash.cc md5.c
 fix_LDADD = -lATerm
 
-test_SOURCES = test.cc util.cc hash.cc md5.c
+test_SOURCES = test.cc util.cc hash.cc md5.c eval.cc values.cc globals.cc db.cc
+test_LDADD = -ldb_cxx-4 -lATerm
 
 install-data-local:
 	$(INSTALL) -d $(localstatedir)/nix
-	$(INSTALL) -d $(localstatedir)/nix/descriptors
-	$(INSTALL) -d $(localstatedir)/nix/sources
 	$(INSTALL) -d $(localstatedir)/nix/links
-	$(INSTALL) -d $(localstatedir)/nix/prebuilts
-	$(INSTALL) -d $(localstatedir)/nix/prebuilts/imports
-	$(INSTALL) -d $(localstatedir)/nix/prebuilts/exports
+#	$(INSTALL) -d $(localstatedir)/nix/prebuilts
+#	$(INSTALL) -d $(localstatedir)/nix/prebuilts/imports
+#	$(INSTALL) -d $(localstatedir)/nix/prebuilts/exports
 	$(INSTALL) -d $(localstatedir)/log/nix
-	$(INSTALL) -d $(prefix)/pkg
+	$(INSTALL) -d $(prefix)/values
 	$(bindir)/nix init
diff --git a/src/eval.cc b/src/eval.cc
new file mode 100644
index 0000000000..14577c8738
--- /dev/null
+++ b/src/eval.cc
@@ -0,0 +1,297 @@
+#include <map>
+#include <iostream>
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/wait.h>
+#include <unistd.h>
+
+#include "eval.hh"
+#include "globals.hh"
+#include "values.hh"
+#include "db.hh"
+
+
+/* A Unix environment is a mapping from strings to strings. */
+typedef map<string, string> Environment;
+
+
+/* Return true iff the given path exists. */
+bool pathExists(string path)
+{
+    int res;
+    struct stat st;
+    res = stat(path.c_str(), &st);
+    if (!res) return true;
+    if (errno != ENOENT)
+        throw SysError("getting status of " + path);
+    return false;
+}
+
+
+/* Compute a derived value by running a program. */
+static Hash computeDerived(Hash sourceHash, string targetName,
+    string platform, Hash prog, Environment env)
+{
+    string targetPath = nixValues + "/" + 
+        (string) sourceHash + "-nf";
+
+    /* Check whether the target already exists. */
+    if (pathExists(targetPath)) 
+        throw Error("derived value in " + targetPath + " already exists");
+
+    /* Find the program corresponding to the hash `prog'. */
+    string progPath = queryValuePath(prog);
+
+    /* Finalize the environment. */
+    env["out"] = targetPath;
+
+    /* Create a log file. */
+    string logFileName = 
+        nixLogDir + "/" + baseNameOf(targetPath) + ".log";
+    /* !!! auto-pclose on exit */
+    FILE * logFile = popen(("tee " + logFileName + " >&2").c_str(), "w"); /* !!! escaping */
+    if (!logFile)
+        throw SysError("unable to create log file " + logFileName);
+
+    try {
+
+        /* 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 0
+                /* Try to use a prebuilt. */
+                string prebuiltHashS, prebuiltFile;
+                if (queryDB(nixDB, dbPrebuilts, hash, prebuiltHashS)) {
+
+                    try {
+                        prebuiltFile = getFile(parseHash(prebuiltHashS));
+                    } catch (Error e) {
+                        cerr << "cannot obtain prebuilt (ignoring): " << e.what() << endl;
+                        goto build;
+                    }
+                
+                    cerr << "substituting prebuilt " << prebuiltFile << endl;
+
+                    int res = system(("tar xfj " + prebuiltFile + " 1>&2").c_str()); // !!! escaping
+                    if (WEXITSTATUS(res) != 0)
+                        /* This is a fatal error, because path may now
+                           have clobbered. */
+                        throw Error("cannot unpack " + prebuiltFile);
+
+                    _exit(0);
+                }
+#endif
+
+            build:
+
+                /* Fill in the environment.  We don't bother freeing
+                   the strings, since we'll exec or die soon
+                   anyway. */
+                const char * env2[env.size() + 1];
+                int i = 0;
+                for (Environment::iterator it = env.begin();
+                     it != env.end(); it++, i++)
+                    env2[i] = (new string(it->first + "=" + it->second))->c_str();
+                env2[i] = 0;
+
+                /* Dup the log handle into stderr. */
+                if (dup2(fileno(logFile), STDERR_FILENO) == -1)
+                    throw Error("cannot pipe standard error into log file: " + string(strerror(errno)));
+            
+                /* Dup stderr to stdin. */
+                if (dup2(STDERR_FILENO, STDOUT_FILENO) == -1)
+                    throw Error("cannot dup stderr into stdout");
+
+                /* Make the program executable.  !!! hack. */
+                if (chmod(progPath.c_str(), 0755))
+                    throw Error("cannot make program executable");
+
+                /* Execute the program.  This should not return. */
+                execle(progPath.c_str(), baseNameOf(progPath).c_str(), 0, env2);
+
+                throw Error("unable to execute builder: " +
+                    string(strerror(errno)));
+            
+            } catch (exception & e) {
+                cerr << "build error: " << e.what() << endl;
+                _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)
+            throw Error("unable to build package");
+
+        /* Check whether the result was created. */
+        if (!pathExists(targetPath))
+            throw Error("program " + progPath + 
+                " failed to create a result in " + targetPath);
+
+        /* Remove write permission from the value. */
+        int res = system(("chmod -R -w " + targetPath).c_str()); // !!! escaping
+        if (WEXITSTATUS(res) != 0)
+            throw Error("cannot remove write permission from " + targetPath);
+
+    } catch (exception &) {
+//         system(("rm -rf " + targetPath).c_str());
+        throw;
+    }
+
+    /* Hash the result. */
+    Hash targetHash = hashFile(targetPath);
+
+    /* Register targetHash -> targetPath.  !!! this should be in
+       values.cc. */
+    setDB(nixDB, dbNFs, sourceHash, targetName);
+
+    /* Register that targetHash was produced by evaluating
+       sourceHash; i.e., that targetHash is a normal form of
+       sourceHash. !!! this shouldn't be here */
+    setDB(nixDB, dbNFs, sourceHash, targetHash);
+
+    return targetHash;
+}
+
+
+/* Throw an exception if the given platform string is not supported by
+   the platform we are executing on. */
+static void checkPlatform(string platform)
+{
+    if (platform != thisSystem)
+        throw Error("a `" + platform +
+            "' is required, but I am a `" + thisSystem + "'");
+}
+
+
+/* Throw an exception with an error message containing the given
+   aterm. */
+static Error badTerm(const string & msg, Expr e)
+{
+    char * s = ATwriteToString(e);
+    return Error(msg + ", in `" + s + "'");
+}
+
+
+/* Hash an expression.  Hopefully the representation used by
+   ATwriteToString() won't change, otherwise all hashes will
+   change. */
+static Hash hashExpr(Expr e)
+{
+    char * s = ATwriteToString(e);
+    debug(s);
+    return hashString(s);
+}
+
+
+/* Evaluate an expression; the result must be a string. */
+static string evalString(Expr e)
+{
+    e = evalValue(e).e;
+    char * s;
+    if (ATmatch(e, "Str(<str>)", &s)) return s;
+    else throw badTerm("string value expected", e);
+}
+
+
+/* Evaluate an expression; the result must be a external
+   non-expression reference. */
+static Hash evalExternal(Expr e)
+{
+    EvalResult r = evalValue(e);
+    char * s;
+    if (ATmatch(r.e, "External(<str>)", &s)) return r.h;
+    else throw badTerm("external non-expression value expected", r.e);
+}
+
+
+/* Evaluate an expression. */
+EvalResult evalValue(Expr e)
+{
+    EvalResult r;
+    char * s;
+    Expr eBuildPlatform, eProg;
+    ATermList args;
+
+    /* Normal forms. */
+    if (ATmatch(e, "Str(<str>)", &s) ||
+        ATmatch(e, "Bool(True)") || 
+        ATmatch(e, "Bool(False)"))
+    {
+        r.e = e;
+    }
+
+    /* External expressions. */
+
+    /* External non-expressions. */
+    else if (ATmatch(e, "External(<str>)", &s)) {
+        r.e = e;
+        r.h = parseHash(s);
+    }
+
+    /* Execution primitive. */
+
+    else if (ATmatch(e, "Exec(<term>, <term>, [<list>])",
+                 &eBuildPlatform, &eProg, &args))
+    {
+        string buildPlatform = evalString(eBuildPlatform);
+
+        checkPlatform(buildPlatform);
+
+        Hash prog = evalExternal(eProg);
+
+        Environment env;
+        while (!ATisEmpty(args)) {
+            debug("arg");
+            Expr arg = ATgetFirst(args);
+            throw badTerm("foo", arg);
+            args = ATgetNext(args);
+        }
+
+        Hash sourceHash = hashExpr(
+            ATmake("Exec(Str(<str>), External(<str>), [])",
+                buildPlatform.c_str(), ((string) prog).c_str()));
+
+        /* Do we know a normal form for sourceHash? */
+        Hash targetHash;
+        string targetHashS;
+        if (queryDB(nixDB, dbNFs, sourceHash, targetHashS)) {
+            /* Yes. */
+            targetHash = parseHash(targetHashS);
+            debug("already built: " + (string) sourceHash 
+                + " -> " + (string) targetHash);
+        } else {
+            /* No, so we compute one. */
+            targetHash = computeDerived(sourceHash, 
+                (string) sourceHash + "-nf", buildPlatform, prog, env);
+        }
+
+        r.e = ATmake("External(<str>)", ((string) targetHash).c_str());
+        r.h = targetHash;
+    }
+
+    /* Barf. */
+    else throw badTerm("invalid expression", e);
+
+    return r;
+}
diff --git a/src/eval.hh b/src/eval.hh
new file mode 100644
index 0000000000..bddc9f5d95
--- /dev/null
+++ b/src/eval.hh
@@ -0,0 +1,86 @@
+#ifndef __EVAL_H
+#define __EVAL_H
+
+extern "C" {
+#include <aterm2.h>
+}
+
+#include "hash.hh"
+
+using namespace std;
+
+
+/* Abstract syntax of Nix values:
+
+   e := Hash(h) -- reference to expression value
+      | External(h) -- reference to non-expression value
+      | Str(s) -- string constant
+      | Bool(b) -- boolean constant
+      | App(e, e) -- application
+      | Lam(x, e) -- lambda abstraction
+      | Exec(platform, e, [(s, e)])
+          -- primitive; execute e with args e* on platform
+      ;
+
+   Semantics
+
+   Each rules given as eval(e) => (e', h'), i.e., expression e has a
+   normal form e' with hash code h'.  evalE = fst . eval.  evalH = snd
+   . eval.
+
+   eval(Hash(h)) => eval(loadExpr(h))
+
+   eval(External(h)) => (External(h), h)
+
+   eval(Str(s)@e) => (e, 0) # idem for Bool
+
+   eval(App(e1, e2)) => eval(App(e1', e2))
+     where e1' = evalE(e1)
+
+   eval(App(Lam(var, body), arg)@in) =>
+     eval(subst(var, arg, body))@out
+     [AND write out to storage, and dbNFs[hash(in)] = hash(out) ???]
+
+   eval(Exec(platform, prog, args)@e) =>
+     (External(h), h)
+     where
+       hIn = hashExpr(e)
+
+       fn = ... form name involving hIn ...
+
+       h =
+         if exec(evalE(platform) => Str(...)
+                , getFile(evalH(prog))
+                , map(makeArg . eval, args)
+                ) then
+           hashExternal(fn)
+         else
+           undef
+
+   makeArg((argn, (External(h), h))) => (argn, getFile(h))
+   makeArg((argn, (Str(s), _))) => (argn, s)
+   makeArg((argn, (Bool(True), _))) => (argn, "1")
+   makeArg((argn, (Bool(False), _))) => (argn, undef)
+
+   getFile :: Hash -> FileName
+   loadExpr :: Hash -> FileName
+   hashExpr :: Expr -> Hash 
+   hashExternal :: FileName -> Hash
+   exec :: Platform -> FileName -> [(String, String)] -> Status
+*/
+
+typedef ATerm Expr;
+
+
+struct EvalResult 
+{
+    Expr e;
+    Hash h;
+};
+
+
+/* Evaluate an expression. */
+EvalResult evalValue(Expr e);
+
+
+#endif /* !__EVAL_H */
diff --git a/src/globals.cc b/src/globals.cc
new file mode 100644
index 0000000000..14fb431d88
--- /dev/null
+++ b/src/globals.cc
@@ -0,0 +1,19 @@
+#include "globals.hh"
+#include "db.hh"
+
+
+string dbRefs = "refs";
+string dbNFs = "nfs";
+string dbNetSources = "netsources";
+
+string nixValues = "/UNINIT";
+string nixLogDir = "/UNINIT";
+string nixDB = "/UNINIT";
+
+
+void initDB()
+{
+    createDB(nixDB, dbRefs);
+    createDB(nixDB, dbNFs);
+    createDB(nixDB, dbNetSources);
+}
diff --git a/src/globals.hh b/src/globals.hh
new file mode 100644
index 0000000000..d4fe4b370f
--- /dev/null
+++ b/src/globals.hh
@@ -0,0 +1,60 @@
+#ifndef __GLOBALS_H
+#define __GLOBALS_H
+
+#include <string>
+
+using namespace std;
+
+
+/* Database names. */
+
+/* dbRefs :: Hash -> FileName
+
+   Maintains a mapping from hashes to filenames within the NixValues
+   directory.  This mapping is for performance only; it can be
+   reconstructed unambiguously.  The reason is that names in this
+   directory are not printed hashes but also might carry some
+   descriptive element (e.g., "aterm-2.0-ae749a...").  Without this
+   mapping, looking up a value would take O(n) time because we would
+   need to read the entire directory. */
+extern string dbRefs;
+
+/* dbNFs :: Hash -> Hash
+
+   Each pair (h1, h2) in this mapping records the fact that the value
+   referenced by h2 is a normal form obtained by evaluating the value
+   referenced by value h1.
+*/
+extern string dbNFs;
+
+/* dbNetSources :: Hash -> URL
+
+   Each pair (hash, url) in this mapping states that the value
+   identified by hash can be obtained by fetching the value pointed
+   to by url.
+
+   TODO: this should be Hash -> [URL]
+
+   TODO: factor this out into a separate tool? */
+extern string dbNetSources;
+
+
+/* Path names. */
+
+/* nixValues is the directory where all Nix values (both files and
+   directories, and both normal and non-normal forms) live. */
+extern string nixValues;
+
+/* nixLogDir is the directory where we log evaluations. */ 
+extern string nixLogDir;
+
+/* nixDB is the file name of the Berkeley DB database where we
+   maintain the dbXXX mappings. */
+extern string nixDB;
+
+
+/* Initialize the databases. */
+void initDB();
+
+
+#endif /* !__GLOBALS_H */
diff --git a/src/hash.cc b/src/hash.cc
index 25d76bd15c..bb25c5168f 100644
--- a/src/hash.cc
+++ b/src/hash.cc
@@ -46,6 +46,8 @@ Hash::operator string() const
 Hash parseHash(const string & s)
 {
     Hash hash;
+    if (s.length() != Hash::hashSize * 2)
+        throw BadRefError("invalid hash: " + s);
     for (unsigned int i = 0; i < Hash::hashSize; i++) {
         string s2(s, i * 2, 2);
         if (!isxdigit(s2[0]) || !isxdigit(s2[1])) 
@@ -74,14 +76,23 @@ bool isHash(const string & s)
 
 
 /* Compute the MD5 hash of a file. */
+Hash hashString(const string & s)
+{
+    Hash hash;
+    md5_buffer(s.c_str(), s.length(), hash.hash);
+    return hash;
+}
+
+
+/* Compute the MD5 hash of a file. */
 Hash hashFile(const string & fileName)
 {
     Hash hash;
     FILE * file = fopen(fileName.c_str(), "rb");
     if (!file)
-        throw Error("file `" + fileName + "' does not exist");
+        throw SysError("file `" + fileName + "' does not exist");
     int err = md5_stream(file, hash.hash);
     fclose(file);
-    if (err) throw Error("cannot hash file");
+    if (err) throw SysError("cannot hash file " + fileName);
     return hash;
 }
diff --git a/src/hash.hh b/src/hash.hh
index 162b2b1c8f..6e20b3cbc1 100644
--- a/src/hash.hh
+++ b/src/hash.hh
@@ -29,6 +29,7 @@ public:
 
 Hash parseHash(const string & s);
 bool isHash(const string & s);
+Hash hashString(const string & s);
 Hash hashFile(const string & fileName);
 
 #endif /* !__HASH_H */
diff --git a/src/nix.cc b/src/nix.cc
index 7990cde3af..db9f187e20 100644
--- a/src/nix.cc
+++ b/src/nix.cc
@@ -11,155 +11,15 @@
 #include <sys/types.h>
 #include <sys/wait.h>
 
-extern "C" {
-#include <aterm1.h>
-}
-
 #include "util.hh"
 #include "hash.hh"
 #include "db.hh"
+#include "nix.hh"
+#include "eval.hh"
 
 using namespace std;
 
 
-/* Database names. */
-
-/* dbRefs :: Hash -> FileName
-
-   Maintains a mapping from hashes to filenames within the NixValues
-   directory.  This mapping is for performance only; it can be
-   reconstructed unambiguously from the nixValues directory.  The
-   reason is that names in this directory are not printed hashes but
-   also might carry some descriptive element (e.g.,
-   "aterm-2.0-ae749a...").  Without this mapping, looking up a value
-   would take O(n) time because we would need to read the entire
-   directory. */
-static string dbRefs = "refs";
-
-/* dbNFs :: Hash -> Hash
-
-   Each pair (h1, h2) in this mapping records the fact that h2 is a
-   normal form obtained by evaluating the value h1.
-
-   We would really like to have h2 be the hash of the object
-   referenced by h2.  However, that gives a cyclic dependency: to
-   compute the hash (and thus the file name) of the object, we need to
-   compute the object, but to do that, we need the file name of the
-   object.
-
-   So for now we abandon the requirement that 
-
-     hashFile(dbRefs[h]) == h.
-
-   I.e., this property does not hold for computed normal forms.
-   Rather, we use h2 = hash(h1).  This allows dbNFs to be
-   reconstructed.  Perhaps using a pseudo random number would be
-   better to prevent the system from being subverted in some way.
-*/
-static string dbNFs = "nfs";
-
-/* dbNetSources :: Hash -> URL
-
-   Each pair (hash, url) in this mapping states that the object
-   identified by hash can be obtained by fetching the object pointed
-   to by url. 
-
-   TODO: this should be Hash -> [URL]
-
-   TODO: factor this out into a separate tool? */
-static string dbNetSources = "netsources";
-
-
-/* Path names. */
-
-/* nixValues is the directory where all Nix values (both files and
-   directories, and both normal and non-normal forms) live. */
-static string nixValues;
-
-/* nixLogDir is the directory where we log evaluations. */ 
-static string nixLogDir;
-
-/* nixDB is the file name of the Berkeley DB database where we
-   maintain the dbXXX mappings. */
-static string nixDB;
-
-
-/* Abstract syntax of Nix values:
-
-   e := Hash(h) -- external reference
-      | Str(s) -- string constant
-      | Bool(b) -- boolean constant
-      | Name(e) -- "&" operator; pointer (file name) formation
-      | App(e, e) -- application
-      | Lam(x, e) -- lambda abstraction
-      | Exec(platform, e, e*)
-          -- primitive; execute e with args e* on platform
-      ;
-*/
-
-
-/* Download object referenced by the given URL into the sources
-   directory.  Return the file name it was downloaded to. */
-string fetchURL(string url)
-{
-    string filename = baseNameOf(url);
-    string fullname = nixSourcesDir + "/" + filename;
-    struct stat st;
-    if (stat(fullname.c_str(), &st)) {
-        cerr << "fetching " << url << endl;
-        /* !!! quoting */
-        string shellCmd =
-            "cd " + nixSourcesDir + " && wget --quiet -N \"" + url + "\"";
-        int res = system(shellCmd.c_str());
-        if (WEXITSTATUS(res) != 0)
-            throw Error("cannot fetch " + url);
-    }
-    return fullname;
-}
-
-
-/* Obtain an object with the given hash.  If a file with that hash is
-   known to exist in the local file system (as indicated by the dbRefs
-   database), we use that.  Otherwise, we attempt to fetch it from the
-   network (using dbNetSources).  We verify that the file has the
-   right hash. */
-string getFile(Hash hash)
-{
-    bool checkedNet = false;
-
-    while (1) {
-
-        string fn, url;
-
-        if (queryDB(nixDB, dbRefs, hash, fn)) {
-
-            /* Verify that the file hasn't changed. !!! race */
-            if (hashFile(fn) != hash)
-                throw Error("file " + fn + " is stale");
-
-            return fn;
-        }
-
-        if (checkedNet)
-            throw Error("consistency problem: file fetched from " + url + 
-                " should have hash " + (string) hash + ", but it doesn't");
-
-        if (!queryDB(nixDB, dbNetSources, hash, url))
-            throw Error("a file with hash " + (string) hash + " is requested, "
-                "but it is not known to exist locally or on the network");
-
-        checkedNet = true;
-        
-        fn = fetchURL(url);
-        
-        setDB(nixDB, dbRefs, hash, fn);
-    }
-}
-
-
-typedef map<string, string> Params;
-
-
 void readPkgDescr(Hash hash,
     Params & pkgImports, Params & fileImports, Params & arguments)
 {
@@ -204,9 +64,6 @@ void readPkgDescr(Hash hash,
 string getPkg(Hash hash);
 
 
-typedef map<string, string> Environment;
-
-
 void fetchDeps(Hash hash, Environment & env)
 {
     /* Read the package description file. */
@@ -538,15 +395,6 @@ void registerInstalledPkg(Hash hash, string path)
 }
 
 
-void initDB()
-{
-    createDB(nixDB, dbRefs);
-    createDB(nixDB, dbInstPkgs);
-    createDB(nixDB, dbPrebuilts);
-    createDB(nixDB, dbNetSources);
-}
-
-
 void verifyDB()
 {
     /* Check that all file references are still valid. */
diff --git a/src/test-builder-1.sh b/src/test-builder-1.sh
new file mode 100644
index 0000000000..80e23354c3
--- /dev/null
+++ b/src/test-builder-1.sh
@@ -0,0 +1,3 @@
+#! /bin/sh
+
+echo "Hello World" > $out
diff --git a/src/test-builder-2.sh b/src/test-builder-2.sh
new file mode 100644
index 0000000000..25a66532ff
--- /dev/null
+++ b/src/test-builder-2.sh
@@ -0,0 +1,5 @@
+#! /bin/sh
+
+mkdir $out || exit 1
+cd $out || exit 1
+echo "Hello World" > bla
diff --git a/src/test.cc b/src/test.cc
index cce226ba92..79468182ea 100644
--- a/src/test.cc
+++ b/src/test.cc
@@ -1,16 +1,82 @@
 #include <iostream>
 
+#include <sys/stat.h>
+#include <sys/types.h>
+
 #include "hash.hh"
+#include "util.hh"
+#include "eval.hh"
+#include "values.hh"
+#include "globals.hh"
 
-int main(int argc, char * * argv)
+
+void evalTest(Expr e)
 {
-    Hash h = hashFile("/etc/passwd");
-    
-    cout << (string) h << endl;
+    EvalResult r = evalValue(e);
+
+    char * s = ATwriteToString(r.e);
+    cout << (string) r.h << ": " << s << endl;
+}
+
+
+void runTests()
+{
+    /* Hashing. */
+    string s = "0b0ffd0538622bfe20b92c4aa57254d9";
+    Hash h = parseHash(s);
+    if ((string) h != s) abort();
+
+    try {
+        h = parseHash("blah blah");
+        abort();
+    } catch (BadRefError err) { };
+
+    try {
+        h = parseHash("0b0ffd0538622bfe20b92c4aa57254d99");
+        abort();
+    } catch (BadRefError err) { };
+
+
+    /* Set up the test environment. */
+
+    mkdir("scratch", 0777);
 
-    h = parseHash("0b0ffd0538622bfe20b92c4aa57254d9");
-    
-    cout << (string) h << endl;
+    string testDir = absPath("scratch");
+    cout << testDir << endl;
+
+    nixValues = testDir;
+    nixLogDir = testDir;
+    nixDB = testDir + "/db";
+
+    initDB();
+
+    /* Expression evaluation. */
+
+    evalTest(ATmake("Str(\"Hello World\")"));
+    evalTest(ATmake("Bool(True)"));
+    evalTest(ATmake("Bool(False)"));
+
+    Hash builder1 = addValue("./test-builder-1.sh");
+
+    evalTest(ATmake("Exec(Str(<str>), External(<str>), [])",
+        thisSystem.c_str(), ((string) builder1).c_str()));
+
+    Hash builder2 = addValue("./test-builder-2.sh");
+
+    evalTest(ATmake("Exec(Str(<str>), External(<str>), [])",
+        thisSystem.c_str(), ((string) builder2).c_str()));
+}
+
+
+int main(int argc, char * * argv)
+{
+    ATerm bottomOfStack;
+    ATinit(argc, argv, &bottomOfStack);
 
-    return 0;
+    try {
+        runTests();
+    } catch (exception & e) {
+        cerr << "error: " << e.what() << endl;
+        return 1;
+    }
 }
diff --git a/src/util.cc b/src/util.cc
index 299fc942f2..8c397aace8 100644
--- a/src/util.cc
+++ b/src/util.cc
@@ -1,47 +1,55 @@
+#include <iostream>
+
 #include "util.hh"
 
 
 string thisSystem = SYSTEM;
-string nixHomeDir = "/nix";
-string nixHomeDirEnvVar = "NIX";
 
 
+SysError::SysError(string msg)
+{
+    char * sysMsg = strerror(errno);
+    err = msg + ": " + sysMsg;
+}
+
 
-string absPath(string filename, string dir)
+string absPath(string path, string dir)
 {
-    if (filename[0] != '/') {
+    if (path[0] != '/') {
         if (dir == "") {
             char buf[PATH_MAX];
             if (!getcwd(buf, sizeof(buf)))
-                throw Error("cannot get cwd");
+                throw SysError("cannot get cwd");
             dir = buf;
         }
-        filename = dir + "/" + filename;
+        path = dir + "/" + path;
         /* !!! canonicalise */
         char resolved[PATH_MAX];
-        if (!realpath(filename.c_str(), resolved))
-            throw Error("cannot canonicalise path " + filename);
-        filename = resolved;
+        if (!realpath(path.c_str(), resolved))
+            throw SysError("cannot canonicalise path " + path);
+        path = resolved;
     }
-    return filename;
+    return path;
+}
+
+
+string dirOf(string path)
+{
+    unsigned int pos = path.rfind('/');
+    if (pos == string::npos) throw Error("invalid file name: " + path);
+    return string(path, 0, pos);
 }
 
 
-/* Return the directory part of the given path, i.e., everything
-   before the final `/'. */
-string dirOf(string s)
+string baseNameOf(string path)
 {
-    unsigned int pos = s.rfind('/');
-    if (pos == string::npos) throw Error("invalid file name");
-    return string(s, 0, pos);
+    unsigned int pos = path.rfind('/');
+    if (pos == string::npos) throw Error("invalid file name: " + path);
+    return string(path, pos + 1);
 }
 
 
-/* Return the base name of the given path, i.e., everything following
-   the final `/'. */
-string baseNameOf(string s)
+void debug(string s)
 {
-    unsigned int pos = s.rfind('/');
-    if (pos == string::npos) throw Error("invalid file name");
-    return string(s, pos + 1);
+    cerr << "debug: " << s << endl;
 }
diff --git a/src/util.hh b/src/util.hh
index d1a1956095..5b41fcea89 100644
--- a/src/util.hh
+++ b/src/util.hh
@@ -12,13 +12,21 @@ using namespace std;
 
 class Error : public exception
 {
+protected:
     string err;
 public:
+    Error() { }
     Error(string _err) { err = _err; }
-    ~Error() throw () { };
+    ~Error() throw () { }
     const char * what() const throw () { return err.c_str(); }
 };
 
+class SysError : public Error
+{
+public:
+    SysError(string msg);
+};
+
 class UsageError : public Error
 {
 public:
@@ -33,15 +41,20 @@ typedef vector<string> Strings;
 extern string thisSystem;
 
 
-/* The prefix of the Nix installation, and the environment variable
-   that can be used to override the default. */
-extern string nixHomeDir;
-extern string nixHomeDirEnvVar;
+/* Return an absolutized path, resolving paths relative to the
+   specified directory, or the current directory otherwise. */
+string absPath(string path, string dir = "");
+
+/* Return the directory part of the given path, i.e., everything
+   before the final `/'. */
+string dirOf(string path);
+
+/* Return the base name of the given path, i.e., everything following
+   the final `/'. */
+string baseNameOf(string path);
 
 
-string absPath(string filename, string dir = "");
-string dirOf(string s);
-string baseNameOf(string s);
+void debug(string s);
 
 
 #endif /* !__UTIL_H */
diff --git a/src/values.cc b/src/values.cc
new file mode 100644
index 0000000000..064203ae28
--- /dev/null
+++ b/src/values.cc
@@ -0,0 +1,100 @@
+#include "values.hh"
+#include "globals.hh"
+#include "db.hh"
+
+
+static void copyFile(string src, string dst)
+{
+    int res = system(("cat " + src + " > " + dst).c_str()); /* !!! escape */
+    if (WEXITSTATUS(res) != 0)
+        throw Error("cannot copy " + src + " to " + dst);
+}
+
+
+static string absValuePath(string s)
+{
+    return nixValues + "/" + s;
+}
+
+
+Hash addValue(string path)
+{
+    Hash hash = hashFile(path);
+
+    string name;
+    if (queryDB(nixDB, dbRefs, hash, name)) {
+        debug((string) hash + " already known");
+        return hash;
+    }
+
+    string baseName = baseNameOf(path);
+    
+    string targetName = (string) hash + "-" + baseName;
+
+    copyFile(path, absValuePath(targetName));
+
+    setDB(nixDB, dbRefs, hash, targetName);
+    
+    return hash;
+}
+
+
+#if 0
+/* Download object referenced by the given URL into the sources
+   directory.  Return the file name it was downloaded to. */
+string fetchURL(string url)
+{
+    string filename = baseNameOf(url);
+    string fullname = nixSourcesDir + "/" + filename;
+    struct stat st;
+    if (stat(fullname.c_str(), &st)) {
+        cerr << "fetching " << url << endl;
+        /* !!! quoting */
+        string shellCmd =
+            "cd " + nixSourcesDir + " && wget --quiet -N \"" + url + "\"";
+        int res = system(shellCmd.c_str());
+        if (WEXITSTATUS(res) != 0)
+            throw Error("cannot fetch " + url);
+    }
+    return fullname;
+}
+#endif
+
+
+string queryValuePath(Hash hash)
+{
+    bool checkedNet = false;
+
+    while (1) {
+
+        string name, url;
+
+        if (queryDB(nixDB, dbRefs, hash, name)) {
+            string fn = absValuePath(name);
+
+            /* Verify that the file hasn't changed. !!! race */
+            if (hashFile(fn) != hash)
+                throw Error("file " + fn + " is stale");
+
+            return fn;
+        }
+
+        throw Error("a file with hash " + (string) hash + " is requested, "
+            "but it is not known to exist locally or on the network");
+#if 0
+        if (checkedNet)
+            throw Error("consistency problem: file fetched from " + url + 
+                " should have hash " + (string) hash + ", but it doesn't");
+
+        if (!queryDB(nixDB, dbNetSources, hash, url))
+            throw Error("a file with hash " + (string) hash + " is requested, "
+                "but it is not known to exist locally or on the network");
+
+        checkedNet = true;
+        
+        fn = fetchURL(url);
+        
+        setDB(nixDB, dbRefs, hash, fn);
+#endif
+    }
+}
diff --git a/src/values.hh b/src/values.hh
new file mode 100644
index 0000000000..5dd7b89c40
--- /dev/null
+++ b/src/values.hh
@@ -0,0 +1,24 @@
+#ifndef __VALUES_H
+#define __VALUES_H
+
+#include <string>
+
+#include "hash.hh"
+
+using namespace std;
+
+
+/* Copy a value to the nixValues directory and register it in dbRefs.
+   Return the hash code of the value. */
+Hash addValue(string pathName);
+
+
+/* Obtain the path of a value with the given hash.  If a file with
+   that hash is known to exist in the local file system (as indicated
+   by the dbRefs database), we use that.  Otherwise, we attempt to
+   fetch it from the network (using dbNetSources).  We verify that the
+   file has the right hash. */
+string queryValuePath(Hash hash);
+
+
+#endif /* !__VALUES_H */