[gentoo-portage-dev] [PATCH] _slot_confict_backtrack: minimize conflict atoms (bug 743631)

[gentoo-portage-dev] [PATCH] _slot_confict_backtrack: minimize conflict atoms (bug 743631)

[Zac Medico]

Prefer choices that minimize conflict atoms, so that choices
which satisfy all parents are preferred. This reduces the
minimum necessary backtrack tries from 21 to 7 for the unit
test related to bug 743115.

Bug: https://bugs.gentoo.org/743115
Bug: https://bugs.gentoo.org/743631
Signed-off-by: Zac Medico <zmedico@gentoo.org>
---
 lib/_emerge/depgraph.py                                     | 6 ++++++
 .../tests/resolver/test_slot_operator_missed_update.py      | 2 +-
 2 files changed, 7 insertions(+), 1 deletion(-)

diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index 3f864aefc..40e7d1325 100644
--- a/lib/_emerge/depgraph.py
+++ b/lib/_emerge/depgraph.py
@@ -1797,6 +1797,12 @@ class depgraph:
 				if parent_atom not in parent_atoms)
 			backtrack_data.append((to_be_masked, conflict_atoms))
 
+		# 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 the
+		# testOverlapSlotConflict method of VirtualMinimizeChildrenTestCase
+		# will not succeed reliably with the default backtrack limit.
+		backtrack_data.sort(key=lambda item: len(item[1]))
 		to_be_masked = backtrack_data[-1][0]
 
 		self._dynamic_config._backtrack_infos.setdefault(
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 fce012f62..1ea701003 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": 25},
+				options={"--update": True, "--deep": True, "--backtrack": 10},
 				success=True,
 				mergelist=[
 					"dev-python/pypy3-7.3.2_rc2_p37-r1",
-- 
2.25.3

[gentoo-portage-dev] Re: [PATCH] _slot_confict_backtrack: minimize conflict atoms (bug 743631)

[Zac Medico]

[-- Attachment #1.1: Type: text/plain, Size: 1144 bytes --]

On 9/19/20 2:40 PM, Zac Medico wrote:
> diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
> index 3f864aefc..40e7d1325 100644
> --- a/lib/_emerge/depgraph.py
> +++ b/lib/_emerge/depgraph.py
> @@ -1797,6 +1797,12 @@ class depgraph:
>  				if parent_atom not in parent_atoms)
>  			backtrack_data.append((to_be_masked, conflict_atoms))
>  
> +		# 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 the
> +		# testOverlapSlotConflict method of VirtualMinimizeChildrenTestCase
> +		# will not succeed reliably with the default backtrack limit.

Updated this comment to indicate that the package version sort sort is actually
needed for deterministic results:

		# 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.

-- 
Thanks,
Zac


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 981 bytes --]