`:m` move operator

[enspritz]

Hi!

In the context of a tree diff, given an element that is re-parented to a different node, version 0.6.3 produces an editscript that transcribes 2 operations, an addition and a removal:

(e/diff
  [{:a 1} {:b 2} {:c 3}
   [{:m 4} {:z 999} {:n 5}]]

; {:z 999} is re-parented to top of tree
  [{:a 1} {:b 2} {:z 999} {:c 3}
   [{:m 4} {:n 5}]])

;;==> [[[2] :+ {:z 999}] [[4 1] :-]]

Given that {:z 999} has = equality, conceptually an editscript could be produced that transcribes a single move operation, perhaps patterned as:

[ [source-path] :m [dest-path] ]

; Continuing the example above:
[[4 1] :m [2]]

This is valuable in the use case where a tree of data elements is persisted in an external datastore where elements are assigned new IDs on creation. By adhering to an editscript that :- deletes an existing element (thus deleting it from the persistence store, forever blapping that ID) only to :+ re-add the equivalent data in a different location, the element is inadvertently is assigned a new ID by the datastore. Such elements are notionally equivalent but are logically now different on account of the persistence layer ID being changed, and that ID is what other things are keyed on. This gives rise to chaos... ;)

BTW, I'm currently thinking to modify the emitted editscript to identify and collapse such pairs, as a kind of post-processor, but I haven't thought-through the implications for element ordering.

[huahaiy]

I would think about this. My preliminary thought is that :m would require a full tree diffing algorithm that has time complexity of O(n^3). I don't think that would be practical.

[enspritz]

I understand your point.

For anyone looking at this in future, for the use case I am currently faced with, I'll move :- entities to a holding container of sorts, :+s will first check for membership in the container and on positive match move them to the destination instead of (re-)creating the element. At algorithm end, remaining content in container is deleted. (N.B. This has a complexity cost that I am willing to pay)