3 ms·

Nice! Lightgrep[1] uses libicu et al to look up code points for a user-specified encoding and encode them as bytes, then just searches for the bytes. Since ripg

Nice! Lightgrep[1] uses libicu et al to look up code points for a user-specified encoding and encode them as bytes, then just searches for the bytes. Since ripgrep is presumably looking just for bytes, too, and compiling UTF-8 multibyte code points to a sequence of bytes, perhaps you can do likewise with ICU and support other encodings. ICU is a bear to build against when cross-compiling, but it knows hundreds of encodings, all of the proper code point names, character classes, named properties, etc., and the surface area of its API that's required for such usage is still pretty small. [1]: http://strozfriedberg.github.io/liblightgrep http://strozfriedberg.github.io/liblightgrep

burntsushi 10y ago
I hadn't heard of liblightgrep, nice. It's on my short list for looking more closely. I doubt I'd ever be comfortable with Rust's regex engine growing a dependency on libicu, but it's still worth understanding your implementation. Some questions, if you don't mind. The big one is: does your regex engine use finite automata, and does it put the text decoding into the automaton itself? For example, when you compile the `.` regex, you end up with an automaton that inlines UTF-8 decoding itself. It looks like this: https://gist.github.com/anonymous/8fbe170bfcca5d7475b59299fabbd0a3 https://gist.github.com/anonymous/8fbe170bfcca5d7475b59299fa... Does you regex library do that for each type of encoding? Or is there a transcoding step?
- jonstewart 10y ago
  Reply fail, see above.
jonstewart 10y ago
Yep! It's a multipattern engine so we use an NFA--slower than a normal engine, but effective when you have thousands of patterns to search for in binary streams. Since we are often searching binary, we'll encounter text fragments in lots of different encodings, so they're all compiled into the NFA. We wrote a paper about its Unicode support: http://www.dfrws.org/sites/default/files/session-files/paper-unicode_search_of_dirty_data_or_how_i_learned_to_stop_worrying_and_love_unicode_technical_standard_18.pdf http://www.dfrws.org/sites/default/files/session-files/paper....

burntsushi 10y ago

I hadn't heard of liblightgrep, nice. It's on my short list for looking more closely. I doubt I'd ever be comfortable with Rust's regex engine growing a dependency on libicu, but it's still worth understanding your implementation. Some questions, if you don't mind. The big one is: does your regex engine use finite automata, and does it put the text decoding into the automaton itself? For example, when you compile the `.` regex, you end up with an automaton that inlines UTF-8 decoding itself. It looks like this: https://gist.github.com/anonymous/8fbe170bfcca5d7475b59299fabbd0a3 https://gist.github.com/anonymous/8fbe170bfcca5d7475b59299fa... Does you regex library do that for each type of encoding? Or is there a transcoding step?

jonstewart 10y ago
Reply fail, see above.

jonstewart 10y ago

Yep! It's a multipattern engine so we use an NFA--slower than a normal engine, but effective when you have thousands of patterns to search for in binary streams. Since we are often searching binary, we'll encounter text fragments in lots of different encodings, so they're all compiled into the NFA. We wrote a paper about its Unicode support: http://www.dfrws.org/sites/default/files/session-files/paper-unicode_search_of_dirty_data_or_how_i_learned_to_stop_worrying_and_love_unicode_technical_standard_18.pdf http://www.dfrws.org/sites/default/files/session-files/paper....