8 ms·

You probably don't need to validate UTF-8 strings

78 points by jakobnissen 2y ago

remram 2y ago
> In Rust, strings are always valid UTF8, and attempting to create a string with invalid UTF8 will panic at runtime: > [piece of code explicitly calling .unwrap()] You misspelled "returns an error". It might be worth considering Python, where the most central change from 2 to 3 was that strings would now be validated UTF-8. I don't understand why it gets discarded with "it was designed in the 1990's" when that change happened so recently.
- lucb1e 2y ago
  There are countries where Python 3's stable release is old enough to legally get married, and this change was being planned since 2004. It's not that recent! This is the oldest concrete plan I can quickly spot: https://github.com/python/peps/blob/b5815e3e638834e28233fc2043026707c5bf5e95/pep-3000.txt#L44 https://github.com/python/peps/blob/b5815e3e638834e28233fc20...
  - remram 2y ago
    Julia is not so different, implementation started in 2009 (I don't know how far before it was planned). Why is it new and Python 3 old? https://github.com/JuliaLang/julia/commit/a9cbc036ac62dc5ba5200416ca7b40a2f9aa59ea https://github.com/JuliaLang/julia/commit/a9cbc036ac62dc5ba5...
- mixmastamyk 2y ago
  Python strings are Unicode, not utf8, at least until encoding time. At which point they become bytes.
  - deathanatos 2y ago
    I'm going to define a "Unicode string" as Rust does: a sequence of USVs / content that can be validly represented as UTF-8. Thus, no, sadly, Python's strings are not Unicode, as they're a sequence of Unicode code points. Because of that, a_string.encode('utf-8') … can raise in Python. For example: In [1]: '\uD83D'.encode('utf-8') --------------------------------------------------------------------------- UnicodeEncodeError Traceback (most recent call last) Cell In[1], line 1 ----> 1 '\uD83D'.encode('utf-8') UnicodeEncodeError: 'utf-8' codec can't encode character '\ud83d' in position 0: surrogates not allowed (The underlying encoding of str in Python these days is either [u8], [u16], or [u32], essentially, depending on the value of the largest code point in the string. So, for some values, e.g., 'hello world', the underlying representation is UTF-8, essentially.)
    - mixmastamyk 2y ago
      Surrogate pairs are not allowed in UTF8 (only in UTF16), so this error is not surprising. It must be decoded from UTF16, then reencoded to UTF8. The in-memory representation is an implementation detail, and can be anything that works, as you described.
      - deathanatos 2y ago
        > Surrogate pairs are not allowed in UTF8 (only in UTF16), so this error is not surprising. It must be decoded from UTF16, then reencoded to UTF8. The source code here is whatever your on-disk .py file is, likely ASCII, so UTF-8. No re-encoding is required, in practice or mentally. > The in-memory representation is an implementation detail, and can be anything that works, as you described. The in memory representation is not really the issue; it's the type itself. Consider a type is a set of possible values: bool, for example, is the set {true, false}. u8 is a set containing {0, 1, … 255}, and things like strings are infinite sets. The set of values that `str` represents is not the same set as what UTF-8 can encode / is not the same set of values as a type that encodes any possible sequence of USVs. The set of all possible `str` instances in Rust != the set of all possible `str` instances in Python. Rust is pretty unique in this regard: I don't think I know of another language whose string type is a sequence of USVs. (Though I assume there is likely one out there.) It is worse, too: there's JS's string type, for example, which is a sequence of UTF-16 code units, which is different yet! So (JS string) ≠ (Python str) ≠ (Rust str)
        mixmastamyk 2y ago
        On disk source-code is not relevant. To normalize surrogate pairs for later export to UTF8, they must be decoded first: >>> '\ud83d\ude04'.encode('utf-16', 'surrogatepass').decode('utf-16') '' >>> _.encode('utf8') b'\xf0\x9f\x98\x84' (The happy face emoji was removed by HN, run line in terminal to see it.) In other words surrogate pairs are only vaild in the context of UTF16 encoded bytes and no where else. If you're adding them into your program by hand on purpose, you're either doing it wrong or specifically to raise an error for illustration purposes.
kstrauser 2y ago
> As always, immutability comes with a performance penalty: Mutating values is generally faster than creating new ones. I get what they're saying, but I'm not sure I agree with it. Mutating one specific value is faster than making a copy and then altering that. Knowing that a value can't be mutated and using that to optimize the rest of the system can be faster yet. I think it's more likely the case that allowing mutability comes with a performance penalty.
- ghusbands 2y ago
  It's easy to see that altering an entry in an array (size N) is O(1) with mutability and at least O(log N) with immutability, and that affects many algorithms. Altering any small part of a larger data structure has similar issues. In the end, many algorithms gain a factor of log N in their time complexity.
  - kstrauser 2y ago
    Right, but look at the bigger picture. Immutability removes a whole lot of order of operations concerns. That frees a smart compiler to use faster algorithms, parallelization, etc. in ways that might not be safely possible if the data might change in place. Yes, that may mean it's slower to deal with individual values. It may also mean that the resulting system can be faster than otherwise.
    - ghusbands 2y ago
      Well, language benchmarks fairly uniformly show that to be untrue in general. None of the fastest languages have forced immutability. It's not like it's a novel, untested idea.
      - sunshowers 2y ago
        I... think that's mostly because compilers haven't yet optimized for that case yet.
- bawolff 2y ago
LegionMammal978 2y ago
There is one property about UTF-8 that distinguishes it from opaque byte strings of unknown encoding: its codepoints are self-delimiting, so you can naively locate instances of a substring (and delete them, replace them, split on them, etc.) without worrying that you've grabbed something else with the same bytes as the substring. Constrast with UTF-16, where a substring might match the bytes at an odd index in the original string, corresponding to totally different characters. Identifying a substring is valid in every human language I know of, as long as the substring itself is semantically meaningful (e.g., it doesn't end in part of a grapheme cluster; though if you want to avoid breaking up words, you may also want a \b-like mechanism). So it does seem to refute the author's notion that you can do nothing with knowledge only of the encoding.
- lmm 2y ago
  > Identifying a substring is valid in every human language I know of, as long as the substring itself is semantically meaningful Nope. Searching a UTF-8 string for a byte sequence, even one that is semantically meaningful, is not a semantically meaningful operation in most human languages. E.g. searching for the byte sequence 63 61 66 C3 A9 will not find the semantically equivalent byte sequence 63 61 66 65 CC 81, and so your program will have very annoying bugs.
  - bqmjjx0kac 2y ago
    Is it possible to cheaply canonicalize UTF-8? Or is a full parse/validation unavoidable if all you need to do is a substring search? I suppose you could also generate all byte sequences that encode the desired substring and do an NFA-to-DFA trick to search in linear time.
    - remram 2y ago
      No, the normalization algorithms require big tables of which codepoints are equivalent to what codepoint.
    - asveikau 2y ago
      I think there is no cheap Unicode normalization. It's done with lookup tables.
