Fix prefix-collision detection for projections (#24049)

If two Specs have the same hash (and prefix) but are not equal, Spack
originally had logic to detect this and raise an error (since both
cannot be installed in the same place). Recently this has eroded and
the check no-longer works; moreover, when defining projections (which
may truncate the hash or other distinguishing properties from the
prefix) Spack was also failing to detect collisions (in both of these
cases, Spack would overwrite the old prefix with the new Spec).

This PR maintains a list of all "taken" prefixes: if a hash is not
registered (i.e. recorded as installed in the database) but the prefix
is occupied, that is a collision. This can detect collisions created
by defining projections (specifically when they omit the hash).

The PR does not detect collisions where specs have the same hash
(and prefix) but are not equal.

4 files changed, 80 insertions, 32 deletions

diff --git a/lib/spack/spack/database.py b/lib/spack/spack/database.py
index dee9a90d10..d998895fed 100644
--- a/lib/spack/spack/database.py
+++ b/lib/spack/spack/database.py
@@ -23,12 +23,13 @@ filesystem.
 import contextlib
 import datetime
 import os
-import six
 import socket
 import sys
 import time
 from typing import Dict  # novm
 
+import six
+
 try:
     import uuid
     _use_uuid = True
@@ -38,7 +39,6 @@ except ImportError:
 
 import llnl.util.filesystem as fs
 import llnl.util.tty as tty
-
 import spack.repo
 import spack.spec
 import spack.store
@@ -382,6 +382,11 @@ class Database(object):
                                 desc='database')
         self._data = {}
 
+        # For every installed spec we keep track of its install prefix, so that
+        # we can answer the simple query whether a given path is already taken
+        # before installing a different spec.
+        self._installed_prefixes = set()
+
         self.upstream_dbs = list(upstream_dbs) if upstream_dbs else []
 
         # whether there was an error at the start of a read transaction
@@ -774,6 +779,7 @@ class Database(object):
 
         # Pass 1: Iterate through database and build specs w/o dependencies
         data = {}
+        installed_prefixes = set()
         for hash_key, rec in installs.items():
             try:
                 # This constructs a spec DAG from the list of all installs
@@ -784,6 +790,9 @@ class Database(object):
                 # TODO: would a more immmutable spec implementation simplify
                 #       this?
                 data[hash_key] = InstallRecord.from_dict(spec, rec)
+
+                if not spec.external and 'installed' in rec and rec['installed']:
+                    installed_prefixes.add(rec['path'])
             except Exception as e:
                 invalid_record(hash_key, e)
 
@@ -805,6 +814,7 @@ class Database(object):
             rec.spec._mark_root_concrete()
 
         self._data = data
