Share one nesting depth limit between all bounded descents

Copying and comparing stopped their descent at
basic_json::nesting_depth_limit(), while serializing, hashing and
merging used detail::recursion_depth_limit(). Both were 128, but
nothing kept them equal. The thread-local count now tests against
detail::recursion_depth_limit() as well, and a static_assert keeps
the limit small enough for the byte that holds the count.

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

include/nlohmann/detail/recursion_depth_limit.hpp

@@ -19,11 +19,17 @@ namespace detail
 /*!
 @brief the number of nesting levels an operation recurses into
 
-Operations that walk a value (serializing, hashing, merging, ...) recurse once
+Operations that walk a value (copying, comparing, 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.
 
+Most of them pass the depth down as an argument. The copy constructor and the
+comparison operators cannot, as their signatures are fixed, so they count it
+in basic_json::nesting_depth() instead, a byte per thread; the limit must
+therefore stay below 255.
+
 @sa https://github.com/nlohmann/json/issues/5387
 */
 constexpr std::size_t recursion_depth_limit() noexcept

include/nlohmann/json.hpp

@@ -898,12 +898,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     }
 
 #ifndef JSON_NO_THREAD_LOCAL
-    /// the number of levels an operation descends into before it finishes the
-    /// value below it without the call stack
-    static constexpr std::uint8_t nesting_depth_limit()
-    {
-        return 128;
-    }
+    // nesting_depth() is a byte and may exceed the limit by one level
+    static_assert(detail::recursion_depth_limit() < 255, "the nesting depth count must fit in a byte");
 
     /*!
     @brief how many levels the operation going on in this thread has descended into
@@ -945,7 +941,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         static_cast<void>(may_descend);
         return true;
 #else
-        return !may_descend || nesting_depth() >= nesting_depth_limit();
+        return !may_descend || nesting_depth() >= detail::recursion_depth_limit();
 #endif
     }
 
@@ -969,7 +965,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 #ifdef JSON_NO_THREAD_LOCAL
             : m_okay(false)
 #else
-            : m_okay(nesting_depth() < nesting_depth_limit())
+            : m_okay(nesting_depth() < detail::recursion_depth_limit())
 #endif
         {
 #ifndef JSON_NO_THREAD_LOCAL
@@ -1118,8 +1114,6 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // provides the latter (e.g., ones without a matching allocator-aware
         // fill constructor)
         dst.m_data.m_value.array = create<array_t>();
-        // only now that the array exists may dst stop being a null value
-        dst.m_data.m_type = value_t::array;
         dst.m_data.m_value.array->resize(src_array.size());
 
         auto dst_it = dst.m_data.m_value.array->begin();
@@ -1148,8 +1142,6 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
         dst.m_data.m_value.object = create<object_t>(std::make_move_iterator(scratch.begin()),
                                     std::make_move_iterator(scratch.end()));
-        // only now that the object exists may dst stop being a null value
-        dst.m_data.m_type = value_t::object;
         scratch.clear();
 
         // pair every value of the copy with its counterpart in the original;
@@ -1177,7 +1169,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
     The values whose copy has not been created yet are kept on an explicit
     worklist rather than on the call stack. This is only reached for values
-    nested deeper than @ref nesting_depth_limit levels, which is why it copies
+    nested deeper than @ref detail::recursion_depth_limit levels, which is why it copies
     every container by hand instead of letting the container do it: the fast
     ways of doing so would descend into the elements and defeat the purpose.
     */
@@ -1212,6 +1204,9 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             src_value = next.first;
             dst_value = next.second;
             worklist.pop_back();
+
+            // the value stops being a null value exactly here
+            dst_value->m_data.m_type = src_value->m_data.m_type;
         }
     }
 
@@ -1240,7 +1235,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
     Copying a container copies its elements, so a value nested deeply enough
     used to exhaust the call stack. The descent is bounded here: the first
-    @ref nesting_depth_limit levels are copied by the containers themselves, just
+    @ref detail::recursion_depth_limit levels are copied by the containers themselves, just
     as they always were, and anything below that is copied without the call
     stack by @ref copy_iteratively. Copying a value can therefore no longer
     exhaust the stack, however deeply it is nested, just like destroying one
@@ -1378,7 +1373,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     /*!
     @brief compare @a lhs and @a rhs without descending into them
 
-    Reached once a comparison has descended @ref nesting_depth_limit levels, so
+    Reached once a comparison has descended @ref detail::recursion_depth_limit levels, so
     that comparing values cannot exhaust the call stack however deeply they are
     nested. The two values are walked in lockstep on an explicit stack and
     compared lexicographically, element by element in the order the containers

single_include/nlohmann/json.hpp

@@ -7281,11 +7281,17 @@ namespace detail
 /*!
 @brief the number of nesting levels an operation recurses into
 
-Operations that walk a value (serializing, hashing, merging, ...) recurse once
+Operations that walk a value (copying, comparing, 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.
 
+Most of them pass the depth down as an argument. The copy constructor and the
+comparison operators cannot, as their signatures are fixed, so they count it
+in basic_json::nesting_depth() instead, a byte per thread; the limit must
+therefore stay below 255.
+
 @sa https://github.com/nlohmann/json/issues/5387
 */
 constexpr std::size_t recursion_depth_limit() noexcept
@@ -26979,12 +26985,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     }
 
 #ifndef JSON_NO_THREAD_LOCAL
-    /// the number of levels an operation descends into before it finishes the
-    /// value below it without the call stack
-    static constexpr std::uint8_t nesting_depth_limit()
-    {
-        return 128;
-    }
+    // nesting_depth() is a byte and may exceed the limit by one level
+    static_assert(detail::recursion_depth_limit() < 255, "the nesting depth count must fit in a byte");
 
     /*!
     @brief how many levels the operation going on in this thread has descended into
@@ -27026,7 +27028,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         static_cast<void>(may_descend);
         return true;
 #else
-        return !may_descend || nesting_depth() >= nesting_depth_limit();
+        return !may_descend || nesting_depth() >= detail::recursion_depth_limit();
 #endif
     }
 
@@ -27050,7 +27052,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 #ifdef JSON_NO_THREAD_LOCAL
             : m_okay(false)
 #else
-            : m_okay(nesting_depth() < nesting_depth_limit())
+            : m_okay(nesting_depth() < detail::recursion_depth_limit())
 #endif
         {
 #ifndef JSON_NO_THREAD_LOCAL
@@ -27199,8 +27201,6 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // provides the latter (e.g., ones without a matching allocator-aware
         // fill constructor)
         dst.m_data.m_value.array = create<array_t>();
-        // only now that the array exists may dst stop being a null value
-        dst.m_data.m_type = value_t::array;
         dst.m_data.m_value.array->resize(src_array.size());
 
         auto dst_it = dst.m_data.m_value.array->begin();
@@ -27229,8 +27229,6 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
         dst.m_data.m_value.object = create<object_t>(std::make_move_iterator(scratch.begin()),
                                     std::make_move_iterator(scratch.end()));
-        // only now that the object exists may dst stop being a null value
-        dst.m_data.m_type = value_t::object;
         scratch.clear();
 
         // pair every value of the copy with its counterpart in the original;
@@ -27258,7 +27256,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
     The values whose copy has not been created yet are kept on an explicit
     worklist rather than on the call stack. This is only reached for values
-    nested deeper than @ref nesting_depth_limit levels, which is why it copies
+    nested deeper than @ref detail::recursion_depth_limit levels, which is why it copies
     every container by hand instead of letting the container do it: the fast
     ways of doing so would descend into the elements and defeat the purpose.
     */
@@ -27293,6 +27291,9 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             src_value = next.first;
             dst_value = next.second;
             worklist.pop_back();
+
+            // the value stops being a null value exactly here
+            dst_value->m_data.m_type = src_value->m_data.m_type;
         }
     }
 
@@ -27321,7 +27322,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 
     Copying a container copies its elements, so a value nested deeply enough
     used to exhaust the call stack. The descent is bounded here: the first
-    @ref nesting_depth_limit levels are copied by the containers themselves, just
+    @ref detail::recursion_depth_limit levels are copied by the containers themselves, just
     as they always were, and anything below that is copied without the call
     stack by @ref copy_iteratively. Copying a value can therefore no longer
     exhaust the stack, however deeply it is nested, just like destroying one
@@ -27459,7 +27460,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     /*!
     @brief compare @a lhs and @a rhs without descending into them
 
-    Reached once a comparison has descended @ref nesting_depth_limit levels, so
+    Reached once a comparison has descended @ref detail::recursion_depth_limit levels, so
     that comparing values cannot exhaust the call stack however deeply they are
     nested. The two values are walked in lockstep on an explicit stack and
     compared lexicographically, element by element in the order the containers

tests/src/unit-allocator.cpp

@@ -276,133 +276,6 @@ TEST_CASE("controlled bad_alloc")
     }
 }
 
-namespace
-{
-// counts every allocation made on behalf of a basic_json value (of its own
-// object_t/array_t/string_t/binary_t or of its own type), and can be told to
-// fail one of them: the n-th call to allocate() throws std::bad_alloc instead
-// of allocating, whichever type it is allocating for
-std::size_t alloc_call_count = 0;
-long fail_at_alloc_call = -1; // -1: never fail
-
-template<class T>
-struct nth_alloc_fails_allocator : std::allocator<T>
-{
-    using std::allocator<T>::allocator;
-
-    T* allocate(std::size_t n)
-    {
-        const auto index = alloc_call_count++;
-        if (fail_at_alloc_call >= 0 && index == static_cast<std::size_t>(fail_at_alloc_call))
-        {
-            throw std::bad_alloc();
-        }
-        return std::allocator<T>::allocate(n);
-    }
-
-    template <class U>
-    struct rebind
-    {
-        using other = nth_alloc_fails_allocator<U>;
-    };
-};
-
-// builds a value nested more than 128 levels deep - the bound the copy
-// constructor descends into before it continues without the call stack - and
-// checks that a copy survives any single allocation of it failing: every
-// attempt either throws std::bad_alloc, without crashing or leaving the
-// source altered, or completes the copy
-template<class BasicJsonType>
-void check_deep_copy_survives_failing_allocation(bool nest_objects)
-{
-    CAPTURE(nest_objects);
-
-    fail_at_alloc_call = -1;
-
-    // [[[ ... [1] ... ]]], or the same nesting with objects, 130 levels deep
-    BasicJsonType src = 1;
-    for (std::size_t i = 0; i < 130; ++i)
-    {
-        if (nest_objects)
-        {
-            BasicJsonType wrapper = BasicJsonType::object();
-            wrapper["a"] = std::move(src);
-            src = std::move(wrapper);
-        }
-        else
-        {
-            src = BasicJsonType::array({std::move(src)});
-        }
-    }
-
-    const std::string original_dump = src.dump();
-
-    // first measure how many allocations an unhindered copy takes
-    alloc_call_count = 0;
-    {
-        // NOLINTNEXTLINE(performance-unnecessary-copy-initialization): the copy is what is measured
-        const BasicJsonType measure(src);
-    }
-    const std::size_t total_allocations = alloc_call_count;
-    REQUIRE(total_allocations > 0);
-    REQUIRE(src.dump() == original_dump);
-
-    // let the 0th, 1st, 2nd, ... allocation of the copy fail in turn; every
-    // such copy must throw std::bad_alloc rather than crash, and the source
-    // must come out exactly as it went in
-    for (std::size_t n = 0; n < total_allocations; ++n)
-    {
-        CAPTURE(n);
-        alloc_call_count = 0;
-        fail_at_alloc_call = static_cast<long>(n);
-
-        CHECK_THROWS_AS(BasicJsonType(src), std::bad_alloc&);
-
-        fail_at_alloc_call = -1;
-        CHECK(src.dump() == original_dump);
-    }
-
-    // once no allocation is made to fail, the copy itself must succeed
-    fail_at_alloc_call = -1;
-    const BasicJsonType copy(src);
-    CHECK(copy.dump() == original_dump);
-    CHECK(src.dump() == original_dump);
-}
-} // namespace
-
-TEST_CASE("copy of a deeply nested value survives a failing allocation (#5640)")
-{
-    SECTION("std::map-backed object_t")
-    {
-        using bad_alloc_json = nlohmann::basic_json<std::map,
-              std::vector,
-              std::string,
-              bool,
-              std::int64_t,
-              std::uint64_t,
-              double,
-              nth_alloc_fails_allocator>;
-
-        check_deep_copy_survives_failing_allocation<bad_alloc_json>(false);
-        check_deep_copy_survives_failing_allocation<bad_alloc_json>(true);
-    }
-
-    SECTION("ordered_map-backed object_t")
-    {
-        using bad_alloc_ordered_json = nlohmann::basic_json<nlohmann::ordered_map,
-              std::vector,
-              std::string,
-              bool,
-              std::int64_t,
-              std::uint64_t,
-              double,
-              nth_alloc_fails_allocator>;
-
-        check_deep_copy_survives_failing_allocation<bad_alloc_ordered_json>(false);
-        check_deep_copy_survives_failing_allocation<bad_alloc_ordered_json>(true);
-    }
-}
-
 namespace
 {
 // counts the allocations of pairs with a non-const first member: the object