spack uninstall can uninstall specs with multiple roots (#11977)

Fixes #3690
Fixes #5637

Uninstalling dependents of a spec was relying on a traversal of the
parents done by inspecting spec._dependents. This is in turn a
DependencyMap that maps a package name to a single DependencySpec object
(an edge in the DAG) and cannot thus model the case where a spec has
multiple configurations of the same parent package installed (for
example if different versions of the same Python library depend on
the same Python installation).

This commit works around this issue by constructing the list of specs to
be uninstalled in an alternative way, and adds tests to verify the
behavior. The core issue with DependencyMap is not resolved here.

2 files changed, 52 insertions, 14 deletions

diff --git a/lib/spack/spack/cmd/uninstall.py b/lib/spack/spack/cmd/uninstall.py
index 532e0c0de4..8ad8dcb4b5 100644
--- a/lib/spack/spack/cmd/uninstall.py
+++ b/lib/spack/spack/cmd/uninstall.py
@@ -9,6 +9,7 @@ import argparse
 
 import spack.cmd
 import spack.environment as ev
+import spack.error
 import spack.package
 import spack.cmd.common.arguments as arguments
 import spack.repo
@@ -126,9 +127,10 @@ def installed_dependents(specs, env):
 
     env_hashes = set(env.all_hashes()) if env else set()
 
+    all_specs_in_db = spack.store.db.query()
+
     for spec in specs:
-        installed = spack.store.db.installed_relatives(
-            spec, direction='parents', transitive=True)
+        installed = [x for x in all_specs_in_db if spec in x]
 
         # separate installed dependents into dpts in this environment and
         # dpts that are outside this environment
@@ -212,16 +214,23 @@ def do_uninstall(env, specs, force):
         if env:
             _remove_from_env(item, env)
 
-    # Sort packages to be uninstalled by the number of installed dependents
-    # This ensures we do things in the right order
-    def num_installed_deps(pkg):
-        dependents = spack.store.db.installed_relatives(
-            pkg.spec, 'parents', True)
-        return len(dependents)
+    # A package is ready to be uninstalled when nothing else references it,
+    # unless we are requested to force uninstall it.
+    is_ready = lambda x: not spack.store.db.query_by_spec_hash(x)[1].ref_count
+    if force:
+        is_ready = lambda x: True
+
+    while packages:
+        ready = [x for x in packages if is_ready(x.spec.dag_hash())]
+        if not ready:
+            msg = 'unexpected error [cannot proceed uninstalling specs with' \
+                  ' remaining dependents {0}]'
+            msg = msg.format(', '.join(x.name for x in packages))
+            raise spack.error.SpackError(msg)
 
-    packages.sort(key=num_installed_deps)
-    for item in packages:
-        item.do_uninstall(force=force)
+        packages = [x for x in packages if x not in ready]
+        for item in ready:
+            item.do_uninstall(force=force)
 
     # write any changes made to the active environment
     if env:
@@ -332,5 +341,5 @@ def uninstall(parser, args):
                 '  Use `spack uninstall --all` to uninstall ALL packages.')
 
     # [any] here handles the --all case by forcing all specs to be returned
-    uninstall_specs(
-        args, spack.cmd.parse_specs(args.packages) if args.packages else [any])
+    specs = spack.cmd.parse_specs(args.packages) if args.packages else [any]
+    uninstall_specs(args, specs)
diff --git a/lib/spack/spack/test/cmd/uninstall.py b/lib/spack/spack/test/cmd/uninstall.py
index c330a08062..f331b1a548 100644
--- a/lib/spack/spack/test/cmd/uninstall.py
+++ b/lib/spack/spack/test/cmd/uninstall.py
@@ -37,7 +37,7 @@ def test_installed_dependents():
 
 
 @pytest.mark.db
-@pytest.mark.usefixtures('database')
+@pytest.mark.usefixtures('mutable_database')
 def test_recursive_uninstall():
     """Test recursive uninstall."""
     uninstall('-y', '-a', '--dependents', 'callpath')
@@ -52,3 +52,32 @@ def test_recursive_uninstall():
     assert len(mpileaks_specs) == 0
     assert len(callpath_specs) == 0
     assert len(mpi_specs) == 3
+
+
+@pytest.mark.db
+@pytest.mark.regression('3690')
+@pytest.mark.usefixtures('mutable_database')
+@pytest.mark.parametrize('constraint,expected_number_of_specs', [
+    ('dyninst', 7), ('libelf', 5)
+])
+def test_uninstall_spec_with_multiple_roots(
+        constraint, expected_number_of_specs
+):
+    uninstall('-y', '-a', '--dependents', constraint)
+
+    all_specs = spack.store.layout.all_specs()
+    assert len(all_specs) == expected_number_of_specs
+
+
+@pytest.mark.db
+@pytest.mark.usefixtures('mutable_database')
+@pytest.mark.parametrize('constraint,expected_number_of_specs', [
+    ('dyninst', 13), ('libelf', 13)
+])
+def test_force_uninstall_spec_with_ref_count_not_zero(
+        constraint, expected_number_of_specs
+):
+    uninstall('-f', '-y', constraint)
+
+    all_specs = spack.store.layout.all_specs()
+    assert len(all_specs) == expected_number_of_specs