* 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.

3 files changed, 351 insertions, 83 deletions

diff --git a/src/libstore/normalise.cc b/src/libstore/normalise.cc
index e69738ceb..f4159f65a 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 a89e4ed89..74f182468 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 571d498c3..e09a4a94b 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);