Resume patch operations from the common prefix in constant time per step

patch() and patch_inplace() keep the values along the previously resolved
pointer, so that the next operation resumes from the prefix the two paths
have in common. To find the resume point, each cached step was tested from the
deepest upwards with a memcmp over its whole prefix. If two paths shared a
prefix and the previous path continued for D more tokens, the search compared
D prefixes of that length: for two "test" operations whose paths share n
tokens and continue for n more, the time was quadratic in n (3.12.0 was
linear).

With more than 16 cached steps, the length of the common prefix of the two
paths is now computed once, and the deepest cached step that ends within it,
at a token boundary of the new path, is taken. Steps that are skipped are
dropped from the cache, so the search is amortized constant per token. With
fewer steps, which is the usual case, they are compared as before, as that
is cheaper for short paths. The operations, and which values stay valid after
them, are unchanged.

Measurements (Apple clang -O2, arm64), patch_inplace() of two "test"
operations whose paths share n tokens and continue for n more:

  n          25k    50k    100k    200k
  before    42 ms  182 ms 1194 ms 5433 ms
  after      0 ms    2 ms    4 ms    8 ms
  3.12.0     3 ms    5 ms   10 ms   19 ms

Patches of ordinary documents (diff() then patch(), and many short
operations): within 0.5 % of before in instructions retired (canada, citm_catalog,
twitter, mesh, update-center, many short synthetic operations).

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

include/nlohmann/detail/json_pointer.hpp

@@ -852,6 +852,139 @@ class json_pointer
     }
 
   private:
+    /*!
+    @brief the pointer prefixes of a flattened object that denote arrays
+
+    @ref unflatten creates arrays exactly below the prefixes that have a
+    reference token 0 among their children, and objects everywhere else.
+    Deciding this up front keeps the result independent of the order in which
+    the flattened object is iterated, which is unspecified for some object
+    types.
+
+    A prefix is identified by the text of the key it is the beginning of:
+    escaping is unambiguous, so equal prefixes of valid keys are equal texts.
+    The set refers to the keys, which must outlive it.
+    */
+    class array_prefix_set
+    {
+      public:
+        void insert(const char* data, std::size_t size)
+        {
+            // flattened objects are usually sorted, so most keys that have a
+            // 0 yield the prefix of the previous one
+            if (last_data != nullptr && last_size == size && std::memcmp(last_data, data, size) == 0)
+            {
+                return;
+            }
+            last_data = data;
+            last_size = size;
+
+            if (table.empty())
+            {
+                table.resize(16);
+            }
+            const std::size_t hash = hash_of(data, size);
+            const std::size_t mask = table.size() - 1;
+            std::size_t i = hash & mask;
+            while (table[i].data != nullptr)
+            {
+                if (table[i].hash == hash && table[i].size == size && std::memcmp(table[i].data, data, size) == 0)
+                {
+                    return;
+                }
+                i = (i + 1) & mask;
+            }
+            table[i] = slot(hash, data, size);
+
+            // keep the load factor below 1/2
+            if (++used * 2 > table.size())
+            {
+                grow();
+            }
+        }
+
+        bool empty() const noexcept
+        {
+            return used == 0;
+        }
+
+        bool contains(const char* data, std::size_t size) const noexcept
+        {
+            if (used == 0)
+            {
+                return false;
+            }
+            const std::size_t hash = hash_of(data, size);
+            const std::size_t mask = table.size() - 1;
+            for (std::size_t i = hash & mask; table[i].data != nullptr; i = (i + 1) & mask)
+            {
+                if (table[i].hash == hash && table[i].size == size && std::memcmp(table[i].data, data, size) == 0)
+                {
+                    return true;
+                }
+            }
+            return false;
+        }
+
+      private:
+        struct slot
+        {
+            slot() noexcept = default;
+
+            slot(std::size_t h, const char* d, std::size_t s) noexcept
+                : hash(h), data(d), size(s)
+            {}
+
+            std::size_t hash = 0;
+            const char* data = nullptr; // nullptr: the slot is empty
+            std::size_t size = 0;
+        };
+
+        static std::size_t hash_of(const char* data, std::size_t size) noexcept
+        {
+            std::uint64_t h = 0x9E3779B97F4A7C15ULL ^ size;
+            std::size_t i = 0;
+            for (; i + 8 <= size; i += 8)
+            {
+                std::uint64_t w = 0;
+                std::memcpy(&w, data + i, 8);
+                h = (h ^ w) * 0x100000001B3ULL;
+                h ^= h >> 32u;
+            }
+            std::uint64_t w = 0;
+            if (i < size)
+            {
+                std::memcpy(&w, data + i, size - i);
+            }
+            h = (h ^ w) * 0x9E3779B97F4A7C15ULL;
+            return detail::conditional_static_cast<std::size_t>(h ^ (h >> 29u));
+        }
+
+        void grow()
+        {
+            std::vector<slot> old(table.size() * 2);
+            old.swap(table);
+            const std::size_t mask = table.size() - 1;
+            for (const auto& s : old)
+            {
+                if (s.data != nullptr)
+                {
+                    std::size_t i = s.hash & mask;
+                    while (table[i].data != nullptr)
+                    {
+                        i = (i + 1) & mask;
+                    }
+                    table[i] = s;
+                }
+            }
+        }
+
+        std::vector<slot> table{};
+        std::size_t used = 0;
+        const char* last_data = nullptr;
+        std::size_t last_size = 0;
+    };
+
     /// @brief the length of the longest common prefix of the first @a limit bytes of @a a and @a b
     static std::size_t common_prefix_length(const char* a, const char* b, const std::size_t limit) noexcept
     {
@@ -874,354 +1007,6 @@ class json_pointer
         return i;
     }
 
