4 ms·

As someone who's written a lot of unicode-aware code in multiple languages, I don't agree at all. The problem I think a lot about is collaborative text editing.

As someone who's written a lot of unicode-aware code in multiple languages, I don't agree at all. The problem I think a lot about is collaborative text editing. I need to express an insert into a text document - eg, "Insert 'a' at position X". The obvious question that comes up is - how should we define "X"? There's a mess of options: - UTF-8 byte offset (from the start of the string). (Or UCS2 offset) - Extended grapheme cluster offset - Code point offset You can also use a line/column position, but the column position ends up being one of the 3 above. I want collaborative editing protocols to work across multiple programs, running on multiple systems. (Eg, a user is in a web browser on a phone, talking to a server written in rust.) This post says that codepoint offsets are Bad, but in my mind they're the only sane answer to this problem. Using byte offsets has two problems: 1) You have to pick an encoding, and thats problematic for cross-language compatibility. UTF-8 byte offsets are meaningless in javascript - they're slow & expensive to convert. UCS2 offsets are meaningless in rust. 2) They make it possible to express invalid data. Inserting in the middle of a codepoint is an invalid operation. I don't want to worry about different systems handling that case differently. Using codepoint offsets make it impossible to even represent the idea of inserting in the middle of a character. Using grapheme cluster offsets is problematic because the grapheme clustering rules change all the time. I want editing operations to be readable from any programming language, and across time. Saying "Insert 'a' at position 20" (measured in grapheme clusters) is ambiguous because "position 20" will drift as unicode's grapheme cluster rules change. The result is that old android phones and new iphones can't reliably edit a document together. And old editing traces can't be reliably replayed. Measuring codepoints is better than the other options because its stable, cross platform and well defined. If you aren't aware of those benefits, you aren't understanding my use case.

jhgb 4y ago
> I need to express an insert into a text document - eg, "Insert 'a' at position X". The obvious question that comes up is - how should we define "X"? Perhaps using a cursor/rider/however-you-call-it into whatever data structure you're using for editable sequences (since there's a bunch of them) is the preferred solution here? I'm hardly an editor expert but I thought that's how this has been being done for decades (and for some possibly useful but really complicated text representations, numerical indices for positions of operations wouldn't really work very well anyway).
- josephg 4y ago
  I hear what you're saying, but text editing operations need to be sent over the network and saved on disk. We need a stable encoding, not just an in-memory reference.
hgs3 4y ago
Yup, code points are the way to go. The LSP is a great example of what happens otherwise [1]. The LSP authors made the controversial decision to sync documents using line/columns and UTF-16 code unit offsets rather than relying on code points. I fear they dug the hole deeper by expanding the set of supported encodings to UTF-8 and 32 rather than standardizing on code points. I can only hope this is treated as a stop gap solution and a proper switch to code points happens in the next major revision. It's not immediately obvious, but line/columns are not a good synchronization method either. Unicode has their own definition of what constitutes a line terminator [2], but different programming languages and environments might have their own definition. [1] https://github.com/microsoft/language-server-protocol/issues/376 https://github.com/microsoft/language-server-protocol/issues... [2] https://en.wikipedia.org/wiki/Newline#Unicode https://en.wikipedia.org/wiki/Newline#Unicode
marcosdumay 4y ago
You have a point in that codepoints aren't useless. But I'm in agreement with the author that they are not the majoritarian concern, and so, they shouldn't be the default way to access a string. Instead, there should be enough flexibility to use them, bytes, or whatever representation you need. But the default interface should still pretty much be grapheme based.
- josephg 4y ago
  Yeah I agree that it should be possible to use any of the indexing systems depending on your needs. My criticism of grapheme cluster based indexing being the "default" is that it only really makes sense for UI code. In other situations (eg, passing JSON text over the network) it adds a lot of complexity and code size, with no benefit. If I'm writing a regex parsing system, or a JSON parser, or an event logger, or a compiler, I'll use a lot of strings. But my code probably doesn't care very much about grapheme cluster boundaries. Handling grapheme cluster boundaries is very complex code. (Rust's unicode-segmentation crate is just shy of 100kb!). When parsing grapheme boundaries isn't needed, all that code is pure overhead.
  - burntsushi 4y ago
    This is just an FYI. I don't mean to say much to your overall point, although, as someone else who has spent a lot of time doing Unicode-y things, I do tend to agree with you. I had a very similar discussion a bit ago.[1] (A quick glance at that discussion might suggest that I disagree with you, but see the last paragraph of my big comment in that thread.) Putting that aside, at least with respect to grapheme segmentation, it might be a little simpler than you think. But maybe only a little. The unicode-segmentation crate also does word segmentation, which is quite a bit more complicated than grapheme segmentation. For example, you can write a regex to parse graphemes without too much fuss[2]. (Compare that with the word segmentation regex, much to my chagrin.[3]) Once you build the regex, actually using it is basically as simple as running the regex.[4] Sadly, not all regex engines will be able to parse that regex due to its use of somewhat obscure Unicode properties. But the Rust regex crate can. :-) And of course, this somewhat shifts code size to heap size. So there's that too. But bottom line is, if you have a nice regex engine available to you, you can whip up a grapheme segmenter pretty quickly. And some regex engines even have grapheme segmentation built in via \X. [1]: https://github.com/BurntSushi/aho-corasick/issues/72 https://github.com/BurntSushi/aho-corasick/issues/72 [2]: https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30202f49d79e531d14d192/scripts/regex/grapheme.sh https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30... [3]: https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30202f49d79e531d14d192/scripts/regex/word.sh#L1 https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30... [4]: https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30202f49d79e531d14d192/src/unicode/grapheme.rs#L185-L204 https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30...
chrismorgan 4y ago
> 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...
kelnos 4y ago
Do you end up having a system that basically just observes the state of the string (in code points) before and after a user operation occurs? So for example, say a document consists of code points (made up, obviously): 1 2 3 4 5 6 This is represented in whatever platform encoding is used, but you can convert to UCS-4 for (space-wasting) simplicity, or whatever make the most sense. Then the user makes an edit, and suddenly the document looks like: 1 2 3 8 9 4 5 6 So you can say "ok, the user inserted something into the middle of the string, and we trust that the platform knows correctly that there is some sort of boundary between 3 and 4 such that an insert there is legal, and that they put something in between there, and that thing is "8 9", which might be two graphemes, or one, who knows, doesn't matter. Is that what you're talking about here? I guess I still don't completely understand how this works in a cross-platform way, though. If grapheme clustering rules change all the time, and the above was done on Windows 11, and then someone views it on an 8-year-old Android phone, can we have confidence that it will be rendered the same? Is it even possible to make that work properly?
- josephg 4y ago
  > Do you end up having a system that basically just observes the state of the string (in code points) before and after a user operation occurs? You're describing diffing, which is one way (probably the worst way) for my code to find out what edits a user made. Good editing libraries will fire editing events instead, for each change made to the document. So in this case, I'd get an event handler firing with an insert event at position 3 & with content "8 9". But yeah, you still sometimes need to reverse engineer edits by looking at the before / after strings and diffing them. We need to send that insert event over the network to other peers, and save it in a database. The question we're debating is: How should we express the edit position? Should we count the number of UTF8 bytes before the insert position ("1 2 3")? Or the number of unicode scalars? Or the number of grapheme clusters? Eg, should a Ukrainian flag have a length of 8 (utf8 bytes), a length of 2 (unicode scalars) or a length of 1 (grapheme cluster)? > If grapheme clustering rules change all the time, and the above was done on Windows 11, and then someone views it on an 8-year-old Android phone, can we have confidence that it will be rendered the same? Is it even possible to make that work properly? Nope! New unicode characters (and new grapheme clusters) are being added all the time. For example, the polar bear emoji is made up of 3 unicode scalar values - (Bear) + (Zero-width joiner) + (Snowflake). If you look at this page[1] on an 8 year old android phone, you might just see BearSnowflake instead of the emoji. The collaborative editing system can't fix the polar bear's rendering. But I want everything else to still work. I still want you to be able to delete those characters if you want, or edit anywhere else in the document correctly. I want my collaborative editing server to work with new emoji that haven't been released yet. If we count characters using grapheme clusters, imagine a document which starts with a polar bear. An old android phone might count that as having a length of 3 (since it doesn't know to join them all together). All the edits made on that android device will look wonky for everyone else, since the editing positions will appear in the wrong locations. If we count characters using the other methods, we don't have this problem. [1] https://emojipedia.org/polar-bear/ https://emojipedia.org/polar-bear/

jhgb 4y ago

> I need to express an insert into a text document - eg, "Insert 'a' at position X". The obvious question that comes up is - how should we define "X"? Perhaps using a cursor/rider/however-you-call-it into whatever data structure you're using for editable sequences (since there's a bunch of them) is the preferred solution here? I'm hardly an editor expert but I thought that's how this has been being done for decades (and for some possibly useful but really complicated text representations, numerical indices for positions of operations wouldn't really work very well anyway).

josephg 4y ago
I hear what you're saying, but text editing operations need to be sent over the network and saved on disk. We need a stable encoding, not just an in-memory reference.

hgs3 4y ago

Yup, code points are the way to go. The LSP is a great example of what happens otherwise [1]. The LSP authors made the controversial decision to sync documents using line/columns and UTF-16 code unit offsets rather than relying on code points. I fear they dug the hole deeper by expanding the set of supported encodings to UTF-8 and 32 rather than standardizing on code points. I can only hope this is treated as a stop gap solution and a proper switch to code points happens in the next major revision. It's not immediately obvious, but line/columns are not a good synchronization method either. Unicode has their own definition of what constitutes a line terminator [2], but different programming languages and environments might have their own definition. [1] https://github.com/microsoft/language-server-protocol/issues/376 https://github.com/microsoft/language-server-protocol/issues... [2] https://en.wikipedia.org/wiki/Newline#Unicode https://en.wikipedia.org/wiki/Newline#Unicode

marcosdumay 4y ago

You have a point in that codepoints aren't useless. But I'm in agreement with the author that they are not the majoritarian concern, and so, they shouldn't be the default way to access a string. Instead, there should be enough flexibility to use them, bytes, or whatever representation you need. But the default interface should still pretty much be grapheme based.

josephg 4y ago
Yeah I agree that it should be possible to use any of the indexing systems depending on your needs. My criticism of grapheme cluster based indexing being the "default" is that it only really makes sense for UI code. In other situations (eg, passing JSON text over the network) it adds a lot of complexity and code size, with no benefit. If I'm writing a regex parsing system, or a JSON parser, or an event logger, or a compiler, I'll use a lot of strings. But my code probably doesn't care very much about grapheme cluster boundaries. Handling grapheme cluster boundaries is very complex code. (Rust's unicode-segmentation crate is just shy of 100kb!). When parsing grapheme boundaries isn't needed, all that code is pure overhead.
- burntsushi 4y ago
  This is just an FYI. I don't mean to say much to your overall point, although, as someone else who has spent a lot of time doing Unicode-y things, I do tend to agree with you. I had a very similar discussion a bit ago.[1] (A quick glance at that discussion might suggest that I disagree with you, but see the last paragraph of my big comment in that thread.) Putting that aside, at least with respect to grapheme segmentation, it might be a little simpler than you think. But maybe only a little. The unicode-segmentation crate also does word segmentation, which is quite a bit more complicated than grapheme segmentation. For example, you can write a regex to parse graphemes without too much fuss[2]. (Compare that with the word segmentation regex, much to my chagrin.[3]) Once you build the regex, actually using it is basically as simple as running the regex.[4] Sadly, not all regex engines will be able to parse that regex due to its use of somewhat obscure Unicode properties. But the Rust regex crate can. :-) And of course, this somewhat shifts code size to heap size. So there's that too. But bottom line is, if you have a nice regex engine available to you, you can whip up a grapheme segmenter pretty quickly. And some regex engines even have grapheme segmentation built in via \X. [1]: https://github.com/BurntSushi/aho-corasick/issues/72 https://github.com/BurntSushi/aho-corasick/issues/72 [2]: https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30202f49d79e531d14d192/scripts/regex/grapheme.sh https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30... [3]: https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30202f49d79e531d14d192/scripts/regex/word.sh#L1 https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30... [4]: https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30202f49d79e531d14d192/src/unicode/grapheme.rs#L185-L204 https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30...

