In depgraph.altlist(), measure the bias of circular

RDEPEND <-> PDEPEND relationships and use it to
optimize merge order. (trunk r8593)

svn path=/main/branches/2.1.2/; revision=8594

1 files changed, 20 insertions, 0 deletions

diff --git a/bin/emerge b/bin/emerge
index bb56f5e5b..ee5b64264 100755
--- a/bin/emerge
+++ b/bin/emerge
@@ -2394,6 +2394,21 @@ class depgraph:
 			return retlist
 		mygraph=self.digraph.copy()
 		self._merge_order_bias(mygraph)
+		def cmp_circular_bias(n1, n2):
+			"""
+			RDEPEND is stronger than PDEPEND and this function
+			measures such a strength bias within a circular
+			dependency relationship.
+			"""
+			n1_n2_medium = n2 in mygraph.child_nodes(n1,
+				ignore_priority=DepPriority.MEDIUM_SOFT)
+			n2_n1_medium = n1 in mygraph.child_nodes(n2,
+				ignore_priority=DepPriority.MEDIUM_SOFT)
+			if n1_n2_medium == n2_n1_medium:
+				return 0
+			elif n1_n2_medium:
+				return 1
+			return -1
 		myblockers = self.blocker_digraph.copy()
 		retlist=[]
 		circular_blocks = False
@@ -2559,6 +2574,11 @@ class depgraph:
 							continue
 						asap_nodes.append(child)
 
+			if selected_nodes and len(selected_nodes) > 1:
+				if not isinstance(selected_nodes, list):
+					selected_nodes = list(selected_nodes)
+				selected_nodes.sort(cmp_circular_bias)
+
 			if not selected_nodes:
 				if not myblockers.is_empty():
 					"""A blocker couldn't be circumnavigated while keeping all