Flatten deeply nested values without recursing per nesting level

json_pointer::flatten() called itself once per nesting level, so
flatten() on a value nested deeply enough exhausted the call stack.
#5547 and #5548 fixed merge_patch() and diff() from #5393, but flatten()
was left out.

flatten() now walks the value with an explicit stack and keeps the path
in one buffer that grows and shrinks with it. It has a single code path
and no depth limit: the old version built a new path string per child,
so the iterative one is no slower on shallow values and much faster on
deep ones. The output, including the order of an ordered_json result,
is unchanged.

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

docs/mkdocs/docs/api/basic_json/binary_t.md

@@ -64,7 +64,18 @@ values of that type directly to a `basic_json` instance, and they will automatic
 rather than arrays:
 
 ```cpp
-using custom_json = nlohmann::ordered_json::with_binary_t<std::vector<std::byte>>;
+using custom_json = nlohmann::basic_json<
+    nlohmann::ordered_map,  // ObjectType
+    std::vector,            // ArrayType
+    std::string,            // StringType
+    bool,                   // BooleanType
+    std::int64_t,           // NumberIntegerType
+    std::uint64_t,          // NumberUnsignedType
+    double,                 // NumberFloatType
+    std::allocator,         // AllocatorType
+    nlohmann::adl_serializer,
+    std::vector<std::byte>  // Custom BinaryType
+>;
 
 std::vector<std::byte> data{std::byte{1}, std::byte{2}, std::byte{3}};
 custom_json j = data;  // Creates a binary value, not an array

docs/mkdocs/docs/examples/as_base_class.cpp

@@ -15,7 +15,19 @@ class base_class_with_hidden_members
     }
 };
 
-using json = nlohmann::json::with_base_class_t<base_class_with_hidden_members>;
+using json = nlohmann::basic_json <
+             std::map,
+             std::vector,
+             std::string,
+             bool,
+             std::int64_t,
+             std::uint64_t,
+             double,
+             std::allocator,
+             nlohmann::adl_serializer,
+             std::vector<std::uint8_t>,
+             base_class_with_hidden_members
+             >;
 
 int main()
 {

include/nlohmann/detail/json_pointer.hpp

@@ -878,64 +878,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);
             }
         }
     }

single_include/nlohmann/json.hpp

@@ -20796,64 +20796,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);
             }
         }
     }

tests/src/unit-bson.cpp

@@ -46,7 +46,9 @@ class huge_binary_t : public std::vector<std::uint8_t>
     }
 };
 
-using huge_binary_json = nlohmann::json::with_binary_t<huge_binary_t>;
+using huge_binary_json = nlohmann::basic_json <
+                         std::map, std::vector, std::string, bool, std::int64_t, std::uint64_t,
+                         double, std::allocator, nlohmann::adl_serializer, huge_binary_t, void >;
 
 // a string type that can be made to report a size beyond INT32_MAX without
 // allocating that much memory, so BSON length overflow can be tested for
@@ -94,7 +96,9 @@ class huge_string_t : public std::string
     bool pretend_huge = false;
 };
 
-using huge_string_json = nlohmann::json::with_string_t<huge_string_t>;
+using huge_string_json = nlohmann::basic_json <
+                         std::map, std::vector, huge_string_t, bool, std::int64_t, std::uint64_t,
+                         double, std::allocator, nlohmann::adl_serializer, std::vector<std::uint8_t>, void >;
 } // namespace
 
 TEST_CASE("BSON")

tests/src/unit-custom-base-class.cpp

@@ -400,7 +400,20 @@ class base_class_with_hidden_members
     std::size_t m_size = 42;
 };
 
-using json_with_hidden_base_members = nlohmann::json::with_base_class_t<base_class_with_hidden_members>;
+using json_with_hidden_base_members =
+    nlohmann::basic_json <
+    std::map,
+    std::vector,
+    std::string,
+    bool,
+    std::int64_t,
+    std::uint64_t,
+    double,
+    std::allocator,
+    nlohmann::adl_serializer,
+    std::vector<std::uint8_t>,
+    base_class_with_hidden_members
+    >;
 
 TEST_CASE("JSON Node as_base_class")
 {
@@ -446,7 +459,19 @@ struct const_member_base
     const int id = 7; // NOLINT(misc-non-private-member-variables-in-classes)
 };
 
-using json_with_const_base = nlohmann::json::with_base_class_t<const_member_base>;
+using json_with_const_base = nlohmann::basic_json <
+                             std::map,
+                             std::vector,
+                             std::string,
+                             bool,
+                             std::int64_t,
+                             std::uint64_t,
+                             double,
+                             std::allocator,
+                             nlohmann::adl_serializer,
+                             std::vector<std::uint8_t>,
+                             const_member_base
+                             >;
 
 // build an array nested @a depth levels deep, with the innermost value 1;
 // every level is constructed (never assigned), since const_member_base does

tests/src/unit-custom-binary-type.cpp

@@ -26,11 +26,15 @@ namespace
 
 // a BinaryType whose value type is signed: the elements must still be
 // processed as the numbers 0..255
-using char_binary_json = nlohmann::json::with_binary_t<std::vector<char>>;
+using char_binary_json = nlohmann::basic_json <
+                         std::map, std::vector, std::string, bool, std::int64_t, std::uint64_t,
+                         double, std::allocator, nlohmann::adl_serializer, std::vector<char>, void >;
 
 #ifdef JSON_HAS_CPP_17
     // a BinaryType whose value type is not an integer type at all
-    using byte_binary_json = nlohmann::json::with_binary_t<std::vector<std::byte>>;
+    using byte_binary_json = nlohmann::basic_json <
+    std::map, std::vector, std::string, bool, std::int64_t, std::uint64_t,
+    double, std::allocator, nlohmann::adl_serializer, std::vector<std::byte>, void >;
 #endif
 
 } // namespace

tests/src/unit-json_pointer.cpp

@@ -939,3 +939,81 @@ 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 not iterative: it takes time and memory
+            // quadratic in the depth, so it is only roundtripped for a
+            // moderate depth
+            std::string small_text;
+            for (std::size_t i = 0; i < 500; ++i)
+            {
+                small_text += objects ? "{\"a\":" : "[";
+            }
+            small_text += "0";
+            small_text += std::string(500, objects ? '}' : ']');
+            const auto small_value = json::parse(small_text);
+            CHECK(small_value.flatten().unflatten() == small_value);
+        }
+    }
+
+    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})");
+    }
+}

tests/src/unit-msgpack.cpp

@@ -2201,7 +2201,10 @@ struct huge_array : std::vector<T, A>
     }
 };
 
-using huge_array_json = nlohmann::json::with_array_t<huge_array>;
+using huge_array_json = nlohmann::basic_json <
+                        std::map, huge_array, std::string, bool, std::int64_t, std::uint64_t,
+                        double, std::allocator, nlohmann::adl_serializer,
+                        std::vector<std::uint8_t>, void >;
 
 TEST_CASE("MessagePack Size above uint32 for array")
 {
@@ -2246,7 +2249,18 @@ template<typename K, typename V,
     }
 };
 
-using huge_object_json = nlohmann::json::with_object_t<huge_map>;
+using huge_object_json = nlohmann::basic_json <
+                         huge_map,
+                         std::vector,
+                         std::string,
+                         bool,
+                         std::int64_t,
+                         std::uint64_t,
+                         double,
+                         std::allocator,
+                         nlohmann::adl_serializer,
+                         std::vector<std::uint8_t>,
+                         void >;
 
 TEST_CASE("MessagePack Size above uint32 for object")
 {
@@ -2281,7 +2295,18 @@ struct huge_string : std::string
     }
 };
 
-using huge_string_json = nlohmann::json::with_string_t<huge_string>;
+using huge_string_json = nlohmann::basic_json <
+                         std::map,
+                         std::vector,
+                         huge_string,
+                         bool,
+                         std::int64_t,
+                         std::uint64_t,
+                         double,
+                         std::allocator,
+                         nlohmann::adl_serializer,
+                         std::vector<std::uint8_t>,
+                         void >;
 
 TEST_CASE("MessagePack Size above uint32 for string")
 {
@@ -2304,7 +2329,18 @@ struct huge_binary : std::vector<std::uint8_t>
     }
 };
 
-using huge_binary_json = nlohmann::json::with_binary_t<huge_binary>;
+using huge_binary_json = nlohmann::basic_json <
+                         std::map,
+                         std::vector,
+                         std::string,
+                         bool,
+                         std::int64_t,
+                         std::uint64_t,
+                         double,
+                         std::allocator,
+                         nlohmann::adl_serializer,
+                         huge_binary,
+                         void >;
 
 TEST_CASE("MessagePack Size above uint32 for binary")
 {
@@ -2354,10 +2390,14 @@ class beyond_uint32_string_t : public std::string
     }
 };
 
-using beyond_uint32_string_json = nlohmann::json::with_string_t<beyond_uint32_string_t>;
+using beyond_uint32_string_json = nlohmann::basic_json <
+                                  std::map, std::vector, beyond_uint32_string_t, bool, std::int64_t, std::uint64_t,
+                                  double, std::allocator, nlohmann::adl_serializer, std::vector<std::uint8_t>, void >;
 #endif
 
-using beyond_uint32_binary_json = nlohmann::json::with_binary_t<beyond_uint32_binary_t>;
+using beyond_uint32_binary_json = nlohmann::basic_json <
+                                  std::map, std::vector, std::string, bool, std::int64_t, std::uint64_t,
+                                  double, std::allocator, nlohmann::adl_serializer, beyond_uint32_binary_t, void >;
 } // namespace
 
 TEST_CASE("MessagePack lengths beyond UINT32_MAX cannot be serialized")

tests/src/unit-ordered_json2.cpp

@@ -217,7 +217,16 @@ void int_to_string(alt_string& target, std::size_t value)
     target = std::to_string(value).c_str();
 }
 
-using alt_json = nlohmann::json::with_string_t<alt_string>;
+using alt_json = nlohmann::basic_json <
+                 std::map,
+                 std::vector,
+                 alt_string,
+                 bool,
+                 std::int64_t,
+                 std::uint64_t,
+                 double,
+                 std::allocator,
+                 nlohmann::adl_serializer >;
 
 bool operator<(const char* op1, const alt_string& op2) noexcept
 {