Invalid diff created when DiffFlags.OMIT_COPY_OPERATION is omitted

[floriangrundig]

Hi all,

first thank you for that awesome library :)

We've encountered a bug where a diff created via

diff = JsonDiff.asJson(source, target) // can't be applied via JsonPatch.apply(diff, source)

^ In other words the generated diff is invalid. An exception is thrown when applying the diff...

Expected Behavior

Given source and target json.
Then target equals JsonPatch.apply(JsonDiff.asJson(source, target), source)

Actual Behavior

thrown exception: [COPY Operation] Missing field xxx

If you create the diff via

JsonNode diff = JsonDiff.asJson(source, target, EnumSet.of(DiffFlags.OMIT_COPY_OPERATION));

it works but the diff might get big...

Specifications

Library Version: (0.4.5-SNAPSHOT until current) 0.4.9
Language (e.g. Java 1.8, Scala, etc): JAVA11

Steps to Reproduce the Problem

This is tricky - I wasn't able to reduce the problem further:

import com.fasterxml.jackson.databind.JsonNode;
import com.fasterxml.jackson.databind.ObjectMapper;
import org.junit.Test;

import java.io.IOException;
import java.util.EnumSet;

public class FailingDelta2Test {


    String p1 = "[\n" +
            "        {\n" +
            "          \"id\": \"id1\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id2\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id3\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id4\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id5\",\n" +
            "          \"data\": {\n" +
            "            \"referrer\": \"ref1\"\n" +
            "          }\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id6\",\n" +
            "          \"data\": {\n" +
            "            \"referrer\": \"ref1\",\n" +
            "            \"title\": \"foo\"\n" +
            "          }\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id7\",\n" +
            "          \"data\": {\n" +
            "            \"referrer\": \"ref1\",\n" +
            "            \"title\": \"foo\"\n" +
            "          }\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id8\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id9\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id10\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id11\",\n" +
            "          \"data\": {\n" +
            "            \"title\": \"foo\"\n" +
            "          }\n" +
            "        }\n" +
            "      ]";

    String p2 = "[\n" +

            "        {\n" +
            "          \"id\": \"id5\",\n" +
            "          \"data\": {\n" +
            "            \"referrer\": \"ref1\"\n" +
            "          }\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id5\",\n" +
            "          \"data\": {\n" +
            "            \"referrer\": \"ref1\"\n" +
            "          }\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id1\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id2\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id3\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id4\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id7\",\n" +
            "          \"data\": {\n" +
            "            \"referrer\": \"ref1\",\n" +
            "            \"title\": \"foo\"\n" +
            "          }\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id2\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id3\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id4\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id6\",\n" +
            "          \"data\": {\n" +
            "            \"referrer\": \"ref1\",\n" +
            "            \"title\": \"foo\"\n" +
            "          }\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id8\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id10\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id9\"\n" +
            "        },\n" +
            "        {\n" +
            "          \"id\": \"id11\",\n" +
            "          \"data\": {\n" +
            "            \"title\": \"foo\"\n" +
            "          }\n" +
            "        }\n" +
            "      ]";

    @Test
    public void testProcess6() throws IOException {

        ObjectMapper mapper = new ObjectMapper();

        JsonNode source = mapper.readValue(p1, JsonNode.class);
        JsonNode target = mapper.readValue(p2, JsonNode.class);

        JsonNode diff = JsonDiff.asJson(source, target /*,  EnumSet.of(DiffFlags.OMIT_COPY_OPERATION) */); // when using DiffFlags.OMIT_COPY_OPERATION the test passes



        // apply the generated diff to source -> we expect to get the target json but it fails with an exception
        JsonNode targetGeneratedViaPatch = JsonPatch.apply(diff, source);


        /*
            Exception:
            [COPY Operation] Missing field "data" at /10
         */

        /*
        When using zjsonpatch v 0.4.6 no error is thrown but following assertEquals would reveal
        that applying the patch generates unexpected json

       Add this to maven
       <dependency>
            <groupId>org.skyscreamer</groupId>
            <artifactId>jsonassert</artifactId>
            <version>1.5.0</version>
            <scope>test</scope>
        </dependency>

        JSONAssert.assertEquals(p2, mapper.writeValueAsString(targetGeneratedViaPatch), true);

         */
    }
}

[holograph]

Confirmed. Looking into it

[holograph]

Interim investigation shows that, as one would expect, this line turned out to be a really bad idea :-)

        // Hack to fix broken COPY operation, need better handling here

I'm still trying to figure out exactly what this does and why, I imagine it'll have to be rewritten with a bunch of unit tests for future proofing.

[holograph]

As far as I can tell the copy calculation mechanism is fundamentally broken; it finds nodes in the document that stay the same (position/value) after applying the patch, and makes a few assumptions about whether or not they're valid to use. The problem is, copy ops source from the current document as the patch is being applied, meaning that assumption can always be busted.

I'm currently researching a cleaner solution where the diff algorithm actually keeps track of the available document state (you can track progress on my fork in the issue-104 branch). This will likely be quite expensive memory-wise, but will be optional with DiffFlags.OMIT_COPY_OPERATION so it's OK as long as it's documented.