* Get rid of the substitutes database table (NIX-47). Instead, if we

  need any info on substitutable paths, we just call the substituters
  (such as download-using-manifests.pl) directly.  This means that
  it's no longer necessary for nix-pull to register substitutes or for
  nix-channel to clear them, which makes those operations much faster
  (NIX-95).  Also, we don't have to worry about keeping nix-pull
  manifests (in /nix/var/nix/manifests) and the database in sync with
  each other.

  The downside is that there is some overhead in calling an external
  program to get the substitutes info.  For instance, "nix-env -qas"
  takes a bit longer.

  Abolishing the substitutes table also makes the logic in
  local-store.cc simpler, as we don't need to store info for invalid
  paths.  On the downside, you cannot do things like "nix-store -qR"
  on a substitutable but invalid path (but nobody did that anyway).

* Never catch interrupts (the Interrupted exception).

14 files changed, 279 insertions, 306 deletions

diff --git a/src/libstore/build.cc b/src/libstore/build.cc
index e300292e96cf..4a2affdf59b3 100644
--- a/src/libstore/build.cc
+++ b/src/libstore/build.cc
@@ -164,6 +164,11 @@ private:
     /* Goals waiting for a build slot. */
     WeakGoals wantingToBuild;
 
+    /* Goals waiting for info from substituters (using --query-info),
+       and the info they're (collectively) waiting for. */
+    WeakGoals waitingForInfo;
+    map<Path, PathSet> requestedInfo;
+
     /* Child processes currently running. */
     Children children;
 
@@ -212,12 +217,24 @@ public:
     /* Put `goal' to sleep until a child process terminates, i.e., a
        call is made to childTerminate(..., true).  */
     void waitForChildTermination(GoalPtr goal);
+
+    /* Put `goal' to sleep until the top-level loop has run `sub' to
+       get info about `storePath' (with --query-info).  We combine
+       substituter invocations to reduce overhead. */
+    void waitForInfo(GoalPtr goal, Path sub, Path storePath);
     
     /* Loop until the specified top-level goals have finished. */
     void run(const Goals & topGoals);
 
     /* Wait for input to become available. */
     void waitForInput();
+
+private:
+
+    /* Process the pending paths in requestedInfo and wake up the
+       goals in waitingForInfo. */
+    void getInfo();
+    
 };
 
 
@@ -783,7 +800,7 @@ void DerivationGoal::haveDerivation()
            substitutes. */
         if (store->hasSubstitutes(*i))
             addWaitee(worker.makeSubstitutionGoal(*i));
-
+    
     if (waitees.empty()) /* to prevent hang (no wake-up event) */
         outputsSubstituted();
     else
@@ -1829,18 +1846,22 @@ PathSet DerivationGoal::checkPathValidity(bool returnValid)
 
 class SubstitutionGoal : public Goal
 {
+    friend class Worker;
+    
 private:
     /* The store path that should be realised through a substitute. */
     Path storePath;
 
-    /* The remaining substitutes for this path. */
-    Substitutes subs;
+    /* The remaining substituters. */
+    Paths subs;
 
-    /* The current substitute. */
-    Substitute sub;
+    /* The current substituter. */
+    Path sub;
 
-    /* Outgoing references for this path. */
+    /* Path info returned by the substituter's --query-info operation. */
+    bool infoOkay;
     PathSet references;
+    Path deriver;
 
     /* Pipe for the substitute's standard output/error. */
     Pipe logPipe;
@@ -1864,8 +1885,9 @@ public:
 
     /* The states. */
     void init();
-    void referencesValid();
     void tryNext();
+    void gotInfo();
+    void referencesValid();
     void tryToRun();
     void finished();
 
@@ -1923,17 +1945,46 @@ void SubstitutionGoal::init()
         return;
     }
 
-    /* !!! race condition; should get the substitutes and the
-       references in a transaction (in case a clearSubstitutes() is
-       done simultaneously). */
+    subs = substituters;
+
+    tryNext();
+}
+
+
+void SubstitutionGoal::tryNext()
+{
+    trace("trying next substituter");
+
+    if (subs.size() == 0) {
+        /* None left.  Terminate this goal and let someone else deal
+           with it. */
+        printMsg(lvlError,
+            format("path `%1%' is required, but there is no substituter that can build it")
+            % storePath);
+        amDone(ecFailed);
+        return;
+    }
+
+    sub = subs.front();
+    subs.pop_front();
+
+    infoOkay = false;
+    state = &SubstitutionGoal::gotInfo;
+    worker.waitForInfo(shared_from_this(), sub, storePath);
+}
 
-    /* Read the substitutes. */
-    subs = store->querySubstitutes(storePath);
 
+void SubstitutionGoal::gotInfo()
+{
+    trace("got info");
+
+    if (!infoOkay) {
+        tryNext();
+        return;
+    }
+    
     /* To maintain the closure invariant, we first have to realise the
        paths referenced by this one. */
-    store->queryReferences(storePath, references);
-
     for (PathSet::iterator i = references.begin();
          i != references.end(); ++i)
         if (*i != storePath) /* ignore self-references */
@@ -1948,7 +1999,7 @@ void SubstitutionGoal::init()
 
 void SubstitutionGoal::referencesValid()
 {
-    trace("all referenced realised");
+    trace("all references realised");
 
     if (nrFailed > 0) {
         printMsg(lvlError,
@@ -1961,28 +2012,7 @@ void SubstitutionGoal::referencesValid()
          i != references.end(); ++i)
         if (*i != storePath) /* ignore self-references */
             assert(store->isValidPath(*i));
-    
-    tryNext();
-}
-
-
-void SubstitutionGoal::tryNext()
-{
-    trace("trying next substitute");
-
-    if (subs.size() == 0) {
-        /* None left.  Terminate this goal and let someone else deal
-           with it. */
-        printMsg(lvlError,
-            format("path `%1%' is required, but it has no (remaining) substitutes")
-            % storePath);
-        amDone(ecFailed);
-        return;
-    }
-    sub = subs.front();
-    subs.pop_front();
 
-    /* Wait until we can run the substitute program. */
     state = &SubstitutionGoal::tryToRun;
     worker.waitForBuildSlot(shared_from_this());
 }
@@ -2013,7 +2043,7 @@ void SubstitutionGoal::tryToRun()
 
     printMsg(lvlInfo,
         format("substituting path `%1%' using substituter `%2%'")
-        % storePath % sub.program);
+        % storePath % sub);
     
     logPipe.create();
 
@@ -2038,14 +2068,15 @@ void SubstitutionGoal::tryToRun()
             commonChildInit(logPipe);
 
             /* Fill in the arguments. */
-            Strings args(sub.args);
-            args.push_front(storePath);
-            args.push_front(baseNameOf(sub.program));
+            Strings args;
+            args.push_back(baseNameOf(sub));
+            args.push_back("--substitute");
+            args.push_back(storePath);
             const char * * argArr = strings2CharPtrs(args);
 
-            execv(sub.program.c_str(), (char * *) argArr);
+            execv(sub.c_str(), (char * *) argArr);
             
-            throw SysError(format("executing `%1%'") % sub.program);
+            throw SysError(format("executing `%1%'") % sub);
             
         } catch (std::exception & e) {
             std::cerr << format("substitute error: %1%\n") % e.what();
@@ -2098,7 +2129,7 @@ void SubstitutionGoal::finished()
 
         printMsg(lvlInfo,
             format("substitution of path `%1%' using substituter `%2%' failed: %3%")
-            % storePath % sub.program % e.msg());
+            % storePath % sub % e.msg());
         
         /* Try the next substitute. */
         state = &SubstitutionGoal::tryNext;
@@ -2113,7 +2144,7 @@ void SubstitutionGoal::finished()
     Transaction txn;
     createStoreTransaction(txn);
     registerValidPath(txn, storePath, contentHash,
-        references, sub.deriver);
+        references, deriver);
     txn.commit();
 
     outputLock->setDeletion(true);
@@ -2298,6 +2329,76 @@ void Worker::waitForChildTermination(GoalPtr goal)
 }
 
 
