Add experimental EAPI 4-slot-abi support.

Refer to 4-slot-abi.docbook for a full description.

8 files changed, 410 insertions, 21 deletions

diff --git a/pym/_emerge/Dependency.py b/pym/_emerge/Dependency.py
index c2d36b2dc..2ec860f83 100644
--- a/pym/_emerge/Dependency.py
+++ b/pym/_emerge/Dependency.py
@@ -6,7 +6,7 @@ from _emerge.DepPriority import DepPriority
 
 class Dependency(SlotObject):
 	__slots__ = ("atom", "blocker", "child", "depth",
-		"parent", "onlydeps", "priority", "root",
+		"parent", "onlydeps", "priority", "root", "want_update",
 		"collapsed_parent", "collapsed_priority")
 	def __init__(self, **kwargs):
 		SlotObject.__init__(self, **kwargs)
diff --git a/pym/_emerge/FakeVartree.py b/pym/_emerge/FakeVartree.py
index e8454e8e9..e62058540 100644
--- a/pym/_emerge/FakeVartree.py
+++ b/pym/_emerge/FakeVartree.py
@@ -10,11 +10,17 @@ from _emerge.Package import Package
 from _emerge.PackageVirtualDbapi import PackageVirtualDbapi
 from portage.const import VDB_PATH
 from portage.dbapi.vartree import vartree
+from portage.dep._slot_abi import find_built_slot_abi_atoms
+from portage.eapi import _get_eapi_attrs
+from portage.exception import InvalidDependString
 from portage.repository.config import _gen_valid_repo
 from portage.update import grab_updates, parse_updates, update_dbentries
 
 if sys.hexversion >= 0x3000000:
 	long = int
