Fix GCC and clang-tidy warnings in the JSON pointer speedups

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

cmake/requirements/requirements-cppcheck.txt

@@ -1 +1 @@
-cppcheck==1.5.3
+cppcheck==1.5.2

include/nlohmann/detail/json_pointer.hpp

@@ -9,10 +9,13 @@
 #pragma once
 
 #include <algorithm> // all_of
+#include <array> // array
 #include <cctype> // isdigit
 #include <cerrno> // errno, ERANGE
 #include <cstddef> // size_t
+#include <cstdint> // uint64_t
 #include <cstdlib> // strtoull
+#include <cstring> // memcmp, memcpy
 #ifndef JSON_NO_IO
     #include <iosfwd> // ostream
 #endif  // JSON_NO_IO
@@ -24,6 +27,7 @@
 #include <nlohmann/detail/exceptions.hpp>
 #include <nlohmann/detail/macro_scope.hpp>
 #include <nlohmann/detail/meta/cpp_future.hpp>
+#include <nlohmann/detail/meta/type_traits.hpp>
 #include <nlohmann/detail/string_concat.hpp>
 #include <nlohmann/detail/string_escape.hpp>
 #include <nlohmann/detail/string_utils.hpp>
@@ -492,50 +496,111 @@ class json_pointer
 
   private:
     /*!
-    @brief the pointer prefixes of a flattened object, and which of them denote arrays
+    @brief the pointer prefixes of a flattened object that 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.
+    @ref unflatten creates arrays exactly below the prefixes that have a
+    reference token 0 among their children, 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 (number 0 is the empty prefix),
-    so each of them is stored only once (as a node) rather than as a copy of
-    all of its reference tokens. The tree does not own the reference tokens:
-    it refers to the tokens of the parsed keys, which must outlive it.
+    A prefix is identified by the text of the key it is the beginning of:
+    escaping is unambiguous, so equal prefixes of valid keys are equal texts.
+    The set refers to the keys, which must outlive it.
     */
-    struct prefix_tree
+    class array_prefix_set
     {
-        // open-addressing hash table from (parent, last reference token) to
-        // the number of the node; empty slots have token == nullptr
+      public:
+        void insert(const char* data, std::size_t size)
+        {
+            // flattened objects are usually sorted, so most keys that have a
+            // 0 yield the prefix of the previous one
+            if (last_data != nullptr && last_size == size && std::memcmp(last_data, data, size) == 0)
+            {
+                return;
+            }
+            last_data = data;
+            last_size = size;
+
+            if (slots.empty())
+            {
+                slots.resize(16);
+            }
+            const std::size_t hash = hash_of(data, size);
+            const std::size_t mask = slots.size() - 1;
+            std::size_t i = hash & mask;
+            while (slots[i].data != nullptr)
+            {
+                if (slots[i].hash == hash && slots[i].size == size && std::memcmp(slots[i].data, data, size) == 0)
+                {
+                    return;
+                }
+                i = (i + 1) & mask;
+            }
+            slots[i] = slot(hash, data, size);
+
+            // keep the load factor below 1/2
+            if (++used * 2 > slots.size())
+            {
+                grow();
+            }
+        }
+
+        bool empty() const noexcept
+        {
+            return used == 0;
+        }
+
+        bool contains(const char* data, std::size_t size) const noexcept
+        {
+            if (used == 0)
+            {
+                return false;
+            }
+            const std::size_t hash = hash_of(data, size);
+            const std::size_t mask = slots.size() - 1;
+            for (std::size_t i = hash & mask; slots[i].data != nullptr; i = (i + 1) & mask)
+            {
+                if (slots[i].hash == hash && slots[i].size == size && std::memcmp(slots[i].data, data, size) == 0)
+                {
+                    return true;
+                }
+            }
+            return false;
+        }
+
+      private:
         struct slot
         {
-            std::size_t hash;
-            std::size_t parent;
-            const string_t* token;
-            std::size_t id;
+            slot() noexcept = default;
 
-            slot() noexcept
-                : hash(0), parent(0), token(nullptr), id(0)
+            slot(std::size_t h, const char* d, std::size_t s) noexcept
+                : hash(h), data(d), size(s)
             {}
 
-            slot(std::size_t h, std::size_t p, const string_t* t, std::size_t i) noexcept
-                : hash(h), parent(p), token(t), id(i)
-            {}
+            std::size_t hash = 0;
+            const char* data = nullptr; // nullptr: the slot is empty
+            std::size_t size = 0;
         };
 
-        std::vector<slot> slots;
-        std::size_t used = 0;
-
-        static std::size_t hash_of(std::size_t parent, const string_t& token) noexcept
+        static std::size_t hash_of(const char* data, std::size_t size) noexcept
         {
-            std::size_t h = parent * static_cast<std::size_t>(0x9E3779B97F4A7C15ULL & (std::numeric_limits<std::size_t>::max)());
-            for (std::size_t i = 0; i < token.size(); ++i)
+            std::uint64_t h = 0x9E3779B97F4A7C15ULL ^ size;
+            std::size_t i = 0;
+            for (; i + 8 <= size; i += 8)
             {
-                h = (h ^ static_cast<unsigned char>(token[i])) * static_cast<std::size_t>(0x100000001B3ULL & (std::numeric_limits<std::size_t>::max)());
+                std::uint64_t w = 0;
+                std::memcpy(&w, data + i, 8);
+                h = (h ^ w) * 0x100000001B3ULL;
+                h ^= h >> 32u;
             }
-            return h ^ (h >> 29u);
+            std::uint64_t w = 0;
+            if (i < size)
+            {
+                std::memcpy(&w, data + i, size - i);
+            }
+            h = (h ^ w) * 0x9E3779B97F4A7C15ULL;
+            return detail::conditional_static_cast<std::size_t>(h ^ (h >> 29u));
         }
 
         void grow()
@@ -545,10 +610,10 @@ class json_pointer
             const std::size_t mask = slots.size() - 1;
             for (const auto& s : old)
             {
-                if (s.token != nullptr)
+                if (s.data != nullptr)
                 {
                     std::size_t i = s.hash & mask;
-                    while (slots[i].token != nullptr)
+                    while (slots[i].data != nullptr)
                     {
                         i = (i + 1) & mask;
                     }
@@ -557,117 +622,160 @@ class json_pointer
             }
         }
 
-        // parent[id] is the number of the prefix without its last token
-        std::vector<std::size_t> parent;
-        // 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;
-
-        // start with the empty prefix only
-        prefix_tree()
-            : slots(16)
-            , parent(1, 0)
-            , is_array(1, false)
-        {}
-
-        // return the number of the prefix with number id extended by
-        // reference_token, adding it if it is new
-        std::size_t add_child(std::size_t id, const string_t& reference_token)
-        {
-            const std::size_t hash = hash_of(id, reference_token);
-            const std::size_t mask = slots.size() - 1;
-            std::size_t i = hash & mask;
-            while (slots[i].token != nullptr)
-            {
-                if (slots[i].hash == hash && slots[i].parent == id && *slots[i].token == reference_token)
-                {
-                    return slots[i].id;
-                }
-                i = (i + 1) & mask;
-            }
-
-            // new prefix
-            const std::size_t child = parent.size();
-            slots[i] = slot(hash, id, &reference_token, child);
-            if (reference_token == "0")
-            {
-                is_array[id] = true;
-            }
-            parent.push_back(id);
-            is_array.push_back(false);
-
-            // keep the load factor below 1/2
-            if (++used * 2 > slots.size())
-            {
-                grow();
-            }
-            return child;
-        }
+        std::vector<slot> slots{};
+        std::size_t used = 0;
+        const char* last_data = nullptr;
+        std::size_t last_size = 0;
     };
 
+    /// @brief the length of the longest common prefix of the first @a limit bytes of @a a and @a b
+    static std::size_t common_prefix_length(const char* a, const char* b, const std::size_t limit) noexcept
+    {
+        std::size_t i = 0;
+        for (; i + 8 <= limit; i += 8)
+        {
+            std::uint64_t x = 0;
+            std::uint64_t y = 0;
+            std::memcpy(&x, a + i, 8);
+            std::memcpy(&y, b + i, 8);
+            if (x != y)
+            {
+                break;
+            }
+        }
+        while (i < limit && a[i] == b[i])
+        {
+            ++i;
+        }
+        return i;
+    }
+
     /*!
-    @brief create and return a reference to the pointed to value
+    @brief check that @a key is a valid JSON pointer, and add the prefixes of
+           it that denote arrays to @a arrays
 
-    @param[in] j  the value to create the pointed to value in
-    @param[in] tokens  the reference tokens of the pointer
-    @param[in] prefixes  prefixes[i] is the number in @a tree of the prefix
-                         consisting of the first i reference tokens
+    @throw parse_error.107  if the key is not empty or begins with '/'
+    @throw parse_error.108  if character '~' is not followed by '0' or '1'
 
-    Complexity: Linear in the number of reference tokens.
+    The same checks as @ref split, which throws the same exceptions, but
+    without building the reference tokens.
+    */
+    static void scan_key(const string_t& key, const string_t* previous, array_prefix_set& arrays)
+    {
+        const std::size_t size = key.size();
+        if (size == 0)
+        {
+            return;
+        }
 
-    @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
+        const char* const data = key.data();
+        if (JSON_HEDLEY_UNLIKELY(data[0] != '/'))
+        {
+            JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_missing_slash, 1, detail::concat("JSON pointer must be empty or begin with '/' - was: '", key, "'"), nullptr));
+        }
+
+        // The beginning of the key that it has in common with the previous
+        // one, which was checked already, is skipped: the scan starts with
+        // the token after the last slash in it.
+        std::size_t begin = 1;
+        if (previous != nullptr)
+        {
+            std::size_t same = common_prefix_length(data, previous->data(), (std::min)(size, previous->size()));
+            while (same > 1 && data[same - 1] != '/')
+            {
+                --same;
+            }
+            if (same > 1)
+            {
+                begin = same;
+            }
+        }
+
+        for (std::size_t i = begin; i <= size; ++i)
+        {
+            if (i == size || data[i] == '/')
+            {
+                // a token 0 makes the pointer before it an array
+                if (i - begin == 1 && data[begin] == '0')
+                {
+                    arrays.insert(data, begin - 1);
+                }
+                begin = i + 1;
+            }
+            else if (data[i] == '~')
+            {
+                // ~ must be followed by 0 or 1
+                if (JSON_HEDLEY_UNLIKELY(i + 1 == size || (data[i + 1] != '0' && data[i + 1] != '1')))
+                {
+                    JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_invalid_escape, 0, "escape character '~' must be followed with '0' or '1'", nullptr));
+                }
+            }
+        }
+    }
+
+    /*!
+    @brief resolve a plain JSON pointer without building its reference tokens
+
+    @param[in] ptr     the value the pointer starts at
+    @param[in] path    a JSON pointer string
+    @param[in] length  the number of leading bytes of @a path to resolve; 0 or
+                       the position of a slash
+    @param[in,out] token  a string to hold the reference tokens, to reuse its storage
+
+    @return the pointed to value, or `nullptr` if the pointer does not denote
+            an existing value, or does so in a way that is not plain: a
+            reference token with an escape, an array index that is malformed or
+            out of range, or a "-". No exception is thrown for these; callers
+            use @ref json_pointer instead, which handles them.
     */
     template<typename BasicJsonType>
