Fix quadratic parent updates for ordered_json with JSON_DIAGNOSTICS

set_parent() re-parented the whole container for ordered_json on every
call (push_back, emplace_back, at(), operator[] on existing keys),
making array building quadratic. at() and array append now set only the
one child's parent; object insertion re-parents only if the vector
capacity changed. Also drop the redundant set_parents() in the copy
constructor. Adds a parent-pointer invariant test.

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

docs/mkdocs/docs/api/basic_json/array_t.md

@@ -27,7 +27,7 @@ To store objects in C++, a type is defined by the template parameters explained
 
 ### Default type
 
-With the default values for `ArrayType` (`std::vector`) and `AllocatorType` (`std::allocator`), the default value for
+With the default values for `ArrayType` (`std::vector`) and `AllocatorType` (`std::allocator`), the default type for
 `array_t` is:
 
 ```cpp

docs/mkdocs/docs/api/basic_json/boolean_t.md

@@ -23,7 +23,7 @@ To store boolean values in C++, a type is defined by the template parameter  `Bo
 
 ### Default type
 
-With the default values for `BooleanType` (`#!cpp bool`), the default value for `boolean_t` is `#!cpp bool`.
+With the default values for `BooleanType` (`#!cpp bool`), the default type for `boolean_t` is `#!cpp bool`.
 
 ### Storage
 

docs/mkdocs/docs/api/basic_json/number_float_t.md

@@ -35,7 +35,7 @@ type to use.
 
 ### Default type
 
-With the default values for `NumberFloatType` (`double`), the default value for `number_float_t` is `#!cpp double`.
+With the default values for `NumberFloatType` (`double`), the default type for `number_float_t` is `#!cpp double`.
 
 ### Default behavior
 
@@ -52,8 +52,9 @@ With the default values for `NumberFloatType` (`double`), the default value for
 > interoperability can be achieved by implementations that expect no more precision or range than these provide, in the
 > sense that implementations will approximate JSON numbers within the expected precision.
 
