Gentoo Websites Logo
Go to: Gentoo Home Documentation Forums Lists Bugs Planet Store Wiki Get Gentoo!
Bug 632026 - sys-apps/portage: redundant package pulled in for virtual || ( foo bar ) || ( bar baz )
Summary: sys-apps/portage: redundant package pulled in for virtual || ( foo bar ) || (...
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: 155723 637452
  Show dependency tree
 
Reported: 2017-09-26 01:41 UTC by Zac Medico
Modified: 2018-05-12 19:35 UTC (History)
2 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 2017-09-26 01:41:04 UTC
For a dep string like "|| ( foo bar ) gorp? ( bar baz )" with USE=gorp enabled, both foo and bar will be pulled in, and later foo will be removed by --depclean.
Comment 1 NP-Hardass gentoo-dev 2017-09-26 01:46:47 UTC
As a real life example, the current virtual/wine-0-r5 exhibits this behavior.  


RDEPEND="
    staging? ( || (
        app-emulation/wine-staging[staging]
        app-emulation/wine-any[staging]
    ) )
    d3d9? ( || (
        app-emulation/wine-d3d9[d3d9]
        app-emulation/wine-any[d3d9]
    ) )
    || (
        app-emulation/wine-vanilla[abi_x86_32=,abi_x86_64=]
        app-emulation/wine-staging[abi_x86_32=,abi_x86_64=]
        app-emulation/wine-d3d9[abi_x86_32=,abi_x86_64=]
        app-emulation/wine-any[abi_x86_32=,abi_x86_64=]
    )
    !app-emulation/wine:0"


emerging virtual/wine[staging] will pull in app-emulation/wine-staging and app-emulation/wine-vanilla where it would be satisfied with just wine-staging,   virtual/wine[staging,d3d9] pulls in app-emulation/wine-{vanilla,staging,d3d9} where it would be satisfied with just wine-any.
Comment 2 Zac Medico gentoo-dev 2017-11-04 22:42:00 UTC
It seems like the delayed || deps evaluation from bug 264434 should handle it, so that needs some investigation:

https://gitweb.gentoo.org/proj/portage.git/commit/?id=e6a9e9692a8e98ccf45d90447ae083619b6f47f9
Comment 3 Zac Medico gentoo-dev 2017-11-04 23:50:23 UTC
The code from bug 264434 doesn't handle the virtual/wine deps because there are multiple overlapping || groups.
Comment 4 Zac Medico gentoo-dev 2017-11-04 23:53:39 UTC
When there are multiple overlapping || groups, we want to process the smaller groups first, so that the choices made for the smaller groups will influence the choices made for the larger groups.
Comment 5 Zac Medico gentoo-dev 2017-11-05 00:10:08 UTC
Since virtuals are handled by recursive expansion (bug 141118), the delayed || evaluation implementation from bug 264434 doesn't apply.
Comment 6 Zac Medico gentoo-dev 2017-11-05 01:18:01 UTC
The problem can be solved in the dep_zapdeps function by conversion to disjunctive normal form (DNF). For, example, this:

   || ( foo bar ) || ( bar baz )

Translates to DNF as:

  || ( ( foo bar ) ( foo baz ) ( bar bar ) ( bar baz ) )

And then the ( bar bar ) choice can be preferred since it is satisfied by the fewest number of packages.
Comment 7 Zac Medico gentoo-dev 2017-11-05 20:01:44 UTC
Since DNF results in exponential explosion of the formula, my plan is to only use DNF for that parts of the dependencies that have overlapping atoms.
Comment 8 Zac Medico gentoo-dev 2017-11-09 13:19:54 UTC
I have a working patch:

https://github.com/gentoo/portage/pull/226
Comment 10 Larry the Git Cow gentoo-dev 2017-11-14 04:03:11 UTC
The bug has been referenced in the following commit(s):

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

commit 9fdaf9bdbdf500b7120aa95cb2ca421b931e6cea
Author:     Zac Medico <zmedico@gentoo.org>
AuthorDate: 2017-11-05 22:21:43 +0000
Commit:     Zac Medico <zmedico@gentoo.org>
CommitDate: 2017-11-14 03:35:19 +0000

    dep_check: use DNF to optimize overlapping virtual || deps (bug 632026)
    
    Deps like these:
    
      || ( foo bar ) || ( bar baz )
    
    Translate to disjunctive normal form (DNF):
    
      || ( ( foo bar ) ( foo baz ) ( bar bar ) ( bar baz ) )
    
    Using DNF, if none of the packages are currently installed,
    then the ( bar bar ) choice will be automatically preferred
    since it is satisfied by the fewest number of packages.
    If the ( foo baz ) choice is already satisfied, then that
    choice will be preferred instead.
    
    Since DNF results in exponential explosion of the formula,
    only use DNF for the parts of the dependencies that have
    overlapping atoms.
    
    In order to simplify the implementation of the dnf_convert
    function, this patch also fixes _expand_new_virtuals to
    normalize results in the same way as use_reduce (with no
    redundant nested lists).
    
    Bug: https://bugs.gentoo.org/632026
    Reviewed-by: Manuel Rüger <mrueg@gentoo.org>
    Reviewed-by: Alec Warner <antarus@gentoo.org>

 pym/portage/dep/_dnf.py                            |  90 +++++++++++++
 pym/portage/dep/dep_check.py                       | 136 ++++++++++++++++++-
 pym/portage/tests/dep/test_dnf_convert.py          |  48 +++++++
 pym/portage/tests/dep/test_overlap_dnf.py          |  28 ++++
 .../resolver/test_virtual_minimize_children.py     | 145 +++++++++++++++++++++
 5 files changed, 440 insertions(+), 7 deletions(-)}