Merge improved argument handling and other general depgraph improvements

from trunk.

svn path=/main/branches/2.1.2/; revision=9754

2 files changed, 690 insertions, 418 deletions

diff --git a/bin/emerge b/bin/emerge
index 1eeae340c..ac1555ef1 100755
--- a/bin/emerge
+++ b/bin/emerge
@@ -188,6 +188,7 @@ options=[
 "--ask",          "--alphabetical",
 "--buildpkg",     "--buildpkgonly",
 "--changelog",    "--columns",
+"--consistent",
 "--debug",        "--deep",
 "--digest",
 "--emptytree",
@@ -364,6 +365,9 @@ def create_depgraph_params(myopts, myaction):
 	# recurse:   go into the dependencies
 	# deep:      go into the dependencies of already merged packages
 	# empty:     pretend nothing is merged
+	# consistent: ensure that installation of new packages does not break
+	#            any deep dependencies of required sets (args, system, or
+	#            world).
 	myparams = set(["recurse"])
 	if "--update" in myopts or \
 		"--newuse" in myopts or \
@@ -378,6 +382,8 @@ def create_depgraph_params(myopts, myaction):
 		myparams.discard("recurse")
 	if "--deep" in myopts:
 		myparams.add("deep")
+	if "--consistent" in myopts:
+		myparams.add("consistent")
 	return myparams
 
 # search functionality
@@ -766,11 +772,26 @@ def clean_world(vardb, cpv):
 	world_set.save()
 	world_set.unlock()
 
-class AtomSet(object):
-	def __init__(self, atoms=None):
+SETPREFIX = "@"
+
+class SetConfig(object):
+	def __init__(self, settings, trees):
+		self.sets = {}
+		self.sets["world"] = WorldSet(settings)
+		self.sets["world"].load()
+		self.sets["system"] = SystemSet(settings)
+
+	def getSets(self):
+		return self.sets
+
+	def getSetAtoms(self, name):
+		return set(self.sets[name])
+
+class InternalPackageSet(object):
+	def __init__(self, initial_atoms=None):
 		self._atoms = {}
-		if atoms:
-			self.update(atoms)
+		if initial_atoms:
+			self.update(initial_atoms)
 	def clear(self):
 		self._atoms.clear()
 	def add(self, atom):
@@ -815,19 +836,47 @@ class AtomSet(object):
 				if best_match:
 					return atoms[transformed_atoms.index(best_match)]
 		return None
+
+	def iterAtomsForPackage(self, pkg):
+		"""
+		Find all matching atoms for a given package. This matches virtual
+		arguments against the PROVIDE metadata.  This will raise an
+		InvalidDependString exception if PROVIDE is invalid.
+		"""
+		cpv_slot_list = ["%s:%s" % (pkg.cpv, pkg.metadata["SLOT"])]
+		cp = portage.cpv_getkey(pkg.cpv)
+		atoms = self._atoms.get(cp)
+		if atoms:
+			for atom in atoms:
+				if portage.match_from_list(atom, cpv_slot_list):
+					yield atom
+		if not pkg.metadata["PROVIDE"]:
+			return
+		provides = portage.flatten(portage_dep.use_reduce(
+			portage_dep.paren_reduce(pkg.metadata["PROVIDE"]),
+			uselist=pkg.metadata["USE"].split()))
+		for provide in provides:
+			provided_cp = portage.dep_getkey(provide)
+			atoms = self._atoms.get(provided_cp)
+			if atoms:
+				for atom in atoms:
+					if portage.match_from_list(atom.replace(provided_cp, cp),
+						cpv_slot_list):
+						yield atom
+
 	def __iter__(self):
 		for atoms in self._atoms.itervalues():
 			for atom in atoms:
 				yield atom
 
-class SystemSet(AtomSet):
+class SystemSet(InternalPackageSet):
 	def __init__(self, settings, **kwargs):
-		AtomSet.__init__(self, **kwargs)
+		InternalPackageSet.__init__(self, **kwargs)
 		self.update(getlist(settings, "system"))
 
-class WorldSet(AtomSet):
+class WorldSet(InternalPackageSet):
 	def __init__(self, settings, **kwargs):
-		AtomSet.__init__(self, **kwargs)
+		InternalPackageSet.__init__(self, **kwargs)
 		self.world_file = os.path.join(settings["ROOT"], portage.WORLD_FILE)
 		self._lock = None
 	def _ensure_dirs(self):
@@ -850,16 +899,12 @@ class WorldSet(AtomSet):
 class RootConfig(object):
 	"""This is used internally by depgraph to track information about a
 	particular $ROOT."""
-	def __init__(self, trees):
+	def __init__(self, trees, setconfig):
 		self.trees = trees
 		self.settings = trees["vartree"].settings
 		self.root = self.settings["ROOT"]
-		self.sets = {}
-		world_set = WorldSet(self.settings)
-		world_set.load()
-		self.sets["world"] = world_set
-		system_set = SystemSet(self.settings)
-		self.sets["system"] = system_set
+		self.setconfig = setconfig
+		self.sets = self.setconfig.getSets()
 
 def create_world_atom(pkg_key, metadata, args_set, root_config):
 	"""Create a new atom for the world file if one does not exist.  If the
@@ -1321,6 +1366,48 @@ class Package(object):
 	def __str__(self):
 		return str(self._digraph_node)
 
+class DependencyArg(object):
+	def __init__(self, arg=None, root_config=None):
+		self.arg = arg
+		self.root_config = root_config
+
+	def __str__(self):
+		return self.arg
+
+class AtomArg(DependencyArg):
+	def __init__(self, atom=None, **kwargs):
+		DependencyArg.__init__(self, **kwargs)
+		self.atom = atom
+		self.set = (self.atom, )
+
+class PackageArg(DependencyArg):
+	def __init__(self, package=None, **kwargs):
+		DependencyArg.__init__(self, **kwargs)
+		self.package = package
+		self.atom = "=" + package.cpv
+		self.set = (self.atom, )
+
+class SetArg(DependencyArg):
+	def __init__(self, set=None, **kwargs):
+		DependencyArg.__init__(self, **kwargs)
+		self.set = set
+		self.name = self.arg[len(SETPREFIX):]
+
+class Dependency(object):
+	__slots__ = ("__weakref__", "atom", "blocker", "depth",
+		"parent", "onlydeps", "priority", "root")
+	def __init__(self, **kwargs):
+		for myattr in self.__slots__:
+			if myattr == "__weakref__":
+				continue
+			myvalue = kwargs.get(myattr, None)
+			setattr(self, myattr, myvalue)
+
+		if self.priority is None:
+			self.priority = DepPriority()
+		if self.depth is None:
+			self.depth = 0
+
 class BlockerCache(DictMixin):
 	"""This caches blockers of installed packages so that dep_check does not
 	have to be done for every single installed package on every invocation of
@@ -1463,7 +1550,7 @@ def show_invalid_depstring_notice(parent_node, depstring, error_msg):
 		f.add_flowing_data(x)
 	f.end_paragraph(1)
 
-class CompositeDbapi(object):
+class DepcheckCompositeDB(object):
 	def __init__(self, depgraph, root):
 		self._depgraph = depgraph
 		self._root = root
@@ -1480,21 +1567,9 @@ class CompositeDbapi(object):
 		else:
 			if pkg.installed and "selective" not in self._depgraph.myparams:
 				try:
-					arg = self._depgraph._set_atoms.findAtomForPackage(
-						pkg.cpv, pkg.metadata)
-				except portage_exception.InvalidDependString:
+					arg = self._depgraph._iter_atoms_for_pkg(pkg).next()
+				except (StopIteration, portage_exception.InvalidDependString):
 					arg = None
-					arg_cp = None
-				if arg:
-					arg_cp = portage.dep_getkey(arg)
-				if arg and arg_cp != pkg.cp:
-					# If this argument matches via PROVIDE but there is a
-					# new-style virtual available, then the argument does
-					# not really apply to this package.
-					virt_pkg, virt_existing = \
-						self._depgraph._select_package(self._root, arg_cp)
-					if virt_pkg and virt_pkg.cp == arg_cp:
-						arg = None
 				if arg:
 					ret = []
 			if ret is None:
@@ -1508,7 +1583,7 @@ class CompositeDbapi(object):
 		return self._depgraph.trees[self._root][
 			self._cpv_tree_map[cpv]].dbapi.aux_get(cpv, wants)
 
-class depgraph:
+class depgraph(object):
 
 	pkg_tree_map = {
 		"ebuild":"porttree",
@@ -1520,6 +1595,8 @@ class depgraph:
 		"LICENSE", "PDEPEND", "PROVIDE", "RDEPEND",
 		"repository", "RESTRICT", "SLOT", "USE"]
 
+	_dep_keys = ["DEPEND", "RDEPEND", "PDEPEND"]
+
 	def __init__(self, settings, trees, myopts, myparams, spinner):
 		self.settings = settings
 		self.target_root = settings["ROOT"]
@@ -1541,6 +1618,9 @@ class depgraph:
 		# Contains a filtered view of preferred packages that are selected
 		# from available repositories.
 		self._filtered_trees = {}
+		# Contains installed packages and new packages that have been added
+		# to the graph.
+		self._graph_trees = {}
 		for myroot in trees:
 			self.trees[myroot] = {}
 			for tree in ("porttree", "bintree"):
@@ -1553,7 +1633,10 @@ class depgraph:
 				clone=self.trees[myroot]["vartree"].settings)
 			self._slot_pkg_map[myroot] = {}
 			vardb = self.trees[myroot]["vartree"].dbapi
