Test that destroy() performs no allocation, even under memory pressure

Update the #4842 regression test: it used to check that destroying a
nested array/object made at least one allocation through the provided
allocator (the old flattening stack). Now that destroy() does not
allocate at all, assert the opposite: zero allocations, deallocations
only.

Rework the #5135 regression test to use a dedicated failing/counting
allocator instead of overriding the process-wide ::operator new and
::operator delete, which affected every allocation in the whole
unit-regression2 binary rather than just the values under test. Keep
the original small repro as one case, and add deep (100000 levels) and
wide-and-deep nested array/object/ordered_json cases, all destroyed
while every further allocation is made to fail: the destructor must
complete without allocating, without throwing, and without leaking.

Co-authored-by: Michael Sam <9461037+michaelsam94@users.noreply.github.com>
Signed-off-by: Niels Lohmann <mail@nlohmann.me>

include/nlohmann/json.hpp

@@ -612,6 +612,68 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         /// constructor for rvalue binary arrays (internal type)
         json_value(binary_t&& value) : binary(create<binary_t>(std::move(value))) {}
 
+        // raw, allocation-free transfer of m_data from src to dst: no
+        // set_parents()/assert_invariant() (the former is O(#children) per
+        // call under JSON_DIAGNOSTICS, which would make the walk below
+        // quadratic); dst takes ownership, src is left as value_t::null.
+        static void take(basic_json& dst, basic_json& src) noexcept
+        {
+            dst.m_data.m_type = src.m_data.m_type;
+            dst.m_data.m_value = src.m_data.m_value;
+            src.m_data.m_type = value_t::null;
+        }
+
+        static bool is_empty_container(const basic_json& v) noexcept
+        {
+            return v.m_data.m_type == value_t::array
+                   ? v.m_data.m_value.array->empty()
+                   : v.m_data.m_value.object->empty();
+        }
+
+        static basic_json& last_child(basic_json& v)
+        {
+            return v.m_data.m_type == value_t::array
+                   ? v.m_data.m_value.array->back()
+                   : std::prev(v.m_data.m_value.object->end())->second;
+        }
+
+        // removes the last child of a non-empty array/object v; this never
+        // allocates, and since it is only ever called when that child is a
+        // scalar or an already-empty array/object, destroying it never
+        // recurses more than one level deep (see destroy() below)
+        static void pop_last_child(basic_json& v)
+        {
+            if (v.m_data.m_type == value_t::array)
+            {
+                v.m_data.m_value.array->pop_back();
+            }
+            else
+            {
+                v.m_data.m_value.object->erase(std::prev(v.m_data.m_value.object->end()));
+            }
+        }
+
+        // deallocates the (already empty) array/object held by v; this is
+        // the same allocator-based free the old recursive implementation
+        // used, just factored out so every level of the walk in destroy()
+        // can share it
+        static void free_container(basic_json& v) noexcept
+        {
+            if (v.m_data.m_type == value_t::array)
+            {
+                AllocatorType<array_t> alloc;
+                std::allocator_traits<decltype(alloc)>::destroy(alloc, v.m_data.m_value.array);
+                std::allocator_traits<decltype(alloc)>::deallocate(alloc, v.m_data.m_value.array, 1);
+            }
+            else
+            {
+                AllocatorType<object_t> alloc;
+                std::allocator_traits<decltype(alloc)>::destroy(alloc, v.m_data.m_value.object);
+                std::allocator_traits<decltype(alloc)>::deallocate(alloc, v.m_data.m_value.object, 1);
+            }
+            v.m_data.m_type = value_t::null; // avoid a double free if v is later destructed
+        }
+
         void destroy(value_t t)
         {
             if (
@@ -626,71 +688,88 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             }
             if (t == value_t::array || t == value_t::object)
             {
-                // flatten the current json_value to a heap-allocated stack
+                // Destroy the tree without recursing per nesting level and
-                std::vector<basic_json> stack;
+                // without any heap allocation: a heap-allocated flattening
-
+                // stack (the previous implementation) can itself throw
-                // move the top-level items to stack
+                // bad_alloc, which would escape this noexcept destructor and
+                // terminate the program (#5135).
+                //
+                // Instead, walk down the "last child" chain, reversing links
+                // as we go: cur is the container currently being emptied,
+                // and prev is its parent (value_t::null when there is none).
+                // Each parent's last child slot doubles as storage for that
+                // parent's own parent link while we are below it, so no
+                // extra memory is needed. We only ever remove a child once
+                // it is a scalar or an empty array/object, which neither
+                // allocates nor recurses more than one level deep.
+                //
+                // This json_value is not itself a basic_json, so the
+                // top-level container is first moved into a local stand-in
+                // ("cur"); this union's own pointer is cleared so it is
+                // never looked at or freed a second time.
+                basic_json cur;
+                cur.m_data.m_type = t;
+                cur.m_data.m_value = *this;
                 if (t == value_t::array)
                 {
-                    stack.reserve(array->size());
+                    array = nullptr;
-                    std::move(array->begin(), array->end(), std::back_inserter(stack));
                 }
                 else
                 {
-                    stack.reserve(object->size());
+                    object = nullptr;
-                    for (auto&& it : *object)
-                    {
-                        stack.push_back(std::move(it.second));
-                    }
                 }
 
-                while (!stack.empty())
+                basic_json prev; // value_t::null: no parent
+
+                while (true)
                 {
-                    // move the last item to a local variable to be processed
+                    if (is_empty_container(cur))
-                    basic_json current_item(std::move(stack.back()));
-                    stack.pop_back();
-
-                    // if current_item is array/object, move
-                    // its children to the stack to be processed later
-                    if (current_item.is_array())
                     {
-                        std::move(current_item.m_data.m_value.array->begin(), current_item.m_data.m_value.array->end(), std::back_inserter(stack));
+                        if (prev.m_data.m_type == value_t::null)
-
-                        current_item.m_data.m_value.array->clear();
-                    }
-                    else if (current_item.is_object())
-                    {
-                        for (auto&& it : *current_item.m_data.m_value.object)
                         {
-                            stack.push_back(std::move(it.second));
+                            break; // back at the top with nothing left to do
                         }
 
-                        current_item.m_data.m_value.object->clear();
+                        // ascend: detach the grandparent link from prev's
+                        // last slot, drop that (now null) slot, free cur
+                        // (it is empty), then move up one level
+                        basic_json gp;
+                        take(gp, last_child(prev));
+                        pop_last_child(prev);
+
+                        free_container(cur);
+
+                        take(cur, prev);
+                        take(prev, gp);
+                        continue;
                     }
 
-                    // it's now safe that current_item gets destructed
+                    basic_json& last = last_child(cur);
-                    // since it doesn't have any children
+                    const bool last_is_container = last.m_data.m_type == value_t::array || last.m_data.m_type == value_t::object;
+
+                    if (!last_is_container || is_empty_container(last))
+                    {
+                        // scalar, or already-empty array/object
+                        pop_last_child(cur);
+                        continue;
+                    }
+
+                    // descend into the non-empty last child, reversing the
+                    // link: its slot takes over prev, and the child becomes
+                    // the new cur
+                    basic_json tmp;
+                    take(tmp, last);
+                    take(last, prev);
+                    take(prev, cur);
+                    take(cur, tmp);
                 }
+
+                free_container(cur);
+                return;
             }
 
             switch (t)
             {
-                case value_t::object:
-                {
-                    AllocatorType<object_t> alloc;
-                    std::allocator_traits<decltype(alloc)>::destroy(alloc, object);
-                    std::allocator_traits<decltype(alloc)>::deallocate(alloc, object, 1);
-                    break;
-                }
-
-                case value_t::array:
-                {
-                    AllocatorType<array_t> alloc;
-                    std::allocator_traits<decltype(alloc)>::destroy(alloc, array);
-                    std::allocator_traits<decltype(alloc)>::deallocate(alloc, array, 1);
-                    break;
-                }
-
                 case value_t::string:
                 {
                     AllocatorType<string_t> alloc;

single_include/nlohmann/json.hpp

@@ -27734,6 +27734,68 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         /// constructor for rvalue binary arrays (internal type)
         json_value(binary_t&& value) : binary(create<binary_t>(std::move(value))) {}
 
+        // raw, allocation-free transfer of m_data from src to dst: no
+        // set_parents()/assert_invariant() (the former is O(#children) per
+        // call under JSON_DIAGNOSTICS, which would make the walk below
+        // quadratic); dst takes ownership, src is left as value_t::null.
+        static void take(basic_json& dst, basic_json& src) noexcept
+        {
+            dst.m_data.m_type = src.m_data.m_type;
+            dst.m_data.m_value = src.m_data.m_value;
+            src.m_data.m_type = value_t::null;
+        }
+
+        static bool is_empty_container(const basic_json& v) noexcept
+        {
+            return v.m_data.m_type == value_t::array
+                   ? v.m_data.m_value.array->empty()
+                   : v.m_data.m_value.object->empty();
+        }
+
+        static basic_json& last_child(basic_json& v)
+        {
+            return v.m_data.m_type == value_t::array
+                   ? v.m_data.m_value.array->back()
+                   : std::prev(v.m_data.m_value.object->end())->second;
+        }
+
+        // removes the last child of a non-empty array/object v; this never
+        // allocates, and since it is only ever called when that child is a
+        // scalar or an already-empty array/object, destroying it never
+        // recurses more than one level deep (see destroy() below)
+        static void pop_last_child(basic_json& v)
+        {
+            if (v.m_data.m_type == value_t::array)
+            {
+                v.m_data.m_value.array->pop_back();
+            }
+            else
+            {
+                v.m_data.m_value.object->erase(std::prev(v.m_data.m_value.object->end()));
+            }
+        }
+
+        // deallocates the (already empty) array/object held by v; this is
+        // the same allocator-based free the old recursive implementation
+        // used, just factored out so every level of the walk in destroy()
+        // can share it
+        static void free_container(basic_json& v) noexcept
+        {
+            if (v.m_data.m_type == value_t::array)
+            {
+                AllocatorType<array_t> alloc;
+                std::allocator_traits<decltype(alloc)>::destroy(alloc, v.m_data.m_value.array);
+                std::allocator_traits<decltype(alloc)>::deallocate(alloc, v.m_data.m_value.array, 1);
+            }
+            else
+            {
+                AllocatorType<object_t> alloc;
+                std::allocator_traits<decltype(alloc)>::destroy(alloc, v.m_data.m_value.object);
+                std::allocator_traits<decltype(alloc)>::deallocate(alloc, v.m_data.m_value.object, 1);
+            }
+            v.m_data.m_type = value_t::null; // avoid a double free if v is later destructed
+        }
+
         void destroy(value_t t)
         {
             if (
@@ -27748,71 +27810,88 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             }
             if (t == value_t::array || t == value_t::object)
             {
-                // flatten the current json_value to a heap-allocated stack
+                // Destroy the tree without recursing per nesting level and
-                std::vector<basic_json> stack;
+                // without any heap allocation: a heap-allocated flattening
-
+                // stack (the previous implementation) can itself throw
-                // move the top-level items to stack
+                // bad_alloc, which would escape this noexcept destructor and
+                // terminate the program (#5135).
+                //
+                // Instead, walk down the "last child" chain, reversing links
+                // as we go: cur is the container currently being emptied,
+                // and prev is its parent (value_t::null when there is none).
+                // Each parent's last child slot doubles as storage for that
+                // parent's own parent link while we are below it, so no
+                // extra memory is needed. We only ever remove a child once
+                // it is a scalar or an empty array/object, which neither
+                // allocates nor recurses more than one level deep.
+                //
+                // This json_value is not itself a basic_json, so the
+                // top-level container is first moved into a local stand-in
+                // ("cur"); this union's own pointer is cleared so it is
+                // never looked at or freed a second time.
+                basic_json cur;
+                cur.m_data.m_type = t;
+                cur.m_data.m_value = *this;
                 if (t == value_t::array)
                 {
-                    stack.reserve(array->size());
+                    array = nullptr;
-                    std::move(array->begin(), array->end(), std::back_inserter(stack));
                 }
                 else
                 {
-                    stack.reserve(object->size());
+                    object = nullptr;
-                    for (auto&& it : *object)
-                    {
-                        stack.push_back(std::move(it.second));
-                    }
                 }
 
-                while (!stack.empty())
+                basic_json prev; // value_t::null: no parent
+
+                while (true)
                 {
-                    // move the last item to a local variable to be processed
+                    if (is_empty_container(cur))
-                    basic_json current_item(std::move(stack.back()));
-                    stack.pop_back();
-
-                    // if current_item is array/object, move
-                    // its children to the stack to be processed later
-                    if (current_item.is_array())
                     {
-                        std::move(current_item.m_data.m_value.array->begin(), current_item.m_data.m_value.array->end(), std::back_inserter(stack));
+                        if (prev.m_data.m_type == value_t::null)
-
-                        current_item.m_data.m_value.array->clear();
-                    }
-                    else if (current_item.is_object())
-                    {
-                        for (auto&& it : *current_item.m_data.m_value.object)
                         {
-                            stack.push_back(std::move(it.second));
+                            break; // back at the top with nothing left to do
                         }
 
-                        current_item.m_data.m_value.object->clear();
+                        // ascend: detach the grandparent link from prev's
+                        // last slot, drop that (now null) slot, free cur
+                        // (it is empty), then move up one level
+                        basic_json gp;
+                        take(gp, last_child(prev));
+                        pop_last_child(prev);
+
+                        free_container(cur);
+
+                        take(cur, prev);
+                        take(prev, gp);
+                        continue;
                     }
 
-                    // it's now safe that current_item gets destructed
+                    basic_json& last = last_child(cur);
-                    // since it doesn't have any children
+                    const bool last_is_container = last.m_data.m_type == value_t::array || last.m_data.m_type == value_t::object;
+
+                    if (!last_is_container || is_empty_container(last))
+                    {
+                        // scalar, or already-empty array/object
+                        pop_last_child(cur);
+                        continue;
+                    }
+
+                    // descend into the non-empty last child, reversing the
+                    // link: its slot takes over prev, and the child becomes
+                    // the new cur
+                    basic_json tmp;
+                    take(tmp, last);
+                    take(last, prev);
+                    take(prev, cur);
+                    take(cur, tmp);
                 }
+
+                free_container(cur);
+                return;
             }
 
             switch (t)
             {
-                case value_t::object:
-                {
-                    AllocatorType<object_t> alloc;
-                    std::allocator_traits<decltype(alloc)>::destroy(alloc, object);
-                    std::allocator_traits<decltype(alloc)>::deallocate(alloc, object, 1);
-                    break;
-                }
-
-                case value_t::array:
-                {
-                    AllocatorType<array_t> alloc;
-                    std::allocator_traits<decltype(alloc)>::destroy(alloc, array);
-                    std::allocator_traits<decltype(alloc)>::deallocate(alloc, array, 1);
-                    break;
-                }
-
                 case value_t::string:
                 {
                     AllocatorType<string_t> alloc;

tests/src/unit-allocator.cpp

@@ -602,3 +602,72 @@ TEST_CASE("bad my_allocator::construct")
         j["test"].push_back("should not leak");
     }
 }
+
+namespace
+{
+std::size_t counting_allocator_allocations = 0;
+std::size_t counting_allocator_deallocations = 0;
+
+template<class T>
+struct counting_allocator : std::allocator<T>
+{
+    using std::allocator<T>::allocator;
+
+    T* allocate(std::size_t n)
+    {
+        ++counting_allocator_allocations;
+        return std::allocator<T>::allocate(n);
+    }
+
+    void deallocate(T* p, std::size_t n)
+    {
+        ++counting_allocator_deallocations;
+        std::allocator<T>::deallocate(p, n);
+    }
+
+    template <class U>
+    struct rebind
+    {
+        using other = counting_allocator<U>;
+    };
+};
+} // namespace
+
+TEST_CASE("destructor performs no allocation, only deallocation")
+{
+    // see https://github.com/nlohmann/json/issues/4842 and
+    // https://github.com/nlohmann/json/issues/5135: destroying nested
+    // arrays/objects used to allocate a temporary stack (first with
+    // std::allocator, later - after #4842 - with the provided allocator).
+    // Since that stack could itself throw bad_alloc from inside the
+    // noexcept destructor (#5135), destroy() no longer allocates anything:
+    // it only ever frees what is already there.
+    using counting_json = nlohmann::basic_json<std::map,
+          std::vector,
+          std::string,
+          bool,
+          std::int64_t,
+          std::uint64_t,
+          double,
+          counting_allocator>;
+
+    SECTION("array")
+    {
+        auto* j = new counting_json({1, {2, {3, 4}}, 5}); // NOLINT(cppcoreguidelines-owning-memory)
+        const auto allocations_before = counting_allocator_allocations;
+        const auto deallocations_before = counting_allocator_deallocations;
+        delete j; // NOLINT(cppcoreguidelines-owning-memory)
+        CHECK(counting_allocator_allocations == allocations_before);
+        CHECK(counting_allocator_deallocations > deallocations_before);
+    }
+
+    SECTION("object")
+    {
+        auto* j = new counting_json({{"a", {{"b", {1, 2}}}}, {"c", 3}}); // NOLINT(cppcoreguidelines-owning-memory)
+        const auto allocations_before = counting_allocator_allocations;
+        const auto deallocations_before = counting_allocator_deallocations;
+        delete j; // NOLINT(cppcoreguidelines-owning-memory)
+        CHECK(counting_allocator_allocations == allocations_before);
+        CHECK(counting_allocator_deallocations > deallocations_before);
+    }
+}

tests/src/unit-regression2.cpp

@@ -40,7 +40,9 @@ using ordered_json = nlohmann::ordered_json;
 #endif
 
 #include <cstdio>
+#include <cstdlib>
 #include <list>
+#include <new>
 #include <tuple>
 #include <type_traits>
 #include <utility>
@@ -107,6 +109,84 @@ DOCTEST_CLANG_SUPPRESS_WARNING("-Wexit-time-destructors")
 
 using float_json = nlohmann::basic_json<std::map, std::vector, std::string, bool, std::int64_t, std::uint64_t, float>;
 
+#if (defined(__cpp_exceptions) || defined(__EXCEPTIONS) || defined(_CPPUNWIND)) && !defined(JSON_NOEXCEPTION)
+namespace
+{
+// An allocator whose allocate() can be told to fail on demand, so tests can
+// check that ~basic_json() tolerates - in fact, after #5135, never even
+// triggers - an allocation failure. This replaces an earlier version of
+// this test that overrode the process-wide ::operator new/::operator
+// delete, which affected every allocation in the whole unit-regression2
+// binary rather than just the values under test.
+std::size_t failing_allocator_allocations = 0;
+std::size_t failing_allocator_deallocations = 0;
+bool fail_next_allocation = false;
+
+template<class T>
+struct failing_allocator : std::allocator<T>
+{
+    using std::allocator<T>::allocator;
+
+    failing_allocator() noexcept = default;
+    template<class U>
+    failing_allocator(const failing_allocator<U>& /*unused*/) noexcept {} // NOLINT(google-explicit-constructor)
+
+    T* allocate(std::size_t n)
+    {
+        if (fail_next_allocation)
+        {
+            fail_next_allocation = false;
+            throw std::bad_alloc();
+        }
+        ++failing_allocator_allocations;
+        return std::allocator<T>::allocate(n);
+    }
+
+    void deallocate(T* p, std::size_t n)
+    {
+        ++failing_allocator_deallocations;
+        std::allocator<T>::deallocate(p, n);
+    }
+
+    template<class U>
+    struct rebind
+    {
+        using other = failing_allocator<U>;
+    };
+};
+
+using failing_json = nlohmann::basic_json<std::map, std::vector, std::string, bool,
+      std::int64_t, std::uint64_t, double, failing_allocator>;
+using failing_ordered_json = nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::string, bool,
+      std::int64_t, std::uint64_t, double, failing_allocator>;
+
+// builds `depth` levels of nesting around a scalar, iteratively (never
+// recursing: each wrap only moves the previous, already-built value, which
+// is O(1)), each level an array or an object depending on `nest_objects`
+template<class BasicJsonType>
+BasicJsonType make_deep_nest(std::size_t depth, bool nest_objects)
+{
+    BasicJsonType v = 0;
+    for (std::size_t i = 0; i < depth; ++i)
+    {
+        if (nest_objects)
+        {
+            BasicJsonType wrapper = BasicJsonType::object();
+            wrapper["x"] = std::move(v);
+            v = std::move(wrapper);
+        }
+        else
+        {
+            BasicJsonType wrapper = BasicJsonType::array();
+            wrapper.push_back(std::move(v));
+            v = std::move(wrapper);
+        }
+    }
+    return v;
+}
+} // namespace
+#endif
+
 /////////////////////////////////////////////////////////////////////
 // for #1647
 /////////////////////////////////////////////////////////////////////
@@ -940,4 +1020,100 @@ TEST_CASE("regression test - excessive binary container size honors allow_except
     CHECK(json::from_cbor(std::vector<std::uint8_t> {0x9b, 0, 0, 0, 0, 0, 0, 0, 0x02}, true, false).is_discarded());
 }
 
+#if (defined(__cpp_exceptions) || defined(__EXCEPTIONS) || defined(_CPPUNWIND)) && !defined(JSON_NOEXCEPTION)
+TEST_CASE("regression test #5135 - destructor never allocates, even under memory pressure")
+{
+    // Before the fix, ~basic_json() flattened a nested array/object into a
+    // heap-allocated std::vector to avoid recursing; that allocation could
+    // itself throw bad_alloc, which escapes a noexcept destructor and
+    // terminates the program. destroy() no longer allocates anything, so
+    // none of the sections below ever observe fail_next_allocation being
+    // consumed: CHECK(fail_next_allocation) confirms it was never touched.
+
+    SECTION("the original report: a small, mixed array/object nest")
+    {
+        failing_allocator_allocations = 0;
+        failing_allocator_deallocations = 0;
+        {
+            failing_json j = failing_json::array(
+            {
+                failing_json::array({1, 2}),
+                failing_json::object({{"key", failing_json::array({3})}})
+            });
+            fail_next_allocation = true;
+        } // j is destroyed here, with every further allocation set to fail
+
+        CHECK(fail_next_allocation);
+        fail_next_allocation = false;
+        CHECK(failing_allocator_deallocations > 0);
+    }
+
+    SECTION("100000-deep nested array")
+    {
+        std::size_t allocations_before = 0;
+        {
+            failing_json j = make_deep_nest<failing_json>(100000, false);
+            allocations_before = failing_allocator_allocations;
+            fail_next_allocation = true;
+        }
+
+        CHECK(fail_next_allocation);
+        fail_next_allocation = false;
+        CHECK(failing_allocator_allocations == allocations_before);
+    }
+
+    SECTION("100000-deep nested object")
+    {
+        std::size_t allocations_before = 0;
+        {
+            failing_json j = make_deep_nest<failing_json>(100000, true);
+            allocations_before = failing_allocator_allocations;
+            fail_next_allocation = true;
+        }
+
+        CHECK(fail_next_allocation);
+        fail_next_allocation = false;
+        CHECK(failing_allocator_allocations == allocations_before);
+    }
+
+    SECTION("100000-deep nested ordered_json")
+    {
+        std::size_t allocations_before = 0;
+        {
+            failing_ordered_json j = make_deep_nest<failing_ordered_json>(100000, true);
+            allocations_before = failing_allocator_allocations;
+            fail_next_allocation = true;
+        }
+
+        CHECK(fail_next_allocation);
+        fail_next_allocation = false;
+        CHECK(failing_allocator_allocations == allocations_before);
+    }
+
+    SECTION("wide and deep: 1000 arrays of 1000 elements, each a small nested object")
+    {
+        std::size_t allocations_before = 0;
+        {
+            failing_json wide = failing_json::array();
+            for (std::size_t i = 0; i < 1000; ++i)
+            {
+                failing_json inner = failing_json::array();
+                for (std::size_t k = 0; k < 1000; ++k)
+                {
+                    inner.push_back(failing_json::object({{"a", 1}, {"b", failing_json::array({1, 2, 3})}}));
+                }
+                wide.push_back(std::move(inner));
+            }
+
+            allocations_before = failing_allocator_allocations;
+            fail_next_allocation = true;
+        }
+
+        CHECK(fail_next_allocation);
+        fail_next_allocation = false;
+        CHECK(failing_allocator_allocations == allocations_before);
+    }
+}
+#endif
+
 DOCTEST_CLANG_SUPPRESS_WARNING_POP