Allow a package to replace its own buildtime dependency

If a package has a buildtime dependency on a previous version that
it will replace, then do not treat it as a slot conflict. This
solves inappropriate behavior for dev-lang/rust[system-bootstrap].

This requires adjustments to package selection logic in several
locations, in order to ensure that an installed package instance
will be selected to satisfy a buildtime dependency when
appropriate. Dependencies of the installed package will be
entirely ignored, but that has already been the case when using
installed package to break cycles, as discussed in bug 199856.

Bug: https://bugs.gentoo.org/756793
Bug: https://bugs.gentoo.org/756961
Signed-off-by: Zac Medico <zmedico@gentoo.org>

3 files changed, 164 insertions, 22 deletions

diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index d10474ab3..1271bda3e 100644
--- a/lib/_emerge/depgraph.py
+++ b/lib/_emerge/depgraph.py
@@ -85,6 +85,8 @@ from _emerge.resolver.output import Display, format_unmatched_atom
 
 # Exposes a depgraph interface to dep_check.
 _dep_check_graph_interface = collections.namedtuple('_dep_check_graph_interface',(
+	# Checks if parent package will replace child.
+	'will_replace_child',
 	# Indicates a removal action, like depclean or prune.
 	'removal_action',
 	# Checks if update is desirable for a given package.
@@ -507,6 +509,7 @@ class _dynamic_depgraph_config:
 		# Track missed updates caused by solved conflicts.
 		self._conflict_missed_update = collections.defaultdict(dict)
 		dep_check_iface = _dep_check_graph_interface(
+			will_replace_child=depgraph._will_replace_child,
 			removal_action="remove" in myparams,
 			want_update_pkg=depgraph._want_update_pkg,
 		)
@@ -3104,6 +3107,22 @@ class depgraph:
 								self._frozen_config.myopts,
 								modified_use=self._pkg_use_enabled(pkg))),
 								level=logging.DEBUG, noiselevel=-1)
+				elif (pkg.installed and myparent and
+					pkg.root == myparent.root and
+					pkg.slot_atom == myparent.slot_atom):
+					# If the parent package is replacing the child package then
+					# there's no slot conflict. Since the child will be replaced,
+					# do not add it to the graph. No attempt will be made to
+					# satisfy its dependencies, which is unsafe if it has any
+					# missing dependencies, as discussed in bug 199856.
+					if debug:
+						writemsg_level(
+							"%s%s %s\n" % ("Replace Child:".ljust(15),
+							pkg, pkg_use_display(pkg,
+							self._frozen_config.myopts,
+							modified_use=self._pkg_use_enabled(pkg))),
+							level=logging.DEBUG, noiselevel=-1)
+					return 1
 
 				else:
 					if debug:
@@ -5877,6 +5896,27 @@ class depgraph:
 			(arg_atoms or update) and
 			not self._too_deep(depth))
 
