* [gentoo-commits] proj/portage:master commit in: pym/portage/tests/dep/, pym/portage/dep/, pym/portage/tests/resolver/
@ 2017-11-14 4:03 Zac Medico
0 siblings, 0 replies; 2+ messages in thread
From: Zac Medico @ 2017-11-14 4:03 UTC (permalink / raw
To: gentoo-commits
commit: 9fdaf9bdbdf500b7120aa95cb2ca421b931e6cea
Author: Zac Medico <zmedico <AT> gentoo <DOT> org>
AuthorDate: Sun Nov 5 22:21:43 2017 +0000
Commit: Zac Medico <zmedico <AT> gentoo <DOT> org>
CommitDate: Tue Nov 14 03:35:19 2017 +0000
URL: https://gitweb.gentoo.org/proj/portage.git/commit/?id=9fdaf9bd
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 <AT> gentoo.org>
Reviewed-by: Alec Warner <antarus <AT> 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(-)
diff --git a/pym/portage/dep/_dnf.py b/pym/portage/dep/_dnf.py
new file mode 100644
index 000000000..59657fd6a
--- /dev/null
+++ b/pym/portage/dep/_dnf.py
@@ -0,0 +1,90 @@
+# Copyright 2017 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from __future__ import unicode_literals
+
+import itertools
+
+
+def dnf_convert(dep_struct):
+ """
+ Convert dep_struct to disjunctive normal form (DNF), where dep_struct
+ is either a conjunction or disjunction of the form produced by
+ use_reduce(opconvert=True).
+ """
+ # Normalize input to have a top-level conjunction.
+ if isinstance(dep_struct, list):
+ if dep_struct and dep_struct[0] == '||':
+ dep_struct = [dep_struct]
+ else:
+ dep_struct = [dep_struct]
+
+ conjunction = []
+ disjunctions = []
+
+ for x in dep_struct:
+ if isinstance (x, list):
+ assert x and x[0] == '||', \
+ 'Normalization error, nested conjunction found in %s' % (dep_struct,)
+ if any(isinstance(element, list) for element in x):
+ x_dnf = ['||']
+ for element in x[1:]:
+ if isinstance(element, list):
+ # Due to normalization, a disjunction must not be
+ # nested directly in another disjunction, so this
+ # must be a conjunction.
+ assert element, 'Normalization error, empty conjunction found in %s' % (x,)
+ assert element[0] != '||', \
+ 'Normalization error, nested disjunction found in %s' % (x,)
+ element = dnf_convert(element)
+ if contains_disjunction(element):
+ assert (len(element) == 1 and
+ element[0] and element[0][0] == '||'), \
+ 'Normalization error, expected single disjunction in %s' % (element,)
+ x_dnf.extend(element[0][1:])
+ else:
+ x_dnf.append(element)
+ else:
+ x_dnf.append(element)
+ x = x_dnf
+ disjunctions.append(x)
+ else:
+ conjunction.append(x)
+
+ if disjunctions and (conjunction or len(disjunctions) > 1):
+ dnf_form = ['||']
+ for x in itertools.product(*[x[1:] for x in disjunctions]):
+ normalized = conjunction[:]
+ for element in x:
+ if isinstance(element, list):
+ normalized.extend(element)
+ else:
+ normalized.append(element)
+ dnf_form.append(normalized)
+ result = [dnf_form]
+ else:
+ result = conjunction + disjunctions
+
+ return result
+
+
+def contains_disjunction(dep_struct):
+ """
+ Search for a disjunction contained in dep_struct, where dep_struct
+ is either a conjunction or disjunction of the form produced by
+ use_reduce(opconvert=True). If dep_struct is a disjunction, then
+ this only returns True if there is a nested disjunction. Due to
+ normalization, recursion is only needed when dep_struct is a
+ disjunction containing a conjunction. If dep_struct is a conjunction,
+ then it is assumed that normalization has elevated any nested
+ disjunctions to the top-level.
+ """
+ is_disjunction = dep_struct and dep_struct[0] == '||'
+ for x in dep_struct:
+ if isinstance(x, list):
+ assert x, 'Normalization error, empty conjunction found in %s' % (dep_struct,)
+ if x[0] == '||':
+ return True
+ elif is_disjunction and contains_disjunction(x):
+ return True
+ return False
diff --git a/pym/portage/dep/dep_check.py b/pym/portage/dep/dep_check.py
index b33f7e5db..2bb9dc339 100644
--- a/pym/portage/dep/dep_check.py
+++ b/pym/portage/dep/dep_check.py
@@ -6,14 +6,20 @@ from __future__ import unicode_literals
__all__ = ['dep_check', 'dep_eval', 'dep_wordreduce', 'dep_zapdeps']
import collections
+import itertools
import logging
import operator
import portage
from portage.dep import Atom, match_from_list, use_reduce
+from portage.dep._dnf import (
+ dnf_convert as _dnf_convert,
+ contains_disjunction as _contains_disjunction,
+)
from portage.exception import InvalidDependString, ParseError
from portage.localization import _
from portage.util import writemsg, writemsg_level
+from portage.util.digraph import digraph
from portage.util.SlotObject import SlotObject
from portage.versions import vercmp, _pkg_str
@@ -28,7 +34,11 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/",
atom because it wouldn't necessarily make sense to block all the components
of a compound virtual. When more than one new-style virtual is matched,
the matches are sorted from highest to lowest versions and the atom is
- expanded to || ( highest match ... lowest match )."""
+ expanded to || ( highest match ... lowest match ).
+
+ The result is normalized in the same way as use_reduce, having a top-level
+ conjuction, and no redundant nested lists.
+ """
newsplit = []
mytrees = trees[myroot]
portdb = mytrees["porttree"].dbapi
@@ -54,14 +64,38 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/",
portdb = trees[myroot]["bintree"].dbapi
pprovideddict = mysettings.pprovideddict
myuse = kwargs["myuse"]
+ is_disjunction = mysplit and mysplit[0] == '||'
for x in mysplit:
if x == "||":
newsplit.append(x)
continue
elif isinstance(x, list):
- newsplit.append(_expand_new_virtuals(x, edebug, mydbapi,
+ assert x, 'Normalization error, empty conjunction found in %s' % (mysplit,)
+ if is_disjunction:
+ assert x[0] != '||', \
+ 'Normalization error, nested disjunction found in %s' % (mysplit,)
+ else:
+ assert x[0] == '||', \
+ 'Normalization error, nested conjunction found in %s' % (mysplit,)
+ x_exp = _expand_new_virtuals(x, edebug, mydbapi,
mysettings, myroot=myroot, trees=trees, use_mask=use_mask,
- use_force=use_force, **kwargs))
+ use_force=use_force, **kwargs)
+ if is_disjunction:
+ if len(x_exp) == 1:
+ x = x_exp[0]
+ if isinstance(x, list):
+ # Due to normalization, a conjunction must not be
+ # nested directly in another conjunction, so this
+ # must be a disjunction.
+ assert x and x[0] == '||', \
+ 'Normalization error, nested conjunction found in %s' % (x_exp,)
+ newsplit.extend(x[1:])
+ else:
+ newsplit.append(x)
+ else:
+ newsplit.append(x_exp)
+ else:
+ newsplit.extend(x_exp)
continue
if not isinstance(x, Atom):
@@ -101,6 +135,8 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/",
a.append(Atom(x.replace(x.cp, y.cp, 1)))
if not a:
newsplit.append(x)
+ elif is_disjunction:
+ newsplit.extend(a)
elif len(a) == 1:
newsplit.append(a[0])
else:
@@ -218,11 +254,18 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/",
newsplit.append(x)
if atom_graph is not None:
atom_graph.add((x, id(x)), graph_parent)
+ elif is_disjunction:
+ newsplit.extend(a)
elif len(a) == 1:
- newsplit.append(a[0])
+ newsplit.extend(a[0])
else:
newsplit.append(['||'] + a)
+ # For consistency with related functions like use_reduce, always
+ # normalize the result to have a top-level conjunction.
+ if is_disjunction:
+ newsplit = [newsplit]
+
return newsplit
def dep_eval(deplist):
@@ -612,9 +655,9 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None):
for choices in choice_bins:
if len(choices) < 2:
continue
- # Prefer choices with all_installed_slots for bug #480736.
- choices.sort(key=operator.attrgetter('all_installed_slots'),
- reverse=True)
+ # Prefer choices with all_installed_slots for bug #480736, and
+ # choices with a smaller number of packages for bug #632026.
+ choices.sort(key=lambda x: (not x.all_installed_slots, len(x.slot_map)))
for choice_1 in choices[1:]:
cps = set(choice_1.cp_map)
for choice_2 in choices:
@@ -741,6 +784,9 @@ def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None,
except ParseError as e:
return [0, "%s" % (e,)]
+ if mysettings.local_config: # if not repoman
+ mysplit = _overlap_dnf(mysplit)
+
mysplit2 = dep_wordreduce(mysplit,
mysettings, mydbapi, mode, use_cache=use_cache)
if mysplit2 is None:
@@ -755,6 +801,82 @@ def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None,
return [1, selected_atoms]
+
+def _overlap_dnf(dep_struct):
+ """
+ Combine overlapping || groups using disjunctive normal form (DNF), in
+ order to minimize the number of packages chosen to satisfy cases like
+ "|| ( foo bar ) || ( bar baz )" as in bug #632026. Non-overlapping
+ groups are excluded from the conversion, since DNF leads to exponential
+ explosion of the formula.
+ """
+ if not _contains_disjunction(dep_struct):
+ return dep_struct
+
+ # map atom.cp to disjunctions
+ cp_map = collections.defaultdict(list)
+ # graph atom.cp, with edges connecting atoms in the same disjunction
+ overlap_graph = digraph()
+ # map id(disjunction) to index in dep_struct, for deterministic output
+ order_map = {}
+ order_key = lambda x: order_map[id(x)]
+ result = []
+ for i, x in enumerate(dep_struct):
+ if isinstance(x, list):
+ assert x and x[0] == '||', \
+ 'Normalization error, nested conjunction found in %s' % (dep_struct,)
+ order_map[id(x)] = i
+ prev_cp = None
+ for atom in _iter_flatten(x):
+ if isinstance(atom, Atom) and not atom.blocker:
+ cp_map[atom.cp].append(x)
+ overlap_graph.add(atom.cp, parent=prev_cp)
+ prev_cp = atom.cp
+ if prev_cp is None: # only contains blockers
+ result.append(x)
+ else:
+ result.append(x)
+
+ # group together disjunctions having atom.cp overlap
+ traversed = set()
+ for cp in overlap_graph:
+ if cp in traversed:
+ continue
+ disjunctions = {}
+ stack = [cp]
+ while stack:
+ cp = stack.pop()
+ traversed.add(cp)
+ for x in cp_map[cp]:
+ disjunctions[id(x)] = x
+ for other_cp in itertools.chain(overlap_graph.child_nodes(cp),
+ overlap_graph.parent_nodes(cp)):
+ if other_cp not in traversed:
+ stack.append(other_cp)
+
+ if len(disjunctions) > 1:
+ # convert overlapping disjunctions to DNF
+ result.extend(_dnf_convert(
+ sorted(disjunctions.values(), key=order_key)))
+ else:
+ # pass through non-overlapping disjunctions
+ result.append(disjunctions.popitem()[1])
+
+ return result
+
+
+def _iter_flatten(dep_struct):
+ """
+ Yield nested elements of dep_struct.
+ """
+ for x in dep_struct:
+ if isinstance(x, list):
+ for x in _iter_flatten(x):
+ yield x
+ else:
+ yield x
+
+
def dep_wordreduce(mydeplist,mysettings,mydbapi,mode,use_cache=1):
"Reduces the deplist to ones and zeros"
deplist=mydeplist[:]
diff --git a/pym/portage/tests/dep/test_dnf_convert.py b/pym/portage/tests/dep/test_dnf_convert.py
new file mode 100644
index 000000000..b92778d4a
--- /dev/null
+++ b/pym/portage/tests/dep/test_dnf_convert.py
@@ -0,0 +1,48 @@
+# Copyright 2017 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.dep import use_reduce
+from portage.dep._dnf import dnf_convert
+
+class DNFConvertTestCase(TestCase):
+
+ def testDNFConvert(self):
+
+ test_cases = (
+ (
+ '|| ( A B ) || ( C D )',
+ [['||', ['A', 'C'], ['A', 'D'], ['B', 'C'], ['B', 'D']]],
+ ),
+ (
+ '|| ( A B ) || ( B C )',
+ [['||', ['A', 'B'], ['A', 'C'], ['B', 'B'], ['B', 'C']]],
+ ),
+ (
+ '|| ( A ( B C D ) )',
+ [['||', 'A', ['B', 'C', 'D']]],
+ ),
+ (
+ '|| ( A ( B C D ) ) E',
+ [['||', ['E', 'A'], ['E', 'B', 'C', 'D']]],
+ ),
+ (
+ '|| ( A ( B C ) ) || ( D E ) F',
+ [['||', ['F', 'A', 'D'], ['F', 'A', 'E'], ['F', 'B', 'C', 'D'], ['F', 'B', 'C', 'E']]],
+ ),
+ (
+ '|| ( A ( B C || ( D E ) ) ( F G ) H )',
+ [['||', 'A', ['B', 'C', 'D'], ['B', 'C', 'E'], ['F', 'G'], 'H']],
+ ),
+ (
+ '|| ( A ( B C || ( D E ) ) F )',
+ [['||', 'A', ['B', 'C', 'D'], ['B', 'C', 'E'], 'F']],
+ ),
+ (
+ '|| ( A ( C || ( D E ) || ( F G ) ) H )',
+ [['||', 'A', ['C', 'D', 'F'], ['C', 'D', 'G'], ['C', 'E', 'F'], ['C', 'E', 'G'], 'H']],
+ ),
+ )
+
+ for dep_str, result in test_cases:
+ self.assertEqual(dnf_convert(use_reduce(dep_str, opconvert=True)), result)
diff --git a/pym/portage/tests/dep/test_overlap_dnf.py b/pym/portage/tests/dep/test_overlap_dnf.py
new file mode 100644
index 000000000..79b3e8e46
--- /dev/null
+++ b/pym/portage/tests/dep/test_overlap_dnf.py
@@ -0,0 +1,28 @@
+# Copyright 2017 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.dep import Atom, use_reduce
+from portage.dep.dep_check import _overlap_dnf
+
+class OverlapDNFTestCase(TestCase):
+
+ def testOverlapDNF(self):
+
+ test_cases = (
+ (
+ '|| ( cat/A cat/B ) cat/E || ( cat/C cat/D )',
+ ['cat/E', ['||', 'cat/A', 'cat/B'], ['||', 'cat/C', 'cat/D']],
+ ),
+ (
+ '|| ( cat/A cat/B ) cat/D || ( cat/B cat/C )',
+ ['cat/D', ['||', ['cat/A', 'cat/B'], ['cat/A', 'cat/C'], ['cat/B', 'cat/B'], ['cat/B', 'cat/C']]],
+ ),
+ (
+ '|| ( cat/A cat/B ) || ( cat/C cat/D ) || ( ( cat/B cat/E ) cat/F )',
+ [['||', ['cat/A', 'cat/B', 'cat/E'], ['cat/A', 'cat/F'], ['cat/B', 'cat/B', 'cat/E'], ['cat/B', 'cat/F']], ['||', 'cat/C', 'cat/D']],
+ ),
+ )
+
+ for dep_str, result in test_cases:
+ self.assertEqual(_overlap_dnf(use_reduce(dep_str, token_class=Atom, opconvert=True)), result)
diff --git a/pym/portage/tests/resolver/test_virtual_minimize_children.py b/pym/portage/tests/resolver/test_virtual_minimize_children.py
new file mode 100644
index 000000000..83ae34e77
--- /dev/null
+++ b/pym/portage/tests/resolver/test_virtual_minimize_children.py
@@ -0,0 +1,145 @@
+# Copyright 2017 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (
+ ResolverPlayground,
+ ResolverPlaygroundTestCase,
+)
+
+class VirtualMinimizeChildrenTestCase(TestCase):
+
+ def testVirtualMinimizeChildren(self):
+ ebuilds = {
+ 'app-misc/bar-1': {
+ 'EAPI': '6',
+ 'RDEPEND': 'virtual/foo'
+ },
+ 'virtual/foo-1': {
+ 'EAPI': '6',
+ 'RDEPEND': '|| ( app-misc/A app-misc/B ) || ( app-misc/B app-misc/C )'
+ },
+ 'app-misc/A-1': {
+ 'EAPI': '6',
+ },
+ 'app-misc/B-1': {
+ 'EAPI': '6',
+ },
+ 'app-misc/C-1': {
+ 'EAPI': '6',
+ },
+ }
+
+ test_cases = (
+ # Test bug 632026, where we want to minimize the number of
+ # packages chosen to satisfy overlapping || deps like
+ # "|| ( foo bar ) || ( bar baz )".
+ ResolverPlaygroundTestCase(
+ ['app-misc/bar'],
+ success=True,
+ mergelist=[
+ 'app-misc/B-1',
+ 'virtual/foo-1',
+ 'app-misc/bar-1',
+ ],
+ ),
+ )
+
+ playground = ResolverPlayground(debug=False,
+ ebuilds=ebuilds)
+
+ try:
+ for test_case in test_cases:
+ playground.run_TestCase(test_case)
+ self.assertEqual(test_case.test_success, True,
+ test_case.fail_msg)
+ finally:
+ playground.debug = False
+ playground.cleanup()
+
+ # If app-misc/A and app-misc/C are installed then
+ # that choice should be preferred over app-misc/B.
+ installed = {
+ 'app-misc/A-1': {
+ 'EAPI': '6',
+ },
+ 'app-misc/C-1': {
+ 'EAPI': '6',
+ },
+ }
+
+ test_cases = (
+ ResolverPlaygroundTestCase(
+ ['app-misc/bar'],
+ success=True,
+ mergelist=[
+ 'virtual/foo-1',
+ 'app-misc/bar-1',
+ ],
+ ),
+ )
+
+ playground = ResolverPlayground(debug=False,
+ ebuilds=ebuilds, installed=installed)
+
+ try:
+ for test_case in test_cases:
+ playground.run_TestCase(test_case)
+ self.assertEqual(test_case.test_success, True,
+ test_case.fail_msg)
+ finally:
+ playground.debug = False
+ playground.cleanup()
+
+ def testOverlapSlotConflict(self):
+ ebuilds = {
+ 'app-misc/bar-1': {
+ 'EAPI': '6',
+ 'RDEPEND': 'virtual/foo'
+ },
+ 'virtual/foo-1': {
+ 'EAPI': '6',
+ 'RDEPEND': '|| ( app-misc/A >=app-misc/B-2 ) || ( <app-misc/B-2 app-misc/C )'
+ },
+ 'app-misc/A-1': {
+ 'EAPI': '6',
+ },
+ 'app-misc/B-2': {
+ 'EAPI': '6',
+ },
+ 'app-misc/B-1': {
+ 'EAPI': '6',
+ },
+ 'app-misc/C-1': {
+ 'EAPI': '6',
+ },
+ }
+
+ test_cases = (
+ # Here the ( >=app-misc/B-2 <app-misc/B-2 ) choice is not satisfiable.
+ ResolverPlaygroundTestCase(
+ ['app-misc/bar'],
+ success=True,
+ ambiguous_merge_order=True,
+ mergelist=[
+ (
+ 'app-misc/C-1',
+ 'app-misc/A-1',
+ ),
+ 'virtual/foo-1',
+ 'app-misc/bar-1',
+ ]
+ ),
+ )
+
+ playground = ResolverPlayground(debug=False,
+ ebuilds=ebuilds)
+
+ try:
+ for test_case in test_cases:
+ playground.run_TestCase(test_case)
+ self.assertEqual(test_case.test_success, True,
+ test_case.fail_msg)
+ finally:
+ playground.debug = False
+ playground.cleanup()
^ permalink raw reply related [flat|nested] 2+ messages in thread
* [gentoo-commits] proj/portage:master commit in: pym/portage/tests/dep/, pym/portage/dep/, pym/portage/tests/resolver/
@ 2018-02-03 0:01 Zac Medico
0 siblings, 0 replies; 2+ messages in thread
From: Zac Medico @ 2018-02-03 0:01 UTC (permalink / raw
To: gentoo-commits
commit: 0ddfb5802d98c618bd20742be49a520c9a54b394
Author: Zac Medico <zmedico <AT> gentoo <DOT> org>
AuthorDate: Fri Feb 2 06:08:59 2018 +0000
Commit: Zac Medico <zmedico <AT> gentoo <DOT> org>
CommitDate: Fri Feb 2 12:01:25 2018 +0000
URL: https://gitweb.gentoo.org/proj/portage.git/commit/?id=0ddfb580
dep_zapdeps: sort by new_slot_count for DNF only (bug 645002)
Sorting of choices by new_slot_count causes the order of
choices specified in the ebuild to be discarded, and
new_slot_count may have variance related to the order that
packages are added to the graph. This variance can
contribute to outcomes that appear to be random, like when
catalyst stage1 builds sometimes pull in paludis to
satisfy perl-cleaner dependencies.
Meanwhile, the order specified in the ebuild has no
variance, and the preferences that it specifies can serve
as a crucial sources of guidance. Therefore, take advantage
of the order specified in the ebuild whenever possible, and
use new_slot_count only when it is needed to select optimal
choices from DNF (as in bug 632026).
This fixes random outcomes in the unit test for bug 645002.
Previously, the unit test pulled in paludis randomly unless
portage-utils was added to the arguments. With this patch,
the portage-utils argument is no longer needed for the unit
test to succeed consistently. The perl-cleaner dependencies
do not have any overlapping || deps, so the DNF conversion
and new_slot_count sorting do not apply, and the first
choice is preferred regardless of the number of slots that
it pulls in:
|| (
( sys-apps/portage app-portage/portage-utils )
sys-apps/pkgcore
sys-apps/paludis
)
The _overlap_dnf function now returns the argument object
when there is no overlap, so OverlapDNFTestCase has to be
adjusted to account for this.
Bug: https://bugs.gentoo.org/645002
Fixes: 9fdaf9bdbdf5 ("dep_check: use DNF to optimize overlapping virtual || deps (bug 632026)")
pym/portage/dep/dep_check.py | 49 ++++++++++++++++++----
pym/portage/tests/dep/test_overlap_dnf.py | 2 +-
.../resolver/test_virtual_minimize_children.py | 12 +++---
3 files changed, 47 insertions(+), 16 deletions(-)
diff --git a/pym/portage/dep/dep_check.py b/pym/portage/dep/dep_check.py
index 7e5a3186e..2896e2389 100644
--- a/pym/portage/dep/dep_check.py
+++ b/pym/portage/dep/dep_check.py
@@ -298,7 +298,8 @@ class _dep_choice(SlotObject):
__slots__ = ('atoms', 'slot_map', 'cp_map', 'all_available',
'all_installed_slots', 'new_slot_count')
-def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None):
+def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None,
+ minimize_slots=False):
"""
Takes an unreduced and reduced deplist and removes satisfied dependencies.
Returned deplist contains steps that must be taken to satisfy dependencies.
@@ -314,7 +315,8 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None):
for x, satisfied in zip(unreduced, reduced):
if isinstance(x, list):
unresolved += dep_zapdeps(x, satisfied, myroot,
- use_binaries=use_binaries, trees=trees)
+ use_binaries=use_binaries, trees=trees,
+ minimize_slots=minimize_slots)
elif not satisfied:
unresolved.append(x)
return unresolved
@@ -386,7 +388,8 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None):
for x, satisfied in zip(deps, satisfieds):
if isinstance(x, list):
atoms = dep_zapdeps(x, satisfied, myroot,
- use_binaries=use_binaries, trees=trees)
+ use_binaries=use_binaries, trees=trees,
+ minimize_slots=minimize_slots)
else:
atoms = [x]
if vardb is None:
@@ -663,9 +666,28 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None):
for choices in choice_bins:
if len(choices) < 2:
continue
- # Prefer choices with all_installed_slots for bug #480736, and
- # choices with a smaller number of new slots for bug #632026.
- choices.sort(key=lambda x: (not x.all_installed_slots, x.new_slot_count))
+
+ sort_keys = []
+ # Prefer choices with all_installed_slots for bug #480736.
+ sort_keys.append(lambda x: not x.all_installed_slots)
+
+ if minimize_slots:
+ # Prefer choices having fewer new slots. When used with DNF form,
+ # this can eliminate unecessary packages that depclean would
+ # ultimately eliminate (see bug 632026). Only use this behavior
+ # when deemed necessary by the caller, since this will discard the
+ # order specified in the ebuild, and the preferences specified
+ # there can serve as a crucial sources of guidance (see bug 645002).
+
+ # NOTE: Under some conditions, new_slot_count value may have some
+ # variance from one calculation to the next because it depends on
+ # the order that packages are added to the graph. This variance can
+ # contribute to outcomes that appear to be random. Meanwhile,
+ # the order specified in the ebuild is without variance, so it
+ # does not have this problem.
+ sort_keys.append(lambda x: x.new_slot_count)
+
+ choices.sort(key=lambda x: tuple(f(x) for f in sort_keys))
for choice_1 in choices[1:]:
cps = set(choice_1.cp_map)
for choice_2 in choices:
@@ -792,8 +814,11 @@ def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None,
except ParseError as e:
return [0, "%s" % (e,)]
+ dnf = False
if mysettings.local_config: # if not repoman
+ orig_split = mysplit
mysplit = _overlap_dnf(mysplit)
+ dnf = mysplit is not orig_split
mysplit2 = dep_wordreduce(mysplit,
mysettings, mydbapi, mode, use_cache=use_cache)
@@ -805,7 +830,7 @@ def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None,
writemsg("mysplit2: %s\n" % (mysplit2), 1)
selected_atoms = dep_zapdeps(mysplit, mysplit2, myroot,
- use_binaries=use_binaries, trees=trees)
+ use_binaries=use_binaries, trees=trees, minimize_slots=dnf)
return [1, selected_atoms]
@@ -817,6 +842,12 @@ def _overlap_dnf(dep_struct):
"|| ( foo bar ) || ( bar baz )" as in bug #632026. Non-overlapping
groups are excluded from the conversion, since DNF leads to exponential
explosion of the formula.
+
+ When dep_struct does not contain any overlapping groups, no DNF
+ conversion will be performed, and dep_struct will be returned as-is.
+ Callers can detect this case by checking if the returned object has
+ the same identity as dep_struct. If the identity is different, then
+ DNF conversion was performed.
"""
if not _contains_disjunction(dep_struct):
return dep_struct
@@ -847,6 +878,7 @@ def _overlap_dnf(dep_struct):
# group together disjunctions having atom.cp overlap
traversed = set()
+ overlap = False
for cp in overlap_graph:
if cp in traversed:
continue
@@ -863,6 +895,7 @@ def _overlap_dnf(dep_struct):
stack.append(other_cp)
if len(disjunctions) > 1:
+ overlap = True
# convert overlapping disjunctions to DNF
result.extend(_dnf_convert(
sorted(disjunctions.values(), key=order_key)))
@@ -870,7 +903,7 @@ def _overlap_dnf(dep_struct):
# pass through non-overlapping disjunctions
result.append(disjunctions.popitem()[1])
- return result
+ return result if overlap else dep_struct
def _iter_flatten(dep_struct):
diff --git a/pym/portage/tests/dep/test_overlap_dnf.py b/pym/portage/tests/dep/test_overlap_dnf.py
index 79b3e8e46..ee48e5556 100644
--- a/pym/portage/tests/dep/test_overlap_dnf.py
+++ b/pym/portage/tests/dep/test_overlap_dnf.py
@@ -12,7 +12,7 @@ class OverlapDNFTestCase(TestCase):
test_cases = (
(
'|| ( cat/A cat/B ) cat/E || ( cat/C cat/D )',
- ['cat/E', ['||', 'cat/A', 'cat/B'], ['||', 'cat/C', 'cat/D']],
+ [['||', 'cat/A', 'cat/B'], 'cat/E', ['||', 'cat/C', 'cat/D']],
),
(
'|| ( cat/A cat/B ) cat/D || ( cat/B cat/C )',
diff --git a/pym/portage/tests/resolver/test_virtual_minimize_children.py b/pym/portage/tests/resolver/test_virtual_minimize_children.py
index 287445e58..b566cb592 100644
--- a/pym/portage/tests/resolver/test_virtual_minimize_children.py
+++ b/pym/portage/tests/resolver/test_virtual_minimize_children.py
@@ -168,17 +168,15 @@ class VirtualMinimizeChildrenTestCase(TestCase):
}
test_cases = (
- # Test bug 645002, where we want to prefer choices
- # based on the number of new slots rather than the total
- # number of slots. This is necessary so that perl-cleaner's
- # deps are satisfied by the ( portage portage-utils )
- # choice which has a larger total number of slots than the
- # paludis choice.
+ # Test bug 645002, where paludis was selected to satisfy a
+ # perl-cleaner dependency because that choice contained fewer
+ # packages than the ( portage portage-utils ) choice which
+ # should have been preferred according to the order of
+ # choices specified in the ebuild.
ResolverPlaygroundTestCase(
[
'app-admin/perl-cleaner',
'virtual/package-manager',
- 'app-portage/portage-utils',
],
all_permutations=True,
success=True,
^ permalink raw reply related [flat|nested] 2+ messages in thread
end of thread, other threads:[~2018-02-03 0:01 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2018-02-03 0:01 [gentoo-commits] proj/portage:master commit in: pym/portage/tests/dep/, pym/portage/dep/, pym/portage/tests/resolver/ Zac Medico
-- strict thread matches above, loose matches on Subject: below --
2017-11-14 4:03 Zac Medico
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox