* Started removing closure store expressions, i.e., the explicit

  representation of closures as ATerms in the Nix store.  Instead, the
  file system pointer graph is now stored in the Nix database.  This
  has many advantages:

  - It greatly simplifies the implementation (we can drop the notion
    of `successors', and so on).

  - It makes registering roots for the garbage collector much easier.
    Instead of specifying the closure expression as a root, you can
    simply specify the store path that must be retained as a root.
    This could not be done previously, since there was no way to find
    the closure store expression containing a given store path.
    
  - Better traceability: it is now possible to query what paths are
    referenced by a path, and what paths refer to a path.

9 files changed, 327 insertions, 750 deletions

diff --git a/src/libstore/gc.cc b/src/libstore/gc.cc
index 9af957693..b6fb66d29 100644
--- a/src/libstore/gc.cc
+++ b/src/libstore/gc.cc
@@ -7,6 +7,7 @@
 #include <unistd.h>
 
 
+#if 0
 void followLivePaths(Path nePath, PathSet & live)
 {
     /* Just to be sure, canonicalise the path.  It is important to do
@@ -96,3 +97,4 @@ PathSet findDeadPaths(const PathSet & live, time_t minAge)
     
     return dead;
 }
+#endif
diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc
index 6dc054fb4..24a522c1e 100644
--- a/src/libstore/misc.cc
+++ b/src/libstore/misc.cc
@@ -1,16 +1,32 @@
 #include "normalise.hh"
 
 
-StoreExpr storeExprFromPath(const Path & path)
+Derivation derivationFromPath(const Path & drvPath)
 {
-    assertStorePath(path);
-    ensurePath(path);
-    ATerm t = ATreadFromNamedFile(path.c_str());
-    if (!t) throw Error(format("cannot read aterm from `%1%'") % path);
-    return parseStoreExpr(t);
+    assertStorePath(drvPath);
+    ensurePath(drvPath);
+    ATerm t = ATreadFromNamedFile(drvPath.c_str());
+    if (!t) throw Error(format("cannot read aterm from `%1%'") % drvPath);
+    return parseDerivation(t);
 }
 
 
+void computeFSClosure(const Path & storePath,
+    PathSet & paths)
+{
+    if (paths.find(storePath) != paths.end()) return;
+    paths.insert(storePath);
+
+    PathSet references;
+    queryReferences(storePath, references);
+
+    for (PathSet::iterator i = references.begin();
+         i != references.end(); ++i)
+        computeFSClosure(*i, paths);
+}
+
+
+#if 0
 PathSet storeExprRoots(const Path & nePath)
 {
     PathSet paths;
@@ -71,3 +87,4 @@ PathSet storeExprRequisites(const Path & nePath,
         paths, doneSet);
     return paths;
 }
+#endif
diff --git a/src/libstore/normalise.cc b/src/libstore/normalise.cc
index 914630b15..a01b6d801 100644
--- a/src/libstore/normalise.cc
+++ b/src/libstore/normalise.cc
@@ -62,7 +62,7 @@ protected:
     bool done;
 
     
-    Goal(Worker & _worker) : worker(_worker)
+    Goal(Worker & worker) : worker(worker)
     {
         done = false;
         nrFailed = 0;
@@ -130,10 +130,9 @@ private:
        (namely build hooks) count as occupied build slots. */
     unsigned int nrChildren;
 
-    /* Maps used to prevent multiple instantiation of a goal for the
+    /* Maps used to prevent multiple instantiations of a goal for the
        same expression / path. */
-    WeakGoalMap normalisationGoals;
-    WeakGoalMap realisationGoals;
+    WeakGoalMap derivationGoals;
     WeakGoalMap substitutionGoals;
 
 public:
@@ -142,8 +141,7 @@ public:
     ~Worker();
 
     /* Make a goal (with caching). */
-    GoalPtr makeNormalisationGoal(const Path & nePath);
-    GoalPtr makeRealisationGoal(const Path & nePath);
+    GoalPtr makeDerivationGoal(const Path & drvPath);
     GoalPtr makeSubstitutionGoal(const Path & storePath);
 
     /* Remove a dead goal. */
@@ -287,19 +285,6 @@ const char * * strings2CharPtrs(const Strings & ss)
 }
 
 
-/* Should only be called after an expression has been normalised. */
-Path queryNormalForm(const Path & nePath)
-{
-    Path nfPath;
-    if (querySuccessor(nePath, nfPath)) return nfPath;
-    /* If there is no successor, than nePath must be a normal form
-       itself. */
-    StoreExpr ne = storeExprFromPath(nePath);
-    if (ne.type != StoreExpr::neClosure) abort();
-    return nePath;
-}
-
-
 /* "Fix", or canonicalise, the meta-data of the files in a store path
    after it has been built.  In particular:
    - the last modification date on each file is set to 0 (i.e.,
@@ -358,32 +343,27 @@ void canonicalisePathMetaData(const Path & path)
 //////////////////////////////////////////////////////////////////////
 
 
-class NormalisationGoal : public Goal
+class DerivationGoal : public Goal
 {
 private:
     /* The path of the derivation store expression. */
-    Path nePath;
+    Path drvPath;
 
-    /* The store expression stored at nePath. */
-    StoreExpr expr;
+    /* The derivation store expression stored at drvPath. */
+    Derivation drv;
     
     /* The remainder is state held during the build. */
 
     /* Locks on the output paths. */
     PathLocks outputLocks;
 
-    /* Input paths, with their closure elements. */
-    ClosureElems inClosures; 
+    /* All input paths (that is, the union of FS closures of the
+       immediate input paths). */
+    PathSet inputPaths; 
 
     /* Referenceable paths (i.e., input and output paths). */
     PathSet allPaths;
 
-    /* The normal forms of the input store expressions. */
-    PathSet inputNFs;
-
-    /* The successor mappings for the input store expressions. */
-    map<Path, Path> inputSucs;
-
     /* The process ID of the builder. */
     Pid pid;
 
@@ -400,12 +380,12 @@ private:
     Pipe toHook;
     Pipe fromHook;
 
-    typedef void (NormalisationGoal::*GoalState)();
+    typedef void (DerivationGoal::*GoalState)();
     GoalState state;
     
 public:
-    NormalisationGoal(const Path & _nePath, Worker & _worker);
-    ~NormalisationGoal();
+    DerivationGoal(const Path & drvPath, Worker & worker);
+    ~DerivationGoal();
 
     void work();
 
@@ -413,7 +393,7 @@ private:
     /* The states. */
     void init();
     void haveStoreExpr();
-    void inputRealised();
+    void inputsRealised();
     void tryToBuild();
     void buildDone();
 
@@ -437,7 +417,7 @@ private:
     /* Must be called after the output paths have become valid (either
        due to a successful build or hook, or because they already
        were). */
-    void createClosure();
+    void computeClosure();
 
     /* Open a log file and a pipe to it. */
     void openLogFile();
@@ -452,19 +432,22 @@ private:
     /* Callback used by the worker to write to the log. */
     void writeLog(int fd, const unsigned char * buf, size_t count);
 
+    /* Return true iff all output paths are valid. */
+    bool allOutputsValid();
+
     string name();
 };
 
 
