find_smallest_cycle: don't merge satisfied PDEPEND too early

After PDEPENDs have been neglected by the find_smallest_cycle function,
do not try to merge them too early if they are already satisfied by
an installed package. This fixes incorrect merge order for PDEPEND
cycles involving xorg-server and xorg-drivers, which was triggered
by commit 5095c2023595a75e2848f1ad3dbe25b5fb451a44 because it gave
PDEPEND higher priority than satisfied buildtime dependencies.

Fixes: 5095c2023595 ("find_smallest_cycle: enhance search prioritization")
Reported-by: josef64 in #gentoo-portage
Bug: https://bugs.gentoo.org/754903
Signed-off-by: Zac Medico <zmedico@gentoo.org>

3 files changed, 30 insertions, 6 deletions

diff --git a/lib/_emerge/DepPrioritySatisfiedRange.py b/lib/_emerge/DepPrioritySatisfiedRange.py
index fb0d7db4e..f546590e0 100644
--- a/lib/_emerge/DepPrioritySatisfiedRange.py
+++ b/lib/_emerge/DepPrioritySatisfiedRange.py
@@ -93,6 +93,7 @@ class DepPrioritySatisfiedRange:
 	ignore_medium      = _ignore_runtime
 	ignore_medium_soft = _ignore_satisfied_buildtime_slot_op
 	ignore_medium_post = _ignore_runtime_post
+	ignore_medium_post_satisifed = _ignore_satisfied_runtime_post
 	ignore_soft        = _ignore_optional
 
 
diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index 1271bda3e..0450291d4 100644
--- a/lib/_emerge/depgraph.py
+++ b/lib/_emerge/depgraph.py
@@ -8052,18 +8052,18 @@ class depgraph:
 									(selected_nodes[0],), noiselevel=-1)
 
 			if selected_nodes and ignore_priority is not None:
-				# Try to merge ignored medium_post deps as soon as possible
+				# Try to merge neglected 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(
+					medium_post_satisifed = children.difference(
 						mygraph.child_nodes(node,
 							ignore_priority = \
-							DepPrioritySatisfiedRange.ignore_soft))
+							DepPrioritySatisfiedRange.ignore_medium_post_satisifed))
 					medium_post = children.difference(
 						mygraph.child_nodes(node,
 						ignore_priority=DepPrioritySatisfiedRange.ignore_medium_post))
-					medium_post -= soft
+					medium_post -= medium_post_satisifed
 					for child in medium_post:
 						if child in selected_nodes:
 							continue
diff --git a/lib/portage/tests/resolver/test_merge_order.py b/lib/portage/tests/resolver/test_merge_order.py
index f81fd2f6f..0510a0636 100644
--- a/lib/portage/tests/resolver/test_merge_order.py
+++ b/lib/portage/tests/resolver/test_merge_order.py
@@ -217,12 +217,23 @@ class MergeOrderTestCase(TestCase):
 				"IUSE" : "X +encode",
 				"RDEPEND" : "|| ( >=media-video/ffmpeg-0.6.90_rc0-r2[X=,encode=] >=media-video/libav-0.6.90_rc[X=,encode=] )",
 			},
+			"x11-base/xorg-drivers-1.20-r2": {
+				"EAPI": "7",
+				"IUSE": "+video_cards_fbdev",
+				"PDEPEND": "x11-base/xorg-server video_cards_fbdev? ( x11-drivers/xf86-video-fbdev )",
+			},
 			"x11-base/xorg-server-1.14.1" : {
 				"EAPI" : "5",
 				"SLOT": "0/1.14.1",
 				"DEPEND" : "media-libs/mesa",
 				"RDEPEND" : "media-libs/mesa",
+				"PDEPEND": "x11-base/xorg-drivers",
 			},
+			"x11-drivers/xf86-video-fbdev-0.5.0-r1": {
+				"EAPI": "7",
+				"DEPEND": "x11-base/xorg-server:=",
+				"RDEPEND": "x11-base/xorg-server",
+			}
 		}
 
 		installed = {
@@ -299,12 +310,24 @@ class MergeOrderTestCase(TestCase):
 				"USE" : "encode",
 				"RDEPEND" : "|| ( >=media-video/ffmpeg-0.6.90_rc0-r2[X=,encode=] >=media-video/libav-0.6.90_rc[X=,encode=] )",
 			},
+			"x11-base/xorg-drivers-1.20-r2": {
+				"EAPI": "7",
+				"IUSE": "+video_cards_fbdev",
+				"USE": "video_cards_fbdev",
+				"PDEPEND": "x11-base/xorg-server x11-drivers/xf86-video-fbdev",
+			},
 			"x11-base/xorg-server-1.14.1" : {
 				"EAPI" : "5",
 				"SLOT": "0/1.14.1",
 				"DEPEND" : "media-libs/mesa",
 				"RDEPEND" : "media-libs/mesa",
+				"PDEPEND": "x11-base/xorg-drivers",
 			},
+			"x11-drivers/xf86-video-fbdev-0.5.0-r1": {
+				"EAPI": "7",
+				"DEPEND": "x11-base/xorg-server:0/1.14.1=",
+				"RDEPEND": "x11-base/xorg-server",
+			}
 		}
 
 		test_cases = (
@@ -486,10 +509,10 @@ class MergeOrderTestCase(TestCase):
 			# Both deps are already satisfied by installed packages, but
 			# the := dep is given higher priority in merge order.
 			ResolverPlaygroundTestCase(
-				["media-libs/mesa", "x11-base/xorg-server"],
+				["media-libs/mesa", "x11-drivers/xf86-video-fbdev", "x11-base/xorg-server"],
 				success=True,
 				all_permutations = True,
-				mergelist = ['x11-base/xorg-server-1.14.1', 'media-libs/mesa-9.1.3']),
+				mergelist = ['x11-base/xorg-server-1.14.1', 'media-libs/mesa-9.1.3', 'x11-drivers/xf86-video-fbdev-0.5.0-r1']),
 			# 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