bugfix: preserve dict order for `Spec.dag_hash()` in Python 2 (#31092)

Fix a bug introduced in #21720. `spack_json.dump()` calls `_strify()` on dictionaries to
convert `unicode` to `str`, but it constructs `dict` objects instead of
`collections.OrderedDict` objects, so in Python 2 (or earlier versions of 3) it can
scramble dictionary order.

This can cause hashes to differ between Python 2 and Python 3, or between Python 3.7
and earlier Python 3's.

- [x] use `OrderedDict` in `_strify`
- [x] add a regression test

2 files changed, 80 insertions, 3 deletions

diff --git a/lib/spack/spack/test/spec_yaml.py b/lib/spack/spack/test/spec_yaml.py
index 7870c881a0..450c88bce8 100644
--- a/lib/spack/spack/test/spec_yaml.py
+++ b/lib/spack/spack/test/spec_yaml.py
@@ -8,7 +8,10 @@
 The YAML and JSON formats preserve DAG information in the spec.
 
 """
+from __future__ import print_function
+
 import ast
+import collections
 import inspect
 import os
 
@@ -433,3 +436,75 @@ spec:
     spec = Spec.from_yaml(yaml)
     concrete_spec = spec.concretized()
     assert concrete_spec.eq_dag(spec)
+
+
+#: A well ordered Spec dictionary, using ``OrderdDict``.
+#: Any operation that transforms Spec dictionaries should
+#: preserve this order.
+ordered_spec = collections.OrderedDict([
+    ("arch", collections.OrderedDict([
+        ("platform", "darwin"),
+        ("platform_os", "bigsur"),
+        ("target", collections.OrderedDict([
+            ("features", [
+                "adx",
+                "aes",
+                "avx",
+                "avx2",
+                "bmi1",
+                "bmi2",
+                "clflushopt",
+                "f16c",
+                "fma",
+                "mmx",
+                "movbe",
+                "pclmulqdq",
+                "popcnt",
+                "rdrand",
+                "rdseed",
+                "sse",
+                "sse2",
+                "sse4_1",
+                "sse4_2",
+                "ssse3",
+                "xsavec",
+                "xsaveopt"
+            ]),
+            ("generation", 0),
+            ("name", "skylake"),
+            ("parents", ["broadwell"]),
+            ("vendor", "GenuineIntel"),
+        ])),
+    ])),
+    ("compiler", collections.OrderedDict([
+        ("name", "apple-clang"),
+        ("version", "13.0.0"),
+    ])),
+    ("name", "zlib"),
+    ("namespace", "builtin"),
+    ("parameters", collections.OrderedDict([
+        ("cflags", []),
+        ("cppflags", []),
+        ("cxxflags", []),
+        ("fflags", []),
+        ("ldflags", []),
+        ("ldlibs", []),
+        ("optimize", True),
+        ("pic", True),
+        ("shared", True),
+    ])),
+    ("version", "1.2.11"),
+])
+
+
+@pytest.mark.regression("31092")
+def test_strify_preserves_order():
+    """Ensure that ``spack_json._strify()`` dumps dictionaries in the right order.
+
+    ``_strify()`` is used in ``spack_json.dump()``, which is used in
+    ``Spec.dag_hash()``, so if this goes wrong, ``Spec`` hashes can vary between python
+    versions.
+
+    """
+    strified = sjson._strify(ordered_spec)
+    assert list(ordered_spec.items()) == list(strified.items())
diff --git a/lib/spack/spack/util/spack_json.py b/lib/spack/spack/util/spack_json.py
index 7083b3c80a..b9fcd1f53f 100644
--- a/lib/spack/spack/util/spack_json.py
+++ b/lib/spack/spack/util/spack_json.py
@@ -4,6 +4,7 @@
 # SPDX-License-Identifier: (Apache-2.0 OR MIT)
 
 """Simple wrapper around JSON to guarantee consistent use of load/dump. """
+import collections
 import json
 from typing import Any, Dict, Optional  # novm
 
@@ -72,9 +73,10 @@ def _strify(data, ignore_dicts=False):
     # if this is a dictionary, return dictionary of byteified keys and values
     # but only if we haven't already byteified it
     if isinstance(data, dict) and not ignore_dicts:
-        return dict((_strify(key, ignore_dicts=True),
-                     _strify(value, ignore_dicts=True)) for key, value in
-                    iteritems(data))
+        return collections.OrderedDict(
+            (_strify(key, ignore_dicts=True), _strify(value, ignore_dicts=True))
+            for key, value in iteritems(data)
+        )
 
     # if it's anything else, return it in its original form
     return data