From: Tom Lane <tgl@sss.pgh.pa.us>
To: Mark Dilger <mark.dilger@enterprisedb.com>
cc: Andrew Dunstan <andrew@dunslane.net>,
        PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>,
        Joel Jacobson <joel@compiler.org>
Subject: Re: Another regexp performance improvement: skip useless
 paren-captures
In-reply-to: <A099E4A8-4377-4C64-A98C-3DEDDC075502@enterprisedb.com>
References: <2219936.1628115334@sss.pgh.pa.us>
 <31908a04-f73b-8c5b-ed99-919fd4cd4b54@dunslane.net>
 <2390507.1628174181@sss.pgh.pa.us>
 <2BFE7DFD-8537-4B4E-BC4C-2F265A836651@enterprisedb.com>
 <3173384.1628442278@sss.pgh.pa.us>
 <BDB634FD-2EE5-4697-91A0-1F53E1363D3B@enterprisedb.com>
 <3224306.1628454300@sss.pgh.pa.us>
 <D6AF940F-C48A-4666-A6E0-B92FC96F0711@enterprisedb.com>
 <3289730.1628461693@sss.pgh.pa.us>
 <B323249F-B221-4DCE-8763-E5070A77452E@enterprisedb.com>
 <3534632.1628536485@sss.pgh.pa.us>
 <A099E4A8-4377-4C64-A98C-3DEDDC075502@enterprisedb.com>
Comments: In-reply-to Mark Dilger <mark.dilger@enterprisedb.com>
	message dated "Mon, 09 Aug 2021 14:01:13 -0700"
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0"
Content-ID: <3643722.1628551890.0@sss.pgh.pa.us>
Date: Mon, 09 Aug 2021 19:31:41 -0400
Message-ID: <3643732.1628551901@sss.pgh.pa.us>
Archived-At: 
 <https://www.postgresql.org/message-id/3643732.1628551901%40sss.pgh.pa.us>
Precedence: bulk

------- =_aaaaaaaaaa0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <3643722.1628551890.1@sss.pgh.pa.us>

Mark Dilger <mark.dilger@enterprisedb.com> writes:
> +select regexp_split_to_array('', '(?:((?:q+))){0}(\1){0,0}?*[^]');
> +server closed the connection unexpectedly

Here's a quick draft patch for this.  Basically it moves the
responsibility for clearing v->subs[] pointers into the freesubre()
recursion, so that it will happen for contained capturing parens
not only the top level.

There is a potentially interesting definitional question:
what exactly ought this regexp do?

		((.)){0}\2

Because the capturing paren sets are zero-quantified, they will
never be matched to any characters, so the backref can never
have any defined referent.  I suspect that study of the POSIX
spec would lead to the conclusion that this is a legal regexp
but it will never match anything.  Implementing that would be
tedious though, and what's more it seems very unlikely that
the user wanted any such behavior.  So I think throwing an
error is an appropriate response.  The existing code will
throw such an error for

		((.)){0}\1

so I guess Spencer did think about this to some extent -- he
just forgot about the possibility of nested parens.

This patch should work OK in HEAD and v14, but it will need
a bit of fooling-about for older branches I think, given that
they fill v->subs[] a little differently.

			regards, tom lane


------- =_aaaaaaaaaa0
Content-Type: text/x-diff; name="fix-zero-quantified-nested-parens.patch";
	charset="us-ascii"
Content-ID: <3643722.1628551890.2@sss.pgh.pa.us>
Content-Description: fix-zero-quantified-nested-parens.patch
Content-Transfer-Encoding: quoted-printable

