pym/_emerge/resolver/backtracking.py

   1 # Copyright 2010-2011 Gentoo Foundation
   2 # Distributed under the terms of the GNU General Public License v2
   3
   4 import copy
   5
   6 class BacktrackParameter(object):
   7
   8         __slots__ = (
   9                 "needed_unstable_keywords", "runtime_pkg_mask", "needed_use_config_changes", "needed_license_changes",
  10                 "rebuild_list", "reinstall_list", "needed_p_mask_changes",
  11                 "slot_abi_replace_installed"
  12         )
  13
  14         def __init__(self):
  15                 self.needed_unstable_keywords = set()
  16                 self.needed_p_mask_changes = set()
  17                 self.runtime_pkg_mask = {}
  18                 self.needed_use_config_changes = {}
  19                 self.needed_license_changes = {}
  20                 self.rebuild_list = set()
  21                 self.reinstall_list = set()
  22                 self.slot_abi_replace_installed = set()
  23
  24         def __deepcopy__(self, memo=None):
  25                 if memo is None:
  26                         memo = {}
  27                 result = BacktrackParameter()
  28                 memo[id(self)] = result
  29
  30                 #Shallow copies are enough here, as we only need to ensure that nobody adds stuff
  31                 #to our sets and dicts. The existing content is immutable.
  32                 result.needed_unstable_keywords = copy.copy(self.needed_unstable_keywords)
  33                 result.needed_p_mask_changes = copy.copy(self.needed_p_mask_changes)
  34                 result.runtime_pkg_mask = copy.copy(self.runtime_pkg_mask)
  35                 result.needed_use_config_changes = copy.copy(self.needed_use_config_changes)
  36                 result.needed_license_changes = copy.copy(self.needed_license_changes)
  37                 result.rebuild_list = copy.copy(self.rebuild_list)
  38                 result.reinstall_list = copy.copy(self.reinstall_list)
  39                 result.slot_abi_replace_installed = copy.copy(self.slot_abi_replace_installed)
  40
  41                 return result
  42
  43         def __eq__(self, other):
  44                 return self.needed_unstable_keywords == other.needed_unstable_keywords and \
  45                         self.needed_p_mask_changes == other.needed_p_mask_changes and \
  46                         self.runtime_pkg_mask == other.runtime_pkg_mask and \
  47                         self.needed_use_config_changes == other.needed_use_config_changes and \
  48                         self.needed_license_changes == other.needed_license_changes and \
  49                         self.rebuild_list == other.rebuild_list and \
  50                         self.reinstall_list == other.reinstall_list and \
  51                         self.slot_abi_replace_installed == other.slot_abi_replace_installed
  52
  53
  54 class _BacktrackNode(object):
  55
  56         __slots__ = (
  57                 "parameter", "depth", "mask_steps", "terminal",
  58         )
  59
  60         def __init__(self, parameter=BacktrackParameter(), depth=0, mask_steps=0, terminal=True):
  61                 self.parameter = parameter
  62                 self.depth = depth
  63                 self.mask_steps = mask_steps
  64                 self.terminal = terminal
  65
  66         def __eq__(self, other):
  67                 return self.parameter == other.parameter
  68
  69
  70 class Backtracker(object):
  71
  72         __slots__ = (
  73                 "_max_depth", "_unexplored_nodes", "_current_node", "_nodes", "_root",
  74         )
  75
  76         def __init__(self, max_depth):
  77                 self._max_depth = max_depth
  78                 self._unexplored_nodes = []
  79                 self._current_node = None
  80                 self._nodes = []
  81
  82                 self._root = _BacktrackNode()
  83                 self._add(self._root)
  84
  85
  86         def _add(self, node, explore=True):
  87                 """
  88                 Adds a newly computed backtrack parameter. Makes sure that it doesn't already exist and
  89                 that we don't backtrack deeper than we are allowed by --backtrack.
  90                 """
  91                 if not self._check_runtime_pkg_mask(node.parameter.runtime_pkg_mask):
  92                         return
  93
  94                 if node.mask_steps <= self._max_depth and node not in self._nodes:
  95                         if explore:
  96                                 self._unexplored_nodes.append(node)
  97                         self._nodes.append(node)
  98
  99
 100         def get(self):
 101                 """
 102                 Returns a backtrack parameter. The backtrack graph is explored with depth first.
 103                 """
 104                 if self._unexplored_nodes:
 105                         node = self._unexplored_nodes.pop()
 106                         self._current_node = node
 107                         return copy.deepcopy(node.parameter)
 108                 else:
 109                         return None
 110
 111
 112         def __len__(self):
 113                 return len(self._unexplored_nodes)
 114
 115         def _check_runtime_pkg_mask(self, runtime_pkg_mask):
 116                 """
 117                 If a package gets masked that caused other packages to be masked
 118                 before, we revert the mask for other packages (bug 375573).
 119                 """
 120
 121                 for pkg, mask_info in runtime_pkg_mask.items():
 122
 123                         if "missing dependency" in mask_info or \
 124                                 "slot_abi_mask_built" in mask_info:
 125                                 continue
 126
 127                         entry_is_valid = False
 128
 129                         for ppkg, patom in runtime_pkg_mask[pkg].get("slot conflict", set()):
 130                                 if ppkg not in runtime_pkg_mask:
 131                                         entry_is_valid = True
 132                                         break
 133
 134                         if not entry_is_valid:
 135                                 return False
 136
 137                 return True
 138
 139         def _feedback_slot_conflicts(self, conflicts_data):
 140                 # Only create BacktrackNode instances for the first
 141                 # conflict which occurred, since the conflicts that
 142                 # occurred later may have been caused by the first
 143                 # conflict.
 144                 self._feedback_slot_conflict(conflicts_data[0])
 145
 146         def _feedback_slot_conflict(self, conflict_data):
 147                 for pkg, parent_atoms in conflict_data:
 148                         new_node = copy.deepcopy(self._current_node)
 149                         new_node.depth += 1
 150                         new_node.mask_steps += 1
 151                         new_node.terminal = False
 152                         new_node.parameter.runtime_pkg_mask.setdefault(
 153                                 pkg, {})["slot conflict"] = parent_atoms
 154                         self._add(new_node)
 155
 156
 157         def _feedback_missing_dep(self, dep):
 158                 new_node = copy.deepcopy(self._current_node)
 159                 new_node.depth += 1
 160                 new_node.mask_steps += 1
 161                 new_node.terminal = False
 162
 163                 new_node.parameter.runtime_pkg_mask.setdefault(
 164                         dep.parent, {})["missing dependency"] = \
 165                                 set([(dep.parent, dep.root, dep.atom)])
 166
 167                 self._add(new_node)
 168
 169
 170         def _feedback_config(self, changes, explore=True):
 171                 """
 172                 Handle config changes. Don't count config changes for the maximum backtrack depth.
 173                 """
 174                 new_node = copy.deepcopy(self._current_node)
 175                 new_node.depth += 1
 176                 para = new_node.parameter
 177
 178                 for change, data in changes.items():
 179                         if change == "needed_unstable_keywords":
 180                                 para.needed_unstable_keywords.update(data)
 181                         elif change == "needed_p_mask_changes":
 182                                 para.needed_p_mask_changes.update(data)
 183                         elif change == "needed_license_changes":
 184                                 for pkg, missing_licenses in data:
 185                                         para.needed_license_changes.setdefault(pkg, set()).update(missing_licenses)
 186                         elif change == "needed_use_config_changes":
 187                                 for pkg, (new_use, new_changes) in data:
 188                                         para.needed_use_config_changes[pkg] = (new_use, new_changes)
 189                         elif change == "slot_abi_mask_built":
 190                                 for pkg, mask_reasons in data.items():
 191                                         para.runtime_pkg_mask.setdefault(pkg,
 192                                                 {}).update(mask_reasons)
 193                         elif change == "slot_abi_replace_installed":
 194                                 para.slot_abi_replace_installed.update(data)
 195                         elif change == "rebuild_list":
 196                                 para.rebuild_list.update(data)
 197                         elif change == "reinstall_list":
 198                                 para.reinstall_list.update(data)
 199
 200                 self._add(new_node, explore=explore)
 201                 self._current_node = new_node
 202
 203
 204         def feedback(self, infos):
 205                 """
 206                 Takes information from the depgraph and computes new backtrack parameters to try.
 207                 """
 208                 assert self._current_node is not None, "call feedback() only after get() was called"
 209
 210                 #Not all config changes require a restart, that's why they can appear together
 211                 #with other conflicts.
 212                 if "config" in infos:
 213                         self._feedback_config(infos["config"], explore=(len(infos)==1))
 214
 215                 #There is at most one of the following types of conflicts for a given restart.
 216                 if "slot conflict" in infos:
 217                         self._feedback_slot_conflicts(infos["slot conflict"])
 218                 elif "missing dependency" in infos:
 219                         self._feedback_missing_dep(infos["missing dependency"])
 220
 221
 222         def backtracked(self):
 223                 """
 224                 If we didn't backtrack, there is only the root.
 225                 """
 226                 return len(self._nodes) > 1
 227
 228
 229         def get_best_run(self):
 230                 """
 231                 Like, get() but returns the backtrack parameter that has as many config changes as possible,
 232                 but has no masks. This makes --autounmask effective, but prevents confusing error messages
 233                 with "masked by backtracking".
 234                 """
 235                 best_node = self._root
 236                 for node in self._nodes:
 237                         if node.terminal and node.depth > best_node.depth:
 238                                 best_node = node
 239
 240                 return copy.deepcopy(best_node.parameter)