backtracking: adjust || preference to break dependency cycles

Store dependency cycle edges as backtracking parameters, and use them
to adjust || preferences in order to break dependency cycles. This
extends direct cycle breaking to handle indirect dependency cycles,
which solves the cmake-bootstrap test case for bug 703440. If any
cycle(s) remain unsolved by the next backtracking run, then backtracking
aborts and the cycle(s) are reported as usual.

Note that backtracking is necessary in order to avoid bugs of the form
"emerge installs packages only to have them removed by depclean", since
this sort of behavior is desirable only when it eliminates a dependency
cycle.

Bug: https://bugs.gentoo.org/382421
Bug: https://bugs.gentoo.org/384107
Bug: https://bugs.gentoo.org/703440
Signed-off-by: Zac Medico <zmedico@gentoo.org>

4 files changed, 84 insertions, 4 deletions

diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index 2ab1bf4ac..dcef06f93 100644
--- a/lib/_emerge/depgraph.py
+++ b/lib/_emerge/depgraph.py
@@ -480,6 +480,7 @@ class _dynamic_depgraph_config(object):
 		# of flags causing the rejection.
 		self.ignored_binaries = {}
 
+		self._circular_dependency = backtrack_parameters.circular_dependency
 		self._needed_unstable_keywords = backtrack_parameters.needed_unstable_keywords
 		self._needed_p_mask_changes = backtrack_parameters.needed_p_mask_changes
 		self._needed_license_changes = backtrack_parameters.needed_license_changes
@@ -4809,6 +4810,7 @@ class depgraph(object):
 				mytrees.pop("pkg_use_enabled", None)
 				mytrees.pop("parent", None)
 				mytrees.pop("atom_graph", None)
+				mytrees.pop("circular_dependency", None)
 				mytrees.pop("priority", None)
 
 				mytrees["pkg_use_enabled"] = self._pkg_use_enabled
@@ -4816,6 +4818,7 @@ class depgraph(object):
 					self._select_atoms_parent = parent
 					mytrees["parent"] = parent
 					mytrees["atom_graph"] = atom_graph
+					mytrees["circular_dependency"] = self._dynamic_config._circular_dependency
 				if priority is not None:
 					mytrees["priority"] = priority
 
@@ -4829,6 +4832,7 @@ class depgraph(object):
 				mytrees.pop("pkg_use_enabled", None)
 				mytrees.pop("parent", None)
 				mytrees.pop("atom_graph", None)
+				mytrees.pop("circular_dependency", None)
 				mytrees.pop("priority", None)
 				mytrees.update(backup_state)
 			if not mycheck[0]:
@@ -8226,7 +8230,30 @@ class depgraph(object):
 
 			if not selected_nodes:
 				self._dynamic_config._circular_deps_for_display = mygraph
-				self._dynamic_config._skip_restart = True
+
+				unsolved_cycle = False
+				if self._dynamic_config._allow_backtracking:
+
+					backtrack_infos = self._dynamic_config._backtrack_infos
+					backtrack_infos.setdefault("config", {})
+					circular_dependency = backtrack_infos["config"].setdefault("circular_dependency", {})
+
+					cycles = mygraph.get_cycles(ignore_priority=DepPrioritySatisfiedRange.ignore_medium_soft)
+					for cycle in cycles:
+						for index, node in enumerate(cycle):
+							if node in self._dynamic_config._circular_dependency:
+								unsolved_cycle = True
+							if index == 0:
+								circular_child = cycle[-1]
+							else:
+								circular_child = cycle[index-1]
+							circular_dependency.setdefault(node, set()).add(circular_child)
+
+				if unsolved_cycle or not self._dynamic_config._allow_backtracking:
+					self._dynamic_config._skip_restart = True
+				else:
+					self._dynamic_config._need_restart = True
+
 				raise self._unknown_internal_error()
 
 			# At this point, we've succeeded in selecting one or more nodes, so
@@ -9461,6 +9488,17 @@ class depgraph(object):
 		return self._dynamic_config._need_restart and \
 			not self._dynamic_config._skip_restart
 
