4 ms·

> 2) They make it possible to express invalid data. Inserting in the middle of a codepoint is an invalid operation. It’s already possible to express invalid da

> 2) They make it possible to express invalid data. Inserting in the middle of a codepoint is an invalid operation. It’s already possible to express invalid data, because the offset may be out of bounds. Please insert 'a' at offset 100 in the string "hello". This leaves only one problem for code unit offsets. But as for scalar value offsets, you’ve ignored the fact that it has precisely the same problem if you use UTF-8 or UTF-16. If you go all in on UTF-8 code units, then UTF-16 and UTF-32 systems are slower, but UTF-8 systems are fast. If you go all in on UTF-16 code units, then UTF-8 and UTF-32 systems are slower, but UTF-16 systems are fast. If you go all in on scalar values, then both UTF-8 and UTF-16 systems are slower, and only UTF-32 systems (which are very few, Python is the only one I can think of offhand) will be fast. We agree that extended grapheme clusters are unsuitable for persistent indexing, but you have failed to sell the virtues of scalar values. They just ensure things are slower for everyone instead of half the people. (Possibly a shade easier in some systems, but probably not particularly, and certainly slower.) (I’ve used more precise terminology than the parent comment: “scalar values” instead of “code points” just for clarity where UTF-16 could be involved, and “UTF-8 code units” instead of UTF-8 bytes and “UTF-16 code units” instead of UCS-2 thingies.)

jhgb 4y ago
> and only UTF-32 systems (which are very few, Python is the only one I can think of offhand) FLOSS Lisps such as SBCL (unless you use 8-bit strings) or CCL use 32-bit characters. Some Schemes such as Chez Scheme do the same thing.
josephg 4y ago
> It’s already possible to express invalid data, because the offset may be out of bounds. Please insert 'a' at offset 100 in the string "hello". Sure; but having only one way data can be invalid is strictly better than having two ways that data can be invalid. Checking for string length is needed in every case. Checking if a given byte offset is valid is only needed when you use byte offsets. Speaking of checking byte offsets - that can be a very complex check to implement efficiently! For example, if you're using javascript, how do you check if a given UTF8 byte offset in a string is valid? Can you do that faster than O(n) time? Oh, and it gets worse. During collaborative editing sessions, its often the case that you have local modifications that the remote peer didn't know about when they created their change. How do you validate an offset from a remote peer without even having a local copy of the document at that point in time? This is a really complex problem. I agree with your later point though: Converting between scalar value counts and string indexes requires conversion in every language I use. In the systems I work with, it helps that I tend to use a custom data structure for strings anyway. This is needed because splicing strings is slow - usually O(n). And that is bad when I need to replay a lot of changes. I use libraries like jumprope[1], which supports offset conversion in O(log n) time. (Fun fact: even with all of its versitility, jumprope is still only 1/3rd the size of rust's unicode-segmentation crate!) > you have failed to sell the virtues of scalar values Maybe my strongest justification is simplicity: The actual semantic data of a text document is fundamentally a list of (indivisible) scalar unicode values. We can tell because inserting in the middle of a multi-byte character would be an invalid / illegal operation. Given that, the most obvious index into a list of scalar values is an integer pointing to an index in that list. If we model a text document like that, we can reuse the same CRDT / OT algorithm for other sorts of lists too. The algorithm I have for merging changes in a list/text document for diamond types works without reference to the actual merged content (!!!). We just need to store the merged positions & lengths of old operations, and that data is weirdly tiny on disk. I could model the document as a list of UTF8 bytes. But any interleaving problems[2] in the CRDT may result in illegal documents. Using scalar unicode values instead gives the system a beautiful, clean semantic separation between the list's semantics and the (local) resulting string - which I can store in whatever form makes the most sense. All that said, it is definitely possible to make collaborative text editing system on top of UTF8 byte offsets / UTF16 code units. But having been in the collaborative editing world for over a decade, my professional opinion is that doing so is a trap for young players. The benefit is outweighed by the cost. [1] https://crates.io/crates/jumprope https://crates.io/crates/jumprope [2] Interleaving problems are real - eg see https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydra.html https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydr...

jhgb 4y ago

> and only UTF-32 systems (which are very few, Python is the only one I can think of offhand) FLOSS Lisps such as SBCL (unless you use 8-bit strings) or CCL use 32-bit characters. Some Schemes such as Chez Scheme do the same thing.

josephg 4y ago

> It’s already possible to express invalid data, because the offset may be out of bounds. Please insert 'a' at offset 100 in the string "hello". Sure; but having only one way data can be invalid is strictly better than having two ways that data can be invalid. Checking for string length is needed in every case. Checking if a given byte offset is valid is only needed when you use byte offsets. Speaking of checking byte offsets - that can be a very complex check to implement efficiently! For example, if you're using javascript, how do you check if a given UTF8 byte offset in a string is valid? Can you do that faster than O(n) time? Oh, and it gets worse. During collaborative editing sessions, its often the case that you have local modifications that the remote peer didn't know about when they created their change. How do you validate an offset from a remote peer without even having a local copy of the document at that point in time? This is a really complex problem. I agree with your later point though: Converting between scalar value counts and string indexes requires conversion in every language I use. In the systems I work with, it helps that I tend to use a custom data structure for strings anyway. This is needed because splicing strings is slow - usually O(n). And that is bad when I need to replay a lot of changes. I use libraries like jumprope[1], which supports offset conversion in O(log n) time. (Fun fact: even with all of its versitility, jumprope is still only 1/3rd the size of rust's unicode-segmentation crate!) > you have failed to sell the virtues of scalar values Maybe my strongest justification is simplicity: The actual semantic data of a text document is fundamentally a list of (indivisible) scalar unicode values. We can tell because inserting in the middle of a multi-byte character would be an invalid / illegal operation. Given that, the most obvious index into a list of scalar values is an integer pointing to an index in that list. If we model a text document like that, we can reuse the same CRDT / OT algorithm for other sorts of lists too. The algorithm I have for merging changes in a list/text document for diamond types works without reference to the actual merged content (!!!). We just need to store the merged positions & lengths of old operations, and that data is weirdly tiny on disk. I could model the document as a list of UTF8 bytes. But any interleaving problems[2] in the CRDT may result in illegal documents. Using scalar unicode values instead gives the system a beautiful, clean semantic separation between the list's semantics and the (local) resulting string - which I can store in whatever form makes the most sense. All that said, it is definitely possible to make collaborative text editing system on top of UTF8 byte offsets / UTF16 code units. But having been in the collaborative editing world for over a decade, my professional opinion is that doing so is a trap for young players. The benefit is outweighed by the cost. [1] https://crates.io/crates/jumprope https://crates.io/crates/jumprope [2] Interleaving problems are real - eg see https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydra.html https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydr...