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

Commit6cfaffc

Browse files
committed
Fix regexport.c to behave sanely with lookaround constraints.
regexport.c thought it could just ignore LACON arcs, but the correctbehavior is to treat them as satisfiable while consuming zero input(rather reminiscently of commit9f1e642). Otherwise, the emittedsimplified-NFA representation may contain no paths leading from initialto final state, which unsurprisingly confuses pg_trgm, as seen inbug #14623 from Jeff Janes.Since regexport's output representation has no concept of an arc thatconsumes zero input, recurse internally to find the next normal arc(s)after any LACON transitions. We'd be forced into changing thatrepresentation if a LACON could be the last arc reaching the finalstate, but fortunately the regex library never builds NFAs with sucha configuration, so there always is a next normal arc.Back-patch to 9.3 where this logic was introduced.Discussion:https://postgr.es/m/20170413180503.25948.94871@wrigleys.postgresql.org
1 parent885fea5 commit6cfaffc

File tree

3 files changed

+80
-25
lines changed

3 files changed

+80
-25
lines changed

‎contrib/pg_trgm/expected/pg_trgm.out

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3684,6 +3684,12 @@ select * from test2 where t ~ ' z foo';
36843684
z foo bar
36853685
(1 row)
36863686

3687+
select * from test2 where t ~ 'qua(?!foo)';
3688+
t
3689+
-------
3690+
quark
3691+
(1 row)
3692+
36873693
drop index test2_idx_gin;
36883694
create index test2_idx_gist on test2 using gist (t gist_trgm_ops);
36893695
set enable_seqscan=off;
@@ -3864,6 +3870,12 @@ select * from test2 where t ~ ' z foo';
38643870
z foo bar
38653871
(1 row)
38663872