+        self._installed_prefixes = installed_prefixes
 
     def reindex(self, directory_layout):
         """Build database index from scratch based on a directory layout.
@@ -824,6 +834,7 @@ class Database(object):
             except CorruptDatabaseError as e:
                 self._error = e
                 self._data = {}
+                self._installed_prefixes = set()
 
         transaction = lk.WriteTransaction(
             self.lock, acquire=_read_suppress_error, release=self._write
@@ -838,12 +849,14 @@ class Database(object):
                 self._error = None
 
             old_data = self._data
+            old_installed_prefixes = self._installed_prefixes
             try:
                 self._construct_from_directory_layout(
                     directory_layout, old_data)
             except BaseException:
                 # If anything explodes, restore old data, skip write.
                 self._data = old_data
+                self._installed_prefixes = old_installed_prefixes
                 raise
 
     def _construct_entry_from_directory_layout(self, directory_layout,
@@ -880,6 +893,7 @@ class Database(object):
         with directory_layout.disable_upstream_check():
             # Initialize data in the reconstructed DB
             self._data = {}
+            self._installed_prefixes = set()
 
             # Start inspecting the installed prefixes
             processed_specs = set()
@@ -1087,6 +1101,8 @@ class Database(object):
             path = None
             if not spec.external and directory_layout:
                 path = directory_layout.path_for_spec(spec)
+                if path in self._installed_prefixes:
+                    raise Exception("Install prefix collision.")
                 try:
                     directory_layout.check_installed(spec)
                     installed = True
@@ -1094,6 +1110,7 @@ class Database(object):
                     tty.warn(
                         'Dependency missing: may be deprecated or corrupted:',
                         path, str(e))
+                self._installed_prefixes.add(path)
             elif spec.external_path:
                 path = spec.external_path
 
@@ -1173,6 +1190,7 @@ class Database(object):
 
         if rec.ref_count == 0 and not rec.installed:
             del self._data[key]
+
             for dep in spec.dependencies(_tracked_deps):
                 self._decrement_ref_count(dep)
 
@@ -1190,11 +1208,17 @@ class Database(object):
         key = self._get_matching_spec_key(spec)
         rec = self._data[key]
 
+        # This install prefix is now free for other specs to use, even if the
+        # spec is only marked uninstalled.
+        if not rec.spec.external:
+            self._installed_prefixes.remove(rec.path)
+
         if rec.ref_count > 0:
             rec.installed = False
             return rec.spec
 
         del self._data[key]
+
         for dep in rec.spec.dependencies(_tracked_deps):
             # FIXME: the two lines below needs to be updated once #11983 is
             # FIXME: fixed. The "if" statement should be deleted and specs are
@@ -1538,6 +1562,10 @@ class Database(object):
         upstream, record = self.query_by_spec_hash(key)
         return record and not record.installed
 
+    def is_occupied_install_prefix(self, path):
+        with self.read_transaction():
+            return path in self._installed_prefixes
+
     @property
     def unused_specs(self):
         """Return all the specs that are currently installed but not needed
diff --git a/lib/spack/spack/installer.py b/lib/spack/spack/installer.py
index fd6bc31d4b..50218be5b9 100644
--- a/lib/spack/spack/installer.py
+++ b/lib/spack/spack/installer.py
@@ -33,12 +33,13 @@ import heapq
 import itertools
 import os
 import shutil
-import six
 import sys
 import time
-
 from collections import defaultdict
 
+import six
+
+
 import llnl.util.filesystem as fs
 import llnl.util.lock as lk
 import llnl.util.tty as tty
@@ -51,7 +52,6 @@ import spack.package
 import spack.package_prefs as prefs
 import spack.repo
 import spack.store
-
 from llnl.util.tty.color import colorize
 from llnl.util.tty.log import log_output
 from spack.util.environment import dump_environment
@@ -814,24 +814,29 @@ class PackageInstaller(object):
         # Determine if the spec is flagged as installed in the database
         rec, installed_in_db = self._check_db(task.pkg.spec)
 
-        # Make sure the installation directory is in the desired state
-        # for uninstalled specs.
-        partial = False
-        if not installed_in_db and os.path.isdir(task.pkg.spec.prefix):
-            if not keep_prefix:
-                task.pkg.remove_prefix()
-            else:
-                tty.debug('{0} is partially installed'
-                          .format(task.pkg_id))
-                partial = True
+        if not installed_in_db:
+            # Ensure there is no other installed spec with the same prefix dir
+            if spack.store.db.is_occupied_install_prefix(task.pkg.spec.prefix):
+                raise InstallError(
+                    "Install prefix collision for {0}".format(task.pkg_id),
+                    long_msg="Prefix directory {0} already used by another "
+                             "installed spec.".format(task.pkg.spec.prefix))
+
+            # Make sure the installation directory is in the desired state
+            # for uninstalled specs.
+            if os.path.isdir(task.pkg.spec.prefix):
+                if not keep_prefix:
+                    task.pkg.remove_prefix()
+                else:
+                    tty.debug('{0} is partially installed'.format(task.pkg_id))
 
         # Destroy the stage for a locally installed, non-DIYStage, package
         if restage and task.pkg.stage.managed_by_spack:
             task.pkg.stage.destroy()
 
