Merge branch 'develop' into copy-scratch-allocator

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

.github/workflows/windows.yml

@@ -124,11 +124,11 @@ jobs:
     steps:
       - uses: actions/checkout@3d3c42e5aac5ba805825da76410c181273ba90b1 # v7.0.1
       - name: Run CMake (Release)
-        run: cmake -S . -B build -G "Visual Studio 17 2022" -A ARM64 -DJSON_BuildTests=On -DCMAKE_CXX_FLAGS="/W4 /WX"
+        run: cmake -S . -B build -G "Visual Studio 18 2026" -A ARM64 -DJSON_BuildTests=On -DCMAKE_CXX_FLAGS="/W4 /WX"
         if: matrix.build_type == 'Release'
         shell: pwsh
       - name: Run CMake (Debug)
-        run: cmake -S . -B build -G "Visual Studio 17 2022" -A ARM64 -DJSON_BuildTests=On -DJSON_FastTests=ON -DCMAKE_CXX_FLAGS="/W4 /WX"
+        run: cmake -S . -B build -G "Visual Studio 18 2026" -A ARM64 -DJSON_BuildTests=On -DJSON_FastTests=ON -DCMAKE_CXX_FLAGS="/W4 /WX"
         if: matrix.build_type == 'Debug'
         shell: pwsh
       - name: Build

docs/mkdocs/docs/api/basic_json/to_bson.md

@@ -46,8 +46,9 @@ Strong guarantee: if an exception is thrown, there are no changes in the JSON va
 
 ## Complexity
 
-Linear in the size of the JSON value `j`. The length prefixes of all nested documents and arrays are computed in one
-pass before anything is written.
+Proportional to the size of the JSON value `j` multiplied by its maximum nesting
+depth, `O(n × d)`. BSON length prefixes are computed recursively before nested
+values are written.
 
 ## Examples
 
@@ -76,4 +77,3 @@ pass before anything is written.
 ## Version history
 
 - Added in version 3.4.0.
-- Linear in the size of `j`, and no longer limited by the call stack for deeply nested values, since version 3.13.0.

docs/mkdocs/docs/features/types/template_parameters.md

@@ -562,7 +562,11 @@ binary32 or binary64 field and have no encoding for `#!cpp long double`.
 ## `AllocatorType`
 
 `AllocatorType` is instantiated with **one** argument, for each of `object_t`, `array_t`, `string_t`, `binary_t`,
-`basic_json`, and `#!cpp std::pair<const StringType, basic_json>`.
+`basic_json`, `#!cpp std::pair<const StringType, basic_json>`, and `#!cpp std::pair<StringType, basic_json>`.
+
+`AllocatorType` is not the only allocator a `basic_json` uses. It allocates the JSON values themselves, but most
+temporary storage is allocated with `#!cpp std::allocator`. This includes the parser's stacks and the stacks that
+process deeply nested values without recursion.
 
 ### Always required
 

include/nlohmann/detail/output/binary_writer.hpp

@@ -122,7 +122,7 @@ class binary_writer
         {
             case value_t::object:
             {
-                write_bson_document(j);
+                write_bson_object(*j.m_data.m_value.object);
                 break;
             }
 
@@ -1197,6 +1197,35 @@ class binary_writer
         }
     }
 
+    /*!
+    @brief Writes a BSON element with key @a name and object @a value
+    */
+    void write_bson_object_entry(const string_t& name,
+                                 const typename BasicJsonType::object_t& value)
+    {
+        write_bson_entry_header(name, 0x03); // object
+        write_bson_object(value);
+    }
+
+    /*!
+    @return The size of the BSON-encoded array @a value
+    */
+    static std::size_t calc_bson_array_size(const typename BasicJsonType::array_t& value)
+    {
+        std::size_t array_index = 0ul;
+
+        const std::size_t embedded_document_size = std::accumulate(std::begin(value), std::end(value), static_cast<std::size_t>(0), [&array_index](std::size_t result, const typename BasicJsonType::array_t::value_type & el)
+        {
+            // the index is built as a std::string, while calc_bson_element_size
+            // takes a string_t; convert explicitly, as the two are only
+            // implicitly convertible for some string types
+            const auto key = std::to_string(array_index++);
+            return result + calc_bson_element_size(string_t(key.data(), key.size()), el);
+        });
+
+        return sizeof(std::int32_t) + embedded_document_size + 1ul;
+    }
+
     /*!
     @return The size of the BSON-encoded binary array @a value
     */
@@ -1205,6 +1234,29 @@ class binary_writer
         return sizeof(std::int32_t) + value.size() + 1ul;
     }
 