kayodelycaon 2y ago
Personally, I prefer Ruby's behavior of explicit encoding on strings and being very cranky when invalid codepoints show up in a UTF-8 string. If you want to ignore invalid UTF-8, use String#scrub to replace heretical values with \uFFFD and life is good. :)
- adgjlsfhk1 2y ago
  life is good until you try to read a file path that is not a valid string and discover that you read the wrong file.
  - kayodelycaon 2y ago
    Definitely and that’s what ASCII-8BIT is for. You’ll get out exactly what you put in. :) Also, the “life is good” was somewhat sarcastic.
singpolyma3 2y ago
Honestly if you don't know that it's valid unicode then it's not a string at all, but a bytstring.
- tsimionescu 2y ago
  Even if you knew it was "valid Unicode", that still doesn't gain you much. There is nothing you can do with a "valid Unicode" string without any extra context that you can't do just as badly as with a byte string. And I'm putting "valid Unicode" in quotes because it's very much possible to have a string composed of well-defined Unicode code points that are nevertheless not a valid string in any meaningful sense, e.g. a string composed exclusively of LTR markers or accents.
3pm 2y ago
Good paper on UTF-8 validation performance: https://arxiv.org/pdf/2010.03090 https://arxiv.org/pdf/2010.03090 The relatively simple algorithm (lookup) can be several times faster than conventional algorithms at a common task using nothing more than the instructions available on commodity processors. It requires fewer than an instruction per input byte in the worst case.
bawolff 2y ago
In terms of actual issues - i think normalizing to NFC is much more important than validating.
camgunz 2y ago
You do have to validate UTF-8 strings: - You can't just skip stuff if you run any kind of normalization - How would you index into or split an invalid UTF-8 string? - How would you apply a regex? - What is its length? - How do you deal with other systems that do validate UTF-8 strings? Meta point: scanning a sequence of byte for invalid UTF-8 sequences is validating. The decision to skip them is just slightly different code than "raise error". It's probably also a lot slower as you have to always do this for every operation, whereas once you've validated a string you can operate on it with impunity. Love this for the hot take/big swing, but it's a whiff.
- fanf2 2y ago
  - delay validation until normalization - treat non-utf-8 bytes as bytes - regexes match bytes just fine: the article has a whole section on ripgrep’s use of bstr - another section discusses how the length of a string is not a well defined quantity - the article says you can delay validation until required
  - paulddraper 2y ago
    Regexes normally match characters, not bytes.
    - tsimionescu 2y ago
      There's nothing about regexes that makes them any better or worse at matching characters rather than bytes (or digits or any other fixed alphabet).
      - camgunz 2y ago
        You need to know about Unicode to use Unicode regexes; if you want to pass invalid UTF-8 into these engines you have to give up Unicode regex support; i.e. how would you match "\p{East Asian Width:Narrow}" on an invalid UTF-8 string?
        2y ago
