include installed hashes in solve and optimize for reuse

3 files changed, 104 insertions, 15 deletions

diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index a6c375ab17..d82d93ff57 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -43,6 +43,7 @@ import spack.package_prefs
 import spack.platforms
 import spack.repo
 import spack.spec
+import spack.store
 import spack.util.timer
 import spack.variant
 import spack.version
@@ -816,18 +817,21 @@ class SpackSolverSetup(object):
             )
 
         if imposed_spec:
-            imposed_constraints = self.spec_clauses(
-                imposed_spec, body=False, required_from=name)
-            for pred in imposed_constraints:
-                # imposed "node"-like conditions are no-ops
-                if pred.name in ("node", "virtual_node"):
-                    continue
-                self.gen.fact(
-                    fn.imposed_constraint(condition_id, pred.name, *pred.args)
-                )
+            self.impose(condition_id, imposed_spec, node=False, name=name)
 
         return condition_id
 
+    def impose(self, condition_id, imposed_spec, node=True, name=None):
+        imposed_constraints = self.spec_clauses(
+            imposed_spec, body=False, required_from=name)
+        for pred in imposed_constraints:
+            # imposed "node"-like conditions are no-ops
+            if not node and pred.name in ("node", "virtual_node"):
+                continue
+            self.gen.fact(
+                fn.imposed_constraint(condition_id, pred.name, *pred.args)
+            )
+
     def package_provider_rules(self, pkg):
         for provider_name in sorted(set(s.name for s in pkg.provided.keys())):
             self.gen.fact(fn.possible_provider(pkg.name, provider_name))
@@ -1127,13 +1131,22 @@ class SpackSolverSetup(object):
 
         # dependencies
         if spec.concrete:
-            clauses.append(fn.concrete(spec.name))
-            # TODO: add concrete depends_on() facts for concrete dependencies
+            clauses.append(fn.hash(spec.name, spec.dag_hash()))
 
         # add all clauses from dependencies
         if transitive:
+            if spec.concrete:
+                for dep_name, dep in spec.dependencies_dict().items():
+                    for dtype in dep.deptypes:
+                        clauses.append(fn.depends_on(spec.name, dep_name, dtype))
+
             for dep in spec.traverse(root=False):
-                clauses.extend(self._spec_clauses(dep, body, transitive=False))
+                if spec.concrete:
+                    clauses.append(fn.hash(dep.name, dep.dag_hash()))
+                else:
+                    clauses.extend(
+                        self._spec_clauses(dep, body, transitive=False)
+                    )
 
         return clauses
 
@@ -1475,6 +1488,26 @@ class SpackSolverSetup(object):
         for pkg, variant, value in sorted(self.variant_values_from_specs):
             self.gen.fact(fn.variant_possible_value(pkg, variant, value))
 
