bugfix: original concretizer is sensitive to dependency order (#41975)

Needed for #40326, which can changes the iteration order over package dependencies during concretization.

While clingo doesn't have this problem, the original concretizer (which we still use for bootstrapping) can be sensitive to iteration order when evaluating dependency constraints in `when` conditions. This can cause it to ignore conditional dependencies unless the dependencies in the condition are listed first in the package.

The issue was in the way the original concretizer would disconnect specs *every* time `normalize()` ran. When specs were disconnected, `^dependency` constraints wouldn't see the dependency in the dependency condition loop.

We now only only disconnect *all* dependencies at the start of `concretize()` and `normalize()`, and we disconnect any leftover dependents from replaced externals at the *end* of `normalize()`.  This trims stale connections while keeping the ones that are needed to trigger dependency conditions.

- [x] refactor `flat_dependencies()` to not disconnect the spec by default.
- [x] `flat_dependencies()` is never called with `copy=True` -- remove the `copy` kwarg.
- [x] disconnect only once at the beginning of `normalize()` or `concretize()`.
- [x] add a test that perturbs dependency iteration order to ensure this doesn't regress.
- [x] disconnect unused dependents at end of `normalize()`

3 files changed, 59 insertions, 41 deletions

diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 9140a3532a..5a491d5eed 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -2768,14 +2768,16 @@ class Spec:
         if self._concrete:
             return
 
+        # take the spec apart once before starting the main concretization loop and resolving
+        # deps, but don't break dependencies during concretization as the spec is built.
+        user_spec_deps = self.flat_dependencies(disconnect=True)
+
         changed = True
         force = False
-
-        user_spec_deps = self.flat_dependencies(copy=False)
         concretizer = spack.concretize.Concretizer(self.copy())
         while changed:
             changes = (
-                self.normalize(force, tests=tests, user_spec_deps=user_spec_deps),
+                self.normalize(force, tests, user_spec_deps, disconnect=False),
                 self._expand_virtual_packages(concretizer),
                 self._concretize_helper(concretizer),
             )
@@ -3108,45 +3110,33 @@ class Spec:
         clone.concretize(tests=tests)
         return clone
 
-    def flat_dependencies(self, **kwargs):
-        """Return a DependencyMap containing all of this spec's
-        dependencies with their constraints merged.
+    def flat_dependencies(self, disconnect: bool = False):
+        """Build DependencyMap of all of this spec's dependencies with their constraints merged.
 
-        If copy is True, returns merged copies of its dependencies
-        without modifying the spec it's called on.
-
-        If copy is False, clears this spec's dependencies and
-        returns them. This disconnects all dependency links including
-        transitive dependencies, except for concrete specs: if a spec
-        is concrete it will not be disconnected from its dependencies
-        (although a non-concrete spec with concrete dependencies will
-        be disconnected from those dependencies).
+        Arguments:
+            disconnect: if True, disconnect all dependents and dependencies among nodes in this
+                spec's DAG.
         """
-        copy = kwargs.get("copy", True)
-
         flat_deps = {}
-        try:
-            deptree = self.traverse(root=False)
-            for spec in deptree:
-                if spec.name not in flat_deps:
-                    if copy:
-                        spec = spec.copy(deps=False)
-                    flat_deps[spec.name] = spec
-                else:
-                    flat_deps[spec.name].constrain(spec)
+        deptree = self.traverse(root=False)
 
-            if not copy:
-                for spec in flat_deps.values():
-                    if not spec.concrete:
-                        spec.clear_edges()
-                self.clear_dependencies()
+        for spec in deptree:
+            if spec.name not in flat_deps:
+                flat_deps[spec.name] = spec
+            else:
+                try:
+                    flat_deps[spec.name].constrain(spec)
+                except spack.error.UnsatisfiableSpecError as e:
+                    # DAG contains two instances of the same package with inconsistent constraints.
+                    raise InconsistentSpecError("Invalid Spec DAG: %s" % e.message) from e
 
-            return flat_deps
+        if disconnect:
+            for spec in flat_deps.values():
+                if not spec.concrete:
+                    spec.clear_edges()
+            self.clear_dependencies()
 
-        except spack.error.UnsatisfiableSpecError as e:
-            # Here, the DAG contains two instances of the same package
-            # with inconsistent constraints.
-            raise InconsistentSpecError("Invalid Spec DAG: %s" % e.message) from e
+        return flat_deps
 
     def index(self, deptype="all"):
         """Return a dictionary that points to all the dependencies in this
@@ -3181,7 +3171,7 @@ class Spec:
         for when_spec, dependency in conditions.items():
             if self.satisfies(when_spec):
                 if dep is None:
-                    dep = dp.Dependency(self.name, Spec(name), depflag=0)
+                    dep = dp.Dependency(Spec(self.name), Spec(name), depflag=0)
                 try:
                     dep.merge(dependency)
                 except spack.error.UnsatisfiableSpecError as e:
@@ -3377,7 +3367,7 @@ class Spec:
 
         return any_change
 
-    def normalize(self, force=False, tests=False, user_spec_deps=None):
+    def normalize(self, force=False, tests=False, user_spec_deps=None, disconnect=True):
         """When specs are parsed, any dependencies specified are hanging off
         the root, and ONLY the ones that were explicitly provided are there.
         Normalization turns a partial flat spec into a DAG, where:
@@ -3414,7 +3404,7 @@ class Spec:
         # user-specified dependencies are recorded separately in case they
         # refer to specs which take several normalization passes to
         # materialize.
-        all_spec_deps = self.flat_dependencies(copy=False)
+        all_spec_deps = self.flat_dependencies(disconnect=disconnect)
 
         if user_spec_deps:
             for name, spec in user_spec_deps.items():
@@ -3439,6 +3429,14 @@ class Spec:
 
         any_change = self._normalize_helper(visited, all_spec_deps, provider_index, tests)
 
+        # remove any leftover dependents outside the spec from, e.g., pruning externals
+        valid = {id(spec) for spec in all_spec_deps.values()} | {id(self)}
+        for spec in all_spec_deps.values():
+            remove = [dep for dep in spec.dependents() if id(dep) not in valid]
+            for dep in remove:
+                del spec._dependents.edges[dep.name]
+                del dep._dependencies.edges[spec.name]
+
         # Mark the spec as normal once done.
         self._normal = True
         return any_change
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
index 948cf5dd0f..5c9f559644 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -132,6 +132,24 @@ def current_host(request, monkeypatch):
             yield target
 
 
+@pytest.fixture(scope="function", params=[True, False])
+def fuzz_dep_order(request, monkeypatch):
+    """Metafunction that tweaks the order of iteration over dependencies in the concretizer.
+
+    The original concretizer can be sensitive to this, so we use this to ensure that it
+    is tested forwards and backwards.
+
+    """
+
+    def reverser(pkg_name):
+        if request.param:
+            pkg_cls = spack.repo.PATH.get_pkg_class(pkg_name)
+            reversed_dict = dict(reversed(list(pkg_cls.dependencies.items())))
+            monkeypatch.setattr(pkg_cls, "dependencies", reversed_dict)
+
+    return reverser
+
+
 @pytest.fixture()
 def repo_with_changing_recipe(tmpdir_factory, mutable_mock_repo):
     repo_namespace = "changing"
@@ -895,7 +913,9 @@ class TestConcretize:
             ("py-extension3@1.0 ^python@3.5.1", ["patchelf@0.10"], []),
         ],
     )
-    def test_conditional_dependencies(self, spec_str, expected, unexpected):
+    def test_conditional_dependencies(self, spec_str, expected, unexpected, fuzz_dep_order):
+        fuzz_dep_order("py-extension3")  # test forwards and backwards
+
         s = Spec(spec_str).concretized()
 
         for dep in expected:
diff --git a/lib/spack/spack/test/spec_dag.py b/lib/spack/spack/test/spec_dag.py
index eecae4282d..ecbdd304e7 100644
--- a/lib/spack/spack/test/spec_dag.py
+++ b/lib/spack/spack/test/spec_dag.py
@@ -322,7 +322,7 @@ class TestSpecDag:
         )[0].spec = Spec("mpich@2.0")
 
         with pytest.raises(spack.spec.InconsistentSpecError):
-            mpileaks.flat_dependencies(copy=False)
+            mpileaks.flat_dependencies()
 
     def test_normalize_twice(self):
         """Make sure normalize can be run twice on the same spec,