Keep diff()'s recursive levels small and its result elided

diff_recursively built every patch operation in place from initializer
lists. Unoptimized builds give each of those temporaries its own stack
slot, so every level of the bounded descent cost kilobytes of stack
(about 6 KB with clang -O0), and the 128 recursive levels overflowed the
1 MB stack of MSVC Debug in the "deeply nested values" test. The
operations and the key comparison of two objects are now built by
separate functions, which diff_iteratively shares, and both diff
functions append to one result instead of returning a patch per level
that the caller copies. With clang -O0, diffing values nested 300 levels
deep now peaks at about 190 KB of stack instead of 880 KB.

Since diff() now owns the only returned value, clang's -Wnrvo no longer
reports the returns of diff_recursively, which alternated between the
local patch and diff_iteratively's result.

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

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

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

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

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

docs/mkdocs/docs/home/exceptions.md

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

include/nlohmann/detail/output/binary_writer.hpp

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

include/nlohmann/json.hpp

@@ -5996,68 +5996,112 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     {
         // the patch
         basic_json result(value_t::array);
-
-        // if the values are the same, return an empty patch
-        if (source == target)
-        {
+        diff_recursively(result, source, target, path, 0);
         return result;
     }
 
-        if (source.type() != target.type())
+  private:
+    /// @brief two arrays or two objects @ref diff_iteratively is diffing
+    struct diff_frame
+    {
+        diff_frame(const basic_json* source_, const basic_json* target_, const std::size_t path_length_) noexcept
+            : source(source_), target(target_), path_length(path_length_)
+        {}
+
+        // declared for GCC's -Weffc++, which asks for them in a class with
+        // pointer members and a non-trivial destructor; the exception
+        // specifications are left implicit, as GCC 4.8 rejects explicit ones
+        // that differ from them
+        diff_frame(const diff_frame&) = default;
+        diff_frame(diff_frame&&) = default;
+        diff_frame& operator=(const diff_frame&) = default;
+        diff_frame& operator=(diff_frame&&) = default;
+        ~diff_frame() = default;
+
+        /// the values being diffed, both arrays or both objects
+        const basic_json* source;
+        const basic_json* target;
+        /// the length of their path in `current_path`
+        std::size_t path_length;
+        /// arrays: the next index to diff
+        std::size_t index = 0;
+        /// objects: the next member of source to look at
+        const_iterator member{}; // NOLINT(readability-redundant-member-init)
+        /// objects: the keys common to both, in source's order
+        std::vector<typename object_t::key_type> common_keys{}; // NOLINT(readability-redundant-member-init)
+        /// objects: the next entry of common_keys
+        std::size_t next_common = 0;
+        /// objects: the "add" operations for keys only target has
+        basic_json added_ops{}; // NOLINT(readability-redundant-member-init)
+    };
+
+    // The operations of a diff are built by the functions below rather than
+    // where they are needed: building one takes several temporaries, and
+    // unoptimized builds give each temporary a stack slot of its own in the
+    // function it appears in. In diff_recursively, which is on the call stack
+    // once per nesting level, that made every level cost kilobytes of stack.
+
+    /// @brief append a "replace" operation for @a path with @a value to @a result
+    static void diff_replace(basic_json& result, const string_t& path, const basic_json& value)
     {
-            // different types: replace value
         result.push_back(
         {
-                {"op", "replace"}, {"path", path}, {"value", target}
+            {"op", "replace"}, {"path", path}, {"value", value}
         });
-            return result;
     }
 
-        switch (source.type())
-        {
-            case value_t::array:
-            {
-                // first pass: traverse common elements
-                std::size_t i = 0;
-                while (i < source.size() && i < target.size())
-                {
-                    // recursive call to compare array values at index i
-                    auto temp_diff = diff(source[i], target[i], detail::concat<string_t>(path, '/', detail::to_string<string_t>(i)));
-                    result.insert(result.end(), temp_diff.begin(), temp_diff.end());
-                    ++i;
-                }
-
-                // We now reached the end of at least one array
-                // in a second pass, traverse the remaining elements
-
-                // remove my remaining elements, highest index first; appending
-                // in that order avoids the quadratic reinsertion done before
-                for (std::size_t j = source.size(); j > i; --j)
+    /// @brief append a "remove" operation for @a path to @a result
+    static void diff_remove(basic_json& result, const string_t& path)
     {
         result.push_back(object(
         {
-                        {"op", "remove"},
-                        {"path", detail::concat<string_t>(path, '/', detail::to_string<string_t>(j - 1))}
+            {"op", "remove"}, {"path", path}
         }));
     }
-                i = source.size();
 
-                // add other remaining elements
-                while (i < target.size())
+    /// @brief append an "add" operation for @a path with @a value to @a result
+    static void diff_add(basic_json& result, const string_t& path, const basic_json& value)
     {
         result.push_back(
         {
-                        {"op", "add"},
-                        {"path", detail::concat<string_t>(path, "/-")},
-                        {"value", target[i]}
+            {"op", "add"}, {"path", path}, {"value", value}
         });
-                    ++i;
     }
 
-                break;
+    /// @brief append the "remove" operations for the elements of array
+    ///        @a source from @a index on, and the "add" operations for the
+    ///        elements of array @a target from source's size on, to @a result
+    static void diff_array_tails(basic_json& result, const basic_json& source, const basic_json& target,
+                                 const string_t& path, const std::size_t index)
+    {
+        // remove my remaining elements, highest index first; appending
+        // in that order avoids the quadratic reinsertion done before
+        for (std::size_t j = source.size(); j > index; --j)
+        {
+            diff_remove(result, detail::concat<string_t>(path, '/', detail::to_string<string_t>(j - 1)));
         }
 
-            case value_t::object:
+        // add other remaining elements
+        for (std::size_t i = source.size(); i < target.size(); ++i)
+        {
+            diff_add(result, detail::concat<string_t>(path, "/-"), target[i]);
+        }
+    }
+
+    /*!
+    @brief compare the keys of objects @a source and @a target
+
+    If the keys both objects have are in the same order in both, and the keys
+    only @a target has come after them, stores the keys common to both in
+    source's order in @a common_keys, stores the "add" operations for the keys
+    only @a target has in @a added_ops, and returns true: the caller then diffs
+    the objects member by member. Otherwise, appends operations that remove
+    every member of @a source and add every member of @a target to @a result,
+    and returns false.
+    */
+    static bool diff_object_keys(basic_json& result, const basic_json& source, const basic_json& target,
+                                 const string_t& path, std::vector<typename object_t::key_type>& common_keys,
+                                 basic_json& added_ops)
     {
         // first pass: record, for every source key, whether it is
         // common to both objects (in source's iteration order) or
@@ -6065,10 +6109,10 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // 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.
+        // with the per-key diffs in the caller's fast path, to match
+        // source's original iteration order (as the original,
+        // pre-reordering-aware implementation did) instead of
+        // grouping all removes before all per-key diffs.
         std::vector<typename object_t::key_type> common_keys_source_order;
         for (auto it = source.cbegin(); it != source.cend(); ++it)
         {
@@ -6084,20 +6128,19 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // 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
+        // for the fast path, 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
+        // The patch ops for keys that were added (i.e., in target but not
+        // in source) are built here so the fast path 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)
@@ -6105,12 +6148,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             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()}
-                        });
+                diff_add(added_ops, detail::concat<string_t>(path, '/', detail::escape(it.key())), it.value());
             }
             else
             {
@@ -6126,43 +6164,12 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         {
             // 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}
-                            }));
-                        }
+            // insertion history), so a plain per-key diff is correct
+            // and minimal, as before
+            common_keys = std::move(common_keys_source_order);
+            return true;
         }
 
