Build the update()/merge_patch() diagnostics test values instead of parsing them

Parsed values carry byte positions under JSON_DIAGNOSTIC_POSITIONS, which
the expected messages do not include.

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

BUILD.bazel

@@ -58,6 +58,7 @@ cc_library(
         "include/nlohmann/detail/output/binary_writer.hpp",
         "include/nlohmann/detail/output/output_adapters.hpp",
         "include/nlohmann/detail/output/serializer.hpp",
+        "include/nlohmann/detail/recursion_depth_limit.hpp",
         "include/nlohmann/detail/string_concat.hpp",
         "include/nlohmann/detail/string_escape.hpp",
         "include/nlohmann/detail/string_utils.hpp",

include/nlohmann/detail/hash.hpp

@@ -11,8 +11,10 @@
 #include <cstdint> // uint8_t
 #include <cstddef> // size_t
 #include <functional> // hash
+#include <vector> // vector
 
 #include <nlohmann/detail/abi_macros.hpp>
+#include <nlohmann/detail/recursion_depth_limit.hpp>
 #include <nlohmann/detail/value_t.hpp>
 
 NLOHMANN_JSON_NAMESPACE_BEGIN
@@ -26,6 +28,9 @@ inline std::size_t combine(std::size_t seed, std::size_t h) noexcept
     return seed;
 }
 
+template<typename BasicJsonType>
+std::size_t hash_iteratively(const BasicJsonType& j);
+
 /*!
 @brief hash a JSON value
 
@@ -33,12 +38,21 @@ The hash function tries to rely on std::hash where possible. Furthermore, the
 type of the JSON value is taken into account to have different hash values for
 null, 0, 0U, and false, etc.
 
+Hashing an array or an object hashes its elements, which used to call this
+function again once per nesting level, so a value nested deeply enough
+exhausted the call stack and terminated the process. The descent is bounded
+here: once @ref recursion_depth_limit levels have been entered, @ref
+hash_iteratively hashes what is left without the call stack. A value nested
+less deeply than that - all but a vanishing minority - is hashed exactly as
+before, without allocating.
+
 @tparam BasicJsonType basic_json specialization
 @param j JSON value to hash
+@param depth nesting level of @a j, counted from the value passed by the caller
 @return hash value of j
 */
 template<typename BasicJsonType>
-std::size_t hash(const BasicJsonType& j)
+std::size_t hash(const BasicJsonType& j, const std::size_t depth = 0)
 {
     using string_t = typename BasicJsonType::string_t;
     using number_integer_t = typename BasicJsonType::number_integer_t;
@@ -56,22 +70,32 @@ std::size_t hash(const BasicJsonType& j)
 
         case BasicJsonType::value_t::object:
         {
+            if (JSON_HEDLEY_UNLIKELY(depth >= recursion_depth_limit()))
+            {
+                return hash_iteratively(j);
+            }
+
             auto seed = combine(type, j.size());
             for (const auto& element : j.items())
             {
                 const auto h = std::hash<string_t> {}(element.key());
                 seed = combine(seed, h);
-                seed = combine(seed, hash(element.value()));
+                seed = combine(seed, hash(element.value(), depth + 1));
             }
             return seed;
         }
 
         case BasicJsonType::value_t::array:
         {
+            if (JSON_HEDLEY_UNLIKELY(depth >= recursion_depth_limit()))
+            {
+                return hash_iteratively(j);
+            }
+
             auto seed = combine(type, j.size());
             for (const auto& element : j)
             {
-                seed = combine(seed, hash(element));
+                seed = combine(seed, hash(element, depth + 1));
             }
             return seed;
         }
@@ -127,5 +151,77 @@ std::size_t hash(const BasicJsonType& j)
     }
 }
 
+/// an array or object whose elements @ref hash_iteratively is hashing
+template<typename BasicJsonType>
+struct hash_frame
+{
+    hash_frame(const BasicJsonType* value_, std::size_t seed_) noexcept
+        : value(value_), position(value_->cbegin()), seed(seed_)
+    {}
+
+    const BasicJsonType* value;
+    typename BasicJsonType::const_iterator position;
+    std::size_t seed;
+};
+
+/*!
+@brief hash the array or object @a j without the call stack
+
+Computes the same value as @ref hash, keeping the arrays and objects it has
+entered on an explicit stack instead of descending into them. Only reached for
+values nested deeper than @ref recursion_depth_limit.
+
+@tparam BasicJsonType basic_json specialization
+@param j array or object to hash
+@return hash value of j
+*/
+template<typename BasicJsonType>
+std::size_t hash_iteratively(const BasicJsonType& j)
+{
+    using string_t = typename BasicJsonType::string_t;
+
+    std::vector<hash_frame<BasicJsonType>> stack;
+    stack.emplace_back(&j, combine(static_cast<std::size_t>(j.type()), j.size()));
+
+    while (true)
+    {
+        // a copy, as entering an element below can reallocate the stack; the
+        // frame itself is only changed through stack.back()
+        const hash_frame<BasicJsonType> frame = stack.back();
+
+        if (frame.position == frame.value->cend())
+        {
+            // all elements are hashed: fold this value's hash into its parent's
+            // seed, exactly where the recursive version returns it
+            const std::size_t h = frame.seed;
+            stack.pop_back();
+            if (stack.empty())
+            {
+                return h;
+            }
+            stack.back().seed = combine(stack.back().seed, h);
+            continue;
+        }
+
+        if (frame.value->is_object())
+        {
+            stack.back().seed = combine(stack.back().seed, std::hash<string_t> {}(frame.position.key()));
+        }
+
+        // advance before entering the element, which pushes onto the stack
+        const BasicJsonType& element = *frame.position;
+        ++stack.back().position;
+
+        if (element.is_structured())
+        {
+            stack.emplace_back(&element, combine(static_cast<std::size_t>(element.type()), element.size()));
+        }
+        else
+        {
+            stack.back().seed = combine(stack.back().seed, hash(element));
+        }
+    }
+}
+
 }  // namespace detail
 NLOHMANN_JSON_NAMESPACE_END

