Read CBOR containers and tags without recursing per nesting level

get_cbor_array() and get_cbor_object() read their elements by calling back
into the value reader, which called them again for a nested container, and a
tag was handled by reading the tagged value the same way. All three cost
native stack, and all three cost a single byte to encode: 0x9F opens an
indefinite-length array, 0x81 a one-element array, and 0xC2 is a tag. Half a
million of any of them crashes the process before the input runs out (#5104).

Apply the shape the MessagePack reader already uses: the open containers live
on the heap stack, parse_cbor_value() reads a single value and only opens a
container rather than reading it to its end, and parse_cbor_internal() loops,
resuming the innermost container after each element.

Two things are specific to CBOR. An indefinite-length container ends at a
break marker rather than at a count, and testing for that marker consumes a
byte which is the first byte of the next element when it is not one; the
frame's count is npos for those, and the driver tracks whether the next value
starts at a fresh byte. And a tag is not a value of its own: instead of
reading the tagged value by recursing, the value reader reports that a tag was
read and the driver reads on, so a chain of tags costs no stack at all.

The switch that decodes a value is unchanged apart from the twelve container
cases and the two tag sites. Verified against the previous commit over
definite and indefinite arrays and maps, all four counted forms, empty
containers, nesting of the forms inside each other, truncated inputs, and all
three tag handlers: identical values, error codes, messages and byte offsets.
500,000 levels of each of the three vectors now report parse_error.110 instead
of crashing, and a well-formed 200,000-level value is read to completion.

On performance: the driver does per element what a counted loop used to do
per container, and CBOR pays for it more than MessagePack because the value
reader also has to be told whether to fetch a byte. Parsing 60,000 small
objects and one array of a million integers is 3 to 4 % slower than the
recursive reader, measured over five alternating runs. Against develop the
same two inputs are about 44 % faster, because the entry point no longer
copies the value it parsed; the earlier commit in this series is what pays
for that.

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

docs/mkdocs/docs/features/binary_formats/ubjson.md

@@ -69,6 +69,12 @@ The library uses the following mapping from JSON values types to UBJSON types ac
     Note that `use_size = true` alone may result in larger representations - the benefit of this parameter is that the
     receiving side is immediately informed on the number of elements of the container.
 
+    An array whose type marker is `Z` (null), `T` (true) or `F` (false) stores no payload at all, because the marker
+    already is the value. Its declared count is therefore the only thing that decides how much memory the receiving side
+    allocates, and a handful of bytes can describe billions of elements. `from_ubjson` rejects such an array with
+    [`out_of_range.408`](../../home/exceptions.md#jsonexceptionout_of_range408) when the count exceeds 1,048,576, and
+    `to_ubjson` writes longer arrays of these types without the annotation, so any value it produces can be read back.
+
 !!! info "Binary values"
 
     If the JSON data contains the binary type, the value stored is a list of integers, as suggested by the UBJSON

docs/mkdocs/docs/home/exceptions.md

@@ -868,6 +868,12 @@ The size of an array or object in a [binary format](../features/binary_formats/i
 the size following `#` for [UBJSON](../features/binary_formats/ubjson.md)/[BJData](../features/binary_formats/bjdata.md),
 or the encoded length for [CBOR](../features/binary_formats/cbor.md).
 
+The exception is also thrown for a [UBJSON](../features/binary_formats/ubjson.md) array of a type that is encoded by its
+marker alone (`Z`, `T` or `F`) whose declared count exceeds 1,048,576. Such an array has no payload, so its count alone
+decides how much memory is allocated, and a handful of bytes would otherwise describe billions of values.
+[`to_ubjson`](../api/basic_json/to_ubjson.md) writes longer arrays of these types without the size and type annotation,
+so any value it produces can still be read back.
+
 !!! failure "Example messages"
 
     ```
@@ -879,6 +885,9 @@ or the encoded length for [CBOR](../features/binary_formats/cbor.md).
     ```
     [json.exception.out_of_range.408] syntax error while parsing CBOR size: excessive map size
     ```
+    ```
+    [json.exception.out_of_range.408] syntax error while parsing UBJSON size: excessive array size
+    ```
 
 ### json.exception.out_of_range.409
 

include/nlohmann/detail/input/binary_reader.hpp

@@ -58,6 +58,26 @@ inline bool little_endianness(int num = 1) noexcept
     return *reinterpret_cast<char*>(&num) == 1;
 }
 
+/*!
+@brief largest element count accepted for a UBJSON container of a valueless type
+
+An element of type 'Z' (null), 'T' (true) or 'F' (false) is encoded by its
+type marker alone, so an optimized container of one of those types has no
+payload at all and its declared count is the only thing that decides how much
+is allocated: `[$Z#L` followed by a large count turns some ten bytes of input
+into that many values (see #2793, which reports 35 GB and 150 seconds). Every
+other type costs at least one byte per element and is bounded by the end of
+the input.
+
+This is a sanity bound rather than a security boundary, and it is far above
+any container met in practice. @ref binary_writer falls back to the
+unoptimized encoding for longer containers, so that a value serialized by
+this library can always be read back.
+
+@sa https://github.com/nlohmann/json/issues/2793
+*/
+JSON_INLINE_VARIABLE constexpr std::size_t max_valueless_container_size = 1 << 20;
+
 ///////////////////
 // binary reader //
 ///////////////////
@@ -110,6 +130,7 @@ class binary_reader
                    const cbor_tag_handler_t tag_handler = cbor_tag_handler_t::error)
     {
         sax = sax_;
+        container_stack.clear();
         bool result = false;
 
         switch (format)
@@ -159,6 +180,57 @@ class binary_reader
     }
 
   private:
+    ////////////////////////
+    // nested containers  //
+    ////////////////////////
+
+    /*!
+    @brief a container that has been opened and not closed yet
+
+    The binary readers do not call themselves once per nesting level. Like
+    @ref parser::sax_parse_internal, which does the same for JSON text, they
+    keep the containers they are inside of on a heap-allocated stack, so that
+    the native call stack does not grow with the nesting depth of the input
+    and a deeply nested value is bounded by memory rather than by the stack
+    (see #5104).
+
+    The members are ordered widest first: frames are stored in a vector, and
+    declaring the `bool` first would pad the struct out for no reason.
+    */
+    struct container_frame
+    {
+        /// number of elements that have not been read yet
+        std::size_t remaining = 0;
+        /// whether to close this container with end_object() or end_array()
+        bool is_object = false;
+    };
+
+    /*!
+    @brief open a nested array or object
+
+    Emits the SAX start event and records the container. This is the only
+    place the binary readers start a container, so a check that rejects one
+    can be made here and is then guaranteed to run before the start event.
+
+    @param[in] is_object  whether an object (true) or an array (false) begins
+    @param[in] len        number of elements the container declares
+
+    @return whether the SAX parser accepted the start event
+    */
+    bool enter_container(const bool is_object, const std::size_t len)
+    {
+        if (JSON_HEDLEY_UNLIKELY(is_object ? !sax->start_object(len) : !sax->start_array(len)))
+        {
+            return false;
+        }
+
+        container_frame frame;
+        frame.remaining = len;
+        frame.is_object = is_object;
+        container_stack.push_back(frame);
+        return true;
+    }
+
     //////////
     // BSON //
     //////////
@@ -491,9 +563,12 @@ class binary_reader
 
     @return whether a valid CBOR value was passed to the SAX parser
     */
-    bool parse_cbor_internal(const bool get_char,
-                             const cbor_tag_handler_t tag_handler)
+    bool parse_cbor_value(const bool get_char,
+                          const cbor_tag_handler_t tag_handler,
+                          bool& tag_pending)
     {
+        tag_pending = false;
+
         switch (get_char ? get() : current)
         {
             // EOF
@@ -685,37 +760,37 @@ class binary_reader
             case 0x95:
             case 0x96:
             case 0x97:
-                return get_cbor_array(
-                           conditional_static_cast<std::size_t>(static_cast<unsigned int>(current) & 0x1Fu), tag_handler);
+                return enter_container(/*is_object*/false,
+                                                    conditional_static_cast<std::size_t>(static_cast<unsigned int>(current) & 0x1Fu));
 
             case 0x98: // array (one-byte uint8_t for n follows)
             {
                 std::uint8_t len{};
-                return get_number(input_format_t::cbor, len) && get_cbor_array(static_cast<std::size_t>(len), tag_handler);
+                return get_number(input_format_t::cbor, len) && enter_container(/*is_object*/false, static_cast<std::size_t>(len));
             }
 
             case 0x99: // array (two-byte uint16_t for n follow)
             {
                 std::uint16_t len{};
-                return get_number(input_format_t::cbor, len) && get_cbor_array(static_cast<std::size_t>(len), tag_handler);
+                return get_number(input_format_t::cbor, len) && enter_container(/*is_object*/false, static_cast<std::size_t>(len));
             }
 
             case 0x9A: // array (four-byte uint32_t for n follow)
             {
                 std::uint32_t len{};
                 std::size_t size{};
-                return get_number(input_format_t::cbor, len) && get_cbor_container_size(len, size, "array") && get_cbor_array(size, tag_handler);
+                return get_number(input_format_t::cbor, len) && get_cbor_container_size(len, size, "array") && enter_container(/*is_object*/false, size);
             }
 
             case 0x9B: // array (eight-byte uint64_t for n follow)
             {
                 std::uint64_t len{};
                 std::size_t size{};
-                return get_number(input_format_t::cbor, len) && get_cbor_container_size(len, size, "array") && get_cbor_array(size, tag_handler);
+                return get_number(input_format_t::cbor, len) && get_cbor_container_size(len, size, "array") && enter_container(/*is_object*/false, size);
             }
 
             case 0x9F: // array (indefinite length)
-                return get_cbor_array(detail::unknown_size(), tag_handler);
+                return enter_container(/*is_object*/false, detail::unknown_size());
 
             // map (0x00..0x17 pairs of data items follow)
             case 0xA0:
@@ -742,36 +817,36 @@ class binary_reader
             case 0xB5:
             case 0xB6:
             case 0xB7:
-                return get_cbor_object(conditional_static_cast<std::size_t>(static_cast<unsigned int>(current) & 0x1Fu), tag_handler);
+                return enter_container(/*is_object*/true, conditional_static_cast<std::size_t>(static_cast<unsigned int>(current) & 0x1Fu));
 
             case 0xB8: // map (one-byte uint8_t for n follows)
             {
                 std::uint8_t len{};
-                return get_number(input_format_t::cbor, len) && get_cbor_object(static_cast<std::size_t>(len), tag_handler);
+                return get_number(input_format_t::cbor, len) && enter_container(/*is_object*/true, static_cast<std::size_t>(len));
             }
 
             case 0xB9: // map (two-byte uint16_t for n follow)
             {
                 std::uint16_t len{};
-                return get_number(input_format_t::cbor, len) && get_cbor_object(static_cast<std::size_t>(len), tag_handler);
+                return get_number(input_format_t::cbor, len) && enter_container(/*is_object*/true, static_cast<std::size_t>(len));
             }
 
             case 0xBA: // map (four-byte uint32_t for n follow)
             {
                 std::uint32_t len{};
                 std::size_t size{};
-                return get_number(input_format_t::cbor, len) && get_cbor_container_size(len, size, "map") && get_cbor_object(size, tag_handler);
+                return get_number(input_format_t::cbor, len) && get_cbor_container_size(len, size, "map") && enter_container(/*is_object*/true, size);
             }
 
             case 0xBB: // map (eight-byte uint64_t for n follow)
             {
                 std::uint64_t len{};
                 std::size_t size{};
-                return get_number(input_format_t::cbor, len) && get_cbor_container_size(len, size, "map") && get_cbor_object(size, tag_handler);
+                return get_number(input_format_t::cbor, len) && get_cbor_container_size(len, size, "map") && enter_container(/*is_object*/true, size);
             }
 
             case 0xBF: // map (indefinite length)
-                return get_cbor_object(detail::unknown_size(), tag_handler);
+                return enter_container(/*is_object*/true, detail::unknown_size());
 
             case 0xC0: // tagged item
             case 0xC1:
@@ -855,7 +930,10 @@ class binary_reader
                             default:
                                 break;
                         }
-                        return parse_cbor_internal(true, tag_handler);
+                        // the tagged value follows; it is read by the loop in
+                        // parse_cbor_internal() rather than by recursing here
+                        tag_pending = true;
+                        return true;
                     }
 
                     case cbor_tag_handler_t::store:
@@ -905,7 +983,11 @@ class binary_reader
                                 break;
                             }
                             default:
-                                return parse_cbor_internal(true, tag_handler);
+                            {
+                                // as above, the tagged value is read by the caller
+                                tag_pending = true;
+                                return true;
+                            }
                         }
                         get();
                         return get_cbor_binary(b) && sax->binary(b);
@@ -996,23 +1078,21 @@ class binary_reader
     }
 
     /*!
-    @brief reads a CBOR string
+    @brief reads a definite-length CBOR string
 
-    This function first reads starting bytes to determine the expected
-    string length and then copies this number of bytes into a string.
-    Additionally, CBOR's strings with indefinite lengths are supported.
+    Reads everything @ref get_cbor_string accepts except the indefinite-length
+    form, which that function handles itself. The bytes are appended to @a
+    result, so consecutive chunks of an indefinite-length string can be read
+    into the same string.
 
-    @param[out] result  created string
+    @param[out] result  string the bytes are appended to
 
     @return whether string creation completed
-    */
-    bool get_cbor_string(string_t& result)
-    {
-        if (JSON_HEDLEY_UNLIKELY(!unexpect_eof(input_format_t::cbor, "string")))
-        {
-            return false;
-        }
 
+    @pre @a current is not EOF
+    */
+    bool get_cbor_string_chunk(string_t& result)
+    {
         switch (current)
         {
             // UTF-8 string (0x00..0x17 bytes follow)
@@ -1068,20 +1148,6 @@ class binary_reader
                 return get_number(input_format_t::cbor, len) && get_string(input_format_t::cbor, len, result);
             }
 
-            case 0x7F: // UTF-8 string (indefinite length)
-            {
-                while (get() != 0xFF)
-                {
-                    string_t chunk;
-                    if (!get_cbor_string(chunk))
-                    {
-                        return false;
-                    }
-                    result.append(chunk);
-                }
-                return true;
-            }
-
             default:
             {
                 auto last_token = get_token_string();
@@ -1092,23 +1158,82 @@ class binary_reader
     }
 
     /*!
-    @brief reads a CBOR byte array
+    @brief reads a CBOR string
 
     This function first reads starting bytes to determine the expected
-    byte array length and then copies this number of bytes into the byte array.
-    Additionally, CBOR's byte arrays with indefinite lengths are supported.
+    string length and then copies this number of bytes into a string.
+    Additionally, CBOR's strings with indefinite lengths are supported.
 
-    @param[out] result  created byte array
+    @param[out] result  created string
+
+    @return whether string creation completed
+    */
+    bool get_cbor_string(string_t& result)
+    {
+        // number of indefinite-length strings that have been opened and not
+        // closed yet. RFC 8949, Section 3.2.3 does not permit nesting them,
+        // but this reader has always accepted it, so the open levels are
+        // counted instead of recursed through, which overflowed the stack for
+        // an input of repeated 0x7F bytes (see #5104). Every chunk is appended
+        // to the same result, so no per-level state is needed.
+        std::size_t open = 0;
+
+        while (true)
+        {
+            if (JSON_HEDLEY_UNLIKELY(!unexpect_eof(input_format_t::cbor, "string")))
+            {
+                return false;
+            }
+
+            if (current == 0x7F) // UTF-8 string (indefinite length)
+            {
+                ++open;
+                get();
+                continue;
+            }
+
+            // a break marker closes the innermost indefinite-length string;
+            // outside of one it is not a string and falls through to the error
+            if (open != 0 && current == 0xFF)
+            {
+                if (--open == 0)
+                {
+                    return true;
+                }
+                get();
+                continue;
+            }
+
+            if (JSON_HEDLEY_UNLIKELY(!get_cbor_string_chunk(result)))
+            {
+                return false;
+            }
+
+            if (open == 0)
+            {
+                return true;
+            }
+
+            get();
+        }
+    }
+
+    /*!
+    @brief reads a definite-length CBOR byte array
+
+    Reads everything @ref get_cbor_binary accepts except the indefinite-length
+    form, which that function handles itself. The bytes are appended to @a
+    result, so consecutive chunks of an indefinite-length byte array can be
+    read into the same byte array.
+
+    @param[out] result  byte array the bytes are appended to
 
     @return whether byte array creation completed
-    */
-    bool get_cbor_binary(binary_t& result)
-    {
-        if (JSON_HEDLEY_UNLIKELY(!unexpect_eof(input_format_t::cbor, "binary")))
-        {
-            return false;
-        }
 
+    @pre @a current is not EOF
+    */
+    bool get_cbor_binary_chunk(binary_t& result)
+    {
         switch (current)
         {
             // Binary data (0x00..0x17 bytes follow)
@@ -1168,20 +1293,6 @@ class binary_reader
                        get_binary(input_format_t::cbor, len, result);
             }
 
-            case 0x5F: // Binary data (indefinite length)
-            {
-                while (get() != 0xFF)
-                {
-                    binary_t chunk;
-                    if (!get_cbor_binary(chunk))
-                    {
-                        return false;
-                    }
-                    result.insert(result.end(), chunk.begin(), chunk.end());
-                }
-                return true;
-            }
-
             default:
             {
                 auto last_token = get_token_string();
@@ -1191,6 +1302,63 @@ class binary_reader
         }
     }
 
+    /*!
+    @brief reads a CBOR byte array
+
+    This function first reads starting bytes to determine the expected
+    byte array length and then copies this number of bytes into the byte array.
+    Additionally, CBOR's byte arrays with indefinite lengths are supported.
+
+    @param[out] result  created byte array
+
+    @return whether byte array creation completed
+    */
+    bool get_cbor_binary(binary_t& result)
+    {
+        // the open indefinite-length byte arrays are counted rather than
+        // recursed through, for the reason given in @ref get_cbor_string
+        std::size_t open = 0;
+
+        while (true)
+        {
+            if (JSON_HEDLEY_UNLIKELY(!unexpect_eof(input_format_t::cbor, "binary")))
+            {
+                return false;
+            }
+
+            if (current == 0x5F) // Binary data (indefinite length)
+            {
+                ++open;
+                get();
+                continue;
+            }
+
+            // a break marker closes the innermost indefinite-length byte
+            // array; outside of one it falls through to the error below
+            if (open != 0 && current == 0xFF)
+            {
+                if (--open == 0)
+                {
+                    return true;
+                }
+                get();
+                continue;
+            }
+
+            if (JSON_HEDLEY_UNLIKELY(!get_cbor_binary_chunk(result)))
+            {
+                return false;
+            }
+
+            if (open == 0)
+            {
+                return true;
+            }
+
+            get();
+        }
+    }
+
     /*!
     @brief narrow a definite CBOR array/map length to std::size_t
 
@@ -1217,96 +1385,110 @@ class binary_reader
     }
 
     /*!
-    @param[in] len  the length of the array or detail::unknown_size() for an
-                    array of indefinite size
+    @brief read a CBOR value and everything nested inside it
+
+    Reads values until the one that was begun here is complete, resuming the
+    enclosing container after each element, so that the nesting depth of the
+    input costs heap rather than native stack (see #5104).
+
+    @param[in] get_char  whether a new character should be retrieved from the
+                         input (true) or whether the last read character
+                         @a current should be considered instead
     @param[in] tag_handler how CBOR tags should be treated
-    @return whether array creation completed
+
+    @return whether reading the value succeeded
     */
-    bool get_cbor_array(const std::size_t len,
-                        const cbor_tag_handler_t tag_handler)
+    bool parse_cbor_internal(const bool get_char,
+                             const cbor_tag_handler_t tag_handler)
     {
-        if (JSON_HEDLEY_UNLIKELY(!sax->start_array(len)))
-        {
-            return false;
-        }
+        // whether the next value starts at a fresh byte or at the one already
+        // read into `current`
+        bool fetch = get_char;
 
-        if (len != detail::unknown_size())
+        // the key currently being read; hoisted out of the loop so that its
+        // capacity is reused across elements and across nesting levels
+        string_t key;
+
+        while (true)
         {
-            for (std::size_t i = 0; i < len; ++i)
+            if (!container_stack.empty())
             {
-                if (JSON_HEDLEY_UNLIKELY(!parse_cbor_internal(true, tag_handler)))
+                // the reference is not held across parse_cbor_value() below,
+                // which can push onto the stack and reallocate it
+                container_frame& top = container_stack.back();
+                bool at_end;
+
+                if (top.remaining != npos)
                 {
-                    return false;
+                    // definite length: the container ends once its elements
+                    // have been read
+                    at_end = (top.remaining == 0);
+                    if (!at_end)
+                    {
+                        // claim the element about to be read
+                        --top.remaining;
+                        if (top.is_object)
+                        {
+                            get();
+                        }
+                    }
+                    fetch = true;
                 }
-            }
-        }
-        else
-        {
-            while (get() != 0xFF)
-            {
-                if (JSON_HEDLEY_UNLIKELY(!parse_cbor_internal(false, tag_handler)))
+                else
                 {
-                    return false;
+                    // indefinite length: the container ends at a break marker.
+                    // Testing for it consumes a byte, which is the first byte
+                    // of the next element when it is not one.
+                    at_end = (get() == 0xFF);
+                    fetch = top.is_object;
                 }
-            }
-        }
 
-        return sax->end_array();
-    }
-
-    /*!
-    @param[in] len  the length of the object or detail::unknown_size() for an
-                    object of indefinite size
-    @param[in] tag_handler how CBOR tags should be treated
-    @return whether object creation completed
-    */
-    bool get_cbor_object(const std::size_t len,
-                         const cbor_tag_handler_t tag_handler)
-    {
-        if (JSON_HEDLEY_UNLIKELY(!sax->start_object(len)))
-        {
-            return false;
-        }
-
-        if (len != 0)
-        {
-            string_t key;
-            if (len != detail::unknown_size())
-            {
-                for (std::size_t i = 0; i < len; ++i)
+                if (at_end)
                 {
-                    get();
+                    const bool is_object = top.is_object;
+                    container_stack.pop_back();
+                    if (JSON_HEDLEY_UNLIKELY(is_object ? !sax->end_object() : !sax->end_array()))
+                    {
+                        return false;
+                    }
+                    // the value begun here is complete once its container is
+                    if (container_stack.empty())
+                    {
+                        return true;
+                    }
+                    continue;
+                }
+
+                if (top.is_object)
+                {
+                    key.clear();
                     if (JSON_HEDLEY_UNLIKELY(!get_cbor_string(key) || !sax->key(key)))
                     {
                         return false;
                     }
-
-                    if (JSON_HEDLEY_UNLIKELY(!parse_cbor_internal(true, tag_handler)))
-                    {
-                        return false;
-                    }
-                    key.clear();
+                    fetch = true;
                 }
             }
-            else
-            {
-                while (get() != 0xFF)
-                {
-                    if (JSON_HEDLEY_UNLIKELY(!get_cbor_string(key) || !sax->key(key)))
-                    {
-                        return false;
-                    }
 
-                    if (JSON_HEDLEY_UNLIKELY(!parse_cbor_internal(true, tag_handler)))
-                    {
-                        return false;
-                    }
-                    key.clear();
+            // a tag is not a value of its own: read on until the tagged value
+            bool tag_pending;
+            do
+            {
+                if (JSON_HEDLEY_UNLIKELY(!parse_cbor_value(fetch, tag_handler, tag_pending)))
+                {
+                    return false;
                 }
+                fetch = true;
+            }
+            while (tag_pending);
+
+            // a value that opened a container left it on the stack; one that
+            // did not, and that was not inside a container, was the whole value
+            if (container_stack.empty())
+            {
+                return true;
             }
         }
-
-        return sax->end_object();
     }
 
     /////////////
@@ -1316,7 +1498,17 @@ class binary_reader
     /*!
     @return whether a valid MessagePack value was passed to the SAX parser
     */
-    bool parse_msgpack_internal()
+    /*!
+    @brief read one MessagePack value
+
+    Reads a single value and passes it to the SAX parser. A value that begins
+    a container is not read to its end: the container is opened with
+    @ref enter_container and its elements are read by
+    @ref parse_msgpack_internal, so that nesting does not consume native stack.
+
+    @return whether reading the value succeeded
+    */
+    bool parse_msgpack_value()
     {
         switch (get())
         {
@@ -1472,7 +1664,7 @@ class binary_reader
             case 0x8D:
             case 0x8E:
             case 0x8F:
-                return get_msgpack_object(conditional_static_cast<std::size_t>(static_cast<unsigned int>(current) & 0x0Fu));
+                return enter_container(/*is_object*/true, conditional_static_cast<std::size_t>(static_cast<unsigned int>(current) & 0x0Fu));
 
             // fixarray
             case 0x90:
@@ -1491,7 +1683,7 @@ class binary_reader
             case 0x9D:
             case 0x9E:
             case 0x9F:
-                return get_msgpack_array(conditional_static_cast<std::size_t>(static_cast<unsigned int>(current) & 0x0Fu));
+                return enter_container(/*is_object*/false, conditional_static_cast<std::size_t>(static_cast<unsigned int>(current) & 0x0Fu));
 
             // fixstr
             case 0xA0:
@@ -1622,25 +1814,25 @@ class binary_reader
             case 0xDC: // array 16
             {
                 std::uint16_t len{};
-                return get_number(input_format_t::msgpack, len) && get_msgpack_array(static_cast<std::size_t>(len));
+                return get_number(input_format_t::msgpack, len) && enter_container(/*is_object*/false, static_cast<std::size_t>(len));
             }
 
             case 0xDD: // array 32
             {
                 std::uint32_t len{};
-                return get_number(input_format_t::msgpack, len) && get_msgpack_array(conditional_static_cast<std::size_t>(len));
+                return get_number(input_format_t::msgpack, len) && enter_container(/*is_object*/false, conditional_static_cast<std::size_t>(len));
             }
 
             case 0xDE: // map 16
             {
                 std::uint16_t len{};
-                return get_number(input_format_t::msgpack, len) && get_msgpack_object(static_cast<std::size_t>(len));
+                return get_number(input_format_t::msgpack, len) && enter_container(/*is_object*/true, static_cast<std::size_t>(len));
             }
 
             case 0xDF: // map 32
             {
                 std::uint32_t len{};
-                return get_number(input_format_t::msgpack, len) && get_msgpack_object(conditional_static_cast<std::size_t>(len));
+                return get_number(input_format_t::msgpack, len) && enter_container(/*is_object*/true, conditional_static_cast<std::size_t>(len));
             }
 
             // negative fixint
@@ -1888,55 +2080,69 @@ class binary_reader
     }
 
     /*!
-    @param[in] len  the length of the array
-    @return whether array creation completed
+    @brief read a MessagePack value and everything nested inside it
+
+    Reads values until the one that was begun here is complete, resuming the
+    enclosing container each time an element ends, so that the nesting depth
+    of the input costs heap rather than native stack (see #5104).
+
+    @return whether reading the value succeeded
     */
-    bool get_msgpack_array(const std::size_t len)
+    bool parse_msgpack_internal()
     {
-        if (JSON_HEDLEY_UNLIKELY(!sax->start_array(len)))
-        {
-            return false;
-        }
-
-        for (std::size_t i = 0; i < len; ++i)
-        {
-            if (JSON_HEDLEY_UNLIKELY(!parse_msgpack_internal()))
-            {
-                return false;
-            }
-        }
-
-        return sax->end_array();
-    }
-
-    /*!
-    @param[in] len  the length of the object
-    @return whether object creation completed
-    */
-    bool get_msgpack_object(const std::size_t len)
-    {
-        if (JSON_HEDLEY_UNLIKELY(!sax->start_object(len)))
-        {
-            return false;
-        }
-
+        // the key currently being read; hoisted out of the loop so that its
+        // capacity is reused across elements and across nesting levels
         string_t key;
-        for (std::size_t i = 0; i < len; ++i)
+
+        while (true)
         {
-            get();
-            if (JSON_HEDLEY_UNLIKELY(!get_msgpack_string(key) || !sax->key(key)))
+            if (!container_stack.empty())
+            {
+                // copied out before anything can push onto the stack and
+                // invalidate a reference into it
+                const bool is_object = container_stack.back().is_object;
+
+                if (container_stack.back().remaining == 0)
+                {
+                    container_stack.pop_back();
+                    if (JSON_HEDLEY_UNLIKELY(is_object ? !sax->end_object() : !sax->end_array()))
+                    {
+                        return false;
+                    }
+                    // the value begun here is complete once its container is
+                    if (container_stack.empty())
+                    {
+                        return true;
+                    }
+                    continue;
+                }
+
+                // claim the element about to be read
+                --container_stack.back().remaining;
+
+                if (is_object)
+                {
+                    get();
+                    key.clear();
+                    if (JSON_HEDLEY_UNLIKELY(!get_msgpack_string(key) || !sax->key(key)))
+                    {
+                        return false;
+                    }
+                }
+            }
+
+            if (JSON_HEDLEY_UNLIKELY(!parse_msgpack_value()))
             {
                 return false;
             }
 
-            if (JSON_HEDLEY_UNLIKELY(!parse_msgpack_internal()))
+            // a value that opened a container left it on the stack; one that
+            // did not, and that was not inside a container, was the whole value
+            if (container_stack.empty())
             {
-                return false;
+                return true;
             }
-            key.clear();
         }
-
-        return sax->end_object();
     }
 
     ////////////
@@ -2391,7 +2597,12 @@ class binary_reader
     {
         result.first = npos; // size
         result.second = 0; // type
-        bool is_ndarray = false;
+        // seed the flag with the caller's context: inside an ndarray dimension
+        // vector another ndarray is not allowed, and get_ubjson_size_value()
+        // rejects it up front instead of reading it and reporting afterwards.
+        // Seeding it with `false` made every '#' of a "[#[#[..." chain descend
+        // another level, which overflowed the stack (see #5104).
+        bool is_ndarray = inside_ndarray;
 
         get_ignore_noop();
 
@@ -2424,13 +2635,11 @@ class binary_reader
             }
 
             const bool is_error = get_ubjson_size_value(result.first, is_ndarray);
-            if (input_format == input_format_t::bjdata && is_ndarray)
+            // an ndarray was read here only if the flag flipped; when it was
+            // seeded true, get_ubjson_size_value() already rejected the nested
+            // dimension vector
+            if (input_format == input_format_t::bjdata && is_ndarray && !inside_ndarray)
             {
-                if (inside_ndarray)
-                {
-                    return sax->parse_error(chars_read, get_token_string(), parse_error::create(112, chars_read,
-                                            exception_message(input_format, "ndarray can not be recursive", "size"), nullptr));
-                }
                 result.second |= (1 << 8); // use bit 8 to indicate ndarray, all UBJSON and BJData markers should be ASCII letters
             }
             return is_error;
@@ -2439,7 +2648,7 @@ class binary_reader
         if (current == '#')
         {
             const bool is_error = get_ubjson_size_value(result.first, is_ndarray);
-            if (input_format == input_format_t::bjdata && is_ndarray)
+            if (input_format == input_format_t::bjdata && is_ndarray && !inside_ndarray)
             {
                 return sax->parse_error(chars_read, get_token_string(), parse_error::create(112, chars_read,
                                         exception_message(input_format, "ndarray requires both type and size", "size"), nullptr));
@@ -2710,6 +2919,17 @@ class binary_reader
 
         if (size_and_type.first != npos)
         {
+            // reading an element of a valueless type consumes no input, so the
+            // declared count alone decides how much is allocated; the check is
+            // made before the start event so that no container is opened that
+            // is then abandoned. See @ref max_valueless_container_size.
+            if (JSON_HEDLEY_UNLIKELY((size_and_type.second == 'Z' || size_and_type.second == 'T' || size_and_type.second == 'F')
+                                     && size_and_type.first > max_valueless_container_size))
+            {
+                return sax->parse_error(chars_read, get_token_string(), out_of_range::create(408,
+                                        exception_message(input_format, "excessive array size", "size"), nullptr));
+            }
+
             if (JSON_HEDLEY_UNLIKELY(!sax->start_array(size_and_type.first)))
             {
                 return false;
@@ -3227,6 +3447,9 @@ class binary_reader
     /// the SAX parser
     json_sax_t* sax = nullptr;
 
+    /// the containers that have been opened and not closed yet; see @ref container_frame
+    std::vector<container_frame> container_stack{};
+
     // excluded markers in bjdata optimized type
 #define JSON_BINARY_READER_MAKE_BJD_OPTIMIZED_TYPE_MARKERS_ \
     make_array<char_int_type>('F', 'H', 'N', 'S', 'T', 'Z', '[', '{')

include/nlohmann/detail/input/json_sax.hpp

@@ -8,11 +8,10 @@
 
 #pragma once
 
-#include <algorithm> // find_if
 #include <cstddef>
 #include <string> // string
 #include <type_traits> // enable_if_t
-#include <utility> // move, pair
+#include <utility> // move
 #include <vector> // vector
 
 #include <nlohmann/detail/exceptions.hpp>
@@ -250,7 +249,7 @@ class json_sax_dom_parser
 
         if (JSON_HEDLEY_UNLIKELY(len != detail::unknown_size() && len > ref_stack.back()->max_size()))
         {
-            return parse_error(0, "", out_of_range::create(408, concat("excessive object size: ", std::to_string(len)), ref_stack.back()));
+            JSON_THROW(out_of_range::create(408, concat("excessive object size: ", std::to_string(len)), ref_stack.back()));
         }
 
         return true;
@@ -299,7 +298,7 @@ class json_sax_dom_parser
 
         if (JSON_HEDLEY_UNLIKELY(len != detail::unknown_size() && len > ref_stack.back()->max_size()))
         {
-            return parse_error(0, "", out_of_range::create(408, concat("excessive array size: ", std::to_string(len)), ref_stack.back()));
+            JSON_THROW(out_of_range::create(408, concat("excessive array size: ", std::to_string(len)), ref_stack.back()));
         }
 
         return true;
@@ -569,7 +568,7 @@ class json_sax_dom_callback_parser
             // check object limit
             if (JSON_HEDLEY_UNLIKELY(len != detail::unknown_size() && len > ref_stack.back()->max_size()))
             {
-                return parse_error(0, "", out_of_range::create(408, concat("excessive object size: ", std::to_string(len)), ref_stack.back()));
+                JSON_THROW(out_of_range::create(408, concat("excessive object size: ", std::to_string(len)), ref_stack.back()));
             }
         }
         return true;
@@ -586,17 +585,7 @@ class json_sax_dom_callback_parser
         // add discarded value at the given key and store the reference for later
         if (keep && ref_stack.back())
         {
-            auto& obj = *ref_stack.back()->m_data.m_value.object;
-            const auto it = obj.find(val);
-            if (it != obj.end())
-            {
-                // this is a duplicate key (legal in JSON); remember its
-                // current value so it can be restored later if the new
-                // value is rejected by the callback, instead of being
-                // erased together with the discarded placeholder
-                duplicate_key_stash.emplace_back(&(it->second), it->second);
-            }
-            object_element = &(obj[val] = discarded);
+            object_element = &(ref_stack.back()->m_data.m_value.object->operator[](val) = discarded);
         }
 
         return true;
@@ -608,18 +597,13 @@ class json_sax_dom_callback_parser
         {
             if (!callback(static_cast<int>(ref_stack.size()) - 1, parse_event_t::object_end, *ref_stack.back()))
             {
-                // discard object, unless this slot holds a duplicate key's
-                // previous value pending restoration, in which case that
-                // value is restored instead of being discarded
-                if (!resolve_duplicate_key_stash(ref_stack.back(), true))
-                {
-                    *ref_stack.back() = discarded;
+                // discard object
+                *ref_stack.back() = discarded;
 
 #if JSON_DIAGNOSTIC_POSITIONS
-                    // Set start/end positions for discarded object.
-                    handle_diagnostic_positions_for_json_value(*ref_stack.back());
+                // Set start/end positions for discarded object.
+                handle_diagnostic_positions_for_json_value(*ref_stack.back());
 #endif
-                }
             }
             else
             {
@@ -633,10 +617,6 @@ class json_sax_dom_callback_parser
 #endif
 
                 ref_stack.back()->set_parents();
-                // this object is finally, definitively kept; drop any
-                // pending duplicate-key stash entry for its slot since it
-                // can no longer be restored
-                resolve_duplicate_key_stash(ref_stack.back(), false);
             }
         }
 
@@ -679,7 +659,7 @@ class json_sax_dom_callback_parser
             // check array limit
             if (JSON_HEDLEY_UNLIKELY(len != detail::unknown_size() && len > ref_stack.back()->max_size()))
             {
-                return parse_error(0, "", out_of_range::create(408, concat("excessive array size: ", std::to_string(len)), ref_stack.back()));
+                JSON_THROW(out_of_range::create(408, concat("excessive array size: ", std::to_string(len)), ref_stack.back()));
             }
         }
 
@@ -706,25 +686,16 @@ class json_sax_dom_callback_parser
 #endif
 
                 ref_stack.back()->set_parents();
-                // this array is finally, definitively kept; drop any
-                // pending duplicate-key stash entry for its slot since it
-                // can no longer be restored
-                resolve_duplicate_key_stash(ref_stack.back(), false);
             }
             else
             {
-                // discard array, unless this slot holds a duplicate key's
-                // previous value pending restoration, in which case that
-                // value is restored instead of being discarded
-                if (!resolve_duplicate_key_stash(ref_stack.back(), true))
-                {
-                    *ref_stack.back() = discarded;
+                // discard array
+                *ref_stack.back() = discarded;
 
 #if JSON_DIAGNOSTIC_POSITIONS
-                    // Set start/end positions for discarded array.
-                    handle_diagnostic_positions_for_json_value(*ref_stack.back());
+                // Set start/end positions for discarded array.
+                handle_diagnostic_positions_for_json_value(*ref_stack.back());
 #endif
-                }
             }
         }
 
@@ -838,48 +809,14 @@ class json_sax_dom_callback_parser
     }
 #endif
 
-    /// if there is a pending duplicate-key stash entry for this exact slot,
-    /// remove it from the stash; if restore_value is true, the stashed
-    /// previous value is moved back into the slot first (use this when the
-    /// new value at that slot was rejected); otherwise the stash entry is
-    /// simply dropped (use this when the new value was accepted, so it
-    /// correctly supersedes the old one and no restore should ever happen
-    /// for this slot again)
-    /// @return whether a matching stash entry was found (and processed)
-    bool resolve_duplicate_key_stash(BasicJsonType* slot, bool restore_value)
-    {
-        const auto it = std::find_if(duplicate_key_stash.begin(), duplicate_key_stash.end(),
-                                     [slot](const std::pair<BasicJsonType*, BasicJsonType>& entry)
-        {
-            return entry.first == slot;
-        });
-
-        if (it == duplicate_key_stash.end())
-        {
-            return false;
-        }
-
-        if (restore_value)
-        {
-            *slot = std::move(it->second);
-        }
-        duplicate_key_stash.erase(it);
-        return true;
-    }
-
-    /// remove the discarded value the callback rejected from its parent,
-    /// unless it is a duplicate key's slot with a stashed previous value,
-    /// in which case that previous value is restored instead
-    void remove_discarded_value(BasicJsonType& parent)
+    /// remove the discarded value the callback rejected from its parent
+    static void remove_discarded_value(BasicJsonType& parent)
     {
         for (auto it = parent.begin(); it != parent.end(); ++it)
         {
             if (it->is_discarded())
             {
-                if (!resolve_duplicate_key_stash(&(*it), true))
-                {
-                    parent.erase(it);
-                }
+                parent.erase(it);
                 break;
             }
         }
@@ -977,16 +914,6 @@ class json_sax_dom_callback_parser
 
         JSON_ASSERT(object_element);
         *object_element = std::move(value);
-        if (!skip_callback)
-        {
-            // this scalar value finally, definitively replaces whatever was
-            // at this slot; drop any pending duplicate-key stash entry for
-            // it since it can no longer be restored (a container value at
-            // this slot is resolved later, in end_object()/end_array(),
-            // since skip_callback is true for the placeholder handling that
-            // happens here for those)
-            resolve_duplicate_key_stash(object_element, false);
-        }
         return {true, object_element};
     }
 
@@ -1000,12 +927,6 @@ class json_sax_dom_callback_parser
     std::vector<bool> key_keep_stack {}; // NOLINT(readability-redundant-member-init)
     /// helper to hold the reference for the next object element
     BasicJsonType* object_element = nullptr;
-    /// stash of (slot pointer, previous value) for object members that
-    /// already existed when key() was called again for the same key
-    /// (duplicate keys); used to restore the previous value if the new
-    /// value is later rejected by the callback, instead of erasing the
-    /// member entirely
-    std::vector<std::pair<BasicJsonType*, BasicJsonType>> duplicate_key_stash {};
     /// whether a syntax error occurred
     bool errored = false;
     /// callback function

include/nlohmann/detail/output/binary_writer.hpp

@@ -826,7 +826,17 @@ class binary_writer
 
                     std::vector<CharType> bjdx = {'[', '{', 'S', 'H', 'T', 'F', 'N', 'Z'}; // excluded markers in bjdata optimized type
 
-                    if (same_prefix && !(use_bjdata && std::find(bjdx.begin(), bjdx.end(), first_prefix) != bjdx.end()))
+                    // an optimized array of a valueless type carries no payload, so a
+                    // reader has nothing but the declared count to bound the allocation
+                    // by and refuses an excessive one. Write the unoptimized form for
+                    // those, at one byte per element, so the result can be read back.
+                    // Objects are not affected: every element is preceded by its key.
+                    const bool valueless_type = (first_prefix == 'Z' || first_prefix == 'T' || first_prefix == 'F');
+                    const bool excessive_valueless = valueless_type
+                                                     && j.m_data.m_value.array->size() > detail::max_valueless_container_size;
+
+                    if (same_prefix && !excessive_valueless
+                            && !(use_bjdata && std::find(bjdx.begin(), bjdx.end(), first_prefix) != bjdx.end()))
                     {
                         prefix_required = false;
                         oa->write_character(to_char_type('$'));

include/nlohmann/json.hpp

@@ -3573,7 +3573,6 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         {
             using std::swap;
             swap(*(m_data.m_value.array), other);
-            set_parents();
         }
         else
         {
@@ -3590,7 +3589,6 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         {
             using std::swap;
             swap(*(m_data.m_value.object), other);
-            set_parents();
         }
         else
         {
@@ -4476,7 +4474,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         auto ia = detail::input_adapter(std::forward<InputType>(i));
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::cbor).sax_parse(input_format_t::cbor, &sdp, strict, tag_handler); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
 
     /// @brief create a JSON value from an input in CBOR format (iterator pair, or iterator+sentinel pair for C++20 ranges support)
@@ -4493,7 +4491,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         auto ia = detail::input_adapter(std::move(first), std::move(last));
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::cbor).sax_parse(input_format_t::cbor, &sdp, strict, tag_handler); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
 
     template<typename T>
@@ -4519,7 +4517,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         // NOLINTNEXTLINE(hicpp-move-const-arg,performance-move-const-arg)
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::cbor).sax_parse(input_format_t::cbor, &sdp, strict, tag_handler); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
 
     /// @brief create a JSON value from an input in MessagePack format
@@ -4534,7 +4532,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         auto ia = detail::input_adapter(std::forward<InputType>(i));
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::msgpack).sax_parse(input_format_t::msgpack, &sdp, strict); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
 
     /// @brief create a JSON value from an input in MessagePack format (iterator pair, or iterator+sentinel pair for C++20 ranges support)
@@ -4550,7 +4548,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         auto ia = detail::input_adapter(std::move(first), std::move(last));
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::msgpack).sax_parse(input_format_t::msgpack, &sdp, strict); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
 
     template<typename T>
@@ -4574,7 +4572,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         // NOLINTNEXTLINE(hicpp-move-const-arg,performance-move-const-arg)
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::msgpack).sax_parse(input_format_t::msgpack, &sdp, strict); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
 
     /// @brief create a JSON value from an input in UBJSON format
@@ -4589,7 +4587,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         auto ia = detail::input_adapter(std::forward<InputType>(i));
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::ubjson).sax_parse(input_format_t::ubjson, &sdp, strict); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
 
     /// @brief create a JSON value from an input in UBJSON format (iterator pair, or iterator+sentinel pair for C++20 ranges support)
@@ -4605,7 +4603,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         auto ia = detail::input_adapter(std::move(first), std::move(last));
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::ubjson).sax_parse(input_format_t::ubjson, &sdp, strict); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
 
     template<typename T>
@@ -4629,7 +4627,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         // NOLINTNEXTLINE(hicpp-move-const-arg,performance-move-const-arg)
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::ubjson).sax_parse(input_format_t::ubjson, &sdp, strict); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
 
     /// @brief create a JSON value from an input in BJData format
