diff options
| -rw-r--r-- | pym/_emerge/depgraph.py | 168 | ||||
| -rw-r--r-- | pym/_emerge/resolver/circular_dependency.py | 227 |
2 files changed, 240 insertions, 155 deletions
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py index 004534dbe..f2950fb66 100644 --- a/pym/_emerge/depgraph.py +++ b/pym/_emerge/depgraph.py @@ -56,6 +56,7 @@ from _emerge.show_invalid_depstring_notice import show_invalid_depstring_notice from _emerge.UnmergeDepPriority import UnmergeDepPriority from _emerge.resolver.slot_collision import slot_conflict_handler +from _emerge.resolver.circular_dependency import circular_dependency_handler if sys.hexversion >= 0x3000000: basestring = str @@ -170,6 +171,7 @@ class _dynamic_depgraph_config(object): self._parent_atoms = {} self._slot_conflict_parent_atoms = set() self._slot_conflict_handler = None + self._circular_dependency_handler = None self._serialized_tasks_cache = None self._scheduler_graph = None self._displayed_list = None @@ -4100,170 +4102,27 @@ class depgraph(object): return retlist, scheduler_graph def _show_circular_deps(self, mygraph): - shortest_cycle = None - cycles = mygraph.get_cycles(ignore_priority=DepPrioritySatisfiedRange.ignore_medium_soft) - for cycle in cycles: - if not shortest_cycle or len(cycle) < len(shortest_cycle): - shortest_cycle = cycle - # Display the USE flags that are enabled on nodes that are part - # of dependency cycles in case that helps the user decide to - # disable some of them. - display_order = [] - tempgraph = mygraph.copy() - while not tempgraph.empty(): - nodes = tempgraph.leaf_nodes() - if not nodes: - node = tempgraph.order[0] - else: - node = nodes[0] - display_order.append(node) - tempgraph.remove(node) - display_order.reverse() + self._dynamic_config._circular_dependency_handler = \ + circular_dependency_handler(self, mygraph) + handler = self._dynamic_config._circular_dependency_handler + self._frozen_config.myopts.pop("--quiet", None) self._frozen_config.myopts["--verbose"] = True self._frozen_config.myopts["--tree"] = True portage.writemsg("\n\n", noiselevel=-1) - self.display(display_order) + self.display(handler.merge_list) prefix = colorize("BAD", " * ") portage.writemsg("\n", noiselevel=-1) portage.writemsg(prefix + "Error: circular dependencies:\n", noiselevel=-1) portage.writemsg("\n", noiselevel=-1) - suggestions = [] - if shortest_cycle: - indent = "" - for id, pkg in enumerate(shortest_cycle): - if id > 0: - parent = shortest_cycle[id-1] - else: - parent = shortest_cycle[-1] - - priorities = mygraph.nodes[parent][0][pkg] - if id > 0: - writemsg(indent + "%s (%s)\n" % (pkg, priorities[-1],), noiselevel=-1) - else: - writemsg(indent + str(pkg) + " depends on\n", noiselevel=-1) - - if priorities[-1].buildtime: - dep = parent.metadata["DEPEND"] - elif priorities[-1].runtime: - dep = parent.metadata["RDEPEND"] - parent_atoms = self._dynamic_config._parent_atoms.get(pkg) - for ppkg, atom in parent_atoms: - if ppkg == parent: - changed_parent = ppkg - parent_atom = atom.unevaluated_atom - break - affecting_use = portage.dep.extract_affecting_use(dep, parent_atom) - - # Make sure we don't want to change a flag that is in use.mask or use.force. - pkgsettings = self._frozen_config.pkgsettings[parent.root] - pkgsettings.setcpv(parent) - affecting_use.difference_update(pkgsettings.usemask, pkgsettings.useforce) - - if affecting_use: - affecting_use = list(affecting_use) - #We iterate over all possible settings of these use flags and gather - #a set of possible changes - use_state = [] - for flag in affecting_use: - use_state.append("disabled") - - def _next_use_state(state, id=None): - if id is None: - id = len(state)-1 - - if id == 0 and state[0] == "enabled": - return False - - if state[id] == "disabled": - state[id] = "enabled" - for i in range(id+1,len(state)): - state[i] = "disabled" - return True - else: - return _next_use_state(state, id-1) - - solutions = set() - while(True): - current_use = [] - for flag, state in zip(affecting_use, use_state): - if state == "enabled": - current_use.append(flag) - reduced_dep = portage.dep.use_reduce(dep, - uselist=current_use, flat=True) - - if parent_atom not in reduced_dep: - #we found a valid solution - solution = [] - for flag, state in zip(affecting_use, use_state): - if state == "enabled" and \ - flag not in parent.use.enabled: - solution.append("+" + flag) - elif state == "disabled" and \ - flag in parent.use.enabled: - solution.append("-" + flag) - solutions.add(frozenset(solution)) - if not _next_use_state(use_state): - break - for solution in solutions: - ignore_solution = False - for other_solution in solutions: - if solution is other_solution: - continue - if solution.issuperset(other_solution): - ignore_solution = True - if ignore_solution: - continue - - #Check if a USE change conflicts with use requirements of the parents. - #If a requiremnet is hard, ignore the suggestion. - #If the requirment is conditional, warn the user that other changes might be needed. - followup_change = False - parent_parent_atoms = self._dynamic_config._parent_atoms.get(changed_parent) - for ppkg, atom in parent_parent_atoms: - atom = atom.unevaluated_atom - if not atom.use: - continue - - for flag in solution: - flag = flag[1:] #flag has a +/- prefix - if flag in atom.use.enabled \ - or flag in atom.use.disabled: - ignore_solution = True - break - elif atom.use.conditional and flag in atom.use.conditional: - followup_change = True - - if ignore_solution: - break - - if ignore_solution: - continue - - changes = [] - for flag in solution: - if flag.startswith("+"): - changes.append(colorize("red", flag)) - else: - changes.append(colorize("blue", flag)) - - msg = "- %s (Change USE: %s)\n" \ - % (parent.cpv, " ".join(changes)) - if followup_change: - msg += " (This change might require USE changes on parent packages.)" - suggestions.append(msg) - - indent += " " - - pkg = shortest_cycle[0] - parent = shortest_cycle[-1] - priorities = mygraph.nodes[parent][0][pkg] - writemsg(indent + "%s (%s)\n" % (pkg, priorities[-1],), noiselevel=-1) - else: + if handler.circular_dep_message is None: mygraph.debug_print() + else: + portage.writemsg(handler.circular_dep_message, noiselevel=-1) + suggestions = handler.suggestions if suggestions: writemsg("\n\nIt might be possible to break this cycle\n", noiselevel=-1) if len(suggestions) == 1: @@ -4274,18 +4133,17 @@ class depgraph(object): writemsg("".join(suggestions), noiselevel=-1) writemsg("\nNote that this change can be reverted, once the package has" + \ " been installed.\n", noiselevel=-1) - if len(cycles) > 3: + if handler.large_cycle_count: writemsg("\nNote that the dependency graph contains a lot of cycles.\n" + \ "Several changes might be required to resolve all cycles.\n" + \ "Temporarily changing some use flag for all packages might be the better option.\n", noiselevel=-1) else: - writemsg("\n", noiselevel=-1) + writemsg("\n\n", noiselevel=-1) writemsg(prefix + "Note that circular dependencies " + \ "can often be avoided by temporarily\n", noiselevel=-1) writemsg(prefix + "disabling USE flags that trigger " + \ "optional dependencies.\n", noiselevel=-1) - def _show_merge_list(self): if self._dynamic_config._serialized_tasks_cache is not None and \ not (self._dynamic_config._displayed_list and \ diff --git a/pym/_emerge/resolver/circular_dependency.py b/pym/_emerge/resolver/circular_dependency.py new file mode 100644 index 000000000..0930049d2 --- /dev/null +++ b/pym/_emerge/resolver/circular_dependency.py @@ -0,0 +1,227 @@ +# Copyright 2010 Gentoo Foundation +# Distributed under the terms of the GNU General Public License v2 + +from __future__ import print_function + +from portage.util import writemsg +from portage.dep import use_reduce, extract_affecting_use +from portage.output import colorize +from _emerge.DepPrioritySatisfiedRange import DepPrioritySatisfiedRange + +class circular_dependency_handler(object): + + def __init__(self, depgraph, graph): + self.depgraph = depgraph + self.graph = graph + self.all_parent_atoms = depgraph._dynamic_config._parent_atoms + + self.cycles, self.shortest_cycle = self._find_cycles() + #Guess if it is a large cluster of cycles. This usually requires + #a global USE change. + self.large_cycle_count = len(self.cycles) > 3 + self.merge_list = self._prepare_reduced_merge_list() + #The digraph dump + self.circular_dep_message = self._prepare_circular_dep_message() + #Suggestions, in machine and human readable form + self.solutions, self.suggestions = self._find_suggestions() + + def _find_cycles(self): + shortest_cycle = None + cycles = self.graph.get_cycles(ignore_priority=DepPrioritySatisfiedRange.ignore_medium_soft) + for cycle in cycles: + if not shortest_cycle or len(cycle) < len(shortest_cycle): + shortest_cycle = cycle + return cycles, shortest_cycle + + def _prepare_reduced_merge_list(self): + """ + Create a merge to be displayed by depgraph.display(). + This merge list contains only packages involved in + the circular deps. + """ + display_order = [] + tempgraph = self.graph.copy() + while not tempgraph.empty(): + nodes = tempgraph.leaf_nodes() + if not nodes: + node = tempgraph.order[0] + else: + node = nodes[0] + display_order.append(node) + tempgraph.remove(node) + display_order.reverse() + return display_order + + def _prepare_circular_dep_message(self): + """ + Like digraph.debug_print(), but prints only the shortest cycle. + """ + if not self.shortest_cycle: + return None + + msg = [] + indent = "" + for pos, pkg in enumerate(self.shortest_cycle): + parent = self.shortest_cycle[pos-1] + priorities = self.graph.nodes[parent][0][pkg] + if pos > 0: + msg.append(indent + "%s (%s)" % (pkg, priorities[-1],)) + else: + msg.append(indent + "%s depends on" % pkg) + indent += " " + + pkg = self.shortest_cycle[0] + parent = self.shortest_cycle[-1] + priorities = self.graph.nodes[parent][0][pkg] + msg.append(indent + "%s (%s)" % (pkg, priorities[-1],)) + + return "\n".join(msg) + + def _get_use_mask_and_force(self, pkg): + pkgsettings = self.depgraph._frozen_config.pkgsettings[pkg.root] + pkgsettings.setcpv(pkg) + return frozenset(pkgsettings.usemask), frozenset(pkgsettings.useforce) + + def _get_autounmask_changes(self, pkg): + needed_use_config_change = self.depgraph._dynamic_config._needed_use_config_changes.get(pkg) + if needed_use_config_change is None: + return frozenset() + + use, changes = needed_use_config_change + return frozenset(changes.keys()) + + def _find_suggestions(self): + if not self.shortest_cycle: + return None, None + + suggestions = [] + final_solutions = {} + + for pos, pkg in enumerate(self.shortest_cycle): + parent = self.shortest_cycle[pos-1] + priorities = self.graph.nodes[parent][0][pkg] + parent_atoms = self.all_parent_atoms.get(pkg) + + if priorities[-1].buildtime: + dep = parent.metadata["DEPEND"] + elif priorities[-1].runtime: + dep = parent.metadata["RDEPEND"] + + for ppkg, atom in parent_atoms: + if ppkg == parent: + changed_parent = ppkg + parent_atom = atom.unevaluated_atom + break + + affecting_use = extract_affecting_use(dep, parent_atom) + + # Make sure we don't want to change a flag that is + # a) in use.mask or use.force + # b) changed by autounmask + usemask, useforce = self._get_use_mask_and_force(parent) + autounmask_changes = self._get_autounmask_changes(parent) + affecting_use.difference_update(usemask, useforce, autounmask_changes) + affecting_use = tuple(affecting_use) + + if not affecting_use: + continue + + #We iterate over all possible settings of these use flags and gather + #a set of possible changes + #TODO: Use the information encoded in REQUIRED_USE + use_state = [] + for flag in affecting_use: + use_state.append("disabled") + + def _next_use_state(state, id=None): + if id is None: + id = len(state)-1 + + if id == 0 and state[0] == "enabled": + return False + + if state[id] == "disabled": + state[id] = "enabled" + for i in range(id+1,len(state)): + state[i] = "disabled" + return True + else: + return _next_use_state(state, id-1) + + solutions = set() + while(True): + current_use = set(self.depgraph._pkg_use_enabled(parent)) + for flag, state in zip(affecting_use, use_state): + if state == "enabled": + current_use.add(flag) + else: + current_use.discard(flag) + reduced_dep = use_reduce(dep, + uselist=current_use, flat=True) + + if parent_atom not in reduced_dep: + #we found a valid solution + solution = set() + use = self.depgraph._pkg_use_enabled(parent) + for flag, state in zip(affecting_use, use_state): + if state == "enabled" and \ + flag not in use: + solution.add((flag, True)) + elif state == "disabled" and \ + flag in use: + solution.add((flag, False)) + solutions.add(frozenset(solution)) + if not _next_use_state(use_state): + break + + for solution in solutions: + ignore_solution = False + for other_solution in solutions: + if solution is other_solution: + continue + if solution.issuperset(other_solution): + ignore_solution = True + if ignore_solution: + continue + + #Check if a USE change conflicts with use requirements of the parents. + #If a requiremnet is hard, ignore the suggestion. + #If the requirment is conditional, warn the user that other changes might be needed. + followup_change = False + parent_parent_atoms = self.depgraph._dynamic_config._parent_atoms.get(changed_parent) + for ppkg, atom in parent_parent_atoms: + + atom = atom.unevaluated_atom + if not atom.use: + continue + + for flag, state in solution: + if flag in atom.use.enabled or flag in atom.use.disabled: + ignore_solution = True + break + elif atom.use.conditional: + for flags in atom.use.conditional.values(): + if flag in flags: + followup_change = True + break + + if ignore_solution: + break + + if ignore_solution: + continue + + changes = [] + for flag, state in solution: + if state: + changes.append(colorize("red", "+"+flag)) + else: + changes.append(colorize("blue", "-"+flag)) + msg = "- %s (Change USE: %s)\n" \ + % (parent.cpv, " ".join(changes)) + if followup_change: + msg += " (This change might require USE changes on parent packages.)" + suggestions.append(msg) + final_solutions.setdefault(pkg, set()).add(frozenset(solution)) + + return final_solutions, suggestions |