PING: Re: [PATCH] json: preserve key-insertion order [PR109163]

[David Malcolm <dmalcolm@redhat.com>]

I'd like to ping the following patch for review:
  https://gcc.gnu.org/pipermail/gcc-patches/2023-March/614165.html

Thanks
Dave

On Fri, 2023-03-17 at 16:53 -0400, David Malcolm wrote:
> PR other/109163 notes that when we write out JSON files, we traverse
> the keys within each object via hash_map iteration, and thus the
> ordering is non-deterministic - it can arbitrarily vary from run to
> run and from different machines, making it harder for users to
> compare
> results and determine if anything has "really" changed.
> 
> I'm running into this issue with SARIF output, but there are several
> places where we're currently emitting JSON:
> 
>   * -fsave-optimization-record emits SRCFILE.opt-record.json.gz
>         "This option is experimental and the format of the data
> within
>         the compressed JSON file is subject to change."; see
>         optinfo-emit-json.{h,cc}, dumpfile.cc, etc
>   * -fdiagnostics-format= with the various "sarif" and "json" options
>   * -fdump-analyzer-json is a developer option in the analyzer
>   * gcov has:
>      "-j, --json-format: Output JSON intermediate format into
>      .gcov.json.gz file"
> 
> This patch adds an auto_vec to class json::object to preserve
> key-insertion order, and use it when writing out objects. 
> Potentially
> this slightly slows down JSON output, but I believe that this isn't
> normally a bottleneck, and that the benefits to the user of
> deterministic output are worth it.
> 
> I had first attempted to use ordered_hash_map.h for this, but ran
> into
> impenetrable template errors, so this patch uses a simpler approach
> of
> just adding an auto_vec to json::object.
> 
> Testing showed a failure of diagnostic-format-json-5.c, which was
> using
> a convoluted set of regexps to consume the output; I believe that
> this
> was brittle, and was intermittently failing for some of the random
> orderings of output.  I rewrote these regexps to work with the
> expected
> output order.  The other such tests seem to pass with the
> now-deterministic orderings.
> 
> Lightly tested with valgrind.
> I manually verified that the SARIF output is now deterministic.
> Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
> 
> OK for trunk?
> 
> gcc/ChangeLog:
>         PR other/109163
>         * json.cc: Update comments to indicate that we now preserve
>         insertion order of keys within objects.
>         (object::print): Traverse keys in insertion order.
>         (object::set): Preserve insertion order of keys.
>         (selftest::test_writing_objects): Add an additional key to
> verify
>         that we preserve insertion order.
>         * json.h (object::m_keys): New field.
> 
> gcc/testsuite/ChangeLog:
>         PR other/109163
>         * c-c++-common/diagnostic-format-json-1.c: Update comment.
>         * c-c++-common/diagnostic-format-json-2.c: Likewise.
>         * c-c++-common/diagnostic-format-json-3.c: Likewise.
>         * c-c++-common/diagnostic-format-json-4.c: Likewise.
>         * c-c++-common/diagnostic-format-json-5.c: Rewrite regexps.
>         * c-c++-common/diagnostic-format-json-stderr-1.c: Update
> comment.
> 
> Signed-off-by: David Malcolm <dmalcolm@redhat.com>
> ---
>  gcc/json.cc                                   |  40 ++++---
>  gcc/json.h                                    |  10 +-
>  .../c-c++-common/diagnostic-format-json-1.c   |   3 +-
>  .../c-c++-common/diagnostic-format-json-2.c   |   3 +-
>  .../c-c++-common/diagnostic-format-json-3.c   |   3 +-
>  .../c-c++-common/diagnostic-format-json-4.c   |   3 +-
>  .../c-c++-common/diagnostic-format-json-5.c   | 100 ++++++++++------
> --
>  .../diagnostic-format-json-stderr-1.c         |   3 +-
>  8 files changed, 95 insertions(+), 70 deletions(-)
> 
> diff --git a/gcc/json.cc b/gcc/json.cc
> index 01879c9c466..741e97b20e5 100644
> --- a/gcc/json.cc
> +++ b/gcc/json.cc
> @@ -31,8 +31,11 @@ using namespace json;
>  /* class json::value.  */
>  
>  /* Dump this json::value tree to OUTF.
> -   No formatting is done.  There are no guarantees about the order
> -   in which the key/value pairs of json::objects are printed.  */
> +
> +   No formatting is done.
> +
> +   The key/value pairs of json::objects are printed in the order
> +   in which the keys were originally inserted.  */
>  
>  void
>  value::dump (FILE *outf) const
> @@ -44,7 +47,7 @@ value::dump (FILE *outf) const
>  }
>  
>  /* class json::object, a subclass of json::value, representing
> -   an unordered collection of key/value pairs.  */
> +   an ordered collection of key/value pairs.  */
>  
>  /* json:object's dtor.  */
>  
> @@ -62,14 +65,17 @@ object::~object ()
>  void
>  object::print (pretty_printer *pp) const
>  {
> -  /* Note that the order is not guaranteed.  */
>    pp_character (pp, '{');
> -  for (map_t::iterator it = m_map.begin (); it != m_map.end ();
> ++it)
> +
> +  /* Iterate in the order that the keys were inserted.  */
> +  unsigned i;
> +  const char *key;
> +  FOR_EACH_VEC_ELT (m_keys, i, key)
>      {
> -      if (it != m_map.begin ())
> +      if (i > 0)
>         pp_string (pp, ", ");
> -      const char *key = const_cast <char *>((*it).first);
> -      value *value = (*it).second;
> +      map_t &mut_map = const_cast<map_t &> (m_map);
> +      value *value = *mut_map.get (key);
>        pp_doublequote (pp);
>        pp_string (pp, key); // FIXME: escaping?
>        pp_doublequote (pp);
> @@ -97,9 +103,13 @@ object::set (const char *key, value *v)
>        *ptr = v;
>      }
>    else
> -    /* If the key wasn't already present, take a copy of the key,
> -       and store the value.  */
> -    m_map.put (xstrdup (key), v);
> +    {
> +      /* If the key wasn't already present, take a copy of the key,
> +        and store the value.  */
> +      char *owned_key = xstrdup (key);
> +      m_map.put (owned_key, v);
> +      m_keys.safe_push (owned_key);
> +    }
>  }
>  
>  /* Get the json::value * for KEY.
> @@ -295,15 +305,17 @@ test_object_get ()
>    ASSERT_EQ (obj.get ("not-present"), NULL);
>  }
>  
> -/* Verify that JSON objects are written correctly.  We can't test
> more than
> -   one key/value pair, as we don't impose a guaranteed ordering.  */
> +/* Verify that JSON objects are written correctly.  */
>  
>  static void
>  test_writing_objects ()
>  {
>    object obj;
>    obj.set ("foo", new json::string ("bar"));
> -  assert_print_eq (obj, "{\"foo\": \"bar\"}");
> +  obj.set ("baz", new json::string ("quux"));
> +  /* This test relies on json::object writing out key/value pairs
> +     in key-insertion order.  */
> +  assert_print_eq (obj, "{\"foo\": \"bar\", \"baz\": \"quux\"}");
>  }
>  
>  /* Verify that JSON arrays are written correctly.  */
> diff --git a/gcc/json.h b/gcc/json.h
> index aa52ba2951a..057119db277 100644
> --- a/gcc/json.h
> +++ b/gcc/json.h
> @@ -82,8 +82,11 @@ class value
>    void dump (FILE *) const;
>  };
>  
> -/* Subclass of value for objects: an unordered collection of
> -   key/value pairs.  */
> +/* Subclass of value for objects: a collection of key/value pairs
> +   preserving the ordering in which keys were inserted.
> +
> +   Preserving the order eliminates non-determinism in the output,
> +   making it easier for the user to compare repeated invocations. 
> */
>  
>  class object : public value
>  {
> @@ -100,6 +103,9 @@ class object : public value
>    typedef hash_map <char *, value *,
>      simple_hashmap_traits<nofree_string_hash, value *> > map_t;
>    map_t m_map;
> +
> +  /* Keep track of order in which keys were inserted.  */
> +  auto_vec <const char *> m_keys;
>  };
>  
>  /* Subclass of value for arrays.  */
> diff --git a/gcc/testsuite/c-c++-common/diagnostic-format-json-1.c
> b/gcc/testsuite/c-c++-common/diagnostic-format-json-1.c
> index af57eb636d5..6bab30e3e6c 100644
> --- a/gcc/testsuite/c-c++-common/diagnostic-format-json-1.c
> +++ b/gcc/testsuite/c-c++-common/diagnostic-format-json-1.c
> @@ -4,8 +4,7 @@
>  #error message
>  
>  /* Use dg-regexp to consume the JSON output starting with
> -   the innermost values, and working outwards.
> -   We can't rely on any ordering of the keys.  */
> +   the innermost values, and working outwards.  */
>  
>  /* { dg-regexp "\"kind\": \"error\"" } */
>  /* { dg-regexp "\"column-origin\": 1" } */
> diff --git a/gcc/testsuite/c-c++-common/diagnostic-format-json-2.c
> b/gcc/testsuite/c-c++-common/diagnostic-format-json-2.c
> index edb802efb8d..3c12103c9f8 100644
> --- a/gcc/testsuite/c-c++-common/diagnostic-format-json-2.c
> +++ b/gcc/testsuite/c-c++-common/diagnostic-format-json-2.c
> @@ -4,8 +4,7 @@
>  #warning message
>  
>  /* Use dg-regexp to consume the JSON output starting with
> -   the innermost values, and working outwards.
> -   We can't rely on any ordering of the keys.  */
> +   the innermost values, and working outwards.  */
>  
>  /* { dg-regexp "\"kind\": \"warning\"" } */
>  /* { dg-regexp "\"column-origin\": 1" } */
> diff --git a/gcc/testsuite/c-c++-common/diagnostic-format-json-3.c
> b/gcc/testsuite/c-c++-common/diagnostic-format-json-3.c
> index bb7b8dc5d16..11d74624ff1 100644
> --- a/gcc/testsuite/c-c++-common/diagnostic-format-json-3.c
> +++ b/gcc/testsuite/c-c++-common/diagnostic-format-json-3.c
> @@ -4,8 +4,7 @@
>  #warning message
>  
>  /* Use dg-regexp to consume the JSON output starting with
> -   the innermost values, and working outwards.
> -   We can't rely on any ordering of the keys.  */
> +   the innermost values, and working outwards.  */
>  
>  /* { dg-regexp "\"kind\": \"error\"" } */
>  /* { dg-regexp "\"column-origin\": 1" } */
> diff --git a/gcc/testsuite/c-c++-common/diagnostic-format-json-4.c
> b/gcc/testsuite/c-c++-common/diagnostic-format-json-4.c
> index 8ac90723cbd..cec1cf924b4 100644
> --- a/gcc/testsuite/c-c++-common/diagnostic-format-json-4.c
> +++ b/gcc/testsuite/c-c++-common/diagnostic-format-json-4.c
> @@ -10,8 +10,7 @@ int test (void)
>  }
>  
>  /* Use dg-regexp to consume the JSON output starting with
> -   the innermost values, and working outwards.
> -   We can't rely on any ordering of the keys.  */
> +   the innermost values, and working outwards.  */
>  
>  /* Verify nested diagnostics.  */
>  
> diff --git a/gcc/testsuite/c-c++-common/diagnostic-format-json-5.c
> b/gcc/testsuite/c-c++-common/diagnostic-format-json-5.c
> index 8d2eb0c5089..86f8c5fb374 100644
> --- a/gcc/testsuite/c-c++-common/diagnostic-format-json-5.c
> +++ b/gcc/testsuite/c-c++-common/diagnostic-format-json-5.c
> @@ -8,49 +8,61 @@ int test (struct s *ptr)
>    return ptr->colour;
>  }
>  
> -/* Use dg-regexp to consume the JSON output starting with
> -   the innermost values, and working outwards.
> -   We can't rely on any ordering of the keys.  */
> +/* Verify fix-it hints.
>  
> -/* { dg-regexp "\"kind\": \"error\"" } */
> -/* { dg-regexp "\"column-origin\": 1" } */
> -/* { dg-regexp "\"escape-source\": false" } */
> -/* { dg-regexp "\"message\": \".*\"" } */
> +   Use dg-regexp to consume the JSON output from start to
> +   finish, relying on the ordering of the keys.
> +   The following uses indentation to visualize the structure
> +   of the JSON (although the actual output is all on one line).
>  
> -/* Verify fix-it hints.  */
> -
> -/* { dg-regexp "\"string\": \"color\"" } */
> -
> -/* { dg-regexp "\"start\": \{" } */
> -/* { dg-regexp "\"file\": \"\[^\n\r\"\]*diagnostic-format-json-
> 5.c\"" } */
> -/* { dg-regexp "\"line\": 8" } */
> -/* { dg-regexp "\"column\": 15" } */
> -/* { dg-regexp "\"display-column\": 15" } */
> -/* { dg-regexp "\"byte-column\": 15" } */
> -
> -/* { dg-regexp "\"next\": \{" } */
> -/* { dg-regexp "\"file\": \"\[^\n\r\"\]*diagnostic-format-json-
> 5.c\"" } */
> -/* { dg-regexp "\"line\": 8" } */
> -/* { dg-regexp "\"column\": 21" } */
> -/* { dg-regexp "\"display-column\": 21" } */
> -/* { dg-regexp "\"byte-column\": 21" } */
> -
> -/* { dg-regexp "\"fixits\": \[\[\{\}, \]*\]" } */
> -
> -/* { dg-regexp "\"caret\": \{" } */
> -/* { dg-regexp "\"file\": \"\[^\n\r\"\]*diagnostic-format-json-
> 5.c\"" } */
> -/* { dg-regexp "\"line\": 8" } */
> -/* { dg-regexp "\"column\": 15" } */
> -/* { dg-regexp "\"display-column\": 15" } */
> -/* { dg-regexp "\"byte-column\": 15" } */
> -
> -/* { dg-regexp "\"finish\": \{" } */
> -/* { dg-regexp "\"file\": \"\[^\n\r\"\]*diagnostic-format-json-
> 5.c\"" } */
> -/* { dg-regexp "\"line\": 8" } */
> -/* { dg-regexp "\"column\": 20" } */
> -/* { dg-regexp "\"display-column\": 20" } */
> -/* { dg-regexp "\"byte-column\": 20" } */
> -
> -/* { dg-regexp "\"locations\": \[\[\{\}, \]*\]" } */
> -/* { dg-regexp "\"children\": \[\[\]\[\]\]" } */
> -/* { dg-regexp "\[\[\{\}, \]*\]" } */
> +  { dg-regexp {\[} }
> +    { dg-regexp {\{} }
> +     { dg-regexp {"kind": "error"} }
> +     { dg-regexp {, "message": "'struct s' has no member named
> 'colour'; did you mean 'color'\?"} }
> +     { dg-regexp {, "children": \[\]} }
> +     { dg-regexp {, "column-origin": 1} }
> +     { dg-regexp {, "locations": } }
> +       { dg-regexp {\[} }
> +         { dg-regexp {\{} }
> +           { dg-regexp {"caret": } }
> +             { dg-regexp {\{} }
> +               { dg-regexp {"file": "[^\n\r"]*diagnostic-format-
> json-5.c"} }
> +               { dg-regexp {, "line": 8} }
> +               { dg-regexp {, "display-column": 15} }
> +               { dg-regexp {, "byte-column": 15} }
> +               { dg-regexp {, "column": 15} }
> +             { dg-regexp {\}} }
> +           { dg-regexp {, "finish": } }
> +             { dg-regexp {\{} }
> +               { dg-regexp {"file": "[^\n\r"]*diagnostic-format-
> json-5.c"} }
> +               { dg-regexp {, "line": 8} }
> +               { dg-regexp {, "display-column": 20} }
> +               { dg-regexp {, "byte-column": 20} }
> +               { dg-regexp {, "column": 20} }
> +             { dg-regexp {\}} }
> +           { dg-regexp {\}} }
> +         { dg-regexp {\]} }
> +       { dg-regexp {, "fixits": } }
> +       { dg-regexp {\[} }
> +         { dg-regexp {\{} }
> +           { dg-regexp {"start": } }
> +             { dg-regexp {\{} }
> +               { dg-regexp {"file": "[^\n\r"]*diagnostic-format-
> json-5.c"} }
> +               { dg-regexp {, "line": 8} }
> +               { dg-regexp {, "display-column": 15} }
> +               { dg-regexp {, "byte-column": 15} }
> +               { dg-regexp {, "column": 15} }
> +             { dg-regexp {\}} }
> +           { dg-regexp {, "next": } }
> +             { dg-regexp {\{} }
> +               { dg-regexp {"file": "[^\n\r"]*diagnostic-format-
> json-5.c"} }
> +               { dg-regexp {, "line": 8} }
> +               { dg-regexp {, "display-column": 21} }
> +               { dg-regexp {, "byte-column": 21} }
> +               { dg-regexp {, "column": 21} }
> +             { dg-regexp {\}} }
> +           { dg-regexp {, "string": "color"} }
> +         { dg-regexp {\}} }
> +       { dg-regexp {\]} }
> +     { dg-regexp {, "escape-source": false\}} }
> +   { dg-regexp {\]} }  */
> diff --git a/gcc/testsuite/c-c++-common/diagnostic-format-json-
> stderr-1.c b/gcc/testsuite/c-c++-common/diagnostic-format-json-
> stderr-1.c
> index 02f780bce10..bcfa92110f5 100644
> --- a/gcc/testsuite/c-c++-common/diagnostic-format-json-stderr-1.c
> +++ b/gcc/testsuite/c-c++-common/diagnostic-format-json-stderr-1.c
> @@ -6,8 +6,7 @@
>  #error message
>  
>  /* Use dg-regexp to consume the JSON output starting with
> -   the innermost values, and working outwards.
> -   We can't rely on any ordering of the keys.  */
> +   the innermost values, and working outwards.  */
>  
>  /* { dg-regexp "\"kind\": \"error\"" } */
>  /* { dg-regexp "\"column-origin\": 1" } */