include/nlohmann/detail/output/serializer.hpp

@@ -30,6 +30,7 @@
 #include <nlohmann/detail/meta/cpp_future.hpp>
 #include <nlohmann/detail/output/binary_writer.hpp>
 #include <nlohmann/detail/output/output_adapters.hpp>
+#include <nlohmann/detail/recursion_depth_limit.hpp>
 #include <nlohmann/detail/string_concat.hpp>
 #include <nlohmann/detail/value_t.hpp>
 
@@ -133,7 +134,7 @@ class serializer
 
     Serializing a container descends into its elements, so a value nested deeply
     enough used to exhaust the call stack and terminate the process with no
-    exception to catch. The descent is bounded here: once @ref dump_depth_limit
+    exception to catch. The descent is bounded here: once @ref recursion_depth_limit
     levels have been entered, @ref dump_iteratively writes out what is left
     without the call stack. A value nested less deeply than that - all but a
     vanishing minority - is written by exactly the code that always wrote it.
@@ -148,7 +149,7 @@ class serializer
         {
             case value_t::object:
             {
-                if (JSON_HEDLEY_UNLIKELY(depth >= dump_depth_limit()))
+                if (JSON_HEDLEY_UNLIKELY(depth >= recursion_depth_limit()))
                 {
                     dump_iteratively(val, current_indent);
                     return;
@@ -223,7 +224,7 @@ class serializer
 
             case value_t::array:
             {
-                if (JSON_HEDLEY_UNLIKELY(depth >= dump_depth_limit()))
+                if (JSON_HEDLEY_UNLIKELY(depth >= recursion_depth_limit()))
                 {
                     dump_iteratively(val, current_indent);
                     return;
@@ -408,19 +409,12 @@ class serializer
     }
 
   private:
-    /// the number of levels @ref dump_internal descends into before it hands
-    /// over to @ref dump_iteratively
-    static constexpr std::size_t dump_depth_limit()
-    {
-        return 128;
-    }
-
     /*!
     @brief write out @a val and everything below it without the call stack
 
     Emits the same bytes as @ref dump_internal, keeping the containers it has
     entered on an explicit stack instead of descending into them. Only reached
-    for values nested deeper than @ref dump_depth_limit, which is why it is not
+    for values nested deeper than @ref recursion_depth_limit, which is why it is not
     written for speed: walking every value this way measured up to 20% slower on
     object-heavy documents than letting the compiler drive the descent.
     */

include/nlohmann/detail/recursion_depth_limit.hpp

@@ -0,0 +1,35 @@
+//     __ _____ _____ _____
+//  __|  |   __|     |   | |  JSON for Modern C++
+// |  |  |__   |  |  | | | |  version 3.12.0
+// |_____|_____|_____|_|___|  https://github.com/nlohmann/json
+//
+// SPDX-FileCopyrightText: 2013-2026 Niels Lohmann <https://nlohmann.me>
+// SPDX-License-Identifier: MIT
+
+#pragma once
+
+#include <cstddef> // size_t
+
+#include <nlohmann/detail/abi_macros.hpp>
+
+NLOHMANN_JSON_NAMESPACE_BEGIN
+namespace detail
+{
+
+/*!
+@brief the number of nesting levels an operation recurses into
+
+Operations that walk a value (serializing, hashing, merging, ...) recurse once
+per nesting level, which is fastest, but a value nested deeply enough would
+exhaust the call stack. So they recurse only this many levels deep and finish
+whatever lies below with an explicit stack. All of them share this limit.
+
+@sa https://github.com/nlohmann/json/issues/5387
+*/
+constexpr std::size_t recursion_depth_limit() noexcept
+{
+    return 128;
+}
+
+}  // namespace detail
+NLOHMANN_JSON_NAMESPACE_END

include/nlohmann/json.hpp

@@ -68,6 +68,7 @@
 #include <nlohmann/detail/output/binary_writer.hpp>
 #include <nlohmann/detail/output/output_adapters.hpp>
 #include <nlohmann/detail/output/serializer.hpp>
+#include <nlohmann/detail/recursion_depth_limit.hpp>
 #include <nlohmann/detail/value_t.hpp>
 #include <nlohmann/json_fwd.hpp>
 #include <nlohmann/ordered_map.hpp>
@@ -3912,17 +3913,54 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             JSON_THROW(type_error::create(312, detail::concat("cannot use update() with ", first.m_object->type_name()), first.m_object));
         }
 
+        update_members(first, last, merge_objects, 0);
+    }
+
+  private:
+    /// @brief an object @ref update_members_iteratively or @ref
+    /// merge_patch_iteratively is merging into, and the members still to merge
+    struct merge_frame
+    {
+        merge_frame(basic_json* target_, const_iterator position_, const_iterator last_) noexcept
+            : target(target_), position(std::move(position_)), last(std::move(last_))
+        {}
+
+        basic_json* target;
+        const_iterator position;
+        const_iterator last;
+    };
+
+    /*!
+    @brief the members loop of @ref update, for this object and range
+
+    Merging a nested object calls this function again, once per nesting
+    level, so a value 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
+    update_members_iteratively merges what is left without the call stack.
+
+    @param[in] depth  nesting level of this object, counted from the object
+                      @ref update was called on
+    */
+    void update_members(const const_iterator& first, const const_iterator& last, const bool merge_objects, const std::size_t depth)
+    {
+        if (JSON_HEDLEY_UNLIKELY(depth >= detail::recursion_depth_limit()))
+        {
+            update_members_iteratively(first, last);
+            return;
+        }
+
         for (auto it = first; it != last; ++it)
         {
             if (merge_objects && it.value().is_object())
             {
-                auto it2 = m_data.m_value.object->find(it.key());
+                const auto it2 = m_data.m_value.object->find(it.key());
                 // Only recurse when the existing value is itself an object.
                 // Otherwise overwrite, matching the documented "all other values
                 // are overwritten as usual" behavior (see #5402).
                 if (it2 != m_data.m_value.object->end() && it2->second.is_object())
                 {
-                    it2->second.update(it.value(), true);
+                    it2->second.update_members(it.value().cbegin(), it.value().cend(), true, depth + 1);
 #if JSON_DIAGNOSTICS
                     it2->second.set_parents();
 #endif
@@ -3936,6 +3974,64 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         }
     }
 
+    /*!
+    @brief merge @a first to @a last into this object without the call stack
+
+    Does the same as @ref update_members with `merge_objects` set, keeping the
+    objects whose merge was interrupted by a nested one on an explicit stack
+    instead of descending into them. A nested object is still merged
+    completely before the next member, in the same order as the recursive
+    version. Only reached for values nested deeper than @ref
+    detail::recursion_depth_limit.
+    */
+    void update_members_iteratively(const_iterator first, const_iterator last)
+    {
+        std::vector<merge_frame> stack;
+
+        basic_json* target = this;
+        while (true)
+        {
+            if (first == last)
+            {
+                if (stack.empty())
+                {
+                    break;
+                }
+
+                // a nested object is merged: continue with its parent
+#if JSON_DIAGNOSTICS
+                target->set_parents();
+#endif
+                target = stack.back().target;
+                first = stack.back().position;
+                last = stack.back().last;
+                stack.pop_back();
+                continue;
+            }
+
+            if (first.value().is_object())
+            {
+                const auto it2 = target->m_data.m_value.object->find(first.key());
+                if (it2 != target->m_data.m_value.object->end() && it2->second.is_object())
+                {
+                    const basic_json& source = first.value();
+                    ++first;
+                    stack.emplace_back(target, first, last);
+                    target = &it2->second;
+                    first = source.cbegin();
+                    last = source.cend();
+                    continue;
+                }
+            }
+            target->m_data.m_value.object->operator[](first.key()) = first.value();
+#if JSON_DIAGNOSTICS
+            target->m_data.m_value.object->operator[](first.key()).m_parent = target;
+#endif
+            ++first;
+        }
+    }
+
+  public:
     /// @brief exchanges the values
     /// @sa https://json.nlohmann.me/api/basic_json/swap/
     void swap(reference other) noexcept (
@@ -5830,9 +5926,30 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     /// @brief applies a JSON Merge Patch
     /// @sa https://json.nlohmann.me/api/basic_json/merge_patch/
     void merge_patch(const basic_json& apply_patch)
+    {
+        apply_merge_patch(apply_patch, 0);
+    }
+
+  private:
+    /*!
+    @brief @ref merge_patch, for a patch at nesting level @a depth
+
+    Applying a nested object calls this function again, once per nesting
+    level, so a patch 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
+    merge_patch_iteratively applies what is left without the call stack.
+    */
+    void apply_merge_patch(const basic_json& apply_patch, const std::size_t depth)
     {
         if (apply_patch.is_object())
         {
+            if (JSON_HEDLEY_UNLIKELY(depth >= detail::recursion_depth_limit()))
+            {
+                merge_patch_iteratively(apply_patch);
+                return;
+            }
+
             if (!is_object())
             {
                 *this = object();
@@ -5845,7 +5962,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                 }
                 else
                 {
-                    operator[](it.key()).merge_patch(it.value());
+                    operator[](it.key()).apply_merge_patch(it.value(), depth + 1);
                 }
             }
         }
@@ -5855,6 +5972,62 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         }
     }
 
+    /*!
+    @brief apply @a apply_patch to this value without the call stack
+
+    Does the same as @ref merge_patch, keeping the objects being patched on an
+    explicit stack instead of descending into them. A nested object is still
+    patched completely before the next member, in the same order as the
+    recursive version. Only reached for patches nested deeper than @ref
+    detail::recursion_depth_limit.
+    */
+    void merge_patch_iteratively(const basic_json& apply_patch)
+    {
+        std::vector<merge_frame> stack;
+
+        // patch `target` with `patch`, or start patching it member by member
+        const auto apply = [&stack](basic_json & target, const basic_json & patch)
+        {
+            if (patch.is_object())
+            {
+                if (!target.is_object())
+                {
+                    target = basic_json::object();
+                }
+                stack.emplace_back(&target, patch.cbegin(), patch.cend());
+            }
+            else
+            {
+                target = patch;
+            }
+        };
+
+        apply(*this, apply_patch);
+        while (!stack.empty())
+        {
+            // a copy, as applying a member below can reallocate the stack;
+            // the frame itself is only changed through stack.back()
+            const merge_frame frame = stack.back();
+            if (frame.position == frame.last)
+            {
+                stack.pop_back();
+                continue;
+            }
+
+            const const_iterator member = frame.position;
+            ++stack.back().position;
+            if (member.value().is_null())
+            {
+                frame.target->erase(member.key());
+            }
+            else
+            {
+                apply(frame.target->operator[](member.key()), member.value());
+            }
+        }
+    }
+
+  public:
     /// @}
 };
 

single_include/nlohmann/json.hpp

@@ -7028,9 +7028,48 @@ NLOHMANN_JSON_NAMESPACE_END
 #include <cstdint> // uint8_t
 #include <cstddef> // size_t
 #include <functional> // hash
+#include <vector> // vector
 
 // #include <nlohmann/detail/abi_macros.hpp>
 
+// #include <nlohmann/detail/recursion_depth_limit.hpp>
+//     __ _____ _____ _____
+//  __|  |   __|     |   | |  JSON for Modern C++
+// |  |  |__   |  |  | | | |  version 3.12.0
+// |_____|_____|_____|_|___|  https://github.com/nlohmann/json
+//
+// SPDX-FileCopyrightText: 2013-2026 Niels Lohmann <https://nlohmann.me>
+// SPDX-License-Identifier: MIT
+
+
+
+#include <cstddef> // size_t
+
+// #include <nlohmann/detail/abi_macros.hpp>
+
+
+NLOHMANN_JSON_NAMESPACE_BEGIN
+namespace detail
+{
+
+/*!
+@brief the number of nesting levels an operation recurses into
+
+Operations that walk a value (serializing, hashing, merging, ...) recurse once
+per nesting level, which is fastest, but a value nested deeply enough would
+exhaust the call stack. So they recurse only this many levels deep and finish
+whatever lies below with an explicit stack. All of them share this limit.
+
+@sa https://github.com/nlohmann/json/issues/5387
+*/
+constexpr std::size_t recursion_depth_limit() noexcept
+{
+    return 128;
+}
+
+}  // namespace detail
+NLOHMANN_JSON_NAMESPACE_END
+
 // #include <nlohmann/detail/value_t.hpp>
 
 
@@ -7045,6 +7084,9 @@ inline std::size_t combine(std::size_t seed, std::size_t h) noexcept
     return seed;
 }
 
+template<typename BasicJsonType>
+std::size_t hash_iteratively(const BasicJsonType& j);
+
 /*!
 @brief hash a JSON value
 
@@ -7052,12 +7094,21 @@ The hash function tries to rely on std::hash where possible. Furthermore, the
 type of the JSON value is taken into account to have different hash values for
 null, 0, 0U, and false, etc.
 
+Hashing an array or an object hashes its elements, which used to call this
+function again once per nesting level, so a value nested deeply enough
+exhausted the call stack and terminated the process. The descent is bounded
+here: once @ref recursion_depth_limit levels have been entered, @ref
+hash_iteratively hashes what is left without the call stack. A value nested
+less deeply than that - all but a vanishing minority - is hashed exactly as
+before, without allocating.
+
 @tparam BasicJsonType basic_json specialization
 @param j JSON value to hash
+@param depth nesting level of @a j, counted from the value passed by the caller
 @return hash value of j
 */
 template<typename BasicJsonType>
-std::size_t hash(const BasicJsonType& j)
+std::size_t hash(const BasicJsonType& j, const std::size_t depth = 0)
 {
     using string_t = typename BasicJsonType::string_t;
     using number_integer_t = typename BasicJsonType::number_integer_t;
@@ -7075,22 +7126,32 @@ std::size_t hash(const BasicJsonType& j)
 
         case BasicJsonType::value_t::object:
         {
+            if (JSON_HEDLEY_UNLIKELY(depth >= recursion_depth_limit()))
+            {
+                return hash_iteratively(j);
+            }
+
             auto seed = combine(type, j.size());
             for (const auto& element : j.items())
             {
                 const auto h = std::hash<string_t> {}(element.key());
                 seed = combine(seed, h);
-                seed = combine(seed, hash(element.value()));
+                seed = combine(seed, hash(element.value(), depth + 1));
             }
             return seed;
         }
 
         case BasicJsonType::value_t::array:
         {
+            if (JSON_HEDLEY_UNLIKELY(depth >= recursion_depth_limit()))
+            {
+                return hash_iteratively(j);
+            }
+
             auto seed = combine(type, j.size());
             for (const auto& element : j)
             {
-                seed = combine(seed, hash(element));
+                seed = combine(seed, hash(element, depth + 1));
             }
             return seed;
         }
@@ -7146,6 +7207,78 @@ std::size_t hash(const BasicJsonType& j)
     }
 }
 
+/// an array or object whose elements @ref hash_iteratively is hashing
+template<typename BasicJsonType>
+struct hash_frame
+{
+    hash_frame(const BasicJsonType* value_, std::size_t seed_) noexcept
+        : value(value_), position(value_->cbegin()), seed(seed_)
+    {}
+
+    const BasicJsonType* value;
+    typename BasicJsonType::const_iterator position;
+    std::size_t seed;
+};
+
+/*!
+@brief hash the array or object @a j without the call stack
+
+Computes the same value as @ref hash, keeping the arrays and objects it has
+entered on an explicit stack instead of descending into them. Only reached for
+values nested deeper than @ref recursion_depth_limit.
+
+@tparam BasicJsonType basic_json specialization
+@param j array or object to hash
+@return hash value of j
+*/
+template<typename BasicJsonType>
+std::size_t hash_iteratively(const BasicJsonType& j)
+{
+    using string_t = typename BasicJsonType::string_t;
+
+    std::vector<hash_frame<BasicJsonType>> stack;
+    stack.emplace_back(&j, combine(static_cast<std::size_t>(j.type()), j.size()));
+
+    while (true)
+    {
+        // a copy, as entering an element below can reallocate the stack; the
+        // frame itself is only changed through stack.back()
+        const hash_frame<BasicJsonType> frame = stack.back();
+
+        if (frame.position == frame.value->cend())
+        {
+            // all elements are hashed: fold this value's hash into its parent's
+            // seed, exactly where the recursive version returns it
+            const std::size_t h = frame.seed;
+            stack.pop_back();
+            if (stack.empty())
+            {
+                return h;
+            }
+            stack.back().seed = combine(stack.back().seed, h);
+            continue;
+        }
+
+        if (frame.value->is_object())
+        {
+            stack.back().seed = combine(stack.back().seed, std::hash<string_t> {}(frame.position.key()));
+        }
+
+        // advance before entering the element, which pushes onto the stack
+        const BasicJsonType& element = *frame.position;
+        ++stack.back().position;
+
+        if (element.is_structured())
+        {
+            stack.emplace_back(&element, combine(static_cast<std::size_t>(element.type()), element.size()));
+        }
+        else
+        {
+            stack.back().seed = combine(stack.back().seed, hash(element));
+        }
+    }
+}
+
 }  // namespace detail
 NLOHMANN_JSON_NAMESPACE_END
 
