[gentoo-portage-dev] [PATCH] backtracking: solve circular dependencies

[Zac Medico]

Store circular dependency edges as backtracking parameters, and use them
to adjust || preferences in order to solve circular dependencies. This
extends direct dependency cycle avoidance 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.

Bug: https://bugs.gentoo.org/384107
Bug: https://bugs.gentoo.org/703440
Signed-off-by: Zac Medico <zmedico@g.o>
---
 lib/_emerge/depgraph.py                       | 46 ++++++++++++++++++-
 lib/_emerge/resolver/backtracking.py          | 10 +++-
 lib/portage/dep/dep_check.py                  | 10 ++++
 .../tests/resolver/test_circular_choices.py   |  7 +++
 4 files changed, 69 insertions(+), 4 deletions(-)

diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index 1a5448c8f..84cf127c1 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
@@ -4798,6 +4799,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
@@ -4805,6 +4807,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
 
@@ -4818,6 +4821,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]:
@@ -8215,7 +8219,34 @@ 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 node in cycle:
+							if node in self._dynamic_config._circular_dependency:
+								unsolved_cycle = True
+							circular_child = None
+							for other_node in cycle:
+								if other_node == node:
+									break
+								circular_child = other_node
+							else:
+								circular_child = other_node
+							if circular_child is not None:
+								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
@@ -9450,6 +9481,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
@@ -9878,7 +9920,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..e94ee2f1e 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,9 @@ class Backtracker(object):
 		para = new_node.parameter
 
 		for change, data in changes.items():
-			if change == "needed_unstable_keywords":
+			if change == "circular_dependency":
+				para.circular_dependency.update(data)
+			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..e1742aaeb 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 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..32b6ce293 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)
-- 
2.21.0