spack diff: make output order deterministic (#25169)

The output order for `spack diff` is nondeterministic for larger diffs -- if you
ran it several times it will not put the fields in the spec in the same order on
successive invocations.

This makes a few fixes to `spack diff`:

- [x] Implement the change discussed in https://github.com/spack/spack/pull/22283#discussion_r598337448
      to make `AspFunction` comparable in and of itself and to eliminate the need for `to_tuple()`

- [x] Sort the lists of diff properties so that the output is always in the same order.

- [x] Make the output for different fields the same as what we use in the solver. Previously, we
      would use `Type(value)` for non-string values and `value` for strings.  Now we just use
      the value.  So the output looks a little cleaner:

      ```
      == Old ==========================        == New ====================
      @@ node_target @@                        @@ node_target @@
      -  gdbm Target(x86_64)                   -  gdbm x86_64
      +  zlib Target(skylake)                  +  zlib skylake
      @@ variant_value @@                      @@ variant_value @@
      -  ncurses symlinks bool(False)          -  ncurses symlinks False
      +  zlib optimize bool(True)              +  zlib optimize True
      @@ version @@                            @@ version @@
      -  gdbm Version(1.18.1)                  -  gdbm 1.18.1
      +  zlib Version(1.2.11)                  +  zlib 1.2.11
      @@ node_os @@                            @@ node_os @@
      -  gdbm catalina                         -  gdbm catalina
      +  zlib catalina                         +  zlib catalina
      ```

I suppose if we want to use `repr()` in the output we could do that and could be
consistent but we don't do that elsewhere -- the types of things in Specs are
all stringifiable so the string and the name of the attribute (`version`, `node_os`,
etc.) are sufficient to know what they are.

6 files changed, 143 insertions, 67 deletions

diff --git a/lib/spack/docs/basic_usage.rst b/lib/spack/docs/basic_usage.rst
index 3503704319..a4b7afe93b 100644
--- a/lib/spack/docs/basic_usage.rst
+++ b/lib/spack/docs/basic_usage.rst
@@ -735,13 +735,13 @@ real quickly since we have two!
         c) use `spack uninstall --all` to uninstall ALL matching specs.
 
 Oh no! We can see from the above that we have two different versions of zlib installed,
-and the only difference between the two is the hash. This is a good use case for 
-``spack diff``, which can easily show us the "diff" or set difference 
+and the only difference between the two is the hash. This is a good use case for
+``spack diff``, which can easily show us the "diff" or set difference
 between properties for two packages. Let's try it out.
 Since the only difference we see in the ``spack find`` view is the hash, let's use
 ``spack diff`` to look for more detail. We will provide the two hashes:
 
-.. code-block::console
+.. code-block:: console
 
     $ spack diff /efzjziy /sl7m27m
     ==> Warning: This interface is subject to change.
@@ -749,34 +749,35 @@ Since the only difference we see in the ``spack find`` view is the hash, let's u
     --- zlib@1.2.11efzjziyc3dmb5h5u5azsthgbgog5mj7g
     +++ zlib@1.2.11sl7m27mzkbejtkrajigj3a3m37ygv4u2
     @@ variant_value @@
-    -  zlib optimize bool(False)
-    +  zlib optimize bool(True)
+    -  zlib optimize False
+    +  zlib optimize True
 
 
 The output is colored, and written in the style of a git diff. This means that you
-can copy paste it into a GitHub markdown as a code block with language "diff" and it
-will render nicely! Here is an example:
+can copy and paste it into a GitHub markdown as a code block with language "diff"
+and it will render nicely! Here is an example:
 
-.. code-block::markdown
+.. code-block:: markdown
 
     ```diff
     --- zlib@1.2.11/efzjziyc3dmb5h5u5azsthgbgog5mj7g
     +++ zlib@1.2.11/sl7m27mzkbejtkrajigj3a3m37ygv4u2
     @@ variant_value @@
-    -  zlib optimize bool(False)
-    +  zlib optimize bool(True)
+    -  zlib optimize False
+    +  zlib optimize True
     ```
 
