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.
(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.
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(-)
*** Bug 703564 has been marked as a duplicate of this bug. ***
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.
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.
Patch posted for review: https://github.com/gentoo/portage/pull/489 https://archives.gentoo.org/gentoo-portage-dev/message/203742b191af991bdb3253c9438fdf2a
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(+)
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(-)
Making this block the latest release (bug 706142) since the fix for bug 705986 is needed for completeness.