@@ -22295,6 +22428,8 @@ NLOHMANN_JSON_NAMESPACE_END
 
 // #include <nlohmann/detail/output/output_adapters.hpp>
 
+// #include <nlohmann/detail/recursion_depth_limit.hpp>
+
 // #include <nlohmann/detail/string_concat.hpp>
 
 // #include <nlohmann/detail/value_t.hpp>
@@ -22400,7 +22535,7 @@ class serializer
 
     Serializing a container descends into its elements, so a value nested deeply
     enough used to exhaust the call stack and terminate the process with no
-    exception to catch. The descent is bounded here: once @ref dump_depth_limit
+    exception to catch. The descent is bounded here: once @ref recursion_depth_limit
     levels have been entered, @ref dump_iteratively writes out what is left
     without the call stack. A value nested less deeply than that - all but a
     vanishing minority - is written by exactly the code that always wrote it.
@@ -22415,7 +22550,7 @@ class serializer
         {
             case value_t::object:
             {
-                if (JSON_HEDLEY_UNLIKELY(depth >= dump_depth_limit()))
+                if (JSON_HEDLEY_UNLIKELY(depth >= recursion_depth_limit()))
                 {
                     dump_iteratively(val, current_indent);
                     return;
@@ -22490,7 +22625,7 @@ class serializer
 
             case value_t::array:
             {
-                if (JSON_HEDLEY_UNLIKELY(depth >= dump_depth_limit()))
+                if (JSON_HEDLEY_UNLIKELY(depth >= recursion_depth_limit()))
                 {
                     dump_iteratively(val, current_indent);
                     return;
@@ -22675,19 +22810,12 @@ class serializer
     }
 
   private:
-    /// the number of levels @ref dump_internal descends into before it hands
-    /// over to @ref dump_iteratively
-    static constexpr std::size_t dump_depth_limit()
-    {
-        return 128;
-    }
-
     /*!
     @brief write out @a val and everything below it without the call stack
 
     Emits the same bytes as @ref dump_internal, keeping the containers it has
     entered on an explicit stack instead of descending into them. Only reached
-    for values nested deeper than @ref dump_depth_limit, which is why it is not
+    for values nested deeper than @ref recursion_depth_limit, which is why it is not
     written for speed: walking every value this way measured up to 20% slower on
     object-heavy documents than letting the compiler drive the descent.
     */
@@ -24000,6 +24128,8 @@ class serializer
 }  // namespace detail
 NLOHMANN_JSON_NAMESPACE_END
 
+// #include <nlohmann/detail/recursion_depth_limit.hpp>
+
 // #include <nlohmann/detail/value_t.hpp>
 
 // #include <nlohmann/json_fwd.hpp>
@@ -28241,17 +28371,54 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             JSON_THROW(type_error::create(312, detail::concat("cannot use update() with ", first.m_object->type_name()), first.m_object));
         }
 
+        update_members(first, last, merge_objects, 0);
+    }
+
+  private:
+    /// @brief an object @ref update_members_iteratively or @ref
+    /// merge_patch_iteratively is merging into, and the members still to merge
+    struct merge_frame
+    {
+        merge_frame(basic_json* target_, const_iterator position_, const_iterator last_) noexcept
+            : target(target_), position(std::move(position_)), last(std::move(last_))
+        {}
+
+        basic_json* target;
+        const_iterator position;
+        const_iterator last;
+    };
+
+    /*!
+    @brief the members loop of @ref update, for this object and range
+
+    Merging a nested object calls this function again, once per nesting
+    level, so a value 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
+    update_members_iteratively merges what is left without the call stack.
+
+    @param[in] depth  nesting level of this object, counted from the object
+                      @ref update was called on
+    */
+    void update_members(const const_iterator& first, const const_iterator& last, const bool merge_objects, const std::size_t depth)
+    {
+        if (JSON_HEDLEY_UNLIKELY(depth >= detail::recursion_depth_limit()))
+        {
+            update_members_iteratively(first, last);
+            return;
+        }
+
         for (auto it = first; it != last; ++it)
         {
             if (merge_objects && it.value().is_object())
             {
-                auto it2 = m_data.m_value.object->find(it.key());
+                const auto it2 = m_data.m_value.object->find(it.key());
                 // Only recurse when the existing value is itself an object.
                 // Otherwise overwrite, matching the documented "all other values
                 // are overwritten as usual" behavior (see #5402).
                 if (it2 != m_data.m_value.object->end() && it2->second.is_object())
                 {
-                    it2->second.update(it.value(), true);
+                    it2->second.update_members(it.value().cbegin(), it.value().cend(), true, depth + 1);
 #if JSON_DIAGNOSTICS
                     it2->second.set_parents();
 #endif
@@ -28265,6 +28432,64 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         }
     }
 
+    /*!
+    @brief merge @a first to @a last into this object without the call stack
+
+    Does the same as @ref update_members with `merge_objects` set, keeping the
+    objects whose merge was interrupted by a nested one on an explicit stack
+    instead of descending into them. A nested object is still merged
+    completely before the next member, in the same order as the recursive
+    version. Only reached for values nested deeper than @ref
+    detail::recursion_depth_limit.
+    */
+    void update_members_iteratively(const_iterator first, const_iterator last)
+    {
+        std::vector<merge_frame> stack;
+
+        basic_json* target = this;
+        while (true)
+        {
+            if (first == last)
+            {
+                if (stack.empty())
+                {
+                    break;
+                }
+
+                // a nested object is merged: continue with its parent
+#if JSON_DIAGNOSTICS
+                target->set_parents();
+#endif
+                target = stack.back().target;
+                first = stack.back().position;
+                last = stack.back().last;
+                stack.pop_back();
+                continue;
+            }
+
+            if (first.value().is_object())
+            {
+                const auto it2 = target->m_data.m_value.object->find(first.key());
+                if (it2 != target->m_data.m_value.object->end() && it2->second.is_object())
+                {
+                    const basic_json& source = first.value();
+                    ++first;
+                    stack.emplace_back(target, first, last);
+                    target = &it2->second;
+                    first = source.cbegin();
+                    last = source.cend();
+                    continue;
+                }
+            }
+            target->m_data.m_value.object->operator[](first.key()) = first.value();
+#if JSON_DIAGNOSTICS
+            target->m_data.m_value.object->operator[](first.key()).m_parent = target;
+#endif
+            ++first;
+        }
+    }
+
+  public:
     /// @brief exchanges the values
     /// @sa https://json.nlohmann.me/api/basic_json/swap/
     void swap(reference other) noexcept (
@@ -30159,9 +30384,30 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     /// @brief applies a JSON Merge Patch
     /// @sa https://json.nlohmann.me/api/basic_json/merge_patch/
     void merge_patch(const basic_json& apply_patch)
+    {
+        apply_merge_patch(apply_patch, 0);
+    }
+
+  private:
+    /*!
+    @brief @ref merge_patch, for a patch at nesting level @a depth
+
+    Applying a nested object calls this function again, once per nesting
+    level, so a patch 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
+    merge_patch_iteratively applies what is left without the call stack.
+    */
+    void apply_merge_patch(const basic_json& apply_patch, const std::size_t depth)
     {
         if (apply_patch.is_object())
         {
+            if (JSON_HEDLEY_UNLIKELY(depth >= detail::recursion_depth_limit()))
+            {
+                merge_patch_iteratively(apply_patch);
+                return;
+            }
+
             if (!is_object())
             {
                 *this = object();
@@ -30174,7 +30420,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                 }
                 else
                 {
-                    operator[](it.key()).merge_patch(it.value());
+                    operator[](it.key()).apply_merge_patch(it.value(), depth + 1);
                 }
             }
         }
@@ -30184,6 +30430,62 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         }
     }
 
+    /*!
+    @brief apply @a apply_patch to this value without the call stack
+
+    Does the same as @ref merge_patch, keeping the objects being patched on an
+    explicit stack instead of descending into them. A nested object is still
+    patched completely before the next member, in the same order as the
+    recursive version. Only reached for patches nested deeper than @ref
+    detail::recursion_depth_limit.
+    */
+    void merge_patch_iteratively(const basic_json& apply_patch)
+    {
+        std::vector<merge_frame> stack;
+
+        // patch `target` with `patch`, or start patching it member by member
+        const auto apply = [&stack](basic_json & target, const basic_json & patch)
+        {
+            if (patch.is_object())
+            {
+                if (!target.is_object())
+                {
+                    target = basic_json::object();
+                }
+                stack.emplace_back(&target, patch.cbegin(), patch.cend());
+            }
+            else
+            {
+                target = patch;
+            }
+        };
+
+        apply(*this, apply_patch);
+        while (!stack.empty())
+        {
+            // a copy, as applying a member below can reallocate the stack;
+            // the frame itself is only changed through stack.back()
+            const merge_frame frame = stack.back();
+            if (frame.position == frame.last)
+            {
+                stack.pop_back();
+                continue;
+            }
+
+            const const_iterator member = frame.position;
+            ++stack.back().position;
+            if (member.value().is_null())
+            {
+                frame.target->erase(member.key());
+            }
+            else
+            {
+                apply(frame.target->operator[](member.key()), member.value());
+            }
+        }
+    }
+
+  public:
     /// @}
 };
 

tests/src/unit-diagnostics.cpp

@@ -363,3 +363,52 @@ TEST_CASE("Regression tests for extended diagnostics")
     }
 }
 