-                    // 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
@@ -6179,11 +6186,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // 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()));
-                        result.push_back(object(
-                        {
-                            {"op", "remove"}, {"path", path_key}
-                        }));
+            diff_remove(result, detail::concat<string_t>(path, '/', detail::escape(it.key())));
         }
 
         // add every key that is either common (just removed
@@ -6192,15 +6195,96 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // target exactly
         for (auto it = target.cbegin(); it != target.cend(); ++it)
         {
-                        const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
-                        result.push_back(
+            diff_add(result, detail::concat<string_t>(path, '/', detail::escape(it.key())), it.value());
+        }
+        return false;
+    }
+
+    /*!
+    @brief @ref diff, for values at nesting level @a depth, appending the
+           operations to @a result
+
+    Diffing two arrays or objects calls this function again, once per nesting
+    level, so values nested deeply enough used to exhaust the call stack and
+    terminate the process. The descent is bounded here: once @ref
+    detail::recursion_depth_limit levels have been entered, @ref
+    diff_iteratively diffs what is left without the call stack.
+    */
+    static void diff_recursively(basic_json& result, const basic_json& source, const basic_json& target,
+                                 const string_t& path, const std::size_t depth)
     {
-                            {"op", "add"}, {"path", path_key},
-                            {"value", it.value()}
-                        });
+        // if the values are the same, there is nothing to do
+        if (source == target)
+        {
+            return;
+        }
+
+        if (JSON_HEDLEY_UNLIKELY(depth >= detail::recursion_depth_limit()))
+        {
+            diff_iteratively(result, source, target, path);
+            return;
+        }
+
+        if (source.type() != target.type())
+        {
+            // different types: replace value
+            diff_replace(result, path, target);
+            return;
+        }
+
+        switch (source.type())
+        {
+            case value_t::array:
+            {
+                // first pass: traverse common elements
+                std::size_t i = 0;
+                while (i < source.size() && i < target.size())
+                {
+                    // recursive call to compare array values at index i
+                    diff_recursively(result, source[i], target[i], detail::concat<string_t>(path, '/', detail::to_string<string_t>(i)), depth + 1);
+                    ++i;
+                }
+
+                // We now reached the end of at least one array
+                // in a second pass, traverse the remaining elements
+                diff_array_tails(result, source, target, path, i);
+                break;
+            }
+
+            case value_t::object:
+            {
+                std::vector<typename object_t::key_type> common_keys;
+                basic_json added_ops(value_t::array);
+                if (diff_object_keys(result, source, target, path, common_keys, added_ops))
+                {
+                    // fast path: common_keys 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) are interleaved
+                    // here too, in source's original order, to match the
+                    // historical (pre-reordering-aware) output order.
+                    auto common_it = common_keys.cbegin();
+                    for (auto it = source.cbegin(); it != source.cend(); ++it)
+                    {
+                        if (common_it != common_keys.cend() && it.key() == *common_it)
+                        {
+                            diff_recursively(result, it.value(), target[it.key()], detail::concat<string_t>(path, '/', detail::escape(it.key())), depth + 1);
+                            ++common_it;
+                        }
+                        else
+                        {
+                            // found a key that is not in target -> remove it
+                            diff_remove(result, detail::concat<string_t>(path, '/', detail::escape(it.key())));
                         }
                     }
 
+                    // append the "add" ops for brand-new keys collected by
+                    // diff_object_keys -- no second source.find() per target
+                    // key needed
+                    result.insert(result.end(), added_ops.begin(), added_ops.end());
+                }
                 break;
             }
 
@@ -6215,16 +6299,166 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             default:
             {
                 // both primitive types: replace value
-                result.push_back(
-                {
-                    {"op", "replace"}, {"path", path}, {"value", target}
-                });
+                diff_replace(result, path, target);
                 break;
             }
         }
