Bug 632026 – sys-apps/portage: redundant package pulled in for virtual || ( foo bar ) || ( bar baz )

• Product: Portage Development
• Status: RESOLVED FIXED

[Description Zac Medico 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 Adam Feldman 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 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 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 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 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 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 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 2017-11-09 13:19:54 UTC]

I have a working patch:

https://github.com/gentoo/portage/pull/226

[Comment 9 Zac Medico 2017-11-12 12:07:00 UTC]

Patch posted for review:

https://archives.gentoo.org/gentoo-portage-dev/message/305b6a9dbc72467a1757a7c108398a78

[Comment 10 Larry the Git Cow 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 <[e-mail]>
AuthorDate: 2017-11-05 22:21:43 +0000
Commit:     Zac Medico <[e-mail]>
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 <[e-mail]>
    Reviewed-by: Alec Warner <[e-mail]>

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