6 ms·

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

by 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?
    - burntsushi 2y ago
      It just doesn't match.
      - camgunz 2y ago
        Maybe! Or maybe another tool is like, "oof that's some junk in there, let's pop that out"
        burntsushi 2y ago
        I'm the author of Rust's regex engine. Treat me as an oracle. What is your specific concern? I would really strongly recommend you read my bstr blog post first though. It should answer a lot of your questions and I hope presents a nuanced data driven analysis.
        camgunz 2y ago
        > I'm the author of Rust's regex engine. Treat me as an oracle. What is your specific concern? I know and I'm terrified haha. That's a very generous offer; I don't disagree w/ your post or OP's basic premise that validation isn't absolutely necessary. I also think it's perfectly reasonable for regexes to not match on invalid bytes (what, we should just ignore stuff now? Total madness). Like, if you don't like it, consider living less dangerously and validating! My overarching worry is that a lot of engineers will read this and think, "validation is indeed for wimps" and suddenly a lot of invalid UTF-8 will end up in databases, tape backups, and S3 tripping us up for years to come. I probably could be mollified with a small title tweak like "In some cases (and you'll know if if you have one) you can intentionally not validate UTF-8 strings, but throw some salt over your shoulder first." I also think there's plenty of weird interactions like with normalization or basic string manipulation people should think about before walking down this road. > I hope presents a nuanced data driven analysis I was actually sold early on when you pointed out that filesystems are creepy attics full of exotic data; perfect use case for not assuming/forcing any kind of string encoding and a really good blueprint for applying solid engineering principles to give the people what they want.
        burntsushi 2y ago
        I think I would point to Go here as a good data point for mollification. Its `string` data is conventionally UTF-8. Go has been a huge player in web services over the last decade and a half, and I'm not sure I've seen a rise in the problem of junk data. The people behind Go were also the people behind UTF-8 (Ken Thompson and Rob Pike). Go's `string` data type is thoughtfully designed. If you iterate over the characters in a string that contains invalid UTF-8, you get replacement codepoints, just like in bstr. Go has transcoding and normalization libraries that work just fine too. I don't think there are much if any weird interactions with normalization or other such things. When you're doing Unicode operations on a conventionally UTF-8 string, you just treat invalid UTF-8 as U+FFFD. That's really all there is to it. Everything else works. Unicode algorithms are defined over codepoints. So all you need is a semantic for how to convert invalid sequences to codepoints. And Unicode (Chapter 3, Section 9) provides exactly that for you. Or in some cases, you can just leave the invalid UTF-8 as-is. The last example in bstr's docs for its "to_lowercase" routine[1], for example, demonstrates how you can perform a Unicode-aware algorithm on a string that contains invalid UTF-8. We've all been burned by mojibake before. I get it. I'm not totally discounting your viewpoint. I do tend to think that "required UTF-8" is probably the better thing for a primitive string data type. But you really do absolutely need to also then support conventional UTF-8. Otherwise you're cutting off a ton of very valid use cases, and potentially forcing others to either take a huge perf hit or to do something dangerous like `unsafe { std::str::from_utf8_unchecked(..) }`. I've seen people do the unchecked variant before just because they had a `&[u8]` but needed it to be a `&str` because they wanted to treat it as a string without doing a second pass over the data. And believe you me, you'd see a lot more of that if I wasn't so careful to provide both `&str` and `&[u8]` APIs for all string oriented operations. ;-) [1]: https://docs.rs/bstr/latest/bstr/trait.ByteSlice.html#examples-58 https://docs.rs/bstr/latest/bstr/trait.ByteSlice.html#exampl...
