Add comparison

1 files changed, 154 insertions, 0 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)