-			self.roots[myroot] = RootConfig(self.trees[myroot])
+			# Create a RootConfig instance that references
+			# the FakeVartree instead of the real one.
+			self.roots[myroot] = RootConfig(self.trees[myroot],
+				trees[myroot]["root_config"].setconfig)
 			# This fakedbapi instance will model the state that the vdb will
 			# have after new packages have been installed.
 			fakedb = portage.fakedbapi(settings=self.pkgsettings[myroot])
@@ -1567,12 +1650,18 @@ class depgraph:
 					fakedb.cpv_inject(pkg,
 						metadata=dict(izip(self._mydbapi_keys,
 						vardb.aux_get(pkg, self._mydbapi_keys))))
+			def graph_tree():
+				pass
+			graph_tree.dbapi = fakedb
+			self._graph_trees[myroot] = {}
+			self._graph_trees[myroot]["porttree"] = graph_tree
+			self._graph_trees[myroot]["vartree"] = self.trees[myroot]["vartree"]
 			del vardb, fakedb
 			self._filtered_trees[myroot] = {}
 			self._filtered_trees[myroot]["vartree"] = self.trees[myroot]["vartree"]
 			def filtered_tree():
 				pass
-			filtered_tree.dbapi = CompositeDbapi(self, myroot)
+			filtered_tree.dbapi = DepcheckCompositeDB(self, myroot)
 			self._filtered_trees[myroot]["porttree"] = filtered_tree
 			dbs = []
 			portdb = self.trees[myroot]["porttree"].dbapi
@@ -1598,10 +1687,11 @@ class depgraph:
 		# contains all sets added to the graph
 		self._sets = {}
 		# contains atoms given as arguments
-		self._sets["args"] = AtomSet()
+		self._sets["args"] = InternalPackageSet()
 		# contains all atoms from all sets added to the graph, including
 		# atoms given as arguments
-		self._set_atoms = AtomSet()
+		self._set_atoms = InternalPackageSet()
+		self._atom_arg_map = {}
 		# contains all nodes pulled in by self._set_atoms
 		self._set_nodes = set()
 		self.blocker_digraph = digraph()
@@ -1616,9 +1706,14 @@ class depgraph:
 		self._missing_args = []
 		self._masked_installed = []
 		self._unsatisfied_deps_for_display = []
-		self._world_problems = False
+		self._dep_stack = []
+		self._unsatisfied_deps = []
+		self._ignored_deps = []
+		self._required_set_names = set(["system", "world"])
+		self._select_atoms = self._select_atoms_highest_available
 		self._select_package = self._select_pkg_highest_available
 		self._highest_pkg_cache = {}
+		self._installed_pkg_cache = {}
 		# All Package instances
 		self._pkg_cache = {}
 
@@ -1656,10 +1751,18 @@ class depgraph:
 					if len(parents) > max_parents:
 						omitted_parents = len(parents) - max_parents
 						pruned_list = []
+						# When generating the pruned list, prefer instances
+						# of DependencyArg over instances of Package.
 						for parent in parents:
-							pruned_list.append(parent)
-							if len(pruned_list) == max_parents:
-								break
+							if isinstance(parent, DependencyArg):
+								pruned_list.append(parent)
+								if len(pruned_list) == max_parents:
+									break
+						for parent in parents:
+							if not isinstance(parent, DependencyArg):
+								pruned_list.append(parent)
+								if len(pruned_list) == max_parents:
+									break
 						parents = pruned_list
 					msg.append(" pulled in by\n")
 					for parent in parents:
@@ -1722,7 +1825,73 @@ class depgraph:
 				return flags
 		return None
 
