Gentoo Websites Logo
Go to: Gentoo Home Documentation Forums Lists Bugs Planet Store Wiki Get Gentoo!
Bug 743631 - sys-apps/portage: slot conflict backtracking should prefer choices that satisfy all parents
Summary: sys-apps/portage: slot conflict backtracking should prefer choices that satis...
Status: RESOLVED FIXED
Alias: None
Product: Portage Development
Classification: Unclassified
Component: Core - Interface (emerge) (show other bugs)
Hardware: All All
: Normal normal (vote)
Assignee: Portage team
URL:
Whiteboard:
Keywords: InVCS
Depends on:
Blocks: 300071 739718
  Show dependency tree
 
Reported: 2020-09-19 21:29 UTC by Zac Medico
Modified: 2020-11-22 07:23 UTC (History)
1 user (show)

See Also:
Package list:
Runtime testing required: ---


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Zac Medico gentoo-dev 2020-09-19 21:29:54 UTC
The test case for bug 743115 has revealed that the amount of backtracking is significantly reduced if we prefer choices that satisfy all parents when we backtrack for a slot conflict. This patch sorts choices by the number of parents that the choice does not satisfy (referred to as "conflict atoms" in the code), and reduces the required backtracking tries from 21 to 7:

> diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
> index 3f864aefc..4d4f34b73 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",
Comment 2 Larry the Git Cow gentoo-dev 2020-09-21 05:39:18 UTC
The bug has been referenced in the following commit(s):

https://gitweb.gentoo.org/proj/portage.git/commit/?id=f64310749f176f8921b72ce282b4294efe81c3f0

commit f64310749f176f8921b72ce282b4294efe81c3f0
Author:     Zac Medico <zmedico@gentoo.org>
AuthorDate: 2020-09-19 21:32:41 +0000
Commit:     Zac Medico <zmedico@gentoo.org>
CommitDate: 2020-09-20 22:27:32 +0000

    _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 <zmedico@gentoo.org>

 lib/_emerge/depgraph.py                                        | 6 ++++++
 lib/portage/tests/resolver/test_slot_operator_missed_update.py | 2 +-
 2 files changed, 7 insertions(+), 1 deletion(-)
Comment 3 Larry the Git Cow gentoo-dev 2020-09-21 05:59:42 UTC
The bug has been referenced in the following commit(s):

https://gitweb.gentoo.org/repo/gentoo.git/commit/?id=862266358f01efa90c12d182d1f85a3014b80439

commit 862266358f01efa90c12d182d1f85a3014b80439
Author:     Zac Medico <zmedico@gentoo.org>
AuthorDate: 2020-09-21 05:35:06 +0000
Commit:     Zac Medico <zmedico@gentoo.org>
CommitDate: 2020-09-21 05:59:31 +0000

    sys-apps/portage: Bump to version 3.0.8
    
     #404157 emerge: --keep-going support pkg_pretend failures
     #644246 Add mercurial sync support
     #710432 emerge: Enable parallel-fetch during pkg_pretend
     #743115 emerge: Fix slot conflict backtracking to group similar
             missed updates into a single backtracking try
     #743631 emerge: Fix slot conflict backtracking to prefer
             choices that satisfy all dependencies
    
    Bug: https://bugs.gentoo.org/739718
    Bug: https://bugs.gentoo.org/404157
    Bug: https://bugs.gentoo.org/644246
    Bug: https://bugs.gentoo.org/710432
    Bug: https://bugs.gentoo.org/743115
    Bug: https://bugs.gentoo.org/743631
    Package-Manager: Portage-3.0.8, Repoman-3.0.1
    Signed-off-by: Zac Medico <zmedico@gentoo.org>

 sys-apps/portage/Manifest             |   1 +
 sys-apps/portage/portage-3.0.8.ebuild | 267 ++++++++++++++++++++++++++++++++++
 2 files changed, 268 insertions(+)