Introduce multi-user undo and redo to Yorkie

[hyemmie]

Last updated at November 27, 2023
edited by @chacha912, @hyemmie
If you find something deprecated, please feel free to add to or correct this issue.

What would you like to be added: Support undo and redo feature for multiple users in Yorkie. The previous issue about multi-user undo/redo is already at #49, which contains specification about undo and initial discussion about it.

This issue is more about sharing the undo/redo related discussions and implements up to date, with the goal of getting more contributors involved in the work.

Why is this needed: Undo and redo are important features in collaborative applications, but Yorkie does not yet support them and there are still technical issues to be resolved.

---

Table of Contents

• 1. Introduction of Undo and Redo
  • 1.1 The Basic Design of Undo and Redo
    • 1.1.1 Previous Information
    • 1.1.2 Data Structure
  • 1.2 The Specification of Undo and Redo
    • 1.2.1 Undo
    • 1.2.2 Redo
• 2. Latest Design of Undo and Redo in Yorkie
  • 2.1 The Goal of Design
  • 2.2 Client Document Design
  • 2.3 Document Editing Process
    • 2.3.1 Local Editing (Update)
    • 2.3.2 Local Editing (Undo)
    • 2.3.3 Local Editing (Redo)
    • 2.3.4 Remote Editing
  • 2.4 Implementation of Reverse Operations
    • 2.4.1 Counter.Increase
    • 2.4.2 Object.Set and Object.Remove
    • 2.4.3 [WIP] Text.Edit
• 3. Discussions and Issues
  • 3.1 Insufficient Discussion about User Intent Prevention
  • 3.2 Unclear Definitions of ‘Reverse’ Operation
  • 3.3 Conflicts between Undo/Redo Implement and Current Policy: Previous Data and GC
• 4. Future Work
  • 4.1 Discussion for Specification
  • 4.2 Implement Remaining Reverse Operations
• 5. References

1. Introduction of Undo and Redo

1.1 The Basic Design of Undo and Redo

In general, here are the choices you need to make to implement undo and redo functionality:

1. Which information will you utilize to move to a "before state" or "after state"?
2. Which data structure will you store the information in?

1.1.1 Previous Information

1. Save the entire state: Select a specific state, and return to that state to undo or redo.
2. Save the delta-state: Save only the difference of state, and apply the difference to undo or redo.
3. Save the actions (reverse operation): Save the reverse operation and apply the operation to undo or redo.
4. Hybrid method
   • Save snapshots at specific points in time, and reverse operation between those points in time.
   • Find closest snapshot and apply the operations afterward to undo or redo.

1.1.2 Data Structure

The following data structures can be used for implementation.

1. Undo stack and redo stack
2. History stack and pointer
3. Doubly linked list

1.2 The Specification of Undo and Redo

To implement undo and redo features, abstract features need to be translated into physical specification. After checking the behavior of the "undo" and "redo" features in other products, I defined the physical specification as follows.

1.2.1 Undo

As mentioned in issue #49, the following criteria could be considered to specify undo and redo functionality.

1. How to select an action to undo? ⇒ 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.

1.2.2 Redo

For a redo operation, unlike an undo, user cannot select a target operation. Since a redo is an undo-dependent operation, the target of a redo is determined by the preceding undo. Therefore, we do not consider action selection for a redo, only whether it is local/global.

In figure (from [4]) above, when A performs the undo operation(2c), a local undo results in the state canceling A's operation set(black -> red) and returning to black(2d1). In the case of global undo, the most recent action, B’s set(red -> green), is canceled and the state is returned to red (2d2).

A subsequent redo in the global undo state results in a state of 2e3, which returns to green, but when A redoes in the local undo state of 2d1, there are two possible outcomes.

1. Local: Restores the exact state lost by undo. (2e1)
2. Global: Restores the state prior to its corresponding undo, regardless of the origin of operations that constitute that state. (2e2)

According to Leo Stewen and Martin Kleppmann[4], most collaborative applications exhibit local undo and global redo behaviour, which is the most intuitive for users. We need to decide if we should implement undo and redo with this strategy in the yorkie project.

2. Latest Design of Undo and Redo in Yorkie

2.1 The Goal of Design

The goals of the undo/redo architecture, currently reflected in version 0.4.7 of the JS-SDK, are as follows.

1. Implementing undo and redo by defining and storing the reverse of a specific operation.
2. Using the undo stack and redo stack for storing reverse operations.

The initial architecture was designed using liveblocks project as a reference and may be modified in the future.

2.2 Client Document Design

The figure below shows the changes made to the existing yorkie document design to support undo and redo. We've colored the newly added elements in green.

The changes include:

1. Add history at Document.
2. Add undoStack and redoStack at history.
3. [WIP] Create new type of Operation to support undo and redo.

