refactor: Index dependency metadata by `when` spec

Part 1 of making all package metadata indexed by `when` condition. This
will allow us to handle all the dictionaries on `PackageBase` consistently.

Convert the current dependency dictionary structure from this:

    { name: { when_spec: [Dependency ...] } }

to this:

    { when_spec: { name: [Dependency ...] } }

On an M1 mac, this actually shaves 5% off the time it takes to load all
packages, I think because we're able to trade off lookups by spec key
for more lookups by name.

13 files changed, 264 insertions, 150 deletions

diff --git a/lib/spack/spack/audit.py b/lib/spack/spack/audit.py
index 03ec05b44d..d9b2610267 100644
--- a/lib/spack/spack/audit.py
+++ b/lib/spack/spack/audit.py
@@ -694,15 +694,13 @@ def _unknown_variants_in_directives(pkgs, error_cls):
                 )
 
         # Check "depends_on" directive
-        for _, triggers in pkg_cls.dependencies.items():
-            triggers = list(triggers)
-            for trigger in list(triggers):
-                vrn = spack.spec.Spec(trigger)
-                errors.extend(
-                    _analyze_variants_in_directive(
-                        pkg_cls, vrn, directive="depends_on", error_cls=error_cls
-                    )
+        for trigger in pkg_cls.dependencies:
+            vrn = spack.spec.Spec(trigger)
+            errors.extend(
+                _analyze_variants_in_directive(
+                    pkg_cls, vrn, directive="depends_on", error_cls=error_cls
                 )
+            )
 
         # Check "patch" directive
         for _, triggers in pkg_cls.provided.items():
@@ -736,70 +734,60 @@ def _issues_in_depends_on_directive(pkgs, error_cls):
     for pkg_name in pkgs:
         pkg_cls = spack.repo.PATH.get_pkg_class(pkg_name)
         filename = spack.repo.PATH.filename_for_package_name(pkg_name)
-        for dependency_name, dependency_data in pkg_cls.dependencies.items():
-            # Check if there are nested dependencies declared. We don't want directives like:
-            #
-            #     depends_on('foo+bar ^fee+baz')
-            #
-            # but we'd like to have two dependencies listed instead.
-            for when, dependency_edge in dependency_data.items():
-                dependency_spec = dependency_edge.spec
-                nested_dependencies = dependency_spec.dependencies()
+
+        for when, deps_by_name in pkg_cls.dependencies.items():
+            for dep_name, dep in deps_by_name.items():
+                # Check if there are nested dependencies declared. We don't want directives like:
+                #
+                #     depends_on('foo+bar ^fee+baz')
+                #
+                # but we'd like to have two dependencies listed instead.
+                nested_dependencies = dep.spec.dependencies()
                 if nested_dependencies:
-                    summary = (
-                        f"{pkg_name}: invalid nested dependency "
-                        f"declaration '{str(dependency_spec)}'"
-                    )
+                    summary = f"{pkg_name}: nested dependency declaration '{dep.spec}'"
+                    ndir = len(nested_dependencies) + 1
                     details = [
-                        f"split depends_on('{str(dependency_spec)}', when='{str(when)}') "
-                        f"into {len(nested_dependencies) + 1} directives",
+                        f"split depends_on('{dep.spec}', when='{when}') into {ndir} directives",
                         f"in {filename}",
                     ]
                     errors.append(error_cls(summary=summary, details=details))
 
-                for s in (dependency_spec, when):
-                    if s.virtual and s.variants:
-                        summary = f"{pkg_name}: virtual dependency cannot have variants"
-                        details = [
-                            f"remove variants from '{str(s)}' in depends_on directive",
-                            f"in {filename}",
-                        ]
-                        errors.append(error_cls(summary=summary, details=details))
-
-            # No need to analyze virtual packages
-            if spack.repo.PATH.is_virtual(dependency_name):
-                continue
+                # No need to analyze virtual packages
+                if spack.repo.PATH.is_virtual(dep_name):
+                    continue
 
-            try:
-                dependency_pkg_cls = spack.repo.PATH.get_pkg_class(dependency_name)
-            except spack.repo.UnknownPackageError:
-                # This dependency is completely missing, so report
-                # and continue the analysis
-                summary = pkg_name + ": unknown package '{0}' in " "'depends_on' directive".format(
-                    dependency_name
-                )
-                details = [" in " + filename]
-                errors.append(error_cls(summary=summary, details=details))
-                continue
+                # check for unknown dependencies
+                try:
+                    dependency_pkg_cls = spack.repo.PATH.get_pkg_class(dep_name)
+                except spack.repo.UnknownPackageError:
+                    # This dependency is completely missing, so report
+                    # and continue the analysis
+                    summary = (
+                        f"{pkg_name}: unknown package '{dep_name}' in " "'depends_on' directive"
+                    )
+                    details = [f" in {filename}"]
+                    errors.append(error_cls(summary=summary, details=details))
+                    continue
 
-            for _, dependency_edge in dependency_data.items():
-                dependency_variants = dependency_edge.spec.variants
+                # check variants
+                dependency_variants = dep.spec.variants
                 for name, value in dependency_variants.items():
                     try:
                         v, _ = dependency_pkg_cls.variants[name]
                         v.validate_or_raise(value, pkg_cls=dependency_pkg_cls)
                     except Exception as e:
                         summary = (
-                            pkg_name + ": wrong variant used for a "
-                            "dependency in a 'depends_on' directive"
+                            f"{pkg_name}: wrong variant used for dependency in 'depends_on()'"
                         )
-                        error_msg = str(e).strip()
+
                         if isinstance(e, KeyError):
-                            error_msg = "the variant {0} does not " "exist".format(error_msg)
-                        error_msg += " in package '" + dependency_name + "'"
+                            error_msg = (
+                                f"variant {str(e).strip()} does not exist in package {dep_name}"
+                            )
+                        error_msg += f" in package '{dep_name}'"
 
                         errors.append(
-                            error_cls(summary=summary, details=[error_msg, "in " + filename])
+                            error_cls(summary=summary, details=[error_msg, f"in {filename}"])
                         )
 
     return errors
@@ -866,14 +854,17 @@ def _version_constraints_are_satisfiable_by_some_version_in_repo(pkgs, error_cls
     for pkg_name in pkgs:
         pkg_cls = spack.repo.PATH.get_pkg_class(pkg_name)
         filename = spack.repo.PATH.filename_for_package_name(pkg_name)
+
         dependencies_to_check = []
-        for dependency_name, dependency_data in pkg_cls.dependencies.items():
-            # Skip virtual dependencies for the time being, check on
-            # their versions can be added later
-            if spack.repo.PATH.is_virtual(dependency_name):
-                continue
 
-            dependencies_to_check.extend([edge.spec for edge in dependency_data.values()])
+        for _, deps_by_name in pkg_cls.dependencies.items():
+            for dep_name, dep in deps_by_name.items():
+                # Skip virtual dependencies for the time being, check on
+                # their versions can be added later
+                if spack.repo.PATH.is_virtual(dep_name):
+                    continue
+
+                dependencies_to_check.append(dep.spec)
 
         host_architecture = spack.spec.ArchSpec.default_arch()
         for s in dependencies_to_check:
@@ -945,18 +936,28 @@ def _named_specs_in_when_arguments(pkgs, error_cls):
     for pkg_name in pkgs:
         pkg_cls = spack.repo.PATH.get_pkg_class(pkg_name)
 
+        def _refers_to_pkg(when):
+            when_spec = spack.spec.Spec(when)
+            return when_spec.name is None or when_spec.name == pkg_name
+
+        def _error_items(when_dict):
+            for when, elts in when_dict.items():
+                if not _refers_to_pkg(when):
+                    yield when, elts, [f"using '{when}', should be '^{when}'"]
+
         def _extracts_errors(triggers, summary):
             _errors = []
             for trigger in list(triggers):
-                when_spec = spack.spec.Spec(trigger)
-                if when_spec.name is not None and when_spec.name != pkg_name:
+                if not _refers_to_pkg(trigger):
                     details = [f"using '{trigger}', should be '^{trigger}'"]
                     _errors.append(error_cls(summary=summary, details=details))
             return _errors
 
-        for dname, triggers in pkg_cls.dependencies.items():
-            summary = f"{pkg_name}: wrong 'when=' condition for the '{dname}' dependency"
-            errors.extend(_extracts_errors(triggers, summary))
+        for when, dnames, details in _error_items(pkg_cls.dependencies):
+            errors.extend(
+                error_cls(f"{pkg_name}: wrong 'when=' condition for '{dname}' dependency", details)
+                for dname in dnames
+            )
 
         for vname, (variant, triggers) in pkg_cls.variants.items():
             summary = f"{pkg_name}: wrong 'when=' condition for the '{vname}' variant"
@@ -971,13 +972,15 @@ def _named_specs_in_when_arguments(pkgs, error_cls):
             summary = f"{pkg_name}: wrong 'when=' condition in 'requires' directive"
             errors.extend(_extracts_errors(triggers, summary))
 
-        triggers = list(pkg_cls.patches)
-        summary = f"{pkg_name}: wrong 'when=' condition in 'patch' directives"
-        errors.extend(_extracts_errors(triggers, summary))
+        for when, _, details in _error_items(pkg_cls.patches):
+            errors.append(
+                error_cls(f"{pkg_name}: wrong 'when=' condition in 'patch' directives", details)
+            )
 
-        triggers = list(pkg_cls.resources)
-        summary = f"{pkg_name}: wrong 'when=' condition in 'resource' directives"
-        errors.extend(_extracts_errors(triggers, summary))
+        for when, _, details in _error_items(pkg_cls.resources):
+            errors.append(
+                error_cls(f"{pkg_name}: wrong 'when=' condition in 'resource' directives", details)
+            )
 
     return llnl.util.lang.dedupe(errors)
 
diff --git a/lib/spack/spack/cmd/dependents.py b/lib/spack/spack/cmd/dependents.py
index b78603bfae..4cbb7cdd3c 100644
--- a/lib/spack/spack/cmd/dependents.py
+++ b/lib/spack/spack/cmd/dependents.py
@@ -3,6 +3,7 @@
 #
 # SPDX-License-Identifier: (Apache-2.0 OR MIT)
 
+import collections
 import sys
 
 import llnl.util.tty as tty
@@ -49,15 +50,25 @@ def inverted_dependencies():
     dag = {}
     for pkg_cls in spack.repo.PATH.all_package_classes():
         dag.setdefault(pkg_cls.name, set())
-        for dep in pkg_cls.dependencies:
+        for dep in pkg_cls.dependencies_by_name():
             deps = [dep]
 
             # expand virtuals if necessary
             if spack.repo.PATH.is_virtual(dep):
                 deps += [s.name for s in spack.repo.PATH.providers_for(dep)]
 
-            for d in deps:
-                dag.setdefault(d, set()).add(pkg_cls.name)
+    dag = collections.defaultdict(set)
+    for pkg_cls in spack.repo.PATH.all_package_classes():
+        for _, deps_by_name in pkg_cls.dependencies.items():
+            for dep in deps_by_name:
+                deps = [dep]
+
+                # expand virtuals if necessary
+                if spack.repo.PATH.is_virtual(dep):
+                    deps += [s.name for s in spack.repo.PATH.providers_for(dep)]
+
+                for d in deps:
+                    dag[d].add(pkg_cls.name)
     return dag
 
 
diff --git a/lib/spack/spack/dependency.py b/lib/spack/spack/dependency.py
index f863c5329d..d8dd7b941f 100644
--- a/lib/spack/spack/dependency.py
+++ b/lib/spack/spack/dependency.py
@@ -79,4 +79,7 @@ class Dependency:
 
     def __repr__(self) -> str:
         types = dt.flag_to_chars(self.depflag)
-        return f"<Dependency: {self.pkg.name} -> {self.spec} [{types}]>"
+        if self.patches:
+            return f"<Dependency: {self.pkg.name} -> {self.spec} [{types}, {self.patches}]>"
+        else:
+            return f"<Dependency: {self.pkg.name} -> {self.spec} [{types}]>"
diff --git a/lib/spack/spack/directives.py b/lib/spack/spack/directives.py
index 2d5c46d698..e837f497af 100644
--- a/lib/spack/spack/directives.py
+++ b/lib/spack/spack/directives.py
@@ -29,6 +29,7 @@ The available directives are:
   * ``requires``
 
 """
+import collections
 import collections.abc
 import functools
 import os.path
@@ -83,7 +84,14 @@ directive_names = ["build_system"]
 _patch_order_index = 0
 
 
-def make_when_spec(value):
+SpecType = Union["spack.spec.Spec", str]
+DepType = Union[Tuple[str, ...], str]
+WhenType = Optional[Union["spack.spec.Spec", str, bool]]
+Patcher = Callable[[Union["spack.package_base.PackageBase", Dependency]], None]
+PatchesType = Optional[Union[Patcher, str, List[Union[Patcher, str]]]]
+
+
+def make_when_spec(value: WhenType) -> Optional["spack.spec.Spec"]:
     """Create a ``Spec`` that indicates when a directive should be applied.
 
     Directives with ``when`` specs, e.g.:
@@ -106,7 +114,7 @@ def make_when_spec(value):
     as part of concretization.
 
     Arguments:
-        value (spack.spec.Spec or bool): a conditional Spec or a constant ``bool``
+        value: a conditional Spec, constant ``bool``, or None if not supplied
            value indicating when a directive should be applied.
 
     """
@@ -116,7 +124,7 @@ def make_when_spec(value):
     # Unsatisfiable conditions are discarded by the caller, and never
     # added to the package class
     if value is False:
-        return False
+        return None
 
     # If there is no constraint, the directive should always apply;
     # represent this by returning the unconstrained `Spec()`, which is
@@ -175,8 +183,8 @@ class DirectiveMeta(type):
         # that the directives are called to set it up.
 
         if "spack.pkg" in cls.__module__:
-            # Ensure the presence of the dictionaries associated
-            # with the directives
+            # Ensure the presence of the dictionaries associated with the directives.
+            # All dictionaries are defaultdicts that create lists for missing keys.
             for d in DirectiveMeta._directive_dict_names:
                 setattr(cls, d, {})
 
@@ -455,7 +463,14 @@ def _execute_version(pkg, ver, **kwargs):
     pkg.versions[version] = kwargs
 
 
-def _depends_on(pkg, spec, when=None, type=dt.DEFAULT_TYPES, patches=None):
+def _depends_on(
+    pkg: "spack.package_base.PackageBase",
+    spec: SpecType,
+    *,
+    when: WhenType = None,
+    type: DepType = dt.DEFAULT_TYPES,
+    patches: PatchesType = None,
+):
     when_spec = make_when_spec(when)
     if not when_spec:
         return
@@ -467,7 +482,6 @@ def _depends_on(pkg, spec, when=None, type=dt.DEFAULT_TYPES, patches=None):
         raise CircularReferenceError("Package '%s' cannot depend on itself." % pkg.name)
 
     depflag = dt.canonicalize(type)
-    conditions = pkg.dependencies.setdefault(dep_spec.name, {})
 
     # call this patches here for clarity -- we want patch to be a list,
     # but the caller doesn't have to make it one.
@@ -495,11 +509,13 @@ def _depends_on(pkg, spec, when=None, type=dt.DEFAULT_TYPES, patches=None):
     assert all(callable(p) for p in patches)
 
     # this is where we actually add the dependency to this package
-    if when_spec not in conditions:
+    deps_by_name = pkg.dependencies.setdefault(when_spec, {})
+    dependency = deps_by_name.get(dep_spec.name)
+
+    if not dependency:
         dependency = Dependency(pkg, dep_spec, depflag=depflag)
-        conditions[when_spec] = dependency
+        deps_by_name[dep_spec.name] = dependency
     else:
-        dependency = conditions[when_spec]
         dependency.spec.constrain(dep_spec, deps=False)
         dependency.depflag |= depflag
 
@@ -544,15 +560,20 @@ def conflicts(conflict_spec, when=None, msg=None):
 
 
 @directive(("dependencies"))
-def depends_on(spec, when=None, type=dt.DEFAULT_TYPES, patches=None):
+def depends_on(
+    spec: SpecType,
+    when: WhenType = None,
+    type: DepType = dt.DEFAULT_TYPES,
+    patches: PatchesType = None,
+):
     """Creates a dict of deps with specs defining when they apply.
 
     Args:
-        spec (spack.spec.Spec or str): the package and constraints depended on
-        when (spack.spec.Spec or str): when the dependent satisfies this, it has
+        spec: the package and constraints depended on
+        when: when the dependent satisfies this, it has
             the dependency represented by ``spec``
-        type (str or tuple): str or tuple of legal Spack deptypes
-        patches (typing.Callable or list): single result of ``patch()`` directive, a
+        type: str or tuple of legal Spack deptypes
+        patches: single result of ``patch()`` directive, a
             ``str`` to be passed to ``patch``, or a list of these
 
     This directive is to be used inside a Package definition to declare
@@ -561,7 +582,7 @@ def depends_on(spec, when=None, type=dt.DEFAULT_TYPES, patches=None):
 
     """
 
-    def _execute_depends_on(pkg):
+    def _execute_depends_on(pkg: "spack.package_base.PackageBase"):
         _depends_on(pkg, spec, when=when, type=type, patches=patches)
 
     return _execute_depends_on
@@ -630,28 +651,31 @@ def provides(*specs, when: Optional[str] = None):
 
 
 @directive("patches")
-def patch(url_or_filename, level=1, when=None, working_dir=".", **kwargs):
+def patch(
+    url_or_filename: str,
+    level: int = 1,
+    when: WhenType = None,
+    working_dir: str = ".",
+    sha256: Optional[str] = None,
+    archive_sha256: Optional[str] = None,
+) -> Patcher:
     """Packages can declare patches to apply to source.  You can
     optionally provide a when spec to indicate that a particular
     patch should only be applied when the package's spec meets
     certain conditions (e.g. a particular version).
 
     Args:
-        url_or_filename (str): url or relative filename of the patch
-        level (int): patch level (as in the patch shell command)
-        when (spack.spec.Spec): optional anonymous spec that specifies when to apply
-            the patch
-        working_dir (str): dir to change to before applying
-
-    Keyword Args:
-        sha256 (str): sha256 sum of the patch, used to verify the patch
-            (only required for URL patches)
-        archive_sha256 (str): sha256 sum of the *archive*, if the patch
-            is compressed (only required for compressed URL patches)
+        url_or_filename: url or relative filename of the patch
+        level: patch level (as in the patch shell command)
+        when: optional anonymous spec that specifies when to apply the patch
+        working_dir: dir to change to before applying
+        sha256: sha256 sum of the patch, used to verify the patch (only required for URL patches)
+        archive_sha256: sha256 sum of the *archive*, if the patch is compressed (only required for
+            compressed URL patches)
 
     """
 
-    def _execute_patch(pkg_or_dep):
+    def _execute_patch(pkg_or_dep: Union["spack.package_base.PackageBase", Dependency]):
         pkg = pkg_or_dep
         if isinstance(pkg, Dependency):
             pkg = pkg.pkg
@@ -673,9 +697,16 @@ def patch(url_or_filename, level=1, when=None, working_dir=".", **kwargs):
         ordering_key = (pkg.name, _patch_order_index)
         _patch_order_index += 1
 
+        patch: spack.patch.Patch
         if "://" in url_or_filename:
             patch = spack.patch.UrlPatch(
-                pkg, url_or_filename, level, working_dir, ordering_key=ordering_key, **kwargs
+                pkg,
+                url_or_filename,
+                level,
+                working_dir,
+                ordering_key=ordering_key,
+                sha256=sha256,
+                archive_sha256=archive_sha256,
             )
         else:
             patch = spack.patch.FilePatch(
diff --git a/lib/spack/spack/package_base.py b/lib/spack/spack/package_base.py
index d1a2387f77..926df89181 100644
--- a/lib/spack/spack/package_base.py
+++ b/lib/spack/spack/package_base.py
@@ -25,7 +25,7 @@ import textwrap
 import time
 import traceback
 import warnings
-from typing import Any, Callable, Dict, Iterable, List, Optional, Tuple, Type, TypeVar
+from typing import Any, Callable, Dict, Iterable, List, Optional, Tuple, Type, TypeVar, Union
 
 import llnl.util.filesystem as fsys
 import llnl.util.tty as tty
@@ -432,6 +432,43 @@ class PackageViewMixin:
 
 Pb = TypeVar("Pb", bound="PackageBase")
 
+WhenDict = Dict[spack.spec.Spec, Dict[str, Any]]
+NameValuesDict = Dict[str, List[Any]]
+NameWhenDict = Dict[str, Dict[spack.spec.Spec, List[Any]]]
+
+
+def _by_name(
+    when_indexed_dictionary: WhenDict, when: bool = False
+) -> Union[NameValuesDict, NameWhenDict]:
+    """Convert a dict of dicts keyed by when/name into a dict of lists keyed by name.
+
+    Optional Arguments:
+        when: if ``True``, don't discared the ``when`` specs; return a 2-level dictionary
+            keyed by name and when spec.
+    """
+    # very hard to define this type to be conditional on `when`
+    all_by_name: Dict[str, Any] = {}
+
+    for when_spec, by_name in when_indexed_dictionary.items():
+        for name, value in by_name.items():
+            if when:
+                when_dict = all_by_name.setdefault(name, {})
+                when_dict.setdefault(when_spec, []).append(value)
+            else:
+                all_by_name.setdefault(name, []).append(value)
+
+    return dict(sorted(all_by_name.items()))
+
+
+def _names(when_indexed_dictionary):
+    """Get sorted names from dicts keyed by when/name."""
+    all_names = set()
+    for when, by_name in when_indexed_dictionary.items():
+        for name in by_name:
+            all_names.add(name)
+
+    return sorted(all_names)
+
 
 class PackageBase(WindowsRPath, PackageViewMixin, metaclass=PackageMeta):
     """This is the superclass for all spack packages.
@@ -525,7 +562,10 @@ class PackageBase(WindowsRPath, PackageViewMixin, metaclass=PackageMeta):
     versions: dict
 
     # Same for dependencies
-    dependencies: dict
+    dependencies: Dict["spack.spec.Spec", Dict[str, "spack.dependency.Dependency"]]
+
+    # and patches
+    patches: Dict["spack.spec.Spec", List["spack.patch.Patch"]]
 
     #: By default, packages are not virtual
     #: Virtual packages override this attribute
@@ -680,6 +720,14 @@ class PackageBase(WindowsRPath, PackageViewMixin, metaclass=PackageMeta):
         super().__init__()
 
     @classmethod
+    def dependency_names(cls):
+        return _names(cls.dependencies)
+
+    @classmethod
+    def dependencies_by_name(cls, when: bool = False):
+        return _by_name(cls.dependencies, when=when)
+
+    @classmethod
     def possible_dependencies(
         cls,
         transitive=True,
@@ -727,11 +775,12 @@ class PackageBase(WindowsRPath, PackageViewMixin, metaclass=PackageMeta):
 
         visited.setdefault(cls.name, set())
 
-        for name, conditions in cls.dependencies.items():
+        for name, conditions in cls.dependencies_by_name(when=True).items():
             # check whether this dependency could be of the type asked for
             depflag_union = 0
-            for dep in conditions.values():
-                depflag_union |= dep.depflag
+            for deplist in conditions.values():
+                for dep in deplist:
+                    depflag_union |= dep.depflag
             if not (depflag & depflag_union):
                 continue
 
@@ -1219,7 +1268,7 @@ class PackageBase(WindowsRPath, PackageViewMixin, metaclass=PackageMeta):
 
     @classmethod
     def dependencies_of_type(cls, deptypes: dt.DepFlag):
-        """Get dependencies that can possibly have these deptypes.
+        """Get names of dependencies that can possibly have these deptypes.
 
         This analyzes the package and determines which dependencies *can*
         be a certain kind of dependency. Note that they may not *always*
@@ -1227,11 +1276,11 @@ class PackageBase(WindowsRPath, PackageViewMixin, metaclass=PackageMeta):
         so something may be a build dependency in one configuration and a
         run dependency in another.
         """
-        return dict(
-            (name, conds)
-            for name, conds in cls.dependencies.items()
-            if any(deptypes & cls.dependencies[name][cond].depflag for cond in conds)
-        )
+        return {
+            name
+            for name, dependencies in cls.dependencies_by_name().items()
+            if any(deptypes & dep.depflag for dep in dependencies)
+        }
 
     # TODO: allow more than one active extendee.
     @property
diff --git a/lib/spack/spack/patch.py b/lib/spack/spack/patch.py
index 09b76a1dc1..75d1ab7f37 100644
--- a/lib/spack/spack/patch.py
+++ b/lib/spack/spack/patch.py
@@ -389,10 +389,9 @@ class PatchCache:
                 patch_dict.pop("sha256")  # save some space
                 index[patch.sha256] = {pkg_class.fullname: patch_dict}
 
-        # and patches on dependencies
-        for name, conditions in pkg_class.dependencies.items():
-            for cond, dependency in conditions.items():
-                for pcond, patch_list in dependency.patches.items():
+        for deps_by_name in pkg_class.dependencies.values():
+            for dependency in deps_by_name.values():
+                for patch_list in dependency.patches.values():
                     for patch in patch_list:
                         dspec_cls = repository.get_pkg_class(dependency.spec.name)
                         patch_dict = patch.to_dict()
diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index f545db58ae..aa00600d0b 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -1643,8 +1643,8 @@ class SpackSolverSetup:
 
     def package_dependencies_rules(self, pkg):
         """Translate 'depends_on' directives into ASP logic."""
-        for _, conditions in sorted(pkg.dependencies.items()):
-            for cond, dep in sorted(conditions.items()):
+        for cond, deps_by_name in sorted(pkg.dependencies.items()):
+            for _, dep in sorted(deps_by_name.items()):
                 depflag = dep.depflag
                 # Skip test dependencies if they're not requested
                 if not self.tests:
@@ -1741,6 +1741,7 @@ class SpackSolverSetup:
             pkg_name, policy, requirement_grp = rule.pkg_name, rule.policy, rule.requirements
 
             requirement_weight = 0
+            # TODO: don't call make_when_spec here; do it in directives.
             main_requirement_condition = spack.directives.make_when_spec(rule.condition)
             if main_requirement_condition is False:
                 continue
@@ -1750,7 +1751,7 @@ class SpackSolverSetup:
                 msg = f"condition to activate requirement {requirement_grp_id}"
                 try:
                     main_condition_id = self.condition(
-                        main_requirement_condition, name=pkg_name, msg=msg
+                        main_requirement_condition, name=pkg_name, msg=msg  # type: ignore
                     )
                 except Exception as e:
                     if rule.kind != RequirementKind.DEFAULT:
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 5a491d5eed..a11e8ab915 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -2876,13 +2876,14 @@ class Spec:
                 continue
 
             # Add any patches from the package to the spec.
-            patches = []
+            patches = set()
             for cond, patch_list in s.package_class.patches.items():
                 if s.satisfies(cond):
                     for patch in patch_list:
-                        patches.append(patch)
+                        patches.add(patch)
             if patches:
                 spec_to_patches[id(s)] = patches
+
         # Also record all patches required on dependencies by
         # depends_on(..., patch=...)
         for dspec in root.traverse_edges(deptype=all, cover="edges", root=False):
@@ -2890,17 +2891,25 @@ class Spec:
                 continue
 
             pkg_deps = dspec.parent.package_class.dependencies
-            if dspec.spec.name not in pkg_deps:
-                continue
 
             patches = []
-            for cond, dependency in pkg_deps[dspec.spec.name].items():
+            for cond, deps_by_name in pkg_deps.items():
+                if not dspec.parent.satisfies(cond):
+                    continue
+
+                dependency = deps_by_name.get(dspec.spec.name)
+                if not dependency:
+                    continue
+
                 for pcond, patch_list in dependency.patches.items():
-                    if dspec.parent.satisfies(cond) and dspec.spec.satisfies(pcond):
+                    if dspec.spec.satisfies(pcond):
                         patches.extend(patch_list)
+
             if patches:
-                all_patches = spec_to_patches.setdefault(id(dspec.spec), [])
-                all_patches.extend(patches)
+                all_patches = spec_to_patches.setdefault(id(dspec.spec), set())
+                for patch in patches:
+                    all_patches.add(patch)
+
         for spec in root.traverse():
             if id(spec) not in spec_to_patches:
                 continue
@@ -3163,13 +3172,17 @@ class Spec:
         If no conditions are True (and we don't depend on it), return
         ``(None, None)``.
         """
-        conditions = self.package_class.dependencies[name]
-
         vt.substitute_abstract_variants(self)
         # evaluate when specs to figure out constraints on the dependency.
         dep = None
-        for when_spec, dependency in conditions.items():
-            if self.satisfies(when_spec):
+        for when_spec, deps_by_name in self.package_class.dependencies.items():
+            if not self.satisfies(when_spec):
+                continue
+
+            for dep_name, dependency in deps_by_name.items():
+                if dep_name != name:
+                    continue
+
                 if dep is None:
                     dep = dp.Dependency(Spec(self.name), Spec(name), depflag=0)
                 try:
@@ -3344,7 +3357,7 @@ class Spec:
 
         while changed:
             changed = False
-            for dep_name in self.package_class.dependencies:
+            for dep_name in self.package_class.dependency_names():
                 # Do we depend on dep_name?  If so pkg_dep is not None.
                 dep = self._evaluate_dependency_conditions(dep_name)
 
diff --git a/lib/spack/spack/test/directives.py b/lib/spack/spack/test/directives.py
index 69291f919e..73d40365b9 100644
--- a/lib/spack/spack/test/directives.py
+++ b/lib/spack/spack/test/directives.py
@@ -29,8 +29,8 @@ def test_true_directives_exist(mock_packages):
     cls = spack.repo.PATH.get_pkg_class("when-directives-true")
 
     assert cls.dependencies
-    assert spack.spec.Spec() in cls.dependencies["extendee"]
-    assert spack.spec.Spec() in cls.dependencies["b"]
+    assert "extendee" in cls.dependencies[spack.spec.Spec()]
+    assert "b" in cls.dependencies[spack.spec.Spec()]
 
     assert cls.resources
     assert spack.spec.Spec() in cls.resources
@@ -43,7 +43,7 @@ def test_constraints_from_context(mock_packages):
     pkg_cls = spack.repo.PATH.get_pkg_class("with-constraint-met")
 
     assert pkg_cls.dependencies
-    assert spack.spec.Spec("@1.0") in pkg_cls.dependencies["b"]
+    assert "b" in pkg_cls.dependencies[spack.spec.Spec("@1.0")]
 
     assert pkg_cls.conflicts
     assert (spack.spec.Spec("+foo@1.0"), None) in pkg_cls.conflicts["%gcc"]
@@ -54,7 +54,7 @@ def test_constraints_from_context_are_merged(mock_packages):
     pkg_cls = spack.repo.PATH.get_pkg_class("with-constraint-met")
 
     assert pkg_cls.dependencies
-    assert spack.spec.Spec("@0.14:15 ^b@3.8:4.0") in pkg_cls.dependencies["c"]
+    assert "c" in pkg_cls.dependencies[spack.spec.Spec("@0.14:15 ^b@3.8:4.0")]
 
 
 @pytest.mark.regression("27754")
diff --git a/lib/spack/spack/test/package_class.py b/lib/spack/spack/test/package_class.py
index 2b1dca6e33..915a53400d 100644
--- a/lib/spack/spack/test/package_class.py
+++ b/lib/spack/spack/test/package_class.py
@@ -71,7 +71,8 @@ def test_possible_direct_dependencies(mock_packages, mpileaks_possible_deps):
 
 def test_possible_dependencies_virtual(mock_packages, mpi_names):
     expected = dict(
-        (name, set(spack.repo.PATH.get_pkg_class(name).dependencies)) for name in mpi_names
+        (name, set(dep for dep in spack.repo.PATH.get_pkg_class(name).dependencies_by_name()))
+        for name in mpi_names
     )
 
     # only one mock MPI has a dependency
diff --git a/lib/spack/spack/test/packages.py b/lib/spack/spack/test/packages.py
index 49066b309f..f2507ee57e 100644
--- a/lib/spack/spack/test/packages.py
+++ b/lib/spack/spack/test/packages.py
@@ -61,14 +61,15 @@ class TestPackage:
         import spack.pkg.builtin.mock.mpich as mp  # noqa: F401
         from spack.pkg.builtin import mock  # noqa: F401
 
-    def test_inheritance_of_diretives(self):
+    def test_inheritance_of_directives(self):
         pkg_cls = spack.repo.PATH.get_pkg_class("simple-inheritance")
 
         # Check dictionaries that should have been filled by directives
-        assert len(pkg_cls.dependencies) == 3
-        assert "cmake" in pkg_cls.dependencies
-        assert "openblas" in pkg_cls.dependencies
-        assert "mpi" in pkg_cls.dependencies
+        dependencies = pkg_cls.dependencies_by_name()
+        assert len(dependencies) == 3
+        assert "cmake" in dependencies
+        assert "openblas" in dependencies
+        assert "mpi" in dependencies
         assert len(pkg_cls.provided) == 2
 
         # Check that Spec instantiation behaves as we expect
diff --git a/lib/spack/spack/test/patch.py b/lib/spack/spack/test/patch.py
index bad8f2403d..e025994cce 100644
--- a/lib/spack/spack/test/patch.py
+++ b/lib/spack/spack/test/patch.py
@@ -196,16 +196,18 @@ def test_nested_directives(mock_packages):
 
     # this ensures that results of dependency patches were properly added
     # to Dependency objects.
-    libelf_dep = next(iter(patcher.dependencies["libelf"].values()))
+    deps_by_name = patcher.dependencies_by_name()
+
+    libelf_dep = deps_by_name["libelf"][0]
     assert len(libelf_dep.patches) == 1
     assert len(libelf_dep.patches[Spec()]) == 1
 
-    libdwarf_dep = next(iter(patcher.dependencies["libdwarf"].values()))
+    libdwarf_dep = deps_by_name["libdwarf"][0]
     assert len(libdwarf_dep.patches) == 2
     assert len(libdwarf_dep.patches[Spec()]) == 1
     assert len(libdwarf_dep.patches[Spec("@20111030")]) == 1
 
-    fake_dep = next(iter(patcher.dependencies["fake"].values()))
+    fake_dep = deps_by_name["fake"][0]
     assert len(fake_dep.patches) == 1
     assert len(fake_dep.patches[Spec()]) == 2
 
diff --git a/lib/spack/spack/test/spec_dag.py b/lib/spack/spack/test/spec_dag.py
index ecbdd304e7..da85be6d1c 100644
--- a/lib/spack/spack/test/spec_dag.py
+++ b/lib/spack/spack/test/spec_dag.py
@@ -51,7 +51,7 @@ def set_dependency(saved_deps, monkeypatch):
 
         cond = Spec(pkg_cls.name)
         dependency = Dependency(pkg_cls, spec)
-        monkeypatch.setitem(pkg_cls.dependencies, spec.name, {cond: dependency})
+        monkeypatch.setitem(pkg_cls.dependencies, cond, {spec.name: dependency})
 
     return _mock