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>

docs/mkdocs/docs/features/types/template_parameters.md

@@ -389,7 +389,6 @@ using array_t = ArrayType<basic_json, AllocatorType<basic_json>>;
 | Functionality                                                                                                                     | Additional requirement                                                                                                                                                                       |
 |-----------------------------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
 | [`diff`](../../api/basic_json/diff.md), [`items`](../../api/basic_json/items.md), [`std::hash`](../../api/basic_json/std_hash.md) | conversion of a `#!cpp std::size_t` to `StringType`: either assignability from the result of `#!cpp std::to_string`, or an ADL overload `#!cpp void int_to_string(StringType&, std::size_t)` |
-| [`operator/(std::size_t)`](../../api/json_pointer/operator_slash.md)                                                              | the same conversion of a `#!cpp std::size_t` to `StringType` as `diff`, `items`, and `std::hash` above                                                                                       |
 | [`std::hash<basic_json>`](../../api/basic_json/std_hash.md)                                                                       | additionally a specialization of `#!cpp std::hash<StringType>`                                                                                                                               |
 | [`to_bson`](../../api/basic_json/to_bson.md)                                                                                      | `find(value_type)` and `npos`                                                                                                                                                                |
 | [`parse`](../../api/basic_json/parse.md) from a `string_t`                                                                        | the input adapters must accept it; otherwise pass a character range                                                                                                                          |

include/nlohmann/detail/json_pointer.hpp

@@ -26,7 +26,6 @@
 #include <nlohmann/detail/macro_scope.hpp>
 #include <nlohmann/detail/string_concat.hpp>
 #include <nlohmann/detail/string_escape.hpp>
-#include <nlohmann/detail/string_utils.hpp>
 #include <nlohmann/detail/value_t.hpp>
 
 NLOHMANN_JSON_NAMESPACE_BEGIN
@@ -117,7 +116,7 @@ class json_pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/operator_slasheq/
     json_pointer& operator/=(std::size_t array_idx)
     {
-        return *this /= detail::to_string<string_t>(array_idx);
+        return *this /= std::to_string(array_idx);
     }
 
     /// @brief create a new JSON pointer by appending the right JSON pointer at the end of the left JSON pointer
@@ -747,7 +746,7 @@ class json_pointer
                         // "-" always fails the range check
                         return false;
                     }
-                    if (JSON_HEDLEY_UNLIKELY(reference_token.size() == 1 && !('0' <= reference_token[0] && reference_token[0] <= '9')))
+                    if (JSON_HEDLEY_UNLIKELY(reference_token.size() == 1 && !("0" <= reference_token && reference_token <= "9")))
                     {
                         // invalid char
                         return false;
@@ -775,7 +774,7 @@ class json_pointer
                     // not throw (see #5395), so such a reference token is treated as "not found"
                     errno = 0; // strtoull() does not reset errno on success
                     char* p_end = nullptr; // NOLINT(misc-const-correctness)
-                    const unsigned long long magnitude = std::strtoull(reference_token.data(), &p_end, 10); // NOLINT(runtime/int)
+                    const unsigned long long magnitude = std::strtoull(reference_token.c_str(), &p_end, 10); // NOLINT(runtime/int)
                     if (JSON_HEDLEY_UNLIKELY(errno == ERANGE // the value exceeds ULLONG_MAX
                                              || magnitude >= static_cast<unsigned long long>((std::numeric_limits<typename BasicJsonType::size_type>::max)()))) // NOLINT(runtime/int)
                     {

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

@@ -18867,8 +18867,6 @@ NLOHMANN_JSON_NAMESPACE_END
 
 // #include <nlohmann/detail/string_escape.hpp>
 
-// #include <nlohmann/detail/string_utils.hpp>
-
 // #include <nlohmann/detail/value_t.hpp>
 
 
@@ -18960,7 +18958,7 @@ class json_pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/operator_slasheq/
     json_pointer& operator/=(std::size_t array_idx)
     {
-        return *this /= detail::to_string<string_t>(array_idx);
+        return *this /= std::to_string(array_idx);
     }
 
     /// @brief create a new JSON pointer by appending the right JSON pointer at the end of the left JSON pointer
@@ -19590,7 +19588,7 @@ class json_pointer
                         // "-" always fails the range check
                         return false;
                     }
-                    if (JSON_HEDLEY_UNLIKELY(reference_token.size() == 1 && !('0' <= reference_token[0] && reference_token[0] <= '9')))
+                    if (JSON_HEDLEY_UNLIKELY(reference_token.size() == 1 && !("0" <= reference_token && reference_token <= "9")))
                     {
                         // invalid char
                         return false;
@@ -19618,7 +19616,7 @@ class json_pointer
                     // not throw (see #5395), so such a reference token is treated as "not found"
                     errno = 0; // strtoull() does not reset errno on success
                     char* p_end = nullptr; // NOLINT(misc-const-correctness)
-                    const unsigned long long magnitude = std::strtoull(reference_token.data(), &p_end, 10); // NOLINT(runtime/int)
+                    const unsigned long long magnitude = std::strtoull(reference_token.c_str(), &p_end, 10); // NOLINT(runtime/int)
                     if (JSON_HEDLEY_UNLIKELY(errno == ERANGE // the value exceeds ULLONG_MAX
                                              || magnitude >= static_cast<unsigned long long>((std::numeric_limits<typename BasicJsonType::size_type>::max)()))) // NOLINT(runtime/int)
                     {
@@ -27201,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();
@@ -27229,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;
@@ -27291,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

tests/src/unit-alt-string.cpp

@@ -343,41 +343,6 @@ TEST_CASE("alternative string type")
         CHECK(j2.flatten().unflatten() == j2);
     }
 
-    SECTION("contains(json_pointer)")
-    {
-        // contains(json_pointer) must compile and work with a string_t that has
-        // no c_str() and no comparison with const char* (see #5666)
-        auto j = alt_json::parse(R"({"foo": ["bar", "baz"]})");
-
-        // present: object key and array indices
-        CHECK(j.contains(alt_json::json_pointer("/foo")));
-        CHECK(j.contains(alt_json::json_pointer("/foo/0")));
-        CHECK(j.contains(alt_json::json_pointer("/foo/1")));
-
-        // missing: absent object key and out-of-range array index
-        CHECK_FALSE(j.contains(alt_json::json_pointer("/bar")));
-        CHECK_FALSE(j.contains(alt_json::json_pointer("/foo/2")));
-
-        // "-" always fails the range check
-        CHECK_FALSE(j.contains(alt_json::json_pointer("/foo/-")));
-
-        // an array index must not have a leading zero
-        CHECK_FALSE(j.contains(alt_json::json_pointer("/foo/01")));
-
-        // a reference token that is not a number
-        CHECK_FALSE(j.contains(alt_json::json_pointer("/foo/bar")));
-    }
-
-    SECTION("operator/(std::size_t)")
-    {
-        // json_pointer::operator/=(std::size_t) must compile without string_t
-        // being constructible from std::string (see #5666)
-        auto j = alt_json::parse(R"({"foo": ["bar", "baz"]})");
-
-        CHECK(j.at(alt_json::json_pointer("/foo") / std::size_t(0)) == j["foo"][0]);
-        CHECK(j.at(alt_json::json_pointer("/foo") / std::size_t(1)) == j["foo"][1]);
-    }
-
     SECTION("patch")
     {
         alt_json const patch1 = alt_json::parse(R"([{ "op": "add", "path": "/a/b", "value": [ "foo", "bar" ] }])");