Gentoo Websites Logo
Go to: Gentoo Home Documentation Forums Lists Bugs Planet Store Wiki Get Gentoo!

Bug 703440

Summary: Portage doesn't use explicit || preference to resolve a circular dependency
Product: Portage Development Reporter: Michał Górny <mgorny>
Component: Core - DependenciesAssignee: Portage team <dev-portage>
Status: RESOLVED FIXED    
Severity: normal CC: pacho, sam
Priority: Normal Keywords: InVCS
Version: unspecified   
Hardware: All   
OS: Linux   
See Also: https://bugs.gentoo.org/show_bug.cgi?id=264434
https://bugs.gentoo.org/show_bug.cgi?id=382421
https://bugs.gentoo.org/show_bug.cgi?id=757306
Whiteboard:
Package list:
Runtime testing required: ---
Bug Depends on: 384107    
Bug Blocks: 706142    

Description Michał Górny archtester Gentoo Infrastructure gentoo-dev Security 2019-12-20 21:02:37 UTC
I have three packages: cmake-bootstrap, cmake and jsoncpp.

cmake-bootstrap does not depend on any of the two.  cmake depends on jsoncpp.  jsoncpp depends on || ( cmake-bootstrap cmake ).

Now if I try to 'emerge cmake', I get:

[nomerge       ] dev-util/cmake-3.16.2::gentoo  USE="ncurses test -doc -emacs -qt5" 
[ebuild  N     ]  dev-libs/jsoncpp-1.9.2-r1:0/22::gentoo  USE="test -doc" 0 KiB
[ebuild  N    ~]   dev-util/cmake-3.16.2::gentoo  USE="ncurses test -doc -emacs -qt5" 0 KiB

Total: 2 packages (2 new), Size of downloads: 0 KiB

 * Error: circular dependencies:

(dev-libs/jsoncpp-1.9.2-r1:0/22::gentoo, ebuild scheduled for merge) depends on
 (dev-util/cmake-3.16.2:0/0::gentoo, ebuild scheduled for merge) (buildtime)
  (dev-libs/jsoncpp-1.9.2-r1:0/22::gentoo, ebuild scheduled for merge) (buildtime_slot_op)

 * Note that circular dependencies can often be avoided by temporarily
 * disabling USE flags that trigger optional dependencies.


Emerge entirely ignores cmake-bootstrap package, even though it is listed as the first preference towards satisfying jsoncpp.  The same happens if I try to emerge anything needing cmake.

If I explicitly type 'emerge -1v cmake cmake-bootstrap', it works just fine.

The relevant ebuilds can be found at:
https://github.com/gentoo/gentoo/pull/14066
Comment 1 Larry the Git Cow gentoo-dev 2019-12-21 23:54:27 UTC
The bug has been referenced in the following commit(s):

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

commit 4e83e35467741535463c2f9284dcf21ab4229391
Author:     Zac Medico <zmedico@gentoo.org>
AuthorDate: 2019-12-21 22:55:34 +0000
Commit:     Zac Medico <zmedico@gentoo.org>
CommitDate: 2019-12-21 23:54:15 +0000

    test_circular_choices: add cases for bug 703440
    
    The testCircularJsoncppCmakeBootstrapOrDeps method fails due to circular
    dependencies triggered when it ignores cmake-bootstrap in order to
    eliminate redundant packages.
    
    Meanwhile, the testVirtualCmakeBootstrapUseConditional method solves the
    problem by using a dependency conditional on the bootstrap USE flag.
    
    Bug: https://bugs.gentoo.org/703440
    Signed-off-by: Zac Medico <zmedico@gentoo.org>

 .../tests/resolver/test_circular_choices.py        | 75 ++++++++++++++++++++++
 1 file changed, 75 insertions(+)
Comment 2 Zac Medico gentoo-dev 2019-12-22 00:07:17 UTC
If we use a dependency conditional on the bootstrap USE flag like in the testVirtualCmakeBootstrapUseConditional method, then the emerge error message will look like this:

>  * Error: circular dependencies:
> 
> (dev-libs/jsoncpp-1.9.2:0/0::test_repo, ebuild scheduled for merge) depends on
>  (dev-util/cmake-3.16.2:0/0::test_repo, ebuild scheduled for merge) (buildtime)
>   (dev-libs/jsoncpp-1.9.2:0/0::test_repo, ebuild scheduled for merge) (buildtime_slot_op)
> 
> It might be possible to break this cycle
> by applying the following change:
> - dev-libs/jsoncpp-1.9.2 (Change USE: +bootstrap)
> 
> Note that this change can be reverted, once the package has been installed.
Comment 3 Larry the Git Cow gentoo-dev 2019-12-22 00:28:32 UTC
The bug has been referenced in the following commit(s):

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

commit ae3e58e83b0a3e75990fd2cef04a0c14b3162650
Author:     Zac Medico <zmedico@gentoo.org>
AuthorDate: 2019-12-22 00:24:47 +0000
Commit:     Zac Medico <zmedico@gentoo.org>
CommitDate: 2019-12-22 00:26:17 +0000

    testVirtualCmakeBootstrapUseConditional: split out virtual/cmake
    
    If we split the dependency conditional on the bootstrap USE flag into a
    virtual, then it suffices to rebuild the virtual with USE=-bootstrap
    instead of rebuilding jsoncpp:
    
     * Error: circular dependencies:
    
    (dev-libs/jsoncpp-1.9.2:0/0::test_repo, ebuild scheduled for merge) depends on
     (virtual/cmake-0:0/0::test_repo, ebuild scheduled for merge) (buildtime)
      (dev-util/cmake-3.16.2:0/0::test_repo, ebuild scheduled for merge) (buildtime)
       (dev-libs/jsoncpp-1.9.2:0/0::test_repo, ebuild scheduled for merge) (buildtime_slot_op)
    
    It might be possible to break this cycle
    by applying the following change:
    - virtual/cmake-0 (Change USE: +bootstrap)
    
    Note that this change can be reverted, once the package has been installed.
    
    Bug: https://bugs.gentoo.org/703440
    Signed-off-by: Zac Medico <zmedico@gentoo.org>

 lib/portage/tests/resolver/test_circular_choices.py | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)
Comment 4 Michał Górny archtester Gentoo Infrastructure gentoo-dev Security 2019-12-22 07:26:04 UTC
The whole point of the exercise is to establish a solution that doesn't require the user to do anything and doesn't leave his system in bootstrap state until manually reset to normal state.
Comment 5 Zac Medico gentoo-dev 2019-12-22 07:49:44 UTC
(In reply to Michał Górny from comment #4)
> The whole point of the exercise is to establish a solution that doesn't
> require the user to do anything and doesn't leave his system in bootstrap
> state until manually reset to normal state.

Sure, but how is the user supposed to eliminate the cmake-bootstrap package from their system if not by toggling a USE flag?
Comment 6 Michał Górny archtester Gentoo Infrastructure gentoo-dev Security 2019-12-22 08:23:33 UTC
By --depclean.
Comment 7 Zac Medico gentoo-dev 2019-12-22 08:36:04 UTC
Yes, and --depclean will not eliminate cmake-bootstrap if it's guided by the "explicit || preference" that's supposed to solve the circular dependency.
Comment 8 Michał Górny archtester Gentoo Infrastructure gentoo-dev Security 2019-12-22 08:40:02 UTC
If both packages are installed, preference shouldn't be relevant.  It should be only relevant when no packages are installed, and emerge is trying to figure out what to do.  Trying to outsmart the developer doesn't help.
Comment 9 Zac Medico gentoo-dev 2019-12-22 08:44:05 UTC
So, when --depclean sees this:

  || ( cmake-bootstrap cmake )

How's it supposed to know which package to eliminate?
Comment 10 Michał Górny archtester Gentoo Infrastructure gentoo-dev Security 2019-12-22 08:45:20 UTC
It should eliminate cmake-bootstrap because revdeps of cmake-bootstrap are a (small) subset of revdeps of cmake.

In other words, it can't eliminate cmake because there are packages that depend on cmake only.  It can eliminate cmake-bootstrap because all its revdeps are happy with cmake.
Comment 11 Zac Medico gentoo-dev 2019-12-22 08:48:12 UTC
Ok, so --depclean is supposed to perform a statistical analysis of all the || deps and determine which package to eliminate based on that? Sounds good to me.
Comment 12 Zac Medico gentoo-dev 2019-12-22 08:54:03 UTC
The delayed || deps evaluation from bug 264434 should produce the desired --depclean behavor.
Comment 13 Zac Medico gentoo-dev 2019-12-22 09:16:58 UTC
In lib/portage/tests/resolver/test_merge_order.py we've got this test case that might be sensitive to a change in || preference handling for installation actions:

# Test swapping of providers for a new-style virtual package,
# which relies on delayed evaluation of disjunctive (virtual
# and ||) deps as required to solve bug #264434. Note that
# this behavior is not supported for old-style PROVIDE virtuals,
# as reported in bug #339164.
ResolverPlaygroundTestCase(
	["media-video/libav"],
	success=True,
	mergelist = ['media-video/libav-0.7_pre20110327', '[uninstall]media-video/ffmpeg-0.7_rc1', '!media-video/ffmpeg']),
Comment 14 Michał Górny archtester Gentoo Infrastructure gentoo-dev Security 2019-12-22 09:22:19 UTC
I'd be happy enough if Portage retried different || solutions upon hitting a circular dep.
Comment 15 Zac Medico gentoo-dev 2019-12-22 19:50:40 UTC
(In reply to Michał Górny from comment #14)
> I'd be happy enough if Portage retried different || solutions upon hitting a
> circular dep.

This sort of retry will be an absolute necessity, since bugs of the form "emerge installs package only to have them removed by depclean" will otherwise be introduced. This sort of behavior is desirable only when it solves a circular dependency.
Comment 16 Larry the Git Cow gentoo-dev 2019-12-24 00:57:48 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 17 Larry the Git Cow gentoo-dev 2019-12-24 01:24:31 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(-)
Comment 18 Zac Medico gentoo-dev 2020-02-29 03:03:14 UTC
Making this block the latest release (bug 706142) since the fix for bug 705986 is needed for completeness.