summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTodd Gamblin <tgamblin@llnl.gov>2018-02-20 11:11:39 -0800
committerTodd Gamblin <tgamblin@llnl.gov>2020-11-17 10:04:13 -0800
commita8a6d943d68deafbff6dd672b92404cf00a89e2b (patch)
tree51e53758dfba590df19bb89a0ba5eaeb765a88ec
parent5b725a37bc08c89627fced7d478edf03bfe80c75 (diff)
downloadspack-a8a6d943d68deafbff6dd672b92404cf00a89e2b.tar.gz
spack-a8a6d943d68deafbff6dd672b92404cf00a89e2b.tar.bz2
spack-a8a6d943d68deafbff6dd672b92404cf00a89e2b.tar.xz
spack-a8a6d943d68deafbff6dd672b92404cf00a89e2b.zip
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
-rw-r--r--lib/spack/spack/cmd/solve.py47
-rw-r--r--lib/spack/spack/package.py19
-rw-r--r--lib/spack/spack/solver/__init__.py4
-rw-r--r--lib/spack/spack/solver/asp.py268
4 files changed, 338 insertions, 0 deletions
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()