commands: add `spack deprecate` command (#12933)

`spack deprecate` allows for the removal of insecure packages with minimal impact to their dependents. It allows one package to be symlinked into the prefix of another to provide seamless transition for rpath'd and hard-coded applications using the old version.

Example usage:

    spack deprecate /hash-of-old-openssl /hash-of-new-openssl

The spack deprecate command is designed for use only in extroardinary circumstances.  The spack deprecate command makes no promises about binary compatibility. It is up to the user to ensure the replacement is suitable for the deprecated package.

13 files changed, 789 insertions, 63 deletions

diff --git a/lib/spack/docs/basic_usage.rst b/lib/spack/docs/basic_usage.rst
index f86724e140..0d2d74b43f 100644
--- a/lib/spack/docs/basic_usage.rst
+++ b/lib/spack/docs/basic_usage.rst
@@ -277,6 +277,52 @@ the tarballs in question to it (see :ref:`mirrors`):
 
        $ spack install galahad
 
+-----------------------------
+Deprecating insecure packages
+-----------------------------
+
+``spack deprecate`` allows for the removal of insecure packages with
+minimal impact to their dependents.
+
+.. warning::
+
+  The ``spack deprecate`` command is designed for use only in
+  extraordinary circumstances. This is a VERY big hammer to be used
+  with care.
+
+The ``spack deprecate`` command will remove one package and replace it
+with another by replacing the deprecated package's prefix with a link
+to the deprecator package's prefix.
+
+.. warning::
+
+  The ``spack deprecate`` command makes no promises about binary
+  compatibility. It is up to the user to ensure the deprecator is
+  suitable for the deprecated package.
+
+Spack tracks concrete deprecated specs and ensures that no future packages
+concretize to a deprecated spec.
+
+The first spec given to the ``spack deprecate`` command is the package
+to deprecate. It is an abstract spec that must describe a single
+installed package. The second spec argument is the deprecator
+spec. By default it must be an abstract spec that describes a single
+installed package, but with the ``-i/--install-deprecator`` it can be
+any abstract spec that Spack will install and then use as the
+deprecator. The ``-I/--no-install-deprecator`` option will ensure
+the default behavior.
+
+By default, ``spack deprecate`` will deprecate all dependencies of the
+deprecated spec, replacing each by the dependency of the same name in
+the deprecator spec. The ``-d/--dependencies`` option will ensure the
+default, while the ``-D/--no-dependencies`` option will deprecate only
+the root of the deprecate spec in favor of the root of the deprecator
+spec.
+
+``spack deprecate`` can use symbolic links or hard links. The default
+behavior is symbolic links, but the ``-l/--link-type`` flag can take
+options ``hard`` or ``soft``.
+
 -----------------------
 Verifying installations
 -----------------------
@@ -372,11 +418,13 @@ only shows the version of installed packages.
 Viewing more metadata
 """"""""""""""""""""""""""""""""
 
-``spack find`` can filter the package list based on the package name, spec, or
-a number of properties of their installation status.  For example, missing
-dependencies of a spec can be shown with ``--missing``, packages which were
-explicitly installed with ``spack install <package>`` can be singled out with
-``--explicit`` and those which have been pulled in only as dependencies with
+``spack find`` can filter the package list based on the package name,
+spec, or a number of properties of their installation status.  For
+example, missing dependencies of a spec can be shown with
+``--missing``, deprecated packages can be included with
+``--deprecated``, packages which were explicitly installed with
+``spack install <package>`` can be singled out with ``--explicit`` and
+those which have been pulled in only as dependencies with
 ``--implicit``.
 
 In some cases, there may be different configurations of the *same*
diff --git a/lib/spack/spack/cmd/__init__.py b/lib/spack/spack/cmd/__init__.py
index 52e20614a1..9dd6dc4c6e 100644
--- a/lib/spack/spack/cmd/__init__.py
+++ b/lib/spack/spack/cmd/__init__.py
@@ -174,7 +174,7 @@ def elide_list(line_list, max_num=10):
         return line_list
 
 
-def disambiguate_spec(spec, env, local=False):
+def disambiguate_spec(spec, env, local=False, installed=True):
     """Given a spec, figure out which installed package it refers to.
 
     Arguments:
@@ -182,12 +182,17 @@ def disambiguate_spec(spec, env, local=False):
         env (spack.environment.Environment): a spack environment,
             if one is active, or None if no environment is active
         local (boolean, default False): do not search chained spack instances
+        installed (boolean or any, or spack.database.InstallStatus or iterable
+            of spack.database.InstallStatus): install status argument passed to
+            database query. See ``spack.database.Database._query`` for details.
     """
     hashes = env.all_hashes() if env else None
     if local:
-        matching_specs = spack.store.db.query_local(spec, hashes=hashes)
+        matching_specs = spack.store.db.query_local(spec, hashes=hashes,
+                                                    installed=installed)
     else:
-        matching_specs = spack.store.db.query(spec, hashes=hashes)
+        matching_specs = spack.store.db.query(spec, hashes=hashes,
+                                              installed=installed)
     if not matching_specs:
         tty.die("Spec '%s' matches no installed packages." % spec)
 
diff --git a/lib/spack/spack/cmd/deprecate.py b/lib/spack/spack/cmd/deprecate.py
new file mode 100644
index 0000000000..286d2e995a
--- /dev/null
+++ b/lib/spack/spack/cmd/deprecate.py
@@ -0,0 +1,129 @@
+# 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)
+'''Deprecate one Spack install in favor of another
+
+Spack packages of different configurations cannot be installed to the same
+location. However, in some circumstances (e.g. security patches) old
+installations should never be used again. In these cases, we will mark the old
+installation as deprecated, remove it, and link another installation into its
+place.
+
+It is up to the user to ensure binary compatibility between the deprecated
+installation and its deprecator.
+'''
+from __future__ import print_function
+import argparse
+import os
+
+import llnl.util.tty as tty
+
+import spack.cmd
+import spack.store
+import spack.cmd.common.arguments as arguments
+import spack.environment as ev
+
+from spack.error import SpackError
+from spack.database import InstallStatuses
+
+description = "Replace one package with another via symlinks"
+section = "admin"
+level = "long"
+
+# Arguments for display_specs when we find ambiguity
+display_args = {
+    'long': True,
+    'show_flags': True,
+    'variants': True,
+    'indent': 4,
+}
+
+
+def setup_parser(sp):
+    setup_parser.parser = sp
+
+    arguments.add_common_arguments(sp, ['yes_to_all'])
+
+    deps = sp.add_mutually_exclusive_group()
+    deps.add_argument('-d', '--dependencies', action='store_true',
+                      default=True, dest='dependencies',
+                      help='Deprecate dependencies (default)')
+    deps.add_argument('-D', '--no-dependencies', action='store_false',
+                      default=True, dest='dependencies',
+                      help='Do not deprecate dependencies')
+
+    install = sp.add_mutually_exclusive_group()
+    install.add_argument('-i', '--install-deprecator', action='store_true',
+                         default=False, dest='install',
+                         help='Concretize and install deprecator spec')
+    install.add_argument('-I', '--no-install-deprecator',
+                         action='store_false', default=False, dest='install',
+                         help='Deprecator spec must already be installed (default)')  # noqa 501
+
+    sp.add_argument('-l', '--link-type', type=str,
+                    default='soft', choices=['soft', 'hard'],
+                    help="Type of filesystem link to use for deprecation (default soft)")  # noqa 501
+
+    sp.add_argument('specs', nargs=argparse.REMAINDER,
+                    help="spec to deprecate and spec to use as deprecator")
+
+
+def deprecate(parser, args):
+    """Deprecate one spec in favor of another"""
+    env = ev.get_env(args, 'deprecate')
+    specs = spack.cmd.parse_specs(args.specs)
+
+    if len(specs) != 2:
+        raise SpackError('spack deprecate requires exactly two specs')
+
+    install_query = [InstallStatuses.INSTALLED, InstallStatuses.DEPRECATED]
+    deprecate = spack.cmd.disambiguate_spec(specs[0], env, local=True,
+                                            installed=install_query)
+
+    if args.install:
+        deprecator = specs[1].concretized()
+    else:
+        deprecator = spack.cmd.disambiguate_spec(specs[1], env, local=True)
+
+    # calculate all deprecation pairs for errors and warning message
+    all_deprecate = []
+    all_deprecators = []
+
+    generator = deprecate.traverse(
+        order='post', type='link', root=True
+    ) if args.dependencies else [deprecate]
+    for spec in generator:
+        all_deprecate.append(spec)
+        all_deprecators.append(deprecator[spec.name])
+        # This will throw a key error if deprecator does not have a dep
+        # that matches the name of a dep of the spec
+
+    if not args.yes_to_all:
+        tty.msg('The following packages will be deprecated:\n')
+        spack.cmd.display_specs(all_deprecate, **display_args)
+        tty.msg("In favor of (respectively):\n")
+        spack.cmd.display_specs(all_deprecators, **display_args)
+        print()
+
+        already_deprecated = []
+        already_deprecated_for = []
+        for spec in all_deprecate:
+            deprecated_for = spack.store.db.deprecator(spec)
+            if deprecated_for:
+                already_deprecated.append(spec)
+                already_deprecated_for.append(deprecated_for)
+
+        tty.msg('The following packages are already deprecated:\n')
+        spack.cmd.display_specs(already_deprecated, **display_args)
+        tty.msg('In favor of (respectively):\n')
+        spack.cmd.display_specs(already_deprecated_for, **display_args)
+
+        answer = tty.get_yes_or_no('Do you want to proceed?', default=False)
+        if not answer:
+            tty.die('Will not deprecate any packages.')
+
+    link_fn = os.link if args.link_type == 'hard' else os.symlink
+
+    for dcate, dcator in zip(all_deprecate, all_deprecators):
+        dcate.package.do_deprecate(dcator, link_fn)
diff --git a/lib/spack/spack/cmd/find.py b/lib/spack/spack/cmd/find.py
index 5d6b07f45f..ed8f2ed2bf 100644
--- a/lib/spack/spack/cmd/find.py
+++ b/lib/spack/spack/cmd/find.py
@@ -14,6 +14,7 @@ import spack.repo
 import spack.cmd as cmd
 import spack.cmd.common.arguments as arguments
 from spack.util.string import plural
+from spack.database import InstallStatuses
 
 description = "list and search installed packages"
 section = "basic"
@@ -83,6 +84,12 @@ def setup_parser(subparser):
                            action='store_true',
                            dest='only_missing',
                            help='show only missing dependencies')
