4 ms·

Ripgrep is based on RE2 and supports backrefs. Wonder why they didn't use that.

by jakear 7y ago

burntsushi 7y ago
Not quite. ripgrep uses Rust's regex engine, not RE2. Rust's regex engine is descended from RE2, but there is no code sharing. Rust's regex engine does not support backreferences. RE2 does not either. ripgrep does however have a -P/--pcre2 flag which causes it to use PCRE2 instead of Rust's regex engine. PCRE2 supports backreferences and other things, like look-around. (ripgrep also has an --auto-hybrid-regex flag, which will automatically enable PCRE2 for you if you write a regex with backreferences or look-around.) The reason not to use an engine like PCRE2 for a project like this is because it would be trivially exposed to ReDoS: https://en.wikipedia.org/wiki/ReDoS https://en.wikipedia.org/wiki/ReDoS
- jakear 7y ago
  Thanks for the clarification. As an aside, how difficult do you think it would be to compile ripgrep to wasm? In VS Code we use ripgrep for full-workspace search and Node's regex library for in-memory searches, but this leads to discrepancies and issues such as catastrophic backtracking in the in-memory search.
  - burntsushi 7y ago
    I've never tried to compile to WASM. It really depends on how much of the OS APIs need to be fixed. e.g., I don't think WASM supports memory maps as one example. In that case, ripgrep could be made to compile without support for memory maps with a bit of work. But that's an easy case. What other things does WASM not support? What about typical file/directory APIs? I don't think it does, or it least, it looks like Rust's standard library doesn't implement anything for them: https://github.com/rust-lang/rust/blob/master/src/libstd/sys/wasm/fs.rs https://github.com/rust-lang/rust/blob/master/src/libstd/sys... At that point, it would be hopelessly difficult to build ripgrep. The right path then would be to build a new application that uses whatever of ripgrep's libraries make sense. Popping up a level though, why would you want to compile to WASM? If you're using Node, then surely you can build an FFI bridge to Rust's regex library. At least at that point, you'd be using the same regex engine. I even maintain official C bindings for them: https://github.com/rust-lang/regex/tree/master/regex-capi https://github.com/rust-lang/regex/tree/master/regex-capi EDIT: Oh, and not sure if this is useful, but the regex crate itself should compile to WASM just fine. I know I've seen people run it in the browser before. If there's a problem here, then please file a bug!
    - jakear 7y ago
      Thanks for all the advice. We'd just be running it on single buffers so I agree it makes more sense to start from the rust regex library than ripgrep. We do however need to continue supporting backrefs and lookaround, so we'll need to add `--auto-hybrid-regex` functionality to fall back to either Node's engine or a webassembly PCRE2. As for wasm vs FFI, it would ideally work in browser (Monaco), which makes wasm the best bet I believe.
      - burntsushi 7y ago
        Ah yeah, for backrefs you'll need to find a way to use PCRE2. Not sure what the WASM story is there. But at that point, if your only problem with Node regexes is catastrophic backtracking, then you might as well just stick with Node. PCRE2 will have the same problem.
- manthideaal 7y ago
  Perhaps to protect against ReDoS the client should use an extended finite automata (1). https://www.arl.wustl.edu/~pcrowley/a25-becchi.pdf https://www.arl.wustl.edu/~pcrowley/a25-becchi.pdf (1) Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions.
  - burntsushi 7y ago
    Nope. That still supports backreferences, and resolving backreferences is an NP-complete problem.[1] And I don't see anything in that paper that addresses that. Note that there may be some versions of the problem that maybe aren't NP-complete[2], but again, not addressed by that paper. Besides, that paper was published 12 years ago. Where is the productionized version of it? Or are you suggesting the the OP go spend a few years writing a regex eninge? :-) Doesn't seem like a particularly practical suggestion. [1] - https://perl.plover.com/NPC/NPC-3SAT.html https://perl.plover.com/NPC/NPC-3SAT.html [2] - https://branchfree.org/2019/04/04/question-is-matching-fixed-regexes-with-back-references-in-p/ https://branchfree.org/2019/04/04/question-is-matching-fixed...
    - manthideaal 7y ago
      In the paper there are some bounds about the number of states in the automata as a function of the length of the input. So one could limit the length of the input when using back references to bound the complexity of the algorithm. They have used their algorithm for snort (network intrusion detection) using asic. The author could contact the authors of the paper and ask for (or pay for) an implementation. By the way, good work ripgrep and rust.

