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

Commitfacce1d

Browse files
committed
Fix performance bug in regexp's citerdissect/creviterdissect.
After detecting a sub-match "dissect" failure (i.e., a backref matchfailure) in the i'th sub-match of an iteration node, we should proceedby adjusting the attempted length of the i'th submatch. As coded,though, these functions changed the attempted length of the *last*sub-match, and only after exhausting all possibilities for that wouldthey back up to adjust the next-to-last sub-match, and then thesecond-from-last, etc; all of which is wasted effort, since onlychanging the start or length of the i'th sub-match can possibly makeit succeed. This oversight creates the possibility for exponentiallybad performance. Fortunately the problem is masked in most cases byoptimizations or constraints applied elsewhere; which explains whywe'd not noticed it before. But it is possible to reach the problemwith fairly simple, if contrived, regexps.Oversight in my commit173e29a. That's pretty ancient now,so back-patch to all supported branches.Discussion:https://postgr.es/m/1808998.1629412269@sss.pgh.pa.us
1 parent9a9c8b9 commitfacce1d

File tree

1 file changed

+10
-8
lines changed

1 file changed

+10
-8
lines changed

‎src/backend/regex/regexec.c‎

Lines changed: 10 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1147,8 +1147,8 @@ citerdissect(struct vars *v,
11471147
* Our strategy is to first find a set of sub-match endpoints that are
11481148
* valid according to the child node's DFA, and then recursively dissect
11491149
* each sub-match to confirm validity. If any validity check fails,
1150-
* backtrackthe lastsub-match and try again. And, when we next try for
1151-
*avalidity check, we need not recheck any successfully verified
1150+
* backtrackthatsub-match and try again. And, when we next try for a
1151+
* validity check, we need not recheck any successfully verified
11521152
* sub-matches that we didn't move the endpoints of. nverified remembers
11531153
* how many sub-matches are currently known okay.
11541154
*/
@@ -1236,12 +1236,13 @@ citerdissect(struct vars *v,
12361236
returnREG_OKAY;
12371237
}
12381238

1239-
/* match failed to verify, so backtrack */
1239+
/* i'th match failed to verify, so backtrack it */
1240+
k=i;
12401241

12411242
backtrack:
12421243

12431244
/*
1244-
* Must consider shorter versions of thecurrent sub-match. However,
1245+
* Must consider shorter versions of thek'th sub-match. However,
12451246
* we'll only ask for a zero-length match if necessary.
12461247
*/
12471248
while (k>0)
@@ -1352,8 +1353,8 @@ creviterdissect(struct vars *v,
13521353
* Our strategy is to first find a set of sub-match endpoints that are
13531354
* valid according to the child node's DFA, and then recursively dissect
13541355
* each sub-match to confirm validity. If any validity check fails,
1355-
* backtrackthe lastsub-match and try again. And, when we next try for
1356-
*avalidity check, we need not recheck any successfully verified
1356+
* backtrackthatsub-match and try again. And, when we next try for a
1357+
* validity check, we need not recheck any successfully verified
13571358
* sub-matches that we didn't move the endpoints of. nverified remembers
13581359
* how many sub-matches are currently known okay.
13591360
*/
@@ -1447,12 +1448,13 @@ creviterdissect(struct vars *v,
14471448
returnREG_OKAY;
14481449
}
14491450

1450-
/* match failed to verify, so backtrack */
1451+
/* i'th match failed to verify, so backtrack it */
1452+
k=i;
14511453

14521454
backtrack:
14531455

14541456
/*
1455-
* Must consider longer versions of thecurrent sub-match.
1457+
* Must consider longer versions of thek'th sub-match.
14561458
*/
14571459
while (k>0)
14581460
{

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp