[gentoo-portage-dev] [PATCH 2/2 v2] depgraph: soname dependency resolution (282639)

[Zac Medico]

Soname dependency resolution is disabled by default, since it will not
work correctly unless all available installed and binary packages have
been built by a version of portage which generates REQUIRES and PROVIDES
metadata.

Soname dependency resolution is enabled when --ignore-soname-deps=n is
specified, and one of the following is true:

 * --usepkgonly option is enabled

 * removal actions (--depclean and --prune)

Soname dependencies are automatically ignored for dependency
calculations that can pull unbuilt ebuilds into the dependency graph,
since unbuilt ebuilds do not have any soname dependency metadata,
making it impossible to determine whether an unresolved soname
dependency can be satisfied.  Therefore, --usepkgonly must be used
in order to enable soname depedency resolution when installing packages.

A new soname.provided file is supported for profiles, making it possible
to selectively ignore soname dependencies (see the portage(5) man page).

When soname dependency resolution is enabled, the soname dependencies
are represented as SonameAtom instances which expose an interface that
is minimally compatible with Atom instances. This allows both types of
atoms to be satisfied using mostly the same mechanisms, with minimal
use of conditional logic to handle the differences. Both atom classes
have "soname" and "package" attributes that make it convenient for
conditional code to distinguish package atoms and soname atoms. Both
classes also implement a match method, so that it is possible to match
a Package instance using identical syntax for both types of atoms.

Since soname dependencies and slot-operator := dependencies share many
properties, the slot-operator rebuild code has been generalized to
handle both types of dependencies. Many of the existing unit tests
involving slot-operator dependencies have been copied and adapted to
test soname dependencies (the new tests are located in the
pym/portage/tests/resolver/soname/ directory).

X-Gentoo-Bug: 282639
X-Gentoo-Bug-URL: https://bugs.gentoo.org/show_bug.cgi?id=282639
---
PATCH 2/2 v2 fixes depgraph._iter_match_pkgs_soname to yield packages in
descending order.

 man/emerge.1                                       |  13 +
 man/portage.5                                      |  23 ++
 pym/_emerge/FakeVartree.py                         |  16 +-
 pym/_emerge/Package.py                             |  55 +++-
 pym/_emerge/actions.py                             |   9 +-
 pym/_emerge/create_depgraph_params.py              |   6 +
 pym/_emerge/create_world_atom.py                   |   6 +-
 pym/_emerge/depgraph.py                            | 347 +++++++++++++++------
 pym/_emerge/main.py                                |  10 +
 pym/_emerge/resolver/DbapiProvidesIndex.py         | 101 ++++++
 pym/_emerge/resolver/output.py                     |  10 +-
 pym/_emerge/resolver/package_tracker.py            |  42 ++-
 pym/_emerge/resolver/slot_collision.py             |  35 ++-
 pym/portage/dbapi/DummyTree.py                     |  16 +
 pym/portage/dep/__init__.py                        |  25 ++
 pym/portage/dep/soname/SonameAtom.py               |  72 +++++
 pym/portage/dep/soname/parse.py                    |  47 +++
 pym/portage/package/ebuild/config.py               |  13 +
 pym/portage/tests/resolver/ResolverPlayground.py   |   3 +
 pym/portage/tests/resolver/soname/__init__.py      |   2 +
 pym/portage/tests/resolver/soname/__test__.py      |   2 +
 .../tests/resolver/soname/test_autounmask.py       | 103 ++++++
 pym/portage/tests/resolver/soname/test_depclean.py |  61 ++++
 .../tests/resolver/soname/test_downgrade.py        | 240 ++++++++++++++
 .../tests/resolver/soname/test_or_choices.py       |  92 ++++++
 .../tests/resolver/soname/test_reinstall.py        |  87 ++++++
 .../tests/resolver/soname/test_skip_update.py      |  86 +++++
 .../soname/test_slot_conflict_reinstall.py         | 342 ++++++++++++++++++++
 .../resolver/soname/test_slot_conflict_update.py   | 117 +++++++
 .../tests/resolver/soname/test_soname_provided.py  |  78 +++++
 .../tests/resolver/soname/test_unsatisfiable.py    |  71 +++++
 .../tests/resolver/soname/test_unsatisfied.py      |  87 ++++++
 pym/portage/tests/resolver/test_package_tracker.py |   4 +-
 33 files changed, 2099 insertions(+), 122 deletions(-)
 create mode 100644 pym/_emerge/resolver/DbapiProvidesIndex.py
 create mode 100644 pym/portage/dbapi/DummyTree.py
 create mode 100644 pym/portage/dep/soname/SonameAtom.py
 create mode 100644 pym/portage/dep/soname/parse.py
 create mode 100644 pym/portage/tests/resolver/soname/__init__.py
 create mode 100644 pym/portage/tests/resolver/soname/__test__.py
 create mode 100644 pym/portage/tests/resolver/soname/test_autounmask.py
 create mode 100644 pym/portage/tests/resolver/soname/test_depclean.py
 create mode 100644 pym/portage/tests/resolver/soname/test_downgrade.py
 create mode 100644 pym/portage/tests/resolver/soname/test_or_choices.py
 create mode 100644 pym/portage/tests/resolver/soname/test_reinstall.py
 create mode 100644 pym/portage/tests/resolver/soname/test_skip_update.py
 create mode 100644 pym/portage/tests/resolver/soname/test_slot_conflict_reinstall.py
 create mode 100644 pym/portage/tests/resolver/soname/test_slot_conflict_update.py
 create mode 100644 pym/portage/tests/resolver/soname/test_soname_provided.py
 create mode 100644 pym/portage/tests/resolver/soname/test_unsatisfiable.py
 create mode 100644 pym/portage/tests/resolver/soname/test_unsatisfied.py

diff --git a/man/emerge.1 b/man/emerge.1
index fd9140f..7d8d003 100644
--- a/man/emerge.1
+++ b/man/emerge.1
@@ -568,6 +568,19 @@ only for debugging purposes, and it only affects built packages
 that specify slot/sub\-slot := operator dependencies which are
 supported beginning with \fBEAPI 5\fR.
 .TP
+.BR "\-\-ignore\-soname\-deps < y | n >"
+Ignore the soname dependencies of binary and installed packages. This
+option is enabled by default, since soname dependencies are relatively
+new, and the required metadata is not guaranteed to exist for binary and
+installed packages built with older versions of portage. Also, soname
+dependencies will be automatically ignored for dependency calculations
+that can pull unbuilt ebuilds into the dependency graph, since unbuilt
+ebuilds do not have any soname dependency metadata, making it impossible
+to determine whether an unresolved soname dependency can be satisfied.
+Therefore, \fB\-\-usepkgonly\fR (or \fB\-\-getbinpkgonly\fR) must be
+used in order to enable soname depedency resolution when installing
+packages.
+.TP
 .BR "-j [JOBS], \-\-jobs[=JOBS]"
 Specifies the number of packages to build simultaneously. If this option is
 given without an argument, emerge will not limit the number of jobs that can
diff --git a/man/portage.5 b/man/portage.5
index cec4e2f..ed5140d 100644
--- a/man/portage.5
+++ b/man/portage.5
@@ -36,6 +36,7 @@ package.use.stable.force
 package.use.stable.mask
 parent
 profile.bashrc
+soname.provided
 use.force
 use.mask
 use.stable.mask
@@ -504,6 +505,28 @@ If needed, this file can be used to set up a special environment for ebuilds,
 different from the standard root environment.  The syntax is the same as for
 any other bash script.
 .TP
+.BR soname.provided
+A list of sonames that portage should assume have been provided. This
+is useful for using portage to install binary packages on top of a base
+image which lacks /var/db/pkg for some reason (perhaps the image was
+assembled by another package manager, or by Linux From Scratch).
+
+.I Format:
+.nf
+\- comments begin with # (no inline comments)
+\- line begins with a multilib category
+\- multilib category is followed by one or more sonames
+\- only one multilib category is allowed per line
+\- prefixing an soname with a '\-' will negate a parent profile setting
+.fi
+
+.I Example:
+.nf
+# provide libc and ld-linux sonames for x86_32 and x86_64 categories
+x86_32 ld-linux.so.2 libc.so.6
+x86_64 ld-linux-x86-64.so.2 libc.so.6
+.fi
+.TP
 \fBuse.force\fR and \fBuse.stable.force\fR
 Some USE flags don't make sense to disable under certain conditions.  Here we
 list forced flags.
diff --git a/pym/_emerge/FakeVartree.py b/pym/_emerge/FakeVartree.py
index 254f667..ebe07bb 100644
--- a/pym/_emerge/FakeVartree.py
+++ b/pym/_emerge/FakeVartree.py
@@ -17,6 +17,7 @@ from portage.eapi import _get_eapi_attrs
 from portage.exception import InvalidData, InvalidDependString
 from portage.update import grab_updates, parse_updates, update_dbentries
 from portage.versions import _pkg_str
+from _emerge.resolver.DbapiProvidesIndex import PackageDbapiProvidesIndex
 
 if sys.hexversion >= 0x3000000:
 	long = int
@@ -24,12 +25,15 @@ if sys.hexversion >= 0x3000000:
 else:
 	_unicode = unicode
 
-class FakeVardbapi(PackageVirtualDbapi):
+class FakeVardbGetPath(object):
 	"""
 	Implements the vardbapi.getpath() method which is used in error handling
 	code for the Package class and vartree.get_provide().
 	"""
-	def getpath(self, cpv, filename=None):
+	def __init__(self, vardb):
+		self.settings = vardb.settings
+
+	def __call__(self, cpv, filename=None):
 		path = os.path.join(self.settings['EROOT'], VDB_PATH, cpv)
 		if filename is not None:
 			path =os.path.join(path, filename)