Ripgrep is based on RE2 and supports backrefs. Wonder why they didn't use that.

by jakear 7y ago

Ripgrep is based on RE2 and supports backrefs. Wonder why they didn't use that.

Not quite. ripgrep uses Rust's regex engine, not RE2. Rust's regex engine is descended from RE2, but there is no code sharing. Rust's regex engine does not support backreferences. RE2 does not either. ripgrep does however have a -P/--pcre2 flag which causes it to use PCRE2 instead of Rust's regex engine. PCRE2 supports backreferences and other things, like look-around. (ripgrep also has an --auto-hybrid-regex flag, which will automatically enable PCRE2 for you if you write a regex with backreferences or look-around.) The reason not to use an engine like PCRE2 for a project like this is because it would be trivially exposed to ReDoS: https://en.wikipedia.org/wiki/ReDoS https://en.wikipedia.org/wiki/ReDoS

jakear 7y ago
Thanks for the clarification. As an aside, how difficult do you think it would be to compile ripgrep to wasm? In VS Code we use ripgrep for full-workspace search and Node's regex library for in-memory searches, but this leads to discrepancies and issues such as catastrophic backtracking in the in-memory search.
- burntsushi 7y ago
  I've never tried to compile to WASM. It really depends on how much of the OS APIs need to be fixed. e.g., I don't think WASM supports memory maps as one example. In that case, ripgrep could be made to compile without support for memory maps with a bit of work. But that's an easy case. What other things does WASM not support? What about typical file/directory APIs? I don't think it does, or it least, it looks like Rust's standard library doesn't implement anything for them: https://github.com/rust-lang/rust/blob/master/src/libstd/sys/wasm/fs.rs https://github.com/rust-lang/rust/blob/master/src/libstd/sys... At that point, it would be hopelessly difficult to build ripgrep. The right path then would be to build a new application that uses whatever of ripgrep's libraries make sense. Popping up a level though, why would you want to compile to WASM? If you're using Node, then surely you can build an FFI bridge to Rust's regex library. At least at that point, you'd be using the same regex engine. I even maintain official C bindings for them: https://github.com/rust-lang/regex/tree/master/regex-capi https://github.com/rust-lang/regex/tree/master/regex-capi EDIT: Oh, and not sure if this is useful, but the regex crate itself should compile to WASM just fine. I know I've seen people run it in the browser before. If there's a problem here, then please file a bug!
  - jakear 7y ago
    Thanks for all the advice. We'd just be running it on single buffers so I agree it makes more sense to start from the rust regex library than ripgrep. We do however need to continue supporting backrefs and lookaround, so we'll need to add `--auto-hybrid-regex` functionality to fall back to either Node's engine or a webassembly PCRE2. As for wasm vs FFI, it would ideally work in browser (Monaco), which makes wasm the best bet I believe.
    - burntsushi 7y ago
      Ah yeah, for backrefs you'll need to find a way to use PCRE2. Not sure what the WASM story is there. But at that point, if your only problem with Node regexes is catastrophic backtracking, then you might as well just stick with Node. PCRE2 will have the same problem.
manthideaal 7y ago
Perhaps to protect against ReDoS the client should use an extended finite automata (1). https://www.arl.wustl.edu/~pcrowley/a25-becchi.pdf https://www.arl.wustl.edu/~pcrowley/a25-becchi.pdf (1) Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions.
- burntsushi 7y ago
  Nope. That still supports backreferences, and resolving backreferences is an NP-complete problem.[1] And I don't see anything in that paper that addresses that. Note that there may be some versions of the problem that maybe aren't NP-complete[2], but again, not addressed by that paper. Besides, that paper was published 12 years ago. Where is the productionized version of it? Or are you suggesting the the OP go spend a few years writing a regex eninge? :-) Doesn't seem like a particularly practical suggestion. [1] - https://perl.plover.com/NPC/NPC-3SAT.html https://perl.plover.com/NPC/NPC-3SAT.html [2] - https://branchfree.org/2019/04/04/question-is-matching-fixed-regexes-with-back-references-in-p/ https://branchfree.org/2019/04/04/question-is-matching-fixed...
  - manthideaal 7y ago
    In the paper there are some bounds about the number of states in the automata as a function of the length of the input. So one could limit the length of the input when using back references to bound the complexity of the algorithm. They have used their algorithm for snort (network intrusion detection) using asic. The author could contact the authors of the paper and ask for (or pay for) an implementation. By the way, good work ripgrep and rust.