Debugging catastrophic backtracking for regular expressions in Python(krishnanchandra.com)
krishnanchandra.com
Debugging catastrophic backtracking for regular expressions in Python
https://krishnanchandra.com/posts/regex-catastrophic-backtracking/
3 comments
What's wrong with that article? It seems like a pretty interesting resource.
Use re2 instead. It's nearly a drop-in replacement:
https://github.com/google/re2
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-...
https://github.com/google/re2
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-...
I wouldn't go so far as "use re2 instead" of re for everything as a superstitious "X tool is objectively better than Y tool" but if you're performance bound on regexes definitely do look at re2.
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 :)
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 :)
> re2 uses a DFA-based system instead that just doesn't support the kinds of regexes that catastrophically backtrack
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.
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.
If it's actually a _regular_ expression, by definition re2 will support it. Of course if by "regular expression" you mean pcre (with things like subpatterns) then this can actually match a many context-free languages as well, and if you're doing that then you probably want a proper parser anyway instead of trying to roll one yourself.
> If it's actually a _regular_ expression, by definition re2 will support it.
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.)
[1]: https://github.com/google/redgrep
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.)
[1]: https://github.com/google/redgrep
[deleted]
And perhaps more relevantly, the regex from the article also works fine in RE2.
Small correction: the RE2 C++ library does have a backtracker, but it doesn't enable any extra expressive power in the regex syntax. It is purely an optimization. It uses memory to guarantee linear time search (assuming the size of the regex is held as a constant).
> It's nearly a drop-in replacement
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.
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.
I think a better analogy than "fan versus air conditioning" would be "window air conditioning versus central air." Look-around is rarely critical functionality, and so whether it's window or central, you're staying cool. The difference is that with window air conditioning, you've got to install them in the appropriate rooms and then uninstall them. It's a bit more work, but it still gets the job done.
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.
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.
I find that to be a much worse analogy! In your analogy the difference is in everything other than functionality (they all cool the room); here, the difference is in the functionality -- re2 literally cannot match against some patterns. Moreover, writing more code around re2 to hack around its limitations is like constantly pumping water over a fan to improvise an evaporative AC unit, not like installing a window AC unit once and then being able to forget about the difference.
> 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.
> 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.
> The much more common cases I see are the regexes that can be specified at run time
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.
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.
> The number of times I've used look-around or even back-references can be counted on one hand.
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'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.
Yes, I use regexes in vim all the time. Never use look-around or really much regex features beyond the basics. 99% of all searches are easily just literals.
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 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
Yeah I know who you are, that's why I was shocked. That's why I'd have thought you leverage regexes more than other folks, not less! On my end I do this all the time. E.g., a very common regex search/replace I do over and over is something like removing duplicate lines, e.g. replacing "^(.*)\n\1\n" with "\1\n" repeatedly. (Obviously exact deduplication you can do a different way, but you can imagine variations on it that are case-specific, e.g. removing all lines or table fields that are prefixes of the following ones.) Of course I'm not claiming this is the majority of my searches (literals are obviously far more common like you said), but this kind of stuff comes up quite regularly, on perhaps a ~weekly basis if not more frequently. I'm very surprised you don't do transformations like these!
For that one in particular, nope. The only thing I can think of is when I'm trying to count occurrences of something, but that's just `sort | uniq -c`.
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...
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...
Any one who considers ~arithmetical methods of producing random digits~ parsing HTML with a regex is, of course, in a state of sin.
— John Von Neumann
— John Von Neumann
"You can't parse [X]HTML with regex. [...]" (2009)
https://stackoverflow.com/a/1732454
https://stackoverflow.com/a/1732454
That said, looking at this particular application, I would not use a regex at all, but simple substring scanning.