Rename diff_target_values::small, which windows.h defines as a macro

<windows.h> (rpcndr.h) defines small as char, so test-windows_h did not
compile with MSVC.

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

include/nlohmann/detail/input/binary_reader.hpp

@@ -86,7 +86,7 @@ JSON_INLINE_VARIABLE constexpr std::size_t max_valueless_container_size = 1 << 2
 /*!
 @brief deserialization of BJData, BON8, BSON, CBOR, MessagePack, and UBJSON values
 */
-template<typename BasicJsonType, typename InputAdapterType, typename SAX = json_sax_dom_binary_parser<BasicJsonType, InputAdapterType>>
+template<typename BasicJsonType, typename InputAdapterType, typename SAX = json_sax_dom_parser<BasicJsonType, InputAdapterType>>
 class binary_reader
 {
     using number_integer_t = typename BasicJsonType::number_integer_t;

include/nlohmann/detail/input/lexer.hpp

@@ -14,7 +14,6 @@
 #include <cstdio> // snprintf
 #include <cstring> // memcmp
 #include <initializer_list> // initializer_list
-#include <limits> // numeric_limits
 #include <string> // char_traits, string
 #include <utility> // move
 #include <vector> // vector
@@ -1817,15 +1816,6 @@ scan_number_done:
     /// significand (see scan_number_bulk_contiguous())
     bool convert_accumulated_float(const float_significand& s, std::true_type /*native*/) noexcept
     {
-        // accept() only needs to know that the value is finite (see the parser):
-        // w < 10^19, so a value below 10^max_exponent10 cannot overflow, and a
-        // value that underflows is a finite number as well. Only a token that
-        // may overflow has to be converted to find out.
-        if (JSON_HEDLEY_UNLIKELY(discard_number_values && s.exponent + 19 <= std::numeric_limits<number_float_t>::max_exponent10))
-        {
-            value_float = 0;
-            return true;
-        }
         value_float = decimal_to_float<number_float_t>(s);
         return true;
     }

include/nlohmann/detail/input/parser.hpp

@@ -250,13 +250,6 @@ class parser
         // value to avoid a goto (see comment where set to true)
         bool skip_to_state_evaluation = false;
 
-        // a document that starts with a container pushes onto the stack at
-        // once: allocate it in one step instead of growing it from 1 byte
-        if (last_token == token_type::begin_object || last_token == token_type::begin_array)
-        {
-            states.reserve(32);
-        }
-
         while (true)
         {
             if (!skip_to_state_evaluation)

include/nlohmann/detail/json_pointer.hpp

@@ -15,7 +15,7 @@
 #include <cstddef> // size_t
 #include <cstdint> // uint64_t
 #include <cstdlib> // strtoull
-#include <cstring> // memcmp, memcpy
+#include <cstring> // memchr, memcmp, memcpy
 #ifndef JSON_NO_IO
     #include <iosfwd> // ostream
 #endif  // JSON_NO_IO
@@ -303,6 +303,12 @@ class json_pointer
         exceeds_size_type  ///< @a s converts to an integer that exceeds size_type
     };
 
+    /// whether a reference token is "-" (a plain comparison with a string literal is not always inlined)
+    static bool is_dash(const string_t& s) noexcept
+    {
+        return s.size() == 1 && s[0] == '-';
+    }
+
     /*!
     @param[in] s    reference token to be converted into an array index
     @param[out] idx the integer representation of @a s if @ref array_index_status::ok
@@ -328,7 +334,7 @@ class json_pointer
         // error condition (cf. RFC 6901, Sect. 4); this also covers single-
         // character tokens, so "/x" and "/xy" fail alike; "-" and the empty
         // token are left to the conversion below and are reported as unresolved
-        if (JSON_HEDLEY_UNLIKELY(!s.empty() && s != "-" && !(s[0] >= '0' && s[0] <= '9')))
+        if (JSON_HEDLEY_UNLIKELY(!s.empty() && !is_dash(s) && !(s[0] >= '0' && s[0] <= '9')))
         {
             return array_index_status::not_a_number;
         }
@@ -475,9 +481,40 @@ class json_pointer
         return pos == size;
     }
 
+    /// reserve room for @a n elements of an array type that has reserve()
+    template<typename ArrayType>
+    static auto reserve_elements(ArrayType& array, const std::size_t n, detail::priority_tag<1> /*unused*/)
+    -> decltype(array.reserve(n), void())
+    {
+        array.reserve(n);
+    }
+
+    template<typename ArrayType>
+    static void reserve_elements(ArrayType& /*array*/, const std::size_t /*n*/, detail::priority_tag<0> /*unused*/)
+    {}
+
     /// @brief object member access with a key that is only copied if it is inserted
+    ///
+    /// Objects that can find the position of a key and insert there
+    /// (std::map) search once, others look the key up and add it if it is missing.
     template<typename BasicJsonType>
