concretizer: enable hash reuse with full hash

With the original DAG hash, we did not store build dependencies in the database, but
with the full DAG hash, we do. Previously, we'd never tell the concretizer about build
dependencies of things used by hash, because we never had them. Now, we have to avoid
telling the concretizer about them, or they'll unnecessarily constrain build
dependencies for new concretizations.

- [x] Make database track all dependencies included in the `dag_hash`
- [x] Modify spec_clauses so that build dependency information is optional
      and off by default.
- [x] `spack diff` asks `spec_clauses` for build dependencies for completeness
- [x] Modify `concretize.lp` so that reuse optimization doesn't affect fresh
      installations.
- [x] Modify concretizer setup so that it does *not* prioritize installed versions
      over package versions. We don't need this with reuse, so they're low priority.
- [x] Fix `test_installed_deps` for full hash and new concretizer (does not work
      for old concretizer with full hash -- leave this for later if we need it)
- [x] Move `test_installed_deps` mock packages to `builtin.mock` for easier debugging
      with `spack -m`.
- [x] Fix `test_reuse_installed_packages_when_package_def_changes` for full hash

12 files changed, 280 insertions, 87 deletions

diff --git a/lib/spack/spack/cmd/diff.py b/lib/spack/spack/cmd/diff.py
index 79dc74655c..be69e3645b 100644
--- a/lib/spack/spack/cmd/diff.py
+++ b/lib/spack/spack/cmd/diff.py
@@ -68,8 +68,14 @@ def compare_specs(a, b, to_string=False, color=None):
     # Prepare a solver setup to parse differences
     setup = asp.SpackSolverSetup()
 
-    a_facts = set(t for t in setup.spec_clauses(a, body=True, expand_hashes=True))
-    b_facts = set(t for t in setup.spec_clauses(b, body=True, expand_hashes=True))
+    # get facts for specs, making sure to include build dependencies of concrete
+    # specs and to descend into dependency hashes so we include all facts.
+    a_facts = set(t for t in setup.spec_clauses(
+        a, body=True, expand_hashes=True, concrete_build_deps=True,
+    ))
+    b_facts = set(t for t in setup.spec_clauses(
+        b, body=True, expand_hashes=True, concrete_build_deps=True,
+    ))
 
     # We want to present them to the user as simple key: values
     intersect = sorted(a_facts.intersection(b_facts))
diff --git a/lib/spack/spack/database.py b/lib/spack/spack/database.py
index 95e3be6715..06389cad78 100644
--- a/lib/spack/spack/database.py
+++ b/lib/spack/spack/database.py
@@ -91,7 +91,8 @@ _db_lock_timeout = 120
 _pkg_lock_timeout = None
 
 # Types of dependencies tracked by the database