+TEST_CASE("Better diagnostics past the descent bound of update() and merge_patch()")
+{
+    // Both merge objects nested more than detail::recursion_depth_limit()
+    // (128) levels deep without recursing; the values they add or replace
+    // there must still know their parents.
+    // The values are built rather than parsed, so that the expected messages
+    // carry no byte positions under JSON_DIAGNOSTIC_POSITIONS.
+    const std::size_t depth = 200;
+    json target = {{"x", 1}};
+    json patch = {{"y", 2}};
+    std::string path;
+    for (std::size_t i = 0; i < depth; ++i)
+    {
+        target = json{{"a", std::move(target)}};
+        patch = json{{"a", std::move(patch)}};
+        path += "/a";
+    }
+    const std::string expected_x = "[json.exception.type_error.304] (" + path + "/x) cannot use at() with number";
+    const std::string expected_y = "[json.exception.type_error.304] (" + path + "/y) cannot use at() with number";
+
+    SECTION("update()")
+    {
+        json j = target;
+        j.update(patch, true);
+
+        // walk down through const references, which leave m_parent alone
+        const json* p = &j;
+        for (std::size_t i = 0; i < depth; ++i)
+        {
+            p = &p->at("a");
+        }
+        CHECK_THROWS_WITH_AS(p->at("x").at(0), expected_x.c_str(), json::type_error);
+        CHECK_THROWS_WITH_AS(p->at("y").at(0), expected_y.c_str(), json::type_error);
+    }
+
+    SECTION("merge_patch()")
+    {
+        json j = target;
+        j.merge_patch(patch);
+
+        const json* p = &j;
+        for (std::size_t i = 0; i < depth; ++i)
+        {
+            p = &p->at("a");
+        }
+        CHECK_THROWS_WITH_AS(p->at("x").at(0), expected_x.c_str(), json::type_error);
+        CHECK_THROWS_WITH_AS(p->at("y").at(0), expected_y.c_str(), json::type_error);
+    }
+}