creatonez 2y ago
My understanding is that Rust has designed the rest of the String API under the assumption of validity. You can't create an invalid String because the methods that operate on strings strive to be tightly optimized UTF-8 manipulation algorithms that assume the string has already been cleaned. Pack all of the actual robustness in the guarantee that you are working with UTF-8, and you can avoid unnecessary CPU cycles, which is one of the goals of systems languages. If you want to skip it, go for raw strings or CStr -- all raw byte buffers have the basic ASCII functions available, which are designed to be robust against whatever you throw at it, and it shouldn't be too hard to introduce genericity for an API to accept both strings and raw data. That being said, I'm not sure how this is actually implemented, I assume there is still some degree of robustness when running methods on strings generated using `unsafe fn from_utf8_unchecked` just by nature of UTF-8's self-synchronization, which may be what the article is pointing out. It's possible that some cleverly optimized UTF-8 algorithms don't need valid data to avoid memory issues / UB that trips the execution of the entire program, and can instead catch the error or perform a lossy transformation on the spot without incurring too much overhead.
- csande17 2y ago
  Rust's "all strings must be valid UTF-8" rule allows them to remove a bounds check in their "get the Unicode code point corresponding to a byte index in the string" function. Like, if you see a byte in the string that indicates it's the start of a 3-byte character, you don't have to worry about whether you'll have a buffer overrun when you try to read the following two bytes. As far as I know that's pretty much the only memory-safety-related benefit of that rule, and it's probably a wash since you still need to do that check at some other point in your program to safely construct a &str from non-constant string data. The impression I get from Rust people is that UTF-8 str is mostly about purity for purity's sake, and any performance improvement is at best a minor side benefit.
deleted 2y ago
[deleted]
kdheepak 2y ago
In my opinion, one argument for internally representing `String`s as UTF8 is it prevents accidentally saving a file as Latin1 or other encodings. I would like to read a file my coworker sent me in my favorite language without having to figure out what the encoding of the file is. For example, my most recent Julia project has the following line: windows1252_to_utf8(s) = decode(Vector{UInt8}(String(coalesce(s, ""))), "Windows-1252") Figuring out that I had to use Windows-1252 (and not Latin1) took a lot more time than I would have liked it to. I get that there's some ergonomic challenges around this in languages like Julia that are optimized for data analysis workflows, but imho all data analysis languages/scripts should be forced to explicitly list encodings/decodings whenever reading/writing a file or default to UTF-8.
- samatman 2y ago
  I don't understand how a language runtime is supposed to prevent your colleague from using an unexpected encoding. Next time you try to load whoops-weird-encoding.txt as utf-8, and get garbage, may I suggest `file whoops-weird-encoding.txt`? It's pretty good at guessing. There might be a Julia package which can do that as well. I haven't run into the problem so I have no need to check.
jdougan 2y ago
I wish Swift grapheme oriented strings had been in the comparison. I think he blows off the grapheme level too quickly.
- adgjlsfhk1 2y ago
  The problem with graphemes is that they are kind of meaningless for most uses since grapheme clusters can be rendered as single glyphs.
- samatman 2y ago
  Raku also has a distinctive (and a bit bizarre) string type for including graphemes. It builds a lookup table of grapheme clusters, and represents them in memory as negative i32s. My Hot Take on this is that finding grapheme clusters is important (Julia has this built in, last I checked it was a crate in Rust), but O(1) access to each grapheme is less important. Except for emoji-heavy applications, such as tend to be written for phones. So, good choice for Swift.
  - jdougan 2y ago
    Interesting. I've been noodling around with a glyph string design that sounds a bit like Raku's. I'll have to take a look at it. Thanks!
  - lizmat 2y ago
    > It builds a lookup table of grapheme clusters, and represents them in memory as negative i32s. Only for those grapheme clusters that do not have a representation in Unicode! Also, these negative i32s are really an implementation detail. > but O(1) access to each grapheme is less important Unless you want regexes to be a. correct in the unicode world, and b. be performant
    - samatman 2y ago
      > Only for those grapheme clusters that do not have a representation in Unicode! I think it's reasonable to consider a grapheme cluster composing one codepoint to be a codepoint, not a grapheme cluster. One grape is not a cluster of grapes. > Also, these negative i32s are really an implementation detail. What a coincidence! I was explicitly discussing the implementation. Oh, is this the thing where some people pretend that Raku is different from Rakudo? Fine. Pretend I said Rakudo. > Unless you want regexes to be a. correct in the unicode world, and b. be performant I work extensively on low-level pattern matching code. So I can say with considerable confidence that blowing up every string to take up four bytes per codepoint or grapheme cluster, is not the only way to make regex correct in the unicode world, nor is it necessarily the best, or even helpful. The assertion that a regex search on a blown-up and custom-tailored string is going to be more performant than performing that search on the native UTF-8 representation of the string, is hard to justify. It's seems evident to me that it would be less so, by default. Furthermore, I'm unsure how O(1) access to anything could aid regexen, since using them is O(n) by definition. I think Raku is an interesting language and that people should check it out, to be clear. That doesn't mean I agree with every choice the Rakudo implementation has made.
cafard 2y ago
"98% of web sites are encoded in UTF8" And quite a few web sites claim to be encoded in UTF8 and serve latin-1. It is best to check, or at least to specify error handling on your decoder.
- qbane 2y ago
  My guess is that the reality is "98% of websites are valid UTF-8 documents". A large portions contain only ASCIIs so they happen to be, just indistinguishable with truly UTF8 encoded ones until they break.
sunshowers 2y ago
So... the main reason to use Unicode in general, and UTF-8 specifically, is that it's the common denominator of a lot of weird stuff you'd see in the wild. For example, most Unix platforms allow filenames to be arbitrary sets of bytes, while Windows lets filenames be UCS-2 (i.e. invalid surrogates are supported). Also, both Unix and Windows have some notion of a "local encoding" (LC_ALL etc on Unix, codepages on Windows). The common denominator, the Schelling point [1], of all of these weird systems is Unicode. Without prior coordination, you can generally assume that other participants in your system would try to use Unicode, and probably with the UTF-8 encoding. Checking at the boundaries of your program that your inputs are valid Unicode/UTF-8 leads to (a) good error messages when they aren't, and (b) not having to deal with jank internally. [1] https://en.wikipedia.org/wiki/Focal_point_(game_theory) https://en.wikipedia.org/wiki/Focal_point_(game_theory)
- tsimionescu 2y ago
  Why would "the path name you entered is not valid Unicode/UTF-8" be a good error message, if the path actually exists on the system? Also, what does "jank" mean here? What do you gain by treating file names as Unicode instead of byte sequences, for the majority of programs that don't even need to display the name, except perhaps in logs? The way I see it, Unicode is only relevant for displaying strings to humans, or for taking input from humans directly. For virtually all other purposes, strings should be treated as byte sequences internally, regardless of whether they were intended to be UTF-8 or something else. For example, if you're reading a JSON document and looking for a hardcoded key, there's no reason whatsoever to represent the JSON or the key as Unicode. The key is a sequence of bytes, the JSON objects have sequences of bytes as keys. The fact that JSON usually prefers UTF-8 is of relatively little relevance.
  - sunshowers 2y ago
    > Why would "the path name you entered is not valid Unicode/UTF-8" be a good error message, if the path actually exists on the system? Some programs have to cope with arbitrary file names. (So yes, cp shouldn't require filenames to be UTF-8.) The vast majority don't. I maintain a Rust crate called camino [1], the readme for which outlines the general philosophy. The fact is that simply enforcing that the file paths you deal with are always UTF-8 greatly simplifies a lot of code. > Also, what does "jank" mean here? What do you gain by treating file names as Unicode instead of byte sequences, for the majority of programs that don't even need to display the name, except perhaps in logs? If you ever have filenames in a text file, how do you match them up with filenames on disk? If you try to support the full space of filenames that can possibly exist on a platform, there is no general, cross-platform solution for doing so. (This is known as the "makefile problem", and if you find the right wiki page you'll see a large table exploring all the possibilities and their tradeoffs.) And if you start pulling that thread, you'll unravel a very large number of problems trying to handle non-Unicode output in reality. But you can simply cut the knot by restricting filenames to Unicode, and most programs should do that. For example, I work at Oxide. Why would any of our services want any internal filenames to be anything but UTF-8 (or really ASCII)? Trying to support weird filenames is unnecessary complexity. So we just use camino. [1] https://crates.io/crates/camino/ https://crates.io/crates/camino/