+void Worker::waitForInfo(GoalPtr goal, Path sub, Path storePath)
+{
+    debug("wait for info");
+    requestedInfo[sub].insert(storePath);
+    waitingForInfo.insert(goal);
+}
+
+
+void Worker::getInfo()
+{
+    for (map<Path, PathSet>::iterator i = requestedInfo.begin();
+         i != requestedInfo.end(); ++i)
+    {
+        Path sub = i->first;
+        PathSet paths = i->second;
+
+        while (!paths.empty()) {
+
+            /* Run the substituter for at most 100 paths at a time to
+               prevent command line overflows. */
+            PathSet paths2;
+            while (!paths.empty() && paths2.size() < 100) {
+                paths2.insert(*paths.begin());
+                paths.erase(paths.begin());
+            }
+
+            /* Ask the substituter for the references and deriver of
+               the paths. */
+            debug(format("running `%1%' to get info about `%2%'") % sub % showPaths(paths2));
+            Strings args;
+            args.push_back("--query-info");
+            args.insert(args.end(), paths2.begin(), paths2.end());
+            string res = runProgram(sub, false, args);
+            std::istringstream str(res);
+
+            while (true) {
+                ValidPathInfo info = decodeValidPathInfo(str);
+                if (info.path == "") break;
+
+                /* !!! inefficient */
+                for (WeakGoals::iterator k = waitingForInfo.begin();
+                     k != waitingForInfo.end(); ++k)
+                {
+                    GoalPtr goal = k->lock();
+                    if (goal) {
+                        SubstitutionGoal * goal2 = dynamic_cast<SubstitutionGoal *>(goal.get());
+                        if (goal2->storePath == info.path) {
+                            goal2->references = info.references;
+                            goal2->deriver = info.deriver;
+                            goal2->infoOkay = true;
+                            wakeUp(goal);
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    for (WeakGoals::iterator k = waitingForInfo.begin();
+         k != waitingForInfo.end(); ++k)
+    {
+        GoalPtr goal = k->lock();
+        if (goal) wakeUp(goal);
+    }
+    
+    requestedInfo.clear();
+    waitingForInfo.clear(); // !!! have we done them all?
+}
+
+
 void Worker::run(const Goals & _topGoals)
 {
     for (Goals::iterator i = _topGoals.begin();
@@ -2324,11 +2425,14 @@ void Worker::run(const Goals & _topGoals)
 
         if (topGoals.empty()) break;
 
-        /* !!! not when we're polling */
-        assert(!children.empty());
-        
+        getInfo();
+
         /* Wait for input. */
-        waitForInput();
+        if (!children.empty())
+            waitForInput();
+        else
+            /* !!! not when we're polling */
+            assert(!awake.empty());
     }
 
     /* If --keep-going is not set, it's possible that the main goal
diff --git a/src/libstore/db.cc b/src/libstore/db.cc
index 657f6b7b4bac..59b9c0c8e339 100644
--- a/src/libstore/db.cc
+++ b/src/libstore/db.cc
@@ -194,7 +194,8 @@ void Database::open2(const string & path, bool removeOldEnv)
 
     env->set_errcall(errorPrinter);
     env->set_msgcall(messagePrinter);
-    //env->set_verbose(DB_VERB_REGISTER, 1);
+    if (getEnv("NIX_DEBUG_DB_REGISTER") == "1")
+        env->set_verbose(DB_VERB_REGISTER, 1);
     env->set_verbose(DB_VERB_RECOVERY, 1);
     
     /* Smaller log files. */
@@ -454,4 +455,14 @@ void Database::enumTable(const Transaction & txn, TableId table,
 }
 
  
+void Database::clearTable(const Transaction & txn, TableId table)
+{
+    try {
+        Db * db = getDb(table);
+        u_int32_t count;
+        db->truncate(txn.txn, &count, 0);
+    } catch (DbException e) { rethrow(e); }
+}
+
+
 }
diff --git a/src/libstore/db.hh b/src/libstore/db.hh
index 54f490f885d5..8672fbc863f5 100644
--- a/src/libstore/db.hh
+++ b/src/libstore/db.hh
@@ -89,6 +89,8 @@ public:
 
     void enumTable(const Transaction & txn, TableId table,
         Strings & keys, const string & keyPrefix = "");
+
+    void clearTable(const Transaction & txn, TableId table);
 };
 
 
diff --git a/src/libstore/gc.cc b/src/libstore/gc.cc
index 3699b234402f..8ce717aaffaa 100644
--- a/src/libstore/gc.cc
+++ b/src/libstore/gc.cc
@@ -602,6 +602,8 @@ void LocalStore::collectGarbage(GCAction action, const PathSet & pathsToDelete,
             }
 #endif
 
+            if (!pathExists(*i)) continue;
+                
             printMsg(lvlInfo, format("deleting `%1%'") % *i);
             
             /* Okay, it's safe to delete. */
diff --git a/src/libstore/globals.cc b/src/libstore/globals.cc
index b0316f77c292..6c4944539d5e 100644
--- a/src/libstore/globals.cc
+++ b/src/libstore/globals.cc
@@ -25,6 +25,7 @@ unsigned int maxBuildJobs = 1;
 bool readOnlyMode = false;
 string thisSystem = "unset";
 unsigned int maxSilentTime = 0;
+Paths substituters;
 
 
 static bool settingsRead = false;
diff --git a/src/libstore/globals.hh b/src/libstore/globals.hh
index 51fa68594798..ea15da0e644b 100644
--- a/src/libstore/globals.hh
+++ b/src/libstore/globals.hh
@@ -67,6 +67,11 @@ extern string thisSystem;
    infinity. */
 extern unsigned int maxSilentTime;
 
+/* The substituters.  There are programs that can somehow realise a
+   store path without building, e.g., by downloading it or copying it
+   from a CD. */
+extern Paths substituters;
+
 
 Strings querySetting(const string & name, const Strings & def);
 
diff --git a/src/libstore/local-store.cc b/src/libstore/local-store.cc
index 1165335125b9..bffefbaa780e 100644
--- a/src/libstore/local-store.cc
+++ b/src/libstore/local-store.cc
@@ -48,22 +48,6 @@ static TableId dbReferences = 0;
    referrer. */
 static TableId dbReferrers = 0;
 
-/* dbSubstitutes :: Path -> [[Path]]
-
-   Each pair $(p, subs)$ tells Nix that it can use any of the
-   substitutes in $subs$ to build path $p$.  Each substitute defines a
-   command-line invocation of a program (i.e., the first list element
-   is the full path to the program, the remaining elements are
-   arguments).
-
-   The main purpose of this is for distributed caching of derivates.
-   One system can compute a derivate and put it on a website (as a Nix
-   archive), for instance, and then another system can register a
-   substitute for that derivate.  The substitute in this case might be
-   a Nix derivation that fetches the Nix archive.
-*/
-static TableId dbSubstitutes = 0;
-
 /* dbDerivers :: Path -> [Path]
 
    This table lists the derivation used to build a path.  There can
@@ -72,13 +56,6 @@ static TableId dbSubstitutes = 0;
 static TableId dbDerivers = 0;
 
 
-bool Substitute::operator == (const Substitute & sub) const
-{
-    return program == sub.program
-        && args == sub.args;
-}
-
-
 static void upgradeStore07();
 static void upgradeStore09();
 
@@ -103,6 +80,8 @@ void checkStoreNotSymlink()
 
 LocalStore::LocalStore(bool reserveSpace)
 {
+    substitutablePathsLoaded = false;
+    
     if (readOnlyMode) return;
 
     checkStoreNotSymlink();
@@ -133,7 +112,6 @@ LocalStore::LocalStore(bool reserveSpace)
     dbValidPaths = nixDB.openTable("validpaths");
     dbReferences = nixDB.openTable("references");
     dbReferrers = nixDB.openTable("referrers", true); /* must be sorted */
-    dbSubstitutes = nixDB.openTable("substitutes");
     dbDerivers = nixDB.openTable("derivers");
 
     int curSchema = 0;
@@ -280,17 +258,6 @@ bool LocalStore::isValidPath(const Path & path)
 }
 
 
-static Substitutes readSubstitutes(const Transaction & txn,
-    const Path & srcPath);
-
-
-static bool isRealisablePath(const Transaction & txn, const Path & path)
-{
-    return isValidPathTxn(txn, path)
-        || readSubstitutes(txn, path).size() > 0;
-}
-
-
 static string addPrefix(const string & prefix, const string & s)
 {
     return prefix + string(1, (char) 0) + s;
@@ -322,11 +289,10 @@ static PathSet getReferrers(const Transaction & txn, const Path & storePath)
 void setReferences(const Transaction & txn, const Path & storePath,
     const PathSet & references)
 {
-    /* For unrealisable paths, we can only clear the references. */
-    if (references.size() > 0 && !isRealisablePath(txn, storePath))
+    /* For invalid paths, we can only clear the references. */
+    if (references.size() > 0 && !isValidPathTxn(txn, storePath))
         throw Error(
-            format("cannot set references for path `%1%' which is invalid and has no substitutes")
-            % storePath);
+            format("cannot set references for invalid path `%1%'") % storePath);
 
     Paths oldReferences;
     nixDB.queryStrings(txn, dbReferences, storePath, oldReferences);
@@ -356,7 +322,7 @@ void queryReferences(const Transaction & txn,
     const Path & storePath, PathSet & references)
 {
     Paths references2;
-    if (!isRealisablePath(txn, storePath))
+    if (!isValidPathTxn(txn, storePath))
         throw Error(format("path `%1%' is not valid") % storePath);
     nixDB.queryStrings(txn, dbReferences, storePath, references2);
     references.insert(references2.begin(), references2.end());
@@ -373,7 +339,7 @@ void LocalStore::queryReferences(const Path & storePath,
 void queryReferrers(const Transaction & txn,
     const Path & storePath, PathSet & referrers)
 {
-    if (!isRealisablePath(txn, storePath))
+    if (!isValidPathTxn(txn, storePath))
         throw Error(format("path `%1%' is not valid") % storePath);
     PathSet referrers2 = getReferrers(txn, storePath);
     referrers.insert(referrers2.begin(), referrers2.end());
@@ -393,7 +359,7 @@ void setDeriver(const Transaction & txn, const Path & storePath,
     assertStorePath(storePath);
     if (deriver == "") return;
     assertStorePath(deriver);
-    if (!isRealisablePath(txn, storePath))
+    if (!isValidPathTxn(txn, storePath))
         throw Error(format("path `%1%' is not valid") % storePath);
     nixDB.setString(txn, dbDerivers, storePath, deriver);
 }
@@ -401,7 +367,7 @@ void setDeriver(const Transaction & txn, const Path & storePath,
 
 static Path queryDeriver(const Transaction & txn, const Path & storePath)
 {
-    if (!isRealisablePath(txn, storePath))
+    if (!isValidPathTxn(txn, storePath))
         throw Error(format("path `%1%' is not valid") % storePath);
     Path deriver;
     if (nixDB.queryString(txn, dbDerivers, storePath, deriver))
@@ -417,119 +383,33 @@ Path LocalStore::queryDeriver(const Path & path)
 }
 
 
-const int substituteVersion = 2;
-
-
-static Substitutes readSubstitutes(const Transaction & txn,
-    const Path & srcPath)
+PathSet LocalStore::querySubstitutablePaths()
 {
-    Strings ss;
-    nixDB.queryStrings(txn, dbSubstitutes, srcPath, ss);
-
-    Substitutes subs;
-    
-    for (Strings::iterator i = ss.begin(); i != ss.end(); ++i) {
-        if (i->size() < 4 || (*i)[3] != 0) {
-            /* Old-style substitute.  !!! remove this code
-               eventually? */
-            break;
+    if (!substitutablePathsLoaded) {
+        for (Paths::iterator i = substituters.begin(); i != substituters.end(); ++i) {
+            debug(format("running `%1%' to find out substitutable paths") % *i);
+            Strings args;
+            args.push_back("--query-paths");
+            Strings ss = tokenizeString(runProgram(*i, false, args), "\n");
+            for (Strings::iterator j = ss.begin(); j != ss.end(); ++j) {
+                if (!isStorePath(*j))
+                    throw Error(format("`%1%' returned a bad substitutable path `%2%'")
+                        % *i % *j);
+                substitutablePaths.insert(*j);
+            }
         }
-        Strings ss2 = unpackStrings(*i);
-        if (ss2.size() == 0) continue;
-        int version;
-        if (!string2Int(ss2.front(), version)) continue;
-        if (version != substituteVersion) continue;
-        if (ss2.size() != 4) throw Error("malformed substitute");
-        Strings::iterator j = ss2.begin();
-        j++;
-        Substitute sub;
-        sub.deriver = *j++;
-        sub.program = *j++;
-        sub.args = unpackStrings(*j++);
-        subs.push_back(sub);
-    }
-
-    return subs;
-}
-
-
-static void writeSubstitutes(const Transaction & txn,
-    const Path & srcPath, const Substitutes & subs)
-{
-    Strings ss;
-
-    for (Substitutes::const_iterator i = subs.begin();
-         i != subs.end(); ++i)
-    {
-        Strings ss2;
-        ss2.push_back((format("%1%") % substituteVersion).str());
-        ss2.push_back(i->deriver);
-        ss2.push_back(i->program);
-        ss2.push_back(packStrings(i->args));
-        ss.push_back(packStrings(ss2));
+        substitutablePathsLoaded = true;
     }
 
-    nixDB.setStrings(txn, dbSubstitutes, srcPath, ss);
+    return substitutablePaths;
 }
 
 
-void registerSubstitute(const Transaction & txn,
-    const Path & srcPath, const Substitute & sub)
+bool LocalStore::hasSubstitutes(const Path & path)
 {
-    assertStorePath(srcPath);
-    
-    Substitutes subs = readSubstitutes(txn, srcPath);
-
-    if (find(subs.begin(), subs.end(), sub) != subs.end())
-        return;
-
-    /* New substitutes take precedence over old ones.  If the
-       substitute is already present, it's moved to the front. */
-    remove(subs.begin(), subs.end(), sub);
-    subs.push_front(sub);
-        
-    writeSubstitutes(txn, srcPath, subs);
-}
-
-
-Substitutes querySubstitutes(const Transaction & txn, const Path & path)
-{
-    return readSubstitutes(txn, path);
-}
-
-
-Substitutes LocalStore::querySubstitutes(const Path & path)
-{
-    return nix::querySubstitutes(noTxn, path);
-}
-
-
-static void invalidatePath(Transaction & txn, const Path & path);
-
-
-void clearSubstitutes()
-{
-    Transaction txn(nixDB);
-    
-    /* Iterate over all paths for which there are substitutes. */
-    Paths subKeys;
-    nixDB.enumTable(txn, dbSubstitutes, subKeys);
-    for (Paths::iterator i = subKeys.begin(); i != subKeys.end(); ++i) {
-        
-        /* Delete all substitutes for path *i. */
-        nixDB.delPair(txn, dbSubstitutes, *i);
-        
-        /* Maintain the cleanup invariant. */
-        if (!isValidPathTxn(txn, *i))
-            invalidatePath(txn, *i);
-    }
-
-    /* !!! there should be no referrers to any of the invalid
-       substitutable paths.  This should be the case by construction
-       (the only referrers can be other invalid substitutable paths,
-       which have all been removed now). */
-    
-    txn.commit();
+    if (!substitutablePathsLoaded)
+        querySubstitutablePaths(); 
+    return substitutablePaths.find(path) != substitutablePaths.end();
 }
 
 
@@ -615,17 +495,12 @@ void registerValidPaths(const Transaction & txn,
    there are no referrers. */
 static void invalidatePath(Transaction & txn, const Path & path)
 {
-    debug(format("unregistering path `%1%'") % path);
+    debug(format("invalidating path `%1%'") % path);
 
     /* Clear the `references' entry for this path, as well as the
-       inverse `referrers' entries, and the `derivers' entry; but only
-       if there are no substitutes for this path.  This maintains the
-       cleanup invariant. */
-    if (querySubstitutes(txn, path).size() == 0) {
-        setReferences(txn, path, PathSet());
-        nixDB.delPair(txn, dbDerivers, path);
-    }
-    
+       inverse `referrers' entries, and the `derivers' entry. */
+    setReferences(txn, path, PathSet());
+    nixDB.delPair(txn, dbDerivers, path);
     nixDB.delPair(txn, dbValidPaths, path);
 }
 
@@ -967,30 +842,7 @@ void verifyStore(bool checkContents)
     }
 
 
-    printMsg(lvlInfo, "checking path realisability");
-    
-    /* "Realisable" paths are those that are valid or have a
-       substitute. */
-    PathSet realisablePaths(validPaths);
-
-    /* Check that the values of the substitute mappings are valid
-       paths. */ 
-    Paths subKeys;
-    nixDB.enumTable(txn, dbSubstitutes, subKeys);
-    for (Paths::iterator i = subKeys.begin(); i != subKeys.end(); ++i) {
-        Substitutes subs = readSubstitutes(txn, *i);
-        if (!isStorePath(*i)) {
-            printMsg(lvlError, format("removing substitutes for non-store path `%1%'") % *i);
-            nixDB.delPair(txn, dbSubstitutes, *i);
-        }
-        else if (subs.size() == 0)
-            nixDB.delPair(txn, dbSubstitutes, *i);
-        else
-	    realisablePaths.insert(*i);
-    }
-    
-
-    /* Check the cleanup invariant: only realisable paths can have
+    /* Check the cleanup invariant: only valid paths can have
        `references', `referrers', or `derivers' entries. */
 
 
@@ -1001,8 +853,8 @@ void verifyStore(bool checkContents)
     for (Paths::iterator i = deriversKeys.begin();
          i != deriversKeys.end(); ++i)
     {
-        if (realisablePaths.find(*i) == realisablePaths.end()) {
-            printMsg(lvlError, format("removing deriver entry for unrealisable path `%1%'")
+        if (validPaths.find(*i) == validPaths.end()) {
+            printMsg(lvlError, format("removing deriver entry for invalid path `%1%'")
                 % *i);
             nixDB.delPair(txn, dbDerivers, *i);
         }
@@ -1024,13 +876,12 @@ void verifyStore(bool checkContents)
     for (Paths::iterator i = referencesKeys.begin();
          i != referencesKeys.end(); ++i)
     {
-        if (realisablePaths.find(*i) == realisablePaths.end()) {
-            printMsg(lvlError, format("removing references entry for unrealisable path `%1%'")
+        if (validPaths.find(*i) == validPaths.end()) {
+            printMsg(lvlError, format("removing references entry for invalid path `%1%'")
                 % *i);
             setReferences(txn, *i, PathSet());
         }
         else {
-            bool isValid = validPaths.find(*i) != validPaths.end();
             PathSet references;
             queryReferences(txn, *i, references);
             for (PathSet::iterator j = references.begin();
@@ -1042,7 +893,7 @@ void verifyStore(bool checkContents)
                         % *j % *i);
                     nixDB.setString(txn, dbReferrers, addPrefix(*j, *i), "");
                 }
-                if (isValid && validPaths.find(*j) == validPaths.end()) {
+                if (validPaths.find(*j) == validPaths.end()) {
                     printMsg(lvlError, format("incomplete closure: `%1%' needs missing `%2%'")
                         % *i % *j);
                 }
@@ -1066,14 +917,14 @@ void verifyStore(bool checkContents)
         Path to(*i, 0, nul);
         Path from(*i, nul + 1);
         
-        if (realisablePaths.find(to) == realisablePaths.end()) {
-            printMsg(lvlError, format("removing referrer entry from `%1%' to unrealisable `%2%'")
+        if (validPaths.find(to) == validPaths.end()) {
+            printMsg(lvlError, format("removing referrer entry from `%1%' to invalid `%2%'")
                 % from % to);
             nixDB.delPair(txn, dbReferrers, *i);
         }
 
-        else if (realisablePaths.find(from) == realisablePaths.end()) {
-            printMsg(lvlError, format("removing referrer entry from unrealisable `%1%' to `%2%'")
+        else if (validPaths.find(from) == validPaths.end()) {
+            printMsg(lvlError, format("removing referrer entry from invalid `%1%' to `%2%'")
                 % from % to);
             nixDB.delPair(txn, dbReferrers, *i);
         }
diff --git a/src/libstore/local-store.hh b/src/libstore/local-store.hh
index 7c5cd2668405..ffcef60716bb 100644
--- a/src/libstore/local-store.hh
+++ b/src/libstore/local-store.hh
@@ -23,6 +23,10 @@ extern string drvsLogDir;
 
 class LocalStore : public StoreAPI
 {
+private:
+    bool substitutablePathsLoaded;
+    PathSet substitutablePaths;
+    
 public:
 
     /* Open the database environment.  If `reserveSpace' is true, make
@@ -41,8 +45,6 @@ public:
     
     bool isValidPath(const Path & path);
 
-    Substitutes querySubstitutes(const Path & srcPath);
-
     Hash queryPathHash(const Path & path);
 
     void queryReferences(const Path & path, PathSet & references);
@@ -51,6 +53,10 @@ public:
 
     Path queryDeriver(const Path & path);
     
+    PathSet querySubstitutablePaths();
+    
+    bool hasSubstitutes(const Path & path);
+    
     Path addToStore(const Path & srcPath, bool fixed = false,
         bool recursive = false, string hashAlgo = "",
         PathFilter & filter = defaultPathFilter);
@@ -86,13 +92,6 @@ void createStoreTransaction(Transaction & txn);
 /* Copy a path recursively. */
 void copyPath(const Path & src, const Path & dst);
 
-/* Register a substitute. */
-void registerSubstitute(const Transaction & txn,
-    const Path & srcPath, const Substitute & sub);
-
-/* Deregister all substitutes. */
-void clearSubstitutes();
-
 /* Register the validity of a path, i.e., that `path' exists, that the
    paths referenced by it exists, and in the case of an output path of
    a derivation, that it has been produced by a succesful execution of
@@ -103,14 +102,6 @@ void registerValidPath(const Transaction & txn,
     const Path & path, const Hash & hash, const PathSet & references,
     const Path & deriver);
 
-struct ValidPathInfo 
-{
-    Path path;
-    Path deriver;
-    Hash hash;
-    PathSet references;
-};
-
 typedef list<ValidPathInfo> ValidPathInfos;
 
 void registerValidPaths(const Transaction & txn,
diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc
index 1319245c057c..25529d8bac67 100644
--- a/src/libstore/misc.cc
+++ b/src/libstore/misc.cc
@@ -63,8 +63,7 @@ void queryMissing(const PathSet & targets,
             bool mustBuild = false;
             for (DerivationOutputs::iterator i = drv.outputs.begin();
                  i != drv.outputs.end(); ++i)
-                if (!store->isValidPath(i->second.path) &&
-                    !store->hasSubstitutes(i->second.path))
+                if (!store->isValidPath(i->second.path) && !store->hasSubstitutes(i->second.path))
                     mustBuild = true;
 
             if (mustBuild) {
@@ -83,8 +82,8 @@ void queryMissing(const PathSet & targets,
             if (store->isValidPath(p)) continue;
             if (store->hasSubstitutes(p))
                 willSubstitute.insert(p);
-            PathSet refs;
-            store->queryReferences(p, todo);
+            // XXX call the substituters
+            // store->queryReferences(p, todo);
         }
     }
 }
diff --git a/src/libstore/remote-store.cc b/src/libstore/remote-store.cc
index 820bf66ad99a..c5d13bf49495 100644
--- a/src/libstore/remote-store.cc
+++ b/src/libstore/remote-store.cc
@@ -164,12 +164,6 @@ bool RemoteStore::isValidPath(const Path & path)
 }
 
 
-Substitutes RemoteStore::querySubstitutes(const Path & path)
-{
-    throw Error("not implemented 2");
-}
-
-
 bool RemoteStore::hasSubstitutes(const Path & path)
 {
     writeInt(wopHasSubstitutes, to);
@@ -221,6 +215,12 @@ Path RemoteStore::queryDeriver(const Path & path)
 }
 
 
+PathSet RemoteStore::querySubstitutablePaths()
+{
+    throw Error("not implemented");
+}
+
+
 Path RemoteStore::addToStore(const Path & _srcPath, bool fixed,
     bool recursive, string hashAlgo, PathFilter & filter)
 {
diff --git a/src/libstore/remote-store.hh b/src/libstore/remote-store.hh
index 29b4a88f9a4b..87850c406873 100644
--- a/src/libstore/remote-store.hh
+++ b/src/libstore/remote-store.hh
@@ -27,10 +27,6 @@ public:
     
     bool isValidPath(const Path & path);
 
-    Substitutes querySubstitutes(const Path & path);
-
-    bool hasSubstitutes(const Path & path);
-    
     Hash queryPathHash(const Path & path);
 
     void queryReferences(const Path & path, PathSet & references);
@@ -39,6 +35,10 @@ public:
 
     Path queryDeriver(const Path & path);
     
+    PathSet querySubstitutablePaths();
+    
+    bool hasSubstitutes(const Path & path);
+    
     Path addToStore(const Path & srcPath, bool fixed = false,
         bool recursive = false, string hashAlgo = "",
         PathFilter & filter = defaultPathFilter);
diff --git a/src/libstore/store-api.cc b/src/libstore/store-api.cc
index 4d5441318832..9eb313da01ff 100644
--- a/src/libstore/store-api.cc
+++ b/src/libstore/store-api.cc
@@ -8,7 +8,8 @@ namespace nix {
 
 bool StoreAPI::hasSubstitutes(const Path & path)
 {
-    return !querySubstitutes(path).empty();
+    PathSet paths = querySubstitutablePaths();
+    return paths.find(path) != paths.end();
 }
 
 
@@ -130,6 +131,24 @@ Path computeStorePathForText(const string & suffix, const string & s,
 }
 
 
+ValidPathInfo decodeValidPathInfo(std::istream & str)
+{
+    ValidPathInfo info;
+    getline(str, info.path);
+    if (str.eof()) { info.path = ""; return info; }
+    getline(str, info.deriver);
+    string s; int n;
+    getline(str, s);
+    if (!string2Int(s, n)) throw Error("number expected");
+    while (n--) {
+        getline(str, s);
+        info.references.insert(s);
+    }
+    if (!str || str.eof()) throw Error("missing input");
+    return info;
+}
+
+
 }
 
 
diff --git a/src/libstore/store-api.hh b/src/libstore/store-api.hh
index 01b561e9d496..f133302b2f84 100644
--- a/src/libstore/store-api.hh
+++ b/src/libstore/store-api.hh
@@ -13,28 +13,6 @@
 namespace nix {
 
 
-/* A substitute is a program invocation that constructs some store
-   path (typically by fetching it from somewhere, e.g., from the
-   network). */
-struct Substitute
-{       
-    /* The derivation that built this store path (empty if none). */
-    Path deriver;
-    
-    /* Program to be executed to create the store path.  Must be in
-       the output path of `storeExpr'. */
-    Path program;
-
-    /* Extra arguments to be passed to the program (the first argument
-       is the store path to be substituted). */
-    Strings args;
-
-    bool operator == (const Substitute & sub) const;
-};
-
-typedef list<Substitute> Substitutes;
-
-
 typedef std::map<Path, Path> Roots;
 
 
@@ -57,13 +35,6 @@ public:
     /* Checks whether a path is valid. */ 
     virtual bool isValidPath(const Path & path) = 0;
 
-    /* Return the substitutes for the given path. */
-    virtual Substitutes querySubstitutes(const Path & path) = 0;
-
-    /* More efficient variant if we just want to know if a path has
-       substitutes. */
-    virtual bool hasSubstitutes(const Path & path);
-
     /* Queries the hash of a valid path. */ 
     virtual Hash queryPathHash(const Path & path) = 0;
 
@@ -81,6 +52,13 @@ public:
        no deriver has been set. */
     virtual Path queryDeriver(const Path & path) = 0;
 
+    /* Query the set of substitutable paths. */
+    virtual PathSet querySubstitutablePaths() = 0;
+
+    /* More efficient variant if we just want to know if a path has
+       substitutes. */
+    virtual bool hasSubstitutes(const Path & path);
+    
     /* Copy the contents of a path to the store and register the
        validity the resulting path.  The resulting path is returned.
        If `fixed' is true, then the output of a fixed-output
@@ -109,10 +87,10 @@ public:
 
     /* Ensure that the output paths of the derivation are valid.  If
        they are already valid, this is a no-op.  Otherwise, validity
-       can be reached in two ways.  First, if the output paths have
-       substitutes, then those can be used.  Second, the output paths
-       can be created by running the builder, after recursively
-       building any sub-derivations. */
+       can be reached in two ways.  First, if the output paths is
+       substitutable, then build the path that way.  Second, the
+       output paths can be created by running the builder, after
+       recursively building any sub-derivations. */
     virtual void buildDerivations(const PathSet & drvPaths) = 0;
 
     /* Ensure that a path is valid.  If it is not currently valid, it
@@ -261,6 +239,17 @@ extern boost::shared_ptr<StoreAPI> store;
 boost::shared_ptr<StoreAPI> openStore(bool reserveSpace = true);
 
 
+struct ValidPathInfo 
+{
+    Path path;
+    Path deriver;
+    Hash hash;
+    PathSet references;
+};
+
+ValidPathInfo decodeValidPathInfo(std::istream & str);
+
+
 }
 
 
diff --git a/src/libstore/worker-protocol.hh b/src/libstore/worker-protocol.hh
index 4a2e8b6942cf..3fdfa1807b3c 100644
--- a/src/libstore/worker-protocol.hh
+++ b/src/libstore/worker-protocol.hh
@@ -12,7 +12,6 @@ namespace nix {
 typedef enum {
     wopQuit,
     wopIsValidPath,
-    wopQuerySubstitutes,
     wopHasSubstitutes,
     wopQueryPathHash,
     wopQueryReferences,