Undo IP2 and IP3 property

[TimYi]

@cricklet Undo should support IP2(operation transform an do-undo pair should be the same) and IP3(a and b are concurrent operation, a- is inverse operation of a, then a-' should be equal to a'-). Suppose two users deletes the same character b from 'abc', then undo their operations. If IP3 is not satisfied, the result should be 'abbc'. In pure text system, it's tolerable. But in some complicate system like spreadsheet collaborative editing system, it may cause serious problem. I search for ot control algorithm to support IP2 and IP3. They ether need ET function(hard to implement), or is too hard to implement, Context based control algorithm is the only algorithm only need IT function to satisfy IP2 and IP3 I know, and it saves all original operation and their context vector, and rerun all transformations if needed(I think this replaced ET function). Do you know some good control algorithm too resolve IP2 and IP3 problem?

[cricklet]

Hello!

Unfortunately, this implementation does not support IP3 -- neither does Dropbox Paper, which is what I'm using to sanity check my test cases. I just tried your test case in it and ended up with abbc :)

My intuition is that there is almost definitely a better solution for spreadsheet editing than OT. Here's a good resource on CRDTs.

Let me know what you end up using!

[TimYi]

Thank you, I did not know much about the crdt theory before, I'll have a look. We intend to use the OT algorithm to implement our spreadsheet collaborative editing, and has put some energy. It's not easy to switch to CRDT model.

[TimYi]

@cricklet Thank you for answer my question, I asked this question to many collaborative editing project, only you answered me. After reading this artical 'An Admissibility-Based Operational Transformation Framework for Collaborative Editing Systems', I find the key to resolve undo puzzles. My way is to build a fixed coordinate system, insert in this system is a insert, delete in this system is a mark delete. Associate this coordinate to real coordinate, and every operation should have both fixed coordinate and real coordinate. Fixed coordinate can resolve tie insert puzzle. Undo a delete operation will not generate a insert operation to the fixed coordinate system, but generate a mark alive operation to the fixed coordinate system. Mark alive to the same point is the same operation. It can be proved that in a one-dimensional system, IP2 is satisfied. And when IP2 is satisfied, IP3 is also satisfied(proved by this artical: Undo Any Operation at Any Time in Group Editors). A spreadsheet is a two-dimensional system, we can separate it into two one-dimensional system, give every column and row an id. Modify cell properties can be id based, so it won't be affected by any dimension. Insert column and insert row can be designed orthogonal, they can be transformed. A merge cell can be represent by a rectangle on fixed coordinate system, so that every insert and delete operation can naturally affect this merge cell correctly. Though some conflict with merge cells should be considered, as they may overlap each other, they are easy to deal with. This idea is similar to this artical: 'Consistency Maintenance Based on the Mark & Retrace ∗ Technique in Groupware Systems'