@@ -50,7 +54,8 @@ class FakeVartree(vartree):
 	is not a matching ebuild in the tree). Instances of this class are not
 	populated until the sync() method is called."""
 	def __init__(self, root_config, pkg_cache=None, pkg_root_config=None,
-		dynamic_deps=True, ignore_built_slot_operator_deps=False):
+		dynamic_deps=True, ignore_built_slot_operator_deps=False,
+		soname_deps=False):
 		self._root_config = root_config
 		self._dynamic_deps = dynamic_deps
 		self._ignore_built_slot_operator_deps = ignore_built_slot_operator_deps
@@ -68,7 +73,10 @@ class FakeVartree(vartree):
 			mykeys.append("_mtime_")
 		self._db_keys = mykeys
 		self._pkg_cache = pkg_cache
-		self.dbapi = FakeVardbapi(real_vartree.settings)
+		self.dbapi = PackageVirtualDbapi(real_vartree.settings)
+		if soname_deps:
+			self.dbapi = PackageDbapiProvidesIndex(self.dbapi)
+		self.dbapi.getpath = FakeVardbGetPath(self.dbapi)
 		self.dbapi._aux_cache_keys = set(self._db_keys)
 
 		# Initialize variables needed for lazy cache pulls of the live ebuild
diff --git a/pym/_emerge/Package.py b/pym/_emerge/Package.py
index 518dbf6..e8a13cb 100644
--- a/pym/_emerge/Package.py
+++ b/pym/_emerge/Package.py
@@ -13,9 +13,10 @@ from portage.cache.mappings import slot_dict_class
 from portage.const import EBUILD_PHASES
 from portage.dep import Atom, check_required_use, use_reduce, \
 	paren_enclose, _slot_separator, _repo_separator
+from portage.dep.soname.parse import parse_soname_deps
 from portage.versions import _pkg_str, _unknown_repo
 from portage.eapi import _get_eapi_attrs, eapi_has_use_aliases
-from portage.exception import InvalidDependString
+from portage.exception import InvalidData, InvalidDependString
 from portage.localization import _
 from _emerge.Task import Task
 
@@ -36,7 +37,8 @@ class Package(Task):
 		"inherited", "iuse", "mtime",
 		"pf", "root", "slot", "sub_slot", "slot_atom", "version") + \
 		("_invalid", "_masks", "_metadata", "_provided_cps",
-		"_raw_metadata", "_use", "_validated_atoms", "_visible")
+		"_raw_metadata", "_provides", "_requires", "_use",
+		"_validated_atoms", "_visible")
 
 	metadata_keys = [
 		"BUILD_TIME", "CHOST", "COUNTER", "DEPEND", "EAPI",
@@ -189,6 +191,16 @@ class Package(Task):
 	def stable(self):
 		return self.cpv.stable
 
+	@property
+	def provides(self):
+		self.invalid
+		return self._provides
+
+	@property
+	def requires(self):
+		self.invalid
+		return self._requires
+
 	@classmethod
 	def _gen_hash_key(cls, cpv=None, installed=None, onlydeps=None,
 		operation=None, repo_name=None, root_config=None,
@@ -311,6 +323,21 @@ class Package(Task):
 				if not self.installed:
 					self._metadata_exception(k, e)
 
+		if self.built:
+			k = 'PROVIDES'
+			try:
+				self._provides = frozenset(
+					parse_soname_deps(self._metadata[k]))
+			except InvalidData as e:
+				self._invalid_metadata(k + ".syntax", "%s: %s" % (k, e))
+
+			k = 'REQUIRES'
+			try:
+				self._requires = frozenset(
+					parse_soname_deps(self._metadata[k]))
+			except InvalidData as e:
+				self._invalid_metadata(k + ".syntax", "%s: %s" % (k, e))
+
 	def copy(self):
 		return Package(built=self.built, cpv=self.cpv, depth=self.depth,
 			installed=self.installed, metadata=self._raw_metadata,
@@ -727,32 +754,48 @@ class Package(Task):
 
 	def __lt__(self, other):
 		if other.cp != self.cp:
-			return False
+			return self.cp < other.cp
 		if portage.vercmp(self.version, other.version) < 0:
 			return True
 		return False
 
 	def __le__(self, other):
 		if other.cp != self.cp:
-			return False
+			return self.cp <= other.cp
 		if portage.vercmp(self.version, other.version) <= 0:
 			return True
 		return False
 
 	def __gt__(self, other):
 		if other.cp != self.cp:
-			return False
+			return self.cp > other.cp
 		if portage.vercmp(self.version, other.version) > 0:
 			return True
 		return False
 
 	def __ge__(self, other):
 		if other.cp != self.cp:
-			return False
+			return self.cp >= other.cp
 		if portage.vercmp(self.version, other.version) >= 0:
 			return True
 		return False
 
+	def with_use(self, use):
+		"""
+		Return an Package instance with the specified USE flags. The
+		current instance may be returned if it has identical USE flags.
+		@param use: a set of USE flags
+		@type use: frozenset
+		@return: A package with the specified USE flags
+		@rtype: Package
+		"""
+		if use is not self.use.enabled:
+			pkg = self.copy()
+			pkg._metadata["USE"] = " ".join(use)
+		else:
+			pkg = self
+		return pkg
+
 _all_metadata_keys = set(x for x in portage.auxdbkeys \
 	if not x.startswith("UNUSED_"))
 _all_metadata_keys.update(Package.metadata_keys)
diff --git a/pym/_emerge/actions.py b/pym/_emerge/actions.py
index d393c78..fa4fe19 100644
--- a/pym/_emerge/actions.py
+++ b/pym/_emerge/actions.py
@@ -787,7 +787,7 @@ def calc_depclean(settings, trees, ldpath_mtimes,
 		for pkg in vardb:
 			if spinner is not None:
 				spinner.update()
-			pkgs_for_cp = vardb.match_pkgs(pkg.cp)
+			pkgs_for_cp = vardb.match_pkgs(Atom(pkg.cp))
 			if not pkgs_for_cp or pkg not in pkgs_for_cp:
 				raise AssertionError("package expected in matches: " + \
 					"cp = %s, cpv = %s matches = %s" % \
@@ -931,8 +931,13 @@ def calc_depclean(settings, trees, ldpath_mtimes,
 
 		parent_strs = []
 		for parent, atoms in parent_atom_dict.items():
+			# Display package atoms and soname
+			# atoms in separate groups.
+			atoms = sorted(atoms, reverse=True,
+				key=operator.attrgetter('package'))
 			parent_strs.append("%s requires %s" %
-				(getattr(parent, "cpv", parent), ", ".join(atoms)))
+				(getattr(parent, "cpv", parent),
+				", ".join(_unicode(atom) for atom in atoms)))
 		parent_strs.sort()
 		msg = []
 		msg.append("  %s pulled in by:\n" % (child_node.cpv,))
diff --git a/pym/_emerge/create_depgraph_params.py b/pym/_emerge/create_depgraph_params.py
index 11e20f4..2c64928 100644
--- a/pym/_emerge/create_depgraph_params.py
+++ b/pym/_emerge/create_depgraph_params.py
@@ -21,6 +21,9 @@ def create_depgraph_params(myopts, myaction):
 	#	removal by the --depclean action as soon as possible
 	# ignore_built_slot_operator_deps: ignore the slot/sub-slot := operator parts
 	#	of dependencies that have been recorded when packages where built
+	# ignore_soname_deps: ignore the soname dependencies of built
+	#   packages, so that they do not trigger dependency resolution
+	#   failures, or cause packages to be rebuilt or replaced.
 	# with_test_deps: pull in test deps for packages matched by arguments
 	# changed_deps: rebuild installed packages with outdated deps
 	# binpkg_changed_deps: reject binary packages with outdated deps
@@ -34,6 +37,9 @@ def create_depgraph_params(myopts, myaction):
 	if ignore_built_slot_operator_deps is not None:
 		myparams["ignore_built_slot_operator_deps"] = ignore_built_slot_operator_deps
 
+	myparams["ignore_soname_deps"] = myopts.get(
+		"--ignore-soname-deps", "y")
+
 	dynamic_deps = myopts.get("--dynamic-deps")
 	if dynamic_deps is not None:
 		myparams["dynamic_deps"] = dynamic_deps
diff --git a/pym/_emerge/create_world_atom.py b/pym/_emerge/create_world_atom.py
index ac994cc..74b0fa5 100644
--- a/pym/_emerge/create_world_atom.py
+++ b/pym/_emerge/create_world_atom.py
@@ -3,7 +3,7 @@
 
 import sys
 
-from portage.dep import _repo_separator
+from portage.dep import Atom, _repo_separator
 from portage.exception import InvalidData
 
 if sys.hexversion >= 0x3000000:
@@ -40,7 +40,7 @@ def create_world_atom(pkg, args_set, root_config):
 			repos.append(portdb.repositories.get_name_for_location(tree))
 
 	available_slots = set()
-	for cpv in portdb.match(cp):
+	for cpv in portdb.match(Atom(cp)):
 		for repo in repos:
 			try:
 				available_slots.add(portdb._pkg_str(_unicode(cpv), repo).slot)
@@ -52,7 +52,7 @@ def create_world_atom(pkg, args_set, root_config):
 	if not slotted:
 		# check the vdb in case this is multislot
 		available_slots = set(vardb._pkg_str(cpv, None).slot \
-			for cpv in vardb.match(cp))
+			for cpv in vardb.match(Atom(cp)))
 		slotted = len(available_slots) > 1 or \
 			(len(available_slots) == 1 and "0" not in available_slots)
 	if slotted and arg_atom.without_repo != cp:
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index 1184dd6..63c89a4 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -20,6 +20,7 @@ from portage import _unicode_decode, _unicode_encode, _encodings
 from portage.const import PORTAGE_PACKAGE_ATOM, USER_CONFIG_PATH, VCS_DIRS
 from portage.dbapi import dbapi
 from portage.dbapi.dep_expand import dep_expand
+from portage.dbapi.DummyTree import DummyTree
 from portage.dbapi._similar_name_search import similar_name_search
 from portage.dep import Atom, best_match_to_list, extract_affecting_use, \
 	check_required_use, human_readable_required_use, match_from_list, \
@@ -77,6 +78,7 @@ from _emerge.UseFlagDisplay import pkg_use_display
 from _emerge.UserQuery import UserQuery
 
 from _emerge.resolver.backtracking import Backtracker, BacktrackParameter
+from _emerge.resolver.DbapiProvidesIndex import DbapiProvidesIndex
 from _emerge.resolver.package_tracker import PackageTracker, PackageTrackerDbapiWrapper
 from _emerge.resolver.slot_collision import slot_conflict_handler
 from _emerge.resolver.circular_dependency import circular_dependency_handler
@@ -125,6 +127,13 @@ class _frozen_depgraph_config(object):
 		# All Package instances
 		self._pkg_cache = {}
 		self._highest_license_masked = {}
+		# We can't know that an soname dep is unsatisfied if there are
+		# any unbuilt ebuilds in the graph, since unbuilt ebuilds have
+		# no soname data. Therefore, only enable soname dependency
+		# resolution if --usepkgonly is enabled, or for removal actions.
+		self.soname_deps_enabled = (
+			("--usepkgonly" in myopts or "remove" in params) and
+			params.get("ignore_soname_deps") != "y")
 		dynamic_deps = myopts.get("--dynamic-deps", "y") != "n"
 		ignore_built_slot_operator_deps = myopts.get(
 			"--ignore-built-slot-operator-deps", "n") == "y"
@@ -143,9 +152,13 @@ class _frozen_depgraph_config(object):
 					pkg_cache=self._pkg_cache,
 					pkg_root_config=self.roots[myroot],
 					dynamic_deps=dynamic_deps,
-					ignore_built_slot_operator_deps=ignore_built_slot_operator_deps)
+					ignore_built_slot_operator_deps=ignore_built_slot_operator_deps,
+					soname_deps=self.soname_deps_enabled)
 			self.pkgsettings[myroot] = portage.config(
 				clone=self.trees[myroot]["vartree"].settings)
+			if self.soname_deps_enabled and "remove" not in params:
+				self.trees[myroot]["bintree"] = DummyTree(
+					DbapiProvidesIndex(trees[myroot]["bintree"].dbapi))
 
 		self._required_set_names = set(["world"])
 
@@ -428,7 +441,9 @@ class _dynamic_depgraph_config(object):
 		self._traverse_ignored_deps = False
 		self._complete_mode = False
 		self._slot_operator_deps = {}
-		self._package_tracker = PackageTracker()
+		self._installed_sonames = collections.defaultdict(list)
+		self._package_tracker = PackageTracker(
+			soname_deps=depgraph._frozen_config.soname_deps_enabled)
 		# Track missed updates caused by solved conflicts.
 		self._conflict_missed_update = collections.defaultdict(dict)
 
@@ -536,6 +551,18 @@ class depgraph(object):
 
 		self.query = UserQuery(myopts).query
 
+	def _index_binpkgs(self):
+		for root in self._frozen_config.trees:
+			bindb = self._frozen_config.trees[root]["bintree"].dbapi
+			if bindb._provides_index:
+				# don't repeat this when backtracking
+				continue
+			root_config = self._frozen_config.roots[root]
+			for cpv in self._frozen_config._trees_orig[
+				root]["bintree"].dbapi.cpv_all():
+				bindb._provides_inject(
+					self._pkg(cpv, "binary", root_config))
+
 	def _load_vdb(self):
 		"""
 		Load installed package metadata if appropriate. This used to be called
@@ -571,6 +598,7 @@ class depgraph(object):
 				if not dynamic_deps:
 					for pkg in vardb:
 						self._dynamic_config._package_tracker.add_installed_pkg(pkg)
+						self._add_installed_sonames(pkg)
 				else:
 					max_jobs = self._frozen_config.myopts.get("--jobs")
 					max_load = self._frozen_config.myopts.get("--load-average")
@@ -589,6 +617,7 @@ class depgraph(object):
 		for pkg in fake_vartree.dbapi:
 			self._spinner_update()
 			self._dynamic_config._package_tracker.add_installed_pkg(pkg)
+			self._add_installed_sonames(pkg)
 			ebuild_path, repo_path = \
 				portdb.findname2(pkg.cpv, myrepo=pkg.repo)
 			if ebuild_path is None:
@@ -631,6 +660,8 @@ class depgraph(object):
 		"""
 
 		debug = "--debug" in self._frozen_config.myopts
+		installed_sonames = self._dynamic_config._installed_sonames
+		package_tracker = self._dynamic_config._package_tracker
 
 		# Get all atoms that might have caused a forced rebuild.
 		atoms = {}
@@ -666,6 +697,32 @@ class depgraph(object):
 				if inst_pkg is reinst_pkg or reinst_pkg is None:
 					continue
 
+				if (inst_pkg is not None and
+					inst_pkg.requires is not None):
+					for atom in inst_pkg.requires:
+						initial_providers = installed_sonames.get(
+							(root, atom))
+						if initial_providers is None:
+							continue
+						final_provider = next(
+							package_tracker.match(root, atom),
+							None)
+						if final_provider:
+							continue
+						for provider in initial_providers:
+							# Find the replacement child.
+							child = next((pkg for pkg in
+								package_tracker.match(
+								root, provider.slot_atom)
+								if not pkg.installed), None)
+
+							if child is None:
+								continue
+
+							forced_rebuilds.setdefault(
+								root, {}).setdefault(
+								child, set()).add(inst_pkg)
+
 				# Generate pseudo-deps for any slot-operator deps of
 				# inst_pkg. Its deps aren't in _slot_operator_deps
 				# because it hasn't been added to the graph, but we
@@ -1216,9 +1273,6 @@ class depgraph(object):
 				if is_non_conflict_parent:
 					parent = non_conflict_node
 
-				atom_set = InternalPackageSet(
-					initial_atoms=(atom,), allow_repo=True)
-
 				matched = []
 				for pkg in conflict:
 					if (pkg is highest_pkg and
@@ -1230,8 +1284,8 @@ class depgraph(object):
 						# version into the graph (bug #531656).
 						non_matching_forced.add(highest_pkg)
 
-					if atom_set.findAtomForPackage(pkg, \
-						modified_use=self._pkg_use_enabled(pkg)) and \
+					if atom.match(pkg.with_use(
+						self._pkg_use_enabled(pkg))) and \
 						not (is_arg_parent and pkg.installed):
 						matched.append(pkg)
 
@@ -1448,13 +1502,8 @@ class depgraph(object):
 			for parent_atom in slot_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,), allow_repo=True)
-				if atom_set.findAtomForPackage(pkg,
-					modified_use=self._pkg_use_enabled(pkg)):
+				if atom.match(pkg.with_use(self._pkg_use_enabled(pkg))):
 					parent_atoms.add(parent_atom)
 				else:
 					all_match = False
@@ -1533,7 +1582,11 @@ class depgraph(object):
 			if not isinstance(parent, Package):
 				continue
 
-			if atom.slot_operator != "=" or not parent.built:
+			if not parent.built:
+				continue
+
+			if not atom.soname and not (
+				atom.package and atom.slot_operator_built):
 				continue
 
 			if pkg not in conflict_pkgs:
@@ -1740,7 +1793,7 @@ class depgraph(object):
 			"""
 			built_slot_operator_parents = set()
 			for parent, atom in self._dynamic_config._parent_atoms.get(existing_pkg, []):
-				if atom.slot_operator_built:
+				if atom.soname or atom.slot_operator_built:
 					built_slot_operator_parents.add(parent)
 
 			for parent, atom in self._dynamic_config._parent_atoms.get(existing_pkg, []):
@@ -1778,6 +1831,9 @@ class depgraph(object):
 		for replacement_parent in self._iter_similar_available(dep.parent,
 			dep.parent.slot_atom, autounmask_level=autounmask_level):
 
