Unflatten in time and memory linear in the pointer depth

#5443 made unflatten() decide between arrays and objects independently
of the iteration order by collecting the pointer prefixes that have a
reference token 0 below them in a std::set<std::vector<string_t>>.
Every such prefix was stored as a copy of all its reference tokens, and
get_and_create() compared whole prefix vectors at every step, so
unflattening a pointer of depth d took time and memory quadratic in d:
a 10,000-level array pointer took 18 s and 1.3 GB, a 100,000-level one
did not finish.

The prefixes are now numbered nodes of a tree, so each is stored once
and get_and_create() follows the tree token by token. The result is
unchanged, including its independence of the iteration order.

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

include/nlohmann/detail/json_pointer.hpp

@@ -16,8 +16,8 @@
     #include <iosfwd> // ostream
 #endif  // JSON_NO_IO
 #include <limits> // max
+#include <map> // map
 #include <numeric> // accumulate
-#include <set> // set
 #include <string> // string
 #include <utility> // move
 #include <vector> // vector
@@ -359,33 +359,45 @@ class json_pointer
 
   private:
     /*!
-    @brief the reference token sequences that denote arrays
+    @brief the pointer prefixes of a flattened object, and which of them denote arrays
 
     @ref unflatten collects the pointer prefixes that have a reference token 0
     among their children; @ref get_and_create creates arrays exactly below
     those prefixes and objects everywhere else. Deciding this up front keeps
     the result independent of the order in which the flattened object is
     iterated, which is unspecified for some object types.
+
+    The prefixes form a tree and are numbered, so each of them is stored only
+    once (as a node) rather than as a copy of all of its reference tokens.
     */
-    using array_parents_t = std::set<std::vector<string_t>>;
+    struct prefix_tree
+    {
+        // children[id] maps a reference token to the number of the prefix
+        // extended by that token; number 0 is the empty prefix
+        std::vector<std::map<string_t, std::size_t>> children;
+        // is_array[id] is true iff some flattened key has the reference token
+        // 0 directly below the prefix with number id
+        std::vector<bool> is_array;
+    };
 
     /*!
     @brief create and return a reference to the pointed to value
 
-    Complexity: Linear in the number of reference tokens.
+    Complexity: Linear in the number of reference tokens (times the logarithm
+    of the number of siblings for the prefix lookup).
 
     @throw parse_error.106 if an array index begins with '0'
     @throw parse_error.109 if array index is not a number
     @throw type_error.313 if value cannot be unflattened
     */
     template<typename BasicJsonType>