+	_unicode = str
+else:
+	_unicode = unicode
 
 class FakeVardbapi(PackageVirtualDbapi):
 	"""
@@ -39,9 +45,10 @@ 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):
+		dynamic_deps=True, ignore_built_slot_abi_deps=False):
 		self._root_config = root_config
 		self._dynamic_deps = dynamic_deps
+		self._ignore_built_slot_abi_deps = ignore_built_slot_abi_deps
 		if pkg_root_config is None:
 			pkg_root_config = self._root_config
 		self._pkg_root_config = pkg_root_config
@@ -101,7 +108,18 @@ class FakeVartree(vartree):
 		self._aux_get_history.add(pkg)
 		# We need to check the EAPI, and this also raises
 		# a KeyError to the caller if appropriate.
-		installed_eapi, repo = self._aux_get(pkg, ["EAPI", "repository"])
+		pkg_obj = self.dbapi._cpv_map[pkg]
+		installed_eapi = pkg_obj.metadata['EAPI']
+		repo = pkg_obj.metadata['repository']
+		eapi_attrs = _get_eapi_attrs(installed_eapi)
+		built_slot_abi_atoms = None
+
+		if eapi_attrs.slot_abi and not self._ignore_built_slot_abi_deps:
+			try:
+				built_slot_abi_atoms = find_built_slot_abi_atoms(pkg_obj)
+			except InvalidDependString:
+				pass
+
 		try:
 			# Use the live ebuild metadata if possible.
 			repo = _gen_valid_repo(repo)
@@ -118,6 +136,16 @@ class FakeVartree(vartree):
 			if not (portage.eapi_is_supported(live_metadata["EAPI"]) and \
 				portage.eapi_is_supported(installed_eapi)):
 				raise KeyError(pkg)
+
+			# preserve built SLOT/ABI := operator deps
+			if built_slot_abi_atoms:
+				live_eapi_attrs = _get_eapi_attrs(live_metadata["EAPI"])
+				if not live_eapi_attrs.slot_abi:
+					raise KeyError(pkg)
+				for k, v in built_slot_abi_atoms.items():
+					live_metadata[k] += (" " +
+						" ".join(_unicode(atom) for atom in v))
+
 			self.dbapi.aux_update(pkg, live_metadata)
 		except (KeyError, portage.exception.PortageException):
 			if self._global_updates is None:
diff --git a/pym/_emerge/Package.py b/pym/_emerge/Package.py
index 18bc2014f..7bf7181ba 100644
--- a/pym/_emerge/Package.py
+++ b/pym/_emerge/Package.py
@@ -26,8 +26,9 @@ class Package(Task):
 		"root_config", "type_name",
 		"category", "counter", "cp", "cpv_split",
 		"inherited", "iuse", "mtime",
-		"pf", "root", "slot", "slot_atom", "version") + \
-	("_invalid", "_raw_metadata", "_masks", "_use", "_visible")
+		"pf", "root", "slot", "slot_abi", "slot_atom", "version") + \
+		("_invalid", "_raw_metadata", "_masks", "_use",
+		"_validated_atoms", "_visible")
 
 	metadata_keys = [
 		"BUILD_TIME", "CHOST", "COUNTER", "DEPEND", "EAPI",
@@ -58,6 +59,7 @@ class Package(Task):
 				"SLOT: invalid value: '%s'" % self.metadata["SLOT"])
 		self.cp = self.cpv.cp
 		self.slot = self.cpv.slot
+		self.slot_abi = self.cpv.slot_abi
 		# sync metadata with validated repo (may be UNKNOWN_REPO)
 		self.metadata['repository'] = self.cpv.repo
 		if (self.iuse.enabled or self.iuse.disabled) and \
@@ -107,6 +109,17 @@ class Package(Task):
 			self._visible = self._eval_visiblity(self.masks)
 		return self._visible
 
+	@property
+	def validated_atoms(self):
+		"""
+		Returns *all* validated atoms from the deps, regardless
+		of USE conditionals, with USE conditionals inside
+		atoms left unevaluated.
+		"""
+		if self._validated_atoms is None:
+			self._validate_deps()
+		return self._validated_atoms
+
 	@classmethod
 	def _gen_hash_key(cls, cpv=None, installed=None, onlydeps=None,
 		operation=None, repo_name=None, root_config=None,
@@ -160,16 +173,21 @@ class Package(Task):
 			dep_eapi = None
 			dep_valid_flag = None
 
+		validated_atoms = []
 		for k in self._dep_keys:
 			v = self.metadata.get(k)
 			if not v:
 				continue
 			try:
-				use_reduce(v, eapi=dep_eapi, matchall=True,
-					is_valid_flag=dep_valid_flag, token_class=Atom)
+				validated_atoms.extend(use_reduce(v, eapi=dep_eapi,
+					matchall=True, is_valid_flag=dep_valid_flag,
+					token_class=Atom, flat=True))
 			except InvalidDependString as e:
 				self._metadata_exception(k, e)
 
+		self._validated_atoms = frozenset(atom for atom in
+			validated_atoms if isinstance(atom, Atom))
+
 		k = 'PROVIDE'
 		v = self.metadata.get(k)
 		if v:
diff --git a/pym/_emerge/Scheduler.py b/pym/_emerge/Scheduler.py
index 30a7e101b..0b72a4cfc 100644
--- a/pym/_emerge/Scheduler.py
+++ b/pym/_emerge/Scheduler.py
@@ -328,12 +328,15 @@ class Scheduler(PollScheduler):
 		self._set_graph_config(graph_config)
 		self._blocker_db = {}
 		dynamic_deps = self.myopts.get("--dynamic-deps", "y") != "n"
+		ignore_built_slot_abi_deps = self.myopts.get(
+			"--ignore-built-slot-abi-deps", "n") == "y"
 		for root in self.trees:
 			if self._uninstall_only:
 				continue
 			if graph_config is None:
 				fake_vartree = FakeVartree(self.trees[root]["root_config"],
-					pkg_cache=self._pkg_cache, dynamic_deps=dynamic_deps)
+					pkg_cache=self._pkg_cache, dynamic_deps=dynamic_deps,
+					ignore_built_slot_abi_deps=ignore_built_slot_abi_deps)
 				fake_vartree.sync()
 			else:
 				fake_vartree = graph_config.trees[root]['vartree']
diff --git a/pym/_emerge/create_depgraph_params.py b/pym/_emerge/create_depgraph_params.py
index 8f15c6813..33d413aa3 100644
--- a/pym/_emerge/create_depgraph_params.py
+++ b/pym/_emerge/create_depgraph_params.py
@@ -15,12 +15,22 @@ def create_depgraph_params(myopts, myaction):
 	# complete:  completely account for all known dependencies
 	# remove:    build graph for use in removing packages
 	# rebuilt_binaries: replace installed packages with rebuilt binaries
+	# rebuild_if_new_slot_abi: rebuild or reinstall packages when
+	#	SLOT/ABI := operator dependencies can be satisfied by a newer
+	#	SLOT/ABI, so that older packages slots will become eligible for
+	#	removal by the --depclean action as soon as possible
+	# ignore_built_slot_abi_deps: ignore the SLOT/ABI := operator parts
+	#	of dependencies that have been recorded when packages where built
 	myparams = {"recurse" : True}
 
 	bdeps = myopts.get("--with-bdeps")
 	if bdeps is not None:
 		myparams["bdeps"] = bdeps
 
+	ignore_built_slot_abi_deps = myopts.get("--ignore-built-slot-abi-deps")
+	if ignore_built_slot_abi_deps is not None:
+		myparams["ignore_built_slot_abi_deps"] = ignore_built_slot_abi_deps
+
 	dynamic_deps = myopts.get("--dynamic-deps")
 	if dynamic_deps is not None:
 		myparams["dynamic_deps"] = dynamic_deps
@@ -31,6 +41,10 @@ def create_depgraph_params(myopts, myaction):
 		myparams["selective"] = True
 		return myparams
 
+	rebuild_if_new_slot_abi = myopts.get('--rebuild-if-new-slot-abi')
+	if rebuild_if_new_slot_abi is not None:
+		myparams['rebuild_if_new_slot_abi'] = rebuild_if_new_slot_abi
+
 	if "--update" in myopts or \
 		"--newuse" in myopts or \
 		"--reinstall" in myopts or \
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index 0c014bcfd..2547fa4e4 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -22,6 +22,7 @@ from portage.dbapi.dep_expand import dep_expand
 from portage.dep import Atom, best_match_to_list, extract_affecting_use, \
 	check_required_use, human_readable_required_use, match_from_list, \
 	_repo_separator
+from portage.dep._slot_abi import ignore_built_slot_abi_deps
 from portage.eapi import eapi_has_strong_blocks, eapi_has_required_use
 from portage.exception import InvalidAtom, InvalidDependString, PortageException
 from portage.output import colorize, create_color_func, \
@@ -110,6 +111,8 @@ class _frozen_depgraph_config(object):
 		self._pkg_cache = {}
 		self._highest_license_masked = {}
 		dynamic_deps = myopts.get("--dynamic-deps", "y") != "n"
+		ignore_built_slot_abi_deps = myopts.get(
+			"--ignore-built-slot-abi-deps", "n") == "y"
 		for myroot in trees:
 			self.trees[myroot] = {}
 			# Create a RootConfig instance that references
@@ -124,7 +127,8 @@ class _frozen_depgraph_config(object):
 				FakeVartree(trees[myroot]["root_config"],
 					pkg_cache=self._pkg_cache,
 					pkg_root_config=self.roots[myroot],
-					dynamic_deps=dynamic_deps)
+					dynamic_deps=dynamic_deps,
+					ignore_built_slot_abi_deps=ignore_built_slot_abi_deps)
 			self.pkgsettings[myroot] = portage.config(
 				clone=self.trees[myroot]["vartree"].settings)
 
@@ -404,6 +408,7 @@ class _dynamic_depgraph_config(object):
 		self._needed_license_changes = backtrack_parameters.needed_license_changes
 		self._needed_use_config_changes = backtrack_parameters.needed_use_config_changes
 		self._runtime_pkg_mask = backtrack_parameters.runtime_pkg_mask
+		self._slot_abi_replace_installed = backtrack_parameters.slot_abi_replace_installed
 		self._need_restart = False
 		# For conditions that always require user intervention, such as
 		# unsatisfied REQUIRED_USE (currently has no autounmask support).
@@ -413,6 +418,8 @@ class _dynamic_depgraph_config(object):
 		self._autounmask = depgraph._frozen_config.myopts.get('--autounmask') != 'n'
 		self._success_without_autounmask = False
 		self._traverse_ignored_deps = False
+		self._complete_mode = False
+		self._slot_abi_deps = {}
 
 		for myroot in depgraph._frozen_config.trees:
 			self.sets[myroot] = _depgraph_sets()
@@ -830,6 +837,7 @@ class depgraph(object):
 			slot_parent_atoms.update(parent_atoms)
 
 		conflict_pkgs = []
+		conflict_atoms = {}
 		for pkg in slot_nodes:
 
 			if self._dynamic_config._allow_backtracking and \
@@ -860,6 +868,7 @@ class depgraph(object):
 					parent_atoms.add(parent_atom)
 				else:
 					all_match = False
+					conflict_atoms.setdefault(parent_atom, set()).add(pkg)
 
 			if not all_match:
 				conflict_pkgs.append(pkg)
@@ -867,8 +876,14 @@ class depgraph(object):
 		if conflict_pkgs and \
 			self._dynamic_config._allow_backtracking and \
 			not self._accept_blocker_conflicts():
-			self._slot_confict_backtrack(root, slot_atom,
-				slot_parent_atoms, conflict_pkgs)
+			remaining = []
+			for pkg in conflict_pkgs:
+				if not self._slot_conflict_backtrack_abi(pkg,
+					slot_nodes, conflict_atoms):
+					remaining.append(pkg)
+			if remaining:
+				self._slot_confict_backtrack(root, slot_atom,
+					slot_parent_atoms, remaining)
 
 	def _slot_confict_backtrack(self, root, slot_atom,
 		all_parents, conflict_pkgs):
@@ -931,6 +946,219 @@ class depgraph(object):
 			writemsg_level("".join("%s\n" % l for l in msg),
 				noiselevel=-1, level=logging.DEBUG)
 
+	def _slot_conflict_backtrack_abi(self, pkg, slot_nodes, conflict_atoms):
+		"""
+		If one or more conflict atoms have a SLOT/ABI dep that can be resolved
+		by rebuilding the parent package, then schedule the rebuild via
+		backtracking, and return True. Otherwise, return False.
+		"""
+
+		found_update = False
+		for parent_atom, conflict_pkgs in conflict_atoms.items():
+			parent, atom = parent_atom
+			if atom.slot_abi_op != "=" or not parent.built:
+				continue
+
+			if pkg not in conflict_pkgs:
+				continue
+
+			for other_pkg in slot_nodes:
+				if other_pkg in conflict_pkgs:
+					continue
+
+				dep = Dependency(atom=atom, child=other_pkg,
+					parent=parent, root=pkg.root)
+
+				if self._slot_abi_update_probe(dep):
+					self._slot_abi_update_backtrack(dep)
+					found_update = True
+
+		return found_update
+
+	def _slot_abi_update_backtrack(self, dep, new_child_slot=None):
+		if new_child_slot is None:
+			child = dep.child
+		else:
+			child = new_child_slot
+		if "--debug" in self._frozen_config.myopts:
+			msg = []
+			msg.append("")
+			msg.append("")
+			msg.append("backtracking to due missed slot abi update:")
+			msg.append("   child package:  %s" % child)
+			if new_child_slot is not None:
+				msg.append("   new child slot package:  %s" % new_child_slot)
+			msg.append("   parent package: %s" % dep.parent)
+			msg.append("   atom: %s" % dep.atom)
+			msg.append("")
+			writemsg_level("\n".join(msg),
+				noiselevel=-1, level=logging.DEBUG)
+		backtrack_infos = self._dynamic_config._backtrack_infos
+		config = backtrack_infos.setdefault("config", {})
+
+		# mask unwanted binary packages if necessary
+		abi_masks = {}
+		if new_child_slot is None:
+			if not child.installed:
+				abi_masks.setdefault(child, {})["slot_abi_mask_built"] = dep
+		if not dep.parent.installed:
+			abi_masks.setdefault(dep.parent, {})["slot_abi_mask_built"] = dep
+		if abi_masks:
+			config.setdefault("slot_abi_mask_built", {}).update(abi_masks)
+
+		# trigger replacement of installed packages if necessary
+		abi_reinstalls = set()
+		if dep.parent.installed:
+			abi_reinstalls.add((dep.parent.root, dep.parent.slot_atom))
+		if new_child_slot is None and child.installed:
+			abi_reinstalls.add((child.root, child.slot_atom))
+		if abi_reinstalls:
+			config.setdefault("slot_abi_replace_installed",
+				set()).update(abi_reinstalls)
+
+		self._dynamic_config._need_restart = True
+
+	def _slot_abi_update_probe(self, dep, new_child_slot=False):
+		"""
+		SLOT/ABI := operators tend to prevent updates from getting pulled in,
+		since installed packages pull in packages with the SLOT/ABI that they
+		were built against. Detect this case so that we can schedule rebuilds
+		and reinstalls when appropriate.
+		NOTE: This function only searches for updates that involve upgrades
+			to higher versions, since the logic required to detect when a
+			downgrade would be desirable is not implemented.
+		"""
+
+		debug = "--debug" in self._frozen_config.myopts
+
+		for replacement_parent in self._iter_similar_available(dep.parent,
+			dep.parent.slot_atom):
+
+			for atom in replacement_parent.validated_atoms:
+				if not atom.slot_abi_op == "=" or \
+					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.
+				atom = atom.without_use
+
+				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
+
+				for pkg in self._iter_similar_available(
+					dep.child, atom):
+					if pkg.slot == dep.child.slot and \
+						pkg.slot_abi == dep.child.slot_abi:
+						# If SLOT/ABI is identical, then there's
+						# no point in updating.
+						continue
+					if new_child_slot:
+						if pkg.slot == dep.child.slot:
+							continue
+						if pkg < dep.child:
+							# the new slot only matters if the
+							# package version is higher
+							continue
+					else:
+						if pkg.slot != dep.child.slot:
+							continue
+						if pkg < dep.child:
+							# be careful not to trigger a rebuild when
+							# the only version available with a
+							# different slot_abi is an older version
+							continue
+
+					if debug:
+						msg = []
+						msg.append("")
+						msg.append("")
+						msg.append("slot_abi_update_probe:")
+						msg.append("   existing child package:  %s" % dep.child)
+						msg.append("   existing parent package: %s" % dep.parent)
+						msg.append("   new child package:  %s" % pkg)
+						msg.append("   new parent package: %s" % replacement_parent)
+						msg.append("")
+						writemsg_level("\n".join(msg),
+							noiselevel=-1, level=logging.DEBUG)
+
+					return pkg
+
+		if debug:
+			msg = []
+			msg.append("")
+			msg.append("")
+			msg.append("slot_abi_update_probe:")
+			msg.append("   existing child package:  %s" % dep.child)
+			msg.append("   existing parent package: %s" % dep.parent)
+			msg.append("   new child package:  %s" % None)
+			msg.append("   new parent package: %s" % None)
+			msg.append("")
+			writemsg_level("\n".join(msg),
+				noiselevel=-1, level=logging.DEBUG)
+
+		return None
+
+	def _iter_similar_available(self, graph_pkg, atom):
+		"""
+		Given a package that's in the graph, do a rough check to
+		see if a similar package is available to install. The given
+		graph_pkg itself may be yielded only if it's not installed.
+		"""
+		for pkg in self._iter_match_pkgs_any(
+			graph_pkg.root_config, atom):
+			if pkg.cp != graph_pkg.cp:
+				# discard old-style virtual match
+				continue
+			if pkg.installed:
+				continue
+			if pkg in self._dynamic_config._runtime_pkg_mask:
+				continue
+			if self._frozen_config.excluded_pkgs.findAtomForPackage(pkg,
+				modified_use=self._pkg_use_enabled(pkg)):
+				continue
+			if not self._pkg_visibility_check(pkg):
+				continue
+			yield pkg
+
+	def _slot_abi_trigger_reinstalls(self):
+		"""
+		Search for packages with slot-abi deps on older slots, and schedule
+		rebuilds if they can link to a newer slot that's in the graph.
+		"""
+
+		rebuild_if_new_slot_abi = self._dynamic_config.myparams.get(
+			"rebuild_if_new_slot_abi", "y") == "y"
+
+		for slot_key, slot_info in self._dynamic_config._slot_abi_deps.items():
+
+			for dep in slot_info:
+				if not (dep.child.built and dep.parent and
+					isinstance(dep.parent, Package) and dep.parent.built):
+					continue
+
+				# Check for slot update first, since we don't want to
+				# trigger reinstall of the child package when a newer
+				# slot will be used instead.
+				if rebuild_if_new_slot_abi:
+					new_child = self._slot_abi_update_probe(dep,
+						new_child_slot=True)
+					if new_child:
+						self._slot_abi_update_backtrack(dep,
+							new_child_slot=new_child)
+						break
+
+				if dep.want_update:
+					if self._slot_abi_update_probe(dep):
+						self._slot_abi_update_backtrack(dep)
+						break
+
 	def _reinstall_for_flags(self, pkg, forced_flags,
 		orig_use, orig_iuse, cur_use, cur_iuse):
 		"""Return a set of flags that trigger reinstallation, or None if there
