BSON writer: write to_bson(j) in one pass, with sizes written afterwards

BSON prefixes every document and array with its size. to_bson() therefore
walked the value twice: once to compute every size, once to write. When
the output is the vector that to_bson(j) returns, the writer now puts a
placeholder in front of each document and array and writes its size there
once the document is complete, so one walk is enough.

Every key and value is still checked as the size pass checked it, in the
same order, so the same exception is thrown; the partial output is
discarded with the vector. If a length would not fit BSON's 32-bit size
fields, the writer drops what it has written and writes the document in
two passes, which reports that error before writing anything, as before.

The two passes remain for output adapters (streams, strings, vectors
passed by reference), for error_handler_t::replace and ignore (which
change sizes), and for integer types wider than 64 bits.

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

include/nlohmann/detail/input/binary_reader.hpp

@@ -22,7 +22,6 @@
     #include <bit>  //byteswap
 #endif
 
-#include <nlohmann/detail/bit_ops.hpp>
 #include <nlohmann/detail/exceptions.hpp>
 #include <nlohmann/detail/input/input_adapters.hpp>
 #include <nlohmann/detail/input/json_sax.hpp>
@@ -742,13 +741,11 @@ class binary_reader
     bool get_cbor_negative_integer()
     {
         NumberType number{};
-        return get_number(number) && emit_cbor_negative_integer(number);
+        if (JSON_HEDLEY_UNLIKELY(!get_number(number)))
-    }
+        {
+            return false;
+        }
 
-    /// pass the CBOR negative integer -1 - @a number to the SAX parser
-    template<typename NumberType>
-    bool emit_cbor_negative_integer(const NumberType number)
-    {
         // the value is -1 - number, which fits into number_integer_t
         // whenever number does; the outer cast undoes the integral promotion
         // for number_integer_t types narrower than int
@@ -973,7 +970,7 @@ class binary_reader
             case 0x95:
             case 0x96:
             case 0x97:
-                return enter_cbor_array(conditional_static_cast<std::size_t>(static_cast<unsigned int>(current) & 0x1Fu));
+                return enter_array(conditional_static_cast<std::size_t>(static_cast<unsigned int>(current) & 0x1Fu));
 
             case 0x98: // array (one-byte uint8_t for n follows)
             case 0x99: // array (two-byte uint16_t for n follow)
@@ -982,7 +979,7 @@ class binary_reader
             {
                 std::uint64_t len{};
                 std::size_t size{};
-                return get_cbor_argument(len) && get_cbor_container_size(len, size, "array") && enter_cbor_array(size);
+                return get_cbor_argument(len) && get_cbor_container_size(len, size, "array") && enter_array(size);
             }
 
             case 0x9F: // array (indefinite length)
@@ -1136,10 +1133,16 @@ class binary_reader
                 return get_half_float(false);
 
             case 0xFA: // Single-Precision Float (four-byte IEEE 754)
-                return get_cbor_float<float>();
+            {
+                float number{};
+                return get_number(number) && emit_float(number);
+            }
 
             case 0xFB: // Double-Precision Float (eight-byte IEEE 754)
-                return get_cbor_float<double>();
+            {
+                double number{};
+                return get_number(number) && emit_float(number);
+            }
 
             default: // anything else (0xFF is handled inside the other types)
             {
@@ -1148,16 +1151,6 @@ class binary_reader
         }
     }
 
