[gentoo-portage-dev] [PATCH v2] find_smallest_cycle: enhance search prioritization

[Zac Medico <zmedico@gentoo.org>]

Enhance the find_smallest_cycle function to prioritize its
search so that it will minimize the use of installed packages
to break cycles. When installed packages must be used to
break cycles, it will now prefer to do this for runtime
dependencies over buildtime dependencies, since it's
preferable to build against latest versions of buildtime
dependencies whenever possible. This should solve some cases
of bug 199856 which have been triggered by unsafe reliance
on installed packages to break cycles.

The included unit test case demonstrates correct merge order
for a dependency calculation involving 6 independent cycles.
This test case fails with the master branch, due to a buildtime
dependency cycle of 3 packages being merged earlier than cycles
of 2 packages. We can generalize this to say that the master
branch may use an installed package to break an arbitrarily
sized cycle in a somewhat random location, even though that
cycle may be composed of smaller independent cycles which
would be safer to break individually.

Bug: https://bugs.gentoo.org/754903
Signed-off-by: Zac Medico <zmedico@gentoo.org>
---
[PATCH v2]
* Add a unit test case which demonstrates a significant flaw
  in the master branch.
* Sort nodes in find_smallest_cycle, for deterministic results. 

 lib/_emerge/DepPriorityNormalRange.py         |  2 +
 lib/_emerge/DepPrioritySatisfiedRange.py      | 52 ++++++++++---------
 lib/_emerge/depgraph.py                       | 43 +++++++++------
 .../tests/resolver/test_merge_order.py        | 10 ++++
 4 files changed, 66 insertions(+), 41 deletions(-)

diff --git a/lib/_emerge/DepPriorityNormalRange.py b/lib/_emerge/DepPriorityNormalRange.py
index 5f3f3da70..10f205a3b 100644
--- a/lib/_emerge/DepPriorityNormalRange.py
+++ b/lib/_emerge/DepPriorityNormalRange.py
@@ -14,6 +14,7 @@ class DepPriorityNormalRange:
 	"""
 	MEDIUM      = 3
 	MEDIUM_SOFT = 2
+	MEDIUM_POST = 2
 	SOFT        = 1
 	NONE        = 0
 
@@ -37,6 +38,7 @@ class DepPriorityNormalRange:
 
 	ignore_medium      = _ignore_runtime
 	ignore_medium_soft = _ignore_runtime_post
+	ignore_medium_post = _ignore_runtime_post
 	ignore_soft        = _ignore_optional
 
 DepPriorityNormalRange.ignore_priority = (
diff --git a/lib/_emerge/DepPrioritySatisfiedRange.py b/lib/_emerge/DepPrioritySatisfiedRange.py
index e056e676f..df2439f1f 100644
--- a/lib/_emerge/DepPrioritySatisfiedRange.py
+++ b/lib/_emerge/DepPrioritySatisfiedRange.py
@@ -8,17 +8,18 @@ class DepPrioritySatisfiedRange:
 
 	not satisfied and buildtime                    HARD
 	not satisfied and runtime              7       MEDIUM
-	not satisfied and runtime_post         6       MEDIUM_SOFT
-	satisfied and buildtime_slot_op        5       SOFT
-	satisfied and buildtime                4       SOFT
-	satisfied and runtime                  3       SOFT
-	satisfied and runtime_post             2       SOFT
+	satisfied and buildtime_slot_op        6       MEDIUM_SOFT
+	satisfied and buildtime                5       MEDIUM_SOFT
+	satisfied and runtime                  4       MEDIUM_SOFT
+	runtime_post                           3       MEDIUM_POST
+	satisfied and runtime_post             2       MEDIUM_POST
 	optional                               1       SOFT
 	(none of the above)                    0       NONE
 	"""
 	MEDIUM      = 7
 	MEDIUM_SOFT = 6
-	SOFT        = 5
+	MEDIUM_POST = 3
+	SOFT        = 1
 	NONE        = 0
 
 	@classmethod
@@ -37,15 +38,23 @@ class DepPrioritySatisfiedRange:
 			return False
 		return bool(priority.runtime_post)
 
+	@classmethod
+	def _ignore_runtime_post(cls, priority):
+		if priority.__class__ is not DepPriority:
+			return False
+		return bool(priority.optional or priority.runtime_post)
+
 	@classmethod
 	def _ignore_satisfied_runtime(cls, priority):
 		if priority.__class__ is not DepPriority:
 			return False
 		if priority.optional:
 			return True