@@ -1326,6 +1554,17 @@ class depgraph(object):
 			depth = min(pkg.depth, depth)
 		pkg.depth = depth
 		deep = self._dynamic_config.myparams.get("deep", 0)
+		update = "--update" in self._frozen_config.myopts
+
+		dep.want_update = (not self._dynamic_config._complete_mode and
+			(arg_atoms or update) and
+			not (deep is not True and depth > deep))
+
+		dep.child = pkg
+		if (not pkg.onlydeps and pkg.built and
+			dep.atom and dep.atom.slot_abi_built):
+			self._add_slot_abi_dep(dep)
+
 		recurse = deep is True or depth + 1 <= deep
 		dep_stack = self._dynamic_config._dep_stack
 		if "recurse" not in self._dynamic_config.myparams:
@@ -1357,6 +1596,14 @@ class depgraph(object):
 			self._dynamic_config._parent_atoms[pkg] = parent_atoms
 		parent_atoms.add(parent_atom)
 
+	def _add_slot_abi_dep(self, dep):
+		slot_key = (dep.root, dep.child.slot_atom)
+		slot_info = self._dynamic_config._slot_abi_deps.get(slot_key)
+		if slot_info is None:
+			slot_info = []
+			self._dynamic_config._slot_abi_deps[slot_key] = slot_info
+		slot_info.append(dep)
+
 	def _add_slot_conflict(self, pkg):
 		self._dynamic_config._slot_collision_nodes.add(pkg)
 		slot_key = (pkg.slot_atom, pkg.root)