-    /// read a single- or double-precision float (kept out of
-    /// parse_cbor_value, which is inlined into parse_cbor_internal)
-    template<typename NumberType>
-    JSON_HEDLEY_NEVER_INLINE
-    bool get_cbor_float()
-    {
-        NumberType number{};
-        return get_number(number) && emit_float(number);
-    }
-
     /*!
     @brief reports a nested indefinite-length CBOR string or byte array
     @param[in] type_name  name of the rejected string type
@@ -1683,157 +1676,6 @@ class binary_reader
         return true;
     }
 
-    /*!
-    @brief read a big-endian number of type @a NumberType at @a data
-    */
-    template<typename NumberType>
-    NumberType load_big_endian(const unsigned char* data) const noexcept
-    {
-        NumberType result{};
-        std::memcpy(&result, data, sizeof(NumberType));
-        if (is_little_endian)
-        {
-            byte_swap(result);
-        }
-        return result;
-    }
-
-    /*!
-    @brief read the integers, floats, booleans, and nulls that follow in a
-           definite-length array, without the per-element bookkeeping of
-           @ref parse_cbor_internal
-
-    Stops at the end of the array, at any other kind of value, and when fewer
-    than 9 bytes (the longest of these values) are left in the input, leaving
-    those to @ref parse_cbor_value, which reads them the same way.
-
-    @param[in,out] remaining  the number of elements of the array not yet read
-    @return whether the SAX parser accepted the values
-    */
-    bool parse_cbor_scalar_run(std::size_t& remaining)
-    {
-        while (remaining != 0 && ia.bulk_remaining() >= 9)
-        {
-            const auto* const data = reinterpret_cast<const unsigned char*>(ia.bulk_data());
-            const unsigned char head = data[0];
-            std::size_t size = 0;
-            bool accepted = true;
-            switch (head)
-            {
-                case 0x18:
-                    size = 2;
-                    accepted = emit_unsigned(data[1]);
-                    break;
-                case 0x19:
-                    size = 3;
-                    accepted = emit_unsigned(load_big_endian<std::uint16_t>(data + 1));
-                    break;
-                case 0x1A:
-                    size = 5;
-                    accepted = emit_unsigned(load_big_endian<std::uint32_t>(data + 1));
-                    break;
-                case 0x1B:
-                    size = 9;
-                    accepted = emit_unsigned(load_big_endian<std::uint64_t>(data + 1));
-                    break;
-                case 0x38:
-                    size = 2;
-                    accepted = emit_cbor_negative_integer(data[1]);
-                    break;
-                case 0x39:
-                    size = 3;
-                    accepted = emit_cbor_negative_integer(load_big_endian<std::uint16_t>(data + 1));
-                    break;
-                case 0x3A:
-                    size = 5;
-                    accepted = emit_cbor_negative_integer(load_big_endian<std::uint32_t>(data + 1));
-                    break;
-                case 0x3B:
-                    size = 9;
-                    accepted = emit_cbor_negative_integer(load_big_endian<std::uint64_t>(data + 1));
-                    break;
-                case 0xF4:
-                    size = 1;
-                    accepted = sax->boolean(false);
-                    break;
-                case 0xF5:
-                    size = 1;
-                    accepted = sax->boolean(true);
-                    break;
-                case 0xF6:
-                    size = 1;
-                    accepted = sax->null();
-                    break;
-                case 0xFA:
-                    size = 5;
-                    accepted = emit_float(load_big_endian<float>(data + 1));
-                    break;
-                case 0xFB:
-                    size = 9;
-                    accepted = emit_float(load_big_endian<double>(data + 1));
-                    break;
-                default:
-                    if (head <= 0x17)
-                    {
-                        size = 1;
-                        accepted = sax->number_unsigned(static_cast<number_unsigned_t>(head));
-                    }
-                    else if (head >= 0x20 && head <= 0x37)
-                    {
-                        size = 1;
-                        accepted = sax->number_integer(static_cast<std::int8_t>(0x20 - 1 - head));
-                    }
-                    else
-                    {
-                        // any other value is read by parse_cbor_value
-                        return true;
-                    }
-                    break;
-            }
-            // as if read by get() and get_number(): current is the head byte
-            ia.bulk_skip(size);
-            chars_read += size;
-            current = head;
-            --remaining;
-            if (JSON_HEDLEY_UNLIKELY(!accepted))
-            {
-                return false;
-            }
-        }
-        return true;
-    }
-
-    /*!
-    @brief open a definite-length array and read the scalars it begins with
-           (see @ref parse_cbor_scalar_run)
-
-    Only the start of an array is tried, which covers arrays of numbers
-    (e.g. coordinates) but costs arrays of other values only one test, not one
-    per element.
-
-    @param[in] len  the number of elements
-    @return whether the SAX parser accepted the array and the values read
-    */
-    bool enter_cbor_array(const std::size_t len)
-    {
-        return enter_array(len) && (len == 0 || parse_cbor_array_start(std::integral_constant<bool, bulk_scan> {}));
-    }
-
-    /// read the scalars the array just opened begins with; out of line, so
-    /// that @ref parse_cbor_value stays small enough to be inlined into
-    /// @ref parse_cbor_internal
-    JSON_HEDLEY_NEVER_INLINE
-    bool parse_cbor_array_start(std::true_type /*bulk*/)
-    {
-        return parse_cbor_scalar_run(container_stack.back().remaining);
-    }
-
-    /// input that is not contiguous: every value is read by parse_cbor_value
-    bool parse_cbor_array_start(std::false_type /*bulk*/) const noexcept
-    {
-        return true;
-    }
-
     /*!
     @brief read a CBOR value and everything nested inside it
 
@@ -1863,7 +1705,6 @@ class binary_reader
                 // pop_back() below, which destroys the container_stack element
                 // it would otherwise alias
                 const container_frame top = container_stack.back();
-                const bool is_object = top.is_object;
                 bool at_end = false;
 
                 if (top.remaining != npos)
@@ -1875,7 +1716,7 @@ class binary_reader
                     {
                         // claim the element about to be read
                         --container_stack.back().remaining;
-                        if (is_object)
+                        if (top.is_object)
                         {
                             get();
                         }
@@ -1888,7 +1729,7 @@ class binary_reader
                     // 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 = is_object;
+                    fetch = top.is_object;
                 }
 
                 if (at_end)
@@ -1905,7 +1746,7 @@ class binary_reader
                     continue;
                 }
 
-                if (is_object)
+                if (top.is_object)
                 {
                     if (JSON_HEDLEY_UNLIKELY(!skip_cbor_key_tags(tag_handler)))
                     {
@@ -2130,7 +1971,7 @@ class binary_reader
             case 0x9D:
             case 0x9E:
             case 0x9F:
-                return enter_msgpack_array(conditional_static_cast<std::size_t>(static_cast<unsigned int>(current) & 0x0Fu));
+                return enter_array(conditional_static_cast<std::size_t>(static_cast<unsigned int>(current) & 0x0Fu));
 
             // fixstr
             case 0xA0:
@@ -2261,13 +2102,13 @@ class binary_reader
             case 0xDC: // array 16
             {
                 std::uint16_t len{};
-                return get_number(len) && enter_msgpack_array(static_cast<std::size_t>(len));
+                return get_number(len) && enter_array(static_cast<std::size_t>(len));
             }
 
             case 0xDD: // array 32
             {
                 std::uint32_t len{};
-                return get_number(len) && enter_msgpack_array(conditional_static_cast<std::size_t>(len));
+                return get_number(len) && enter_array(conditional_static_cast<std::size_t>(len));
             }
 
             case 0xDE: // map 16
@@ -2609,138 +2450,6 @@ class binary_reader
         }
     }
 
-    /*!
-    @brief read the integers, floats, booleans, and nils that follow in a
-           MessagePack array, without the per-element bookkeeping of
-           @ref parse_msgpack_internal
-
-    Stops at the end of the array, at any other kind of value, and when fewer
-    than 9 bytes (the longest of these values) are left in the input, leaving
-    those to @ref parse_msgpack_value, which reads them the same way.
-
-    @param[in,out] remaining  the number of elements of the array not yet read
-    @return whether the SAX parser accepted the values
-    */
-    bool parse_msgpack_scalar_run(std::size_t& remaining)
-    {
-        while (remaining != 0 && ia.bulk_remaining() >= 9)
-        {
-            const auto* const data = reinterpret_cast<const unsigned char*>(ia.bulk_data());
-            const unsigned char head = data[0];
-            std::size_t size = 0;
-            bool accepted = true;
-            switch (head)
-            {
-                case 0xC0: // nil
-                    size = 1;
-                    accepted = sax->null();
-                    break;
-                case 0xC2: // false
-                    size = 1;
-                    accepted = sax->boolean(false);
-                    break;
-                case 0xC3: // true
-                    size = 1;
-                    accepted = sax->boolean(true);
-                    break;
-                case 0xCA: // float 32
-                    size = 5;
-                    accepted = emit_float(load_big_endian<float>(data + 1));
-                    break;
-                case 0xCB: // float 64
-                    size = 9;
-                    accepted = emit_float(load_big_endian<double>(data + 1));
-                    break;
-                case 0xCC: // uint 8
-                    size = 2;
-                    accepted = emit_unsigned(data[1]);
-                    break;
-                case 0xCD: // uint 16
-                    size = 3;
-                    accepted = emit_unsigned(load_big_endian<std::uint16_t>(data + 1));
-                    break;
-                case 0xCE: // uint 32
-                    size = 5;
-                    accepted = emit_unsigned(load_big_endian<std::uint32_t>(data + 1));
-                    break;
-                case 0xCF: // uint 64
-                    size = 9;
-                    accepted = emit_unsigned(load_big_endian<std::uint64_t>(data + 1));
-                    break;
-                case 0xD0: // int 8
-                    size = 2;
-                    accepted = emit_signed(static_cast<std::int8_t>(data[1]));
-                    break;
-                case 0xD1: // int 16
-                    size = 3;
-                    accepted = emit_signed(load_big_endian<std::int16_t>(data + 1));
-                    break;
-                case 0xD2: // int 32
-                    size = 5;
-                    accepted = emit_signed(load_big_endian<std::int32_t>(data + 1));
-                    break;
-                case 0xD3: // int 64
-                    size = 9;
-                    accepted = emit_signed(load_big_endian<std::int64_t>(data + 1));
-                    break;
-                default:
-                    if (head <= 0x7F)
-                    {
-                        // positive fixint
-                        size = 1;
-                        accepted = sax->number_unsigned(static_cast<number_unsigned_t>(head));
-                    }
-                    else if (head >= 0xE0)
-                    {
-                        // negative fixint
-                        size = 1;
-                        accepted = sax->number_integer(static_cast<std::int8_t>(head));
-                    }
-                    else
-                    {
-                        // any other value is read by parse_msgpack_value
-                        return true;
-                    }
-                    break;
-            }
-            // as if read by get() and get_number(): current is the last byte
-            ia.bulk_skip(size);
-            chars_read += size;
-            current = data[size - 1];
-            --remaining;
-            if (JSON_HEDLEY_UNLIKELY(!accepted))
-            {
-                return false;
-            }
-        }
-        return true;
-    }
-
-    /*!
-    @brief open a MessagePack array and read the scalars it begins with (see
-           @ref parse_msgpack_scalar_run)
-    @param[in] len  the number of elements
-    @return whether the SAX parser accepted the array and the values read
-    */
-    bool enter_msgpack_array(const std::size_t len)
-    {
-        return enter_array(len) && (len == 0 || parse_msgpack_array_start(std::integral_constant<bool, bulk_scan> {}));
-    }
-
-    /// read the scalars the array just opened begins with; out of line, so
-    /// that @ref parse_msgpack_value stays small enough to be inlined
-    JSON_HEDLEY_NEVER_INLINE
-    bool parse_msgpack_array_start(std::true_type /*bulk*/)
-    {
-        return parse_msgpack_scalar_run(container_stack.back().remaining);
-    }
-
-    /// input that is not contiguous: every value is read by parse_msgpack_value
-    bool parse_msgpack_array_start(std::false_type /*bulk*/) const noexcept
-    {
-        return true;
-    }
-
     /*!
     @brief read a MessagePack value and everything nested inside it
 
@@ -3982,13 +3691,13 @@ class binary_reader
                 return sax->null();
 
             case 0xFB:
-                return sax->number_float(static_cast<number_float_t>(-1.0), no_source);
+                return sax->number_float(static_cast<number_float_t>(-1.0), "");
 
             case 0xFC:
-                return sax->number_float(static_cast<number_float_t>(0.0), no_source);
+                return sax->number_float(static_cast<number_float_t>(0.0), "");
 
             case 0xFD:
-                return sax->number_float(static_cast<number_float_t>(1.0), no_source);
+                return sax->number_float(static_cast<number_float_t>(1.0), "");
 
             case 0xFF: // empty string
             {
@@ -4357,27 +4066,6 @@ class binary_reader
         return current;
     }
 
-    /// reverse the byte order of a double with a single byteswap(): GCC does
-    /// not merge the byte-wise swap of the generic version into one
-    static void byte_swap(double& number) noexcept
-    {
-        static_assert(sizeof(double) == sizeof(std::uint64_t), "double must have 64 bits");
-        std::uint64_t bits{};
-        std::memcpy(&bits, &number, sizeof(bits));
-        bits = byteswap(bits);
-        std::memcpy(&number, &bits, sizeof(bits));
-    }
-
-    /// reverse the byte order of a float with a single byteswap()
-    static void byte_swap(float& number) noexcept
-    {
-        static_assert(sizeof(float) == sizeof(std::uint32_t), "float must have 32 bits");
-        std::uint32_t bits{};
-        std::memcpy(&bits, &number, sizeof(bits));
-        bits = byteswap(bits);
-        std::memcpy(&number, &bits, sizeof(bits));
-    }
-
     template<class NumberType>
     static void byte_swap(NumberType& number)
     {
@@ -4513,7 +4201,7 @@ class binary_reader
         {
             return out_of_range_error(exception_id::number_overflow, "number overflow", "value");
         }
-        return sax->number_float(result, no_source);
+        return sax->number_float(result, "");
     }
 
     /*!
@@ -4573,7 +4261,7 @@ class binary_reader
         }();
         return sax->number_float((half & 0x8000u) != 0
                                  ? static_cast<number_float_t>(-val)
-                                 : static_cast<number_float_t>(val), no_source);
+                                 : static_cast<number_float_t>(val), "");
     }
 
     /*!
@@ -4898,10 +4586,6 @@ class binary_reader
     /// the SAX parser
     json_sax_t* sax = nullptr;
 
-    /// the (empty) source text of every number_float event: binary formats
-    /// have none, and a string_t built for each float would cost more
-    const string_t no_source{};
-
     /// the containers that have been opened and not closed yet; see @ref container_frame
     std::vector<container_frame> container_stack{};
 

include/nlohmann/detail/output/binary_writer.hpp

@@ -2088,7 +2088,8 @@ class binary_writer
         /// arrays: the first index with one more digit; only maintained by
         /// @ref calc_bson_sizes
         std::uint64_t index_boundary = 10;
-        /// @ref calc_bson_sizes only: where its size goes in the table
+        /// @ref calc_bson_sizes: where its size goes in the table; @ref
+        /// write_bson_document_single_pass: the position of its size field
         std::size_t size_slot;
         /// @ref calc_bson_sizes only: the size of its entries seen so far
         std::size_t entries_size = 0;
@@ -2339,6 +2340,197 @@ class binary_writer
         }
     }
 
+    template<typename SinkType>
+    using sink_written_t = decltype(std::declval<const SinkType&>().written());
+
+    /*!
+    @brief whether BSON documents can be written in a single pass: the sink
+           can overwrite what it has written (output_vector_sink), and every
+           integer fits the 64 bits BSON has, so that writing an array of
+           numbers needs no range check
+    */
+    using bson_single_pass_sink = std::integral_constant < bool,
+          is_detected<sink_written_t, OutputSinkType>::value
+          && std::numeric_limits<typename BasicJsonType::number_integer_t>::is_specialized
+          && std::numeric_limits<typename BasicJsonType::number_integer_t>::digits <= std::numeric_limits<std::int64_t>::digits
+          && std::numeric_limits<typename BasicJsonType::number_unsigned_t>::is_specialized
+          && std::numeric_limits<typename BasicJsonType::number_unsigned_t>::digits <= std::numeric_limits<std::uint64_t>::digits >;
+
+    /// write a placeholder for the size of an object or array whose entries
+    /// follow; @return its position, for @ref patch_bson_size
+    std::size_t write_bson_size_placeholder()
+    {
+        const std::size_t pos = oa.written();
+        write_number<std::int32_t>(0, true);
+        return pos;
+    }
+
+    /// end the object or array whose size is at @a pos and write its size
+    /// there: everything from that field to the terminating null byte
+    /// @return false (and the size is not written) if it does not fit
+    bool close_bson_container(const std::size_t pos)
+    {
+        oa.write_character(to_char_type(0x00));
+        const std::size_t size = oa.written() - pos;
+        if (JSON_HEDLEY_UNLIKELY(!value_in_range_of<std::int32_t>(size)))
+        {
+            return false;
+        }
+        std::array<CharType, sizeof(std::int32_t)> bytes{};
+        store_little_endian<std::int32_t>(bytes.data(), static_cast<std::int32_t>(size));
+        oa.overwrite(pos, bytes.data(), bytes.size());
+        return true;
+    }
+
+    /*!
+    @brief check the value @a j of a BSON entry as @ref calc_bson_value_size
+           does, for @ref write_bson_document_single_pass
+    @return at least the size of the value
+    A number, boolean, or null needs no check there (its integers have at most
+    64 bits) and has at most 8 characters; a discarded value is rejected with
+    the same exception when it is written.
+    */
+    std::size_t check_bson_value(const BasicJsonType& j)
+    {
+        return (j.is_string() || j.is_binary()) ? calc_bson_value_size(j) : 8;
+    }
+
+    /// whether an entry of @a entry_size characters keeps the document that
+    /// begins at @a start, closed by @a open_containers null bytes, within
+    /// the 32-bit size of BSON
+    bool bson_entry_fits(const std::size_t start, const std::size_t entry_size, const std::size_t open_containers) const noexcept
+    {
+        const std::size_t limit = static_cast<std::size_t>((std::numeric_limits<std::int32_t>::max)());
+        const std::size_t written = oa.written() - start;
+        return written <= limit && entry_size <= limit - written && open_containers <= limit - written - entry_size;
+    }
+
+    /*!
+    @brief Serializes the JSON object @a document as a BSON document in a
+           single pass, writing the size of each object and array once it is
+           complete
+
+    Checks every key and value as @ref calc_bson_sizes does, in the same
+    order, so the same exception is thrown; the output written up to then is
+    discarded with the vector it was written to.
+
+    @return false as soon as the document or a string, binary value, object,
+            or array in it would be larger than the 32-bit BSON sizes allow;
+            nothing large has been written then, and the caller writes the
+            document in two passes, which reports that error
+    */
+    template < typename SinkType = OutputSinkType,
+               typename std::enable_if < is_detected<sink_written_t, SinkType>::value, int >::type = 0 >
+    bool write_bson_document_single_pass(const BasicJsonType& document)
+    {
+        const std::size_t start = oa.written();
+        // the object or array whose entries are being written (with the
+        // position of its size), and the ones it is in
+        bson_frame current(&document, write_bson_size_placeholder());
+        std::vector<bson_frame> parents;
+
+        while (true)
+        {
+            const BasicJsonType* nested = nullptr;
+            std::size_t nested_size_pos = 0;
+            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;
+                    const std::size_t header_size = calc_bson_entry_header_size(el.first, el.second);
+                    const std::size_t value_size = el.second.is_structured() ? 0 : check_bson_value(el.second);
+                    if (JSON_HEDLEY_UNLIKELY(!bson_entry_fits(start, header_size + value_size, parents.size() + 1)))
+                    {
+                        return false;
+                    }
+                    if (el.second.is_structured())
+                    {
+                        write_bson_entry_header(el.first, el.second.is_object() ? 0x03 : 0x04);
+                        nested_size_pos = write_bson_size_placeholder();
+                        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())
+                {
+                    if (is_bson_fixed_size(array[current.index]))
+                    {
+                        write_bson_array_fixed_entries(current);
+                        if (current.index == array.size())
+                        {
+                            break;
+                        }
+                    }
+
+                    // a string, binary value, object or array
+                    const BasicJsonType& el = array[current.index];
+                    const string_t index_name(current.index_name.data(), current.index_name_size);
+                    current.next_index();
+                    const std::size_t value_size = el.is_structured() ? 0 : check_bson_value(el);
+                    if (JSON_HEDLEY_UNLIKELY(!bson_entry_fits(start, 2 + index_name.size() + value_size, parents.size() + 1)))
+                    {
+                        return false;
+                    }
+                    if (el.is_structured())
+                    {
+                        write_bson_entry_header(index_name, el.is_object() ? 0x03 : 0x04);
+                        nested_size_pos = write_bson_size_placeholder();
+                        nested = &el;
+                    }
+                    else
+                    {
+                        write_bson_value(index_name, el);
+                    }
+                }
+            }
+
+            if (nested != nullptr)
+            {
+                if (nested->is_array())
+                {
+                    // an array of booleans, numbers and null is written without a frame on the stack
+                    bson_frame leaf(nested, nested_size_pos);
+                    write_bson_array_fixed_entries(leaf);
+                    if (leaf.index == nested->m_data.m_value.array->size())
+                    {
+                        if (JSON_HEDLEY_UNLIKELY(!close_bson_container(nested_size_pos)))
+                        {
+                            return false;
+                        }
+                        continue;
+                    }
+                    parents.push_back(std::move(current));
+                    current = std::move(leaf);
+                    continue;
+                }
+                parents.push_back(std::move(current));
+                current = bson_frame(nested, nested_size_pos);
+                continue;
+            }
+
+            if (JSON_HEDLEY_UNLIKELY(!close_bson_container(current.size_slot)))
+            {
+                return false;
+            }
+            if (parents.empty())
+            {
+                return true;
+            }
+            current = std::move(parents.back());
+            parents.pop_back();
+        }
+    }
+
     /*!
     @brief Serializes the JSON object @a document as a BSON document
 
@@ -2350,6 +2542,39 @@ class binary_writer
     @pre       document.type() == value_t::object
     */
     void write_bson_document(const BasicJsonType& document)