-	def create(self, pkg, myparent, priority=None):
+	def _create_graph(self, allow_unsatisfied=False):
+		debug = "--debug" in self.myopts
+		buildpkgonly = "--buildpkgonly" in self.myopts
+		nodeps = "--nodeps" in self.myopts
+		empty = "empty" in self.myparams
+		deep = "deep" in self.myparams
+		consistent = "consistent" in self.myparams
+		dep_stack = self._dep_stack
+		while dep_stack:
+			dep = dep_stack.pop()
+			if isinstance(dep, Package):
+				if not self._add_pkg_deps(dep):
+					return 0
+				continue
+			update = "--update" in self.myopts and dep.depth <= 1
+			if dep.blocker:
+				if not buildpkgonly and \
+					not nodeps and \
+					dep.parent not in self._slot_collision_nodes:
+					if dep.parent.onlydeps:
+						# It's safe to ignore blockers if the
+						# parent is an --onlydeps node.
+						continue
+					# The blocker applies to the root where
+					# the parent is or will be installed.
+					self.blocker_parents.setdefault(
+						("blocks", dep.parent.root, dep.atom), set()).add(
+							dep.parent)
+				continue
+			dep_pkg, existing_node = self._select_package(dep.root, dep.atom,
+				onlydeps=dep.onlydeps)
+			if not dep_pkg:
+				if allow_unsatisfied:
+					self._unsatisfied_deps.append(dep)
+					continue
+				self._unsatisfied_deps_for_display.append(
+					((dep.root, dep.atom), {"myparent":dep.parent}))
+				return 0
+			# In some cases, dep_check will return deps that shouldn't
+			# 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 (existing_node or empty or deep or update):
+				myarg = None
+				if dep.root == self.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:
+					if consistent:
+						self._ignored_deps.append(dep)
+					continue
+
+			if not self._add_pkg(dep_pkg, dep.parent,
+				priority=dep.priority, depth=dep.depth):
+				return 0
+		return 1
+
+	def _add_pkg(self, pkg, myparent, priority=None, depth=0):
 		if priority is None:
 			priority = DepPriority()
 		"""
@@ -1739,20 +1908,21 @@ class depgraph:
 
 		# select the correct /var database that we'll be checking against
 		vardbapi = self.trees[pkg.root]["vartree"].dbapi
-		portdb = self.trees[pkg.root]["porttree"].dbapi
 		pkgsettings = self.pkgsettings[pkg.root]
 
-		arg = None
-		if pkg.root == self.target_root:
- 			try:
-				arg = self._set_atoms.findAtomForPackage(
-					pkg.cpv, pkg.metadata)
+		args = None
+		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
+					show_invalid_depstring_notice(
+						pkg, pkg.metadata["PROVIDE"], str(e))
+					return 0
+				del e
+			else:
+				args = [arg for arg, atom in arg_atoms]
 
 		if not pkg.onlydeps:
 			if not pkg.installed and \
@@ -1773,6 +1943,10 @@ class depgraph:
 			if existing_node:
 				if pkg.cpv == existing_node.cpv:
 					# The existing node can be reused.
+					if args:
+						for arg in args:
+							self.digraph.add(existing_node, arg,
+								priority=priority)
 					# 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
@@ -1834,7 +2008,7 @@ class depgraph:
 			if not visible(pkgsettings, pkg):
 				self._masked_installed.append((pkg, pkgsettings))
 
-		if arg:
+		if args:
 			self._set_nodes.add(pkg)
 
 		# Do this even when addme is False (--onlydeps) so that the
@@ -1842,13 +2016,9 @@ class depgraph:
 		# self._show_slot_collision_notice() needs to be called later.
 		if pkg.onlydeps:
 			self.digraph.add(pkg, myparent, priority=priority)
-
-		merging = not (pkg.installed or pkg.onlydeps)
-		myuse = pkg.metadata["USE"].split()
-		mytype = pkg.type_name
-		myroot = pkg.root
-		mykey = pkg.cpv
-		metadata = pkg.metadata
+		if args:
+			for arg in args:
+				self.digraph.add(pkg, arg, priority=priority)
 
 		""" This section determines whether we go deeper into dependencies or not.
 		    We want to go deeper on a few occasions:
@@ -1856,19 +2026,32 @@ class depgraph:
 		    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 and pkg.onlydeps:
-			pass
-		elif "deep" not in self.myparams and not merging and \
-			not ("--update" in self.myopts and arg and merging):
-			return 1
-		elif "recurse" not in self.myparams:
+		dep_stack = self._dep_stack
+		if "recurse" not in self.myparams:
 			return 1
+		elif pkg.installed and \
+			"deep" not in self.myparams:
+			if "consistent" not in self.myparams:
+				return 1
+			dep_stack = self._ignored_deps
 
 		self.spinner.update()
 
-		""" Check DEPEND/RDEPEND/PDEPEND/SLOT
-		Pull from bintree if it's binary package, porttree if it's ebuild.
-		Binpkg's can be either remote or local. """
+		if args:
+			depth = 0
+		pkg.depth = depth
+		dep_stack.append(pkg)
+		return 1
+
+	def _add_pkg_deps(self, pkg):
+
+		mytype = pkg.type_name
+		myroot = pkg.root
+		mykey = pkg.cpv
+		metadata = pkg.metadata
+		myuse = metadata["USE"].split()
+		jbigkey = pkg
+		depth = pkg.depth + 1
 
 		edepend={}
 		depkeys = ["DEPEND","RDEPEND","PDEPEND"]
@@ -1901,6 +2084,8 @@ class depgraph:
 			(myroot, edepend["PDEPEND"], DepPriority(runtime_post=True))
 		)
 
+		debug = "--debug" in self.myopts
+		strict = mytype != "installed"
 		try:
 			for dep_root, dep_string, dep_priority in deps:
 				if pkg.onlydeps:
@@ -1909,10 +2094,37 @@ class depgraph:
 					dep_priority = DepPriority()
 				if not dep_string:
 					continue
-				if not self.select_dep(dep_root, dep_string, myparent=pkg,
-					myuse=myuse, priority=dep_priority, parent_arg=arg):
+				if debug:
+					print
+					print "Parent:   ", jbigkey
+					print "Depstring:", dep_string
+					print "Priority:", dep_priority
+				vardb = self.roots[dep_root].trees["vartree"].dbapi
+				try:
+					selected_atoms = self._select_atoms(dep_root,
+						dep_string, myuse=myuse, strict=strict)
+				except portage_exception.InvalidDependString, e:
+					show_invalid_depstring_notice(jbigkey, dep_string, str(e))
 					return 0
+				if debug:
+					print "Candidates:", selected_atoms
+				for atom in selected_atoms:
+					blocker = atom.startswith("!")
+					if blocker:
+						atom = atom[1:]
+					mypriority = dep_priority.copy()
+					if not blocker and vardb.match(atom):
+						mypriority.satisfied = True
+					self._dep_stack.append(
+						Dependency(atom=atom,
+							blocker=blocker, depth=depth, parent=pkg,
+							priority=mypriority, root=dep_root))
+				if debug:
+					print "Exiting...", jbigkey
 		except ValueError, e:
+			if not e.args or not isinstance(e.args[0], list) or \
+				len(e.args[0]) < 2:
+				raise
 			pkgs = e.args[0]
 			portage.writemsg("\n\n!!! An atom in the dependencies " + \
 				"is not fully-qualified. Multiple matches:\n\n", noiselevel=-1)
