From b1004f40f7e4dd02feec2d0cb26bd6c95dd66dde Mon Sep 17 00:00:00 2001 From: Eelco Dolstra Date: Fri, 30 Dec 2011 14:47:14 +0000 Subject: * Reject a build if there is a cycle among the outputs. This is necessary because existing code assumes that the references graph is acyclic. --- src/libstore/gc.cc | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) (limited to 'src/libstore/gc.cc') 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; } -- cgit 1.4.1