Patch order sometimes wrong

[jbussemaker]

Python 3.9.18, jsonpatch 1.33

I came across an issue where sometimes the order of the created patch operations is wrong:

src_obj = {'a': [{'id': [1]}, {'id': [2]}], 'b': [{'id': 5}]}
tgt_obj = {'a': [{'id': []}, {'id': [1]}], 'b': [{'id': 5, 'newKey': 2}]}

patch = jsonpatch.make_patch(src_obj, tgt_obj)
print(patch)

The correct patch is (of course, using a combination of adds and removes would also work, but it seems jsonpatch prefers moves):

[
  {"op": "move", "from": "/a/1/id/0", "path": "/b/0/newKey"},
  {"op": "move", "from": "/a/0/id/0", "path": "/a/1/id/0"}
]

However, sometimes the patch is created in the reverse order, which because the operations are "chained" results in a wrongly-modified target object.

Reproduce (patch_test.py):

import jsonpatch

src_obj = {'a': [{'id': [1]}, {'id': [2]}], 'b': [{'id': 5}]}
tgt_obj = {'a': [{'id': []}, {'id': [1]}], 'b': [{'id': 5, 'newKey': 2}]}

patch = jsonpatch.make_patch(src_obj, tgt_obj)
print(patch)

# Check normal application of the patch
tgt_obj_check = jsonpatch.apply_patch(src_obj, patch)
print('Forward', 'OK' if len(jsonpatch.make_patch(tgt_obj, tgt_obj_check).patch) == 0 else 'ERROR', '->', tgt_obj_check)

# Check reverse application of the patch
tgt_obj_check = jsonpatch.apply_patch(src_obj, patch.patch[::-1])
print('Reverse', 'OK' if len(jsonpatch.make_patch(tgt_obj, tgt_obj_check).patch) == 0 else 'ERROR', '->', tgt_obj_check)

Running the script several times (note that the results are random, so probably related to some internal Python hash):

>> python patch_test.py
[{"op": "move", "from": "/a/1/id/0", "path": "/b/0/newKey"}, {"op": "move", "from": "/a/0/id/0", "path": "/a/1/id/0"}]
Forward OK -> {'a': [{'id': []}, {'id': [1]}], 'b': [{'id': 5, 'newKey': 2}]}
Reverse ERROR -> {'a': [{'id': []}, {'id': [2]}], 'b': [{'id': 5, 'newKey': 1}]}

>> python patch_test.py
[{"op": "move", "from": "/a/0/id/0", "path": "/a/1/id/0"}, {"op": "move", "from": "/a/1/id/0", "path": "/b/0/newKey"}]
Forward ERROR -> {'a': [{'id': []}, {'id': [2]}], 'b': [{'id': 5, 'newKey': 1}]}
Reverse OK -> {'a': [{'id': []}, {'id': [1]}], 'b': [{'id': 5, 'newKey': 2}]}

>> python patch_test.py
[{"op": "move", "from": "/a/0/id/0", "path": "/a/1/id/0"}, {"op": "move", "from": "/a/1/id/0", "path": "/b/0/newKey"}]
Forward ERROR -> {'a': [{'id': []}, {'id': [2]}], 'b': [{'id': 5, 'newKey': 1}]}
Reverse OK -> {'a': [{'id': []}, {'id': [1]}], 'b': [{'id': 5, 'newKey': 2}]}

>> python patch_test.py
[{"op": "move", "from": "/a/0/id/0", "path": "/a/1/id/0"}, {"op": "move", "from": "/a/1/id/0", "path": "/b/0/newKey"}]
Forward ERROR -> {'a': [{'id': []}, {'id': [2]}], 'b': [{'id': 5, 'newKey': 1}]}
Reverse OK -> {'a': [{'id': []}, {'id': [1]}], 'b': [{'id': 5, 'newKey': 2}]}

>> python patch_test.py
[{"op": "move", "from": "/a/0/id/0", "path": "/a/1/id/0"}, {"op": "move", "from": "/a/1/id/0", "path": "/b/0/newKey"}]
Forward ERROR -> {'a': [{'id': []}, {'id': [2]}], 'b': [{'id': 5, 'newKey': 1}]}
Reverse OK -> {'a': [{'id': []}, {'id': [1]}], 'b': [{'id': 5, 'newKey': 2}]}

>> python patch_test.py
[{"op": "move", "from": "/a/0/id/0", "path": "/a/1/id/0"}, {"op": "move", "from": "/a/1/id/0", "path": "/b/0/newKey"}]
Forward ERROR -> {'a': [{'id': []}, {'id': [2]}], 'b': [{'id': 5, 'newKey': 1}]}
Reverse OK -> {'a': [{'id': []}, {'id': [1]}], 'b': [{'id': 5, 'newKey': 2}]}

>> python patch_test.py
[{"op": "move", "from": "/a/1/id/0", "path": "/b/0/newKey"}, {"op": "move", "from": "/a/0/id/0", "path": "/a/1/id/0"}]
Forward OK -> {'a': [{'id': []}, {'id': [1]}], 'b': [{'id': 5, 'newKey': 2}]}
Reverse ERROR -> {'a': [{'id': []}, {'id': [2]}], 'b': [{'id': 5, 'newKey': 1}]}

>> python patch_test.py
[{"op": "move", "from": "/a/1/id/0", "path": "/b/0/newKey"}, {"op": "move", "from": "/a/0/id/0", "path": "/a/1/id/0"}]
Forward OK -> {'a': [{'id': []}, {'id': [1]}], 'b': [{'id': 5, 'newKey': 2}]}
Reverse ERROR -> {'a': [{'id': []}, {'id': [2]}], 'b': [{'id': 5, 'newKey': 1}]}

>> python patch_test.py
[{"op": "move", "from": "/a/1/id/0", "path": "/b/0/newKey"}, {"op": "move", "from": "/a/0/id/0", "path": "/a/1/id/0"}]
Forward OK -> {'a': [{'id': []}, {'id': [1]}], 'b': [{'id': 5, 'newKey': 2}]}
Reverse ERROR -> {'a': [{'id': []}, {'id': [2]}], 'b': [{'id': 5, 'newKey': 1}]}

Maybe related to issues #152 #151 #121 #30 #4 ?