* Reject a build if there is a cycle among the outputs. This is

  necessary because existing code assumes that the references graph is
  acyclic.

4 files changed, 24 insertions, 9 deletions

diff --git a/src/libstore/build.cc b/src/libstore/build.cc
index 149cd8b09783..d8f8826e1990 100644
--- a/src/libstore/build.cc
+++ b/src/libstore/build.cc
@@ -278,10 +278,6 @@ public:
 };
 
 
-MakeError(SubstError, Error)
-MakeError(BuildError, Error) /* denotes a permanent build failure */
-
-
 //////////////////////////////////////////////////////////////////////
 
 
@@ -1982,7 +1978,8 @@ void DerivationGoal::computeClosure()
     }
 
     /* Register each output path as valid, and register the sets of
-       paths referenced by each of them. */
+       paths referenced by each of them.  If there are cycles in the
+       outputs, this will fail. */
     ValidPathInfos infos;
     foreach (DerivationOutputs::iterator, i, drv.outputs) {
         ValidPathInfo info;
diff --git a/src/libstore/gc.cc b/src/libstore/gc.cc
index feaab573ef30..ec775113309f 100644
--- a/src/libstore/gc.cc
+++ b/src/libstore/gc.cc
@@ -372,8 +372,13 @@ static void addAdditionalRoots(StoreAPI & store, PathSet & roots)
 
 
 static void dfsVisit(StoreAPI & store, const PathSet & paths,
-    const Path & path, PathSet & visited, Paths & sorted)
+    const Path & path, PathSet & visited, Paths & sorted,
+    PathSet & parents)
 {
+    if (parents.find(path) != parents.end())
+        throw BuildError(format("cycle detected in the references of `%1%'") % path);
+    parents.insert(path);
+    
     if (visited.find(path) != visited.end()) return;
     visited.insert(path);
     
@@ -385,18 +390,19 @@ static void dfsVisit(StoreAPI & store, const PathSet & paths,
         /* Don't traverse into paths that don't exist.  That can
            happen due to substitutes for non-existent paths. */
         if (*i != path && paths.find(*i) != paths.end())
-            dfsVisit(store, paths, *i, visited, sorted);
+            dfsVisit(store, paths, *i, visited, sorted, parents);
 
     sorted.push_front(path);
+    parents.erase(path);
 }
 
 
 Paths topoSortPaths(StoreAPI & store, const PathSet & paths)
 {
     Paths sorted;
-    PathSet visited;
+    PathSet visited, parents;
     foreach (PathSet::const_iterator, i, paths)
-        dfsVisit(store, paths, *i, visited, sorted);
+        dfsVisit(store, paths, *i, visited, sorted, parents);
     return sorted;
 }
 
diff --git a/src/libstore/local-store.cc b/src/libstore/local-store.cc
index 29817df9d6e8..771776f6a2c7 100644
--- a/src/libstore/local-store.cc
+++ b/src/libstore/local-store.cc
@@ -966,12 +966,14 @@ void LocalStore::registerValidPaths(const ValidPathInfos & infos)
     while (1) {
         try {
             SQLiteTxn txn(db);
+            PathSet paths;
     
             foreach (ValidPathInfos::const_iterator, i, infos) {
                 assert(i->hash.type == htSHA256);
                 /* !!! Maybe the registration info should be updated if the
                    path is already valid. */
                 if (!isValidPath(i->path)) addValidPath(*i);
+                paths.insert(i->path);
             }
 
             foreach (ValidPathInfos::const_iterator, i, infos) {
@@ -980,6 +982,12 @@ void LocalStore::registerValidPaths(const ValidPathInfos & infos)
                     addReference(referrer, queryValidPathId(*j));
             }
 
+            /* Do a topological sort of the paths.  This will throw an
+               error if a cycle is detected and roll back the
+               transaction.  Cycles can only occur when a derivation
+               has multiple outputs. */
+            topoSortPaths(*this, paths);
+
             txn.commit();
             break;
         } catch (SQLiteBusy & e) {
diff --git a/src/libstore/store-api.hh b/src/libstore/store-api.hh
index 14890f5225ad..61bcaf50507f 100644
--- a/src/libstore/store-api.hh
+++ b/src/libstore/store-api.hh
@@ -349,6 +349,10 @@ void exportPaths(StoreAPI & store, const Paths & paths,
     bool sign, Sink & sink);
 
 
+MakeError(SubstError, Error)
+MakeError(BuildError, Error) /* denotes a permanent build failure */
+
+
 }