Editor History Change Management and State Backtracking

Previously, we implemented view layer adaptation based on React to reuse the React component ecosystem and reduce development costs. Next, we need to discuss the operation management of the editor and support for backtracking, which is commonly referred to as Redo/Undo functionality. In collaborative editing scenarios, the synchronization of local and remote changes becomes more complex.

Overview

For editors, History management is an essential capability. There are typically two approaches to implementing history recording:

  1. Full Snapshot Storage: For each operation, we store the complete data snapshot in a stack. When the user triggers redo, we retrieve the complete data and apply it to the editor state. The advantage of this approach is its simplicity and minimal design requirements. However, the disadvantage is that it can easily lead to OOM (Out of Memory) when there are many operations.

  2. Change-Based Implementation: An Op is an atomic record of an operation, such as insert("1"). To undo an operation, we simply apply its inverse operation to the editor, for example delete(1). The advantage is finer granularity and lower storage pressure, while the disadvantage is the need for complex design and computation.

In local editing scenarios, implementing basic History functionality based on Op only requires operations to support the invert method. For collaborative editing scenarios, we need to focus on handling remote changes. That is, when users A and B edit the same document simultaneously, A should not undo B's operations and vice versa. This relies on transform implementation.

Furthermore, even in non-collaborative editing scenarios, we need to consider situations where we don't want to skip certain states during undo. For example, in image upload scenarios, since the upload process is asynchronous, we need to add a loading state during upload, and after the upload is complete, we need to replace the src with the official url. The initial src can be a temporary blob url.

In this process, we need the blob -> http state as an non-undoable operation, otherwise undoing would revert to the loading transient state. In this case, we can either use transform to transform this op to the initial state, or merge the operations from loading -> http into a single op.

In the following example, we first insert a temporary blob image op1, then replace it with the official http address undoable. Theoretically, without implementing the transform operation transformation for collaboration, we typically wouldn't record invert2, which allows us to directly undo to the initial state, skipping the temporary blob state.

// https://quilljs.com/playground/snow
const Delta = Quill.imports.delta;
let base = new Delta();
const op1 = new Delta().insert(" ", { src: "blob" });
const invert1 = op1.invert(base); // { delete: 1 }
base = base.compose(op1); // { insert: " ", attributes: { src: "blob" } }
const undoable = new Delta().retain(1, { src: "http" });
base = base.compose(undoable); // { insert: " ", attributes: { src: "http" } }
base = base.compose(invert1); // []

The above seems to work fine, but it's not a complete solution. In the following example, if a new op has a position offset, problems will occur. If we don't perform transform, invert1 will only execute delete, which will delete the inserted insert("1") operation instead of the actual blob state operation.

Even if we execute the transform operation, since there's no actual invert operation for inserting the character 1, the final base will retain this insertion operation. This is actually expected, just like remote Op operations - even if all local undo stacks are executed, all remote Op will remain in the draft.

// https://quilljs.com/playground/snow
const Delta = Quill.imports.delta;
let base = new Delta();
const op1 = new Delta().insert(" ", { src: "blob" });
let invert1 = op1.invert(base); // { delete: 1 }
base = base.compose(op1); // { insert: " ", attributes: { src: "blob" } }
const undoable = new Delta().insert("1").retain(1, { src: "http" });
base = base.compose(undoable); // { insert:"1" }, { insert: " ", attributes: { src: "http" } }
invert1 = undoable.transform(invert1); // { retain: 1 }, { delete: 1 }
base = base.compose(invert1); // { insert: "1" }

Undo

To implement the undo operation, we first need to place operation change records into the undo stack. Typically, we only need to listen to the ContentChange event through the event module to record each operation's changes. However, note that the recorded changes should be the inverted operations, not the original operations directly.

Here, previous is the editor data snapshot before applying the operation. This parameter's main purpose is to record the original attribute values. If a data structure design like OT-JSON is used, the original records are directly stored in the op, in which case previous is not needed. This mainly depends on the data structure design.

let inverted = changes.invert(previous);
this.undoStack.push({ delta: inverted, range: undoRange, id: idSet });