@@ -4644,7 +4642,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         auto ia = detail::input_adapter(std::forward<InputType>(i));
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::bjdata).sax_parse(input_format_t::bjdata, &sdp, strict); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
 
     /// @brief create a JSON value from an input in BJData format (iterator pair, or iterator+sentinel pair for C++20 ranges support)
@@ -4660,7 +4658,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         auto ia = detail::input_adapter(std::move(first), std::move(last));
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::bjdata).sax_parse(input_format_t::bjdata, &sdp, strict); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
 
     /// @brief create a JSON value from an input in BSON format
@@ -4675,7 +4673,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         auto ia = detail::input_adapter(std::forward<InputType>(i));
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::bson).sax_parse(input_format_t::bson, &sdp, strict); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
 
     /// @brief create a JSON value from an input in BSON format (iterator pair, or iterator+sentinel pair for C++20 ranges support)
@@ -4691,7 +4689,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         auto ia = detail::input_adapter(std::move(first), std::move(last));
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::bson).sax_parse(input_format_t::bson, &sdp, strict); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
 
     template<typename T>
@@ -4715,7 +4713,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         detail::json_sax_dom_parser<basic_json, decltype(ia)> sdp(result, allow_exceptions);
         // NOLINTNEXTLINE(hicpp-move-const-arg,performance-move-const-arg)
         const bool res = binary_reader<decltype(ia)>(std::move(ia), input_format_t::bson).sax_parse(input_format_t::bson, &sdp, strict); // cppcheck-suppress[accessMoved]
