//     __ _____ _____ _____
//  __|  |   __|     |   | |  JSON for Modern C++ (supporting code)
// |  |  |__   |  |  | | | |  version 3.12.0
// |_____|_____|_____|_|___|  https://github.com/nlohmann/json
//
// SPDX-FileCopyrightText: 2013-2026 Niels Lohmann <https://nlohmann.me>
// SPDX-License-Identifier: MIT

#include "doctest_compatibility.h"

#include <nlohmann/json.hpp>
using nlohmann::json;
#ifdef JSON_TEST_NO_GLOBAL_UDLS
    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>
#include "make_test_data_available.hpp"

namespace
{
// alternating objects and arrays nested `depth` levels deep, with members that
// depend on `variant` at some levels, so diffing two variants yields
// operations on many levels: replacing the innermost value, adding, removing,
// and (for ordered_json) reordering members, and changing array lengths
template<typename BasicJsonType>
BasicJsonType nested(const std::size_t depth, const int variant)
{
    BasicJsonType value = variant;
    for (std::size_t i = 0; i < depth; ++i)
    {
        if (i % 2 == 0)
        {
            BasicJsonType object = BasicJsonType::object();
            if ((i + static_cast<std::size_t>(variant)) % 7 == 0)
            {
                object["x"] = i;
            }
            if (variant == 2 && i % 11 == 0)
            {
                object["z"] = "z";
            }
            object["a"] = std::move(value);
            if (variant == 1 && i % 5 == 0)
            {
                object["y"] = 1;
            }
            value = std::move(object);
        }
        else
        {
            BasicJsonType array = BasicJsonType::array({std::move(value)});
            if ((i + static_cast<std::size_t>(variant)) % 3 == 0)
            {
                array.push_back(i);
            }
            value = std::move(array);
        }
    }
    return value;
}

// a path of `depth` reference tokens, as nested() nests its values
std::string nested_path(const std::size_t depth)
{
    std::string path;
    for (std::size_t i = depth; i > 0; --i)
    {
        path += (i - 1) % 2 == 0 ? "/a" : "/0";
    }
    return path;
}
} // namespace

TEST_CASE("JSON patch")
{
    SECTION("examples from RFC 6902")
    {
        SECTION("4. Operations")
        {
            // the ordering of members in JSON objects is not significant:
            const json op1 = R"({ "op": "add", "path": "/a/b/c", "value": "foo" })"_json;
            const json op2 = R"({ "path": "/a/b/c", "op": "add", "value": "foo" })"_json;
            const json op3 = R"({ "value": "foo", "path": "/a/b/c", "op": "add" })"_json;

            // check if the operation objects are equivalent
            CHECK(op1 == op2);
            CHECK(op1 == op3);
        }

        SECTION("4.1 add")
        {
            json const patch1 = R"([{ "op": "add", "path": "/a/b", "value": [ "foo", "bar" ] }])"_json;

            // However, the object itself or an array containing it does need
            // to exist, and it remains an error for that not to be the case.
            // For example, an "add" with a target location of "/a/b" starting
            // with this document
            json const doc1 = R"({ "a": { "foo": 1 } })"_json;

            // is not an error, because "a" exists, and "b" will be added to
            // its value.
            CHECK_NOTHROW(doc1.patch(patch1));
            auto doc1_ans = R"(
                {
                    "a": {
                        "foo": 1,
                        "b": [ "foo", "bar" ]
                    }
                }
            )"_json;
            CHECK(doc1.patch(patch1) == doc1_ans);

            // It is an error in this document:
            json const doc2 = R"({ "q": { "bar": 2 } })"_json;

            // because "a" does not exist.
#if JSON_DIAGNOSTIC_POSITIONS
            CHECK_THROWS_WITH_AS(doc2.patch(patch1), "[json.exception.out_of_range.403] (bytes 0-21) key 'a' not found", json::out_of_range&);
#else
            CHECK_THROWS_WITH_AS(doc2.patch(patch1), "[json.exception.out_of_range.403] key 'a' not found", json::out_of_range&);
#endif

            json const doc3 = R"({ "a": {} })"_json;
            json const patch2 = R"([{ "op": "add", "path": "/a/b/c", "value": 1 }])"_json;

            // should cause an error because "b" does not exist in doc3
#if JSON_DIAGNOSTICS
            CHECK_THROWS_WITH_AS(doc3.patch(patch2), "[json.exception.out_of_range.403] (/a) key 'b' not found", json::out_of_range&);
#elif JSON_DIAGNOSTIC_POSITIONS
            CHECK_THROWS_WITH_AS(doc3.patch(patch2), "[json.exception.out_of_range.403] (bytes 7-9) key 'b' not found", json::out_of_range&);
#else
            CHECK_THROWS_WITH_AS(doc3.patch(patch2), "[json.exception.out_of_range.403] key 'b' not found", json::out_of_range&);
#endif
        }

        SECTION("4.2 remove")
        {
            // If removing an element from an array, any elements above the
            // specified index are shifted one position to the left.
            json const doc = {1, 2, 3, 4};
            json const patch = {{{"op", "remove"}, {"path", "/1"}}};
            CHECK(doc.patch(patch) == json({1, 3, 4}));
        }

        SECTION("A.1. Adding an Object Member")
        {
            // An example target JSON document:
            json const doc = R"(
                    { "foo": "bar"}
                )"_json;

            // A JSON Patch document:
            json const patch = R"(
                    [
                        { "op": "add", "path": "/baz", "value": "qux" }
                    ]
                )"_json;

            // The resulting JSON document:
            json expected = R"(
                    {
                        "baz": "qux",
                        "foo": "bar"
                    }
                )"_json;

            // check if patched value is as expected
            CHECK(doc.patch(patch) == expected);

            // check roundtrip
            CHECK(doc.patch(json::diff(doc, expected)) == expected);
        }

        SECTION("A.2. Adding an Array Element")
        {
            // An example target JSON document:
            json const doc = R"(
                    { "foo": [ "bar", "baz" ] }
                )"_json;

            // A JSON Patch document:
            json const patch = R"(
                    [
                        { "op": "add", "path": "/foo/1", "value": "qux" }
                    ]
                )"_json;

            // The resulting JSON document:
            json expected = R"(
                    { "foo": [ "bar", "qux", "baz" ] }
                )"_json;

            // check if patched value is as expected
            CHECK(doc.patch(patch) == expected);

            // check roundtrip
            CHECK(doc.patch(json::diff(doc, expected)) == expected);
        }

        SECTION("A.3. Removing an Object Member")
        {
            // An example target JSON document:
            json const doc = R"(
                    {
                        "baz": "qux",
                        "foo": "bar"
                    }
                )"_json;

            // A JSON Patch document:
            json const patch = R"(
                    [
                        { "op": "remove", "path": "/baz" }
                    ]
                )"_json;

            // The resulting JSON document:
            json expected = R"(
                    { "foo": "bar" }
                )"_json;

            // check if patched value is as expected
            CHECK(doc.patch(patch) == expected);

            // check roundtrip
            CHECK(doc.patch(json::diff(doc, expected)) == expected);
        }

        SECTION("A.4. Removing an Array Element")
        {
            // An example target JSON document:
            json const doc = R"(
                    { "foo": [ "bar", "qux", "baz" ] }
                )"_json;

            // A JSON Patch document:
            json const patch = R"(
                    [
                        { "op": "remove", "path": "/foo/1" }
                    ]
                )"_json;

            // The resulting JSON document:
            json expected = R"(
                    { "foo": [ "bar", "baz" ] }
                )"_json;

            // check if patched value is as expected
            CHECK(doc.patch(patch) == expected);

            // check roundtrip
            CHECK(doc.patch(json::diff(doc, expected)) == expected);
        }

        SECTION("A.5. Replacing a Value")
        {
            // An example target JSON document:
            json const doc = R"(
                    {
                        "baz": "qux",
                        "foo": "bar"
                    }
                )"_json;

            // A JSON Patch document:
            json const patch = R"(
                    [
                        { "op": "replace", "path": "/baz", "value": "boo" }
                    ]
                )"_json;

            json expected = R"(
                    {
                        "baz": "boo",
                        "foo": "bar"
                    }
                )"_json;

            // check if patched value is as expected
            CHECK(doc.patch(patch) == expected);

            // check roundtrip
            CHECK(doc.patch(json::diff(doc, expected)) == expected);
        }

        SECTION("A.6. Moving a Value")
        {
            // An example target JSON document:
            json const doc = R"(
                    {
                        "foo": {
                           "bar": "baz",
                            "waldo": "fred"
                        },
                        "qux": {
                            "corge": "grault"
                        }
                    }
                )"_json;

            // A JSON Patch document:
            json const patch = R"(
                    [
                        { "op": "move", "from": "/foo/waldo", "path": "/qux/thud" }
                    ]
                )"_json;

            // The resulting JSON document:
            json expected = R"(
                    {
                        "foo": {
                           "bar": "baz"
                        },
                        "qux": {
                            "corge": "grault",
                            "thud": "fred"
                        }
                    }
                )"_json;

            // check if patched value is as expected
            CHECK(doc.patch(patch) == expected);

            // check roundtrip
            CHECK(doc.patch(json::diff(doc, expected)) == expected);
        }

        SECTION("A.7. Moving a Value")
        {
            // An example target JSON document:
            json const doc = R"(
                    { "foo": [ "all", "grass", "cows", "eat" ] }
                )"_json;

            // A JSON Patch document:
            json const patch = R"(
                    [
                        { "op": "move", "from": "/foo/1", "path": "/foo/3" }
                    ]
                )"_json;

            // The resulting JSON document:
            json expected = R"(
                    { "foo": [ "all", "cows", "eat", "grass" ] }
                )"_json;

            // check if patched value is as expected
            CHECK(doc.patch(patch) == expected);

            // check roundtrip
            CHECK(doc.patch(json::diff(doc, expected)) == expected);
        }

        SECTION("A.8. Testing a Value: Success")
        {
            // An example target JSON document:
            json doc = R"(
                    {
                         "baz": "qux",
                         "foo": [ "a", 2, "c" ]
                    }
                )"_json;

            // A JSON Patch document that will result in successful evaluation:
            json const patch = R"(
                    [
                        { "op": "test", "path": "/baz", "value": "qux" },
                        { "op": "test", "path": "/foo/1", "value": 2 }
                    ]
                )"_json;

            // check if evaluation does not throw
            CHECK_NOTHROW(doc.patch(patch));
            // check if patched document is unchanged
            CHECK(doc.patch(patch) == doc);
        }

        SECTION("A.9. Testing a Value: Error")
        {
            // An example target JSON document:
            json const doc = R"(
                    { "baz": "qux" }
                )"_json;

            // A JSON Patch document that will result in an error condition:
            json patch = R"(
                    [
                        { "op": "test", "path": "/baz", "value": "bar" }
                    ]
                )"_json;

            // check that evaluation throws
            CHECK_THROWS_AS(doc.patch(patch), json::other_error&);
