Consistent patch ordering (#10879)

* preserve the order in which patches are applied by packages (in spite of grouping them by 'when')

* add tests confirming patch order

10 files changed, 175 insertions, 24 deletions

diff --git a/lib/spack/spack/directives.py b/lib/spack/spack/directives.py
index 08df20ae88..26f43171b8 100644
--- a/lib/spack/spack/directives.py
+++ b/lib/spack/spack/directives.py
@@ -51,6 +51,8 @@ __all__ = []
 #: These are variant names used by Spack internally; packages can't use them
 reserved_names = ['patches']
 
+_patch_order_index = 0
+
 
 class DirectiveMeta(type):
     """Flushes the directives that were temporarily stored in the staging
@@ -267,8 +269,8 @@ def _depends_on(pkg, spec, when=None, type=default_deptype, patches=None):
         patches = [patches]
 
     # auto-call patch() directive on any strings in patch list
-    patches = [patch(p) if isinstance(p, string_types)
-               else p for p in patches]
+    patches = [patch(p) if isinstance(p, string_types) else p
+               for p in patches]
     assert all(callable(p) for p in patches)
 
     # this is where we actually add the dependency to this package
@@ -422,12 +424,18 @@ def patch(url_or_filename, level=1, when=None, working_dir=".", **kwargs):
         if isinstance(pkg, Dependency):
             pkg = pkg.pkg
 
+        global _patch_order_index
+        ordering_key = (pkg.name, _patch_order_index)
+        _patch_order_index += 1
+
         if '://' in url_or_filename:
             patch = spack.patch.UrlPatch(
-                pkg, url_or_filename, level, working_dir, **kwargs)
+                pkg, url_or_filename, level, working_dir,
+                ordering_key=ordering_key, **kwargs)
         else:
             patch = spack.patch.FilePatch(
-                pkg, url_or_filename, level, working_dir)
+                pkg, url_or_filename, level, working_dir,
+                ordering_key=ordering_key)
 
         cur_patches.append(patch)
 
diff --git a/lib/spack/spack/patch.py b/lib/spack/spack/patch.py
index 9895fde4e1..ef03c54f45 100644
--- a/lib/spack/spack/patch.py
+++ b/lib/spack/spack/patch.py
@@ -107,12 +107,14 @@ class FilePatch(Patch):
         working_dir (str): path within the source directory where patch
             should be applied
     """
-    def __init__(self, pkg, relative_path, level, working_dir):
+    def __init__(self, pkg, relative_path, level, working_dir,
+                 ordering_key=None):
         self.relative_path = relative_path
         abs_path = os.path.join(pkg.package_dir, self.relative_path)
         super(FilePatch, self).__init__(pkg, abs_path, level, working_dir)
         self.path = abs_path
         self._sha256 = None
+        self.ordering_key = ordering_key
 
     @property
     def sha256(self):
@@ -136,11 +138,14 @@ class UrlPatch(Patch):
         working_dir (str): path within the source directory where patch
             should be applied
     """
-    def __init__(self, pkg, url, level=1, working_dir='.', **kwargs):
+    def __init__(self, pkg, url, level=1, working_dir='.', ordering_key=None,
+                 **kwargs):
         super(UrlPatch, self).__init__(pkg, url, level, working_dir)
 
         self.url = url
 
+        self.ordering_key = ordering_key
+
         self.archive_sha256 = kwargs.get('archive_sha256')
         if allowed_archive(self.url) and not self.archive_sha256:
             raise PatchDirectiveError(
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index e74d38ea5e..ce5a536c6e 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -94,6 +94,7 @@ from llnl.util.filesystem import find_headers, find_libraries, is_exe
 from llnl.util.lang import key_ordering, HashableMap, ObjectWrapper, dedupe
 from llnl.util.lang import check_kwargs, memoized
 from llnl.util.tty.color import cwrite, colorize, cescape, get_color_when
+import llnl.util.tty as tty
 
 import spack.architecture
 import spack.compiler
@@ -1918,6 +1919,9 @@ class Spec(object):
             raise InvalidDependencyError(
                 self.name + " does not depend on " + comma_or(extra))
 
+        # This dictionary will store object IDs rather than Specs as keys
+        # since the Spec __hash__ will change as patches are added to them
+        spec_to_patches = {}
         for s in self.traverse():
             # After concretizing, assign namespaces to anything left.
             # Note that this doesn't count as a "change".  The repository
@@ -1938,16 +1942,12 @@ class Spec(object):
             for cond, patch_list in s.package_class.patches.items():
                 if s.satisfies(cond):
                     for patch in patch_list:
-                        patches.append(patch.sha256)
+                        patches.append(patch)
             if patches:
-                mvar = s.variants.setdefault(
-                    'patches', MultiValuedVariant('patches', ())
-                )
-                mvar.value = patches
-                # FIXME: Monkey patches mvar to store patches order
-                mvar._patches_in_order_of_appearance = patches
+                spec_to_patches[id(s)] = patches
 
-        # Apply patches required on dependencies by depends_on(..., patch=...)
+        # Also record all patches required on dependencies by
+        # depends_on(..., patch=...)
         for dspec in self.traverse_edges(deptype=all,
                                          cover='edges', root=False):
             pkg_deps = dspec.parent.package_class.dependencies
@@ -1963,16 +1963,29 @@ class Spec(object):
                     for pcond, patch_list in dependency.patches.items():
                         if dspec.spec.satisfies(pcond):
                             for patch in patch_list:
-                                patches.append(patch.sha256)
+                                patches.append(patch)
             if patches:
-                mvar = dspec.spec.variants.setdefault(
-                    'patches', MultiValuedVariant('patches', ())
-                )
-                mvar.value = mvar.value + tuple(patches)
-                # FIXME: Monkey patches mvar to store patches order
-                p = getattr(mvar, '_patches_in_order_of_appearance', [])
-                mvar._patches_in_order_of_appearance = list(
-                    dedupe(p + patches))
+                all_patches = spec_to_patches.setdefault(id(dspec.spec), [])
+                all_patches.extend(patches)
+
+        for spec in self.traverse():
+            if id(spec) not in spec_to_patches:
+                continue
+
+            patches = list(dedupe(spec_to_patches[id(spec)]))
+            mvar = spec.variants.setdefault(
+                'patches', MultiValuedVariant('patches', ())
+            )
+            mvar.value = tuple(p.sha256 for p in patches)
+            # FIXME: Monkey patches mvar to store patches order
+            full_order_keys = list(tuple(p.ordering_key) + (p.sha256,) for p
+                                   in patches)
+            ordered_hashes = sorted(full_order_keys)
+            tty.debug("Ordered hashes [{0}]: ".format(spec.name) +
+                      ', '.join('/'.join(str(e) for e in t)
+                                for t in ordered_hashes))
+            mvar._patches_in_order_of_appearance = list(
+                t[-1] for t in ordered_hashes)
 
         for s in self.traverse():
             if s.external_module and not s.external_path:
diff --git a/lib/spack/spack/test/patch.py b/lib/spack/spack/test/patch.py
index f06d9fd7d5..a62ebb8599 100644
--- a/lib/spack/spack/test/patch.py
+++ b/lib/spack/spack/test/patch.py
@@ -104,6 +104,33 @@ def test_patch_in_spec(mock_packages, config):
              baz_sha256) ==
             spec.variants['patches'].value)
 
+    assert ((foo_sha256, bar_sha256, baz_sha256) ==
+            tuple(spec.variants['patches']._patches_in_order_of_appearance))
+
+
+def test_patch_order(mock_packages, config):
+    spec = Spec('dep-diamond-patch-top')
+    spec.concretize()
+
+    mid2_sha256 = 'mid21234abcd1234abcd1234abcd1234abcd1234abcd1234abcd1234abcd1234'  # noqa: E501
+    mid1_sha256 = '0b62284961dab49887e31319843431ee5b037382ac02c4fe436955abef11f094'  # noqa: E501
+    top_sha256 = 'f7de2947c64cb6435e15fb2bef359d1ed5f6356b2aebb7b20535e3772904e6db'  # noqa: E501
+
+    dep = spec['patch']
+    patch_order = dep.variants['patches']._patches_in_order_of_appearance
+    # 'mid2' comes after 'mid1' alphabetically
+    # 'top' comes after 'mid1'/'mid2' alphabetically
+    # 'patch' comes last of all specs in the dag, alphabetically, so the
+    # patches of 'patch' to itself are applied last. The patches applied by
+    # 'patch' are ordered based on their appearance in the package.py file
+    expected_order = (
+        mid1_sha256,
+        mid2_sha256,
+        top_sha256,
+        foo_sha256, bar_sha256, baz_sha256)
+
+    assert expected_order == tuple(patch_order)
+
 
 def test_nested_directives(mock_packages):
     """Ensure pkg data structures are set up properly by nested directives."""
diff --git a/var/spack/repos/builtin.mock/packages/dep-diamond-patch-mid1/mid1.patch b/var/spack/repos/builtin.mock/packages/dep-diamond-patch-mid1/mid1.patch
new file mode 100644
index 0000000000..a4adb72bb1
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/dep-diamond-patch-mid1/mid1.patch
@@ -0,0 +1 @@
+mid1
diff --git a/var/spack/repos/builtin.mock/packages/dep-diamond-patch-mid1/package.py b/var/spack/repos/builtin.mock/packages/dep-diamond-patch-mid1/package.py
new file mode 100644
index 0000000000..f4ec1554fa
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/dep-diamond-patch-mid1/package.py
@@ -0,0 +1,30 @@
+# Copyright 2013-2019 Lawrence Livermore National Security, LLC and other
+# Spack Project Developers. See the top-level COPYRIGHT file for details.
+#
+# SPDX-License-Identifier: (Apache-2.0 OR MIT)
+
+from spack import *
+
+
+class DepDiamondPatchMid1(Package):
+    r"""Package that requires a patch on a dependency
+
+  W
+ / \
+X   Y
+ \ /
+  Z
+
+    This is package X
+    """
+
+    homepage = "http://www.example.com"
+    url = "http://www.example.com/patch-a-dependency-1.0.tar.gz"
+
+    version('1.0', '0123456789abcdef0123456789abcdef')
+
+    # single patch file in repo
+    depends_on('patch', patches='mid1.patch')
+
+    def install(self, spec, prefix):
+        pass
diff --git a/var/spack/repos/builtin.mock/packages/dep-diamond-patch-mid2/package.py b/var/spack/repos/builtin.mock/packages/dep-diamond-patch-mid2/package.py
new file mode 100644
index 0000000000..2aea75f307
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/dep-diamond-patch-mid2/package.py
@@ -0,0 +1,33 @@
+# Copyright 2013-2019 Lawrence Livermore National Security, LLC and other
+# Spack Project Developers. See the top-level COPYRIGHT file for details.
+#
+# SPDX-License-Identifier: (Apache-2.0 OR MIT)
+
+from spack import *
+
+
+class DepDiamondPatchMid2(Package):
+    r"""Package that requires a patch on a dependency
+
+  W
+ / \
+X   Y
+ \ /
+  Z
+
+    This is package Y
+    """
+
+    homepage = "http://www.example.com"
+    url = "http://www.example.com/patch-a-dependency-1.0.tar.gz"
+
+    version('1.0', '0123456789abcdef0123456789abcdef')
+
+    # single patch file in repo
+    depends_on('patch', patches=[
+        patch('http://example.com/urlpatch.patch',
+              sha256='mid21234abcd1234abcd1234abcd1234abcd1234abcd1234abcd1234abcd1234'),  # noqa: E501
+    ])
+
+    def install(self, spec, prefix):
+        pass
diff --git a/var/spack/repos/builtin.mock/packages/dep-diamond-patch-top/package.py b/var/spack/repos/builtin.mock/packages/dep-diamond-patch-top/package.py
new file mode 100644
index 0000000000..21388011c5
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/dep-diamond-patch-top/package.py
@@ -0,0 +1,32 @@
+# Copyright 2013-2019 Lawrence Livermore National Security, LLC and other
+# Spack Project Developers. See the top-level COPYRIGHT file for details.
+#
+# SPDX-License-Identifier: (Apache-2.0 OR MIT)
+
+from spack import *
+
+
+class DepDiamondPatchTop(Package):
+    r"""Package that requires a patch on a dependency
+
+  W
+ / \
+X   Y
+ \ /
+  Z
+
+    This is package W
+    """
+
+    homepage = "http://www.example.com"
+    url = "http://www.example.com/patch-a-dependency-1.0.tar.gz"
+
+    version('1.0', '0123456789abcdef0123456789abcdef')
+
+    # single patch file in repo
+    depends_on('patch', patches='top.patch')
+    depends_on('dep-diamond-patch-mid1')
+    depends_on('dep-diamond-patch-mid2')
+
+    def install(self, spec, prefix):
+        pass
diff --git a/var/spack/repos/builtin.mock/packages/dep-diamond-patch-top/top.patch b/var/spack/repos/builtin.mock/packages/dep-diamond-patch-top/top.patch
new file mode 100644
index 0000000000..bf1a1fdefa
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/dep-diamond-patch-top/top.patch
@@ -0,0 +1 @@
+top
diff --git a/var/spack/repos/builtin.mock/packages/patch/package.py b/var/spack/repos/builtin.mock/packages/patch/package.py
index 704362af37..37ea72fb1a 100644
--- a/var/spack/repos/builtin.mock/packages/patch/package.py
+++ b/var/spack/repos/builtin.mock/packages/patch/package.py
@@ -13,9 +13,10 @@ class Patch(Package):
     url = "http://www.example.com/patch-1.0.tar.gz"
 
     version('1.0', '0123456789abcdef0123456789abcdef')
+    version('2.0', '0123456789abcdef0123456789abcdef')
 
     patch('foo.patch')
-    patch('bar.patch')
+    patch('bar.patch', when='@2:')
     patch('baz.patch')
 
     def install(self, spec, prefix):