commit: b9cedd4a7b0616c0231196b5ee867a6af909d654
Author: Arthur Zamarin <arthurzam <AT> gentoo <DOT> org>
AuthorDate: Thu Dec 15 19:04:46 2022 +0000
Commit: Arthur Zamarin <arthurzam <AT> gentoo <DOT> org>
CommitDate: Tue Dec 20 19:33:22 2022 +0000
URL:
https://gitweb.gentoo.org/proj/pkgcore/pkgcore.git/commit/?id=b9cedd4a
Add REQUIRED_USE satisfaction solver
Based on new `snakeoil.constraints`, this adds a solver which can build
satisfying USE flag combinations for a given set of REQUIRED_USE
restricts. This will be used by new tool `pkgdev tatt`.
Signed-off-by: Arthur Zamarin <arthurzam <AT> gentoo.org>
pyproject.toml | 4 +-
src/pkgcore/restrictions/required_use.py | 118 ++++++++++++++++++++++++++++++
tests/restrictions/test_required_use.py | 121 +++++++++++++++++++++++++++++++
3 files changed, 241 insertions(+), 2 deletions(-)
diff --git a/pyproject.toml b/pyproject.toml
index 16c48bd22..a3d891463 100644
--- a/pyproject.toml
+++ b/pyproject.toml
@@ -1,7 +1,7 @@
[build-system]
requires = [
"flit_core >=3.8,<4",
- "snakeoil~=0.10.3",
+ "snakeoil~=0.10.4",
]
build-backend = "py_build"
backend-path = ["."]
@@ -28,7 +28,7 @@ classifiers = [
dynamic = ["version"]
dependencies = [
- "snakeoil~=0.10.3",
+ "snakeoil~=0.10.4",
"lxml",
]
diff --git a/src/pkgcore/restrictions/required_use.py
b/src/pkgcore/restrictions/required_use.py
new file mode 100644
index 000000000..a1906d4b0
--- /dev/null
+++ b/src/pkgcore/restrictions/required_use.py
@@ -0,0 +1,118 @@
+from typing import Iterator, Protocol
+
+from snakeoil.constraints import Constraint, Problem
+from . import restriction, boolean, packages, values
+
+
+class _use_constraint(Protocol):
+ def __call__(self, on: frozenset[str]) -> bool:
+ raise NotImplementedError('Constraint', '__call__')
+
+
+def __use_flags_state_any(negate: bool, vals: frozenset[str]) ->
_use_constraint:
+ def check(on: frozenset[str]):
+ return vals.isdisjoint(on) == negate
+ return check
+
+
+def __condition(negate: bool, vals: frozenset[str], *children:
_use_constraint) -> _use_constraint:
+ def check(on: frozenset[str]):
+ return vals.issubset(on) == negate or all(c(on) for c in children)
+ return check
+
+
+def __or_constraint(negate: bool, *children: _use_constraint) ->
_use_constraint:
+ def check(on: frozenset[str]):
+ return any(c(on) for c in children) != negate
+ return check
+
+
+def __and_constraint(negate: bool, *children: _use_constraint) ->
_use_constraint:
+ def check(on: frozenset[str]):
+ return all(c(on) for c in children) != negate
+ return check
+
+
+def __just_one_constraint(negate: bool, *children: _use_constraint) ->
_use_constraint:
+ def check(on: frozenset[str]):
+ return (1 == sum(c(on) for c in children)) != negate
+ return check
+
+
+def __at_most_one_constraint(negate: bool, *children: _use_constraint) ->
_use_constraint:
+ def check(on: frozenset[str]):
+ return (1 >= sum(c(on) for c in children)) != negate
+ return check
+
+
+def __to_single_constraint(restrict) -> tuple[_use_constraint, frozenset[str]]:
+ if isinstance(restrict, values.ContainmentMatch):
+ assert not restrict.all
+ return __use_flags_state_any(restrict.negate,
frozenset(restrict.vals)), frozenset(restrict.vals)
+ elif isinstance(restrict, packages.Conditional):
+ assert isinstance(x := restrict.restriction, values.ContainmentMatch)
+ children, variables = zip(*(__to_single_constraint(c) for c in
restrict.payload))
+ return __condition(x.negate, frozenset(x.vals), *children),
frozenset(x.vals).union(*variables)
+ elif isinstance(restrict, boolean.OrRestriction):
+ children, variables = zip(*(__to_single_constraint(c) for c in
restrict.restrictions))
+ return __or_constraint(restrict.negate, *children),
frozenset().union(*variables)
+ elif isinstance(restrict, boolean.AndRestriction):
+ children, variables = zip(*(__to_single_constraint(c) for c in
restrict.restrictions))
+ return __and_constraint(restrict.negate, *children),
frozenset().union(*variables)
+ elif isinstance(restrict, boolean.JustOneRestriction):
+ children, variables = zip(*(__to_single_constraint(c) for c in
restrict.restrictions))
+ return __just_one_constraint(restrict.negate, *children),
frozenset().union(*variables)
+ elif isinstance(restrict, boolean.AtMostOneOfRestriction):
+ children, variables = zip(*(__to_single_constraint(c) for c in
restrict.restrictions))
+ return __at_most_one_constraint(restrict.negate, *children),
frozenset().union(*variables)
+ else:
+ raise NotImplementedError('build_constraint', type(restrict))
+
+
+def __to_multiple_constraint(restrict) -> Iterator[tuple[_use_constraint,
frozenset[str]]]:
+ if isinstance(restrict, packages.Conditional):
+ assert isinstance(x := restrict.restriction, values.ContainmentMatch)
+ for rule in restrict.payload:
+ for func, variables in __to_multiple_constraint(rule):
+ yield __condition(x.negate, frozenset(x.vals), func),
frozenset(x.vals).union(variables)
+ elif isinstance(restrict, boolean.AndRestriction):
+ assert not restrict.negate
+ for rule in restrict.restrictions:
+ yield from __to_multiple_constraint(rule)
+ else:
+ yield __to_single_constraint(restrict)
+
+
+def __wrapper(constraint_func: _use_constraint) -> Constraint:
+ def check(**kwargs):
+ return constraint_func(frozenset(k for k, v in kwargs.items() if v))
+ return check
+
+
+def find_constraint_satisfaction(restricts: restriction.base, iuse: set[str],
force_true=(), force_false=(), prefer_true=()) -> Iterator[dict[str, bool]]:
+ """Return iterator for use flags combination satisfying REQUIRED_USE
+
+ :param restricts: Parsed restricts of REQUIRED_USE
+ :param iuse: Known IUSE for the restricts. Any USE flag encountered
+ not in this set, will be forced to a False value.
+ :param force_true: USE flags which will be force to only True value.
+ :param force_false: USE flags which will be force to only False value.
+ :param prefer_true: USE flags which will have a preference to True value.
+ All other flags, which aren't forced, will have a preference to False.
+ :return: Iterator returning satisfying use flags combination, of USE flag
+ and it's state.
+ """
+ problem = Problem()
+
+ prefer_false = iuse.difference(force_true, force_false, prefer_true)
+ problem.add_variable((True, False), *prefer_false)
+ problem.add_variable((False, True),
*iuse.intersection(prefer_true).difference(force_false, force_true))
+ problem.add_variable((False, ), *iuse.intersection(force_false))
+ problem.add_variable((True, ), *iuse.intersection(force_true))
+
+ for rule in restricts:
+ for constraint_func, variables in __to_multiple_constraint(rule):
+ if missing_vars := variables - problem.variables.keys():
+ problem.add_variable((False, ), *missing_vars)
+ problem.add_constraint(__wrapper(constraint_func), variables)
+ return iter(problem)
diff --git a/tests/restrictions/test_required_use.py
b/tests/restrictions/test_required_use.py
new file mode 100644
index 000000000..a669c5038
--- /dev/null
+++ b/tests/restrictions/test_required_use.py
@@ -0,0 +1,121 @@
+from itertools import islice
+
+import pytest
+
+from pkgcore.ebuild.eapi import get_eapi
+from pkgcore.ebuild.ebuild_src import base as ebuild
+from pkgcore.restrictions.required_use import find_constraint_satisfaction as
solver
+
+def parse(required_use):
+ o = ebuild(None, 'dev-util/diffball-0.1-r1')
+ object.__setattr__(o, 'eapi', get_eapi('8', suppress_unsupported=True))
+ object.__setattr__(o, 'data', {'REQUIRED_USE': required_use})
+ return o.required_use
+
+def test_simple():
+ required_use = parse(required_use='bar foo')
+ assert tuple(solver(required_use, {'bar', 'foo'})) == ({'bar': True,
'foo': True},)
+
+def test_negative_simple():
+ required_use = parse(required_use='!bar foo')
+ assert tuple(solver(required_use, {'bar', 'foo'})) == ({'bar': False,
'foo': True},)
+
+def test_missing_iuse():
+ required_use = parse(required_use='!bar foo? ( bar )')
+ assert tuple(solver(required_use, {'bar'})) == ({'bar': False, 'foo':
False},)
+
[email protected](('required_use', 'exclude'), (
+ ('bar? ( foo )', {'bar': True, 'foo': False}),
+ ('bar? ( !foo )', {'bar': True, 'foo': True}),
+ ('!bar? ( foo )', {'bar': False, 'foo': False}),
+ ('!bar? ( !foo )', {'bar': False, 'foo': True}),
+))
+def test_condition(required_use, exclude):
+ required_use = parse(required_use=required_use)
+ solutions = tuple(solver(required_use, {'bar', 'foo'}))
+ assert len(solutions) == 3
+ assert exclude not in solutions
+
[email protected](('required_use', 'exclude'), (
+ ('?? ( bar foo )', {'bar': True, 'foo': True}),
+ ('?? ( !bar foo )', {'bar': False, 'foo': True}),
+ ('?? ( bar !foo )', {'bar': True, 'foo': False}),
+ ('?? ( !bar !foo )', {'bar': False, 'foo': False}),
+))
+def test_at_most(required_use, exclude):
+ required_use = parse(required_use=required_use)
+ solutions = tuple(solver(required_use, {'bar', 'foo'}))
+ assert len(solutions) == 3
+ assert exclude not in solutions
+
[email protected](('required_use', 'exclude'), (
+ ('|| ( bar foo )', {'bar': False, 'foo': False}),
+ ('|| ( !bar foo )', {'bar': True, 'foo': False}),
+ ('|| ( bar !foo )', {'bar': False, 'foo': True}),
+ ('|| ( !bar !foo )', {'bar': True, 'foo': True}),
+))
+def test_or(required_use, exclude):
+ required_use = parse(required_use=required_use)
+ solutions = tuple(solver(required_use, {'bar', 'foo'}))
+ assert len(solutions) == 3
+ assert exclude not in solutions
+
[email protected](('required_use', 'include'), (
+ ('bar foo', {'bar': True, 'foo': True}),
+ ('!bar foo', {'bar': False, 'foo': True}),
+ ('bar !foo', {'bar': True, 'foo': False}),
+ ('!bar !foo', {'bar': False, 'foo': False}),
+))
+def test_and(required_use, include):
+ required_use = parse(required_use=required_use)
+ solutions = tuple(solver(required_use, {'bar', 'foo'}))
+ assert solutions == (include,)
+
[email protected](('required_use', 'iuse', 'force_true'), (
+ pytest.param(
+ 'test? ( jpeg jpeg2k tiff truetype )',
+ {'examples', 'imagequant', 'jpeg', 'jpeg2k', 'lcms', 'test', 'tiff',
'tk', 'truetype', 'webp', 'xcb', 'zlib'},
+ {'test'},
+ id='pillow'),
+ pytest.param(
+ 'test? ( cuda gpl? ( openssl? ( bindist ) fdk? ( bindist ) ) ) cuda? (
nvenc ) ^^ ( openssl fdk )',
+ {'cuda', 'gpl', 'openssl', 'bindist', 'fdk', 'test', 'nvenc'},
+ {'test', 'fdk'},
+ id='ffmpeg'),
+ pytest.param(
+ '|| ( openssl ( gnutls ssl ) ) ssl? ( ( gnutls openssl ) )',
+ {'openssl', 'gnutls', 'ssl'},
+ {'ssl'},
+ id='weird'),
+ pytest.param(
+ '|| ( ssl ( gnutls? ( openssl ) ) )',
+ {'openssl', 'gnutls', 'ssl'},
+ {'gnutls'},
+ id='weird2'),
+))
+def test_complex_force_true(required_use, iuse, force_true):
+ required_use = parse(required_use=required_use)
+ solution = None
+ for solution in islice(solver(required_use, iuse, force_true=force_true),
20):
+ assert all(solution[flag] for flag in force_true)
+ use_flags = tuple(k for k, v in solution.items() if v)
+ misses = [restrict for restrict in
required_use.evaluate_depset(use_flags) if not restrict.match(use_flags)]
+ assert not misses
+ assert solution is not None
+
[email protected](('required_use', 'iuse', 'force_false'), (
+ pytest.param(
+ '|| ( openssl ( gnutls ssl ) )',
+ {'openssl', 'gnutls', 'ssl'},
+ {'openssl'},
+ id='custom'),
+))
+def test_complex_force_false(required_use, iuse, force_false):
+ required_use = parse(required_use=required_use)
+ solution = None
+ for solution in islice(solver(required_use, iuse,
force_false=force_false), 20):
+ assert all(not solution[flag] for flag in force_false)
+ use_flags = tuple(k for k, v in solution.items() if v)
+ misses = [restrict for restrict in
required_use.evaluate_depset(use_flags) if not restrict.match(use_flags)]
+ assert not misses
+ assert solution is not None
