6 ms·

Do operators like complement work with Unicode?

nsajko 4y ago
Of course, Unicode is just another alphabet. Specific expressions might be problematic though, depending on the implementation. EDIT: If malicious inputs are something to be worried about, I think a good way to do this would be to check for exceedingly costly blowups of various kinds during/after translation to a finite automaton (so before automaton execution). This would enable having complemented expressions when safe (in lots of cases, at least).
- joppy 4y ago
  To get something useful and not attackable, the complement operation would need to take the complement inside the set of valid UTF-8 strings rather than the set of all byte-sequences, which is probably doable but I'm not sure how straightforward it would be.
  - nsajko 4y ago
    > the complement operation would need to take the complement inside the set of valid UTF-8 strings rather than the set of all byte-sequences Anything else would be a bug in any case.
dan-dev 4y ago
Yes and straighforwardly so if you use character classes as your basic building blocks. Here I implemented a Haskell implementation that is easily extandable to include complements: https://github.com/dan-blank/hgrep-smallcore https://github.com/dan-blank/hgrep-smallcore (I like this project because it translates ERE compliant regexes - sans negated character sets - down to only 4 constructs, one of which being character classes). It implements https://www.ccs.neu.edu/home/turon/re-deriv.pdf https://www.ccs.neu.edu/home/turon/re-deriv.pdf, character classes are described in 4.2. I actually had complement in it as a 5th construct, but when the submission came closer and the examiners found some errors in my logic (my fault for not writing good enough unit tests!), I took complement out again when cleaning the project up.
- burntsushi 4y ago
  I tried to test your program because I'm pretty sure your techniques can't be used in a general purpose regex engine. (I've long wanted to make use of regex derivatives somehow, but I don't think it's feasible because of the downsides of building up a full DFA.) More to the point, I also suspected that you might be using a sparse representation for transitions in your DFA if the alphabet of your DFA is indeed all of Unicode. This is also problematic because it tends to make search time quite a bit slower. In any case, I built your program with 'stack install' but got this when I tried to use it with Unicode: $ hgrep-exe '^\pL{42}$' OpenSubtitles2018.raw.sample.en hgrep-exe: Maybe.fromJust: Nothing I get the same for '\w{42}'. Hmm, maybe you don't support counted repetitions? OK, '\w' works, but is it Unicode aware? $ echo 'β' > /tmp/beta $ echo 'b' /tmp/b $ hgrep-exe '\w' /tmp/beta $ hgrep-exe '\w' /tmp/b $ Hmmm, no, but '\w' doesn't seem to work at all... I can't seem to get much working: $ hgrep-exe '[a-z]' /tmp/b $ hgrep-exe 'b' /tmp/b b OK, so a simple literal search works. I don't know. I'm not sure how to do a Unicode stress test with your tool.
  - tinco 4y ago
    Mostly irrelevant but those runtime errors are the main reason why I stopped using Haskell. Haskell is a great language with a great booming ecosystem, but if you can have uncaught exceptions in IO monads, and even unchecked errors in your pure code like that fromJust there, then what's the point? For all its ceremony is not much more functionally pure than JavaScript. And a language without purity as a concept like Rust has achieved frankly a more tight feeling of safety and great flexibility despite having a more simple typesystem. Imo Haskell has to drastically change like it did in the early 2000's to become competitive again.
    - dan-dev 4y ago
      Hold on! See: https://github.com/dan-blank/hgrep-smallcore/issues/1 https://github.com/dan-blank/hgrep-smallcore/issues/1 Using `fromJust` is deeply frowned upon, and indeed a few eyebrows were raised then showing my code to the examiners. This and a handful other warts unfortunate, but few and easy to work around. This function and others are in the prelude, but one can use other preludes that don't have these escape hatches. This does not undermine the huge benefits that people get from having IO checked by the typesystem. Just as having tyepcasting in a language does not undermine the benefits of types in that language.

Of course, Unicode is just another alphabet. Specific expressions might be problematic though, depending on the implementation. EDIT: If malicious inputs are something to be worried about, I think a good way to do this would be to check for exceedingly costly blowups of various kinds during/after translation to a finite automaton (so before automaton execution). This would enable having complemented expressions when safe (in lots of cases, at least).

joppy 4y ago
To get something useful and not attackable, the complement operation would need to take the complement inside the set of valid UTF-8 strings rather than the set of all byte-sequences, which is probably doable but I'm not sure how straightforward it would be.
- nsajko 4y ago
  > the complement operation would need to take the complement inside the set of valid UTF-8 strings rather than the set of all byte-sequences Anything else would be a bug in any case.

dan-dev 4y ago

Yes and straighforwardly so if you use character classes as your basic building blocks. Here I implemented a Haskell implementation that is easily extandable to include complements: https://github.com/dan-blank/hgrep-smallcore https://github.com/dan-blank/hgrep-smallcore (I like this project because it translates ERE compliant regexes - sans negated character sets - down to only 4 constructs, one of which being character classes). It implements https://www.ccs.neu.edu/home/turon/re-deriv.pdf https://www.ccs.neu.edu/home/turon/re-deriv.pdf, character classes are described in 4.2. I actually had complement in it as a 5th construct, but when the submission came closer and the examiners found some errors in my logic (my fault for not writing good enough unit tests!), I took complement out again when cleaning the project up.

burntsushi 4y ago
I tried to test your program because I'm pretty sure your techniques can't be used in a general purpose regex engine. (I've long wanted to make use of regex derivatives somehow, but I don't think it's feasible because of the downsides of building up a full DFA.) More to the point, I also suspected that you might be using a sparse representation for transitions in your DFA if the alphabet of your DFA is indeed all of Unicode. This is also problematic because it tends to make search time quite a bit slower. In any case, I built your program with 'stack install' but got this when I tried to use it with Unicode: $ hgrep-exe '^\pL{42}$' OpenSubtitles2018.raw.sample.en hgrep-exe: Maybe.fromJust: Nothing I get the same for '\w{42}'. Hmm, maybe you don't support counted repetitions? OK, '\w' works, but is it Unicode aware? $ echo 'β' > /tmp/beta $ echo 'b' /tmp/b $ hgrep-exe '\w' /tmp/beta $ hgrep-exe '\w' /tmp/b $ Hmmm, no, but '\w' doesn't seem to work at all... I can't seem to get much working: $ hgrep-exe '[a-z]' /tmp/b $ hgrep-exe 'b' /tmp/b b OK, so a simple literal search works. I don't know. I'm not sure how to do a Unicode stress test with your tool.
- tinco 4y ago
  Mostly irrelevant but those runtime errors are the main reason why I stopped using Haskell. Haskell is a great language with a great booming ecosystem, but if you can have uncaught exceptions in IO monads, and even unchecked errors in your pure code like that fromJust there, then what's the point? For all its ceremony is not much more functionally pure than JavaScript. And a language without purity as a concept like Rust has achieved frankly a more tight feeling of safety and great flexibility despite having a more simple typesystem. Imo Haskell has to drastically change like it did in the early 2000's to become competitive again.
  - dan-dev 4y ago
    Hold on! See: https://github.com/dan-blank/hgrep-smallcore/issues/1 https://github.com/dan-blank/hgrep-smallcore/issues/1 Using `fromJust` is deeply frowned upon, and indeed a few eyebrows were raised then showing my code to the examiners. This and a handful other warts unfortunate, but few and easy to work around. This function and others are in the prelude, but one can use other preludes that don't have these escape hatches. This does not undermine the huge benefits that people get from having IO checked by the typesystem. Just as having tyepcasting in a language does not undermine the benefits of types in that language.