Move the JSON pointer throw sites into out-of-line helpers

Messages, ids and exception types are unchanged.

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

include/nlohmann/detail/json_pointer.hpp

@@ -17,7 +17,6 @@
 #endif  // JSON_NO_IO
 #include <limits> // max
 #include <map> // map
-#include <numeric> // accumulate
 #include <string> // string
 #include <utility> // move
 #include <vector> // vector
@@ -69,12 +68,21 @@ class json_pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/to_string/
     string_t to_string() const
     {
-        return std::accumulate(reference_tokens.begin(), reference_tokens.end(),
+        // one buffer: every token adds its escaped form (at least its length) and a slash
-                               string_t{},
+        std::size_t length = 0;
-                               [](const string_t& a, const string_t& b)
+        for (const auto& reference_token : reference_tokens)
         {
-            return detail::concat<string_t>(a, '/', detail::escape(b));
+            length += reference_token.size() + 1;
-        });
+        }
+
+        string_t result;
+        result.reserve(length);
+        for (const auto& reference_token : reference_tokens)
+        {
+            result.append("/", 1);
+            detail::escape_into(result, reference_token);
+        }
+        return result;
     }
 
     /// @brief return a string representation of the JSON pointer
@@ -129,21 +137,29 @@ class json_pointer
     friend json_pointer operator/(const json_pointer& lhs,
                                   const json_pointer& rhs)
     {
-        return json_pointer(lhs) /= rhs;
+        json_pointer result;
+        result.reference_tokens.reserve(lhs.reference_tokens.size() + rhs.reference_tokens.size());
+        result.reference_tokens.insert(result.reference_tokens.end(), lhs.reference_tokens.begin(), lhs.reference_tokens.end());
+        result.reference_tokens.insert(result.reference_tokens.end(), rhs.reference_tokens.begin(), rhs.reference_tokens.end());
+        return result;
     }
 
     /// @brief create a new JSON pointer by appending the unescaped token at the end of the JSON pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/operator_slash/
     friend json_pointer operator/(const json_pointer& lhs, string_t token) // NOLINT(performance-unnecessary-value-param)
     {
-        return json_pointer(lhs) /= std::move(token);
+        json_pointer result;
+        result.reference_tokens.reserve(lhs.reference_tokens.size() + 1);
+        result.reference_tokens.insert(result.reference_tokens.end(), lhs.reference_tokens.begin(), lhs.reference_tokens.end());
+        result.reference_tokens.push_back(std::move(token));
+        return result;
     }
 
     /// @brief create a new JSON pointer by appending the array-index-token at the end of the JSON pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/operator_slash/
     friend json_pointer operator/(const json_pointer& lhs, std::size_t array_idx)
     {
-        return json_pointer(lhs) /= array_idx;
+        return lhs / detail::to_string<string_t>(array_idx);
     }
 
     /// @brief returns the parent of this JSON pointer
@@ -155,8 +171,9 @@ class json_pointer
             return *this;
         }
 
-        json_pointer res = *this;
+        json_pointer res;
-        res.pop_back();
+        res.reference_tokens.reserve(reference_tokens.size() - 1);
+        res.reference_tokens.insert(res.reference_tokens.end(), reference_tokens.begin(), reference_tokens.end() - 1);
         return res;
     }
 
@@ -244,21 +261,76 @@ class json_pointer
     }
 
   private:
+    // The throw sites below are kept out of line, so that the hot functions neither
+    // contain the message construction nor the cleanup code that comes with it.
+
     /// @throw out_of_range.405 always
-    JSON_HEDLEY_NO_RETURN static void throw_no_parent()
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_no_parent()
     {
         JSON_THROW(detail::out_of_range::create(detail::exception_id::patch_on_root, "JSON pointer has no parent", nullptr));
     }
 
     /// @throw out_of_range.404 always
     template<typename BasicJsonContext>
-    JSON_HEDLEY_NO_RETURN static void throw_unresolved(const string_t& reference_token, BasicJsonContext context)
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_unresolved(const string_t& reference_token, BasicJsonContext context)
     {
         static_cast<void>(reference_token); // unused when JSON_NOEXCEPTION is defined
         static_cast<void>(context);
         JSON_THROW(detail::out_of_range::create(detail::exception_id::pointer_unresolved, detail::concat("unresolved reference token '", reference_token, "'"), context));
     }
 