@@ -1924,6 +2136,7 @@ class depgraph:
 					"!!! This binary package cannot be installed: '%s'\n" % \
 					mykey, noiselevel=-1)
 			elif mytype == "ebuild":
+				portdb = self.roots[myroot].trees["porttree"].dbapi
 				myebuild, mylocation = portdb.findname2(mykey)
 				portage.writemsg("!!! This ebuild cannot be installed: " + \
 					"'%s'\n" % myebuild, noiselevel=-1)
@@ -1932,16 +2145,44 @@ class depgraph:
 			return 0
 		return 1
 
-	def select_files(self,myfiles):
-		"given a list of .tbz2s, .ebuilds and deps, create the appropriate depgraph and return a favorite list"
+	def _iter_atoms_for_pkg(self, pkg):
+		# TODO: add multiple $ROOT support
+		if pkg.root != self.target_root:
+			return
+		atom_arg_map = self._atom_arg_map
+		for atom in self._set_atoms.iterAtomsForPackage(pkg):
+			atom_cp = portage.dep_getkey(atom)
+			if atom_cp != pkg.cp:
+				have_new_virt = False
+				for db, pkg_type, built, installed, db_keys in \
+					self._filtered_trees[pkg.root]["dbs"]:
+					if db.cp_list(atom_cp):
+						have_new_virt = True
+						break
+				if have_new_virt:
+					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, create the
+		appropriate depgraph and return a favorite list."""
+		root_config = self.roots[self.target_root]
+		sets = root_config.sets
+		getSetAtoms = root_config.setconfig.getSetAtoms
+		oneshot = "--oneshot" in self.myopts or \
+			"--onlydeps" in self.myopts
 		myfavorites=[]
 		myroot = self.target_root
+		dbs = self._filtered_trees[myroot]["dbs"]
 		vardb = self.trees[myroot]["vartree"].dbapi
 		portdb = self.trees[myroot]["porttree"].dbapi
 		bindb = self.trees[myroot]["bintree"].dbapi
-		bindb_keys = list(bindb._aux_cache_keys)
 		pkgsettings = self.pkgsettings[myroot]
-		arg_atoms = []
+		args = []
 		onlydeps = "--onlydeps" in self.myopts
 		for x in myfiles:
 			ext = os.path.splitext(x)[1]
@@ -1968,9 +2209,8 @@ class depgraph:
 				pkg = Package(type_name="binary", root=myroot,
 					cpv=mykey, built=True, metadata=metadata,
 					onlydeps=onlydeps)
-				if not self.create(pkg, None):
-					return (0,myfavorites)
-				arg_atoms.append((x, "="+mykey))
+				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)
@@ -2007,9 +2247,8 @@ class depgraph:
 				metadata["USE"] = pkgsettings["PORTAGE_USE"]
 				pkg = Package(type_name="ebuild", root=myroot,
 					cpv=mykey, metadata=metadata, onlydeps=onlydeps)
-				if not self.create(pkg, None):
-					return (0,myfavorites)
-				arg_atoms.append((x, "="+mykey))
+				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" + \
@@ -2037,8 +2276,29 @@ class depgraph:
 					atom = portage.cpv_getkey(owner_cpv)
 				else:
 					atom = "%s:%s" % (portage.cpv_getkey(owner_cpv), slot)
-				arg_atoms.append((x, atom))
+				args.append(AtomArg(arg=atom, atom=atom,
+					root_config=root_config))
 			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.PackageNotFound(
+							"emerge: there are no sets to satisfy '%s'." % s)
+					if s in self._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._sets[s] = expanded_set
+					args.append(SetArg(arg=x, set=expanded_set,
+						root_config=root_config))
+					#if not oneshot:
+					#	myfavorites.append(x)
+					continue
 				if not is_valid_package_atom(x):
 					portage.writemsg("\n\n!!! '%s' is not a valid package atom.\n" % x,
 						noiselevel=-1)
@@ -2053,28 +2313,21 @@ class depgraph:
 				#   2) It takes away freedom from the resolver to choose other
 				#      possible expansions when necessary.
 				if "/" in x:
-					arg_atoms.append((x, x))
+					args.append(AtomArg(arg=x, atom=x,
+						root_config=root_config))
 					continue
 				try:
-					mykey = None
-					if "--usepkg" in self.myopts:
-						mykey = portage.dep_expand(x, mydb=bindb,
-							settings=pkgsettings)
-					if ("--usepkgonly" in self.myopts or mykey) and \
-						not portage.dep_getkey(mykey).startswith("null/"):
-						arg_atoms.append((x, mykey))
-						continue
-
-					if "--usepkgonly" in self.myopts:
-						mykey = portage.dep_expand(x, mydb=vardb,
-							settings=pkgsettings)
-						arg_atoms.append((x, mykey))
-						continue
-
 					try:
-						mykey = portage.dep_expand(x,
-							mydb=portdb, settings=pkgsettings)
+						for db, pkg_type, built, installed, db_keys in dbs:
+							mykey = portage.dep_expand(x,
+								mydb=db, settings=pkgsettings)
+							if portage.dep_getkey(mykey).startswith("null/"):
+								continue
+							break
 					except ValueError, e:
+						if not e.args or not isinstance(e.args[0], list) or \
+							len(e.args[0]) < 2:
+							raise
 						mykey = portage.dep_expand(x,
 							mydb=vardb, settings=pkgsettings)
 						cp = portage.dep_getkey(mykey)
@@ -2082,77 +2335,130 @@ class depgraph:
 							cp not in e[0]:
 							raise
 						del e
-					arg_atoms.append((x, mykey))
-				except ValueError, errpkgs:
+					args.append(AtomArg(arg=x, atom=mykey,
+						root_config=root_config))
+				except ValueError, e:
+					if not e.args or not isinstance(e.args[0], list) or \
+						len(e.args[0]) < 2:
+						raise
 					print "\n\n!!! The short ebuild name \"" + x + "\" is ambiguous.  Please specify"
 					print "!!! one of the following fully-qualified ebuild names instead:\n"
-					for i in errpkgs[0]:
+					for i in e.args[0]:
 						print "    " + green(i)
 					print
-					sys.exit(1)
+					return False, myfavorites
 
 		if "--update" in self.myopts:
-			"""Make sure all installed slots are updated when possible. Do this
-			with --emptytree also, to ensure that all slots are remerged."""
-			vardb = self.trees[self.target_root]["vartree"].dbapi
+			# Enable greedy SLOT atoms for atoms given as arguments.
+			# This is currently disabled for sets since greedy SLOT
+			# atoms could be a property of the set itself.
 			greedy_atoms = []
-			for myarg, myatom in arg_atoms:
-				myslots = set()
-				for cpv in vardb.match(myatom):
-					myslots.add(vardb.aux_get(cpv, ["SLOT"])[0])
-				for myslot in myslots:
-					myslot_atom = "%s:%s" % \
-						(portage.dep_getkey(myatom), myslot)
-					greedy_atoms.append((myarg, myslot_atom))
+			for arg in args:
 				# In addition to any installed slots, also try to pull
 				# in the latest new slot that may be available.
-				greedy_atoms.append((myarg, myatom))
-			arg_atoms = greedy_atoms
-
-		oneshot = "--oneshot" in self.myopts or \
-			"--onlydeps" in self.myopts
-		""" These are used inside self.create() in order to ensure packages
-		that happen to match arguments are not incorrectly marked as nomerge."""
+				greedy_atoms.append(arg)
+				if not isinstance(arg, (AtomArg, PackageArg)):
+					continue
+				atom_cp = portage.dep_getkey(arg.atom)
+				slots = set()
+				for cpv in vardb.match(atom_cp):
+					slots.add(vardb.aux_get(cpv, ["SLOT"])[0])
+				for slot in slots:
+					greedy_atoms.append(
+						AtomArg(arg=arg.arg, atom="%s:%s" % (atom_cp, slot),
+							root_config=root_config))
+			args = greedy_atoms
+			del greedy_atoms
+
+		# Create the "args" package set from atoms and
+		# packages given as arguments.
 		args_set = self._sets["args"]
-		for myarg, myatom in arg_atoms:
+		for arg in args:
+			if not isinstance(arg, (AtomArg, PackageArg)):
+				continue
+			myatom = arg.atom
 			if myatom in args_set:
 				continue
 			args_set.add(myatom)
-			self._set_atoms.add(myatom)
 			if not oneshot:
 				myfavorites.append(myatom)
-
-		for myarg, myatom in arg_atoms:
-				atom_cp = portage.dep_getkey(myatom)
-				pprovided = pkgsettings.pprovideddict.get(
-					portage.dep_getkey(myatom))
-				if pprovided and portage.match_from_list(myatom, pprovided):
-					self._pprovided_args.append((myarg, myatom))
-					continue
-				pkg, existing_node = self._select_package(
-					myroot, myatom, onlydeps=onlydeps)
-				if not pkg:
-					self._unsatisfied_deps_for_display.append(
-						((myroot, myatom), {"myparent":None}))
-					return False, myfavorites
-				if atom_cp != pkg.cp:
-					# For old-style virtuals, we need to repeat the
-					# package.provided check against the selected package.
-					expanded_atom = myatom.replace(atom_cp, pkg.cp)
-					pprovided = pkgsettings.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._pprovided_args.append((myarg, myatom))
-						continue
-				if pkg.installed and "selective" not in self.myparams:
-					self._unsatisfied_deps_for_display.append(
-						((myroot, myatom), {"myparent":None}))
-					return 0, myfavorites
-
+		self._set_atoms.update(chain(*self._sets.itervalues()))
+		atom_arg_map = self._atom_arg_map
+		for arg in args:
+			for atom in arg.set:
+				atom_key = (atom, myroot)
+				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)
+		pprovideddict = pkgsettings.pprovideddict
+		# Order needs to be preserved since a feature of --nodeps
+		# is to allow the user to force a specific merge order.
+		args.reverse()
+		while args:
+			arg = args.pop()
+			for atom in arg.set:
+				atom_cp = portage.dep_getkey(atom)
 				try:
-					self.mysd = self.create(pkg, None)
+					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._pprovided_args.append((arg, atom))
+						continue
+					if isinstance(arg, PackageArg):
+						if not self._add_pkg(arg.package, arg) or \
+							not self._create_graph():
+							sys.stderr.write(("\n\n!!! Problem resolving " + \
+								"dependencies for %s\n") % arg.arg)
+							return 0, myfavorites
+						continue
+					pkg, existing_node = self._select_package(
+						myroot, atom, onlydeps=onlydeps)
+					if not pkg:
+						if not (isinstance(arg, SetArg) and \
+							arg.name in ("system", "world")):
+							self._unsatisfied_deps_for_display.append(
+								((myroot, atom), {}))
+							return 0, myfavorites
+						self._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._pprovided_args.append((arg, atom))
+							continue
+					if pkg.installed and "selective" not in self.myparams:
+						self._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
+
+					self._dep_stack.append(
+						Dependency(atom=atom, onlydeps=onlydeps, root=myroot, parent=arg))
+					if not self._create_graph():
+						if 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")
@@ -2170,28 +2476,60 @@ class depgraph:
 				except SystemExit, e:
 					raise # Needed else can't exit
 				except Exception, e:
-					print >> sys.stderr, "\n\n!!! Problem in '%s' dependencies." % myatom
+					print >> sys.stderr, "\n\n!!! Problem in '%s' dependencies." % atom
 					print >> sys.stderr, "!!!", str(e), getattr(e, "__module__", None)
 					raise
 
-				if not self.mysd:
-					return (0,myfavorites)
-
 		missing=0
 		if "--usepkgonly" in self.myopts:
 			for xs in self.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]
 
+		if not self._complete_graph():
+			return False, myfavorites
+
 		if not self.validate_blockers():
 			return False, myfavorites
 		
 		# We're true here unless we are missing binaries.
 		return (not missing,myfavorites)
 
+	def _select_atoms_from_graph(self, *pargs, **kwargs):
+		"""
+		Prefer atoms matching packages that have already been
+		added to the graph or those that are installed and have
+		not been scheduled for replacement.
+		"""
+		kwargs["trees"] = self._graph_trees
+		return self._select_atoms_highest_available(*pargs, **kwargs)
+
+	def _select_atoms_highest_available(self, root, depstring,
+		myuse=None, strict=True, trees=None):
+		"""This will raise InvalidDependString if necessary. If trees is
+		None then self._filtered_trees is used."""
+		pkgsettings = self.pkgsettings[root]
+		if trees is None:
+			trees = self._filtered_trees
+		if True:
+			try:
+				if not strict:
+					portage_dep._dep_check_strict = False
+				mycheck = portage.dep_check(depstring, None,
+					pkgsettings, myuse=myuse,
+					myroot=root, trees=trees)
+			finally:
+				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):
 		xinfo = '"%s"' % atom
 		if arg:
@@ -2208,19 +2546,7 @@ class depgraph:
 		pkgsettings = self.pkgsettings[root]
 		root_config = self.roots[root]
 		portdb = self.roots[root].trees["porttree"].dbapi
-		dbs = []
-		portdb = self.trees[root]["porttree"].dbapi
-		bindb  = self.trees[root]["bintree"].dbapi
-		vardb  = self.trees[root]["vartree"].dbapi
-		#               (db, pkg_type, built, installed, db_keys)
-		if "--usepkgonly" not in self.myopts:
-			db_keys = list(portdb._aux_cache_keys)
-			dbs.append((portdb, "ebuild", False, False, db_keys))
-		if "--usepkg" in self.myopts:
-			db_keys = list(bindb._aux_cache_keys)
-			dbs.append((bindb,  "binary", True, False, db_keys))
-		db_keys = self._mydbapi_keys
-		dbs.append((vardb, "installed", True, True, db_keys))
+		dbs = self._filtered_trees[root]["dbs"]
 		for db, pkg_type, built, installed, db_keys in dbs:
 			if installed:
 				continue
@@ -2356,8 +2682,9 @@ class depgraph:
 					myarg = None
 					if root == self.target_root:
 						try:
-							myarg = self._set_atoms.findAtomForPackage(
-								pkg.cpv, pkg.metadata)
+							myarg = self._iter_atoms_for_pkg(pkg).next()
+						except StopIteration:
+							pass
 						except portage_exception.InvalidDependString:
 							if not installed:
 								# masked by corruption
@@ -2496,127 +2823,126 @@ class depgraph:
 		# ordered by type preference ("ebuild" type is the last resort)
 		return  matched_packages[-1], existing_node
 
-	def select_dep(self, myroot, depstring, myparent=None, arg=None,
-		myuse=None, raise_on_missing=False, priority=DepPriority(),
-		rev_deps=False, parent_arg=None):
-		""" Given a depstring, create the depgraph such that all dependencies are satisfied.
-		    myroot = $ROOT from environment, where {R,P}DEPENDs are merged to.
-		    myparent = the node whose depstring is being passed in
-		    arg = package was specified on the command line, merge even if it's already installed
-		    myuse = USE flags at present
-		    raise_on_missing = Given that the depgraph is not proper, raise an exception if true
-		    else continue trying.
-		    return 1 on success, 0 for failure
+	def _select_pkg_from_graph(self, root, atom, onlydeps=False):
 		"""
+		Select packages that have already been added to the graph or
+		those that are installed and have not been scheduled for
+		replacement.
+		"""
+		graph_db = self._graph_trees[root]["porttree"].dbapi
+		matches = graph_db.match(atom)
+		if not matches:
+			return None, None
+		cpv = matches[-1] # highest match
+		slot_atom = "%s:%s" % (portage.cpv_getkey(cpv),
+			graph_db.aux_get(cpv, ["SLOT"])[0])
+		e_pkg = self._slot_pkg_map[root].get(slot_atom)
+		if e_pkg:
+			return e_pkg, e_pkg
+		cache_key = (root, atom, onlydeps)
+		ret = self._installed_pkg_cache.get(cache_key)
+		if ret is not None:
+			return ret
+		metadata = dict(izip(self._mydbapi_keys,
+			graph_db.aux_get(cpv, self._mydbapi_keys)))
+		pkg = Package(cpv=cpv, built=True,
+			installed=True, type_name="installed",
+			metadata=metadata, root=root)
+		ret = (pkg, None)
+		self._installed_pkg_cache[cache_key] = ret
+		return ret
 
