uninstall: fix accidental cubic complexity (#34005)

* uninstall: fix accidental cubic complexity

Currently spack uninstall runs in worst case cubic time complexity
thanks to traversal during traversal during traversal while collecting
the specs to be uninstalled.

Also brings down the number of error messages printed to something
linear in the amount of matching specs instead of quadratic.

3 files changed, 66 insertions, 17 deletions

diff --git a/lib/spack/spack/cmd/uninstall.py b/lib/spack/spack/cmd/uninstall.py
index 8c112840fd..7134ca7256 100644
--- a/lib/spack/spack/cmd/uninstall.py
+++ b/lib/spack/spack/cmd/uninstall.py
@@ -17,6 +17,7 @@ import spack.error
 import spack.package_base
 import spack.repo
 import spack.store
+import spack.traverse as traverse
 from spack.database import InstallStatuses
 
 description = "remove installed packages"
@@ -144,11 +145,7 @@ def installed_dependents(specs, env):
         active environment, and one from specs to dependent installs outside of
         the active environment.
 
-        Any of the input specs may appear in both mappings (if there are
-        dependents both inside and outside the current environment).
-
-        If a dependent spec is used both by the active environment and by
-        an inactive environment, it will only appear in the first mapping.
+        Every installed dependent spec is listed once.
 
         If there is not current active environment, the first mapping will be
         empty.
@@ -158,19 +155,27 @@ def installed_dependents(specs, env):
 
     env_hashes = set(env.all_hashes()) if env else set()
 
-    all_specs_in_db = spack.store.db.query()
+    # Ensure we stop traversal at input specs.
+    visited = set(s.dag_hash() for s in specs)
 
     for spec in specs:
-        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
-        for dpt in installed:
-            if dpt not in specs:
-                if dpt.dag_hash() in env_hashes:
-                    active_dpts.setdefault(spec, set()).add(dpt)
-                else:
-                    outside_dpts.setdefault(spec, set()).add(dpt)
+        for dpt in traverse.traverse_nodes(
+            spec.dependents(deptype="all"),
+            direction="parents",
+            visited=visited,
+            deptype="all",
+            root=True,
+            key=lambda s: s.dag_hash(),
+        ):
+            hash = dpt.dag_hash()
+            # Ensure that all the specs we get are installed
+            record = spack.store.db.query_local_by_spec_hash(hash)
+            if record is None or not record.installed:
+                continue
+            if hash in env_hashes:
+                active_dpts.setdefault(spec, set()).add(dpt)
+            else:
+                outside_dpts.setdefault(spec, set()).add(dpt)
 
     return active_dpts, outside_dpts
 
@@ -250,7 +255,7 @@ def do_uninstall(env, specs, force):
         if force:
             return True
 
-        _, record = spack.store.db.query_by_spec_hash(dag_hash)
+        record = spack.store.db.query_local_by_spec_hash(dag_hash)
         if not record.ref_count:
             return True
 
diff --git a/lib/spack/spack/database.py b/lib/spack/spack/database.py
index f74008e8f3..ba4158ee80 100644
--- a/lib/spack/spack/database.py
+++ b/lib/spack/spack/database.py
@@ -723,6 +723,15 @@ class Database(object):
                 return True, db._data[hash_key]
         return False, None
 
+    def query_local_by_spec_hash(self, hash_key):
+        """Get a spec by hash in the local database
+
+        Return:
+            (InstallRecord or None): InstallRecord when installed
+                locally, otherwise None."""
+        with self.read_transaction():
+            return self._data.get(hash_key, None)
+
     def _assign_dependencies(self, hash_key, installs, data):
         # Add dependencies from other records in the install DB to
         # form a full spec.
diff --git a/lib/spack/spack/test/cmd/uninstall.py b/lib/spack/spack/test/cmd/uninstall.py
index ddbd54e252..be9fa3aa16 100644
--- a/lib/spack/spack/test/cmd/uninstall.py
+++ b/lib/spack/spack/test/cmd/uninstall.py
@@ -3,12 +3,14 @@
 #
 # SPDX-License-Identifier: (Apache-2.0 OR MIT)
 
+import itertools
 import sys
 
 import pytest
 
 import llnl.util.tty as tty
 
+import spack.cmd.uninstall
 import spack.environment
 import spack.store
 from spack.main import SpackCommand, SpackCommandError
@@ -41,6 +43,39 @@ def test_installed_dependents(mutable_database):
 
 
 @pytest.mark.db
+def test_correct_installed_dependents(mutable_database):
+    # Test whether we return the right dependents.
+
+    # Take callpath from the database
+    callpath = spack.store.db.query_local("callpath")[0]
+
+    # Ensure it still has dependents and dependencies
+    dependents = callpath.dependents(deptype="all")
+    dependencies = callpath.dependencies(deptype="all")
+    assert dependents and dependencies
+
+    # Uninstall it, so it's missing.
+    callpath.package.do_uninstall(force=True)
+
+    # Retrieve all dependent hashes
+    inside_dpts, outside_dpts = spack.cmd.uninstall.installed_dependents(dependencies, None)
+    dependent_hashes = [s.dag_hash() for s in itertools.chain(*outside_dpts.values())]
+    set_dependent_hashes = set(dependent_hashes)
+
+    # We dont have an env, so this should be empty.
+    assert not inside_dpts
+
+    # Assert uniqueness
+    assert len(dependent_hashes) == len(set_dependent_hashes)
+
+    # Ensure parents of callpath are listed
+    assert all(s.dag_hash() in set_dependent_hashes for s in dependents)
+
+    # Ensure callpath itself is not, since it was missing.
+    assert callpath.dag_hash() not in set_dependent_hashes
+
+
+@pytest.mark.db
 def test_recursive_uninstall(mutable_database):
     """Test recursive uninstall."""
     uninstall("-y", "-a", "--dependents", "callpath")