|
|
|
|
|
|
by practal
918 days ago
|
|
|
I've read up on CRDTs over the last two months or so (and I've come across your very helpful posts as well, of course), because I am building a collaborative editor for Practal [0]. In particular, I've invented a new simple text format for this which I call Recursive teXt (RX) [1]. The idea is to just develop a CRDT for RX. RX is naturally structured as a tree, and it seems to make sense to model a document as an A of blocks, a block as an A of lines and blocks, and a line as an A of characters. Here "A of" stands for some sort of CRDT array based on inserting via predecessor (and successor?). Each A-object (document, block, line) is referenced by its own id and stored in a purely functional tree (similar to how Redux would do it [3], and I think Automerge does it similarly). Would be great to get your opinion on this design choice, maybe you see some obvious (or not so obvious) problems with it. One problem seems to be one that Kleppmann points out in [2, end of section 4], when you press enter in the middle of a line, so that a line is split into two lines, you have to deal with that in a special way. Similarly with splitting/joining blocks. [0] https://practal.com [1] https://practal.com/recursivetext/ [2] https://martin.kleppmann.com/papers/list-move-papoc20.pdf [3] https://redux.js.org/usage/structuring-reducers/normalizing-... |
|
|
> One problem seems to be one that Kleppmann points out in [2, end of section 4], when you press enter in the middle of a line, so that a line is split into two lines, you have to deal with that in a special way. Similarly with splitting/joining blocks.
I was about to mention this problem. We ran into this with Google wave. The initial document model (based on an xml tree) used <line> tags for lines. We hit exactly this problem - if you press enter in the middle of a line while someone is concurrently editing that line, how does it handle those changes? The initial code had special split and join operations but nobody could figure out how to make split and join work correctly in an OT system.
Wave was over a decade ago now. I don’t know if anyone has solved this problem - all the working systems that I know of bailed on this approach. It’s much easier if you just make newline characters be an item that can be inserted or deleted like any other character. And then make lines be a higher order concept.
If you get this working (working = passing fuzz test suite), I’d love to hear about it. But the well trodden path of those who come before is to use newline characters instead.