+    /// @throw out_of_range.402 always
+    template<typename BasicJsonContext>
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_past_the_end(std::size_t size, BasicJsonContext context)
+    {
+        static_cast<void>(size); // unused when JSON_NOEXCEPTION is defined
+        static_cast<void>(context);
+        JSON_THROW(detail::out_of_range::create(detail::exception_id::pointer_past_the_end_index, detail::concat("array index '-' (", std::to_string(size), ") is out of range"), context));
+    }
+
+    /// @throw out_of_range.401 always
+    template<typename BasicJsonContext>
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_index_out_of_range(std::size_t idx, BasicJsonContext context)
+    {
+        static_cast<void>(idx); // unused when JSON_NOEXCEPTION is defined
+        static_cast<void>(context);
+        JSON_THROW(detail::out_of_range::create(detail::exception_id::array_index_out_of_range, detail::concat("array index ", std::to_string(idx), " is out of range"), context));
+    }
+
+    /// @throw parse_error.106 always
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_leading_zero(const string_t& s)
+    {
+        static_cast<void>(s); // unused when JSON_NOEXCEPTION is defined
+        JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_index_leading_zero, 0, detail::concat("array index '", s, "' must not begin with '0'"), nullptr));
+    }
+
+    /// @throw parse_error.109 always
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_not_a_number(const string_t& s)
+    {
+        static_cast<void>(s); // unused when JSON_NOEXCEPTION is defined
+        JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_index_not_a_number, 0, detail::concat("array index '", s, "' is not a number"), nullptr));
+    }
+
+    /// @throw out_of_range.410 always
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_exceeds_size_type(const string_t& s)
+    {
+        static_cast<void>(s); // unused when JSON_NOEXCEPTION is defined
+        JSON_THROW(detail::out_of_range::create(detail::exception_id::value_out_of_range, detail::concat("array index ", s, " exceeds size_type"), nullptr));
+    }
+
+    /// @throw parse_error.107 always
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_missing_slash(const string_t& reference_string)
+    {
+        static_cast<void>(reference_string); // unused when JSON_NOEXCEPTION is defined
+        JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_missing_slash, 1, detail::concat("JSON pointer must be empty or begin with '/' - was: '", reference_string, "'"), nullptr));
+    }
+
+    /// @throw parse_error.108 always
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_invalid_escape()
+    {
+        JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_invalid_escape, 0, "escape character '~' must be followed with '0' or '1'", nullptr));
+    }
+
     /*!
     @brief result of @ref parse_array_index
 
@@ -305,6 +377,30 @@ class json_pointer
             return array_index_status::not_a_number;
         }
 
+        // fast path: up to 18 decimal digits cannot overflow unsigned long long or
+        // size_type (9 digits for a 32-bit size_type), so strtoull and errno are not needed
+        constexpr std::size_t max_fast_digits = sizeof(size_type) >= 8 ? 18 : 9;
+        if (!s.empty() && s.size() <= max_fast_digits)
+        {
+            size_type acc = 0;
+            bool all_digits = true;
+            for (std::size_t i = 0; i < s.size(); ++i)
+            {
+                const char c = s[i];
+                if (JSON_HEDLEY_UNLIKELY(c < '0' || c > '9'))
+                {
+                    all_digits = false;
+                    break;
+                }
+                acc = static_cast<size_type>(acc * 10 + static_cast<size_type>(c - '0'));
+            }
+            if (JSON_HEDLEY_LIKELY(all_digits))
+            {
+                idx = acc;
+                return array_index_status::ok;
+            }
+        }
+
         const char* p = s.data();
         char* p_end = nullptr; // NOLINT(misc-const-correctness)
         errno = 0; // strtoull doesn't reset errno
@@ -343,16 +439,14 @@ class json_pointer
         typename BasicJsonType::size_type idx{};
         switch (parse_array_index<BasicJsonType>(s, idx))
         {
-            // the branches differ in their messages, not after JSON_THROW's expansion
-            // NOLINTNEXTLINE(bugprone-branch-clone)
             case array_index_status::leading_zero:
-                JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_index_leading_zero, 0, detail::concat("array index '", s, "' must not begin with '0'"), nullptr));
+                throw_leading_zero(s);
             case array_index_status::not_a_number:
-                JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_index_not_a_number, 0, detail::concat("array index '", s, "' is not a number"), nullptr));
+                throw_not_a_number(s);
             case array_index_status::unresolved:
                 throw_unresolved(s, nullptr);
             case array_index_status::exceeds_size_type:
-                JSON_THROW(detail::out_of_range::create(detail::exception_id::value_out_of_range, detail::concat("array index ", s, " exceeds size_type"), nullptr));
+                throw_exceeds_size_type(s);
             case array_index_status::ok:
             default:
                 break;
@@ -361,6 +455,83 @@ class json_pointer
         return idx;
     }
 
+    /*!
+    @brief compare with a JSON pointer string without splitting it into tokens
+
+    @throw parse_error.107  if the string is not empty or begins with '/'
+    @throw parse_error.108  if character '~' is not followed by '0' or '1'
+    */
+    bool equals_string(const string_t& reference_string) const
+    {
+        if (reference_string.empty())
+        {
+            return reference_tokens.empty();
+        }
+
+        if (JSON_HEDLEY_UNLIKELY(reference_string[0] != '/'))
+        {
+            throw_missing_slash(reference_string);
+        }
+
+        // the whole string is validated, whether or not it matches
+        const std::size_t size = reference_string.size();
+        for (std::size_t pos = reference_string.find_first_of('~');
+                pos != string_t::npos;
+                pos = reference_string.find_first_of('~', pos + 1))
+        {
+            if (JSON_HEDLEY_UNLIKELY(pos == size - 1 || (reference_string[pos + 1] != '0' && reference_string[pos + 1] != '1')))
+            {
+                throw_invalid_escape();
+            }
+        }
+
+        // compare token by token, unescaping the string on the fly
+        std::size_t pos = 0; // the slash in front of the next token
+        for (const auto& reference_token : reference_tokens)
+        {
+            if (pos >= size)
+            {
+                return false;
+            }
+
+            std::size_t i = pos + 1;
+            std::size_t j = 0;
+            const std::size_t token_size = reference_token.size();
+            while (i < size && reference_string[i] != '/')
+            {
+                char c = reference_string[i++];
+                if (c == '~')
+                {
+                    c = (reference_string[i++] == '0') ? '~' : '/';
+                }
+                if (j == token_size || reference_token[j] != c)
+                {
+                    return false;
+                }
+                ++j;
+            }
+            if (j != token_size)
+            {
+                return false;
+            }
+            pos = i;
+        }
+        return pos == size;
+    }
+
+    /// @brief object member access with a key that is only copied if it is inserted
+    template<typename BasicJsonType>
+    static BasicJsonType& object_member(BasicJsonType& object, const string_t& key)
+    {
+        auto& members = *object.m_data.m_value.object;
+        const auto it = members.find(key);
+        if (it != members.end())
+        {
+            return it->second;
+        }
+        return object.operator[](key);
+    }
+
   JSON_PRIVATE_UNLESS_TESTED:
     json_pointer top() const
     {
@@ -404,23 +575,26 @@ class json_pointer
 
         // 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, string_t&& reference_token)
+        std::size_t add_child(std::size_t id, const string_t& reference_token)
         {
             if (reference_token == "0")
             {
                 is_array[id] = true;
             }
 
+            // shared prefixes are found without copying the token
+            const auto found = children[id].find(reference_token);
+            if (found != children[id].end())
+            {
+                return found->second;
+            }
+
             // read the number before the emplace_back below, which may
             // reallocate children and invalidate the iterator
-            const std::size_t next = children.size();
+            const std::size_t child = children.size();
-            const auto inserted = children[id].emplace(std::move(reference_token), next);
+            children[id].emplace(reference_token, child);
-            const std::size_t child = inserted.first->second;
+            children.emplace_back();
-            if (inserted.second)
+            is_array.push_back(false);
-            {
-                children.emplace_back();
-                is_array.push_back(false);
-            }
             return child;
         }
 
@@ -478,7 +652,7 @@ class json_pointer
                 case detail::value_t::object:
                 {
                     // create an entry in the object
-                    result = &result->operator[](reference_token);
+                    result = &object_member(*result, reference_token);
                     break;
                 }
 
@@ -558,7 +732,7 @@ class json_pointer
                 case detail::value_t::object:
                 {
                     // use unchecked object access
-                    ptr = &ptr->operator[](reference_token);
+                    ptr = &object_member(*ptr, reference_token);
                     break;
                 }
 
@@ -608,8 +782,13 @@ class json_pointer
             {
                 case detail::value_t::object:
                 {
-                    // note: at performs range check
+                    const auto it = ptr->m_data.m_value.object->find(reference_token);
-                    ptr = &ptr->at(reference_token);
+                    if (JSON_HEDLEY_UNLIKELY(it == ptr->m_data.m_value.object->end()))
+                    {
+                        // at() throws out_of_range.403 with the usual message
+                        ptr->at(reference_token);
+                    }
+                    ptr = &it->second;
                     break;
                 }
 
@@ -618,19 +797,16 @@ class json_pointer
                     if (JSON_HEDLEY_UNLIKELY(reference_token == "-"))
                     {
                         // "-" always fails the range check
-                        JSON_THROW(detail::out_of_range::create(detail::exception_id::pointer_past_the_end_index, detail::concat(
+                        throw_past_the_end(ptr->m_data.m_value.array->size(), ptr);
-                                "array index '-' (", std::to_string(ptr->m_data.m_value.array->size()),
-                                ") is out of range"), ptr));
                     }
 
                     const auto idx = array_index<BasicJsonType>(reference_token);
                     // Bounds check before access to avoid exception with JSON_NOEXCEPTION
                     if (JSON_HEDLEY_UNLIKELY(idx >= ptr->m_data.m_value.array->size()))
                     {
-                        JSON_THROW(detail::out_of_range::create(detail::exception_id::array_index_out_of_range, detail::concat(
+                        throw_index_out_of_range(idx, ptr);
-                                "array index ", std::to_string(idx), " is out of range"), ptr));
                     }
-                    ptr = &ptr->operator[](idx);
+                    ptr = &(*ptr->m_data.m_value.array)[idx];
                     break;
                 }
 
@@ -678,7 +854,9 @@ class json_pointer
                 {
                     // use unchecked object access; the const operator[]
                     // asserts that the key exists
-                    ptr = &ptr->operator[](reference_token);
+                    const auto it = ptr->m_data.m_value.object->find(reference_token);
+                    JSON_ASSERT(it != ptr->m_data.m_value.object->end());
+                    ptr = &it->second;
                     break;
                 }
 
@@ -687,12 +865,14 @@ class json_pointer
                     if (JSON_HEDLEY_UNLIKELY(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));
+                        throw_past_the_end(ptr->m_data.m_value.array->size(), ptr);
                     }
 
                     // use unchecked array access; the const operator[]
                     // asserts that the index exists
-                    ptr = &ptr->operator[](array_index<BasicJsonType>(reference_token));
+                    const auto idx = array_index<BasicJsonType>(reference_token);
+                    JSON_ASSERT(idx < ptr->m_data.m_value.array->size());
+                    ptr = &(*ptr->m_data.m_value.array)[idx];
                     break;
                 }
 
@@ -733,12 +913,12 @@ class json_pointer
             {
                 case detail::value_t::object:
                 {
-                    const auto it = ptr->find(reference_token);
+                    const auto it = ptr->m_data.m_value.object->find(reference_token);
-                    if (JSON_HEDLEY_UNLIKELY(it == ptr->end()))
+                    if (JSON_HEDLEY_UNLIKELY(it == ptr->m_data.m_value.object->end()))
                     {
                         return nullptr;
                     }
-                    ptr = &*it;
+                    ptr = &it->second;
                     break;
                 }
 
@@ -757,12 +937,10 @@ class json_pointer
                     typename BasicJsonType::size_type idx{};
                     switch (parse_array_index<BasicJsonType>(reference_token, idx))
                     {
-                        // the branches differ in their messages, not after JSON_THROW's expansion
-                        // NOLINTNEXTLINE(bugprone-branch-clone)
                         case array_index_status::leading_zero:
-                            JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_index_leading_zero, 0, detail::concat("array index '", reference_token, "' must not begin with '0'"), nullptr));
+                            throw_leading_zero(reference_token);
                         case array_index_status::not_a_number:
-                            JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_index_not_a_number, 0, detail::concat("array index '", reference_token, "' is not a number"), nullptr));
+                            throw_not_a_number(reference_token);
                         case array_index_status::unresolved:
                         case array_index_status::exceeds_size_type:
                             return nullptr;
@@ -775,7 +953,7 @@ class json_pointer
                     {
                         return nullptr;
                     }
