4 ms·
Does anyone understand what the bug in grep was? UTF-8 regular expression matching shouldn't be different from ASCII at all, as far as I can tell. In UTF-8, ev
by Nitramp 15y ago
Does anyone understand what the bug in grep was?
UTF-8 regular expression matching shouldn't be different from ASCII at all, as far as I can tell. In UTF-8, every byte by itself can be identified as a start byte or trail byte, so if you want to match a regular expression, you don't even have to care about UTF-8 in any way. Any legal character in the regexp you want to look for can only match at a legal character start in the haystack.
- 4ad 15y agoGNU grep uselessly converts UTF-8 to some multibyte char internal representation. You are completely right, matching regular expressions with UTF-8 text is the same as with ASCII text, one of the reasons why UTF-8 is so good.
- omgtehlion 15y agoYou both are wrong. If you take arbitrary byte in ascii stream you can be sure that this is a whole char, but if you take arbitrary byte in utf-8 stream you can get a start of a char / end of char / or whole char.
- 4ad 15y agoObviously choosing an arbitrary offset in the byte stream might not align on rune boundary, but UTF-8 is great because you can determine that. You can determine the start/end boundaries in any subset of the byte stream, as opposed to most other encodings. The issue is completely unrelated to the fact that matching regexps in UTF-8 text is the same as matching regexp in ASCII text. The regular expression tool doesn't even need to care that the text is UTF-8. It's just byte comparisons, the tool doesn't even need to be aware of rune boundaries.
- omgtehlion 15y agojust look into grep’s sources. it has loads of low-level optimizations to make string search faster. But all these optimizations work only with exact-witdth encodings, thats why it is related. P.S.: and sometimes there are a lot of problems with lower and upper-case letters http://www.gnu.org/s/grep/devel.html http://www.gnu.org/s/grep/devel.html
- colomon 15y agoDon't some of the common cases of searching require the ability to quickly skip forward N characters for high efficiency? That's simple pointer arithmetic in the ASCII case, but requires reading each byte skipped in UTF-8, right? (I'm particularly thinking of Boyer-Moore -- http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_sear... -- but I'm sure there are other examples as well.)
- _delirium 15y ago> It's just byte comparisons If it's just doing byte comparisons, then the tool isn't properly implementing http://en.wikipedia.org/wiki/Unicode_equivalence http://en.wikipedia.org/wiki/Unicode_equivalence, unless it can assume that all input text was already normalized.
- EdiX 15y ago> UTF-8 regular expression matching shouldn't be different from ASCII at all, as far as I can tell. Not really. First the '.' operator needs to work differently. This can be still done fast, but if you actually want to claim unicode support you should also consider: - Unicode collation orders - Unicode string equivalence algorithms - Unicode normalization algorithms This will also take care of all the unicode weirdnesses that no one actually uses or cares about but you still must implement to claim compatibility like: presentational forms, combining diacritics, ligatures, double sized characters and other odd stuff.
- vilya 15y agoCharacter classes would trip you up, I think. e.g. \w for word characters.