Move operation #319
Description
Automerge documents should have a way of moving some subtree to a different location in the document. This includes changing an object to have a new parent node, reordering elements in a list, and renaming a key in a map. We have already designed an algorithm to do this; the next step is to integrate it into Automerge. We should also ensure that the move operation is compatible with undo (#318).
When two users concurrently move the same object, the result after merging should be that the moved object appears in one of the two destination locations (picked arbitrarily based on ordering of operation IDs). When multiple objects are moved to new parents, the algorithm should ensure that no cycles are introduced into the document. These rules ensure that the document remains a tree (i.e. there is no more than one path from the root to a given document object, and every object apart from the root has one parent).
One open question is what the algorithm should do when the same object is concurrently moved and removed:
- should the object appear in the destination location of the move (i.e. the move takes precedence over the remove), or
- should the object be deleted from all locations in the document (i.e. the remove takes precedence over the move)?
I think option 1 would fit better with Automerge's current architecture. It would also be consistent with Automerge's current behaviour: when a key in a map is concurrently removed and updated to a new value, the new value takes precedence.
Adding support for a move operation would also fix #263.