1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
# Copyright 2010-2011 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",
"rebuild_list", "reinstall_list", "needed_p_mask_changes"
)
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()
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.runtime_pkg_mask = copy.copy(self.runtime_pkg_mask)
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)
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
class _BacktrackNode:
__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 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 _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 == "rebuild_list":
para.rebuild_list.update(data)
elif change == "reinstall_list":
para.reinstall_list.update(data)
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_conflict(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)
|