#if JSON_DIAGNOSTICS
            CHECK_THROWS_WITH_STD_STR(doc.patch(patch), "[json.exception.other_error.501] (/0) unsuccessful: " + patch[0].dump());
#elif JSON_DIAGNOSTIC_POSITIONS
            CHECK_THROWS_WITH_STD_STR(doc.patch(patch), "[json.exception.other_error.501] (bytes 47-95) unsuccessful: " + patch[0].dump());
#else
            CHECK_THROWS_WITH_STD_STR(doc.patch(patch), "[json.exception.other_error.501] unsuccessful: " + patch[0].dump());
#endif
        }

        SECTION("A.10. Adding a Nested Member Object")
        {
            // An example target JSON document:
            json const doc = R"(
                    { "foo": "bar" }
                )"_json;

            // A JSON Patch document:
            json const patch = R"(
                    [
                        { "op": "add", "path": "/child", "value": { "grandchild": { } } }
                    ]
                )"_json;

            // The resulting JSON document:
            json expected = R"(
                {
                    "foo": "bar",
                    "child": {
                        "grandchild": {
                        }
                    }
                }
                )"_json;

            // check if patched value is as expected
            CHECK(doc.patch(patch) == expected);

            // check roundtrip
            CHECK(doc.patch(json::diff(doc, expected)) == expected);
        }

        SECTION("A.11. Ignoring Unrecognized Elements")
        {
            // An example target JSON document:
            json const doc = R"(
                    { "foo": "bar" }
                )"_json;

            // A JSON Patch document:
            json const patch = R"(
                    [
                        { "op": "add", "path": "/baz", "value": "qux", "xyz": 123 }
                    ]
                )"_json;

            json expected = R"(
                    {
                        "foo": "bar",
                        "baz": "qux"
                    } 
                )"_json;

            // check if patched value is as expected
            CHECK(doc.patch(patch) == expected);

            // check roundtrip
            CHECK(doc.patch(json::diff(doc, expected)) == expected);
        }

        SECTION("A.12. Adding to a Nonexistent Target")
        {
            // An example target JSON document:
            json const doc = R"(
                    { "foo": "bar" }
                )"_json;

            // A JSON Patch document:
            json const patch = R"(
                    [
                        { "op": "add", "path": "/baz/bat", "value": "qux" }
                    ]
                )"_json;

            // This JSON Patch document, applied to the target JSON document
            // above, would result in an error (therefore, it would not be
            // applied), because the "add" operation's target location that
            // references neither the root of the document, nor a member of
            // an existing object, nor a member of an existing array.
#if JSON_DIAGNOSTIC_POSITIONS
            CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.403] (bytes 21-37) key 'baz' not found", json::out_of_range&);
#else
            CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.403] key 'baz' not found", json::out_of_range&);
#endif
        }

        // A.13. Invalid JSON Patch Document
        // not applicable: the library cannot tell the duplicate "op" members
        // apart, because the parser resolves them (the last one is kept); see
        // "duplicate member names in an operation" below

        SECTION("A.14. Escape Ordering")
        {
            // An example target JSON document:
            json const doc = R"(
                    {
                        "/": 9,
                        "~1": 10
                    }
                )"_json;

            // A JSON Patch document:
            json const patch = R"(
                    [
                        {"op": "test", "path": "/~01", "value": 10}
                    ]
                )"_json;

            json expected = R"(
                    {
                        "/": 9,
                        "~1": 10
                    } 
                )"_json;

            // check if patched value is as expected
            CHECK(doc.patch(patch) == expected);

            // check roundtrip
            CHECK(doc.patch(json::diff(doc, expected)) == expected);
        }

        SECTION("A.15. Comparing Strings and Numbers")
        {
            // An example target JSON document:
            json const doc = R"(
                    {
                        "/": 9,
                        "~1": 10
                    } 
                )"_json;

            // A JSON Patch document that will result in an error condition:
            json patch = R"(
                    [
                        {"op": "test", "path": "/~01", "value": "10"}
                    ]
                )"_json;

            // check that evaluation throws
            CHECK_THROWS_AS(doc.patch(patch), json::other_error&);
#if JSON_DIAGNOSTICS
            CHECK_THROWS_WITH_STD_STR(doc.patch(patch), "[json.exception.other_error.501] (/0) unsuccessful: " + patch[0].dump());
#elif JSON_DIAGNOSTIC_POSITIONS
            CHECK_THROWS_WITH_STD_STR(doc.patch(patch), "[json.exception.other_error.501] (bytes 47-92) unsuccessful: " + patch[0].dump());
#else
            CHECK_THROWS_WITH_STD_STR(doc.patch(patch), "[json.exception.other_error.501] unsuccessful: " + patch[0].dump());
#endif
        }

        SECTION("A.16. Adding an Array Value")
        {
            // An example target JSON document:
            json const doc = R"(
                    { "foo": ["bar"] }
                )"_json;

            // A JSON Patch document:
            json const patch = R"(
                    [
                        { "op": "add", "path": "/foo/-", "value": ["abc", "def"] }
                    ]
                )"_json;

            // The resulting JSON document:
            json expected = R"(
                    { "foo": ["bar", ["abc", "def"]] }
                )"_json;

            // check if patched value is as expected
            CHECK(doc.patch(patch) == expected);

            // check roundtrip
            CHECK(doc.patch(json::diff(doc, expected)) == expected);
        }
    }

    SECTION("own examples")
    {
        SECTION("add")
        {
            SECTION("add to the root element")
            {
                // If the path is the root of the target document - the
                // specified value becomes the entire content of the target
                // document.

                // An example target JSON document:
                json const doc = 17;

                // A JSON Patch document:
                json const patch = R"(
                        [
                            { "op": "add", "path": "", "value": [1,2,3] }
                        ]
                    )"_json;

                // The resulting JSON document:
                json expected = {1, 2, 3};

                // check if patched value is as expected
                CHECK(doc.patch(patch) == expected);

                // check roundtrip
                CHECK(doc.patch(json::diff(doc, expected)) == expected);
            }

            SECTION("add to end of the array")
            {
                // The specified index MUST NOT be greater than the number of
                // elements in the array. The example below uses and index of
                // exactly the number of elements in the array which is legal.

                // An example target JSON document:
                json const doc = {0, 1, 2};

                // A JSON Patch document:
                json const patch = R"(
                    [
                        { "op": "add", "path": "/3", "value": 3 }
                    ]
                )"_json;

                // The resulting JSON document:
                json expected = {0, 1, 2, 3};

                // check if patched value is as expected
                CHECK(doc.patch(patch) == expected);

                // check roundtrip
                CHECK(doc.patch(json::diff(doc, expected)) == expected);
            }
        }

        SECTION("copy")
        {
            // An example target JSON document:
            json const doc = R"(
                {
                    "foo": {
                        "bar": "baz",
                        "waldo": "fred"
                    },
                    "qux": {
                       "corge": "grault"
                    }
                }
            )"_json;

            // A JSON Patch document:
            json const patch = R"(
                [
                    { "op": "copy", "from": "/foo/waldo", "path": "/qux/thud" }
                ]
            )"_json;

            // The resulting JSON document:
            json expected = R"(
                {
                    "foo": {
                        "bar": "baz",
                        "waldo": "fred"
                    },
                    "qux": {
                       "corge": "grault",
                       "thud": "fred"
                    }
                }
            )"_json;

            // check if patched value is as expected
            CHECK(doc.patch(patch) == expected);

            // check roundtrip
            CHECK(doc.patch(json::diff(doc, expected)) == expected);
        }

        SECTION("replace")
        {
            json const j = "string";
            json const patch = {{{"op", "replace"}, {"path", ""}, {"value", 1}}};
            CHECK(j.patch(patch) == json(1));
        }

        SECTION("documentation GIF")
        {
            {
                // a JSON patch
                json const p1 = R"(
                     [{"op": "add", "path": "/GB", "value": "London"}]
                    )"_json;

                // a JSON value
                json const source = R"(
                      {"D": "Berlin", "F": "Paris"}
                    )"_json;

                // apply the patch
                const json target = source.patch(p1);
                // target = { "D": "Berlin", "F": "Paris", "GB": "London" }
                CHECK(target == R"({ "D": "Berlin", "F": "Paris", "GB": "London" })"_json);

                // create a diff from two JSONs
                const json p2 = json::diff(target, source); // NOLINT(readability-suspicious-call-argument)
                // p2 = [{"op": "delete", "path": "/GB"}]
                CHECK(p2 == R"([{"op":"remove","path":"/GB"}])"_json);
            }
            {
                // a JSON value
                json j = {"good", "bad", "ugly"};

                // a JSON pointer
                auto ptr = json::json_pointer("/2");

                // use to access elements
                j[ptr] = {{"it", "cattivo"}};
                CHECK(j == R"(["good","bad",{"it":"cattivo"}])"_json);

                // use user-defined string literal
                j["/2/en"_json_pointer] = "ugly";
                CHECK(j == R"(["good","bad",{"en":"ugly","it":"cattivo"}])"_json);

                const json flat = j.flatten();
                CHECK(flat == R"({"/0":"good","/1":"bad","/2/en":"ugly","/2/it":"cattivo"})"_json);
            }
        }
    }

    SECTION("patch_inplace")
    {
        SECTION("happy path: patch_inplace mirrors patch() on success")
        {
            // mirrors "A.5. Replacing a Value" above, but applies the patch with
            // patch_inplace() to a mutable copy instead of using patch()'s
            // returned copy
            json doc = R"(
                    {
                        "baz": "qux",
                        "foo": "bar"
                    }
                )"_json;

            json const patch = R"(
                    [
                        { "op": "replace", "path": "/baz", "value": "boo" }
                    ]
                )"_json;

            json const expected = R"(
                    {
                        "baz": "boo",
                        "foo": "bar"
                    }
                )"_json;

            doc.patch_inplace(patch);
            CHECK(doc == expected);
        }

        // this test relies on the "test" operation actually throwing so the
        // partial-application state can be observed right after the throw
        // point; under JSON_NOEXCEPTION, JSON_THROW() calls std::abort()
        // instead (there is no C++ exception to throw), and doctest's
        // CHECK_THROWS_AS() is compiled out to a no-op that never even
        // invokes the given expression (see doctest's "--no-throw" test
        // filter, which ci_test_noexceptions passes) -- so patch()/
        // patch_inplace() would never be called at all and the follow-up
        // state assertions below would fail against the untouched original
