* Re-enable support for substitutes in the normaliser.

* A better substitute mechanism.

  Instead of generating a store expression for each store path for
  which we have a substitute, we can have a single store expression
  that builds a generic program that is invoked to build the desired
  store path, which is passed as an argument.

  This means that operations like `nix-pull' only produce O(1) files
  instead of O(N) files in the store when registering N substitutes.
  (It consumes O(N) database storage, of course, but that's not a
  performance problem).

* Added a test for the substitute mechanism.
  
* `nix-store --substitute' reads the substitutes from standard input,
  instead of from the command line.  This prevents us from running
  into the kernel's limit on command line length.

10 files changed, 444 insertions, 108 deletions

diff --git a/src/libstore/normalise.cc b/src/libstore/normalise.cc
index e69738ceb579..f4159f65a13e 100644
--- a/src/libstore/normalise.cc
+++ b/src/libstore/normalise.cc
@@ -160,6 +160,26 @@ public:
 //////////////////////////////////////////////////////////////////////
 
 
+void killChild(pid_t pid)
+{
+    /* Send a KILL signal to every process in the child process group
+       (which hopefully includes *all* its children). */
+    if (kill(-pid, SIGKILL) != 0)
+        printMsg(lvlError, format("killing process %1%") % pid);
+    else {
+        /* Wait until the child dies, disregarding the exit status. */
+        int status;
+        while (waitpid(pid, &status, 0) == -1)
+            if (errno != EINTR) printMsg(lvlError,
+                format("waiting for process %1%") % pid);
+    }
+}
+
+
+
+//////////////////////////////////////////////////////////////////////
+
+
 void Goal::addWaiter(GoalPtr waiter)
 {
     waiters.insert(waiter);
@@ -197,9 +217,6 @@ private:
     
     /* The remainder is state held during the build. */
 
-    /* Whether it's being built by a hook or by ourselves. */
-    bool inHook;
-
     /* Locks on the output paths. */
     PathLocks outputLocks;
 
@@ -305,20 +322,7 @@ NormalisationGoal::~NormalisationGoal()
     if (pid != -1) {
         printMsg(lvlError, format("killing child process %1% (%2%)")
             % pid % nePath);
-
-        /* Send a KILL signal to every process in the child
-           process group (which hopefully includes *all* its
-           children). */
-        if (kill(-pid, SIGKILL) != 0)
-            printMsg(lvlError, format("killing process %1%") % pid);
-        else {
-            /* Wait until the child dies, disregarding the exit
-               status. */
-            int status;
-            while (waitpid(pid, &status, 0) == -1)
-                if (errno != EINTR) printMsg(lvlError,
-                    format("waiting for process %1%") % pid);
-        }
+        killChild(pid);
     }
 
     try {
@@ -488,7 +492,7 @@ void NormalisationGoal::buildDone()
     /* Close the log file. */
     fdLogFile.close();
 
-    debug(format("builder process %1% finished") % pid);
+    debug(format("builder process for `%1%' finished") % nePath);
 
     /* Check the exit status. */
     if (!WIFEXITED(status) || WEXITSTATUS(status) != 0) {
@@ -501,8 +505,9 @@ void NormalisationGoal::buildDone()
                 % nePath % WTERMSIG(status));
         else
             throw Error(format("builder for `%1%' failed died abnormally") % nePath);
-    } else
-        deleteTmpDir(true);
+    }
+    
+    deleteTmpDir(true);
 
     /* Compute a closure store expression, and register it as our
        successor. */
@@ -629,6 +634,7 @@ NormalisationGoal::HookReply NormalisationGoal::tryBuildHook()
         /* Acquire locks and such.  If we then see that there now is a
            successor, we're done. */
         if (!prepareBuild()) {
+            /* Tell the hook to exit. */
             writeLine(toHook.writeSide, "cancel");
             terminateBuildHook();
             return rpDone;
@@ -664,10 +670,9 @@ NormalisationGoal::HookReply NormalisationGoal::tryBuildHook()
             s += i->first + " " + i->second + "\n";
         writeStringToFile(successorsListFN, s);
 
+        /* Tell the hook to proceed. */ 
         writeLine(toHook.writeSide, "okay");
 
-        inHook = true;
-    
         return rpAccept;
     }
 
