6 ms·
As Russ points out in his earlier re2-related blog posts, these regex engines still perform non-linearly on inputs which don't involve look-around, look-behind,
by fasdg 15y ago
As Russ points out in his earlier re2-related blog posts, these regex engines still perform non-linearly on inputs which don't involve look-around, look-behind, etc. There's plenty of room for improvement even if they want to keep these features.
- snprbob86 15y agoSeems like the default should be linear runtime and you should have to explicitly ask for the richer feature set (and opt into the assertion that you trust the input not to DOS your process). Could easily be added as a modifier (see `man perlre`), but should be implemented as two to enable explicit behavior and toggling the default. Randomly picking the letter N: /(\w+) \1/n # Error: look-behind is incompatible with linear runtime RE engine /(\w+) \1/N # Works! /(\w+) \1/ # Preferable works for backwards compat, maybe overridden by an ENV var
- mdwrigh2 15y agoI don't think you need to even go as far as adding a modifier. A smart enough regex engine would know when it could use the linear runtime algorithm, and when it needs to fall back.
- xyzzyz 15y agoBut the user may not necessarily know it.
- snprbob86 15y agoHence my last example without the modifier & the comment saying it should work. My claim was that there should be a modifier to demand a particular performance characteristic. i.e. "I want an error if I do something stupid" Assuming that means that a library function exists to verify that no linearity-breaking features are used, you could also use that to validate user input, which may be good enough.