-
-        return result;
     }
+
+    /*!
+    @brief @ref diff without the call stack, appending the operations to
+           @a result
+
+    Produces the same operations as @ref diff_recursively. Only reached for
+    values nested more deeply than @ref detail::recursion_depth_limit.
+    */
+    static void diff_iteratively(basic_json& result, const basic_json& source, const basic_json& target,
+                                 const string_t& path)
+    {
+        // The arrays and objects being diffed are kept on an explicit stack,
+        // and every pair of elements is still diffed completely before the
+        // next one, so the operations come out in the same order as in
+        // diff_recursively. The path of the values being diffed is kept in
+        // one buffer that grows and shrinks with the stack, rather than in a
+        // new string per level.
+        std::vector<diff_frame> stack;
+        string_t current_path = path;
+
+        // diff `s` against `t`, whose path is current_path: primitives,
+        // values of different types, and objects whose members were reordered
+        // are handled right away; arrays and other objects get a frame
+        const auto enter = [&result, &stack, &current_path](const basic_json & s, const basic_json & t)
+        {
+            // if the values are the same, there is nothing to do. Arrays and
+            // objects are not compared up front: comparing them visits
+            // everything below them, so doing that at every level would take
+            // quadratic time in the nesting depth - equal ones yield no
+            // operations anyway.
+            if ((!s.is_structured() || !t.is_structured()) && s == t)
+            {
+                return;
+            }
+
+            if (s.type() != t.type())
+            {
+                // different types: replace value
+                diff_replace(result, current_path, t);
+                return;
+            }
+
+            switch (s.type())
+            {
+                case value_t::array:
+                {
+                    stack.emplace_back(&s, &t, current_path.size());
+                    return;
+                }
+
+                case value_t::object:
+                {
+                    std::vector<typename object_t::key_type> common_keys;
+                    basic_json added_ops(value_t::array);
+                    if (diff_object_keys(result, s, t, current_path, common_keys, added_ops))
+                    {
+                        // fast path: the frame walks source in lockstep with
+                        // common_keys, as diff_recursively does, and appends
+                        // added_ops once all members are done
+                        stack.emplace_back(&s, &t, current_path.size());
+                        stack.back().member = s.cbegin();
+                        stack.back().common_keys = std::move(common_keys);
+                        stack.back().added_ops = std::move(added_ops);
+                    }
+                    return;
+                }
+
+                case value_t::null:
+                case value_t::string:
+                case value_t::boolean:
+                case value_t::number_integer:
+                case value_t::number_unsigned:
+                case value_t::number_float:
+                case value_t::binary:
+                case value_t::discarded:
+                default:
+                {
+                    // both primitive types: replace value
+                    diff_replace(result, current_path, t);
+                    return;
+                }
+            }
+        };
+
+        enter(source, target);
+        while (!stack.empty())
+        {
+            // invalidated when enter() pushes a frame and by the pop_back()
+            // at the end, so not used after either
+            diff_frame& frame = stack.back();
+            const std::size_t path_length = frame.path_length;
+            const std::size_t depth = stack.size();
+
+            if (frame.source->is_array())
+            {
+                const auto& source_array = *frame.source->m_data.m_value.array;
+                const auto& target_array = *frame.target->m_data.m_value.array;
+
+                // first pass: traverse common elements
+                if (frame.index < source_array.size() && frame.index < target_array.size())
+                {
+                    const std::size_t i = frame.index++;
+                    detail::concat_into(current_path, '/', detail::to_string<string_t>(i));
+                    enter(source_array[i], target_array[i]); // may push, which invalidates `frame`
+                    if (stack.size() == depth)
+                    {
+                        current_path.resize(path_length);
+                    }
+                    continue;
+                }
+
+                // We now reached the end of at least one array
+                // in a second pass, traverse the remaining elements
+                diff_array_tails(result, *frame.source, *frame.target, current_path, frame.index);
+            }
+            else
+            {
+                if (frame.member != frame.source->cend())
+                {
+                    const const_iterator it = frame.member;
+                    ++frame.member;
+                    if (frame.next_common < frame.common_keys.size() && it.key() == frame.common_keys[frame.next_common])
+                    {
+                        ++frame.next_common;
+                        const basic_json& target_value = (*frame.target)[it.key()];
+                        detail::concat_into(current_path, '/', detail::escape(it.key()));
+                        enter(it.value(), target_value); // may push, which invalidates `frame`
+                        if (stack.size() == depth)
+                        {
+                            current_path.resize(path_length);
+                        }
+                    }
+                    else
+                    {
+                        // found a key that is not in target -> remove it
+                        diff_remove(result, detail::concat<string_t>(current_path, '/', detail::escape(it.key())));
+                    }
+                    continue;
+                }
+
+                // append the "add" ops for brand-new keys collected when the
+                // object was entered
+                result.insert(result.end(), frame.added_ops.begin(), frame.added_ops.end());
+            }
+
+            // this array or object is done: continue with the one it is in
+            stack.pop_back();
+            if (!stack.empty())
+            {
+                current_path.resize(stack.back().path_length);
+            }
+        }
+    }
+
+  public:
     /// @}
 
     ////////////////////////////////

