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>

docs/mkdocs/docs/api/basic_json/basic_json.md

@@ -67,11 +67,7 @@ basic_json(basic_json&& other) noexcept;
     - **objects**: [`object_t`](object_t.md) and all kinds of compatible associative containers such as `std::map`,
      `std::unordered_map`, `std::multimap`, and `std::unordered_multimap` with a `key_type` compatible to `string_t`
      and a `value_type` from which a `basic_json` value can be constructed.
-    - **strings**: `string_t`, string literals, and all compatible string containers can be used. Since version 3.13.0,
-      this includes `#!cpp std::u8string` (C++20): its code units are stored as a JSON string and
-      [`get<std::u8string>()`](get.md) reads it back (in version 3.12.0, a `#!cpp std::u8string` was stored as an array
-      of numbers; `get<std::u8string>()` still accepts such an array). `#!cpp std::u8string_view` and `#!cpp char8_t`
-      arrays are not strings; they are stored as arrays of code units.
+    - **strings**: `string_t`, string literals, and all compatible string containers can be used.
 
     !!! note "Rvalue containers are moved from"
 

docs/mkdocs/docs/api/basic_json/get.md

@@ -130,12 +130,6 @@ overload (3).
     `#!cpp json(true).get<double>()` throw. This is the behavior of all 3.x versions;
     [`basic_json_view::get<T>()`](../basic_json_view/get.md) behaves the same.
 