In addition, editors typically need to merge adjacent operations. Our implementation merges adjacent operations within a certain period of time, with a preset threshold of 1s. Additionally, we need to record the last selection range in the stack. Similar to the slate editor, merging is determined by checking if adjacent types are the same.

let inverted = changes.invert(previous);
let undoRange = this.currentRange;
let idSet = new Set<string>([id]);
  const timestamp = Date.now();
if (
  // If triggered within the delay time slice or during batch execution, merge with the previous record
  (this.lastRecord + this.DELAY > timestamp || this.isBatching()) &&
  this.undoStack.length > 0
) {
  const item = this.undoStack.pop();
  if (item) {
    inverted = inverted.compose(item.delta);
    undoRange = item.range;
    idSet = item.id.add(id);
  }
} 
this.undoStack.push({ delta: inverted, range: undoRange, id: idSet });

When executing the undo method specifically, we only need to pop a record from the stack and apply it to the editor. Note that we still need to use the current editor's snapshot as the previous for invert, so that the redo op can be placed into the redo stack.

const item = this.undoStack.pop();
const base = this.editor.state.toBlock();
const inverted = item.delta.invert(base);
this.redoStack.push({
  id: item.id,
  delta: inverted,
  range: this.transformRange(item.range, inverted),
});
this.lastRecord = 0;
const { HISTORY } = APPLY_SOURCE;
this.editor.state.apply(item.delta, { source: HISTORY, autoCaret: false });
this.restoreSelection(item);

Redo

redo is the opposite operation of undo, and its basic code implementation is similar to undo.

const item = this.redoStack.pop();
const base = this.editor.state.toBlock();
const inverted = item.delta.invert(base);
this.undoStack.push({
  id: item.id,
  delta: inverted,
  range: this.transformRange(item.range, inverted),
});
this.lastRecord = 0;
const { HISTORY } = APPLY_SOURCE;
this.editor.state.apply(item.delta, { source: HISTORY, autoCaret: false });
this.restoreSelection(item);

Here, transformRange transforms the range selection into the selection after inverted. For example, if the undo delta is insert("xxx") and the range index is 3, then after invert it becomes delete 3, and the range needs to be transformed to position 0.

const start = delta.transformPosition(range.start);
const end = delta.transformPosition(range.start + range.len);
return new RawRange(start, end - start);

Collaboration Basics

The History module itself needs to be designed with collaboration capabilities. As previously mentioned, for remote Op, we cannot allow clients that did not generate this Op to undo it, i.e., A should not undo B's Op. Here we need to review the basic collaboration implementation, which is the use of Delta's transform function: ob1 = transform(oa, ob).

// https://quilljs.com/playground/snow
// https://www.npmjs.com/package/quill-delta#transform
const Delta = Quill.imports.delta;
let baseA = new Delta().insert("12");
let baseB = new Delta().insert("12");
const oa = new Delta().retain(2).insert("A");
const ob = new Delta().retain(2).insert("B");
baseA = baseA.compose(oa); // [{insert:"12A"}]
baseB = baseB.compose(ob); // [{insert:"12B"}]
const ob1 = oa.transform(ob, true); // [{retain:3},{insert:"B"}]
const oa1 = ob.transform(oa); // [{retain:2},{insert:"A"}]
baseA = baseA.compose(ob1); // [{insert:"12AB"}]
baseB = baseB.compose(oa1); // [{insert:"12AB"}]

In the following example, after obtaining inverted, there are two values in the undo stack. If an undoable op is obtained at this time, such as a remote operation or an image upload completion operation, we need to transform the existing data in the stack, similar to oa1 = transform(remoteOp, a) to process all operations in the stack.

// https://www.npmjs.com/package/quill-delta#invert
// https://github.com/slab/quill/blob/main/packages/quill/src/modules/history.ts
const Delta = Quill.imports.delta;
let base = new Delta();
const op1 = new Delta().insert("1");
const op2 = new Delta().retain(1).insert("2");
let invert1 = op1.invert(base); // [{delete:1}]
base = base.compose(op1); // [{insert:"1"}]
let invert2 = op2.invert(base); // [{retain:1},{delete:1}]
base = base.compose(op2); // [{insert:"12"}]
let undoable = new Delta().retain(2).insert("3");
base = base.compose(undoable); // [{insert:"123"}]
invert2 = undoable.transform(invert2, true); // [{retain:1},{delete:1}]
invert1 = undoable.transform(invert1, true); // [{delete:1}]

The above algorithm implementation actually has a problem. Our undoable op is always in its original state, but since we assume the inverted content will actually be applied to base, the undoable also needs to be transformed. That is, we also need to solve the impact of the invert operation on undoable.

In the following example, if we don't do undoable transform, the result of invert1 would be retain: 3, delete: 1, and with the base being 00031000, the deleted character would be 3. This is clearly incorrect, but after applying the transform, it becomes retain: 4, delete: 1, which correctly deletes the 1 character.

const Delta = Quill.imports.delta;
let base = new Delta().insert("000000");
const op1 = new Delta().retain(3).insert("1");
const op2 = new Delta().retain(3).insert("2");
let invert1 = op1.invert(base); // [{retain:3},{delete:1}]
base = base.compose(op1); // [{insert:"0001000"}]
let invert2 = op2.invert(base); // [{retain: 3},{delete:1}]
base = base.compose(op2); // [{insert:"00021000"}]
let undoable = new Delta().retain(4).insert("3");
base = base.compose(undoable); // [{insert:"000231000"}]
invert2 = undoable.transform(invert2, true); // [{retain:3},{delete:1}]
undoable = invert2.transform(undoable); // [{retain:3},{insert:"3"}]
invert1 = undoable.transform(invert1, true); // [{retain:4},{delete:1}]

Therefore, after a remote operation is sent to the local, we need to transform all ops in the entire stack. The actual implementation here is to ensure that each historical operation in the stack can still be correctly applied to the document state that already contains remote changes. This is equivalent to handling the impact of remote operations on the historical operations in the local stack, allowing the local to correctly undo.

let remoteDelta = delta;
for (let i = stack.length - 1; i >= 0; i--) {
  const prevItem = stack[i];
  stack[i] = {
    id: prevItem.id,
    delta: remoteDelta.transform(prevItem.delta, true),
    range: prevItem.range && this.transformRange(prevItem.range, remoteDelta),
  };
  remoteDelta = prevItem.delta.transform(remoteDelta);
  if (!stack[i].delta.ops.length) {
    stack.splice(i, 1);
  }
}

Client-Side Changes

Local ChangeSet refers to local change handling, such as the local preview state during image upload. Before actually uploading to the server, its content attributes are temporary states. For collaboration, similar situations require special handling:

  • Client-side attributes: client-side attribute values will not be synchronized, which are the common client-side-* attributes. For client-side attribute handling, such as code block highlighting, attributes that are only processed locally will not be actually synchronized.
  • Temporary hidden blocks: Taking the image upload example above, the temporary state is an insert op rather than a client-side attribute, so it cannot be directly handled through attribute states. Therefore, we can actually synchronize the op, but synchronization to other clients is limited to data only, and it will be hidden in the view. Thus, the block is temporarily hidden.
  • Temporarily disable collaboration: If the temporary op should not be synchronized, and the final state should be merged before synchronization. The simplest approach is to disable collaboration during local processing and enable it again after the final state is determined, i.e., i(" ", {src: "blob"}) + r(1, {src: "http"}) = i(" ", {src: "http"}).
  • Local state changes: In the easysync scheduling method for collaboration, the AXY scheduling model is mentioned. You can observe the ot.js visualization tool to maintain server statelessness as much as possible and avoid complex state diagrams. If complete handling of local changes is required, Z (local queue) needs to be extended. However, since the queue content has already been applied locally, methods for moving op forward and backward in the queue need to be implemented.

