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: <1303A200-4615-4559-961A-CC906DE07EAF@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>
 <3643732.1628551901@sss.pgh.pa.us>
 <1303A200-4615-4559-961A-CC906DE07EAF@enterprisedb.com>
Comments: In-reply-to Mark Dilger <mark.dilger@enterprisedb.com>
	message dated "Mon, 09 Aug 2021 18:38:33 -0700"
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0"
Content-ID: <3756736.1628561894.0@sss.pgh.pa.us>
Date: Mon, 09 Aug 2021 22:20:33 -0400
Message-ID: <3756810.1628562033@sss.pgh.pa.us>
Archived-At: 
 <https://www.postgresql.org/message-id/3756810.1628562033%40sss.pgh.pa.us>
Precedence: bulk

------- =_aaaaaaaaaa0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <3756736.1628561894.1@sss.pgh.pa.us>
Content-Transfer-Encoding: quoted-printable

Mark Dilger <mark.dilger@enterprisedb.com> writes:
> I ran a lot of tests with the patch, and the asserts have all cleared up=
, but I don't know how to think about the user facing differences.  If we =
had a good reason for raising an error for these back-references, maybe th=
at'd be fine, but it seems to just be an implementation detail.

I thought about this some more, and I'm coming around to the idea that
throwing an error is the wrong thing.  As a contrary example, consider

	(.)|(\1\1)

We don't throw an error for this, and neither does Perl, even though
the capturing parens can never be defined in the branch where the
backrefs are.  So it seems hard to argue that this is okay but the
other thing isn't.  Another interesting example is

	(.){0}(\1){0}

I think that the correct interpretation is that this is a valid
regexp matching an empty string (i.e., zero repetitions of each
part), even though neither capture group will be defined.
That's different from

	(.){0}(\1)

which can never match.

So I took another look at the code, and it doesn't seem that hard
to make it act this way.  The attached passes regression, but
I've not beat on it with random strings.

			regards, tom lane


------- =_aaaaaaaaaa0
Content-Type: text/x-diff;
	name="alternate-fix-zero-quantified-nested-parens.patch";
	charset="us-ascii"
Content-ID: <3756736.1628561894.2@sss.pgh.pa.us>
Content-Description: alternate-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..d9840171a3 100644
--- a/src/backend/regex/regcomp.c
+++ b/src/backend/regex/regcomp.c
@@ -1089,11 +1089,23 @@ parseqatom(struct vars *v,
 	/* annoying special case:  {0} or {0,0} cancels everything */
 	if (m =3D=3D 0 && n =3D=3D 0)
 	{
-		if (atom !=3D NULL)
-			freesubre(v, atom);
-		if (atomtype =3D=3D '(')
-			v->subs[subno] =3D NULL;
-		delsub(v->nfa, lp, rp);
+		/*
+		 * If we had capturing subexpression(s) within the atom, we don't want
+		 * to destroy them, because it's legal (if useless) to back-ref them
+		 * later.  Hence, just unlink the atom from lp/rp and then ignore it.
+		 */
+		if (atom !=3D NULL && (atom->flags & CAP))
+		{
+			delsub(v->nfa, lp, atom->begin);
+			delsub(v->nfa, atom->end, rp);
+		}
+		else
+		{
+			/* Otherwise, we can clean up any subre infrastructure we made */
+			if (atom !=3D NULL)
+				freesubre(v, atom);
+			delsub(v->nfa, lp, rp);
+		}
 		EMPTYARC(lp, rp);
 		return top;
 	}
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..96c0e6fa59 100644
--- a/src/test/modules/test_regex/expected/test_regex.out
+++ b/src/test/modules/test_regex/expected/test_regex.out
@@ -3506,6 +3506,21 @@ select * from test_regex('((.))(\2)', 'xyy', 'oRP')=
;
  {yy,NULL,NULL,NULL}
 (2 rows)
 =

+-- expectMatch	21.39 NPQR	{((.)){0}(\2){0}}	xyz	{}	{}	{}	{}
+select * from test_regex('((.)){0}(\2){0}', 'xyz', 'NPQR');
+                         test_regex                         =

+------------------------------------------------------------
+ {3,REG_UBACKREF,REG_UBOUNDS,REG_UNONPOSIX,REG_UEMPTYMATCH}
+ {"",NULL,NULL,NULL}
+(2 rows)
+
+-- expectNomatch	21.40 PQR	{((.)){0}(\2)}	xxx
+select * from test_regex('((.)){0}(\2)', 'xxx', 'PQR');
+                 test_regex                 =

+--------------------------------------------
+ {3,REG_UBACKREF,REG_UBOUNDS,REG_UNONPOSIX}
+(1 row)
+
 -- 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..29806e9417 100644
--- a/src/test/modules/test_regex/sql/test_regex.sql
+++ b/src/test/modules/test_regex/sql/test_regex.sql
@@ -1020,6 +1020,10 @@ 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');
+-- expectMatch	21.39 NPQR	{((.)){0}(\2){0}}	xyz	{}	{}	{}	{}
+select * from test_regex('((.)){0}(\2){0}', 'xyz', 'NPQR');
+-- expectNomatch	21.40 PQR	{((.)){0}(\2)}	xxx
+select * from test_regex('((.)){0}(\2)', 'xxx', 'PQR');
 =

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

------- =_aaaaaaaaaa0--