-!!! note "`std::u8string` conversions"
-
-    Since version 3.13.0, `#!cpp get<std::u8string>()` (C++20) reads a JSON string; it also accepts an array of numbers,
-    the form in which version 3.12.0 stored a `#!cpp std::u8string`. Any other JSON type throws
-    [`type_error.302`](../../home/exceptions.md#jsonexceptiontype_error302) ("type must be string or array").
-
 !!! note "`std::optional` conversions"
 
     Prior to version 3.13.0, `#!cpp get<std::optional<T>>()` (and other conversions to `std::optional<T>`) failed to

docs/mkdocs/docs/features/types/template_parameters.md

@@ -425,7 +425,7 @@ using array_t = ArrayType<basic_json, AllocatorType<basic_json>>;
 | Type                                                                 | Reason                                                                                                  |
 |----------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------|
 | `#!cpp std::wstring`, `#!cpp std::u16string`, `#!cpp std::u32string` | the character type is not one byte wide                                                                 |
-| `#!cpp std::u8string`                                                | one byte wide, but `#!cpp char8_t` is not `#!cpp char`-compatible (as a *value*, it converts to and from a JSON string) |
+| `#!cpp std::u8string`                                                | one byte wide, but `#!cpp char8_t` is not `#!cpp char`-compatible                                       |
 | `absl::Cord`                                                         | no `value_type`, and the storage is not contiguous                                                      |
 | `QString`                                                            | no `append(const char*, size_type)`; its `QChar` is also two bytes wide, though that is never diagnosed |
 

docs/mkdocs/docs/home/releases/unreleased.md

@@ -8,16 +8,6 @@ These changes are part of the `develop` branch, but not of a release yet.
   exception is thrown during the conversion, the source may be partially moved-from, so the strong exception guarantee
   no longer holds for the source of an rvalue conversion (the JSON value itself is unaffected). Lvalues and `const`
   objects are still copied. See [`basic_json`](../../api/basic_json/basic_json.md).
-- In C++20 (library support for `char8_t`, `__cpp_lib_char8_t`), a `#!cpp std::u8string` is a JSON **string**:
-  `json j = std::u8string(u8"abc");` stores `"abc"`, and `#!cpp j.get<std::u8string>()` reads it back. Version 3.12.0
-  stored a `#!cpp std::u8string` as an array of code units (`[97,98,99]`); on the 3.13.0 development branch it was
-  already stored as a string if `std::filesystem` is available, but could not be read back. Now the result no longer
-  depends on whether `std::filesystem::path` is supported, and `#!cpp get<std::u8string>()` accepts both a JSON string
-  and the array of numbers written by 3.12.0. **Consequence:** JSON documents produced from a `#!cpp std::u8string` by
-  3.12.0 (arrays) are still read, but code that checks `is_array()` on such a value, or that reads it as
-  `#!cpp std::vector<char8_t>` / `#!cpp std::vector<std::uint8_t>`, now sees a string; to keep the array form, convert
-  explicitly, e.g., `#!cpp json(std::vector<char8_t>(s.begin(), s.end()))`. `#!cpp std::u8string_view` and
-  `#!cpp char8_t` arrays are unchanged (arrays of code units). See [`basic_json`](../../api/basic_json/basic_json.md).
 
 ## API changes
 

include/nlohmann/detail/conversions/from_json.hpp

@@ -785,37 +785,6 @@ void from_json(const BasicJsonType& j, std::unordered_map<Key, Value, Hash, KeyE
     from_json_pair_array_to_map(j, m);
 }
 
-#if defined(__cpp_lib_char8_t)
-// a std::u8string is read from a JSON string; the array of code units written by
-// versions before 3.13.0 is still accepted
-template < typename BasicJsonType, typename Tr, typename Allocator,
-           enable_if_t < std::is_same<typename json_type_of_t<BasicJsonType>::string_t::value_type, char>::value, int > = 0 >
-inline void from_json(const BasicJsonType& j, std::basic_string<char8_t, Tr, Allocator>& s)
-{
-    if (j.is_string())
-    {
-        const auto& str = string_value(j);
-        const char* const data = str.data();
-        const std::size_t size = str.size();
-        std::basic_string<char8_t, Tr, Allocator> ret(s.get_allocator());
-        ret.resize(size);
-        for (std::size_t i = 0; i < size; ++i)
-        {
-            ret[i] = static_cast<char8_t>(static_cast<unsigned char>(data[i]));
-        }
-        s = std::move(ret);
-    }
-    else if (j.is_array())
-    {
-        from_json_array_impl(j, s, priority_tag<3> {});
-    }
-    else
-    {
-        throw_type_must_be("string or array", j);
-    }
-}
-#endif
-
 #if JSON_HAS_FILESYSTEM || JSON_HAS_EXPERIMENTAL_FILESYSTEM
 
 // Workaround for MSVC 19.51 (and possibly later): in large cpp files, the compiler may fail to resolve with generic has_from_json (issue #4996)

include/nlohmann/detail/conversions/to_json.hpp

@@ -625,20 +625,16 @@ inline void to_json(BasicJsonType& j, const T& t)
     to_json_tuple_impl(j, t, make_index_sequence<std::tuple_size<T>::value> {});
 }
 
-// a std::u8string is a JSON string (it was an array of code units before 3.13.0);
-// defined outside the std::filesystem guard so that the result does not depend
-// on whether std::filesystem::path is supported
+#if JSON_HAS_FILESYSTEM || JSON_HAS_EXPERIMENTAL_FILESYSTEM
 #if defined(__cpp_lib_char8_t)
 template<typename BasicJsonType, typename Tr, typename Allocator>
 inline void to_json(BasicJsonType& j, const std::basic_string<char8_t, Tr, Allocator>& s)
 {
-    using string_t = typename BasicJsonType::string_t;
-    // char may alias any object; the code units are copied unchanged
-    j = string_t(reinterpret_cast<const char*>(s.data()), s.size());
+    using OtherAllocator = typename std::allocator_traits<Allocator>::template rebind_alloc<char>;
+    j = std::basic_string<char, std::char_traits<char>, OtherAllocator>(s.begin(), s.end(), s.get_allocator());
 }
 #endif
 
-#if JSON_HAS_FILESYSTEM || JSON_HAS_EXPERIMENTAL_FILESYSTEM
 // Workaround for MSVC 19.51 (and possibly later): in large cpp files, the compiler may fail to resolve with generic has_to_json (issue #4996)
 template<typename BasicJsonType>
 struct has_to_json<BasicJsonType, std_fs::path, void> : std::true_type {};

include/nlohmann/detail/json_pointer.hpp

@@ -1091,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
 
@@ -1119,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);

single_include/nlohmann/json.hpp

@@ -6928,37 +6928,6 @@ void from_json(const BasicJsonType& j, std::unordered_map<Key, Value, Hash, KeyE
     from_json_pair_array_to_map(j, m);
 }
 
-#if defined(__cpp_lib_char8_t)
-// a std::u8string is read from a JSON string; the array of code units written by
-// versions before 3.13.0 is still accepted
-template < typename BasicJsonType, typename Tr, typename Allocator,
-           enable_if_t < std::is_same<typename json_type_of_t<BasicJsonType>::string_t::value_type, char>::value, int > = 0 >
-inline void from_json(const BasicJsonType& j, std::basic_string<char8_t, Tr, Allocator>& s)
-{
-    if (j.is_string())
-    {
-        const auto& str = string_value(j);
-        const char* const data = str.data();
-        const std::size_t size = str.size();
-        std::basic_string<char8_t, Tr, Allocator> ret(s.get_allocator());
-        ret.resize(size);
-        for (std::size_t i = 0; i < size; ++i)
-        {
-            ret[i] = static_cast<char8_t>(static_cast<unsigned char>(data[i]));
-        }
-        s = std::move(ret);
-    }
-    else if (j.is_array())
-    {
-        from_json_array_impl(j, s, priority_tag<3> {});
-    }
-    else
-    {
-        throw_type_must_be("string or array", j);
-    }
-}
-#endif
-
 #if JSON_HAS_FILESYSTEM || JSON_HAS_EXPERIMENTAL_FILESYSTEM
 
 // Workaround for MSVC 19.51 (and possibly later): in large cpp files, the compiler may fail to resolve with generic has_from_json (issue #4996)
@@ -8360,20 +8329,16 @@ inline void to_json(BasicJsonType& j, const T& t)
     to_json_tuple_impl(j, t, make_index_sequence<std::tuple_size<T>::value> {});
 }
 
-// a std::u8string is a JSON string (it was an array of code units before 3.13.0);
-// defined outside the std::filesystem guard so that the result does not depend
-// on whether std::filesystem::path is supported
+#if JSON_HAS_FILESYSTEM || JSON_HAS_EXPERIMENTAL_FILESYSTEM
 #if defined(__cpp_lib_char8_t)
 template<typename BasicJsonType, typename Tr, typename Allocator>
 inline void to_json(BasicJsonType& j, const std::basic_string<char8_t, Tr, Allocator>& s)
 {
-    using string_t = typename BasicJsonType::string_t;
-    // char may alias any object; the code units are copied unchanged
-    j = string_t(reinterpret_cast<const char*>(s.data()), s.size());
+    using OtherAllocator = typename std::allocator_traits<Allocator>::template rebind_alloc<char>;
+    j = std::basic_string<char, std::char_traits<char>, OtherAllocator>(s.begin(), s.end(), s.get_allocator());
 }
 #endif
 
-#if JSON_HAS_FILESYSTEM || JSON_HAS_EXPERIMENTAL_FILESYSTEM
 // Workaround for MSVC 19.51 (and possibly later): in large cpp files, the compiler may fail to resolve with generic has_to_json (issue #4996)
 template<typename BasicJsonType>
 struct has_to_json<BasicJsonType, std_fs::path, void> : std::true_type {};
@@ -27301,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
 
@@ -27329,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);

tests/CMakeLists.txt

@@ -364,16 +364,6 @@ json_test_add_test_for(src/unit-class_parser.cpp
     MAIN test_main CXX_STANDARDS ${test_cxx_standards} ${test_force}
 )
 