-    BasicJsonType& get_and_create(BasicJsonType& j, const array_parents_t& array_parents) const
+    BasicJsonType& get_and_create(BasicJsonType& j, const prefix_tree& tree) const
     {
         auto* result = &j;
 
-        // the reference tokens that have been consumed so far; used to look up
-        // whether the value to be created below is an array or an object
-        std::vector<string_t> prefix;
+        // the number of the prefix consumed so far; used to look up whether
+        // the value to be created below is an array or an object
+        std::size_t id = 0;
 
         // in case no reference tokens exist, return a reference to the JSON value
         // j which will be overwritten by a primitive value
@@ -395,7 +407,7 @@ class json_pointer
             {
                 case detail::value_t::null:
                 {
-                    if (array_parents.find(prefix) != array_parents.end())
+                    if (tree.is_array[id])
                     {
                         // some reference token below this position is 0, so the
                         // value is an array
@@ -440,7 +452,9 @@ class json_pointer
                     JSON_THROW(detail::type_error::create(313, "invalid value to unflatten", &j));
             }
 
-            prefix.push_back(reference_token);
+            const auto it = tree.children[id].find(reference_token);
+            JSON_ASSERT(it != tree.children[id].end());
+            id = it->second;
         }
 
         return *result;
@@ -878,64 +892,127 @@ class json_pointer
     @param[in,out] result        the result object to insert values to
 
     @note Empty objects or arrays are flattened to `null`.
+
+    The value is walked with an explicit stack rather than the call stack, so
+    arbitrarily deeply nested values can be flattened.
+
+    @sa https://github.com/nlohmann/json/issues/5393
     */
     template<typename BasicJsonType>
     static void flatten(const string_t& reference_string,
                         const BasicJsonType& value,
                         BasicJsonType& result)
     {
-        switch (value.type())
+        using object_const_iterator = typename BasicJsonType::object_t::const_iterator;
+
+        // an array or object being walked: the container, the array index or
+        // object iterator of the next child, and the length of the path of the
+        // container itself
+        struct frame
         {
-            case detail::value_t::array:
-            {
-                if (value.m_data.m_value.array->empty())
-                {
-                    // flatten empty array as null
-                    result[reference_string] = nullptr;
-                }
-                else
-                {
-                    // iterate array and use index as a reference string
-                    for (std::size_t i = 0; i < value.m_data.m_value.array->size(); ++i)
-                    {
-                        flatten(detail::concat<string_t>(reference_string, '/', std::to_string(i)),
-                                value.m_data.m_value.array->operator[](i), result);
-                    }
-                }
-                break;
-            }
+            const BasicJsonType* container;
+            std::size_t index;
+            object_const_iterator member;
+            std::size_t path_length;
+        };
 
-            case detail::value_t::object:
-            {
-                if (value.m_data.m_value.object->empty())
-                {
-                    // flatten empty object as null
-                    result[reference_string] = nullptr;
-                }
-                else
-                {
-                    // iterate object and use keys as reference string
-                    for (const auto& element : *value.m_data.m_value.object)
-                    {
-                        flatten(detail::concat<string_t>(reference_string, '/', detail::escape(element.first)), element.second, result);
-                    }
-                }
-                break;
-            }
+        // The containers being flattened are kept on an explicit stack, and
+        // every child is flattened completely before the next one, so the
+        // entries come out in the same order as with a recursive walk. The
+        // path of the value being flattened is kept in one buffer that grows
+        // and shrinks with the stack, rather than in a new string per level.
+        std::vector<frame> stack;
+        string_t path = reference_string;
 
-            case detail::value_t::null:
-            case detail::value_t::string:
-            case detail::value_t::boolean:
-            case detail::value_t::number_integer:
-            case detail::value_t::number_unsigned:
-            case detail::value_t::number_float:
-            case detail::value_t::binary:
-            case detail::value_t::discarded:
-            default:
+        // 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)
+        {
+            switch (v.type())
             {
-                // add a primitive value with its reference string
-                result[reference_string] = value;
-                break;
+                case detail::value_t::array:
+                {
+                    if (v.m_data.m_value.array->empty())
+                    {
+                        // flatten empty array as null
+                        result[path] = nullptr;
+                    }
+                    else
+                    {
+                        stack.push_back({&v, 0, object_const_iterator(), path.size()});
+                    }
+                    return;
+                }
+
+                case detail::value_t::object:
+                {
+                    if (v.m_data.m_value.object->empty())
+                    {
+                        // flatten empty object as null
+                        result[path] = nullptr;
+                    }
+                    else
+                    {
+                        stack.push_back({&v, 0, v.m_data.m_value.object->begin(), path.size()});
+                    }
+                    return;
+                }
+
+                case detail::value_t::null:
+                case detail::value_t::string:
+                case detail::value_t::boolean:
+                case detail::value_t::number_integer:
+                case detail::value_t::number_unsigned:
+                case detail::value_t::number_float:
+                case detail::value_t::binary:
+                case detail::value_t::discarded:
+                default:
+                {
+                    // add a primitive value with its reference string
+                    result[path] = v;
+                    return;
+                }
+            }
+        };
+
+        enter(value);
+        while (!stack.empty())
+        {
+            // the frame is changed through stack.back(): enter() may push a
+            // frame, which would invalidate a reference to it
+            const BasicJsonType* const container = stack.back().container;
+
+            // drop the path of the previous child
+            path.resize(stack.back().path_length);
+
+            if (container->is_array())
+            {
+                const auto& array = *container->m_data.m_value.array;
+                const std::size_t i = stack.back().index;
+                if (i == array.size())
+                {
+                    stack.pop_back();
+                    continue;
+                }
+
+                // iterate array and use index as a reference string
+                ++stack.back().index;
+                detail::concat_into(path, '/', detail::to_string<string_t>(i));
+                enter(array[i]);
+            }
+            else
+            {
+                const object_const_iterator it = stack.back().member;
+                if (it == container->m_data.m_value.object->end())
+                {
+                    stack.pop_back();
+                    continue;
+                }
+
+                // iterate object and use keys as reference string
+                ++stack.back().member;
+                detail::concat_into(path, '/', detail::escape(it->first));
+                enter(it->second);
             }
         }
     }
@@ -963,19 +1040,31 @@ class json_pointer
 
         // collect the pointer prefixes that have a reference token 0 among
         // their children; the values below them are arrays, all others are
-        // objects (see array_parents_t)
-        array_parents_t array_parents;
+        // objects (see prefix_tree)
+        prefix_tree tree;
+        tree.children.emplace_back();
+        tree.is_array.push_back(false);
         for (const auto& element : *value.m_data.m_value.object)
         {
             json_pointer ptr(element.first);
-            std::vector<string_t> prefix;
+            std::size_t id = 0;
             for (auto& reference_token : ptr.reference_tokens)
             {
                 if (reference_token == "0")
                 {
-                    array_parents.insert(prefix);
+                    tree.is_array[id] = true;
+                }
+
+                // do not keep a reference into tree.children across the
+                // push_back below, as it may reallocate
+                const std::size_t next = tree.children.size();
+                const auto inserted = tree.children[id].emplace(std::move(reference_token), next);
+                id = inserted.first->second;
+                if (inserted.second)
+                {
+                    tree.children.emplace_back();
+                    tree.is_array.push_back(false);
                 }
-                prefix.push_back(std::move(reference_token));
             }
         }
 
@@ -991,7 +1080,7 @@ class json_pointer
             // that if the JSON pointer is "" (i.e., points to the whole value),
             // function get_and_create returns a reference to the result itself.
             // An assignment will then create a primitive value.
-            json_pointer(element.first).get_and_create(result, array_parents) = element.second;
+            json_pointer(element.first).get_and_create(result, tree) = element.second;
         }
 
         return result;

include/nlohmann/detail/output/binary_writer.hpp

@@ -85,12 +85,6 @@ template<typename BasicJsonType, typename CharType, typename OutputSinkType = ou
 class binary_writer
 {
     using string_t = typename BasicJsonType::string_t;
-
-    /// an object key as string_t: a reference when object_t::key_type already is
-    /// string_t, otherwise a converted copy that outlives sanitize_utf8_for_write's result
-    using object_key_string_t = typename std::conditional <
-                                std::is_same<typename BasicJsonType::object_t::key_type, string_t>::value,
-                                const string_t&, string_t >::type;
     using binary_t = typename BasicJsonType::binary_t;
     using number_float_t = typename BasicJsonType::number_float_t;
 
@@ -825,10 +819,8 @@ class binary_writer
 
                 for (const auto& el : *j.m_data.m_value.object)
                 {
-                    // a converted key must outlive the reference returned by sanitize_utf8_for_write
-                    const object_key_string_t key_string = el.first;
                     string_t storage;
-                    const string_t& key = sanitize_utf8_for_write(key_string, j, storage);
+                    const string_t& key = sanitize_utf8_for_write(el.first, j, storage);
                     write_number_with_ubjson_prefix(key.size(), true, use_bjdata);
                     oa.write_characters(
                           reinterpret_cast<const CharType*>(key.data()),
@@ -1374,10 +1366,8 @@ class binary_writer
                     continue;
                 }
 
-                // a converted key must outlive the reference returned by sanitize_utf8_for_write
-                const object_key_string_t key_string = current.object_it->first;
                 string_t storage;
-                const string_t& key = sanitize_utf8_for_write(key_string, j, storage);
+                const string_t& key = sanitize_utf8_for_write(current.object_it->first, j, storage);
                 write_number_with_ubjson_prefix(key.size(), true, use_bjdata);
                 oa.write_characters(
                       reinterpret_cast<const CharType*>(key.data()),
@@ -2740,11 +2730,6 @@ class binary_writer
     itself in every case but a sanitized `replace`/`ignore` one, so @a
     storage must outlive the returned reference only then.
 
-    @a s must be an lvalue that outlives the returned reference. An object key
-    whose `key_type` is not @ref string_t must therefore first be converted
-    into a named string_t (see @ref object_key_string_t); the deleted overload
-    below enforces this at compile time.
-
     @param[in] s        the string (value or object key) to write
     @param[in] context  the value @a s belongs to (for diagnostics)
     @param[out] storage  backing storage for a sanitized copy
@@ -2774,10 +2759,6 @@ class binary_writer
         }
     }
 
-    /// deleted: anything but a string_t would bind a temporary that dies before the returned reference is used
-    template < typename T, enable_if_t < !std::is_same<T, string_t>::value, int > = 0 >
-    const string_t& sanitize_utf8_for_write(const T& /*s*/, const BasicJsonType& /*context*/, string_t& /*storage*/) const = delete;
-
     /*!
     @brief write an integer in the shortest encoding
 

single_include/nlohmann/json.hpp

@@ -19928,8 +19928,8 @@ NLOHMANN_JSON_NAMESPACE_END
     #include <iosfwd> // ostream
 #endif  // JSON_NO_IO
 #include <limits> // max
+#include <map> // map
 #include <numeric> // accumulate
-#include <set> // set
 #include <string> // string
 #include <utility> // move
 #include <vector> // vector
@@ -20277,33 +20277,45 @@ class json_pointer
 
   private:
     /*!
-    @brief the reference token sequences that denote arrays
+    @brief the pointer prefixes of a flattened object, and which of them denote arrays
 
     @ref unflatten collects the pointer prefixes that have a reference token 0
     among their children; @ref get_and_create creates arrays exactly below
     those prefixes and objects everywhere else. Deciding this up front keeps
     the result independent of the order in which the flattened object is
     iterated, which is unspecified for some object types.
+
+    The prefixes form a tree and are numbered, so each of them is stored only
+    once (as a node) rather than as a copy of all of its reference tokens.
     */
-    using array_parents_t = std::set<std::vector<string_t>>;
+    struct prefix_tree
+    {
+        // children[id] maps a reference token to the number of the prefix
+        // extended by that token; number 0 is the empty prefix
+        std::vector<std::map<string_t, std::size_t>> children;
+        // is_array[id] is true iff some flattened key has the reference token
+        // 0 directly below the prefix with number id
+        std::vector<bool> is_array;
+    };
 
     /*!
     @brief create and return a reference to the pointed to value
 
-    Complexity: Linear in the number of reference tokens.
+    Complexity: Linear in the number of reference tokens (times the logarithm
+    of the number of siblings for the prefix lookup).
 
     @throw parse_error.106 if an array index begins with '0'
     @throw parse_error.109 if array index is not a number
     @throw type_error.313 if value cannot be unflattened
     */
     template<typename BasicJsonType>
-    BasicJsonType& get_and_create(BasicJsonType& j, const array_parents_t& array_parents) const
+    BasicJsonType& get_and_create(BasicJsonType& j, const prefix_tree& tree) const
     {
         auto* result = &j;
 
-        // the reference tokens that have been consumed so far; used to look up
-        // whether the value to be created below is an array or an object
-        std::vector<string_t> prefix;
+        // the number of the prefix consumed so far; used to look up whether
+        // the value to be created below is an array or an object
+        std::size_t id = 0;
 
         // in case no reference tokens exist, return a reference to the JSON value
         // j which will be overwritten by a primitive value
@@ -20313,7 +20325,7 @@ class json_pointer
             {
                 case detail::value_t::null:
                 {
-                    if (array_parents.find(prefix) != array_parents.end())
+                    if (tree.is_array[id])
                     {
                         // some reference token below this position is 0, so the
                         // value is an array
@@ -20358,7 +20370,9 @@ class json_pointer
                     JSON_THROW(detail::type_error::create(313, "invalid value to unflatten", &j));
             }
 
-            prefix.push_back(reference_token);
+            const auto it = tree.children[id].find(reference_token);
+            JSON_ASSERT(it != tree.children[id].end());
+            id = it->second;
         }
 
         return *result;
@@ -20796,64 +20810,127 @@ class json_pointer
     @param[in,out] result        the result object to insert values to
 
     @note Empty objects or arrays are flattened to `null`.
+
+    The value is walked with an explicit stack rather than the call stack, so
+    arbitrarily deeply nested values can be flattened.
+
+    @sa https://github.com/nlohmann/json/issues/5393
     */
     template<typename BasicJsonType>
     static void flatten(const string_t& reference_string,
                         const BasicJsonType& value,
                         BasicJsonType& result)
     {
-        switch (value.type())
+        using object_const_iterator = typename BasicJsonType::object_t::const_iterator;
+
+        // an array or object being walked: the container, the array index or
+        // object iterator of the next child, and the length of the path of the
+        // container itself
+        struct frame
         {
-            case detail::value_t::array:
-            {
-                if (value.m_data.m_value.array->empty())
-                {
-                    // flatten empty array as null
-                    result[reference_string] = nullptr;
-                }
-                else
-                {
-                    // iterate array and use index as a reference string
-                    for (std::size_t i = 0; i < value.m_data.m_value.array->size(); ++i)
-                    {
-                        flatten(detail::concat<string_t>(reference_string, '/', std::to_string(i)),
-                                value.m_data.m_value.array->operator[](i), result);
-                    }
-                }
-                break;
-            }
+            const BasicJsonType* container;
+            std::size_t index;
+            object_const_iterator member;
+            std::size_t path_length;
+        };
 
-            case detail::value_t::object:
-            {
-                if (value.m_data.m_value.object->empty())
-                {
-                    // flatten empty object as null
-                    result[reference_string] = nullptr;
-                }
-                else
-                {
-                    // iterate object and use keys as reference string
-                    for (const auto& element : *value.m_data.m_value.object)
-                    {
-                        flatten(detail::concat<string_t>(reference_string, '/', detail::escape(element.first)), element.second, result);
-                    }
-                }
-                break;
-            }
+        // The containers being flattened are kept on an explicit stack, and
+        // every child is flattened completely before the next one, so the
+        // entries come out in the same order as with a recursive walk. The
+        // path of the value being flattened is kept in one buffer that grows
+        // and shrinks with the stack, rather than in a new string per level.
+        std::vector<frame> stack;
+        string_t path = reference_string;
 
-            case detail::value_t::null:
-            case detail::value_t::string:
-            case detail::value_t::boolean:
-            case detail::value_t::number_integer:
-            case detail::value_t::number_unsigned:
-            case detail::value_t::number_float:
-            case detail::value_t::binary:
-            case detail::value_t::discarded:
-            default:
+        // 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)
+        {
+            switch (v.type())
             {
-                // add a primitive value with its reference string
-                result[reference_string] = value;
-                break;
+                case detail::value_t::array:
+                {
+                    if (v.m_data.m_value.array->empty())
+                    {
+                        // flatten empty array as null
+                        result[path] = nullptr;
+                    }
+                    else
+                    {
+                        stack.push_back({&v, 0, object_const_iterator(), path.size()});
+                    }
+                    return;
+                }
+
+                case detail::value_t::object:
+                {
+                    if (v.m_data.m_value.object->empty())
+                    {
+                        // flatten empty object as null
+                        result[path] = nullptr;
+                    }
+                    else
+                    {
+                        stack.push_back({&v, 0, v.m_data.m_value.object->begin(), path.size()});
+                    }
+                    return;
+                }
+
+                case detail::value_t::null:
+                case detail::value_t::string:
+                case detail::value_t::boolean:
+                case detail::value_t::number_integer:
+                case detail::value_t::number_unsigned:
+                case detail::value_t::number_float:
+                case detail::value_t::binary:
+                case detail::value_t::discarded:
+                default:
+                {
+                    // add a primitive value with its reference string
+                    result[path] = v;
+                    return;
+                }
+            }
+        };
+
+        enter(value);
+        while (!stack.empty())
+        {
+            // the frame is changed through stack.back(): enter() may push a
+            // frame, which would invalidate a reference to it
+            const BasicJsonType* const container = stack.back().container;
+
+            // drop the path of the previous child
+            path.resize(stack.back().path_length);
+
+            if (container->is_array())
+            {
+                const auto& array = *container->m_data.m_value.array;
+                const std::size_t i = stack.back().index;
+                if (i == array.size())
+                {
+                    stack.pop_back();
+                    continue;
+                }
+
+                // iterate array and use index as a reference string
+                ++stack.back().index;
+                detail::concat_into(path, '/', detail::to_string<string_t>(i));
+                enter(array[i]);
+            }
+            else
+            {
+                const object_const_iterator it = stack.back().member;
+                if (it == container->m_data.m_value.object->end())
+                {
+                    stack.pop_back();
+                    continue;
+                }
+
+                // iterate object and use keys as reference string
+                ++stack.back().member;
+                detail::concat_into(path, '/', detail::escape(it->first));
+                enter(it->second);
             }
         }
     }
@@ -20881,19 +20958,31 @@ class json_pointer
 
         // collect the pointer prefixes that have a reference token 0 among
         // their children; the values below them are arrays, all others are
-        // objects (see array_parents_t)
-        array_parents_t array_parents;
+        // objects (see prefix_tree)
+        prefix_tree tree;
+        tree.children.emplace_back();
+        tree.is_array.push_back(false);
         for (const auto& element : *value.m_data.m_value.object)
         {
             json_pointer ptr(element.first);
-            std::vector<string_t> prefix;
+            std::size_t id = 0;
             for (auto& reference_token : ptr.reference_tokens)
             {
                 if (reference_token == "0")
                 {
-                    array_parents.insert(prefix);
+                    tree.is_array[id] = true;
+                }
+
+                // do not keep a reference into tree.children across the
+                // push_back below, as it may reallocate
+                const std::size_t next = tree.children.size();
+                const auto inserted = tree.children[id].emplace(std::move(reference_token), next);
+                id = inserted.first->second;
+                if (inserted.second)
+                {
+                    tree.children.emplace_back();
+                    tree.is_array.push_back(false);
                 }
-                prefix.push_back(std::move(reference_token));
             }
         }
 
@@ -20909,7 +20998,7 @@ class json_pointer
             // that if the JSON pointer is "" (i.e., points to the whole value),
             // function get_and_create returns a reference to the result itself.
             // An assignment will then create a primitive value.
-            json_pointer(element.first).get_and_create(result, array_parents) = element.second;
+            json_pointer(element.first).get_and_create(result, tree) = element.second;
         }
 
         return result;
@@ -21590,12 +21679,6 @@ template<typename BasicJsonType, typename CharType, typename OutputSinkType = ou
 class binary_writer
 {
     using string_t = typename BasicJsonType::string_t;
-
-    /// an object key as string_t: a reference when object_t::key_type already is
-    /// string_t, otherwise a converted copy that outlives sanitize_utf8_for_write's result
-    using object_key_string_t = typename std::conditional <
-                                std::is_same<typename BasicJsonType::object_t::key_type, string_t>::value,
-                                const string_t&, string_t >::type;
     using binary_t = typename BasicJsonType::binary_t;
     using number_float_t = typename BasicJsonType::number_float_t;
 
@@ -22330,10 +22413,8 @@ class binary_writer
 
                 for (const auto& el : *j.m_data.m_value.object)
                 {
-                    // a converted key must outlive the reference returned by sanitize_utf8_for_write
-                    const object_key_string_t key_string = el.first;
                     string_t storage;
-                    const string_t& key = sanitize_utf8_for_write(key_string, j, storage);
+                    const string_t& key = sanitize_utf8_for_write(el.first, j, storage);
                     write_number_with_ubjson_prefix(key.size(), true, use_bjdata);
                     oa.write_characters(
                           reinterpret_cast<const CharType*>(key.data()),
@@ -22879,10 +22960,8 @@ class binary_writer
                     continue;
                 }
 
-                // a converted key must outlive the reference returned by sanitize_utf8_for_write
-                const object_key_string_t key_string = current.object_it->first;
                 string_t storage;
-                const string_t& key = sanitize_utf8_for_write(key_string, j, storage);
+                const string_t& key = sanitize_utf8_for_write(current.object_it->first, j, storage);
                 write_number_with_ubjson_prefix(key.size(), true, use_bjdata);
                 oa.write_characters(
                       reinterpret_cast<const CharType*>(key.data()),
@@ -24245,11 +24324,6 @@ class binary_writer
     itself in every case but a sanitized `replace`/`ignore` one, so @a
     storage must outlive the returned reference only then.
 
-    @a s must be an lvalue that outlives the returned reference. An object key
-    whose `key_type` is not @ref string_t must therefore first be converted
-    into a named string_t (see @ref object_key_string_t); the deleted overload
-    below enforces this at compile time.
-
     @param[in] s        the string (value or object key) to write
     @param[in] context  the value @a s belongs to (for diagnostics)
     @param[out] storage  backing storage for a sanitized copy
@@ -24279,10 +24353,6 @@ class binary_writer
         }
     }
 
-    /// deleted: anything but a string_t would bind a temporary that dies before the returned reference is used
-    template < typename T, enable_if_t < !std::is_same<T, string_t>::value, int > = 0 >
-    const string_t& sanitize_utf8_for_write(const T& /*s*/, const BasicJsonType& /*context*/, string_t& /*storage*/) const = delete;
-
     /*!
     @brief write an integer in the shortest encoding
 

tests/src/unit-binary_utf8_error_handler.cpp

@@ -12,10 +12,7 @@
 #include <nlohmann/json.hpp>
 using nlohmann::json;
 
-#include <map>
-#include <memory>
 #include <string>
-#include <utility>
 #include <vector>
 
 namespace
@@ -58,49 +55,6 @@ std::string dump_and_parse(const std::string& raw, eh error_handler)
     return json::parse(json(raw).dump(-1, ' ', false, error_handler)).get<std::string>();
 }
 
-// an object key type that is not string_t, but converts implicitly to it
-class converting_key
-{
-  public:
-    converting_key(const char* s) : m_value(s) {} // NOLINT(google-explicit-constructor,hicpp-explicit-conversions)
-    converting_key(std::string s) : m_value(std::move(s)) {} // NOLINT(google-explicit-constructor,hicpp-explicit-conversions)
-
-    // the conversion yields a temporary string_t
-    operator std::string() const // NOLINT(google-explicit-constructor,hicpp-explicit-conversions)
-    {
-        return m_value;
-    }
-
-    // read by the exception messages when JSON_DIAGNOSTICS is enabled
-    const char* data() const noexcept
-    {
-        return m_value.data();
-    }
-
-    friend bool operator<(const converting_key& lhs, const converting_key& rhs)
-    {
-        return lhs.m_value < rhs.m_value;
-    }
-
-  private:
-    std::string m_value;
-};
-
-// ObjectType using converting_key; the Key template argument is ignored
-template<typename Key, typename Value, typename Compare, typename Allocator>
-class converting_key_object : public std::map<converting_key, Value, std::less<converting_key>, // NOLINT(modernize-use-transparent-functors)
-    typename std::allocator_traits<Allocator>::template rebind_alloc<std::pair<const converting_key, Value>>>
-{
-    using base_type = std::map<converting_key, Value, std::less<converting_key>, // NOLINT(modernize-use-transparent-functors)
-                               typename std::allocator_traits<Allocator>::template rebind_alloc<std::pair<const converting_key, Value>>>;
-
-                             public:
-                               using base_type::base_type;
-                               using base_type::operator=;
-};
-
-using converting_key_json = nlohmann::basic_json<converting_key_object>;
-
 } // namespace
 
 TEST_CASE("UTF-8 error_handler for the binary readers and writers")
@@ -416,109 +370,3 @@ TEST_CASE("UTF-8 error_handler for the binary readers and writers")
         CHECK(json::from_bson(bson_bytes)["k"].get<std::string>() == ill_formed_cases()[0].bytes);
     }
 }
-
-// The UBJSON and BJData writers bind the (possibly sanitized) key to a const
-// string_t&. If key_type is not string_t but converts to it, the converted
-// temporary must outlive that reference; this was a use-after-scope found by
-// AddressSanitizer. Keys exceed the small string optimization on purpose.
-TEST_CASE("UBJSON and BJData writers with an object_t whose key_type is not string_t")
-{
-    const std::string long_prefix(70, 'k');
-
-    SECTION("well-formed keys, every error_handler")
-    {
-        const std::string key1 = long_prefix + "-first";
-        const std::string key2 = long_prefix + "-second";
-
-        converting_key_json::object_t o;
-        o.emplace(converting_key(key1), 1);
-        o.emplace(converting_key(key2), "value");
-        const converting_key_json v(std::move(o));
-
-        json expected;
-        expected[key1] = 1;
-        expected[key2] = "value";
-
-        const bool combos[3][2] = {{false, false}, {true, false}, {true, true}};
-        for (const auto h : all_handlers())
-        {
-            CAPTURE(static_cast<int>(h))
-            for (const auto& combo : combos)
-            {
-                const bool use_count = combo[0];
-                const bool use_type = combo[1];
-                CAPTURE(use_count)
-                CAPTURE(use_type)
-
-                CHECK(json::from_ubjson(converting_key_json::to_ubjson(v, use_count, use_type, h)) == expected);
-                CHECK(json::from_bjdata(converting_key_json::to_bjdata(v, use_count, use_type, json::bjdata_version_t::draft2, h)) == expected);
-                CHECK(json::from_bjdata(converting_key_json::to_bjdata(v, use_count, use_type, json::bjdata_version_t::draft3, h)) == expected);
-            }
-        }
-    }
-
-    SECTION("ill-formed keys")
-    {
-        for (const auto& c : ill_formed_cases())
-        {
-            CAPTURE(c.name)
-            const std::string key = long_prefix + c.bytes;
-
-            converting_key_json::object_t o;
-            o.emplace(converting_key(key), 1);
-            const converting_key_json v(std::move(o));
-
-            CHECK_THROWS_AS(converting_key_json::to_ubjson(v, false, false, eh::strict), converting_key_json::type_error&);
-            CHECK_THROWS_AS(converting_key_json::to_bjdata(v, false, false, json::bjdata_version_t::draft2, eh::strict), converting_key_json::type_error&);
-
-            for (const auto h :
-                    {
-                        eh::replace, eh::ignore
-                    })
-            {
-                CAPTURE(static_cast<int>(h))
-                const std::string expected = dump_and_parse(key, h);
-
-                CHECK(json::from_ubjson(converting_key_json::to_ubjson(v, false, false, h)).begin().key() == expected);
-                CHECK(json::from_bjdata(converting_key_json::to_bjdata(v, false, false, json::bjdata_version_t::draft2, h)).begin().key() == expected);
-            }
-
-            CHECK(json::from_ubjson(converting_key_json::to_ubjson(v, false, false, eh::keep)).begin().key() == key);
-            CHECK(json::from_bjdata(converting_key_json::to_bjdata(v, false, false, json::bjdata_version_t::draft2, eh::keep)).begin().key() == key);
-        }
-    }
-
-    SECTION("nested deeper than the recursion limit")
-    {
-        // wrap the previous value, innermost first
-        converting_key_json v = 42;
-        json expected = 42;
-        for (int i = 199; i >= 0; --i)
-        {
-            const std::string key = "level-" + std::to_string(i) + "-" + std::string(64, 'x');
-
-            converting_key_json::object_t o;
-            o.emplace(converting_key(key), std::move(v));
-            v = converting_key_json(std::move(o));
-
-            json e;
-            e[key] = std::move(expected);
-            expected = std::move(e);
-        }
-
-        for (const auto h : all_handlers())
-        {
-            CAPTURE(static_cast<int>(h))
-            for (const bool use_count :
-                    {
-                        false, true
-                    })
-            {
-                CAPTURE(use_count)
-
-                CHECK(json::from_ubjson(converting_key_json::to_ubjson(v, use_count, false, h)) == expected);
-                CHECK(json::from_bjdata(converting_key_json::to_bjdata(v, use_count, false, json::bjdata_version_t::draft2, h)) == expected);
-            }
-        }
-    }
-}

tests/src/unit-json_pointer.cpp

@@ -939,3 +939,114 @@ TEST_CASE("unescaping keeps a '~' that does not start an escape sequence")
     nlohmann::detail::unescape(s);
     CHECK(s == "~/~");
 }
+
+TEST_CASE("flatten of structured values")
+{
+    SECTION("values nested too deeply for the call stack (#5393)")
+    {
+        // flatten() used to recurse once per nesting level
+        const std::size_t depth = 100000;
+        for (const bool objects :
+                {
+                    false, true
+                })
+        {
+            CAPTURE(objects)
+            std::string text;
+            std::string path;
+            for (std::size_t i = 0; i < depth; ++i)
+            {
+                text += objects ? "{\"a\":" : "[";
+                path += objects ? "/a" : "/0";
+            }
+            text += "0";
+            text += std::string(depth, objects ? '}' : ']');
+            const auto value = json::parse(text);
+
+            const auto flat = value.flatten();
+            REQUIRE(flat.size() == 1);
+            REQUIRE(flat.begin().key().size() == path.size());
+            CHECK(flat.begin().key() == path);
+            CHECK(flat.begin().value() == 0);
+
+            // unflatten() is linear in the depth, so the value roundtrips
+            CHECK(flat.unflatten() == value);
+        }
+    }
+
+    SECTION("unflatten of a deeply nested pointer")
+    {
+        const std::size_t depth = 100000;
+        for (const bool objects :
+                {
+                    false, true
+                })
+        {
+            CAPTURE(objects)
+            std::string path;
+            for (std::size_t i = 0; i < depth; ++i)
+            {
+                path += objects ? "/a" : "/0";
+            }
+
+            json flat = json::object();
+            flat[path] = 1;
+            const json value = flat.unflatten();
+
+            // walk down iteratively
+            std::size_t levels = 0;
+            const json* current = &value;
+            while (objects ? current->is_object() : current->is_array())
+            {
+                REQUIRE(current->size() == 1);
+                current = objects ? &current->at("a") : &current->at(0);
+                ++levels;
+            }
+            CHECK(levels == depth);
+            CHECK(*current == 1);
+        }
+    }
+
+    SECTION("unflatten does not depend on the iteration order")
+    {
+        // the "0" key comes after its sibling in iteration order
+        const nlohmann::ordered_json flat_array = nlohmann::ordered_json::parse(R"({"/a/1": 2, "/a/0": 1})");
+        CHECK(flat_array.unflatten() == nlohmann::ordered_json::parse(R"({"a": [1, 2]})"));
+
+        const nlohmann::ordered_json flat_object = nlohmann::ordered_json::parse(R"({"/b/1": 2})");
+        CHECK(flat_object.unflatten() == nlohmann::ordered_json::parse(R"({"b": {"1": 2}})"));
+    }
+
+    SECTION("objects and arrays interleaved")
+    {
+        const json value =
+        {
+            {"a", {1, {{"b", json::array()}, {"c", json::object()}}, json::array({{{"x~/", {true, nullptr}}}})}},
+            {"a/b", {{"~", 1}}},
+            {"z", "s"}
+        };
+
+        const json expected =
+        {
+            {"/a/0", 1},
+            {"/a/1/b", nullptr},
+            {"/a/1/c", nullptr},
+            {"/a/2/0/x~0~1/0", true},
+            {"/a/2/0/x~0~1/1", nullptr},
+            {"/a~1b/~0", 1},
+            {"/z", "s"}
+        };
+
+        CHECK(value.flatten() == expected);
+    }
+
+    SECTION("order of the entries of an ordered_json")
+    {
+        const auto value = nlohmann::ordered_json::parse(
+                               R"({"z":"s","a/b":{"~":1,"k":[]},"a":[1,{"c":{},"b":[]},[{"x~/":[true,null],"w":2}]]})");
+
+        const auto flat = value.flatten();
+        CHECK(flat.dump() ==
+              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})");
+    }
+}