-		portdb = self.trees[myroot]["porttree"].dbapi
-		bindb  = self.trees[myroot]["bintree"].dbapi
-		vardb  = self.trees[myroot]["vartree"].dbapi
-		pkgsettings = self.pkgsettings[myroot]
-		if myparent:
-			p_type, p_root, p_key, p_status = myparent
-
-		if "--debug" in self.myopts:
-			print
-			print "Parent:   ",myparent
-			print "Depstring:",depstring
-			if rev_deps:
-				print "Reverse:", rev_deps
-			print "Priority:", priority
-
-		#processing dependencies
-		""" Call portage.dep_check to evaluate the use? conditionals and make sure all
-		dependencies are satisfiable. """
-		if arg:
-			mymerge = [depstring]
-			pprovided = pkgsettings.pprovideddict.get(
-				portage.dep_getkey(depstring))
-			if pprovided and portage.match_from_list(depstring, pprovided):
-				mymerge = []
-		else:
-			try:
-				if myparent and p_status == "nomerge":
-					portage_dep._dep_check_strict = False
-				mycheck = portage.dep_check(depstring, None,
-					pkgsettings, myuse=myuse, myroot=myroot,
-					trees=self._filtered_trees)
-			finally:
-				portage_dep._dep_check_strict = True
-
-			if not mycheck[0]:
-				if myparent:
-					show_invalid_depstring_notice(
-						myparent, depstring, mycheck[1])
-				else:
-					sys.stderr.write("\n%s\n%s\n" % (depstring, mycheck[1]))
-				return 0
-			mymerge = mycheck[1]
+	def _complete_graph(self):
+		"""
+		Add any deep dependencies of required sets (args, system, world) that
+		have not been pulled into the graph yet. This ensures that the graph
+		is consistent such that initially satisfied deep dependencies are not
+		broken in the new graph. Initially unsatisfied dependencies are
+		irrelevant since we only want to avoid breaking dependencies that are
+		intially satisfied.
+
+		Since this method can consume enough time to disturb users, it is
+		currently only enabled by the --consistent option.
+		"""
+		if "consistent" not in self.myparams:
+			# Skip this to avoid consuming enough time to disturb users.
+			return 1
 
