5 files changed, 110 insertions, 6 deletions
diff --git a/src/libstore/Makefile.am b/src/libstore/Makefile.am
index 8c61b36f487a..31735e8936c7 100644
--- a/src/libstore/Makefile.am
+++ b/src/libstore/Makefile.am
@@ -4,7 +4,8 @@ libstore_a_SOURCES = \
  store.cc store.hh storeexpr.cc storeexpr.hh \
  normalise.cc misc.cc normalise.hh \
  globals.cc globals.hh db.cc db.hh \
- references.cc references.hh pathlocks.cc pathlocks.hh
+ references.cc references.hh pathlocks.cc pathlocks.hh \
+ gc.cc gc.hh
 
 AM_CXXFLAGS = -Wall \
  -I.. ${bdb_include} ${aterm_include} -I../libutil
diff --git a/src/libstore/gc.cc b/src/libstore/gc.cc
new file mode 100644
index 000000000000..aed7c2294b04
--- /dev/null
+++ b/src/libstore/gc.cc
@@ -0,0 +1,83 @@
+#include "normalise.hh"
+#include "globals.hh"
+
+
+void followLivePaths(Path nePath, PathSet & live)
+{
+    /* Just to be sure, canonicalise the path.  It is important to do
+       this here and in findDeadPath() to ensure that a live path is
+       not mistaken for a dead path due to some non-canonical
+       representation. */
+    nePath = canonPath(nePath);
+    
+    if (live.find(nePath) != live.end()) return;
+    live.insert(nePath);
+
+    startNest(nest, lvlDebug, format("following `%1%'") % nePath);
+    assertStorePath(nePath);
+
+    if (isValidPath(nePath)) {
+
+        /* !!! should make sure that no substitutes are used */
+        StoreExpr ne = storeExprFromPath(nePath);
+
+        /* !!! painfully similar to requisitesWorker() */
+        if (ne.type == StoreExpr::neClosure)
+            for (ClosureElems::iterator i = ne.closure.elems.begin();
+                 i != ne.closure.elems.end(); ++i)
+            {
+                Path p = canonPath(i->first);
+                if (live.find(p) == live.end()) {
+                    debug(format("found live `%1%'") % p);
+                    assertStorePath(p);
+                    live.insert(p);
+                }
+            }
+    
+        else if (ne.type == StoreExpr::neDerivation)
+            for (PathSet::iterator i = ne.derivation.inputs.begin();
+                 i != ne.derivation.inputs.end(); ++i)
+                followLivePaths(*i, live);
+
+        else abort();
+        
+    }
+
+    Path nfPath;
+    if (querySuccessor(nePath, nfPath))
+        followLivePaths(nfPath, live);
+}
+
+
+PathSet findLivePaths(const Paths & roots)
+{
+    PathSet live;
+
+    startNest(nest, lvlDebug, "finding live paths");
+
+    for (Paths::const_iterator i = roots.begin(); i != roots.end(); ++i)
+        followLivePaths(*i, live);
+
+    return live;
+}
+
+
+PathSet findDeadPaths(const PathSet & live)
+{
+    PathSet dead;
+
+    startNest(nest, lvlDebug, "finding dead paths");
+
+    Strings storeNames = readDirectory(nixStore);
+
+    for (Strings::iterator i = storeNames.begin(); i != storeNames.end(); ++i) {
+        Path p = canonPath(nixStore + "/" + *i);
+        if (live.find(p) == live.end()) {
+            debug(format("dead path `%1%'") % p);
+            dead.insert(p);
+        } else
+            debug(format("live path `%1%'") % p);
+    }
+    
+    return dead;
+}
diff --git a/src/libstore/gc.hh b/src/libstore/gc.hh
new file mode 100644
index 000000000000..997057ba9b7b
--- /dev/null
+++ b/src/libstore/gc.hh
@@ -0,0 +1,24 @@
+#ifndef __GC_H
+#define __GC_H
+
+#include "storeexpr.hh"
+
+
+/* Determine the set of "live" store paths, given a set of root store
+   expressions.  The live store paths are those that are reachable
+   from the roots.  The roots are reachable by definition.  Any path
+   mentioned in a reachable store expression is also reachable.  If a
+   derivation store expression is reachable, then its successor (if it
+   exists) if also reachable.  It is not an error for store
+   expressions not to exist (since this can happen on derivation store
+   expressions, for instance, due to the substitute mechanism), but
+   successor links are followed even for non-existant derivations. */
+PathSet findLivePaths(const Paths & roots);
+
+/* Given a set of "live" store paths, determine the set of "dead"
+   store paths (which are simply all store paths that are not in the
+   live set). */
+PathSet findDeadPaths(const PathSet & live);
+
+
+#endif /* !__GC_H */
diff --git a/src/libstore/normalise.hh b/src/libstore/normalise.hh
index 43be136e5b75..7b0835b45ef4 100644
--- a/src/libstore/normalise.hh
+++ b/src/libstore/normalise.hh
@@ -40,9 +40,5 @@ PathSet storeExprRoots(const Path & nePath);
 PathSet storeExprRequisites(const Path & nePath,
     bool includeExprs, bool includeSuccessors);
 
-/* Return the list of the paths of all known store expressions whose
-   output paths are completely contained in the set `outputs'. */
-PathSet findGenerators(const PathSet & outputs);
-
 
 #endif /* !__NORMALISE_H */
diff --git a/src/libstore/store.cc b/src/libstore/store.cc
index 44b3a29e34d9..fdd22c3b889a 100644
--- a/src/libstore/store.cc
+++ b/src/libstore/store.cc
@@ -388,7 +388,7 @@ static void invalidatePath(const Path & path, Transaction & txn)
                 subs2.push_back(*j);
             else
                 found = true;
-        if (!found) throw Error("integrity error in substitutes mapping");
+        // !!!        if (!found) throw Error("integrity error in substitutes mapping");
         writeSubstitutes(txn, *i, subs);
 
 	/* If path *i now has no substitutes left, and is not valid,