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/operator[].md

@@ -137,13 +137,10 @@ Strong exception safety: if an exception occurs, the original value stays intact
 
         When the JSON pointer traverses intermediate levels that don't exist at all yet (not just a missing
         leaf), each missing level is created as an array or an object depending on whether the corresponding
-        pointer token is a valid array index: the token `0`, a sequence of digits that does not begin with `0`,
+        pointer token parses as a non-negative integer: a numeric token creates an array, a non-numeric token
-        or the token `-` creates an array, and every other token creates an object. For example, on an
+        creates an object. For example, on an initially `#!json null` value, `/foo/0/0/0` creates nested arrays,
-        initially `#!json null` value, `/foo/0/0/0` creates nested arrays, while `/foo/one/one/one` creates
+        while `/foo/one/one/one` creates nested objects. This is not specified by the JSON Pointer RFC; it is
-        nested objects. Tokens such as `01` or the empty token cannot be array indices (cf. RFC 6901, Sect. 4)
+        this library's own, intentional disambiguation rule. See also [JSON Pointer](../../features/json_pointer.md).
-        and therefore create objects, just as they would if the level already existed as an object. This is not
-        specified by the JSON Pointer RFC; it is this library's own, intentional disambiguation rule. See also
-        [JSON Pointer](../../features/json_pointer.md).
 
 !!! warning "Deprecation"
 

docs/mkdocs/docs/community/roadmap.md