+    /*!
+    @brief Writes a BSON element with key @a name and array @a value
+    */
+    void write_bson_array(const string_t& name,
+                          const typename BasicJsonType::array_t& value)
+    {
+        write_bson_entry_header(name, 0x04); // array
+        write_number<std::int32_t>(to_bson_length(calc_bson_array_size(value)), true);
+
+        std::size_t array_index = 0ul;
+
+        for (const auto& el : value)
+        {
+            // the index is built as a std::string, while write_bson_element takes
+            // a string_t; convert explicitly, as the two are only implicitly
+            // convertible for some string types
+            const auto key = std::to_string(array_index++);
+            write_bson_element(string_t(key.data(), key.size()), el);
+        }
+
+        oa.write_character(to_char_type(0x00));
+    }
+
     /*!
     @brief Writes a BSON element with key @a name and binary value @a value
     */
@@ -1226,37 +1278,43 @@ class binary_writer
     }
 
     /*!
-    @return The size of the value of the BSON document entry for @a j, which
-            is neither an object nor an array
+    @brief Calculates the size necessary to serialize the JSON value @a j with its @a name
+    @return The calculated size for the BSON document entry for @a j with the given @a name.
     */
-    static std::size_t calc_bson_value_size(const BasicJsonType& j)
+    static std::size_t calc_bson_element_size(const string_t& name,
+            const BasicJsonType& j)
     {
+        const auto header_size = calc_bson_entry_header_size(name, j);
         switch (j.type())
         {
+            case value_t::object:
+                return header_size + calc_bson_object_size(*j.m_data.m_value.object);
+
+            case value_t::array:
+                return header_size + calc_bson_array_size(*j.m_data.m_value.array);
+
             case value_t::binary:
-                return calc_bson_binary_size(*j.m_data.m_value.binary);
+                return header_size + calc_bson_binary_size(*j.m_data.m_value.binary);
 
             case value_t::boolean:
-                return 1ul;
+                return header_size + 1ul;
 
             case value_t::number_float:
-                return 8ul;
+                return header_size + 8ul;
 
             case value_t::number_integer:
-                return calc_bson_integer_size(j.m_data.m_value.number_integer);
+                return header_size + calc_bson_integer_size(j.m_data.m_value.number_integer);
 
             case value_t::number_unsigned:
-                return calc_bson_unsigned_size(j.m_data.m_value.number_unsigned);
+                return header_size + calc_bson_unsigned_size(j.m_data.m_value.number_unsigned);
 
             case value_t::string:
-                return calc_bson_string_size(*j.m_data.m_value.string);
+                return header_size + calc_bson_string_size(*j.m_data.m_value.string);
 
             case value_t::null:
-                return 0ul;
+                return header_size + 0ul;
 
             // LCOV_EXCL_START
-            case value_t::object:
-            case value_t::array:
             case value_t::discarded:
             default:
                 JSON_ASSERT(false); // NOLINT(cert-dcl03-c,hicpp-static-assert,misc-static-assert)
@@ -1266,13 +1324,22 @@ class binary_writer
     }
 
     /*!
-    @brief Writes the BSON document entry with key @a name for @a j, which is
-           neither an object nor an array
+    @brief Serializes the JSON value @a j to BSON and associates it with the
+           key @a name.
+    @param name The name to associate with the JSON entity @a j within the
+                current BSON document
     */
-    void write_bson_value(const string_t& name, const BasicJsonType& j)
+    void write_bson_element(const string_t& name,
+                            const BasicJsonType& j)
     {
         switch (j.type())
         {
+            case value_t::object:
+                return write_bson_object_entry(name, *j.m_data.m_value.object);
+
+            case value_t::array:
+                return write_bson_array(name, *j.m_data.m_value.array);
+
             case value_t::binary:
                 return write_bson_binary(name, *j.m_data.m_value.binary);
 
@@ -1295,8 +1362,6 @@ class binary_writer
                 return write_bson_null(name);
 
             // LCOV_EXCL_START
-            case value_t::object:
-            case value_t::array:
             case value_t::discarded:
             default:
                 JSON_ASSERT(false); // NOLINT(cert-dcl03-c,hicpp-static-assert,misc-static-assert)
@@ -1305,221 +1370,37 @@ class binary_writer
         }
     }
 
-    /// @brief an object or array of the BSON document being sized or written
-    struct bson_frame
-    {
-        explicit bson_frame(const BasicJsonType* value_, const std::size_t size_slot_ = 0)
-            : value(value_)
-            , size_slot(size_slot_)
-        {
-            if (value->is_object())
-            {
-                member = value->m_data.m_value.object->cbegin();
-            }
-        }
-
-        /// the object or array
-        const BasicJsonType* value;
-        /// objects: the next member
-        typename BasicJsonType::object_t::const_iterator member{};
-        /// arrays: the index of the next element
-        std::size_t index = 0;
-        /// @ref calc_bson_sizes only: where its size goes in the table
-        std::size_t size_slot;
-        /// @ref calc_bson_sizes only: the size of its entries seen so far
-        std::size_t entries_size = 0;
-    };
-
     /*!
-    @brief creates the name BSON gives the array element with index @a index
-    @param[out] name  receives the decimal index
+    @brief Calculates the size of the BSON serialization of the given
+           JSON-object @a j.
+    @param[in] value  JSON value to serialize
+    @pre       value.type() == value_t::object
     */
-    static void create_bson_index_name(const std::size_t index, string_t& name)
+    static std::size_t calc_bson_object_size(const typename BasicJsonType::object_t& value)
     {
-        // the index is built as a std::string; convert explicitly, as the
-        // two are only implicitly convertible for some string types
-        const auto key = std::to_string(index);
-        name = string_t(key.data(), key.size());
+        const std::size_t document_size = std::accumulate(value.begin(), value.end(), static_cast<std::size_t>(0),
+                                          [](size_t result, const typename BasicJsonType::object_t::value_type & el)
+        {
+            return result += calc_bson_element_size(el.first, el.second);
+        });
+
+        return sizeof(std::int32_t) + document_size + 1ul;
     }
 
     /*!
-    @brief Calculates the size of every object and array in the BSON document
-           @a document, including the document itself.
-
-    BSON prefixes every document and array with its size, so all of them have
-    to be known before the first byte is written. They are computed in a
-    single pass, each one from the sizes of its entries, which keeps
-    serializing linear in the size of the document; computing each size by
-    walking the entire value below it made it quadratic in the nesting depth.
-    The pass keeps the objects and arrays it has entered on an explicit stack,
-    so a deeply nested value cannot exhaust the call stack.
-
-    @param[in] document  the JSON object to serialize
-    @param[out] nested_sizes  the sizes of the objects and arrays in
-                              @a document, in the order they are written
-    @return the size of @a document
-    @throw out_of_range.409 if a key contains U+0000, before anything is
-           written
+    @param[in] value  JSON value to serialize
+    @pre       value.type() == value_t::object
     */
-    static std::size_t calc_bson_sizes(const BasicJsonType& document, std::vector<std::size_t>& nested_sizes)
+    void write_bson_object(const typename BasicJsonType::object_t& value)
     {
-        // the object or array whose entries are being sized, and the ones it
-        // is in; nothing is allocated unless the document nests
-        bson_frame current(&document);
-        std::vector<bson_frame> parents;
-        // string_t need not be default constructible
-        string_t index_name("", 0);
+        write_number<std::int32_t>(to_bson_length(calc_bson_object_size(value)), true);
 
-        while (true)
+        for (const auto& el : value)
         {
-            // size entries until the current object or array is done, or an
-            // entry is an object or array itself
-            const BasicJsonType* nested = nullptr;
-            if (current.value->is_object())
-            {
-                const auto& object = *current.value->m_data.m_value.object;
-                while (nested == nullptr && current.member != object.cend())
-                {
-                    const auto& el = *current.member;
-                    ++current.member;
-                    current.entries_size += calc_bson_entry_header_size(el.first, el.second);
-                    if (el.second.is_structured())
-                    {
-                        nested = &el.second;
-                    }
-                    else
-                    {
-                        current.entries_size += calc_bson_value_size(el.second);
-                    }
-                }
-            }
-            else
-            {
-                const auto& array = *current.value->m_data.m_value.array;
-                while (nested == nullptr && current.index < array.size())
-                {
-                    const BasicJsonType& el = array[current.index];
-                    create_bson_index_name(current.index, index_name);
-                    current.entries_size += calc_bson_entry_header_size(index_name, el);
-                    ++current.index;
-                    if (el.is_structured())
-                    {
-                        nested = &el;
-                    }
-                    else
-                    {
-                        current.entries_size += calc_bson_value_size(el);
-                    }
-                }
-            }
-
-            if (nested != nullptr)
-            {
-                // its size is added to the current one's once it is done
-                nested_sizes.push_back(0);
-                parents.push_back(std::move(current));
-                current = bson_frame(nested, nested_sizes.size() - 1);
-                continue;
-            }
-
-            // the int32 size, the entries, and the terminating null byte
-            const std::size_t size = sizeof(std::int32_t) + current.entries_size + 1ul;
-            if (parents.empty())
-            {
-                return size;
-            }
-            nested_sizes[current.size_slot] = size;
-            current = std::move(parents.back());
-            parents.pop_back();
-            current.entries_size += size;
+            write_bson_element(el.first, el.second);
         }
-    }
 
-    /*!
-    @brief Serializes the JSON object @a document as a BSON document
-
-    Writes the objects and arrays in it without the call stack, keeping the
-    ones it has entered on an explicit stack, so a deeply nested value
-    cannot exhaust the call stack.
-
-    @param[in] document  the JSON object to serialize
-    @pre       document.type() == value_t::object
-    */
-    void write_bson_document(const BasicJsonType& document)
-    {
-        std::vector<std::size_t> nested_sizes;
-        const std::size_t document_size = calc_bson_sizes(document, nested_sizes);
-        write_number<std::int32_t>(to_bson_length(document_size), true);
-
-        // the object or array whose entries are being written, and the ones
-        // it is in
-        bson_frame current(&document);
-        std::vector<bson_frame> parents;
-        std::size_t next_size = 0;
-        // string_t need not be default constructible
-        string_t index_name("", 0);
-
-        while (true)
-        {
-            // write entries until the current object or array is done, or an
-            // entry is an object or array itself
-            const string_t* nested_name = nullptr;
-            const BasicJsonType* nested = nullptr;
-            if (current.value->is_object())
-            {
-                const auto& object = *current.value->m_data.m_value.object;
-                while (nested == nullptr && current.member != object.cend())
-                {
-                    const auto& el = *current.member;
-                    ++current.member;
-                    if (el.second.is_structured())
-                    {
-                        nested_name = &el.first;
-                        nested = &el.second;
-                    }
-                    else
-                    {
-                        write_bson_value(el.first, el.second);
-                    }
-                }
-            }
-            else
-            {
-                const auto& array = *current.value->m_data.m_value.array;
-                while (nested == nullptr && current.index < array.size())
-                {
-                    const BasicJsonType& el = array[current.index];
-                    create_bson_index_name(current.index, index_name);
-                    ++current.index;
-                    if (el.is_structured())
-                    {
-                        nested_name = &index_name;
-                        nested = &el;
-                    }
-                    else
-                    {
-                        write_bson_value(index_name, el);
-                    }
-                }
-            }
-
-            if (nested != nullptr)
-            {
-                write_bson_entry_header(*nested_name, nested->is_object() ? 0x03 : 0x04);
-                write_number<std::int32_t>(to_bson_length(nested_sizes[next_size++]), true);
-                parents.push_back(std::move(current));
-                current = bson_frame(nested);
-                continue;
-            }
-
-            oa.write_character(to_char_type(0x00));
-            if (parents.empty())
-            {
-                return;
-            }
-            current = std::move(parents.back());
-            parents.pop_back();
-        }
+        oa.write_character(to_char_type(0x00));
     }
 
     //////////

include/nlohmann/json.hpp

@@ -978,7 +978,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     using copy_worklist_t = std::vector<std::pair<const basic_json*, basic_json*>>;
 
     /// scratch space to build the key skeleton of an object copy in one go
-    using copy_scratch_t = std::vector<std::pair<typename object_t::key_type, basic_json>>;
+    using copy_scratch_value_t = std::pair<typename object_t::key_type, basic_json>;
+    using copy_scratch_t = std::vector<copy_scratch_value_t, AllocatorType<copy_scratch_value_t>>;
 
     /// @brief copy everything of @a src into @a dst but its type and value
     static void copy_metadata(const basic_json& src, basic_json& dst)

single_include/nlohmann/json.hpp

@@ -19150,7 +19150,7 @@ class binary_writer
         {
             case value_t::object:
             {
-                write_bson_document(j);
+                write_bson_object(*j.m_data.m_value.object);
                 break;
             }
 
@@ -20225,6 +20225,35 @@ class binary_writer
         }
     }
 