In the current design, the document is designed to attach to each client, so each client manages their own undo stack. Therefore, the current design is "local undo" behavior.

2.3 Document Editing Process

Here's the documentation on how a document is edited in Yorkie: document-editing.md

Based on this, the document editing behavior process, including undo and redo, looks like following.

2.3.1 Local Editing (Update)

Local Editing still consists of three logic parts:

1. Calling Document.Update.
2. Pushing Changes to Server.
3. Propagating Changes to Peers.

However, there is an additional process that needs to be handled inside Document.Update.

1-1 ~ 1-2. When Document.Update is called, the proxy applies the user's edits to the Clone and creates a Change for it.

1-3. Changes are applied to Root. The Root can be only updated by changes.

• To implement transaction processing, user's edits are first applied to the Clone instead of the Root. If applying to the clone fails, the changes won't be reflected in the root.

1-4. (✨new) Generate the reverse operations of the operations contained in change, referencing the current root state.

• To implement local undo, create a reverse operation and add it to the undo stack only when a local update occurs.

1-5. Those changes are added to LocalChanges. It is used later to send local changes to the server.

• Changes are first applied locally and then later reflected on the remote. Refer to the local-first software for more information.

1-6. (✨new) Reverse operations are pushed to undoStack and clears redoStack.

• Most apps follow a simple strategy: when there's a local update, they clear the redo stack. It's a simple and intuitive approach, but here's the catch: if users undo several steps and then do something new, the redo stack resets, and any redo steps after that point are lost.
• Another way to handle this is by branching the redo stack. This means even if users undo and then do something new, the previous redo steps are saved. However, managing branches can get a bit tricky. (Ref: history branch issue in vscode)

2.3.2 Local Editing (Undo)

In addition to Update, Undo and Redo are editing that can occur locally. However, the logic part of Undo and Redo is not much different than Update ; locally calls a method on document and the change is passed through the server to the other peers.

1. Calling Document.History.Undo
2. Pushing Changes to Server.
3. Propagating Changes to Peers.

The only different part is number 1, the process inside Document.History.Undo (or Redo).

1-0 ~ 1-1. (✨new) When Document.History.Undo() is called, the history operation is popped from the undoStack, and based on this, Change is generated within a context.

1-2 ~ 1-3. (✨new) Apply the change to both the clone and the root.

• If applying the reverse change is not possible, skip the following steps.
  (For example, if the target element is deleted in set and remove operations.)

1-4 ~ 1-5. (✨new) Generate a reverse change for the change and push it to the redoStack.

• To implement global redo, create a reverse change based on the document state at the undo point.

1-6. Those changes are added to LocalChanges. It is used later to send local changes to the server.

2.3.3 Local Editing (Redo)

Redo works the same way as undo, just swapping the roles of the undoStack and redoStack.

2.3.4 Remote Editing

Operations caused by one user's undo or redo are also communicated to other peers via change, so other peers can pull the change and apply it to their document just as before.

2.4 Implementation of Reverse Operations

In the above design, every time an operation is executed, its reverse operation must be generated and put into the undoStack. Therefore, we need to implement a reverse operation for every operation currently supported by Yorkie.

2.4.1 Counter.Increase

The reverse operation of Counter.Increase is defined in the simplest way: Another Counter.Increase operation that subtracts the opposite of an added value. (code)

// increase_operation.ts
private toReverseOperation(): Operation {
  const primitiveValue = this.value.deepcopy() as Primitive;

  const valueType = primitiveValue.getType();
  const value =
    valueType === PrimitiveType.Long
      ? (primitiveValue.getValue() as Long).multiply(-1)
      : (primitiveValue.getValue() as number) * -1;

  const reverseOp = IncreaseOperation.create(
    this.getParentCreatedAt(),
    Primitive.of(value, primitiveValue.getCreatedAt()),
  );
  return reverseOp;
}

As in the code above, the value of the counter operation is multiplied by -1 to create a new Increase operation with that value as value as the reverse operation.

2.4.2 Object.Set and Object.Remove

The reverse operations of Object set and remove can be defined as follows:

• Set: If the value did not exist previously, it is deleted; otherwise, the previous value is set.
• Remove: The previous value is set.

// set_operation.ts 
private toReverseOperation(value: CRDTElement | undefined): Operation {
  let reverseOp: SetOperation | RemoveOperation = RemoveOperation.create(
    this.getParentCreatedAt(),
    this.value.getCreatedAt(),
  );

  if (value !== undefined && !value.isRemoved()) {
    reverseOp = SetOperation.create(
      this.key,
      value.deepcopy(),
      this.getParentCreatedAt(),
    );
  }
  return reverseOp;
}