-NormalisationGoal::NormalisationGoal(const Path & _nePath, Worker & _worker)
-    : Goal(_worker)
+DerivationGoal::DerivationGoal(const Path & drvPath, Worker & worker)
+    : Goal(worker)
 {
-    nePath = _nePath;
-    state = &NormalisationGoal::init;
+    this->drvPath = drvPath;
+    state = &DerivationGoal::init;
 }
 
 
-NormalisationGoal::~NormalisationGoal()
+DerivationGoal::~DerivationGoal()
 {
     if (pid != -1) worker.childTerminated(pid);
     
@@ -478,75 +461,70 @@ NormalisationGoal::~NormalisationGoal()
 }
 
 
-void NormalisationGoal::work()
+void DerivationGoal::work()
 {
     (this->*state)();
 }
 
 
-void NormalisationGoal::init()
+void DerivationGoal::init()
 {
     trace("init");
 
-    /* If we already have a successor, then we are done already; don't
-       add the expression as a goal. */
-    Path nfPath;
-    if (querySuccessor(nePath, nfPath)) {
-        amDone();
-        return;
-    }
-
     /* The first thing to do is to make sure that the store expression
        exists.  If it doesn't, it may be created through a
        substitute. */
-    addWaitee(worker.makeSubstitutionGoal(nePath));
+    addWaitee(worker.makeSubstitutionGoal(drvPath));
 
-    state = &NormalisationGoal::haveStoreExpr;
+    state = &DerivationGoal::haveStoreExpr;
 }
 
 
-void NormalisationGoal::haveStoreExpr()
+void DerivationGoal::haveStoreExpr()
 {
-    trace("loading store expression");
+    trace("loading derivation");
 
     if (nrFailed != 0) {
         printMsg(lvlError,
-            format("cannot normalise missing store expression `%1%'")
-            % nePath);
+            format("cannot build missing derivation `%1%'")
+            % drvPath);
         amDone(false);
         return;
     }
 
-    assert(isValidPath(nePath));
+    assert(isValidPath(drvPath));
 
-    /* Get the store expression. */
-    expr = storeExprFromPath(nePath);
+    /* Get the derivation. */
+    drv = derivationFromPath(drvPath);
 
-    /* If this is a normal form (i.e., a closure) we are also done. */
-    if (expr.type == StoreExpr::neClosure) {
-        amDone();
+    /* If all the outputs already exist, then we're done. */
+    if (allOutputsValid()) {
+        amDone(true);
         return;
     }
-    assert(expr.type == StoreExpr::neDerivation);
 
-    /* Inputs must be realised before we can build this goal. */
-    for (PathSet::iterator i = expr.derivation.inputs.begin();
-         i != expr.derivation.inputs.end(); ++i)
-        addWaitee(worker.makeRealisationGoal(*i));
+    /* Inputs must be built before we can build this goal. */
+    for (PathSet::iterator i = drv.inputDrvs.begin();
+         i != drv.inputDrvs.end(); ++i)
+        addWaitee(worker.makeDerivationGoal(*i));
 
-    state = &NormalisationGoal::inputRealised;
+    for (PathSet::iterator i = drv.inputSrcs.begin();
+         i != drv.inputSrcs.end(); ++i)
+        addWaitee(worker.makeSubstitutionGoal(*i));
+
+    state = &DerivationGoal::inputsRealised;
 }
 
 
-void NormalisationGoal::inputRealised()
+void DerivationGoal::inputsRealised()
 {
     trace("all inputs realised");
 
     if (nrFailed != 0) {
         printMsg(lvlError,
-            format("cannot normalise derivation `%1%': "
-                "%2% closure element(s) could not be realised")
-            % nePath % nrFailed);
+            format("cannot build derivation `%1%': "
+                "%2% inputs could not be realised")
+            % drvPath % nrFailed);
         amDone(false);
         return;
     }
@@ -554,12 +532,12 @@ void NormalisationGoal::inputRealised()
     /* Okay, try to build.  Note that here we don't wait for a build
        slot to become available, since we don't need one if there is a
        build hook. */
-    state = &NormalisationGoal::tryToBuild;
+    state = &DerivationGoal::tryToBuild;
     worker.wakeUp(shared_from_this());
 }
 
 
-void NormalisationGoal::tryToBuild()
+void DerivationGoal::tryToBuild()
 {
     trace("trying to build");
 
@@ -570,7 +548,7 @@ void NormalisationGoal::tryToBuild()
             case rpAccept:
                 /* Yes, it has started doing so.  Wait until we get
                    EOF from the hook. */
-                state = &NormalisationGoal::buildDone;
+                state = &DerivationGoal::buildDone;
                 return;
             case rpPostpone:
                 /* Not now; wait until at least one child finishes. */
@@ -580,7 +558,7 @@ void NormalisationGoal::tryToBuild()
                 /* We should do it ourselves. */
                 break;
             case rpDone:
-                /* Somebody else did it (there is a successor now). */
+                /* Somebody else did it. */
                 amDone();
                 return;
         }
@@ -591,8 +569,8 @@ void NormalisationGoal::tryToBuild()
             return;
         }
 
-        /* Acquire locks and such.  If we then see that there now is a
-           successor, we're done. */
+        /* Acquire locks and such.  If we then see that the build has
+           been done by somebody else, we're done. */
         if (!prepareBuild()) {
             amDone();
             return;
@@ -609,11 +587,11 @@ void NormalisationGoal::tryToBuild()
 
     /* This state will be reached when we get EOF on the child's
        log pipe. */
-    state = &NormalisationGoal::buildDone;
+    state = &DerivationGoal::buildDone;
 }
 
 
-void NormalisationGoal::buildDone()
+void DerivationGoal::buildDone()
 {
     trace("build done");
 
@@ -634,23 +612,23 @@ void NormalisationGoal::buildDone()
     /* Close the log file. */
     fdLogFile.close();
 
-    debug(format("builder process for `%1%' finished") % nePath);
+    debug(format("builder process for `%1%' finished") % drvPath);
 
     /* Check the exit status. */
     if (!statusOk(status)) {
         deleteTmpDir(false);
         printMsg(lvlError, format("builder for `%1%' %2%")
-            % nePath % statusToString(status));
+            % drvPath % statusToString(status));
         amDone(false);
         return;
     }
     
     deleteTmpDir(true);
 
-    /* Compute a closure store expression, and register it as our
-       successor. */
+    /* Compute the FS closure of the outputs and register them as
+       being valid. */
     try {
-        createClosure();
+        computeClosure();
     } catch (BuildError & e) {
         printMsg(lvlError, e.msg());
         amDone(false);
@@ -725,7 +703,7 @@ string showPaths(const PathSet & paths)
 }
 
 
-NormalisationGoal::HookReply NormalisationGoal::tryBuildHook()
+DerivationGoal::HookReply DerivationGoal::tryBuildHook()
 {
     Path buildHook = getEnv("NIX_BUILD_HOOK");
     if (buildHook == "") return rpDecline;
@@ -757,8 +735,8 @@ NormalisationGoal::HookReply NormalisationGoal::tryBuildHook()
             execl(buildHook.c_str(), buildHook.c_str(),
                 (worker.canBuildMore() ? (string) "1" : "0").c_str(),
                 thisSystem.c_str(),
-                expr.derivation.platform.c_str(),
-                nePath.c_str(), 0);
+                drv.platform.c_str(),
+                drvPath.c_str(), 0);
             
             throw SysError(format("executing `%1%'") % buildHook);
             
