emerge: add --rebuild and --norebuild-atoms opts

Rebuild when build-time/run-time deps are upgraded.

If pkgA has been updated, and pkgB depends on pkgA at both
build-time and run-time, pkgB needs to be rebuilt. This
feature ensures that all packages are consistent when
dependencies that are used at both runtime and build time
are changed.

This feature only rebuilds packages one layer deep. That
means that if you upgrade libcros, for example, packages
that depend directly on libcros will be rebuilt and
reinstalled, but indirect dependencies will not be rebuilt.

BUG=chromium-os:14296

TEST=Test whether packages rebuilding a bunch of packages.

Change-Id: Idbc0532b4b1de28fd9e5a0abe3b7dbe1a3abd2c8

Review URL: http://codereview.chromium.org/6905107

12 files changed, 317 insertions, 26 deletions

diff --git a/pym/_emerge/DepPriority.py b/pym/_emerge/DepPriority.py
index f99b7264f..b08ffe583 100644
--- a/pym/_emerge/DepPriority.py
+++ b/pym/_emerge/DepPriority.py
@@ -4,7 +4,7 @@
 from _emerge.AbstractDepPriority import AbstractDepPriority
 class DepPriority(AbstractDepPriority):
 
-	__slots__ = ("satisfied", "optional", "rebuild")
+	__slots__ = ("satisfied", "optional", "rebuild", "ignored")
 
 	def __int__(self):
 		"""
@@ -24,17 +24,19 @@ class DepPriority(AbstractDepPriority):
 
 		"""
 
+		if self.optional:
+			return -3
 		if self.buildtime:
 			return 0
 		if self.runtime:
 			return -1
 		if self.runtime_post:
 			return -2
-		if self.optional:
-			return -3
 		return -4
 
 	def __str__(self):
+		if self.ignored:
+			return "ignored"
 		if self.optional:
 			return "optional"
 		if self.buildtime:
diff --git a/pym/_emerge/DepPriorityNormalRange.py b/pym/_emerge/DepPriorityNormalRange.py
index 259a1df65..808c9504b 100644
--- a/pym/_emerge/DepPriorityNormalRange.py
+++ b/pym/_emerge/DepPriorityNormalRange.py
@@ -33,7 +33,7 @@ class DepPriorityNormalRange(object):
 	def _ignore_runtime(cls, priority):
 		if priority.__class__ is not DepPriority:
 			return False
-		return not priority.buildtime
+		return bool(priority.optional or not priority.buildtime)
 
 	ignore_medium      = _ignore_runtime
 	ignore_medium_soft = _ignore_runtime_post
diff --git a/pym/_emerge/DepPrioritySatisfiedRange.py b/pym/_emerge/DepPrioritySatisfiedRange.py
index aa32d8f86..589afde3c 100644
--- a/pym/_emerge/DepPrioritySatisfiedRange.py
+++ b/pym/_emerge/DepPrioritySatisfiedRange.py
@@ -80,6 +80,7 @@ class DepPrioritySatisfiedRange(object):
 		if priority.__class__ is not DepPriority:
 			return False
 		return bool(priority.satisfied or \
+			priority.optional or \
 			not priority.buildtime)
 
 	ignore_medium      = _ignore_runtime
diff --git a/pym/_emerge/Dependency.py b/pym/_emerge/Dependency.py
index 63b2a1b12..d5d519d97 100644
--- a/pym/_emerge/Dependency.py
+++ b/pym/_emerge/Dependency.py
@@ -5,11 +5,16 @@ from _emerge.DepPriority import DepPriority
 from _emerge.SlotObject import SlotObject
 class Dependency(SlotObject):
 	__slots__ = ("atom", "blocker", "child", "depth",
-		"parent", "onlydeps", "priority", "root")
+		"parent", "onlydeps", "priority", "root",
+		"collapsed_parent", "collapsed_priority")
 	def __init__(self, **kwargs):
 		SlotObject.__init__(self, **kwargs)
 		if self.priority is None:
 			self.priority = DepPriority()
 		if self.depth is None:
 			self.depth = 0