#if !defined(JSON_NOEXCEPTION)
        SECTION("distinguishing contract vs patch(): partial application on failure")
        {
            // Unlike patch(), which is all-or-nothing because it applies the
            // patch to an internal copy that is simply discarded when an
            // exception is thrown (leaving the original untouched no matter
            // what), patch_inplace() mutates the document it is called on
            // directly and immediately, operation by operation. So if a JSON
            // Patch fails partway through, whatever operations already
            // succeeded remain applied -- the document is left in a partially
            // patched state. This is empirically verified current behavior,
            // not just documented intent, and is pinned here as such.
            json const original = R"(
                    {
                        "baz": "qux",
                        "foo": "bar"
                    }
                )"_json;

            // the first operation ("replace") succeeds; the second ("test")
            // fails because the value at "/baz" no longer (and never did)
            // equal "not boo"
            json const patch = R"(
                    [
                        { "op": "replace", "path": "/baz", "value": "boo" },
                        { "op": "test", "path": "/baz", "value": "not boo" }
                    ]
                )"_json;

            // patch() never modifies the object it is called on -- it always
            // operates on (and returns) a separate copy, so the original is
            // left completely untouched, regardless of success or failure.
            // copy_for_patch is intentionally a real copy, not a reference
            // to `original`: the whole point of this check is to catch a
            // hypothetical future regression where patch() *does* mutate its
            // receiver. Using a reference here would make the assertion
            // below compare `original` to itself -- trivially true even if
            // such a bug existed -- which is exactly what a static analyzer
            // can't see when it suggests "this copy is never modified, use
            // a reference instead".
            json copy_for_patch = original; // NOLINT(performance-unnecessary-copy-initialization)
            CHECK_THROWS_AS(copy_for_patch.patch(patch), json::other_error&);
            CHECK(copy_for_patch == original);

            // patch_inplace(), in contrast, already applied the successful
            // "replace" operation to the document before the "test" operation
            // threw -- that change is not rolled back
            json doc = original;
            CHECK_THROWS_AS(doc.patch_inplace(patch), json::other_error&);
            CHECK(doc != original);
            CHECK(doc.at("baz") == "boo");
            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")
            {
                // a copy has exactly as much capacity as elements
                json doc = copy_ops;
                CHECK(doc.patch(doc) == expected_copies);

                doc.patch_inplace(doc);
                CHECK(doc == expected_copies);
            }

#if JSON_DIAGNOSTICS
            SECTION("patch stored inside the patched value")
            {
                // the parent pointers of JSON_DIAGNOSTICS make the aliasing detectable
                const json op = {{"op", "replace"}, {"path", "/patch"}, {"value", 1}};
                json doc = {{"a", 1}, {"patch", json::array({op})}};
                const json expected = doc.patch(doc["patch"]);

                doc.patch_inplace(doc["patch"]);
                CHECK(doc == expected);
            }