@@ -799,8 +777,8 @@ NormalisationGoal::HookReply NormalisationGoal::tryBuildHook()
 
     else if (reply == "accept") {
 
-        /* Acquire locks and such.  If we then see that there now is a
-           successor, we're done. */
+        /* Acquire locks and such.  If we then see that the output
+           paths are now valid, we're done. */
         if (!prepareBuild()) {
             /* Tell the hook to exit. */
             writeLine(toHook.writeSide, "cancel");
@@ -808,39 +786,28 @@ NormalisationGoal::HookReply NormalisationGoal::tryBuildHook()
             return rpDone;
         }
 
-        printMsg(lvlInfo, format("running hook to build path `%1%'")
-            % showPaths(outputPaths(expr.derivation.outputs)));
+        printMsg(lvlInfo, format("running hook to build path(s) %1%")
+            % showPaths(outputPaths(drv.outputs)));
         
         /* Write the information that the hook needs to perform the
            build, i.e., the set of input paths (including closure
-           expressions), the set of output paths, and the successor
-           mappings for the input expressions. */
+           expressions), the set of output paths, and [!!!]. */
         
         Path inputListFN = tmpDir + "/inputs";
         Path outputListFN = tmpDir + "/outputs";
-        Path successorsListFN = tmpDir + "/successors";
 
         string s;
-        for (ClosureElems::iterator i = inClosures.begin();
-             i != inClosures.end(); ++i)
-            s += i->first + "\n";
-        for (PathSet::iterator i = inputNFs.begin();
-             i != inputNFs.end(); ++i)
+        for (PathSet::iterator i = inputPaths.begin();
+             i != inputPaths.end(); ++i)
             s += *i + "\n";
         writeStringToFile(inputListFN, s);
         
         s = "";
-        for (DerivationOutputs::iterator i = expr.derivation.outputs.begin();
-             i != expr.derivation.outputs.end(); ++i)
+        for (DerivationOutputs::iterator i = drv.outputs.begin();
+             i != drv.outputs.end(); ++i)
             s += i->second.path + "\n";
         writeStringToFile(outputListFN, s);
         
-        s = "";
-        for (map<Path, Path>::iterator i = inputSucs.begin();
-             i != inputSucs.end(); ++i)
-            s += i->first + " " + i->second + "\n";
-        writeStringToFile(successorsListFN, s);
-
         /* Tell the hook to proceed. */ 
         writeLine(toHook.writeSide, "okay");
 
@@ -851,7 +818,7 @@ NormalisationGoal::HookReply NormalisationGoal::tryBuildHook()
 }
 
 
-void NormalisationGoal::terminateBuildHook()
+void DerivationGoal::terminateBuildHook()
 {
     /* !!! drain stdout of hook */
     debug("terminating build hook");
@@ -866,25 +833,23 @@ void NormalisationGoal::terminateBuildHook()
 }
 
 
-bool NormalisationGoal::prepareBuild()
+bool DerivationGoal::prepareBuild()
 {
     /* Obtain locks on all output paths.  The locks are automatically
        released when we exit this function or Nix crashes. */
     /* !!! BUG: this could block, which is not allowed. */
-    outputLocks.lockPaths(outputPaths(expr.derivation.outputs));
+    outputLocks.lockPaths(outputPaths(drv.outputs));
 
-    /* Now check again whether there is a successor.  This is because
+    /* Now check again whether the outputs are valid.  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 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 nfPath;
-    if (querySuccessor(nePath, nfPath)) {
-        debug(format("skipping build of expression `%1%', someone beat us to it")
-            % nePath);
+       reuse its results.  (Strictly speaking the first check 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. */
+    if (allOutputsValid()) {
+        debug(format("skipping build of derivation `%1%', someone beat us to it")
+            % drvPath);
         outputLocks.setDeletion(true);
         return false;
     }
@@ -893,39 +858,45 @@ bool NormalisationGoal::prepareBuild()
        running the build hook. */
     
     /* The outputs are referenceable paths. */
-    for (DerivationOutputs::iterator i = expr.derivation.outputs.begin();
-         i != expr.derivation.outputs.end(); ++i)
+    for (DerivationOutputs::iterator i = drv.outputs.begin();
+         i != drv.outputs.end(); ++i)
     {
         debug(format("building path `%1%'") % i->second.path);
         allPaths.insert(i->second.path);
     }
-    
-    /* Get information about the inputs (these all exist now). */
-    for (PathSet::iterator i = expr.derivation.inputs.begin();
-         i != expr.derivation.inputs.end(); ++i)
+
+    /* Determine the full set of input paths. */
+
+    /* First, the input derivations. */
+    for (PathSet::iterator i = drv.inputDrvs.begin();
+         i != drv.inputDrvs.end(); ++i)
     {
-        checkInterrupt();
-        Path nePath = *i;
-        Path nfPath = queryNormalForm(nePath);
-        inputNFs.insert(nfPath);
-        if (nfPath != nePath) inputSucs[nePath] = nfPath;
-        /* !!! nfPath should be a root of the garbage collector while
-           we are building */
-        StoreExpr ne = storeExprFromPath(nfPath);
-        if (ne.type != StoreExpr::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);
-	}
+        /* Add all the output closures of the input derivation `*i' as
+           input paths.  !!!  there should be a way to indicate
+           specific outputs. */
+        /* !!! is `*i' present? */
+        assert(isValidPath(*i));
+        Derivation inDrv = derivationFromPath(*i);
+        for (DerivationOutputs::iterator j = inDrv.outputs.begin();
+             j != inDrv.outputs.end(); ++j)
+            computeFSClosure(j->second.path, inputPaths);
     }
 
+    for (PathSet::iterator i = inputPaths.begin(); i != inputPaths.end(); ++i)
+        debug(format("INPUT %1%") % *i);
+
+    allPaths.insert(inputPaths.begin(), inputPaths.end());
+
+    /* Second, the input sources. */
+    for (PathSet::iterator i = drv.inputSrcs.begin();
+         i != drv.inputSrcs.end(); ++i)
+        computeFSClosure(*i, inputPaths);
+
     /* We can skip running the builder if all output paths are already
        valid. */
     bool fastBuild = true;
-    for (DerivationOutputs::iterator i = expr.derivation.outputs.begin();
-         i != expr.derivation.outputs.end(); ++i)
+    for (DerivationOutputs::iterator i = drv.outputs.begin();
+         i != drv.outputs.end(); ++i)
         if (!isValidPath(i->second.path)) { 
             fastBuild = false;
             break;
@@ -933,7 +904,7 @@ bool NormalisationGoal::prepareBuild()
 
     if (fastBuild) {
         printMsg(lvlChatty, format("skipping build; output paths already exist"));
-        createClosure();
+        computeClosure();
         return false;
     }
 
@@ -941,21 +912,21 @@ bool NormalisationGoal::prepareBuild()
 }
 
 
-void NormalisationGoal::startBuilder()
+void DerivationGoal::startBuilder()
 {
     startNest(nest, lvlInfo,
-        format("building path `%1%'") % showPaths(outputPaths(expr.derivation.outputs)))
+        format("building path(s) `%1%'") % showPaths(outputPaths(drv.outputs)))
     
     /* Right platform? */
