Export json_sax_dom_parser from the C++20 module for MSVC

MSVC needs the detail classes that basic_json befriends to be visible in
the module (#3970, as json_sax_dom_callback_parser); with its new
template parameter, json_sax_dom_parser failed in ci_module_cpp20
(C2039, not a member of nlohmann::detail).

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

include/nlohmann/detail/input/binary_reader.hpp

@@ -86,7 +86,7 @@ JSON_INLINE_VARIABLE constexpr std::size_t max_valueless_container_size = 1 << 2
 /*!
 @brief deserialization of BJData, BON8, BSON, CBOR, MessagePack, and UBJSON values
 */
-template<typename BasicJsonType, typename InputAdapterType, typename SAX = json_sax_dom_parser<BasicJsonType, InputAdapterType>>
+template<typename BasicJsonType, typename InputAdapterType, typename SAX = json_sax_dom_binary_parser<BasicJsonType, InputAdapterType>>
 class binary_reader
 {
     using number_integer_t = typename BasicJsonType::number_integer_t;

include/nlohmann/detail/input/lexer.hpp

@@ -14,6 +14,7 @@
 #include <cstdio> // snprintf
 #include <cstring> // memcmp
 #include <initializer_list> // initializer_list
+#include <limits> // numeric_limits
 #include <string> // char_traits, string
 #include <utility> // move
 #include <vector> // vector
@@ -1816,6 +1817,15 @@ scan_number_done:
     /// significand (see scan_number_bulk_contiguous())
     bool convert_accumulated_float(const float_significand& s, std::true_type /*native*/) noexcept
     {
+        // accept() only needs to know that the value is finite (see the parser):
+        // w < 10^19, so a value below 10^max_exponent10 cannot overflow, and a
+        // value that underflows is a finite number as well. Only a token that
+        // may overflow has to be converted to find out.
+        if (JSON_HEDLEY_UNLIKELY(discard_number_values && s.exponent + 19 <= std::numeric_limits<number_float_t>::max_exponent10))
+        {
+            value_float = 0;
+            return true;
+        }
         value_float = decimal_to_float<number_float_t>(s);
         return true;
     }

include/nlohmann/detail/input/parser.hpp

@@ -56,8 +56,8 @@ using parser_callback_t =
 template<typename SAX>
 struct sax_ignores_number_text : std::false_type {};
 
-template<typename BasicJsonType, typename InputAdapterType>
+template<typename BasicJsonType, typename InputAdapterType, bool Collect>
-struct sax_ignores_number_text<json_sax_dom_parser<BasicJsonType, InputAdapterType>> : std::true_type {};
+struct sax_ignores_number_text<json_sax_dom_parser<BasicJsonType, InputAdapterType, Collect>> : std::true_type {};
 
 template<typename BasicJsonType, typename InputAdapterType>
 struct sax_ignores_number_text<json_sax_dom_callback_parser<BasicJsonType, InputAdapterType>> : std::true_type {};
@@ -131,7 +131,7 @@ class parser
         }
         else
         {
-            json_sax_dom_parser<BasicJsonType, InputAdapterType> sdp(result, allow_exceptions, &m_lexer);
+            json_sax_dom_parser<BasicJsonType, InputAdapterType, true> sdp(result, allow_exceptions, &m_lexer);
 
             // in case of an error, return a discarded value
             if (!parse_dom(sdp, strict))
@@ -243,12 +243,19 @@ class parser
     JSON_HEDLEY_NON_NULL(2)
     bool sax_parse_internal(SAX* sax)
     {
+        // value to avoid a goto (see comment where set to true)
+        bool skip_to_state_evaluation = false;
+
         // stack to remember the hierarchy of structured values we are parsing
         // true = array; false = object (bytes, not std::vector<bool>, whose
         // push_back() is a call with GCC)
         std::vector<std::uint8_t> states;
-        // value to avoid a goto (see comment where set to true)
+        // a document that starts with a container pushes onto the stack at
-        bool skip_to_state_evaluation = false;
+        // once: allocate it in one step instead of growing it from 1 byte
+        if (last_token == token_type::begin_object || last_token == token_type::begin_array)
+        {
+            states.reserve(32);
+        }
 
         while (true)
         {

include/nlohmann/detail/view/image.hpp

@@ -255,81 +255,6 @@ struct number_token
     bool is_float; ///< a fraction or an exponent
 };
 
-/// advance over ASCII digits, eight bytes at a time
-inline const unsigned char* digit_run(const unsigned char* p, const unsigned char* e) noexcept
-{
-    constexpr std::uint64_t ones = 0x0101010101010101ull;
-    while (e - p >= 8)
-    {
-        // (the digits become 0..9; a byte above 9, or with bit 7 set, is no digit. A carry
-        // out of a byte with bit 7 set only affects the bytes above, after the first one
-        // that count_trailing_zeros finds.)
-        const std::uint64_t x = read_eight_bytes(p) ^ (ones * 0x30u);
-        const std::uint64_t not_digit = ((x + (ones * 0x76u)) | x) & (ones * 0x80u);
-        if (not_digit != 0)
-        {
-            return p + (static_cast<std::size_t>(count_trailing_zeros(not_digit)) / 8);
-        }
-        p += 8;
-    }
-    while (p != e && is_digit(*p))
-    {
-        ++p;
-    }
-    return p;
-}
-
-/// whether the n bytes at p are ASCII digits (n > 0)
-inline bool all_digits(const unsigned char* p, std::size_t n) noexcept
-{
-    const auto digits = [](const unsigned char* q)
-    {
-        constexpr std::uint64_t ones = 0x0101010101010101ull;
-        const std::uint64_t x = read_eight_bytes(q) ^ (ones * 0x30u);
-        return (((x + (ones * 0x76u)) | x) & (ones * 0x80u)) == 0;
-    };
-    if (n >= 8)
-    {
-        for (std::size_t i = 0; i + 8 < n; i += 8)
-        {
-            if (!digits(p + i))
-            {
-                return false;
-            }
-        }
-        return digits(p + n - 8); // (overlapping the bytes before: they are digits)
-    }
-    for (std::size_t i = 0; i < n; ++i)
-    {
-        if (!is_digit(p[i]))
-        {
-            return false;
-        }
-    }
-    return true;
-}
-
-/// Whether a float token has the shape that the parser records for most of
-/// them: [-]digits.digits, with the numbers of digits of the node's layout
-/// (extra). Then the token is a number of that layout, and the general scan
-/// that follows is not needed.
-inline bool plain_float_token(const unsigned char* s, std::size_t len, std::uint16_t extra) noexcept
-{
-    const std::size_t int_digits = extra & 0xFFu;
-    const std::size_t frac_digits = extra >> 8u;
-    if (int_digits == 0 || int_digits >= 255 || frac_digits == 0 || frac_digits >= 255 || len == 0)
-    {
-        return false;
-    }
-    const std::size_t negative = *s == '-' ? 1 : 0;
-    if (len != negative + int_digits + 1 + frac_digits)
-    {
-        return false;
-    }
-    const unsigned char* const p = s + negative;
-    return !(int_digits > 1 && *p == '0') && p[int_digits] == '.' && all_digits(p, int_digits) && all_digits(p + int_digits + 1, frac_digits);
-}
-
 /// whether [s, s + len) is a JSON number (the grammar the parser accepts)
 inline bool scan_number_token(const unsigned char* s, std::size_t len, number_token& t)
 {
@@ -348,7 +273,11 @@ inline bool scan_number_token(const unsigned char* s, std::size_t len, number_to
     }
     else if (*p >= '1' && *p <= '9')
     {
-        p = digit_run(p + 1, e);
+        do
+        {
+            ++p;
+        }
+        while (p != e && is_digit(*p));
     }
     else
     {
@@ -360,7 +289,10 @@ inline bool scan_number_token(const unsigned char* s, std::size_t len, number_to
     if (p != e && *p == '.')
     {
         const unsigned char* const f0 = ++p;
-        p = digit_run(p, e);
+        while (p != e && is_digit(*p))
+        {
+            ++p;
+        }
         if (p == f0)
         {
             return false;
@@ -471,15 +403,10 @@ struct float_range
 template<typename Check>
 bool check_distinct_ranges(std::vector<byte_range>& ranges, Check check)
 {
-    // (save() writes the ranges in the order of the nodes, which is sorted already)
+    std::sort(ranges.begin(), ranges.end(), [](const byte_range & a, const byte_range & b)
-    const auto before = [](const byte_range & a, const byte_range & b)
     {
         return a.off != b.off ? a.off < b.off : a.len < b.len;
-    };
+    });
-    if (!std::is_sorted(ranges.begin(), ranges.end(), before))
-    {
-        std::sort(ranges.begin(), ranges.end(), before);
-    }
     std::size_t end = 0;
     for (std::size_t i = 0; i < ranges.size(); ++i)
     {
@@ -501,8 +428,7 @@ bool check_distinct_ranges(std::vector<byte_range>& ranges, Check check)
 /// record layouts that match it), tokens must not overlap.
 inline bool check_float_ranges(std::vector<float_range>& ranges, const unsigned char* text)
 {
-    // (save() writes the tokens in the order of the nodes, which is sorted already)
+    std::sort(ranges.begin(), ranges.end(), [](const float_range & a, const float_range & b)
-    const auto before = [](const float_range & a, const float_range & b)
     {
         if (a.off != b.off)
         {
@@ -513,11 +439,7 @@ inline bool check_float_ranges(std::vector<float_range>& ranges, const unsigned
             return a.len < b.len;
         }
         return a.extra < b.extra;
-    };
+    });
-    if (!std::is_sorted(ranges.begin(), ranges.end(), before))
-    {
-        std::sort(ranges.begin(), ranges.end(), before);
-    }
     std::size_t end = 0;
     std::size_t i = 0;
     while (i < ranges.size())
@@ -527,18 +449,14 @@ inline bool check_float_ranges(std::vector<float_range>& ranges, const unsigned
         {
             return false;
         }
-        const unsigned char* const s = text + r.off;
-        std::uint16_t layout = r.extra;
-        if (!plain_float_token(s, r.len, r.extra))
-        {
         number_token t{};
+        const unsigned char* const s = text + r.off;
         if (!scan_number_token(s, r.len, t) || !float_token_finite(s, r.len, t))
         {
             return false;
         }
         // the digit layout the parser records (or "many", as compaction writes it)
-            layout = float_layout(t);
+        const std::uint16_t layout = float_layout(t);
-        }
         for (; i < ranges.size() && ranges[i].off == r.off && ranges[i].len == r.len; ++i)
         {
             if (ranges[i].extra != layout && ranges[i].extra != 0xFFFFu)

include/nlohmann/detail/view/materialize.hpp

@@ -40,7 +40,7 @@ template<typename BasicJsonType, bool Editable>
 BasicJsonType materialize(const document_data& d, const node* n)
 {
     using string_t = typename BasicJsonType::string_t;
-    using sax_t = json_sax_dom_parser<BasicJsonType, iterator_input_adapter<const char*>>;
+    using sax_t = json_sax_dom_parser<BasicJsonType, iterator_input_adapter<const char*>, true>;
     using nav = navigation<Editable>;
 
     // the open containers: their next element (or key of the next member),

include/nlohmann/json.hpp

@@ -158,9 +158,11 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     friend class ::nlohmann::detail::binary_writer;
     template<typename BasicJsonType, typename InputType, typename SAX>
     friend class ::nlohmann::detail::binary_reader;
-    template<typename BasicJsonType, typename InputAdapterType>
+    template<typename BasicJsonType, typename InputAdapterType, bool Collect>
     friend class ::nlohmann::detail::json_sax_dom_parser;
     template<typename BasicJsonType, typename InputAdapterType>
+    friend class ::nlohmann::detail::json_sax_dom_binary_parser;
+    template<typename BasicJsonType, typename InputAdapterType>
     friend class ::nlohmann::detail::json_sax_dom_callback_parser;
 #if JSON_DIAGNOSTIC_POSITIONS
     friend struct ::nlohmann::detail::diagnostic_positions;
@@ -6287,7 +6289,7 @@ public:
            from_ubjson/from_bjdata/from_bon8/from_bson overloads
 
     Building the @ref binary_reader as a named local, rather than as a
-    temporary that @ref detail::json_sax_dom_parser::parse is called on in
+    temporary that @ref detail::json_sax_dom_binary_parser::parse is called on in
     the same expression, avoids a false-positive cppcheck accessMoved
     warning in each of the 16 callers.
     */
@@ -6298,7 +6300,7 @@ public:
                                        const cbor_tag_handler_t tag_handler = cbor_tag_handler_t::error)
     {
         basic_json result;
-        detail::json_sax_dom_parser<basic_json, InputAdapterType> sdp(result, allow_exceptions);
+        detail::json_sax_dom_binary_parser<basic_json, InputAdapterType> sdp(result, allow_exceptions);
         binary_reader<InputAdapterType> reader(std::move(ia), format, error_handler);
         if (!reader.sax_parse(&sdp, strict, tag_handler))
         {

include/nlohmann/json_view.hpp

@@ -723,12 +723,8 @@ class basic_json_view
     template<typename, bool> friend class basic_json_document;
     template<typename, bool> friend class basic_json_view;
     template<typename, typename> friend class detail::view::editor;
-    template<typename, typename> friend class detail::view::view_side;
     friend iterator;
 
-    /// whether the view is one of an editable document
-    static constexpr bool is_editable = Editable;
-
     basic_json_view(const document_data* d, const node* n) noexcept
         : m_doc(d), m_node(n)
     {}

src/modules/json.cppm

@@ -60,6 +60,7 @@ inline namespace json_literals
 namespace detail
 {
     using NLOHMANN_JSON_NAMESPACE::detail::json_sax_dom_callback_parser;
+    using NLOHMANN_JSON_NAMESPACE::detail::json_sax_dom_parser;
     using NLOHMANN_JSON_NAMESPACE::detail::unknown_size;
 } // namespace detail
 

tests/src/unit-class_parser.cpp

@@ -2952,3 +2952,81 @@ TEST_CASE("diagnostic positions: value lifetime, input adapters, and SAX")
     }
 }
 #endif
+
+TEST_CASE("accept() agrees with parse() on floats around the overflow limit")
+{
+    // accept() does not convert a float that cannot overflow; the tokens
+    // around the limit (and beyond it) must still be rejected exactly as
+    // parse() rejects them
+    const char* const numbers[] =
+    {
+        "1e0", "123.456e-5", "1e-400", "-1e-400", "1e307", "1e308", "1e309", "-1e309",
+        "10e307", "100e307", "0.1e309", "0.1e310", "1E+308", "1E+309",
+        "1.7976931348623157e308", "1.7976931348623159e308", "1.8e308", "-1.7976931348623157e308",
+        "12345678901234567e291", "12345678901234567e292", "123456789012345678e290", "123456789012345678e291",
+        "1234567890123456789e289", "1234567890123456789e290", "9999999999999999999e289", "9999999999999999999e290",
+        "0.00000000000000000001e328", "0.00000000000000000001e329"
+    };
+
+    for (const char* number : numbers)
+    {
+        for (const std::string& text :
+                {
+                    std::string(number), "[" + std::string(number) + "]", "{\"a\":" + std::string(number) + "}"
+                })
+        {
+            INFO(text);
+            const bool parses = !json::parse(text, nullptr, false).is_discarded();
+            CHECK(json::accept(text) == parses);
+        }
+    }
+}
+
+namespace
+{
+// a DOM parser that reports parse errors without throwing, as in the sax_no_exception example
+template<typename BasicJsonType>
+class quiet_dom_parser : public nlohmann::detail::json_sax_dom_parser<BasicJsonType, nlohmann::detail::string_input_adapter_type>
+{
+  public:
+    explicit quiet_dom_parser(BasicJsonType& j)
+        : nlohmann::detail::json_sax_dom_parser<BasicJsonType, nlohmann::detail::string_input_adapter_type>(j, false)
+    {}
+
+    bool parse_error(std::size_t /*unused*/, const std::string& /*unused*/, const nlohmann::detail::exception& /*unused*/)
+    {
+        return false;
+    }
+};
+
+template<typename BasicJsonType>
+std::string read_before_error(const std::string& text)
+{
+    BasicJsonType j;
+    quiet_dom_parser<BasicJsonType> sax(j);
+    CHECK(!BasicJsonType::sax_parse(text, &sax));
+    return j.dump();
+}
+} // namespace
+
+TEST_CASE("a json_sax_dom_parser keeps the values read before a parse error")
+{
+    // a json_sax_dom_parser that a user constructs stores every value in place, so a
+    // handler that does not throw on a parse error sees what was read before it
+    const std::vector<std::pair<std::string, std::string>> cases =
+    {
+        {"[1,2,3,]", "[1,2,3]"},
+        {"[[1,[2,3],4],[5,", "[[1,[2,3],4],[5]]"},
+        {R"({"a":1,"b":[1,2,{"c":)", R"({"a":1,"b":[1,2,{"c":null}]})"},
+        {R"({"a":1,"a":)", R"({"a":1})"},
+        {"[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,]", "[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]"},
+        {R"({"k0":0,"k1":1,"k2":{"x":[true,)", R"({"k0":0,"k1":1,"k2":{"x":[true]}})"},
+        {R"([{},[],{"a":[]},x)", R"([{},[],{"a":[]}])"},
+    };
+    for (const auto& c : cases)
+    {
+        CAPTURE(c.first)
+        CHECK(read_before_error<json>(c.first) == c.second);
+        CHECK(read_before_error<nlohmann::ordered_json>(c.first) == c.second);
+    }
+}

tests/src/unit-json_view_dump.cpp

@@ -345,35 +345,6 @@ TEST_CASE("json_view comparison")
         }
     }
 
-    SECTION("objects whose first keys differ or repeat")
-    {
-        const std::array<const char*, 17> texts =
-        {
-            {
-                R"({"a":1,"b":2})", R"({"a":1,"c":2})", R"({"b":1,"a":2})", R"({"a":1,"a":2,"b":3})", R"({"a":2,"b":3})",
-                R"({"a":1,"b":1,"a":2})", R"({"a":2,"b":1})", R"({"a":1,"a":2})", R"({"b":1})", R"({"a":1,"b":2,"c":3,"d":4,"e":5})",
-                R"({"a":1,"b":2,"c":3,"d":4,"f":5})", R"({"a":1,"b":2,"c":3,"a":4,"e":5})", R"({"a":4,"b":2,"c":3,"e":5})",
-                R"({"\u0061":1,"b":2})", R"({})", R"([{"a":1,"b":2}])", R"([{"a":1,"c":2}])"
-            }
-        };
-        for (const char* const x : texts)
-        {
-            for (const char* const y : texts)
-            {
-                CAPTURE(x)
-                CAPTURE(y)
-                const ordered_json_document dx = ordered_json_document::parse(x);
-                const ordered_json_document dy = ordered_json_document::parse(y);
-                const ordered_json_editable_document ex = ordered_json_editable_document::parse(x);
-                const ordered_json jx = ordered_json::parse(x);
-                const ordered_json jy = ordered_json::parse(y);
-                CHECK((dx.root() == dy.root()) == (jx == jy));
-                CHECK((dx.root() == jy) == (jx == jy));
-                CHECK((ex.root() == dy.root()) == (jx == jy));
-            }
-        }
-    }
-
     SECTION("numbers, duplicate keys, member order")
     {
         const auto same = [](const char* x, const char* y)
@@ -414,151 +385,6 @@ TEST_CASE("json_view comparison")
         CHECK(!(null_document.root() == discarded));
     }
 
-    SECTION("values that are the same text, or the same value written differently, at any depth")
-    {
-        // nested arrays and objects around depths where the walk over equal text gives up
-        for (const int depth :
-                {
-                    1, 5, 47, 48, 49, 50, 60, 300
-                })
-        {
-            CAPTURE(depth)
-            std::string head;
-            std::string tail;
-            for (int i = 0; i < depth; ++i)
-            {
-                head += i % 2 == 0 ? R"({"k":[1,"s",{"x":true},)" : R"([null,2.5,{"y":)";
-                tail.insert(0, i % 2 == 0 ? "]}" : "}]");
-            }
-            // the same text, one number changed, and one number written differently
-            const auto with_number = [&](const char* number)
-            {
-                std::string result = head;
-                result += number;
-                result += tail;
-                return result;
-            };
-            const std::string text = with_number("7");
-            const std::string changed = with_number("8");
-            const std::string spelled = with_number("7.0");
-            const json_document a = json_document::parse(text);
-            const json_document b = json_document::parse(text);
-            const json_document c = json_document::parse(changed);
-            const json_document d = json_document::parse(spelled);
-            CHECK(a.root() == b.root());
-            CHECK(a.root() != c.root());
-            CHECK(c.root() != a.root());
-            CHECK(a.root() == d.root());
-            CHECK(d.root() == a.root());
-            CHECK(a.root() == json::parse(text));
-            CHECK(a.root() != json::parse(changed));
-            CHECK(json::parse(spelled) == a.root());
-            const nlohmann::json_editable_document e = nlohmann::json_editable_document::parse(text);
-            CHECK(a.root() == e.root());
-            CHECK(e.root() == a.root());
-            CHECK(c.root() != e.root());
-            CHECK(e.root() == e.root());
-            const ordered_json_document oa = ordered_json_document::parse(text);
-            const ordered_json_document oc = ordered_json_document::parse(changed);
-            CHECK(oa.root() != oc.root());
-            CHECK(oa.root() == ordered_json::parse(text));
-            CHECK(oc.root() != ordered_json::parse(text));
-        }
-
-        // not the same text, but the same value
-        const auto same = [](const char* x, const char* y)
-        {
-            const json_document dx = json_document::parse(x);
-            const json_document dy = json_document::parse(y);
-            const bool equal = dx.root() == dy.root();
-            CHECK(equal == (json::parse(x) == json::parse(y)));
-            CHECK(equal == (dx.root() == json::parse(y)));
-            return equal;
-        };
-        CHECK(same(R"({"a":1,"a":2})", R"({"a":3,"a":2})"));
-        CHECK(same(R"({"a":1,"b":[1,{"c":2,"c":3}]})", R"({"b":[1,{"c":9,"c":3}],"a":1})"));
-        CHECK(!same(R"({"a":1,"a":2})", R"({"a":2,"a":3})"));
-        CHECK(same("[1.0,-0,0,1e2]", "[1.00,0,-0,100.0]"));
-        CHECK(same(R"(["\u00e9","\n"])", "[\"\xc3\xa9\",\"\\n\"]"));
-        CHECK(!same(R"({"a":[1,2,{"b":null}]})", R"({"a":[1,2,{"b":false}]})"));
-        CHECK(!same(R"({"a":[1,2,{"b":null}]})", R"({"a":[1,2,{"c":null}]})"));
-        CHECK(!same(R"({"a":[1,2,{"b":null}]})", R"({"a":[1,2,{"b":null,"c":1}]})"));
-
-        // edited documents: moved sequences, links, and values of new nodes
-        nlohmann::json_editable_document edited = nlohmann::json_editable_document::parse(R"({"a":[1,2,3],"b":{"c":"d"},"e":0.5})");
-        const json_document plain = json_document::parse(R"({"a":[1,2,3,4],"b":{"c":"x","y":null},"e":0.5,"z":[]})");
-        edited.push_back(edited.root()["a"], 4);
-        edited.set(edited.root()["b"], "c", "x");
-        edited.set(edited.root()["b"], "y", nullptr);
-        edited.set(edited.root(), "z", json::array());
-        CHECK(edited.root() == plain.root());
-        CHECK(plain.root() == edited.root());
-        edited.erase(edited.root()["a"], 0);
-        CHECK(edited.root() != plain.root());
-        CHECK(edited.root()["a"] == json::parse("[2,3,4]"));
-        const json_document tail = json_document::parse("[2,3,4]");
-        CHECK(edited.root()["a"] == tail.root());
-    }
-
-    SECTION("large documents, with a difference at any place")
-    {
-        const auto make = [](std::size_t count, std::size_t changed, bool swap_members)
-        {
-            std::string text = R"({"b":1,"list":[)";
-            for (std::size_t i = 0; i < count; ++i)
-            {
-                text += (i != 0 ? "," : "");
-                const std::string id = std::to_string(i == changed ? i + 1 : i);
-                if (swap_members && i % 3 == 0)
-                {
-                    text += R"({"v":[1.5,"s",{"k":)";
-                    text += id;
-                    text += R"(}],"id":)";
-                    text += id;
-                    text += "}";
-                }
-                else
-                {
-                    text += R"({"id":)";
-                    text += id;
-                    text += R"(,"v":[1.5,"s",{"k":)";
-                    text += id;
-                    text += "}]}";
-                }
-            }
-            return text + R"(],"a":{"y":2,"x":3}})";
-        };
-        const std::size_t count = 3000;
-        for (const std::size_t changed :
-                {
-                    count, std::size_t{0}, std::size_t{1}, count / 2, count - 1
-                })
-        {
-            for (const bool swap :
-                    {
-                        false, true
-                    })
-            {
-                CAPTURE(changed)
-                CAPTURE(swap)
-                const std::string text_a = make(count, count, false);
-                const std::string text_b = make(count, changed, swap);
-                const json_document a = json_document::parse(text_a);
-                const json_document b = json_document::parse(text_b);
-                const bool equal = changed == count;
-                CHECK((a.root() == b.root()) == equal);
-                CHECK((b.root() == a.root()) == equal);
-                CHECK((a.root() == json::parse(text_b)) == equal);
-                CHECK((json::parse(text_b) == a.root()) == equal);
-                CHECK((a.root()["list"] == b.root()["list"]) == equal);
-                const ordered_json_document oa = ordered_json_document::parse(text_a);
-                const ordered_json_document ob = ordered_json_document::parse(text_b);
-                CHECK((oa.root() == ob.root()) == (equal && !swap));
-                CHECK((oa.root() == ordered_json::parse(text_b)) == (equal && !swap));
-            }
-        }
-    }
-
     SECTION("deep nesting")
     {
         const std::string deep = std::string(100000, '[') + std::string(100000, ']');

tests/src/unit-json_view_image.cpp

@@ -682,66 +682,6 @@ TEST_CASE("json_view images: ownership")
 #if !defined(JSON_NOEXCEPTION)
 TEST_CASE("json_view images: errors")
 {
-#if !defined(JSON_NOEXCEPTION)
-    SECTION("float tokens: a changed byte is accepted if the text is still a number with the digits the node records")
-    {
-        for (const char* const token :
-                {
-                    "-12.375", "0.5", "123456.0", "-0.0", "9999999999999999999.5", "0.000000000000000000000001", "1.25e10", "5E-3"
-                })
-        {
-            CAPTURE(token)
-            const std::string text = std::string("[") + token + "]";
-            const json_document d = json_document::parse(text);
-            const std::vector<std::uint8_t> image = d.save();
-            const std::size_t at = text_at(image) + 1; // the first byte of the token
-            const std::uint16_t recorded = node_at(image, 1).extra;
-            CHECK(loaded_dump(image) == json::parse(text).dump());
-            for (std::size_t pos = 0; token[pos] != '\0'; ++pos)
-            {
-                for (unsigned int byte = 0; byte < 256; ++byte)
-                {
-                    std::vector<std::uint8_t> changed = image;
-                    changed[at + pos] = static_cast<std::uint8_t>(byte);
-                    std::string t = token;
-                    t[pos] = static_cast<char>(byte);
-                    // the digits of the integer part and of the fraction of the changed token
-                    std::size_t integer = 0;
-                    std::size_t fraction = 0;
-                    std::size_t k = (t[0] == '-') ? 1 : 0;
-                    for (; k < t.size() && t[k] >= '0' && t[k] <= '9'; ++k)
-                    {
-                        ++integer;
-                    }
-                    if (k < t.size() && t[k] == '.')
-                    {
-                        for (++k; k < t.size() && t[k] >= '0' && t[k] <= '9'; ++k)
-                        {
-                            ++fraction;
-                        }
-                    }
-                    // (as a JSON text, the token may have white space around it)
-                    const bool float_token = json::accept(t) && t.find_first_of(std::string(" \t\r\n\0", 5)) == std::string::npos && (t.find('.') != std::string::npos || t.find_first_of("eE") != std::string::npos)
-                                             && ((integer | (fraction << 8U)) == recorded);
-                    CAPTURE(pos)
-                    CAPTURE(byte)
-                    std::string result;
-                    try
-                    {
-                        result = loaded_dump(changed);
-                    }
-                    catch (const json::parse_error& e)
-                    {
-                        CHECK(std::string(e.what()) == check_failed);
-                        result = "rejected";
-                    }
-                    CHECK((result != "rejected") == float_token);
-                }
-            }
-        }
-    }
-#endif
-
     SECTION("a literal as the root: dump() after loading")
     {
         for (const char* text :

tests/src/unit-ordered_json.cpp

@@ -237,3 +237,274 @@ TEST_CASE("regression test for issue #5673 - ordered_json::emplace with a non-rv
         CHECK(oj.dump() == "{\"a\":1}");
     }
 }
+
+namespace
+{
+// the sizes around which the DOM parser changes how it stores the elements of
+// an array (16) and the members of an object in a vector (32, and 64 for the
+// key index)
+const std::size_t container_sizes[] = {0, 1, 2, 3, 15, 16, 17, 18, 31, 32, 33, 34, 63, 64, 65, 66, 200};
+
+template<typename Json>
+std::string array_text(const std::size_t n, const std::size_t depth)
+{
+    std::string text = "[";
+    for (std::size_t i = 0; i < n; ++i)
+    {
+        text += (i == 0 ? "" : ",");
+        // alternate scalars, empty containers and nested containers
+        switch (i % 4)
+        {
+            case 0:
+                text += std::to_string(i);
+                break;
+            case 1:
+                text += "\"s" + std::to_string(i) + "\"";
+                break;
+            case 2:
+                text += depth == 0 ? "[]" : array_text<Json>(n / 2, depth - 1);
+                break;
+            default:
+                text += depth == 0 ? "{}" : "{\"a\":" + array_text<Json>(n / 3, depth - 1) + ",\"b\":null}";
+                break;
+        }
+    }
+    return text + "]";
+}
+
+template<typename Json>
+std::string object_text(const std::size_t n, const std::size_t depth, const bool duplicates)
+{
+    std::string text = "{";
+    for (std::size_t i = 0; i < n; ++i)
+    {
+        text += (i == 0 ? "" : ",");
+        text += "\"key" + std::to_string(i) + "\":";
+        switch (i % 4)
+        {
+            case 0:
+                text += std::to_string(i);
+                break;
+            case 1:
+                text += depth == 0 ? "[]" : array_text<Json>(n / 2, depth - 1);
+                break;
+            case 2:
+                text += depth == 0 ? "{}" : object_text<Json>(n / 2, depth - 1, duplicates);
+                break;
+            default:
+                text += "\"value\"";
+                break;
+        }
+    }
+    if (duplicates)
+    {
+        // keys that are there already, the first and the last one, with other values
+        text += n == 0 ? "" : ",";
+        text += "\"key0\":[1,2],\"key" + std::to_string(n - 1) + "\":{\"again\":true}";
+    }
+    return text + "}";
+}
+
+template<typename Json>
+void check_same_dump(const std::string& text)
+{
+    // the text is what dump() writes for the parsed value, and the value
+    // survives a second round trip: arrays keep their elements in order, an
+    // ordered_json keeps its members in order of appearance
+    const Json parsed = Json::parse(text);
+    const Json again = Json::parse(parsed.dump());
+    CHECK(parsed == again);
+    CHECK(parsed.dump() == again.dump());
+    CHECK(Json::accept(text));
+}
+} // namespace
+
+TEST_CASE("parsing containers of sizes around the limits of the DOM parser")
+{
+    SECTION("arrays")
+    {
+        for (const std::size_t n : container_sizes)
+        {
+            const std::string text = array_text<json>(n, 2);
+            INFO("size ", n);
+
+            const json parsed = json::parse(text);
+            CHECK(parsed.is_array());
+            CHECK(parsed.size() == n);
+            for (std::size_t i = 0; i < n; i += 4)
+            {
+                CHECK(parsed[i] == i);
+            }
+            check_same_dump<json>(text);
+            check_same_dump<ordered_json>(text);
+            CHECK(ordered_json::parse(text).dump() == parsed.dump());
+        }
+    }
+
+    SECTION("objects")
+    {
+        for (const bool duplicates :
+                {
+                    false, true
+                })
+        {
+            for (const std::size_t n : container_sizes)
+            {
+                const std::string text = object_text<json>(n, 2, duplicates);
+                INFO("size ", n, " duplicates ", duplicates);
+
+                const json parsed = json::parse(text);
+                const ordered_json ordered = ordered_json::parse(text);
+                CHECK(parsed.is_object());
+                CHECK(ordered.is_object());
+                CHECK(parsed.size() == ordered.size());
+                // the same members, in the order of their first appearance
+                std::size_t i = 0;
+                for (auto it = ordered.begin(); it != ordered.end(); ++it, ++i)
+                {
+                    if (i < n)
+                    {
+                        CHECK(it.key() == "key" + std::to_string(i));
+                    }
+                    CHECK(parsed.at(it.key()) == json(it.value()));
+                }
+                if (duplicates && n > 1)
+                {
+                    // the later value replaced the earlier one in its place
+                    CHECK(ordered.at("key0") == ordered_json::parse("[1,2]"));
+                    CHECK(ordered.at("key" + std::to_string(n - 1)) == ordered_json::parse("{\"again\":true}"));
+                    CHECK(ordered.begin().key() == "key0");
+                    CHECK(ordered.size() == n);
+                }
+                check_same_dump<json>(text);
+                check_same_dump<ordered_json>(text);
+            }
+        }
+    }
+
+    SECTION("objects with many different and repeated keys")
+    {
+        // 300 members of which a third repeat an earlier key
+        std::string text = "{";
+        for (std::size_t i = 0; i < 300; ++i)
+        {
+            text += (i == 0 ? "" : ",");
+            text += "\"k" + std::to_string(i % 200) + "\":" + std::to_string(i);
+        }
+        text += "}";
+
+        const ordered_json ordered = ordered_json::parse(text);
+        const json parsed = json::parse(text);
+        CHECK(ordered.size() == 200);
+        CHECK(parsed.size() == 200);
+        std::size_t i = 0;
+        for (auto it = ordered.begin(); it != ordered.end(); ++it, ++i)
+        {
+            CHECK(it.key() == "k" + std::to_string(i));
+            // the last value written
+            CHECK(it.value() == (i < 100 ? i + 200 : i));
+            CHECK(parsed.at(it.key()) == json(it.value()));
+        }
+    }
+}
+
+namespace
+{
+// a deterministic source of structure for parsing tests: builds a JSON text
+// and, at the same time, the value it has to parse to
+class tree_generator
+{
+  public:
+    explicit tree_generator(std::uint32_t seed) : state(seed) {}
+
+    template<typename Json>
+    Json make(std::string& text, const std::size_t depth)
+    {
+        switch (next(depth == 0 ? 5 : 9))
+        {
+            case 0:
+                text += "null";
+                return Json(nullptr);
+            case 1:
+                text += "true";
+                return Json(true);
+            case 2:
+            {
+                const int n = static_cast<int>(next(2000)) - 1000;
+                text += std::to_string(n);
+                return Json(n);
+            }
+            case 3:
+                text += "\"text\"";
+                return Json("text");
+            case 4:
+                text += "2.5";
+                return Json(2.5);
+            case 5:
+            case 6:
+            case 7:
+            {
+                Json array = Json::array();
+                text += "[";
+                const std::size_t n = size();
+                for (std::size_t i = 0; i < n; ++i)
+                {
+                    text += (i == 0 ? "" : ",");
+                    array.push_back(make<Json>(text, depth - 1));
+                }
+                text += "]";
+                return array;
+            }
+            default:
+            {
+                Json object = Json::object();
+                text += "{";
+                const std::size_t n = size();
+                for (std::size_t i = 0; i < n; ++i)
+                {
+                    const std::string key = "k" + std::to_string(i);
+                    text += (i == 0 ? "\"" : ",\"") + key + "\":";
+                    object[key] = make<Json>(text, depth - 1);
+                }
+                text += "}";
+                return object;
+            }
+        }
+    }
+
+  private:
+    std::uint32_t next(const std::uint32_t bound)
+    {
+        state = state * 1664525U + 1013904223U;
+        return (state >> 8) % bound;
+    }
+
+    std::size_t size()
+    {
+        return container_sizes[next(sizeof(container_sizes) / sizeof(*container_sizes))];
+    }
+
+    std::uint32_t state;
+};
+} // namespace
+
+TEST_CASE("parsing random trees of arrays and objects")
+{
+    for (std::uint32_t seed = 1; seed <= 150; ++seed)
+    {
+        INFO("seed ", seed);
+
+        std::string text;
+        std::string ordered_text;
+        const json expected = tree_generator(seed).make<json>(text, 3);
+        const ordered_json ordered_expected = tree_generator(seed).make<ordered_json>(ordered_text, 3);
+        CHECK(text == ordered_text);
+
+        CHECK(json::parse(text) == expected);
+        CHECK(json::accept(text));
+        const ordered_json ordered = ordered_json::parse(text);
+        CHECK(ordered == ordered_expected);
+        CHECK(ordered.dump() == ordered_expected.dump());
+        CHECK(json::parse(text).dump() == expected.dump());
+    }
+}