In addition to collaboration, there is also the processing of the History module, which also has similar handling of local image preview and other states.

  1. Remote operations: Treat them as remote op processing, i.e., undoable operations, which is equivalent to placing them at the forefront of the snapshot. Our principle is that we cannot undo other people's op, so placing it at the forefront is equivalent to the content left in the blank draft after all operations have been undone.
  2. Merge states: Since these ops are not actually sent out, no additional scheduling is required. Therefore, compared to requiring the server to schedule collaboration, the processing here can be relatively freely merged, similar to the following form: 
    const id1 = state.apply(i(" ", { src: "blob" }));
const id2 = state.apply(r(1, { src: "http" }));
editor.history.merge(id1, id2);

Actually, for the initial case we discussed, solution 1 is not applicable. Because the prerequisite for executing this operation is to have the prerequisite for executing this operation, i.e., the above insert op. Undoing only the retain op is meaningless, and the benchmark of the operation will be deleted when executing undo. Therefore, for this case, we still need to focus our design on allowing undo stack state merging. In addition, due to the data structure design of delta, we don't need to worry about the actual order, we just need to compose.

Operation Merging

If it's just a normal History module implementation, we have basically completed the design. However, there are some special cases that require merging data in the undo stack. Let's still take image upload as an example. There will be a temporary state during upload, but now we'll change the solution and consider the transient state problem from the perspective of actively merging Op.

In this case, if ctrl+z is triggered, it will cause the upload to return to the loading state instead of undoing the insert. Therefore, it's obvious that the retain attrs op should be merged into the insert in the History module, so that undo will undo the insert instead of retain attrs.

Let's first implement the merge. Since our modules are separated, there's no way to directly communicate with the History module. We need to modify apply and write the identifier into the undo stack. However, simply removing the retain op and merging it into insert is not enough; we also need transform data processing.

const { id: id1 } = state.apply(new Delta().insert());
const { id: id2 } = state.apply(new Delta().retain());
const index1 = editor.history.stack.findIndex(it => it.id === id1);
const index2 = editor.history.stack.findIndex(it => it.id === id2);
const delta1 = editor.history.stack[index1].delta;
const delta2 = editor.history.stack[index2].delta;
const delta = delta1.compose(delta2);
editor.history.stack[index1] = { id: id1, delta };
editor.history.stack.splice(index2, 1);

Here we need to look at the specific meaning of transform. In collaboration, b'=a.t(b) means that if a and b both branch from the same draft, then b' is what b needs to transform into based on a after a has been applied. We can also understand that tf solves the impact of operation a on operation b.

The previous undoable implementation needs to process all historical undo stacks. The assumption here is that the undoable op already exists in the draft. That is, even if all ops in the undo stack have been executed, the undoable op still exists in the draft at this time. Due to this assumption, all historical data will be affected, hence the need for transformation.

Assuming we have records a, b, c at this time, with c being the top of the stack, the goal is to merge records a and c. Let's first look at c as an op. Since b may insert new content, causing the retain of a/c to be inconsistent, after inverted, the retain of c will be larger than that of a. Therefore, we need to eliminate the impact caused by b.

Let's take a specific example. Suppose our content is 132, and the text insertion order is 123. Then we can construct the relevant inverted op. Now we want to merge 4 into 2, but obviously if we directly take it out and compose, the result is incorrect. The retain value cannot match 2. Therefore, we need to transform all operations between them. Since there is only 3 between 2 and 4, we only need to handle the impact caused by 3.

const op1 = new Delta().insert("1");
const op2 = new Delta().retain(1).insert("2");
const op3 = new Delta().retain(1).insert("3");
const op4 = new Delta().retain(2).retain(1, { src: "2" });

const invert1 = new Delta().delete(1);
const invert2 = new Delta().retain(1).delete(1);
const invert3 = new Delta().retain(1).delete(1);
const invert4 = new Delta().retain(2).retain(1, { src: "1" });

invert3.transform(invert4); // [{"retain":1},{"retain":1,"attributes":{"src":"1"}}]