-This implementation does exactly follow this approach, as it uses double precision floating-point numbers. Note that
+This implementation does exactly follow this approach, as it uses double precision floating-point numbers by default.
-numbers smaller than `-1.79769313486232e+308` or greater than `1.79769313486232e+308` are rejected during parsing with
+Note that with the default `double`, numbers smaller than `-1.79769313486232e+308` or greater than
+`1.79769313486232e+308` are rejected during parsing with
 [`out_of_range.406`](../../home/exceptions.md#jsonexceptionout_of_range406). Non-finite values (NaN and infinity) can
 only be stored by assigning them directly and are serialized to `null`.
 

docs/mkdocs/docs/api/basic_json/number_integer_t.md

@@ -31,7 +31,7 @@ to use.
 
 ### Default type
 
-With the default values for `NumberIntegerType` (`std::int64_t`), the default value for `number_integer_t` is
+With the default values for `NumberIntegerType` (`std::int64_t`), the default type for `number_integer_t` is
 `#!cpp std::int64_t`.
 
 ### Default behavior

docs/mkdocs/docs/api/basic_json/number_unsigned_t.md

@@ -32,7 +32,7 @@ the type to use.
 
 ### Default type
 
-With the default values for `NumberUnsignedType` (`std::uint64_t`), the default value for `number_unsigned_t` is
+With the default values for `NumberUnsignedType` (`std::uint64_t`), the default type for `number_unsigned_t` is
 `#!cpp std::uint64_t`.
 
 ### Default behavior

docs/mkdocs/docs/api/basic_json/object_t.md

@@ -36,7 +36,7 @@ To store objects in C++, a type is defined by the template parameters described
 ### Default type
 
 With the default values for `ObjectType` (`std::map`), `StringType` (`std::string`), and `AllocatorType`
-(`std::allocator`), the default value for `object_t` is:
+(`std::allocator`), the default type for `object_t` is:
 
 ```cpp
 // until C++14

docs/mkdocs/docs/api/basic_json/string_t.md

@@ -32,7 +32,7 @@ JSON class into byte-sized characters during deserialization.
 
 ### Default type
 
-With the default values for `StringType` (`std::string`), the default value for `string_t` is `#!cpp std::string`.
+With the default values for `StringType` (`std::string`), the default type for `string_t` is `#!cpp std::string`.
 
 ### Encoding
 

docs/mkdocs/docs/features/types/index.md

@@ -120,7 +120,7 @@ requirements are collected in [Template Parameter Requirements](template_paramet
 
 ### Default type
 
-With the default values for *ObjectType* (`std::map`), *StringType* (`std::string`), and *AllocatorType* (`std::allocator`), the default value for `object_t` is:
+With the default values for *ObjectType* (`std::map`), *StringType* (`std::string`), and *AllocatorType* (`std::allocator`), the default type for `object_t` is:
 
 ```cpp
 std::map<
@@ -177,7 +177,7 @@ json j = m;
 
 ### Default type
 
-With the default values for *ArrayType* (`std::vector`) and *AllocatorType* (`std::allocator`), the default value for `array_t` is:
+With the default values for *ArrayType* (`std::vector`) and *AllocatorType* (`std::allocator`), the default type for `array_t` is:
 
 ```cpp
 std::vector<
@@ -209,7 +209,7 @@ Unicode values are split by the JSON class into byte-sized characters during des
 
 ### Default type
 
-With the default values for *StringType* (`std::string`), the default value for `string_t` is `#!cpp std::string`.
+With the default values for *StringType* (`std::string`), the default type for `string_t` is `#!cpp std::string`.
 
 ### Encoding
 
@@ -234,7 +234,7 @@ String values are stored as pointers in a `basic_json` type. That is, for any ac
 
 ### Default type
 
-With the default values for *BooleanType* (`#!cpp bool`), the default value for `boolean_t` is `#!cpp bool`.
+With the default values for *BooleanType* (`#!cpp bool`), the default type for `boolean_t` is `#!cpp bool`.
 
 ### Storage
 
@@ -252,9 +252,9 @@ This description includes both integer and floating-point numbers. However, C++
 
 ### Default types
 
-With the default values for *NumberIntegerType* (`std::int64_t`), the default value for `number_integer_t` is `std::int64_t`.
+With the default values for *NumberIntegerType* (`std::int64_t`), the default type for `number_integer_t` is `std::int64_t`.
-With the default values for *NumberUnsignedType* (`std::uint64_t`), the default value for `number_unsigned_t` is `std::uint64_t`.
+With the default values for *NumberUnsignedType* (`std::uint64_t`), the default type for `number_unsigned_t` is `std::uint64_t`.
-With the default values for *NumberFloatType* (`#!cpp double`), the default value for `number_float_t` is `#!cpp double`.
+With the default values for *NumberFloatType* (`#!cpp double`), the default type for `number_float_t` is `#!cpp double`.
 
 ### Default behavior
 
@@ -281,7 +281,7 @@ As this range is a subrange of the exactly supported range [`INT64_MIN`, `INT64_
 
 > This specification allows implementations to set limits on the range and precision of numbers accepted. Since software that implements IEEE 754-2008 binary64 (double precision) numbers is generally available and widely used, good interoperability can be achieved by implementations that expect no more precision or range than these provide, in the sense that implementations will approximate JSON numbers within the expected precision.
 
-This implementation does exactly follow this approach, as it uses double precision floating-point numbers. Note that numbers smaller than `#!c -1.79769313486232e+308` or greater than `#!c 1.79769313486232e+308` are rejected during parsing with [`out_of_range.406`](../../home/exceptions.md#jsonexceptionout_of_range406). Non-finite values (NaN and infinity) can only be stored by assigning them directly and are serialized to `#!json null`.
+This implementation does exactly follow this approach, as it uses double precision floating-point numbers by default (see *NumberFloatType* above). Note that with the default `#!cpp double`, numbers smaller than `#!c -1.79769313486232e+308` or greater than `#!c 1.79769313486232e+308` are rejected during parsing with [`out_of_range.406`](../../home/exceptions.md#jsonexceptionout_of_range406). Non-finite values (NaN and infinity) can only be stored by assigning them directly and are serialized to `#!json null`.
 
 ### Storage
 

include/nlohmann/json.hpp

@@ -1123,7 +1123,60 @@ public:
 #else
         static_cast<void>(old_capacity);
 #endif
-        return set_parent(j);
+        set_parent_plain(j);
+        return j;
+    }
+
+    /// @brief capacity of the stored object if it is vector-backed (ordered_map), else 0
+#if JSON_DIAGNOSTICS
+    template < typename O = object_t, detail::enable_if_t < detail::has_capacity<O>::value, int > = 0 >
+    std::size_t object_capacity() const noexcept
+    {
+        return m_data.m_value.object->capacity();
+    }
+
+    template < typename O = object_t, detail::enable_if_t < !detail::has_capacity<O>::value, int > = 0 >
+    std::size_t object_capacity() const noexcept
+    {
+        return 0;
+    }
+#else
+    static constexpr std::size_t object_capacity() noexcept
+    {
+        return 0;
+    }
+#endif
+
+    /// @brief set parent of an element that was just looked up or inserted into an object
+    reference set_parent_after_object_emplace(reference j, std::size_t old_capacity)
+    {
+#if JSON_DIAGNOSTICS
+        if (JSON_HEDLEY_UNLIKELY(object_capacity() != old_capacity))
+        {
+            set_parents();
+            return j;
+        }
+        j.m_parent = this;
+#else
+        static_cast<void>(old_capacity);
+#endif
+        return j;
+    }
+
+    void set_parent_plain(reference j) noexcept
+    {
+#if JSON_DIAGNOSTICS
+        j.m_parent = this;
+#else
+        static_cast<void>(j);
+#endif
+    }
+
+    /// @brief set the parent of an element accessed via at(); never moves elements
+    reference set_parent_at(reference j) noexcept
+    {
+        set_parent_plain(j);
+        return j;
     }
 
     reference set_parent(reference j)
@@ -2557,7 +2610,6 @@ public:
             copy_leaf_value(other, *this);
         }
 
-        set_parents();
         assert_invariant();
     }
 
@@ -3445,7 +3497,7 @@ public:
     /// @sa https://json.nlohmann.me/api/basic_json/at/
     reference at(size_type idx)
     {
-        return set_parent(array_at(*this, idx));
+        return set_parent_at(array_at(*this, idx));
     }
 
     /// @brief access specified array element with bounds checking
@@ -3459,7 +3511,7 @@ public:
     /// @sa https://json.nlohmann.me/api/basic_json/at/
     reference at(const typename object_t::key_type& key)
     {
-        return set_parent(object_at(*this, key));
+        return set_parent_at(object_at(*this, key));
     }
 
     /// @brief access specified object element with bounds checking
@@ -3468,7 +3520,7 @@ public:
                  detail::is_usable_as_basic_json_key_type<basic_json_t, KeyType>::value, int> = 0>
     reference at(KeyType && key)
     {
-        return set_parent(object_at(*this, std::forward<KeyType>(key)));
+        return set_parent_at(object_at(*this, std::forward<KeyType>(key)));
     }
 
     /// @brief access specified object element with bounds checking
@@ -3566,8 +3618,9 @@ public:
         // operator[] only works for objects
         if (JSON_HEDLEY_LIKELY(is_object()))
         {
+            const auto old_capacity = object_capacity();
             auto result = m_data.m_value.object->emplace(std::move(key), nullptr);
-            return set_parent(result.first->second);
+            return set_parent_after_object_emplace(result.first->second, old_capacity);
         }
 
         throw_subscript_wrong_type("string");
@@ -3617,8 +3670,9 @@ public:
         // operator[] only works for objects
         if (JSON_HEDLEY_LIKELY(is_object()))
         {
+            const auto old_capacity = object_capacity();
             auto result = m_data.m_value.object->emplace(lookup_key(std::forward<KeyType>(key)), nullptr);
-            return set_parent(result.first->second);
+            return set_parent_after_object_emplace(result.first->second, old_capacity);
         }
 
         throw_subscript_wrong_type("string");
@@ -4585,8 +4639,9 @@ public:
         }
 
         // add the element to the object
