From 7d5c863e01b4a70d5ef3614b91694cf080a420c9 Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Mon, 22 Jan 2024 12:02:54 +0200 Subject: Add comparison --- libbuild2/json.cxx | 154 +++++++++++++++++++++++++++++++++++++++++++++++++ libbuild2/json.hxx | 24 +++++++- libbuild2/variable.cxx | 66 +++++++++++++-------- libbuild2/variable.hxx | 4 +- 4 files changed, 219 insertions(+), 29 deletions(-) diff --git a/libbuild2/json.cxx b/libbuild2/json.cxx index 0fee8af..dfa1a07 100644 --- a/libbuild2/json.cxx +++ b/libbuild2/json.cxx @@ -12,6 +12,160 @@ using namespace butl::json; namespace build2 { + int json_value:: + compare (const json_value& v, bool ignore_name) const + { + int r (0); + + if (!ignore_name) + r = name < v.name ? -1 : (name > v.name ? 1 : 0); + + if (r == 0) + { + if (type != v.type) + { + // Handle the special signed/unsigned number case here. + // + if (type == json_type::signed_number && + v.type == json_type::unsigned_number) + { + if (signed_number < 0) + r = -1; + else + { + uint64_t u (static_cast (signed_number)); + r = u < v.unsigned_number ? -1 : (u > v.unsigned_number ? 1 : 0); + } + } + else if (type == json_type::unsigned_number && + v.type == json_type::signed_number) + { + if (v.signed_number < 0) + r = 1; + else + { + uint64_t u (static_cast (v.signed_number)); + r = unsigned_number < u ? -1 : (unsigned_number > u ? 1 : 0); + } + } + else + r = (static_cast (type) < static_cast (v.type) + ? -1 + : 1); + } + } + + if (r == 0) + { + switch (type) + { + case json_type::null: + { + r = 0; + break; + } + case json_type::boolean: + { + r = boolean == v.boolean ? 0 : boolean ? 1 : -1; + break; + } + case json_type::signed_number: + { + r = (signed_number < v.signed_number + ? -1 + : (signed_number > v.signed_number ? 1 : 0)); + break; + } + case json_type::unsigned_number: + { + r = (unsigned_number < v.unsigned_number + ? -1 + : (unsigned_number > v.unsigned_number ? 1 : 0)); + break; + } + case json_type::string: + { + r = string.compare (v.string); + break; + } + case json_type::array: + { + auto i (container.begin ()), ie (container.end ()); + auto j (v.container.begin ()), je (v.container.end ()); + + for (; i != ie && j != je; ++i, ++j) + { + if ((r = i->compare (*j)) != 0) + break; + } + + if (r == 0) + r = i == ie ? -1 : (j == je ? 1 : 0); // More elements than other? + + break; + } + case json_type::object: + { + // We don't expect there to be a large number of members so it makes + // sense to iterate in the lexicographical order without making any + // copies. + // + auto next = [] (container_type::const_iterator p, // == e for first + container_type::const_iterator b, + container_type::const_iterator e) + { + // We need to find an element with the "smallest" name that is + // greater than the previous entry. + // + auto n (e); + + for (auto i (b); i != e; ++i) + { + if (p == e || *i->name > *p->name) + { + int r; + if (n == e || (r = n->name->compare (*i->name)) > 0) + n = i; + else + assert (r != 0); // No duplicates. + } + } + + return n; + }; + + auto ib (container.begin ()), ie (container.end ()), i (ie); + auto jb (v.container.begin ()), je (v.container.end ()), j (je); + + while ((i = next (i, ib, ie)) != ie && + (j = next (j, jb, je)) != je) + { + // Determine if both have this name and if not, which name comes + // first. + // + int n (i->name->compare (*j->name)); + + r = (n < 0 // If i's first, then i is greater. + ? -1 + : (n > 0 // If j's first, then j is greater. + ? 1 + : i->compare (*j, true))); // Both have name, compare value. + + if (r != 0) + break; + } + + if (r == 0) + r = i == ie ? -1 : (j == je ? 1 : 0); // More members than other? + + break; + } + } + } + + return r; + } + #ifndef BUILD2_BOOTSTRAP json_value:: json_value (parser& p) diff --git a/libbuild2/json.hxx b/libbuild2/json.hxx index 816b55c..6fc633c 100644 --- a/libbuild2/json.hxx +++ b/libbuild2/json.hxx @@ -26,9 +26,14 @@ namespace build2 // string and value. The latter allows us to use the JSON value itself as an // element of a container. // - enum class json_type + // Note also that we don't assume that object members are in a sorted order + // (but do assume there are no duplicates). However, we could add an + // argument to signal that this is the case to speed up some functions, for + // example, compare(). + // + enum class json_type: uint8_t { - null, + null, // Note: keep first for comparison. boolean, signed_number, unsigned_number, @@ -222,6 +227,21 @@ namespace build2 case json_type::object: container.~container_type (); break; } } + + // Note that values of different types are never equal, except for + // signed/unsigned numbers. Null is equal to null and is less than any + // other value. Arrays are compared lexicographically. Object members are + // considered in the lexicographically-compared name-ascending order (see + // RFC8785). An absent member is less than a present member (even if it's + // null). + // + // Note that while it doesn't make much sense to compare members to + // non-members, we allow it with a non-member always being less than a + // member (even if null), unless ignore_name is true, in which case member + // names are ignored. + // + int + compare (const json_value&, bool ignore_name = false) const; }; // Throws invalid_json_output. diff --git a/libbuild2/variable.cxx b/libbuild2/variable.cxx index 62da025..c83d55e 100644 --- a/libbuild2/variable.cxx +++ b/libbuild2/variable.cxx @@ -1646,6 +1646,9 @@ namespace build2 new (&v.data_) json_value (move (x)); } + // @@ TODO: ? + // + /* void value_traits:: append (value& v, json_value&& x) { @@ -1681,22 +1684,35 @@ namespace build2 else new (&v.data_) json_value (move (x)); } + */ - void - json_value_assign (value& v, names&& ns, const variable*) + static void + json_assign (value& v, names&& ns, const variable* var) { - if (!v) + using traits = value_traits; + + try { - new (&v.data_) json_value (); - v.null = false; + traits::assign (v, traits::convert (move (ns))); } + catch (const invalid_argument& e) + { + // Note: ns is not guaranteed to be valid. + // + diag_record dr (fail); + dr << "invalid json value"; - v.as ().assign (make_move_iterator (ns.begin ()), - make_move_iterator (ns.end ())); + if (var != nullptr) + dr << " in variable " << var->name; + + dr << ": " << e; + } } - void - json_value_append (value& v, names&& ns, const variable*) + // @@ TODO: ? + /* + static void + json_append (value& v, names&& ns, const variable*) { if (!v) { @@ -1710,8 +1726,8 @@ namespace build2 make_move_iterator (ns.end ())); } - void - json_value_prepend (value& v, names&& ns, const variable*) + static void + json_prepend (value& v, names&& ns, const variable*) { if (!v) { @@ -1724,18 +1740,18 @@ namespace build2 make_move_iterator (ns.begin ()), make_move_iterator (ns.end ())); } + */ static names_view - json_value_reverse (const value& v, names&, bool) + json_reverse (const value&, names& storage, bool) { - const auto& x (v.as ()); - return names_view (x.data (), x.size ()); + return names_view (storage); // @@ TODO } static int - json_value_compare (const value& l, const value& r) + json_compare (const value& l, const value& r) { - return vector_compare (l, r); + return l.as ().compare (r.as ()); } const json_value value_traits::empty_instance; @@ -1757,13 +1773,13 @@ namespace build2 &default_dtor, &default_copy_ctor, &default_copy_assign, - &cmdline_assign, - &cmdline_append, - &cmdline_prepend, - &cmdline_reverse, + &json_assign, + nullptr, //&cmdline_append, @@ + nullptr, //&cmdline_prepend, @@ + &json_reverse, nullptr, // No cast (cast data_ directly). - &cmdline_compare, - &default_empty + &json_compare, + &default_empty }; // cmdline @@ -1820,7 +1836,7 @@ namespace build2 new (&v.data_) cmdline (move (x)); } - void + static void cmdline_assign (value& v, names&& ns, const variable*) { if (!v) @@ -1833,7 +1849,7 @@ namespace build2 make_move_iterator (ns.end ())); } - void + static void cmdline_append (value& v, names&& ns, const variable*) { if (!v) @@ -1848,7 +1864,7 @@ namespace build2 make_move_iterator (ns.end ())); } - void + static void cmdline_prepend (value& v, names&& ns, const variable*) { if (!v) diff --git a/libbuild2/variable.hxx b/libbuild2/variable.hxx index eddf1ac..fa9ea92 100644 --- a/libbuild2/variable.hxx +++ b/libbuild2/variable.hxx @@ -1190,8 +1190,8 @@ namespace build2 static json_value convert (names&&); static void assign (value&, json_value&&); - static void append (value&, json_value&&); - static void prepend (value&, json_value&&); + //static void append (value&, json_value&&); + //static void prepend (value&, json_value&&); static bool empty (const json_value&); // null or empty string|array|object static const json_value empty_instance; // null -- cgit v1.1