@@ -36,13 +36,26 @@ work items are tracked in the [GitHub milestones](https://github.com/nlohmann/js
 ## API stability
 
 Releases follow [semantic versioning](https://semver.org): a minor or patch release of version 3.x does not break code
-that uses the public API. In particular, a 3.x release does not:
+that uses the public API, unless that code opts in to a change with a macro as described [below](#version-40). In
+particular, a 3.x release does not:
 
-- change the signature of a function (its parameter types, return type, number of parameters, or the const-ness of a
+- make breaking changes to the signature of a function: the types or order of its existing parameters, its return type,
-  member function);
+  its `noexcept` or `constexpr` specifier, or the const-ness of a member function. New parameters may be added if they
-- remove or rename a function or class;
+  have a default value;
+- remove or rename a function or class, or change the template parameters of a public class template;
 - change which exceptions a function throws, or the [exception ids](../home/exceptions.md);
-- change access specifiers or default arguments.
+- change access specifiers, or change or remove existing default arguments. New default arguments may be added;
+- change the JSON type that a valid input parses to, or the text that `dump()` produces for a valid value;
+- accept input that was rejected before, or reject input that was accepted before;
+- change the order in which the keys of an object are iterated. The default type sorts keys, and
+  [`ordered_json`](../api/ordered_json.md) keeps insertion order;
+- change when iterators, pointers, or references are invalidated, or the state of a moved-from `basic_json`;
+- add or remove implicit conversions from `basic_json`;
+- change how `to_json` and `from_json` functions are found, or the behavior of
+  [`adl_serializer`](../api/adl_serializer/index.md);
+- add pure virtual functions to the [`json_sax`](../api/json_sax/index.md) interface;
+- remove, rename, renumber, or add enumerators of `value_t`;
+- remove or rename a documented macro, CMake option, CMake target, or header, or change what a documented macro does.
 
 Exceptions to these rules, for instance when fixing a bug requires changing the exception a function throws, are
 documented in the [release notes](../home/releases.md).
@@ -51,13 +64,14 @@ The following are **not** part of the public API and may change in any release,
 
 - The text of exception messages returned by `what()`. Use the [exception id](../home/exceptions.md) to tell errors
   apart.
-- The ABI, including `sizeof(basic_json)` and the memory layout of its values. Recompile your code when you upgrade the
+- The ABI, including `sizeof(basic_json)` and the memory layout of its values. The
-  library. The [versioned inline namespace](../features/namespace.md) turns mixing versions into a link error.
+  [versioned inline namespace](../features/namespace.md) turns mixing versions into a link error.
+- The hash values returned by `std::hash` for `basic_json`. Numbers that compare equal still hash equally.
 - Everything in namespace `nlohmann::detail`, and macros and type traits that are not documented in the
   [API reference](../api/basic_json/index.md).
 
-Changes that would break the public API are only added behind a macro whose default keeps the 3.x behavior, see
+Breaking changes are only added behind a macro whose default keeps the 3.x behavior. See [Version 4.0](#version-40) and
-[Version 4.0](#version-40).
+the [macro overview](../features/macros.md).
 
 ## Version 4.0
 

docs/mkdocs/docs/examples/contains__json_pointer.cpp

@@ -19,25 +19,9 @@ int main()
               << j.contains("/array/1"_json_pointer) << '\n'
               << j.contains("/array/-"_json_pointer) << '\n'
               << j.contains("/array/4"_json_pointer) << '\n'
-              << j.contains("/baz"_json_pointer) << std::endl;
+              << j.contains("/baz"_json_pointer) << '\n'
-
+              // an array index with a leading '0' is not found
-    try
+              << j.contains("/array/01"_json_pointer) << '\n'
-    {
+              // an array index that is not a number is not found
-        // try to use an array index with leading '0'
+              << j.contains("/array/one"_json_pointer) << std::endl;
-        j.contains("/array/01"_json_pointer);
-    }
-    catch (const json::parse_error& e)
-    {
-        std::cout << e.what() << '\n';
-    }
-
-    try
-    {
-        // try to use an array index that is not a number
-        j.contains("/array/one"_json_pointer);
-    }
-    catch (const json::parse_error& e)
-    {
-        std::cout << e.what() << '\n';
-    }
 }

docs/mkdocs/docs/examples/contains__json_pointer.output

@@ -5,3 +5,5 @@ true
 false
 false
 false
+false
+false

docs/mkdocs/docs/examples/parse_error.cpp

@@ -8,7 +8,7 @@ int main()
     try
     {
         // parsing input with a syntax error
-        json::parse("[1,2,3,]");
+        json j = json::parse("[1,2,3,]");
     }
     catch (const json::parse_error& e)
     {

include/nlohmann/detail/json_pointer.hpp

@@ -473,19 +473,15 @@ class json_pointer
             // convert null values to arrays or objects before continuing
             if (ptr->is_null())
             {
-                // check if the reference token is a valid array index, that is
+                // check if the reference token is a number
-                // a nonempty sequence of digits without a leading '0'
+                const bool nums =
-                // (cf. RFC 6901, Sect. 4); tokens that could never be a valid
+                    std::all_of(reference_token.begin(), reference_token.end(),
-                // array index (such as "01" or "") are treated as object keys
-                const bool nums = !reference_token.empty()
-                                  && (reference_token.size() == 1 || reference_token[0] != '0')
-                                  && std::all_of(reference_token.begin(), reference_token.end(),
                                 [](const unsigned char x)
                 {
                     return std::isdigit(x);
                 });
 
-                // change value to an array for array indices or "-" or to object otherwise
+                // change value to an array for numbers or "-" or to object otherwise
                 *ptr = (nums || reference_token == "-")
                        ? detail::value_t::array
                        : detail::value_t::object;
@@ -882,49 +878,70 @@ 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
+        {
+            const BasicJsonType* container;
+            std::size_t index;
+            object_const_iterator member;
+            std::size_t path_length;
+        };
+
+        // 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;
+
+        // 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())
             {
                 case detail::value_t::array:
                 {
-                if (value.m_data.m_value.array->empty())
+                    if (v.m_data.m_value.array->empty())
                     {
                         // flatten empty array as null
-                    result[reference_string] = nullptr;
+                        result[path] = nullptr;
                     }
                     else
                     {
-                    // iterate array and use index as a reference string
+                        stack.push_back({&v, 0, object_const_iterator(), path.size()});
-                    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);
                     }
-                }
+                    return;
-                break;
                 }
 
                 case detail::value_t::object:
                 {
-                if (value.m_data.m_value.object->empty())
+                    if (v.m_data.m_value.object->empty())
                     {
                         // flatten empty object as null
-                    result[reference_string] = nullptr;
+                        result[path] = nullptr;
                     }
                     else
                     {
-                    // iterate object and use keys as reference string
+                        stack.push_back({&v, 0, v.m_data.m_value.object->begin(), path.size()});
-                    for (const auto& element : *value.m_data.m_value.object)
-                    {
-                        flatten(detail::concat<string_t>(reference_string, '/', detail::escape(element.first)), element.second, result);
                     }
-                }
+                    return;
-                break;
                 }
 
                 case detail::value_t::null:
@@ -938,8 +955,50 @@ class json_pointer
                 default:
                 {
                     // add a primitive value with its reference string
-                result[reference_string] = value;
+                    result[path] = v;
-                break;
+                    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

@@ -20391,19 +20391,15 @@ class json_pointer
             // convert null values to arrays or objects before continuing
             if (ptr->is_null())
             {
-                // check if the reference token is a valid array index, that is
+                // check if the reference token is a number
-                // a nonempty sequence of digits without a leading '0'
+                const bool nums =
-                // (cf. RFC 6901, Sect. 4); tokens that could never be a valid
+                    std::all_of(reference_token.begin(), reference_token.end(),
-                // array index (such as "01" or "") are treated as object keys
-                const bool nums = !reference_token.empty()
-                                  && (reference_token.size() == 1 || reference_token[0] != '0')
-                                  && std::all_of(reference_token.begin(), reference_token.end(),
                                 [](const unsigned char x)
                 {
                     return std::isdigit(x);
                 });
 
-                // change value to an array for array indices or "-" or to object otherwise
+                // change value to an array for numbers or "-" or to object otherwise
                 *ptr = (nums || reference_token == "-")
                        ? detail::value_t::array
                        : detail::value_t::object;
@@ -20800,49 +20796,70 @@ 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
+        {
+            const BasicJsonType* container;
+            std::size_t index;
+            object_const_iterator member;
+            std::size_t path_length;
+        };
+
+        // 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;
+
+        // 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())
             {
                 case detail::value_t::array:
                 {
-                if (value.m_data.m_value.array->empty())
+                    if (v.m_data.m_value.array->empty())
                     {
                         // flatten empty array as null
-                    result[reference_string] = nullptr;
+                        result[path] = nullptr;
                     }
                     else
                     {
-                    // iterate array and use index as a reference string
+                        stack.push_back({&v, 0, object_const_iterator(), path.size()});
-                    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);
                     }
-                }
+                    return;
-                break;
                 }
 
                 case detail::value_t::object:
                 {
-                if (value.m_data.m_value.object->empty())
+                    if (v.m_data.m_value.object->empty())
                     {
                         // flatten empty object as null
-                    result[reference_string] = nullptr;
+                        result[path] = nullptr;
                     }
                     else
                     {
-                    // iterate object and use keys as reference string
+                        stack.push_back({&v, 0, v.m_data.m_value.object->begin(), path.size()});
-                    for (const auto& element : *value.m_data.m_value.object)
-                    {
-                        flatten(detail::concat<string_t>(reference_string, '/', detail::escape(element.first)), element.second, result);
                     }
-                }
+                    return;
-                break;
                 }
 
                 case detail::value_t::null:
@@ -20856,8 +20873,50 @@ class json_pointer
                 default:
                 {
                     // add a primitive value with its reference string
-                result[reference_string] = value;
+                    result[path] = v;
-                break;
+                    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/CMakeLists.txt

@@ -138,7 +138,8 @@ json_test_set_test_options(test-disabled_exceptions
 # only the #972 regression test needs thirdparty/fifo_map on its include path
 json_test_set_test_options(test-regression1 LINK_LIBRARIES fifo_map_include)
 
-# GCC's false -Warray-bounds error with JSON_DIAGNOSTICS only shows up when optimizing (#5742).
+# Regression test for GCC's false -Warray-bounds error with JSON_DIAGNOSTICS (#5742, fixed in #5585). It only
+# showed up when optimizing, so build this test with -O3 and the warning as an error.
 # -O3 makes the optimizer-driven warnings of the ci_test_gcc flag set (-Winline,
 # -Wsuggest-attribute=...) fire on the library's inline functions; they are not
 # what this test checks, so turn them off for it.

tests/src/unit-json_pointer.cpp

@@ -466,72 +466,6 @@ TEST_CASE("JSON pointers")
         }
     }
 
-    SECTION("creating intermediate levels")
-    {
-        SECTION("tokens that are valid array indices create arrays")
-        {
-            json j;
-            j["/0"_json_pointer] = 1;
-            CHECK(j == json({1}));
-
-            json j2;
-            j2["/2"_json_pointer] = 1;
-            CHECK(j2 == json({nullptr, nullptr, 1}));
-
-            json j3;
-            j3["/-"_json_pointer] = 1;
-            CHECK(j3 == json({1}));
-
-            json j4;
-            j4["/foo/0/0"_json_pointer] = 1;
-            CHECK(j4 == json({{"foo", {{1}}}}));
-        }
-
-        SECTION("tokens that are no valid array indices create objects")
-        {
-            json j;
-            j["/one"_json_pointer] = 1;
-            CHECK(j == json({{"one", 1}}));
-
-            // leading '0' can never be a valid array index (RFC 6901, Sect. 4)
-            json j2;
-            j2["/01"_json_pointer] = 1;
-            CHECK(j2 == json({{"01", 1}}));
-
-            // the empty token is a valid object key, but no valid array index
-            json j3;
-            j3["/"_json_pointer] = 1;
-            CHECK(j3 == json({{"", 1}}));
-        }
-
-        SECTION("creating a level yields the same result as reusing it (#5357)")
-        {
-            json j;
-            j["/a/b/01/d"_json_pointer] = "value";
-
-            json j_init = json::object();
-            j_init["/a/b"_json_pointer] = json::object();
-            j_init["/a/b/01/d"_json_pointer] = "value";
-
-            const json expected = json::parse(R"({"a":{"b":{"01":{"d":"value"}}}})");
-            CHECK(j == expected);
-            CHECK(j_init == expected);
-
-            // unflatten uses the same key
-            const json flat = {{"/a/b/01/d", "value"}};
-            CHECK(flat.unflatten() == expected);
-        }
-
-        SECTION("existing arrays still reject invalid indices")
-        {
-            json j = {1, 2, 3};
-            CHECK_THROWS_WITH_AS(j["/01"_json_pointer],
-                                 "[json.exception.parse_error.106] parse error: array index '01' must not begin with '0'", json::parse_error&);
-            CHECK_THROWS_WITH_AS(j.at("/01"_json_pointer),
-                                 "[json.exception.parse_error.106] parse error: array index '01' must not begin with '0'", json::parse_error&);
-        }
-    }
-
     SECTION("flatten")
     {
         json j =
@@ -1005,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})");
+    }
+}