From f64310749f176f8921b72ce282b4294efe81c3f0 Mon Sep 17 00:00:00 2001 From: Zac Medico Date: Sat, 19 Sep 2020 14:32:41 -0700 Subject: _slot_confict_backtrack: minimize conflict atoms (bug 743631) 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 --- lib/_emerge/depgraph.py | 6 ++++++ lib/portage/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..7281d8692 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 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] 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", -- cgit v1.2.3