@@ -1187,6 +1192,21 @@ private:
     /* The store path that should be realised through a substitute. */
     Path storePath;
 
+    /* The remaining substitutes for this path. */
+    Substitutes subs;
+
+    /* The current substitute. */
+    Substitute sub;
+
+    /* The normal form of the substitute store expression. */
+    Path nfSub;
+
+    /* Pipe for the substitute's standard output/error. */
+    Pipe logPipe;
+
+    /* The process ID of the builder. */
+    pid_t pid;
+
     typedef void (SubstitutionGoal::*GoalState)();
     GoalState state;
 
@@ -1198,6 +1218,10 @@ public:
 
     /* The states. */
     void init();
+    void tryNext();
+    void exprNormalised();
+    void exprRealised();
+    void finished();
 };
 
 
@@ -1205,12 +1229,19 @@ SubstitutionGoal::SubstitutionGoal(const Path & _storePath, Worker & _worker)
     : Goal(_worker)
 {
     storePath = _storePath;
+    pid = -1;
     state = &SubstitutionGoal::init;
 }
 
 
 SubstitutionGoal::~SubstitutionGoal()
 {
+    /* !!! turn this into a destructor for pids */
+    if (pid != -1) {
+        printMsg(lvlError, format("killing child process %1% (%2%)")
+            % pid % storePath);
+        killChild(pid);
+    }
 }
 
 
@@ -1230,7 +1261,171 @@ void SubstitutionGoal::init()
         return;
     }
 