3873+
select * from test2 where t ~ 'qua(?!foo)';
3874+
t
3875+
-------
3876+
quark
3877+
(1 row)
3878+
38673879
-- Check similarity threshold (bug #14202)
38683880
CREATE TEMP TABLE restaurants (city text);
38693881
INSERT INTO restaurants SELECT 'Warsaw' FROM generate_series(1, 10000);

‎contrib/pg_trgm/sql/pg_trgm.sql

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -86,7 +86,9 @@ select * from test2 where t ~ 'z foo bar';
8686
select*from test2where t ~' z foo bar';
8787
select*from test2where t ~' z foo bar';
8888
select*from test2where t ~' z foo';
89+
select*from test2where t ~'qua(?!foo)';
8990
dropindex test2_idx_gin;
91+
9092
createindextest2_idx_giston test2 using gist (t gist_trgm_ops);
9193
set enable_seqscan=off;
9294
explain (costs off)
@@ -121,6 +123,7 @@ select * from test2 where t ~ 'z foo bar';
121123
select*from test2where t ~' z foo bar';
122124
select*from test2where t ~' z foo bar';
123125
select*from test2where t ~' z foo';
126+
select*from test2where t ~'qua(?!foo)';
124127

125128
-- Check similarity threshold (bug #14202)
126129

‎src/backend/regex/regexport.c

Lines changed: 65 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -6,8 +6,8 @@
66
* In this implementation, the NFA defines a necessary but not sufficient
77
* condition for a string to match the regex: that is, there can be strings
88
* that match the NFA but don't match the full regex, but not vice versa.
9-
* Thus, for example, it is okay for the functions below toignore lookaround
10-
* constraints, which merely constrain the string some more.
9+
* Thus, for example, it is okay for the functions below totreat lookaround
10+
* constraints as no-ops, since they merely constrain the string some more.
1111
*
1212
* Notice that these functions return info into caller-provided arrays
1313
* rather than doing their own malloc's. This simplifies the APIs by
@@ -72,29 +72,78 @@ pg_reg_getfinalstate(const regex_t *regex)
7272
}
7373

7474
/*
75-
* Get number of outgoing NFA arcs of state number "st".
75+
* pg_reg_getnumoutarcs() and pg_reg_getoutarcs() mask the existence of LACON
76+
* arcs from the caller, treating any LACON as being automatically satisfied.
77+
* Since the output representation does not support arcs that consume no
78+
* character when traversed, we have to recursively traverse LACON arcs here,
79+
* and report whatever normal arcs are reachable by traversing LACON arcs.
80+
* Note that this wouldn't work if it were possible to reach the final state
81+
* via LACON traversal, but the regex library never builds NFAs that have
82+
* LACON arcs leading directly to the final state. (This is because the
83+
* regex executor is designed to consume one character beyond the nominal
84+
* match end --- possibly an EOS indicator --- so there is always a set of
85+
* ordinary arcs leading to the final state.)
7686
*
77-
* Note: LACON arcs are ignored, both here and in pg_reg_getoutarcs().
87+
* traverse_lacons is a recursive subroutine used by both exported functions
88+
* to count and then emit the reachable regular arcs. *arcs_count is
89+
* incremented by the number of reachable arcs, and as many as will fit in
90+
* arcs_len (possibly 0) are emitted into arcs[].
91+
*/
92+
staticvoid
93+
traverse_lacons(structcnfa*cnfa,intst,
94+
int*arcs_count,
95+
regex_arc_t*arcs,intarcs_len)
96+
{
97+
structcarc*ca;
98+
99+
/*
100+
* Since this function recurses, it could theoretically be driven to stack
101+
* overflow. In practice, this is mostly useful to backstop against a
102+
* failure of the regex compiler to remove a loop of LACON arcs.
103+
*/
104+
check_stack_depth();
105+
106+
for (ca=cnfa->states[st];ca->co!=COLORLESS;ca++)
107+
{
108+
if (ca->co<cnfa->ncolors)
109+
{
110+
/* Ordinary arc, so count and possibly emit it */
111+
intndx= (*arcs_count)++;
112+
113+
if (ndx<arcs_len)
114+
{
115+
arcs[ndx].co=ca->co;
116+
arcs[ndx].to=ca->to;
117+
}
118+
}
119+
else
120+
{
121+
/* LACON arc --- assume it's satisfied and recurse... */
122+
/* ... but first, assert it doesn't lead directly to post state */
123+
Assert(ca->to!=cnfa->post);
124+
125+
traverse_lacons(cnfa,ca->to,arcs_count,arcs,arcs_len);
126+
}
127+
}
128+
}
129+
130+
/*
131+
* Get number of outgoing NFA arcs of state number "st".
78132
*/
79133
int
80134
pg_reg_getnumoutarcs(constregex_t*regex,intst)
81135
{
82136
structcnfa*cnfa;
83-
structcarc*ca;
84-
intcount;
137+
intarcs_count;
85138

86139
assert(regex!=NULL&&regex->re_magic==REMAGIC);
87140
cnfa=&((structguts*)regex->re_guts)->search;
88141

89142
if (st<0||st >=cnfa->nstates)
90143
return0;
91-
count=0;
92-
for (ca=cnfa->states[st];ca->co!=COLORLESS;ca++)
93-
{
94-
if (ca->co<cnfa->ncolors)
95-
count++;
96-
}
97-
returncount;
144+
arcs_count=0;
145+
traverse_lacons(cnfa,st,&arcs_count,NULL,0);
146+
returnarcs_count;
98147
}
99148

100149
/*
@@ -107,24 +156,15 @@ pg_reg_getoutarcs(const regex_t *regex, int st,
107156
regex_arc_t*arcs,intarcs_len)
108157
{
109158
structcnfa*cnfa;
110-
structcarc*ca;
159+
intarcs_count;
111160

112161
assert(regex!=NULL&&regex->re_magic==REMAGIC);
113162
cnfa=&((structguts*)regex->re_guts)->search;
114163

115164
if (st<0||st >=cnfa->nstates||arcs_len <=0)
116165
return;
117-
for (ca=cnfa->states[st];ca->co!=COLORLESS;ca++)
118-
{
119-
if (ca->co<cnfa->ncolors)
120-
{
121-
arcs->co=ca->co;
122-
arcs->to=ca->to;
123-
arcs++;
124-
if (--arcs_len==0)
125-
break;
126-
}
127-
}
166+
arcs_count=0;
167+
traverse_lacons(cnfa,st,&arcs_count,arcs,arcs_len);
128168
}
129169

130170
/*

0 commit comments

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