Attachment #196212 for bug #275217

View | Details | Raw Unified | Return to bug 275217 | Differences between
Collapse All | Expand All




from _emerge.UnmergeDepPriority import UnmergeDepPriority
from _emerge.visible import visible

class _frozen_depgraph_config(object):

	def __init__(self, settings, trees, myopts, spinner, dynamic_config, depgraph):

	_dep_keys = ["DEPEND", "RDEPEND", "PDEPEND"]

	def __init__(self, settings, trees, myopts, myparams, spinner):
		self.settings = settings
		self.target_root = settings["ROOT"]
		self.myopts = myopts
		self.myparams = myparams
		self.edebug = 0
		if settings.get("PORTAGE_DEBUG", "") == "1":
			self.edebug = 1

		self._opts_no_restart = frozenset(["--buildpkgonly",
			"--fetchonly", "--fetch-all-uri", "--pretend"])
		self.pkgsettings = {}
		# Maps slot atom to package for each Package added to the graph.
		self._slot_pkg_map = {}
		# Maps nodes to the reasons they were selected for reinstallation.
		self._reinstall_nodes = {}
		self.mydbapi = {}
		self.trees = {}
		self._trees_orig = trees
		self.roots = {}
		# 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 = {}
		# All Package instances
		self._pkg_cache = {}
		for myroot in trees:
			self.trees[myroot] = {}
			# Create a RootConfig instance that references

				self.trees[myroot][tree] = trees[myroot][tree]
			self.trees[myroot]["vartree"] = \
				FakeVartree(trees[myroot]["root_config"],
					pkg_cache=dynamic_config._pkg_cache)
			self.pkgsettings[myroot] = portage.config(
				clone=self.trees[myroot]["vartree"].settings)
			dynamic_config._slot_pkg_map[myroot] = {}
			vardb = self.trees[myroot]["vartree"].dbapi
			preload_installed_pkgs = "--nodeps" not in self.myopts and \
				"--buildpkgonly" not in self.myopts

			trees[myroot]["vartree"].dbapi._clear_cache()
			gc.collect()

			dynamic_config.mydbapi[myroot] = fakedb
			def graph_tree():
				pass
			graph_tree.dbapi = fakedb
			self._graph_trees[myroot] = {}
			dynamic_config._filtered_trees[myroot] = {}
			# Substitute the graph tree for the vartree in dep_check() since we
			# want atom selections to be consistent with package selections
			# have already been made.

			self._graph_trees[myroot]["vartree"]    = graph_tree
			def filtered_tree():
				pass
			filtered_tree.dbapi = _dep_check_composite_db(depgraph, myroot)
			dynamic_config._filtered_trees[myroot]["porttree"] = filtered_tree

			# Passing in graph_tree as the vartree here could lead to better
			# atom selections in some cases by causing atoms for packages that

			# the parent package into self._select_atoms() calls so that
			# unresolvable direct circular dependencies can be detected and
			# avoided when possible.
			dynamic_config._filtered_trees[myroot]["graph_db"] = graph_tree.dbapi
			dynamic_config._filtered_trees[myroot]["vartree"] = self.trees[myroot]["vartree"]

			dbs = []
			portdb = self.trees[myroot]["porttree"].dbapi

				dbs.append((bindb,  "binary", True, False, db_keys))
			db_keys = list(trees[myroot]["vartree"].dbapi._aux_cache_keys)
			dbs.append((vardb, "installed", True, True, db_keys))
			dynamic_config._filtered_trees[myroot]["dbs"] = dbs
			if "--usepkg" in self.myopts:
				self.trees[myroot]["bintree"].populate(
					"--getbinpkg" in self.myopts,
					"--getbinpkgonly" in self.myopts)
		del trees

		self._required_set_names = set(["system", "world"])

class _dynamic_depgraph_config(object):

	def __init__(self, myparams):
		self.myparams = myparams
		# Maps slot atom to package for each Package added to the graph.
		self._slot_pkg_map = {}
		# Maps nodes to the reasons they were selected for reinstallation.
		self._reinstall_nodes = {}
		self.mydbapi = {}
		# Contains a filtered view of preferred packages that are selected
		# from available repositories.
		self._filtered_trees = {}
		# All Package instances
		self._pkg_cache = {}
		#contains the args created by select_files
		self._initial_arg_list = []
		self.digraph = portage.digraph()
		# contains all sets added to the graph
		self._sets = {}
		# contains atoms given as arguments

		self._unsatisfied_deps = []
		self._initially_unsatisfied_deps = []
		self._ignored_deps = []
		self._highest_pkg_cache = {}


class depgraph(object):

	pkg_tree_map = RootConfig.pkg_tree_map

	_dep_keys = ["DEPEND", "RDEPEND", "PDEPEND"]
	
	def __init__(self, settings, trees, myopts, myparams, spinner):	
		self._dynamic_config = _dynamic_depgraph_config(myparams)
		self._frozen_config = _frozen_depgraph_config(settings, trees, \
			myopts, spinner, self._dynamic_config, self)
		
		self._select_atoms = self._select_atoms_highest_available
		self._select_package = self._select_pkg_highest_available
		self._highest_pkg_cache = {}

	def _show_slot_collision_notice(self):
		"""Show an informational message advising the user to mask one of the

		cases.
		"""

		if not self._dynamic_config._slot_collision_info:
			return

		self._show_merge_list()

		explanation_columns = 70
		explanations = 0
		for (slot_atom, root), slot_nodes \
			in self._dynamic_config._slot_collision_info.iteritems():
			msg.append(str(slot_atom))
			msg.append("\n\n")

			for node in slot_nodes:
				msg.append(indent)
				msg.append(str(node))
				parent_atoms = self._dynamic_config._parent_atoms.get(node)
				if parent_atoms:
					pruned_list = set()
					# Prefer conflict atoms over others.
					for parent_atom in parent_atoms:
						if len(pruned_list) >= max_parents:
							break
						if parent_atom in self._dynamic_config._slot_conflict_parent_atoms:
							pruned_list.add(parent_atom)

					# If this package was pulled in by conflict atoms then

							parent, atom = parent_atom
							if isinstance(parent, Package) and \
								(parent.slot_atom, parent.root) \
								in self._dynamic_config._slot_collision_info:
								pruned_list.add(parent_atom)
						for parent_atom in parent_atoms:
							if len(pruned_list) >= max_parents:

		sys.stderr.write("".join(msg))
		sys.stderr.flush()

		explanations_for_all = explanations == len(self._dynamic_config._slot_collision_info)

		if explanations_for_all or "--quiet" in self._frozen_config.myopts:
			return

		msg = []

			# conflicts between two packages.
			return None

		all_conflict_atoms = self._dynamic_config._slot_conflict_parent_atoms
		matched_node = None
		matched_atoms = None
		unmatched_node = None
		for node in slot_nodes:
			parent_atoms = self._dynamic_config._parent_atoms.get(node)
			if not parent_atoms:
				# Normally, there are always parent atoms. If there are
				# none then something unexpected is happening and there's

		packages that have been pulled into a given slot.
		"""
		for (slot_atom, root), slot_nodes \
			in self._dynamic_config._slot_collision_info.iteritems():

			all_parent_atoms = set()
			for pkg in slot_nodes:
				parent_atoms = self._dynamic_config._parent_atoms.get(pkg)
				if not parent_atoms:
					continue
				all_parent_atoms.update(parent_atoms)

			for pkg in slot_nodes:
				parent_atoms = self._dynamic_config._parent_atoms.get(pkg)
				if parent_atoms is None:
					parent_atoms = set()
					self._dynamic_config._parent_atoms[pkg] = parent_atoms
				for parent_atom in all_parent_atoms:
					if parent_atom in parent_atoms:
						continue

					if atom_set.findAtomForPackage(pkg):
						parent_atoms.add(parent_atom)
					else:
						self._dynamic_config._slot_conflict_parent_atoms.add(parent_atom)

	def _reinstall_for_flags(self, forced_flags,
		orig_use, orig_iuse, cur_use, cur_iuse):
		"""Return a set of flags that trigger reinstallation, or None if there
		are no such flags."""
		if "--newuse" in self._frozen_config.myopts:
			flags = set(orig_iuse.symmetric_difference(
				cur_iuse).difference(forced_flags))
			flags.update(orig_iuse.intersection(orig_use).symmetric_difference(
				cur_iuse.intersection(cur_use)))
			if flags:
				return flags
		elif "changed-use" == self._frozen_config.myopts.get("--reinstall"):
			flags = orig_iuse.intersection(orig_use).symmetric_difference(
				cur_iuse.intersection(cur_use))
			if flags:

		return None

	def _create_graph(self, allow_unsatisfied=False):
		dep_stack = self._dynamic_config._dep_stack
		dep_disjunctive_stack = self._dynamic_config._dep_disjunctive_stack
		while dep_stack or dep_disjunctive_stack:
			self._frozen_config.spinner.update()
			while dep_stack:
				dep = dep_stack.pop()
				if isinstance(dep, Package):

		return 1

	def _add_dep(self, dep, allow_unsatisfied=False):
		debug = "--debug" in self._frozen_config.myopts
		buildpkgonly = "--buildpkgonly" in self._frozen_config.myopts
		nodeps = "--nodeps" in self._frozen_config.myopts
		empty = "empty" in self._dynamic_config.myparams
		deep = "deep" in self._dynamic_config.myparams
		update = "--update" in self._frozen_config.myopts and dep.depth <= 1
		if dep.blocker:
			if not buildpkgonly and \
				not nodeps and \
				dep.parent not in self._dynamic_config._slot_collision_nodes:
				if dep.parent.onlydeps:
					# It's safe to ignore blockers if the
					# parent is an --onlydeps node.

				blocker = Blocker(atom=dep.atom,
					eapi=dep.parent.metadata["EAPI"],
					root=dep.parent.root)
				self._dynamic_config._blocker_parents.add(blocker, dep.parent)
			return 1
		dep_pkg, existing_node = self._select_package(dep.root, dep.atom,
			onlydeps=dep.onlydeps)

				# pulled in by --with-bdeps=y.
				return 1
			if allow_unsatisfied:
				self._dynamic_config._unsatisfied_deps.append(dep)
				return 1
			self._dynamic_config._unsatisfied_deps_for_display.append(
				((dep.root, dep.atom), {"myparent":dep.parent}))
			return 0
		# In some cases, dep_check will return deps that shouldn't

			not dep_pkg.installed and \
			not (existing_node or empty or deep or update):
			myarg = None
			if dep.root == self._frozen_config.target_root:
				try:
					myarg = self._iter_atoms_for_pkg(dep_pkg).next()
				except StopIteration:

						# should have been masked.
						raise
			if not myarg:
				self._dynamic_config._ignored_deps.append(dep)
				return 1

		if not self._add_pkg(dep_pkg, dep):

		"""
		# Ensure that the dependencies of the same package
		# are never processed more than once.
		previously_added = pkg in self._dynamic_config.digraph

		# select the correct /var database that we'll be checking against
		vardbapi = self._frozen_config.trees[pkg.root]["vartree"].dbapi
		pkgsettings = self._frozen_config.pkgsettings[pkg.root]

		arg_atoms = None
		if True:


		if not pkg.onlydeps:
			if not pkg.installed and \
				"empty" not in self._dynamic_config.myparams and \
				vardbapi.match(pkg.slot_atom):
				# Increase the priority of dependencies on packages that
				# are being rebuilt. This optimizes merge order so that

				# are being merged in that case.
				priority.rebuild = True

			existing_node = self._dynamic_config._slot_pkg_map[pkg.root].get(pkg.slot_atom)
			slot_collision = False
			if existing_node:
				existing_node_matches = pkg.cpv == existing_node.cpv

					if arg_atoms:
						for parent_atom in arg_atoms:
							parent, atom = parent_atom
							self._dynamic_config.digraph.add(existing_node, parent,
								priority=priority)
							self._add_parent_atom(existing_node, parent_atom)
					# If a direct circular dependency is not an unsatisfied

					# way.
					if existing_node != myparent or \
						(priority.buildtime and not priority.satisfied):
						self._dynamic_config.digraph.addnode(existing_node, myparent,
							priority=priority)
						if dep.atom is not None and dep.parent is not None:
							self._add_parent_atom(existing_node,

				# only being partially added to the graph.  It must not be
				# allowed to interfere with the other nodes that have been
				# added.  Do not overwrite data for existing nodes in
				# self._dynamic_config.mydbapi since that data will be used for blocker
				# validation.
				# Even though the graph is now invalid, continue to process
				# dependencies so that things like --fetchonly can still
				# function despite collisions.
				pass
			elif not previously_added:
				self._dynamic_config._slot_pkg_map[pkg.root][pkg.slot_atom] = pkg
				self._dynamic_config.mydbapi[pkg.root].cpv_inject(pkg)
				self._dynamic_config._filtered_trees[pkg.root]["porttree"].dbapi._clear_cache()

			if not pkg.installed:
				# Allow this package to satisfy old-style virtuals in case it

				try:
					pkgsettings.setinst(pkg.cpv, pkg.metadata)
					# For consistency, also update the global virtuals.
					settings = self._frozen_config.roots[pkg.root].settings
					settings.unlock()
					settings.setinst(pkg.cpv, pkg.metadata)
					settings.lock()

					return 0

		if arg_atoms:
			self._dynamic_config._set_nodes.add(pkg)

		# Do this even when addme is False (--onlydeps) so that the
		# parent/child relationship is always known in case
		# self._show_slot_collision_notice() needs to be called later.
		self._dynamic_config.digraph.add(pkg, myparent, priority=priority)
		if dep.atom is not None and dep.parent is not None:
			self._add_parent_atom(pkg, (dep.parent, dep.atom))

		if arg_atoms:
			for parent_atom in arg_atoms:
				parent, atom = parent_atom
				self._dynamic_config.digraph.add(pkg, parent, priority=priority)
				self._add_parent_atom(pkg, parent_atom)

		""" This section determines whether we go deeper into dependencies or not.

		    emerge --deep <pkgspec>; we need to recursively check dependencies of pkgspec
		    If we are in --nodeps (no recursion) mode, we obviously only check 1 level of dependencies.
		"""
		dep_stack = self._dynamic_config._dep_stack
		if "recurse" not in self._dynamic_config.myparams:
			return 1
		elif pkg.installed and \
			"deep" not in self._dynamic_config.myparams:
			dep_stack = self._dynamic_config._ignored_deps

		self._frozen_config.spinner.update()

		if arg_atoms:
			depth = 0

		return 1

	def _add_parent_atom(self, pkg, parent_atom):
		parent_atoms = self._dynamic_config._parent_atoms.get(pkg)
		if parent_atoms is None:
			parent_atoms = set()
			self._dynamic_config._parent_atoms[pkg] = parent_atoms
		parent_atoms.add(parent_atom)

	def _add_slot_conflict(self, pkg):
		self._dynamic_config._slot_collision_nodes.add(pkg)
		slot_key = (pkg.slot_atom, pkg.root)
		slot_nodes = self._dynamic_config._slot_collision_info.get(slot_key)
		if slot_nodes is None:
			slot_nodes = set()
			slot_nodes.add(self._dynamic_config._slot_pkg_map[pkg.root][pkg.slot_atom])
			self._dynamic_config._slot_collision_info[slot_key] = slot_nodes
		slot_nodes.add(pkg)

	def _add_pkg_deps(self, pkg, allow_unsatisfied=False):

		myuse = pkg.use.enabled
		jbigkey = pkg
		depth = pkg.depth + 1
		removal_action = "remove" in self._dynamic_config.myparams

		edepend={}
		depkeys = ["DEPEND","RDEPEND","PDEPEND"]

			edepend[k] = metadata[k]

		if not pkg.built and \
			"--buildpkgonly" in self._frozen_config.myopts and \
			"deep" not in self._dynamic_config.myparams and \
			"empty" not in self._dynamic_config.myparams:
			edepend["RDEPEND"] = ""
			edepend["PDEPEND"] = ""
		bdeps_optional = False

		if pkg.built and not removal_action:
			if self._frozen_config.myopts.get("--with-bdeps", "n") == "y":
				# Pull in build time deps as requested, but marked them as
				# "optional" since they are not strictly required. This allows
				# more freedom in the merge order calculation for solving

				# built packages do not have build time dependencies.
				edepend["DEPEND"] = ""

		if removal_action and self._frozen_config.myopts.get("--with-bdeps", "y") == "n":
			edepend["DEPEND"] = ""

		bdeps_root = "/"
		root_deps = self._frozen_config.myopts.get("--root-deps")
		if root_deps is not None:
			if root_deps is True:
				bdeps_root = myroot

			(myroot, edepend["PDEPEND"], self._priority(runtime_post=True))
		)

		debug = "--debug" in self._frozen_config.myopts
		strict = mytype != "installed"
		try:
			if not strict:

					"!!! This binary package cannot be installed: '%s'\n" % \
					mykey, noiselevel=-1)
			elif mytype == "ebuild":
				portdb = self._frozen_config.roots[myroot].trees["porttree"].dbapi
				myebuild, mylocation = portdb.findname2(mykey)
				portage.writemsg("!!! This ebuild cannot be installed: " + \
					"'%s'\n" % myebuild, noiselevel=-1)

	def _add_pkg_dep_string(self, pkg, dep_root, dep_priority, dep_string,
		allow_unsatisfied):
		depth = pkg.depth + 1
		debug = "--debug" in self._frozen_config.myopts
		strict = pkg.type_name != "installed"

		if debug:

		if debug:
			print "Candidates:", selected_atoms

		vardb = self._frozen_config.roots[dep_root].trees["vartree"].dbapi

		for atom in selected_atoms:
			try:


	def _queue_disjunctive_deps(self, pkg, dep_root, dep_priority, dep_struct):
		"""
		Queue disjunctive (virtual and ||) deps in self._dynamic_config._dep_disjunctive_stack.
		Yields non-disjunctive deps. Raises InvalidDependString when 
		necessary.
		"""

			i += 1

	def _queue_disjunction(self, pkg, dep_root, dep_priority, dep_struct):
		self._dynamic_config._dep_disjunctive_stack.append(
			(pkg, dep_root, dep_priority, dep_struct))

	def _pop_disjunction(self, allow_unsatisfied):
		"""
		Pop one disjunctive dep from self._dynamic_config._dep_disjunctive_stack, and use it to
		populate self._dynamic_config._dep_stack.
		"""
		pkg, dep_root, dep_priority, dep_struct = \
			self._dynamic_config._dep_disjunctive_stack.pop()
		dep_string = portage.dep.paren_enclose(dep_struct)
		if not self._add_pkg_dep_string(
			pkg, dep_root, dep_priority, dep_string, allow_unsatisfied):

		return 1

	def _priority(self, **kwargs):
		if "remove" in self._dynamic_config.myparams:
			priority_constructor = UnmergeDepPriority
		else:
			priority_constructor = DepPriority

			atom_without_category, "null"))
		cat, atom_pn = portage.catsplit(null_cp)

		dbs = self._dynamic_config._filtered_trees[root_config.root]["dbs"]
		categories = set()
		for db, pkg_type, built, installed, db_keys in dbs:
			for cat in db.categories:

	def _have_new_virt(self, root, atom_cp):
		ret = False
		for db, pkg_type, built, installed, db_keys in \
			self._dynamic_config._filtered_trees[root]["dbs"]:
			if db.cp_list(atom_cp):
				ret = True
				break


	def _iter_atoms_for_pkg(self, pkg):
		# TODO: add multiple $ROOT support
		if pkg.root != self._frozen_config.target_root:
			return
		atom_arg_map = self._dynamic_config._atom_arg_map
		root_config = self._frozen_config.roots[pkg.root]
		for atom in self._dynamic_config._set_atoms.iterAtomsForPackage(pkg):
			atom_cp = portage.dep_getkey(atom)
			if atom_cp != pkg.cp and \
				self._have_new_virt(pkg.root, atom_cp):


	def select_files(self, myfiles):
		"""Given a list of .tbz2s, .ebuilds sets, and deps, populate
		self._dynamic_config._initial_arg_list and call self._resolve to create the 
		appropriate depgraph and return a favorite list."""
		debug = "--debug" in self._frozen_config.myopts
		root_config = self._frozen_config.roots[self._frozen_config.target_root]
		sets = root_config.sets
		getSetAtoms = root_config.setconfig.getSetAtoms
		myfavorites=[]
		myroot = self._frozen_config.target_root
		dbs = self._dynamic_config._filtered_trees[myroot]["dbs"]
		vardb = self._frozen_config.trees[myroot]["vartree"].dbapi
		real_vardb = self._frozen_config._trees_orig[myroot]["vartree"].dbapi
		portdb = self._frozen_config.trees[myroot]["porttree"].dbapi
		bindb = self._frozen_config.trees[myroot]["bintree"].dbapi
		pkgsettings = self._frozen_config.pkgsettings[myroot]
		args = []
		onlydeps = "--onlydeps" in self._frozen_config.myopts
		lookup_owners = []
		for x in myfiles:
			ext = os.path.splitext(x)[1]

				mytbz2=portage.xpak.tbz2(x)
				mykey=mytbz2.getelements("CATEGORY")[0]+"/"+os.path.splitext(os.path.basename(x))[0]
				if os.path.realpath(x) != \
					os.path.realpath(self._frozen_config.trees[myroot]["bintree"].getname(mykey)):
					print colorize("BAD", "\n*** You need to adjust PKGDIR to emerge this package.\n")
					return 0, myfavorites
				db_keys = list(bindb._aux_cache_keys)

				pkg = Package(type_name="binary", root_config=root_config,
					cpv=mykey, built=True, metadata=metadata,
					onlydeps=onlydeps)
				self._dynamic_config._pkg_cache[pkg] = pkg
				args.append(PackageArg(arg=x, package=pkg,
					root_config=root_config))
			elif ext==".ebuild":

						print colorize("BAD", "\n*** You are emerging a masked package. It is MUCH better to use")
						print colorize("BAD", "*** /etc/portage/package.* to accomplish this. See portage(5) man")
						print colorize("BAD", "*** page for details.")
						countdown(int(self._frozen_config.settings["EMERGE_WARNING_DELAY"]),
							"Continuing...")
				else:
					raise portage.exception.PackageNotFound(

				metadata = izip(db_keys, portdb.aux_get(mykey, db_keys))
				pkg = Package(type_name="ebuild", root_config=root_config,
					cpv=mykey, metadata=metadata, onlydeps=onlydeps)
				self._dynamic_config._pkg_cache[pkg] = pkg
				args.append(PackageArg(arg=x, package=pkg,
					root_config=root_config))
			elif x.startswith(os.path.sep):

					s = x[len(SETPREFIX):]
					if s not in sets:
						raise portage.exception.PackageSetNotFound(s)
					if s in self._dynamic_config._sets:
						continue
					# Recursively expand sets so that containment tests in
					# self._get_parent_sets() properly match atoms in nested
					# sets (like if world contains system).
					expanded_set = InternalPackageSet(
						initial_atoms=getSetAtoms(s))
					self._dynamic_config._sets[s] = expanded_set
					args.append(SetArg(arg=x, set=expanded_set,
						root_config=root_config))
					continue

					print
					print
					ambiguous_package_name(x, expanded_atoms, root_config,
						self._frozen_config.spinner, self._frozen_config.myopts)
					return False, myfavorites
				if expanded_atoms:
					atom = expanded_atoms[0]

				args.append(AtomArg(arg=atom, atom=atom,
					root_config=root_config))

		if "--update" in self._frozen_config.myopts:
			# In some cases, the greedy slots behavior can pull in a slot that
			# the user would want to uninstall due to it being blocked by a
			# newer version in a different slot. Therefore, it's necessary to

		# Order needs to be preserved since a feature of --nodeps
		# is to allow the user to force a specific merge order.
		args.reverse()
		self._dynamic_config._initial_arg_list = args[:]
	
		return self._resolve(myfavorites)
	
	def _resolve(self, myfavorites):
		"""Given self._dynamic_config._initial_arg_list, pull in the root nodes, 
		call self._creategraph to process theier deps and return 
		a favorite list."""
		debug = "--debug" in self._frozen_config.myopts
		onlydeps = "--onlydeps" in self._frozen_config.myopts
		myroot = self._frozen_config.target_root
		pkgsettings = self._frozen_config.pkgsettings[myroot]
		pprovideddict = pkgsettings.pprovideddict
		for arg in self._dynamic_config._initial_arg_list:
			for atom in arg.set:
				self._frozen_config.spinner.update()
				dep = Dependency(atom=atom, onlydeps=onlydeps,
					root=myroot, parent=arg)
				atom_cp = portage.dep_getkey(atom)

					pprovided = pprovideddict.get(portage.dep_getkey(atom))
					if pprovided and portage.match_from_list(atom, pprovided):
						# A provided package has been specified on the command line.
						self._dynamic_config._pprovided_args.append((arg, atom))
						continue
					if isinstance(arg, PackageArg):
						if not self._add_pkg(arg.package, dep) or \

					if not pkg:
						if not (isinstance(arg, SetArg) and \
							arg.name in ("system", "world")):
							self._dynamic_config._unsatisfied_deps_for_display.append(
								((myroot, atom), {}))
							return 0, myfavorites
						self._dynamic_config._missing_args.append((arg, atom))
						continue
					if atom_cp != pkg.cp:
						# For old-style virtuals, we need to repeat the

							portage.match_from_list(expanded_atom, pprovided):
							# A provided package has been
							# specified on the command line.
							self._dynamic_config._pprovided_args.append((arg, atom))
							continue
					if pkg.installed and "selective" not in self._dynamic_config.myparams:
						self._dynamic_config._unsatisfied_deps_for_display.append(
							((myroot, atom), {}))
						# Previous behavior was to bail out in this case, but
						# since the dep is satisfied by the installed package,

			return 0, myfavorites

		missing=0
		if "--usepkgonly" in self._frozen_config.myopts:
			for xs in self._dynamic_config.digraph.all_nodes():
				if not isinstance(xs, Package):
					continue
				if len(xs) >= 4 and xs[0] != "binary" and xs[3] == "merge":

		The package selection cache is automatically invalidated, since
		arguments influence package selections.
		"""
		args_set = self._dynamic_config._sets["args"]
		args_set.clear()
		for arg in args:
			if not isinstance(arg, (AtomArg, PackageArg)):

				continue
			args_set.add(atom)

		self._dynamic_config._set_atoms.clear()
		self._dynamic_config._set_atoms.update(chain(*self._dynamic_config._sets.itervalues()))
		atom_arg_map = self._dynamic_config._atom_arg_map
		atom_arg_map.clear()
		for arg in args:
			for atom in arg.set:


		# Invalidate the package selection cache, since
		# arguments influence package selections.
		self._dynamic_config._highest_pkg_cache.clear()
		for trees in self._dynamic_config._filtered_trees.itervalues():
			trees["porttree"].dbapi._clear_cache()

	def _greedy_slots(self, root_config, atom, blocker_lookahead=False):

		added to the graph or those that are installed and have
		not been scheduled for replacement.
		"""
		kwargs["trees"] = self._frozen_config._graph_trees
		return self._select_atoms_highest_available(*pargs, **kwargs)

	def _select_atoms_highest_available(self, root, depstring,
		myuse=None, parent=None, strict=True, trees=None, priority=None):
		"""This will raise InvalidDependString if necessary. If trees is
		None then self._dynamic_config._filtered_trees is used."""
		pkgsettings = self._frozen_config.pkgsettings[root]
		if trees is None:
			trees = self._dynamic_config._filtered_trees
		if True:
			try:
				if parent is not None:

		masked_pkg_instances = set()
		missing_licenses = []
		have_eapi_mask = False
		pkgsettings = self._frozen_config.pkgsettings[root]
		implicit_iuse = pkgsettings._get_implicit_iuse()
		root_config = self._frozen_config.roots[root]
		portdb = self._frozen_config.roots[root].trees["porttree"].dbapi
		dbs = self._dynamic_config._filtered_trees[root]["dbs"]
		for db, pkg_type, built, installed, db_keys in dbs:
			if installed:
				continue

			# since arguments are root nodes. Never traverse the same
			# package twice, in order to prevent an infinite loop.
			selected_parent = None
			for parent in self._dynamic_config.digraph.parent_nodes(node):
				if isinstance(parent, DependencyArg):
					msg.append('(dependency required by "%s" [argument])' % \
						(colorize('INFORM', str(parent))))

				slot_available = False
				for other_db, other_type, other_built, \
					other_installed, other_keys in \
					self._dynamic_config._filtered_trees[root_config.root]["dbs"]:
					try:
						if atom.slot == \
							other_db.aux_get(cpv, ["SLOT"])[0]:


	def _select_pkg_highest_available(self, root, atom, onlydeps=False):
		cache_key = (root, atom, onlydeps)
		ret = self._dynamic_config._highest_pkg_cache.get(cache_key)
		if ret is not None:
			pkg, existing = ret
			if pkg and not existing:
				existing = self._dynamic_config._slot_pkg_map[root].get(pkg.slot_atom)
				if existing and existing == pkg:
					# Update the cache to reflect that the
					# package has been added to the graph.
					ret = pkg, pkg
					self._dynamic_config._highest_pkg_cache[cache_key] = ret
			return ret
		ret = self._select_pkg_highest_available_imp(root, atom, onlydeps=onlydeps)
		self._dynamic_config._highest_pkg_cache[cache_key] = ret
		pkg, existing = ret
		if pkg is not None:
			settings = pkg.root_config.settings

		return ret

	def _select_pkg_highest_available_imp(self, root, atom, onlydeps=False):
		root_config = self._frozen_config.roots[root]
		pkgsettings = self._frozen_config.pkgsettings[root]
		dbs = self._dynamic_config._filtered_trees[root]["dbs"]
		vardb = self._frozen_config.roots[root].trees["vartree"].dbapi
		portdb = self._frozen_config.roots[root].trees["porttree"].dbapi
		# List of acceptable packages, ordered by type preference.
		matched_packages = []
		highest_version = None

		atom_cp = atom.cp
		existing_node = None
		myeb = None
		usepkgonly = "--usepkgonly" in self._frozen_config.myopts
		empty = "empty" in self._dynamic_config.myparams
		selective = "selective" in self._dynamic_config.myparams
		reinstall = False
		noreplace = "--noreplace" in self._frozen_config.myopts
		# Behavior of the "selective" parameter depends on
		# whether or not a package matches an argument atom.
		# If an installed package provides an old-style

					# above visibility checks are complete.

					myarg = None
					if root == self._frozen_config.target_root:
						try:
							myarg = self._iter_atoms_for_pkg(pkg).next()
						except StopIteration:

					# will always end with a break statement below
					# this point.
					if find_existing_node:
						e_pkg = self._dynamic_config._slot_pkg_map[root].get(pkg.slot_atom)
						if not e_pkg:
							break
						if portage.dep.match_from_list(atom, [e_pkg]):

					# Compare built package to current config and
					# reject the built package if necessary.
					if built and not installed and \
						("--newuse" in self._frozen_config.myopts or \
						"--reinstall" in self._frozen_config.myopts):
						iuses = pkg.iuse.all
						old_use = pkg.use.enabled
						if myeb:

					# Compare current config to installed package
					# and do not reinstall if possible.
					if not installed and \
						("--newuse" in self._frozen_config.myopts or \
						"--reinstall" in self._frozen_config.myopts) and \
						cpv in vardb.match(atom):
						pkgsettings.setcpv(pkg)
						forced_flags = set()

						myeb = pkg
					matched_packages.append(pkg)
					if reinstall_for_flags:
						self._dynamic_config._reinstall_nodes[pkg] = \
							reinstall_for_flags
					break

		if not matched_packages:
			return None, None

		if "--debug" in self._frozen_config.myopts:
			for pkg in matched_packages:
				portage.writemsg("%s %s\n" % \
					((pkg.type_name + ":").rjust(10), pkg.cpv), noiselevel=-1)

		those that are installed and have not been scheduled for
		replacement.
		"""
		graph_db = self._frozen_config._graph_trees[root]["porttree"].dbapi
		matches = graph_db.match_pkgs(atom)
		if not matches:
			return None, None
		pkg = matches[-1] # highest match
		in_graph = self._dynamic_config._slot_pkg_map[root].get(pkg.slot_atom)
		return pkg, in_graph

	def _complete_graph(self):

		Since this method can consume enough time to disturb users, it is
		currently only enabled by the --complete-graph option.
		"""
		if "--buildpkgonly" in self._frozen_config.myopts or \
			"recurse" not in self._dynamic_config.myparams:
			return 1

		if "complete" not in self._dynamic_config.myparams:
			# Skip this to avoid consuming enough time to disturb users.
			return 1


		# accounted for.
		self._select_atoms = self._select_atoms_from_graph
		self._select_package = self._select_pkg_from_graph
		already_deep = "deep" in self._dynamic_config.myparams
		if not already_deep:
			self._dynamic_config.myparams.add("deep")

		for root in self._frozen_config.roots:
			required_set_names = self._frozen_config._required_set_names.copy()
			if root == self._frozen_config.target_root and \
				(already_deep or "empty" in self._dynamic_config.myparams):
				required_set_names.difference_update(self._dynamic_config._sets)
			if not required_set_names and not self._dynamic_config._ignored_deps:
				continue
			root_config = self._frozen_config.roots[root]
			setconfig = root_config.setconfig
			args = []
			# Reuse existing SetArg instances when available.
			for arg in self._dynamic_config.digraph.root_nodes():
				if not isinstance(arg, SetArg):
					continue
				if arg.root_config != root_config:

			vardb = root_config.trees["vartree"].dbapi
			for arg in args:
				for atom in arg.set:
					self._dynamic_config._dep_stack.append(
						Dependency(atom=atom, root=root, parent=arg))
			if self._dynamic_config._ignored_deps:
				self._dynamic_config._dep_stack.extend(self._dynamic_config._ignored_deps)
				self._dynamic_config._ignored_deps = []
			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._dynamic_config._unsatisfied_deps:
				dep = self._dynamic_config._unsatisfied_deps.pop()
				matches = vardb.match_pkgs(dep.atom)
				if not matches:
					self._dynamic_config._initially_unsatisfied_deps.append(dep)
					continue
				# An scheduled installation broke a deep dependency.
				# Add the installed package to the graph so that it

		operation = "merge"
		if installed or onlydeps:
			operation = "nomerge"
		pkg = self._dynamic_config._pkg_cache.get(
			(type_name, root_config.root, cpv, operation))
		if pkg is None and onlydeps and not installed:
			# Maybe it already got pulled in as a "merge" node.
			pkg = self._dynamic_config.mydbapi[root_config.root].get(
				(type_name, root_config.root, cpv, 'merge'))

		if pkg is None:
			tree_type = self.pkg_tree_map[type_name]
			db = root_config.trees[tree_type].dbapi
			db_keys = list(self._frozen_config._trees_orig[root_config.root][
				tree_type].dbapi._aux_cache_keys)
			try:
				metadata = izip(db_keys, db.aux_get(cpv, db_keys))

			pkg = Package(built=(type_name != "ebuild"), cpv=cpv,
				installed=installed, metadata=metadata,
				root_config=root_config, type_name=type_name)
			self._dynamic_config._pkg_cache[pkg] = pkg
		return pkg

	def _validate_blockers(self):

		correct merge order such that mutually blocking packages are never
		installed simultaneously."""

		if "--buildpkgonly" in self._frozen_config.myopts or \
			"--nodeps" in self._frozen_config.myopts:
			return True

		#if "deep" in self._dynamic_config.myparams:
		if True:
			# Pull in blockers from all installed packages that haven't already
			# been pulled into the depgraph.  This is not enabled by default

			# additional dep_check calls that are required.

			dep_keys = ["DEPEND","RDEPEND","PDEPEND"]
			for myroot in self._frozen_config.trees:
				vardb = self._frozen_config.trees[myroot]["vartree"].dbapi
				portdb = self._frozen_config.trees[myroot]["porttree"].dbapi
				pkgsettings = self._frozen_config.pkgsettings[myroot]
				final_db = self._dynamic_config.mydbapi[myroot]

				blocker_cache = BlockerCache(myroot, vardb)
				stale_cache = set(blocker_cache)
				for pkg in vardb:
					cpv = pkg.cpv
					stale_cache.discard(cpv)
					pkg_in_graph = self._dynamic_config.digraph.contains(pkg)

					# Check for masked installed packages. Only warn about
					# packages that are in the graph in order to avoid warning

					# the merge process or by --depclean.
					if pkg in final_db:
						if pkg_in_graph and not visible(pkgsettings, pkg):
							self._dynamic_config._masked_installed.add(pkg)

					blocker_atoms = None
					blockers = None

						blockers = []
						try:
							blockers.extend(
								self._dynamic_config._blocker_parents.child_nodes(pkg))
						except KeyError:
							pass
						try:
							blockers.extend(
								self._dynamic_config._irrelevant_blockers.child_nodes(pkg))
						except KeyError:
							pass
					if blockers is not None:


					# If this node has any blockers, create a "nomerge"
					# node for it so that they can be enforced.
					self._frozen_config.spinner.update()
					blocker_data = blocker_cache.get(cpv)
					if blocker_data is not None and \
						blocker_data.counter != long(pkg.metadata["COUNTER"]):

							try:
								success, atoms = portage.dep_check(depstr,
									final_db, pkgsettings, myuse=pkg.use.enabled,
									trees=self._frozen_config._graph_trees, myroot=myroot)
							except Exception, e:
								if isinstance(e, SystemExit):
									raise

							for atom in blocker_atoms:
								blocker = Blocker(atom=portage.dep.Atom(atom),
									eapi=pkg.metadata["EAPI"], root=myroot)
								self._dynamic_config._blocker_parents.add(blocker, pkg)
						except portage.exception.InvalidAtom, e:
							depstr = " ".join(vardb.aux_get(pkg.cpv, dep_keys))
							show_invalid_depstring_notice(

		# Discard any "uninstall" tasks scheduled by previous calls
		# to this method, since those tasks may not make sense given
		# the current graph state.
		previous_uninstall_tasks = self._dynamic_config._blocker_uninstalls.leaf_nodes()
		if previous_uninstall_tasks:
			self._dynamic_config._blocker_uninstalls = digraph()
			self._dynamic_config.digraph.difference_update(previous_uninstall_tasks)

		for blocker in self._dynamic_config._blocker_parents.leaf_nodes():
			self._frozen_config.spinner.update()
			root_config = self._frozen_config.roots[blocker.root]
			virtuals = root_config.settings.getvirtuals()
			myroot = blocker.root
			initial_db = self._frozen_config.trees[myroot]["vartree"].dbapi
			final_db = self._dynamic_config.mydbapi[myroot]
			
			provider_virtual = False
			if blocker.cp in virtuals and \

						blocked_final.add(pkg)

			if not blocked_initial and not blocked_final:
				parent_pkgs = self._dynamic_config._blocker_parents.parent_nodes(blocker)
				self._dynamic_config._blocker_parents.remove(blocker)
				# Discard any parents that don't have any more blockers.
				for pkg in parent_pkgs:
					self._dynamic_config._irrelevant_blockers.add(blocker, pkg)
					if not self._dynamic_config._blocker_parents.child_nodes(pkg):
						self._dynamic_config._blocker_parents.remove(pkg)
				continue
			for parent in self._dynamic_config._blocker_parents.parent_nodes(blocker):
				unresolved_blocks = False
				depends_on_order = set()
				for pkg in blocked_initial:

						# confuse users if displayed like a normal blocker.
						continue

					self._dynamic_config._blocked_pkgs.add(pkg, blocker)

					if parent.operation == "merge":
						# Maybe the blocked package can be replaced or simply

						# merge of either package is triggered.
						continue

					self._dynamic_config._blocked_pkgs.add(pkg, blocker)

					# Maybe the blocking package can be
					# unmerged to resolve this block.

				# into the graph.
				if not unresolved_blocks and depends_on_order:
					for inst_pkg, inst_task in depends_on_order:
						if self._dynamic_config.digraph.contains(inst_pkg) and \
							self._dynamic_config.digraph.parent_nodes(inst_pkg):
							unresolved_blocks = True
							break


							operation="uninstall",
							root_config=inst_pkg.root_config,
							type_name=inst_pkg.type_name)
						self._dynamic_config._pkg_cache[uninst_task] = uninst_task
						# Enforce correct merge order with a hard dep.
						self._dynamic_config.digraph.addnode(uninst_task, inst_task,
							priority=BlockerDepPriority.instance)
						# Count references to this blocker so that it can be
						# invalidated after nodes referencing it have been
						# merged.
						self._dynamic_config._blocker_uninstalls.addnode(uninst_task, blocker)
				if not unresolved_blocks and not depends_on_order:
					self._dynamic_config._irrelevant_blockers.add(blocker, parent)
					self._dynamic_config._blocker_parents.remove_edge(blocker, parent)
					if not self._dynamic_config._blocker_parents.parent_nodes(blocker):
						self._dynamic_config._blocker_parents.remove(blocker)
					if not self._dynamic_config._blocker_parents.child_nodes(parent):
						self._dynamic_config._blocker_parents.remove(parent)
				if unresolved_blocks:
					self._dynamic_config._unsolvable_blockers.add(blocker, parent)

		return True


		acceptable = False
		for x in ("--buildpkgonly", "--fetchonly",
			"--fetch-all-uri", "--nodeps"):
			if x in self._frozen_config.myopts:
				acceptable = True
				break
		return acceptable


	def altlist(self, reversed=False):

		while self._dynamic_config._serialized_tasks_cache is None:
			self._resolve_conflicts()
			try:
				self._dynamic_config._serialized_tasks_cache, self._dynamic_config._scheduler_graph = \
					self._serialize_tasks()
			except self._serialize_tasks_retry:
				pass

		retlist = self._dynamic_config._serialized_tasks_cache[:]
		if reversed:
			retlist.reverse()
		return retlist

		internal Package instances such that this depgraph instance should
		not be used to perform any more calculations.
		"""
		if self._dynamic_config._scheduler_graph is None:
			self.altlist()
		self.break_refs(self._dynamic_config._scheduler_graph.order)
		return self._dynamic_config._scheduler_graph

	def break_refs(self, nodes):
		"""

				# original RootConfig instance which references the actual
				# vartree.
				node.root_config = \
					self._frozen_config._trees_orig[node.root_config.root]["root_config"]

	def _resolve_conflicts(self):
		if not self._complete_graph():

		if not self._validate_blockers():
			raise self._unknown_internal_error()

		if self._dynamic_config._slot_collision_info:
			self._process_slot_conflicts()

	def _serialize_tasks(self):

		if "--debug" in self._frozen_config.myopts:
			writemsg("\ndigraph:\n\n", noiselevel=-1)
			self._dynamic_config.digraph.debug_print()
			writemsg("\n", noiselevel=-1)

		scheduler_graph = self._dynamic_config.digraph.copy()

		if '--nodeps' in self._frozen_config.myopts:
			# Preserve the package order given on the command line.
			return ([node for node in scheduler_graph \
				if isinstance(node, Package) \
				and node.operation == 'merge'], scheduler_graph)

		mygraph=self._dynamic_config.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

					node.installed or node.onlydeps:
					removed_nodes.add(node)
			if removed_nodes:
				self._frozen_config.spinner.update()
				mygraph.difference_update(removed_nodes)
			if not removed_nodes:
				break

			elif n1_n2_medium:
				return 1
			return -1
		myblocker_uninstalls = self._dynamic_config._blocker_uninstalls.copy()
		retlist=[]
		# Contains uninstall tasks that have been scheduled to
		# occur after overlapping blockers have been installed.

		# resolved.
		ignored_uninstall_tasks = set()
		have_uninstall_task = False
		complete = "complete" in self._dynamic_config.myparams
		asap_nodes = []

		def get_nodes(**kwargs):

					node in scheduled_uninstalls)]

		# sys-apps/portage needs special treatment if ROOT="/"
		running_root = self._frozen_config._running_root.root
		from portage.const import PORTAGE_PACKAGE_ATOM
		runtime_deps = InternalPackageSet(
			initial_atoms=[PORTAGE_PACKAGE_ATOM])
		running_portage = self._frozen_config.trees[running_root]["vartree"].dbapi.match_pkgs(
			PORTAGE_PACKAGE_ATOM)
		replacement_portage = self._dynamic_config.mydbapi[running_root].match_pkgs(
			PORTAGE_PACKAGE_ATOM)

		if running_portage:

				return True
			return priority_range.ignore_medium_soft(priority)

		tree_mode = "--tree" in self._frozen_config.myopts
		# Tracks whether or not the current iteration should prefer asap_nodes
		# if available.  This is set to False when the previous iteration
		# failed to select any nodes.  It is reset whenever nodes are

		# unresolved blockers or circular dependencies.

		while not mygraph.empty():
			self._frozen_config.spinner.update()
			selected_nodes = None
			ignore_priority = None
			if drop_satisfied or (prefer_asap and asap_nodes):

							with_some_uninstalls_excluded = []
							for node in nodes:
								if node.operation == "uninstall":
									slot_node = self._dynamic_config.mydbapi[node.root
										].match_pkgs(node.slot_atom)
									if slot_node and \
										slot_node[0].operation == "merge":

						# on installation of blocking packages.
						continue

					root_config = self._frozen_config.roots[task.root]
					inst_pkg = self._dynamic_config._pkg_cache[
						("installed", task.root, task.cpv, "nomerge")]

					if self._dynamic_config.digraph.contains(inst_pkg):
						continue

					forbid_overlap = False

						# For packages in the world set, go ahead an uninstall
						# when necessary, as long as the atom will be satisfied
						# in the final state.
						graph_db = self._dynamic_config.mydbapi[task.root]
						skip = False
						try:
							for atom in root_config.sets[

									break
								if not satisfied:
									skip = True
									self._dynamic_config._blocked_world_pkgs[inst_pkg] = atom
									break
						except portage.exception.InvalidDependString, e:
							portage.writemsg("!!! Invalid PROVIDE in " + \

					continue

			if not selected_nodes:
				self._dynamic_config._circular_deps_for_display = mygraph
				raise self._unknown_internal_error()

			# At this point, we've succeeded in selecting one or more nodes, so

					have_uninstall_task = True
					uninst_task = node
				else:
					vardb = self._frozen_config.trees[node.root]["vartree"].dbapi
					previous_cpv = vardb.match(node.slot_atom)
					if previous_cpv:
						# The package will be replaced by this one, so remove

							root=blocker.root, eapi=blocker.eapi,
							satisfied=True))

		unsolvable_blockers = set(self._dynamic_config._unsolvable_blockers.leaf_nodes())
		for node in myblocker_uninstalls.root_nodes():
			unsolvable_blockers.add(node)


		if have_uninstall_task and \
			not complete and \
			not unsolvable_blockers:
			self._dynamic_config.myparams.add("complete")
			raise self._serialize_tasks_retry("")

		if unsolvable_blockers and \
			not self._accept_blocker_conflicts():
			self._dynamic_config._unsatisfied_blockers_for_display = unsolvable_blockers
			self._dynamic_config._serialized_tasks_cache = retlist[:]
			self._dynamic_config._scheduler_graph = scheduler_graph
			raise self._unknown_internal_error()

		if self._dynamic_config._slot_collision_info and \
			not self._accept_blocker_conflicts():
			self._dynamic_config._serialized_tasks_cache = retlist[:]
			self._dynamic_config._scheduler_graph = scheduler_graph
			raise self._unknown_internal_error()

		return retlist, scheduler_graph

			display_order.append(node)
			tempgraph.remove(node)
		display_order.reverse()
		self._frozen_config.myopts.pop("--quiet", None)
		self._frozen_config.myopts.pop("--verbose", None)
		self._frozen_config.myopts["--tree"] = True
		portage.writemsg("\n\n", noiselevel=-1)
		self.display(display_order)
		prefix = colorize("BAD", " * ")

			"optional dependencies.\n", noiselevel=-1)

	def _show_merge_list(self):
		if self._dynamic_config._serialized_tasks_cache is not None and \
			not (self._dynamic_config._displayed_list and \
			(self._dynamic_config._displayed_list == self._dynamic_config._serialized_tasks_cache or \
			self._dynamic_config._displayed_list == \
				list(reversed(self._dynamic_config._serialized_tasks_cache)))):
			display_list = self._dynamic_config._serialized_tasks_cache[:]
			if "--tree" in self._frozen_config.myopts:
				display_list.reverse()
			self.display(display_list)



		conflict_pkgs = {}
		for blocker in blockers:
			for pkg in chain(self._dynamic_config._blocked_pkgs.child_nodes(blocker), \
				self._dynamic_config._blocker_parents.parent_nodes(blocker)):
				parent_atoms = self._dynamic_config._parent_atoms.get(pkg)
				if not parent_atoms:
					atom = self._dynamic_config._blocked_world_pkgs.get(pkg)
					if atom is not None:
						parent_atoms = set([("@world", atom)])
				if parent_atoms:

			sys.stderr.write("".join(msg))
			sys.stderr.flush()

		if "--quiet" not in self._frozen_config.myopts:
			show_blocker_docs_link()

	def display(self, mylist, favorites=[], verbosity=None):

		# This is used to prevent display_problems() from
		# redundantly displaying this exact same merge list
		# again via _show_merge_list().
		self._dynamic_config._displayed_list = mylist

		if verbosity is None:
			verbosity = ("--quiet" in self._frozen_config.myopts and 1 or \
				"--verbose" in self._frozen_config.myopts and 3 or 2)
		favorites_set = InternalPackageSet(favorites)
		oneshot = "--oneshot" in self._frozen_config.myopts or \
			"--onlydeps" in self._frozen_config.myopts
		columns = "--columns" in self._frozen_config.myopts
		changelogs=[]
		p=[]
		blockers = []

		counters = PackageCounters()

		if verbosity == 1 and "--verbose" not in self._frozen_config.myopts:
			def create_use_string(*args):
				return ""
		else:
			def create_use_string(name, cur_iuse, iuse_forced, cur_use,
				old_iuse, old_use,
				is_new, reinst_flags,
				all_flags=(verbosity == 3 or "--quiet" in self._frozen_config.myopts),
				alphabetical=("--alphabetical" in self._frozen_config.myopts)):
				enabled = []
				if alphabetical:
					disabled = enabled

					ret = '%s="%s" ' % (name, ret)
				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._dynamic_config._pkg_cache[
				("installed", uninstall.root, uninstall.cpv, "nomerge")]
			try:
				mygraph.remove(inst_pkg)

				pass

			try:
				inst_pkg_blockers = self._dynamic_config._blocker_parents.child_nodes(inst_pkg)
			except KeyError:
				inst_pkg_blockers = []


			# 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)


			# 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:

				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]):

						# 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))

			pkg_type = x[0]
			myroot = x[1]
			pkg_key = x[2]
			portdb = self._frozen_config.trees[myroot]["porttree"].dbapi
			bindb  = self._frozen_config.trees[myroot]["bintree"].dbapi
			vardb = self._frozen_config.trees[myroot]["vartree"].dbapi
			vartree = self._frozen_config.trees[myroot]["vartree"]
			pkgsettings = self._frozen_config.pkgsettings[myroot]

			fetch=" "
			indent = " " * depth

						counters.blocks_satisfied += 1
				resolved = portage.key_expand(
					str(x.atom).lstrip("!"), mydb=vardb, settings=pkgsettings)
				if "--columns" in self._frozen_config.myopts and "--quiet" in self._frozen_config.myopts:
					addl += " " + colorize(blocker_style, resolved)
				else:
					addl = "[%s %s] %s%s" % \
						(colorize(blocker_style, "blocks"),
						addl, indent, colorize(blocker_style, resolved))
				block_parents = self._dynamic_config._blocker_parents.parent_nodes(x)
				block_parents = set([pnode[2] for pnode in block_parents])
				block_parents = ", ".join(block_parents)
				if resolved!=x[2]:

						if ordered:
							counters.newslot += 1

					if "--changelog" in self._frozen_config.myopts:
						inst_matches = vardb.match(pkg.slot_atom)
						if inst_matches:
							changelogs.extend(calc_changelog(

					# Prevent USE_EXPAND_HIDDEN flags from being hidden if they
					# are the only thing that triggered reinstallation.
					reinst_flags_map = {}
					reinstall_for_flags = self._dynamic_config._reinstall_nodes.get(pkg)
					reinst_expand_map = None
					if reinstall_for_flags:
						reinst_flags_map = map_to_use_expand(

					if pkg_type == "ebuild" and pkg_merge:
						try:
							myfilesdict = portdb.getfetchsizes(pkg_key,
								useflags=pkg_use, debug=self._frozen_config.edebug)
						except portage.exception.InvalidDependString, e:
							src_uri = portdb.aux_get(pkg_key, ["SRC_URI"])[0]
							show_invalid_depstring_notice(x, src_uri, str(e))

					xs[2] = "-" + xs[2]

				mywidth = 130
				if "COLUMNWIDTH" in self._frozen_config.settings:
					try:
						mywidth = int(self._frozen_config.settings["COLUMNWIDTH"])
					except ValueError, e:
						portage.writemsg("!!! %s\n" % str(e), noiselevel=-1)
						portage.writemsg(
							"!!! Unable to parse COLUMNWIDTH='%s'\n" % \
							self._frozen_config.settings["COLUMNWIDTH"], noiselevel=-1)
						del e
				oldlp = mywidth - 30
				newlp = oldlp - 30

					myoldbest = blue("["+", ".join(myoldbest)+"]")

				pkg_cp = xs[0]
				root_config = self._frozen_config.roots[myroot]
				system_set = root_config.sets["system"]
				world_set  = root_config.sets["world"]


					pkg_system = system_set.findAtomForPackage(pkg)
					pkg_world  = world_set.findAtomForPackage(pkg)
					if not (oneshot or pkg_world) and \
						myroot == self._frozen_config.target_root and \
						favorites_set.findAtomForPackage(pkg):
						# Maybe it will be added to world now.
						if create_world_atom(pkg, favorites_set, root_config):

				if x[1]!="/":
					if myoldbest:
						myoldbest +=" "
					if "--columns" in self._frozen_config.myopts:
						if "--quiet" in self._frozen_config.myopts:
							myprint=addl+" "+indent+pkgprint(pkg_cp)
							myprint=myprint+darkblue(" "+xs[1]+xs[2])+" "
							myprint=myprint+myoldbest

						myprint += indent + pkgprint(pkg_key) + " " + \
							myoldbest + darkgreen("to " + myroot)
				else:
					if "--columns" in self._frozen_config.myopts:
						if "--quiet" in self._frozen_config.myopts:
							myprint=addl+" "+indent+pkgprint(pkg_cp)
							myprint=myprint+" "+green(xs[1]+xs[2])+" "
							myprint=myprint+myoldbest

					continue
				p.append((myprint, verboseadd, repoadd))

				if "--tree" not in self._frozen_config.myopts and \
					"--quiet" not in self._frozen_config.myopts and \
					not self._frozen_config._opts_no_restart.intersection(self._frozen_config.myopts) and \
					pkg.root == self._frozen_config._running_root.root and \
					portage.match_from_list(
					portage.const.PORTAGE_PACKAGE_ATOM, [pkg]) and \
					not vardb.cpv_exists(pkg.cpv) and \
					"--quiet" not in self._frozen_config.myopts:
						if mylist_index < len(mylist) - 1:
							p.append(colorize("WARN", "*** Portage will stop merging at this point and reload itself,"))
							p.append(colorize("WARN", "    then resume the merge."))

			if show_repos:
				sys.stdout.write(str(repo_display))

		if "--changelog" in self._frozen_config.myopts:
			print
			for revision,text in changelogs:
				print bold('*'+revision)

			sys.stderr.flush()

		# This goes to stdout for parsing by programs like autounmask.
		for pargs, kwargs in self._dynamic_config._unsatisfied_deps_for_display:
			self._show_unsatisfied_dep(*pargs, **kwargs)

	def _display_problems(self):
		if self._dynamic_config._circular_deps_for_display is not None:
			self._show_circular_deps(
				self._dynamic_config._circular_deps_for_display)

		# The user is only notified of a slot conflict if
		# there are no unresolvable blocker conflicts.
		if self._dynamic_config._unsatisfied_blockers_for_display is not None:
			self._show_unsatisfied_blockers(
				self._dynamic_config._unsatisfied_blockers_for_display)
		else:
			self._show_slot_collision_notice()

		# TODO: Add generic support for "set problem" handlers so that
		# the below warnings aren't special cases for world only.

		if self._dynamic_config._missing_args:
			world_problems = False
			if "world" in self._dynamic_config._sets:
				# Filter out indirect members of world (from nested sets)
				# since only direct members of world are desired here.
				world_set = self._frozen_config.roots[self._frozen_config.target_root].sets["world"]
				for arg, atom in self._dynamic_config._missing_args:
					if arg.name == "world" and atom in world_set:
						world_problems = True
						break

				sys.stderr.write("!!! Please run " + \
					green("emaint --check world")+"\n\n")

		if self._dynamic_config._missing_args:
			sys.stderr.write("\n" + colorize("BAD", "!!!") + \
				" Ebuilds for the following packages are either all\n")
			sys.stderr.write(colorize("BAD", "!!!") + \
				" masked or don't exist:\n")
			sys.stderr.write(" ".join(str(atom) for arg, atom in \
				self._dynamic_config._missing_args) + "\n")

		if self._dynamic_config._pprovided_args:
			arg_refs = {}
			for arg, atom in self._dynamic_config._pprovided_args:
				if isinstance(arg, SetArg):
					parent = arg.name
					arg_atom = (atom, atom)

					refs.append(parent)
			msg = []
			msg.append(bad("\nWARNING: "))
			if len(self._dynamic_config._pprovided_args) > 1:
				msg.append("Requested packages will not be " + \
					"merged because they are listed in\n")
			else:

			sys.stderr.write("".join(msg))

		masked_packages = []
		for pkg in self._dynamic_config._masked_installed:
			root_config = pkg.root_config
			pkgsettings = self._frozen_config.pkgsettings[pkg.root]
			mreasons = get_masking_status(pkg, pkgsettings, root_config)
			masked_packages.append((root_config, pkgsettings,
				pkg.cpv, pkg.metadata, mreasons))

		to the world file if necessary."""
		for x in ("--buildpkgonly", "--fetchonly", "--fetch-all-uri",
			"--oneshot", "--onlydeps", "--pretend"):
			if x in self._frozen_config.myopts:
				return
		root_config = self._frozen_config.roots[self._frozen_config.target_root]
		world_set = root_config.sets["world"]

		world_locked = False

		if hasattr(world_set, "load"):
			world_set.load() # maybe it's changed on disk

		args_set = self._dynamic_config._sets["args"]
		portdb = self._frozen_config.trees[self._frozen_config.target_root]["porttree"].dbapi
		added_favorites = set()
		for x in self._dynamic_config._set_nodes:
			pkg_type, root, pkg_key, pkg_status = x
			if pkg_status != "nomerge":
				continue

					root, portage.VDB_PATH, pkg_key, "PROVIDE"), noiselevel=-1)
				del e
		all_added = []
		for k in self._dynamic_config._sets:
			if k in ("args", "world") or not root_config.sets[k].world_candidate:
				continue
			s = SETPREFIX + k

		if not isinstance(mergelist, list):
			mergelist = []

		fakedb = self._dynamic_config.mydbapi
		trees = self._frozen_config.trees
		serialized_tasks = []
		masked_tasks = []
		for x in mergelist:

				continue
			tree_type = self.pkg_tree_map[pkg_type]
			mydb = trees[myroot][tree_type].dbapi
			db_keys = list(self._frozen_config._trees_orig[myroot][
				tree_type].dbapi._aux_cache_keys)
			try:
				metadata = izip(db_keys, mydb.aux_get(pkg_key, db_keys))

				raise portage.exception.PackageNotFound(pkg_key)
			installed = action == "uninstall"
			built = pkg_type != "ebuild"
			root_config = self._frozen_config.roots[myroot]
			pkg = Package(built=built, cpv=pkg_key,
				installed=installed, metadata=metadata,
				operation=action, root_config=root_config,
				type_name=pkg_type)
			self._dynamic_config._pkg_cache[pkg] = pkg

			root_config = self._frozen_config.roots[pkg.root]
			if "merge" == pkg.operation and \
				not visible(root_config.settings, pkg):
				if skip_masked:
					masked_tasks.append(Dependency(root=pkg.root, parent=pkg))
				else:
					self._dynamic_config._unsatisfied_deps_for_display.append(
						((pkg.root, "="+pkg.cpv), {"myparent":None}))

			fakedb[myroot].cpv_inject(pkg)
			serialized_tasks.append(pkg)
			self._frozen_config.spinner.update()

		if self._dynamic_config._unsatisfied_deps_for_display:
			return False

		if not serialized_tasks or "--nodeps" in self._frozen_config.myopts:
			self._dynamic_config._serialized_tasks_cache = serialized_tasks
			self._dynamic_config._scheduler_graph = self._dynamic_config.digraph
		else:
			self._select_package = self._select_pkg_from_graph
			self._dynamic_config.myparams.add("selective")
			# Always traverse deep dependencies in order to account for
			# potentially unsatisfied dependencies of installed packages.
			# This is necessary for correct --keep-going or --resume operation

			# deep depenedencies of a scheduled build, that build needs to
			# be cancelled. In order for this type of situation to be
			# recognized, deep traversal of dependencies is required.
			self._dynamic_config.myparams.add("deep")

			favorites = resume_data.get("favorites")
			args_set = self._dynamic_config._sets["args"]
			if isinstance(favorites, list):
				args = self._load_favorites(favorites)
			else:

				return False

			unsatisfied_deps = []
			for dep in self._dynamic_config._unsatisfied_deps:
				if not isinstance(dep.parent, Package):
					continue
				if dep.parent.operation == "merge":

				# which is scheduled to be installed.
				unsatisfied_install = False
				traversed = set()
				dep_stack = self._dynamic_config.digraph.parent_nodes(dep.parent)
				while dep_stack:
					node = dep_stack.pop()
					if not isinstance(node, Package):

					if node in traversed:
						continue
					traversed.add(node)
					dep_stack.extend(self._dynamic_config.digraph.parent_nodes(node))

				if unsatisfied_install:
					unsatisfied_deps.append(dep)

				# UnsatisfiedResumeDep exception.
				raise self.UnsatisfiedResumeDep(self,
					masked_tasks + unsatisfied_deps)
			self._dynamic_config._serialized_tasks_cache = None
			try:
				self.altlist()
			except self._unknown_internal_error:

		This allows Package instances to be matched with
		DependencyArg instances during graph creation.
		"""
		root_config = self._frozen_config.roots[self._frozen_config.target_root]
		getSetAtoms = root_config.setconfig.getSetAtoms
		sets = root_config.sets
		args = []

				s = x[len(SETPREFIX):]
				if s not in sets:
					continue
				if s in self._dynamic_config._sets:
					continue
				# Recursively expand sets so that containment tests in
				# self._get_parent_sets() properly match atoms in nested
				# sets (like if world contains system).
				expanded_set = InternalPackageSet(
					initial_atoms=getSetAtoms(s))
				self._dynamic_config._sets[s] = expanded_set
				args.append(SetArg(arg=x, set=expanded_set,
					root_config=root_config))
			else:

		graph in order to avoid making a potentially unsafe decision.
		"""

