From 8ea366b33f5b64c09098543549410e7fbb6d1f9e Mon Sep 17 00:00:00 2001 From: Harmen Stoppels Date: Mon, 21 Nov 2022 16:44:48 +0100 Subject: 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. --- lib/spack/spack/cmd/uninstall.py | 39 ++++++++++++++++++++--------------- lib/spack/spack/database.py | 9 ++++++++ lib/spack/spack/test/cmd/uninstall.py | 35 +++++++++++++++++++++++++++++++ 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 @@ -40,6 +42,39 @@ def test_installed_dependents(mutable_database): uninstall("-y", "libelf") +@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.""" -- cgit v1.2.3-70-g09d2