search

automerge / automerge-classic

A JSON-like data structure (a CRDT) that can be modified concurrently by different users, and merged again automatically.
http://automerge.org/
MIT License
14.75k stars 466 forks source link

Move operation #319

Open ept opened 3 years ago

ept commented 3 years ago

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:

  1. should the object appear in the destination location of the move (i.e. the move takes precedence over the remove), or
  2. 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.

echarles commented 3 years ago

@ept I don't have strong opinion on the options. I would just say that if one of the options is much easier to implement than the other, it would be the one to choose for now.

If have tried the workaround described on https://github.com/automerge/automerge/issues/263#issuecomment-648795698.

  1. After a move, the nested structure is kept, but unfortunately object types like Automerge.Text (with insert/delete capabilities) are converted to simple strings.
  2. I am also not sure that the observers of the changed object continue to be operational (I would say they should).

This makes this feature a needed one IMHO for the next release.