From 38fc97f83f41cf92ac4bb11b718ec098c4762802 Mon Sep 17 00:00:00 2001 From: Zac Medico Date: Tue, 30 Oct 2007 21:25:29 +0000 Subject: [PATCH] Implement a "consistent" depgraph parameter (enabled by --consistent) that can be used ensure that installation of new packages does not break any deep dependencies of required sets (args, system, or world). Unfortunately, the performance penalty for small dep calculations is too great to enable this parameter by default. At least it will be useful for testing backtracking behavior when that is implemented. svn path=/main/trunk/; revision=8341 --- pym/_emerge/__init__.py | 155 ++++++++++++++++++++++++++++++++++++++-- 1 file changed, 151 insertions(+), 4 deletions(-) diff --git a/pym/_emerge/__init__.py b/pym/_emerge/__init__.py index 2d97624ef..28e52a7ef 100644 --- a/pym/_emerge/__init__.py +++ b/pym/_emerge/__init__.py @@ -188,6 +188,7 @@ options=[ "--ask", "--alphabetical", "--buildpkg", "--buildpkgonly", "--changelog", "--columns", +"--consistent", "--debug", "--deep", "--digest", "--emptytree", @@ -364,6 +365,9 @@ 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 + # consistent: ensure that installation of new packages does not break + # any deep dependencies of required sets (args, system, or + # world). myparams = set(["recurse"]) if "--update" in myopts or \ "--newuse" in myopts or \ @@ -377,6 +381,8 @@ def create_depgraph_params(myopts, myaction): myparams.discard("recurse") if "--deep" in myopts: myparams.add("deep") + if "--consistent" in myopts: + myparams.add("consistent") return myparams @@ -1098,6 +1104,9 @@ class depgraph(object): # Contains a filtered view of preferred packages that are selected # from available repositories. self._filtered_trees = {} + # Contains installed packages and new packages that have been added + # to the graph. + self._graph_trees = {} for myroot in trees: self.trees[myroot] = {} for tree in ("porttree", "bintree"): @@ -1125,6 +1134,12 @@ class depgraph(object): fakedb.cpv_inject(pkg, metadata=dict(izip(self._mydbapi_keys, vardb.aux_get(pkg, self._mydbapi_keys)))) + def graph_tree(): + pass + graph_tree.dbapi = fakedb + self._graph_trees[myroot] = {} + self._graph_trees[myroot]["porttree"] = graph_tree + self._graph_trees[myroot]["vartree"] = self.trees[myroot]["vartree"] del vardb, fakedb self._filtered_trees[myroot] = {} self._filtered_trees[myroot]["vartree"] = self.trees[myroot]["vartree"] @@ -1181,6 +1196,11 @@ class depgraph(object): self._pprovided_args = [] self._missing_args = [] self._dep_stack = [] + self._unsatisfied_deps = [] + self._required_set_names = set(["args", "system", "world"]) + self._select_atoms = self._select_atoms_highest_available + self._select_package = self._select_pkg_highest_available + self._required_set_missing_atoms = set() def _show_slot_collision_notice(self, packages): """Show an informational message advising the user to mask one of the @@ -1253,7 +1273,7 @@ class depgraph(object): return flags return None - def _create_graph(self): + def _create_graph(self, allow_unsatisfied=False): debug = "--debug" in self.myopts buildpkgonly = "--buildpkgonly" in self.myopts nodeps = "--nodeps" in self.myopts @@ -1279,6 +1299,9 @@ class depgraph(object): continue dep_pkg, existing_node = self._select_package(dep.root, dep.atom) if not dep_pkg: + if allow_unsatisfied: + self._unsatisfied_deps.append(dep) + continue self._show_unsatisfied_dep(dep.root, dep.atom, myparent=dep.parent.digraph_node) return 0 @@ -1811,6 +1834,9 @@ class depgraph(object): missing += 1 print "Missing binary for:",xs[2] + if not self._complete_graph(): + return False, myfavorites + if not self.validate_blockers(): return False, myfavorites @@ -1943,8 +1969,17 @@ class depgraph(object): if atom_populated: break - def _select_atoms(self, root, depstring, myuse=None, strict=True, - trees=None): + def _select_atoms_from_graph(self, *pargs, **kwargs): + """ + Prefer atoms matching packages that have already been + added to the graph or those that are installed and have + not been scheduled for replacement. + """ + kwargs["trees"] = self._graph_trees + return self._select_atoms_highest_available(*pargs, **kwargs) + + def _select_atoms_highest_available(self, root, depstring, + myuse=None, strict=True, trees=None): """This will raise InvalidDependString if necessary. If trees is None then self._filtered_trees is used.""" pkgsettings = self.pkgsettings[root] @@ -2061,7 +2096,7 @@ class depgraph(object): print xfrom print - def _select_package(self, root, atom, onlydeps=False): + def _select_pkg_highest_available(self, root, atom, onlydeps=False): pkgsettings = self.pkgsettings[root] dbs = self._filtered_trees[root]["dbs"] vardb = self.roots[root].trees["vartree"].dbapi @@ -2250,6 +2285,106 @@ class depgraph(object): # ordered by type preference ("ebuild" type is the last resort) return matched_packages[-1], existing_node + def _select_pkg_from_graph(self, root, atom, onlydeps=False): + """ + Select packages that have already been added to the graph or + those that are installed and have not been scheduled for + replacement. + """ + graph_db = self._graph_trees[root]["porttree"].dbapi + matches = graph_db.match(atom) + if not matches: + return None, None + cpv = matches[-1] # highest match + slot_atom = "%s:%s" % (portage.cpv_getkey(cpv), + graph_db.aux_get(cpv, ["SLOT"])[0]) + e_pkg = self._slot_pkg_map[root].get(slot_atom) + if e_pkg: + return e_pkg, e_pkg.digraph_node + metadata = dict(izip(self._mydbapi_keys, + graph_db.aux_get(cpv, self._mydbapi_keys))) + pkg = Package(cpv=cpv, built=True, + installed=True, type_name="installed", + metadata=metadata, root=root) + return pkg, None + + def _complete_graph(self): + """ + Add any deep dependencies of required sets (args, system, world) that + have not been pulled into the graph yet. This ensures that the graph + is consistent such that initially satisfied deep dependencies are not + broken in the new graph. Initially unsatisfied dependencies are + irrelevant since we only want to avoid breaking dependencies that are + intially satisfied. + + Since this method can consume enough time to disturb users, it is + currently only enabled by the --consistent option. + """ + if "consistent" not in self.myparams: + # Skip this to avoid consuming enough time to disturb users. + return 1 + + if "--buildpkgonly" in self.myopts or \ + "recurse" not in self.myparams: + return 1 + + # Put the depgraph into a mode that causes it to only + # select packages that have already been added to the + # graph or those that are installed and have not been + # scheduled for replacement. Also, toggle the "deep" + # parameter so that all dependencies are traversed and + # accounted for. + self._select_atoms = self._select_atoms_from_graph + self._select_package = self._select_pkg_from_graph + self.myparams.add("deep") + + for root in self.roots: + required_set_names = self._required_set_names.copy() + if root == self.target_root and \ + ("deep" in self.myparams or "empty" in self.myparams): + required_set_names.difference_update(self._sets) + if not required_set_names: + continue + setconfig = self.roots[root].settings.setconfig + required_set_atoms = set() + for s in required_set_names: + if s == "args": + required_set_atoms.update(self._sets["args"]) + else: + required_set_atoms.update(setconfig.getSetAtoms(s)) + vardb = self.roots[root].trees["vartree"].dbapi + for atom in required_set_atoms: + self._dep_stack.append( + Dependency(atom=atom, depth=0, + priority=DepPriority(), root=root)) + if not self._create_graph(allow_unsatisfied=True): + return 0 + # Check the unsatisfied deps to see if any initially satisfied deps + # will become unsatisfied due to an upgrade. Initially unsatisfied + # deps are irrelevant since we only want to avoid breaking deps + # that are initially satisfied. + while self._unsatisfied_deps: + dep = self._unsatisfied_deps.pop() + matches = vardb.match(dep.atom) + if not matches: + # Initially unsatisfied. + continue + # An scheduled installation broke a deep dependency. + # Add the installed package to the graph so that it + # will be appropriately reported as a slot collision + # (possibly solvable via backtracking). + cpv = matches[-1] # highest match + metadata = dict(izip(self._mydbapi_keys, + vardb.aux_get(cpv, self._mydbapi_keys))) + pkg = Package(type_name="installed", root=root, + cpv=cpv, metadata=metadata, built=True, + installed=True) + if not self._add_pkg(pkg, myparent=dep.parent): + return 0 + if not self._create_graph(allow_unsatisfied=True): + return 0 + return 1 + def validate_blockers(self): """Remove any blockers from the digraph that do not match any of the packages within the graph. If necessary, create hard deps to ensure @@ -2508,6 +2643,18 @@ class depgraph(object): self._altlist_cache[reversed] = retlist[:] return retlist mygraph=self.digraph.copy() + # Prune "nomerge" root nodes if nothing depends on them, since + # otherwise they slow down merge order calculation. Don't remove + # non-root nodes since they help optimize merge order in some cases + # such as revdep-rebuild. + while True: + removed_something = False + for node in mygraph.root_nodes(): + if node[-1] == "nomerge": + mygraph.remove(node) + removed_something = True + if not removed_something: + break self._merge_order_bias(mygraph) myblockers = self.blocker_digraph.copy() retlist=[] -- 2.26.2