-        return res ? result : basic_json(value_t::discarded);
+        return res ? std::move(result) : basic_json(value_t::discarded);
     }
     /// @}
 
@@ -5159,139 +5157,34 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
             case value_t::object:
             {
-                // first pass: record, for every source key, whether it is
-                // common to both objects (in source's iteration order) or
-                // was deleted (i.e., in source but not in target) -- this is
-                // a by-product of the target.find() call already needed to
-                // tell the two cases apart, so it adds no extra lookups. The
-                // "remove" ops themselves are emitted later, interleaved
-                // with the recursive per-key diffs in the fast path below,
-                // to match source's original iteration order (as the
-                // original, pre-reordering-aware implementation did) instead
-                // of grouping all removes before all recursive diffs.
-                std::vector<typename object_t::key_type> common_keys_source_order;
+                // first pass: traverse this object's elements
                 for (auto it = source.cbegin(); it != source.cend(); ++it)
                 {
+                    // escape the key name to be used in a JSON patch
+                    const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+
                     if (target.find(it.key()) != target.end())
                     {
-                        common_keys_source_order.push_back(it.key());
-                    }
-                }
-
-                // second pass: find keys that were added (i.e., in target but
-                // not in source), and record the keys common to both, in
-                // target's iteration order -- again a by-product of the
-                // source.find() call already needed to detect added keys. At
-                // the same time, determine whether every added key comes
-                // after every common key in target's order (a precondition
-                // for the fast path below, which only ever appends new keys
-                // at the very end): for an object_t whose iteration order is
-                // a pure function of the key set (e.g. the default std::map,
-                // which always iterates in sorted key order), the order
-                // check further below is always true and this whole
-                // mechanism is effectively a no-op; it only matters for a
-                // reorderable object_t such as the one backing `ordered_json`.
-                // patch ops for keys that were added (i.e., in target but not
-                // in source); built here so the fast path below can reuse
-                // them without a second source.find() per target key. Only
-                // used by the fast path -- the slow (reordering) path
-                // rebuilds "add" ops for every key itself.
-                std::vector<typename object_t::key_type> common_keys_target_order;
-                basic_json added_ops(value_t::array);
-                bool new_keys_form_suffix = true;
-                bool seen_new_key = false;
-                for (auto it = target.cbegin(); it != target.cend(); ++it)
-                {
-                    if (source.find(it.key()) == source.end())
-                    {
-                        seen_new_key = true;
-                        const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
-                        added_ops.push_back(
-                        {
-                            {"op", "add"}, {"path", path_key},
-                            {"value", it.value()}
-                        });
+                        // recursive call to compare object values at key it
+                        auto temp_diff = diff(it.value(), target[it.key()], path_key);
+                        result.insert(result.end(), temp_diff.begin(), temp_diff.end());
                     }
                     else
                     {
-                        common_keys_target_order.push_back(it.key());
-                        if (seen_new_key)
-                        {
-                            new_keys_form_suffix = false;
-                        }
-                    }
-                }
-
-                if (common_keys_source_order == common_keys_target_order && new_keys_form_suffix)
-                {
-                    // fast path: order of common keys already matches (or the
-                    // object_t's iteration order does not depend on
-                    // insertion history), so a plain per-key recursive diff
-                    // is correct and minimal, as before. common_keys_source_order
-                    // is, by construction, the subsequence of source's keys
-                    // that are common to both objects, in source's iteration
-                    // order -- so it can be walked in lockstep with `source`
-                    // using a cheap key comparison instead of another lookup.
-                    // Deleted keys (those source keys not in common_keys_source_order)
-                    // are interleaved here too, in source's original order, to
-                    // match the historical (pre-reordering-aware) output order.
-                    auto common_it = common_keys_source_order.cbegin();
-                    for (auto it = source.cbegin(); it != source.cend(); ++it)
-                    {
-                        if (common_it != common_keys_source_order.cend() && it.key() == *common_it)
-                        {
-                            const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
-                            auto temp_diff = diff(it.value(), target[it.key()], path_key);
-                            result.insert(result.end(), temp_diff.begin(), temp_diff.end());
-                            ++common_it;
-                        }
-                        else
-                        {
-                            // found a key that is not in target -> remove it
-                            const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
-                            result.push_back(object(
-                            {
-                                {"op", "remove"}, {"path", path_key}
-                            }));
-                        }
-                    }
-
-                    // append the "add" ops for brand-new keys collected above
-                    // during the pass over target -- no second source.find()
-                    // per target key needed
-                    result.insert(result.end(), added_ops.begin(), added_ops.end());
-                }
-                else
-                {
-                    // slow path: the common keys are in a different relative
-                    // order in source and target (only possible for a
-                    // reorderable object_t like ordered_map). Building a
-                    // minimal reordering patch is a nontrivial (LCS-like)
-                    // problem; instead, remove every source key -- both
-                    // deleted keys (which must be removed regardless) and
-                    // common keys (removed so they can be re-added in
-                    // target's order) -- and re-add every key that should
-                    // remain, with its final target value, in target's
-                    // order. basic_json::patch()'s "add" operation on an
-                    // object uses operator[], which appends at the end for a
-                    // vector-backed insertion-ordered map when the key does
-                    // not already exist -- so removing a key and then adding
-                    // it moves it to the end, fixing its position.
-                    for (auto it = source.cbegin(); it != source.cend(); ++it)
-                    {
-                        const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
+                        // found a key that is not in o -> remove it
                         result.push_back(object(
                         {
                             {"op", "remove"}, {"path", path_key}
                         }));
                     }
+                }
 
-                    // add every key that is either common (just removed
-                    // above) or brand new, in target's iteration order, so
-                    // that the final order after applying the patch matches
-                    // target exactly
-                    for (auto it = target.cbegin(); it != target.cend(); ++it)
+                // second pass: traverse other object's elements
+                for (auto it = target.cbegin(); it != target.cend(); ++it)
+                {
+                    if (source.find(it.key()) == source.end())
                     {
+                        // found a key that is not in this -> add it
                         const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
                         result.push_back(
                         {

tests/src/unit-bjdata.cpp

@@ -3288,8 +3288,10 @@ TEST_CASE("BJData")
             CHECK_THROWS_WITH_AS(_ = json::from_bjdata(vR1), "[json.exception.parse_error.113] parse error at byte 6: syntax error while parsing BJData size: ndarray dimensional vector is not allowed", json::parse_error&);
             CHECK(json::from_bjdata(vR1, true, false).is_discarded());
 
+            // a dimension vector that opens another one is rejected where the
+            // nested '[' is read, rather than after it has been descended into
             std::vector<uint8_t> const vR2 = {'[', '$', 'i', '#', '[', '#', '[', 'i', 1, ']', ']', 1};
-            CHECK_THROWS_WITH_AS(_ = json::from_bjdata(vR2), "[json.exception.parse_error.113] parse error at byte 11: syntax error while parsing BJData size: expected length type specification (U, i, u, I, m, l, M, L) after '#'; last byte: 0x5D", json::parse_error&);
+            CHECK_THROWS_WITH_AS(_ = json::from_bjdata(vR2), "[json.exception.parse_error.113] parse error at byte 7: syntax error while parsing BJData size: ndarray dimensional vector is not allowed", json::parse_error&);
             CHECK(json::from_bjdata(vR2, true, false).is_discarded());
 
             std::vector<uint8_t> const vR3 = {'[', '#', '[', 'i', '2', 'i', 2, ']'};
@@ -3297,7 +3299,7 @@ TEST_CASE("BJData")
             CHECK(json::from_bjdata(vR3, true, false).is_discarded());
 
             std::vector<uint8_t> const vR4 = {'[', '$', 'i', '#', '[', '$', 'i', '#', '[', 'i', 1, ']', 1};
-            CHECK_THROWS_WITH_AS(_ = json::from_bjdata(vR4), "[json.exception.parse_error.110] parse error at byte 14: syntax error while parsing BJData number: unexpected end of input", json::parse_error&);
+            CHECK_THROWS_WITH_AS(_ = json::from_bjdata(vR4), "[json.exception.parse_error.113] parse error at byte 9: syntax error while parsing BJData size: ndarray dimensional vector is not allowed", json::parse_error&);
             CHECK(json::from_bjdata(vR4, true, false).is_discarded());
 
             std::vector<uint8_t> const vR5 = {'[', '$', 'i', '#', '[', '[', '[', ']', ']', ']'};
@@ -3305,12 +3307,25 @@ TEST_CASE("BJData")
             CHECK(json::from_bjdata(vR5, true, false).is_discarded());
 
             std::vector<uint8_t> const vR6 = {'[', '$', 'i', '#', '[', '$', 'i', '#', '[', 'i', '2', 'i', 2, ']'};
-            CHECK_THROWS_WITH_AS(_ = json::from_bjdata(vR6), "[json.exception.parse_error.112] parse error at byte 14: syntax error while parsing BJData size: ndarray can not be recursive", json::parse_error&);
+            CHECK_THROWS_WITH_AS(_ = json::from_bjdata(vR6), "[json.exception.parse_error.113] parse error at byte 9: syntax error while parsing BJData size: ndarray dimensional vector is not allowed", json::parse_error&);
             CHECK(json::from_bjdata(vR6, true, false).is_discarded());
 
             std::vector<uint8_t> const vH = {'[', 'H', '[', '#', '[', '$', 'i', '#', '[', 'i', '2', 'i', 2, ']'};
             CHECK_THROWS_WITH_AS(_ = json::from_bjdata(vH), "[json.exception.parse_error.113] parse error at byte 3: syntax error while parsing BJData size: ndarray dimensional vector is not allowed", json::parse_error&);
             CHECK(json::from_bjdata(vH, true, false).is_discarded());
+
+            // Every "#[" of this chain used to open another dimension vector
+            // and cost several stack frames before anything was rejected, so a
+            // long enough chain crashed the process (see #5104). The nested
+            // vector is refused where it is read, so the length is irrelevant.
+            std::vector<uint8_t> vRdeep = {'['};
+            for (std::size_t i = 0; i < 100000; ++i)
+            {
+                vRdeep.push_back('#');
+                vRdeep.push_back('[');
+            }
+            CHECK_THROWS_WITH_AS(_ = json::from_bjdata(vRdeep), "[json.exception.parse_error.113] parse error at byte 5: syntax error while parsing BJData size: ndarray dimensional vector is not allowed", json::parse_error&);
+            CHECK(json::from_bjdata(vRdeep, true, false).is_discarded());
         }
 
         SECTION("objects")

tests/src/unit-cbor.cpp

@@ -2035,6 +2035,145 @@ TEST_CASE("CBOR definite length equal to the indefinite-length sentinel")
     }
 }
 
+TEST_CASE("CBOR nesting does not consume the call stack")
+{
+    // Containers used to be read by calling back into the value reader once
+    // per element, and a tag by calling it for the tagged value, so the native
+    // call stack grew with the nesting depth of the input. Each of the three
+    // costs a single byte to encode -- 0x9F, 0x81 and 0xC2 -- so a payload of
+    // repeated bytes crashed the process (#5104). The containers are kept on a
+    // heap stack now, and a tag is read in a loop.
+    //
+    // Deeply nested values must not be compared, copied or dumped here: those
+    // operations are still recursive and would reintroduce the crash.
+    json _;
+
+    SECTION("indefinite-length containers")
+    {
+        const std::vector<uint8_t> input(500000, 0x9F);
+        CHECK_THROWS_WITH_AS(_ = json::from_cbor(input), "[json.exception.parse_error.110] parse error at byte 500001: syntax error while parsing CBOR value: unexpected end of input", json::parse_error&);
+        CHECK(json::from_cbor(input, true, false).is_discarded());
+    }
+
+    SECTION("definite-length containers")
+    {
+        const std::vector<uint8_t> input(500000, 0x81);
+        CHECK_THROWS_WITH_AS(_ = json::from_cbor(input), "[json.exception.parse_error.110] parse error at byte 500001: syntax error while parsing CBOR value: unexpected end of input", json::parse_error&);
+        CHECK(json::from_cbor(input, true, false).is_discarded());
+    }
+
+    SECTION("tags")
+    {
+        // a tag is not a value of its own, so a chain of them used to recurse
+        const std::vector<uint8_t> input(500000, 0xC2);
+        CHECK_THROWS_WITH_AS(_ = json::from_cbor(input, true, true, json::cbor_tag_handler_t::ignore), "[json.exception.parse_error.110] parse error at byte 500001: syntax error while parsing CBOR value: unexpected end of input", json::parse_error&);
+        CHECK(json::from_cbor(input, true, false, json::cbor_tag_handler_t::ignore).is_discarded());
+    }
+
+    SECTION("a well-formed deep value is read through the SAX interface")
+    {
+        std::vector<uint8_t> input(200000, 0x9F);
+        input.insert(input.end(), 200000, 0xFF);
+
+        SaxCountdown accept_all(1000000);
+        CHECK(json::sax_parse(input, &accept_all, json::input_format_t::cbor));
+    }
+
+    SECTION("a well-formed deep value is read into a value")
+    {
+        const std::size_t depth = 10000;
+        std::vector<uint8_t> input(depth, 0x81);
+        input.push_back(0x00);
+
+        json j = json::from_cbor(input);
+
+        std::size_t measured = 0;
+        const json* p = &j;
+        while (p->is_array() && !p->empty())
+        {
+            p = &p->front();
+            ++measured;
+        }
+        CHECK(measured == depth);
+        CHECK(p->is_number());
+    }
+
+    SECTION("containers are still read the same way")
+    {
+        CHECK(json::from_cbor(std::vector<uint8_t>({0x80})) == json::array());
+        CHECK(json::from_cbor(std::vector<uint8_t>({0xA0})) == json::object());
+        CHECK(json::from_cbor(std::vector<uint8_t>({0x9F, 0xFF})) == json::array());
+        CHECK(json::from_cbor(std::vector<uint8_t>({0xBF, 0xFF})) == json::object());
+        CHECK(json::from_cbor(std::vector<uint8_t>({0x9F, 0x01, 0x02, 0xFF})) == json({1, 2}));
+        CHECK(json::from_cbor(std::vector<uint8_t>({0xBF, 0x61, 'a', 0x01, 0xFF})) == json({{"a", 1}}));
+        // definite and indefinite forms nested inside each other
+        CHECK(json::from_cbor(std::vector<uint8_t>({0x9F, 0x82, 0x01, 0x02, 0xA1, 0x61, 'k', 0xBF, 0xFF, 0xFF})) == json({{1, 2}, {{"k", json::object()}}}));
+    }
+
+    SECTION("tagged values are still read the same way")
+    {
+        const auto ignore = json::cbor_tag_handler_t::ignore;
+        CHECK(json::from_cbor(std::vector<uint8_t>({0xC2, 0x01}), true, true, ignore) == json(1));
+        // a chain of tags resolves to the value that follows it
+        CHECK(json::from_cbor(std::vector<uint8_t>({0xC2, 0xC2, 0xC2, 0x01}), true, true, ignore) == json(1));
+        // a tag inside a container, and one in front of a container
+        CHECK(json::from_cbor(std::vector<uint8_t>({0x82, 0xC2, 0x01, 0x02}), true, true, ignore) == json({1, 2}));
+        CHECK(json::from_cbor(std::vector<uint8_t>({0xC2, 0x82, 0x01, 0x02}), true, true, ignore) == json({1, 2}));
+    }
+}
+
+TEST_CASE("CBOR indefinite-length strings do not recurse per chunk")
+{
+    // Reading an indefinite-length string or byte array used to call itself
+    // once per chunk, so a payload of repeated 0x7F (or 0x5F) bytes exhausted
+    // the call stack before any of the input was rejected. The open levels are
+    // counted now, and the levels below prove the reader still reads the same
+    // values and reports the same errors at the same byte offsets.
+    json _;
+
+    SECTION("many open levels are reported, not crashed on")
+    {
+        const std::vector<uint8_t> input(200000, 0x7F);
+        CHECK_THROWS_WITH_AS(_ = json::from_cbor(input), "[json.exception.parse_error.110] parse error at byte 200001: syntax error while parsing CBOR string: unexpected end of input", json::parse_error&);
+        CHECK(json::from_cbor(input, true, false).is_discarded());
+    }
+
+    SECTION("many open levels are reported, not crashed on (binary)")
+    {
+        const std::vector<uint8_t> input(200000, 0x5F);
+        CHECK_THROWS_WITH_AS(_ = json::from_cbor(input), "[json.exception.parse_error.110] parse error at byte 200001: syntax error while parsing CBOR binary: unexpected end of input", json::parse_error&);
+        CHECK(json::from_cbor(input, true, false).is_discarded());
+    }
+
+    SECTION("chunks are still concatenated")
+    {
+        CHECK(json::from_cbor(std::vector<uint8_t>({0x7F, 0xFF})) == json(""));
+        CHECK(json::from_cbor(std::vector<uint8_t>({0x7F, 0x61, 0x61, 0xFF})) == json("a"));
+        // nested indefinite-length strings are concatenated across levels
+        CHECK(json::from_cbor(std::vector<uint8_t>({0x7F, 0x7F, 0x61, 0x61, 0xFF, 0x61, 0x62, 0xFF})) == json("ab"));
+        CHECK(json::from_cbor(std::vector<uint8_t>({0x7F, 0x7F, 0x7F, 0x61, 0x7A, 0xFF, 0xFF, 0xFF})) == json("z"));
+        CHECK(json::from_cbor(std::vector<uint8_t>({0xA1, 0x7F, 0x61, 0x61, 0xFF, 0x01})) == json({{"a", 1}}));
+    }
+
+    SECTION("chunks are still concatenated (binary)")
+    {
+        CHECK(json::from_cbor(std::vector<uint8_t>({0x5F, 0x41, 0x61, 0xFF})) == json::binary({0x61}));
+        CHECK(json::from_cbor(std::vector<uint8_t>({0x5F, 0x5F, 0x41, 0x61, 0xFF, 0x41, 0x62, 0xFF})) == json::binary({0x61, 0x62}));
+    }
+
+    SECTION("a chunk that is not a string is still rejected")
+    {
+        CHECK_THROWS_WITH_AS(_ = json::from_cbor(std::vector<uint8_t>({0x7F, 0x7F, 0x00})), "[json.exception.parse_error.113] parse error at byte 3: syntax error while parsing CBOR string: expected length specification (0x60-0x7B) or indefinite string type (0x7F); last byte: 0x00", json::parse_error&);
+        CHECK_THROWS_WITH_AS(_ = json::from_cbor(std::vector<uint8_t>({0x5F, 0x5F, 0x00})), "[json.exception.parse_error.113] parse error at byte 3: syntax error while parsing CBOR binary: expected length specification (0x40-0x5B) or indefinite binary array type (0x5F); last byte: 0x00", json::parse_error&);
+    }
+
+    SECTION("a break marker outside an indefinite-length string is not a string")
+    {
+        // 0xFF only closes a string that was opened; on its own it is not one
+        CHECK_THROWS_WITH_AS(_ = json::from_cbor(std::vector<uint8_t>({0xA1, 0xFF, 0x01})), "[json.exception.parse_error.113] parse error at byte 2: syntax error while parsing CBOR string: expected length specification (0x60-0x7B) or indefinite string type (0x7F); last byte: 0xFF", json::parse_error&);
+    }
+}
+
 TEST_CASE("CBOR roundtrips" * doctest::skip())
 {
     SECTION("input from flynn")

tests/src/unit-diagnostics.cpp

@@ -273,36 +273,5 @@ TEST_CASE("Regression tests for extended diagnostics")
         CHECK(j1["numbers"]["two"] == 2);
         CHECK(j1["string"] == "t");
     }
-
-    SECTION("Regression test - swap(array_t&)/swap(object_t&) must update JSON_DIAGNOSTICS parent pointers")
-    {
-        // swap(array_t&)
-        {
-            json j = json::array();
-            json::array_t arr = {json::array({1})};
-            j.swap(arr);
-
-            // parent pointers of the moved-in elements must point into j, not
-            // into the now-defunct free-standing array_t
-            CHECK_THROWS_WITH_AS(j[0][0].get<std::string>(), "[json.exception.type_error.302] (/0/0) type must be string, but is number", json::type_error);
-
-            // must not trigger assert_invariant() in a debug/assert-enabled build
-            json const k = j;
-            CHECK(k == j);
-        }
-
-        // swap(object_t&)
-        {
-            json o = json::object();
-            json::object_t obj = {{"a", json::array({1})}};
-            o.swap(obj);
-
-            CHECK_THROWS_WITH_AS(o["a"][0].get<std::string>(), "[json.exception.type_error.302] (/a/0) type must be string, but is number", json::type_error);
-
-            // must not trigger assert_invariant() in a debug/assert-enabled build
-            json const p = o;
-            CHECK(p == o);
-        }
-    }
 }
 

tests/src/unit-msgpack.cpp

@@ -1598,6 +1598,67 @@ TEST_CASE("MessagePack")
 }
 
 // use this testcase outside [hide] to run it with Valgrind
