From 7fdb5d855e9bd97825c1886e9788ecb1539e7759 Mon Sep 17 00:00:00 2001 From: Zac Medico Date: Tue, 19 Jun 2012 14:27:11 -0700 Subject: depgraph: optimize slot conflict backtrack order --- pym/_emerge/depgraph.py | 8 ++++++-- pym/_emerge/resolver/backtracking.py | 10 +++++++++- 2 files changed, 15 insertions(+), 3 deletions(-) diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py index 071d05863..291080ac7 100644 --- a/pym/_emerge/depgraph.py +++ b/pym/_emerge/depgraph.py @@ -366,7 +366,11 @@ class _dynamic_depgraph_config(object): # This use used to check if we have accounted for blockers # relevant to a package. self._traversed_pkg_deps = set() - self._slot_collision_info = {} + # This should be ordered such that the backtracker will + # attempt to solve conflicts which occurred earlier first, + # since an earlier conflict can be the cause of a conflict + # which occurs later. + self._slot_collision_info = OrderedDict() # Slot collision nodes are not allowed to block other packages since # blocker validation is only able to account for one package per slot. self._slot_collision_nodes = set() @@ -911,7 +915,7 @@ class depgraph(object): to_be_masked = backtrack_data[-1][0] self._dynamic_config._backtrack_infos.setdefault( - "slot conflict", []).extend(backtrack_data) + "slot conflict", []).append(backtrack_data) self._dynamic_config._need_restart = True if debug: msg = [] diff --git a/pym/_emerge/resolver/backtracking.py b/pym/_emerge/resolver/backtracking.py index f2857b0f5..2f8b6d0b6 100644 --- a/pym/_emerge/resolver/backtracking.py +++ b/pym/_emerge/resolver/backtracking.py @@ -131,6 +131,14 @@ class Backtracker(object): return True + def _feedback_slot_conflicts(self, conflicts_data): + # This should be ordered such that the backtracker will + # attempt to solve conflicts which occurred earlier first, + # since an earlier conflict can be the cause of a conflict + # which occurs later. + for slot_data in reversed(conflicts_data): + self._feedback_slot_conflict(slot_data) + def _feedback_slot_conflict(self, conflict_data): for pkg, parent_atoms in conflict_data: new_node = copy.deepcopy(self._current_node) @@ -196,7 +204,7 @@ class Backtracker(object): #There is at most one of the following types of conflicts for a given restart. if "slot conflict" in infos: - self._feedback_slot_conflict(infos["slot conflict"]) + self._feedback_slot_conflicts(infos["slot conflict"]) elif "missing dependency" in infos: self._feedback_missing_dep(infos["missing dependency"]) -- cgit v1.2.3-1-g7c22