+    {
+        write_bson_document(document, bson_single_pass_sink());
+    }
+
+    /// the sink can overwrite: one pass, unless the error handler replaces or
+    /// drops ill-formed UTF-8, which changes the sizes the checks compute
+    void write_bson_document(const BasicJsonType& document, std::true_type /*single_pass*/)
+    {
+        const std::size_t start = oa.written();
+        if ((error_handler == error_handler_t::keep || error_handler == error_handler_t::strict)
+                && write_bson_document_single_pass(document))
+        {
+            return;
+        }
+        // a length does not fit: start over, so that it is reported as the
+        // two passes report it, before anything is written
+        oa.rewind(start);
+        write_bson_document_two_pass(document);
+    }
+
+    void write_bson_document(const BasicJsonType& document, std::false_type /*single_pass*/)
+    {
+        write_bson_document_two_pass(document);
+    }
+
+    /*!
+    @brief Serializes the JSON object @a document as a BSON document: the
+           sizes of all objects and arrays first, then the entries
+
+    @param[in] document  the JSON object to serialize
+    @pre       document.type() == value_t::object
+    */
+    void write_bson_document_two_pass(const BasicJsonType& document)
     {
         std::vector<std::size_t> nested_sizes;
         const std::size_t document_size = calc_bson_sizes(document, nested_sizes);

include/nlohmann/detail/output/output_adapters.hpp

@@ -227,6 +227,29 @@ class output_vector_sink
     void flush() noexcept
     {}
 
+    /// the number of characters written so far, the position of the next one
+    std::size_t written() const noexcept
+    {
+        return position();
+    }
+
+    /// @brief replace @a length characters written before, from position @a pos
+    ///
+    /// Lets a writer put a length in front of data it has written since, such
+    /// as the size of a BSON document, without computing it in advance.
+    void overwrite(const std::size_t pos, const CharType* s, const std::size_t length) noexcept
+    {
+        JSON_ASSERT(pos + length <= position());
+        std::memcpy(v->data() + pos, s, length * sizeof(CharType));
+    }
+
+    /// drop the characters written from position @a pos on
+    void rewind(const std::size_t pos) noexcept
+    {
+        JSON_ASSERT(pos <= position());
+        cursor = v->data() + pos;
+    }
+
   private:
     /// number of characters of *v written so far
     std::size_t position() const noexcept

tests/src/unit-bson.cpp

@@ -2267,3 +2267,132 @@ TEST_CASE("BSON large strings and binaries (chunked reader)")
         }
     }
 }
