Gentoo Archives: gentoo-commits

From: "Zac Medico (zmedico)" <zmedico@g.o>
To: gentoo-commits@l.g.o
Subject: [gentoo-commits] portage r9981 - in main/trunk/pym: _emerge portage
Date: Sat, 26 Apr 2008 20:16:07
Message-Id: E1JpqoW-0004CA-53@stork.gentoo.org
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