OT for deltas

[pjasiun]

It should be possible to transform delta with another delta. By default it should transform all operations inside one delta with all operations inside another delta, but, for some special cases, special behavior should be provided, to bring result which user expect most.

Note that, in these special cases, two deltas should have special behavior to get the same result on both sides. This is why delta can not have special behavior with operations, because operations can not have special behavior with deltas.

Deltas and operations are two different abstraction levels and we should not mix them.

[scofalik]

Problem with transforming Delta by Operation is not even abstraction levels or pairing. Simply, a Delta may have different transformation against the same Operation when that Operation is in various Deltas.

In other word Delta x Operation may need to have various different results, depending on in which Delta that Operation is.

However other points are, of course, valid.

[pjasiun]

Maybe operations will need to be smarter to handle deltas. One idea is that move will be able to get Number.POSITIVE INFINITY as howMany parameter, what will means "from here to the end of that element children.

[pjasiun]

Related: ckeditor/ckeditor5#3464, ckeditor/ckeditor5#3473.

[scofalik]

Almost every pair of deltas has a conflicting scenario (usually one) where we would have to detect it and write a special case OT for this scenario. This means we have to define "if"s for ~30 cases. It makes our approach and work on OT almost useless. The whole idea was to create OT for basic operations and then make up deltas from them and hopefuly most deltas would not need any special treatment.

Fortunately, it appears that slight changes in basic operations OT will enable us to automatically solve most of the mentioned cases. All changes need to be done to MoveOperation:

1. Make MoveOperation "greedy". Right now, when nodes are inserted between moved range, they stay there and moved range splits into two. After changes moved range will also include inserted nodes.
2. If MoveOperation starts from 0 offset it will include all nodes from the beginning of the parent node. That was not true before. Let's say that we are Inserting 2 nodes at [ 1, 0 ] and moving 3 nodes from [ 1, 0 ]. Before, move sourcePosition would be transformed to [ 1, 2 ]. Now it will stay at [ 1, 0 ] and, combined with previous point, will move nodes inserted at [ 1, 0 ]. Note, that this behavior is only true for offset 0. Inserting at [ 1, 3 ] and moving from [ 1, 3 ] will not include inserted nodes. This change is dictated by the fact that we need a way to say that move has to move "all nodes from the beginning of parent to X" no matter of what further operations we execute. We debated -1 offset but it would complicate OT algorithms more.
3. MoveOperation will now accept Infinity as correct value for howMany parameter. In this case, MoveOperation will move all nodes from sourcePosition to the end of parent node. This is similiar to the case above but does not change anything in OT algorithms. Note that using arbitrary large number (let's say 100000) will throw error as there aren't that many nodes in the parent. We keep that validation, while Infinity is on the fly changed to a proper number when executing operation.
4. To ensure proper delta OT we also introduce some prioritizing to MoveOperations. All MoveOperations created by "special" deltas (Wrap,Unwrap,Split,Merge) have to be weaker than MoveOperations created by "basic" deltas (Move,Remove).

Applying those changes to MoveOperation will leave us with ~9 special cases to solve (most of them are really special and we first had to come up what in fact should happen, so even with perfect, ultra smart operations they could not be handled automatically).

[pjasiun]

What if moveOperation would be greedy by default? I know that it would bring worse UX, move inserted content, but I think we should give up perfect UX in exchange for less cases to handle. We would not need Infinity then and move from 1, would work the same way as move from 0. I wonder that bringing more options and cases will cause more issues to handle in the future.

[scofalik]

I also thought that we could just make MoveOperation sticky and inserting at the position equal to the start or end of move range would result in moving inserted nodes. This is easier to code and also we don't have a special case for offset 0. On the other hand it may invalid some of assumptions we made while researching OT. I don't know exactly but there might be a case that something works only because MoveOperation is not sticky. We will have to think through it again. Note, that we have to keep undo on our minds too.

[pjasiun]

I hope we have tests for these cases :)

[scofalik]

I am not afraid of simple operation vs operation transformations but operations history and undo.

[scofalik]

For now I pushed t/72 with updated move algorithms.

[scofalik]

Follow up issues ckeditor/ckeditor5-engine#183 ckeditor/ckeditor5-engine#184

[Reinmar]

Shouldn't this issue be closed?

[scofalik]

I don't think so, nothing has been merged yet. Basically this is hanging on a branch and waiting for Features to be ready.