class _dep_check_composite_db(portage.dbapi):
	"""
	A dbapi-like interface that is optimized for use in dep_check() calls.
	This is built on top of the existing depgraph package selection logic.
	Some packages that have been added to the graph may be masked from this
	view in order to influence the atom preference selection that occurs
	via dep_check().
	"""
	def __init__(self, depgraph, root):
		portage.dbapi.__init__(self)
		self._depgraph = depgraph
		self._root = root
		self._match_cache = {}
		self._cpv_pkg_map = {}

	def _clear_cache(self):
		self._match_cache.clear()
		self._cpv_pkg_map.clear()

	def match(self, atom):
		ret = self._match_cache.get(atom)
		if ret is not None:
				return ret[:]
			orig_atom = atom
			if "/" not in atom:
				atom = self._dep_expand(atom)
			pkg, existing = self._depgraph._select_package(self._root, atom)
			if not pkg:
				ret = []
			else:
				# Return the highest available from select_package() as well as
				# any matching slots in the graph db.
				slots = set()
				slots.add(pkg.metadata["SLOT"])
				atom_cp = portage.dep_getkey(atom)
				if pkg.cp.startswith("virtual/"):
					# For new-style virtual lookahead that occurs inside
					# dep_check(), examine all slots. This is needed
					# so that newer slots will not unnecessarily be pulled in
					# when a satisfying lower slot is already installed. For
					# example, if virtual/jdk-1.4 is satisfied via kaffe then
					# there's no need to pull in a newer slot to satisfy a
					# virtual/jdk dependency.
					for db, pkg_type, built, installed, db_keys in \
						self._depgraph._filtered_trees[self._root]["dbs"]:
						for cpv in db.match(atom):
							if portage.cpv_getkey(cpv) != pkg.cp:
								continue
							slots.add(db.aux_get(cpv, ["SLOT"])[0])
				ret = []
				if self._visible(pkg):
					self._cpv_pkg_map[pkg.cpv] = pkg
					ret.append(pkg.cpv)
				slots.remove(pkg.metadata["SLOT"])
				while slots:
					slot_atom = "%s:%s" % (atom_cp, slots.pop())
					pkg, existing = self._depgraph._select_package(
						self._root, slot_atom)
					if not pkg:
						continue
					if not self._visible(pkg):
						continue
					self._cpv_pkg_map[pkg.cpv] = pkg
					ret.append(pkg.cpv)
				if ret:
					self._cpv_sort_ascending(ret)
			self._match_cache[orig_atom] = ret
			return ret[:]
		orig_atom = atom
		if "/" not in atom:
			atom = self._dep_expand(atom)
		pkg, existing = self._depgraph._select_package(self._root, atom)
		if not pkg:
			ret = []
		else:
			# Return the highest available from select_package() as well as
			# any matching slots in the graph db.
			slots = set()
			slots.add(pkg.metadata["SLOT"])
			atom_cp = portage.dep_getkey(atom)
			if pkg.cp.startswith("virtual/"):
				# For new-style virtual lookahead that occurs inside
				# dep_check(), examine all slots. This is needed
				# so that newer slots will not unnecessarily be pulled in
				# when a satisfying lower slot is already installed. For
				# example, if virtual/jdk-1.4 is satisfied via kaffe then
				# there's no need to pull in a newer slot to satisfy a
				# virtual/jdk dependency.
				for db, pkg_type, built, installed, db_keys in \
					self._depgraph._dynamic_config._filtered_trees[self._root]["dbs"]:
					for cpv in db.match(atom):
						if portage.cpv_getkey(cpv) != pkg.cp:
							continue
						slots.add(db.aux_get(cpv, ["SLOT"])[0])
			ret = []
			if self._visible(pkg):
				self._cpv_pkg_map[pkg.cpv] = pkg
				ret.append(pkg.cpv)
			slots.remove(pkg.metadata["SLOT"])
			while slots:
				slot_atom = "%s:%s" % (atom_cp, slots.pop())
				pkg, existing = self._depgraph._select_package(
					self._root, slot_atom)
				if not pkg:
					continue
				if not self._visible(pkg):
					continue
				self._cpv_pkg_map[pkg.cpv] = pkg
				ret.append(pkg.cpv)
			if ret:
				self._cpv_sort_ascending(ret)
		self._match_cache[orig_atom] = ret
		return ret[:]

	def _visible(self, pkg):
		if pkg.installed and "selective" not in self._depgraph.myparams:
			try:
				arg = self._depgraph._iter_atoms_for_pkg(pkg).next()
			except (StopIteration, portage.exception.InvalidDependString):
				arg = None
			if arg:
				return False
		if pkg.installed:
			try:
				if not visible(
					self._depgraph.pkgsettings[pkg.root], pkg):
					return False
			except portage.exception.InvalidDependString:
				pass
		in_graph = self._depgraph._dynamic_config._slot_pkg_map[
			self._root].get(pkg.slot_atom)
		if in_graph is None:
			# Mask choices for packages which are not the highest visible
			# version within their slot (since they usually trigger slot
			# conflicts).
			highest_visible, in_graph = self._depgraph._select_package(
				self._root, pkg.slot_atom)
			if pkg != highest_visible:
				# version within their slot (since they usually trigger slot
				# conflicts).
				highest_visible, in_graph = self._depgraph._select_package(
					self._root, pkg.slot_atom)
				if pkg != highest_visible:
					return False
			elif in_graph != pkg:
				# Mask choices for packages that would trigger a slot
				# conflict with a previously selected package.
				return False
		elif in_graph != pkg:
			# Mask choices for packages that would trigger a slot
			# conflict with a previously selected package.
			return False
		return True

	def _dep_expand(self, atom):
		"""
		This is only needed for old installed packages that may
		contain atoms that are not fully qualified with a specific
		category. Emulate the cpv_expand() function that's used by
		dbapi.match() in cases like this. If there are multiple
		matches, it's often due to a new-style virtual that has
		been added, so try to filter those out to avoid raising
		a ValueError.
		"""
		root_config = self._depgraph.roots[self._root]
		orig_atom = atom
		expanded_atoms = self._depgraph._dep_expand(root_config, atom)
		if len(expanded_atoms) > 1:
			non_virtual_atoms = []
			for x in expanded_atoms:
				if not portage.dep_getkey(x).startswith("virtual/"):
					non_virtual_atoms.append(x)
			if len(non_virtual_atoms) == 1:
				expanded_atoms = non_virtual_atoms
		if len(expanded_atoms) > 1:
			# compatible with portage.cpv_expand()
			raise portage.exception.AmbiguousPackageName(
				[portage.dep_getkey(x) for x in expanded_atoms])
		if expanded_atoms:
			atom = expanded_atoms[0]
		else:
			null_atom = insert_category_into_atom(atom, "null")
			null_cp = portage.dep_getkey(null_atom)
			cat, atom_pn = portage.catsplit(null_cp)
			virts_p = root_config.settings.get_virts_p().get(atom_pn)
			if virts_p:
				# Allow the resolver to choose which virtual.
				atom = insert_category_into_atom(atom, "virtual")
			else:
				atom = insert_category_into_atom(atom, "null")
		return atom
				cat, atom_pn = portage.catsplit(null_cp)
				virts_p = root_config.settings.get_virts_p().get(atom_pn)
				if virts_p:
					# Allow the resolver to choose which virtual.
					atom = insert_category_into_atom(atom, "virtual")
				else:
					atom = insert_category_into_atom(atom, "null")
			return atom

	def aux_get(self, cpv, wants):
		metadata = self._cpv_pkg_map[cpv].metadata
		return [metadata.get(x, "") for x in wants]


def ambiguous_package_name(arg, atoms, root_config, spinner, myopts):

			if not skip_unsatisfied:
				raise

			graph = mydepgraph._dynamic_config.digraph
			unsatisfied_parents = dict((dep.parent, dep.parent) \
				for dep in e.value)
			traversed_nodes = set()

Return to bug 275217