+
+TEST_CASE("BSON written in one pass and in two passes")
+{
+    // to_bson() into a returned vector writes each size once the object or
+    // array is complete; through an output adapter, all sizes are computed
+    // first. Both must produce the same bytes and throw the same exceptions.
+    const auto two_pass = [](const json & j, const json::error_handler_t handler)
+    {
+        std::vector<std::uint8_t> result;
+        json::to_bson(j, result, handler);
+        return result;
+    };
+
+    const auto check_same = [&](const json & j, const json::error_handler_t handler)
+    {
+        CAPTURE(j.dump(-1, ' ', true, json::error_handler_t::replace))
+        CAPTURE(static_cast<int>(handler))
+#if !defined(JSON_NOEXCEPTION)
+        std::string one_pass_error;
+        std::string two_pass_error;
+        std::vector<std::uint8_t> one;
+        std::vector<std::uint8_t> two;
+        try
+        {
+            one = json::to_bson(j, handler);
+        }
+        catch (const json::exception& e)
+        {
+            one_pass_error = e.what();
+        }
+        try
+        {
+            two = two_pass(j, handler);
+        }
+        catch (const json::exception& e)
+        {
+            two_pass_error = e.what();
+        }
+        CHECK(one_pass_error == two_pass_error);
+        CHECK(one == two);
+#else
+        CHECK(json::to_bson(j, handler) == two_pass(j, handler));
+#endif
+    };
+
+    const json::error_handler_t handlers[] = {json::error_handler_t::keep, json::error_handler_t::strict,
+                                              json::error_handler_t::replace, json::error_handler_t::ignore
+                                             };
+
+    SECTION("corpus")
+    {
+        for (const auto& value : utils::round_trip_corpus::values())
+        {
+            const json document = value.is_object() ? value : json{{"value", value}};
+            for (const auto handler : handlers)
+            {
+                check_same(document, handler);
+            }
+        }
+    }
+
+    SECTION("nesting and arrays of every length class")
+    {
+        json document = json::object();
+        document["empty object"] = json::object();
+        document["empty array"] = json::array();
+        for (const std::size_t n :
+                {
+                    std::size_t(1), std::size_t(9), std::size_t(10), std::size_t(11), std::size_t(99), std::size_t(100), std::size_t(101), std::size_t(1000)
+                })
+        {
+            json numbers = json::array();
+            json mixed = json::array();
+            for (std::size_t i = 0; i < n; ++i)
+            {
+                numbers.push_back(i % 3 == 0 ? json(static_cast<double>(i) / 3) : json(static_cast<std::int64_t>(i) * 1000003));
+                mixed.push_back(i % 4 == 0 ? json("s" + std::to_string(i)) : i % 4 == 1 ? json::array({i, json::object({{"k", i}})}) : i % 4 == 2 ? json(nullptr) : json(i % 2 == 0));
+            }
+            document["numbers " + std::to_string(n)] = numbers;
+            document["mixed " + std::to_string(n)] = mixed;
+            document["nested " + std::to_string(n)] = json::object({{"a", numbers}, {"b", json::array({mixed, json::object()})}});
+        }
+        document["binary"] = json::binary({1, 2, 3}, 0x80);
+        document["binary old"] = json::binary({1, 2, 3}, 0x02);
+        for (const auto handler : handlers)
+        {
+            check_same(document, handler);
+        }
+    }
+
+    SECTION("errors at every position")
+    {
+        // an entry that cannot be written, at each place among valid ones
+        const std::string bad_utf8 = "\xC3\x28";
+        const json bad_entries[] =
+        {
+            json::object({{std::string("a\0b", 3), 1}}),
+            json::object({{"s", bad_utf8}}),
+            json::object({{bad_utf8, 1}}),
+            json::array({1, 2, bad_utf8}),
+            json::object({{"b", json::binary({1}, 0x100)}}),
+            json::object({{"d", json(json::value_t::discarded)}}),
+            json::array({json(json::value_t::discarded)}),
+        };
+        for (const auto& bad : bad_entries)
+        {
+            for (std::size_t pos = 0; pos < 4; ++pos)
+            {
+                json document = json::object();
+                json list = json::array();
+                for (std::size_t i = 0; i < 4; ++i)
+                {
+                    if (i == pos)
+                    {
+                        document["x" + std::to_string(i)] = bad;
+                        list.push_back(bad);
+                    }
+                    document["n" + std::to_string(i)] = json::array({i, "str", json::object({{"k", i}})});
+                    list.push_back(i);
+                }
+                document["list"] = list;
+                for (const auto handler : handlers)
+                {
+                    check_same(document, handler);
+                }
+            }
+        }
+    }
+}

