Option to use unique identifier when diffing lists

[Valian]

Is your feature request related to a problem? Please describe.

Currently items in lists are compared by index.

In some cases, list patches might be much smaller if we would use unique identifier present in items to distinguish if they were moved around. For example:

original = [
  %{id: 1, name: "test1"},
  %{id: 2, name: "test2"},
  %{id: 3, name: "test3"},
  %{id: 4, name: "test4"},
  %{id: 5, name: "test5"},
  %{id: 6, name: "test6"},
]

updated = List.insert_at(original, 0, %{id: 123, name: "test123"})

Jsonpatch.diff(original, updated)

Output:

[
  %{value: %{id: 6, name: "test6"}, path: "/6", op: "add"},
  %{value: "test5", path: "/5/name", op: "replace"},
  %{value: 5, path: "/5/id", op: "replace"},
  %{value: "test4", path: "/4/name", op: "replace"},
  %{value: 4, path: "/4/id", op: "replace"},
  %{value: "test3", path: "/3/name", op: "replace"},
  %{value: 3, path: "/3/id", op: "replace"},
  %{value: "test2", path: "/2/name", op: "replace"},
  %{value: 2, path: "/2/id", op: "replace"},
  %{value: "test1", path: "/1/name", op: "replace"},
  %{value: 1, path: "/1/id", op: "replace"},
  %{value: "test123", path: "/0/name", op: "replace"},
  %{value: 123, path: "/0/id", op: "replace"}
]

Describe the solution you'd like I'd love to have additional option to diff being a function returning unique identifier for a given object &object_hash/1 that would trigger different diffing mechanism for lists.

Output I'd like to get for the previous example:

Jsonpatch.diff(original, updated, object_hash: fn %{id: id} -> id end)

[
  %{value: %{id: 123, name: "test123"}, path: "/0", op: "add"}
]

Describe alternatives you've considered Some JS libraries support such option, eg jsondiffpatch

Additional context I'm planning to use json_patch in LiveVue to reduce payload size. Already playing with it. It's very common that items in lists have unique identifiers (eg. id) that should make it possible to create much more optimized patches.

[corka149]

Hi @Valian

I checkout jsondiffpatch. It sounds like a neat feature. I will plan it for version 2.3.

[Valian]

I wonder how much work it would take for CursorAI to implement 😅

I may try to give it a quick shot and see.

[corka149]

My time is a heavily limited but the feature is not forgotten. :laughing:

[Valian]

I've tried working on this, but it's not trivial. We have to generate removals, additions, and then adjust indexes of all elements and see if any "moves" are necessary.

Well by saying "tried working on this" I meant having a lengthy discussion with CursorAI and getting some starting implementation and tests, but sadly it's not really up to the standard I'd like it to be. And still has bugs 😅

[corka149]

In my head it would require to create a full hash-to-index map for source and then use it while checking the target only for moves. All detected moves will be ignored in the next step where the regular diff algorithm will run to detect changes, additions and deletions. But so far I had no chance to test it. 😕

[Valian]

Hmm... would it work for my initial example?

Eg. element with id 1 moved from index: 0 to index: 1 but that was not a real move, rather a result of inserting another item at index 0.

So personally I'm thinking about getting that full hash-to-index map, finding all additions and removals, and then updating the indexes of that map so we can find "real" moves (that are not results of additions / removals).

So in the previous example, after discovering insertion at index 0 we would increase indexes of all source elements which are >= 0 to accomodate for that. And then checking for moves will properly give us nothing.

[corka149]

Oh, yes. The expected new index needs to be calculated for all subsequent items.