-    if (expr.derivation.platform != thisSystem)
+    if (drv.platform != thisSystem)
         throw BuildError(
             format("a `%1%' is required to build `%3%', but I am a `%2%'")
-            % expr.derivation.platform % thisSystem % nePath);
+            % drv.platform % thisSystem % drvPath);
 
     /* If any of the outputs already exist but are not registered,
        delete them. */
-    for (DerivationOutputs::iterator i = expr.derivation.outputs.begin(); 
-         i != expr.derivation.outputs.end(); ++i)
+    for (DerivationOutputs::iterator i = drv.outputs.begin(); 
+         i != drv.outputs.end(); ++i)
     {
         Path path = i->second.path;
         if (isValidPath(path))
@@ -990,8 +961,8 @@ void NormalisationGoal::startBuilder()
     env["NIX_STORE"] = nixStore;
 
     /* Add all bindings specified in the derivation expression. */
-    for (StringPairs::iterator i = expr.derivation.env.begin();
-         i != expr.derivation.env.end(); ++i)
+    for (StringPairs::iterator i = drv.env.begin();
+         i != drv.env.end(); ++i)
         env[i->first] = i->second;
 
     /* Create a temporary directory where the build will take
@@ -1007,7 +978,7 @@ void NormalisationGoal::startBuilder()
 
     /* Run the builder. */
     printMsg(lvlChatty, format("executing builder `%1%'") %
-        expr.derivation.builder);
+        drv.builder);
 
     /* Create the log file and pipe. */
     openLogFile();
@@ -1032,8 +1003,8 @@ void NormalisationGoal::startBuilder()
             initChild();
 
             /* Fill in the arguments. */
-            Strings args(expr.derivation.args);
-            args.push_front(baseNameOf(expr.derivation.builder));
+            Strings args(drv.args);
+            args.push_front(baseNameOf(drv.builder));
             const char * * argArr = strings2CharPtrs(args);
 
             /* Fill in the environment. */
@@ -1044,11 +1015,11 @@ void NormalisationGoal::startBuilder()
             const char * * envArr = strings2CharPtrs(envStrs);
 
             /* Execute the program.  This should not return. */
-            execve(expr.derivation.builder.c_str(),
+            execve(drv.builder.c_str(),
                 (char * *) argArr, (char * *) envArr);
 
             throw SysError(format("executing `%1%'")
-                % expr.derivation.builder);
+                % drv.builder);
             
         } catch (exception & e) {
             cerr << format("build error: %1%\n") % e.what();
@@ -1064,29 +1035,25 @@ void NormalisationGoal::startBuilder()
 }
 
 
-void NormalisationGoal::createClosure()
+void DerivationGoal::computeClosure()
 {
-    /* The resulting closure expression. */
-    StoreExpr nf;
-    nf.type = StoreExpr::neClosure;
-    
     startNest(nest, lvlTalkative,
-        format("computing closure for `%1%'") % nePath);
+        format("determining closure for `%1%'") % drvPath);
+
+    map<Path, PathSet> allReferences;
     
     /* 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 (DerivationOutputs::iterator i = expr.derivation.outputs.begin(); 
-         i != expr.derivation.outputs.end(); ++i)
+    for (DerivationOutputs::iterator i = drv.outputs.begin(); 
+         i != drv.outputs.end(); ++i)
     {
         Path path = i->second.path;
         if (!pathExists(path)) {
             throw BuildError(
                 format("builder for `%1%' failed to produce output path `%2%'")
-                % nePath % path);
+                % drvPath % path);
         }
-        nf.closure.roots.insert(path);
 
         /* Check that fixed-output derivations produced the right
            outputs (i.e., the content hash should match the specified
@@ -1117,101 +1084,67 @@ void NormalisationGoal::createClosure()
 
 	/* For this output path, find the references to other paths contained
 	   in it. */
-        startNest(nest2, lvlChatty,
-            format("scanning for store references in `%1%'") % path);
-        Strings refPaths;
+        PathSet references;
         if (!pathExists(path + "/nix-support/no-scan")) {
-            refPaths = filterReferences(path, 
-                Strings(allPaths.begin(), allPaths.end()));
-        }
-        nest2.close();
-
-	/* 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). */
-        PathSet outputPaths = ::outputPaths(expr.derivation.outputs);
-        for (Paths::iterator j = refPaths.begin();
-	     j != refPaths.end(); ++j)
-	{
-            checkInterrupt();
-	    Path path = *j;
-	    elem.refs.insert(path);
-            if (inClosures.find(path) != inClosures.end())
-                usedPaths.insert(path);
-	    else if (outputPaths.find(path) == outputPaths.end())
-		abort();
+            startNest(nest2, lvlChatty,
+                format("scanning for store references in `%1%'") % path);
+            Paths references2;
+            references2 = filterReferences(path, 
+                Paths(allPaths.begin(), allPaths.end()));
+            references = PathSet(references2.begin(), references2.end());
+
+            /* For debugging, print out the referenced and
+               unreferenced paths. */
+            for (PathSet::iterator i = inputPaths.begin();
+                 i != inputPaths.end(); ++i)
+            {
+                PathSet::iterator j = references.find(*i);
+                if (j == references.end())
+                    debug(format("unreferenced input: `%1%'") % *i);
+                else
+                    debug(format("referenced input: `%1%'") % *i);
+            }
+            
+            nest2.close();
         }
 
-        nf.closure.elems[path] = elem;
+        allReferences[path] = references;
     }
 