- samatman 2y ago
  Regex compilers know what a character is, so that "α+" doesn't match one 0xce followed by one-or-more 0xb1. Regex engines neither know nor care what a character is. They match bytes. Invalid UFT-8 is just another thing they won't match, along with all the valid sequences which also don't match.
  - camgunz 2y ago
    > Regex engines neither know nor care what a character is. They match bytes. I think this is mostly not true, for example there's some interesting behavior in POSIX-compliant engines: "Other than POSIX-compliant engines part of a POSIX-compliant system, none of the regex flavors discussed in this tutorial support collating sequences. Note that a fully POSIX-compliant regex engine treats ch as a single character when the locale is set to Czech. This means that [^x]emie also matches chemie. [^x] matches a single character that is not an x, which includes ch in the Czech POSIX locale. In any other regular expression engine, or in a POSIX engine using a locale that does not treat ch as a digraph, [^x]emie matches the misspelled word cemie but not chemie, as [^x] cannot match the two characters ch." If you were just matching bytes you wouldn't do any of this. These engines clearly know that "ch" is two characters and two bytes under some locales and 1 character and two bytes under others. Same stuff goes for the Unicode regexes: using the traditional patterns leads to unexpected results: "In Unicode, à can be encoded as two code points: U+0061 (a) followed by U+0300 (grave accent). In this situation, . applied to à will match a without the accent. ^.$ will fail to match, since the string consists of two code points. ^..$ matches à." [1]. \p{Letter} works correctly here though, again showing that these engines know about more than just bytes. [0]: https://www.regular-expressions.info/posixbrackets.html#coll https://www.regular-expressions.info/posixbrackets.html#coll [1]: https://www.regular-expressions.info/unicode.html https://www.regular-expressions.info/unicode.html
  - zzo38computer 2y ago
    The regex compiler then can have a flag to treat the regex as Unicode or non-Unicode. The regex engine then does not need to care which flag the compiler used.
sunshowers 2y ago
This world sucks to write production code in. It's sometimes necessary but it sucks.
deleted 2y ago
[deleted]
camgunz 2y ago
>> - You can't just skip stuff if you run any kind of normalization > - delay validation until normalization You probably want to normalize if you want to use them as keys in a hash table, which is pretty common. Or serialize them to JSON (or protobufs, or msgpack, etc. etc.), also pretty common. Why? Because you're commonly comparing strings and normalization lets strings that should be equal be equal. Canonicalization also requires sorting which requires normalization, etc. etc. >> - How would you index into or split an invalid UTF-8 string? > - treat non-utf-8 bytes as bytes Well I mean by code point, or grapheme. Does the invalid byte go with the 1st or the 2nd? What about multiple invalid bytes? Will all implementations agree? Also hey, looks like you scanned a string and found some invalid bytes. Looks like you validated a UTF-8 string! >> - How would you apply a regex? > - regexes match bytes just fine: the article has a whole section on ripgrep’s use of bstr They definitely don't [0]. If you're allowing invalid UTF-8 you're giving up Unicode support entirely, by necessity. >> - What is its length? > - another section discusses how the length of a string is not a well defined quantity The article doesn't say that, it says you can know neither the printed length of a Unicode string just by its contents, nor the number of characters in a Unicode string. It's right about the first, but wrong about the second: a Unicode character is represented by a Unicode code point, so their number is knowable. UTF-8 strings have a specific number of bytes and a specific number of code points and graphemes. You can know the number of bytes, code points or graphemes, but not if the string is invalid, because all bets are off. >> - How do you deal with other systems that do validate UTF-8 strings? > - the article says you can delay validation until required My general point is there are very few things you can do without validating. If you're passing them around completely internally, never normalizing, never sending to another system, never writing them into a file name or a file itself, etc. You can gain a tiny amount of speedup by not validating, but it's a huge risk and not worth it for 99% of programs. [0]: https://docs.rs/regex/1.10.4/regex/bytes/index.html#syntax https://docs.rs/regex/1.10.4/regex/bytes/index.html#syntax
- burntsushi 2y ago
  Your link to the regex crate docs doesn't support what you're saying, as far as I can tell. You can search on `&[u8]` just fine with full Unicode support. Invalid UTF-8 just won't match. > My general point is there are very few things you can do without validating. Pretty much all string processing I've built up in Rust over the past ten years is based on the idea of not validating up front. It's too costly to do. There's an entire section in my blog post on bstr about this: https://blog.burntsushi.net/bstr/#motivation-based-on-performance https://blog.burntsushi.net/bstr/#motivation-based-on-perfor... The rest of the blog may be very useful to read as well.

