[PATCH] backtracking: solve circular dependencies

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

[PATCH] backtracking: solve circular dependencies

Zac Medico-2
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 <[hidden email]>
---
 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