// remove_operation.ts 
private toReverseOperation(
  parentObject: CRDTContainer,
): Operation | undefined {
  if (parentObject instanceof CRDTObject) {
    const key = parentObject.subPathOf(this.createdAt);
    const value = parentObject.get(key);
    return SetOperation.create(
      key,
      value.deepcopy(),
      this.getParentCreatedAt(),
    );
  }
}

In the case of setting the previous value, the time of re-creation is indicated in the movedAt field. Therefore, the lifecycle of a CRDTElement is as follows.

Even if an element is removed, it can be revived through undo, so garbage collection should be modified to consider this.
As explained in section 3.3, we tested with the disabledGC option set in the whiteboard example.(code)

• Support Undo/Redo for object.set and object.remove operations yorkie-js-sdk#658
• Additional patched tasks
  • Bug: Add missing removedAt during Primitive deepcopy yorkie-js-sdk#692
  • We need to handle cases where reverse operations cannot be executed. In object set and remove operations, if the target of the operation has been removed by another peer, the operation cannot be executed. Therefore, when executing set and remove operations through undo/redo, we check if the element has been removed and, if so, avoid executing the operation.
    • Prevent empty ops are applied during undo/redo yorkie-js-sdk#687
  • When setting values for objects or arrays, we initially created the outer shells of objects ({}) and arrays ([]), and then individually set the inner values. As a result, multiple operations were generated, and creating reverse operations was also verbose. Therefore, we modified the set and add operations to allow for the nested values.
    • Enhance Set and Add for representing nested elements yorkie-js-sdk#691
    • Modify converter to allow setting values for object and array #687

2.4.3 [WIP] Text.Edit

Also it’s still work in progress.

• Update EditReverse operation to support undo and redo on Text.edit yorkie-js-sdk#649

To implement the reverse operation of Text.Edit, a new operation need to be defined. The new operation, Text.EditReverse , restores the deleted text from the original edit. Also it removes the inserted text from the original edit.

export class EditReverseOperation extends Operation {
  // TODO(Hyemmie): need to add more fields to support
  // the reverse operation of rich text edit.
  private deletedIDs: Array<RGATreeSplitPos>;
  private insertedIDs: Array<RGATreeSplitPos>;
  private attributes?: Map<string, string>;

This idea was inspired by [2] Weihai Yu's “Supporting String-Wise Operations and Selective Undo for Peer-to-Peer Group Editing” paper.

FYI) I tried implementing the reverse operation of Text.Edit as another Text.Edit. However, Text.Edit is defined by fromPos, toPos, and content. Therefore, if RGATreeSplit’s structure is changed by some event (e.g., sync with other peers) after Text.Edit is defined as an reverse operation, there is no guarantee that it will be modified to the desired location and with the desired content by the time the reverse operation is popped from the undoStack and executed.