-                    ptr = &ptr->operator[](idx);
+                    ptr = &(*ptr->m_data.m_value.array)[idx];
                     break;
                 }
 
@@ -808,13 +986,14 @@ class json_pointer
             {
                 case detail::value_t::object:
                 {
-                    if (!ptr->contains(reference_token))
+                    const auto it = ptr->m_data.m_value.object->find(reference_token);
+                    if (it == ptr->m_data.m_value.object->end())
                     {
                         // we did not find the key in the object
                         return false;
                     }
 
-                    ptr = &ptr->operator[](reference_token);
+                    ptr = &it->second;
                     break;
                 }
 
@@ -836,13 +1015,13 @@ class json_pointer
                         return false;
                     }
 
-                    if (idx >= ptr->size())
+                    if (idx >= ptr->m_data.m_value.array->size())
                     {
                         // index out of range
                         return false;
                     }
 
-                    ptr = &ptr->operator[](idx);
+                    ptr = &(*ptr->m_data.m_value.array)[idx];
                     break;
                 }
 
@@ -889,9 +1068,18 @@ class json_pointer
         // check if a nonempty reference string begins with slash
         if (JSON_HEDLEY_UNLIKELY(reference_string[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: '", reference_string, "'"), nullptr));
+            throw_missing_slash(reference_string);
         }
 
+        // every slash starts a reference token
+        const std::size_t size = reference_string.size();
+        std::size_t token_count = 0;
+        for (std::size_t i = 0; i < size; ++i)
+        {
+            token_count += (reference_string[i] == '/') ? 1 : 0;
+        }
+        result.reserve(token_count);
+
         // extract the reference tokens:
         // - slash: position of the last read slash (or end of string)
         // - start: position after the previous slash
@@ -913,25 +1101,29 @@ class json_pointer
             const auto count = (slash == string_t::npos ? reference_string.size() : slash) - start;
             auto reference_token = string_t(reference_string.data() + start, count);
 
-            // check reference tokens are properly escaped
+            // check reference tokens are properly escaped; a token without
-            for (std::size_t pos = reference_token.find_first_of('~');
+            // a '~' (the common case) needs neither check nor unescaping
-                    pos != string_t::npos;
+            std::size_t pos = reference_token.find_first_of('~');
-                    pos = reference_token.find_first_of('~', pos + 1))
+            if (pos != string_t::npos)
             {
-                JSON_ASSERT(reference_token[pos] == '~');
+                for (; pos != string_t::npos; pos = reference_token.find_first_of('~', pos + 1))
-
-                // ~ must be followed by 0 or 1
-                if (JSON_HEDLEY_UNLIKELY(pos == reference_token.size() - 1 ||
-                                         (reference_token[pos + 1] != '0' &&
-                                          reference_token[pos + 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));
+                    JSON_ASSERT(reference_token[pos] == '~');
+
+                    // ~ must be followed by 0 or 1
+                    if (JSON_HEDLEY_UNLIKELY(pos == reference_token.size() - 1 ||
+                                             (reference_token[pos + 1] != '0' &&
+                                              reference_token[pos + 1] != '1')))
+                    {
+                        throw_invalid_escape();
+                    }
                 }
+
+                detail::unescape(reference_token);
             }
 
             // finally, store the reference token
-            detail::unescape(reference_token);
+            result.push_back(std::move(reference_token));
-            result.push_back(reference_token);
         }
 
         return result;
@@ -1097,18 +1289,22 @@ class json_pointer
         // collect the pointer prefixes that have a reference token 0 among
         // their children; the values below them are arrays, all others are
         // objects (see prefix_tree)
+        // (each key is parsed once and the pointer kept for the second pass)
         prefix_tree tree;
+        std::vector<json_pointer> pointers;
+        pointers.reserve(value.m_data.m_value.object->size());
         for (const auto& element : *value.m_data.m_value.object)
         {
-            json_pointer ptr(element.first);
+            pointers.emplace_back(element.first);
             std::size_t id = 0;
-            for (auto& reference_token : ptr.reference_tokens)
+            for (const auto& reference_token : pointers.back().reference_tokens)
             {
-                id = tree.add_child(id, std::move(reference_token));
+                id = tree.add_child(id, reference_token);
             }
         }
 
         // iterate the JSON object values
+        std::size_t index = 0;
         for (const auto& element : *value.m_data.m_value.object)
         {
             if (JSON_HEDLEY_UNLIKELY(!element.second.is_primitive()))
@@ -1120,7 +1316,7 @@ class json_pointer
             // that if the JSON pointer is "" (i.e., points to the whole value),
             // function get_and_create returns a reference to the result itself.
             // An assignment will then create a primitive value.
-            json_pointer(element.first).get_and_create(result, tree) = element.second;
+            pointers[index++].get_and_create(result, tree) = element.second;
         }
 
         return result;
@@ -1159,7 +1355,7 @@ class json_pointer
         = delete;
 #else
     {
-        return *this == json_pointer(rhs);
+        return equals_string(rhs);
     }
 #endif
 
@@ -1243,7 +1439,7 @@ inline bool operator==(const json_pointer<RefStringTypeLhs>& lhs,
     = delete;
 #else
 {
-    return lhs == json_pointer<RefStringTypeLhs>(rhs);
+    return lhs.equals_string(rhs);
 }
 #endif
 
@@ -1256,7 +1452,7 @@ inline bool operator==(const StringType& lhs,
     = delete;
 #else
 {
-    return json_pointer<RefStringTypeRhs>(lhs) == rhs;
+    return rhs.equals_string(lhs);
 }
 #endif
 

include/nlohmann/detail/string_escape.hpp

@@ -9,6 +9,7 @@
 #pragma once
 
 #include <cstddef> // size_t
+#include <utility> // move
 
 #include <nlohmann/detail/abi_macros.hpp>
 
@@ -24,39 +25,46 @@ namespace detail
  * Note the order of escaping "~" to "~0" and "/" to "~1" is important.
  *
  * The string is rebuilt in a single pass, appending whole runs between the
- * characters that need escaping. Scanning with find_first_of() keeps the
+ * characters that need escaping, while repeated replace() calls would move
- * common case -- nothing to escape -- as fast as a single search, while
+ * the tail of the string once per escaped character. @ref escape_into appends
- * repeated replace() calls would move the tail of the string once per
+ * the escaped string to an existing one.
- * escaped character.
  */
+template<typename StringType>
+inline void escape_into(StringType& out, const StringType& s)
+{
+    const std::size_t size = s.size();
+    std::size_t run = 0;
+    for (std::size_t i = 0; i < size; ++i)
+    {
+        const char c = s[i];
+        if (c == '~' || c == '/')
+        {
+            out.append(s.data() + run, i - run);
+            out.append(c == '~' ? "~0" : "~1", 2);
+            run = i + 1;
+        }
+    }
+    out.append(s.data() + run, size - run);
+}
+
 template<typename StringType>
 inline StringType escape(const StringType& s)
 {
-    auto next_special = [&s](std::size_t from)
+    // a single scan for both special characters; nothing to escape is the common case
+    const std::size_t size = s.size();
+    std::size_t i = 0;
+    while (i < size && s[i] != '~' && s[i] != '/')
     {
-        const auto tilde = s.find_first_of('~', from);
+        ++i;
-        const auto slash = s.find_first_of('/', from);
+    }
-        return tilde < slash ? tilde : slash; // npos is the largest value
+    if (i == size)
-    };
-
-    auto pos = next_special(0);
-    if (pos == StringType::npos)
     {
         return s;
     }
 
     StringType result;
-    result.reserve(s.size() + 2);
+    result.reserve(size + 2);
-
+    escape_into(result, s);
-    std::size_t run = 0;
-    while (pos != StringType::npos)
-    {
-        result.append(s.data() + run, pos - run);
-        result.append(s[pos] == '~' ? "~0" : "~1", 2);
-        run = pos + 1;
-        pos = next_special(run);
-    }
-    result.append(s.data() + run, s.size() - run);
     return result;
 }
 
@@ -101,7 +109,7 @@ inline void unescape(StringType& s)
         pos = s.find_first_of('~', run);
     }
     result.append(s.data() + run, s.size() - run);
-    s = result;
+    s = std::move(result);
 }
 
 }  // namespace detail

include/nlohmann/json.hpp

@@ -6562,24 +6562,18 @@ public:
         };
 
         // wrapper for "add" operation; add value at ptr
-        const auto operation_add = [&result](json_pointer & ptr, const basic_json & val)
+        const auto operation_add = [&result](json_pointer & ptr, basic_json val)
         {
             // adding to the root of the target document means replacing it
             if (ptr.empty())
             {
-                result = val;
+                result = std::move(val);
                 return;
             }
 
-            // make sure the top element of the pointer exists
+            // get reference to the parent of the JSON pointer ptr; a missing
-            json_pointer const top_pointer = ptr.top();
+            // parent (or one of its ancestors) is reported by at()
-            if (top_pointer != ptr)
+            auto last_path = std::move(ptr.reference_tokens.back());
-            {
-                result.at(top_pointer);
-            }
-
-            // get reference to the parent of the JSON pointer ptr
-            const auto last_path = ptr.back();
             ptr.pop_back();
             // parent must exist when performing patch add per RFC6902 specs
             basic_json& parent = result.at(ptr);
@@ -6590,7 +6584,7 @@ public:
                 case value_t::object:
                 {
                     // use operator[] to add value
-                    parent[last_path] = val;
+                    parent[std::move(last_path)] = std::move(val);
                     break;
                 }
 
@@ -6599,7 +6593,7 @@ public:
                     if (last_path == "-")
                     {
                         // special case: append to back
-                        parent.push_back(val);
+                        parent.push_back(std::move(val));
                     }
                     else
                     {
@@ -6611,7 +6605,7 @@ public:
                         }
 
                         // default case: insert add offset
-                        parent.insert(parent.begin() + static_cast<difference_type>(idx), val);
+                        parent.insert(parent.begin() + static_cast<difference_type>(idx), std::move(val));
                     }
                     break;
                 }
@@ -6634,7 +6628,8 @@ public:
         const auto operation_remove = [this, & result](json_pointer & ptr)
         {
             // get reference to the parent of the JSON pointer ptr
-            const auto last_path = ptr.back();
+            static_cast<void>(ptr.back()); // throws out_of_range.405 if ptr is the root
+            const auto last_path = std::move(ptr.reference_tokens.back());
             ptr.pop_back();
             basic_json& parent = result.at(ptr);
 
@@ -6734,8 +6729,8 @@ public:
             }
 
             // collect mandatory members
-            const auto op = get_value("op", "op", true).template get<string_t>();
+            const string_t& op = *get_value("op", "op", true).m_data.m_value.string;
-            const auto path = get_value(op, "path", true).template get<string_t>();
+            const string_t& path = *get_value(op, "path", true).m_data.m_value.string;
             json_pointer ptr(path);
 
             switch (get_op(op))
@@ -6761,7 +6756,7 @@ public:
 
                 case patch_operations::move:
                 {
-                    const auto from_path = get_value("move", "from", true).template get<string_t>();
+                    const string_t& from_path = *get_value("move", "from", true).m_data.m_value.string;
                     json_pointer from_ptr(from_path);
 
                     if (JSON_HEDLEY_UNLIKELY(is_proper_prefix(from_ptr, ptr)))
@@ -6770,29 +6765,28 @@ public:
                     }
 
                     // the "from" location must exist - use at()
-                    basic_json const v = result.at(from_ptr);
+                    // a root "from" is rejected by operation_remove below, which must leave result intact
+                    basic_json v = from_ptr.empty() ? basic_json(result) : std::move(result.at(from_ptr));
 
                     // The move operation is functionally identical to a
                     // "remove" operation on the "from" location, followed
                     // immediately by an "add" operation at the target
                     // location with the value that was just removed.
                     operation_remove(from_ptr);
-                    operation_add(ptr, v);
+                    operation_add(ptr, std::move(v));
                     break;
                 }
 
                 case patch_operations::copy:
                 {
-                    const auto from_path = get_value("copy", "from", true).template get<string_t>();
+                    const string_t& from_path = *get_value("copy", "from", true).m_data.m_value.string;
                     const json_pointer from_ptr(from_path);
 
-                    // the "from" location must exist - use at()
-                    basic_json const v = result.at(from_ptr);
-
                     // The copy is functionally identical to an "add"
                     // operation at the target location using the value
-                    // specified in the "from" member.
+                    // specified in the "from" member; the "from" location
-                    operation_add(ptr, v);
+                    // must exist - use at()
+                    operation_add(ptr, result.at(from_ptr));
                     break;
                 }
 

single_include/nlohmann/json.hpp

@@ -3415,6 +3415,7 @@ NLOHMANN_JSON_NAMESPACE_END
 
 
 #include <cstddef> // size_t
+#include <utility> // move
 
 // #include <nlohmann/detail/abi_macros.hpp>
 
@@ -3431,39 +3432,46 @@ namespace detail
  * Note the order of escaping "~" to "~0" and "/" to "~1" is important.
  *
  * The string is rebuilt in a single pass, appending whole runs between the
- * characters that need escaping. Scanning with find_first_of() keeps the
+ * characters that need escaping, while repeated replace() calls would move
- * common case -- nothing to escape -- as fast as a single search, while
+ * the tail of the string once per escaped character. @ref escape_into appends
- * repeated replace() calls would move the tail of the string once per
+ * the escaped string to an existing one.
- * escaped character.
  */
+template<typename StringType>
+inline void escape_into(StringType& out, const StringType& s)
+{
+    const std::size_t size = s.size();
+    std::size_t run = 0;
+    for (std::size_t i = 0; i < size; ++i)
+    {
+        const char c = s[i];
+        if (c == '~' || c == '/')
+        {
+            out.append(s.data() + run, i - run);
+            out.append(c == '~' ? "~0" : "~1", 2);
+            run = i + 1;
+        }
+    }
+    out.append(s.data() + run, size - run);
+}
+
 template<typename StringType>
 inline StringType escape(const StringType& s)
 {
-    auto next_special = [&s](std::size_t from)
+    // a single scan for both special characters; nothing to escape is the common case
+    const std::size_t size = s.size();
+    std::size_t i = 0;
+    while (i < size && s[i] != '~' && s[i] != '/')
     {
-        const auto tilde = s.find_first_of('~', from);
+        ++i;
-        const auto slash = s.find_first_of('/', from);
+    }
-        return tilde < slash ? tilde : slash; // npos is the largest value
+    if (i == size)
-    };
-
-    auto pos = next_special(0);
-    if (pos == StringType::npos)
     {
         return s;
     }
 
     StringType result;
-    result.reserve(s.size() + 2);
+    result.reserve(size + 2);
-
+    escape_into(result, s);
-    std::size_t run = 0;
-    while (pos != StringType::npos)
-    {
-        result.append(s.data() + run, pos - run);
-        result.append(s[pos] == '~' ? "~0" : "~1", 2);
-        run = pos + 1;
-        pos = next_special(run);
-    }
-    result.append(s.data() + run, s.size() - run);
     return result;
 }
 
@@ -3508,7 +3516,7 @@ inline void unescape(StringType& s)
         pos = s.find_first_of('~', run);
     }
     result.append(s.data() + run, s.size() - run);
-    s = result;
+    s = std::move(result);
 }
 
 }  // namespace detail
@@ -20632,7 +20640,6 @@ NLOHMANN_JSON_NAMESPACE_END
 #endif  // JSON_NO_IO
 #include <limits> // max
 #include <map> // map
-#include <numeric> // accumulate
 #include <string> // string
 #include <utility> // move
 #include <vector> // vector
@@ -20690,12 +20697,21 @@ class json_pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/to_string/
     string_t to_string() const
     {
-        return std::accumulate(reference_tokens.begin(), reference_tokens.end(),
+        // one buffer: every token adds its escaped form (at least its length) and a slash
-                               string_t{},
+        std::size_t length = 0;
-                               [](const string_t& a, const string_t& b)
+        for (const auto& reference_token : reference_tokens)
         {
-            return detail::concat<string_t>(a, '/', detail::escape(b));
+            length += reference_token.size() + 1;
-        });
+        }
+
+        string_t result;
+        result.reserve(length);
+        for (const auto& reference_token : reference_tokens)
+        {
+            result.append("/", 1);
+            detail::escape_into(result, reference_token);
+        }
+        return result;
     }
 
     /// @brief return a string representation of the JSON pointer