+TEST_CASE("MessagePack nesting does not consume the call stack")
+{
+    // Reading a container used to call back into the value reader once per
+    // element, so the native call stack grew with the nesting depth of the
+    // input: one frame per byte for repeated 0x91 (a one-element array), which
+    // crashes the process long before the input is exhausted (#5104). The
+    // containers are kept on a heap stack now.
+    //
+    // Note that deeply nested values must not be compared, copied or dumped
+    // here: those operations are still recursive, and would reintroduce the
+    // very crash this checks for. Depth is measured by descending instead.
+
+    SECTION("an unterminated chain is reported, not crashed on")
+    {
+        json _;
+        const std::vector<uint8_t> input(300000, 0x91);
+        CHECK_THROWS_WITH_AS(_ = json::from_msgpack(input), "[json.exception.parse_error.110] parse error at byte 300001: syntax error while parsing MessagePack value: unexpected end of input", json::parse_error&);
+        CHECK(json::from_msgpack(input, true, false).is_discarded());
+    }
+
+    SECTION("a well-formed deep value is read through the SAX interface")
+    {
+        std::vector<uint8_t> input(300000, 0x91);
+        input.push_back(0x01); // innermost value
+
+        SaxCountdown accept_all(600001);
+        CHECK(json::sax_parse(input, &accept_all, json::input_format_t::msgpack));
+    }
+
+    SECTION("a well-formed deep value is read into a value")
+    {
+        const std::size_t depth = 10000;
+        std::vector<uint8_t> input(depth, 0x91);
+        input.push_back(0x01);
+
+        json j = json::from_msgpack(input);
+
+        std::size_t measured = 0;
+        const json* p = &j;
+        while (p->is_array() && !p->empty())
+        {
+            p = &p->front();
+            ++measured;
+        }
+        CHECK(measured == depth);
+        CHECK(p->is_number());
+    }
+
+    SECTION("containers are still read the same way")
+    {
+        CHECK(json::from_msgpack(std::vector<uint8_t>({0x90})) == json::array());
+        CHECK(json::from_msgpack(std::vector<uint8_t>({0x80})) == json::object());
+        CHECK(json::from_msgpack(std::vector<uint8_t>({0x92, 0x90, 0x80})) == json({json::array(), json::object()}));
+        CHECK(json::from_msgpack(std::vector<uint8_t>({0x91, 0x91, 0x91, 0x90})) == json({{{json::array()}}}));
+        CHECK(json::from_msgpack(std::vector<uint8_t>({0x81, 0xA1, 'a', 0x81, 0xA1, 'b', 0x92, 0x01, 0x02})) == json({{"a", {{"b", {1, 2}}}}}));
+        // array 16 and map 32, i.e. the counted forms
+        CHECK(json::from_msgpack(std::vector<uint8_t>({0xDC, 0x00, 0x02, 0x01, 0x02})) == json({1, 2}));
+        CHECK(json::from_msgpack(std::vector<uint8_t>({0xDF, 0x00, 0x00, 0x00, 0x01, 0xA1, 'k', 0xC3})) == json({{"k", true}}));
+    }
+}
+
 TEST_CASE("single MessagePack roundtrip")
 {
     SECTION("sample.json")

tests/src/unit-ordered_json.cpp

@@ -81,84 +81,3 @@ TEST_CASE("regression test for issue #3732 - iteration_proxy_value<iter_impl<ord
     };
     static_cast<void>(fn);
 }
