Merge branch 'develop' into fix-self-aliasing-pointer-patch

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

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

@@ -69,6 +69,16 @@ Duplicate member names inside an operation object are resolved by the parser bef
 is kept, see [`object_t`](object_t.md#behavior)), so `#!json {"op": "add", "op": "remove", "path": "/a"}` is a
 `remove` operation.
 
+The JSON patch may be the JSON value itself (`#!cpp j.patch_inplace(j)`): the operations are then read from a copy of
+the patch made before the first operation is applied, so the result is the same as that of
+`#!cpp j = j.patch(j)`, and the exception safety is the same as above.
+
+!!! danger "Undefined behavior"
+
+    The JSON patch must not be a value stored inside the JSON value (e.g., `#!cpp j.patch_inplace(j["patch"])`), as the
+    operations may change or destroy it while it is read. Pass a copy (`#!cpp j.patch_inplace(json(j["patch"]))`) or use
+    [`patch`](patch.md) instead.
+
 ## Examples
 
 ??? example "Example: apply a JSON patch in place"
@@ -121,3 +131,4 @@ is kept, see [`object_t`](object_t.md#behavior)), so `#!json {"op": "add", "op":
 - Throws [`parse_error.109`](../../home/exceptions.md#jsonexceptionparse_error109) instead of
   [`out_of_range.404`](../../home/exceptions.md#jsonexceptionout_of_range404) for a one-character array index that is
   not a digit (e.g., `/x`) in version 3.13.0, as it already did for longer ones.
+- Applying a JSON value as patch to itself no longer results in undefined behavior in version 3.13.0.

docs/mkdocs/docs/api/json_pointer/operator_slasheq.md

@@ -18,7 +18,8 @@ json_pointer& operator/=(std::size_t array_idx)
 ## Parameters
 
 `ptr` (in)
-:    JSON pointer to append
+:    JSON pointer to append; may be the JSON pointer itself (`#!cpp p /= p`), which then appends a copy of its
+     reference tokens
 
 `token` (in)
 :    reference token to append
@@ -68,6 +69,7 @@ json_pointer& operator/=(std::size_t array_idx)
 
 ## Version history
 
-1. Added in version 3.6.0.
+1. Added in version 3.6.0. Appending a JSON pointer to itself no longer results in undefined behavior in version
+   3.13.0.
 2. Added in version 3.6.0. Changed type of `token` to `string_t` in version 3.11.0.
 3. Added in version 3.6.0.

include/nlohmann/detail/json_pointer.hpp

@@ -243,6 +243,13 @@ class json_pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/operator_slasheq/
     json_pointer& operator/=(const json_pointer& ptr)
     {
+        // insert() must not be given iterators into the vector it inserts
+        // into: append a copy when a pointer is appended to itself
+        if (JSON_HEDLEY_UNLIKELY(&ptr == this))
+        {
+            return *this /= json_pointer(ptr);
+        }
+
         reference_tokens.insert(reference_tokens.end(),
                                 ptr.reference_tokens.begin(),
                                 ptr.reference_tokens.end());

include/nlohmann/detail/view/edit.hpp

@@ -26,7 +26,6 @@
 #include <nlohmann/detail/view/lookup.hpp>
 #include <nlohmann/detail/view/macro_scope.hpp>
 #include <nlohmann/detail/view/node.hpp>
-#include <nlohmann/detail/view/scan.hpp>
 #include <nlohmann/detail/view/view_mode.hpp>
 
 NLOHMANN_JSON_NAMESPACE_BEGIN
@@ -47,9 +46,10 @@ struct first_true<false, Conditions...> : std::integral_constant < int, 1 + firs
 /// (type_error.316 with the same message), so that an editable document
 /// only holds valid UTF-8: the error is at the first byte that no
 /// well-formed sequence can continue with (Unicode, Table 3-7).
-NLOHMANN_VIEW_ALWAYS_INLINE void check_utf8_bytewise(const unsigned char* p, std::size_t n, std::size_t i)
+inline void check_utf8(const char* s, std::size_t n)
 {
-    for (; i < n;)
+    const auto* const p = reinterpret_cast<const unsigned char*>(s); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast)
+    for (std::size_t i = 0; i < n;)
     {
         const unsigned char c = p[i];
         if (c < 0x80)
@@ -79,43 +79,6 @@ NLOHMANN_VIEW_ALWAYS_INLINE void check_utf8_bytewise(const unsigned char* p, std
     }
 }
 
-/// The long-string path of check_utf8(): skips well-formed runs with the
-/// parser's string scan (which stops at a quote, a backslash, or a control
-/// character, all legal here, and at ill-formed UTF-8); the byte-wise check
-/// runs only from where the scan found ill-formed UTF-8, to report it.
-NLOHMANN_VIEW_NOINLINE inline void check_utf8_scan(const unsigned char* p, std::size_t n)
-{
-    const unsigned char* const e = p + n;
-    const unsigned char* q = p;
-    for (;;)
-    {
-        q = scan_string_run<true>(q, e);
-        if (q == e)
-        {
-            return;
-        }
-        if (*q >= 0x80)
-        {
-            check_utf8_bytewise(p, n, static_cast<std::size_t>(q - p));
-            return; // not reached: the scan stopped at ill-formed UTF-8
-        }
-        ++q; // a quote, backslash, or control character
-    }
-}
-
-inline void check_utf8(const char* s, std::size_t n)
-{
-    const auto* const p = reinterpret_cast<const unsigned char*>(s); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast)
-    if (NLOHMANN_VIEW_UNLIKELY(n >= 32))
-    {
-        check_utf8_scan(p, n);
-        return;
-    }
-    // short strings: the vector scan costs more than it saves; (the loop is
-    // inlined with a constant start, so this path is the plain byte-wise check)
-    check_utf8_bytewise(p, n, 0);
-}
-
 /*!
 @brief the edits of an editable basic_json_document
 

include/nlohmann/json.hpp

@@ -6950,6 +6950,15 @@ public:
     /// @sa https://json.nlohmann.me/api/basic_json/patch/
     void patch_inplace(const basic_json& json_patch)
     {
+        // the operations below change *this while iterating json_patch: apply
+        // a copy when a value is applied as patch to itself
+        if (JSON_HEDLEY_UNLIKELY(&json_patch == this))
+        {
+            const basic_json json_patch_copy = json_patch;
+            patch_inplace(json_patch_copy);
+            return;
+        }
+
         basic_json& result = *this;
         // the valid JSON Patch operations
         enum class patch_operations {add, remove, replace, move, copy, test, invalid};

single_include/nlohmann/json.hpp

@@ -24307,6 +24307,13 @@ class json_pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/operator_slasheq/
     json_pointer& operator/=(const json_pointer& ptr)
     {
+        // insert() must not be given iterators into the vector it inserts
+        // into: append a copy when a pointer is appended to itself
+        if (JSON_HEDLEY_UNLIKELY(&ptr == this))
+        {
+            return *this /= json_pointer(ptr);
+        }
+
         reference_tokens.insert(reference_tokens.end(),
                                 ptr.reference_tokens.begin(),
                                 ptr.reference_tokens.end());
@@ -43245,6 +43252,15 @@ public:
     /// @sa https://json.nlohmann.me/api/basic_json/patch/
     void patch_inplace(const basic_json& json_patch)
     {
+        // the operations below change *this while iterating json_patch: apply
+        // a copy when a value is applied as patch to itself
+        if (JSON_HEDLEY_UNLIKELY(&json_patch == this))
+        {
+            const basic_json json_patch_copy = json_patch;
+            patch_inplace(json_patch_copy);
+            return;
+        }
+
         basic_json& result = *this;
         // the valid JSON Patch operations
         enum class patch_operations {add, remove, replace, move, copy, test, invalid};

single_include/nlohmann/json_view.hpp

@@ -3740,8 +3740,6 @@ NLOHMANN_JSON_NAMESPACE_END
 
 // #include <nlohmann/detail/view/node.hpp>
 
-// #include <nlohmann/detail/view/scan.hpp>
-
 // #include <nlohmann/detail/view/view_mode.hpp>
 //     __ _____ _____ _____
 //  __|  |   __|     |   | |  JSON for Modern C++
@@ -3815,9 +3813,10 @@ struct first_true<false, Conditions...> : std::integral_constant < int, 1 + firs
 /// (type_error.316 with the same message), so that an editable document
 /// only holds valid UTF-8: the error is at the first byte that no
 /// well-formed sequence can continue with (Unicode, Table 3-7).
-NLOHMANN_VIEW_ALWAYS_INLINE void check_utf8_bytewise(const unsigned char* p, std::size_t n, std::size_t i)
+inline void check_utf8(const char* s, std::size_t n)
 {
-    for (; i < n;)
+    const auto* const p = reinterpret_cast<const unsigned char*>(s); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast)
+    for (std::size_t i = 0; i < n;)
     {
         const unsigned char c = p[i];
         if (c < 0x80)
@@ -3847,43 +3846,6 @@ NLOHMANN_VIEW_ALWAYS_INLINE void check_utf8_bytewise(const unsigned char* p, std
     }
 }
 
-/// The long-string path of check_utf8(): skips well-formed runs with the
-/// parser's string scan (which stops at a quote, a backslash, or a control
-/// character, all legal here, and at ill-formed UTF-8); the byte-wise check
-/// runs only from where the scan found ill-formed UTF-8, to report it.
-NLOHMANN_VIEW_NOINLINE inline void check_utf8_scan(const unsigned char* p, std::size_t n)
-{
-    const unsigned char* const e = p + n;
-    const unsigned char* q = p;
-    for (;;)
-    {
-        q = scan_string_run<true>(q, e);
-        if (q == e)
-        {
-            return;
-        }
-        if (*q >= 0x80)
-        {
-            check_utf8_bytewise(p, n, static_cast<std::size_t>(q - p));
-            return; // not reached: the scan stopped at ill-formed UTF-8
-        }
-        ++q; // a quote, backslash, or control character
-    }
-}
-
-inline void check_utf8(const char* s, std::size_t n)
-{
-    const auto* const p = reinterpret_cast<const unsigned char*>(s); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast)
-    if (NLOHMANN_VIEW_UNLIKELY(n >= 32))
-    {
-        check_utf8_scan(p, n);
-        return;
-    }
-    // short strings: the vector scan costs more than it saves; (the loop is
-    // inlined with a constant start, so this path is the plain byte-wise check)
-    check_utf8_bytewise(p, n, 0);
-}
-
 /*!
 @brief the edits of an editable basic_json_document
 

tests/src/unit-json_patch.cpp

@@ -826,6 +826,109 @@ TEST_CASE("JSON patch")
             CHECK(doc.at("foo") == "bar");
         }
 #endif // !defined(JSON_NOEXCEPTION)
+
+        SECTION("applying a value as patch to itself")
+        {
+            // a JSON patch is an array, so an array of operations can be
+            // applied to itself; the operations are read from the patch as
+            // it was before the first operation, as patch() does it
+            const json copy_op = {{"op", "copy"}, {"from", "/0"}, {"path", "/-"}};
+            json copy_ops = json::array();
+            for (int i = 0; i < 5; ++i)
+            {
+                copy_ops.push_back(copy_op);
+            }
+
+            json expected_copies = copy_ops;
+            for (int i = 0; i < 5; ++i)
+            {
+                expected_copies.push_back(copy_op);
+            }
+
+            SECTION("copy operations without spare capacity")
+            {
+                json doc = copy_ops;
+                doc.get_ref<json::array_t&>().shrink_to_fit();
+                CHECK(doc.patch(doc) == expected_copies);
+
+                doc.patch_inplace(doc);
+                CHECK(doc == expected_copies);
+            }
+
+            SECTION("copy operations with spare capacity")
+            {
+                json doc = copy_ops;
+                doc.get_ref<json::array_t&>().reserve(100);
+                CHECK(doc.patch(doc) == expected_copies);
+
+                doc.patch_inplace(doc);
+                CHECK(doc == expected_copies);
+            }
+
+            SECTION("remove operations")
+            {
+                json doc = R"([
+                        {"op": "remove", "path": "/0"},
+                        {"op": "remove", "path": "/0"},
+                        {"op": "remove", "path": "/0"}
+                    ])"_json;
+                CHECK(doc.patch(doc) == json::array());
+
+                doc.patch_inplace(doc);
+                CHECK(doc == json::array());
+            }
+
+            SECTION("operations that read a changed element")
+            {
+                // the second operation is still a "test" operation, although
+                // the first one replaced it in the document
+                json doc = R"([
+                        {"op": "replace", "path": "/1", "value": 1},
+                        {"op": "test", "path": "/1", "value": 1},
+                        {"op": "add", "path": "/-", "value": 2}
+                    ])"_json;
+                const json expected = R"([
+                        {"op": "replace", "path": "/1", "value": 1},
+                        1,
+                        {"op": "add", "path": "/-", "value": 2},
+                        2
+                    ])"_json;
+                CHECK(doc.patch(doc) == expected);
+
+                doc.patch_inplace(doc);
+                CHECK(doc == expected);
+            }
+
+            SECTION("replacing the root")
+            {
+                json doc = R"([
+                        {"op": "add", "path": "", "value": [1, 2]},
+                        {"op": "add", "path": "/-", "value": 3},
+                        {"op": "replace", "path": "", "value": {"a": 4}}
+                    ])"_json;
+                const json expected = {{"a", 4}};
+                CHECK(doc.patch(doc) == expected);
+
+                doc.patch_inplace(doc);
+                CHECK(doc == expected);
+            }
+
+#if !defined(JSON_NOEXCEPTION)
+            SECTION("failing operation")
+            {
+                // the operations before the failing one remain applied
+                json doc = R"([
+                        {"op": "add", "path": "/-", "value": 1},
+                        {"op": "test", "path": "/0/op", "value": "remove"}
+                    ])"_json;
+                CHECK_THROWS_AS(doc.patch(doc), json::other_error&);
+
+                CHECK_THROWS_AS(doc.patch_inplace(doc), json::other_error&);
+                CHECK(doc.size() == 3);
+                CHECK(doc.back() == 1);
+            }
+#endif // !defined(JSON_NOEXCEPTION)
+        }
     }
 
     SECTION("errors")

tests/src/unit-json_pointer.cpp

@@ -845,6 +845,44 @@ TEST_CASE("JSON pointers")
         CHECK(ptr.to_string() == "/object/~1");
     }
 
+    SECTION("appending a pointer to itself")
+    {
+        // operator/= must not pass iterators into its own token vector to
+        // insert(); each pointer is appended to itself and must yield the
+        // pointer whose string representation is the original one twice
+        const std::vector<std::string> pointers =
+        {
+            "",
+            "/",
+            "/a",
+            "/a/b",
+            "/foo/0/-",
+            "/a~1b/~0c/~01",
+            "/1/2/3/4/5/6/7/8/9/10/11/12/13/14/15/16/17"
+        };
+
+        for (const auto& s : pointers)
+        {
+            CAPTURE(s)
+            json::json_pointer ptr(s);
+            const json::json_pointer expected(s + s);
+
+            json::json_pointer& ret = (ptr /= ptr);
+            CHECK(&ret == &ptr);
+            CHECK(ptr == expected);
+            CHECK(ptr.to_string() == s + s);
+
+            // appending to itself again doubles the pointer once more
+            ptr /= ptr;
+            CHECK(ptr.to_string() == s + s + s + s);
+
+            // operator/ appends to a copy and leaves the operand unchanged
+            const json::json_pointer original(s);
+            CHECK((original / original) == expected);
+            CHECK(original.to_string() == s);
+        }
+    }
+
     SECTION("equality comparison")
     {
         std::string ptr_string{"/foo/bar"};

tests/src/unit-json_view_edit.cpp

@@ -941,123 +941,3 @@ TEST_CASE("json_view edits: duplicate keys")
         CHECK(d.root()["o"]["d"].get<int>() == 0);
     }
 }
-
-#if !defined(JSON_NOEXCEPTION)
-TEST_CASE("json_view edits: check_utf8 agrees with the byte-wise check")
-{
-    namespace dv = nlohmann::detail::view;
-
-    // "ok" or the exception message
-    const auto run = [](bool fast, const std::string & s) -> std::string
-    {
-        try
-        {
-            if (fast)
-            {
-                dv::check_utf8(s.data(), s.size());
-            }
-            else
-            {
-                dv::check_utf8_bytewise(reinterpret_cast<const unsigned char*>(s.data()), s.size(), 0);
-            }
-        }
-        catch (const json::type_error& e)
-        {
-            return {e.what()};
-        }
-        return {"ok"};
-    };
-    std::size_t errors = 0;
-    const auto same = [&](const std::string & s)
-    {
-        const std::string a = run(true, s);
-        const std::string b = run(false, s);
-        if (a != b)
-        {
-            INFO("fast: " << a << ", byte-wise: " << b << ", length " << s.size());
-            CHECK(a == b);
-        }
-        errors += b != "ok" ? 1 : 0;
-    };
-
-    const std::vector<std::string> pieces =
-    {
-        "a", "Z", " ", "\"", "\\", "\n", "\x01", "\x7f", "\xc3\xa4", "\xe4\xb8\xad", "\xf0\x9f\x98\x80",
-        "\x80", "\xbf", "\xc0\x80", "\xc1\xbf", "\xc2", "\xe0\x80\x80", "\xe0\x9f\xbf", "\xed\xa0\x80", "\xed\xbf\xbf",
-        "\xf0\x80\x80\x80", "\xf0\x8f\xbf\xbf", "\xf4\x90\x80\x80", "\xf4\x8f\xbf\xbf", "\xf5", "\xf8", "\xff", "\xfe",
-        "\xe4\xb8", "\xf0\x9f\x98", "\xf0\x9f", "\xf0"
-    };
-
-    // every piece behind prefixes of every length, and followed by more bytes
-    for (std::size_t prefix = 0; prefix <= 64; ++prefix)
-    {
-        for (const auto& piece : pieces)
-        {
-            same(std::string(prefix, 'x') + piece);
-            same(std::string(prefix, 'x') + piece + "yz");
-            same(std::string(prefix, '"') + piece);
-            same(std::string(prefix, '\xc3') + piece);
-            same(std::string(prefix / 2, '\xc3').append(prefix / 2, '\xa4') + piece);
-            same(std::string(prefix, 'x') + "\xe4\xb8\xad" + piece);
-        }
-    }
-    // an invalid byte at every position of valid strings of every length
-    for (std::size_t len = 0; len <= 64; ++len)
-    {
-        const std::string ascii(len, 'a');
-        std::string mixed;
-        while (mixed.size() < len)
-        {
-            if (mixed.size() % 7 == 0)
-            {
-                mixed += "\xc3\xa4";
-            }
-            else if (mixed.size() % 11 == 0)
-            {
-                mixed += "\xf0\x9f\x98\x80";
-            }
-            else
-            {
-                mixed += "a";
-            }
-        }
-        same(ascii);
-        same(mixed);
-        for (std::size_t pos = 0; pos < len; ++pos)
-        {
-            for (const char bad :
-                    {'\x80', '\xc0', '\xc2', '\xe0', '\xf4', '\xff', '"', '\\', '\x1f'
-                    })
-            {
-                std::string s = ascii;
-                s[pos] = bad;
-                same(s);
-                s = mixed;
-                s[pos] = bad;
-                same(s);
-            }
-        }
-    }
-    // random bytes, biased to the interesting ones
-    std::mt19937 gen(5869); // NOLINT(cert-msc32-c,cert-msc51-cpp,bugprone-random-generator-seed): reproducible
-    static const std::array<unsigned char, 23> interesting = {{0x00, 0x1f, 0x22, 0x5c, 0x7f, 0x80, 0x8f, 0x90, 0x9f, 0xa0, 0xbf, 0xc0, 0xc2, 0xdf, 0xe0, 0xe1, 0xed, 0xef, 0xf0, 0xf1, 0xf4, 0xf5, 0xff}};
-    for (int i = 0; i < 100000; ++i)
-    {
-        std::string s(gen() % 80, 'a');
-        for (auto& c : s)
-        {
-            const unsigned r = gen() % 8;
-            if (r == 0)
-            {
-                c = static_cast<char>(gen() & 0xff);
-            }
-            else if (r == 1)
-            {
-                c = static_cast<char>(interesting[gen() % interesting.size()]);
-            }
-        }
-        same(s);
-    }
-    CHECK(errors > 1000);
-}
-#endif