zzo38computer 2y ago
I agree. Validating UTF-8 will waste processing time, as well as not work well with non-Unicode text; and (like it says in the article) often you should not actually care what character encoding (if any) it uses anyways. Furthermore, it is often useful to measure the length or split by bytes rather than Unicode code points anyways. Unicode string types are just a bad idea, I think. Byte strings are better; you can still add functions to deal with Unicode or other character codes if necessary (and/or add explicit tagging for character encoding, if that is helpful). Many programming languages though make it difficult to work with byte strings, non-Unicode strings, etc. This often causes problems, in my experience, unless you are careful. Unicode string types are a problem especially when used incorrectly, since if used in a library they can even be exposed to applications that call it even if they do not want it and even if the library doesn't or shouldn't really care. GOTO is not a problem; it is good, because it does not affect library APIs; even if a library uses it, your program does not have to use it, and vice-versa. Unicode string types do not have that kind of benefit, so they are a much more significant problem, and should be avoided when designing a programming language. (None of the above means that there is never any reason to deal with UTF-8, although usually there isn't a good one. For example, if a file in ASCII format can contain commands which are used to produce some output in a UTF-16 format, then it makes sense to treat the arguments to those commands as WTF-8 so that they can be converted to UTF-16, since WTF-8 is the "corresponding ASCII-compatible character encoding" than UTF-16. Similarly, if the output file is JIS, then using EUC-JP would be sensible.)
andrewaylett 2y ago
As a small nit, the reason Rust has pairs of types (String vs &str) is not due to mutability, but to allow references to substrings. A String is an allocated object, with a location and length. A str is a sequence of characters "somewhere", which is why you can only have references to str, never an actual str object. Cstr and Osstr are similar. You could use &[u8] instead of any of them, but the stronger types enforce some guarantees on what you'll find in the sequence.

78 points by jakobnissen 2y ago

> In Rust, strings are always valid UTF8, and attempting to create a string with invalid UTF8 will panic at runtime: > [piece of code explicitly calling .unwrap()] You misspelled "returns an error". It might be worth considering Python, where the most central change from 2 to 3 was that strings would now be validated UTF-8. I don't understand why it gets discarded with "it was designed in the 1990's" when that change happened so recently.

lucb1e 2y ago
There are countries where Python 3's stable release is old enough to legally get married, and this change was being planned since 2004. It's not that recent! This is the oldest concrete plan I can quickly spot: https://github.com/python/peps/blob/b5815e3e638834e28233fc2043026707c5bf5e95/pep-3000.txt#L44 https://github.com/python/peps/blob/b5815e3e638834e28233fc20...
- remram 2y ago
  Julia is not so different, implementation started in 2009 (I don't know how far before it was planned). Why is it new and Python 3 old? https://github.com/JuliaLang/julia/commit/a9cbc036ac62dc5ba5200416ca7b40a2f9aa59ea https://github.com/JuliaLang/julia/commit/a9cbc036ac62dc5ba5...
mixmastamyk 2y ago
Python strings are Unicode, not utf8, at least until encoding time. At which point they become bytes.
- deathanatos 2y ago
  I'm going to define a "Unicode string" as Rust does: a sequence of USVs / content that can be validly represented as UTF-8. Thus, no, sadly, Python's strings are not Unicode, as they're a sequence of Unicode code points. Because of that, a_string.encode('utf-8') … can raise in Python. For example: In [1]: '\uD83D'.encode('utf-8') --------------------------------------------------------------------------- UnicodeEncodeError Traceback (most recent call last) Cell In[1], line 1 ----> 1 '\uD83D'.encode('utf-8') UnicodeEncodeError: 'utf-8' codec can't encode character '\ud83d' in position 0: surrogates not allowed (The underlying encoding of str in Python these days is either [u8], [u16], or [u32], essentially, depending on the value of the largest code point in the string. So, for some values, e.g., 'hello world', the underlying representation is UTF-8, essentially.)
  - mixmastamyk 2y ago
    Surrogate pairs are not allowed in UTF8 (only in UTF16), so this error is not surprising. It must be decoded from UTF16, then reencoded to UTF8. The in-memory representation is an implementation detail, and can be anything that works, as you described.
    - deathanatos 2y ago
      > Surrogate pairs are not allowed in UTF8 (only in UTF16), so this error is not surprising. It must be decoded from UTF16, then reencoded to UTF8. The source code here is whatever your on-disk .py file is, likely ASCII, so UTF-8. No re-encoding is required, in practice or mentally. > The in-memory representation is an implementation detail, and can be anything that works, as you described. The in memory representation is not really the issue; it's the type itself. Consider a type is a set of possible values: bool, for example, is the set {true, false}. u8 is a set containing {0, 1, … 255}, and things like strings are infinite sets. The set of values that `str` represents is not the same set as what UTF-8 can encode / is not the same set of values as a type that encodes any possible sequence of USVs. The set of all possible `str` instances in Rust != the set of all possible `str` instances in Python. Rust is pretty unique in this regard: I don't think I know of another language whose string type is a sequence of USVs. (Though I assume there is likely one out there.) It is worse, too: there's JS's string type, for example, which is a sequence of UTF-16 code units, which is different yet! So (JS string) ≠ (Python str) ≠ (Rust str)
      - mixmastamyk 2y ago
        On disk source-code is not relevant. To normalize surrogate pairs for later export to UTF8, they must be decoded first: >>> '\ud83d\ude04'.encode('utf-16', 'surrogatepass').decode('utf-16') '' >>> _.encode('utf8') b'\xf0\x9f\x98\x84' (The happy face emoji was removed by HN, run line in terminal to see it.) In other words surrogate pairs are only vaild in the context of UTF16 encoded bytes and no where else. If you're adding them into your program by hand on purpose, you're either doing it wrong or specifically to raise an error for illustration purposes.

kstrauser 2y ago

> As always, immutability comes with a performance penalty: Mutating values is generally faster than creating new ones. I get what they're saying, but I'm not sure I agree with it. Mutating one specific value is faster than making a copy and then altering that. Knowing that a value can't be mutated and using that to optimize the rest of the system can be faster yet. I think it's more likely the case that allowing mutability comes with a performance penalty.

ghusbands 2y ago
It's easy to see that altering an entry in an array (size N) is O(1) with mutability and at least O(log N) with immutability, and that affects many algorithms. Altering any small part of a larger data structure has similar issues. In the end, many algorithms gain a factor of log N in their time complexity.
- kstrauser 2y ago
  Right, but look at the bigger picture. Immutability removes a whole lot of order of operations concerns. That frees a smart compiler to use faster algorithms, parallelization, etc. in ways that might not be safely possible if the data might change in place. Yes, that may mean it's slower to deal with individual values. It may also mean that the resulting system can be faster than otherwise.
  - ghusbands 2y ago
    Well, language benchmarks fairly uniformly show that to be untrue in general. None of the fastest languages have forced immutability. It's not like it's a novel, untested idea.
    - sunshowers 2y ago
      I... think that's mostly because compilers haven't yet optimized for that case yet.
bawolff 2y ago

LegionMammal978 2y ago

There is one property about UTF-8 that distinguishes it from opaque byte strings of unknown encoding: its codepoints are self-delimiting, so you can naively locate instances of a substring (and delete them, replace them, split on them, etc.) without worrying that you've grabbed something else with the same bytes as the substring. Constrast with UTF-16, where a substring might match the bytes at an odd index in the original string, corresponding to totally different characters. Identifying a substring is valid in every human language I know of, as long as the substring itself is semantically meaningful (e.g., it doesn't end in part of a grapheme cluster; though if you want to avoid breaking up words, you may also want a \b-like mechanism). So it does seem to refute the author's notion that you can do nothing with knowledge only of the encoding.

lmm 2y ago
> Identifying a substring is valid in every human language I know of, as long as the substring itself is semantically meaningful Nope. Searching a UTF-8 string for a byte sequence, even one that is semantically meaningful, is not a semantically meaningful operation in most human languages. E.g. searching for the byte sequence 63 61 66 C3 A9 will not find the semantically equivalent byte sequence 63 61 66 65 CC 81, and so your program will have very annoying bugs.
- bqmjjx0kac 2y ago
  Is it possible to cheaply canonicalize UTF-8? Or is a full parse/validation unavoidable if all you need to do is a substring search? I suppose you could also generate all byte sequences that encode the desired substring and do an NFA-to-DFA trick to search in linear time.
  - remram 2y ago
    No, the normalization algorithms require big tables of which codepoints are equivalent to what codepoint.
  - asveikau 2y ago
    I think there is no cheap Unicode normalization. It's done with lookup tables.

kayodelycaon 2y ago

Personally, I prefer Ruby's behavior of explicit encoding on strings and being very cranky when invalid codepoints show up in a UTF-8 string. If you want to ignore invalid UTF-8, use String#scrub to replace heretical values with \uFFFD and life is good. :)

adgjlsfhk1 2y ago
life is good until you try to read a file path that is not a valid string and discover that you read the wrong file.
- kayodelycaon 2y ago
  Definitely and that’s what ASCII-8BIT is for. You’ll get out exactly what you put in. :) Also, the “life is good” was somewhat sarcastic.