chrismorgan 4y ago

> 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...

kelnos 4y ago

Do you end up having a system that basically just observes the state of the string (in code points) before and after a user operation occurs? So for example, say a document consists of code points (made up, obviously): 1 2 3 4 5 6 This is represented in whatever platform encoding is used, but you can convert to UCS-4 for (space-wasting) simplicity, or whatever make the most sense. Then the user makes an edit, and suddenly the document looks like: 1 2 3 8 9 4 5 6 So you can say "ok, the user inserted something into the middle of the string, and we trust that the platform knows correctly that there is some sort of boundary between 3 and 4 such that an insert there is legal, and that they put something in between there, and that thing is "8 9", which might be two graphemes, or one, who knows, doesn't matter. Is that what you're talking about here? I guess I still don't completely understand how this works in a cross-platform way, though. If grapheme clustering rules change all the time, and the above was done on Windows 11, and then someone views it on an 8-year-old Android phone, can we have confidence that it will be rendered the same? Is it even possible to make that work properly?

josephg 4y ago
> Do you end up having a system that basically just observes the state of the string (in code points) before and after a user operation occurs? You're describing diffing, which is one way (probably the worst way) for my code to find out what edits a user made. Good editing libraries will fire editing events instead, for each change made to the document. So in this case, I'd get an event handler firing with an insert event at position 3 & with content "8 9". But yeah, you still sometimes need to reverse engineer edits by looking at the before / after strings and diffing them. We need to send that insert event over the network to other peers, and save it in a database. The question we're debating is: How should we express the edit position? Should we count the number of UTF8 bytes before the insert position ("1 2 3")? Or the number of unicode scalars? Or the number of grapheme clusters? Eg, should a Ukrainian flag have a length of 8 (utf8 bytes), a length of 2 (unicode scalars) or a length of 1 (grapheme cluster)? > If grapheme clustering rules change all the time, and the above was done on Windows 11, and then someone views it on an 8-year-old Android phone, can we have confidence that it will be rendered the same? Is it even possible to make that work properly? Nope! New unicode characters (and new grapheme clusters) are being added all the time. For example, the polar bear emoji is made up of 3 unicode scalar values - (Bear) + (Zero-width joiner) + (Snowflake). If you look at this page[1] on an 8 year old android phone, you might just see BearSnowflake instead of the emoji. The collaborative editing system can't fix the polar bear's rendering. But I want everything else to still work. I still want you to be able to delete those characters if you want, or edit anywhere else in the document correctly. I want my collaborative editing server to work with new emoji that haven't been released yet. If we count characters using grapheme clusters, imagine a document which starts with a polar bear. An old android phone might count that as having a length of 3 (since it doesn't know to join them all together). All the edits made on that android device will look wonky for everyone else, since the editing positions will appear in the wrong locations. If we count characters using the other methods, we don't have this problem. [1] https://emojipedia.org/polar-bear/ https://emojipedia.org/polar-bear/