+		if self.collapsed_parent is None:
+			self.collapsed_parent = self.parent
+		if self.collapsed_priority is None:
+			self.collapsed_priority = self.priority
 
diff --git a/pym/_emerge/UnmergeDepPriority.py b/pym/_emerge/UnmergeDepPriority.py
index 0f67f3b78..db4836e54 100644
--- a/pym/_emerge/UnmergeDepPriority.py
+++ b/pym/_emerge/UnmergeDepPriority.py
@@ -3,7 +3,7 @@
 
 from _emerge.AbstractDepPriority import AbstractDepPriority
 class UnmergeDepPriority(AbstractDepPriority):
-	__slots__ = ("optional", "satisfied",)
+	__slots__ = ("ignored", "optional", "satisfied",)
 	"""
 	Combination of properties           Priority  Category
 
@@ -32,6 +32,8 @@ class UnmergeDepPriority(AbstractDepPriority):
 		return -2
 
 	def __str__(self):
+		if self.ignored:
+			return "ignored"
 		myvalue = self.__int__()
 		if myvalue > self.SOFT:
 			return "hard"
diff --git a/pym/_emerge/create_depgraph_params.py b/pym/_emerge/create_depgraph_params.py
index d60259ef2..09863479a 100644
--- a/pym/_emerge/create_depgraph_params.py
+++ b/pym/_emerge/create_depgraph_params.py
@@ -33,7 +33,7 @@ def create_depgraph_params(myopts, myaction):
 	deep = myopts.get("--deep")
 	if deep is not None and deep != 0:
 		myparams["deep"] = deep
-	if "--complete-graph" in myopts:
+	if "--complete-graph" in myopts or "--rebuild" in myopts:
 		myparams["complete"] = True
 	if "--emptytree" in myopts:
 		myparams["empty"] = True
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index 73b81e1d1..f55d84d49 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -9,6 +9,7 @@ import logging
 import re
 import sys
 import textwrap
+from collections import deque
 from itertools import chain
 
 import portage
@@ -127,6 +128,10 @@ class _frozen_depgraph_config(object):
 		self.nousepkg_atoms = _wildcard_set(atoms)
 		atoms = ' '.join(myopts.get("--useoldpkg-atoms", [])).split()
 		self.useoldpkg_atoms = _wildcard_set(atoms)
+		atoms = ' '.join(myopts.get("--norebuild-atoms", [])).split()
+		self.norebuild_atoms = _wildcard_set(atoms)
+
+		self.rebuild = "--rebuild" in myopts
 
 class _depgraph_sets(object):
 	def __init__(self):
@@ -139,6 +144,128 @@ class _depgraph_sets(object):
 		self.atoms = InternalPackageSet(allow_repo=True)
 		self.atom_arg_map = {}
 
+class _rebuild_config(object):
+	def __init__(self, frozen_config, backtrack_parameters):
+		self._graph = digraph()
+		self._frozen_config = frozen_config
+		self.rebuild_list = backtrack_parameters.rebuild_list.copy()
+		self.orig_rebuild_list = self.rebuild_list.copy()
+		self.reinstall_list = backtrack_parameters.reinstall_list.copy()
+
+	def add(self, dep_pkg, dep):
+		parent = dep.collapsed_parent
+		priority = dep.collapsed_priority
+		norebuild_atoms = self._frozen_config.norebuild_atoms
+		if (self._frozen_config.rebuild and isinstance(parent, Package) and
+			parent.built and (priority.buildtime or priority.runtime) and
+			isinstance(dep_pkg, Package) and
+			not norebuild_atoms.findAtomForPackage(parent)):
+			self._graph.add(dep_pkg, parent, priority)
+
+	def _trigger_rebuild(self, parent, build_deps, runtime_deps):
+		root_slot = (parent.root, parent.slot_atom)
+		if root_slot in self.rebuild_list:
+			return False
+		trees = self._frozen_config.trees
+		children = set(build_deps).intersection(runtime_deps)
+		reinstall = False
+		for slot_atom in children:
+			kids = set([build_deps[slot_atom], runtime_deps[slot_atom]])
+			for dep_pkg in kids:
+				dep_root_slot = (dep_pkg.root, slot_atom)
+				if (not dep_pkg.built and
+					dep_root_slot not in self.orig_rebuild_list):
+					# There's no binary package for dep_pkg, so any binary
+					# package for this parent would be invalid. Force rebuild.
+					self.rebuild_list.add(root_slot)
+					return True
+				elif ("--usepkg" in self._frozen_config.myopts and
+					(dep_root_slot in self.reinstall_list or
+					dep_root_slot in self.rebuild_list or
+					not dep_pkg.installed)):
+
+					# A direct rebuild dependency is being installed. We
+					# should update the parent as well to the latest binary,
+					# if that binary is valid.
+					#
+					# To validate the binary, we check whether all of the
+					# rebuild dependencies are present on the same binhost.
+					#
+					# 1) If parent is present on the binhost, but one of its
+					#    rebuild dependencies is not, then the parent should
+					#    be rebuilt from source.
+					# 2) Otherwise, the parent binary is assumed to be valid,
+					#    because all of its rebuild dependencies are
+					#    consistent.
+					bintree = trees[parent.root]["bintree"]
+					uri = bintree.get_pkgindex_uri(parent.cpv)
+					dep_uri = bintree.get_pkgindex_uri(dep_pkg.cpv)
+					bindb = bintree.dbapi
+
+					if uri and uri != dep_uri:
+						# 1) Remote binary package is invalid because it was
+						#    built without dep_pkg. Force rebuild.
+						self.rebuild_list.add(root_slot)
+						return True
+					elif (parent.installed and
+						root_slot not in self.reinstall_list):
+						inst_build_time = parent.metadata.get("BUILD_TIME")
+						try:
+							bin_build_time, = bindb.aux_get(parent.cpv,
+								["BUILD_TIME"])
+						except KeyError:
+							continue
+						if bin_build_time != inst_build_time:
+							# 2) Remote binary package is valid, and local package
+							#    is not up to date. Force reinstall.
+							reinstall = True
+		if reinstall:
+			self.reinstall_list.add(root_slot)
+		return reinstall
+
+	def trigger_rebuilds(self):
+		"""
+		Trigger rebuilds where necessary. If pkgA has been updated, and pkgB
+		depends on pkgA at both build-time and run-time, pkgB needs to be
+		rebuilt.
+		"""
+		need_restart = False
+		graph = self._graph
+		build_deps = {}
+		runtime_deps = {}
+		leaf_nodes = deque(graph.leaf_nodes())
+
+		# Trigger rebuilds bottom-up (starting with the leaves) so that parents
+		# will always know which children are being rebuilt.
+		while leaf_nodes:
+			node = leaf_nodes.popleft()
+			slot_atom = node.slot_atom
+
+			# Remove our leaf node from the graph, keeping track of deps.
+			parents = graph.nodes[node][1].items()
+			graph.remove(node)
+			for parent, priorities in parents:
+				for priority in priorities:
+					if priority.buildtime:
+						build_deps.setdefault(parent, {})[slot_atom] = node
+					if priority.runtime:
+						runtime_deps.setdefault(parent, {})[slot_atom] = node
+				if not graph.child_nodes(parent):
+					leaf_nodes.append(parent)
+
+			# Trigger rebuilds for our leaf node. Because all of our children
+			# have been processed, build_deps and runtime_deps will be
+			# completely filled in, and self.rebuild_list / self.reinstall_list
+			# will tell us whether any of our children need to be rebuilt or
+			# reinstalled.
+			node_build_deps = build_deps.get(node, {})
+			node_runtime_deps = runtime_deps.get(node, {})
+			if self._trigger_rebuild(node, node_build_deps, node_runtime_deps):
+				need_restart = True
+
+		return need_restart
+
+
 class _dynamic_depgraph_config(object):
 
 	def __init__(self, depgraph, myparams, allow_backtracking, backtrack_parameters):
@@ -306,6 +433,7 @@ class depgraph(object):
 		self._frozen_config = frozen_config
 		self._dynamic_config = _dynamic_depgraph_config(self, myparams,
 			allow_backtracking, backtrack_parameters)
+		self._rebuild = _rebuild_config(frozen_config, backtrack_parameters)
 
 		self._select_atoms = self._select_atoms_highest_available
 		self._select_package = self._select_pkg_highest_available
@@ -671,6 +799,8 @@ class depgraph(object):
 		if dep.blocker:
 			if not buildpkgonly and \
 				not nodeps and \
+				not dep.collapsed_priority.ignored and \
+				not dep.collapsed_priority.optional and \
 				dep.parent not in self._dynamic_config._slot_collision_nodes:
 				if dep.parent.onlydeps:
 					# It's safe to ignore blockers if the
@@ -695,9 +825,9 @@ class depgraph(object):
 				dep.root].get(dep_pkg.slot_atom)
 
 		if not dep_pkg:
-			if dep.priority.optional:
-				# This could be an unnecessary build-time dep
-				# pulled in by --with-bdeps=y.
+			if (dep.collapsed_priority.optional or
+				dep.collapsed_priority.ignored):
+				# This is an unnecessary build-time dep.
 				return 1
 			if allow_unsatisfied:
 				self._dynamic_config._unsatisfied_deps.append(dep)
@@ -740,7 +870,10 @@ class depgraph(object):
 
 			return 0
 
-		if not self._add_pkg(dep_pkg, dep):
+		self._rebuild.add(dep_pkg, dep)
+
+		if (not dep.collapsed_priority.ignored and
+			not self._add_pkg(dep_pkg, dep)):
 			return 0
 		return 1
 
@@ -1110,6 +1243,7 @@ class depgraph(object):
 			edepend["RDEPEND"] = ""
 			edepend["PDEPEND"] = ""
 
+		ignore_build_time_deps = False
 		if pkg.built and not removal_action:
 			if self._frozen_config.myopts.get("--with-bdeps", "n") == "y":
 				# Pull in build time deps as requested, but marked them as
@@ -1121,11 +1255,10 @@ class depgraph(object):
 				# failing.
 				pass
 			else:
-				# built packages do not have build time dependencies.
-				edepend["DEPEND"] = ""
+				ignore_build_time_deps = True
 
 		if removal_action and self._frozen_config.myopts.get("--with-bdeps", "y") == "n":
-			edepend["DEPEND"] = ""
+			ignore_build_time_deps = True
 
 		if removal_action:
 			depend_root = myroot
@@ -1136,13 +1269,14 @@ class depgraph(object):
 				if root_deps is True:
 					depend_root = myroot
 				elif root_deps == "rdeps":
-					edepend["DEPEND"] = ""
+					ignore_build_time_deps = True
 
 		deps = (
 			(depend_root, edepend["DEPEND"],
-				self._priority(buildtime=(not pkg.built),
-				optional=pkg.built),
-				pkg.built),
+				self._priority(buildtime=True,
+				optional=pkg.built,
+				ignored=ignore_build_time_deps),
+				pkg.built or ignore_build_time_deps),
 			(myroot, edepend["RDEPEND"],
 				self._priority(runtime=True),
 				False),
@@ -1266,6 +1400,7 @@ class depgraph(object):
 
 			mypriority = dep_priority.copy()
 			if not atom.blocker:
+				root_slot = (pkg.root, pkg.slot_atom)
 				inst_pkgs = [inst_pkg for inst_pkg in vardb.match_pkgs(atom)
 					if not reinstall_atoms.findAtomForPackage(inst_pkg,
 							modified_use=self._pkg_use_enabled(inst_pkg))]
@@ -1375,7 +1510,8 @@ class depgraph(object):
 				# same depth as the virtual itself.
 				dep = Dependency(atom=atom,
 					blocker=atom.blocker, child=child, depth=virt_dep.depth,
-					parent=virt_pkg, priority=mypriority, root=dep_root)
+					parent=virt_pkg, priority=mypriority, root=dep_root,
+					collapsed_parent=pkg, collapsed_priority=dep_priority)
 
 				ignored = False
 				if not atom.blocker and \
@@ -1931,9 +2067,12 @@ class depgraph(object):
 		pkgsettings = self._frozen_config.pkgsettings[myroot]
 		pprovideddict = pkgsettings.pprovideddict
 		virtuals = pkgsettings.getvirtuals()
-		for arg in self._expand_set_args(
-			self._dynamic_config._initial_arg_list,
-			add_to_digraph=True):
+		args = self._dynamic_config._initial_arg_list[:]
+		for root, atom in chain(self._rebuild.rebuild_list,
+			self._rebuild.reinstall_list):
+			args.append(AtomArg(arg=atom, atom=atom,
+				root_config=self._frozen_config.roots[root]))
+		for arg in self._expand_set_args(args, add_to_digraph=True):
 			for atom in arg.pset.getAtoms():
 				self._spinner_update()
 				dep = Dependency(atom=atom, onlydeps=onlydeps,
@@ -2049,6 +2188,14 @@ class depgraph(object):
 			self._dynamic_config._success_without_autounmask = True
 			return False, myfavorites
 
+		if self._rebuild.trigger_rebuilds():
+			backtrack_infos = self._dynamic_config._backtrack_infos
+			config = backtrack_infos.setdefault("config", {})
+			config["rebuild_list"] = self._rebuild.rebuild_list
+			config["reinstall_list"] = self._rebuild.reinstall_list
+			self._dynamic_config._need_restart = True
+			return False, myfavorites
+
 		# We're true here unless we are missing binaries.
 		return (True, myfavorites)
 
@@ -2538,7 +2685,12 @@ class depgraph(object):
 								pkg.iuse.is_valid_flag):
 								required_use_unsatisfied.append(pkg)
 								continue
-						if pkg.built and not mreasons:
+						root_slot = (pkg.root, pkg.slot_atom)
+						if pkg.built and root_slot in self._rebuild.rebuild_list:
+							mreasons = ["need to rebuild from source"]
+						elif pkg.installed and root_slot in self._rebuild.reinstall_list:
+							mreasons = ["need to rebuild from source"]
+						elif pkg.built and not mreasons:
 							mreasons = ["use flag configuration mismatch"]
 					masked_packages.append(
 						(root_config, pkgsettings, cpv, repo, metadata, mreasons))
@@ -3216,6 +3368,12 @@ class depgraph(object):
 					if pkg in self._dynamic_config._runtime_pkg_mask:
 						# The package has been masked by the backtracking logic
 						continue
+					root_slot = (pkg.root, pkg.slot_atom)
+					if pkg.built and root_slot in self._rebuild.rebuild_list:
+						continue
+					if (pkg.installed and
+						root_slot in self._rebuild.reinstall_list):
+						continue
 
 					if not pkg.installed and \
 						self._frozen_config.excluded_pkgs.findAtomForPackage(pkg, \
diff --git a/pym/_emerge/help.py b/pym/_emerge/help.py
index fb1e129e7..bf2437dce 100644
--- a/pym/_emerge/help.py
+++ b/pym/_emerge/help.py
@@ -565,6 +565,12 @@ def help(myopts, havecolor=1):
 		for line in wrap(desc, desc_width):
 			print(desc_indent + line)
 		print()
+		print("       " + green("--norebuild-atoms") + " " + turquoise("ATOMS"))
+		desc = "A space separated list of package names or slot atoms." + \
+			" Emerge will not rebuild matching packages due to --rebuild."
+		for line in wrap(desc, desc_width):
+			print(desc_indent + line)
+		print()
 		print("       "+green("--oneshot")+" ("+green("-1")+" short option)")
 		print("              Emerge as normal, but don't add packages to the world profile.")
 		print("              This package will only be updated if it is depended upon by")
@@ -616,6 +622,13 @@ def help(myopts, havecolor=1):
 		for line in wrap(desc, desc_width):
 			print(desc_indent + line)
 		print()
+		print("       " + green("--rebuild") + " [ %s | %s ]" % \
+			(turquoise("y"), turquoise("n")))
+		desc = "Rebuild packages when dependencies that are used " + \
+			"at both build-time and run-time are upgraded."
+		for line in wrap(desc, desc_width):
+			print(desc_indent + line)
+		print()
 		print("       " + green("--rebuilt-binaries") + " [ %s | %s ]" % \
 			(turquoise("y"), turquoise("n")))
 		desc = "Replace installed packages with binary packages that have " + \
diff --git a/pym/_emerge/main.py b/pym/_emerge/main.py
index e0cd0c024..434fd5a57 100644
--- a/pym/_emerge/main.py
+++ b/pym/_emerge/main.py
@@ -440,6 +440,7 @@ def insert_optional_args(args):
 		'--package-moves'        : y_or_n,
 		'--quiet'                : y_or_n,
 		'--quiet-build'          : y_or_n,
+		'--rebuild'              : y_or_n,
 		'--rebuilt-binaries'     : y_or_n,
 		'--root-deps'  : ('rdeps',),
 		'--select'               : y_or_n,
@@ -741,6 +742,14 @@ def parse_opts(tmpcmdline, silent=False):
 			"action" : "append",
 		},
 
+		"--norebuild-atoms": {
+			"help"   :"A space separated list of package names or slot atoms. " + \
+				"Emerge will not rebuild these packages due to the " + \
+				"--rebuild flag. ",
+
+			"action" : "append",
+		},
+
 		"--package-moves": {
 			"help"     : "perform package moves when necessary",
 			"type"     : "choice",
@@ -760,6 +769,13 @@ def parse_opts(tmpcmdline, silent=False):
 			"choices"  : true_y_or_n
 		},
 
+		"--rebuild": {
+			"help"     : "Rebuild packages when dependencies that are " + \
+				"used at both build-time and run-time are upgraded.",
+			"type"     : "choice",
+			"choices"  : true_y_or_n
+		},
+
 		"--rebuilt-binaries": {
 			"help"     : "replace installed packages with binary " + \
 			             "packages that have been rebuilt",
@@ -889,7 +905,7 @@ def parse_opts(tmpcmdline, silent=False):
 	else:
 		myoptions.binpkg_respect_use = None
 
-	if myoptions.complete_graph in true_y:
+	if myoptions.complete_graph in true_y or myoptions.rebuild in true_y:
 		myoptions.complete_graph = True
 	else:
 		myoptions.complete_graph = None
@@ -910,6 +926,12 @@ def parse_opts(tmpcmdline, silent=False):
 			parser.error("Invalid Atom(s) in --reinstall-atoms parameter: '%s' (only package names and slot atoms (with wildcards) allowed)\n" % \
 				(",".join(bad_atoms),))
 
+	if myoptions.norebuild_atoms:
+		bad_atoms = _find_bad_atoms(myoptions.norebuild_atoms)
+		if bad_atoms and not silent:
+			parser.error("Invalid Atom(s) in --norebuild-atoms parameter: '%s' (only package names and slot atoms (with wildcards) allowed)\n" % \
+				(",".join(bad_atoms),))
+
 	if myoptions.nousepkg_atoms:
 		bad_atoms = _find_bad_atoms(myoptions.nousepkg_atoms)
 		if bad_atoms and not silent:
@@ -953,6 +975,11 @@ def parse_opts(tmpcmdline, silent=False):
 	else:
 		myoptions.quiet_build = None
 
+	if myoptions.rebuild in true_y:
+		myoptions.rebuild = True
+	else:
+		myoptions.rebuild = None
+
 	if myoptions.rebuilt_binaries in true_y:
 		myoptions.rebuilt_binaries = True
 
diff --git a/pym/_emerge/resolver/backtracking.py b/pym/_emerge/resolver/backtracking.py
index 1ffada96f..f00e6ca19 100644
--- a/pym/_emerge/resolver/backtracking.py
+++ b/pym/_emerge/resolver/backtracking.py
@@ -7,6 +7,7 @@ class BacktrackParameter(object):
 
 	__slots__ = (
 		"needed_unstable_keywords", "runtime_pkg_mask", "needed_use_config_changes", "needed_license_changes",
+		"rebuild_list", "reinstall_list"
 	)
 
 	def __init__(self):
@@ -14,6 +15,8 @@ class BacktrackParameter(object):
 		self.runtime_pkg_mask = {}
 		self.needed_use_config_changes = {}
 		self.needed_license_changes = {}
+		self.rebuild_list = set()
+		self.reinstall_list = set()
 
 	def __deepcopy__(self, memo=None):
 		if memo is None:
@@ -27,6 +30,8 @@ class BacktrackParameter(object):
 		result.runtime_pkg_mask = copy.copy(self.runtime_pkg_mask)
 		result.needed_use_config_changes = copy.copy(self.needed_use_config_changes)
 		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)
 
 		return result
 
@@ -34,7 +39,9 @@ class BacktrackParameter(object):
 		return self.needed_unstable_keywords == other.needed_unstable_keywords and \
 			self.runtime_pkg_mask == other.runtime_pkg_mask and \
 			self.needed_use_config_changes == other.needed_use_config_changes and \
-			self.needed_license_changes == other.needed_license_changes
+			self.needed_license_changes == other.needed_license_changes and \
+			self.rebuild_list == other.rebuild_list and \
+			self.reinstall_list == other.reinstall_list
 
 
 class _BacktrackNode:
@@ -137,6 +144,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 == "rebuild_list":
+				para.rebuild_list.update(data)
+			elif change == "reinstall_list":
+				para.reinstall_list.update(data)
 
 		self._add(new_node, explore=explore)
 		self._current_node = new_node
diff --git a/pym/portage/dbapi/bintree.py b/pym/portage/dbapi/bintree.py
index 16b79db47..33cd6580c 100644
--- a/pym/portage/dbapi/bintree.py
+++ b/pym/portage/dbapi/bintree.py
@@ -228,6 +228,7 @@ class binarytree(object):
 			self.invalids = []
 			self.settings = settings
 			self._pkg_paths = {}
+			self._pkgindex_uri = {}
 			self._populating = False
 			self._all_directory = os.path.isdir(
 				os.path.join(self.pkgdir, "All"))
@@ -874,8 +875,9 @@ class binarytree(object):
 				# Organize remote package list as a cpv -> metadata map.
 				remotepkgs = _pkgindex_cpv_map_latest_build(pkgindex)
 				remote_base_uri = pkgindex.header.get("URI", base_url)
-				for remote_metadata in remotepkgs.values():
+				for cpv, remote_metadata in remotepkgs.items():
 					remote_metadata["BASE_URI"] = remote_base_uri
+					self._pkgindex_uri[cpv] = url
 				self._remotepkgs.update(remotepkgs)
 				self._remote_has_index = True
 				for cpv in remotepkgs:
@@ -1225,6 +1227,10 @@ class binarytree(object):
 		# package is downloaded, state is updated by self.inject().
 		return True
 
+	def get_pkgindex_uri(self, pkgname):
+		"""Returns the URI to the Packages file for a given package."""
+		return self._pkgindex_uri.get(pkgname)
+
 	def gettbz2(self, pkgname):
 		"""Fetches the package from a remote site, if necessary.  Attempts to
 		resume if the file appears to be partially downloaded."""
diff --git a/pym/portage/tests/resolver/test_rebuild.py b/pym/portage/tests/resolver/test_rebuild.py
new file mode 100644
index 000000000..2185bf791
--- /dev/null
+++ b/pym/portage/tests/resolver/test_rebuild.py
@@ -0,0 +1,66 @@
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (ResolverPlayground,
+	ResolverPlaygroundTestCase)
+
+class RebuildTestCase(TestCase):
+
+	def testRebuild(self):
+		"""
+		Rebuild packages when dependencies that are used at both build-time and
+		run-time are upgraded.
+		"""
+
+		ebuilds = {
+			"sys-libs/x-1": { },
+			"sys-libs/x-2": { },
+			"sys-apps/a-1": { "DEPEND"  : "sys-libs/x", "RDEPEND" : "sys-libs/x"},
+			"sys-apps/a-2": { "DEPEND"  : "sys-libs/x", "RDEPEND" : "sys-libs/x"},
+			"sys-apps/b-1": { "DEPEND"  : "sys-libs/x", "RDEPEND" : "sys-libs/x"},
+			"sys-apps/b-2": { "DEPEND"  : "sys-libs/x", "RDEPEND" : "sys-libs/x"},
+			"sys-apps/c-1": { "DEPEND"  : "sys-libs/x", "RDEPEND" : ""},
+			"sys-apps/c-2": { "DEPEND"  : "sys-libs/x", "RDEPEND" : ""},
+			"sys-apps/d-1": { "RDEPEND" : "sys-libs/x"},
+			"sys-apps/d-2": { "RDEPEND" : "sys-libs/x"},
+			"sys-apps/e-2": { "DEPEND"  : "sys-libs/x", "RDEPEND" : "sys-libs/x"},
+			"sys-apps/f-2": { "DEPEND"  : "sys-apps/a", "RDEPEND" : "sys-apps/a"},
+			}
+
+		installed = {
+			"sys-libs/x-1": { },
+			"sys-apps/a-1": { "DEPEND"  : "sys-libs/x", "RDEPEND" : "sys-libs/x"},
+			"sys-apps/b-1": { "DEPEND"  : "sys-libs/x", "RDEPEND" : "sys-libs/x"},
+			"sys-apps/c-1": { "DEPEND"  : "sys-libs/x", "RDEPEND" : ""},
+			"sys-apps/d-1": { "RDEPEND" : "sys-libs/x"},
+			"sys-apps/e-1": { "DEPEND"  : "sys-libs/x", "RDEPEND" : "sys-libs/x"},
+			"sys-apps/f-1": { "DEPEND"  : "sys-apps/a", "RDEPEND" : "sys-apps/a"},
+			}
+
+		world = ["sys-apps/a", "sys-apps/b", "sys-apps/c", "sys-apps/d",
+			"sys-apps/e", "sys-apps/f"]
+
+		test_cases = (
+				ResolverPlaygroundTestCase(
+					["sys-libs/x"],
+					options = {"--rebuild" : True,
+						"--norebuild-atoms" : ["sys-apps/b"]},
+					mergelist = ['sys-libs/x-2', 'sys-apps/a-2', 'sys-apps/e-2'],
+					ignore_mergelist_order = True,
+					success = True),
+
+				ResolverPlaygroundTestCase(
+					["sys-libs/x"],
+					options = {"--rebuild" : True},
+					mergelist = ['sys-libs/x-2', 'sys-apps/a-2', 'sys-apps/b-2', 'sys-apps/e-2'],
+					ignore_mergelist_order = True,
+					success = True),
+			)
+
+		playground = ResolverPlayground(ebuilds=ebuilds,
+			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:
+			playground.cleanup()