singpolyma3 2y ago

Honestly if you don't know that it's valid unicode then it's not a string at all, but a bytstring.

tsimionescu 2y ago
Even if you knew it was "valid Unicode", that still doesn't gain you much. There is nothing you can do with a "valid Unicode" string without any extra context that you can't do just as badly as with a byte string. And I'm putting "valid Unicode" in quotes because it's very much possible to have a string composed of well-defined Unicode code points that are nevertheless not a valid string in any meaningful sense, e.g. a string composed exclusively of LTR markers or accents.

3pm 2y ago

Good paper on UTF-8 validation performance: https://arxiv.org/pdf/2010.03090 https://arxiv.org/pdf/2010.03090 The relatively simple algorithm (lookup) can be several times faster than conventional algorithms at a common task using nothing more than the instructions available on commodity processors. It requires fewer than an instruction per input byte in the worst case.

bawolff 2y ago

In terms of actual issues - i think normalizing to NFC is much more important than validating.

camgunz 2y ago

You do have to validate UTF-8 strings: - You can't just skip stuff if you run any kind of normalization - How would you index into or split an invalid UTF-8 string? - How would you apply a regex? - What is its length? - How do you deal with other systems that do validate UTF-8 strings? Meta point: scanning a sequence of byte for invalid UTF-8 sequences is validating. The decision to skip them is just slightly different code than "raise error". It's probably also a lot slower as you have to always do this for every operation, whereas once you've validated a string you can operate on it with impunity. Love this for the hot take/big swing, but it's a whiff.

fanf2 2y ago
- delay validation until normalization - treat non-utf-8 bytes as bytes - regexes match bytes just fine: the article has a whole section on ripgrep’s use of bstr - another section discusses how the length of a string is not a well defined quantity - the article says you can delay validation until required
- paulddraper 2y ago
  Regexes normally match characters, not bytes.
  - tsimionescu 2y ago
    There's nothing about regexes that makes them any better or worse at matching characters rather than bytes (or digits or any other fixed alphabet).
    - camgunz 2y ago
      You need to know about Unicode to use Unicode regexes; if you want to pass invalid UTF-8 into these engines you have to give up Unicode regex support; i.e. how would you match "\p{East Asian Width:Narrow}" on an invalid UTF-8 string?
      - 2y ago

creatonez 2y ago

