search

peer-base / peer-pad

📝 Online editor providing collaborative editing in really real-time using CRDTs and IPFS.
https://peerpad.net
MIT License
678 stars 57 forks source link

Multi-user undo #272

Open jimpick opened 5 years ago

jimpick commented 5 years ago

Right now, if the user hits their "Undo" key sequence eg. Command-Z or Ctrl-Z, they might (surprisingly) undo the edits of another user that is concurrently editing the same doc.

There are other multi-user editors that use Codemirror. It might be good to investigate what they are doing for this.

parkan commented 5 years ago

here-be-dragons

I actually got frustrated with how this worked in another collaborative editor a little while ago and went around looking for better solutions. Sadly, I didn't find anyone who had a sane undo behavior, and sort of lost my faith in the undo-redo mechanic overall. Some editors I looked at solved the problem in the Alexander the Great style, by disabling undo altogether.

From the data model perspective, it seems clear that you must implement undo as a first class replicated type, or else you will end up in causality hell. I'm not sure what research exists on this subject w/δ-CRDTs, the only papers I've seen focus on undo with operation-based CRDTs.

From a user perspective, the most intuitive thing is probably undoing all user input events (insertions as well as deletions) since the last idle input event or periodic "tick" (whichever is nearer). Codemirror has its own edit stack that mixes real user input and update() events, so we would probably need to extract the history, modify it to remove only the user events, and write it back (while blocking the UI to prevent further updates).

The best hack solution I can think of is to peek at the history, undo any user input events until the first update() coming from the network, and send a corresponding edit event.

Overall, this feels like a treacherous area with a lot of opportunity for corruption and problems in synchronizing "our" state and codemirror history. A good way to simplify this might be replacing the CM history facilities with our own, but that might make us less compatible as a drop-in solution.

jimpick commented 5 years ago

I see that automerge tackled that issue on the CRDT level recently:

https://github.com/automerge/automerge#undo-and-redo

parkan commented 5 years ago

@jimpick their approach (generate "negated" versions of history events) is similar to my intuition, but their system is OP-based (I think, based on https://github.com/automerge/automerge/blob/master/backend/op_set.js), which makes that easier

jimpick commented 5 years ago

ProseMirror (a relative of CodeMirror, by the same author) also has collaborative editing support. I believe that what they do is keep track of a stack of changes, and then they can rewind back to a checkpoint, and replay the changes (minus what was undid by a particular writer).

Of course, it's not very well defined what users should expect when they hit undo on some text they added, but some other writer modified... (I'm going to guess that all future modifications get tossed)

parkan commented 5 years ago

tossing all your changes since some checkpoint + any causally related 3rd party changes seems to be reasonably intuitive for the user, though I'm not sure how the 3rd party will feel about it -- you would probably need some heuristics to keep the maximum set of tossed changes reasonable

I definitely support disabling undo altogether as a short-term fix