From 429015460241fea04b8f52958a53d023397d0134 Mon Sep 17 00:00:00 2001 From: Zac Medico Date: Mon, 18 Sep 2006 08:31:59 +0000 Subject: [PATCH] Thanks to Jason Stubbs for this patch from bug #147766 which enables creation of a full and complete depgraph, leaving no dependencies unaccounted for. This will allow more accurate merge order and proper detection of circular dependencies! svn path=/main/trunk/; revision=4472 --- bin/emerge | 90 +++++++++--------- pym/portage.py | 248 ++++++++++++++++++++++++++++++++----------------- 2 files changed, 208 insertions(+), 130 deletions(-) diff --git a/bin/emerge b/bin/emerge index 4f52a3200..97ffca2b4 100755 --- a/bin/emerge +++ b/bin/emerge @@ -352,24 +352,18 @@ def create_depgraph_params(myopts, myaction): # recurse: go into the dependencies # deep: go into the dependencies of already merged packages # empty: pretend nothing is merged - myparams=["self","recurse"] + myparams = ["self", "recurse", "selective"] add=[] sub=[] if "--update" in myopts or myaction in ("system", "world"): - add.extend(["selective","empty"]) + add.append("empty") if "--emptytree" in myopts: add.extend(["empty"]) sub.extend(["selective"]) if "--nodeps" in myopts: sub.extend(["recurse"]) - if "--noreplace" in myopts: - add.extend(["selective"]) if "--deep" in myopts: add.extend(["deep"]) - if "--selective" in myopts: - add.extend(["selective"]) - if myaction in ["world","system"]: - add.extend(["selective"]) elif myaction in ["depclean"]: add.extend(["empty"]) sub.extend(["selective"]) @@ -679,7 +673,8 @@ class depgraph: "--getbinpkg" in self.myopts, "--getbinpkgonly" in self.myopts) - def create(self,mybigkey,myparent=None,addme=1,myuse=None): + def create(self, mybigkey, myparent=None, addme=1, myuse=None, + soft_dep=False, arg=None): """ Fills the digraph with nodes comprised of packages to merge. mybigkey is the package spec of the package to merge. @@ -697,10 +692,11 @@ class depgraph: if addme and jbigkey != myparent: # Refuse to make a node depend on itself so that the we don't # don't create a bogus circular dependency in self.altlist(). - self.digraph.addnode(jbigkey, myparent) + self.digraph.addnode(jbigkey, myparent, soft_dep=soft_dep) return 1 jbigkey = " ".join(mybigkey) + " nomerge" if self.digraph.hasnode(jbigkey): + self.digraph.addnode(jbigkey, myparent, soft_dep=soft_dep) return 1 self.spinner.update() @@ -723,7 +719,8 @@ class depgraph: if self.mydbapi[parent_root].match(mykey) or \ self.trees[parent_root]["vartree"].dbapi.match(mykey): mybigkey.append(myparent.split()[2]) - self.digraph.addnode(" ".join(mybigkey), myparent) + self.digraph.addnode(" ".join(mybigkey), myparent, + soft_dep=soft_dep) return 1 else: mydbapi = self.trees[myroot][self.pkg_tree_map[mytype]].dbapi @@ -744,7 +741,7 @@ class depgraph: installed we skip merging it.""" if "self" not in self.myparams or \ ("selective" in self.myparams and \ - vardbapi.cpv_exists(mykey)): + not arg and vardbapi.cpv_exists(mykey)): merging=0 elif "selective" in self.myparams and vardbapi.cpv_exists(mykey): merging=0 @@ -782,7 +779,7 @@ class depgraph: """ At this point, we have either hit a blocker and returned, found the package in the depgraph already and returned, or we are here. Whether we are merging or not; we must add the package to the depgraph; so we do that here. """ - self.digraph.addnode(string.join(mybigkey),myparent) + self.digraph.addnode(" ".join(mybigkey), myparent, soft_dep=soft_dep) """ This section determines whether we go deeper into dependencies or not. We want to go deeper on a few occasions: @@ -815,26 +812,20 @@ class depgraph: """ We have retrieve the dependency information, now we need to recursively process them. DEPEND gets processed for root = "/", {R,P}DEPEND in myroot. """ - mydep={} mp=string.join(mybigkey) try: - if myroot=="/": - mydep["/"]=edepend["DEPEND"]+" "+edepend["RDEPEND"] - if not self.select_dep("/",mydep["/"],myparent=mp,myuse=myuse): - return 0 - else: - mydep["/"]=edepend["DEPEND"] - mydep[myroot]=edepend["RDEPEND"] - if not self.select_dep("/",mydep["/"],myparent=mp,myuse=myuse): - return 0 - if not self.select_dep(myroot,mydep[myroot],myparent=mp,myuse=myuse): - return 0 - + if not self.select_dep("/", edepend["DEPEND"], myparent=mp, + myuse=myuse): + return 0 + if not self.select_dep(myroot,edepend["RDEPEND"], myparent=mp, + myuse=myuse, soft_deps=True): + return 0 if edepend.has_key("PDEPEND") and edepend["PDEPEND"]: # Post Depend -- Add to the list without a parent, as it depends # on a package being present AND must be built after that package. - if not self.select_dep(myroot,edepend["PDEPEND"],myuse=myuse): + if not self.select_dep(myroot, edepend["PDEPEND"], myuse=myuse, + soft_deps=True): return 0 except ValueError, e: pkgs = e.args[0] @@ -940,7 +931,11 @@ class depgraph: sys.stderr.flush() try: - self.mysd = self.select_dep(myroot, mykey, arg=x) + if "--noreplace" in self.myopts: + arg = None + else: + arg = x + self.mysd = self.select_dep(myroot, mykey, arg=arg) except portage_exception.MissingSignature, e: portage.writemsg("\n\n!!! A missing gpg signature is preventing portage from calculating the\n") portage.writemsg("!!! required dependencies. This is a security feature enabled by the admin\n") @@ -969,7 +964,7 @@ class depgraph: missing=0 if "--usepkgonly" in self.myopts: - for x in self.digraph.dict.keys(): + for x in self.digraph.all_nodes(): xs=string.split(x," ") if (xs[0] != "binary") and (xs[3]=="merge"): if missing == 0: @@ -993,7 +988,8 @@ class depgraph: if curslot == myslot: return match - def select_dep(self,myroot,depstring,myparent=None,arg=None,myuse=None,raise_on_missing=False): + def select_dep(self, myroot, depstring, myparent=None, arg=None, + myuse=None, raise_on_missing=False, soft_deps=False): """ Given a depstring, create the depgraph such that all dependencies are satisfied. myroot = $ROOT from environment, where {R,P}DEPENDs are merged to. myparent = the node whose depstring is being passed in @@ -1006,6 +1002,7 @@ class depgraph: portdb = self.trees[myroot]["porttree"].dbapi bindb = self.trees[myroot]["bintree"].dbapi + vardb = self.trees[myroot]["vartree"].dbapi pkgsettings = self.pkgsettings[myroot] if "--debug" in self.myopts: @@ -1020,7 +1017,7 @@ class depgraph: mycheck = portage.dep_check(depstring, self.mydbapi[myroot], pkgsettings, myuse=myuse, use_binaries=("--usepkgonly" in self.myopts), - myroot=myroot, trees=self.trees) + myroot=myroot, trees=self.trees, return_all_deps=True) if not mycheck[0]: mymerge=[] @@ -1056,9 +1053,6 @@ class depgraph: self.pkgsettings[p_root].setinst(p_key, self.trees[p_root][self.pkg_tree_map[p_type]].dbapi) - if not mymerge: - return 1 - if "--debug" in self.myopts: print "Candidates:",mymerge for x in mymerge: @@ -1076,6 +1070,12 @@ class depgraph: selected_pkg = ["blocks", myroot, x[1:], None] else: #We are not processing a blocker but a normal dependency + pkg_key = portage.dep_getkey(x) + if pkg_key in pkgsettings.pprovideddict and \ + portage.match_from_list( + x, pkgsettings.pprovideddict[pkg_key]): + continue + # List of acceptable packages, ordered by type preference. matched_packages = [] myeb_matches = portdb.xmatch("match-visible", x) @@ -1178,15 +1178,16 @@ class depgraph: if myparent: #we are a dependency, so we want to be unconditionally added + soft_dep = soft_deps or vardb.match(x) if not self.create(selected_pkg[0:3], myparent, - myuse=selected_pkg[-1]): + myuse=selected_pkg[-1], soft_dep=soft_dep, arg=arg): return 0 else: #if mysource is not set, then we are a command-line dependency and should not be added #if --onlydeps is specified. if not self.create(selected_pkg[0:3], myparent, addme=("--onlydeps" not in self.myopts), - myuse=selected_pkg[-1]): + myuse=selected_pkg[-1], arg=arg): return 0 if "--debug" in self.myopts: @@ -1205,13 +1206,16 @@ class depgraph: while (not mygraph.empty()): mycurkey=mygraph.firstzero() if not mycurkey: - print "!!! Error: circular dependencies:" - print - for x in mygraph.dict.keys(): - for y in mygraph.dict[x][1]: - print y,"depends on",x - print - sys.exit(1) + 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 diff --git a/pym/portage.py b/pym/portage.py index 551b4441b..86c665114 100644 --- a/pym/portage.py +++ b/pym/portage.py @@ -313,84 +313,161 @@ def flatten(mytokens): class digraph: def __init__(self): - self.dict={} - #okeys = keys, in order they were added (to optimize firstzero() ordering) - self.okeys=[] - - def addnode(self,mykey,myparent): - if not self.dict.has_key(mykey): - self.okeys.append(mykey) - if myparent is None: - self.dict[mykey]=[0,[]] - else: - self.dict[mykey]=[0,[myparent]] - self.dict[myparent][0]=self.dict[myparent][0]+1 - return - if myparent and (not myparent in self.dict[mykey][1]): - self.dict[mykey][1].append(myparent) - self.dict[myparent][0]=self.dict[myparent][0]+1 + """Create an empty digraph""" + + # { node : ( { child : soft_dep } , { parent : soft_dep } ) } + self.nodes = {} + self.order = [] - def delnode(self,mykey): - if not self.dict.has_key(mykey): + def add(self, node, parent, soft_dep=False): + """Adds the specified node with the specified parent. + + If the dep is a soft-dep and the node already has a hard + relationship to the parent, the relationship is left as hard.""" + + if node not in self.nodes: + self.nodes[node] = ({}, {}) + self.order.append(node) + + if not parent: return - for x in self.dict[mykey][1]: - self.dict[x][0]=self.dict[x][0]-1 - del self.dict[mykey] - while 1: - try: - self.okeys.remove(mykey) - except ValueError: - break + + if parent not in self.nodes: + self.nodes[parent] = ({}, {}) + self.order.append(parent) + + if parent in self.nodes[node][1]: + if not soft_dep: + self.nodes[node][1][parent] = False + else: + self.nodes[node][1][parent] = soft_dep + + if node in self.nodes[parent][0]: + if not soft_dep: + self.nodes[parent][0][node] = False + else: + self.nodes[parent][0][node] = soft_dep + + def remove(self, node): + """Removes the specified node from the digraph, also removing + and ties to other nodes in the digraph. Raises KeyError if the + node doesn't exist.""" + + if node not in self.nodes: + raise KeyError(node) + + for parent in self.nodes[node][1]: + del self.nodes[parent][0][node] + for child in self.nodes[node][0]: + del self.nodes[child][1][node] + + del self.nodes[node] + self.order.remove(node) + + def contains(self, node): + """Checks if the digraph contains mynode""" + return node in self.nodes + + def all_nodes(self): + """Return a list of all nodes in the graph""" + return self.order[:] + + def child_nodes(self, node): + """Return all children of the specified node""" + return self.nodes[node][0].keys() + + def parent_nodes(self, node): + """Return all parents of the specified node""" + return self.nodes[node][1].keys() - def allnodes(self): - "returns all nodes in the dictionary" - return self.dict.keys() + def leaf_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.""" + + leaf_nodes = [] + for node in self.order: + is_leaf_node = True + for child in self.nodes[node][0]: + if not (ignore_soft_deps and self.nodes[node][0][child]): + is_leaf_node = False + break + if is_leaf_node: + leaf_nodes.append(node) + return leaf_nodes + + def is_empty(self): + """Checks if the digraph is empty""" + return len(self.nodes) == 0 + + def clone(self): + clone = digraph() + clone.nodes = copy.deepcopy(self.nodes) + clone.order = self.order[:] + return clone + + # Backward compatibility + addnode = add + allnodes = all_nodes + allzeros = leaf_nodes + hasnode = contains + empty = is_empty + copy = clone + + def delnode(self, node): + try: + self.remove(node) + except KeyError: + pass def firstzero(self): - "returns first node with zero references, or NULL if no such node exists" - for x in self.okeys: - if self.dict[x][0]==0: - return x + leaf_nodes = self.leaf_nodes() + if leaf_nodes: + return leaf_nodes[0] return None - def depth(self, mykey): - depth=0 - while (self.dict[mykey][1]): - depth=depth+1 - mykey=self.dict[mykey][1][0] - return depth - - def allzeros(self): - "returns all nodes with zero references, or NULL if no such node exists" - zerolist = [] - for x in self.dict.keys(): - mys = string.split(x) - if mys[0] != "blocks" and self.dict[x][0]==0: - zerolist.append(x) - return zerolist - def hasallzeros(self): - "returns 0/1, Are all nodes zeros? 1 : 0" - zerolist = [] - for x in self.dict.keys(): - if self.dict[x][0]!=0: - return 0 - return 1 + return len(self.leaf_nodes() == 0) - def empty(self): - if len(self.dict)==0: - return 1 - return 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, + if self.nodes[node][0]: + print "depends on" + else: + print "(no children)" + for child in self.nodes[node][0]: + print " ",child, + if self.nodes[node][0][child]: + print "(hard)" + else: + print "(soft)" - def hasnode(self,mynode): - return self.dict.has_key(mynode) - def copy(self): - mygraph=digraph() - for x in self.dict.keys(): - mygraph.dict[x]=self.dict[x][:] - mygraph.okeys=self.okeys[:] - return mygraph def elog_process(cpv, mysettings): mylogfiles = listdir(mysettings["T"]+"/logging/") @@ -3293,7 +3370,8 @@ def dep_eval(deplist): return 0 return 1 -def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None): +def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None, + return_all_deps=False): """Takes an unreduced and reduced deplist and removes satisfied dependencies. Returned deplist contains steps that must be taken to satisfy dependencies.""" if trees is None: @@ -3308,8 +3386,9 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None): for (dep, satisfied) in zip(unreduced, reduced): if isinstance(dep, list): unresolved += dep_zapdeps(dep, satisfied, myroot, - use_binaries=use_binaries, trees=trees) - elif not satisfied: + use_binaries=use_binaries, trees=trees, + return_all_deps=return_all_deps) + elif not satisfied or return_all_deps: unresolved.append(dep) return unresolved @@ -3413,7 +3492,7 @@ def dep_expand(mydep, mydb=None, use_cache=1, settings=None): mydep, mydb=mydb, use_cache=use_cache, settings=settings) + postfix def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None, - use_cache=1, use_binaries=0, myroot="/", trees=None): + use_cache=1, use_binaries=0, myroot="/", trees=None, return_all_deps=False): """Takes a depend string and parses the condition.""" #check_config_instance(mysettings) @@ -3478,23 +3557,18 @@ def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None, writemsg("\n\n\n", 1) writemsg("mysplit: %s\n" % (mysplit), 1) writemsg("mysplit2: %s\n" % (mysplit2), 1) - myeval=dep_eval(mysplit2) - writemsg("myeval: %s\n" % (myeval), 1) - if myeval: - return [1,[]] - else: - myzaps = dep_zapdeps(mysplit, mysplit2, myroot, - use_binaries=use_binaries, trees=trees) - mylist = flatten(myzaps) - writemsg("myzaps: %s\n" % (myzaps), 1) - writemsg("mylist: %s\n" % (mylist), 1) - #remove duplicates - mydict={} - for x in mylist: - mydict[x]=1 - writemsg("mydict: %s\n" % (mydict), 1) - return [1,mydict.keys()] + myzaps = dep_zapdeps(mysplit, mysplit2, myroot, + use_binaries=use_binaries, trees=trees, return_all_deps=return_all_deps) + mylist = flatten(myzaps) + writemsg("myzaps: %s\n" % (myzaps), 1) + writemsg("mylist: %s\n" % (mylist), 1) + #remove duplicates + mydict={} + for x in mylist: + mydict[x]=1 + writemsg("mydict: %s\n" % (mydict), 1) + return [1,mydict.keys()] def dep_wordreduce(mydeplist,mysettings,mydbapi,mode,use_cache=1): "Reduces the deplist to ones and zeros" -- 2.26.2