#endif

            SECTION("copy operations with spare capacity")
            {
                // reserve while the array is empty: reallocating non-empty
                // elements behind the library's back leaves stale parent
                // pointers with JSON_DIAGNOSTICS
                json doc = json::array();
                doc.get_ref<json::array_t&>().reserve(100);
                for (int i = 0; i < 5; ++i)
                {
                    doc.push_back(copy_op);
                }
                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")
    {
        SECTION("unknown operation")
        {
            SECTION("not an array")
            {
                json const j;
                json const patch = {{"op", "add"}, {"path", ""}, {"value", 1}};
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.104] parse error: JSON patch must be an array of objects", json::parse_error&);
            }

            SECTION("not an array of objects")
            {
                json const j;
                json const patch = {"op", "add", "path", "", "value", 1};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.104] parse error: (/0) JSON patch must be an array of objects", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.104] parse error: JSON patch must be an array of objects", json::parse_error&);
#endif
            }

            SECTION("missing 'op'")
            {
                json const j;
                json const patch = {{{"foo", "bar"}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation must have member 'op'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation must have member 'op'", json::parse_error&);
#endif
            }

            SECTION("non-string 'op'")
            {
                json const j;
                json const patch = {{{"op", 1}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation must have string member 'op'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation must have string member 'op'", json::parse_error&);
#endif
            }

            SECTION("invalid operation")
            {
                json const j;
                json const patch = {{{"op", "foo"}, {"path", ""}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation value 'foo' is invalid", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation value 'foo' is invalid", json::parse_error&);
#endif
            }
        }

        SECTION("add")
        {
            SECTION("missing 'path'")
            {
                json const j;
                json const patch = {{{"op", "add"}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'add' must have member 'path'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'add' must have member 'path'", json::parse_error&);
#endif
            }

            SECTION("non-string 'path'")
            {
                json const j;
                json const patch = {{{"op", "add"}, {"path", 1}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'add' must have string member 'path'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'add' must have string member 'path'", json::parse_error&);
#endif
            }

            SECTION("missing 'value'")
            {
                json const j;
                json const patch = {{{"op", "add"}, {"path", ""}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'add' must have member 'value'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'add' must have member 'value'", json::parse_error&);
#endif
            }

            SECTION("invalid array index")
            {
                json const j = {1, 2};
                json const patch = {{{"op", "add"}, {"path", "/4"}, {"value", 4}}};
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.out_of_range.401] array index 4 is out of range", json::out_of_range&);
            }
        }

        SECTION("remove")
        {
            SECTION("missing 'path'")
            {
                json const j;
                json const patch = {{{"op", "remove"}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'remove' must have member 'path'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'remove' must have member 'path'", json::parse_error&);
#endif
            }

            SECTION("non-string 'path'")
            {
                json const j;
                json const patch = {{{"op", "remove"}, {"path", 1}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'remove' must have string member 'path'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'remove' must have string member 'path'", json::parse_error&);
#endif
            }

            SECTION("nonexisting target location (array)")
            {
                json const j = {1, 2, 3};
                json const patch = {{{"op", "remove"}, {"path", "/17"}}};
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.out_of_range.401] array index 17 is out of range", json::out_of_range&);
            }

            SECTION("nonexisting target location (object)")
            {
                json const j = {{"foo", 1}, {"bar", 2}};
                json const patch = {{{"op", "remove"}, {"path", "/baz"}}};
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.out_of_range.403] key 'baz' not found", json::out_of_range&);
            }

            SECTION("root element as target location")
            {
                json const j = "string";
                json const patch = {{{"op", "remove"}, {"path", ""}}};
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.out_of_range.405] JSON pointer has no parent", json::out_of_range&);
            }
        }

        SECTION("replace")
        {
            SECTION("missing 'path'")
            {
                json const j;
                json const patch = {{{"op", "replace"}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'replace' must have member 'path'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'replace' must have member 'path'", json::parse_error&);
#endif
            }

            SECTION("non-string 'path'")
            {
                json const j;
                json const patch = {{{"op", "replace"}, {"path", 1}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'replace' must have string member 'path'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'replace' must have string member 'path'", json::parse_error&);
#endif
            }

            SECTION("missing 'value'")
            {
                json const j;
                json const patch = {{{"op", "replace"}, {"path", ""}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'replace' must have member 'value'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'replace' must have member 'value'", json::parse_error&);
#endif
            }

            SECTION("nonexisting target location (array)")
            {
                json const j = {1, 2, 3};
                json const patch = {{{"op", "replace"}, {"path", "/17"}, {"value", 19}}};
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.out_of_range.401] array index 17 is out of range", json::out_of_range&);
            }

            SECTION("nonexisting target location (object)")
            {
                json const j = {{"foo", 1}, {"bar", 2}};
                json const patch = {{{"op", "replace"}, {"path", "/baz"}, {"value", 3}}};
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.out_of_range.403] key 'baz' not found", json::out_of_range&);
            }
        }

        SECTION("move")
        {
            SECTION("missing 'path'")
            {
                json const j;
                json const patch = {{{"op", "move"}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'move' must have member 'path'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'move' must have member 'path'", json::parse_error&);
#endif
            }

            SECTION("non-string 'path'")
            {
                json const j;
                json const patch = {{{"op", "move"}, {"path", 1}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'move' must have string member 'path'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'move' must have string member 'path'", json::parse_error&);
#endif
            }

            SECTION("missing 'from'")
            {
                json const j;
                json const patch = {{{"op", "move"}, {"path", ""}}};
                CHECK_THROWS_AS(j.patch(patch), json::parse_error&);
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'move' must have member 'from'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'move' must have member 'from'", json::parse_error&);
#endif
            }

            SECTION("non-string 'from'")
            {
                json const j;
                json const patch = {{{"op", "move"}, {"path", ""}, {"from", 1}}};
                CHECK_THROWS_AS(j.patch(patch), json::parse_error&);
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'move' must have string member 'from'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'move' must have string member 'from'", json::parse_error&);
#endif
            }

            SECTION("nonexisting from location (array)")
            {
                json const j = {1, 2, 3};
                json const patch = {{{"op", "move"}, {"path", "/0"}, {"from", "/5"}}};
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.out_of_range.401] array index 5 is out of range", json::out_of_range&);
            }

            SECTION("nonexisting from location (object)")
            {
                json const j = {{"foo", 1}, {"bar", 2}};
                json const patch = {{{"op", "move"}, {"path", "/baz"}, {"from", "/baz"}}};
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.out_of_range.403] key 'baz' not found", json::out_of_range&);
            }
        }

        SECTION("copy")
        {
            SECTION("missing 'path'")
            {
                json const j;
                json const patch = {{{"op", "copy"}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'copy' must have member 'path'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'copy' must have member 'path'", json::parse_error&);
#endif
            }

            SECTION("non-string 'path'")
            {
                json const j;
                json const patch = {{{"op", "copy"}, {"path", 1}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'copy' must have string member 'path'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'copy' must have string member 'path'", json::parse_error&);
#endif
            }

            SECTION("missing 'from'")
            {
                json const j;
                json const patch = {{{"op", "copy"}, {"path", ""}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'copy' must have member 'from'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'copy' must have member 'from'", json::parse_error&);
#endif
            }

            SECTION("non-string 'from'")
            {
                json const j;
                json const patch = {{{"op", "copy"}, {"path", ""}, {"from", 1}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'copy' must have string member 'from'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'copy' must have string member 'from'", json::parse_error&);
#endif
            }

            SECTION("nonexisting from location (array)")
            {
                json const j = {1, 2, 3};
                json const patch = {{{"op", "copy"}, {"path", "/0"}, {"from", "/5"}}};
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.out_of_range.401] array index 5 is out of range", json::out_of_range&);
            }

            SECTION("nonexisting from location (object)")
            {
                json const j = {{"foo", 1}, {"bar", 2}};
                json const patch = {{{"op", "copy"}, {"path", "/fob"}, {"from", "/baz"}}};
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.out_of_range.403] key 'baz' not found", json::out_of_range&);
            }
        }

        SECTION("test")
        {
            SECTION("missing 'path'")
            {
                json const j;
                json const patch = {{{"op", "test"}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'test' must have member 'path'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'test' must have member 'path'", json::parse_error&);
#endif
            }

            SECTION("non-string 'path'")
            {
                json const j;
                json const patch = {{{"op", "test"}, {"path", 1}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'test' must have string member 'path'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'test' must have string member 'path'", json::parse_error&);
#endif
            }

            SECTION("missing 'value'")
            {
                json const j;
                json const patch = {{{"op", "test"}, {"path", ""}}};
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: (/0) operation 'test' must have member 'value'", json::parse_error&);
#else
                CHECK_THROWS_WITH_AS(j.patch(patch), "[json.exception.parse_error.105] parse error: operation 'test' must have member 'value'", json::parse_error&);
#endif
            }
        }
    }

    SECTION("Examples from jsonpatch.com")
    {
        SECTION("Simple Example")
        {
            // The original document
            json const doc = R"(
                {
                  "baz": "qux",
                  "foo": "bar"
                }
            )"_json;

            // The patch
            json const patch = R"(
                [
                  { "op": "replace", "path": "/baz", "value": "boo" },
                  { "op": "add", "path": "/hello", "value": ["world"] },
                  { "op": "remove", "path": "/foo"}
                ]
            )"_json;

            // The result
            json result = R"(
                {
                   "baz": "boo",
                   "hello": ["world"]
                }
            )"_json;

            // check if patched value is as expected
            CHECK(doc.patch(patch) == result);

            // check roundtrip
            CHECK(doc.patch(json::diff(doc, result)) == result);
        }

        SECTION("Operations")
        {
            // The original document
            json const doc = R"(
                {
                  "biscuits": [
                    {"name":"Digestive"},
                    {"name": "Choco Liebniz"}
                  ]
                }
            )"_json;

            SECTION("add")
            {
                // The patch
                json const patch = R"(
                    [
                        {"op": "add", "path": "/biscuits/1", "value": {"name": "Ginger Nut"}}
                    ]
                )"_json;

                // The result
                json result = R"(
                    {
                      "biscuits": [
                        {"name": "Digestive"},
                        {"name": "Ginger Nut"},
                        {"name": "Choco Liebniz"}
                      ]
                    }
                )"_json;

                // check if patched value is as expected
                CHECK(doc.patch(patch) == result);

                // check roundtrip
                CHECK(doc.patch(json::diff(doc, result)) == result);
            }

            SECTION("remove")
            {
                // The patch
                json const patch = R"(
                    [
                        {"op": "remove", "path": "/biscuits"}
                    ]
                )"_json;

                // The result
                json result = R"(
                    {}
                )"_json;

                // check if patched value is as expected
                CHECK(doc.patch(patch) == result);

                // check roundtrip
                CHECK(doc.patch(json::diff(doc, result)) == result);
            }

            SECTION("replace")
            {
                // The patch
                json const patch = R"(
                    [
                        {"op": "replace", "path": "/biscuits/0/name", "value": "Chocolate Digestive"}
                    ]
                )"_json;

                // The result
                json result = R"(
                    {
                      "biscuits": [
                        {"name": "Chocolate Digestive"},
                        {"name": "Choco Liebniz"}
                      ]
                    }
                )"_json;

                // check if patched value is as expected
                CHECK(doc.patch(patch) == result);

                // check roundtrip
                CHECK(doc.patch(json::diff(doc, result)) == result);
            }

            SECTION("copy")
            {
                // The patch
                json const patch = R"(
                    [
                        {"op": "copy", "from": "/biscuits/0", "path": "/best_biscuit"}
                    ]
                )"_json;

                // The result
                json result = R"(
                    {
                      "biscuits": [
                        {"name": "Digestive"},
                        {"name": "Choco Liebniz"}
                      ],
                      "best_biscuit": {
                        "name": "Digestive"
                      }
                    }
                )"_json;

                // check if patched value is as expected
                CHECK(doc.patch(patch) == result);

                // check roundtrip
                CHECK(doc.patch(json::diff(doc, result)) == result);
            }

            SECTION("move")
            {
                // The patch
                json const patch = R"(
                    [
                        {"op": "move", "from": "/biscuits", "path": "/cookies"}
                    ]
                )"_json;

                // The result
                json result = R"(
                    {
                      "cookies": [
                        {"name": "Digestive"},
                        {"name": "Choco Liebniz"}
                      ]
                    }
                )"_json;

                // check if patched value is as expected
                CHECK(doc.patch(patch) == result);

                // check roundtrip
                CHECK(doc.patch(json::diff(doc, result)) == result);
            }

            SECTION("test")
            {
                // The patch
                json patch = R"(
                    [
                        {"op": "test", "path": "/best_biscuit/name", "value": "Choco Liebniz"}
                    ]
                )"_json;

                // the test will fail
                CHECK_THROWS_AS(doc.patch(patch), json::other_error&);
#if JSON_DIAGNOSTICS
                CHECK_THROWS_WITH_STD_STR(doc.patch(patch), "[json.exception.other_error.501] (/0) unsuccessful: " + patch[0].dump());
#elif JSON_DIAGNOSTIC_POSITIONS
                CHECK_THROWS_WITH_STD_STR(doc.patch(patch), "[json.exception.other_error.501] (bytes 47-117) unsuccessful: " + patch[0].dump());
#else
                CHECK_THROWS_WITH_STD_STR(doc.patch(patch), "[json.exception.other_error.501] unsuccessful: " + patch[0].dump());
#endif
            }
        }
    }

    SECTION("Examples from bruth.github.io/jsonpatch-js")
    {
        SECTION("add")
        {
            CHECK(R"( {} )"_json.patch(
                      R"( [{"op": "add", "path": "/foo", "value": "bar"}] )"_json
                  ) == R"( {"foo": "bar"} )"_json);

            CHECK(R"( {"foo": [1, 3]} )"_json.patch(
                      R"( [{"op": "add", "path": "/foo", "value": "bar"}] )"_json
                  ) == R"( {"foo": "bar"} )"_json);

            CHECK(R"( {"foo": [{}]} )"_json.patch(
                      R"( [{"op": "add", "path": "/foo/0/bar", "value": "baz"}] )"_json
                  ) == R"( {"foo": [{"bar": "baz"}]} )"_json);
        }

        SECTION("remove")
        {
            CHECK(R"( {"foo": "bar"} )"_json.patch(
                      R"( [{"op": "remove", "path": "/foo"}] )"_json
                  ) == R"( {} )"_json);

            CHECK(R"( {"foo": [1, 2, 3]} )"_json.patch(
                      R"( [{"op": "remove", "path": "/foo/1"}] )"_json
                  ) == R"( {"foo": [1, 3]} )"_json);

            CHECK(R"( {"foo": [{"bar": "baz"}]} )"_json.patch(
                      R"( [{"op": "remove", "path": "/foo/0/bar"}] )"_json
                  ) == R"( {"foo": [{}]} )"_json);
        }

        SECTION("replace")
        {
            CHECK(R"( {"foo": "bar"} )"_json.patch(
                      R"( [{"op": "replace", "path": "/foo", "value": 1}] )"_json
                  ) == R"( {"foo": 1} )"_json);

            CHECK(R"( {"foo": [1, 2, 3]} )"_json.patch(
                      R"( [{"op": "replace", "path": "/foo/1", "value": 4}] )"_json
                  ) == R"( {"foo": [1, 4, 3]} )"_json);

            CHECK(R"( {"foo": [{"bar": "baz"}]} )"_json.patch(
                      R"( [{"op": "replace", "path": "/foo/0/bar", "value": 1}] )"_json
                  ) == R"( {"foo": [{"bar": 1}]} )"_json);
        }

        SECTION("move")
        {
            CHECK(R"( {"foo": [1, 2, 3]} )"_json.patch(
                      R"( [{"op": "move", "from": "/foo", "path": "/bar"}] )"_json
                  ) == R"( {"bar": [1, 2, 3]} )"_json);
        }

        SECTION("copy")
        {
            CHECK(R"( {"foo": [1, 2, 3]} )"_json.patch(
                      R"( [{"op": "copy", "from": "/foo/1", "path": "/bar"}] )"_json
                  ) == R"( {"foo": [1, 2, 3], "bar": 2} )"_json);
        }

        SECTION("copy")
        {
            CHECK_NOTHROW(R"( {"foo": "bar"} )"_json.patch(
                              R"( [{"op": "test", "path": "/foo", "value": "bar"}] )"_json));
        }
    }

    SECTION("Tests from github.com/json-patch/json-patch-tests")
    {
        for (const auto* filename :
                {
                    TEST_DATA_DIRECTORY "/json-patch-tests/spec_tests.json",
                    TEST_DATA_DIRECTORY "/json-patch-tests/tests.json"
                })
        {
            CAPTURE(filename)
            std::ifstream f(filename);
            json const suite = json::parse(f);

            for (const auto& test : suite)
            {
                INFO_WITH_TEMP(test.value("comment", ""));

                // skip tests marked as disabled
                if (test.value("disabled", false))
                {
                    continue;
                }

                const auto& doc = test["doc"];
                const auto& patch = test["patch"];

                if (test.count("error") == 0) // NOLINT(readability-container-contains)
                {
                    // if an expected value is given, use it; use doc otherwise
                    const auto& expected = test.value("expected", doc);
                    CHECK(doc.patch(patch) == expected);
                }
                else
                {
                    CHECK_THROWS(doc.patch(patch));
                }
            }
        }
    }
}

TEST_CASE("JSON patch - add to a primitive parent (regression #4292)")
{
    // Regression test for https://github.com/nlohmann/json/issues/4292
    //
    // An "add" operation whose parent location resolves to a primitive
    // (non-container) value must be rejected with a catchable exception.
    // Previously this hit JSON_ASSERT(false) in operation_add, which aborts
    // the process in debug builds and silently dropped the operation (leaving
    // a wrong result) when assertions were compiled out (NDEBUG). It now
    // throws out_of_range.411.
    //
    // The documents below are constructed programmatically (not parsed) so
    // they carry no byte positions; the JSON_DIAGNOSTICS path prefix is
    // handled by the guards. The exact message with positions is covered in
    // unit-diagnostic-positions.cpp.

    SECTION("string parent")
    {
        json const doc = {{"foo", {{"bar", "a string"}}}};
        json const patch = {{{"op", "add"}, {"path", "/foo/bar/baz"}, {"value", 1}}};
#if JSON_DIAGNOSTICS
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.411] (/foo/bar) cannot add value: the JSON Patch 'add' target's parent is of type string, but must be an object or array", json::out_of_range&);
#else
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.411] cannot add value: the JSON Patch 'add' target's parent is of type string, but must be an object or array", json::out_of_range&);
#endif
    }

    SECTION("null parent")
    {
        json const doc = {{"foo", nullptr}};
        json const patch = {{{"op", "add"}, {"path", "/foo/bar"}, {"value", 1}}};
#if JSON_DIAGNOSTICS
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.411] (/foo) cannot add value: the JSON Patch 'add' target's parent is of type null, but must be an object or array", json::out_of_range&);
#else
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.411] cannot add value: the JSON Patch 'add' target's parent is of type null, but must be an object or array", json::out_of_range&);
#endif
    }

    SECTION("null document")
    {
        json const doc = nullptr;
        json const patch = {{{"op", "add"}, {"path", "/-"}, {"value", 1}}};
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.411] cannot add value: the JSON Patch 'add' target's parent is of type null, but must be an object or array", json::out_of_range&);
    }

    SECTION("number parent")
    {
        json const doc = {{"foo", 1}};
        json const patch = {{{"op", "add"}, {"path", "/foo/bar"}, {"value", 2}}};
#if JSON_DIAGNOSTICS
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.411] (/foo) cannot add value: the JSON Patch 'add' target's parent is of type number, but must be an object or array", json::out_of_range&);
#else
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.411] cannot add value: the JSON Patch 'add' target's parent is of type number, but must be an object or array", json::out_of_range&);
#endif
    }

    SECTION("original two-step sequence from the issue")
    {
        // The user's two-step patch from #4292: first turn /xyz/1 into a
        // string, then try to add a member inside that string.
        json const doc = R"( { "xyz": [ { "lmn": "214", "nnp": "001" } ] } )"_json;
        json const patch = R"(
            [
                { "op": "add", "path": "/xyz/1",     "value": "" },
                { "op": "add", "path": "/xyz/1/lmn", "value": "214" }
            ]
        )"_json;

        CHECK_THROWS_AS(doc.patch(patch), json::out_of_range&);
    }
}

TEST_CASE("JSON patch - remove with primitive or null parent (regression #5396)")
{
    // Regression test for https://github.com/nlohmann/json/issues/5396
    //
    // RFC 6902 (§4.2) requires the target location of a "remove" operation
    // to exist. When the target's parent resolves to a primitive value or
    // null, the operation must fail. Previously operation_remove silently
    // did nothing in this case (neither the "is_object" nor the "is_array"
    // branch matched, and there was no final "else"), so the patch appeared
    // to succeed without changing the document. It now throws
    // out_of_range.413.

    SECTION("parent is a primitive (number)")
    {
        json const doc = {{"a", 1}};
        json const patch = {{{"op", "remove"}, {"path", "/a/b"}}};
#if JSON_DIAGNOSTICS
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.413] (/a) cannot remove value: the JSON Patch 'remove' target's parent is of type number, but must be an object or array", json::out_of_range&);
#else
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.413] cannot remove value: the JSON Patch 'remove' target's parent is of type number, but must be an object or array", json::out_of_range&);
#endif
    }

    SECTION("parent is a primitive (string)")
    {
        json const doc = {{"foo", {{"bar", "a string"}}}};
        json const patch = {{{"op", "remove"}, {"path", "/foo/bar/baz"}}};
#if JSON_DIAGNOSTICS
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.413] (/foo/bar) cannot remove value: the JSON Patch 'remove' target's parent is of type string, but must be an object or array", json::out_of_range&);
#else
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.413] cannot remove value: the JSON Patch 'remove' target's parent is of type string, but must be an object or array", json::out_of_range&);
#endif
    }

    SECTION("top-level document is null")
    {
        json const doc = nullptr;
        json const patch = {{{"op", "remove"}, {"path", "/a"}}};
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.413] cannot remove value: the JSON Patch 'remove' target's parent is of type null, but must be an object or array", json::out_of_range&);
    }

    SECTION("legitimate removes still work")
    {
        // object member
        json const doc1 = {{"a", 1}, {"b", 2}};
        json const patch1 = {{{"op", "remove"}, {"path", "/a"}}};
        CHECK(doc1.patch(patch1) == json({{"b", 2}}));

        // array element
        json const doc2 = R"([1, 2, 3])"_json;
        json const patch2 = {{{"op", "remove"}, {"path", "/1"}}};
        CHECK(doc2.patch(patch2) == R"([1, 3])"_json);
    }
}