-    /* Close the closure.  That is, for any referenced path, add the paths
-       referenced by it. */
-    PathSet donePaths;
-
-    while (!usedPaths.empty()) {
-        checkInterrupt();
-	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("unreferenced input: `%1%'") % i->first);
-        else
-            debug(format("referenced input: `%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 = unparseStoreExpr(nf);
-    Path nfPath = writeTerm(nfTerm, "s");
-
-    /* Register each output 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. */
+    /* Register each output path as valid, and register the sets of
+       paths referenced by each of them.  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.
+
+       The reason that we do the transaction here and not on the fly
+       while we are scanning (above) is so that we don't hold database
+       locks for too long. */
     Transaction txn;
     createStoreTransaction(txn);
-    for (DerivationOutputs::iterator i = expr.derivation.outputs.begin(); 
-         i != expr.derivation.outputs.end(); ++i)
+    for (DerivationOutputs::iterator i = drv.outputs.begin(); 
+         i != drv.outputs.end(); ++i)
+    {
         registerValidPath(txn, i->second.path);
-    registerSuccessor(txn, nePath, nfPath);
+        setReferences(txn, i->second.path,
+            allReferences[i->second.path]);
+    }
     txn.commit();
 
     /* It is now safe to delete the lock files, since all future
-       lockers will see the successor; they will not create new lock
-       files with the same names as the old (unlinked) lock files. */
+       lockers will see that the output paths are valid; they will not
+       create new lock files with the same names as the old (unlinked)
+       lock files. */
     outputLocks.setDeletion(true);
 }
 
 
-void NormalisationGoal::openLogFile()
+void DerivationGoal::openLogFile()
 {
     /* Create a log file. */
-    Path logFileName = nixLogDir + "/" + baseNameOf(nePath);
+    Path logFileName = nixLogDir + "/" + baseNameOf(drvPath);
     fdLogFile = open(logFileName.c_str(),
         O_CREAT | O_WRONLY | O_TRUNC, 0666);
     if (fdLogFile == -1)
@@ -1222,7 +1155,7 @@ void NormalisationGoal::openLogFile()
 }
 
 
-void NormalisationGoal::initChild()
+void DerivationGoal::initChild()
 {
     commonChildInit(logPipe);
     
@@ -1251,13 +1184,13 @@ void NormalisationGoal::initChild()
 }
 
 
-void NormalisationGoal::deleteTmpDir(bool force)
+void DerivationGoal::deleteTmpDir(bool force)
 {
     if (tmpDir != "") {
         if (keepFailed && !force)
 	    printMsg(lvlError, 
 		format("builder for `%1%' failed; keeping build directory `%2%'")
-                % nePath % tmpDir);
+                % drvPath % tmpDir);
         else
             deletePath(tmpDir);
         tmpDir = "";
@@ -1265,7 +1198,7 @@ void NormalisationGoal::deleteTmpDir(bool force)
 }
 
 
-void NormalisationGoal::writeLog(int fd,
+void DerivationGoal::writeLog(int fd,
     const unsigned char * buf, size_t count)
 {
     assert(fd == logPipe.readSide);
@@ -1273,179 +1206,27 @@ void NormalisationGoal::writeLog(int fd,
 }
 
 
-string NormalisationGoal::name()
-{
-    return (format("normalisation of `%1%'") % nePath).str();
-}
-
-
-
-//////////////////////////////////////////////////////////////////////
-
-
-class RealisationGoal : public Goal
-{
-private:
-    /* The path of the store expression. */
-    Path nePath;
-
-    /* The normal form. */
-    Path nfPath;
-
-    /* Whether we should try to delete a broken successor mapping. */
-    bool tryFallback;
-
-    /* The store expression stored at nePath. */
-    StoreExpr expr;
-    
-    typedef void (RealisationGoal::*GoalState)();
-    GoalState state;
-    
-public:
-    RealisationGoal(const Path & _nePath, Worker & _worker);
-    ~RealisationGoal();
-
-    void work();
-    
-    /* The states. */
-    void init();
-    void isNormalised();
-    void haveStoreExpr();
-    void elemFinished();
-
-    void fallBack(const format & error);
-    
-    string name();
-};
-
-
-RealisationGoal::RealisationGoal(const Path & _nePath, Worker & _worker)
-    : Goal(_worker)
-{
-    nePath = _nePath;
-    tryFallback = ::tryFallback;
-    state = &RealisationGoal::init;
-}
-
-
-RealisationGoal::~RealisationGoal()
-{
-}
-
-
-void RealisationGoal::work()
-{
-    (this->*state)();
-}
-
-
-void RealisationGoal::init()
+bool DerivationGoal::allOutputsValid()
 {
-    trace("init");
+    unsigned int nrValid = 0;
+    for (DerivationOutputs::iterator i = drv.outputs.begin();
+         i != drv.outputs.end(); ++i)
+        if (isValidPath(i->second.path)) nrValid++;
 
-    if (querySuccessor(nePath, nfPath)) {
-        nrFailed = 0;
-        isNormalised();
-        return;
+    if (nrValid != 0) {
+        if (nrValid == drv.outputs.size()) return true;
+        throw Error(
+            format("derivation `%1%' is blocked by its output paths")
+            % drvPath);
     }
 
-    /* First normalise the expression (which is a no-op if the
-       expression is already a closure). */
-    addWaitee(worker.makeNormalisationGoal(nePath));
-
-    /* Since there is no successor right now, the normalisation goal
-       will perform an actual build.  So there is no sense in trying a
-       fallback if the realisation of the closure fails (it can't
-       really fail). */
-    tryFallback = false;
-
-    state = &RealisationGoal::isNormalised;
+    return false;
 }
 
 
-void RealisationGoal::isNormalised()
+string DerivationGoal::name()
 {
-    trace("has been normalised");
-
-    if (nrFailed != 0) {
-        amDone(false);
-        return;
-    }
-
-    nfPath = queryNormalForm(nePath);
-
-    /* Now make sure that the store expression exists.  If it doesn't,
-       it may be created through a substitute. */
-    addWaitee(worker.makeSubstitutionGoal(nfPath));
-
-    state = &RealisationGoal::haveStoreExpr;
-}
-
-
-void RealisationGoal::haveStoreExpr()
-{
-    trace("loading store expression");
-
-    if (nrFailed != 0) {
-        fallBack(format("cannot realise closure `%1%' since that file is missing") % nfPath);
-        return;
-    }
-
-    assert(isValidPath(nfPath));
-
-    /* Get the store expression. */
-    expr = storeExprFromPath(nfPath);
-
-    /* If this is a normal form (i.e., a closure) we are also done. */
-    if (expr.type != StoreExpr::neClosure)
-        throw Error(format("expected closure in `%1%'") % nfPath);
-
-    /* Each path in the closure should exist, or should be creatable
-       through a substitute. */
-    for (ClosureElems::const_iterator i = expr.closure.elems.begin();
-         i != expr.closure.elems.end(); ++i)
-        addWaitee(worker.makeSubstitutionGoal(i->first));
-    
-    state = &RealisationGoal::elemFinished;
-}
-
-
-void RealisationGoal::elemFinished()
-{
-    trace("all closure elements present");
-
-    if (nrFailed != 0) {
-        fallBack(
-            format("cannot realise closure `%1%': "
-                "%2% closure element(s) are not present "
-                "and could not be substituted")
-            % nfPath % nrFailed);
-        return;
-    }
-
-    amDone();
-}
-
-
-void RealisationGoal::fallBack(const format & error)
-{
-    if (tryFallback && nePath != nfPath) {
-        printMsg(lvlError, format("%1%; trying to normalise derivation instead")
-            % error);
-        tryFallback = false;
-        unregisterSuccessor(nePath);
-        nrFailed = 0;
-        init();
-    } else {
-        printMsg(lvlError, format("%1%; maybe `--fallback' will help") % error);
-        amDone(false);
-    }
-}
-
-
-string RealisationGoal::name()
-{
-    return (format("realisation of `%1%'") % nePath).str();
+    return (format("building of `%1%'") % drvPath).str();
 }
 
 
@@ -1478,7 +1259,7 @@ private:
     GoalState state;
 
 public:
-    SubstitutionGoal(const Path & _nePath, Worker & _worker);
+    SubstitutionGoal(const Path & storePath, Worker & worker);
     ~SubstitutionGoal();
 
     void work();
@@ -1496,10 +1277,10 @@ public:
 };
 
 
-SubstitutionGoal::SubstitutionGoal(const Path & _storePath, Worker & _worker)
-    : Goal(_worker)
+SubstitutionGoal::SubstitutionGoal(const Path & storePath, Worker & worker)
+    : Goal(worker)
 {
-    storePath = _storePath;
+    this->storePath = storePath;
     state = &SubstitutionGoal::init;
 }
 
@@ -1717,7 +1498,7 @@ private:
     bool success;
     
 public:
-    PseudoGoal(Worker & _worker) : Goal(_worker)
+    PseudoGoal(Worker & worker) : Goal(worker)
     {
         success = true;
     }
@@ -1786,15 +1567,9 @@ static GoalPtr addGoal(const Path & path,
 }
 
 
-GoalPtr Worker::makeNormalisationGoal(const Path & nePath)
-{
-    return addGoal<NormalisationGoal>(nePath, *this, normalisationGoals);
-}
-
-
-GoalPtr Worker::makeRealisationGoal(const Path & nePath)
+GoalPtr Worker::makeDerivationGoal(const Path & nePath)
 {
-    return addGoal<RealisationGoal>(nePath, *this, realisationGoals);
+    return addGoal<DerivationGoal>(nePath, *this, derivationGoals);
 }
 
 
@@ -1815,8 +1590,7 @@ static void removeGoal(GoalPtr goal, WeakGoalMap & goalMap)
 void Worker::removeGoal(GoalPtr goal)
 {
     topGoals.erase(goal);
-    ::removeGoal(goal, normalisationGoals);
-    ::removeGoal(goal, realisationGoals);
+    ::removeGoal(goal, derivationGoals);
     ::removeGoal(goal, substitutionGoals);
 }
 
@@ -1996,27 +1770,13 @@ void Worker::waitForInput()
 //////////////////////////////////////////////////////////////////////
 
 
-Path normaliseStoreExpr(const Path & nePath)
+void buildDerivation(const Path & drvPath)
 {
-    startNest(nest, lvlDebug, format("normalising `%1%'") % nePath);
+    startNest(nest, lvlDebug, format("building `%1%'") % drvPath);
 
     Worker worker;
-    if (!worker.run(worker.makeNormalisationGoal(nePath)))
-        throw Error(format("normalisation of store expression `%1%' failed") % nePath);
-
-    return queryNormalForm(nePath);
-}
-
-
-Path realiseStoreExpr(const Path & nePath)
-{
-    startNest(nest, lvlDebug, format("realising `%1%'") % nePath);
-
-    Worker worker;
-    if (!worker.run(worker.makeRealisationGoal(nePath)))
-        throw Error(format("realisation of store expression `%1%' failed") % nePath);
-
-    return queryNormalForm(nePath);
+    if (!worker.run(worker.makeDerivationGoal(drvPath)))
+        throw Error(format("build of derivation `%1%' failed") % drvPath);
 }
 
 
diff --git a/src/libstore/normalise.hh b/src/libstore/normalise.hh
index 7b0835b45..2a084b7ed 100644
--- a/src/libstore/normalise.hh
+++ b/src/libstore/normalise.hh
@@ -4,28 +4,31 @@
 #include "storeexpr.hh"
 
 
-/* Normalise a store 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 normaliseStoreExpr(const Path & nePath);
-
-/* Realise a store expression.  If the expression is a derivation, it
-   is first normalised into a closure.  The closure is then realised
-   in the file system (i.e., it is ensured that each path in the
-   closure exists in the file system, if necessary by using the
-   substitute mechanism).  Returns the normal form of the expression
-   (i.e., its closure expression). */
-Path realiseStoreExpr(const Path & nePath);
+/* Perform the specified derivation, if necessary.  That is, do
+   whatever is necessary to create the output paths of the
+   derivation.  If the output paths already exists, we're done.  If
+   they have substitutes, we can use those instead.  Otherwise, the
+   build action described by the derivation is performed, after
+   recursively building any sub-derivations. */
+void buildDerivation(const Path & drvPath);
 
 /* Ensure that a path exists, possibly by instantiating it by
    realising a substitute. */
-void ensurePath(const Path & path);
+void ensurePath(const Path & storePath);
 
-/* Read a store expression, after ensuring its existence through
-   ensurePath(). */
-StoreExpr storeExprFromPath(const Path & path);
+/* Read a derivation store expression, after ensuring its existence
+   through ensurePath(). */
+Derivation derivationFromPath(const Path & drvPath);
 
+
+/* Places in `paths' the set of all store paths in the file system
+   closure of `storePath'; that is, all paths than can be directly or
+   indirectly reached from it.  `paths' is not cleared. */
+void computeFSClosure(const Path & storePath,
+    PathSet & paths);
+
+
+#if 0
 /* Get the list of root (output) paths of the given store
    expression. */
 PathSet storeExprRoots(const Path & nePath);
@@ -39,6 +42,7 @@ PathSet storeExprRoots(const Path & nePath);
    successors. */
 PathSet storeExprRequisites(const Path & nePath,
     bool includeExprs, bool includeSuccessors);
+#endif
 
 
 #endif /* !__NORMALISE_H */
diff --git a/src/libstore/store.cc b/src/libstore/store.cc
index 0d89f7a5d..51e2e7e7d 100644
--- a/src/libstore/store.cc
+++ b/src/libstore/store.cc
@@ -23,23 +23,18 @@ static Database nixDB;
    is, produced by a succesful build). */
 static TableId dbValidPaths = 0;
 
-/* dbSuccessors :: Path -> Path
+/* dbReferences :: 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$.
+   This table lists the outgoing file system references for each
+   output path that has been built by a Nix derivation.  These are
+   found by scanning the path for the hash components of input
+   paths. */
+static TableId dbReferences = 0;
 
-   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 = 0;
-
-/* dbSuccessorsRev :: Path -> [Path]
+/* dbReferers :: Path -> [Path]
 
-   The reverse mapping of dbSuccessors (i.e., it stores the
-   predecessors of a Nix expression).
-*/
-static TableId dbSuccessorsRev = 0;
+   This table is just the reverse mapping of dbReferences. */
+static TableId dbReferers = 0;
 
 /* dbSubstitutes :: Path -> [[Path]]
 
@@ -76,8 +71,8 @@ void openDB()
         return;
     }
     dbValidPaths = nixDB.openTable("validpaths");
-    dbSuccessors = nixDB.openTable("successors");
-    dbSuccessorsRev = nixDB.openTable("successors-rev");
+    dbReferences = nixDB.openTable("references");
+    dbReferers = nixDB.openTable("referers");
     dbSubstitutes = nixDB.openTable("substitutes");
 }
 
@@ -199,81 +194,31 @@ bool isValidPath(const Path & path)
 }
 
 
-static bool isUsablePathTxn(const Path & path, const Transaction & txn)
-{
-    if (isValidPathTxn(path, txn)) return true;
-    Paths subs;
-    nixDB.queryStrings(txn, dbSubstitutes, path, subs);
-    return subs.size() > 0;
-}
-
-
-void registerSuccessor(const Transaction & txn,
-    const Path & srcPath, const Path & sucPath)
+void setReferences(const Transaction & txn, const Path & storePath,
+    const PathSet & references)
 {
-    assertStorePath(srcPath);
-    assertStorePath(sucPath);
-    
-    if (!isUsablePathTxn(sucPath, txn))	throw Error(
-	format("path `%1%' cannot be a successor, since it is not usable")
-	% sucPath);
+    nixDB.setStrings(txn, dbReferences, storePath,
+        Paths(references.begin(), references.end()));
 
-    Path known;
-    if (nixDB.queryString(txn, dbSuccessors, srcPath, known) &&
-        known != sucPath)
+    /* Update the referers mappings of all referenced paths. */
+    for (PathSet::const_iterator i = references.begin();
+         i != references.end(); ++i)
     {
-        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);
-}
-
-
-void unregisterSuccessor(const Path & srcPath)
-{
-    assertStorePath(srcPath);
-
-    Transaction txn(nixDB);
-
-    Path sucPath;
-    if (!nixDB.queryString(txn, dbSuccessors, srcPath, sucPath)) {
-        txn.abort();
-        return;
+        Paths referers;
+        nixDB.queryStrings(txn, dbReferers, *i, referers);
+        PathSet referers2(referers.begin(), referers.end());
+        referers2.insert(storePath);
+        nixDB.setStrings(txn, dbReferers, *i,
+            Paths(referers2.begin(), referers2.end()));
     }
-    nixDB.delPair(txn, dbSuccessors, srcPath);
-
-    Paths revs;
-    nixDB.queryStrings(txn, dbSuccessorsRev, sucPath, revs);
-    Paths::iterator i = find(revs.begin(), revs.end(), srcPath);
-    assert(i != revs.end());
-    revs.erase(i);
-    nixDB.setStrings(txn, dbSuccessorsRev, sucPath, revs);
-
-    txn.commit();
-}
-
-
-bool querySuccessor(const Path & srcPath, Path & sucPath)
-{
-    return nixDB.queryString(noTxn, dbSuccessors, srcPath, sucPath);
 }
 
 
-Paths queryPredecessors(const Path & sucPath)
+void queryReferences(const Path & storePath, PathSet & references)
 {
-    Paths revs;
-    nixDB.queryStrings(noTxn, dbSuccessorsRev, sucPath, revs);
-    return revs;
+    Paths references2;
+    nixDB.queryStrings(noTxn, dbReferences, storePath, references2);
+    references.insert(references2.begin(), references2.end());
 }
 
 
@@ -355,18 +300,6 @@ Substitutes querySubstitutes(const Path & srcPath)
 }
 
 