-
-TEST_CASE("regression test - diff() must account for ordered_json member order")
-{
-    SECTION("pure reorder, no value changes")
-    {
-        ordered_json a = {{"a", 1}, {"b", 2}};
-        ordered_json b = {{"b", 2}, {"a", 1}};
-        CHECK(a != b); // order-sensitive equality
-        CHECK(a.patch(ordered_json::diff(a, b)) == b);
-    }
-
-    SECTION("new key must land at the front")
-    {
-        ordered_json c = {{"b", 2}};
-        ordered_json e = {{"a", 1}, {"b", 2}};
-        CHECK(c.patch(ordered_json::diff(c, e)) == e);
-    }
-
-    SECTION("reorder plus a value change on one of the reordered keys")
-    {
-        ordered_json a = {{"a", 1}, {"b", 2}};
-        ordered_json b = {{"b", 20}, {"a", 1}};
-        CHECK(a != b);
-        CHECK(a.patch(ordered_json::diff(a, b)) == b);
-    }
-
-    SECTION("reorder plus a deleted key")
-    {
-        ordered_json a = {{"a", 1}, {"b", 2}, {"c", 3}};
-        ordered_json b = {{"b", 2}, {"a", 1}};
-        CHECK(a != b);
-        CHECK(a.patch(ordered_json::diff(a, b)) == b);
-    }
-
-    SECTION("reorder plus a nested value that itself needs a recursive diff")
-    {
-        ordered_json a = {{"a", {{"x", 1}, {"y", 2}}}, {"b", 2}};
-        ordered_json b = {{"b", 2}, {"a", {{"x", 1}, {"y", 99}}}};
-        CHECK(a != b);
-        CHECK(a.patch(ordered_json::diff(a, b)) == b);
-    }
-
-    SECTION("three or more keys shuffled into a different order")
-    {
-        ordered_json a = {{"a", 1}, {"b", 2}, {"c", 3}, {"d", 4}};
-        ordered_json b = {{"d", 4}, {"b", 2}, {"a", 1}, {"c", 3}};
-        CHECK(a != b);
-        CHECK(a.patch(ordered_json::diff(a, b)) == b);
-    }
-
-    SECTION("matching order still produces a minimal patch (fast path unaffected)")
-    {
-        ordered_json a = {{"a", 1}, {"b", 2}, {"c", 3}};
-        ordered_json b = {{"a", 1}, {"b", 20}, {"c", 3}};
-        auto p = ordered_json::diff(a, b);
-        // only the changed value should be touched, not a wholesale remove+add
-        CHECK(p.size() == 1);
-        CHECK(p[0]["op"] == "replace");
-        CHECK(p[0]["path"] == "/b");
-        CHECK(a.patch(p) == b);
-    }
-
-    SECTION("plain json (std::map-backed) is unaffected by same-key-different-insertion-order")
-    {
-        json a;
-        a["b"] = 2;
-        a["a"] = 1;
-
-        json b;
-        b["a"] = 1;
-        b["b"] = 2;
-
-        // std::map iteration is always sorted by key, so a == b regardless of
-        // insertion order, and diff() must still produce the same minimal
-        // (empty) result as before this fix
-        CHECK(a == b);
-        auto p = json::diff(a, b);
-        CHECK(p.empty());
-        CHECK(a.patch(p) == b);
-    }
-}

