summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorZac Medico <zmedico@gentoo.org>2008-04-26 20:16:02 +0000
committerZac Medico <zmedico@gentoo.org>2008-04-26 20:16:02 +0000
commite21e34bed60810fe3a15a74d45c03d850890e13b (patch)
tree4de6e1d365de7579226d9bbee409635d0c72d396
parentd1bf7a6eb4d25460560a6a5054159f404f164653 (diff)
downloadportage-e21e34bed60810fe3a15a74d45c03d850890e13b.tar.gz
portage-e21e34bed60810fe3a15a74d45c03d850890e13b.tar.bz2
portage-e21e34bed60810fe3a15a74d45c03d850890e13b.zip
Use digraphs to clean up blocker reference counting in the depgraph.
svn path=/main/trunk/; revision=9981
-rw-r--r--pym/_emerge/__init__.py92
-rw-r--r--pym/portage/__init__.py22
2 files changed, 69 insertions, 45 deletions
diff --git a/pym/_emerge/__init__.py b/pym/_emerge/__init__.py
index 59024197c..1f50bbf9f 100644
--- a/pym/_emerge/__init__.py
+++ b/pym/_emerge/__init__.py
@@ -929,6 +929,8 @@ class BlockerDepPriority(DepPriority):
def __int__(self):
return 0
+BlockerDepPriority.instance = BlockerDepPriority()
+
class UnmergeDepPriority(AbstractDepPriority):
__slots__ = ()
"""
@@ -1723,9 +1725,12 @@ class depgraph(object):
self._atom_arg_map = {}
# contains all nodes pulled in by self._set_atoms
self._set_nodes = set()
- self.blocker_digraph = digraph()
- self.blocker_parents = {}
- self._unresolved_blocker_parents = {}
+ # Contains only Blocker -> Uninstall edges
+ self._blocker_uninstalls = digraph()
+ # Contains only Package -> Blocker edges
+ self._blocker_parents = digraph()
+ # Contains only unsolvable Package -> Blocker edges
+ self._unsolvable_blockers = digraph()
self._slot_collision_info = set()
# Slot collision nodes are not allowed to block other packages since
# blocker validation is only able to account for one package per slot.
@@ -1889,9 +1894,8 @@ class depgraph(object):
return 1
# The blocker applies to the root where
# the parent is or will be installed.
- self.blocker_parents.setdefault(
- Blocker(atom=dep.atom, root=dep.parent.root), set()).add(
- dep.parent)
+ blocker = Blocker(atom=dep.atom, root=dep.parent.root)
+ self._blocker_parents.add(blocker, dep.parent)
return 1
dep_pkg, existing_node = self._select_package(dep.root, dep.atom,
onlydeps=dep.onlydeps)
@@ -3129,17 +3133,12 @@ class depgraph(object):
blocker_cache.BlockerData(counter, blocker_atoms)
if blocker_atoms:
for myatom in blocker_atoms:
- blocker = ("blocks", myroot, myatom[1:])
- myparents = \
- self.blocker_parents.get(blocker, None)
- if not myparents:
- myparents = set()
- self.blocker_parents[blocker] = myparents
- myparents.add(node)
+ blocker = Blocker(atom=myatom[1:], root=myroot)
+ self._blocker_parents.add(blocker, node)
blocker_cache.flush()
del blocker_cache
- for blocker in self.blocker_parents.keys():
+ for blocker in self._blocker_parents.leaf_nodes():
self.spinner.update()
mytype, myroot, mydep = blocker
initial_db = self.trees[myroot]["vartree"].dbapi
@@ -3147,7 +3146,12 @@ class depgraph(object):
blocked_initial = initial_db.match(mydep)
blocked_final = final_db.match(mydep)
if not blocked_initial and not blocked_final:
- del self.blocker_parents[blocker]
+ parent_pkgs = self._blocker_parents.parent_nodes(blocker)
+ self._blocker_parents.remove(blocker)
+ # Discard any parents that don't have any more blockers.
+ for pkg in parent_pkgs:
+ if not self._blocker_parents.child_nodes(pkg):
+ self._blocker_parents.remove(pkg)
continue
blocked_slots_initial = {}
blocked_slots_final = {}
@@ -3159,7 +3163,7 @@ class depgraph(object):
blocked_slots_final[cpv] = \
"%s:%s" % (portage.dep_getkey(cpv),
final_db.aux_get(cpv, ["SLOT"])[0])
- for parent in list(self.blocker_parents[blocker]):
+ for parent in self._blocker_parents.parent_nodes(blocker):
ptype, proot, pcpv, pstatus = parent
pdbapi = self.trees[proot][self.pkg_tree_map[ptype]].dbapi
pslot = pdbapi.aux_get(pcpv, ["SLOT"])[0]
@@ -3237,18 +3241,19 @@ class depgraph(object):
self._pkg_cache[uninst_task] = uninst_task
# Enforce correct merge order with a hard dep.
self.digraph.addnode(uninst_task, inst_task,
- priority=BlockerDepPriority())
+ priority=BlockerDepPriority.instance)
# Count references to this blocker so that it can be
# invalidated after nodes referencing it have been
# merged.
- self.blocker_digraph.addnode(uninst_task, blocker)
+ self._blocker_uninstalls.addnode(uninst_task, blocker)
if not unresolved_blocks and not depends_on_order:
- self.blocker_parents[blocker].remove(parent)
+ self._blocker_parents.remove_edge(blocker, parent)
+ if not self._blocker_parents.parent_nodes(blocker):
+ self._blocker_parents.remove(blocker)
+ if not self._blocker_parents.child_nodes(parent):
+ self._blocker_parents.remove(parent)
if unresolved_blocks:
- self._unresolved_blocker_parents.setdefault(
- blocker, set()).add(parent)
- if not self.blocker_parents[blocker]:
- del self.blocker_parents[blocker]
+ self._unsolvable_blockers.add(blocker, parent)
return True
@@ -3324,7 +3329,7 @@ class depgraph(object):
elif n1_n2_medium:
return 1
return -1
- myblockers = self.blocker_digraph.copy()
+ myblocker_uninstalls = self._blocker_uninstalls.copy()
retlist=[]
# Contains any Uninstall tasks that have been ignored
# in order to avoid the circular deps code path. These
@@ -3333,9 +3338,7 @@ class depgraph(object):
ignored_uninstall_tasks = set()
have_uninstall_task = False
complete = "complete" in self.myparams
- myblocker_parents = self.blocker_parents.copy()
- for k, v in myblocker_parents.iteritems():
- myblocker_parents[k] = v.copy()
+ myblocker_parents = self._blocker_parents.copy()
asap_nodes = []
portage_node = None
def get_nodes(**kwargs):
@@ -3508,13 +3511,13 @@ class depgraph(object):
selected_nodes = list(selected_nodes)
selected_nodes.sort(cmp_circular_bias)
- if not selected_nodes and not myblockers.is_empty():
+ if not selected_nodes and not myblocker_uninstalls.is_empty():
# An Uninstall task needs to be executed in order to
# avoid conflict if possible.
min_parent_deps = None
uninst_task = None
- for task in myblockers.leaf_nodes():
+ for task in myblocker_uninstalls.leaf_nodes():
# Do some sanity checks so that system or world packages
# don't get uninstalled inappropriately here (only really
# necessary when --complete-graph has not been enabled).
@@ -3599,7 +3602,7 @@ class depgraph(object):
# to avoid the circular deps code path, but the
# blocker will still be counted as an unresolved
# conflict.
- for node in myblockers.leaf_nodes():
+ for node in myblocker_uninstalls.leaf_nodes():
try:
mygraph.remove(node)
except KeyError:
@@ -3682,24 +3685,23 @@ class depgraph(object):
pass
if uninst_task is not None and \
uninst_task not in ignored_uninstall_tasks and \
- myblockers.contains(uninst_task):
- myblockers.remove(uninst_task)
- for blocker in myblockers.root_nodes():
- if myblockers.child_nodes(blocker):
- continue
- myblockers.remove(blocker)
- unresolved = \
- self._unresolved_blocker_parents.get(blocker)
- if unresolved:
- myblocker_parents[blocker] = unresolved
- else:
- del myblocker_parents[blocker]
+ myblocker_uninstalls.contains(uninst_task):
+ blocker_nodes = myblocker_uninstalls.parent_nodes(uninst_task)
+ myblocker_uninstalls.remove(uninst_task)
+ # Discard any blockers that this Uninstall solves.
+ for blocker in blocker_nodes:
+ if not myblocker_uninstalls.child_nodes(blocker):
+ myblocker_uninstalls.remove(blocker)
if node[-1] != "nomerge":
retlist.append(list(node))
mygraph.remove(node)
- for blocker in myblocker_parents:
+ unsolvable_blockers = set(self._unsolvable_blockers.leaf_nodes())
+ for node in myblocker_uninstalls.root_nodes():
+ unsolvable_blockers.add(node)
+
+ for blocker in unsolvable_blockers:
retlist.append(list(blocker))
# If any Uninstall tasks need to be executed in order
@@ -3709,7 +3711,7 @@ class depgraph(object):
# are properly identified and blocked from execution).
if have_uninstall_task and \
not complete and \
- not myblocker_parents:
+ not unsolvable_blockers:
self.myparams.add("complete")
raise self._serialize_tasks_retry("")
@@ -3917,7 +3919,7 @@ class depgraph(object):
addl = addl + " " + red(resolved)
else:
addl = "[blocks " + addl + "] " + red(resolved)
- block_parents = self.blocker_parents[tuple(x)]
+ block_parents = self._blocker_parents.parent_nodes(tuple(x))
block_parents = set([pnode[2] for pnode in block_parents])
block_parents = ", ".join(block_parents)
if resolved!=x[2]:
diff --git a/pym/portage/__init__.py b/pym/portage/__init__.py
index edb50fb3f..bd32623a0 100644
--- a/pym/portage/__init__.py
+++ b/pym/portage/__init__.py
@@ -389,6 +389,28 @@ class digraph(object):
del self.nodes[node]
self.order.remove(node)
+ def remove_edge(self, child, parent):
+ """
+ Remove edge in the direction from child to parent. Note that it is
+ possible for a remaining edge to exist in the opposite direction.
+ Any endpoint vertices that become isolated will remain in the graph.
+ """
+
+ # Nothing should be modified when a KeyError is raised.
+ for k in parent, child:
+ if k not in self.nodes:
+ raise KeyError(k)
+
+ # Make sure the edge exists.
+ if child not in self.nodes[parent][0]:
+ raise KeyError(child)
+ if parent not in self.nodes[child][1]:
+ raise KeyError(parent)
+
+ # Remove the edge.
+ del self.nodes[child][1][parent]
+ del self.nodes[parent][0][child]
+
def contains(self, node):
"""Checks if the digraph contains mynode"""
return node in self.nodes