-static void unregisterPredecessors(const Path & path, Transaction & txn)
-{
-    /* Remove any successor mappings to this path (but not *from*
-       it). */
-    Paths revs;
-    nixDB.queryStrings(txn, dbSuccessorsRev, path, revs);
-    for (Paths::iterator i = revs.begin(); i != revs.end(); ++i)
-        nixDB.delPair(txn, dbSuccessors, *i);
-    nixDB.delPair(txn, dbSuccessorsRev, path);
-}
- 
-
 void clearSubstitutes()
 {
     Transaction txn(nixDB);
@@ -375,16 +308,6 @@ void clearSubstitutes()
     Paths subKeys;
     nixDB.enumTable(txn, dbSubstitutes, subKeys);
     for (Paths::iterator i = subKeys.begin(); i != subKeys.end(); ++i) {
-
-        /* If this path has not become valid in the mean-while, delete
-           any successor mappings *to* it.  This is to preserve the
-           invariant the all successors are `usable' as opposed to
-           `valid' (i.e., the successor must be valid *or* have at
-           least one substitute). */
-        if (!isValidPath(*i)) {
-            unregisterPredecessors(*i, txn);
-        }
-        
         /* Delete all substitutes for path *i. */
         nixDB.delPair(txn, dbSubstitutes, *i);
     }
@@ -407,7 +330,6 @@ static void invalidatePath(const Path & path, Transaction & txn)
     debug(format("unregistering path `%1%'") % path);
 
     nixDB.delPair(txn, dbValidPaths, path);
-    unregisterPredecessors(path, txn);
 }
 
 