+    subparser.add_argument(
+        '--deprecated', action='store_true',
+        help='show deprecated packages as well as installed specs')
+    subparser.add_argument(
+        '--only-deprecated', action='store_true',
+        help='show only deprecated packages')
     subparser.add_argument('-N', '--namespace',
                            action='store_true',
                            help='show fully qualified package names')
@@ -100,18 +107,24 @@ def setup_parser(subparser):
 
 def query_arguments(args):
     # Set up query arguments.
-    installed, known = True, any
-    if args.only_missing:
-        installed = False
-    elif args.missing:
-        installed = any
+    installed = []
+    if not (args.only_missing or args.only_deprecated):
+        installed.append(InstallStatuses.INSTALLED)
+    if (args.deprecated or args.only_deprecated) and not args.only_missing:
+        installed.append(InstallStatuses.DEPRECATED)
+    if (args.missing or args.only_missing) and not args.only_deprecated:
+        installed.append(InstallStatuses.MISSING)
+
+    known = any
     if args.unknown:
         known = False
+
     explicit = any
     if args.explicit:
         explicit = True
     if args.implicit:
         explicit = False
+
     q_args = {'installed': installed, 'known': known, "explicit": explicit}
 
     # Time window of installation
diff --git a/lib/spack/spack/cmd/uninstall.py b/lib/spack/spack/cmd/uninstall.py
index 8ad8dcb4b5..2d903fdd47 100644
--- a/lib/spack/spack/cmd/uninstall.py
+++ b/lib/spack/spack/cmd/uninstall.py
@@ -14,6 +14,7 @@ import spack.package
 import spack.cmd.common.arguments as arguments
 import spack.repo
 import spack.store
