Re: [gentoo-portage-dev] [PATCH] dep_check: use DNF to optimize overlapping virtual || deps (bug 632026)

[Zac Medico]

On 11/13/2017 01:11 PM, Alec Warner wrote:
> 
> 
> On Sun, Nov 12, 2017 at 6:48 AM, Zac Medico  > wrote:
> 
> diff --git a/pym/portage/dep/_dnf.py b/pym/portage/dep/_dnf.py
> new file mode 100644
> index 0..503b209c2
> --- /dev/null
> +++ b/pym/portage/dep/_dnf.py
> @@ -0,0 +1,97 @@
> +# 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
> 
> 
> 
> I'm not a huge fan of asserts, but if we use them can we use them in the
> expr, message form?
> 
> assert x, "Assertion failed, wanted x in list form in dep: %s" % dep_struct
> 
> or whatever.

Yes, I've added messages in v2. Also, I noticed that the above assertion
wasn't strict enough. Fixing that allowed me to eliminate some
unnecessary code.
-- 
Thanks,
Zac



signature.asc
Description: OpenPGP digital signature

Re: [gentoo-portage-dev] [PATCH] dep_check: use DNF to optimize overlapping virtual || deps (bug 632026)

[Alec Warner]

On Sun, Nov 12, 2017 at 6:48 AM, Zac Medico  wrote:

> 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
> ---
>  pym/portage/dep/_dnf.py|  97 
>  pym/portage/dep/dep_check.py   | 127
> +++--
>  pym/portage/tests/dep/test_dnf_convert.py  |  48 
>  pym/portage/tests/dep/test_overlap_dnf.py  |  28 +
>  .../resolver/test_virtual_minimize_children.py |  92 +++
>  5 files changed, 385 insertions(+), 7 deletions(-)
>  create mode 100644 pym/portage/dep/_dnf.py
>  create mode 100644 pym/portage/tests/dep/test_dnf_convert.py
>  create mode 100644 pym/portage/tests/dep/test_overlap_dnf.py
>  create mode 100644 pym/portage/tests/resolver/test_virtual_minimize_
> children.py
>
> diff --git a/pym/portage/dep/_dnf.py b/pym/portage/dep/_dnf.py
> new file mode 100644
> index 0..503b209c2
> --- /dev/null
> +++ b/pym/portage/dep/_dnf.py
> @@ -0,0 +1,97 @@
> +# 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
>


I'm not a huge fan of asserts, but if we use them can we use them in the
expr, message form?

assert x, "Assertion failed, wanted x in list form in dep: %s" % dep_struct

or whatever.


> +   if x[0] == '||':
> +   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 and
> element[0] != '||'
> +   element =
> dnf_convert(element)
> +   if
> contains_disjunction(element):
> +   assert
> (len(element) == 1 and
> +
>  element[0] and element[0][0] == '||')
> +
>  x_dnf.extend(element[0][1:])
> +   else:
> +
>  x_dnf.append(element)
> +   else:
> +
>  x_dnf.append(element)
> +   x = x_dnf
> +   disjunctions.append(x)
> +   else:
> +   for x in dnf_convert(x):
> +   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] == '||'
> +   disjunctions.append(x)
> +   else:
> +   conjunction.append(x)
> +   else:
> +

[gentoo-portage-dev] [PATCH] dep_check: use DNF to optimize overlapping virtual || deps (bug 632026)

[Zac Medico]

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
---
 pym/portage/dep/_dnf.py|  97 
 pym/portage/dep/dep_check.py   | 127 +++--
 pym/portage/tests/dep/test_dnf_convert.py  |  48 
 pym/portage/tests/dep/test_overlap_dnf.py  |  28 +
 .../resolver/test_virtual_minimize_children.py |  92 +++
 5 files changed, 385 insertions(+), 7 deletions(-)
 create mode 100644 pym/portage/dep/_dnf.py
 create mode 100644 pym/portage/tests/dep/test_dnf_convert.py
 create mode 100644 pym/portage/tests/dep/test_overlap_dnf.py
 create mode 100644 pym/portage/tests/resolver/test_virtual_minimize_children.py

diff --git a/pym/portage/dep/_dnf.py b/pym/portage/dep/_dnf.py
new file mode 100644
index 0..503b209c2
--- /dev/null
+++ b/pym/portage/dep/_dnf.py
@@ -0,0 +1,97 @@
+# 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
+   if x[0] == '||':
+   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 and 
element[0] != '||'
+   element = 
dnf_convert(element)
+   if 
contains_disjunction(element):
+   assert 
(len(element) == 1 and
+   
element[0] and element[0][0] == '||')
+   
x_dnf.extend(element[0][1:])
+   else:
+   
x_dnf.append(element)
+   else:
+   x_dnf.append(element)
+   x = x_dnf
+   disjunctions.append(x)
+   else:
+   for x in dnf_convert(x):
+   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] == '||'
+   disjunctions.append(x)
+   else:
+   conjunction.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]):
+