There's actually another question here. Think about why when processing undoable earlier, the transformation was for historical records, but here the change is for new records. Actually, we still need to process historical records, but the undoable op doesn't actually participate in our undo process at all. After processing, it disappears directly, so it doesn't need to be processed.

Let's take another example. Suppose our content is 312 and the writing order is 123. Thus, the inverted op can be inferred. At this time, if we just remove invert3 and merge it into a previous op, when we execute invert2 later, we will find that it deletes 1 instead of 2, which causes an index pointing problem.

const op1 = new Delta().insert("1");
const op2 = new Delta().retain(1).insert("2");
const op3 = new Delta().insert("3");

const invert1 = new Delta().delete(1);
const invert2 = new Delta().retain(1).delete(1);
const invert3 = new Delta().delete(1);

Therefore, the initial example only applies to the scenario of processing attrs, because the op being merged itself does not affect other ops, but this is basically the only actual scenario. It will affect the historical record index and will be affected by previously operated ops in terms of its own index, just like xxx|yyy. This situation is not common, but it will be useful in Local CS.

Therefore, we also need to apply the transformation to historical records like undoable. However, because they affect each other, should we use the transformed value of the merged op or the original value as the benchmark? After consideration, I think we should use the original value as the benchmark. After all, when they affect each other, it's the initial value.

Still using the above example, suppose our content is 312 and the writing order is 123. It should be noted that we perform the transformation assuming the new op does not exist. Therefore, we should first invert it again before transforming, which is equivalent to undoing invert3 on the current benchmark, which is op3 in the following example.

const op1 = new Delta().insert("1");
const op2 = new Delta().retain(1).insert("2");
const op3 = new Delta().insert("3");

const invert1 = new Delta().delete(1);
const invert2 = new Delta().retain(1).delete(1);
const invert3 = new Delta().delete(1);

const invert21 = op3.transform(invert2); // [{"retain":2},{"delete":1}]
const invert11 = op3.transform(invert1); // [{"retain":1},{"delete":1}]

Multi-Plugin Design

Earlier we also talked about the extensibility of Blocks design. A typical example is the canvas extension in Feishu documents. When changes are made, it's obvious that its collaboration algorithm is not OT-JSON, and only the canvas id exists during data initialization. That is, the canvas completely breaks away from the document's own data structure design. Collaboration is implemented independently rather than relying on Feishu, and data does not need to be stored in Feishu.

There are pros and cons to not storing data in Feishu at all. The advantage is obvious: Feishu documents don't need to handle related changes at all, they just need to provide sufficient extensibility. Separated module development means higher efficiency. The disadvantage is that the implementation of extensibility itself will be more complex. For example, operation transformation needs to provide extension capabilities, and multiple structure designs will also lead to larger size, requiring more careful architectural design.

Although the overall data is not in Feishu documents, when you close the canvas editing mode, you can execute Ctrl+Z to undo canvas changes. This means that historical operations exist in the document's own operation stack. Due to the inconsistent data structures and operation transformations that need to be provided by the canvas itself, the document also needs to provide extensibility here.

Through breakpoints, we can see that Feishu's extensibility is reflected through different modules. The document's own undo module is also independently registered to the editor, and the canvas is also registered to the editor through an independent module. They maintain their own undo stacks respectively, while the main module maintains a complete content stack. Therefore, in this case, the corresponding module can be independently scheduled according to the id to perform undo.

undoStack: [
  {_id: 'module1'},
  {_id: 'module2'}
]
// module1 => undoStack: [{...}]
// module2 => undoStack: [{...}]

Summary

Here, we have discussed in detail the design and implementation of the History module in the editor, mainly focusing on the implementation of Redo/Undo functionality, as well as complex processing strategies in collaborative editing scenarios, including stack structure design, operation merging, client-side changes, controlled merging, multi-plugin design, collaboration infrastructure, etc.

So far, we have implemented the design of the history module. Regarding the clipboard processing of the Core service, it has been discussed in the article "Serialization and Deserialization in Rich Text Editor Exploration". Next, we need to discuss the State module in the Core service to manage the editor state in an incremental change mode.

Daily Question

References

ON THIS PAGE