by fanf2 2y ago

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?
  - burntsushi 2y ago
    It just doesn't match.
    - camgunz 2y ago
      Maybe! Or maybe another tool is like, "oof that's some junk in there, let's pop that out"
      - burntsushi 2y ago
        I'm the author of Rust's regex engine. Treat me as an oracle. What is your specific concern? I would really strongly recommend you read my bstr blog post first though. It should answer a lot of your questions and I hope presents a nuanced data driven analysis.
        camgunz 2y ago
        > I'm the author of Rust's regex engine. Treat me as an oracle. What is your specific concern? I know and I'm terrified haha. That's a very generous offer; I don't disagree w/ your post or OP's basic premise that validation isn't absolutely necessary. I also think it's perfectly reasonable for regexes to not match on invalid bytes (what, we should just ignore stuff now? Total madness). Like, if you don't like it, consider living less dangerously and validating! My overarching worry is that a lot of engineers will read this and think, "validation is indeed for wimps" and suddenly a lot of invalid UTF-8 will end up in databases, tape backups, and S3 tripping us up for years to come. I probably could be mollified with a small title tweak like "In some cases (and you'll know if if you have one) you can intentionally not validate UTF-8 strings, but throw some salt over your shoulder first." I also think there's plenty of weird interactions like with normalization or basic string manipulation people should think about before walking down this road. > I hope presents a nuanced data driven analysis I was actually sold early on when you pointed out that filesystems are creepy attics full of exotic data; perfect use case for not assuming/forcing any kind of string encoding and a really good blueprint for applying solid engineering principles to give the people what they want.
        burntsushi 2y ago
        I think I would point to Go here as a good data point for mollification. Its `string` data is conventionally UTF-8. Go has been a huge player in web services over the last decade and a half, and I'm not sure I've seen a rise in the problem of junk data. The people behind Go were also the people behind UTF-8 (Ken Thompson and Rob Pike). Go's `string` data type is thoughtfully designed. If you iterate over the characters in a string that contains invalid UTF-8, you get replacement codepoints, just like in bstr. Go has transcoding and normalization libraries that work just fine too. I don't think there are much if any weird interactions with normalization or other such things. When you're doing Unicode operations on a conventionally UTF-8 string, you just treat invalid UTF-8 as U+FFFD. That's really all there is to it. Everything else works. Unicode algorithms are defined over codepoints. So all you need is a semantic for how to convert invalid sequences to codepoints. And Unicode (Chapter 3, Section 9) provides exactly that for you. Or in some cases, you can just leave the invalid UTF-8 as-is. The last example in bstr's docs for its "to_lowercase" routine[1], for example, demonstrates how you can perform a Unicode-aware algorithm on a string that contains invalid UTF-8. We've all been burned by mojibake before. I get it. I'm not totally discounting your viewpoint. I do tend to think that "required UTF-8" is probably the better thing for a primitive string data type. But you really do absolutely need to also then support conventional UTF-8. Otherwise you're cutting off a ton of very valid use cases, and potentially forcing others to either take a huge perf hit or to do something dangerous like `unsafe { std::str::from_utf8_unchecked(..) }`. I've seen people do the unchecked variant before just because they had a `&[u8]` but needed it to be a `&str` because they wanted to treat it as a string without doing a second pass over the data. And believe you me, you'd see a lot more of that if I wasn't so careful to provide both `&str` and `&[u8]` APIs for all string oriented operations. ;-) [1]: https://docs.rs/bstr/latest/bstr/trait.ByteSlice.html#examples-58 https://docs.rs/bstr/latest/bstr/trait.ByteSlice.html#exampl...