-    static BasicJsonType& get_and_create(BasicJsonType& j, const std::vector<string_t>& tokens,
-                                         const std::vector<std::size_t>& prefixes, const prefix_tree& tree)
+    static BasicJsonType* resolve_plain(BasicJsonType* ptr, const string_t& path, const std::size_t length, string_t& token)
     {
-        auto* result = &j;
-
-        // in case no reference tokens exist, return a reference to the JSON value
-        // j which will be overwritten by a primitive value
-        for (std::size_t i = 0; i < tokens.size(); ++i)
+        for (std::size_t pos = 0; pos < length;)
         {
-            const auto& reference_token = tokens[i];
-            switch (result->type())
+            if (JSON_HEDLEY_UNLIKELY(path[pos] != '/'))
             {
-                case detail::value_t::null:
-                {
-                    if (tree.is_array[prefixes[i]])
-                    {
-                        // some reference token below this position is 0, so the
-                        // value is an array
-                        result = &result->operator[](array_index<BasicJsonType>(reference_token));
-                    }
-                    else
-                    {
-                        // start a new object otherwise
-                        result = &result->operator[](reference_token);
-                    }
-                    break;
-                }
+                return nullptr;
+            }
 
+            // the reference token between the slash at pos and the next one
+            std::size_t end = path.find_first_of('/', pos + 1);
+            if (end == string_t::npos || end > length)
+            {
+                end = length;
+            }
+            token.clear();
+            token.append(path.data() + pos + 1, end - pos - 1);
+            if (JSON_HEDLEY_UNLIKELY(token.find_first_of('~') != string_t::npos))
+            {
+                return nullptr;
+            }
+
+            switch (ptr->type())
+            {
                 case detail::value_t::object:
                 {
-                    // create an entry in the object
-                    result = &object_member(*result, reference_token);
+                    const auto it = ptr->m_data.m_value.object->find(token);
+                    if (JSON_HEDLEY_UNLIKELY(it == ptr->m_data.m_value.object->end()))
+                    {
+                        return nullptr;
+                    }
+                    ptr = &it->second;
                     break;
                 }
 
                 case detail::value_t::array:
                 {
-                    // create an entry in the array
-                    result = &result->operator[](array_index<BasicJsonType>(reference_token));
+                    typename BasicJsonType::size_type idx{};
+                    if (JSON_HEDLEY_UNLIKELY(parse_array_index<BasicJsonType>(token, idx) != array_index_status::ok || idx >= ptr->m_data.m_value.array->size()))
+                    {
+                        return nullptr;
+                    }
+                    ptr = &(*ptr->m_data.m_value.array)[idx];
                     break;
                 }
 
-                /*
-                The following code is only reached if there exists a reference
-                token _and_ the current value is primitive. In this case, we have
-                an error situation, because primitive values may only occur as
-                a single value; that is, with an empty list of reference tokens.
-                */
+                case detail::value_t::null:
                 case detail::value_t::string:
                 case detail::value_t::boolean:
                 case detail::value_t::number_integer:
@@ -676,11 +784,12 @@ class json_pointer
                 case detail::value_t::binary:
                 case detail::value_t::discarded:
                 default:
-                    JSON_THROW(detail::type_error::create(detail::exception_id::unflatten_invalid_value, "invalid value to unflatten", &j));
+                    return nullptr;
             }
+            pos = end;
         }
 
-        return *result;
+        return ptr;
     }
 
     /*!
@@ -1135,20 +1244,45 @@ class json_pointer
     // Add the entry (key, v) to the object `obj`. Flattened paths are pairwise
     // distinct, so objects that can append a key known to be absent
     // (ordered_map) skip the lookup, which is linear and would make flatten
-    // quadratic; all other object types use operator[].
+    // quadratic. Objects with a positional insert (std::map) insert next to
+    // the entry added last: paths come out in nearly sorted order, so the
+    // position is usually right and no search from the root is needed.
+    // All other object types use operator[].
     template<typename ObjectType, typename ValueType>
-    static auto add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, detail::priority_tag<1> /*unused*/)
+    static auto add_flattened(ObjectType& obj, typename ObjectType::iterator& /*hint*/, const string_t& key, ValueType&& v, detail::priority_tag<2> /*unused*/)
     -> decltype(obj.emplace_new_key(key, std::forward<ValueType>(v)), void())
     {
         obj.emplace_new_key(key, std::forward<ValueType>(v));
     }
 
     template<typename ObjectType, typename ValueType>
-    static void add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, detail::priority_tag<0> /*unused*/)
+    static auto add_flattened(ObjectType& obj, typename ObjectType::iterator& hint, const string_t& key, ValueType&& v, detail::priority_tag<1> /*unused*/)
+    -> decltype(hint = obj.emplace_hint(hint, key, std::forward<ValueType>(v)), void())
+    {
+        hint = obj.emplace_hint(hint, key, std::forward<ValueType>(v));
+        ++hint;
+    }
+
+    template<typename ObjectType, typename ValueType>
+    static void add_flattened(ObjectType& obj, typename ObjectType::iterator& /*hint*/, const string_t& key, ValueType&& v, detail::priority_tag<0> /*unused*/)
     {
         obj[key] = std::forward<ValueType>(v);
     }
 
+    /// append the decimal representation of @a i to @a out
+    static void append_index(string_t& out, std::size_t i)
+    {
+        std::array<char, 24> buf{};
+        std::size_t pos = buf.size();
+        do
+        {
+            buf[--pos] = static_cast<char>('0' + (i % 10));
+            i /= 10;
+        }
+        while (i != 0);
+        out.append(buf.data() + pos, buf.size() - pos);
+    }
+
     /*!
     @param[in] reference_string  the reference string to the current value
     @param[in] value             the value to consider
@@ -1194,7 +1328,8 @@ class json_pointer
         // flatten `v`, whose path is `path`: primitives and empty containers
         // are added to the result right away; other containers get a frame
         auto& object = *result.m_data.m_value.object;
-        const auto enter = [&stack, &path, &object](const BasicJsonType & v)
+        auto hint = object.end();
+        const auto enter = [&stack, &path, &object, &hint](const BasicJsonType & v)
         {
             switch (v.type())
             {
@@ -1203,7 +1338,7 @@ class json_pointer
                     if (v.m_data.m_value.array->empty())
                     {
                         // flatten empty array as null
-                        add_flattened(object, path, nullptr, detail::priority_tag<1> {});
+                        add_flattened(object, hint, path, nullptr, detail::priority_tag<2> {});
                     }
                     else
                     {
@@ -1217,7 +1352,7 @@ class json_pointer
                     if (v.m_data.m_value.object->empty())
                     {
                         // flatten empty object as null
-                        add_flattened(object, path, nullptr, detail::priority_tag<1> {});
+                        add_flattened(object, hint, path, nullptr, detail::priority_tag<2> {});
                     }
                     else
                     {
@@ -1237,7 +1372,7 @@ class json_pointer
                 default:
                 {
                     // add a primitive value with its reference string
-                    add_flattened(object, path, v, detail::priority_tag<1> {});
+                    add_flattened(object, hint, path, v, detail::priority_tag<2> {});
                     return;
                 }
             }
@@ -1265,7 +1400,8 @@ class json_pointer
 
                 // iterate array and use index as a reference string
                 ++stack.back().index;
-                detail::concat_into(path, '/', detail::to_string<string_t>(i));
+                path.push_back('/');
+                append_index(path, i);
                 enter(array[i]);
             }
             else
@@ -1279,7 +1415,8 @@ class json_pointer
 
                 // iterate object and use keys as reference string
                 ++stack.back().member;
-                detail::concat_into(path, '/', detail::escape(it->first));
+                path.push_back('/');
+                detail::escape_into(path, it->first);
                 enter(it->second);
             }
         }
@@ -1310,53 +1447,30 @@ class json_pointer
 
         BasicJsonType result;
 
-        // parse every key once; the reference tokens are kept for the second
-        // pass (the vectors are never resized, so the tree may refer to them)
-        std::vector<std::vector<string_t>> keys;
-        keys.reserve(value.m_data.m_value.object->size());
+        // check every key, and collect the prefixes that have a reference
+        // token 0 among their children; the values below them are arrays,
+        // all others are objects (see array_prefix_set)
+        array_prefix_set arrays;
+        const string_t* previous_key = nullptr;
         for (const auto& element : *value.m_data.m_value.object)
         {
-            json_pointer ptr(element.first);
-            keys.push_back(std::move(ptr.reference_tokens));
+            scan_key(element.first, previous_key, arrays);
+            previous_key = &element.first;
         }
 
-        // collect the pointer prefixes that have a reference token 0 among
-        // their children; the values below them are arrays, all others are
-        // objects (see prefix_tree)
-        prefix_tree tree;
-        // the number of the prefix with i + 1 tokens of the previous key; keys
-        // are often sorted, so most of the prefix is the same as for the
-        // previous key and need not be looked up again
-        std::vector<std::size_t> path;
-        const std::vector<string_t>* previous = nullptr;
-        // the number of the complete prefix (i.e., the key) of each key
-        std::vector<std::size_t> leaves;
-        leaves.reserve(keys.size());
-        for (const auto& tokens : keys)
-        {
-            std::size_t common = 0;
-            if (previous != nullptr)
-            {
-                const std::size_t limit = (std::min)(tokens.size(), previous->size());
-                while (common < limit && tokens[common] == (*previous)[common])
-                {
-                    ++common;
-                }
-            }
-            path.resize(common);
-            std::size_t id = common == 0 ? 0 : path[common - 1];
-            for (std::size_t i = common; i < tokens.size(); ++i)
-            {
-                id = tree.add_child(id, tokens[i]);
-                path.push_back(id);
-            }
-            leaves.push_back(id);
-            previous = &tokens;
-        }
+        // values[i] is the value after the first i reference tokens of the
+        // previous key, ends[i] the length of that prefix of the key. Keys are
+        // often sorted, so most of the path to the value of a key is the
+        // same as for the previous key and need not be looked up again. Only
+        // the values below the common prefix are dropped, and only they can
+        // move when a value is added: the ones above are not inside the
+        // container that grows.
+        std::vector<BasicJsonType*> values(1, &result);
+        std::vector<std::size_t> ends(1, 0);
+        const string_t* previous = nullptr;
+        string_t token;
 
         // iterate the JSON object values
-        std::vector<std::size_t> prefixes;
-        std::size_t key_index = 0;
         for (const auto& element : *value.m_data.m_value.object)
         {
             if (JSON_HEDLEY_UNLIKELY(!element.second.is_primitive()))
@@ -1364,21 +1478,100 @@ class json_pointer
                 JSON_THROW(detail::type_error::create(detail::exception_id::unflatten_value_not_primitive, "values in object must be primitive", &element.second));
             }
 
-            const auto& tokens = keys[key_index];
-            // number the prefixes of this key from its last one to the first
-            prefixes.resize(tokens.size());
-            for (std::size_t i = tokens.size(), id = leaves[key_index]; i > 0; --i)
+            const string_t& key = element.first;
+            const char* const data = key.data();
+
+            // the number of reference tokens the key has in common with the
+            // previous one
+            std::size_t depth = 0;
+            if (previous != nullptr)
             {
-                id = tree.parent[id];
-                prefixes[i - 1] = id;
+                const std::size_t same = common_prefix_length(data, previous->data(), (std::min)(key.size(), previous->size()));
+                depth = ends.size() - 1;
+                while (depth > 0 && (ends[depth] > same || (ends[depth] == same && same < key.size() && data[same] != '/')))
+                {
+                    --depth;
+                }
             }
-            ++key_index;
+            values.resize(depth + 1);
+            ends.resize(depth + 1);
+            previous = &key;
 
             // Assign the value to the reference pointed to by JSON pointer. Note
             // 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.
-            get_and_create(result, tokens, prefixes, tree) = element.second;
+            // the value is the result itself. An assignment will then create a
+            // primitive value.
+            BasicJsonType* current = values.back();
+            for (std::size_t pos = ends.back(); pos < key.size();)
+            {
+                // the reference token between the slash at pos and the next
+                std::size_t end = key.find_first_of('/', pos + 1);
+                if (end == string_t::npos)
+                {
+                    end = key.size();
+                }
+                token.clear();
+                token.append(data + pos + 1, end - pos - 1);
+                if (token.find_first_of('~') != string_t::npos)
+                {
+                    detail::unescape(token);
+                }
+
+                switch (current->type())
+                {
+                    case detail::value_t::null:
+                    {
+                        if (arrays.contains(data, pos))
+                        {
+                            // some reference token below this position is 0, so the
+                            // value is an array
+                            current = &current->operator[](array_index<BasicJsonType>(token));
+                        }
+                        else
+                        {
+                            // start a new object otherwise
+                            current = &current->operator[](token);
+                        }
+                        break;
+                    }
+
+                    case detail::value_t::object:
+                    {
+                        // create an entry in the object
+                        current = &object_member(*current, token);
+                        break;
+                    }
+
+                    case detail::value_t::array:
+                    {
+                        // create an entry in the array
+                        current = &current->operator[](array_index<BasicJsonType>(token));
+                        break;
+                    }
+
+                    /*
+                    The following code is only reached if there exists a reference
+                    token _and_ the current value is primitive. In this case, we have
+                    an error situation, because primitive values may only occur as
+                    a single value; that is, with an empty list of reference tokens.
+                    */
+                    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:
+                        JSON_THROW(detail::type_error::create(detail::exception_id::unflatten_invalid_value, "invalid value to unflatten", &result));
+                }
+
+                values.push_back(current);
+                ends.push_back(end);
+                pos = end;
+            }
+
+            *current = element.second;
         }
 
         return result;