diff --git a/src/backend/regex/regcomp.c b/src/backend/regex/regcomp.c
index ae3a7b6a38..ae1ff670f9 100644
--- a/src/backend/regex/regcomp.c
+++ b/src/backend/regex/regcomp.c
@@ -550,8 +550,6 @@ freev(struct vars *v,
 {
 	if (v->re !=3D NULL)
 		rfree(v->re);
-	if (v->subs !=3D v->sub10)
-		FREE(v->subs);
 	if (v->nfa !=3D NULL)
 		freenfa(v->nfa);
 	if (v->tree !=3D NULL)
@@ -562,6 +560,8 @@ freev(struct vars *v,
 		freecvec(v->cv);
 	if (v->cv2 !=3D NULL)
 		freecvec(v->cv2);
+	if (v->subs !=3D v->sub10)
+		FREE(v->subs);
 	if (v->lacons !=3D NULL)
 		freelacons(v->lacons, v->nlacons);
 	ERR(err);					/* nop if err=3D=3D0 */
@@ -1091,8 +1091,8 @@ parseqatom(struct vars *v,
 	{
 		if (atom !=3D NULL)
 			freesubre(v, atom);
-		if (atomtype =3D=3D '(')
-			v->subs[subno] =3D NULL;
+		/* freesubre() will clean up any v->subs[] pointers into the atom */
+		assert(atomtype !=3D '(' || v->subs[subno] =3D=3D NULL);
 		delsub(v->nfa, lp, rp);
 		EMPTYARC(lp, rp);
 		return top;
@@ -2127,9 +2127,24 @@ freesrnode(struct vars *v,		/* might be NULL */
 	if (sr =3D=3D NULL)
 		return;
 =

+	/*
+	 * If the node is referenced in v->subs[], clear that to avoid leaving a
+	 * dangling pointer.  This should only ever matter when parseqatom() is
+	 * throwing away a {0,0}-quantified atom that contains capturing parens.
+	 * Doing this will cause later backrefs to such parens to fail, which is
+	 * maybe not strictly POSIX but seems more helpful than allowing a backr=
ef
+	 * that can never have a defined referent.
+	 */
+	if (sr->capno > 0 && v !=3D NULL)
+	{
+		assert(v->subs[sr->capno] =3D=3D sr);
+		v->subs[sr->capno] =3D NULL;
+	}
+
 	if (!NULLCNFA(sr->cnfa))
 		freecnfa(&sr->cnfa);
 	sr->flags =3D 0;				/* in particular, not INUSE */
+	sr->capno =3D 0;
 	sr->child =3D sr->sibling =3D NULL;
 	sr->begin =3D sr->end =3D NULL;
 =

diff --git a/src/test/modules/test_regex/expected/test_regex.out b/src/tes=
t/modules/test_regex/expected/test_regex.out
index 5a6cdf47c2..850e0c8ef5 100644
--- a/src/test/modules/test_regex/expected/test_regex.out
+++ b/src/test/modules/test_regex/expected/test_regex.out
@@ -3506,6 +3506,10 @@ select * from test_regex('((.))(\2)', 'xyy', 'oRP')=
;
  {yy,NULL,NULL,NULL}
 (2 rows)
 =

+-- # throwing an error for this is arguably not per POSIX
+-- expectError	21.39 -		{((.)){0}(\2){0}}	ESUBREG
+select * from test_regex('((.)){0}(\2){0}', '', '-');
+ERROR:  invalid regular expression: invalid backreference number
 -- doing 22 "multicharacter collating elements"
 -- # again ugh
 -- MCCEs are not implemented in Postgres, so we skip all these tests
diff --git a/src/test/modules/test_regex/sql/test_regex.sql b/src/test/mod=
ules/test_regex/sql/test_regex.sql
index 3419564203..378f22b67b 100644
--- a/src/test/modules/test_regex/sql/test_regex.sql
+++ b/src/test/modules/test_regex/sql/test_regex.sql
@@ -1020,6 +1020,9 @@ select * from test_regex('((.))(\2){0}', 'xy', 'RPQ'=
);
 select * from test_regex('((.))(\2)', 'xyy', 'RP');
 -- expectMatch	21.38 oRP	((.))(\2)	xyy	yy	{}	{}	{}
 select * from test_regex('((.))(\2)', 'xyy', 'oRP');
+-- # throwing an error for this is arguably not per POSIX
+-- expectError	21.39 -		{((.)){0}(\2){0}}	ESUBREG
+select * from test_regex('((.)){0}(\2){0}', '', '-');
 =

 -- doing 22 "multicharacter collating elements"
 -- # again ugh

------- =_aaaaaaaaaa0--