[arnsholt]

To be fair, the reason Perl, Python and PCRE (which all use pretty much the same regex syntax) don't use the linear-time algorithms is because they can't. Features like look-around and matching what you've already matched (/(\w+) \1/ to find repeated words for example) give you more expressivity than regular languages, but also takes away linear time algorithms.

[fasdg]

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]

Seems 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]

I 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.

[snprbob86]

Hence 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.

[xyzzyz]

But the user may not necessarily know it.