-		if not mymerge and arg:
-			# A provided package has been specified on the command line.  The
-			# package will not be merged and a warning will be displayed.
-			if depstring in self._set_atoms:
-				self._pprovided_args.append((arg, depstring))
+		if "--buildpkgonly" in self.myopts or \
+			"recurse" not in self.myparams:
+			return 1
 
-		if "--debug" in self.myopts:
-			print "Candidates:",mymerge
-		for x in mymerge:
-			selected_pkg = None
-			if x.startswith("!"):
-				if "--buildpkgonly" not in self.myopts and \
-					"--nodeps" not in self.myopts and \
-					myparent not in self._slot_collision_nodes:
-					p_type, p_root, p_key, p_status = myparent
-					if  p_type != "installed" and p_status != "merge":
-						# It's safe to ignore blockers from --onlydeps nodes.
-						continue
-					self.blocker_parents.setdefault(
-						("blocks", p_root, x[1:]), set()).add(myparent)
+		# Put the depgraph into a mode that causes it to only
+		# select packages that have already been added to the
+		# graph or those that are installed and have not been
+		# scheduled for replacement. Also, toggle the "deep"
+		# parameter so that all dependencies are traversed and
+		# accounted for.
+		self._select_atoms = self._select_atoms_from_graph
+		self._select_package = self._select_pkg_from_graph
+		self.myparams.add("deep")
+
+		for root in self.roots:
+			required_set_names = self._required_set_names.copy()
+			if root == self.target_root and \
+				("deep" in self.myparams or "empty" in self.myparams):
+				required_set_names.difference_update(self._sets)
+			if not required_set_names and not self._ignored_deps:
 				continue