-        if not partial and self.layout.check_installed(task.pkg.spec) and (
-                rec.spec.dag_hash() not in task.request.overwrite or
-                rec.installation_time > task.request.overwrite_time
+        if installed_in_db and (
+            rec.spec.dag_hash() not in task.request.overwrite or
+            rec.installation_time > task.request.overwrite_time
         ):
             self._update_installed(task)
 
diff --git a/lib/spack/spack/test/conftest.py b/lib/spack/spack/test/conftest.py
index 2443d0edf0..3d9f9429dc 100644
--- a/lib/spack/spack/test/conftest.py
+++ b/lib/spack/spack/test/conftest.py
@@ -26,17 +26,15 @@ except ImportError:
     def parse_date(string):  # type: ignore
         pytest.skip("dateutil package not available")
 
-import py
-import pytest
-
 import archspec.cpu.microarchitecture
 import archspec.cpu.schema
-from llnl.util.filesystem import mkdirp, remove_linked_tree, working_dir
+import py
+import pytest
 
 import spack.architecture
+import spack.caches
 import spack.compilers
 import spack.config
-import spack.caches
 import spack.database
 import spack.directory_layout
 import spack.environment as ev
@@ -47,14 +45,14 @@ import spack.platforms.test
 import spack.repo
 import spack.stage
 import spack.store
+import spack.subprocess_context
 import spack.util.executable
 import spack.util.gpg
-import spack.subprocess_context
 import spack.util.spack_yaml as syaml
-
-from spack.util.pattern import Bunch
-from spack.fetch_strategy import FetchStrategyComposite, URLFetchStrategy
+from llnl.util.filesystem import mkdirp, remove_linked_tree, working_dir
 from spack.fetch_strategy import FetchError
+from spack.fetch_strategy import FetchStrategyComposite, URLFetchStrategy
+from spack.util.pattern import Bunch
 
 
 #
@@ -767,7 +765,7 @@ class MockLayout(object):
         self.root = root
 
     def path_for_spec(self, spec):
-        return '/'.join([self.root, spec.name])
+        return '/'.join([self.root, spec.name + '-' + spec.dag_hash()])
 
     def check_installed(self, spec):
         return True
diff --git a/lib/spack/spack/test/install.py b/lib/spack/spack/test/install.py
index 6a533bb8b1..90bab99c20 100644
--- a/lib/spack/spack/test/install.py
+++ b/lib/spack/spack/test/install.py
@@ -4,20 +4,20 @@
 # SPDX-License-Identifier: (Apache-2.0 OR MIT)
 
 import os
-import pytest
 import shutil
 
-import llnl.util.filesystem as fs
+import pytest
 
-from spack.package import InstallError, PackageBase, PackageStillNeededError
+import llnl.util.filesystem as fs
 import spack.error
 import spack.patch
 import spack.repo
 import spack.store
-from spack.spec import Spec
 import spack.util.spack_json as sjson
+from spack.package import InstallError, PackageBase, PackageStillNeededError
 from spack.package import (_spack_build_envfile, _spack_build_logfile,
                            _spack_configure_argsfile)
+from spack.spec import Spec
 
 
 def find_nothing(*args):
@@ -325,6 +325,23 @@ def test_second_install_no_overwrite_first(install_mockery, mock_fetch):
         spack.package.Package.remove_prefix = remove_prefix
 
 
+def test_install_prefix_collision_fails(config, mock_fetch, mock_packages, tmpdir):
+    """
+    Test that different specs with coinciding install prefixes will fail
+    to install.
+    """
+    projections = {'all': 'all-specs-project-to-this-prefix'}
+    store = spack.store.Store(str(tmpdir), projections=projections)
+    with spack.store.use_store(store):
+        with spack.config.override('config:checksum', False):
+            pkg_a = Spec('libelf@0.8.13').concretized().package
+            pkg_b = Spec('libelf@0.8.12').concretized().package
+            pkg_a.do_install()
+
+            with pytest.raises(InstallError, match="Install prefix collision"):
+                pkg_b.do_install()
+
+
 def test_store(install_mockery, mock_fetch):
     spec = Spec('cmake-client').concretized()
     pkg = spec.package