From 6f5e3326cef2a2049c8f4ea757accafe4fc9d53f Mon Sep 17 00:00:00 2001 From: Eelco Dolstra Date: Fri, 30 Dec 2011 15:02:50 +0000 Subject: * Move topoSortPaths() out of gc.cc. --- src/libstore/misc.cc | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) (limited to 'src/libstore/misc.cc') diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc index d4bbccd111ba..abe59d1628fb 100644 --- a/src/libstore/misc.cc +++ b/src/libstore/misc.cc @@ -97,4 +97,40 @@ void queryMissing(StoreAPI & store, const PathSet & targets, } +static void dfsVisit(StoreAPI & store, const PathSet & paths, + 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); + + PathSet references; + if (store.isValidPath(path)) + store.queryReferences(path, references); + + foreach (PathSet::iterator, i, references) + /* 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, parents); + + sorted.push_front(path); + parents.erase(path); +} + + +Paths topoSortPaths(StoreAPI & store, const PathSet & paths) +{ + Paths sorted; + PathSet visited, parents; + foreach (PathSet::const_iterator, i, paths) + dfsVisit(store, paths, *i, visited, sorted, parents); + return sorted; +} + + } -- cgit 1.4.1 From a71d02440b03cdb5dad6e43f786c0cc86cbb87b1 Mon Sep 17 00:00:00 2001 From: Eelco Dolstra Date: Fri, 30 Dec 2011 17:13:25 +0000 Subject: * Oops. --- src/libstore/misc.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/libstore/misc.cc') diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc index abe59d1628fb..4ac0afe844b6 100644 --- a/src/libstore/misc.cc +++ b/src/libstore/misc.cc @@ -103,10 +103,10 @@ static void dfsVisit(StoreAPI & store, const PathSet & paths, { 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); + parents.insert(path); PathSet references; if (store.isValidPath(path)) -- cgit 1.4.1