-		if not priority.satisfied:
+		if priority.buildtime:
 			return False
-		return not priority.buildtime
+		if not priority.runtime:
+			return True
+		return bool(priority.satisfied)
 
 	@classmethod
 	def _ignore_satisfied_buildtime(cls, priority):
@@ -61,37 +70,32 @@ class DepPrioritySatisfiedRange:
 	def _ignore_satisfied_buildtime_slot_op(cls, priority):
 		if priority.__class__ is not DepPriority:
 			return False
-		return bool(priority.optional or \
-			priority.satisfied)
-
-	@classmethod
-	def _ignore_runtime_post(cls, priority):
-		if priority.__class__ is not DepPriority:
-			return False
-		return bool(priority.optional or \
-			priority.satisfied or \
-			priority.runtime_post)
+		if priority.optional:
+			return True
+		if priority.satisfied:
+			return True
+		return not priority.buildtime and not priority.runtime
 
 	@classmethod
 	def _ignore_runtime(cls, priority):
 		if priority.__class__ is not DepPriority:
 			return False
-		return bool(priority.satisfied or \
-			priority.optional or \
-			not priority.buildtime)
+		return bool(priority.optional or
+			priority.satisfied or priority.runtime)
 
 	ignore_medium      = _ignore_runtime
-	ignore_medium_soft = _ignore_runtime_post
-	ignore_soft        = _ignore_satisfied_buildtime
+	ignore_medium_soft = _ignore_satisfied_buildtime_slot_op
+	ignore_medium_post = _ignore_runtime_post
+	ignore_soft        = _ignore_optional
 
 
 DepPrioritySatisfiedRange.ignore_priority = (
 	None,
 	DepPrioritySatisfiedRange._ignore_optional,
 	DepPrioritySatisfiedRange._ignore_satisfied_runtime_post,
+	DepPrioritySatisfiedRange._ignore_runtime_post,
 	DepPrioritySatisfiedRange._ignore_satisfied_runtime,
 	DepPrioritySatisfiedRange._ignore_satisfied_buildtime,
 	DepPrioritySatisfiedRange._ignore_satisfied_buildtime_slot_op,
-	DepPrioritySatisfiedRange._ignore_runtime_post,
 	DepPrioritySatisfiedRange._ignore_runtime
 )
diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index 6aaacfe44..af26ecd93 100644
--- a/lib/_emerge/depgraph.py
+++ b/lib/_emerge/depgraph.py
@@ -7905,7 +7905,7 @@ class depgraph:
 								if check_asap_parent:
 									for node in nodes:
 										parents = mygraph.parent_nodes(node,
-											ignore_priority=DepPrioritySatisfiedRange.ignore_soft)
+											ignore_priority=DepPrioritySatisfiedRange.ignore_medium_soft)
 										if any(x in asap_nodes for x in parents):
 											selected_nodes = [node]
 											break
@@ -7921,7 +7921,7 @@ class depgraph:
 
 			if not selected_nodes:
 
-				def find_smallest_cycle(mergeable_nodes, priority_ranges):
+				def find_smallest_cycle(mergeable_nodes, local_priority_range):
 					if prefer_asap and asap_nodes:
 						nodes = asap_nodes
 					else:
@@ -7938,18 +7938,27 @@ class depgraph:
 					# these smaller independent cycles.
 					smallest_cycle = None
 					ignore_priority = None
-					for node in nodes:
-						if not mygraph.parent_nodes(node):
-							continue
-						for local_priority_range in priority_ranges:
+
+					# Sort nodes for deterministic results.
+					nodes = sorted(nodes)
+					for priority in (local_priority_range.ignore_priority[i] for i in range(
+						local_priority_range.MEDIUM_POST,
+						local_priority_range.MEDIUM_SOFT + 1)):
+						for node in nodes:
+							if not mygraph.parent_nodes(node):
+								continue
 							selected_nodes = set()
