Test unordered object equality without std::unordered_map

basic_json<std::unordered_map> instantiates std::pair<const string,
basic_json> while basic_json is still incomplete. The standard does not
require std::unordered_map to support that, and libstdc++ 6 to 9 as well
as the EDG front ends of icpc and nvc++ reject it, which broke the build
of unit-comparison on those CI jobs.

The test now uses an object type derived from std::map (which, as the
default object type, works everywhere) whose comparator orders keys
ascending or descending as chosen at construction, and whose operator==
does not depend on the order of the entries - the property of
std::unordered_map the test is about.

Signed-off-by: Niels Lohmann <mail@nlohmann.me>

docs/mkdocs/docs/api/basic_json/to_msgpack.md

@@ -34,15 +34,6 @@ The exact mapping and its limitations are described on a [dedicated page](../../
 
 Strong guarantee: if an exception is thrown, there are no changes in the JSON value.
 
-## Exceptions
-
-- Throws [`out_of_range.412`](../../home/exceptions.md#jsonexceptionout_of_range412) if the length of a string, binary
-  value, array, or object exceeds 4294967295, the maximum MessagePack can store; example:
-  `"MessagePack length 4294967296 exceeds maximum of 4294967295"`
-- Throws [`out_of_range.415`](../../home/exceptions.md#jsonexceptionout_of_range415) if the subtype of a binary value
-  exceeds 255, the maximum of the MessagePack ext type; example:
-  `"subtype 70000 is too large for the MessagePack ext type (max 255)"`
-
 ## Complexity
 
 Linear in the size of the JSON value `j`.
@@ -74,4 +65,3 @@ Linear in the size of the JSON value `j`.
 ## Version history
 
 - Added in version 2.0.9.
-- Throws `out_of_range.412` and `out_of_range.415` since version 3.13.0.

docs/mkdocs/docs/features/binary_formats/messagepack.md

@@ -65,8 +65,6 @@ specification:
       - arrays with more than 4294967295 elements
       - objects with more than 4294967295 elements
 
-    Serializing such a value throws [`out_of_range.412`](../../home/exceptions.md#jsonexceptionout_of_range412).
-
 !!! info "NaN/infinity handling"
 
     `NaN`, `Infinity`, and `-Infinity` are serialized as a MessagePack float 32 (type 0xCA, 5 bytes total),

docs/mkdocs/docs/home/exceptions.md

@@ -932,25 +932,19 @@ A JSON Patch `add` operation cannot be applied because the target location's par
 
 ### json.exception.out_of_range.412
 
-BSON stores the length of documents, arrays, strings, and binary values in a signed 32-bit integer, and MessagePack
-stores the length of strings, binary values, arrays, and objects in at most an unsigned 32-bit integer. This exception
-is thrown when a value is too large to be described by such a length field.
+BSON stores the length of documents, arrays, strings, and binary values in a signed 32-bit integer. This exception is thrown when a value is too large to be described by such a length field.
 
-!!! failure "Example messages"
+!!! failure "Example message"
 
     ```
     BSON length 2147483661 exceeds maximum of 2147483647
     ```
-    ```
-    MessagePack length 4294967296 exceeds maximum of 4294967295
-    ```
 
 !!! note
 
-    This exception was added in version 3.13.0. Before that, the BSON length was silently truncated, and
+    This exception was added in version 3.13.0. Before that, the length was silently truncated, and
     [`to_bson`](../api/basic_json/to_bson.md) produced documents with negative length prefixes that
-    [`from_bson`](../api/basic_json/from_bson.md) rejected; [`to_msgpack`](../api/basic_json/to_msgpack.md) wrote such
-    a value without any length, producing output that could not be read back.
+    [`from_bson`](../api/basic_json/from_bson.md) rejected.
 
 ### json.exception.out_of_range.413
 

include/nlohmann/detail/output/binary_writer.hpp

@@ -466,23 +466,6 @@ class binary_writer
         }
     }
 
-    /*!
-    @brief check that @a length fits into the 32 bits that MessagePack stores
-           the length of a string, binary value, array, or object in
-    @return the length as an unsigned 32-bit integer
-    @throw out_of_range.412 if @a length exceeds the range of std::uint32_t
-    */
-    static std::uint32_t to_msgpack_length(const std::size_t length, const BasicJsonType& j)
-    {
-        if (JSON_HEDLEY_UNLIKELY(!value_in_range_of<std::uint32_t>(length)))
-        {
-            JSON_THROW(out_of_range::create(412, concat("MessagePack length ", std::to_string(length), " exceeds maximum of ", std::to_string((std::numeric_limits<std::uint32_t>::max)())), &j));
-        }
-
-        static_cast<void>(j);
-        return static_cast<std::uint32_t>(length);
-    }
-
     /*!
     @param[in] j  JSON value to serialize
     */
@@ -623,7 +606,7 @@ class binary_writer
             case value_t::string:
             {
                 // step 1: write control byte and the string length
-                const auto N = to_msgpack_length(j.m_data.m_value.string->size(), j);
+                const auto N = j.m_data.m_value.string->size();
                 if (N <= 31)
                 {
                     // fixstr
@@ -641,7 +624,7 @@ class binary_writer
                     oa.write_character(to_char_type(0xDA));
                     write_number(static_cast<std::uint16_t>(N));
                 }
-                else
+                else if (N <= (std::numeric_limits<std::uint32_t>::max)())
                 {
                     // str 32
                     oa.write_character(to_char_type(0xDB));
@@ -658,7 +641,7 @@ class binary_writer
             case value_t::array:
             {
                 // step 1: write control byte and the array size
-                const auto N = to_msgpack_length(j.m_data.m_value.array->size(), j);
+                const auto N = j.m_data.m_value.array->size();
                 if (N <= 15)
                 {
                     // fixarray
@@ -670,7 +653,7 @@ class binary_writer
                     oa.write_character(to_char_type(0xDC));
                     write_number(static_cast<std::uint16_t>(N));
                 }
-                else
+                else if (N <= (std::numeric_limits<std::uint32_t>::max)())
                 {
                     // array 32
                     oa.write_character(to_char_type(0xDD));
@@ -692,7 +675,7 @@ class binary_writer
                 const bool use_ext = j.m_data.m_value.binary->has_subtype();
 
                 // step 1: write control byte and the byte string length
-                const auto N = to_msgpack_length(j.m_data.m_value.binary->size(), j);
+                const auto N = j.m_data.m_value.binary->size();
                 if (N <= (std::numeric_limits<std::uint8_t>::max)())
                 {
                     std::uint8_t output_type{};
@@ -744,7 +727,7 @@ class binary_writer
                     oa.write_character(to_char_type(output_type));
                     write_number(static_cast<std::uint16_t>(N));
                 }
-                else
+                else if (N <= (std::numeric_limits<std::uint32_t>::max)())
                 {
                     const std::uint8_t output_type = use_ext
                                                      ? 0xC9 // ext 32
@@ -776,7 +759,7 @@ class binary_writer
             case value_t::object:
             {
                 // step 1: write control byte and the object size
-                const auto N = to_msgpack_length(j.m_data.m_value.object->size(), j);
+                const auto N = j.m_data.m_value.object->size();
                 if (N <= 15)
                 {
                     // fixmap
@@ -788,7 +771,7 @@ class binary_writer
                     oa.write_character(to_char_type(0xDE));
                     write_number(static_cast<std::uint16_t>(N));
                 }
-                else
+                else if (N <= (std::numeric_limits<std::uint32_t>::max)())
                 {
                     // map 32
                     oa.write_character(to_char_type(0xDF));

include/nlohmann/json.hpp

@@ -1492,13 +1492,28 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                         compare_keys(current.lhs_object_it->first, current.rhs_object_it->first,
                                      std::integral_constant<bool, Ordered> {});
 
-                    if (key_result != compare_result::equal)
-                    {
-                        return key_result;
-                    }
-
                     left = &(current.lhs_object_it->second);
                     right = &(current.rhs_object_it->second);
+
+                    if (key_result != compare_result::equal)
+                    {
+                        // An object type without a fixed order of its entries -
+                        // std::unordered_map, say - may enumerate two equal
+                        // objects differently, and its operator== does not care.
+                        // Equality then finds the entry by its key; an ordering,
+                        // or an object type that compares its entries in
+                        // sequence (ordered_map), is decided by the key itself.
+                        const auto* rhs_object = current.rhs_value->m_data.m_value.object;
+                        const auto found = (!Ordered && !detail::is_ordered_map<object_t>::value)
+                                           ? rhs_object->find(current.lhs_object_it->first)
+                                           : rhs_object->cend();
+                        if (found == rhs_object->cend())
+                        {
+                            return key_result;
+                        }
+                        right = &(found->second);
+                    }
+
                     ++current.lhs_object_it;
                     ++current.rhs_object_it;
                 }

single_include/nlohmann/json.hpp

@@ -19931,23 +19931,6 @@ class binary_writer
         }
     }
 
-    /*!
-    @brief check that @a length fits into the 32 bits that MessagePack stores
-           the length of a string, binary value, array, or object in
-    @return the length as an unsigned 32-bit integer
-    @throw out_of_range.412 if @a length exceeds the range of std::uint32_t
-    */
-    static std::uint32_t to_msgpack_length(const std::size_t length, const BasicJsonType& j)
-    {
-        if (JSON_HEDLEY_UNLIKELY(!value_in_range_of<std::uint32_t>(length)))
-        {
-            JSON_THROW(out_of_range::create(412, concat("MessagePack length ", std::to_string(length), " exceeds maximum of ", std::to_string((std::numeric_limits<std::uint32_t>::max)())), &j));
-        }
-
-        static_cast<void>(j);
-        return static_cast<std::uint32_t>(length);
-    }
-
     /*!
     @param[in] j  JSON value to serialize
     */
@@ -20088,7 +20071,7 @@ class binary_writer
             case value_t::string:
             {
                 // step 1: write control byte and the string length
-                const auto N = to_msgpack_length(j.m_data.m_value.string->size(), j);
+                const auto N = j.m_data.m_value.string->size();
                 if (N <= 31)
                 {
                     // fixstr
@@ -20106,7 +20089,7 @@ class binary_writer
                     oa.write_character(to_char_type(0xDA));
                     write_number(static_cast<std::uint16_t>(N));
                 }
-                else
+                else if (N <= (std::numeric_limits<std::uint32_t>::max)())
                 {
                     // str 32
                     oa.write_character(to_char_type(0xDB));
@@ -20123,7 +20106,7 @@ class binary_writer
             case value_t::array:
             {
                 // step 1: write control byte and the array size
-                const auto N = to_msgpack_length(j.m_data.m_value.array->size(), j);
+                const auto N = j.m_data.m_value.array->size();
                 if (N <= 15)
                 {
                     // fixarray
@@ -20135,7 +20118,7 @@ class binary_writer
                     oa.write_character(to_char_type(0xDC));
                     write_number(static_cast<std::uint16_t>(N));
                 }
-                else
+                else if (N <= (std::numeric_limits<std::uint32_t>::max)())
                 {
                     // array 32
                     oa.write_character(to_char_type(0xDD));
@@ -20157,7 +20140,7 @@ class binary_writer
                 const bool use_ext = j.m_data.m_value.binary->has_subtype();
 
                 // step 1: write control byte and the byte string length
-                const auto N = to_msgpack_length(j.m_data.m_value.binary->size(), j);
+                const auto N = j.m_data.m_value.binary->size();
                 if (N <= (std::numeric_limits<std::uint8_t>::max)())
                 {
                     std::uint8_t output_type{};
@@ -20209,7 +20192,7 @@ class binary_writer
                     oa.write_character(to_char_type(output_type));
                     write_number(static_cast<std::uint16_t>(N));
                 }
-                else
+                else if (N <= (std::numeric_limits<std::uint32_t>::max)())
                 {
                     const std::uint8_t output_type = use_ext
                                                      ? 0xC9 // ext 32
@@ -20241,7 +20224,7 @@ class binary_writer
             case value_t::object:
             {
                 // step 1: write control byte and the object size
-                const auto N = to_msgpack_length(j.m_data.m_value.object->size(), j);
+                const auto N = j.m_data.m_value.object->size();
                 if (N <= 15)
                 {
                     // fixmap
@@ -20253,7 +20236,7 @@ class binary_writer
                     oa.write_character(to_char_type(0xDE));
                     write_number(static_cast<std::uint16_t>(N));
                 }
-                else
+                else if (N <= (std::numeric_limits<std::uint32_t>::max)())
                 {
                     // map 32
                     oa.write_character(to_char_type(0xDF));
@@ -26467,13 +26450,28 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                         compare_keys(current.lhs_object_it->first, current.rhs_object_it->first,
                                      std::integral_constant<bool, Ordered> {});
 
-                    if (key_result != compare_result::equal)
-                    {
-                        return key_result;
-                    }
-
                     left = &(current.lhs_object_it->second);
                     right = &(current.rhs_object_it->second);
+
+                    if (key_result != compare_result::equal)
+                    {
+                        // An object type without a fixed order of its entries -
+                        // std::unordered_map, say - may enumerate two equal
+                        // objects differently, and its operator== does not care.
+                        // Equality then finds the entry by its key; an ordering,
+                        // or an object type that compares its entries in
+                        // sequence (ordered_map), is decided by the key itself.
+                        const auto* rhs_object = current.rhs_value->m_data.m_value.object;
+                        const auto found = (!Ordered && !detail::is_ordered_map<object_t>::value)
+                                           ? rhs_object->find(current.lhs_object_it->first)
+                                           : rhs_object->cend();
+                        if (found == rhs_object->cend())
+                        {
+                            return key_result;
+                        }
+                        right = &(found->second);
+                    }
+
                     ++current.lhs_object_it;
                     ++current.rhs_object_it;
                 }

tests/src/unit-comparison.cpp

@@ -16,6 +16,9 @@
 #include "doctest_compatibility.h"
 
 #include <cstdint>
+#include <map>
+#include <string>
+#include <vector>
 
 #define JSON_TESTS_PRIVATE
 #include <nlohmann/json.hpp>
@@ -735,3 +738,132 @@ TEST_CASE("regression #3868 - heterogeneous comparisons compile under C++20 (P24
     }
 }
 #endif
+
+namespace
+{
+// orders keys ascending or descending, as chosen when a map is created
+template<class Key>
+class directed_less
+{
+  public:
+    directed_less() = default;
+
+    explicit directed_less(const bool descending) noexcept
+        : m_descending(descending)
+    {}
+
+    bool operator()(const Key& lhs, const Key& rhs) const
+    {
+        return m_descending ? rhs < lhs : lhs < rhs;
+    }
+
+  private:
+    bool m_descending = false;
+};
+
+// An object type that, like std::unordered_map, enumerates its entries in no
+// fixed order - ascending or descending by key, depending on how the map was
+// created - and whose operator== does not depend on that order.
+// std::unordered_map itself cannot be used here: the standard does not
+// require it to accept an incomplete mapped type such as basic_json, and
+// libstdc++ 6 to 9 as well as the EDG front ends of icpc and nvc++ reject
+// basic_json<std::unordered_map>. std::map, the default object type, works
+// with all supported compilers.
+template<class Key, class Value, class /*Compare*/, class Allocator>
+struct unordered_object_t : std::map<Key, Value, directed_less<Key>, Allocator>
+{
+    using base_type = std::map<Key, Value, directed_less<Key>, Allocator>;
+    using base_type::base_type;
+
+    friend bool operator==(const unordered_object_t& lhs, const unordered_object_t& rhs)
+    {
+        if (lhs.size() != rhs.size())
+        {
+            return false;
+        }
+        for (const auto& entry : lhs)
+        {
+            const auto it = rhs.find(entry.first);
+            if (it == rhs.end() || !(it->second == entry.second))
+            {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    friend bool operator!=(const unordered_object_t& lhs, const unordered_object_t& rhs)
+    {
+        return !(lhs == rhs);
+    }
+};
+using unordered_json = nlohmann::basic_json<unordered_object_t>;
+
+// the entries "0" to "9", enumerated in ascending or in descending order
+unordered_json make_unordered_object(const bool descending)
+{
+    unordered_json j = unordered_json::object_t(directed_less<std::string>(descending));
+    for (int i = 0; i < 10; ++i)
+    {
+        j[std::to_string(i)] = i;
+    }
+    return j;
+}
+
+template<typename Json>
+Json nest(Json j, const std::size_t depth)
+{
+    for (std::size_t i = 0; i < depth; ++i)
+    {
+        Json outer = Json::object();
+        outer["x"] = std::move(j);
+        j = std::move(outer);
+    }
+    return j;
+}
+} // namespace
+
+TEST_CASE("equality of objects whose entries have no fixed order")
+{
+    // Values nested deeper than a bound are compared without the call stack,
+    // entry by entry. That must agree with the object type's own operator==,
+    // which for unordered_object_t (as for std::unordered_map) does not
+    // depend on the order of the entries, and for ordered_map does.
+    REQUIRE(make_unordered_object(true).begin().key() == "9");
+    REQUIRE(make_unordered_object(false).begin().key() == "0");
+
+    for (const std::size_t depth : std::vector<std::size_t> {0, 200})
+    {
+        CAPTURE(depth);
+
+        const unordered_json descending = nest(make_unordered_object(true), depth);
+        const unordered_json ascending = nest(make_unordered_object(false), depth);
+        CHECK(descending == ascending);
+        CHECK_FALSE(descending != ascending);
+
+        // a copy is equal to its original
+        const unordered_json copy = descending; // NOLINT(performance-unnecessary-copy-initialization)
+        CHECK(copy == descending);
+
+        // a different value, a different key, or another entry still count
+        unordered_json other_value = make_unordered_object(true);
+        other_value["5"] = 42;
+        CHECK_FALSE(nest(other_value, depth) == ascending);
+
+        unordered_json other_key = make_unordered_object(true);
+        other_key.erase("5");
+        other_key["50"] = 5;
+        CHECK_FALSE(nest(other_key, depth) == ascending);
+
+        unordered_json more_entries = make_unordered_object(true);
+        more_entries["10"] = 10;
+        CHECK_FALSE(nest(more_entries, depth) == ascending);
+        CHECK_FALSE(ascending == nest(more_entries, depth));
+
+        // ordered_json compares its entries in sequence
+        const nlohmann::ordered_json ab = nest(nlohmann::ordered_json({{"a", 1}, {"b", 2}}), depth);
+        const nlohmann::ordered_json ba = nest(nlohmann::ordered_json({{"b", 2}, {"a", 1}}), depth);
+        CHECK_FALSE(ab == ba);
+        CHECK(ab != ba);
+    }
+}

tests/src/unit-msgpack.cpp

@@ -14,7 +14,6 @@ using nlohmann::json;
     using namespace nlohmann::literals; // NOLINT(google-build-using-namespace)
 #endif
 
-#include <cstdint> // SIZE_MAX, UINT32_MAX
 #include <fstream>
 #include <sstream>
 #include <iomanip>
@@ -2151,81 +2150,3 @@ TEST_CASE("MessagePack with std::byte")
     }
 }
 #endif
-
-namespace
-{
-// types that report a size beyond UINT32_MAX without allocating that much
-// memory, so the MessagePack length limit can be tested cheaply; see the
-// similar types in unit-bson.cpp
-std::size_t beyond_uint32_size()
-{
-    return static_cast<std::size_t>((std::numeric_limits<std::uint32_t>::max)()) + 1;
-}
-
-class beyond_uint32_binary_t : public std::vector<std::uint8_t>
-{
-  public:
-    using std::vector<std::uint8_t>::vector;
-
-    size_type size() const noexcept // NOLINT(readability-convert-member-functions-to-static)
-    {
-        return beyond_uint32_size();
-    }
-};
-
-// with clang and libstdc++ 10, the std::filesystem::path conversion that
-// C++17 builds consider for every string type is ambiguous for a class
-// derived from std::string, so the string case is not tested there
-#if !(defined(__clang__) && defined(_GLIBCXX_RELEASE) && _GLIBCXX_RELEASE < 11)
-    #define JSON_TEST_BEYOND_UINT32_STRING 1
-#endif
-
-#ifdef JSON_TEST_BEYOND_UINT32_STRING
-class beyond_uint32_string_t : public std::string
-{
-  public:
-    using std::string::string;
-
-    size_type size() const noexcept // NOLINT(readability-convert-member-functions-to-static)
-    {
-        return beyond_uint32_size();
-    }
-};
-#endif
-
-using beyond_uint32_binary_json = nlohmann::basic_json <
-                                  std::map, std::vector, std::string, bool, std::int64_t, std::uint64_t,
-                                  double, std::allocator, nlohmann::adl_serializer, beyond_uint32_binary_t, void >;
-
-#ifdef JSON_TEST_BEYOND_UINT32_STRING
-using beyond_uint32_string_json = nlohmann::basic_json <
-                                  std::map, std::vector, beyond_uint32_string_t, bool, std::int64_t, std::uint64_t,
-                                  double, std::allocator, nlohmann::adl_serializer, std::vector<std::uint8_t>, void >;
-#endif
-} // namespace
-
-TEST_CASE("MessagePack lengths beyond UINT32_MAX cannot be serialized")
-{
-    // MessagePack stores the length of a string, binary value, array, or
-    // object in at most 32 bits; a larger one used to be written without any
-    // length at all
-#if SIZE_MAX > UINT32_MAX
-    {
-        const char* const expected = "[json.exception.out_of_range.412] MessagePack length 4294967296 exceeds maximum of 4294967295";
-
-        const beyond_uint32_binary_json binary = beyond_uint32_binary_json::binary(beyond_uint32_binary_t{});
-        CHECK_THROWS_WITH_AS(beyond_uint32_binary_json::to_msgpack(binary), expected, beyond_uint32_binary_json::out_of_range&);
-
-        const beyond_uint32_binary_json ext = beyond_uint32_binary_json::binary(beyond_uint32_binary_t{}, 42);
-        CHECK_THROWS_WITH_AS(beyond_uint32_binary_json::to_msgpack(ext), expected, beyond_uint32_binary_json::out_of_range&);
-
-#ifdef JSON_TEST_BEYOND_UINT32_STRING
-        // created from its type rather than from a beyond_uint32_string_t:
-        // that would consider the std::filesystem::path conversion, which
-        // libstdc++ 10 cannot decide for a class derived from std::string
-        const beyond_uint32_string_json string(beyond_uint32_string_json::value_t::string);
-        CHECK_THROWS_WITH_AS(beyond_uint32_string_json::to_msgpack(string), expected, beyond_uint32_string_json::out_of_range&);
-#endif
-    }
-#endif
-}