I agree with (2). (1) is in theory right, but it's very rare to see it done. The only one I'm aware of actually doing a "switch between linear time and unbound

I agree with (2). (1) is in theory right, but it's very rare to see it done. The only one I'm aware of actually doing a "switch between linear time and unbounded backtracking" is Tcl, and I'm not familiar enough with it to know if it actually gives any guarantees. The difficulty in (1) is rooted in: 1) implementation complexity, 2) performance and 3) match semantics. (1)+(2) are related, and indeed, if you want your linear time engine to compete with your backtracker engine, you're going to need to do a fair bit of work. (3) is also quite tricky. Cox's RE2 paves the path for how to get linear time engines to mostly agree with backtrackers, but there may be some corner cases where there is some disagreement. So for something like Python, (3) may be quite difficult to overcome. Popping up a level, I'm not sure how relevant all of this is to your overall point. As the author of Rust's regex crate, I actually generally agree with your post, insomuch as catastrophic backtracking is handled as a security vulnerability. I'm mostly just picking at nits and elaborating here.