+	def _will_replace_child(self, parent, root, atom):
+		"""
+		Check if a given parent package will replace a child package
+		for the given root and atom.
+
+		@param parent: parent package
+		@type parent: Package
+		@param root: child root
+		@type root: str
+		@param atom: child atom
+		@type atom: Atom
+		@rtype: Package
+		@return: child package to replace, or None
+		"""
+		if parent.root != root or parent.cp != atom.cp:
+			return None
+		for child in self._iter_match_pkgs(self._frozen_config.roots[root], "installed", atom):
+			if parent.slot_atom == child.slot_atom:
+				return child
+		return None
+
 	def _too_deep(self, depth):
 		"""
 		Check if a package depth is deeper than the max allowed depth.
@@ -6440,19 +6480,21 @@ class depgraph:
 					# Calculation of USE for unbuilt ebuilds is relatively
 					# expensive, so it is only performed lazily, after the
 					# above visibility checks are complete.
-
-					myarg = None
-					try:
-						for myarg, myarg_atom in self._iter_atoms_for_pkg(pkg):
-							if myarg.force_reinstall:
-								reinstall = True
-								break
-					except InvalidDependString:
-						if not installed:
-							# masked by corruption
-							continue
-					if not installed and myarg:
-						found_available_arg = True
+					effective_parent = parent or self._select_atoms_parent
+					if not (effective_parent and self._will_replace_child(
+						effective_parent, root, atom)):
+						myarg = None
+						try:
+							for myarg, myarg_atom in self._iter_atoms_for_pkg(pkg):
+								if myarg.force_reinstall:
+									reinstall = True
+									break
+						except InvalidDependString:
+							if not installed:
+								# masked by corruption
+								continue
+						if not installed and myarg:
+							found_available_arg = True
 
 					if atom.package and atom.unevaluated_atom.use:
 						#Make sure we don't miss a 'missing IUSE'.
diff --git a/lib/portage/dep/dep_check.py b/lib/portage/dep/dep_check.py
index b89d5d651..3bed6c348 100644
--- a/lib/portage/dep/dep_check.py
+++ b/lib/portage/dep/dep_check.py
@@ -405,9 +405,15 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None,
 		for atom in atoms:
 			if atom.blocker:
 				continue
+
+			# It's not a downgrade if parent is replacing child.
+			replacing = (parent and graph_interface and
+				graph_interface.will_replace_child(parent, myroot, atom))
 			# Ignore USE dependencies here since we don't want USE
 			# settings to adversely affect || preference evaluation.
 			avail_pkg = mydbapi_match_pkgs(atom.without_use)
+			if not avail_pkg and replacing:
+				avail_pkg = [replacing]
 			if avail_pkg:
 				avail_pkg = avail_pkg[-1] # highest (ascending order)
 				avail_slot = Atom("%s:%s" % (atom.cp, avail_pkg.slot))
@@ -416,7 +422,7 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None,
 				all_use_satisfied = False
 				break
 
-			if graph_db is not None and downgrade_probe is not None:
+			if not replacing and graph_db is not None and downgrade_probe is not None:
 				slot_matches = graph_db.match_pkgs(avail_slot)
 				if (len(slot_matches) > 1 and
 					avail_pkg < slot_matches[-1] and
@@ -463,7 +469,7 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None,
 						avail_pkg = avail_pkg_use
 					avail_slot = Atom("%s:%s" % (atom.cp, avail_pkg.slot))
 
-			if downgrade_probe is not None and graph is not None:
+			if not replacing and downgrade_probe is not None and graph is not None:
 				highest_in_slot = mydbapi_match_pkgs(avail_slot)
 				highest_in_slot = (highest_in_slot[-1]
 					if highest_in_slot else None)
@@ -576,14 +582,14 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None,
 				this_choice.all_in_graph = all_in_graph
 
 				circular_atom = None
-				if not (parent is None or priority is None) and \
-					(parent.onlydeps or
-					(priority.buildtime and not priority.satisfied and not priority.optional)):
+				if parent and parent.onlydeps:
 						# Check if the atom would result in a direct circular
-						# dependency and try to avoid that if it seems likely
-						# to be unresolvable. This is only relevant for
-						# buildtime deps that aren't already satisfied by an
-						# installed package.
+						# dependency and avoid that for --onlydeps arguments
+						# since it can defeat the purpose of --onlydeps.
+						# This check should only be used for --onlydeps
+						# arguments, since it can interfere with circular
+						# dependency backtracking choices, causing the test
+						# case for bug 756961 to fail.
 						cpv_slot_list = [parent]
 						for atom in atoms:
 							if atom.blocker:
diff --git a/lib/portage/tests/resolver/test_circular_choices_rust.py b/lib/portage/tests/resolver/test_circular_choices_rust.py
new file mode 100644
index 000000000..612f76c48
--- /dev/null
+++ b/lib/portage/tests/resolver/test_circular_choices_rust.py
@@ -0,0 +1,94 @@
+# Copyright 2020 Gentoo Authors
+# 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 CircularRustTestCase(TestCase):
+	def testCircularPypyExe(self):
+
+		ebuilds = {
+			"dev-lang/rust-1.47.0-r2": {
+				"EAPI": "7",
+				"SLOT": "stable/1.47",
+				"BDEPEND": "|| ( =dev-lang/rust-1.46* =dev-lang/rust-bin-1.46* =dev-lang/rust-1.47* =dev-lang/rust-bin-1.47* )",
+			},
+			"dev-lang/rust-1.46.0": {
+				"EAPI": "7",
+				"SLOT": "stable/1.46",
+				"BDEPEND": "|| ( =dev-lang/rust-1.45* =dev-lang/rust-bin-1.45* =dev-lang/rust-1.46* =dev-lang/rust-bin-1.46* )",
+			},
+			"dev-lang/rust-bin-1.47.0": {
+				"EAPI": "7",
+			},
+			"dev-lang/rust-bin-1.46.0": {
+				"EAPI": "7",
+			},
+		}
+
+		installed = {
+			"dev-lang/rust-1.46.0": {
+				"EAPI": "7",
+				"SLOT": "stable/1.46",
+				"BDEPEND": "|| ( =dev-lang/rust-1.45* =dev-lang/rust-bin-1.45* =dev-lang/rust-1.46* =dev-lang/rust-bin-1.46* )",
+			},
+		}
+
+		test_cases = (
+			# Test bug 756961, where a circular dependency was reported
+			# when a package would replace its own builtime dependency.
+			# This needs to be tested with and without --update, since
+			# that affects package selection logic significantly,
+			# expecially for packages given as arguments.
+			ResolverPlaygroundTestCase(
+				["=dev-lang/rust-1.46*"],
+				mergelist=["dev-lang/rust-1.46.0"],
+				success=True,
+			),
+			ResolverPlaygroundTestCase(
+				["=dev-lang/rust-1.46*"],
+				options={"--update": True},
+				mergelist=[],
+				success=True,
+			),
+			ResolverPlaygroundTestCase(
+				["=dev-lang/rust-1.46*"],
+				options={"--deep": True, "--update": True},
+				mergelist=[],
+				success=True,
+			),
+			ResolverPlaygroundTestCase(
+				["dev-lang/rust"],
+				mergelist=["dev-lang/rust-1.47.0-r2"],
+				success=True,
+			),
+			ResolverPlaygroundTestCase(
+				["dev-lang/rust"],
+				options={"--update": True},
+				mergelist=["dev-lang/rust-1.47.0-r2"],
+				success=True,
+			),
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options={"--deep": True, "--update": True},
+				mergelist=["dev-lang/rust-1.47.0-r2"],
+				success=True,
+			),
+		)
+
+		world = ["dev-lang/rust"]
+
+		playground = ResolverPlayground(
+			ebuilds=ebuilds, 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()