Give a deep copy its type only after its container exists

When copying a value nested deeper than 128 levels, and an allocation
fails while an inner array or object is being copied, the partially
built copy ended up with an element typed array/object but holding a
null pointer. That element was already a fully constructed member of
its parent's container, so destroying the parent during stack
unwinding dereferenced the null pointer (release builds) or failed
assert_invariant() (debug builds), instead of letting std::bad_alloc
reach the caller.

copy_iteratively() set a pending worklist element's type right after
popping it, before the next loop iteration created its container in
copy_array_level()/copy_object_level(). Move that type assignment into
those two functions, right after the container is successfully
created, and drop the premature one in copy_iteratively(), so a
half-built element stays a null value - as copy_shallow()'s comment
already promised - until it can safely hold one.

Add a regression test to tests/src/unit-allocator.cpp that copies a
value nested 130 levels deep (both arrays and objects, with a
std::map- and an ordered_map-backed object_t) and fails every
allocation of the copy in turn: each attempt must throw std::bad_alloc
without crashing, and the source must stay unchanged.

Fixes #5640.

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

include/nlohmann/json.hpp

@@ -1118,6 +1118,8 @@ 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();
@@ -1146,6 +1148,8 @@ 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;
@@ -1208,9 +1212,6 @@ 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;
         }
     }
 

single_include/nlohmann/json.hpp

@@ -27199,6 +27199,8 @@ 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();
@@ -27227,6 +27229,8 @@ 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;
@@ -27289,9 +27293,6 @@ 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;
         }
     }
 

tests/src/unit-allocator.cpp

@@ -276,6 +276,133 @@ 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