6 files changed, 66 insertions, 25 deletions
diff --git a/src/globals.cc b/src/globals.cc
index f34f8f1029c5..22d2758b61b0 100644
--- a/src/globals.cc
+++ b/src/globals.cc
@@ -7,7 +7,9 @@ Database nixDB;
 
 TableId dbValidPaths;
 TableId dbSuccessors;
+TableId dbSuccessorsRev;
 TableId dbSubstitutes;
+TableId dbSubstitutesRev;
 
 
 string nixStore = "/UNINIT";
@@ -24,7 +26,9 @@ void openDB()
     nixDB.open(nixDBPath);
     dbValidPaths = nixDB.openTable("validpaths");
     dbSuccessors = nixDB.openTable("successors");
+    dbSuccessorsRev = nixDB.openTable("successors-rev");
     dbSubstitutes = nixDB.openTable("substitutes");
+    dbSubstitutesRev = nixDB.openTable("substitutes-rev");
 }
 
 
diff --git a/src/globals.hh b/src/globals.hh
index 0ea2fca092c3..910e47e01cdd 100644
--- a/src/globals.hh
+++ b/src/globals.hh
@@ -33,6 +33,13 @@ extern TableId dbValidPaths;
 extern TableId dbSuccessors;
 
 
+/* dbSuccessorsRev :: Path -> [Path]
+
+   The reverse mapping of dbSuccessors.
+*/
+extern TableId dbSuccessorsRev;
+
+
 /* dbSubstitutes :: Path -> [Path]
 
    Each pair $(p, [ps])$ tells Nix that it can realise any of the
@@ -47,6 +54,13 @@ extern TableId dbSuccessors;
 extern TableId dbSubstitutes;
 
 
+/* dbSubstitutesRev :: Path -> [Path]
+
+   The reverse mapping of dbSubstitutes.
+*/
+extern TableId dbSubstitutesRev;
+
+
 /* Path names. */
 
 /* nixStore is the directory where we generally store atomic and
diff --git a/src/normalise.cc b/src/normalise.cc
index 834276f1beff..0dfc9f8e4d12 100644
--- a/src/normalise.cc
+++ b/src/normalise.cc
@@ -8,13 +8,6 @@
 #include "globals.hh"
 
 
-void registerSuccessor(const Transaction & txn,
-    const Path & path1, const Path & path2)
-{
-    nixDB.setString(txn, dbSuccessors, path1, path2);
-}
-
-
 static Path useSuccessor(const Path & path)
 {
     string pathSucc;
diff --git a/src/normalise.hh b/src/normalise.hh
index 4b4db4ee2a07..e8e72f5bc857 100644
--- a/src/normalise.hh
+++ b/src/normalise.hh
@@ -34,9 +34,5 @@ PathSet nixExprRequisites(const Path & nePath,
    output paths are completely contained in the set `outputs'. */
 PathSet findGenerators(const PathSet & outputs);
 
-/* Register a successor. */
-void registerSuccessor(const Transaction & txn,
-    const Path & path1, const Path & path2);
-
 
 #endif /* !__NORMALISE_H */
diff --git a/src/store.cc b/src/store.cc
index b2b479e0ddaa..de1dcca7082e 100644
--- a/src/store.cc
+++ b/src/store.cc
@@ -81,26 +81,50 @@ void copyPath(const Path & src, const Path & dst)
 }
 
 
+void registerSuccessor(const Transaction & txn,
+    const Path & path1, const Path & path2)
+{
+    Path known;
+    if (nixDB.queryString(txn, dbSuccessors, path1, known) &&
+        known != path2)
+    {
+        throw Error(format(
+            "the `impossible' happened: expression in path "
+            "`%1%' appears to have multiple successors "
+            "(known `%2%', new `%3%'")
+            % path1 % known % path2);
+    }
+
+    Paths revs;
+    nixDB.queryStrings(txn, dbSuccessorsRev, path2, revs);
+    revs.push_back(path1);
+
+    nixDB.setString(txn, dbSuccessors, path1, path2);
+    nixDB.setStrings(txn, dbSuccessorsRev, path2, revs);
+}
+
+
 void registerSubstitute(const Path & srcPath, const Path & subPath)
 {
-#if 0
-    Strings subs;
-    queryListDB(nixDB, dbSubstitutes, srcId, subs); /* non-existence = ok */
+    Transaction txn(nixDB);
 
-    for (Strings::iterator it = subs.begin(); it != subs.end(); it++)
-        if (parseHash(*it) == subId) return;
-    
-    subs.push_back(subId);
-    
-    setListDB(nixDB, dbSubstitutes, srcId, subs);
-#endif
+    Paths subs;
+    nixDB.queryStrings(txn, dbSubstitutes, srcPath, subs);
 
-    /* For now, accept only one substitute per id. */
-    Strings subs;
-    subs.push_back(subPath);
+    if (find(subs.begin(), subs.end(), subPath) != subs.end()) {
+        /* Nothing to do if the substitute is already known. */
+        txn.abort();
+        return;
+    }
+    subs.push_front(subPath); /* new substitutes take precedence */
+
+    Paths revs;
+    nixDB.queryStrings(txn, dbSubstitutesRev, subPath, revs);
+    revs.push_back(srcPath);
     
-    Transaction txn(nixDB);
     nixDB.setStrings(txn, dbSubstitutes, srcPath, subs);
+    nixDB.setStrings(txn, dbSubstitutesRev, subPath, revs);
+
     txn.commit();
 }
 
diff --git a/src/store.hh b/src/store.hh
index 69de8247860f..7b32a1a731e9 100644
--- a/src/store.hh
+++ b/src/store.hh
@@ -12,6 +12,16 @@ using namespace std;
 /* Copy a path recursively. */
 void copyPath(const Path & src, const Path & dst);
 
+/* Register a successor.  This function accepts a transaction handle
+   so that it can be enclosed in an atomic operation with calls to
+   registerValidPath().  This must be atomic, since if we register a
+   successor for a derivation without registering the paths built in
+   the derivation, we have a successor with dangling pointers, and if
+   we do it in reverse order, we can get an obstructed build (since to
+   rebuild the successor, the outputs paths must not exist). */
+void registerSuccessor(const Transaction & txn,
+    const Path & path1, const Path & path2);
+
 /* Register a substitute. */
 void registerSubstitute(const Path & srcPath, const Path & subPath);