bugfix: fix config merge order for OrderdDicts (#18482)

The logic in `config.py` merges lists correctly so that list elements
from higher-precedence config files come first, but the way we merge
`dict` elements reverses the precedence.

Since `mirrors.yaml` relies on `OrderedDict` for precedence, this bug
causes mirrors in lower-precedence config scopes to be checked before
higher-precedence scopes.

We should probably convert `mirrors.yaml` to use a list at some point,
but in the meantie here's a fix for `OrderedDict`.

- [x] ensuring that keys are ordered correctly in `OrderedDict` by
      re-inserting keys from the destination `dict` after adding the keys from
      the source `dict`.

- [x] also simplify the logic in `merge_yaml` by always reinserting
      common keys -- this preserves mark information without all the special
      cases, and makes it simpler to preserve insertion order.

Assuming a default spack configuration, if we run this:

```console
$ spack mirror add foo https://bar.com
```

Results before this change:

```console
$ spack config blame mirrors
---                                                          mirrors:
/Users/gamblin2/src/spack/etc/spack/defaults/mirrors.yaml:2    spack-public: https://spack-llnl-mirror.s3-us-west-2.amazonaws.com/
/Users/gamblin2/.spack/mirrors.yaml:2                          foo: https://bar.com
```

Results after:

```console
$ spack config blame mirrors
---                                                          mirrors:
/Users/gamblin2/.spack/mirrors.yaml:2                          foo: https://bar.com
/Users/gamblin2/src/spack/etc/spack/defaults/mirrors.yaml:2    spack-public: https://spack-llnl-mirror.s3-us-west-2.amazonaws.com/
```

5 files changed, 67 insertions, 30 deletions

diff --git a/lib/spack/spack/cmd/external.py b/lib/spack/spack/cmd/external.py
index 9570576c4f..52af72ed8f 100644
--- a/lib/spack/spack/cmd/external.py
+++ b/lib/spack/spack/cmd/external.py
@@ -230,7 +230,7 @@ def _update_pkg_config(scope, pkg_to_entries, not_buildable):
 
     pkgs_cfg = spack.config.get('packages', scope=scope)
 
-    spack.config.merge_yaml(pkgs_cfg, pkg_to_cfg)
+    pkgs_cfg = spack.config.merge_yaml(pkgs_cfg, pkg_to_cfg)
     spack.config.set('packages', pkgs_cfg, scope=scope)
 
     return all_new_specs
diff --git a/lib/spack/spack/config.py b/lib/spack/spack/config.py
index a0fcdd100a..9c12454edb 100644
--- a/lib/spack/spack/config.py
+++ b/lib/spack/spack/config.py
@@ -959,6 +959,11 @@ def merge_yaml(dest, source):
 
        dest = merge_yaml(dest, source)
 
+    In the result, elements from lists from ``source`` will appear before
+    elements of lists from ``dest``. Likewise, when iterating over keys
+    or items in merged ``OrderedDict`` objects, keys from ``source`` will
+    appear before keys from ``dest``.
+
     Config file authors can optionally end any attribute in a dict
     with `::` instead of `:`, and the key will override that of the
     parent instead of merging.
@@ -978,34 +983,26 @@ def merge_yaml(dest, source):
 
     # Source dict is merged into dest.
     elif they_are(dict):
-        # track keys for marking
-        key_marks = {}
+        # save dest keys to reinsert later -- this ensures that  source items
+        # come *before* dest in OrderdDicts
+        dest_keys = [dk for dk in dest.keys() if dk not in source]
 
         for sk, sv in iteritems(source):
-            if _override(sk) or sk not in dest:
-                # if sk ended with ::, or if it's new, completely override
-                dest[sk] = copy.copy(sv)
-                # copy ruamel comments manually
+            # always remove the dest items. Python dicts do not overwrite
+            # keys on insert, so this ensures that source keys are copied
+            # into dest along with mark provenance (i.e., file/line info).
+            merge = sk in dest
+            old_dest_value = dest.pop(sk, None)
+
+            if merge and not _override(sk):
+                dest[sk] = merge_yaml(old_dest_value, sv)
             else:
-                # otherwise, merge the YAML
-                dest[sk] = merge_yaml(dest[sk], source[sk])
-
-            # this seems unintuitive, but see below. We need this because
-            # Python dicts do not overwrite keys on insert, and we want
-            # to copy mark information on source keys to dest.
-            key_marks[sk] = sk
-
-        # ensure that keys are marked in the destination. The
-        # key_marks dict ensures we can get the actual source key
-        # objects from dest keys
-        for dk in list(dest.keys()):
-            if dk in key_marks and syaml.markable(dk):
-                syaml.mark(dk, key_marks[dk])
-            elif dk in key_marks:
-                # The destination key may not be markable if it was derived
-                # from a schema default. In this case replace the key.
-                val = dest.pop(dk)
-                dest[key_marks[dk]] = val
+                # if sk ended with ::, or if it's new, completely override
+                dest[sk] = copy.deepcopy(sv)
+
+        # reinsert dest keys so they are last in the result
+        for dk in dest_keys:
+            dest[dk] = dest.pop(dk)
 
         return dest
 
diff --git a/lib/spack/spack/test/cmd/config.py b/lib/spack/spack/test/cmd/config.py
index d330754aa1..7830f1c4e2 100644
--- a/lib/spack/spack/test/cmd/config.py
+++ b/lib/spack/spack/test/cmd/config.py
@@ -326,14 +326,15 @@ def test_config_add_update_dict_from_file(mutable_empty_config, tmpdir):
     # get results
     output = config('get', 'packages')
 
+    # added config comes before prior config
     expected = """packages:
   all:
-    compiler: [gcc]
     version:
     - 1.0.0
+    compiler: [gcc]
 """
 
-    assert output == expected
+    assert expected == output
 
 
 def test_config_add_invalid_file_fails(tmpdir):
diff --git a/lib/spack/spack/test/config.py b/lib/spack/spack/test/config.py
index 55bdcb674c..f43a571e73 100644
--- a/lib/spack/spack/test/config.py
+++ b/lib/spack/spack/test/config.py
@@ -430,6 +430,41 @@ def test_read_config_override_list(mock_low_high_config, write_config_file):
     }
 
 