-# test the conversions again without std::filesystem::path support: a
-# std::u8string must be a JSON string in this configuration, too
-json_test_set_test_options(test-conversions2_no_filesystem
-    COMPILE_DEFINITIONS JSON_HAS_FILESYSTEM=0 JSON_HAS_EXPERIMENTAL_FILESYSTEM=0
-)
-json_test_add_test_for(src/unit-conversions2.cpp
-    NAME test-conversions2_no_filesystem
-    MAIN test_main CXX_STANDARDS ${test_cxx_standards} ${test_force}
-)
-
 # test diagnostic positions again without regular diagnostics (JSON pointer paths)
 json_test_set_test_options(test-diagnostic-positions_only
     COMPILE_DEFINITIONS JSON_DIAGNOSTICS=0

tests/src/unit-alt-string.cpp

@@ -536,20 +536,4 @@ TEST_CASE("alternative string type with json_view")
     }
 }
 
-// a std::u8string is a JSON string, whatever the string type of the JSON value
-// JSON_HAS_CPP_20 JSON_HAS_CPP_23 (do not remove; see note at top of file)
-#if defined(__cpp_lib_char8_t)
-TEST_CASE("alternative string type and std::u8string")
-{
-    const std::u8string s = u8"abc";
-    const alt_json j = s;
-    CHECK(j.is_string());
-    CHECK(j.get<alt_string>() == alt_string("abc"));
-    CHECK(j.get<std::u8string>() == s);
-
-    // the array of code units written by versions before 3.13.0
-    CHECK(alt_json::array({0x61, 0x62, 0x63}).get<std::u8string>() == s);
-}
-#endif
-
 DOCTEST_CLANG_SUPPRESS_WARNING_POP

tests/src/unit-conversions2.cpp

@@ -27,12 +27,10 @@ using nlohmann::json;
 #include <deque>
 #include <forward_list>
 #include <list>
-#include <map>
 #include <set>
 #include <unordered_map>
 #include <unordered_set>
 #include <valarray>
-#include <vector>
 
 // NLOHMANN_JSON_SERIALIZE_ENUM uses a static std::pair
 DOCTEST_CLANG_SUPPRESS_WARNING_PUSH
@@ -709,115 +707,39 @@ TEST_CASE("std::filesystem::path")
 }
 #endif
 