-			else:
-				pkg, existing_node = self._select_package(myroot, x)
-				if not pkg:
-					self._unsatisfied_deps_for_display.append(
-						((myroot, x), {"myparent":myparent}))
-					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 myparent and not arg and vardb.match(x) and \
-					not existing_node and \
-					"empty" not in self.myparams and \
-					"deep" not in self.myparams and \
-					not ("--update" in self.myopts and parent_arg):
-					myarg = None
-					if pkg.root == self.target_root:
-						try:
-							myarg = self._set_atoms.findAtomForPackage(
-								pkg.cpv, pkg.metadata)
-						except portage_exception.InvalidDependString:
-							# This is already handled inside
-							# self.create() when necessary.
-							pass
-					if not myarg:
-						continue
-
-			if myparent:
-				#we are a dependency, so we want to be unconditionally added
-				mypriority = priority.copy()
-				if vardb.match(x):
-					mypriority.satisfied = True
-				if not self.create(pkg, myparent, priority=mypriority):
+			root_config = self.roots[root]
+			setconfig = root_config.setconfig
+			args = []
+			# Reuse existing SetArg instances when available.
+			for arg in self.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._dep_stack.append(
+						Dependency(atom=atom, root=root, parent=arg))
+			if self._ignored_deps:
+				self._dep_stack.extend(self._ignored_deps)
+				self._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._unsatisfied_deps:
+				dep = self._unsatisfied_deps.pop()
+				matches = vardb.match(dep.atom)
+				if not matches:
+					# Initially unsatisfied.
+					continue
+				# An scheduled installation broke a deep dependency.
+				# Add the installed package to the graph so that it
+				# will be appropriately reported as a slot collision
+				# (possibly solvable via backtracking).
+				cpv = matches[-1] # highest match
+				metadata = dict(izip(self._mydbapi_keys,
+					vardb.aux_get(cpv, self._mydbapi_keys)))
+				pkg = Package(type_name="installed", root=root,
+					cpv=cpv, metadata=metadata, built=True,
+					installed=True)
+				if not self._add_pkg(pkg, dep.parent,
+					priority=dep.priority, depth=dep.depth):
 					return 0
-			else:
-				#if mysource is not set, then we are a command-line dependency and should not be added
-				#if --onlydeps is specified.
-				if not self.create(pkg, myparent):
+				if not self._create_graph(allow_unsatisfied=True):
 					return 0
-
-		if "--debug" in self.myopts:
-			print "Exiting...",myparent
 		return 1
 
 	def validate_blockers(self):
@@ -3163,81 +3489,11 @@ class depgraph:
 		self._altlist_cache[reversed] = retlist[:]
 		return retlist
 
-	def xcreate(self,mode="system"):
-		myroot = self.target_root
-		pkgsettings = self.pkgsettings[myroot]
-		vardb = self.trees[self.target_root]["vartree"].dbapi
-		portdb = self.trees[self.target_root]["porttree"].dbapi
-		bindb = self.trees[self.target_root]["bintree"].dbapi
-		bindb_keys = list(bindb._aux_cache_keys)
-
-		root_config = self.roots[self.target_root]
-		world_set = root_config.sets["world"]
-		system_set = root_config.sets["system"]
-		mylist = list(system_set)
-		self._sets["system"] = system_set
-		if mode == "world":
-			self._sets["world"] = world_set
-			for x in world_set:
-				if not portage.isvalidatom(x):
-					self._world_problems = True
-					continue
-				elif not vardb.match(x):
-					self._world_problems = True
-				mylist.append(x)
-
-		for myatom in mylist:
-			self._set_atoms.add(myatom)
-
-		for mydep in mylist:
-			atom_cp = portage.dep_getkey(mydep)
-			pprovided = pkgsettings.pprovideddict.get(
-				portage.dep_getkey(mydep))
-			if pprovided and portage.match_from_list(mydep, pprovided):
-				self._pprovided_args.append((mydep, mydep))
-				continue
-
-			pkg, existing_node = self._select_package(
-				self.target_root, mydep)
-			if not pkg:
-				self._missing_args.append(mydep)
-				continue
-			if atom_cp != pkg.cp:
-				# For old-style virtuals, we need to repeat the
-				# package.provided check against the selected package.
-				expanded_atom = mydep.replace(atom_cp, pkg.cp)
-				pprovided = pkgsettings.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._pprovided_args.append((mydep, mydep))
-					continue
-			if pkg.installed and "selective" not in self.myparams:
-				# 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.
-				self._unsatisfied_deps_for_display.append(
-					((myroot, mydep), {"myparent":None}))
-
-			if not self.create(pkg, None):
-				print >> sys.stderr, "\n\n!!! Problem resolving dependencies for", mydep
-				return 0
-
-		if not self.validate_blockers():
-			return False
-
-		return 1
-
 	def display(self, mylist, favorites=[], verbosity=None):
 		if verbosity is None:
 			verbosity = ("--quiet" in self.myopts and 1 or \
 				"--verbose" in self.myopts and 3 or 2)
-		favorites_set = AtomSet()
-		favorites_set.update(favorites)
+		favorites_set = InternalPackageSet(favorites)
 		changelogs=[]
 		p=[]
 		blockers = []
@@ -3475,7 +3731,6 @@ class depgraph:
 					cpv=pkg_key, built=built, installed=installed,
 					metadata=metadata)
 				pkg_use = metadata["USE"].split()