-Awesome! Now let's read the diff. It tells us that our first zlib was built without optimize (False)
-and the second was built with optimize (True). You can't see it in the docs here, but
-the output above is also colored based on the content being an addition (+) or subtraction (-).
+Awesome! Now let's read the diff. It tells us that our first zlib was built with ``~optimize``
+(``False``) and the second was built with ``+optimize`` (``True``). You can't see it in the docs
+here, but the output above is also colored based on the content being an addition (+) or
+subtraction (-).
 
-This is a small example, but there are actually several kinds of differences that you can view, a variant value
-being just one of them. The first package that you provide (A)
-being diffed against B means that we see what is added to B but not in A (green) and what is present in A that is
-removed in B (red). Here is another example with an additional difference type, ``VERSION``:
+This is a small example, but you will be able to see differences for any attributes on the
+installation spec. Running ``spack diff A B`` means we'll see which spec attributes are on
+``B`` but not on ``A`` (green) and which are on ``A`` but not on ``B`` (red). Here is another
+example with an additional difference type, ``version``:
 
-.. code-block::console
+.. code-block:: console
 
     $ spack diff python@2.7.8 python@3.8.11
     ==> Warning: This interface is subject to change.
@@ -787,42 +788,41 @@ removed in B (red). Here is another example with an additional difference type,
     -  python patches a8c52415a8b03c0e5f28b5d52ae498f7a7e602007db2b9554df28cd5685839b8
     +  python patches 0d98e93189bc278fbc37a50ed7f183bd8aaf249a8e1670a465f0db6bb4f8cf87
     @@ version @@
-    -  openssl Version(1.0.2u)
-    +  openssl Version(1.1.1k)
-    -  python Version(2.7.8)
-    +  python Version(3.8.11)
-
-Let's say that we were only interested in one kind of attribute above, versions!
-We can ask the command to only output this attribute.  To do this, you'd add 
-the ``-a`` for attribute parameter, which defaults to all. 
-Here is how you would filter to show just versions:
+    -  openssl 1.0.2u
+    +  openssl 1.1.1k
+    -  python 2.7.8
+    +  python 3.8.11
 
+Let's say that we were only interested in one kind of attribute above, ``version``.
+We can ask the command to only output this attribute.  To do this, you'd add
+the ``--attribute`` for attribute parameter, which defaults to all. Here is how you
+would filter to show just versions:
 
 .. code-block:: console
 
-    $ spack diff -a version python@2.7.8 python@3.8.11
+    $ spack diff --attribute version python@2.7.8 python@3.8.11
     ==> Warning: This interface is subject to change.
 
     --- python@2.7.8/tsxdi6gl4lihp25qrm4d6nys3nypufbf
     +++ python@3.8.11/yjtseru4nbpllbaxb46q7wfkyxbuvzxx
     @@ version @@
-    -  openssl Version(1.0.2u)
-    +  openssl Version(1.1.1k)
-    -  python Version(2.7.8)
-    +  python Version(3.8.11)
+    -  openssl 1.0.2u
+    +  openssl 1.1.1k
+    -  python 2.7.8
+    +  python 3.8.11
 
-And you can add as many attributes as you'd like with multiple `-a`.
-Finally, if you want to view the data as json (and possibly pipe into an output file)
-just add ``--json``:
+And you can add as many attributes as you'd like with multiple `--attribute` arguments
+(for lots of attributes, you can use ``-a`` for short). Finally, if you want to view the
+data as json (and possibly pipe into an output file) just add ``--json``:
 
 
 .. code-block:: console
-   
+
     $ spack diff --json python@2.7.8 python@3.8.11
 
 
-This data will be much longer because along with the differences for A vs. B and
-B vs. A, we also capture the intersection.
+This data will be much longer because along with the differences for ``A`` vs. ``B`` and
+``B`` vs. ``A``, the JSON output also showsthe intersection.
 
 
 ------------------------
diff --git a/lib/spack/llnl/util/lang.py b/lib/spack/llnl/util/lang.py
index 3e81a34422..abb889ee7b 100644
--- a/lib/spack/llnl/util/lang.py
+++ b/lib/spack/llnl/util/lang.py
@@ -258,6 +258,47 @@ def decorator_with_or_without_args(decorator):
     return new_dec
 
 