-_tracked_deps = ('link', 'run')
+# We store by DAG hash, so we track the dependencies that the DAG hash includes.
+_tracked_deps = ht.dag_hash.deptype
 
 # Default list of fields written for each install record
 default_install_record_fields = [
@@ -1601,11 +1602,12 @@ class Database(object):
         needed, visited = set(), set()
         with self.read_transaction():
             for key, rec in self._data.items():
-                if rec.explicit:
-                    # recycle `visited` across calls to avoid
-                    # redundantly traversing
-                    for spec in rec.spec.traverse(visited=visited):
-                        needed.add(spec.dag_hash())
+                if not rec.explicit:
+                    continue
+
+                # recycle `visited` across calls to avoid redundantly traversing
+                for spec in rec.spec.traverse(visited=visited, deptype=("link", "run")):
+                    needed.add(spec.dag_hash())
 
             unused = [rec.spec for key, rec in self._data.items()
                       if key not in needed and rec.installed]
diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index 363552e782..21578b2dc2 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -77,22 +77,25 @@ def ast_getter(*names):
 ast_type = ast_getter("ast_type", "type")
 ast_sym = ast_getter("symbol", "term")
 
+#: Order of precedence for version origins. Topmost types are preferred.
+version_origin_fields = [
+    'spec',
+    'external',
+    'packages_yaml',
+    'package_py',
+    'installed',
+]
+
+#: Look up version precedence strings by enum id
+version_origin_str = {
+    i: name for i, name in enumerate(version_origin_fields)
+}
 
 #: Enumeration like object to mark version provenance
 version_provenance = collections.namedtuple(  # type: ignore
     'VersionProvenance',
-    ['external', 'packages_yaml', 'package_py', 'spec', 'installed']
-)(installed=0, spec=1, external=2, packages_yaml=3, package_py=4)
-
-#: String representation of version origins, to emit legible
-# facts for the ASP solver
-version_origin_str = {
-    0: 'installed',
-    1: 'spec',
-    2: 'external',
-    3: 'packages_yaml',
-    4: 'package_py'
-}
+    version_origin_fields,
+)(**{name: i for i, name in enumerate(version_origin_fields)})
 
 #: Named tuple to contain information on declared versions
 DeclaredVersion = collections.namedtuple(
@@ -698,15 +701,12 @@ class SpackSolverSetup(object):
     def pkg_version_rules(self, pkg):
         """Output declared versions of a package.
 
-        This uses self.possible_versions so that we include any versions
+        This uses self.declared_versions so that we include any versions
         that arise from a spec.
         """
         def key_fn(version):
-            # Origins are sorted by order of importance:
-            # 1. Spec from command line
-            # 2. Externals
-            # 3. Package preferences
-            # 4. Directives in package.py
+            # Origins are sorted by precedence defined in `version_origin_str`,
+            # then by order added.
             return version.origin, version.idx
 
         pkg = packagize(pkg)
@@ -1149,7 +1149,14 @@ class SpackSolverSetup(object):
             raise RuntimeError(msg)
         return clauses
 
-    def _spec_clauses(self, spec, body=False, transitive=True, expand_hashes=False):
+    def _spec_clauses(
+            self,
+            spec,
+            body=False,
+            transitive=True,
+            expand_hashes=False,
+            concrete_build_deps=False,
+    ):
         """Return a list of clauses for a spec mandates are true.
 
         Arguments:
@@ -1160,6 +1167,8 @@ class SpackSolverSetup(object):
                 dependencies (default True)
             expand_hashes (bool): if True, descend into hashes of concrete specs
                 (default False)
+            concrete_build_deps (bool): if False, do not include pure build deps
+                of concrete specs (as they have no effect on runtime constraints)
 
         Normally, if called with ``transitive=True``, ``spec_clauses()`` just generates
         hashes for the dependency requirements of concrete specs. If ``expand_hashes``
@@ -1267,18 +1276,34 @@ class SpackSolverSetup(object):
 
         # add all clauses from dependencies
         if transitive:
-            if spec.concrete:
-                # TODO: We need to distinguish 2 specs from the same package later
-                for edge in spec.edges_to_dependencies():
-                    for dtype in edge.deptypes:
-                        clauses.append(fn.depends_on(spec.name, edge.spec.name, dtype))
+            # TODO: Eventually distinguish 2 deps on the same pkg (build and link)
+            for dspec in spec.edges_to_dependencies():
+                dep = dspec.spec
 
-            for dep in spec.traverse(root=False):
                 if spec.concrete:
-                    clauses.append(fn.hash(dep.name, dep.dag_hash()))
+                    # We know dependencies are real for concrete specs. For abstract
+                    # specs they just mean the dep is somehow in the DAG.
+                    for dtype in dspec.deptypes:
+                        # skip build dependencies of already-installed specs
+                        if concrete_build_deps or dtype != "build":
+                            clauses.append(fn.depends_on(spec.name, dep.name, dtype))
+
+                    # imposing hash constraints for all but pure build deps of
+                    # already-installed concrete specs.
+                    if concrete_build_deps or dspec.deptypes != ("build",):
+                        clauses.append(fn.hash(dep.name, dep.dag_hash()))
+
+                # if the spec is abstract, descend into dependencies.
+                # if it's concrete, then the hashes above take care of dependency
+                # constraints, but expand the hashes if asked for.
                 if not spec.concrete or expand_hashes:
                     clauses.extend(
-                        self._spec_clauses(dep, body, transitive=False)
+                        self._spec_clauses(
+                            dep,
+                            body=body,
+                            expand_hashes=expand_hashes,
+                            concrete_build_deps=concrete_build_deps,
+                        )
                     )
 
         return clauses
@@ -1812,12 +1837,14 @@ class SpackSolverSetup(object):
                 fn.virtual_root(spec.name) if spec.virtual
                 else fn.root(spec.name)
             )
+
             for clause in self.spec_clauses(spec):
                 self.gen.fact(clause)
                 if clause.name == 'variant_set':
-                    self.gen.fact(fn.variant_default_value_from_cli(
-                        *clause.args
-                    ))
+                    self.gen.fact(
+                        fn.variant_default_value_from_cli(*clause.args)
+                    )
+
         self.gen.h1("Variant Values defined in specs")
         self.define_variant_values()
 
@@ -1840,6 +1867,7 @@ class SpecBuilder(object):
     ignored_attributes = ["opt_criterion"]
 
     def __init__(self, specs):
+        self._specs = {}
         self._result = None
         self._command_line_specs = specs
         self._flag_sources = collections.defaultdict(lambda: set())
diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index 65dbd0b19d..9cc5efa00f 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -885,8 +885,27 @@ build(Package) :- not hash(Package, _), node(Package).
 %   200+        Shifted priorities for build nodes; correspond to priorities 0 - 99.
 %   100 - 199   Unshifted priorities. Currently only includes minimizing #builds.
 %   0   -  99   Priorities for non-built nodes.
-build_priority(Package, 200) :- build(Package), node(Package).
-build_priority(Package, 0)   :- not build(Package), node(Package).
+build_priority(Package, 200) :- build(Package), node(Package), optimize_for_reuse().
+build_priority(Package, 0)   :- not build(Package), node(Package), optimize_for_reuse().
+
+% don't adjust build priorities if reuse is not enabled
+build_priority(Package, 0)   :- node(Package), not optimize_for_reuse().
+
+% don't assign versions from installed packages unless reuse is enabled
+% NOTE: that "installed" means the declared version was only included because
+% that package happens to be installed, NOT because it was asked for on the
+% command line.  If the user specifies a hash, the origin will be "spec".
+%
+% TODO: There's a slight inconsistency with this: if the user concretizes
+% and installs `foo ^bar`, for some build dependency `bar`, and then later
+% does a `spack install --fresh foo ^bar/abcde` (i.e.,the hash of `bar`, it
+% currently *won't* force versions for `bar`'s build dependencies -- `--fresh`
+% will instead build the latest bar. When we actually include transitive
+% build deps in the solve, consider using them as a preference to resolve this.
+:- version(Package, Version),
+   version_weight(Package, Weight),
+   version_declared(Package, Version, Weight, "installed"),
+   not optimize_for_reuse().
 
 #defined installed_hash/2.
 
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index cf27a8db68..10afd16004 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -1599,7 +1599,15 @@ class Spec(object):
     def traverse_edges(self, visited=None, d=0, deptype='all',
                        dep_spec=None, **kwargs):
         """Generic traversal of the DAG represented by this spec.
-           This will yield each node in the spec.  Options:
+
+           This yields ``DependencySpec`` objects as they are traversed.
+
+           When traversing top-down, an imaginary incoming edge to the root
+           is yielded first as ``DependencySpec(None, root, ())``. When
+           traversing bottom-up, imaginary edges to leaves are yielded first
+           as ``DependencySpec(left, None, ())`` objects.
+
+           Options:
 
            order    [=pre|post]
                Order to traverse spec nodes. Defaults to preorder traversal.
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
index 4c2c8f5bb2..43941908f9 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -1292,8 +1292,10 @@ class TestConcretize(object):
         assert ht.build_hash(root) == ht.build_hash(new_root_with_reuse)
         assert ht.build_hash(root) != ht.build_hash(new_root_without_reuse)
 
-        # package hashes are different, so dag hashes will be different
-        assert root.dag_hash() != new_root_with_reuse.dag_hash()
+        # DAG hash should be the same with reuse since only the dependency changed
+        assert root.dag_hash() == new_root_with_reuse.dag_hash()
+
+        # Structure and package hash will be different without reuse
         assert root.dag_hash() != new_root_without_reuse.dag_hash()
 
     @pytest.mark.regression('20784')
diff --git a/lib/spack/spack/test/spec_dag.py b/lib/spack/spack/test/spec_dag.py
index 78555340a7..eca87f1f13 100644
--- a/lib/spack/spack/test/spec_dag.py
+++ b/lib/spack/spack/test/spec_dag.py
@@ -84,54 +84,58 @@ w->y deptypes are (link, build), w->x and y->z deptypes are (test)
 
 
 @pytest.mark.usefixtures('config')
-def test_installed_deps(monkeypatch):
-    """Preinstall a package P with a constrained build dependency D, then
-    concretize a dependent package which also depends on P and D, specifying
-    that the installed instance of P should be used. In this case, D should
-    not be constrained by P since P is already built.
-    """
-    # FIXME: this requires to concretize build deps separately if we are
-    # FIXME: using the clingo based concretizer
-    if spack.config.get('config:concretizer') == 'clingo':
-        pytest.xfail('requires separate concretization of build dependencies')
-
-    default = ('build', 'link')
-    build_only = ('build',)
-
-    mock_repo = MockPackageMultiRepo()
-    e = mock_repo.add_package('e', [], [])
-    d = mock_repo.add_package('d', [], [])
-    c_conditions = {
-        d.name: {
-            'c': 'd@2'
-        },
-        e.name: {
-            'c': 'e@2'
-        }
-    }
-    c = mock_repo.add_package('c', [d, e], [build_only, default],
-                              conditions=c_conditions)
-    b = mock_repo.add_package('b', [d, e], [default, default])
-    mock_repo.add_package('a', [b, c], [default, default])
+def test_installed_deps(monkeypatch, mock_packages):
+    """Ensure that concrete specs and their build deps don't constrain solves.
 
-    with spack.repo.use_repositories(mock_repo):
-        c_spec = Spec('c')
-        c_spec.concretize()
-        assert c_spec['d'].version == spack.version.Version('2')
+    Preinstall a package ``c`` that has a constrained build dependency on ``d``, then
+    install ``a`` and ensure that neither:
 
-        c_installed = spack.spec.Spec.from_dict(c_spec.to_dict())
-        installed_names = [s.name for s in c_installed.traverse()]
+      * ``c``'s package constraints, nor
+      * the concrete ``c``'s build dependencies
 
-        def _mock_installed(self):
-            return self.name in installed_names
+    constrain ``a``'s dependency on ``d``.
 
-        monkeypatch.setattr(Spec, 'installed', _mock_installed)
-        a_spec = Spec('a')
-        a_spec._add_dependency(c_installed, default)
-        a_spec.concretize()
-
-        assert a_spec['d'].version == spack.version.Version('3')
-        assert a_spec['e'].version == spack.version.Version('2')
+    """
+    if spack.config.get('config:concretizer') == 'original':
+        pytest.xfail('fails with the original concretizer and full hashes')
+
+    # see installed-deps-[abcde] test packages.
+    #     a
+    #    / \
+    #   b   c   b --> d build/link
+    #   |\ /|   b --> e build/link
+    #   |/ \|   c --> d build
+    #   d   e   c --> e build/link
+    #
+    a, b, c, d, e = ["installed-deps-%s" % s for s in "abcde"]
+
+    # install C, which will force d's version to be 2
+    # BUT d is only a build dependency of C, so it won't constrain
+    # link/run dependents of C when C is depended on as an existing
+    # (concrete) installation.
+    c_spec = Spec(c)
+    c_spec.concretize()
+    assert c_spec[d].version == spack.version.Version('2')
+
+    installed_names = [s.name for s in c_spec.traverse()]
+
+    def _mock_installed(self):
+        return self.name in installed_names
+
+    monkeypatch.setattr(Spec, 'installed', _mock_installed)
+
+    # install A, which depends on B, C, D, and E, and force A to
+    # use the installed C.  It should *not* force A to use the installed D
+    # *if* we're doing a fresh installation.
+    a_spec = Spec(a)
+    a_spec._add_dependency(c_spec, ("build", "link"))
+    a_spec.concretize()
+    assert spack.version.Version('2') == a_spec[c][d].version
+    assert spack.version.Version('2') == a_spec[e].version
+    assert spack.version.Version('3') == a_spec[b][d].version
+    assert spack.version.Version('3') == a_spec[d].version
+
+    # TODO: with reuse, this will be different -- verify the reuse case
 
 
 @pytest.mark.usefixtures('config')
diff --git a/var/spack/repos/builtin.mock/packages/installed-deps-a/package.py b/var/spack/repos/builtin.mock/packages/installed-deps-a/package.py
new file mode 100644
index 0000000000..c3b4d67d74
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/installed-deps-a/package.py
@@ -0,0 +1,26 @@
+# Copyright 2013-2022 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 spack import *
+
+
+class InstalledDepsA(Package):
+    """Used by test_installed_deps test case."""
+    #     a
+    #    / \
+    #   b   c   b --> d build/link
+    #   |\ /|   b --> e build/link
+    #   |/ \|   c --> d build
+    #   d   e   c --> e build/link
+
+    homepage = "http://www.example.com"
+    url      = "http://www.example.com/a-1.0.tar.gz"
+
+    version("1", "0123456789abcdef0123456789abcdef")
+    version("2", "abcdef0123456789abcdef0123456789")
+    version("3", "def0123456789abcdef0123456789abc")
+
+    depends_on("installed-deps-b", type=("build", "link"))
+    depends_on("installed-deps-c", type=("build", "link"))
diff --git a/var/spack/repos/builtin.mock/packages/installed-deps-b/package.py b/var/spack/repos/builtin.mock/packages/installed-deps-b/package.py
new file mode 100644
index 0000000000..66c24d9c31
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/installed-deps-b/package.py
@@ -0,0 +1,26 @@
+# Copyright 2013-2022 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 spack import *
+
+
+class InstalledDepsB(Package):
+    """Used by test_installed_deps test case."""
+    #     a
+    #    / \
+    #   b   c   b --> d build/link
+    #   |\ /|   b --> e build/link
+    #   |/ \|   c --> d build
+    #   d   e   c --> e build/link
+
+    homepage = "http://www.example.com"
+    url      = "http://www.example.com/b-1.0.tar.gz"
+
+    version("1", "0123456789abcdef0123456789abcdef")
+    version("2", "abcdef0123456789abcdef0123456789")
+    version("3", "def0123456789abcdef0123456789abc")
+
+    depends_on("installed-deps-d", type=("build", "link"))
+    depends_on("installed-deps-e", type=("build", "link"))
diff --git a/var/spack/repos/builtin.mock/packages/installed-deps-c/package.py b/var/spack/repos/builtin.mock/packages/installed-deps-c/package.py
new file mode 100644
index 0000000000..703245d5b8
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/installed-deps-c/package.py
@@ -0,0 +1,26 @@
+# Copyright 2013-2022 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 spack import *
+
+
+class InstalledDepsC(Package):
+    """Used by test_installed_deps test case."""
+    #     a
+    #    / \
+    #   b   c   b --> d build/link
+    #   |\ /|   b --> e build/link
+    #   |/ \|   c --> d build
+    #   d   e   c --> e build/link
+
+    homepage = "http://www.example.com"
+    url      = "http://www.example.com/c-1.0.tar.gz"
+
+    version("1", "0123456789abcdef0123456789abcdef")
+    version("2", "abcdef0123456789abcdef0123456789")
+    version("3", "def0123456789abcdef0123456789abc")
+
+    depends_on("installed-deps-d@2", type="build")
+    depends_on("installed-deps-e@2", type=("build", "link"))
diff --git a/var/spack/repos/builtin.mock/packages/installed-deps-d/package.py b/var/spack/repos/builtin.mock/packages/installed-deps-d/package.py
new file mode 100644
index 0000000000..b2e4bb41f8
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/installed-deps-d/package.py
@@ -0,0 +1,23 @@
+# Copyright 2013-2022 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 spack import *
+
+
+class InstalledDepsD(Package):
+    """Used by test_installed_deps test case."""
+    #     a
+    #    / \
+    #   b   c   b --> d build/link
+    #   |\ /|   b --> e build/link
+    #   |/ \|   c --> d build
+    #   d   e   c --> e build/link
+
+    homepage = "http://www.example.com"
+    url      = "http://www.example.com/d-1.0.tar.gz"
+
+    version("1", "0123456789abcdef0123456789abcdef")
+    version("2", "abcdef0123456789abcdef0123456789")
+    version("3", "def0123456789abcdef0123456789abc")
diff --git a/var/spack/repos/builtin.mock/packages/installed-deps-e/package.py b/var/spack/repos/builtin.mock/packages/installed-deps-e/package.py
new file mode 100644
index 0000000000..7ae70d9bd0
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/installed-deps-e/package.py
@@ -0,0 +1,23 @@
+# Copyright 2013-2022 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 spack import *
+
+
+class InstalledDepsE(Package):
+    """Used by test_installed_deps test case."""
+    #     a
+    #    / \
+    #   b   c   b --> d build/link
+    #   |\ /|   b --> e build/link
+    #   |/ \|   c --> d build
+    #   d   e   c --> e build/link
+
+    homepage = "http://www.example.com"
+    url      = "http://www.example.com/e-1.0.tar.gz"
+
+    version("1", "0123456789abcdef0123456789abcdef")
+    version("2", "abcdef0123456789abcdef0123456789")
+    version("3", "def0123456789abcdef0123456789abc")