-    abort();
+    /* Otherwise, get the substitutes. */
+    subs = querySubstitutes(storePath);
+
+    /* Try the first one. */
+    tryNext();
+}
+
+
+void SubstitutionGoal::tryNext()
+{
+    debug(format("trying next substitute of `%1%'") % storePath);
+
+    if (subs.size() == 0) throw Error(
+        format("path `%1%' is required, but it has no (remaining) substitutes")
+            % storePath);
+    sub = subs.front();
+    subs.pop_front();
+
+    /* Normalise the substitute store expression. */
+    worker.addNormalisationGoal(sub.storeExpr, shared_from_this());
+    nrWaitees = 1;
+
+    state = &SubstitutionGoal::exprNormalised;
+}
+
+
+void SubstitutionGoal::exprNormalised()
+{
+    debug(format("store expr normalised of `%1%'") % storePath);
+
+    /* Realise the substitute store expression. */
+    if (!querySuccessor(sub.storeExpr, nfSub))
+        nfSub = sub.storeExpr;
+    worker.addRealisationGoal(nfSub, shared_from_this());
+    nrWaitees = 1;
+
+    state = &SubstitutionGoal::exprRealised;
+}
+
+
+void SubstitutionGoal::exprRealised()
+{
+    debug(format("store expr realised of `%1%'") % storePath);
+
+    /* What's the substitute program? */
+    StoreExpr expr = storeExprFromPath(nfSub);
+    assert(expr.type == StoreExpr::neClosure);
+    assert(!expr.closure.roots.empty());
+    Path program =
+        canonPath(*expr.closure.roots.begin() + "/" + sub.program);
+
+    printMsg(lvlChatty, format("executing substitute `%1%'") % program);
+
+    logPipe.create();
+
+    /* Fork the substitute program. */
+    switch (pid = fork()) {
+        
+    case -1:
+        throw SysError("unable to fork");
+
+    case 0:
+        try { /* child */
+
+            logPipe.readSide.close();
+
+            /* !!! close other handles */
+
+            /* !!! this is cut & paste - fix */
+
+            /* Put the child in a separate process group so that it
+               doesn't receive terminal signals. */
+            if (setpgid(0, 0) == -1)
+                throw SysError(format("setting process group"));
+            
+            /* Dup the write side of the logger pipe into stderr. */
+            if (dup2(logPipe.writeSide, STDERR_FILENO) == -1)
+                throw SysError("cannot pipe standard error into log file");
+            logPipe.readSide.close();
+            
+            /* Dup stderr to stdin. */
+            if (dup2(STDERR_FILENO, STDOUT_FILENO) == -1)
+                throw SysError("cannot dup stderr into stdout");
+
+            /* Reroute stdin to /dev/null. */
+            int fdDevNull = open(pathNullDevice.c_str(), O_RDWR);
+            if (fdDevNull == -1)
+                throw SysError(format("cannot open `%1%'") % pathNullDevice);
+            if (dup2(fdDevNull, STDIN_FILENO) == -1)
+                throw SysError("cannot dup null device into stdin");
+
+            /* Fill in the arguments.  !!! cut & paste */
+            const char * argArr[sub.args.size() + 3];
+            const char * * p = argArr;
+            string progName = baseNameOf(program);
+            *p++ = progName.c_str();
+            *p++ = storePath.c_str();
+            for (Strings::const_iterator i = sub.args.begin();
+                 i != sub.args.end(); i++)
+                *p++ = i->c_str();
+            *p = 0;
+
+            execv(program.c_str(), (char * *) argArr);
+            
+            throw SysError(format("executing `%1%'") % program);
+            
+        } catch (exception & e) {
+            cerr << format("substitute error: %1%\n") % e.what();
+        }
+        _exit(1);
+    }
+    
+    /* parent */
+    logPipe.writeSide.close();
+    worker.childStarted(shared_from_this(),
+        pid, logPipe.readSide, false);
+
+    state = &SubstitutionGoal::finished;
+}
+
+
+void SubstitutionGoal::finished()
+{
+    debug(format("substitute finished of `%1%'") % storePath);
+
+    int status;
+
+    /* Since we got an EOF on the logger pipe, the substitute is
+       presumed to have terminated.  */
+    /* !!! this could block! */
+    if (waitpid(pid, &status, 0) != pid)
+        throw SysError(format("substitute for `%1%' should have terminated")
+            % storePath);
+
+    /* So the child is gone now. */
+    worker.childTerminated(pid);
+    pid = -1;
+
+    /* Close the read side of the logger pipe. */
+    logPipe.readSide.close();
+
+    debug(format("substitute for `%1%' finished") % storePath);
+
+    /* Check the exit status. */
+    /* !!! cut & paste */
+    if (!WIFEXITED(status) || WEXITSTATUS(status) != 0) {
+        if (WIFEXITED(status))
+            throw Error(format("builder for `%1%' failed with exit code %2%")
+                % storePath % WEXITSTATUS(status));
+        else if (WIFSIGNALED(status))
+            throw Error(format("builder for `%1%' failed due to signal %2%")
+                % storePath % WTERMSIG(status));
+        else
+            throw Error(format("builder for `%1%' failed died abnormally") % storePath);
+    }
+
+    if (!pathExists(storePath))
+        throw Error(format("substitute did not produce path `%1%'") % storePath);
+
+    Transaction txn;
+    createStoreTransaction(txn);
+    registerValidPath(txn, storePath);
+    txn.commit();
+
+    amDone();
 }
 
 
diff --git a/src/libstore/store.cc b/src/libstore/store.cc
index a89e4ed89fa7..74f182468a5d 100644
--- a/src/libstore/store.cc
+++ b/src/libstore/store.cc
@@ -41,10 +41,12 @@ static TableId dbSuccessors;
 */
 static TableId dbSuccessorsRev;
 