+from spack.database import InstallStatuses
 
 from llnl.util import tty
 from llnl.util.tty.colify import colify
@@ -81,7 +82,9 @@ def find_matching_specs(env, specs, allow_multiple_matches=False, force=False):
     specs_from_cli = []
     has_errors = False
     for spec in specs:
-        matching = spack.store.db.query_local(spec, hashes=hashes)
+        install_query = [InstallStatuses.INSTALLED, InstallStatuses.DEPRECATED]
+        matching = spack.store.db.query_local(spec, hashes=hashes,
+                                              installed=install_query)
         # For each spec provided, make sure it refers to only one package.
         # Fail and ask user to be unambiguous if it doesn't
         if not allow_multiple_matches and len(matching) > 1:
diff --git a/lib/spack/spack/database.py b/lib/spack/spack/database.py
index 4d532d1f00..5110e66c7a 100644
--- a/lib/spack/spack/database.py
+++ b/lib/spack/spack/database.py
@@ -46,7 +46,6 @@ from spack.error import SpackError
 from spack.version import Version
 from spack.util.lock import Lock, WriteTransaction, ReadTransaction, LockError
 
-
 # DB goes in this directory underneath the root
 _db_dirname = '.spack-db'
 
@@ -77,6 +76,36 @@ def _autospec(function):
     return converter
 
 
+class InstallStatus(str):
+    pass
+
+
+class InstallStatuses(object):
+    INSTALLED = InstallStatus('installed')
+    DEPRECATED = InstallStatus('deprecated')
+    MISSING = InstallStatus('missing')
+
+    @classmethod
+    def canonicalize(cls, query_arg):
+        if query_arg is True:
+            return [cls.INSTALLED]
+        elif query_arg is False:
+            return [cls.MISSING]
+        elif query_arg is any:
+            return [cls.INSTALLED, cls.DEPRECATED, cls.MISSING]
+        elif isinstance(query_arg, InstallStatus):
+            return [query_arg]
+        else:
+            try:  # Try block catches if it is not an iterable at all
+                if any(type(x) != InstallStatus for x in query_arg):
+                    raise TypeError
+            except TypeError:
+                raise TypeError(
+                    'installation query must be `any`, boolean, '
+                    'InstallStatus, or iterable of InstallStatus')
+            return query_arg
+
+
 class InstallRecord(object):
     """A record represents one installation in the DB.
 
@@ -109,7 +138,8 @@ class InstallRecord(object):
             installed,
             ref_count=0,
             explicit=False,
-            installation_time=None
+            installation_time=None,
+            deprecated_for=None
     ):
         self.spec = spec
         self.path = str(path) if path else None
@@ -117,16 +147,29 @@ class InstallRecord(object):
         self.ref_count = ref_count
         self.explicit = explicit
         self.installation_time = installation_time or _now()
+        self.deprecated_for = deprecated_for
+
+    def install_type_matches(self, installed):
+        installed = InstallStatuses.canonicalize(installed)
+        if self.installed:
+            return InstallStatuses.INSTALLED in installed
+        elif self.deprecated_for:
+            return InstallStatuses.DEPRECATED in installed
+        else:
+            return InstallStatuses.MISSING in installed
 
     def to_dict(self):
-        return {
+        rec_dict = {
             'spec': self.spec.to_node_dict(),
             'path': self.path,
             'installed': self.installed,
             'ref_count': self.ref_count,
             'explicit': self.explicit,
-            'installation_time': self.installation_time
+            'installation_time': self.installation_time,
         }
+        if self.deprecated_for:
+            rec_dict.update({'deprecated_for': self.deprecated_for})
+        return rec_dict
 
     @classmethod
     def from_dict(cls, spec, dictionary):
@@ -136,6 +179,7 @@ class InstallRecord(object):
         # Old databases may have "None" for path for externals
         if d['path'] == 'None':
             d['path'] = None
+
         return InstallRecord(spec, **d)
 
 
@@ -533,13 +577,37 @@ class Database(object):
                 self._data = old_data
                 raise
 
+    def _construct_entry_from_directory_layout(self, directory_layout,
+                                               old_data, spec,
+                                               deprecator=None):
+        # Try to recover explicit value from old DB, but
+        # default it to True if DB was corrupt. This is
+        # just to be conservative in case a command like
+        # "autoremove" is run by the user after a reindex.
+        tty.debug(
+            'RECONSTRUCTING FROM SPEC.YAML: {0}'.format(spec))
+        explicit = True
+        inst_time = os.stat(spec.prefix).st_ctime
+        if old_data is not None:
+            old_info = old_data.get(spec.dag_hash())
+            if old_info is not None:
+                explicit = old_info.explicit
+                inst_time = old_info.installation_time
+
+        extra_args = {
+            'explicit': explicit,
+            'installation_time': inst_time
+        }
+        self._add(spec, directory_layout, **extra_args)
+        if deprecator:
+            self._deprecate(spec, deprecator)
+
     def _construct_from_directory_layout(self, directory_layout, old_data):
         # Read first the `spec.yaml` files in the prefixes. They should be
         # considered authoritative with respect to DB reindexing, as
         # entries in the DB may be corrupted in a way that still makes
         # them readable. If we considered DB entries authoritative
         # instead, we would perpetuate errors over a reindex.
-
         with directory_layout.disable_upstream_check():
             # Initialize data in the reconstructed DB
             self._data = {}
@@ -548,26 +616,14 @@ class Database(object):
             processed_specs = set()
 
             for spec in directory_layout.all_specs():
-                # Try to recover explicit value from old DB, but
-                # default it to True if DB was corrupt. This is
-                # just to be conservative in case a command like
-                # "autoremove" is run by the user after a reindex.
-                tty.debug(
-                    'RECONSTRUCTING FROM SPEC.YAML: {0}'.format(spec))
-                explicit = True
-                inst_time = os.stat(spec.prefix).st_ctime
-                if old_data is not None:
-                    old_info = old_data.get(spec.dag_hash())
-                    if old_info is not None:
-                        explicit = old_info.explicit
-                        inst_time = old_info.installation_time
-
-                extra_args = {
-                    'explicit': explicit,
-                    'installation_time': inst_time
-                }
-                self._add(spec, directory_layout, **extra_args)
+                self._construct_entry_from_directory_layout(directory_layout,
+                                                            old_data, spec)
+                processed_specs.add(spec)
 
+            for spec, deprecator in directory_layout.all_deprecated_specs():
+                self._construct_entry_from_directory_layout(directory_layout,
+                                                            old_data, spec,
+                                                            deprecator)
                 processed_specs.add(spec)
 
             for key, entry in old_data.items():
@@ -625,6 +681,10 @@ class Database(object):
                 counts.setdefault(dep_key, 0)
                 counts[dep_key] += 1
 
+            if rec.deprecated_for:
+                counts.setdefault(rec.deprecated_for, 0)
+                counts[rec.deprecated_for] += 1
+
         for rec in self._data.values():
             key = rec.spec.dag_hash()
             expected = counts[key]
@@ -761,7 +821,7 @@ class Database(object):
                     installed = True
                 except DirectoryLayoutError as e:
                     tty.warn(
-                        'Dependency missing due to corrupt install directory:',
+                        'Dependency missing: may be deprecated or corrupted:',
                         path, str(e))
             elif spec.external_path:
                 path = spec.external_path
@@ -840,6 +900,15 @@ class Database(object):
             for dep in spec.dependencies(_tracked_deps):
                 self._decrement_ref_count(dep)
 
+    def _increment_ref_count(self, spec):
+        key = spec.dag_hash()
+
+        if key not in self._data:
+            return
+
+        rec = self._data[key]
+        rec.ref_count += 1
+
     def _remove(self, spec):
         """Non-locking version of remove(); does real work.
         """
@@ -854,6 +923,10 @@ class Database(object):
         for dep in rec.spec.dependencies(_tracked_deps):
             self._decrement_ref_count(dep)
 
+        if rec.deprecated_for:
+            new_spec = self._data[rec.deprecated_for].spec
+            self._decrement_ref_count(new_spec)
+
         # Returns the concrete spec so we know it in the case where a
         # query spec was passed in.
         return rec.spec
@@ -874,6 +947,46 @@ class Database(object):
         with self.write_transaction():
             return self._remove(spec)
 
+    def deprecator(self, spec):
+        """Return the spec that the given spec is deprecated for, or None"""
+        with self.read_transaction():
+            spec_key = self._get_matching_spec_key(spec)
+            spec_rec = self._data[spec_key]
+
+            if spec_rec.deprecated_for:
+                return self._data[spec_rec.deprecated_for].spec
+            else:
+                return None
+
+    def specs_deprecated_by(self, spec):
+        """Return all specs deprecated in favor of the given spec"""
+        with self.read_transaction():
+            return [rec.spec for rec in self._data.values()
+                    if rec.deprecated_for == spec.dag_hash()]
+
+    def _deprecate(self, spec, deprecator):
+        spec_key = self._get_matching_spec_key(spec)
+        spec_rec = self._data[spec_key]
+
+        deprecator_key = self._get_matching_spec_key(deprecator)
+
+        self._increment_ref_count(deprecator)
+
+        # If spec was already deprecated, update old deprecator's ref count
+        if spec_rec.deprecated_for:
+            old_repl_rec = self._data[spec_rec.deprecated_for]
+            self._decrement_ref_count(old_repl_rec.spec)
+
+        spec_rec.deprecated_for = deprecator_key
+        spec_rec.installed = False
+        self._data[spec_key] = spec_rec
+
+    @_autospec
+    def deprecate(self, spec, deprecator):
+        """Marks a spec as deprecated in favor of its deprecator"""
+        with self.write_transaction():
+            return self._deprecate(spec, deprecator)
+
     @_autospec
     def installed_relatives(self, spec, direction='children', transitive=True,
                             deptype='all'):
@@ -944,9 +1057,13 @@ class Database(object):
             dag_hash (str): hash (or hash prefix) to look up
             default (object, optional): default value to return if dag_hash is
                 not in the DB (default: None)
-            installed (bool or any, optional): if ``True``, includes only
-                installed specs in the search; if ``False`` only missing specs,
-                and if ``any``, either installed or missing (default: any)
+            installed (bool or any, or InstallStatus or iterable of
+                InstallStatus, optional): if ``True``, includes only installed
+                specs in the search; if ``False`` only missing specs, and if
+                ``any``, all specs in database. If an InstallStatus or iterable
+                of InstallStatus, returns specs whose install status
+                (installed, deprecated, or missing) matches (one of) the
+                InstallStatus. (default: any)
 
         ``installed`` defaults to ``any`` so that we can refer to any
         known hash.  Note that ``query()`` and ``query_one()`` differ in
@@ -960,7 +1077,7 @@ class Database(object):
             # hash is a full hash and is in the data somewhere
             if dag_hash in self._data:
                 rec = self._data[dag_hash]
-                if installed is any or rec.installed == installed:
+                if rec.install_type_matches(installed):
                     return [rec.spec]
                 else:
                     return default
@@ -969,7 +1086,7 @@ class Database(object):
             # installed) spec.
             matches = [record.spec for h, record in self._data.items()
                        if h.startswith(dag_hash) and
-                       (installed is any or installed == record.installed)]
+                       record.install_type_matches(installed)]
             if matches:
                 return matches
 
@@ -983,9 +1100,13 @@ class Database(object):
             dag_hash (str): hash (or hash prefix) to look up
             default (object, optional): default value to return if dag_hash is
                 not in the DB (default: None)
-            installed (bool or any, optional): if ``True``, includes only
-                installed specs in the search; if ``False`` only missing specs,
-                and if ``any``, either installed or missing (default: any)
+            installed (bool or any, or InstallStatus or iterable of
+                InstallStatus, optional): if ``True``, includes only installed
+                specs in the search; if ``False`` only missing specs, and if
+                ``any``, all specs in database. If an InstallStatus or iterable
+                of InstallStatus, returns specs whose install status
+                (installed, deprecated, or missing) matches (one of) the
+                InstallStatus. (default: any)
 
         ``installed`` defaults to ``any`` so that we can refer to any
         known hash.  Note that ``query()`` and ``query_one()`` differ in
@@ -1030,10 +1151,13 @@ class Database(object):
                 Spack, but have since either changed their name or
                 been removed
 
-            installed (bool or any, optional): Specs for which a prefix exists
-                are "installed". A spec that is NOT installed will be in the
-                database if some other spec depends on it but its installation
-                has gone away since Spack installed it.
+            installed (bool or any, or InstallStatus or iterable of
+                InstallStatus, optional): if ``True``, includes only installed
+                specs in the search; if ``False`` only missing specs, and if
+                ``any``, all specs in database. If an InstallStatus or iterable
+                of InstallStatus, returns specs whose install status
+                (installed, deprecated, or missing) matches (one of) the
+                InstallStatus. (default: True)
 
             explicit (bool or any, optional): A spec that was installed
                 following a specific user request is marked as explicit. If
@@ -1078,7 +1202,7 @@ class Database(object):
             if hashes is not None and rec.spec.dag_hash() not in hashes:
                 continue
 
-            if installed is not any and rec.installed != installed:
+            if not rec.install_type_matches(installed):
                 continue
 
             if explicit is not any and rec.explicit != explicit:
diff --git a/lib/spack/spack/directory_layout.py b/lib/spack/spack/directory_layout.py
index a48b841147..f8a42bf42b 100644
--- a/lib/spack/spack/directory_layout.py
+++ b/lib/spack/spack/directory_layout.py
@@ -90,14 +90,23 @@ class DirectoryLayout(object):
         assert(not path.startswith(self.root))
         return os.path.join(self.root, path)
 
-    def remove_install_directory(self, spec):
+    def remove_install_directory(self, spec, deprecated=False):
         """Removes a prefix and any empty parent directories from the root.
            Raised RemoveFailedError if something goes wrong.
         """
         path = self.path_for_spec(spec)
         assert(path.startswith(self.root))
 
-        if os.path.exists(path):
+        if deprecated:
+            if os.path.exists(path):
+                try:
+                    metapath = self.deprecated_file_path(spec)
+                    os.unlink(path)
+                    os.remove(metapath)
+                except OSError as e:
+                    raise RemoveFailedError(spec, path, e)
+
+        elif os.path.exists(path):
             try:
                 shutil.rmtree(path)
             except OSError as e:
@@ -191,6 +200,7 @@ class YamlDirectoryLayout(DirectoryLayout):
         # If any of these paths change, downstream databases may not be able to
         # locate files in older upstream databases
         self.metadata_dir        = '.spack'
+        self.deprecated_dir      = 'deprecated'
         self.spec_file_name      = 'spec.yaml'
         self.extension_file_name = 'extensions.yaml'
         self.packages_dir        = 'repos'  # archive of package.py files
@@ -232,6 +242,30 @@ class YamlDirectoryLayout(DirectoryLayout):
         _check_concrete(spec)
         return os.path.join(self.metadata_path(spec), self.spec_file_name)
 
+    def deprecated_file_name(self, spec):
+        """Gets name of deprecated spec file in deprecated dir"""
+        _check_concrete(spec)
+        return spec.dag_hash() + '_' + self.spec_file_name
+
+    def deprecated_file_path(self, deprecated_spec, deprecator_spec=None):
+        """Gets full path to spec file for deprecated spec
+
+        If the deprecator_spec is provided, use that. Otherwise, assume
+        deprecated_spec is already deprecated and its prefix links to the
+        prefix of its deprecator."""
+        _check_concrete(deprecated_spec)
+        if deprecator_spec:
+            _check_concrete(deprecator_spec)
+
+        # If deprecator spec is None, assume deprecated_spec already deprecated
+        # and use its link to find the file.
+        base_dir = self.path_for_spec(
+            deprecator_spec
+        ) if deprecator_spec else os.readlink(deprecated_spec.prefix)
+
+        return os.path.join(base_dir, self.metadata_dir, self.deprecated_dir,
+                            self.deprecated_file_name(deprecated_spec))
+
     @contextmanager
     def disable_upstream_check(self):
         self.check_upstream = False
@@ -307,6 +341,20 @@ class YamlDirectoryLayout(DirectoryLayout):
         spec_files = glob.glob(pattern)
         return [self.read_spec(s) for s in spec_files]
 
+    def all_deprecated_specs(self):
+        if not os.path.isdir(self.root):
+            return []
+
+        path_elems = ["*"] * len(self.path_scheme.split(os.sep))
+        path_elems += [self.metadata_dir, self.deprecated_dir,
+                       '*_' + self.spec_file_name]
+        pattern = os.path.join(self.root, *path_elems)
+        spec_files = glob.glob(pattern)
+        get_depr_spec_file = lambda x: os.path.join(
+            os.path.dirname(os.path.dirname(x)), self.spec_file_name)
+        return set((self.read_spec(s), self.read_spec(get_depr_spec_file(s)))
+                   for s in spec_files)
+
     def specs_by_hash(self):
         by_hash = {}
         for spec in self.all_specs():
diff --git a/lib/spack/spack/package.py b/lib/spack/spack/package.py
index e3d4f1b6e9..b49c8c1a23 100644
--- a/lib/spack/spack/package.py
+++ b/lib/spack/spack/package.py
@@ -2112,14 +2112,19 @@ class PackageBase(with_metaclass(PackageMeta, PackageViewMixin, object)):
             raise NotImplementedError(msg)
 
     @staticmethod
-    def uninstall_by_spec(spec, force=False):
+    def uninstall_by_spec(spec, force=False, deprecator=None):
         if not os.path.isdir(spec.prefix):
             # prefix may not exist, but DB may be inconsistent. Try to fix by
             # removing, but omit hooks.
             specs = spack.store.db.query(spec, installed=True)
             if specs:
-                spack.store.db.remove(specs[0])
-                tty.msg("Removed stale DB entry for %s" % spec.short_spec)
+                if deprecator:
+                    spack.store.db.deprecate(specs[0], deprecator)
+                    tty.msg("Deprecating stale DB entry for "
+                            "%s" % spec.short_spec)
+                else:
+                    spack.store.db.remove(specs[0])
+                    tty.msg("Removed stale DB entry for %s" % spec.short_spec)
                 return
             else:
                 raise InstallError(str(spec) + " is not installed.")
@@ -2130,7 +2135,7 @@ class PackageBase(with_metaclass(PackageMeta, PackageViewMixin, object)):
             if dependents:
                 raise PackageStillNeededError(spec, dependents)
 
-        # Try to get the pcakage for the spec
+        # Try to get the package for the spec
         try:
             pkg = spec.package
         except spack.repo.UnknownEntityError:
@@ -2146,11 +2151,19 @@ class PackageBase(with_metaclass(PackageMeta, PackageViewMixin, object)):
             if not spec.external:
                 msg = 'Deleting package prefix [{0}]'
                 tty.debug(msg.format(spec.short_spec))
-                spack.store.layout.remove_install_directory(spec)
+                # test if spec is already deprecated, not whether we want to
+                # deprecate it now
+                deprecated = bool(spack.store.db.deprecator(spec))
+                spack.store.layout.remove_install_directory(spec, deprecated)
             # Delete DB entry
-            msg = 'Deleting DB entry [{0}]'
-            tty.debug(msg.format(spec.short_spec))
-            spack.store.db.remove(spec)
+            if deprecator:
+                msg = 'deprecating DB entry [{0}] in favor of [{1}]'
+                tty.debug(msg.format(spec.short_spec, deprecator.short_spec))
+                spack.store.db.deprecate(spec, deprecator)
+            else:
+                msg = 'Deleting DB entry [{0}]'
+                tty.debug(msg.format(spec.short_spec))
+                spack.store.db.remove(spec)
 
         if pkg is not None:
             spack.hooks.post_uninstall(spec)
@@ -2162,6 +2175,64 @@ class PackageBase(with_metaclass(PackageMeta, PackageViewMixin, object)):
         # delegate to instance-less method.
         Package.uninstall_by_spec(self.spec, force)
 
+    def do_deprecate(self, deprecator, link_fn):
+        """Deprecate this package in favor of deprecator spec"""
+        spec = self.spec
+
+        # Check whether package to deprecate has active extensions
+        if self.extendable:
+            view = spack.filesystem_view.YamlFilesystemView(spec.prefix,
+                                                            spack.store.layout)
+            active_exts = view.extensions_layout.extension_map(spec).values()
+            if active_exts:
+                short = spec.format('{name}/{hash:7}')
+                m = "Spec %s has active extensions\n" % short
+                for active in active_exts:
+                    m += '        %s\n' % active.format('{name}/{hash:7}')
+                    m += "Deactivate extensions before deprecating %s" % short
+                tty.die(m)
+
+        # Check whether package to deprecate is an active extension
+        if self.is_extension:
+            extendee = self.extendee_spec
+            view = spack.filesystem_view.YamlFilesystemView(extendee.prefix,
+                                                            spack.store.layout)
+
+            if self.is_activated(view):
+                short = spec.format('{name}/{hash:7}')
+                short_ext = extendee.format('{name}/{hash:7}')
+                msg = "Spec %s is an active extension of %s\n" % (short,
+                                                                  short_ext)
+                msg += "Deactivate %s to be able to deprecate it" % short
+                tty.die(msg)
+
+        # Install deprecator if it isn't installed already
+        if not spack.store.db.query(deprecator):
+            deprecator.package.do_install()
+
+        old_deprecator = spack.store.db.deprecator(spec)
+        if old_deprecator:
+            # Find this specs yaml file from its old deprecation
+            self_yaml = spack.store.layout.deprecated_file_path(spec,
+                                                                old_deprecator)
+        else:
+            self_yaml = spack.store.layout.spec_file_path(spec)
+
+        # copy spec metadata to "deprecated" dir of deprecator
+        depr_yaml = spack.store.layout.deprecated_file_path(spec,
+                                                            deprecator)
+        fs.mkdirp(os.path.dirname(depr_yaml))
+        shutil.copy2(self_yaml, depr_yaml)
+
+        # Any specs deprecated in favor of this spec are re-deprecated in
+        # favor of its new deprecator
+        for deprecated in spack.store.db.specs_deprecated_by(spec):
+            deprecated.package.do_deprecate(deprecator, link_fn)
+
+        # Now that we've handled metadata, uninstall and replace with link
+        Package.uninstall_by_spec(spec, force=True, deprecator=deprecator)
+        link_fn(deprecator.prefix, spec.prefix)
+
     def _check_extendable(self):
         if not self.extendable:
             raise ValueError("Package %s is not extendable!" % self.name)
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index cb4942b157..050f027679 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -2241,6 +2241,21 @@ class Spec(object):
         # Mark everything in the spec as concrete, as well.
         self._mark_concrete()
 
+        # If any spec in the DAG is deprecated, throw an error
+        deprecated = []
+        for x in self.traverse():
+            _, rec = spack.store.db.query_by_spec_hash(x.dag_hash())
+            if rec and rec.deprecated_for:
+                deprecated.append(rec)
+        if deprecated:
+            msg = "\n    The following specs have been deprecated"
+            msg += " in favor of specs with the hashes shown:\n"
+            for rec in deprecated:
+                msg += '        %s  --> %s\n' % (rec.spec, rec.deprecated_for)
+            msg += '\n'
+            msg += "    For each package listed, choose another spec\n"
+            raise SpecDeprecatedError(msg)
+
         # Now that the spec is concrete we should check if
         # there are declared conflicts
         #
@@ -4493,3 +4508,7 @@ class ConflictsInSpecError(SpecError, RuntimeError):
 class SpecDependencyNotFoundError(SpecError):
     """Raised when a failure is encountered writing the dependencies of
     a spec."""
+
+
+class SpecDeprecatedError(SpecError):
+    """Raised when a spec concretizes to a deprecated spec or dependency."""
diff --git a/lib/spack/spack/test/cmd/deprecate.py b/lib/spack/spack/test/cmd/deprecate.py
new file mode 100644
index 0000000000..6bc87fa5e3
--- /dev/null
+++ b/lib/spack/spack/test/cmd/deprecate.py
@@ -0,0 +1,192 @@
+# 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)
+import pytest
+from spack.main import SpackCommand
+import spack.store
+from spack.database import InstallStatuses
+
+install = SpackCommand('install')
+uninstall = SpackCommand('uninstall')
+deprecate = SpackCommand('deprecate')
+find = SpackCommand('find')
+activate = SpackCommand('activate')
+
+
+def test_deprecate(mock_packages, mock_archive, mock_fetch, install_mockery):
+    install('libelf@0.8.13')
+    install('libelf@0.8.10')
+
+    all_installed = spack.store.db.query()
+    assert len(all_installed) == 2
+
+    deprecate('-y', 'libelf@0.8.10', 'libelf@0.8.13')
+
+    non_deprecated = spack.store.db.query()
+    all_available = spack.store.db.query(installed=any)
+    assert all_available == all_installed
+    assert non_deprecated == spack.store.db.query('libelf@0.8.13')
+
+
+def test_deprecate_fails_no_such_package(mock_packages, mock_archive,
+                                         mock_fetch, install_mockery):
+    """Tests that deprecating a spec that is not installed fails.
+
+    Tests that deprecating without the ``-i`` option in favor of a spec that
+    is not installed fails."""
+    output = deprecate('-y', 'libelf@0.8.10', 'libelf@0.8.13',
+                       fail_on_error=False)
+    assert "Spec 'libelf@0.8.10' matches no installed packages" in output
+
+    install('libelf@0.8.10')
+
+    output = deprecate('-y', 'libelf@0.8.10', 'libelf@0.8.13',
+                       fail_on_error=False)
+    assert "Spec 'libelf@0.8.13' matches no installed packages" in output
+
+
+def test_deprecate_install(mock_packages, mock_archive, mock_fetch,
+                           install_mockery):
+    """Tests that the ```-i`` option allows us to deprecate in favor of a spec
+    that is not yet installed."""
+    install('libelf@0.8.10')
+
+    to_deprecate = spack.store.db.query()
+    assert len(to_deprecate) == 1
+
+    deprecate('-y', '-i', 'libelf@0.8.10', 'libelf@0.8.13')
+
+    non_deprecated = spack.store.db.query()
+    deprecated = spack.store.db.query(installed=InstallStatuses.DEPRECATED)
+    assert deprecated == to_deprecate
+    assert len(non_deprecated) == 1
+    assert non_deprecated[0].satisfies('libelf@0.8.13')
+
+
+def test_deprecate_deps(mock_packages, mock_archive, mock_fetch,
+                        install_mockery):
+    """Test that the deprecate command deprecates all dependencies properly."""
+    install('libdwarf@20130729 ^libelf@0.8.13')
+    install('libdwarf@20130207 ^libelf@0.8.10')
+
+    new_spec = spack.spec.Spec('libdwarf@20130729^libelf@0.8.13').concretized()
+    old_spec = spack.spec.Spec('libdwarf@20130207^libelf@0.8.10').concretized()
+
+    all_installed = spack.store.db.query()
+
+    deprecate('-y', '-d', 'libdwarf@20130207', 'libdwarf@20130729')
+
+    non_deprecated = spack.store.db.query()
+    all_available = spack.store.db.query(installed=any)
+    deprecated = spack.store.db.query(installed=InstallStatuses.DEPRECATED)
+
+    assert all_available == all_installed
+    assert sorted(all_available) == sorted(deprecated + non_deprecated)
+
+    assert sorted(non_deprecated) == sorted(list(new_spec.traverse()))
+    assert sorted(deprecated) == sorted(list(old_spec.traverse()))
+
+
+def test_deprecate_fails_active_extensions(mock_packages, mock_archive,
+                                           mock_fetch, install_mockery):
+    """Tests that active extensions and their extendees cannot be
+    deprecated."""
+    install('extendee')
+    install('extension1')
+    activate('extension1')
+
+    output = deprecate('-yi', 'extendee', 'extendee@nonexistent',
+                       fail_on_error=False)
+    assert 'extension1' in output
+    assert "Deactivate extensions before deprecating" in output
+
+    output = deprecate('-yiD', 'extension1', 'extension1@notaversion',
+                       fail_on_error=False)
+    assert 'extendee' in output
+    assert 'is an active extension of' in output
+
+
+def test_uninstall_deprecated(mock_packages, mock_archive, mock_fetch,
+                              install_mockery):
+    """Tests that we can still uninstall deprecated packages."""
+    install('libelf@0.8.13')
+    install('libelf@0.8.10')
+
+    deprecate('-y', 'libelf@0.8.10', 'libelf@0.8.13')
+
+    non_deprecated = spack.store.db.query()
+
+    uninstall('-y', 'libelf@0.8.10')
+
+    assert spack.store.db.query() == spack.store.db.query(installed=any)
+    assert spack.store.db.query() == non_deprecated
+
+
+def test_deprecate_already_deprecated(mock_packages, mock_archive, mock_fetch,
+                                      install_mockery):
+    """Tests that we can re-deprecate a spec to change its deprecator."""
+    install('libelf@0.8.13')
+    install('libelf@0.8.12')
+    install('libelf@0.8.10')
+
+    deprecated_spec = spack.spec.Spec('libelf@0.8.10').concretized()
+
+    deprecate('-y', 'libelf@0.8.10', 'libelf@0.8.12')
+
+    deprecator = spack.store.db.deprecator(deprecated_spec)
+    assert deprecator == spack.spec.Spec('libelf@0.8.12').concretized()
+
+    deprecate('-y', 'libelf@0.8.10', 'libelf@0.8.13')
+
+    non_deprecated = spack.store.db.query()
+    all_available = spack.store.db.query(installed=any)
+    assert len(non_deprecated) == 2
+    assert len(all_available) == 3
+
+    deprecator = spack.store.db.deprecator(deprecated_spec)
+    assert deprecator == spack.spec.Spec('libelf@0.8.13').concretized()
+
+
+def test_deprecate_deprecator(mock_packages, mock_archive, mock_fetch,
+                              install_mockery):
+    """Tests that when a deprecator spec is deprecated, its deprecatee specs
+    are updated to point to the new deprecator."""
+    install('libelf@0.8.13')
+    install('libelf@0.8.12')
+    install('libelf@0.8.10')
+
+    first_deprecated_spec = spack.spec.Spec('libelf@0.8.10').concretized()
+    second_deprecated_spec = spack.spec.Spec('libelf@0.8.12').concretized()
+    final_deprecator = spack.spec.Spec('libelf@0.8.13').concretized()
+
+    deprecate('-y', 'libelf@0.8.10', 'libelf@0.8.12')
+
+    deprecator = spack.store.db.deprecator(first_deprecated_spec)
+    assert deprecator == second_deprecated_spec
+
+    deprecate('-y', 'libelf@0.8.12', 'libelf@0.8.13')
+
+    non_deprecated = spack.store.db.query()
+    all_available = spack.store.db.query(installed=any)
+    assert len(non_deprecated) == 1
+    assert len(all_available) == 3
+
+    first_deprecator = spack.store.db.deprecator(first_deprecated_spec)
+    assert first_deprecator == final_deprecator
+    second_deprecator = spack.store.db.deprecator(second_deprecated_spec)
+    assert second_deprecator == final_deprecator
+
+
+def test_concretize_deprecated(mock_packages, mock_archive, mock_fetch,
+                               install_mockery):
+    """Tests that the concretizer throws an error if we concretize to a
+    deprecated spec"""
+    install('libelf@0.8.13')
+    install('libelf@0.8.10')
+
+    deprecate('-y', 'libelf@0.8.10', 'libelf@0.8.13')
+
+    spec = spack.spec.Spec('libelf@0.8.10')
+    with pytest.raises(spack.spec.SpecDeprecatedError):
+        spec.concretize()
diff --git a/lib/spack/spack/test/cmd/find.py b/lib/spack/spack/test/cmd/find.py
index 55706c264c..45b065fce9 100644
--- a/lib/spack/spack/test/cmd/find.py
+++ b/lib/spack/spack/test/cmd/find.py
@@ -50,6 +50,8 @@ def test_query_arguments():
     args = Bunch(
         only_missing=False,
         missing=False,
+        only_deprecated=False,
+        deprecated=False,
         unknown=False,
         explicit=False,
         implicit=False,
@@ -61,7 +63,7 @@ def test_query_arguments():
     assert 'installed' in q_args
     assert 'known' in q_args
     assert 'explicit' in q_args
-    assert q_args['installed'] is True
+    assert q_args['installed'] == ['installed']
     assert q_args['known'] is any
     assert q_args['explicit'] is any
     assert 'start_date' in q_args
diff --git a/lib/spack/spack/test/cmd/reindex.py b/lib/spack/spack/test/cmd/reindex.py
new file mode 100644
index 0000000000..0ee36b3001
--- /dev/null
+++ b/lib/spack/spack/test/cmd/reindex.py
@@ -0,0 +1,53 @@
+# 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)
+import os
+from spack.main import SpackCommand
+import spack.store
+
+install = SpackCommand('install')
+deprecate = SpackCommand('deprecate')
+reindex = SpackCommand('reindex')
+
+
+def test_reindex_basic(mock_packages, mock_archive, mock_fetch,
+                       install_mockery):
+    install('libelf@0.8.13')
+    install('libelf@0.8.12')
+
+    all_installed = spack.store.db.query()
+
+    reindex()
+
+    assert spack.store.db.query() == all_installed
+
+
+def test_reindex_db_deleted(mock_packages, mock_archive, mock_fetch,
+                            install_mockery):
+    install('libelf@0.8.13')
+    install('libelf@0.8.12')
+
+    all_installed = spack.store.db.query()
+
+    os.remove(spack.store.db._index_path)
+    reindex()
+
+    assert spack.store.db.query() == all_installed
+
+
+def test_reindex_with_deprecated_packages(mock_packages, mock_archive,
+                                          mock_fetch, install_mockery):
+    install('libelf@0.8.13')
+    install('libelf@0.8.12')
+
+    deprecate('-y', 'libelf@0.8.12', 'libelf@0.8.13')
+
+    all_installed = spack.store.db.query(installed=any)
+    non_deprecated = spack.store.db.query(installed=True)
+
+    os.remove(spack.store.db._index_path)
+    reindex()
+
+    assert spack.store.db.query(installed=any) == all_installed
+    assert spack.store.db.query(installed=True) == non_deprecated
diff --git a/lib/spack/spack/test/database.py b/lib/spack/spack/test/database.py
index 6938b5d0f0..099894e0d2 100644
--- a/lib/spack/spack/test/database.py
+++ b/lib/spack/spack/test/database.py
@@ -437,6 +437,16 @@ def test_025_reindex(mutable_database):
     _check_db_sanity(mutable_database)
 
 
+def test_026_reindex_after_deprecate(mutable_database):
+    """Make sure reindex works and ref counts are valid after deprecation."""
+    mpich = mutable_database.query_one('mpich')
+    zmpi = mutable_database.query_one('zmpi')
+    mutable_database.deprecate(mpich, zmpi)
+
+    spack.store.store.reindex()
+    _check_db_sanity(mutable_database)
+
+
 def test_030_db_sanity_from_another_process(mutable_database):
     def read_and_modify():
         # check that other process can read DB
@@ -458,6 +468,15 @@ def test_040_ref_counts(database):
     database._check_ref_counts()
 
 
+def test_041_ref_counts_deprecate(mutable_database):
+    """Ensure that we have appropriate ref counts after deprecating"""
+    mpich = mutable_database.query_one('mpich')
+    zmpi = mutable_database.query_one('zmpi')
+
+    mutable_database.deprecate(mpich, zmpi)
+    mutable_database._check_ref_counts()
+
+
 def test_050_basic_query(database):
     """Ensure querying database is consistent with what is installed."""
     # query everything