@@ -20750,21 +20766,29 @@ class json_pointer
     friend json_pointer operator/(const json_pointer& lhs,
                                   const json_pointer& rhs)
     {
-        return json_pointer(lhs) /= rhs;
+        json_pointer result;
+        result.reference_tokens.reserve(lhs.reference_tokens.size() + rhs.reference_tokens.size());
+        result.reference_tokens.insert(result.reference_tokens.end(), lhs.reference_tokens.begin(), lhs.reference_tokens.end());
+        result.reference_tokens.insert(result.reference_tokens.end(), rhs.reference_tokens.begin(), rhs.reference_tokens.end());
+        return result;
     }
 
     /// @brief create a new JSON pointer by appending the unescaped token at the end of the JSON pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/operator_slash/
     friend json_pointer operator/(const json_pointer& lhs, string_t token) // NOLINT(performance-unnecessary-value-param)
     {
-        return json_pointer(lhs) /= std::move(token);
+        json_pointer result;
+        result.reference_tokens.reserve(lhs.reference_tokens.size() + 1);
+        result.reference_tokens.insert(result.reference_tokens.end(), lhs.reference_tokens.begin(), lhs.reference_tokens.end());
+        result.reference_tokens.push_back(std::move(token));
+        return result;
     }
 
     /// @brief create a new JSON pointer by appending the array-index-token at the end of the JSON pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/operator_slash/
     friend json_pointer operator/(const json_pointer& lhs, std::size_t array_idx)
     {
-        return json_pointer(lhs) /= array_idx;
+        return lhs / detail::to_string<string_t>(array_idx);
     }
 
     /// @brief returns the parent of this JSON pointer
@@ -20776,8 +20800,9 @@ class json_pointer
             return *this;
         }
 
-        json_pointer res = *this;
+        json_pointer res;
-        res.pop_back();
+        res.reference_tokens.reserve(reference_tokens.size() - 1);
+        res.reference_tokens.insert(res.reference_tokens.end(), reference_tokens.begin(), reference_tokens.end() - 1);
         return res;
     }
 
@@ -20865,21 +20890,76 @@ class json_pointer
     }
 
   private:
+    // The throw sites below are kept out of line, so that the hot functions neither
+    // contain the message construction nor the cleanup code that comes with it.
+
     /// @throw out_of_range.405 always
-    JSON_HEDLEY_NO_RETURN static void throw_no_parent()
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_no_parent()
     {
         JSON_THROW(detail::out_of_range::create(detail::exception_id::patch_on_root, "JSON pointer has no parent", nullptr));
     }
 
     /// @throw out_of_range.404 always
     template<typename BasicJsonContext>
-    JSON_HEDLEY_NO_RETURN static void throw_unresolved(const string_t& reference_token, BasicJsonContext context)
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_unresolved(const string_t& reference_token, BasicJsonContext context)
     {
         static_cast<void>(reference_token); // unused when JSON_NOEXCEPTION is defined
         static_cast<void>(context);
         JSON_THROW(detail::out_of_range::create(detail::exception_id::pointer_unresolved, detail::concat("unresolved reference token '", reference_token, "'"), context));
     }
 
+    /// @throw out_of_range.402 always
+    template<typename BasicJsonContext>
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_past_the_end(std::size_t size, BasicJsonContext context)
+    {
+        static_cast<void>(size); // unused when JSON_NOEXCEPTION is defined
+        static_cast<void>(context);
+        JSON_THROW(detail::out_of_range::create(detail::exception_id::pointer_past_the_end_index, detail::concat("array index '-' (", std::to_string(size), ") is out of range"), context));
+    }
+
+    /// @throw out_of_range.401 always
+    template<typename BasicJsonContext>
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_index_out_of_range(std::size_t idx, BasicJsonContext context)
+    {
+        static_cast<void>(idx); // unused when JSON_NOEXCEPTION is defined
+        static_cast<void>(context);
+        JSON_THROW(detail::out_of_range::create(detail::exception_id::array_index_out_of_range, detail::concat("array index ", std::to_string(idx), " is out of range"), context));
+    }
+
+    /// @throw parse_error.106 always
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_leading_zero(const string_t& s)
+    {
+        static_cast<void>(s); // unused when JSON_NOEXCEPTION is defined
+        JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_index_leading_zero, 0, detail::concat("array index '", s, "' must not begin with '0'"), nullptr));
+    }
+
+    /// @throw parse_error.109 always
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_not_a_number(const string_t& s)
+    {
+        static_cast<void>(s); // unused when JSON_NOEXCEPTION is defined
+        JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_index_not_a_number, 0, detail::concat("array index '", s, "' is not a number"), nullptr));
+    }
+
+    /// @throw out_of_range.410 always
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_exceeds_size_type(const string_t& s)
+    {
+        static_cast<void>(s); // unused when JSON_NOEXCEPTION is defined
+        JSON_THROW(detail::out_of_range::create(detail::exception_id::value_out_of_range, detail::concat("array index ", s, " exceeds size_type"), nullptr));
+    }
+
+    /// @throw parse_error.107 always
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_missing_slash(const string_t& reference_string)
+    {
+        static_cast<void>(reference_string); // unused when JSON_NOEXCEPTION is defined
+        JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_missing_slash, 1, detail::concat("JSON pointer must be empty or begin with '/' - was: '", reference_string, "'"), nullptr));
+    }
+
+    /// @throw parse_error.108 always
+    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_invalid_escape()
+    {
+        JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_invalid_escape, 0, "escape character '~' must be followed with '0' or '1'", nullptr));
+    }
+
     /*!
     @brief result of @ref parse_array_index
 
@@ -20926,6 +21006,30 @@ class json_pointer
             return array_index_status::not_a_number;
         }
 
+        // fast path: up to 18 decimal digits cannot overflow unsigned long long or
+        // size_type (9 digits for a 32-bit size_type), so strtoull and errno are not needed
+        constexpr std::size_t max_fast_digits = sizeof(size_type) >= 8 ? 18 : 9;
+        if (!s.empty() && s.size() <= max_fast_digits)
+        {
+            size_type acc = 0;
+            bool all_digits = true;
+            for (std::size_t i = 0; i < s.size(); ++i)
+            {
+                const char c = s[i];
+                if (JSON_HEDLEY_UNLIKELY(c < '0' || c > '9'))
+                {
+                    all_digits = false;
+                    break;
+                }
+                acc = static_cast<size_type>(acc * 10 + static_cast<size_type>(c - '0'));
+            }
+            if (JSON_HEDLEY_LIKELY(all_digits))
+            {
+                idx = acc;
+                return array_index_status::ok;
+            }
+        }
+
         const char* p = s.data();
         char* p_end = nullptr; // NOLINT(misc-const-correctness)
         errno = 0; // strtoull doesn't reset errno
@@ -20964,16 +21068,14 @@ class json_pointer
         typename BasicJsonType::size_type idx{};
         switch (parse_array_index<BasicJsonType>(s, idx))
         {
-            // the branches differ in their messages, not after JSON_THROW's expansion
-            // NOLINTNEXTLINE(bugprone-branch-clone)
             case array_index_status::leading_zero:
-                JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_index_leading_zero, 0, detail::concat("array index '", s, "' must not begin with '0'"), nullptr));
+                throw_leading_zero(s);
             case array_index_status::not_a_number:
-                JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_index_not_a_number, 0, detail::concat("array index '", s, "' is not a number"), nullptr));
+                throw_not_a_number(s);
             case array_index_status::unresolved:
                 throw_unresolved(s, nullptr);
             case array_index_status::exceeds_size_type:
-                JSON_THROW(detail::out_of_range::create(detail::exception_id::value_out_of_range, detail::concat("array index ", s, " exceeds size_type"), nullptr));
+                throw_exceeds_size_type(s);
             case array_index_status::ok:
             default:
                 break;
@@ -20982,6 +21084,83 @@ class json_pointer
         return idx;
     }
 
+    /*!
+    @brief compare with a JSON pointer string without splitting it into tokens
+
+    @throw parse_error.107  if the string is not empty or begins with '/'
+    @throw parse_error.108  if character '~' is not followed by '0' or '1'
+    */
+    bool equals_string(const string_t& reference_string) const
+    {
+        if (reference_string.empty())
+        {
+            return reference_tokens.empty();
+        }
+
+        if (JSON_HEDLEY_UNLIKELY(reference_string[0] != '/'))
+        {
+            throw_missing_slash(reference_string);
+        }
+
+        // the whole string is validated, whether or not it matches
+        const std::size_t size = reference_string.size();
+        for (std::size_t pos = reference_string.find_first_of('~');
+                pos != string_t::npos;
+                pos = reference_string.find_first_of('~', pos + 1))
+        {
+            if (JSON_HEDLEY_UNLIKELY(pos == size - 1 || (reference_string[pos + 1] != '0' && reference_string[pos + 1] != '1')))
+            {
+                throw_invalid_escape();
+            }
+        }
+
+        // compare token by token, unescaping the string on the fly
+        std::size_t pos = 0; // the slash in front of the next token
+        for (const auto& reference_token : reference_tokens)
+        {
+            if (pos >= size)
+            {
+                return false;
+            }
+
+            std::size_t i = pos + 1;
+            std::size_t j = 0;
+            const std::size_t token_size = reference_token.size();
+            while (i < size && reference_string[i] != '/')
+            {
+                char c = reference_string[i++];
+                if (c == '~')
+                {
+                    c = (reference_string[i++] == '0') ? '~' : '/';
+                }
+                if (j == token_size || reference_token[j] != c)
+                {
+                    return false;
+                }
+                ++j;
+            }
+            if (j != token_size)
+            {
+                return false;
+            }
+            pos = i;
+        }
+        return pos == size;
+    }
+
+    /// @brief object member access with a key that is only copied if it is inserted
+    template<typename BasicJsonType>
+    static BasicJsonType& object_member(BasicJsonType& object, const string_t& key)
+    {
+        auto& members = *object.m_data.m_value.object;
+        const auto it = members.find(key);
+        if (it != members.end())
+        {
+            return it->second;
+        }
+        return object.operator[](key);
+    }
+
   JSON_PRIVATE_UNLESS_TESTED:
     json_pointer top() const
     {
@@ -21025,23 +21204,26 @@ class json_pointer
 
         // 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, string_t&& reference_token)
+        std::size_t add_child(std::size_t id, const string_t& reference_token)
         {
             if (reference_token == "0")
             {
                 is_array[id] = true;
             }
 
+            // shared prefixes are found without copying the token
+            const auto found = children[id].find(reference_token);
+            if (found != children[id].end())
+            {
+                return found->second;
+            }
+
             // read the number before the emplace_back below, which may
             // reallocate children and invalidate the iterator
-            const std::size_t next = children.size();
+            const std::size_t child = children.size();
-            const auto inserted = children[id].emplace(std::move(reference_token), next);
+            children[id].emplace(reference_token, child);
-            const std::size_t child = inserted.first->second;
+            children.emplace_back();
-            if (inserted.second)
+            is_array.push_back(false);
-            {
-                children.emplace_back();
-                is_array.push_back(false);
-            }
             return child;
         }
 
@@ -21099,7 +21281,7 @@ class json_pointer
                 case detail::value_t::object:
                 {
                     // create an entry in the object
-                    result = &result->operator[](reference_token);
+                    result = &object_member(*result, reference_token);
                     break;
                 }
 
@@ -21179,7 +21361,7 @@ class json_pointer
                 case detail::value_t::object:
                 {
                     // use unchecked object access
-                    ptr = &ptr->operator[](reference_token);
+                    ptr = &object_member(*ptr, reference_token);
                     break;
                 }
 
@@ -21229,8 +21411,13 @@ class json_pointer
             {
                 case detail::value_t::object:
                 {
-                    // note: at performs range check
+                    const auto it = ptr->m_data.m_value.object->find(reference_token);
-                    ptr = &ptr->at(reference_token);
+                    if (JSON_HEDLEY_UNLIKELY(it == ptr->m_data.m_value.object->end()))
+                    {
+                        // at() throws out_of_range.403 with the usual message
+                        ptr->at(reference_token);
+                    }
+                    ptr = &it->second;
                     break;
                 }
 
@@ -21239,19 +21426,16 @@ class json_pointer
                     if (JSON_HEDLEY_UNLIKELY(reference_token == "-"))
                     {
                         // "-" always fails the range check
-                        JSON_THROW(detail::out_of_range::create(detail::exception_id::pointer_past_the_end_index, detail::concat(
+                        throw_past_the_end(ptr->m_data.m_value.array->size(), ptr);
-                                "array index '-' (", std::to_string(ptr->m_data.m_value.array->size()),
-                                ") is out of range"), ptr));
                     }
 
                     const auto idx = array_index<BasicJsonType>(reference_token);
                     // Bounds check before access to avoid exception with JSON_NOEXCEPTION
                     if (JSON_HEDLEY_UNLIKELY(idx >= ptr->m_data.m_value.array->size()))
                     {
-                        JSON_THROW(detail::out_of_range::create(detail::exception_id::array_index_out_of_range, detail::concat(
+                        throw_index_out_of_range(idx, ptr);
-                                "array index ", std::to_string(idx), " is out of range"), ptr));
                     }
-                    ptr = &ptr->operator[](idx);
+                    ptr = &(*ptr->m_data.m_value.array)[idx];
                     break;
                 }
 
@@ -21299,7 +21483,9 @@ class json_pointer
                 {
                     // use unchecked object access; the const operator[]
                     // asserts that the key exists
-                    ptr = &ptr->operator[](reference_token);
+                    const auto it = ptr->m_data.m_value.object->find(reference_token);
+                    JSON_ASSERT(it != ptr->m_data.m_value.object->end());
+                    ptr = &it->second;
                     break;
                 }
 
@@ -21308,12 +21494,14 @@ class json_pointer
                     if (JSON_HEDLEY_UNLIKELY(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));
+                        throw_past_the_end(ptr->m_data.m_value.array->size(), ptr);
                     }
 
                     // use unchecked array access; the const operator[]
                     // asserts that the index exists
-                    ptr = &ptr->operator[](array_index<BasicJsonType>(reference_token));
+                    const auto idx = array_index<BasicJsonType>(reference_token);
+                    JSON_ASSERT(idx < ptr->m_data.m_value.array->size());
+                    ptr = &(*ptr->m_data.m_value.array)[idx];
                     break;
                 }
 
@@ -21354,12 +21542,12 @@ class json_pointer
             {
                 case detail::value_t::object:
                 {
-                    const auto it = ptr->find(reference_token);
+                    const auto it = ptr->m_data.m_value.object->find(reference_token);
-                    if (JSON_HEDLEY_UNLIKELY(it == ptr->end()))
+                    if (JSON_HEDLEY_UNLIKELY(it == ptr->m_data.m_value.object->end()))
                     {
                         return nullptr;
                     }
-                    ptr = &*it;
+                    ptr = &it->second;
                     break;
                 }
 
@@ -21378,12 +21566,10 @@ class json_pointer
                     typename BasicJsonType::size_type idx{};
                     switch (parse_array_index<BasicJsonType>(reference_token, idx))
                     {
-                        // the branches differ in their messages, not after JSON_THROW's expansion
-                        // NOLINTNEXTLINE(bugprone-branch-clone)
                         case array_index_status::leading_zero:
-                            JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_index_leading_zero, 0, detail::concat("array index '", reference_token, "' must not begin with '0'"), nullptr));
+                            throw_leading_zero(reference_token);
                         case array_index_status::not_a_number:
-                            JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_index_not_a_number, 0, detail::concat("array index '", reference_token, "' is not a number"), nullptr));
+                            throw_not_a_number(reference_token);
                         case array_index_status::unresolved:
                         case array_index_status::exceeds_size_type:
                             return nullptr;
@@ -21396,7 +21582,7 @@ class json_pointer
                     {
                         return nullptr;
                     }
-                    ptr = &ptr->operator[](idx);
+                    ptr = &(*ptr->m_data.m_value.array)[idx];
                     break;
                 }
 
@@ -21429,13 +21615,14 @@ class json_pointer
             {
                 case detail::value_t::object:
                 {
-                    if (!ptr->contains(reference_token))
+                    const auto it = ptr->m_data.m_value.object->find(reference_token);
+                    if (it == ptr->m_data.m_value.object->end())
                     {
                         // we did not find the key in the object
                         return false;
                     }
 
-                    ptr = &ptr->operator[](reference_token);
+                    ptr = &it->second;
                     break;
                 }
 
@@ -21457,13 +21644,13 @@ class json_pointer
                         return false;
                     }
 
-                    if (idx >= ptr->size())
+                    if (idx >= ptr->m_data.m_value.array->size())
                     {
                         // index out of range
                         return false;
                     }
 
-                    ptr = &ptr->operator[](idx);
+                    ptr = &(*ptr->m_data.m_value.array)[idx];
                     break;
                 }
 