-/* dbSubstitutes :: Path -> [Path]
+/* dbSubstitutes :: Path -> [(Path, Path, [string])]
 
-   Each pair $(p, [ps])$ tells Nix that it can realise any of the
-   Nix expressions stored at paths $ps$ to produce a path $p$.
+   Each pair $(p, subs)$ tells Nix that it can use any of the
+   substitutes in $subs$ to build path $p$.  Each substitute is a
+   tuple $(storeExpr, program, args)$ (see the type `Substitute' in
+   `store.hh').
 
    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
@@ -56,11 +58,20 @@ static TableId dbSubstitutes;
 
 /* dbSubstitutesRev :: Path -> [Path]
 
-   The reverse mapping of dbSubstitutes.
+   The reverse mapping of dbSubstitutes; it maps store expressions
+   back to the paths for which they are substitutes.
 */
 static TableId dbSubstitutesRev;
 
 
+bool Substitute::operator == (const Substitute & sub)
+{
+    return storeExpr == sub.storeExpr
+        && program == sub.program
+        && args == sub.args;
+}
+
+
 void openDB()
 {
     nixDB.open(nixDBPath);
@@ -241,44 +252,89 @@ Paths queryPredecessors(const Path & sucPath)
 }
 
 
-void registerSubstitute(const Path & srcPath, const Path & subPath)
+static Substitutes readSubstitutes(const Transaction & txn,
+    const Path & srcPath)
 {
-    assertStorePath(srcPath);
-    assertStorePath(subPath);
+    Strings ss;
+    nixDB.queryStrings(txn, dbSubstitutes, srcPath, ss);
+
+    Substitutes subs;
     
-    if (!isValidPathTxn(subPath, noTxn)) throw Error(
-	format("path `%1%' cannot be a substitute, since it is not valid")
-	% subPath);
+    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;
+        }
+        Strings ss2 = unpackStrings(*i);
+        if (ss2.size() != 3) throw Error("malformed substitute");
+        Strings::iterator j = ss2.begin();
+        Substitute sub;
+        sub.storeExpr = *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(i->storeExpr);
+        ss2.push_back(i->program);
+        ss2.push_back(packStrings(i->args));
+        ss.push_back(packStrings(ss2));
+    }
 
+    if (ss.size() == 0)
+        nixDB.delPair(txn, dbSubstitutes, srcPath);
+    else
+        nixDB.setStrings(txn, dbSubstitutes, srcPath, ss);
+}
+
+
+void registerSubstitute(const Path & srcPath,
+    const Substitute & sub)
+{
+    assertStorePath(srcPath);
+    assertStorePath(sub.storeExpr);
+    
     Transaction txn(nixDB);
 
-    Paths subs;
-    nixDB.queryStrings(txn, dbSubstitutes, srcPath, subs);
+    Substitutes subs = readSubstitutes(txn, srcPath);
 
-    if (find(subs.begin(), subs.end(), subPath) != subs.end()) {
+    if (find(subs.begin(), subs.end(), sub) != subs.end()) {
         /* Nothing to do if the substitute is already known. */
         txn.abort();
         return;
     }
-    subs.push_front(subPath); /* new substitutes take precedence */
+    subs.push_front(sub); /* new substitutes take precedence */
 
+    writeSubstitutes(txn, srcPath, subs);
+    
     Paths revs;
-    nixDB.queryStrings(txn, dbSubstitutesRev, subPath, revs);
+    nixDB.queryStrings(txn, dbSubstitutesRev, sub.storeExpr, revs);
     if (find(revs.begin(), revs.end(), srcPath) == revs.end())
         revs.push_back(srcPath);
     
-    nixDB.setStrings(txn, dbSubstitutes, srcPath, subs);
-    nixDB.setStrings(txn, dbSubstitutesRev, subPath, revs);
+    nixDB.setStrings(txn, dbSubstitutesRev, sub.storeExpr, revs);
 
     txn.commit();
 }
 
 
-Paths querySubstitutes(const Path & srcPath)
+Substitutes querySubstitutes(const Path & srcPath)
 {
-    Paths subPaths;
-    nixDB.queryStrings(noTxn, dbSubstitutes, srcPath, subPaths);
-    return subPaths;
+    return readSubstitutes(noTxn, srcPath);
 }
 
 
@@ -291,16 +347,6 @@ void registerValidPath(const Transaction & txn, const Path & _path)
 }
 
 