samatman 2y ago
Regex compilers know what a character is, so that "α+" doesn't match one 0xce followed by one-or-more 0xb1. Regex engines neither know nor care what a character is. They match bytes. Invalid UFT-8 is just another thing they won't match, along with all the valid sequences which also don't match.
- camgunz 2y ago
  > Regex engines neither know nor care what a character is. They match bytes. I think this is mostly not true, for example there's some interesting behavior in POSIX-compliant engines: "Other than POSIX-compliant engines part of a POSIX-compliant system, none of the regex flavors discussed in this tutorial support collating sequences. Note that a fully POSIX-compliant regex engine treats ch as a single character when the locale is set to Czech. This means that [^x]emie also matches chemie. [^x] matches a single character that is not an x, which includes ch in the Czech POSIX locale. In any other regular expression engine, or in a POSIX engine using a locale that does not treat ch as a digraph, [^x]emie matches the misspelled word cemie but not chemie, as [^x] cannot match the two characters ch." If you were just matching bytes you wouldn't do any of this. These engines clearly know that "ch" is two characters and two bytes under some locales and 1 character and two bytes under others. Same stuff goes for the Unicode regexes: using the traditional patterns leads to unexpected results: "In Unicode, à can be encoded as two code points: U+0061 (a) followed by U+0300 (grave accent). In this situation, . applied to à will match a without the accent. ^.$ will fail to match, since the string consists of two code points. ^..$ matches à." [1]. \p{Letter} works correctly here though, again showing that these engines know about more than just bytes. [0]: https://www.regular-expressions.info/posixbrackets.html#coll https://www.regular-expressions.info/posixbrackets.html#coll [1]: https://www.regular-expressions.info/unicode.html https://www.regular-expressions.info/unicode.html
- zzo38computer 2y ago
  The regex compiler then can have a flag to treat the regex as Unicode or non-Unicode. The regex engine then does not need to care which flag the compiler used.

sunshowers 2y ago

This world sucks to write production code in. It's sometimes necessary but it sucks.

deleted 2y ago

[deleted]

camgunz 2y ago

>> - You can't just skip stuff if you run any kind of normalization > - delay validation until normalization You probably want to normalize if you want to use them as keys in a hash table, which is pretty common. Or serialize them to JSON (or protobufs, or msgpack, etc. etc.), also pretty common. Why? Because you're commonly comparing strings and normalization lets strings that should be equal be equal. Canonicalization also requires sorting which requires normalization, etc. etc. >> - How would you index into or split an invalid UTF-8 string? > - treat non-utf-8 bytes as bytes Well I mean by code point, or grapheme. Does the invalid byte go with the 1st or the 2nd? What about multiple invalid bytes? Will all implementations agree? Also hey, looks like you scanned a string and found some invalid bytes. Looks like you validated a UTF-8 string! >> - How would you apply a regex? > - regexes match bytes just fine: the article has a whole section on ripgrep’s use of bstr They definitely don't [0]. If you're allowing invalid UTF-8 you're giving up Unicode support entirely, by necessity. >> - What is its length? > - another section discusses how the length of a string is not a well defined quantity The article doesn't say that, it says you can know neither the printed length of a Unicode string just by its contents, nor the number of characters in a Unicode string. It's right about the first, but wrong about the second: a Unicode character is represented by a Unicode code point, so their number is knowable. UTF-8 strings have a specific number of bytes and a specific number of code points and graphemes. You can know the number of bytes, code points or graphemes, but not if the string is invalid, because all bets are off. >> - How do you deal with other systems that do validate UTF-8 strings? > - the article says you can delay validation until required My general point is there are very few things you can do without validating. If you're passing them around completely internally, never normalizing, never sending to another system, never writing them into a file name or a file itself, etc. You can gain a tiny amount of speedup by not validating, but it's a huge risk and not worth it for 99% of programs. [0]: https://docs.rs/regex/1.10.4/regex/bytes/index.html#syntax https://docs.rs/regex/1.10.4/regex/bytes/index.html#syntax

burntsushi 2y ago
Your link to the regex crate docs doesn't support what you're saying, as far as I can tell. You can search on `&[u8]` just fine with full Unicode support. Invalid UTF-8 just won't match. > My general point is there are very few things you can do without validating. Pretty much all string processing I've built up in Rust over the past ten years is based on the idea of not validating up front. It's too costly to do. There's an entire section in my blog post on bstr about this: https://blog.burntsushi.net/bstr/#motivation-based-on-performance https://blog.burntsushi.net/bstr/#motivation-based-on-perfor... The rest of the blog may be very useful to read as well.