+        const auto old_capacity = object_capacity();
         auto res = m_data.m_value.object->insert(val);
-        set_parent(res.first->second);
+        set_parent_after_object_emplace(res.first->second, old_capacity);
     }
 
     /// @brief add an object to an object
@@ -4662,8 +4717,9 @@ public:
         }
 
         // add the element to the array (perfect forwarding)
+        const auto old_capacity = object_capacity();
         auto res = m_data.m_value.object->emplace(std::forward<Args>(args)...);
-        set_parent(res.first->second);
+        set_parent_after_object_emplace(res.first->second, old_capacity);
 
         // create a result iterator and set iterator to the result of emplace
         auto it = begin();

single_include/nlohmann/json.hpp

@@ -30471,7 +30471,60 @@ public:
 #else
         static_cast<void>(old_capacity);
 #endif
-        return set_parent(j);
+        set_parent_plain(j);
+        return j;
+    }
+
+    /// @brief capacity of the stored object if it is vector-backed (ordered_map), else 0
+#if JSON_DIAGNOSTICS
+    template < typename O = object_t, detail::enable_if_t < detail::has_capacity<O>::value, int > = 0 >
+    std::size_t object_capacity() const noexcept
+    {
+        return m_data.m_value.object->capacity();
+    }
+
+    template < typename O = object_t, detail::enable_if_t < !detail::has_capacity<O>::value, int > = 0 >
+    std::size_t object_capacity() const noexcept
+    {
+        return 0;
+    }
+#else
+    static constexpr std::size_t object_capacity() noexcept
+    {
+        return 0;
+    }
+#endif
+
+    /// @brief set parent of an element that was just looked up or inserted into an object
+    reference set_parent_after_object_emplace(reference j, std::size_t old_capacity)
+    {
+#if JSON_DIAGNOSTICS
+        if (JSON_HEDLEY_UNLIKELY(object_capacity() != old_capacity))
+        {
+            set_parents();
+            return j;
+        }
+        j.m_parent = this;
+#else
+        static_cast<void>(old_capacity);
+#endif
+        return j;
+    }
+
+    void set_parent_plain(reference j) noexcept
+    {
+#if JSON_DIAGNOSTICS
+        j.m_parent = this;
+#else
+        static_cast<void>(j);
+#endif
+    }
+
+    /// @brief set the parent of an element accessed via at(); never moves elements
+    reference set_parent_at(reference j) noexcept
+    {
+        set_parent_plain(j);
+        return j;
     }
 
     reference set_parent(reference j)