-// a std::u8string is a JSON string since 3.13.0 (it was an array of code units
-// before); independent of whether std::filesystem::path is supported, see the
-// test-conversions2_no_filesystem target
-// JSON_HAS_CPP_20 JSON_HAS_CPP_23 (do not remove; see note at top of file)
+// the ADL to_json overload for std::u8string only exists under the same guard
+// as std::filesystem::path support (it is otherwise only reached indirectly,
+// via std::filesystem::path::u8string()) -- mirror both #if conditions from
+// include/nlohmann/detail/conversions/to_json.hpp exactly
+#if JSON_HAS_FILESYSTEM || JSON_HAS_EXPERIMENTAL_FILESYSTEM
 #if defined(__cpp_lib_char8_t)
 TEST_CASE("std::u8string")
 {
-    // use \u universal-character-names (rather than raw \x byte escapes
-    // or literal non-ASCII source bytes) to compose the multi-byte UTF-8
-    // encoding -- MSVC treats \x escapes used that way inside a u8
-    // literal as a nonstandard extension (warning C5321), which some of
-    // our CI configs promote to an error; \u is portable and produces
-    // the exact same encoded bytes without depending on the source
-    // file's encoding
-    const std::u8string utf8 = u8"P\u011B\u0161ina";
-
     SECTION("ascii")
     {
         const std::u8string s = u8"Path";
         json const j = s;
 
-        CHECK(j.is_string());
         CHECK(j.template get<std::string>() == "Path");
     }
 
     SECTION("utf-8")
     {
-        json const j = utf8;
+        // use \u universal-character-names (rather than raw \x byte escapes
+        // or literal non-ASCII source bytes) to compose the multi-byte UTF-8
+        // encoding -- MSVC treats \x escapes used that way inside a u8
+        // literal as a nonstandard extension (warning C5321), which some of
+        // our CI configs promote to an error; \u is portable and produces
+        // the exact same encoded bytes without depending on the source
+        // file's encoding
+        const std::u8string s = u8"P\u011B\u0161ina";
+        json const j = s;
 
-        CHECK(j.is_string());
         CHECK(j.template get<std::string>() == "P\xc4\x9b\xc5\xa1ina");
     }
-
-    SECTION("round trip")
-    {
-        json const j = utf8;
-        CHECK(j.template get<std::u8string>() == utf8);
-
-        std::u8string back;
-        j.get_to(back);
-        CHECK(back == utf8);
-
-        // from a string
-        json const j_string = "P\xc4\x9b\xc5\xa1ina";
-        CHECK(j_string.template get<std::u8string>() == utf8);
-
-        // empty, and with an embedded NUL
-        CHECK(json(std::u8string()).template get<std::u8string>().empty());
-        const std::u8string with_nul(u8"a\0b", 3);
-        CHECK(json(with_nul).template get<std::u8string>() == with_nul);
-
-        // the lvalue and rvalue paths, and in containers
-        std::u8string lvalue = utf8;
-        CHECK(json(lvalue).template get<std::u8string>() == utf8);
-        CHECK(json(std::move(lvalue)).template get<std::u8string>() == utf8);
-        const std::vector<std::u8string> vec = {utf8, u8"x"};
-        json const j_vec = vec;
-        CHECK(j_vec.is_array());
-        CHECK(j_vec[0].is_string());
-        CHECK(j_vec.template get<std::vector<std::u8string>>() == vec);
-        const std::map<std::string, std::u8string> map = {{"k", utf8}};
-        CHECK(json(map).template get<std::map<std::string, std::u8string>>() == map);
-    }
-
-    SECTION("array of code units (written by versions before 3.13.0)")
-    {
-        json const j = json::array({0x50, 0xC4, 0x9B, 0xC5, 0xA1, 0x69, 0x6E, 0x61});
-        CHECK(j.template get<std::u8string>() == utf8);
-        CHECK(json::array().template get<std::u8string>().empty());
-        CHECK(json::parse("[97, 98]").template get<std::u8string>() == u8"ab");
-
-        std::u8string s = u8"overwritten";
-        j.get_to(s);
-        CHECK(s == utf8);
-    }
-
-    SECTION("other types")
-    {
-#if !defined(JSON_NOEXCEPTION)
-        CHECK_THROWS_WITH_AS(json(1).template get<std::u8string>(), "[json.exception.type_error.302] type must be string or array, but is number", json::type_error);
-        CHECK_THROWS_WITH_AS(json(nullptr).template get<std::u8string>(), "[json.exception.type_error.302] type must be string or array, but is null", json::type_error);
-        CHECK_THROWS_AS(json::object().template get<std::u8string>(), json::type_error);
-        // an element that is not a number
-        CHECK_THROWS_AS(json::array({"a"}).template get<std::u8string>(), json::type_error);
-#endif
-    }
-
-    SECTION("ordered_json")
-    {
-        nlohmann::ordered_json const j = utf8;
-        CHECK(j.is_string());
-        CHECK(j.template get<std::string>() == "P\xc4\x9b\xc5\xa1ina");
-        CHECK(j.template get<std::u8string>() == utf8);
-        CHECK(nlohmann::ordered_json::array({0x61, 0x62}).template get<std::u8string>() == u8"ab");
-    }
-
-    SECTION("std::u8string_view and char8_t arrays are unchanged (arrays of code units)")
-    {
-        const std::u8string_view view = utf8;
-        json const j_view = view;
-        CHECK(j_view.is_array());
-        CHECK(j_view.size() == 8);
-
-        const char8_t arr[] = u8"ab";
-        json const j_arr = arr;
-        CHECK(j_arr == json::array({0x61, 0x62, 0}));
-    }
 }
 #endif
+#endif
 
 #if !defined(JSON_NOEXCEPTION)
 namespace

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);
+}