4 ms·

OK, now that I have hands on a keyboard, this is what I meant by Hyperscan's match semantics being "peculiar": $ echo 'foobar' | hg -o '\w{3}' 1:foobar

OK, now that I have hands on a keyboard, this is what I meant by Hyperscan's match semantics being "peculiar": $ echo 'foobar' | hg -o '\w{3}' 1:foobar $ echo 'foobar' | grep -E -n -o '\w{3}' 1:foo 1:bar Here's the aforementioned reddit thread: https://old.reddit.com/r/cpp/comments/143d148/hypergrep_a_new_fastest_grep_to_search/jn952bp/ https://old.reddit.com/r/cpp/comments/143d148/hypergrep_a_ne... I want to be clear that these are intended semantics as part of Hyperscan. It's not a bug with Hyperscan. But it is something you'll need to figure out how to deal with (whether that's papering over it somehow, although I'm not sure that's possible, or documenting it as a difference) if you're building a grep around Hyperscan.

kazinator 3y ago
How about: use Hyperscan to round up all the lines that contain matches, and process those again with regex for the "-o" semantics.
- burntsushi 3y ago
  You mean two different regex engines for the same search? That is perhaps conceptually fine, but in practice any two regex engines are likely to have differences that will make that strategy fall apart in some cases. (Perhaps unless those regex engines rigorously stick to a spec like POSIX or ecmascript. But that's not the case here. IIRC Hyperscan meticulously matches the behavior of a subset of PCRE2, but ripgrep's default engine is not PCRE2.) You could perhaps work around this by only applying it as an optimization when you know the pattern has identical semantics in both regex engines. But you would have to do the work to characterize them. I would rather just make the regex crate faster. If you look at the rebar benchmarks, it's not that far behind and is sometimes even faster. The case where Hyperscan really destroys everything else is for searches for many patterns. Hyperscan has other logistical issues. It is a beast to build. And its pattern compilation times can be large (again, see rebar). Hyperscan itself only supports x86-64, so one would probably want to actually use Vectorscan (a fork of Hyperscan that supports additional architectures).
cozzyd 3y ago
is that an alias, or does hypergrep really use the same command name as mercurial?
- tedunangst 3y ago
  It was renamed: https://github.com/p-ranav/hypergrep/commit/ee85b713aa84e0050a3b36030000778ccfd4882f https://github.com/p-ranav/hypergrep/commit/ee85b713aa84e005...