-							if gather_deps(local_priority_range.ignore_medium_soft,
+							if gather_deps(priority,
 								mergeable_nodes, selected_nodes, node):
 								if smallest_cycle is None or \
 									len(selected_nodes) < len(smallest_cycle):
 									smallest_cycle = selected_nodes
-									ignore_priority = local_priority_range.ignore_medium_soft
-								break
+									ignore_priority = priority
+
+						# Exit this loop with the lowest possible priority, which
+						# minimizes the use of installed packages to break cycles.
+						if smallest_cycle is not None:
+							break
 
 					return smallest_cycle, ignore_priority
 
@@ -7963,7 +7972,7 @@ class depgraph:
 				for local_priority_range in priority_ranges:
 					mergeable_nodes = set(get_nodes(ignore_priority=local_priority_range.ignore_medium))
 					if mergeable_nodes:
-						selected_nodes, ignore_priority = find_smallest_cycle(mergeable_nodes, priority_ranges)
+						selected_nodes, ignore_priority = find_smallest_cycle(mergeable_nodes, local_priority_range)
 						if selected_nodes:
 							break
 
@@ -8001,19 +8010,19 @@ class depgraph:
 									(selected_nodes[0],), noiselevel=-1)
 
 			if selected_nodes and ignore_priority is not None:
-				# Try to merge ignored medium_soft deps as soon as possible
+				# Try to merge ignored medium_post deps as soon as possible
 				# if they're not satisfied by installed packages.
 				for node in selected_nodes:
 					children = set(mygraph.child_nodes(node))
 					soft = children.difference(
-						mygraph.child_nodes(node,
-						ignore_priority=DepPrioritySatisfiedRange.ignore_soft))
-					medium_soft = children.difference(
 						mygraph.child_nodes(node,
 							ignore_priority = \
-							DepPrioritySatisfiedRange.ignore_medium_soft))
-					medium_soft -= soft
-					for child in medium_soft:
+							DepPrioritySatisfiedRange.ignore_soft))
+					medium_post = children.difference(
+						mygraph.child_nodes(node,
+						ignore_priority=DepPrioritySatisfiedRange.ignore_medium_post))
+					medium_post -= soft
+					for child in medium_post:
 						if child in selected_nodes:
 							continue
 						if child in asap_nodes:
diff --git a/lib/portage/tests/resolver/test_merge_order.py b/lib/portage/tests/resolver/test_merge_order.py
index 0003cd7d8..f81fd2f6f 100644
--- a/lib/portage/tests/resolver/test_merge_order.py
+++ b/lib/portage/tests/resolver/test_merge_order.py
@@ -490,6 +490,16 @@ class MergeOrderTestCase(TestCase):
 				success=True,
 				all_permutations = True,
 				mergelist = ['x11-base/xorg-server-1.14.1', 'media-libs/mesa-9.1.3']),
+			# Test prioritization of the find_smallest_cycle function, which should
+			# minimize the use of installed packages to break cycles. If installed
+			# packages must be used to break cycles, then it should prefer to do this
+			# for runtime dependencies over buildtime dependencies. If a package needs
+			# to be uninstalled in order to solve a blocker, then it should prefer to
+			# do this before it uses an installed package to break a cycle.
+			ResolverPlaygroundTestCase(
+				["app-misc/some-app-a", "app-misc/some-app-b", "app-misc/some-app-c", "app-misc/circ-buildtime-a", "app-misc/blocker-buildtime-unbuilt-a", "media-libs/mesa", "x11-base/xorg-server", "app-misc/circ-direct-a", "app-misc/circ-direct-b", "app-misc/circ-satisfied-a", "app-misc/circ-satisfied-b", "app-misc/circ-satisfied-c"],
+				success = True,
+				mergelist = ['app-misc/circ-post-runtime-a-1', 'app-misc/circ-post-runtime-c-1', 'app-misc/circ-post-runtime-b-1', 'app-misc/some-app-b-1', 'app-misc/circ-runtime-a-1', 'app-misc/circ-runtime-b-1', 'app-misc/circ-runtime-c-1', 'app-misc/some-app-a-1', 'app-misc/blocker-buildtime-unbuilt-a-1', '[uninstall]app-misc/installed-blocker-a-1', '!app-misc/installed-blocker-a', 'app-misc/circ-direct-a-1', 'app-misc/circ-direct-b-1', 'x11-base/xorg-server-1.14.1', 'media-libs/mesa-9.1.3', 'app-misc/circ-buildtime-a-1', 'app-misc/circ-buildtime-b-1', 'app-misc/circ-buildtime-c-1', 'app-misc/some-app-c-1', 'app-misc/circ-satisfied-a-1', 'app-misc/circ-satisfied-b-1', 'app-misc/circ-satisfied-c-1']),
 		)
 
 		playground = ResolverPlayground(ebuilds=ebuilds, installed=installed)
-- 
2.26.2