tests/src/unit-regression2.cpp

@@ -1566,106 +1566,4 @@ TEST_CASE("issue #5402 - update(merge_objects=true) overwrites a primitive with
     CHECK(mixed == json({{"keep", {{"a", 1}, {"b", 2}}}, {"replace", {{"x", 2}}}}));
 }
 
-TEST_CASE("regression test - parser callback must not lose a duplicate key's prior value")
-{
-    // a callback that rejects only the scalar value 2
-    const json::parser_callback_t drop_value_2 = [](int /*depth*/, json::parse_event_t ev, json & v) noexcept
-    {
-        return !(ev == json::parse_event_t::value && v == 2);
-    };
-
-    SECTION("duplicate key, second (scalar) value rejected - prior value is restored")
-    {
-        const json j = json::parse(R"({"a":1,"a":2})", drop_value_2);
-        CHECK(j.dump() == "{\"a\":1}");
-    }
-
-    SECTION("duplicate key, second value is an object rejected at object_end - prior value is restored")
-    {
-        const json j = json::parse(R"({"a":1,"a":{"x":2}})",
-                                   [](int depth, json::parse_event_t ev, json& /*parsed*/) noexcept
-        {
-            return !(ev == json::parse_event_t::object_end && depth == 1);
-        });
-        CHECK(j.dump() == "{\"a\":1}");
-    }
-
-    SECTION("duplicate key, second value is an array rejected at array_end - prior value is restored")
-    {
-        const json j = json::parse(R"({"a":1,"a":[9,9]})",
-                                   [](int depth, json::parse_event_t ev, json& /*parsed*/) noexcept
-        {
-            return !(ev == json::parse_event_t::array_end && depth == 1);
-        });
-        CHECK(j.dump() == "{\"a\":1}");
-    }
-
-    SECTION("duplicate key, second value accepted (scalar) - last value wins")
-    {
-        const json j = json::parse(R"({"a":1,"a":2})", [](int, json::parse_event_t, json&) noexcept
-        {
-            return true;
-        });
-        CHECK(j.dump() == "{\"a\":2}");
-    }
-
-    SECTION("duplicate key, second value accepted (object) - last value wins")
-    {
-        const json j = json::parse(R"({"a":1,"a":{"x":2}})", [](int, json::parse_event_t, json&) noexcept
-        {
-            return true;
-        });
-        CHECK(j.dump() == "{\"a\":{\"x\":2}}");
-    }
-
-    SECTION("brand new (non-duplicate) key, value rejected - member is fully absent")
-    {
-        const json j = json::parse(R"({"a":1,"b":2})", drop_value_2);
-        CHECK(j.dump() == "{\"a\":1}");
-    }
-
-    SECTION("duplicate key nested two levels deep")
-    {
-        const json j = json::parse(R"({"outer":{"a":1,"a":2}})", drop_value_2);
-        CHECK(j.dump() == "{\"outer\":{\"a\":1}}");
-    }
-
-    SECTION("three occurrences of the same key - middle rejected, last accepted")
-    {
-        const json j = json::parse(R"({"k":1,"k":2,"k":3})", drop_value_2);
-        CHECK(j.dump() == "{\"k\":3}");
-    }
-}
-
-TEST_CASE("regression test - excessive binary container size honors allow_exceptions=false")
-{
-    // CBOR array with declared length 2^63
-    const std::vector<std::uint8_t> cbor = {0x9b, 0x80, 0, 0, 0, 0, 0, 0, 0};
-    // CBOR map with declared length 2^63
-    const std::vector<std::uint8_t> cbor_m = {0xbb, 0x80, 0, 0, 0, 0, 0, 0, 0};
-    // UBJSON array with declared length 2^63-1
-    const std::vector<std::uint8_t> ubj = {'[', '#', 'L', 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
-    // BJData array with declared length 2^63-1 (little endian)
-    const std::vector<std::uint8_t> bjd = {'[', '#', 'L', 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f};
-
-    // allow_exceptions=false must report failure instead of throwing/aborting
-    CHECK(json::from_cbor(cbor, true, false).is_discarded());
-    CHECK(json::from_cbor(cbor_m, true, false).is_discarded());
-    CHECK(json::from_ubjson(ubj, true, false).is_discarded());
-    CHECK(json::from_bjdata(bjd, true, false).is_discarded());
-
-    // allow_exceptions=true (the default) must still throw exactly as before.
-    // The exact message text is not checked here: on platforms where
-    // std::size_t is 32-bit, the CBOR reader's own length-narrowing check
-    // (get_cbor_container_size(), unrelated to this fix) intercepts a
-    // declared length of 2^63 before it ever reaches the check this test
-    // targets, with different (but equally valid, and already correct)
-    // wording -- see unit-cbor.cpp for coverage of that message.
-    json _;
-    CHECK_THROWS_AS(_ = json::from_cbor(cbor), json::out_of_range);
-
-    // regression guard: a genuinely truncated CBOR input must remain discarded
-    CHECK(json::from_cbor(std::vector<std::uint8_t> {0x9b, 0, 0, 0, 0, 0, 0, 0, 0x02}, true, false).is_discarded());
-}
-
 DOCTEST_CLANG_SUPPRESS_WARNING_POP

tests/src/unit-ubjson.cpp

@@ -2149,6 +2149,61 @@ TEST_CASE("UBJSON")
     }
 }
 
