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.

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

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.

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.

But the user may not necessarily know it.

Confirming that Fedora 16 is affected, with the latest updates as of the time of this writing.

No, they don't. Be wary. I tried to use btrfs in raid10 (data and metadata) mode for my latest array of large disks (4x 2TB WD Caviar Blacks); 70 GB in copying data from my old md array, I got a kernel OOPS. This was with very recent btrfs code -- Fedora 16 with a 3.1.x kernel and btrfs-progs-0.19-16.fc16. It's simply not ready.