6 files changed, 82 insertions, 20 deletions
diff --git a/src/libstore/Makefile.am b/src/libstore/Makefile.am
index 3fa941b3bd79..384f99b9ff28 100644
--- a/src/libstore/Makefile.am
+++ b/src/libstore/Makefile.am
@@ -2,7 +2,8 @@ lib_LTLIBRARIES = libstore.la
 
 libstore_la_SOURCES = \
  store.cc store.hh derivations.cc derivations.hh \
- build.cc misc.cc build.hh \
+ build.cc build.hh \
+ misc.cc misc.hh \
  globals.cc globals.hh db.cc db.hh \
  references.cc references.hh pathlocks.cc pathlocks.hh \
  gc.cc gc.hh derivations-ast.hh
diff --git a/src/libstore/build.cc b/src/libstore/build.cc
index 2f6d69d3e15e..9dd12a46d6ba 100644
--- a/src/libstore/build.cc
+++ b/src/libstore/build.cc
@@ -17,6 +17,7 @@
 #include "build.hh"
 #include "references.hh"
 #include "pathlocks.hh"
+#include "misc.hh"
 #include "globals.hh"
 #include "gc.hh"
 
diff --git a/src/libstore/build.hh b/src/libstore/build.hh
index 9e3d365e989a..489a6cabc8a5 100644
--- a/src/libstore/build.hh
+++ b/src/libstore/build.hh
@@ -15,23 +15,6 @@ void buildDerivations(const PathSet & drvPaths);
    be made valid by running a substitute (if defined for the path). */
 void ensurePath(const Path & storePath);
 
-/* Read a derivation, after ensuring its existence through
-   ensurePath(). */
-Derivation derivationFromPath(const Path & drvPath);
-
-/* Place 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.  If
-   `flipDirection' is true, the set of paths that can reach
-   `storePath' is returned; that is, the closures under the
-   `referrers' relation instead of the `references' relation is
-   returned. */
-void computeFSClosure(const Path & storePath,
-    PathSet & paths, bool flipDirection = false);
-
-/* Return the path corresponding to the output identifier `id' in the
-   given derivation. */
-Path findOutput(const Derivation & drv, string id);
     
 
 #endif /* !__BUILD_H */
diff --git a/src/libstore/gc.cc b/src/libstore/gc.cc
index 5f4f5b27ff79..c2bc5bdb1b92 100644
--- a/src/libstore/gc.cc
+++ b/src/libstore/gc.cc
@@ -1,6 +1,6 @@
 #include "globals.hh"
 #include "gc.hh"
-#include "build.hh"
+#include "misc.hh"
 #include "pathlocks.hh"
 
 #include <boost/shared_ptr.hpp>
diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc
index 33efe8bebc98..91cf25f27187 100644
--- a/src/libstore/misc.cc
+++ b/src/libstore/misc.cc
@@ -29,10 +29,55 @@ void computeFSClosure(const Path & storePath,
 }
 
 
- Path findOutput(const Derivation & drv, string id)
+Path findOutput(const Derivation & drv, string id)
 {
     for (DerivationOutputs::const_iterator i = drv.outputs.begin();
          i != drv.outputs.end(); ++i)
         if (i->first == id) return i->second.path;
     throw Error(format("derivation has no output `%1%'") % id);
 }
+
+
+void queryMissing(const PathSet & targets,
+    PathSet & willBuild, PathSet & willSubstitute)
+{
+    PathSet todo(targets.begin(), targets.end()), done;
+
+    while (!todo.empty()) {
+        Path p = *(todo.begin());
+        todo.erase(p);
+        if (done.find(p) != done.end()) continue;
+        done.insert(p);
+
+        if (isDerivation(p)) {
+            if (!isValidPath(p)) continue;
+            Derivation drv = derivationFromPath(p);
+
+            bool mustBuild = false;
+            for (DerivationOutputs::iterator i = drv.outputs.begin();
+                 i != drv.outputs.end(); ++i)
+                if (!isValidPath(i->second.path) &&
+                    querySubstitutes(noTxn, i->second.path).size() == 0)
+                    mustBuild = true;
+
+            if (mustBuild) {
+                willBuild.insert(p);
+                todo.insert(drv.inputSrcs.begin(), drv.inputSrcs.end());
+                for (DerivationInputs::iterator i = drv.inputDrvs.begin();
+                     i != drv.inputDrvs.end(); ++i)
+                    todo.insert(i->first);
+            } else 
+                for (DerivationOutputs::iterator i = drv.outputs.begin();
+                     i != drv.outputs.end(); ++i)
+                    todo.insert(i->second.path);
+        }
+
+        else {
+            if (isValidPath(p)) continue;
+            if (querySubstitutes(noTxn, p).size() > 0)
+                willSubstitute.insert(p);
+            PathSet refs;
+            queryReferences(noTxn, p, todo);
+        }
+    }
+}
diff --git a/src/libstore/misc.hh b/src/libstore/misc.hh
new file mode 100644
index 000000000000..f758f5bfd58e
--- /dev/null
+++ b/src/libstore/misc.hh
@@ -0,0 +1,32 @@
+#ifndef __MISC_H
+#define __MISC_H
+
+#include "derivations.hh"
+
+
+/* Read a derivation, after ensuring its existence through
+   ensurePath(). */
+Derivation derivationFromPath(const Path & drvPath);
+
+/* Place 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.  If
+   `flipDirection' is true, the set of paths that can reach
+   `storePath' is returned; that is, the closures under the
+   `referrers' relation instead of the `references' relation is
+   returned. */
+void computeFSClosure(const Path & storePath,
+    PathSet & paths, bool flipDirection = false);
+
+/* Return the path corresponding to the output identifier `id' in the
+   given derivation. */
+Path findOutput(const Derivation & drv, string id);
+
+/* Given a set of paths that are to be built, return the set of
+   derivations that will be built, and the set of output paths that
+   will be substituted. */
+void queryMissing(const PathSet & targets,
+    PathSet & willBuild, PathSet & willSubstitute);
+
+
+#endif /* !__MISC_H */