From a8a6d943d68deafbff6dd672b92404cf00a89e2b Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Tue, 20 Feb 2018 11:11:39 -0800 Subject: concretizer: beginnings of solve() command - `spack solve` command outputs a really basic ASP program that handles unconditional dependencies, architecture and versions - doesn't yet handle conflicts, picking latest versions, preferred versions, compilers, etc. - doesn't handle variants --- lib/spack/spack/cmd/solve.py | 47 +++++++ lib/spack/spack/package.py | 19 +++ lib/spack/spack/solver/__init__.py | 4 + lib/spack/spack/solver/asp.py | 268 +++++++++++++++++++++++++++++++++++++ 4 files changed, 338 insertions(+) create mode 100644 lib/spack/spack/cmd/solve.py create mode 100644 lib/spack/spack/solver/__init__.py create mode 100644 lib/spack/spack/solver/asp.py (limited to 'lib') diff --git a/lib/spack/spack/cmd/solve.py b/lib/spack/spack/cmd/solve.py new file mode 100644 index 0000000000..771f352484 --- /dev/null +++ b/lib/spack/spack/cmd/solve.py @@ -0,0 +1,47 @@ +# Copyright 2013-2019 Lawrence Livermore National Security, LLC and other +# Spack Project Developers. See the top-level COPYRIGHT file for details. +# +# SPDX-License-Identifier: (Apache-2.0 OR MIT) + +from __future__ import print_function + +import argparse + +import spack +import spack.cmd +import spack.cmd.common.arguments as arguments +import spack.package +import spack.solver.asp as asp + +description = "concretize a specs using an ASP solver" +section = 'developer' +level = 'long' + + +def setup_parser(subparser): + arguments.add_common_arguments(subparser, ['long', 'very_long']) + subparser.add_argument( + '-y', '--yaml', action='store_true', default=False, + help='print concrete spec as YAML') + subparser.add_argument( + '-c', '--cover', action='store', + default='nodes', choices=['nodes', 'edges', 'paths'], + help='how extensively to traverse the DAG (default: nodes)') + subparser.add_argument( + '-N', '--namespaces', action='store_true', default=False, + help='show fully qualified package names') + subparser.add_argument( + '-I', '--install-status', action='store_true', default=False, + help='show install status of packages. packages can be: ' + 'installed [+], missing and needed by an installed package [-], ' + 'or not installed (no annotation)') + subparser.add_argument( + '-t', '--types', action='store_true', default=False, + help='show dependency types') + subparser.add_argument( + 'specs', nargs=argparse.REMAINDER, help="specs of packages") + + +def solve(parser, args): + specs = spack.cmd.parse_specs(args.specs) + asp.solve(specs) diff --git a/lib/spack/spack/package.py b/lib/spack/spack/package.py index 725e1a69d3..ab03368135 100644 --- a/lib/spack/spack/package.py +++ b/lib/spack/spack/package.py @@ -763,6 +763,25 @@ class PackageBase(with_metaclass(PackageMeta, PackageViewMixin, object)): return visited + def enum_constraints(self, visited=None): + """Return transitive dependency constraints on this package.""" + if visited is None: + visited = set() + visited.add(self.name) + + names = [] + clauses = [] + + for name in self.dependencies: + if name not in visited and not spack.spec.Spec(name).virtual: + pkg = spack.repo.get(name) + dvis, dnames, dclauses = pkg.enum_constraints(visited) + visited |= dvis + names.extend(dnames) + clauses.extend(dclauses) + + return visited + # package_dir and module are *class* properties (see PackageMeta), # but to make them work on instances we need these defs as well. @property diff --git a/lib/spack/spack/solver/__init__.py b/lib/spack/spack/solver/__init__.py new file mode 100644 index 0000000000..94f8ac4d9e --- /dev/null +++ b/lib/spack/spack/solver/__init__.py @@ -0,0 +1,4 @@ +# Copyright 2013-2019 Lawrence Livermore National Security, LLC and other +# Spack Project Developers. See the top-level COPYRIGHT file for details. +# +# SPDX-License-Identifier: (Apache-2.0 OR MIT) diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py new file mode 100644 index 0000000000..f810e5a1a9 --- /dev/null +++ b/lib/spack/spack/solver/asp.py @@ -0,0 +1,268 @@ +# Copyright 2013-2019 Lawrence Livermore National Security, LLC and other +# Spack Project Developers. See the top-level COPYRIGHT file for details. +# +# SPDX-License-Identifier: (Apache-2.0 OR MIT) + +from __future__ import print_function + +import collections +import types + +import spack +import spack.cmd +import spack.spec +import spack.package + + +def title(name): + print() + print("%% %s" % name) + print("% -----------------------------------------") + + +def section(name): + print() + print("%") + print("%% %s" % name) + print("%") + + +def _id(thing): + """Quote string if needed for it to be a valid identifier.""" + return '"%s"' % str(thing) + + +def issequence(obj): + if isinstance(obj, basestring): + return False + return isinstance(obj, (collections.Sequence, types.GeneratorType)) + + +def listify(args): + if len(args) == 1 and issequence(args[0]): + return list(args[0]) + return list(args) + + +def packagize(pkg): + if isinstance(pkg, spack.package.PackageMeta): + return pkg + return spack.repo.path.get_pkg_class(pkg) + + +def specify(spec): + if isinstance(spec, spack.spec.Spec): + return spec + return spack.spec.Spec(spec) + + +class AspFunction(object): + def __init__(self, name): + self.name = name + self.args = [] + + def __call__(self, *args): + self.args[:] = args + return self + + def __str__(self): + return "%s(%s)" % ( + self.name, ', '.join(_id(arg) for arg in self.args)) + + +class AspAnd(object): + def __init__(self, *args): + args = listify(args) + self.args = args + + def __str__(self): + s = ", ".join(str(arg) for arg in self.args) + return s + + +class AspOr(object): + def __init__(self, *args): + args = listify(args) + self.args = args + + def __str__(self): + return " | ".join(str(arg) for arg in self.args) + + +class AspNot(object): + def __init__(self, arg): + self.arg = arg + + def __str__(self): + return "not %s" % self.arg + + +class AspBuilder(object): + def _or(self, *args): + return AspOr(*args) + + def _and(self, *args): + return AspAnd(*args) + + def _not(self, arg): + return AspNot(arg) + + def _fact(self, head): + """ASP fact (a rule without a body).""" + print("%s." % head) + + def _rule(self, head, body): + """ASP rule (an implication).""" + print("%s :- %s." % (head, body)) + + def _constraint(self, body): + """ASP integrity constraint (rule with no head; can't be true).""" + print(":- %s." % body) + + def __getattr__(self, name): + return AspFunction(name) + + +asp = AspBuilder() + + +def pkg_version_rules(pkg): + pkg = packagize(pkg) + asp._rule( + asp._or(asp.version(pkg.name, v) for v in pkg.versions), + asp.node(pkg.name)) + + +def spec_versions(spec): + spec = specify(spec) + + if spec.concrete: + asp._rule(asp.version(spec.name, spec.version), + asp.node(spec.name)) + else: + version = spec.versions + impossible, possible = [], [] + for v in spec.package.versions: + if v.satisfies(version): + possible.append(v) + else: + impossible.append(v) + + if impossible: + asp._rule( + asp._and(asp._not(asp.version(spec.name, v)) + for v in impossible), + asp.node(spec.name)) + if possible: + asp._rule( + asp._or(asp.version(spec.name, v) for v in possible), + asp.node(spec.name)) + + +def pkg_rules(pkg): + pkg = packagize(pkg) + + # versions + pkg_version_rules(pkg) + + # dependencies + for name, conditions in pkg.dependencies.items(): + for cond, dep in conditions.items(): + asp._fact(asp.depends_on(dep.pkg.name, dep.spec.name)) + + +def spec_rules(spec): + asp._fact(asp.node(spec.name)) + spec_versions(spec) + + # seed architecture at the root (we'll propagate later) + # TODO: use better semantics. + arch = spack.spec.ArchSpec(spack.architecture.sys_type()) + spec_arch = spec.architecture + if spec_arch: + if spec_arch.platform: + arch.platform = spec_arch.platform + if spec_arch.os: + arch.os = spec_arch.os + if spec_arch.target: + arch.target = spec_arch.target + asp._fact(asp.arch_platform(spec.name, arch.platform)) + asp._fact(asp.arch_os(spec.name, arch.os)) + asp._fact(asp.arch_target(spec.name, arch.target)) + + # TODO + # dependencies + # compiler + # external_path + # external_module + # compiler_flags + # namespace + +# +# These are handwritten parts for the Spack ASP model. +# + + +#: generate the problem space, establish cardinality constraints +_generate = """\ +% One version, arch, etc. per package +{ version(P, V) : version(P, V) } = 1 :- node(P). +{ arch_platform(P, A) : arch_platform(P, A) } = 1 :- node(P). +{ arch_os(P, A) : arch_os(P, A) } = 1 :- node(P). +{ arch_target(P, T) : arch_target(P, T) } = 1 :- node(P). +""" + +#: define the rules of Spack concretization +_define = """\ +% dependencies imply new nodes. +node(D) :- node(P), depends_on(P, D). + +% propagate platform, os, target downwards +arch_platform(D, A) :- node(D), depends_on(P, D), arch_platform(P, A). +arch_os(D, A) :- node(D), depends_on(P, D), arch_os(P, A). +arch_target(D, A) :- node(D), depends_on(P, D), arch_target(P, A). +""" + +#: what parts of the model to display to read models back in +_display = """\ +#show node/1. +#show depends_on/2. +#show version/2. +#show arch_platform/2. +#show arch_os/2. +#show arch_target/2. +""" + + +def solve(specs): + """Solve for a stable model of specs. + + Arguments: + specs (list): list of Specs to solve. + """ + + # get list of all possible dependencies + pkg_names = set(spec.fullname for spec in specs) + pkgs = [spack.repo.path.get_pkg_class(name) for name in pkg_names] + pkgs = spack.package.possible_dependencies(*pkgs) + + title("Generate") + print(_generate) + + title("Define") + print(_define) + + title("Package Constraints") + for pkg in pkgs: + section(pkg) + pkg_rules(pkg) + + title("Spec Constraints") + for spec in specs: + section(str(spec)) + spec_rules(spec) + + title("Display") + print(_display) + print() + print() -- cgit v1.2.3-60-g2f50