Improve `undo` performance by skipping collaborative editing validation when unneccesary

[loui7]

📝 Provide a description of the improvement

At the moment in @ckeditor/ckeditor5-undo/src/basecommand.js

There is the following code:

for (const operationToUndo of operationsToUndo) {
    const nextBaseVersion = operationToUndo.baseVersion + 1;
    const historyOperations = Array.from(document.history.getOperations(nextBaseVersion));
    const transformedSets = transformSets([operationToUndo.getReversed()], historyOperations, {
        useRelations: true,
        document: this.editor.model.document,
        padWithNoOps: false,
        forceWeakRemove: true
    });
    const reversedOperations = transformedSets.operationsA;
    // After reversed operation has been transformed by all history operations, apply it.
    for (let operation of reversedOperations) {
        // Do not apply any operation on non-editable space.
        const affectedSelectable = operation.affectedSelectable;
        if (affectedSelectable && !model.canEditAt(affectedSelectable)) {
            operation = new NoOperation(operation.baseVersion);
        }
        // Before applying, add the operation to the `undoingBatch`.
        undoingBatch.addOperation(operation);
        model.applyOperation(operation);
        document.history.setOperationAsUndone(operationToUndo, operation);
    }
}

Most of which's purpose seems to be for people using collaboration features, to reconcile an undo operation and any changes made by other users since the undoing user last made a change.

I was able to considerably improve performance by creating a fork of the Undo plugin and changing it to

let latestDocumentVersion = document.version
for (const operationToUndo of operationsToUndo) {
    const operation = operationToUndo.getReversed()
    operation.baseVersion = latestDocumentVersion
    latestDocumentVersion++
    undoingBatch.addOperation(operation);
    model.applyOperation(operation);
    document.history.setOperationAsUndone(operationToUndo, operation);
}

which seems work work fine, with significantly better performance (3s vs 15s for a batch unwrapping a number of elements simultaneously).

For a fix to go into master though, I imagine it should detect whether there have been any other operations since operation we are looking to undo (or just whether they have collaborative editing enabled), and if not skip transformSets.

📃 Other details

• CKEditor version: 41.0.0

---

If you'd like to see this improvement implemented, add a 👍 reaction to this post.

[loui7]

Just realised transformSets is used for more than just collaborative editing, for example if a batch contains the following operations

1. remove element (send to graveyard at position 0)
2. insert element

and we want to undo it, undoing the insert element will send it to the graveyard at position 0, and transformSets will be needed to recognise that the previously removed element which we now want to recover will now be at position 1 in the graveyard.

Curious how many other similar cases there are like this. If it was just this one I suppose it could be solved by adding removed elements to the end of the graveyard instead of the beginning (assuming that wouldn't have other significant consequences). Curious what the team thinks.

[scofalik]

HI @loui7,

your conclusions are rather correct, especially in the second post.

The transformations are needed for RTC but it is not the only reason.

As you noticed, the problem is with how we handle removing -- by moving nodes to the graveyard. Precisely, making insertion and then removing inserted node does not bring the model to the initial state. For collaboration purposes we wanted to have the graveyard root, so that if you undo your remove, you will undo it together with other people change (that might have happened at the same time).

Another problem is that some of the other changes that happens in the editor should not be undoable, and we would like to skip them. It's a similar problem. I can see several uses of isUndoable: false in our codebase (and another several in our closed-source repo for commercial features).

At some point we also thought that maybe we will bring in selective undo feature, i.e. you would be able to see the list of very recent changes and undo a chosen one. I even created a prototype on a company hackathon back in the day but it never got traction.

If it was just this one I suppose it could be solved by adding removed elements to the end of the graveyard instead of the beginning (assuming that wouldn't have other significant consequences.

I was designing these fundamentals for the editor around 8 years ago, so excuse my memory, but I don't remember exactly why I finally opted for inserting at 0 position. I remember considering both options, and AFAIR, I concluded that it doesn't matter (for performance) and it mattered for simplicity. But I don't remember reasoning: might be that I didn't consider switching the behavior depending on whether RTC is used, but it might be also these other things I mentioned.

I put many hours trying to overcome this issue. I'd happily avoid the transformations but with the other requirements we set, at some point, we concluded we are fine with the solution and went with what we achieved. Maybe it would be possible to optimize the process and really skip some transformations if there were no removes and no non-undoable operations. I dislike such optimizations in critical places of the system, I'd rather have slower but more predictable system (unless the optimizations are really proven to be correct, and with infinite possibilities in OT space, it always seems risky).

Of course it saddens me, that the undo sometimes is very sluggish.

The problem is that when you make undo and get X operations to undo, you need to transform them by operations that should actually not matter anymore. With every undo step, the operation history grows, which means that you need to make even more operations.

Say you have operations A,B,C,D,E in the history (A is the oldest). When you undo E, you create a reverse operation (E') and you don't need to transform it, as it is last. So you have A,B,C,D,E,E'. Then, when you undo D, the reversed D' must be transformed by E and E' (because D' bases on state A+B+C+D). But intuitively, you should not need to do it. E and E' should not matter anymore, as they cancelled each other. Unfortunately, A+B+C+D != A+B+C+D+E+E'.

First problem is the remove operation. Second is the undoable operations, though. E.g. let's say that D is undoable. You have A+B+C+D+E+E'. You will need to transform C' by at least D. If remote operation comes and adds to the history right now, you'll have A+B+C+D+E+E'+R. Now you need to transform C' by D and by R for sure. But maybe it would be possible to skip E+E'?

I remember doing these analysis years ago and there was always something going wrong. I believe that the biggest problem might have been the remove operation and the graveyard.

[loui7]

@scofalik thanks for your detailed reply! I managed to work around the issue for our use case by making our own "graveyard" root and adding removed elements to the end of it (allowing us to skip the transforms). We lock ckeditor down so undoable operations are impossible and changes are limited can only happen through our plugin, so thankfully there weren't too many edge cases to test for.

Keen for a native solution in the future if there is appetite and you think it is possible though, as I imagine we'll get to a place where we want to extend our plugins functionality in ways that this workaround would make difficult.

Big fan of you and the teams work!