json::diff generates incorrect patch when removing multiple array elements.

[tmyersjstar]

Removing multiple elements from an array will generate a patch which is incorrect. Here is a unit test that will fail:

// Exists in TEST_CASE("JSON patch")
SECTION("remove multiple")
{
    json doc = R"(
        {
            "arr1": [1, 2, 3, 4]
        }
    )"_json;
    json expected = R"(
        {
            "arr1": [1, 2]
        }
    )"_json;

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

The patch that is generated is the following:

[
    {
        "op": "remove",
        "path": "/2"
    },
    {
        "op": "remove",
        "path": "/3"
    }
]

This fails obviously because first index 2 is removed, and then index 3 is attempted to be removed, but the size is only 2 at this point:

test/src/unit.cpp:13106: FAILED:
  CHECK( doc.patch(json::diff(doc, expected)) == expected )
due to unexpected exception with message:
  array index 3 is out of range

Sorry if this is already a known issue or not the right way to report this issue. I will try to take a look into creating a fix if I have time.

[nlohmann]

Thanks for reporting! My diff algorithm is flawed in this point - I start processing arrays from the beginning, and never realized that I may invalidate indices...

[tmyersjstar]

I think I potentially have a fix. I'll have to think about whether there is something naive with it. It works by essentially reversing the order of the removes so that indices aren't invalidated.

In json::diff, use the following code block in place of what was there (comment remains intact):

// remove my remaining elements
size_t old_i = i;
i = source.size() - 1;
while (i >= old_i)
{
    result.push_back(object(
    {
        {"op", "remove"},
        {"path", path + "/" + std::to_string(i)}
    }));
    --i;
}
i = source.size();

I haven't yet looked through contribution guidelines quite yet, but I will do so later and create a pull request potentially.

[nlohmann]

@tmyersjstar, thanks for your proposal. In fact, I came up with the very same idea: I created a branch feature/issue269 (see 15a314a and 3f97a5d). Please let me know whether this works for you.

[tmyersjstar]

Awesome! I am using that latest source in my project and it is working correctly now. The diff algorithm seems to be working correctly for at least the json objects I am generating.

Thanks for the fix and for creating this library!

[nlohmann]

You're welcome. I shall add a test case and merge the fix to the develop branch.

Just as a remark: The diff algorithm used is really primitive right now. I had a quick glance at what the Python package jsonpatch is doing... There is quite some optimization work to do form my side...