tests/src/unit-hash.cpp

@@ -13,6 +13,78 @@ using json = nlohmann::json;
 using ordered_json = nlohmann::ordered_json;
 
 #include <set>
+#include <string>
+
+namespace
+{
+// how detail::hash defines the hash of an array or object: the seeds of the
+// elements, combined in order. Recursive, so only usable on values nested a
+// few hundred levels deep - which is exactly what is needed to check that the
+// iterative path taken below detail::recursion_depth_limit() computes the same.
+template<typename BasicJsonType>
+std::size_t reference_hash(const BasicJsonType& j)
+{
+    using nlohmann::detail::combine;
+    using string_t = typename BasicJsonType::string_t;
+
+    if (!j.is_structured())
+    {
+        return std::hash<BasicJsonType> {}(j);
+    }
+
+    auto seed = combine(static_cast<std::size_t>(j.type()), j.size());
+    for (const auto& element : j.items())
+    {
+        if (j.is_object())
+        {
+            seed = combine(seed, std::hash<string_t> {}(element.key()));
+        }
+        seed = combine(seed, reference_hash(element.value()));
+    }
+    return seed;
+}
+
+// a value nested `depth` levels deep, with siblings on every level
+template<typename BasicJsonType>
+BasicJsonType nested(const std::size_t depth, const bool objects)
+{
+    BasicJsonType value = "leaf";
+    for (std::size_t i = 0; i < depth; ++i)
+    {
+        if (objects)
+        {
+            value = BasicJsonType{{"before", i}, {"nested", std::move(value)}, {"after", {i, "x"}}};
+        }
+        else
+        {
+            value = BasicJsonType::array({i, std::move(value), BasicJsonType::object({{"k", i}})});
+        }
+    }
+    return value;
+}
+
+std::string nested_text(const std::size_t depth, const bool objects)
+{
+    std::string text;
+    if (objects)
+    {
+        text.reserve((6 * depth) + 1);
+        for (std::size_t i = 0; i < depth; ++i)
+        {
+            text += "{\"a\":";
+        }
+        text += "1";
+        text.append(depth, '}');
+    }
+    else
+    {
+        text.assign(depth, '[');
+        text += "1";
+        text.append(depth, ']');
+    }
+    return text;
+}
+} // namespace
 
 TEST_CASE("hash<nlohmann::json>")
 {
@@ -111,3 +183,44 @@ TEST_CASE("hash<nlohmann::ordered_json>")
 
     CHECK(hashes.size() == 21);
 }
+
+TEST_CASE("hash of deeply nested values")
+{
+    SECTION("hashing past the descent bound computes the same values")
+    {
+        // every depth on either side of where the iterative path takes over
+        for (std::size_t depth = 0; depth <= (2 * nlohmann::detail::recursion_depth_limit()) + 10; ++depth)
+        {
+            CAPTURE(depth);
+            const auto arrays = nested<json>(depth, false);
+            const auto objects = nested<json>(depth, true);
+            const auto ordered = nested<ordered_json>(depth, true);
+            CHECK(std::hash<json> {}(arrays) == reference_hash(arrays));
+            CHECK(std::hash<json> {}(objects) == reference_hash(objects));
+            CHECK(std::hash<ordered_json> {}(ordered) == reference_hash(ordered));
+        }
+    }
+
+    SECTION("values nested too deeply for the call stack (#5545)")
+    {
+        // recursing once per level used to exhaust the call stack here; the
+        // values are only parsed and hashed, never copied or compared, since
+        // those recurse as well
+        const std::size_t depth = 100000;
+        for (const bool objects :
+                {
+                    false, true
+                })
+        {
+            CAPTURE(objects);
+            const auto text = nested_text(depth, objects);
+            const auto a = json::parse(text);
+            const auto b = json::parse(text);
+            CHECK(std::hash<json> {}(a) == std::hash<json> {}(b));
+
+            const auto c = ordered_json::parse(text);
+            const auto d = ordered_json::parse(text);
+            CHECK(std::hash<ordered_json> {}(c) == std::hash<ordered_json> {}(d));
+        }
+    }
+}

tests/src/unit-merge_patch.cpp

@@ -14,6 +14,60 @@ using nlohmann::json;
     using namespace nlohmann::literals; // NOLINT(google-build-using-namespace)
 #endif
 