tests/src/unit-cbor.cpp

@@ -29,9 +29,7 @@ using nlohmann::json;
 #include "round_trip_corpus.hpp"
 #include "test_utils.hpp"
 #include "sax_countdown.hpp"
-#include "sax_event_loggers.hpp"
 using utils::SaxCountdown;
-using utils::SaxEventLogger;
 
 
 TEST_CASE("CBOR")
@@ -2448,78 +2446,6 @@ TEST_CASE("CBOR SAX parsing stops at every event")
     CHECK(count_events(std::vector<std::uint8_t>({0xBF, 0x61, 'a', 0x9F, 0x01, 0xFF, 0xFF})) == 6);
 }
 
-TEST_CASE("CBOR arrays of scalars from contiguous and non-contiguous input")
-{
-    // contiguous input reads the integers, floats, booleans, and nulls an
-    // array begins with in one loop, other input value by value; both must
-    // give the same events, value, or error for the complete document and for
-    // every truncation of it, and stop at every event a SAX handler rejects
-    const std::vector<std::uint8_t> cbor =
-    {
-        0xA3,                                                       // map(3)
-        0x61, 'a',                                                  // "a"
-        0x98, 0x16,                                                 // array(22)
-        0x00, 0x17, 0x18, 0xFF, 0x19, 0x01, 0x00,                   // 0, 23, 255, 256
-        0x1A, 0x00, 0x01, 0x00, 0x00,                               // 65536
-        0x1B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,       // 18446744073709551615
-        0x20, 0x37, 0x38, 0xFF, 0x39, 0x01, 0x00,                   // -1, -24, -256, -257
-        0x3A, 0x00, 0x01, 0x00, 0x00,                               // -65537
-        0x3B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,       // -18446744073709551616 (a float)
-        0x3B, 0x7F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,       // -9223372036854775808
-        0xF4, 0xF5, 0xF6,                                           // false, true, null
-        0xFA, 0x3F, 0xC0, 0x00, 0x00,                               // 1.5 (float32)
-        0xFB, 0xBF, 0xB9, 0x99, 0x99, 0x99, 0x99, 0x99, 0x9A,       // -0.1
-        0xF9, 0x3C, 0x00,                                           // 1.0 (float16, ends the loop)
-        0x01, 0x61, 'a',                                            // 1, "a"
-        0xFB, 0x40, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,       // 2.5
-        0x61, 'b',                                                  // "b"
-        0x83,                                                       // array(3)
-        0x82, 0xFB, 0x3F, 0xF4, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // [1.25,
-        0xFB, 0xC0, 0x0E, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,       //  -3.75]
-        0x82, 0xFB, 0x3F, 0xF4, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // [1.25,
-        0xFB, 0xC0, 0x0E, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,       //  -3.75]
-        0x80,                                                       // []
-        0x61, 'c',                                                  // "c"
-        0x84, 0xA0, 0x01, 0xC1, 0x02, 0x81, 0x03                    // [{}, 1, tag(1) 2, [3]]
-    };
-    const auto tags = json::cbor_tag_handler_t::ignore;
-
-    const json j = json::from_cbor(cbor, true, true, tags);
-    CHECK(j["a"].size() == 22);
-    CHECK(j["a"][5] == 18446744073709551615u);
-    CHECK(j["a"][11].is_number_float());
-    CHECK(j["a"][11] == -18446744073709551616.0);
-    CHECK(j["a"][12] == (std::numeric_limits<std::int64_t>::min)());
-    CHECK(j["a"][17] == -0.1);
-    CHECK(j["b"] == json::parse("[[1.25, -3.75], [1.25, -3.75], []]"));
-    CHECK(j["c"] == json::parse("[{}, 1, 2, [3]]"));
-
-    for (std::size_t length = 0; length <= cbor.size(); ++length)
-    {
-        CAPTURE(length)
-        const std::vector<std::uint8_t> contiguous(cbor.begin(), cbor.begin() + static_cast<std::ptrdiff_t>(length));
-        const std::list<std::uint8_t> bytewise(contiguous.begin(), contiguous.end());
-
-        CHECK(json::from_cbor(contiguous, true, false, tags).dump() == json::from_cbor(bytewise.begin(), bytewise.end(), true, false, tags).dump());
-
-        SaxEventLogger from_contiguous;
-        SaxEventLogger from_bytewise;
-        CHECK(json::sax_parse(contiguous, &from_contiguous, json::input_format_t::cbor, true, false, false, tags)
-              == json::sax_parse(bytewise.begin(), bytewise.end(), &from_bytewise, json::input_format_t::cbor, true, false, false, tags));
-        CHECK(from_contiguous.events == from_bytewise.events);
-    }
-
-    for (int events = 0; events <= 60; ++events)
-    {
-        CAPTURE(events)
-        const std::list<std::uint8_t> bytewise(cbor.begin(), cbor.end());
-        SaxCountdown from_contiguous(events);
-        SaxCountdown from_bytewise(events);
-        CHECK(json::sax_parse(cbor, &from_contiguous, json::input_format_t::cbor, true, false, false, tags)
-              == json::sax_parse(bytewise.begin(), bytewise.end(), &from_bytewise, json::input_format_t::cbor, true, false, false, tags));
-    }
-}
-
 TEST_CASE("CBOR indefinite-length strings do not recurse per chunk")
 {
     // Reading an indefinite-length string or byte array used to call itself

tests/src/unit-msgpack.cpp

@@ -27,15 +27,12 @@ using nlohmann::json;
 #include <sstream>
 #include <iomanip>
 #include <limits>
-#include <list>
 #include <set>
 #include "make_test_data_available.hpp"
 #include "round_trip_corpus.hpp"
 #include "test_utils.hpp"
 #include "sax_countdown.hpp"
-#include "sax_event_loggers.hpp"
 using utils::SaxCountdown;
-using utils::SaxEventLogger;
 
 
 TEST_CASE("MessagePack")
@@ -2215,97 +2212,3 @@ TEST_CASE("MessagePack large strings and binaries (chunked reader)")
         }
     }
 }
