diff options
| -rw-r--r-- | pym/_emerge/depgraph.py | 181 | ||||
| -rw-r--r-- | pym/_emerge/resolver/backtracking.py | 184 | ||||
| -rw-r--r-- | pym/portage/tests/resolver/test_autounmask.py | 13 | ||||
| -rw-r--r-- | pym/portage/tests/resolver/test_backtracking.py | 72 |
4 files changed, 352 insertions, 98 deletions
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py index 50aefda28..1131d0600 100644 --- a/pym/_emerge/depgraph.py +++ b/pym/_emerge/depgraph.py @@ -52,6 +52,7 @@ from _emerge.SetArg import SetArg from _emerge.show_invalid_depstring_notice import show_invalid_depstring_notice from _emerge.UnmergeDepPriority import UnmergeDepPriority +from _emerge.resolver.backtracking import Backtracker, BacktrackParameter from _emerge.resolver.slot_collision import slot_conflict_handler from _emerge.resolver.circular_dependency import circular_dependency_handler from _emerge.resolver.output import display, filter_iuse_defaults @@ -127,8 +128,7 @@ class _depgraph_sets(object): class _dynamic_depgraph_config(object): - def __init__(self, depgraph, myparams, allow_backtracking, - runtime_pkg_mask, needed_unstable_keywords, needed_use_config_changes, needed_license_changes): + def __init__(self, depgraph, myparams, allow_backtracking, backtrack_parameters): self.myparams = myparams.copy() self._vdb_loaded = False self._allow_backtracking = allow_backtracking @@ -195,33 +195,16 @@ class _dynamic_depgraph_config(object): self._initially_unsatisfied_deps = [] self._ignored_deps = [] self._highest_pkg_cache = {} - if runtime_pkg_mask is None: - runtime_pkg_mask = {} - else: - runtime_pkg_mask = dict((k, v.copy()) for (k, v) in \ - runtime_pkg_mask.items()) - - if needed_unstable_keywords is None: - self._needed_unstable_keywords = set() - else: - self._needed_unstable_keywords = needed_unstable_keywords.copy() - - if needed_license_changes is None: - self._needed_license_changes = {} - else: - self._needed_license_changes = needed_license_changes.copy() - if needed_use_config_changes is None: - self._needed_use_config_changes = {} - else: - self._needed_use_config_changes = \ - dict((k.copy(), (v[0].copy(), v[1].copy())) for (k, v) in \ - needed_use_config_changes.items()) + self._needed_unstable_keywords = backtrack_parameters.needed_unstable_keywords + self._needed_license_changes = backtrack_parameters.needed_license_changes + self._needed_use_config_changes = backtrack_parameters.needed_use_config_changes + self._runtime_pkg_mask = backtrack_parameters.runtime_pkg_mask + self._need_restart = False + self._backtrack_infos = {} self._autounmask = depgraph._frozen_config.myopts.get('--autounmask', 'n') == True - - self._runtime_pkg_mask = runtime_pkg_mask - self._need_restart = False + self._success_without_autounmask = False for myroot in depgraph._frozen_config.trees: self.sets[myroot] = _depgraph_sets() @@ -300,15 +283,13 @@ class depgraph(object): _dep_keys = ["DEPEND", "RDEPEND", "PDEPEND"] def __init__(self, settings, trees, myopts, myparams, spinner, - frozen_config=None, runtime_pkg_mask=None, needed_unstable_keywords=None, \ - needed_use_config_changes=None, needed_license_changes=None, allow_backtracking=False): + frozen_config=None, backtrack_parameters=BacktrackParameter(), allow_backtracking=False): if frozen_config is None: frozen_config = _frozen_depgraph_config(settings, trees, myopts, spinner) self._frozen_config = frozen_config self._dynamic_config = _dynamic_depgraph_config(self, myparams, - allow_backtracking, runtime_pkg_mask, needed_unstable_keywords, \ - needed_use_config_changes, needed_license_changes) + allow_backtracking, backtrack_parameters) self._select_atoms = self._select_atoms_highest_available self._select_package = self._select_pkg_highest_available @@ -722,16 +703,14 @@ class depgraph(object): (dep.parent, self._dynamic_config._runtime_pkg_mask[ dep.parent]), noiselevel=-1) - else: + elif not self.need_restart(): # Do not backtrack if only USE have to be changed in # order to satisfy the dependency. dep_pkg, existing_node = \ self._select_package(dep.root, dep.atom.without_use, onlydeps=dep.onlydeps) if dep_pkg is None: - self._dynamic_config._runtime_pkg_mask.setdefault( - dep.parent, {})["missing dependency"] = \ - set([(dep.parent, dep.root, dep.atom)]) + self._dynamic_config._backtrack_infos["missing dependency"] = dep self._dynamic_config._need_restart = True if "--debug" in self._frozen_config.myopts: msg = [] @@ -882,47 +861,46 @@ class depgraph(object): self._dynamic_config._runtime_pkg_mask[ existing_node]), noiselevel=-1) elif self._dynamic_config._allow_backtracking and \ - not self._accept_blocker_conflicts(): + not self._accept_blocker_conflicts() and \ + not self.need_restart(): + self._add_slot_conflict(pkg) if dep.atom is not None and dep.parent is not None: self._add_parent_atom(pkg, (dep.parent, dep.atom)) + if arg_atoms: for parent_atom in arg_atoms: parent, atom = parent_atom self._add_parent_atom(pkg, parent_atom) self._process_slot_conflicts() - # NOTE: We always mask existing_node since - # _select_package tries to avoid slot conflicts when - # possible and therefore a conflict typically means - # that existing_node was a poor choice. - to_be_masked = existing_node - - parent_atoms = \ - self._dynamic_config._parent_atoms.get(pkg, set()) - if parent_atoms: - conflict_atoms = self._dynamic_config._slot_conflict_parent_atoms.intersection(parent_atoms) - if conflict_atoms: - parent_atoms = conflict_atoms - - if pkg >= existing_node: - # We only care about the parent atoms - # when they trigger a downgrade. - parent_atoms = set() - - self._dynamic_config._runtime_pkg_mask.setdefault( - to_be_masked, {})["slot conflict"] = parent_atoms + backtrack_data = [] + all_parents = set() + for node, other_node in (existing_node, pkg), (pkg, existing_node): + parent_atoms = \ + self._dynamic_config._parent_atoms.get(node, set()) + if parent_atoms: + conflict_atoms = self._dynamic_config._slot_conflict_parent_atoms.intersection(parent_atoms) + if conflict_atoms: + parent_atoms = conflict_atoms + all_parents.update(parent_atoms) + if node < other_node: + parent_atoms = set() + backtrack_data.append((node, parent_atoms)) + + self._dynamic_config._backtrack_infos["slot conflict"] = backtrack_data self._dynamic_config._need_restart = True if "--debug" in self._frozen_config.myopts: msg = [] msg.append("") msg.append("") msg.append("backtracking due to slot conflict:") - msg.append(" package: %s" % to_be_masked) - msg.append(" slot: %s" % to_be_masked.slot_atom) + msg.append(" first package: %s" % existing_node) + msg.append(" second package: %s" % pkg) + msg.append(" slot: %s" % pkg.slot_atom) msg.append(" parents: %s" % \ [(str(parent), atom) \ - for parent, atom in parent_atoms]) + for parent, atom in all_parents]) msg.append("") writemsg_level("".join("%s\n" % l for l in msg), noiselevel=-1, level=logging.DEBUG) @@ -1917,6 +1895,8 @@ class depgraph(object): set(self._dynamic_config.digraph).intersection( \ self._dynamic_config._needed_license_changes) : #We failed if the user needs to change the configuration + if not missing: + self._dynamic_config._success_without_autounmask = True return False, myfavorites # We're true here unless we are missing binaries. @@ -2631,9 +2611,18 @@ class depgraph(object): if masked_by_unstable_keywords: self._dynamic_config._needed_unstable_keywords.add(pkg) + backtrack_infos = self._dynamic_config._backtrack_infos + backtrack_infos.setdefault("config", {}) + backtrack_infos["config"].setdefault("needed_unstable_keywords", set()) + backtrack_infos["config"]["needed_unstable_keywords"].add(pkg) + if missing_licenses: self._dynamic_config._needed_license_changes.setdefault(pkg, set()).update(missing_licenses) + backtrack_infos = self._dynamic_config._backtrack_infos + backtrack_infos.setdefault("config", {}) + backtrack_infos["config"].setdefault("needed_license_changes", set()) + backtrack_infos["config"]["needed_license_changes"].add((pkg, frozenset(missing_licenses))) return True @@ -2709,8 +2698,12 @@ class depgraph(object): if required_use and check_required_use(required_use, old_use, pkg.iuse.is_valid_flag) and \ not check_required_use(required_use, new_use, pkg.iuse.is_valid_flag): return old_use - + self._dynamic_config._needed_use_config_changes[pkg] = (new_use, new_changes) + backtrack_infos = self._dynamic_config._backtrack_infos + backtrack_infos.setdefault("config", {}) + backtrack_infos["config"].setdefault("needed_use_config_changes", []) + backtrack_infos["config"]["needed_use_config_changes"].append((pkg, (new_use, new_changes))) if want_restart_for_use_change(pkg, new_use): self._dynamic_config._need_restart = True return new_use @@ -5136,18 +5129,12 @@ class depgraph(object): def need_restart(self): return self._dynamic_config._need_restart + + def success_without_autounmask(self): + return self._dynamic_config._success_without_autounmask - def get_backtrack_parameters(self): - return { - "needed_unstable_keywords": - self._dynamic_config._needed_unstable_keywords.copy(), \ - "runtime_pkg_mask": - self._dynamic_config._runtime_pkg_mask.copy(), - "needed_use_config_changes": - self._dynamic_config._needed_use_config_changes.copy(), - "needed_license_changes": - self._dynamic_config._needed_license_changes.copy(), - } + def get_backtrack_infos(self): + return self._dynamic_config._backtrack_infos class _dep_check_composite_db(dbapi): @@ -5375,44 +5362,42 @@ def backtrack_depgraph(settings, trees, myopts, myparams, finally: _spinner_stop(spinner) -def _backtrack_depgraph(settings, trees, myopts, myparams, - myaction, myfiles, spinner): - backtrack_max = myopts.get('--backtrack', 5) - backtrack_parameters = {} - needed_unstable_keywords = None - allow_backtracking = backtrack_max > 0 - backtracked = 0 +def _backtrack_depgraph(settings, trees, myopts, myparams, myaction, myfiles, spinner): + + max_depth = myopts.get('--backtrack', 5) + allow_backtracking = max_depth > 0 + backtracker = Backtracker(max_depth) + frozen_config = _frozen_depgraph_config(settings, trees, myopts, spinner) - while True: + + while backtracker: + backtrack_parameters = backtracker.get() + mydepgraph = depgraph(settings, trees, myopts, myparams, spinner, frozen_config=frozen_config, allow_backtracking=allow_backtracking, - **backtrack_parameters) + backtrack_parameters=backtrack_parameters) success, favorites = mydepgraph.select_files(myfiles) - if not success: - if mydepgraph.need_restart() and backtracked < backtrack_max: - backtrack_parameters = mydepgraph.get_backtrack_parameters() - backtracked += 1 - elif backtracked and allow_backtracking: - if "--debug" in myopts: - writemsg_level( - "\n\nbacktracking aborted after %s tries\n\n" % \ - backtracked, noiselevel=-1, level=logging.DEBUG) - # Backtracking failed, so disable it and do - # a plain dep calculation + error message. - allow_backtracking = False - #Don't reset needed_unstable_keywords here, since we don't want to - #send the user through a "one step at a time" unmasking session for - #no good reason. - backtrack_parameters.pop('runtime_pkg_mask', None) - else: - break - else: + + if success or mydepgraph.success_without_autounmask(): break + elif mydepgraph.need_restart(): + backtracker.feedback(mydepgraph.get_backtrack_infos()) + + if not (success or mydepgraph.success_without_autounmask()) and backtracker.backtracked(): + backtrack_parameters = backtracker.get_best_run() + + mydepgraph = depgraph(settings, trees, myopts, myparams, spinner, + frozen_config=frozen_config, + allow_backtracking=False, + backtrack_parameters=backtrack_parameters) + success, favorites = mydepgraph.select_files(myfiles) + return (success, mydepgraph, favorites) + def resume_depgraph(settings, trees, mtimedb, myopts, myparams, spinner): """ Raises PackageSetNotFound if myfiles contains a missing package set. diff --git a/pym/_emerge/resolver/backtracking.py b/pym/_emerge/resolver/backtracking.py new file mode 100644 index 000000000..ded97e19d --- /dev/null +++ b/pym/_emerge/resolver/backtracking.py @@ -0,0 +1,184 @@ +# Copyright 2010 Gentoo Foundation +# Distributed under the terms of the GNU General Public License v2 + +import copy + +class BacktrackParameter(object): + + __slots__ = ( + "needed_unstable_keywords", "runtime_pkg_mask", "needed_use_config_changes", "needed_license_changes", + ) + + def __init__(self): + self.needed_unstable_keywords = set() + self.runtime_pkg_mask = {} + self.needed_use_config_changes = {} + self.needed_license_changes = {} + + def __deepcopy__(self, memo=None): + if memo is None: + memo = {} + result = BacktrackParameter() + memo[id(self)] = result + + #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.needed_unstable_keywords = copy.copy(self.needed_unstable_keywords) + result.runtime_pkg_mask = copy.copy(self.runtime_pkg_mask) + result.needed_use_config_changes = copy.copy(self.needed_use_config_changes) + result.needed_license_changes = copy.copy(self.needed_license_changes) + + return result + + def __eq__(self, other): + return self.needed_unstable_keywords == other.needed_unstable_keywords and \ + self.runtime_pkg_mask == other.runtime_pkg_mask and \ + self.needed_use_config_changes == other.needed_use_config_changes and \ + self.needed_license_changes == other.needed_license_changes + + +class _BacktrackNode: + + __slots__ = ( + "parameter", "depth", "mask_steps", "terminal", + ) + + def __init__(self, parameter=BacktrackParameter(), depth=0, mask_steps=0, terminal=True): + self.parameter = parameter + self.depth = depth + self.mask_steps = mask_steps + self.terminal = terminal + + def __eq__(self, other): + return self.parameter == other.parameter + + +class Backtracker(object): + + __slots__ = ( + "_max_depth", "_unexplored_nodes", "_current_node", "_nodes", "_root", + ) + + def __init__(self, max_depth): + self._max_depth = max_depth + self._unexplored_nodes = [] + self._current_node = None + self._nodes = [] + + self._root = _BacktrackNode() + self._add(self._root) + + + def _add(self, node, explore=True): + """ + Adds a newly computed backtrack parameter. Makes sure that it doesn't already exist and + that we don't backtrack deeper than we are allowed by --backtrack. + """ + if node.mask_steps <= self._max_depth and node not in self._nodes: + if explore: + self._unexplored_nodes.append(node) + self._nodes.append(node) + + + def get(self): + """ + Returns a backtrack paramater. The backtrack graph is explored with depth first. + """ + if self._unexplored_nodes: + node = self._unexplored_nodes.pop() + self._current_node = node + return copy.deepcopy(node.parameter) + else: + return None + + + def __len__(self): + return len(self._unexplored_nodes) + + + def _feedback_slot_conflict(self, conflict_data): + for pkg, parent_atoms in conflict_data: + new_node = copy.deepcopy(self._current_node) + new_node.depth += 1 + new_node.mask_steps += 1 + new_node.terminal = False + for other_pkg, other_parent_atoms in conflict_data: + if other_pkg is pkg: + continue + new_node.parameter.runtime_pkg_mask.setdefault( + other_pkg, {})["slot conflict"] = other_parent_atoms + self._add(new_node) + + + def _feedback_missing_dep(self, dep): + new_node = copy.deepcopy(self._current_node) + new_node.depth += 1 + new_node.mask_steps += 1 + new_node.terminal = False + + new_node.parameter.runtime_pkg_mask.setdefault( + dep.parent, {})["missing dependency"] = \ + set([(dep.parent, dep.root, dep.atom)]) + + self._add(new_node) + + + def _feedback_config(self, changes, explore=True): + """ + Handle config changes. Don't count config changes for the maximum backtrack depth. + """ + new_node = copy.deepcopy(self._current_node) + new_node.depth += 1 + para = new_node.parameter + + for change, data in changes.items(): + if change == "needed_unstable_keywords": + para.needed_unstable_keywords.update(data) + elif change == "needed_license_changes": + for pkg, missing_licenses in data: + para.needed_license_changes.setdefault(pkg, set()).update(missing_licenses) + elif change == "needed_use_config_changes": + for pkg, (new_use, new_changes) in data: + para.needed_use_config_changes[pkg] = (new_use, new_changes) + + self._add(new_node, explore=explore) + self._current_node = new_node + + + def feedback(self, infos): + """ + Takes infomration from the depgraph and computes new backtrack parameters to try. + """ + assert self._current_node is not None, "call feedback() only after get() was called" + + #Not all config changes require a restart, that's why they can appear together + #with other conflicts. + if "config" in infos: + self._feedback_config(infos["config"], explore=(len(infos)==1)) + + #There is at most one of the following types of conflicts for a given restart. + if "slot conflict" in infos: + self._feedback_slot_conflict(infos["slot conflict"]) + elif "missing dependency" in infos: + self._feedback_missing_dep(infos["missing dependency"]) + + + def backtracked(self): + """ + If we dind't backtrack, there is only the root. + """ + return len(self._nodes) > 1 + + + def get_best_run(self): + """ + Like, get() but returns the backtrack parameter that has as many config changes as possible, + but has no masks. This maskes --autounmask effective, but prevents confusing error messages + with "masked by backtracking". + """ + best_node = self._root + for node in self._nodes: + if node.terminal and node.depth > best_node.depth: + best_node = node + + return copy.deepcopy(best_node.parameter) diff --git a/pym/portage/tests/resolver/test_autounmask.py b/pym/portage/tests/resolver/test_autounmask.py index ce3ce38f0..760c76487 100644 --- a/pym/portage/tests/resolver/test_autounmask.py +++ b/pym/portage/tests/resolver/test_autounmask.py @@ -194,6 +194,11 @@ class AutounmaskTestCase(TestCase): "dev-libs/A-1": { "LICENSE": "TEST" }, "dev-libs/B-1": { "LICENSE": "TEST", "IUSE": "foo", "KEYWORDS": "~x86"}, "dev-libs/C-1": { "DEPEND": "dev-libs/B[foo]", "EAPI": 2 }, + + "dev-libs/D-1": { "DEPEND": "dev-libs/E dev-libs/F", "LICENSE": "TEST" }, + "dev-libs/E-1": { "LICENSE": "TEST" }, + "dev-libs/E-2": { "LICENSE": "TEST" }, + "dev-libs/F-1": { "DEPEND": "=dev-libs/E-1", "LICENSE": "TEST" }, } test_cases = ( @@ -217,6 +222,14 @@ class AutounmaskTestCase(TestCase): license_changes = { "dev-libs/B-1": set(["TEST"]) }, unstable_keywords = ["dev-libs/B-1"], use_changes = { "dev-libs/B-1": { "foo": True } }), + + #Test license with backtracking. + ResolverPlaygroundTestCase( + ["=dev-libs/D-1"], + options = {"--autounmask": True}, + success = False, + mergelist = ["dev-libs/E-1", "dev-libs/F-1", "dev-libs/D-1"], + license_changes = { "dev-libs/D-1": set(["TEST"]), "dev-libs/E-1": set(["TEST"]), "dev-libs/E-2": set(["TEST"]), "dev-libs/F-1": set(["TEST"]) }), ) playground = ResolverPlayground(ebuilds=ebuilds) diff --git a/pym/portage/tests/resolver/test_backtracking.py b/pym/portage/tests/resolver/test_backtracking.py index 91a739aaf..41b6d50b6 100644 --- a/pym/portage/tests/resolver/test_backtracking.py +++ b/pym/portage/tests/resolver/test_backtracking.py @@ -30,6 +30,44 @@ class BacktrackingTestCase(TestCase): finally: playground.cleanup() + + def testHittingTheBacktrackLimit(self): + ebuilds = { + "dev-libs/A-1": {}, + "dev-libs/A-2": {}, + "dev-libs/B-1": {}, + "dev-libs/B-2": {}, + "dev-libs/C-1": { "DEPEND": "dev-libs/A dev-libs/B" }, + "dev-libs/D-1": { "DEPEND": "=dev-libs/A-1 =dev-libs/B-1" }, + } + + test_cases = ( + ResolverPlaygroundTestCase( + ["dev-libs/C", "dev-libs/D"], + all_permutations = True, + mergelist = ["dev-libs/A-1", "dev-libs/B-1", "dev-libs/C-1", "dev-libs/D-1"], + ignore_mergelist_order = True, + success = True), + #This one hits the backtrack limit. Be aware that this depends on the argument order. + ResolverPlaygroundTestCase( + ["dev-libs/D", "dev-libs/C"], + options = { "--backtrack": 1 }, + mergelist = ["dev-libs/A-1", "dev-libs/B-1", "dev-libs/A-2", "dev-libs/B-2", "dev-libs/C-1", "dev-libs/D-1"], + ignore_mergelist_order = True, + slot_collision_solutions = [], + success = False), + ) + + playground = ResolverPlayground(ebuilds=ebuilds) + + 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 testBacktrackingGoodVersionFirst(self): """ When backtracking due to slot conflicts, we masked the version that has been pulled @@ -59,3 +97,37 @@ class BacktrackingTestCase(TestCase): self.assertEqual(test_case.test_success, True, test_case.fail_msg) finally: playground.cleanup() + + def testBacktrackWithoutUpdates(self): + """ + If --update is not given we might have to mask the old installed version later. + """ + + ebuilds = { + "dev-libs/A-1": { "DEPEND": "dev-libs/Z" }, + "dev-libs/B-1": { "DEPEND": ">=dev-libs/Z-2" }, + "dev-libs/Z-1": { }, + "dev-libs/Z-2": { }, + } + + installed = { + "dev-libs/Z-1": { "USE": "" }, + } + + test_cases = ( + ResolverPlaygroundTestCase( + ["dev-libs/B", "dev-libs/A"], + all_permutations = True, + mergelist = ["dev-libs/Z-2", "dev-libs/B-1", "dev-libs/A-1", ], + ignore_mergelist_order = True, + success = True), + ) + + playground = ResolverPlayground(ebuilds=ebuilds, installed=installed) + + 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() |