4 ms·

why not just full regex

• mbell 10y ago
  regex search is slow and difficult to index efficiently.
  • jcoffland 10y ago
    It's plenty fast for many purposes. I grep large source code repos all the time. It's very fast as long as you avoid grepping large binary files for no reason. The link below shows timings for various regex on a 20MiB text file for several different regex softwares. The best code never exceeds half a second for even the worst expressions. Most are much faster. http://sljit.sourceforge.net/regex_perf.html http://sljit.sourceforge.net/regex_perf.html
    • bdonlan 10y ago
      For most reasonable search regexes, it's reasonably fast if your repository is already cached in memory. However, it's still fairly heavyweight, and the cost of running even these reasonable searches hundreds or thousands of times a second becomes significant. When you add to this the fact that it's possible to deliberately construct regexes that are much more complicated to evaluate (particularly if you allow extensions beyond a true regular language) - potentially being a DoS target - and many repos won't be cached when the search comes in (or caching them would also be very expensive), the costs just get higher. In contrast, a simple keyword search can be performed with a predictable, low cost, so it's no wonder that they'd prefer to implement this instead.
      • milesrout 10y ago
        >When you add to this the fact that it's possible to deliberately construct regexes that are much more complicated to evaluate (particularly if you allow extensions beyond a true regular language) - potentially being a DoS target Only if you allow extensions, but then they aren't regular expressions.
        • tyingq 10y ago
          Backreferences aren't really an extension though, are they? Re2 excludes them specifically .
          • milesrout 10y ago
            Backreferences are certainly an extension. They are the primary reason that regular expression engines that allow them are slow.
            • tyingq 10y ago
              Ahhh, "extension" meaning not in the POSIX basic definition. Sure. Though I don't know many tools that implement REs in that basic form. They almost all include features outside that definition.
              • burntsushi 10y ago
                No, extension as in it is not regular. Nothing to do with POSIX. RE2, Go and Rust do not provide backreference support in exchange for predictable performance.
                • deleted 10y ago
                  [deleted]
                • deleted 10y ago
                  [deleted]
                • deleted 10y ago
                  [deleted]
              • notriddle 10y ago
                There are plenty of regex engines that are guaranteed O(n) for all regexes they accept. There's re2, go-regex, and rust-regex just to list a few popular ones. They still use Perl-like syntax, and might still be able to parse non-regular languages, but you don't need to worry about users deliberately crafting regexes to eat up CPU time like PCRE.
  • kevincox 10y ago
    Do you remember Google code search? Difficult yes, but definitely not slow. This seems like it would be a high value feature as well.
• tyingq 10y ago
  Actually, I would really just be happy with better docs. In code search, for example, this appears to work: foo AND bar NOT baz OR fizz So, it supports AND, NOT, and OR. Nowhere, though, does it say that. I don't know if I can group these to get around precedence either. Parenthesis are ignored. It does mention NOT somewhere. And, there's no navigation to search help by the search button. I had to google to find out any help was available. Also, it ignores some characters for unknown reasons. Like $, for example. That's a meaningful sigil in Perl, PHP, and so on...it's quite frustrating that it's ignored.
  • OJFord 10y ago
    > this appears to work: foo AND bar NOT baz OR fizz `AND` being implicit in `bar NOT baz`, and in `foo bar`. Also AND/OR is per file, rather than line which I wondered after reading this comment. There's some information here [0] that's mainly centred on issues/PRs, but some transferable (this might be what you referred to that does mention NOT). There's also a bit more information here [1]; it does at least acknowledge that `$` will be swallowed. [0] - https://help.github.com/articles/search-syntax https://help.github.com/articles/search-syntax [1] - https://help.github.com/articles/searching-code/ https://help.github.com/articles/searching-code/