+#include <string>
+
+namespace
+{
+// RFC 7396's MergePatch, written recursively as in the RFC; only usable on
+// values nested a few hundred levels deep
+void reference_merge_patch(json& target, const json& patch)
+{
+    if (!patch.is_object())
+    {
+        target = patch;
+        return;
+    }
+    if (!target.is_object())
+    {
+        target = json::object();
+    }
+    for (auto it = patch.begin(); it != patch.end(); ++it)
+    {
+        if (it.value().is_null())
+        {
+            target.erase(it.key());
+        }
+        else
+        {
+            reference_merge_patch(target[it.key()], it.value());
+        }
+    }
+}
+
+// objects nested `depth` levels deep under the key "a", with members that
+// differ by `variant` on the way down
+std::string nested_objects(const std::size_t depth, const int variant)
+{
+    std::string text;
+    for (std::size_t i = 0; i < depth; ++i)
+    {
+        text += "{";
+        if ((i + static_cast<std::size_t>(variant)) % 3 == 0)
+        {
+            text += "\"s" + std::to_string(variant) + "\":" + std::to_string(i) + ",";
+        }
+        if (variant == 2 && i % 5 == 0)
+        {
+            text += "\"s0\":null,";
+        }
+        text += "\"a\":";
+    }
+    text += variant == 1 ? "{\"x\":1,\"y\":null}" : "{\"y\":2}";
+    text.append(depth, '}');
+    return text;
+}
+} // namespace
+
 TEST_CASE("JSON Merge Patch")
 {
     SECTION("examples from RFC 7396")
@@ -242,3 +296,52 @@ TEST_CASE("JSON Merge Patch")
         }
     }
 }
+
+TEST_CASE("JSON Merge Patch on deeply nested values")
+{
+    SECTION("patching past the descent bound gives the same result")
+    {
+        // every depth on either side of where the iterative version takes
+        // over (detail::recursion_depth_limit(), 128)
+        for (std::size_t depth = 0; depth <= 300; ++depth)
+        {
+            CAPTURE(depth);
+            for (int variant = 0; variant < 3; ++variant)
+            {
+                CAPTURE(variant);
+                const json patch = json::parse(nested_objects(depth, variant));
+
+                json result = json::parse(nested_objects(depth, (variant + 1) % 3));
+                json expected = result;
+                result.merge_patch(patch);
+                reference_merge_patch(expected, patch);
+                CHECK(result == expected);
+
+                // a target that is not an object, and an empty one
+                json from_null;
+                from_null.merge_patch(patch);
+                json expected_from_null;
+                reference_merge_patch(expected_from_null, patch);
+                CHECK(from_null == expected_from_null);
+            }
+        }
+    }
+
+    SECTION("patches nested too deeply for the call stack (#5393)")
+    {
+        // applying a patch used to recurse once per nesting level. The result
+        // is only walked, never copied or compared, since those recurse too.
+        const std::size_t depth = 100000;
+        json target = json::parse(nested_objects(depth, 0));
+        target.merge_patch(json::parse(nested_objects(depth, 1)));
+
+        const json* p = &target;
+        for (std::size_t i = 0; i < depth; ++i)
+        {
+            p = &p->at("a");
+        }
+        // {"y":2} patched with {"x":1,"y":null}
+        CHECK(p->size() == 1);
+        CHECK(p->at("x") == 1);
+    }
+}

tests/src/unit-modifiers.cpp

@@ -11,6 +11,53 @@
 #include <nlohmann/json.hpp>
 using nlohmann::json;
 
+#include <string>
+
+namespace
+{
+// update(source, true) as documented, written recursively; only usable on
+// values nested a few hundred levels deep
+void reference_update(json& target, const json& source)
+{
+    for (auto it = source.begin(); it != source.end(); ++it)
+    {
+        const auto existing = target.find(it.key());
+        if (it.value().is_object() && existing != target.end() && existing->is_object())
+        {
+            reference_update(*existing, it.value());
+        }
+        else
+        {
+            target[it.key()] = it.value();
+        }
+    }
+}
+
+// objects nested `depth` levels deep under the key "a", with members that
+// differ by `variant` on the way down
+std::string nested_objects(const std::size_t depth, const int variant)
+{
+    std::string text;
+    for (std::size_t i = 0; i < depth; ++i)
+    {
+        text += "{";
+        if ((i + static_cast<std::size_t>(variant)) % 3 == 0)
+        {
+            text += "\"s" + std::to_string(variant) + "\":" + std::to_string(i) + ",";
+        }
+        if (variant == 2 && i % 5 == 0)
+        {
+            // an object replacing a primitive, which is not merged
+            text += "\"s0\":{\"o\":1},";
+        }
+        text += "\"a\":";
+    }
+    text += variant == 1 ? "{\"x\":1}" : "{\"y\":2}";
+    text.append(depth, '}');
+    return text;
+}
+} // namespace
+
 TEST_CASE("modifiers")
 {
     SECTION("clear()")
@@ -988,3 +1035,44 @@ TEST_CASE("modifiers")
         }
     }
 }
+
+TEST_CASE("update() on deeply nested values")
+{
+    SECTION("merging past the descent bound gives the same result")
+    {
+        // every depth on either side of where the iterative version takes
+        // over (detail::recursion_depth_limit(), 128)
+        for (std::size_t depth = 0; depth <= 300; ++depth)
+        {
+            CAPTURE(depth);
+            for (int variant = 0; variant < 3; ++variant)
+            {
+                CAPTURE(variant);
+                const json source = json::parse(nested_objects(depth, variant));
+                json result = json::parse(nested_objects(depth, (variant + 1) % 3));
+                json expected = result;
+                result.update(source, true);
+                reference_update(expected, source);
+                CHECK(result == expected);
+            }
+        }
+    }
+
+    SECTION("objects nested too deeply for the call stack (#5545)")
+    {
+        // merging used to recurse once per nesting level. The result is only
+        // walked, never copied or compared, since those recurse too.
+        const std::size_t depth = 100000;
+        json target = json::parse(nested_objects(depth, 0));
+        target.update(json::parse(nested_objects(depth, 1)), true);
+
+        const json* p = &target;
+        for (std::size_t i = 0; i < depth; ++i)
+        {
+            p = &p->at("a");
+        }
+        CHECK(p->size() == 2);
+        CHECK(p->at("x") == 1);
+        CHECK(p->at("y") == 2);
+    }
+}