summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorZac Medico <zmedico@gentoo.org>2006-10-02 22:08:04 +0000
committerZac Medico <zmedico@gentoo.org>2006-10-02 22:08:04 +0000
commitca46312928473ffe22740498aca6891ef623497c (patch)
tree080ab72aa3217fa768fcd5023eb76d24ff7157f8
parentbdfdb9a8caafd9e760176f298d016ce233f98d9c (diff)
downloadportage-ca46312928473ffe22740498aca6891ef623497c.tar.gz
portage-ca46312928473ffe22740498aca6891ef623497c.tar.bz2
portage-ca46312928473ffe22740498aca6891ef623497c.zip
Fix depgraph.altlist() so that it can identify a group of nodes that completely satisfy eachothers non-soft deps. This should complete the fix for bug #149881.
svn path=/main/trunk/; revision=4572
-rwxr-xr-xbin/emerge34
-rw-r--r--pym/portage.py10
2 files changed, 40 insertions, 4 deletions
diff --git a/bin/emerge b/bin/emerge
index 08c43b579..ca34683a8 100755
--- a/bin/emerge
+++ b/bin/emerge
@@ -1256,26 +1256,56 @@ class depgraph:
mygraph=self.digraph.copy()
retlist=[]
while not mygraph.empty():
+ ignore_priority = -1
if reversed:
nodes = mygraph.root_nodes()
if not nodes:
+ ignore_priority = digraph.SOFT
nodes = mygraph.root_nodes(ignore_priority=digraph.SOFT)
if not nodes:
+ ignore_priority = digraph.MEDIUM
nodes = mygraph.root_nodes(ignore_priority=digraph.MEDIUM)
else:
nodes = mygraph.leaf_nodes()
if not nodes:
+ ignore_priority = digraph.SOFT
nodes = mygraph.leaf_nodes(ignore_priority=digraph.SOFT)
if not nodes:
+ ignore_priority = digraph.MEDIUM
nodes = mygraph.leaf_nodes(ignore_priority=digraph.MEDIUM)
- if not nodes:
+
+ selected_nodes = None
+ if nodes:
+ if ignore_priority <= digraph.SOFT or len(nodes) == 1:
+ selected_nodes = [nodes[0]]
+ else:
+ """Find two or more nodes that are mutually dependent and
+ completely satisfy eachother's non-soft deps."""
+ nodes = set(nodes)
+ selected_nodes = None
+ for node in nodes:
+ selected_nodes = set(mygraph.child_nodes(node,
+ ignore_priority=digraph.SOFT))
+ selected_nodes.add(node)
+ grandchildren = set()
+ for child in mygraph.child_nodes(node,
+ ignore_priority=digraph.SOFT):
+ grandchildren.update(mygraph.child_nodes(child,
+ ignore_priority=digraph.SOFT))
+ if grandchildren.issubset(selected_nodes):
+ break
+ selected_nodes = None
+
+ if not selected_nodes:
print "!!! Error: circular dependencies:"
print
mygraph.debug_print()
sys.exit(1)
- for node in nodes:
+
+ for node in selected_nodes:
retlist.append(node.split())
mygraph.remove(node)
+
return retlist
def xcreate(self,mode="system"):
diff --git a/pym/portage.py b/pym/portage.py
index f3de6d9e3..620ef06bd 100644
--- a/pym/portage.py
+++ b/pym/portage.py
@@ -375,9 +375,15 @@ class digraph:
"""Return a list of all nodes in the graph"""
return self.order[:]
- def child_nodes(self, node):
+ def child_nodes(self, node, ignore_priority=-1):
"""Return all children of the specified node"""
- return self.nodes[node][0].keys()
+ if ignore_priority == -1:
+ return self.nodes[node][0].keys()
+ children = []
+ for child, priority in self.nodes[node][0].iteritems():
+ if priority > ignore_priority:
+ children.append(child)
+ return children
def parent_nodes(self, node):
"""Return all parents of the specified node"""