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: 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 ++++++++++++++++++++++++++++++++--
 1 file changed, 32 insertions(+), 2 deletions(-)

(limited to 'bin')

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"):
-- 
cgit v1.2.3-1-g7c22