@@ -1815,9 +2062,14 @@ class depgraph(object):
 			# Yield ~, =*, < and <= atoms first, since those are more likely to
 			# cause slot conflicts, and we want those atoms to be displayed
 			# in the resulting slot conflict message (see bug #291142).
+			# Give similar treatment to SLOT/ABI atoms.
 			conflict_atoms = []
 			normal_atoms = []
+			abi_atoms = []
 			for atom in cp_atoms:
+				if atom.slot_abi_built:
+					abi_atoms.append(atom)
+					continue
 				conflict = False
 				for child_pkg in atom_pkg_graph.child_nodes(atom):
 					existing_node, matches = \
@@ -1830,7 +2082,7 @@ class depgraph(object):
 				else:
 					normal_atoms.append(atom)
 
-			for atom in chain(conflict_atoms, normal_atoms):
+			for atom in chain(abi_atoms, conflict_atoms, normal_atoms):
 				child_pkgs = atom_pkg_graph.child_nodes(atom)
 				# if more than one child, yield highest version
 				if len(child_pkgs) > 1:
@@ -2256,6 +2508,8 @@ class depgraph(object):
 			atom_list.append((root, '__auto_rebuild__', atom))
 		for root, atom in self._rebuild.reinstall_list:
 			atom_list.append((root, '__auto_reinstall__', atom))