TEST_CASE("JSON patch - move where 'from' is a proper prefix of 'path' (regression #5397)")
{
    // Regression test for https://github.com/nlohmann/json/issues/5397
    //
    // RFC 6902 (§4.4) forbids "from" from being a proper prefix of "path"
    // for a "move" operation: "a location cannot be moved into one of its
    // children." "move" is implemented as remove-then-add; for an object
    // target this happened to throw anyway as a side effect of the "add"
    // step re-resolving through the now-removed parent, but for an array
    // target the removal shifted subsequent indices, so "path" silently
    // re-resolved to a different element and the operation "succeeded"
    // with a corrupted result. It now throws out_of_range.414 for both
    // object and array targets.

    SECTION("array target (from the issue)")
    {
        json const doc = R"([[1,2],[3]])"_json;
        json const patch = {{{"op", "move"}, {"from", "/0"}, {"path", "/0/0"}}};
#if JSON_DIAGNOSTIC_POSITIONS
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.414] (bytes 0-11) cannot move value: 'from' path '/0' is a proper prefix of 'path' '/0/0'", json::out_of_range&);
#else
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.414] cannot move value: 'from' path '/0' is a proper prefix of 'path' '/0/0'", json::out_of_range&);
#endif
    }

    SECTION("object target")
    {
        json const doc = R"({"a": {"b": 1}})"_json;
        json const patch = {{{"op", "move"}, {"from", "/a"}, {"path", "/a/b"}}};
#if JSON_DIAGNOSTIC_POSITIONS
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.414] (bytes 0-15) cannot move value: 'from' path '/a' is a proper prefix of 'path' '/a/b'", json::out_of_range&);
#else
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.414] cannot move value: 'from' path '/a' is a proper prefix of 'path' '/a/b'", json::out_of_range&);
#endif
    }

    SECTION("from == path is not a proper prefix and must not be rejected")
    {
        // "from" equal to "path" is a no-op move; it is not a *proper*
        // prefix relationship, so this new check must not reject it.
        json const doc = R"({"a": 1, "b": 2})"_json;
        json const patch = {{{"op", "move"}, {"from", "/a"}, {"path", "/a"}}};
        CHECK(doc.patch(patch) == doc);
    }

    SECTION("raw string prefix that is not a pointer-token prefix must be allowed")
    {
        // "/ab" is a string-prefix of "/abc/x" as raw text, but "ab" and
        // "abc" are different reference tokens, so this is NOT a
        // pointer-token prefix relationship and the move must succeed.
        // This is the key case proving the check compares tokens, not
        // raw pointer text (a naive std::string prefix/rfind check on
        // the undecoded pointer would wrongly reject this).
        json const doc = R"({"ab": 1, "abc": {"x": 2}})"_json;
        json const patch = {{{"op", "move"}, {"from", "/ab"}, {"path", "/abc/x"}}};
        json const result = R"({"abc": {"x": 1}})"_json;
        CHECK(doc.patch(patch) == result);
    }

    SECTION("escaped reference tokens are compared unescaped")
    {
        // "from" is the single token "a/b" (escaped as "a~1b"); "path"
        // addresses member "x" of that same value, so "from" is a
        // proper (token-level) prefix of "path" and must be rejected.
        json const doc = R"({"a/b": {"x": 1}})"_json;
        json const patch = {{{"op", "move"}, {"from", "/a~1b"}, {"path", "/a~1b/x"}}};
#if JSON_DIAGNOSTIC_POSITIONS
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.414] (bytes 0-17) cannot move value: 'from' path '/a~1b' is a proper prefix of 'path' '/a~1b/x'", json::out_of_range&);
#else
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.414] cannot move value: 'from' path '/a~1b' is a proper prefix of 'path' '/a~1b/x'", json::out_of_range&);
#endif
    }

    SECTION("ordinary valid moves still work")
    {
        // unrelated top-level members
        json const doc1 = R"({"a": 1, "b": 2})"_json;
        json const patch1 = {{{"op", "move"}, {"from", "/a"}, {"path", "/c"}}};
        CHECK(doc1.patch(patch1) == R"({"b": 2, "c": 1})"_json);

        // sibling paths that share a textual prefix but are unrelated
        json const doc2 = R"({"a": {"x": 1}, "b": {"y": 2}})"_json;
        json const patch2 = {{{"op", "move"}, {"from", "/a/x"}, {"path", "/b/z"}}};
        CHECK(doc2.patch(patch2) == R"({"a": {}, "b": {"y": 2, "z": 1}})"_json);

        // "path" is a proper prefix of "from" (the reverse relationship,
        // which RFC 6902 does not forbid)
        json const doc3 = R"({"a": {"b": 1}})"_json;
        json const patch3 = {{{"op", "move"}, {"from", "/a/b"}, {"path", "/a"}}};
        CHECK(doc3.patch(patch3) == R"({"a": 1})"_json);
    }

    SECTION("root 'from' is a proper prefix of every non-root 'path'")
    {
        // the whole document is a proper prefix of any location inside it
        json const doc = R"({"a": 1})"_json;
        json const patch = {{{"op", "move"}, {"from", ""}, {"path", "/a"}}};
#if JSON_DIAGNOSTIC_POSITIONS
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.414] (bytes 0-8) cannot move value: 'from' path '' is a proper prefix of 'path' '/a'", json::out_of_range&);
#else
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.414] cannot move value: 'from' path '' is a proper prefix of 'path' '/a'", json::out_of_range&);
#endif
    }

    SECTION("root 'path' is never a proper prefix violation for a non-root 'from'")
    {
        // the reverse of the above: moving a non-root location to the root
        // is the "path is a prefix of from" relationship, which RFC 6902
        // permits (already covered generally above; this pins the root
        // case specifically, since root is the one path with no reference
        // tokens at all)
        json const doc = R"({"a": {"b": 1}})"_json;
        json const patch = {{{"op", "move"}, {"from", "/a"}, {"path", ""}}};
        CHECK(doc.patch(patch) == R"({"b": 1})"_json);
    }

    SECTION("array index tokens that are not a number")
    {
        json const doc = R"({"a": [1, 2]})"_json;

        // "-" cannot be removed and is reported as unresolved
        json const patch_dash = {{{"op", "remove"}, {"path", "/a/-"}}};
        CHECK_THROWS_WITH_AS(doc.patch(patch_dash), "[json.exception.out_of_range.404] unresolved reference token '-'", json::out_of_range&);

        // a single character is reported like a longer token
        json const patch_x = {{{"op", "remove"}, {"path", "/a/x"}}};
        CHECK_THROWS_WITH_AS(doc.patch(patch_x), "[json.exception.parse_error.109] parse error: array index 'x' is not a number", json::parse_error&);
        json const patch_xy = {{{"op", "remove"}, {"path", "/a/xy"}}};
        CHECK_THROWS_WITH_AS(doc.patch(patch_xy), "[json.exception.parse_error.109] parse error: array index 'xy' is not a number", json::parse_error&);
    }

    SECTION("the array-append token '-' is an ordinary child token")
    {
        // "-" (append-to-array) addresses a location *inside* the array,
        // so "from" pointing at the array is still a proper prefix of
        // "path" ending in "-" and must be rejected like any other child.
        json const doc = R"({"a": [1, 2]})"_json;
        json const patch = {{{"op", "move"}, {"from", "/a"}, {"path", "/a/-"}}};
#if JSON_DIAGNOSTIC_POSITIONS
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.414] (bytes 0-13) cannot move value: 'from' path '/a' is a proper prefix of 'path' '/a/-'", json::out_of_range&);
#else
        CHECK_THROWS_WITH_AS(doc.patch(patch), "[json.exception.out_of_range.414] cannot move value: 'from' path '/a' is a proper prefix of 'path' '/a/-'", json::out_of_range&);
