From 2ac555f3b25262fa6bc1f24a487223b178ecf937 Mon Sep 17 00:00:00 2001 From: Zac Medico Date: Fri, 23 Oct 2009 04:43:44 +0000 Subject: [PATCH] Factor the --tree code out of depgraph.display(). svn path=/main/trunk/; revision=14702 --- pym/_emerge/depgraph.py | 282 +++++++++++++++++++++------------------- 1 file changed, 146 insertions(+), 136 deletions(-) diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py index 54dc5bce1..74f79b3c9 100644 --- a/pym/_emerge/depgraph.py +++ b/pym/_emerge/depgraph.py @@ -3876,6 +3876,7 @@ class depgraph(object): oneshot = "--oneshot" in self._frozen_config.myopts or \ "--onlydeps" in self._frozen_config.myopts columns = "--columns" in self._frozen_config.myopts + tree_display = "--tree" in self._frozen_config.myopts changelogs=[] p=[] blockers = [] @@ -3953,151 +3954,23 @@ class depgraph(object): return ret repo_display = RepoDisplay(self._frozen_config.roots) - - tree_nodes = [] - display_list = [] - mygraph = self._dynamic_config.digraph.copy() - - # If there are any Uninstall instances, add the corresponding - # blockers to the digraph (useful for --tree display). - - executed_uninstalls = set(node for node in mylist \ - if isinstance(node, Package) and node.operation == "unmerge") - - for uninstall in self._dynamic_config._blocker_uninstalls.leaf_nodes(): - uninstall_parents = \ - self._dynamic_config._blocker_uninstalls.parent_nodes(uninstall) - if not uninstall_parents: - continue - - # Remove the corresponding "nomerge" node and substitute - # the Uninstall node. - inst_pkg = self._pkg(uninstall.cpv, "installed", - uninstall.root_config, installed=True) - - try: - mygraph.remove(inst_pkg) - except KeyError: - pass - - try: - inst_pkg_blockers = self._dynamic_config._blocker_parents.child_nodes(inst_pkg) - except KeyError: - inst_pkg_blockers = [] - - # Break the Package -> Uninstall edges. - mygraph.remove(uninstall) - - # Resolution of a package's blockers - # depend on it's own uninstallation. - for blocker in inst_pkg_blockers: - mygraph.add(uninstall, blocker) - - # Expand Package -> Uninstall edges into - # Package -> Blocker -> Uninstall edges. - for blocker in uninstall_parents: - mygraph.add(uninstall, blocker) - for parent in self._dynamic_config._blocker_parents.parent_nodes(blocker): - if parent != inst_pkg: - mygraph.add(blocker, parent) - - # If the uninstall task did not need to be executed because - # of an upgrade, display Blocker -> Upgrade edges since the - # corresponding Blocker -> Uninstall edges will not be shown. - upgrade_node = \ - self._dynamic_config._slot_pkg_map[uninstall.root].get(uninstall.slot_atom) - if upgrade_node is not None and \ - uninstall not in executed_uninstalls: - for blocker in uninstall_parents: - mygraph.add(upgrade_node, blocker) - unsatisfied_blockers = [] - i = 0 - depth = 0 - shown_edges = set() + ordered_nodes = [] for x in mylist: if isinstance(x, Blocker) and not x.satisfied: unsatisfied_blockers.append(x) - continue - graph_key = x - if "--tree" in self._frozen_config.myopts: - depth = len(tree_nodes) - while depth and graph_key not in \ - mygraph.child_nodes(tree_nodes[depth-1]): - depth -= 1 - if depth: - tree_nodes = tree_nodes[:depth] - tree_nodes.append(graph_key) - display_list.append((x, depth, True)) - shown_edges.add((graph_key, tree_nodes[depth-1])) - else: - traversed_nodes = set() # prevent endless circles - traversed_nodes.add(graph_key) - def add_parents(current_node, ordered): - parent_nodes = None - # Do not traverse to parents if this node is an - # an argument or a direct member of a set that has - # been specified as an argument (system or world). - if current_node not in self._dynamic_config._set_nodes: - parent_nodes = mygraph.parent_nodes(current_node) - if parent_nodes: - child_nodes = set(mygraph.child_nodes(current_node)) - selected_parent = None - # First, try to avoid a direct cycle. - for node in parent_nodes: - if not isinstance(node, (Blocker, Package)): - continue - if node not in traversed_nodes and \ - node not in child_nodes: - edge = (current_node, node) - if edge in shown_edges: - continue - selected_parent = node - break - if not selected_parent: - # A direct cycle is unavoidable. - for node in parent_nodes: - if not isinstance(node, (Blocker, Package)): - continue - if node not in traversed_nodes: - edge = (current_node, node) - if edge in shown_edges: - continue - selected_parent = node - break - if selected_parent: - shown_edges.add((current_node, selected_parent)) - traversed_nodes.add(selected_parent) - add_parents(selected_parent, False) - display_list.append((current_node, - len(tree_nodes), ordered)) - tree_nodes.append(current_node) - tree_nodes = [] - add_parents(graph_key, True) else: - display_list.append((x, depth, True)) + ordered_nodes.append(x) + + if tree_display: + display_list = self._tree_display(ordered_nodes) + else: + display_list = [(x, 0, True) for x in ordered_nodes] + mylist = display_list for x in unsatisfied_blockers: mylist.append((x, 0, True)) - last_merge_depth = 0 - for i in range(len(mylist)-1,-1,-1): - graph_key, depth, ordered = mylist[i] - if not ordered and depth == 0 and i > 0 \ - and graph_key == mylist[i-1][0] and \ - mylist[i-1][1] == 0: - # An ordered node got a consecutive duplicate when the tree was - # being filled in. - del mylist[i] - continue - if ordered and graph_key[-1] != "nomerge": - last_merge_depth = depth - continue - if depth >= last_merge_depth or \ - i < len(mylist) - 1 and \ - depth >= mylist[i+1][1]: - del mylist[i] - # files to fetch list - avoids counting a same file twice # in size display (verbose mode) myfetchlist=[] @@ -4605,6 +4478,143 @@ class depgraph(object): sys.stdout.flush() return os.EX_OK + def _tree_display(self, mylist): + + # If there are any Uninstall instances, add the + # corresponding blockers to the digraph. + mygraph = self._dynamic_config.digraph.copy() + + executed_uninstalls = set(node for node in mylist \ + if isinstance(node, Package) and node.operation == "unmerge") + + for uninstall in self._dynamic_config._blocker_uninstalls.leaf_nodes(): + uninstall_parents = \ + self._dynamic_config._blocker_uninstalls.parent_nodes(uninstall) + if not uninstall_parents: + continue + + # Remove the corresponding "nomerge" node and substitute + # the Uninstall node. + inst_pkg = self._pkg(uninstall.cpv, "installed", + uninstall.root_config, installed=True) + + try: + mygraph.remove(inst_pkg) + except KeyError: + pass + + try: + inst_pkg_blockers = self._dynamic_config._blocker_parents.child_nodes(inst_pkg) + except KeyError: + inst_pkg_blockers = [] + + # Break the Package -> Uninstall edges. + mygraph.remove(uninstall) + + # Resolution of a package's blockers + # depend on it's own uninstallation. + for blocker in inst_pkg_blockers: + mygraph.add(uninstall, blocker) + + # Expand Package -> Uninstall edges into + # Package -> Blocker -> Uninstall edges. + for blocker in uninstall_parents: + mygraph.add(uninstall, blocker) + for parent in self._dynamic_config._blocker_parents.parent_nodes(blocker): + if parent != inst_pkg: + mygraph.add(blocker, parent) + + # If the uninstall task did not need to be executed because + # of an upgrade, display Blocker -> Upgrade edges since the + # corresponding Blocker -> Uninstall edges will not be shown. + upgrade_node = \ + self._dynamic_config._slot_pkg_map[uninstall.root].get(uninstall.slot_atom) + if upgrade_node is not None and \ + uninstall not in executed_uninstalls: + for blocker in uninstall_parents: + mygraph.add(upgrade_node, blocker) + + depth = 0 + shown_edges = set() + tree_nodes = [] + display_list = [] + + for x in mylist: + depth = len(tree_nodes) + while depth and x not in \ + mygraph.child_nodes(tree_nodes[depth-1]): + depth -= 1 + if depth: + tree_nodes = tree_nodes[:depth] + tree_nodes.append(x) + display_list.append((x, depth, True)) + shown_edges.add((x, tree_nodes[depth-1])) + else: + traversed_nodes = set() # prevent endless circles + traversed_nodes.add(x) + def add_parents(current_node, ordered): + parent_nodes = None + # Do not traverse to parents if this node is an + # an argument or a direct member of a set that has + # been specified as an argument (system or world). + if current_node not in self._dynamic_config._set_nodes: + parent_nodes = mygraph.parent_nodes(current_node) + if parent_nodes: + child_nodes = set(mygraph.child_nodes(current_node)) + selected_parent = None + # First, try to avoid a direct cycle. + for node in parent_nodes: + if not isinstance(node, (Blocker, Package)): + continue + if node not in traversed_nodes and \ + node not in child_nodes: + edge = (current_node, node) + if edge in shown_edges: + continue + selected_parent = node + break + if not selected_parent: + # A direct cycle is unavoidable. + for node in parent_nodes: + if not isinstance(node, (Blocker, Package)): + continue + if node not in traversed_nodes: + edge = (current_node, node) + if edge in shown_edges: + continue + selected_parent = node + break + if selected_parent: + shown_edges.add((current_node, selected_parent)) + traversed_nodes.add(selected_parent) + add_parents(selected_parent, False) + display_list.append((current_node, + len(tree_nodes), ordered)) + tree_nodes.append(current_node) + tree_nodes = [] + add_parents(x, True) + + last_merge_depth = 0 + for i in range(len(display_list) - 1, -1, -1): + node, depth, ordered = display_list[i] + if not ordered and depth == 0 and i > 0 \ + and node == display_list[i-1][0] and \ + display_list[i-1][1] == 0: + # An ordered node got a consecutive duplicate + # when the tree was being filled in. + del display_list[i] + continue + if ordered and isinstance(node, Package) \ + and node.operation == 'merge': + last_merge_depth = depth + continue + if depth >= last_merge_depth or \ + i < len(display_list) - 1 and \ + depth >= display_list[i+1][1]: + del display_list[i] + + return display_list + def display_problems(self): """ Display problems with the dependency graph such as slot collisions. -- 2.26.2