[prev in list] [next in list] [prev in thread] [next in thread]
List: gentoo-portage-dev
Subject: [gentoo-portage-dev] [PATCH] backtracking: solve circular dependencies
From: Zac Medico <zmedico () gentoo ! org>
Date: 2019-12-23 13:30:22
Message-ID: 20191223133022.22365-1-zmedico () gentoo ! org
[Download RAW message or body]
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@gentoo.org>
---
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
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic