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