1 |
Author: zmedico |
2 |
Date: 2008-04-27 00:25:51 +0000 (Sun, 27 Apr 2008) |
3 |
New Revision: 9987 |
4 |
|
5 |
Modified: |
6 |
main/branches/2.1.2/bin/emerge |
7 |
main/branches/2.1.2/pym/portage.py |
8 |
Log: |
9 |
Use digraphs to clean up blocker reference counting in the depgraph. |
10 |
(trunk r9981) |
11 |
|
12 |
|
13 |
Modified: main/branches/2.1.2/bin/emerge |
14 |
=================================================================== |
15 |
--- main/branches/2.1.2/bin/emerge 2008-04-27 00:23:47 UTC (rev 9986) |
16 |
+++ main/branches/2.1.2/bin/emerge 2008-04-27 00:25:51 UTC (rev 9987) |
17 |
@@ -1091,6 +1091,8 @@ |
18 |
def __int__(self): |
19 |
return 0 |
20 |
|
21 |
+BlockerDepPriority.instance = BlockerDepPriority() |
22 |
+ |
23 |
class UnmergeDepPriority(AbstractDepPriority): |
24 |
__slots__ = () |
25 |
""" |
26 |
@@ -1862,9 +1864,12 @@ |
27 |
self._atom_arg_map = {} |
28 |
# contains all nodes pulled in by self._set_atoms |
29 |
self._set_nodes = set() |
30 |
- self.blocker_digraph = digraph() |
31 |
- self.blocker_parents = {} |
32 |
- self._unresolved_blocker_parents = {} |
33 |
+ # Contains only Blocker -> Uninstall edges |
34 |
+ self._blocker_uninstalls = digraph() |
35 |
+ # Contains only Package -> Blocker edges |
36 |
+ self._blocker_parents = digraph() |
37 |
+ # Contains only unsolvable Package -> Blocker edges |
38 |
+ self._unsolvable_blockers = digraph() |
39 |
self._slot_collision_info = set() |
40 |
# Slot collision nodes are not allowed to block other packages since |
41 |
# blocker validation is only able to account for one package per slot. |
42 |
@@ -2028,9 +2033,8 @@ |
43 |
return 1 |
44 |
# The blocker applies to the root where |
45 |
# the parent is or will be installed. |
46 |
- self.blocker_parents.setdefault( |
47 |
- Blocker(atom=dep.atom, root=dep.parent.root), set()).add( |
48 |
- dep.parent) |
49 |
+ blocker = Blocker(atom=dep.atom, root=dep.parent.root) |
50 |
+ self._blocker_parents.add(blocker, dep.parent) |
51 |
return 1 |
52 |
dep_pkg, existing_node = self._select_package(dep.root, dep.atom, |
53 |
onlydeps=dep.onlydeps) |
54 |
@@ -3276,17 +3280,12 @@ |
55 |
blocker_cache.BlockerData(counter, blocker_atoms) |
56 |
if blocker_atoms: |
57 |
for myatom in blocker_atoms: |
58 |
- blocker = ("blocks", myroot, myatom[1:]) |
59 |
- myparents = \ |
60 |
- self.blocker_parents.get(blocker, None) |
61 |
- if not myparents: |
62 |
- myparents = set() |
63 |
- self.blocker_parents[blocker] = myparents |
64 |
- myparents.add(node) |
65 |
+ blocker = Blocker(atom=myatom[1:], root=myroot) |
66 |
+ self._blocker_parents.add(blocker, node) |
67 |
blocker_cache.flush() |
68 |
del blocker_cache |
69 |
|
70 |
- for blocker in self.blocker_parents.keys(): |
71 |
+ for blocker in self._blocker_parents.leaf_nodes(): |
72 |
self.spinner.update() |
73 |
mytype, myroot, mydep = blocker |
74 |
initial_db = self.trees[myroot]["vartree"].dbapi |
75 |
@@ -3294,7 +3293,12 @@ |
76 |
blocked_initial = initial_db.match(mydep) |
77 |
blocked_final = final_db.match(mydep) |
78 |
if not blocked_initial and not blocked_final: |
79 |
- del self.blocker_parents[blocker] |
80 |
+ parent_pkgs = self._blocker_parents.parent_nodes(blocker) |
81 |
+ self._blocker_parents.remove(blocker) |
82 |
+ # Discard any parents that don't have any more blockers. |
83 |
+ for pkg in parent_pkgs: |
84 |
+ if not self._blocker_parents.child_nodes(pkg): |
85 |
+ self._blocker_parents.remove(pkg) |
86 |
continue |
87 |
blocked_slots_initial = {} |
88 |
blocked_slots_final = {} |
89 |
@@ -3306,7 +3310,7 @@ |
90 |
blocked_slots_final[cpv] = \ |
91 |
"%s:%s" % (portage.dep_getkey(cpv), |
92 |
final_db.aux_get(cpv, ["SLOT"])[0]) |
93 |
- for parent in list(self.blocker_parents[blocker]): |
94 |
+ for parent in self._blocker_parents.parent_nodes(blocker): |
95 |
ptype, proot, pcpv, pstatus = parent |
96 |
pdbapi = self.trees[proot][self.pkg_tree_map[ptype]].dbapi |
97 |
pslot = pdbapi.aux_get(pcpv, ["SLOT"])[0] |
98 |
@@ -3384,18 +3388,19 @@ |
99 |
self._pkg_cache[uninst_task] = uninst_task |
100 |
# Enforce correct merge order with a hard dep. |
101 |
self.digraph.addnode(uninst_task, inst_task, |
102 |
- priority=BlockerDepPriority()) |
103 |
+ priority=BlockerDepPriority.instance) |
104 |
# Count references to this blocker so that it can be |
105 |
# invalidated after nodes referencing it have been |
106 |
# merged. |
107 |
- self.blocker_digraph.addnode(uninst_task, blocker) |
108 |
+ self._blocker_uninstalls.addnode(uninst_task, blocker) |
109 |
if not unresolved_blocks and not depends_on_order: |
110 |
- self.blocker_parents[blocker].remove(parent) |
111 |
+ self._blocker_parents.remove_edge(blocker, parent) |
112 |
+ if not self._blocker_parents.parent_nodes(blocker): |
113 |
+ self._blocker_parents.remove(blocker) |
114 |
+ if not self._blocker_parents.child_nodes(parent): |
115 |
+ self._blocker_parents.remove(parent) |
116 |
if unresolved_blocks: |
117 |
- self._unresolved_blocker_parents.setdefault( |
118 |
- blocker, set()).add(parent) |
119 |
- if not self.blocker_parents[blocker]: |
120 |
- del self.blocker_parents[blocker] |
121 |
+ self._unsolvable_blockers.add(blocker, parent) |
122 |
|
123 |
return True |
124 |
|
125 |
@@ -3471,7 +3476,7 @@ |
126 |
elif n1_n2_medium: |
127 |
return 1 |
128 |
return -1 |
129 |
- myblockers = self.blocker_digraph.copy() |
130 |
+ myblocker_uninstalls = self._blocker_uninstalls.copy() |
131 |
retlist=[] |
132 |
# Contains any Uninstall tasks that have been ignored |
133 |
# in order to avoid the circular deps code path. These |
134 |
@@ -3480,9 +3485,7 @@ |
135 |
ignored_uninstall_tasks = set() |
136 |
have_uninstall_task = False |
137 |
complete = "complete" in self.myparams |
138 |
- myblocker_parents = self.blocker_parents.copy() |
139 |
- for k, v in myblocker_parents.iteritems(): |
140 |
- myblocker_parents[k] = v.copy() |
141 |
+ myblocker_parents = self._blocker_parents.copy() |
142 |
asap_nodes = [] |
143 |
portage_node = None |
144 |
def get_nodes(**kwargs): |
145 |
@@ -3655,13 +3658,13 @@ |
146 |
selected_nodes = list(selected_nodes) |
147 |
selected_nodes.sort(cmp_circular_bias) |
148 |
|
149 |
- if not selected_nodes and not myblockers.is_empty(): |
150 |
+ if not selected_nodes and not myblocker_uninstalls.is_empty(): |
151 |
# An Uninstall task needs to be executed in order to |
152 |
# avoid conflict if possible. |
153 |
|
154 |
min_parent_deps = None |
155 |
uninst_task = None |
156 |
- for task in myblockers.leaf_nodes(): |
157 |
+ for task in myblocker_uninstalls.leaf_nodes(): |
158 |
# Do some sanity checks so that system or world packages |
159 |
# don't get uninstalled inappropriately here (only really |
160 |
# necessary when --complete-graph has not been enabled). |
161 |
@@ -3746,7 +3749,7 @@ |
162 |
# to avoid the circular deps code path, but the |
163 |
# blocker will still be counted as an unresolved |
164 |
# conflict. |
165 |
- for node in myblockers.leaf_nodes(): |
166 |
+ for node in myblocker_uninstalls.leaf_nodes(): |
167 |
try: |
168 |
mygraph.remove(node) |
169 |
except KeyError: |
170 |
@@ -3829,24 +3832,23 @@ |
171 |
pass |
172 |
if uninst_task is not None and \ |
173 |
uninst_task not in ignored_uninstall_tasks and \ |
174 |
- myblockers.contains(uninst_task): |
175 |
- myblockers.remove(uninst_task) |
176 |
- for blocker in myblockers.root_nodes(): |
177 |
- if myblockers.child_nodes(blocker): |
178 |
- continue |
179 |
- myblockers.remove(blocker) |
180 |
- unresolved = \ |
181 |
- self._unresolved_blocker_parents.get(blocker) |
182 |
- if unresolved: |
183 |
- myblocker_parents[blocker] = unresolved |
184 |
- else: |
185 |
- del myblocker_parents[blocker] |
186 |
+ myblocker_uninstalls.contains(uninst_task): |
187 |
+ blocker_nodes = myblocker_uninstalls.parent_nodes(uninst_task) |
188 |
+ myblocker_uninstalls.remove(uninst_task) |
189 |
+ # Discard any blockers that this Uninstall solves. |
190 |
+ for blocker in blocker_nodes: |
191 |
+ if not myblocker_uninstalls.child_nodes(blocker): |
192 |
+ myblocker_uninstalls.remove(blocker) |
193 |
|
194 |
if node[-1] != "nomerge": |
195 |
retlist.append(list(node)) |
196 |
mygraph.remove(node) |
197 |
|
198 |
- for blocker in myblocker_parents: |
199 |
+ unsolvable_blockers = set(self._unsolvable_blockers.leaf_nodes()) |
200 |
+ for node in myblocker_uninstalls.root_nodes(): |
201 |
+ unsolvable_blockers.add(node) |
202 |
+ |
203 |
+ for blocker in unsolvable_blockers: |
204 |
retlist.append(list(blocker)) |
205 |
|
206 |
# If any Uninstall tasks need to be executed in order |
207 |
@@ -3856,7 +3858,7 @@ |
208 |
# are properly identified and blocked from execution). |
209 |
if have_uninstall_task and \ |
210 |
not complete and \ |
211 |
- not myblocker_parents: |
212 |
+ not unsolvable_blockers: |
213 |
self.myparams.add("complete") |
214 |
raise self._serialize_tasks_retry("") |
215 |
|
216 |
@@ -4064,7 +4066,7 @@ |
217 |
addl = addl + " " + red(resolved) |
218 |
else: |
219 |
addl = "[blocks " + addl + "] " + red(resolved) |
220 |
- block_parents = self.blocker_parents[tuple(x)] |
221 |
+ block_parents = self._blocker_parents.parent_nodes(tuple(x)) |
222 |
block_parents = set([pnode[2] for pnode in block_parents]) |
223 |
block_parents = ", ".join(block_parents) |
224 |
if resolved!=x[2]: |
225 |
|
226 |
Modified: main/branches/2.1.2/pym/portage.py |
227 |
=================================================================== |
228 |
--- main/branches/2.1.2/pym/portage.py 2008-04-27 00:23:47 UTC (rev 9986) |
229 |
+++ main/branches/2.1.2/pym/portage.py 2008-04-27 00:25:51 UTC (rev 9987) |
230 |
@@ -391,6 +391,28 @@ |
231 |
del self.nodes[node] |
232 |
self.order.remove(node) |
233 |
|
234 |
+ def remove_edge(self, child, parent): |
235 |
+ """ |
236 |
+ Remove edge in the direction from child to parent. Note that it is |
237 |
+ possible for a remaining edge to exist in the opposite direction. |
238 |
+ Any endpoint vertices that become isolated will remain in the graph. |
239 |
+ """ |
240 |
+ |
241 |
+ # Nothing should be modified when a KeyError is raised. |
242 |
+ for k in parent, child: |
243 |
+ if k not in self.nodes: |
244 |
+ raise KeyError(k) |
245 |
+ |
246 |
+ # Make sure the edge exists. |
247 |
+ if child not in self.nodes[parent][0]: |
248 |
+ raise KeyError(child) |
249 |
+ if parent not in self.nodes[child][1]: |
250 |
+ raise KeyError(parent) |
251 |
+ |
252 |
+ # Remove the edge. |
253 |
+ del self.nodes[child][1][parent] |
254 |
+ del self.nodes[parent][0][child] |
255 |
+ |
256 |
def contains(self, node): |
257 |
"""Checks if the digraph contains mynode""" |
258 |
return node in self.nodes |
259 |
|
260 |
-- |
261 |
gentoo-commits@l.g.o mailing list |