+			if replacement_parent is dep.parent:
+				continue
+
 			if replacement_parent < dep.parent:
 				if want_downgrade_parent is None:
 					want_downgrade_parent = self._downgrade_probe(
@@ -1796,35 +1852,51 @@ class depgraph(object):
 			except InvalidDependString:
 				continue
 
+			if replacement_parent.requires is not None:
+				atoms = list(atoms)
+				atoms.extend(replacement_parent.requires)
+
 			# List of list of child,atom pairs for each atom.
 			replacement_candidates = []
 			# Set of all packages all atoms can agree on.
 			all_candidate_pkgs = None
+			atom_not_selected = False
 
 			for atom in atoms:
-				if atom.blocker or \
-					atom.cp != dep.atom.cp:
-					continue
 
-				# Discard USE deps, we're only searching for an approximate
-				# pattern, and dealing with USE states is too complex for
-				# this purpose.
-				unevaluated_atom = atom.unevaluated_atom
-				atom = atom.without_use
+				if not atom.package:
+					unevaluated_atom = None
+					if atom.match(dep.child):
+						# We are searching for a replacement_parent
+						# atom that will pull in a different child,
+						# so continue checking the rest of the atoms.
+						continue
+				else:
 
-				if replacement_parent.built and \
-					portage.dep._match_slot(atom, dep.child):
-					# Our selected replacement_parent appears to be built
-					# for the existing child selection. So, discard this
-					# parent and search for another.
-					break
+					if atom.blocker or \
+						atom.cp != dep.child.cp:
+						continue
+
+					# Discard USE deps, we're only searching for an
+					# approximate pattern, and dealing with USE states
+					# is too complex for this purpose.
+					unevaluated_atom = atom.unevaluated_atom
+					atom = atom.without_use
+
+					if replacement_parent.built and \
+						portage.dep._match_slot(atom, dep.child):
+						# We are searching for a replacement_parent
+						# atom that will pull in a different child,
+						# so continue checking the rest of the atoms.
+						continue
 
 				candidate_pkg_atoms = []
 				candidate_pkgs = []
 				for pkg in self._iter_similar_available(
 					dep.child, atom):
-					if pkg.slot == dep.child.slot and \
-						pkg.sub_slot == dep.child.sub_slot:
+					if (dep.atom.package and
+						pkg.slot == dep.child.slot and
+						pkg.sub_slot == dep.child.sub_slot):
 						# If slot/sub-slot is identical, then there's
 						# no point in updating.
 						continue
@@ -1863,7 +1935,8 @@ class depgraph(object):
 						# slot conflict).
 						insignificant = True
 
-					if not insignificant:
+					if (not insignificant and
+						unevaluated_atom is not None):
 						# Evaluate USE conditionals and || deps, in order
 						# to see if this atom is really desirable, since
 						# otherwise we may trigger an undesirable rebuild
@@ -1872,14 +1945,19 @@ class depgraph(object):
 							selected_atoms = self._select_atoms_probe(
 								dep.child.root, replacement_parent)
 						if unevaluated_atom not in selected_atoms:
-							continue
+							atom_not_selected = True
+							break
 
 					if not insignificant and \
 						check_reverse_dependencies(dep.child, pkg,
 							replacement_parent=replacement_parent):
 
-						candidate_pkg_atoms.append((pkg, unevaluated_atom))
+						candidate_pkg_atoms.append(
+							(pkg, unevaluated_atom or atom))
 						candidate_pkgs.append(pkg)
+
+				if atom_not_selected:
+					continue
 				replacement_candidates.append(candidate_pkg_atoms)
 				if all_candidate_pkgs is None:
 					all_candidate_pkgs = set(candidate_pkgs)
@@ -2183,10 +2261,8 @@ class depgraph(object):
 			for dep in slot_info:
 
 				atom = dep.atom
-				if atom.slot_operator is None:
-					continue
 
-				if not atom.slot_operator_built:
+				if not (atom.soname or atom.slot_operator_built):
 					new_child_slot = self._slot_change_probe(dep)
 					if new_child_slot is not None:
 						self._slot_change_backtrack(dep, new_child_slot)
@@ -2471,7 +2547,7 @@ class depgraph(object):
 							(dep.parent,
 							self._dynamic_config._runtime_pkg_mask[
 							dep.parent]), noiselevel=-1)
-				elif dep.atom.slot_operator_built and \
+				elif dep.atom.package and dep.atom.slot_operator_built and \
 					self._slot_operator_unsatisfied_probe(dep):
 					self._slot_operator_unsatisfied_backtrack(dep)
 					return 1
@@ -2483,8 +2559,9 @@ class depgraph(object):
 					# return None, and eventually we come through here
 					# and skip the "missing dependency" backtracking path.
 					dep_pkg, existing_node = \
-						self._select_package(dep.root, dep.atom.without_use,
-							onlydeps=dep.onlydeps)
+						self._select_package(dep.root,
+							dep.atom.without_use if dep.atom.package
+							else dep.atom, onlydeps=dep.onlydeps)
 					if dep_pkg is None:
 						self._dynamic_config._backtrack_infos["missing dependency"] = dep
 						self._dynamic_config._need_restart = True
@@ -2520,11 +2597,8 @@ class depgraph(object):
 			matches = pkg.cpv == existing_node.cpv
 			if pkg != existing_node and \
 				atom is not None:
-				# Use package set for matching since it will match via
-				# PROVIDE when necessary, while match_from_list does not.
-				matches = bool(InternalPackageSet(initial_atoms=(atom,),
-					allow_repo=True).findAtomForPackage(existing_node,
-					modified_use=self._pkg_use_enabled(existing_node)))
+				matches = atom.match(existing_node.with_use(
+					self._pkg_use_enabled(existing_node)))
 
 		return (existing_node, matches)
 
@@ -2563,8 +2637,8 @@ class depgraph(object):
 				# Display the specific atom from SetArg or
 				# Package types.
 				uneval = ""
-				if dep.atom and dep.atom.unevaluated_atom and \
-						dep.atom is not dep.atom.unevaluated_atom:
+				if (dep.atom and dep.atom.package and
+					dep.atom is not dep.atom.unevaluated_atom):
 					uneval = " (%s)" % (dep.atom.unevaluated_atom,)
 				writemsg_level(
 					"%s%s%s required by %s\n" %
@@ -2728,8 +2802,9 @@ class depgraph(object):
 			not (deep is not True and depth > deep))
 
 		dep.child = pkg
-		if (not pkg.onlydeps and
-			dep.atom and dep.atom.slot_operator is not None):
+		if not pkg.onlydeps and dep.atom and (
+			dep.atom.soname or
+			dep.atom.slot_operator == "="):
 			self._add_slot_operator_dep(dep)
 
 		recurse = deep is True or depth + 1 <= deep
@@ -2745,6 +2820,32 @@ class depgraph(object):
 			dep_stack.append(pkg)
 		return 1
 
+	def _add_installed_sonames(self, pkg):
+		if (self._frozen_config.soname_deps_enabled and
+			pkg.provides is not None):
+			for atom in pkg.provides:
+				self._dynamic_config._installed_sonames[
+					(pkg.root, atom)].append(pkg)
+
+	def _add_pkg_soname_deps(self, pkg, allow_unsatisfied=False):
+		if (self._frozen_config.soname_deps_enabled and
+			pkg.requires is not None):
+			if isinstance(pkg.depth, int):
+				depth = pkg.depth + 1
+			else:
+				depth = pkg.depth
+			soname_provided = self._frozen_config.roots[
+				pkg.root].settings.soname_provided
+			for atom in pkg.requires:
+				if atom in soname_provided:
+					continue
+				dep = Dependency(atom=atom, blocker=False, depth=depth,
+					parent=pkg, priority=self._priority(runtime=True),
+					root=pkg.root)
+				if not self._add_dep(dep,
+					allow_unsatisfied=allow_unsatisfied):
+					return False
+		return True
 
 	def _remove_pkg(self, pkg):
 		"""
@@ -2832,6 +2933,10 @@ class depgraph(object):
 
 	def _add_pkg_deps(self, pkg, allow_unsatisfied=False):
 
+		if not self._add_pkg_soname_deps(pkg,
+			allow_unsatisfied=allow_unsatisfied):
+			return False
+
 		myroot = pkg.root
 		metadata = pkg._metadata
 		removal_action = "remove" in self._dynamic_config.myparams
@@ -3482,6 +3587,9 @@ class depgraph(object):
 		self._dynamic_config._initial_arg_list and call self._resolve to create the
 		appropriate depgraph and return a favorite list."""
 		self._load_vdb()
+		if (self._frozen_config.soname_deps_enabled and
+			"remove" not in self._dynamic_config.myparams):
+			self._index_binpkgs()
 		debug = "--debug" in self._frozen_config.myopts
 		root_config = self._frozen_config.roots[self._frozen_config.target_root]
 		sets = root_config.sets
@@ -4451,7 +4559,7 @@ class depgraph(object):
 			# (aka unsatisfied_dependency is not None) we
 			# need that the start_node doesn't match the atom.
 			if not unsatisfied_dependency or \
-				not InternalPackageSet(initial_atoms=(patom,)).findAtomForPackage(start_node):
+				not patom.match(start_node):
 				start_node_parent_atoms.setdefault(patom, []).append(ppkg)
 
 		if start_node_parent_atoms:
@@ -4459,7 +4567,16 @@ class depgraph(object):
 			# If not, then this package got pulled in by an Arg and
 			# will be correctly handled by the code that handles later
 			# packages in the dep chain.
-			best_match = best_match_to_list(node.cpv, start_node_parent_atoms)
+			if (any(not x.package for x in start_node_parent_atoms) and
+				any(x.package for x in start_node_parent_atoms)):
+				for x in list(start_node_parent_atoms):
+					if not x.package:
+						del start_node_parent_atoms[x]
+			if next(iter(start_node_parent_atoms)).package:
+				best_match = best_match_to_list(node.cpv,
+					start_node_parent_atoms)
+			else:
+				best_match = next(iter(start_node_parent_atoms))
 
 			child = node
 			for ppkg in start_node_parent_atoms[best_match]:
@@ -4486,10 +4603,11 @@ class depgraph(object):
 				for ppkg, patom in all_parents[child]:
 					if ppkg == node:
 						if child is start_node and unsatisfied_dependency and \
-							InternalPackageSet(initial_atoms=(patom,)).findAtomForPackage(child):
+							patom.match(child):
 							# This atom is satisfied by child, there must be another atom.
 							continue
-						atom = patom.unevaluated_atom
+						atom = (patom.unevaluated_atom
+							if patom.package else patom)
 						break
 
 				dep_strings = set()
@@ -4558,8 +4676,7 @@ class depgraph(object):
 						# flag changes.
 						for ppkg, atom in all_parents[start_node]:
 							if parent is ppkg:
-								atom_set = InternalPackageSet(initial_atoms=(atom,))
-								if not atom_set.findAtomForPackage(start_node):
+								if not atom.match(start_node):
 									parent_unsatisfied = parent
 								break
 					else:
