Debugging catastrophic backtracking for regular expressions in Python
krishnanchandra.com
krishnanchandra.com
That said, looking at this particular application, I would not use a regex at all, but simple substring scanning.
There are python bindings:
https://pypi.org/project/google-re2/
I just had to point out a similar problem in a Swift project. I'd like to submit a PR to switch that project to re2 but I haven't been able to make the time yet.
https://github.com/tuist/xcbeautify/issues/138#issuecomment-...
Erm, not really. That's like calling a fan a near-drop-in-replacement for air conditioning. It's certainly useful, but the functionality it lacks (albeit for good reason) can be rather critical - e.g., it can't do lookarounds.
Usually look-around can be replaced with two regexes or by just using capture groups. Not always of course, and it depends on whether a regex is the interface to what you're using. This is why, for example, I caved and added optional PCRE2 support to ripgrep. Since the interface is a regex, you don't have the full flexibility that you would if you were using a regex from a programming language.
> Look-around is rarely critical functionality
I have to disagree; I've seen them be needed enough to find them critical. (more below)
> when you don't have the full flexibility that you would if you were using a regex from a programming language.
But that's exactly my point - the cases where you can work around it with a programming language is the rare case, not the common one. The only cases where I'd say lookarounds are non-critical are a fraction of those situations where the developer is the one hard-coding the regex. That might be the case if you're prototyping something like a lexer (where the user is the developer), but that's not the majority of cases. And in those cases, you can (and likely will) hard-code a faster implementation anyway.
The much more common cases I see are the regexes that can be specified at run time, where making user write code or jump through other hoops is something between painful and impossible. I feel you argued against your own point in reference to ripgrep, honestly -- because these are the 2 most common situations where I see regexes:
1. Find/replace in text editors. This is probably the most common use of regexes I see. Here, backreferences or lookarounds are absolutely necessary for some replacements.
2. File names/paths, in command-lines or configuration files or such. Lookarounds (and sometimes backreferences) are such a critical tool here. Imagine the difference between being able to write a negation like '^(?!.*/\.(cache|git|svn)/).*[Bb]urnt[Ss]ushi' vs. not being able to.
That's essentially what I acknowledged: when the regex is the interface.
From my point of view, my previous comment anticipated this critque already. The only real difference I can see is a disagreement about how common it is. We won't resolve that one.
I've been using regexes for decades. The number of times I've used look-around or even back-references can be counted on one hand. I can't even remember the last time I used it at all.
I'm shocked. What do you most commonly use regexes for? For me, I type them in my text editor find/replace more frequently than anything, and use backreferences there on a pretty regular basis.
I also use regexes with ripgrep of course. ripgrep has features that standard grep doesn't have that typically mitigate the need for look-around, such as the `-r/--replace` flag. (I can't remember I when I last used `-P/--pcre2` in ripgrep for a reason that wasn't testing it.)
Otherwise the rest of my regex use is in programs for a variety of tasks.
Note that I'm the author of Rust's regex crate and of this regex benchmark: https://github.com/BurntSushi/rebar
I'll note that Discord also uses the regex crate for something to do with automod[1]. It would be interesting to ask their users how often they're annoyed by the lack of look-around or backreferences or some other fancy feature. Although in their case, the linear time guarantee is likely essential to exposing regex support in the first place.
[1]: https://support.discord.com/hc/en-us/articles/10069840290711...
For context on why, python's in-built re library is a backtracking regex implementation (as are most) but google's re2 uses a DFA-based system instead that just doesn't support the kinds of regexes that catastrophically backtrack (well, re2 can can fall back to its NFA approach instead which can handle the same kinds of backtracking regexes that re can, but this fallback can be disabled.)
It's also incidentally quite a lot faster for many of the common cases. I swapped re->re2 for an internal rules engine relying heavily on regexes that needed to be robust to novice users and got roughly twice the performance out of it as a happy side effect. For my purposes it was fully drop-in, just swapping out some imports. The only downside was that the regexes that I was explicitly choosing not to support anymore now errored out as intended (and the users that wrote them were given workarounds but not lookarounds :)
There are certain fearures that are harder or impossible to implement with RE2's approach, but it's not true that it doesn't support the kind of regex that would catastrophically backtrack using a backtracking engine.
`(.*a)*b` would be a (silly) example of a regex that can catastrophically backtrack using backtracking engines and re2 supports it just fine without backtracking.
Hmmm, kinda sorta. Regular languages are closed under complement and intersection, but RE2 doesn't support them. They are difficult to implement efficiently, particularly with respect to building the regex. There are some issues on the RE2 issue tracker about this.
Of course, you could say that you could always rewrite a regex using complement or intersection to an equivalent regex that doesn't use those operations. While true, such a feat is usually quite tricky. So treat this comment as adding more clarity as opposed to me trying to correct you perhaps. :-)
Complement and intersection are not implemented in any "general purpose" regex engine that I know of. You tend to find them in more specialty projects like redgrep[1] or in libraries specifically devoted to the construction and manipulation of DFAs. (RE2 doesn't have such a thing, only a lazy DFA, because full DFAs are too expensive to build in the "general purpose" context.)
— John Von Neumann