Can undo/redo operation be provided in automerge?

[hackerwins]

Hi. I'm considering using automerge to implement a collaborative text based edit editor. automerge provides general purpose format(JSON), I think it is appropriate to represent the editor's documentation.

And I have two questions.

• features like undo/redo are required in the editor. Can we implement undo/redo using automerge?
• Is there anything else to consider to implement a text-based editor using automerge?

Thank you for wonderful work.

[ept]

Hi @hackerwins! I think it would be awesome to have undo/redo support in Automerge. I've wanted to implement it for ages, but haven't yet had the time. If you have the time and want to contribute a design proposal, that would be great!

[hackerwins]

@ept Thanks for the reply. I do not know how to design and implement undo/redo right now. It seems that there are a lot of problems to think about, such as whether another user's operation should be undo. I'll leave a comment if I find out something. Thank you.

[FUEANGFA]

Thank you.

[FUEANGFA]

Thank you.

[aral]

(Not having looked into the Automerge algorithm yet) In WOOT (which is a CRDT algorithm that uses tombstones), redo and undo are implemented by having the atoms/characters/rows/operations have a “visibility” factor. <= 0 is deemed “invisible/active”, > 0 is deemed “visible/active”. An undo in such a system is effectively visibilityFactor-- and a redo is visibilityFactor++. Not sure if it will help here but thought I’d throw it out there.

(Just stumbled on this and looking forward to looking into it in more depth today.)

[ghost]

@aral thats super helpful. thanks for sharing this as i was wondering how it works

[FUEANGFA]

Thank you.

[ept]

@aral The undo algorithm you describe has an unfortunate edge case, which IIRC the paper fails to acknowledge: if two users concurrently undo the same operation (so the visibility factor goes to –1), and then one of the users redoes the operation, the redo has no user-visible effect, since the visibility factor is stuck at 0 (which is still within the inactive range). It effectively becomes impossible for the user to redo the operation.

This problem does not apply if users can only undo their own changes, but in that case, you don't even need a counter — a boolean flag would be sufficient. However, I think a better approach to implementing undo is to generate new operations that cancel out the effect of the undone operations (e.g. to undo a deletion, generate a new insertion; to undo an insertion, generate a new deletion).

[jessep]

Hi @ept! We did YC together, hope you are well. Automerge seems awesome and much needed.

I have a few thoughts about undo/redo based on my work with WorkFlowy, which updates via operations on a tree.

1) Undos append new operations onto the stack, and we keep a pointer into a past point in the stack based on where the undo is (as you suggested above) 2) Only undo operations performed on the current client (this is the user expectation, and as you already have a client key (I assume) it is easy to implement) 3) You need to undo/redo based on batches of operations, not individual operation, because lots of user interactions will prompt multiple operations, which need to be undone in a single step, not individually (ie: selecting 1000 non-adjacent lines and copy/pasting them elsewhere, you'd expect to be able to undo in one action, not 1000).

That's it! I'm assuming you've already thought about this more than I have, but wanted to chime in.

[ept]

Hi @jessep, great to hear from you! Thanks for sharing your experience, that's very helpful. I am planning to work on undo soon, and will follow those principles.

[coodoo]

I have successfully implemented undo/redo using the approach that @ept mentioned: generate new operations that cancel out the effect of the undone operations, but in batch, it worked perfectly for both text editor (which uses a linear data structure) and tree.

On top of that, time travel through all the history steps can be done in a similar manner, the difference is that user can only undo/redo it's own operation, but could travers all history steps.

That being said, it would be super cool to have this built into automerge itself and expose an API like A.undo(change, snapshot).

[ept]

Hi @coodoo, is your undo/redo implementation publicly available? I'm currently working on an undo feature built into Automerge itself (work-in-progress on the undo branch) and it would be nice to compare notes.

[ept]

I have now posted an implementation of undo/redo on PR #112. Feedback welcome if anyone wants to give it a try! The API is super simple: doc = Automerge.undo(doc) undoes the most recent change by the local user, and doc = Automerge.redo(doc) redoes it again.

[johnrees]

Thanks for implementing this feature @ept. Should this issue be closed now?

[ept]

Yes, thanks for reminding me. Undo/redo is available since Automerge 0.9.0, so I will close this issue.

[phedkvist]

How do you prevent from undoing the same changes multiple times after you have already undone something in the past when you keep adding operations to the history that cancels the operations out? For example:

      let s1 = Automerge.change(Automerge.init(), doc => doc.birds = [])
      s1 = Automerge.change(s1, doc => doc.birds.push('peregrine falcon'))
      s1 = Automerge.change(s1, doc => doc.birds.push('sparrowhawk'))
      assert.deepEqual(s1, {birds: ['peregrine falcon', 'sparrowhawk']})
      s1 = Automerge.undo(s1)
      assert.deepEqual(s1, {birds: ['peregrine falcon']})
      s1 = Automerge.undo(s1)
      assert.deepEqual(s1, {birds: []})
      s1 = Automerge.redo(s1)
      assert.deepEqual(s1, {birds: ['peregrine falcon']})
      s1 = Automerge.redo(s1)
      assert.deepEqual(s1, {birds: ['peregrine falcon', 'sparrowhawk']})

In this example, after the last redo has been done it would require additional 6 undos to get to the initial state, right?

[ept]

Hi @PHedkvist, Automerge tags every change to indicate whether it's a regular change, an undo, or a redo. Only regular changes add new items to the undo history, by setting the undoable argument to OpSet.addChange(). Undos and redos navigate backwards and forwards in the undo history without changing it. Does that answer your question?

[phedkvist]

@ept Great, thanks for the clarification.