summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--pym/_emerge/depgraph.py168
-rw-r--r--pym/_emerge/resolver/circular_dependency.py227
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