* generic/regc_nfa.c: Fixed infinite loop in the regexp compiler

        * generic/regcomp.c:    [Bug 1810038].  Corrected looping logic in
        * tests/regexp.test:    fixempties() to avoid wasting time walking a
        list of dead states [Bug 1832612].  Convert optst() from expensive
        no-op to a cheap no-op.  Improve newline usage in debug output.

1 files changed, 45 insertions, 1 deletions

diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c
index 9881cd4..dd26e64 100644
--- a/generic/regc_nfa.c
+++ b/generic/regc_nfa.c
@@ -803,6 +803,26 @@ struct arc *con;
 		return 1;
 	}
 
+	/*
+	 * DGP 2007-11-15: Cloning a state with a circular constraint on its
+	 * list of outs can lead to trouble [Bug 1810038], so get rid of them
+	 * first.
+	 */
+
+	for (a = from->outs; a != NULL; a = nexta) {
+		nexta = a->outchain;
+		switch (a->type) {
+		case '^':
+		case '$':
+		case BEHIND:
+		case AHEAD:
+			if (from == a->to) {
+				freearc(nfa, a);
+			}
+			break;
+		}
+	}
+
 	/* first, clone from state if necessary to avoid other outarcs */
 	if (from->nouts > 1) {
 		s = newstate(nfa);
@@ -921,6 +941,29 @@ struct arc *con;
 		return 1;
 	}
 
+	/*
+	 * DGP 2007-11-15: Here we duplicate the same protections as appear
+	 * in pull() above to avoid troubles with cloning a state with a
+	 * circular constraint on its list of ins.  It is not clear whether
+	 * this is necessary, or is protecting against a "can't happen".
+	 * Any test case that actually leads to a freearc() call here would
+	 * be a welcome addition to the test suite.
+	 */
+
+	for (a = to->ins; a != NULL; a = nexta) {
+		nexta = a->inchain;
+		switch (a->type) {
+		case '^':
+		case '$':
+		case BEHIND:
+		case AHEAD:
+			if (a->from == to) {
+				freearc(nfa, a);
+			}
+			break;
+		}
+	}
+
 	/* first, clone to state if necessary to avoid other inarcs */
 	if (to->nins > 1) {
 		s = newstate(nfa);
@@ -1041,7 +1084,8 @@ FILE *f;			/* for debug output; NULL none */
 	/* find and eliminate empties until there are no more */
 	do {
 		progress = 0;
-		for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
+		for (s = nfa->states; s != NULL && !NISERR()
+			&& s->no != FREESTATE; s = nexts) {
 			nexts = s->next;
 			for (a = s->outs; a != NULL && !NISERR(); a = nexta) {
 				nexta = a->outchain;