@@ -562,34 +484,5 @@ void verifyStore()
             nixDB.delPair(txn, dbSubstitutes, *i);
     }
 
-    /* Check that the values of the successor mappings are usable
-       paths. */ 
-    Paths sucKeys;
-    nixDB.enumTable(txn, dbSuccessors, sucKeys);
-    for (Paths::iterator i = sucKeys.begin(); i != sucKeys.end(); ++i) {
-        /* Note that *i itself does not have to be valid, just its
-           successor. */
-        Path sucPath;
-        if (nixDB.queryString(txn, dbSuccessors, *i, sucPath) &&
-            usablePaths.find(sucPath) == usablePaths.end())
-        {
-            printMsg(lvlError,
-                format("found successor mapping to non-existent path `%1%'") % sucPath);
-            nixDB.delPair(txn, dbSuccessors, *i);
-        }
-    }
-
-    /* Check that the keys of the reverse successor mappings are valid
-       paths. */ 
-    Paths rsucKeys;
-    nixDB.enumTable(txn, dbSuccessorsRev, rsucKeys);
-    for (Paths::iterator i = rsucKeys.begin(); i != rsucKeys.end(); ++i) {
-        if (usablePaths.find(*i) == usablePaths.end()) {
-            printMsg(lvlError,
-                format("found reverse successor mapping for non-existent path `%1%'") % *i);
-            nixDB.delPair(txn, dbSuccessorsRev, *i);
-        }
-    }
-
     txn.commit();
 }
diff --git a/src/libstore/store.hh b/src/libstore/store.hh
index c27918cbb..65c3baf98 100644
--- a/src/libstore/store.hh
+++ b/src/libstore/store.hh
@@ -40,27 +40,6 @@ 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);
-
-/* Remove a successor mapping. */
-void unregisterSuccessor(const Path & srcPath);
-
-/* 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. */
 typedef list<pair<Path, Substitute> > SubstitutePairs;
 void registerSubstitutes(const Transaction & txn,
@@ -81,6 +60,14 @@ void assertStorePath(const Path & path);
 /* Checks whether a path is valid. */ 
 bool isValidPath(const Path & path);
 
+/* Sets the set of outgoing FS references for a store path. */
+void setReferences(const Transaction & txn, const Path & storePath,
+    const PathSet & references);
+
+/* Queries the set of outgoing FS references for a store path.  The
+   result is not cleared. */
+void queryReferences(const Path & storePath, PathSet & references);
+
 /* Constructs a unique store path name. */
 Path makeStorePath(const string & type,
     const Hash & hash, const string & suffix);
diff --git a/src/libstore/storeexpr-ast.def b/src/libstore/storeexpr-ast.def
index 0c70948d4..fa7d0387d 100644
--- a/src/libstore/storeexpr-ast.def
+++ b/src/libstore/storeexpr-ast.def
@@ -1,8 +1,6 @@
 init initStoreExprHelpers
 
-Closure | ATermList ATermList | ATerm |
-Derive | ATermList ATermList string string ATermList ATermList | ATerm |
+Derive | ATermList ATermList ATermList string string ATermList ATermList | ATerm |
 
 | string string | ATerm | EnvBinding |
-| string ATermList | ATerm | ClosureElem |
 | string string string string | ATerm | DerivationOutput |
diff --git a/src/libstore/storeexpr.cc b/src/libstore/storeexpr.cc
index d8300a066..d7c87bfa1 100644
--- a/src/libstore/storeexpr.cc
+++ b/src/libstore/storeexpr.cc
@@ -20,7 +20,7 @@ Path writeTerm(ATerm t, const string & suffix)
 }
 
 
-void checkPath(const string & s)
+static void checkPath(const string & s)
 {
     if (s.size() == 0 || s[0] != '/')
         throw Error(format("bad path `%1%' in store expression") % s);
@@ -39,108 +39,53 @@ static void parsePaths(ATermList paths, PathSet & out)
 }
 
 