@@ -4602,11 +4719,13 @@ class depgraph(object):
 		"""
 		backtrack_mask = False
 		autounmask_broke_use_dep = False
-		atom_set = InternalPackageSet(initial_atoms=(atom.without_use,),
-			allow_repo=True)
-		atom_set_with_use = InternalPackageSet(initial_atoms=(atom,),
-			allow_repo=True)
-		xinfo = '"%s"' % atom.unevaluated_atom
+		if atom.package:
+			xinfo = '"%s"' % atom.unevaluated_atom
+			atom_without_use = atom.without_use
+		else:
+			xinfo = '"%s"' % atom
+			atom_without_use = None
+
 		if arg:
 			xinfo='"%s"' % arg
 		if isinstance(myparent, AtomArg):
@@ -4630,12 +4749,18 @@ class depgraph(object):
 		for db, pkg_type, built, installed, db_keys in dbs:
 			if installed:
 				continue
-			if hasattr(db, "xmatch"):
+			if atom.soname:
+				if not isinstance(db, DbapiProvidesIndex):
+					continue
+				cpv_list = db.match(atom)
+			elif hasattr(db, "xmatch"):
 				cpv_list = db.xmatch("match-all-cpv-only", atom.without_use)
 			else:
 				cpv_list = db.match(atom.without_use)
 
-			if atom.repo is None and hasattr(db, "getRepositories"):
+			if atom.soname:
+				repo_list = [None]
+			elif atom.repo is None and hasattr(db, "getRepositories"):
 				repo_list = db.getRepositories()
 			else:
 				repo_list = [atom.repo]
@@ -4666,8 +4791,10 @@ class depgraph(object):
 							masked_packages.append(
 								(root_config, pkgsettings, cpv, repo, metadata, mreasons))
 							continue
-						if not atom_set.findAtomForPackage(pkg,
-							modified_use=self._pkg_use_enabled(pkg)):
+						if atom.soname and not atom.match(pkg):
+							continue
+						if (atom_without_use is not None and
+							not atom_without_use.match(pkg)):
 							continue
 						if pkg in self._dynamic_config._runtime_pkg_mask:
 							backtrack_reasons = \
@@ -4680,12 +4807,12 @@ class depgraph(object):
 							mreasons = ["exclude option"]
 						if mreasons:
 							masked_pkg_instances.add(pkg)
-						if atom.unevaluated_atom.use:
+						if atom.package and atom.unevaluated_atom.use:
 							try:
 								if not pkg.iuse.is_valid_flag(atom.unevaluated_atom.use.required) \
 									or atom.violated_conditionals(self._pkg_use_enabled(pkg), pkg.iuse.is_valid_flag).use:
 									missing_use.append(pkg)
-									if atom_set_with_use.findAtomForPackage(pkg):
+									if atom.match(pkg):
 										autounmask_broke_use_dep = True
 									if not mreasons:
 										continue
@@ -4952,7 +5079,7 @@ class depgraph(object):
 			mask_docs = True
 		else:
 			cp_exists = False
-			if not atom.cp.startswith("null/"):
+			if atom.package and not atom.cp.startswith("null/"):
 				for pkg in self._iter_match_pkgs_any(
 					root_config, Atom(atom.cp)):
 					cp_exists = True
@@ -5011,7 +5138,28 @@ class depgraph(object):
 				pkg_type, atom, onlydeps=onlydeps):
 				yield pkg
 
-	def _iter_match_pkgs(self, root_config, pkg_type, atom, onlydeps=False):
+	def _iter_match_pkgs(self, root_config, pkg_type, atom,
+		onlydeps=False):
+		if atom.package:
+			return self._iter_match_pkgs_atom(root_config, pkg_type,
+				atom, onlydeps=onlydeps)
+		else:
+			return self._iter_match_pkgs_soname(root_config, pkg_type,
+				atom, onlydeps=onlydeps)
+
+	def _iter_match_pkgs_soname(self, root_config, pkg_type, atom,
+		onlydeps=False):
+		db = root_config.trees[self.pkg_tree_map[pkg_type]].dbapi
+		installed = pkg_type == 'installed'
+
+		if isinstance(db, DbapiProvidesIndex):
+			# descending order
+			for cpv in reversed(db.match(atom)):
+				yield self._pkg(cpv, pkg_type, root_config,
+					installed=installed, onlydeps=onlydeps)
+
+	def _iter_match_pkgs_atom(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
@@ -5114,14 +5262,21 @@ class depgraph(object):
 						return
 
 	def _select_pkg_highest_available(self, root, atom, onlydeps=False, parent=None):
-		cache_key = (root, atom, atom.unevaluated_atom, onlydeps, self._dynamic_config._autounmask)
+		if atom.package:
+			cache_key = (root, atom, atom.unevaluated_atom, onlydeps,
+				self._dynamic_config._autounmask)
+			self._dynamic_config._highest_pkg_cache_cp_map.\
+				setdefault((root, atom.cp), []).append(cache_key)
+		else:
+			cache_key = (root, atom, onlydeps,
+				self._dynamic_config._autounmask)
+			self._dynamic_config._highest_pkg_cache_cp_map.\
+				setdefault((root, atom), []).append(cache_key)
 		ret = self._dynamic_config._highest_pkg_cache.get(cache_key)
 		if ret is not None:
 			return ret
 		ret = self._select_pkg_highest_available_imp(root, atom, onlydeps=onlydeps, parent=parent)
 		self._dynamic_config._highest_pkg_cache[cache_key] = ret
-		self._dynamic_config._highest_pkg_cache_cp_map. \
-			setdefault(atom.cp, []).append(cache_key)
 		pkg, existing = ret
 		if pkg is not None:
 			if self._pkg_visibility_check(pkg) and \
@@ -5136,11 +5291,15 @@ class depgraph(object):
 		return False
 
 	def _prune_highest_pkg_cache(self, pkg):
+		cache = self._dynamic_config._highest_pkg_cache
+		key_map = self._dynamic_config._highest_pkg_cache_cp_map
 		for cp in pkg.provided_cps:
-			for cache_key in self._dynamic_config. \
-				_highest_pkg_cache_cp_map.pop(cp, []):
-				self._dynamic_config._highest_pkg_cache.pop(
-					cache_key, None)
+			for cache_key in key_map.pop((pkg.root, cp), []):
+				cache.pop(cache_key, None)
+		if pkg.provides is not None:
+			for atom in pkg.provides:
+				for cache_key in key_map.pop((pkg.root, atom), []):
+					cache.pop(cache_key, None)
 
 	def _want_installed_pkg(self, pkg):
 		"""
@@ -5540,12 +5699,13 @@ class depgraph(object):
 		# 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
-		have_new_virt = atom_cp.startswith("virtual/") and \
-			self._have_new_virt(root, atom_cp)
-		atom_set = InternalPackageSet(initial_atoms=(atom,), allow_repo=True)
+		atom_cp = None
+		have_new_virt = None
+		if atom.package:
+			atom_cp = atom.cp
+			have_new_virt = (atom_cp.startswith("virtual/") and
+				self._have_new_virt(root, atom_cp))
+
 		existing_node = None
 		myeb = None
 		rebuilt_binaries = 'rebuilt_binaries' in self._dynamic_config.myparams
@@ -5590,9 +5750,10 @@ class depgraph(object):
 				# Ignore USE deps for the initial match since we want to
 				# ensure that updates aren't missed solely due to the user's
 				# USE configuration.
-				for pkg in self._iter_match_pkgs(root_config, pkg_type, atom.without_use,
+				for pkg in self._iter_match_pkgs(root_config, pkg_type,
+					atom.without_use if atom.package else atom,
 					onlydeps=onlydeps):
-					if pkg.cp != atom_cp and have_new_virt:
+					if have_new_virt is True and pkg.cp != atom_cp:
 						# pull in a new-style virtual instead
 						continue
 					if pkg in self._dynamic_config._runtime_pkg_mask:
@@ -5711,14 +5872,14 @@ class depgraph(object):
 					if not installed and myarg:
 						found_available_arg = True
 
-					if atom.unevaluated_atom.use:
+					if atom.package and atom.unevaluated_atom.use:
 						#Make sure we don't miss a 'missing IUSE'.
 						if pkg.iuse.get_missing_iuse(atom.unevaluated_atom.use.required):
 							# Don't add this to packages_with_invalid_use_config
 							# since IUSE cannot be adjusted by the user.
 							continue
 
-					if atom.use:
+					if atom.package and atom.use is not None:
 
 						if autounmask_level and autounmask_level.allow_use_changes and not pkg.built:
 							target_use = {}
@@ -5778,7 +5939,7 @@ class depgraph(object):
 								packages_with_invalid_use_config.append(pkg)
 							continue
 
-					if pkg.cp == atom_cp:
+					if atom_cp is None or pkg.cp == atom_cp:
 						if highest_version is None:
 							highest_version = pkg
 						elif pkg > highest_version:
@@ -5797,9 +5958,11 @@ class depgraph(object):
 
 						# Use PackageSet.findAtomForPackage()
 						# for PROVIDE support.
-						if atom_set.findAtomForPackage(e_pkg, modified_use=self._pkg_use_enabled(e_pkg)):
+						if atom.match(e_pkg.with_use(
+							self._pkg_use_enabled(e_pkg))):
 							if highest_version and \
-								e_pkg.cp == atom_cp and \
+								(atom_cp is None or
+								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
@@ -5865,7 +6028,8 @@ class depgraph(object):
 					# Compare current config to installed package
 					# and do not reinstall if possible.
 					if not installed and not useoldpkg and cpv in vardb.match(atom):
-						inst_pkg = vardb.match_pkgs('=' + pkg.cpv)[0]
+						inst_pkg = vardb.match_pkgs(
+							Atom('=' + pkg.cpv))[0]
 						if "--newrepo" in self._frozen_config.myopts and pkg.repo != inst_pkg.repo:
 							reinstall = True
 						elif reinstall_use:
@@ -5906,8 +6070,9 @@ class depgraph(object):
 
 		# Filter out any old-style virtual matches if they are
 		# mixed with new-style virtual matches.
-		cp = atom.cp
+		cp = atom_cp
 		if len(matched_packages) > 1 and \
+			cp is not None and \
 			"virtual" == portage.catsplit(cp)[0]:
 			for pkg in matched_packages:
 				if pkg.cp != cp:
@@ -6893,7 +7058,7 @@ class depgraph(object):
 		runtime_deps = InternalPackageSet(
 			initial_atoms=[PORTAGE_PACKAGE_ATOM])
 		running_portage = self._frozen_config.trees[running_root]["vartree"].dbapi.match_pkgs(
-			PORTAGE_PACKAGE_ATOM)
+			Atom(PORTAGE_PACKAGE_ATOM))
 		replacement_portage = list(self._dynamic_config._package_tracker.match(
 			running_root, Atom(PORTAGE_PACKAGE_ATOM)))
 
diff --git a/pym/_emerge/main.py b/pym/_emerge/main.py
index 5d5e936..b56277c 100644
--- a/pym/_emerge/main.py
+++ b/pym/_emerge/main.py
@@ -455,6 +455,16 @@ def parse_opts(tmpcmdline, silent=False):
 			"choices": y_or_n
 		},
 
