diff options
Diffstat (limited to 'gcc/json.cc')
| -rw-r--r-- | gcc/json.cc | 375 |
1 files changed, 375 insertions, 0 deletions
diff --git a/gcc/json.cc b/gcc/json.cc index e66a7ae..f3f3645 100644 --- a/gcc/json.cc +++ b/gcc/json.cc @@ -74,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. @@ -100,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. */ @@ -180,6 +314,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. @@ -234,6 +370,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. */ @@ -283,6 +449,7 @@ void array::append (value *v) { gcc_assert (v); + v->m_pointer_token = pointer::token (*this, m_elements.length ()); m_elements.safe_push (v); } @@ -540,6 +707,213 @@ 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); +} + /* Run all of the selftests within this file. */ void @@ -553,6 +927,7 @@ json_cc_tests () test_writing_strings (); test_writing_literals (); test_formatting (); + test_comparisons (); } } // namespace selftest |