-static void checkClosure(const Closure & closure)
+void throwBadDrv(ATerm t)
 {
-    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 (!matchClosure(t, roots, elems))
-        return false;
-
-    parsePaths(roots, closure.roots);
-
-    for (ATermIterator i(elems); i; ++i) {
-        ATerm path;
-        ATermList refs;
-        if (!matchClosureElem(*i, path, refs))
-            throw badTerm("not a closure element", *i);
-        ClosureElem elem;
-        parsePaths(refs, elem.refs);
-        closure.elems[aterm2String(path)] = elem;
-    }
-
-    checkClosure(closure);
-    return true;
+    throw badTerm("not a valid derivation", t);
 }
 
 
-static bool parseDerivation(ATerm t, Derivation & derivation)
+Derivation parseDerivation(ATerm t)
 {
-    ATermList outs, ins, args, bnds;
+    Derivation drv;
+    ATermList outs, inDrvs, inSrcs, args, bnds;
     ATerm builder, platform;
 
-    if (!matchDerive(t, outs, ins, platform, builder, args, bnds))
-        return false;
+    if (!matchDerive(t, outs, inDrvs, inSrcs, platform, builder, args, bnds))
+        throwBadDrv(t);
 
     for (ATermIterator i(outs); i; ++i) {
         ATerm id, path, hashAlgo, hash;
         if (!matchDerivationOutput(*i, id, path, hashAlgo, hash))
-            return false;
+            throwBadDrv(t);
         DerivationOutput out;
         out.path = aterm2String(path);
         checkPath(out.path);
         out.hashAlgo = aterm2String(hashAlgo);
         out.hash = aterm2String(hash);
-        derivation.outputs[aterm2String(id)] = out;
+        drv.outputs[aterm2String(id)] = out;
     }
 
-    parsePaths(ins, derivation.inputs);
+    parsePaths(inDrvs, drv.inputDrvs);
+    parsePaths(inSrcs, drv.inputSrcs);
 
-    derivation.builder = aterm2String(builder);
-    derivation.platform = aterm2String(platform);
+    drv.builder = aterm2String(builder);
+    drv.platform = aterm2String(platform);
     
     for (ATermIterator i(args); i; ++i) {
         if (ATgetType(*i) != AT_APPL)
             throw badTerm("string expected", *i);
-        derivation.args.push_back(aterm2String(*i));
+        drv.args.push_back(aterm2String(*i));
     }
 
     for (ATermIterator i(bnds); i; ++i) {
         ATerm s1, s2;
         if (!matchEnvBinding(*i, s1, s2))
             throw badTerm("tuple of strings expected", *i);
-        derivation.env[aterm2String(s1)] = aterm2String(s2);
+        drv.env[aterm2String(s1)] = aterm2String(s2);
     }
 
-    return true;
-}
-
-
-StoreExpr parseStoreExpr(ATerm t)
-{
-    StoreExpr ne;
-    if (parseClosure(t, ne.closure))
-        ne.type = StoreExpr::neClosure;
-    else if (parseDerivation(t, ne.derivation))
-        ne.type = StoreExpr::neDerivation;
-    else throw badTerm("not a store expression", t);
-    return ne;
+    return drv;
 }
 
 
@@ -154,27 +99,11 @@ static ATermList unparsePaths(const PathSet & paths)
 }
 
 
-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,
-            makeClosureElem(
-                toATerm(i->first),
-                unparsePaths(i->second.refs)));
-
-    return makeClosure(roots, elems);
-}
-
-
-static ATerm unparseDerivation(const Derivation & derivation)
+ATerm unparseDerivation(const Derivation & drv)
 {
     ATermList outputs = ATempty;
-    for (DerivationOutputs::const_iterator i = derivation.outputs.begin();
-         i != derivation.outputs.end(); i++)
+    for (DerivationOutputs::const_iterator i = drv.outputs.begin();
+         i != drv.outputs.end(); i++)
         outputs = ATinsert(outputs,
             makeDerivationOutput(
                 toATerm(i->first),
@@ -183,13 +112,13 @@ static ATerm unparseDerivation(const Derivation & derivation)
                 toATerm(i->second.hash)));
 
     ATermList args = ATempty;
-    for (Strings::const_iterator i = derivation.args.begin();
-         i != derivation.args.end(); i++)
+    for (Strings::const_iterator i = drv.args.begin();
+         i != drv.args.end(); i++)
         args = ATinsert(args, toATerm(*i));
 
     ATermList env = ATempty;
-    for (StringPairs::const_iterator i = derivation.env.begin();
-         i != derivation.env.end(); i++)
+    for (StringPairs::const_iterator i = drv.env.begin();
+         i != drv.env.end(); i++)
         env = ATinsert(env,
             makeEnvBinding(
                 toATerm(i->first),
@@ -197,19 +126,10 @@ static ATerm unparseDerivation(const Derivation & derivation)
 
     return makeDerive(
         ATreverse(outputs),
-        unparsePaths(derivation.inputs),
-        toATerm(derivation.platform),
-        toATerm(derivation.builder),
+        unparsePaths(drv.inputDrvs),
+        unparsePaths(drv.inputSrcs),
+        toATerm(drv.platform),
+        toATerm(drv.builder),
         ATreverse(args),
         ATreverse(env));
 }
-
-
-ATerm unparseStoreExpr(const StoreExpr & ne)
-{
-    if (ne.type == StoreExpr::neClosure)
-        return unparseClosure(ne.closure);
-    else if (ne.type == StoreExpr::neDerivation)
-        return unparseDerivation(ne.derivation);
-    else abort();
-}
diff --git a/src/libstore/storeexpr.hh b/src/libstore/storeexpr.hh
index d8b8b2a96..8eb80a19a 100644
--- a/src/libstore/storeexpr.hh
+++ b/src/libstore/storeexpr.hh
@@ -14,11 +14,13 @@ struct ClosureElem
 
 typedef map<Path, ClosureElem> ClosureElems;
 
+/*
 struct Closure
 {
     PathSet roots;
     ClosureElems elems;
 };
+*/
 
 
 struct DerivationOutput
@@ -43,20 +45,14 @@ typedef map<string, string> StringPairs;
 struct Derivation
 {
     DerivationOutputs outputs; /* keyed on symbolic IDs */
-    PathSet inputs; /* store expressions, not actual inputs */
+    PathSet inputDrvs; /* inputs that are sub-derivations */
+    PathSet inputSrcs; /* inputs that are sources */
     string platform;
     Path builder;
     Strings args;
     StringPairs env;
 };
 
-struct StoreExpr
-{
-    enum { neClosure, neDerivation } type;
-    Closure closure;
-    Derivation derivation;
-};
-
 
 /* Hash an aterm. */
 Hash hashTerm(ATerm t);
@@ -65,10 +61,10 @@ Hash hashTerm(ATerm t);
 Path writeTerm(ATerm t, const string & suffix);
 
 /* Parse a store expression. */
-StoreExpr parseStoreExpr(ATerm t);
+Derivation parseDerivation(ATerm t);
 
 /* Parse a store expression. */
-ATerm unparseStoreExpr(const StoreExpr & ne);
+ATerm unparseDerivation(const Derivation & drv);
 
 
 #endif /* !__STOREEXPR_H */