+    /*!
+    @brief Writes a BSON element with key @a name and object @a value
+    */
+    void write_bson_object_entry(const string_t& name,
+                                 const typename BasicJsonType::object_t& value)
+    {
+        write_bson_entry_header(name, 0x03); // object
+        write_bson_object(value);
+    }
+
+    /*!
+    @return The size of the BSON-encoded array @a value
+    */
+    static std::size_t calc_bson_array_size(const typename BasicJsonType::array_t& value)
+    {
+        std::size_t array_index = 0ul;
+
+        const std::size_t embedded_document_size = std::accumulate(std::begin(value), std::end(value), static_cast<std::size_t>(0), [&array_index](std::size_t result, const typename BasicJsonType::array_t::value_type & el)
+        {
+            // the index is built as a std::string, while calc_bson_element_size
+            // takes a string_t; convert explicitly, as the two are only
+            // implicitly convertible for some string types
+            const auto key = std::to_string(array_index++);
+            return result + calc_bson_element_size(string_t(key.data(), key.size()), el);
+        });
+
+        return sizeof(std::int32_t) + embedded_document_size + 1ul;
+    }
+
     /*!
     @return The size of the BSON-encoded binary array @a value
     */
@@ -20233,6 +20262,29 @@ class binary_writer
         return sizeof(std::int32_t) + value.size() + 1ul;
     }
 
+    /*!
+    @brief Writes a BSON element with key @a name and array @a value
+    */
+    void write_bson_array(const string_t& name,
+                          const typename BasicJsonType::array_t& value)
+    {
+        write_bson_entry_header(name, 0x04); // array
+        write_number<std::int32_t>(to_bson_length(calc_bson_array_size(value)), true);
+
+        std::size_t array_index = 0ul;
+
+        for (const auto& el : value)
+        {
+            // the index is built as a std::string, while write_bson_element takes
+            // a string_t; convert explicitly, as the two are only implicitly
+            // convertible for some string types
+            const auto key = std::to_string(array_index++);
+            write_bson_element(string_t(key.data(), key.size()), el);
+        }
+
+        oa.write_character(to_char_type(0x00));
+    }
+
     /*!
     @brief Writes a BSON element with key @a name and binary value @a value
     */
@@ -20254,37 +20306,43 @@ class binary_writer
     }
 
     /*!
-    @return The size of the value of the BSON document entry for @a j, which
-            is neither an object nor an array
+    @brief Calculates the size necessary to serialize the JSON value @a j with its @a name
+    @return The calculated size for the BSON document entry for @a j with the given @a name.
     */
-    static std::size_t calc_bson_value_size(const BasicJsonType& j)
+    static std::size_t calc_bson_element_size(const string_t& name,
+            const BasicJsonType& j)
     {
+        const auto header_size = calc_bson_entry_header_size(name, j);
         switch (j.type())
         {
+            case value_t::object:
+                return header_size + calc_bson_object_size(*j.m_data.m_value.object);
+
+            case value_t::array:
+                return header_size + calc_bson_array_size(*j.m_data.m_value.array);
+
             case value_t::binary:
-                return calc_bson_binary_size(*j.m_data.m_value.binary);
+                return header_size + calc_bson_binary_size(*j.m_data.m_value.binary);
 
             case value_t::boolean:
-                return 1ul;
+                return header_size + 1ul;
 
             case value_t::number_float:
-                return 8ul;
+                return header_size + 8ul;
 
             case value_t::number_integer:
-                return calc_bson_integer_size(j.m_data.m_value.number_integer);
+                return header_size + calc_bson_integer_size(j.m_data.m_value.number_integer);
 
             case value_t::number_unsigned:
-                return calc_bson_unsigned_size(j.m_data.m_value.number_unsigned);
+                return header_size + calc_bson_unsigned_size(j.m_data.m_value.number_unsigned);
 
             case value_t::string:
-                return calc_bson_string_size(*j.m_data.m_value.string);
+                return header_size + calc_bson_string_size(*j.m_data.m_value.string);
 
             case value_t::null:
-                return 0ul;
+                return header_size + 0ul;
 
             // LCOV_EXCL_START
-            case value_t::object:
-            case value_t::array:
             case value_t::discarded:
             default:
                 JSON_ASSERT(false); // NOLINT(cert-dcl03-c,hicpp-static-assert,misc-static-assert)
@@ -20294,13 +20352,22 @@ class binary_writer
     }
 
     /*!
-    @brief Writes the BSON document entry with key @a name for @a j, which is
-           neither an object nor an array
+    @brief Serializes the JSON value @a j to BSON and associates it with the
+           key @a name.
+    @param name The name to associate with the JSON entity @a j within the
+                current BSON document
     */
-    void write_bson_value(const string_t& name, const BasicJsonType& j)
+    void write_bson_element(const string_t& name,
+                            const BasicJsonType& j)
     {
         switch (j.type())
         {
+            case value_t::object:
+                return write_bson_object_entry(name, *j.m_data.m_value.object);
+
+            case value_t::array:
+                return write_bson_array(name, *j.m_data.m_value.array);
+
             case value_t::binary:
                 return write_bson_binary(name, *j.m_data.m_value.binary);
 
@@ -20323,8 +20390,6 @@ class binary_writer
                 return write_bson_null(name);
 
             // LCOV_EXCL_START
-            case value_t::object:
-            case value_t::array:
             case value_t::discarded:
             default:
                 JSON_ASSERT(false); // NOLINT(cert-dcl03-c,hicpp-static-assert,misc-static-assert)
@@ -20333,221 +20398,37 @@ class binary_writer
         }
     }
 
-    /// @brief an object or array of the BSON document being sized or written
-    struct bson_frame
-    {
-        explicit bson_frame(const BasicJsonType* value_, const std::size_t size_slot_ = 0)
-            : value(value_)
-            , size_slot(size_slot_)
-        {
-            if (value->is_object())
-            {
-                member = value->m_data.m_value.object->cbegin();
-            }
-        }
-
-        /// the object or array
-        const BasicJsonType* value;
-        /// objects: the next member
-        typename BasicJsonType::object_t::const_iterator member{};
-        /// arrays: the index of the next element
-        std::size_t index = 0;
-        /// @ref calc_bson_sizes only: where its size goes in the table
-        std::size_t size_slot;
-        /// @ref calc_bson_sizes only: the size of its entries seen so far
-        std::size_t entries_size = 0;
-    };
-
     /*!
-    @brief creates the name BSON gives the array element with index @a index
-    @param[out] name  receives the decimal index
+    @brief Calculates the size of the BSON serialization of the given
+           JSON-object @a j.
+    @param[in] value  JSON value to serialize
+    @pre       value.type() == value_t::object
     */
-    static void create_bson_index_name(const std::size_t index, string_t& name)
+    static std::size_t calc_bson_object_size(const typename BasicJsonType::object_t& value)
     {
-        // the index is built as a std::string; convert explicitly, as the
-        // two are only implicitly convertible for some string types
-        const auto key = std::to_string(index);
-        name = string_t(key.data(), key.size());
+        const std::size_t document_size = std::accumulate(value.begin(), value.end(), static_cast<std::size_t>(0),
+                                          [](size_t result, const typename BasicJsonType::object_t::value_type & el)
+        {
+            return result += calc_bson_element_size(el.first, el.second);
+        });
+
+        return sizeof(std::int32_t) + document_size + 1ul;
     }
 
     /*!
-    @brief Calculates the size of every object and array in the BSON document
-           @a document, including the document itself.
-
-    BSON prefixes every document and array with its size, so all of them have
-    to be known before the first byte is written. They are computed in a
-    single pass, each one from the sizes of its entries, which keeps
-    serializing linear in the size of the document; computing each size by
-    walking the entire value below it made it quadratic in the nesting depth.
-    The pass keeps the objects and arrays it has entered on an explicit stack,
-    so a deeply nested value cannot exhaust the call stack.
-
-    @param[in] document  the JSON object to serialize
-    @param[out] nested_sizes  the sizes of the objects and arrays in
-                              @a document, in the order they are written
-    @return the size of @a document
-    @throw out_of_range.409 if a key contains U+0000, before anything is
-           written
+    @param[in] value  JSON value to serialize
+    @pre       value.type() == value_t::object
     */
-    static std::size_t calc_bson_sizes(const BasicJsonType& document, std::vector<std::size_t>& nested_sizes)
+    void write_bson_object(const typename BasicJsonType::object_t& value)
     {
-        // the object or array whose entries are being sized, and the ones it
-        // is in; nothing is allocated unless the document nests
-        bson_frame current(&document);
-        std::vector<bson_frame> parents;
-        // string_t need not be default constructible
-        string_t index_name("", 0);
+        write_number<std::int32_t>(to_bson_length(calc_bson_object_size(value)), true);
 
-        while (true)
+        for (const auto& el : value)
         {
-            // size entries until the current object or array is done, or an
-            // entry is an object or array itself
-            const BasicJsonType* nested = nullptr;
-            if (current.value->is_object())
-            {
-                const auto& object = *current.value->m_data.m_value.object;
-                while (nested == nullptr && current.member != object.cend())
-                {
-                    const auto& el = *current.member;
-                    ++current.member;
-                    current.entries_size += calc_bson_entry_header_size(el.first, el.second);
-                    if (el.second.is_structured())
-                    {
-                        nested = &el.second;
-                    }
-                    else
-                    {
-                        current.entries_size += calc_bson_value_size(el.second);
-                    }
-                }
-            }
-            else
-            {
-                const auto& array = *current.value->m_data.m_value.array;
-                while (nested == nullptr && current.index < array.size())
-                {
-                    const BasicJsonType& el = array[current.index];
-                    create_bson_index_name(current.index, index_name);
-                    current.entries_size += calc_bson_entry_header_size(index_name, el);
-                    ++current.index;
-                    if (el.is_structured())
-                    {
-                        nested = &el;
-                    }
-                    else
-                    {
-                        current.entries_size += calc_bson_value_size(el);
-                    }
-                }
-            }
-
-            if (nested != nullptr)
-            {
-                // its size is added to the current one's once it is done
-                nested_sizes.push_back(0);
-                parents.push_back(std::move(current));
-                current = bson_frame(nested, nested_sizes.size() - 1);
-                continue;
-            }
-
-            // the int32 size, the entries, and the terminating null byte
-            const std::size_t size = sizeof(std::int32_t) + current.entries_size + 1ul;
-            if (parents.empty())
-            {
-                return size;
-            }
-            nested_sizes[current.size_slot] = size;
-            current = std::move(parents.back());
-            parents.pop_back();
-            current.entries_size += size;
+            write_bson_element(el.first, el.second);
         }
-    }
 
-    /*!
-    @brief Serializes the JSON object @a document as a BSON document
-
-    Writes the objects and arrays in it without the call stack, keeping the
-    ones it has entered on an explicit stack, so a deeply nested value
-    cannot exhaust the call stack.
-
-    @param[in] document  the JSON object to serialize
-    @pre       document.type() == value_t::object
-    */
-    void write_bson_document(const BasicJsonType& document)
-    {
-        std::vector<std::size_t> nested_sizes;
-        const std::size_t document_size = calc_bson_sizes(document, nested_sizes);
-        write_number<std::int32_t>(to_bson_length(document_size), true);
-
-        // the object or array whose entries are being written, and the ones
-        // it is in
-        bson_frame current(&document);
-        std::vector<bson_frame> parents;
-        std::size_t next_size = 0;
-        // string_t need not be default constructible
-        string_t index_name("", 0);
-
-        while (true)
-        {
-            // write entries until the current object or array is done, or an
-            // entry is an object or array itself
-            const string_t* nested_name = nullptr;
-            const BasicJsonType* nested = nullptr;
-            if (current.value->is_object())
-            {
-                const auto& object = *current.value->m_data.m_value.object;
-                while (nested == nullptr && current.member != object.cend())
-                {
-                    const auto& el = *current.member;
-                    ++current.member;
-                    if (el.second.is_structured())
-                    {
-                        nested_name = &el.first;
-                        nested = &el.second;
-                    }
-                    else
-                    {
-                        write_bson_value(el.first, el.second);
-                    }
-                }
-            }
-            else
-            {
-                const auto& array = *current.value->m_data.m_value.array;
-                while (nested == nullptr && current.index < array.size())
-                {
-                    const BasicJsonType& el = array[current.index];
-                    create_bson_index_name(current.index, index_name);
-                    ++current.index;
-                    if (el.is_structured())
-                    {
-                        nested_name = &index_name;
-                        nested = &el;
-                    }
-                    else
-                    {
-                        write_bson_value(index_name, el);
-                    }
-                }
-            }
-
-            if (nested != nullptr)
-            {
-                write_bson_entry_header(*nested_name, nested->is_object() ? 0x03 : 0x04);
-                write_number<std::int32_t>(to_bson_length(nested_sizes[next_size++]), true);
-                parents.push_back(std::move(current));
-                current = bson_frame(nested);
-                continue;
-            }
-
-            oa.write_character(to_char_type(0x00));
-            if (parents.empty())
-            {
-                return;
-            }
-            current = std::move(parents.back());
-            parents.pop_back();
-        }
+        oa.write_character(to_char_type(0x00));
     }
 
     //////////
@@ -25555,7 +25436,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     using copy_worklist_t = std::vector<std::pair<const basic_json*, basic_json*>>;
 
     /// scratch space to build the key skeleton of an object copy in one go
-    using copy_scratch_t = std::vector<std::pair<typename object_t::key_type, basic_json>>;
+    using copy_scratch_value_t = std::pair<typename object_t::key_type, basic_json>;
+    using copy_scratch_t = std::vector<copy_scratch_value_t, AllocatorType<copy_scratch_value_t>>;
 
     /// @brief copy everything of @a src into @a dst but its type and value
     static void copy_metadata(const basic_json& src, basic_json& dst)

tests/src/unit-allocator.cpp

@@ -270,6 +270,82 @@ TEST_CASE("controlled bad_alloc")
     }
 }
 