-
-TEST_CASE("MessagePack arrays of scalars from contiguous and non-contiguous input")
-{
-    // contiguous input reads the integers, floats, booleans, and nils an
-    // array begins with in one loop, other input value by value; both must
-    // give the same events, value, or error for the complete document and for
-    // every truncation of it, and stop at every event a SAX handler rejects
-    const std::vector<std::uint8_t> msgpack =
-    {
-        0x83,                                                       // map(3)
-        0xA1, 'a',                                                  // "a"
-        0xDC, 0x00, 0x16,                                           // array 16 (22)
-        0x00, 0x7F, 0xCC, 0xFF, 0xCD, 0x01, 0x00,                   // 0, 127, 255, 256
-        0xCE, 0x00, 0x01, 0x00, 0x00,                               // 65536
-        0xCF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,       // 18446744073709551615
-        0xFF, 0xE0, 0xD0, 0x80, 0xD1, 0xFF, 0x00,                   // -1, -32, -128, -256
-        0xD2, 0xFF, 0xFE, 0xFF, 0xFF,                               // -65537
-        0xD3, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,       // -9223372036854775808
-        0xC2, 0xC3, 0xC0,                                           // false, true, nil
-        0xCA, 0x3F, 0xC0, 0x00, 0x00,                               // 1.5 (float 32)
-        0xCB, 0xBF, 0xB9, 0x99, 0x99, 0x99, 0x99, 0x99, 0x9A,       // -0.1
-        0xA1, 'x',                                                  // "x" (ends the loop)
-        0x01,                                                       // 1
-        0xCB, 0x40, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,       // 2.5
-        0xD9, 0x01, 'y',                                            // "y" (str 8)
-        0xC0,                                                       // nil
-        0xA1, 'b',                                                  // "b"
-        0x93,                                                       // fixarray(3)
-        0x92, 0xCB, 0x3F, 0xF4, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // [1.25,
-        0xCB, 0xC0, 0x0E, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,       //  -3.75]
-        0x92, 0xCB, 0x3F, 0xF4, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // [1.25,
-        0xCB, 0xC0, 0x0E, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,       //  -3.75]
-        0x90,                                                       // []
-        0xA1, 'c',                                                  // "c"
-        0x94, 0x80, 0x01, 0xC4, 0x01, 0x05, 0x91, 0x03              // [{}, 1, bin 8, [3]]
-    };
-
-    const json j = json::from_msgpack(msgpack);
-    CHECK(j["a"].size() == 22);
-    CHECK(j["a"][5] == 18446744073709551615u);
-    CHECK(j["a"][7] == -32);
-    CHECK(j["a"][11] == (std::numeric_limits<std::int64_t>::min)());
-    CHECK(j["a"][15] == 1.5);
-    CHECK(j["a"][16] == -0.1);
-    CHECK(j["a"][17] == "x");
-    CHECK(j["b"] == json::parse("[[1.25, -3.75], [1.25, -3.75], []]"));
-    CHECK(j["c"][2].is_binary());
-
-    for (std::size_t length = 0; length <= msgpack.size(); ++length)
-    {
-        CAPTURE(length)
-        const std::vector<std::uint8_t> contiguous(msgpack.begin(), msgpack.begin() + static_cast<std::ptrdiff_t>(length));
-        const std::list<std::uint8_t> bytewise(contiguous.begin(), contiguous.end());
-
-        CHECK(json::from_msgpack(contiguous, true, false).dump() == json::from_msgpack(bytewise.begin(), bytewise.end(), true, false).dump());
-#if !defined(JSON_NOEXCEPTION)
-        std::string contiguous_error;
-        std::string bytewise_error;
-        try
-        {
-            static_cast<void>(json::from_msgpack(contiguous));
-        }
-        catch (const json::parse_error& e)
-        {
-            contiguous_error = e.what();
-        }
-        try
-        {
-            static_cast<void>(json::from_msgpack(bytewise.begin(), bytewise.end()));
-        }
-        catch (const json::parse_error& e)
-        {
-            bytewise_error = e.what();
-        }
-        CHECK(contiguous_error == bytewise_error);
-#endif
-
-        SaxEventLogger from_contiguous;
-        SaxEventLogger from_bytewise;
-        CHECK(json::sax_parse(contiguous, &from_contiguous, json::input_format_t::msgpack)
-              == json::sax_parse(bytewise.begin(), bytewise.end(), &from_bytewise, json::input_format_t::msgpack));
-        CHECK(from_contiguous.events == from_bytewise.events);
-    }
-
-    for (int events = 0; events <= 60; ++events)
-    {
-        CAPTURE(events)
-        const std::list<std::uint8_t> bytewise(msgpack.begin(), msgpack.end());
-        SaxCountdown from_contiguous(events);
-        SaxCountdown from_bytewise(events);
-        CHECK(json::sax_parse(msgpack, &from_contiguous, json::input_format_t::msgpack)
-              == json::sax_parse(bytewise.begin(), bytewise.end(), &from_bytewise, json::input_format_t::msgpack));
-    }
-}