-    static BasicJsonType& object_member(BasicJsonType& object, const string_t& key)
+    static auto object_member_impl(BasicJsonType& object, const string_t& key, detail::priority_tag<1> /*unused*/)
+    -> decltype(object.m_data.m_value.object->emplace_hint(object.m_data.m_value.object->lower_bound(key), key, nullptr), std::declval<BasicJsonType&>())
+    {
+        auto& members = *object.m_data.m_value.object;
+        auto it = members.lower_bound(key);
+        if (it != members.end() && !members.key_comp()(key, it->first))
+        {
+            return it->second;
+        }
+
+        const auto old_capacity = object.container_capacity();
+        it = members.emplace_hint(it, key, nullptr);
+        return object.set_parent_after_insert(it->second, old_capacity);
+    }
+
+    template<typename BasicJsonType>
+    static BasicJsonType& object_member_impl(BasicJsonType& object, const string_t& key, detail::priority_tag<0> /*unused*/)
     {
         auto& members = *object.m_data.m_value.object;
         const auto it = members.find(key);
@@ -488,6 +525,12 @@ class json_pointer
         return object.operator[](key);
     }
 
+    template<typename BasicJsonType>
+    static BasicJsonType& object_member(BasicJsonType& object, const string_t& key)
+    {
+        return object_member_impl(object, key, detail::priority_tag<1> {});
+    }
+
   JSON_PRIVATE_UNLESS_TESTED:
     json_pointer top() const
     {
@@ -720,48 +763,103 @@ class json_pointer
         }
     }
 
+    /*!
+    @brief the values along the pointer last resolved by @ref resolve_plain
+
+    A patch from @ref basic_json::diff lists its operations in document order,
+    so consecutive pointers share most of their reference tokens; the values
+    along the previous pointer are kept to resume from the common prefix.
+    `steps[k]` is the value after the first `k` reference tokens together with
+    the length of the prefix of `*path` that holds them. A value stays valid as
+    long as no operation changes its container: callers keep only values up to
+    the parent of the pointer they modify, or call `reset()`.
+    */
+    template<typename BasicJsonType>
+    struct plain_steps
+    {
+        const string_t* path = nullptr;
+        std::vector<std::pair<std::size_t, BasicJsonType*>> steps{};
+
+        void reset() noexcept
+        {
+            path = nullptr;
+            steps.clear();
+        }
+    };
+
     /*!
     @brief resolve a plain JSON pointer without building its reference tokens
 
-    @param[in] ptr     the value the pointer starts at
+    @param[in] root    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
+    @param[in,out] cache  the values along the previously resolved pointer;
+                          @a path must outlive the next call
 
     @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.
+            an existing value, or does so in a way that is not plain: an array
+            index that is malformed or out of range, or a "-", or a reference
+            token with an escape. No exception is
+            thrown for these; callers use @ref json_pointer instead, which
+            handles them.
     */
     template<typename BasicJsonType>
-    static BasicJsonType* resolve_plain(BasicJsonType* ptr, const string_t& path, const std::size_t length, string_t& token)
+    static BasicJsonType* resolve_plain(BasicJsonType* root, const string_t& path, const std::size_t length, string_t& token, plain_steps<BasicJsonType>& cache)
     {
-        for (std::size_t pos = 0; pos < length;)
+        auto& steps = cache.steps;
+
+        // resume from the deepest step that is also a prefix of this path
+        std::size_t depth = 1;
+        if (cache.path != nullptr && !steps.empty() && steps[0].second == root)
+        {
+            const string_t& previous = *cache.path;
+            for (depth = steps.size(); depth > 1; --depth)
+            {
+                // a step ends at a token boundary of the previous path
+                const std::size_t prefix = steps[depth - 1].first;
+                if (prefix <= length && (prefix == length || path[prefix] == '/') && std::memcmp(path.data(), previous.data(), prefix) == 0)
+                {
+                    break;
+                }
+            }
+            steps.resize(depth);
+        }
+        else
+        {
+            steps.assign(1, std::make_pair(std::size_t{0}, root));
+        }
+        cache.path = &path;
+
+        BasicJsonType* ptr = steps[depth - 1].second;
+        for (std::size_t pos = steps[depth - 1].first; pos < length;)
         {
             if (JSON_HEDLEY_UNLIKELY(path[pos] != '/'))
             {
                 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)
+            // the reference token between the slash at pos and the next one,
+            // which must not have an escape
+            const char* const begin = path.data() + pos + 1;
+            const char* const limit = path.data() + length;
+            const char* end = begin;
+            while (end < limit && *end != '/')
             {
-                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;
+                if (JSON_HEDLEY_UNLIKELY(*end == '~'))
+                {
+                    return nullptr;
+                }
+                ++end;
             }
 
             switch (ptr->type())
             {
                 case detail::value_t::object:
                 {
+                    token.clear();
+                    token.append(begin, static_cast<std::size_t>(end - begin));
                     const auto it = ptr->m_data.m_value.object->find(token);
                     if (JSON_HEDLEY_UNLIKELY(it == ptr->m_data.m_value.object->end()))
                     {
@@ -773,8 +871,24 @@ class json_pointer
 
                 case detail::value_t::array:
                 {
-                    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()))
+                    // an index of up to 18 digits without a leading zero fits into size_type
+                    // (9 digits for a 32-bit size_type); everything else is left to json_pointer
+                    constexpr std::size_t max_digits = sizeof(typename BasicJsonType::size_type) >= 8 ? 18 : 9;
+                    const std::size_t digits = static_cast<std::size_t>(end - begin);
+                    if (JSON_HEDLEY_UNLIKELY(digits == 0 || digits > max_digits || (digits > 1 && *begin == '0')))
+                    {
+                        return nullptr;
+                    }
+                    typename BasicJsonType::size_type idx = 0;
+                    for (const char* c = begin; c != end; ++c)
+                    {
+                        if (JSON_HEDLEY_UNLIKELY(*c < '0' || *c > '9'))
+                        {
+                            return nullptr;
+                        }
+                        idx = static_cast<typename BasicJsonType::size_type>((idx * 10) + static_cast<typename BasicJsonType::size_type>(*c - '0'));
+                    }
+                    if (JSON_HEDLEY_UNLIKELY(idx >= ptr->m_data.m_value.array->size()))
                     {
                         return nullptr;
                     }
@@ -793,7 +907,8 @@ class json_pointer
                 default:
                     return nullptr;
             }
-            pos = end;
+            pos = static_cast<std::size_t>(end - path.data());
+            steps.emplace_back(pos, ptr);
         }
 
         return ptr;
@@ -907,7 +1022,7 @@ class json_pointer
 
                 case detail::value_t::array:
                 {
-                    if (JSON_HEDLEY_UNLIKELY(reference_token == "-"))
+                    if (JSON_HEDLEY_UNLIKELY(is_dash(reference_token)))
                     {
                         // "-" always fails the range check
                         JSON_THROW(detail::out_of_range::create(detail::exception_id::pointer_past_the_end_index, detail::concat(
@@ -978,7 +1093,7 @@ class json_pointer
 
                 case detail::value_t::array:
                 {
-                    if (JSON_HEDLEY_UNLIKELY(reference_token == "-"))
+                    if (JSON_HEDLEY_UNLIKELY(is_dash(reference_token)))
                     {
                         // "-" cannot be used for const access
                         JSON_THROW(detail::out_of_range::create(detail::exception_id::pointer_past_the_end_index, detail::concat("array index '-' (", std::to_string(ptr->m_data.m_value.array->size()), ") is out of range"), ptr));
@@ -1040,7 +1155,7 @@ class json_pointer
 
                 case detail::value_t::array:
                 {
-                    if (JSON_HEDLEY_UNLIKELY(reference_token == "-"))
+                    if (JSON_HEDLEY_UNLIKELY(is_dash(reference_token)))
                     {
                         // "-" always fails the range check
                         return nullptr;
@@ -1117,7 +1232,7 @@ class json_pointer
 
                 case detail::value_t::array:
                 {
-                    if (JSON_HEDLEY_UNLIKELY(reference_token == "-"))
+                    if (JSON_HEDLEY_UNLIKELY(is_dash(reference_token)))
                     {
                         // "-" always fails the range check
                         return false;
@@ -1276,6 +1391,52 @@ class json_pointer
         obj[key] = std::forward<ValueType>(v);
     }
 
+    /// the number of entries that flattening @a value adds: its primitive
+    /// values and empty containers
+    template<typename BasicJsonType>
+    static std::size_t count_flattened(const BasicJsonType& value)
+    {
+        std::size_t count = 0;
+        std::vector<const BasicJsonType*> pending(1, &value);
+        while (!pending.empty())
+        {
+            const BasicJsonType* const v = pending.back();
+            pending.pop_back();
+            if (v->is_array() && !v->m_data.m_value.array->empty())
+            {
+                for (const auto& element : *v->m_data.m_value.array)
+                {
+                    pending.push_back(&element);
+                }
+            }
+            else if (v->is_object() && !v->m_data.m_value.object->empty())
+            {
+                for (const auto& member : *v->m_data.m_value.object)
+                {
+                    pending.push_back(&member.second);
+                }
+            }
+            else
+            {
+                ++count;
+            }
+        }
+        return count;
+    }
+
+    // Reserve the storage for @a value of objects that have a reserve(), so
+    // that it does not have to be moved while it grows
+    template<typename ObjectType, typename BasicJsonType>
+    static auto reserve_flattened(ObjectType& obj, const BasicJsonType& value, detail::priority_tag<1> /*unused*/)
+    -> decltype(obj.reserve(std::size_t {}), void())
+    {
+        obj.reserve(count_flattened(value));
+    }
+
+    template<typename ObjectType, typename BasicJsonType>
+    static void reserve_flattened(ObjectType& /*obj*/, const BasicJsonType& /*value*/, detail::priority_tag<0> /*unused*/)
+    {}
+
     /// append the decimal representation of @a i to @a out
     static void append_index(string_t& out, std::size_t i)
     {
@@ -1385,6 +1546,7 @@ class json_pointer
             }
         };
 
+        reserve_flattened(object, value, detail::priority_tag<1> {});
         enter(value);
         while (!stack.empty())
         {
@@ -1392,8 +1554,9 @@ class json_pointer
             // frame, which would invalidate a reference to it
             const BasicJsonType* const container = stack.back().container;
 
-            // drop the path of the previous child
-            path.resize(stack.back().path_length);
+            // the path of the previous child is replaced by the path of the
+            // next one; for an array element in one resize
+            const std::size_t path_length = stack.back().path_length;
 
             if (container->is_array())
             {
@@ -1407,8 +1570,20 @@ class json_pointer
 
                 // iterate array and use index as a reference string
                 ++stack.back().index;
-                path.push_back('/');
-                append_index(path, i);
+                std::array<char, 24> digits{};
+                std::size_t pos = digits.size();
+                std::size_t rest = i;
+                do
+                {
+                    digits[--pos] = static_cast<char>('0' + rest % 10);
+                    rest /= 10;
+                }
+                while (rest != 0);
+                const std::size_t count = digits.size() - pos;
+                path.resize(path_length + 1 + count);
+                char* const out = &path[path_length];
+                out[0] = '/';
+                std::memcpy(out + 1, digits.data() + pos, count);
                 enter(array[i]);
             }
             else
@@ -1422,6 +1597,7 @@ class json_pointer
 
                 // iterate object and use keys as reference string
                 ++stack.back().member;
+                path.resize(path_length);
                 path.push_back('/');
                 detail::escape_into(path, it->first);
                 enter(it->second);
@@ -1517,8 +1693,28 @@ class json_pointer
                 {
                     end = key.size();
                 }
+                const std::size_t token_size = end - pos - 1;
+
+                // a token that is a plain index of up to 9 digits, which is
+                // the case for almost all array elements, is not copied
+                std::size_t index = 0;
+                bool plain_index = current->type() == detail::value_t::array && token_size != 0 && token_size <= 9 && (token_size == 1 || data[pos + 1] != '0');
+                for (std::size_t k = pos + 1; plain_index && k < end; ++k)
+                {
+                    plain_index = data[k] >= '0' && data[k] <= '9';
+                    index = (index * 10) + static_cast<std::size_t>(data[k] - '0');
+                }
+                if (plain_index)
+                {
+                    current = &current->operator[](static_cast<typename BasicJsonType::size_type>(index));
+                    values.push_back(current);
+                    ends.push_back(end);
+                    pos = end;
+                    continue;
+                }
+
                 token.clear();
-                token.append(data + pos + 1, end - pos - 1);
+                token.append(data + pos + 1, token_size);
                 if (token.find_first_of('~') != string_t::npos)
                 {
                     detail::unescape(token);
@@ -1528,10 +1724,13 @@ class json_pointer
                 {
                     case detail::value_t::null:
                     {
-                        if (arrays.contains(data, pos))
+                        // a first child 0 makes the value an array without a look-up
+                        if ((token_size == 1 && data[pos + 1] == '0') || arrays.contains(data, pos))
                         {
                             // some reference token below this position is 0, so the
                             // value is an array
+                            *current = BasicJsonType(detail::value_t::array);
+                            reserve_elements(*current->m_data.m_value.array, 2, detail::priority_tag<1> {});
                             current = &current->operator[](array_index<BasicJsonType>(token));
                         }
                         else

include/nlohmann/json.hpp

@@ -161,8 +161,6 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     template<typename BasicJsonType, typename InputAdapterType>
     friend class ::nlohmann::detail::json_sax_dom_parser;
     template<typename BasicJsonType, typename InputAdapterType>
-    friend class ::nlohmann::detail::json_sax_dom_binary_parser;
-    template<typename BasicJsonType, typename InputAdapterType>
     friend class ::nlohmann::detail::json_sax_dom_callback_parser;
 #if JSON_DIAGNOSTIC_POSITIONS
     friend struct ::nlohmann::detail::diagnostic_positions;
@@ -6289,7 +6287,7 @@ public:
            from_ubjson/from_bjdata/from_bon8/from_bson overloads
 
     Building the @ref binary_reader as a named local, rather than as a
-    temporary that @ref detail::json_sax_dom_binary_parser::parse is called on in
+    temporary that @ref detail::json_sax_dom_parser::parse is called on in
     the same expression, avoids a false-positive cppcheck accessMoved
     warning in each of the 16 callers.
     */
@@ -6300,7 +6298,7 @@ public:
                                        const cbor_tag_handler_t tag_handler = cbor_tag_handler_t::error)
     {
         basic_json result;
-        detail::json_sax_dom_binary_parser<basic_json, InputAdapterType> sdp(result, allow_exceptions);
+        detail::json_sax_dom_parser<basic_json, InputAdapterType> sdp(result, allow_exceptions);
         binary_reader<InputAdapterType> reader(std::move(ia), format, error_handler);
         if (!reader.sax_parse(&sdp, strict, tag_handler))
         {
@@ -6880,6 +6878,72 @@ public:
     /// @name JSON Patch functions
     /// @{
 
+  private:
+    /// the members of an operation of a JSON patch that are of interest
+    struct patch_members
+    {
+        basic_json* op = nullptr;
+        basic_json* path = nullptr;
+        basic_json* value = nullptr;
+        basic_json* from = nullptr;
+    };
+
+    /// @brief find the members "op", "path", "value", and "from" of the object @a val in one pass
+    static patch_members find_patch_members(const basic_json& val, std::true_type /*key_type is string_t*/)
+    {
+        patch_members members;
+        for (auto& member : *val.m_data.m_value.object)
+        {
+            const string_t& key = member.first;
+            switch (key.size())
+            {
+                case 2:
+                    if (key == "op")
+                    {
+                        members.op = &member.second;
+                    }
+                    break;
+                case 4:
+                    if (key == "path")
+                    {
+                        members.path = &member.second;
+                    }
+                    else if (key == "from")
+                    {
+                        members.from = &member.second;
+                    }
+                    break;
+                case 5:
+                    if (key == "value")
+                    {
+                        members.value = &member.second;
+                    }
+                    break;
+                default:
+                    break;
+            }
+        }
+        return members;
+    }
+
+    /// @brief find the members by lookup for key types other than string_t
+    static patch_members find_patch_members(const basic_json& val, std::false_type /*key_type is not string_t*/)
+    {
+        const auto find_member = [&val](const char* name) -> basic_json *
+        {
+            const auto it = val.m_data.m_value.object->find(string_t(name));
+            return it != val.m_data.m_value.object->end() ? &it->second : nullptr;
+        };
+
+        patch_members members;
+        members.op = find_member("op");
+        members.path = find_member("path");
+        members.value = find_member("value");
+        members.from = find_member("from");
+        return members;
+    }
+
+  public:
     /// @brief applies a JSON patch in-place without copying the object
     /// @sa https://json.nlohmann.me/api/basic_json/patch/
     void patch_inplace(const basic_json& json_patch)
@@ -7053,18 +7117,18 @@ public:
         // 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)
+        typename json_pointer::template plain_steps<basic_json> steps;
+        const auto try_plain = [&result, &token, &steps](patch_operations operation, const string_t& path, const patch_members & members, const basic_json & val)
         {
-            if (path.empty() || path.find_first_of('~') != string_t::npos)
+            if (path.empty())
             {
                 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())
+            const basic_json* const value_ptr = members.value;
+            const basic_json& value = value_ptr != nullptr ? *value_ptr : val;
+            if (operation != patch_operations::remove && value_ptr == nullptr)
             {
                 return false;
             }
@@ -7073,7 +7137,7 @@ public:
             {
                 case patch_operations::replace:
                 {
-                    basic_json* const target = json_pointer::resolve_plain(&result, path, path.size(), token);
+                    basic_json* const target = json_pointer::resolve_plain(&result, path, path.size(), token, steps);
                     if (target == nullptr)
                     {
                         return false;
@@ -7084,7 +7148,7 @@ public:
 
                 case patch_operations::test:
                 {
-                    const basic_json* const target = json_pointer::resolve_plain(&result, path, path.size(), token);
+                    const basic_json* const target = json_pointer::resolve_plain(&result, path, path.size(), token, steps);
                     // a failing test is reported below
                     return target != nullptr && *target == value;
                 }
@@ -7104,13 +7168,17 @@ public:
                     }
                     --slash;
 
-                    basic_json* const parent = json_pointer::resolve_plain(&result, path, slash, token);
+                    basic_json* const parent = json_pointer::resolve_plain(&result, path, slash, token, steps);
                     if (parent == nullptr)
                     {
                         return false;
                     }
                     token.clear();
                     token.append(path.data() + slash + 1, path.size() - slash - 1);
+                    if (token.find_first_of('~') != string_t::npos)
+                    {
+                        return false;
+                    }
 
                     if (operation == patch_operations::add)
                     {
@@ -7166,31 +7234,32 @@ public:
             }
         };
 
+        // the name of the first member to check
+        const string_t op_member = "op";
+
         // iterate and apply the operations
         for (const auto& val : json_patch)
         {
             // wrapper to get a value for an operation
-            const auto get_value = [&val](const string_t& op,
-                                          const string_t& member,
+            const auto get_value = [&val](basic_json * found,
+                                          const string_t& op,
+                                          const char* member,
                                           bool string_type) -> basic_json &
             {
-                // find value
-                auto it = val.m_data.m_value.object->find(member);
-
                 // check if the desired value is present
-                if (JSON_HEDLEY_UNLIKELY(it == val.m_data.m_value.object->end()))
+                if (JSON_HEDLEY_UNLIKELY(found == nullptr))
                 {
-                    detail::throw_patch_missing_member(op, member, false, val);
+                    detail::throw_patch_missing_member(op, string_t(member), false, val);
                 }
 
                 // check if the result is of type string
-                if (JSON_HEDLEY_UNLIKELY(string_type && !it->second.is_string()))
+                if (JSON_HEDLEY_UNLIKELY(string_type && !found->is_string()))
                 {
-                    detail::throw_patch_missing_member(op, member, true, val);
+                    detail::throw_patch_missing_member(op, string_t(member), true, val);
                 }
 
                 // no error: return value
-                return it->second;
+                return *found;
             };
 
             // type check: every element of the array must be an object
@@ -7199,26 +7268,30 @@ public:
                 detail::throw_patch_not_an_array(val);
             }
 
+            const patch_members members = find_patch_members(val, std::is_same<typename object_t::key_type, string_t> {});
+
             // 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 string_t& op = *get_value(members.op, op_member, "op", true).m_data.m_value.string;
+            const string_t& path = *get_value(members.path, 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))
+            if (try_plain(operation, path, members, val))
             {
                 continue;
             }
 
+            // the general operations may change any container
+            steps.reset();
             json_pointer ptr(path);
 
             switch (operation)
             {
                 case patch_operations::add:
                 {
-                    operation_add(ptr, get_value("add", "value", false));
+                    operation_add(ptr, get_value(members.value, "add", "value", false));
                     break;
                 }
 
@@ -7231,13 +7304,13 @@ public:
                 case patch_operations::replace:
                 {
                     // the "path" location must exist - use at()
-                    result.at(ptr) = get_value("replace", "value", false);
+                    result.at(ptr) = get_value(members.value, "replace", "value", false);
                     break;
                 }
 
                 case patch_operations::move:
                 {
-                    const string_t& from_path = *get_value("move", "from", true).m_data.m_value.string;
+                    const string_t& from_path = *get_value(members.from, "move", "from", true).m_data.m_value.string;
                     json_pointer from_ptr(from_path);
 
                     if (JSON_HEDLEY_UNLIKELY(is_proper_prefix(from_ptr, ptr)))
@@ -7260,7 +7333,7 @@ public:
 
                 case patch_operations::copy:
                 {
-                    const string_t& from_path = *get_value("copy", "from", true).m_data.m_value.string;
+                    const string_t& from_path = *get_value(members.from, "copy", "from", true).m_data.m_value.string;
                     const json_pointer from_ptr(from_path);
 
                     // The copy is functionally identical to an "add"
@@ -7278,7 +7351,7 @@ public:
                     {
                         // check if "value" matches the one at "path"
                         // the "path" location must exist - use at()
-                        success = (result.at(ptr) == get_value("test", "value", false));
+                        success = (result.at(ptr) == get_value(members.value, "test", "value", false));
                     }
                     JSON_INTERNAL_CATCH (out_of_range&)
                     {
@@ -7370,13 +7443,18 @@ public:
     /// @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)
     {
+        // the keys are distinct and in the order of std::map; the members are
+        // added without looking them up
         basic_json entry(value_t::object);
-        entry["op"] = op;
-        entry["path"] = path;
+        auto& members = *entry.m_data.m_value.object;
+        typename object_t::iterator hint = members.end();
+        json_pointer::add_flattened(members, hint, string_t("op"), string_t(op), detail::priority_tag<2> {});
+        json_pointer::add_flattened(members, hint, string_t("path"), path, detail::priority_tag<2> {});
         if (value != nullptr)
         {
-            entry["value"] = *value;
+            json_pointer::add_flattened(members, hint, string_t("value"), *value, detail::priority_tag<2> {});
         }
+        entry.set_parents();
         result.push_back(std::move(entry));
     }
 
@@ -7398,6 +7476,50 @@ public:
         diff_operation(result, "add", path, &value);
     }
 
+    /// @brief the values in the target of the members of a source object, for the
+    ///        objects of up to 16 members without allocating
+    ///
+    /// reserve() must be called with the number of values that are added.
+    class diff_target_values
+    {
+      public:
+        diff_target_values() = default;
+        diff_target_values(const diff_target_values&) = delete;
+        diff_target_values& operator=(const diff_target_values&) = delete;
+        ~diff_target_values() = default;
+
+        void reserve(const std::size_t n)
+        {
+            if (n > inline_size)
+            {
+                large.resize(n);
+                items = large.data();
+            }
+        }
+
+        void push_back(const basic_json* value)
+        {
+            items[count++] = value;
+        }
+
+        std::size_t size() const noexcept
+        {
+            return count;
+        }
+
+        const basic_json* operator[](const std::size_t i) const noexcept
+        {
+            return items[i];
+        }
+
+      private:
+        static constexpr std::size_t inline_size = 16;
+        std::size_t count = 0;
+        const basic_json** items = inline_items;
+        std::vector<const basic_json*> large{}; // NOLINT(readability-redundant-member-init)
+        const basic_json* inline_items[inline_size]; // NOLINT(cppcoreguidelines-pro-type-member-init,hicpp-member-init)
+    };
+
     /// @brief append "/" and the decimal representation of @a index to @a path
     static void diff_append_index(string_t& path, std::size_t index)
     {
@@ -7478,8 +7600,9 @@ public:
     operations that remove every member of @a source and add every member of
     @a target to @a result, and returns false.
     */
+    template<typename TargetValues>
     static bool diff_object_keys(basic_json& result, const basic_json& source, const basic_json& target,
-                                 const string_t& path, std::vector<const basic_json*>& target_values,
+                                 const string_t& path, TargetValues& target_values,
                                  std::vector<const_iterator>& added)
     {
         // first pass: one lookup per source key
@@ -7693,7 +7816,7 @@ public:
 
             case value_t::object:
             {
-                std::vector<const basic_json*> target_values;
+                diff_target_values target_values;
                 std::vector<const_iterator> added;
                 if (diff_object_keys(result, source, target, path, target_values, added))
                 {

tests/src/unit-class_parser.cpp

@@ -2952,32 +2952,3 @@ TEST_CASE("diagnostic positions: value lifetime, input adapters, and SAX")
     }
 }
 #endif
-
-TEST_CASE("accept() agrees with parse() on floats around the overflow limit")
-{
-    // accept() does not convert a float that cannot overflow; the tokens
-    // around the limit (and beyond it) must still be rejected exactly as
-    // parse() rejects them
-    const char* const numbers[] =
-    {
-        "1e0", "123.456e-5", "1e-400", "-1e-400", "1e307", "1e308", "1e309", "-1e309",
-        "10e307", "100e307", "0.1e309", "0.1e310", "1E+308", "1E+309",
-        "1.7976931348623157e308", "1.7976931348623159e308", "1.8e308", "-1.7976931348623157e308",
-        "12345678901234567e291", "12345678901234567e292", "123456789012345678e290", "123456789012345678e291",
-        "1234567890123456789e289", "1234567890123456789e290", "9999999999999999999e289", "9999999999999999999e290",
-        "0.00000000000000000001e328", "0.00000000000000000001e329"
-    };
-
-    for (const char* number : numbers)
-    {
-        for (const std::string& text :
-                {
-                    std::string(number), "[" + std::string(number) + "]", "{\"a\":" + std::string(number) + "}"
-                })
-        {
-            INFO(text);
-            const bool parses = !json::parse(text, nullptr, false).is_discarded();
-            CHECK(json::accept(text) == parses);
-        }
-    }
-}

tests/src/unit-ordered_json.cpp

@@ -237,274 +237,3 @@ TEST_CASE("regression test for issue #5673 - ordered_json::emplace with a non-rv
         CHECK(oj.dump() == "{\"a\":1}");
     }
 }
-
-namespace
-{
-// the sizes around which the DOM parser changes how it stores the elements of
-// an array (16) and the members of an object in a vector (32, and 64 for the
-// key index)
-const std::size_t container_sizes[] = {0, 1, 2, 3, 15, 16, 17, 18, 31, 32, 33, 34, 63, 64, 65, 66, 200};
-
-template<typename Json>
-std::string array_text(const std::size_t n, const std::size_t depth)
-{
-    std::string text = "[";
-    for (std::size_t i = 0; i < n; ++i)
-    {
-        text += (i == 0 ? "" : ",");
-        // alternate scalars, empty containers and nested containers
-        switch (i % 4)
-        {
-            case 0:
-                text += std::to_string(i);
-                break;
-            case 1:
-                text += "\"s" + std::to_string(i) + "\"";
-                break;
-            case 2:
-                text += depth == 0 ? "[]" : array_text<Json>(n / 2, depth - 1);
-                break;
-            default:
-                text += depth == 0 ? "{}" : "{\"a\":" + array_text<Json>(n / 3, depth - 1) + ",\"b\":null}";
-                break;
-        }
-    }
-    return text + "]";
-}
-
-template<typename Json>
-std::string object_text(const std::size_t n, const std::size_t depth, const bool duplicates)
-{
-    std::string text = "{";
-    for (std::size_t i = 0; i < n; ++i)
-    {
-        text += (i == 0 ? "" : ",");
-        text += "\"key" + std::to_string(i) + "\":";
-        switch (i % 4)
-        {
-            case 0:
-                text += std::to_string(i);
-                break;
-            case 1:
-                text += depth == 0 ? "[]" : array_text<Json>(n / 2, depth - 1);
-                break;
-            case 2:
-                text += depth == 0 ? "{}" : object_text<Json>(n / 2, depth - 1, duplicates);
-                break;
-            default:
-                text += "\"value\"";
-                break;
-        }
-    }
-    if (duplicates)
-    {
-        // keys that are there already, the first and the last one, with other values
-        text += n == 0 ? "" : ",";
-        text += "\"key0\":[1,2],\"key" + std::to_string(n - 1) + "\":{\"again\":true}";
-    }
-    return text + "}";
-}
-
-template<typename Json>
-void check_same_dump(const std::string& text)
-{
-    // the text is what dump() writes for the parsed value, and the value
-    // survives a second round trip: arrays keep their elements in order, an
-    // ordered_json keeps its members in order of appearance
-    const Json parsed = Json::parse(text);
-    const Json again = Json::parse(parsed.dump());
-    CHECK(parsed == again);
-    CHECK(parsed.dump() == again.dump());
-    CHECK(Json::accept(text));
-}
-} // namespace
-
-TEST_CASE("parsing containers of sizes around the limits of the DOM parser")
-{
-    SECTION("arrays")
-    {
-        for (const std::size_t n : container_sizes)
-        {
-            const std::string text = array_text<json>(n, 2);
-            INFO("size ", n);
-
-            const json parsed = json::parse(text);
-            CHECK(parsed.is_array());
-            CHECK(parsed.size() == n);
-            for (std::size_t i = 0; i < n; i += 4)
-            {
-                CHECK(parsed[i] == i);
-            }
-            check_same_dump<json>(text);
-            check_same_dump<ordered_json>(text);
-            CHECK(ordered_json::parse(text).dump() == parsed.dump());
-        }
-    }
-
-    SECTION("objects")
-    {
-        for (const bool duplicates :
-                {
-                    false, true
-                })
-        {
-            for (const std::size_t n : container_sizes)
-            {
-                const std::string text = object_text<json>(n, 2, duplicates);
-                INFO("size ", n, " duplicates ", duplicates);
-
-                const json parsed = json::parse(text);
-                const ordered_json ordered = ordered_json::parse(text);
-                CHECK(parsed.is_object());
-                CHECK(ordered.is_object());
-                CHECK(parsed.size() == ordered.size());
-                // the same members, in the order of their first appearance
-                std::size_t i = 0;
-                for (auto it = ordered.begin(); it != ordered.end(); ++it, ++i)
-                {
-                    if (i < n)
-                    {
-                        CHECK(it.key() == "key" + std::to_string(i));
-                    }
-                    CHECK(parsed.at(it.key()) == json(it.value()));
-                }
-                if (duplicates && n > 1)
-                {
-                    // the later value replaced the earlier one in its place
-                    CHECK(ordered.at("key0") == ordered_json::parse("[1,2]"));
-                    CHECK(ordered.at("key" + std::to_string(n - 1)) == ordered_json::parse("{\"again\":true}"));
-                    CHECK(ordered.begin().key() == "key0");
-                    CHECK(ordered.size() == n);
-                }
-                check_same_dump<json>(text);
-                check_same_dump<ordered_json>(text);
-            }
-        }
-    }
-
-    SECTION("objects with many different and repeated keys")
-    {
-        // 300 members of which a third repeat an earlier key
-        std::string text = "{";
-        for (std::size_t i = 0; i < 300; ++i)
-        {
-            text += (i == 0 ? "" : ",");
-            text += "\"k" + std::to_string(i % 200) + "\":" + std::to_string(i);
-        }
-        text += "}";
-
-        const ordered_json ordered = ordered_json::parse(text);
-        const json parsed = json::parse(text);
-        CHECK(ordered.size() == 200);
-        CHECK(parsed.size() == 200);
-        std::size_t i = 0;
-        for (auto it = ordered.begin(); it != ordered.end(); ++it, ++i)
-        {
-            CHECK(it.key() == "k" + std::to_string(i));
-            // the last value written
-            CHECK(it.value() == (i < 100 ? i + 200 : i));
-            CHECK(parsed.at(it.key()) == json(it.value()));
-        }
-    }
-}
-
-namespace
-{
-// a deterministic source of structure for parsing tests: builds a JSON text
-// and, at the same time, the value it has to parse to
-class tree_generator
-{
-  public:
-    explicit tree_generator(std::uint32_t seed) : state(seed) {}
-
-    template<typename Json>
-    Json make(std::string& text, const std::size_t depth)
-    {
-        switch (next(depth == 0 ? 5 : 9))
-        {
-            case 0:
-                text += "null";
-                return Json(nullptr);
-            case 1:
-                text += "true";
-                return Json(true);
-            case 2:
-            {
-                const int n = static_cast<int>(next(2000)) - 1000;
-                text += std::to_string(n);
-                return Json(n);
-            }
-            case 3:
-                text += "\"text\"";
-                return Json("text");
-            case 4:
-                text += "2.5";
-                return Json(2.5);
-            case 5:
-            case 6:
-            case 7:
-            {
-                Json array = Json::array();
-                text += "[";
-                const std::size_t n = size();
-                for (std::size_t i = 0; i < n; ++i)
-                {
-                    text += (i == 0 ? "" : ",");
-                    array.push_back(make<Json>(text, depth - 1));
-                }
-                text += "]";
-                return array;
-            }
-            default:
-            {
-                Json object = Json::object();
-                text += "{";
-                const std::size_t n = size();
-                for (std::size_t i = 0; i < n; ++i)
-                {
-                    const std::string key = "k" + std::to_string(i);
-                    text += (i == 0 ? "\"" : ",\"") + key + "\":";
-                    object[key] = make<Json>(text, depth - 1);
-                }
-                text += "}";
-                return object;
-            }
-        }
-    }
-
-  private:
-    std::uint32_t next(const std::uint32_t bound)
-    {
-        state = state * 1664525U + 1013904223U;
-        return (state >> 8) % bound;
-    }
-
-    std::size_t size()
-    {
-        return container_sizes[next(sizeof(container_sizes) / sizeof(*container_sizes))];
-    }
-
-    std::uint32_t state;
-};
-} // namespace
-
-TEST_CASE("parsing random trees of arrays and objects")
-{
-    for (std::uint32_t seed = 1; seed <= 150; ++seed)
-    {
-        INFO("seed ", seed);
-
-        std::string text;
-        std::string ordered_text;
-        const json expected = tree_generator(seed).make<json>(text, 3);
-        const ordered_json ordered_expected = tree_generator(seed).make<ordered_json>(ordered_text, 3);
-        CHECK(text == ordered_text);
-
-        CHECK(json::parse(text) == expected);
-        CHECK(json::accept(text));
-        const ordered_json ordered = ordered_json::parse(text);
-        CHECK(ordered == ordered_expected);
-        CHECK(ordered.dump() == ordered_expected.dump());
-        CHECK(json::parse(text).dump() == expected.dump());
-    }
-}