Skip to content

Commit 1fee1bf

Browse files
tglsfdctglsfdc
committed
Fix regex back-references that are directly quantified with *.
The syntax "\n*", that is a backref with a * quantifier directly applied to it, has never worked correctly in Spencer's library. This has been an open bug in the Tcl bug tracker since 2005: https://sourceforge.net/tracker/index.php?func=detail&aid=1115587&group_id=10894&atid=110894 The core of the problem is in parseqatom(), which first changes "\n*" to "\n+|" and then applies repeat() to the NFA representing the backref atom. repeat() thinks that any arc leading into its "rp" argument is part of the sub-NFA to be repeated. Unfortunately, since parseqatom() already created the arc that was intended to represent the empty bypass around "\n+", this arc gets moved too, so that it now leads into the state loop created by repeat(). Thus, what was supposed to be an "empty" bypass gets turned into something that represents zero or more repetitions of the NFA representing the backref atom. In the original example, in place of ^([bc])\1*$ we now have something that acts like ^([bc])(\1+|[bc]*)$ At runtime, the branch involving the actual backref fails, as it's supposed to, but then the other branch succeeds anyway. We could no doubt fix this by some rearrangement of the operations in parseqatom(), but that code is plenty ugly already, and what's more the whole business of converting "x*" to "x+|" probably needs to go away to fix another problem I'll mention in a moment. Instead, this patch suppresses the *-conversion when the target is a simple backref atom, leaving the case of m == 0 to be handled at runtime. This makes the patch in regcomp.c a one-liner, at the cost of having to tweak cbrdissect() a little. In the event I went a bit further than that and rewrote cbrdissect() to check all the string-length-related conditions before it starts comparing characters. It seems a bit stupid to possibly iterate through many copies of an n-character backreference, only to fail at the end because the target string's length isn't a multiple of n --- we could have found that out before starting. The existing coding could only be a win if integer division is hugely expensive compared to character comparison, but I don't know of any modern machine where that might be true. This does not fix all the problems with quantified back-references. In particular, the code is still broken for back-references that appear within a larger expression that is quantified (so that direct insertion of the quantification limits into the BACKREF node doesn't apply). I think fixing that will take some major surgery on the NFA code, specifically introducing an explicit iteration node type instead of trying to transform iteration into concatenation of modified regexps. Back-patch to all supported branches. In HEAD, also add a regression test case for this. (It may seem a bit silly to create a regression test file for just one test case; but I'm expecting that we will soon import a whole bunch of regex regression tests from Tcl, so might as well create the infrastructure now.)
1 parent f559846 commit 1fee1bf

File tree

2 files changed

+52
-29
lines changed

2 files changed

+52
-29
lines changed

‎src/backend/regex/regcomp.c

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1080,8 +1080,12 @@ parseqatom(struct vars * v,
10801080
NOERR();
10811081
}
10821082

1083-
/* it's quantifier time; first, turn x{0,...} into x{1,...}|empty */
1084-
if (m == 0)
1083+
/*
1084+
* It's quantifier time. If the atom is just a BACKREF, we'll let it deal
1085+
* with quantifiers internally. Otherwise, the first step is to turn
1086+
* x{0,...} into x{1,...}|empty
1087+
*/
1088+
if (m == 0 && atomtype != BACKREF)
10851089
{
10861090
EMPTYARC(s2, atom->end); /* the bypass */
10871091
assert(PREF(qprefer) != 0);

‎src/backend/regex/regexec.c

Lines changed: 46 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -716,7 +716,7 @@ cdissect(struct vars * v,
716716
case '|': /* alternation */
717717
assert(t->left != NULL);
718718
return caltdissect(v, t, begin, end);
719-
case 'b': /* back ref -- shouldn't be calling us! */
719+
case 'b': /* back reference */
720720
assert(t->left == NULL && t->right == NULL);
721721
return cbrdissect(v, t, begin, end);
722722
case '.': /* concatenation */
@@ -973,12 +973,12 @@ cbrdissect(struct vars * v,
973973
chr *begin, /* beginning of relevant substring */
974974
chr *end) /* end of same */
975975
{
976-
int i;
977976
int n = t->subno;
978-
size_t len;
979-
chr *paren;
977+
size_t numreps;
978+
size_t tlen;
979+
size_t brlen;
980+
chr *brstring;
980981
chr *p;
981-
chr *stop;
982982
int min = t->min;
983983
int max = t->max;
984984

@@ -989,46 +989,65 @@ cbrdissect(struct vars * v,
989989

990990
MDEBUG(("cbackref n%d %d{%d-%d}\n", t->retry, n, min, max));
991991

992+
/* get the backreferenced string */
992993
if (v->pmatch[n].rm_so == -1)
993994
return REG_NOMATCH;
994-
paren = v->start + v->pmatch[n].rm_so;
995-
len = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;
995+
brstring = v->start + v->pmatch[n].rm_so;
996+
brlen = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;
996997

997998
/* no room to maneuver -- retries are pointless */
998999
if (v->mem[t->retry])
9991000
return REG_NOMATCH;
10001001
v->mem[t->retry] = 1;
10011002

1002-
/* special-case zero-length string */
1003-
if (len == 0)
1003+
/* special cases for zero-length strings */
1004+
if (brlen == 0)
1005+
{
1006+
/*
1007+
* matches only if target is zero length, but any number of
1008+
* repetitions can be considered to be present
1009+
*/
1010+
if (begin == end && min <= max)
1011+
{
1012+
MDEBUG(("cbackref matched trivially\n"));
1013+
return REG_OKAY;
1014+
}
1015+
return REG_NOMATCH;
1016+
}
1017+
if (begin == end)
10041018
{
1005-
if (begin == end)
1019+
/* matches only if zero repetitions are okay */
1020+
if (min == 0)
1021+
{
1022+
MDEBUG(("cbackref matched trivially\n"));
10061023
return REG_OKAY;
1024+
}
10071025
return REG_NOMATCH;
10081026
}
10091027

1010-
/* and too-short string */
1011-
assert(end >= begin);
1012-
if ((size_t) (end - begin) < len)
1028+
/*
1029+
* check target length to see if it could possibly be an allowed number of
1030+
* repetitions of brstring
1031+
*/
1032+
assert(end > begin);
1033+
tlen = end - begin;
1034+
if (tlen % brlen != 0)
1035+
return REG_NOMATCH;
1036+
numreps = tlen / brlen;
1037+
if (numreps < min || (numreps > max && max != INFINITY))
10131038
return REG_NOMATCH;
1014-
stop = end - len;
10151039

1016-
/* count occurrences */
1017-
i = 0;
1018-
for (p = begin; p <= stop && (i < max || max == INFINITY); p += len)
1040+
/* okay, compare the actual string contents */
1041+
p = begin;
1042+
while (numreps-- > 0)
10191043
{
1020-
if ((*v->g->compare) (paren, p, len) != 0)
1021-
break;
1022-
i++;
1044+
if ((*v->g->compare) (brstring, p, brlen) != 0)
1045+
return REG_NOMATCH;
1046+
p += brlen;
10231047
}
1024-
MDEBUG(("cbackref found %d\n", i));
10251048

1026-
/* and sort it out */
1027-
if (p != end) /* didn't consume all of it */
1028-
return REG_NOMATCH;
1029-
if (min <= i && (i <= max || max == INFINITY))
1030-
return REG_OKAY;
1031-
return REG_NOMATCH; /* out of range */
1049+
MDEBUG(("cbackref matched\n"));
1050+
return REG_OKAY;
10321051
}
10331052

10341053
/*

0 commit comments

Comments
 (0)