export class EditOperation extends Operation {
  private fromPos: RGATreeSplitPos;
  private toPos: RGATreeSplitPos;
  private content: string;
  private attributes: Map<string, string>;
  private maxCreatedAtMapByActor?: Map<string, TimeTicket>;

3. Discussions and Issues

3.1 Insufficient Discussion about User Intent Prevention

In collaborative editing situations, preserving each user's intent is very important. The "expected behavior" of application to preserve users’ intent itself determines the direction of the feature.

Of course, preserving user intent in undo and redo behavior is still important, but it is not easy to implement. The Automerge project is reworking the undo and redo features to better reflect user intent in various edge cases, and Prof. Weihai Yu, who has written many papers on CRDT and co-editing, has also conducted research on preserving user intent in undo and redo situations.

• Roadmap to Automerge 1.0 automerge/automerge-classic#300
• automerge/automerge-classic@f374320

Here's an example from [3], which shows that user intent may not be preserved in the following case:

Example 1 The state after two insertions ins1 (with string “this is hard”) and ins2
*(“*not ”) is “this is not hard”. Undoing ins1 *results in state “*not *”. If the text
“is hard” is a single unit and the string “*not *” is part of it, then, without the text
“is hard”, the string “*not ” becomes groundless.

When a user inserts a string str into an existing unit string str0, str0 is the ground of
str. If str0 had not existed, the user would not have inserted str and the existence of str
is groundless.

In Yorkie, we need a minimum standard for preserving user intent. We haven’t even begun to discuss whether the above example is appropriate or inappropriate for Yorkie.

3.2 Unclear Definitions of ‘Reverse’ Operation

There are two(or more) ways to define a reverse operation:

1. An operation that overwrites the new operation to negate the effect of the target operation, but does not reverts the state of the internal data structure (e.g. Counter.Increase).
2. An operation that reverts the state of the internal data structure to the previous state (e.g. Text.Edit and Text.EditReverse).

Here's where things get tricky. The difficulty of implementing a reverse operation depends on which ‘reverse’ you choose for each operation. And for certain operations, it may even be impossible to implement using method 1 (For Text.Edit, I tried to overwrite the effect with a completely new Text.Edit operation like method 1, but switched to method 2 - the approach described in 2.4.3.).

Eventually, not specifying a policy and choosing different methods for each operation led to confusion.

3.3 Conflicts between Undo/Redo Implement and Current Policy: Previous Data and GC

In essence, undo and redo are "revert to a previous state" functions. Therefore, based on the current implementation direction, defining reverse operations may require information "from a previous time".

Text.EditReverse, the reverse of Text.Edit described in 2.4.3, works by clearing the removedAt of (logically) deleted nodes and adding the removedAt of newly inserted nodes. This means that the EditReverse operation only modifies the removedAt without inserting or deleting any new nodes, and the target nodes must all "necessarily exist".

In this seemingly obvious situation, a problem arises. It's a conflict with Garbage Collection. GC in traditional Yorkie physically deletes nodes that were cleared before minSyncedTicket. If an EditReverse operation referencing a node cleared by GC is held in the undo stack and then performed, it will not be able to perform properly.

For example, a user edits the text as shown below.

1. "" -> "ABCDEF" (inserts new text “ABCDEF”)
2. "ABCDEF" -> "AB1EF" (drags “CD” and inserts “1”)
3. "AB1EF" -> "A2F" (drags “B1E” and inserts “2”)

If user call undo after 3, it will erase the "2" node from "A2F" (marking it removedAt) and restore the "B", "1", and "E" nodes (removing the removedAt marking).

This is the state on the left in the figure above. If user undo once again, it will reverse operation 2 so that the “AB1EF” goes back to "ABCDEF". To do this, it needs to erase the "1" node and revive the "C" and "D" nodes. The state after this operation is shown on the right.

In the same situation, if nodes "C" and "D" were physically deleted by garbage collection, how should the Text.EditReverse operation behave? In the figure above, some nodes have been deleted by GC. In this situation, the undo operation to revert "AB1EF" to "ABCDEF" cannot be performed.

As a temporary workaround, GC was now modified to be optional.

• Add DisableGC option to document yorkie-js-sdk#644

However, this is not a fundamental solution, and there are two possible approaches we can consider:

1. Remove the need for previous temporal context when defining reverse operations.
   1. This can be considered in conjunction with method 1 mentioned in 3.2.
2. Limit the functionality of GC to account for undo and redo.: Consider elements in the undo/redo stack during garbage collection  #664
   1. The ticket information of the reverse operations in the undo and redo stack could be used as the GC's execution limit (e.g. minSyncedTicket).
   2. This may seem inefficient by reducing the scope of the GC, but we should benchmark to check how inefficient it is, as it can be over-optimized even in corner cases.

4. Future Work

4.1 Discussion for Specification

Before implementing the remaining reverse operations, we need to discuss the questions below, otherwise we will develop without direction, not knowing what the results should be for different edge cases.

• Do we want to finalize the local undo & global redo approach as a policy?
  • Yes, we have decided to implement the local undo and global redo approach. For undo, we opted for local undo since the user's intention is to undo their own edits. Undoing edits made by others might confuse them, and for the person undoing, it would be inconvenient to redo all their changes. Similarly, for redo, we chose to implement global redo, following the approach used in applications like Figma and Google Docs.

Ref: Guide on redo from Figma
We had a lot of trouble until we settled on a principle to help guide us: if you undo a lot, copy something, and redo back to the present (a common operation), the document should not change. This may seem obvious but the single-player implementation of redo means “put back what I did” which may end up overwriting what other people did next if you’re not careful. This is why in Figma an undo operation modifies redo history at the time of the undo, and likewise a redo operation modifies undo history at the time of the redo.

• Do the reverse operations need to revert exactly to the previous internal data structure state?

4.2 Implement Remaining Reverse Operations

Of the unfilled checks below, Object.Set, Object.Remove, and Text.Edit are under working.

• Basic Implementation: Introduce basic architecture to support undo and redo yorkie-js-sdk#650
  • Counter.Increase
  • Presence.Set
• Object: Support Undo/Redo for object.set and object.remove operations yorkie-js-sdk#658
  • Object.Set
  • Object.Remove
• Array
  • Array.Add: Support Undo/Redo for Array.Add and Array.Remove #691
  • 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
• Implement history.pause() and history.resume()
• Implement doc.subscribe('history', callbackFn)

5. References

[1] nbilly team, Undo/Redo we can do. (2022)
[2] Weihai Yu, Supporting String-Wise Operations and Selective Undo for Peer-to-Peer Group Editing (2014)
[3] Weihai Yu, CRDT Supporting Selective Undo for Collaborative Text Editing (2015)
[4] Leo Stewen and Martin Kleppmann, Undo and Redo Support for Replicated Registers (draft)