Gentoo Websites Logo
Go to: Gentoo Home Documentation Forums Lists Bugs Planet Store Wiki Get Gentoo!
Bug 384107 - sys-apps/portage: adjust || preference to solve circular dependencies via backtracking
Summary: sys-apps/portage: adjust || preference to solve circular dependencies via bac...
Status: IN_PROGRESS
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
: 703564 (view as bug list)
Depends on: 264434
Blocks: 155723 300071 382421 701268 703440
  Show dependency tree
 
Reported: 2011-09-22 15:38 UTC by Zac Medico
Modified: 2019-12-24 01:24 UTC (History)
3 users (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 2011-09-22 15:38:18 UTC
The delayed || operator handling (from bug 264434) evaluates dependencies in a somewhat random order. We can optimize it to handle circular dependencies better by scanning the stack for circular dependencies and adding choices that avoid circular dependencies to the graph first, so that those choices will propagate to other similar choices.

For example, consider icedtea which has a build-time dependency on both virtual/jdk and xalan. It is important to evaluate the icedtea build-time virtual/jdk dependency as soon as possible, such that it avoids a circular dependency by selecting icedtea-bin to satisfy virtual/jdk. Once this icedtea-bin choice has been added to the graph, it will be used to optimize later choices, so that icedtea-bin will also be selected to satisfy xalan's build-time virtual/jdk dependency. In this way, choices that avoid direct circular dependencies will propagate to help avoid indirect circular dependencies.
Comment 1 Zac Medico gentoo-dev 2014-11-10 20:12:19 UTC
(In reply to Zac Medico from comment #0)
> We can optimize it to handle circular dependencies
> better by scanning the stack for circular dependencies and adding choices
> that avoid circular dependencies to the graph first, so that those choices
> will propagate to other similar choices.

For optimal performance, _dep_disjunctive_stack will have to be split into two separate stacks: one for those that contain circular deps, and another for those that do not contain circular deps. Then, depgraph._pop_disjunction can prioritize evaluation of the stack containing circular deps.
Comment 2 Larry the Git Cow gentoo-dev 2019-09-12 19:43:27 UTC
The bug has been referenced in the following commit(s):

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

commit 524aa791f28ffcc1df921d8a8a9c111b7e359099
Author:     Zac Medico <zmedico@gentoo.org>
AuthorDate: 2019-09-12 19:40:44 +0000
Commit:     Zac Medico <zmedico@gentoo.org>
CommitDate: 2019-09-12 19:42:37 +0000

    VirtualCircularChoicesTestCase: remove todo flag (bug 384107)
    
    This test passes since the fix for bug 639346 in commit
    09185309aad49b83f29ef94b11318998e520e138.
    
    Bug: https://bugs.gentoo.org/384107
    Bug: https://bugs.gentoo.org/639346
    Signed-off-by: Zac Medico <zmedico@gentoo.org>

 lib/portage/tests/resolver/test_circular_choices.py | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)
Comment 3 Zac Medico gentoo-dev 2019-12-22 21:17:44 UTC
*** Bug 703564 has been marked as a duplicate of this bug. ***
Comment 4 Zac Medico gentoo-dev 2019-12-22 21:19:02 UTC
As discussed in bug 703440, || preference adjustment for circular dependency solving must occur via backtracking, since "emerge installs packages only to have them removed by depclean" behavior is desirable only when it solves a circular dependency.
Comment 5 Zac Medico gentoo-dev 2019-12-22 22:08:47 UTC
This can be handled similarly to the runtime_pkg_mask backtrack parameter, except that we would want mask different child candidates per parent package so that it will apply only where it is necessary to break a dependency cycle. For example, in bug 703440 we would only want to mask cmake as a child candidate of the jsoncpp parent package, while for other parent packages we want to allow cmake as a child candidate. This approach can be generalized to solve bug 407351 as well.
Comment 7 Larry the Git Cow gentoo-dev 2019-12-24 00:57:51 UTC
The bug has been referenced in the following commit(s):

https://gitweb.gentoo.org/repo/gentoo.git/commit/?id=39293f8a4667fce2112792953dbc16f69b9fcb66

commit 39293f8a4667fce2112792953dbc16f69b9fcb66
Author:     Zac Medico <zmedico@gentoo.org>
AuthorDate: 2019-12-24 00:52:27 +0000
Commit:     Zac Medico <zmedico@gentoo.org>
CommitDate: 2019-12-24 00:57:38 +0000

    sys-apps/portage: Bump to version 2.3.83
    
     #384107 adjust || preference to break dependency cycles,
             which solves bug 382421 and bug 703440
     #703348 emerge --with-test-deps: allow circular deps
    
    Bug: https://bugs.gentoo.org/701268
    Bug: https://bugs.gentoo.org/382421
    Bug: https://bugs.gentoo.org/384107
    Bug: https://bugs.gentoo.org/703440
    Bug: https://bugs.gentoo.org/703348
    Package-Manager: Portage-2.3.83, Repoman-2.3.20
    Signed-off-by: Zac Medico <zmedico@gentoo.org>

 sys-apps/portage/Manifest              |   1 +
 sys-apps/portage/portage-2.3.83.ebuild | 276 +++++++++++++++++++++++++++++++++
 2 files changed, 277 insertions(+)
Comment 8 Larry the Git Cow gentoo-dev 2019-12-24 01:24:34 UTC
The bug has been referenced in the following commit(s):

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

commit f78a91e44e3e82008e89f05fe3871e2cb03a8646
Author:     Zac Medico <zmedico@gentoo.org>
AuthorDate: 2019-12-23 05:42:16 +0000
Commit:     Zac Medico <zmedico@gentoo.org>
CommitDate: 2019-12-24 00:40:07 +0000

    backtracking: adjust || preference to break dependency cycles
    
    Store dependency cycle edges as backtracking parameters, and use them
    to adjust || preferences in order to break dependency cycles. This
    extends direct cycle breaking to handle indirect dependency cycles,
    which solves the cmake-bootstrap test case for bug 703440. If any
    cycle(s) remain unsolved by the next backtracking run, then backtracking
    aborts and the cycle(s) are reported as usual.
    
    Note that backtracking is necessary in order to avoid bugs of the form
    "emerge installs packages only to have them removed by depclean", since
    this sort of behavior is desirable only when it eliminates a dependency
    cycle.
    
    Bug: https://bugs.gentoo.org/382421
    Bug: https://bugs.gentoo.org/384107
    Bug: https://bugs.gentoo.org/703440
    Signed-off-by: Zac Medico <zmedico@gentoo.org>

 lib/_emerge/depgraph.py                            | 42 ++++++++++++++++++++--
 lib/_emerge/resolver/backtracking.py               | 11 ++++--
 lib/portage/dep/dep_check.py                       | 10 ++++++
 .../tests/resolver/test_circular_choices.py        | 25 +++++++++++++
 4 files changed, 84 insertions(+), 4 deletions(-)