include/nlohmann/json.hpp

@@ -7066,6 +7066,125 @@ public:
             detail::throw_patch_not_an_array(json_patch);
         }
 
+        // the usual patch operations "add", "remove", "replace" and "test" on
+        // a pointer without escapes that denotes existing array elements and
+        // object members (as "add" does for the parent of the new value), as
+        // a diff creates them: apply the operation and return true; return
+        // false, with nothing changed, for all others
+        string_t token;
+        const string_t value_key = "value";
+        const auto try_plain = [&result, &token, &value_key](patch_operations operation, const string_t& path, const basic_json & val)
+        {
+            if (path.empty() || path.find_first_of('~') != string_t::npos)
+            {
+                return false;
+            }
+
+            // a missing "value" is reported below
+            const auto value_it = val.m_data.m_value.object->find(value_key);
+            const basic_json& value = value_it != val.m_data.m_value.object->end() ? value_it->second : val;
+            if (operation != patch_operations::remove && value_it == val.m_data.m_value.object->end())
+            {
+                return false;
+            }
+
+            switch (operation)
+            {
+                case patch_operations::replace:
+                {
+                    basic_json* const target = json_pointer::resolve_plain(&result, path, path.size(), token);
+                    if (target == nullptr)
+                    {
+                        return false;
+                    }
+                    *target = value;
+                    return true;
+                }
+
+                case patch_operations::test:
+                {
+                    const basic_json* const target = json_pointer::resolve_plain(&result, path, path.size(), token);
+                    // a failing test is reported below
+                    return target != nullptr && *target == value;
+                }
+
+                case patch_operations::add:
+                case patch_operations::remove:
+                {
+                    // the parent of the pointer and its last reference token
+                    std::size_t slash = path.size();
+                    while (slash > 0 && path[slash - 1] != '/')
+                    {
+                        --slash;
+                    }
+                    if (slash == 0)
+                    {
+                        return false;
+                    }
+                    --slash;
+
+                    basic_json* const parent = json_pointer::resolve_plain(&result, path, slash, token);
+                    if (parent == nullptr)
+                    {
+                        return false;
+                    }
+                    token.clear();
+                    token.append(path.data() + slash + 1, path.size() - slash - 1);
+
+                    if (operation == patch_operations::add)
+                    {
+                        if (parent->is_object())
+                        {
+                            (*parent)[token] = value;
+                            return true;
+                        }
+                        if (parent->is_array())
+                        {
+                            typename basic_json::size_type idx{};
+                            if (token == "-")
+                            {
+                                parent->push_back(value);
+                                return true;
+                            }
+                            if (json_pointer::template parse_array_index<basic_json_t>(token, idx) == json_pointer::array_index_status::ok && idx <= parent->size())
+                            {
+                                parent->insert(parent->begin() + static_cast<difference_type>(idx), value);
+                                return true;
+                            }
+                        }
+                        return false;
+                    }
+
+                    if (parent->is_object())
+                    {
+                        const auto it = parent->find(token);
+                        if (it == parent->end())
+                        {
+                            return false;
+                        }
+                        parent->erase(it);
+                        return true;
+                    }
+                    if (parent->is_array())
+                    {
+                        typename basic_json::size_type idx{};
+                        if (json_pointer::template parse_array_index<basic_json_t>(token, idx) == json_pointer::array_index_status::ok && idx < parent->size())
+                        {
+                            parent->erase(idx);
+                            return true;
+                        }
+                    }
+                    return false;
+                }
+
+                case patch_operations::move:
+                case patch_operations::copy:
+                case patch_operations::invalid:
+                default:
+                    return false;
+            }
+        };
+
         // iterate and apply the operations
         for (const auto& val : json_patch)
         {
@@ -7102,9 +7221,19 @@ public:
             // collect mandatory members
             const string_t& op = *get_value("op", "op", true).m_data.m_value.string;
             const string_t& path = *get_value(op, "path", true).m_data.m_value.string;
+            const patch_operations operation = get_op(op);
+
+            // the usual operations on a plain pointer are applied without
+            // building the pointer's reference tokens; anything else (and
+            // every error) is handled below
+            if (try_plain(operation, path, val))
+            {
+                continue;
+            }
+
             json_pointer ptr(path);
 
-            switch (get_op(op))
+            switch (operation)
             {
                 case patch_operations::add:
                 {
@@ -7212,7 +7341,8 @@ public:
     {
         // the patch
         basic_json result(value_t::array);
-        diff_recursively(result, source, target, path, 0);
+        string_t buffer = path;
+        diff_recursively(result, source, target, buffer, 0);
         return result;
     }
 
@@ -7256,31 +7386,69 @@ public:
     // function it appears in. In diff_recursively, which is on the call stack
     // once per nesting level, that made every level cost kilobytes of stack.
 
+    /// @brief append an operation @a op for @a path to @a result, with @a value if it is not null
+    static void diff_operation(basic_json& result, const char* op, const string_t& path, const basic_json* value)
+    {
+        basic_json entry(value_t::object);
+        entry["op"] = op;
+        entry["path"] = path;
+        if (value != nullptr)
+        {
+            entry["value"] = *value;
+        }
+        result.push_back(std::move(entry));
+    }
+
     /// @brief append a "replace" operation for @a path with @a value to @a result
     static void diff_replace(basic_json& result, const string_t& path, const basic_json& value)
     {
-        result.push_back(
-        {
-            {"op", "replace"}, {"path", path}, {"value", value}
-        });
+        diff_operation(result, "replace", path, &value);
     }
 
     /// @brief append a "remove" operation for @a path to @a result
     static void diff_remove(basic_json& result, const string_t& path)
     {
-        result.push_back(object(
-        {
-            {"op", "remove"}, {"path", path}
-        }));
+        diff_operation(result, "remove", path, nullptr);
     }
 
     /// @brief append an "add" operation for @a path with @a value to @a result
     static void diff_add(basic_json& result, const string_t& path, const basic_json& value)
     {
-        result.push_back(
-        {
-            {"op", "add"}, {"path", path}, {"value", value}
-        });
+        diff_operation(result, "add", path, &value);
+    }
+
+    /// @brief append "/" and the decimal representation of @a index to @a path
+    static void diff_append_index(string_t& path, std::size_t index)
+    {
+        path.push_back('/');
+        json_pointer::append_index(path, index);
+    }
+
+    /// @brief append "/" and the escaped @a key to @a path
+    static void diff_append_key(string_t& path, const string_t& key)
+    {
+        path.push_back('/');
+        detail::escape_into(path, key);
+    }
+
+    /// @brief the path of the member @a key of the value at @a path
+    static string_t diff_key_path(const string_t& path, const string_t& key)
+    {
+        string_t result;
+        result.reserve(path.size() + key.size() + 1);
+        result.append(path.data(), path.size());
+        diff_append_key(result, key);
+        return result;
+    }
+
+    /// @brief the path of the element @a index of the value at @a path
+    static string_t diff_index_path(const string_t& path, const std::size_t index)
+    {
+        string_t result;
+        result.reserve(path.size() + 8);
+        result.append(path.data(), path.size());
+        diff_append_index(result, index);
+        return result;
     }
 
     /// @brief append the "remove" operations for the elements of array
@@ -7293,13 +7461,18 @@ public:
         // in that order avoids the quadratic reinsertion done before
         for (std::size_t j = source.size(); j > index; --j)
         {
-            diff_remove(result, detail::concat<string_t>(path, '/', detail::to_string<string_t>(j - 1)));
+            diff_remove(result, diff_index_path(path, j - 1));
         }
 
         // add other remaining elements
-        for (std::size_t i = source.size(); i < target.size(); ++i)
+        if (source.size() < target.size())
         {
-            diff_add(result, detail::concat<string_t>(path, "/-"), target[i]);
+            string_t tail_path = path;
+            tail_path.append("/-", 2);
+            for (std::size_t i = source.size(); i < target.size(); ++i)
+            {
+                diff_add(result, tail_path, target[i]);
+            }
         }
     }
 
@@ -7308,7 +7481,7 @@ public:
     {
         for (const auto& it : added)
         {
-            diff_add(result, detail::concat<string_t>(path, '/', detail::escape(it.key())), it.value());
+            diff_add(result, diff_key_path(path, it.key()), it.value());
         }
     }
 
@@ -7329,10 +7502,25 @@ public:
                                  std::vector<const_iterator>& added)
     {
         // first pass: one lookup per source key
+        // Objects of the same size usually have the same keys, in the same
+        // order: walk them together as long as that holds, which takes no lookups.
         target_values.reserve(source.size());
         std::size_t common = 0;
-        for (auto it = source.cbegin(); it != source.cend(); ++it)
+        bool together = source.size() == target.size();
+        for (auto it = source.cbegin(), partner = target.cbegin(); it != source.cend(); ++it)
         {
+            if (together)
+            {
+                if (it.key() == partner.key())
+                {
+                    target_values.push_back(&partner.value());
+                    ++common;
+                    ++partner;
+                    continue;
+                }
+                together = false;
+            }
+
             const auto found = target.find(it.key());
             if (found != target.cend())
             {
@@ -7345,6 +7533,12 @@ public:
             }
         }
 
+        // the same keys in the same order
+        if (together)
+        {
+            return true;
+        }
+
         // second pass: find the keys only target has. An object type that
         // keeps its members in insertion order, such as the one backing
         // ordered_json, also needs the common keys to be in the same order
@@ -7410,6 +7604,13 @@ public:
             return true;
         }
 
+        // equal objects, whose members are in a different order, need no
+        // operations
+        if (source == target)
+        {
+            return false;
+        }
+
         // slow path: the common keys are in a different relative
         // order in source and target (only possible for a
         // reorderable object_t like ordered_map). Building a
@@ -7426,7 +7627,7 @@ public:
         // it moves it to the end, fixing its position.
         for (auto it = source.cbegin(); it != source.cend(); ++it)
         {
-            diff_remove(result, detail::concat<string_t>(path, '/', detail::escape(it.key())));
+            diff_remove(result, diff_key_path(path, it.key()));
         }
 
         // add every key that is either common (just removed
@@ -7435,7 +7636,7 @@ public:
         // target exactly
         for (auto it = target.cbegin(); it != target.cend(); ++it)
         {
-            diff_add(result, detail::concat<string_t>(path, '/', detail::escape(it.key())), it.value());
+            diff_add(result, diff_key_path(path, it.key()), it.value());
         }
         return false;
     }