+TEST_CASE("UBJSON optimized arrays of a valueless type are bounded")
+{
+    // An element of type 'Z', 'T' or 'F' is encoded by its marker alone, so an
+    // optimized array of one of those has no payload and the declared count is
+    // the only thing deciding how much is allocated. Ten bytes used to produce
+    // billions of values (#2793); every other type costs at least one byte per
+    // element and is bounded by the end of the input.
+    json _;
+
+    SECTION("an excessive count is rejected")
+    {
+        // 'l' is a big-endian int32: 0x7FFFFFFF elements, about 34 GB of value
+        for (const auto marker :
+                {'Z', 'T', 'F'
+                })
+        {
+            const std::vector<uint8_t> input = {'[', '$', static_cast<uint8_t>(marker), '#', 'l', 0x7F, 0xFF, 0xFF, 0xFF};
+            CHECK_THROWS_WITH_AS(_ = json::from_ubjson(input), "[json.exception.out_of_range.408] syntax error while parsing UBJSON size: excessive array size", json::out_of_range&);
+            CHECK(json::from_ubjson(input, true, false).is_discarded());
+        }
+    }
+
+    SECTION("ordinary counts are unaffected")
+    {
+        CHECK(json::from_ubjson(std::vector<uint8_t>({'[', '$', 'Z', '#', 'i', 3})) == json({nullptr, nullptr, nullptr}));
+        CHECK(json::from_ubjson(std::vector<uint8_t>({'[', '$', 'T', '#', 'i', 2})) == json({true, true}));
+        CHECK(json::from_ubjson(std::vector<uint8_t>({'[', '$', 'F', '#', 'i', 2})) == json({false, false}));
+        // 'N' is a no-op rather than a value, and still yields an empty array
+        CHECK(json::from_ubjson(std::vector<uint8_t>({'[', '$', 'N', '#', 'i', 2})) == json::array());
+    }
+
+    SECTION("a type with a payload is unaffected")
+    {
+        // the same count for 'U' is bounded by the end of the input instead
+        const std::vector<uint8_t> input = {'[', '$', 'U', '#', 'l', 0x7F, 0xFF, 0xFF, 0xFF};
+        CHECK_THROWS_AS(_ = json::from_ubjson(input), json::parse_error&);
+    }
+
+    SECTION("the writer stays within what the reader accepts")
+    {
+        // below the limit the optimized form is used and is tiny; above it the
+        // writer falls back so that the result can still be read back
+        json const at_limit(1048576, nullptr);
+        const auto v_at_limit = json::to_ubjson(at_limit, true, true);
+        CHECK(v_at_limit.size() == 9);
+        CHECK(v_at_limit.at(1) == '$');
+        CHECK(json::from_ubjson(v_at_limit) == at_limit);
+
+        json const above_limit(1048577, nullptr);
+        const auto v_above_limit = json::to_ubjson(above_limit, true, true);
+        CHECK(v_above_limit.at(1) != '$');
+        CHECK(json::from_ubjson(v_above_limit) == above_limit);
+    }
+}
+
 TEST_CASE("Universal Binary JSON Specification Examples 1")
 {
     SECTION("Null Value")