6 ms·

> The main time you want to be able to index by code point is if you’re implementing algorithms defined in the unicode spec that operate on unicode strings (cas

by sanxiyn 10y ago

> The main time you want to be able to index by code point is if you’re implementing algorithms defined in the unicode spec that operate on unicode strings (casefolding, segmentation, NFD/NFC). Most if not all of these algorithms operate on whole strings, so implementing them as an iteration pass is usually necessary anyway, so you don’t lose anything if you can’t do arbitrary code point indexing. Another algorithm for unicode strings which wants to index by code point is unicode regular expression matching. I heard that you do lose something here if you can't assume all code points encode to same length. Unlike other algorithms you mentioned which only iterate forward, depending on implementation regex needs to backtrack. I once heard that complexity of implementing regex directly on UTF-8 is one reason why Python will not use UTF-8 internally.

Manishearth 10y ago
Hm, interesting. You still don't need arbitrary indexing for that; just the ability to iterate backwards, but I can see how it would complicate things. I wonder if it could be implemented on utf8 without affecting performance much. burntsushi's utf8-ranges library used by the Rust Regex lib probably makes this easier to deal with. I wonder how it performs in relation to the Python implementation (which I assume is in native code)
- Animats 10y ago
  UTF-8 substrings can't find a misaligned match, because of the way UTF-8 is encoded. First bytes are unambiguous. I had to write "rfind" in Rust, and here it is: fn rfind(s: &[&str], key: &str) -> Option<usize> { (0 .. s.len()).rev().find(|&i| s[i] == key) } No need to explicitly worry about rune boundaries. This, like forward find, returns a byte index into a UTF-8 string. Explicit byte indices into UTF-8 strings are troublesome.
  - Manishearth 10y ago
    > because of the way UTF-8 is encoded. Yes, I know, I mention this in my blog post :) Rust's indexing methods on strings actually do operate on byte indices. You can't do `"foo"[2]`, but you can do `"foo[2..3]"`, and it will panic if you are not on a boundary. Nobody uses this (like you say, it's troublesome) :P I've seen folks just break out the byte/char iterator whenever they need something more complicated, because usually they do need to iterate anyway. Rust internally stores slices as byte indices (well, pointer + byte length), but the compiler enforces the validity of that.
  - dbaupp 10y ago
    Incidentally, that function could be s.iter().rev().position(|ss| ss == key), or drop the `rev()` and use `.rposition(...)` if one wants indices from the start of the slice. Although I'm not sure how searching a slice of strings for a specific one is related to UTF-8: the &str's are used completely opaquely. Did you mean to be searching a &str itself?
pjscott 10y ago
Backtracking in a UTF-8 string is easy: when you need to remember a location, just record its byte offset. You have exactly the same issue in UTF-16, which is also variable-width and therefore not O(1)-indexable by code point. There are loads of regular expression engines which operate on both of these encodings, and I've never seen them go to any great pains to work around the lack of code point indexing.
- sanxiyn 10y ago
  Yes, you have exactly the same issue in UTF-16, I never said otherwise.
  - pjscott 10y ago
    I agree that you never said otherwise, and I applaud you for your accuracy in not doing so. :-D The reason I bring it up is that UTF-16 is a very commonly used internal encoding for strings, and regular expression engines for platforms which use UTF-16 internally are generally designed to work on that encoding without conversion to UTF-32. Examples that spring to mind are most JavaScript regular expression engines, the ICU regular expression engine, and java.util.regex. If variable-width encodings were so difficult to deal with then you would expect these to have run into some problems with it; however, as far as I can tell, they have not. This is evidence against variable-width encodings being difficult for regular expression engines to deal with. (Sanity check for my argument above: If you read through https://swtch.com/~rsc/regexp/regexp2.html https://swtch.com/~rsc/regexp/regexp2.html, which covers both backtracking and non-backtracking regex engines and includes code, none of the code examples would need more than trivial modification to deal with variable-width encodings.)
    - Manishearth 10y ago
      Note that JS isn't UTF-16, it's slightly different. In JS unpaired surrogates are allowed. String indexing is by code unit, so non-BMP code points are considered to be two "characters". IIRC Java also allows unpaired surrogates? But does consider non-BMP codepoints to be single characters. I think. Idk. So from JSs point of view it is a fixed-width encoding, one where all byte values are valid. `"\uD83D\uDC68".match(/\ud83d/)` works (U+D83D is a high surrogate, and "\uD83D\uDC68" is U+1F468 MAN), so the regex engine operates on code units, not code points. I think for Java the regex engine would have to deal with it as a variable-width encoding, though. Edit: Hacker News removes emoji from comments.
Animats 10y ago
If everything that can match in a regular expression is valid UTF-8, and everything the regular expression can generate is valid UTF-8, you can just run the regular expression on the byte string. This requires that matches match UTF-8 substrings, only. That's easy for explicit strings, such as "abc". For more general forms, "." must match one rune, not one byte. But that's not hard. Python's problem is that strings are random-access indexable by rune (in the Go sense). Python either needs a representation that's rune-indexable, or it needs to generate an index array for strings that need one. There's an argument for the second approach, because most loops don't need a random-access index. "for i in "abcdef: ... " does not, for example.
- pjscott 10y ago
  It's also possible to chunk the index array: to store the byte-index of every 16th rune, say, and do a bit of cheap iteration afterward. I've had good success with this approach: it's fast, it's light on memory, and it preserves constant-time indexing by code point.
- Manishearth 10y ago
  > Python's problem is that strings are random-access indexable by rune Yeah, one of my points in the blog post is that random-access rune (code point) indexing isn't very valuable. Python is stuck with it, but if anyone in the future needs to make a similar choice, I hope they don't use O(1) rune indexing as a reason unless they have a very specific use case where O(1) rune indexing actually matters. (I, for one, am very happy with the "rune" terminology, "char" is way too overloaded. It took me a minute to understand why they did that in Go when I first picked it up, but when I realized the reason I found it brilliant)
  - Animats 10y ago
    One approach for a Python implementation would be to store strings as UTF-8, and generate an index array as needed. For most operations, you don't need an index. Concatenation doesn't need one. Ordinary iteration (for c in "hello" :) doesn't need one. Regular expressions don't need an index. That covers most of the common use cases. I like "rune" as terminology. A rune is one Unicode code point. A grapheme is a sequence of runes which should not be split.
hoytech 10y ago
There are many considerations of course and I might not have fully grasped your point, but in reference to your last paragraph: By default RE2 matches directly against the UTF-8 encoding, see this neat state diagram: https://swtch.com/~rsc/regexp/regexp3.html#step3 https://swtch.com/~rsc/regexp/regexp3.html#step3 In terms of backtracing engines, perl also stores strings internally as UTF-8 (on most platforms) and its regexp engine runs directly on them. It can also match "eXtended grapheme clusters" with \X.
burntsushi 10y ago
> Another algorithm for unicode strings which wants to index by code point is unicode regular expression matching. Why? This is certainly not a requirement for at least some levels of Unicode support. > I once heard that complexity of implementing regex directly on UTF-8 is one reason why Python will not use UTF-8 internally. It's really not that bad. Both RE2 and Rust's regex engine operate on UTF-8 directly, and this is one of the reasons why these engines are fast. If your automaton is byte based, then you can do a lot of nice tricks in your DFA implementation. (In fact, it's a critical reason why ripgrep doesn't slow down when handling Unicode features, unlike GNU grep.) For Rust at least, the trickier parts of generating the UTF-8 automaton are available for reuse in the utf8-ranges crate: https://docs.rs/utf8-ranges/1.0.0/utf8_ranges/ https://docs.rs/utf8-ranges/1.0.0/utf8_ranges/ (Which is used in at least two regex implementations I've written.) I'd say the complexity claim might be coming from some other component of the implementation, or something more related to how Python strings are generally represented, rather than it being a fundamental complexity of building a regex engine on UTF-8 directly.

by sanxiyn 10y ago

Manishearth 10y ago

Hm, interesting. You still don't need arbitrary indexing for that; just the ability to iterate backwards, but I can see how it would complicate things. I wonder if it could be implemented on utf8 without affecting performance much. burntsushi's utf8-ranges library used by the Rust Regex lib probably makes this easier to deal with. I wonder how it performs in relation to the Python implementation (which I assume is in native code)

Animats 10y ago
UTF-8 substrings can't find a misaligned match, because of the way UTF-8 is encoded. First bytes are unambiguous. I had to write "rfind" in Rust, and here it is: fn rfind(s: &[&str], key: &str) -> Option<usize> { (0 .. s.len()).rev().find(|&i| s[i] == key) } No need to explicitly worry about rune boundaries. This, like forward find, returns a byte index into a UTF-8 string. Explicit byte indices into UTF-8 strings are troublesome.
- Manishearth 10y ago
  > because of the way UTF-8 is encoded. Yes, I know, I mention this in my blog post :) Rust's indexing methods on strings actually do operate on byte indices. You can't do `"foo"[2]`, but you can do `"foo[2..3]"`, and it will panic if you are not on a boundary. Nobody uses this (like you say, it's troublesome) :P I've seen folks just break out the byte/char iterator whenever they need something more complicated, because usually they do need to iterate anyway. Rust internally stores slices as byte indices (well, pointer + byte length), but the compiler enforces the validity of that.
- dbaupp 10y ago
  Incidentally, that function could be s.iter().rev().position(|ss| ss == key), or drop the `rev()` and use `.rposition(...)` if one wants indices from the start of the slice. Although I'm not sure how searching a slice of strings for a specific one is related to UTF-8: the &str's are used completely opaquely. Did you mean to be searching a &str itself?

pjscott 10y ago

Backtracking in a UTF-8 string is easy: when you need to remember a location, just record its byte offset. You have exactly the same issue in UTF-16, which is also variable-width and therefore not O(1)-indexable by code point. There are loads of regular expression engines which operate on both of these encodings, and I've never seen them go to any great pains to work around the lack of code point indexing.

sanxiyn 10y ago
Yes, you have exactly the same issue in UTF-16, I never said otherwise.
- pjscott 10y ago
  I agree that you never said otherwise, and I applaud you for your accuracy in not doing so. :-D The reason I bring it up is that UTF-16 is a very commonly used internal encoding for strings, and regular expression engines for platforms which use UTF-16 internally are generally designed to work on that encoding without conversion to UTF-32. Examples that spring to mind are most JavaScript regular expression engines, the ICU regular expression engine, and java.util.regex. If variable-width encodings were so difficult to deal with then you would expect these to have run into some problems with it; however, as far as I can tell, they have not. This is evidence against variable-width encodings being difficult for regular expression engines to deal with. (Sanity check for my argument above: If you read through https://swtch.com/~rsc/regexp/regexp2.html https://swtch.com/~rsc/regexp/regexp2.html, which covers both backtracking and non-backtracking regex engines and includes code, none of the code examples would need more than trivial modification to deal with variable-width encodings.)
  - Manishearth 10y ago
    Note that JS isn't UTF-16, it's slightly different. In JS unpaired surrogates are allowed. String indexing is by code unit, so non-BMP code points are considered to be two "characters". IIRC Java also allows unpaired surrogates? But does consider non-BMP codepoints to be single characters. I think. Idk. So from JSs point of view it is a fixed-width encoding, one where all byte values are valid. `"\uD83D\uDC68".match(/\ud83d/)` works (U+D83D is a high surrogate, and "\uD83D\uDC68" is U+1F468 MAN), so the regex engine operates on code units, not code points. I think for Java the regex engine would have to deal with it as a variable-width encoding, though. Edit: Hacker News removes emoji from comments.

Animats 10y ago

If everything that can match in a regular expression is valid UTF-8, and everything the regular expression can generate is valid UTF-8, you can just run the regular expression on the byte string. This requires that matches match UTF-8 substrings, only. That's easy for explicit strings, such as "abc". For more general forms, "." must match one rune, not one byte. But that's not hard. Python's problem is that strings are random-access indexable by rune (in the Go sense). Python either needs a representation that's rune-indexable, or it needs to generate an index array for strings that need one. There's an argument for the second approach, because most loops don't need a random-access index. "for i in "abcdef: ... " does not, for example.

pjscott 10y ago
It's also possible to chunk the index array: to store the byte-index of every 16th rune, say, and do a bit of cheap iteration afterward. I've had good success with this approach: it's fast, it's light on memory, and it preserves constant-time indexing by code point.
Manishearth 10y ago
> Python's problem is that strings are random-access indexable by rune Yeah, one of my points in the blog post is that random-access rune (code point) indexing isn't very valuable. Python is stuck with it, but if anyone in the future needs to make a similar choice, I hope they don't use O(1) rune indexing as a reason unless they have a very specific use case where O(1) rune indexing actually matters. (I, for one, am very happy with the "rune" terminology, "char" is way too overloaded. It took me a minute to understand why they did that in Go when I first picked it up, but when I realized the reason I found it brilliant)
- Animats 10y ago
  One approach for a Python implementation would be to store strings as UTF-8, and generate an index array as needed. For most operations, you don't need an index. Concatenation doesn't need one. Ordinary iteration (for c in "hello" :) doesn't need one. Regular expressions don't need an index. That covers most of the common use cases. I like "rune" as terminology. A rune is one Unicode code point. A grapheme is a sequence of runes which should not be split.

hoytech 10y ago

There are many considerations of course and I might not have fully grasped your point, but in reference to your last paragraph: By default RE2 matches directly against the UTF-8 encoding, see this neat state diagram: https://swtch.com/~rsc/regexp/regexp3.html#step3 https://swtch.com/~rsc/regexp/regexp3.html#step3 In terms of backtracing engines, perl also stores strings internally as UTF-8 (on most platforms) and its regexp engine runs directly on them. It can also match "eXtended grapheme clusters" with \X.

burntsushi 10y ago

> Another algorithm for unicode strings which wants to index by code point is unicode regular expression matching. Why? This is certainly not a requirement for at least some levels of Unicode support. > I once heard that complexity of implementing regex directly on UTF-8 is one reason why Python will not use UTF-8 internally. It's really not that bad. Both RE2 and Rust's regex engine operate on UTF-8 directly, and this is one of the reasons why these engines are fast. If your automaton is byte based, then you can do a lot of nice tricks in your DFA implementation. (In fact, it's a critical reason why ripgrep doesn't slow down when handling Unicode features, unlike GNU grep.) For Rust at least, the trickier parts of generating the UTF-8 automaton are available for reuse in the utf8-ranges crate: https://docs.rs/utf8-ranges/1.0.0/utf8_ranges/ https://docs.rs/utf8-ranges/1.0.0/utf8_ranges/ (Which is used in at least two regex implementations I've written.) I'd say the complexity claim might be coming from some other component of the implementation, or something more related to how Python strings are generally represented, rather than it being a fundamental complexity of building a regex engine on UTF-8 directly.