@@ -7444,6 +7645,9 @@ public:
     @brief @ref diff, for values at nesting level @a depth, appending the
            operations to @a result
 
+    @a path is the path of the values; it is a buffer that is extended and
+    shortened again below, and is the same when the function returns.
+
     Diffing two arrays or objects calls this function again, once per nesting
     level, so values nested deeply enough used to exhaust the call stack and
     terminate the process. The descent is bounded here: once @ref
@@ -7451,7 +7655,7 @@ public:
     diff_iteratively diffs what is left without the call stack.
     */
     static void diff_recursively(basic_json& result, const basic_json& source, const basic_json& target,
-                                 const string_t& path, const std::size_t depth)
+                                 string_t& path, const std::size_t depth)
     {
         // if the values are the same, there is nothing to do
         if (source == target)
@@ -7463,9 +7667,9 @@ public:
     }
 
     /// @brief @ref diff_recursively for values known to be unequal; callers
-    ///        compare first so they build no path for equal ones
+    ///        compare first so they extend the path only for unequal ones
     static void diff_unequal(basic_json& result, const basic_json& source, const basic_json& target,
-                             const string_t& path, const std::size_t depth)
+                             string_t& path, const std::size_t depth)
     {
         if (JSON_HEDLEY_UNLIKELY(depth >= detail::recursion_depth_limit()))
         {
@@ -7484,6 +7688,8 @@ public:
         {
             case value_t::array:
             {
+                const std::size_t path_length = path.size();
+
                 // first pass: traverse common elements
                 std::size_t i = 0;
                 while (i < source.size() && i < target.size())
@@ -7491,7 +7697,9 @@ public:
                     // recursive call to compare array values at index i
                     if (!(source[i] == target[i]))
                     {
-                        diff_unequal(result, source[i], target[i], detail::concat<string_t>(path, '/', detail::to_string<string_t>(i)), depth + 1);
+                        diff_append_index(path, i);
+                        diff_unequal(result, source[i], target[i], path, depth + 1);
+                        path.resize(path_length);
                     }
                     ++i;
                 }
@@ -7513,6 +7721,7 @@ public:
                     // lookup is needed. Deleted keys are interleaved here
                     // too, in source's original order, to match the
                     // historical (pre-reordering-aware) output order.
+                    const std::size_t path_length = path.size();
                     std::size_t i = 0;
                     for (auto it = source.cbegin(); it != source.cend(); ++it, ++i)
                     {
@@ -7520,13 +7729,15 @@ public:
                         {
                             if (!(it.value() == *target_values[i]))
                             {
-                                diff_unequal(result, it.value(), *target_values[i], detail::concat<string_t>(path, '/', detail::escape(it.key())), depth + 1);
+                                diff_append_key(path, it.key());
+                                diff_unequal(result, it.value(), *target_values[i], path, depth + 1);
+                                path.resize(path_length);
                             }
                         }
                         else
                         {
                             // found a key that is not in target -> remove it
-                            diff_remove(result, detail::concat<string_t>(path, '/', detail::escape(it.key())));
+                            diff_remove(result, diff_key_path(path, it.key()));
                         }
                     }
 
@@ -7657,7 +7868,7 @@ public:
                 if (i < source_array.size() && i < target_array.size())
                 {
                     ++stack.back().index;
-                    detail::concat_into(current_path, '/', detail::to_string<string_t>(i));
+                    diff_append_index(current_path, i);
                     enter(source_array[i], target_array[i]);
                     if (stack.size() == depth)
                     {
@@ -7680,7 +7891,7 @@ public:
                     if (target_value_ptr != nullptr)
                     {
                         const basic_json& target_value = *target_value_ptr;
-                        detail::concat_into(current_path, '/', detail::escape(it.key()));
+                        diff_append_key(current_path, it.key());
                         enter(it.value(), target_value);
                         if (stack.size() == depth)
                         {
@@ -7690,7 +7901,7 @@ public:
                     else
                     {
                         // found a key that is not in target -> remove it
-                        diff_remove(result, detail::concat<string_t>(current_path, '/', detail::escape(it.key())));
+                        diff_remove(result, diff_key_path(current_path, it.key()));
                     }
                     continue;
                 }

tests/CMakeLists.txt

@@ -118,7 +118,7 @@ endif()
 
 if (CMAKE_CXX_COMPILER_ID STREQUAL "MSVC")
     # avoid stack overflow, see https://github.com/nlohmann/json/issues/2955
-    json_test_set_test_options("test-bon8;test-cbor;test-msgpack;test-ubjson;test-bjdata;test-binary_formats" LINK_OPTIONS /STACK:4000000)
+    json_test_set_test_options("test-bon8;test-cbor;test-msgpack;test-ubjson;test-bjdata;test-bjdata_round_trip_draft2;test-bjdata_round_trip_draft3;test-binary_formats" LINK_OPTIONS /STACK:4000000)
 endif()
 
 # disable exceptions for test-disabled_exceptions

tests/src/bjdata_round_trip.hpp

@@ -0,0 +1,103 @@
+//     __ _____ _____ _____
+//  __|  |   __|     |   | |  JSON for Modern C++ (supporting code)
+// |  |  |__   |  |  | | | |  version 3.12.0
+// |_____|_____|_____|_|___|  https://github.com/nlohmann/json
+//
+// SPDX-FileCopyrightText: 2013-2026 Niels Lohmann <https://nlohmann.me>
+// SPDX-License-Identifier: MIT
+
+#pragma once
+
+#include <cstdint> // uint8_t
+#include <vector> // vector
+
+#include "doctest_compatibility.h"
+
+#include <nlohmann/json.hpp>
+
+#include "round_trip_corpus.hpp"
+
+// The BJData round-trip invariants, split by the BJData version that turns a
+// corpus value into j1 (unit-bjdata_round_trip_draft2.cpp and
+// unit-bjdata_round_trip_draft3.cpp). They were part of unit-bjdata.cpp, but
+// took 80 % of its time; as separate tests, both halves run in parallel and
+// stay below the ctest timeout under Valgrind.
+namespace utils
+{
+
+// This checks what the parse_bjdata_fuzzer driver checks (see
+// tests/src/fuzzer-parse_bjdata.cpp), so that a regression shows up in CI
+// rather than as an OSS-Fuzz report: every value from_bjdata() returns
+// (j1) can be serialized with any combination of options, the result can
+// be parsed back (j2), and serializing j2 again with the same options
+// yields a value-equal result.
+//
+// Beyond the driver, this also checks that j2 equals j1 and that
+// serializing j2 reproduces the exact bytes, both except for values that
+// contain a binary value: a binary value is only written as a binary
+// value with Draft 3's optimized binary array, and otherwise read back as
+// an array of integers, for which the writer may choose different (but
+// equally valid) type markers when it is serialized again (see #5494).
+//
+// Values are compared with dump() rather than operator==, because a NaN
+// never compares equal to itself.
+//
+// Only the corpus values written with @a initial_version become j1; each j1
+// is then serialized with every combination of options, both versions
+// included.
+inline void check_bjdata_round_trip(const nlohmann::json::bjdata_version_t initial_version)
+{
+    using nlohmann::json;
+
+    struct options
+    {
+        bool use_size;
+        bool use_type;
+        json::bjdata_version_t version;
+    };
+    const std::vector<options> all_options =
+    {
+        {false, false, json::bjdata_version_t::draft2},
+        {true, false, json::bjdata_version_t::draft2},
+        {true, true, json::bjdata_version_t::draft2},
+        {false, false, json::bjdata_version_t::draft3},
+        {true, false, json::bjdata_version_t::draft3},
+        {true, true, json::bjdata_version_t::draft3},
+    };
+
+    for (const auto& j0 : utils::round_trip_corpus::values())
+    {
+        // turn the corpus value into a value as from_bjdata() returns it
+        for (const auto& initial : all_options)
+        {
+            if (initial.version != initial_version)
+            {
+                continue;
+            }
+
+            const json j1 = json::from_bjdata(json::to_bjdata(j0, initial.use_size, initial.use_type, initial.version));
+            const bool has_binary = utils::round_trip_corpus::contains_binary(j1);
+
+            for (const auto& o : all_options)
+            {
+                INFO("j1 = " << j1.dump() << ", use_size = " << o.use_size << ", use_type = " << o.use_type
+                     << ", draft3 = " << (o.version == json::bjdata_version_t::draft3));
+
+                const std::vector<std::uint8_t> vec = json::to_bjdata(j1, o.use_size, o.use_type, o.version);
+                json j2;
+                // anything the library writes must be parsable by the library
+                REQUIRE_NOTHROW(j2 = json::from_bjdata(vec));
+                const std::vector<std::uint8_t> vec2 = json::to_bjdata(j2, o.use_size, o.use_type, o.version);
+                CHECK(json::from_bjdata(vec2).dump() == j2.dump());
+
+                if (!has_binary)
+                {
+                    CHECK(j2.dump() == j1.dump());
+                    CHECK(vec2 == vec);
+                }
+            }
+        }
+    }
+}
+
+} // namespace utils

tests/src/unit-bjdata.cpp

@@ -28,7 +28,6 @@ using ordered_json = nlohmann::ordered_json;
 #include <fstream>
 #include <set>
 #include "make_test_data_available.hpp"
-#include "round_trip_corpus.hpp"
 #include "test_utils.hpp"
 #include "sax_countdown.hpp"
 using utils::SaxCountdown;
@@ -4441,70 +4440,6 @@ TEST_CASE("BJData use_type requires use_size")
     }
 }
 
-TEST_CASE("BJData round-trip invariants")
-{
-    // This checks what the parse_bjdata_fuzzer driver checks (see
-    // tests/src/fuzzer-parse_bjdata.cpp), so that a regression shows up in CI
-    // rather than as an OSS-Fuzz report: every value from_bjdata() returns
-    // (j1) can be serialized with any combination of options, the result can
-    // be parsed back (j2), and serializing j2 again with the same options
-    // yields a value-equal result.
-    //
-    // Beyond the driver, this also checks that j2 equals j1 and that
-    // serializing j2 reproduces the exact bytes, both except for values that
-    // contain a binary value: a binary value is only written as a binary
-    // value with Draft 3's optimized binary array, and otherwise read back as
-    // an array of integers, for which the writer may choose different (but
-    // equally valid) type markers when it is serialized again (see #5494).
-    //
-    // Values are compared with dump() rather than operator==, because a NaN
-    // never compares equal to itself.
-    struct options
-    {
-        bool use_size;
-        bool use_type;
-        json::bjdata_version_t version;
-    };
-    const std::vector<options> all_options =
-    {
-        {false, false, json::bjdata_version_t::draft2},
-        {true, false, json::bjdata_version_t::draft2},
-        {true, true, json::bjdata_version_t::draft2},
-        {false, false, json::bjdata_version_t::draft3},
-        {true, false, json::bjdata_version_t::draft3},
-        {true, true, json::bjdata_version_t::draft3},
-    };
-
-    for (const auto& j0 : utils::round_trip_corpus::values())
-    {
-        // turn the corpus value into a value as from_bjdata() returns it
-        for (const auto& initial : all_options)
-        {
-            const json j1 = json::from_bjdata(json::to_bjdata(j0, initial.use_size, initial.use_type, initial.version));
-            const bool has_binary = utils::round_trip_corpus::contains_binary(j1);
-
-            for (const auto& o : all_options)
-            {
-                INFO("j1 = " << j1.dump() << ", use_size = " << o.use_size << ", use_type = " << o.use_type
-                     << ", draft3 = " << (o.version == json::bjdata_version_t::draft3));
-
-                const std::vector<std::uint8_t> vec = json::to_bjdata(j1, o.use_size, o.use_type, o.version);
-                json j2;
-                // anything the library writes must be parsable by the library
-                REQUIRE_NOTHROW(j2 = json::from_bjdata(vec));
-                const std::vector<std::uint8_t> vec2 = json::to_bjdata(j2, o.use_size, o.use_type, o.version);
-                CHECK(json::from_bjdata(vec2).dump() == j2.dump());
-
-                if (!has_binary)
-                {
-                    CHECK(j2.dump() == j1.dump());
-                    CHECK(vec2 == vec);
-                }
-            }
-        }
-    }
-}
-
 TEST_CASE("BJData round trip of a binary value is value-stable, not byte-stable")
 {
     // OSS-Fuzz issue 474480402: a Draft 3 optimized binary array is read as a

tests/src/unit-bjdata_round_trip_draft2.cpp

@@ -0,0 +1,22 @@
+//     __ _____ _____ _____
+//  __|  |   __|     |   | |  JSON for Modern C++ (supporting code)
+// |  |  |__   |  |  | | | |  version 3.12.0
+// |_____|_____|_____|_|___|  https://github.com/nlohmann/json
+//
+// SPDX-FileCopyrightText: 2013-2026 Niels Lohmann <https://nlohmann.me>
+// SPDX-License-Identifier: MIT
+
+#include "doctest_compatibility.h"
+
+#include <nlohmann/json.hpp>
+using nlohmann::json;
+
+#include "bjdata_round_trip.hpp"
+
+// split from unit-bjdata.cpp, see bjdata_round_trip.hpp; the other half is in
+// unit-bjdata_round_trip_draft3.cpp
+
+TEST_CASE("BJData round-trip invariants (j1 written with Draft 2)")
+{
+    utils::check_bjdata_round_trip(json::bjdata_version_t::draft2);
+}

tests/src/unit-bjdata_round_trip_draft3.cpp

@@ -0,0 +1,22 @@
+//     __ _____ _____ _____
+//  __|  |   __|     |   | |  JSON for Modern C++ (supporting code)
+// |  |  |__   |  |  | | | |  version 3.12.0
+// |_____|_____|_____|_|___|  https://github.com/nlohmann/json
+//
+// SPDX-FileCopyrightText: 2013-2026 Niels Lohmann <https://nlohmann.me>
+// SPDX-License-Identifier: MIT
+
+#include "doctest_compatibility.h"
+
+#include <nlohmann/json.hpp>
+using nlohmann::json;
+
+#include "bjdata_round_trip.hpp"
+
+// split from unit-bjdata.cpp, see bjdata_round_trip.hpp; the other half is in
+// unit-bjdata_round_trip_draft2.cpp
+
+TEST_CASE("BJData round-trip invariants (j1 written with Draft 3)")
+{
+    utils::check_bjdata_round_trip(json::bjdata_version_t::draft3);
+}

tests/src/unit-large_json.cpp

@@ -13,8 +13,6 @@ using nlohmann::json;
 
 #include <algorithm>
 #include <string>
-#include <utility>
-#include <vector>
 
 TEST_CASE("tests on very large JSONs")
 {
@@ -55,24 +53,6 @@ const json* innermost_value(const json& j, std::size_t& depth)
     return current;
 }
 
-// The text of a value nested depth levels deep around the number 0. Level i is
-// an array if pattern[i % pattern.size()] is '[', and otherwise an object with
-// the single member "a", which every object type enumerates in the same order.
-std::string nested_text(std::size_t depth, const std::string& pattern)
-{
-    std::string text;
-    std::string closing;
-    for (std::size_t i = 0; i < depth; ++i)
-    {
-        const bool array = pattern[i % pattern.size()] == '[';
-        text += array ? "[" : "{\"a\":";
-        closing += array ? ']' : '}';
-    }
-    text += '0';
-    text.append(closing.rbegin(), closing.rend());
-    return text;
-}
-
 } // namespace
 
 TEST_CASE("tests on deeply nested JSONs")
@@ -244,385 +224,4 @@ TEST_CASE("tests on deeply nested JSONs")
             CHECK(*innermost_value(j, unused) == 0);
         }
     }
-
-    SECTION("issue #5650 - stack overflow converting between specializations")
-    {
-        const std::vector<std::string> patterns = {"[", "{", "[{"};
-
-        SECTION("json to ordered_json")
-        {
-            for (const auto& pattern : patterns)
-            {
-                CAPTURE(pattern)
-                const std::string text = nested_text(depth, pattern);
-                const json j = json::parse(text);
-
-                const nlohmann::ordered_json converted = j;
-                CHECK(converted.dump() == text);
-            }
-        }
-
-        SECTION("ordered_json to json")
-        {
-            for (const auto& pattern : patterns)
-            {
-                CAPTURE(pattern)
-                const std::string text = nested_text(depth, pattern);
-                const nlohmann::ordered_json o = nlohmann::ordered_json::parse(text);
-
-                const json converted = o;
-                CHECK(converted.dump() == text);
-            }
-        }
-
-        SECTION("get<ordered_json>()")
-        {
-            for (const auto& pattern : patterns)
-            {
-                CAPTURE(pattern)
-                const std::string text = nested_text(depth, pattern);
-                const json j = json::parse(text);
-
-                CHECK(j.get<nlohmann::ordered_json>().dump() == text);
-            }
-        }
-
-        SECTION("depths around the bound of the recursive descent")
-        {
-            for (std::size_t d = 1; d <= 300; ++d)
-            {
-                CAPTURE(d)
-                for (const auto& pattern : patterns)
-                {
-                    CAPTURE(pattern)
-                    const std::string text = nested_text(d, pattern);
-                    const json j = json::parse(text);
-
-                    const nlohmann::ordered_json converted = j;
-                    CHECK(converted.dump() == text);
-                    const json back = converted;
-                    CHECK(back.dump() == text);
-                }
-            }
-        }
-
-        SECTION("values below the bound are converted as values above it")
-        {
-            // Bury a value below the bound, where it is converted without the
-            // call stack, and compare it with the same value converted on its
-            // own by the containers' range constructors. Its objects have
-            // members that the two object types enumerate in different orders.
-            const auto bury = [](nlohmann::ordered_json value)
-            {
-                for (std::size_t i = 0; i < 200; ++i)
-                {
-                    value = nlohmann::ordered_json::array({std::move(value)});
-                }
-                return value;
-            };
-            const auto dig = [](const json & value)
-            {
-                const json* current = &value;
-                for (std::size_t i = 0; i < 200; ++i)
-                {
-                    current = &current->at(0);
-                }
-                return current;
-            };
-
-            nlohmann::ordered_json value = nlohmann::ordered_json::object();
-            value["z"] = {1, -2, 3U, 4.5, true, nullptr, "six", nlohmann::ordered_json::binary({7, 8}, 9),
-                          nlohmann::ordered_json::binary({10}), nlohmann::ordered_json::array(), nlohmann::ordered_json::object()
-                         };
-            value["y"] = {{"x", {{"w", 1}, {"v", 2}}}, {"u", {3, {{"t", 4}, {"s", 5}}}}};
-            value["r"] = nlohmann::ordered_json::array({nlohmann::ordered_json(nlohmann::ordered_json::value_t::discarded)});
-
-            const json converted_above = value;
-            const json buried = bury(value);
-            const json& converted_below = *dig(buried);
-
-            CHECK(converted_below.dump() == converted_above.dump());
-            CHECK(converted_below.at("z").at(7).get_binary().subtype() == 9);
-            CHECK_FALSE(converted_below.at("z").at(8).get_binary().has_subtype());
-            CHECK(converted_below.at("r").at(0).is_discarded());
-
-            // a discarded value is never equal to anything, so compare the rest
-            value.erase("r");
-            const json without_discarded_above = value;
-            const json without_discarded_buried = bury(value);
-            CHECK(*dig(without_discarded_buried) == without_discarded_above);
-        }
-    }
 }
-
-namespace
-{
-json nested_array(const std::size_t depth, json leaf)
-{
-    json j = std::move(leaf);
-    for (std::size_t i = 0; i < depth; ++i)
-    {
-        json a = json::array();
-        a.push_back(std::move(j));
-        j = std::move(a);
-    }
-    return j;
-}
-
-json nested_object(const std::size_t depth, json leaf)
-{
-    json j = std::move(leaf);
-    for (std::size_t i = 0; i < depth; ++i)
-    {
-        json o = json::object();
-        o["k"] = std::move(j);
-        j = std::move(o);
-    }
-    return j;
-}
-} // namespace
-
-TEST_CASE("issue #5392 - binary writers on deeply nested values")
-{
-    // 200 is past the point where the writers stop recursing, and still
-    // shallow enough that from_* and operator== (which still recurse) are fine.
-    const json deep_array = nested_array(200, json(0));
-    const json deep_object = nested_object(200, json("x"));
-    const json empty_array = nested_array(200, json::array());
-    const json empty_object = nested_object(200, json::object());
-    const json mixed = nested_object(80, nested_array(80, json(true)));
-
-    SECTION("roundtrip past the recursion bound")
-    {
-        CHECK(json::from_cbor(json::to_cbor(deep_array)) == deep_array);
-        CHECK(json::from_msgpack(json::to_msgpack(deep_array)) == deep_array);
-        CHECK(json::from_ubjson(json::to_ubjson(deep_array)) == deep_array);
-        CHECK(json::from_ubjson(json::to_ubjson(deep_array, true, false)) == deep_array);
-        CHECK(json::from_ubjson(json::to_ubjson(deep_array, true, true)) == deep_array);
-        CHECK(json::from_bjdata(json::to_bjdata(deep_array)) == deep_array);
-        CHECK(json::from_bon8(json::to_bon8(deep_array)) == deep_array);
-
-        CHECK(json::from_cbor(json::to_cbor(deep_object)) == deep_object);
-        CHECK(json::from_msgpack(json::to_msgpack(deep_object)) == deep_object);
-        CHECK(json::from_ubjson(json::to_ubjson(deep_object)) == deep_object);
-        CHECK(json::from_ubjson(json::to_ubjson(deep_object, true, true)) == deep_object);
-        CHECK(json::from_bjdata(json::to_bjdata(deep_object)) == deep_object);
-        CHECK(json::from_bon8(json::to_bon8(deep_object)) == deep_object);
-
-        CHECK(json::from_cbor(json::to_cbor(empty_array)) == empty_array);
-        CHECK(json::from_msgpack(json::to_msgpack(empty_array)) == empty_array);
-        CHECK(json::from_ubjson(json::to_ubjson(empty_array)) == empty_array);
-        CHECK(json::from_ubjson(json::to_ubjson(empty_array, true, true)) == empty_array);
-        CHECK(json::from_bon8(json::to_bon8(empty_array)) == empty_array);
-
-        CHECK(json::from_cbor(json::to_cbor(empty_object)) == empty_object);
-        CHECK(json::from_msgpack(json::to_msgpack(empty_object)) == empty_object);
-        CHECK(json::from_ubjson(json::to_ubjson(empty_object)) == empty_object);
-        CHECK(json::from_bon8(json::to_bon8(empty_object)) == empty_object);
-
-        CHECK(json::from_cbor(json::to_cbor(mixed)) == mixed);
-        CHECK(json::from_msgpack(json::to_msgpack(mixed)) == mixed);
-        CHECK(json::from_ubjson(json::to_ubjson(mixed)) == mixed);
-        CHECK(json::from_bjdata(json::to_bjdata(mixed)) == mixed);
-        CHECK(json::from_bon8(json::to_bon8(mixed)) == mixed);
-    }
-
-    SECTION("the two ways of writing a value meet at the bound")
-    {
-        for (std::size_t depth = 120; depth <= 140; ++depth)
-        {
-            CAPTURE(depth)
-
-            const json array = nested_array(depth, json(7));
-            CHECK(json::from_cbor(json::to_cbor(array)) == array);
-            CHECK(json::from_msgpack(json::to_msgpack(array)) == array);
-            CHECK(json::from_ubjson(json::to_ubjson(array, true, true)) == array);
-            CHECK(json::from_bon8(json::to_bon8(array)) == array);
-
-            const json object = nested_object(depth, json(7));
-            CHECK(json::from_cbor(json::to_cbor(object)) == object);
-            CHECK(json::from_msgpack(json::to_msgpack(object)) == object);
-            CHECK(json::from_bjdata(json::to_bjdata(object)) == object);
-            CHECK(json::from_bon8(json::to_bon8(object)) == object);
-        }
-    }
-
-    SECTION("a BJData ndarray below the bound is still an ndarray")
-    {
-        const json ndarray = json({{"_ArrayType_", "uint8"}, {"_ArraySize_", {2, 3}}, {"_ArrayData_", {1, 2, 3, 4, 5, 6}}});
-        const json invalid = json({{"_ArrayType_", "nope"}, {"_ArraySize_", {1}}, {"_ArrayData_", {1}}});
-
-        const json deep_ndarray = nested_array(140, ndarray);
-        const json deep_invalid = nested_array(140, invalid);
-
-        CHECK(json::from_bjdata(json::to_bjdata(deep_ndarray)) == deep_ndarray);
-        CHECK(json::from_bjdata(json::to_bjdata(deep_invalid)) == deep_invalid);
-        CHECK(json::from_bjdata(json::to_bjdata(ndarray)) == ndarray);
-    }
-
-    SECTION("byte-exact across the switch-over")
-    {
-        // nested one-element arrays around the recursion bound: the exact
-        // bytes a writer produces do not depend on whether it stayed on the
-        // call stack or moved to the heap one partway through
-        for (const std::size_t depth :
-                {
-                    nlohmann::detail::recursion_depth_limit() - 1, nlohmann::detail::recursion_depth_limit(),
-                    nlohmann::detail::recursion_depth_limit() + 1, nlohmann::detail::recursion_depth_limit() + 2
-                })
-        {
-            CAPTURE(depth)
-            const json array = nested_array(depth, json(0));
-
-            std::vector<std::uint8_t> expected_cbor(depth, 0x81);
-            expected_cbor.push_back(0x00);
-            CHECK(json::to_cbor(array) == expected_cbor);
-
-            std::vector<std::uint8_t> expected_msgpack(depth, 0x91);
-            expected_msgpack.push_back(0x00);
-            CHECK(json::to_msgpack(array) == expected_msgpack);
-
-            std::string expected_ubjson(depth, '[');
-            expected_ubjson += "i";
-            expected_ubjson += '\0';
-            expected_ubjson.append(depth, ']');
-            const auto packed_ubjson = json::to_ubjson(array);
-            CHECK(std::string(packed_ubjson.begin(), packed_ubjson.end()) == expected_ubjson);
-
-            std::vector<std::uint8_t> expected_bon8(depth, 0x81);
-            expected_bon8.push_back(0x90);
-            CHECK(json::to_bon8(array) == expected_bon8);
-        }
-    }
-
-    SECTION("a deep object, and a BJData ndarray, past the recursion bound")
-    {
-        const std::size_t depth = nlohmann::detail::recursion_depth_limit() + 50;
-
-        const json object = nested_object(depth, json(42));
-        CHECK(json::from_cbor(json::to_cbor(object)) == object);
-        CHECK(json::from_msgpack(json::to_msgpack(object)) == object);
-        CHECK(json::from_ubjson(json::to_ubjson(object, true, true)) == object);
-        CHECK(json::from_bjdata(json::to_bjdata(object)) == object);
-        CHECK(json::from_bon8(json::to_bon8(object)) == object);
-
-        const json ndarray = json({{"_ArrayType_", "uint8"}, {"_ArraySize_", {2, 3}}, {"_ArrayData_", {1, 2, 3, 4, 5, 6}}});
-        const json deep_ndarray = nested_array(depth, ndarray);
-        CHECK(json::from_bjdata(json::to_bjdata(deep_ndarray)) == deep_ndarray);
-    }
-
-    SECTION("a discarded value past the recursion bound still throws type_error.321")
-    {
-        const std::size_t depth = nlohmann::detail::recursion_depth_limit() + 50;
-        const json discarded_leaf(json::value_t::discarded);
-        const json deep_discarded = nested_array(depth, discarded_leaf);
-
-        // with diagnostics, the message names the path to the discarded leaf
-#if JSON_DIAGNOSTICS
-        std::string path;
-        for (std::size_t i = 0; i < depth; ++i)
-        {
-            path += "/0";
-        }
-        const std::string prefix = "[json.exception.type_error.321] (" + path + ") ";
-#else
-        const std::string prefix = "[json.exception.type_error.321] ";
-#endif
-
-        CHECK_THROWS_WITH_AS(json::to_cbor(deep_discarded), (prefix + "cannot serialize discarded value to CBOR").c_str(), json::type_error);
-        CHECK_THROWS_WITH_AS(json::to_msgpack(deep_discarded), (prefix + "cannot serialize discarded value to MessagePack").c_str(), json::type_error);
-        CHECK_THROWS_WITH_AS(json::to_ubjson(deep_discarded), (prefix + "cannot serialize discarded value to UBJSON").c_str(), json::type_error);
-        CHECK_THROWS_WITH_AS(json::to_bjdata(deep_discarded), (prefix + "cannot serialize discarded value to BJData").c_str(), json::type_error);
-    }
-
-    SECTION("BON8 past the recursion bound: discarded values and errors")
-    {
-        const std::size_t depth = nlohmann::detail::recursion_depth_limit() + 50;
-
-        // BON8 rejects a discarded value (type_error.321), deep or not
-        const json deep_discarded = nested_array(depth, json(json::value_t::discarded));
-        CHECK_THROWS_AS(json::to_bon8(deep_discarded), json::type_error);
-
-        // errors are thrown from below the bound as from above it
-        const json deep_invalid_string = nested_array(depth, json(std::string("\x80")));
-        CHECK_THROWS_AS(json::to_bon8(deep_invalid_string), json::type_error);
-
-        json deep_invalid_key = json::object();
-        deep_invalid_key[std::string("\x80")] = 1;
-        deep_invalid_key = nested_object(depth, deep_invalid_key);
-        CHECK_THROWS_AS(json::to_bon8(deep_invalid_key), json::type_error);
-
-        const json deep_too_large = nested_array(depth, json(9223372036854775808u));
-        CHECK_THROWS_AS(json::to_bon8(deep_too_large), json::out_of_range);
-    }
-
-    SECTION("does not overflow the C++ stack")
-    {
-        const std::size_t depth = 100000;
-        const json j = json::parse(std::string(depth, '[') + "0" + std::string(depth, ']'));
-
-        std::vector<std::uint8_t> packed;
-        CHECK_NOTHROW(packed = json::to_cbor(j));
-        CHECK(json::from_cbor(packed) == j);
-
-        CHECK_NOTHROW(packed = json::to_msgpack(j));
-        CHECK(json::from_msgpack(packed) == j);
-
-        CHECK_NOTHROW(packed = json::to_ubjson(j));
-        CHECK(json::from_ubjson(packed) == j);
-
-        CHECK_NOTHROW(packed = json::to_ubjson(j, true, false));
-        CHECK(json::from_ubjson(packed) == j);
-
-        CHECK_NOTHROW(packed = json::to_bjdata(j));
-        CHECK(json::from_bjdata(packed) == j);
-
-        CHECK_NOTHROW(packed = json::to_bon8(j));
-        CHECK(json::from_bon8(packed) == j);
-    }
-
-    SECTION("BON8 containers with more than four elements past the recursion bound")
-    {
-        // such containers are closed with 0xFE, which the iterative writer
-        // must emit when it leaves them; strings next to each other must
-        // still be separated with 0xFF
-        const std::size_t depth = nlohmann::detail::recursion_depth_limit() + 50;
-        json wide_array = json::array({1, "a", "b", json::array(), 5});
-        json wide_object = json({{"k1", "v"}, {"k2", 2}, {"k3", ""}, {"k4", json::object()}, {"k5", nullptr}});
-        for (std::size_t i = 0; i < depth; ++i)
-        {
-            wide_array = json::array({"s", wide_array, "t", wide_object, true});
-            wide_object = json({{"a", wide_object}, {"b", "x"}, {"c", "y"}, {"d", wide_array.size()}, {"e", "z"}});
-        }
-
-        CHECK(json::from_bon8(json::to_bon8(wide_array)) == wide_array);
-        CHECK(json::from_bon8(json::to_bon8(wide_object)) == wide_object);
-    }
-
-    SECTION("regression test for https://issues.oss-fuzz.com/issues/566583014")
-    {
-        // 200000 nested one-element CBOR arrays, the innermost holding null;
-        // round-tripping this used to recurse once per level on the way back
-        // out through to_cbor(), deep enough to overflow the stack
-        std::vector<std::uint8_t> v(200000, 0x81);
-        v.push_back(0xf6);
-        const json j = json::from_cbor(v);
-        CHECK(json::to_cbor(j) == v);
-
-        // the MessagePack analogue: fixarray of 1 nesting down to nil
-        std::vector<std::uint8_t> v_msgpack(200000, 0x91);
-        v_msgpack.push_back(0xc0);
-        const json j_msgpack = json::from_msgpack(v_msgpack);
-        CHECK(json::to_msgpack(j_msgpack) == v_msgpack);
-    }
-
-    SECTION("regression test for https://issues.oss-fuzz.com/issues/572238015")
-    {
-        // the BON8 analogue: 200000 nested one-element arrays down to null
-        std::vector<std::uint8_t> v(200000, 0x81);
-        v.push_back(0xFA);
-        const json j = json::from_bon8(v);
-        CHECK(json::to_bon8(j) == v);
-    }
-}
-

tests/src/unit-large_json_binary_writers.cpp

@@ -0,0 +1,294 @@
+//     __ _____ _____ _____
+//  __|  |   __|     |   | |  JSON for Modern C++ (supporting code)
+// |  |  |__   |  |  | | | |  version 3.12.0
+// |_____|_____|_____|_|___|  https://github.com/nlohmann/json
+//
+// SPDX-FileCopyrightText: 2013-2026 Niels Lohmann <https://nlohmann.me>
+// SPDX-License-Identifier: MIT
+
+
+#include "doctest_compatibility.h"
+
+#include <nlohmann/json.hpp>
+using nlohmann::json;
+
+#include <cstddef>
+#include <cstdint>
+#include <string>
+#include <utility>
+#include <vector>
+
+// split from unit-large_json.cpp so that both run in parallel and stay below
+// the ctest timeout under Valgrind
+
+namespace
+{
+json nested_array(const std::size_t depth, json leaf)
+{
+    json j = std::move(leaf);
+    for (std::size_t i = 0; i < depth; ++i)
+    {
+        json a = json::array();
+        a.push_back(std::move(j));
+        j = std::move(a);
+    }
+    return j;
+}
+
+json nested_object(const std::size_t depth, json leaf)
+{
+    json j = std::move(leaf);
+    for (std::size_t i = 0; i < depth; ++i)
+    {
+        json o = json::object();
+        o["k"] = std::move(j);
+        j = std::move(o);
+    }
+    return j;
+}
+} // namespace
+
+TEST_CASE("issue #5392 - binary writers on deeply nested values")
+{
+    // 200 is past the point where the writers stop recursing, and still
+    // shallow enough that from_* and operator== (which still recurse) are fine.
+    const json deep_array = nested_array(200, json(0));
+    const json deep_object = nested_object(200, json("x"));
+    const json empty_array = nested_array(200, json::array());
+    const json empty_object = nested_object(200, json::object());
+    const json mixed = nested_object(80, nested_array(80, json(true)));
+
+    SECTION("roundtrip past the recursion bound")
+    {
+        CHECK(json::from_cbor(json::to_cbor(deep_array)) == deep_array);
+        CHECK(json::from_msgpack(json::to_msgpack(deep_array)) == deep_array);
+        CHECK(json::from_ubjson(json::to_ubjson(deep_array)) == deep_array);
+        CHECK(json::from_ubjson(json::to_ubjson(deep_array, true, false)) == deep_array);
+        CHECK(json::from_ubjson(json::to_ubjson(deep_array, true, true)) == deep_array);
+        CHECK(json::from_bjdata(json::to_bjdata(deep_array)) == deep_array);
+        CHECK(json::from_bon8(json::to_bon8(deep_array)) == deep_array);
+
+        CHECK(json::from_cbor(json::to_cbor(deep_object)) == deep_object);
+        CHECK(json::from_msgpack(json::to_msgpack(deep_object)) == deep_object);
+        CHECK(json::from_ubjson(json::to_ubjson(deep_object)) == deep_object);
+        CHECK(json::from_ubjson(json::to_ubjson(deep_object, true, true)) == deep_object);
+        CHECK(json::from_bjdata(json::to_bjdata(deep_object)) == deep_object);
+        CHECK(json::from_bon8(json::to_bon8(deep_object)) == deep_object);
+
+        CHECK(json::from_cbor(json::to_cbor(empty_array)) == empty_array);
+        CHECK(json::from_msgpack(json::to_msgpack(empty_array)) == empty_array);
+        CHECK(json::from_ubjson(json::to_ubjson(empty_array)) == empty_array);
+        CHECK(json::from_ubjson(json::to_ubjson(empty_array, true, true)) == empty_array);
+        CHECK(json::from_bon8(json::to_bon8(empty_array)) == empty_array);
+
+        CHECK(json::from_cbor(json::to_cbor(empty_object)) == empty_object);
+        CHECK(json::from_msgpack(json::to_msgpack(empty_object)) == empty_object);
+        CHECK(json::from_ubjson(json::to_ubjson(empty_object)) == empty_object);
+        CHECK(json::from_bon8(json::to_bon8(empty_object)) == empty_object);
+
+        CHECK(json::from_cbor(json::to_cbor(mixed)) == mixed);
+        CHECK(json::from_msgpack(json::to_msgpack(mixed)) == mixed);
+        CHECK(json::from_ubjson(json::to_ubjson(mixed)) == mixed);
+        CHECK(json::from_bjdata(json::to_bjdata(mixed)) == mixed);
+        CHECK(json::from_bon8(json::to_bon8(mixed)) == mixed);
+    }
+
+    SECTION("the two ways of writing a value meet at the bound")
+    {
+        for (std::size_t depth = 120; depth <= 140; ++depth)
+        {
+            CAPTURE(depth)
+
+            const json array = nested_array(depth, json(7));
+            CHECK(json::from_cbor(json::to_cbor(array)) == array);
+            CHECK(json::from_msgpack(json::to_msgpack(array)) == array);
+            CHECK(json::from_ubjson(json::to_ubjson(array, true, true)) == array);
+            CHECK(json::from_bon8(json::to_bon8(array)) == array);
+
+            const json object = nested_object(depth, json(7));
+            CHECK(json::from_cbor(json::to_cbor(object)) == object);
+            CHECK(json::from_msgpack(json::to_msgpack(object)) == object);
+            CHECK(json::from_bjdata(json::to_bjdata(object)) == object);
+            CHECK(json::from_bon8(json::to_bon8(object)) == object);
+        }
+    }
+
+    SECTION("a BJData ndarray below the bound is still an ndarray")
+    {
+        const json ndarray = json({{"_ArrayType_", "uint8"}, {"_ArraySize_", {2, 3}}, {"_ArrayData_", {1, 2, 3, 4, 5, 6}}});
+        const json invalid = json({{"_ArrayType_", "nope"}, {"_ArraySize_", {1}}, {"_ArrayData_", {1}}});
+
+        const json deep_ndarray = nested_array(140, ndarray);
+        const json deep_invalid = nested_array(140, invalid);
+
+        CHECK(json::from_bjdata(json::to_bjdata(deep_ndarray)) == deep_ndarray);
+        CHECK(json::from_bjdata(json::to_bjdata(deep_invalid)) == deep_invalid);
+        CHECK(json::from_bjdata(json::to_bjdata(ndarray)) == ndarray);
+    }
+
+    SECTION("byte-exact across the switch-over")
+    {
+        // nested one-element arrays around the recursion bound: the exact
+        // bytes a writer produces do not depend on whether it stayed on the
+        // call stack or moved to the heap one partway through
+        for (const std::size_t depth :
+                {
+                    nlohmann::detail::recursion_depth_limit() - 1, nlohmann::detail::recursion_depth_limit(),
+                    nlohmann::detail::recursion_depth_limit() + 1, nlohmann::detail::recursion_depth_limit() + 2
+                })
+        {
+            CAPTURE(depth)
+            const json array = nested_array(depth, json(0));
+
+            std::vector<std::uint8_t> expected_cbor(depth, 0x81);
+            expected_cbor.push_back(0x00);
+            CHECK(json::to_cbor(array) == expected_cbor);
+
+            std::vector<std::uint8_t> expected_msgpack(depth, 0x91);
+            expected_msgpack.push_back(0x00);
+            CHECK(json::to_msgpack(array) == expected_msgpack);
+
+            std::string expected_ubjson(depth, '[');
+            expected_ubjson += "i";
+            expected_ubjson += '\0';
+            expected_ubjson.append(depth, ']');
+            const auto packed_ubjson = json::to_ubjson(array);
+            CHECK(std::string(packed_ubjson.begin(), packed_ubjson.end()) == expected_ubjson);
+
+            std::vector<std::uint8_t> expected_bon8(depth, 0x81);
+            expected_bon8.push_back(0x90);
+            CHECK(json::to_bon8(array) == expected_bon8);
+        }
+    }
+
+    SECTION("a deep object, and a BJData ndarray, past the recursion bound")
+    {
+        const std::size_t depth = nlohmann::detail::recursion_depth_limit() + 50;
+
+        const json object = nested_object(depth, json(42));
+        CHECK(json::from_cbor(json::to_cbor(object)) == object);
+        CHECK(json::from_msgpack(json::to_msgpack(object)) == object);
+        CHECK(json::from_ubjson(json::to_ubjson(object, true, true)) == object);
+        CHECK(json::from_bjdata(json::to_bjdata(object)) == object);
+        CHECK(json::from_bon8(json::to_bon8(object)) == object);
+
+        const json ndarray = json({{"_ArrayType_", "uint8"}, {"_ArraySize_", {2, 3}}, {"_ArrayData_", {1, 2, 3, 4, 5, 6}}});
+        const json deep_ndarray = nested_array(depth, ndarray);
+        CHECK(json::from_bjdata(json::to_bjdata(deep_ndarray)) == deep_ndarray);
+    }
+
+    SECTION("a discarded value past the recursion bound still throws type_error.321")
+    {
+        const std::size_t depth = nlohmann::detail::recursion_depth_limit() + 50;
+        const json discarded_leaf(json::value_t::discarded);
+        const json deep_discarded = nested_array(depth, discarded_leaf);
+
+        // with diagnostics, the message names the path to the discarded leaf
+#if JSON_DIAGNOSTICS
+        std::string path;
+        for (std::size_t i = 0; i < depth; ++i)
+        {
+            path += "/0";
+        }
+        const std::string prefix = "[json.exception.type_error.321] (" + path + ") ";
+#else
+        const std::string prefix = "[json.exception.type_error.321] ";
+#endif
+
+        CHECK_THROWS_WITH_AS(json::to_cbor(deep_discarded), (prefix + "cannot serialize discarded value to CBOR").c_str(), json::type_error);
+        CHECK_THROWS_WITH_AS(json::to_msgpack(deep_discarded), (prefix + "cannot serialize discarded value to MessagePack").c_str(), json::type_error);
+        CHECK_THROWS_WITH_AS(json::to_ubjson(deep_discarded), (prefix + "cannot serialize discarded value to UBJSON").c_str(), json::type_error);
+        CHECK_THROWS_WITH_AS(json::to_bjdata(deep_discarded), (prefix + "cannot serialize discarded value to BJData").c_str(), json::type_error);
+    }
+
+    SECTION("BON8 past the recursion bound: discarded values and errors")
+    {
+        const std::size_t depth = nlohmann::detail::recursion_depth_limit() + 50;
+
+        // BON8 rejects a discarded value (type_error.321), deep or not
+        const json deep_discarded = nested_array(depth, json(json::value_t::discarded));
+        CHECK_THROWS_AS(json::to_bon8(deep_discarded), json::type_error);
+
+        // errors are thrown from below the bound as from above it
+        const json deep_invalid_string = nested_array(depth, json(std::string("\x80")));
+        CHECK_THROWS_AS(json::to_bon8(deep_invalid_string), json::type_error);
+
+        json deep_invalid_key = json::object();
+        deep_invalid_key[std::string("\x80")] = 1;
+        deep_invalid_key = nested_object(depth, deep_invalid_key);
+        CHECK_THROWS_AS(json::to_bon8(deep_invalid_key), json::type_error);
+
+        const json deep_too_large = nested_array(depth, json(9223372036854775808u));
+        CHECK_THROWS_AS(json::to_bon8(deep_too_large), json::out_of_range);
+    }
+
+    SECTION("does not overflow the C++ stack")
+    {
+        const std::size_t depth = 100000;
+        const json j = json::parse(std::string(depth, '[') + "0" + std::string(depth, ']'));
+
+        std::vector<std::uint8_t> packed;
+        CHECK_NOTHROW(packed = json::to_cbor(j));
+        CHECK(json::from_cbor(packed) == j);
+
+        CHECK_NOTHROW(packed = json::to_msgpack(j));
+        CHECK(json::from_msgpack(packed) == j);
+
+        CHECK_NOTHROW(packed = json::to_ubjson(j));
+        CHECK(json::from_ubjson(packed) == j);
+
+        CHECK_NOTHROW(packed = json::to_ubjson(j, true, false));
+        CHECK(json::from_ubjson(packed) == j);
+
+        CHECK_NOTHROW(packed = json::to_bjdata(j));
+        CHECK(json::from_bjdata(packed) == j);
+
+        CHECK_NOTHROW(packed = json::to_bon8(j));
+        CHECK(json::from_bon8(packed) == j);
+    }
+
+    SECTION("BON8 containers with more than four elements past the recursion bound")
+    {
+        // such containers are closed with 0xFE, which the iterative writer
+        // must emit when it leaves them; strings next to each other must
+        // still be separated with 0xFF
+        const std::size_t depth = nlohmann::detail::recursion_depth_limit() + 50;
+        json wide_array = json::array({1, "a", "b", json::array(), 5});
+        json wide_object = json({{"k1", "v"}, {"k2", 2}, {"k3", ""}, {"k4", json::object()}, {"k5", nullptr}});
+        for (std::size_t i = 0; i < depth; ++i)
+        {
+            wide_array = json::array({"s", wide_array, "t", wide_object, true});
+            wide_object = json({{"a", wide_object}, {"b", "x"}, {"c", "y"}, {"d", wide_array.size()}, {"e", "z"}});
+        }
+
+        CHECK(json::from_bon8(json::to_bon8(wide_array)) == wide_array);
+        CHECK(json::from_bon8(json::to_bon8(wide_object)) == wide_object);
+    }
+
+    SECTION("regression test for https://issues.oss-fuzz.com/issues/566583014")
+    {
+        // 200000 nested one-element CBOR arrays, the innermost holding null;
+        // round-tripping this used to recurse once per level on the way back
+        // out through to_cbor(), deep enough to overflow the stack
+        std::vector<std::uint8_t> v(200000, 0x81);
+        v.push_back(0xf6);
+        const json j = json::from_cbor(v);
+        CHECK(json::to_cbor(j) == v);
+
+        // the MessagePack analogue: fixarray of 1 nesting down to nil
+        std::vector<std::uint8_t> v_msgpack(200000, 0x91);
+        v_msgpack.push_back(0xc0);
+        const json j_msgpack = json::from_msgpack(v_msgpack);
+        CHECK(json::to_msgpack(j_msgpack) == v_msgpack);
+    }
+
+    SECTION("regression test for https://issues.oss-fuzz.com/issues/572238015")
+    {
+        // the BON8 analogue: 200000 nested one-element arrays down to null
+        std::vector<std::uint8_t> v(200000, 0x81);
+        v.push_back(0xFA);
+        const json j = json::from_bon8(v);
+        CHECK(json::to_bon8(j) == v);
+    }
+}
+

tests/src/unit-large_json_conversions.cpp

@@ -0,0 +1,156 @@
+//     __ _____ _____ _____
+//  __|  |   __|     |   | |  JSON for Modern C++ (supporting code)
+// |  |  |__   |  |  | | | |  version 3.12.0
+// |_____|_____|_____|_|___|  https://github.com/nlohmann/json
+//
+// SPDX-FileCopyrightText: 2013-2026 Niels Lohmann <https://nlohmann.me>
+// SPDX-License-Identifier: MIT
+
+#include "doctest_compatibility.h"
+
+#include <nlohmann/json.hpp>
+using nlohmann::json;
+
+#include <cstddef>
+#include <string>
+#include <utility>
+#include <vector>
+
+// split from unit-large_json.cpp so that both run in parallel and stay below
+// the ctest timeout under Valgrind
+
+namespace
+{
+
+// The text of a value nested depth levels deep around the number 0. Level i is
+// an array if pattern[i % pattern.size()] is '[', and otherwise an object with
+// the single member "a", which every object type enumerates in the same order.
+std::string nested_text(std::size_t depth, const std::string& pattern)
+{
+    std::string text;
+    std::string closing;
+    for (std::size_t i = 0; i < depth; ++i)
+    {
+        const bool array = pattern[i % pattern.size()] == '[';
+        text += array ? "[" : "{\"a\":";
+        closing += array ? ']' : '}';
+    }
+    text += '0';
+    text.append(closing.rbegin(), closing.rend());
+    return text;
+}
+
+} // namespace
+
+TEST_CASE("issue #5650 - stack overflow converting between specializations")
+{
+    // deep enough to exhaust the call stack, but small enough to stay cheap:
+    // parsing is iterative, so building the values below costs little
+    const std::size_t depth = 100000;
+
+    const std::vector<std::string> patterns = {"[", "{", "[{"};
+
+    SECTION("json to ordered_json")
+    {
+        for (const auto& pattern : patterns)
+        {
+            CAPTURE(pattern)
+            const std::string text = nested_text(depth, pattern);
+            const json j = json::parse(text);
+
+            const nlohmann::ordered_json converted = j;
+            CHECK(converted.dump() == text);
+        }
+    }
+
+    SECTION("ordered_json to json")
+    {
+        for (const auto& pattern : patterns)
+        {
+            CAPTURE(pattern)
+            const std::string text = nested_text(depth, pattern);
+            const nlohmann::ordered_json o = nlohmann::ordered_json::parse(text);
+
+            const json converted = o;
+            CHECK(converted.dump() == text);
+        }
+    }
+
+    SECTION("get<ordered_json>()")
+    {
+        for (const auto& pattern : patterns)
+        {
+            CAPTURE(pattern)
+            const std::string text = nested_text(depth, pattern);
+            const json j = json::parse(text);
+
+            CHECK(j.get<nlohmann::ordered_json>().dump() == text);
+        }
+    }
+
+    SECTION("depths around the bound of the recursive descent")
+    {
+        for (std::size_t d = 1; d <= 300; ++d)
+        {
+            CAPTURE(d)
+            for (const auto& pattern : patterns)
+            {
+                CAPTURE(pattern)
+                const std::string text = nested_text(d, pattern);
+                const json j = json::parse(text);
+
+                const nlohmann::ordered_json converted = j;
+                CHECK(converted.dump() == text);
+                const json back = converted;
+                CHECK(back.dump() == text);
+            }
+        }
+    }
+
+    SECTION("values below the bound are converted as values above it")
+    {
+        // Bury a value below the bound, where it is converted without the
+        // call stack, and compare it with the same value converted on its
+        // own by the containers' range constructors. Its objects have
+        // members that the two object types enumerate in different orders.
+        const auto bury = [](nlohmann::ordered_json value)
+        {
+            for (std::size_t i = 0; i < 200; ++i)
+            {
+                value = nlohmann::ordered_json::array({std::move(value)});
+            }
+            return value;
+        };
+        const auto dig = [](const json & value)
+        {
+            const json* current = &value;
+            for (std::size_t i = 0; i < 200; ++i)
+            {
+                current = &current->at(0);
+            }
+            return current;
+        };
+
+        nlohmann::ordered_json value = nlohmann::ordered_json::object();
+        value["z"] = {1, -2, 3U, 4.5, true, nullptr, "six", nlohmann::ordered_json::binary({7, 8}, 9),
+                      nlohmann::ordered_json::binary({10}), nlohmann::ordered_json::array(), nlohmann::ordered_json::object()
+                     };
+        value["y"] = {{"x", {{"w", 1}, {"v", 2}}}, {"u", {3, {{"t", 4}, {"s", 5}}}}};
+        value["r"] = nlohmann::ordered_json::array({nlohmann::ordered_json(nlohmann::ordered_json::value_t::discarded)});
+
+        const json converted_above = value;
+        const json buried = bury(value);
+        const json& converted_below = *dig(buried);
+
+        CHECK(converted_below.dump() == converted_above.dump());
+        CHECK(converted_below.at("z").at(7).get_binary().subtype() == 9);
+        CHECK_FALSE(converted_below.at("z").at(8).get_binary().has_subtype());
+        CHECK(converted_below.at("r").at(0).is_discarded());
+
+        // a discarded value is never equal to anything, so compare the rest
+        value.erase("r");
+        const json without_discarded_above = value;
+        const json without_discarded_buried = bury(value);
+        CHECK(*dig(without_discarded_buried) == without_discarded_above);
+    }
+}