cheapDiff produce a wrong patch when inverting values in list

[eniac314]

I may have found a bug. I tried replacing diff by cheapDiff for efficiency reasons but found out that the json output after applying the patch was not the same.

Here is an example of diverging results:

import Json.Diff as Diff exposing (..)
import Json.Patch.Invertible as Inv exposing (..)
import Json.Encode as E
import Json.Decode as D                                 
import Json.Patch as JP exposing (..)

doc1 = E.list E.int [1,2,3,4]
doc2 = E.list E.int [2,1,3,4]

patch = Diff.diff doc1 doc2
-- [Remove ["1"],Add ["0"] <internals>] : Patch

cheapPatch = Diff.cheapDiff doc1 doc2 |> Inv.toMinimalPatch
-- [Replace ["1"] <internals>] : Patch

JP.apply patch doc1 |> Result.toMaybe |> Maybe.map (D.decodeValue <| D.list D.int)
-- Just (Ok [2,1,3,4])

JP.apply cheapPatch doc1 |> Result.toMaybe |> Maybe.map (D.decodeValue <| D.list D.int)
-- Just (Ok [1,1,3,4]) : Maybe (Result D.Error (List Int))

[Lattyware]

I took a really quick look at this, and I think this is just a really odd bug with the implementation of get in Diff.elm. I have no idea why it would return Nothing for the zero case, and presumably that's what is causing this.

I'll push up a fix as soon as I can, but that probably won't be for a bit (I'm ill right now), and it'd make sense to also run test cases for cheapDiff to try and make sure there aren't any other hidden issues. If time is a factor, you might want to try applying that fix (just removing the else case so get is just values |> List.drop i |> List.head) and hopefully that fixes things for you.

[eniac314]

Thank you for replying so quickly. Your fix works for this simple test case. I'll take a closer look tomorrow to see if it works in my code base as well.

Take care!

[eniac314]

So circling back to this problem:
With the test suite rewritten with cheapDiff instead of diff like this:

toTest : TestCase -> Test
toTest { description, a, b, patch } =
    test (description ++ " | a: " ++ (a |> JsonE.encode 0) ++ " | b: " ++ (b |> JsonE.encode 0) ++ " | patch: " ++ (patch |> Json.encoder |> JsonE.encode 0))
        (\_ -> Diff.cheapDiff a b |> toMinimalPatch |> expectPatchEqual patch)

With the get function as it is I get 30 tests failing. Changing it the way you told me improves the situation to only 9 tests failing. Here is the log:

    [Add ["2"] <internals>,Replace ["1"] <internals>]
    ╷
    │ Expect.equal
    ╵
    [Add ["1"] <internals>]


↓ Diff
↓ Diff.diff correctly handles
✗ add to beginning of array | a: ["foo","sil"] | b: ["bar","foo","sil"] | patch: [{"op":"add","path":"/0","value":"bar"}]

    [Add ["2"] <internals>,Replace ["1"] <internals>,Replace ["0"] <internals>]
    ╷
    │ Expect.equal
    ╵
    [Add ["0"] <internals>]


↓ Diff
↓ Diff.diff correctly handles
✗ add nested array | a: ["foo","sil"] | b: ["foo",["bar","baz"],"sil"] | patch: [{"op":"add","path":"/1","value":["bar","baz"]}]

    [Add ["2"] <internals>,Replace ["1"] <internals>]
    ╷
    │ Expect.equal
    ╵
    [Add ["1"] <internals>]


↓ Diff
↓ Diff.diff correctly handles
✗ replace root | a: {"foo":"bar"} | b: {"baz":"qux"} | patch: [{"op":"replace","path":"","value":{"baz":"qux"}}]

    [Add ["baz"] <internals>,Remove ["foo"]]
    ╷
    │ Expect.equal
    ╵
    [Replace [] <internals>]


↓ Diff
↓ Diff.diff correctly handles
✗ removing first item | a: [1,2,3,4] | b: [2,3,4] | patch: [{"op":"remove","path":"/0"}]

    [Remove ["3"],Replace ["2"] <internals>,Replace ["1"] <internals>,Replace ["0"] <internals>]
    ╷
    │ Expect.equal
    ╵
    [Remove ["0"]]


↓ Diff
↓ Diff.diff correctly handles
✗ removing multiple items | a: [1,2,3,4] | b: [1,3] | patch: [{"op":"remove","path":"/3"},{"op":"remove","path":"/1"}]

    [Remove ["3"],Remove ["2"],Replace ["1"] <internals>]
    ╷
    │ Expect.equal
    ╵
    [Remove ["3"],Remove ["1"]]


↓ Diff
↓ Diff.diff correctly handles
✗ complex list change | a: [1,2,3,4] | b: [1,5,4] | patch: [{"op":"remove","path":"/2"},{"op":"replace","path":"/1","value":5}]

    [Remove ["3"],Replace ["2"] <internals>,Replace ["1"] <internals>]
    ╷
    │ Expect.equal
    ╵
    [Remove ["2"],Replace ["1"] <internals>]


↓ Diff
↓ Diff.diff correctly handles
✗ giant replacements vs lots of small changes | a: {"a":[1,2,3,4,5,6,7,8,9,10,"add some length to this so it should not be replaced because repeating all this is more expensive than the overhead from the operations"]} | b: {"a":[11,12,13,14,5,6,7,8,9,10,"add some length to this so it should not be replaced because repeating all this is more expensive than the overhead from the operations"]} | patch: [{"op":"replace","path":"/a/0","value":11},{"op":"replace","path":"/a/1","value":12},{"op":"replace","path":"/a/2","value":13},{"op":"replace","path":"/a/3","value":14}]

    [Replace ["a","3"] <internals>,Replace ["a","2"] <internals>,Replace ["a","1"] <internals>,Replace ["a","0"] <internals>]
    ╷
    │ Expect.equal
    ╵
    [Replace ["a","0"] <internals>,Replace ["a","1"] <internals>,Replace ["a","2"] <internals>,Replace ["a","3"] <internals>]


↓ Diff
↓ Diff.diff correctly handles
✗ pick between lots of small changes vs a reasonable replacement | a: {"a":{"b":{"c":{"1":1,"2":2,"3":3}}}} | b: {"a":{"b":{"c":{"x":1,"y":2,"z":3}}}} | patch: [{"op":"replace","path":"/a/b/c","value":{"x":1,"y":2,"z":3}}]

    [Remove ["a","b","c","1"],Remove ["a","b","c","2"],Remove ["a","b","c","3"],Add ["a","b","c","x"] <internals>,Add ["a","b","c","y"] <internals>,Add ["a","b","c","z"] <internals>]
    ╷
    │ Expect.equal
    ╵
    [Replace ["a","b","c"] <internals>]



TEST RUN FAILED

Duration: 413 ms
Passed:   136
Failed:   9

I am not sure how to proceed from here.

[Lattyware]

Thanks for taking a look at this. I suspect, looking at the failures here, that these are not actually failures, but rather the expected difference between a cheap diff and an expensive one.

The answer is probably to have different expected results for the cheap diff, or a different test suite that just checks if generating the patch and applying it produces the expected value, rather than looking for the "correct" patch, as we aren't looking for optimal results with the cheap diff, just working ones.

[Lattyware]

Sorry for being so slow with this, but I believe that this issue should now be fixed as of 1.0.1. If you think there is any problem with the fix, feel free to create a new issue, but hopefully it solves the issue.

[eniac314]

All right, thanks a lot, I'll give it a spin.  Aug 9, 2021, 00:12 by ***@***.***:

…

Sorry for being so slow with this, but I believe that this issue should now be fixed as of 1.0.1. If you think there is any problem with the fix, feel free to create a new issue, but hopefully it solves the issue. — You are receiving this because you authored the thread. Reply to this email directly, > view it on GitHub <#2 (comment)>> , or > unsubscribe <https://github.com/notifications/unsubscribe-auth/ACER6MS5S2SGE4GNESGA7MTT336LVANCNFSM46T3AAMA>> . Triage notifications on the go with GitHub Mobile for > iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675>> or > Android <https://play.google.com/store/apps/details?id=com.github.android&utm_campaign=notification-email>> .