Add comparison

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<uint64_t> (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<uint64_t> (v.signed_number));
+            r = unsigned_number < u ? -1 : (unsigned_number > u ? 1 : 0);
+          }
+        }
+        else
+          r = (static_cast<uint8_t> (type) < static_cast<uint8_t> (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<json_value>::
   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<json_value>;
+
+    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<json_value> ().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<json_value> ());
-    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<name> (l, r);
+    return l.as<json_value> ().compare (r.as<json_value> ());
   }
 
   const json_value value_traits<json_value>::empty_instance;
@@ -1757,13 +1773,13 @@ namespace build2
     &default_dtor<json_value>,
     &default_copy_ctor<json_value>,
     &default_copy_assign<json_value>,
-    &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<cmdline>
+    &json_compare,
+    &default_empty<json_value>
   };
 
   // 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