From ca46312928473ffe22740498aca6891ef623497c Mon Sep 17 00:00:00 2001
From: Zac Medico <zmedico@gentoo.org>
Date: Mon, 2 Oct 2006 22:08:04 +0000
Subject: [PATCH] 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
---
 bin/emerge     | 34 ++++++++++++++++++++++++++++++++--
 pym/portage.py | 10 ++++++++--
 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"""
-- 
2.26.2