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

tools/amalgamate/CHANGES.md

@@ -8,6 +8,3 @@ The following changes have been made to the code with respect to <https://github
   - membership check
   - made function from `_is_within`
   - removed unused variable `actual_path`
-- Added the optional config key `external`: include paths listed there are kept as
-  `#include` directives instead of being inlined (the first directive per path; the
-  repeated ones are commented out).

tools/amalgamate/README.md

@@ -57,11 +57,6 @@ Python v.2.7.0 or higher is required.
    amalgamation. Have a look at `test/source.c.json` and `test/include.h.json`
    to see two examples.
 
-   The optional `external` list names include paths that are kept as `#include`
-   directives instead of being inlined, e.g. `["nlohmann/json.hpp"]` for a header
-   that includes another amalgamated header. Only the first directive for each
-   of these paths is kept; the repeated ones are commented out.
-
  * The `-s, --source` option should specify the path to the source directory.
    This is useful for supporting separate source and build directories.
 

tools/amalgamate/amalgamate.py

@@ -62,10 +62,6 @@ class Amalgamation(object):
         return None
 
     def __init__(self, args):
-        # include paths that are kept as #include directives instead of
-        # being inlined (e.g. a header amalgamated on its own)
-        self.external = []
-        self.included_external = []
         with open(args.config, 'r') as f:
             config = json.loads(f.read())
             for key in config:
@@ -224,14 +220,11 @@ class TranslationUnit(object):
         while include_match:
             if not _is_within(include_match, skippable_contexts):
                 include_path = include_match.group("path")
-                if include_path in self.amalgamation.external:
-                    includes.append((include_match, None))
-                else:
-                    search_same_dir = include_match.group(1) == '"'
-                    found_included_path = self.amalgamation.find_included_file(
-                        include_path, self.file_dir if search_same_dir else None)
-                    if found_included_path:
-                        includes.append((include_match, found_included_path))
+                search_same_dir = include_match.group(1) == '"'
+                found_included_path = self.amalgamation.find_included_file(
+                    include_path, self.file_dir if search_same_dir else None)
+                if found_included_path:
+                    includes.append((include_match, found_included_path))
 
             include_match = self.include_pattern.search(self.content,
                                                         include_match.end())
@@ -242,17 +235,6 @@ class TranslationUnit(object):
         for include in includes:
             include_match, found_included_path = include
             tmp_content += self.content[prev_end:include_match.start()]
-            if found_included_path is None:
-                # an external header: keep the first directive and comment
-                # out the repeated ones
-                include_path = include_match.group("path")
-                if include_path in self.amalgamation.included_external:
-                    tmp_content += "// {0}".format(include_match.group(0))
-                else:
-                    self.amalgamation.included_external.append(include_path)
-                    tmp_content += include_match.group(0)
-                prev_end = include_match.end()
-                continue
             tmp_content += "// {0}\n".format(include_match.group(0))
             if found_included_path not in self.amalgamation.included_files:
                 t = TranslationUnit(found_included_path, self.amalgamation, False)

tools/amalgamate/config_json_view.json

@@ -1,9 +0,0 @@
-{
-	"project": "JSON for Modern C++",
-	"target": "single_include/nlohmann/json_view.hpp",
-	"sources": [
-		"include/nlohmann/json_view.hpp"
-	],
-	"include_paths": ["include"],
-	"external": ["nlohmann/json.hpp"]
-}