diff -uNr portage.pdepend/bin/emerge portage/bin/emerge --- portage.pdepend/bin/emerge 2006-09-19 20:11:56.000000000 +0000 +++ portage/bin/emerge 2006-09-19 20:24:40.000000000 +0000 @@ -1197,39 +1197,33 @@ return 1 - def altlist(self): + def altlist(self, reversed=False): mygraph=self.digraph.copy() - dolist=["/"] retlist=[] - for x in self.trees.keys(): - self.trees[x]["merge"] = [] - if x not in dolist: - dolist.append(x) - while (not mygraph.empty()): - mycurkey=mygraph.firstzero() - if not mycurkey: - installables = mygraph.leaf_nodes(ignore_soft_deps=True) - if not installables: - print "!!! Error: circular dependencies:" - print - for x in mygraph.allnodes(): - for y in mygraph.parent_nodes(x): - print y,"depends on",x - print - sys.exit(1) - mycurkey = installables[0] - splitski=string.split(mycurkey) - #I'm not sure of the significance of the following lines (vestigal?) so I'm commenting 'em out. - #These lines remove already-merged things from our alt-list - #if "--update" in myopts: - # if not portage.db["/"]["vartree"].exists_specific(splitski[2]): - # portage.db["/"]["merge"].append(splitski) - #else: - self.trees[splitski[1]]["merge"].append(splitski) - mygraph.delnode(mycurkey) - for x in dolist: - for y in self.trees[x]["merge"]: - retlist.append(y) + while not mygraph.empty(): + if reversed: + nodes = mygraph.root_nodes() + if not nodes: + nodes = mygraph.root_nodes(ignore_soft_deps=True) + if nodes: + next_node = nodes[-1] + else: + next_node = None + else: + nodes = mygraph.leaf_nodes() + if not nodes: + nodes = mygraph.leaf_nodes(ignore_soft_deps=True) + if nodes: + next_node = nodes[0] + else: + next_node = None + if not next_node: + print "!!! Error: circular dependencies:" + print + mygraph.debug_print() + sys.exit(1) + retlist.append(next_node.split()) + mygraph.remove(next_node) return retlist def xcreate(self,mode="system"): @@ -1394,29 +1388,33 @@ overlays_real = [os.path.realpath(t) \ for t in self.settings["PORTDIR_OVERLAY"].split()] - if "--tree" in self.myopts: - mylist.reverse() - mygraph=self.digraph.copy() - + tree_nodes = [] + node_depth = {} i = 0 - while i < len(mylist): - if mylist[i][-1]=="nomerge": - if "--tree" not in self.myopts: - # we don't care about this elements - mylist.pop(i) - continue - if (i == (len(mylist) - 1)) \ - or (mygraph.depth(string.join(mylist[i])) \ - >= mygraph.depth(string.join(mylist[i+1]))): - # end of a useless branch (may be the last one) - # -> delete the element and test the previous one - mylist.pop(i) - if i > 0: - i -= 1 - continue - # the branch continues, or we've found a good element. - # -> let's see what's next, if anything - i += 1 + depth = 0 + for x in mylist: + graph_key = " ".join(x) + if "--tree" in self.myopts: + depth = len(tree_nodes) + while depth: + if graph_key in self.digraph.child_nodes(tree_nodes[depth-1]): + break + depth -= 1 + tree_nodes = tree_nodes[:depth] + tree_nodes.append(graph_key) + node_depth[graph_key] = depth + + last_merge_depth = 0 + for i in xrange(len(mylist)-1,-1,-1): + graph_key = " ".join(mylist[i]) + if mylist[i][-1] != "nomerge": + last_merge_depth = node_depth[graph_key] + continue + if node_depth[graph_key] >= last_merge_depth or \ + i != len(mylist)-1 and node_depth[graph_key] >= node_depth[" ".join(mylist[i+1])]: + del mylist[i] + del node_depth[graph_key] + del tree_nodes display_overlays=False # files to fetch list - avoids counting a same file twice @@ -1637,9 +1635,7 @@ oldlp=mywidth-30 newlp=oldlp-30 - indent="" - if "--tree" in self.myopts: - indent=" "*mygraph.depth(string.join(x)) + indent=" "*node_depth[" ".join(x)] if myoldbest: myoldbest=portage.pkgsplit(myoldbest)[1]+"-"+portage.pkgsplit(myoldbest)[2] @@ -3514,7 +3510,7 @@ mydepgraph.display(mymergelist) prompt="Would you like to resume merging these packages?" else: - mydepgraph.display(mydepgraph.altlist()) + mydepgraph.display(mydepgraph.altlist(reversed=("--tree" in myopts))) mergecount=0 for x in mydepgraph.altlist(): if x[3]!="nomerge": @@ -3558,7 +3554,7 @@ sys.exit(0) mydepgraph.display(mymergelist) else: - mydepgraph.display(mydepgraph.altlist()) + mydepgraph.display(mydepgraph.altlist(reversed=("--tree" in myopts))) else: if ("--buildpkgonly" in myopts): if not mydepgraph.digraph.hasallzeros(): diff -uNr portage.pdepend/pym/portage.py portage/pym/portage.py --- portage.pdepend/pym/portage.py 2006-09-19 20:11:56.000000000 +0000 +++ portage/pym/portage.py 2006-09-19 20:15:00.000000000 +0000 @@ -397,6 +397,23 @@ leaf_nodes.append(node) return leaf_nodes + def root_nodes(self, ignore_soft_deps=False): + """Return all nodes that have no children + + If ignore_soft_deps is True, soft deps are not counted as + children in calculations.""" + + root_nodes = [] + for node in self.order: + is_root_node = True + for child in self.nodes[node][1]: + if not (ignore_soft_deps and self.nodes[node][1][child]): + is_root_node = False + break + if is_root_node: + root_nodes.append(node) + return root_nodes + def is_empty(self): """Checks if the digraph is empty""" return len(self.nodes) == 0 @@ -430,29 +447,6 @@ def hasallzeros(self): return len(self.leaf_nodes() == 0) - def depth(self, node): - """Find how many nodes are in the parent chain of the passed node - - This method doesn't make sense unless there is no more than one - parent for each node. As this digraph is capable of having multiple - parents on a node, this implementation chooses an arbitrary parent - for calculations, stopping as soon as a loop is detected in order - to mimic the sorts of counts that would have previously been - returned. - - This method is only used by emerge's --tree option. That option - needs to be reworked to not use this so that this method can be - removed altogether.""" - - parents = {} - while self.nodes[node][1]: - parent = self.nodes[node][1].keys()[0] - if parent in parents: - break - parents[parent] = True - node = parent - return len(parents) - def debug_print(self): for node in self.nodes: print node,