My understanding is that Rust has designed the rest of the String API under the assumption of validity. You can't create an invalid String because the methods that operate on strings strive to be tightly optimized UTF-8 manipulation algorithms that assume the string has already been cleaned. Pack all of the actual robustness in the guarantee that you are working with UTF-8, and you can avoid unnecessary CPU cycles, which is one of the goals of systems languages. If you want to skip it, go for raw strings or CStr -- all raw byte buffers have the basic ASCII functions available, which are designed to be robust against whatever you throw at it, and it shouldn't be too hard to introduce genericity for an API to accept both strings and raw data. That being said, I'm not sure how this is actually implemented, I assume there is still some degree of robustness when running methods on strings generated using `unsafe fn from_utf8_unchecked` just by nature of UTF-8's self-synchronization, which may be what the article is pointing out. It's possible that some cleverly optimized UTF-8 algorithms don't need valid data to avoid memory issues / UB that trips the execution of the entire program, and can instead catch the error or perform a lossy transformation on the spot without incurring too much overhead.

csande17 2y ago
Rust's "all strings must be valid UTF-8" rule allows them to remove a bounds check in their "get the Unicode code point corresponding to a byte index in the string" function. Like, if you see a byte in the string that indicates it's the start of a 3-byte character, you don't have to worry about whether you'll have a buffer overrun when you try to read the following two bytes. As far as I know that's pretty much the only memory-safety-related benefit of that rule, and it's probably a wash since you still need to do that check at some other point in your program to safely construct a &str from non-constant string data. The impression I get from Rust people is that UTF-8 str is mostly about purity for purity's sake, and any performance improvement is at best a minor side benefit.

deleted 2y ago

[deleted]

kdheepak 2y ago

In my opinion, one argument for internally representing `String`s as UTF8 is it prevents accidentally saving a file as Latin1 or other encodings. I would like to read a file my coworker sent me in my favorite language without having to figure out what the encoding of the file is. For example, my most recent Julia project has the following line: windows1252_to_utf8(s) = decode(Vector{UInt8}(String(coalesce(s, ""))), "Windows-1252") Figuring out that I had to use Windows-1252 (and not Latin1) took a lot more time than I would have liked it to. I get that there's some ergonomic challenges around this in languages like Julia that are optimized for data analysis workflows, but imho all data analysis languages/scripts should be forced to explicitly list encodings/decodings whenever reading/writing a file or default to UTF-8.

samatman 2y ago
I don't understand how a language runtime is supposed to prevent your colleague from using an unexpected encoding. Next time you try to load whoops-weird-encoding.txt as utf-8, and get garbage, may I suggest `file whoops-weird-encoding.txt`? It's pretty good at guessing. There might be a Julia package which can do that as well. I haven't run into the problem so I have no need to check.

jdougan 2y ago

I wish Swift grapheme oriented strings had been in the comparison. I think he blows off the grapheme level too quickly.

adgjlsfhk1 2y ago
The problem with graphemes is that they are kind of meaningless for most uses since grapheme clusters can be rendered as single glyphs.
samatman 2y ago
Raku also has a distinctive (and a bit bizarre) string type for including graphemes. It builds a lookup table of grapheme clusters, and represents them in memory as negative i32s. My Hot Take on this is that finding grapheme clusters is important (Julia has this built in, last I checked it was a crate in Rust), but O(1) access to each grapheme is less important. Except for emoji-heavy applications, such as tend to be written for phones. So, good choice for Swift.
- jdougan 2y ago
  Interesting. I've been noodling around with a glyph string design that sounds a bit like Raku's. I'll have to take a look at it. Thanks!
- lizmat 2y ago
  > It builds a lookup table of grapheme clusters, and represents them in memory as negative i32s. Only for those grapheme clusters that do not have a representation in Unicode! Also, these negative i32s are really an implementation detail. > but O(1) access to each grapheme is less important Unless you want regexes to be a. correct in the unicode world, and b. be performant
  - samatman 2y ago
    > Only for those grapheme clusters that do not have a representation in Unicode! I think it's reasonable to consider a grapheme cluster composing one codepoint to be a codepoint, not a grapheme cluster. One grape is not a cluster of grapes. > Also, these negative i32s are really an implementation detail. What a coincidence! I was explicitly discussing the implementation. Oh, is this the thing where some people pretend that Raku is different from Rakudo? Fine. Pretend I said Rakudo. > Unless you want regexes to be a. correct in the unicode world, and b. be performant I work extensively on low-level pattern matching code. So I can say with considerable confidence that blowing up every string to take up four bytes per codepoint or grapheme cluster, is not the only way to make regex correct in the unicode world, nor is it necessarily the best, or even helpful. The assertion that a regex search on a blown-up and custom-tailored string is going to be more performant than performing that search on the native UTF-8 representation of the string, is hard to justify. It's seems evident to me that it would be less so, by default. Furthermore, I'm unsure how O(1) access to anything could aid regexen, since using them is O(n) by definition. I think Raku is an interesting language and that people should check it out, to be clear. That doesn't mean I agree with every choice the Rakudo implementation has made.

cafard 2y ago

"98% of web sites are encoded in UTF8" And quite a few web sites claim to be encoded in UTF8 and serve latin-1. It is best to check, or at least to specify error handling on your decoder.

