Fix potential infinite loop in regular expression execution.

tglsfdc · tglsfdc · commit 2a887828964e · 2015-10-02T14:26:36.000-04:00
In cfindloop(), if the initial call to shortest() reports that a zero-length match is possible at the current search start point, but then it is unable to construct any actual match to that, it'll just loop around with the same start point, and thus make no progress. We need to force the start point to be advanced. This is safe because the loop over "begin" points has already tried and failed to match starting at "close", so there is surely no need to try that again. This bug was introduced in commit e2bd904, wherein we allowed continued searching after we'd run out of match possibilities, but evidently failed to think hard enough about exactly where we needed to search next. Because of the way this code works, such a match failure is only possible in the presence of backrefs --- otherwise, shortest()'s judgment that a match is possible should always be correct. That probably explains how come the bug has escaped detection for several years. The actual fix is a one-liner, but I took the trouble to add/improve some comments related to the loop logic. After fixing that, the submitted test case "()*\1" didn't loop anymore. But it reported failure, though it seems like it ought to match a zero-length string; both Tcl and Perl think it does. That seems to be from overenthusiastic optimization on my part when I rewrote the iteration match logic in commit 173e29a: we can't just "declare victory" for a zero-length match without bothering to set match data for capturing parens inside the iterator node. Per fuzz testing by Greg Stark. The first part of this is a bug in all supported branches, and the second part is a bug since 9.2 where the iteration rewrite happened.
diff --git a/src/backend/regex/regexec.c b/src/backend/regex/regexec.c
@@ -423,6 +423,7 @@ cfindloop(struct vars * v,
 	close = v->search_start;
 	do
 	{
+		/* Search with the search RE for match range at/beyond "close" */
 		MDEBUG(("\ncsearch at %ld\n", LOFF(close)));
 		close = shortest(v, s, close, close, v->stop, &cold, (int *) NULL);
 		if (ISERR())
@@ -431,10 +432,11 @@ cfindloop(struct vars * v,
 			return v->err;
 		}
 		if (close == NULL)
-			break;				/* NOTE BREAK */
+			break;				/* no more possible match anywhere */
 		assert(cold != NULL);
 		open = cold;
 		cold = NULL;
+		/* Search for matches starting between "open" and "close" inclusive */
 		MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close)));
 		for (begin = open; begin <= close; begin++)
 		{
@@ -443,6 +445,7 @@ cfindloop(struct vars * v,
 			estop = v->stop;
 			for (;;)
 			{
+				/* Here we use the top node's detailed RE */
 				if (shorter)
 					end = shortest(v, d, begin, estart,
 								   estop, (chr **) NULL, &hitend);
@@ -457,8 +460,9 @@ cfindloop(struct vars * v,
 				if (hitend && cold == NULL)
 					cold = begin;
 				if (end == NULL)
-					break;		/* NOTE BREAK OUT */
+					break;		/* no match with this begin point, try next */
 				MDEBUG(("tentative end %ld\n", LOFF(end)));
+				/* Dissect the potential match to see if it really matches */
 				zapsubs(v->pmatch, v->nmatch);
 				zapmem(v, v->g->tree);
 				er = cdissect(v, v->g->tree, begin, end);
@@ -478,21 +482,28 @@ cfindloop(struct vars * v,
 					*coldp = cold;
 					return er;
 				}
-				/* try next shorter/longer match with same begin point */
+				/* Try next longer/shorter match with same begin point */
 				if (shorter)
 				{
 					if (end == estop)
-						break;	/* NOTE BREAK OUT */
+						break;	/* no more, so try next begin point */
 					estart = end + 1;
 				}
 				else
 				{
 					if (end == begin)
-						break;	/* NOTE BREAK OUT */
+						break;	/* no more, so try next begin point */
 					estop = end - 1;
 				}
 			}					/* end loop over endpoint positions */
 		}						/* end loop over beginning positions */
+
+		/*
+		 * If we get here, there is no possible match starting at or before
+		 * "close", so consider matches beyond that.  We'll do a fresh search
+		 * with the search RE to find a new promising match range.
+		 */
+		close++;
 	} while (close < v->stop);
 
 	*coldp = cold;