@@ -31905,7 +31958,6 @@ public:
             copy_leaf_value(other, *this);
         }
 
-        set_parents();
         assert_invariant();
     }
 
@@ -32793,7 +32845,7 @@ public:
     /// @sa https://json.nlohmann.me/api/basic_json/at/
     reference at(size_type idx)
     {
-        return set_parent(array_at(*this, idx));
+        return set_parent_at(array_at(*this, idx));
     }
 
     /// @brief access specified array element with bounds checking
@@ -32807,7 +32859,7 @@ public:
     /// @sa https://json.nlohmann.me/api/basic_json/at/
     reference at(const typename object_t::key_type& key)
     {
-        return set_parent(object_at(*this, key));
+        return set_parent_at(object_at(*this, key));
     }
 
     /// @brief access specified object element with bounds checking
@@ -32816,7 +32868,7 @@ public:
                  detail::is_usable_as_basic_json_key_type<basic_json_t, KeyType>::value, int> = 0>
     reference at(KeyType && key)
     {
-        return set_parent(object_at(*this, std::forward<KeyType>(key)));
+        return set_parent_at(object_at(*this, std::forward<KeyType>(key)));
     }
 
     /// @brief access specified object element with bounds checking
@@ -32914,8 +32966,9 @@ public:
         // operator[] only works for objects
         if (JSON_HEDLEY_LIKELY(is_object()))
         {
+            const auto old_capacity = object_capacity();
             auto result = m_data.m_value.object->emplace(std::move(key), nullptr);
-            return set_parent(result.first->second);
+            return set_parent_after_object_emplace(result.first->second, old_capacity);
         }
 
         throw_subscript_wrong_type("string");
@@ -32965,8 +33018,9 @@ public:
         // operator[] only works for objects
         if (JSON_HEDLEY_LIKELY(is_object()))
         {
+            const auto old_capacity = object_capacity();
             auto result = m_data.m_value.object->emplace(lookup_key(std::forward<KeyType>(key)), nullptr);
-            return set_parent(result.first->second);
+            return set_parent_after_object_emplace(result.first->second, old_capacity);
         }
 
         throw_subscript_wrong_type("string");
@@ -33933,8 +33987,9 @@ public:
         }
 
         // add the element to the object
+        const auto old_capacity = object_capacity();
         auto res = m_data.m_value.object->insert(val);
-        set_parent(res.first->second);
+        set_parent_after_object_emplace(res.first->second, old_capacity);
     }
 
     /// @brief add an object to an object
@@ -34010,8 +34065,9 @@ public:
         }
 
         // add the element to the array (perfect forwarding)
+        const auto old_capacity = object_capacity();
         auto res = m_data.m_value.object->emplace(std::forward<Args>(args)...);
-        set_parent(res.first->second);
+        set_parent_after_object_emplace(res.first->second, old_capacity);
 
         // create a result iterator and set iterator to the result of emplace
         auto it = begin();

tests/src/unit-diagnostics.cpp

@@ -13,9 +13,11 @@
 #endif
 
 #define JSON_DIAGNOSTICS 1
+#define JSON_TESTS_PRIVATE
 
 #include <nlohmann/json.hpp>
 using nlohmann::json;
+using nlohmann::ordered_json;
 
 #include <map>
 #include <unordered_map>
@@ -631,3 +633,99 @@ TEST_CASE("Better diagnostics past the descent bound of update(), merge_patch()
         CHECK_THROWS_WITH_AS(p->at("y").at(0), expected_y.c_str(), json::type_error);
     }
 }
+
+namespace
+{
+// check that every child's parent pointer points to the containing value
+template<typename BasicJsonType>
+bool parents_consistent(const BasicJsonType& j)
+{
+    bool ok = true;
+    if (j.is_array() || j.is_object())
+    {
+        for (const auto& child : j)
+        {
+            ok = ok && child.m_parent == &j && parents_consistent(child);
+        }
+    }
+    return ok;
+}
+} // namespace
+
+TEST_CASE_TEMPLATE("Parent pointers stay consistent", J, json, ordered_json)
+{
+    SECTION("parse, copy, move, assign, swap")
+    {
+        J j = J::parse(R"({"a":[1,{"b":[2,3]},[4]],"c":{"d":{"e":[]}}})");
+        CHECK(parents_consistent(j));
+
+        J copy(j);
+        CHECK(parents_consistent(copy));
+
+        J moved(std::move(copy));
+        CHECK(parents_consistent(moved));
+
+        J assigned;
+        assigned = j;
+        CHECK(parents_consistent(assigned));
+
+        J other = {1, 2, {{"k", J::array({1, 2})}}};
+        other.swap(assigned);
+        CHECK(parents_consistent(other));
+        CHECK(parents_consistent(assigned));
+    }
+
+    SECTION("push_back growth")
+    {
+        J arr = J::array();
+        for (int i = 0; i < 500; ++i)
+        {
+            arr.push_back(J::array({i}));
+        }
+        CHECK(parents_consistent(arr));
+
+        J obj = J::object();
+        for (int i = 0; i < 500; ++i)
+        {
+            obj.push_back({std::to_string(i), J::array({i})});
+        }
+        CHECK(parents_consistent(obj));
+    }
+
+    SECTION("emplace_back and emplace growth")
+    {
+        J arr = J::array();
+        J obj = J::object();
+        for (int i = 0; i < 500; ++i)
+        {
+            arr.emplace_back(J::array({i}));
+            obj.emplace(std::to_string(i), J::array({i}));
+        }
+        CHECK(parents_consistent(arr));
+        CHECK(parents_consistent(obj));
+    }
+
+    SECTION("operator[] growth and at()")
+    {
+        J obj = J::object();
+        for (int i = 0; i < 500; ++i)
+        {
+            obj[std::to_string(i)] = J::array({i});
+            CHECK(obj[std::to_string(i / 2)].m_parent == &obj);
+        }
+        CHECK(parents_consistent(obj));
+
+        J arr = J::array();
+        for (int i = 0; i < 500; ++i)
+        {
+            arr[static_cast<size_t>(i)] = J::object({{"x", i}});
+        }
+        for (size_t i = 0; i < 500; ++i)
+        {
+            CHECK(arr.at(i).m_parent == &arr);
+        }
+        CHECK(obj.at("3").m_parent == &obj);
+        CHECK(parents_consistent(arr));
+        CHECK(parents_consistent(obj));
+    }
+}