Debugging catastrophic backtracking for regular expressions in Python

https://krishnanchandra.com/posts/regex-catastrophic-backtracking/

by EntICOnc • 3 years ago

22 19 3 years ago

patrickmay• 3 years ago

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

AceJohnny2• 3 years ago

"You can't parse [X]HTML with regex. [...]" (2009)

https://stackoverflow.com/a/1732454

js2• 3 years ago

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

dataflow4• 3 years ago

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.

burntsushi6• 3 years ago

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.

ketralnis• 3 years ago

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 :)

burntsushi6• 3 years ago

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

yatac422• 3 years ago

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.

userbinator• 3 years ago

No discussion about exponential backtracking in regexes is complete without a mention of this infamous article: https://swtch.com/~rsc/regexp/regexp1.html

That said, looking at this particular application, I would not use a regex at all, but simple substring scanning.

richbell• 3 years ago

What's wrong with that article? It seems like a pretty interesting resource.

Debugging catastrophic backtracking for regular expressions in Python

Related Stories