single_include/nlohmann/json.hpp

@@ -19931,23 +19931,6 @@ class binary_writer
         }
     }
 
-    /*!
-    @brief check that @a length fits into the 32 bits that MessagePack stores
-           the length of a string, binary value, array, or object in
-    @return the length as an unsigned 32-bit integer
-    @throw out_of_range.412 if @a length exceeds the range of std::uint32_t
-    */
-    static std::uint32_t to_msgpack_length(const std::size_t length, const BasicJsonType& j)
-    {
-        if (JSON_HEDLEY_UNLIKELY(!value_in_range_of<std::uint32_t>(length)))
-        {
-            JSON_THROW(out_of_range::create(412, concat("MessagePack length ", std::to_string(length), " exceeds maximum of ", std::to_string((std::numeric_limits<std::uint32_t>::max)())), &j));
-        }
-
-        static_cast<void>(j);
-        return static_cast<std::uint32_t>(length);
-    }
-
     /*!
     @param[in] j  JSON value to serialize
     */
@@ -20088,7 +20071,7 @@ class binary_writer
             case value_t::string:
             {
                 // step 1: write control byte and the string length
-                const auto N = to_msgpack_length(j.m_data.m_value.string->size(), j);
+                const auto N = j.m_data.m_value.string->size();
                 if (N <= 31)
                 {
                     // fixstr
@@ -20106,7 +20089,7 @@ class binary_writer
                     oa.write_character(to_char_type(0xDA));
                     write_number(static_cast<std::uint16_t>(N));
                 }
-                else
+                else if (N <= (std::numeric_limits<std::uint32_t>::max)())
                 {
                     // str 32
                     oa.write_character(to_char_type(0xDB));
@@ -20123,7 +20106,7 @@ class binary_writer
             case value_t::array:
             {
                 // step 1: write control byte and the array size
-                const auto N = to_msgpack_length(j.m_data.m_value.array->size(), j);
+                const auto N = j.m_data.m_value.array->size();
                 if (N <= 15)
                 {
                     // fixarray
@@ -20135,7 +20118,7 @@ class binary_writer
                     oa.write_character(to_char_type(0xDC));
                     write_number(static_cast<std::uint16_t>(N));
                 }
-                else
+                else if (N <= (std::numeric_limits<std::uint32_t>::max)())
                 {
                     // array 32
                     oa.write_character(to_char_type(0xDD));
@@ -20157,7 +20140,7 @@ class binary_writer
                 const bool use_ext = j.m_data.m_value.binary->has_subtype();
 
                 // step 1: write control byte and the byte string length
-                const auto N = to_msgpack_length(j.m_data.m_value.binary->size(), j);
+                const auto N = j.m_data.m_value.binary->size();
                 if (N <= (std::numeric_limits<std::uint8_t>::max)())
                 {
                     std::uint8_t output_type{};
@@ -20209,7 +20192,7 @@ class binary_writer
                     oa.write_character(to_char_type(output_type));
                     write_number(static_cast<std::uint16_t>(N));
                 }
-                else
+                else if (N <= (std::numeric_limits<std::uint32_t>::max)())
                 {
                     const std::uint8_t output_type = use_ext
                                                      ? 0xC9 // ext 32
@@ -20241,7 +20224,7 @@ class binary_writer
             case value_t::object:
             {
                 // step 1: write control byte and the object size
-                const auto N = to_msgpack_length(j.m_data.m_value.object->size(), j);
+                const auto N = j.m_data.m_value.object->size();
                 if (N <= 15)
                 {
                     // fixmap
@@ -20253,7 +20236,7 @@ class binary_writer
                     oa.write_character(to_char_type(0xDE));
                     write_number(static_cast<std::uint16_t>(N));
                 }
-                else
+                else if (N <= (std::numeric_limits<std::uint32_t>::max)())
                 {
                     // map 32
                     oa.write_character(to_char_type(0xDF));
@@ -30971,68 +30954,112 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     {
         // the patch
         basic_json result(value_t::array);
-
-        // if the values are the same, return an empty patch
-        if (source == target)
-        {
+        diff_recursively(result, source, target, path, 0);
         return result;
     }
 
-        if (source.type() != target.type())
+  private:
+    /// @brief two arrays or two objects @ref diff_iteratively is diffing
+    struct diff_frame
+    {
+        diff_frame(const basic_json* source_, const basic_json* target_, const std::size_t path_length_) noexcept
+            : source(source_), target(target_), path_length(path_length_)
+        {}
+
+        // declared for GCC's -Weffc++, which asks for them in a class with
+        // pointer members and a non-trivial destructor; the exception
+        // specifications are left implicit, as GCC 4.8 rejects explicit ones
+        // that differ from them
+        diff_frame(const diff_frame&) = default;
+        diff_frame(diff_frame&&) = default;
+        diff_frame& operator=(const diff_frame&) = default;
+        diff_frame& operator=(diff_frame&&) = default;
+        ~diff_frame() = default;
+
+        /// the values being diffed, both arrays or both objects
+        const basic_json* source;
+        const basic_json* target;
+        /// the length of their path in `current_path`
+        std::size_t path_length;
+        /// arrays: the next index to diff
+        std::size_t index = 0;
+        /// objects: the next member of source to look at
+        const_iterator member{}; // NOLINT(readability-redundant-member-init)
+        /// objects: the keys common to both, in source's order
+        std::vector<typename object_t::key_type> common_keys{}; // NOLINT(readability-redundant-member-init)
+        /// objects: the next entry of common_keys
+        std::size_t next_common = 0;
+        /// objects: the "add" operations for keys only target has
+        basic_json added_ops{}; // NOLINT(readability-redundant-member-init)
+    };
+
+    // The operations of a diff are built by the functions below rather than
+    // where they are needed: building one takes several temporaries, and
+    // unoptimized builds give each temporary a stack slot of its own in the
+    // function it appears in. In diff_recursively, which is on the call stack
+    // once per nesting level, that made every level cost kilobytes of stack.
+
+    /// @brief append a "replace" operation for @a path with @a value to @a result
+    static void diff_replace(basic_json& result, const string_t& path, const basic_json& value)
     {
-            // different types: replace value
         result.push_back(
         {
-                {"op", "replace"}, {"path", path}, {"value", target}
+            {"op", "replace"}, {"path", path}, {"value", value}
         });
-            return result;
     }
 
-        switch (source.type())
-        {
-            case value_t::array:
-            {
-                // first pass: traverse common elements
-                std::size_t i = 0;
-                while (i < source.size() && i < target.size())
-                {
-                    // recursive call to compare array values at index i
-                    auto temp_diff = diff(source[i], target[i], detail::concat<string_t>(path, '/', detail::to_string<string_t>(i)));
-                    result.insert(result.end(), temp_diff.begin(), temp_diff.end());
-                    ++i;
-                }
-
-                // We now reached the end of at least one array
-                // in a second pass, traverse the remaining elements
-
-                // remove my remaining elements, highest index first; appending
-                // in that order avoids the quadratic reinsertion done before
-                for (std::size_t j = source.size(); j > i; --j)
+    /// @brief append a "remove" operation for @a path to @a result
+    static void diff_remove(basic_json& result, const string_t& path)
     {
         result.push_back(object(
         {
-                        {"op", "remove"},
-                        {"path", detail::concat<string_t>(path, '/', detail::to_string<string_t>(j - 1))}
+            {"op", "remove"}, {"path", path}
         }));
     }
-                i = source.size();
 
-                // add other remaining elements
-                while (i < target.size())
+    /// @brief append an "add" operation for @a path with @a value to @a result
+    static void diff_add(basic_json& result, const string_t& path, const basic_json& value)
     {
         result.push_back(
         {
-                        {"op", "add"},
-                        {"path", detail::concat<string_t>(path, "/-")},
-                        {"value", target[i]}
+            {"op", "add"}, {"path", path}, {"value", value}
         });
-                    ++i;
     }
 
-                break;
+    /// @brief append the "remove" operations for the elements of array
+    ///        @a source from @a index on, and the "add" operations for the
+    ///        elements of array @a target from source's size on, to @a result
+    static void diff_array_tails(basic_json& result, const basic_json& source, const basic_json& target,
+                                 const string_t& path, const std::size_t index)
+    {
+        // remove my remaining elements, highest index first; appending
+        // in that order avoids the quadratic reinsertion done before
+        for (std::size_t j = source.size(); j > index; --j)
+        {
+            diff_remove(result, detail::concat<string_t>(path, '/', detail::to_string<string_t>(j - 1)));
         }
 
-            case value_t::object:
+        // add other remaining elements
+        for (std::size_t i = source.size(); i < target.size(); ++i)
+        {
+            diff_add(result, detail::concat<string_t>(path, "/-"), target[i]);
+        }
+    }
+
+    /*!
+    @brief compare the keys of objects @a source and @a target
+
+    If the keys both objects have are in the same order in both, and the keys
+    only @a target has come after them, stores the keys common to both in
+    source's order in @a common_keys, stores the "add" operations for the keys
+    only @a target has in @a added_ops, and returns true: the caller then diffs
+    the objects member by member. Otherwise, appends operations that remove
+    every member of @a source and add every member of @a target to @a result,
+    and returns false.
+    */
+    static bool diff_object_keys(basic_json& result, const basic_json& source, const basic_json& target,
+                                 const string_t& path, std::vector<typename object_t::key_type>& common_keys,
+                                 basic_json& added_ops)
     {
         // first pass: record, for every source key, whether it is
         // common to both objects (in source's iteration order) or
@@ -31040,10 +31067,10 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // 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.
+        // with the per-key diffs in the caller's fast path, to match
+        // source's original iteration order (as the original,
+        // pre-reordering-aware implementation did) instead of
+        // grouping all removes before all per-key diffs.
         std::vector<typename object_t::key_type> common_keys_source_order;
         for (auto it = source.cbegin(); it != source.cend(); ++it)
         {
@@ -31059,20 +31086,19 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // 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
+        // for the fast path, 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
+        // The patch ops for keys that were added (i.e., in target but not
+        // in source) are built here so the fast path 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)
@@ -31080,12 +31106,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             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()}
-                        });
+                diff_add(added_ops, detail::concat<string_t>(path, '/', detail::escape(it.key())), it.value());
             }
             else
             {
@@ -31101,43 +31122,12 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         {
             // 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}
-                            }));
-                        }
+            // insertion history), so a plain per-key diff is correct
+            // and minimal, as before
+            common_keys = std::move(common_keys_source_order);
+            return true;
         }
 
-                    // 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
@@ -31154,11 +31144,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // 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()));
-                        result.push_back(object(
-                        {
-                            {"op", "remove"}, {"path", path_key}
-                        }));
+            diff_remove(result, detail::concat<string_t>(path, '/', detail::escape(it.key())));
         }
 
         // add every key that is either common (just removed
@@ -31167,15 +31153,96 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // target exactly
         for (auto it = target.cbegin(); it != target.cend(); ++it)
         {
-                        const auto path_key = detail::concat<string_t>(path, '/', detail::escape(it.key()));
-                        result.push_back(
+            diff_add(result, detail::concat<string_t>(path, '/', detail::escape(it.key())), it.value());
+        }
+        return false;
+    }
+
+    /*!
+    @brief @ref diff, for values at nesting level @a depth, appending the
+           operations to @a result
+
+    Diffing two arrays or objects calls this function again, once per nesting
+    level, so values nested deeply enough used to exhaust the call stack and
+    terminate the process. The descent is bounded here: once @ref
+    detail::recursion_depth_limit levels have been entered, @ref
+    diff_iteratively diffs what is left without the call stack.
+    */
+    static void diff_recursively(basic_json& result, const basic_json& source, const basic_json& target,
+                                 const string_t& path, const std::size_t depth)
     {
-                            {"op", "add"}, {"path", path_key},
-                            {"value", it.value()}
-                        });
+        // if the values are the same, there is nothing to do
+        if (source == target)
+        {
+            return;
+        }
+
+        if (JSON_HEDLEY_UNLIKELY(depth >= detail::recursion_depth_limit()))
+        {
+            diff_iteratively(result, source, target, path);
+            return;
+        }
+
+        if (source.type() != target.type())
+        {
+            // different types: replace value
+            diff_replace(result, path, target);
+            return;
+        }
+
+        switch (source.type())
+        {
+            case value_t::array:
+            {
+                // first pass: traverse common elements
+                std::size_t i = 0;
+                while (i < source.size() && i < target.size())
+                {
+                    // recursive call to compare array values at index i
+                    diff_recursively(result, source[i], target[i], detail::concat<string_t>(path, '/', detail::to_string<string_t>(i)), depth + 1);
+                    ++i;
+                }
+
+                // We now reached the end of at least one array
+                // in a second pass, traverse the remaining elements
+                diff_array_tails(result, source, target, path, i);
+                break;
+            }
+
+            case value_t::object:
+            {
+                std::vector<typename object_t::key_type> common_keys;
+                basic_json added_ops(value_t::array);
+                if (diff_object_keys(result, source, target, path, common_keys, added_ops))
+                {
+                    // fast path: common_keys 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) are interleaved
+                    // here too, in source's original order, to match the
+                    // historical (pre-reordering-aware) output order.
+                    auto common_it = common_keys.cbegin();
+                    for (auto it = source.cbegin(); it != source.cend(); ++it)
+                    {
+                        if (common_it != common_keys.cend() && it.key() == *common_it)
+                        {
+                            diff_recursively(result, it.value(), target[it.key()], detail::concat<string_t>(path, '/', detail::escape(it.key())), depth + 1);
+                            ++common_it;
+                        }
+                        else
+                        {
+                            // found a key that is not in target -> remove it
+                            diff_remove(result, detail::concat<string_t>(path, '/', detail::escape(it.key())));
                         }
                     }
 
+                    // append the "add" ops for brand-new keys collected by
+                    // diff_object_keys -- no second source.find() per target
+                    // key needed
+                    result.insert(result.end(), added_ops.begin(), added_ops.end());
+                }
                 break;
             }
 
@@ -31190,16 +31257,166 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             default:
             {
                 // both primitive types: replace value
-                result.push_back(
-                {
-                    {"op", "replace"}, {"path", path}, {"value", target}
-                });
+                diff_replace(result, path, target);
                 break;
             }
         }
-
-        return result;
     }
+
+    /*!
+    @brief @ref diff without the call stack, appending the operations to
+           @a result
+
+    Produces the same operations as @ref diff_recursively. Only reached for
+    values nested more deeply than @ref detail::recursion_depth_limit.
+    */
+    static void diff_iteratively(basic_json& result, const basic_json& source, const basic_json& target,
+                                 const string_t& path)
+    {
+        // The arrays and objects being diffed are kept on an explicit stack,
+        // and every pair of elements is still diffed completely before the
+        // next one, so the operations come out in the same order as in
+        // diff_recursively. The path of the values being diffed is kept in
+        // one buffer that grows and shrinks with the stack, rather than in a
+        // new string per level.
+        std::vector<diff_frame> stack;
+        string_t current_path = path;
+
+        // diff `s` against `t`, whose path is current_path: primitives,
+        // values of different types, and objects whose members were reordered
+        // are handled right away; arrays and other objects get a frame
+        const auto enter = [&result, &stack, &current_path](const basic_json & s, const basic_json & t)
+        {
+            // if the values are the same, there is nothing to do. Arrays and
+            // objects are not compared up front: comparing them visits
+            // everything below them, so doing that at every level would take
+            // quadratic time in the nesting depth - equal ones yield no
+            // operations anyway.
+            if ((!s.is_structured() || !t.is_structured()) && s == t)
+            {
+                return;
+            }
+
+            if (s.type() != t.type())
+            {
+                // different types: replace value
+                diff_replace(result, current_path, t);
+                return;
+            }
+
+            switch (s.type())
+            {
+                case value_t::array:
+                {
+                    stack.emplace_back(&s, &t, current_path.size());
+                    return;
+                }
+
+                case value_t::object:
+                {
+                    std::vector<typename object_t::key_type> common_keys;
+                    basic_json added_ops(value_t::array);
+                    if (diff_object_keys(result, s, t, current_path, common_keys, added_ops))
+                    {
+                        // fast path: the frame walks source in lockstep with
+                        // common_keys, as diff_recursively does, and appends
+                        // added_ops once all members are done
+                        stack.emplace_back(&s, &t, current_path.size());
+                        stack.back().member = s.cbegin();
+                        stack.back().common_keys = std::move(common_keys);
+                        stack.back().added_ops = std::move(added_ops);
+                    }
+                    return;
+                }
+
+                case value_t::null:
+                case value_t::string:
+                case value_t::boolean:
+                case value_t::number_integer:
+                case value_t::number_unsigned:
+                case value_t::number_float:
+                case value_t::binary:
+                case value_t::discarded:
+                default:
+                {
+                    // both primitive types: replace value
+                    diff_replace(result, current_path, t);
+                    return;
+                }
+            }
+        };
+
+        enter(source, target);
+        while (!stack.empty())
+        {
+            // invalidated when enter() pushes a frame and by the pop_back()
+            // at the end, so not used after either
+            diff_frame& frame = stack.back();
+            const std::size_t path_length = frame.path_length;
+            const std::size_t depth = stack.size();
+
+            if (frame.source->is_array())
+            {
+                const auto& source_array = *frame.source->m_data.m_value.array;
+                const auto& target_array = *frame.target->m_data.m_value.array;
+
+                // first pass: traverse common elements
+                if (frame.index < source_array.size() && frame.index < target_array.size())
+                {
+                    const std::size_t i = frame.index++;
+                    detail::concat_into(current_path, '/', detail::to_string<string_t>(i));
+                    enter(source_array[i], target_array[i]); // may push, which invalidates `frame`
+                    if (stack.size() == depth)
+                    {
+                        current_path.resize(path_length);
+                    }
+                    continue;
+                }
+
+                // We now reached the end of at least one array
+                // in a second pass, traverse the remaining elements
+                diff_array_tails(result, *frame.source, *frame.target, current_path, frame.index);
+            }
+            else
+            {
+                if (frame.member != frame.source->cend())
+                {
+                    const const_iterator it = frame.member;
+                    ++frame.member;
+                    if (frame.next_common < frame.common_keys.size() && it.key() == frame.common_keys[frame.next_common])
+                    {
+                        ++frame.next_common;
+                        const basic_json& target_value = (*frame.target)[it.key()];
+                        detail::concat_into(current_path, '/', detail::escape(it.key()));
+                        enter(it.value(), target_value); // may push, which invalidates `frame`
+                        if (stack.size() == depth)
+                        {
+                            current_path.resize(path_length);
+                        }
+                    }
+                    else
+                    {
+                        // found a key that is not in target -> remove it
+                        diff_remove(result, detail::concat<string_t>(current_path, '/', detail::escape(it.key())));
+                    }
+                    continue;
+                }
+
+                // append the "add" ops for brand-new keys collected when the
+                // object was entered
+                result.insert(result.end(), frame.added_ops.begin(), frame.added_ops.end());
+            }
+
+            // this array or object is done: continue with the one it is in
+            stack.pop_back();
+            if (!stack.empty())
+            {
+                current_path.resize(stack.back().path_length);
+            }
+        }
+    }
+
+  public:
     /// @}
 
     ////////////////////////////////

tests/src/unit-json_patch.cpp

@@ -15,8 +15,65 @@ using nlohmann::json;
 #endif
 
 #include <fstream>
+#include <string>
+#include <vector>
 #include "make_test_data_available.hpp"
 
+namespace
+{
+// alternating objects and arrays nested `depth` levels deep, with members that
+// depend on `variant` at some levels, so diffing two variants yields
+// operations on many levels: replacing the innermost value, adding, removing,
+// and (for ordered_json) reordering members, and changing array lengths
+template<typename BasicJsonType>
+BasicJsonType nested(const std::size_t depth, const int variant)
+{
+    BasicJsonType value = variant;
+    for (std::size_t i = 0; i < depth; ++i)
+    {
+        if (i % 2 == 0)
+        {
+            BasicJsonType object = BasicJsonType::object();
+            if ((i + static_cast<std::size_t>(variant)) % 7 == 0)
+            {
+                object["x"] = i;
+            }
+            if (variant == 2 && i % 11 == 0)
+            {
+                object["z"] = "z";
+            }
+            object["a"] = std::move(value);
+            if (variant == 1 && i % 5 == 0)
+            {
+                object["y"] = 1;
+            }
+            value = std::move(object);
+        }
+        else
+        {
+            BasicJsonType array = BasicJsonType::array({std::move(value)});
+            if ((i + static_cast<std::size_t>(variant)) % 3 == 0)
+            {
+                array.push_back(i);
+            }
+            value = std::move(array);
+        }
+    }
+    return value;
+}
+
+// a path of `depth` reference tokens, as nested() nests its values
+std::string nested_path(const std::size_t depth)
+{
+    std::string path;
+    for (std::size_t i = depth; i > 0; --i)
+    {
+        path += (i - 1) % 2 == 0 ? "/a" : "/0";
+    }
+    return path;
+}
+} // namespace
+
 TEST_CASE("JSON patch")
 {
     SECTION("examples from RFC 6902")
@@ -1751,3 +1808,99 @@ TEST_CASE("JSON patch - diff emits array removals in descending index order")
         CHECK(source.patch(patch) == target);
     }
 }
+
+TEST_CASE("JSON patch: diff of deeply nested values")
+{
+    SECTION("the diff reproduces the target at every depth")
+    {
+        // depths on either side of the nesting depth up to which diff()
+        // recurses (detail::recursion_depth_limit(), 128); not every depth up
+        // to 300, as the test would then time out under Valgrind
+        std::vector<std::size_t> depths;
+        for (std::size_t depth = 0; depth <= 16; ++depth)
+        {
+            depths.push_back(depth);
+        }
+        for (std::size_t depth = 120; depth <= 136; ++depth)
+        {
+            depths.push_back(depth);
+        }
+        depths.push_back(300);
+
+        for (const auto depth : depths)
+        {
+            CAPTURE(depth);
+            for (int from = 0; from < 3; ++from)
+            {
+                for (int to = 0; to < 3; ++to)
+                {
+                    CAPTURE(from);
+                    CAPTURE(to);
+                    const auto source = nested<json>(depth, from);
+                    const auto target = nested<json>(depth, to);
+                    const auto patch = json::diff(source, target);
+                    CHECK(source.patch(patch) == target);
+                    CHECK(patch.empty() == (from == to));
+
+                    const auto ordered_source = nested<nlohmann::ordered_json>(depth, from);
+                    const auto ordered_target = nested<nlohmann::ordered_json>(depth, to);
+                    CHECK(ordered_source.patch(nlohmann::ordered_json::diff(ordered_source, ordered_target)) == ordered_target);
+                }
+            }
+        }
+    }
+
+    SECTION("a difference only in the innermost value is one replace operation")
+    {
+        for (std::size_t depth = 0; depth <= 300; ++depth)
+        {
+            CAPTURE(depth);
+            json source = 1;
+            json target = 2;
+            for (std::size_t i = 0; i < depth; ++i)
+            {
+                source = i % 2 == 0 ? json::object({{"a", std::move(source)}}) : json::array({std::move(source)});
+                target = i % 2 == 0 ? json::object({{"a", std::move(target)}}) : json::array({std::move(target)});
+            }
+            CHECK(json::diff(source, target, "/root") == json::array({{{"op", "replace"}, {"path", "/root" + nested_path(depth)}, {"value", 2}}}));
+        }
+    }
+
+    SECTION("values nested too deeply for the call stack (#5393)")
+    {
+        // diff() used to recurse once per nesting level, and compared the
+        // values with operator== on every level. The values are only
+        // parsed and diffed, never copied or compared, since those recurse
+        // too.
+        const std::size_t depth = 100000;
+        for (const bool objects :
+                {
+                    false, true
+                })
+        {
+            CAPTURE(objects);
+            std::string source_text;
+            std::string target_text;
+            std::string equal_text;
+            std::string path;
+            for (std::size_t i = 0; i < depth; ++i)
+            {
+                source_text += objects ? "{\"a\":" : "[";
+                path += objects ? "/a" : "/0";
+            }
+            target_text = source_text + "2";
+            equal_text = source_text + "1";
+            source_text += "1";
+            const std::string closing(depth, objects ? '}' : ']');
+            const auto source = json::parse(source_text + closing);
+
+            const auto patch = json::diff(source, json::parse(target_text + closing));
+            REQUIRE(patch.size() == 1);
+            CHECK(patch[0]["op"] == "replace");
+            CHECK(patch[0]["path"] == path);
+            CHECK(patch[0]["value"] == 2);
+
+            CHECK(json::diff(source, json::parse(equal_text + closing)).empty());
+        }
+    }
+}

tests/src/unit-msgpack.cpp

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