qbane 2y ago
My guess is that the reality is "98% of websites are valid UTF-8 documents". A large portions contain only ASCIIs so they happen to be, just indistinguishable with truly UTF8 encoded ones until they break.

sunshowers 2y ago

So... the main reason to use Unicode in general, and UTF-8 specifically, is that it's the common denominator of a lot of weird stuff you'd see in the wild. For example, most Unix platforms allow filenames to be arbitrary sets of bytes, while Windows lets filenames be UCS-2 (i.e. invalid surrogates are supported). Also, both Unix and Windows have some notion of a "local encoding" (LC_ALL etc on Unix, codepages on Windows). The common denominator, the Schelling point [1], of all of these weird systems is Unicode. Without prior coordination, you can generally assume that other participants in your system would try to use Unicode, and probably with the UTF-8 encoding. Checking at the boundaries of your program that your inputs are valid Unicode/UTF-8 leads to (a) good error messages when they aren't, and (b) not having to deal with jank internally. [1] https://en.wikipedia.org/wiki/Focal_point_(game_theory) https://en.wikipedia.org/wiki/Focal_point_(game_theory)

tsimionescu 2y ago
Why would "the path name you entered is not valid Unicode/UTF-8" be a good error message, if the path actually exists on the system? Also, what does "jank" mean here? What do you gain by treating file names as Unicode instead of byte sequences, for the majority of programs that don't even need to display the name, except perhaps in logs? The way I see it, Unicode is only relevant for displaying strings to humans, or for taking input from humans directly. For virtually all other purposes, strings should be treated as byte sequences internally, regardless of whether they were intended to be UTF-8 or something else. For example, if you're reading a JSON document and looking for a hardcoded key, there's no reason whatsoever to represent the JSON or the key as Unicode. The key is a sequence of bytes, the JSON objects have sequences of bytes as keys. The fact that JSON usually prefers UTF-8 is of relatively little relevance.
- sunshowers 2y ago
  > Why would "the path name you entered is not valid Unicode/UTF-8" be a good error message, if the path actually exists on the system? Some programs have to cope with arbitrary file names. (So yes, cp shouldn't require filenames to be UTF-8.) The vast majority don't. I maintain a Rust crate called camino [1], the readme for which outlines the general philosophy. The fact is that simply enforcing that the file paths you deal with are always UTF-8 greatly simplifies a lot of code. > Also, what does "jank" mean here? What do you gain by treating file names as Unicode instead of byte sequences, for the majority of programs that don't even need to display the name, except perhaps in logs? If you ever have filenames in a text file, how do you match them up with filenames on disk? If you try to support the full space of filenames that can possibly exist on a platform, there is no general, cross-platform solution for doing so. (This is known as the "makefile problem", and if you find the right wiki page you'll see a large table exploring all the possibilities and their tradeoffs.) And if you start pulling that thread, you'll unravel a very large number of problems trying to handle non-Unicode output in reality. But you can simply cut the knot by restricting filenames to Unicode, and most programs should do that. For example, I work at Oxide. Why would any of our services want any internal filenames to be anything but UTF-8 (or really ASCII)? Trying to support weird filenames is unnecessary complexity. So we just use camino. [1] https://crates.io/crates/camino/ https://crates.io/crates/camino/

zzo38computer 2y ago

I agree. Validating UTF-8 will waste processing time, as well as not work well with non-Unicode text; and (like it says in the article) often you should not actually care what character encoding (if any) it uses anyways. Furthermore, it is often useful to measure the length or split by bytes rather than Unicode code points anyways. Unicode string types are just a bad idea, I think. Byte strings are better; you can still add functions to deal with Unicode or other character codes if necessary (and/or add explicit tagging for character encoding, if that is helpful). Many programming languages though make it difficult to work with byte strings, non-Unicode strings, etc. This often causes problems, in my experience, unless you are careful. Unicode string types are a problem especially when used incorrectly, since if used in a library they can even be exposed to applications that call it even if they do not want it and even if the library doesn't or shouldn't really care. GOTO is not a problem; it is good, because it does not affect library APIs; even if a library uses it, your program does not have to use it, and vice-versa. Unicode string types do not have that kind of benefit, so they are a much more significant problem, and should be avoided when designing a programming language. (None of the above means that there is never any reason to deal with UTF-8, although usually there isn't a good one. For example, if a file in ASCII format can contain commands which are used to produce some output in a UTF-16 format, then it makes sense to treat the arguments to those commands as WTF-8 so that they can be converted to UTF-16, since WTF-8 is the "corresponding ASCII-compatible character encoding" than UTF-16. Similarly, if the output file is JIS, then using EUC-JP would be sensible.)

andrewaylett 2y ago

As a small nit, the reason Rust has pairs of types (String vs &str) is not due to mutability, but to allow references to substrings. A String is an allocated object, with a location and length. A str is a sequence of characters "somewhere", which is why you can only have references to str, never an actual str object. Cstr and Osstr are similar. You could use &[u8] instead of any of them, but the stronger types enforce some guarantees on what you'll find in the sequence.