@@ -21510,9 +21697,18 @@ class json_pointer
         // check if a nonempty reference string begins with slash
         if (JSON_HEDLEY_UNLIKELY(reference_string[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: '", reference_string, "'"), nullptr));
+            throw_missing_slash(reference_string);
         }
 
+        // every slash starts a reference token
+        const std::size_t size = reference_string.size();
+        std::size_t token_count = 0;
+        for (std::size_t i = 0; i < size; ++i)
+        {
+            token_count += (reference_string[i] == '/') ? 1 : 0;
+        }
+        result.reserve(token_count);
+
         // extract the reference tokens:
         // - slash: position of the last read slash (or end of string)
         // - start: position after the previous slash
@@ -21534,25 +21730,29 @@ class json_pointer
             const auto count = (slash == string_t::npos ? reference_string.size() : slash) - start;
             auto reference_token = string_t(reference_string.data() + start, count);
 
-            // check reference tokens are properly escaped
+            // check reference tokens are properly escaped; a token without
-            for (std::size_t pos = reference_token.find_first_of('~');
+            // a '~' (the common case) needs neither check nor unescaping
-                    pos != string_t::npos;
+            std::size_t pos = reference_token.find_first_of('~');
-                    pos = reference_token.find_first_of('~', pos + 1))
+            if (pos != string_t::npos)
             {
-                JSON_ASSERT(reference_token[pos] == '~');
+                for (; pos != string_t::npos; pos = reference_token.find_first_of('~', pos + 1))
-
-                // ~ must be followed by 0 or 1
-                if (JSON_HEDLEY_UNLIKELY(pos == reference_token.size() - 1 ||
-                                         (reference_token[pos + 1] != '0' &&
-                                          reference_token[pos + 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));
+                    JSON_ASSERT(reference_token[pos] == '~');
+
+                    // ~ must be followed by 0 or 1
+                    if (JSON_HEDLEY_UNLIKELY(pos == reference_token.size() - 1 ||
+                                             (reference_token[pos + 1] != '0' &&
+                                              reference_token[pos + 1] != '1')))
+                    {
+                        throw_invalid_escape();
+                    }
                 }
+
+                detail::unescape(reference_token);
             }
 
             // finally, store the reference token
-            detail::unescape(reference_token);
+            result.push_back(std::move(reference_token));
-            result.push_back(reference_token);
         }
 
         return result;
@@ -21718,18 +21918,22 @@ class json_pointer
         // collect the pointer prefixes that have a reference token 0 among
         // their children; the values below them are arrays, all others are
         // objects (see prefix_tree)
+        // (each key is parsed once and the pointer kept for the second pass)
         prefix_tree tree;
+        std::vector<json_pointer> pointers;
+        pointers.reserve(value.m_data.m_value.object->size());
         for (const auto& element : *value.m_data.m_value.object)
         {
-            json_pointer ptr(element.first);
+            pointers.emplace_back(element.first);
             std::size_t id = 0;
-            for (auto& reference_token : ptr.reference_tokens)
+            for (const auto& reference_token : pointers.back().reference_tokens)
             {
-                id = tree.add_child(id, std::move(reference_token));
+                id = tree.add_child(id, reference_token);
             }
         }
 
         // iterate the JSON object values
+        std::size_t index = 0;
         for (const auto& element : *value.m_data.m_value.object)
         {
             if (JSON_HEDLEY_UNLIKELY(!element.second.is_primitive()))
@@ -21741,7 +21945,7 @@ class json_pointer
             // that if the JSON pointer is "" (i.e., points to the whole value),
             // function get_and_create returns a reference to the result itself.
             // An assignment will then create a primitive value.
-            json_pointer(element.first).get_and_create(result, tree) = element.second;
+            pointers[index++].get_and_create(result, tree) = element.second;
         }
 
         return result;
@@ -21780,7 +21984,7 @@ class json_pointer
         = delete;
 #else
     {
-        return *this == json_pointer(rhs);
+        return equals_string(rhs);
     }
 #endif
 
@@ -21864,7 +22068,7 @@ inline bool operator==(const json_pointer<RefStringTypeLhs>& lhs,
     = delete;
 #else
 {
-    return lhs == json_pointer<RefStringTypeLhs>(rhs);
+    return lhs.equals_string(rhs);
 }
 #endif
 
@@ -21877,7 +22081,7 @@ inline bool operator==(const StringType& lhs,
     = delete;
 #else
 {
-    return json_pointer<RefStringTypeRhs>(lhs) == rhs;
+    return rhs.equals_string(lhs);
 }
 #endif
 
@@ -35910,24 +36114,18 @@ public:
         };
 
         // wrapper for "add" operation; add value at ptr
-        const auto operation_add = [&result](json_pointer & ptr, const basic_json & val)
+        const auto operation_add = [&result](json_pointer & ptr, basic_json val)
         {
             // adding to the root of the target document means replacing it
             if (ptr.empty())
             {
-                result = val;
+                result = std::move(val);
                 return;
             }
 
-            // make sure the top element of the pointer exists
+            // get reference to the parent of the JSON pointer ptr; a missing
-            json_pointer const top_pointer = ptr.top();
+            // parent (or one of its ancestors) is reported by at()
-            if (top_pointer != ptr)
+            auto last_path = std::move(ptr.reference_tokens.back());
-            {
-                result.at(top_pointer);
-            }
-
-            // get reference to the parent of the JSON pointer ptr
-            const auto last_path = ptr.back();
             ptr.pop_back();
             // parent must exist when performing patch add per RFC6902 specs
             basic_json& parent = result.at(ptr);
@@ -35938,7 +36136,7 @@ public:
                 case value_t::object:
                 {
                     // use operator[] to add value
-                    parent[last_path] = val;
+                    parent[std::move(last_path)] = std::move(val);
                     break;
                 }
 
@@ -35947,7 +36145,7 @@ public:
                     if (last_path == "-")
                     {
                         // special case: append to back
-                        parent.push_back(val);
+                        parent.push_back(std::move(val));
                     }
                     else
                     {
@@ -35959,7 +36157,7 @@ public:
                         }
 
                         // default case: insert add offset
-                        parent.insert(parent.begin() + static_cast<difference_type>(idx), val);
+                        parent.insert(parent.begin() + static_cast<difference_type>(idx), std::move(val));
                     }
                     break;
                 }
@@ -35982,7 +36180,8 @@ public:
         const auto operation_remove = [this, & result](json_pointer & ptr)
         {
             // get reference to the parent of the JSON pointer ptr
-            const auto last_path = ptr.back();
+            static_cast<void>(ptr.back()); // throws out_of_range.405 if ptr is the root
+            const auto last_path = std::move(ptr.reference_tokens.back());
             ptr.pop_back();
             basic_json& parent = result.at(ptr);
 
@@ -36082,8 +36281,8 @@ public:
             }
 
             // collect mandatory members
-            const auto op = get_value("op", "op", true).template get<string_t>();
+            const string_t& op = *get_value("op", "op", true).m_data.m_value.string;
-            const auto path = get_value(op, "path", true).template get<string_t>();
+            const string_t& path = *get_value(op, "path", true).m_data.m_value.string;
             json_pointer ptr(path);
 
             switch (get_op(op))
@@ -36109,7 +36308,7 @@ public:
 
                 case patch_operations::move:
                 {
-                    const auto from_path = get_value("move", "from", true).template get<string_t>();
+                    const string_t& from_path = *get_value("move", "from", true).m_data.m_value.string;
                     json_pointer from_ptr(from_path);
 
                     if (JSON_HEDLEY_UNLIKELY(is_proper_prefix(from_ptr, ptr)))
@@ -36118,29 +36317,28 @@ public:
                     }
 
                     // the "from" location must exist - use at()
-                    basic_json const v = result.at(from_ptr);
+                    // a root "from" is rejected by operation_remove below, which must leave result intact
+                    basic_json v = from_ptr.empty() ? basic_json(result) : std::move(result.at(from_ptr));
 
                     // The move operation is functionally identical to a
                     // "remove" operation on the "from" location, followed
                     // immediately by an "add" operation at the target
                     // location with the value that was just removed.
                     operation_remove(from_ptr);
-                    operation_add(ptr, v);
+                    operation_add(ptr, std::move(v));
                     break;
                 }
 
                 case patch_operations::copy:
                 {
-                    const auto from_path = get_value("copy", "from", true).template get<string_t>();
+                    const string_t& from_path = *get_value("copy", "from", true).m_data.m_value.string;
                     const json_pointer from_ptr(from_path);
 
-                    // the "from" location must exist - use at()
-                    basic_json const v = result.at(from_ptr);
-
                     // The copy is functionally identical to an "add"
                     // operation at the target location using the value
-                    // specified in the "from" member.
+                    // specified in the "from" member; the "from" location
-                    operation_add(ptr, v);
+                    // must exist - use at()
+                    operation_add(ptr, result.at(from_ptr));
                     break;
                 }
 

tests/src/unit-json_pointer.cpp

@@ -23,8 +23,14 @@ using nlohmann::json;
     using namespace nlohmann::literals; // NOLINT(google-build-using-namespace)
 #endif
 
+#include <cerrno>
+#include <cstdlib>
+#include <limits>
 #include <map>
+#include <random>
 #include <sstream>
+#include <string>
+#include <vector>
 
 TEST_CASE("JSON pointers")
 {
@@ -1071,3 +1077,193 @@ TEST_CASE("flatten of structured values")
               R"({"/z":"s","/a~1b/~0":1,"/a~1b/k":null,"/a/0":1,"/a/1/c":null,"/a/1/b":null,"/a/2/0/x~0~1/0":true,"/a/2/0/x~0~1/1":null,"/a/2/0/w":2})");
     }
 }