+		for root, atom in self._dynamic_config._slot_abi_replace_installed:
+			atom_list.append((root, '__auto_slot_abi_replace_installed__', atom))
 
 		set_dict = {}
 		for root, set_name, atom in atom_list:
@@ -2421,6 +2675,12 @@ class depgraph(object):
 			self._dynamic_config._need_restart = True
 			return False, myfavorites
 
+		if "config" in self._dynamic_config._backtrack_infos and \
+			("slot_abi_mask_built" in self._dynamic_config._backtrack_infos["config"] or
+			"slot_abi_replace_installed" in self._dynamic_config._backtrack_infos["config"]) and \
+			self.need_restart():
+			return False, myfavorites
+
 		# We're true here unless we are missing binaries.
 		return (True, myfavorites)
 
@@ -2575,6 +2835,22 @@ class depgraph(object):
 		"""This will raise InvalidDependString if necessary. If trees is
 		None then self._dynamic_config._filtered_trees is used."""
 
+		if not isinstance(depstring, list):
+			eapi = None
+			is_valid_flag = None
+			if parent is not None:
+				eapi = parent.metadata['EAPI']
+				if not parent.installed:
+					is_valid_flag = parent.iuse.is_valid_flag
+			depstring = portage.dep.use_reduce(depstring,
+				uselist=myuse, opconvert=True, token_class=Atom,
+				is_valid_flag=is_valid_flag, eapi=eapi)
+
+		if (self._dynamic_config.myparams.get(
+			"ignore_built_slot_abi_deps", "n") == "y" and
+			parent and parent.built):
+			ignore_built_slot_abi_deps(depstring)
+
 		pkgsettings = self._frozen_config.pkgsettings[root]
 		if trees is None:
 			trees = self._dynamic_config._filtered_trees