#endif
    }
}

TEST_CASE("JSON patch - diff emits array removals in descending index order")
{
    SECTION("array shrunk to empty")
    {
        json const source = {0, 1, 2, 3, 4};
        json const target = json::array();

        json const patch = json::diff(source, target);

        json const expected = R"(
            [
                {"op": "remove", "path": "/4"},
                {"op": "remove", "path": "/3"},
                {"op": "remove", "path": "/2"},
                {"op": "remove", "path": "/1"},
                {"op": "remove", "path": "/0"}
            ]
        )"_json;

        CHECK(patch == expected);
        CHECK(source.patch(patch) == target);
    }

    SECTION("array partially shrunk, after a replacement at a common index")
    {
        json const source = {0, 1, 2, 3, 4};
        json const target = {0, 9};

        json const patch = json::diff(source, target);

        // the replacement comes first, then the removals, highest index first
        json const expected = R"(
            [
                {"op": "replace", "path": "/1", "value": 9},
                {"op": "remove", "path": "/4"},
                {"op": "remove", "path": "/3"},
                {"op": "remove", "path": "/2"}
            ]
        )"_json;

        CHECK(patch == expected);
        CHECK(source.patch(patch) == target);
    }

    SECTION("nested array shrunk")
    {
        json const source = {{"a", {0, 1, 2}}};
        json const target = {{"a", json::array()}};

        json const patch = json::diff(source, target);

        json const expected = R"(
            [
                {"op": "remove", "path": "/a/2"},
                {"op": "remove", "path": "/a/1"},
                {"op": "remove", "path": "/a/0"}
            ]
        )"_json;

        CHECK(patch == expected);
        CHECK(source.patch(patch) == target);
    }

    SECTION("many removals still round-trip")
    {
        json source = json::array();
        for (int i = 0; i < 1000; ++i)
        {
            source.push_back(i);
        }
        json const target = json::array();

        json const patch = json::diff(source, target);

        CHECK(patch.size() == 1000);
        CHECK(patch.front().at("path") == "/999");
        CHECK(patch.back().at("path") == "/0");
        CHECK(source.patch(patch) == target);
    }
}

TEST_CASE("JSON patch: diff of deeply nested values")
{
    SECTION("the diff reproduces the target at every depth")
    {
        // depths on either side of the nesting depth up to which diff()
        // recurses (detail::recursion_depth_limit(), 128 by default); not every depth up
        // to 300, as the test would then time out under Valgrind
        std::vector<std::size_t> depths;
        for (std::size_t depth = 0; depth <= 16; ++depth)
        {
            depths.push_back(depth);
        }
        const std::size_t limit = nlohmann::detail::recursion_depth_limit();
        for (std::size_t depth = limit > 8 ? limit - 8 : 0; depth <= limit + 8; ++depth)
        {
            depths.push_back(depth);
        }
        depths.push_back(300);

        for (const auto depth : depths)
        {
            CAPTURE(depth)
            for (int from = 0; from < 3; ++from)
            {
                for (int to = 0; to < 3; ++to)
                {
                    CAPTURE(from)
                    CAPTURE(to)
                    const auto source = nested<json>(depth, from);
                    const auto target = nested<json>(depth, to);
                    const auto patch = json::diff(source, target);
                    CHECK(source.patch(patch) == target);
                    CHECK(patch.empty() == (from == to));

                    const auto ordered_source = nested<nlohmann::ordered_json>(depth, from);
                    const auto ordered_target = nested<nlohmann::ordered_json>(depth, to);
                    CHECK(ordered_source.patch(nlohmann::ordered_json::diff(ordered_source, ordered_target)) == ordered_target);
                }
            }
        }
    }

    SECTION("a difference only in the innermost value is one replace operation")
    {
        for (std::size_t depth = 0; depth <= 300; ++depth)
        {
            CAPTURE(depth)
            json source = 1;
            json target = 2;
            for (std::size_t i = 0; i < depth; ++i)
            {
                source = i % 2 == 0 ? json::object({{"a", std::move(source)}}) : json::array({std::move(source)});
                target = i % 2 == 0 ? json::object({{"a", std::move(target)}}) : json::array({std::move(target)});
            }
            CHECK(json::diff(source, target, "/root") == json::array({{{"op", "replace"}, {"path", "/root" + nested_path(depth)}, {"value", 2}}}));
        }
    }

    SECTION("values nested too deeply for the call stack (#5393)")
    {
        // diff() used to recurse once per nesting level, and compared the
        // values with operator== on every level. The values are only
        // parsed and diffed, never copied or compared, since those recurse
        // too.
        const std::size_t depth = 100000;
        for (const bool objects :
                {
                    false, true
                })
        {
            CAPTURE(objects)
            std::string source_text;
            std::string target_text;
            std::string equal_text;
            std::string path;
            for (std::size_t i = 0; i < depth; ++i)
            {
                source_text += objects ? "{\"a\":" : "[";
                path += objects ? "/a" : "/0";
            }
            target_text = source_text + "2";
            equal_text = source_text + "1";
            source_text += "1";
            const std::string closing(depth, objects ? '}' : ']');
            const auto source = json::parse(source_text + closing);

            const auto patch = json::diff(source, json::parse(target_text + closing));
            REQUIRE(patch.size() == 1);
            CHECK(patch[0]["op"] == "replace");
            CHECK(patch[0]["path"] == path);
            CHECK(patch[0]["value"] == 2);

            CHECK(json::diff(source, json::parse(equal_text + closing)).empty());
        }
    }
}

TEST_CASE("JSON patch - diff() takes the fast path for non-reorderable object types (regression #5639)")
{
    // #5465 added an order check to diff()'s object handling so a
    // member-by-member diff is only used when it would also reproduce
    // target's member *order* -- needed for ordered_json, whose object_t
    // keeps insertion order and whose patch() "add" op appends a new
    // member at the end. For json's default object_t (std::map, which
    // orders members by key regardless of insertion history), that check
    // could still fail: a new key that sorts before an existing common key
    // makes target's iteration interleave the new key between common keys,
    // even though nothing else about the object changed. That sent the
    // whole object through the slow (remove-every-member,
    // re-add-every-member) path instead of the minimal one.
    SECTION("json: added key sorts before an existing common key")
    {
        const json source = {{"a", 1}, {"c", {{"x", 1}, {"y", 2}}}};
        const json target = {{"a", 1}, {"b", 0}, {"c", {{"x", 1}, {"y", 2}}}};

        const json patch = json::diff(source, target);

        // only the new key is added; "a" and "c" are left alone instead of
        // being removed and re-added
        const json expected = R"([{"op": "add", "path": "/b", "value": 0}])"_json;
        CHECK(patch == expected);
        CHECK(source.patch(patch) == target);
    }

    SECTION("ordered_json: reordering behavior from #5465 is unchanged")
    {
        using nlohmann::ordered_json;

        // same key/value shape as the json case above, but for ordered_json
        // the *target*'s member order must be reproduced, so the slow path
        // is still required here.
        ordered_json source;
        source["a"] = 1;
        source["c"] = ordered_json{{"x", 1}, {"y", 2}};

        ordered_json target;
        target["a"] = 1;
        target["b"] = 0;
        target["c"] = ordered_json{{"x", 1}, {"y", 2}};

        const ordered_json patch = ordered_json::diff(source, target);

        // unlike the json case: every member is still removed and re-added
        // so the result ends up in target's order (2 removes + 3 adds)
        CHECK(patch.size() == 5);
        CHECK(source.patch(patch) == target);
    }
}

TEST_CASE("JSON patch - every operation on ordered_json")
{
    using nlohmann::ordered_json;

    const ordered_json doc = {{"foo", "bar"}, {"arr", {1, 2, 3}}, {"obj", {{"a", 1}}}};

    SECTION("successful operations")
    {
        const ordered_json patch = ordered_json::parse(R"([
            {"op": "add", "path": "/obj/b", "value": 2},
            {"op": "add", "path": "/arr/1", "value": 9},
            {"op": "add", "path": "/arr/-", "value": 4},
            {"op": "remove", "path": "/arr/0"},
            {"op": "remove", "path": "/obj/a"},
            {"op": "replace", "path": "/foo", "value": "baz"},
            {"op": "move", "from": "/foo", "path": "/moved"},
            {"op": "copy", "from": "/obj", "path": "/copied"},
            {"op": "test", "path": "/copied/b", "value": 2}
        ])");

        const ordered_json expected = ordered_json::parse(R"({
            "arr": [9, 2, 3, 4], "obj": {"b": 2}, "moved": "baz", "copied": {"b": 2}
        })");

        CHECK(doc.patch(patch) == expected);

        // adding to the root replaces the document
        CHECK(doc.patch(ordered_json::parse(R"([{"op": "add", "path": "", "value": [1]}])")) == ordered_json({1}));
    }

    SECTION("failing operations")
    {
        ordered_json _;
#if JSON_DIAGNOSTICS
        CHECK_THROWS_WITH_AS(_ = doc.patch(ordered_json::parse(R"([{"op": "add", "path": "/arr/4", "value": 1}])")),
                             "[json.exception.out_of_range.401] (/arr) array index 4 is out of range", ordered_json::out_of_range&);
#else
        CHECK_THROWS_WITH_AS(_ = doc.patch(ordered_json::parse(R"([{"op": "add", "path": "/arr/4", "value": 1}])")),
                             "[json.exception.out_of_range.401] array index 4 is out of range", ordered_json::out_of_range&);
#endif
        CHECK_THROWS_WITH_AS(_ = doc.patch(ordered_json::parse(R"([{"op": "add", "path": "/nope/x", "value": 1}])")),
                             "[json.exception.out_of_range.403] key 'nope' not found", ordered_json::out_of_range&);
        CHECK_THROWS_WITH_AS(_ = doc.patch(ordered_json::parse(R"([{"op": "remove", "path": "/obj/nope"}])")),
                             "[json.exception.out_of_range.403] key 'nope' not found", ordered_json::out_of_range&);
#if JSON_DIAGNOSTICS
        CHECK_THROWS_WITH_AS(_ = doc.patch(ordered_json::parse(R"([{"op": "remove", "path": "/arr/3"}])")),
                             "[json.exception.out_of_range.401] (/arr) array index 3 is out of range", ordered_json::out_of_range&);
#else
        CHECK_THROWS_WITH_AS(_ = doc.patch(ordered_json::parse(R"([{"op": "remove", "path": "/arr/3"}])")),
                             "[json.exception.out_of_range.401] array index 3 is out of range", ordered_json::out_of_range&);
#endif
#if JSON_DIAGNOSTICS
        CHECK_THROWS_WITH_AS(_ = doc.patch(ordered_json::parse(R"([{"op": "test", "path": "/foo", "value": "qux"}])")),
                             "[json.exception.other_error.501] (/0) unsuccessful: {\"op\":\"test\",\"path\":\"/foo\",\"value\":\"qux\"}", ordered_json::other_error&);
#elif JSON_DIAGNOSTIC_POSITIONS
        CHECK_THROWS_WITH_AS(_ = doc.patch(ordered_json::parse(R"([{"op": "test", "path": "/foo", "value": "qux"}])")),
                             "[json.exception.other_error.501] (bytes 1-47) unsuccessful: {\"op\":\"test\",\"path\":\"/foo\",\"value\":\"qux\"}", ordered_json::other_error&);
#else
        CHECK_THROWS_WITH_AS(_ = doc.patch(ordered_json::parse(R"([{"op": "test", "path": "/foo", "value": "qux"}])")),
                             "[json.exception.other_error.501] unsuccessful: {\"op\":\"test\",\"path\":\"/foo\",\"value\":\"qux\"}", ordered_json::other_error&);
#endif
#if JSON_DIAGNOSTICS
        CHECK_THROWS_WITH_AS(_ = doc.patch(ordered_json::parse(R"([{"op": "add", "path": "/foo"}])")),
                             "[json.exception.parse_error.105] parse error: (/0) operation 'add' must have member 'value'", ordered_json::parse_error&);
#elif JSON_DIAGNOSTIC_POSITIONS
        CHECK_THROWS_WITH_AS(_ = doc.patch(ordered_json::parse(R"([{"op": "add", "path": "/foo"}])")),
                             "[json.exception.parse_error.105] parse error: (bytes 1-30) operation 'add' must have member 'value'", ordered_json::parse_error&);
#else
        CHECK_THROWS_WITH_AS(_ = doc.patch(ordered_json::parse(R"([{"op": "add", "path": "/foo"}])")),
                             "[json.exception.parse_error.105] parse error: operation 'add' must have member 'value'", ordered_json::parse_error&);
#endif
        CHECK_THROWS_WITH_AS(_ = doc.patch(ordered_json::parse(R"([{"op": "move", "from": "/obj", "path": "/obj/a/b"}])")),
                             "[json.exception.out_of_range.414] cannot move value: 'from' path '/obj' is a proper prefix of 'path' '/obj/a/b'", ordered_json::out_of_range&);
    }

    SECTION("diff reproduces the target")
    {
        const ordered_json source = {{"a", 1}, {"b", 2}, {"c", {{"x", 1}}}, {"l", {1, 2, 3}}};
        const std::vector<ordered_json> targets =
        {
            // a key removed, a key added, a nested change, a shorter array
            {{"a", 1}, {"c", {{"x", 2}}}, {"l", {1}}, {"d", 4}},
            // the same keys in another order
            {{"c", {{"x", 1}}}, {"a", 1}, {"b", 2}, {"l", {1, 2, 3}}},
            // new keys ahead of the common ones
            {{"new", true}, {"a", 1}, {"b", 3}, {"c", {{"x", 1}}}, {"l", {1, 2, 3}}},
        };
        for (const auto& target : targets)
        {
            CAPTURE(target.dump())
            CHECK(source.patch(ordered_json::diff(source, target)) == target);
        }
    }
}

TEST_CASE_TEMPLATE("JSON patch - diff round trip on hand-made documents", Json, nlohmann::json, nlohmann::ordered_json)
{
    const auto roundtrip = [](const Json & a, const Json & b)
    {
        CAPTURE(a.dump())
        CAPTURE(b.dump())
        const Json p = Json::diff(a, b);
        CHECK(a.patch(p) == b);
        CHECK(Json::diff(b, b).empty());
    };

    SECTION("reordered keys")
    {
        const Json a = Json::parse(R"({"x":1,"y":2,"z":{"p":1,"q":2}})");
        const Json b = Json::parse(R"({"z":{"q":2,"p":1},"y":2,"x":1})");
        roundtrip(a, b);
        roundtrip(b, a);
    }

    SECTION("nested add, remove and replace")
    {
        const Json a = Json::parse(R"({"a":[1,2,{"k":"v","gone":true}],"b":{"c":{"d":1}},"e":"s"})");
        const Json b = Json::parse(R"({"a":[1,3,{"k":"w","new":[]}],"b":{"c":{"d":[1,2]}},"f":null})");
        roundtrip(a, b);
        roundtrip(b, a);
    }

    SECTION("arrays of different length and type changes")
    {
        roundtrip(Json::parse("[1,2,3,4,5]"), Json::parse("[1,3]"));
        roundtrip(Json::parse("[1]"), Json::parse("[1,[2],{\"a\":3}]"));
        roundtrip(Json::parse("[]"), Json::parse("{}"));
        roundtrip(Json::parse("{\"a\":[]}"), Json::parse("{\"a\":{}}"));
        roundtrip(Json(1), Json::parse("[1]"));
    }
}

TEST_CASE("JSON patch - behavior documented in the API reference")
{
    SECTION("duplicate member names in an operation")
    {
        // RFC 6902, A.13: the parser resolves the duplicates (the last one
        // is kept), so this is a "remove" and not an "add"
        const json patch = json::parse(R"([{"op": "add", "op": "remove", "path": "/a"}])");
        CHECK(patch == json::parse(R"([{"op": "remove", "path": "/a"}])"));
        CHECK(json({{"a", 1}, {"b", 2}}).patch(patch) == json({{"b", 2}}));
    }

    SECTION("add with a leading zero in an array index")
    {
        const json patch = R"([{"op": "add", "path": "/01", "value": 1}])"_json;
        json doc = json::array();
#if !defined(JSON_NOEXCEPTION)
        CHECK_THROWS_AS(doc.patch(patch), json::parse_error&);
        CHECK_THROWS_AS(doc.patch_inplace(patch), json::parse_error&);
#endif
        CHECK(doc == json::array());
    }

    SECTION("test compares numbers by value")
    {
        const json doc = R"({"a": 1, "b": 0, "c": 1.5})"_json;
        CHECK(doc.patch(R"([{"op": "test", "path": "/a", "value": 1.0}])"_json) == doc);
        CHECK(doc.patch(R"([{"op": "test", "path": "/b", "value": -0.0}])"_json) == doc);
        CHECK(doc.patch(R"([{"op": "test", "path": "/c", "value": 1.5}])"_json) == doc);
        CHECK_THROWS_AS(doc.patch(R"([{"op": "test", "path": "/a", "value": 2}])"_json), json::other_error&);
        CHECK_THROWS_AS(doc.patch(R"([{"op": "test", "path": "/a", "value": "1"}])"_json), json::other_error&);
    }

    SECTION("test ignores the order of object members, but not the order of array elements")
    {
        const json doc = R"({"o": {"x": 1, "y": 2}, "a": [1, 2]})"_json;
        CHECK(doc.patch(R"([{"op": "test", "path": "/o", "value": {"y": 2, "x": 1}}])"_json) == doc);
        CHECK(doc.patch(R"([{"op": "test", "path": "/a", "value": [1, 2]}])"_json) == doc);
        CHECK_THROWS_AS(doc.patch(R"([{"op": "test", "path": "/a", "value": [2, 1]}])"_json), json::other_error&);
    }

    SECTION("test on a path that does not exist")
    {
        const json doc = R"({"a": 1})"_json;
        // with a "value" member, the failed lookup is a failed test
        CHECK_THROWS_AS(doc.patch(R"([{"op": "test", "path": "/b", "value": 1}])"_json), json::other_error&);
        CHECK_THROWS_AS(doc.patch(R"([{"op": "test", "path": "/b", "value": null}])"_json), json::other_error&);
        // without it, an exception is thrown, too; which one depends on the
        // order of evaluation of the operands of ==, so it is not checked
        CHECK_THROWS(doc.patch(R"([{"op": "test", "path": "/b"}])"_json));
    }

    SECTION("patch() has the strong guarantee")
    {
        // independent values, so that the comparison below checks the untouched document
        const auto make_doc = []
        {
            return R"({"a": [1, 2], "o": {"k": "v"}})"_json;
        };
        const json doc = make_doc();
        const json before = make_doc();

        const std::vector<json> failing =
        {
            // remove of a member that does not exist
            R"([{"op": "add", "path": "/n", "value": 1}, {"op": "remove", "path": "/missing"}])"_json,
            // replace of a member that does not exist
            R"([{"op": "remove", "path": "/a/0"}, {"op": "replace", "path": "/missing", "value": 1}])"_json,
            // move from a member that does not exist
            R"([{"op": "add", "path": "/n", "value": 1}, {"op": "move", "from": "/missing", "path": "/m"}])"_json,
            // copy from a member that does not exist
            R"([{"op": "add", "path": "/n", "value": 1}, {"op": "copy", "from": "/missing", "path": "/m"}])"_json,
            // out-of-range array index
            R"([{"op": "add", "path": "/n", "value": 1}, {"op": "add", "path": "/a/5", "value": 1}])"_json,
            // failing test after a successful operation
            R"([{"op": "remove", "path": "/o"}, {"op": "test", "path": "/a", "value": []}])"_json,
        };
        for (const auto& patch : failing)
        {
            CAPTURE(patch.dump())
            CHECK_THROWS_AS(doc.patch(patch), json::exception&);
            CHECK(doc == before);

            json copy = make_doc();
            CHECK_THROWS_AS(copy.patch(patch), json::exception&);
            CHECK(copy == before);
        }
    }
}

TEST_CASE("JSON patch - diff behavior documented in the API reference")
{
    SECTION("path is a verbatim prefix")
    {
        // not escaped and not validated
        CHECK(json::diff(1, 2) == R"([{"op": "replace", "path": "", "value": 2}])"_json);
        CHECK(json::diff(1, 2, "abc") == R"([{"op": "replace", "path": "abc", "value": 2}])"_json);
        CHECK(json::diff(1, 2, "/root") == R"([{"op": "replace", "path": "/root", "value": 2}])"_json);
        // an escaped token in a non-root prefix is kept as given
        CHECK(json::diff(R"({"a": 1})"_json, R"({"a": 2})"_json, "/x~1y/~0")
              == R"([{"op": "replace", "path": "/x~1y/~0/a", "value": 2}])"_json);
        CHECK(json::diff(R"({"a": 1})"_json, R"({"a": 2})"_json, "/p")
              == R"([{"op": "replace", "path": "/p/a", "value": 2}])"_json);
    }

    SECTION("keys are escaped in the paths")
    {
        const json source = json::object();
        const json target =
        {
            {"", 0}, {"/", 1}, {"~", 2}, {"~1", 3}, {"~01", 4}
        };
        const json patch = json::diff(source, target);
        REQUIRE(patch.size() == 5);

        // the order of the operations is not checked
        json paths = json::object();
        for (const auto& op : patch)
        {
            CHECK(op["op"] == "add");
            paths[op["path"].get<std::string>()] = op["value"];
        }
        CHECK(paths == json({{"/", 0}, {"/~1", 1}, {"/~0", 2}, {"/~01", 3}, {"/~001", 4}}));
        CHECK(source.patch(patch) == target);
    }

    SECTION("NaN is not equal to itself")
    {
        const json nan = std::numeric_limits<json::number_float_t>::quiet_NaN();
        const json patch = json::diff(nan, nan);
        CHECK(patch.size() == 1);
        CHECK(patch[0]["op"] == "replace");
        CHECK(patch[0]["path"] == "");
        CHECK(patch[0]["value"].is_number_float());
        CHECK(nan.patch(patch) != nan);

        // a NaN in a patch is serialized as null
        CHECK(json::parse(patch.dump())[0]["value"].is_null());

        const json nested = {{"a", {1, nan}}};
        const json nested_patch = json::diff(nested, nested);
        CHECK(nested_patch.size() == 1);
        CHECK(nested_patch[0]["path"] == "/a/1");

        // infinity is equal to itself
        const json inf = std::numeric_limits<json::number_float_t>::infinity();
        CHECK(json::diff(inf, inf).empty());
    }

    SECTION("discarded values are not equal to themselves")
    {
        const json discarded(json::value_t::discarded);
        const json patch = json::diff(discarded, discarded);
        CHECK(patch.size() == 1);
        CHECK(patch[0]["op"] == "replace");
        CHECK(patch[0]["path"] == "");
        CHECK(patch[0]["value"].is_discarded());
        CHECK(discarded.patch(patch) != discarded);
    }

    SECTION("numbers that compare equal produce no operation")
    {
        CHECK(json::diff(json(1), json(1.0)).empty());
        CHECK(json::diff(json(1.0), json(1)).empty());
        CHECK(json::diff(json(1U), json(1)).empty());
        CHECK(json::diff(json(1), json(1U)).empty());
        CHECK(json::diff(json(0.0), json(-0.0)).empty());

        // the patched value keeps the number type of the source
        const json source = 1;
        const json patched = source.patch(json::diff(source, json(1.0)));
        CHECK(patched.is_number_integer());
        CHECK(patched == json(1.0));

        // different values are replaced
        CHECK(json::diff(json(1), json(2.0)) == R"([{"op": "replace", "path": "", "value": 2.0}])"_json);
        CHECK(json::diff(json(1), json(-1)) == R"([{"op": "replace", "path": "", "value": -1}])"_json);
        CHECK(json::diff(json(1.0), json(1.5)) == R"([{"op": "replace", "path": "", "value": 1.5}])"_json);
        CHECK(json::diff(json(1), json("1")) == R"([{"op": "replace", "path": "", "value": "1"}])"_json);
    }

    SECTION("binary values")
    {
        const json a = json::binary({1, 2});
        const json b = json::binary({1, 3});
        CHECK(json::diff(a, a).empty());

        const json patch = json::diff(a, b);
        CHECK(patch.size() == 1);
        CHECK(patch[0]["op"] == "replace");
        CHECK(patch[0]["path"] == "");
        CHECK(patch[0]["value"].is_binary());
        CHECK(a.patch(patch) == b);

        // serialized, the binary value is an object
        const json parsed = json::parse(patch.dump());
        CHECK(parsed[0]["value"].is_object());
        CHECK(parsed[0]["value"] == R"({"bytes": [1, 3], "subtype": null})"_json);
    }

    SECTION("a difference as a whole is a replace of the root")
    {
        CHECK(json::diff(json::array({1}), json::object()) == R"([{"op": "replace", "path": "", "value": {}}])"_json);
        CHECK(json::diff(json(nullptr), json::array()) == R"([{"op": "replace", "path": "", "value": []}])"_json);
    }
}

TEST_CASE("JSON patch - operations that are left to json_pointer")
{
    // the usual operations on a plain pointer are applied without building a
    // json_pointer; the following are not plain, and some are errors
    SECTION("a path without a slash")
    {
        const json j = {{"a", 1}};

        CHECK_THROWS_AS(j.patch(R"([{"op": "add", "path": "abc", "value": 1}])"_json), json::parse_error&);
        CHECK_THROWS_AS(j.patch(R"([{"op": "remove", "path": "abc"}])"_json), json::parse_error&);
    }

    SECTION("remove with an escaped reference token")
    {
        const json j = {{"a/b", 1}, {"c~d", 2}, {"e", 3}};

        CHECK(j.patch(R"([{"op": "remove", "path": "/a~1b"}])"_json) == json({{"c~d", 2}, {"e", 3}}));
        CHECK(j.patch(R"([{"op": "remove", "path": "/c~0d"}])"_json) == json({{"a/b", 1}, {"e", 3}}));
        CHECK_THROWS_AS(j.patch(R"([{"op": "remove", "path": "/missing~1key"}])"_json), json::out_of_range&);
    }

    SECTION("a path through a primitive value")
    {
        const json j = {{"a", 1}};

        CHECK_THROWS_AS(j.patch(R"([{"op": "test", "path": "/a/b", "value": 1}])"_json), json::other_error&);
        CHECK_THROWS_AS(j.patch(R"([{"op": "replace", "path": "/a/b", "value": 1}])"_json), json::out_of_range&);
    }
}

TEST_CASE("JSON patch - diff of objects with many members")
{
    // more members than diff() keeps without allocating
    for (const std::size_t members :
            {
                16u, 17u, 40u
            })
    {
        CAPTURE(members)

        json source = json::object();
        json target = json::object();
        for (std::size_t i = 0; i < members; ++i)
        {
            const std::string key = "key" + std::to_string(i);
            source[key] = i;
            // every third member differs
            target[key] = (i % 3 == 0) ? i + 1 : i;
        }
        // the same keys, a removed and an added one
        source["removed"] = true;
        target["added"] = false;

        const json patch = json::diff(source, target);
        CHECK(source.patch(patch) == target);
        CHECK(patch.size() == ((members + 2) / 3) + 2);

        const nlohmann::ordered_json ordered_source = source;
        const nlohmann::ordered_json ordered_target = target;
        CHECK(ordered_source.patch(nlohmann::ordered_json::diff(ordered_source, ordered_target)) == ordered_target);
    }
}

TEST_CASE("JSON patch - diff of leaf values below the bound of the recursive descent")
{
    // the values at the innermost level are diffed without recursion: equal
    // leaves yield nothing, leaves of different types and different leaves
    // are replaced
    const std::size_t depth = nlohmann::detail::recursion_depth_limit() + 72; // 200 by default

    json source = {1, "text", 3, {{"x", 1}, {"y", 2}}, true, nullptr};
    json target = {1, 2, 4, {{"x", 1}, {"y", 3}}, true, nullptr};
    for (std::size_t i = 0; i < depth; ++i)
    {
        source = json::array({std::move(source)});
        target = json::array({std::move(target)});
    }

    const json patch = json::diff(source, target);
    CHECK(patch.size() == 3);
    CHECK(source.patch(patch) == target);

    // the same with objects as the outer levels
    json object_source = {{"equal", 1}, {"type", "text"}, {"value", 3}};
    json object_target = {{"equal", 1}, {"type", 2}, {"value", 4}};
    for (std::size_t i = 0; i < depth; ++i)
    {
        object_source = json::object({{"a", std::move(object_source)}});
        object_target = json::object({{"a", std::move(object_target)}});
    }

    const json object_patch = json::diff(object_source, object_target);
    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
        const json inserted = 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}
        ])");
        CHECK(doc.patch(inserted) == json::parse(R"({"a": [{"b": [9]}, {"b": [1, 2, 3]}, {"b": [4, 5, 6]}], "c": {"d": {"e": 7}}})"));

        // an element removed from the front
        const json removed_front = 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}
        ])");
        CHECK(doc.patch(removed_front) == json::parse(R"({"a": [{"b": [4, 5, 60]}], "c": {"d": {"e": 7}}})"));

        // a value replaced above the path that was resolved before
        const json replaced_above = 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}
        ])");
        CHECK(doc.patch(replaced_above) == 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);
}