-static void setOrClearStrings(Transaction & txn,
-    TableId table, const string & key, const Strings & value)
-{
-    if (value.size() > 0)
-        nixDB.setStrings(txn, table, key, value);
-    else
-        nixDB.delPair(txn, table, key);
-}
-
-
 static void invalidatePath(const Path & path, Transaction & txn)
 {
     debug(format("unregistering path `%1%'") % path);
@@ -319,12 +365,15 @@ static void invalidatePath(const Path & path, Transaction & txn)
     revs.clear();
     nixDB.queryStrings(txn, dbSubstitutesRev, path, revs);
     for (Paths::iterator i = revs.begin(); i != revs.end(); ++i) {
-        Paths subs;
-        nixDB.queryStrings(txn, dbSubstitutes, *i, subs);
-        if (find(subs.begin(), subs.end(), path) == subs.end())
-            throw Error("integrity error in substitutes mapping");
-        subs.remove(path);
-        setOrClearStrings(txn, dbSubstitutes, *i, subs);
+        Substitutes subs = readSubstitutes(txn, *i), subs2;
+        bool found = false;
+        for (Substitutes::iterator j = subs.begin(); j != subs.end(); ++j)
+            if (j->storeExpr != path)
+                subs2.push_back(*j);
+            else
+                found = true;
+        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,
 	   then it too should be invalidated.  This is because it may
@@ -438,28 +487,28 @@ void verifyStore()
 
     /* Check that the values of the substitute mappings are valid
        paths. */ 
-    Paths subs;
-    nixDB.enumTable(txn, dbSubstitutes, subs);
-    for (Paths::iterator i = subs.begin(); i != subs.end(); ++i) {
-        Paths subPaths, subPaths2;
-        nixDB.queryStrings(txn, dbSubstitutes, *i, subPaths);
-        for (Paths::iterator j = subPaths.begin(); j != subPaths.end(); ++j)
-            if (validPaths.find(*j) == validPaths.end())
+    Paths subKeys;
+    nixDB.enumTable(txn, dbSubstitutes, subKeys);
+    for (Paths::iterator i = subKeys.begin(); i != subKeys.end(); ++i) {
+        Substitutes subs = readSubstitutes(txn, *i), subs2;
+        for (Substitutes::iterator j = subs.begin(); j != subs.end(); ++j)
+            if (validPaths.find(j->storeExpr) == validPaths.end())
                 printMsg(lvlError,
-                    format("found substitute mapping to non-existent path `%1%'") % *j);
+                    format("found substitute mapping to non-existent path `%1%'")
+                    % j->storeExpr);
             else
-                subPaths2.push_back(*j);
-        if (subPaths.size() != subPaths2.size())
-            setOrClearStrings(txn, dbSubstitutes, *i, subPaths2);
-	if (subPaths2.size() > 0)
+                subs2.push_back(*j);
+        if (subs.size() != subs2.size())
+            writeSubstitutes(txn, *i, subs2);
+	if (subs2.size() > 0)
 	    usablePaths.insert(*i);
     }
 
     /* Check that the keys of the reverse substitute mappings are
        valid paths. */ 
-    Paths rsubs;
-    nixDB.enumTable(txn, dbSubstitutesRev, rsubs);
-    for (Paths::iterator i = rsubs.begin(); i != rsubs.end(); ++i) {
+    Paths rsubKeys;
+    nixDB.enumTable(txn, dbSubstitutesRev, rsubKeys);
+    for (Paths::iterator i = rsubKeys.begin(); i != rsubKeys.end(); ++i) {
         if (validPaths.find(*i) == validPaths.end()) {
             printMsg(lvlError,
                 format("found reverse substitute mapping for non-existent path `%1%'") % *i);
@@ -469,9 +518,9 @@ void verifyStore()
 
     /* Check that the values of the successor mappings are usable
        paths. */ 
-    Paths sucs;
-    nixDB.enumTable(txn, dbSuccessors, sucs);
-    for (Paths::iterator i = sucs.begin(); i != sucs.end(); ++i) {
+    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;
@@ -486,9 +535,9 @@ void verifyStore()
 
     /* Check that the keys of the reverse successor mappings are valid
        paths. */ 
-    Paths rsucs;
-    nixDB.enumTable(txn, dbSuccessorsRev, rsucs);
-    for (Paths::iterator i = rsucs.begin(); i != rsucs.end(); ++i) {
+    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);
diff --git a/src/libstore/store.hh b/src/libstore/store.hh
index 571d498c362d..e09a4a94b70d 100644
--- a/src/libstore/store.hh
+++ b/src/libstore/store.hh
@@ -9,6 +9,29 @@
 using namespace std;
 
 
+/* A substitute is a program invocation that constructs some store
+   path (typically by fetching it from somewhere, e.g., from the
+   network). */
+struct Substitute
+{
+    /* Store expression to be normalised and realised in order to
+       obtain `program'. */
+    Path storeExpr;
+
+    /* 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);
+};
+
+typedef list<Substitute> Substitutes;
+
+
 /* Open the database environment. */
 void openDB();
 
@@ -40,10 +63,11 @@ bool querySuccessor(const Path & srcPath, Path & sucPath);
 Paths queryPredecessors(const Path & sucPath);
 
 /* Register a substitute. */
-void registerSubstitute(const Path & srcPath, const Path & subPath);
+void registerSubstitute(const Path & srcPath,
+    const Substitute & sub);
 
 /* Return the substitutes expression for the given path. */
-Paths querySubstitutes(const Path & srcPath);
+Substitutes querySubstitutes(const Path & srcPath);
 
 /* Register the validity of a path. */
 void registerValidPath(const Transaction & txn, const Path & path);
diff --git a/src/nix-env/main.cc b/src/nix-env/main.cc
index 8cbc3b7038ba..50ff0b19e9fc 100644
--- a/src/nix-env/main.cc
+++ b/src/nix-env/main.cc
@@ -499,7 +499,7 @@ static void opQuery(Globals & globals,
                 installedPaths.insert(i->second.outPath);
             
             for (DrvInfoList::iterator i = drvs2.begin(); i != drvs2.end(); ++i) {
-                Paths subs = querySubstitutes(i->drvPath);
+                Substitutes subs = querySubstitutes(i->drvPath);
                 cout << format("%1%%2%%3% %4%\n")
                     % (installedPaths.find(i->outPath)
                         != installedPaths.end() ? 'I' : '-')
diff --git a/src/nix-store/main.cc b/src/nix-store/main.cc
index 4be8e8f4495b..79d65c4be5d5 100644
--- a/src/nix-store/main.cc
+++ b/src/nix-store/main.cc
@@ -18,12 +18,6 @@ void printHelp()
 }
 
 
-static Path checkPath(const Path & arg)
-{
-    return arg; /* !!! check that arg is in the store */
-}
-
-
 /* Realise paths from the given store expressions. */
 static void opRealise(Strings opFlags, Strings opArgs)
 {
@@ -32,7 +26,7 @@ static void opRealise(Strings opFlags, Strings opArgs)
     for (Strings::iterator i = opArgs.begin();
          i != opArgs.end(); i++)
     {
-        Path nfPath = normaliseStoreExpr(checkPath(*i));
+        Path nfPath = normaliseStoreExpr(*i);
         realiseClosure(nfPath);
         cout << format("%1%\n") % (string) nfPath;
     }
@@ -46,7 +40,7 @@ static void opDelete(Strings opFlags, Strings opArgs)
 
     for (Strings::iterator it = opArgs.begin();
          it != opArgs.end(); it++)
-        deleteFromStore(checkPath(*it));
+        deleteFromStore(*it);
 }
 
 
@@ -101,7 +95,7 @@ static void opQuery(Strings opFlags, Strings opArgs)
                  i != opArgs.end(); i++)
             {
                 StringSet paths = storeExprRoots(
-                    maybeNormalise(checkPath(*i), normalise, realise));
+                    maybeNormalise(*i, normalise, realise));
                 for (StringSet::iterator j = paths.begin(); 
                      j != paths.end(); j++)
                     cout << format("%s\n") % *j;
@@ -115,7 +109,7 @@ static void opQuery(Strings opFlags, Strings opArgs)
                  i != opArgs.end(); i++)
             {
                 StringSet paths2 = storeExprRequisites(
-                    maybeNormalise(checkPath(*i), normalise, realise),
+                    maybeNormalise(*i, normalise, realise),
                     includeExprs, includeSuccessors);
                 paths.insert(paths2.begin(), paths2.end());
             }
@@ -129,7 +123,7 @@ static void opQuery(Strings opFlags, Strings opArgs)
             for (Strings::iterator i = opArgs.begin();
                  i != opArgs.end(); i++)
             {
-                Paths preds = queryPredecessors(checkPath(*i));
+                Paths preds = queryPredecessors(*i);
                 for (Paths::iterator j = preds.begin();
                      j != preds.end(); j++)
                     cout << format("%s\n") % *j;
@@ -141,7 +135,7 @@ static void opQuery(Strings opFlags, Strings opArgs)
             PathSet roots;
             for (Strings::iterator i = opArgs.begin();
                  i != opArgs.end(); i++)
-                roots.insert(maybeNormalise(checkPath(*i), normalise, realise));
+                roots.insert(maybeNormalise(*i, normalise, realise));
 	    printDotGraph(roots);
             break;
         }
@@ -162,8 +156,8 @@ static void opSuccessor(Strings opFlags, Strings opArgs)
     for (Strings::iterator i = opArgs.begin();
          i != opArgs.end(); )
     {
-        Path path1 = checkPath(*i++);
-        Path path2 = checkPath(*i++);
+        Path path1 = *i++;
+        Path path2 = *i++;
         registerSuccessor(txn, path1, path2);
     }
     txn.commit();
@@ -173,14 +167,28 @@ static void opSuccessor(Strings opFlags, Strings opArgs)
 static void opSubstitute(Strings opFlags, Strings opArgs)
 {
     if (!opFlags.empty()) throw UsageError("unknown flag");
-    if (opArgs.size() % 2) throw UsageError("expecting even number of arguments");
-    
-    for (Strings::iterator i = opArgs.begin();
-         i != opArgs.end(); )
-    {
-        Path src = checkPath(*i++);
-        Path sub = checkPath(*i++);
-        registerSubstitute(src, sub);
+    if (!opArgs.empty())
+        throw UsageError("no arguments expected");
+
+    while (1) {
+        Path srcPath;
+        Substitute sub;
+        getline(cin, srcPath);
+        if (cin.eof()) break;
+        getline(cin, sub.storeExpr);
+        getline(cin, sub.program);
+        string s;
+        getline(cin, s);
+        istringstream st(s);
+        int n;
+        st >> n;
+        if (!st) throw Error("number expected");
+        while (n--) {
+            getline(cin, s);
+            sub.args.push_back(s);
+        }
+        if (!cin || cin.eof()) throw Error("missing input");
+        registerSubstitute(srcPath, sub);
     }
 }
 
@@ -260,7 +268,7 @@ static void opInit(Strings opFlags, Strings opArgs)
 {
     if (!opFlags.empty()) throw UsageError("unknown flag");
     if (!opArgs.empty())
-        throw UsageError("--init does not have arguments");
+        throw UsageError("no arguments expected");
     initDB();
 }
 
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 4256625d9dc2..3f10b402b4b5 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -17,9 +17,10 @@ dependencies.sh: dependencies.nix
 locking.sh: locking.nix
 parallel.sh: parallel.nix
 build-hook.sh: build-hook.nix
+substitutes.sh: substitutes.nix substituter.nix
 
 TESTS = init.sh simple.sh dependencies.sh locking.sh parallel.sh \
-  build-hook.sh
+  build-hook.sh substitutes.sh
 
 XFAIL_TESTS =
 
diff --git a/tests/substituter.builder.sh b/tests/substituter.builder.sh
new file mode 100644
index 000000000000..c9ce0a08c6a8
--- /dev/null
+++ b/tests/substituter.builder.sh
@@ -0,0 +1,22 @@
+# Set a PATH (!!! impure).
+export PATH=/bin:/usr/bin:$PATH
+
+mkdir $out
+
+cat > $out/substituter <<EOF
+#! /bin/sh -ex
+echo \$*
+
+case \$* in
+    *aaaa*)
+        echo "Closure([\"\$2\"],[(\"\$2\",[])])" > \$1
+        ;;
+    *)
+        mkdir \$1
+        echo \$3 \$4 > \$1/hello
+        ;;
+esac        
+EOF
+
+chmod +x $out/substituter
+
diff --git a/tests/substituter.nix.in b/tests/substituter.nix.in
new file mode 100644
index 000000000000..8f9da530c38e
--- /dev/null
+++ b/tests/substituter.nix.in
@@ -0,0 +1,6 @@
+derivation {
+  name = "substituter";
+  system = "@system@";
+  builder = "@shell@";
+  args = ["-e" "-x" ./substituter.builder.sh];
+}
\ No newline at end of file
diff --git a/tests/substitutes.nix.in b/tests/substitutes.nix.in
new file mode 100644
index 000000000000..e3473621608d
--- /dev/null
+++ b/tests/substitutes.nix.in
@@ -0,0 +1,6 @@
+derivation {
+  name = "substitutes";
+  system = "@system@";
+  builder = "@shell@";
+  args = ["-e" "-x" ./simple.builder.sh];
+}
\ No newline at end of file
diff --git a/tests/substitutes.sh b/tests/substitutes.sh
new file mode 100644
index 000000000000..ea214a8a8a43
--- /dev/null
+++ b/tests/substitutes.sh
@@ -0,0 +1,25 @@
+# Instantiate.
+storeExpr=$($TOP/src/nix-instantiate/nix-instantiate substitutes.nix)
+echo "store expr is $storeExpr"
+
+# Find the output path.
+outPath=$($TOP/src/nix-store/nix-store -qvvvvv "$storeExpr")
+echo "output path is $outPath"
+
+# Instantiate the substitute program.
+subExpr=$($TOP/src/nix-instantiate/nix-instantiate substituter.nix)
+echo "store expr is $subExpr"
+
+# Register a fake successor, and a substitute for it.
+suc=$NIX_STORE_DIR/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa-s.store
+(echo $suc && echo $subExpr && echo "/substituter" && echo 3 && echo $outPath && echo Hallo && echo Wereld) | $TOP/src/nix-store/nix-store --substitute
+$TOP/src/nix-store/nix-store --successor $storeExpr $suc
+
+# Register a substitute for the output path.
+(echo $outPath && echo $subExpr && echo "/substituter" && echo 3 && echo $outPath && echo Hallo && echo Wereld) | $TOP/src/nix-store/nix-store --substitute
+
+
+$TOP/src/nix-store/nix-store -rvvvvv "$storeExpr"
+
+text=$(cat "$outPath"/hello)
+if test "$text" != "Hallo Wereld"; then exit 1; fi