+namespace
+{
+// counts the allocations of pairs with a non-const first member: the object
+// types store std::pair<const Key, T>, so only the scratch space of the
+// iterative deep copy allocates std::pair<Key, T>
+std::size_t scratch_pair_allocations = 0;
+
+template<class T>
+struct is_scratch_pair : std::false_type {};
+
+template<class K, class V>
+struct is_scratch_pair<std::pair<K, V>> : std::integral_constant < bool, !std::is_const<K>::value > {};
+
+template<class T>
+struct scratch_counting_allocator : std::allocator<T>
+{
+    using std::allocator<T>::allocator;
+
+    T* allocate(std::size_t n)
+    {
+        if (is_scratch_pair<T>::value)
+        {
+            ++scratch_pair_allocations;
+        }
+        return std::allocator<T>::allocate(n);
+    }
+
+#ifdef __cpp_lib_allocate_at_least
+    // std::allocator<T>::allocate_at_least would bypass the counting, and
+    // libc++'s containers prefer it over allocate from C++23 on
+    auto allocate_at_least(std::size_t n)
+    {
+        if (is_scratch_pair<T>::value)
+        {
+            ++scratch_pair_allocations;
+        }
+        return std::allocator<T>::allocate_at_least(n);
+    }
+#endif
+
+    template <class U>
+    struct rebind
+    {
+        using other = scratch_counting_allocator<U>;
+    };
+};
+} // namespace
+
+TEST_CASE("deep copy uses the provided allocator")
+{
+    using counting_json = nlohmann::basic_json<std::map,
+          std::vector,
+          std::string,
+          bool,
+          std::int64_t,
+          std::uint64_t,
+          double,
+          scratch_counting_allocator>;
+
+    // deeper than the 128 levels the copy constructor descends into, so the
+    // innermost objects are copied by the iterative deep copy
+    counting_json j = 1;
+    for (std::size_t i = 0; i < 300; ++i)
+    {
+        counting_json wrapper = counting_json::object();
+        wrapper["a"] = std::move(j);
+        j = std::move(wrapper);
+    }
+
+    scratch_pair_allocations = 0;
+    // NOLINTNEXTLINE(performance-unnecessary-copy-initialization): the copy is what is tested
+    const counting_json copy(j);
+    CHECK(scratch_pair_allocations > 0);
+    CHECK(copy == j);
+}
+
 namespace
 {
 template<class T>

tests/src/unit-bson.cpp

@@ -49,7 +49,7 @@ using huge_binary_json = nlohmann::basic_json <
 // for *object keys* (e.g. "s" or "nested" below). Only the designated test
 // value is meant to lie about its size - if every huge_string_t (including
 // keys) reported a huge size, the running totals computed while walking the
-// BSON document (see calc_bson_sizes in binary_writer.hpp)
+// BSON document (see calc_bson_object_size & friends in binary_writer.hpp)
 // would need more than 32 bits, and on platforms where std::size_t is only
 // 32 bits wide that arithmetic would silently wrap around, producing wrong
 // (or even unguarded) lengths. The fake size is therefore opt-in via
@@ -1697,67 +1697,3 @@ TEST_CASE("BSON roundtrips" * doctest::skip())
         }
     }
 }
