[josephg]

I'm working on a CRDT to solve this problem too[1]. How do you plan on implementing collaborative text editing on top of your event-reordering system? Off the top of my head I can't think of a way to implement text on your proposed system which would be performant and simple.

[1] https://github.com/josephg/diamond-types

[nobu-mori]

The basic prototype I have right now works like this:

The data model has this type in TypeScript:

    {
        text: string;
        cursors: {
            [userId]: {
                offset: number;
            }
        };
    }

Basically, the data model is a string of text and a set of cursors, one for each user. The cursors contain an offset into the text where each user is editing.

When a user connects, the `user-connected` event is handled by setting the cursor position for that user to offset 0. When a user presses a key, an `insert-text` event is sent. The event handler for `insert-text` looks at the user's cursor position and inserts the text at that position and increases the user's cursor. Then, the event handler looks at all the cursors. Each cursor that has an offset greater than the location of the inserted text gets incremented by the length of the inserted text. Removal works the same way, but it removes text and decrements cursor offsets instead. When a user disconnects, the `user-disconnected` event handler removes the cursor to keep the total data size bounded.

As an example, let's say the text was "cat boy" and User A has cursor offset 0 and User B has cursor offset 4. Imagine User A inserts "dog" just a moment before User B inserts "girl", e.g. User B sends `insert-text: "girl"`. The first time this event gets applied, "girl" gets inserted at offset 4. When User A's insertion of "dog" arrives, the insertion of "girl" gets undone and then "dog" is inserted. After "dog" is inserted, User B's cursor is now at offset 7. So when `insert-text: "girl"` is re-applied, "girl" gets inserted at offset 7 and the final text is the same.

One thing I like about this system is that it's very simple. My prototype is like a collaborative notepad. The logic for state updates is only 100 lines long, including a lot of boiler plate for the event handlers (each is an interface implementation).

[toomim]

What happens if User B moves his cursor to position 0 at the same time that User A types at position 0?

Depending on the order that those events arrive, and how ordering is disambiguated, it's possible that different peers could see User B's cursor at different positions.

I believe that the system you're describing is akin to an OT system, but where the "operations" to transform are the "cursor move" actions that occur simultaneously with insertions and deletions. Most OT systems, on the other hand, are trying to transform inserts and deletes against one another.

Edit: Yes, in fact this is equivalent to OT if you replace every OT insert or delete with a tuple [move cursor, ins/del] in your system.

[nobu-mori]

The case where User B navigates to cursor offset 0 as User A inserts at position 0 is actually easy because User B's cursor can just stay at 0. A harder case would be where User B moves to cursor offset X while User A removes text between (Y, Z) where 0 < Y < Z < X. How that situation gets handled is up to the application developer.

I'm not familiar with OT specifically, but the text editor I'm working on is just a proof-of-concept for the database. The database I'm building is designed to make it very easy to program very complicated multi-player scenarios, although it requires a little work to think of conflict resolution.