[gentoo-portage-dev] [PATCH] _slot_confict_backtrack: group similar missed updates (bug 743115)

[Zac Medico <zmedico@gentoo.org>]

When a slot conflict occurs due to a missed update, and some other
similar update(s) are available, add the similar update(s) to the
runtime package mask for the same backtracking choice. This reduces
minimum number of backtrack tries required to solve the test case
for bug 743115 from 7 to 4, where the difference of 3 corresponds
to the number of other similar setuptools updates available.

Bug: https://bugs.gentoo.org/743115
Signed-off-by: Zac Medico <zmedico@gentoo.org>
---
 lib/_emerge/depgraph.py                       | 25 ++++++++++++++++---
 lib/_emerge/resolver/backtracking.py          |  7 +++---
 .../test_slot_operator_missed_update.py       |  2 +-
 3 files changed, 26 insertions(+), 8 deletions(-)

diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index 7281d8692..2a840b2ca 100644
--- a/lib/_emerge/depgraph.py
+++ b/lib/_emerge/depgraph.py
@@ -1795,15 +1795,32 @@ class depgraph:
 				self._dynamic_config._parent_atoms.get(to_be_masked, set())
 			conflict_atoms = set(parent_atom for parent_atom in all_parents \
 				if parent_atom not in parent_atoms)
-			backtrack_data.append((to_be_masked, conflict_atoms))
+
+			similar_pkgs = []
+			if conflict_atoms:
+				# If the conflict has been triggered by a missed update, then
+				# we can avoid excessive backtracking if we detect similar missed
+				# updates and mask them as part of the same backtracking choice.
+				for similar_pkg in self._iter_similar_available(to_be_masked, slot_atom):
+					if similar_pkg in conflict_pkgs:
+						continue
+					similar_conflict_atoms = []
+					for parent_atom in conflict_atoms:
+						parent, atom = parent_atom
+						if not atom.match(similar_pkg):
+							similar_conflict_atoms.append(parent_atom)
+					if similar_conflict_atoms:
+						similar_pkgs.append((similar_pkg, set(similar_conflict_atoms)))
+			similar_pkgs.append((to_be_masked, conflict_atoms))
+			backtrack_data.append(tuple(similar_pkgs))
 
 		# Prefer choices that minimize conflict atoms. This is intended
 		# to take precedence over the earlier package version sort. The
 		# package version sort is still needed or else choices for the
 		# testOverlapSlotConflict method of VirtualMinimizeChildrenTestCase
 		# become non-deterministic.
-		backtrack_data.sort(key=lambda item: len(item[1]))
-		to_be_masked = backtrack_data[-1][0]
+		backtrack_data.sort(key=lambda similar_pkgs: max(len(item[1]) for item in similar_pkgs))
+		to_be_masked = [item[0] for item in backtrack_data[-1]]
 
 		self._dynamic_config._backtrack_infos.setdefault(
 			"slot conflict", []).append(backtrack_data)
@@ -1814,7 +1831,7 @@ class depgraph:
 				"",
 				"backtracking due to slot conflict:",
 				"   first package:  %s" % existing_node,
-				"  package to mask: %s" % to_be_masked,
+				"  package(s) to mask: %s" % str(to_be_masked),
 				"      slot: %s" % slot_atom,
 				"   parents: %s" % ", ".join(
 					"(%s, '%s')" % (ppkg, atom) for ppkg, atom in all_parents
diff --git a/lib/_emerge/resolver/backtracking.py b/lib/_emerge/resolver/backtracking.py
index bc3fb3206..ca94623ac 100644
--- a/lib/_emerge/resolver/backtracking.py
+++ b/lib/_emerge/resolver/backtracking.py
@@ -166,13 +166,14 @@ class Backtracker:
 		self._feedback_slot_conflict(conflicts_data[0])
 
 	def _feedback_slot_conflict(self, conflict_data):
-		for pkg, parent_atoms in conflict_data:
+		for similar_pkgs in conflict_data:
 			new_node = copy.deepcopy(self._current_node)
 			new_node.depth += 1
 			new_node.mask_steps += 1
 			new_node.terminal = False
-			new_node.parameter.runtime_pkg_mask.setdefault(
-				pkg, {})["slot conflict"] = parent_atoms
+			for pkg, parent_atoms in similar_pkgs:
+				new_node.parameter.runtime_pkg_mask.setdefault(
+					pkg, {})["slot conflict"] = parent_atoms
 			self._add(new_node)
 
 
diff --git a/lib/portage/tests/resolver/test_slot_operator_missed_update.py b/lib/portage/tests/resolver/test_slot_operator_missed_update.py
index 1ea701003..efad70615 100644
--- a/lib/portage/tests/resolver/test_slot_operator_missed_update.py
+++ b/lib/portage/tests/resolver/test_slot_operator_missed_update.py
@@ -90,7 +90,7 @@ class BacktrackMissedUpdateTestCase(TestCase):
 			# Bug 743115: missed updates trigger excessive backtracking
 			ResolverPlaygroundTestCase(
 				[">=dev-python/pypy3-7.3.2_rc", "@world"],
-				options={"--update": True, "--deep": True, "--backtrack": 10},
+				options={"--update": True, "--deep": True, "--backtrack": 4},
 				success=True,
 				mergelist=[
 					"dev-python/pypy3-7.3.2_rc2_p37-r1",
-- 
2.25.3