| # Copyright 2010-2012 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", |
| "prune_rebuilds", "rebuild_list", "reinstall_list", "needed_p_mask_changes", |
| "slot_operator_mask_built", "slot_operator_replace_installed" |
| ) |
| |
| def __init__(self): |
| self.needed_unstable_keywords = set() |
| self.needed_p_mask_changes = set() |
| self.runtime_pkg_mask = {} |
| self.needed_use_config_changes = {} |
| self.needed_license_changes = {} |
| self.rebuild_list = set() |
| self.reinstall_list = set() |
| self.slot_operator_replace_installed = set() |
| self.slot_operator_mask_built = set() |
| self.prune_rebuilds = False |
| |
| 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.needed_p_mask_changes = copy.copy(self.needed_p_mask_changes) |
| result.needed_use_config_changes = copy.copy(self.needed_use_config_changes) |
| result.needed_license_changes = copy.copy(self.needed_license_changes) |
| result.rebuild_list = copy.copy(self.rebuild_list) |
| result.reinstall_list = copy.copy(self.reinstall_list) |
| result.slot_operator_replace_installed = copy.copy(self.slot_operator_replace_installed) |
| result.slot_operator_mask_built = self.slot_operator_mask_built.copy() |
| result.prune_rebuilds = self.prune_rebuilds |
| |
| # runtime_pkg_mask contains nested dicts that must also be copied |
| result.runtime_pkg_mask = {} |
| for k, v in self.runtime_pkg_mask.items(): |
| result.runtime_pkg_mask[k] = copy.copy(v) |
| |
| return result |
| |
| def __eq__(self, other): |
| return self.needed_unstable_keywords == other.needed_unstable_keywords and \ |
| self.needed_p_mask_changes == other.needed_p_mask_changes 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 and \ |
| self.rebuild_list == other.rebuild_list and \ |
| self.reinstall_list == other.reinstall_list and \ |
| self.slot_operator_replace_installed == other.slot_operator_replace_installed and \ |
| self.slot_operator_mask_built == other.slot_operator_mask_built and \ |
| self.prune_rebuilds == other.prune_rebuilds |
| |
| |
| class _BacktrackNode(object): |
| |
| __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 not self._check_runtime_pkg_mask(node.parameter.runtime_pkg_mask): |
| return |
| |
| 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 parameter. 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 _check_runtime_pkg_mask(self, runtime_pkg_mask): |
| """ |
| If a package gets masked that caused other packages to be masked |
| before, we revert the mask for other packages (bug 375573). |
| """ |
| |
| for pkg, mask_info in runtime_pkg_mask.items(): |
| |
| if "missing dependency" in mask_info or \ |
| "slot_operator_mask_built" in mask_info: |
| continue |
| |
| entry_is_valid = False |
| |
| for ppkg, patom in runtime_pkg_mask[pkg].get("slot conflict", set()): |
| if ppkg not in runtime_pkg_mask: |
| entry_is_valid = True |
| break |
| |
| if not entry_is_valid: |
| return False |
| |
| return True |
| |
| def _feedback_slot_conflicts(self, conflicts_data): |
| # Only create BacktrackNode instances for the first |
| # conflict which occurred, since the conflicts that |
| # occurred later may have been caused by the first |
| # conflict. |
| self._feedback_slot_conflict(conflicts_data[0]) |
| |
| 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 |
| new_node.parameter.runtime_pkg_mask.setdefault( |
| pkg, {})["slot conflict"] = 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_p_mask_changes": |
| para.needed_p_mask_changes.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) |
| elif change == "slot_conflict_abi": |
| new_node.terminal = False |
| elif change == "slot_operator_mask_built": |
| para.slot_operator_mask_built.update(data) |
| for pkg, mask_reasons in data.items(): |
| para.runtime_pkg_mask.setdefault(pkg, |
| {}).update(mask_reasons) |
| elif change == "slot_operator_replace_installed": |
| para.slot_operator_replace_installed.update(data) |
| elif change == "rebuild_list": |
| para.rebuild_list.update(data) |
| elif change == "reinstall_list": |
| para.reinstall_list.update(data) |
| elif change == "prune_rebuilds": |
| para.prune_rebuilds = True |
| para.slot_operator_replace_installed.clear() |
| for pkg in para.slot_operator_mask_built: |
| runtime_masks = para.runtime_pkg_mask.get(pkg) |
| if runtime_masks is None: |
| continue |
| runtime_masks.pop("slot_operator_mask_built", None) |
| if not runtime_masks: |
| para.runtime_pkg_mask.pop(pkg) |
| para.slot_operator_mask_built.clear() |
| |
| self._add(new_node, explore=explore) |
| self._current_node = new_node |
| |
| |
| def feedback(self, infos): |
| """ |
| Takes information 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_conflicts(infos["slot conflict"]) |
| elif "missing dependency" in infos: |
| self._feedback_missing_dep(infos["missing dependency"]) |
| |
| |
| def backtracked(self): |
| """ |
| If we didn'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 makes --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) |