From: Tom Lane <tgl@sss.pgh.pa.us>
To: Aleksander Alekseev <aleksander@timescale.com>
Cc: dhyan@nataraj.su
Cc: pgsql-bugs@lists.postgresql.org
Subject: Re: BUG #18708: regex problem: (?:[^\d\D]){0} asserts with "lp->nouts == 0 && rp->nins == 0"
Date: Thu, 14 Nov 2024 21:14:27 -0500
Message-ID: <2344149.1731636867@sss.pgh.pa.us> (raw)
In-Reply-To: <2242483.1731627374@sss.pgh.pa.us>
References: <18708-f94f2599c9d2c005@postgresql.org>
<CAJ7c6TMPSrcbzkX0ePnNTbh7M22hRiPfD0KOcW4L9YjdbnF0Ug@mail.gmail.com>
<2242483.1731627374@sss.pgh.pa.us>
I wrote:
> So I think the right thing to do is to fix colorcomplement() so
> that it still produces some arc between its "from" and "to"
> states, keeping the graph connected until we finish parsing the
> regex. It has to be a dummy arc that can't match anything, of
> course. We can throw away such an arc once we get to regex
> optimization, because we don't need delsub() to work anymore.
> In the attached draft patch I represented the dummy arc as a PLAIN
> arc with a new fake color BLACK. Another way to do it could be to
> introduce a new arc "type" value, but that seemed like it would
> involve touching more code.
After thinking awhile longer, I decided to try it that way (with
a new arc type), and I believe I like the result better after all.
It's just a few lines more code, and I think it's more robust.
Up to now PLAIN arcs always matched exactly one character,
so the first version was putting a major dent in their semantics.
We got rid of the bogus arcs before doing anything that really leans
hard on arc semantics, but still it seems messy. Hence v2 attached.
I'm not especially in love with the CANTMATCH arc type name, but
other possibilities such as DUMMY or NOMATCH felt too generic.
Better ideas anyone?
regards, tom lane
Attachments:v2-fix-bug-18708.patch (text/x-diff, 6.8K) downloaddiff --git a/src/backend/regex/regc_color.c b/src/backend/regex/regc_color.cindex 30bda0e5ad..8ae788f519 100644--- a/src/backend/regex/regc_color.c+++ b/src/backend/regex/regc_color.c@@ -1075,9 +1075,19 @@ colorcomplement(struct nfa *nfa,
assert(of != from);
- /* A RAINBOW arc matches all colors, making the complement empty */+ /*+ * A RAINBOW arc matches all colors, making the complement empty. But we+ * can't just return without making any arcs, because that would leave the+ * NFA disconnected which would break any future delsub(). Instead, make+ * a CANTMATCH arc. Also set the HASCANTMATCH flag so we know we need to+ * clean that up at the start of NFA optimization.+ */
if (findarc(of, PLAIN, RAINBOW) != NULL)
+ {+ newarc(nfa, CANTMATCH, 0, from, to);+ nfa->flags |= HASCANTMATCH;
return;
+ }
/* Otherwise, transiently mark the colors that appear in of's out-arcs */
for (a = of->outs; a != NULL; a = a->outchain)
@@ -1089,6 +1099,12 @@ colorcomplement(struct nfa *nfa,
assert(!UNUSEDCOLOR(cd));
cd->flags |= COLMARK;
}
++ /*+ * There's no syntax for re-complementing a color set, so we cannot+ * see CANTMATCH arcs here.+ */+ assert(a->type != CANTMATCH);
}
/* Scan colors, clear transient marks, add arcs for unmarked colors */
diff --git a/src/backend/regex/regc_nfa.c b/src/backend/regex/regc_nfa.cindex f1819a24f6..acd2286def 100644--- a/src/backend/regex/regc_nfa.c+++ b/src/backend/regex/regc_nfa.c@@ -1462,6 +1462,7 @@ removetraverse(struct nfa *nfa,
{
case PLAIN:
case EMPTY:
+ case CANTMATCH:
/* nothing to do */
break;
case AHEAD:
@@ -1599,6 +1600,12 @@ optimize(struct nfa *nfa,
if (verbose)
fprintf(f, "\ninitial cleanup:\n");
#endif
+ /* If we have any CANTMATCH arcs, drop them; but this is uncommon */+ if (nfa->flags & HASCANTMATCH)+ {+ removecantmatch(nfa);+ nfa->flags &= ~HASCANTMATCH;+ }
cleanup(nfa); /* may simplify situation */
#ifdef REG_DEBUG
if (verbose)
@@ -2922,6 +2929,34 @@ clonesuccessorstates(struct nfa *nfa,
}
}
+/*+ * removecantmatch - remove CANTMATCH arcs, which are no longer useful+ * once we are done with the parsing phase. (We need them only to+ * preserve connectedness of NFA subgraphs during parsing.)+ */+static void+removecantmatch(struct nfa *nfa)+{+ struct state *s;++ for (s = nfa->states; s != NULL; s = s->next)+ {+ struct arc *a;+ struct arc *nexta;++ for (a = s->outs; a != NULL; a = nexta)+ {+ nexta = a->outchain;+ if (a->type == CANTMATCH)+ {+ freearc(nfa, a);+ if (NISERR())+ return;+ }+ }+ }+}+
/*
* cleanup - clean up NFA after optimizations
*/
@@ -3627,6 +3662,8 @@ dumpnfa(struct nfa *nfa,
fprintf(f, ", eol [%ld]", (long) nfa->eos[1]);
if (nfa->flags & HASLACONS)
fprintf(f, ", haslacons");
+ if (nfa->flags & HASCANTMATCH)+ fprintf(f, ", hascantmatch");
if (nfa->flags & MATCHALL)
{
fprintf(f, ", minmatchall %d", nfa->minmatchall);
@@ -3749,6 +3786,9 @@ dumparc(struct arc *a,
break;
case EMPTY:
break;
+ case CANTMATCH:+ fprintf(f, "X");+ break;
default:
fprintf(f, "0x%x/0%lo", a->type, (long) a->co);
break;
diff --git a/src/backend/regex/regcomp.c b/src/backend/regex/regcomp.cindex 8a6cfb2973..15b264e50f 100644--- a/src/backend/regex/regcomp.c+++ b/src/backend/regex/regcomp.c@@ -215,6 +215,7 @@ static void clonesuccessorstates(struct nfa *nfa, struct state *ssource,
struct state *spredecessor,
struct arc *refarc, char *curdonemap,
char *outerdonemap, int nstates);
+static void removecantmatch(struct nfa *nfa);
static void cleanup(struct nfa *nfa);
static void markreachable(struct nfa *nfa, struct state *s,
struct state *okay, struct state *mark);
@@ -342,6 +343,7 @@ struct vars
#define BEHIND 'r' /* color-lookbehind arc */
#define WBDRY 'w' /* word boundary constraint */
#define NWBDRY 'W' /* non-word-boundary constraint */
+#define CANTMATCH 'x' /* arc that cannot match anything */
#define SBEGIN 'A' /* beginning of string (even if not BOL) */
#define SEND 'Z' /* end of string (even if not EOL) */
@@ -2368,6 +2370,7 @@ nfanode(struct vars *v,
nfa = newnfa(v, v->cm, v->nfa);
NOERRZ();
dupnfa(nfa, t->begin, t->end, nfa->init, nfa->final);
+ nfa->flags = v->nfa->flags;
if (!ISERR())
specialcolors(nfa);
if (!ISERR())
diff --git a/src/include/regex/regguts.h b/src/include/regex/regguts.hindex 3ca3647e11..fd69299a16 100644--- a/src/include/regex/regguts.h+++ b/src/include/regex/regguts.h@@ -410,6 +410,8 @@ struct cnfa
int flags; /* bitmask of the following flags: */
#define HASLACONS 01 /* uses lookaround constraints */
#define MATCHALL 02 /* matches all strings of a range of lengths */
+#define HASCANTMATCH 04 /* contains CANTMATCH arcs */+ /* Note: HASCANTMATCH appears in nfa structs' flags, but never in cnfas */
int pre; /* setup state number */
int post; /* teardown state number */
color bos[2]; /* colors, if any, assigned to BOS and BOL */
diff --git a/src/test/modules/test_regex/expected/test_regex.out b/src/test/modules/test_regex/expected/test_regex.outindex 731ba506d3..c44c717edf 100644--- a/src/test/modules/test_regex/expected/test_regex.out+++ b/src/test/modules/test_regex/expected/test_regex.out@@ -2071,6 +2071,20 @@ select * from test_regex('[\s\S]*', '012 3456789abc_*', 'LNPE');
{"012 3456789abc_*"}
(2 rows)
+-- bug #18708:+select * from test_regex('(?:[^\d\D]){0}', '0123456789abc*', 'LNPQE');+ test_regex +--------------------------------------------------------------------+ {0,REG_UBOUNDS,REG_UBBS,REG_UNONPOSIX,REG_ULOCALE,REG_UEMPTYMATCH}+ {""}+(2 rows)++select * from test_regex('[^\d\D]', '0123456789abc*', 'ILPE');+ test_regex +--------------------------------------------------------+ {0,REG_UBBS,REG_UNONPOSIX,REG_ULOCALE,REG_UIMPOSSIBLE}+(1 row)+
-- check char classes' handling of newlines
select * from test_regex('\s+', E'abc \n def', 'LP');
test_regex
diff --git a/src/test/modules/test_regex/sql/test_regex.sql b/src/test/modules/test_regex/sql/test_regex.sqlindex 478fa2c547..b2a847577e 100644--- a/src/test/modules/test_regex/sql/test_regex.sql+++ b/src/test/modules/test_regex/sql/test_regex.sql@@ -619,6 +619,9 @@ select * from test_regex('[^1\D0]', 'abc0123456789*', 'LPE');
select * from test_regex('\W', '0123456789abc_*', 'LP');
select * from test_regex('[\W]', '0123456789abc_*', 'LPE');
select * from test_regex('[\s\S]*', '012 3456789abc_*', 'LNPE');
+-- bug #18708:+select * from test_regex('(?:[^\d\D]){0}', '0123456789abc*', 'LNPQE');+select * from test_regex('[^\d\D]', '0123456789abc*', 'ILPE');
-- check char classes' handling of newlines
select * from test_regex('\s+', E'abc \n def', 'LP');
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-bugs@postgresql.org
Cc: tgl@sss.pgh.pa.us, aleksander@timescale.com, dhyan@nataraj.su, pgsql-bugs@lists.postgresql.org
Subject: Re: BUG #18708: regex problem: (?:[^\d\D]){0} asserts with "lp->nouts == 0 && rp->nins == 0"
In-Reply-To: <2344149.1731636867@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox