Move-detection bug

[alfonsotw]

Disclaimer: Claude code found this bug, but I have checked the reproduction script and it is legit.

"""
Minimal reproduction of jsonpatch move-detection bug.

jsonpatch.make_patch() can produce patches containing `move` ops whose `from`
path is stale — i.e., it points to an index/key that no longer exists (or points
to the wrong element) in the intermediate state after preceding ops have been
applied. This makes the generated patch INVALID: jsonpatch's own
`JsonPatch.apply()` raises an exception on the generated patch.

Root cause: jsonpatch's DiffBuilder._item_added only adjusts the recorded
`from`-key for subsequent inserts when BOTH the old-key and the new-key are
ints (array indices). When the move detection involves mixed-type arrays
(containing dicts, primitives, and lists), preceding add/remove ops can shift
indices, making the recorded `from` path stale.

The 3 minimal reproductions below were found by brute-force search over
random arrays of mixed types.
"""

import sys
import os
import copy

sys.path.insert(0, os.path.join(os.path.dirname(__file__), '..', 'server'))

import jsonpatch


def demo(label, old, new):
    """Show that jsonpatch.make_patch(old, new).apply(old) fails."""
    patch = jsonpatch.make_patch(old, new)
    ops = patch.patch
    has_moves = sum(1 for op in ops if op.get('op') == 'move')
    print(f"\n{'='*60}")
    print(f"Case: {label}")
    print(f"  old: {old}")
    print(f"  new: {new}")
    print(f"  ops ({len(ops)}, {has_moves} moves): {ops}")

    try:
        result = patch.apply(copy.deepcopy(old))
        if result == new:
            print("  jsonpatch.apply: OK (no bug)")
        else:
            print(f"  jsonpatch.apply: WRONG RESULT")
            print(f"    expected: {new}")
            print(f"    got:      {result}")
    except Exception as e:
        print(f"  jsonpatch.apply: FAILS — {type(e).__name__}: {e}")
        print(f"  ^^^ BUG: jsonpatch generated an invalid patch it cannot apply itself")


# Case 1: seed=1 — 'a' is not a valid sequence index
# After preceding replace+add ops shift array elements, the remove at /d/arr/3/a
# targets the wrong element (a primitive instead of a dict).
demo(
    "Stale remove-inside-dict after index shift",
    {'d': {'arr': ['', 42, '', {'a': 1}]}},
    {'d': {'arr': [{'a': 1}, {'a': 1}, [1], {}, False, '', {'a': 1}]}},
)

# Case 2: seed=17 — indexing into an integer
# After removes shift indices, a remove at /d/arr/4/b tries to index into 42.
demo(
    "Indexing into integer after index shift",
    {'d': {'arr': [42, -1, 42, True, {'b': 'x'}, [1], 42]}},
    {'d': {'arr': ['', None, False, {}, {}, 42]}},
)

# Case 3: seed=25 — removing from empty array
# After removes, /d/arr/2/0 targets an array that no longer exists at that index.
demo(
    "Remove from non-existent array position",
    {'d': {'arr': [False, 42, [1], {'a': 1}, None, 42]}},
    {'d': {'arr': [None, 42, []]}},
)

print(f"\n{'='*60}")
print("All 3 cases demonstrate that jsonpatch.make_patch() generates patches")
print("that jsonpatch's own .apply() cannot execute. This is a confirmed bug")
print("in jsonpatch's move-detection algorithm (DiffBuilder._item_added).")
print("Workaround: disable move detection via _NoMoveDiffBuilder.")