From 7f1e15f743357e037d7c4f6f6000863c26f3dfc3 Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Fri, 24 Mar 2023 11:38:14 -0400 Subject: [PATCH] json: preserve key-insertion order [PR109163] 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. 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 --- 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 ++++++++++++--------- .../c-c++-common/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 01879c9..741e97b 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 ((*it).first); - value *value = (*it).second; + map_t &mut_map = const_cast (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 aa52ba2..057119d 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 > map_t; map_t m_map; + + /* Keep track of order in which keys were inserted. */ + auto_vec 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 af57eb6..6bab30e 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 edb802e..3c12103 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 bb7b8dc..11d7462 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 8ac9072..cec1cf9 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 8d2eb0c..86f8c5f 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 02f780b..bcfa921 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" } */ -- 2.7.4