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. 😆

[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.

[corka149]

Still not forgotten. 😄

I am thinking back and forth about this. It seems not to be a standard feature for a library that create diffs (inspiration of this lib jsonpatch.make_patch) and I see why.

It is not easy to say when it makes sense or not. When someone already know what matters, then they could create manually pretty simple the patch. The current implementation might be "dump" but it is a robust one.

[corka149]

At the moment it doesnt fit into this library. But I am open for good PRs.

[Valian]

Ok, thank you @corka149! Probably I'll try implementing this in my own fork soon and if it won't match your vision of jsonpatch I'll either publish it as a new lib or pull it directly into LiveVue 👍

At the moment it doesnt fit into this library

Just last question, why? In my opinion it might allow to create much smaller diffs for certain cases, and it can't be done in a different place than in the library creating the diff.

[corka149]

It is somehow not versatile and almost very specific to an use case. Yes, this library allows creating the diffs but it also allows to create patches "manually".

Another blocker for me is to distinguish when the object_hash function shall be used or not when one is provided. Maybe an data structure has several list. The object_hash function could check them all. But is this intended?