Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

Commitf68970e

Browse files
committed
Fix performance issue in new regex match-all detection code.
Commit824bf71 introduced a new search of the NFAs generated byregex compilation. I failed to think hard about the performancecharacteristics of that search, with the predictable outcomethat it's bad: weird regexes can trigger exponential search time.Worse, there's no check-for-interrupt in that code, so you can'teven cancel the query if this happens.Fix by introducing memo-ization of the search results, so that any oneNFA state need be examined in detail just once. This potentially usesa lot of memory, but we can bound the memory usage by putting a limiton the number of states for which we'll try to prove match-all-ness.That is sane because we already have a limit (DUPINF) on the maximumfinite string length that a matchall regex can match; and patternsthat involve much more than DUPINF states would probably exceed thatlimit anyway.Also, rearrange the logic so that we check the basic is-the-graph-all-RAINBOW-arcs property before we start the recursive search todetermine path lengths. This will ensure that we fall out quicklywhenever the NFA couldn't possibly be matchall.Also stick in a check-for-interrupt, just in case these measuresdon't completely eliminate the risk of slowness.Discussion:https://postgr.es/m/3483895.1619898362@sss.pgh.pa.us
1 parentb94409a commitf68970e

File tree

4 files changed

+366
-163
lines changed

4 files changed

+366
-163
lines changed

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp