7 ms·

Debugging catastrophic backtracking for regular expressions in Python

22 points by EntICOnc 3y ago

patrickmay 3y 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 3y ago
  "You can't parse [X]HTML with regex. [...]" (2009) https://stackoverflow.com/a/1732454 https://stackoverflow.com/a/1732454
js2 3y ago
Use re2 instead. It's nearly a drop-in replacement: https://github.com/google/re2 https://github.com/google/re2 There are python bindings: https://pypi.org/project/google-re2/ 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-1648722342 https://github.com/tuist/xcbeautify/issues/138#issuecomment-...
- dataflow 3y 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.
  - burntsushi 3y 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.
    - dataflow 3y ago
      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.
      - burntsushi 3y ago
        > 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.
- ketralnis 3y 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 :)
  - burntsushi 3y 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).
  - yatac42 3y 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.
    - yatac42 3y ago
      And perhaps more relevantly, the regex from the article also works fine in RE2.
userbinator 3y ago
No discussion about exponential backtracking in regexes is complete without a mention of this infamous article: https://swtch.com/~rsc/regexp/regexp1.html 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 3y ago
  What's wrong with that article? It seems like a pretty interesting resource.

22 points by EntICOnc 3y 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 3y ago
"You can't parse [X]HTML with regex. [...]" (2009) https://stackoverflow.com/a/1732454 https://stackoverflow.com/a/1732454

js2 3y ago

Use re2 instead. It's nearly a drop-in replacement: https://github.com/google/re2 https://github.com/google/re2 There are python bindings: https://pypi.org/project/google-re2/ 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-1648722342 https://github.com/tuist/xcbeautify/issues/138#issuecomment-...

dataflow 3y 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.
- burntsushi 3y 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.
  - dataflow 3y ago
    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.
    - burntsushi 3y ago
      > 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.
ketralnis 3y 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 :)
- burntsushi 3y 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).
- yatac42 3y 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.
  - yatac42 3y ago
    And perhaps more relevantly, the regex from the article also works fine in RE2.

userbinator 3y ago

No discussion about exponential backtracking in regexes is complete without a mention of this infamous article: https://swtch.com/~rsc/regexp/regexp1.html 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 3y ago
What's wrong with that article? It seems like a pretty interesting resource.