[gentoo-portage-dev] [PATCH] depgraph: avoid missed update with slot operator and circ dep (bug 612874)

[Zac Medico]

Fix check_reverse_dependencies to ignore direct circular dependencies,
since these dependencies tend to prevent updates of packages. This
solves a missed update from llvm:0 to llvm:4 when clang is not in the
world file, as demonstrated by the included test case.

X-Gentoo-bug: 612874
X-Gentoo-bug-url: https://bugs.gentoo.org/show_bug.cgi?id=612874
---
 pym/_emerge/depgraph.py                            | 31 ++++++++++++-----
 .../resolver/test_slot_operator_exclusive_slots.py | 39 ++++++++++++++++++++++
 pym/portage/util/digraph.py                        |  6 ++++
 3 files changed, 68 insertions(+), 8 deletions(-)

diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index f4145d0..e94b96c 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -1844,14 +1844,29 @@ class depgraph(object):
 					if (not self._too_deep(parent.depth) and
 						not self._frozen_config.excluded_pkgs.
 						findAtomForPackage(parent,
-						modified_use=self._pkg_use_enabled(parent)) and
-						(self._upgrade_available(parent) or
-						(parent.installed and self._in_blocker_conflict(parent)))):
-						# This parent may be irrelevant, since an
-						# update is available (see bug 584626), or
-						# it could be uninstalled in order to solve
-						# a blocker conflict (bug 612772).
-						continue
+						modified_use=self._pkg_use_enabled(parent))):
+						# Check for common reasons that the parent's
+						# dependency might be irrelevant.
+						if self._upgrade_available(parent):
+							# This parent could be replaced by
+							# an upgrade (bug 584626).
+							continue
+						if parent.installed and self._in_blocker_conflict(parent):
+							# This parent could be uninstalled in order
+							# to solve a blocker conflict (bug 612772).
+							continue
+						if self._dynamic_config.digraph.has_edge(parent,
+							existing_pkg):
+							# There is a direct circular dependency between
+							# parent and existing_pkg. This type of
+							# relationship tends to prevent updates
+							# of packages (bug 612874). Since candidate_pkg
+							# is available, we risk a missed update if we
+							# don't try to eliminate this parent from the
+							# graph. Therefore, we give candidate_pkg a
+							# chance, and assume that it will be masked
+							# by backtracking if necessary.
+							continue
 
 				atom_set = InternalPackageSet(initial_atoms=(atom,),
 					allow_repo=True)
diff --git a/pym/portage/tests/resolver/test_slot_operator_exclusive_slots.py b/pym/portage/tests/resolver/test_slot_operator_exclusive_slots.py
index 2ab379c..689ed31 100644
--- a/pym/portage/tests/resolver/test_slot_operator_exclusive_slots.py
+++ b/pym/portage/tests/resolver/test_slot_operator_exclusive_slots.py
@@ -107,3 +107,42 @@ class SlotOperatorExclusiveSlotsTestCase(TestCase):
 					test_case.fail_msg)
 		finally:
 			playground.cleanup()
+
+
+		world = ["media-libs/mesa"]
+
+		test_cases = (
+
+			# Test bug #612874, where a direct circular dependency
+			# between llvm-3.9.1 and clang-3.9.1-r100 causes a
+			# missed update from llvm:0 to llvm:4. Since llvm:4 does
+			# not have a dependency on clang, the upgrade from llvm:0
+			# to llvm:4 makes the installed sys-devel/clang-3.9.1-r100
+			# instance eligible for removal by emerge --depclean, which
+			# explains why clang does not appear in the mergelist.
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {"--update": True, "--deep": True},
+				success = True,
+				ambiguous_merge_order = True,
+				mergelist = [
+					'sys-devel/llvm-4.0.0',
+					(
+						'media-libs/mesa-17.0.1',
+						'[uninstall]sys-devel/llvm-3.9.1',
+						'!sys-devel/llvm:0',
+					)
+				],
+			),
+
+		)
+
+		playground = ResolverPlayground(ebuilds=ebuilds,
+			installed=installed, world=world)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success, True,
+					test_case.fail_msg)
+		finally:
+			playground.cleanup()
diff --git a/pym/portage/util/digraph.py b/pym/portage/util/digraph.py
index 4a9cb43..b6be0c9 100644
--- a/pym/portage/util/digraph.py
+++ b/pym/portage/util/digraph.py
@@ -93,6 +93,12 @@ class digraph(object):
 			del self.nodes[node]
 		self.order = order
 
+	def has_edge(self, child, parent):
+		"""
+		Return True if the given edge exists.
+		"""
+		return child in self.nodes[parent][0]
+
 	def remove_edge(self, child, parent):
 		"""
 		Remove edge in the direction from child to parent. Note that it is
-- 
2.10.2