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

Bug 632026

Summary: sys-apps/portage: redundant package pulled in for virtual || ( foo bar ) || ( bar baz )
Product: Portage Development Reporter: Zac Medico <zmedico>
Component: Core - Interface (emerge)Assignee: Portage team <dev-portage>
Status: RESOLVED FIXED    
Severity: normal CC: esigra, np-hardass
Priority: Normal Keywords: InVCS
Version: unspecified   
Hardware: All   
OS: All   
See Also: https://bugs.gentoo.org/show_bug.cgi?id=264434
https://bugs.gentoo.org/show_bug.cgi?id=141118
https://bugs.gentoo.org/show_bug.cgi?id=639346
https://bugs.gentoo.org/show_bug.cgi?id=645002
https://bugs.gentoo.org/show_bug.cgi?id=645914
https://bugs.gentoo.org/show_bug.cgi?id=649622
https://bugs.gentoo.org/show_bug.cgi?id=701996
Whiteboard:
Package list:
Runtime testing required: ---
Bug Depends on:    
Bug Blocks: 155723, 637452    

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(-)}