pym/_emerge/resolver/circular_dependency.py

   1 # Copyright 2010-2011 Gentoo Foundation
   2 # Distributed under the terms of the GNU General Public License v2
   3
   4 from __future__ import print_function
   5
   6 from itertools import chain, product
   7 import logging
   8
   9 from portage.dep import use_reduce, extract_affecting_use, check_required_use, get_required_use_flags
  10 from portage.exception import InvalidDependString
  11 from portage.output import colorize
  12 from portage.util import writemsg_level
  13 from _emerge.DepPrioritySatisfiedRange import DepPrioritySatisfiedRange
  14
  15 class circular_dependency_handler(object):
  16
  17         def __init__(self, depgraph, graph):
  18                 self.depgraph = depgraph
  19                 self.graph = graph
  20                 self.all_parent_atoms = depgraph._dynamic_config._parent_atoms
  21
  22                 if "--debug" in depgraph._frozen_config.myopts:
  23                         # Show this debug output before doing the calculations
  24                         # that follow, so at least we have this debug info
  25                         # if we happen to hit a bug later.
  26                         writemsg_level("\n\ncircular dependency graph:\n\n",
  27                                 level=logging.DEBUG, noiselevel=-1)
  28                         self.debug_print()
  29
  30                 self.cycles, self.shortest_cycle = self._find_cycles()
  31                 #Guess if it is a large cluster of cycles. This usually requires
  32                 #a global USE change.
  33                 self.large_cycle_count = len(self.cycles) > 3
  34                 self.merge_list = self._prepare_reduced_merge_list()
  35                 #The digraph dump
  36                 self.circular_dep_message = self._prepare_circular_dep_message()
  37                 #Suggestions, in machine and human readable form
  38                 self.solutions, self.suggestions = self._find_suggestions()
  39
  40         def _find_cycles(self):
  41                 shortest_cycle = None
  42                 cycles = self.graph.get_cycles(ignore_priority=DepPrioritySatisfiedRange.ignore_medium_soft)
  43                 for cycle in cycles:
  44                         if not shortest_cycle or len(cycle) < len(shortest_cycle):
  45                                 shortest_cycle = cycle
  46                 return cycles, shortest_cycle
  47
  48         def _prepare_reduced_merge_list(self):
  49                 """
  50                 Create a merge to be displayed by depgraph.display().
  51                 This merge list contains only packages involved in
  52                 the circular deps.
  53                 """
  54                 display_order = []
  55                 tempgraph = self.graph.copy()
  56                 while tempgraph:
  57                         nodes = tempgraph.leaf_nodes()
  58                         if not nodes:
  59                                 node = tempgraph.order[0]
  60                         else:
  61                                 node = nodes[0]
  62                         display_order.append(node)
  63                         tempgraph.remove(node)
  64                 display_order.reverse()
  65                 return display_order
  66
  67         def _prepare_circular_dep_message(self):
  68                 """
  69                 Like digraph.debug_print(), but prints only the shortest cycle.
  70                 """
  71                 if not self.shortest_cycle:
  72                         return None
  73
  74                 msg = []
  75                 indent = ""
  76                 for pos, pkg in enumerate(self.shortest_cycle):
  77                         parent = self.shortest_cycle[pos-1]
  78                         priorities = self.graph.nodes[parent][0][pkg]
  79                         if pos > 0:
  80                                 msg.append(indent + "%s (%s)" % (pkg, priorities[-1],))
  81                         else:
  82                                 msg.append(indent + "%s depends on" % pkg)
  83                         indent += " "
  84
  85                 pkg = self.shortest_cycle[0]
  86                 parent = self.shortest_cycle[-1]
  87                 priorities = self.graph.nodes[parent][0][pkg]
  88                 msg.append(indent + "%s (%s)" % (pkg, priorities[-1],))
  89
  90                 return "\n".join(msg)
  91
  92         def _get_use_mask_and_force(self, pkg):
  93                 return pkg.use.mask, pkg.use.force
  94
  95         def _get_autounmask_changes(self, pkg):
  96                 needed_use_config_change = self.depgraph._dynamic_config._needed_use_config_changes.get(pkg)
  97                 if needed_use_config_change is None:
  98                         return frozenset()
  99
 100                 use, changes = needed_use_config_change
 101                 return frozenset(changes.keys())
 102
 103         def _find_suggestions(self):
 104                 if not self.shortest_cycle:
 105                         return None, None
 106
 107                 suggestions = []
 108                 final_solutions = {}
 109
 110                 for pos, pkg in enumerate(self.shortest_cycle):
 111                         parent = self.shortest_cycle[pos-1]
 112                         priorities = self.graph.nodes[parent][0][pkg]
 113                         parent_atoms = self.all_parent_atoms.get(pkg)
 114
 115                         if priorities[-1].buildtime:
 116                                 dep = parent.metadata["DEPEND"]
 117                         elif priorities[-1].runtime:
 118                                 dep = parent.metadata["RDEPEND"]
 119
 120                         for ppkg, atom in parent_atoms:
 121                                 if ppkg == parent:
 122                                         changed_parent = ppkg
 123                                         parent_atom = atom.unevaluated_atom
 124                                         break
 125
 126                         try:
 127                                 affecting_use = extract_affecting_use(dep, parent_atom,
 128                                         eapi=parent.metadata["EAPI"])
 129                         except InvalidDependString:
 130                                 if not parent.installed:
 131                                         raise
 132                                 affecting_use = set()
 133
 134                         # Make sure we don't want to change a flag that is
 135                         #       a) in use.mask or use.force
 136                         #       b) changed by autounmask
 137
 138                         usemask, useforce = self._get_use_mask_and_force(parent)
 139                         autounmask_changes = self._get_autounmask_changes(parent)
 140                         untouchable_flags = frozenset(chain(usemask, useforce, autounmask_changes))
 141
 142                         affecting_use.difference_update(untouchable_flags)
 143
 144                         #If any of the flags we're going to touch is in REQUIRED_USE, add all
 145                         #other flags in REQUIRED_USE to affecting_use, to not lose any solution.
 146                         required_use_flags = get_required_use_flags(parent.metadata["REQUIRED_USE"])
 147
 148                         if affecting_use.intersection(required_use_flags):
 149                                 affecting_use.update(required_use_flags)
 150                                 affecting_use.difference_update(untouchable_flags)
 151
 152                         affecting_use = tuple(affecting_use)
 153
 154                         if not affecting_use:
 155                                 continue
 156
 157                         #We iterate over all possible settings of these use flags and gather
 158                         #a set of possible changes
 159                         #TODO: Use the information encoded in REQUIRED_USE
 160                         solutions = set()
 161                         for use_state in product(("disabled", "enabled"),
 162                                 repeat=len(affecting_use)):
 163                                 current_use = set(self.depgraph._pkg_use_enabled(parent))
 164                                 for flag, state in zip(affecting_use, use_state):
 165                                         if state == "enabled":
 166                                                 current_use.add(flag)
 167                                         else:
 168                                                 current_use.discard(flag)
 169                                 try:
 170                                         reduced_dep = use_reduce(dep,
 171                                                 uselist=current_use, flat=True)
 172                                 except InvalidDependString:
 173                                         if not parent.installed:
 174                                                 raise
 175                                         reduced_dep = None
 176
 177                                 if reduced_dep is not None and \
 178                                         parent_atom not in reduced_dep:
 179                                         #We found an assignment that removes the atom from 'dep'.
 180                                         #Make sure it doesn't conflict with REQUIRED_USE.
 181                                         required_use = parent.metadata["REQUIRED_USE"]
 182
 183                                         if check_required_use(required_use, current_use, parent.iuse.is_valid_flag):
 184                                                 use = self.depgraph._pkg_use_enabled(parent)
 185                                                 solution = set()
 186                                                 for flag, state in zip(affecting_use, use_state):
 187                                                         if state == "enabled" and \
 188                                                                 flag not in use:
 189                                                                 solution.add((flag, True))
 190                                                         elif state == "disabled" and \
 191                                                                 flag in use:
 192                                                                 solution.add((flag, False))
 193                                                 solutions.add(frozenset(solution))
 194
 195                         for solution in solutions:
 196                                 ignore_solution = False
 197                                 for other_solution in solutions:
 198                                         if solution is other_solution:
 199                                                 continue
 200                                         if solution.issuperset(other_solution):
 201                                                 ignore_solution = True
 202                                 if ignore_solution:
 203                                         continue
 204
 205                                 #Check if a USE change conflicts with use requirements of the parents.
 206                                 #If a requiremnet is hard, ignore the suggestion.
 207                                 #If the requirment is conditional, warn the user that other changes might be needed.
 208                                 followup_change = False
 209                                 parent_parent_atoms = self.depgraph._dynamic_config._parent_atoms.get(changed_parent)
 210                                 for ppkg, atom in parent_parent_atoms:
 211
 212                                         atom = atom.unevaluated_atom
 213                                         if not atom.use:
 214                                                 continue
 215
 216                                         for flag, state in solution:
 217                                                 if flag in atom.use.enabled or flag in atom.use.disabled:
 218                                                         ignore_solution = True
 219                                                         break
 220                                                 elif atom.use.conditional:
 221                                                         for flags in atom.use.conditional.values():
 222                                                                 if flag in flags:
 223                                                                         followup_change = True
 224                                                                         break
 225
 226                                         if ignore_solution:
 227                                                 break
 228
 229                                 if ignore_solution:
 230                                         continue
 231
 232                                 changes = []
 233                                 for flag, state in solution:
 234                                         if state:
 235                                                 changes.append(colorize("red", "+"+flag))
 236                                         else:
 237                                                 changes.append(colorize("blue", "-"+flag))
 238                                 msg = "- %s (Change USE: %s)\n" \
 239                                         % (parent.cpv, " ".join(changes))
 240                                 if followup_change:
 241                                         msg += " (This change might require USE changes on parent packages.)"
 242                                 suggestions.append(msg)
 243                                 final_solutions.setdefault(pkg, set()).add(solution)
 244
 245                 return final_solutions, suggestions
 246
 247         def debug_print(self):
 248                 """
 249                 Create a copy of the digraph, prune all root nodes,
 250                 and call the debug_print() method.
 251                 """
 252                 graph = self.graph.copy()
 253                 while True:
 254                         root_nodes = graph.root_nodes(
 255                                 ignore_priority=DepPrioritySatisfiedRange.ignore_medium_soft)
 256                         if not root_nodes:
 257                                 break
 258                         graph.difference_update(root_nodes)
 259
 260                 graph.debug_print()