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

[Richard Biener <richard.guenther@gmail.com>]

> Am 24.03.2023 um 15:44 schrieb David Malcolm via Gcc-patches <gcc-patches@gcc.gnu.org>:
> 
> I'd like to ping the following patch for review:
>  https://gcc.gnu.org/pipermail/gcc-patches/2023-March/614165.html

Ok.

Richard 

> 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" } */
>