# Copyright 1999-2009 Gentoo Foundation
# Distributed under the terms of the GNU General Public License v2
# $Id$

import gc
import logging
import re
import sys
import textwrap
from itertools import chain, izip

import portage
from portage import os
from portage import digraph
from portage.output import bold, blue, colorize, create_color_func, darkblue, \
	darkgreen, green, nc_len, red, teal, turquoise, yellow
bad = create_color_func("BAD")
from portage.sets import SETPREFIX
from portage.sets.base import InternalPackageSet
from portage.util import cmp_sort_key, writemsg, writemsg_stdout
from portage.util import writemsg_level

from _emerge.AtomArg import AtomArg
from _emerge.Blocker import Blocker
from _emerge.BlockerCache import BlockerCache
from _emerge.BlockerDepPriority import BlockerDepPriority
from _emerge.changelog import calc_changelog
from _emerge.countdown import countdown
from _emerge.create_world_atom import create_world_atom
from _emerge.Dependency import Dependency
from _emerge.DependencyArg import DependencyArg
from _emerge.DepPriority import DepPriority
from _emerge.DepPriorityNormalRange import DepPriorityNormalRange
from _emerge.DepPrioritySatisfiedRange import DepPrioritySatisfiedRange
from _emerge.FakeVartree import FakeVartree
from _emerge._find_deep_system_runtime_deps import _find_deep_system_runtime_deps
from _emerge.format_size import format_size
from _emerge.is_valid_package_atom import is_valid_package_atom
from _emerge.Package import Package
from _emerge.PackageArg import PackageArg
from _emerge.PackageCounters import PackageCounters
from _emerge.PackageVirtualDbapi import PackageVirtualDbapi
from _emerge.RepoDisplay import RepoDisplay
from _emerge.RootConfig import RootConfig
from _emerge.search import search
from _emerge.SetArg import SetArg
from _emerge.show_invalid_depstring_notice import show_invalid_depstring_notice
from _emerge.UnmergeDepPriority import UnmergeDepPriority
from _emerge.visible import visible

class _frozen_depgraph_config(object):

	def __init__(self, settings, trees, myopts, spinner):
		self.settings = settings
		self.target_root = settings["ROOT"]
		self.myopts = myopts
		self.edebug = 0
		if settings.get("PORTAGE_DEBUG", "") == "1":
			self.edebug = 1
		self.spinner = spinner
		self._running_root = trees["/"]["root_config"]
		self._opts_no_restart = frozenset(["--buildpkgonly",
			"--fetchonly", "--fetch-all-uri", "--pretend"])
		self.pkgsettings = {}
		self.trees = {}
		self._trees_orig = trees
		self.roots = {}
		# All Package instances
		self._pkg_cache = {}
		for myroot in trees:
			self.trees[myroot] = {}
			# Create a RootConfig instance that references
			# the FakeVartree instead of the real one.
			self.roots[myroot] = RootConfig(
				trees[myroot]["vartree"].settings,
				self.trees[myroot],
				trees[myroot]["root_config"].setconfig)
			for tree in ("porttree", "bintree"):
				self.trees[myroot][tree] = trees[myroot][tree]
			self.trees[myroot]["vartree"] = \
				FakeVartree(trees[myroot]["root_config"],
					pkg_cache=self._pkg_cache)
			self.pkgsettings[myroot] = portage.config(
				clone=self.trees[myroot]["vartree"].settings)

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

class _dynamic_depgraph_config(object):

	def __init__(self, depgraph, myparams, allow_backtracking,
		runtime_pkg_mask):
		self.myparams = myparams.copy()
		self._allow_backtracking = allow_backtracking
		# 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 = {}
		# Contains installed packages and new packages that have been added
		# to the graph.
		self._graph_trees = {}
		# Caches visible packages returned from _select_package, for use in
		# depgraph._iter_atoms_for_pkg() SLOT logic.
		self._visible_pkgs = {}
		#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._sets["args"] = InternalPackageSet()
		# contains all atoms from all sets added to the graph, including
		# atoms given as arguments
		self._set_atoms = InternalPackageSet()
		self._atom_arg_map = {}
		# contains all nodes pulled in by self._set_atoms
		self._set_nodes = set()
		# Contains only Blocker -> Uninstall edges
		self._blocker_uninstalls = digraph()
		# Contains only Package -> Blocker edges
		self._blocker_parents = digraph()
		# Contains only irrelevant Package -> Blocker edges
		self._irrelevant_blockers = digraph()
		# Contains only unsolvable Package -> Blocker edges
		self._unsolvable_blockers = digraph()
		# Contains all Blocker -> Blocked Package edges
		self._blocked_pkgs = digraph()
		# Contains world packages that have been protected from
		# uninstallation but may not have been added to the graph
		# if the graph is not complete yet.
		self._blocked_world_pkgs = {}
		self._slot_collision_info = {}
		# Slot collision nodes are not allowed to block other packages since
		# blocker validation is only able to account for one package per slot.
		self._slot_collision_nodes = set()
		self._parent_atoms = {}
		self._slot_conflict_parent_atoms = set()
		self._serialized_tasks_cache = None
		self._scheduler_graph = None
		self._displayed_list = None
		self._pprovided_args = []
		self._missing_args = []
		self._masked_installed = set()
		self._unsatisfied_deps_for_display = []
		self._unsatisfied_blockers_for_display = None
		self._circular_deps_for_display = None
		self._dep_stack = []
		self._dep_disjunctive_stack = []
		self._unsatisfied_deps = []
		self._initially_unsatisfied_deps = []
		self._ignored_deps = []
		self._highest_pkg_cache = {}
		if runtime_pkg_mask is None:
			runtime_pkg_mask = {}
		else:
			runtime_pkg_mask = dict((k, v.copy()) for (k, v) in \
				runtime_pkg_mask.iteritems())
		self._runtime_pkg_mask = runtime_pkg_mask
		self._need_restart = False

		for myroot in depgraph._frozen_config.trees:
			self._slot_pkg_map[myroot] = {}
			vardb = depgraph._frozen_config.trees[myroot]["vartree"].dbapi
			preload_installed_pkgs = \
				"--nodeps" not in depgraph._frozen_config.myopts and \
				"--buildpkgonly" not in depgraph._frozen_config.myopts
			# This fakedbapi instance will model the state that the vdb will
			# have after new packages have been installed.
			fakedb = PackageVirtualDbapi(vardb.settings)
			if preload_installed_pkgs:
				for pkg in vardb:
					depgraph._spinner_update()
					# This triggers metadata updates via FakeVartree.
					vardb.aux_get(pkg.cpv, [])
					fakedb.cpv_inject(pkg)

			# Now that the vardb state is cached in our FakeVartree,
			# we won't be needing the real vartree cache for awhile.
			# To make some room on the heap, clear the vardbapi
			# caches.
			depgraph._frozen_config._trees_orig[myroot
				]["vartree"].dbapi._clear_cache()
			gc.collect()

			self.mydbapi[myroot] = fakedb
			def graph_tree():
				pass
			graph_tree.dbapi = fakedb
			self._graph_trees[myroot] = {}
			self._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]["porttree"]   = graph_tree
			self._graph_trees[myroot]["vartree"]    = graph_tree
			def filtered_tree():
				pass
			filtered_tree.dbapi = _dep_check_composite_db(depgraph, myroot)
			self._filtered_trees[myroot]["porttree"] = filtered_tree
			self._visible_pkgs[myroot] = PackageVirtualDbapi(vardb.settings)

			# Passing in graph_tree as the vartree here could lead to better
			# atom selections in some cases by causing atoms for packages that
			# have been added to the graph to be preferred over other choices.
			# However, it can trigger atom selections that result in
			# unresolvable direct circular dependencies. For example, this
			# happens with gwydion-dylan which depends on either itself or
			# gwydion-dylan-bin. In case gwydion-dylan is not yet installed,
			# gwydion-dylan-bin needs to be selected in order to avoid a
			# an unresolvable direct circular dependency.
			#
			# To solve the problem described above, pass in "graph_db" so that
			# packages that have been added to the graph are distinguishable
			# from other available packages and installed packages. Also, pass
			# the parent package into self._select_atoms() calls so that
			# unresolvable direct circular dependencies can be detected and
			# avoided when possible.
			self._filtered_trees[myroot]["graph_db"] = graph_tree.dbapi
			self._filtered_trees[myroot]["vartree"] = \
				depgraph._frozen_config.trees[myroot]["vartree"]

			dbs = []
			portdb = depgraph._frozen_config.trees[myroot]["porttree"].dbapi
			bindb  = depgraph._frozen_config.trees[myroot]["bintree"].dbapi
			vardb  = depgraph._frozen_config.trees[myroot]["vartree"].dbapi
			#               (db, pkg_type, built, installed, db_keys)
			if "--usepkgonly" not in depgraph._frozen_config.myopts:
				db_keys = list(portdb._aux_cache_keys)
				dbs.append((portdb, "ebuild", False, False, db_keys))
			if "--usepkg" in depgraph._frozen_config.myopts:
				db_keys = list(bindb._aux_cache_keys)
				dbs.append((bindb,  "binary", True, False, db_keys))
			db_keys = list(depgraph._frozen_config._trees_orig[myroot
				]["vartree"].dbapi._aux_cache_keys)
			dbs.append((vardb, "installed", True, True, db_keys))
			self._filtered_trees[myroot]["dbs"] = dbs
			if "--usepkg" in depgraph._frozen_config.myopts:
				depgraph._frozen_config._trees_orig[myroot
					]["bintree"].populate(
					"--getbinpkg" in depgraph._frozen_config.myopts,
					"--getbinpkgonly" in depgraph._frozen_config.myopts)

class depgraph(object):

	pkg_tree_map = RootConfig.pkg_tree_map

	_dep_keys = ["DEPEND", "RDEPEND", "PDEPEND"]
	
	def __init__(self, settings, trees, myopts, myparams, spinner,
		frozen_config=None, runtime_pkg_mask=None, allow_backtracking=False):
		if frozen_config is None:
			frozen_config = _frozen_depgraph_config(settings, trees,
			myopts, spinner)
		self._frozen_config = frozen_config
		self._dynamic_config = _dynamic_depgraph_config(self, myparams,
			allow_backtracking, runtime_pkg_mask)

		self._select_atoms = self._select_atoms_highest_available
		self._select_package = self._select_pkg_highest_available

	def _spinner_update(self):
		if self._frozen_config.spinner:
			self._frozen_config.spinner.update()

	def _show_missed_update(self):

		if '--quiet' in self._frozen_config.myopts and \
			'--debug' not in self._frozen_config.myopts:
			return

		# In order to minimize noise, show only the highest
		# missed update from each SLOT.
		missed_updates = {}
		for pkg, mask_reasons in \
			self._dynamic_config._runtime_pkg_mask.iteritems():
			if pkg.installed:
				# Exclude installed here since we only
				# want to show available updates.
				continue
			k = (pkg.root, pkg.slot_atom)
			if k in missed_updates:
				other_pkg, mask_type, parent_atoms = missed_updates[k]
				if other_pkg > pkg:
					continue
			for mask_type, parent_atoms in mask_reasons.iteritems():
				if not parent_atoms:
					continue
				missed_updates[k] = (pkg, mask_type, parent_atoms)
				break

		if not missed_updates:
			return

		missed_update_types = {}
		for pkg, mask_type, parent_atoms in missed_updates.itervalues():
			missed_update_types.setdefault(mask_type,
				[]).append((pkg, parent_atoms))

		self._show_missed_update_slot_conflicts(
			missed_update_types.get("slot conflict"))

		self._show_missed_update_unsatisfied_dep(
			missed_update_types.get("missing dependency"))

	def _show_missed_update_unsatisfied_dep(self, missed_updates):

		if not missed_updates:
			return

		write = sys.stderr.write

		for pkg, parent_atoms in missed_updates:

			write("\n!!! The following update has been skipped " + \
				"due to unsatisfied dependencies:\n\n")

			write(str(pkg.slot_atom))
			if pkg.root != '/':
				write(" for %s" % (pkg.root,))
			write("\n")

			for parent, root, atom in parent_atoms:
				self._show_unsatisfied_dep(root, atom, myparent=parent)
				write("\n")

		sys.stderr.flush()

	def _show_missed_update_slot_conflicts(self, missed_updates):

		if not missed_updates:
			return

		msg = []
		msg.append("\n!!! One or more updates have been skipped due to " + \
			"a dependency conflict:\n\n")

		indent = "  "
		for pkg, parent_atoms in missed_updates:
			msg.append(str(pkg.slot_atom))
			if pkg.root != '/':
				msg.append(" for %s" % (pkg.root,))
			msg.append("\n\n")

			for parent, atom in parent_atoms:
				msg.append(indent)
				msg.append(str(pkg))

				msg.append(" conflicts with\n")
				msg.append(2*indent)
				if isinstance(parent,
					(PackageArg, AtomArg)):
					# For PackageArg and AtomArg types, it's
					# redundant to display the atom attribute.
					msg.append(str(parent))
				else:
					# Display the specific atom from SetArg or
					# Package types.
					msg.append("%s required by %s" % (atom, parent))
				msg.append("\n")
			msg.append("\n")

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

	def _show_slot_collision_notice(self):
		"""Show an informational message advising the user to mask one of the
		the packages. In some cases it may be possible to resolve this
		automatically, but support for backtracking (removal nodes that have
		already been selected) will be required in order to handle all possible
		cases.
		"""

		if not self._dynamic_config._slot_collision_info:
			return

		self._show_merge_list()

		msg = []
		msg.append("\n!!! Multiple package instances within a single " + \
			"package slot have been pulled\n")
		msg.append("!!! into the dependency graph, resulting" + \
			" in a slot conflict:\n\n")
		indent = "  "
		# Max number of parents shown, to avoid flooding the display.
		max_parents = 3
		explanation_columns = 70
		explanations = 0
		for (slot_atom, root), slot_nodes \
			in self._dynamic_config._slot_collision_info.iteritems():
			msg.append(str(slot_atom))
			if root != '/':
				msg.append(" for %s" % (root,))
			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
					# show those alone since those are the most interesting.
					if not pruned_list:
						# When generating the pruned list, prefer instances
						# of DependencyArg over instances of Package.
						for parent_atom in parent_atoms:
							if len(pruned_list) >= max_parents:
								break
							parent, atom = parent_atom
							if isinstance(parent, DependencyArg):
								pruned_list.add(parent_atom)
						# Prefer Packages instances that themselves have been
						# pulled into collision slots.
						for parent_atom in parent_atoms:
							if len(pruned_list) >= max_parents:
								break
							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:
								break
							pruned_list.add(parent_atom)
					omitted_parents = len(parent_atoms) - len(pruned_list)
					parent_atoms = pruned_list
					msg.append(" pulled in by\n")
					for parent_atom in parent_atoms:
						parent, atom = parent_atom
						msg.append(2*indent)
						if isinstance(parent,
							(PackageArg, AtomArg)):
							# For PackageArg and AtomArg types, it's
							# redundant to display the atom attribute.
							msg.append(str(parent))
						else:
							# Display the specific atom from SetArg or
							# Package types.
							msg.append("%s required by %s" % (atom, parent))
						msg.append("\n")
					if omitted_parents:
						msg.append(2*indent)
						msg.append("(and %d more)\n" % omitted_parents)
				else:
					msg.append(" (no parents)\n")
				msg.append("\n")
			explanation = self._slot_conflict_explanation(slot_nodes)
			if explanation:
				explanations += 1
				msg.append(indent + "Explanation:\n\n")
				for line in textwrap.wrap(explanation, explanation_columns):
					msg.append(2*indent + line + "\n")
				msg.append("\n")
		msg.append("\n")
		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 = []
		msg.append("It may be possible to solve this problem ")
		msg.append("by using package.mask to prevent one of ")
		msg.append("those packages from being selected. ")
		msg.append("However, it is also possible that conflicting ")
		msg.append("dependencies exist such that they are impossible to ")
		msg.append("satisfy simultaneously.  If such a conflict exists in ")
		msg.append("the dependencies of two different packages, then those ")
		msg.append("packages can not be installed simultaneously.")

		from formatter import AbstractFormatter, DumbWriter
		f = AbstractFormatter(DumbWriter(sys.stderr, maxcol=72))
		for x in msg:
			f.add_flowing_data(x)
		f.end_paragraph(1)

		msg = []
		msg.append("For more information, see MASKED PACKAGES ")
		msg.append("section in the emerge man page or refer ")
		msg.append("to the Gentoo Handbook.")
		for x in msg:
			f.add_flowing_data(x)
		f.end_paragraph(1)
		f.writer.flush()

	def _slot_conflict_explanation(self, slot_nodes):
		"""
		When a slot conflict occurs due to USE deps, there are a few
		different cases to consider:

		1) New USE are correctly set but --newuse wasn't requested so an
		   installed package with incorrect USE happened to get pulled
		   into graph before the new one.

		2) New USE are incorrectly set but an installed package has correct
		   USE so it got pulled into the graph, and a new instance also got
		   pulled in due to --newuse or an upgrade.

		3) Multiple USE deps exist that can't be satisfied simultaneously,
		   and multiple package instances got pulled into the same slot to
		   satisfy the conflicting deps.

		Currently, explanations and suggested courses of action are generated
		for cases 1 and 2. Case 3 is too complex to give a useful suggestion.
		"""

		if len(slot_nodes) != 2:
			# Suggestions are only implemented for
			# 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
				# currently no suggestion for this case.
				return None
			conflict_atoms = all_conflict_atoms.intersection(parent_atoms)
			for parent_atom in conflict_atoms:
				parent, atom = parent_atom
				if not atom.use:
					# Suggestions are currently only implemented for cases
					# in which all conflict atoms have USE deps.
					return None
			if conflict_atoms:
				if matched_node is not None:
					# If conflict atoms match multiple nodes
					# then there's no suggestion.
					return None
				matched_node = node
				matched_atoms = conflict_atoms
			else:
				if unmatched_node is not None:
					# Neither node is matched by conflict atoms, and
					# there is no suggestion for this case.
					return None
				unmatched_node = node

		if matched_node is None or unmatched_node is None:
			# This shouldn't happen.
			return None

		if unmatched_node.installed and not matched_node.installed and \
			unmatched_node.cpv == matched_node.cpv:
			# If the conflicting packages are the same version then
			# --newuse should be all that's needed. If they are different
			# versions then there's some other problem.
			return "New USE are correctly set, but --newuse wasn't" + \
				" requested, so an installed package with incorrect USE " + \
				"happened to get pulled into the dependency graph. " + \
				"In order to solve " + \
				"this, either specify the --newuse option or explicitly " + \
				" reinstall '%s'." % matched_node.slot_atom

		if matched_node.installed and not unmatched_node.installed:
			atoms = sorted(set(atom for parent, atom in matched_atoms))
			explanation = ("New USE for '%s' are incorrectly set. " + \
				"In order to solve this, adjust USE to satisfy '%s'") % \
				(matched_node.slot_atom, atoms[0])
			if len(atoms) > 1:
				for atom in atoms[1:-1]:
					explanation += ", '%s'" % (atom,)
				if len(atoms) > 2:
					explanation += ","
				explanation += " and '%s'" % (atoms[-1],)
			explanation += "."
			return explanation

		return None

	def _process_slot_conflicts(self):
		"""
		Process slot conflict data to identify specific atoms which
		lead to conflict. These atoms only match a subset of the
		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
					# Use package set for matching since it will match via
					# PROVIDE when necessary, while match_from_list does not.
					parent, atom = parent_atom
					atom_set = InternalPackageSet(
						initial_atoms=(atom,))
					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 or \
			"--binpkg-respect-use" 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 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._spinner_update()
			while dep_stack:
				dep = dep_stack.pop()
				if isinstance(dep, Package):
					if not self._add_pkg_deps(dep,
						allow_unsatisfied=allow_unsatisfied):
						return 0
					continue
				if not self._add_dep(dep, allow_unsatisfied=allow_unsatisfied):
					return 0
			if dep_disjunctive_stack:
				if not self._pop_disjunction(allow_unsatisfied):
					return 0
		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 = self._dynamic_config.myparams.get("deep", 0)
		recurse = empty or deep is True or dep.depth <= deep
		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.
					return 1
				# The blocker applies to the root where
				# the parent is or will be installed.
				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)
		if not dep_pkg:
			if dep.priority.optional:
				# This could be an unecessary build-time dep
				# 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}))

			# The parent node should not already be in
			# runtime_pkg_mask, since that would trigger an
			# infinite backtracking loop.
			if self._dynamic_config._allow_backtracking:
				if dep.parent in self._dynamic_config._runtime_pkg_mask:
					if "--debug" in self._frozen_config.myopts:
						writemsg(
							"!!! backtracking loop detected: %s %s\n" % \
							(dep.parent,
							self._dynamic_config._runtime_pkg_mask[
							dep.parent]), noiselevel=-1)
				else:
					# Do not backtrack if only USE have to be changed in
					# order to satisfy the dependency.
					dep_pkg, existing_node = \
						self._select_package(dep.root, dep.atom.without_use,
							onlydeps=dep.onlydeps)
					if dep_pkg is None:
						self._dynamic_config._runtime_pkg_mask.setdefault(
							dep.parent, {})["missing dependency"] = \
								set([(dep.parent, dep.root, dep.atom)])
						self._dynamic_config._need_restart = True
						if "--debug" in self._frozen_config.myopts:
							msg = []
							msg.append("")
							msg.append("")
							msg.append("backtracking due to unsatisfied dep:")
							msg.append("    parent: %s" % dep.parent)
							msg.append("  priority: %s" % dep.priority)
							msg.append("      root: %s" % dep.root)
							msg.append("      atom: %s" % dep.atom)
							msg.append("")
							writemsg_level("".join("%s\n" % l for l in msg),
								noiselevel=-1, level=logging.DEBUG)

			return 0
		# In some cases, dep_check will return deps that shouldn't
		# be proccessed any further, so they are identified and
		# discarded here. Try to discard as few as possible since
		# discarded dependencies reduce the amount of information
		# available for optimization of merge order.
		if dep.priority.satisfied and \
			not dep_pkg.installed and \
			not (existing_node or recurse):
			myarg = None
			if dep.root == self._frozen_config.target_root:
				try:
					myarg = self._iter_atoms_for_pkg(dep_pkg).next()
				except StopIteration:
					pass
				except portage.exception.InvalidDependString:
					if not dep_pkg.installed:
						# This shouldn't happen since the package
						# 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):
			return 0
		return 1

	def _add_pkg(self, pkg, dep):
		myparent = None
		priority = None
		depth = 0
		if dep is None:
			dep = Dependency()
		else:
			myparent = dep.parent
			priority = dep.priority
			depth = dep.depth
		if priority is None:
			priority = DepPriority()
		"""
		Fills the digraph with nodes comprised of packages to merge.
		mybigkey is the package spec of the package to merge.
		myparent is the package depending on mybigkey ( or None )
		addme = Should we add this package to the digraph or are we just looking at it's deps?
			Think --onlydeps, we need to ignore packages in that case.
		#stuff to add:
		#SLOT-aware emerge
		#IUSE-aware emerge -> USE DEP aware depgraph
		#"no downgrade" emerge
		"""
		# 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:
			try:
				arg_atoms = list(self._iter_atoms_for_pkg(pkg))
			except portage.exception.InvalidDependString, e:
				if not pkg.installed:
					show_invalid_depstring_notice(
						pkg, pkg.metadata["PROVIDE"], str(e))
					return 0
				del e

		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
				# dependencies are rebuilt/updated as soon as possible,
				# which is needed especially when emerge is called by
				# revdep-rebuild since dependencies may be affected by ABI
				# breakage that has rendered them useless. Don't adjust
				# priority here when in "empty" mode since all packages
				# 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 existing_node_matches and \
					pkg != existing_node and \
					dep.atom is not None:
					# Use package set for matching since it will match via
					# PROVIDE when necessary, while match_from_list does not.
					atom_set = InternalPackageSet(initial_atoms=[dep.atom])
					if not atom_set.findAtomForPackage(existing_node):
						existing_node_matches = False
				if existing_node_matches:
					# The existing node can be reused.
					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
					# buildtime dependency then drop it here since otherwise
					# it can skew the merge order calculation in an unwanted
					# 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,
								(dep.parent, dep.atom))
					return 1
				else:
					# A slot conflict has occurred. 
					# The existing node should not already be in
					# runtime_pkg_mask, since that would trigger an
					# infinite backtracking loop.
					if self._dynamic_config._allow_backtracking and \
						existing_node in \
						self._dynamic_config._runtime_pkg_mask:
						if "--debug" in self._frozen_config.myopts:
							writemsg(
								"!!! backtracking loop detected: %s %s\n" % \
								(existing_node,
								self._dynamic_config._runtime_pkg_mask[
								existing_node]), noiselevel=-1)
					elif self._dynamic_config._allow_backtracking and \
						not self._accept_blocker_conflicts():
						self._add_slot_conflict(pkg)
						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._add_parent_atom(pkg, parent_atom)
						self._process_slot_conflicts()

						parent_atoms = \
							self._dynamic_config._parent_atoms.get(pkg, set())
						if parent_atoms:
							parent_atoms = self._dynamic_config._slot_conflict_parent_atoms.intersection(parent_atoms)
						if pkg >= existing_node:
							# We only care about the parent atoms
							# when they trigger a downgrade.
							parent_atoms = set()

						self._dynamic_config._runtime_pkg_mask.setdefault(
							existing_node, {})["slot conflict"] = parent_atoms
						self._dynamic_config._need_restart = True
						if "--debug" in self._frozen_config.myopts:
							msg = []
							msg.append("")
							msg.append("")
							msg.append("backtracking due to slot conflict:")
							msg.append("   package: %s" % existing_node)
							msg.append("      slot: %s" % existing_node.slot_atom)
							msg.append("   parents: %s" % \
								[(str(parent), atom) \
								for parent, atom in parent_atoms])
							msg.append("")
							writemsg_level("".join("%s\n" % l for l in msg),
								noiselevel=-1, level=logging.DEBUG)
						return 0

					# A slot collision has occurred.  Sometimes this coincides
					# with unresolvable blockers, so the slot collision will be
					# shown later if there are no unresolvable blockers.
					self._add_slot_conflict(pkg)
					slot_collision = True

			if slot_collision:
				# Now add this node to the graph so that self.display()
				# can show use flags and --tree portage.output.  This node is
				# 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
				# doesn't already. Any pre-existing providers will be preferred
				# over this one.
				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()
				except portage.exception.InvalidDependString, e:
					show_invalid_depstring_notice(
						pkg, pkg.metadata["PROVIDE"], str(e))
					del e
					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.
		    We want to go deeper on a few occasions:
		    Installing package A, we need to make sure package A's deps are met.
		    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.
		"""
		if arg_atoms:
			depth = 0
		pkg.depth = depth
		deep = self._dynamic_config.myparams.get("deep", 0)
		empty = "empty" in self._dynamic_config.myparams
		recurse = empty or deep is True or depth + 1 <= deep
		dep_stack = self._dynamic_config._dep_stack
		if "recurse" not in self._dynamic_config.myparams:
			return 1
		elif pkg.installed and not recurse:
			dep_stack = self._dynamic_config._ignored_deps

		self._spinner_update()

		if not previously_added:
			dep_stack.append(pkg)
		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):

		mytype = pkg.type_name
		myroot = pkg.root
		mykey = pkg.cpv
		metadata = pkg.metadata
		myuse = pkg.use.enabled
		jbigkey = pkg
		depth = pkg.depth + 1
		removal_action = "remove" in self._dynamic_config.myparams

		edepend={}
		depkeys = ["DEPEND","RDEPEND","PDEPEND"]
		for k in depkeys:
			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
				# circular dependencies. Don't convert to PDEPEND since that
				# could make --with-bdeps=y less effective if it is used to
				# adjust merge order to prevent built_with_use() calls from
				# failing.
				bdeps_optional = True
			else:
				# 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"] = ""

		if removal_action:
			bdeps_root = myroot
		else:
			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
				elif root_deps == "rdeps":
					edepend["DEPEND"] = ""

		deps = (
			(bdeps_root, edepend["DEPEND"],
				self._priority(buildtime=(not bdeps_optional),
				optional=bdeps_optional)),
			(myroot, edepend["RDEPEND"], self._priority(runtime=True)),
			(myroot, edepend["PDEPEND"], self._priority(runtime_post=True))
		)

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

			for dep_root, dep_string, dep_priority in deps:
				if not dep_string:
					continue
				if debug:
					print
					print "Parent:   ", jbigkey
					print "Depstring:", dep_string
					print "Priority:", dep_priority

				try:

					dep_string = portage.dep.paren_normalize(
						portage.dep.use_reduce(
						portage.dep.paren_reduce(dep_string),
						uselist=pkg.use.enabled))

					dep_string = list(self._queue_disjunctive_deps(
						pkg, dep_root, dep_priority, dep_string))

				except portage.exception.InvalidDependString, e:
					if pkg.installed:
						del e
						continue
					show_invalid_depstring_notice(pkg, dep_string, str(e))
					return 0

				if not dep_string:
					continue

				dep_string = portage.dep.paren_enclose(dep_string)

				if not self._add_pkg_dep_string(
					pkg, dep_root, dep_priority, dep_string,
					allow_unsatisfied):
					return 0

		except portage.exception.AmbiguousPackageName, e:
			pkgs = e.args[0]
			portage.writemsg("\n\n!!! An atom in the dependencies " + \
				"is not fully-qualified. Multiple matches:\n\n", noiselevel=-1)
			for cpv in pkgs:
				portage.writemsg("    %s\n" % cpv, noiselevel=-1)
			portage.writemsg("\n", noiselevel=-1)
			if mytype == "binary":
				portage.writemsg(
					"!!! 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)
			portage.writemsg("!!! Please notify the package maintainer " + \
				"that atoms must be fully-qualified.\n", noiselevel=-1)
			return 0
		finally:
			portage.dep._dep_check_strict = True
		return 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:
			print
			print "Parent:   ", pkg
			print "Depstring:", dep_string
			print "Priority:", dep_priority

		try:
			selected_atoms = self._select_atoms(dep_root,
				dep_string, myuse=pkg.use.enabled, parent=pkg,
				strict=strict, priority=dep_priority)
		except portage.exception.InvalidDependString, e:
			show_invalid_depstring_notice(pkg, dep_string, str(e))
			del e
			if pkg.installed:
				return 1
			return 0

		if debug:
			print "Candidates:", selected_atoms

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

		for atom in selected_atoms:
			try:

				atom = portage.dep.Atom(atom)

				mypriority = dep_priority.copy()
				if not atom.blocker and vardb.match(atom):
					mypriority.satisfied = True

				if not self._add_dep(Dependency(atom=atom,
					blocker=atom.blocker, depth=depth, parent=pkg,
					priority=mypriority, root=dep_root),
					allow_unsatisfied=allow_unsatisfied):
					return 0

			except portage.exception.InvalidAtom, e:
				show_invalid_depstring_notice(
					pkg, dep_string, str(e))
				del e
				if not pkg.installed:
					return 0

		if debug:
			print "Exiting...", pkg

		return 1

	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 = 0
		while i < len(dep_struct):
			x = dep_struct[i]
			if isinstance(x, list):
				for y in self._queue_disjunctive_deps(
					pkg, dep_root, dep_priority, x):
					yield y
			elif x == "||":
				self._queue_disjunction(pkg, dep_root, dep_priority,
					[ x, dep_struct[ i + 1 ] ] )
				i += 1
			else:
				try:
					x = portage.dep.Atom(x)
				except portage.exception.InvalidAtom:
					if not pkg.installed:
						raise portage.exception.InvalidDependString(
							"invalid atom: '%s'" % x)
				else:
					# Note: Eventually this will check for PROPERTIES=virtual
					# or whatever other metadata gets implemented for this
					# purpose.
					if x.cp.startswith('virtual/'):
						self._queue_disjunction( pkg, dep_root,
							dep_priority, [ str(x) ] )
					else:
						yield str(x)
			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 0
		return 1

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

	def _dep_expand(self, root_config, atom_without_category):
		"""
		@param root_config: a root config instance
		@type root_config: RootConfig
		@param atom_without_category: an atom without a category component
		@type atom_without_category: String
		@rtype: list
		@returns: a list of atoms containing categories (possibly empty)
		"""
		null_cp = portage.dep_getkey(insert_category_into_atom(
			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:
				if db.cp_list("%s/%s" % (cat, atom_pn)):
					categories.add(cat)

		deps = []
		for cat in categories:
			deps.append(insert_category_into_atom(
				atom_without_category, cat))
		return deps

	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
		return ret

	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):
				continue
			visible_pkgs = \
				self._dynamic_config._visible_pkgs[pkg.root].match_pkgs(atom)
			visible_pkgs.reverse() # descending order
			higher_slot = None
			for visible_pkg in visible_pkgs:
				if visible_pkg.cp != atom_cp:
					continue
				if pkg >= visible_pkg:
					# This is descending order, and we're not
					# interested in any versions <= pkg given.
					break
				if pkg.slot_atom != visible_pkg.slot_atom:
					higher_slot = visible_pkg
					break
			if higher_slot is not None:
				continue
			for arg in atom_arg_map[(atom, pkg.root)]:
				if isinstance(arg, PackageArg) and \
					arg.package != pkg:
					continue
				yield arg, atom

	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]
			if ext==".tbz2":
				if not os.path.exists(x):
					if os.path.exists(
						os.path.join(pkgsettings["PKGDIR"], "All", x)):
						x = os.path.join(pkgsettings["PKGDIR"], "All", x)
					elif os.path.exists(
						os.path.join(pkgsettings["PKGDIR"], x)):
						x = os.path.join(pkgsettings["PKGDIR"], x)
					else:
						print "\n\n!!! Binary package '"+str(x)+"' does not exist."
						print "!!! Please ensure the tbz2 exists as specified.\n"
						return 0, myfavorites
				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

				pkg = self._pkg(mykey, "binary", root_config,
					onlydeps=onlydeps)
				args.append(PackageArg(arg=x, package=pkg,
					root_config=root_config))
			elif ext==".ebuild":
				ebuild_path = portage.util.normalize_path(os.path.abspath(x))
				pkgdir = os.path.dirname(ebuild_path)
				tree_root = os.path.dirname(os.path.dirname(pkgdir))
				cp = pkgdir[len(tree_root)+1:]
				e = portage.exception.PackageNotFound(
					("%s is not in a valid portage tree " + \
					"hierarchy or does not exist") % x)
				if not portage.isvalidatom(cp):
					raise e
				cat = portage.catsplit(cp)[0]
				mykey = cat + "/" + os.path.basename(ebuild_path[:-7])
				if not portage.isvalidatom("="+mykey):
					raise e
				ebuild_path = portdb.findname(mykey)
				if ebuild_path:
					if ebuild_path != os.path.join(os.path.realpath(tree_root),
						cp, os.path.basename(ebuild_path)):
						print colorize("BAD", "\n*** You need to adjust PORTDIR or PORTDIR_OVERLAY to emerge this package.\n")
						return 0, myfavorites
					if mykey not in portdb.xmatch(
						"match-visible", portage.dep_getkey(mykey)):
						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(
						"%s is not in a valid portage tree hierarchy or does not exist" % x)
				pkg = self._pkg(mykey, "ebuild", root_config,
					onlydeps=onlydeps)
				args.append(PackageArg(arg=x, package=pkg,
					root_config=root_config))
			elif x.startswith(os.path.sep):
				if not x.startswith(myroot):
					portage.writemsg(("\n\n!!! '%s' does not start with" + \
						" $ROOT.\n") % x, noiselevel=-1)
					return 0, []
				# Queue these up since it's most efficient to handle
				# multiple files in a single iter_owners() call.
				lookup_owners.append(x)
			else:
				if x in ("system", "world"):
					x = SETPREFIX + x
				if x.startswith(SETPREFIX):
					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
				if not is_valid_package_atom(x):
					portage.writemsg("\n\n!!! '%s' is not a valid package atom.\n" % x,
						noiselevel=-1)
					portage.writemsg("!!! Please check ebuild(5) for full details.\n")
					portage.writemsg("!!! (Did you specify a version but forget to prefix with '='?)\n")
					return (0,[])
				# Don't expand categories or old-style virtuals here unless
				# necessary. Expansion of old-style virtuals here causes at
				# least the following problems:
				#   1) It's more difficult to determine which set(s) an atom
				#      came from, if any.
				#   2) It takes away freedom from the resolver to choose other
				#      possible expansions when necessary.
				if "/" in x:
					args.append(AtomArg(arg=x, atom=x,
						root_config=root_config))
					continue
				expanded_atoms = self._dep_expand(root_config, x)
				installed_cp_set = set()
				for atom in expanded_atoms:
					atom_cp = portage.dep_getkey(atom)
					if vardb.cp_list(atom_cp):
						installed_cp_set.add(atom_cp)

				if len(installed_cp_set) > 1:
					non_virtual_cps = set()
					for atom_cp in installed_cp_set:
						if not atom_cp.startswith("virtual/"):
							non_virtual_cps.add(atom_cp)
					if len(non_virtual_cps) == 1:
						installed_cp_set = non_virtual_cps

				if len(expanded_atoms) > 1 and len(installed_cp_set) == 1:
					installed_cp = iter(installed_cp_set).next()
					expanded_atoms = [atom for atom in expanded_atoms \
						if portage.dep_getkey(atom) == installed_cp]

				if len(expanded_atoms) > 1:
					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]
				else:
					null_atom = insert_category_into_atom(x, "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 depgraph to choose which virtual.
						atom = insert_category_into_atom(x, "virtual")
					else:
						atom = insert_category_into_atom(x, "null")

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

		if lookup_owners:
			relative_paths = []
			search_for_multiple = False
			if len(lookup_owners) > 1:
				search_for_multiple = True

			for x in lookup_owners:
				if not search_for_multiple and os.path.isdir(x):
					search_for_multiple = True
				relative_paths.append(x[len(myroot):])

			owners = set()
			for pkg, relative_path in \
				real_vardb._owners.iter_owners(relative_paths):
				owners.add(pkg.mycpv)
				if not search_for_multiple:
					break

			if not owners:
				portage.writemsg(("\n\n!!! '%s' is not claimed " + \
					"by any package.\n") % lookup_owners[0], noiselevel=-1)
				return 0, []

			for cpv in owners:
				slot = vardb.aux_get(cpv, ["SLOT"])[0]
				if not slot:
					# portage now masks packages with missing slot, but it's
					# possible that one was installed by an older version
					atom = portage.cpv_getkey(cpv)
				else:
					atom = "%s:%s" % (portage.cpv_getkey(cpv), slot)
				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
			# detect and discard any that should be uninstalled. Each time
			# that arguments are updated, package selections are repeated in
			# order to ensure consistency with the current arguments:
			#
			#  1) Initialize args
			#  2) Select packages and generate initial greedy atoms
			#  3) Update args with greedy atoms
			#  4) Select packages and generate greedy atoms again, while
			#     accounting for any blockers between selected packages
			#  5) Update args with revised greedy atoms

			self._set_args(args)
			greedy_args = []
			for arg in args:
				greedy_args.append(arg)
				if not isinstance(arg, AtomArg):
					continue
				for atom in self._greedy_slots(arg.root_config, arg.atom):
					greedy_args.append(
						AtomArg(arg=arg.arg, atom=atom,
							root_config=arg.root_config))

			self._set_args(greedy_args)
			del greedy_args

			# Revise greedy atoms, accounting for any blockers
			# between selected packages.
			revised_greedy_args = []
			for arg in args:
				revised_greedy_args.append(arg)
				if not isinstance(arg, AtomArg):
					continue
				for atom in self._greedy_slots(arg.root_config, arg.atom,
					blocker_lookahead=True):
					revised_greedy_args.append(
						AtomArg(arg=arg.arg, atom=atom,
							root_config=arg.root_config))
			args = revised_greedy_args
			del revised_greedy_args

		self._set_args(args)

		myfavorites = set(myfavorites)
		for arg in args:
			if isinstance(arg, (AtomArg, PackageArg)):
				myfavorites.add(arg.atom)
			elif isinstance(arg, SetArg):
				myfavorites.add(arg.arg)
		myfavorites = list(myfavorites)

		if debug:
			portage.writemsg("\n", noiselevel=-1)
		# Order needs to be preserved since a feature of --nodeps
		# is to allow the user to force a specific merge order.
		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
		virtuals = pkgsettings.getvirtuals()
		for arg in self._dynamic_config._initial_arg_list:
			for atom in arg.set:
				self._spinner_update()
				dep = Dependency(atom=atom, onlydeps=onlydeps,
					root=myroot, parent=arg)
				atom_cp = portage.dep_getkey(atom)
				try:
					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 \
							not self._create_graph():
							if not self._dynamic_config._need_restart:
								sys.stderr.write(("\n\n!!! Problem " + \
									"resolving dependencies for %s\n") % \
									arg.arg)
							return 0, myfavorites
						continue
					if debug:
						portage.writemsg("      Arg: %s\n     Atom: %s\n" % \
							(arg, atom), noiselevel=-1)
					pkg, existing_node = self._select_package(
						myroot, atom, onlydeps=onlydeps)
					if not pkg:
						pprovided_match = False
						for virt_choice in virtuals.get(atom.cp, []):
							expanded_atom = portage.dep.Atom(
								atom.replace(atom.cp,
								portage.dep_getkey(virt_choice), 1))
							pprovided = pprovideddict.get(expanded_atom.cp)
							if pprovided and \
								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))
								pprovided_match = True
								break
						if pprovided_match:
							continue

						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
						# package.provided check against the selected package.
						expanded_atom = atom.replace(atom_cp, pkg.cp)
						pprovided = pprovideddict.get(pkg.cp)
						if pprovided and \
							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,
						# it's more friendly to continue building the graph
						# and just show a warning message. Therefore, only bail
						# out here if the atom is not from either the system or
						# world set.
						if not (isinstance(arg, SetArg) and \
							arg.name in ("system", "world")):
							return 0, myfavorites

					# Add the selected package to the graph as soon as possible
					# so that later dep_check() calls can use it as feedback
					# for making more consistent atom selections.
					if not self._add_pkg(pkg, dep):
						if self._dynamic_config._need_restart:
							pass
						elif isinstance(arg, SetArg):
							sys.stderr.write(("\n\n!!! Problem resolving " + \
								"dependencies for %s from %s\n") % \
								(atom, arg.arg))
						else:
							sys.stderr.write(("\n\n!!! Problem resolving " + \
								"dependencies for %s\n") % atom)
						return 0, myfavorites

				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")
					portage.writemsg("!!! to aid in the detection of malicious intent.\n\n")
					portage.writemsg("!!! THIS IS A POSSIBLE INDICATION OF TAMPERED FILES -- CHECK CAREFULLY.\n")
					portage.writemsg("!!! Affected file: %s\n" % (e), noiselevel=-1)
					return 0, myfavorites
				except portage.exception.InvalidSignature, e:
					portage.writemsg("\n\n!!! An invalid gpg signature is preventing portage from calculating the\n")
					portage.writemsg("!!! required dependencies. This is a security feature enabled by the admin\n")
					portage.writemsg("!!! to aid in the detection of malicious intent.\n\n")
					portage.writemsg("!!! THIS IS A POSSIBLE INDICATION OF TAMPERED FILES -- CHECK CAREFULLY.\n")
					portage.writemsg("!!! Affected file: %s\n" % (e), noiselevel=-1)
					return 0, myfavorites
				except SystemExit, e:
					raise # Needed else can't exit
				except Exception, e:
					print >> sys.stderr, "\n\n!!! Problem in '%s' dependencies." % atom
					print >> sys.stderr, "!!!", str(e), getattr(e, "__module__", None)
					raise

		# Now that the root packages have been added to the graph,
		# process the dependencies.
		if not self._create_graph():
			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":
					if missing == 0:
						print
					missing += 1
					print "Missing binary for:",xs[2]

		try:
			self.altlist()
		except self._unknown_internal_error:
			return False, myfavorites

		# We're true here unless we are missing binaries.
		return (not missing,myfavorites)

	def _set_args(self, args):
		"""
		Create the "args" package set from atoms and packages given as
		arguments. This method can be called multiple times if necessary.
		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
			atom = arg.atom
			if atom in args_set:
				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:
				atom_key = (atom, arg.root_config.root)
				refs = atom_arg_map.get(atom_key)
				if refs is None:
					refs = []
					atom_arg_map[atom_key] = refs
					if arg not in refs:
						refs.append(arg)

		# 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):
		"""
		Return a list of slot atoms corresponding to installed slots that
		differ from the slot of the highest visible match. When
		blocker_lookahead is True, slot atoms that would trigger a blocker
		conflict are automatically discarded, potentially allowing automatic
		uninstallation of older slots when appropriate.
		"""
		highest_pkg, in_graph = self._select_package(root_config.root, atom)
		if highest_pkg is None:
			return []
		vardb = root_config.trees["vartree"].dbapi
		slots = set()
		for cpv in vardb.match(atom):
			# don't mix new virtuals with old virtuals
			if portage.cpv_getkey(cpv) == highest_pkg.cp:
				slots.add(vardb.aux_get(cpv, ["SLOT"])[0])

		slots.add(highest_pkg.metadata["SLOT"])
		if len(slots) == 1:
			return []
		greedy_pkgs = []
		slots.remove(highest_pkg.metadata["SLOT"])
		while slots:
			slot = slots.pop()
			slot_atom = portage.dep.Atom("%s:%s" % (highest_pkg.cp, slot))
			pkg, in_graph = self._select_package(root_config.root, slot_atom)
			if pkg is not None and \
				pkg.cp == highest_pkg.cp and pkg < highest_pkg:
				greedy_pkgs.append(pkg)
		if not greedy_pkgs:
			return []
		if not blocker_lookahead:
			return [pkg.slot_atom for pkg in greedy_pkgs]

		blockers = {}
		blocker_dep_keys = ["DEPEND", "PDEPEND", "RDEPEND"]
		for pkg in greedy_pkgs + [highest_pkg]:
			dep_str = " ".join(pkg.metadata[k] for k in blocker_dep_keys)
			try:
				atoms = self._select_atoms(
					pkg.root, dep_str, pkg.use.enabled,
					parent=pkg, strict=True)
			except portage.exception.InvalidDependString:
				continue
			blocker_atoms = (x for x in atoms if x.blocker)
			blockers[pkg] = InternalPackageSet(initial_atoms=blocker_atoms)

		if highest_pkg not in blockers:
			return []

		# filter packages with invalid deps
		greedy_pkgs = [pkg for pkg in greedy_pkgs if pkg in blockers]

		# filter packages that conflict with highest_pkg
		greedy_pkgs = [pkg for pkg in greedy_pkgs if not \
			(blockers[highest_pkg].findAtomForPackage(pkg) or \
			blockers[pkg].findAtomForPackage(highest_pkg))]

		if not greedy_pkgs:
			return []

		# If two packages conflict, discard the lower version.
		discard_pkgs = set()
		greedy_pkgs.sort(reverse=True)
		for i in xrange(len(greedy_pkgs) - 1):
			pkg1 = greedy_pkgs[i]
			if pkg1 in discard_pkgs:
				continue
			for j in xrange(i + 1, len(greedy_pkgs)):
				pkg2 = greedy_pkgs[j]
				if pkg2 in discard_pkgs:
					continue
				if blockers[pkg1].findAtomForPackage(pkg2) or \
					blockers[pkg2].findAtomForPackage(pkg1):
					# pkg1 > pkg2
					discard_pkgs.add(pkg2)

		return [pkg.slot_atom for pkg in greedy_pkgs \
			if pkg not in discard_pkgs]

	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._dynamic_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:
					trees[root]["parent"] = parent
				if priority is not None:
					trees[root]["priority"] = priority
				if not strict:
					portage.dep._dep_check_strict = False
				mycheck = portage.dep_check(depstring, None,
					pkgsettings, myuse=myuse,
					myroot=root, trees=trees)
			finally:
				if parent is not None:
					trees[root].pop("parent")
				if priority is not None:
					trees[root].pop("priority")
				portage.dep._dep_check_strict = True
			if not mycheck[0]:
				raise portage.exception.InvalidDependString(mycheck[1])
			selected_atoms = mycheck[1]
		return selected_atoms

	def _show_unsatisfied_dep(self, root, atom, myparent=None, arg=None):
		atom = portage.dep.Atom(atom)
		atom_set = InternalPackageSet(initial_atoms=(atom,))
		xinfo = '"%s"' % atom
		if arg:
			xinfo='"%s"' % arg
		# Discard null/ from failed cpv_expand category expansion.
		xinfo = xinfo.replace("null/", "")
		masked_packages = []
		missing_use = []
		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
			match = db.match
			if hasattr(db, "xmatch"):
				cpv_list = db.xmatch("match-all", atom.without_use)
			else:
				cpv_list = db.match(atom.without_use)
			# descending order
			cpv_list.reverse()
			for cpv in cpv_list:
				metadata, mreasons  = get_mask_info(root_config, cpv,
					pkgsettings, db, pkg_type, built, installed, db_keys)
				if metadata is not None:
					pkg = Package(built=built, cpv=cpv,
						installed=installed, metadata=metadata,
						root_config=root_config)
					if pkg.cp != atom.cp:
						# A cpv can be returned from dbapi.match() as an
						# old-style virtual match even in cases when the
						# package does not actually PROVIDE the virtual.
						# Filter out any such false matches here.
						if not atom_set.findAtomForPackage(pkg):
							continue
					if mreasons:
						masked_pkg_instances.add(pkg)
					if atom.use:
						missing_use.append(pkg)
						if not mreasons:
							continue
				masked_packages.append(
					(root_config, pkgsettings, cpv, metadata, mreasons))

		missing_use_reasons = []
		missing_iuse_reasons = []
		for pkg in missing_use:
			use = pkg.use.enabled
			iuse = implicit_iuse.union(re.escape(x) for x in pkg.iuse.all)
			iuse_re = re.compile("^(%s)$" % "|".join(iuse))
			missing_iuse = []
			for x in atom.use.required:
				if iuse_re.match(x) is None:
					missing_iuse.append(x)
			mreasons = []
			if missing_iuse:
				mreasons.append("Missing IUSE: %s" % " ".join(missing_iuse))
				missing_iuse_reasons.append((pkg, mreasons))
			else:
				need_enable = sorted(atom.use.enabled.difference(use))
				need_disable = sorted(atom.use.disabled.intersection(use))
				if need_enable or need_disable:
					changes = []
					changes.extend(colorize("red", "+" + x) \
						for x in need_enable)
					changes.extend(colorize("blue", "-" + x) \
						for x in need_disable)
					mreasons.append("Change USE: %s" % " ".join(changes))
					missing_use_reasons.append((pkg, mreasons))

		unmasked_use_reasons = [(pkg, mreasons) for (pkg, mreasons) \
			in missing_use_reasons if pkg not in masked_pkg_instances]

		unmasked_iuse_reasons = [(pkg, mreasons) for (pkg, mreasons) \
			in missing_iuse_reasons if pkg not in masked_pkg_instances]

		show_missing_use = False
		if unmasked_use_reasons:
			# Only show the latest version.
			show_missing_use = unmasked_use_reasons[:1]
		elif unmasked_iuse_reasons:
			if missing_use_reasons:
				# All packages with required IUSE are masked,
				# so display a normal masking message.
				pass
			else:
				show_missing_use = unmasked_iuse_reasons

		if show_missing_use:
			print "\nemerge: there are no ebuilds built with USE flags to satisfy "+green(xinfo)+"."
			print "!!! One of the following packages is required to complete your request:"
			for pkg, mreasons in show_missing_use:
				print "- "+pkg.cpv+" ("+", ".join(mreasons)+")"

		elif masked_packages:
			print "\n!!! " + \
				colorize("BAD", "All ebuilds that could satisfy ") + \
				colorize("INFORM", xinfo) + \
				colorize("BAD", " have been masked.")
			print "!!! One of the following masked packages is required to complete your request:"
			have_eapi_mask = show_masked_packages(masked_packages)
			if have_eapi_mask:
				print
				msg = ("The current version of portage supports " + \
					"EAPI '%s'. You must upgrade to a newer version" + \
					" of portage before EAPI masked packages can" + \
					" be installed.") % portage.const.EAPI
				from textwrap import wrap
				for line in wrap(msg, 75):
					print line
			print
			show_mask_docs()
		else:
			print "\nemerge: there are no ebuilds to satisfy "+green(xinfo)+"."

		# Show parent nodes and the argument that pulled them in.
		traversed_nodes = set()
		node = myparent
		msg = []
		while node is not None:
			traversed_nodes.add(node)
			msg.append('(dependency required by "%s" [%s])' % \
				(colorize('INFORM', str(node.cpv)), node.type_name))

			if node not in self._dynamic_config.digraph:
				# The parent is not in the graph due to backtracking.
				break

			# When traversing to parents, prefer arguments over packages
			# 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))))
					selected_parent = None
					break
				if parent not in traversed_nodes:
					selected_parent = parent
			node = selected_parent
		for line in msg:
			print line

		print

	def _iter_match_pkgs(self, root_config, pkg_type, atom, onlydeps=False):
		"""
		Iterate over Package instances of pkg_type matching the given atom.
		This does not check visibility and it also does not match USE for
		unbuilt ebuilds since USE are lazily calculated after visibility
		checks (to avoid the expense when possible).
		"""

		db = root_config.trees[self.pkg_tree_map[pkg_type]].dbapi

		if hasattr(db, "xmatch"):
			cpv_list = db.xmatch("match-all", atom)
		else:
			cpv_list = db.match(atom)

		# USE=multislot can make an installed package appear as if
		# it doesn't satisfy a slot dependency. Rebuilding the ebuild
		# won't do any good as long as USE=multislot is enabled since
		# the newly built package still won't have the expected slot.
		# Therefore, assume that such SLOT dependencies are already
		# satisfied rather than forcing a rebuild.
		installed = pkg_type == 'installed'
		if installed and not cpv_list and atom.slot:
			for cpv in db.match(atom.cp):
				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]:
							slot_available = True
							break
					except KeyError:
						pass
				if not slot_available:
					continue
				inst_pkg = self._pkg(cpv, "installed",
					root_config, installed=installed)
				# Remove the slot from the atom and verify that
				# the package matches the resulting atom.
				atom_without_slot = portage.dep.remove_slot(atom)
				if atom.use:
					atom_without_slot += str(atom.use)
				atom_without_slot = portage.dep.Atom(atom_without_slot)
				if portage.match_from_list(
					atom_without_slot, [inst_pkg]):
					cpv_list = [inst_pkg.cpv]
				break

		if cpv_list:

			# descending order
			cpv_list.reverse()
			for cpv in cpv_list:
				try:
					pkg = self._pkg(cpv, pkg_type, root_config,
						installed=installed, onlydeps=onlydeps)
				except portage.exception.PackageNotFound:
					pass
				else:
					if pkg.cp != atom.cp:
						# A cpv can be returned from dbapi.match() as an
						# old-style virtual match even in cases when the
						# package does not actually PROVIDE the virtual.
						# Filter out any such false matches here.
						if not InternalPackageSet(initial_atoms=(atom,)
							).findAtomForPackage(pkg):
							continue
					yield pkg

	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
			if visible(settings, pkg) and not (pkg.installed and \
				settings._getMissingKeywords(pkg.cpv, pkg.metadata)):
				self._dynamic_config._visible_pkgs[pkg.root].cpv_inject(pkg)
		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
		if not isinstance(atom, portage.dep.Atom):
			atom = portage.dep.Atom(atom)
		atom_cp = atom.cp
		atom_set = InternalPackageSet(initial_atoms=(atom,))
		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
		avoid_update = "--update" not 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
		# virtual that is no longer provided by an available
		# package, the installed package may match an argument
		# atom even though none of the available packages do.
		# Therefore, "selective" logic does not consider
		# whether or not an installed package matches an
		# argument atom. It only considers whether or not
		# available packages match argument atoms, which is
		# represented by the found_available_arg flag.
		found_available_arg = False
		for find_existing_node in True, False:
			if existing_node:
				break
			for db, pkg_type, built, installed, db_keys in dbs:
				if existing_node:
					break
				if installed and not find_existing_node:
					want_reinstall = reinstall or empty or \
						(found_available_arg and not selective)
					if want_reinstall and matched_packages:
						continue

				for pkg in self._iter_match_pkgs(root_config, pkg_type, atom, 
					onlydeps=onlydeps):
					if pkg in self._dynamic_config._runtime_pkg_mask:
						# The package has been masked by the backtracking logic
						continue
					cpv = pkg.cpv
					# Make --noreplace take precedence over --newuse.
					if not pkg.installed and noreplace and \
						cpv in vardb.match(atom):
						# If the installed version is masked, it may
						# be necessary to look at lower versions,
						# in case there is a visible downgrade.
						continue
					reinstall_for_flags = None

					if not pkg.installed or \
						(pkg.built and matched_packages and \
						not (avoid_update and pkg.installed)):
						# Only enforce visibility on installed packages
						# if there is at least one other visible package
						# available. By filtering installed masked packages
						# here, packages that have been masked since they
						# were installed can be automatically downgraded
						# to an unmasked version.
						try:
							if not visible(pkgsettings, pkg):
								continue
						except portage.exception.InvalidDependString:
							if not installed:
								continue

						# Enable upgrade or downgrade to a version
						# with visible KEYWORDS when the installed
						# version is masked by KEYWORDS, but never
						# reinstall the same exact version only due
						# to a KEYWORDS mask.
						if built and matched_packages:

							different_version = None
							for avail_pkg in matched_packages:
								if not portage.dep.cpvequal(
									pkg.cpv, avail_pkg.cpv):
									different_version = avail_pkg
									break
							if different_version is not None:

								if installed and \
									pkgsettings._getMissingKeywords(
									pkg.cpv, pkg.metadata):
									continue

								# If the ebuild no longer exists or it's
								# keywords have been dropped, reject built
								# instances (installed or binary).
								# If --usepkgonly is enabled, assume that
								# the ebuild status should be ignored.
								if not usepkgonly:
									try:
										pkg_eb = self._pkg(
											pkg.cpv, "ebuild", root_config)
									except portage.exception.PackageNotFound:
										continue
									else:
										if not visible(pkgsettings, pkg_eb):
											continue

					# Calculation of USE for unbuilt ebuilds is relatively
					# expensive, so it is only performed lazily, after the
					# 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:
							pass
						except portage.exception.InvalidDependString:
							if not installed:
								# masked by corruption
								continue
					if not installed and myarg:
						found_available_arg = True

					if atom.use and not pkg.built:
						use = pkg.use.enabled
						if atom.use.enabled.difference(use):
							continue
						if atom.use.disabled.intersection(use):
							continue
					if pkg.cp == atom_cp:
						if highest_version is None:
							highest_version = pkg
						elif pkg > highest_version:
							highest_version = pkg
					# At this point, we've found the highest visible
					# match from the current repo. Any lower versions
					# from this repo are ignored, so this so the loop
					# 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
						# Use PackageSet.findAtomForPackage()
						# for PROVIDE support.
						if atom_set.findAtomForPackage(e_pkg):
							if highest_version and \
								e_pkg.cp == atom_cp and \
								e_pkg < highest_version and \
								e_pkg.slot_atom != highest_version.slot_atom:
								# There is a higher version available in a
								# different slot, so this existing node is
								# irrelevant.
								pass
							else:
								matched_packages.append(e_pkg)
								existing_node = e_pkg
						break
					# 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 or \
						"--binpkg-respect-use" in self._frozen_config.myopts):
						iuses = pkg.iuse.all
						old_use = pkg.use.enabled
						if myeb:
							pkgsettings.setcpv(myeb)
						else:
							pkgsettings.setcpv(pkg)
						now_use = pkgsettings["PORTAGE_USE"].split()
						forced_flags = set()
						forced_flags.update(pkgsettings.useforce)
						forced_flags.update(pkgsettings.usemask)
						cur_iuse = iuses
						if myeb and not usepkgonly:
							cur_iuse = myeb.iuse.all
						if self._reinstall_for_flags(forced_flags,
							old_use, iuses,
							now_use, cur_iuse):
							break
					# 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()
						forced_flags.update(pkgsettings.useforce)
						forced_flags.update(pkgsettings.usemask)
						old_use = vardb.aux_get(cpv, ["USE"])[0].split()
						old_iuse = set(filter_iuse_defaults(
							vardb.aux_get(cpv, ["IUSE"])[0].split()))
						cur_use = pkg.use.enabled
						cur_iuse = pkg.iuse.all
						reinstall_for_flags = \
							self._reinstall_for_flags(
							forced_flags, old_use, old_iuse,
							cur_use, cur_iuse)
						if reinstall_for_flags:
							reinstall = True
					if not built:
						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)

		# Filter out any old-style virtual matches if they are
		# mixed with new-style virtual matches.
		cp = portage.dep_getkey(atom)
		if len(matched_packages) > 1 and \
			"virtual" == portage.catsplit(cp)[0]:
			for pkg in matched_packages:
				if pkg.cp != cp:
					continue
				# Got a new-style virtual, so filter
				# out any old-style virtuals.
				matched_packages = [pkg for pkg in matched_packages \
					if pkg.cp == cp]
				break

		if len(matched_packages) > 1:
			if avoid_update:
				if existing_node is not None:
					return existing_node, existing_node
				for pkg in matched_packages:
					if pkg.installed:
						return pkg, existing_node

			bestmatch = portage.best(
				[pkg.cpv for pkg in matched_packages])
			matched_packages = [pkg for pkg in matched_packages \
				if portage.dep.cpvequal(pkg.cpv, bestmatch)]

		# 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._dynamic_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):
		"""
		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 --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

		# 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
		already_deep = self._dynamic_config.myparams.get("deep") is True
		if not already_deep:
			self._dynamic_config.myparams["deep"] = True

		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:
					continue
				if arg.name in required_set_names:
					args.append(arg)
					required_set_names.remove(arg.name)
			# Create new SetArg instances only when necessary.
			for s in required_set_names:
				expanded_set = InternalPackageSet(
					initial_atoms=setconfig.getSetAtoms(s))
				atom = SETPREFIX + s
				args.append(SetArg(arg=atom, set=expanded_set,
					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
				# will be appropriately reported as a slot collision
				# (possibly solvable via backtracking).
				pkg = matches[-1] # highest match
				if not self._add_pkg(pkg, dep):
					return 0
				if not self._create_graph(allow_unsatisfied=True):
					return 0
		return 1

	def _pkg(self, cpv, type_name, root_config, installed=False, 
		onlydeps=False):
		"""
		Get a package instance from the cache, or create a new
		one if necessary. Raises PackageNotFound from aux_get if it
		failures for some reason (package does not exist or is
		corrupt).
		"""
		operation = "merge"
		if installed or onlydeps:
			operation = "nomerge"
		pkg = self._frozen_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))
			except KeyError:
				raise portage.exception.PackageNotFound(cpv)
			pkg = Package(built=(type_name != "ebuild"), cpv=cpv,
				installed=installed, metadata=metadata, onlydeps=onlydeps,
				root_config=root_config, type_name=type_name)
			self._frozen_config._pkg_cache[pkg] = pkg
		return pkg

	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
		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
			# due to the performance penalty that is incurred by all the
			# 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
					# about those that will be automatically uninstalled during
					# 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
					if pkg_in_graph:
						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:
						blockers = set(str(blocker.atom) \
							for blocker in blockers)

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

					# If blocker data from the graph is available, use
					# it to validate the cache and update the cache if
					# it seems invalid.
					if blocker_data is not None and \
						blockers is not None:
						if not blockers.symmetric_difference(
							blocker_data.atoms):
							continue
						blocker_data = None

					if blocker_data is None and \
						blockers is not None:
						# Re-use the blockers from the graph.
						blocker_atoms = sorted(blockers)
						counter = long(pkg.metadata["COUNTER"])
						blocker_data = \
							blocker_cache.BlockerData(counter, blocker_atoms)
						blocker_cache[pkg.cpv] = blocker_data
						continue

					if blocker_data:
						blocker_atoms = blocker_data.atoms
					else:
						# Use aux_get() to trigger FakeVartree global
						# updates on *DEPEND when appropriate.
						depstr = " ".join(vardb.aux_get(pkg.cpv, dep_keys))
						# It is crucial to pass in final_db here in order to
						# optimize dep_check calls by eliminating atoms via
						# dep_wordreduce and dep_eval calls.
						try:
							portage.dep._dep_check_strict = False
							try:
								success, atoms = portage.dep_check(depstr,
									final_db, pkgsettings, myuse=pkg.use.enabled,
									trees=self._dynamic_config._graph_trees, myroot=myroot)
							except Exception, e:
								if isinstance(e, SystemExit):
									raise
								# This is helpful, for example, if a ValueError
								# is thrown from cpv_expand due to multiple
								# matches (this can happen if an atom lacks a
								# category).
								show_invalid_depstring_notice(
									pkg, depstr, str(e))
								del e
								raise
						finally:
							portage.dep._dep_check_strict = True
						if not success:
							replacement_pkg = final_db.match_pkgs(pkg.slot_atom)
							if replacement_pkg and \
								replacement_pkg[0].operation == "merge":
								# This package is being replaced anyway, so
								# ignore invalid dependencies so as not to
								# annoy the user too much (otherwise they'd be
								# forced to manually unmerge it first).
								continue
							show_invalid_depstring_notice(pkg, depstr, atoms)
							return False
						blocker_atoms = [myatom for myatom in atoms \
							if myatom.startswith("!")]
						blocker_atoms.sort()
						counter = long(pkg.metadata["COUNTER"])
						blocker_cache[cpv] = \
							blocker_cache.BlockerData(counter, blocker_atoms)
					if blocker_atoms:
						try:
							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(
								pkg, depstr, "Invalid Atom: %s" % (e,))
							return False
				for cpv in stale_cache:
					del blocker_cache[cpv]
				blocker_cache.flush()
				del blocker_cache

		# 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._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 \
				not self._have_new_virt(blocker.root, blocker.cp):
				provider_virtual = True

			# Use this to check PROVIDE for each matched package
			# when necessary.
			atom_set = InternalPackageSet(
				initial_atoms=[blocker.atom])

			if provider_virtual:
				atoms = []
				for provider_entry in virtuals[blocker.cp]:
					provider_cp = \
						portage.dep_getkey(provider_entry)
					atoms.append(blocker.atom.replace(
						blocker.cp, provider_cp))
			else:
				atoms = [blocker.atom]

			blocked_initial = set()
			for atom in atoms:
				for pkg in initial_db.match_pkgs(atom):
					if atom_set.findAtomForPackage(pkg):
						blocked_initial.add(pkg)

			blocked_final = set()
			for atom in atoms:
				for pkg in final_db.match_pkgs(atom):
					if atom_set.findAtomForPackage(pkg):
						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:
					if pkg.slot_atom == parent.slot_atom and \
						not blocker.atom.blocker.overlap.forbid:
						# New !!atom blockers do not allow temporary
						# simulaneous installation, so unlike !atom
						# blockers, !!atom blockers aren't ignored
						# when they match other packages occupying
						# the same slot.
						continue
					if parent.installed:
						# Two currently installed packages conflict with
						# eachother. Ignore this case since the damage
						# is already done and this would be likely to
						# 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
						# unmerged to resolve this block.
						depends_on_order.add((pkg, parent))
						continue
					# None of the above blocker resolutions techniques apply,
					# so apparently this one is unresolvable.
					unresolved_blocks = True
				for pkg in blocked_final:
					if pkg.slot_atom == parent.slot_atom and \
						not blocker.atom.blocker.overlap.forbid:
						# New !!atom blockers do not allow temporary
						# simulaneous installation, so unlike !atom
						# blockers, !!atom blockers aren't ignored
						# when they match other packages occupying
						# the same slot.
						continue
					if parent.operation == "nomerge" and \
						pkg.operation == "nomerge":
						# This blocker will be handled the next time that a
						# 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.
					if parent.operation == "merge" and pkg.installed:
						depends_on_order.add((pkg, parent))
						continue
					elif parent.operation == "nomerge":
						depends_on_order.add((parent, pkg))
						continue
					# None of the above blocker resolutions techniques apply,
					# so apparently this one is unresolvable.
					unresolved_blocks = True

				# Make sure we don't unmerge any package that have been pulled
				# 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

				if not unresolved_blocks and depends_on_order:
					for inst_pkg, inst_task in depends_on_order:
						uninst_task = Package(built=inst_pkg.built,
							cpv=inst_pkg.cpv, installed=inst_pkg.installed,
							metadata=inst_pkg.metadata,
							operation="uninstall",
							root_config=inst_pkg.root_config,
							type_name=inst_pkg.type_name)
						# 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

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

	def _merge_order_bias(self, mygraph):
		"""
		For optimal leaf node selection, promote deep system runtime deps and
		order nodes from highest to lowest overall reference count.
		"""

		node_info = {}
		for node in mygraph.order:
			node_info[node] = len(mygraph.parent_nodes(node))
		deep_system_deps = _find_deep_system_runtime_deps(mygraph)

		def cmp_merge_preference(node1, node2):

			if node1.operation == 'uninstall':
				if node2.operation == 'uninstall':
					return 0
				return 1

			if node2.operation == 'uninstall':
				if node1.operation == 'uninstall':
					return 0
				return -1

			node1_sys = node1 in deep_system_deps
			node2_sys = node2 in deep_system_deps
			if node1_sys != node2_sys:
				if node1_sys:
					return -1
				return 1

			return node_info[node2] - node_info[node1]

		mygraph.order.sort(key=cmp_sort_key(cmp_merge_preference))

	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

	def schedulerGraph(self):
		"""
		The scheduler graph is identical to the normal one except that
		uninstall edges are reversed in specific cases that require
		conflicting packages to be temporarily installed simultaneously.
		This is intended for use by the Scheduler in it's parallelization
		logic. It ensures that temporary simultaneous installation of
		conflicting packages is avoided when appropriate (especially for
		!!atom blockers), but allowed in specific cases that require it.

		Note that this method calls break_refs() which alters the state of
		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):
		"""
		Take a mergelist like that returned from self.altlist() and
		break any references that lead back to the depgraph. This is
		useful if you want to hold references to packages without
		also holding the depgraph on the heap.
		"""
		for node in nodes:
			if hasattr(node, "root_config"):
				# The FakeVartree references the _package_cache which
				# references the depgraph. So that Package instances don't
				# hold the depgraph and FakeVartree on the heap, replace
				# the RootConfig that references the FakeVartree with the
				# 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():
			raise self._unknown_internal_error()

		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
		# such as revdep-rebuild.
		removed_nodes = set()
		while True:
			for node in mygraph.root_nodes():
				if not isinstance(node, Package) or \
					node.installed or node.onlydeps:
					removed_nodes.add(node)
			if removed_nodes:
				self._spinner_update()
				mygraph.difference_update(removed_nodes)
			if not removed_nodes:
				break
			removed_nodes.clear()
		self._merge_order_bias(mygraph)
		def cmp_circular_bias(n1, n2):
			"""
			RDEPEND is stronger than PDEPEND and this function
			measures such a strength bias within a circular
			dependency relationship.
			"""
			n1_n2_medium = n2 in mygraph.child_nodes(n1,
				ignore_priority=priority_range.ignore_medium_soft)
			n2_n1_medium = n1 in mygraph.child_nodes(n2,
				ignore_priority=priority_range.ignore_medium_soft)
			if n1_n2_medium == n2_n1_medium:
				return 0
			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.
		scheduled_uninstalls = set()
		# Contains any Uninstall tasks that have been ignored
		# in order to avoid the circular deps code path. These
		# correspond to blocker conflicts that could not be
		# resolved.
		ignored_uninstall_tasks = set()
		have_uninstall_task = False
		complete = "complete" in self._dynamic_config.myparams
		asap_nodes = []

		def get_nodes(**kwargs):
			"""
			Returns leaf nodes excluding Uninstall instances
			since those should be executed as late as possible.
			"""
			return [node for node in mygraph.leaf_nodes(**kwargs) \
				if isinstance(node, Package) and \
					(node.operation != "uninstall" or \
					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:
			running_portage = running_portage[0]
		else:
			running_portage = None

		if replacement_portage:
			replacement_portage = replacement_portage[0]
		else:
			replacement_portage = None

		if replacement_portage == running_portage:
			replacement_portage = None

		if replacement_portage is not None:
			# update from running_portage to replacement_portage asap
			asap_nodes.append(replacement_portage)

		if running_portage is not None:
			try:
				portage_rdepend = self._select_atoms_highest_available(
					running_root, running_portage.metadata["RDEPEND"],
					myuse=running_portage.use.enabled,
					parent=running_portage, strict=False)
			except portage.exception.InvalidDependString, e:
				portage.writemsg("!!! Invalid RDEPEND in " + \
					"'%svar/db/pkg/%s/RDEPEND': %s\n" % \
					(running_root, running_portage.cpv, e), noiselevel=-1)
				del e
				portage_rdepend = []
			runtime_deps.update(atom for atom in portage_rdepend \
				if not atom.startswith("!"))

		def gather_deps(ignore_priority, mergeable_nodes,
			selected_nodes, node):
			"""
			Recursively gather a group of nodes that RDEPEND on
			eachother. This ensures that they are merged as a group
			and get their RDEPENDs satisfied as soon as possible.
			"""
			if node in selected_nodes:
				return True
			if node not in mergeable_nodes:
				return False
			if node == replacement_portage and \
				mygraph.child_nodes(node,
				ignore_priority=priority_range.ignore_medium_soft):
				# Make sure that portage always has all of it's
				# RDEPENDs installed first.
				return False
			selected_nodes.add(node)
			for child in mygraph.child_nodes(node,
				ignore_priority=ignore_priority):
				if not gather_deps(ignore_priority,
					mergeable_nodes, selected_nodes, child):
					return False
			return True

		def ignore_uninst_or_med(priority):
			if priority is BlockerDepPriority.instance:
				return True
			return priority_range.ignore_medium(priority)

		def ignore_uninst_or_med_soft(priority):
			if priority is BlockerDepPriority.instance:
				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
		# successfully selected.
		prefer_asap = True

		# Controls whether or not the current iteration should drop edges that
		# are "satisfied" by installed packages, in order to solve circular
		# dependencies. The deep runtime dependencies of installed packages are
		# not checked in this case (bug #199856), so it must be avoided
		# whenever possible.
		drop_satisfied = False

		# State of variables for successive iterations that loosen the
		# criteria for node selection.
		#
		# iteration   prefer_asap   drop_satisfied
		# 1           True          False
		# 2           False         False
		# 3           False         True
		#
		# If no nodes are selected on the last iteration, it is due to
		# unresolved blockers or circular dependencies.

		while not mygraph.empty():
			self._spinner_update()
			selected_nodes = None
			ignore_priority = None
			if drop_satisfied or (prefer_asap and asap_nodes):
				priority_range = DepPrioritySatisfiedRange
			else:
				priority_range = DepPriorityNormalRange
			if prefer_asap and asap_nodes:
				# ASAP nodes are merged before their soft deps. Go ahead and
				# select root nodes here if necessary, since it's typical for
				# the parent to have been removed from the graph already.
				asap_nodes = [node for node in asap_nodes \
					if mygraph.contains(node)]
				for node in asap_nodes:
					if not mygraph.child_nodes(node,
						ignore_priority=priority_range.ignore_soft):
						selected_nodes = [node]
						asap_nodes.remove(node)
						break
			if not selected_nodes and \
				not (prefer_asap and asap_nodes):
				for i in xrange(priority_range.NONE,
					priority_range.MEDIUM_SOFT + 1):
					ignore_priority = priority_range.ignore_priority[i]
					nodes = get_nodes(ignore_priority=ignore_priority)
					if nodes:
						# If there is a mixture of merges and uninstalls,
						# do the uninstalls first.
						if len(nodes) > 1:
							good_uninstalls = []
							for node in nodes:
								if node.operation == "uninstall":
									good_uninstalls.append(node)

							if good_uninstalls:
								nodes = good_uninstalls
							else:
								nodes = nodes

						if ignore_priority is None and not tree_mode:
							# Greedily pop all of these nodes since no
							# relationship has been ignored. This optimization
							# destroys --tree output, so it's disabled in tree
							# mode.
							selected_nodes = nodes
						else:
							# For optimal merge order:
							#  * Only pop one node.
							#  * Removing a root node (node without a parent)
							#    will not produce a leaf node, so avoid it.
							#  * It's normal for a selected uninstall to be a
							#    root node, so don't check them for parents.
							for node in nodes:
								if node.operation == "uninstall" or \
									mygraph.parent_nodes(node):
									selected_nodes = [node]
									break

						if selected_nodes:
							break

			if not selected_nodes:
				nodes = get_nodes(ignore_priority=priority_range.ignore_medium)
				if nodes:
					mergeable_nodes = set(nodes)
					if prefer_asap and asap_nodes:
						nodes = asap_nodes
					for i in xrange(priority_range.SOFT,
						priority_range.MEDIUM_SOFT + 1):
						ignore_priority = priority_range.ignore_priority[i]
						for node in nodes:
							if not mygraph.parent_nodes(node):
								continue
							selected_nodes = set()
							if gather_deps(ignore_priority,
								mergeable_nodes, selected_nodes, node):
								break
							else:
								selected_nodes = None
						if selected_nodes:
							break

					if prefer_asap and asap_nodes and not selected_nodes:
						# We failed to find any asap nodes to merge, so ignore
						# them for the next iteration.
						prefer_asap = False
						continue

			if selected_nodes and ignore_priority is not None:
				# Try to merge ignored medium_soft deps as soon as possible
				# if they're not satisfied by installed packages.
				for node in selected_nodes:
					children = set(mygraph.child_nodes(node))
					soft = children.difference(
						mygraph.child_nodes(node,
						ignore_priority=DepPrioritySatisfiedRange.ignore_soft))
					medium_soft = children.difference(
						mygraph.child_nodes(node,
							ignore_priority = \
							DepPrioritySatisfiedRange.ignore_medium_soft))
					medium_soft.difference_update(soft)
					for child in medium_soft:
						if child in selected_nodes:
							continue
						if child in asap_nodes:
							continue
						asap_nodes.append(child)

			if selected_nodes and len(selected_nodes) > 1:
				if not isinstance(selected_nodes, list):
					selected_nodes = list(selected_nodes)
				selected_nodes.sort(key=cmp_sort_key(cmp_circular_bias))

			if not selected_nodes and not myblocker_uninstalls.is_empty():
				# An Uninstall task needs to be executed in order to
				# avoid conflict if possible.

				if drop_satisfied:
					priority_range = DepPrioritySatisfiedRange
				else:
					priority_range = DepPriorityNormalRange

				mergeable_nodes = get_nodes(
					ignore_priority=ignore_uninst_or_med)

				min_parent_deps = None
				uninst_task = None
				for task in myblocker_uninstalls.leaf_nodes():
					# Do some sanity checks so that system or world packages
					# don't get uninstalled inappropriately here (only really
					# necessary when --complete-graph has not been enabled).

					if task in ignored_uninstall_tasks:
						continue

					if task in scheduled_uninstalls:
						# It's been scheduled but it hasn't
						# been executed yet due to dependence
						# on installation of blocking packages.
						continue

					root_config = self._frozen_config.roots[task.root]
					inst_pkg = self._pkg(task.cpv, "installed", root_config,
						installed=True)

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

					forbid_overlap = False
					heuristic_overlap = False
					for blocker in myblocker_uninstalls.parent_nodes(task):
						if blocker.eapi in ("0", "1"):
							heuristic_overlap = True
						elif blocker.atom.blocker.overlap.forbid:
							forbid_overlap = True
							break
					if forbid_overlap and running_root == task.root:
						continue

					if heuristic_overlap and running_root == task.root:
						# Never uninstall sys-apps/portage or it's essential
						# dependencies, except through replacement.
						try:
							runtime_dep_atoms = \
								list(runtime_deps.iterAtomsForPackage(task))
						except portage.exception.InvalidDependString, e:
							portage.writemsg("!!! Invalid PROVIDE in " + \
								"'%svar/db/pkg/%s/PROVIDE': %s\n" % \
								(task.root, task.cpv, e), noiselevel=-1)
							del e
							continue

						# Don't uninstall a runtime dep if it appears
						# to be the only suitable one installed.
						skip = False
						vardb = root_config.trees["vartree"].dbapi
						for atom in runtime_dep_atoms:
							other_version = None
							for pkg in vardb.match_pkgs(atom):
								if pkg.cpv == task.cpv and \
									pkg.metadata["COUNTER"] == \
									task.metadata["COUNTER"]:
									continue
								other_version = pkg
								break
							if other_version is None:
								skip = True
								break
						if skip:
							continue

						# For packages in the system set, don't take
						# any chances. If the conflict can't be resolved
						# by a normal replacement operation then abort.
						skip = False
						try:
							for atom in root_config.sets[
								"system"].iterAtomsForPackage(task):
								skip = True
								break
						except portage.exception.InvalidDependString, e:
							portage.writemsg("!!! Invalid PROVIDE in " + \
								"'%svar/db/pkg/%s/PROVIDE': %s\n" % \
								(task.root, task.cpv, e), noiselevel=-1)
							del e
							skip = True
						if skip:
							continue

					# Note that the world check isn't always
					# necessary since self._complete_graph() will
					# add all packages from the system and world sets to the
					# graph. This just allows unresolved conflicts to be
					# detected as early as possible, which makes it possible
					# to avoid calling self._complete_graph() when it is
					# unnecessary due to blockers triggering an abortion.
					if not complete:
						# 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[
								"world"].iterAtomsForPackage(task):
								satisfied = False
								for pkg in graph_db.match_pkgs(atom):
									if pkg == inst_pkg:
										continue
									satisfied = True
									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 " + \
								"'%svar/db/pkg/%s/PROVIDE': %s\n" % \
								(task.root, task.cpv, e), noiselevel=-1)
							del e
							skip = True
						if skip:
							continue

					# Check the deps of parent nodes to ensure that
					# the chosen task produces a leaf node. Maybe
					# this can be optimized some more to make the
					# best possible choice, but the current algorithm
					# is simple and should be near optimal for most
					# common cases.
					mergeable_parent = False
					parent_deps = set()
					for parent in mygraph.parent_nodes(task):
						parent_deps.update(mygraph.child_nodes(parent,
							ignore_priority=priority_range.ignore_medium_soft))
						if parent in mergeable_nodes and \
							gather_deps(ignore_uninst_or_med_soft,
							mergeable_nodes, set(), parent):
							mergeable_parent = True

					if not mergeable_parent:
						continue

					parent_deps.remove(task)
					if min_parent_deps is None or \
						len(parent_deps) < min_parent_deps:
						min_parent_deps = len(parent_deps)
						uninst_task = task

				if uninst_task is not None:
					# The uninstall is performed only after blocking
					# packages have been merged on top of it. File
					# collisions between blocking packages are detected
					# and removed from the list of files to be uninstalled.
					scheduled_uninstalls.add(uninst_task)
					parent_nodes = mygraph.parent_nodes(uninst_task)

					# Reverse the parent -> uninstall edges since we want
					# to do the uninstall after blocking packages have
					# been merged on top of it.
					mygraph.remove(uninst_task)
					for blocked_pkg in parent_nodes:
						mygraph.add(blocked_pkg, uninst_task,
							priority=BlockerDepPriority.instance)
						scheduler_graph.remove_edge(uninst_task, blocked_pkg)
						scheduler_graph.add(blocked_pkg, uninst_task,
							priority=BlockerDepPriority.instance)

					# Sometimes a merge node will render an uninstall
					# node unnecessary (due to occupying the same SLOT),
					# and we want to avoid executing a separate uninstall
					# task in that case.
					slot_node = self._dynamic_config.mydbapi[uninst_task.root
						].match_pkgs(uninst_task.slot_atom)
					if slot_node and \
						slot_node[0].operation == "merge":
						mygraph.add(slot_node[0], uninst_task,
							priority=BlockerDepPriority.instance)

					# Reset the state variables for leaf node selection and
					# continue trying to select leaf nodes.
					prefer_asap = True
					drop_satisfied = False
					continue

			if not selected_nodes:
				# Only select root nodes as a last resort. This case should
				# only trigger when the graph is nearly empty and the only
				# remaining nodes are isolated (no parents or children). Since
				# the nodes must be isolated, ignore_priority is not needed.
				selected_nodes = get_nodes()

			if not selected_nodes and not drop_satisfied:
				drop_satisfied = True
				continue

			if not selected_nodes and not myblocker_uninstalls.is_empty():
				# If possible, drop an uninstall task here in order to avoid
				# the circular deps code path. The corresponding blocker will
				# still be counted as an unresolved conflict.
				uninst_task = None
				for node in myblocker_uninstalls.leaf_nodes():
					try:
						mygraph.remove(node)
					except KeyError:
						pass
					else:
						uninst_task = node
						ignored_uninstall_tasks.add(node)
						break

				if uninst_task is not None:
					# Reset the state variables for leaf node selection and
					# continue trying to select leaf nodes.
					prefer_asap = True
					drop_satisfied = False
					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
			# reset state variables for leaf node selection.
			prefer_asap = True
			drop_satisfied = False

			mygraph.difference_update(selected_nodes)

			for node in selected_nodes:
				if isinstance(node, Package) and \
					node.operation == "nomerge":
					continue

				# Handle interactions between blockers
				# and uninstallation tasks.
				solved_blockers = set()
				uninst_task = None
				if isinstance(node, Package) and \
					"uninstall" == node.operation:
					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
						# the corresponding Uninstall task if necessary.
						previous_cpv = previous_cpv[0]
						uninst_task = \
							("installed", node.root, previous_cpv, "uninstall")
						try:
							mygraph.remove(uninst_task)
						except KeyError:
							pass

				if uninst_task is not None and \
					uninst_task not in ignored_uninstall_tasks and \
					myblocker_uninstalls.contains(uninst_task):
					blocker_nodes = myblocker_uninstalls.parent_nodes(uninst_task)
					myblocker_uninstalls.remove(uninst_task)
					# Discard any blockers that this Uninstall solves.
					for blocker in blocker_nodes:
						if not myblocker_uninstalls.child_nodes(blocker):
							myblocker_uninstalls.remove(blocker)
							solved_blockers.add(blocker)

				retlist.append(node)

				if (isinstance(node, Package) and \
					"uninstall" == node.operation) or \
					(uninst_task is not None and \
					uninst_task in scheduled_uninstalls):
					# Include satisfied blockers in the merge list
					# since the user might be interested and also
					# it serves as an indicator that blocking packages
					# will be temporarily installed simultaneously.
					for blocker in solved_blockers:
						retlist.append(Blocker(atom=blocker.atom,
							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)

		for blocker in unsolvable_blockers:
			retlist.append(blocker)

		# If any Uninstall tasks need to be executed in order
		# to avoid a conflict, complete the graph with any
		# dependencies that may have been initially
		# neglected (to ensure that unsafe Uninstall tasks
		# are properly identified and blocked from execution).
		if have_uninstall_task and \
			not complete and \
			not unsolvable_blockers:
			self._dynamic_config.myparams["complete"] = True
			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

	def _show_circular_deps(self, mygraph):
		# No leaf nodes are available, so we have a circular
		# dependency panic situation.  Reduce the noise level to a
		# minimum via repeated elimination of root nodes since they
		# have no parents and thus can not be part of a cycle.
		while True:
			root_nodes = mygraph.root_nodes(
				ignore_priority=DepPrioritySatisfiedRange.ignore_medium_soft)
			if not root_nodes:
				break
			mygraph.difference_update(root_nodes)
		# Display the USE flags that are enabled on nodes that are part
		# of dependency cycles in case that helps the user decide to
		# disable some of them.
		display_order = []
		tempgraph = mygraph.copy()
		while not tempgraph.empty():
			nodes = tempgraph.leaf_nodes()
			if not nodes:
				node = tempgraph.order[0]
			else:
				node = nodes[0]
			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", " * ")
		portage.writemsg("\n", noiselevel=-1)
		portage.writemsg(prefix + "Error: circular dependencies:\n",
			noiselevel=-1)
		portage.writemsg("\n", noiselevel=-1)
		mygraph.debug_print()
		portage.writemsg("\n", noiselevel=-1)
		portage.writemsg(prefix + "Note that circular dependencies " + \
			"can often be avoided by temporarily\n", noiselevel=-1)
		portage.writemsg(prefix + "disabling USE flags that trigger " + \
			"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)

	def _show_unsatisfied_blockers(self, blockers):
		self._show_merge_list()
		msg = "Error: The above package list contains " + \
			"packages which cannot be installed " + \
			"at the same time on the same system."
		prefix = colorize("BAD", " * ")
		from textwrap import wrap
		portage.writemsg("\n", noiselevel=-1)
		for line in wrap(msg, 70):
			portage.writemsg(prefix + line + "\n", noiselevel=-1)

		# Display the conflicting packages along with the packages
		# that pulled them in. This is helpful for troubleshooting
		# cases in which blockers don't solve automatically and
		# the reasons are not apparent from the normal merge list
		# display.

		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:
					conflict_pkgs[pkg] = parent_atoms

		if conflict_pkgs:
			# Reduce noise by pruning packages that are only
			# pulled in by other conflict packages.
			pruned_pkgs = set()
			for pkg, parent_atoms in conflict_pkgs.iteritems():
				relevant_parent = False
				for parent, atom in parent_atoms:
					if parent not in conflict_pkgs:
						relevant_parent = True
						break
				if not relevant_parent:
					pruned_pkgs.add(pkg)
			for pkg in pruned_pkgs:
				del conflict_pkgs[pkg]

		if conflict_pkgs:
			msg = []
			msg.append("\n")
			indent = "  "
			# Max number of parents shown, to avoid flooding the display.
			max_parents = 3
			for pkg, parent_atoms in conflict_pkgs.iteritems():

				pruned_list = set()

				# Prefer packages that are not directly involved in a conflict.
				for parent_atom in parent_atoms:
					if len(pruned_list) >= max_parents:
						break
					parent, atom = parent_atom
					if parent not in conflict_pkgs:
						pruned_list.add(parent_atom)

				for parent_atom in parent_atoms:
					if len(pruned_list) >= max_parents:
						break
					pruned_list.add(parent_atom)

				omitted_parents = len(parent_atoms) - len(pruned_list)
				msg.append(indent + "%s pulled in by\n" % pkg)

				for parent_atom in pruned_list:
					parent, atom = parent_atom
					msg.append(2*indent)
					if isinstance(parent,
						(PackageArg, AtomArg)):
						# For PackageArg and AtomArg types, it's
						# redundant to display the atom attribute.
						msg.append(str(parent))
					else:
						# Display the specific atom from SetArg or
						# Package types.
						msg.append("%s required by %s" % (atom, parent))
					msg.append("\n")

				if omitted_parents:
					msg.append(2*indent)
					msg.append("(and %d more)\n" % omitted_parents)

				msg.append("\n")

			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
					removed = enabled
				else:
					disabled = []
					removed = []
				cur_iuse = set(cur_iuse)
				enabled_flags = cur_iuse.intersection(cur_use)
				removed_iuse = set(old_iuse).difference(cur_iuse)
				any_iuse = cur_iuse.union(old_iuse)
				any_iuse = list(any_iuse)
				any_iuse.sort()
				for flag in any_iuse:
					flag_str = None
					isEnabled = False
					reinst_flag = reinst_flags and flag in reinst_flags
					if flag in enabled_flags:
						isEnabled = True
						if is_new or flag in old_use and \
							(all_flags or reinst_flag):
							flag_str = red(flag)
						elif flag not in old_iuse:
							flag_str = yellow(flag) + "%*"
						elif flag not in old_use:
							flag_str = green(flag) + "*"
					elif flag in removed_iuse:
						if all_flags or reinst_flag:
							flag_str = yellow("-" + flag) + "%"
							if flag in old_use:
								flag_str += "*"
							flag_str = "(" + flag_str + ")"
							removed.append(flag_str)
						continue
					else:
						if is_new or flag in old_iuse and \
							flag not in old_use and \
							(all_flags or reinst_flag):
							flag_str = blue("-" + flag)
						elif flag not in old_iuse:
							flag_str = yellow("-" + flag)
							if flag not in iuse_forced:
								flag_str += "%"
						elif flag in old_use:
							flag_str = green("-" + flag) + "*"
					if flag_str:
						if flag in iuse_forced:
							flag_str = "(" + flag_str + ")"
						if isEnabled:
							enabled.append(flag_str)
						else:
							disabled.append(flag_str)

				if alphabetical:
					ret = " ".join(enabled)
				else:
					ret = " ".join(enabled + disabled + removed)
				if ret:
					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._pkg(uninstall.cpv, "installed",
				uninstall.root_config, installed=True)

			try:
				mygraph.remove(inst_pkg)
			except KeyError:
				pass

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

			# Break the Package -> Uninstall edges.
			mygraph.remove(uninstall)

			# Resolution of a package's blockers
			# depend on it's own uninstallation.
			for blocker in inst_pkg_blockers:
				mygraph.add(uninstall, blocker)

			# Expand Package -> Uninstall edges into
			# Package -> Blocker -> Uninstall edges.
			for blocker in uninstall_parents:
				mygraph.add(uninstall, blocker)
				for parent in self._dynamic_config._blocker_parents.parent_nodes(blocker):
					if parent != inst_pkg:
						mygraph.add(blocker, parent)

			# If the uninstall task did not need to be executed because
			# of an upgrade, display Blocker -> Upgrade edges since the
			# corresponding Blocker -> Uninstall edges will not be shown.
			upgrade_node = \
				self._dynamic_config._slot_pkg_map[uninstall.root].get(uninstall.slot_atom)
			if upgrade_node is not None and \
				uninstall not in executed_uninstalls:
				for blocker in uninstall_parents:
					mygraph.add(upgrade_node, blocker)

		unsatisfied_blockers = []
		i = 0
		depth = 0
		shown_edges = set()
		for x in mylist:
			if isinstance(x, Blocker) and not x.satisfied:
				unsatisfied_blockers.append(x)
				continue
			graph_key = x
			if "--tree" in self._frozen_config.myopts:
				depth = len(tree_nodes)
				while depth and graph_key not in \
					mygraph.child_nodes(tree_nodes[depth-1]):
						depth -= 1
				if depth:
					tree_nodes = tree_nodes[:depth]
					tree_nodes.append(graph_key)
					display_list.append((x, depth, True))
					shown_edges.add((graph_key, tree_nodes[depth-1]))
				else:
					traversed_nodes = set() # prevent endless circles
					traversed_nodes.add(graph_key)
					def add_parents(current_node, ordered):
						parent_nodes = None
						# Do not traverse to parents if this node is an
						# an argument or a direct member of a set that has
						# been specified as an argument (system or world).
						if current_node not in self._dynamic_config._set_nodes:
							parent_nodes = mygraph.parent_nodes(current_node)
						if parent_nodes:
							child_nodes = set(mygraph.child_nodes(current_node))
							selected_parent = None
							# First, try to avoid a direct cycle.
							for node in parent_nodes:
								if not isinstance(node, (Blocker, Package)):
									continue
								if node not in traversed_nodes and \
									node not in child_nodes:
									edge = (current_node, node)
									if edge in shown_edges:
										continue
									selected_parent = node
									break
							if not selected_parent:
								# A direct cycle is unavoidable.
								for node in parent_nodes:
									if not isinstance(node, (Blocker, Package)):
										continue
									if node not in traversed_nodes:
										edge = (current_node, node)
										if edge in shown_edges:
											continue
										selected_parent = node
										break
							if selected_parent:
								shown_edges.add((current_node, selected_parent))
								traversed_nodes.add(selected_parent)
								add_parents(selected_parent, False)
						display_list.append((current_node,
							len(tree_nodes), ordered))
						tree_nodes.append(current_node)
					tree_nodes = []
					add_parents(graph_key, True)
			else:
				display_list.append((x, depth, True))
		mylist = display_list
		for x in unsatisfied_blockers:
			mylist.append((x, 0, True))

		last_merge_depth = 0
		for i in xrange(len(mylist)-1,-1,-1):
			graph_key, depth, ordered = mylist[i]
			if not ordered and depth == 0 and i > 0 \
				and graph_key == mylist[i-1][0] and \
				mylist[i-1][1] == 0:
				# An ordered node got a consecutive duplicate when the tree was
				# being filled in.
				del mylist[i]
				continue
			if ordered and graph_key[-1] != "nomerge":
				last_merge_depth = depth
				continue
			if depth >= last_merge_depth or \
				i < len(mylist) - 1 and \
				depth >= mylist[i+1][1]:
					del mylist[i]

		# files to fetch list - avoids counting a same file twice
		# in size display (verbose mode)
		myfetchlist=[]

		# Use this set to detect when all the "repoadd" strings are "[0]"
		# and disable the entire repo display in this case.
		repoadd_set = set()

		for mylist_index in xrange(len(mylist)):
			x, depth, ordered = mylist[mylist_index]
			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

			if isinstance(x, Blocker):
				if x.satisfied:
					blocker_style = "PKG_BLOCKER_SATISFIED"
					addl = "%s  %s  " % (colorize(blocker_style, "b"), fetch)
				else:
					blocker_style = "PKG_BLOCKER"
					addl = "%s  %s  " % (colorize(blocker_style, "B"), fetch)
				if ordered:
					counters.blocks += 1
					if x.satisfied:
						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]:
					addl += colorize(blocker_style,
						" (\"%s\" is blocking %s)") % \
						(str(x.atom).lstrip("!"), block_parents)
				else:
					addl += colorize(blocker_style,
						" (is blocking %s)") % block_parents
				if isinstance(x, Blocker) and x.satisfied:
					if columns:
						continue
					p.append(addl)
				else:
					blockers.append(addl)
			else:
				pkg_status = x[3]
				pkg_merge = ordered and pkg_status == "merge"
				if not pkg_merge and pkg_status == "merge":
					pkg_status = "nomerge"
				built = pkg_type != "ebuild"
				installed = pkg_type == "installed"
				pkg = x
				metadata = pkg.metadata
				ebuild_path = None
				repo_name = metadata["repository"]
				if pkg_type == "ebuild":
					ebuild_path = portdb.findname(pkg_key)
					if not ebuild_path: # shouldn't happen
						raise portage.exception.PackageNotFound(pkg_key)
					repo_path_real = os.path.dirname(os.path.dirname(
						os.path.dirname(ebuild_path)))
				else:
					repo_path_real = portdb.getRepositoryPath(repo_name)
				pkg_use = list(pkg.use.enabled)
				if not pkg.built and pkg.operation == 'merge' and \
					'fetch' in pkg.metadata.restrict:
					fetch = red("F")
					if ordered:
						counters.restrict_fetch += 1
					if portdb.fetch_check(pkg_key, pkg_use):
						fetch = green("f")
						if ordered:
							counters.restrict_fetch_satisfied += 1

				#we need to use "--emptrytree" testing here rather than "empty" param testing because "empty"
				#param is used for -u, where you still *do* want to see when something is being upgraded.
				myoldbest = []
				myinslotlist = None
				installed_versions = vardb.match(portage.cpv_getkey(pkg_key))
				if vardb.cpv_exists(pkg_key):
					addl="  "+yellow("R")+fetch+"  "
					if ordered:
						if pkg_merge:
							counters.reinst += 1
						elif pkg_status == "uninstall":
							counters.uninst += 1
				# filter out old-style virtual matches
				elif installed_versions and \
					portage.cpv_getkey(installed_versions[0]) == \
					portage.cpv_getkey(pkg_key):
					myinslotlist = vardb.match(pkg.slot_atom)
					# If this is the first install of a new-style virtual, we
					# need to filter out old-style virtual matches.
					if myinslotlist and \
						portage.cpv_getkey(myinslotlist[0]) != \
						portage.cpv_getkey(pkg_key):
						myinslotlist = None
					if myinslotlist:
						myoldbest = myinslotlist[:]
						addl = "   " + fetch
						if not portage.dep.cpvequal(pkg_key,
							portage.best([pkg_key] + myoldbest)):
							# Downgrade in slot
							addl += turquoise("U")+blue("D")
							if ordered:
								counters.downgrades += 1
						else:
							# Update in slot
							addl += turquoise("U") + " "
							if ordered:
								counters.upgrades += 1
					else:
						# New slot, mark it new.
						addl = " " + green("NS") + fetch + "  "
						myoldbest = vardb.match(portage.cpv_getkey(pkg_key))
						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(
								portdb.findname(pkg_key),
								inst_matches[0], pkg_key))
				else:
					addl = " " + green("N") + " " + fetch + "  "
					if ordered:
						counters.new += 1

				verboseadd = ""
				repoadd = None

				if True:
					# USE flag display
					forced_flags = set()
					pkgsettings.setcpv(pkg) # for package.use.{mask,force}
					forced_flags.update(pkgsettings.useforce)
					forced_flags.update(pkgsettings.usemask)

					cur_use = [flag for flag in pkg.use.enabled \
						if flag in pkg.iuse.all]
					cur_iuse = sorted(pkg.iuse.all)

					if myoldbest and myinslotlist:
						previous_cpv = myoldbest[0]
					else:
						previous_cpv = pkg.cpv
					if vardb.cpv_exists(previous_cpv):
						old_iuse, old_use = vardb.aux_get(
								previous_cpv, ["IUSE", "USE"])
						old_iuse = list(set(
							filter_iuse_defaults(old_iuse.split())))
						old_iuse.sort()
						old_use = old_use.split()
						is_new = False
					else:
						old_iuse = []
						old_use = []
						is_new = True

					old_use = [flag for flag in old_use if flag in old_iuse]

					use_expand = pkgsettings["USE_EXPAND"].lower().split()
					use_expand.sort()
					use_expand.reverse()
					use_expand_hidden = \
						pkgsettings["USE_EXPAND_HIDDEN"].lower().split()

					def map_to_use_expand(myvals, forcedFlags=False,
						removeHidden=True):
						ret = {}
						forced = {}
						for exp in use_expand:
							ret[exp] = []
							forced[exp] = set()
							for val in myvals[:]:
								if val.startswith(exp.lower()+"_"):
									if val in forced_flags:
										forced[exp].add(val[len(exp)+1:])
									ret[exp].append(val[len(exp)+1:])
									myvals.remove(val)
						ret["USE"] = myvals
						forced["USE"] = [val for val in myvals \
							if val in forced_flags]
						if removeHidden:
							for exp in use_expand_hidden:
								ret.pop(exp, None)
						if forcedFlags:
							return ret, forced
						return ret

					# 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(
							list(reinstall_for_flags), removeHidden=False)
						for k in list(reinst_flags_map):
							if not reinst_flags_map[k]:
								del reinst_flags_map[k]
						if not reinst_flags_map.get("USE"):
							reinst_expand_map = reinst_flags_map.copy()
							reinst_expand_map.pop("USE", None)
					if reinst_expand_map and \
						not set(reinst_expand_map).difference(
						use_expand_hidden):
						use_expand_hidden = \
							set(use_expand_hidden).difference(
							reinst_expand_map)

					cur_iuse_map, iuse_forced = \
						map_to_use_expand(cur_iuse, forcedFlags=True)
					cur_use_map = map_to_use_expand(cur_use)
					old_iuse_map = map_to_use_expand(old_iuse)
					old_use_map = map_to_use_expand(old_use)

					use_expand.sort()
					use_expand.insert(0, "USE")
					
					for key in use_expand:
						if key in use_expand_hidden:
							continue
						verboseadd += create_use_string(key.upper(),
							cur_iuse_map[key], iuse_forced[key],
							cur_use_map[key], old_iuse_map[key],
							old_use_map[key], is_new,
							reinst_flags_map.get(key))

				if verbosity == 3:
					# size verbose
					mysize=0
					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))
							del e
							return 1
						if myfilesdict is None:
							myfilesdict="[empty/missing/bad digest]"
						else:
							for myfetchfile in myfilesdict:
								if myfetchfile not in myfetchlist:
									mysize+=myfilesdict[myfetchfile]
									myfetchlist.append(myfetchfile)
							if ordered:
								counters.totalsize += mysize
						verboseadd += format_size(mysize)

					# overlay verbose
					# assign index for a previous version in the same slot
					has_previous = False
					repo_name_prev = None
					slot_atom = "%s:%s" % (portage.dep_getkey(pkg_key),
						metadata["SLOT"])
					slot_matches = vardb.match(slot_atom)
					if slot_matches:
						has_previous = True
						repo_name_prev = vardb.aux_get(slot_matches[0],
							["repository"])[0]

					# now use the data to generate output
					if pkg.installed or not has_previous:
						repoadd = repo_display.repoStr(repo_path_real)
					else:
						repo_path_prev = None
						if repo_name_prev:
							repo_path_prev = portdb.getRepositoryPath(
								repo_name_prev)
						if repo_path_prev == repo_path_real:
							repoadd = repo_display.repoStr(repo_path_real)
						else:
							repoadd = "%s=>%s" % (
								repo_display.repoStr(repo_path_prev),
								repo_display.repoStr(repo_path_real))
					if repoadd:
						repoadd_set.add(repoadd)

				xs = [portage.cpv_getkey(pkg_key)] + \
					list(portage.catpkgsplit(pkg_key)[2:])
				if xs[2] == "r0":
					xs[2] = ""
				else:
					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

				# Convert myoldbest from a list to a string.
				if not myoldbest:
					myoldbest = ""
				else:
					for pos, key in enumerate(myoldbest):
						key = portage.catpkgsplit(key)[2] + \
							"-" + portage.catpkgsplit(key)[3]
						if key[-3:] == "-r0":
							key = key[:-3]
						myoldbest[pos] = key
					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 = False
				pkg_world = False
				try:
					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):
							pkg_world = True
				except portage.exception.InvalidDependString:
					# This is reported elsewhere if relevant.
					pass

				def pkgprint(pkg_str):
					if pkg_merge:
						if pkg_system:
							return colorize("PKG_MERGE_SYSTEM", pkg_str)
						elif pkg_world:
							return colorize("PKG_MERGE_WORLD", pkg_str)
						else:
							return colorize("PKG_MERGE", pkg_str)
					elif pkg_status == "uninstall":
						return colorize("PKG_UNINSTALL", pkg_str)
					else:
						if pkg_system:
							return colorize("PKG_NOMERGE_SYSTEM", pkg_str)
						elif pkg_world:
							return colorize("PKG_NOMERGE_WORLD", pkg_str)
						else:
							return colorize("PKG_NOMERGE", pkg_str)

				if 'interactive' in pkg.metadata.properties and \
					pkg.operation == 'merge':
					addl = colorize("WARN", "I") + addl[1:]
					if ordered:
						counters.interactive += 1

				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=myprint+darkgreen("to "+x[1])
							verboseadd = None
						else:
							if not pkg_merge:
								myprint = "[%s] %s%s" % \
									(pkgprint(pkg_status.ljust(13)),
									indent, pkgprint(pkg.cp))
							else:
								myprint = "[%s %s] %s%s" % \
									(pkgprint(pkg.type_name), addl,
									indent, pkgprint(pkg.cp))
							if (newlp-nc_len(myprint)) > 0:
								myprint=myprint+(" "*(newlp-nc_len(myprint)))
							myprint=myprint+"["+darkblue(xs[1]+xs[2])+"] "
							if (oldlp-nc_len(myprint)) > 0:
								myprint=myprint+" "*(oldlp-nc_len(myprint))
							myprint=myprint+myoldbest
							myprint += darkgreen("to " + pkg.root)
					else:
						if not pkg_merge:
							myprint = "[%s] " % pkgprint(pkg_status.ljust(13))
						else:
							myprint = "[%s %s] " % (pkgprint(pkg_type), addl)
						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
							verboseadd = None
						else:
							if not pkg_merge:
								myprint = "[%s] %s%s" % \
									(pkgprint(pkg_status.ljust(13)),
									indent, pkgprint(pkg.cp))
							else:
								myprint = "[%s %s] %s%s" % \
									(pkgprint(pkg.type_name), addl,
									indent, pkgprint(pkg.cp))
							if (newlp-nc_len(myprint)) > 0:
								myprint=myprint+(" "*(newlp-nc_len(myprint)))
							myprint=myprint+green(" ["+xs[1]+xs[2]+"] ")
							if (oldlp-nc_len(myprint)) > 0:
								myprint=myprint+(" "*(oldlp-nc_len(myprint)))
							myprint += myoldbest
					else:
						if not pkg_merge:
							myprint = "[%s] %s%s %s" % \
								(pkgprint(pkg_status.ljust(13)),
								indent, pkgprint(pkg.cpv),
								myoldbest)
						else:
							myprint = "[%s %s] %s%s %s" % \
								(pkgprint(pkg_type), addl, indent,
								pkgprint(pkg.cpv), myoldbest)

				if columns and pkg.operation == "uninstall":
					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."))

		out = sys.stdout
		show_repos = repoadd_set and repoadd_set != set(["0"])

		for x in p:
			if isinstance(x, basestring):
				out.write("%s\n" % (x,))
				continue

			myprint, verboseadd, repoadd = x

			if verboseadd:
				myprint += " " + verboseadd

			if show_repos and repoadd:
				myprint += " " + teal("[%s]" % repoadd)

			out.write("%s\n" % (myprint,))

		for x in blockers:
			print x

		if verbosity == 3:
			print
			print counters
			if show_repos:
				writemsg_stdout(str(repo_display), noiselevel=-1)

		if "--changelog" in self._frozen_config.myopts:
			writemsg_stdout('\n', noiselevel=-1)
			for revision,text in changelogs:
				writemsg_stdout(bold('*'+revision) + '\n' + text,
					noiselevel=-1)

		sys.stdout.flush()
		return os.EX_OK

	def display_problems(self):
		"""
		Display problems with the dependency graph such as slot collisions.
		This is called internally by display() to show the problems _after_
		the merge list where it is most likely to be seen, but if display()
		is not going to be called then this method should be called explicitly
		to ensure that the user is notified of problems with the graph.

		All output goes to stderr, except for unsatisfied dependencies which
		go to stdout for parsing by programs such as autounmask.
		"""

		# Note that show_masked_packages() sends it's output to
		# stdout, and some programs such as autounmask parse the
		# output in cases when emerge bails out. However, when
		# show_masked_packages() is called for installed packages
		# here, the message is a warning that is more appropriate
		# to send to stderr, so temporarily redirect stdout to
		# stderr. TODO: Fix output code so there's a cleaner way
		# to redirect everything to stderr.
		sys.stdout.flush()
		sys.stderr.flush()
		stdout = sys.stdout
		try:
			sys.stdout = sys.stderr
			self._display_problems()
		finally:
			sys.stdout = stdout
			sys.stdout.flush()
			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)
		elif self._dynamic_config._slot_collision_info:
			self._show_slot_collision_notice()
		else:
			self._show_missed_update()

		# 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

			if world_problems:
				sys.stderr.write("\n!!! Problems have been " + \
					"detected with your world file\n")
				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)
				else:
					parent = "args"
					arg_atom = (arg.arg, atom)
				refs = arg_refs.setdefault(arg_atom, [])
				if parent not in refs:
					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:
				msg.append("A requested package will not be " + \
					"merged because it is listed in\n")
			msg.append("package.provided:\n\n")
			problems_sets = set()
			for (arg, atom), refs in arg_refs.iteritems():
				ref_string = ""
				if refs:
					problems_sets.update(refs)
					refs.sort()
					ref_string = ", ".join(["'%s'" % name for name in refs])
					ref_string = " pulled in by " + ref_string
				msg.append("  %s%s\n" % (colorize("INFORM", str(arg)), ref_string))
			msg.append("\n")
			if "world" in problems_sets:
				msg.append("This problem can be solved in one of the following ways:\n\n")
				msg.append("  A) Use emaint to clean offending packages from world (if not installed).\n")
				msg.append("  B) Uninstall offending packages (cleans them from world).\n")
				msg.append("  C) Remove offending entries from package.provided.\n\n")
				msg.append("The best course of action depends on the reason that an offending\n")
				msg.append("package.provided entry exists.\n\n")
			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))
		if masked_packages:
			sys.stderr.write("\n" + colorize("BAD", "!!!") + \
				" The following installed packages are masked:\n")
			show_masked_packages(masked_packages)
			show_mask_docs()
			print

	def saveNomergeFavorites(self):
		"""Find atoms in favorites that are not in the mergelist and add them
		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, "lock"):
			world_set.lock()
			world_locked = True

		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

			try:
				myfavkey = create_world_atom(x, args_set, root_config)
				if myfavkey:
					if myfavkey in added_favorites:
						continue
					added_favorites.add(myfavkey)
			except portage.exception.InvalidDependString, e:
				writemsg("\n\n!!! '%s' has invalid PROVIDE: %s\n" % \
					(pkg_key, str(e)), noiselevel=-1)
				writemsg("!!! see '%s'\n\n" % os.path.join(
					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 s in world_set:
				continue
			all_added.append(SETPREFIX + k)
		all_added.extend(added_favorites)
		all_added.sort()
		for a in all_added:
			print ">>> Recording %s in \"world\" favorites file..." % \
				colorize("INFORM", str(a))
		if all_added:
			world_set.update(all_added)

		if world_locked:
			world_set.unlock()

	def _loadResumeCommand(self, resume_data, skip_masked=True,
		skip_missing=True):
		"""
		Add a resume command to the graph and validate it in the process.  This
		will raise a PackageNotFound exception if a package is not available.
		"""

		if not isinstance(resume_data, dict):
			return False

		mergelist = resume_data.get("mergelist")
		if not isinstance(mergelist, list):
			mergelist = []

		fakedb = self._dynamic_config.mydbapi
		trees = self._frozen_config.trees
		serialized_tasks = []
		masked_tasks = []
		for x in mergelist:
			if not (isinstance(x, list) and len(x) == 4):
				continue
			pkg_type, myroot, pkg_key, action = x
			if pkg_type not in self.pkg_tree_map:
				continue
			if action != "merge":
				continue
			root_config = self._frozen_config.roots[myroot]
			try:
				pkg = self._pkg(pkg_key, pkg_type, root_config)
			except portage.exception.PackageNotFound:
				# It does no exist or it is corrupt.
				if skip_missing:
					# TODO: log these somewhere
					continue
				raise

			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._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["selective"] = True
			# 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
			# in case a package from a group of circularly dependent packages
			# fails. In this case, a package which has recently been installed
			# may have an unsatisfied circular dependency (pulled in by
			# PDEPEND, for example). So, even though a package is already
			# installed, it may not have all of it's dependencies satisfied, so
			# it may not be usable. If such a package is in the subgraph of
			# 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["deep"] = True

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

			for task in serialized_tasks:
				if isinstance(task, Package) and \
					task.operation == "merge":
					if not self._add_pkg(task, None):
						return False

			# Packages for argument atoms need to be explicitly
			# added via _add_pkg() so that they are included in the
			# digraph (needed at least for --tree display).
			for arg in args:
				for atom in arg.set:
					pkg, existing_node = self._select_package(
						arg.root_config.root, atom)
					if existing_node is None and \
						pkg is not None:
						if not self._add_pkg(pkg, Dependency(atom=atom,
							root=pkg.root, parent=arg)):
							return False

			# Allow unsatisfied deps here to avoid showing a masking
			# message for an unsatisfied dep that isn't necessarily
			# masked.
			if not self._create_graph(allow_unsatisfied=True):
				return False

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

				# For unsatisfied deps of installed packages, only account for
				# them if they are in the subgraph of dependencies of a package
				# 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):
						continue
					if node.operation == "merge":
						unsatisfied_install = True
						break
					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)

			if masked_tasks or unsatisfied_deps:
				# This probably means that a required package
				# was dropped via --skipfirst. It makes the
				# resume list invalid, so convert it to a
				# 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:
				return False

		return True

	def _load_favorites(self, favorites):
		"""
		Use a list of favorites to resume state from a
		previous select_files() call. This creates similar
		DependencyArg instances to those that would have
		been created by the original select_files() call.
		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 = []
		for x in favorites:
			if not isinstance(x, basestring):
				continue
			if x in ("system", "world"):
				x = SETPREFIX + x
			if x.startswith(SETPREFIX):
				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:
				if not portage.isvalidatom(x):
					continue
				args.append(AtomArg(arg=x, atom=x,
					root_config=root_config))

		self._set_args(args)
		return args

	class UnsatisfiedResumeDep(portage.exception.PortageException):
		"""
		A dependency of a resume list is not installed. This
		can occur when a required package is dropped from the
		merge list via --skipfirst.
		"""
		def __init__(self, depgraph, value):
			portage.exception.PortageException.__init__(self, value)
			self.depgraph = depgraph

	class _internal_exception(portage.exception.PortageException):
		def __init__(self, value=""):
			portage.exception.PortageException.__init__(self, value)

	class _unknown_internal_error(_internal_exception):
		"""
		Used by the depgraph internally to terminate graph creation.
		The specific reason for the failure should have been dumped
		to stderr, unfortunately, the exact reason for the failure
		may not be known.
		"""

	class _serialize_tasks_retry(_internal_exception):
		"""
		This is raised by the _serialize_tasks() method when it needs to
		be called again for some reason. The only case that it's currently
		used for is when neglected dependencies need to be added to the
		graph in order to avoid making a potentially unsafe decision.
		"""

	def need_restart(self):
		return self._dynamic_config._need_restart

	def get_runtime_pkg_mask(self):
		return self._dynamic_config._runtime_pkg_mask.copy()

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._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._dynamic_config.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._frozen_config.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:
				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

	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 "--quiet" in myopts:
		print "!!! The short ebuild name \"%s\" is ambiguous. Please specify" % arg
		print "!!! one of the following fully-qualified ebuild names instead:\n"
		for cp in sorted(set(portage.dep_getkey(atom) for atom in atoms)):
			print "    " + colorize("INFORM", cp)
		return

	s = search(root_config, spinner, "--searchdesc" in myopts,
		"--quiet" not in myopts, "--usepkg" in myopts,
		"--usepkgonly" in myopts)
	null_cp = portage.dep_getkey(insert_category_into_atom(
		arg, "null"))
	cat, atom_pn = portage.catsplit(null_cp)
	s.searchkey = atom_pn
	for cp in sorted(set(portage.dep_getkey(atom) for atom in atoms)):
		s.addCP(cp)
	s.output()
	print "!!! The short ebuild name \"%s\" is ambiguous. Please specify" % arg
	print "!!! one of the above fully-qualified ebuild names instead.\n"

def insert_category_into_atom(atom, category):
	alphanum = re.search(r'\w', atom)
	if alphanum:
		ret = atom[:alphanum.start()] + "%s/" % category + \
			atom[alphanum.start():]
	else:
		ret = None
	return ret

def backtrack_depgraph(settings, trees, myopts, myparams, 
	myaction, myfiles, spinner):
	"""
	Raises PackageSetNotFound if myfiles contains a missing package set.
	"""
	backtrack_max = 30
	runtime_pkg_mask = None
	allow_backtracking = True
	backtracked = 0
	frozen_config = _frozen_depgraph_config(settings, trees,
		myopts, spinner)
	while True:
		mydepgraph = depgraph(settings, trees, myopts, myparams, spinner,
			frozen_config=frozen_config,
			allow_backtracking=allow_backtracking,
			runtime_pkg_mask=runtime_pkg_mask)
		success, favorites = mydepgraph.select_files(myfiles)
		if not success:
			if mydepgraph.need_restart() and backtracked < backtrack_max:
				runtime_pkg_mask = mydepgraph.get_runtime_pkg_mask()
				backtracked += 1
			elif backtracked and allow_backtracking:
				if "--debug" in myopts:
					writemsg_level(
						"\n\nbacktracking aborted after %s tries\n\n" % \
						backtracked, noiselevel=-1, level=logging.DEBUG)
				# Backtracking failed, so disable it and do
				# a plain dep calculation + error message.
				allow_backtracking = False
				runtime_pkg_mask = None
			else:
				break
		else:
			break
	return (success, mydepgraph, favorites)

def resume_depgraph(settings, trees, mtimedb, myopts, myparams, spinner):
	"""
	Construct a depgraph for the given resume list. This will raise
	PackageNotFound or depgraph.UnsatisfiedResumeDep when necessary.
	@rtype: tuple
	@returns: (success, depgraph, dropped_tasks)
	"""
	skip_masked = True
	skip_unsatisfied = True
	mergelist = mtimedb["resume"]["mergelist"]
	dropped_tasks = set()
	frozen_config = _frozen_depgraph_config(settings, trees,
		myopts, spinner)
	while True:
		mydepgraph = depgraph(settings, trees,
			myopts, myparams, spinner, frozen_config=frozen_config)
		try:
			success = mydepgraph._loadResumeCommand(mtimedb["resume"],
				skip_masked=skip_masked)
		except depgraph.UnsatisfiedResumeDep, e:
			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()
			unsatisfied_stack = list(unsatisfied_parents)
			while unsatisfied_stack:
				pkg = unsatisfied_stack.pop()
				if pkg in traversed_nodes:
					continue
				traversed_nodes.add(pkg)

				# If this package was pulled in by a parent
				# package scheduled for merge, removing this
				# package may cause the the parent package's
				# dependency to become unsatisfied.
				for parent_node in graph.parent_nodes(pkg):
					if not isinstance(parent_node, Package) \
						or parent_node.operation not in ("merge", "nomerge"):
						continue
					unsatisfied = \
						graph.child_nodes(parent_node,
						ignore_priority=DepPrioritySatisfiedRange.ignore_soft)
					if pkg in unsatisfied:
						unsatisfied_parents[parent_node] = parent_node
						unsatisfied_stack.append(parent_node)

			pruned_mergelist = []
			for x in mergelist:
				if isinstance(x, list) and \
					tuple(x) not in unsatisfied_parents:
					pruned_mergelist.append(x)

			# If the mergelist doesn't shrink then this loop is infinite.
			if len(pruned_mergelist) == len(mergelist):
				# This happens if a package can't be dropped because
				# it's already installed, but it has unsatisfied PDEPEND.
				raise
			mergelist[:] = pruned_mergelist

			# Exclude installed packages that have been removed from the graph due
			# to failure to build/install runtime dependencies after the dependent
			# package has already been installed.
			dropped_tasks.update(pkg for pkg in \
				unsatisfied_parents if pkg.operation != "nomerge")
			mydepgraph.break_refs(unsatisfied_parents)

			del e, graph, traversed_nodes, \
				unsatisfied_parents, unsatisfied_stack
			continue
		else:
			break
	return (success, mydepgraph, dropped_tasks)

def get_mask_info(root_config, cpv, pkgsettings,
	db, pkg_type, built, installed, db_keys):
	eapi_masked = False
	try:
		metadata = dict(izip(db_keys,
			db.aux_get(cpv, db_keys)))
	except KeyError:
		metadata = None

	if metadata is None:
		mreasons = ["corruption"]
	else:
		eapi = metadata['EAPI']
		if eapi[:1] == '-':
			eapi = eapi[1:]
		if not portage.eapi_is_supported(eapi):
			mreasons = ['EAPI %s' % eapi]
		else:
			pkg = Package(type_name=pkg_type, root_config=root_config,
				cpv=cpv, built=built, installed=installed, metadata=metadata)
			mreasons = get_masking_status(pkg, pkgsettings, root_config)
	return metadata, mreasons

def show_masked_packages(masked_packages):
	shown_licenses = set()
	shown_comments = set()
	# Maybe there is both an ebuild and a binary. Only
	# show one of them to avoid redundant appearance.
	shown_cpvs = set()
	have_eapi_mask = False
	for (root_config, pkgsettings, cpv,
		metadata, mreasons) in masked_packages:
		if cpv in shown_cpvs:
			continue
		shown_cpvs.add(cpv)
		comment, filename = None, None
		if "package.mask" in mreasons:
			comment, filename = \
				portage.getmaskingreason(
				cpv, metadata=metadata,
				settings=pkgsettings,
				portdb=root_config.trees["porttree"].dbapi,
				return_location=True)
		missing_licenses = []
		if metadata:
			if not portage.eapi_is_supported(metadata["EAPI"]):
				have_eapi_mask = True
			try:
				missing_licenses = \
					pkgsettings._getMissingLicenses(
						cpv, metadata)
			except portage.exception.InvalidDependString:
				# This will have already been reported
				# above via mreasons.
				pass

		print "- "+cpv+" (masked by: "+", ".join(mreasons)+")"

		if comment and comment not in shown_comments:
			writemsg_stdout(filename + ":\n" + comment + "\n",
				noiselevel=-1)
			shown_comments.add(comment)
		portdb = root_config.trees["porttree"].dbapi
		for l in missing_licenses:
			l_path = portdb.findLicensePath(l)
			if l in shown_licenses:
				continue
			msg = ("A copy of the '%s' license" + \
			" is located at '%s'.") % (l, l_path)
			print msg
			print
			shown_licenses.add(l)
	return have_eapi_mask

def show_mask_docs():
	print "For more information, see the MASKED PACKAGES section in the emerge"
	print "man page or refer to the Gentoo Handbook."

def filter_iuse_defaults(iuse):
	for flag in iuse:
		if flag.startswith("+") or flag.startswith("-"):
			yield flag[1:]
		else:
			yield flag

def show_blocker_docs_link():
	print
	print "For more information about " + bad("Blocked Packages") + ", please refer to the following"
	print "section of the Gentoo Linux x86 Handbook (architecture is irrelevant):"
	print
	print "http://www.gentoo.org/doc/en/handbook/handbook-x86.xml?full=1#blocked"
	print

def get_masking_status(pkg, pkgsettings, root_config):

	mreasons = portage.getmaskingstatus(
		pkg, settings=pkgsettings,
		portdb=root_config.trees["porttree"].dbapi)

	if not pkg.installed:
		if not pkgsettings._accept_chost(pkg.cpv, pkg.metadata):
			mreasons.append("CHOST: %s" % \
				pkg.metadata["CHOST"])
		if pkg.invalid:
			for msg_type, msgs in pkg.invalid.iteritems():
				for msg in msgs:
					mreasons.append("invalid: %s" % (msg,))

	if not pkg.metadata["SLOT"]:
		mreasons.append("invalid: SLOT is undefined")

	return mreasons