+		"--ignore-soname-deps": {
+			"help": "Ignore the soname dependencies of binary and "
+				"installed packages. This option is enabled by "
+				"default, since soname dependencies are relatively "
+				"new, and the required metadata is not guaranteed to "
+				"exist for binary and installed packages built with "
+				"older versions of portage.",
+			"choices": y_or_n
+		},
+
 		"--jobs": {
 
 			"shortopt" : "-j",
diff --git a/pym/_emerge/resolver/DbapiProvidesIndex.py b/pym/_emerge/resolver/DbapiProvidesIndex.py
new file mode 100644
index 0000000..59ae719
--- /dev/null
+++ b/pym/_emerge/resolver/DbapiProvidesIndex.py
@@ -0,0 +1,101 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+import bisect
+import collections
+import sys
+
+class DbapiProvidesIndex(object):
+	"""
+	The DbapiProvidesIndex class is used to wrap existing dbapi
+	interfaces, index packages by the sonames that they provide, and
+	implement the dbapi.match method for SonameAtom instances. Since
+	this class acts as a wrapper, it can be used conditionally, so that
+	soname indexing overhead is avoided when soname dependency
+	resolution is disabled.
+
+	Since it's possible for soname atom match results to consist of
+	packages with multiple categories or names, it is essential that
+	Package.__lt__ behave meaningfully when Package.cp is dissimilar,
+	so that match results will be correctly ordered by version for each
+	value of Package.cp.
+	"""
+
+	_copy_attrs = ('aux_get', 'aux_update', 'categories', 'cpv_all',
+		'cpv_exists', 'cp_all', 'cp_list', 'getfetchsizes',
+		'settings', '_aux_cache_keys', '_clear_cache',
+		'_cpv_sort_ascending', '_pkg_str', '_pkg_str_aux_keys')
+
+	def __init__(self, db):
+		self._db = db
+		for k in self._copy_attrs:
+			try:
+				setattr(self, k, getattr(db, k))
+			except AttributeError:
+				pass
+		self._provides_index = collections.defaultdict(list)
+
+	def match(self, atom, use_cache=DeprecationWarning):
+		if atom.soname:
+			result = self._match_soname(atom)
+		else:
+			result = self._db.match(atom)
+		return result
+
+	def _match_soname(self, atom):
+		result = self._provides_index.get(atom)
+		if result is None:
+			result = []
+		else:
+			result = [pkg.cpv for pkg in result]
+		return result
+
+	def _provides_inject(self, pkg):
+		index = self._provides_index
+		for atom in pkg.provides:
+			# Use bisect.insort for ordered match results.
+			bisect.insort(index[atom], pkg)
+
+class PackageDbapiProvidesIndex(DbapiProvidesIndex):
+	"""
+	This class extends DbapiProvidesIndex in order to make it suitable
+	for wrapping a PackageVirtualDbapi instance.
+	"""
+
+	_copy_attrs = DbapiProvidesIndex._copy_attrs + (
+		"clear", "get", "_cpv_map")
+
+	def clear(self):
+		self._db.clear()
+		self._provides_index.clear()
+
+	def __bool__(self):
+		return bool(self._db)
+
+	if sys.hexversion < 0x3000000:
+		__nonzero__ = __bool__
+
+	def __iter__(self):
+		return iter(self._db)
+
+	def __contains__(self, item):
+		return item in self._db
+
+	def match_pkgs(self, atom):
+		return [self._db._cpv_map[cpv] for cpv in self.match(atom)]
+
+	def cpv_inject(self, pkg):
+		self._db.cpv_inject(pkg)
+		self._provides_inject(pkg)
+
+	def cpv_remove(self, pkg):
+		self._db.cpv_remove(pkg)
+		index = self._provides_index
+		for atom in pkg.provides:
+			items = index[atom]
+			try:
+				items.remove(pkg)
+			except ValueError:
+				pass
+			if not items:
+				del index[atom]
diff --git a/pym/_emerge/resolver/output.py b/pym/_emerge/resolver/output.py
index 14d1b28..7df0302 100644
--- a/pym/_emerge/resolver/output.py
+++ b/pym/_emerge/resolver/output.py
@@ -15,7 +15,7 @@ import sys
 import portage
 from portage import os
 from portage.dbapi.dep_expand import dep_expand
-from portage.dep import cpvequal, _repo_separator, _slot_separator
+from portage.dep import Atom, cpvequal, _repo_separator, _slot_separator
 from portage.eapi import _get_eapi_attrs
 from portage.exception import InvalidDependString, SignatureException
 from portage.localization import localized_size
@@ -659,7 +659,8 @@ class Display(object):
 
 		if self.vardb.cpv_exists(pkg.cpv):
 			# Do a cpv match first, in case the SLOT has changed.
-			pkg_info.previous_pkg = self.vardb.match_pkgs('=' + pkg.cpv)[0]
+			pkg_info.previous_pkg = self.vardb.match_pkgs(
+				Atom('=' + pkg.cpv))[0]
 		else:
 			slot_matches = self.vardb.match_pkgs(pkg.slot_atom)
 			if slot_matches:
@@ -742,7 +743,7 @@ class Display(object):
 		"""
 		myoldbest = []
 		myinslotlist = None
-		installed_versions = self.vardb.match_pkgs(pkg.cp)
+		installed_versions = self.vardb.match_pkgs(Atom(pkg.cp))
 		if self.vardb.cpv_exists(pkg.cpv):
 			pkg_info.attr_display.replace = True
 			installed_version = pkg_info.previous_pkg
@@ -931,6 +932,9 @@ def format_unmatched_atom(pkg, atom, pkg_use_enabled):
 	#	4. repository
 	#	5. USE
 
+	if atom.soname:
+		return "%s" % (atom,), ""
+
 	highlight = set()
 
 	def perform_coloring():
diff --git a/pym/_emerge/resolver/package_tracker.py b/pym/_emerge/resolver/package_tracker.py
index 406d5ce..398d4cf 100644
--- a/pym/_emerge/resolver/package_tracker.py
+++ b/pym/_emerge/resolver/package_tracker.py
@@ -3,6 +3,7 @@
 
 from __future__ import print_function
 
+import bisect
 import collections
 
 import portage
@@ -43,7 +44,11 @@ class PackageTracker(object):
 		3) Packages that block each other.
 	"""
 
-	def __init__(self):
+	def __init__(self, soname_deps=False):
+		"""
+		@param soname_deps: enable soname match support
+		@type soname_deps: bool
+		"""
 		# Mapping from package keys to set of packages.
 		self._cp_pkg_map = collections.defaultdict(list)
 		self._cp_vdb_pkg_map = collections.defaultdict(list)
@@ -61,6 +66,10 @@ class PackageTracker(object):
 		self._replaced_by = collections.defaultdict(list)
 
 		self._match_cache = collections.defaultdict(dict)
+		if soname_deps:
+			self._provides_index = collections.defaultdict(list)
+		else:
+			self._provides_index = None
 
 	def add_pkg(self, pkg):
 		"""
@@ -85,8 +94,19 @@ class PackageTracker(object):
 				self._replacing[pkg].append(installed)
 				self._replaced_by[installed].append(pkg)
 
+		self._add_provides(pkg)
+
 		self._match_cache.pop(cp_key, None)
 
+	def _add_provides(self, pkg):
+		if (self._provides_index is not None and
+			pkg.provides is not None):
+			index = self._provides_index
+			root = pkg.root
+			for atom in pkg.provides:
+				# Use bisect.insort for ordered match results.
+				bisect.insort(index[(root, atom)], pkg)
+
 	def add_installed_pkg(self, installed):
 		"""
 		Add an installed package during vdb load. These packages
@@ -133,6 +153,19 @@ class PackageTracker(object):
 				del self._replaced_by[installed]
 		del self._replacing[pkg]
 
+		if self._provides_index is not None:
+			index = self._provides_index
+			root = pkg.root
+			for atom in pkg.provides:
+				key = (root, atom)
+				items = index[key]
+				try:
+					items.remove(pkg)
+				except ValueError:
+					pass
+				if not items:
+					del index[key]
+
 		self._match_cache.pop(cp_key, None)
 
 	def discard_pkg(self, pkg):
@@ -151,6 +184,9 @@ class PackageTracker(object):
 		If 'installed' is True, installed non-replaced
 		packages may also be returned.
 		"""
+		if atom.soname:
+			return iter(self._provides_index.get((root, atom), []))
+
 		cp_key = root, atom.cp
 		cache_key = root, atom, atom.unevaluated_atom, installed
 		try:
@@ -285,8 +321,6 @@ class PackageTrackerDbapiWrapper(object):
 		self._package_tracker.add_pkg(pkg)
 
 	def match_pkgs(self, atom):
-		if not isinstance(atom, Atom):
-			atom = Atom(atom)
 		ret = sorted(self._package_tracker.match(self._root, atom),
 			key=cmp_sort_key(lambda x, y: vercmp(x.version, y.version)))
 		return ret
@@ -298,4 +332,4 @@ class PackageTrackerDbapiWrapper(object):
 		return self.match_pkgs(atom)
 
 	def cp_list(self, cp):
-		return self.match_pkgs(cp)
+		return self.match_pkgs(Atom(cp))
diff --git a/pym/_emerge/resolver/slot_collision.py b/pym/_emerge/resolver/slot_collision.py
index baeab08..5473d72 100644
--- a/pym/_emerge/resolver/slot_collision.py
+++ b/pym/_emerge/resolver/slot_collision.py
@@ -271,16 +271,27 @@ class slot_conflict_handler(object):
 					num_all_specific_atoms = 0
 
 					for ppkg, atom in parent_atoms:
-						atom_set = InternalPackageSet(initial_atoms=(atom,))
-						atom_without_use_set = InternalPackageSet(initial_atoms=(atom.without_use,))
-						atom_without_use_and_slot_set = InternalPackageSet(initial_atoms=(
-							atom.without_use.without_slot,))
+						if not atom.soname:
+							atom_set = InternalPackageSet(
+								initial_atoms=(atom,))
+							atom_without_use_set = InternalPackageSet(
+								initial_atoms=(atom.without_use,))
+							atom_without_use_and_slot_set = \
+								InternalPackageSet(initial_atoms=(
+								atom.without_use.without_slot,))
 
 						for other_pkg in pkgs:
 							if other_pkg == pkg:
 								continue
 
-							if not atom_without_use_and_slot_set.findAtomForPackage(other_pkg, \
+							if atom.soname:
+								# The soname does not match.
+								key = ("soname", atom)
+								atoms = collision_reasons.get(key, set())
+								atoms.add((ppkg, atom, other_pkg))
+								num_all_specific_atoms += 1
+								collision_reasons[key] = atoms
+							elif not atom_without_use_and_slot_set.findAtomForPackage(other_pkg,
 								modified_use=_pkg_use_enabled(other_pkg)):
 								if atom.operator is not None:
 									# The version range does not match.
@@ -381,7 +392,7 @@ class slot_conflict_handler(object):
 							if not verboseconflicts:
 								selected_for_display.update(
 										best_matches.values())
-						elif type == "slot":
+						elif type in ("soname", "slot"):
 							for ppkg, atom, other_pkg in parents:
 								selected_for_display.add((ppkg, atom))
 								if not verboseconflicts:
@@ -532,7 +543,10 @@ class slot_conflict_handler(object):
 								ordered_list.append(parent_atom)
 					for parent_atom in ordered_list:
 						parent, atom = parent_atom
-						if isinstance(parent, PackageArg):
+						if atom.soname:
+							msg.append("%s required by %s\n" %
+								(atom, parent))
+						elif isinstance(parent, PackageArg):
 							# For PackageArg it's
 							# redundant to display the atom attribute.
 							msg.append("%s\n" % (parent,))
@@ -677,6 +691,9 @@ class slot_conflict_handler(object):
 		for id, pkg in enumerate(config):
 			involved_flags = {}
 			for ppkg, atom in all_conflict_atoms_by_slotatom[id]:
+				if not atom.package:
+					continue
+
 				if ppkg in conflict_nodes and not ppkg in config:
 					#The parent is part of a slot conflict itself and is
 					#not part of the current config.
@@ -882,6 +899,8 @@ class slot_conflict_handler(object):
 
 			#Go through all (parent, atom) pairs for the current slot conflict.
 			for ppkg, atom in all_conflict_atoms_by_slotatom[id]:
+				if not atom.package:
+					continue
 				use = atom.unevaluated_atom.use
 				if not use:
 					#No need to force something for an atom without USE conditionals.
@@ -952,6 +971,8 @@ class slot_conflict_handler(object):
 					new_use = old_use
 
 			for ppkg, atom in all_conflict_atoms_by_slotatom[id]:
+				if not atom.package:
+					continue
 				if not hasattr(ppkg, "use"):
 					#It's a SetArg or something like that.
 					continue
diff --git a/pym/portage/dbapi/DummyTree.py b/pym/portage/dbapi/DummyTree.py
new file mode 100644
index 0000000..6579e88
--- /dev/null
+++ b/pym/portage/dbapi/DummyTree.py
@@ -0,0 +1,16 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+class DummyTree(object):
+	"""
+	Most internal code only accesses the "dbapi" attribute of the
+	binarytree, portagetree, and vartree classes. DummyTree is useful
+	in cases where alternative dbapi implementations (or wrappers that
+	modify or extend behavior of existing dbapi implementations) are
+	needed, since it allows these implementations to be exposed through
+	an interface which is minimally compatible with the *tree classes.
+	"""
+	__slots__ = ("dbapi",)
+
+	def __init__(self, dbapi):
+		self.dbapi = dbapi
diff --git a/pym/portage/dep/__init__.py b/pym/portage/dep/__init__.py
index c457df0..e2e416c 100644
--- a/pym/portage/dep/__init__.py
+++ b/pym/portage/dep/__init__.py
@@ -1172,6 +1172,12 @@ class Atom(_unicode):
 	class emulates most of the str methods that are useful with atoms.
 	"""
 
+	# Distiguishes package atoms from other atom types
+	package = True
+
+	# Distiguishes soname atoms from other atom types
+	soname = False
+
 	class _blocker(object):
 		__slots__ = ("overlap",)
 
@@ -1561,6 +1567,25 @@ class Atom(_unicode):
 		memo[id(self)] = self
 		return self
 
+	def match(self, pkg):
+		"""
+		Check if the given package instance matches this atom. This
+		includes support for virtual matches via PROVIDE metadata.
+
+		@param pkg: a Package instance
+		@type pkg: Package
+		@return: True if this atom matches pkg, otherwise False
+		@rtype: bool
+		"""
+		if pkg.cp == self.cp:
+			return bool(match_from_list(self, [pkg]))
+		else:
+			for provided_cp in pkg.provided_cps:
+				if provided_cp == self.cp:
+					return bool(match_from_list(
+						self.replace(self.cp, provided_cp, 1), [pkg]))
+		return False
+
 _extended_cp_re_cache = {}
 
 def extended_cp_match(extended_cp, other_cp):
diff --git a/pym/portage/dep/soname/SonameAtom.py b/pym/portage/dep/soname/SonameAtom.py
new file mode 100644
index 0000000..a7dad97
--- /dev/null
+++ b/pym/portage/dep/soname/SonameAtom.py
@@ -0,0 +1,72 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from __future__ import unicode_literals
+
+import sys
+
+from portage import _encodings, _unicode_encode
+
+class SonameAtom(object):
+
+	__slots__ = ("multilib_category", "soname", "_hash_key",
+		"_hash_value")
+
+	# Distiguishes package atoms from other atom types
+	package = False
+
+	def __init__(self, multilib_category, soname):
+		object.__setattr__(self, "multilib_category", multilib_category)
+		object.__setattr__(self, "soname", soname)
+		object.__setattr__(self, "_hash_key",
+			(multilib_category, soname))
+		object.__setattr__(self, "_hash_value", hash(self._hash_key))
+
+	def __setattr__(self, name, value):
+		raise AttributeError("SonameAtom instances are immutable",
+			self.__class__, name, value)
+
+	def __hash__(self):
+		return self._hash_value
+
+	def __eq__(self, other):
+		try:
+			return self._hash_key == other._hash_key
+		except AttributeError:
+			return False
+
+	def __ne__(self, other):
+		try:
+			return self._hash_key != other._hash_key
+		except AttributeError:
+			return True
+
+	def __repr__(self):
+		return "%s('%s', '%s')" % (
+			self.__class__.__name__,
+			self.multilib_category,
+			self.soname
+		)
+
+	def __str__(self):
+		return "%s: %s" % (self.multilib_category, self.soname)
+
+	if sys.hexversion < 0x3000000:
+
+		__unicode__ = __str__
+
+		def __str__(self):
+			return _unicode_encode(self.__unicode__(),
+				encoding=_encodings['content'])
+
+	def match(self, pkg):
+		"""
+		Check if the given package instance matches this atom. Unbuilt
+		ebuilds, which do not have soname metadata, will never match.
+
+		@param pkg: a Package instance
+		@type pkg: Package
+		@return: True if this atom matches pkg, otherwise False
+		@rtype: bool
+		"""
+		return pkg.provides is not None and self in pkg.provides
diff --git a/pym/portage/dep/soname/parse.py b/pym/portage/dep/soname/parse.py
new file mode 100644
index 0000000..3f37572
--- /dev/null
+++ b/pym/portage/dep/soname/parse.py
@@ -0,0 +1,47 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from __future__ import unicode_literals
+
+from portage.exception import InvalidData
+from portage.localization import _
+from portage.dep.soname.SonameAtom import SonameAtom
+
+_error_empty_category = _("Multilib category empty: %s")
+_error_missing_category = _("Multilib category missing: %s")
+_error_duplicate_category = _("Multilib category occurs"
+	" more than once: %s")
+
+def parse_soname_deps(s):
+	"""
+	Parse a REQUIRES or PROVIDES dependency string, and raise
+	InvalidData if necessary.
+
+	@param s: REQUIRES or PROVIDES string
+	@type s: str
+	@rtype: iter
+	@return: An iterator of SonameAtom instances
+	"""
+
+	categories = set()
+	category = None
+	previous_soname = None
+	for soname in s.split():
+		if soname.endswith(":"):
+			if category is not None and previous_soname is None:
+					raise InvalidData(_error_empty_category % category)
+
+			category = soname[:-1]
+			previous_soname = None
+			if category in categories:
+				raise InvalidData(_error_duplicate_category % category)
+			categories.add(category)
+
+		elif category is None:
+			raise InvalidData(_error_missing_category % soname)
+		else:
+			previous_soname = soname
+			yield SonameAtom(category, soname)
+
+	if category is not None and previous_soname is None:
+		raise InvalidData(_error_empty_category % category)
diff --git a/pym/portage/package/ebuild/config.py b/pym/portage/package/ebuild/config.py
index e119498..71fe4df 100644
--- a/pym/portage/package/ebuild/config.py
+++ b/pym/portage/package/ebuild/config.py
@@ -22,6 +22,7 @@ from _emerge.Package import Package
 import portage
 portage.proxy.lazyimport.lazyimport(globals(),
 	'portage.data:portage_gid',
+	'portage.dep.soname.SonameAtom:SonameAtom',
 	'portage.dbapi.vartree:vartree',
 	'portage.package.ebuild.doebuild:_phase_func_map',
 )
@@ -230,6 +231,7 @@ class config(object):
 		self._features_overrides = []
 		self._make_defaults = None
 		self._parent_stable = None
+		self._soname_provided = None
 
 		# _unknown_features records unknown features that
 		# have triggered warning messages, and ensures that
@@ -266,6 +268,7 @@ class config(object):
 			self.make_defaults_use = clone.make_defaults_use
 			self.mycpv = clone.mycpv
 			self._setcpv_args_hash = clone._setcpv_args_hash
+			self._soname_provided = clone._soname_provided
 
 			# immutable attributes (internal policy ensures lack of mutation)
 			self._locations_manager = clone._locations_manager
@@ -1049,6 +1052,16 @@ class config(object):
 	def punmaskdict(self):
 		return self._mask_manager._punmaskdict.copy()
 
+	@property
+	def soname_provided(self):
+		if self._soname_provided is None:
+			d = stack_dictlist((grabdict(
+				os.path.join(x, "soname.provided"), recursive=True)
+				for x in self.profiles), incremental=True)
+			self._soname_provided = frozenset(SonameAtom(cat, soname)
+				for cat, sonames in d.items() for soname in sonames)
+		return self._soname_provided
+
 	def expandLicenseTokens(self, tokens):
 		""" Take a token from ACCEPT_LICENSE or package.license and expand it
 		if it's a group token (indicated by @) or just return it if it's not a
diff --git a/pym/portage/tests/resolver/ResolverPlayground.py b/pym/portage/tests/resolver/ResolverPlayground.py
index b5c0446..84ad17c 100644
--- a/pym/portage/tests/resolver/ResolverPlayground.py
+++ b/pym/portage/tests/resolver/ResolverPlayground.py
@@ -40,6 +40,7 @@ class ResolverPlayground(object):
 	config_files = frozenset(("eapi", "layout.conf", "make.conf", "package.accept_keywords",
 		"package.keywords", "package.license", "package.mask", "package.properties",
 		"package.unmask", "package.use", "package.use.aliases", "package.use.stable.mask",
+		"soname.provided",
 		"unpack_dependencies", "use.aliases", "use.force", "use.mask", "layout.conf"))
 
 	metadata_xml_template = """<?xml version="1.0" encoding="UTF-8"?>
@@ -254,6 +255,8 @@ class ResolverPlayground(object):
 			unknown_keys.discard("COUNTER")
 			unknown_keys.discard("repository")
 			unknown_keys.discard("USE")
+			unknown_keys.discard("PROVIDES")
+			unknown_keys.discard("REQUIRES")
 			if unknown_keys:
 				raise ValueError("metadata of installed '%s' contains unknown keys: %s" %
 					(cpv, sorted(unknown_keys)))
diff --git a/pym/portage/tests/resolver/soname/__init__.py b/pym/portage/tests/resolver/soname/__init__.py
new file mode 100644
index 0000000..4725d33
--- /dev/null
+++ b/pym/portage/tests/resolver/soname/__init__.py
@@ -0,0 +1,2 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
diff --git a/pym/portage/tests/resolver/soname/__test__.py b/pym/portage/tests/resolver/soname/__test__.py
new file mode 100644
index 0000000..4725d33
--- /dev/null
+++ b/pym/portage/tests/resolver/soname/__test__.py
@@ -0,0 +1,2 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
diff --git a/pym/portage/tests/resolver/soname/test_autounmask.py b/pym/portage/tests/resolver/soname/test_autounmask.py
new file mode 100644
index 0000000..be0f94e
--- /dev/null
+++ b/pym/portage/tests/resolver/soname/test_autounmask.py
@@ -0,0 +1,103 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (
+	ResolverPlayground, ResolverPlaygroundTestCase)
+
+class SonameAutoUnmaskTestCase(TestCase):
+
+	def testSonameAutoUnmask(self):
+
+		binpkgs = {
+			"dev-libs/icu-49" : {
+				"KEYWORDS": "x86",
+				"PROVIDES": "x86_32: libicu.so.49",
+			},
+			"dev-libs/icu-4.8" : {
+				"KEYWORDS": "x86",
+				"PROVIDES": "x86_32: libicu.so.48",
+			},
+			"dev-libs/libxml2-2.7.8" : {
+				"KEYWORDS": "~x86",
+				"DEPEND":  "dev-libs/icu",
+				"RDEPEND": "dev-libs/icu",
+				"REQUIRES": "x86_32: libicu.so.49",
+			},
+		}
+
+		installed = {
+			"dev-libs/icu-4.8" : {
+				"KEYWORDS": "x86",
+				"PROVIDES": "x86_32: libicu.so.48",
+			},
+			"dev-libs/libxml2-2.7.8" : {
+				"KEYWORDS": "~x86",
+				"DEPEND":  "dev-libs/icu",
+				"RDEPEND": "dev-libs/icu",
+				"REQUIRES": "x86_32: libicu.so.48",
+			},
+		}
+
+		world = ["dev-libs/libxml2"]
+
+		test_cases = (
+
+			ResolverPlaygroundTestCase(
+				["dev-libs/icu"],
+				options = {
+					"--autounmask": True,
+					"--ignore-soname-deps": "n",
+					"--oneshot": True,
+					"--usepkgonly": True,
+				},
+				success = False,
+				mergelist = [
+					"[binary]dev-libs/icu-49",
+					"[binary]dev-libs/libxml2-2.7.8"
+				],
+				unstable_keywords = ['dev-libs/libxml2-2.7.8'],
+			),
+
+			ResolverPlaygroundTestCase(
+				["dev-libs/icu"],
+				options = {
+					"--autounmask": True,
+					"--ignore-soname-deps": "y",
+					"--oneshot": True,
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = [
+					"[binary]dev-libs/icu-49"
+				]
+			),
+
+			# Test that dev-libs/icu-49 update is skipped due to
+			# dev-libs/libxml2-2.7.8 being masked by KEYWORDS. Note
+			# that this result is questionable, since the installed
+			# dev-libs/libxml2-2.7.8 instance is also masked!
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--autounmask": True,
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = [],
+			),
+
+		)
+
+		playground = ResolverPlayground(binpkgs=binpkgs,
+			installed=installed, world=world, debug=False)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success, True, test_case.fail_msg)
+		finally:
+			playground.debug = False
+			playground.cleanup()
diff --git a/pym/portage/tests/resolver/soname/test_depclean.py b/pym/portage/tests/resolver/soname/test_depclean.py
new file mode 100644
index 0000000..50cc169
--- /dev/null
+++ b/pym/portage/tests/resolver/soname/test_depclean.py
@@ -0,0 +1,61 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (ResolverPlayground,
+	ResolverPlaygroundTestCase)
+
+class SonameDepcleanTestCase(TestCase):
+
+	def testSonameDepclean(self):
+
+		installed = {
+			"app-misc/A-1" : {
+				"RDEPEND": "dev-libs/B",
+				"DEPEND": "dev-libs/B",
+				"REQUIRES": "x86_32: libB.so.1 libc.so.6",
+			},
+			"dev-libs/B-1" : {
+				"PROVIDES": "x86_32: libB.so.1",
+			},
+			"sys-libs/glibc-2.19-r1" : {
+				"PROVIDES": "x86_32: libc.so.6"
+			},
+		}
+
+		world = ("app-misc/A",)
+
+		test_cases = (
+
+			ResolverPlaygroundTestCase(
+				[],
+				options={
+					"--depclean": True,
+					"--ignore-soname-deps": "n",
+				},
+				success=True,
+				cleanlist=[]
+			),
+
+			ResolverPlaygroundTestCase(
+				[],
+				options={
+					"--depclean": True,
+					"--ignore-soname-deps": "y",
+				},
+				success=True,
+				cleanlist=["sys-libs/glibc-2.19-r1"]
+			),
+		)
+
+		playground = ResolverPlayground(debug=False,
+			installed=installed, world=world)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success, True,
+					test_case.fail_msg)
+		finally:
+			# Disable debug so that cleanup works.
+			playground.debug = False
+			playground.cleanup()
diff --git a/pym/portage/tests/resolver/soname/test_downgrade.py b/pym/portage/tests/resolver/soname/test_downgrade.py
new file mode 100644
index 0000000..a95be34
--- /dev/null
+++ b/pym/portage/tests/resolver/soname/test_downgrade.py
@@ -0,0 +1,240 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (ResolverPlayground,
+	ResolverPlaygroundTestCase)
+
+class SonameDowngradeTestCase(TestCase):
+
+	def testSingleSlot(self):
+
+		ebuilds = {
+			"dev-libs/icu-49" : {
+			},
+			"dev-libs/icu-4.8" : {
+			},
+			"dev-libs/libxml2-2.7.8" : {
+				"DEPEND": "dev-libs/icu",
+				"RDEPEND": "dev-libs/icu",
+			},
+		}
+
+		binpkgs = {
+			"dev-libs/icu-49" : {
+				"PROVIDES": "x86_32: libicu.so.49",
+			},
+			"dev-libs/icu-4.8" : {
+				"PROVIDES": "x86_32: libicu.so.48",
+			},
+			"dev-libs/libxml2-2.7.8" : {
+				"DEPEND": "dev-libs/icu",
+				"RDEPEND": "dev-libs/icu",
+				"REQUIRES": "x86_32: libicu.so.48",
+			},
+		}
+		installed = {
+			"dev-libs/icu-49" : {
+				"PROVIDES": "x86_32: libicu.so.49",
+			},
+			"dev-libs/libxml2-2.7.8" : {
+				"DEPEND": "dev-libs/icu",
+				"RDEPEND": "dev-libs/icu",
+				"REQUIRES": "x86_32: libicu.so.49",
+			},
+		}
+
+		user_config = {
+			"package.mask" : (
+				">=dev-libs/icu-49",
+			),
+		}
+
+		world = ["dev-libs/libxml2"]
+
+		test_cases = (
+
+			ResolverPlaygroundTestCase(
+				["dev-libs/icu"],
+				options = {
+					"--autounmask": "n",
+					"--ignore-soname-deps": "n",
+					"--oneshot": True,
+					"--usepkgonly": True
+				},
+				success = True,
+				mergelist = [
+					"[binary]dev-libs/icu-4.8",
+					"[binary]dev-libs/libxml2-2.7.8"
+				]
+			),
+
+			ResolverPlaygroundTestCase(
+				["dev-libs/icu"],
+				options = {
+					"--autounmask": "n",
+					"--ignore-soname-deps": "y",
+					"--oneshot": True,
+					"--usepkgonly": True
+				},
+				success = True,
+				mergelist = [
+					"[binary]dev-libs/icu-4.8",
+				]
+			),
+
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--autounmask": "n",
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = [
+					"[binary]dev-libs/icu-4.8",
+					"[binary]dev-libs/libxml2-2.7.8"
+				]
+			),
+
+			# In this case, soname dependencies are not respected,
+			# because --usepkgonly is not enabled. This could be
+			# handled differently, by respecting soname dependencies
+			# as long as no unbuilt ebuilds get pulled into the graph.
+			# However, that kind of conditional dependency accounting
+			# would add a significant amount of complexity.
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkg": True,
+				},
+				success = True,
+				mergelist = [
+					"[binary]dev-libs/icu-4.8",
+				]
+			),
+
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--deep": True,
+					"--update": True,
+				},
+				success = True,
+				mergelist = [
+					"dev-libs/icu-4.8",
+				]
+			),
+		)
+
+		playground = ResolverPlayground(binpkgs=binpkgs,
+			ebuilds=ebuilds, installed=installed,
+			user_config=user_config, world=world, debug=False)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success, True, test_case.fail_msg)
+		finally:
+			# Disable debug so that cleanup works.
+			playground.debug = False
+			playground.cleanup()
+
+	def testTwoSlots(self):
+
+		ebuilds = {
+			"dev-libs/glib-1.2.10" : {
+				"SLOT": "1"
+			},
+			"dev-libs/glib-2.30.2" : {
+				"SLOT": "2"
+			},
+			"dev-libs/dbus-glib-0.98" : {
+				"EAPI": "1",
+				"DEPEND":  "dev-libs/glib:2",
+				"RDEPEND": "dev-libs/glib:2"
+			},
+		}
+		binpkgs = {
+			"dev-libs/glib-1.2.10" : {
+				"SLOT": "1",
+				"PROVIDES": "x86_32: libglib-1.0.so.0",
+			},
+			"dev-libs/glib-2.30.2" : {
+				"PROVIDES": "x86_32: libglib-2.0.so.30",
+				"SLOT": "2",
+			},
+			"dev-libs/glib-2.32.3" : {
+				"PROVIDES": "x86_32: libglib-2.0.so.32",
+				"SLOT": "2",
+			},
+			"dev-libs/dbus-glib-0.98" : {
+				"EAPI": "1",
+				"DEPEND":  "dev-libs/glib:2",
+				"RDEPEND": "dev-libs/glib:2",
+				"REQUIRES": "x86_32: libglib-2.0.so.30",
+			},
+		}
+		installed = {
+			"dev-libs/glib-1.2.10" : {
+				"PROVIDES": "x86_32: libglib-1.0.so.0",
+				"SLOT": "1",
+			},
+			"dev-libs/glib-2.32.3" : {
+				"PROVIDES": "x86_32: libglib-2.0.so.32",
+				"SLOT": "2",
+			},
+			"dev-libs/dbus-glib-0.98" : {
+				"EAPI": "1",
+				"DEPEND":  "dev-libs/glib:2",
+				"RDEPEND": "dev-libs/glib:2",
+				"REQUIRES": "x86_32: libglib-2.0.so.32",
+			},
+		}
+
+		user_config = {
+			"package.mask" : (
+				">=dev-libs/glib-2.32",
+			),
+		}
+
+		world = [
+			"dev-libs/glib:1",
+			"dev-libs/dbus-glib",
+		]
+
+		test_cases = (
+
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--autounmask": "n",
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = [
+					"[binary]dev-libs/glib-2.30.2",
+					"[binary]dev-libs/dbus-glib-0.98"
+				]
+			),
+
+		)
+
+		playground = ResolverPlayground(ebuilds=ebuilds, binpkgs=binpkgs,
+			installed=installed, user_config=user_config, world=world,
+			debug=False)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success, True, test_case.fail_msg)
+		finally:
+			# Disable debug so that cleanup works.
+			playground.debug = False
+			playground.cleanup()
diff --git a/pym/portage/tests/resolver/soname/test_or_choices.py b/pym/portage/tests/resolver/soname/test_or_choices.py
new file mode 100644
index 0000000..2420cd3
--- /dev/null
+++ b/pym/portage/tests/resolver/soname/test_or_choices.py
@@ -0,0 +1,92 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (ResolverPlayground,
+	ResolverPlaygroundTestCase)
+
+class SonameOrChoicesTestCase(TestCase):
+
+	def testSonameConflictMissedUpdate(self):
+
+		binpkgs = {
+			"dev-lang/ocaml-4.02.1" : {
+				"EAPI": "5",
+				"PROVIDES": "x86_32: libocaml-4.02.1.so",
+			},
+
+			"dev-lang/ocaml-4.01.0" : {
+				"EAPI": "5",
+				"PROVIDES": "x86_32: libocaml-4.01.0.so",
+			},
+
+			"dev-ml/lablgl-1.05" : {
+				"DEPEND": (">=dev-lang/ocaml-3.10.2 "
+					"|| ( dev-ml/labltk <dev-lang/ocaml-4.02 )"),
+				"RDEPEND": (">=dev-lang/ocaml-3.10.2 "
+					"|| ( dev-ml/labltk <dev-lang/ocaml-4.02 )"),
+				"REQUIRES": "x86_32: libocaml-4.02.1.so",
+			},
+
+			"dev-ml/labltk-8.06.0" : {
+				"EAPI": "5",
+				"SLOT": "0/8.06.0",
+				"DEPEND": ">=dev-lang/ocaml-4.02",
+				"RDEPEND": ">=dev-lang/ocaml-4.02",
+				"REQUIRES": "x86_32: libocaml-4.02.1.so",
+			},
+		}
+
+		installed = {
+			"dev-lang/ocaml-4.01.0" : {
+				"EAPI": "5",
+				"PROVIDES": "x86_32: libocaml-4.01.0.so",
+			},
+
+			"dev-ml/lablgl-1.05" : {
+				"DEPEND": (">=dev-lang/ocaml-3.10.2 "
+					"|| ( dev-ml/labltk <dev-lang/ocaml-4.02 )"),
+				"RDEPEND": (">=dev-lang/ocaml-3.10.2 "
+					"|| ( dev-ml/labltk <dev-lang/ocaml-4.02 )"),
+				"REQUIRES": "x86_32: libocaml-4.01.0.so",
+			},
+		}
+
+		world = (
+			"dev-lang/ocaml",
+			"dev-ml/lablgl",
+		)
+
+		test_cases = (
+
+			# bug #531656: If an ocaml update is desirable,
+			# then we need to pull in dev-ml/labltk.
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkgonly": True
+				},
+				success = True,
+				mergelist = [
+					"[binary]dev-lang/ocaml-4.02.1",
+					"[binary]dev-ml/labltk-8.06.0",
+					"[binary]dev-ml/lablgl-1.05",
+				]
+			),
+
+		)
+
+		playground = ResolverPlayground(debug=False,
+			binpkgs=binpkgs, installed=installed, world=world)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success, True,
+					test_case.fail_msg)
+		finally:
+			# Disable debug so that cleanup works.
+			playground.debug = False
+			playground.cleanup()
diff --git a/pym/portage/tests/resolver/soname/test_reinstall.py b/pym/portage/tests/resolver/soname/test_reinstall.py
new file mode 100644
index 0000000..b8f2d2c
--- /dev/null
+++ b/pym/portage/tests/resolver/soname/test_reinstall.py
@@ -0,0 +1,87 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (ResolverPlayground,
+	ResolverPlaygroundTestCase)
+
+class SonameReinstallTestCase(TestCase):
+
+	def testSonameReinstall(self):
+
+		binpkgs = {
+			"app-misc/A-1" : {
+				"RDEPEND": "dev-libs/B",
+				"DEPEND": "dev-libs/B",
+				"REQUIRES": "x86_32: libB.so.2",
+			},
+			"dev-libs/B-2" : {
+				"PROVIDES": "x86_32: libB.so.2",
+			},
+			"dev-libs/B-1" : {
+				"PROVIDES": "x86_32: libB.so.1",
+			},
+		}
+
+		installed = {
+			"app-misc/A-1" : {
+				"RDEPEND": "dev-libs/B",
+				"DEPEND": "dev-libs/B",
+				"REQUIRES": "x86_32: libB.so.1",
+			},
+			"dev-libs/B-1" : {
+				"PROVIDES": "x86_32: libB.so.1",
+			},
+		}
+
+		world = ("app-misc/A",)
+
+		test_cases = (
+
+			# Test that --ignore-soname-deps prevents the above
+			# rebuild from being triggered.
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkgonly": True
+				},
+				success = True,
+				mergelist = [
+					"[binary]dev-libs/B-2",
+					"[binary]app-misc/A-1",
+				]
+			),
+
+			# Test that --ignore-soname-deps prevents the above
+			# reinstall from being triggered.
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--deep": True,
+					"--ignore-soname-deps": "y",
+					"--update": True,
+					"--usepkgonly": True
+				},
+				success = True,
+				mergelist = [
+					"[binary]dev-libs/B-2",
+				]
+			),
+
+		)
+
+		playground = ResolverPlayground(debug=False,
+			binpkgs=binpkgs, installed=installed,
+			world=world)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success, True,
+					test_case.fail_msg)
+		finally:
+			# Disable debug so that cleanup works.
+			playground.debug = False
+			playground.cleanup()
diff --git a/pym/portage/tests/resolver/soname/test_skip_update.py b/pym/portage/tests/resolver/soname/test_skip_update.py
new file mode 100644
index 0000000..67e1e02
--- /dev/null
+++ b/pym/portage/tests/resolver/soname/test_skip_update.py
@@ -0,0 +1,86 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (ResolverPlayground,
+	ResolverPlaygroundTestCase)
+
+class SonameSkipUpdateTestCase(TestCase):
+
+	def testSonameSkipUpdate(self):
+
+		binpkgs = {
+			"app-misc/A-1" : {
+				"RDEPEND": "dev-libs/B",
+				"DEPEND": "dev-libs/B",
+				"REQUIRES": "x86_32: libB.so.1",
+			},
+			"dev-libs/B-2" : {
+				"PROVIDES": "x86_32: libB.so.2",
+			},
+			"dev-libs/B-1" : {
+				"PROVIDES": "x86_32: libB.so.1",
+			},
+		}
+
+		installed = {
+			"app-misc/A-1" : {
+				"RDEPEND": "dev-libs/B",
+				"DEPEND": "dev-libs/B",
+				"REQUIRES": "x86_32: libB.so.1",
+			},
+			"dev-libs/B-1" : {
+				"PROVIDES": "x86_32: libB.so.1",
+			},
+		}
+
+		world = ("app-misc/A",)
+
+		test_cases = (
+
+			# Test that --ignore-soname-deps allows the upgrade,
+			# even though it will break an soname dependency of
+			# app-misc/A-1.
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--deep": True,
+					"--ignore-soname-deps": "y",
+					"--update": True,
+					"--usepkgonly": True
+				},
+				success = True,
+				mergelist = [
+					"[binary]dev-libs/B-2",
+				]
+			),
+
+			# Test that upgrade to B-2 is skipped with --usepkgonly
+			# because it will break an soname dependency that
+			# cannot be satisfied by the available binary packages.
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkgonly": True
+				},
+				success = True,
+				mergelist = []
+			),
+
+		)
+
+		playground = ResolverPlayground(debug=False,
+			binpkgs=binpkgs, installed=installed,
+			world=world)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success, True,
+					test_case.fail_msg)
+		finally:
+			# Disable debug so that cleanup works.
+			playground.debug = False
+			playground.cleanup()
diff --git a/pym/portage/tests/resolver/soname/test_slot_conflict_reinstall.py b/pym/portage/tests/resolver/soname/test_slot_conflict_reinstall.py
new file mode 100644
index 0000000..40e6995
--- /dev/null
+++ b/pym/portage/tests/resolver/soname/test_slot_conflict_reinstall.py
@@ -0,0 +1,342 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (
+	ResolverPlayground, ResolverPlaygroundTestCase)
+
+class SonameSlotConflictReinstallTestCase(TestCase):
+
+	def testSonameSlotConflictReinstall(self):
+
+		binpkgs = {
+
+			"app-misc/A-1" : {
+				"PROVIDES": "x86_32: libA-1.so",
+			},
+
+			"app-misc/A-2" : {
+				"PROVIDES": "x86_32: libA-2.so",
+			},
+
+			"app-misc/B-0" : {
+				"DEPEND": "app-misc/A",
+				"RDEPEND": "app-misc/A",
+				"REQUIRES": "x86_32: libA-2.so",
+			},
+
+			"app-misc/C-0" : {
+				"EAPI": "5",
+				"DEPEND": "<app-misc/A-2",
+				"RDEPEND": "<app-misc/A-2"
+			},
+
+			"app-misc/D-1" : {
+				"PROVIDES": "x86_32: libD-1.so",
+			},
+
+			"app-misc/D-2" : {
+				"PROVIDES": "x86_32: libD-2.so",
+			},
+
+			"app-misc/E-0" : {
+				"DEPEND": "app-misc/D",
+				"RDEPEND": "app-misc/D",
+				"REQUIRES": "x86_32: libD-2.so",
+			},
+
+		}
+
+		installed = {
+
+			"app-misc/A-1" : {
+				"PROVIDES": "x86_32: libA-1.so",
+			},
+
+			"app-misc/B-0" : {
+				"DEPEND": "app-misc/A",
+				"RDEPEND": "app-misc/A",
+				"REQUIRES": "x86_32: libA-1.so",
+			},
+
+			"app-misc/C-0" : {
+				"DEPEND": "<app-misc/A-2",
+				"RDEPEND": "<app-misc/A-2"
+			},
+
+			"app-misc/D-1" : {
+				"PROVIDES": "x86_32: libD-1.so",
+			},
+
+			"app-misc/E-0" : {
+				"DEPEND": "app-misc/D",
+				"RDEPEND": "app-misc/D",
+				"REQUIRES": "x86_32: libD-1.so",
+			},
+
+		}
+
+		world = ["app-misc/B", "app-misc/C", "app-misc/E"]
+
+		test_cases = (
+
+			# Test bug #439688, where a slot conflict prevents an
+			# upgrade and we don't want to trigger unnecessary rebuilds.
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = [
+					"[binary]app-misc/D-2",
+					"[binary]app-misc/E-0"
+				]
+			),
+
+		)
+
+		playground = ResolverPlayground(binpkgs=binpkgs,
+			installed=installed, world=world, debug=False)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success,
+					True, test_case.fail_msg)
+		finally:
+			playground.debug = False
+			playground.cleanup()
+
+	def testSonameSlotConflictMassRebuild(self):
+		"""
+		Bug 486580
+		Before this bug was fixed, emerge would backtrack for each
+		package that needs a rebuild. This could cause it to hit the
+		backtrack limit and not rebuild all needed packages.
+		"""
+		binpkgs = {
+
+			"app-misc/A-1" : {
+				"DEPEND": "app-misc/B",
+				"RDEPEND": "app-misc/B",
+				"REQUIRES": "x86_32: libB-2.so",
+			},
+
+			"app-misc/B-1" : {
+				"SLOT": "1",
+				"PROVIDES": "x86_32: libB-1.so",
+			},
+
+			"app-misc/B-2" : {
+				"SLOT": "2",
+				"PROVIDES": "x86_32: libB-2.so",
+			},
+		}
+
+		installed = {
+			"app-misc/B-1" : {
+				"SLOT": "1",
+				"PROVIDES": "x86_32: libB-1.so",
+			},
+		}
+
+		expected_mergelist = [
+			'[binary]app-misc/A-1',
+			'[binary]app-misc/B-2'
+		]
+
+		for i in range(5):
+			binpkgs["app-misc/C%sC-1" % i] = {
+				"DEPEND": "app-misc/B",
+				"RDEPEND": "app-misc/B",
+				"REQUIRES": "x86_32: libB-2.so",
+			}
+
+			installed["app-misc/C%sC-1" % i] = {
+				"DEPEND": "app-misc/B",
+				"RDEPEND": "app-misc/B",
+				"REQUIRES": "x86_32: libB-1.so",
+			}
+			for x in ("DEPEND", "RDEPEND"):
+				binpkgs["app-misc/A-1"][x] += " app-misc/C%sC" % i
+
+			expected_mergelist.append("[binary]app-misc/C%sC-1" % i)
+
+
+		test_cases = (
+			ResolverPlaygroundTestCase(
+				["app-misc/A"],
+				ignore_mergelist_order=True,
+				all_permutations=True,
+				options = {
+					"--backtrack": 3,
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = expected_mergelist),
+		)
+
+		world = []
+
+		playground = ResolverPlayground(binpkgs=binpkgs,
+			installed=installed, world=world, debug=False)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success,
+					True, test_case.fail_msg)
+		finally:
+			playground.debug = False
+			playground.cleanup()
+
+	def testSonameSlotConflictForgottenChild(self):
+		"""
+		Similar to testSonameSlotConflictMassRebuild above, but this
+		time the rebuilds are scheduled, but the package causing the
+		rebuild (the child) is not installed.
+		"""
+		binpkgs = {
+
+			"app-misc/A-2" : {
+				"DEPEND": "app-misc/B app-misc/C",
+				"RDEPEND": "app-misc/B app-misc/C",
+				"REQUIRES": "x86_32: libB-2.so",
+			},
+
+			"app-misc/B-2" : {
+				"PROVIDES": "x86_32: libB-2.so",
+				"SLOT": "2",
+			},
+
+			"app-misc/C-1": {
+				"DEPEND": "app-misc/B",
+				"RDEPEND": "app-misc/B",
+				"REQUIRES": "x86_32: libB-2.so",
+			},
+		}
+
+		installed = {
+			"app-misc/A-1" : {
+				"DEPEND": "app-misc/B app-misc/C",
+				"RDEPEND": "app-misc/B app-misc/C",
+				"REQUIRES": "x86_32: libB-1.so",
+			},
+
+			"app-misc/B-1" : {
+				"PROVIDES": "x86_32: libB-1.so",
+				"SLOT": "1",
+			},
+
+			"app-misc/C-1": {
+				"DEPEND": "app-misc/B",
+				"RDEPEND": "app-misc/B",
+				"REQUIRES": "x86_32: libB-1.so",
+			},
+		}
+
+		test_cases = (
+			ResolverPlaygroundTestCase(
+				["app-misc/A"],
+				options = {
+					"--ignore-soname-deps": "n",
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = [
+					'[binary]app-misc/B-2',
+					'[binary]app-misc/C-1',
+					'[binary]app-misc/A-2',
+				]
+			),
+		)
+
+		world = []
+
+		playground = ResolverPlayground(binpkgs=binpkgs,
+			installed=installed, world=world, debug=False)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success, True, test_case.fail_msg)
+		finally:
+			playground.debug = False
+			playground.cleanup()
+
+	def testSonameSlotConflictMixedDependencies(self):
+		"""
+		Bug 487198
+		For parents with mixed >= and < dependencies, we scheduled
+		reinstalls for the >= atom, but in the end didn't install the
+		child update because of the < atom.
+		"""
+		binpkgs = {
+			"cat/slotted-lib-1" : {
+				"PROVIDES": "x86_32: lib1.so",
+				"SLOT": "1",
+			},
+			"cat/slotted-lib-2" : {
+				"PROVIDES": "x86_32: lib2.so",
+				"SLOT": "2",
+			},
+			"cat/slotted-lib-3" : {
+				"PROVIDES": "x86_32: lib3.so",
+				"SLOT": "3",
+			},
+			"cat/slotted-lib-4" : {
+				"PROVIDES": "x86_32: lib4.so",
+				"SLOT": "4",
+			},
+			"cat/slotted-lib-5" : {
+				"PROVIDES": "x86_32: lib5.so",
+				"SLOT": "5",
+			},
+			"cat/user-1" : {
+				"DEPEND": ">=cat/slotted-lib-2 <cat/slotted-lib-4",
+				"RDEPEND": ">=cat/slotted-lib-2 <cat/slotted-lib-4",
+				"REQUIRES": "x86_32: lib3.so",
+			},
+		}
+
+		installed = {
+			"cat/slotted-lib-3" : {
+				"PROVIDES": "x86_32: lib3.so",
+				"SLOT": "3",
+			},
+			"cat/user-1" : {
+				"DEPEND": ">=cat/slotted-lib-2 <cat/slotted-lib-4",
+				"RDEPEND": ">=cat/slotted-lib-2 <cat/slotted-lib-4",
+				"REQUIRES": "x86_32: lib3.so",
+			},
+		}
+
+		test_cases = (
+			ResolverPlaygroundTestCase(
+				["cat/user"],
+				options = {
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = []),
+		)
+
+		world = []
+
+		playground = ResolverPlayground(binpkgs=binpkgs,
+			installed=installed, world=world, debug=False)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success,
+					True, test_case.fail_msg)
+		finally:
+			playground.debug = False
+			playground.cleanup()
diff --git a/pym/portage/tests/resolver/soname/test_slot_conflict_update.py b/pym/portage/tests/resolver/soname/test_slot_conflict_update.py
new file mode 100644
index 0000000..c607496
--- /dev/null
+++ b/pym/portage/tests/resolver/soname/test_slot_conflict_update.py
@@ -0,0 +1,117 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (
+	ResolverPlayground, ResolverPlaygroundTestCase)
+
+class SonameSlotConflictUpdateTestCase(TestCase):
+
+	def testSonameSlotConflictUpdate(self):
+
+		binpkgs = {
+
+			"app-text/podofo-0.9.2" : {
+				"RDEPEND" : "dev-util/boost-build",
+			},
+
+			"dev-cpp/libcmis-0.3.1" : {
+				"DEPEND": "dev-libs/boost",
+				"RDEPEND": "dev-libs/boost",
+				"REQUIRES": "x86_32: libboost-1.53.so",
+			},
+
+			"dev-libs/boost-1.53.0" : {
+				"PROVIDES": "x86_32: libboost-1.53.so",
+				"RDEPEND" : "=dev-util/boost-build-1.53.0",
+			},
+
+			"dev-libs/boost-1.52.0" : {
+				"PROVIDES": "x86_32: libboost-1.52.so",
+				"RDEPEND" : "=dev-util/boost-build-1.52.0",
+			},
+
+			"dev-util/boost-build-1.53.0" : {
+			},
+
+			"dev-util/boost-build-1.52.0" : {
+			},
+
+
+		}
+
+		installed = {
+
+			"app-text/podofo-0.9.2" : {
+				"RDEPEND" : "dev-util/boost-build",
+			},
+
+			"dev-cpp/libcmis-0.3.1" : {
+				"DEPEND": "dev-libs/boost",
+				"RDEPEND": "dev-libs/boost",
+				"REQUIRES": "x86_32: libboost-1.52.so",
+			},
+
+			"dev-util/boost-build-1.52.0" : {
+			},
+
+			"dev-libs/boost-1.52.0" : {
+				"PROVIDES": "x86_32: libboost-1.52.so",
+				"RDEPEND" : "=dev-util/boost-build-1.52.0",
+			},
+
+		}
+
+		world = [
+			"dev-cpp/libcmis",
+			"dev-libs/boost",
+			"app-text/podofo",
+		]
+
+		test_cases = (
+
+			ResolverPlaygroundTestCase(
+				world,
+				all_permutations = True,
+				options = {
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = [
+					'[binary]dev-util/boost-build-1.53.0',
+					'[binary]dev-libs/boost-1.53.0',
+					'[binary]dev-cpp/libcmis-0.3.1'
+				]
+			),
+
+			ResolverPlaygroundTestCase(
+				world,
+				all_permutations = True,
+				options = {
+					"--deep": True,
+					"--ignore-soname-deps": "y",
+					"--update": True,
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = [
+					'[binary]dev-util/boost-build-1.53.0',
+					'[binary]dev-libs/boost-1.53.0',
+				]
+			),
+
+		)
+
+		playground = ResolverPlayground(binpkgs=binpkgs,
+			installed=installed, world=world, debug=False)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success,
+					True, test_case.fail_msg)
+		finally:
+			playground.debug = False
+			playground.cleanup()
diff --git a/pym/portage/tests/resolver/soname/test_soname_provided.py b/pym/portage/tests/resolver/soname/test_soname_provided.py
new file mode 100644
index 0000000..162da47
--- /dev/null
+++ b/pym/portage/tests/resolver/soname/test_soname_provided.py
@@ -0,0 +1,78 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (
+	ResolverPlayground, ResolverPlaygroundTestCase)
+
+class SonameProvidedTestCase(TestCase):
+
+	def testSonameProvided(self):
+
+		binpkgs = {
+			"app-misc/A-1" : {
+				"EAPI": "5",
+				"PROVIDES": "x86_32: libA.so.1",
+			},
+			"app-misc/B-1" : {
+				"DEPEND": "app-misc/A",
+				"RDEPEND": "app-misc/A",
+				"REQUIRES": "x86_32: libA.so.2",
+			},
+			"app-misc/B-0" : {
+				"DEPEND": "app-misc/A",
+				"RDEPEND": "app-misc/A",
+				"REQUIRES": "x86_32: libA.so.1",
+			},
+		}
+
+		installed = {
+			"app-misc/A-1" : {
+				"EAPI": "5",
+				"PROVIDES": "x86_32: libA.so.1",
+			},
+
+			"app-misc/B-0" : {
+				"DEPEND": "app-misc/A",
+				"RDEPEND": "app-misc/A",
+				"REQUIRES": "x86_32: libA.so.1",
+			},
+		}
+
+		world = ["app-misc/B"]
+
+		profile = {
+			"soname.provided": (
+				"x86_32 libA.so.2",
+			),
+		}
+
+		test_cases = (
+
+			# Allow update due to soname dependency satisfied by
+			# soname.provided.
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = ["[binary]app-misc/B-1"],
+			),
+
+		)
+
+		playground = ResolverPlayground(binpkgs=binpkgs, debug=False,
+			profile=profile, installed=installed, world=world)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(
+					test_case.test_success, True, test_case.fail_msg)
+		finally:
+			# Disable debug so that cleanup works.
+			playground.debug = False
+			playground.cleanup()
diff --git a/pym/portage/tests/resolver/soname/test_unsatisfiable.py b/pym/portage/tests/resolver/soname/test_unsatisfiable.py
new file mode 100644
index 0000000..039a9df
--- /dev/null
+++ b/pym/portage/tests/resolver/soname/test_unsatisfiable.py
@@ -0,0 +1,71 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (
+	ResolverPlayground, ResolverPlaygroundTestCase)
+
+class SonameUnsatisfiableTestCase(TestCase):
+
+	def testSonameUnsatisfiable(self):
+
+		binpkgs = {
+			"app-misc/A-1" : {
+				"EAPI": "5",
+				"PROVIDES": "x86_32: libA.so.1",
+			},
+			"app-misc/B-1" : {
+				"DEPEND": "app-misc/A",
+				"RDEPEND": "app-misc/A",
+				"REQUIRES": "x86_32: libA.so.2",
+			},
+			"app-misc/B-0" : {
+				"DEPEND": "app-misc/A",
+				"RDEPEND": "app-misc/A",
+				"REQUIRES": "x86_32: libA.so.1",
+			},
+		}
+
+		installed = {
+			"app-misc/A-1" : {
+				"EAPI": "5",
+				"PROVIDES": "x86_32: libA.so.1",
+			},
+
+			"app-misc/B-0" : {
+				"DEPEND": "app-misc/A",
+				"RDEPEND": "app-misc/A",
+				"REQUIRES": "x86_32: libA.so.1",
+			},
+		}
+
+		world = ["app-misc/B"]
+
+		test_cases = (
+
+			# Skip update due to unsatisfied soname dependency.
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = [],
+			),
+
+		)
+
+		playground = ResolverPlayground(binpkgs=binpkgs, debug=False,
+			installed=installed, world=world)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(
+					test_case.test_success, True, test_case.fail_msg)
+		finally:
+			# Disable debug so that cleanup works.
+			playground.debug = False
+			playground.cleanup()
diff --git a/pym/portage/tests/resolver/soname/test_unsatisfied.py b/pym/portage/tests/resolver/soname/test_unsatisfied.py
new file mode 100644
index 0000000..27cdcc4
--- /dev/null
+++ b/pym/portage/tests/resolver/soname/test_unsatisfied.py
@@ -0,0 +1,87 @@
+# Copyright 2015 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (ResolverPlayground,
+	ResolverPlaygroundTestCase)
+
+class SonameUnsatisfiedTestCase(TestCase):
+
+	def testSonameUnsatisfied(self):
+
+		binpkgs = {
+			"app-misc/A-1" : {
+				"EAPI": "5",
+				"PROVIDES": "x86_32: libA.so.1",
+			},
+			"app-misc/A-2" : {
+				"EAPI": "5",
+				"PROVIDES": "x86_32: libA.so.2",
+			},
+			"app-misc/B-0" : {
+				"DEPEND": "app-misc/A",
+				"RDEPEND": "app-misc/A",
+				"REQUIRES": "x86_32: libA.so.2",
+			}
+		}
+
+		installed = {
+			"app-misc/A-2" : {
+				"EAPI": "5",
+				"PROVIDES": "x86_32: libA.so.2",
+			},
+
+			"app-misc/B-0" : {
+				"DEPEND": "app-misc/A",
+				"RDEPEND": "app-misc/A",
+				"REQUIRES": "x86_32: libA.so.1",
+			}
+		}
+
+		world = ["app-misc/B"]
+
+		test_cases = (
+
+			# Demonstrate bug #439694, where a broken
+			# soname dependency needs to trigger a reinstall.
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {
+					"--deep": True,
+					"--ignore-soname-deps": "n",
+					"--update": True,
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = [
+					"[binary]app-misc/B-0"
+				]
+			),
+
+			# This doesn't trigger a reinstall, since there's no version
+			# change to trigger complete graph mode, and initially
+			# unsatisfied deps are ignored in complete graph mode anyway.
+			ResolverPlaygroundTestCase(
+				["app-misc/A"],
+				options = {
+					"--ignore-soname-deps": "n",
+					"--oneshot": True,
+					"--usepkgonly": True,
+				},
+				success = True,
+				mergelist = [
+					"[binary]app-misc/A-2"
+				]
+			),
+		)
+
+		playground = ResolverPlayground(binpkgs=binpkgs, debug=False,
+			installed=installed, world=world)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success, True, test_case.fail_msg)
+		finally:
+			# Disable debug so that cleanup works.
+			playground.debug = False
+			playground.cleanup()
diff --git a/pym/portage/tests/resolver/test_package_tracker.py b/pym/portage/tests/resolver/test_package_tracker.py
index 8fa3513..468c3d8 100644
--- a/pym/portage/tests/resolver/test_package_tracker.py
+++ b/pym/portage/tests/resolver/test_package_tracker.py
@@ -116,11 +116,11 @@ class PackageTrackerTestCase(TestCase):
 				if pkg.root == "/" and pkg.cp == x_atom:
 					self.assertTrue(pkg in matches)
 			self.assertTrue(not dbapi.cp_list(y_atom))
-			matches = dbapi.match(x_atom)
+			matches = dbapi.match(Atom(x_atom))
 			for pkg in pkgs:
 				if pkg.root == "/" and pkg.cp == x_atom:
 					self.assertTrue(pkg in matches)
-			self.assertTrue(not dbapi.match(y_atom))
+			self.assertTrue(not dbapi.match(Atom(y_atom)))
 
 		check_dbapi([])
 
-- 
2.0.5