-
-TEST_CASE("BSON: deeply nested values")
-{
-    SECTION("documents and arrays round-trip at every depth")
-    {
-        // nested documents and arrays, with siblings on every level, so
-        // every length prefix covers entries of both kinds
-        json value = "leaf";
-        for (std::size_t depth = 0; depth <= 300; ++depth)
-        {
-            CAPTURE(depth);
-            const json document = {{"value", value}, {"n", depth}};
-            CHECK(json::from_bson(json::to_bson(document)) == document);
-
-value = depth % 2 == 0 ? json{{"a", std::move(value)}, {"b", {1, "x"}}} :
-            json::array({std::move(value), depth, json::object()});
-        }
-    }
-
-    SECTION("a key containing U+0000 is rejected before anything is written")
-    {
-        json value = json::object({{std::string("bad\0key", 7), 1}});
-        for (std::size_t depth = 0; depth < 200; ++depth)
-        {
-            value = json{{"a", {{"b", 1}}}, {"z", std::move(value)}};
-        }
-        std::vector<std::uint8_t> output;
-        CHECK_THROWS_AS(json::to_bson(value, output), json::out_of_range&);
-        CHECK(output.empty());
-    }
-
-    SECTION("values nested too deeply for the call stack (#5392)")
-    {
-        // serializing recursed once per nesting level, and computed every
-        // nested document's length by walking everything below it again.
-        // The values are only parsed, serialized and walked, never copied or
-        // compared, since those recurse too.
-        const std::size_t depth = 100000;
-        for (const bool objects :
-                {
-                    false, true
-                })
-        {
-            CAPTURE(objects);
-            std::string text = "{\"a\":";
-            for (std::size_t i = 0; i < depth; ++i)
-            {
-                text += objects ? "{\"a\":" : "[";
-            }
-            text += "1";
-            text.append(depth, objects ? '}' : ']');
-            text += "}";
-
-            const auto bson = json::to_bson(json::parse(text));
-            const auto result = json::from_bson(bson);
-            const json* p = &result.at("a");
-            for (std::size_t i = 0; i < depth; ++i)
-            {
-                p = objects ? &p->at("a") : &p->at(0);
-            }
-            CHECK(*p == 1);
-        }
-    }
-}

tests/src/unit-merge_patch.cpp

@@ -62,7 +62,7 @@ std::string nested_objects(const std::size_t depth, const int variant)
         }
         text += "\"a\":";
     }
-    text += variant == 1 ? "{\"x\":1,\"y\":null}" : "{\"y\":2}";
+    text += variant == 1 ? R"({"x":1,"y":null})" : "{\"y\":2}";
     text.append(depth, '}');
     return text;
 }

tests/src/unit-modifiers.cpp

@@ -48,7 +48,7 @@ std::string nested_objects(const std::size_t depth, const int variant)
         if (variant == 2 && i % 5 == 0)
         {
             // an object replacing a primitive, which is not merged
-            text += "\"s0\":{\"o\":1},";
+            text += R"("s0":{"o":1},)";
         }
         text += "\"a\":";
     }