17 ms·

This is effectively just a nicer syntax than usual for regular expressions, but there are actual areas of semantics where regexp languages are ripe for improvem

• avgcorrection 4y ago
  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.
• SonOfLilit 4y ago
  Note that "minimal DFA" is not very relevant these days, with Google's `re2` being the only implementation I'm aware of that implements a DFA. All others sacrifice predictable performance for feature parity with Perl.
  • kevincox 4y ago
    It is incredibly relevant if you want to process uset-provided expressions. Otherwise you expose yourself to a DoS attack. The Rust regex crate is also DFA based and safe for untrusted inputs.
    • SonOfLilit 4y ago
      Nice to know about Rust. From reading the docs the situation seems to be more complicated and more impressive: https://docs.rs/regex/latest/regex/#untrusted-input https://docs.rs/regex/latest/regex/#untrusted-input
    • Someone 4y ago
      .NET added timeouts to handle that. It’s a per-regex setting with a global default (https://docs.microsoft.com/en-us/dotnet/api/system.text.regularexpressions.regex.matchtimeout?view=net-6.0 https://docs.microsoft.com/en-us/dotnet/api/system.text.regu...).
      • nsajko 4y ago
        I guess that adding timeouts can significantly decrease the run time efficiency?
        • Someone 4y ago
          It can, but this isn’t a hard timeout. From the description (“The MatchTimeout property defines the approximate maximum time interval for a Regex instance to execute”), it seems they have their regex engine periodically (say after handling every 10,000 instructions of the compiled regex) check whether they went over the limit.
• burntsushi 4y ago
  > most regexp libraries are stuck in the 80s/90s, not keeping up with recent developments in research. Can you show me the research that states how to add things like complement and intersection to general purpose regex libraries? Most regex engines are backtracking based, and in that context, adding complement/intersection seems pretty intractable to me. For the small subset of regex engines that are based on finite state machines, it's pretty much intractable there too outside of niche regex engines. In fact, the research[1] suggests that adding things like complement/intersection is quite difficult: > In particular, we show that when constructing a regular expression defining the complement of a given regular expression, a double exponential size increase cannot be avoided. Similarly, when constructing a regular expression defining the intersection of a fixed and an arbitrary number of regular expressions, an exponential and double exponential size increase, respectively, cannot be avoided. And indeed, as another commenter pointed out, "minimal DFA" is effectively irrelevant for any general purpose regex engine. Not only do you not have the the budget to build a DFA, but you certainly don't have the budget to minimize that DFA. With respect to reversal, RE2 and Rust's regex crate both do that. But mostly as an internal strategy for finding the start-of-match when using a lazy DFA. It's otherwise a somewhat niche feature more generally. With respect to JITs, plenty of regex engines out there do that. PCRE comes to mind. So does V8. As a general purpose regex engine author, we aren't "stuck" in the 80s/90s. There are just some fundamental trade offs at play here that make your ideas difficult to support. It's not like we haven't thought about it. Moreover, for things like complement and intersection specifically, actually reasoning about them in regex syntax is pretty tricky! I'm not sure if you've tried it or not. (There are some niche regex engines that implement it, like redgrep.) [1]: https://dl.acm.org/doi/10.1145/2071368.2071372 https://dl.acm.org/doi/10.1145/2071368.2071372
  • nsajko 4y ago
    > Can you show me the research that states how to add things like complement and intersection to general purpose regex libraries? Sorry, don't have time for that right now, but look into regular expression derivatives and similar stuff. > Most regex engines are backtracking based, and in that context, adding complement/intersection seems pretty intractable to me. Yeah, I wasn't really considering irregular "regexp", they don't make much sense in theory, so of course that extending them wouldn't make much sense either. Thing is, extending true regular expressions with operators like complement and concepts like weights seems like it could make the "theoretically pure" regexps more powerful *in practice* than irregular regexps (with backreferences, etc. Certainly more understandable. > For the small subset of regex engines that are based on finite state machines, it's pretty much intractable there too outside of niche regex engines. Don't think so. There are many examples, but mostly implemented in "functional" programming languages. > In fact, the research[1] suggests that adding things like complement/intersection is quite difficult: > > ... You misunderstood the abstract. It's not saying that its difficult to translate extended RE (RE with these additional operators) to finite automata, it's just saying that translating extended RE to traditional RE can cause a huge blowup (something I already hinted at in the comment above). So this is a pro, not a con. > And indeed, as another commenter pointed out, "minimal DFA" is effectively irrelevant for any general purpose regex engine. Not only do you not have the the budget to build a DFA, but you certainly don't have the budget to minimize that DFA. It's possible to produce NFA directly from extended RE, see "Antimirov derivatives" for a start. The original Antimirov derivatives don't support complementation and similar, but there are extensions that do. Search for something like "partial derivatives regular expression complement", or "derived term automata complement". > niche regex engines that implement it, like redgrep Thanks for the pointer.
• Alex3917 4y ago
  What's the overall best regex library today that can be used in production? E.g. in terms of features, speed of compilation, and speed of matching.
• pygy_ 4y ago
  I wrote a JS/TS lib that adds support for RegExp composition, set opperations, atomic groups and arbitrary bounds. https://github.com/compose-regexp/compose-regexp.js https://github.com/compose-regexp/compose-regexp.js
  • pygy_ 4y ago
    ... and FWIW no one seems to care one bit about it ... (this would have been an edit, but I'm out of the window)
    • alrlroipsp 4y ago
      At least back in my day, thread hi-jacking was kinda frowned upon. You kids are like aliens to me.
      • pygy_ 4y ago
        When I posted, the submission had 123 points, and nsajko’s critical comment was at the top of the thread. My lib’s show HN which addresses most of his concerns, royally got 5 votes. Given that Rulex was obviously a success, I didn’t feel like my comment would take from them. Also, the discrepancy between the upvotes on that comment and the lack of uptick for compose-regexp felt interesting to point out
• BurningFrog 4y ago
  > This is effectively just a nicer syntax than usual for regular expressions OK, but the painful syntax is the biggest problem for regular expressions!
• mtlmtlmtlmtl 4y ago
  I'm not sure how useful even more powerful regex would actually be. Using large, complicated regexes is a very bug-prone practice in general.
  • nsajko 4y ago
    > Using large, complicated regexes is a very bug-prone practice in general. Yes, this is exactly why extending RE is necessary.
• RcouF1uZ4gsC 4y ago
  > * JIT. It should be possible to compile regexps with libgccjit or with llvm. Although not JIT in that it needs the regex specified at compile time, both Rust and C++ (using the compile time reflex library) can generate the code to evaluate the regex at compile time.
  • burntsushi 4y ago
    The regex crate (for Rust) does not have this capability. It used to many years ago via the regex_macros crate, but I abandoned it mostly because of not having enough resources to dedicate to it and its somewhat niche usage. If you need compile time regexes, it's better to use something like re2c. The reflex library is interesting, but more like a C++ template hack. Its codegen is impressive, but it's missing (last time I checked) a lot of the classical optimizations that a regex engine typically has. Like a literal prefilter scan.
    • RcouF1uZ4gsC 4y ago
      > It used to many years ago via the regex_macros crate, but I abandoned it mostly because of not having enough resources to dedicate to it and its somewhat niche usage. As an aside, my impression is that Rust developers are using macros less now than they were even a couple of years ago. It seemed a few years ago, a lot of people coming to Rust were impressed by the power of macros (especially procedural) and used them in a lot of libraries. It seems now, people are realizing the costs of macros to tooling and understandability, and are using them more judiciously.
      • burntsushi 4y ago
        I don't think I've detected any such shift personally. (I've been using Rust daily since before 1.0 was released.)