-    /*!
-    @brief the prefixes of a flattened object that are marked as arrays, for
-           prefixes that are not short
-
-    A prefix is identified by the tokens it consists of: a node of a tree
-    stands for the prefix of its parent followed by a token, and is looked up
-    by its parent and the text of the token. The node of a prefix is found by
-    walking the tokens of the key from the root, so identifying all prefixes
-    of a key together costs one pass over the key, however long the prefixes
-    are, and no prefix is ever compared byte by byte as a whole. The nodes
-    along the key that was walked last are kept, and the walk of the next key
-    starts below the beginning it has in common with that key. The tree refers
-    to the keys, which must outlive it.
-    */
-    class prefix_tree
-    {
-      public:
-        /// @brief set the seed of the hash function, before anything is added
-        void reseed(const std::uint64_t seed_value) noexcept
-        {
-            seed = seed_value;
-        }
-
-        /// @brief mark the first @a prefix_size bytes of the key of @a key_size bytes at @a data
-        void mark(const char* data, std::size_t key_size, std::size_t prefix_size)
-        {
-            nodes[walk(data, key_size, prefix_size)].marked = true;
-            any_marked = true;
-        }
-
-        bool is_marked(const char* data, std::size_t key_size, std::size_t prefix_size)
-        {
-            return any_marked && nodes[walk(data, key_size, prefix_size)].marked;
-        }
-
-        bool empty() const noexcept
-        {
-            return !any_marked;
-        }
-
-        /// @brief the hash of the first @a size bytes at @a data, for the seed @a seed_value
-        static std::size_t hash_bytes(const char* data, std::size_t size, const std::uint64_t seed_value) noexcept
-        {
-            std::uint64_t h = seed_value ^ size;
-            std::size_t i = 0;
-            for (; i + 8 <= size; i += 8)
-            {
-                std::uint64_t w = 0;
-                std::memcpy(&w, data + i, 8);
-                h = (h ^ w) * 0x100000001B3ULL;
-                h ^= h >> 32u;
-            }
-            std::uint64_t w = 0;
-            if (i < size)
-            {
-                std::memcpy(&w, data + i, size - i);
-            }
-            h = (h ^ w) * 0x9E3779B97F4A7C15ULL;
-            return detail::conditional_static_cast<std::size_t>(h ^ (h >> 29u));
-        }
-
-      private:
-        struct node
-        {
-            std::size_t parent = 0;
-            std::size_t hash = 0;
-            const char* token = nullptr;
-            std::size_t token_size = 0;
-            bool marked = false;
-        };
-
-        /// @brief a slot of the hash table; the index of a node, 0 if the slot is empty
-        struct bucket
-        {
-            std::size_t index = 0;
-        };
-
-        /// @brief the node after a token of the key that was walked last, and where the token ends
-        struct step
-        {
-            std::size_t node = 0;
-            std::size_t end = 0;
-        };
-
-        /// @brief the index of the node of the prefix that ends at the slash (or the end) at @a prefix_size
-        std::size_t walk(const char* data, std::size_t key_size, std::size_t prefix_size)
-        {
-            if (nodes.empty())
-            {
-                nodes.emplace_back();
-                table.resize(16);
-                chain.emplace_back();
-            }
-
-            if (data != last_key)
-            {
-                // keep the nodes within the beginning that this key has in common
-                // with the key they were found for; a prefix that ends inside a
-                // token of this key is not one of its prefixes
-                const std::size_t same = common_prefix_length(data, last_key, (std::min)(key_size, last_key_size));
-                std::size_t keep = chain.size();
-                while (keep > 1 && (chain[keep - 1].end > same || (chain[keep - 1].end == same && same < key_size && data[same] != '/')))
-                {
-                    --keep;
-                }
-                chain.resize(keep);
-                last_key = data;
-                last_key_size = key_size;
-            }
-
-            // walk the tokens that are not walked yet
-            while (chain.back().end < prefix_size && chain.back().end < key_size)
-            {
-                const std::size_t start = chain.back().end + 1;
-                const void* const slash = std::memchr(data + start, '/', key_size - start);
-                const std::size_t end = slash == nullptr ? key_size : static_cast<std::size_t>(static_cast<const char*>(slash) - data);
-                step next;
-                next.node = child(chain.back().node, data + start, end - start);
-                next.end = end;
-                chain.push_back(next);
-            }
-
-            if (chain.back().end == prefix_size)
-            {
-                return chain.back().node;
-            }
-            // an earlier call walked further
-            const auto it = std::lower_bound(chain.begin(), chain.end(), prefix_size, [](const step & s, std::size_t size)
-            {
-                return s.end < size;
-            });
-            return it->node;
-        }
-
-        std::size_t slot_of(std::size_t parent, std::size_t hash) const noexcept
-        {
-            std::uint64_t x = static_cast<std::uint64_t>(hash) ^ (static_cast<std::uint64_t>(parent) * 0x9E3779B97F4A7C15ULL);
-            x ^= x >> 32u;
-            x *= 0xD6E8FEB86659FD93ULL;
-            x ^= x >> 32u;
-            return static_cast<std::size_t>(x) & (table.size() - 1);
-        }
-
-        /// @brief the node of the prefix of the node @a parent followed by the token, which is added if it is not there
-        std::size_t child(std::size_t parent, const char* token, std::size_t token_size)
-        {
-            const std::size_t hash = hash_bytes(token, token_size, seed);
-            std::size_t i = slot_of(parent, hash);
-            while (table[i].index != 0)
-            {
-                const node& n = nodes[table[i].index];
-                if (n.parent == parent && n.hash == hash && n.token_size == token_size && std::memcmp(n.token, token, token_size) == 0)
-                {
-                    return table[i].index;
-                }
-                i = (i + 1) & (table.size() - 1);
-            }
-
-            node created;
-            created.parent = parent;
-            created.hash = hash;
-            created.token = token;
-            created.token_size = token_size;
-            nodes.push_back(created);
-            table[i].index = nodes.size() - 1;
-
-            // keep the load factor below 1/2
-            if (nodes.size() * 2 > table.size())
-            {
-                std::vector<bucket> old(table.size() * 2);
-                old.swap(table);
-                for (std::size_t k = 1; k < nodes.size(); ++k)
-                {
-                    std::size_t j = slot_of(nodes[k].parent, nodes[k].hash);
-                    while (table[j].index != 0)
-                    {
-                        j = (j + 1) & (table.size() - 1);
-                    }
-                    table[j].index = k;
-                }
-            }
-            return nodes.size() - 1;
-        }
-
-        std::uint64_t seed = 0;
-        /// @brief the nodes; the first is the root, the empty prefix
-        std::vector<node> nodes{};
-        /// @brief the nodes (not the root) in a hash table
-        std::vector<bucket> table{};
-        /// @brief the root, and the node after each token of the key that was walked last
-        std::vector<step> chain{};
-        const char* last_key = nullptr;
-        std::size_t last_key_size = 0;
-        bool any_marked = false;
-    };
-
-    /*!
-    @brief the pointer prefixes of a flattened object that denote arrays
-
-    @ref unflatten creates arrays exactly below the prefixes that have a
-    reference token 0 among their children, and objects everywhere else.
-    Deciding this up front keeps the result independent of the order in which
-    the flattened object is iterated, which is unspecified for some object
-    types.
-
-    A prefix is identified by the text of the key it is the beginning of:
-    escaping is unambiguous, so equal prefixes of valid keys are equal texts.
-    The set refers to the keys, which must outlive it. Short prefixes are
-    kept in a hash table and compared as texts, which costs at most the length
-    of the bound. Longer prefixes are kept in a @ref prefix_tree, because
-    hashing and comparing every one of the prefixes of a key with many tokens
-    from its beginning would take quadratic time.
-
-    The hash function depends on a seed that is derived from the address of a
-    local variable, which address space layout randomization changes between
-    processes, so keys cannot be crafted to collide in advance; the result
-    does not depend on the seed. Where the addresses are not randomized, or
-    when the seed is known, keys can collide: k short prefixes then cost
-    k^2 / 2 comparisons of fewer than 64 bytes each. The long prefixes are not
-    hashed as a whole.
-    */
-    class array_prefix_set
-    {
-      public:
-        /// @brief choose the seed of the hash function, before anything is added: it is derived from the address that is passed
-        void reseed(const void* address) noexcept
-        {
-            // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast): the address is only a source of entropy
-            std::uint64_t x = static_cast<std::uint64_t>(reinterpret_cast<std::uintptr_t>(address)) ^ 0x9E3779B97F4A7C15ULL;
-            x *= 0xBF58476D1CE4E5B9ULL;
-            seed = x ^ (x >> 31u);
-            tree.reseed(seed);
-        }
-
-        /// @brief add the first @a prefix_size bytes of the key of @a key_size bytes at @a data
-        void insert(const char* data, std::size_t key_size, std::size_t prefix_size)
-        {
-            if (prefix_size >= short_limit)
-            {
-                tree.mark(data, key_size, prefix_size);
-                return;
-            }
-
-            // flattened objects are usually sorted, so most keys that have a
-            // 0 yield the prefix of the previous one
-            if (last_data != nullptr && last_size == prefix_size && std::memcmp(last_data, data, prefix_size) == 0)
-            {
-                return;
-            }
-            last_data = data;
-            last_size = prefix_size;
-
-            const std::size_t hash = prefix_tree::hash_bytes(data, prefix_size, seed);
-            if (table.empty())
-            {
-                table.resize(16);
-            }
-            const std::size_t mask = table.size() - 1;
-            std::size_t i = hash & mask;
-            while (table[i].data != nullptr)
-            {
-                if (table[i].hash == hash && table[i].size == prefix_size && std::memcmp(table[i].data, data, prefix_size) == 0)
-                {
-                    return;
-                }
-                i = (i + 1) & mask;
-            }
-            table[i] = slot(hash, data, prefix_size);
-
-            // keep the load factor below 1/2
-            if (++used * 2 > table.size())
-            {
-                grow();
-            }
-        }
-
-        bool empty() const noexcept
-        {
-            return used == 0 && tree.empty();
-        }
-
-        /// @brief whether the first @a prefix_size bytes of the key of @a key_size bytes at @a data were added
-        bool contains(const char* data, std::size_t key_size, std::size_t prefix_size)
-        {
-            if (prefix_size >= short_limit)
-            {
-                return tree.is_marked(data, key_size, prefix_size);
-            }
-            if (used == 0)
-            {
-                return false;
-            }
-            const std::size_t hash = prefix_tree::hash_bytes(data, prefix_size, seed);
-            const std::size_t mask = table.size() - 1;
-            for (std::size_t i = hash & mask; table[i].data != nullptr; i = (i + 1) & mask)
-            {
-                if (table[i].hash == hash && table[i].size == prefix_size && std::memcmp(table[i].data, data, prefix_size) == 0)
-                {
-                    return true;
-                }
-            }
-            return false;
-        }
-
-      private:
-        /// @brief prefixes of fewer bytes are kept in the hash table
-        static constexpr std::size_t short_limit = 64;
-
-        struct slot
-        {
-            slot() noexcept = default;
-
-            slot(std::size_t h, const char* d, std::size_t s) noexcept
-                : hash(h), data(d), size(s)
-            {}
-
-            std::size_t hash = 0;
-            const char* data = nullptr; // nullptr: the slot is empty
-            std::size_t size = 0;
-        };
-
-        void grow()
-        {
-            std::vector<slot> old(table.size() * 2);
-            old.swap(table);
-            const std::size_t mask = table.size() - 1;
-            for (const auto& s : old)
-            {
-                if (s.data != nullptr)
-                {
-                    std::size_t i = s.hash & mask;
-                    while (table[i].data != nullptr)
-                    {
-                        i = (i + 1) & mask;
-                    }
-                    table[i] = s;
-                }
-            }
-        }
-
-        std::uint64_t seed = 0;
-        prefix_tree tree{};
-        std::vector<slot> table{};
-        std::size_t used = 0;
-        const char* last_data = nullptr;
-        std::size_t last_size = 0;
-    };
-
     /*!
     @brief check that @a key is a valid JSON pointer, and add the prefixes of
            it that denote arrays to @a arrays
@@ -1267,7 +1052,7 @@ class json_pointer
                 // a token 0 makes the pointer before it an array
                 if (i - begin == 1 && data[begin] == '0')
                 {
-                    arrays.insert(data, size, begin - 1);
+                    arrays.insert(data, begin - 1);
                 }
                 begin = i + 1;
             }
@@ -1306,6 +1091,32 @@ class json_pointer
         }
     };
 
+    /*!
+    @brief the number of the deepest step of the previous path that is a prefix of the new one
+
+    Comparing every one of many steps with the beginning of the path would take
+    quadratic time. Instead, the length of the common beginning of the two paths
+    is computed once: a step whose prefix is not longer is a prefix of the new
+    path, too. For few steps, which is the usual case, @ref resolve_plain
+    compares them, which is cheaper.
+    */
+    template<typename Steps>
+    JSON_HEDLEY_NEVER_INLINE static std::size_t deepest_shared_step(const string_t& path, const std::size_t length, const string_t& previous, const Steps& steps) noexcept
+    {
+        const std::size_t same = common_prefix_length(path.data(), previous.data(), (std::min)(length, previous.size()));
+        std::size_t depth = steps.size();
+        for (; 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 <= same && (prefix == length || path[prefix] == '/'))
+            {
+                break;
+            }
+        }
+        return depth;
+    }
+
     /*!
     @brief resolve a plain JSON pointer without building its reference tokens
 
@@ -1334,13 +1145,20 @@ class json_pointer
         if (cache.path != nullptr && !steps.empty() && steps[0].second == root)
         {
             const string_t& previous = *cache.path;
-            for (depth = steps.size(); depth > 1; --depth)
+            if (JSON_HEDLEY_UNLIKELY(steps.size() > 16))
             {
-                // 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)
+                depth = deepest_shared_step(path, length, previous, steps);
+            }
+            else
+            {
+                for (depth = steps.size(); depth > 1; --depth)
                 {
-                    break;
+                    // 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);
@@ -2277,7 +2095,6 @@ class json_pointer
         // token 0 among their children; the values below them are arrays,
         // all others are objects (see array_prefix_set)
         array_prefix_set arrays;
-        arrays.reseed(&arrays);
         const string_t* previous_key = nullptr;
         for (const auto& element : *value.m_data.m_value.object)
         {
@@ -2369,7 +2186,7 @@ class json_pointer
                     case detail::value_t::null:
                     {
                         // a first child 0 makes the value an array without a look-up
-                        if ((token_size == 1 && data[pos + 1] == '0') || arrays.contains(data, key.size(), pos))
+                        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

single_include/nlohmann/json.hpp

@@ -27027,6 +27027,139 @@ class json_pointer
     }
 
   private:
+    /*!
+    @brief the pointer prefixes of a flattened object that denote arrays
+
+    @ref unflatten creates arrays exactly below the prefixes that have a
+    reference token 0 among their children, and objects everywhere else.
+    Deciding this up front keeps the result independent of the order in which
+    the flattened object is iterated, which is unspecified for some object
+    types.
+
+    A prefix is identified by the text of the key it is the beginning of:
+    escaping is unambiguous, so equal prefixes of valid keys are equal texts.
+    The set refers to the keys, which must outlive it.
+    */
+    class array_prefix_set
+    {
+      public:
+        void insert(const char* data, std::size_t size)
+        {
+            // flattened objects are usually sorted, so most keys that have a
+            // 0 yield the prefix of the previous one
+            if (last_data != nullptr && last_size == size && std::memcmp(last_data, data, size) == 0)
+            {
+                return;
+            }
+            last_data = data;
+            last_size = size;
+
+            if (table.empty())
+            {
+                table.resize(16);
+            }
+            const std::size_t hash = hash_of(data, size);
+            const std::size_t mask = table.size() - 1;
+            std::size_t i = hash & mask;
+            while (table[i].data != nullptr)
+            {
+                if (table[i].hash == hash && table[i].size == size && std::memcmp(table[i].data, data, size) == 0)
+                {
+                    return;
+                }
+                i = (i + 1) & mask;
+            }
+            table[i] = slot(hash, data, size);
+
+            // keep the load factor below 1/2
+            if (++used * 2 > table.size())
+            {
+                grow();
+            }
+        }
+
+        bool empty() const noexcept
+        {
+            return used == 0;
+        }
+
+        bool contains(const char* data, std::size_t size) const noexcept
+        {
+            if (used == 0)
+            {
+                return false;
+            }
+            const std::size_t hash = hash_of(data, size);
+            const std::size_t mask = table.size() - 1;
+            for (std::size_t i = hash & mask; table[i].data != nullptr; i = (i + 1) & mask)
+            {
+                if (table[i].hash == hash && table[i].size == size && std::memcmp(table[i].data, data, size) == 0)
+                {
+                    return true;
+                }
+            }
+            return false;
+        }
+
+      private:
+        struct slot
+        {
+            slot() noexcept = default;
+
+            slot(std::size_t h, const char* d, std::size_t s) noexcept
+                : hash(h), data(d), size(s)
+            {}
+
+            std::size_t hash = 0;
+            const char* data = nullptr; // nullptr: the slot is empty
+            std::size_t size = 0;
+        };
+
+        static std::size_t hash_of(const char* data, std::size_t size) noexcept
+        {
+            std::uint64_t h = 0x9E3779B97F4A7C15ULL ^ size;
+            std::size_t i = 0;
+            for (; i + 8 <= size; i += 8)
+            {
+                std::uint64_t w = 0;
+                std::memcpy(&w, data + i, 8);
+                h = (h ^ w) * 0x100000001B3ULL;
+                h ^= h >> 32u;
+            }
+            std::uint64_t w = 0;
+            if (i < size)
+            {
+                std::memcpy(&w, data + i, size - i);
+            }
+            h = (h ^ w) * 0x9E3779B97F4A7C15ULL;
+            return detail::conditional_static_cast<std::size_t>(h ^ (h >> 29u));
+        }
+
+        void grow()
+        {
+            std::vector<slot> old(table.size() * 2);
+            old.swap(table);
+            const std::size_t mask = table.size() - 1;
+            for (const auto& s : old)
+            {
+                if (s.data != nullptr)
+                {
+                    std::size_t i = s.hash & mask;
+                    while (table[i].data != nullptr)
+                    {
+                        i = (i + 1) & mask;
+                    }
+                    table[i] = s;
+                }
+            }
+        }
+
+        std::vector<slot> table{};
+        std::size_t used = 0;
+        const char* last_data = nullptr;
+        std::size_t last_size = 0;
+    };
+
     /// @brief the length of the longest common prefix of the first @a limit bytes of @a a and @a b
     static std::size_t common_prefix_length(const char* a, const char* b, const std::size_t limit) noexcept
     {
@@ -27049,354 +27182,6 @@ class json_pointer
         return i;
     }
 
-    /*!
-    @brief the prefixes of a flattened object that are marked as arrays, for
-           prefixes that are not short
-
-    A prefix is identified by the tokens it consists of: a node of a tree
-    stands for the prefix of its parent followed by a token, and is looked up
-    by its parent and the text of the token. The node of a prefix is found by
-    walking the tokens of the key from the root, so identifying all prefixes
-    of a key together costs one pass over the key, however long the prefixes
-    are, and no prefix is ever compared byte by byte as a whole. The nodes
-    along the key that was walked last are kept, and the walk of the next key
-    starts below the beginning it has in common with that key. The tree refers
-    to the keys, which must outlive it.
-    */
-    class prefix_tree
-    {
-      public:
-        /// @brief set the seed of the hash function, before anything is added
-        void reseed(const std::uint64_t seed_value) noexcept
-        {
-            seed = seed_value;
-        }
-
-        /// @brief mark the first @a prefix_size bytes of the key of @a key_size bytes at @a data
-        void mark(const char* data, std::size_t key_size, std::size_t prefix_size)
-        {
-            nodes[walk(data, key_size, prefix_size)].marked = true;
-            any_marked = true;
-        }
-
-        bool is_marked(const char* data, std::size_t key_size, std::size_t prefix_size)
-        {
-            return any_marked && nodes[walk(data, key_size, prefix_size)].marked;
-        }
-
-        bool empty() const noexcept
-        {
-            return !any_marked;
-        }
-
-        /// @brief the hash of the first @a size bytes at @a data, for the seed @a seed_value
-        static std::size_t hash_bytes(const char* data, std::size_t size, const std::uint64_t seed_value) noexcept
-        {
-            std::uint64_t h = seed_value ^ size;
-            std::size_t i = 0;
-            for (; i + 8 <= size; i += 8)
-            {
-                std::uint64_t w = 0;
-                std::memcpy(&w, data + i, 8);
-                h = (h ^ w) * 0x100000001B3ULL;
-                h ^= h >> 32u;
-            }
-            std::uint64_t w = 0;
-            if (i < size)
-            {
-                std::memcpy(&w, data + i, size - i);
-            }
-            h = (h ^ w) * 0x9E3779B97F4A7C15ULL;
-            return detail::conditional_static_cast<std::size_t>(h ^ (h >> 29u));
-        }
-
-      private:
-        struct node
-        {
-            std::size_t parent = 0;
-            std::size_t hash = 0;
-            const char* token = nullptr;
-            std::size_t token_size = 0;
-            bool marked = false;
-        };
-
-        /// @brief a slot of the hash table; the index of a node, 0 if the slot is empty
-        struct bucket
-        {
-            std::size_t index = 0;
-        };
-
-        /// @brief the node after a token of the key that was walked last, and where the token ends
-        struct step
-        {
-            std::size_t node = 0;
-            std::size_t end = 0;
-        };
-
-        /// @brief the index of the node of the prefix that ends at the slash (or the end) at @a prefix_size
-        std::size_t walk(const char* data, std::size_t key_size, std::size_t prefix_size)
-        {
-            if (nodes.empty())
-            {
-                nodes.emplace_back();
-                table.resize(16);
-                chain.emplace_back();
-            }
-
-            if (data != last_key)
-            {
-                // keep the nodes within the beginning that this key has in common
-                // with the key they were found for; a prefix that ends inside a
-                // token of this key is not one of its prefixes
-                const std::size_t same = common_prefix_length(data, last_key, (std::min)(key_size, last_key_size));
-                std::size_t keep = chain.size();
-                while (keep > 1 && (chain[keep - 1].end > same || (chain[keep - 1].end == same && same < key_size && data[same] != '/')))
-                {
-                    --keep;
-                }
-                chain.resize(keep);
-                last_key = data;
-                last_key_size = key_size;
-            }
-
-            // walk the tokens that are not walked yet
-            while (chain.back().end < prefix_size && chain.back().end < key_size)
-            {
-                const std::size_t start = chain.back().end + 1;
-                const void* const slash = std::memchr(data + start, '/', key_size - start);
-                const std::size_t end = slash == nullptr ? key_size : static_cast<std::size_t>(static_cast<const char*>(slash) - data);
-                step next;
-                next.node = child(chain.back().node, data + start, end - start);
-                next.end = end;
-                chain.push_back(next);
-            }
-
-            if (chain.back().end == prefix_size)
-            {
-                return chain.back().node;
-            }
-            // an earlier call walked further
-            const auto it = std::lower_bound(chain.begin(), chain.end(), prefix_size, [](const step & s, std::size_t size)
-            {
-                return s.end < size;
-            });
-            return it->node;
-        }
-
-        std::size_t slot_of(std::size_t parent, std::size_t hash) const noexcept
-        {
-            std::uint64_t x = static_cast<std::uint64_t>(hash) ^ (static_cast<std::uint64_t>(parent) * 0x9E3779B97F4A7C15ULL);
-            x ^= x >> 32u;
-            x *= 0xD6E8FEB86659FD93ULL;
-            x ^= x >> 32u;
-            return static_cast<std::size_t>(x) & (table.size() - 1);
-        }
-
-        /// @brief the node of the prefix of the node @a parent followed by the token, which is added if it is not there
-        std::size_t child(std::size_t parent, const char* token, std::size_t token_size)
-        {
-            const std::size_t hash = hash_bytes(token, token_size, seed);
-            std::size_t i = slot_of(parent, hash);
-            while (table[i].index != 0)
-            {
-                const node& n = nodes[table[i].index];
-                if (n.parent == parent && n.hash == hash && n.token_size == token_size && std::memcmp(n.token, token, token_size) == 0)
-                {
-                    return table[i].index;
-                }
-                i = (i + 1) & (table.size() - 1);
-            }
-
-            node created;
-            created.parent = parent;
-            created.hash = hash;
-            created.token = token;
-            created.token_size = token_size;
-            nodes.push_back(created);
-            table[i].index = nodes.size() - 1;
-
-            // keep the load factor below 1/2
-            if (nodes.size() * 2 > table.size())
-            {
-                std::vector<bucket> old(table.size() * 2);
-                old.swap(table);
-                for (std::size_t k = 1; k < nodes.size(); ++k)
-                {
-                    std::size_t j = slot_of(nodes[k].parent, nodes[k].hash);
-                    while (table[j].index != 0)
-                    {
-                        j = (j + 1) & (table.size() - 1);
-                    }
-                    table[j].index = k;
-                }
-            }
-            return nodes.size() - 1;
-        }
-
-        std::uint64_t seed = 0;
-        /// @brief the nodes; the first is the root, the empty prefix
-        std::vector<node> nodes{};
-        /// @brief the nodes (not the root) in a hash table
-        std::vector<bucket> table{};
-        /// @brief the root, and the node after each token of the key that was walked last
-        std::vector<step> chain{};
-        const char* last_key = nullptr;
-        std::size_t last_key_size = 0;
-        bool any_marked = false;
-    };
-
-    /*!
-    @brief the pointer prefixes of a flattened object that denote arrays
-
-    @ref unflatten creates arrays exactly below the prefixes that have a
-    reference token 0 among their children, and objects everywhere else.
-    Deciding this up front keeps the result independent of the order in which
-    the flattened object is iterated, which is unspecified for some object
-    types.
-
-    A prefix is identified by the text of the key it is the beginning of:
-    escaping is unambiguous, so equal prefixes of valid keys are equal texts.
-    The set refers to the keys, which must outlive it. Short prefixes are
-    kept in a hash table and compared as texts, which costs at most the length
-    of the bound. Longer prefixes are kept in a @ref prefix_tree, because
-    hashing and comparing every one of the prefixes of a key with many tokens
-    from its beginning would take quadratic time.
-
-    The hash function depends on a seed that is derived from the address of a
-    local variable, which address space layout randomization changes between
-    processes, so keys cannot be crafted to collide in advance; the result
-    does not depend on the seed. Where the addresses are not randomized, or
-    when the seed is known, keys can collide: k short prefixes then cost
-    k^2 / 2 comparisons of fewer than 64 bytes each. The long prefixes are not
-    hashed as a whole.
-    */
-    class array_prefix_set
-    {
-      public:
-        /// @brief choose the seed of the hash function, before anything is added: it is derived from the address that is passed
-        void reseed(const void* address) noexcept
-        {
-            // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast): the address is only a source of entropy
-            std::uint64_t x = static_cast<std::uint64_t>(reinterpret_cast<std::uintptr_t>(address)) ^ 0x9E3779B97F4A7C15ULL;
-            x *= 0xBF58476D1CE4E5B9ULL;
-            seed = x ^ (x >> 31u);
-            tree.reseed(seed);
-        }
-
-        /// @brief add the first @a prefix_size bytes of the key of @a key_size bytes at @a data
-        void insert(const char* data, std::size_t key_size, std::size_t prefix_size)
-        {
-            if (prefix_size >= short_limit)
-            {
-                tree.mark(data, key_size, prefix_size);
-                return;
-            }
-
-            // flattened objects are usually sorted, so most keys that have a
-            // 0 yield the prefix of the previous one
-            if (last_data != nullptr && last_size == prefix_size && std::memcmp(last_data, data, prefix_size) == 0)
-            {
-                return;
-            }
-            last_data = data;
-            last_size = prefix_size;
-
-            const std::size_t hash = prefix_tree::hash_bytes(data, prefix_size, seed);
-            if (table.empty())
-            {
-                table.resize(16);
-            }
-            const std::size_t mask = table.size() - 1;
-            std::size_t i = hash & mask;
-            while (table[i].data != nullptr)
-            {
-                if (table[i].hash == hash && table[i].size == prefix_size && std::memcmp(table[i].data, data, prefix_size) == 0)
-                {
-                    return;
-                }
-                i = (i + 1) & mask;
-            }
-            table[i] = slot(hash, data, prefix_size);
-
-            // keep the load factor below 1/2
-            if (++used * 2 > table.size())
-            {
-                grow();
-            }
-        }
-
-        bool empty() const noexcept
-        {
-            return used == 0 && tree.empty();
-        }
-
-        /// @brief whether the first @a prefix_size bytes of the key of @a key_size bytes at @a data were added
-        bool contains(const char* data, std::size_t key_size, std::size_t prefix_size)
-        {
-            if (prefix_size >= short_limit)
-            {
-                return tree.is_marked(data, key_size, prefix_size);
-            }
-            if (used == 0)
-            {
-                return false;
-            }
-            const std::size_t hash = prefix_tree::hash_bytes(data, prefix_size, seed);
-            const std::size_t mask = table.size() - 1;
-            for (std::size_t i = hash & mask; table[i].data != nullptr; i = (i + 1) & mask)
-            {
-                if (table[i].hash == hash && table[i].size == prefix_size && std::memcmp(table[i].data, data, prefix_size) == 0)
-                {
-                    return true;
-                }
-            }
-            return false;
-        }
-
-      private:
-        /// @brief prefixes of fewer bytes are kept in the hash table
-        static constexpr std::size_t short_limit = 64;
-
-        struct slot
-        {
-            slot() noexcept = default;
-
-            slot(std::size_t h, const char* d, std::size_t s) noexcept
-                : hash(h), data(d), size(s)
-            {}
-
-            std::size_t hash = 0;
-            const char* data = nullptr; // nullptr: the slot is empty
-            std::size_t size = 0;
-        };
-
-        void grow()
-        {
-            std::vector<slot> old(table.size() * 2);
-            old.swap(table);
-            const std::size_t mask = table.size() - 1;
-            for (const auto& s : old)
-            {
-                if (s.data != nullptr)
-                {
-                    std::size_t i = s.hash & mask;
-                    while (table[i].data != nullptr)
-                    {
-                        i = (i + 1) & mask;
-                    }
-                    table[i] = s;
-                }
-            }
-        }
-
-        std::uint64_t seed = 0;
-        prefix_tree tree{};
-        std::vector<slot> table{};
-        std::size_t used = 0;
-        const char* last_data = nullptr;
-        std::size_t last_size = 0;
-    };
-
     /*!
     @brief check that @a key is a valid JSON pointer, and add the prefixes of
            it that denote arrays to @a arrays
@@ -27442,7 +27227,7 @@ class json_pointer
                 // a token 0 makes the pointer before it an array
                 if (i - begin == 1 && data[begin] == '0')
                 {
-                    arrays.insert(data, size, begin - 1);
+                    arrays.insert(data, begin - 1);
                 }
                 begin = i + 1;
             }
@@ -27481,6 +27266,32 @@ class json_pointer
         }
     };
 
+    /*!
+    @brief the number of the deepest step of the previous path that is a prefix of the new one
+
+    Comparing every one of many steps with the beginning of the path would take
+    quadratic time. Instead, the length of the common beginning of the two paths
+    is computed once: a step whose prefix is not longer is a prefix of the new
+    path, too. For few steps, which is the usual case, @ref resolve_plain
+    compares them, which is cheaper.
+    */
+    template<typename Steps>
+    JSON_HEDLEY_NEVER_INLINE static std::size_t deepest_shared_step(const string_t& path, const std::size_t length, const string_t& previous, const Steps& steps) noexcept
+    {
+        const std::size_t same = common_prefix_length(path.data(), previous.data(), (std::min)(length, previous.size()));
+        std::size_t depth = steps.size();
+        for (; 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 <= same && (prefix == length || path[prefix] == '/'))
+            {
+                break;
+            }
+        }
+        return depth;
+    }
+
     /*!
     @brief resolve a plain JSON pointer without building its reference tokens
 
@@ -27509,13 +27320,20 @@ class json_pointer
         if (cache.path != nullptr && !steps.empty() && steps[0].second == root)
         {
             const string_t& previous = *cache.path;
-            for (depth = steps.size(); depth > 1; --depth)
+            if (JSON_HEDLEY_UNLIKELY(steps.size() > 16))
             {
-                // 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)
+                depth = deepest_shared_step(path, length, previous, steps);
+            }
+            else
+            {
+                for (depth = steps.size(); depth > 1; --depth)
                 {
-                    break;
+                    // 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);
@@ -28452,7 +28270,6 @@ class json_pointer
         // token 0 among their children; the values below them are arrays,
         // all others are objects (see array_prefix_set)
         array_prefix_set arrays;
-        arrays.reseed(&arrays);
         const string_t* previous_key = nullptr;
         for (const auto& element : *value.m_data.m_value.object)
         {
@@ -28544,7 +28361,7 @@ class json_pointer
                     case detail::value_t::null:
                     {
                         // a first child 0 makes the value an array without a look-up
-                        if ((token_size == 1 && data[pos + 1] == '0') || arrays.contains(data, key.size(), pos))
+                        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

tests/src/unit-json_patch.cpp

@@ -14,9 +14,12 @@ using nlohmann::json;
     using namespace nlohmann::literals; // NOLINT(google-build-using-namespace)
 #endif
 
+#include <algorithm>
 #include <cstddef>
+#include <ctime>
 #include <fstream>
 #include <limits>
+#include <random>
 #include <string>
 #include <utility>
 #include <vector>
@@ -2551,3 +2554,419 @@ TEST_CASE("JSON patch - diff of leaf values below the bound of the recursive des
     CHECK(object_patch.size() == 2);
     CHECK(object_source.patch(object_patch) == object_target);
 }
+
+namespace
+{
+// all pointers to values below `value` (not to `value` itself)
+void collect_pointers(const json& value, const std::string& path, std::vector<std::string>& pointers)
+{
+    if (value.is_object())
+    {
+        for (const auto& element : value.items())
+        {
+            std::string child = path;
+            child += '/';
+            for (const char c : element.key())
+            {
+                if (c == '~')
+                {
+                    child += "~0";
+                }
+                else if (c == '/')
+                {
+                    child += "~1";
+                }
+                else
+                {
+                    child += c;
+                }
+            }
+            pointers.push_back(child);
+            collect_pointers(element.value(), child, pointers);
+        }
+    }
+    else if (value.is_array())
+    {
+        for (std::size_t i = 0; i < value.size(); ++i)
+        {
+            std::string child = path;
+            child += '/';
+            child += std::to_string(i);
+            pointers.push_back(child);
+            collect_pointers(value[i], child, pointers);
+        }
+    }
+}
+
+// a random document of at most `depth` levels, with the names as keys
+json random_document(std::mt19937& gen, const std::vector<std::string>& names, const int depth)
+{
+    const int kind = std::uniform_int_distribution<int>(0, 9)(gen);
+    if (depth == 0 || kind < 2)
+    {
+        return std::uniform_int_distribution<int>(0, 3)(gen);
+    }
+    const int size = std::uniform_int_distribution<int>(1, 3)(gen);
+    json result = kind < 6 ? json::array() : json::object();
+    for (int i = 0; i < size; ++i)
+    {
+        if (kind < 6)
+        {
+            result.push_back(random_document(gen, names, depth - 1));
+        }
+        else
+        {
+            result[names[std::uniform_int_distribution<std::size_t>(0, names.size() - 1)(gen)]] = random_document(gen, names, depth - 1);
+        }
+    }
+    return result;
+}
+
+// the strings, one after the other
+std::string concat(std::string first, const std::string& second, const std::string& third = std::string())
+{
+    first += second;
+    first += third;
+    return first;
+}
+
+// the best of five times in seconds that std::clock() measures to apply the patch
+double patch_cpu_time(json& doc, const json& patch)
+{
+    double best = 1e30;
+    for (int i = 0; i < 5; ++i)
+    {
+        const std::clock_t start = std::clock();
+        doc.patch_inplace(patch);
+        best = (std::min)(best, static_cast<double>(std::clock() - start) / static_cast<double>(CLOCKS_PER_SEC));
+    }
+    return best;
+}
+} // namespace
+
+TEST_CASE("JSON patch - consecutive operations with paths that share a prefix")
+{
+    SECTION("tokens that start the same way")
+    {
+        const json doc = {{"a", {{"bc", {{"x", 1}}}, {"b", {{"x", 2}}}, {"b2", 3}}}};
+
+        // the second path shares "/a/b" with the first, but not the token "bc"
+        const json patch = json::parse(R"([
+            {"op": "test", "path": "/a/bc/x", "value": 1},
+            {"op": "test", "path": "/a/b/x", "value": 2},
+            {"op": "test", "path": "/a/bc/x", "value": 1},
+            {"op": "test", "path": "/a/b2", "value": 3},
+            {"op": "test", "path": "/a/b/x", "value": 2}
+        ])");
+        CHECK(doc.patch(patch) == doc);
+
+        json inplace = doc;
+        inplace.patch_inplace(patch);
+        CHECK(inplace == doc);
+
+        // a path that is a prefix of the previous one, and the other way round
+        const json prefixes = json::parse(R"([
+            {"op": "test", "path": "/a/bc/x", "value": 1},
+            {"op": "test", "path": "/a/bc", "value": {"x": 1}},
+            {"op": "test", "path": "/a/bc/x", "value": 1},
+            {"op": "test", "path": "/a", "value": {"bc": {"x": 1}, "b": {"x": 2}, "b2": 3}},
+            {"op": "test", "path": "/a/b/x", "value": 2},
+            {"op": "test", "path": "", "value": {"a": {"bc": {"x": 1}, "b": {"x": 2}, "b2": 3}}}
+        ])");
+        CHECK(doc.patch(prefixes) == doc);
+    }
+
+    SECTION("operations above a path that was resolved before")
+    {
+        const json doc = json::parse(R"({"a": [{"b": [1, 2, 3]}, {"b": [4, 5, 6]}], "c": {"d": {"e": 7}}})");
+
+        // an element inserted before the elements of an array moves them
+        CHECK(doc.patch(json::parse(R"([
+            {"op": "test", "path": "/a/0/b/2", "value": 3},
+            {"op": "add", "path": "/a/0", "value": {"b": [9]}},
+            {"op": "test", "path": "/a/1/b/2", "value": 3},
+            {"op": "test", "path": "/a/0/b/0", "value": 9},
+            {"op": "test", "path": "/a/2/b/0", "value": 4}
+        ])")) == json::parse(R"({"a": [{"b": [9]}, {"b": [1, 2, 3]}, {"b": [4, 5, 6]}], "c": {"d": {"e": 7}}})"));
+
+        // an element removed from the front
+        CHECK(doc.patch(json::parse(R"([
+            {"op": "test", "path": "/a/1/b/2", "value": 6},
+            {"op": "remove", "path": "/a/0"},
+            {"op": "test", "path": "/a/0/b/2", "value": 6},
+            {"op": "replace", "path": "/a/0/b/2", "value": 60},
+            {"op": "test", "path": "/a/0/b/2", "value": 60}
+        ])")) == json::parse(R"({"a": [{"b": [4, 5, 60]}], "c": {"d": {"e": 7}}})"));
+
+        // a value replaced above the path that was resolved before
+        CHECK(doc.patch(json::parse(R"([
+            {"op": "test", "path": "/c/d/e", "value": 7},
+            {"op": "replace", "path": "/c/d", "value": {"e": 8, "f": {"g": 9}}},
+            {"op": "test", "path": "/c/d/e", "value": 8},
+            {"op": "test", "path": "/c/d/f/g", "value": 9},
+            {"op": "remove", "path": "/c/d/f"},
+            {"op": "add", "path": "/c/d/f", "value": [1]},
+            {"op": "test", "path": "/c/d/f/0", "value": 1}
+        ])")) == json::parse(R"({"a": [{"b": [1, 2, 3]}, {"b": [4, 5, 6]}], "c": {"d": {"e": 8, "f": [1]}}})"));
+
+#if !defined(JSON_NOEXCEPTION)
+        // a value removed above the path that was resolved before is gone
+        const json removed = json::parse(R"([
+            {"op": "test", "path": "/c/d/e", "value": 7},
+            {"op": "remove", "path": "/c/d"},
+            {"op": "test", "path": "/c/d/e", "value": 7}
+        ])");
+        CHECK_THROWS_AS(doc.patch(removed), json::other_error&);
+        json inplace = doc;
+        CHECK_THROWS_AS(inplace.patch_inplace(removed), json::other_error&);
+
+        const json emptied = json::parse(R"([
+            {"op": "test", "path": "/a/1/b/2", "value": 6},
+            {"op": "remove", "path": "/a/1"},
+            {"op": "test", "path": "/a/1/b/2", "value": 6}
+        ])");
+        CHECK_THROWS_AS(doc.patch(emptied), json::other_error&);
+#endif
+    }
+
+    SECTION("paths with more than 16 tokens")
+    {
+        // 40 levels, with an array at the bottom and a second branch at level 20
+        std::string prefix20;
+        std::string prefix40;
+        json doc = {{"leaf", {1, 2, 3}}};
+        for (int i = 40; i > 0; --i)
+        {
+            if (i == 20)
+            {
+                doc["other"] = {{"x", 5}};
+            }
+            doc = {{"n", doc}};
+        }
+        for (int i = 1; i <= 40; ++i)
+        {
+            prefix40 += "/n";
+            if (i == 20)
+            {
+                prefix20 = prefix40;
+            }
+        }
+
+        const auto op = [](const char* name, const std::string & path, const json & value)
+        {
+            return json({{"op", name}, {"path", path}, {"value", value}});
+        };
+        const json patch =
+        {
+            op("test", concat(prefix40, "/leaf/2"), 3),
+            op("test", concat(prefix20, "/other/x"), 5),
+            op("test", concat(prefix40, "/leaf/0"), 1),
+            op("add", concat(prefix40, "/leaf/0"), 0),
+            op("test", concat(prefix40, "/leaf/3"), 3),
+            op("replace", concat(prefix20, "/other"), {{"x", 6}}),
+            op("test", concat(prefix20, "/other/x"), 6),
+            op("test", concat(prefix40, "/leaf/1"), 1),
+            {{"op", "remove"}, {"path", concat(prefix20, "/other")}},
+            op("test", concat(prefix40, "/leaf/1"), 1)
+        };
+        json expected = doc;
+        for (const auto& operation : patch)
+        {
+            expected = expected.patch(json::array({operation}));
+        }
+        CHECK(doc.patch(patch) == expected);
+        json inplace = doc;
+        inplace.patch_inplace(patch);
+        CHECK(inplace == expected);
+        CHECK(expected[json::json_pointer(concat(prefix40, "/leaf"))] == json({0, 1, 2, 3}));
+        CHECK(!expected[json::json_pointer(prefix20)].contains("other"));
+
+#if !defined(JSON_NOEXCEPTION)
+        // the value that was resolved before is gone with the member that held it
+        const json gone =
+        {
+            op("test", concat(prefix40, "/leaf/2"), 3),
+            {{"op", "remove"}, {"path", prefix20}},
+            op("test", concat(prefix40, "/leaf/2"), 3)
+        };
+        CHECK_THROWS_AS(doc.patch(gone), json::other_error&);
+#endif
+    }
+
+    SECTION("random sequences of operations give the same result as one operation at a time")
+    {
+        std::mt19937 gen(20261110); // NOLINT(cert-msc32-c,cert-msc51-cpp,bugprone-random-generator-seed): reproducible
+        const std::vector<std::string> names = {"a", "b", "ab", "abc", "a/b", "a~b", "1", "10", "token_longer_than_eight_bytes"};
+        const auto pick = [&gen](const std::size_t n)
+        {
+            return std::uniform_int_distribution<std::size_t>(0, n - 1)(gen);
+        };
+
+        for (int round = 0; round < 300; ++round)
+        {
+            const json start = random_document(gen, names, 7);
+            json current = start;
+            json patch = json::array();
+            std::string previous;
+
+            for (int step = 0; step < 25; ++step)
+            {
+                std::vector<std::string> pointers;
+                collect_pointers(current, "", pointers);
+                if (pointers.empty())
+                {
+                    break;
+                }
+
+                // most of the time, stay below a part of the previous path
+                std::vector<std::string> candidates;
+                if (!previous.empty() && pick(10) < 8)
+                {
+                    std::string prefix = previous;
+                    const std::size_t cut = prefix.find('/', 1 + pick(prefix.size()));
+                    prefix = prefix.substr(0, cut == std::string::npos ? prefix.size() : cut);
+                    for (const auto& p : pointers)
+                    {
+                        if (p.compare(0, prefix.size(), prefix) == 0)
+                        {
+                            candidates.push_back(p);
+                        }
+                    }
+                }
+                if (candidates.empty())
+                {
+                    candidates = pointers;
+                }
+                const std::string path = candidates[pick(candidates.size())];
+                const json::json_pointer pointer(path);
+
+                json operation;
+                switch (pick(5))
+                {
+                    case 0:
+                        operation = {{"op", "test"}, {"path", path}, {"value", current[pointer]}};
+                        break;
+                    case 1:
+                        operation = {{"op", "replace"}, {"path", path}, {"value", static_cast<int>(pick(100))}};
+                        break;
+                    case 2:
+                        operation = {{"op", "remove"}, {"path", path}};
+                        break;
+                    default:
+                    {
+                        // add below an array or object, which may be the root
+                        const json::json_pointer parent_pointer = pick(4) == 0 ? json::json_pointer() : pointer;
+                        const std::string parent_path = parent_pointer.to_string();
+                        const json& parent = current[parent_pointer];
+                        std::string token = "-";
+                        if (parent.is_array())
+                        {
+                            token = pick(3) == 0 ? "-" : std::to_string(pick(parent.size() + 1));
+                        }
+                        else if (parent.is_object())
+                        {
+                            token = pick(2) == 0 ? "new" : "ab";
+                        }
+                        else
+                        {
+                            // a primitive parent: replace it instead
+                            operation = {{"op", "replace"}, {"path", parent_path}, {"value", json::array({1, 2})}};
+                            break;
+                        }
+                        operation = {{"op", "add"}, {"path", concat(parent_path, "/", token)}, {"value", json::object({{"k", {1, 2}}})}};
+                        break;
+                    }
+                }
+                if (operation["path"].get<std::string>().empty())
+                {
+                    continue;
+                }
+
+                // one operation at a time: the cache is empty at the start of each
+                current = current.patch(json::array({operation}));
+                patch.push_back(operation);
+                previous = operation["path"].get<std::string>();
+            }
+
+            CHECK(start.patch(patch) == current);
+            json inplace = start;
+            inplace.patch_inplace(patch);
+            CHECK(inplace == current);
+
+            // the same for a type that keeps the order of the members, which makes
+            // objects that were built in a different order unequal: leave out the
+            // tests of structured values
+            json without_tests = json::array();
+            for (const auto& operation : patch)
+            {
+                if (operation["op"] != "test" || !operation["value"].is_structured())
+                {
+                    without_tests.push_back(operation);
+                }
+            }
+            const nlohmann::ordered_json ordered_patch = without_tests;
+            nlohmann::ordered_json ordered_inplace = start;
+            ordered_inplace.patch_inplace(ordered_patch);
+            CHECK(json(ordered_inplace) == current);
+        }
+    }
+}
+
+TEST_CASE("JSON patch - time is linear for long paths that share a prefix")
+{
+    // The time of the patch is compared with the time of a patch that is
+    // linear for sure, because a bound in seconds would depend on the machine:
+    // both test the same two values at the end of paths with 2n tokens. The
+    // second path of the first patch shares n tokens with the first one and
+    // continues for n tokens: the ratio is 1 to 2, and about 60 when every
+    // step is compared with the start of the path. The time that std::clock()
+    // measures is mostly the time of the processor, which a busy machine does
+    // not inflate (on MSVC, it is the time that has passed).
+    constexpr std::size_t n = 25000;
+
+    const auto nest = [](const std::size_t depth, const std::string & inner)
+    {
+        std::string text;
+        for (std::size_t i = 0; i < depth; ++i)
+        {
+            text += "{\"a\":";
+        }
+        text += inner;
+        text.append(depth, '}');
+        return text;
+    };
+    std::string as;
+    for (std::size_t i = 0; i < n; ++i)
+    {
+        as += "/a";
+    }
+    const std::string deep = nest(n, "1");
+    std::string members = "{\"x\":";
+    members += deep;
+    members += ",\"y\":";
+    members += deep;
+    members += "}";
+    json doc = json::parse(nest(n, members));
+
+    const auto test_op = [](const std::string & path)
+    {
+        return json({{"op", "test"}, {"path", path}, {"value", 1}});
+    };
+    const json shared = json::array({test_op(concat(as, "/x", as)), test_op(concat(as, "/y", as))});
+    const json same = json::array({test_op(concat(as, "/x", as)), test_op(concat(as, "/x", as))});
+
+    // the operations do not change the document, which is too deep to copy;
+    // a busy machine may spoil one comparison, hardly two
+    bool linear = false;
+    double t_shared = 0;
+    double t_same = 0;
+    for (int attempt = 0; attempt < 2 && !linear; ++attempt)
+    {
+        t_shared = patch_cpu_time(doc, shared);
+        t_same = (std::max)(patch_cpu_time(doc, same), 1e-3);
+        linear = t_shared < 10 * t_same;
+    }
+    CAPTURE(t_shared)
+    CAPTURE(t_same)
+    CHECK(linear);
+}

tests/src/unit-json_pointer.cpp

@@ -23,10 +23,8 @@ using nlohmann::json;
     using namespace nlohmann::literals; // NOLINT(google-build-using-namespace)
 #endif
 
-#include <algorithm>
 #include <cerrno>
 #include <cstdlib>
-#include <ctime>
 #include <limits>
 #include <map>
 #include <random>
@@ -1562,294 +1560,3 @@ TEST_CASE("JSON patch with moves and copies")
     CHECK_THROWS_AS(inplace.patch_inplace(json::parse(R"([{"op":"move","from":"","path":""}])")), json::out_of_range&);
     CHECK(inplace == doc);
 }
-
-namespace
-{
-// the keys of a shape of flattened objects with long keys; `zero` is the
-// token that is repeated `m` times
-// 0: one key, 1: one `zero` followed by tokens 1, 2: the token 1 followed by
-// tokens `zero`, 3 and 4: two keys with a long prefix, apart from other keys,
-// 5: the same for two long branches, 6: more of the keys of 3
-std::vector<std::string> shape_keys(const int shape, const std::size_t m, const std::string& zero)
-{
-    std::string repeated;
-    for (std::size_t i = 0; i < m; ++i)
-    {
-        repeated += "/" + zero;
-    }
-    std::vector<std::string> keys;
-    switch (shape)
-    {
-        case 0:
-            keys.push_back(repeated);
-            break;
-        case 1:
-        {
-            std::string key = "/" + zero;
-            for (std::size_t i = 1; i < m; ++i)
-            {
-                key += "/1";
-            }
-            keys.push_back(key);
-            break;
-        }
-        case 2:
-        {
-            std::string key = "/1";
-            for (std::size_t i = 1; i < m; ++i)
-            {
-                key += "/" + zero;
-            }
-            keys.push_back(key);
-            break;
-        }
-        case 3:
-        case 4:
-            keys = {repeated + "/a0", "/10", repeated + "/a1", "/11"};
-            break;
-        case 5:
-            keys = {"/x" + repeated + "/a0", "/y" + repeated + "/a0", "/x" + repeated + "/a1", "/y" + repeated + "/a1"};
-            break;
-        case 6:
-            for (int j = 0; j < 4; ++j)
-            {
-                keys.push_back(repeated + "/a" + std::to_string(j));
-                keys.push_back("/1" + std::to_string(j));
-            }
-            break;
-        default:
-            break;
-    }
-    return keys;
-}
-
-// the best of `runs` times in seconds that std::clock() measures to unflatten the keys,
-// which an ordered_json holds in the order they are given (shape 4 uses a
-// json, which sorts them)
-double unflatten_cpu_time(const int shape, const std::size_t m, const int runs, const std::string& zero)
-{
-    const std::vector<std::string> keys = shape_keys(shape, m, zero);
-    nlohmann::ordered_json ordered = nlohmann::ordered_json::object();
-    json sorted = json::object();
-    for (const auto& key : keys)
-    {
-        ordered[key] = 1;
-        sorted[key] = 1;
-    }
-
-    double best = 1e30;
-    for (int i = 0; i < runs; ++i)
-    {
-        const std::clock_t start = std::clock();
-        if (shape == 4)
-        {
-            const json nested = sorted.unflatten();
-        }
-        else
-        {
-            const nlohmann::ordered_json nested = ordered.unflatten();
-        }
-        best = (std::min)(best, static_cast<double>(std::clock() - start) / static_cast<double>(CLOCKS_PER_SEC));
-    }
-    return best;
-}
-} // namespace
-
-TEST_CASE("unflatten of keys with many reference tokens")
-{
-    using nlohmann::ordered_json;
-
-    SECTION("which prefixes become arrays")
-    {
-        // sorted keys that share a long beginning
-        CHECK(json({{"/x/y/q/1", 5}, {"/x/y/w/0", 4}, {"/x/y/w/1", 3}, {"/x/y/z/0", 1}, {"/x/y/z/1", 2}}).unflatten() ==
-        json::parse(R"({"x":{"y":{"q":{"1":5},"w":[4,3],"z":[1,2]}}})"));
-
-        // prefixes that differ in the position of a slash only
-        CHECK(json({{"/a/0/x", 1}, {"/a/1/y", 3}, {"/ab/1", 2}}).unflatten() ==
-        json::parse(R"({"a":[{"x":1},{"y":3}],"ab":{"1":2}})"));
-        CHECK(json({{"/a/b/1", 1}, {"/ab/0", 2}}).unflatten() ==
-        json::parse(R"({"a":{"b":{"1":1}},"ab":[2]})"));
-
-        // tokens longer than one word, escapes, and a token 0 below a token 1
-        const std::string t = "token_with_more_than_eight_bytes";
-        CHECK(json({{"/" + t + "/1/b/0", 1}, {"/" + t + "/0", 2}, {"/" + t + "/2/a~1b", 3}}).unflatten() ==
-        json::parse(R"({"token_with_more_than_eight_bytes":[2,{"b":[1]},{"a/b":3}]})"));
-
-        // prefixes of more than 64 bytes, that share a long beginning
-        std::string deep;
-        json expected = {{"a", {1, 2}}, {"b", {{"1", 3}}}, {"c", {{"1", {{"x", {4}}}}}}};
-        for (int i = 0; i < 30; ++i)
-        {
-            deep += "/seg";
-            expected = {{"seg", expected}};
-        }
-        CHECK(json({{deep + "/c/1/x/0", 4}, {deep + "/a/1", 2}, {deep + "/b/1", 3}, {deep + "/a/0", 1}}).unflatten() == expected);
-        CHECK(json(ordered_json({{deep + "/c/1/x/0", 4}, {deep + "/a/1", 2}, {deep + "/b/1", 3}, {deep + "/a/0", 1}}).unflatten()) == expected);
-        CHECK(json(ordered_json({{deep + "/a/1", 2}, {deep + "/a/0", 1}, {deep + "/b/1", 3}, {deep + "/c/1/x/0", 4}}).unflatten()) == expected);
-
-        // prefixes of every length around the limit up to which they are hashed directly
-        for (std::size_t length = 40; length < 90; ++length)
-        {
-            const std::string name(length, 'x');
-            const json flat = {{"/" + name + "/a/0", 1}, {"/" + name + "/a/1", 2}, {"/" + name + "/b/1", 3}, {"/" + name + "/c/1/0", 4}};
-            CHECK(flat.unflatten() == json({{name, {{"a", {1, 2}}, {"b", {{"1", 3}}}, {"c", {{"1", {4}}}}}}}));
-        }
-
-        // only the parent of a token 0 is an array, however deep the key is
-        CHECK(json({{"/0/1/1/1", 1}}).unflatten() == json::parse(R"([{"1":{"1":{"1":1}}}])"));
-        CHECK(json({{"/1/1/1/0", 1}}).unflatten() == json::parse(R"({"1":{"1":{"1":[1]}}})"));
-        CHECK(json({{"/1/0/1/0", 1}}).unflatten() == json::parse(R"({"1":[{"1":[1]}]})"));
-    }
-
-    SECTION("the result does not depend on the order of the keys")
-    {
-        // random documents without empty containers and without the key "0" in
-        // an object: flatten() and unflatten() are inverse to each other
-        std::mt19937 gen(20261110); // NOLINT(cert-msc32-c,cert-msc51-cpp,bugprone-random-generator-seed): reproducible
-        const std::vector<std::string> names = {"a", "b", "ab", "1", "2", "10", "a/b", "a~b", "token_with_more_than_eight_bytes", "x"};
-
-        struct builder
-        {
-            std::mt19937& gen;
-            const std::vector<std::string>& names;
-
-            json operator()(int depth) const
-            {
-                const int kind = std::uniform_int_distribution<int>(0, 9)(gen);
-                if (depth == 0 || kind < 3)
-                {
-                    return kind;
-                }
-                json result = kind < 6 ? json::array() : json::object();
-                const int size = std::uniform_int_distribution<int>(1, 4)(gen);
-                for (int i = 0; i < size; ++i)
-                {
-                    if (kind < 6)
-                    {
-                        result.push_back((*this)(depth - 1));
-                    }
-                    else
-                    {
-                        result[names[std::uniform_int_distribution<std::size_t>(0, names.size() - 1)(gen)]] = (*this)(depth - 1);
-                    }
-                }
-                return result;
-            }
-        };
-        const builder build{gen, names};
-
-        for (int round = 0; round < 200; ++round)
-        {
-            const json doc = build(6);
-            const json flat = doc.flatten();
-            CHECK(flat.unflatten() == doc);
-
-            // the same entries in shuffled order, in an object that keeps it
-            std::vector<std::pair<std::string, json>> entries;
-            for (const auto& el : flat.items())
-            {
-                entries.emplace_back(el.key(), el.value());
-            }
-            std::shuffle(entries.begin(), entries.end(), gen);
-            ordered_json shuffled = ordered_json::object();
-            for (const auto& e : entries)
-            {
-                shuffled[e.first] = e.second;
-            }
-            CHECK(json(shuffled.unflatten()) == doc);
-        }
-    }
-
-    SECTION("keys with long prefixes, in every order")
-    {
-        // prefixes of more than 64 bytes that share a long beginning, and
-        // continue with tokens that start the same way
-        std::string deep;
-        for (int i = 0; i < 30; ++i)
-        {
-            deep += "/seg";
-        }
-        const std::string other = deep.substr(0, 70) + "/x" + deep.substr(70);
-        std::vector<std::string> keys = {deep + "/a/0", deep + "/ab/1", deep + "/ab/x", deep + "/abc/0/y/0", other + "/b/1/0", deep + "/abc/1"};
-        std::sort(keys.begin(), keys.end());
-
-        // the result for the keys in sorted order, which json iterates in
-        json sorted = json::object();
-        for (const auto& key : keys)
-        {
-            sorted[key] = 1;
-        }
-        const json expected = sorted.unflatten();
-        CHECK(expected.is_object());
-
-        // ordered_json iterates in the order the keys were added
-        std::vector<std::size_t> order(keys.size());
-        for (std::size_t i = 0; i < order.size(); ++i)
-        {
-            order[i] = i;
-        }
-        std::size_t permutations = 0;
-        bool all_equal = true;
-        do
-        {
-            nlohmann::ordered_json flat = nlohmann::ordered_json::object();
-            for (const auto i : order)
-            {
-                flat[keys[i]] = 1;
-            }
-            all_equal = all_equal && json(flat.unflatten()) == expected;
-            ++permutations;
-        }
-        while (std::next_permutation(order.begin(), order.end()));
-        CHECK(permutations == 720);
-        CHECK(all_equal);
-    }
-
-    SECTION("time is linear in the number of tokens")
-    {
-        // A bound in seconds would depend on the machine. Instead, the time is
-        // compared with the time for the same keys with the token 0 replaced by
-        // a token that is not a number: there is no array, so no prefix is
-        // looked up. The ratio is 1 to 3 for a linear algorithm, and between
-        // 12 and 100 when looking up a prefix takes time proportional to its
-        // length. The time that std::clock() measures is mostly the time of the
-        // processor, which a busy machine does not inflate (on MSVC, it is the
-        // time that has passed), and the best of two or three runs counts.
-        for (int shape = 0; shape < 7; ++shape)
-        {
-            // the shapes with several keys, in an order that does not sort them,
-            // need more tokens to be slow enough to tell
-            const bool many = shape == 3 || shape == 5 || shape == 6;
-            const std::size_t m = many ? 40000 : 10000;
-            const int runs = many ? 2 : 3;
-
-            // a busy machine may spoil one comparison, hardly two
-            bool linear = false;
-            double t_array = 0;
-            double t_object = 0;
-            for (int attempt = 0; attempt < 2 && !linear; ++attempt)
-            {
-                t_array = unflatten_cpu_time(shape, m, runs, "0");
-                t_object = (std::max)(unflatten_cpu_time(shape, m, runs, "a"), 1e-3);
-                linear = t_array < 6 * t_object;
-            }
-            CAPTURE(shape)
-            CAPTURE(t_array)
-            CAPTURE(t_object)
-            CHECK(linear);
-        }
-
-        // the nesting is as expected: an array exactly below each token 0
-        const json nested_deep = json::object({{shape_keys(0, 1000, "0")[0], 1}}).unflatten();
-        std::size_t depth = 0;
-        for (const json* p = &nested_deep; p->is_array(); p = &p->back())
-        {
-            ++depth;
-        }
-        CHECK(depth == 1000);
-        const json nested_ones = json::object({{shape_keys(1, 1000, "0")[0], 1}}).unflatten();
-        CHECK(nested_ones.is_array());
-        CHECK(nested_ones.back().is_object());
-    }
-}