frankjr 3y ago
It might be the intended behavior of Hyperscan but it really feels like a bug in Hypergrep to report the matches like this - you cannot report a match which doesn't fully match the regex... I also wonder if there's a performance issue when matching a really long line because Hyperscan is not greedy and will ping back to Hypergrep for every sub match. I guessing this is the reason for those shenanigans in the callback [0]. $ python -c 'print("foo" + "bar" * 3000)' | hg -o 'foo.*bar' [0] https://github.com/p-ranav/hypergrep/blob/ee85b713aa84e0050a3b36030000778ccfd4882f/src/match_handler.cpp#L52 https://github.com/p-ranav/hypergrep/blob/ee85b713aa84e0050a...
- burntsushi 3y ago
  I don't disagree. It's why I brought this up. It's tricky to use Hyperscan, as-is, as a regex engine in a grep tool for these reasons. I don't mean to claim it is impossible, but there are non-trivial issues you'll need to solve. It's hard to learn too much from hypergrep. It still has some rough spots: $ hgrep -o 'foo.*bar' foobarbar.txt foobarbar.txt 1:[Omitted long line with 1 matches] $ hgrep -M0 -o 'foo.*bar' foobarbar.txt Too few arguments For more information try --help $ hgrep -M 0 -o 'foo.*bar' foobarbar.txt foobarbar.txt 1:[Omitted long line with 1 matches] $ hgrep -M 0 'foo.*bar' foobarbar.txt foobarbar.txt 1:[Omitted long line with 1 matches] $ hgrep -M0 'foo.*bar' foobarbar.txt terminate called after throwing an instance of 'std::invalid_argument' what(): pattern not found zsh: IOT instruction (core dumped) hgrep -M0 'foo.*bar' foobarbar.txt Another issue with Hyperscan is that if you enable HS_FLAG_UTF8[1], which hypergrep does[2,3], and then search invalid UTF-8, then the result is UB. > This flag instructs Hyperscan to treat the pattern as a sequence of UTF-8 characters. The results of scanning invalid UTF-8 sequences with a Hyperscan library that has been compiled with one or more patterns using this flag are undefined. That's another issue you'll need to grapple with if you use Hyperscan. PCRE2 used to have this issue[4], but they've since defined the semantics of searching invalid UTF-8 with Unicode mode enabled. ripgrep 14 uses that new mode, but I haven't updated that FAQ answer yet. Hyperscan isn't alone. Many regex engines do not support searching arbitrary byte sequences[5]. And this is why many/most regex engines are awkward to use in a fast grep implementation. Because you really do not want your grep to fall over when it comes across invalid UTF-8. And the overhead of doing UTF-8 checking in the first place (and perhaps let you just skip over lines that contain invalid UTF-8) would make it difficult to be competitive in performance. It also inhibits its usage in OSINT work. [1]: https://intel.github.io/hyperscan/dev-reference/api_files.html https://intel.github.io/hyperscan/dev-reference/api_files.ht... [2]: https://github.com/p-ranav/hypergrep/blob/ee85b713aa84e0050a3b36030000778ccfd4882f/src/compiler.cpp#L42 https://github.com/p-ranav/hypergrep/blob/ee85b713aa84e0050a... [3]: https://github.com/p-ranav/hypergrep/blob/ee85b713aa84e0050a3b36030000778ccfd4882f/src/file_filter.cpp#L14 https://github.com/p-ranav/hypergrep/blob/ee85b713aa84e0050a... [4]: https://github.com/BurntSushi/ripgrep/blob/master/FAQ.md#why-does-ripgrep-get-slower-when-i-enable-pcre2-regexes https://github.com/BurntSushi/ripgrep/blob/master/FAQ.md#why... [5]: https://github.com/BurntSushi/rebar/blob/96c6779b7e1cdd850b8a8801b24a19a77f3a6863/benchmarks/definitions/test/unicode/invalid-utf8.toml https://github.com/BurntSushi/rebar/blob/96c6779b7e1cdd850b8...

kazinator 3y ago

How about: use Hyperscan to round up all the lines that contain matches, and process those again with regex for the "-o" semantics.

burntsushi 3y ago
You mean two different regex engines for the same search? That is perhaps conceptually fine, but in practice any two regex engines are likely to have differences that will make that strategy fall apart in some cases. (Perhaps unless those regex engines rigorously stick to a spec like POSIX or ecmascript. But that's not the case here. IIRC Hyperscan meticulously matches the behavior of a subset of PCRE2, but ripgrep's default engine is not PCRE2.) You could perhaps work around this by only applying it as an optimization when you know the pattern has identical semantics in both regex engines. But you would have to do the work to characterize them. I would rather just make the regex crate faster. If you look at the rebar benchmarks, it's not that far behind and is sometimes even faster. The case where Hyperscan really destroys everything else is for searches for many patterns. Hyperscan has other logistical issues. It is a beast to build. And its pattern compilation times can be large (again, see rebar). Hyperscan itself only supports x86-64, so one would probably want to actually use Vectorscan (a fork of Hyperscan that supports additional architectures).

cozzyd 3y ago

is that an alias, or does hypergrep really use the same command name as mercurial?

tedunangst 3y ago
It was renamed: https://github.com/p-ranav/hypergrep/commit/ee85b713aa84e0050a3b36030000778ccfd4882f https://github.com/p-ranav/hypergrep/commit/ee85b713aa84e005...

frankjr 3y ago

It might be the intended behavior of Hyperscan but it really feels like a bug in Hypergrep to report the matches like this - you cannot report a match which doesn't fully match the regex... I also wonder if there's a performance issue when matching a really long line because Hyperscan is not greedy and will ping back to Hypergrep for every sub match. I guessing this is the reason for those shenanigans in the callback [0]. $ python -c 'print("foo" + "bar" * 3000)' | hg -o 'foo.*bar' [0] https://github.com/p-ranav/hypergrep/blob/ee85b713aa84e0050a3b36030000778ccfd4882f/src/match_handler.cpp#L52 https://github.com/p-ranav/hypergrep/blob/ee85b713aa84e0050a...

burntsushi 3y ago
I don't disagree. It's why I brought this up. It's tricky to use Hyperscan, as-is, as a regex engine in a grep tool for these reasons. I don't mean to claim it is impossible, but there are non-trivial issues you'll need to solve. It's hard to learn too much from hypergrep. It still has some rough spots: $ hgrep -o 'foo.*bar' foobarbar.txt foobarbar.txt 1:[Omitted long line with 1 matches] $ hgrep -M0 -o 'foo.*bar' foobarbar.txt Too few arguments For more information try --help $ hgrep -M 0 -o 'foo.*bar' foobarbar.txt foobarbar.txt 1:[Omitted long line with 1 matches] $ hgrep -M 0 'foo.*bar' foobarbar.txt foobarbar.txt 1:[Omitted long line with 1 matches] $ hgrep -M0 'foo.*bar' foobarbar.txt terminate called after throwing an instance of 'std::invalid_argument' what(): pattern not found zsh: IOT instruction (core dumped) hgrep -M0 'foo.*bar' foobarbar.txt Another issue with Hyperscan is that if you enable HS_FLAG_UTF8[1], which hypergrep does[2,3], and then search invalid UTF-8, then the result is UB. > This flag instructs Hyperscan to treat the pattern as a sequence of UTF-8 characters. The results of scanning invalid UTF-8 sequences with a Hyperscan library that has been compiled with one or more patterns using this flag are undefined. That's another issue you'll need to grapple with if you use Hyperscan. PCRE2 used to have this issue[4], but they've since defined the semantics of searching invalid UTF-8 with Unicode mode enabled. ripgrep 14 uses that new mode, but I haven't updated that FAQ answer yet. Hyperscan isn't alone. Many regex engines do not support searching arbitrary byte sequences[5]. And this is why many/most regex engines are awkward to use in a fast grep implementation. Because you really do not want your grep to fall over when it comes across invalid UTF-8. And the overhead of doing UTF-8 checking in the first place (and perhaps let you just skip over lines that contain invalid UTF-8) would make it difficult to be competitive in performance. It also inhibits its usage in OSINT work. [1]: https://intel.github.io/hyperscan/dev-reference/api_files.html https://intel.github.io/hyperscan/dev-reference/api_files.ht... [2]: https://github.com/p-ranav/hypergrep/blob/ee85b713aa84e0050a3b36030000778ccfd4882f/src/compiler.cpp#L42 https://github.com/p-ranav/hypergrep/blob/ee85b713aa84e0050a... [3]: https://github.com/p-ranav/hypergrep/blob/ee85b713aa84e0050a3b36030000778ccfd4882f/src/file_filter.cpp#L14 https://github.com/p-ranav/hypergrep/blob/ee85b713aa84e0050a... [4]: https://github.com/BurntSushi/ripgrep/blob/master/FAQ.md#why-does-ripgrep-get-slower-when-i-enable-pcre2-regexes https://github.com/BurntSushi/ripgrep/blob/master/FAQ.md#why... [5]: https://github.com/BurntSushi/rebar/blob/96c6779b7e1cdd850b8a8801b24a19a77f3a6863/benchmarks/definitions/test/unicode/invalid-utf8.toml https://github.com/BurntSushi/rebar/blob/96c6779b7e1cdd850b8...