Remove extensions from view in the correct order (#12961)

When removing packages from a view, extensions were being deactivated
in an arbitrary order. Extensions must be deactivated in preorder
traversal (dependents before dependencies), so when this order was
violated the view update would fail.

This commit ensures that views deactivate extensions based on a
preorder traversal and adds a test for it.

2 files changed, 39 insertions, 17 deletions

diff --git a/lib/spack/spack/filesystem_view.py b/lib/spack/spack/filesystem_view.py
index 5455ccb107..3d17d7e4ce 100644
--- a/lib/spack/spack/filesystem_view.py
+++ b/lib/spack/spack/filesystem_view.py
@@ -399,23 +399,31 @@ class YamlFilesystemView(FilesystemView):
                      "The following packages will be unusable: %s"
                      % ", ".join((s.name for s in dependents)))
 
-        extensions = set(filter(lambda s: s.package.is_extension,
-                         to_deactivate))
-        standalones = to_deactivate - extensions
-
-        # Please note that a traversal of the DAG in post-order and then
-        # forcibly removing each package should remove the need to specify
-        # with_dependents for deactivating extensions/allow removal without
-        # additional checks (force=True). If removal performance becomes
-        # unbearable for whatever reason, this should be the first point of
-        # attack.
-        #
-        # see: https://github.com/spack/spack/pull/3227#discussion_r117147475
-        remove_extension = ft.partial(self.remove_extension,
-                                      with_dependents=with_dependents)
-
-        set(map(remove_extension, extensions))
-        set(map(self.remove_standalone, standalones))
+        # Determine the order that packages should be removed from the view;
+        # dependents come before their dependencies.
+        to_deactivate_sorted = list()
+        depmap = dict()
+        for spec in to_deactivate:
+            depmap[spec] = set(d for d in spec.traverse(root=False)
+                               if d in to_deactivate)
+
+        while depmap:
+            for spec in [s for s, d in depmap.items() if not d]:
+                to_deactivate_sorted.append(spec)
+                for s in depmap.keys():
+                    depmap[s].discard(spec)
+                depmap.pop(spec)
+        to_deactivate_sorted.reverse()
+
+        # Ensure that the sorted list contains all the packages
+        assert set(to_deactivate_sorted) == to_deactivate
+
+        # Remove the packages from the view
+        for spec in to_deactivate_sorted:
+            if spec.package.is_extension:
+                self.remove_extension(spec, with_dependents=with_dependents)
+            else:
+                self.remove_standalone(spec)
 
         self._purge_empty_directories()
 
diff --git a/lib/spack/spack/test/views.py b/lib/spack/spack/test/views.py
index a94fa42c21..52ecb91e73 100644
--- a/lib/spack/spack/test/views.py
+++ b/lib/spack/spack/test/views.py
@@ -6,6 +6,8 @@
 import os
 
 from spack.spec import Spec
+from spack.directory_layout import YamlDirectoryLayout
+from spack.filesystem_view import YamlFilesystemView
 
 
 def test_global_activation(install_mockery, mock_fetch):
@@ -27,3 +29,15 @@ def test_global_activation(install_mockery, mock_fetch):
         extendee_spec.prefix, '.spack', 'extensions.yaml')
     assert (view.extensions_layout.extension_file_path(extendee_spec) ==
             expected_path)
+
+
+def test_remove_extensions_ordered(install_mockery, mock_fetch, tmpdir):
+    view_dir = str(tmpdir.join('view'))
+    layout = YamlDirectoryLayout(view_dir)
+    view = YamlFilesystemView(view_dir, layout)
+    e2 = Spec('extension2').concretized()
+    e2.package.do_install()
+    view.add_specs(e2)
+
+    e1 = e2['extension1']
+    view.remove_specs(e1, e2)