+	def need_display_problems(self):
+		"""
+		Returns true if this depgraph has problems which need to be
+		displayed to the user.
+		"""
+		if self.need_config_change():
+			return True
+		if self._dynamic_config._circular_deps_for_display:
+			return True
+		return False
+
 	def need_config_change(self):
 		"""
 		Returns true if backtracking should terminate due to a needed
@@ -9889,7 +9927,7 @@ def _backtrack_depgraph(settings, trees, myopts, myparams, myaction, myfiles, sp
 		elif backtracker:
 			backtracked += 1
 
-	if not (success or mydepgraph.need_config_change()) and backtracked:
+	if backtracked and not success and not mydepgraph.need_display_problems():
 
 		if debug:
 			writemsg_level(
diff --git a/lib/_emerge/resolver/backtracking.py b/lib/_emerge/resolver/backtracking.py
index 99e4565c8..430c81186 100644
--- a/lib/_emerge/resolver/backtracking.py
+++ b/lib/_emerge/resolver/backtracking.py
@@ -6,12 +6,14 @@ import copy
 class BacktrackParameter(object):
 
 	__slots__ = (
+		"circular_dependency",
 		"needed_unstable_keywords", "runtime_pkg_mask", "needed_use_config_changes", "needed_license_changes",
 		"prune_rebuilds", "rebuild_list", "reinstall_list", "needed_p_mask_changes",
 		"slot_operator_mask_built", "slot_operator_replace_installed"
 	)
 
 	def __init__(self):
+		self.circular_dependency = {}
 		self.needed_unstable_keywords = set()
 		self.needed_p_mask_changes = set()
 		self.runtime_pkg_mask = {}
@@ -31,6 +33,7 @@ class BacktrackParameter(object):
 
 		#Shallow copies are enough here, as we only need to ensure that nobody adds stuff
 		#to our sets and dicts. The existing content is immutable.
+		result.circular_dependency = copy.copy(self.circular_dependency)
 		result.needed_unstable_keywords = copy.copy(self.needed_unstable_keywords)
 		result.needed_p_mask_changes = copy.copy(self.needed_p_mask_changes)
 		result.needed_use_config_changes = copy.copy(self.needed_use_config_changes)
@@ -49,7 +52,8 @@ class BacktrackParameter(object):
 		return result
 
 	def __eq__(self, other):
-		return self.needed_unstable_keywords == other.needed_unstable_keywords and \
+		return self.circular_dependency == other.circular_dependency and \
+			self.needed_unstable_keywords == other.needed_unstable_keywords and \
 			self.needed_p_mask_changes == other.needed_p_mask_changes and \
 			self.runtime_pkg_mask == other.runtime_pkg_mask and \
 			self.needed_use_config_changes == other.needed_use_config_changes and \
@@ -195,7 +199,10 @@ class Backtracker(object):
 		para = new_node.parameter
 
 		for change, data in changes.items():
-			if change == "needed_unstable_keywords":
+			if change == "circular_dependency":
+				for pkg, circular_children in data.items():
+					para.circular_dependency.setdefault(pkg, set()).update(circular_children)
+			elif change == "needed_unstable_keywords":
 				para.needed_unstable_keywords.update(data)
 			elif change == "needed_p_mask_changes":
 				para.needed_p_mask_changes.update(data)
diff --git a/lib/portage/dep/dep_check.py b/lib/portage/dep/dep_check.py
index 2896e2389..3a0c7bbe9 100644
--- a/lib/portage/dep/dep_check.py
+++ b/lib/portage/dep/dep_check.py
@@ -367,6 +367,7 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None,
 	pkg_use_enabled = trees[myroot].get("pkg_use_enabled")
 	want_update_pkg = trees[myroot].get("want_update_pkg")
 	downgrade_probe = trees[myroot].get("downgrade_probe")
+	circular_dependency = trees[myroot].get("circular_dependency")
 	vardb = None
 	if "vartree" in trees[myroot]:
 		vardb = trees[myroot]["vartree"].dbapi
@@ -589,6 +590,15 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None,
 							if match_from_list(atom, cpv_slot_list):
 								circular_atom = atom
 								break
+						else:
+							for circular_child in circular_dependency.get(parent, []):
+								for atom in atoms:
+									if not atom.blocker and atom.match(circular_child):
+										circular_atom = atom
+										break
+								if circular_atom is not None:
+									break
+
 				if circular_atom is not None:
 					other.append(this_choice)
 				else:
diff --git a/lib/portage/tests/resolver/test_circular_choices.py b/lib/portage/tests/resolver/test_circular_choices.py
index d963280b7..a5c10b476 100644
--- a/lib/portage/tests/resolver/test_circular_choices.py
+++ b/lib/portage/tests/resolver/test_circular_choices.py
@@ -33,9 +33,16 @@ class CircularJsoncppCmakeBootstrapTestCase(TestCase):
 			#    (dev-libs/jsoncpp-1.9.2:0/0::test_repo, ebuild scheduled for merge) (buildtime_slot_op)
 			ResolverPlaygroundTestCase(
 				['dev-util/cmake'],
+				options = {"--backtrack": 0},
 				circular_dependency_solutions = {},
 				success = False,
 			),
+			# Demonstrate that backtracking adjusts || preferences in order to solve bug 703440.
+			ResolverPlaygroundTestCase(
+				['dev-util/cmake'],
+				mergelist = ['dev-util/cmake-bootstrap-3.16.2', 'dev-libs/jsoncpp-1.9.2', 'dev-util/cmake-3.16.2'],
+				success = True,
+			),
 		)
 
 		playground = ResolverPlayground(ebuilds=ebuilds)
@@ -46,6 +53,24 @@ class CircularJsoncppCmakeBootstrapTestCase(TestCase):
 		finally:
 			playground.cleanup()
 
+		test_cases = (
+			# Demonstrate elimination of cmake-bootstrap via --depclean.
+			ResolverPlaygroundTestCase(
+				[],
+				options = {'--depclean': True},
+				success = True,
+				cleanlist = ['dev-util/cmake-bootstrap-3.16.2'],
+			),
+		)
+
+		playground = ResolverPlayground(ebuilds=ebuilds, installed=ebuilds, world=['dev-util/cmake'])
+		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()
+
 	def testVirtualCmakeBootstrapUseConditional(self):
 
 		ebuilds = {