+
+namespace
+{
+// reference implementation of the array index rules (RFC 6901, Sect. 4) based on strtoull
+enum class index_class
+{
+    ok,
+    leading_zero,
+    not_a_number,
+    unresolved,
+    exceeds_size_type
+};
+
+index_class classify_index(const std::string& s, std::size_t& idx)
+{
+    if (s.size() > 1 && s[0] == '0')
+    {
+        return index_class::leading_zero;
+    }
+    if (!s.empty() && s != "-" && !(s[0] >= '0' && s[0] <= '9'))
+    {
+        return index_class::not_a_number;
+    }
+    char* end = nullptr;
+    errno = 0;
+    const unsigned long long res = std::strtoull(s.c_str(), &end, 10); // NOLINT(runtime/int)
+    if (end == s.c_str() || errno == ERANGE || static_cast<std::size_t>(end - s.c_str()) != s.size())
+    {
+        return index_class::unresolved;
+    }
+    if (res >= static_cast<unsigned long long>((std::numeric_limits<std::size_t>::max)())) // NOLINT(runtime/int)
+    {
+        return index_class::exceeds_size_type;
+    }
+    idx = static_cast<std::size_t>(res);
+    return index_class::ok;
+}
+
+// the observable behavior of json_pointer::at() and contains() for an array index token
+void check_index_token(const std::string& token)
+{
+    const json array = {10, 20, 30};
+    const json::json_pointer ptr("/" + token);
+
+    std::size_t idx = 0;
+    const auto cls = classify_index(token, idx);
+    const bool exists = cls == index_class::ok && idx < array.size();
+
+    CAPTURE(token)
+    CHECK(array.contains(ptr) == (exists && token != "-"));
+
+    if (token == "-")
+    {
+        CHECK_THROWS_AS(array.at(ptr), json::out_of_range&);
+        return;
+    }
+
+    switch (cls)
+    {
+        case index_class::leading_zero:
+            CHECK_THROWS_AS(array.at(ptr), json::parse_error&);
+            break;
+        case index_class::not_a_number:
+            CHECK_THROWS_AS(array.at(ptr), json::parse_error&);
+            break;
+        case index_class::unresolved:
+        case index_class::exceeds_size_type:
+            CHECK_THROWS_AS(array.at(ptr), json::out_of_range&);
+            break;
+        case index_class::ok:
+        default:
+            if (exists)
+            {
+                CHECK(array.at(ptr) == array[idx]);
+            }
+            else
+            {
+                CHECK_THROWS_AS(array.at(ptr), json::out_of_range&);
+            }
+            break;
+    }
+}
+} // namespace
+
+TEST_CASE("JSON pointer array index tokens match strtoull semantics")
+{
+    SECTION("boundary values")
+    {
+        const std::string max_digits = std::to_string((std::numeric_limits<std::size_t>::max)());
+        const std::vector<std::string> tokens =
+        {
+            "", "-", "0", "1", "2", "3", "00", "01", "007", "+1", "-1", " 1", "1 ", "1a", "a1", "0x1", "1e1", "1.0",
+            "999999999", "1000000000", "99999999999999999", "999999999999999999", "1000000000000000000",
+            "9999999999999999999", "18446744073709551614", max_digits, "18446744073709551616",
+            "99999999999999999999999", "000000000000000000000"
+        };
+        for (const auto& token : tokens)
+        {
+            check_index_token(token);
+        }
+    }
+
+    SECTION("random tokens")
+    {
+        std::mt19937 gen(42);
+        const std::string alphabet = "0123456789012345678901234567890123456789-+ ex";
+        for (int i = 0; i < 5000; ++i)
+        {
+            std::string token(static_cast<std::size_t>(gen() % 23), '0');
+            for (auto& c : token)
+            {
+                c = alphabet[gen() % alphabet.size()];
+            }
+            check_index_token(token);
+        }
+    }
+}
+
+TEST_CASE("JSON pointer operations on pointers with escaped tokens")
+{
+    const std::vector<std::string> strings =
+    {
+        "", "/", "//", "/a", "/a/b", "/a~1b", "/~0", "/~01", "/~10", "/a~0~1/b/", "/0/1/2", "/ ", "/a/", "/~1/~0"
+    };
+
+    for (const auto& str : strings)
+    {
+        CAPTURE(str)
+        const json::json_pointer ptr(str);
+        CHECK(ptr.to_string() == str);
+        CHECK(ptr / "x" / "y" / std::size_t{3} == json::json_pointer(str + "/x/y/3"));
+        CHECK(ptr.parent_pointer() == (str.empty() ? ptr : json::json_pointer(str.substr(0, str.rfind('/')))));
+
+        // comparison with a string, in place, and with every other pointer
+#if !defined(JSON_TEST_DEPRECATED_FUNCTIONS_DELETED)
+        for (const auto& other : strings)
+        {
+            CAPTURE(other)
+            CHECK((ptr == other) == (str == other));
+            CHECK((other == ptr) == (str == other));
+            CHECK((ptr != other) == (str != other));
+        }
+        CHECK_THROWS_AS(ptr == "x", json::parse_error&);
+        CHECK_THROWS_AS(ptr == "/~", json::parse_error&);
+        CHECK_THROWS_AS(ptr == "/b/~2", json::parse_error&);
+#endif
+    }
+}
+
+TEST_CASE("JSON pointer lookups")
+{
+    json j = {{"a", {{"b", {1, 2, 3}}}}, {"", 7}, {"~/", {{"x", nullptr}}}};
+    const json& cj = j;
+
+    CHECK(cj[json::json_pointer("/a/b/2")] == 3);
+    CHECK(cj.at(json::json_pointer("/a/b/1")) == 2);
+    CHECK(cj.at(json::json_pointer("/")) == 7);
+    CHECK(cj.contains(json::json_pointer("/~0~1/x")));
+    CHECK(!cj.contains(json::json_pointer("/a/c")));
+    CHECK(cj.value(json::json_pointer("/a/b/0"), 5) == 1);
+    CHECK(cj.value(json::json_pointer("/a/b/3"), 5) == 5);
+    CHECK(cj.value(json::json_pointer("/a/zz"), 5) == 5);
+
+    CHECK_THROWS_AS(cj.at(json::json_pointer("/a/c")), json::out_of_range&);
+    CHECK_THROWS_AS(cj.at(json::json_pointer("/a/b/3")), json::out_of_range&);
+
+    // non-const access reuses existing entries and creates missing ones
+    j[json::json_pointer("/a/b/1")] = 20;
+    j[json::json_pointer("/n/m")] = 1;
+    CHECK(j["a"]["b"] == json({1, 20, 3}));
+    CHECK(j["n"]["m"] == 1);
+}
+
+TEST_CASE("JSON patch with moves and copies")
+{
+    json doc = {{"a", {{"b", {1, 2, 3}}}}, {"c", {{"d", "x"}}}};
+
+    CHECK(doc.patch(json::parse(R"([{"op":"move","from":"/a/b","path":"/c/e"}])")) ==
+          json::parse(R"({"a":{},"c":{"d":"x","e":[1,2,3]}})"));
+    CHECK(doc.patch(json::parse(R"([{"op":"copy","from":"/a/b","path":"/c/e"}])")) ==
+          json::parse(R"({"a":{"b":[1,2,3]},"c":{"d":"x","e":[1,2,3]}})"));
+    CHECK(doc.patch(json::parse(R"([{"op":"move","from":"/a/b/0","path":"/a/b/2"}])")) ==
+          json::parse(R"({"a":{"b":[2,3,1]},"c":{"d":"x"}})"));
+
+    // a failing move leaves a copy-patched document untouched
+    CHECK_THROWS_AS(doc.patch(json::parse(R"([{"op":"move","from":"","path":""}])")), json::out_of_range&);
+    json inplace = doc;
+    CHECK_THROWS_AS(inplace.patch_inplace(json::parse(R"([{"op":"move","from":"","path":""}])")), json::out_of_range&);
+    CHECK(inplace == doc);
+}