Spack can automatically remove unused specs (#13534)

* Spack can uninstall unused specs

fixes #4382

Added an option to spack uninstall that removes all unused specs i.e.
build dependencies or transitive dependencies that are left
in the store after the specs that pulled them in have been removed.

* Moved the functionality to its own command

The command has been named 'spack autoremove' to follow the naming used
for the same functionality by other widely known package managers i.e.
yum and apt.

* Speed-up autoremoving specs by not locking and re-reading the scratch DB

* Make autoremove work directly on Spack's store

* Added unit tests for the new command

* Display a terser output to the user

* Renamed the "autoremove" command "gc"

Following discussion there's more consensus around
the latter name.

* Preserve root specs in env contexts

* Instead of preserving specs, restrict gc to the active environment

* Added docs

* Added a unit test for gc within an environment

* Updated copyright to 2020

* Updated documentation according to review

Rephrased a couple of sentences, added references to
`spack find` and dependency types.

* Updated function naming and docstrings

* Simplified computation of unused specs

Since the new approach uses private attributes of the DB
it has been coded as a method of that class rather than a
freestanding function.

7 files changed, 193 insertions, 7 deletions

diff --git a/lib/spack/docs/basic_usage.rst b/lib/spack/docs/basic_usage.rst
index d66745e4a0..3ad83c57bd 100644
--- a/lib/spack/docs/basic_usage.rst
+++ b/lib/spack/docs/basic_usage.rst
@@ -232,6 +232,50 @@ remove dependent packages *before* removing their dependencies or use the
 
 .. _nondownloadable:
 
+^^^^^^^^^^^^^^^^^^
+Garbage collection
+^^^^^^^^^^^^^^^^^^
+
+When Spack builds software from sources, if often installs tools that are needed
+just to build or test other software. These are not necessary at runtime.
+To support cases where removing these tools can be a benefit Spack provides
+the ``spack gc`` ("garbage collector") command, which will uninstall all unneeded packages:
+
+.. code-block:: console
+
+   $ spack find
+   ==> 24 installed packages
+   -- linux-ubuntu18.04-broadwell / gcc@9.0.1 ----------------------
+   autoconf@2.69    findutils@4.6.0  libiconv@1.16        libszip@2.1.1  m4@1.4.18    openjpeg@2.3.1  pkgconf@1.6.3  util-macros@1.19.1
+   automake@1.16.1  gdbm@1.18.1      libpciaccess@0.13.5  libtool@2.4.6  mpich@3.3.2  openssl@1.1.1d  readline@8.0   xz@5.2.4
+   cmake@3.16.1     hdf5@1.10.5      libsigsegv@2.12      libxml2@2.9.9  ncurses@6.1  perl@5.30.0     texinfo@6.5    zlib@1.2.11
+
+   $ spack gc
+   ==> The following packages will be uninstalled:
+
+       -- linux-ubuntu18.04-broadwell / gcc@9.0.1 ----------------------
+       vn47edz autoconf@2.69    6m3f2qn findutils@4.6.0  ubl6bgk libtool@2.4.6  pksawhz openssl@1.1.1d  urdw22a readline@8.0
+       ki6nfw5 automake@1.16.1  fklde6b gdbm@1.18.1      b6pswuo m4@1.4.18      k3s2csy perl@5.30.0     lp5ya3t texinfo@6.5
+       ylvgsov cmake@3.16.1     5omotir libsigsegv@2.12  leuzbbh ncurses@6.1    5vmfbrq pkgconf@1.6.3   5bmv4tg util-macros@1.19.1
+
+   ==> Do you want to proceed? [y/N] y
+
+   [ ... ]
+
+   $ spack find
+   ==> 9 installed packages
+   -- linux-ubuntu18.04-broadwell / gcc@9.0.1 ----------------------
+   hdf5@1.10.5  libiconv@1.16  libpciaccess@0.13.5  libszip@2.1.1  libxml2@2.9.9  mpich@3.3.2  openjpeg@2.3.1  xz@5.2.4  zlib@1.2.11
+
+In the example above Spack went through all the packages in the DB
+and removed everything that is not either:
+
+1. A package installed upon explicit request of the user
+2. A ``link`` or ``run`` dependency, even transitive, of one of the packages at point 1.
+
+You can check :ref:`cmd-spack-find-metadata` to see how to query for explicitly installed packages
+or :ref:`dependency-types` for a more thorough treatment of dependency types.
+
 ^^^^^^^^^^^^^^^^^^^^^^^^^
 Non-Downloadable Tarballs
 ^^^^^^^^^^^^^^^^^^^^^^^^^
@@ -414,6 +458,8 @@ Packages are divided into groups according to their architecture and
 compiler.  Within each group, Spack tries to keep the view simple, and
 only shows the version of installed packages.
 
+.. _cmd-spack-find-metadata:
+
 """"""""""""""""""""""""""""""""
 Viewing more metadata
 """"""""""""""""""""""""""""""""
diff --git a/lib/spack/docs/packaging_guide.rst b/lib/spack/docs/packaging_guide.rst
index 1d701c8551..223c509ac1 100644
--- a/lib/spack/docs/packaging_guide.rst
+++ b/lib/spack/docs/packaging_guide.rst
@@ -1950,6 +1950,8 @@ issues with 1.64.0, 1.65.0, and 1.66.0, you can say:
    depends_on('boost@1.59.0:1.63,1.65.1,1.67.0:')
 
 
+.. _dependency-types:
+
 ^^^^^^^^^^^^^^^^
 Dependency types
 ^^^^^^^^^^^^^^^^
diff --git a/lib/spack/spack/cmd/gc.py b/lib/spack/spack/cmd/gc.py
new file mode 100644
index 0000000000..ca9d88169a
--- /dev/null
+++ b/lib/spack/spack/cmd/gc.py
@@ -0,0 +1,47 @@
+# Copyright 2013-2020 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 llnl.util.tty as tty
+
+import spack.cmd.common.arguments
+import spack.cmd.uninstall
+import spack.environment
+import spack.store
+
+description = "remove specs that are now no longer needed"
+section = "build"
+level = "short"
+
+
+def setup_parser(subparser):
+    spack.cmd.common.arguments.add_common_arguments(subparser, ['yes_to_all'])
+
+
+def gc(parser, args):
+    specs = spack.store.db.unused_specs
+
+    # Restrict garbage collection to the active environment
+    # speculating over roots that are yet to be installed
+    env = spack.environment.get_env(args=None, cmd_name='gc')
+    if env:
+        msg = 'Restricting the garbage collection to the "{0}" environment'
+        tty.msg(msg.format(env.name))
+        env.concretize()
+        roots = [s for s in env.roots()]
+        all_hashes = set([s.dag_hash() for r in roots for s in r.traverse()])
+        lr_hashes = set([s.dag_hash() for r in roots
+                         for s in r.traverse(deptype=('link', 'run'))])
+        maybe_to_be_removed = all_hashes - lr_hashes
+        specs = [s for s in specs if s.dag_hash() in maybe_to_be_removed]
+
+    if not specs:
+        msg = "There are no unused specs. Spack's store is clean."
+        tty.msg(msg)
+        return
+
+    if not args.yes_to_all:
+        spack.cmd.uninstall.confirm_removal(specs)
+
+    spack.cmd.uninstall.do_uninstall(None, specs, force=False)
diff --git a/lib/spack/spack/cmd/uninstall.py b/lib/spack/spack/cmd/uninstall.py
index df69330b96..906da8d3b3 100644
--- a/lib/spack/spack/cmd/uninstall.py
+++ b/lib/spack/spack/cmd/uninstall.py
@@ -6,6 +6,7 @@
 from __future__ import print_function
 
 import argparse
+import sys
 
 import spack.cmd
 import spack.environment as ev
@@ -31,8 +32,8 @@ error_message = """You can either:
 # Arguments for display_specs when we find ambiguity
 display_args = {
     'long': True,
-    'show_flags': True,
-    'variants': True,
+    'show_flags': False,
+    'variants': False,
     'indent': 4,
 }
 
@@ -324,11 +325,7 @@ def uninstall_specs(args, specs):
         return
 
     if not args.yes_to_all:
-        tty.msg('The following packages will be uninstalled:\n')
-        spack.cmd.display_specs(anything_to_do, **display_args)
-        answer = tty.get_yes_or_no('Do you want to proceed?', default=False)
-        if not answer:
-            tty.die('Will not uninstall any packages.')
+        confirm_removal(anything_to_do)
 
     # just force-remove things in the remove list
     for spec in remove_list:
@@ -338,6 +335,21 @@ def uninstall_specs(args, specs):
     do_uninstall(env, uninstall_list, args.force)
 
 
+def confirm_removal(specs):
+    """Display the list of specs to be removed and ask for confirmation.
+
+    Args:
+        specs (list): specs to be removed
+    """
+    tty.msg('The following packages will be uninstalled:\n')
+    spack.cmd.display_specs(specs, **display_args)
+    print('')
+    answer = tty.get_yes_or_no('Do you want to proceed?', default=False)
+    if not answer:
+        tty.msg('Aborting uninstallation')
+        sys.exit(0)
+
+
 def uninstall(parser, args):
     if not args.packages and not args.all:
         tty.die('uninstall requires at least one package argument.',
diff --git a/lib/spack/spack/database.py b/lib/spack/spack/database.py
index e219b0ad71..22fc266b5b 100644
--- a/lib/spack/spack/database.py
+++ b/lib/spack/spack/database.py
@@ -1295,6 +1295,30 @@ class Database(object):
         upstream, record = self.query_by_spec_hash(key)
         return record and not record.installed
 
+    @property
+    def unused_specs(self):
+        """Return all the specs that are currently installed but not needed
+        at runtime to satisfy user's requests.
+
+        Specs in the return list are those which are not either:
+            1. Installed on an explicit user request
+            2. Installed as a "run" or "link" dependency (even transitive) of
+               a spec at point 1.
+        """
+        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())
+
+            unused = [rec.spec for key, rec in self._data.items()
+                      if key not in needed and rec.installed]
+
+        return unused
+
 
 class UpstreamDatabaseLockingError(SpackError):
     """Raised when an operation would need to lock an upstream database"""
diff --git a/lib/spack/spack/test/cmd/gc.py b/lib/spack/spack/test/cmd/gc.py
new file mode 100644
index 0000000000..76eb608cf2
--- /dev/null
+++ b/lib/spack/spack/test/cmd/gc.py
@@ -0,0 +1,44 @@
+# Copyright 2013-2020 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
+
+import spack.environment as ev
+import spack.spec
+import spack.main
+
+gc = spack.main.SpackCommand('gc')
+
+
+@pytest.mark.db
+def test_no_packages_to_remove(config, mutable_database, capsys):
+    with capsys.disabled():
+        output = gc('-y')
+    assert 'There are no unused specs.' in output
+
+
+@pytest.mark.db
+def test_packages_are_removed(config, mutable_database, capsys):
+    s = spack.spec.Spec('simple-inheritance')
+    s.concretize()
+    s.package.do_install(fake=True, explicit=True)
+    with capsys.disabled():
+        output = gc('-y')
+    assert 'Successfully uninstalled cmake' in output
+
+
+@pytest.mark.db
+def test_gc_with_environment(config, mutable_database, capsys):
+    s = spack.spec.Spec('simple-inheritance')
+    s.concretize()
+    s.package.do_install(fake=True, explicit=True)
+
+    e = ev.create('test_gc')
+    e.add('cmake')
+    with e:
+        with capsys.disabled():
+            output = gc('-y')
+    assert 'Restricting the garbage collection' in output
+    assert 'There are no unused specs' in output
diff --git a/lib/spack/spack/test/database.py b/lib/spack/spack/test/database.py
index e856b8f588..24a219a491 100644
--- a/lib/spack/spack/test/database.py
+++ b/lib/spack/spack/test/database.py
@@ -706,3 +706,14 @@ def test_uninstall_by_spec(mutable_database):
             else:
                 mutable_database.remove(spec)
     assert len(mutable_database.query()) == 0
+
+
+def test_query_unused_specs(mutable_database):
+    # This spec installs a fake cmake as a build only dependency
+    s = spack.spec.Spec('simple-inheritance')
+    s.concretize()
+    s.package.do_install(fake=True, explicit=True)
+
+    unused = spack.store.db.unused_specs
+    assert len(unused) == 1
+    assert unused[0].name == 'cmake'