@@ -4298,8 +4574,14 @@ class depgraph(object):
 			"recurse" not in self._dynamic_config.myparams:
 			return 1
 
+		complete_if_new_ver = self._dynamic_config.myparams.get(
+			"complete_if_new_ver", "y") == "y"
+		rebuild_if_new_slot_abi = self._dynamic_config.myparams.get(
+			"rebuild_if_new_slot_abi", "y") == "y"
+		complete_if_new_slot = rebuild_if_new_slot_abi
+
 		if "complete" not in self._dynamic_config.myparams and \
-			self._dynamic_config.myparams.get("complete_if_new_ver", "y") == "y":
+			(complete_if_new_ver or complete_if_new_slot):
 			# Enable complete mode if an installed package version will change.
 			version_change = False
 			for node in self._dynamic_config.digraph:
@@ -4308,10 +4590,19 @@ class depgraph(object):
 					continue
 				vardb = self._frozen_config.roots[
 					node.root].trees["vartree"].dbapi
-				inst_pkg = vardb.match_pkgs(node.slot_atom)
-				if inst_pkg and inst_pkg[0].cp == node.cp:
-					inst_pkg = inst_pkg[0]
-					if inst_pkg < node or node < inst_pkg:
+
+				if complete_if_new_ver:
+					inst_pkg = vardb.match_pkgs(node.slot_atom)
+					if inst_pkg and inst_pkg[0].cp == node.cp:
+						inst_pkg = inst_pkg[0]
+						if inst_pkg < node or node < inst_pkg:
+							version_change = True
+							break
+
+				if complete_if_new_slot:
+					cp_list = vardb.match_pkgs(Atom(node.cp))
+					if (cp_list and cp_list[0].cp == node.cp and
+						not any(node.slot == pkg.slot for pkg in cp_list)):
 						version_change = True
 						break
 