-
 				try:
 					restrict = flatten(use_reduce(paren_reduce(
 						mydbapi.aux_get(pkg_key, ["RESTRICT"])[0]),
@@ -3703,13 +3958,7 @@ class depgraph:
 						if repo_name_prev:
 							repo_path_prev = portdb.getRepositoryPath(
 								repo_name_prev)
-						# To avoid false positives during the transition
-						# period, don't show ? if the installed package
-						# is missing a repository label. Stages starting
-						# with 2007.1 will come with repository lables.
-						ignore_missing_labels = True
-						if (ignore_missing_labels and not repo_path_prev) or \
-							repo_path_prev == repo_path_real:
+						if repo_path_prev == repo_path_real:
 							repoadd = repo_display.repoStr(repo_path_real)
 						else:
 							repoadd = "%s=>%s" % (
@@ -3848,8 +4097,7 @@ class depgraph:
 						myversion = "%s-%s" % (mysplit[1], mysplit[2])
 	
 					if myversion != portage.VERSION and "--quiet" not in self.myopts:
-						if mylist_index < len(mylist) - 1 and \
-							"livecvsportage" not in self.settings.features:
+						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."))
 							print
@@ -3887,7 +4135,18 @@ class depgraph:
 
 		self._show_slot_collision_notice()
 
-		if self._world_problems:
+		# TODO: Add generic support for "set problem" handlers so that
+		# the below warnings aren't special cases for world only.
+
+		if self._missing_args:
+			world_problems = False
+			if "world" in self._sets:
+				for arg, atom in self._missing_args:
+					if arg.name == "world":
+						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 " + \
@@ -3898,17 +4157,21 @@ class depgraph:
 				" Ebuilds for the following packages are either all\n")
 			sys.stderr.write(colorize("BAD", "!!!") + \
 				" masked or don't exist:\n")
-			sys.stderr.write(" ".join(self._missing_args) + "\n")
+			sys.stderr.write(" ".join(atom for arg, atom in \
+				self._missing_args) + "\n")
 
 		if self._pprovided_args:
 			arg_refs = {}
-			for arg_atom in self._pprovided_args:
-				arg, atom = arg_atom
-				arg_refs[arg_atom] = []
-				cp = portage.dep_getkey(atom)
-				for set_name, atom_set in self._sets.iteritems():
-					if atom in atom_set:
-						arg_refs[arg_atom].append(set_name)
+			for arg, atom in self._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._pprovided_args) > 1:
@@ -4015,7 +4278,7 @@ class depgraph:
 		root_config = self.roots[self.target_root]
 		world_set = root_config.sets["world"]
 		world_set.lock()
-		world_set.load()
+		world_set.load() # maybe it's changed on disk
 		args_set = self._sets["args"]
 		portdb = self.trees[self.target_root]["porttree"].dbapi
 		added_favorites = set()
@@ -4032,15 +4295,27 @@ class depgraph:
 					if myfavkey in added_favorites:
 						continue
 					added_favorites.add(myfavkey)
-					world_set.add(myfavkey)
-					print ">>> Recording",myfavkey,"in \"world\" favorites file..."
 			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
-		if added_favorites:
+		all_added = []
+		for k in self._sets:
+			if k in ("args", "world"):
+				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", a)
+		if all_added:
+			world_set.update(all_added)
 			world_set.save()
 		world_set.unlock()
 
@@ -4286,9 +4561,9 @@ class MergeTask(object):
 				del x, mytype, myroot, mycpv, mystatus, quiet_config
 			del shown_verifying_msg, quiet_settings
 
-		root_config = RootConfig(self.trees[self.target_root])
+		root_config = self.trees[self.target_root]["root_config"]
 		system_set = root_config.sets["system"]
-		args_set = AtomSet(favorites)
+		args_set = InternalPackageSet(favorites)
 		world_set = root_config.sets["world"]
 		if "--resume" not in self.myopts:
 			mymergelist = mylist
@@ -6108,12 +6383,11 @@ def action_depclean(settings, trees, ldpath_mtimes,
 	vardb = dep_check_trees[myroot]["vartree"].dbapi
 	# Constrain dependency selection to the installed packages.
 	dep_check_trees[myroot]["porttree"] = dep_check_trees[myroot]["vartree"]
-	system_set = SystemSet(settings)
-	syslist = list(system_set)
-	world_set = WorldSet(settings)
-	world_set.load()
-	worldlist = list(world_set)
-	args_set = AtomSet()
+	root_config = trees[myroot]["root_config"]
+	setconfig = root_config.setconfig
+	syslist = setconfig.getSetAtoms("system")
+	worldlist = setconfig.getSetAtoms("world")
+	args_set = InternalPackageSet()
 	fakedb = portage.fakedbapi(settings=settings)
 	myvarlist = vardb.cpv_all()
 
@@ -6581,32 +6855,20 @@ def action_build(settings, trees, mtimedb,
 			return os.EX_OK
 
 		myparams = create_depgraph_params(myopts, myaction)
-		if myaction in ["system","world"]:
-			if "--quiet" not in myopts and "--nodeps" not in myopts:
-				print "Calculating",myaction,"dependencies  ",
-				sys.stdout.flush()
-			mydepgraph = depgraph(settings, trees, myopts, myparams, spinner)
-			if not mydepgraph.xcreate(myaction):
-				print "!!! Depgraph creation failed."
-				mydepgraph.display_problems()
-				return 1
-			if "--quiet" not in myopts and "--nodeps" not in myopts:
-				print "\b\b... done!"
-		else:
-			if "--quiet" not in myopts and "--nodeps" not in myopts:
-				print "Calculating dependencies  ",
-				sys.stdout.flush()
-			mydepgraph = depgraph(settings, trees, myopts, myparams, spinner)
-			try:
-				retval, favorites = mydepgraph.select_files(myfiles)
-			except portage_exception.PackageNotFound, e:
-				portage.writemsg("\n!!! %s\n" % str(e), noiselevel=-1)
-				return 1
-			if not retval:
-				mydepgraph.display_problems()
-				return 1
-			if "--quiet" not in myopts and "--nodeps" not in myopts:
-				print "\b\b... done!"
+		if "--quiet" not in myopts and "--nodeps" not in myopts:
+			print "Calculating dependencies  ",
+			sys.stdout.flush()
+		mydepgraph = depgraph(settings, trees, myopts, myparams, spinner)
+		try:
+			retval, favorites = mydepgraph.select_files(myfiles)
+		except portage_exception.PackageNotFound, e:
+			portage.writemsg("\n!!! %s\n" % str(e), noiselevel=-1)
+			return 1
+		if not retval:
+			mydepgraph.display_problems()
+			return 1
+		if "--quiet" not in myopts and "--nodeps" not in myopts:
+			print "\b\b... done!"
 		display = pretend or \
 			((ask or tree or verbose) and not (quiet and not ask))
 		if not display:
@@ -6894,6 +7156,11 @@ def load_emerge_config(trees=None):
 		kwargs[k] = os.environ.get(envvar, None)
 	trees = portage.create_trees(trees=trees, **kwargs)
 
+	for root, root_trees in trees.iteritems():
+		settings = root_trees["vartree"].settings
+		setconfig = SetConfig(settings, root_trees)
+		root_trees["root_config"] = RootConfig(root_trees, setconfig)
+
 	settings = trees["/"]["vartree"].settings
 
 	for myroot in trees:
@@ -7102,9 +7369,12 @@ def emerge_main():
 
 """
 
-	if (myaction in ["world", "system"]) and myfiles:
-		print "emerge: please specify a package class (\"world\" or \"system\") or individual packages, but not both."
-		sys.exit(1)
+	if myaction in ("world", "system"):
+		if myfiles:
+			print "emerge: please specify a package class (\"world\" " + \
+				"or \"system\") or individual packages, but not both."
+			return 1
+		myfiles.append(myaction)
 
 	for x in myfiles:
 		ext = os.path.splitext(x)[1]
diff --git a/pym/portage.py b/pym/portage.py
index 4fee4e47a..cac0316b7 100644
--- a/pym/portage.py
+++ b/pym/portage.py
@@ -453,7 +453,9 @@ class digraph:
 
 	def clone(self):
 		clone = digraph()
-		clone.nodes = copy.deepcopy(self.nodes)
+		clone.nodes = {}
+		for k, v in self.nodes.iteritems():
+			clone.nodes[k] = (v[0].copy(), v[1].copy())
 		clone.order = self.order[:]
 		return clone