Support Multi-User Undo/Redo

[hackerwins]

Description:

Written by @hyemmie

About multi-user undo/redo

When specifying Undo/Redo functionality, the following criteria could be considered.

1. How to select an action to cancel? ⇒ linear vs selective

• linear: Users can't choose which actions to undo, and by default, they can undo and redo in reverse order, starting with the most recent action. If user want to cancel a specific action that is not the most recent, user need to cancel all of them, starting with the most recent and ending with that action.
• selective: Users can randomly select an action to cancel among all actions and undo and redo only that action.

2. Does a single user have permission to undo/redo all actions in collaborative editing environment? ⇒ local vs global

• local: Users can only undo and redo their own actions.
• global: Users can undo and redo the actions of all participants in a collaborative edit.

	Local	Global
Linear	Undo one’s own action in reverse chronological order from newest to oldest. (ex. Automerge, Google Docs, Figma)	Undo all users' actions in reverse chronological order from newest to oldest . (ex. CodePair)
Selective	Select and undo any of one’s own actions. (ex. Azurite)	Select and undo any of all users’ actions.

For Yorkie, we don't need selective functionality at this point, but rather the ability for users to undo/redo only their own work.

Discussion

To provide multi-user (”local-linear”) undo/redo, we can start with the following tasks.

1. Implement data structure for multi-user (”local-linear”) undo/redo.
   This task could be done in two ways.

• Implement Individual data structure for PoC and integrate it with Yorkie’s RGATreeSplit.
• Implement additional undo/redo feature to current RGATreeSplit.

2. Design the overall architecture.
   We'll need to combine ideas on how to manage and store tasks separately for each user, how to integrate with your current database, and more into a single architecture.

Here are some reference implementations you might want to check out.
Reference:

• Automerge: https://github.com/automerge/automerge#undo-and-redo
• Yjs: https://github.com/yjs/yjs#yundomanager

Why:

To eliminate the user experience of canceling another user's operation, Yorkie needs to support user-specific undo/redo.

[hackerwins]

Tasks:

• Basic Implementation: Introduce basic architecture to support undo and redo yorkie-js-sdk#650
  • Presence.Set
  • Counter.Increase
• Object: Support Undo/Redo for object.set and object.remove operations yorkie-js-sdk#658
  • Object.Set
  • Object.Remove
• Array:
  • Array.Add
  • Array.Remove
  • Array.Move
• Text: Update EditReverse operation to support undo and redo on Text.edit yorkie-js-sdk#649
  • Text.Edit
  • Text.Style
• Tree:
  • Tree.Edit
  • Tree.Style