@@ -4329,6 +4620,7 @@ class depgraph(object):
 		# scheduled for replacement. Also, toggle the "deep"
 		# parameter so that all dependencies are traversed and
 		# accounted for.
+		self._complete_mode = True
 		self._select_atoms = self._select_atoms_from_graph
 		if "remove" in self._dynamic_config.myparams:
 			self._select_package = self._select_pkg_from_installed
@@ -4956,6 +5248,8 @@ class depgraph(object):
 
 		self._process_slot_conflicts()
 
+		self._slot_abi_trigger_reinstalls()
+
 		if not self._validate_blockers():
 			self._dynamic_config._skip_restart = True
 			raise self._unknown_internal_error()
diff --git a/pym/_emerge/main.py b/pym/_emerge/main.py
index c52a3eaab..efd954bb9 100644
--- a/pym/_emerge/main.py
+++ b/pym/_emerge/main.py
@@ -477,6 +477,7 @@ def insert_optional_args(args):
 		'--package-moves'        : y_or_n,
 		'--quiet'                : y_or_n,
 		'--quiet-build'          : y_or_n,
+		'--rebuild-if-new-slot-abi': y_or_n,
 		'--rebuild-if-new-rev'   : y_or_n,
 		'--rebuild-if-new-ver'   : y_or_n,
 		'--rebuild-if-unbuilt'   : y_or_n,
@@ -746,6 +747,16 @@ def parse_opts(tmpcmdline, silent=False):
 			"choices" : true_y_or_n
 		},
 
+		"--ignore-built-slot-abi-deps": {
+			"help": "Ignore the SLOT/ABI := operator parts of dependencies that have "
+				"been recorded when packages where built. This option is intended "
+				"only for debugging purposes, and it only affects built packages "
+				"that specify SLOT/ABI := operator dependencies using the "
+				"experimental \"4-slot-abi\" EAPI.",
+			"type": "choice",
+			"choices": y_or_n
+		},
+
 		"--jobs": {
 
 			"shortopt" : "-j",
@@ -859,6 +870,15 @@ def parse_opts(tmpcmdline, silent=False):
 			"choices"  : true_y_or_n,
 		},
 
