Make flatten() linear for ordered_json

json_pointer::flatten inserted every leaf with operator[], which searches
ordered_map linearly, so flatten() was quadratic (citm_catalog.json: 265 ms
vs 5 ms for json). Flattened paths are unique by construction, so
ordered_map gets emplace_new_key() to append a key known to be absent;
other object types still use operator[]. Parent pointers are set once at
the end for JSON_DIAGNOSTICS.

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

include/nlohmann/detail/json_pointer.hpp

@@ -938,6 +938,23 @@ class json_pointer
     }
 
   private:
+    // Add the entry (key, v) to the object `obj`. Flattened paths are pairwise
+    // distinct, so objects that can append a key known to be absent
+    // (ordered_map) skip the lookup, which is linear and would make flatten
+    // quadratic; all other object types use operator[].
+    template<typename ObjectType, typename ValueType>
+    static auto add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, int /*unused*/)
+    -> decltype(obj.emplace_new_key(key, std::forward<ValueType>(v)), void())
+    {
+        obj.emplace_new_key(key, std::forward<ValueType>(v));
+    }
+
+    template<typename ObjectType, typename ValueType>
+    static void add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, ...)
+    {
+        obj[key] = std::forward<ValueType>(v);
+    }
+
     /*!
     @param[in] reference_string  the reference string to the current value
     @param[in] value             the value to consider
@@ -982,7 +999,8 @@ class json_pointer
 
         // flatten `v`, whose path is `path`: primitives and empty containers
         // are added to the result right away; other containers get a frame
-        const auto enter = [&stack, &path, &result](const BasicJsonType & v)
+        auto& object = *result.m_data.m_value.object;
+        const auto enter = [&stack, &path, &object](const BasicJsonType & v)
         {
             switch (v.type())
             {
@@ -991,7 +1009,7 @@ class json_pointer
                     if (v.m_data.m_value.array->empty())
                     {
                         // flatten empty array as null
-                        result[path] = nullptr;
+                        add_flattened(object, path, nullptr, 0);
                     }
                     else
                     {
@@ -1005,7 +1023,7 @@ class json_pointer
                     if (v.m_data.m_value.object->empty())
                     {
                         // flatten empty object as null
-                        result[path] = nullptr;
+                        add_flattened(object, path, nullptr, 0);
                     }
                     else
                     {
@@ -1025,7 +1043,7 @@ class json_pointer
                 default:
                 {
                     // add a primitive value with its reference string
-                    result[path] = v;
+                    add_flattened(object, path, v, 0);
                     return;
                 }
             }
@@ -1071,6 +1089,10 @@ class json_pointer
                 enter(it->second);
             }
         }
+
+        // the entries were added without going through basic_json, so the
+        // parent pointers (JSON_DIAGNOSTICS) have to be set now
+        result.set_parents();
     }
 
     /*!

include/nlohmann/json.hpp

@@ -1123,60 +1123,7 @@ public:
 #else
         static_cast<void>(old_capacity);
 #endif
-        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;
+        return set_parent(j);
     }
 
     reference set_parent(reference j)
@@ -2610,6 +2557,7 @@ public:
             copy_leaf_value(other, *this);
         }
 
+        set_parents();
         assert_invariant();
     }
 
@@ -3497,7 +3445,7 @@ public:
     /// @sa https://json.nlohmann.me/api/basic_json/at/
     reference at(size_type idx)
     {
-        return set_parent_at(array_at(*this, idx));
+        return set_parent(array_at(*this, idx));
     }
 
     /// @brief access specified array element with bounds checking
@@ -3511,7 +3459,7 @@ public:
     /// @sa https://json.nlohmann.me/api/basic_json/at/
     reference at(const typename object_t::key_type& key)
     {
-        return set_parent_at(object_at(*this, key));
+        return set_parent(object_at(*this, key));
     }
 
     /// @brief access specified object element with bounds checking
@@ -3520,7 +3468,7 @@ public:
                  detail::is_usable_as_basic_json_key_type<basic_json_t, KeyType>::value, int> = 0>
     reference at(KeyType && key)
     {
-        return set_parent_at(object_at(*this, std::forward<KeyType>(key)));
+        return set_parent(object_at(*this, std::forward<KeyType>(key)));
     }
 
     /// @brief access specified object element with bounds checking
@@ -3618,9 +3566,8 @@ 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_after_object_emplace(result.first->second, old_capacity);
+            return set_parent(result.first->second);
         }
 
         throw_subscript_wrong_type("string");
@@ -3670,9 +3617,8 @@ 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_after_object_emplace(result.first->second, old_capacity);
+            return set_parent(result.first->second);
         }
 
         throw_subscript_wrong_type("string");
@@ -4639,9 +4585,8 @@ public:
         }
 
         // add the element to the object
-        const auto old_capacity = object_capacity();
         auto res = m_data.m_value.object->insert(val);
-        set_parent_after_object_emplace(res.first->second, old_capacity);
+        set_parent(res.first->second);
     }
 
     /// @brief add an object to an object
@@ -4717,9 +4662,8 @@ 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_after_object_emplace(res.first->second, old_capacity);
+        set_parent(res.first->second);
 
         // create a result iterator and set iterator to the result of emplace
         auto it = begin();

include/nlohmann/ordered_map.hpp

@@ -143,6 +143,17 @@ public:
         return {std::prev(this->end()), true};
     }
 
+    /// @brief add an element at the end without checking whether the key exists
+    /// @note The caller must guarantee that @a key is not yet contained, otherwise
+    ///       the container holds duplicate keys. This avoids the linear search of
+    ///       emplace() and operator[] when many keys known to be new are added.
+    template<class V, detail::enable_if_t<
+                 detail::is_constructible<T, V>::value, int> = 0>
+    void emplace_new_key(const key_type& key, V && t)
+    {
+        append(key, std::forward<V>(t));
+    }
+
     T& operator[](const key_type& key)
     {
         return emplace(key, T{}).first->second;

single_include/nlohmann/json.hpp

@@ -21559,6 +21559,23 @@ class json_pointer
     }
 
   private:
+    // Add the entry (key, v) to the object `obj`. Flattened paths are pairwise
+    // distinct, so objects that can append a key known to be absent
+    // (ordered_map) skip the lookup, which is linear and would make flatten
+    // quadratic; all other object types use operator[].
+    template<typename ObjectType, typename ValueType>
+    static auto add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, int /*unused*/)
+    -> decltype(obj.emplace_new_key(key, std::forward<ValueType>(v)), void())
+    {
+        obj.emplace_new_key(key, std::forward<ValueType>(v));
+    }
+
+    template<typename ObjectType, typename ValueType>
+    static void add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, ...)
+    {
+        obj[key] = std::forward<ValueType>(v);
+    }
+
     /*!
     @param[in] reference_string  the reference string to the current value
     @param[in] value             the value to consider
@@ -21603,7 +21620,8 @@ class json_pointer
 
         // flatten `v`, whose path is `path`: primitives and empty containers
         // are added to the result right away; other containers get a frame
-        const auto enter = [&stack, &path, &result](const BasicJsonType & v)
+        auto& object = *result.m_data.m_value.object;
+        const auto enter = [&stack, &path, &object](const BasicJsonType & v)
         {
             switch (v.type())
             {
@@ -21612,7 +21630,7 @@ class json_pointer
                     if (v.m_data.m_value.array->empty())
                     {
                         // flatten empty array as null
-                        result[path] = nullptr;
+                        add_flattened(object, path, nullptr, 0);
                     }
                     else
                     {
@@ -21626,7 +21644,7 @@ class json_pointer
                     if (v.m_data.m_value.object->empty())
                     {
                         // flatten empty object as null
-                        result[path] = nullptr;
+                        add_flattened(object, path, nullptr, 0);
                     }
                     else
                     {
@@ -21646,7 +21664,7 @@ class json_pointer
                 default:
                 {
                     // add a primitive value with its reference string
-                    result[path] = v;
+                    add_flattened(object, path, v, 0);
                     return;
                 }
             }
@@ -21692,6 +21710,10 @@ class json_pointer
                 enter(it->second);
             }
         }
+
+        // the entries were added without going through basic_json, so the
+        // parent pointers (JSON_DIAGNOSTICS) have to be set now
+        result.set_parents();
     }
 
     /*!
@@ -29158,6 +29180,17 @@ public:
         return {std::prev(this->end()), true};
     }
 
+    /// @brief add an element at the end without checking whether the key exists
+    /// @note The caller must guarantee that @a key is not yet contained, otherwise
+    ///       the container holds duplicate keys. This avoids the linear search of
+    ///       emplace() and operator[] when many keys known to be new are added.
+    template<class V, detail::enable_if_t<
+                 detail::is_constructible<T, V>::value, int> = 0>
+    void emplace_new_key(const key_type& key, V && t)
+    {
+        append(key, std::forward<V>(t));
+    }
+
     T& operator[](const key_type& key)
     {
         return emplace(key, T{}).first->second;
@@ -30471,60 +30504,7 @@ public:
 #else
         static_cast<void>(old_capacity);
 #endif
-        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;
+        return set_parent(j);
     }
 
     reference set_parent(reference j)
@@ -31958,6 +31938,7 @@ public:
             copy_leaf_value(other, *this);
         }
 
+        set_parents();
         assert_invariant();
     }
 
@@ -32845,7 +32826,7 @@ public:
     /// @sa https://json.nlohmann.me/api/basic_json/at/
     reference at(size_type idx)
     {
-        return set_parent_at(array_at(*this, idx));
+        return set_parent(array_at(*this, idx));
     }
 
     /// @brief access specified array element with bounds checking
@@ -32859,7 +32840,7 @@ public:
     /// @sa https://json.nlohmann.me/api/basic_json/at/
     reference at(const typename object_t::key_type& key)
     {
-        return set_parent_at(object_at(*this, key));
+        return set_parent(object_at(*this, key));
     }
 
     /// @brief access specified object element with bounds checking
@@ -32868,7 +32849,7 @@ public:
                  detail::is_usable_as_basic_json_key_type<basic_json_t, KeyType>::value, int> = 0>
     reference at(KeyType && key)
     {
-        return set_parent_at(object_at(*this, std::forward<KeyType>(key)));
+        return set_parent(object_at(*this, std::forward<KeyType>(key)));
     }
 
     /// @brief access specified object element with bounds checking
@@ -32966,9 +32947,8 @@ 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_after_object_emplace(result.first->second, old_capacity);
+            return set_parent(result.first->second);
         }
 
         throw_subscript_wrong_type("string");
@@ -33018,9 +32998,8 @@ 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_after_object_emplace(result.first->second, old_capacity);
+            return set_parent(result.first->second);
         }
 
         throw_subscript_wrong_type("string");
@@ -33987,9 +33966,8 @@ public:
         }
 
         // add the element to the object
-        const auto old_capacity = object_capacity();
         auto res = m_data.m_value.object->insert(val);
-        set_parent_after_object_emplace(res.first->second, old_capacity);
+        set_parent(res.first->second);
     }
 
     /// @brief add an object to an object
@@ -34065,9 +34043,8 @@ 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_after_object_emplace(res.first->second, old_capacity);
+        set_parent(res.first->second);
 
         // create a result iterator and set iterator to the result of emplace
         auto it = begin();

tests/src/unit-diagnostics.cpp

@@ -13,11 +13,9 @@
 #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>
@@ -633,99 +631,3 @@ 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));
-    }
-}

tests/src/unit-json_pointer.cpp

@@ -24,6 +24,8 @@ using nlohmann::json;
 #endif
 
 #include <map>
+#include <string>
+#include <vector>
 #include <sstream>
 
 TEST_CASE("JSON pointers")
@@ -1071,3 +1073,53 @@ TEST_CASE("flatten of structured values")
               R"({"/z":"s","/a~1b/~0":1,"/a~1b/k":null,"/a/0":1,"/a/1/c":null,"/a/1/b":null,"/a/2/0/x~0~1/0":true,"/a/2/0/x~0~1/1":null,"/a/2/0/w":2})");
     }
 }
+
+TEST_CASE("flatten of ordered_json")
+{
+    using nlohmann::ordered_json;
+
+    SECTION("keeps the document order of the leaves")
+    {
+        const ordered_json j = ordered_json::parse(R"({
+            "z": 1, "a": {"y": [true, null, {}], "b": "x", "": []},
+            "m~n": 2.5, "o/p": {"k": {}}, "0": [[1], [2, 3]]
+        })");
+
+        const ordered_json flat = j.flatten();
+        std::vector<std::string> keys;
+        for (const auto& el : flat.items())
+        {
+            keys.push_back(el.key());
+        }
+        const std::vector<std::string> expected =
+        {
+            "/z", "/a/y/0", "/a/y/1", "/a/y/2", "/a/b", "/a/", "/m~0n", "/o~1p/k", "/0/0/0", "/0/1/0", "/0/1/1"
+        };
+        CHECK(keys == expected);
+        CHECK(flat.size() == expected.size());
+        CHECK(flat["/m~0n"] == 2.5);
+        CHECK(flat["/a/y/2"].is_null());
+    }
+
+    SECTION("round-trips and agrees with json")
+    {
+        ordered_json j;
+        for (int i = 0; i < 200; ++i)
+        {
+            j["k" + std::to_string(i)] = {{"v", i}, {"l", {i, i + 1, "s"}}};
+        }
+        const ordered_json flat = j.flatten();
+        CHECK(flat.size() == 800);
+        CHECK(flat.unflatten() == j);
+
+        // same entries as for a sorted object
+        const nlohmann::json plain = nlohmann::json::parse(j.dump());
+        CHECK(nlohmann::json::parse(flat.dump()) == plain.flatten());
+    }
+
+    SECTION("primitive and empty root")
+    {
+        CHECK(ordered_json(1).flatten() == ordered_json({{"", 1}}));
+        CHECK(ordered_json::array().flatten() == ordered_json({{"", nullptr}}));
+    }
+}