+def test_ordereddict_merge_order():
+    """"Test that source keys come before dest keys in merge_yaml results."""
+    source = syaml.syaml_dict([
+        ("k1", "v1"),
+        ("k2", "v2"),
+        ("k3", "v3"),
+    ])
+
+    dest = syaml.syaml_dict([
+        ("k4", "v4"),
+        ("k3", "WRONG"),
+        ("k5", "v5"),
+    ])
+
+    result = spack.config.merge_yaml(dest, source)
+    assert "WRONG" not in result.values()
+
+    expected_keys = ["k1", "k2", "k3", "k4", "k5"]
+    expected_items = [
+        ("k1", "v1"), ("k2", "v2"), ("k3", "v3"), ("k4", "v4"), ("k5", "v5")
+    ]
+    assert expected_keys == list(result.keys())
+    assert expected_items == list(result.items())
+
+
+def test_list_merge_order():
+    """"Test that source lists are prepended to dest."""
+    source = ["a", "b", "c"]
+    dest = ["d", "e", "f"]
+
+    result = spack.config.merge_yaml(dest, source)
+
+    assert ["a", "b", "c", "d", "e", "f"] == result
+
+
 def test_internal_config_update(mock_low_high_config, write_config_file):
     write_config_file('config', config_low, 'low')
 
diff --git a/lib/spack/spack/test/config_values.py b/lib/spack/spack/test/config_values.py
index bea1283b74..a0bf7e52f8 100644
--- a/lib/spack/spack/test/config_values.py
+++ b/lib/spack/spack/test/config_values.py
@@ -35,8 +35,12 @@ def test_set_install_hash_length_upper_case(mock_packages, mutable_config,
     mutable_config.set('config:install_hash_length', 5)
     mutable_config.set(
         'config:install_tree',
-        {'root': str(tmpdir),
-         'projections': {'all': '{name}-{HASH}'}}
+        {
+            'root': str(tmpdir),
+            'projections': {
+                'all': '{name}-{HASH}'
+            }
+        }
     )
     monkeypatch.setattr(spack.store, 'store', spack.store._store())