12 ms·
UTF-8 String Indexing Strategies
- cjohansson 7y agoThanks for the article, I’m curious of what the author think of string indexing in Rust. It’s also explicit so I guess you would like it as well
- the_mitsuhiko 7y agoFrom my personal experience I think Rust's string system is hard to beat at the moment. It's pretty darn good from a usability point of view and it also found a nice solution to work with UCS2 windows APIs by providing a OsStr type.
- richardwhiuk 7y agoThe only annoyance is the occasional unwrap, when something is provably impossible, but the type system can't detect it.
- 1f60c 7y agoThat’s what `unwrap` is for, though.
- chrismorgan 7y agoI’m glad that Rust strings aren’t indexable by integer, but I think that making them indexable by range (of UTF-8 code unit offsets) was an error. `foo[0..10]` should have been `foo.slice(0..10)` or similar instead.
- the_mitsuhiko 7y agoIt’s a bit of a footgun indeed but it’s quite handy in combination with the char index iterator.
- chrismorgan 7y agoSure, you do want to be able to index by code unit range, but it shouldn’t have been with the Index trait.
- zucker42 7y agoThere's no reason this couldn't be added now, though, right?
- burntsushi 7y agoAFAIK about Julia, Rust and Julia handle strings similarly. i.e., Strings are represented by UTF-8 internally, and they are required to be valid UTF-8. I've also built strings in Rust that are only conventionally UTF-8, similar to Go. It's still an experiment though: https://docs.rs/bstr https://docs.rs/bstr --- It turns out that conventionally UTF-8 strings can be quite useful in a lot of cases, since the real world often provides data without any guaranteed encoding (e.g., the contents of files).
- StefanKarpinski 7y agoJulia strings are not required to be valid Unicode since 1.0, they can hold arbitrary data. Moreover you can round trip arbitrary data from a file through strings, through chars, then back to disk and you will get an identically file regardless of its content. The principle is this: a program should never error because of broken data, only because of programmer error.
- burntsushi 7y agoOh interesting! TIL. I think that probably means that this is UB then: https://github.com/JuliaLang/julia/blob/d8ff21c69c118e8801e87841a5eb70c0489f4007/base/regex.jl#L8 https://github.com/JuliaLang/julia/blob/d8ff21c69c118e8801e8... --- You can't enable NO_UTF_CHECK in PCRE if you're going to pass data that isn't valid UTF-8. N.B. As of PCRE 10.33, you can able the PCRE2_JIT_INVALID_UTF check for JIT matching instead. It looks like this is also coming to the standard interpreter as well: https://lists.exim.org/lurker/message/20190524.173112.0d226a15.en.html https://lists.exim.org/lurker/message/20190524.173112.0d226a...
- StefanKarpinski 7y agoYeah the PCRE situation is a bit unfortunate. Avoiding crashes on invalid data would be the minimum and hopefully PCRE does that officially soon. To really make things work well, we would have to patch PCRE to handle what Julia considers invalid characters to be, which is doable, but it may be better to just reimplement regex functionality in Julia, which is non-trivial, but that way we naturally get correct treatment of invalid data, JIT, and support for other string types.
- ChrisSD 7y ago> One issue to consider is that strings typically feature random access indexing of code points True but I find it's much rarer to actually need random access to arbitrary code points. Most of the time I either use strings as opaque "things" or I'm iterating through characters to find something interesting (e.g. parsing) where I can build my own index, if and when necessary. I do agree with the article that if an abstraction is very leaky it's better to be upfront about that.
- richardwhiuk 7y agoI think that accessing characters by index is _probably_ a code smell in most places, especially if that string may contain arbitrary UTF-8.
- masklinn 7y agoAccessing string content by arbitrary indices is probably an error. Accessing string content by indices you got from previous lookups is useful for a number of situations.
- ben509 7y agoIt's usually wrong, but you have a large number of people who don't get regular expressions. It's hard to visualize an automata crawling over a string and handing out matches. The simpler mental model of splitting and splicing is easily grokable, so there's a lot of utility in supporting it.
- rwmj 7y agoIt's a good article, but it would be nice if he'd also covered the Python 3 C API anti-pattern: forcing strings to be utf-8. This means that you have latent bugs in your code. Notably when trying to treat all filenames as strings, sooner or later your code will explode when it meets someone's filesystem which has ancient Latin1 filenames. Also when dealing with unfiltered user input. (And to head off replies - yes I understand you can "just do X" where "X" is some complicated thing to avoid the bug if you remember to do "X" beforehand)
- namibj 7y agoIt's like how you can't use perl6 syntax for bencoded data (a length-prefixed/T(L)V format used in .torrent files), because the format contains some raw binary unsigned integers that make it invalid utf-8 in practice.
- raiph 7y agoAre you sure UTF8-C8[1] doesn't cover this use case? [1] https://docs.perl6.org/language/unicode#UTF8-C8 https://docs.perl6.org/language/unicode#UTF8-C8
- benj111 7y agoWhen you say 'explode' what do you mean? I can see rendering being a problem, but then if someone decided to use cuneiform in their file names I'd guess many people would have problems rendering that. Surely as long as there's internal consistency??? Now I could see a mechanism where you UTF-8 code could 'explode' latin1 only software.
- masklinn 7y ago> When you say 'explode' what do you mean? You will get runtime errors or data loss/corruption. > then if someone decided to use cuneiform in their file names I'd guess many people would have problems rendering that. Surely as long as there's internal consistency??? That's not the issue. The issue is that neither UNIX nor Windows file names are guaranteed to be valid unicode (I think OSX's are): * UNIX filenames are semi-arbitrary bags of bytes, there is no guarantee whatsoever those bags will be utf8-compatible in any way. * Windows file names are semi-arbitrary bags of UTF16 code units, meaning they can contain unpaired surrogates, meaning they can't be decoded to unicode and thus can't be transcoded to UTF8. Which means the conversion to unicode will either be partial (it will error out) or they will be lossy (the data will not round-trip). Either way, it'll cause intractable issues for the developer who will either have filesystem APIs blowing up in their face with little to no way of handling it, or the data they return will not necessarily be usable down the line.
- masklinn 7y agoIt's sad and odd that Rust and (probably especially) Swift are missing from the article.
- chrisseaton 7y agoWhy are there interesting technical differences in the way those languages do things compared to the other examples given? The author obviously can't cover all languages and strategies in a short article can they?
- saagarjha 7y agoYes: Swift groups by grapheme clusters, and Rust makes it difficult to do byte indexing.
- masklinn 7y ago> Rust makes it difficult to do byte indexing. Not sure how. If you want to get a specific byte, just convert to a bytes slice (that's free) and index that. And you can slice strings (using byte-indexed indices), but your boundaries have to fall on codepoint boundaries. The only thing that's difficult is getting a codepoint at a specific index (byte or otherwise).
- afiori 7y ago> Not sure how. If you want to get a specific byte, just convert to a slice (that's free) and index that. But then it is not automatic to cast that slice as a string.
- burntsushi 7y agoIf you want a single byte and `s` is a `&str`, then `s.as_bytes()[i]` returns a `u8` in `s` at index `i`. If the index `i` is out of bounds, then it panics, but no other UTF-8 checking is performed. You do not need to do this if you're slicing. For example, if you know that `i..j` indexes a valid UTF-8 subslice of `s`, then `&s[i..j]` returns a subslice of `s` with type `&str`. The only reason to subslice `s.as_bytes()` is if you want the raw bytes which may or may not be valid UTF-8. And in this case, it is a good thing that it is not automatic to convert that back to a `&str` since it may not be valid UTF-8.
- nabla9 7y agoIterating code points is OK, as long as you know that know that iterating code points is not the same as iterating grapheme clusters aka user perceived characters. You get away with it most of the time, but you should know you are not dealing with full Unicode and have a plan to deal with exceptions. Unicode normalization does not solve it all. Unfortunately almost all "Absolute minimum you must know about Unicode" articles don't cover the absolute minimum you have to know about Unicode. Arbitrary well formed UTF-8 combined with advanced string algorithms and data structures where the unit is 'char' requires more than code points.
- mont 7y agoDo you know any "absolute minimum you must know about Unicode" articles that do go into enough depth?
- nabla9 7y agoUnfortunately I don't. I started to learn Unicode, then realized how complicated it is to do right and stopped because I realized that nobody really cares if it works almost all the time. As Joel below demonstrates, you can get away with 29 languages by treating code points as characters and without knowing about grapheme clusters and other stuff. https://www.joelonsoftware.com/2003/10/08/the-absolute-minimum-every-software-developer-absolutely-positively-must-know-about-unicode-and-character-sets-no-excuses/ https://www.joelonsoftware.com/2003/10/08/the-absolute-minim... >When CityDesk publishes the web page, it converts it to UTF-8 encoding, which has been well supported by web browsers for many years. That’s the way all 29 language versions of Joel on Software are encoded and I have not yet heard a single person who has had any trouble viewing them.
- masklinn 7y ago> As Joel below demonstrates, you can get away with 29 languages by treating code points as characters and without knowing about grapheme clusters and other stuff. If you treat text as completely opaque it does work fine. Issues crop up when you want or need to manipulate said text, either to extract information or to modify it.
- maxdamantus 7y agoIs there any real case where code point indexing is useful? It seems like all these attempts to restrict strings in such a way to accommodate code points is just introducing complexity with no gain. UTF-8 was designed to be an encoding (of code points) on top of the "bytes" abstraction just as Unicode is designed to be an encoding (of human text) on top of the "code points" abstraction. I think it should be uncontroversial that there are very good reasons to at least handle arbitrary sequences of code points (eg, you want to be able to handle input from future versions of Unicode, and you don't know about the grapheme clustering of those code points), but I don't see a good reason not to handle arbitrary sequences of bytes. The only reason I can see is in ensuring that text is losslessly convertible to other UTFs, particularly UTF-16 (which exists for historical reasons), but this just seems like a matter of when the information is lost (is it during conversion from string to UTF-16, or from bytes to string), not if it is lost. As far as I can tell with the Python story, for example, people decided to add special "Unicode" strings into Python 2, then presumably some code used the "Unicode" strings and some code used the "byte" strings, so this situation is obviously underisable .. then in Python 3 they tried fixing it by replacing which sort of string was the default. Why would it not have been better to just improve Unicode support for the existing strings instead of splitting the type into two and forcing everyone to decide whether their strings are for "bytes" or for "Unicode"?
- dtech 7y agoProgrammers are rarely interested in individual bytes, except sometimes if a string is abused as a byte array. In all other cases iterating or indexing over characters is the intention, and code points are the proper abstraction for characters, not bytes. Also I might be wrong, but you can just look at the bytes to know how much bytes a UTF-8 character is, since the first byte with value 0 to 127 represents the final byte while 128 to 255 represents that the next byte is part of the character.
- maxdamantus 7y agoBut code points are not an abstraction for characters. The character "á" can be written as two code points (U+61, U+301). If a character can be two code points, why can't it be three bytes?
- bakery2k 7y agoThe article does not mention Python, other than to reference CPython's "Flexible String Representation". However, it's interesting that alternative Python implementations have decided against that model and indeed use UTF-8 strings internally. MicroPython saves memory by simply making indexing into its strings O(n) [1], while PyPy's UTF-8 strings have "an optional extra index data structure to make indexing O(1)" [2]. For compatibility, of course, Python implementations have to provide indexing of code points - it would be interesting to examine the pros & cons of the different string representations. I wonder if new high-level languages would be better off using one of these representations, or taking the Go/Julia approach of only indexing bytes. [1] https://github.com/micropython/micropython/blob/a4f1d82757b8e95c21a095c99b7c3f04ded88104/py/objstrunicode.c#L156 https://github.com/micropython/micropython/blob/a4f1d82757b8... [2] https://twitter.com/pypyproject/status/1095971192513708032 https://twitter.com/pypyproject/status/1095971192513708032
- raiph 7y ago"इंडेक्स" का क्या अर्थ है? [1] Including the quote marks, spaces, and question mark, that's 18 characters. This isn't just about text editing, far from it. For a lot of string processing, indexing into the underlying codepoints is even less interesting than indexing into the underlying bytes. [1] https://translate.google.com/#view=home&op=translate&sl=hi&tl=en&text=%22%E0%A4%87%E0%A4%82%E0%A4%A1%E0%A5%87%E0%A4%95%E0%A5%8D%E0%A4%B8%22%20%E0%A4%95%E0%A4%BE%20%E0%A4%95%E0%A5%8D%E0%A4%AF%E0%A4%BE%20%E0%A4%85%E0%A4%B0%E0%A5%8D%E0%A4%A5%20%E0%A4%B9%E0%A5%88%3F https://translate.google.com/#view=home&op=translate&sl=hi&t...
- onboardram 7y agoI am not a linguist, but as a native speaker, shouldn't they be considered 15 characters? क्स, क्या and र्थ each form individual conjunct consonants. Counting them as two would then beget the question as to why डे is not considered two characters too, seeing as it is formed by combining ड and ए, much like क्स is formed by combining क् and स.
- raiph 7y ago
- Someone 7y ago”So, Emacs pretends it has constant time access into its UTF-8 text data, but it’s only faking it with some simple optimizations. This usually works out just fine.” Usually, except when you’re writing in, and searching for Chinese, Greek, Hindi, Korean, Russian, Turkish, etc, text, like 50+% of the world’s population? It seems Emacs is made for programmers, who predominantly type and search for ascii text.
- appleflaxen 7y agoaccording to the article, it is independent of the language, and depends only on the number of strings you are iterating across simultaneously.
- munchbunny 7y agoThat sounds about right. You don't pick up vim for a shopping list. You pick it up because you're a programmer.
- johannes1234321 7y agoWhich doesn't mean you can't keep your shopping list in it. Or be using it to build a shopping list tool - including test data.
- anoncake 7y agoSome people use Emacs just for Org. That's a lot closer to a shopping list than to programming. And programmers sometimes write text in natural language.
- munchbunny 7y agoI would guess that the parent comment's point is still true: Emacs (and Vim) are far more commonly used for programming and other work, probably ASCII heavy, than for natural language text editing. I'd be willing to bet that for both Emacs and Vim, 90%+ characters by volume are ASCII. I wouldn't make a similar bet for Microsoft Word.
- jasonhansel 7y agoCould you store the string in multibyte form, and then keep a skip list (or other data structure) to get indexing in O(log n)?
- tracker1 7y agoIsn't it just best to do NFKC (or similar) normalization on input for indexing?
- cryptonector 7y agoThe xi rope science blog post series is, I think, the definitive answer to UTF-8 "indexing".