Skip to content

Commit b1ca28e

Browse files
tglsfdctglsfdc
committed
Fix misoptimization of "{1,1}" quantifiers in regular expressions.
A bounded quantifier with m = n = 1 might be thought a no-op. But according to our documentation (which traces back to Henry Spencer's original man page) it still imposes greediness, or non-greediness in the case of the non-greedy variant "{1,1}?", on whatever it's attached to. This turns out not to work though, because parseqatom() optimizes away the m = n = 1 case without regard for whether it's supposed to change the greediness of the argument RE. We can fix this by just not applying the optimization when the greediness needs to change; the subsequent general cases handle it fine. The three cases in which we can still apply the optimization are (a) no quantifier, or quantifier does not impose a preference; (b) atom has no greediness property, implying it cannot match a variable amount of text anyway; or (c) quantifier's greediness is same as atom's. Note that in most cases where one of these applies, we'd have exited earlier in the "not a messy case" fast path. I think it's now only possible to get to the optimization when the atom involves capturing parentheses or a non-top-level backref. Back-patch to all supported branches. I'd ordinarily be hesitant to put a subtle behavioral change into back branches, but in this case it's very hard to see a reason why somebody would write "{1,1}?" unless they're trying to get the documented change-of-greediness behavior. Discussion: https://postgr.es/m/5bb27a41-350d-37bf-901e-9d26f5592dd0@charter.net
1 parent 08e3fd9 commit b1ca28e

File tree

3 files changed

+63
-1
lines changed

3 files changed

+63
-1
lines changed

‎src/backend/regex/regcomp.c

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1147,7 +1147,10 @@ parseqatom(struct vars * v,
11471147
/* rest of branch can be strung starting from atom->end */
11481148
s2 = atom->end;
11491149
}
1150-
else if (m == 1 && n == 1)
1150+
else if (m == 1 && n == 1 &&
1151+
(qprefer == 0 ||
1152+
(atom->flags & (LONGER | SHORTER | MIXED)) == 0 ||
1153+
qprefer == (atom->flags & (LONGER | SHORTER | MIXED))))
11511154
{
11521155
/* no/vacuous quantifier: done */
11531156
EMPTYARC(s, atom->begin); /* empty prefix */

‎src/test/regress/expected/regex.out

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -295,6 +295,55 @@ select regexp_matches('foo/bar/baz',
295295
{foo,bar,baz}
296296
(1 row)
297297

298+
-- Test that greediness can be overridden by outer quantifier
299+
select regexp_matches('llmmmfff', '^(l*)(.*)(f*)$');
300+
regexp_matches
301+
----------------
302+
{ll,mmmfff,""}
303+
(1 row)
304+
305+
select regexp_matches('llmmmfff', '^(l*){1,1}(.*)(f*)$');
306+
regexp_matches
307+
----------------
308+
{ll,mmmfff,""}
309+
(1 row)
310+
311+
select regexp_matches('llmmmfff', '^(l*){1,1}?(.*)(f*)$');
312+
regexp_matches
313+
------------------
314+
{"",llmmmfff,""}
315+
(1 row)
316+
317+
select regexp_matches('llmmmfff', '^(l*){1,1}?(.*){1,1}?(f*)$');
318+
regexp_matches
319+
----------------
320+
{"",llmmm,fff}
321+
(1 row)
322+
323+
select regexp_matches('llmmmfff', '^(l*?)(.*)(f*)$');
324+
regexp_matches
325+
------------------
326+
{"",llmmmfff,""}
327+
(1 row)
328+
329+
select regexp_matches('llmmmfff', '^(l*?){1,1}(.*)(f*)$');
330+
regexp_matches
331+
----------------
332+
{ll,mmmfff,""}
333+
(1 row)
334+
335+
select regexp_matches('llmmmfff', '^(l*?){1,1}?(.*)(f*)$');
336+
regexp_matches
337+
------------------
338+
{"",llmmmfff,""}
339+
(1 row)
340+
341+
select regexp_matches('llmmmfff', '^(l*?){1,1}?(.*){1,1}?(f*)$');
342+
regexp_matches
343+
----------------
344+
{"",llmmm,fff}
345+
(1 row)
346+
298347
-- Test for infinite loop in cfindloop with zero-length possible match
299348
-- but no actual match (can only happen in the presence of backrefs)
300349
select 'a' ~ '$()|^\1';

‎src/test/regress/sql/regex.sql

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -76,6 +76,16 @@ select regexp_matches('Programmer', '(\w)(.*?\1)', 'g');
7676
select regexp_matches('foo/bar/baz',
7777
'^([^/]+?)(?:/([^/]+?))(?:/([^/]+?))?$', '');
7878

79+
-- Test that greediness can be overridden by outer quantifier
80+
select regexp_matches('llmmmfff', '^(l*)(.*)(f*)$');
81+
select regexp_matches('llmmmfff', '^(l*){1,1}(.*)(f*)$');
82+
select regexp_matches('llmmmfff', '^(l*){1,1}?(.*)(f*)$');
83+
select regexp_matches('llmmmfff', '^(l*){1,1}?(.*){1,1}?(f*)$');
84+
select regexp_matches('llmmmfff', '^(l*?)(.*)(f*)$');
85+
select regexp_matches('llmmmfff', '^(l*?){1,1}(.*)(f*)$');
86+
select regexp_matches('llmmmfff', '^(l*?){1,1}?(.*)(f*)$');
87+
select regexp_matches('llmmmfff', '^(l*?){1,1}?(.*){1,1}?(f*)$');
88+
7989
-- Test for infinite loop in cfindloop with zero-length possible match
8090
-- but no actual match (can only happen in the presence of backrefs)
8191
select 'a' ~ '$()|^\1';

0 commit comments

Comments
 (0)