+def key_ordering(cls):
+    """Decorates a class with extra methods that implement rich comparison
+       operations and ``__hash__``.  The decorator assumes that the class
+       implements a function called ``_cmp_key()``.  The rich comparison
+       operations will compare objects using this key, and the ``__hash__``
+       function will return the hash of this key.
+
+       If a class already has ``__eq__``, ``__ne__``, ``__lt__``, ``__le__``,
+       ``__gt__``, or ``__ge__`` defined, this decorator will overwrite them.
+
+       Raises:
+           TypeError: If the class does not have a ``_cmp_key`` method
+    """
+    def setter(name, value):
+        value.__name__ = name
+        setattr(cls, name, value)
+
+    if not has_method(cls, '_cmp_key'):
+        raise TypeError("'%s' doesn't define _cmp_key()." % cls.__name__)
+
+    setter('__eq__',
+           lambda s, o:
+           (s is o) or (o is not None and s._cmp_key() == o._cmp_key()))
+    setter('__lt__',
+           lambda s, o: o is not None and s._cmp_key() < o._cmp_key())
+    setter('__le__',
+           lambda s, o: o is not None and s._cmp_key() <= o._cmp_key())
+
+    setter('__ne__',
+           lambda s, o:
+           (s is not o) and (o is None or s._cmp_key() != o._cmp_key()))
+    setter('__gt__',
+           lambda s, o: o is None or s._cmp_key() > o._cmp_key())
+    setter('__ge__',
+           lambda s, o: o is None or s._cmp_key() >= o._cmp_key())
+
+    setter('__hash__', lambda self: hash(self._cmp_key()))
+
+    return cls
+
+
 #: sentinel for testing that iterators are done in lazy_lexicographic_ordering
 done = object()
 
diff --git a/lib/spack/spack/cmd/diff.py b/lib/spack/spack/cmd/diff.py
index ff1f9a41d6..79ba13b568 100644
--- a/lib/spack/spack/cmd/diff.py
+++ b/lib/spack/spack/cmd/diff.py
@@ -80,13 +80,13 @@ def compare_specs(a, b, to_string=False, colorful=True):
     # Prepare a solver setup to parse differences
     setup = asp.SpackSolverSetup()
 
-    a_facts = set(to_tuple(t) for t in setup.spec_clauses(a, body=True))
-    b_facts = set(to_tuple(t) for t in setup.spec_clauses(b, body=True))
+    a_facts = set(t for t in setup.spec_clauses(a, body=True))
+    b_facts = set(t for t in setup.spec_clauses(b, body=True))
 
     # We want to present them to the user as simple key: values
-    intersect = list(a_facts.intersection(b_facts))
-    spec1_not_spec2 = list(a_facts.difference(b_facts))
-    spec2_not_spec1 = list(b_facts.difference(a_facts))
+    intersect = sorted(a_facts.intersection(b_facts))
+    spec1_not_spec2 = sorted(a_facts.difference(b_facts))
+    spec2_not_spec1 = sorted(b_facts.difference(a_facts))
 
     # Format the spec names to be colored
     fmt = "{name}{@version}{/hash}"
@@ -103,32 +103,16 @@ def compare_specs(a, b, to_string=False, colorful=True):
     }
 
 
-def to_tuple(asp_function):
+def flatten(functions):
     """
-    Prepare tuples of objects.
-
-    If we need to save to json, convert to strings
-    See https://gist.github.com/tgamblin/83eba3c6d27f90d9fa3afebfc049ceaf
-    """
-    args = []
-    for arg in asp_function.args:
-        if isinstance(arg, str):
-            args.append(arg)
-            continue
-        args.append("%s(%s)" % (type(arg).__name__, str(arg)))
-    return tuple([asp_function.name] + args)
-
-
-def flatten(tuple_list):
-    """
-    Given a list of tuples, convert into a list of key: value tuples.
+    Given a list of ASP functions, convert into a list of key: value tuples.
 
     We are squashing whatever is after the first index into one string for
     easier parsing in the interface
     """
     updated = []
-    for item in tuple_list:
-        updated.append([item[0], " ".join(item[1:])])
+    for fun in functions:
+        updated.append([fun.name, " ".join(str(a) for a in fun.args)])
     return updated
 
 
diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index 2251183c55..35181d69c9 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -93,6 +93,7 @@ def _id(thing):
         return '"%s"' % str(thing)
 
 
+@llnl.util.lang.key_ordering
 class AspFunction(AspObject):
     def __init__(self, name, args=None):
         self.name = name
diff --git a/lib/spack/spack/test/cmd/diff.py b/lib/spack/spack/test/cmd/diff.py
index 76ab8455b4..f795570a4d 100644
--- a/lib/spack/spack/test/cmd/diff.py
+++ b/lib/spack/spack/test/cmd/diff.py
@@ -30,8 +30,8 @@ def test_diff(install_mockery, mock_fetch, mock_archive, mock_packages):
     c = spack.cmd.diff.compare_specs(specA, specB, to_string=True)
     assert len(c['a_not_b']) == 1
     assert len(c['b_not_a']) == 1
-    assert c['a_not_b'][0] == ['variant_value', 'mpileaks debug bool(False)']
-    assert c['b_not_a'][0] == ['variant_value', 'mpileaks debug bool(True)']
+    assert c['a_not_b'][0] == ['variant_value', 'mpileaks debug False']
+    assert c['b_not_a'][0] == ['variant_value', 'mpileaks debug True']
 
 
 def test_load_first(install_mockery, mock_fetch, mock_archive, mock_packages):
@@ -75,5 +75,5 @@ def test_load_first(install_mockery, mock_fetch, mock_archive, mock_packages):
 
     assert len(result['a_not_b']) == 1
     assert len(result['b_not_a']) == 1
-    assert result['a_not_b'][0] == ['variant_value', 'mpileaks debug bool(False)']
-    assert result['b_not_a'][0] == ['variant_value', 'mpileaks debug bool(True)']
+    assert result['a_not_b'][0] == ['variant_value', 'mpileaks debug False']
+    assert result['b_not_a'][0] == ['variant_value', 'mpileaks debug True']
diff --git a/lib/spack/spack/test/llnl/util/lang.py b/lib/spack/spack/test/llnl/util/lang.py
index 80e4ff92fa..d9561bb2a5 100644
--- a/lib/spack/spack/test/llnl/util/lang.py
+++ b/lib/spack/spack/test/llnl/util/lang.py
@@ -155,3 +155,53 @@ def test_uniq():
     assert [1, 2, 3] == llnl.util.lang.uniq([1, 1, 1, 1, 2, 2, 2, 3, 3])
     assert [1, 2, 1] == llnl.util.lang.uniq([1, 1, 1, 1, 2, 2, 2, 1, 1])
     assert [] == llnl.util.lang.uniq([])
+
+
+def test_key_ordering():
+    """Ensure that key ordering works correctly."""
+
+    with pytest.raises(TypeError):
+        @llnl.util.lang.key_ordering
+        class ClassThatHasNoCmpKeyMethod(object):
+            # this will raise b/c it does not define _cmp_key
+            pass
+
+    @llnl.util.lang.key_ordering
+    class KeyComparable(object):
+        def __init__(self, t):
+            self.t = t
+
+        def _cmp_key(self):
+            return self.t
+
+    a = KeyComparable((1, 2, 3))
+    a2 = KeyComparable((1, 2, 3))
+    b = KeyComparable((2, 3, 4))
+    b2 = KeyComparable((2, 3, 4))
+
+    assert a == a
+    assert a == a2
+    assert a2 == a
+
+    assert b == b
+    assert b == b2
+    assert b2 == b
+
+    assert a != b
+
+    assert a < b
+    assert b > a
+
+    assert a <= b
+    assert b >= a
+
+    assert a <= a
+    assert a <= a2
+    assert b >= b
+    assert b >= b2
+
+    assert hash(a) != hash(b)
+    assert hash(a) == hash(a)
+    assert hash(a) == hash(a2)
+    assert hash(b) == hash(b)
+    assert hash(b) == hash(b2)