+    def define_installed_packages(self, possible):
+        """Add facts about all specs already in the database.
+
+        Arguments:
+            possible (dict): result of Package.possible_dependencies() for
+                specs in this solve.
+        """
+        with spack.store.db.read_transaction():
+            for spec in spack.store.db.query(installed=True):
+                # tell the solver about any installed packages that could
+                # be dependencies (don't tell it about the others)
+                if spec.name in possible:
+                    # this indicates that there is a spec like this installed
+                    h = spec.dag_hash()
+                    self.gen.fact(fn.installed_hash(spec.name, h))
+
+                    # this describes what constraints it imposes on the solve
+                    self.impose(h, spec)
+                    self.gen.newline()
+
     def setup(self, driver, specs, tests=False, reuse=False):
         """Generate an ASP program with relevant constraints for specs.
 
@@ -1577,6 +1610,10 @@ class SpackSolverSetup(object):
         self.gen.h1("Target Constraints")
         self.define_target_constraints()
 
+        if reuse:
+            self.gen.h1("Installed packages")
+            self.define_installed_packages(possible)
+
 
 class SpecBuilder(object):
     """Class with actions to rebuild a spec from ASP results."""
@@ -1586,6 +1623,14 @@ class SpecBuilder(object):
         self._flag_sources = collections.defaultdict(lambda: set())
         self._flag_compiler_defaults = set()
 
+    def hash(self, pkg, h):
+        if pkg not in self._specs:
+            self._specs[pkg] = spack.store.db.get_by_hash(h)[0]
+        else:
+            # ensure that if it's already there, it's correct
+            spec = self._specs[pkg]
+            assert spec.dag_hash() == h
+
     def node(self, pkg):
         if pkg not in self._specs:
             self._specs[pkg] = spack.spec.Spec(pkg)
@@ -1727,6 +1772,7 @@ class SpecBuilder(object):
         # them here so that directives that build objects (like node and
         # node_compiler) are called in the right order.
         function_tuples.sort(key=lambda f: {
+            "hash": -3,
             "node": -2,
             "node_compiler": -1,
         }.get(f[0], 0))
@@ -1749,6 +1795,12 @@ class SpecBuilder(object):
             if spack.repo.path.is_virtual(pkg):
                 continue
 
+            # if we've already gotten a concrete spec for this pkg,
+            # do not bother calling actions on it.
+            spec = self._specs.get(pkg)
+            if spec and spec.concrete:
+                continue
+
             action(*args)
 
         # namespace assignment is done after the fact, as it is not
diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index 00c8abe82d..ab2d45fedd 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -88,17 +88,27 @@ attr(Name, A1, A2, A3) :- impose(ID), imposed_constraint(ID, Name, A1, A2, A3).
 #defined imposed_constraint/5.
 
 %-----------------------------------------------------------------------------
+% Concrete specs
+%-----------------------------------------------------------------------------
+% if a package is assigned a hash, it's concrete.
+concrete(Package) :- hash(Package, _), node(Package).
+
+%-----------------------------------------------------------------------------
 % Dependency semantics
 %-----------------------------------------------------------------------------
 % Dependencies of any type imply that one package "depends on" another
 depends_on(Package, Dependency) :- depends_on(Package, Dependency, _).
 
-% a dependency holds if its condition holds
+% a dependency holds if its condition holds and if it is not external or
+% concrete. We chop off dependencies for externals, and dependencies of
+% concrete specs don't need to be resolved -- they arise from the concrete
+% specs themselves.
 dependency_holds(Package, Dependency, Type) :-
   dependency_condition(ID, Package, Dependency),
   dependency_type(ID, Type),
   condition_holds(ID),
-  not external(Package).
+  not external(Package),
+  not concrete(Package).
 
 % We cut off dependencies of externals (as we don't really know them).
 % Don't impose constraints on dependencies that don't exist.
@@ -251,6 +261,7 @@ possible_provider_weight(Dependency, Virtual, 100, "fallback") :- provider(Depen
 % These allow us to easily define conditional dependency and conflict rules
 % without enumerating all spec attributes every time.
 node(Package)                          :- attr("node", Package).
+hash(Package, Hash)                    :- attr("hash", Package, Hash).
 version(Package, Version)              :- attr("version", Package, Version).
 version_satisfies(Package, Constraint) :- attr("version_satisfies", Package, Constraint).
 node_platform(Package, Platform)       :- attr("node_platform", Package, Platform).
@@ -261,12 +272,14 @@ variant_value(Package, Variant, Value) :- attr("variant_value", Package, Variant
 variant_set(Package, Variant, Value)   :- attr("variant_set", Package, Variant, Value).
 node_flag(Package, FlagType, Flag)     :- attr("node_flag", Package, FlagType, Flag).
 node_compiler(Package, Compiler)       :- attr("node_compiler", Package, Compiler).
+depends_on(Package, Dependency, Type)  :- attr("depends_on", Package, Dependency, Type).
 node_compiler_version(Package, Compiler, Version)
   :- attr("node_compiler_version", Package, Compiler, Version).
 node_compiler_version_satisfies(Package, Compiler, Version)
   :- attr("node_compiler_version_satisfies", Package, Compiler, Version).
 
 attr("node", Package)                          :- node(Package).
+attr("hash", Package, Hash)                    :- hash(Package, Hash).
 attr("version", Package, Version)              :- version(Package, Version).
 attr("version_satisfies", Package, Constraint) :- version_satisfies(Package, Constraint).
 attr("node_platform", Package, Platform)       :- node_platform(Package, Platform).
@@ -277,6 +290,7 @@ attr("variant_value", Package, Variant, Value) :- variant_value(Package, Variant
 attr("variant_set", Package, Variant, Value)   :- variant_set(Package, Variant, Value).
 attr("node_flag", Package, FlagType, Flag)     :- node_flag(Package, FlagType, Flag).
 attr("node_compiler", Package, Compiler)       :- node_compiler(Package, Compiler).
+attr("depends_on", Package, Dependency, Type)  :- depends_on(Package, Dependency, Type).
 attr("node_compiler_version", Package, Compiler, Version)
   :- node_compiler_version(Package, Compiler, Version).
 attr("node_compiler_version_satisfies", Package, Compiler, Version)
@@ -732,6 +746,21 @@ no_flags(Package, FlagType)
 #defined node_flag/3.
 #defined node_flag_set/3.
 
+
+%-----------------------------------------------------------------------------
+% Installed packages
+%-----------------------------------------------------------------------------
+% the solver is free to choose at most one installed hash for each package
+{ hash(Package, Hash) : installed_hash(Package, Hash) } 1 :- node(Package).
+
+% if a hash is selected, we impose all the constraints that implies
+impose(Hash) :- hash(Package, Hash).
+
+% if we haven't selected a hash for a package, we'll be building it
+build(Package) :- not hash(Package, _), node(Package).
+
+#defined installed_hash/2.
+
 %-----------------------------------------------------------------------------
 % How to optimize the spec (high to low priority)
 %-----------------------------------------------------------------------------
@@ -740,12 +769,17 @@ no_flags(Package, FlagType)
 %   2. a `#minimize{ 0@2 : #true }.` statement that ensures the criterion
 %      is displayed (clingo doesn't display sums over empty sets by default)
 
+% Try hard to reuse installed packages (i.e., minimize the number built)
+opt_criterion(17, "number of packages to build (vs. reuse)").
+#minimize { 0@17 : #true }.
+#minimize { 1@17,Package : build(Package) }.
+
 % Minimize the number of deprecated versions being used
 opt_criterion(16, "deprecated versions used").
 #minimize{ 0@16 : #true }.
 #minimize{ 1@16,Package : deprecated(Package, _)}.
 
-% The highest priority is to minimize the:
+% Minimize the:
 % 1. Version weight
 % 2. Number of variants with a non default value, if not set
 % for the root(Package)
diff --git a/lib/spack/spack/solver/display.lp b/lib/spack/spack/solver/display.lp
index 818ce2d90a..e4787f6e4b 100644
--- a/lib/spack/spack/solver/display.lp
+++ b/lib/spack/spack/solver/display.lp
@@ -12,6 +12,7 @@
 % Spec-related functions.
 % Used to build the result of the solve.
 #show node/1.
+#show hash/2.
 #show depends_on/3.
 #show version/2.
 #show variant_value/3.
@@ -26,6 +27,8 @@
 #show no_flags/2.
 #show external_spec_selected/2.
 
+#show build/1.
+
 % names of optimization criteria
 #show opt_criterion/2.