+		"--rebuild-if-new-slot-abi": {
+			"help"     : ("Automatically rebuild or reinstall packages when SLOT/ABI := "
+				"operator dependencies can be satisfied by a newer slot, so that "
+				"older packages slots will become eligible for removal by the "
+				"--depclean action as soon as possible."),
+			"type"     : "choice",
+			"choices"  : true_y_or_n
+		},
+
 		"--rebuild-if-new-rev": {
 			"help"     : "Rebuild packages when dependencies that are " + \
 				"used at both build-time and run-time are built, " + \
@@ -1100,6 +1120,9 @@ def parse_opts(tmpcmdline, silent=False):
 	if myoptions.quiet_build in true_y:
 		myoptions.quiet_build = 'y'
 
+	if myoptions.rebuild_if_new_slot_abi in true_y:
+		myoptions.rebuild_if_new_slot_abi = 'y'
+
 	if myoptions.rebuild_if_new_ver in true_y:
 		myoptions.rebuild_if_new_ver = True
 	else:
diff --git a/pym/_emerge/resolver/backtracking.py b/pym/_emerge/resolver/backtracking.py
index e3c5c7d78..09df9c822 100644
--- a/pym/_emerge/resolver/backtracking.py
+++ b/pym/_emerge/resolver/backtracking.py
@@ -7,7 +7,8 @@ class BacktrackParameter(object):
 
 	__slots__ = (
 		"needed_unstable_keywords", "runtime_pkg_mask", "needed_use_config_changes", "needed_license_changes",
-		"rebuild_list", "reinstall_list", "needed_p_mask_changes"
+		"rebuild_list", "reinstall_list", "needed_p_mask_changes",
+		"slot_abi_replace_installed"
 	)
 
 	def __init__(self):
@@ -18,6 +19,7 @@ class BacktrackParameter(object):
 		self.needed_license_changes = {}
 		self.rebuild_list = set()
 		self.reinstall_list = set()
+		self.slot_abi_replace_installed = set()
 
 	def __deepcopy__(self, memo=None):
 		if memo is None:
@@ -34,6 +36,7 @@ class BacktrackParameter(object):
 		result.needed_license_changes = copy.copy(self.needed_license_changes)
 		result.rebuild_list = copy.copy(self.rebuild_list)
 		result.reinstall_list = copy.copy(self.reinstall_list)
+		result.slot_abi_replace_installed = copy.copy(self.slot_abi_replace_installed)
 
 		return result
 
@@ -44,7 +47,8 @@ class BacktrackParameter(object):
 			self.needed_use_config_changes == other.needed_use_config_changes and \
 			self.needed_license_changes == other.needed_license_changes and \
 			self.rebuild_list == other.rebuild_list and \
-			self.reinstall_list == other.reinstall_list
+			self.reinstall_list == other.reinstall_list and \
+			self.slot_abi_replace_installed == other.slot_abi_replace_installed
 
 
 class _BacktrackNode(object):
@@ -114,9 +118,10 @@ class Backtracker(object):
 		before, we revert the mask for other packages (bug 375573).
 		"""
 
-		for pkg in runtime_pkg_mask:
+		for pkg, mask_info in runtime_pkg_mask.items():
 
-			if "missing dependency" in runtime_pkg_mask[pkg]:
+			if "missing dependency" in mask_info or \
+				"slot_abi_mask_built" in mask_info:
 				continue
 
 			entry_is_valid = False
@@ -181,6 +186,10 @@ class Backtracker(object):
 			elif change == "needed_use_config_changes":
 				for pkg, (new_use, new_changes) in data:
 					para.needed_use_config_changes[pkg] = (new_use, new_changes)
+			elif change == "slot_abi_mask_built":
+				para.runtime_pkg_mask.update(data)
+			elif change == "slot_abi_replace_installed":
+				para.slot_abi_replace_installed.update(data)
 			elif change == "rebuild_list":
 				para.rebuild_list.update(data)
 			elif change == "reinstall_list":