diff options
Diffstat (limited to 'gcc/json.cc')
| -rw-r--r-- | gcc/json.cc | 502 |
1 files changed, 498 insertions, 4 deletions
diff --git a/gcc/json.cc b/gcc/json.cc index 4cf962f..7153f08 100644 --- a/gcc/json.cc +++ b/gcc/json.cc @@ -24,7 +24,6 @@ along with GCC; see the file COPYING3. If not see #include "json.h" #include "pretty-print.h" #include "math.h" -#include "make-unique.h" #include "selftest.h" using namespace json; @@ -75,6 +74,52 @@ print_escaped_json_string (pretty_printer *pp, pp_character (pp, '"'); } +/* class pointer::token. */ + +pointer::token::token () +{ + m_parent = nullptr; + m_data.u_member = nullptr; + m_kind = kind::root_value; +} + +pointer::token::token (json::object &parent, const char *member) +{ + m_parent = &parent; + m_data.u_member = xstrdup (member); // ideally we'd share + m_kind = kind::object_member; +} + +pointer::token::token (json::array &parent, size_t index) +{ + m_parent = &parent; + m_data.u_index = index; + m_kind = kind::array_index; +} + +pointer::token::~token () +{ + if (m_kind == kind::object_member) + { + gcc_assert (m_data.u_member); + free (m_data.u_member); + } +} + +pointer::token & +pointer::token::operator= (pointer::token &&other) +{ + m_parent = other.m_parent; + m_data = other.m_data; + m_kind = other.m_kind; + + other.m_parent = nullptr; + other.m_data.u_member = nullptr; + other.m_kind = kind::root_value; + + return *this; +} + /* class json::value. */ /* Dump this json::value tree to OUTF. @@ -101,6 +146,94 @@ value::dump () const fprintf (stderr, "\n"); } +/* A deterministic total ordering for comparing json values, so that we + can e.g. put them in std::map. + + This is intended to follow the condition for equality described in + the JSON Schema standard (§4.3, “Instance equality”), as referenced + by SARIF v2.1.0 (§3.7.3 "Array properties with unique values"), but has + the following limitations: + - numbers are supposed to be checked for "the same mathematical value", + but in this implementation int vs float numbers won't compare as equal, + and float number comparison is bitwise + - strings are supposed to be "the same codepoint-for-codepoint", but + this implementation doesn't take into account canonicalization issues. */ + +int +value::compare (const value &val_a, const value &val_b) +{ + enum kind kind_a = val_a.get_kind (); + enum kind kind_b = val_b.get_kind (); + if (kind_a != kind_b) + return (int)kind_a - (int)kind_b; + + switch (kind_a) + { + default: + gcc_unreachable (); + + case JSON_OBJECT: + { + const object &obj_a = (const object &)val_a; + const object &obj_b = (const object &)val_b; + return object::compare (obj_a, obj_b); + } + break; + + case JSON_ARRAY: + { + const array &arr_a = (const array &)val_a; + const array &arr_b = (const array &)val_b; + if (int cmp_size = (int)arr_a.size () - (int)arr_b.size ()) + return cmp_size; + for (size_t idx = 0; idx < arr_a.size (); ++idx) + if (int cmp_element = compare (*arr_a[idx], *arr_b[idx])) + return cmp_element; + return 0; + } + break; + + case JSON_INTEGER: + { + const integer_number &int_a = (const integer_number &)val_a; + const integer_number &int_b = (const integer_number &)val_b; + return int_a.get () - int_b.get (); + } + break; + + case JSON_FLOAT: + { + const float_number &float_a = (const float_number &)val_a; + const float_number &float_b = (const float_number &)val_b; + union u + { + double u_double; + char u_buf[sizeof(double)]; + }; + union u u_a, u_b; + u_a.u_double = float_a.get (); + u_b.u_double = float_b.get (); + return memcmp (&u_a, &u_b, sizeof(double)); + } + break; + + case JSON_STRING: + { + const string &str_a = (const string &)val_a; + const string &str_b = (const string &)val_b; + return strcmp (str_a.get_string (), str_b.get_string ()); + } + break; + + case JSON_TRUE: + case JSON_FALSE: + case JSON_NULL: + /* All instances of literals compare equal to instances + of the same literal. */ + return 0; + } +} + /* class json::object, a subclass of json::value, representing an ordered collection of key/value pairs. */ @@ -156,6 +289,30 @@ object::print (pretty_printer *pp, bool formatted) const pp_character (pp, '}'); } +std::unique_ptr<value> +object::clone () const +{ + return clone_as_object (); +} + +std::unique_ptr<object> +object::clone_as_object () const +{ + auto result = std::make_unique<object> (); + + /* Iterate in the order that the keys were inserted. */ + unsigned i; + const char *key; + FOR_EACH_VEC_ELT (m_keys, i, key) + { + map_t &mut_map = const_cast<map_t &> (m_map); + value *value = *mut_map.get (key); + result->set (key, value->clone ()); + } + + return result; +} + /* Set the json::value * for KEY, taking ownership of V (and taking a copy of KEY if necessary). */ @@ -181,6 +338,8 @@ object::set (const char *key, value *v) m_map.put (owned_key, v); m_keys.safe_push (owned_key); } + + v->m_pointer_token = pointer::token (*this, key); } /* Get the json::value * for KEY. @@ -235,6 +394,36 @@ object::set_bool (const char *key, bool v) set (key, new json::literal (v)); } +/* Subroutine of json::compare for comparing a pairs of objects. */ + +int +object::compare (const json::object &obj_a, const json::object &obj_b) +{ + if (int cmp_size = (int)obj_a.m_keys.length () - (int)obj_b.m_keys.length ()) + return cmp_size; + + for (auto iter_a : obj_a.m_map) + { + const char *key = iter_a.first; + const value *value_a = iter_a.second; + gcc_assert (value_a); + + const value *value_b = obj_b.get (key); + if (!value_b) + /* Key is in OBJ_A but not in OBJ_B. */ + return 1; + /* If key is OBJ_B but not in OBJ_A, then the + count of keys will have been different, or + OBJ_A would have had a key not in OBJ_B. */ + if (int cmp_value = value::compare (*value_a, *value_b)) + /* Values for key are non-equal. */ + return cmp_value; + } + + /* Objects are equal. */ + return 0; +} + /* class json::array, a subclass of json::value, representing an ordered collection of values. */ @@ -278,12 +467,24 @@ array::print (pretty_printer *pp, bool formatted) const pp_character (pp, ']'); } +std::unique_ptr<value> +array::clone () const +{ + auto result = std::make_unique<array> (); + unsigned i; + value *v; + FOR_EACH_VEC_ELT (m_elements, i, v) + result->append (v->clone ()); + return result; +} + /* Append non-NULL value V to a json::array, taking ownership of V. */ void array::append (value *v) { gcc_assert (v); + v->m_pointer_token = pointer::token (*this, m_elements.length ()); m_elements.safe_push (v); } @@ -307,6 +508,12 @@ float_number::print (pretty_printer *pp, pp_string (pp, tmp); } +std::unique_ptr<value> +float_number::clone () const +{ + return std::make_unique<float_number> (m_value); +} + /* class json::integer_number, a subclass of json::value, wrapping a long. */ /* Implementation of json::value::print for json::integer_number. */ @@ -320,6 +527,11 @@ integer_number::print (pretty_printer *pp, pp_string (pp, tmp); } +std::unique_ptr<value> +integer_number::clone () const +{ + return std::make_unique<integer_number> (m_value); +} /* class json::string, a subclass of json::value. */ @@ -335,9 +547,10 @@ string::string (const char *utf8) string::string (const char *utf8, size_t len) { gcc_assert (utf8); - m_utf8 = XNEWVEC (char, len); + m_utf8 = XNEWVEC (char, len + 1); m_len = len; memcpy (m_utf8, utf8, len); + m_utf8[len] = '\0'; } /* Implementation of json::value::print for json::string. */ @@ -349,6 +562,12 @@ string::print (pretty_printer *pp, print_escaped_json_string (pp, m_utf8, m_len); } +std::unique_ptr<value> +string::clone () const +{ + return std::make_unique<string> (m_utf8, m_len); +} + /* class json::literal, a subclass of json::value. */ /* Implementation of json::value::print for json::literal. */ @@ -373,6 +592,12 @@ literal::print (pretty_printer *pp, } } +std::unique_ptr<value> +literal::clone () const +{ + return std::make_unique<literal> (m_kind); +} + #if CHECKING_P @@ -510,7 +735,7 @@ test_formatting () { object obj; object *child = new object; - std::unique_ptr<object> grandchild = ::make_unique<object> (); + std::unique_ptr<object> grandchild = std::make_unique<object> (); obj.set_string ("str", "bar"); obj.set ("child", child); @@ -518,7 +743,7 @@ test_formatting () array *arr = new array; for (int i = 0; i < 3; i++) - arr->append (::make_unique<integer_number> (i)); + arr->append (std::make_unique<integer_number> (i)); grandchild->set ("arr", arr); grandchild->set_integer ("int", 1066); @@ -541,6 +766,272 @@ test_formatting () " \"int\": 1776}, \"int\": 42}")); } +/* Helper function for reporting failure of JSON comparisons. */ + +static void +fail_comparison (const location &loc, + const char *desc, + const value &val_a, const value &val_b, + const char *desc_expected_value, + int actual_value) +{ + fprintf (stderr, "val_a: "); + val_a.dump (); + + fprintf (stderr, "val_b: "); + val_b.dump (); + + selftest::fail_formatted (loc, + "%s: failed JSON comparison:" + " expected: %s got: %i\n", + desc, + desc_expected_value, actual_value); +} + +/* Implementation of ASSERT_JSON_EQ. */ + +static void +assert_json_equal (const location &loc, + const char *desc, + const value &val_a, const value &val_b) +{ + /* Comparison should return zero, both ways, indicating no differences. */ + const int a_vs_b = value::compare (val_a, val_b); + if (a_vs_b != 0) + fail_comparison (loc, desc, val_a, val_b, "zero", a_vs_b); + + const int b_vs_a = value::compare (val_b, val_a); + if (b_vs_a != 0) + fail_comparison (loc, desc, val_b, val_a, "zero", b_vs_a); +} + +/* Verify that json::value::compare returns 0 ("no differences") on + VAL1 and VAL2, in both orders. */ + +#define ASSERT_JSON_EQ(VAL1, VAL2) \ + SELFTEST_BEGIN_STMT \ + assert_json_equal ((SELFTEST_LOCATION), \ + "ASSERT_JSON_EQ", \ + (VAL1), (VAL2)); \ + SELFTEST_END_STMT + +/* Implementation of ASSERT_JSON_NE. */ + +static void +assert_json_non_equal (const location &loc, + const char *desc, + const value &val_a, const value &val_b) +{ + /* Comparison should be non-zero, indicating differences. */ + const int a_vs_b = value::compare (val_a, val_b); + if (a_vs_b == 0) + fail_comparison (loc, desc, val_a, val_b, "non-zero", a_vs_b); + + const int b_vs_a = value::compare (val_b, val_a); + ASSERT_NE_AT (loc, b_vs_a, 0); + if (b_vs_a == 0) + fail_comparison (loc, desc, val_b, val_a, "non-zero", b_vs_a); + + /* Swapping the args should swap the sign of the result + (but isn't necessarily the negation). */ + if ( (a_vs_b > 0) == (b_vs_a > 0) ) + fail_comparison (loc, desc, val_b, val_a, "opposite signs", 1); +} + +/* Verify that json::value::compare returns non-zero ("different") on + VAL1 and VAL2, in both orders, and that they have opposite + sign. */ + +#define ASSERT_JSON_NE(VAL1, VAL2) \ + SELFTEST_BEGIN_STMT \ + assert_json_non_equal ((SELFTEST_LOCATION), \ + "ASSERT_JSON_NE", \ + (VAL1), (VAL2)); \ + SELFTEST_END_STMT + +/* Verify that json::value::compare works as expected. */ + +static void +test_comparisons () +{ + /* Literals. */ + + literal null_lit (JSON_NULL); + ASSERT_JSON_EQ (null_lit, null_lit); + + literal other_null_lit (JSON_NULL); + ASSERT_JSON_EQ (null_lit, other_null_lit); + + literal true_lit (JSON_TRUE); + ASSERT_JSON_EQ (true_lit, true_lit); + ASSERT_JSON_NE (true_lit, null_lit); + + literal false_lit (JSON_FALSE); + ASSERT_JSON_EQ (false_lit, false_lit); + ASSERT_JSON_NE (false_lit, true_lit); + ASSERT_JSON_NE (false_lit, null_lit); + + /* Strings. */ + string str_foo_1 ("foo"); + ASSERT_JSON_EQ (str_foo_1, str_foo_1); + + string str_foo_2 ("foo"); + ASSERT_JSON_EQ (str_foo_1, str_foo_2); + + string str_bar ("bar"); + ASSERT_JSON_NE (str_bar, str_foo_1); + + /* Numbers. */ + integer_number i_42 (42); + ASSERT_JSON_EQ (i_42, i_42); + integer_number i_42_2 (42); + ASSERT_JSON_EQ (i_42, i_42_2); + integer_number i_43 (43); + ASSERT_JSON_NE (i_42, i_43); + + float_number f_zero (0.0); + ASSERT_JSON_EQ (f_zero, f_zero); + float_number f_zero_2 (0.0); + ASSERT_JSON_EQ (f_zero, f_zero_2); + float_number f_one (1.0); + ASSERT_JSON_NE (f_zero, f_one); + /* We don't yet test the more awkward cases e.g. NaN. */ + + /* Objects. */ + + // Empty object + // Self comparison should be 0 + object empty_obj_a; + ASSERT_JSON_EQ (empty_obj_a, empty_obj_a); + + // Instances of empty objects should compare equal to each other + object empty_obj_b; + ASSERT_JSON_EQ (empty_obj_a, empty_obj_b); + + // Object with one field: + object obj_1; + obj_1.set_string ("foo", "bar"); + // Self comparison should be 0 + ASSERT_JSON_EQ (obj_1, obj_1); + + // but should be different to an empty object: + ASSERT_JSON_NE (obj_1, empty_obj_a); + + // Another with one field, with same key/value: + object obj_2; + obj_2.set_string ("foo", "bar"); + ASSERT_JSON_EQ (obj_1, obj_2); + + // Same key, different value: + object obj_3; + obj_3.set_string ("foo", "baz"); + ASSERT_JSON_NE (obj_1, obj_3); + + // Adding an extra property: + obj_2.set_integer ("year", 1066); + ASSERT_JSON_NE (obj_1, obj_2); + + /* Different insertion order, but same k-v pairs should be equal, + despite having different serialization. */ + object obj_4; + obj_4.set_integer ("year", 1066); + obj_4.set_string ("foo", "bar"); + ASSERT_JSON_EQ (obj_2, obj_4); + ASSERT_PRINT_EQ (obj_2, false, "{\"foo\": \"bar\", \"year\": 1066}"); + ASSERT_PRINT_EQ (obj_4, false, "{\"year\": 1066, \"foo\": \"bar\"}"); + + /* Arrays. */ + + // Empty array + array empty_arr_a; + // Self comparison should be 0 + ASSERT_JSON_EQ (empty_arr_a, empty_arr_a); + + // Objects and arrays are different + ASSERT_JSON_NE (empty_obj_a, empty_arr_a); + + // Instances of empty arrays should compare equal to each other + array empty_arr_b; + ASSERT_JSON_EQ (empty_arr_a, empty_arr_b); + + // Array with one element: + array arr_1; + arr_1.append (std::make_unique<string> ("foo")); + // Self comparison should be 0 + ASSERT_JSON_EQ (arr_1, arr_1); + + // but should be different to an empty array: + ASSERT_JSON_NE (arr_1, empty_arr_a); + + // Another with one element: + array arr_2; + arr_2.append (std::make_unique<string> ("foo")); + ASSERT_JSON_EQ (arr_1, arr_2); + + // Adding an extra element: + arr_2.append (std::make_unique<string> ("bar")); + ASSERT_JSON_NE (arr_1, arr_2); +} + +/* Ensure that json::string's get_string is usable as a C-style string. */ + +static void +test_strcmp () +{ + string str ("foobar", 3); + ASSERT_EQ (strcmp (str.get_string (), "foo"), 0); +} + +static void +test_cloning () +{ + // Objects + { + object obj; + obj.set_string ("foo", "bar"); + + auto obj_clone = obj.clone (); + ASSERT_JSON_EQ (obj, *obj_clone); + } + + // Arrays + { + array arr; + arr.append (std::make_unique<string> ("foo")); + + auto arr_clone = arr.clone (); + ASSERT_JSON_EQ (arr, *arr_clone); + } + + // float_number + { + float_number f_one (1.0); + auto f_clone = f_one.clone (); + ASSERT_JSON_EQ (f_one, *f_clone); + } + + // integer_number + { + integer_number num (42); + auto num_clone = num.clone (); + ASSERT_JSON_EQ (num, *num_clone); + } + + // string + { + string str ("foo"); + auto str_clone = str.clone (); + ASSERT_JSON_EQ (str, *str_clone); + } + + // literal + { + literal lit (JSON_TRUE); + auto lit_clone = lit.clone (); + ASSERT_JSON_EQ (lit, *lit_clone); + } +} + /* Run all of the selftests within this file. */ void @@ -554,6 +1045,9 @@ json_cc_tests () test_writing_strings (); test_writing_literals (); test_formatting (); + test_comparisons (); + test_strcmp (); + test_cloning (); } } // namespace selftest |